deitch/00-README Secret

## 00-README
This is an attempt to recreate the hash tree entries for a given actual filesystem.

I included a small part of `debugfs -R "htree_dump ..."`. It includes the root, the first intermeidate entries, and the leaf blocks.
That should be enough to walk through two examples with different hashes.

I picked `dir155`, `dir478`. The first is in the first leaf block (`Entry #0`) and the second is in the second leaf block (`Entry #1`).

If I understood it correctly, it means they should have the same hash `>= 0x00000000 && < 0x78b6e3b8` and different
minor hashes:

* `dir155` should have a minor hash `>= 0x00000000 && < 0x00f48688`
* `dir478` should have a minor hash `>= 0x00f48688 && < 0x01d79cd2`

In practice, running this program, I get:

```
'dir478  ' big endian 0xf6f8ed00 0x9badc917
'dir478  ' little endian 0xa02183aa 0x8aeccbf9
'dir478  ' little endian everything 0x5508c3a8 0x5a368183
'dir478  ' default 0x417265e4 0xf1aa5da7

'dir478' big endian 0x1a3bfd48 0x12dc18e0
'dir478' little endian 0x012225e2 0x3f08755d
'dir478' little endian everything 0xde57bedc 0x11b0ec31
'dir478' default 0x85d98a6a 0xb2a4a5d4

'dir155' big endian 0xe5e55c18 0xe79b7856
'dir155' little endian 0x00d11d98 0xb9b6b16b
'dir155' little endian everything 0x875c99c4 0x3c0ff545
'dir155' default 0x4dcd6bd2 0xdace5b4d

'dir155  ' big endian 0xf121845e 0x3dcaa3c4
'dir155  ' little endian 0x2b876520 0x4522abe0
'dir155  ' little endian everything 0x2ef2c5b6 0x4d4619d4
'dir155  ' default 0xf55d1b6c 0x86093cde
```

