lz4probe.py

#!/usr/bin/env python3
"""Tolerant LZ4 *block* decoder for spelunking.

Standard decoders demand a known output size and abort on the first
inconsistency. For reverse engineering we want the opposite: decode as far as
the stream stays self-consistent, then report where it stopped.
"""
import sys, re


def lz4_block_decode(src, start=0, limit=1 << 22):
    out = bytearray()
    i = start
    n = len(src)
    while i < n and len(out) < limit:
        tok = src[i]; i += 1
        lit = tok >> 4
        if lit == 15:
            while i < n:
                b = src[i]; i += 1
                lit += b
                if b != 255:
                    break
            else:
                break
        if i + lit > n:
            break
        out += src[i:i + lit]
        i += lit
        if i + 2 > n:
            break                      # last block legally ends on literals
        off = src[i] | (src[i + 1] << 8)
        i += 2
        if off == 0 or off > len(out):
            i -= 2
            break                      # invalid back-reference: stop cleanly
        ml = tok & 0x0F
        if ml == 15:
            while i < n:
                b = src[i]; i += 1
                ml += b
                if b != 255:
                    break
            else:
                break
        ml += 4
        p = len(out) - off
        for _ in range(ml):            # byte-wise: overlapping matches are legal
            out.append(out[p]); p += 1
    return bytes(out), i


def printable_ratio(b):
    if not b:
        return 0.0
    return sum(1 for x in b if 32 <= x < 127 or x in (9, 10, 13)) / len(b)


def scan(path, lo, hi, min_out=256, step=1):
    d = open(path, "rb").read()
    hits = []
    for s in range(lo, hi, step):
        out, end = lz4_block_decode(d, s, limit=1 << 20)
        if len(out) >= min_out and (end - s) > 64:
            ratio = len(out) / max(1, end - s)
            hits.append((s, end, len(out), ratio, printable_ratio(out)))
    # keep only local maxima so we report block starts, not every offset inside
    best = []
    for h in sorted(hits, key=lambda x: -x[2]):
        if all(abs(h[0] - b[0]) > 32 for b in best):
            best.append(h)
    return sorted(best)


if __name__ == "__main__":
    path = sys.argv[1]
    lo = int(sys.argv[2], 0)
    hi = int(sys.argv[3], 0)
    print(f"scanning {path} {lo:#x}..{hi:#x}")
    for s, e, n, ratio, pr in scan(path, lo, hi)[:25]:
        print(f"  block@{s:#08x} consumed={e-s:<6} out={n:<7} ratio={ratio:5.2f} printable={pr:.2f}")