git.m6w6.name Git - awesomized/libmemcached/blob - src/libhashkit/murmur3.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/hashkitcon.h"
  17
  18 #include "libhashkit/murmur3.h"
  19
  20 //-----------------------------------------------------------------------------
  21 // Platform-specific functions and macros
  22
  23 #ifdef __GNUC__
  24 #  define FORCE_INLINE __attribute__((always_inline)) inline
  25 #else
  26 #  define FORCE_INLINE inline
  27 #endif
  28
  29 static FORCE_INLINE uint32_t rotl32(uint32_t x, int8_t r) {
  30   return (x << r) | (x >> (32 - r));
  31 }
  32
  33 #define ROTL32(x, y) rotl32(x, y)
  34
  35 //-----------------------------------------------------------------------------
  36 // Block read - if your platform needs to do endian-swapping or can only
  37 // handle aligned reads, do the conversion here
  38
  39 #include <cassert>
  40 #include <cstring>
  41 template<typename T>
  42 static inline T getblock(const T *blocks, int i) {
  43   T b;
  44   memcpy(&b, ((const uint8_t *) blocks) + i * sizeof(T), sizeof(T));
  45   return b;
  46 }
  47
  48 //-----------------------------------------------------------------------------
  49 // Finalization mix - force all bits of a hash block to avalanche
  50
  51 static FORCE_INLINE uint32_t fmix32(uint32_t h) {
  52   h ^= h >> 16;
  53   h *= 0x85ebca6b;
  54   h ^= h >> 13;
  55   h *= 0xc2b2ae35;
  56   h ^= h >> 16;
  57
  58   return h;
  59 }
  60
  61 //-----------------------------------------------------------------------------
  62
  63 void MurmurHash3_x86_32(const void *key, int len, uint32_t seed, void *out) {
  64   const uint8_t *data = (const uint8_t *) key;
  65   const int nblocks = len / 4;
  66   int i;
  67
  68   uint32_t h1 = seed;
  69
  70   uint32_t c1 = 0xcc9e2d51;
  71   uint32_t c2 = 0x1b873593;
  72
  73   //----------
  74   // body
  75
  76   const uint32_t *blocks = (const uint32_t *) (data + nblocks * 4);
  77
  78   for (i = -nblocks; i; i++) {
  79     uint32_t k1 = getblock(blocks, i);
  80 #if WORDS_BIGENDIAN
  81     k1 = BYTESWAP_32(k1);
  82 #endif
  83
  84     k1 *= c1;
  85     k1 = ROTL32(k1, 15);
  86     k1 *= c2;
  87
  88     h1 ^= k1;
  89     h1 = ROTL32(h1, 13);
  90     h1 = h1 * 5 + 0xe6546b64;
  91   }
  92
  93   //----------
  94   // tail
  95
  96   const uint8_t *tail = (const uint8_t *) (data + nblocks * 4);
  97
  98   uint32_t k1 = 0;
  99   memcpy(&k1, tail, len & 3);
 100 #if WORDS_BIGENDIAN
 101   k1 = BYTESWAP_32(k1);
 102 #endif
 103
 104   k1 *= c1;
 105   k1 = ROTL32(k1, 15);
 106   k1 *= c2;
 107   h1 ^= k1;
 108
 109   //----------
 110   // finalization
 111
 112   h1 ^= len;
 113
 114   h1 = fmix32(h1);
 115
 116   *(uint32_t *) out = h1;
 117 }