Pages

January 11, 2013

So I Wrote A Disassembler

It was the middle of the Texas summer and I had just returned from India back to USA and had absolutely no work to do since I had not registered for any courses in the summer. Back in India, my mentor suggested that I try my hand at writing a disassembler as a first step to get into the realm of low-level system code, OS internals and system software. So that's exactly what I did. I wrote a disassembler for 32bit windows PE files with support for integer, floating-point, MMX, SSE1 and AES instructions :D

Let me tell you, it was not an easy start. I had no clue where to even start. So I started reading up on the format of PE files. Found a very good resource online for this: Matt Pietrek's Explanation of the PE file format MSDN_Mag-Feb2002. I got stuck at one point trying to learn how to find where the code section actually begins in the binary. This article helped a lot in solving my doubts. That link also has some amazing work on x86 assembly and reverse engineering. One must also know about memory mapped files. It comes in very handy when reading files in which you must read data randomly instead of in a sequential way. Memory mapping is achieved with the help of the OS. What it does is it maps the file from the hard disk to virtual memory pages to the process that maps the file. Now the user process can access the file contents just the way it accesses memory locations via a pointer.

I then started reading the Intel SW Developers Manuals which gives a huge amount of information on the processor architecture and more importantly the Instruction Set Architecture (ISA). Volume2 describes the instruction format that is used by the Intel processors and detailed encoding of each and every assembly instruction. Since instructions in the x86 ISA has variable encoding lengths it takes some effort to achieve a successful disassembly. When going through the ISA, one might think that the instructions have random opcodes without any particular format to it but that is far from the truth. Take a look at this document which graphically depicts the opcodes of all instructions. Even though the instructions are encoded into different sizes, it is easy to disassemble using the general instruction format given below.

 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 | [Prefix] |  Opcode  | [ModR/M] |  [SIB]  |   [Disp]   |   [Imm]    |
 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
     <= 4   | 1/2byte  |  1byte   | 0/1byte | 1/2/4bytes | 1/2/4bytes |
    1 byte  |
     each   |

Using the above format, we can start processing at the very first byte of the code section by checking whether it is a prefix/opcode and moving on from there. The state machine below gives a more accurate picture about the disassembly process. Links to source code & binaries of my disassembler is posted in the Code Section. Look at the code and you will get a better understanding of the whole thing.

The ERROR state may be entered from any other state because of disassembly errors like starting disassembly from the middle of an instruction or may be an instruction that is not supported yet. If you look at the source code, there are about 9k LOC (with comments) for just the disassembly engine. This may sound too much but it is only because of different instructions. The logic is the same in processing all instructions(opcode handlers). Only thing is to determine which state to go to next by looking at the current information. There are a lot of if-else conditions to be checked because what the next byte means depends on what has been processed until now. The main part of disassembly, the opcode processing, is easily done using jump tables - I have used an array of function pointers that store addresses of the opcode handler functions and I can call the appropriate function by a simple table lookup when the opcode byte is read.

It was a completely involving experience to work on this project, about one and a half months of summer time gone by in a flash of frantic coding! The very first time that I tested the code and saw a small snippet of the disassembler output on the geeky green color console window, I was elated, and eager to do more and complete the project. There is no better way than coding to kill time!

November 18, 2012

Switch's jump table


We all have heard that using a switch() block instead of a long if-else ladder results in faster code. Let us see why it is so. The secret to switch()'s faster code is the use of jump tables. A jump table basically consists of rows of addresses that point to locations in the code section. This table is indexed using the value of the variable specified in switch()'s condition. Every address points to one of the 'case' blocks or the 'default' block. This table is accessed by the CPU's 'Scaled-Index+Displacement' addressing mode. Now let us see what this table looks like:

--[ Basic jump table layout
- Each value in the 'Address' column points to the beginning of a 'case' block.
- Each row is 4 bytes long: standard size of a pointer.

+-------+------------+
| Index | Address    |
+-------+------------+
| 0     | codeloc0   | - 4 bytes
|--------------------|
| 1     | codeloc1   | - 4 bytes
|--------------------|
| 2     | codeloc2   | - 4 bytes
|--------------------|
| 3     | codeloc3   | - 4 bytes
|--------------------|
|...
|...

Let us review what a typical switch() block is made of. Every switch statement requires a value to use as index into the jump table. This value can be either stored in a variable or be generated as the result of an expression. Whatever the case, switch uses this as a number to index into the jump table. This is followed by zero or more case blocks with optional break statements. There may optionally be a default block also. If the break statement is omitted at the end of any case block then control falls-through to the next case block until a break or some other control transfer statement is encountered.

--[ switch() block layout

switch(value)
{
case 0: [break;]
case 1: [break;]
case 2: [break;]
...
[default: ...]
}

--] switch() block layout

In order to understand what exactly is being done with the 'value' and how the jump table is used we must look at the assembly code generated by the compiler. The basic steps done is outlined in the following pseudo-code.

begin switch()
    if value > highest_case_value then
    if default was defined then
        jump to default block
    else
        jump out of switch block

    index := value * scale_factor + addr of jump_table
    jump to code location stored at jump_table[index]
    // case blocks follow sequentially
    // followed by optional default block
end switch()

Let us get into a bit of assembly now. All doubts should be cleared after this.

--[ Disassembly snippets

; ** switch() begins
; switch(iIn)
0041155E mov eax,dword ptr [iIn]
00411561 mov dword ptr [ebp-0DCh],eax
00411567 cmp dword ptr [ebp-0DCh],7
0041156E ja $LN2+4 (4115B2h)
00411570 mov ecx,dword ptr [ebp-0DCh]
00411576 jmp dword ptr (411610h)[ecx*4]

iIn is the variable whose value is used to index into the jump table. The value is moved into eax first. It is then copied to a scratch-pad area and compared with the number 7, which is the highest value used in any of the case statements. If value of iIn is above 7 then control is transferred to the default block via the ja(jump if above) instruction. Notice that compiler has generated an unsigned compare instruction ja(jump if above) instead of jg(jump if greater) even though iIn is an signed variable. This is because the jump table index must always be >=0. If iIn was less than 7 then it is again moved to ecx from the scratch-pad area and the next jump instruction directly jumps to the appropriate case block(!). How did that happen you say? Well, scaled-Index+Displacement addressing mode and indirect jump happened! The ecx register is the index, 4 is the scaling factor because each row of the jump table is 4bytes long and 00411610h is the starting address of the jump table. The jump instruction uses the value at the calculated jump table index as an absolute offset. For example, if iIn was 3 then index = 00411610h + 3*4 = 00411610h + 0Ch = 0041161Ch. Value at 0041161Ch = 00411592. This is nothing but the address of the beginning of 'case 3' block. So the jump instruction transfers control to this block!

; case 0: vUnderConst(); break;
0041157D call vUnderConst (41107Dh)
00411582 jmp $LN2+1Bh (4115C9h)

; case 1: vUnderConst(); break;
00411584 call vUnderConst (41107Dh)
00411589 jmp $LN2+1Bh (4115C9h)

; case 2: vUnderConst(); break;
0041158B call vUnderConst (41107Dh)
00411590 jmp $LN2+1Bh (4115C9h)

; case 3: vUnderConst(); break;
00411592 call vUnderConst (41107Dh)
00411597 jmp $LN2+1Bh (4115C9h)

; case 4: vUnderConst(); break;
00411599 call vUnderConst (41107Dh)
0041159E jmp $LN2+1Bh (4115C9h)

; case 5: vUnderConst(); break;
004115A0 call vUnderConst (41107Dh)
004115A5 jmp $LN2+1Bh (4115C9h)

; case 6: vUnderConst(); break;
004115A7 call vUnderConst (41107Dh)
004115AC jmp $LN2+1Bh (4115C9h)

; case 7: return 0;
004115AE call vUnderConst (41107Dh)
004115B0 jmp $LN2+1Bh (4115C9h)

; default: printf("No such service\n"); break;
004115B2 mov esi,esp
004115B4 push offset string "No such service\n" (41575Ch)
004115B9 call dword ptr [__imp__printf (4182DCh)]

; ** switch() ends

--] Disassembly snippets

--[ Annotated jump table
- Index: Logical index of each row.
- CodeAddr: Location where the row value is stored.
- CodeLoc: Absolute code offsets that point to each of the case blocks.
+-------+------------+-----------+
| Index | CodeAddr   | CodeLoc   |
+-------+------------+-----------+
| 0     | 00411610   | 0041157d  |
|--------------------------------|
| 1     | 00411614   | 00411584  |
|--------------------------------|
| 2     | 00411618   | 0041158b  |
|--------------------------------|
| 3     | 0041161C   | 00411592  |
|--------------------------------|
| 4     | 00411620   | 00411599  |
|--------------------------------|
| 5     | 00411624   | 004115a0  |
|--------------------------------|
| 6     | 00411628   | 004115a7  |
|--------------------------------|
| 7     | 0041162C   | 004115ae  |
|--------------------------------|

--] Annotated jump table

I hope you understood how the switch statement uses a jump table to optimize code when choices are to be made based on multiple condition values. Before we conclude there are some things related to the jump table that is to be mentioned. The above explanation assumed that the case values started from 0 and continued with consecutive numbers until 7. What happens if the case values do not begin from 0? What happens when the case values are not consecutive? At first, it looks like a lot of if-else conditions might have to be generated by the compiler. No, again the jump table comes to our rescue.
The jump table always has entries from index 0 to highest_case_value. It is always zero-based. So for every case value that is not specified in the source code, the jump table entry for that value will point to the switch's 'default' block, if present, or to the statement after the switch block. For example, consider the following source code and the jump table generated.

switch(val)
{
   case 1: break;
   case 6: break;
   case 7: break;
   case 9: break;
   default: printf(“Invalid\n”); break;
}
after_switch: statement x

+-------+------------+-----------+
| Index | CodeAddr   | CodeLoc   |
+-------+------------+-----------+
|   0   | codeaddr0  | default   |
|--------------------------------|
|   1   | 00411614   | 00411584  |
|--------------------------------|
|   2   | 00411618   | 0041158b  |
|--------------------------------|
|   3   | 0041161C   | 00411592  |
|--------------------------------|
|   4   | 00411620   | 00411599  |
|--------------------------------|
|   5   | 00411624   | 004115a0  |
|--------------------------------|
|   6   | 00411628   | 004115a7  |
|--------------------------------|
|   7   | 0041162C   | 004115ae  |
|--------------------------------|