Stumped on LC-3 Assembly Assignment (Extended Unsigned Multiplication)

[frankfjf]

Homework Statement

I've already figured out the code for part 1 of the assignment. I'm stuck on part 2. Specifically, I'm not sure how one would obtain the values for the multiplier and multiplicand from R6, as the notes from the professor in the code claim, nor how to format the result in doubleword ACC:MPR.
Specifically, I'm unclear on how the whole argument list being passed to UNSMUL in R6 part works. Am I missing some code? When I step through it using the LC3 Simulator, I get nothing being passed to the registers in UNSMUL with regards to obtaining the multiplier and the multiplicand. I have the feeling I need to do something with the subroutine call, but I'm not sure what.

Problem Statement
Implement and test
1) Subroutine SHIFTR to perform a logical right shift on R0
2) Subroutine UNSMUL to multiply a pair of unsigned words and return the double-word product.

Homework Equations

The professor gives the following details/notes for the mentioned part of the assignment:

Extended Unsigned Multiplication
1. Apply the algorithm described in Note 17 on the class page.
2. Modify the implementation to take into account a carry produced at the addition step of the algorithm. If there is a carry, set the high-bit of the shifted ACC.

Under Specific Instructions for the Extended Unsigned Multiplication part, he writes:

• The UNSMUL subroutine has 3 parameters 1) the multiplier, 2) the multiplicand, and 3) the address for the double-word product. These must be prepared by the caller in an argument-list in memory. The address of the argument-list is passed to UNSMUL in R6.
• A start-up source file is provided. You will need the OR, XOR and OFLO subroutines from the previous assignment.Note 17:

General Multiplication Algorithm
================================
Obtains the double-length product of a pair of N-bit unsigned integers.

MPR : Multiplier MND : Multiplicand ACC : Accumulator
The algorithm treats ACC as a high-end extension of MPR

1: MPR := multiplier //Initialize
MND := multiplicand
ACC := 0

2: LOOP N times //Iterate

2.1: IF (low-bit of MPR = 1) //Test
2.1.1: ACC := ACC + MND //Add

2.2: SHIFT (ACC:MPR) right once //Shift

ENDLOOP

3: Product is available in ACC:MPR

The Attempt at a Solution

Here is my code thus far, including the professor's comments and my own on how it should work. As I said before, my problem seems to be figuring out how to get the multiplier and multiplicand values out of memory so I can work with them, and then generating the product in the specified format and putting it where it needs to go.

.ORIG	x3000

	LD	R4, PRINT
	LD	R5, PRNTLN

;Testing the SHIFTR subroutine
	LD	R0, X
	JSRR	R5	;Println(X)
	JSR	SHIFTR
	JSRR	R5	;Println(ShiftR(X))

;Testing the UNSMUL subroutine
	LEA	R6, ARGS
;
;Prepare the argument list for a call to UNSMUL
;
	JSR	UNSMUL	;A x B

	LD	R0, A
	JSRR	R5	;Println(A)
	LD	R0, B
	JSRR	R5	;Println(B)
	LD	R0, ABHI
	JSRR	R4	;Print(HighWord A x B)
	LD	R0, ABLO
	JSRR	R5	;Println(LowWord A x B)

	TRAP	x25

ARGS	.BLKW	3	;Argument-list for UNSMUL

X	.FILL	xABCD

A	.FILL	20
B	.FILL	10
ABLO	.BLKW	1	;Low-word of A x B
ABHI	.BLKW	1	;High-word of A x B

PRINT	.FILL	x5000
PRNTLN	.FILL	x5005

SHIFTR	;Perform a Shift-Right on R0

	ST	R1, SHIFTR1
	ST	R2, SHIFTR2
	ST	R3, SHIFTR3
	ST	R4, SHIFTR4
	ST	R7, SHIFTR7
	
	AND	R1, R1, #0	;Clearing R1 for the shifted result.
	ADD	R1, R0, R1	;Placing contents of R0 into R1.
	AND	R0, R0, #0	;Clearing R0 for containing shifted result later.
	LD	R2, STMASK	;Setting Test Mask (STMASK) and Set Mask (SSMASK), respectively.
	LD	R3, SSMASK
	
SHIFT1
	AND	R4, R1, R2
	BRZ	SHIFT2
	ADD	R0, R0, R3
SHIFT2
	ADD 	R2, R2, R2
	ADD 	R3, R3, R3
	BRNP	SHIFT1
	
	LD	R1, SHIFTR1
	LD	R2, SHIFTR2
	LD	R3, SHIFTR3
	LD	R4, SHIFTR4
	LD	R7, SHIFTR7

	RET

