diff options
Diffstat (limited to 'e2fsprogs/ext2fs/dirhash.c')
-rw-r--r-- | e2fsprogs/ext2fs/dirhash.c | 234 |
1 files changed, 0 insertions, 234 deletions
diff --git a/e2fsprogs/ext2fs/dirhash.c b/e2fsprogs/ext2fs/dirhash.c deleted file mode 100644 index ab3243fd7..000000000 --- a/e2fsprogs/ext2fs/dirhash.c +++ /dev/null | |||
@@ -1,234 +0,0 @@ | |||
1 | /* vi: set sw=4 ts=4: */ | ||
2 | /* | ||
3 | * dirhash.c -- Calculate the hash of a directory entry | ||
4 | * | ||
5 | * Copyright (c) 2001 Daniel Phillips | ||
6 | * | ||
7 | * Copyright (c) 2002 Theodore Ts'o. | ||
8 | * | ||
9 | * %Begin-Header% | ||
10 | * This file may be redistributed under the terms of the GNU Public | ||
11 | * License. | ||
12 | * %End-Header% | ||
13 | */ | ||
14 | |||
15 | #include <stdio.h> | ||
16 | #include <string.h> | ||
17 | |||
18 | #include "ext2_fs.h" | ||
19 | #include "ext2fs.h" | ||
20 | |||
21 | /* | ||
22 | * Keyed 32-bit hash function using TEA in a Davis-Meyer function | ||
23 | * H0 = Key | ||
24 | * Hi = E Mi(Hi-1) + Hi-1 | ||
25 | * | ||
26 | * (see Applied Cryptography, 2nd edition, p448). | ||
27 | * | ||
28 | * Jeremy Fitzhardinge <jeremy@zip.com.au> 1998 | ||
29 | * | ||
30 | * This code is made available under the terms of the GPL | ||
31 | */ | ||
32 | #define DELTA 0x9E3779B9 | ||
33 | |||
34 | static void TEA_transform(__u32 buf[4], __u32 const in[]) | ||
35 | { | ||
36 | __u32 sum = 0; | ||
37 | __u32 b0 = buf[0], b1 = buf[1]; | ||
38 | __u32 a = in[0], b = in[1], c = in[2], d = in[3]; | ||
39 | int n = 16; | ||
40 | |||
41 | do { | ||
42 | sum += DELTA; | ||
43 | b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b); | ||
44 | b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d); | ||
45 | } while(--n); | ||
46 | |||
47 | buf[0] += b0; | ||
48 | buf[1] += b1; | ||
49 | } | ||
50 | |||
51 | /* F, G and H are basic MD4 functions: selection, majority, parity */ | ||
52 | #define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z)))) | ||
53 | #define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z))) | ||
54 | #define H(x, y, z) ((x) ^ (y) ^ (z)) | ||
55 | |||
56 | /* | ||
57 | * The generic round function. The application is so specific that | ||
58 | * we don't bother protecting all the arguments with parens, as is generally | ||
59 | * good macro practice, in favor of extra legibility. | ||
60 | * Rotation is separate from addition to prevent recomputation | ||
61 | */ | ||
62 | #define ROUND(f, a, b, c, d, x, s) \ | ||
63 | (a += f(b, c, d) + x, a = (a << s) | (a >> (32-s))) | ||
64 | #define K1 0 | ||
65 | #define K2 013240474631UL | ||
66 | #define K3 015666365641UL | ||
67 | |||
68 | /* | ||
69 | * Basic cut-down MD4 transform. Returns only 32 bits of result. | ||
70 | */ | ||
71 | static void halfMD4Transform (__u32 buf[4], __u32 const in[]) | ||
72 | { | ||
73 | __u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3]; | ||
74 | |||
75 | /* Round 1 */ | ||
76 | ROUND(F, a, b, c, d, in[0] + K1, 3); | ||
77 | ROUND(F, d, a, b, c, in[1] + K1, 7); | ||
78 | ROUND(F, c, d, a, b, in[2] + K1, 11); | ||
79 | ROUND(F, b, c, d, a, in[3] + K1, 19); | ||
80 | ROUND(F, a, b, c, d, in[4] + K1, 3); | ||
81 | ROUND(F, d, a, b, c, in[5] + K1, 7); | ||
82 | ROUND(F, c, d, a, b, in[6] + K1, 11); | ||
83 | ROUND(F, b, c, d, a, in[7] + K1, 19); | ||
84 | |||
85 | /* Round 2 */ | ||
86 | ROUND(G, a, b, c, d, in[1] + K2, 3); | ||
87 | ROUND(G, d, a, b, c, in[3] + K2, 5); | ||
88 | ROUND(G, c, d, a, b, in[5] + K2, 9); | ||
89 | ROUND(G, b, c, d, a, in[7] + K2, 13); | ||
90 | ROUND(G, a, b, c, d, in[0] + K2, 3); | ||
91 | ROUND(G, d, a, b, c, in[2] + K2, 5); | ||
92 | ROUND(G, c, d, a, b, in[4] + K2, 9); | ||
93 | ROUND(G, b, c, d, a, in[6] + K2, 13); | ||
94 | |||
95 | /* Round 3 */ | ||
96 | ROUND(H, a, b, c, d, in[3] + K3, 3); | ||
97 | ROUND(H, d, a, b, c, in[7] + K3, 9); | ||
98 | ROUND(H, c, d, a, b, in[2] + K3, 11); | ||
99 | ROUND(H, b, c, d, a, in[6] + K3, 15); | ||
100 | ROUND(H, a, b, c, d, in[1] + K3, 3); | ||
101 | ROUND(H, d, a, b, c, in[5] + K3, 9); | ||
102 | ROUND(H, c, d, a, b, in[0] + K3, 11); | ||
103 | ROUND(H, b, c, d, a, in[4] + K3, 15); | ||
104 | |||
105 | buf[0] += a; | ||
106 | buf[1] += b; | ||
107 | buf[2] += c; | ||
108 | buf[3] += d; | ||
109 | } | ||
110 | |||
111 | #undef ROUND | ||
112 | #undef F | ||
113 | #undef G | ||
114 | #undef H | ||
115 | #undef K1 | ||
116 | #undef K2 | ||
117 | #undef K3 | ||
118 | |||
119 | /* The old legacy hash */ | ||
120 | static ext2_dirhash_t dx_hack_hash (const char *name, int len) | ||
121 | { | ||
122 | __u32 hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; | ||
123 | while (len--) { | ||
124 | __u32 hash = hash1 + (hash0 ^ (*name++ * 7152373)); | ||
125 | |||
126 | if (hash & 0x80000000) hash -= 0x7fffffff; | ||
127 | hash1 = hash0; | ||
128 | hash0 = hash; | ||
129 | } | ||
130 | return (hash0 << 1); | ||
131 | } | ||
132 | |||
133 | static void str2hashbuf(const char *msg, int len, __u32 *buf, int num) | ||
134 | { | ||
135 | __u32 pad, val; | ||
136 | int i; | ||
137 | |||
138 | pad = (__u32)len | ((__u32)len << 8); | ||
139 | pad |= pad << 16; | ||
140 | |||
141 | val = pad; | ||
142 | if (len > num*4) | ||
143 | len = num * 4; | ||
144 | for (i=0; i < len; i++) { | ||
145 | if ((i % 4) == 0) | ||
146 | val = pad; | ||
147 | val = msg[i] + (val << 8); | ||
148 | if ((i % 4) == 3) { | ||
149 | *buf++ = val; | ||
150 | val = pad; | ||
151 | num--; | ||
152 | } | ||
153 | } | ||
154 | if (--num >= 0) | ||
155 | *buf++ = val; | ||
156 | while (--num >= 0) | ||
157 | *buf++ = pad; | ||
158 | } | ||
159 | |||
160 | /* | ||
161 | * Returns the hash of a filename. If len is 0 and name is NULL, then | ||
162 | * this function can be used to test whether or not a hash version is | ||
163 | * supported. | ||
164 | * | ||
165 | * The seed is an 4 longword (32 bits) "secret" which can be used to | ||
166 | * uniquify a hash. If the seed is all zero's, then some default seed | ||
167 | * may be used. | ||
168 | * | ||
169 | * A particular hash version specifies whether or not the seed is | ||
170 | * represented, and whether or not the returned hash is 32 bits or 64 | ||
171 | * bits. 32 bit hashes will return 0 for the minor hash. | ||
172 | */ | ||
173 | errcode_t ext2fs_dirhash(int version, const char *name, int len, | ||
174 | const __u32 *seed, | ||
175 | ext2_dirhash_t *ret_hash, | ||
176 | ext2_dirhash_t *ret_minor_hash) | ||
177 | { | ||
178 | __u32 hash; | ||
179 | __u32 minor_hash = 0; | ||
180 | const char *p; | ||
181 | int i; | ||
182 | __u32 in[8], buf[4]; | ||
183 | |||
184 | /* Initialize the default seed for the hash checksum functions */ | ||
185 | buf[0] = 0x67452301; | ||
186 | buf[1] = 0xefcdab89; | ||
187 | buf[2] = 0x98badcfe; | ||
188 | buf[3] = 0x10325476; | ||
189 | |||
190 | /* Check to see if the seed is all zero's */ | ||
191 | if (seed) { | ||
192 | for (i=0; i < 4; i++) { | ||
193 | if (seed[i]) | ||
194 | break; | ||
195 | } | ||
196 | if (i < 4) | ||
197 | memcpy(buf, seed, sizeof(buf)); | ||
198 | } | ||
199 | |||
200 | switch (version) { | ||
201 | case EXT2_HASH_LEGACY: | ||
202 | hash = dx_hack_hash(name, len); | ||
203 | break; | ||
204 | case EXT2_HASH_HALF_MD4: | ||
205 | p = name; | ||
206 | while (len > 0) { | ||
207 | str2hashbuf(p, len, in, 8); | ||
208 | halfMD4Transform(buf, in); | ||
209 | len -= 32; | ||
210 | p += 32; | ||
211 | } | ||
212 | minor_hash = buf[2]; | ||
213 | hash = buf[1]; | ||
214 | break; | ||
215 | case EXT2_HASH_TEA: | ||
216 | p = name; | ||
217 | while (len > 0) { | ||
218 | str2hashbuf(p, len, in, 4); | ||
219 | TEA_transform(buf, in); | ||
220 | len -= 16; | ||
221 | p += 16; | ||
222 | } | ||
223 | hash = buf[0]; | ||
224 | minor_hash = buf[1]; | ||
225 | break; | ||
226 | default: | ||
227 | *ret_hash = 0; | ||
228 | return EXT2_ET_DIRHASH_UNSUPP; | ||
229 | } | ||
230 | *ret_hash = hash & ~1; | ||
231 | if (ret_minor_hash) | ||
232 | *ret_minor_hash = minor_hash; | ||
233 | return 0; | ||
234 | } | ||