parsematcher.py

import struct
import dataclasses

@dataclasses.dataclass
class Node:
    node_delta: int | None
    mask_delta: int
    terminal: bool
    value: int | None = None

    @classmethod
    def parse(cls, data: bytes):
        opt, nxt = struct.unpack("<Hh", data)
        terminal = (opt & 4) != 0
        if terminal:
            return cls(node_delta=None, mask_delta=None, terminal=True, value=nxt)
        if (opt & 2) == 0:
            nxt = -nxt
        md = opt & ~7
        if (opt & 1) == 0:
            md = -md
        return cls(node_delta=nxt-4, mask_delta=md-16, terminal=False)

NODES_ADDR = 0x2DE00
NODES_BEGIN = 0x13E8
MASK_ADDR = 0x2D2E0
MASK_BEGIN = 0x760

fp = open("usr/lib/x86_64-linux-gnu/liblzma.so.5.6.0", "rb")

def node_at(node_offset, idx):
    fp.seek(NODES_ADDR + node_offset + 4 * idx)
    return Node.parse(fp.read(4))

def mask_at(offset):
    fp.seek(MASK_ADDR + offset)
    lo, hi = struct.unpack("<QQ", fp.read(16))
    return (hi << 64) | lo

def match(data: bytes) -> int | None:
    data = data[:44]
    noff = NODES_BEGIN
    moff = MASK_BEGIN
    for v in data:
        if v >= 128:
            return
        print(f"{v=:x} {noff=} {moff=}", end=" ")
        mask = mask_at(moff)
        print(f"mask={bin(mask)[2:]}", end=" ")
        if (mask >> v) & 1 == 0:
            # No match
            return
        pos = (mask & ((1 << v) - 1)).bit_count()
        print(f"{pos=}")
        node = node_at(noff, pos)
        if node.terminal:
            return node.value
        print(f"{node.node_delta=} {node.mask_delta=}")
        noff += node.node_delta
        moff += node.mask_delta
    return

# print(hex(match(b"\x7FELF")))

def dfs(nbegin=NODES_BEGIN, moff=MASK_BEGIN, cur=b""):
    mask = mask_at(moff)
    pos = 0
    for i in range(128):
        if (mask >> i) & 1 == 0:
            continue
        node = node_at(nbegin, pos)
        pos += 1
        nxt = cur + bytes([i])
        if node.terminal:
            print(hex(node.value), nxt)
        else:
            dfs(nbegin + node.node_delta, moff + node.mask_delta, nxt)

dfs()