linux/fs/ext4/hash.c
<<
>>
Prefs
   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
  16static 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 */
  53static __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 */
 103static __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
 119static __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
 135static 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
 161static 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 */
 200static 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
 274int 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        }
 299opaque_seq:
 300#endif
 301        return __ext4fs_dirhash(name, len, hinfo);
 302}
 303