2 * Copyright (c) 2006 Bob Jenkins
3 * Copyright (c) 2011 Your File System Inc.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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.
26 /* This is an OPR version of Bob Jenkins' hash routines. His original copyright
29 * lookup3.c, by Bob Jenkins, May 2006, Public Domain.
31 * You can use this free for any purpose. It's in the public domain.
35 #ifndef OPENAFS_OPR_JHASH_H
36 #define OPENAFS_OPR_JHASH_H 1
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))))
42 #define opr_jhash_mix(a,b,c) \
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; \
52 #define opr_jhash_final(a,b,c) \
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); \
63 static_inline afs_uint32
64 opr_jhash(const afs_uint32 *k, size_t length, afs_uint32 initval)
68 /* Set up the internal state */
69 a = b = c = 0xdeadbeef + (((afs_uint32)length)<<2) + initval;
75 opr_jhash_mix(a, b, c);
80 /* All the case statements fall through */
87 opr_jhash_final(a, b, c);
89 case 0: /* case 0: nothing left to add */
96 /* Simplified version of the above function to hash just one int */
98 static_inline afs_uint32
99 opr_jhash_int(afs_uint32 a, afs_uint32 initval) {
102 a += 0xdeadbeef + 4 + initval;
103 b = c = 0xdeadbeef + 4 + initval;
104 opr_jhash_final(a, b, c);
109 /* and one to do two ints */
111 static_inline afs_uint32
112 opr_jhash_int2(afs_uint32 a, afs_uint32 b, afs_uint32 initval)
116 a += 0xdeadbeef + 8 + initval;
117 b += 0xdeadbeef + 8 + initval;
118 c = 0xdeadbeef + 8 + initval;
119 opr_jhash_final(a, b, c);
124 static_inline afs_uint32
125 opr_jhash_opaque(const void *val, size_t length, afs_uint32 initval)
127 const unsigned char *str = (const unsigned char *) val;
130 /* Set up the internal state */
131 a = b = c = 0xdeadbeef + ((afs_uint32)length) + initval;
133 while (length > 12) {
134 a += (afs_uint32) str[3]<<24 |
135 (afs_uint32) str[2]<<16 |
136 (afs_uint32) str[1]<<8 |
138 b += (afs_uint32) str[7]<<24 |
139 (afs_uint32) str[6]<<16 |
140 (afs_uint32) str[5]<<8 |
142 c += (afs_uint32) str[11]<<24 |
143 (afs_uint32) str[10]<<16 |
144 (afs_uint32) str[9]<<8 |
146 opr_jhash_mix(a, b, c);
151 /* All the case statements fall through */
153 case 12 : c += (afs_uint32) str[11]<<24; /* fall through */
154 case 11 : c += (afs_uint32) str[10]<<16; /* fall through */
155 case 10 : c += (afs_uint32) str[9]<<8; /* fall through */
156 case 9 : c += (afs_uint32) str[8]; /* fall through */
157 case 8 : b += (afs_uint32) str[7]<<24; /* fall through */
158 case 7 : b += (afs_uint32) str[6]<<16; /* fall through */
159 case 6 : b += (afs_uint32) str[5]<<8; /* fall through */
160 case 5 : b += (afs_uint32) str[4]; /* fall through */
161 case 4 : a += (afs_uint32) str[3]<<24; /* fall through */
162 case 3 : a += (afs_uint32) str[2]<<16; /* fall through */
163 case 2 : a += (afs_uint32) str[1]<<8; /* fall through */
164 case 1 : a += (afs_uint32) str[0];
165 opr_jhash_final(a, b, c); /* fall through */
166 case 0: /* case 0: nothing left to add */