Doom64 LZSS codec

def decode(data) -> bytes:
    """Decompress bytes-like data, returning a bytes object."""
    buf = iter(data)
    out = bytearray()
    cmd = 1
    while True:
        if cmd == 1:
            cmd = next(buf) | 0x100
        if cmd & 1:
            p = next(buf) << 4
            b = next(buf)
            p |= (b >> 4)
            b &= 0xF
            if not b:
                break
            p += 1
            for i in range(b+1):
                out.append(out[-p])
        else:
            out.append(next(buf))
        cmd >>= 1
    return bytes(out)


def length(data) -> (int, int):
    """Returns a tuple (compressed size, decompressed size),
    basically by running it through decompression."""
    cmd = 1
    out, pos = 0, 0
    while True:
        if cmd == 1:
            cmd = data[pos] | 0x100
            pos += 1
        if cmd & 1:
            b = data[pos+1]
            pos += 2
            b &= 0xF
            if not b:
                break
            out += b + 1
        else:
            out += 1
            pos += 1
        cmd >>= 1
    return (pos, out)


def _search(data, pos, sz, shoe=2, cap = 0x10, window=0x1000):
    """Returns (position, length) for sz length substring at pos.
    To recycle this code readily, shoe and cap set the min and max lengths,
    and window adjusts the maximum distance.  More cost-effective done here."""
    ml = min(cap, sz - pos)
    if ml < shoe:
        return 0, 0
    mp = max(0, pos - window)
    hitp, hitl = 0, shoe
    if mp < pos:
        hl = data[mp:pos+hitl].find(data[pos:pos+hitl])
        while hl < (pos - mp):
            while (hitl < ml) and (data[pos + hitl] == data[mp + hl + hitl]):
                hitl += 1
            mp += hl
            hitp = mp
            if hitl == ml:
                return hitp, hitl
            mp += 1
            hitl += 1
            if mp >= pos:
                break
            hl = data[mp:pos+hitl].find(data[pos:pos+hitl])
    # If length less than minimum length, return miss.
    if hitl <= shoe:
        hitl = 1
    return hitp, hitl-1

def encode(data) -> bytes:
    """Encodes data, returning a bytes object."""
    sz = len(data)
    out = bytearray(1)
    c, cmds = 0, 0
    pos, flag = 0, 1
    while pos < sz:
        hitp, hitl = _search(data, pos, sz)
        if hitl < 2:
            # Push a raw if copying isn't possible.
            out.append(data[pos])
            pos += 1
        else:
            # If the shoe fits, wear it...but check for a better fit ;*)
            tstp, tstl = _search(data, pos+1, sz)
            if (hitl + 1) < tstl:
                out.append(data[pos])
                pos += 1
                flag <<= 1
                if flag == 0x100:
                    out[cmds] = c
                    c, flag = 0, 1
                    cmds = len(out)
                    out.append(0)
                hitl = tstl
                hitp = tstp
            c |= flag
            e = pos - hitp - 1
            e &= 0xFFF
            pos += hitl
            hitl -= 1
            e <<= 4
            e |= hitl & 0xF
            out.append(e >> 8)
            out.append(e & 0xFF)
        # Advance the flag and refill if required.
        flag <<= 1
        if flag == 0x100:
            out[cmds] = c
            c, flag = 0, 1
            cmds = len(out)
            out.append(0)
    # File ends with a "dead" copy command.
    out.append(0)
    out.append(0)
    c |= flag
    out[cmds] = c
    return bytes(out)


def main():
    pass

if __name__ == '__main__':
    main()