The actual correct value (from Ted's program) is:

```
dir478: retval=1, hash=0x012225e2, minor_hash=0x3f08755d
dir155: retval=2, hash=0x00d11d98, minor_hash=0xb9b6b16b
```

Clearly, "little-endian" is the way to go.

## dumpe2fs -h
dumpe2fs 1.46.2 (28-Feb-2021)
Filesystem volume name:   <none>
Last mounted on:          /mnt
Filesystem UUID:          bfb48e1c-af70-44d2-808c-f08284328250
Filesystem magic number:  0xEF53
Filesystem revision #:    1 (dynamic)
Filesystem features:      has_journal ext_attr resize_inode dir_index filetype needs_recovery extent 64bit flex_bg sparse_super large_file huge_file dir_nlink extra_isize metadata_csum
Filesystem flags:         signed_directory_hash
Default mount options:    user_xattr acl
Filesystem state:         clean
Errors behavior:          Continue
Filesystem OS type:       Linux
Inode count:              24384
Block count:              97656
Reserved block count:     4882
Overhead clusters:        11765
Free blocks:              85877
Free inodes:              24373
First block:              1
Block size:               1024
Fragment size:            1024
Group descriptor size:    64
Reserved GDT blocks:      256
Blocks per group:         8192
Fragments per group:      8192
Inodes per group:         2032
Inode blocks per group:   508
Flex block group size:    16
Filesystem created:       Sun Oct  3 07:35:45 2021
Last mount time:          Sun Oct  3 07:35:56 2021
Last write time:          Sun Oct  3 07:35:56 2021
Mount count:              1
Maximum mount count:      -1
Last checked:             Sun Oct  3 07:35:45 2021
Check interval:           0 (<none>)
Lifetime writes:          279 kB
Reserved blocks uid:      0 (user root)
Reserved blocks gid:      0 (group root)
First inode:              11
Inode size:	          256
Required extra isize:     32
Desired extra isize:      32
Journal inode:            8
Default directory hash:   half_md4
Directory Hash Seed:      d64563bc-ea93-4aaf-a943-4657711ed153
Journal backup:           inode blocks
Checksum type:            crc32c
Checksum:                 0x319a41d5
Journal features:         journal_64bit journal_checksum_v3
Total journal size:       4096k
Total journal blocks:     4096
Max transaction length:   4096
Fast commit length:       0
Journal sequence:         0x00000010
Journal start:            191
Journal checksum type:    crc32c
Journal checksum:         0x6e607f4e

## htree partial
  Root node dump:
         Reserved zero: 0
         Hash Version: 1
         Info length: 8
         Indirect levels: 1
         Flags: 0
Number of entries (count): 2
Number of entries (limit): 123
Checksum: 0x49f0afdc
Entry #0: Hash 0x00000000, block 124
Entry #1: Hash 0x78b6e3b8, block 128

Entry #0: Hash 0x00000000, block 124
Number of entries (count): 113
Number of entries (limit): 126
Checksum: 0x78407270
Entry #0: Hash 0x00000000, block 1
Entry #1: Hash 0x00f48688, block 193
Entry #2: Hash 0x01d79cd2, block 106
Entry #3: Hash 0x03683f9a, block 65
Entry #4: Hash 0x04ac5706, block 117
Entry #5: Hash 0x054ef51e, block 229
Entry #6: Hash 0x065308c4, block 28
Entry #7: Hash 0x079cd6ce, block 112

...

Entry #0: Hash 0x00000000, block 1
Reading directory block 1, phys 6459
168 0x00d11d98-b9b6b16b (16) dir155   332 0x009edafe-77de7d72 (16) dir319
751 0x006dafdc-6afa2778 (16) dir738   1059 0x00b0ab82-5a00d833 (16) dir1046
1212 0x006ae700-bca6f6d1 (16) dir1199   1228 0x001a18f4-57afcc8f (16) dir1215
1275 0x00c3d654-e82129c2 (16) dir1262   1629 0x0026b924-e52cfad3 (16) dir1616
2565 0x004ac982-dd64b725 (16) dir2552   2807 0x00b5ffce-a3ded238 (16) dir2794
2833 0x00868900-0ccabeeb (16) dir2820   3545 0x000191e8-0c5e3868 (16) dir3532
3623 0x00bdf402-49c4f856 (16) dir3610   4117 0x0001d3a0-4c221661 (16) dir4104
4459 0x00ba1688-1f47b1c5 (16) dir4446   4545 0x00342a40-99ca12d0 (16) dir4532
4852 0x0047241c-3428c5db (16) dir4839   5195 0x00ba60a0-46ef597f (16) dir5182
5740 0x00021d04-edcbb350 (16) dir5727   6011 0x004736d4-1b989a50 (16) dir5998
6146 0x004b27fc-ba8d696f (16) dir6133   6318 0x0098db80-b2d9597e (16) dir6305
6341 0x0018b3a4-849f2551 (16) dir6328   6366 0x005e00ba-a49338e5 (16) dir6353
6815 0x00d79b2a-74635907 (16) dir6802   7383 0x000560ec-b7c1daf1 (16) dir7370
7542 0x00b80b98-7a59047d (16) dir7529   7736 0x00755a8e-ee51760f (16) dir7723
7936 0x001188ca-fdea82e4 (16) dir7923   8234 0x0049ccd2-dfa33506 (16) dir8221
8274 0x009ec9c8-cb9908ef (16) dir8261   8774 0x00b17344-3770c751 (16) dir8761
8785 0x00dfc65e-7c8f9ea9 (16) dir8772   9027 0x00462d96-39baa6c5 (16) dir9014
9125 0x00bb422e-4d34f507 (16) dir9112   9269 0x00e08810-4ca93ffe (16) dir9256
9755 0x001d4f3e-a74b5f02 (16) dir9742
9854 0x00927210-b157233b (420) dir9841   leaf block checksum: 0x3f46833f

Entry #1: Hash 0x00f48688, block 193
Reading directory block 193, phys 15176
4241 0x00f48688-f520af73 (16) dir4228   5289 0x00fdde90-e7ed6279 (16) dir5276
7725 0x010e05a8-5690e3ed (16) dir7712   947 0x010f7606-a8879c44 (16) dir934
491 0x012225e2-3f08755d (16) dir478   7024 0x012d3e46-a37e0a33 (16) dir7011
3285 0x013a0a90-2291ddf9 (16) dir3272   3472 0x014c419c-6d3383fb (16) dir3459
5505 0x0150df6c-cbceba3c (16) dir5492   5990 0x015204b6-17f3a5b6 (16) dir5977
5670 0x0152fa00-820ba126 (16) dir5657   2080 0x01598a48-fdf4a1ee (16) dir2067
7375 0x015b1668-43d8d27d (16) dir7362   7140 0x0162c36c-56f57e2e (16) dir7127
3086 0x0164282a-69a6a93c (16) dir3073   7750 0x016f9990-b875cace (16) dir7737
5278 0x017004b4-6b7e5849 (16) dir5265   635 0x0174e118-c32b81a7 (16) dir622
3238 0x01790172-c2e2de0b (16) dir3225   3171 0x017a9bda-06da12d7 (16) dir3158
3486 0x017ce64c-55a5dace (16) dir3473   5658 0x017fdeac-a3b550ea (16) dir5645
5767 0x01810fc2-15cd0db9 (16) dir5754   6339 0x0193f890-256af9f3 (16) dir6326
8143 0x01a6a1aa-c23401ba (16) dir8130   799 0x01aab9f6-438ee9f3 (16) dir786
2035 0x01ba1b4c-9bfc0499 (16) dir2022   1486 0x01bb59c6-7d229002 (16) dir1473
5641 0x01bf8f9c-6634a7ff (16) dir5628   1930 0x01c13b76-cfd90b59 (16) dir1917
7404 0x01d24ac8-fdaea6cf (16) dir7391   1170 0x01d2e46e-59803ba8 (16) dir1157
8341 0x014e2896-132e95f6 (16) dir8328   8881 0x0103e2a0-a63682a5 (16) dir8868
8915 0x0121834c-abebf96d (16) dir8902   9039 0x011f521a-8367528e (16) dir9026
9129 0x01a5c6a6-da5663e2 (16) dir9116   9274 0x0162cbd4-0ee22734 (16) dir9261
9417 0x01b9bc06-d2ca54b5 (404) dir9404   leaf block checksum: 0x2acd1ec2

Entry #2: Hash 0x01d79cd2, block 106
Reading directory block 106, phys 11292
2722 0x01d79cd2-e4504fa7 (16) dir2709   2032 0x01dbd6f0-a7b596e1 (16) dir2019
404 0x01dc1b36-bb5f5db8 (16) dir391   3006 0x01e4d28c-19a4c7f4 (16) dir2993
3706 0x020452fc-4a640a7d (16) dir3693   40 0x020f0350-3f4c70a4 (16) dir27
3493 0x02252060-6fd336ea (16) dir3480   4037 0x022a0f68-8d9dff4d (16) dir4024
700 0x022cdc0e-c557c210 (16) dir687   2712 0x023628fe-f04d6773 (16) dir2699
3205 0x023c09ce-856a7490 (16) dir3192   2889 0x026bf58a-97919501 (16) dir2876
4247 0x02774826-00e603e7 (16) dir4234   2615 0x02797db6-288fd7c4 (16) dir2602
4406 0x028f5818-2b66bf57 (16) dir4393   128 0x029feafc-d866b9c5 (16) dir115
3482 0x02bc0ee6-5904f9af (16) dir3469   571 0x02bc9104-b6cebcc7 (16) dir558
2860 0x02c7ab58-42f9608b (16) dir2847   720 0x02cdca86-b2537515 (16) dir707
1266 0x0302e79c-554e5dcc (16) dir1253   4063 0x03032e6e-8057480d (16) dir4050
2204 0x03056008-787a1630 (16) dir2191   1111 0x030b89fc-3be18009 (16) dir1098
3093 0x03128820-5f065cff (16) dir3080   3313 0x031a1600-2394ab3e (16) dir3300
440 0x033d977a-5fec45ad (16) dir427   3794 0x033f5cbe-cd58b230 (16) dir3781
298 0x03427db6-0ed709e9 (16) dir285   2346 0x035ab6f2-aa90ce5d (16) dir2333
2773 0x035d8e0e-ba2de107 (16) dir2760   3674 0x035fc654-d12ccd45 (16) dir3661
4668 0x03552296-ec0ba75b (16) dir4655   4692 0x0346cf2c-07396d30 (16) dir4679
5105 0x027d05e0-63caac2e (16) dir5092   5127 0x031f9e90-5031fc0a (16) dir5114
5276 0x0350c0d8-5dcfe28d (16) dir5263   5486 0x029b8746-cb9b7979 (16) dir5473
5790 0x01faf240-6b389659 (16) dir5777   5980 0x01f259b0-a64f8402 (16) dir5967
5983 0x0347f5b0-da764772 (16) dir5970   6395 0x0214580a-a46dec3f (16) dir6382
6420 0x01eb197c-45eea61b (16) dir6407   6708 0x025e69a8-5f2885d7 (16) dir6695
6943 0x01e2a02a-f23884c6 (16) dir6930   6996 0x02d3e942-d7403167 (16) dir6983
7209 0x0214b3e6-1c8dcded (16) dir7196   7242 0x02eea7ec-31f61f9c (16) dir7229
7469 0x02615db2-c0de0f46 (16) dir7456   7572 0x0228ebcc-f9c02856 (16) dir7559
7651 0x029d8c3e-e0e25700 (16) dir7638   8216 0x02622cac-7c33f60f (16) dir8203
8651 0x0299a816-91b477f1 (16) dir8638   9327 0x02b89052-7cf6f732 (16) dir9314
9367 0x02241ee8-f2fc5c1d (16) dir9354   9411 0x021f3da8-b20945ae (16) dir9398
9516 0x02b0b8c2-e17714ac (116) dir9503   leaf block checksum: 0xbd88b5a6

Entry #3: Hash 0x03683f9a, block 65
Reading directory block 65, phys 9311
530 0x03683f9a-3e0fc171 (16) dir517   1726 0x037c96e8-726d4280 (16) dir1713
1283 0x03a01562-9ef2c1e5 (16) dir1270   1515 0x03a7c79c-a642ca76 (16) dir1502
2058 0x03b78c14-98b7463a (16) dir2045   1579 0x03d4b8aa-9a1bdf56 (16) dir1566
661 0x03f05178-ce3ec138 (16) dir648   757 0x040a8f66-b1737721 (16) dir744
135 0x0425cb68-de25d8e7 (16) dir122   2144 0x0427fa18-6f952a9b (16) dir2131
831 0x044d5f50-0e726859 (16) dir818   597 0x04665dc2-71b3c53a (16) dir584
595 0x0470fb72-e8927128 (16) dir582   776 0x04772b22-4d4a282d (16) dir763
2606 0x037ab4e2-1dc5d037 (16) dir2593   2652 0x04a10eb6-408523c5 (16) dir2639
2654 0x03b4b0d6-3ca79932 (16) dir2641   2763 0x03ed0b66-db62e007 (16) dir2750
3050 0x0427b100-ab21aaee (16) dir3037   3235 0x0382babe-4634e9ad (16) dir3222
3437 0x03f1d2e6-a5dafe50 (16) dir3424   3839 0x03ff7910-ab3e9c08 (16) dir3826
3961 0x03fab352-9c465552 (16) dir3948   4052 0x03da0070-39f65bd9 (16) dir4039
4100 0x03f0c5ec-b7d4c3ca (16) dir4087   4159 0x046045ce-65590cbd (16) dir4146
4378 0x0403d440-9b181754 (16) dir4365   4418 0x037305e0-6897ee6f (16) dir4405
4756 0x03f8e04a-4a860101 (16) dir4743   4782 0x04482e1c-65890307 (16) dir4769
4955 0x03ce1520-c891697d (16) dir4942   4979 0x036b3cc6-620fa38a (16) dir4966
5367 0x037838e6-f1cc0ce7 (16) dir5354   6137 0x045c6ec6-c4c1e6d0 (16) dir6124
6350 0x0465289a-1162efdb (16) dir6337   6551 0x0458b4da-211c872f (16) dir6538
6883 0x046882c0-b5930ac2 (16) dir6870   7357 0x0443fcc2-10e43c6b (16) dir7344
7674 0x03e7e61e-3ca9768b (16) dir7661   7714 0x0389dcc8-e5858a28 (16) dir7701
7738 0x042eaa8c-5ef6bc20 (16) dir7725   8181 0x0375acb0-daeb064e (16) dir8168
8203 0x0439b712-1eb4b9b2 (16) dir8190   8697 0x04a215f8-ef668860 (16) dir8684
8877 0x03d18ee4-2f28f3d7 (16) dir8864   9176 0x037383b8-10c1058e (16) dir9163
9196 0x03942d88-78726b10 (16) dir9183   9267 0x038f1efa-0a836119 (16) dir9254
9841 0x0384b11c-5468f698 (244) dir9828   leaf block checksum: 0x551b7685

## main.c
#include <string.h>
#include <stdio.h>


typedef unsigned int __u32;
typedef __u32 u32;

# define fallthrough

#define DX_HASH_LEGACY			0
#define DX_HASH_HALF_MD4		1
#define DX_HASH_TEA			2
#define DX_HASH_LEGACY_UNSIGNED		3
#define DX_HASH_HALF_MD4_UNSIGNED	4
#define DX_HASH_TEA_UNSIGNED		5
#define DX_HASH_SIPHASH			6

/* 32 and 64 bit signed EOF for dx directories */
#define EXT4_HTREE_EOF_32BIT   ((1UL  << (32 - 1)) - 1)
#define EXT4_HTREE_EOF_64BIT   ((1ULL << (64 - 1)) - 1)

struct dx_hash_info
{
	u32		hash;
	u32		minor_hash;
	int		hash_version;
	u32		*seed;
};


/**
 * rol32 - rotate a 32-bit value left
 * @word: value to rotate
 * @shift: bits to roll
 */
static inline __u32 rol32(__u32 word, unsigned int shift)
{
	return (word << (shift & 31)) | (word >> ((-shift) & 31));
}

#define DELTA 0x9E3779B9

static void TEA_transform(__u32 buf[4], __u32 const in[])
{
	__u32	sum = 0;
	__u32	b0 = buf[0], b1 = buf[1];
	__u32	a = in[0], b = in[1], c = in[2], d = in[3];
	int	n = 16;

	do {
		sum += DELTA;
		b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b);
		b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d);
	} while (--n);

	buf[0] += b0;
	buf[1] += b1;
}

