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