aboutsummaryrefslogtreecommitdiff
path: root/fs/f2fs/hash.c
blob: e3beac546c63a96acb1c2e863624238d85299ab1 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
// SPDX-License-Identifier: GPL-2.0
/*
 * fs/f2fs/hash.c
 *
 * Copyright (c) 2012 Samsung Electronics Co., Ltd.
 *             http://www.samsung.com/
 *
 * Portions of this code from linux/fs/ext3/hash.c
 *
 * Copyright (C) 2002 by Theodore Ts'o
 */
#include <linux/types.h>
#include <linux/fs.h>
#include <linux/f2fs_fs.h>
#include <linux/pagemap.h>
#include <linux/unicode.h>

#include "f2fs.h"

/*
 * Hashing code copied from ext3
 */
#define DELTA 0x9E3779B9

static void TEA_transform(unsigned int buf[4], unsigned int const in[])
{
	__u32 sum = 0;
	__u32 b0 = buf[0], b1 = buf[1];
	__u32 a = in[0], b = in[1], c = in[2], d = in[3];
	int n = 16;

	do {
		sum += DELTA;
		b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b);
		b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d);
	} while (--n);

	buf[0] += b0;
	buf[1] += b1;
}

static void str2hashbuf(const unsigned char *msg, size_t len,
				unsigned int *buf, int num)
{
	unsigned pad, val;
	int i;

	pad = (__u32)len | ((__u32)len << 8);
	pad |= pad << 16;

	val = pad;
	if (len > num * 4)
		len = num * 4;
	for (i = 0; i < len; i++) {
		if ((i % 4) == 0)
			val = pad;
		val = msg[i] + (val << 8);
		if ((i % 4) == 3) {
			*buf++ = val;
			val = pad;
			num--;
		}
	}
	if (--num >= 0)
		*buf++ = val;
	while (--num >= 0)
		*buf++ = pad;
}

static u32 TEA_hash_name(const u8 *p, size_t len)
{
	__u32 in[8], buf[4];

	/* Initialize the default seed for the hash checksum functions */
	buf[0] = 0x67452301;
	buf[1] = 0xefcdab89;
	buf[2] = 0x98badcfe;
	buf[3] = 0x10325476;

	while (1) {
		str2hashbuf(p, len, in, 4);
		TEA_transform(buf, in);
		p += 16;
		if (len <= 16)
			break;
		len -= 16;
	}
	return buf[0] & ~F2FS_HASH_COL_BIT;
}

/*
 * Compute @fname->hash.  For all directories, @fname->disk_name must be set.
 * For casefolded directories, @fname->usr_fname must be set, and also
 * @fname->cf_name if the filename is valid Unicode.
 */
void f2fs_hash_filename(const struct inode *dir, struct f2fs_filename *fname)
{
	const u8 *name = fname->disk_name.name;
	size_t len = fname->disk_name.len;

	WARN_ON_ONCE(!name);

	if (is_dot_dotdot(name, len)) {
		fname->hash = 0;
		return;
	}

#ifdef CONFIG_UNICODE
	if (IS_CASEFOLDED(dir)) {
		/*
		 * If the casefolded name is provided, hash it instead of the
		 * on-disk name.  If the casefolded name is *not* provided, that
		 * should only be because the name wasn't valid Unicode, so fall
		 * back to treating the name as an opaque byte sequence.  Note
		 * that to handle encrypted directories, the fallback must use
		 * usr_fname (plaintext) rather than disk_name (ciphertext).
		 */
		WARN_ON_ONCE(!fname->usr_fname->name);
		if (fname->cf_name.name) {
			name = fname->cf_name.name;
			len = fname->cf_name.len;
		} else {
			name = fname->usr_fname->name;
			len = fname->usr_fname->len;
		}
		if (IS_ENCRYPTED(dir)) {
			struct qstr tmp = QSTR_INIT(name, len);

			fname->hash =
				cpu_to_le32(fscrypt_fname_siphash(dir, &tmp));
			return;
		}
	}
#endif
	fname->hash = cpu_to_le32(TEA_hash_name(name, len));
}