0x864 - a minimal self-hosted x86-64 assembler written in assembly

Low-level coding has fascinated me for a long time. I did a bunch of assembly projects before, like Pong as a bootable floppy image or a simple bootloader for the FAT12 filesystem. For years now, I have been dreaming about writing an assembler in assembly language.

Aside from drafting out the code on paper and writing machine code directly with a hex editor, writing the assembler in assembly is about as low as software development can get. As a bonus, since the assembler is written in assembly itself, the ability to self-host the project comes naturally.

And let’s not lie, being able to assemble a hello world program with your own assembler feels like a strong achievement.

By the middle of the year, I finally got around to it. For the lulz and many insights about the x86 architecture, I created 0x864 - my x86-64 assembler.

This post will provide an overview of the project, offering insights into its development and the challenges encountered during the implementation, as well as the future of the project. For detailed usage instructions and current limitations, consult the technical documentation.

Brief overview of available features

The assembler is able to parse and assemble a limited, but versatile subset of the x86-64 instruction set. Only the Intel syntax is supported - that is a personal preference of mine. I do not like the % prefix of registers or the offset addressing of the AT&T syntax. Comments are supported by 0x864. If a semicolon (;) is encountered, all characters following it until the end of the line are treated as comment and discarded.

The set of supported instructions arose naturally while implementing the assembler - as the ability to assemble itself is the project’s primary goal, all instructions used in the assembler’s code itself were implemented. These include:

arithmetic instructions add, dec, div, inc, mul, neg, sub
bitwise instructions like and, or, xor
the shift instructions shl and shr
data transfer instructions lea, mov, movsb, movsd, movsq, movsw, pop, push, xchg
control flow instructions call, cmp, jmp, nop, retn and conditional jump instructions
int and syscall for interaction with the operating system.

0x864 being able to assemble itself, shows that it can handle and support the instruction set for an adequately complex program. Labels are supported similarly to how NASM handles them. For example a simple function that checks if a number is even might be implemented as

is_even:
        and rdi, 1      ; Mask the least significant bit
        cmp rdi, 0      ; Check if the LSB was not set
        je .ret_true
        xor eax, eax    ; Set eax to 0 to return false
        jmp .ret

.ret_true:
        mov eax, 1      ; Set eax to 1 to return true

.ret:
        retn

Here the labels .ret_true and .ret are local to the is_even function and internally stored and resolved as is_even.ret_true and is_even.ret.

Furthermore, labels can be declared as global at the beginning of the source file. Global labels have Elf64_Sym.st_info set to STB_GLOBAL and can be linked against.

The output format is controlled by a -f switch with the two options -fbin and -felf64 similar to how NASM handles output. The binary format just outputs the .text section and is only useful for inspecting the assembled program without the overhead of the ELF format while the ELF64 format directly generates a relocatable ELF file.

0x864 also supports register indirect memory addressing with an 8 or 16-bit displacement via the ModR/M byte. However, the SIB byte is not supported so

        mov eax, [rbp - 8]

is supported, while

        mov eax, [rsi + rcx * 4]

is not.

Aside from the instructions mentioned above - which are all part of the standard x86 instruction set - 0x864 lacks

floating-point instructions
SIMD instructions
AMD-V and Intel VT-x instructions as well as many more extensions to the x86 instruction set.

High-level structure

The most important file in the whole repository is the C-header file src/0x864.h. It describes the API of the assembler and defines constants as well as several structures holding the context of the program being assembled - like tables with symbol offsets and pointers to the buffer for the assembly text and assembled binary code.

The parsing and assembling is all written in x86-64 assembly language in the file src/0x864.s. Due to all functions written in assembly being exported and declared in the header file, they can be linked against in higher-languages and tested separately.

The directory tests contains a bunch of unit tests for the internal functions of the assembler. These unit tests are written in C for readability and make use of the acutest library. Furthermore the tests/demos subdirectory contains multiple example programs written in assembly, which are assembled by 0x864 and NASM each and then compared byte-for-byte.

The assembly code is independent of any external API like the libc or ABI like the syscall interface of the operating system. Instead it relies on the C code for interfacing with the OS. Buffers for binary output and symbol tables are allocated on the heap using libc. The allocation of these buffers is covered by the API of 0x864 and handled in src/0x864.c.

Finally, src/harness.c implements the actual entrypoint, command-line argument parsing, reading the input file, calling the high-level functions from the 0x864 API and writing the binary output file.

Provided high-level functions are

assemble: This function parses the assembly text from a provided string, assembles the binary code (.text segment) into a buffer and stores the offsets of all symbols inside the .text segment.
elf64_dump: This function writes the binary relocatable .ELF contents to a buffer taking the already assembled binary program and symbol table as input.

Defining self-hosting for 0x864

First things first, 0x864 cannot produce executables directly. Tnstead, it can assemble assembly language into relocatable ELF files. Furthermore, as mentioned earlier, some parts of the assembler are written in C and it still requires a C compiler to build those C parts and link everything together. So why is it still called a self-hosted assembler?

Quoting the Wikipedia page about self-hosting,

Self-hosting is the use of a program as part of the toolchain […] that produces new versions of that same program

and that is exactly what 0x864 does - it replaces NASM as an assembler in its own build chain.

Notable insights

Even if most functions implemented in assembly language inside 0x864 are only called by other assembly functions, following the calling conventions of the System V ABI adds significant value as
- first, calling functions is straightforward if their arguments are known, as the way the arguments are passed to the function follows from the calling conventions.
- second, these functions are compatible with other languages that use the same calling conventions. They can be easily called and validated in unit tests or be used by a harness around the assembly code.

