lib/jhash.c

   1 /*
   2  * Copyright (c) 2008, 2009, 2010, 2012 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
  17 #include <config.h>
  18 #include "jhash.h"
  19 #include <string.h>
  20 #include "unaligned.h"
  21
  22 /* This is the public domain lookup3 hash by Bob Jenkins from
  23  * http://burtleburtle.net/bob/c/lookup3.c, modified for style. */
  24
  25 static inline uint32_t
  26 jhash_rot(uint32_t x, int k)
  27 {
  28     return (x << k) | (x >> (32 - k));
  29 }
  30
  31 static inline void
  32 jhash_mix(uint32_t *a, uint32_t *b, uint32_t *c)
  33 {
  34       *a -= *c; *a ^= jhash_rot(*c,  4); *c += *b;
  35       *b -= *a; *b ^= jhash_rot(*a,  6); *a += *c;
  36       *c -= *b; *c ^= jhash_rot(*b,  8); *b += *a;
  37       *a -= *c; *a ^= jhash_rot(*c, 16); *c += *b;
  38       *b -= *a; *b ^= jhash_rot(*a, 19); *a += *c;
  39       *c -= *b; *c ^= jhash_rot(*b,  4); *b += *a;
  40 }
  41
  42 static inline void
  43 jhash_final(uint32_t *a, uint32_t *b, uint32_t *c)
  44 {
  45       *c ^= *b; *c -= jhash_rot(*b, 14);
  46       *a ^= *c; *a -= jhash_rot(*c, 11);
  47       *b ^= *a; *b -= jhash_rot(*a, 25);
  48       *c ^= *b; *c -= jhash_rot(*b, 16);
  49       *a ^= *c; *a -= jhash_rot(*c,  4);
  50       *b ^= *a; *b -= jhash_rot(*a, 14);
  51       *c ^= *b; *c -= jhash_rot(*b, 24);
  52 }
  53
  54 /* Returns the Jenkins hash of the 'n' 32-bit words at 'p', starting from
  55  * 'basis'.  'p' must be properly aligned.
  56  *
  57  * Use hash_words() instead, unless you're computing a hash function whose
  58  * value is exposed "on the wire" so we don't want to change it. */
  59 uint32_t
  60 jhash_words(const uint32_t *p, size_t n, uint32_t basis)
  61 {
  62     uint32_t a, b, c;
  63
  64     a = b = c = 0xdeadbeef + (((uint32_t) n) << 2) + basis;
  65
  66     while (n > 3) {
  67         a += p[0];
  68         b += p[1];
  69         c += p[2];
  70         jhash_mix(&a, &b, &c);
  71         n -= 3;
  72         p += 3;
  73     }
  74
  75     switch (n) {
  76     case 3:
  77         c += p[2];
  78         /* fall through */
  79     case 2:
  80         b += p[1];
  81         /* fall through */
  82     case 1:
  83         a += p[0];
  84         jhash_final(&a, &b, &c);
  85         /* fall through */
  86     case 0:
  87         break;
  88     }
  89     return c;
  90 }
  91
  92 /* Returns the Jenkins hash of the 'n' bytes at 'p', starting from 'basis'.
  93  *
  94  * Use hash_bytes() instead, unless you're computing a hash function whose
  95  * value is exposed "on the wire" so we don't want to change it. */
  96 uint32_t
  97 jhash_bytes(const void *p_, size_t n, uint32_t basis)
  98 {
  99     const uint32_t *p = p_;
 100     uint32_t a, b, c;
 101
 102     a = b = c = 0xdeadbeef + n + basis;
 103
 104     while (n >= 12) {
 105         a += get_unaligned_u32(p);
 106         b += get_unaligned_u32(p + 1);
 107         c += get_unaligned_u32(p + 2);
 108         jhash_mix(&a, &b, &c);
 109         n -= 12;
 110         p += 3;
 111     }
 112
 113     if (n) {
 114         uint32_t tmp[3];
 115
 116         tmp[0] = tmp[1] = tmp[2] = 0;
 117         memcpy(tmp, p, n);
 118         a += tmp[0];
 119         b += tmp[1];
 120         c += tmp[2];
 121         jhash_final(&a, &b, &c);
 122     }
 123
 124     return c;
 125 }