module/zcommon/cityhash.c

   1 // Copyright (c) 2011 Google, Inc.
   2 //
   3 // Permission is hereby granted, free of charge, to any person obtaining a copy
   4 // of this software and associated documentation files (the "Software"), to deal
   5 // in the Software without restriction, including without limitation the rights
   6 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   7 // copies of the Software, and to permit persons to whom the Software is
   8 // furnished to do so, subject to the following conditions:
   9 //
  10 // The above copyright notice and this permission notice shall be included in
  11 // all copies or substantial portions of the Software.
  12 //
  13 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  14 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  15 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  16 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  17 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  18 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  19 // THE SOFTWARE.
  20
  21 /*
  22  * Copyright (c) 2017 by Delphix. All rights reserved.
  23  */
  24
  25 #include <cityhash.h>
  26
  27 #define HASH_K1 0xb492b66fbe98f273ULL
  28 #define HASH_K2 0x9ae16a3b2f90404fULL
  29
  30 /*
  31  * Bitwise right rotate.  Normally this will compile to a single
  32  * instruction.
  33  */
  34 static inline uint64_t
  35 rotate(uint64_t val, int shift)
  36 {
  37         // Avoid shifting by 64: doing so yields an undefined result.
  38         return (shift == 0 ? val : (val >> shift) | (val << (64 - shift)));
  39 }
  40
  41 static inline uint64_t
  42 cityhash_helper(uint64_t u, uint64_t v, uint64_t mul)
  43 {
  44         uint64_t a = (u ^ v) * mul;
  45         a ^= (a >> 47);
  46         uint64_t b = (v ^ a) * mul;
  47         b ^= (b >> 47);
  48         b *= mul;
  49         return (b);
  50 }
  51
  52 static inline uint64_t
  53 cityhash_impl(uint64_t w1, uint64_t w2, uint64_t w3, uint64_t w4)
  54 {
  55         uint64_t mul = HASH_K2 + 64;
  56         uint64_t a = w1 * HASH_K1;
  57         uint64_t b = w2;
  58         uint64_t c = w4 * mul;
  59         uint64_t d = w3 * HASH_K2;
  60         return (cityhash_helper(rotate(a + b, 43) + rotate(c, 30) + d,
  61             a + rotate(b + HASH_K2, 18) + c, mul));
  62 }
  63
  64 /*
  65  * Passing w as the 2nd argument could save one 64-bit multiplication.
  66  */
  67 uint64_t
  68 cityhash1(uint64_t w)
  69 {
  70         return (cityhash_impl(0, w, 0, 0));
  71 }
  72
  73 uint64_t
  74 cityhash2(uint64_t w1, uint64_t w2)
  75 {
  76         return (cityhash_impl(w1, w2, 0, 0));
  77 }
  78
  79 uint64_t
  80 cityhash3(uint64_t w1, uint64_t w2, uint64_t w3)
  81 {
  82         return (cityhash_impl(w1, w2, w3, 0));
  83 }
  84
  85 uint64_t
  86 cityhash4(uint64_t w1, uint64_t w2, uint64_t w3, uint64_t w4)
  87 {
  88         return (cityhash_impl(w1, w2, w3, w4));
  89 }
  90
  91 #if defined(_KERNEL)
  92 EXPORT_SYMBOL(cityhash1);
  93 EXPORT_SYMBOL(cityhash2);
  94 EXPORT_SYMBOL(cityhash3);
  95 EXPORT_SYMBOL(cityhash4);
  96 #endif