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/jbd2.h> 14 #include <linux/cryptohash.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 37 /* The old legacy hash */ 38 static __u32 dx_hack_hash(const char *name, int len) 39 { 40 __u32 hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; 41 while (len--) { 42 __u32 hash = hash1 + (hash0 ^ (*name++ * 7152373)); 43 44 if (hash & 0x80000000) hash -= 0x7fffffff; 45 hash1 = hash0; 46 hash0 = hash; 47 } 48 return (hash0 << 1); 49 } 50 51 static void str2hashbuf(const char *msg, int len, __u32 *buf, int num) 52 { 53 __u32 pad, val; 54 int i; 55 56 pad = (__u32)len | ((__u32)len << 8); 57 pad |= pad << 16; 58 59 val = pad; 60 if (len > num*4) 61 len = num * 4; 62 for (i = 0; i < len; i++) { 63 if ((i % 4) == 0) 64 val = pad; 65 val = msg[i] + (val << 8); 66 if ((i % 4) == 3) { 67 *buf++ = val; 68 val = pad; 69 num--; 70 } 71 } 72 if (--num >= 0) 73 *buf++ = val; 74 while (--num >= 0) 75 *buf++ = pad; 76 } 77 78 /* 79 * Returns the hash of a filename. If len is 0 and name is NULL, then 80 * this function can be used to test whether or not a hash version is 81 * supported. 82 * 83 * The seed is an 4 longword (32 bits) "secret" which can be used to 84 * uniquify a hash. If the seed is all zero's, then some default seed 85 * may be used. 86 * 87 * A particular hash version specifies whether or not the seed is 88 * represented, and whether or not the returned hash is 32 bits or 64 89 * bits. 32 bit hashes will return 0 for the minor hash. 90 */ 91 int ext4fs_dirhash(const char *name, int len, struct dx_hash_info *hinfo) 92 { 93 __u32 hash; 94 __u32 minor_hash = 0; 95 const char *p; 96 int i; 97 __u32 in[8], buf[4]; 98 99 /* Initialize the default seed for the hash checksum functions */ 100 buf[0] = 0x67452301; 101 buf[1] = 0xefcdab89; 102 buf[2] = 0x98badcfe; 103 buf[3] = 0x10325476; 104 105 /* Check to see if the seed is all zero's */ 106 if (hinfo->seed) { 107 for (i = 0; i < 4; i++) { 108 if (hinfo->seed[i]) 109 break; 110 } 111 if (i < 4) 112 memcpy(buf, hinfo->seed, sizeof(buf)); 113 } 114 115 switch (hinfo->hash_version) { 116 case DX_HASH_LEGACY: 117 hash = dx_hack_hash(name, len); 118 break; 119 case DX_HASH_HALF_MD4: 120 p = name; 121 while (len > 0) { 122 str2hashbuf(p, len, in, 8); 123 half_md4_transform(buf, in); 124 len -= 32; 125 p += 32; 126 } 127 minor_hash = buf[2]; 128 hash = buf[1]; 129 break; 130 case DX_HASH_TEA: 131 p = name; 132 while (len > 0) { 133 str2hashbuf(p, len, in, 4); 134 TEA_transform(buf, in); 135 len -= 16; 136 p += 16; 137 } 138 hash = buf[0]; 139 minor_hash = buf[1]; 140 break; 141 default: 142 hinfo->hash = 0; 143 return -1; 144 } 145 hash = hash & ~1; 146 if (hash == (EXT4_HTREE_EOF << 1)) 147 hash = (EXT4_HTREE_EOF-1) << 1; 148 hinfo->hash = hash; 149 hinfo->minor_hash = minor_hash; 150 return 0; 151 } 152