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