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 // Modified by Ingo Weinhold (bonefish), Jan. 2003:
16 // Fixed r5_hash() and added key_offset_for_name().
17
18 //
19 // keyed_hash
20 // yura_hash
21 // r5_hash
22 //
23
24 #include "hashes.h"
25 #include "reiserfs.h"
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 uint32 sum = 0; \
35 int n = rounds; \
36 uint32 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 uint32 keyed_hash(const signed char *msg, int len)
54 {
55 uint32 k[] = { 0x9464a485, 0x542e1a94, 0x3e846bff, 0xb75bcfc3};
56
57 uint32 h0 = k[0], h1 = k[1];
58 uint32 a, b, c, d;
59 uint32 pad;
60 int i;
61
62
63 // assert(len >= 0 && len < 256);
64
65 pad = (uint32)len | ((uint32)len << 8);
66 pad |= pad << 16;
67
68 while(len >= 16)
69 {
70 a = (uint32)msg[ 0] |
71 (uint32)msg[ 1] << 8 |
72 (uint32)msg[ 2] << 16|
73 (uint32)msg[ 3] << 24;
74 b = (uint32)msg[ 4] |
75 (uint32)msg[ 5] << 8 |
76 (uint32)msg[ 6] << 16|
77 (uint32)msg[ 7] << 24;
78 c = (uint32)msg[ 8] |
79 (uint32)msg[ 9] << 8 |
80 (uint32)msg[10] << 16|
81 (uint32)msg[11] << 24;
82 d = (uint32)msg[12] |
83 (uint32)msg[13] << 8 |
84 (uint32)msg[14] << 16|
85 (uint32)msg[15] << 24;
86
87 TEACORE(PARTROUNDS);
88
89 len -= 16;
90 msg += 16;
91 }
92
93 if (len >= 12)
94 {
95 //assert(len < 16);
96 if (len >= 16)
97 *(int *)0 = 0;
98
99 a = (uint32)msg[ 0] |
100 (uint32)msg[ 1] << 8 |
101 (uint32)msg[ 2] << 16|
102 (uint32)msg[ 3] << 24;
103 b = (uint32)msg[ 4] |
104 (uint32)msg[ 5] << 8 |
105 (uint32)msg[ 6] << 16|
106 (uint32)msg[ 7] << 24;
107 c = (uint32)msg[ 8] |
108 (uint32)msg[ 9] << 8 |
109 (uint32)msg[10] << 16|
110 (uint32)msg[11] << 24;
111
112 d = pad;
113 for(i = 12; i < len; i++)
114 {
115 d <<= 8;
116 d |= msg[i];
117 }
118 }
119 else if (len >= 8)
120 {
121 //assert(len < 12);
122 if (len >= 12)
123 *(int *)0 = 0;
124 a = (uint32)msg[ 0] |
125 (uint32)msg[ 1] << 8 |
126 (uint32)msg[ 2] << 16|
127 (uint32)msg[ 3] << 24;
128 b = (uint32)msg[ 4] |
129 (uint32)msg[ 5] << 8 |
130 (uint32)msg[ 6] << 16|
131 (uint32)msg[ 7] << 24;
132
133 c = d = pad;
134 for(i = 8; i < len; i++)
135 {
136 c <<= 8;
137 c |= msg[i];
138 }
139 }
140 else if (len >= 4)
141 {
142 //assert(len < 8);
143 if (len >= 8)
144 *(int *)0 = 0;
145 a = (uint32)msg[ 0] |
146 (uint32)msg[ 1] << 8 |
147 (uint32)msg[ 2] << 16|
148 (uint32)msg[ 3] << 24;
149
150 b = c = d = pad;
151 for(i = 4; i < len; i++)
152 {
153 b <<= 8;
154 b |= msg[i];
155 }
156 }
157 else
158 {
159 //assert(len < 4);
160 if (len >= 4)
161 *(int *)0 = 0;
162 a = b = c = d = pad;
163 for(i = 0; i < len; i++)
164 {
165 a <<= 8;
166 a |= msg[i];
167 }
168 }
169
170 TEACORE(FULLROUNDS);
171
172 /* return 0;*/
173 return h0^h1;
174 }
175
176 /* What follows in this file is copyright 2000 by Hans Reiser, and the
177 * licensing of what follows is governed by reiserfs/README */
178
yura_hash(const signed char * msg,int len)179 uint32 yura_hash (const signed char *msg, int len)
180 {
181 int j, pow;
182 uint32 a, c;
183 int i;
184
185 for (pow=1,i=1; i < len; i++) pow = pow * 10;
186
187 if (len == 1)
188 a = msg[0]-48;
189 else
190 a = (msg[0] - 48) * pow;
191
192 for (i=1; i < len; i++) {
193 c = msg[i] - 48;
194 for (pow=1,j=i; j < len-1; j++) pow = pow * 10;
195 a = a + c * pow;
196 }
197
198 for (; i < 40; i++) {
199 c = '0' - 48;
200 for (pow=1,j=i; j < len-1; j++) pow = pow * 10;
201 a = a + c * pow;
202 }
203
204 for (; i < 256; i++) {
205 c = i;
206 for (pow=1,j=i; j < len-1; j++) pow = pow * 10;
207 a = a + c * pow;
208 }
209
210 a = a << 7;
211 return a;
212 }
213
r5_hash(const signed char * msg,int len)214 uint32 r5_hash (const signed char *msg, int len)
215 {
216 uint32 a=0;
217 // bonefish: len was ignored
218 // while(*msg) {
219 while(len--) {
220 a += *msg << 4;
221 a += *msg >> 4;
222 a *= 11;
223 msg++;
224 }
225 return a;
226 }
227
228
229 // bonefish:
230 // from reiserfs_fs.h:
231 /* hash value occupies bits from 7 up to 30 */
232 #define GET_HASH_VALUE(offset) ((offset) & 0x7fffff80LL)
233 #define MAX_GENERATION_NUMBER 127
234
235 // bonefish:
236 // derived from name.c: get_third_component()
237 uint32
key_offset_for_name(hash_function_t hash,const char * name,int len)238 key_offset_for_name(hash_function_t hash, const char *name, int len)
239 {
240 uint32 res;
241
242 if (!len || (len == 1 && name[0] == '.'))
243 return DOT_OFFSET;
244 if (len == 2 && name[0] == '.' && name[1] == '.')
245 return DOT_DOT_OFFSET;
246
247 res = (*hash)((const signed char*)name, len);
248
249 // take bits from 7-th to 30-th including both bounds
250 res = GET_HASH_VALUE(res);
251 if (res == 0)
252 // needed to have no names before "." and ".." those have hash
253 // value == 0 and generation conters 1 and 2 accordingly
254 res = 128;
255 return res + MAX_GENERATION_NUMBER;
256 }
257
258