Chapter 10
Program Flow Constructs

The assembly language we have studied thus far is executed in sequence. In this chapter we will learn how to organize assembly language instructions to implement the other two required program flow constructs — repetition and binary decision.

Text string manipulations provide many examples of using program flow constructs, so we will use them to illustrate many of the concepts. Almost any program displays many text string messages on the screen, which are simply arrays of characters.

10.1 Repetition

The algorithms we choose when programming interact closely with the data storage structure. As you probably know, a string of characters is stored in an array. Each element of the array is of type char, and in C the end of the data is signified with a sentinel value, the NUL character (see Table 2.3 on page 49).

Array processing is usually a repetitive task. The processing of a character string is a good example of repetition. Consider the C program in Listing 10.1.

The while statement on lines 13 – 17,

controls the execution of the statements within the {…} block.

1. It evaluates the boolean expression *aString != ’\0’.
2. If the boolean expression evaluates to false, program flow jumps to the statement immediately following the {…} block.
3. If the boolean expression evaluates to true, program flow enters the {…} block and executes the statements there in sequence.
4. At the end of the {…} block program flow jumps back up to the evaluation of the boolean expression.

The pointer variable is incremented with the

statement. Notice that this variable must be changed inside the {…} block. Otherwise, the boolean expression will always evaluate to true, giving an “infinite” loop.

It is important that you identify the variable that the while construct uses to control program flow — the Loop Control Variable (LCV). Make sure that the value of the LCV is changed within the {…} block. Note that there may be more than one LCV.

The way that the while construct controls program flow can be seen in the flow chart in Figure 10.1.

This flow chart shows that we need the following assembly language tools to construct a while loop:

• Instruction(s) to evaluate boolean expressions.
• An instruction that conditionally transfers control (jumps) to another location in the program. This is represented by the large diamond, which shows two possible paths.
• An instruction that unconditionally transfers control to another location in the program. This is represented by the line that leads from “Execute body of while loop” back to the top.

We will explore instructions that provide these tools in the next three subsections.

10.1.1 Comparison Instructions

Most arithmetic and logic instructions affect the condition code bits in the rflags register. (See page 470.) In this section we will look at two instructions that are used to set the condition codes to show the relationship between two values without changing either of them.

One is cmp (compare). The syntax is

where s denotes the size of the operand:

The cmp operation consists of subtracting the source operand from the destination operand and setting the condition code bits in the rflags register accordingly. Neither of the operand values is changed. The subtraction is done internally simply to get the result and set the OF, SF, ZF, AF, PF, CF condition codes according to the result.

The other instruction is test. The syntax is

where s denotes the size of the operand:

The test operation consists of performing a bit-wise and between the two operands and setting the condition codes in the rflags register accordingly. Neither of the operand values is changed. The and operation is done internally simply to get the result and set the SF, ZF, and PF condition codes according to the result. The OF and CF are set to 0, and the AF value is undefined.

10.1.2 Conditional Jumps

These instructions are used to alter the flow of the program depending on the settings of the condition code bits in the rflags register. The general format is

where cc is a 1 – 4 letter sequence specifying the condition codes, and label is a memory location. Program flow is transferred to label if cc is true. Otherwise, the instruction immediately following the conditional jump is executed. The conditional jump instructions are listed in Table 10.1.

A good way to appreciate the meaning of the cc sequences in this table is to consider a very common application of a conditional jump:

If the value in the bl register is numerically above the value in the al register, or if they are equal, then program control transfers to the address labeled “somePlace.” Otherwise, program control continues with the movb instruction.

The differences between “greater” versus “above”, and “less” versus “below”, are a little subtle. “Above” and “below” refer to a sequence of unsigned numbers. For example, characters would probably be considered to be unsigned in most applications. “Greater” and “less” refer to signed values. Integers are commonly considered to be signed.

Table 10.2 lists four conditional jumps that are commonly used when processing unsigned values, and Table 10.3 lists four commonly used with signed values.

Since most instructions affect the settings of the condition codes in the rflags register, each must be used immediately after the instruction that determines the conditions that the programmer intends to cause the jump.

