1 /* 2 * Copyright 2010, Haiku Inc. All rights reserved. 3 * This file may be used under the terms of the MIT License. 4 * 5 * Authors: 6 * Janito V. Ferreira Filho 7 */ 8 9 10 #include "HTree.h" 11 12 #include <new> 13 #include <string.h> 14 15 #include "HTreeEntryIterator.h" 16 #include "Inode.h" 17 #include "Volume.h" 18 19 20 //#define TRACE_EXT2 21 #ifdef TRACE_EXT2 22 # define TRACE(x...) dprintf("\33[34mext2:\33[0m " x) 23 #else 24 # define TRACE(x...) ; 25 #endif 26 27 28 bool 29 HTreeRoot::IsValid() const 30 { 31 if (reserved != 0) 32 return false; 33 if (hash_version != HTREE_HASH_LEGACY 34 && hash_version != HTREE_HASH_HALF_MD4 35 && hash_version != HTREE_HASH_TEA) 36 return false; 37 if (root_info_length != 8) 38 return false; 39 if (indirection_levels > 1) 40 return false; 41 42 // TODO: Maybe we should check the false directory entries too? 43 44 return true; 45 } 46 47 48 HTree::HTree(Volume* volume, Inode* directory) 49 : 50 fDirectory(directory), 51 fRootEntry(NULL) 52 { 53 fBlockSize = volume->BlockSize(); 54 fIndexed = volume->IndexedDirectories() 55 && (directory->Flags() & EXT2_INODE_INDEXED) != 0; 56 57 ext2_super_block superBlock = volume->SuperBlock(); 58 fHashSeed[0] = superBlock.HashSeed(0); 59 fHashSeed[1] = superBlock.HashSeed(1); 60 fHashSeed[2] = superBlock.HashSeed(2); 61 fHashSeed[3] = superBlock.HashSeed(3); 62 63 TRACE("HTree::HTree() %lx %lx %lx %lx\n", fHashSeed[0], 64 fHashSeed[1], fHashSeed[2], fHashSeed[3]); 65 66 if (fHashSeed[0] == 0 && fHashSeed[1] == 0 && fHashSeed[2] == 0 67 && fHashSeed[3] == 0) { 68 fHashSeed[0] = 0x67452301; 69 fHashSeed[1] = 0xefcdab89; 70 fHashSeed[2] = 0x98badcfe; 71 fHashSeed[3] = 0x10325476; 72 } 73 } 74 75 76 HTree::~HTree() 77 { 78 } 79 80 81 status_t 82 HTree::Lookup(const char* name, DirectoryIterator** iterator) 83 { 84 if (!fIndexed || (name[0] == '.' 85 && (name[1] == '\0' || (name[1] == '.' && name[2] == '0')))) { 86 // No HTree support or looking for trivial directories 87 // TODO: Does these directories get hashed? 88 *iterator = new(std::nothrow) DirectoryIterator(fDirectory); 89 90 if (*iterator == NULL) 91 return B_NO_MEMORY; 92 return B_OK; 93 } 94 95 HTreeRoot root; 96 size_t length = sizeof(root); 97 98 status_t status = fDirectory->ReadAt(0, (uint8*)&root, &length); 99 if (status < B_OK) 100 return status; 101 102 if (length != sizeof(root) || !root.IsValid()) { 103 // Fallback to linear search 104 *iterator = new(std::nothrow) DirectoryIterator(fDirectory); 105 if (*iterator == NULL) 106 return B_NO_MEMORY; 107 108 return B_OK; 109 } 110 111 uint32 hash = _Hash(name, root.hash_version); 112 113 off_t start = (off_t)root.root_info_length 114 + 2 * (sizeof(HTreeFakeDirEntry) + 4); 115 116 fRootEntry = new(std::nothrow) HTreeEntryIterator(start, fDirectory); 117 if (fRootEntry == NULL) 118 return B_NO_MEMORY; 119 120 fRootDeleter.SetTo(fRootEntry); 121 status = fRootEntry->Init(); 122 if (status != B_OK) 123 return status; 124 125 return fRootEntry->Lookup(hash, (uint32)root.indirection_levels, iterator); 126 } 127 128 129 uint32 130 HTree::_Hash(const char* name, uint8 version) 131 { 132 uint32 hash; 133 134 switch (version) { 135 case HTREE_HASH_LEGACY: 136 hash = _HashLegacy(name); 137 break; 138 case HTREE_HASH_HALF_MD4: 139 hash = _HashHalfMD4(name); 140 break; 141 case HTREE_HASH_TEA: 142 hash = _HashTEA(name); 143 break; 144 default: 145 panic("Hash verification succeeded but then failed?"); 146 hash = 0; 147 }; 148 149 TRACE("Filename hash: %u\n", hash); 150 151 return hash & ~1; 152 } 153 154 155 uint32 156 HTree::_HashLegacy(const char* name) 157 { 158 uint32 hash = 0x12a3fe2d; 159 uint32 previous = 0x37abe8f9; 160 161 for (; *name != '\0'; ++name) { 162 uint32 next = previous + (hash ^ (*name * 7152373)); 163 164 if ((next & 0x80000000) != 0) 165 next -= 0x7fffffff; 166 167 previous = hash; 168 hash = next; 169 } 170 171 return hash; 172 } 173 174 175 /*inline*/ uint32 176 HTree::_MD4F(uint32 x, uint32 y, uint32 z) 177 { 178 return z ^ (x & (y ^ z)); 179 } 180 181 182 /*inline*/ uint32 183 HTree::_MD4G(uint32 x, uint32 y, uint32 z) 184 { 185 return (x & y) + ((x ^ y) & z); 186 } 187 188 189 /*inline*/ uint32 190 HTree::_MD4H(uint32 x, uint32 y, uint32 z) 191 { 192 return x ^ y ^ z; 193 } 194 195 196 /*inline*/ void 197 HTree::_MD4RotateVars(uint32& a, uint32& b, uint32& c, uint32& d) 198 { 199 uint32 oldD = d; 200 d = c; 201 c = b; 202 b = a; 203 a = oldD; 204 } 205 206 207 void 208 HTree::_HalfMD4Transform(uint32 buffer[4], uint32 blocks[8]) 209 { 210 uint32 a, b, c, d; 211 212 a = buffer[0]; 213 b = buffer[1]; 214 c = buffer[2]; 215 d = buffer[3]; 216 217 // Round 1 218 uint32 shifts[4] = { 3, 7, 11, 19 }; 219 220 for (int i = 0; i < 8; ++i) { 221 a += _MD4F(b, c, d) + blocks[i]; 222 uint32 shift = shifts[i % 4]; 223 a = (a << shift) | (a >> (32 - shift)); 224 225 _MD4RotateVars(a, b, c, d); 226 } 227 228 // Round 2 229 shifts[1] = 5; 230 shifts[2] = 9; 231 shifts[3] = 13; 232 233 for (int j = 0; j < 2; ++j) { 234 for (int i = j; i < 4; i += 2) { 235 a += _MD4G(b, c, d) + blocks[i] + 013240474631UL; 236 uint32 shift = shifts[i / 2]; 237 a = (a << shift) | (a >> (32 - shift)); 238 239 _MD4RotateVars(a, b, c, d); 240 } 241 } 242 243 // Round 3 244 shifts[1] = 9; 245 shifts[2] = 11; 246 shifts[3] = 15; 247 248 for (int i = 0; i < 4; ++i) { 249 a += _MD4H(b, c, d) + blocks[3 - i] + 015666365641UL; 250 uint32 shift = shifts[i*2]; 251 a = (a << shift) | (a >> (32 - shift)); 252 253 _MD4RotateVars(a, b, c, d); 254 255 a += _MD4H(b, c, d) + blocks[7 - i] + 015666365641UL; 256 shift = shifts[i*2 + 1]; 257 a = (a << shift) | (a >> (32 - shift)); 258 259 _MD4RotateVars(a, b, c, d); 260 } 261 262 buffer[0] += a; 263 buffer[1] += b; 264 buffer[2] += c; 265 buffer[3] += d; 266 } 267 268 269 uint32 270 HTree::_HashHalfMD4(const char* name) 271 { 272 uint32 buffer[4]; 273 274 buffer[0] = fHashSeed[0]; 275 buffer[1] = fHashSeed[1]; 276 buffer[2] = fHashSeed[2]; 277 buffer[3] = fHashSeed[3]; 278 279 for (int length = strlen(name); length > 0; length -= 32) { 280 uint32 blocks[8]; 281 282 _PrepareBlocksForHash(name, length, blocks, 8); 283 _HalfMD4Transform(buffer, blocks); 284 285 name += 32; 286 } 287 288 return buffer[1]; 289 } 290 291 292 void 293 HTree::_TEATransform(uint32 buffer[4], uint32 blocks[4]) 294 { 295 uint32 x, y; 296 x = buffer[0]; 297 y = buffer[1]; 298 299 uint32 a, b, c, d; 300 a = blocks[0]; 301 b = blocks[1]; 302 c = blocks[2]; 303 d = blocks[3]; 304 305 uint32 sum = 0; 306 307 for (int i = 16; i > 0; --i) { 308 sum += 0x9E3779B9; 309 x += ((y << 4) + a) ^ (y + sum) ^ ((y >> 5) + b); 310 y += ((x << 4) + c) ^ (x + sum) ^ ((x >> 5) + d); 311 } 312 313 buffer[0] += x; 314 buffer[1] += y; 315 } 316 317 318 uint32 319 HTree::_HashTEA(const char* name) 320 { 321 uint32 buffer[4]; 322 323 buffer[0] = fHashSeed[0]; 324 buffer[1] = fHashSeed[1]; 325 buffer[2] = fHashSeed[2]; 326 buffer[3] = fHashSeed[3]; 327 328 for (int length = strlen(name); length > 0; length -= 16) { 329 uint32 blocks[4]; 330 331 _PrepareBlocksForHash(name, length, blocks, 4); 332 TRACE("_HashTEA %lx %lx %lx\n", blocks[0], blocks[1], blocks[2]); 333 _TEATransform(buffer, blocks); 334 335 name += 16; 336 } 337 338 return buffer[0]; 339 } 340 341 342 void 343 HTree::_PrepareBlocksForHash(const char* string, int length, uint32* blocks, 344 int numBlocks) 345 { 346 uint32 padding = (uint32)length; 347 padding = (padding << 8) | padding; 348 padding = (padding << 16) | padding; 349 350 int numBytes = numBlocks * 4; 351 if (length > numBytes) 352 length = numBytes; 353 354 int completeIterations = length / 4; 355 356 for (int i = 0; i < completeIterations; ++i) { 357 uint32 value = 0 | *(string++); 358 value = (value << 8) | *(string++); 359 value = (value << 8) | *(string++); 360 value = (value << 8) | *(string++); 361 blocks[i] = value; 362 } 363 364 if (completeIterations < numBlocks) { 365 int remainingBytes = length % 4; 366 367 uint32 value = padding; 368 for (int i = 0; i < remainingBytes; ++i) 369 value = (value << 8) + *(string++); 370 371 blocks[completeIterations] = value; 372 373 for (int i = completeIterations + 1; i < numBlocks; ++i) 374 blocks[i] = padding; 375 } 376 } 377