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 } 141