opr: Add opr_jhash_int2 function
[openafs.git] / src / opr / jhash.h
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     afs_uint32 k[3];
127
128     /* Set up the internal state */
129     a = b = c = 0xdeadbeef + (((afs_uint32)length)<<2) + initval;
130
131     while (length > 12) {
132         memcpy(&k, str, 12);
133         a += k[0];
134         b += k[1];
135         c += k[2];
136         opr_jhash_mix(a, b, c);
137         length -= 12;
138         str += 12;
139     }
140
141     /* All the case statements fall through */
142     switch(length) {
143       case 12 : c += (afs_uint32) str[11]<<24;
144       case 11 : c += (afs_uint32) str[10]<<16;
145       case 10 : c += (afs_uint32) str[9]<<8;
146       case 9  : c += (afs_uint32) str[8];
147       case 8  : b += (afs_uint32) str[7]<<24;
148       case 7  : b += (afs_uint32) str[6]<<16;
149       case 6  : b += (afs_uint32) str[5]<<8;
150       case 5  : b += (afs_uint32) str[4];
151       case 4  : a += (afs_uint32) str[3]<<24;
152       case 3  : a += (afs_uint32) str[2]<<16;
153       case 2  : a += (afs_uint32) str[1]<<8;
154       case 1  : a += (afs_uint32) str[0];
155         opr_jhash_final(a, b, c);
156       case 0:     /* case 0: nothing left to add */
157         break;
158     }
159
160     return c;
161 }
162
163 #endif