]>
Commit | Line | Data |
---|---|---|
52783e0c TT |
1 | /* |
2 | * dirhash.c -- Calculate the hash of a directory entry | |
3 | * | |
4 | * Copyright (c) 2001 Daniel Phillips | |
5 | * | |
6 | * Copyright (c) 2002 Theodore Ts'o. | |
7 | * | |
8 | * %Begin-Header% | |
9 | * This file may be redistributed under the terms of the GNU Public | |
10 | * License. | |
11 | * %End-Header% | |
12 | */ | |
13 | ||
14 | #include <stdio.h> | |
15 | ||
16 | #include "ext2_fs.h" | |
17 | #include "ext2fs.h" | |
18 | ||
503f9e7f TT |
19 | /* F, G and H are basic MD4 functions: selection, majority, parity */ |
20 | #define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z)))) | |
21 | #define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z))) | |
22 | #define H(x, y, z) ((x) ^ (y) ^ (z)) | |
23 | ||
24 | /* | |
25 | * The generic round function. The application is so specific that | |
26 | * we don't bother protecting all the arguments with parens, as is generally | |
27 | * good macro practice, in favor of extra legibility. | |
28 | * Rotation is separate from addition to prevent recomputation | |
29 | */ | |
30 | #define ROUND(f, a, b, c, d, x, s) \ | |
31 | (a += f(b, c, d) + x, a = (a << s) | (a >> (32-s))) | |
32 | #define K1 0 | |
33 | #define K2 013240474631UL | |
34 | #define K3 015666365641UL | |
35 | ||
36 | /* | |
37 | * Basic cut-down MD4 transform. Returns only 32 bits of result. | |
38 | */ | |
39 | static __u32 halfMD4Transform (__u32 buf[4], __u32 const in[]) | |
40 | { | |
41 | __u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3]; | |
42 | ||
43 | /* Round 1 */ | |
44 | ROUND(F, a, b, c, d, in[0] + K1, 3); | |
45 | ROUND(F, d, a, b, c, in[1] + K1, 7); | |
46 | ROUND(F, c, d, a, b, in[2] + K1, 11); | |
47 | ROUND(F, b, c, d, a, in[3] + K1, 19); | |
48 | ROUND(F, a, b, c, d, in[4] + K1, 3); | |
49 | ROUND(F, d, a, b, c, in[5] + K1, 7); | |
50 | ROUND(F, c, d, a, b, in[6] + K1, 11); | |
51 | ROUND(F, b, c, d, a, in[7] + K1, 19); | |
52 | ||
53 | /* Round 2 */ | |
54 | ROUND(G, a, b, c, d, in[1] + K2, 3); | |
55 | ROUND(G, d, a, b, c, in[3] + K2, 5); | |
56 | ROUND(G, c, d, a, b, in[5] + K2, 9); | |
57 | ROUND(G, b, c, d, a, in[7] + K2, 13); | |
58 | ROUND(G, a, b, c, d, in[0] + K2, 3); | |
59 | ROUND(G, d, a, b, c, in[2] + K2, 5); | |
60 | ROUND(G, c, d, a, b, in[4] + K2, 9); | |
61 | ROUND(G, b, c, d, a, in[6] + K2, 13); | |
62 | ||
63 | /* Round 3 */ | |
64 | ROUND(H, a, b, c, d, in[3] + K3, 3); | |
65 | ROUND(H, d, a, b, c, in[7] + K3, 9); | |
66 | ROUND(H, c, d, a, b, in[2] + K3, 11); | |
67 | ROUND(H, b, c, d, a, in[6] + K3, 15); | |
68 | ROUND(H, a, b, c, d, in[1] + K3, 3); | |
69 | ROUND(H, d, a, b, c, in[5] + K3, 9); | |
70 | ROUND(H, c, d, a, b, in[0] + K3, 11); | |
71 | ROUND(H, b, c, d, a, in[4] + K3, 15); | |
72 | ||
73 | buf[0] += a; | |
74 | buf[1] += b; | |
75 | buf[2] += c; | |
76 | buf[3] += d; | |
77 | ||
78 | return buf[1]; /* "most hashed" word */ | |
79 | /* Alternative: return sum of all words? */ | |
80 | } | |
81 | ||
82 | #undef ROUND | |
83 | #undef F | |
84 | #undef G | |
85 | #undef H | |
86 | #undef K1 | |
87 | #undef K2 | |
88 | #undef K3 | |
89 | ||
90 | /* The old legacy hash */ | |
52783e0c TT |
91 | static ext2_dirhash_t dx_hack_hash (const char *name, int len) |
92 | { | |
93 | __u32 hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; | |
94 | while (len--) { | |
95 | __u32 hash = hash1 + (hash0 ^ (*name++ * 7152373)); | |
96 | ||
97 | if (hash & 0x80000000) hash -= 0x7fffffff; | |
98 | hash1 = hash0; | |
99 | hash0 = hash; | |
100 | } | |
1acb01b4 | 101 | return (hash0 << 1); |
52783e0c TT |
102 | } |
103 | ||
104 | /* | |
105 | * Returns the hash of a filename. If len is 0 and name is NULL, then | |
106 | * this function can be used to test whether or not a hash version is | |
107 | * supported. | |
503f9e7f TT |
108 | * |
109 | * The seed is an 4 longword (32 bits) "secret" which can be used to | |
110 | * uniquify a hash. If the seed is all zero's, then some default seed | |
111 | * may be used. | |
112 | * | |
113 | * A particular hash version specifies whether or not the seed is | |
114 | * represented, and whether or not the returned hash is 32 bits or 64 | |
115 | * bits. 32 bit hashes will return 0 for the minor hash. | |
52783e0c TT |
116 | */ |
117 | errcode_t ext2fs_dirhash(int version, const char *name, int len, | |
503f9e7f TT |
118 | const __u32 seed[4], |
119 | ext2_dirhash_t *ret_hash, | |
120 | ext2_dirhash_t *ret_minor_hash) | |
52783e0c TT |
121 | { |
122 | __u32 hash; | |
503f9e7f TT |
123 | __u32 minor_hash = 0; |
124 | char *p; | |
125 | int i; | |
52783e0c | 126 | |
503f9e7f TT |
127 | /* Check to see if the seed is all zero's */ |
128 | for (i=0; i < 4; i++) { | |
129 | if (seed[i]) | |
130 | break; | |
131 | } | |
132 | ||
133 | if (version == EXT2_HASH_LEGACY) | |
52783e0c | 134 | hash = dx_hack_hash(name, len); |
503f9e7f TT |
135 | else if ((version == EXT2_HASH_HALF_MD4) || |
136 | (version == EXT2_HASH_HALF_MD4_SEED) || | |
137 | (version == EXT2_HASH_HALF_MD4_64)) { | |
138 | char in[32]; | |
139 | __u32 buf[4]; | |
140 | ||
141 | if ((i == 4) || (version == EXT2_HASH_HALF_MD4)) { | |
142 | buf[0] = 0x67452301; | |
143 | buf[1] = 0xefcdab89; | |
144 | buf[2] = 0x98badcfe; | |
145 | buf[3] = 0x10325476; | |
146 | } else | |
147 | memcpy(buf, in, sizeof(buf)); | |
148 | while (len) { | |
149 | if (len < 32) { | |
150 | memcpy(in, name, len); | |
151 | memset(in+len, 0, 32-len); | |
152 | hash = halfMD4Transform(buf, (__u32 *) in); | |
153 | break; | |
154 | } | |
155 | hash = halfMD4Transform(buf, (__u32 *) p); | |
156 | len -= 32; | |
157 | p += 32; | |
158 | } | |
159 | if (version == EXT2_HASH_HALF_MD4_64) | |
160 | minor_hash = buf[2]; | |
161 | } else { | |
52783e0c TT |
162 | *ret_hash = 0; |
163 | return EXT2_ET_DIRHASH_UNSUPP; | |
164 | } | |
165 | *ret_hash = hash; | |
503f9e7f TT |
166 | if (ret_minor_hash) |
167 | *ret_minor_hash = minor_hash; | |
52783e0c TT |
168 | return 0; |
169 | ||
170 | } | |
503f9e7f TT |
171 | |
172 | ||
173 |