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