1 /* 2 * linux/fs/ext4/hash.c 3 * 4 * Copyright (C) 2002 by Theodore Ts'o 5 * 6 * This file is released under the GPL v2. 7 * 8 * This file may be redistributed under the terms of the GNU Public 9 * License. 10 */ 11 12 #include <linux/fs.h> 13 #include <linux/compiler.h> 14 #include <linux/bitops.h> 15 #include "ext4.h" 16 17 #define DELTA 0x9E3779B9 18 19 static void TEA_transform(__u32 buf[4], __u32 const in[]) 20 { 21 __u32 sum = 0; 22 __u32 b0 = buf[0], b1 = buf[1]; 23 __u32 a = in[0], b = in[1], c = in[2], d = in[3]; 24 int n = 16; 25 26 do { 27 sum += DELTA; 28 b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b); 29 b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d); 30 } while (--n); 31 32 buf[0] += b0; 33 buf[1] += b1; 34 } 35 36 /* F, G and H are basic MD4 functions: selection, majority, parity */ 37 #define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z)))) 38 #define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z))) 39 #define H(x, y, z) ((x) ^ (y) ^ (z)) 40 41 /* 42 * The generic round function. The application is so specific that 43 * we don't bother protecting all the arguments with parens, as is generally 44 * good macro practice, in favor of extra legibility. 45 * Rotation is separate from addition to prevent recomputation 46 */ 47 #define ROUND(f, a, b, c, d, x, s) \ 48 (a += f(b, c, d) + x, a = rol32(a, s)) 49 #define K1 0 50 #define K2 013240474631UL 51 #define K3 015666365641UL 52 53 /* 54 * Basic cut-down MD4 transform. Returns only 32 bits of result. 55 */ 56 static __u32 half_md4_transform(__u32 buf[4], __u32 const in[8]) 57 { 58 __u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3]; 59 60 /* Round 1 */ 61 ROUND(F, a, b, c, d, in[0] + K1, 3); 62 ROUND(F, d, a, b, c, in[1] + K1, 7); 63 ROUND(F, c, d, a, b, in[2] + K1, 11); 64 ROUND(F, b, c, d, a, in[3] + K1, 19); 65 ROUND(F, a, b, c, d, in[4] + K1, 3); 66 ROUND(F, d, a, b, c, in[5] + K1, 7); 67 ROUND(F, c, d, a, b, in[6] + K1, 11); 68 ROUND(F, b, c, d, a, in[7] + K1, 19); 69 70 /* Round 2 */ 71 ROUND(G, a, b, c, d, in[1] + K2, 3); 72 ROUND(G, d, a, b, c, in[3] + K2, 5); 73 ROUND(G, c, d, a, b, in[5] + K2, 9); 74 ROUND(G, b, c, d, a, in[7] + K2, 13); 75 ROUND(G, a, b, c, d, in[0] + K2, 3); 76 ROUND(G, d, a, b, c, in[2] + K2, 5); 77 ROUND(G, c, d, a, b, in[4] + K2, 9); 78 ROUND(G, b, c, d, a, in[6] + K2, 13); 79 80 /* Round 3 */ 81 ROUND(H, a, b, c, d, in[3] + K3, 3); 82 ROUND(H, d, a, b, c, in[7] + K3, 9); 83 ROUND(H, c, d, a, b, in[2] + K3, 11); 84 ROUND(H, b, c, d, a, in[6] + K3, 15); 85 ROUND(H, a, b, c, d, in[1] + K3, 3); 86 ROUND(H, d, a, b, c, in[5] + K3, 9); 87 ROUND(H, c, d, a, b, in[0] + K3, 11); 88 ROUND(H, b, c, d, a, in[4] + K3, 15); 89 90 buf[0] += a; 91 buf[1] += b; 92 buf[2] += c; 93 buf[3] += d; 94 95 return buf[1]; /* "most hashed" word */ 96 } 97 #undef ROUND 98 #undef K1 99 #undef K2 100 #undef K3 101 #undef F 102 #undef G 103 #undef H 104 105 /* The old legacy hash */ 106 static __u32 dx_hack_hash_unsigned(const char *name, int len) 107 { 108 __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; 109 const unsigned char *ucp = (const unsigned char *) name; 110 111 while (len--) { 112 hash = hash1 + (hash0 ^ (((int) *ucp++) * 7152373)); 113 114 if (hash & 0x80000000) 115 hash -= 0x7fffffff; 116 hash1 = hash0; 117 hash0 = hash; 118 } 119 return hash0 << 1; 120 } 121 122 static __u32 dx_hack_hash_signed(const char *name, int len) 123 { 124 __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; 125 const signed char *scp = (const signed char *) name; 126 127 while (len--) { 128 hash = hash1 + (hash0 ^ (((int) *scp++) * 7152373)); 129 130 if (hash & 0x80000000) 131 hash -= 0x7fffffff; 132 hash1 = hash0; 133 hash0 = hash; 134 } 135 return hash0 << 1; 136 } 137 138 static void str2hashbuf_signed(const char *msg, int len, __u32 *buf, int num) 139 { 140 __u32 pad, val; 141 int i; 142 const signed char *scp = (const signed char *) msg; 143 144 pad = (__u32)len | ((__u32)len << 8); 145 pad |= pad << 16; 146 147 val = pad; 148 if (len > num*4) 149 len = num * 4; 150 for (i = 0; i < len; i++) { 151 if ((i % 4) == 0) 152 val = pad; 153 val = ((int) scp[i]) + (val << 8); 154 if ((i % 4) == 3) { 155 *buf++ = val; 156 val = pad; 157 num--; 158 } 159 } 160 if (--num >= 0) 161 *buf++ = val; 162 while (--num >= 0) 163 *buf++ = pad; 164 } 165 166 static void str2hashbuf_unsigned(const char *msg, int len, __u32 *buf, int num) 167 { 168 __u32 pad, val; 169 int i; 170 const unsigned char *ucp = (const unsigned char *) msg; 171 172 pad = (__u32)len | ((__u32)len << 8); 173 pad |= pad << 16; 174 175 val = pad; 176 if (len > num*4) 177 len = num * 4; 178 for (i = 0; i < len; i++) { 179 if ((i % 4) == 0) 180 val = pad; 181 val = ((int) ucp[i]) + (val << 8); 182 if ((i % 4) == 3) { 183 *buf++ = val; 184 val = pad; 185 num--; 186 } 187 } 188 if (--num >= 0) 189 *buf++ = val; 190 while (--num >= 0) 191 *buf++ = pad; 192 } 193 194 /* 195 * Returns the hash of a filename. If len is 0 and name is NULL, then 196 * this function can be used to test whether or not a hash version is 197 * supported. 198 * 199 * The seed is an 4 longword (32 bits) "secret" which can be used to 200 * uniquify a hash. If the seed is all zero's, then some default seed 201 * may be used. 202 * 203 * A particular hash version specifies whether or not the seed is 204 * represented, and whether or not the returned hash is 32 bits or 64 205 * bits. 32 bit hashes will return 0 for the minor hash. 206 */ 207 int ext4fs_dirhash(const char *name, int len, struct dx_hash_info *hinfo) 208 { 209 __u32 hash; 210 __u32 minor_hash = 0; 211 const char *p; 212 int i; 213 __u32 in[8], buf[4]; 214 void (*str2hashbuf)(const char *, int, __u32 *, int) = 215 str2hashbuf_signed; 216 217 /* Initialize the default seed for the hash checksum functions */ 218 buf[0] = 0x67452301; 219 buf[1] = 0xefcdab89; 220 buf[2] = 0x98badcfe; 221 buf[3] = 0x10325476; 222 223 /* Check to see if the seed is all zero's */ 224 if (hinfo->seed) { 225 for (i = 0; i < 4; i++) { 226 if (hinfo->seed[i]) { 227 memcpy(buf, hinfo->seed, sizeof(buf)); 228 break; 229 } 230 } 231 } 232 233 switch (hinfo->hash_version) { 234 case DX_HASH_LEGACY_UNSIGNED: 235 hash = dx_hack_hash_unsigned(name, len); 236 break; 237 case DX_HASH_LEGACY: 238 hash = dx_hack_hash_signed(name, len); 239 break; 240 case DX_HASH_HALF_MD4_UNSIGNED: 241 str2hashbuf = str2hashbuf_unsigned; 242 case DX_HASH_HALF_MD4: 243 p = name; 244 while (len > 0) { 245 (*str2hashbuf)(p, len, in, 8); 246 half_md4_transform(buf, in); 247 len -= 32; 248 p += 32; 249 } 250 minor_hash = buf[2]; 251 hash = buf[1]; 252 break; 253 case DX_HASH_TEA_UNSIGNED: 254 str2hashbuf = str2hashbuf_unsigned; 255 case DX_HASH_TEA: 256 p = name; 257 while (len > 0) { 258 (*str2hashbuf)(p, len, in, 4); 259 TEA_transform(buf, in); 260 len -= 16; 261 p += 16; 262 } 263 hash = buf[0]; 264 minor_hash = buf[1]; 265 break; 266 default: 267 hinfo->hash = 0; 268 return -1; 269 } 270 hash = hash & ~1; 271 if (hash == (EXT4_HTREE_EOF_32BIT << 1)) 272 hash = (EXT4_HTREE_EOF_32BIT - 1) << 1; 273 hinfo->hash = hash; 274 hinfo->minor_hash = minor_hash; 275 return 0; 276 } 277