138 lines · c
1// SPDX-License-Identifier: GPL-2.02/*3 * fs/f2fs/hash.c4 *5 * Copyright (c) 2012 Samsung Electronics Co., Ltd.6 * http://www.samsung.com/7 *8 * Portions of this code from linux/fs/ext3/hash.c9 *10 * Copyright (C) 2002 by Theodore Ts'o11 */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 ext322 */23#define DELTA 0x9E3779B924 25static 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 42static 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 70static 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 also94 * @fname->cf_name if the filename is valid Unicode and is not "." or "..".95 */96void 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 the112 * on-disk name. If the casefolded name is *not* provided, that113 * should only be because the name wasn't valid Unicode or was114 * "." or "..", so fall back to treating the name as an opaque115 * byte sequence. Note that to handle encrypted directories,116 * the fallback must use usr_fname (plaintext) rather than117 * 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#endif136 fname->hash = cpu_to_le32(TEA_hash_name(name, len));137}138