Trouble with Extended Multiplication in LC-3 Assembly

In summary, the code calculates the product of two numbers by using an algorithm in the relevant equations section. First, the code sets up some registers and stores the values of the multiplier, multiplicand, and product. It then starts a loop that tests the multiplier and multiplicand against each other, and branches based on whether the multiplier and multiplicand are equal.
  • #1
Enharmonics
29
2

Homework Statement



gDaWNVB.png


So basically, I have to implement the algorithm given in the relevant equations section.

Homework Equations



Rxov2aZ.png


The Attempt at a Solution



First and foremost, my code. Some bits that weren't directly relevant to the problem I'm having were removed for readability's sake. The RightShift subroutine implements a logical shift right. Print subroutine just prints the contents of R0 onto the console in binary form.

Code:
    .ORIG    x3000

; Calculate AB = A x B
    LEA    R6, ARGS

    LD    R0, B      

    STR    R0, R6, #0    ; Store B into Multiplier address of ARGS

    JSR    PRINT    

    LD    R0, A      

    STR    R0, R6, #1    ; Store A into Multiplicand address of ARGS
  
    JSR    PRINT       

    LEA    R0, AB        ; R0 <- starting address of AB

    STR    R0, R6, #2    ; Store starting address of AB into Product word of ARGS

    JSR    XMULT

    ; DID WE LOAD THE PRODUCT PROPERLY?

    ; THIS SHOULD PRINT THE LEAST SIGNIFICANT BITS OF PRODUCT

    LDR    R0, R0, #0

    JSR    PRINT

    ; THIS SHOULD PRINT THE MOST SIGNIFICANT BITS OF PRODUCT

    LEA    R0, AB

    ADD    R0, R0, #1

    LDR    R0, R0, #0

    JSR    PRINT

; Calculate XY = X * Y    TRAP    x25
;    Test Data
A    .FILL    x0010
B    .FILL    x00AB
X    .FILL    x1234
Y    .FILL    xABCD
AB    .BLKW    2
XY    .BLKW    2
;    Argument List
ARGS    .BLKW    1    ;Multiplier   (value)
    .BLKW    1    ;Multiplicand (value)
    .BLKW    1    ;Product      (address);**********************************************************

XMULT    ;Extended Multiplication
    ;Arguments located by R6
    ;    multiplier (value)
    ;    multiplicand (value)
    ;    product (address)

    ST    R7, XMU7    ;Save Registers
    ST    R0, XMU0    ; TEMP register (for storing temp results and passing to RightShift subroutine)
    ST    R1, XMU1    ; Will store MPR (Multiplier)
    ST    R2, XMU2    ; Will store MND (Multiplicand)
    ST    R3, XMU3    ; Will store ACC (Accumulator)
    ST    R4, XMU4    ; Will serve as a COUNTER for loop
    ST    R5, XMU5    ; Will store BITMASK for testing
    ST    R6, XMU6    ; Argument list    LDR    R1, R6, #0    ; Store MPR into R1 (Multiplier is first item in the argument list pointed to by R6)
    LDR    R2, R6, #1    ; Store MND into R2 (Multiplicand is second item)

    AND    R3, R3, #0    ; ACC <- 0

    LD    R4, COUNTER    ; Set counter

    LD    R5, BITMASK    ; Set R5 to 0000 0000 0000 0001, the bitmask needed to test MPR[0]

    ; Counter and operands ready - now we can start the loop

MULOOP    ; MUltiplication LOOP
  
    AND    R0, R5, R1    ; Test MPR[0]  
    BRz    ELSE    ; Branch if MPR[0] isn't set
    ADD    R3, R3, R2    ; ACC <- ACC + MND  
 
ELSE
    AND    R0, R0, #0    ; Clear R0
    ADD    R0, R3, #0    ; R0 <- ACC
    JSR    SHIFT        ; ShiftRight(ACC)
    ADD    R3, R0, #0    ; R3 <- Right-shifted ACC
    ADD    R0, R1, #0    ; R0 <- MPR  
    JSR    SHIFT        ; ShiftRight(MPR)
    ADD    R1, R0, #0    ; R1 <- Right-shifted MPR
    ADD    R4, R4, #-1    ; Decrement Counter
    BRp    MULOOP        ; If Counter > 0, branch to beginning of loop  

MULOOPEND    ; MUltiplication LOOP ends here

; Write results to memory addresses (OUT-parameter segment)

    LDR    R0, R6, #2    ; R0 <- Product(address), least significant digit
    STR    R1, R0, #0    ; Right-shifted MPR goes in the lower address word
    STR    R3, R0, #1    ; Right-shifted ACC goes in the higher address word

      
    LD    R7, XMU7    ; Restore Registers
    LD     R0, XMU0
    LD    R1, XMU1  
    LD    R2, XMU2
    LD    R3, XMU3
    LD    R4, XMU4
    LD    R5, XMU5
    LD    R6, XMU6
    RET

XMU0    .BLKW    1
XMU1    .BLKW    1
XMU2    .BLKW    1
XMU3    .BLKW    1
XMU4    .BLKW    1
XMU5    .BLKW    1
XMU6    .BLKW    1
XMU7    .BLKW    1

