File: /usr/src/linux/fs/reiserfs/hashes.c
1
2 /*
3 * Keyed 32-bit hash function using TEA in a Davis-Meyer function
4 * H0 = Key
5 * Hi = E Mi(Hi-1) + Hi-1
6 *
7 * (see Applied Cryptography, 2nd edition, p448).
8 *
9 * Jeremy Fitzhardinge <jeremy@zip.com.au> 1998
10 *
11 * Jeremy has agreed to the contents of reiserfs/README. -Hans
12 * Yura's function is added (04/07/2000)
13 */
14
15 //
16 // keyed_hash
17 // yura_hash
18 // r5_hash
19 //
20
21 #include <asm/types.h>
22
23
24
25 #define DELTA 0x9E3779B9
26 #define FULLROUNDS 10 /* 32 is overkill, 16 is strong crypto */
27 #define PARTROUNDS 6 /* 6 gets complete mixing */
28
29 /* a, b, c, d - data; h0, h1 - accumulated hash */
30 #define TEACORE(rounds) \
31 do { \
32 u32 sum = 0; \
33 int n = rounds; \
34 u32 b0, b1; \
35 \
36 b0 = h0; \
37 b1 = h1; \
38 \
39 do \
40 { \
41 sum += DELTA; \
42 b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b); \
43 b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d); \
44 } while(--n); \
45 \
46 h0 += b0; \
47 h1 += b1; \
48 } while(0)
49
50
51 u32 keyed_hash(const char *msg, int len)
52 {
53 u32 k[] = { 0x9464a485, 0x542e1a94, 0x3e846bff, 0xb75bcfc3};
54
55 u32 h0 = k[0], h1 = k[1];
56 u32 a, b, c, d;
57 u32 pad;
58 int i;
59
60
61 // assert(len >= 0 && len < 256);
62
63 pad = (u32)len | ((u32)len << 8);
64 pad |= pad << 16;
65
66 while(len >= 16)
67 {
68 a = (u32)msg[ 0] |
69 (u32)msg[ 1] << 8 |
70 (u32)msg[ 2] << 16|
71 (u32)msg[ 3] << 24;
72 b = (u32)msg[ 4] |
73 (u32)msg[ 5] << 8 |
74 (u32)msg[ 6] << 16|
75 (u32)msg[ 7] << 24;
76 c = (u32)msg[ 8] |
77 (u32)msg[ 9] << 8 |
78 (u32)msg[10] << 16|
79 (u32)msg[11] << 24;
80 d = (u32)msg[12] |
81 (u32)msg[13] << 8 |
82 (u32)msg[14] << 16|
83 (u32)msg[15] << 24;
84
85 TEACORE(PARTROUNDS);
86
87 len -= 16;
88 msg += 16;
89 }
90
91 if (len >= 12)
92 {
93 //assert(len < 16);
94 if (len >= 16)
95 *(int *)0 = 0;
96
97 a = (u32)msg[ 0] |
98 (u32)msg[ 1] << 8 |
99 (u32)msg[ 2] << 16|
100 (u32)msg[ 3] << 24;
101 b = (u32)msg[ 4] |
102 (u32)msg[ 5] << 8 |
103 (u32)msg[ 6] << 16|
104 (u32)msg[ 7] << 24;
105 c = (u32)msg[ 8] |
106 (u32)msg[ 9] << 8 |
107 (u32)msg[10] << 16|
108 (u32)msg[11] << 24;
109
110 d = pad;
111 for(i = 12; i < len; i++)
112 {
113 d <<= 8;
114 d |= msg[i];
115 }
116 }
117 else if (len >= 8)
118 {
119 //assert(len < 12);
120 if (len >= 12)
121 *(int *)0 = 0;
122 a = (u32)msg[ 0] |
123 (u32)msg[ 1] << 8 |
124 (u32)msg[ 2] << 16|
125 (u32)msg[ 3] << 24;
126 b = (u32)msg[ 4] |
127 (u32)msg[ 5] << 8 |
128 (u32)msg[ 6] << 16|
129 (u32)msg[ 7] << 24;
130
131 c = d = pad;
132 for(i = 8; i < len; i++)
133 {
134 c <<= 8;
135 c |= msg[i];
136 }
137 }
138 else if (len >= 4)
139 {
140 //assert(len < 8);
141 if (len >= 8)
142 *(int *)0 = 0;
143 a = (u32)msg[ 0] |
144 (u32)msg[ 1] << 8 |
145 (u32)msg[ 2] << 16|
146 (u32)msg[ 3] << 24;
147
148 b = c = d = pad;
149 for(i = 4; i < len; i++)
150 {
151 b <<= 8;
152 b |= msg[i];
153 }
154 }
155 else
156 {
157 //assert(len < 4);
158 if (len >= 4)
159 *(int *)0 = 0;
160 a = b = c = d = pad;
161 for(i = 0; i < len; i++)
162 {
163 a <<= 8;
164 a |= msg[i];
165 }
166 }
167
168 TEACORE(FULLROUNDS);
169
170 /* return 0;*/
171 return h0^h1;
172 }
173
174 /* What follows in this file is copyright 2000 by Hans Reiser, and the
175 * licensing of what follows is governed by reiserfs/README */
176
177 u32 yura_hash (const char *msg, int len)
178 {
179 int j, pow;
180 u32 a, c;
181 int i;
182
183 for (pow=1,i=1; i < len; i++) pow = pow * 10;
184
185 if (len == 1)
186 a = msg[0]-48;
187 else
188 a = (msg[0] - 48) * pow;
189
190 for (i=1; i < len; i++) {
191 c = msg[i] - 48;
192 for (pow=1,j=i; j < len-1; j++) pow = pow * 10;
193 a = a + c * pow;
194 }
195
196 for (; i < 40; i++) {
197 c = '0' - 48;
198 for (pow=1,j=i; j < len-1; j++) pow = pow * 10;
199 a = a + c * pow;
200 }
201
202 for (; i < 256; i++) {
203 c = i;
204 for (pow=1,j=i; j < len-1; j++) pow = pow * 10;
205 a = a + c * pow;
206 }
207
208 a = a << 7;
209 return a;
210 }
211
212 u32 r5_hash (const char *msg, int len)
213 {
214 u32 a=0;
215 while(*msg) {
216 a += *msg << 4;
217 a += *msg >> 4;
218 a *= 11;
219 msg++;
220 }
221 return a;
222 }
223