git.m6w6.name Git - awesomized/libmemcached/blob - src/libhashkit/murmur.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 Michael Wallner   <mike@php.net>                |
  13     +--------------------------------------------------------------------+
  14 */
  15
  16 #include "libhashkit/common.h"
  17
  18 #ifdef HAVE_MURMUR_HASH
  19
  20 #  ifdef BYTESWAP_HEADER
  21 #    include BYTESWAP_HEADER
  22 #  endif
  23
  24 #  include <cstring>
  25
  26 uint32_t hashkit_murmur(const char *key, size_t length, void *context) {
  27   /*
  28     'm' and 'r' are mixing constants generated offline.  They're not
  29     really 'magic', they just happen to work well.
  30   */
  31
  32   const unsigned int m = 0x5bd1e995;
  33   const uint32_t seed = (0xdeadbeef * (uint32_t) length);
  34   const int r = 24;
  35
  36   // Initialize the hash to a 'random' value
  37
  38   uint32_t h = seed ^ (uint32_t) length;
  39
  40   // Mix 4 bytes at a time into the hash
  41
  42   const unsigned char *data = (const unsigned char *) key;
  43   (void) context;
  44
  45   while (length >= 4) {
  46     uint32_t k;
  47     memcpy(&k, data, sizeof(k));
  48 #  if WORDS_BIGENDIAN
  49     k = BYTESWAP_32(k);
  50 #  endif
  51
  52     k *= m;
  53     k ^= k >> r;
  54     k *= m;
  55
  56     h *= m;
  57     h ^= k;
  58
  59     data += 4;
  60     length -= 4;
  61   }
  62
  63   // Handle the last few bytes of the input array
  64   if (length) {
  65     uint32_t k = 0;
  66     memcpy(&k, data, length);
  67 #  if WORDS_BIGENDIAN
  68     k = BYTESWAP_32(k);
  69 #  endif
  70     h ^= k;
  71     h *= m;
  72   }
  73
  74   /*
  75     Do a few final mixes of the hash to ensure the last few bytes are
  76     well-incorporated.
  77   */
  78
  79   h ^= h >> 13;
  80   h *= m;
  81   h ^= h >> 15;
  82
  83   return h;
  84 }
  85
  86 #else
  87 uint32_t hashkit_murmur(const char *, size_t, void *) {
  88   return 0;
  89 }
  90 #endif