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 u32 TEA_hash_name(const u8 *p, size_t len) |
71 | { |
72 | __u32 in[8], buf[4]; |
73 | |
74 | /* Initialize the default seed for the hash checksum functions */ |
75 | buf[0] = 0x67452301; |
76 | buf[1] = 0xefcdab89; |
77 | buf[2] = 0x98badcfe; |
78 | buf[3] = 0x10325476; |
79 | |
80 | while (1) { |
81 | str2hashbuf(msg: p, len, buf: in, num: 4); |
82 | TEA_transform(buf, in); |
83 | p += 16; |
84 | if (len <= 16) |
85 | break; |
86 | len -= 16; |
87 | } |
88 | return buf[0] & ~F2FS_HASH_COL_BIT; |
89 | } |
90 | |
91 | /* |
92 | * Compute @fname->hash. For all directories, @fname->disk_name must be set. |
93 | * For casefolded directories, @fname->usr_fname must be set, and also |
94 | * @fname->cf_name if the filename is valid Unicode and is not "." or "..". |
95 | */ |
96 | void f2fs_hash_filename(const struct inode *dir, struct f2fs_filename *fname) |
97 | { |
98 | const u8 *name = fname->disk_name.name; |
99 | size_t len = fname->disk_name.len; |
100 | |
101 | WARN_ON_ONCE(!name); |
102 | |
103 | if (is_dot_dotdot(name, len)) { |
104 | fname->hash = 0; |
105 | return; |
106 | } |
107 | |
108 | #if IS_ENABLED(CONFIG_UNICODE) |
109 | if (IS_CASEFOLDED(dir)) { |
110 | /* |
111 | * If the casefolded name is provided, hash it instead of the |
112 | * on-disk name. If the casefolded name is *not* provided, that |
113 | * should only be because the name wasn't valid Unicode or was |
114 | * "." or "..", so fall back to treating the name as an opaque |
115 | * byte sequence. Note that to handle encrypted directories, |
116 | * the fallback must use usr_fname (plaintext) rather than |
117 | * disk_name (ciphertext). |
118 | */ |
119 | WARN_ON_ONCE(!fname->usr_fname->name); |
120 | if (fname->cf_name.name) { |
121 | name = fname->cf_name.name; |
122 | len = fname->cf_name.len; |
123 | } else { |
124 | name = fname->usr_fname->name; |
125 | len = fname->usr_fname->len; |
126 | } |
127 | if (IS_ENCRYPTED(dir)) { |
128 | struct qstr tmp = QSTR_INIT(name, len); |
129 | |
130 | fname->hash = |
131 | cpu_to_le32(fscrypt_fname_siphash(dir, &tmp)); |
132 | return; |
133 | } |
134 | } |
135 | #endif |
136 | fname->hash = cpu_to_le32(TEA_hash_name(name, len)); |
137 | } |
138 | |