Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

help creating a logical right shift

I'm reading a book that uses the little computer 3 comp.
This ISA has very limited instructions (16).
ADD AND BR JMP JSR JSRR LD LDI LDR LEA NOT RET RTI ST STI STR TRAP

The problem is that I need to create a logical right shift using only this instructions. I know this is easily accomplish using division, but this processor has no division instruction and its not allowed.

Can someone please help implement this algorithm.

clear R1
for (i=1; i<16; i++)
if (R0[i])
set R1[i-1]

Comments

  • rondezvuerondezvue Member Posts: 1
    Hi there,

    Have you found the solution yet?
    I am also lookin for the logical right shift in LC3.

    Rgds,



    : I'm reading a book that uses the little computer 3 comp.
    : This ISA has very limited instructions (16).
    : ADD AND BR JMP JSR JSRR LD LDI LDR LEA NOT RET RTI ST STI STR TRAP
    :
    : The problem is that I need to create a logical right shift using only this instructions. I know this is easily accomplish using division, but this processor has no division instruction and its not allowed.
    :
    : Can someone please help implement this algorithm.
    :
    : clear R1
    : for (i=1; i<16; i++)
    : if (R0[i])
    : set R1[i-1]
    :


  • JojooJojoo Member Posts: 1
    Hi there, I am also looking for the solution for shift right with lc3. any tips please.

    : I'm reading a book that uses the little computer 3 comp.
    : This ISA has very limited instructions (16).
    : ADD AND BR JMP JSR JSRR LD LDI LDR LEA NOT RET RTI ST STI STR TRAP
    :
    : The problem is that I need to create a logical right shift using only this instructions. I know this is easily accomplish using division, but this processor has no division instruction and its not allowed.
    :
    : Can someone please help implement this algorithm.
    :
    : clear R1
    : for (i=1; i<16; i++)
    : if (R0[i])
    : set R1[i-1]
    :
    :

  • marcosoftmarcosoft Member Posts: 4
    Do u have two dual lnb (with no built in swith) for dish network that u might not need?


    U can't do div, unless U can figure out the right shift. That's life in the lc3...

    Don't ask me to explain you the code, unless you have two dual lnb's for me.. Good luck!

    ;

    ;Class Section Time: 12:30PM - 1:45PM M,W Section 1

    ;

    ;Assignment 5: Multiplication & Division

    ;

    ;Compute the product of unsigned untegers


    .ORIG x3000
    LEA R6, MULARGS
    JSR MUL
    LDR R2, R6, #1
    LEA R6, DIVARGS
    STR R2, R6, #0 ;Store multiplier as the divisor
    STR R0, R6, #1 ;Store the product as the dividend
    STR R1, R6, #2 ; ( may be double length)
    JSR DIV
    ST R0, QUOTNT
    ST R1, REMNDR
    ;

    TRAP x25 ;Halt

    ;Data Area

    MULARGS .FILL #83 ;Multiplicand
    .FILL #20 ;Multiplier
    DIVARGS .BLKW 1 ;Divisor
    PRODUCT .BLKW 2 ;Dividend / Product
    QUOTNT .BLKW 1 ;Quotient
    REMNDR .BLKW 1 ;Remainder
    ;***************************************************
    ;Subroutine to perform a Logical Shift Right
    ;Parameter is passed in R0. Result is returned in R0
    ;***************************************************
    RSH ST R7, RSH_7
    ST R4, RSH_4
    ST R3, RSH_3
    ST R2, RSH_2
    ST R1, RSH_1

    ADD R3, R0, #0 ;Swap contents of R0 to R3
    AND R0, R0, #0 ;Clear R0, this register will have the final result
    ADD R1, R0, #1 ;R1 = 1 (0000 0000 0000 0001)
    ADD R2, R0, #2 ;R2 = 2 (0000 0000 0000 0010)

    RSHLOOP AND R4, R3, R2
    BRZ RSHSKIP
    ADD R0, R0, R1
    RSHSKIP ADD R1, R1, R1
    ADD R2, R2, R2
    BRNP RSHLOOP

    LD R1, RSH_1
    LD R2, RSH_2
    LD R3, RSH_3
    LD R4, RSH_4
    LD R7, RSH_7
    RET
    ;
    RSH_1 .BLKW 1
    RSH_2 .BLKW 1
    RSH_3 .BLKW 1
    RSH_4 .BLKW 1
    RSH_7 .BLKW 1
    ;***********************************************************
    ;Subroutine to perform integer division of unsigned integers
    ;R6 locates the divisor and doubleword dividend in memory.
    ;On return R1 stores the remainder, R0 stores the quotient
    ;***********************************************************
    DIV ST R7, DIV_7 ;The idea is to implement this algorithm
    ST R6, DIV_6 ; DVR = divisor, ACC:QUO = dividend (double word), n = number of bits of divisor (16 bits on LC3)
    ST R5, DIV_5 ; while (n) {
    ST R4, DIV_4 ; shift (ACC:QUO) //left once
    ST R3, DIV_3 ; if (DVR <= ACC) {
    LDR R5, R6, #0 ;R5=DVR ; ACC = ACC - DVR
    ADD R6, R6, #1 ; SET low bit of QUO
    LDR R3, R6, #0 ;R3=QUO ; }
    ADD R6, R6, #1 ; n--
    LDR R4, R6, #0 ;R4=ACC ; }
    AND R6, R6, #0
    LD R6, COUNT_D ;R6 set to N bits of DVR (16), this will be the counter.
    LD R7, DIV_M ;This is use to see if high bit of QUO=1, if so the bit gets carry over to ACC
    LOOP_D AND R2, R3, R7
    BRn SKIP_D
    ADD R4, R4, R4 ;Shift (ACC:QUO) left once. This section gets executed if QUO high bit is not equal to 1
    ADD R3, R3, R3
    BRnzp SKIP_D2
    SKIP_D ADD R4, R4, R4 ;Shift (ACC:QUO) left once. This section gets executed if QUO high bit = 1
    ADD R3, R3, R3 ;If QUO high bit=1, the 1 gets carry over to ACC first bit place.
    ADD R4, R4, #1
    SKIP_D2 NOT R2, R5
    ADD R2, R2, #1 ;if (DVR <= ACC)
    ADD R1, R2, R4
    BRn SKIP_D3
    ADD R4, R4, R2 ;ACC=ACC - DVR
    AND R2, R2, #0 ;This section sets low bit of QUO to 1 by calling OR Sub
    ADD R2, R2, #1
    ADD R1, R3, #0
    ST R7, TEMP_D
    JSR OR
    LD R7, TEMP_D
    ADD R3, R0, #0
    SKIP_D3 ADD R6, R6, #-1
    BRnp LOOP_D
    ADD R0, R3, #0 ;Stores quotient in R0
    ADD R1, R4, #0 ;Stores remainder in R1

    LD R3, DIV_3
    LD R4, DIV_4
    LD R5, DIV_5
    LD R6, DIV_6
    LD R7, DIV_7
    RET
    ;Register Save Area
    DIV_3 .BLKW 1
    DIV_4 .BLKW 1
    DIV_5 .BLKW 1
    DIV_6 .BLKW 1
    DIV_7 .BLKW 1
    DIV_M .FILL x8000
    COUNT_D .FILL x0010
    TEMP_D .BLKW 1
    ;**************************************************
    ;Subroutine to multiply a pair of unsigned integers
    ;Parameter R6 points to multiplier and multiplicand
    ; stored in contiguous memory words
    ;Doubleword product returned in R1:R0
    ;**************************************************
    MUL ST R7, MUL_7 ;The idea is to implement this algorithms
    ST R6, MUL_6 ;n = number of bits of MPR (16 bits on LC3)
    ST R5, MUL_5 ;while (n) {
    ST R4, MUL_4 ; if (low-bit of MPR=1)
    ST R3, MUL_3 ; ACC = ACC + MND
    ST R2, MUL_2 ; SHIFT (ACC:MPR) right once
    ; n-- } Result is store in ACC:MPR
    LDR R2, R6, #0 ;R2=MPR
    ADD R6, R6, #1
    LDR R3, R6, #0 ;R3=MND
    AND R1, R1, #0 ;R1=ACC
    LD R6, COUNT_M ;R6=Counter for loop base on number of bits of MPR (16 bits on LC3)
    LD R4, MASK_M ;R4=x0001 Use to test if low bit of MPR=1

    LOOP_M AND R5, R2, R4 ; if (low-bit of MPR=1)
    BRz SKIP_M
    ADD R1, R1, R3 ; then ACC = ACC + MND
    SKIP_M AND R5, R1, R4 ;Checks if low-bit of ACC=1
    BRnz SKIP_M2
    ADD R0, R2, #0
    JSR RSH
    ADD R2, R0, #0
    ST R1, SAVE_M
    LD R1, MASK_M2 ;x8000
    JSR OR
    ADD R2, R0, #0
    LD R1, SAVE_M
    ADD R0, R1, #0
    JSR RSH
    ADD R1, R0, #0
    BRnzp SKIP_M3
    SKIP_M2 ADD R0, R2, #0
    JSR RSH
    ADD R2, R0, #0
    ADD R0, R1, #0
    JSR RSH
    ADD R1, R0, #0
    SKIP_M3 ADD R6, R6, #-1
    BRnp LOOP_M
    ADD R0, R2, #0

    LD R2, MUL_2
    LD R3, MUL_3
    LD R4, MUL_4
    LD R5, MUL_5
    LD R6, MUL_6
    LD R7, MUL_7
    RET
    MASK_M2 .FILL x8000
    MASK_M .FILL x0001
    COUNT_M .FILL x0010
    SAVE_M .BLKW 1
    MUL_2 .BLKW 1
    MUL_3 .BLKW 1
    MUL_4 .BLKW 1
    MUL_5 .BLKW 1
    MUL_6 .BLKW 1
    MUL_7 .BLKW 1
    ;************************************
    ;Subroutine to compute Inclusive-OR *
    ;Parameters in: R1, R2 out: R0 *
    ;************************************
    OR ST R7, OR_7
    ST R2, OR_2
    ST R1, OR_1

    NOT R1, R1 ;Formula implemeted for OR is as follows:
    NOT R2, R2 ;NOT(NOT(a) AND NOT(b)) where a=R1 and b=R2
    AND R0, R2, R1
    NOT R0, R0

    LD R1, OR_1
    LD R2, OR_2
    LD R7, OR_7
    RET
    ;
    ;Register Save Area
    OR_1 .BLKW 1
    OR_2 .BLKW 1
    OR_7 .BLKW 1
    ;***********************************
    ;Subroutine to compute Exclusive-OR*
    ;Parameters in: R1, R2 out: R0 *
    ;***********************************
    XOR ST R7, XOR_7
    ST R2, XOR_2
    ST R1, XOR_1

    ADD R0, R2, #0 ;R0 <- R2, R2=b R1=a
    NOT R2, R2 ;This method is used to save
    AND R2, R2, R1 ;the contents of R2 which will be use in
    NOT R1, R1 ;the following formula
    AND R1, R1, R0 ;(a AND NOT(b)) OR (NOT(a) AND b)
    JSR OR

    LD R7, XOR_7
    LD R2, XOR_2
    LD R1, XOR_1
    RET
    ;
    ;Register Save Area
    XOR_7 .FILL 0
    XOR_2 .FILL 0
    XOR_1 .FILL 0

    ;******************************************
    ;Subroutine to check for unsigned overflow*
    ;Parameters in: R1, R2 out: R0 *
    ;******************************************
    CARRY ST R7, CARRY_7
    ST R4, CARRY_4
    ST R2, CARRY_2
    ST R1, CARRY_1

    ADD R4, R1, R2 ;R4 is used to store the sum a+b, where a=R1, and b=R2
    NOT R4, R4 ;Formula implemeted for unsigned overflow is as follows:
    JSR XOR ;s = a+b
    AND R4, R0, R4 ;carry = high-bit( (a AND b) OR ((a XOR b) AND NOT(s) )
    AND R1, R1, R2
    ADD R2, R4, #0
    JSR OR
    LD R4, CHECK
    AND R0, R0, R4

    LD R7, CARRY_7
    LD R4, CARRY_4
    LD R2, CARRY_2
    LD R1, CARRY_1
    RET
    ;
    ;Register Save Area
    CARRY_7 .FILL 0
    CARRY_4 .FILL 0
    CARRY_2 .FILL 0
    CARRY_1 .FILL 0
    CHECK .FILL x8000 ;This is used to isolate the high-bit
    ;****************************************************************************************************************************************************
    .END

  • marcosoftmarcosoft Member Posts: 4
    Do u have two dual lnb (with no built in swith) for dish network that u might not need?


    U can't do div, unless U can figure out the right shift. That's life in the lc3...

    Don't ask me to explain you the code, unless you have two dual lnb's for me.. Good luck!

    ;

    ;Class Section Time: 12:30PM - 1:45PM M,W Section 1

    ;

    ;Assignment 5: Multiplication & Division

    ;

    ;Compute the product of unsigned untegers


    .ORIG x3000
    LEA R6, MULARGS
    JSR MUL
    LDR R2, R6, #1
    LEA R6, DIVARGS
    STR R2, R6, #0 ;Store multiplier as the divisor
    STR R0, R6, #1 ;Store the product as the dividend
    STR R1, R6, #2 ; ( may be double length)
    JSR DIV
    ST R0, QUOTNT
    ST R1, REMNDR
    ;

    TRAP x25 ;Halt

    ;Data Area

    MULARGS .FILL #83 ;Multiplicand
    .FILL #20 ;Multiplier
    DIVARGS .BLKW 1 ;Divisor
    PRODUCT .BLKW 2 ;Dividend / Product
    QUOTNT .BLKW 1 ;Quotient
    REMNDR .BLKW 1 ;Remainder
    ;***************************************************
    ;Subroutine to perform a Logical Shift Right
    ;Parameter is passed in R0. Result is returned in R0
    ;***************************************************
    RSH ST R7, RSH_7
    ST R4, RSH_4
    ST R3, RSH_3
    ST R2, RSH_2
    ST R1, RSH_1

    ADD R3, R0, #0 ;Swap contents of R0 to R3
    AND R0, R0, #0 ;Clear R0, this register will have the final result
    ADD R1, R0, #1 ;R1 = 1 (0000 0000 0000 0001)
    ADD R2, R0, #2 ;R2 = 2 (0000 0000 0000 0010)

    RSHLOOP AND R4, R3, R2
    BRZ RSHSKIP
    ADD R0, R0, R1
    RSHSKIP ADD R1, R1, R1
    ADD R2, R2, R2
    BRNP RSHLOOP

    LD R1, RSH_1
    LD R2, RSH_2
    LD R3, RSH_3
    LD R4, RSH_4
    LD R7, RSH_7
    RET
    ;
    RSH_1 .BLKW 1
    RSH_2 .BLKW 1
    RSH_3 .BLKW 1
    RSH_4 .BLKW 1
    RSH_7 .BLKW 1
    ;***********************************************************
    ;Subroutine to perform integer division of unsigned integers
    ;R6 locates the divisor and doubleword dividend in memory.
    ;On return R1 stores the remainder, R0 stores the quotient
    ;***********************************************************
    DIV ST R7, DIV_7 ;The idea is to implement this algorithm
    ST R6, DIV_6 ; DVR = divisor, ACC:QUO = dividend (double word), n = number of bits of divisor (16 bits on LC3)
    ST R5, DIV_5 ; while (n) {
    ST R4, DIV_4 ; shift (ACC:QUO) //left once
    ST R3, DIV_3 ; if (DVR <= ACC) {
    LDR R5, R6, #0 ;R5=DVR ; ACC = ACC - DVR
    ADD R6, R6, #1 ; SET low bit of QUO
    LDR R3, R6, #0 ;R3=QUO ; }
    ADD R6, R6, #1 ; n--
    LDR R4, R6, #0 ;R4=ACC ; }
    AND R6, R6, #0
    LD R6, COUNT_D ;R6 set to N bits of DVR (16), this will be the counter.
    LD R7, DIV_M ;This is use to see if high bit of QUO=1, if so the bit gets carry over to ACC
    LOOP_D AND R2, R3, R7
    BRn SKIP_D
    ADD R4, R4, R4 ;Shift (ACC:QUO) left once. This section gets executed if QUO high bit is not equal to 1
    ADD R3, R3, R3
    BRnzp SKIP_D2
    SKIP_D ADD R4, R4, R4 ;Shift (ACC:QUO) left once. This section gets executed if QUO high bit = 1
    ADD R3, R3, R3 ;If QUO high bit=1, the 1 gets carry over to ACC first bit place.
    ADD R4, R4, #1
    SKIP_D2 NOT R2, R5
    ADD R2, R2, #1 ;if (DVR <= ACC)
    ADD R1, R2, R4
    BRn SKIP_D3
    ADD R4, R4, R2 ;ACC=ACC - DVR
    AND R2, R2, #0 ;This section sets low bit of QUO to 1 by calling OR Sub
    ADD R2, R2, #1
    ADD R1, R3, #0
    ST R7, TEMP_D
    JSR OR
    LD R7, TEMP_D
    ADD R3, R0, #0
    SKIP_D3 ADD R6, R6, #-1
    BRnp LOOP_D
    ADD R0, R3, #0 ;Stores quotient in R0
    ADD R1, R4, #0 ;Stores remainder in R1

    LD R3, DIV_3
    LD R4, DIV_4
    LD R5, DIV_5
    LD R6, DIV_6
    LD R7, DIV_7
    RET
    ;Register Save Area
    DIV_3 .BLKW 1
    DIV_4 .BLKW 1
    DIV_5 .BLKW 1
    DIV_6 .BLKW 1
    DIV_7 .BLKW 1
    DIV_M .FILL x8000
    COUNT_D .FILL x0010
    TEMP_D .BLKW 1
    ;**************************************************
    ;Subroutine to multiply a pair of unsigned integers
    ;Parameter R6 points to multiplier and multiplicand
    ; stored in contiguous memory words
    ;Doubleword product returned in R1:R0
    ;**************************************************
    MUL ST R7, MUL_7 ;The idea is to implement this algorithms
    ST R6, MUL_6 ;n = number of bits of MPR (16 bits on LC3)
    ST R5, MUL_5 ;while (n) {
    ST R4, MUL_4 ; if (low-bit of MPR=1)
    ST R3, MUL_3 ; ACC = ACC + MND
    ST R2, MUL_2 ; SHIFT (ACC:MPR) right once
    ; n-- } Result is store in ACC:MPR
    LDR R2, R6, #0 ;R2=MPR
    ADD R6, R6, #1
    LDR R3, R6, #0 ;R3=MND
    AND R1, R1, #0 ;R1=ACC
    LD R6, COUNT_M ;R6=Counter for loop base on number of bits of MPR (16 bits on LC3)
    LD R4, MASK_M ;R4=x0001 Use to test if low bit of MPR=1

    LOOP_M AND R5, R2, R4 ; if (low-bit of MPR=1)
    BRz SKIP_M
    ADD R1, R1, R3 ; then ACC = ACC + MND
    SKIP_M AND R5, R1, R4 ;Checks if low-bit of ACC=1
    BRnz SKIP_M2
    ADD R0, R2, #0
    JSR RSH
    ADD R2, R0, #0
    ST R1, SAVE_M
    LD R1, MASK_M2 ;x8000
    JSR OR
    ADD R2, R0, #0
    LD R1, SAVE_M
    ADD R0, R1, #0
    JSR RSH
    ADD R1, R0, #0
    BRnzp SKIP_M3
    SKIP_M2 ADD R0, R2, #0
    JSR RSH
    ADD R2, R0, #0
    ADD R0, R1, #0
    JSR RSH
    ADD R1, R0, #0
    SKIP_M3 ADD R6, R6, #-1
    BRnp LOOP_M
    ADD R0, R2, #0

    LD R2, MUL_2
    LD R3, MUL_3
    LD R4, MUL_4
    LD R5, MUL_5
    LD R6, MUL_6
    LD R7, MUL_7
    RET
    MASK_M2 .FILL x8000
    MASK_M .FILL x0001
    COUNT_M .FILL x0010
    SAVE_M .BLKW 1
    MUL_2 .BLKW 1
    MUL_3 .BLKW 1
    MUL_4 .BLKW 1
    MUL_5 .BLKW 1
    MUL_6 .BLKW 1
    MUL_7 .BLKW 1
    ;************************************
    ;Subroutine to compute Inclusive-OR *
    ;Parameters in: R1, R2 out: R0 *
    ;************************************
    OR ST R7, OR_7
    ST R2, OR_2
    ST R1, OR_1

    NOT R1, R1 ;Formula implemeted for OR is as follows:
    NOT R2, R2 ;NOT(NOT(a) AND NOT(b)) where a=R1 and b=R2
    AND R0, R2, R1
    NOT R0, R0

    LD R1, OR_1
    LD R2, OR_2
    LD R7, OR_7
    RET
    ;
    ;Register Save Area
    OR_1 .BLKW 1
    OR_2 .BLKW 1
    OR_7 .BLKW 1
    ;***********************************
    ;Subroutine to compute Exclusive-OR*
    ;Parameters in: R1, R2 out: R0 *
    ;***********************************
    XOR ST R7, XOR_7
    ST R2, XOR_2
    ST R1, XOR_1

    ADD R0, R2, #0 ;R0 <- R2, R2=b R1=a
    NOT R2, R2 ;This method is used to save
    AND R2, R2, R1 ;the contents of R2 which will be use in
    NOT R1, R1 ;the following formula
    AND R1, R1, R0 ;(a AND NOT(b)) OR (NOT(a) AND b)
    JSR OR

    LD R7, XOR_7
    LD R2, XOR_2
    LD R1, XOR_1
    RET
    ;
    ;Register Save Area
    XOR_7 .FILL 0
    XOR_2 .FILL 0
    XOR_1 .FILL 0

    ;******************************************
    ;Subroutine to check for unsigned overflow*
    ;Parameters in: R1, R2 out: R0 *
    ;******************************************
    CARRY ST R7, CARRY_7
    ST R4, CARRY_4
    ST R2, CARRY_2
    ST R1, CARRY_1

    ADD R4, R1, R2 ;R4 is used to store the sum a+b, where a=R1, and b=R2
    NOT R4, R4 ;Formula implemeted for unsigned overflow is as follows:
    JSR XOR ;s = a+b
    AND R4, R0, R4 ;carry = high-bit( (a AND b) OR ((a XOR b) AND NOT(s) )
    AND R1, R1, R2
    ADD R2, R4, #0
    JSR OR
    LD R4, CHECK
    AND R0, R0, R4

    LD R7, CARRY_7
    LD R4, CARRY_4
    LD R2, CARRY_2
    LD R1, CARRY_1
    RET
    ;
    ;Register Save Area
    CARRY_7 .FILL 0
    CARRY_4 .FILL 0
    CARRY_2 .FILL 0
    CARRY_1 .FILL 0
    CHECK .FILL x8000 ;This is used to isolate the high-bit
    ;****************************************************************************************************************************************************
    .END

Sign In or Register to comment.