The jump instructions bring up another addressing mode — rip-relative. ¹

rip-relative:

The target is a memory address determined by adding an offset to the current address in the rip register.

syntax: a programmer-defined label example: je  somePlace

The offset, which can be positive or negative, is stored immediately following the opcode for the instruction in two’s complement format. Thus, the offset becomes a part of the instruction, similar to the immediate data addressing mode. Just like the immediate addressing mode, the offset is stored in little endian order in memory.

The following steps occur during program execution of a jcc instruction (recall Figure 6.5):

1. The jump instruction, including the offset value, is fetched.
2. As always, the rip register is incremented by the number of bytes in the jump instruction, including the offset value that is stored as part of the jump instruction.
3. If the conditions to cause a jump are true, the offset is added to the rip register.
4. If they are not true, the instruction has no effect.

When a conditional jump instruction is assembled, the assembler computes the number of bytes from the jump instruction to the specified label. The assembler then subtracts the number of bytes in the jump instruction from the distance to the label to yield the offset. This computed offset is stored as part of the jump instruction. Each jump instruction has several forms, depending on the number of bytes that must be used to store the offset. Note that the offset is stored in two’s complement format to allow for negative jumps.

For example, if the offset will fit into eight bits the opcode for the je instruction is 74₁₆, and it is 0f84₁₆ if more than eight bits are required to store the offset (in which case the offset is stored in as a thirty-two bit value). The machine code is shown in Table 10.4 for four different target address offsets. Notice that the 32-bit offsets are stored in little endian order in memory.

10.1.3 Unconditional Jump

We also need an instruction that unconditionally transfers control to another location in the program. The instruction has three forms:

Program flow is transferred to the location specified by the operand.

The first form is limited to those situations where the distance, in number of bytes, to the target location will fit within a 32-bit signed integer. The addressing mode is rip-relative. That is, the 32-bit signed integer is added to the current value in the rip register. This is sufficient for most cases.

In the other two forms, the target address is stored in the specified register or memory location, and the operand is accessed indirectly. The address is an unsigned 64-bit value. The jmp instruction moves this stored address directly into the rip register, replacing the address that was in there. The “*” character is used to indicate “indirection.”

The three ways to use an unconditional jump are shown in Listing 10.2.

The most commonly used form is rip-relative as shown on line 19:

On lines 22 – 23 an address is loaded into a register, then the jump is made indirectly via the register to that address.

Lines 26 – 28 show how an address can be stored in memory, then the memory used indirectly for the jump.

Of course, the indirect techniques are not required in this simple example, but they might be needed for some programs.

10.1.4 while Loop

We are now prepared to look at how a while loop is constructed at the assembly language level. As usual, we begin with the assembly language generated by the gcc compiler for the program in Listing 10.1, which is shown in Listing 10.3 with comments added.

Let us consider the loop:

Notice that after initializing the loop control variable it jumps to the condition test,

which is at the bottom of the loop:

Let us rearrange the instructions so that this is a true while loop — the condition test is at the top of the loop. The exit condition has been changed from jne to je for correctness. The original is on the left, the rearranged on the right:

We also see another version of the mov instruction on line 22 of the compiler’s version:

This instruction converts the data size from 8-bit to 32-bit, placing zeros in the high-order 24 bits, as it copies the byte from memory to the eax register. The memory address of the copied byte is in the rax register. (Yes, this instruction writes over the address in the register as it executes.)

The x86-64 architecture includes instructions for extending the size of a value by adding more bits to the left. There are two ways to do this:

• Sign extend — copy the sign bit to each of the new high-order bits. For example, when sign extending an 8-bit value to 16 bits, 85 would become ff85, but 75 would become 0075.
• Zero extend — make each of the new high-order bits zero. When zero extending 85 to sixteen bits, it becomes 0085.

Sign extension can be accomplished with the movs instruction:

where s denotes the size of the source operand and d the size of the destination operand. (Use the s column for d.)

