lib/hash.c

   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 #include <config.h>
  17 #include "hash.h"
  18 #include <string.h>
  19 #include "unaligned.h"
  20
  21 /* Returns the hash of 'a', 'b', and 'c'. */
  22 uint32_t
  23 hash_3words(uint32_t a, uint32_t b, uint32_t c)
  24 {
  25     return hash_finish(hash_add(hash_add(hash_add(a, 0), b), c), 12);
  26 }
  27
  28 /* Returns the hash of the 'n' bytes at 'p', starting from 'basis'. */
  29 uint32_t
  30 hash_bytes(const void *p_, size_t n, uint32_t basis)
  31 {
  32     const uint32_t *p = p_;
  33     size_t orig_n = n;
  34     uint32_t hash;
  35
  36     hash = basis;
  37     while (n >= 4) {
  38         hash = hash_add(hash, get_unaligned_u32(p));
  39         n -= 4;
  40         p += 1;
  41     }
  42
  43     if (n) {
  44         uint32_t tmp = 0;
  45
  46         memcpy(&tmp, p, n);
  47         hash = hash_add(hash, tmp);
  48     }
  49
  50     return hash_finish(hash, orig_n);
  51 }
  52
  53 uint32_t
  54 hash_double(double x, uint32_t basis)
  55 {
  56     uint32_t value[2];
  57     BUILD_ASSERT_DECL(sizeof x == sizeof value);
  58
  59     memcpy(value, &x, sizeof value);
  60     return hash_3words(value[0], value[1], basis);
  61 }
  62
  63 uint32_t
  64 hash_words__(const uint32_t p[], size_t n_words, uint32_t basis)
  65 {
  66     return hash_words_inline(p, n_words, basis);
  67 }
  68
  69 uint32_t
  70 hash_words64__(const uint64_t p[], size_t n_words, uint32_t basis)
  71 {
  72     return hash_words64_inline(p, n_words, basis);
  73 }
  74
  75 #if !(defined(__x86_64__))
  76 void
  77 hash_bytes128(const void *p_, size_t len, uint32_t basis, ovs_u128 *out)
  78 {
  79     const uint32_t c1 = 0x239b961b;
  80     const uint32_t c2 = 0xab0e9789;
  81     const uint32_t c3 = 0x38b34ae5;
  82     const uint32_t c4 = 0xa1e38b93;
  83     const uint8_t *tail, *data = (const uint8_t *)p_;
  84     const uint32_t *blocks = (const uint32_t *)p_;
  85     const int nblocks = len / 16;
  86     uint32_t h1 = basis;
  87     uint32_t h2 = basis;
  88     uint32_t h3 = basis;
  89     uint32_t h4 = basis;
  90     uint32_t k1, k2, k3, k4;
  91
  92     /* Body */
  93     for (int i = 0; i < nblocks; i++) {
  94         uint32_t k1 = get_unaligned_u32(&blocks[i * 4 + 0]);
  95         uint32_t k2 = get_unaligned_u32(&blocks[i * 4 + 1]);
  96         uint32_t k3 = get_unaligned_u32(&blocks[i * 4 + 2]);
  97         uint32_t k4 = get_unaligned_u32(&blocks[i * 4 + 3]);
  98
  99         k1 *= c1;
 100         k1 = hash_rot(k1, 15);
 101         k1 *= c2;
 102         h1 ^= k1;
 103
 104         h1 = hash_rot(h1, 19);
 105         h1 += h2;
 106         h1 = h1 * 5 + 0x561ccd1b;
 107
 108         k2 *= c2;
 109         k2 = hash_rot(k2, 16);
 110         k2 *= c3;
 111         h2 ^= k2;
 112
 113         h2 = hash_rot(h2, 17);
 114         h2 += h3;
 115         h2 = h2 * 5 + 0x0bcaa747;
 116
 117         k3 *= c3;
 118         k3 = hash_rot(k3, 17);
 119         k3 *= c4;
 120         h3 ^= k3;
 121
 122         h3 = hash_rot(h3, 15);
 123         h3 += h4;
 124         h3 = h3 * 5 + 0x96cd1c35;
 125
 126         k4 *= c4;
 127         k4 = hash_rot(k4, 18);
 128         k4 *= c1;
 129         h4 ^= k4;
 130
 131         h4 = hash_rot(h4, 13);
 132         h4 += h1;
 133         h4 = h4 * 5 + 0x32ac3b17;
 134     }
 135
 136     /* Tail */
 137     k1 = k2 = k3 = k4 = 0;
 138     tail = data + nblocks * 16;
 139     switch (len & 15) {
 140     case 15:
 141         k4 ^= tail[14] << 16;
 142     case 14:
 143         k4 ^= tail[13] << 8;
 144     case 13:
 145         k4 ^= tail[12] << 0;
 146         k4 *= c4;
 147         k4 = hash_rot(k4, 18);
 148         k4 *= c1;
 149         h4 ^= k4;
 150
 151     case 12:
 152         k3 ^= tail[11] << 24;
 153     case 11:
 154         k3 ^= tail[10] << 16;
 155     case 10:
 156         k3 ^= tail[9] << 8;
 157     case 9:
 158         k3 ^= tail[8] << 0;
 159         k3 *= c3;
 160         k3 = hash_rot(k3, 17);
 161         k3 *= c4;
 162         h3 ^= k3;
 163
 164     case 8:
 165         k2 ^= tail[7] << 24;
 166     case 7:
 167         k2 ^= tail[6] << 16;
 168     case 6:
 169         k2 ^= tail[5] << 8;
 170     case 5:
 171         k2 ^= tail[4] << 0;
 172         k2 *= c2;
 173         k2 = hash_rot(k2, 16);
 174         k2 *= c3;
 175         h2 ^= k2;
 176
 177     case 4:
 178         k1 ^= tail[3] << 24;
 179     case 3:
 180         k1 ^= tail[2] << 16;
 181     case 2:
 182         k1 ^= tail[1] << 8;
 183     case 1:
 184         k1 ^= tail[0] << 0;
 185         k1 *= c1;
 186         k1 = hash_rot(k1, 15);
 187         k1 *= c2;
 188         h1 ^= k1;
 189     };
 190
 191     /* Finalization */
 192     h1 ^= len;
 193     h2 ^= len;
 194     h3 ^= len;
 195     h4 ^= len;
 196
 197     h1 += h2;
 198     h1 += h3;
 199     h1 += h4;
 200     h2 += h1;
 201     h3 += h1;
 202     h4 += h1;
 203
 204     h1 = mhash_finish(h1);
 205     h2 = mhash_finish(h2);
 206     h3 = mhash_finish(h3);
 207     h4 = mhash_finish(h4);
 208
 209     h1 += h2;
 210     h1 += h3;
 211     h1 += h4;
 212     h2 += h1;
 213     h3 += h1;
 214     h4 += h1;
 215
 216     out->u32[0] = h1;
 217     out->u32[1] = h2;
 218     out->u32[2] = h3;
 219     out->u32[3] = h4;
 220 }
 221
 222 #else /* __x86_64__ */
 223
 224 static inline uint64_t
 225 hash_rot64(uint64_t x, int8_t r)
 226 {
 227     return (x << r) | (x >> (64 - r));
 228 }
 229
 230 static inline uint64_t
 231 fmix64(uint64_t k)
 232 {
 233     k ^= k >> 33;
 234     k *= 0xff51afd7ed558ccdULL;
 235     k ^= k >> 33;
 236     k *= 0xc4ceb9fe1a85ec53ULL;
 237     k ^= k >> 33;
 238
 239     return k;
 240 }
 241
 242 void
 243 hash_bytes128(const void *p_, size_t len, uint32_t basis, ovs_u128 *out)
 244 {
 245     const uint64_t c1 = 0x87c37b91114253d5ULL;
 246     const uint64_t c2 = 0x4cf5ad432745937fULL;
 247     const uint8_t *tail, *data = (const uint8_t *)p_;
 248     const uint64_t *blocks = (const uint64_t *)p_;
 249     const int nblocks = len / 16;
 250     uint64_t h1 = basis;
 251     uint64_t h2 = basis;
 252     uint64_t k1, k2;
 253
 254     /* Body */
 255     for (int i = 0; i < nblocks; i++) {
 256         k1 = get_unaligned_u64(&blocks[i * 2 + 0]);
 257         k2 = get_unaligned_u64(&blocks[i * 2 + 1]);
 258
 259         k1 *= c1;
 260         k1 = hash_rot64(k1, 31);
 261         k1 *= c2;
 262         h1 ^= k1;
 263
 264         h1 = hash_rot64(h1, 27);
 265         h1 += h2;
 266         h1 = h1 * 5 + 0x52dce729;
 267
 268         k2 *= c2;
 269         k2 = hash_rot64(k2, 33);
 270         k2 *= c1;
 271         h2 ^= k2;
 272
 273         h2 = hash_rot64(h2, 31);
 274         h2 += h1;
 275         h2 = h2 * 5 + 0x38495ab5;
 276     }
 277
 278     /* Tail */
 279     k1 = 0;
 280     k2 = 0;
 281     tail = data + nblocks * 16;
 282     switch (len & 15) {
 283     case 15:
 284         k2 ^= ((uint64_t) tail[14]) << 48;
 285     case 14:
 286         k2 ^= ((uint64_t) tail[13]) << 40;
 287     case 13:
 288         k2 ^= ((uint64_t) tail[12]) << 32;
 289     case 12:
 290         k2 ^= ((uint64_t) tail[11]) << 24;
 291     case 11:
 292         k2 ^= ((uint64_t) tail[10]) << 16;
 293     case 10:
 294         k2 ^= ((uint64_t) tail[9]) << 8;
 295     case 9:
 296         k2 ^= ((uint64_t) tail[8]) << 0;
 297         k2 *= c2;
 298         k2 = hash_rot64(k2, 33);
 299         k2 *= c1;
 300         h2 ^= k2;
 301
 302     case 8:
 303         k1 ^= ((uint64_t) tail[7]) << 56;
 304     case 7:
 305         k1 ^= ((uint64_t) tail[6]) << 48;
 306     case 6:
 307         k1 ^= ((uint64_t) tail[5]) << 40;
 308     case 5:
 309         k1 ^= ((uint64_t) tail[4]) << 32;
 310     case 4:
 311         k1 ^= ((uint64_t) tail[3]) << 24;
 312     case 3:
 313         k1 ^= ((uint64_t) tail[2]) << 16;
 314     case 2:
 315         k1 ^= ((uint64_t) tail[1]) << 8;
 316     case 1:
 317         k1 ^= ((uint64_t) tail[0]) << 0;
 318         k1 *= c1;
 319         k1 = hash_rot64(k1, 31);
 320         k1 *= c2;
 321         h1 ^= k1;
 322     };
 323
 324     /* Finalization */
 325     h1 ^= len;
 326     h2 ^= len;
 327     h1 += h2;
 328     h2 += h1;
 329     h1 = fmix64(h1);
 330     h2 = fmix64(h2);
 331     h1 += h2;
 332     h2 += h1;
 333
 334     out->u64.lo = h1;
 335     out->u64.hi = h2;
 336 }
 337 #endif /* __x86_64__ */