Contents of /trunk/mkinitrd-magellan/busybox/e2fsprogs/old_e2fsprogs/ext2fs/dirhash.c
Parent Directory | Revision Log
Revision 816 -
(show annotations)
(download)
Fri Apr 24 18:33:46 2009 UTC (15 years ago) by niro
File MIME type: text/plain
File size: 5428 byte(s)
Fri Apr 24 18:33:46 2009 UTC (15 years ago) by niro
File MIME type: text/plain
File size: 5428 byte(s)
-updated to busybox-1.13.4
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 | } |