Langton's ant: Difference between revisions

=={{header|LC-3}}==

<lang LC-3>

.orig x3000

ld r1, ASCIIDIFF1

; user input for grid size

lea r0, STGRIDSIZE

puts

in

add r0, r0, r1

add r0, r0, #-1

brz SELECTED100

ld r0, GRID300

st r0, GRIDSIZE

brnzp GRIDSELECTED

SELECTED100

ld r0, GRID100

st r0, GRIDSIZE

GRIDSELECTED

; User input for number of additional ants

lea r0, STHOWMANY

puts

in

add r1, r1, r0 ; r1 = number of additional ants

add r1, r1, #1

st r1, LIVINGANTS

; INITIALIZE FIRST ANT

and r7, r7, x0

add r7, r7, #9 ; loop counter for the other ants

and r1, r1, x0  ; x and y coordinates go in here

and r3, r3, x0  ; to be mapped to a cell id

; check grid size for starting coordinates

ld r4, GRIDSIZE

ld r6, GRID100

not r6, r6

add r6, r6, #1

add r6, r6, r4  ; grid size - 100

brz GRID100B

ld r1, START300

ld r3, START300

brnzp FIRSTANTCOORDINATES

GRID100B

ld r1, START100

ld r3, START100

FIRSTANTCOORDINATES

JSR MAPPY   ; takes r1 and r3 values, converts to cell id in r5

ld r6, LIVEANTTEMPLATE  ; = x8000, alive and facing north

add r6, r6, r5  ; complete antword for ant 1

lea r4, ANTWORD

str r6, r4, #0  ; put first ant in base address of ANTWORD array

ld r2, LIVINGANTS

ANTSETUPLOOP

add r4, r4, #1  ;   increment address of ant

add r2, r2, #-1

brnz INITIALIZEDEAD

JSR ANTCOORDS

JSR MAPPY

ld r6, LIVEANTTEMPLATE

add r6, r5, r6

brnzp READYTOSTORE

INITIALIZEDEAD

and r6, r6, x0

READYTOSTORE

str r6, r4, #0

add r7, r7, #-1

brnz DONESETUP

brnzp ANTSETUPLOOP

DONESETUP

