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 }