krb5 commit: Add a hash table implementation to libkrb5support

Greg Hudson ghudson at mit.edu
Wed Aug 22 13:49:25 EDT 2018


https://github.com/krb5/krb5/commit/09e814fe47f5ceeb35bee15ced6e346db8a5e81d
commit 09e814fe47f5ceeb35bee15ced6e346db8a5e81d
Author: Greg Hudson <ghudson at mit.edu>
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;
+}


More information about the cvs-krb5 mailing list