clang-10: use AFS_FALLTHROUGH for case fallthrough
[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];                 AFS_FALLTHROUGH;
83       case 2 : b+=k[1];                 AFS_FALLTHROUGH;
84       case 1 : a+=k[0];
85         opr_jhash_final(a, b, c);       AFS_FALLTHROUGH;
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;  AFS_FALLTHROUGH;
151       case 11 : c += (afs_uint32) str[10]<<16;  AFS_FALLTHROUGH;
152       case 10 : c += (afs_uint32) str[9]<<8;    AFS_FALLTHROUGH;
153       case 9  : c += (afs_uint32) str[8];       AFS_FALLTHROUGH;
154       case 8  : b += (afs_uint32) str[7]<<24;   AFS_FALLTHROUGH;
155       case 7  : b += (afs_uint32) str[6]<<16;   AFS_FALLTHROUGH;
156       case 6  : b += (afs_uint32) str[5]<<8;    AFS_FALLTHROUGH;
157       case 5  : b += (afs_uint32) str[4];       AFS_FALLTHROUGH;
158       case 4  : a += (afs_uint32) str[3]<<24;   AFS_FALLTHROUGH;
159       case 3  : a += (afs_uint32) str[2]<<16;   AFS_FALLTHROUGH;
160       case 2  : a += (afs_uint32) str[1]<<8;    AFS_FALLTHROUGH;
161       case 1  : a += (afs_uint32) str[0];
162         opr_jhash_final(a, b, c);               AFS_FALLTHROUGH;
163       case 0:     /* case 0: nothing left to add */
164         break;
165     }
166
167     return c;
168 }
169
170 #endif