Decode the x86-64 subset

Stage 2 of 8. This stage applies Disassembly and Control Flow, sections "The Instruction Format Has One Rule Per Field" and "Linear Sweep".

What you build

You build a decoder for the part of x86-64 that clang emits for the fixtures at -O0 and -O1. decode(code, address) reads one instruction and returns an Instruction with its bytes, a normalized operation, its operands, its operand width, its control-flow kind and its branch target. It also records where the displacement field and the immediate field sit inside the instruction. linear_sweep decodes a byte range in address order and lists every byte that it cannot decode.

The decoder is checked against a disassembler listing. For every instruction of the four committed objects, your address, your bytes and your AT&T text must equal the captured listing.

Why it matters

Every later stage trusts the decoder. A wrong operand width changes a 32-bit value into a 64-bit value, and the recompiled C then differs from the original. A wrong field offset makes stage 3 miss the relocation on the lea that holds the jump table base.

The listing gives you an oracle with no judgment in it. You do not decide that your decode looks right. You compare it.

The subset

Anything else raises DecodeError with the address and the opcode bytes.

Work through one concrete case

At address 0x3 of tenths_and_fifths at -O1, the bytes are 48 69 c0 67 66 66 66.

The result is imulq $0x66666667, %rax, %rax, length 7, width 64, immediate_offset 3. Remove the 48 and the same bytes decode as imull with a 32-bit operand size. The two forms compute different values, and stage 5 recognizes the division idiom only in the 64-bit product.

A memory operand at -O0: 48 63 04 81 at 0x6f is movslq (%rcx,%rax,4), %rax. ModRM 04 has mod=0 and rm=4, so a SIB byte follows. SIB 81 has scale 1 << 2 = 4, index 0 (rax) and base 1 (rcx).

A RIP-relative operand: 48 8d 0d 00 00 00 00 at 0x5c is leaq (%rip), %rcx. ModRM 0d has mod=0 and rm=5, which in 64-bit mode means RIP plus a 32-bit displacement. The displacement field starts at offset 3, so its absolute address is 0x5f. That is the r_offset of the relocation from stage 1.

A branch: 77 0c at 0x58 is ja with an 8-bit displacement of 12. The target is the end of the instruction plus 12: 0x5a + 0xc = 0x66.

Type other bytes into the lab, for example 48 63 04 81 or 66 0f 1f 44 00 00, and read the field table before you write the decoder branch for them.

Implement the contract

Implement these in the decoder module. The starter supplies the operand classes, the Instruction dataclass, the AT&T renderer, _Cursor, the _State helpers (operand_size, register, immediate, displacement, finish, relative), parse_objdump, compare_with_objdump and disassemble.

Operand order follows AT&T: source first, destination last. Instruction.flow is next, branch, jump, call, return, indirect-jump or indirect-call. Immediates are signed, except for mov and shift counts, which the listing prints unsigned.

Verify and inspect

python3 scripts/project_test.py mini-decompiler --stage 2 --path learning-artifacts/mini-decompiler --strict
cd learning-artifacts/mini-decompiler
python3 -m minidec disasm samples/samples-x86_64-O1.o --oracle samples/samples-x86_64-O1.objdump.txt

The starter copied the fixture objects and listings into samples. You can also pass your own object and a listing you captured with llvm-objdump -d -r. The command prints every instruction with the relocation target after it, and then reports oracle: 56/56 instructions agree with llvm-objdump. The -O0 object has 102 instructions. The held-out objects have 76 and 38.

Failure cases

• 90 0f 0a decoded at address 1 raises DecodeError whose reason names 0f 0a.
• 48 69 c0 67 66 stops inside the immediate and raises instead of reading past the end.
• Fifteen 66 prefixes and a 90 is 16 bytes, which is longer than the 15-byte architectural limit, and raises.
• 31 c0 0f 0a c3 swept linearly gives xorl %eax, %eax, two undecodable bytes at 2 and 3, and retq.

Extensions

• Add movsd and cvtsi2sd with the f2 prefix and XMM registers, and extend the oracle check to a fixture that uses double.
• Add VEX prefixes (c4, c5) and decode one AVX instruction from your own compiled loop.
• Make linear_sweep restart at the next function symbol after a decode error, and measure how many instructions it recovers.