/*
  *  OpenVPN -- An application to securely tunnel IP networks
  *             over a single TCP/UDP port, with support for SSL/TLS-based
  *             session authentication and key exchange,
  *             packet encryption, packet authentication, and
  *             packet compression.
  *

  *  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
  *  as published by the Free Software Foundation.
  *
  *  This program is distributed in the hope that it will be useful,
  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  *  GNU General Public License for more details.
  *

  *  You should have received a copy of the GNU General Public License along
  *  with this program; if not, write to the Free Software Foundation, Inc.,
  *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

  */
 

 #ifdef HAVE_CONFIG_H
 #include "config.h"
 #elif defined(_MSC_VER)
 #include "config-msvc.h"
 #endif
 

 #include "syshead.h"
 
 #if P2MP_SERVER
 

 #include "integer.h"

 #include "list.h"
 #include "misc.h"
 
 #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))

 {

     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;

     }

     return h;

 }
 
 void

 hash_free(struct hash *hash)

 {

     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;
         }

     }

     free(hash->buckets);
     free(hash);

 }
 
 struct hash_element *

 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;

     he = bucket->list;

     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;

     }
 

     return NULL;

 }
 
 bool

 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;

     he = bucket->list;

     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;

     }

     return false;

 }
 
 bool

 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;

     hv = hash_value(hash, key);
     bucket = &hash->buckets[hv & hash->mask];

     if ((he = hash_lookup_fast(hash, bucket, key, hv))) /* already exists? */

     {

         if (replace)
         {
             he->value = value;
             ret = true;
         }

     }

     else

     {

         hash_add_fast(hash, bucket, key, hv, value);
         ret = true;

     }
 

     return ret;

 }
 
 void

 hash_remove_by_value(struct hash *hash, void *value)

 {

     struct hash_iterator hi;
     struct hash_element *he;

     hash_iterator_init(hash, &hi);
     while ((he = hash_iterator_next(&hi)))

     {

         if (he->value == value)
         {
             hash_iterator_delete_element(&hi);
         }

     }

     hash_iterator_free(&hi);

 }
 
 static void

 hash_remove_marked(struct hash *hash, struct hash_bucket *bucket)

 {

     struct hash_element *prev = NULL;
     struct hash_element *he = bucket->list;

     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;
         }

     }
 }
 
 uint32_t

 void_ptr_hash_function(const void *key, uint32_t iv)

 {

     return hash_func((const void *)&key, sizeof(key), iv);

 }
 
 bool

 void_ptr_compare_function(const void *key1, const void *key2)

 {

     return key1 == key2;

 }
 
 void

 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;

 }
 
 void

 hash_iterator_init(struct hash *hash,
                    struct hash_iterator *hi)

 {

     hash_iterator_init_range(hash, hi, 0, hash->n_buckets);

 }
 
 static inline void

 hash_iterator_lock(struct hash_iterator *hi, struct hash_bucket *b)

 {

     hi->bucket = b;
     hi->last = NULL;
     hi->bucket_marked = false;

 }
 
 static inline void

 hash_iterator_unlock(struct hash_iterator *hi)

 {

     if (hi->bucket)

     {

         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)

 {

     hi->last = hi->elem;
     hi->elem = hi->elem->next;

 }
 
 void

 hash_iterator_free(struct hash_iterator *hi)

 {

     hash_iterator_unlock(hi);

 }
 
 struct hash_element *

 hash_iterator_next(struct hash_iterator *hi)

 {

     struct hash_element *ret = NULL;
     if (hi->elem)

     {

         ret = hi->elem;
         hash_iterator_advance(hi);

     }

     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;
                 }
             }
         }

     }

     return ret;

 }
 
 void

 hash_iterator_delete_element(struct hash_iterator *hi)

 {

     ASSERT(hi->last);
     hi->last->key = NULL;
     hi->bucket_marked = true;

 }
 
 
 #ifdef LIST_TEST
 
 /*
  * Test the hash code by implementing a simple
  * word frequency algorithm.
  */
 
 struct word
 {

     const char *word;
     int n;

 };
 
 static uint32_t

 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);

 }
 
 static bool

 word_compare_function(const void *key1, const void *key2)

 {

     return strcmp((const char *)key1, (const char *)key2) == 0;

 }
 
 static void

 print_nhash(struct hash *hash)

 {

     struct hash_iterator hi;
     struct hash_element *he;
     int count = 0;

     hash_iterator_init(hash, &hi, true);

     while ((he = hash_iterator_next(&hi)))

     {

         printf("%d ", (int) he->value);
         ++count;

     }

     printf("\n");

     hash_iterator_free(&hi);
     ASSERT(count == hash_n_elements(hash));

 }
 
 static void

 rmhash(struct hash *hash, const char *word)

 {

     hash_remove(hash, word);

 }
 
 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);
         }
 
 #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));
         }
 

 #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);
         }

 #endif
 

         hash_free(hash);
         hash_free(nhash);
         gc_free(&gc);
     }

     openvpn_thread_cleanup();

 }
 

 #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.
  * --------------------------------------------------------------------
  */

 
 #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);  \
     }

 
 uint32_t

 hash_func(const uint8_t *k, uint32_t length, uint32_t initval)

 {

     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 */

     /*---------------------------------------- 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;

     }
 

     /*------------------------------------- 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 */

     }

     mix(a, b, c);
     /*-------------------------------------- report the result */
     return c;

 }
 

 #else  /* if P2MP_SERVER */
 static void

 dummy(void)
 {

 }

 #endif /* P2MP_SERVER */