summaryrefslogtreecommitdiff
path: root/src/openvpn/list.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/openvpn/list.c')
-rw-r--r--src/openvpn/list.c924
1 files changed, 475 insertions, 449 deletions
diff --git a/src/openvpn/list.c b/src/openvpn/list.c
index ea6bd74..fb9f664 100644
--- a/src/openvpn/list.c
+++ b/src/openvpn/list.c
@@ -5,7 +5,7 @@
* packet encryption, packet authentication, and
* packet compression.
*
- * Copyright (C) 2002-2010 OpenVPN Technologies, Inc. <sales@openvpn.net>
+ * Copyright (C) 2002-2017 OpenVPN Technologies, Inc. <sales@openvpn.net>
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License version 2
@@ -38,294 +38,306 @@
#include "memdbg.h"
struct hash *
-hash_init (const int n_buckets,
- const uint32_t iv,
- uint32_t (*hash_function)(const void *key, uint32_t iv),
- bool (*compare_function)(const void *key1, const void *key2))
+hash_init(const int n_buckets,
+ const uint32_t iv,
+ uint32_t (*hash_function)(const void *key, uint32_t iv),
+ bool (*compare_function)(const void *key1, const void *key2))
{
- struct hash *h;
- int i;
-
- ASSERT (n_buckets > 0);
- ALLOC_OBJ_CLEAR (h, struct hash);
- h->n_buckets = (int) adjust_power_of_2 (n_buckets);
- h->mask = h->n_buckets - 1;
- h->hash_function = hash_function;
- h->compare_function = compare_function;
- h->iv = iv;
- ALLOC_ARRAY (h->buckets, struct hash_bucket, h->n_buckets);
- for (i = 0; i < h->n_buckets; ++i)
+ struct hash *h;
+ int i;
+
+ ASSERT(n_buckets > 0);
+ ALLOC_OBJ_CLEAR(h, struct hash);
+ h->n_buckets = (int) adjust_power_of_2(n_buckets);
+ h->mask = h->n_buckets - 1;
+ h->hash_function = hash_function;
+ h->compare_function = compare_function;
+ h->iv = iv;
+ ALLOC_ARRAY(h->buckets, struct hash_bucket, h->n_buckets);
+ for (i = 0; i < h->n_buckets; ++i)
{
- struct hash_bucket *b = &h->buckets[i];
- b->list = NULL;
+ struct hash_bucket *b = &h->buckets[i];
+ b->list = NULL;
}
- return h;
+ return h;
}
void
-hash_free (struct hash *hash)
+hash_free(struct hash *hash)
{
- int i;
- for (i = 0; i < hash->n_buckets; ++i)
+ int i;
+ for (i = 0; i < hash->n_buckets; ++i)
{
- struct hash_bucket *b = &hash->buckets[i];
- struct hash_element *he = b->list;
-
- while (he)
- {
- struct hash_element *next = he->next;
- free (he);
- he = next;
- }
+ struct hash_bucket *b = &hash->buckets[i];
+ struct hash_element *he = b->list;
+
+ while (he)
+ {
+ struct hash_element *next = he->next;
+ free(he);
+ he = next;
+ }
}
- free (hash->buckets);
- free (hash);
+ free(hash->buckets);
+ free(hash);
}
struct hash_element *
-hash_lookup_fast (struct hash *hash,
- struct hash_bucket *bucket,
- const void *key,
- uint32_t hv)
+hash_lookup_fast(struct hash *hash,
+ struct hash_bucket *bucket,
+ const void *key,
+ uint32_t hv)
{
- struct hash_element *he;
- struct hash_element *prev = NULL;
+ struct hash_element *he;
+ struct hash_element *prev = NULL;
- he = bucket->list;
+ he = bucket->list;
- while (he)
+ while (he)
{
- if (hv == he->hash_value && (*hash->compare_function)(key, he->key))
- {
- /* move to head of list */
- if (prev)
- {
- prev->next = he->next;
- he->next = bucket->list;
- bucket->list = he;
- }
- return he;
- }
- prev = he;
- he = he->next;
+ if (hv == he->hash_value && (*hash->compare_function)(key, he->key))
+ {
+ /* move to head of list */
+ if (prev)
+ {
+ prev->next = he->next;
+ he->next = bucket->list;
+ bucket->list = he;
+ }
+ return he;
+ }
+ prev = he;
+ he = he->next;
}
- return NULL;
+ return NULL;
}
bool
-hash_remove_fast (struct hash *hash,
- struct hash_bucket *bucket,
- const void *key,
- uint32_t hv)
+hash_remove_fast(struct hash *hash,
+ struct hash_bucket *bucket,
+ const void *key,
+ uint32_t hv)
{
- struct hash_element *he;
- struct hash_element *prev = NULL;
+ struct hash_element *he;
+ struct hash_element *prev = NULL;
- he = bucket->list;
+ he = bucket->list;
- while (he)
+ while (he)
{
- if (hv == he->hash_value && (*hash->compare_function)(key, he->key))
- {
- if (prev)
- prev->next = he->next;
- else
- bucket->list = he->next;
- free (he);
- --hash->n_elements;
- return true;
- }
- prev = he;
- he = he->next;
+ if (hv == he->hash_value && (*hash->compare_function)(key, he->key))
+ {
+ if (prev)
+ {
+ prev->next = he->next;
+ }
+ else
+ {
+ bucket->list = he->next;
+ }
+ free(he);
+ --hash->n_elements;
+ return true;
+ }
+ prev = he;
+ he = he->next;
}
- return false;
+ return false;
}
bool
-hash_add (struct hash *hash, const void *key, void *value, bool replace)
+hash_add(struct hash *hash, const void *key, void *value, bool replace)
{
- uint32_t hv;
- struct hash_bucket *bucket;
- struct hash_element *he;
- bool ret = false;
+ uint32_t hv;
+ struct hash_bucket *bucket;
+ struct hash_element *he;
+ bool ret = false;
- hv = hash_value (hash, key);
- bucket = &hash->buckets[hv & hash->mask];
+ hv = hash_value(hash, key);
+ bucket = &hash->buckets[hv & hash->mask];
- if ((he = hash_lookup_fast (hash, bucket, key, hv))) /* already exists? */
+ if ((he = hash_lookup_fast(hash, bucket, key, hv))) /* already exists? */
{
- if (replace)
- {
- he->value = value;
- ret = true;
- }
+ if (replace)
+ {
+ he->value = value;
+ ret = true;
+ }
}
- else
+ else
{
- hash_add_fast (hash, bucket, key, hv, value);
- ret = true;
+ hash_add_fast(hash, bucket, key, hv, value);
+ ret = true;
}
- return ret;
+ return ret;
}
void
-hash_remove_by_value (struct hash *hash, void *value)
+hash_remove_by_value(struct hash *hash, void *value)
{
- struct hash_iterator hi;
- struct hash_element *he;
+ struct hash_iterator hi;
+ struct hash_element *he;
- hash_iterator_init (hash, &hi);
- while ((he = hash_iterator_next (&hi)))
+ hash_iterator_init(hash, &hi);
+ while ((he = hash_iterator_next(&hi)))
{
- if (he->value == value)
- hash_iterator_delete_element (&hi);
+ if (he->value == value)
+ {
+ hash_iterator_delete_element(&hi);
+ }
}
- hash_iterator_free (&hi);
+ hash_iterator_free(&hi);
}
static void
-hash_remove_marked (struct hash *hash, struct hash_bucket *bucket)
+hash_remove_marked(struct hash *hash, struct hash_bucket *bucket)
{
- struct hash_element *prev = NULL;
- struct hash_element *he = bucket->list;
+ struct hash_element *prev = NULL;
+ struct hash_element *he = bucket->list;
- while (he)
+ while (he)
{
- if (!he->key) /* marked? */
- {
- struct hash_element *newhe;
- if (prev)
- newhe = prev->next = he->next;
- else
- newhe = bucket->list = he->next;
- free (he);
- --hash->n_elements;
- he = newhe;
- }
- else
- {
- prev = he;
- he = he->next;
- }
+ if (!he->key) /* marked? */
+ {
+ struct hash_element *newhe;
+ if (prev)
+ {
+ newhe = prev->next = he->next;
+ }
+ else
+ {
+ newhe = bucket->list = he->next;
+ }
+ free(he);
+ --hash->n_elements;
+ he = newhe;
+ }
+ else
+ {
+ prev = he;
+ he = he->next;
+ }
}
}
uint32_t
-void_ptr_hash_function (const void *key, uint32_t iv)
+void_ptr_hash_function(const void *key, uint32_t iv)
{
- return hash_func ((const void *)&key, sizeof (key), iv);
+ return hash_func((const void *)&key, sizeof(key), iv);
}
bool
-void_ptr_compare_function (const void *key1, const void *key2)
+void_ptr_compare_function(const void *key1, const void *key2)
{
- return key1 == key2;
+ return key1 == key2;
}
void
-hash_iterator_init_range (struct hash *hash,
- struct hash_iterator *hi,
- int start_bucket,
- int end_bucket)
+hash_iterator_init_range(struct hash *hash,
+ struct hash_iterator *hi,
+ int start_bucket,
+ int end_bucket)
{
- if (end_bucket > hash->n_buckets)
- end_bucket = hash->n_buckets;
-
- ASSERT (start_bucket >= 0 && start_bucket <= end_bucket);
-
- hi->hash = hash;
- hi->elem = NULL;
- hi->bucket = NULL;
- hi->last = NULL;
- hi->bucket_marked = false;
- hi->bucket_index_start = start_bucket;
- hi->bucket_index_end = end_bucket;
- hi->bucket_index = hi->bucket_index_start - 1;
+ if (end_bucket > hash->n_buckets)
+ {
+ end_bucket = hash->n_buckets;
+ }
+
+ ASSERT(start_bucket >= 0 && start_bucket <= end_bucket);
+
+ hi->hash = hash;
+ hi->elem = NULL;
+ hi->bucket = NULL;
+ hi->last = NULL;
+ hi->bucket_marked = false;
+ hi->bucket_index_start = start_bucket;
+ hi->bucket_index_end = end_bucket;
+ hi->bucket_index = hi->bucket_index_start - 1;
}
void
-hash_iterator_init (struct hash *hash,
- struct hash_iterator *hi)
+hash_iterator_init(struct hash *hash,
+ struct hash_iterator *hi)
{
- hash_iterator_init_range (hash, hi, 0, hash->n_buckets);
+ hash_iterator_init_range(hash, hi, 0, hash->n_buckets);
}
static inline void
-hash_iterator_lock (struct hash_iterator *hi, struct hash_bucket *b)
+hash_iterator_lock(struct hash_iterator *hi, struct hash_bucket *b)
{
- hi->bucket = b;
- hi->last = NULL;
- hi->bucket_marked = false;
+ hi->bucket = b;
+ hi->last = NULL;
+ hi->bucket_marked = false;
}
static inline void
-hash_iterator_unlock (struct hash_iterator *hi)
+hash_iterator_unlock(struct hash_iterator *hi)
{
- if (hi->bucket)
+ if (hi->bucket)
{
- if (hi->bucket_marked)
- {
- hash_remove_marked (hi->hash, hi->bucket);
- hi->bucket_marked = false;
- }
- hi->bucket = NULL;
- hi->last = NULL;
+ if (hi->bucket_marked)
+ {
+ hash_remove_marked(hi->hash, hi->bucket);
+ hi->bucket_marked = false;
+ }
+ hi->bucket = NULL;
+ hi->last = NULL;
}
}
static inline void
-hash_iterator_advance (struct hash_iterator *hi)
+hash_iterator_advance(struct hash_iterator *hi)
{
- hi->last = hi->elem;
- hi->elem = hi->elem->next;
+ hi->last = hi->elem;
+ hi->elem = hi->elem->next;
}
void
-hash_iterator_free (struct hash_iterator *hi)
+hash_iterator_free(struct hash_iterator *hi)
{
- hash_iterator_unlock (hi);
+ hash_iterator_unlock(hi);
}
struct hash_element *
-hash_iterator_next (struct hash_iterator *hi)
+hash_iterator_next(struct hash_iterator *hi)
{
- struct hash_element *ret = NULL;
- if (hi->elem)
+ struct hash_element *ret = NULL;
+ if (hi->elem)
{
- ret = hi->elem;
- hash_iterator_advance (hi);
+ ret = hi->elem;
+ hash_iterator_advance(hi);
}
- else
+ else
{
- while (++hi->bucket_index < hi->bucket_index_end)
- {
- struct hash_bucket *b;
- hash_iterator_unlock (hi);
- b = &hi->hash->buckets[hi->bucket_index];
- if (b->list)
- {
- hash_iterator_lock (hi, b);
- hi->elem = b->list;
- if (hi->elem)
- {
- ret = hi->elem;
- hash_iterator_advance (hi);
- break;
- }
- }
- }
+ while (++hi->bucket_index < hi->bucket_index_end)
+ {
+ struct hash_bucket *b;
+ hash_iterator_unlock(hi);
+ b = &hi->hash->buckets[hi->bucket_index];
+ if (b->list)
+ {
+ hash_iterator_lock(hi, b);
+ hi->elem = b->list;
+ if (hi->elem)
+ {
+ ret = hi->elem;
+ hash_iterator_advance(hi);
+ break;
+ }
+ }
+ }
}
- return ret;
+ return ret;
}
void
-hash_iterator_delete_element (struct hash_iterator *hi)
+hash_iterator_delete_element(struct hash_iterator *hi)
{
- ASSERT (hi->last);
- hi->last->key = NULL;
- hi->bucket_marked = true;
+ ASSERT(hi->last);
+ hi->last->key = NULL;
+ hi->bucket_marked = true;
}
@@ -338,312 +350,326 @@ hash_iterator_delete_element (struct hash_iterator *hi)
struct word
{
- const char *word;
- int n;
+ const char *word;
+ int n;
};
static uint32_t
-word_hash_function (const void *key, uint32_t iv)
+word_hash_function(const void *key, uint32_t iv)
{
- const char *str = (const char *) key;
- const int len = strlen (str);
- return hash_func ((const uint8_t *)str, len, iv);
+ const char *str = (const char *) key;
+ const int len = strlen(str);
+ return hash_func((const uint8_t *)str, len, iv);
}
static bool
-word_compare_function (const void *key1, const void *key2)
+word_compare_function(const void *key1, const void *key2)
{
- return strcmp ((const char *)key1, (const char *)key2) == 0;
+ return strcmp((const char *)key1, (const char *)key2) == 0;
}
static void
-print_nhash (struct hash *hash)
+print_nhash(struct hash *hash)
{
- struct hash_iterator hi;
- struct hash_element *he;
- int count = 0;
+ struct hash_iterator hi;
+ struct hash_element *he;
+ int count = 0;
- hash_iterator_init (hash, &hi, true);
+ hash_iterator_init(hash, &hi, true);
- while ((he = hash_iterator_next (&hi)))
+ while ((he = hash_iterator_next(&hi)))
{
- printf ("%d ", (int) he->value);
- ++count;
+ printf("%d ", (int) he->value);
+ ++count;
}
- printf ("\n");
+ printf("\n");
- hash_iterator_free (&hi);
- ASSERT (count == hash_n_elements (hash));
+ hash_iterator_free(&hi);
+ ASSERT(count == hash_n_elements(hash));
}
static void
-rmhash (struct hash *hash, const char *word)
+rmhash(struct hash *hash, const char *word)
{
- hash_remove (hash, word);
+ hash_remove(hash, word);
}
void
-list_test (void)
+list_test(void)
{
- openvpn_thread_init ();
-
- {
- struct gc_arena gc = gc_new ();
- struct hash *hash = hash_init (10000, get_random (), word_hash_function, word_compare_function);
- struct hash *nhash = hash_init (256, get_random (), word_hash_function, word_compare_function);
-
- printf ("hash_init n_buckets=%d mask=0x%08x\n", hash->n_buckets, hash->mask);
-
- /* parse words from stdin */
- while (true)
- {
- char buf[256];
- char wordbuf[256];
- int wbi;
- int bi;
- char c;
-
- if (!fgets(buf, sizeof(buf), stdin))
- break;
-
- bi = wbi = 0;
- do
- {
- c = buf[bi++];
- if (isalnum (c) || c == '_')
- {
- ASSERT (wbi < (int) sizeof (wordbuf));
- wordbuf[wbi++] = c;
- }
- else
- {
- if (wbi)
- {
- struct word *w;
- ASSERT (wbi < (int) sizeof (wordbuf));
- wordbuf[wbi++] = '\0';
-
- /* word is parsed from stdin */
-
- /* does it already exist in table? */
- w = (struct word *) hash_lookup (hash, wordbuf);
-
- if (w)
- {
- /* yes, increment count */
- ++w->n;
- }
- else
- {
- /* no, make a new object */
- ALLOC_OBJ_GC (w, struct word, &gc);
- w->word = string_alloc (wordbuf, &gc);
- w->n = 1;
- ASSERT (hash_add (hash, w->word, w, false));
- ASSERT (hash_add (nhash, w->word, (void*) ((random() & 0x0F) + 1), false));
- }
- }
- wbi = 0;
- }
- } while (c);
- }
+ openvpn_thread_init();
-#if 1
- /* remove some words from the table */
{
- rmhash (hash, "true");
- rmhash (hash, "false");
- }
+ struct gc_arena gc = gc_new();
+ struct hash *hash = hash_init(10000, get_random(), word_hash_function, word_compare_function);
+ struct hash *nhash = hash_init(256, get_random(), word_hash_function, word_compare_function);
+
+ printf("hash_init n_buckets=%d mask=0x%08x\n", hash->n_buckets, hash->mask);
+
+ /* parse words from stdin */
+ while (true)
+ {
+ char buf[256];
+ char wordbuf[256];
+ int wbi;
+ int bi;
+ char c;
+
+ if (!fgets(buf, sizeof(buf), stdin))
+ {
+ break;
+ }
+
+ bi = wbi = 0;
+ do
+ {
+ c = buf[bi++];
+ if (isalnum(c) || c == '_')
+ {
+ ASSERT(wbi < (int) sizeof(wordbuf));
+ wordbuf[wbi++] = c;
+ }
+ else
+ {
+ if (wbi)
+ {
+ struct word *w;
+ ASSERT(wbi < (int) sizeof(wordbuf));
+ wordbuf[wbi++] = '\0';
+
+ /* word is parsed from stdin */
+
+ /* does it already exist in table? */
+ w = (struct word *) hash_lookup(hash, wordbuf);
+
+ if (w)
+ {
+ /* yes, increment count */
+ ++w->n;
+ }
+ else
+ {
+ /* no, make a new object */
+ ALLOC_OBJ_GC(w, struct word, &gc);
+ w->word = string_alloc(wordbuf, &gc);
+ w->n = 1;
+ ASSERT(hash_add(hash, w->word, w, false));
+ ASSERT(hash_add(nhash, w->word, (void *) ((random() & 0x0F) + 1), false));
+ }
+ }
+ wbi = 0;
+ }
+ } while (c);
+ }
+
+#if 1
+ /* remove some words from the table */
+ {
+ rmhash(hash, "true");
+ rmhash(hash, "false");
+ }
#endif
- /* output contents of hash table */
- {
- int base;
- int inc = 0;
- int count = 0;
-
- for (base = 0; base < hash_n_buckets (hash); base += inc) {
- struct hash_iterator hi;
- struct hash_element *he;
- inc = (get_random () % 3) + 1;
- hash_iterator_init_range (hash, &hi, true, base, base + inc);
-
- while ((he = hash_iterator_next (&hi)))
- {
- struct word *w = (struct word *) he->value;
- printf ("%6d '%s'\n", w->n, w->word);
- ++count;
- }
-
- hash_iterator_free (&hi);
- }
- ASSERT (count == hash_n_elements (hash));
- }
-
+ /* output contents of hash table */
+ {
+ int base;
+ int inc = 0;
+ int count = 0;
+
+ for (base = 0; base < hash_n_buckets(hash); base += inc) {
+ struct hash_iterator hi;
+ struct hash_element *he;
+ inc = (get_random() % 3) + 1;
+ hash_iterator_init_range(hash, &hi, true, base, base + inc);
+
+ while ((he = hash_iterator_next(&hi)))
+ {
+ struct word *w = (struct word *) he->value;
+ printf("%6d '%s'\n", w->n, w->word);
+ ++count;
+ }
+
+ hash_iterator_free(&hi);
+ }
+ ASSERT(count == hash_n_elements(hash));
+ }
+
#if 1
- /* test hash_remove_by_value function */
- {
- int i;
- for (i = 1; i <= 16; ++i)
- {
- printf ("[%d] ***********************************\n", i);
- print_nhash (nhash);
- hash_remove_by_value (nhash, (void *) i, true);
- }
- printf ("FINAL **************************\n");
- print_nhash (nhash);
- }
+ /* test hash_remove_by_value function */
+ {
+ int i;
+ for (i = 1; i <= 16; ++i)
+ {
+ printf("[%d] ***********************************\n", i);
+ print_nhash(nhash);
+ hash_remove_by_value(nhash, (void *) i, true);
+ }
+ printf("FINAL **************************\n");
+ print_nhash(nhash);
+ }
#endif
- hash_free (hash);
- hash_free (nhash);
- gc_free (&gc);
- }
+ hash_free(hash);
+ hash_free(nhash);
+ gc_free(&gc);
+ }
- openvpn_thread_cleanup ();
+ openvpn_thread_cleanup();
}
-#endif
+#endif /* ifdef LIST_TEST */
/*
---------------------------------------------------------------------
-hash() -- hash a variable-length key into a 32-bit value
- k : the key (the unaligned variable-length array of bytes)
- len : the length of the key, counting by bytes
- level : can be any 4-byte value
-Returns a 32-bit value. Every bit of the key affects every bit of
-the return value. Every 1-bit and 2-bit delta achieves avalanche.
-About 36+6len instructions.
-
-The best hash table sizes are powers of 2. There is no need to do
-mod a prime (mod is sooo slow!). If you need less than 32 bits,
-use a bitmask. For example, if you need only 10 bits, do
- h = (h & hashmask(10));
-In which case, the hash table should have hashsize(10) elements.
-
-If you are hashing n strings (uint8_t **)k, do it like this:
- for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
-
-By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. You may use this
-code any way you wish, private, educational, or commercial. It's free.
-
-See http://burlteburtle.net/bob/hash/evahash.html
-Use for hash table lookup, or anything where one collision in 2^32 is
-acceptable. Do NOT use for cryptographic purposes.
-
---------------------------------------------------------------------
-
-mix -- mix 3 32-bit values reversibly.
-For every delta with one or two bit set, and the deltas of all three
- high bits or all three low bits, whether the original value of a,b,c
- is almost all zero or is uniformly distributed,
-* If mix() is run forward or backward, at least 32 bits in a,b,c
- have at least 1/4 probability of changing.
-* If mix() is run forward, every bit of c will change between 1/3 and
- 2/3 of the time. (Well, 22/100 and 78/100 for some 2-bit deltas.)
-mix() was built out of 36 single-cycle latency instructions in a
- structure that could supported 2x parallelism, like so:
- a -= b;
- a -= c; x = (c>>13);
- b -= c; a ^= x;
- b -= a; x = (a<<8);
- c -= a; b ^= x;
- c -= b; x = (b>>13);
- ...
- Unfortunately, superscalar Pentiums and Sparcs can't take advantage
- of that parallelism. They've also turned some of those single-cycle
- latency instructions into multi-cycle latency instructions. Still,
- this is the fastest good hash I could find. There were about 2^^68
- to choose from. I only looked at a billion or so.
-
-James Yonan Notes:
-
-* This function is faster than it looks, and appears to be
- appropriate for our usage in OpenVPN which is primarily
- for hash-table based address lookup (IPv4, IPv6, and Ethernet MAC).
- NOTE: This function is never used for cryptographic purposes, only
- to produce evenly-distributed indexes into hash tables.
-
-* Benchmark results: 11.39 machine cycles per byte on a P2 266Mhz,
- and 12.1 machine cycles per byte on a
- 2.2 Ghz P4 when hashing a 6 byte string.
---------------------------------------------------------------------
-*/
+ * --------------------------------------------------------------------
+ * hash() -- hash a variable-length key into a 32-bit value
+ * k : the key (the unaligned variable-length array of bytes)
+ * len : the length of the key, counting by bytes
+ * level : can be any 4-byte value
+ * Returns a 32-bit value. Every bit of the key affects every bit of
+ * the return value. Every 1-bit and 2-bit delta achieves avalanche.
+ * About 36+6len instructions.
+ *
+ * The best hash table sizes are powers of 2. There is no need to do
+ * mod a prime (mod is sooo slow!). If you need less than 32 bits,
+ * use a bitmask. For example, if you need only 10 bits, do
+ * h = (h & hashmask(10));
+ * In which case, the hash table should have hashsize(10) elements.
+ *
+ * If you are hashing n strings (uint8_t **)k, do it like this:
+ * for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
+ *
+ * By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. You may use this
+ * code any way you wish, private, educational, or commercial. It's free.
+ *
+ * See http://burlteburtle.net/bob/hash/evahash.html
+ * Use for hash table lookup, or anything where one collision in 2^32 is
+ * acceptable. Do NOT use for cryptographic purposes.
+ *
+ * --------------------------------------------------------------------
+ *
+ * mix -- mix 3 32-bit values reversibly.
+ * For every delta with one or two bit set, and the deltas of all three
+ * high bits or all three low bits, whether the original value of a,b,c
+ * is almost all zero or is uniformly distributed,
+ * If mix() is run forward or backward, at least 32 bits in a,b,c
+ * have at least 1/4 probability of changing.
+ * If mix() is run forward, every bit of c will change between 1/3 and
+ * 2/3 of the time. (Well, 22/100 and 78/100 for some 2-bit deltas.)
+ * mix() was built out of 36 single-cycle latency instructions in a
+ * structure that could supported 2x parallelism, like so:
+ * a -= b;
+ * a -= c; x = (c>>13);
+ * b -= c; a ^= x;
+ * b -= a; x = (a<<8);
+ * c -= a; b ^= x;
+ * c -= b; x = (b>>13);
+ * ...
+ * Unfortunately, superscalar Pentiums and Sparcs can't take advantage
+ * of that parallelism. They've also turned some of those single-cycle
+ * latency instructions into multi-cycle latency instructions. Still,
+ * this is the fastest good hash I could find. There were about 2^^68
+ * to choose from. I only looked at a billion or so.
+ *
+ * James Yonan Notes:
+ *
+ * This function is faster than it looks, and appears to be
+ * appropriate for our usage in OpenVPN which is primarily
+ * for hash-table based address lookup (IPv4, IPv6, and Ethernet MAC).
+ * NOTE: This function is never used for cryptographic purposes, only
+ * to produce evenly-distributed indexes into hash tables.
+ *
+ * Benchmark results: 11.39 machine cycles per byte on a P2 266Mhz,
+ * and 12.1 machine cycles per byte on a
+ * 2.2 Ghz P4 when hashing a 6 byte string.
+ * --------------------------------------------------------------------
+ */
#define mix(a,b,c) \
-{ \
- a -= b; a -= c; a ^= (c>>13); \
- b -= c; b -= a; b ^= (a<<8); \
- c -= a; c -= b; c ^= (b>>13); \
- a -= b; a -= c; a ^= (c>>12); \
- b -= c; b -= a; b ^= (a<<16); \
- c -= a; c -= b; c ^= (b>>5); \
- a -= b; a -= c; a ^= (c>>3); \
- b -= c; b -= a; b ^= (a<<10); \
- c -= a; c -= b; c ^= (b>>15); \
-}
+ { \
+ a -= b; a -= c; a ^= (c>>13); \
+ b -= c; b -= a; b ^= (a<<8); \
+ c -= a; c -= b; c ^= (b>>13); \
+ a -= b; a -= c; a ^= (c>>12); \
+ b -= c; b -= a; b ^= (a<<16); \
+ c -= a; c -= b; c ^= (b>>5); \
+ a -= b; a -= c; a ^= (c>>3); \
+ b -= c; b -= a; b ^= (a<<10); \
+ c -= a; c -= b; c ^= (b>>15); \
+ }
uint32_t
-hash_func (const uint8_t *k, uint32_t length, uint32_t initval)
+hash_func(const uint8_t *k, uint32_t length, uint32_t initval)
{
- uint32_t a, b, c, len;
+ uint32_t a, b, c, len;
- /* Set up the internal state */
- len = length;
- a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
- c = initval; /* the previous hash value */
+ /* Set up the internal state */
+ len = length;
+ a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
+ c = initval; /* the previous hash value */
- /*---------------------------------------- handle most of the key */
- while (len >= 12)
+ /*---------------------------------------- handle most of the key */
+ while (len >= 12)
{
- a += (k[0] + ((uint32_t) k[1] << 8)
- + ((uint32_t) k[2] << 16)
- + ((uint32_t) k[3] << 24));
- b += (k[4] + ((uint32_t) k[5] << 8)
- + ((uint32_t) k[6] << 16)
- + ((uint32_t) k[7] << 24));
- c += (k[8] + ((uint32_t) k[9] << 8)
- + ((uint32_t) k[10] << 16)
- + ((uint32_t) k[11] << 24));
- mix (a, b, c);
- k += 12;
- len -= 12;
+ a += (k[0] + ((uint32_t) k[1] << 8)
+ + ((uint32_t) k[2] << 16)
+ + ((uint32_t) k[3] << 24));
+ b += (k[4] + ((uint32_t) k[5] << 8)
+ + ((uint32_t) k[6] << 16)
+ + ((uint32_t) k[7] << 24));
+ c += (k[8] + ((uint32_t) k[9] << 8)
+ + ((uint32_t) k[10] << 16)
+ + ((uint32_t) k[11] << 24));
+ mix(a, b, c);
+ k += 12;
+ len -= 12;
}
- /*------------------------------------- handle the last 11 bytes */
- c += length;
- switch (len) /* all the case statements fall through */
+ /*------------------------------------- handle the last 11 bytes */
+ c += length;
+ switch (len) /* all the case statements fall through */
{
- case 11:
- c += ((uint32_t) k[10] << 24);
- case 10:
- c += ((uint32_t) k[9] << 16);
- case 9:
- c += ((uint32_t) k[8] << 8);
- /* the first byte of c is reserved for the length */
- 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];
- /* case 0: nothing left to add */
+ case 11:
+ c += ((uint32_t) k[10] << 24);
+
+ case 10:
+ c += ((uint32_t) k[9] << 16);
+
+ case 9:
+ c += ((uint32_t) k[8] << 8);
+
+ /* the first byte of c is reserved for the length */
+ 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];
+ /* case 0: nothing left to add */
}
- mix (a, b, c);
- /*-------------------------------------- report the result */
- return c;
+ mix(a, b, c);
+ /*-------------------------------------- report the result */
+ return c;
}
-#else
-static void dummy(void) {}
+#else /* if P2MP_SERVER */
+static void
+dummy(void) {
+}
#endif /* P2MP_SERVER */
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-10 05:24:13 +0000