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