ext2_hash.c revision 311231 
1/*-
2 * Copyright (c) 2010, 2013 Zheng Liu <lz@freebsd.org>
3 * Copyright (c) 2012, Vyacheslav Matyushin
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 *    notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 *    notice, this list of conditions and the following disclaimer in the
13 *    documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25 * SUCH DAMAGE.
26 *
27 * $FreeBSD: stable/11/sys/fs/ext2fs/ext2_hash.c 311231 2017-01-04 02:42:17Z pfg $
28 */
29
30/*
31 * The following notice applies to the code in ext2_half_md4():
32 *
33 * Copyright (C) 1990-2, RSA Data Security, Inc. All rights reserved.
34 *
35 * License to copy and use this software is granted provided that it
36 * is identified as the "RSA Data Security, Inc. MD4 Message-Digest
37 * Algorithm" in all material mentioning or referencing this software
38 * or this function.
39 *
40 * License is also granted to make and use derivative works provided
41 * that such works are identified as "derived from the RSA Data
42 * Security, Inc. MD4 Message-Digest Algorithm" in all material
43 * mentioning or referencing the derived work.
44 *
45 * RSA Data Security, Inc. makes no representations concerning either
46 * the merchantability of this software or the suitability of this
47 * software for any particular purpose. It is provided "as is"
48 * without express or implied warranty of any kind.
49 *
50 * These notices must be retained in any copies of any part of this
51 * documentation and/or software.
52 */
53
54#include <sys/param.h>
55#include <sys/systm.h>
56#include <sys/conf.h>
57#include <sys/vnode.h>
58#include <sys/stat.h>
59#include <sys/mount.h>
60
61#include <fs/ext2fs/htree.h>
62#include <fs/ext2fs/inode.h>
63#include <fs/ext2fs/ext2_mount.h>
64#include <fs/ext2fs/ext2_extern.h>
65
66/* F, G, and H are MD4 functions */
67#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
68#define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z)))
69#define H(x, y, z) ((x) ^ (y) ^ (z))
70
71/* ROTATE_LEFT rotates x left n bits */
72#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32 - (n))))
73
74/*
75 * FF, GG, and HH are transformations for rounds 1, 2, and 3.
76 * Rotation is separated from addition to prevent recomputation.
77 */
78#define FF(a, b, c, d, x, s) { \
79	(a) += F ((b), (c), (d)) + (x); \
80	(a) = ROTATE_LEFT ((a), (s)); \
81}
82
83#define GG(a, b, c, d, x, s) { \
84	(a) += G ((b), (c), (d)) + (x) + (uint32_t)0x5A827999; \
85	(a) = ROTATE_LEFT ((a), (s)); \
86}
87
88#define HH(a, b, c, d, x, s) { \
89	(a) += H ((b), (c), (d)) + (x) + (uint32_t)0x6ED9EBA1; \
90	(a) = ROTATE_LEFT ((a), (s)); \
91}
92
93/*
94 * MD4 basic transformation.  It transforms state based on block.
95 *
96 * This is a half md4 algorithm since Linux uses this algorithm for dir
97 * index.  This function is derived from the RSA Data Security, Inc. MD4
98 * Message-Digest Algorithm and was modified as necessary.
99 *
100 * The return value of this function is uint32_t in Linux, but actually we don't
101 * need to check this value, so in our version this function doesn't return any
102 * value.
103 */
104static void
105ext2_half_md4(uint32_t hash[4], uint32_t data[8])
106{
107	uint32_t a = hash[0], b = hash[1], c = hash[2], d = hash[3];
108
109	/* Round 1 */
110	FF(a, b, c, d, data[0],  3);
111	FF(d, a, b, c, data[1],  7);
112	FF(c, d, a, b, data[2], 11);
113	FF(b, c, d, a, data[3], 19);
114	FF(a, b, c, d, data[4],  3);
115	FF(d, a, b, c, data[5],  7);
116	FF(c, d, a, b, data[6], 11);
117	FF(b, c, d, a, data[7], 19);
118
119	/* Round 2 */
120	GG(a, b, c, d, data[1],  3);
121	GG(d, a, b, c, data[3],  5);
122	GG(c, d, a, b, data[5],  9);
123	GG(b, c, d, a, data[7], 13);
124	GG(a, b, c, d, data[0],  3);
125	GG(d, a, b, c, data[2],  5);
126	GG(c, d, a, b, data[4],  9);
127	GG(b, c, d, a, data[6], 13);
128
129	/* Round 3 */
130	HH(a, b, c, d, data[3],  3);
131	HH(d, a, b, c, data[7],  9);
132	HH(c, d, a, b, data[2], 11);
133	HH(b, c, d, a, data[6], 15);
134	HH(a, b, c, d, data[1],  3);
135	HH(d, a, b, c, data[5],  9);
136	HH(c, d, a, b, data[0], 11);
137	HH(b, c, d, a, data[4], 15);
138
139	hash[0] += a;
140	hash[1] += b;
141	hash[2] += c;
142	hash[3] += d;
143}
144
145/*
146 * Tiny Encryption Algorithm.
147 */
148static void
149ext2_tea(uint32_t hash[4], uint32_t data[8])
150{
151	uint32_t tea_delta = 0x9E3779B9;
152	uint32_t sum;
153	uint32_t x = hash[0], y = hash[1];
154	int n = 16;
155	int i = 1;
156
157	while (n-- > 0) {
158		sum = i * tea_delta;
159		x += ((y << 4) + data[0]) ^ (y + sum) ^ ((y >> 5) + data[1]);
160		y += ((x << 4) + data[2]) ^ (x + sum) ^ ((x >> 5) + data[3]);
161		i++;
162	}
163
164	hash[0] += x;
165	hash[1] += y;
166}
167
168static uint32_t
169ext2_legacy_hash(const char *name, int len, int unsigned_char)
170{
171	uint32_t h0, h1 = 0x12A3FE2D, h2 = 0x37ABE8F9;
172	uint32_t multi = 0x6D22F5;
173	const unsigned char *uname = (const unsigned char *)name;
174	const signed char *sname = (const signed char *)name;
175	int val, i;
176
177	for (i = 0; i < len; i++) {
178		if (unsigned_char)
179			val = (u_int)*uname++;
180		else
181			val = (int)*sname++;
182
183		h0 = h2 + (h1 ^ (val * multi));
184		if (h0 & 0x80000000)
185			h0 -= 0x7FFFFFFF;
186		h2 = h1;
187		h1 = h0;
188	}
189
190	return (h1 << 1);
191}
192
193static void
194ext2_prep_hashbuf(const char *src, int slen, uint32_t *dst, int dlen,
195    int unsigned_char)
196{
197	uint32_t padding = slen | (slen << 8) | (slen << 16) | (slen << 24);
198	uint32_t buf_val;
199	const unsigned char *ubuf = (const unsigned char *)src;
200	const signed char *sbuf = (const signed char *)src;
201	int len, i;
202	int buf_byte;
203
204	if (slen > dlen)
205		len = dlen;
206	else
207		len = slen;
208
209	buf_val = padding;
210
211	for (i = 0; i < len; i++) {
212		if (unsigned_char)
213			buf_byte = (u_int)ubuf[i];
214		else
215			buf_byte = (int)sbuf[i];
216
217		if ((i % 4) == 0)
218			buf_val = padding;
219
220		buf_val <<= 8;
221		buf_val += buf_byte;
222
223		if ((i % 4) == 3) {
224			*dst++ = buf_val;
225			dlen -= sizeof(uint32_t);
226			buf_val = padding;
227		}
228	}
229
230	dlen -= sizeof(uint32_t);
231	if (dlen >= 0)
232		*dst++ = buf_val;
233
234	dlen -= sizeof(uint32_t);
235	while (dlen >= 0) {
236		*dst++ = padding;
237		dlen -= sizeof(uint32_t);
238	}
239}
240
241int
242ext2_htree_hash(const char *name, int len,
243    uint32_t *hash_seed, int hash_version,
244    uint32_t *hash_major, uint32_t *hash_minor)
245{
246	uint32_t hash[4];
247	uint32_t data[8];
248	uint32_t major = 0, minor = 0;
249	int unsigned_char = 0;
250
251	if (!name || !hash_major)
252		return (-1);
253
254	if (len < 1 || len > 255)
255		goto error;
256
257	hash[0] = 0x67452301;
258	hash[1] = 0xEFCDAB89;
259	hash[2] = 0x98BADCFE;
260	hash[3] = 0x10325476;
261
262	if (hash_seed)
263		memcpy(hash, hash_seed, sizeof(hash));
264
265	switch (hash_version) {
266	case EXT2_HTREE_TEA_UNSIGNED:
267		unsigned_char = 1;
268		/* FALLTHROUGH */
269	case EXT2_HTREE_TEA:
270		while (len > 0) {
271			ext2_prep_hashbuf(name, len, data, 16, unsigned_char);
272			ext2_tea(hash, data);
273			len -= 16;
274			name += 16;
275		}
276		major = hash[0];
277		minor = hash[1];
278		break;
279	case EXT2_HTREE_LEGACY_UNSIGNED:
280		unsigned_char = 1;
281		/* FALLTHROUGH */
282	case EXT2_HTREE_LEGACY:
283		major = ext2_legacy_hash(name, len, unsigned_char);
284		break;
285	case EXT2_HTREE_HALF_MD4_UNSIGNED:
286		unsigned_char = 1;
287		/* FALLTHROUGH */
288	case EXT2_HTREE_HALF_MD4:
289		while (len > 0) {
290			ext2_prep_hashbuf(name, len, data, 32, unsigned_char);
291			ext2_half_md4(hash, data);
292			len -= 32;
293			name += 32;
294		}
295		major = hash[1];
296		minor = hash[2];
297		break;
298	default:
299		goto error;
300	}
301
302	major &= ~1;
303	if (major == (EXT2_HTREE_EOF << 1))
304		major = (EXT2_HTREE_EOF - 1) << 1;
305	*hash_major = major;
306	if (hash_minor)
307		*hash_minor = minor;
308
309	return (0);
310
311error:
312	*hash_major = 0;
313	if (hash_minor)
314		*hash_minor = 0;
315	return (-1);
316}
317