lib/hash.h

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