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/cryptohash.h> 14 #include "ext4.h" 15 16 #define DELTA 0x9E3779B9 17 18 static void TEA_transform(__u32 buf[4], __u32 const in[]) 19 { 20 __u32 sum = 0; 21 __u32 b0 = buf[0], b1 = buf[1]; 22 __u32 a = in[0], b = in[1], c = in[2], d = in[3]; 23 int n = 16; 24 25 do { 26 sum += DELTA; 27 b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b); 28 b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d); 29 } while (--n); 30 31 buf[0] += b0; 32 buf[1] += b1; 33 } 34 35 36 /* The old legacy hash */ 37 static __u32 dx_hack_hash_unsigned(const char *name, int len) 38 { 39 __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; 40 const unsigned char *ucp = (const unsigned char *) name; 41 42 while (len--) { 43 hash = hash1 + (hash0 ^ (((int) *ucp++) * 7152373)); 44 45 if (hash & 0x80000000) 46 hash -= 0x7fffffff; 47 hash1 = hash0; 48 hash0 = hash; 49 } 50 return hash0 << 1; 51 } 52 53 static __u32 dx_hack_hash_signed(const char *name, int len) 54 { 55 __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; 56 const signed char *scp = (const signed char *) name; 57 58 while (len--) { 59 hash = hash1 + (hash0 ^ (((int) *scp++) * 7152373)); 60 61 if (hash & 0x80000000) 62 hash -= 0x7fffffff; 63 hash1 = hash0; 64 hash0 = hash; 65 } 66 return hash0 << 1; 67 } 68 69 static void str2hashbuf_signed(const char *msg, int len, __u32 *buf, int num) 70 { 71 __u32 pad, val; 72 int i; 73 const signed char *scp = (const signed char *) msg; 74 75 pad = (__u32)len | ((__u32)len << 8); 76 pad |= pad << 16; 77 78 val = pad; 79 if (len > num*4) 80 len = num * 4; 81 for (i = 0; i < len; i++) { 82 if ((i % 4) == 0) 83 val = pad; 84 val = ((int) scp[i]) + (val << 8); 85 if ((i % 4) == 3) { 86 *buf++ = val; 87 val = pad; 88 num--; 89 } 90 } 91 if (--num >= 0) 92 *buf++ = val; 93 while (--num >= 0) 94 *buf++ = pad; 95 } 96 97 static void str2hashbuf_unsigned(const char *msg, int len, __u32 *buf, int num) 98 { 99 __u32 pad, val; 100 int i; 101 const unsigned char *ucp = (const unsigned char *) msg; 102 103 pad = (__u32)len | ((__u32)len << 8); 104 pad |= pad << 16; 105 106 val = pad; 107 if (len > num*4) 108 len = num * 4; 109 for (i = 0; i < len; i++) { 110 if ((i % 4) == 0) 111 val = pad; 112 val = ((int) ucp[i]) + (val << 8); 113 if ((i % 4) == 3) { 114 *buf++ = val; 115 val = pad; 116 num--; 117 } 118 } 119 if (--num >= 0) 120 *buf++ = val; 121 while (--num >= 0) 122 *buf++ = pad; 123 } 124 125 /* 126 * Returns the hash of a filename. If len is 0 and name is NULL, then 127 * this function can be used to test whether or not a hash version is 128 * supported. 129 * 130 * The seed is an 4 longword (32 bits) "secret" which can be used to 131 * uniquify a hash. If the seed is all zero's, then some default seed 132 * may be used. 133 * 134 * A particular hash version specifies whether or not the seed is 135 * represented, and whether or not the returned hash is 32 bits or 64 136 * bits. 32 bit hashes will return 0 for the minor hash. 137 */ 138 int ext4fs_dirhash(const char *name, int len, struct dx_hash_info *hinfo) 139 { 140 __u32 hash; 141 __u32 minor_hash = 0; 142 const char *p; 143 int i; 144 __u32 in[8], buf[4]; 145 void (*str2hashbuf)(const char *, int, __u32 *, int) = 146 str2hashbuf_signed; 147 148 /* Initialize the default seed for the hash checksum functions */ 149 buf[0] = 0x67452301; 150 buf[1] = 0xefcdab89; 151 buf[2] = 0x98badcfe; 152 buf[3] = 0x10325476; 153 154 /* Check to see if the seed is all zero's */ 155 if (hinfo->seed) { 156 for (i = 0; i < 4; i++) { 157 if (hinfo->seed[i]) { 158 memcpy(buf, hinfo->seed, sizeof(buf)); 159 break; 160 } 161 } 162 } 163 164 switch (hinfo->hash_version) { 165 case DX_HASH_LEGACY_UNSIGNED: 166 hash = dx_hack_hash_unsigned(name, len); 167 break; 168 case DX_HASH_LEGACY: 169 hash = dx_hack_hash_signed(name, len); 170 break; 171 case DX_HASH_HALF_MD4_UNSIGNED: 172 str2hashbuf = str2hashbuf_unsigned; 173 case DX_HASH_HALF_MD4: 174 p = name; 175 while (len > 0) { 176 (*str2hashbuf)(p, len, in, 8); 177 half_md4_transform(buf, in); 178 len -= 32; 179 p += 32; 180 } 181 minor_hash = buf[2]; 182 hash = buf[1]; 183 break; 184 case DX_HASH_TEA_UNSIGNED: 185 str2hashbuf = str2hashbuf_unsigned; 186 case DX_HASH_TEA: 187 p = name; 188 while (len > 0) { 189 (*str2hashbuf)(p, len, in, 4); 190 TEA_transform(buf, in); 191 len -= 16; 192 p += 16; 193 } 194 hash = buf[0]; 195 minor_hash = buf[1]; 196 break; 197 default: 198 hinfo->hash = 0; 199 return -1; 200 } 201 hash = hash & ~1; 202 if (hash == (EXT4_HTREE_EOF_32BIT << 1)) 203 hash = (EXT4_HTREE_EOF_32BIT - 1) << 1; 204 hinfo->hash = hash; 205 hinfo->minor_hash = minor_hash; 206 return 0; 207 } 208