LCOV - code coverage report
Current view: top level - fs/ext4 - hash.c (source / functions) Hit Total Coverage
Test: landlock.info Lines: 85 158 53.8 %
Date: 2021-04-22 12:43:58 Functions: 4 8 50.0 %

          Line data    Source code
       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           0 : static void TEA_transform(__u32 buf[4], __u32 const in[])
      17             : {
      18           0 :         __u32   sum = 0;
      19           0 :         __u32   b0 = buf[0], b1 = buf[1];
      20           0 :         __u32   a = in[0], b = in[1], c = in[2], d = in[3];
      21           0 :         int     n = 16;
      22             : 
      23           0 :         do {
      24           0 :                 sum += DELTA;
      25           0 :                 b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b);
      26           0 :                 b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d);
      27           0 :         } while (--n);
      28             : 
      29           0 :         buf[0] += b0;
      30           0 :         buf[1] += b1;
      31           0 : }
      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       11142 : static __u32 half_md4_transform(__u32 buf[4], __u32 const in[8])
      54             : {
      55       11142 :         __u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3];
      56             : 
      57             :         /* Round 1 */
      58       11142 :         ROUND(F, a, b, c, d, in[0] + K1,  3);
      59       11142 :         ROUND(F, d, a, b, c, in[1] + K1,  7);
      60       11142 :         ROUND(F, c, d, a, b, in[2] + K1, 11);
      61       11142 :         ROUND(F, b, c, d, a, in[3] + K1, 19);
      62       11142 :         ROUND(F, a, b, c, d, in[4] + K1,  3);
      63       11142 :         ROUND(F, d, a, b, c, in[5] + K1,  7);
      64       11142 :         ROUND(F, c, d, a, b, in[6] + K1, 11);
      65       11142 :         ROUND(F, b, c, d, a, in[7] + K1, 19);
      66             : 
      67             :         /* Round 2 */
      68       11142 :         ROUND(G, a, b, c, d, in[1] + K2,  3);
      69       11142 :         ROUND(G, d, a, b, c, in[3] + K2,  5);
      70       11142 :         ROUND(G, c, d, a, b, in[5] + K2,  9);
      71       11142 :         ROUND(G, b, c, d, a, in[7] + K2, 13);
      72       11142 :         ROUND(G, a, b, c, d, in[0] + K2,  3);
      73       11142 :         ROUND(G, d, a, b, c, in[2] + K2,  5);
      74       11142 :         ROUND(G, c, d, a, b, in[4] + K2,  9);
      75       11142 :         ROUND(G, b, c, d, a, in[6] + K2, 13);
      76             : 
      77             :         /* Round 3 */
      78       11142 :         ROUND(H, a, b, c, d, in[3] + K3,  3);
      79       11142 :         ROUND(H, d, a, b, c, in[7] + K3,  9);
      80       11142 :         ROUND(H, c, d, a, b, in[2] + K3, 11);
      81       11142 :         ROUND(H, b, c, d, a, in[6] + K3, 15);
      82       11142 :         ROUND(H, a, b, c, d, in[1] + K3,  3);
      83       11142 :         ROUND(H, d, a, b, c, in[5] + K3,  9);
      84       11142 :         ROUND(H, c, d, a, b, in[0] + K3, 11);
      85       11142 :         ROUND(H, b, c, d, a, in[4] + K3, 15);
      86             : 
      87       11142 :         buf[0] += a;
      88       11142 :         buf[1] += b;
      89       11142 :         buf[2] += c;
      90       11142 :         buf[3] += d;
      91             : 
      92       11142 :         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           0 : static __u32 dx_hack_hash_unsigned(const char *name, int len)
     104             : {
     105           0 :         __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
     106           0 :         const unsigned char *ucp = (const unsigned char *) name;
     107             : 
     108           0 :         while (len--) {
     109           0 :                 hash = hash1 + (hash0 ^ (((int) *ucp++) * 7152373));
     110             : 
     111           0 :                 if (hash & 0x80000000)
     112           0 :                         hash -= 0x7fffffff;
     113             :                 hash1 = hash0;
     114             :                 hash0 = hash;
     115             :         }
     116           0 :         return hash0 << 1;
     117             : }
     118             : 
     119           0 : static __u32 dx_hack_hash_signed(const char *name, int len)
     120             : {
     121           0 :         __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
     122           0 :         const signed char *scp = (const signed char *) name;
     123             : 
     124           0 :         while (len--) {
     125           0 :                 hash = hash1 + (hash0 ^ (((int) *scp++) * 7152373));
     126             : 
     127           0 :                 if (hash & 0x80000000)
     128           0 :                         hash -= 0x7fffffff;
     129             :                 hash1 = hash0;
     130             :                 hash0 = hash;
     131             :         }
     132           0 :         return hash0 << 1;
     133             : }
     134             : 
     135       11142 : static void str2hashbuf_signed(const char *msg, int len, __u32 *buf, int num)
     136             : {
     137       11142 :         __u32   pad, val;
     138       11142 :         int     i;
     139       11142 :         const signed char *scp = (const signed char *) msg;
     140             : 
     141       11142 :         pad = (__u32)len | ((__u32)len << 8);
     142       11142 :         pad |= pad << 16;
     143             : 
     144       11142 :         val = pad;
     145       11142 :         if (len > num*4)
     146             :                 len = num * 4;
     147      168266 :         for (i = 0; i < len; i++) {
     148      157124 :                 val = ((int) scp[i]) + (val << 8);
     149      157124 :                 if ((i % 4) == 3) {
     150       35838 :                         *buf++ = val;
     151       35838 :                         val = pad;
     152       35838 :                         num--;
     153             :                 }
     154             :         }
     155       11142 :         if (--num >= 0)
     156       10013 :                 *buf++ = val;
     157       54427 :         while (--num >= 0)
     158       43285 :                 *buf++ = pad;
     159       11142 : }
     160             : 
     161           0 : static void str2hashbuf_unsigned(const char *msg, int len, __u32 *buf, int num)
     162             : {
     163           0 :         __u32   pad, val;
     164           0 :         int     i;
     165           0 :         const unsigned char *ucp = (const unsigned char *) msg;
     166             : 
     167           0 :         pad = (__u32)len | ((__u32)len << 8);
     168           0 :         pad |= pad << 16;
     169             : 
     170           0 :         val = pad;
     171           0 :         if (len > num*4)
     172             :                 len = num * 4;
     173           0 :         for (i = 0; i < len; i++) {
     174           0 :                 val = ((int) ucp[i]) + (val << 8);
     175           0 :                 if ((i % 4) == 3) {
     176           0 :                         *buf++ = val;
     177           0 :                         val = pad;
     178           0 :                         num--;
     179             :                 }
     180             :         }
     181           0 :         if (--num >= 0)
     182           0 :                 *buf++ = val;
     183           0 :         while (--num >= 0)
     184           0 :                 *buf++ = pad;
     185           0 : }
     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       10052 : static int __ext4fs_dirhash(const char *name, int len,
     201             :                             struct dx_hash_info *hinfo)
     202             : {
     203       10052 :         __u32   hash;
     204       10052 :         __u32   minor_hash = 0;
     205       10052 :         const char      *p;
     206       10052 :         int             i;
     207       10052 :         __u32           in[8], buf[4];
     208       10052 :         void            (*str2hashbuf)(const char *, int, __u32 *, int) =
     209             :                                 str2hashbuf_signed;
     210             : 
     211             :         /* Initialize the default seed for the hash checksum functions */
     212       10052 :         buf[0] = 0x67452301;
     213       10052 :         buf[1] = 0xefcdab89;
     214       10052 :         buf[2] = 0x98badcfe;
     215       10052 :         buf[3] = 0x10325476;
     216             : 
     217             :         /* Check to see if the seed is all zero's */
     218       10052 :         if (hinfo->seed) {
     219       10052 :                 for (i = 0; i < 4; i++) {
     220       10052 :                         if (hinfo->seed[i]) {
     221       10052 :                                 memcpy(buf, hinfo->seed, sizeof(buf));
     222       10052 :                                 break;
     223             :                         }
     224             :                 }
     225             :         }
     226             : 
     227       10052 :         switch (hinfo->hash_version) {
     228           0 :         case DX_HASH_LEGACY_UNSIGNED:
     229           0 :                 hash = dx_hack_hash_unsigned(name, len);
     230           0 :                 break;
     231           0 :         case DX_HASH_LEGACY:
     232           0 :                 hash = dx_hack_hash_signed(name, len);
     233           0 :                 break;
     234           0 :         case DX_HASH_HALF_MD4_UNSIGNED:
     235           0 :                 str2hashbuf = str2hashbuf_unsigned;
     236       10052 :                 fallthrough;
     237       10052 :         case DX_HASH_HALF_MD4:
     238       10052 :                 p = name;
     239       21194 :                 while (len > 0) {
     240       11142 :                         (*str2hashbuf)(p, len, in, 8);
     241       11142 :                         half_md4_transform(buf, in);
     242       11142 :                         len -= 32;
     243       11142 :                         p += 32;
     244             :                 }
     245       10052 :                 minor_hash = buf[2];
     246       10052 :                 hash = buf[1];
     247       10052 :                 break;
     248           0 :         case DX_HASH_TEA_UNSIGNED:
     249           0 :                 str2hashbuf = str2hashbuf_unsigned;
     250           0 :                 fallthrough;
     251           0 :         case DX_HASH_TEA:
     252           0 :                 p = name;
     253           0 :                 while (len > 0) {
     254           0 :                         (*str2hashbuf)(p, len, in, 4);
     255           0 :                         TEA_transform(buf, in);
     256           0 :                         len -= 16;
     257           0 :                         p += 16;
     258             :                 }
     259           0 :                 hash = buf[0];
     260           0 :                 minor_hash = buf[1];
     261           0 :                 break;
     262           0 :         default:
     263           0 :                 hinfo->hash = 0;
     264           0 :                 return -1;
     265             :         }
     266       10052 :         hash = hash & ~1;
     267       10052 :         if (hash == (EXT4_HTREE_EOF_32BIT << 1))
     268           0 :                 hash = (EXT4_HTREE_EOF_32BIT - 1) << 1;
     269       10052 :         hinfo->hash = hash;
     270       10052 :         hinfo->minor_hash = minor_hash;
     271       10052 :         return 0;
     272             : }
     273             : 
     274       10052 : 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       10052 :         return __ext4fs_dirhash(name, len, hinfo);
     302             : }

Generated by: LCOV version 1.14