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
25struct JournalRevokeHeader;
26
27
28struct 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
43struct 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
61struct 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
77struct 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
95struct 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
112class HTree {
113public:
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
126private:
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