# X86 Disassembly/Branches

## Branching

Computer science professors tell their students to avoid jumps and
**goto** instructions, to avoid the proverbial \"spaghetti code.\"
Unfortunately, assembly only has jump instructions to control program
flow. This chapter will explore the subject that many people avoid like
the plague, and will attempt to show how the spaghetti of assembly can
be translated into the more familiar control structures of high-level
language. Specifically, this chapter will focus on **If-Then-Else** and
**Switch** branching instructions.

## If-Then

Let\'s consider a generic **if** statement in pseudo-code followed by
its equivalent form using jumps:

+----------------------------------+----------------------------------+
| `if (condition) then`\           | ![](_C_langu                     |
| ` do_action;`                    | age_if.png "_C_language_if.png") |
|                                  |                                  |
| `if                              |                                  |
| not (condition) then goto end;`\ |                                  |
| `  do_action;`\                  |                                  |
| `end:`                           |                                  |
+----------------------------------+----------------------------------+

What does this code do? In English, the code checks the condition and
performs a jump only if it is *false*. With that in mind, let\'s compare
some actual C code and its Assembly translation:

+-------------+--------------+
| ``` C       | ``` asm      |
|  if(x == 0) |  mov eax, $x |
|  {          |  cmp eax, 0  |
|    x = 1;   |  jne end     |
|  }          |  mov eax, 1  |
|  x++;       |  end:        |
| ```         |  inc eax     |
|             |  mov $x, eax |
|             | ```          |
+-------------+--------------+

Note that when we translate to assembly, we need to *negate* the
condition of the jump because\--like we said above\--we only jump if the
condition is false. To recreate the high-level code, simply negate the
condition once again.

Negating a comparison may be tricky if you\'re not paying attention.
Here are the correct dual forms:

  Instruction   Meaning
  ------------- ----------------------------------------
  JNE           **J**ump if **n**ot **e**qual
  JE            **J**ump if **e**qual
  JG            **J**ump if **g**reater
  JLE           **J**ump if **l**ess than or **e**qual
  JL            **J**ump if **l**ess than
  JGE           **J**ump if **g**reater or **e**qual

And here are some examples.

``` asm
 mov eax, $x                     //move x into eax
 cmp eax, $y                     //compare eax with y
 jg end                          //jump if greater than
 inc eax
 mov $x, eax                    //increment x
 end:
 ...
```

Is produced by these C statements:

``` C
 if(x <= y)
 {
    x++;
 }
```

As you can see, x is incremented only if it is **less than or equal to**
y. Thus, if it is greater than y, it will not be incremented as in the
assembler code. Similarly, the C code

``` C
 if(x < y)
 {
    x++;
 }
```

produces this assembler code:

``` asm
 mov eax, $x                        //move x into eax
 cmp eax, $y                        //compare eax with y
 jge end                            //jump if greater than or equal to
 inc eax
 move $x, eax                       //increment x
 end:
 ...
```

X is incremented in the C code only if it is **less than** y, so the
assembler code now jumps if it\'s greater than or equal to y. This kind
of thing takes practice, so we will try to include lots of examples in
this section.

## If-Then-Else

Let us now look at a more complicated case: the **If-Then-Else**
instruction.

+----------------------------------+----------------------------------+
| `if (condition) then`\           | ![](C_language_if_el             |
| `  do_action`\                   | se.png "C_language_if_else.png") |
| `else`\                          |                                  |
| `  do_alternative_action;`       |                                  |
|                                  |                                  |
| `if not (condition) goto else;`\ |                                  |
| `  do_action;`\                  |                                  |
| `  goto end;`\                   |                                  |
| `else:`\                         |                                  |
| `  do_alternative_action;`\      |                                  |
| `end:`                           |                                  |
+----------------------------------+----------------------------------+

Now, what happens here? Like before, the if statement only jumps to the
else clause when the condition is false. However, we must also install
an *unconditional* jump at the end of the \"then\" clause, so we don\'t
perform the else clause directly afterwards.

Now, here is an example of a real C If-Then-Else:

