ceph/src/rocksdb/util/murmurhash.cc

   1 //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
   2 //  This source code is licensed under both the GPLv2 (found in the
   3 //  COPYING file in the root directory) and Apache 2.0 License
   4 //  (found in the LICENSE.Apache file in the root directory).
   5 //
   6 /*
   7   Murmurhash from http://sites.google.com/site/murmurhash/
   8
   9   All code is released to the public domain. For business purposes, Murmurhash
  10   is under the MIT license.
  11 */
  12 #include "murmurhash.h"
  13 #include "port/lang.h"
  14
  15 #if defined(__x86_64__)
  16
  17 // -------------------------------------------------------------------
  18 //
  19 // The same caveats as 32-bit MurmurHash2 apply here - beware of alignment
  20 // and endian-ness issues if used across multiple platforms.
  21 //
  22 // 64-bit hash for 64-bit platforms
  23
  24 #ifdef ROCKSDB_UBSAN_RUN
  25 #if defined(__clang__)
  26 __attribute__((__no_sanitize__("alignment")))
  27 #elif defined(__GNUC__)
  28 __attribute__((__no_sanitize_undefined__))
  29 #endif
  30 #endif
  31 uint64_t MurmurHash64A ( const void * key, int len, unsigned int seed )
  32 {
  33     const uint64_t m = 0xc6a4a7935bd1e995;
  34     const int r = 47;
  35
  36     uint64_t h = seed ^ (len * m);
  37
  38     const uint64_t * data = (const uint64_t *)key;
  39     const uint64_t * end = data + (len/8);
  40
  41     while(data != end)
  42     {
  43         uint64_t k = *data++;
  44
  45         k *= m;
  46         k ^= k >> r;
  47         k *= m;
  48
  49         h ^= k;
  50         h *= m;
  51     }
  52
  53     const unsigned char * data2 = (const unsigned char*)data;
  54
  55     switch(len & 7)
  56     {
  57     case 7: h ^= ((uint64_t)data2[6]) << 48; FALLTHROUGH_INTENDED;
  58     case 6: h ^= ((uint64_t)data2[5]) << 40; FALLTHROUGH_INTENDED;
  59     case 5: h ^= ((uint64_t)data2[4]) << 32; FALLTHROUGH_INTENDED;
  60     case 4: h ^= ((uint64_t)data2[3]) << 24; FALLTHROUGH_INTENDED;
  61     case 3: h ^= ((uint64_t)data2[2]) << 16; FALLTHROUGH_INTENDED;
  62     case 2: h ^= ((uint64_t)data2[1]) << 8;  FALLTHROUGH_INTENDED;
  63     case 1: h ^= ((uint64_t)data2[0]);
  64         h *= m;
  65     };
  66
  67     h ^= h >> r;
  68     h *= m;
  69     h ^= h >> r;
  70
  71     return h;
  72 }
  73
  74 #elif defined(__i386__)
  75
  76 // -------------------------------------------------------------------
  77 //
  78 // Note - This code makes a few assumptions about how your machine behaves -
  79 //
  80 // 1. We can read a 4-byte value from any address without crashing
  81 // 2. sizeof(int) == 4
  82 //
  83 // And it has a few limitations -
  84 //
  85 // 1. It will not work incrementally.
  86 // 2. It will not produce the same results on little-endian and big-endian
  87 //    machines.
  88
  89 unsigned int MurmurHash2 ( const void * key, int len, unsigned int seed )
  90 {
  91     // 'm' and 'r' are mixing constants generated offline.
  92     // They're not really 'magic', they just happen to work well.
  93
  94     const unsigned int m = 0x5bd1e995;
  95     const int r = 24;
  96
  97     // Initialize the hash to a 'random' value
  98
  99     unsigned int h = seed ^ len;
 100
 101     // Mix 4 bytes at a time into the hash
 102
 103     const unsigned char * data = (const unsigned char *)key;
 104
 105     while(len >= 4)
 106     {
 107         unsigned int k = *(unsigned int *)data;
 108
 109         k *= m;
 110         k ^= k >> r;
 111         k *= m;
 112
 113         h *= m;
 114         h ^= k;
 115
 116         data += 4;
 117         len -= 4;
 118     }
 119
 120     // Handle the last few bytes of the input array
 121
 122     switch(len)
 123     {
 124     case 3: h ^= data[2] << 16; FALLTHROUGH_INTENDED;
 125     case 2: h ^= data[1] << 8;  FALLTHROUGH_INTENDED;
 126     case 1: h ^= data[0];
 127         h *= m;
 128     };
 129
 130     // Do a few final mixes of the hash to ensure the last few
 131     // bytes are well-incorporated.
 132
 133     h ^= h >> 13;
 134     h *= m;
 135     h ^= h >> 15;
 136
 137     return h;
 138 }
 139
 140 #else
 141
 142 // -------------------------------------------------------------------
 143 //
 144 // Same as MurmurHash2, but endian- and alignment-neutral.
 145 // Half the speed though, alas.
 146
 147 unsigned int MurmurHashNeutral2 ( const void * key, int len, unsigned int seed )
 148 {
 149     const unsigned int m = 0x5bd1e995;
 150     const int r = 24;
 151
 152     unsigned int h = seed ^ len;
 153
 154     const unsigned char * data = (const unsigned char *)key;
 155
 156     while(len >= 4)
 157     {
 158         unsigned int k;
 159
 160         k  = data[0];
 161         k |= data[1] << 8;
 162         k |= data[2] << 16;
 163         k |= data[3] << 24;
 164
 165         k *= m;
 166         k ^= k >> r;
 167         k *= m;
 168
 169         h *= m;
 170         h ^= k;
 171
 172         data += 4;
 173         len -= 4;
 174     }
 175
 176     switch(len)
 177     {
 178     case 3: h ^= data[2] << 16; FALLTHROUGH_INTENDED;
 179     case 2: h ^= data[1] << 8;  FALLTHROUGH_INTENDED;
 180     case 1: h ^= data[0];
 181         h *= m;
 182     };
 183
 184     h ^= h >> 13;
 185     h *= m;
 186     h ^= h >> 15;
 187
 188     return h;
 189 }
 190
 191 #endif