d1107351fcec6fc155b50d1632edc80d5bb54aca
[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         /* fall through */
84       case 2 : b+=k[1];
85         /* fall through */
86       case 1 : a+=k[0];
87         opr_jhash_final(a, b, c);
88         /* fall through */
89       case 0:     /* case 0: nothing left to add */
90         break;
91     }
92
93     return c;
94 }
95
96 /* Simplified version of the above function to hash just one int */
97
98 static_inline afs_uint32
99 opr_jhash_int(afs_uint32 a, afs_uint32 initval) {
100    afs_uint32 b, c;
101
102    a += 0xdeadbeef + 4 + initval;
103    b = c = 0xdeadbeef + 4 + initval;
104    opr_jhash_final(a, b, c);
105
106    return c;
107 }
108
109 /* and one to do two ints */
110
111 static_inline afs_uint32
112 opr_jhash_int2(afs_uint32 a, afs_uint32 b, afs_uint32 initval)
113 {
114    afs_uint32 c;
115
116    a += 0xdeadbeef + 8 + initval;
117    b += 0xdeadbeef + 8 + initval;
118    c =  0xdeadbeef + 8 + initval;
119    opr_jhash_final(a, b, c);
120
121    return c;
122 }
123
124 static_inline afs_uint32
125 opr_jhash_opaque(const void *val, size_t length, afs_uint32 initval)
126 {
127     const unsigned char *str = (const unsigned char *) val;
128     afs_uint32 a,b,c;
129
130     /* Set up the internal state */
131     a = b = c = 0xdeadbeef + ((afs_uint32)length) + initval;
132
133     while (length > 12) {
134         a += (afs_uint32) str[3]<<24 |
135             (afs_uint32) str[2]<<16 |
136             (afs_uint32) str[1]<<8 |
137             (afs_uint32) str[0];
138         b += (afs_uint32) str[7]<<24 |
139             (afs_uint32) str[6]<<16 |
140             (afs_uint32) str[5]<<8 |
141             (afs_uint32) str[4];
142         c += (afs_uint32) str[11]<<24 |
143             (afs_uint32) str[10]<<16 |
144             (afs_uint32) str[9]<<8 |
145             (afs_uint32) str[8];
146         opr_jhash_mix(a, b, c);
147         length -= 12;
148         str += 12;
149     }
150
151     /* All the case statements fall through */
152     switch(length) {
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 */
167         break;
168     }
169
170     return c;
171 }
172
173 #endif