source: mainline/uspace/lib/ext4/libext4_hash.c@ 111d2d6

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 111d2d6 was 38542dc, checked in by Martin Decky <martin@…>, 13 years ago

ext4 code review and coding style cleanup
  • Property mode set to 100644
File size: 7.5 KB
Line 
1/*
2 * Copyright (c) 2012 Frantisek Princ
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - 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 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/** @addtogroup libext4
30 * @{
31 */
32/**
33 * @file libext4_hash.c
34 * @brief Hashing algorithms for ext4 HTree.
35 */
36
37#include <errno.h>
38#include <mem.h>
39#include "libext4.h"
40
41#define TEA_DELTA 0x9E3779B9
42
43/* F, G and H are basic MD4 functions: selection, majority, parity */
44#define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
45#define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z)))
46#define H(x, y, z) ((x) ^ (y) ^ (z))
47
48/*
49 * The generic round function. The application is so specific that
50 * we don't bother protecting all the arguments with parens, as is generally
51 * good macro practice, in favor of extra legibility.
52 * Rotation is separate from addition to prevent recomputation
53 */
54#define ROUND(f, a, b, c, d, x, s) \
55 (a += f(b, c, d) + x, a = (a << s) | (a >> (32 - s)))
56
57#define K1 0
58#define K2 013240474631UL
59#define K3 015666365641UL
60
61static void tea_transform(uint32_t buf[4], uint32_t const in[])
62{
63 uint32_t sum = 0;
64 uint32_t b0 = buf[0];
65 uint32_t b1 = buf[1];
66 uint32_t a = in[0];
67 uint32_t b = in[1];
68 uint32_t c = in[2];
69 uint32_t d = in[3];
70
71 int n = 16;
72
73 do {
74 sum += TEA_DELTA;
75 b0 += ((b1 << 4) + a) ^ (b1 + sum) ^ ((b1 >> 5) + b);
76 b1 += ((b0 << 4) + c) ^ (b0 + sum) ^ ((b0 >> 5) + d);
77 } while (--n);
78
79 buf[0] += b0;
80 buf[1] += b1;
81}
82
83
84static void half_md4_transform(uint32_t buf[4], const uint32_t in[8])
85{
86 uint32_t a = buf[0], b = buf[1], c = buf[2], d = buf[3];
87
88 /* Round 1 */
89 ROUND(F, a, b, c, d, in[0] + K1, 3);
90 ROUND(F, d, a, b, c, in[1] + K1, 7);
91 ROUND(F, c, d, a, b, in[2] + K1, 11);
92 ROUND(F, b, c, d, a, in[3] + K1, 19);
93 ROUND(F, a, b, c, d, in[4] + K1, 3);
94 ROUND(F, d, a, b, c, in[5] + K1, 7);
95 ROUND(F, c, d, a, b, in[6] + K1, 11);
96 ROUND(F, b, c, d, a, in[7] + K1, 19);
97
98 /* Round 2 */
99 ROUND(G, a, b, c, d, in[1] + K2, 3);
100 ROUND(G, d, a, b, c, in[3] + K2, 5);
101 ROUND(G, c, d, a, b, in[5] + K2, 9);
102 ROUND(G, b, c, d, a, in[7] + K2, 13);
103 ROUND(G, a, b, c, d, in[0] + K2, 3);
104 ROUND(G, d, a, b, c, in[2] + K2, 5);
105 ROUND(G, c, d, a, b, in[4] + K2, 9);
106 ROUND(G, b, c, d, a, in[6] + K2, 13);
107
108 /* Round 3 */
109 ROUND(H, a, b, c, d, in[3] + K3, 3);
110 ROUND(H, d, a, b, c, in[7] + K3, 9);
111 ROUND(H, c, d, a, b, in[2] + K3, 11);
112 ROUND(H, b, c, d, a, in[6] + K3, 15);
113 ROUND(H, a, b, c, d, in[1] + K3, 3);
114 ROUND(H, d, a, b, c, in[5] + K3, 9);
115 ROUND(H, c, d, a, b, in[0] + K3, 11);
116 ROUND(H, b, c, d, a, in[4] + K3, 15);
117
118 buf[0] += a;
119 buf[1] += b;
120 buf[2] += c;
121 buf[3] += d;
122}
123
124static uint32_t hash_unsigned(const char *name, int len)
125{
126 uint32_t hash;
127 uint32_t hash0 = 0x12a3fe2d;
128 uint32_t hash1 = 0x37abe8f9;
129 const unsigned char *ucp = (const unsigned char *) name;
130
131 while (len--) {
132 hash = hash1 + (hash0 ^ (((int) *ucp++) * 7152373));
133
134 if (hash & 0x80000000)
135 hash -= 0x7fffffff;
136
137 hash1 = hash0;
138 hash0 = hash;
139 }
140
141 return hash0 << 1;
142}
143
144static uint32_t hash_signed(const char *name, int len)
145{
146 uint32_t hash;
147 uint32_t hash0 = 0x12a3fe2d;
148 uint32_t hash1 = 0x37abe8f9;
149 const signed char *scp = (const signed char *) name;
150
151 while (len--) {
152 hash = hash1 + (hash0 ^ (((int) *scp++) * 7152373));
153
154 if (hash & 0x80000000)
155 hash -= 0x7fffffff;
156
157 hash1 = hash0;
158 hash0 = hash;
159 }
160
161 return hash0 << 1;
162}
163
164static void str2hashbuf_signed(const char *msg, int len, uint32_t *buf, int num)
165{
166 uint32_t pad, val;
167 int i;
168 const signed char *scp = (const signed char *) msg;
169
170 pad = (uint32_t) len | ((uint32_t) len << 8);
171 pad |= pad << 16;
172
173 val = pad;
174 if (len > num * 4)
175 len = num * 4;
176
177 for (i = 0; i < len; i++) {
178 if ((i % 4) == 0)
179 val = pad;
180
181 val = ((int) scp[i]) + (val << 8);
182 if ((i % 4) == 3) {
183 *buf++ = val;
184 val = pad;
185 num--;
186 }
187 }
188
189 if (--num >= 0)
190 *buf++ = val;
191
192 while (--num >= 0)
193 *buf++ = pad;
194}
195
196static void str2hashbuf_unsigned(const char *msg, int len, uint32_t *buf,
197 int num)
198{
199 uint32_t pad, val;
200 int i;
201 const unsigned char *ucp = (const unsigned char *) msg;
202
203 pad = (uint32_t) len | ((uint32_t) len << 8);
204 pad |= pad << 16;
205
206 val = pad;
207 if (len > num * 4)
208 len = num * 4;
209
210 for (i = 0; i < len; i++) {
211 if ((i % 4) == 0)
212 val = pad;
213
214 val = ((int) ucp[i]) + (val << 8);
215 if ((i % 4) == 3) {
216 *buf++ = val;
217 val = pad;
218 num--;
219 }
220 }
221
222 if (--num >= 0)
223 *buf++ = val;
224
225 while (--num >= 0)
226 *buf++ = pad;
227}
228
229/** Compute hash value of the string.
230 *
231 * @param hinfo Hash info structure with information about
232 * the algorithm, hash seed and with the place
233 * for the output hash value
234 * @param len Length of the name
235 * @param name Name to be hashed
236 *
237 * @return Error code
238 *
239 */
240int ext4_hash_string(ext4_hash_info_t *hinfo, int len, const char *name)
241{
242 uint32_t hash = 0;
243 uint32_t minor_hash = 0;
244 const char *p;
245 int i;
246 uint32_t in[8], buf[4];
247 void (*str2hashbuf)(const char *, int, uint32_t *, int) =
248 str2hashbuf_signed;
249
250 /* Initialize the default seed for the hash checksum functions */
251 buf[0] = 0x67452301;
252 buf[1] = 0xefcdab89;
253 buf[2] = 0x98badcfe;
254 buf[3] = 0x10325476;
255
256 /* Check if the seed is all zero's */
257 if (hinfo->seed) {
258 for (i = 0; i < 4; i++) {
259 if (hinfo->seed[i] != 0)
260 break;
261
262 }
263
264 if (i < 4)
265 memcpy(buf, hinfo->seed, sizeof(buf));
266 }
267
268 switch (hinfo->hash_version) {
269 case EXT4_HASH_VERSION_LEGACY_UNSIGNED:
270 hash = hash_unsigned(name, len);
271 break;
272 case EXT4_HASH_VERSION_LEGACY:
273 hash = hash_signed(name, len);
274 break;
275 case EXT4_HASH_VERSION_HALF_MD4_UNSIGNED:
276 str2hashbuf = str2hashbuf_unsigned;
277 case EXT4_HASH_VERSION_HALF_MD4:
278 p = name;
279
280 while (len > 0) {
281 (*str2hashbuf)(p, len, in, 8);
282 half_md4_transform(buf, in);
283 len -= 32;
284 p += 32;
285 }
286
287 minor_hash = buf[2];
288 hash = buf[1];
289 break;
290 case EXT4_HASH_VERSION_TEA_UNSIGNED:
291 str2hashbuf = str2hashbuf_unsigned;
292 case EXT4_HASH_VERSION_TEA:
293 p = name;
294
295 while (len > 0) {
296 (*str2hashbuf)(p, len, in, 4);
297 tea_transform(buf, in);
298 len -= 16;
299 p += 16;
300 }
301
302 hash = buf[0];
303 minor_hash = buf[1];
304 break;
305 default:
306 hinfo->hash = 0;
307 return EINVAL;
308 }
309
310 hash = hash & ~1;
311 if (hash == (EXT4_DIRECTORY_HTREE_EOF << 1))
312 hash = (EXT4_DIRECTORY_HTREE_EOF - 1) << 1;
313
314 hinfo->hash = hash;
315 hinfo->minor_hash = minor_hash;
316
317 return EOK;
318}
319
320/**
321 * @}
322 */
Note: See TracBrowser for help on using the repository browser.