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