]>
Commit | Line | Data |
---|---|---|
c49d1dd1 BP |
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 | * | |
5a8cc785 | 94 | * Use hash_bytes() instead, unless you're computing a hash function whose |
c49d1dd1 BP |
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 | { | |
db5a1019 | 99 | const uint32_t *p = p_; |
c49d1dd1 BP |
100 | uint32_t a, b, c; |
101 | ||
102 | a = b = c = 0xdeadbeef + n + basis; | |
103 | ||
104 | while (n >= 12) { | |
db5a1019 AW |
105 | a += get_unaligned_u32(p); |
106 | b += get_unaligned_u32(p + 1); | |
107 | c += get_unaligned_u32(p + 2); | |
c49d1dd1 BP |
108 | jhash_mix(&a, &b, &c); |
109 | n -= 12; | |
db5a1019 | 110 | p += 3; |
c49d1dd1 BP |
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 | } |