"Fossies" - the Fresh Open Source Software Archive

Member "memcached-1.6.15/murmur3_hash.c" (16 Jul 2020, 2826 Bytes) of package /linux/www/memcached-1.6.15.tar.gz:

    1 //-----------------------------------------------------------------------------
    2 // MurmurHash3 was written by Austin Appleby, and is placed in the public
    3 // domain. The author hereby disclaims copyright to this source code.
    4 
    5 // Note - The x86 and x64 versions do _not_ produce the same results, as the
    6 // algorithms are optimized for their respective platforms. You can still
    7 // compile and run any of them on any platform, but your performance with the
    8 // non-native version will be less than optimal.
    9 
   10 #include "murmur3_hash.h"
   11 
   12 //-----------------------------------------------------------------------------
   13 // Platform-specific functions and macros
   14 
   15 // Microsoft Visual Studio
   16 
   17 #if defined(_MSC_VER)
   18 
   19 #define FORCE_INLINE    __forceinline
   20 
   21 #include <stdlib.h>
   22 
   23 #define ROTL32(x,y)    _rotl(x,y)
   24 
   25 #define BIG_CONSTANT(x) (x)
   26 
   27 // Other compilers
   28 
   29 #else    // defined(_MSC_VER)
   30 
   31 #define    FORCE_INLINE inline __attribute__((always_inline))
   32 
   33 static inline uint32_t rotl32 ( uint32_t x, int8_t r )
   34 {
   35   return (x << r) | (x >> (32 - r));
   36 }
   37 
   38 #define    ROTL32(x,y)    rotl32(x,y)
   39 
   40 #define BIG_CONSTANT(x) (x##LLU)
   41 
   42 #endif // !defined(_MSC_VER)
   43 
   44 //-----------------------------------------------------------------------------
   45 // Block read - if your platform needs to do endian-swapping or can only
   46 // handle aligned reads, do the conversion here
   47 
   48 static FORCE_INLINE uint32_t getblock32 ( const uint32_t * p, int i )
   49 {
   50   return p[i];
   51 }
   52 
   53 //-----------------------------------------------------------------------------
   54 // Finalization mix - force all bits of a hash block to avalanche
   55 
   56 static FORCE_INLINE uint32_t fmix32 ( uint32_t h )
   57 {
   58   h ^= h >> 16;
   59   h *= 0x85ebca6b;
   60   h ^= h >> 13;
   61   h *= 0xc2b2ae35;
   62   h ^= h >> 16;
   63 
   64   return h;
   65 }
   66 
   67 //-----------------------------------------------------------------------------
   68 
   69 /* Definition modified slightly from the public domain interface (no seed +
   70  * return value */
   71 uint32_t MurmurHash3_x86_32 ( const void * key, size_t length)
   72 {
   73   const uint8_t * data = (const uint8_t*)key;
   74   const int nblocks = length / 4;
   75 
   76   uint32_t h1 = 0;
   77 
   78   uint32_t c1 = 0xcc9e2d51;
   79   uint32_t c2 = 0x1b873593;
   80 
   81   //----------
   82   // body
   83 
   84   const uint32_t * blocks = (const uint32_t *)(data + nblocks*4);
   85 
   86   for(int i = -nblocks; i; i++)
   87   {
   88     uint32_t k1 = getblock32(blocks,i);
   89 
   90     k1 *= c1;
   91     k1 = ROTL32(k1,15);
   92     k1 *= c2;
   93 
   94     h1 ^= k1;
   95     h1 = ROTL32(h1,13);
   96     h1 = h1*5+0xe6546b64;
   97   }
   98 
   99   //----------
  100   // tail
  101 
  102   const uint8_t * tail = (const uint8_t*)(data + nblocks*4);
  103 
  104   uint32_t k1 = 0;
  105 
  106   switch(length & 3)
  107   {
  108   case 3: k1 ^= tail[2] << 16;
  109   case 2: k1 ^= tail[1] << 8;
  110   case 1: k1 ^= tail[0];
  111           k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
  112   };
  113 
  114   //----------
  115   // finalization
  116 
  117   h1 ^= length;
  118 
  119   h1 = fmix32(h1);
  120 
  121   //*(uint32_t*)out = h1;
  122   return h1;
  123 }
  124