]>
Commit | Line | Data |
---|---|---|
c803536e SS |
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 | } |