1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Apr 16, 2010 #1
    1. The problem statement, all variables and given/known data

    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.

    2. Relevant 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


    3: Product is available in ACC:MPR

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

    .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
        AND R4, R1, R2
        BRZ SHIFT2
        ADD R0, R0, R3
        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


    SHIFTR1 .BLKW   1   ;Register save area
    SHIFTR2 .BLKW   1
    SHIFTR3 .BLKW   1
    SHIFTR4 .BLKW   1
    SHIFTR7 .BLKW   1
    STMASK  .FILL   x02
    SSMASK  .FILL   x01

    UNSMUL  ;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, UCOUNT

        AND R5, R1, R4
        BRZ UMST1
        ADD R3, R3, R2

        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


    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   x0008

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

    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

    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
        ADD R6, R6, #0
        BRZP    L2
        ADD R0, R0, b10
        LD  R1, OFL1
        LD  R2, OFL2
        LD  R3, OFL3
        LD  R4, OFL4
        LD  R5, OFL5
        LD  R6, OFL6
        LD  R7, OFL7

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

    Last edited: Apr 16, 2010
  2. jcsd
  3. Apr 16, 2010 #2


    Staff: Mentor

    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.
  4. Apr 16, 2010 #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?
  5. Apr 16, 2010 #4


    Staff: Mentor

    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.
    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.
  6. Apr 16, 2010 #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: Apr 16, 2010
  7. Apr 16, 2010 #6


    Staff: Mentor

    I copied a few lines of your code that show the relevant variables.
    Code (Text):

    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.
  8. Apr 16, 2010 #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.
  9. Apr 17, 2010 #8


    Staff: Mentor

    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.
  10. Apr 18, 2010 #9
    Did you ever figure it out??
  11. Apr 18, 2010 #10


    Staff: Mentor

    Did I figure what out? If you are waiting on me for an answer, I don't know what the question is.
  12. Apr 19, 2010 #11
    I wasn't talking to you n00b
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook