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

- 141K All Categories
- 103.8K Programming Languages
- 6.5K Assembler Developer
- 1.9K Basic
- 40K C and C++
- 2.9K C#
- 7.9K Delphi and Kylix
- 4 Haskell
- 9.7K Java
- 4.1K Pascal
- 1.3K Perl
- 2K PHP
- 551 Python
- 37 Ruby
- 4.4K VB.NET
- 1.6K VBA
- 20.9K Visual Basic
- 2.6K Game programming
- 317 Console programming
- 92 DirectX Game dev
- 1 Minecraft
- 112 Newbie Game Programmers
- 2 Oculus Rift
- 9K Applications
- 1.8K Computer Graphics
- 744 Computer Hardware
- 3.5K Database & SQL
- 535 Electronics development
- 1.6K Matlab
- 628 Sound & Music
- 258 XML Development
- 3.3K Classifieds
- 199 Co-operative Projects
- 198 For sale
- 190 FreeLance Software City
- 1.9K Jobs Available
- 604 Jobs Wanted
- 210 Wanted
- 2.9K Microsoft .NET
- 1.8K ASP.NET
- 1.1K .NET General
- 3.4K Miscellaneous
- 7 Join the Team
- 355 Comments on this site
- 70 Computer Emulators
- 2.1K General programming
- 187 New programming languages
- 629 Off topic board
- 217 Mobile & Wireless
- 89 Android
- 126 Palm Pilot
- 340 Multimedia
- 156 Demo programming
- 184 MP3 programming
- Bash scripts
- 27 Cloud Computing
- 53 FreeBSD
- 1.7K LINUX programming
- 370 MS-DOS
- Shell scripting
- 321 Windows CE & Pocket PC
- 4.1K Windows programming
- 942 Software Development
- 417 Algorithms
- 68 Object Orientation
- 92 Project Management
- 95 Quality & Testing
- 269 Security
- 7.7K WEB-Development
- 1.8K Active Server Pages
- 62 AJAX
- 5 Bootstrap Themes
- 55 CGI Development
- 28 ColdFusion
- 224 Flash development
- 1.4K HTML & WEB-Design
- 1.4K Internet Development
- 2.2K JavaScript
- 37 JQuery
- 308 WEB Servers
- 151 WEB-Services / SOAP

marcosoft
Member Posts: **4**

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]

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]

Terms of use / Privacy statement / Publisher: Lars Hagelin

Programmers Heaven articles / Programmers Heaven files / Programmers Heaven uploaded content / Programmers Heaven C Sharp ebook / Operated by CommunityHeaven

© 1997-2017 Programmersheaven.com - All rights reserved.

## Comments

1Have 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]

:

1: 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]

:

:

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

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