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(p, len, in, 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. 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, so fall 114 * back to treating the name as an opaque byte sequence. Note 115 * that to handle encrypted directories, the fallback must use 116 * usr_fname (plaintext) rather than disk_name (ciphertext). 117 */ 118 WARN_ON_ONCE(!fname->usr_fname->name); 119 if (fname->cf_name.name) { 120 name = fname->cf_name.name; 121 len = fname->cf_name.len; 122 } else { 123 name = fname->usr_fname->name; 124 len = fname->usr_fname->len; 125 } 126 if (IS_ENCRYPTED(dir)) { 127 struct qstr tmp = QSTR_INIT(name, len); 128 129 fname->hash = 130 cpu_to_le32(fscrypt_fname_siphash(dir, &tmp)); 131 return; 132 } 133 } 134 #endif 135 fname->hash = cpu_to_le32(TEA_hash_name(name, len)); 136 } 137