lib/hash.h

   1 /*
   2  * Copyright (c) 2008, 2009, 2010, 2012, 2013 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 #ifndef HASH_H
  17 #define HASH_H 1
  18
  19 #include <stdbool.h>
  20 #include <stddef.h>
  21 #include <stdint.h>
  22 #include <string.h>
  23 #include "util.h"
  24
  25 #ifdef __cplusplus
  26 extern "C" {
  27 #endif
  28
  29 static inline uint32_t
  30 hash_rot(uint32_t x, int k)
  31 {
  32     return (x << k) | (x >> (32 - k));
  33 }
  34
  35 uint32_t hash_bytes(const void *, size_t n_bytes, uint32_t basis);
  36
  37 static inline uint32_t hash_int(uint32_t x, uint32_t basis);
  38 static inline uint32_t hash_2words(uint32_t, uint32_t);
  39 static inline uint32_t hash_uint64(const uint64_t);
  40 static inline uint32_t hash_uint64_basis(const uint64_t x,
  41                                          const uint32_t basis);
  42 uint32_t hash_3words(uint32_t, uint32_t, uint32_t);
  43
  44 static inline uint32_t hash_boolean(bool x, uint32_t basis);
  45 uint32_t hash_double(double, uint32_t basis);
  46
  47 static inline uint32_t hash_pointer(const void *, uint32_t basis);
  48 static inline uint32_t hash_string(const char *, uint32_t basis);
  49
  50 /* Murmurhash by Austin Appleby,
  51  * from http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp.
  52  *
  53  * The upstream license there says:
  54  *
  55  * // MurmurHash3 was written by Austin Appleby, and is placed in the public
  56  * // domain. The author hereby disclaims copyright to this source code.
  57  *
  58  * See hash_words() for sample usage. */
  59
  60 static inline uint32_t mhash_add__(uint32_t hash, uint32_t data)
  61 {
  62     data *= 0xcc9e2d51;
  63     data = hash_rot(data, 15);
  64     data *= 0x1b873593;
  65     return hash ^ data;
  66 }
  67
  68 static inline uint32_t mhash_add(uint32_t hash, uint32_t data)
  69 {
  70     hash = mhash_add__(hash, data);
  71     hash = hash_rot(hash, 13);
  72     return hash * 5 + 0xe6546b64;
  73 }
  74
  75 static inline uint32_t mhash_finish(uint32_t hash, uint32_t n_bytes)
  76 {
  77     hash ^= n_bytes;
  78     hash ^= hash >> 16;
  79     hash *= 0x85ebca6b;
  80     hash ^= hash >> 13;
  81     hash *= 0xc2b2ae35;
  82     hash ^= hash >> 16;
  83     return hash;
  84 }
  85
  86 #if !(defined(__SSE4_2__) && defined(__x86_64__))
  87 /* Mhash-based implemantation. */
  88
  89 static inline uint32_t hash_add(uint32_t hash, uint32_t data)
  90 {
  91     return mhash_add(hash, data);
  92 }
  93
  94 static inline uint32_t hash_finish(uint32_t hash, uint32_t final)
  95 {
  96     return mhash_finish(hash, final);
  97 }
  98
  99 /* Returns the hash of the 'n' 32-bit words at 'p', starting from 'basis'.
 100  * 'p' must be properly aligned.
 101  *
 102  * This is inlined for the compiler to have access to the 'n_words', which
 103  * in many cases is a constant. */
 104 static inline uint32_t
 105 hash_words_inline(const uint32_t p[], size_t n_words, uint32_t basis)
 106 {
 107     uint32_t hash;
 108     size_t i;
 109
 110     hash = basis;
 111     for (i = 0; i < n_words; i++) {
 112         hash = hash_add(hash, p[i]);
 113     }
 114     return hash_finish(hash, n_words * 4);
 115 }
 116
 117 static inline uint32_t
 118 hash_words64_inline(const uint64_t p[], size_t n_words, uint64_t basis)
 119 {
 120     return hash_words_inline((uint32_t *)p, n_words * 2,
 121                              (uint32_t)basis ^ basis >> 32);
 122 }
 123
 124 static inline uint32_t hash_pointer(const void *p, uint32_t basis)
 125 {
 126     /* Often pointers are hashed simply by casting to integer type, but that
 127      * has pitfalls since the lower bits of a pointer are often all 0 for
 128      * alignment reasons.  It's hard to guess where the entropy really is, so
 129      * we give up here and just use a high-quality hash function.
 130      *
 131      * The double cast suppresses a warning on 64-bit systems about casting to
 132      * an integer to different size.  That's OK in this case, since most of the
 133      * entropy in the pointer is almost certainly in the lower 32 bits. */
 134     return hash_int((uint32_t) (uintptr_t) p, basis);
 135 }
 136
 137 static inline uint32_t hash_2words(uint32_t x, uint32_t y)
 138 {
 139     return hash_finish(hash_add(hash_add(x, 0), y), 8);
 140 }
 141
 142 static inline uint32_t hash_uint64(const uint64_t x)
 143 {
 144     return hash_2words((uint32_t)(x >> 32), (uint32_t)x);
 145 }
 146
 147 static inline uint32_t hash_uint64_basis(const uint64_t x,
 148                                          const uint32_t basis)
 149 {
 150     return hash_3words((uint32_t)(x >> 32), (uint32_t)x, basis);
 151 }
 152
 153 #else /* __SSE4_2__ && __x86_64__ */
 154 #include <smmintrin.h>
 155
 156 static inline uint32_t hash_add(uint32_t hash, uint32_t data)
 157 {
 158     return _mm_crc32_u32(hash, data);
 159 }
 160
 161 static inline uint32_t hash_finish(uint64_t hash, uint64_t final)
 162 {
 163     /* The finishing multiplier 0x805204f3 has been experimentally
 164      * derived to pass the testsuite hash tests. */
 165     hash = _mm_crc32_u64(hash, final) * 0x805204f3;
 166     return hash ^ (uint32_t)hash >> 16; /* Increase entropy in LSBs. */
 167 }
 168
 169 /* Returns the hash of the 'n' 32-bit words at 'p_', starting from 'basis'.
 170  * We access 'p_' as a uint64_t pointer, which is fine for __SSE_4_2__.
 171  *
 172  * This is inlined for the compiler to have access to the 'n_words', which
 173  * in many cases is a constant. */
 174 static inline uint32_t
 175 hash_words_inline(const uint32_t p_[], size_t n_words, uint32_t basis)
 176 {
 177     const uint64_t *p = (const void *)p_;
 178     uint64_t hash1 = basis;
 179     uint64_t hash2 = 0;
 180     uint64_t hash3 = n_words;
 181     const uint32_t *endp = (const uint32_t *)p + n_words;
 182     const uint64_t *limit = p + n_words / 2 - 3;
 183
 184     while (p <= limit) {
 185         hash1 = _mm_crc32_u64(hash1, p[0]);
 186         hash2 = _mm_crc32_u64(hash2, p[1]);
 187         hash3 = _mm_crc32_u64(hash3, p[2]);
 188         p += 3;
 189     }
 190     switch (endp - (const uint32_t *)p) {
 191     case 1:
 192         hash1 = _mm_crc32_u32(hash1, *(const uint32_t *)&p[0]);
 193         break;
 194     case 2:
 195         hash1 = _mm_crc32_u64(hash1, p[0]);
 196         break;
 197     case 3:
 198         hash1 = _mm_crc32_u64(hash1, p[0]);
 199         hash2 = _mm_crc32_u32(hash2, *(const uint32_t *)&p[1]);
 200         break;
 201     case 4:
 202         hash1 = _mm_crc32_u64(hash1, p[0]);
 203         hash2 = _mm_crc32_u64(hash2, p[1]);
 204         break;
 205     case 5:
 206         hash1 = _mm_crc32_u64(hash1, p[0]);
 207         hash2 = _mm_crc32_u64(hash2, p[1]);
 208         hash3 = _mm_crc32_u32(hash3, *(const uint32_t *)&p[2]);
 209         break;
 210     }
 211     return hash_finish(hash1, hash2 << 32 | hash3);
 212 }
 213
 214 /* A simpler version for 64-bit data.
 215  * 'n_words' is the count of 64-bit words, basis is 64 bits. */
 216 static inline uint32_t
 217 hash_words64_inline(const uint64_t p[], size_t n_words, uint64_t basis)
 218 {
 219     uint64_t hash1 = (uint32_t)basis;
 220     uint64_t hash2 = basis >> 32;
 221     uint64_t hash3 = n_words;
 222     const uint64_t *endp = p + n_words;
 223     const uint64_t *limit = endp - 3;
 224
 225     while (p <= limit) {
 226         hash1 = _mm_crc32_u64(hash1, p[0]);
 227         hash2 = _mm_crc32_u64(hash2, p[1]);
 228         hash3 = _mm_crc32_u64(hash3, p[2]);
 229         p += 3;
 230     }
 231     switch (endp - p) {
 232     case 1:
 233         hash1 = _mm_crc32_u64(hash1, p[0]);
 234         break;
 235     case 2:
 236         hash1 = _mm_crc32_u64(hash1, p[0]);
 237         hash2 = _mm_crc32_u64(hash2, p[1]);
 238         break;
 239     }
 240     return hash_finish(hash1, hash2 << 32 | hash3);
 241 }
 242
 243 static inline uint32_t hash_uint64_basis(const uint64_t x,
 244                                          const uint32_t basis)
 245 {
 246     /* '23' chosen to mix bits enough for the test-hash to pass. */
 247     return hash_finish(_mm_crc32_u64(basis, x), 23);
 248 }
 249
 250 static inline uint32_t hash_uint64(const uint64_t x)
 251 {
 252     return hash_uint64_basis(x, 0);
 253 }
 254
 255 static inline uint32_t hash_2words(uint32_t x, uint32_t y)
 256 {
 257     return hash_uint64((uint64_t)y << 32 | x);
 258 }
 259
 260 static inline uint32_t hash_pointer(const void *p, uint32_t basis)
 261 {
 262     return hash_uint64_basis((uint64_t) (uintptr_t) p, basis);
 263 }
 264 #endif
 265
 266 uint32_t hash_words__(const uint32_t p[], size_t n_words, uint32_t basis);
 267 uint32_t hash_words64__(const uint64_t p[], size_t n_words, uint64_t basis);
 268
 269 /* Inline the larger hash functions only when 'n_words' is known to be
 270  * compile-time constant. */
 271 #if __GNUC__ >= 4
 272 static inline uint32_t
 273 hash_words(const uint32_t p[], size_t n_words, uint32_t basis)
 274 {
 275     if (__builtin_constant_p(n_words)) {
 276         return hash_words_inline(p, n_words, basis);
 277     } else {
 278         return hash_words__(p, n_words, basis);
 279     }
 280 }
 281
 282 static inline uint32_t
 283 hash_words64(const uint64_t p[], size_t n_words, uint64_t basis)
 284 {
 285     if (__builtin_constant_p(n_words)) {
 286         return hash_words64_inline(p, n_words, basis);
 287     } else {
 288         return hash_words64__(p, n_words, basis);
 289     }
 290 }
 291
 292 #else
 293
 294 static inline uint32_t
 295 hash_words(const uint32_t p[], size_t n_words, uint32_t basis)
 296 {
 297     return hash_words__(p, n_words, basis);
 298 }
 299
 300 static inline uint32_t
 301 hash_words64(const uint64_t p[], size_t n_words, uint64_t basis)
 302 {
 303     return hash_words64__(p, n_words, basis);
 304 }
 305 #endif
 306
 307 static inline uint32_t hash_string(const char *s, uint32_t basis)
 308 {
 309     return hash_bytes(s, strlen(s), basis);
 310 }
 311
 312 static inline uint32_t hash_int(uint32_t x, uint32_t basis)
 313 {
 314     return hash_2words(x, basis);
 315 }
 316
 317 /* An attempt at a useful 1-bit hash function.  Has not been analyzed for
 318  * quality. */
 319 static inline uint32_t hash_boolean(bool x, uint32_t basis)
 320 {
 321     const uint32_t P0 = 0xc2b73583;   /* This is hash_int(1, 0). */
 322     const uint32_t P1 = 0xe90f1258;   /* This is hash_int(2, 0). */
 323     return (x ? P0 : P1) ^ hash_rot(basis, 1);
 324 }
 325
 326 #ifdef __cplusplus
 327 }
 328 #endif
 329
 330 #endif /* hash.h */