Section 12.3 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 high-level languages as the if or if-else statement.
Subsection 12.3.1 Simple 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 12.3.1). 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.)
/* yesNo1.c
* Prompts user to enter a y/n response.
* 2017-09-29: Bob Plantz
*/
#include <unistd.h>
int main(void)
{
char *prompt = "Save changes? ";
char *yes = "Changes saved.\n";
char *no = "Changes discarded.\n";
char response;
while (*prompt != '\0') {
write(STDOUT_FILENO, prompt, 1);
prompt++;
}
read (STDIN_FILENO, &response, 1);
if (response == 'y') {
while (*yes != '\0') {
write(STDOUT_FILENO, yes, 1);
yes++;
}
}
else {
while (*no != '\0') {
write(STDOUT_FILENO, no, 1);
no++;
}
}
return 0;
}
Let's look at the flow of the program that the if-else controls:
The Boolean expression
(response == 'y')is evaluated.If the evaluation is true, the first block, the one that displays “Changes saved.”, is executed.
If the evaluation is false, the second block, the one that displays “Changes discarded.”, is executed.
In both cases the next statement to be executed is
return 0;.
The way that the if-else construct controls program flow can be seen from the flow chart in Figure 12.3.2.
if-else construct. The large diamond represents a binary decision that leads to two possible paths, “true” or “false.” Either the “then” block or the “else” block is executed, but not both. Each leads to the end of the if-else construct.This flow chart shows that we need the following assembly language tools to construct an if-else:
Instruction(s) to evaluate Boolean expressions.
An instruction that conditionally transfers control (branches) 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 ‘Then’ part” to the end of the
if-elseconstruct. Program control must branch around the “Else” part.
We already know the instructions that are needed to implement an if-else construct. The important thing to note is that there must be an unconditional branch 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 12.3.3.
.arch armv6
.fpu vfp
.file "yesNo1.c"
.section .rodata
.align 2
.LC0:
.ascii "Save changes? \000"
.align 2
.LC1:
.ascii "Changes saved.\012\000"
.align 2
.LC2:
.ascii "Changes discarded.\012\000"
.text
.align 2
.global main
.type main, %function
main:
@ args = 0, pretend = 0, frame = 16
@ frame_needed = 1, uses_anonymous_args = 0
stmfd sp!, {fp, lr}
add fp, sp, #4
sub sp, sp, #16
ldr r3, .L11 @@ prompt message
str r3, [fp, #-8]
ldr r3, .L11+4 @@ "yes" message
str r3, [fp, #-12]
ldr r3, .L11+8 @@ "no" message
str r3, [fp, #-16]
b .L2
.L3:
mov r0, #1
ldr r1, [fp, #-8]
mov r2, #1
bl write
ldr r3, [fp, #-8]
add r3, r3, #1
str r3, [fp, #-8]
.L2:
ldr r3, [fp, #-8]
ldrb r3, [r3] @ zero_extendqisi2
cmp r3, #0
bne .L3
sub r3, fp, #17 @@ address of response
mov r0, #0
mov r1, r3
mov r2, #1
bl read
ldrb r3, [fp, #-17] @ zero_extendqisi2
cmp r3, #121 @@ is it 'y'?
bne .L4 @@ no, branch to "no" message
b .L5 @@ yes, do "yes" message
.L6:
mov r0, #1
ldr r1, [fp, #-12]
mov r2, #1
bl write
ldr r3, [fp, #-12]
add r3, r3, #1
str r3, [fp, #-12]
.L5:
ldr r3, [fp, #-12]
ldrb r3, [r3] @ zero_extendqisi2
cmp r3, #0
bne .L6
b .L7 @@ branch over else part
.L4:
b .L8 @@ else part
.L9:
mov r0, #1 @@ do "no" message
ldr r1, [fp, #-16]
mov r2, #1
bl write
ldr r3, [fp, #-16]
add r3, r3, #1
str r3, [fp, #-16]
.L8:
ldr r3, [fp, #-16]
ldrb r3, [r3] @ zero_extendqisi2
cmp r3, #0
bne .L9
.L7:
mov r3, #0
mov r0, r3
sub sp, fp, #4
@ sp needed
ldmfd sp!, {fp, pc}
.L12:
.align 2
.L11:
.word .LC0
.word .LC1
.word .LC2
.ident "GCC: (Raspbian 4.9.2-10) 4.9.2"
This program introduces a new instruction, ldrb, which as you probably guess, loads a byte from memory. We also introduce the strb instruction for completness.
LDRB-
Loads a byte from memory into a register and zeroes the 24 high-order bits.
LDRB<c> <Rt>, <label> % Label LDRB<c> <Rt>, [<Rn>{, #+/-<imm>}] % Offset, immediate LDRB<c> <Rt>, [<Rn>, #+/-<imm>]! % Pre-indexed, immediate LDRB<c> <Rt>, [<Rn>], #+/-<imm> % Post-indexed, immediate LDRB<c> <Rt>, [<Rn>, +/-<Rm>{, <shift>}] % Offset, register LDRB<c> <Rt>, [<Rn>, +/-<Rm>{, <shift>}]! % Pre-indexed, register LDRB<c> <Rt>, [<Rn>], +/-<Rm>{, <shift>} % Post-indexed, register<c>is the condition code, Table 9.2.1.<Rt>is the destination register,<Rn>is the base register, and<Rm>contains an offset value.<label>is a labeled memory address.<imm>is a signed integer in the range \(-2048 \ldots +2047\text{.}\)
The memory address to load the word from is determined the following way (further explained in Section 11.1):
The Label form uses the address corresponding to the
<label>.In the Offset form, the signed integer is added to the value in the base register,
<Rn>, the value at this address is loaded into<Rt>, but the base register is not changed.In the Pre-indexed form, the signed integer is added to the value in the base register,
<Rn>, the base register is updated to the new address, and then the value at this new address is loaded into<Rt>.In the Post-indexed form, the signed integer is added to the value in the base register,
<Rn>, the value at this new address is loaded into<Rt>, and then the base register is updated to the new address.
STRB-
Stores a word from a register into memory.
STRB<c> <Rt>, <label> % Label STRB<c> <Rt>, [<Rn>{, #+/-<imm>}] % Offset, immediate STRB<c> <Rt>, [<Rn>, #+/-<imm>]! % Pre-indexed, immediate STRB<c> <Rt>, [<Rn>], #+/-<imm> % Post-indexed, immediate STRB<c> <Rt>, [<Rn>, +/-<Rm>{, <shift>}] % Offset, register STRB<c> <Rt>, [<Rn>, +/-<Rm>{, <shift>}]! % Pre-indexed, register STRB<c> <Rt>, [<Rn>], +/-<Rm>{, <shift>} % Post-indexed, register<c>is the condition code, Table 9.2.1.<Rt>is the source register, and<Rn>is the base register.<label>is a labeled memory address.<imm>is a signed integer in the range \(-2048 \ldots +2047\text{.}\)
The memory address to store the word at is determined the following way (further explained in Section 11.1):
The Label form uses the address corresponding to the
<label>.In the Offset form, the signed integer is added to the value in the base register,
<Rn>, the value in<Rt>is stored at this address, but the base register is not changed..In the Pre-indexed form, the signed integer is added to the value in the base register,
<Rn>, the base register is updated to the new address, and then the value in<Rt>is stored at this address.In the Post-indexed form, the signed integer is added to the value in the base register,
<Rn>, the value in<Rt>is stored at this address, and then the base register is updated to the new address.
Our assembly language version of the yes/no program in Listing 12.3.4 follows this general pattern. It, of course, uses more meaningful labels than what the compiler generated.
@ yesNo2.s
@ Prompts user to enter a y/n response.
@ 2017-09-29: Bob Plantz
@ Define my Raspberry Pi
.cpu cortex-a53
.fpu neon-fp-armv8
.syntax unified @ modern syntax
@ Useful source code constants
.equ STDOUT,1
.equ STDIN,0
.equ NUL,0
.equ response,-20
.equ local,8
@ Constant program data
.section .rodata
.align 2
prompt:
.asciz "Save changes? "
.align 2
yes:
.asciz "Changes saved.\n"
.align 2
no:
.asciz "Changes discarded.\n"
@ The program
.text
.align 2
.global main
.type main, %function
main:
sub sp, sp, 16 @ space for saving regs
@ (keeping 8-byte sp align)
str r4, [sp, 4] @ save r4
str fp, [sp, 8] @ fp
str lr, [sp, 12] @ lr
add fp, sp, 12 @ set our frame pointer
sub sp, sp, local @ local variable
ldr r4, promptAddr @ prompt user
promptLoop:
ldrb r3, [r4] @ get a char
cmp r3, NUL @ end of string?
beq getResponse @ yes, get response
mov r0, STDOUT @ no, write to screen
mov r1, r4 @ address of current char
mov r2, 1 @ write 1 byte
bl write
add r4, r4, 1 @ increment pointer var
b promptLoop @ back to top
getResponse:
mov r0, STDIN @ from keyboard
add r1, fp, response @ address of response
mov r2, 1 @ one char
bl read
ldrb r3, [fp, response] @ load response
cmp r3, 'y @ was it 'y'?
bne discard @ no, discard changes
ldr r4, yesAddr @ "Changes saved."
yesLoop:
ldrb r3, [r4] @ get a char
cmp r3, NUL @ end of string?
beq endThen @ yes, end of then block
mov r0, STDOUT @ no, write to screen
mov r1, r4 @ address of current char
mov r2, 1 @ write 1 byte
bl write
add r4, r4, 1 @ increment pointer var
b yesLoop @ back to top
endThen:
b endElse @ branch over else block
discard:
ldr r4, noAddr @ "Changes discarded."
noLoop:
ldrb r3, [r4] @ get a char
cmp r3, NUL @ end of string?
beq endElse @ yes, end of if-else
mov r0, STDOUT @ no, write to screen
mov r1, r4 @ address of current char
mov r2, 1 @ write 1 byte
bl write
add r4, r4, 1 @ increment pointer var
b noLoop @ back to top
endElse:
mov r0, 0 @ return 0;
add sp, sp, local @ deallocate local var
ldr r4, [sp, 4] @ restore r4
ldr fp, [sp, 8] @ fp
ldr lr, [sp, 12] @ lr
add sp, sp, 16 @ sp
bx lr @ return
.align 2
promptAddr:
.word prompt
yesAddr:
.word yes
noAddr:
.word no
The branch out of the “then” block over the “then” block:
yesLoop:
ldrb r3, [r4] @ get a char
cmp r3, NUL @ end of string?
beq endThen @ yes, end of then block
mov r0, STDOUT @ no, write to screen
mov r1, r4 @ address of current char
mov r2, 1 @ write 1 byte
bl write
add r4, r4, 1 @ increment pointer var
b yesLoop @ back to top
endThen:
b endElse @ branch over else block
could be done more efficiently with:
yesLoop:
ldrb r3, [r4] @ get a char
cmp r3, NUL @ end of string?
beq endElse @ yes, end of if-else construct
mov r0, STDOUT @ no, write to screen
mov r1, r4 @ address of current char
mov r2, 1 @ write 1 byte
bl write
add r4, r4, 1 @ increment pointer var
b yesLoop @ back to top
But it would be very rare for this gain in efficiency to be noticeable. On the other hand, using the strict “if-then-else” structure makes the code more readable for anyone who modifies it. The trade-off here is an almost certainly unnoticeable performance gain versus a fair chance of introducing a bug into the code. (In case you have not learned this yet, it is much easier to make a coding error in code that is more difficult to read.)
The overall structure of an if-else can be seen in Listing 12.3.5 follows this general pattern. It, of course, uses more meaningful labels than what the compiler generated.
@ if-else.s
@ NOT A FUNCTION. Shows if-else structure.
@ 2017-09-29: Bob Plantz
-------
ldrb r3, [fp, #-response] @ load response
cmp r3, 'y @ was it 'y'?
bne discard @ no, discard changes
( else block )
endThen:
b endElse @ branch over else block
discard:
( then block )
endElse:
-------
if-else construct (prog asm).Subsection 12.3.2 Range Checking
Another common programming problem is to check to see if a variable is within a certain range. This requires a compound Boolean expression, as shown in the C program in Listing 12.3.6.
/* range1.c
* Checks to see if a character entered by user is a numeral.
* 2017-09-29: Bob Plantz
*/
#include <unistd.h>
int main()
{
char response; // For user's response
char *prompt = "Enter a single character: ";
char *numeral = "You entered a numeral.\n";
char *other = "You entered a non-numeric character.\n";
while (*prompt != '\0') {
write(STDOUT_FILENO, prompt, 1);
prompt++;
}
read(STDIN_FILENO, &response, 1);
if ((response <= '9') && (response >= '0')) {
while (*numeral != '\0') {
write(STDOUT_FILENO, numeral, 1);
numeral++;
}
}
else {
while (*other != '\0') {
write(STDOUT_FILENO, other, 1);
other++;
}
}
return 0;
}
if-else construct (C).We will move directly to my assembly language version of this range-checking program in Listing 12.3.7.
@ range2.s
@ Checks if user entered a numeral
@ 2017-09-29: Bob Plantz
@ Define my Raspberry Pi
.cpu cortex-a53
.fpu neon-fp-armv8
.syntax unified @ modern syntax
@ Useful source code constants
.equ STDOUT,1
.equ STDIN,0
.equ NUL,0
.equ response,-20
.equ local,8
@ Constant program data
.section .rodata
.align 2
prompt:
.asciz "Enter a single character: "
.align 2
numeral:
.asciz "You entered a numeral.\n"
.align 2
other:
.asciz "You entered a non-numeric character.\n"
@ The program
.text
.align 2
.global main
.type main, %function
main:
sub sp, sp, 16 @ space for saving regs
@ (keeping 8-byte sp align)
str r4, [sp, 4] @ save r4
str fp, [sp, 8] @ fp
str lr, [sp, 12] @ lr
add fp, sp, 12 @ set our frame pointer
sub sp, sp, local @ local variable
ldr r4, promptAddr @ prompt user
promptLoop:
ldrb r3, [r4] @ get a char
cmp r3, NUL @ end of string?
beq getResponse @ yes, get response
mov r0, STDOUT @ no, write to screen
mov r1, r4 @ address of current char
mov r2, 1 @ write 1 byte
bl write
add r4, r4, 1 @ increment pointer var
b promptLoop @ back to top
getResponse:
mov r0, STDIN @ from keyboard
add r1, fp, response @ address of response
mov r2, 1 @ one char
bl read
ldrb r3, [fp, response] @ load response
cmp r3, '9 @ check high end
bhi notNumeral @ >'9', other char
cmp r3, '0 @ check low end
blo notNumeral @ <'0', other char
ldr r4, numeralAddr @ "You entered a numeral."
numLoop:
ldrb r3, [r4] @ get a char
cmp r3, NUL @ end of string?
beq endThen @ yes, end of then block
mov r0, STDOUT @ no, write to screen
mov r1, r4 @ address of current char
mov r2, 1 @ write 1 byte
bl write
add r4, r4, 1 @ increment pointer var
b numLoop @ back to top
endThen:
b endElse @ branch over else block
notNumeral:
ldr r4, otherAddr @ "You entered some other character."
notNumLoop:
ldrb r3, [r4] @ get a char
cmp r3, NUL @ end of string?
beq endElse @ yes, end of if-else
mov r0, STDOUT @ no, write to screen
mov r1, r4 @ address of current char
mov r2, 1 @ write 1 byte
bl write
add r4, r4, 1 @ increment pointer var
b notNumLoop @ back to top
endElse:
mov r0, 0 @ return 0;
add sp, sp, local @ deallocate local var
ldr r4, [sp, 4] @ restore r4
ldr fp, [sp, 8] @ fp
ldr lr, [sp, 12] @ lr
add sp, sp, 16 @ sp
bx lr @ return
.align 2
promptAddr:
.word prompt
numeralAddr:
.word numeral
otherAddr:
.word other
When a Boolean expression is used to control the flow of a program (for example, while loop, if-else) most language employ Short Circuit Evaluation of the expression. That is, as each term is evaluated, if it is determined that the entire expression evaluates to either “true” or “false” the appropriate action is taken, without evaluating the remaining terms in the expression. We can see how this is implemented by looking at the assembly language that implements the Boolean expression,
((response <= '9') && (response >= '0'))
in Listing 12.3.6.
From Listing 12.3.7 this is the code sequence:
ldrb r3, [fp, #-response] @ load response cmp r3, #'9 @ check high end bhi notNumeral @ >'9', other char cmp r3, #'0 @ check low end blo notNumeral @ <'0', other char
If it is determined that the user's response is higher than the character ‘9’, there is no need to do further checking. The bhi notNumeral instruction “short circuits” further evaluation of this Boolean expression.