lib/hash.h

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