2 * Copyright (c) 2013 Grzegorz Kostka (kostka.grzegorz@gmail.com)
\r
5 * Copyright (c) 2010, 2013 Zheng Liu <lz@freebsd.org>
\r
6 * Copyright (c) 2012, Vyacheslav Matyushin
\r
7 * All rights reserved.
\r
9 * Redistribution and use in source and binary forms, with or without
\r
10 * modification, are permitted provided that the following conditions
\r
12 * 1. Redistributions of source code must retain the above copyright
\r
13 * notice, this list of conditions and the following disclaimer.
\r
14 * 2. Redistributions in binary form must reproduce the above copyright
\r
15 * notice, this list of conditions and the following disclaimer in the
\r
16 * documentation and/or other materials provided with the distribution.
\r
18 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
\r
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
\r
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
\r
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
\r
22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
\r
23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
\r
24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
\r
25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
\r
26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
\r
27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
\r
33 * The following notice applies to the code in ext2_half_md4():
\r
35 * Copyright (C) 1990-2, RSA Data Security, Inc. All rights reserved.
\r
37 * License to copy and use this software is granted provided that it
\r
38 * is identified as the "RSA Data Security, Inc. MD4 Message-Digest
\r
39 * Algorithm" in all material mentioning or referencing this software
\r
42 * License is also granted to make and use derivative works provided
\r
43 * that such works are identified as "derived from the RSA Data
\r
44 * Security, Inc. MD4 Message-Digest Algorithm" in all material
\r
45 * mentioning or referencing the derived work.
\r
47 * RSA Data Security, Inc. makes no representations concerning either
\r
48 * the merchantability of this software or the suitability of this
\r
49 * software for any particular purpose. It is provided "as is"
\r
50 * without express or implied warranty of any kind.
\r
52 * These notices must be retained in any copies of any part of this
\r
53 * documentation and/or software.
\r
56 /** @addtogroup lwext4
\r
61 * @brief Directory indexing hash functions.
\r
64 #include <ext4_config.h>
\r
65 #include <ext4_types.h>
\r
67 #include <ext4_errno.h>
\r
69 /* F, G, and H are MD4 functions */
\r
70 #define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
\r
71 #define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z)))
\r
72 #define H(x, y, z) ((x) ^ (y) ^ (z))
\r
74 /* ROTATE_LEFT rotates x left n bits */
\r
75 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32 - (n))))
\r
78 * FF, GG, and HH are transformations for rounds 1, 2, and 3.
\r
79 * Rotation is separated from addition to prevent recomputation.
\r
81 #define FF(a, b, c, d, x, s) { \
\r
82 (a) += F ((b), (c), (d)) + (x); \
\r
83 (a) = ROTATE_LEFT ((a), (s)); \
\r
86 #define GG(a, b, c, d, x, s) { \
\r
87 (a) += G ((b), (c), (d)) + (x) + (uint32_t)0x5A827999; \
\r
88 (a) = ROTATE_LEFT ((a), (s)); \
\r
91 #define HH(a, b, c, d, x, s) { \
\r
92 (a) += H ((b), (c), (d)) + (x) + (uint32_t)0x6ED9EBA1; \
\r
93 (a) = ROTATE_LEFT ((a), (s)); \
\r
97 * MD4 basic transformation. It transforms state based on block.
\r
99 * This is a half md4 algorithm since Linux uses this algorithm for dir
\r
100 * index. This function is derived from the RSA Data Security, Inc. MD4
\r
101 * Message-Digest Algorithm and was modified as necessary.
\r
103 * The return value of this function is uint32_t in Linux, but actually we don't
\r
104 * need to check this value, so in our version this function doesn't return any
\r
108 ext2_half_md4(uint32_t hash[4], uint32_t data[8])
\r
110 uint32_t a = hash[0], b = hash[1], c = hash[2], d = hash[3];
\r
113 FF(a, b, c, d, data[0], 3);
\r
114 FF(d, a, b, c, data[1], 7);
\r
115 FF(c, d, a, b, data[2], 11);
\r
116 FF(b, c, d, a, data[3], 19);
\r
117 FF(a, b, c, d, data[4], 3);
\r
118 FF(d, a, b, c, data[5], 7);
\r
119 FF(c, d, a, b, data[6], 11);
\r
120 FF(b, c, d, a, data[7], 19);
\r
123 GG(a, b, c, d, data[1], 3);
\r
124 GG(d, a, b, c, data[3], 5);
\r
125 GG(c, d, a, b, data[5], 9);
\r
126 GG(b, c, d, a, data[7], 13);
\r
127 GG(a, b, c, d, data[0], 3);
\r
128 GG(d, a, b, c, data[2], 5);
\r
129 GG(c, d, a, b, data[4], 9);
\r
130 GG(b, c, d, a, data[6], 13);
\r
133 HH(a, b, c, d, data[3], 3);
\r
134 HH(d, a, b, c, data[7], 9);
\r
135 HH(c, d, a, b, data[2], 11);
\r
136 HH(b, c, d, a, data[6], 15);
\r
137 HH(a, b, c, d, data[1], 3);
\r
138 HH(d, a, b, c, data[5], 9);
\r
139 HH(c, d, a, b, data[0], 11);
\r
140 HH(b, c, d, a, data[4], 15);
\r
149 * Tiny Encryption Algorithm.
\r
152 ext2_tea(uint32_t hash[4], uint32_t data[8])
\r
154 uint32_t tea_delta = 0x9E3779B9;
\r
156 uint32_t x = hash[0], y = hash[1];
\r
161 sum = i * tea_delta;
\r
162 x += ((y << 4) + data[0]) ^ (y + sum) ^ ((y >> 5) + data[1]);
\r
163 y += ((x << 4) + data[2]) ^ (x + sum) ^ ((x >> 5) + data[3]);
\r
172 ext2_legacy_hash(const char *name, int len, int unsigned_char)
\r
174 uint32_t h0, h1 = 0x12A3FE2D, h2 = 0x37ABE8F9;
\r
175 uint32_t multi = 0x6D22F5;
\r
176 const unsigned char *uname = (const unsigned char *)name;
\r
177 const signed char *sname = (const signed char *)name;
\r
180 for (i = 0; i < len; i++) {
\r
182 val = (unsigned int)*uname++;
\r
184 val = (int)*sname++;
\r
186 h0 = h2 + (h1 ^ (val * multi));
\r
187 if (h0 & 0x80000000)
\r
197 ext2_prep_hashbuf(const char *src, uint32_t slen, uint32_t *dst, int dlen,
\r
200 uint32_t padding = slen | (slen << 8) | (slen << 16) | (slen << 24);
\r
204 const unsigned char *ubuf = (const unsigned char *)src;
\r
205 const signed char *sbuf = (const signed char *)src;
\r
207 if (slen > (uint32_t)dlen)
\r
214 for (i = 0; i < len; i++) {
\r
216 buf_byte = (unsigned int)ubuf[i];
\r
218 buf_byte = (int)sbuf[i];
\r
224 buf_val += buf_byte;
\r
226 if ((i % 4) == 3) {
\r
228 dlen -= sizeof(uint32_t);
\r
233 dlen -= sizeof(uint32_t);
\r
237 dlen -= sizeof(uint32_t);
\r
238 while (dlen >= 0) {
\r
240 dlen -= sizeof(uint32_t);
\r
245 ext2_htree_hash(const char *name, int len,
\r
246 const uint32_t *hash_seed, int hash_version,
\r
247 uint32_t *hash_major, uint32_t *hash_minor)
\r
251 uint32_t major = 0, minor = 0;
\r
252 int unsigned_char = 0;
\r
254 if (!name || !hash_major)
\r
257 if (len < 1 || len > 255)
\r
260 hash[0] = 0x67452301;
\r
261 hash[1] = 0xEFCDAB89;
\r
262 hash[2] = 0x98BADCFE;
\r
263 hash[3] = 0x10325476;
\r
266 memcpy(hash, hash_seed, sizeof(hash));
\r
268 switch (hash_version) {
\r
269 case EXT2_HTREE_TEA_UNSIGNED:
\r
271 case EXT2_HTREE_TEA:
\r
273 ext2_prep_hashbuf(name, len, data, 16, unsigned_char);
\r
274 ext2_tea(hash, data);
\r
281 case EXT2_HTREE_LEGACY_UNSIGNED:
\r
283 case EXT2_HTREE_LEGACY:
\r
284 major = ext2_legacy_hash(name, len, unsigned_char);
\r
286 case EXT2_HTREE_HALF_MD4_UNSIGNED:
\r
288 case EXT2_HTREE_HALF_MD4:
\r
290 ext2_prep_hashbuf(name, len, data, 32, unsigned_char);
\r
291 ext2_half_md4(hash, data);
\r
303 if (major == (EXT2_HTREE_EOF << 1))
\r
304 major = (EXT2_HTREE_EOF - 1) << 1;
\r
305 *hash_major = major;
\r
307 *hash_minor = minor;
\r