Theodore Ts'o | 52783e0 | 2002-03-11 15:04:45 -0500 | [diff] [blame] | 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 | |
Theodore Ts'o | 503f9e7 | 2002-06-26 16:52:10 -0400 | [diff] [blame^] | 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 */ |
Theodore Ts'o | 52783e0 | 2002-03-11 15:04:45 -0500 | [diff] [blame] | 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 | } |
Theodore Ts'o | 1acb01b | 2002-03-12 13:41:31 -0500 | [diff] [blame] | 101 | return (hash0 << 1); |
Theodore Ts'o | 52783e0 | 2002-03-11 15:04:45 -0500 | [diff] [blame] | 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. |
Theodore Ts'o | 503f9e7 | 2002-06-26 16:52:10 -0400 | [diff] [blame^] | 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. |
Theodore Ts'o | 52783e0 | 2002-03-11 15:04:45 -0500 | [diff] [blame] | 116 | */ |
| 117 | errcode_t ext2fs_dirhash(int version, const char *name, int len, |
Theodore Ts'o | 503f9e7 | 2002-06-26 16:52:10 -0400 | [diff] [blame^] | 118 | const __u32 seed[4], |
| 119 | ext2_dirhash_t *ret_hash, |
| 120 | ext2_dirhash_t *ret_minor_hash) |
Theodore Ts'o | 52783e0 | 2002-03-11 15:04:45 -0500 | [diff] [blame] | 121 | { |
| 122 | __u32 hash; |
Theodore Ts'o | 503f9e7 | 2002-06-26 16:52:10 -0400 | [diff] [blame^] | 123 | __u32 minor_hash = 0; |
| 124 | char *p; |
| 125 | int i; |
Theodore Ts'o | 52783e0 | 2002-03-11 15:04:45 -0500 | [diff] [blame] | 126 | |
Theodore Ts'o | 503f9e7 | 2002-06-26 16:52:10 -0400 | [diff] [blame^] | 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) |
Theodore Ts'o | 52783e0 | 2002-03-11 15:04:45 -0500 | [diff] [blame] | 134 | hash = dx_hack_hash(name, len); |
Theodore Ts'o | 503f9e7 | 2002-06-26 16:52:10 -0400 | [diff] [blame^] | 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 { |
Theodore Ts'o | 52783e0 | 2002-03-11 15:04:45 -0500 | [diff] [blame] | 162 | *ret_hash = 0; |
| 163 | return EXT2_ET_DIRHASH_UNSUPP; |
| 164 | } |
| 165 | *ret_hash = hash; |
Theodore Ts'o | 503f9e7 | 2002-06-26 16:52:10 -0400 | [diff] [blame^] | 166 | if (ret_minor_hash) |
| 167 | *ret_minor_hash = minor_hash; |
Theodore Ts'o | 52783e0 | 2002-03-11 15:04:45 -0500 | [diff] [blame] | 168 | return 0; |
| 169 | |
| 170 | } |
Theodore Ts'o | 503f9e7 | 2002-06-26 16:52:10 -0400 | [diff] [blame^] | 171 | |
| 172 | |
| 173 | |