diff options
author | Neels Hofmeyr <nhofmeyr@sysmocom.de> | 2024-05-23 02:59:53 +0200 |
---|---|---|
committer | Neels Hofmeyr <nhofmeyr@sysmocom.de> | 2024-05-27 16:35:19 +0200 |
commit | 64b91d29eb9947e8cda45928f8481a8dafeb0def (patch) | |
tree | 9032dd7e13d8eda4110c6c4904046c8ee6b11fe1 | |
parent | c380bd9fa67f4b65c30244de9304e43bf7580eef (diff) |
add jhash.h, copied from linux/jhash.hneels/jhash
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
-rw-r--r-- | include/osmocom/core/Makefile.am | 1 | ||||
-rw-r--r-- | include/osmocom/core/jhash.h | 171 | ||||
-rw-r--r-- | tests/Makefile.am | 8 | ||||
-rw-r--r-- | tests/jhash/jhash_test.c | 56 | ||||
-rw-r--r-- | tests/jhash/jhash_test.ok | 25 | ||||
-rw-r--r-- | tests/testsuite.at | 6 |
6 files changed, 265 insertions, 2 deletions
diff --git a/include/osmocom/core/Makefile.am b/include/osmocom/core/Makefile.am index 7c29ca10..980f8134 100644 --- a/include/osmocom/core/Makefile.am +++ b/include/osmocom/core/Makefile.am @@ -27,6 +27,7 @@ osmocore_HEADERS = \ 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 00000000..763fcd7d --- /dev/null +++ b/include/osmocom/core/jhash.h @@ -0,0 +1,171 @@ +#pragma once +#include <osmocom/core/bit32gen.h> + +/* Below is a partial copy of + * https://raw.githubusercontent.com/torvalds/linux/3eb3c33c1d87029a3832e205eebd59cfb56ba3a4/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 partial copy of + * https://raw.githubusercontent.com/torvalds/linux/22c033989c3eb9731ad0c497dfab4231b8e367d6/include/linux/unaligned/packed_struct.h + * with an osmo_ prefix applied to avoid any collisions. + */ +struct osmo_unaligned_cpu32 { + uint32_t x; +} __attribute__((__packed__)); + +static inline uint32_t osmo_get_unaligned_cpu32(const void *p) +{ + const struct osmo_unaligned_cpu32 *ptr = (const struct osmo_unaligned_cpu32 *)p; + return ptr->x; +} + +/* Below is a partial copy of + * https://raw.githubusercontent.com/torvalds/linux/79e3ea5aab48c83de9410e43b52895406847eca7/tools/include/linux/jhash.h + * with an osmo_ prefix applied to avoid any collisions. + */ +/* jhash.h: Jenkins hash support. + * + * Copyright (C) 2006. Bob Jenkins (bob_jenkins@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 (kadlec@blackhole.kfki.hu) + * + * I've modified Bob's hash to be useful in the Linux kernel, and + * any bugs present are my fault. + * Jozsef + */ + +/* 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_get_unaligned_cpu32(k); + b += osmo_get_unaligned_cpu32(k + 4); + c += osmo_get_unaligned_cpu32(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; +} diff --git a/tests/Makefile.am b/tests/Makefile.am index 58900d3e..1e8997c1 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -59,6 +59,7 @@ check_PROGRAMS = timer/timer_test sms/sms_test ussd/ussd_test \ osmo_io/osmo_io_test \ soft_uart/soft_uart_test \ rlp/rlp_test \ + jhash/jhash_test \ $(NULL) if ENABLE_MSGFILE @@ -391,6 +392,7 @@ soft_uart_soft_uart_test_SOURCES = soft_uart/soft_uart_test.c 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 @@ EXTRA_DIST = testsuite.at $(srcdir)/package.m4 $(TESTSUITE) \ 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 @@ endif 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 00000000..e2c8c71e --- /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 00000000..e28ccc46 --- /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 e721b937..3433fb01 100644 --- a/tests/testsuite.at +++ b/tests/testsuite.at @@ -547,3 +547,9 @@ AT_KEYWORDS([rlp]) 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 |