BIGMOVELOOP ; one iteration of this loop moves all 10 ants (doing nothing if they're dead)

ld r1, LIVINGANTS

brz EVERYONEISDEAD

ld r1, ANTWORD

; FOR LOOP TO MOVE ALL 10 ANTS

ld r1, STEPCOUNT

add r1, r1, #1

st r1, STEPCOUNT

BRNZP BIGMOVELOOP

EVERYONEISDEAD ; :(

halt

STGRIDSIZE .stringz "Grid size? 1 for 100, 3 for 300 "

STHOWMANY .stringz "How many additional ants? "

ASCIIDIFF1 .fill #-48

SUBTEMP1 .fill #0

LIVINGANTS .fill #0

GRIDSIZE .fill #0

GRID100 .fill #100

GRID300 .fill #300

STEPCOUNT .fill #0

ANTWORD .blkw #10

START100 .fill #50

START300 .fill #150

LIVEANTTEMPLATE .fill x8000

ANTCOORDTEMP .fill #0

ANTCOORDTEMP2 .fill #0

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

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

;                             SUBROUTINES

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

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

; SUBROUTINE

ANTSONTHEMOVE

; [1] check if dead

; [2] extract current location

; [3] extract current direction

; [4] check current colour

; [5] turn

; [7] change location or kill

; INPUT: R1:

address of ant

;        R4:

grid size

; LOCAL: R2: ant word

;           R3: cell id of ant

st r2, MOVETEMP2

st r3, MOVETEMP3

st r5, MOVETEMP5

st r6, MOVETEMP6

st r7, MOVETEMP7

ldr r2, r1, #0 ; r2 = copy of ant-word

; [1] CHECK FOR DEATH. word for dead ants == x0000

add r2, r2, #0

brz ENDOFMOVE ; if ant-word + 0 == 0, ant is dead.

; [2] extract current location

ld r3, IDMASK ; for getting rid of first 3 bits of ant-word, leaving only location

and r3, r2, r3 ; r3 = cell id of ant

; [4] check current colour and flip it

jsr FLIPPITY    ; flips bit, puts original colour in R5

                ; white/0: turn right; black/1: turn left

; [5] turn the ant according to pre-flipped colour

add r0, r5, #0

brnp LEFTTURN

jsr TAKEARIGHTTURN

brnzp DONETURNING

LEFTTURN

jsr TAKEALEFTTURN

DONETURNING

; [7] change location and kill

ldr r2, r1, #0 ; reload modified antword from memory

ld r5, SOUTH    ; butmasks

ld r6, EAST

and r5, r5, r2

and r6, r6, r2  ; isolating the two direction bits, 2b and 3b, to determine direction

add r5, r5, #0  ;    check if 2b is 0

brnp SECTIOND   ;

add r6, r6, #0  ;   check if 3b is 0

brnp SECTIONC

; if both are zero, direction is north

;; if cell id <= grid size, ant is already at the top and will die

not r0, r4

add r0, r0, #1  ; r0 = negative grid size

add r3, r0, r3  ; r3 = cell id - grid

brn ANTDEATHISPERMANENT ; if negative, kill it

add r2, r2, r0  ; antword - grid size

brnzp ENDOFMOVE

SECTIONC

; if direction is 01, ant faces east

;; if (cellID % grid != grid -1)

;; then cellid++, else die

not r0, r4

add r0, r0, #1

add r5, r3, #0  ;    copy celll id to r5 to repeatedly subtract grid size

EASTMODLOOP

add r5, r5, r0  ;   cell id - grid

add r5, r5, #1  ; if this is 0, then r5 == grid - 1

brz ANTDEATHISPERMANENT

add r5, r5, #-1 ; but if not, undo it and re-loop

brn MOVEEAST    ; if negative, allowed to move east

                ; if equal to grid-1, ant is on eastern border and will die

BRNZP EASTMODLOOP

MOVEEAST

add r2, r2, #1  ; move east: CellID++

brnzp ENDOFMOVE

SECTIOND    ; first direction bit is 1

add r6, r6, #0  ; check if second bit is 0

brnp SECTIONF

; if it is 0, then direction is 10 = south

; if ant is on southern border, it dies

; if cellID >= grid^2-grid, then ant is on southern border

ld r0, N100

add r0, r0, r3  ; checking if grid size = 100

brz GRIDIS100

ld r0, GRIDSQ300HALF

add r3, r3, r0

add r3, r3, r0

add r3, r3, r0

add r3, r3, r0

brzp ANTDEATHISPERMANENT

add r2, r2, r4

brnzp ENDOFMOVE

GRIDIS100

ld r0, GRIDSQ100

add r3, r3, r0

brzp ANTDEATHISPERMANENT

add r2, r2, r4

brnzp ENDOFMOVE

SECTIONF

; direction bits are 11 = WEST

; if cellID % grid != 0, ant can go west, otherwise dead

add r6, r3, #0  ; copy cell id to r6

not r0, r4

add r0, r0, #1  ; r0 = -grid

WESTMODLOOP

add r6, r6, r0

brz ANTDEATHISPERMANENT

brn CANMOVEWEST

brp WESTMODLOOP

CANMOVEWEST

add r2, r2, #-1

brnzp ENDOFMOVE

ANTDEATHISPERMANENT

and r2, r2, #0

ld r7, LIVINGANTS

add r7, r7, #-1

st r7, LIVINGANTS

ENDOFMOVE

str r1, r2, #0  ;    double check this syntax

ld r2, MOVETEMP2

ld r3, MOVETEMP3

ld r5, MOVETEMP5

ld r6, MOVETEMP6

ld r7, MOVETEMP7

RET

N100 .fill #-100

GRIDSQ100 .fill #-9900

GRIDSQ300HALF .fill #-22425

MOVETEMP3 .fill #0

MOVETEMP2 .fill #0

MOVETEMP4 .fill #0

MOVETEMP5 .fill #0

MOVETEMP6 .fill #0

MOVETEMP7 .fill x0

IDMASK .fill x1FFF    ;   for extracting bits 12-0, the cell ID of the ant

; end of ANTSONTHEMOVE subroutine

FAKEXOR ; subroutine

; XOR of two registers

; INPUT r2, r4

; OUTPUT r6 = r2 XOR r4

; A in r4, not A in r5

; B in r2; not B in r6

; r4 XOR r2

st r5, XORTEMP5

not r6, r2

and r6, r6, r4  ; r6 = a & ~b

not r6, r6      ; r6 = ~(a & ~b)

not r5, r4      ; r5 = ~ a

and r5, r5, r2  ; r5 = ~a & b

not r5, r5      ; r5 = ~(~a & b)

and r6, r5, r6  ; r6 = ~(a & ~b) & ~(~a & b)

not r6, r6      ; r6 = ~( ~(a & ~b) & ~(~a & b) ) = a XOR b

ld r5, XORTEMP5

RET 

XORTEMP5 .fill #0

; SUBROUTINE

 FLIPPITY

; Takes a cell id and flips the bit in the grid, returns the original colour

; INPUT     r1: cell id

; LOCAL     r2: which bit to flip, then bitmask

;           r3: quotient, then address of byte to change

; OUTOUT    r5: original colour of cell id, before flipping. 1 if black, 0 if white.

;

; First, get byte (GRID + OFFSET)

; CELL ID / 16

st r4, FLIPTEMP4

st r5, FLIPTEMP5

st r6, FLIPTEMP6

and r3, r3, #0

add r2, r1, #0  ; copy cell id into r2

; loop to divide cellid by 16

FLIPLOOP

add r2, r2, #-16 ; cell id - 16

brn FLIPLOOPDONE    ; if negative, division done

add r3, r3, #1      ; if not negative, increment quotient and subtract again

BRNZP FLIPLOOP

FLIPLOOPDONE

add r2, r2, #8      ; add 16 back to negative number to get cellid % 16

add r2, r2, #8      ; this is which bit within the byte that the cell ID refers to

lea r4, GRID        ; starting address of GRID array

add r3, r3, r4      ; r3 = address of byte that will be changed = GRID base address + CELL ID / 16

lea r4, BM1         ; r4 = address of butmask array

add r4, r4, r2      ; r4 + which bit to flip = address of appropriate bitmask

ldr r2, r4, #0      ; r2 = bitmask to flip one bit

ldr r4, r3, #0      ; r4 = byte to be changed

and r0, r2, r4      ; indicates original colour of bit. 0 if white, non-zero if black

; A in r4, not A in r5

; B in r2; not B in r6

; r4 XOR r2

not r6, r2

and r6, r6, r4  ; r6 = a & ~b

not r6, r6      ; r6 = ~(a & ~b)

not r5, r4      ; r5 = ~ a

and r5, r5, r2  ; r5 = ~a & b

not r5, r5      ; r5 = ~(~a & b)

and r6, r5, r6  ; r6 = ~(a & ~b) & ~(~a & b)

not r6, r6      ; r6 = ~( ~(a & ~b) & ~(~a & b) ) = a XOR b

str r6, r3, #0

ld r4, FLIPTEMP4

ld r6, FLIPTEMP6

add r5, r0, #0  ; move colour of bit into r5 for output

ret

GRID .fill x8000

FLIPTEMP4 .fill #0

FLIPTEMP5 .fill #0

FLIPTEMP6 .fill #0

; bitmasks for flipping one bit

BM1 .fill x8000

BM2 .fill x4000

BM3 .fill x2000

BM4 .fill x1000

BM5 .fill x0800

BM6 .fill x0400

BM7 .fill x0200

BM8 .fill x0100

BM9 .fill x0080

BM10 .fill x0040

BM11 .fill x0020

BM12 .fill x0010

BM13 .fill x0008

BM14 .fill x0004

BM15 .fill x0002

BM16 .fill x0001

; END OF FLIPPITY SUBROUTINE

; SUBROUTINE

TAKEALEFTTURN

; turns the ant 90 degrees left

; INPUT R1: address in memory of ANT

; LOCAL R2: ant

;       R3: bitmask

;       R4: 3rdbit

;       R5: 2nd and 3rd bit

;       R6:

;       R7:

;       R0:

st r2, LEFTTURNTEMP2

st r3, LEFTTURNTEMP3

st r4, LEFTTURNTEMP4

st r6, LEFTTURNTEMP6

st r7, LEFTTURNTEMP7  ;  store r7, load before RET

ldr r2, r1, #0  ;  load ant into r2

ld r3, EAST

and r4, r2, r3 ; r4 = 3rdbit

ld r3, WEST

;and r5, r2, r3 ; r5 = 2nd and 3rd bits

add r4, r4, #0 ; check if 3rd bit is 0

brnp THIRDBIT1  ; If so, continue. If not, jump to next part.

; 3rd bit is 0, so XOR r2 ant-word with WEST bitmask, already in R3

BRNZP LEFTTURNEND

THIRDBIT1

; third bit is 1, so use EAST bitmask

ld r3, EAST

LEFTTURNEND

add r0, r4, #0  ; move r4 3rdbit into r0 temporarily

add r4, r3, #0  ; move r3 bitmask into r4 for the XOR subroutine

JSR FAKEXOR   ; r6 = r2 XOR r4

              ; flips the correct bit to turn left

add r3, r4, #0 ; moves r4 bitmask back into r3

add r4, r0, #0  ; moves r0 3rdbit back into r3

str r6, r1, #0  ; store tweaked ant-word with new direction back in memory

ld r2, LEFTTURNTEMP2

ld r3, LEFTTURNTEMP3

ld r4, LEFTTURNTEMP4

ld r6, LEFTTURNTEMP6

ld r7, LEFTTURNTEMP7

RET

WEST .fill X6000

EAST .fill x2000

NORTH .fill x0000

SOUTH .fill x4000

LEFTTURNTEMP2 .fill #0

LEFTTURNTEMP3 .fill #0

LEFTTURNTEMP4 .fill #0

LEFTTURNTEMP6 .fill #0

LEFTTURNTEMP7 .fill #0

; end of TAKEALEFTTURN subroutine

; SUBROUTINE

TAKEARIGHTTURN

; turns the ant 90 degrees right

; INPUT R1: address in memory of ANT

; LOCAL R2: ant

;       R3: bitmask

;       R4: 3rdbit

;   R5: 2nd and 3rd bit

;   R6:

;   R7:

;   R0:

st r2, RIGHTTURNTEMP2

st r3, RIGHTTURNTEMP3

st r4, RIGHTTURNTEMP4

st r6, RIGHTTURNTEMP6

st r7, RIGHTTURNTEMP7  ;  store r7, load before RET

ldr r2, r1, #0  ;  load ant into r2

ld r3, EAST

and r4, r2, r3 ; r4 = 3rdbit

;ld r3, WEST

;and r5, r2, r3 ; r5 = 2nd and 3rd bits

add r4, r4, #0 ; check if 3rd bit is 0

brnp THIRDBIT1RIGHT  ; If so, continue. If not, jump to next part.

; 3rd bit is 0, so XOR r2 ant-word with EAST bitmask

ld r3, EAST

BRNZP RIGHTTURNEND

THIRDBIT1RIGHT

; third bit is 1, so use WEST bitmask

ld r3, WEST

RIGHTTURNEND

add r0, r4, #0  ; move r4 3rdbit into r0 temporarily

add r4, r3, #0  ; move r3 bitmask into r4 for the XOR subroutine

JSR FAKEXOR   ; r6 = r2 XOR r4

              ; flips the correct bit to turn right

add r3, r4, #0 ; moves r4 bitmask back into r3

add r4, r0, #0  ; moves r0 3rdbit back into r3

str r6, r1, #0  ; store modified ant-word with new direction back in memory

ld r2, RIGHTTURNTEMP2

ld r3, RIGHTTURNTEMP3

ld r4, RIGHTTURNTEMP4

ld r6, RIGHTTURNTEMP6

ld r7, RIGHTTURNTEMP7

RET

RIGHTTURNTEMP2 .fill #0

RIGHTTURNTEMP3 .fill #0

RIGHTTURNTEMP4 .fill #0

RIGHTTURNTEMP6 .fill #0

RIGHTTURNTEMP7 .fill #0

; end of TAKEARIGHTTURN subroutine

; SUBROUTINE

ANTCOORDS

; INPUT     r2: index of ant

; OUTPUT    r1: x coordinate value

;           r3: y coordinate value

; "Enter x coordinates for ant #whatever"

st r4, COORD2

ld r0, NEWLINE

out

lea r0, ENTERXCOORDS

puts

ld r3, ASCIIPLUS

;add r0, r2, r3

;out

ld r0, NEWLINE

out

ld r5, ASCIIDIFF 

getc

out

add r4, r0, r5  ; r4 holds first digit of x

add r1, r4, r4  ; r1 = 2 * r4

add r1, r1, r1  ; r1 = 4 * r4

add r1, r1, r1  ; r1 = 8 * r4

add r1, r1, r4  ; r1 = 9 * r4

add r1, r1, r4  ; r1 = 10 * r4

getc

out

add r4, r0, r5  ; r4 holds 2nd digit of x

add r1, r1, r4  ; full value of x coordt

st r1, COORD1

; "enter y coords"

ld r0, NEWLINE

out

lea r0, ENTERYCOORDS

puts

ld r3, ASCIIPLUS

;add r0, r2, r3

;out

ld r0, NEWLINE

out

ld r5, ASCIIDIFF 

getc

out

add r4, r0, r5  ; r4 holds first digit of y

add r1, r4, r4  ; r1 = 2 * r4

add r1, r1, r1  ; r1 = 4 * r4

add r1, r1, r1  ; r1 = 8 * r4

add r1, r1, r4  ; r1 = 9 * r4

add r1, r1, r4  ; r1 = 10 * r4

getc

out

add r4, r0, r5  ; r4 holds 2nd digit of y

add r3, r1, r4  ; full value of y coord

ld r1, COORD1

ld r4, COORD2

RET

ENTERXCOORDS .STRINGZ "Enter x coordinates for ant "

ENTERYCOORDS .STRINGZ "Enter y coordinates for ant "

ASCIIDIFF .fill #-48

ASCIIPLUS .fill #48

COORD1 .fill #0

NEWLINE .fill #10

COORD2 .fill #0

COORD3 .fill #0

; END OF ANT_COORDINATES_SUBROUTINE

MAPPY

; Maps the coordinates of the ant

; Input:  R1: x coord

;  R3: y coord

;  R4: grid size

; Output: R5: Cell ID

; Cell ID = grid size * y coord + x coord

st r6, MAP1

st r7, MAP2

; multiply by 100

add R0, R3, R3 ; 2y

add R0, R0, R0 ; 4y

add R6, R0, R0 ; 8y

add R6, R6, R6 ; 16y

add R6, R6, R6 ; 32y

add R0, R0, R6 ; 36y

add R6, R6, R6 ; 64y

add R0, R0, R6 ; 100y

ld R7, N100a

add R7, R4, R7

brz GRID100a

add R0, R0, R0 ;200y

add R0, R0, R3 ;300y

GRID100a

Add R5, R0, R1  ; OUTPUT: R5 = grid*y + x

ld r6, MAP1

ld r7, MAP2

RET

N100a .fill #-100

MAP1 .fill #0

MAP2 .fill #0

; END OF MAPPY SUBROUTINE

.end

</lang>