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

   1 /*
   2     +--------------------------------------------------------------------+
   3     | libmemcached-awesome - 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 /* By Paul Hsieh (C) 2004, 2005.  Covered under the Paul Hsieh
  17  * derivative license.
  18  * See: http://www.azillionmonkeys.com/qed/weblicense.html for license
  19  * details.
  20  * http://www.azillionmonkeys.com/qed/hash.html
  21 */
  22
  23 #include "libhashkit/common.h"
  24
  25 #undef get16bits
  26 #if (defined(__GNUC__) && defined(__i386__))
  27 #  define get16bits(d) (*((const uint16_t *) (d)))
  28 #endif
  29
  30 #if !defined(get16bits)
  31 #  define get16bits(d) \
  32     ((((uint32_t)(((const uint8_t *) (d))[1])) << 8) + (uint32_t)(((const uint8_t *) (d))[0]))
  33 #endif
  34
  35 #ifdef HAVE_HSIEH_HASH
  36 uint32_t hashkit_hsieh(const char *key, size_t key_length, void *) {
  37   uint32_t hash = 0, tmp;
  38   int rem;
  39
  40   if (key_length <= 0 || key == NULL)
  41     return 0;
  42
  43   rem = key_length & 3;
  44   key_length >>= 2;
  45
  46   /* Main loop */
  47   for (; key_length > 0; key_length--) {
  48     hash += get16bits(key);
  49     tmp = (get16bits(key + 2) << 11) ^ hash;
  50     hash = (hash << 16) ^ tmp;
  51     key += 2 * sizeof(uint16_t);
  52     hash += hash >> 11;
  53   }
  54
  55   /* Handle end cases */
  56   switch (rem) {
  57   case 3:
  58     hash += get16bits(key);
  59     hash ^= hash << 16;
  60     hash ^= (uint32_t) key[sizeof(uint16_t)] << 18;
  61     hash += hash >> 11;
  62     break;
  63   case 2:
  64     hash += get16bits(key);
  65     hash ^= hash << 11;
  66     hash += hash >> 17;
  67     break;
  68   case 1:
  69     hash += (unsigned char) (*key);
  70     hash ^= hash << 10;
  71     hash += hash >> 1;
  72   default:
  73     break;
  74   }
  75
  76   /* Force "avalanching" of final 127 bits */
  77   hash ^= hash << 3;
  78   hash += hash >> 5;
  79   hash ^= hash << 4;
  80   hash += hash >> 17;
  81   hash ^= hash << 25;
  82   hash += hash >> 6;
  83
  84   return hash;
  85 }
  86 #else
  87 uint32_t hashkit_hsieh(const char *, size_t, void *) {
  88   return 0;
  89 }
  90 #endif