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