Reference no: EM13358460

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-