8.4: Branching

Last updated
Save as PDF

Page ID: 76134

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

8.4.1 Simple If statements

Now that the handling of conditional logic has been covered, how to use this knowledge to implement branching and looping can be addressed.

This section will begin with a small pseudo code example of an if statement.

if (r1 > 0) 
{ 
    print("Number is positive") 
}

In this statement, the value in r1 is checked to see if it is a positive integer. If it is, the string “Number is positive” is printed, otherwise nothing happens. The most important characteristic of this code fragment is the statement that prints the output happens when the condition is positive. This might seem obvious, but taking note of it now will save confusion very soon.

The second thing to notice is that in this code fragment the statement that is executed is a code block contained between the curly brackets (“{” and “}”). Any code block that is between curly brackets is the equivalent of a statement, which is why this works. However, for the sake of clarity in this discussion all branching will be into a code block.

This simple if statement will begin to define the canonical form for an if statement. Here the form is simple:

    CMP r1, r2 
    B{condition flag for false} End_If_Label 
        block of code to enter if condition is true 
    End_If_Label

Note that if the condition tested for is true, the block should be entered. Therefore, the condition flag to check is the condition flag for the false condition. This is obvious if it is thought about, but most programmers instinctively want to branch on the positive condition. Branching on the positive condition actually invalidates structured programming, where blocks are checked and entered, each in turn, if the condition is positive. It leads to branching to solve the immediate problem, and quickly devolves to spaghetti code. That is why almost all students that the author has encountered, when left to their own devices in assembly, reinvent spaghetti code. Disorganized code is the natural orientation, and organized systems are unnatural if not enforced.

The if statement in the pseudo code above is now implemented in the following program.

    .text 
    .global main 
