fs/f2fs/hash.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * fs/f2fs/hash.c
   4  *
   5  * Copyright (c) 2012 Samsung Electronics Co., Ltd.
   6  *             http://www.samsung.com/
   7  *
   8  * Portions of this code from linux/fs/ext3/hash.c
   9  *
  10  * Copyright (C) 2002 by Theodore Ts'o
  11  */
  12 #include <linux/types.h>
  13 #include <linux/fs.h>
  14 #include <linux/f2fs_fs.h>
  15 #include <linux/cryptohash.h>
  16 #include <linux/pagemap.h>
  17 #include <linux/unicode.h>
  18
  19 #include "f2fs.h"
  20
  21 /*
  22  * Hashing code copied from ext3
  23  */
  24 #define DELTA 0x9E3779B9
  25
  26 static void TEA_transform(unsigned int buf[4], unsigned int const in[])
  27 {
  28         __u32 sum = 0;
  29         __u32 b0 = buf[0], b1 = buf[1];
  30         __u32 a = in[0], b = in[1], c = in[2], d = in[3];
  31         int n = 16;
  32
  33         do {
  34                 sum += DELTA;
  35                 b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b);
  36                 b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d);
  37         } while (--n);
  38
  39         buf[0] += b0;
  40         buf[1] += b1;
  41 }
  42
  43 static void str2hashbuf(const unsigned char *msg, size_t len,
  44                                 unsigned int *buf, int num)
  45 {
  46         unsigned pad, val;
  47         int i;
  48
  49         pad = (__u32)len | ((__u32)len << 8);
  50         pad |= pad << 16;
  51
  52         val = pad;
  53         if (len > num * 4)
  54                 len = num * 4;
  55         for (i = 0; i < len; i++) {
  56                 if ((i % 4) == 0)
  57                         val = pad;
  58                 val = msg[i] + (val << 8);
  59                 if ((i % 4) == 3) {
  60                         *buf++ = val;
  61                         val = pad;
  62                         num--;
  63                 }
  64         }
  65         if (--num >= 0)
  66                 *buf++ = val;
  67         while (--num >= 0)
  68                 *buf++ = pad;
  69 }
  70
  71 static f2fs_hash_t __f2fs_dentry_hash(const struct qstr *name_info,
  72                                 struct fscrypt_name *fname)
  73 {
  74         __u32 hash;
  75         f2fs_hash_t f2fs_hash;
  76         const unsigned char *p;
  77         __u32 in[8], buf[4];
  78         const unsigned char *name = name_info->name;
  79         size_t len = name_info->len;
  80
  81         /* encrypted bigname case */
  82         if (fname && !fname->disk_name.name)
  83                 return cpu_to_le32(fname->hash);
  84
  85         if (is_dot_dotdot(name_info))
  86                 return 0;
  87
  88         /* Initialize the default seed for the hash checksum functions */
  89         buf[0] = 0x67452301;
  90         buf[1] = 0xefcdab89;
  91         buf[2] = 0x98badcfe;
  92         buf[3] = 0x10325476;
  93
  94         p = name;
  95         while (1) {
  96                 str2hashbuf(p, len, in, 4);
  97                 TEA_transform(buf, in);
  98                 p += 16;
  99                 if (len <= 16)
 100                         break;
 101                 len -= 16;
 102         }
 103         hash = buf[0];
 104         f2fs_hash = cpu_to_le32(hash & ~F2FS_HASH_COL_BIT);
 105         return f2fs_hash;
 106 }
 107
 108 f2fs_hash_t f2fs_dentry_hash(const struct inode *dir,
 109                 const struct qstr *name_info, struct fscrypt_name *fname)
 110 {
 111 #ifdef CONFIG_UNICODE
 112         struct f2fs_sb_info *sbi = F2FS_SB(dir->i_sb);
 113         const struct unicode_map *um = sbi->s_encoding;
 114         int r, dlen;
 115         unsigned char *buff;
 116         struct qstr folded;
 117
 118         if (!name_info->len || !IS_CASEFOLDED(dir))
 119                 goto opaque_seq;
 120
 121         buff = f2fs_kzalloc(sbi, sizeof(char) * PATH_MAX, GFP_KERNEL);
 122         if (!buff)
 123                 return -ENOMEM;
 124
 125         dlen = utf8_casefold(um, name_info, buff, PATH_MAX);
 126         if (dlen < 0) {
 127                 kvfree(buff);
 128                 goto opaque_seq;
 129         }
 130         folded.name = buff;
 131         folded.len = dlen;
 132         r = __f2fs_dentry_hash(&folded, fname);
 133
 134         kvfree(buff);
 135         return r;
 136
 137 opaque_seq:
 138 #endif
 139         return __f2fs_dentry_hash(name_info, fname);
 140 }