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

In summary, the conversation discusses the implementation and testing of two subroutines for a computer science assignment. The first subroutine, SHIFTR, performs a logical right shift on a given value in register R0. The second subroutine, UNSMUL, multiplies a pair of unsigned words and returns the double-word product. The professor has provided notes and instructions for the implementation of UNSMUL, including the use of an argument-list in memory passed to the subroutine through register R6. The conversation also mentions the use of other subroutines from a previous assignment, including OR, XOR, and OFLO.
  • #1
frankfjf
168
0

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.

Code:
.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
 
Last edited:
Physics news on Phys.org
  • #2
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.
 
  • #3
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?
 
  • #4
frankfjf said:
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.
frankfjf said:
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.
 
  • #5
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.
 
Last edited:
  • #6
I copied a few lines of your code that show the relevant variables.
Code:
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.
 
  • #7
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.
 
  • #8
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.
 
  • #9
Did you ever figure it out??
 
  • #10
Did I figure what out? If you are waiting on me for an answer, I don't know what the question is.
 
  • #11
I wasn't talking to you n00b
 

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

1. How do I perform extended unsigned multiplication in LC-3 Assembly?

To perform extended unsigned multiplication in LC-3 Assembly, you will need to use the MUL instruction. This instruction takes in two registers and multiplies their values together, storing the result in a third register. To perform extended multiplication, you will need to use two registers to represent the 16-bit value and use a third register to store the 32-bit result.

2. What is the difference between signed and unsigned multiplication in LC-3 Assembly?

Signed multiplication in LC-3 Assembly takes into account the sign bit of the operands, while unsigned multiplication does not. This means that signed multiplication can result in both positive and negative values, while unsigned multiplication can only result in positive values.

3. How do I handle overflow in extended unsigned multiplication?

In extended unsigned multiplication, overflow can occur if the result is larger than 16 bits and cannot be stored in the designated register. To handle overflow, you can use the ADD instruction to add the upper 16 bits of the result to the original 32-bit register. This will allow you to store the full 32-bit result.

4. Can extended unsigned multiplication be performed with decimal values in LC-3 Assembly?

No, extended unsigned multiplication in LC-3 Assembly can only be performed with binary values. If you need to multiply decimal values, you will first need to convert them to binary before using the MUL instruction.

5. Are there any alternative methods for performing extended unsigned multiplication in LC-3 Assembly?

Yes, there are alternative methods for performing extended unsigned multiplication in LC-3 Assembly. One method is to use the SHIFT and ADD instructions to multiply the 16-bit values, similar to how you would perform multiplication by hand. Another method is to use the MUL instruction with a combination of ADD and AND instructions to handle overflow. It is recommended to explore and experiment with different methods to find the most efficient solution for your specific task.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
2K
  • Programming and Computer Science
Replies
4
Views
4K
  • Engineering and Comp Sci Homework Help
Replies
5
Views
2K
  • Introductory Physics Homework Help
Replies
2
Views
819
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
4
Views
2K
  • Introductory Physics Homework Help
Replies
7
Views
4K
  • Introductory Physics Homework Help
Replies
9
Views
2K
Back
Top