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