How to write a disassembler?

Question

I'm interested in writing an x86 dissembler as an educational project.

The only real resource I have found is Spiral Space's, "How to write a disassembler". While this gives a nice high level description of the various components of a disassembler, I'm interested in some more detailed resources. I've also taken a quick look at NASM's source code but this is somewhat of a heavyweight to learn from.

I realize one of the major challenges of this project is the rather large x86 instruction set I'm going to have to handle. I'm also interested in basic structure, basic disassembler links, etc.

Can anyone point me to any detailed resources on writing a x86 disassembler?

Answer 1

Start with some small program that has been assembled, and which gives you both the generated code and the instructions. Get yourself a reference with the instruction architecture, and work through some of the generated code with the architecture reference, by hand. You'll find that the instructions have a very stereotypical structure of inst op op op with varying number of operands. All you need to do is translate the hax or octal representation of the code to match the instructions; a little playing around will reveal it.

That process, automated, is the core of a disassembler. Ideally, you're probably going to want to construct a n array of instruction structures internally (or externally, if the program is really large). You can then translate that array into the instructions in assembler format.

Answer 2

You need a table of opcodes to load from.

The fundamental lookup datastructure is a trie, however a table will do well enough if you don't care much about speed.

To get the base opcode type, beginswith match on the table.

There are a few stock ways of decoding register arguments; however, there are enough special cases to require implementing most of them individually.

Since this is educational, have a look at ndisasm.

Answer 3

I would recommend checking out some open source disassemblers, preferably distorm and especially "disOps (Instructions Sets DataBase)" (ctrl+find it on the page).

The documentation itself is full of juicy information about opcodes and instructions.

Quote from http://ragestorm.net/distorm/vol1.html:

80x86 Instruction:

A 80x86 instruction is divided to a number of elements:

1. Instruction prefixes, affects the behaviour of the instruction's operation.
2. Mandatory prefix used as an opcode byte for SSE instructions.
3. Opcode bytes, could be one or more bytes (up to 3 whole bytes).
4. ModR/M byte is optional and sometimes could contain a part of the opcode itself.
5. SIB byte is optional and represents complex memory indirection forms.
6. Displacement is optional and it is a value of a varying size of bytes(byte, word, long) and used as an offset.
7. Immediate is optional and it is used as a general number value built from a varying size of bytes(byte, word, long).

The format looks as follows:

/-------------------------------------------------------------------------------------------------------------------------------------------\
|*Prefixes | *Mandatory Prefix | *REX Prefix | Opcode Bytes | *ModR/M | *SIB | *Displacement (1,2 or 4 bytes) | *Immediate (1,2 or 4 bytes) |
\-------------------------------------------------------------------------------------------------------------------------------------------/
* means the element is optional.

The data structures and decoding phases are explained in http://ragestorm.net/distorm/vol2.html

Quote:

Decoding Phases

1. [Prefixes]
2. [Fetch Opcode]
3. [Filter Opcode]
4. [Extract Operand(s)]
5. [Text Formatting]
6. [Hex Dump]
7. [Decoded Instruction]

Each step is explained also.

Answer 4

Take a look at section 17.2 of the 80386 Programmer's Reference Manual. A disassembler is really just a glorified finite-state machine. The steps in disassembly are:

1. Check if the current byte is an instruction prefix byte (F3, F2, or F0); if so, then you've got a REP/REPE/REPNE/LOCK prefix. Advance to the next byte.
2. Check to see if the current byte is an address size byte (67). If so, decode addresses in the rest of the instruction in 16-bit mode if currently in 32-bit mode, or decode addresses in 32-bit mode if currently in 16-bit mode
3. Check to see if the current byte is an operand size byte (66). If so, decode immediate operands in 16-bit mode if currently in 32-bit mode, or decode immediate operands in 32-bit mode if currently in 16-bit mode
4. Check to see if the current byte is a segment override byte (2E, 36, 3E, 26, 64, or 65). If so, use the corresponding segment register for decoding addresses instead of the default segment register.
5. The next byte is the opcode. If the opcode is 0F, then it is an extended opcode, and read the next byte as the extended opcode.
6. Depending on the particular opcode, read in and decode a Mod R/M byte, a Scale Index Base (SIB) byte, a displacement (0, 1, 2, or 4 bytes), and/or an immediate value (0, 1, 2, or 4 bytes). The sizes of these fields depend on the opcode , address size override, and operand size overrides previously decoded.

The opcode tells you the operation being performed. The arguments of the opcode can be decoded form the values of the Mod R/M, SIB, displacement, and immediate value. There are a lot of possibilities and a lot of special cases, due to the complex nature of x86. See the links above for a more thorough explanation.