SHIFTR1	.BLKW	1	;Register save area
SHIFTR2	.BLKW	1
SHIFTR3	.BLKW	1
SHIFTR4	.BLKW	1
SHIFTR7	.BLKW	1
STMASK	.FILL	x02
SSMASK	.FILL	x01UNSMUL	;Unsigned Multiplication
	;Argument-list in memory located by R6
	; R6[0] multiplier value
	; R6[1] multiplicand value
	; R6[2] product address

	ST	R1, UMUL1
	ST	R2, UMUL2
	ST	R3, UMUL3
	ST	R4, UMUL4
	ST	R5, UMUL5
	ST	R6, UMUL6
	ST	R7, UMUL7

	LDR	R1, R6, #0	;R1 = MPR
	ADD	R6, R6, #1
	LDR	R2, R6, #0	;R2 = MND	
	AND	R3, R3, #0	;R3 = ACC
	LD	R4, UTMASK
	LD	R6, UCOUNTUMLOOP
	AND	R5, R1, R4
	BRZ	UMST1
	ADD	R3, R3, R2

UMST1
	ADD	R0, R3, #0
	JSR	SHIFTR
	ADD	R3, R0, #0
	ADD	R0, R1, #0
	JSR	SHIFTR
	ADD	R1, R0, #0
	ADD	R6, R6, #-1
	BRNP	UMLOOP
		
	LD	R1, UMUL1
	LD	R2, UMUL2
	LD	R3, UMUL3
	LD	R4, UMUL4
	LD	R5, UMUL5
	LD	R6, UMUL6
	LD	R7, UMUL7

	RET

UMUL1	.BLKW	1	;Register save area
UMUL2	.BLKW	1
UMUL3	.BLKW	1
UMUL4	.BLKW	1
UMUL5	.BLKW	1
UMUL6	.BLKW	1
UMUL7	.BLKW	1
UHOLD	.BLKW	1
UTMASK	.FILL	x0001
UCOUNT	.FILL	x0008OR	;R0 = R1 or R2	
	ST	R7, OR7
	ST	R4, OR4
	ST	R3, OR3

	NOT	R3, R1
	NOT	R4, R2
	AND	R0, R3, R4
	NOT	R0, R0

	LD	R3, OR3
	LD	R4, OR4
	LD	R7, OR7
	RET

OR3	.BLKW	1
OR4	.BLKW	1
OR7	.BLKW	1

XOR	;R0 = R1 xor R2
	ST	R7, XOR7
	ST	R4, XOR4
	ST	R3, XOR3
	ST	R2, XOR2
	ST	R1, XOR1

	NOT	R3, R1
	NOT	R4, R2
	AND	R1, R1, R4
	AND	R2, R2, R3
	JSR	OR

	LD	R1, XOR1
	LD	R2, XOR2
	LD	R3, XOR3
	LD	R4, XOR4
	LD	R7, XOR7
	RET

XOR1	.BLKW	1
XOR2	.BLKW	1
XOR3	.BLKW	1
XOR4	.BLKW	1
XOR7	.BLKW	1

OFLO	;R0 = 0000 0000 0000 00vc
	; c = Carry(R1 + R2)
	; v = Overflow(R1 + R2)
	ST	R7, OFL7
	ST	R6, OFL6
	ST	R5, OFL5
	ST	R4, OFL4
	ST	R3, OFL3
	ST	R2, OFL2
	ST	R1, OFL1

	ADD	R3, R1, R2	; R3 = a + b
	AND	R4, R1, R2	; R4 = a and b
	JSR	XOR
	ADD	R5, R0, #0	; R5 = a xor b

	ADD	R2, R3, #0
	JSR	XOR
	NOT	R2, R5
	AND	R6, R2, R0;	; R6 = overflow

	NOT	R3, R3
	AND	R2, R3, R5
	ADD	R1, R4, #0
	JSR	OR
	ADD	R5, R0, #0	; R5 = carry

	AND	R0, R0, #0
	ADD	R5, R5, #0
	BRZP	L1
	ADD	R0, R0, #1
L1
	ADD	R6, R6, #0
	BRZP	L2
	ADD	R0, R0, b10
L2
	LD	R1, OFL1
	LD	R2, OFL2
	LD	R3, OFL3
	LD	R4, OFL4
	LD	R5, OFL5
	LD	R6, OFL6
	LD	R7, OFL7
	RET

OFL1	.BLKW	1
OFL2	.BLKW	1
OFL3	.BLKW	1
OFL4	.BLKW	1
OFL5	.BLKW	1
OFL6	.BLKW	1
OFL7	.BLKW	1	.END

 

[Mark44]

The argument list isn't being passed in R6 - the address of the argument list is passed in R6. You need to dereference this address to get at the items in the argument list.

; R6[0] multiplier value
; R6[1] multiplicand value
; R6[2] product address

For example, if the value in R6 happens to be 1000 and all three numbers happen to be 4 bytes, then multiplier_value is in locations 1000 through 1003, multiplicand_value is in locations 1004 through 1007, and product_address is in locations 1008 through 1011.

I don't know LS-3 assembly or the architecture it runs on, so I can't help you much with syntax issues.

Hope this helps.

 

[frankfjf]