Since the assembly code in 0x864 does not link against the libc directly and therefore lacks access to functions like strncmp, nor does 0x864 support storing data, such as strings, in the .data segment, checking for keywords like opcodes is a challenge. Since mnemonics for opcodes are generally short (less than 8 characters in length), a string containing them can be stored in a single register as an integer. Taking a look at the ASCII table

Letter	ASCII code (hex)
…	…
`a`	0x61
`b`	0x62
`c`	0x63
`d`	0x64
…	…

add becomes 0x646461, with the first letter being stored in the least significant byte. Then, a simple assembly function that mimics the behavior of the C-function

int testinst(const char *assembly_text, uint64_t encoded_instruction)
{
        for (char c; (c = encoded_instruction & 0xff) != 0;) {
                if (c != *(assembly_text++))
                        return 0;

                encoded_instruction >>= 8;
        }

        // Check for newline, space, null-terminator, ...
        return is_opcode_delimiter(assembly_text);
}

can be used to check if the current position in the assembly code is the start of the add instruction with

        mov rsi, 0x646461       ; add
        call .testinst
        cmp rax, 1
        jne .check_next_instruction
        lea rsi, [rbp - 32]     ; Load additional argument for as_add
        call as_add

That provides an easy way to check for (short) strings without implementing .data segment handling to store data that is not code.

Some instructions are really similar in the way they are encoded. For example, there are many instructions which can be described in 5 cases, where for each case the operand-size override prefix is used for the 16-bit operation and the REX prefix for the 64-bit operation and the opcodes follow the logic, that the opcodes for the 64/32/16-bit operation are just the opcode for the 8-bit operation plus one. These cases are
1. the destination is the rax, eax, ax, al register and the source an immediate with the same size as the register or in the case of the rax register a 32-bit immediate, that will be sign-extended for 64-bit.
2. the destination is a register or memory address described by the ModRM:r/m bits, an additional 3-bit integer defining the operation is stored in the ModRM:reg bits and the source is an immediate with the size of the register except for a 64-bit register, where the source is a 32-bit immediate sign-extended to 64-bit.
3. the same as case 2, but an 8-bit immediate is sign-extended to the operation size.
4. the destination is a register or memory address described by the ModRM:r/m bits and the source is another register.
5. the destination is a register and the source is a register or memory address described by the ModRM:r/m bits.
That’s a lot of logic but fortunately these cases describe a bunch of instructions like add, and, cmp, or, sub, xor.

0x864 has a generic implementation for them in the form of the as_genop2ax32 (Assemble generic operation with two operands, special ax handling and immediates up to 32 bits) function. That function has the declaration
```
enum AsmErr as_genop2ax32(struct AsmCtx *ctx, struct AsmOp *op,
                          uint8_t op_al_imm8, uint8_t op_rimm8,
                          uint8_t op_rsimm8, uint8_t op_rmr8,
                          uint8_t op_rrm8, uint8_t modrm_reg);
```
where ctx and op are internal structures of the assembler, the next five arguments are just the opcodes for the 8-bit operation of each case mentioned above and the final argument modrm_reg is the 3-bit integer encoded in the ModRM:reg bits in cases 2 and 3.

With this generic implementation, assembling an instruction like add becomes as simple as
```
;;; rdi: `struct AsmCtx *ctx`
;;; rsi: `struct AsmOp *op`
as_add:
        push rbp
        mov rbp, rsp
        sub rsp, 16

        mov edx, 0x04           ; uint8_t op_al_imm8 = 0x04
        mov ecx, 0x80           ; uint8_t op_rimm8 = 0x80
        mov r8d, 0x83           ; uint8_t op_rsimm8 = 0x83
        mov r9d, 0x00           ; uint8_t op_rmr8 = 0x00
        mov eax, 0x02
        mov [rbp - 16], rax     ; uint8_t op_rrm8 = 0x02
        xor eax, eax
        mov [rbp - 8], rax      ; uint8_t modrm_mod = 0
        call as_genop2ax32

        mov rsp, rbp
        pop rbp
        retn
```
Error handling is important and improves the developer experience. The project was started under the assumption that 0x864 would only ever encounter valid input files. That assumption quickly turned out to be wrong. Silly errors like a misspelled instruction still happen and investigating why the assembler silently exited is tedious.

Therefore the enum AsmErr was introduced, which defines constants for common errors like for example
- an unknown instruction
- invalid operand types for an instruction
- a reference to an unknown label
Finally, the harness was extended with a print_error function that prints a human-readable description for the constants of the AsmErr enumeration.

Possible next steps

Removing the dependency on the C compiler for the build chain would be a great path forward for the project. Since the C-code currently handles all the interfacing with the operating system and the libc, removing it would require the implementation of the extern keyword, so that the ELF file assembled by 0x864 can be linked against the libc directly. That would be some work implementing the generation of relocation tables in the ELF64 output, but generally doable.

In addition, I’d really like to explore the idea of generating EFI executables for writing code that is bootable on a modern x86 system directly in assembly.

Conclusion

Writing an assembler in assembly is surprisingly doable. Working on the first half of the project felt rather dull, as there was little visible progress. Then, about halfway through the project - when it could assemble the first minimal programs - hacking the project together became a joy. With a solid foundation, additional features could be added quite easily and were directly visible with the ability to assemble further demo programs. Also, the path forward changed from a labyrinth to a clear road as the demand for new instructions to implement directly emerged from the codebase of 0x864 itself.

It was a great little project for me and I really enjoyed the late nights I spent hacking it together and gaining new insights into the x86 architecture.