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    18204115 : gpr_uint32 gpr_murmur_hash3(const void *key, size_t len, gpr_uint32 seed) {
      50    18192481 :   const gpr_uint8 *data = (const gpr_uint8 *)key;
      51    18204115 :   const size_t nblocks = len / 4;
      52             :   int i;
      53             : 
      54    18192481 :   gpr_uint32 h1 = seed;
      55             :   gpr_uint32 k1;
      56             : 
      57    18192481 :   const gpr_uint32 c1 = 0xcc9e2d51;
      58    18192481 :   const gpr_uint32 c2 = 0x1b873593;
      59             : 
      60    18204115 :   const gpr_uint32 *blocks = ((const gpr_uint32 *)key) + nblocks;
      61    18204115 :   const gpr_uint8 *tail = (const gpr_uint8 *)(data + nblocks * 4);
      62             : 
      63             :   /* body */
      64    64774889 :   for (i = -(int)nblocks; i; i++) {
      65    46570774 :     k1 = GETBLOCK32(blocks, i);
      66             : 
      67    46570774 :     k1 *= c1;
      68    46570774 :     k1 = ROTL32(k1, 15);
      69    46570774 :     k1 *= c2;
      70             : 
      71    46570774 :     h1 ^= k1;
      72    46570774 :     h1 = ROTL32(h1, 13);
      73    46570774 :     h1 = h1 * 5 + 0xe6546b64;
      74             :   }
      75             : 
      76    18192481 :   k1 = 0;
      77             : 
      78             :   /* tail */
      79    18204115 :   switch (len & 3) {
      80             :     case 3:
      81     3352389 :       k1 ^= ((gpr_uint32)tail[2]) << 16;
      82             :     case 2:
      83     8569010 :       k1 ^= ((gpr_uint32)tail[1]) << 8;
      84             :     case 1:
      85    11582523 :       k1 ^= tail[0];
      86    11582523 :       k1 *= c1;
      87    11582523 :       k1 = ROTL32(k1, 15);
      88    11582523 :       k1 *= c2;
      89    11582523 :       h1 ^= k1;
      90             :   };
      91             : 
      92             :   /* finalization */
      93    18204115 :   h1 ^= (gpr_uint32)len;
      94    18204115 :   FMIX32(h1);
      95    18204115 :   return h1;
      96             : }