From 3a2bbdb05ca6a6996e424c9fb225cb0d53804125 Mon Sep 17 00:00:00 2001
From: Alberto Gonzalez Iniesta <agi@inittab.org>
Date: Tue, 27 Dec 2016 18:25:47 +0100
Subject: New upstream version 2.4.0

---
 src/openvpn/list.c | 924 +++++++++++++++++++++++++++--------------------------
 1 file changed, 475 insertions(+), 449 deletions(-)

(limited to 'src/openvpn/list.c')

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 */
-- 
cgit v1.2.3