]>
Commit | Line | Data |
---|---|---|
ac27a0ec | 1 | /* |
617ba13b | 2 | * linux/fs/ext4/hash.c |
ac27a0ec DK |
3 | * |
4 | * Copyright (C) 2002 by Theodore Ts'o | |
5 | * | |
6 | * This file is released under the GPL v2. | |
7 | * | |
8 | * This file may be redistributed under the terms of the GNU Public | |
9 | * License. | |
10 | */ | |
11 | ||
12 | #include <linux/fs.h> | |
1c83a9aa JD |
13 | #include <linux/compiler.h> |
14 | #include <linux/bitops.h> | |
3dcf5451 | 15 | #include "ext4.h" |
ac27a0ec DK |
16 | |
17 | #define DELTA 0x9E3779B9 | |
18 | ||
19 | static void TEA_transform(__u32 buf[4], __u32 const in[]) | |
20 | { | |
21 | __u32 sum = 0; | |
22 | __u32 b0 = buf[0], b1 = buf[1]; | |
23 | __u32 a = in[0], b = in[1], c = in[2], d = in[3]; | |
24 | int n = 16; | |
25 | ||
26 | do { | |
27 | sum += DELTA; | |
28 | b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b); | |
29 | b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d); | |
af5bc92d | 30 | } while (--n); |
ac27a0ec DK |
31 | |
32 | buf[0] += b0; | |
33 | buf[1] += b1; | |
34 | } | |
35 | ||
1c83a9aa JD |
36 | /* F, G and H are basic MD4 functions: selection, majority, parity */ |
37 | #define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z)))) | |
38 | #define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z))) | |
39 | #define H(x, y, z) ((x) ^ (y) ^ (z)) | |
40 | ||
41 | /* | |
42 | * The generic round function. The application is so specific that | |
43 | * we don't bother protecting all the arguments with parens, as is generally | |
44 | * good macro practice, in favor of extra legibility. | |
45 | * Rotation is separate from addition to prevent recomputation | |
46 | */ | |
47 | #define ROUND(f, a, b, c, d, x, s) \ | |
48 | (a += f(b, c, d) + x, a = rol32(a, s)) | |
49 | #define K1 0 | |
50 | #define K2 013240474631UL | |
51 | #define K3 015666365641UL | |
52 | ||
53 | /* | |
54 | * Basic cut-down MD4 transform. Returns only 32 bits of result. | |
55 | */ | |
56 | static __u32 half_md4_transform(__u32 buf[4], __u32 const in[8]) | |
57 | { | |
58 | __u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3]; | |
59 | ||
60 | /* Round 1 */ | |
61 | ROUND(F, a, b, c, d, in[0] + K1, 3); | |
62 | ROUND(F, d, a, b, c, in[1] + K1, 7); | |
63 | ROUND(F, c, d, a, b, in[2] + K1, 11); | |
64 | ROUND(F, b, c, d, a, in[3] + K1, 19); | |
65 | ROUND(F, a, b, c, d, in[4] + K1, 3); | |
66 | ROUND(F, d, a, b, c, in[5] + K1, 7); | |
67 | ROUND(F, c, d, a, b, in[6] + K1, 11); | |
68 | ROUND(F, b, c, d, a, in[7] + K1, 19); | |
69 | ||
70 | /* Round 2 */ | |
71 | ROUND(G, a, b, c, d, in[1] + K2, 3); | |
72 | ROUND(G, d, a, b, c, in[3] + K2, 5); | |
73 | ROUND(G, c, d, a, b, in[5] + K2, 9); | |
74 | ROUND(G, b, c, d, a, in[7] + K2, 13); | |
75 | ROUND(G, a, b, c, d, in[0] + K2, 3); | |
76 | ROUND(G, d, a, b, c, in[2] + K2, 5); | |
77 | ROUND(G, c, d, a, b, in[4] + K2, 9); | |
78 | ROUND(G, b, c, d, a, in[6] + K2, 13); | |
79 | ||
80 | /* Round 3 */ | |
81 | ROUND(H, a, b, c, d, in[3] + K3, 3); | |
82 | ROUND(H, d, a, b, c, in[7] + K3, 9); | |
83 | ROUND(H, c, d, a, b, in[2] + K3, 11); | |
84 | ROUND(H, b, c, d, a, in[6] + K3, 15); | |
85 | ROUND(H, a, b, c, d, in[1] + K3, 3); | |
86 | ROUND(H, d, a, b, c, in[5] + K3, 9); | |
87 | ROUND(H, c, d, a, b, in[0] + K3, 11); | |
88 | ROUND(H, b, c, d, a, in[4] + K3, 15); | |
89 | ||
90 | buf[0] += a; | |
91 | buf[1] += b; | |
92 | buf[2] += c; | |
93 | buf[3] += d; | |
94 | ||
95 | return buf[1]; /* "most hashed" word */ | |
96 | } | |
97 | #undef ROUND | |
98 | #undef K1 | |
99 | #undef K2 | |
100 | #undef K3 | |
101 | #undef F | |
102 | #undef G | |
103 | #undef H | |
ac27a0ec DK |
104 | |
105 | /* The old legacy hash */ | |
f99b2589 | 106 | static __u32 dx_hack_hash_unsigned(const char *name, int len) |
ac27a0ec | 107 | { |
f99b2589 TT |
108 | __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; |
109 | const unsigned char *ucp = (const unsigned char *) name; | |
110 | ||
111 | while (len--) { | |
112 | hash = hash1 + (hash0 ^ (((int) *ucp++) * 7152373)); | |
113 | ||
114 | if (hash & 0x80000000) | |
115 | hash -= 0x7fffffff; | |
116 | hash1 = hash0; | |
117 | hash0 = hash; | |
118 | } | |
119 | return hash0 << 1; | |
120 | } | |
121 | ||
122 | static __u32 dx_hack_hash_signed(const char *name, int len) | |
123 | { | |
124 | __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; | |
125 | const signed char *scp = (const signed char *) name; | |
126 | ||
ac27a0ec | 127 | while (len--) { |
f99b2589 | 128 | hash = hash1 + (hash0 ^ (((int) *scp++) * 7152373)); |
ac27a0ec | 129 | |
f99b2589 TT |
130 | if (hash & 0x80000000) |
131 | hash -= 0x7fffffff; | |
ac27a0ec DK |
132 | hash1 = hash0; |
133 | hash0 = hash; | |
134 | } | |
f99b2589 TT |
135 | return hash0 << 1; |
136 | } | |
137 | ||
138 | static void str2hashbuf_signed(const char *msg, int len, __u32 *buf, int num) | |
139 | { | |
140 | __u32 pad, val; | |
141 | int i; | |
142 | const signed char *scp = (const signed char *) msg; | |
143 | ||
144 | pad = (__u32)len | ((__u32)len << 8); | |
145 | pad |= pad << 16; | |
146 | ||
147 | val = pad; | |
148 | if (len > num*4) | |
149 | len = num * 4; | |
150 | for (i = 0; i < len; i++) { | |
151 | if ((i % 4) == 0) | |
152 | val = pad; | |
153 | val = ((int) scp[i]) + (val << 8); | |
154 | if ((i % 4) == 3) { | |
155 | *buf++ = val; | |
156 | val = pad; | |
157 | num--; | |
158 | } | |
159 | } | |
160 | if (--num >= 0) | |
161 | *buf++ = val; | |
162 | while (--num >= 0) | |
163 | *buf++ = pad; | |
ac27a0ec DK |
164 | } |
165 | ||
f99b2589 | 166 | static void str2hashbuf_unsigned(const char *msg, int len, __u32 *buf, int num) |
ac27a0ec DK |
167 | { |
168 | __u32 pad, val; | |
169 | int i; | |
f99b2589 | 170 | const unsigned char *ucp = (const unsigned char *) msg; |
ac27a0ec DK |
171 | |
172 | pad = (__u32)len | ((__u32)len << 8); | |
173 | pad |= pad << 16; | |
174 | ||
175 | val = pad; | |
176 | if (len > num*4) | |
177 | len = num * 4; | |
af5bc92d | 178 | for (i = 0; i < len; i++) { |
ac27a0ec DK |
179 | if ((i % 4) == 0) |
180 | val = pad; | |
f99b2589 | 181 | val = ((int) ucp[i]) + (val << 8); |
ac27a0ec DK |
182 | if ((i % 4) == 3) { |
183 | *buf++ = val; | |
184 | val = pad; | |
185 | num--; | |
186 | } | |
187 | } | |
188 | if (--num >= 0) | |
189 | *buf++ = val; | |
190 | while (--num >= 0) | |
191 | *buf++ = pad; | |
192 | } | |
193 | ||
194 | /* | |
195 | * Returns the hash of a filename. If len is 0 and name is NULL, then | |
196 | * this function can be used to test whether or not a hash version is | |
197 | * supported. | |
198 | * | |
199 | * The seed is an 4 longword (32 bits) "secret" which can be used to | |
200 | * uniquify a hash. If the seed is all zero's, then some default seed | |
201 | * may be used. | |
202 | * | |
203 | * A particular hash version specifies whether or not the seed is | |
204 | * represented, and whether or not the returned hash is 32 bits or 64 | |
205 | * bits. 32 bit hashes will return 0 for the minor hash. | |
206 | */ | |
617ba13b | 207 | int ext4fs_dirhash(const char *name, int len, struct dx_hash_info *hinfo) |
ac27a0ec DK |
208 | { |
209 | __u32 hash; | |
210 | __u32 minor_hash = 0; | |
211 | const char *p; | |
212 | int i; | |
213 | __u32 in[8], buf[4]; | |
f99b2589 TT |
214 | void (*str2hashbuf)(const char *, int, __u32 *, int) = |
215 | str2hashbuf_signed; | |
ac27a0ec DK |
216 | |
217 | /* Initialize the default seed for the hash checksum functions */ | |
218 | buf[0] = 0x67452301; | |
219 | buf[1] = 0xefcdab89; | |
220 | buf[2] = 0x98badcfe; | |
221 | buf[3] = 0x10325476; | |
222 | ||
223 | /* Check to see if the seed is all zero's */ | |
224 | if (hinfo->seed) { | |
af5bc92d | 225 | for (i = 0; i < 4; i++) { |
0e79537d CD |
226 | if (hinfo->seed[i]) { |
227 | memcpy(buf, hinfo->seed, sizeof(buf)); | |
ac27a0ec | 228 | break; |
0e79537d | 229 | } |
ac27a0ec | 230 | } |
ac27a0ec DK |
231 | } |
232 | ||
233 | switch (hinfo->hash_version) { | |
f99b2589 TT |
234 | case DX_HASH_LEGACY_UNSIGNED: |
235 | hash = dx_hack_hash_unsigned(name, len); | |
236 | break; | |
ac27a0ec | 237 | case DX_HASH_LEGACY: |
f99b2589 | 238 | hash = dx_hack_hash_signed(name, len); |
ac27a0ec | 239 | break; |
f99b2589 TT |
240 | case DX_HASH_HALF_MD4_UNSIGNED: |
241 | str2hashbuf = str2hashbuf_unsigned; | |
ac27a0ec DK |
242 | case DX_HASH_HALF_MD4: |
243 | p = name; | |
244 | while (len > 0) { | |
f99b2589 | 245 | (*str2hashbuf)(p, len, in, 8); |
ac27a0ec DK |
246 | half_md4_transform(buf, in); |
247 | len -= 32; | |
248 | p += 32; | |
249 | } | |
250 | minor_hash = buf[2]; | |
251 | hash = buf[1]; | |
252 | break; | |
f99b2589 TT |
253 | case DX_HASH_TEA_UNSIGNED: |
254 | str2hashbuf = str2hashbuf_unsigned; | |
ac27a0ec DK |
255 | case DX_HASH_TEA: |
256 | p = name; | |
257 | while (len > 0) { | |
f99b2589 | 258 | (*str2hashbuf)(p, len, in, 4); |
ac27a0ec DK |
259 | TEA_transform(buf, in); |
260 | len -= 16; | |
261 | p += 16; | |
262 | } | |
263 | hash = buf[0]; | |
264 | minor_hash = buf[1]; | |
265 | break; | |
266 | default: | |
267 | hinfo->hash = 0; | |
268 | return -1; | |
269 | } | |
270 | hash = hash & ~1; | |
d1f5273e FY |
271 | if (hash == (EXT4_HTREE_EOF_32BIT << 1)) |
272 | hash = (EXT4_HTREE_EOF_32BIT - 1) << 1; | |
ac27a0ec DK |
273 | hinfo->hash = hash; |
274 | hinfo->minor_hash = minor_hash; | |
275 | return 0; | |
276 | } |