Changeset 0d8322da in mainline for uspace/lib/ext4/libext4_hash.c
- Timestamp:
- 2012-09-23T08:03:08Z (13 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- c99d470
- Parents:
- 8595b954
- File:
-
- 1 edited
-
uspace/lib/ext4/libext4_hash.c (modified) (1 diff)
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/ext4/libext4_hash.c
r8595b954 r0d8322da 35 35 */ 36 36 37 #include "libext4.h" 37 38 #include <errno.h> 38 #include <mem.h>39 #include "libext4.h"40 39 41 #define TEA_DELTA 0x9E3779B942 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 that50 * we don't bother protecting all the arguments with parens, as is generally51 * good macro practice, in favor of extra legibility.52 * Rotation is separate from addition to prevent recomputation53 */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 058 #define K2 013240474631UL59 #define K3 015666365641UL60 61 static 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 84 static 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 124 static 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 144 static 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 164 static 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 196 static 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 about232 * the algorithm, hash seed and with the place233 * for the output hash value234 * @param len Length of the name235 * @param name Name to be hashed236 *237 * @return Error code238 *239 */240 40 int ext4_hash_string(ext4_hash_info_t *hinfo, int len, const char *name) 241 41 { 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; 42 // TODO 43 hinfo->hash = 0; 44 return ENOTSUP; 318 45 } 319 46
Note:
See TracChangeset
for help on using the changeset viewer.
