Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Trouble with Extended Multiplication in LC-3 Assembly

  1. Dec 10, 2017 #1
    1. The problem statement, all variables and given/known data


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

    2. Relevant equations


    3. 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 (Text):
        .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



        LDR    R0, R0, #0

        JSR    PRINT


        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  
        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

    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:


    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.
  2. jcsd
  3. Dec 11, 2017 #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: Dec 11, 2017
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted