datapath-windows/ovsext/Jhash.c

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