legacy-libs/grpc/deps/grpc/src/core/lib/gpr/murmur_hash.cc

   1 /*
   2  *
   3  * Copyright 2015 gRPC authors.
   4  *
   5  * Licensed under the Apache License, Version 2.0 (the "License");
   6  * you may not use this file except in compliance with the License.
   7  * You may obtain a copy of the License at
   8  *
   9  *     http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  *
  17  */
  18
  19 #include <grpc/support/port_platform.h>
  20
  21 #include "src/core/lib/gpr/murmur_hash.h"
  22
  23 #include <string.h>
  24
  25 #define ROTL32(x, r) ((x) << (r)) | ((x) >> (32 - (r)))
  26
  27 #define FMIX32(h)    \
  28   (h) ^= (h) >> 16;  \
  29   (h) *= 0x85ebca6b; \
  30   (h) ^= (h) >> 13;  \
  31   (h) *= 0xc2b2ae35; \
  32   (h) ^= (h) >> 16;
  33
  34 uint32_t gpr_murmur_hash3(const void* key, size_t len, uint32_t seed) {
  35   uint32_t h1 = seed;
  36   uint32_t k1;
  37
  38   const uint32_t c1 = 0xcc9e2d51;
  39   const uint32_t c2 = 0x1b873593;
  40
  41   const uint8_t* keyptr = static_cast<const uint8_t*>(key);
  42   const size_t bsize = sizeof(k1);
  43   const size_t nblocks = len / bsize;
  44
  45   /* body */
  46   for (size_t i = 0; i < nblocks; i++, keyptr += bsize) {
  47     memcpy(&k1, keyptr, bsize);
  48
  49     k1 *= c1;
  50     k1 = ROTL32(k1, 15);
  51     k1 *= c2;
  52
  53     h1 ^= k1;
  54     h1 = ROTL32(h1, 13);
  55     h1 = h1 * 5 + 0xe6546b64;
  56   }
  57
  58   k1 = 0;
  59
  60   /* tail */
  61   switch (len & 3) {
  62     case 3:
  63       k1 ^= (static_cast<uint32_t>(keyptr[2])) << 16;
  64     /* fallthrough */
  65     case 2:
  66       k1 ^= (static_cast<uint32_t>(keyptr[1])) << 8;
  67     /* fallthrough */
  68     case 1:
  69       k1 ^= keyptr[0];
  70       k1 *= c1;
  71       k1 = ROTL32(k1, 15);
  72       k1 *= c2;
  73       h1 ^= k1;
  74   };
  75
  76   /* finalization */
  77   h1 ^= static_cast<uint32_t>(len);
  78   FMIX32(h1);
  79   return h1;
  80 }