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