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