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 val = ((int) scp[i]) + (val << 8); 152 if ((i % 4) == 3) { 153 *buf++ = val; 154 val = pad; 155 num--; 156 } 157 } 158 if (--num >= 0) 159 *buf++ = val; 160 while (--num >= 0) 161 *buf++ = pad; 162 } 163 164 static void str2hashbuf_unsigned(const char *msg, int len, __u32 *buf, int num) 165 { 166 __u32 pad, val; 167 int i; 168 const unsigned char *ucp = (const unsigned char *) msg; 169 170 pad = (__u32)len | ((__u32)len << 8); 171 pad |= pad << 16; 172 173 val = pad; 174 if (len > num*4) 175 len = num * 4; 176 for (i = 0; i < len; i++) { 177 val = ((int) ucp[i]) + (val << 8); 178 if ((i % 4) == 3) { 179 *buf++ = val; 180 val = pad; 181 num--; 182 } 183 } 184 if (--num >= 0) 185 *buf++ = val; 186 while (--num >= 0) 187 *buf++ = pad; 188 } 189 190 /* 191 * Returns the hash of a filename. If len is 0 and name is NULL, then 192 * this function can be used to test whether or not a hash version is 193 * supported. 194 * 195 * The seed is an 4 longword (32 bits) "secret" which can be used to 196 * uniquify a hash. If the seed is all zero's, then some default seed 197 * may be used. 198 * 199 * A particular hash version specifies whether or not the seed is 200 * represented, and whether or not the returned hash is 32 bits or 64 201 * bits. 32 bit hashes will return 0 for the minor hash. 202 */ 203 int ext4fs_dirhash(const char *name, int len, struct dx_hash_info *hinfo) 204 { 205 __u32 hash; 206 __u32 minor_hash = 0; 207 const char *p; 208 int i; 209 __u32 in[8], buf[4]; 210 void (*str2hashbuf)(const char *, int, __u32 *, int) = 211 str2hashbuf_signed; 212 213 /* Initialize the default seed for the hash checksum functions */ 214 buf[0] = 0x67452301; 215 buf[1] = 0xefcdab89; 216 buf[2] = 0x98badcfe; 217 buf[3] = 0x10325476; 218 219 /* Check to see if the seed is all zero's */ 220 if (hinfo->seed) { 221 for (i = 0; i < 4; i++) { 222 if (hinfo->seed[i]) { 223 memcpy(buf, hinfo->seed, sizeof(buf)); 224 break; 225 } 226 } 227 } 228 229 switch (hinfo->hash_version) { 230 case DX_HASH_LEGACY_UNSIGNED: 231 hash = dx_hack_hash_unsigned(name, len); 232 break; 233 case DX_HASH_LEGACY: 234 hash = dx_hack_hash_signed(name, len); 235 break; 236 case DX_HASH_HALF_MD4_UNSIGNED: 237 str2hashbuf = str2hashbuf_unsigned; 238 case DX_HASH_HALF_MD4: 239 p = name; 240 while (len > 0) { 241 (*str2hashbuf)(p, len, in, 8); 242 half_md4_transform(buf, in); 243 len -= 32; 244 p += 32; 245 } 246 minor_hash = buf[2]; 247 hash = buf[1]; 248 break; 249 case DX_HASH_TEA_UNSIGNED: 250 str2hashbuf = str2hashbuf_unsigned; 251 case DX_HASH_TEA: 252 p = name; 253 while (len > 0) { 254 (*str2hashbuf)(p, len, in, 4); 255 TEA_transform(buf, in); 256 len -= 16; 257 p += 16; 258 } 259 hash = buf[0]; 260 minor_hash = buf[1]; 261 break; 262 default: 263 hinfo->hash = 0; 264 return -1; 265 } 266 hash = hash & ~1; 267 if (hash == (EXT4_HTREE_EOF_32BIT << 1)) 268 hash = (EXT4_HTREE_EOF_32BIT - 1) << 1; 269 hinfo->hash = hash; 270 hinfo->minor_hash = minor_hash; 271 return 0; 272 } 273