opr: Convert jhash to use AFS types
[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 #endif