git.m6w6.name Git - m6w6/libmemcached/blob - libhashkit/hsieh.c

   1 /* By Paul Hsieh (C) 2004, 2005.  Covered under the Paul Hsieh
   2  * derivative license.
   3  * See: http://www.azillionmonkeys.com/qed/weblicense.html for license
   4  * details.
   5  * http://www.azillionmonkeys.com/qed/hash.html
   6 */
   7
   8 #include "hash_common.h"
   9
  10 #undef get16bits
  11 #if (defined(__GNUC__) && defined(__i386__))
  12 #define get16bits(d) (*((const uint16_t *) (d)))
  13 #endif
  14
  15 #if !defined (get16bits)
  16 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
  17                       +(uint32_t)(((const uint8_t *)(d))[0]) )
  18 #endif
  19
  20 uint32_t hashkit_hsieh(const char *key, size_t key_length)
  21 {
  22   uint32_t hash = 0, tmp;
  23   int rem;
  24
  25   if (key_length <= 0 || key == NULL)
  26     return 0;
  27
  28   rem = key_length & 3;
  29   key_length >>= 2;
  30
  31   /* Main loop */
  32   for (;key_length > 0; key_length--)
  33   {
  34     hash  += get16bits (key);
  35     tmp    = (get16bits (key+2) << 11) ^ hash;
  36     hash   = (hash << 16) ^ tmp;
  37     key  += 2*sizeof (uint16_t);
  38     hash  += hash >> 11;
  39   }
  40
  41   /* Handle end cases */
  42   switch (rem)
  43   {
  44   case 3: hash += get16bits (key);
  45           hash ^= hash << 16;
  46           hash ^= key[sizeof (uint16_t)] << 18;
  47           hash += hash >> 11;
  48           break;
  49   case 2: hash += get16bits (key);
  50           hash ^= hash << 11;
  51           hash += hash >> 17;
  52           break;
  53   case 1: hash += *key;
  54           hash ^= hash << 10;
  55           hash += hash >> 1;
  56   }
  57
  58   /* Force "avalanching" of final 127 bits */
  59   hash ^= hash << 3;
  60   hash += hash >> 5;
  61   hash ^= hash << 4;
  62   hash += hash >> 17;
  63   hash ^= hash << 25;
  64   hash += hash >> 6;
  65
  66   return hash;
  67 }
  68