Problem Statement
Given two integers X and Y compute the product XY (multiplication), the quotient X=Y (integer division), and the modulus X (mod Y) (remainder).
Inputs
The integers X and Y are stored at locations 3100 and 3101, respectively.
Outputs
The product XY, the quotient X=Y, and modulus X (mod Y) are stored at locations 3102, 3103, and 3104, respectively. If X;Y inputs are invalid for X=Y and X (mod Y) (see section 5.2.5 on page 5-3) place 0 in both locations 3103 and 3104.
The program
Subroutines
Subroutines in assembly language correspond to functions in C/C++ and other computer languages: they form a group of code that is intended to be used multiple times. They perform a logical task
by operating on parameters passed to them, and at the end they return one or more results. As an example consider the simple subroutine in listing 5.1 on page 5-2 which implements the function
f n = 2n+3. The integer n is located at 3120, and the result Fn is stored at location 3121. Register R0 is used to pass parameter n to the subroutine, and R1 is used to pass the return value f n from the
subroutine to the calling program.
Execution is transfered to the subroutine using the JSR ("jump to subroutine") instruction. This instruction also saves the return address, that is the address of the instruction that follows JSR, in
register R7. See figure 5.1 on page 5-2 for the steps taken during execution of JSR. The subroutine terminates execution via the RET "return from subroutine" instruction. It simply assigns the return
value in R7 to the PC.
The program will have two subroutines: MULT for the multiplication and DIV for division and modulus.
Revision: 1.8, August 14, 2005 5-1
LAB 5 5.2. THE PROGRAM
1 LDI R0 , N ; Argument N i s now i n R0
2 JSR F ; Jump t o s u b r o u t i n e F.
3 STI R1 , FN
4 HALT
5 N .FILL 3120 ;Addr e s s where n i s l o c a t e d
6 FN .FILL 3121 ;Addr e s s where fnwi l l be s t o r e d .
7 ; S u b r o u t i n e F b e g i n s
8 F AND R1 , R1 , x0 ; Cl e a r R1
9 ADD R1 , R0 , x0 ; R1 R0
10 ADD R1 , R1 , R1 ; R1 R1 + R1
11 ADD R1 , R1 , x3 ; R1 R1 + 3 . Re s u l t i s i n R1
12 RET ; Re tu r n from s u b r o u t i n e
13 END
Listing 5.1: A subroutine for the function f (n) = 2n+3.
will proceed from there.
execution of JSR.
LC3 state right before
F Addr
JSR Addr + 1
Copy PC to R7
for the RET instruction.
JSR Addr + 1
IR to PC so execution
Copy F's address from
Step 2 Step 3
PC
R7
JSR F
IR IR
JSR F
R7
PC
JSR Addr + 1
0
JSR Addr + 1
PC
R7
JSR F
IR
Step 1
Figure 5.1: The steps taken during execution of JSR.
5.2.2 Saving and restoring registers
Make sure that at the beginning of your subroutines you save all registers that will be destroyed in
the course of the subroutine. Before returning to the calling program, restore saved registers. As an
example, listing 5.2 on page 5-3 shows how to save and restore registers R5 and R6 in a subroutine.
5.2.3 Structure of the assembly program
The general structure of the assembly program for this problem can be seen in listing 5.3 on page 5-
3.
5-2
LAB 5 5.2. THE PROGRAM
1 SUB . . . ; S u b r o u t i n e i s e n t e r e d
2 ST R5 , SaveReg5 ; Save R5
3 ST R6 , SaveReg6 ; Save R6
4 . . . ; us e R5 and R6
5 . . .
6
7 LD R5 , SaveReg5 ; Re s t o r e R5
8 LD R6 , SaveReg6 ; Re s t o r e R6
9 RET ; Back t o t h e c a l li n g program
10 SaveReg5 .FILL x0
11 SaveReg6 .FILL x0
Listing 5.2: Saving and restoring registers R5 and R6.
1 . . .
2 JSR MULT; Jump t o t h e mu l t i p l i c a t i o n s u b r o u t i n e
3 . . . ; Here p r o d u c t XY i s i n R2
4 JSR DIV ; Jump t o t h e d i v i s i o n and mod s u b r o u t i n e
5
6 HALT
7 . . .
8 . . . ; Mu l t i p l i c a t i o n s u b r o u t i n e b e g i n s
9 MULT . . . ; Save r e g i s t e r s t h a t wi l l be o v e rwri t t e n
10 . . . ; Mu l t i p l i c a t i o n Algorithm
11 . . . ; Re s t o r e s aved r e g i s t e r s
12 . . . ; R2 ha s t h e p r o d u c t .
13 RET ; Re t ur n from s u b r o u t i n e
14 ; Di v i s i o n and mod s u b r o u t i n e b e g i n s
15 DIV . . .
16 . . .
17 RET
18 END
Listing 5.3: General structure of assembly program.
5.2.4 Multiplication
Multiplication is achieved via addition:
XY = |X +X +{z: : :+X}
Ytimes
(5.1)
Listing 5.4 on page 5-4 shows the pseudo-code for the multiplication algorithm. Parameters X and
Y are passed to the multiplication subroutine MULT via registers R0 and R1. The result is in R2.
5.2.5 Division and modulus
Integer division X=Y and modulus X (mod Y) satisfy this formula:
X = X=Y
Y +X (mod Y) (5.2)
Where X=Y is the quotient and X (mod Y) is the remainder. For example, if X = 41 and Y = 7, the
equation becomes
41 = 5
7+6 (5.3)
5-3
LAB 5 5.2. THE PROGRAM
1 / / Mu l t i p l y i n g XY. Pr o d u c t i s i n v a r i a b l e prod .
2 s i g n 1 / / The s i g n of t h e p r o d u c t
3 i f X < 0 t h e n
4 X = ??X / / Conve r t X t o p o s i t i v e
5 s i g n = ??s i g n
6 i f Y < 0 t h e n
7 Y = ??Y / / Conve r t Y t o p o s i t i v e
8 s i g n = ??s i g n
9 prod 0 / / I n i t i a l i z e p r o d u c t
10 whi l e Y 6= 0 do
11 prod prod + X
12 Y Y?? 1
13 i f s i g n < 0 t h e n
14 prod ??prod / / Ad j u s t s i g n of p r o d u c t
Listing 5.4: Pseudo-code for multiplication.
Subroutine DIV will compute both the quotient and remainder. Parameter X is passed to DIV
through R0 and Y through R1. For simplicity division and modulus are defined only for X 0 and
Y > 0. Subroutine DIV should check if these conditions are satisfied. If, not it should return with
R2 = 0, indicating that the results are not valid. If they are satisfied, R2 = 1, to indicate that the
results are valid. Overflow conditions need not be checked at this time. Figure 5.2 summarizes the
input arguments and results that should be returned.
Register Input parameter Result
R0 X X=Y or 0 if invalid
R1 Y X (mod Y) or 0 if invalid
R2 1 if results valid, 0 otherwise
Figure 5.2: Input parameters and returned results for DIV.
Listing 5.5 shows the pseudo-code for the algorithm that performs integer division and modulus
functions. The quotient is computed by successively subtracting Y from X. The leftover quantity is
the remainder.
1 / / Fi n d i n g t h e q u o t i e n t X/Y and r emai n d e r X mod Y.
2 q u o t i e n t 0 / / I n i t i a l i z e q u o t i e n t
3 r emai n d e r 0 / / I n i t i a l i z e r emai n d e r ( i n c a s e i n p u t i n v a l i d )
4 v a l i d 0 / / I n i t i a l i z e v a l i d
5 i f X < 0 or Y 0 t h e n
6 e x i t
7 v a l i d = 1
8 temp X / / Holds q u a n t i t y l e f t
9 whi l e temp Y do
10 temp = temp ?? Y
11 q u o t i e n t q u o t i e n t + 1
12 r emai n d e r temp
Listing 5.5: Pseudo-code for integer division and modulus.
5-4
LAB 5 5.3. TESTING
5.3 Testing
You should first write the MULT subroutine, thoroughly test it, and then proceed to implement the
DIV subroutine. Thoroughly test DIV. Finally, test the program as a whole for various inputs.
5.4 What to turn in
A hardcopy of the assembly source code.
Electronic version of the assembly code.
For each of the (X;Y) pairs (100;17); (211;4); (11;??15); (12;0), screenshots that show the
contents of locations 3100 through 3104.
5-