A longer example

Here is a long(er) example to illustrate the concepts introduced in this module. To make the “diff” between revisions stand out more, you can copy-and-paste each section of code into files. Then, use vimdiff or a similar visualized diff command to have the changes highlighted. If you have XWindow running, there is a whole list of these tools: tkdiff, xxdiff, diffuse, gvimdiff, etc.

int x,y,z;
int main(void)
{
  x = 5;
  z = 0;
  while (x > 0)
  {
    y = 0;
    while (y < 5)
    {
      if (((x > 2) && (x != y)) || (y == 1))
      {
        z = z + x;
      }
    }
  }
}

This program no particular “meaning” as in useful behavior, its only purpose is to serve as an example.

First, I can comment out the entire program, and start to work on it little-by-little. This can be done with a single command in vi, there is a reason to learn how to use it!

# int x,y,z;
# int main(void)
# {
#   x = 5;
#   z = 0;
#   while (x > 0)
#   {
#     y = 0;
#     while (y < 5)
#     {
#       if (((x > 2) && (x != y)) || (y == 1))
#       {
#         z = z + x;
#       }
#     }
#   }
# }

Next, let us divide the data portion from the code portion. We can also insert the program template to start and exit.

# int x,y,z;
.data
x: .int 0
y: .int 0
z: .int 0
.text
.global _start
# int main(void)
_start:
# {
#   x = 5;
#   z = 0;
#   while (x > 0)
#   {
#     y = 0;
#     while (y < 5)
#     {
#       if (((x > 2) && (x != y)) || (y == 1))
#       {
#         z = z + x;
#       }
#     }
#   }
# }
movl $1,%eax
movl $0,%ebx
int $0x80

# int x,y,z;
.data
x: .int 0
y: .int 0
z: .int 0
.text
.global _start
# int main(void)
_start:
# {
#   x = 5;
    movl $5,x
#   z = 0;
    movl $0,z
#   while (x > 0)
#   {
#     y = 0;
      movl $0,y
#     while (y < 5)
#     {
#       if (((x > 2) && (x != y)) || (y == 1))
#       {
#         z = z + x;
#       }
#     }
#   }
# }
movl $1,%eax
movl $0,%ebx
int $0x80

Adding x to z requires an intermediate register, but otherwise it is also straightforward.

# int x,y,z;
.data
x: .int 0
y: .int 0
z: .int 0
.text
.global _start
# int main(void)
_start:
# {
#   x = 5;
    movl $5,x
#   z = 0;
    movl $0,z
#   while (x > 0)
#   {
#     y = 0;
      movl $0,y
#     while (y < 5)
#     {
#       if (((x > 2) && (x != y)) || (y == 1))
#       {
#         z = z + x;
          movl x,%eax
          addl %eax,z
#       }
#     }
#   }
# }
movl $1,%eax
movl $0,%ebx
int $0x80

Now let us take care of the inner-most conditional statement. First, we reduce to “ugly” conditional statement code:

# int x,y,z;
.data
x: .int 0
y: .int 0
z: .int 0
.text
.global _start
# int main(void)
_start:
# {
#   x = 5;
    movl $5,x
#   z = 0;
    movl $0,z
#   while (x > 0)
#   {
#     y = 0;
      movl $0,y
#     while (y < 5)
#     {
#       // if (((x > 2) && (x != y)) || (y == 1))
#       if (!(((x > 2) && (x != y)) || (y == 1))) goto endIf1
#       {
#         z = z + x;
          movl x,%eax
          addl %eax,z
#       }
#       endIf1:
#     }
#   }
# }
movl $1,%eax
movl $0,%ebx
int $0x80

DeMorgan’s law allows us to simplify the negated disjunction a little. DeMorgan’s law says X + Y = X ⋅Y . Then, we can optimize a negation out by using a different comparison operator. As a result, we have the following code:

Now is a good time to take care of the conjunction. We can reduce the conjunction by converting the conditional-goto into multiple statements:

# int x,y,z;
.data
x: .int 0
y: .int 0
z: .int 0
.text
.global _start
# int main(void)
_start:
# {
#   x = 5;
    movl $5,x
