Article Community improvements enabled

Build a Tiny x86-64 Assembler: Resolve Forward Jumps with Fixups

Daniel McCarthy published 2 weeks ago 6 min read 168 views
New post
Daniel McCarthy remains the original author. Improvements are attributed to their editors and reviewed by the original author before publication.

A forward jump refers to code you have not emitted yet. At the moment you write the jump instruction, you know the target's name, but its byte position may still be unknown.

An assembler can handle this by reserving the displacement field and recording a fixup: a promise to fill in those bytes after the target label has a position.

We will build a small Python emitter for three x86-64 instructions: NOP, RET, and an unconditional JMP using a signed 32-bit relative displacement. The example produces and inspects raw bytes. Its Python methods form the input interface; there is no assembly-text parser or executable-file writer.

Fix the encoding before calculating positions

Our emitter always uses these unprefixed encodings:

Instruction Encoding Length
NOP 90 1 byte
Near RET C3 1 byte
Near JMP rel32 E9 followed by a signed 32-bit displacement 5 bytes

Intel's instruction-set reference, Volume 2A documents E9 rel32 as valid in 64-bit mode. The processor sign-extends that displacement and adds it to the instruction pointer of the following instruction. The NOP and RET entries are in Volume 2B.

For a jump beginning at byte offset start, this gives:

next_ip      = start + 5
displacement = target_offset - next_ip

The signed 32-bit field can represent displacements from -2**31 through 2**31 - 1, inclusive. The four displacement bytes are written in little-endian order.

We deliberately keep every jump five bytes long. That makes the layout stable while we patch it: replacing four placeholder bytes with four final bytes changes no label offsets.

A fixup needs a patch location and a target

A label records the current byte offset and emits no bytes. A jump emits E9, reserves four zero bytes, and records the offset of the first reserved byte together with the target's name.

When finalizing the buffer, we look up every target, compute its displacement, validate the range, and replace the corresponding placeholder. The stored field offset is start + 1, so the following instruction is at field + 4.

Using buffer offsets works because both the jump and its target belong to the same image. If that image starts at address base, the common base cancels:

(base + target_offset) - (base + next_ip)
    = target_offset - next_ip

The complete emitter

Save this as tiny_fixups.py and run python tiny_fixups.py. It uses the Python 3.10 standard library. Label names are supplied directly as strings, and they must be unique across this image.

from dataclasses import dataclass


class AssemblyError(ValueError):
    pass


def rel32(target, next_ip):
    displacement = target - next_ip
    if not -(1 << 31) <= displacement < (1 << 31):
        raise AssemblyError("jump target is outside the signed rel32 range")
    return displacement.to_bytes(4, "little", signed=True)


@dataclass(frozen=True)
class Fixup:
    field: int  # Offset of the first displacement byte.
    label: str


class TinyAssembler:
    def __init__(self):
        self._code = bytearray()
        self._labels = {}
        self._fixups = []

    @property
    def offset(self):
        return len(self._code)

    def label(self, name):
        if name in self._labels:
            raise AssemblyError(f"duplicate label: {name}")
        self._labels[name] = self.offset

    def nop(self):
        self._code.append(0x90)

    def ret(self):
        self._code.append(0xC3)

    def jmp(self, label):
        self._code.append(0xE9)
        field = self.offset
        self._code.extend(b"\x00\x00\x00\x00")
        self._fixups.append(Fixup(field, label))

    def finish(self):
        result = bytearray(self._code)
        for fixup in self._fixups:
            if fixup.label not in self._labels:
                raise AssemblyError(f"undefined label: {fixup.label}")
            target = self._labels[fixup.label]
            next_ip = fixup.field + 4
            result[fixup.field:next_ip] = rel32(target, next_ip)
        return bytes(result)


def example():
    asm = TinyAssembler()
    asm.label("entry")
    asm.jmp("done")
    asm.nop()
    asm.label("again")
    asm.nop()
    asm.jmp("again")
    asm.label("done")
    asm.ret()
    return asm.finish()


if __name__ == "__main__":
    print(example().hex(" "))

It prints:

e9 07 00 00 00 90 90 e9 fa ff ff ff c3

Trace the two jumps

The example contains a forward reference to done and a backward reference to again:

Start offset Instruction Following offset Target offset Displacement
0x00 jmp done 0x05 0x0c +7
0x05 nop 0x06 — —
0x06 again: nop 0x07 — —
0x07 jmp again 0x0c 0x06 -6
0x0c done: ret 0x0d — —

For the first jump, 12 - 5 is 7, which becomes 07 00 00 00. For the second, 6 - 12 is -6, encoded as fa ff ff ff.

Subtracting the jump's start instead of its end would make both destinations wrong by five bytes. Subtracting the displacement field's start would make them wrong by four. Naming the stored position field and calculating field + 4 keeps that distinction visible.

Keep errors explicit

An undefined label means the emitter cannot finish a branch. A duplicate label would make the intended destination ambiguous. Both raise AssemblyError.

The range check prevents an out-of-range displacement from being silently truncated. You can test both signed boundaries without allocating a multi-gigabyte code buffer:

assert rel32((1 << 31) - 1, 0) == bytes.fromhex("ff ff ff 7f")
assert rel32(-(1 << 31), 0) == bytes.fromhex("00 00 00 80")

try:
    rel32(1 << 31, 0)
except AssemblyError:
    pass
else:
    raise AssertionError("an out-of-range jump was accepted")

finish() patches a copy of the buffer. A failure therefore leaves the emitter's original placeholders intact, and repeated successful calls produce the same bytes while the emitted layout is unchanged. Adding more instructions or labels later can, of course, change a subsequent result.

Compare against an independent assembler

The equivalent NASM source is:

BITS 64
entry:
    jmp near done
    nop
again:
    nop
    jmp near again
done:
    ret

Save it as reference.asm and assemble a flat binary:

nasm -f bin reference.asm -o reference.bin

The explicit near operands keep the comparison on the five-byte form used by our emitter. Assemblers can otherwise choose a shorter branch encoding when the target is close enough. NASM describes its assembly syntax in the official language manual.

With GNU objdump installed, inspect the binary using:

objdump -D -b binary -m i386:x86-64 reference.bin

The important addresses in the disassembly are a jump at offset 0 to 0xc, and a jump at offset 7 to 0x6. Before publication, the emitter passed 12 scenario tests, and 64 generated layouts containing forward and backward jumps matched NASM byte for byte. The example was also checked with objdump. These checks verify the emitted encoding; this walkthrough does not execute the generated buffer.

What changes when an assembler grows

Adding a short-jump optimization changes the problem. Replacing a five-byte jump with a two-byte one moves later instructions and can alter other branch distances. An assembler then needs a layout strategy that accounts for those size changes; our fixed-size design avoids that extra dependency.

This example also resolves only labels within one contiguous image. A target supplied by another object file needs a mechanism for carrying unresolved address information to a later stage, such as the relocation records used by an object format. The in-memory Fixup objects here are the emitter's own bookkeeping; they are not ELF relocation entries.

Labels can be recorded at the end of the current buffer, so a complete code generator must also ensure every executed branch reaches valid code and has an appropriate execution context. Producing an executable or a callable JIT function adds memory management, platform, and calling-convention requirements beyond this encoding exercise.

For more practice with x86-64 execution flow, jumps, and calls, see my Mastering 64-bit Assembly Language Programming with NASM and C Integration course. For a broader compiler project involving fixups and label handling, my Creating a C Compiler From Scratch Video Course! provides related lessons in the context of building a compiler.

Discussion 0

No comments yet. Start a thoughtful discussion.

Join the discussion

You need an account to contribute.

Sign in