In the Intel syntax the instruction is movsx. The size of the data is determined by the operands, so the size characters (b, w, l, or q) are not appended to the instruction, and the order of the operands is reversed.

In some cases the Intel syntax is ambiguous. Intel-syntax assemblers use keywords to specify the data size in such cases. For example, the nasm assembler uses
    movsx destination, BYTE [source]
to move one byte and zero extend, and uses
    movsx destination, WORD [source]
to move two bytes and sign extend.

Zero extension can be accomplished with the movz instruction:

where s denotes the size of the source operand and d the size of the destination operand. (Use the s column for d.)

In the Intel syntax the instruction is movzx The size of the data is determined by the operands, so the size characters (b, w, l, or q) are not appended to the instruction, and the order of the operands is reversed.

There is also a set of instructions that double the size of data in portions of the rax register, shown in Table 10.5. The doubling operation includes sign extention into the affected higher-order portion of the register.

Notice that these instructions do not explicitly specify any operands, but they may change the rax register. They do not affect the condition codes in the rflags register.

Returning to while loops, the general structure of a count-controlled while loop is shown in Listing 10.4.

This is not a complete program or even a function. It simply shows the key elements of a while loop.

Our assembly language version of a “Hello world” program in Listing 10.5 uses a sentinel-controlled while loop.

Consider the sequence on lines 26 – 28:

We had to move the pointer value into a register in order to dereference the pointer. These two instructions implement the C expression:

In particular, you have to move the address into a register, then dereference it with the “(register)” syntax.

There are two common errors when using the assembly language syntax.

• The assembly language dereference operator does not work on variable names. For example, you cannot use
          cmpb    $0, (ptr(%rbp))  # *** DOES NOT WORK ***

  to dereference the variable, ptr.

  Neither do

          cmpb $0, (theString)   # *** DOES NOT WORK ***

  nor

          cmpb $0, (\$theString)   # *** DOES NOT WORK ***

  work to dereference the theString location. Unfortunately, the assembler may not consider any of these to be syntax errors, just an unnecessary set of parentheses. Therefore, you probably will not get an assembler error message, just incorrect program behavior.

• Another common error is to forget to dereference the register once you get the address stored in it:
          cmpb    $0, %esi  # *** DOES NOT WORK ***

  This would compare a byte in the esi register itself with the value zero. Since there are four bytes in the esi register, this code will generate an assembler warning message because it does not specify which byte.

We also need to add one to the pointer variable so as to move it to the next character in the string. Adding one is a common operation, so there is an operator that simply adds one,

where s denotes the size of the operand:

On line 35 of the program in Listing 10.5, incl is used to add one to the address stored in memory:

Subtracting one from a counter is also a common operation. The dec instruction subtracts one from an operand and sets the rflags register accordingly. The operand can be a register or a memory location.

where s denotes the size of the operand:

A decl instruction is used on line 27 in Listing 10.6 to both subtract one from the counter variable and to set the condition codes in the rflags register for the jg instruction.

This is clearly better than using

This program also demonstrates how to implement a do-while loop.

10.2 Binary Decisions

We now know how to implement two of the primary program flow constructs — sequence and repetition. We continue on with the third — binary decision. You know this construct from C/C++ as the if-else.

We start the discussion with a common example — a simple program that asks the user whether changes should be saved or not (Listing 10.7). This example program does not do anything, so there really is nothing to change, but you have certainly seen this construct. (As usual, this program is meant to illustrate concepts, not good C/C++ programming practices.)

Let’s look at the flow of the program that the if-else controls.

1. The boolean expression (response == ’y’) is evaluated.
2. If the evaluation is true, the first block, the one that displays “Changes saved.”, is executed.
3. If the evaluation is false, the second block, the one that displays “Changes discarded.”, is executed.
4. In both cases the next statement to be executed is the return 0;

The program control flow of the if-else construct is illustrated in Figure 10.2.

We already know all the assembly language instructions needed to implement the if-else in Listing 10.7. The important thing to note is that there must be an unconditional jump at the end of the “then” block to transfer program flow around the “else” block. The assembly language generated for this program is shown in Listing 10.8.