Changeset beb9336 in mainline for uspace/lib/ext4/libext4_hash.c
- Timestamp:
- 2012-08-24T14:07:52Z (13 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- 041ab64
- Parents:
- bd29f9c9 (diff), db81577 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)links above to see all the changes relative to each parent. - File:
-
- 1 edited
-
uspace/lib/ext4/libext4_hash.c (modified) (12 diffs)
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/ext4/libext4_hash.c
rbd29f9c9 rbeb9336 29 29 /** @addtogroup libext4 30 30 * @{ 31 */ 32 31 */ 33 32 /** 34 * @file 35 * @brief 33 * @file libext4_hash.c 34 * @brief Hashing algorithms for ext4 HTree. 36 35 */ 37 36 38 37 #include <errno.h> 39 38 #include <mem.h> 40 41 39 #include "libext4.h" 42 40 43 #define TEA_DELTA 0x9E3779B9 44 41 #define TEA_DELTA 0x9E3779B9 45 42 46 43 /* 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 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)) 51 47 52 48 /* … … 56 52 * Rotation is separate from addition to prevent recomputation 57 53 */ 58 #define ROUND(f, a, b, c, d, x, s) 59 60 #define K1 0 61 #define K 2 013240474631UL62 #define K 3 015666365641UL63 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 64 60 65 61 static void tea_transform(uint32_t buf[4], uint32_t const in[]) 66 62 { 67 63 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]; 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 70 71 int n = 16; 71 72 72 73 do { 73 74 sum += TEA_DELTA; 74 b0 += ((b1 << 4) +a) ^ (b1+sum) ^ ((b1 >> 5)+b);75 b1 += ((b0 << 4) +c) ^ (b0+sum) ^ ((b0 >> 5)+d);75 b0 += ((b1 << 4) + a) ^ (b1 + sum) ^ ((b1 >> 5) + b); 76 b1 += ((b0 << 4) + c) ^ (b0 + sum) ^ ((b0 >> 5) + d); 76 77 } while (--n); 77 78 78 79 buf[0] += b0; 79 80 buf[1] += b1; … … 84 85 { 85 86 uint32_t a = buf[0], b = buf[1], c = buf[2], d = buf[3]; 86 87 87 88 /* Round 1 */ 88 89 ROUND(F, a, b, c, d, in[0] + K1, 3); … … 94 95 ROUND(F, c, d, a, b, in[6] + K1, 11); 95 96 ROUND(F, b, c, d, a, in[7] + K1, 19); 96 97 97 98 /* Round 2 */ 98 99 ROUND(G, a, b, c, d, in[1] + K2, 3); … … 104 105 ROUND(G, c, d, a, b, in[4] + K2, 9); 105 106 ROUND(G, b, c, d, a, in[6] + K2, 13); 106 107 107 108 /* Round 3 */ 108 109 ROUND(H, a, b, c, d, in[3] + K3, 3); … … 114 115 ROUND(H, c, d, a, b, in[0] + K3, 11); 115 116 ROUND(H, b, c, d, a, in[4] + K3, 15); 116 117 117 118 buf[0] += a; 118 119 buf[1] += b; 119 120 buf[2] += c; 120 121 buf[3] += d; 121 122 122 } 123 123 124 124 static uint32_t hash_unsigned(const char *name, int len) 125 125 { 126 uint32_t hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; 126 uint32_t hash; 127 uint32_t hash0 = 0x12a3fe2d; 128 uint32_t hash1 = 0x37abe8f9; 127 129 const unsigned char *ucp = (const unsigned char *) name; 128 130 129 131 while (len--) { 130 132 hash = hash1 + (hash0 ^ (((int) *ucp++) * 7152373)); 131 132 if (hash & 0x80000000) {133 134 if (hash & 0x80000000) 133 135 hash -= 0x7fffffff; 134 }136 135 137 hash1 = hash0; 136 138 hash0 = hash; 137 139 } 140 138 141 return hash0 << 1; 139 142 } … … 141 144 static uint32_t hash_signed(const char *name, int len) 142 145 { 143 uint32_t hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; 146 uint32_t hash; 147 uint32_t hash0 = 0x12a3fe2d; 148 uint32_t hash1 = 0x37abe8f9; 144 149 const signed char *scp = (const signed char *) name; 145 150 146 151 while (len--) { 147 152 hash = hash1 + (hash0 ^ (((int) *scp++) * 7152373)); 148 149 if (hash & 0x80000000) {153 154 if (hash & 0x80000000) 150 155 hash -= 0x7fffffff; 151 }156 152 157 hash1 = hash0; 153 158 hash0 = hash; 154 159 } 160 155 161 return hash0 << 1; 156 162 } … … 161 167 int i; 162 168 const signed char *scp = (const signed char *) msg; 163 164 pad = (uint32_t) len | ((uint32_t)len << 8);169 170 pad = (uint32_t) len | ((uint32_t) len << 8); 165 171 pad |= pad << 16; 166 172 167 173 val = pad; 168 if (len > num *4) {174 if (len > num * 4) 169 175 len = num * 4; 170 } 171 176 172 177 for (i = 0; i < len; i++) { 173 if ((i % 4) == 0) {178 if ((i % 4) == 0) 174 179 val = pad; 175 }180 176 181 val = ((int) scp[i]) + (val << 8); 177 182 if ((i % 4) == 3) { … … 181 186 } 182 187 } 183 184 if (--num >= 0) {188 189 if (--num >= 0) 185 190 *buf++ = val; 186 } 187 188 while (--num >= 0) { 191 192 while (--num >= 0) 189 193 *buf++ = pad; 190 } 191 } 192 193 194 static void str2hashbuf_unsigned(const char *msg, int len, uint32_t *buf, int num) 194 } 195 196 static void str2hashbuf_unsigned(const char *msg, int len, uint32_t *buf, 197 int num) 195 198 { 196 199 uint32_t pad, val; 197 200 int i; 198 201 const unsigned char *ucp = (const unsigned char *) msg; 199 200 pad = (uint32_t) len | ((uint32_t)len << 8);202 203 pad = (uint32_t) len | ((uint32_t) len << 8); 201 204 pad |= pad << 16; 202 205 203 206 val = pad; 204 if (len > num*4) { 205 len = num * 4; 206 } 207 207 if (len > num * 4) 208 len = num * 4; 209 208 210 for (i = 0; i < len; i++) { 209 if ((i % 4) == 0) {211 if ((i % 4) == 0) 210 212 val = pad; 211 }213 212 214 val = ((int) ucp[i]) + (val << 8); 213 215 if ((i % 4) == 3) { … … 217 219 } 218 220 } 219 220 if (--num >= 0) {221 222 if (--num >= 0) 221 223 *buf++ = val; 222 } 223 224 while (--num >= 0) { 224 225 while (--num >= 0) 225 226 *buf++ = pad; 226 } 227 } 228 227 } 229 228 230 229 /** Compute hash value of the string. 231 230 * 232 * @param hinfo hash info structure with information about 233 * the algorithm, hash seed and with the place 234 * for the output hash value 235 * @param len length of the name 236 * @param name name to be hashed 237 * @return error code 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 * 238 239 */ 239 240 int ext4_hash_string(ext4_hash_info_t *hinfo, int len, const char *name) … … 242 243 uint32_t minor_hash = 0; 243 244 const char *p; 244 int i; 245 uint32_t in[8], buf[4]; 246 void (*str2hashbuf)(const char *, int, uint32_t *, int) = str2hashbuf_signed; 247 248 /* Initialize the default seed for the hash checksum functions */ 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 */ 249 251 buf[0] = 0x67452301; 250 252 buf[1] = 0xefcdab89; 251 253 buf[2] = 0x98badcfe; 252 254 buf[3] = 0x10325476; 253 254 255 256 /* Check if the seed is all zero's */ 255 257 if (hinfo->seed) { 256 258 for (i = 0; i < 4; i++) { 257 if (hinfo->seed[i] != 0) { 258 break; 259 } 260 } 261 if (i < 4) { 259 if (hinfo->seed[i] != 0) 260 break; 261 262 } 263 264 if (i < 4) 262 265 memcpy(buf, hinfo->seed, sizeof(buf)); 263 } 264 } 265 266 } 267 266 268 switch (hinfo->hash_version) { 267 case EXT4_HASH_VERSION_LEGACY_UNSIGNED: 268 hash = hash_unsigned(name, len); 269 break; 270 271 case EXT4_HASH_VERSION_LEGACY: 272 hash = hash_signed(name, len); 273 break; 274 275 276 case EXT4_HASH_VERSION_HALF_MD4_UNSIGNED: 277 str2hashbuf = str2hashbuf_unsigned; 278 279 case EXT4_HASH_VERSION_HALF_MD4: 280 p = name; 281 while (len > 0) { 282 (*str2hashbuf)(p, len, in, 8); 283 half_md4_transform(buf, in); 284 len -= 32; 285 p += 32; 286 } 287 minor_hash = buf[2]; 288 hash = buf[1]; 289 break; 290 291 292 case EXT4_HASH_VERSION_TEA_UNSIGNED: 293 str2hashbuf = str2hashbuf_unsigned; 294 295 case EXT4_HASH_VERSION_TEA: 296 p = name; 297 while (len > 0) { 298 (*str2hashbuf)(p, len, in, 4); 299 tea_transform(buf, in); 300 len -= 16; 301 p += 16; 302 } 303 hash = buf[0]; 304 minor_hash = buf[1]; 305 break; 306 307 default: 308 hinfo->hash = 0; 309 return EINVAL; 310 } 311 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 312 310 hash = hash & ~1; 313 if (hash == (EXT4_DIRECTORY_HTREE_EOF << 1)) { 314 hash = (EXT4_DIRECTORY_HTREE_EOF-1) << 1; 315 } 316 311 if (hash == (EXT4_DIRECTORY_HTREE_EOF << 1)) 312 hash = (EXT4_DIRECTORY_HTREE_EOF - 1) << 1; 313 317 314 hinfo->hash = hash; 318 315 hinfo->minor_hash = minor_hash; 319 316 320 317 return EOK; 321 318 } … … 323 320 /** 324 321 * @} 325 */ 322 */
Note:
See TracChangeset
for help on using the changeset viewer.
