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 #ifndef HTREE_H 9 #define HTREE_H 10 11 12 #include <AutoDeleter.h> 13 14 #include "ext2.h" 15 #include "DirectoryIterator.h" 16 #include "HTreeEntryIterator.h" 17 #include "Inode.h" 18 19 20 #define HTREE_HASH_LEGACY 0 21 #define HTREE_HASH_HALF_MD4 1 22 #define HTREE_HASH_TEA 2 23 24 25 struct JournalRevokeHeader; 26 27 28 struct HTreeFakeDirEntry { 29 uint32 inode_id; 30 uint16 entry_length; 31 uint8 name_length; 32 uint8 file_type; 33 char file_name[0]; 34 35 uint32 InodeID() const 36 { return B_LENDIAN_TO_HOST_INT32(inode_id); } 37 38 39 void SetEntryLength(uint16 entryLength) 40 { entry_length = B_HOST_TO_LENDIAN_INT16(entryLength); } 41 } _PACKED; 42 43 struct HTreeCountLimit { 44 uint16 limit; 45 uint16 count; 46 47 uint16 Limit() const 48 { return B_LENDIAN_TO_HOST_INT16(limit); } 49 uint16 Count() const 50 { return B_LENDIAN_TO_HOST_INT16(count); } 51 bool IsFull() const 52 { return limit == count; } 53 54 void SetLimit(uint16 value) 55 { limit = B_HOST_TO_LENDIAN_INT16(value); } 56 57 void SetCount(uint16 value) 58 { count = B_HOST_TO_LENDIAN_INT16(value); } 59 } _PACKED; 60 61 struct HTreeEntry { 62 uint32 hash; 63 uint32 block; 64 65 uint32 Hash() const 66 { return B_LENDIAN_TO_HOST_INT32(hash); } 67 uint32 Block() const 68 { return B_LENDIAN_TO_HOST_INT32(block); } 69 70 void SetHash(uint32 newHash) 71 { hash = B_HOST_TO_LENDIAN_INT32(newHash); } 72 73 void SetBlock(uint32 newBlock) 74 { block = B_HOST_TO_LENDIAN_INT32(newBlock); } 75 } _PACKED; 76 77 struct HTreeRoot { 78 HTreeFakeDirEntry dot; 79 char dot_entry_name[4]; 80 HTreeFakeDirEntry dotdot; 81 char dotdot_entry_name[4]; 82 83 uint32 reserved; 84 uint8 hash_version; 85 uint8 root_info_length; 86 uint8 indirection_levels; 87 uint8 flags; 88 89 HTreeCountLimit count_limit[0]; 90 91 bool IsValid() const; 92 // Implemented in HTree.cpp 93 } _PACKED; 94 95 struct HTreeIndirectNode { 96 HTreeFakeDirEntry fake_entry; 97 HTreeEntry entries[0]; 98 } _PACKED; 99 100 101 /*! Hash implementations: 102 * References: 103 * Main reference: Linux htree patch: 104 * http://thunk.org/tytso/linux/ext3-dxdir/patch-ext3-dxdir-2.5.40 105 * Original MD4 hash: (Modified version used) 106 * http://tools.ietf.org/html/rfc1320 107 * TEA Wikipedia article: (Modified version used) 108 * http://en.wikipedia.org/Tiny_Encryption_Algorithm 109 */ 110 111 112 class HTree { 113 public: 114 HTree(Volume* volume, Inode* directory); 115 ~HTree(); 116 117 status_t PrepareForHash(); 118 uint32 Hash(const char* name, uint8 length); 119 120 status_t Lookup(const char* name, 121 DirectoryIterator** directory); 122 123 static status_t InitDir(Transaction& transaction, Inode* inode, 124 Inode* parent); 125 126 private: 127 status_t _LookupInNode(uint32 hash, off_t& firstEntry, 128 off_t& lastEntry, 129 uint32 remainingIndirects); 130 131 uint32 _HashLegacy(const char* name, uint8 length); 132 133 inline uint32 _MD4F(uint32 x, uint32 y, uint32 z); 134 inline uint32 _MD4G(uint32 x, uint32 y, uint32 z); 135 inline uint32 _MD4H(uint32 x, uint32 y, uint32 z); 136 inline void _MD4RotateVars(uint32& a, uint32& b, 137 uint32& c, uint32& d); 138 void _HalfMD4Transform(uint32 buffer[4], 139 uint32 blocks[8]); 140 uint32 _HashHalfMD4(const char* name, uint8 length); 141 142 void _TEATransform(uint32 buffer[4], 143 uint32 blocks[4]); 144 uint32 _HashTEA(const char* name, uint8 length); 145 146 void _PrepareBlocksForHash(const char* string, 147 uint32 length, uint32* blocks, uint32 numBlocks); 148 149 inline status_t _FallbackToLinearIteration( 150 DirectoryIterator** iterator); 151 152 bool fIndexed; 153 uint32 fBlockSize; 154 Inode* fDirectory; 155 uint8 fHashVersion; 156 uint32 fHashSeed[4]; 157 HTreeEntryIterator* fRootEntry; 158 ObjectDeleter<HTreeEntryIterator> fRootEntryDeleter; 159 }; 160 161 #endif // HTREE_H 162 163