main: 
    SUB sp, sp, #4 
    STR lr, [sp, #0] 
    
    MOV r2, #92
    MOV r1, #0 
    CMP r2, r1 
    BLE EndIf 
        LDR r0, =IsPositive 
        BL printf 
    EndIf:
    
    LDR lr, [sp, #0] 
    ADD sp, sp, #4 
    MOV pc, lr
    
.data 
    IsPositive: .asciz "Number is Positive\n"

8.4.2 Complex logical statements

While the example above showed how to translate a single logical condition, it begs the question of how to translate complex logical conditions. Programmers might think that to translate a condition such as the one that follows requires complex programming logic. Remember that ASCII codes for a number n is an integer value such that 30 ≤ n ≤ 39, and the integer value of n, called i here, is i = n – 30. This is the result of the following code fragment:

if ((n >= 30) && (n <= 39)) 
    i = n – 30;

One of the reasons programs became complex before structured programming became prevalent is that programmers would try to solve this type of complex logical condition by reasoning about the program. This could result in mostly uncommented code that would look very similar to the following program. For readers who recognize this type of program, you are old. For those of you who do not believe programs like this existed, this is actually nice code. It is indented, does not have a hug number of variables in a single global memory, and it works. This would have been uncommon before language that use structured constructs, like C or Java.

.text 
    .global main 
main: 
    SUB sp, sp, #4 
    STR lr, [sp, #0] 
    
    MOV r0, #0x32 
    BL converToInt 
    
    LDR lr, [sp, #0] 
    ADD sp, sp, #4 
    MOV pc, lr
    
converToInt: 
    SUB sp, sp, #4 
    STR lr, [sp, #0] 
    
    mov r4, #0x30 
    cmp r0, r4 
    blt NotANumber 
    
    mov r4, #0x39 
    cmp r0, r4 
    blt convert 
    b NotANumber
    
IsANumber: 
    LDR lr, [sp, #0] 
    ADD sp, sp, #4 
    MOV pc, lr
    
NotANumber: 
    LDR r0, =output 
    BL printf 
    
    LDR lr, [sp, #0] 
    ADD sp, sp, #4 
    MOV pc, lr
    
convert: 
    SUB r0, #0x30 
    B IsANumber
    
.data 
    output: .asciz "NAN\n"

If reasoning about a program is a bad choice to solve logic, how should a programmer proceed? The easy way to solve this problem is to realize that in a HLL, the compiler is going to reduce the complex logical condition into a logical equation that will reduce into a logical (or boolean) variable.

To begin, most HLLs represent a boolean (or logical) variable as a 32-bit value where only the lowest order bit is used. Since only one bit is used, this reduces the equation to a simple logic expression. In face, if the upper 31 bits are assumed to be 0, and only the single lowest order bit is considered, all of the bitwise operations (with the exception of logical NOT) become logical operations. The complex if statement above would be translated into the equivalent of the following code fragment:

    boolean logical = (n >= 30) && (n <= 39));
    if (logical) 
        i = n – 30;

This code fragment is easily translated into the following assembly language code fragment. Note that in this code fragment r4 and r5 will only have a value of 0 or 1, bits 1..31 will always be 0.

    .text 
    .global main

main: 
    SUB sp, sp, #4 
    STR lr, [sp, #0] 
    
    MOV r0, #0x32 
    BL convertToInt 
    
    LDR lr, [sp, #0] 
    ADD sp, sp, #4 
    MOV pc, lr 
# End main 

convertToInt: 
    SUB sp, sp, #4 
    STR lr, [sp, #0] 
    
    MOV r4, #0 
    MOV r1, #0x30 
    CMP r0, r1 
    MOVGT r4, #1 
    
    MOV r5, #0 
    MOV r1, #0x39 
    CMP r0, r1 
    MOVLT r5, #1 
    
    AND r4, r4, r5 
    
    MOV r1, #0 
    CMP r4, r1 
    BEQ Else 
        SUB r0, r0, #0x30 
        B EndIf 
    Else: 
        ldr r0, =output 
        BL printf
    EndIf:
        LDR lr, [sp, #0] 
        ADD sp, sp, #4 
        MOV pc, lr
.data 
    output: .asciz "NAN\n"

The code for using the logical variable is roughly the same amount of code as the spaghetti code, but I believe most readers will find it much easier to follow, even though it is not documented. This is because the code is logically coherent. It doesn’t require a lot of interleaving reasoning with confusing branching, implementing what is effectively unrestricted goto statements. As the exercises at the end of the chapter will show, this structure for processing logical statements grows linearly in complexity, whereas the complexity of using program reasoning becomes overwhelming complex quickly.

8.4.3 If-Else statements

A more useful version of the if statement also allows for the false condition, or an if-else statement. If the condition is true, the first block is executed, otherwise the second block is executed. A simple code fragment illustrating this point is shown below.

if (($r0 > 0) == 0) 
{ 
    print("Number is positive") 
} 
else 
{ 
    print("Number is negative") 
}

This is a modification to the logic in the simple if statement. This code will output an answer stating if the value in r0 is positive or negative. This section builds on the if statement to show how to translate an if-else statement from pseudo code to assembly language. To translate the if-else statement, use the following steps.

Implement the conditional part of the statement to create a logical variable that indicates whether to enter the block or branch.
Add two labels to the program, one for the else and one for the end of the if (e.g., an endIf label). The branch should be inserted after the evaluation of the logical variable. The negative condition for the branch will be to the else label. This allows the positive condition to sequentially flow into the if block.
At the end of the if block, branch around the else block by using an unconditional branch statement to the endIf. You now have the basic structure of the if statement, and your code should like the following assembly code fragment.

MOV r1, #0 
CMP r0, r1 
BLE Else 
    # if block 
    B EndIf 
Else: 
    #else block 
EndIf:

4. Once the structure of the if-else statement is in place, you should put the code for the blocks into the program. This completes the if-else statement translation. This is the following program.

.text 
    .global main 

main: 
    SUB sp, sp, #4 
    STR lr, [sp, #0] 
    
    MOV r0, #-0x32 
    
    # (if r0 > 0) 
    MOV r1, #0 
    CMP r0, r1 
    BLE Else 
        # Code block for if 
        LDR r0, =positive 
        BL printf 
        B EndIf 
    
    Else: 
        # Code block for else 
        LDR r0, =negative 
        BL printf 
        
    EndIf: 
    
    LDR lr, [sp, #0] 
    ADD sp, sp, #4 
    MOV pc, lr 
# End main
.data 
    positive: .asciz "Number is Positive\n" 
    negative: .asciz "Number is Negative\n"

8.4.4 If-Else If-Else statements

The final type of branch to be introduced in this text allows the programmer to choose one of several options. It is implemented as an if-elseif-else statement. In this statement, the if and elseif statements will contain a conditional to decide if they will be executed or not. The else will be automatically chosen if no condition is true.

To introduce the if-elseif-else statement, the following code fragment that translates a number grade into a letter grade is implemented. The following pseudo code fragment shows the logic for this if-elseif-else statement.

if (grade > 100) || grade < 0) 
{ 
    print("Grade must be between 0..100") 
} 
elseif (grade >= 90) 
{ 
    print("Grade is A") 
} 
elseif (grade >= 80) 
{ 
    print("Grade is B") 
} 
elseif (grade >= 70) 
{ 
    print("Grade is C") 
} 
elseif (grade >= 60) 
{
    print("Grade is D") 
} 
else{ 
    print("Grade is F") 
}

To translate the if-else if-else statement, once again the overall structure for the statement will be generated, and then the code blocks will be filled in. Readers and programmers are strongly encouraged to implement algorithmic logic in this manner. Students who want to implement the code using some sort of reasoning will find themselves completely overwhelmed and will miss many important algorithmic decisions, especially when blocks containing other blocks as nested logic are used later in this chapter.

The steps in the translation of the if-else if-else statement are as follows.

1. Implement the beginning of the statement with a comment, and place a label in the code for each elseif condition, and for the final else and EndIf conditions. At the end of each code block, place a branch to the end-if label (once any block is executed, you will exit the entire if-elseif-else statement). Your code would look as follows:

#if block
    # first if check, invalid input block 
    b EndIf 
grade_A: 
    b EndIf 
grade_B: 
    b EndIf 
grade_C: 
    b EndIf 
grade_D: 
    b EndIf 
else: 
    b EndIf 
End_If:

2. Next put the logic conditions in the beginning of each if and elseif block. In these if and elseif statements the code will branch to the next label. When this step is completed, you should now have code that looks something like the following (note: the grade is in r4):

#if block
    #check 0 <= r4 <= 100 
    MOV r1, #0 
    MOV r0, #0 
    CMP r4, r0 
    MOVGE r0, #1 
    
    MOV r2, #0 
    MOV r0, #100 
    CMP r4, r0 
    MOVLE r2, #1 
    
    AND r1, r1, r2 
    MOV r2, #1 
    CMP r1, r2 
    BEQ grade_A // Grade is valid 
    
    # Code block for Invalid Grade 
    B EndIf
grade_A: 
    MOV r0, #90 
    CMP r4, r0 
    BLT grade_B 
    
    # Code block for grade of A 
    B EndIf
    
grade_B: 
    MOV r0, #80 
    CMP r4, r0 
    BLT grade_C 
    
    # Code block for grade of B 
    B EndIf
    
grade_C: 
    MOV r0, #70 
    CMP r4, r0 
    BLT grade_D 
    
    # Code block for grade of C 
    B EndIf
    
grade_D: 
    MOV r0, #60 
    CMP r4, r0 
    BLT Else 
    
    # Code block for grade of D 
    B EndIf

Else: 
    # Code block for grade of F
    B EndIf

EndIf:

3. The last step is to fill in the code blocks with the appropriate logic. The following program implements this completed if-elseif-else statement. This final program, called CheckGrades.s, is shown below.

.text 
.global main 

main: 
# Save return to os on stack 
    SUB sp, sp, #4 
    STR lr, [sp, #0] 
    
    MOV r4, #92 
    
#if block 
    #check 0 <= r4 <= 100 
    MOV r1, #0 
    MOV r0, #0 
    CMP r4, r0 
    MOVGE r1, #1 
    
    MOV r2, #0 
    MOV r0, #100 
    CMP r4, r0 
    MOVLE r2, #1 
    
    AND r1, r1, r2 
    MOV r2, #1 
    CMP r1, r2 
    BEQ grade_A // Grade is valid 
    
    # Code block for Invalid Grade 
    LDR r0, =Invalid 
    BL printf 
    B EndIf 
    
    grade_A: 
    MOV r0, #90 
    CMP r4, r0 
    BLT grade_B 
        
    # Code block for grade of A 
    LDR r0, =GradeA 
    BL printf 
    B EndIf
    
    grade_B: 
    MOV r0, #80 
    CMP r4, r0 
    BLT grade_C
    
    # Code block for grade of B 
    LDR r0, =GradeB 
    BL printf 
    B EndIf
    
    grade_C: 
    MOV r0, #70 
    CMP r4, r0 
    BLT grade_D 
    
    # Code block for grade of C 
    LDR r0, =GradeC 
    BL printf 
    B EndIf
    
    grade_D: 
    MOV r0, #60 
    CMP r4, r0 
    BLT Else 
    
    # Code block for grade of D 
    LDR r0, =GradeD 
    BL printf 
    B EndIf
    
    Else: 
    # Code block for grade of F 
    LDR r0, =GradeF 
    BL printf 
    B EndIf 
    
    EndIf:
    
# Return to the OS 
    ldr lr, [sp, #0] 
    add sp, sp, #4 
    mov pc, lr
    
.data 
    GradeA: .asciz "Grade is A\n" 
    GradeB: .asciz "Grade is B\n" 
    GradeC: .asciz "Grade is C\n" 
    GradeD: .asciz "Grade is D\n" 
    GradeF: .asciz "Grade is F\n" 
    Invalid: .asciz "Grade must be 0 <= grade <= 100\n"