1f5166768STheodore Ts'o // SPDX-License-Identifier: GPL-2.0 2ac27a0ecSDave Kleikamp /* 3617ba13bSMingming Cao * linux/fs/ext4/hash.c 4ac27a0ecSDave Kleikamp * 5ac27a0ecSDave Kleikamp * Copyright (C) 2002 by Theodore Ts'o 6ac27a0ecSDave Kleikamp */ 7ac27a0ecSDave Kleikamp 8ac27a0ecSDave Kleikamp #include <linux/fs.h> 91c83a9aaSJason A. Donenfeld #include <linux/compiler.h> 101c83a9aaSJason A. Donenfeld #include <linux/bitops.h> 113dcf5451SChristoph Hellwig #include "ext4.h" 12ac27a0ecSDave Kleikamp 13ac27a0ecSDave Kleikamp #define DELTA 0x9E3779B9 14ac27a0ecSDave Kleikamp 15ac27a0ecSDave Kleikamp static void TEA_transform(__u32 buf[4], __u32 const in[]) 16ac27a0ecSDave Kleikamp { 17ac27a0ecSDave Kleikamp __u32 sum = 0; 18ac27a0ecSDave Kleikamp __u32 b0 = buf[0], b1 = buf[1]; 19ac27a0ecSDave Kleikamp __u32 a = in[0], b = in[1], c = in[2], d = in[3]; 20ac27a0ecSDave Kleikamp int n = 16; 21ac27a0ecSDave Kleikamp 22ac27a0ecSDave Kleikamp do { 23ac27a0ecSDave Kleikamp sum += DELTA; 24ac27a0ecSDave Kleikamp b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b); 25ac27a0ecSDave Kleikamp b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d); 26ac27a0ecSDave Kleikamp } while (--n); 27ac27a0ecSDave Kleikamp 28ac27a0ecSDave Kleikamp buf[0] += b0; 29ac27a0ecSDave Kleikamp buf[1] += b1; 30ac27a0ecSDave Kleikamp } 31ac27a0ecSDave Kleikamp 321c83a9aaSJason A. Donenfeld /* F, G and H are basic MD4 functions: selection, majority, parity */ 331c83a9aaSJason A. Donenfeld #define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z)))) 341c83a9aaSJason A. Donenfeld #define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z))) 351c83a9aaSJason A. Donenfeld #define H(x, y, z) ((x) ^ (y) ^ (z)) 361c83a9aaSJason A. Donenfeld 371c83a9aaSJason A. Donenfeld /* 381c83a9aaSJason A. Donenfeld * The generic round function. The application is so specific that 391c83a9aaSJason A. Donenfeld * we don't bother protecting all the arguments with parens, as is generally 401c83a9aaSJason A. Donenfeld * good macro practice, in favor of extra legibility. 411c83a9aaSJason A. Donenfeld * Rotation is separate from addition to prevent recomputation 421c83a9aaSJason A. Donenfeld */ 431c83a9aaSJason A. Donenfeld #define ROUND(f, a, b, c, d, x, s) \ 441c83a9aaSJason A. Donenfeld (a += f(b, c, d) + x, a = rol32(a, s)) 451c83a9aaSJason A. Donenfeld #define K1 0 461c83a9aaSJason A. Donenfeld #define K2 013240474631UL 471c83a9aaSJason A. Donenfeld #define K3 015666365641UL 481c83a9aaSJason A. Donenfeld 491c83a9aaSJason A. Donenfeld /* 501c83a9aaSJason A. Donenfeld * Basic cut-down MD4 transform. Returns only 32 bits of result. 511c83a9aaSJason A. Donenfeld */ 521c83a9aaSJason A. Donenfeld static __u32 half_md4_transform(__u32 buf[4], __u32 const in[8]) 531c83a9aaSJason A. Donenfeld { 541c83a9aaSJason A. Donenfeld __u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3]; 551c83a9aaSJason A. Donenfeld 561c83a9aaSJason A. Donenfeld /* Round 1 */ 571c83a9aaSJason A. Donenfeld ROUND(F, a, b, c, d, in[0] + K1, 3); 581c83a9aaSJason A. Donenfeld ROUND(F, d, a, b, c, in[1] + K1, 7); 591c83a9aaSJason A. Donenfeld ROUND(F, c, d, a, b, in[2] + K1, 11); 601c83a9aaSJason A. Donenfeld ROUND(F, b, c, d, a, in[3] + K1, 19); 611c83a9aaSJason A. Donenfeld ROUND(F, a, b, c, d, in[4] + K1, 3); 621c83a9aaSJason A. Donenfeld ROUND(F, d, a, b, c, in[5] + K1, 7); 631c83a9aaSJason A. Donenfeld ROUND(F, c, d, a, b, in[6] + K1, 11); 641c83a9aaSJason A. Donenfeld ROUND(F, b, c, d, a, in[7] + K1, 19); 651c83a9aaSJason A. Donenfeld 661c83a9aaSJason A. Donenfeld /* Round 2 */ 671c83a9aaSJason A. Donenfeld ROUND(G, a, b, c, d, in[1] + K2, 3); 681c83a9aaSJason A. Donenfeld ROUND(G, d, a, b, c, in[3] + K2, 5); 691c83a9aaSJason A. Donenfeld ROUND(G, c, d, a, b, in[5] + K2, 9); 701c83a9aaSJason A. Donenfeld ROUND(G, b, c, d, a, in[7] + K2, 13); 711c83a9aaSJason A. Donenfeld ROUND(G, a, b, c, d, in[0] + K2, 3); 721c83a9aaSJason A. Donenfeld ROUND(G, d, a, b, c, in[2] + K2, 5); 731c83a9aaSJason A. Donenfeld ROUND(G, c, d, a, b, in[4] + K2, 9); 741c83a9aaSJason A. Donenfeld ROUND(G, b, c, d, a, in[6] + K2, 13); 751c83a9aaSJason A. Donenfeld 761c83a9aaSJason A. Donenfeld /* Round 3 */ 771c83a9aaSJason A. Donenfeld ROUND(H, a, b, c, d, in[3] + K3, 3); 781c83a9aaSJason A. Donenfeld ROUND(H, d, a, b, c, in[7] + K3, 9); 791c83a9aaSJason A. Donenfeld ROUND(H, c, d, a, b, in[2] + K3, 11); 801c83a9aaSJason A. Donenfeld ROUND(H, b, c, d, a, in[6] + K3, 15); 811c83a9aaSJason A. Donenfeld ROUND(H, a, b, c, d, in[1] + K3, 3); 821c83a9aaSJason A. Donenfeld ROUND(H, d, a, b, c, in[5] + K3, 9); 831c83a9aaSJason A. Donenfeld ROUND(H, c, d, a, b, in[0] + K3, 11); 841c83a9aaSJason A. Donenfeld ROUND(H, b, c, d, a, in[4] + K3, 15); 851c83a9aaSJason A. Donenfeld 861c83a9aaSJason A. Donenfeld buf[0] += a; 871c83a9aaSJason A. Donenfeld buf[1] += b; 881c83a9aaSJason A. Donenfeld buf[2] += c; 891c83a9aaSJason A. Donenfeld buf[3] += d; 901c83a9aaSJason A. Donenfeld 911c83a9aaSJason A. Donenfeld return buf[1]; /* "most hashed" word */ 921c83a9aaSJason A. Donenfeld } 931c83a9aaSJason A. Donenfeld #undef ROUND 941c83a9aaSJason A. Donenfeld #undef K1 951c83a9aaSJason A. Donenfeld #undef K2 961c83a9aaSJason A. Donenfeld #undef K3 971c83a9aaSJason A. Donenfeld #undef F 981c83a9aaSJason A. Donenfeld #undef G 991c83a9aaSJason A. Donenfeld #undef H 100ac27a0ecSDave Kleikamp 101ac27a0ecSDave Kleikamp /* The old legacy hash */ 102f99b2589STheodore Ts'o static __u32 dx_hack_hash_unsigned(const char *name, int len) 103ac27a0ecSDave Kleikamp { 104f99b2589STheodore Ts'o __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; 105f99b2589STheodore Ts'o const unsigned char *ucp = (const unsigned char *) name; 106ac27a0ecSDave Kleikamp 107f99b2589STheodore Ts'o while (len--) { 108f99b2589STheodore Ts'o hash = hash1 + (hash0 ^ (((int) *ucp++) * 7152373)); 109f99b2589STheodore Ts'o 110f99b2589STheodore Ts'o if (hash & 0x80000000) 111f99b2589STheodore Ts'o hash -= 0x7fffffff; 112ac27a0ecSDave Kleikamp hash1 = hash0; 113ac27a0ecSDave Kleikamp hash0 = hash; 114ac27a0ecSDave Kleikamp } 115f99b2589STheodore Ts'o return hash0 << 1; 116ac27a0ecSDave Kleikamp } 117ac27a0ecSDave Kleikamp 118f99b2589STheodore Ts'o static __u32 dx_hack_hash_signed(const char *name, int len) 119f99b2589STheodore Ts'o { 120f99b2589STheodore Ts'o __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; 121f99b2589STheodore Ts'o const signed char *scp = (const signed char *) name; 122f99b2589STheodore Ts'o 123f99b2589STheodore Ts'o while (len--) { 124f99b2589STheodore Ts'o hash = hash1 + (hash0 ^ (((int) *scp++) * 7152373)); 125f99b2589STheodore Ts'o 126f99b2589STheodore Ts'o if (hash & 0x80000000) 127f99b2589STheodore Ts'o hash -= 0x7fffffff; 128f99b2589STheodore Ts'o hash1 = hash0; 129f99b2589STheodore Ts'o hash0 = hash; 130f99b2589STheodore Ts'o } 131f99b2589STheodore Ts'o return hash0 << 1; 132f99b2589STheodore Ts'o } 133f99b2589STheodore Ts'o 134f99b2589STheodore Ts'o static void str2hashbuf_signed(const char *msg, int len, __u32 *buf, int num) 135ac27a0ecSDave Kleikamp { 136ac27a0ecSDave Kleikamp __u32 pad, val; 137ac27a0ecSDave Kleikamp int i; 138f99b2589STheodore Ts'o const signed char *scp = (const signed char *) msg; 139ac27a0ecSDave Kleikamp 140ac27a0ecSDave Kleikamp pad = (__u32)len | ((__u32)len << 8); 141ac27a0ecSDave Kleikamp pad |= pad << 16; 142ac27a0ecSDave Kleikamp 143ac27a0ecSDave Kleikamp val = pad; 144ac27a0ecSDave Kleikamp if (len > num*4) 145ac27a0ecSDave Kleikamp len = num * 4; 146ac27a0ecSDave Kleikamp for (i = 0; i < len; i++) { 147f99b2589STheodore Ts'o val = ((int) scp[i]) + (val << 8); 148f99b2589STheodore Ts'o if ((i % 4) == 3) { 149f99b2589STheodore Ts'o *buf++ = val; 150f99b2589STheodore Ts'o val = pad; 151f99b2589STheodore Ts'o num--; 152f99b2589STheodore Ts'o } 153f99b2589STheodore Ts'o } 154f99b2589STheodore Ts'o if (--num >= 0) 155f99b2589STheodore Ts'o *buf++ = val; 156f99b2589STheodore Ts'o while (--num >= 0) 157f99b2589STheodore Ts'o *buf++ = pad; 158f99b2589STheodore Ts'o } 159f99b2589STheodore Ts'o 160f99b2589STheodore Ts'o static void str2hashbuf_unsigned(const char *msg, int len, __u32 *buf, int num) 161f99b2589STheodore Ts'o { 162f99b2589STheodore Ts'o __u32 pad, val; 163f99b2589STheodore Ts'o int i; 164f99b2589STheodore Ts'o const unsigned char *ucp = (const unsigned char *) msg; 165f99b2589STheodore Ts'o 166f99b2589STheodore Ts'o pad = (__u32)len | ((__u32)len << 8); 167f99b2589STheodore Ts'o pad |= pad << 16; 168f99b2589STheodore Ts'o 169f99b2589STheodore Ts'o val = pad; 170f99b2589STheodore Ts'o if (len > num*4) 171f99b2589STheodore Ts'o len = num * 4; 172f99b2589STheodore Ts'o for (i = 0; i < len; i++) { 173f99b2589STheodore Ts'o val = ((int) ucp[i]) + (val << 8); 174ac27a0ecSDave Kleikamp if ((i % 4) == 3) { 175ac27a0ecSDave Kleikamp *buf++ = val; 176ac27a0ecSDave Kleikamp val = pad; 177ac27a0ecSDave Kleikamp num--; 178ac27a0ecSDave Kleikamp } 179ac27a0ecSDave Kleikamp } 180ac27a0ecSDave Kleikamp if (--num >= 0) 181ac27a0ecSDave Kleikamp *buf++ = val; 182ac27a0ecSDave Kleikamp while (--num >= 0) 183ac27a0ecSDave Kleikamp *buf++ = pad; 184ac27a0ecSDave Kleikamp } 185ac27a0ecSDave Kleikamp 186ac27a0ecSDave Kleikamp /* 187ac27a0ecSDave Kleikamp * Returns the hash of a filename. If len is 0 and name is NULL, then 188ac27a0ecSDave Kleikamp * this function can be used to test whether or not a hash version is 189ac27a0ecSDave Kleikamp * supported. 190ac27a0ecSDave Kleikamp * 191ac27a0ecSDave Kleikamp * The seed is an 4 longword (32 bits) "secret" which can be used to 192ac27a0ecSDave Kleikamp * uniquify a hash. If the seed is all zero's, then some default seed 193ac27a0ecSDave Kleikamp * may be used. 194ac27a0ecSDave Kleikamp * 195ac27a0ecSDave Kleikamp * A particular hash version specifies whether or not the seed is 196ac27a0ecSDave Kleikamp * represented, and whether or not the returned hash is 32 bits or 64 197ac27a0ecSDave Kleikamp * bits. 32 bit hashes will return 0 for the minor hash. 198ac27a0ecSDave Kleikamp */ 199617ba13bSMingming Cao int ext4fs_dirhash(const char *name, int len, struct dx_hash_info *hinfo) 200ac27a0ecSDave Kleikamp { 201ac27a0ecSDave Kleikamp __u32 hash; 202ac27a0ecSDave Kleikamp __u32 minor_hash = 0; 203ac27a0ecSDave Kleikamp const char *p; 204ac27a0ecSDave Kleikamp int i; 205ac27a0ecSDave Kleikamp __u32 in[8], buf[4]; 206f99b2589STheodore Ts'o void (*str2hashbuf)(const char *, int, __u32 *, int) = 207f99b2589STheodore Ts'o str2hashbuf_signed; 208ac27a0ecSDave Kleikamp 209ac27a0ecSDave Kleikamp /* Initialize the default seed for the hash checksum functions */ 210ac27a0ecSDave Kleikamp buf[0] = 0x67452301; 211ac27a0ecSDave Kleikamp buf[1] = 0xefcdab89; 212ac27a0ecSDave Kleikamp buf[2] = 0x98badcfe; 213ac27a0ecSDave Kleikamp buf[3] = 0x10325476; 214ac27a0ecSDave Kleikamp 215ac27a0ecSDave Kleikamp /* Check to see if the seed is all zero's */ 216ac27a0ecSDave Kleikamp if (hinfo->seed) { 217ac27a0ecSDave Kleikamp for (i = 0; i < 4; i++) { 2180e79537dSCong Ding if (hinfo->seed[i]) { 2190e79537dSCong Ding memcpy(buf, hinfo->seed, sizeof(buf)); 220ac27a0ecSDave Kleikamp break; 221ac27a0ecSDave Kleikamp } 2220e79537dSCong Ding } 223ac27a0ecSDave Kleikamp } 224ac27a0ecSDave Kleikamp 225ac27a0ecSDave Kleikamp switch (hinfo->hash_version) { 226f99b2589STheodore Ts'o case DX_HASH_LEGACY_UNSIGNED: 227f99b2589STheodore Ts'o hash = dx_hack_hash_unsigned(name, len); 228ac27a0ecSDave Kleikamp break; 229f99b2589STheodore Ts'o case DX_HASH_LEGACY: 230f99b2589STheodore Ts'o hash = dx_hack_hash_signed(name, len); 231f99b2589STheodore Ts'o break; 232f99b2589STheodore Ts'o case DX_HASH_HALF_MD4_UNSIGNED: 233f99b2589STheodore Ts'o str2hashbuf = str2hashbuf_unsigned; 234ac27a0ecSDave Kleikamp case DX_HASH_HALF_MD4: 235ac27a0ecSDave Kleikamp p = name; 236ac27a0ecSDave Kleikamp while (len > 0) { 237f99b2589STheodore Ts'o (*str2hashbuf)(p, len, in, 8); 238ac27a0ecSDave Kleikamp half_md4_transform(buf, in); 239ac27a0ecSDave Kleikamp len -= 32; 240ac27a0ecSDave Kleikamp p += 32; 241ac27a0ecSDave Kleikamp } 242ac27a0ecSDave Kleikamp minor_hash = buf[2]; 243ac27a0ecSDave Kleikamp hash = buf[1]; 244ac27a0ecSDave Kleikamp break; 245f99b2589STheodore Ts'o case DX_HASH_TEA_UNSIGNED: 246f99b2589STheodore Ts'o str2hashbuf = str2hashbuf_unsigned; 247ac27a0ecSDave Kleikamp case DX_HASH_TEA: 248ac27a0ecSDave Kleikamp p = name; 249ac27a0ecSDave Kleikamp while (len > 0) { 250f99b2589STheodore Ts'o (*str2hashbuf)(p, len, in, 4); 251ac27a0ecSDave Kleikamp TEA_transform(buf, in); 252ac27a0ecSDave Kleikamp len -= 16; 253ac27a0ecSDave Kleikamp p += 16; 254ac27a0ecSDave Kleikamp } 255ac27a0ecSDave Kleikamp hash = buf[0]; 256ac27a0ecSDave Kleikamp minor_hash = buf[1]; 257ac27a0ecSDave Kleikamp break; 258ac27a0ecSDave Kleikamp default: 259ac27a0ecSDave Kleikamp hinfo->hash = 0; 260ac27a0ecSDave Kleikamp return -1; 261ac27a0ecSDave Kleikamp } 262ac27a0ecSDave Kleikamp hash = hash & ~1; 263d1f5273eSFan Yong if (hash == (EXT4_HTREE_EOF_32BIT << 1)) 264d1f5273eSFan Yong hash = (EXT4_HTREE_EOF_32BIT - 1) << 1; 265ac27a0ecSDave Kleikamp hinfo->hash = hash; 266ac27a0ecSDave Kleikamp hinfo->minor_hash = minor_hash; 267ac27a0ecSDave Kleikamp return 0; 268ac27a0ecSDave Kleikamp } 269