krb5 commit: Add a hash table implementation to libkrb5support
Greg Hudson <[email protected]>
| Newsgroups | gmane.comp.encryption.kerberos.cvs |
|---|---|
| Message-ID | <[email protected]> |
https://github.com/krb5/krb5/commit/09e814fe47f5ceeb35bee15ced6e346db8a5e81d commit 09e814fe47f5ceeb35bee15ced6e346db8a5e81d Author: Greg Hudson <[email protected]> Date: Sat Aug 4 20:11:09 2018 -0400 Add a hash table implementation to libkrb5support .gitignore | 1 + src/include/k5-hashtab.h | 79 ++++++++ src/util/support/Makefile.in | 16 ++- src/util/support/deps | 11 + src/util/support/hashtab.c | 243 +++++++++++++++++++++++++ src/util/support/libkrb5support-fixed.exports | 5 + src/util/support/t_hashtab.c | 176 ++++++++++++++++++ 7 files changed, 527 insertions(+), 4 deletions(-) diff --git a/.gitignore b/.gitignore index cb926f3..5f0fa91 100644 --- a/.gitignore +++ b/.gitignore @@ -559,6 +559,7 @@ local.properties /src/util/support/libkrb5support.exports /src/util/support/t_base64 +/src/util/support/t_hashtab /src/util/support/t_hex /src/util/support/t_json /src/util/support/t_k5buf diff --git a/src/include/k5-hashtab.h b/src/include/k5-hashtab.h new file mode 100644 index 0000000..dc0ef36 --- /dev/null +++ b/src/include/k5-hashtab.h @@ -0,0 +1,79 @@ +/* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */ +/* include/k5-hash.h - hash table interface definitions */ +/* + * Copyright (C) 2018 by the Massachusetts Institute of Technology. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED + * OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * This file contains declarations for a simple hash table using siphash. Some + * limitations which might need to be addressed in the future: + * + * - The table does not manage caller memory. This limitation could be + * addressed by adding an optional free callback to k5_hashtab_create(), to + * be called by k5_hashtab_free() and k5_hashtab_remove(). + * + * - There is no way to iterate over a hash table. + * + * - k5_hashtab_add() does not check for duplicate entries. + */ + +#ifndef K5_HASH_H +#define K5_HASH_H + +#define K5_HASH_SEED_LEN 16 + +struct k5_hashtab; + +/* + * Create a new hash table in *ht_out. seed must point to random bytes if keys + * might be under the control of an attacker; otherwise it may be NULL. + * initial_buckets controls the initial allocation of hash buckets; pass zero + * to use a default value. The number of hash buckets will be doubled as the + * number of entries increases. Return 0 on success, ENOMEM on failure. + */ +int k5_hashtab_create(const uint8_t seed[K5_HASH_SEED_LEN], + size_t initial_buckets, struct k5_hashtab **ht_out); + +/* Release the memory used by a hash table. Keys and values are the caller's + * responsibility. */ +void k5_hashtab_free(struct k5_hashtab *ht); + +/* Add an entry to a hash table. key and val must remain valid until the entry + * is removed or the hash table is freed. The caller must avoid duplicates. */ +int k5_hashtab_add(struct k5_hashtab *ht, const void *key, size_t klen, + void *val); + +/* Remove an entry from a hash table by key. Does not free key or the + * associated value. Return 1 if the key was found and removed, 0 if not. */ +int k5_hashtab_remove(struct k5_hashtab *ht, const void *key, size_t klen); + +/* Retrieve a value from a hash table by key. */ +void *k5_hashtab_get(struct k5_hashtab *ht, const void *key, size_t klen); + +#endif /* K5_HASH_H */ diff --git a/src/util/support/Makefile.in b/src/util/support/Makefile.in index 890218b..b1842da 100644 --- a/src/util/support/Makefile.in +++ b/src/util/support/Makefile.in @@ -82,6 +82,7 @@ STLIBOBJS= \ base64.o \ json.o \ hex.o \ + hashtab.o \ bcmp.o \ strerror_r.o \ dir_filenames.o \ @@ -109,6 +110,7 @@ LIBOBJS= \ $(OUTPRE)base64.$(OBJEXT) \ $(OUTPRE)json.$(OBJEXT) \ $(OUTPRE)hex.$(OBJEXT) \ + $(OUTPRE)hashtab.$(OBJEXT) \ $(OUTPRE)bcmp.$(OBJEXT) \ $(OUTPRE)strerror_r.$(OBJEXT) \ $(OUTPRE)dir_filenames.$(OBJEXT) \ @@ -141,11 +143,13 @@ SRCS=\ $(srcdir)/t_path.c \ $(srcdir)/t_json.c \ $(srcdir)/t_hex.c \ + $(srcdir)/t_hashtab.c \ $(srcdir)/zap.c \ $(srcdir)/path.c \ $(srcdir)/base64.c \ $(srcdir)/json.c \ $(srcdir)/hex.c \ + $(srcdir)/hashtab.c \ $(srcdir)/bcmp.c \ $(srcdir)/strerror_r.c \ $(srcdir)/dir_filenames.c \ @@ -227,6 +231,9 @@ t_json: $(T_JSON_OBJS) t_hex: t_hex.o hex.o $(CC_LINK) -o $@ t_hex.o hex.o +t_hashtab: t_hashtab.o + $(CC_LINK) -o $@ t_hashtab.o + t_unal: t_unal.o $(CC_LINK) -o t_unal t_unal.o @@ -238,8 +245,8 @@ T_UTF16_OBJS= t_utf16.o utf8_conv.o utf8.o k5buf.o $(PRINTF_ST_OBJ) t_utf16: $(T_UTF16_OBJS) $(CC_LINK) -o $@ $(T_UTF16_OBJS) -TEST_PROGS= t_k5buf t_path t_path_win t_base64 t_json t_hex t_unal t_utf8 \ - t_utf16 +TEST_PROGS= t_k5buf t_path t_path_win t_base64 t_json t_hex t_hashtab t_unal \ + t_utf8 t_utf16 check-unix: $(TEST_PROGS) ./t_k5buf @@ -248,6 +255,7 @@ check-unix: $(TEST_PROGS) ./t_base64 ./t_json ./t_hex + ./t_hashtab ./t_unal ./t_utf8 ./t_utf16 @@ -255,8 +263,8 @@ check-unix: $(TEST_PROGS) clean: $(RM) t_k5buf.o t_k5buf t_unal.o t_unal path_win.o path_win $(RM) t_path_win.o t_path_win t_path.o t_path t_base64.o t_base64 - $(RM) t_json.o t_json t_hex.o t_hex libkrb5support.exports - $(RM) t_utf8.o t_utf8 t_utf16.o t_utf16 + $(RM) t_json.o t_json t_hex.o t_hex t_hashtab.o t_hashtab + $(RM) t_utf8.o t_utf8 t_utf16.o t_utf16 libkrb5support.exports @lib_frag@ @libobj_frag@ diff --git a/src/util/support/deps b/src/util/support/deps index 80e9a1c..1fc042b 100644 --- a/src/util/support/deps +++ b/src/util/support/deps @@ -66,6 +66,10 @@ t_json.so t_json.po $(OUTPRE)t_json.$(OBJEXT): $(top_srcdir)/include/k5-json.h \ t_hex.so t_hex.po $(OUTPRE)t_hex.$(OBJEXT): $(BUILDTOP)/include/autoconf.h \ $(top_srcdir)/include/k5-hex.h $(top_srcdir)/include/k5-platform.h \ $(top_srcdir)/include/k5-thread.h t_hex.c +t_hashtab.so t_hashtab.po $(OUTPRE)t_hashtab.$(OBJEXT): \ + $(BUILDTOP)/include/autoconf.h $(top_srcdir)/include/k5-hashtab.h \ + $(top_srcdir)/include/k5-platform.h $(top_srcdir)/include/k5-queue.h \ + $(top_srcdir)/include/k5-thread.h hashtab.c t_hashtab.c zap.so zap.po $(OUTPRE)zap.$(OBJEXT): $(BUILDTOP)/include/autoconf.h \ $(top_srcdir)/include/k5-platform.h $(top_srcdir)/include/k5-thread.h \ zap.c @@ -82,12 +86,19 @@ json.so json.po $(OUTPRE)json.$(OBJEXT): $(BUILDTOP)/include/autoconf.h \ hex.so hex.po $(OUTPRE)hex.$(OBJEXT): $(BUILDTOP)/include/autoconf.h \ $(top_srcdir)/include/k5-hex.h $(top_srcdir)/include/k5-platform.h \ $(top_srcdir)/include/k5-thread.h hex.c +hashtab.so hashtab.po $(OUTPRE)hashtab.$(OBJEXT): $(BUILDTOP)/include/autoconf.h \ + $(top_srcdir)/include/k5-hashtab.h $(top_srcdir)/include/k5-platform.h \ + $(top_srcdir)/include/k5-queue.h $(top_srcdir)/include/k5-thread.h \ + hashtab.c bcmp.so bcmp.po $(OUTPRE)bcmp.$(OBJEXT): $(BUILDTOP)/include/autoconf.h \ $(top_srcdir)/include/k5-platform.h $(top_srcdir)/include/k5-thread.h \ bcmp.c strerror_r.so strerror_r.po $(OUTPRE)strerror_r.$(OBJEXT): \ $(BUILDTOP)/include/autoconf.h $(top_srcdir)/include/k5-platform.h \ $(top_srcdir)/include/k5-thread.h strerror_r.c +dir_filenames.so dir_filenames.po $(OUTPRE)dir_filenames.$(OBJEXT): \ + $(BUILDTOP)/include/autoconf.h $(top_srcdir)/include/k5-platform.h \ + $(top_srcdir)/include/k5-thread.h dir_filenames.c t_utf8.so t_utf8.po $(OUTPRE)t_utf8.$(OBJEXT): $(BUILDTOP)/include/autoconf.h \ $(top_srcdir)/include/k5-platform.h $(top_srcdir)/include/k5-thread.h \ $(top_srcdir)/include/k5-utf8.h t_utf8.c diff --git a/src/util/support/hashtab.c b/src/util/support/hashtab.c new file mode 100644 index 0000000..e04e491 --- /dev/null +++ b/src/util/support/hashtab.c @@ -0,0 +1,243 @@ +/* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */ +/* util/support/hash.c - hash table implementation */ +/* + * Copyright (C) 2018 by the Massachusetts Institute of Technology. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED + * OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "k5-platform.h" +#include "k5-hashtab.h" +#include "k5-queue.h" + +struct entry { + const void *key; + size_t klen; + void *val; + K5_SLIST_ENTRY(entry) next; +}; + +struct k5_hashtab { + uint64_t k0; + uint64_t k1; + size_t nbuckets; + size_t nentries; + K5_SLIST_HEAD(bucket_list, entry) *buckets; +}; + +/* Return x rotated to the left by r bits. */ +static inline uint64_t +rotl64(uint64_t x, int r) +{ + return (x << r) | (x >> (64 - r)); +} + +static inline void +sipround(uint64_t *v0, uint64_t *v1, uint64_t *v2, uint64_t *v3) +{ + *v0 += *v1; + *v2 += *v3; + *v1 = rotl64(*v1, 13) ^ *v0; + *v3 = rotl64(*v3, 16) ^ *v2; + *v0 = rotl64(*v0, 32); + *v2 += *v1; + *v0 += *v3; + *v1 = rotl64(*v1, 17) ^ *v2; + *v3 = rotl64(*v3, 21) ^ *v0; + *v2 = rotl64(*v2, 32); +} + +/* SipHash-2-4 from https://131002.net/siphash/siphash.pdf (Jean-Philippe + * Aumasson and Daniel J. Bernstein) */ +static uint64_t +siphash24(const uint8_t *data, size_t len, uint64_t k0, uint64_t k1) +{ + uint64_t v0 = k0 ^ 0x736F6D6570736575; + uint64_t v1 = k1 ^ 0x646F72616E646F6D; + uint64_t v2 = k0 ^ 0x6C7967656E657261; + uint64_t v3 = k1 ^ 0x7465646279746573; + uint64_t mi; + const uint8_t *p, *end = data + (len - len % 8); + uint8_t last[8] = { 0 }; + + /* Process each full 8-byte chunk of data. */ + for (p = data; p < end; p += 8) { + mi = load_64_le(p); + v3 ^= mi; + sipround(&v0, &v1, &v2, &v3); + sipround(&v0, &v1, &v2, &v3); + v0 ^= mi; + } + + /* Process the last 0-7 bytes followed by the length mod 256. */ + memcpy(last, end, len % 8); + last[7] = len & 0xFF; + mi = load_64_le(last); + v3 ^= mi; + sipround(&v0, &v1, &v2, &v3); + sipround(&v0, &v1, &v2, &v3); + v0 ^= mi; + + /* Finalize. */ + v2 ^= 0xFF; + sipround(&v0, &v1, &v2, &v3); + sipround(&v0, &v1, &v2, &v3); + sipround(&v0, &v1, &v2, &v3); + sipround(&v0, &v1, &v2, &v3); + return v0 ^ v1 ^ v2 ^ v3; +} + +int +k5_hashtab_create(const uint8_t seed[K5_HASH_SEED_LEN], size_t initial_buckets, + struct k5_hashtab **ht_out) +{ + struct k5_hashtab *ht; + + *ht_out = NULL; + + ht = malloc(sizeof(*ht)); + if (ht == NULL) + return ENOMEM; + + if (seed != NULL) { + ht->k0 = load_64_le(seed); + ht->k1 = load_64_le(seed + 8); + } else { + ht->k0 = ht->k1 = 0; + } + ht->nbuckets = (initial_buckets > 0) ? initial_buckets : 64; + ht->nentries = 0; + ht->buckets = calloc(ht->nbuckets, sizeof(*ht->buckets)); + if (ht->buckets == NULL) { + free(ht); + return ENOMEM; + } + + *ht_out = ht; + return 0; +} + +void +k5_hashtab_free(struct k5_hashtab *ht) +{ + size_t i; + struct entry *ent; + + for (i = 0; i < ht->nbuckets; i++) { + while (!K5_SLIST_EMPTY(&ht->buckets[i])) { + ent = K5_SLIST_FIRST(&ht->buckets[i]); + K5_SLIST_REMOVE_HEAD(&ht->buckets[i], next); + free(ent); + } + } + free(ht->buckets); + free(ht); +} + +static int +resize_table(struct k5_hashtab *ht) +{ + size_t i, j, newsize = ht->nbuckets * 2; + struct bucket_list *newbuckets; + struct entry *ent; + + newbuckets = calloc(newsize, sizeof(*newbuckets)); + if (newbuckets == NULL) + return ENOMEM; + + /* Rehash all the entries into the new buckets. */ + for (i = 0; i < ht->nbuckets; i++) { + while (!K5_SLIST_EMPTY(&ht->buckets[i])) { + ent = K5_SLIST_FIRST(&ht->buckets[i]); + j = siphash24(ent->key, ent->klen, ht->k0, ht->k1) % newsize; + K5_SLIST_REMOVE_HEAD(&ht->buckets[i], next); + K5_SLIST_INSERT_HEAD(&newbuckets[j], ent, next); + } + } + + free(ht->buckets); + ht->buckets = newbuckets; + ht->nbuckets = newsize; + return 0; +} + +int +k5_hashtab_add(struct k5_hashtab *ht, const void *key, size_t klen, void *val) +{ + size_t i; + struct entry *ent; + + if (ht->nentries == ht->nbuckets) { + if (resize_table(ht) != 0) + return ENOMEM; + } + + ent = malloc(sizeof(*ent)); + if (ent == NULL) + return ENOMEM; + ent->key = key; + ent->klen = klen; + ent->val = val; + + i = siphash24(key, klen, ht->k0, ht->k1) % ht->nbuckets; + K5_SLIST_INSERT_HEAD(&ht->buckets[i], ent, next); + + ht->nentries++; + return 0; +} + +int +k5_hashtab_remove(struct k5_hashtab *ht, const void *key, size_t klen) +{ + size_t i; + struct entry *ent; + + i = siphash24(key, klen, ht->k0, ht->k1) % ht->nbuckets; + K5_SLIST_FOREACH(ent, &ht->buckets[i], next) { + if (ent->klen == klen && memcmp(ent->key, key, klen) == 0) { + K5_SLIST_REMOVE(&ht->buckets[i], ent, entry, next); + free(ent); + ht->nentries--; + return 1; + } + } + return 0; +} + +void * +k5_hashtab_get(struct k5_hashtab *ht, const void *key, size_t klen) +{ + size_t i; + struct entry *ent; + + i = siphash24(key, klen, ht->k0, ht->k1) % ht->nbuckets; + K5_SLIST_FOREACH(ent, &ht->buckets[i], next) { + if (ent->klen == klen && memcmp(ent->key, key, klen) == 0) + return ent->val; + } + return NULL; +} diff --git a/src/util/support/libkrb5support-fixed.exports b/src/util/support/libkrb5support-fixed.exports index 16ed5a6..ff46656 100644 --- a/src/util/support/libkrb5support-fixed.exports +++ b/src/util/support/libkrb5support-fixed.exports @@ -18,6 +18,11 @@ k5_get_error k5_free_error k5_clear_error k5_set_error_info_callout_fn +k5_hashtab_add +k5_hashtab_create +k5_hashtab_free +k5_hashtab_get +k5_hashtab_remove k5_hex_decode k5_hex_encode k5_json_array_add diff --git a/src/util/support/t_hashtab.c b/src/util/support/t_hashtab.c new file mode 100644 index 0000000..f51abc4 --- /dev/null +++ b/src/util/support/t_hashtab.c @@ -0,0 +1,176 @@ +/* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */ +/* util/support/t_hash.c - tests for hash table code */ +/* + * Copyright (C) 2018 by the Massachusetts Institute of Technology. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED + * OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/* hash.c has no linker dependencies, so we can simply include its source code + * to test its static functions and look inside its structures. */ +#include "hashtab.c" + +/* These match the sip64 test vectors in the reference C implementation of + * siphash at https://github.com/veorq/SipHash */ +const uint64_t vectors[64] = { + 0x726FDB47DD0E0E31, + 0x74F839C593DC67FD, + 0x0D6C8009D9A94F5A, + 0x85676696D7FB7E2D, + 0xCF2794E0277187B7, + 0x18765564CD99A68D, + 0xCBC9466E58FEE3CE, + 0xAB0200F58B01D137, + 0x93F5F5799A932462, + 0x9E0082DF0BA9E4B0, + 0x7A5DBBC594DDB9F3, + 0xF4B32F46226BADA7, + 0x751E8FBC860EE5FB, + 0x14EA5627C0843D90, + 0xF723CA908E7AF2EE, + 0xA129CA6149BE45E5, + 0x3F2ACC7F57C29BDB, + 0x699AE9F52CBE4794, + 0x4BC1B3F0968DD39C, + 0xBB6DC91DA77961BD, + 0xBED65CF21AA2EE98, + 0xD0F2CBB02E3B67C7, + 0x93536795E3A33E88, + 0xA80C038CCD5CCEC8, + 0xB8AD50C6F649AF94, + 0xBCE192DE8A85B8EA, + 0x17D835B85BBB15F3, + 0x2F2E6163076BCFAD, + 0xDE4DAAACA71DC9A5, + 0xA6A2506687956571, + 0xAD87A3535C49EF28, + 0x32D892FAD841C342, + 0x7127512F72F27CCE, + 0xA7F32346F95978E3, + 0x12E0B01ABB051238, + 0x15E034D40FA197AE, + 0x314DFFBE0815A3B4, + 0x027990F029623981, + 0xCADCD4E59EF40C4D, + 0x9ABFD8766A33735C, + 0x0E3EA96B5304A7D0, + 0xAD0C42D6FC585992, + 0x187306C89BC215A9, + 0xD4A60ABCF3792B95, + 0xF935451DE4F21DF2, + 0xA9538F0419755787, + 0xDB9ACDDFF56CA510, + 0xD06C98CD5C0975EB, + 0xE612A3CB9ECBA951, + 0xC766E62CFCADAF96, + 0xEE64435A9752FE72, + 0xA192D576B245165A, + 0x0A8787BF8ECB74B2, + 0x81B3E73D20B49B6F, + 0x7FA8220BA3B2ECEA, + 0x245731C13CA42499, + 0xB78DBFAF3A8D83BD, + 0xEA1AD565322A1A0B, + 0x60E61C23A3795013, + 0x6606D7E446282B93, + 0x6CA4ECB15C5F91E1, + 0x9F626DA15C9625F3, + 0xE51B38608EF25F57, + 0x958A324CEB064572 +}; + +static void +test_siphash() +{ + uint8_t seq[64]; + uint64_t k0, k1, hval; + size_t i; + + for (i = 0; i < sizeof(seq); i++) + seq[i] = i; + k0 = load_64_le(seq); + k1 = load_64_le(seq + 8); + + for (i = 0; i < sizeof(seq); i++) { + hval = siphash24(seq, i, k0, k1); + assert(hval == vectors[i]); + } +} + +static void +test_hashtab() +{ + int st; + struct k5_hashtab *ht; + size_t i; + char zeros[100] = { 0 }; + + st = k5_hashtab_create(NULL, 4, &ht); + assert(st == 0 && ht != NULL && ht->nentries == 0); + + st = k5_hashtab_add(ht, "abc", 3, &st); + assert(st == 0 && ht->nentries == 1); + assert(k5_hashtab_get(ht, "abc", 3) == &st); + assert(k5_hashtab_get(ht, "bcde", 4) == NULL); + + st = k5_hashtab_add(ht, "bcde", 4, &ht); + assert(st == 0 && ht->nentries == 2); + assert(k5_hashtab_get(ht, "abc", 3) == &st); + assert(k5_hashtab_get(ht, "bcde", 4) == &ht); + + k5_hashtab_remove(ht, "abc", 3); + assert(ht->nentries == 1); + assert(k5_hashtab_get(ht, "abc", 3) == NULL); + assert(k5_hashtab_get(ht, "bcde", 4) == &ht); + + k5_hashtab_remove(ht, "bcde", 4); + assert(ht->nentries == 0); + assert(k5_hashtab_get(ht, "abc", 3) == NULL); + assert(k5_hashtab_get(ht, "bcde", 4) == NULL); + + for (i = 0; i < sizeof(zeros); i++) { + st = k5_hashtab_add(ht, zeros, i, zeros + i); + assert(st == 0 && ht->nentries == i + 1 && ht->nbuckets >= i + 1); + } + for (i = 0; i < sizeof(zeros); i++) { + assert(k5_hashtab_get(ht, zeros, i) == zeros + i); + k5_hashtab_remove(ht, zeros, i); + assert(ht->nentries == sizeof(zeros) - i - 1); + if (i > 0) + assert(k5_hashtab_get(ht, zeros, i - 1) == NULL); + } + + k5_hashtab_free(ht); +} + +int +main() +{ + test_siphash(); + test_hashtab(); + return 0; +}