Commit | Line | Data |
---|---|---|
805e021f CE |
1 | /* |
2 | * Copyright (c) 2006 Bob Jenkins | |
3 | * Copyright (c) 2011 Your File System Inc. | |
4 | * | |
5 | * Redistribution and use in source and binary forms, with or without | |
6 | * modification, are permitted provided that the following conditions | |
7 | * are met: | |
8 | * 1. Redistributions of source code must retain the above copyright | |
9 | * notice, this list of conditions and the following disclaimer. | |
10 | * 2. Redistributions in binary form must reproduce the above copyright | |
11 | * notice, this list of conditions and the following disclaimer in the | |
12 | * documentation and/or other materials provided with the distribution. | |
13 | * | |
14 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR `AS IS'' AND ANY EXPRESS OR | |
15 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES | |
16 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. | |
17 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, | |
18 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT | |
19 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
20 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
21 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
22 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF | |
23 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
24 | */ | |
25 | ||
26 | /* This is an OPR version of Bob Jenkins' hash routines. His original copyright | |
27 | * declaration reads: | |
28 | * | |
29 | * lookup3.c, by Bob Jenkins, May 2006, Public Domain. | |
30 | * | |
31 | * You can use this free for any purpose. It's in the public domain. | |
32 | * It has no warranty. | |
33 | */ | |
34 | ||
35 | #ifndef OPENAFS_OPR_JHASH_H | |
36 | #define OPENAFS_OPR_JHASH_H 1 | |
37 | ||
38 | #define opr_jhash_size(n) ((afs_uint32)1<<(n)) | |
39 | #define opr_jhash_mask(n) (opr_jhash_size(n)-1) | |
40 | #define opr_jhash_rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) | |
41 | ||
42 | #define opr_jhash_mix(a,b,c) \ | |
43 | { \ | |
44 | a -= c; a ^= opr_jhash_rot(c, 4); c += b; \ | |
45 | b -= a; b ^= opr_jhash_rot(a, 6); a += c; \ | |
46 | c -= b; c ^= opr_jhash_rot(b, 8); b += a; \ | |
47 | a -= c; a ^= opr_jhash_rot(c,16); c += b; \ | |
48 | b -= a; b ^= opr_jhash_rot(a,19); a += c; \ | |
49 | c -= b; c ^= opr_jhash_rot(b, 4); b += a; \ | |
50 | } | |
51 | ||
52 | #define opr_jhash_final(a,b,c) \ | |
53 | { \ | |
54 | c ^= b; c -= opr_jhash_rot(b,14); \ | |
55 | a ^= c; a -= opr_jhash_rot(c,11); \ | |
56 | b ^= a; b -= opr_jhash_rot(a,25); \ | |
57 | c ^= b; c -= opr_jhash_rot(b,16); \ | |
58 | a ^= c; a -= opr_jhash_rot(c,4); \ | |
59 | b ^= a; b -= opr_jhash_rot(a,14); \ | |
60 | c ^= b; c -= opr_jhash_rot(b,24); \ | |
61 | } | |
62 | ||
63 | static_inline afs_uint32 | |
64 | opr_jhash(const afs_uint32 *k, size_t length, afs_uint32 initval) | |
65 | { | |
66 | afs_uint32 a,b,c; | |
67 | ||
68 | /* Set up the internal state */ | |
69 | a = b = c = 0xdeadbeef + (((afs_uint32)length)<<2) + initval; | |
70 | ||
71 | while (length > 3) { | |
72 | a += k[0]; | |
73 | b += k[1]; | |
74 | c += k[2]; | |
75 | opr_jhash_mix(a, b, c); | |
76 | length -= 3; | |
77 | k += 3; | |
78 | } | |
79 | ||
80 | /* All the case statements fall through */ | |
81 | switch(length) { | |
82 | case 3 : c+=k[2]; | |
83 | case 2 : b+=k[1]; | |
84 | case 1 : a+=k[0]; | |
85 | opr_jhash_final(a, b, c); | |
86 | case 0: /* case 0: nothing left to add */ | |
87 | break; | |
88 | } | |
89 | ||
90 | return c; | |
91 | } | |
92 | ||
93 | /* Simplified version of the above function to hash just one int */ | |
94 | ||
95 | static_inline afs_uint32 | |
96 | opr_jhash_int(afs_uint32 a, afs_uint32 initval) { | |
97 | afs_uint32 b, c; | |
98 | ||
99 | a += 0xdeadbeef + 4 + initval; | |
100 | b = c = 0xdeadbeef + 4 + initval; | |
101 | opr_jhash_final(a, b, c); | |
102 | ||
103 | return c; | |
104 | } | |
105 | ||
106 | /* and one to do two ints */ | |
107 | ||
108 | static_inline afs_uint32 | |
109 | opr_jhash_int2(afs_uint32 a, afs_uint32 b, afs_uint32 initval) | |
110 | { | |
111 | afs_uint32 c; | |
112 | ||
113 | a += 0xdeadbeef + 8 + initval; | |
114 | b += 0xdeadbeef + 8 + initval; | |
115 | c = 0xdeadbeef + 8 + initval; | |
116 | opr_jhash_final(a, b, c); | |
117 | ||
118 | return c; | |
119 | } | |
120 | ||
121 | static_inline afs_uint32 | |
122 | opr_jhash_opaque(const void *val, size_t length, afs_uint32 initval) | |
123 | { | |
124 | const unsigned char *str = (const unsigned char *) val; | |
125 | afs_uint32 a,b,c; | |
126 | ||
127 | /* Set up the internal state */ | |
128 | a = b = c = 0xdeadbeef + ((afs_uint32)length) + initval; | |
129 | ||
130 | while (length > 12) { | |
131 | a += (afs_uint32) str[3]<<24 | | |
132 | (afs_uint32) str[2]<<16 | | |
133 | (afs_uint32) str[1]<<8 | | |
134 | (afs_uint32) str[0]; | |
135 | b += (afs_uint32) str[7]<<24 | | |
136 | (afs_uint32) str[6]<<16 | | |
137 | (afs_uint32) str[5]<<8 | | |
138 | (afs_uint32) str[4]; | |
139 | c += (afs_uint32) str[11]<<24 | | |
140 | (afs_uint32) str[10]<<16 | | |
141 | (afs_uint32) str[9]<<8 | | |
142 | (afs_uint32) str[8]; | |
143 | opr_jhash_mix(a, b, c); | |
144 | length -= 12; | |
145 | str += 12; | |
146 | } | |
147 | ||
148 | /* All the case statements fall through */ | |
149 | switch(length) { | |
150 | case 12 : c += (afs_uint32) str[11]<<24; | |
151 | case 11 : c += (afs_uint32) str[10]<<16; | |
152 | case 10 : c += (afs_uint32) str[9]<<8; | |
153 | case 9 : c += (afs_uint32) str[8]; | |
154 | case 8 : b += (afs_uint32) str[7]<<24; | |
155 | case 7 : b += (afs_uint32) str[6]<<16; | |
156 | case 6 : b += (afs_uint32) str[5]<<8; | |
157 | case 5 : b += (afs_uint32) str[4]; | |
158 | case 4 : a += (afs_uint32) str[3]<<24; | |
159 | case 3 : a += (afs_uint32) str[2]<<16; | |
160 | case 2 : a += (afs_uint32) str[1]<<8; | |
161 | case 1 : a += (afs_uint32) str[0]; | |
162 | opr_jhash_final(a, b, c); | |
163 | case 0: /* case 0: nothing left to add */ | |
164 | break; | |
165 | } | |
166 | ||
167 | return c; | |
168 | } | |
169 | ||
170 | #endif |