#   z = 0;
    movl $0,z
#   while (x > 0)
#   {
#     y = 0;
      movl $0,y
#     while (y < 5)
#     {
#       // if (((x > 2) && (x != y)) || (y == 1))
#       // if (!(((x > 2) && (x != y)) || (y == 1))) goto endIf1
#       // if (!((x > 2) && (x != y)) && (y != 1)) goto endIf1
#       if ((x > 2) && (x != y)) goto if1_1;
#       if (y != 1) goto endIf1
        if1_1:
#       {
#         z = z + x;
          movl x,%eax
          addl %eax,z
#       }
#       endIf1:
#     }
#   }
# }
movl $1,%eax
movl $0,%ebx
int $0x80

# int x,y,z;
.data
x: .int 0
y: .int 0
z: .int 0
.text
.global _start
# int main(void)
_start:
# {
#   x = 5;
    movl $5,x
#   z = 0;
    movl $0,z
#   while (x > 0)
#   {
#     y = 0;
      movl $0,y
#     while (y < 5)
#     {
#       // if (((x > 2) && (x != y)) || (y == 1))
#       // if (!(((x > 2) && (x != y)) || (y == 1))) goto endIf1
#       // if (!((x > 2) && (x != y)) && (y != 1)) goto endIf1
#       if ((x > 2) && (x != y)) goto if1_1;
#       // if (y != 1) goto endIf1
        cmpl $1,y
        jnz  endIf1
        if1_1:
#       {
#         z = z + x;
          movl x,%eax
          addl %eax,z
#       }
        endIf1:
#     }
#   }
# }
movl $1,%eax
movl $0,%ebx
int $0x80

# int x,y,z;
.data
x: .int 0
y: .int 0
z: .int 0
.text
.global _start
# int main(void)
_start:
# {
#   x = 5;
    movl $5,x
#   z = 0;
    movl $0,z
#   while (x > 0)
#   {
#     y = 0;
      movl $0,y
#     while (y < 5)
#     {
#       // if (((x > 2) && (x != y)) || (y == 1))
#       // if (!(((x > 2) && (x != y)) || (y == 1))) goto endIf1
#       // if (!((x > 2) && (x != y)) && (y != 1)) goto endIf1
#       // if ((x > 2) && (x != y)) goto if1_1;
#       if (x <= 2) goto if1_2;
#       if (x != y) goto if1_1;
        if1_2:
#       // if (y != 1) goto endIf1
        cmpl $1,y
        jnz  endIf1
        if1_1:
#       {
#         z = z + x;
          movl x,%eax
          addl %eax,z
#       }
        endIf1:
#     }
#   }
# }
movl $1,%eax
movl $0,%ebx
int $0x80

# int x,y,z;
.data
x: .int 0
y: .int 0
z: .int 0
.text
.global _start
# int main(void)
_start:
# {
#   x = 5;
    movl $5,x
#   z = 0;
    movl $0,z
#   while (x > 0)
#   {
#     y = 0;
      movl $0,y
#     while (y < 5)
#     {
#       // if (((x > 2) && (x != y)) || (y == 1))
#       // if (!(((x > 2) && (x != y)) || (y == 1))) goto endIf1
#       // if (!((x > 2) && (x != y)) && (y != 1)) goto endIf1
#       // if ((x > 2) && (x != y)) goto if1_1;
#       // if (x <= 2) goto if1_2;
        cmpl $2,x
        jng  if1_2
#       // if (x != y) goto if1_1;
        movl y,%eax
        cmpl %eax,x
        jnz  if1_1
        if1_2:
#       // if (y != 1) goto endIf1
        cmpl $1,y
        jnz  endIf1
        if1_1:
#       {
#         z = z + x;
          movl x,%eax
          addl %eax,z
#       }
        endIf1:
#     }
#   }
# }
movl $1,%eax
movl $0,%ebx
int $0x80

Now is a good time to test the code with different combinations of values for the variables. Once the conditional statement is checked, we can work on the inner loop.

# int x,y,z;
.data
x: .int 0
y: .int 0
z: .int 0
.text
.global _start
# int main(void)
_start:
# {
#   x = 5;
    movl $5,x