I see what you mean there, but the problem is that the argument list seems to be empty by default, only having 3 "blocks of words" set aside for it. I'm not sure if the professor wants me to edit that and come up with the argument list or to have something fill it in through the program itself (Which seems to be the case, since A and B contain two values to be multiplied together already.).

The problem is that if it's the latter, I'm uncertain how one would populate the argument list in that way, at least in terms of the last argument (The product address), since the product itself doesn't exist yet until the subroutine does its thing, presumably.

And then of course, how do I format the result of UNSMUL to come back as a doubleword?

 

[Mark44]

I see what you mean there, but the problem is that the argument list seems to be empty by default, only having 3 "blocks of words" set aside for it. I'm not sure if the professor wants me to edit that and come up with the argument list or to have something fill it in through the program itself (Which seems to be the case, since A and B contain two values to be multiplied together already.).

The problem is that if it's the latter, I'm uncertain how one would populate the argument list in that way, at least in terms of the last argument (The product address), since the product itself doesn't exist yet until the subroutine does its thing, presumably.

OK, here's the arrangement:
addr: A
addr + 2: B
addr + 4: address of product

R6: addr

In the third element of the array, there needs to be the address of a DWORD block of memory. A DWORD is the right size if the multiplier and multiplicant are WORD-sized (which I'm assuming is 2 bytes. If for some reason a WORD is larger, then adjust the offsets above accordingly.

Your program probably has a data section for storage of local variables. When you allocate storage for the two numbers being multiplied, be sure to set aside some storage for a DWORD. You can initialize it to 0 or leave it uninitialized. It doesn't matter, since your UNSMUL routine will overwrite that storage.

The way this seems to be working is that when you call UNSMUL, the R6 register is set to addr, the address of the argument list. The first two items on the list are the two numbers being multiplied, and the third item is the address of a DWORD into which the routine puts its answer.

And then of course, how do I format the result of UNSMUL to come back as a doubleword?

I don't think you need to worry about it. The answer is stored in a DWORD so that's the answer. Again, I don't know what the architecture is, and particularly if numbers are stored in "big-endian" or "little-endian" format. If you don't know those terms, you can google them.

When you get your routine working, test it with some easy numbers, such as 0x100 and 0x200, or however your system recognizes hex numbers. The answer should be 0x20000.

 

[frankfjf]

That makes a lot of sense. But then, how would I tell the computer to store each item in a different location set aside in a different block of memory?

Or in other words, how do I say "Put this in the first block in ARGS, put this in the second block in ARGS, and put this in the third block in ARGS"?

UPDATE: Actually, nevermind on the question. I figured it out on my own. My only problem now is how to have the third merely contain the address of a doubleword that will contain the answer.

 

[Mark44]

I copied a few lines of your code that show the relevant variables.

ARGS	.BLKW	3	;Argument-list for UNSMUL

X	.FILL	xABCD

A	.FILL	20
B	.FILL	10
ABLO	.BLKW	1	;Low-word of A x B
ABHI	.BLKW	1	;High-word of A x B

I'm guessing that ARGS .BLKW 3 means allocate a block of 3 words for ARGS, and that A .FILL 20 means allocate a word (?) for A and fill it with the value 20.

If that's anywhere close, you need to load a register with A, then store it at location ARGS, load a register (can be the same register) with B, then store it at location ARGS + 2. Finally, load the address of ABLO (using LEA) into a register, and store it at location ARGS + 4, and then you're ready to call UNSMUL.

If all goes well, ABLO should have 0 in it and ABHI should have 2 in it, based on what you show for A and B.

If all doesn't go well, some things to try are
Store A at location ARGS + 1 and store B at loc. ARGS + 2. In the previous paragraph I'm assuming that addressing is byte-oriented. If it's word-oriented, that's what this is taking care of.
Load the address of ABHI in the last location, instead of ABLO. Whatever, you want to have 2 end up in ABHI and 0 in ABLO.

 

[frankfjf]

UMSMUL ends up with the high word in R1 and the low word in R0. If I just tell UMSMUL to store the value of R1 into ABHI and the value of R0 into ABLO, this produces a doubleword product based on the formatting at the end. But then, what is the point of the third memory location in ARGS if I can just store each word directly into ABHI and ABLO? The assignment asks for a third parameter but it doesn't seem that one is required.

 

[Mark44]

Good question. Did you write all the code, including the code for UNSMUL? If so, then your routine doesn't quite meet the specification that it return the dword product in the location pointed to by the third mem. location in ARGS. If you didn't write the code for UNSMUL, then there is a disconnect between what the routine is advertised to do vs. what it actually does.

I sure hope you have some sort of debugger to use, something that allows you to single-step through the program and see what's in the registers and memory. Sounds like you do, which makes things a lot easier.

 

[c4t1337]

Did you ever figure it out??

 

[Mark44]

Did I figure what out? If you are waiting on me for an answer, I don't know what the question is.

 

[c4t1337]

I wasn't talking to you n00b