git.m6w6.name Git - awesomized/libmemcached/blob - src/libhashkit/hsieh.cc

   1 /*
   2     +--------------------------------------------------------------------+
   3     | libmemcached - C/C++ Client Library for memcached                  |
   4     +--------------------------------------------------------------------+
   5     | Redistribution and use in source and binary forms, with or without |
   6     | modification, are permitted under the terms of the BSD license.    |
   7     | You should have received a copy of the license in a bundled file   |
   8     | named LICENSE; in case you did not receive a copy you can review   |
   9     | the terms online at: https://opensource.org/licenses/BSD-3-Clause  |
  10     +--------------------------------------------------------------------+
  11     | Copyright (c) 2006-2014 Brian Aker   https://datadifferential.com/ |
  12     | Copyright (c) 2020-2021 Michael Wallner        https://awesome.co/ |
  13     +--------------------------------------------------------------------+
  14 */
  15
  16 #include "libhashkit/common.h"
  17
  18 #undef get16bits
  19 #if (defined(__GNUC__) && defined(__i386__))
  20 #  define get16bits(d) (*((const uint16_t *) (d)))
  21 #endif
  22
  23 #if !defined(get16bits)
  24 #  define get16bits(d) \
  25     ((((uint32_t)(((const uint8_t *) (d))[1])) << 8) + (uint32_t)(((const uint8_t *) (d))[0]))
  26 #endif
  27
  28 #ifdef HAVE_HSIEH_HASH
  29 uint32_t hashkit_hsieh(const char *key, size_t key_length, void *) {
  30   uint32_t hash = 0, tmp;
  31   int rem;
  32
  33   if (key_length <= 0 || key == NULL)
  34     return 0;
  35
  36   rem = key_length & 3;
  37   key_length >>= 2;
  38
  39   /* Main loop */
  40   for (; key_length > 0; key_length--) {
  41     hash += get16bits(key);
  42     tmp = (get16bits(key + 2) << 11) ^ hash;
  43     hash = (hash << 16) ^ tmp;
  44     key += 2 * sizeof(uint16_t);
  45     hash += hash >> 11;
  46   }
  47
  48   /* Handle end cases */
  49   switch (rem) {
  50   case 3:
  51     hash += get16bits(key);
  52     hash ^= hash << 16;
  53     hash ^= (uint32_t) key[sizeof(uint16_t)] << 18;
  54     hash += hash >> 11;
  55     break;
  56   case 2:
  57     hash += get16bits(key);
  58     hash ^= hash << 11;
  59     hash += hash >> 17;
  60     break;
  61   case 1:
  62     hash += (unsigned char) (*key);
  63     hash ^= hash << 10;
  64     hash += hash >> 1;
  65   default:
  66     break;
  67   }
  68
  69   /* Force "avalanching" of final 127 bits */
  70   hash ^= hash << 3;
  71   hash += hash >> 5;
  72   hash ^= hash << 4;
  73   hash += hash >> 17;
  74   hash ^= hash << 25;
  75   hash += hash >> 6;
  76
  77   return hash;
  78 }
  79 #else
  80 uint32_t hashkit_hsieh(const char *, size_t, void *) {
  81   return 0;
  82 }
  83 #endif