/* F, G and H are basic MD4 functions: selection, majority, parity */
#define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
#define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z)))
#define H(x, y, z) ((x) ^ (y) ^ (z))

/*
 * The generic round function.  The application is so specific that
 * we don't bother protecting all the arguments with parens, as is generally
 * good macro practice, in favor of extra legibility.
 * Rotation is separate from addition to prevent recomputation
 */
#define ROUND(f, a, b, c, d, x, s)	\
	(a += f(b, c, d) + x, a = rol32(a, s))
#define K1 0
#define K2 013240474631UL
#define K3 015666365641UL

/*
 * Basic cut-down MD4 transform.  Returns only 32 bits of result.
 */
static __u32 half_md4_transform(__u32 buf[4], __u32 const in[8])
{
	__u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3];

	/* Round 1 */
	ROUND(F, a, b, c, d, in[0] + K1,  3);
	ROUND(F, d, a, b, c, in[1] + K1,  7);
	ROUND(F, c, d, a, b, in[2] + K1, 11);
	ROUND(F, b, c, d, a, in[3] + K1, 19);
	ROUND(F, a, b, c, d, in[4] + K1,  3);
	ROUND(F, d, a, b, c, in[5] + K1,  7);
	ROUND(F, c, d, a, b, in[6] + K1, 11);
	ROUND(F, b, c, d, a, in[7] + K1, 19);

	/* Round 2 */
	ROUND(G, a, b, c, d, in[1] + K2,  3);
	ROUND(G, d, a, b, c, in[3] + K2,  5);
	ROUND(G, c, d, a, b, in[5] + K2,  9);
	ROUND(G, b, c, d, a, in[7] + K2, 13);
	ROUND(G, a, b, c, d, in[0] + K2,  3);
	ROUND(G, d, a, b, c, in[2] + K2,  5);
	ROUND(G, c, d, a, b, in[4] + K2,  9);
	ROUND(G, b, c, d, a, in[6] + K2, 13);

	/* Round 3 */
	ROUND(H, a, b, c, d, in[3] + K3,  3);
	ROUND(H, d, a, b, c, in[7] + K3,  9);
	ROUND(H, c, d, a, b, in[2] + K3, 11);
	ROUND(H, b, c, d, a, in[6] + K3, 15);
	ROUND(H, a, b, c, d, in[1] + K3,  3);
	ROUND(H, d, a, b, c, in[5] + K3,  9);
	ROUND(H, c, d, a, b, in[0] + K3, 11);
	ROUND(H, b, c, d, a, in[4] + K3, 15);

	buf[0] += a;
	buf[1] += b;
	buf[2] += c;
	buf[3] += d;

	return buf[1]; /* "most hashed" word */
}

/* The old legacy hash */
static __u32 dx_hack_hash_unsigned(const char *name, int len)
{
	__u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
	const unsigned char *ucp = (const unsigned char *) name;

	while (len--) {
		hash = hash1 + (hash0 ^ (((int) *ucp++) * 7152373));

		if (hash & 0x80000000)
			hash -= 0x7fffffff;
		hash1 = hash0;
		hash0 = hash;
	}
	return hash0 << 1;
}

static __u32 dx_hack_hash_signed(const char *name, int len)
{
	__u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
	const signed char *scp = (const signed char *) name;

	while (len--) {
		hash = hash1 + (hash0 ^ (((int) *scp++) * 7152373));

		if (hash & 0x80000000)
			hash -= 0x7fffffff;
		hash1 = hash0;
		hash0 = hash;
	}
	return hash0 << 1;
}

static void str2hashbuf_signed(const char *msg, int len, __u32 *buf, int num)
{
	__u32	pad, val;
	int	i;
	const signed char *scp = (const signed char *) msg;

	pad = (__u32)len | ((__u32)len << 8);
	pad |= pad << 16;

	val = pad;
	if (len > num*4)
		len = num * 4;
	for (i = 0; i < len; i++) {
		val = ((int) scp[i]) + (val << 8);
		if ((i % 4) == 3) {
			*buf++ = val;
			val = pad;
			num--;
		}
	}
	if (--num >= 0)
		*buf++ = val;
	while (--num >= 0)
		*buf++ = pad;
}

static void str2hashbuf_unsigned(const char *msg, int len, __u32 *buf, int num)
{
	__u32	pad, val;
	int	i;
	const unsigned char *ucp = (const unsigned char *) msg;

	pad = (__u32)len | ((__u32)len << 8);
	pad |= pad << 16;

	val = pad;
	if (len > num*4)
		len = num * 4;
	for (i = 0; i < len; i++) {
		val = ((int) ucp[i]) + (val << 8);
		if ((i % 4) == 3) {
			*buf++ = val;
			val = pad;
			num--;
		}
	}
	if (--num >= 0)
		*buf++ = val;
	while (--num >= 0)
		*buf++ = pad;
}

/*
 * Returns the hash of a filename.  If len is 0 and name is NULL, then
 * this function can be used to test whether or not a hash version is
 * supported.
 *
 * The seed is an 4 longword (32 bits) "secret" which can be used to
 * uniquify a hash.  If the seed is all zero's, then some default seed
 * may be used.
 *
 * A particular hash version specifies whether or not the seed is
 * represented, and whether or not the returned hash is 32 bits or 64
 * bits.  32 bit hashes will return 0 for the minor hash.
 */
static int __ext4fs_dirhash(const char *name, int len, struct dx_hash_info *hinfo)
{
	__u32	hash;
	__u32	minor_hash = 0;
	const char	*p;
	int		i;
	__u32		in[8], buf[4];
	void		(*str2hashbuf)(const char *, int, __u32 *, int) =
				str2hashbuf_signed;

	/* Initialize the default seed for the hash checksum functions */
	buf[0] = 0x67452301;
	buf[1] = 0xefcdab89;
	buf[2] = 0x98badcfe;
	buf[3] = 0x10325476;

	/* Check to see if the seed is all zero's */
	if (hinfo->seed) {
		for (i = 0; i < 4; i++) {
			if (hinfo->seed[i]) {
				memcpy(buf, hinfo->seed, sizeof(buf));
				break;
			}
		}
	}

	switch (hinfo->hash_version) {
	case DX_HASH_LEGACY_UNSIGNED:
		hash = dx_hack_hash_unsigned(name, len);
		break;
	case DX_HASH_LEGACY:
		hash = dx_hack_hash_signed(name, len);
		break;
	case DX_HASH_HALF_MD4_UNSIGNED:
		str2hashbuf = str2hashbuf_unsigned;
		fallthrough;
	case DX_HASH_HALF_MD4:
		p = name;
		while (len > 0) {
			(*str2hashbuf)(p, len, in, 8);
			half_md4_transform(buf, in);
			len -= 32;
			p += 32;
		}
		minor_hash = buf[2];
		hash = buf[1];
		break;
	case DX_HASH_TEA_UNSIGNED:
		str2hashbuf = str2hashbuf_unsigned;
		fallthrough;
	case DX_HASH_TEA:
		p = name;
		while (len > 0) {
			(*str2hashbuf)(p, len, in, 4);
			TEA_transform(buf, in);
			len -= 16;
			p += 16;
		}
		hash = buf[0];
		minor_hash = buf[1];
		break;
	default:
		hinfo->hash = 0;
		return -1;
	}
	hash = hash & ~1;
	if (hash == (EXT4_HTREE_EOF_32BIT << 1))
		hash = (EXT4_HTREE_EOF_32BIT - 1) << 1;
	hinfo->hash = hash;
	hinfo->minor_hash = minor_hash;
	return 0;
}


static void calculate(char *name) {
    struct dx_hash_info hinfo;
    hinfo.hash_version = DX_HASH_HALF_MD4;
    __u32           buf[4];
    // actual bytes at 0x04ec of size __le32[4]
    // d645 63bc ea93 4aaf a943 4657 711e d153
    //
    // this matches exactly with what dumpe2fs gives
    // Directory Hash Seed:      d64563bc-ea93-4aaf-a943-4657711ed153

    // if we assume these to be big endian
    buf[0] = 0xd64563bc;
    buf[1] = 0xea934aaf;
    buf[2] = 0xa9434657;
    buf[3] = 0x711ed153;

    hinfo.seed = buf;
    __ext4fs_dirhash(name, strlen(name), &hinfo);
    printf("'%s' big endian %#010x %#010x\n", name, hinfo.hash, hinfo.minor_hash);

    // if we assume these to be 4 u32 in order, but little-endian
    buf[0] = 0xbc6345d6;
    buf[1] = 0xaf4a93ea;
    buf[2] = 0x574643a9;
    buf[3] = 0x53d11e71;

    hinfo.seed = buf;
    __ext4fs_dirhash(name, strlen(name), &hinfo);
    printf("'%s' little endian %#010x %#010x\n", name, hinfo.hash, hinfo.minor_hash);

    // if we assume it to be one big little-endian array, which makes no sense, but who knows?
    buf[3] = 0xbc6345d6;
    buf[2] = 0xaf4a93ea;
    buf[1] = 0x574643a9;
    buf[0] = 0x53d11e71;
    hinfo.seed = buf;
    __ext4fs_dirhash(name, strlen(name), &hinfo);
    printf("'%s' little endian everything %#010x %#010x\n", name, hinfo.hash, hinfo.minor_hash);

    // and to use the default
    buf[3] = 0x0;
    buf[2] = 0x0;
    buf[1] = 0x0;
    buf[0] = 0x0;
    hinfo.seed = buf;
    __ext4fs_dirhash(name, strlen(name), &hinfo);
    printf("'%s' default %#010x %#010x\n", name, hinfo.hash, hinfo.minor_hash);
}

