]>
Commit | Line | Data |
---|---|---|
52783e0c TT |
1 | /* |
2 | * dirhash.c -- Calculate the hash of a directory entry | |
3 | * | |
4 | * Copyright (c) 2001 Daniel Phillips | |
efc6f628 | 5 | * |
52783e0c TT |
6 | * Copyright (c) 2002 Theodore Ts'o. |
7 | * | |
8 | * %Begin-Header% | |
543547a5 TT |
9 | * This file may be redistributed under the terms of the GNU Library |
10 | * General Public License, version 2. | |
52783e0c TT |
11 | * %End-Header% |
12 | */ | |
13 | ||
d1154eb4 | 14 | #include "config.h" |
52783e0c | 15 | #include <stdio.h> |
d3f91798 | 16 | #include <string.h> |
28b44ef0 | 17 | #include <limits.h> |
52783e0c TT |
18 | |
19 | #include "ext2_fs.h" | |
20 | #include "ext2fs.h" | |
21 | ||
b33278c4 TT |
22 | /* |
23 | * Keyed 32-bit hash function using TEA in a Davis-Meyer function | |
24 | * H0 = Key | |
25 | * Hi = E Mi(Hi-1) + Hi-1 | |
26 | * | |
27 | * (see Applied Cryptography, 2nd edition, p448). | |
28 | * | |
29 | * Jeremy Fitzhardinge <jeremy@zip.com.au> 1998 | |
efc6f628 | 30 | * |
b33278c4 TT |
31 | * This code is made available under the terms of the GPL |
32 | */ | |
33 | #define DELTA 0x9E3779B9 | |
34 | ||
35 | static void TEA_transform(__u32 buf[4], __u32 const in[]) | |
36 | { | |
37 | __u32 sum = 0; | |
38 | __u32 b0 = buf[0], b1 = buf[1]; | |
39 | __u32 a = in[0], b = in[1], c = in[2], d = in[3]; | |
40 | int n = 16; | |
41 | ||
efc6f628 TT |
42 | do { |
43 | sum += DELTA; | |
44 | b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b); | |
45 | b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d); | |
b33278c4 TT |
46 | } while(--n); |
47 | ||
48 | buf[0] += b0; | |
49 | buf[1] += b1; | |
50 | } | |
51 | ||
503f9e7f TT |
52 | /* F, G and H are basic MD4 functions: selection, majority, parity */ |
53 | #define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z)))) | |
54 | #define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z))) | |
55 | #define H(x, y, z) ((x) ^ (y) ^ (z)) | |
56 | ||
57 | /* | |
58 | * The generic round function. The application is so specific that | |
59 | * we don't bother protecting all the arguments with parens, as is generally | |
60 | * good macro practice, in favor of extra legibility. | |
61 | * Rotation is separate from addition to prevent recomputation | |
62 | */ | |
63 | #define ROUND(f, a, b, c, d, x, s) \ | |
64 | (a += f(b, c, d) + x, a = (a << s) | (a >> (32-s))) | |
65 | #define K1 0 | |
66 | #define K2 013240474631UL | |
67 | #define K3 015666365641UL | |
68 | ||
69 | /* | |
70 | * Basic cut-down MD4 transform. Returns only 32 bits of result. | |
71 | */ | |
b33278c4 | 72 | static void halfMD4Transform (__u32 buf[4], __u32 const in[]) |
503f9e7f TT |
73 | { |
74 | __u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3]; | |
75 | ||
76 | /* Round 1 */ | |
77 | ROUND(F, a, b, c, d, in[0] + K1, 3); | |
78 | ROUND(F, d, a, b, c, in[1] + K1, 7); | |
79 | ROUND(F, c, d, a, b, in[2] + K1, 11); | |
80 | ROUND(F, b, c, d, a, in[3] + K1, 19); | |
81 | ROUND(F, a, b, c, d, in[4] + K1, 3); | |
82 | ROUND(F, d, a, b, c, in[5] + K1, 7); | |
83 | ROUND(F, c, d, a, b, in[6] + K1, 11); | |
84 | ROUND(F, b, c, d, a, in[7] + K1, 19); | |
85 | ||
86 | /* Round 2 */ | |
87 | ROUND(G, a, b, c, d, in[1] + K2, 3); | |
88 | ROUND(G, d, a, b, c, in[3] + K2, 5); | |
89 | ROUND(G, c, d, a, b, in[5] + K2, 9); | |
90 | ROUND(G, b, c, d, a, in[7] + K2, 13); | |
91 | ROUND(G, a, b, c, d, in[0] + K2, 3); | |
92 | ROUND(G, d, a, b, c, in[2] + K2, 5); | |
93 | ROUND(G, c, d, a, b, in[4] + K2, 9); | |
94 | ROUND(G, b, c, d, a, in[6] + K2, 13); | |
95 | ||
96 | /* Round 3 */ | |
97 | ROUND(H, a, b, c, d, in[3] + K3, 3); | |
98 | ROUND(H, d, a, b, c, in[7] + K3, 9); | |
99 | ROUND(H, c, d, a, b, in[2] + K3, 11); | |
100 | ROUND(H, b, c, d, a, in[6] + K3, 15); | |
101 | ROUND(H, a, b, c, d, in[1] + K3, 3); | |
102 | ROUND(H, d, a, b, c, in[5] + K3, 9); | |
103 | ROUND(H, c, d, a, b, in[0] + K3, 11); | |
104 | ROUND(H, b, c, d, a, in[4] + K3, 15); | |
105 | ||
106 | buf[0] += a; | |
107 | buf[1] += b; | |
108 | buf[2] += c; | |
109 | buf[3] += d; | |
503f9e7f TT |
110 | } |
111 | ||
112 | #undef ROUND | |
113 | #undef F | |
114 | #undef G | |
115 | #undef H | |
116 | #undef K1 | |
117 | #undef K2 | |
118 | #undef K3 | |
119 | ||
120 | /* The old legacy hash */ | |
f77704e4 TT |
121 | static ext2_dirhash_t dx_hack_hash (const char *name, int len, |
122 | int unsigned_flag) | |
52783e0c | 123 | { |
f77704e4 TT |
124 | __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; |
125 | const unsigned char *ucp = (const unsigned char *) name; | |
126 | const signed char *scp = (const signed char *) name; | |
127 | int c; | |
128 | ||
52783e0c | 129 | while (len--) { |
f77704e4 TT |
130 | if (unsigned_flag) |
131 | c = (int) *ucp++; | |
132 | else | |
133 | c = (int) *scp++; | |
134 | hash = hash1 + (hash0 ^ (c * 7152373)); | |
efc6f628 | 135 | |
52783e0c TT |
136 | if (hash & 0x80000000) hash -= 0x7fffffff; |
137 | hash1 = hash0; | |
138 | hash0 = hash; | |
139 | } | |
1acb01b4 | 140 | return (hash0 << 1); |
52783e0c TT |
141 | } |
142 | ||
f77704e4 TT |
143 | static void str2hashbuf(const char *msg, int len, __u32 *buf, int num, |
144 | int unsigned_flag) | |
b33278c4 TT |
145 | { |
146 | __u32 pad, val; | |
f77704e4 TT |
147 | int i, c; |
148 | const unsigned char *ucp = (const unsigned char *) msg; | |
149 | const signed char *scp = (const signed char *) msg; | |
b33278c4 TT |
150 | |
151 | pad = (__u32)len | ((__u32)len << 8); | |
152 | pad |= pad << 16; | |
153 | ||
154 | val = pad; | |
155 | if (len > num*4) | |
156 | len = num * 4; | |
157 | for (i=0; i < len; i++) { | |
f77704e4 TT |
158 | if (unsigned_flag) |
159 | c = (int) ucp[i]; | |
160 | else | |
161 | c = (int) scp[i]; | |
162 | ||
163 | val = c + (val << 8); | |
b33278c4 TT |
164 | if ((i % 4) == 3) { |
165 | *buf++ = val; | |
166 | val = pad; | |
167 | num--; | |
168 | } | |
169 | } | |
170 | if (--num >= 0) | |
171 | *buf++ = val; | |
172 | while (--num >= 0) | |
173 | *buf++ = pad; | |
174 | } | |
175 | ||
52783e0c TT |
176 | /* |
177 | * Returns the hash of a filename. If len is 0 and name is NULL, then | |
178 | * this function can be used to test whether or not a hash version is | |
179 | * supported. | |
efc6f628 | 180 | * |
503f9e7f TT |
181 | * The seed is an 4 longword (32 bits) "secret" which can be used to |
182 | * uniquify a hash. If the seed is all zero's, then some default seed | |
183 | * may be used. | |
efc6f628 | 184 | * |
503f9e7f TT |
185 | * A particular hash version specifies whether or not the seed is |
186 | * represented, and whether or not the returned hash is 32 bits or 64 | |
187 | * bits. 32 bit hashes will return 0 for the minor hash. | |
28b44ef0 GKB |
188 | * |
189 | * This function doesn't do any normalization or casefolding of the | |
190 | * input string. To take charset encoding into account, use | |
191 | * ext2fs_dirhash2. | |
192 | * | |
52783e0c TT |
193 | */ |
194 | errcode_t ext2fs_dirhash(int version, const char *name, int len, | |
b33278c4 | 195 | const __u32 *seed, |
503f9e7f TT |
196 | ext2_dirhash_t *ret_hash, |
197 | ext2_dirhash_t *ret_minor_hash) | |
52783e0c TT |
198 | { |
199 | __u32 hash; | |
503f9e7f | 200 | __u32 minor_hash = 0; |
cc90bdfd | 201 | const char *p; |
b33278c4 TT |
202 | int i; |
203 | __u32 in[8], buf[4]; | |
f77704e4 | 204 | int unsigned_flag = 0; |
b33278c4 TT |
205 | |
206 | /* Initialize the default seed for the hash checksum functions */ | |
207 | buf[0] = 0x67452301; | |
208 | buf[1] = 0xefcdab89; | |
209 | buf[2] = 0x98badcfe; | |
210 | buf[3] = 0x10325476; | |
52783e0c | 211 | |
503f9e7f | 212 | /* Check to see if the seed is all zero's */ |
b33278c4 TT |
213 | if (seed) { |
214 | for (i=0; i < 4; i++) { | |
215 | if (seed[i]) | |
216 | break; | |
217 | } | |
218 | if (i < 4) | |
219 | memcpy(buf, seed, sizeof(buf)); | |
503f9e7f | 220 | } |
efc6f628 | 221 | |
b33278c4 | 222 | switch (version) { |
f77704e4 TT |
223 | case EXT2_HASH_LEGACY_UNSIGNED: |
224 | unsigned_flag++; | |
9e30fb23 | 225 | /* fallthrough */ |
b33278c4 | 226 | case EXT2_HASH_LEGACY: |
f77704e4 | 227 | hash = dx_hack_hash(name, len, unsigned_flag); |
b33278c4 | 228 | break; |
f77704e4 TT |
229 | case EXT2_HASH_HALF_MD4_UNSIGNED: |
230 | unsigned_flag++; | |
9e30fb23 | 231 | /* fallthrough */ |
b33278c4 | 232 | case EXT2_HASH_HALF_MD4: |
cc90bdfd | 233 | p = name; |
b33278c4 | 234 | while (len > 0) { |
f77704e4 | 235 | str2hashbuf(p, len, in, 8, unsigned_flag); |
b33278c4 | 236 | halfMD4Transform(buf, in); |
503f9e7f TT |
237 | len -= 32; |
238 | p += 32; | |
239 | } | |
b33278c4 TT |
240 | minor_hash = buf[2]; |
241 | hash = buf[1]; | |
242 | break; | |
f77704e4 TT |
243 | case EXT2_HASH_TEA_UNSIGNED: |
244 | unsigned_flag++; | |
9e30fb23 | 245 | /* fallthrough */ |
b33278c4 TT |
246 | case EXT2_HASH_TEA: |
247 | p = name; | |
248 | while (len > 0) { | |
f77704e4 | 249 | str2hashbuf(p, len, in, 4, unsigned_flag); |
b33278c4 TT |
250 | TEA_transform(buf, in); |
251 | len -= 16; | |
252 | p += 16; | |
253 | } | |
254 | hash = buf[0]; | |
255 | minor_hash = buf[1]; | |
256 | break; | |
257 | default: | |
52783e0c TT |
258 | *ret_hash = 0; |
259 | return EXT2_ET_DIRHASH_UNSUPP; | |
260 | } | |
b33278c4 | 261 | *ret_hash = hash & ~1; |
503f9e7f TT |
262 | if (ret_minor_hash) |
263 | *ret_minor_hash = minor_hash; | |
52783e0c | 264 | return 0; |
52783e0c | 265 | } |
28b44ef0 GKB |
266 | |
267 | /* | |
268 | * Returns the hash of a filename considering normalization and | |
269 | * casefolding. This is a wrapper around ext2fs_dirhash with string | |
270 | * encoding support based on the nls_table and the flags. Check | |
271 | * ext2fs_dirhash for documentation on the input and output parameters. | |
272 | */ | |
273 | errcode_t ext2fs_dirhash2(int version, const char *name, int len, | |
388e1d56 TT |
274 | const struct ext2fs_nls_table *charset, |
275 | int hash_flags, const __u32 *seed, | |
28b44ef0 GKB |
276 | ext2_dirhash_t *ret_hash, |
277 | ext2_dirhash_t *ret_minor_hash) | |
278 | { | |
279 | errcode_t r; | |
280 | int dlen; | |
28b44ef0 | 281 | |
a8567fdb | 282 | if (len && charset && (hash_flags & EXT4_CASEFOLD_FL)) { |
28b44ef0 GKB |
283 | char buff[PATH_MAX]; |
284 | ||
a8567fdb | 285 | dlen = charset->ops->casefold(charset, name, len, buff, |
28b44ef0 | 286 | sizeof(buff)); |
28b44ef0 GKB |
287 | if (dlen < 0) { |
288 | if (dlen == -EINVAL) | |
289 | goto opaque_seq; | |
290 | ||
291 | return dlen; | |
292 | } | |
293 | r = ext2fs_dirhash(version, buff, dlen, seed, ret_hash, | |
294 | ret_minor_hash); | |
295 | return r; | |
296 | } | |
297 | ||
298 | opaque_seq: | |
299 | return ext2fs_dirhash(version, name, len, seed, ret_hash, | |
300 | ret_minor_hash); | |
301 | } |