``` C
 if(x == 10)
 {
    x = 0;
 }
 else
 {
    x++;
 }
```

Which gets translated into the following assembly code:

``` asm
 mov eax, $x
 cmp eax, 0x0A ;0x0A = 10
 jne else
 mov eax, 0
 jmp end
 else:
 inc eax
 end:
 mov $x, eax
```

As you can see, the addition of a single unconditional jump can add an
entire extra option to our conditional.

## Switch-Case

**Switch-Case** structures can be very complicated when viewed in
assembly language, so we will examine a few examples. First, keep in
mind that in C, there are several keywords that are commonly used in a
switch statement. Here is a recap:

Switch : This keyword tests the argument, and starts the switch structure\
Case : This creates a label that execution will switch to, depending on the value of the argument.\
Break : This statement jumps to the end of the switch block\
Default : This is the label that execution jumps to if and only if it doesn\'t match up to any other conditions

Lets say we have a general switch statement, but with an extra label at
the end, as such:

``` C
 switch (x)
 {
 //body of switch statement
 }
 end_of_switch:
```

Now, every **break** statement will be immediately replaced with the
statement

``` asm
 jmp end_of_switch
```

But what do the rest of the statements get changed to? The case
statements can each resolve to any number of arbitrary integer values.
How do we test for that? The answer is that we use a \"Switch Table\".
Here is a simple, C example:

``` C
 int main(int argc, char **argv)
 { //line 10
    switch(argc)
    {
        case 1:
            MyFunction(1);
            break;
        case 2:
            MyFunction(2);
            break;
        case 3:
            MyFunction(3);
            break;
        case 4:
            MyFunction(4);
            break;
        default:
            MyFunction(5);
    }
    return 0;
 }
```

And when we compile this with **cl.exe**, we can generate the following
listing file:

``` asm
 tv64 = -4      ; size = 4
 _argc$ = 8     ; size = 4
 _argv$ = 12        ; size = 4
 _main  PROC NEAR
 ; Line 10
    push    ebp
    mov ebp, esp
    push    ecx
 ; Line 11
    mov eax, DWORD PTR _argc$[ebp]
    mov DWORD PTR tv64[ebp], eax
    mov ecx, DWORD PTR tv64[ebp]
    sub ecx, 1
    mov DWORD PTR tv64[ebp], ecx
    cmp DWORD PTR tv64[ebp], 3
    ja  SHORT $L810
    mov edx, DWORD PTR tv64[ebp]
    jmp DWORD PTR $L818[edx*4]
 $L806:
 ; Line 14
    push    1
    call    _MyFunction
    add esp, 4
 ; Line 15
    jmp SHORT $L803
 $L807:
 ; Line 17
    push    2
    call    _MyFunction
    add esp, 4
 ; Line 18
        jmp     SHORT $L803
 $L808:
 ; Line 19
    push    3
    call    _MyFunction
    add esp, 4
 ; Line 20
    jmp SHORT $L803
 $L809:
 ; Line 22
    push    4
    call    _MyFunction
    add esp, 4
 ; Line 23
    jmp SHORT $L803
 $L810:
 ; Line 25
    push    5
    call    _MyFunction
    add esp, 4
 $L803:
 ; Line 27
    xor eax, eax
 ; Line 28
    mov esp, ebp
    pop ebp
    ret 0
 $L818:
    DD  $L806
    DD  $L807
    DD  $L808
    DD  $L809
 _main  ENDP
```

Lets work our way through this. First, we see that line 10 sets up our
standard stack frame, and it also saves ecx. Why does it save ecx?
Scanning through the function, we never see a corresponding \"pop ecx\"
instruction, so it seems that the value is never restored at all. In
fact, the compiler isn\'t saving ecx at all, but is instead simply
reserving space on the stack: it\'s creating a local variable. The
original C code didn\'t have any local variables, however, so perhaps
the compiler just needed some extra scratch space to store intermediate
values. Why doesn\'t the compiler execute the more familiar \"sub esp,
4\" command to create the local variable? **push ecx** is just a faster
instruction that does the same thing. This \"scratch space\" is being
referenced by a *negative offset* from ebp. **tv64** was defined in the
beginning of the listing as having the value -4, so every call to
\"tv64\[ebp\]\" is a call to this scratch space.