int main(int argc, char *argv[]) {
    int i;

    for (i = 1; i < argc; i++) {
      calculate(argv[i]);
      printf("\n");
    }
}

## main.go
package ext4

const (
	teaDelta       uint32 = 0x9E3779B9
	k1             uint32 = 0
	k2             uint32 = 013240474631
	k3             uint32 = 015666365641
	ext4HtreeEOF32 uint32 = ((1 << (32 - 1)) - 1)
	ext4HtreeEOF64 uint64 = ((1 << (64 - 1)) - 1)
)

type hashVersion uint8

const (
	HashVersionLegacy          = 0
	HashVersionHalfMD4         = 1
	HashVersionTEA             = 2
	HashVersionLegacyUnsigned  = 3
	HashVersionHalfMD4Unsigned = 4
	HashVersionTEAUnsigned     = 5
	HashVersionSIP             = 6
)

func TEATransform(buf [4]uint32, in []uint32) [4]uint32 {
	var sum uint32
	var b0, b1 = buf[0], buf[1]
	var a, b, c, d = in[0], in[1], in[2], in[3]
	var n int = 16

	for ; n > 0; n-- {
		sum += teaDelta
		b0 += ((b1 << 4) + a) ^ (b1 + sum) ^ ((b1 >> 5) + b)
		b1 += ((b0 << 4) + c) ^ (b0 + sum) ^ ((b0 >> 5) + d)
	}

	buf[0] += b0
	buf[1] += b1
	return buf
}

// rol32 - rotate a 32-bit value left
func rol32(word uint32, shift uint) uint32 {
	return (word << (shift & 31)) | (word >> ((-shift) & 31))
}

// F, G and H are basic MD4 functions: selection, majority, parity */
func f(x, y, z uint32) uint32 {
	return ((z) ^ ((x) & ((y) ^ (z))))
}
func g(x, y, z uint32) uint32 {
	return (((x) & (y)) + (((x) ^ (y)) & (z)))
}
func h(x, y, z uint32) uint32 {
	return ((x) ^ (y) ^ (z))
}

func round(f func(uint32, uint32, uint32) uint32, a, b, c, d, x uint32, s uint) uint32 {
	return rol32(a+f(b, c, d)+x, s)
}

// halfMD4Transform basic cut-down MD4 transform.  Returns only 32 bits of result.
func halfMD4Transform(buf [4]uint32, in []uint32) [4]uint32 {
	var a, b, c, d uint32 = buf[0], buf[1], buf[2], buf[3]

	/* Round 1 */
	a = round(f, a, b, c, d, in[0]+k1, 3)
	d = round(f, d, a, b, c, in[1]+k1, 7)
	c = round(f, c, d, a, b, in[2]+k1, 11)
	b = round(f, b, c, d, a, in[3]+k1, 19)
	a = round(f, a, b, c, d, in[4]+k1, 3)
	d = round(f, d, a, b, c, in[5]+k1, 7)
	c = round(f, c, d, a, b, in[6]+k1, 11)
	b = round(f, b, c, d, a, in[7]+k1, 19)

	/* Round 2 */
	a = round(g, a, b, c, d, in[1]+k2, 3)
	d = round(g, d, a, b, c, in[3]+k2, 5)
	c = round(g, c, d, a, b, in[5]+k2, 9)
	b = round(g, b, c, d, a, in[7]+k2, 13)
	a = round(g, a, b, c, d, in[0]+k2, 3)
	d = round(g, d, a, b, c, in[2]+k2, 5)
	c = round(g, c, d, a, b, in[4]+k2, 9)
	b = round(g, b, c, d, a, in[6]+k2, 13)

	/* Round 3 */
	a = round(h, a, b, c, d, in[3]+k3, 3)
	d = round(h, d, a, b, c, in[7]+k3, 9)
	c = round(h, c, d, a, b, in[2]+k3, 11)
	b = round(h, b, c, d, a, in[6]+k3, 15)
	a = round(h, a, b, c, d, in[1]+k3, 3)
	d = round(h, d, a, b, c, in[5]+k3, 9)
	c = round(h, c, d, a, b, in[0]+k3, 11)
	b = round(h, b, c, d, a, in[4]+k3, 15)

	buf[0] += a
	buf[1] += b
	buf[2] += c
	buf[3] += d

	return buf
}

// the old legacy hash
func dxHackHash(name string, signed bool) uint32 {
	var hash uint32
	var hash0, hash1 uint32 = 0x12a3fe2d, 0x37abe8f9
	b := []byte(name)

	for i := len(b); i > 0; i-- {
		// get the specific character
		var c int
		if signed {
			c = int(int8(b[i-1]))
		} else {
			c = int(uint8(b[i-1]))
		}
		// the value of the individual character depends on if it is signed or not
		hash = hash1 + (hash0 ^ uint32(c*7152373))

		if hash&0x80000000 != 0 {
			hash -= 0x7fffffff
		}
		hash1 = hash0
		hash0 = hash
	}
	return hash0 << 1
}

func str2hashbuf(msg string, num int, signed bool) []uint32 {
	var buf [8]uint32
	var pad, val uint32
	b := []byte(msg)
	size := len(b)

	pad = uint32(size) | (uint32(size) << 8)
	pad |= pad << 16

	val = pad
	if size > num*4 {
		size = num * 4
	}
	var j int
	for i := 0; i < size; i++ {
		var c int
		if signed {
			c = int(int8(b[i]))
		} else {
			c = int(uint8(b[i]))
		}
		val = uint32(c) + (val << 8)
		if (i % 4) == 3 {
			buf[j] = val
			val = pad
			num--
			j++
		}
	}
	num--
	if num >= 0 {
		buf[j] = val
		j++
	}
	for num--; num >= 0; num-- {
		buf[j] = pad
		j++
	}
	return buf[:]
}

func ext4fsDirhash(name string, version hashVersion, seed []uint32) (uint32, uint32) {
	var hash, minorHash uint32
	/* Initialize the default seed for the hash checksum functions */
	var buf = [4]uint32{0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476}

	// Check to see if the seed is all zero, and if so, use the default
	for i, val := range seed {
		if val != 0 {
			buf[i] = val
		}
	}

	switch version {
	case HashVersionLegacyUnsigned:
		hash = dxHackHash(name, false)
	case HashVersionLegacy:
		hash = dxHackHash(name, true)
	case HashVersionHalfMD4Unsigned:
		for i := 0; i < len(name); i += 32 {
			in := str2hashbuf(name[i:], 8, false)
			buf = halfMD4Transform(buf, in)
		}
		minorHash = buf[2]
		hash = buf[1]
	case HashVersionHalfMD4:
		for i := 0; i < len(name); i += 32 {
			in := str2hashbuf(name[i:], 8, true)
			buf = halfMD4Transform(buf, in)
		}
		minorHash = buf[2]
		hash = buf[1]
	case HashVersionTEAUnsigned:
		for i := 0; i < len(name); i += 16 {
			in := str2hashbuf(name[i:], 4, false)
			buf = TEATransform(buf, in)
		}
		hash = buf[0]
		minorHash = buf[1]
	case HashVersionTEA:
		for i := 0; i < len(name); i += 16 {
			in := str2hashbuf(name[i:], 4, true)
			buf = TEATransform(buf, in)
		}
		hash = buf[0]
		minorHash = buf[1]
	default:
		return 0, 0
	}
	hash = hash & ^uint32(1)
	if hash == (ext4HtreeEOF32 << 1) {
		hash = (ext4HtreeEOF32 - 1) << 1
	}
	return hash, minorHash
}

## works.c
// courtesy of Ted Ts'o
// to compile: gcc -g -o md4 works.c -luuid -lext2fs -lcom_err
// for alpine prerequisites: apk add gcc libc-dev e2fsprogs-dev

#include <stdio.h>
#include <stdlib.h>

#include <et/com_err.h>
#include <uuid/uuid.h>
#include <ext2fs/ext2_fs.h>
#include <ext2fs/ext2fs.h>

