Received-SPF: pass (google.com: domain of linux-ext4-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
MIME-Version: 1.0
References: <CAF1vpkgPAy3FJ9mN22OVQ41jQAYoRdoCdqzYwRYYPXD4uucdpg@mail.gmail.com>
 <3A493D20-568A-4D63-A575-5DEEBFAAF41A@dilger.ca> <CAF1vpkigHMdKphnNjDm7=rR6TTxViHGGHi3bb64rsHG7KbqYzQ@mail.gmail.com>
 <CAF1vpkhwSOfGfErUUrp0YU5hSt58TtykTECiJXTcgqDtG0WVVg@mail.gmail.com>
 <YWSck57bsX/LqAKr@mit.edu> <CAF1vpkiKx3jArgjNBrid9-MSHBweGsFL0zu0UgDX_dq_hrkUgw@mail.gmail.com>
 <YWXGRgfxJZMe9iut@mit.edu>
In-Reply-To: <YWXGRgfxJZMe9iut@mit.edu>
From:   Avi Deitcher <avi@deitcher.net>
Date:   Tue, 12 Oct 2021 19:20:26 -0700
Message-ID: <CAF1vpkidOGm0OmRac+OqaXcnJptn1O22OLHXJZoPfEbhxb3Ttw@mail.gmail.com>
Subject: Re: algorithm for half-md4 used in htree directories
To:     "Theodore Ts'o" <tytso@mit.edu>
Cc:     linux-ext4@vger.kernel.org
Content-Type: text/plain; charset="UTF-8"
Precedence: bulk

Yep, right here
https://git.kernel.org/pub/scm/fs/ext2/e2fsprogs.git/tree/lib/ext2fs/dirhash.c

Hey, that's your name on it, Ted!

I am close, must be messing it up somehow. I literally copied the
majority of that (actually, some slight variant, but basically the
same) into a standalone main.c, removed any library dependencies by
copying those in so I can get a standalone, and I still am not quite
getting it. Maybe I am messing up the seed?

dump2fs of the superblock shows:

Default directory hash:   half_md4
Directory Hash Seed:      d64563bc-ea93-4aaf-a943-4657711ed153

and debugfs of the hash tree shows:

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
...

So it has the hash version correct (I also gdb-ed through my little
program. Maybe I am getting the u32 order wrong in the seed? Or the
endianness?

I should just create a gist with this, shouldn't I?

On Tue, Oct 12, 2021 at 10:30 AM Theodore Ts'o <tytso@mit.edu> wrote:
>
> On Mon, Oct 11, 2021 at 07:58:00PM -0700, Avi Deitcher wrote:
> > Aha. I missed that the seed is injected into buf before passing it
> > into half_md4_transform. I was looking at it as just the empty buffer
> > before the first iteration of the loop (or, in my case, since I was
> > testing with a 6 char filename, the only iteration).
> >
> > I will repeat my experiment with that and see if I can tease it out.
>
> BTW, if you are looking for a userspace implementation of the hash,
> it's available in libext2fs in e2fsprogs.
>
> Cheers,
>
>                                         - Ted


-- 
Avi Deitcher
avi@deitcher.net
Follow me http://twitter.com/avideitcher
Read me http://blog.atomicinc.com