; Data

COUNTER    .FILL    x0008
BITMASK    .FILL    x0001

;*********************************************************

The part that's giving me problems is in the MUltiplication LOOP (MULOOP in the code). A little perspective: I'm trying to test my code on the first bit multiplication given in the code, namely, I'm calculating

AB = A x B

where A = x0010 = b0000 0000 0001 0000
and B = x00AB = b0000 0000 1010 1011

To illustrate my problem, here's what happens when I execute the program:

dspxDci.png


Ignore the characters - those are there because the print function I used was borrowed from some other code I wrote that was supposed to print the char representations of bits.

Notice the first two bit values, 0000 0000 1010 1011 and 0000 0000 0001 0000. These correspond to the values A and B, which in decimal are 171 and 16, respectively.

The last two bit values, 0000 0000 0000 0000 and 0000 0000 0000 0000 1010, correspond to the right shifted MPR and ACC values that are supposed to represent the product of the two numbers.

Now, according to some bit multiplication calculators I've consulted, the product of x0010 and x00AB should be xAB0 = b1010 1011 0000

So basically, once the loop has fully iterated and the right-shifted ACC and MPR values are stored into their respective memory addresses, ACC contains a value that could possibly be part of the right answer (x000A), while MPR is totally empty (x0000).

For the answer to be correct as it is, MPR should contain xB000 = b1011 0000 0000 000, since that way ACC:MPR represents xAB0.

In other words, the problem I'm having is that the implementation isn't fully working. I say "isn't fully working" because I've been sitting at my PC for the past few hours using the Step Into function on my LC-3 simulator to go through the code step by step, and I can say for sure most everything in my code is working as intended.

Stepping through MULOOP one step at a time, however, reveals something strange: while the logical shift right works properly for both ACC and MPR (the values in each are divided by two, with truncation, each time), MPR gets divided all the way down to zero before the loop exits.

In fact, ACC used to get zeroed out too at first, when I had my counter set to 16 - this was because the multiplication loop is supposed to iterate N times, where N is the number of bits that make up the numbers you're multiplying, and since the LC-3 is 16-bit addressable, I thought I'd set the counter to 16 bits.

The reason I changed it to 8 is that technically x0010 and x00AB are 8 bit numbers (normally you'd represent them as x10 and xAB, respectively), so I thought maybe 16 iterations of the "multiplication loop" was too much for two 8 bit numbers, and was causing the right shifts within the loop to zero them out (due to being executed too many times).

So that's where I'm at right now. I need to either get ACC to be x00AB instead of x000A (what it is now) or get MPR to be xB000 so that ACC:MPR reads x000A B000, which would be correct for the purposes of the algorithm.

But I don't know what to do. I don't even know what's going wrong. The error must be semantic in nature, because as far as I've seen during program execution, the syntax is correct.

Any help would be appreciated.
 

Attachments

  • gDaWNVB.png
    gDaWNVB.png
    17.8 KB · Views: 1,474
  • Rxov2aZ.png
    Rxov2aZ.png
    12.9 KB · Views: 1,734
  • dspxDci.png
    dspxDci.png
    9.7 KB · Views: 683
  • Like
Likes berkeman
Physics news on Phys.org
  • #2
You are right shifting you low order results into the bit bucket.
Here's how you are using you registers in that loop:
R1: Multiplier (halved on each cycle, ends up zero)
R2: Multiplicand
R3: High order by of product.
R4: Loop counter (8,7,6,... 0)
R5: Bit mask for odd/even bit (1).

At the end, you store R1 and R3. Which is zero and the high-order byte of the product.
You are generating the low-order bits, but never saving them. The get shifted into oblivion when you right-shift R3.
 
Last edited:

Related to Trouble with Extended Multiplication in LC-3 Assembly

1. What is LC-3 assembly language?

LC-3 assembly language is a low-level programming language used for writing programs that can be executed by the LC-3 processor. It consists of a set of instructions and data registers that are used to manipulate data and control the computer's operations.

2. What is extended multiplication in LC-3 assembly?

Extended multiplication in LC-3 assembly refers to the process of multiplying two numbers that are larger than the 16-bit data size of the LC-3 processor. This requires extra steps and considerations compared to regular multiplication operations.

3. What are the challenges with extended multiplication in LC-3 assembly?

The main challenge with extended multiplication in LC-3 assembly is the limitation of the 16-bit data size. This means that the processor can only handle numbers up to 65535, and any result larger than that will cause an overflow error. Additionally, extended multiplication requires more instructions and calculations, making it a more complex operation.

4. How can I perform extended multiplication in LC-3 assembly?

To perform extended multiplication in LC-3 assembly, you will need to use a combination of instructions such as ADD, AND, and NOT, along with careful manipulation of the data registers. It is also important to handle potential overflow errors and account for the extra steps required for larger numbers.

5. Are there any tips for troubleshooting trouble with extended multiplication in LC-3 assembly?

Yes, some tips for troubleshooting trouble with extended multiplication in LC-3 assembly include carefully checking your code for any errors, using a debugger to step through your program and identify any issues, and breaking down the multiplication process into smaller, more manageable steps.

Similar threads

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