fs/ext4/hash.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  *  linux/fs/ext4/hash.c
   4  *
   5  * Copyright (C) 2002 by Theodore Ts'o
   6  */
   7
   8 #include <linux/fs.h>
   9 #include <linux/unicode.h>
  10 #include <linux/compiler.h>
  11 #include <linux/bitops.h>
  12 #include "ext4.h"
  13
  14 #define DELTA 0x9E3779B9
  15
  16 static void TEA_transform(__u32 buf[4], __u32 const in[])
  17 {
  18         __u32   sum = 0;
  19         __u32   b0 = buf[0], b1 = buf[1];
  20         __u32   a = in[0], b = in[1], c = in[2], d = in[3];
  21         int     n = 16;
  22
  23         do {
  24                 sum += DELTA;
  25                 b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b);
  26                 b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d);
  27         } while (--n);
  28
  29         buf[0] += b0;
  30         buf[1] += b1;
  31 }
  32
  33 /* F, G and H are basic MD4 functions: selection, majority, parity */
  34 #define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
  35 #define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z)))
  36 #define H(x, y, z) ((x) ^ (y) ^ (z))
  37
  38 /*
  39  * The generic round function.  The application is so specific that
  40  * we don't bother protecting all the arguments with parens, as is generally
  41  * good macro practice, in favor of extra legibility.
  42  * Rotation is separate from addition to prevent recomputation
  43  */
  44 #define ROUND(f, a, b, c, d, x, s)      \
  45         (a += f(b, c, d) + x, a = rol32(a, s))
  46 #define K1 0
  47 #define K2 013240474631UL
  48 #define K3 015666365641UL
  49
  50 /*
  51  * Basic cut-down MD4 transform.  Returns only 32 bits of result.
  52  */
  53 static __u32 half_md4_transform(__u32 buf[4], __u32 const in[8])
  54 {
  55         __u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3];
  56
  57         /* Round 1 */
  58         ROUND(F, a, b, c, d, in[0] + K1,  3);
  59         ROUND(F, d, a, b, c, in[1] + K1,  7);
  60         ROUND(F, c, d, a, b, in[2] + K1, 11);
  61         ROUND(F, b, c, d, a, in[3] + K1, 19);
  62         ROUND(F, a, b, c, d, in[4] + K1,  3);
  63         ROUND(F, d, a, b, c, in[5] + K1,  7);
  64         ROUND(F, c, d, a, b, in[6] + K1, 11);
  65         ROUND(F, b, c, d, a, in[7] + K1, 19);
  66
  67         /* Round 2 */
  68         ROUND(G, a, b, c, d, in[1] + K2,  3);
  69         ROUND(G, d, a, b, c, in[3] + K2,  5);
  70         ROUND(G, c, d, a, b, in[5] + K2,  9);
  71         ROUND(G, b, c, d, a, in[7] + K2, 13);
  72         ROUND(G, a, b, c, d, in[0] + K2,  3);
  73         ROUND(G, d, a, b, c, in[2] + K2,  5);
  74         ROUND(G, c, d, a, b, in[4] + K2,  9);
  75         ROUND(G, b, c, d, a, in[6] + K2, 13);
  76
  77         /* Round 3 */
  78         ROUND(H, a, b, c, d, in[3] + K3,  3);
  79         ROUND(H, d, a, b, c, in[7] + K3,  9);
  80         ROUND(H, c, d, a, b, in[2] + K3, 11);
  81         ROUND(H, b, c, d, a, in[6] + K3, 15);
  82         ROUND(H, a, b, c, d, in[1] + K3,  3);
  83         ROUND(H, d, a, b, c, in[5] + K3,  9);
  84         ROUND(H, c, d, a, b, in[0] + K3, 11);
  85         ROUND(H, b, c, d, a, in[4] + K3, 15);
  86
  87         buf[0] += a;
  88         buf[1] += b;
  89         buf[2] += c;
  90         buf[3] += d;
  91
  92         return buf[1]; /* "most hashed" word */
  93 }
  94 #undef ROUND
  95 #undef K1
  96 #undef K2
  97 #undef K3
  98 #undef F
  99 #undef G
 100 #undef H
 101
 102 /* The old legacy hash */
 103 static __u32 dx_hack_hash_unsigned(const char *name, int len)
 104 {
 105         __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
 106         const unsigned char *ucp = (const unsigned char *) name;
 107
 108         while (len--) {
 109                 hash = hash1 + (hash0 ^ (((int) *ucp++) * 7152373));
 110
 111                 if (hash & 0x80000000)
 112                         hash -= 0x7fffffff;
 113                 hash1 = hash0;
 114                 hash0 = hash;
 115         }
 116         return hash0 << 1;
 117 }
 118
 119 static __u32 dx_hack_hash_signed(const char *name, int len)
 120 {
 121         __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
 122         const signed char *scp = (const signed char *) name;
 123
 124         while (len--) {
 125                 hash = hash1 + (hash0 ^ (((int) *scp++) * 7152373));
 126
 127                 if (hash & 0x80000000)
 128                         hash -= 0x7fffffff;
 129                 hash1 = hash0;
 130                 hash0 = hash;
 131         }
 132         return hash0 << 1;
 133 }
 134
 135 static void str2hashbuf_signed(const char *msg, int len, __u32 *buf, int num)
 136 {
 137         __u32   pad, val;
 138         int     i;
 139         const signed char *scp = (const signed char *) msg;
 140
 141         pad = (__u32)len | ((__u32)len << 8);
 142         pad |= pad << 16;
 143
 144         val = pad;
 145         if (len > num*4)
 146                 len = num * 4;
 147         for (i = 0; i < len; i++) {
 148                 val = ((int) scp[i]) + (val << 8);
 149                 if ((i % 4) == 3) {
 150                         *buf++ = val;
 151                         val = pad;
 152                         num--;
 153                 }
 154         }
 155         if (--num >= 0)
 156                 *buf++ = val;
 157         while (--num >= 0)
 158                 *buf++ = pad;
 159 }
 160
 161 static void str2hashbuf_unsigned(const char *msg, int len, __u32 *buf, int num)
 162 {
 163         __u32   pad, val;
 164         int     i;
 165         const unsigned char *ucp = (const unsigned char *) msg;
 166
 167         pad = (__u32)len | ((__u32)len << 8);
 168         pad |= pad << 16;
 169
 170         val = pad;
 171         if (len > num*4)
 172                 len = num * 4;
 173         for (i = 0; i < len; i++) {
 174                 val = ((int) ucp[i]) + (val << 8);
 175                 if ((i % 4) == 3) {
 176                         *buf++ = val;
 177                         val = pad;
 178                         num--;
 179                 }
 180         }
 181         if (--num >= 0)
 182                 *buf++ = val;
 183         while (--num >= 0)
 184                 *buf++ = pad;
 185 }
 186
 187 /*
 188  * Returns the hash of a filename.  If len is 0 and name is NULL, then
 189  * this function can be used to test whether or not a hash version is
 190  * supported.
 191  *
 192  * The seed is an 4 longword (32 bits) "secret" which can be used to
 193  * uniquify a hash.  If the seed is all zero's, then some default seed
 194  * may be used.
 195  *
 196  * A particular hash version specifies whether or not the seed is
 197  * represented, and whether or not the returned hash is 32 bits or 64
 198  * bits.  32 bit hashes will return 0 for the minor hash.
 199  */
 200 static int __ext4fs_dirhash(const char *name, int len,
 201                             struct dx_hash_info *hinfo)
 202 {
 203         __u32   hash;
 204         __u32   minor_hash = 0;
 205         const char      *p;
 206         int             i;
 207         __u32           in[8], buf[4];
 208         void            (*str2hashbuf)(const char *, int, __u32 *, int) =
 209                                 str2hashbuf_signed;
 210
 211         /* Initialize the default seed for the hash checksum functions */
 212         buf[0] = 0x67452301;
 213         buf[1] = 0xefcdab89;
 214         buf[2] = 0x98badcfe;
 215         buf[3] = 0x10325476;
 216
 217         /* Check to see if the seed is all zero's */
 218         if (hinfo->seed) {
 219                 for (i = 0; i < 4; i++) {
 220                         if (hinfo->seed[i]) {
 221                                 memcpy(buf, hinfo->seed, sizeof(buf));
 222                                 break;
 223                         }
 224                 }
 225         }
 226
 227         switch (hinfo->hash_version) {
 228         case DX_HASH_LEGACY_UNSIGNED:
 229                 hash = dx_hack_hash_unsigned(name, len);
 230                 break;
 231         case DX_HASH_LEGACY:
 232                 hash = dx_hack_hash_signed(name, len);
 233                 break;
 234         case DX_HASH_HALF_MD4_UNSIGNED:
 235                 str2hashbuf = str2hashbuf_unsigned;
 236                 fallthrough;
 237         case DX_HASH_HALF_MD4:
 238                 p = name;
 239                 while (len > 0) {
 240                         (*str2hashbuf)(p, len, in, 8);
 241                         half_md4_transform(buf, in);
 242                         len -= 32;
 243                         p += 32;
 244                 }
 245                 minor_hash = buf[2];
 246                 hash = buf[1];
 247                 break;
 248         case DX_HASH_TEA_UNSIGNED:
 249                 str2hashbuf = str2hashbuf_unsigned;
 250                 fallthrough;
 251         case DX_HASH_TEA:
 252                 p = name;
 253                 while (len > 0) {
 254                         (*str2hashbuf)(p, len, in, 4);
 255                         TEA_transform(buf, in);
 256                         len -= 16;
 257                         p += 16;
 258                 }
 259                 hash = buf[0];
 260                 minor_hash = buf[1];
 261                 break;
 262         default:
 263                 hinfo->hash = 0;
 264                 return -1;
 265         }
 266         hash = hash & ~1;
 267         if (hash == (EXT4_HTREE_EOF_32BIT << 1))
 268                 hash = (EXT4_HTREE_EOF_32BIT - 1) << 1;
 269         hinfo->hash = hash;
 270         hinfo->minor_hash = minor_hash;
 271         return 0;
 272 }
 273
 274 int ext4fs_dirhash(const struct inode *dir, const char *name, int len,
 275                    struct dx_hash_info *hinfo)
 276 {
 277 #ifdef CONFIG_UNICODE
 278         const struct unicode_map *um = dir->i_sb->s_encoding;
 279         int r, dlen;
 280         unsigned char *buff;
 281         struct qstr qstr = {.name = name, .len = len };
 282
 283         if (len && IS_CASEFOLDED(dir) && um) {
 284                 buff = kzalloc(sizeof(char) * PATH_MAX, GFP_KERNEL);
 285                 if (!buff)
 286                         return -ENOMEM;
 287
 288                 dlen = utf8_casefold(um, &qstr, buff, PATH_MAX);
 289                 if (dlen < 0) {
 290                         kfree(buff);
 291                         goto opaque_seq;
 292                 }
 293
 294                 r = __ext4fs_dirhash(buff, dlen, hinfo);
 295
 296                 kfree(buff);
 297                 return r;
 298         }
 299 opaque_seq:
 300 #endif
 301         return __ext4fs_dirhash(name, len, hinfo);
 302 }