#   z = 0;
    movl $0,z
#   while (x > 0)
#   {
#     y = 0;
      movl $0,y
#     // while (y < 5)
#     if (y >= 5) goto endWhile1
#     {
#       // if (((x > 2) && (x != y)) || (y == 1))
#       // if (!(((x > 2) && (x != y)) || (y == 1))) goto endIf1
#       // if (!((x > 2) && (x != y)) && (y != 1)) goto endIf1
#       // if ((x > 2) && (x != y)) goto if1_1;
#       // if (x <= 2) goto if1_2;
        cmpl $2,x
        jng  if1_2
#       // if (x != y) goto if1_1;
        movl y,%eax
        cmpl %eax,x
        jnz  if1_1
        if1_2:
#       // if (y != 1) goto endIf1
        cmpl $1,y
        jnz  endIf1
        if1_1:
#       {
#         z = z + x;
          movl x,%eax
          addl %eax,z
#       }
        endIf1:
#     }
      endWhile1:
#   }
# }
movl $1,%eax
movl $0,%ebx
int $0x80

Note the use of indentation makes it (relatively) easy to locate the beginning and the end of the inner while loop. Next, we translate the inner loop to assembly code:

# int x,y,z;
.data
x: .int 0
y: .int 0
z: .int 0
.text
.global _start
# int main(void)
_start:
# {
#   x = 5;
    movl $5,x
#   z = 0;
    movl $0,z
#   while (x > 0)
#   {
#     y = 0;
      movl $0,y
#     // while (y < 5)
#     // if (y >= 5) goto endWhile1
      cmpl $5,y
      jnl  endWhile1
#     {
#       // if (((x > 2) && (x != y)) || (y == 1))
#       // if (!(((x > 2) && (x != y)) || (y == 1))) goto endIf1
#       // if (!((x > 2) && (x != y)) && (y != 1)) goto endIf1
#       // if ((x > 2) && (x != y)) goto if1_1;
#       // if (x <= 2) goto if1_2;
        cmpl $2,x
        jng  if1_2
#       // if (x != y) goto if1_1;
        movl y,%eax
        cmpl %eax,x
        jnz  if1_1
        if1_2:
#       // if (y != 1) goto endIf1
        cmpl $1,y
        jnz  endIf1
        if1_1:
#       {
#         z = z + x;
          movl x,%eax
          addl %eax,z
#       }
        endIf1:
#     }
      endWhile1:
#   }
# }
movl $1,%eax
movl $0,%ebx
int $0x80

This is a good time to test the inner loop. Once the inner loop is tested (to a certain extent), it is time to complete the outer loop. I am combining all the steps, as it gets boring after a while!

# int x,y,z;
.data
x: .int 0
y: .int 0
z: .int 0
.text
.global _start
# int main(void)
_start:
# {
#   x = 5;
    movl $5,x
#   z = 0;
    movl $0,z
#   // while (x > 0)
#   // if (x <= 0) goto endWhile2
    cmpl $0,x
    jng  endWhile2
#   {
#     y = 0;
      movl $0,y
#     // while (y < 5)
#     // if (y >= 5) goto endWhile1
      cmpl $5,y
      jnl  endWhile1
#     {
#       // if (((x > 2) && (x != y)) || (y == 1))
#       // if (!(((x > 2) && (x != y)) || (y == 1))) goto endIf1
#       // if (!((x > 2) && (x != y)) && (y != 1)) goto endIf1
#       // if ((x > 2) && (x != y)) goto if1_1;
#       // if (x <= 2) goto if1_2;
        cmpl $2,x
        jng  if1_2
#       // if (x != y) goto if1_1;
        movl y,%eax
        cmpl %eax,x
        jnz  if1_1
        if1_2:
#       // if (y != 1) goto endIf1
        cmpl $1,y
        jnz  endIf1
        if1_1:
#       {
#         z = z + x;
          movl x,%eax
          addl %eax,z
#       }
        endIf1:
#     }
      endWhile1:
#   }
    endWhile2:
# }
movl $1,%eax
movl $0,%ebx
int $0x80

7 A longer example