There are a few things that we need to notice about the function in
general:

-   Label \$L803 is the end_of_switch label. Therefore, every \"jmp
    SHORT \$L803\" statement is a **break**. This is verifiable by
    comparing with the C code line-by-line.
-   Label \$L818 contains a list of hard-coded memory addresses, which
    here are labels in the code section! Remember, labels resolve to the
    memory address of the instruction. This must be an important part of
    our puzzle.

To solve this puzzle, we will take an in-depth look at line 11:

``` asm
 mov    eax, DWORD PTR _argc$[ebp]
 mov    DWORD PTR tv64[ebp], eax
 mov    ecx, DWORD PTR tv64[ebp]
 sub    ecx, 1
 mov    DWORD PTR tv64[ebp], ecx
 cmp    DWORD PTR tv64[ebp], 3
 ja SHORT $L810
 mov    edx, DWORD PTR tv64[ebp]
 jmp    DWORD PTR $L818[edx*4]
```

This sequence performs the following pseudo-C operation:

`if( argc - 1 >= 4 )`\
`{`\
`   goto $L810;   /* the default */`\
`}`\
`label *L818[] = { $L806, $L807, $L808, $L809 };  /* define a table of jumps, one per each case */`\
`//`\
`goto L818[argc - 1];   /* use the address from the table to jump to the correct case */`

Here\'s why\...

### The Setup

``` asm
 mov    eax, DWORD PTR _argc$[ebp]
 mov    DWORD PTR tv64[ebp], eax
 mov    ecx, DWORD PTR tv64[ebp]
 sub    ecx, 1
 mov    DWORD PTR tv64[ebp], ecx
```

The value of argc is moved into eax. The value of eax is then
immediately moved to the scratch space. The value of the scratch space
is then moved into ecx. Sounds like an awfully convoluted way to get the
same value into so many different locations, but remember: I turned off
the optimizations. The value of ecx is then decremented by 1. Why
didn\'t the compiler use a **dec** instruction instead? Perhaps the
statement is a general statement, that in this case just happens to have
an argument of 1. We don\'t know why exactly, all we know is this:

-   **eax = \"scratch pad\"**
-   **ecx = eax - 1**

Finally, the last line moves the new, decremented value of ecx *back
into the scratch pad*. Very inefficient.

### The Compare and Jumps

``` asm
 cmp    DWORD PTR tv64[ebp], 3
 ja SHORT $L810
```

The value of the scratch pad is compared with the value 3, and if the
*unsigned* value is above 3 (4 or more), execution jumps to label
\$L810. How do I know the value is unsigned? I know because **ja** is an
unsigned conditional jump. Let\'s look back at the original C code
switch:

``` C
        switch(argc)
    {
        case 1:
            MyFunction(1);
            break;
        case 2:
            MyFunction(2);
            break;
        case 3:
            MyFunction(3);
            break;
        case 4:
            MyFunction(4);
            break;
        default:
            MyFunction(5);
    }
```

Remember, the scratch pad contains the value (argc - 1), which means
that this condition is only triggered when argc \> 4. What happens when
argc is greater than 4? The function goes to the default condition. Now,
let\'s look at the next two lines:

``` asm
 mov    edx, DWORD PTR tv64[ebp]
 jmp    DWORD PTR $L818[edx*4]
```

**edx** gets the value of the scratch pad (argc - 1), and then there is
a very weird jump that takes place: execution jumps to a location
pointed to by the value (edx \* 4 + \$L818). What is \$L818? We will
examine that right now.

### The Switch Table

``` asm
 $L818:
    DD  $L806
    DD  $L807
    DD  $L808
    DD  $L809
```

\$L818 is a pointer, in the code section, to a list of other code
section pointers. These pointers are all 32bit values (DD is a DWORD).
Let\'s look back at our jump statement:

``` asm
 jmp    DWORD PTR $L818[edx*4]
```

