Lecture 30 In-Class Worksheet
1 Learning Objectives
This worksheet is based on Patt & Patel textbook sections 5.4–5.5. After completing this
lesson, you will know how to:
• [S30-1] Use one or more ADD, AND, and NOT instructions to evaluate simple arithmetic
(addition, subtraction, multiplication by a small constant) and and logical (bit-wise
Boolean operators and shifts) expressions.
• [S30-2] Implement arithmetic comparison (equal, not equal, less than, greater than)
between two registers, and between a register and a constant.
• [S30-4] Use BR to implement if statements and loops.
2 Multiplication by Repeated Addition
A simplest way to multiply to numbers A
and B is to form the sum
S = B + B + · · · + B,
adding B a total of A times. We can describe
this procedure using a flow chart, as shown
on the right. In the flow chart, ovals rep-
resent the start and end of the procedure,
boxes represent actions that update vari-
ables or memory, and diamonds represent
branches where a decision is made about
how to proceed. The decision is based on a
test or condition that must be true or false,
giving two possible paths of execution.
1
Lecture 30 In-Class Worksheet
Q1. Fill in the missing information in the bottom box of the flowchart above.
2.1 Variable Allocation
We will write a small LC-3 program to implement the multiplication by
Var. Reg.
repeated addition procedure above. The procedure takes two input values,
A and B, and produces one output, S. There are several ways that these A R0
values can be provided to our program. One common way to do this is B R1
to place the inputs in registers. Another is to place the values at certain S R2
locations in memory. For this exercise, we will assume that the values are
given in registers and that we will return the result in a register. Specifically, we will assume
that A will be provided in register R0, B will be provided in register R1, and we will return
S in register R2.
The table above on the right lists how each variable will be stored. For a small procedure
like what we are writing, all of the values we will need can be placed in registers.
2.2 Writing the Code: Simple Blocks
Now that we know where the values we want to operate on will be, we can write the
program. Let’s implement the operations in the boxes.
Q2. Write the assembly language statements for the boxes in the flow chart above.
2.3 Writing the Code: Loops
To change the flow of execution, we will need to use a BR instruction. There are two parts
necessary to implement the diamond-shaped element of the flow chart:
• Set condition code. We need to execute an instruction that modifies the CC register
in a way that reflects the condition we want to test. Instructions that modify the C
register are ADD, AND, NOT, LD, LDI, and LDR.1
• Branch on condition. We can now use the BR instruction to transfer control based
on whether the condition holds or not.
In our case, we would like to test if A = 0, which means testing if R0 = 0. One way to do
this is to perform an operation that does not change A, but makes it the destination register
of one of the instructions that update the CC register.
1
In the second edition of the Patt & Patel textbook, LEA also modified the CC register, however, this was
changed in the third edition.
2
Lecture 30 In-Class Worksheet
Q3. Give an assembly language statement that writes the value stored in R0 to a
register, but that does not modify R0.
Next, we need to determine which of the bits n, z, and p to set in the BR instruction. Note
that we can always set more than one.
Q4. Give the values of the values of the n, z, and p bits in a branch instruction that
branches when the Z flag is set in the CC register.
Q5. What does a BR instruction where n = z = p = 1 do?
Q6. What does a BR instruction where n = z = p = 0 do?
We specify the target of the BR instruction if the branch is taken as a PC-relative value
PCoffset9. When writing the instructions, it often convenient to use a string label to
refer to the targets of BR instructions while we are writing the code. Once we’re done, we
can turn the labels into the corresponding PCoffset9 values.
2.4 Putting It All Together
Q7. Write down the complete procedure for multiplication by repeated addition in
assembly language using labels for BR instruction targets. Then translate the labels to
PCoffset9 values.
Q8. Translate your answer to Q7 into machine code in hexadecimal.
3 Other Test Conditions
More complex test conditions, such as testing for equality of the values in two registers, can
be accomplished using arithmetic operations. For example, To test if the values in R1 and
R2 are equal, we would subtract R2 from R1 (or vice versa) and test the result for zero. In
many cases, we do not need to result R1 − R2, we only want to update the CC register with
the result. However, since we have to specify a destination register, we specify a destination
register that is not used to store a useful value.
3
Lecture 30 In-Class Worksheet
Q9. Give sequence of instructions that sets the Z bit in CC if R1 − R2 is zero. Use R0
as the destination to discard the result.
We can use the n and p bits to test for inequalities as well.
Q10. Give assembly language code to test for R1 < R2, R1 > R2, R1 ≤ R2, and
R1 ≥ R2. Also give the corresponding BR instruction n, z, and p values. You may
assume that no two’s complement overflow would occur. You may use R0 to discard
the result.
