source: mainline/uspace/lib/ext4/libext4_hash.c@ f22d5ef0

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since f22d5ef0 was f22d5ef0, checked in by Frantisek Princ <frantisek.princ@…>, 13 years ago

Copyright update
  • Property mode set to 100644
File size: 7.2 KB
RevLine 
[8158db7]1/*
[f22d5ef0]2 * Copyright (c) 2012 Frantisek Princ
[8158db7]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/**
34 * @file libext4_hash.c
[c25e39b]35 * @brief Hashing algorithms for ext4 HTree.
[8158db7]36 */
37
38#include <errno.h>
39#include <mem.h>
40
[246a5af]41#include "libext4.h"
[8158db7]42
43#define TEA_DELTA 0x9E3779B9
44
45
46/* F, G and H are basic MD4 functions: selection, majority, parity */
47#define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
48#define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z)))
49#define H(x, y, z) ((x) ^ (y) ^ (z))
50
[ab77928]51
[8158db7]52/*
53 * The generic round function. The application is so specific that
54 * we don't bother protecting all the arguments with parens, as is generally
55 * good macro practice, in favor of extra legibility.
56 * Rotation is separate from addition to prevent recomputation
57 */
58#define ROUND(f, a, b, c, d, x, s) \
59 (a += f(b, c, d) + x, a = (a << s) | (a >> (32 - s)))
60#define K1 0
61#define K2 013240474631UL
62#define K3 015666365641UL
63
64
[ab77928]65static void tea_transform(uint32_t buf[4], uint32_t const in[])
[8158db7]66{
67 uint32_t sum = 0;
68 uint32_t b0 = buf[0], b1 = buf[1];
69 uint32_t a = in[0], b = in[1], c = in[2], d = in[3];
70 int n = 16;
71
72 do {
73 sum += TEA_DELTA;
74 b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b);
75 b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d);
76 } while (--n);
77
78 buf[0] += b0;
79 buf[1] += b1;
80}
81
82
83static void half_md4_transform(uint32_t buf[4], const uint32_t in[8])
84{
85 uint32_t a = buf[0], b = buf[1], c = buf[2], d = buf[3];
86
87 /* Round 1 */
88 ROUND(F, a, b, c, d, in[0] + K1, 3);
89 ROUND(F, d, a, b, c, in[1] + K1, 7);
90 ROUND(F, c, d, a, b, in[2] + K1, 11);
91 ROUND(F, b, c, d, a, in[3] + K1, 19);
92 ROUND(F, a, b, c, d, in[4] + K1, 3);
93 ROUND(F, d, a, b, c, in[5] + K1, 7);
94 ROUND(F, c, d, a, b, in[6] + K1, 11);
95 ROUND(F, b, c, d, a, in[7] + K1, 19);
96
97 /* Round 2 */
98 ROUND(G, a, b, c, d, in[1] + K2, 3);
99 ROUND(G, d, a, b, c, in[3] + K2, 5);
100 ROUND(G, c, d, a, b, in[5] + K2, 9);
101 ROUND(G, b, c, d, a, in[7] + K2, 13);
102 ROUND(G, a, b, c, d, in[0] + K2, 3);
103 ROUND(G, d, a, b, c, in[2] + K2, 5);
104 ROUND(G, c, d, a, b, in[4] + K2, 9);
105 ROUND(G, b, c, d, a, in[6] + K2, 13);
106
107 /* Round 3 */
108 ROUND(H, a, b, c, d, in[3] + K3, 3);
109 ROUND(H, d, a, b, c, in[7] + K3, 9);
110 ROUND(H, c, d, a, b, in[2] + K3, 11);
111 ROUND(H, b, c, d, a, in[6] + K3, 15);
112 ROUND(H, a, b, c, d, in[1] + K3, 3);
113 ROUND(H, d, a, b, c, in[5] + K3, 9);
114 ROUND(H, c, d, a, b, in[0] + K3, 11);
115 ROUND(H, b, c, d, a, in[4] + K3, 15);
116
117 buf[0] += a;
118 buf[1] += b;
119 buf[2] += c;
120 buf[3] += d;
121
122}
123
124static uint32_t hash_unsigned(const char *name, int len)
125{
126 uint32_t hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
127 const unsigned char *ucp = (const unsigned char *) name;
128
129 while (len--) {
130 hash = hash1 + (hash0 ^ (((int) *ucp++) * 7152373));
131
132 if (hash & 0x80000000) {
133 hash -= 0x7fffffff;
134 }
135 hash1 = hash0;
136 hash0 = hash;
137 }
138 return hash0 << 1;
139}
140
141static uint32_t hash_signed(const char *name, int len)
142{
143 uint32_t hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
144 const signed char *scp = (const signed char *) name;
145
146 while (len--) {
147 hash = hash1 + (hash0 ^ (((int) *scp++) * 7152373));
148
149 if (hash & 0x80000000) {
150 hash -= 0x7fffffff;
151 }
152 hash1 = hash0;
153 hash0 = hash;
154 }
155 return hash0 << 1;
156}
157
158static void str2hashbuf_signed(const char *msg, int len, uint32_t *buf, int num)
159{
160 uint32_t pad, val;
161 int i;
162 const signed char *scp = (const signed char *) msg;
163
164 pad = (uint32_t)len | ((uint32_t)len << 8);
165 pad |= pad << 16;
166
167 val = pad;
168 if (len > num*4) {
169 len = num * 4;
170 }
171
172 for (i = 0; i < len; i++) {
173 if ((i % 4) == 0) {
174 val = pad;
175 }
176 val = ((int) scp[i]) + (val << 8);
177 if ((i % 4) == 3) {
178 *buf++ = val;
179 val = pad;
180 num--;
181 }
182 }
183
184 if (--num >= 0) {
185 *buf++ = val;
186 }
187
188 while (--num >= 0) {
189 *buf++ = pad;
190 }
191}
192
193
194static void str2hashbuf_unsigned(const char *msg, int len, uint32_t *buf, int num)
195{
196 uint32_t pad, val;
197 int i;
198 const unsigned char *ucp = (const unsigned char *) msg;
199
200 pad = (uint32_t)len | ((uint32_t)len << 8);
201 pad |= pad << 16;
202
203 val = pad;
204 if (len > num*4) {
205 len = num * 4;
206 }
207
208 for (i = 0; i < len; i++) {
209 if ((i % 4) == 0) {
210 val = pad;
211 }
212 val = ((int) ucp[i]) + (val << 8);
213 if ((i % 4) == 3) {
214 *buf++ = val;
215 val = pad;
216 num--;
217 }
218 }
219
220 if (--num >= 0) {
221 *buf++ = val;
222 }
223
224 while (--num >= 0) {
225 *buf++ = pad;
226 }
227}
228
[246a5af]229int ext4_hash_string(ext4_hash_info_t *hinfo, int len, const char *name)
[8158db7]230{
231 uint32_t hash = 0;
232 uint32_t minor_hash = 0;
233 const char *p;
234 int i;
235 uint32_t in[8], buf[4];
[ab77928]236 void (*str2hashbuf)(const char *, int, uint32_t *, int) = str2hashbuf_signed;
237
[8158db7]238 /* Initialize the default seed for the hash checksum functions */
239 buf[0] = 0x67452301;
240 buf[1] = 0xefcdab89;
241 buf[2] = 0x98badcfe;
242 buf[3] = 0x10325476;
243
244 /* Check if the seed is all zero's */
245 if (hinfo->seed) {
246 for (i = 0; i < 4; i++) {
247 if (hinfo->seed[i] != 0) {
248 break;
249 }
[ab77928]250 }
251 if (i < 4) {
252 memcpy(buf, hinfo->seed, sizeof(buf));
[8158db7]253 }
254 }
255
256 switch (hinfo->hash_version) {
257 case EXT4_HASH_VERSION_LEGACY_UNSIGNED:
258 hash = hash_unsigned(name, len);
259 break;
260
261 case EXT4_HASH_VERSION_LEGACY:
262 hash = hash_signed(name, len);
263 break;
264
265
266 case EXT4_HASH_VERSION_HALF_MD4_UNSIGNED:
[ab77928]267 str2hashbuf = str2hashbuf_unsigned;
[8158db7]268
269 case EXT4_HASH_VERSION_HALF_MD4:
270 p = name;
271 while (len > 0) {
[ab77928]272 (*str2hashbuf)(p, len, in, 8);
[8158db7]273 half_md4_transform(buf, in);
274 len -= 32;
275 p += 32;
276 }
277 minor_hash = buf[2];
278 hash = buf[1];
279 break;
280
281
282 case EXT4_HASH_VERSION_TEA_UNSIGNED:
[ab77928]283 str2hashbuf = str2hashbuf_unsigned;
[8158db7]284
285 case EXT4_HASH_VERSION_TEA:
286 p = name;
287 while (len > 0) {
[ab77928]288 (*str2hashbuf)(p, len, in, 4);
[8158db7]289 tea_transform(buf, in);
290 len -= 16;
291 p += 16;
292 }
293 hash = buf[0];
294 minor_hash = buf[1];
295 break;
296
297 default:
298 hinfo->hash = 0;
299 return EINVAL;
300 }
301
302 hash = hash & ~1;
303 if (hash == (EXT4_DIRECTORY_HTREE_EOF << 1)) {
304 hash = (EXT4_DIRECTORY_HTREE_EOF-1) << 1;
305 }
[ab77928]306
[8158db7]307 hinfo->hash = hash;
308 hinfo->minor_hash = minor_hash;
309
310 return EOK;
311}
312
313/**
314 * @}
315 */
Note: See TracBrowser for help on using the repository browser.