In this jump, \$L818 *isn\'t the offset, it\'s the base*, edx\*4 is the
offset. As we said earlier, edx contains the value of (argc - 1). If
argc == 1, we jump to \[\$L818 + 0\] which is \$L806. If argc == 2, we
jump to \[\$L818 + 4\], which is \$L807. Get the picture? A quick look
at labels \$L806, \$L807, \$L808, and \$L809 shows us exactly what we
expect to see: the bodies of the **case** statements from the original C
code, above. Each one of the case statements calls the function
\"MyFunction\", then breaks, and then jumps to the end of the switch
block.

## Ternary Operator ?:

Again, the best way to learn is by doing. Therefore we will go through a
mini example to explain the ternary operator. Consider the following C
code program:

``` C
 int main(int argc, char **argv)
 {
    return (argc > 1)?(5):(0);
 }
```

**cl.exe** produces the following assembly listing file:

``` asm
 _argc$ = 8                     ; size = 4
 _argv$ = 12                        ; size = 4
 _main  PROC NEAR
 ; File c:\documents and settings\andrew\desktop\test2.c
 ; Line 2
    push    ebp
    mov ebp, esp
 ; Line 3
    xor eax, eax
 
        cmp DWORD PTR _argc$[ebp], 1
        setle   al
        dec eax
        and eax, 5
 ; Line 4
    pop ebp
    ret 0
 _main  ENDP
```

Line 2 sets up a stack frame, and line 4 is a standard exit sequence.
There are no local variables. It is clear that Line 3 is where we want
to look.

The instruction \"xor eax, eax\" simply sets eax to 0. For more
information on that line, see the chapter on unintuitive
instructions. The **cmp** instruction
tests the condition of the ternary operator. The **setle** function is
one of a set of x86 functions that works like a conditional move: al
gets the value 1 if argc \<= 1. Isn\'t that the exact opposite of what
we wanted? In this case, it is. Let\'s look at what happens when argc =
0: **al** gets the value 1. **al** is decremented (al = 0), and then eax
is logically anded with 5. 5 & 0 = 0. When argc == 2 (greater than 1),
the **setle** instruction doesn\'t do anything, and eax still is zero.
eax is then decremented, which means that eax == -1. What is -1?

In x86 processors, negative numbers are stored in **two\'s-complement**
format. For instance, let\'s look at the following C code:

``` C
 BYTE x;
 x = -1;
```

At the end of this C code, **x** will have the value 11111111: all ones!

When argc is greater than 1, setle sets al to zero. Decrementing this
value sets every bit in eax to a logical 1. Now, when we perform the
logical **and** function we get:

` ...11111111`\
`&...00000101     ;101 is 5 in binary`\
`------------`\
` ...00000101`

eax gets the value 5. In this case, it\'s a roundabout method of doing
it, but as a reverser, this is the stuff you need to worry about.

For reference, here is the GCC assembly output of the same ternary
operator from above:

``` asm
 _main:
 pushl  %ebp
 movl   %esp, %ebp
 subl   $8, %esp
 xorl   %eax, %eax
 andl   $-16, %esp
 call   __alloca
 call   ___main
 xorl   %edx, %edx
 cmpl   $2, 8(%ebp)
 setge  %dl
 leal   (%edx,%edx,4), %eax
 leave
 ret
```

Notice that GCC produces slightly different code than cl.exe produces.
However, the stack frame is set up the same way. Notice also that GCC
doesn\'t give us line numbers, or other hints in the code. The ternary
operator line occurs after the instruction \"call \_\_main\". Let\'s
highlight that section here:

``` asm
 xorl   %edx, %edx
 cmpl   $2, 8(%ebp)
 setge  %dl
 leal   (%edx,%edx,4), %eax
```

Again, **xor** is used to set edx to 0 quickly. Argc is tested against 2
(instead of 1), and dl is set if argc is *greater then or equal*. If dl
gets set to 1, the **leal** instruction directly thereafter will move
the value of 5 into eax (because lea (edx,edx,4) means edx + edx \* 4,
i.e. edx \* 5).
