x86 CALL is relative. that's why your PE compressor leaves money on the table

compress a Windows exe with gzip or with a "normal" LZ77 and the ratio is worse than the file deserves. not because PE is random. because the most repeated thing in the file — call some_helper — is encoded as a different 5-byte sequence every time it appears.

this is the E8/E9 filter. UPX has done it for decades. I didn't invent it. I finally put it in TinyLoad and the compressor stopped being the embarrassing part of the project.

the encoding that fights LZ

on x86-64, a direct near call is:

E8 xx xx xx xx

E8 then a 32-bit displacement from the next instruction. same for E9 (jmp).

so this C:

foo();
foo();
foo();

does not become three copies of the same bytes. it becomes three calls whose displacements differ by the distance between the call sites.

offset 0x100:  E8  FB 0E 00 00     ; foo is at 0x1000,  0x1000 - 0x105 = 0xEFB
offset 0x120:  E8  DB 0E 00 00     ; 0x1000 - 0x125 = 0xEDB
offset 0x140:  E8  BB 0E 00 00     ; 0x1000 - 0x145 = 0xEBB

LZ77 lives on repeated byte strings. those three 5-byte sequences share E8 and then diverge. the compressor emits three almost-literals instead of one match. multiply that by every call in .text and you have paid a tax on the densest, most redundant part of the binary.

the destinations were the same. the encoding hid that.

the 15-line fix

before matching, walk the buffer and add the file position into every apparent rel32:

static void lzflt(BYTE* b, size_t n) {
    for (size_t i = 0; i + 5 <= n; i++) {
        if (b[i] == 0xE8 || b[i] == 0xE9) {
            uint32_t v;
            memcpy(&v, b + i + 1, 4);
            v += (uint32_t)(i + 5);
            memcpy(b + i + 1, &v, 4);
            i += 4;
        }
    }
}

after the filter the three calls become:

E8 00 10 00 00
E8 00 10 00 00
E8 00 10 00 00

(assuming foo landed at file offset 0x1000 — the exact number doesn't matter. what matters is they are identical.)

now LZ77 sees a 5-byte match with distance 0x20. that is what a compressor is for.

undo it after inflate, same loop, subtract instead of add:

static void lzunflt(BYTE* b, size_t n) {
    for (size_t i = 0; i + 5 <= n; i++) {
        if (b[i] == 0xE8 || b[i] == 0xE9) {
            uint32_t v;
            memcpy(&v, b + i + 1, 4);
            v -= (uint32_t)(i + 5);
            memcpy(b + i + 1, &v, 4);
            i += 4;
        }
    }
}

the transform is its own inverse. you do not store extra metadata. if you filtered, you unfilter. the bitstream does not know this happened.

it is a heuristic, and that is the interesting part

the loop does not disassemble. it does not look at section flags. if it sees E8 and four bytes, it treats them as a rel32.

that is wrong some of the time:

• immediate constants that happen to start with E8 / E9
• .rdata / .data / overlay bytes
• x64 RIP-relative addressing is 48 8B 05 rel32 etc. — those rel32s sit behind a different opcode, so this particular filter misses them (and should, unless you also scan for those prefixes)

false positives are not fatal. you add i+5 on the way in and subtract it on the way out, so the bytes come back bit-identical even if that E8 was never a call. you only lose if the false-positive locations don't form a repeating pattern, in which case you turned four data bytes into four other data bytes and LZ is about as happy as before.

the real miss is the other way: calls you didn't catch. TinyLoad still runs this over the whole file, not just executable sections. that is the honest limitation. a PE-aware pass that only filters IMAGE_SCN_MEM_EXECUTE sections would cut false hits in data and still get the calls. I have not done that yet. the 15 lines were the 80%.

once the calls look the same, lazy LZ77 is the next bottleneck

the old TinyLoad compressor was: hash chain, 64KB window, lazy eval (look one or two bytes ahead). that is a fine first compressor. it is also the one every tutorial writes.

two things were still leaving matches on the table.

1. greedy/lazy parse is not optimal parse.

at position i you might have a length-5 match and, two bytes later, a length-40 match. taking the 5-byte match can block the 40. lazy eval catches the obvious version of this. it does not catch "emit two literals so a later match uses a distance I already used."

the current parse is reverse DP: from the end of the buffer, each position stores the cheapest (match or literal) given a cost model, then we retune the cost model from the parse and do it again. six passes. four different initial cost guesses, keep the best bitstream.

for variant in 4 cost guesses:
    for pass in 6:
        for i from n-1 down to 0:
            cost[i] = min(
                bits(literal at i) + cost[i+1],
                bits(match of length L, dist D) + cost[i+L]
                for each candidate (L,D) at i
            )
        rebuild huffman lengths from that parse
        use those lengths as the next cost model

this is the same idea as Zopfli / "optimal parse LZ", just smaller and angrier because it has to live in the same .cpp as a PE loader.

2. distances repeat.

PE code does not jump around uniformly. you call the same import thunks, you copy the same stack setup. DEFLATE noticed this in 1993: keep the last 4 distances and give them their own symbols (rep0..rep3). if the next match uses a distance you just used, you spend a short code instead of re-encoding the distance.

TinyLoad's distance alphabet is: 21 length-bucket symbols for a 1MB window, plus 4 repeat-distance symbols. same trick, smaller table.

then the literals and the (length, extra-bits) symbols go through a depth-limited canonical Huffman tree (max 15 bits, same cap as DEFLATE). code lengths are packed two nibbles per byte in the header so the decoder can rebuild the tree without a second format.

none of that helps much until the E8 filter makes the repeated calls actually repeated. you can optimal-parse all day; if the bytes don't match, there is nothing to parse.

what this is not

it is not a new algorithm. UPX's filter 0x26 / 0x36 / 0x46 family is this idea with more prefixes and more care. cabarc, some game packers, anything that has compressed x86 for a living.

it is also not "PE-aware compression" in the sense I keep promising. PE-aware would mean: don't waste match budget on the zero-padding between sections, maybe delta-encode relocs, maybe treat the import name table as its own stream. the E8 filter is the one transform that is both stupid-cheap and aimed at the actual instruction encoding.

why I'm writing this instead of "TinyLoad v7.4 dropped"

because the interesting object here is the instruction encoding, not the repo. a relative call is a good idea for a linker and a hostile input for a compressor. once you see that, you start seeing the rest of PE the same way — RVAs, import thunks, reloc blocks — and the compressor becomes a series of "undo the encoding, then LZ, then redo it."

source, including lzflt / lzunflt and the parse, is in one file:

https://github.com/iamsopotatoe-coder/TinyLoad

if you build it, --c is the compressor. --vm is a different article.