Line data    Source code

       1             : /*
       2             :  *
       3             :  * Copyright 2015, Google Inc.
       4             :  * All rights reserved.
       5             :  *
       6             :  * Redistribution and use in source and binary forms, with or without
       7             :  * modification, are permitted provided that the following conditions are
       8             :  * met:
       9             :  *
      10             :  *     * Redistributions of source code must retain the above copyright
      11             :  * notice, this list of conditions and the following disclaimer.
      12             :  *     * Redistributions in binary form must reproduce the above
      13             :  * copyright notice, this list of conditions and the following disclaimer
      14             :  * in the documentation and/or other materials provided with the
      15             :  * distribution.
      16             :  *     * Neither the name of Google Inc. nor the names of its
      17             :  * contributors may be used to endorse or promote products derived from
      18             :  * this software without specific prior written permission.
      19             :  *
      20             :  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
      21             :  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
      22             :  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
      23             :  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
      24             :  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
      25             :  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
      26             :  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
      27             :  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
      28             :  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
      29             :  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
      30             :  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
      31             :  *
      32             :  */
      33             : 
      34             : #include "src/core/support/murmur_hash.h"
      35             : 
      36             : #define ROTL32(x, r) ((x) << (r)) | ((x) >> (32 - (r)))
      37             : 
      38             : #define FMIX32(h)    \
      39             :   (h) ^= (h) >> 16;  \
      40             :   (h) *= 0x85ebca6b; \
      41             :   (h) ^= (h) >> 13;  \
      42             :   (h) *= 0xc2b2ae35; \
      43             :   (h) ^= (h) >> 16;
      44             : 
      45             : /* Block read - if your platform needs to do endian-swapping or can only
      46             :    handle aligned reads, do the conversion here */
      47             : #define GETBLOCK32(p, i) (p)[(i)]
      48             : 
      49     4769019 : gpr_uint32 gpr_murmur_hash3(const void *key, size_t len, gpr_uint32 seed) {
      50     4769019 :   const gpr_uint8 *data = (const gpr_uint8 *)key;
      51     4769019 :   const size_t nblocks = len / 4;
      52             :   int i;
      53             : 
      54     4769019 :   gpr_uint32 h1 = seed;
      55             :   gpr_uint32 k1;
      56             : 
      57     4769019 :   const gpr_uint32 c1 = 0xcc9e2d51;
      58     4769019 :   const gpr_uint32 c2 = 0x1b873593;
      59             : 
      60     4769019 :   const gpr_uint32 *blocks = ((const gpr_uint32 *)key) + nblocks;
      61     4769019 :   const gpr_uint8 *tail = (const gpr_uint8 *)(data + nblocks * 4);
      62             : 
      63             :   /* body */
      64    24272013 :   for (i = -(int)nblocks; i; i++) {
      65    19502994 :     k1 = GETBLOCK32(blocks, i);
      66             : 
      67    19502994 :     k1 *= c1;
      68    19502994 :     k1 = ROTL32(k1, 15);
      69    19502994 :     k1 *= c2;
      70             : 
      71    19502994 :     h1 ^= k1;
      72    19502994 :     h1 = ROTL32(h1, 13);
      73    19502994 :     h1 = h1 * 5 + 0xe6546b64;
      74             :   }
      75             : 
      76     4769019 :   k1 = 0;
      77             : 
      78             :   /* tail */
      79     4769019 :   switch (len & 3) {
      80             :     case 3:
      81      879929 :       k1 ^= ((gpr_uint32)tail[2]) << 16;
      82             :     case 2:
      83     1095149 :       k1 ^= ((gpr_uint32)tail[1]) << 8;
      84             :     case 1:
      85     2043041 :       k1 ^= tail[0];
      86     2043041 :       k1 *= c1;
      87     2043041 :       k1 = ROTL32(k1, 15);
      88     2043041 :       k1 *= c2;
      89     2043041 :       h1 ^= k1;
      90             :   };
      91             : 
      92             :   /* finalization */
      93     4769019 :   h1 ^= (gpr_uint32)len;
      94     4769019 :   FMIX32(h1);
      95     4769019 :   return h1;
      96             : }