neels has uploaded this change for review. ( https://gerrit.osmocom.org/c/libosmocore/+/36913?usp=email )
Change subject: add jhash.h, copied from linux/jhash.h ...................................................................... add jhash.h, copied from linux/jhash.h Allow using arbitrary length data as hashtable key: Copy jhash.h implementation from the linux kernel. Apply osmo_ prefix to all global symbols. Add jhash_test to ensure the code import works as intended. First application will be a hashtable keyed by umts_cell_id in osmo-hnbgw.git. Related: SYS#6773 Change-Id: I0c9652bbc9e2a18b1200e7d63bb6f64ded7d75fa --- M include/osmocom/core/Makefile.am A include/osmocom/core/jhash.h M tests/Makefile.am A tests/jhash/jhash_test.c A tests/jhash/jhash_test.ok M tests/testsuite.at 6 files changed, 304 insertions(+), 2 deletions(-) git pull ssh://gerrit.osmocom.org:29418/libosmocore refs/changes/13/36913/1 diff --git a/include/osmocom/core/Makefile.am b/include/osmocom/core/Makefile.am index 7c29ca1..980f813 100644 --- a/include/osmocom/core/Makefile.am +++ b/include/osmocom/core/Makefile.am @@ -27,6 +27,7 @@ hashtable.h \ isdnhdlc.h \ it_q.h \ + jhash.h \ linuxlist.h \ linuxrbtree.h \ log2.h \ diff --git a/include/osmocom/core/jhash.h b/include/osmocom/core/jhash.h new file mode 100644 index 0000000..a63e930 --- /dev/null +++ b/include/osmocom/core/jhash.h @@ -0,0 +1,191 @@ +#pragma once +#include <osmocom/core/bit32gen.h> + +/* Below is a partial copy of + * https://raw.githubusercontent.com/torvalds/linux/master/tools/include/linux/bitops.h + * with an osmo_ prefix applied to avoid any collisions. + */ +/* SPDX-License-Identifier: GPL-2.0 */ +/** + * rol32 - rotate a 32-bit value left + * @word: value to rotate + * @shift: bits to roll + */ +static inline uint32_t osmo_rol32(uint32_t word, unsigned int shift) +{ + return (word << shift) | (word >> ((-shift) & 31)); +} + +/* Below is a copy of + * https://raw.githubusercontent.com/torvalds/linux/79e3ea5aab48c83de9410e43b52895406847eca7/tools/include/linux/jhash.h + * with an osmo_ prefix applied to avoid any collisions. + * Using osmo_load32le() instead of __get_unaligned_cpu32(). + */ +/* jhash.h: Jenkins hash support. + * + * Copyright (C) 2006. Bob Jenkins (bob_jenk...@burtleburtle.net) + * + * https://burtleburtle.net/bob/hash/ + * + * These are the credits from Bob's sources: + * + * lookup3.c, by Bob Jenkins, May 2006, Public Domain. + * + * These are functions for producing 32-bit hashes for hash table lookup. + * hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() + * are externally useful functions. Routines to test the hash are included + * if SELF_TEST is defined. You can use this free for any purpose. It's in + * the public domain. It has no warranty. + * + * Copyright (C) 2009-2010 Jozsef Kadlecsik (kad...@blackhole.kfki.hu) + * + * I've modified Bob's hash to be useful in the Linux kernel, and + * any bugs present are my fault. + * Jozsef + */ + +/* Best hash sizes are of power of two */ +#define osmo_jhash_size(n) ((uint32_t)1<<(n)) +/* Mask the hash value, i.e (value & osmo_jhash_mask(n)) instead of (value % n) */ +#define osmo_jhash_mask(n) (osmo_jhash_size(n)-1) + +/* __osmo_jhash_mix -- mix 3 32-bit values reversibly. */ +#define __osmo_jhash_mix(a, b, c) \ +{ \ + a -= c; a ^= osmo_rol32(c, 4); c += b; \ + b -= a; b ^= osmo_rol32(a, 6); a += c; \ + c -= b; c ^= osmo_rol32(b, 8); b += a; \ + a -= c; a ^= osmo_rol32(c, 16); c += b; \ + b -= a; b ^= osmo_rol32(a, 19); a += c; \ + c -= b; c ^= osmo_rol32(b, 4); b += a; \ +} + +/* __osmo_jhash_final - final mixing of 3 32-bit values (a,b,c) into c */ +#define __osmo_jhash_final(a, b, c) \ +{ \ + c ^= b; c -= osmo_rol32(b, 14); \ + a ^= c; a -= osmo_rol32(c, 11); \ + b ^= a; b -= osmo_rol32(a, 25); \ + c ^= b; c -= osmo_rol32(b, 16); \ + a ^= c; a -= osmo_rol32(c, 4); \ + b ^= a; b -= osmo_rol32(a, 14); \ + c ^= b; c -= osmo_rol32(b, 24); \ +} + +/* An arbitrary initial parameter */ +#define JHASH_INITVAL 0xdeadbeef + +/* osmo_jhash - hash an arbitrary key + * @k: sequence of bytes as key + * @length: the length of the key + * @initval: the previous hash, or an arbitray value + * + * The generic version, hashes an arbitrary sequence of bytes. + * No alignment or length assumptions are made about the input key. + * + * Returns the hash value of the key. The result depends on endianness. + */ +static inline uint32_t osmo_jhash(const void *key, uint32_t length, uint32_t initval) +{ + uint32_t a, b, c; + const uint8_t *k = key; + + /* Set up the internal state */ + a = b = c = JHASH_INITVAL + length + initval; + + /* All but the last block: affect some 32 bits of (a,b,c) */ + while (length > 12) { + a += osmo_load32le(k); + b += osmo_load32le(k + 4); + c += osmo_load32le(k + 8); + __osmo_jhash_mix(a, b, c); + length -= 12; + k += 12; + } + /* Last block: affect all 32 bits of (c) */ + /* All the case statements fall through */ + switch (length) { + case 12: c += (uint32_t)k[11]<<24; + case 11: c += (uint32_t)k[10]<<16; + case 10: c += (uint32_t)k[9]<<8; + case 9: c += k[8]; + case 8: b += (uint32_t)k[7]<<24; + case 7: b += (uint32_t)k[6]<<16; + case 6: b += (uint32_t)k[5]<<8; + case 5: b += k[4]; + case 4: a += (uint32_t)k[3]<<24; + case 3: a += (uint32_t)k[2]<<16; + case 2: a += (uint32_t)k[1]<<8; + case 1: a += k[0]; + __osmo_jhash_final(a, b, c); + case 0: /* Nothing left to add */ + break; + } + + return c; +} + +/* osmo_jhash2 - hash an array of uint32_t's + * @k: the key which must be an array of uint32_t's + * @length: the number of uint32_t's in the key + * @initval: the previous hash, or an arbitray value + * + * Returns the hash value of the key. + */ +static inline uint32_t osmo_jhash2(const uint32_t *k, uint32_t length, uint32_t initval) +{ + uint32_t a, b, c; + + /* Set up the internal state */ + a = b = c = JHASH_INITVAL + (length<<2) + initval; + + /* Handle most of the key */ + while (length > 3) { + a += k[0]; + b += k[1]; + c += k[2]; + __osmo_jhash_mix(a, b, c); + length -= 3; + k += 3; + } + + /* Handle the last 3 uint32_t's: all the case statements fall through */ + switch (length) { + case 3: c += k[2]; + case 2: b += k[1]; + case 1: a += k[0]; + __osmo_jhash_final(a, b, c); + case 0: /* Nothing left to add */ + break; + } + + return c; +} + + +/* __osmo_jhash_nwords - hash exactly 3, 2 or 1 word(s) */ +static inline uint32_t __osmo_jhash_nwords(uint32_t a, uint32_t b, uint32_t c, uint32_t initval) +{ + a += initval; + b += initval; + c += initval; + + __osmo_jhash_final(a, b, c); + + return c; +} + +static inline uint32_t osmo_jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval) +{ + return __osmo_jhash_nwords(a, b, c, initval + JHASH_INITVAL + (3 << 2)); +} + +static inline uint32_t osmo_jhash_2words(uint32_t a, uint32_t b, uint32_t initval) +{ + return __osmo_jhash_nwords(a, b, 0, initval + JHASH_INITVAL + (2 << 2)); +} + +static inline uint32_t osmo_jhash_1word(uint32_t a, uint32_t initval) +{ + return __osmo_jhash_nwords(a, 0, 0, initval + JHASH_INITVAL + (1 << 2)); +} diff --git a/tests/Makefile.am b/tests/Makefile.am index 58900d3..1e8997c 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -59,6 +59,7 @@ osmo_io/osmo_io_test \ soft_uart/soft_uart_test \ rlp/rlp_test \ + jhash/jhash_test \ $(NULL) if ENABLE_MSGFILE @@ -391,6 +392,7 @@ rlp_rlp_test_SOURCES = rlp/rlp_test.c rlp_rlp_test_LDADD = $(top_builddir)/src/gsm/libosmogsm.la $(LDADD) +jhash_jhash_test_SOURCES = jhash/jhash_test.c # The `:;' works around a Bash 3.2 bug when the output is not writeable. $(srcdir)/package.m4: $(top_srcdir)/configure.ac @@ -505,6 +507,7 @@ soft_uart/soft_uart_test.ok \ rlp/rlp_test.ok \ socket/socket_sctp_test.ok socket/socket_sctp_test.err \ + jhash/jhash_test.ok \ $(NULL) if ENABLE_LIBSCTP @@ -729,8 +732,9 @@ soft_uart/soft_uart_test \ >$(srcdir)/soft_uart/soft_uart_test.ok rlp/rlp_test \ - >$(srcdir)/rlp/rlp_test.ok \ - $(NULL) + >$(srcdir)/rlp/rlp_test.ok + jhash/jhash_test \ + >$(srcdir)/jhash/jhash_test.ok check-local: atconfig $(TESTSUITE) diff --git a/tests/jhash/jhash_test.c b/tests/jhash/jhash_test.c new file mode 100644 index 0000000..da498c8 --- /dev/null +++ b/tests/jhash/jhash_test.c @@ -0,0 +1,56 @@ +#include <osmocom/core/linuxlist.h> +#include <osmocom/core/hashtable.h> +#include <osmocom/core/jhash.h> + +struct item { + const char blob[32]; + struct hlist_node node; +}; + +struct item items[] = { + { "blob one", }, + { "blob two and five are the same", }, + { "third blob", }, + { "fourth blob", }, + { "blob two and five are the same", }, +}; + +uint32_t item_hash(const struct item *item) +{ + return osmo_jhash(item->blob, strlen(item->blob), 0); +} + +int main(void) +{ + int i; + struct item *item; + + DECLARE_HASHTABLE(haystack, 5); + hash_init(haystack); + + printf("add:\n"); + for (i = 0; i < ARRAY_SIZE(items); i++) { + uint32_t hash; + item = &items[i]; + hash_add(haystack, &item->node, hash = item_hash(item)); + printf("- adding items[%d]#%x = %s\n", i, hash, item->blob); + } + + printf("list:\n"); + hash_for_each(haystack, i, item, node) + printf("- %s [%d]\n", item->blob, (int)(item - items)); + + printf("find:\n"); + for (i = 0; i < ARRAY_SIZE(items); i++) { + uint32_t hash; + struct item *needle = &items[i]; + hash = item_hash(needle); + printf("- looking up items[%d]#%x = %s\n", i, hash, needle->blob); + hash_for_each_possible(haystack, item, node, hash) + printf(" - %s items[%d]\n", + (item == needle) ? "found" : "not", + (int)(item - items)); + } + + return 0; +} diff --git a/tests/jhash/jhash_test.ok b/tests/jhash/jhash_test.ok new file mode 100644 index 0000000..e28ccc4 --- /dev/null +++ b/tests/jhash/jhash_test.ok @@ -0,0 +1,25 @@ +add: +- adding items[0]#b286bb61 = blob one +- adding items[1]#ad4eb7b = blob two and five are the same +- adding items[2]#6b8eae61 = third blob +- adding items[3]#24a546dc = fourth blob +- adding items[4]#ad4eb7b = blob two and five are the same +list: +- blob two and five are the same [4] +- blob two and five are the same [1] +- blob one [0] +- fourth blob [3] +- third blob [2] +find: +- looking up items[0]#b286bb61 = blob one + - found items[0] +- looking up items[1]#ad4eb7b = blob two and five are the same + - not items[4] + - found items[1] +- looking up items[2]#6b8eae61 = third blob + - found items[2] +- looking up items[3]#24a546dc = fourth blob + - found items[3] +- looking up items[4]#ad4eb7b = blob two and five are the same + - found items[4] + - not items[1] diff --git a/tests/testsuite.at b/tests/testsuite.at index e721b93..3433fb0 100644 --- a/tests/testsuite.at +++ b/tests/testsuite.at @@ -547,3 +547,9 @@ cat $abs_srcdir/rlp/rlp_test.ok > expout AT_CHECK([$abs_top_builddir/tests/rlp/rlp_test], [0], [expout], [ignore]) AT_CLEANUP + +AT_SETUP([jhash]) +AT_KEYWORDS([jhash]) +cat $abs_srcdir/jhash/jhash_test.ok > expout +AT_CHECK([$abs_top_builddir/tests/jhash/jhash_test], [0], [expout], [ignore]) +AT_CLEANUP -- To view, visit https://gerrit.osmocom.org/c/libosmocore/+/36913?usp=email To unsubscribe, or for help writing mail filters, visit https://gerrit.osmocom.org/settings Gerrit-Project: libosmocore Gerrit-Branch: master Gerrit-Change-Id: I0c9652bbc9e2a18b1200e7d63bb6f64ded7d75fa Gerrit-Change-Number: 36913 Gerrit-PatchSet: 1 Gerrit-Owner: neels <nhofm...@sysmocom.de> Gerrit-MessageType: newchange