int main(int argc, char **argv)
{
        uuid_t  buf;
        unsigned int *p;
        int i;
        ext2_dirhash_t hash, minor_hash;
        errcode_t retval;

        uuid_parse("d64563bc-ea93-4aaf-a943-4657711ed153", buf);
        p = (unsigned int *) buf;
        for (i=0; i < 4; i++) {
                printf("buf[%d] = 0x%08x\n", i, p[i]);
        }

        for (i=1; i<argc; i++) {
          retval = ext2fs_dirhash(1, argv[i], strlen(argv[i]), p,
                                  &hash, &minor_hash);
          printf("%s: retval=%u, hash=0x%08x, minor_hash=0x%08x\n",
                 argv[i], i, hash, minor_hash);
        }

        exit(0);
}
	This is an attempt to recreate the hash tree entries for a given actual filesystem.

	I included a small part of `debugfs -R "htree_dump ..."`. It includes the root, the first intermeidate entries, and the leaf blocks.
	That should be enough to walk through two examples with different hashes.

	I picked `dir155`, `dir478`. The first is in the first leaf block (`Entry #0`) and the second is in the second leaf block (`Entry #1`).

	If I understood it correctly, it means they should have the same hash `>= 0x00000000 && < 0x78b6e3b8` and different
	minor hashes:

	* `dir155` should have a minor hash `>= 0x00000000 && < 0x00f48688`
	* `dir478` should have a minor hash `>= 0x00f48688 && < 0x01d79cd2`

	In practice, running this program, I get:

	```
	'dir478 ' big endian 0xf6f8ed00 0x9badc917
	'dir478 ' little endian 0xa02183aa 0x8aeccbf9
	'dir478 ' little endian everything 0x5508c3a8 0x5a368183
	'dir478 ' default 0x417265e4 0xf1aa5da7

	'dir478' big endian 0x1a3bfd48 0x12dc18e0
	'dir478' little endian 0x012225e2 0x3f08755d
	'dir478' little endian everything 0xde57bedc 0x11b0ec31
	'dir478' default 0x85d98a6a 0xb2a4a5d4

	'dir155' big endian 0xe5e55c18 0xe79b7856
	'dir155' little endian 0x00d11d98 0xb9b6b16b
	'dir155' little endian everything 0x875c99c4 0x3c0ff545
	'dir155' default 0x4dcd6bd2 0xdace5b4d

	'dir155 ' big endian 0xf121845e 0x3dcaa3c4
	'dir155 ' little endian 0x2b876520 0x4522abe0
	'dir155 ' little endian everything 0x2ef2c5b6 0x4d4619d4
	'dir155 ' default 0xf55d1b6c 0x86093cde
	```

	The actual correct value (from Ted's program) is:

	```
	dir478: retval=1, hash=0x012225e2, minor_hash=0x3f08755d
	dir155: retval=2, hash=0x00d11d98, minor_hash=0xb9b6b16b
	```

	Clearly, "little-endian" is the way to go.
	dumpe2fs 1.46.2 (28-Feb-2021)
	Filesystem volume name: <none>
	Last mounted on: /mnt
	Filesystem UUID: bfb48e1c-af70-44d2-808c-f08284328250
	Filesystem magic number: 0xEF53
	Filesystem revision #: 1 (dynamic)
	Filesystem features: has_journal ext_attr resize_inode dir_index filetype needs_recovery extent 64bit flex_bg sparse_super large_file huge_file dir_nlink extra_isize metadata_csum
	Filesystem flags: signed_directory_hash
	Default mount options: user_xattr acl
	Filesystem state: clean
	Errors behavior: Continue
	Filesystem OS type: Linux
	Inode count: 24384
	Block count: 97656
	Reserved block count: 4882
	Overhead clusters: 11765
	Free blocks: 85877
	Free inodes: 24373
	First block: 1
	Block size: 1024
	Fragment size: 1024
	Group descriptor size: 64
	Reserved GDT blocks: 256
	Blocks per group: 8192
	Fragments per group: 8192
	Inodes per group: 2032
	Inode blocks per group: 508
	Flex block group size: 16
	Filesystem created: Sun Oct 3 07:35:45 2021
	Last mount time: Sun Oct 3 07:35:56 2021
	Last write time: Sun Oct 3 07:35:56 2021
	Mount count: 1
	Maximum mount count: -1
	Last checked: Sun Oct 3 07:35:45 2021
	Check interval: 0 (<none>)
	Lifetime writes: 279 kB
	Reserved blocks uid: 0 (user root)
	Reserved blocks gid: 0 (group root)
	First inode: 11
	Inode size: 256
	Required extra isize: 32
	Desired extra isize: 32
	Journal inode: 8
	Default directory hash: half_md4
	Directory Hash Seed: d64563bc-ea93-4aaf-a943-4657711ed153
	Journal backup: inode blocks
	Checksum type: crc32c
	Checksum: 0x319a41d5
	Journal features: journal_64bit journal_checksum_v3
	Total journal size: 4096k
	Total journal blocks: 4096
	Max transaction length: 4096
	Fast commit length: 0
	Journal sequence: 0x00000010
	Journal start: 191
	Journal checksum type: crc32c
	Journal checksum: 0x6e607f4e
	Root node dump:
	Reserved zero: 0
	Hash Version: 1
	Info length: 8
	Indirect levels: 1
	Flags: 0
	Number of entries (count): 2
	Number of entries (limit): 123
	Checksum: 0x49f0afdc
	Entry #0: Hash 0x00000000, block 124
	Entry #1: Hash 0x78b6e3b8, block 128

	Entry #0: Hash 0x00000000, block 124
	Number of entries (count): 113
	Number of entries (limit): 126
	Checksum: 0x78407270
	Entry #0: Hash 0x00000000, block 1
	Entry #1: Hash 0x00f48688, block 193
	Entry #2: Hash 0x01d79cd2, block 106
	Entry #3: Hash 0x03683f9a, block 65
	Entry #4: Hash 0x04ac5706, block 117
	Entry #5: Hash 0x054ef51e, block 229
	Entry #6: Hash 0x065308c4, block 28
	Entry #7: Hash 0x079cd6ce, block 112

	...

	Entry #0: Hash 0x00000000, block 1
	Reading directory block 1, phys 6459
	168 0x00d11d98-b9b6b16b (16) dir155 332 0x009edafe-77de7d72 (16) dir319
	751 0x006dafdc-6afa2778 (16) dir738 1059 0x00b0ab82-5a00d833 (16) dir1046
	1212 0x006ae700-bca6f6d1 (16) dir1199 1228 0x001a18f4-57afcc8f (16) dir1215
	1275 0x00c3d654-e82129c2 (16) dir1262 1629 0x0026b924-e52cfad3 (16) dir1616
	2565 0x004ac982-dd64b725 (16) dir2552 2807 0x00b5ffce-a3ded238 (16) dir2794
	2833 0x00868900-0ccabeeb (16) dir2820 3545 0x000191e8-0c5e3868 (16) dir3532
	3623 0x00bdf402-49c4f856 (16) dir3610 4117 0x0001d3a0-4c221661 (16) dir4104
	4459 0x00ba1688-1f47b1c5 (16) dir4446 4545 0x00342a40-99ca12d0 (16) dir4532
	4852 0x0047241c-3428c5db (16) dir4839 5195 0x00ba60a0-46ef597f (16) dir5182
	5740 0x00021d04-edcbb350 (16) dir5727 6011 0x004736d4-1b989a50 (16) dir5998
	6146 0x004b27fc-ba8d696f (16) dir6133 6318 0x0098db80-b2d9597e (16) dir6305
	6341 0x0018b3a4-849f2551 (16) dir6328 6366 0x005e00ba-a49338e5 (16) dir6353
	6815 0x00d79b2a-74635907 (16) dir6802 7383 0x000560ec-b7c1daf1 (16) dir7370
	7542 0x00b80b98-7a59047d (16) dir7529 7736 0x00755a8e-ee51760f (16) dir7723
	7936 0x001188ca-fdea82e4 (16) dir7923 8234 0x0049ccd2-dfa33506 (16) dir8221
	8274 0x009ec9c8-cb9908ef (16) dir8261 8774 0x00b17344-3770c751 (16) dir8761
	8785 0x00dfc65e-7c8f9ea9 (16) dir8772 9027 0x00462d96-39baa6c5 (16) dir9014
	9125 0x00bb422e-4d34f507 (16) dir9112 9269 0x00e08810-4ca93ffe (16) dir9256
	9755 0x001d4f3e-a74b5f02 (16) dir9742
	9854 0x00927210-b157233b (420) dir9841 leaf block checksum: 0x3f46833f

	Entry #1: Hash 0x00f48688, block 193
	Reading directory block 193, phys 15176
	4241 0x00f48688-f520af73 (16) dir4228 5289 0x00fdde90-e7ed6279 (16) dir5276
	7725 0x010e05a8-5690e3ed (16) dir7712 947 0x010f7606-a8879c44 (16) dir934
	491 0x012225e2-3f08755d (16) dir478 7024 0x012d3e46-a37e0a33 (16) dir7011
	3285 0x013a0a90-2291ddf9 (16) dir3272 3472 0x014c419c-6d3383fb (16) dir3459
	5505 0x0150df6c-cbceba3c (16) dir5492 5990 0x015204b6-17f3a5b6 (16) dir5977
	5670 0x0152fa00-820ba126 (16) dir5657 2080 0x01598a48-fdf4a1ee (16) dir2067
	7375 0x015b1668-43d8d27d (16) dir7362 7140 0x0162c36c-56f57e2e (16) dir7127
	3086 0x0164282a-69a6a93c (16) dir3073 7750 0x016f9990-b875cace (16) dir7737
	5278 0x017004b4-6b7e5849 (16) dir5265 635 0x0174e118-c32b81a7 (16) dir622
	3238 0x01790172-c2e2de0b (16) dir3225 3171 0x017a9bda-06da12d7 (16) dir3158
	3486 0x017ce64c-55a5dace (16) dir3473 5658 0x017fdeac-a3b550ea (16) dir5645
	5767 0x01810fc2-15cd0db9 (16) dir5754 6339 0x0193f890-256af9f3 (16) dir6326
	8143 0x01a6a1aa-c23401ba (16) dir8130 799 0x01aab9f6-438ee9f3 (16) dir786
	2035 0x01ba1b4c-9bfc0499 (16) dir2022 1486 0x01bb59c6-7d229002 (16) dir1473
	5641 0x01bf8f9c-6634a7ff (16) dir5628 1930 0x01c13b76-cfd90b59 (16) dir1917
	7404 0x01d24ac8-fdaea6cf (16) dir7391 1170 0x01d2e46e-59803ba8 (16) dir1157
	8341 0x014e2896-132e95f6 (16) dir8328 8881 0x0103e2a0-a63682a5 (16) dir8868
	8915 0x0121834c-abebf96d (16) dir8902 9039 0x011f521a-8367528e (16) dir9026
	9129 0x01a5c6a6-da5663e2 (16) dir9116 9274 0x0162cbd4-0ee22734 (16) dir9261
	9417 0x01b9bc06-d2ca54b5 (404) dir9404 leaf block checksum: 0x2acd1ec2

	Entry #2: Hash 0x01d79cd2, block 106
	Reading directory block 106, phys 11292
	2722 0x01d79cd2-e4504fa7 (16) dir2709 2032 0x01dbd6f0-a7b596e1 (16) dir2019
	404 0x01dc1b36-bb5f5db8 (16) dir391 3006 0x01e4d28c-19a4c7f4 (16) dir2993
	3706 0x020452fc-4a640a7d (16) dir3693 40 0x020f0350-3f4c70a4 (16) dir27
	3493 0x02252060-6fd336ea (16) dir3480 4037 0x022a0f68-8d9dff4d (16) dir4024
	700 0x022cdc0e-c557c210 (16) dir687 2712 0x023628fe-f04d6773 (16) dir2699
	3205 0x023c09ce-856a7490 (16) dir3192 2889 0x026bf58a-97919501 (16) dir2876
	4247 0x02774826-00e603e7 (16) dir4234 2615 0x02797db6-288fd7c4 (16) dir2602
	4406 0x028f5818-2b66bf57 (16) dir4393 128 0x029feafc-d866b9c5 (16) dir115
	3482 0x02bc0ee6-5904f9af (16) dir3469 571 0x02bc9104-b6cebcc7 (16) dir558
	2860 0x02c7ab58-42f9608b (16) dir2847 720 0x02cdca86-b2537515 (16) dir707
	1266 0x0302e79c-554e5dcc (16) dir1253 4063 0x03032e6e-8057480d (16) dir4050
	2204 0x03056008-787a1630 (16) dir2191 1111 0x030b89fc-3be18009 (16) dir1098
	3093 0x03128820-5f065cff (16) dir3080 3313 0x031a1600-2394ab3e (16) dir3300
	440 0x033d977a-5fec45ad (16) dir427 3794 0x033f5cbe-cd58b230 (16) dir3781
	298 0x03427db6-0ed709e9 (16) dir285 2346 0x035ab6f2-aa90ce5d (16) dir2333
	2773 0x035d8e0e-ba2de107 (16) dir2760 3674 0x035fc654-d12ccd45 (16) dir3661
	4668 0x03552296-ec0ba75b (16) dir4655 4692 0x0346cf2c-07396d30 (16) dir4679
	5105 0x027d05e0-63caac2e (16) dir5092 5127 0x031f9e90-5031fc0a (16) dir5114
	5276 0x0350c0d8-5dcfe28d (16) dir5263 5486 0x029b8746-cb9b7979 (16) dir5473
	5790 0x01faf240-6b389659 (16) dir5777 5980 0x01f259b0-a64f8402 (16) dir5967
	5983 0x0347f5b0-da764772 (16) dir5970 6395 0x0214580a-a46dec3f (16) dir6382
	6420 0x01eb197c-45eea61b (16) dir6407 6708 0x025e69a8-5f2885d7 (16) dir6695
	6943 0x01e2a02a-f23884c6 (16) dir6930 6996 0x02d3e942-d7403167 (16) dir6983
	7209 0x0214b3e6-1c8dcded (16) dir7196 7242 0x02eea7ec-31f61f9c (16) dir7229
	7469 0x02615db2-c0de0f46 (16) dir7456 7572 0x0228ebcc-f9c02856 (16) dir7559
	7651 0x029d8c3e-e0e25700 (16) dir7638 8216 0x02622cac-7c33f60f (16) dir8203
	8651 0x0299a816-91b477f1 (16) dir8638 9327 0x02b89052-7cf6f732 (16) dir9314
	9367 0x02241ee8-f2fc5c1d (16) dir9354 9411 0x021f3da8-b20945ae (16) dir9398
	9516 0x02b0b8c2-e17714ac (116) dir9503 leaf block checksum: 0xbd88b5a6

	Entry #3: Hash 0x03683f9a, block 65
	Reading directory block 65, phys 9311
	530 0x03683f9a-3e0fc171 (16) dir517 1726 0x037c96e8-726d4280 (16) dir1713
	1283 0x03a01562-9ef2c1e5 (16) dir1270 1515 0x03a7c79c-a642ca76 (16) dir1502
	2058 0x03b78c14-98b7463a (16) dir2045 1579 0x03d4b8aa-9a1bdf56 (16) dir1566
	661 0x03f05178-ce3ec138 (16) dir648 757 0x040a8f66-b1737721 (16) dir744
	135 0x0425cb68-de25d8e7 (16) dir122 2144 0x0427fa18-6f952a9b (16) dir2131
	831 0x044d5f50-0e726859 (16) dir818 597 0x04665dc2-71b3c53a (16) dir584
	595 0x0470fb72-e8927128 (16) dir582 776 0x04772b22-4d4a282d (16) dir763
	2606 0x037ab4e2-1dc5d037 (16) dir2593 2652 0x04a10eb6-408523c5 (16) dir2639
	2654 0x03b4b0d6-3ca79932 (16) dir2641 2763 0x03ed0b66-db62e007 (16) dir2750
	3050 0x0427b100-ab21aaee (16) dir3037 3235 0x0382babe-4634e9ad (16) dir3222
	3437 0x03f1d2e6-a5dafe50 (16) dir3424 3839 0x03ff7910-ab3e9c08 (16) dir3826
	3961 0x03fab352-9c465552 (16) dir3948 4052 0x03da0070-39f65bd9 (16) dir4039
	4100 0x03f0c5ec-b7d4c3ca (16) dir4087 4159 0x046045ce-65590cbd (16) dir4146
	4378 0x0403d440-9b181754 (16) dir4365 4418 0x037305e0-6897ee6f (16) dir4405
	4756 0x03f8e04a-4a860101 (16) dir4743 4782 0x04482e1c-65890307 (16) dir4769
	4955 0x03ce1520-c891697d (16) dir4942 4979 0x036b3cc6-620fa38a (16) dir4966
	5367 0x037838e6-f1cc0ce7 (16) dir5354 6137 0x045c6ec6-c4c1e6d0 (16) dir6124
	6350 0x0465289a-1162efdb (16) dir6337 6551 0x0458b4da-211c872f (16) dir6538
	6883 0x046882c0-b5930ac2 (16) dir6870 7357 0x0443fcc2-10e43c6b (16) dir7344
	7674 0x03e7e61e-3ca9768b (16) dir7661 7714 0x0389dcc8-e5858a28 (16) dir7701
	7738 0x042eaa8c-5ef6bc20 (16) dir7725 8181 0x0375acb0-daeb064e (16) dir8168
	8203 0x0439b712-1eb4b9b2 (16) dir8190 8697 0x04a215f8-ef668860 (16) dir8684
	8877 0x03d18ee4-2f28f3d7 (16) dir8864 9176 0x037383b8-10c1058e (16) dir9163
	9196 0x03942d88-78726b10 (16) dir9183 9267 0x038f1efa-0a836119 (16) dir9254
	9841 0x0384b11c-5468f698 (244) dir9828 leaf block checksum: 0x551b7685
	#include <string.h>
	#include <stdio.h>


	typedef unsigned int __u32;
	typedef __u32 u32;

	# define fallthrough

	#define DX_HASH_LEGACY 0
	#define DX_HASH_HALF_MD4 1
	#define DX_HASH_TEA 2
	#define DX_HASH_LEGACY_UNSIGNED 3
	#define DX_HASH_HALF_MD4_UNSIGNED 4
	#define DX_HASH_TEA_UNSIGNED 5
	#define DX_HASH_SIPHASH 6

	/* 32 and 64 bit signed EOF for dx directories */
	#define EXT4_HTREE_EOF_32BIT ((1UL << (32 - 1)) - 1)
	#define EXT4_HTREE_EOF_64BIT ((1ULL << (64 - 1)) - 1)

	struct dx_hash_info
	{
	u32 hash;
	u32 minor_hash;
	int hash_version;
	u32 *seed;
	};


	/**
	* rol32 - rotate a 32-bit value left
	* @word: value to rotate
	* @shift: bits to roll
	*/
	static inline __u32 rol32(__u32 word, unsigned int shift)
	{
	return (word << (shift & 31)) \| (word >> ((-shift) & 31));
	}

	#define DELTA 0x9E3779B9

	static void TEA_transform(__u32 buf[4], __u32 const in[])
	{
	__u32 sum = 0;
	__u32 b0 = buf[0], b1 = buf[1];
	__u32 a = in[0], b = in[1], c = in[2], d = in[3];
	int n = 16;

	do {
	sum += DELTA;
	b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b);
	b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d);
	} while (--n);

	buf[0] += b0;
	buf[1] += b1;
	}

	/* F, G and H are basic MD4 functions: selection, majority, parity */
	#define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
	#define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z)))
	#define H(x, y, z) ((x) ^ (y) ^ (z))

	/*
	* The generic round function. The application is so specific that
	* we don't bother protecting all the arguments with parens, as is generally
	* good macro practice, in favor of extra legibility.
	* Rotation is separate from addition to prevent recomputation
	*/
	#define ROUND(f, a, b, c, d, x, s) \
	(a += f(b, c, d) + x, a = rol32(a, s))
	#define K1 0
	#define K2 013240474631UL
	#define K3 015666365641UL

	/*
	* Basic cut-down MD4 transform. Returns only 32 bits of result.
	*/
	static __u32 half_md4_transform(__u32 buf[4], __u32 const in[8])
	{
	__u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3];

	/* Round 1 */
	ROUND(F, a, b, c, d, in[0] + K1, 3);
	ROUND(F, d, a, b, c, in[1] + K1, 7);
	ROUND(F, c, d, a, b, in[2] + K1, 11);
	ROUND(F, b, c, d, a, in[3] + K1, 19);
	ROUND(F, a, b, c, d, in[4] + K1, 3);
	ROUND(F, d, a, b, c, in[5] + K1, 7);
	ROUND(F, c, d, a, b, in[6] + K1, 11);
	ROUND(F, b, c, d, a, in[7] + K1, 19);

	/* Round 2 */
	ROUND(G, a, b, c, d, in[1] + K2, 3);
	ROUND(G, d, a, b, c, in[3] + K2, 5);
	ROUND(G, c, d, a, b, in[5] + K2, 9);
	ROUND(G, b, c, d, a, in[7] + K2, 13);
	ROUND(G, a, b, c, d, in[0] + K2, 3);
	ROUND(G, d, a, b, c, in[2] + K2, 5);
	ROUND(G, c, d, a, b, in[4] + K2, 9);
	ROUND(G, b, c, d, a, in[6] + K2, 13);

	/* Round 3 */
	ROUND(H, a, b, c, d, in[3] + K3, 3);
	ROUND(H, d, a, b, c, in[7] + K3, 9);
	ROUND(H, c, d, a, b, in[2] + K3, 11);
	ROUND(H, b, c, d, a, in[6] + K3, 15);
	ROUND(H, a, b, c, d, in[1] + K3, 3);
	ROUND(H, d, a, b, c, in[5] + K3, 9);
	ROUND(H, c, d, a, b, in[0] + K3, 11);
	ROUND(H, b, c, d, a, in[4] + K3, 15);

	buf[0] += a;
	buf[1] += b;
	buf[2] += c;
	buf[3] += d;

	return buf[1]; /* "most hashed" word */
	}

	/* The old legacy hash */
	static __u32 dx_hack_hash_unsigned(const char *name, int len)
	{
	__u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
	const unsigned char ucp = (const unsigned char ) name;

	while (len--) {
	hash = hash1 + (hash0 ^ (((int) ucp++) 7152373));

	if (hash & 0x80000000)
	hash -= 0x7fffffff;
	hash1 = hash0;
	hash0 = hash;
	}
	return hash0 << 1;
	}

	static __u32 dx_hack_hash_signed(const char *name, int len)
	{
	__u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
	const signed char scp = (const signed char ) name;

	while (len--) {
	hash = hash1 + (hash0 ^ (((int) scp++) 7152373));

	if (hash & 0x80000000)
	hash -= 0x7fffffff;
	hash1 = hash0;
	hash0 = hash;
	}
	return hash0 << 1;
	}

	static void str2hashbuf_signed(const char msg, int len, __u32 buf, int num)
	{
	__u32 pad, val;
	int i;
	const signed char scp = (const signed char ) msg;

	pad = (__u32)len \| ((__u32)len << 8);
	pad \|= pad << 16;

	val = pad;
	if (len > num*4)
	len = num * 4;
	for (i = 0; i < len; i++) {
	val = ((int) scp[i]) + (val << 8);
	if ((i % 4) == 3) {
	*buf++ = val;
	val = pad;
	num--;
	}
	}
	if (--num >= 0)
	*buf++ = val;
	while (--num >= 0)
	*buf++ = pad;
	}

	static void str2hashbuf_unsigned(const char msg, int len, __u32 buf, int num)
	{
	__u32 pad, val;
	int i;
	const unsigned char ucp = (const unsigned char ) msg;

	pad = (__u32)len \| ((__u32)len << 8);
	pad \|= pad << 16;

	val = pad;
	if (len > num*4)
	len = num * 4;
	for (i = 0; i < len; i++) {
	val = ((int) ucp[i]) + (val << 8);
	if ((i % 4) == 3) {
	*buf++ = val;
	val = pad;
	num--;
	}
	}
	if (--num >= 0)
	*buf++ = val;
	while (--num >= 0)
	*buf++ = pad;
	}

	/*
	* Returns the hash of a filename. If len is 0 and name is NULL, then
	* this function can be used to test whether or not a hash version is
	* supported.
	*
	* The seed is an 4 longword (32 bits) "secret" which can be used to
	* uniquify a hash. If the seed is all zero's, then some default seed
	* may be used.
	*
	* A particular hash version specifies whether or not the seed is
	* represented, and whether or not the returned hash is 32 bits or 64
	* bits. 32 bit hashes will return 0 for the minor hash.
	*/
	static int __ext4fs_dirhash(const char name, int len, struct dx_hash_info hinfo)
	{
	__u32 hash;
	__u32 minor_hash = 0;
	const char *p;
	int i;
	__u32 in[8], buf[4];
	void (str2hashbuf)(const char , int, __u32 *, int) =
	str2hashbuf_signed;

	/* Initialize the default seed for the hash checksum functions */
	buf[0] = 0x67452301;
	buf[1] = 0xefcdab89;
	buf[2] = 0x98badcfe;
	buf[3] = 0x10325476;

	/* Check to see if the seed is all zero's */
	if (hinfo->seed) {
	for (i = 0; i < 4; i++) {
	if (hinfo->seed[i]) {
	memcpy(buf, hinfo->seed, sizeof(buf));
	break;
	}
	}
	}

	switch (hinfo->hash_version) {
	case DX_HASH_LEGACY_UNSIGNED:
	hash = dx_hack_hash_unsigned(name, len);
	break;
	case DX_HASH_LEGACY:
	hash = dx_hack_hash_signed(name, len);
	break;
	case DX_HASH_HALF_MD4_UNSIGNED:
	str2hashbuf = str2hashbuf_unsigned;
	fallthrough;
	case DX_HASH_HALF_MD4:
	p = name;
	while (len > 0) {
	(*str2hashbuf)(p, len, in, 8);
	half_md4_transform(buf, in);
	len -= 32;
	p += 32;
	}
	minor_hash = buf[2];
	hash = buf[1];
	break;
	case DX_HASH_TEA_UNSIGNED:
	str2hashbuf = str2hashbuf_unsigned;
	fallthrough;
	case DX_HASH_TEA:
	p = name;
	while (len > 0) {
	(*str2hashbuf)(p, len, in, 4);
	TEA_transform(buf, in);
	len -= 16;
	p += 16;
	}
	hash = buf[0];
	minor_hash = buf[1];
	break;
	default:
	hinfo->hash = 0;
	return -1;
	}
	hash = hash & ~1;
	if (hash == (EXT4_HTREE_EOF_32BIT << 1))
	hash = (EXT4_HTREE_EOF_32BIT - 1) << 1;
	hinfo->hash = hash;
	hinfo->minor_hash = minor_hash;
	return 0;
	}


	static void calculate(char *name) {
	struct dx_hash_info hinfo;
	hinfo.hash_version = DX_HASH_HALF_MD4;
	__u32 buf[4];
	// actual bytes at 0x04ec of size __le32[4]
	// d645 63bc ea93 4aaf a943 4657 711e d153
	//
	// this matches exactly with what dumpe2fs gives
	// Directory Hash Seed: d64563bc-ea93-4aaf-a943-4657711ed153

	// if we assume these to be big endian
	buf[0] = 0xd64563bc;
	buf[1] = 0xea934aaf;
	buf[2] = 0xa9434657;
	buf[3] = 0x711ed153;

	hinfo.seed = buf;
	__ext4fs_dirhash(name, strlen(name), &hinfo);
	printf("'%s' big endian %#010x %#010x\n", name, hinfo.hash, hinfo.minor_hash);

	// if we assume these to be 4 u32 in order, but little-endian
	buf[0] = 0xbc6345d6;
	buf[1] = 0xaf4a93ea;
	buf[2] = 0x574643a9;
	buf[3] = 0x53d11e71;

	hinfo.seed = buf;
	__ext4fs_dirhash(name, strlen(name), &hinfo);
	printf("'%s' little endian %#010x %#010x\n", name, hinfo.hash, hinfo.minor_hash);

	// if we assume it to be one big little-endian array, which makes no sense, but who knows?
	buf[3] = 0xbc6345d6;
	buf[2] = 0xaf4a93ea;
	buf[1] = 0x574643a9;
	buf[0] = 0x53d11e71;
	hinfo.seed = buf;
	__ext4fs_dirhash(name, strlen(name), &hinfo);
	printf("'%s' little endian everything %#010x %#010x\n", name, hinfo.hash, hinfo.minor_hash);

	// and to use the default
	buf[3] = 0x0;
	buf[2] = 0x0;
	buf[1] = 0x0;
	buf[0] = 0x0;
	hinfo.seed = buf;
	__ext4fs_dirhash(name, strlen(name), &hinfo);
	printf("'%s' default %#010x %#010x\n", name, hinfo.hash, hinfo.minor_hash);
	}

	int main(int argc, char *argv[]) {
	int i;

	for (i = 1; i < argc; i++) {
	calculate(argv[i]);
	printf("\n");
	}
	}
	package ext4

	const (
	teaDelta uint32 = 0x9E3779B9
	k1 uint32 = 0
	k2 uint32 = 013240474631
	k3 uint32 = 015666365641
	ext4HtreeEOF32 uint32 = ((1 << (32 - 1)) - 1)
	ext4HtreeEOF64 uint64 = ((1 << (64 - 1)) - 1)
	)

	type hashVersion uint8

	const (
	HashVersionLegacy = 0
	HashVersionHalfMD4 = 1
	HashVersionTEA = 2
	HashVersionLegacyUnsigned = 3
	HashVersionHalfMD4Unsigned = 4
	HashVersionTEAUnsigned = 5
	HashVersionSIP = 6
	)

	func TEATransform(buf [4]uint32, in []uint32) [4]uint32 {
	var sum uint32
	var b0, b1 = buf[0], buf[1]
	var a, b, c, d = in[0], in[1], in[2], in[3]
	var n int = 16

	for ; n > 0; n-- {
	sum += teaDelta
	b0 += ((b1 << 4) + a) ^ (b1 + sum) ^ ((b1 >> 5) + b)
	b1 += ((b0 << 4) + c) ^ (b0 + sum) ^ ((b0 >> 5) + d)
	}

	buf[0] += b0
	buf[1] += b1
	return buf
	}

	// rol32 - rotate a 32-bit value left
	func rol32(word uint32, shift uint) uint32 {
	return (word << (shift & 31)) \| (word >> ((-shift) & 31))
	}

	// F, G and H are basic MD4 functions: selection, majority, parity */
	func f(x, y, z uint32) uint32 {
	return ((z) ^ ((x) & ((y) ^ (z))))
	}
	func g(x, y, z uint32) uint32 {
	return (((x) & (y)) + (((x) ^ (y)) & (z)))
	}
	func h(x, y, z uint32) uint32 {
	return ((x) ^ (y) ^ (z))
	}

	func round(f func(uint32, uint32, uint32) uint32, a, b, c, d, x uint32, s uint) uint32 {
	return rol32(a+f(b, c, d)+x, s)
	}

	// halfMD4Transform basic cut-down MD4 transform. Returns only 32 bits of result.
	func halfMD4Transform(buf [4]uint32, in []uint32) [4]uint32 {
	var a, b, c, d uint32 = buf[0], buf[1], buf[2], buf[3]

	/* Round 1 */
	a = round(f, a, b, c, d, in[0]+k1, 3)
	d = round(f, d, a, b, c, in[1]+k1, 7)
	c = round(f, c, d, a, b, in[2]+k1, 11)
	b = round(f, b, c, d, a, in[3]+k1, 19)
	a = round(f, a, b, c, d, in[4]+k1, 3)
	d = round(f, d, a, b, c, in[5]+k1, 7)
	c = round(f, c, d, a, b, in[6]+k1, 11)
	b = round(f, b, c, d, a, in[7]+k1, 19)

	/* Round 2 */
	a = round(g, a, b, c, d, in[1]+k2, 3)
	d = round(g, d, a, b, c, in[3]+k2, 5)
	c = round(g, c, d, a, b, in[5]+k2, 9)
	b = round(g, b, c, d, a, in[7]+k2, 13)
	a = round(g, a, b, c, d, in[0]+k2, 3)
	d = round(g, d, a, b, c, in[2]+k2, 5)
	c = round(g, c, d, a, b, in[4]+k2, 9)
	b = round(g, b, c, d, a, in[6]+k2, 13)

	/* Round 3 */
	a = round(h, a, b, c, d, in[3]+k3, 3)
	d = round(h, d, a, b, c, in[7]+k3, 9)
	c = round(h, c, d, a, b, in[2]+k3, 11)
	b = round(h, b, c, d, a, in[6]+k3, 15)
	a = round(h, a, b, c, d, in[1]+k3, 3)
	d = round(h, d, a, b, c, in[5]+k3, 9)
	c = round(h, c, d, a, b, in[0]+k3, 11)
	b = round(h, b, c, d, a, in[4]+k3, 15)

	buf[0] += a
	buf[1] += b
	buf[2] += c
	buf[3] += d

	return buf
	}

	// the old legacy hash
	func dxHackHash(name string, signed bool) uint32 {
	var hash uint32
	var hash0, hash1 uint32 = 0x12a3fe2d, 0x37abe8f9
	b := []byte(name)

	for i := len(b); i > 0; i-- {
	// get the specific character
	var c int
	if signed {
	c = int(int8(b[i-1]))
	} else {
	c = int(uint8(b[i-1]))
	}
	// the value of the individual character depends on if it is signed or not
	hash = hash1 + (hash0 ^ uint32(c*7152373))

	if hash&0x80000000 != 0 {
	hash -= 0x7fffffff
	}
	hash1 = hash0
	hash0 = hash
	}
	return hash0 << 1
	}

	func str2hashbuf(msg string, num int, signed bool) []uint32 {
	var buf [8]uint32
	var pad, val uint32
	b := []byte(msg)
	size := len(b)

	pad = uint32(size) \| (uint32(size) << 8)
	pad \|= pad << 16

	val = pad
	if size > num*4 {
	size = num * 4
	}
	var j int
	for i := 0; i < size; i++ {
	var c int
	if signed {
	c = int(int8(b[i]))
	} else {
	c = int(uint8(b[i]))
	}
	val = uint32(c) + (val << 8)
	if (i % 4) == 3 {
	buf[j] = val
	val = pad
	num--
	j++
	}
	}
	num--
	if num >= 0 {
	buf[j] = val
	j++
	}
	for num--; num >= 0; num-- {
	buf[j] = pad
	j++
	}
	return buf[:]
	}

	func ext4fsDirhash(name string, version hashVersion, seed []uint32) (uint32, uint32) {
	var hash, minorHash uint32
	/* Initialize the default seed for the hash checksum functions */
	var buf = [4]uint32{0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476}

	// Check to see if the seed is all zero, and if so, use the default
	for i, val := range seed {
	if val != 0 {
	buf[i] = val
	}
	}

	switch version {
	case HashVersionLegacyUnsigned:
	hash = dxHackHash(name, false)
	case HashVersionLegacy:
	hash = dxHackHash(name, true)
	case HashVersionHalfMD4Unsigned:
	for i := 0; i < len(name); i += 32 {
	in := str2hashbuf(name[i:], 8, false)
	buf = halfMD4Transform(buf, in)
	}
	minorHash = buf[2]
	hash = buf[1]
	case HashVersionHalfMD4:
	for i := 0; i < len(name); i += 32 {
	in := str2hashbuf(name[i:], 8, true)
	buf = halfMD4Transform(buf, in)
	}
	minorHash = buf[2]
	hash = buf[1]
	case HashVersionTEAUnsigned:
	for i := 0; i < len(name); i += 16 {
	in := str2hashbuf(name[i:], 4, false)
	buf = TEATransform(buf, in)
	}
	hash = buf[0]
	minorHash = buf[1]
	case HashVersionTEA:
	for i := 0; i < len(name); i += 16 {
	in := str2hashbuf(name[i:], 4, true)
	buf = TEATransform(buf, in)
	}
	hash = buf[0]
	minorHash = buf[1]
	default:
	return 0, 0
	}
	hash = hash & ^uint32(1)
	if hash == (ext4HtreeEOF32 << 1) {
	hash = (ext4HtreeEOF32 - 1) << 1
	}
	return hash, minorHash
	}
	// courtesy of Ted Ts'o
	// to compile: gcc -g -o md4 works.c -luuid -lext2fs -lcom_err
	// for alpine prerequisites: apk add gcc libc-dev e2fsprogs-dev

	#include <stdio.h>
	#include <stdlib.h>

	#include <et/com_err.h>
	#include <uuid/uuid.h>
	#include <ext2fs/ext2_fs.h>
	#include <ext2fs/ext2fs.h>

	int main(int argc, char **argv)
	{
	uuid_t buf;
	unsigned int *p;
	int i;
	ext2_dirhash_t hash, minor_hash;
	errcode_t retval;

	uuid_parse("d64563bc-ea93-4aaf-a943-4657711ed153", buf);
	p = (unsigned int *) buf;
	for (i=0; i < 4; i++) {
	printf("buf[%d] = 0x%08x\n", i, p[i]);
	}

	for (i=1; i<argc; i++) {
	retval = ext2fs_dirhash(1, argv[i], strlen(argv[i]), p,
	&hash, &minor_hash);
	printf("%s: retval=%u, hash=0x%08x, minor_hash=0x%08x\n",
	argv[i], i, hash, minor_hash);
	}

	exit(0);
	}