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