; Sieve of Eratosthenes demo for the Hades website.
; fnh 2006.11.30
;

start:	
	movi r1, 1		; $0001
	lsli r1, 8		; $0100
	jsr message

	jsr sieve

	movi r1, 1		; $0001
	lsli r1, 8		; $0100
	bseti r1, 7		; $0180
	jsr message

	jsr print_sieve
      	halt


message:
	; copies he string pointed to by r1 to the parallel
	; terminal. Modifies r1; uses r2,r3 and r10.

	; initialize r10 as pointer to the parallel terminal
	; at $7000. Note that bit 9 is wired to nclear,
        ; while bit 8 is wired to strobe, and bits 7..0 are
        ; are terminal data bits.
        ;
	movi r10, 7		; $0007
	lsli r10, 12		; $7000 base address
	movi r3, 0		; $0000 for null-check

p1:
	ldw r2, 0(r1)		; load next char to r2
	cmpe r2, r3		; null? (end of string)
	bt p2
	
	bseti r2, 9		; set terminal nreset-bit
	stw r2, 0(r10)		; write char to terminal
	bseti r2, 8		; set clk-bit
	stw r2, 0(r10)		; to terminal again
	bclri r2, 8		; reset clk-bit
	stw r2, 0(r10)		; and to terminal again

	addi r1, 2		; increment ptr
	br p1			; not yet, next char
p2:
	jmp r15			; return



sieve:
	; initialize r14 as pointer to sieve at $8100
	;
	movi r14, 8		; $0008
	lsli r14, 4		; $0080
	addi r14, 1		; $0081
	lsli r14, 8		; $8100

	; initialize r13 as the sieve size, here 256
	;
	movi r13, 1		; $0001
	lsli r13, 8		; $0100

	; initialize r12 as "marker value" $cccc
	movi r12, $c
	lsli r12, 4
	addi r12, $c
	lsli r12, 4
	addi r12, $c
	lsli r12, 4
	addi r12, $c

clear_sieve:
	; write the special "marker" value to all sieve
	; locations. We use r1 as the pointer and r2
	; as the loop end marker.
	;
	mov r1, r14		; first element
	mov r2, r14		; first element
	addu r2, r13		; add sieve size twice
	addu r2, r13		; (byte addressing)
				; to get last element

l2:	
	stw r12, 0(r1)		; store marker at *r1
	addi r1, 2		; increment pointer
	cmplt r1, r2		; loop end check
	bt l2			; next iteration

mark_even:
	; mark all even numbers in the sieve
	;
	mov r1, r14		; pointer
	movi r3, 2		; current value is 2	

	addu r1, r3		; skip sieve entry 
	addu r1, r3		; skip sieve entry 
	addu r1, r3		; skip sieve entry 
	addu r1, r3		; skip sieve entry 

l3:
	stw r3, 0(r1)		; store 2 at *r1
	addi r1, 4		; increment to next
				; even location
	cmplt r1, r2		; loop end check
	bt l3			; next iteration


mark_outer:
	; outer loop over all odd integers
	; r4 holds the current value


	movi r4, 3		; first odd number

mark_odd:
	; inner loop to mark all multiples of the
 	; current value of r4

	mov r1, r14		; pointer
	addu r1, r4		; increment to next 
	addu r1, r4		; multiple in sieve
	addu r1, r4		; increment to next 
	addu r1, r4		; multiple in sieve

l4:
	cmplt r1, r2		; in bounds?
	bf el4			; no, exit loop
	stw r4, 0(r1)		; store r4 at *r1
	addu r1, r4		; increment to next 
	addu r1, r4		; multiple in sieve
	br l4			; next iteration

el4:
	; increment r4 to next odd number
	;
	addi r4, 2
	
	; check for outer loop termination
	;
	cmplt r4, r13		; r4 < r14?
	bt mark_odd		; next outer iteration

	; the sieve is ready now: all positions with
	; sieve[x] = x are prime numbers.
	jmp r15			; return




; 
print_sieve:
	; we assume that r14 still holds a pointer to the
	; sieve array, and r13 is the size of the sieve.

	movi r10, 7		; $0007
	lsli r10, 12		; $7000 terminal base address

	movi r8, 2		; $0002
	lsli r8, 4		; $0020 = 32 for linefeed check

	mov r1, r14		; pointer to sieve
	movi r2, 0		; counter

p5:
	ldw r4, 0(r1)		; load sieve value at index
	cmpe r4, r12		; check sieve[x] == 0xcccc?
	bt star			; yes: prime, print a star

dot:				; r9 = '.' = $2e
	movi r9, 2
	lsli r9, 4
	addi r9, $e
	br pds

star:	                       	; r9 = '*' = $2a
	movi r9, 2
	lsli r9, 4
	addi r9, $a

pds:	; output symbol from r9 to terminal

	bseti r9, 9		; terminal.nclear passive
	stw r9, 0(r10)		; write data	
	bseti r9, 8		; set strobe bit
	stw r9, 0(r10)		; write data again	
	bclri r9, 8		; reset strobe bit
	stw r9, 0(r10)		; and write again

	addi r2, 1		; increment index
	addi r1, 2		; increment sieve pointer

	; check for line feed after 32 chars (8 rows, 32 cols)
 	;
	cmpe r2, r8
	bt linefeed

pds2:
	cmplt r2, r13		; check loop end
	bt p5			; next iteration

	; we're done.
	jmp r15			; return


linefeed:
	movi r9, 13		; cr character
	bseti r9, 9		; terminal.nclear passive
	stw r9, 0(r10)		; write data
	bseti r9, 8		; set strobe bit
	stw r9, 0(r10)		; write data again	
	bclri r9, 8		; reset strobe bit
	stw r9, 0(r10)		; and write again

	movi r9, 10		; linefeed character
	bseti r9, 9		; terminal.nclear passive
	stw r9, 0(r10)		; write data
	bseti r9, 8		; set strobe bit
	stw r9, 0(r10)		; write data again	
	bclri r9, 8		; reset strobe bit
	stw r9, 0(r10)		; and write again

	; update r8 for next check
	addi r8, 15
	addi r8, 15
	addi r8, 2

	; back into printing loop
	br pds2

	halt


; the static data


	.org	$0100
	.ascii  "Welcome to the Sieve of Eratosthenes demo!"
	.defw	10
	.defw	13
	.ascii	"Please wait..."
	.defw	0

	.org	$0180
	.ascii  "Ready. Sieve:"
	.defw	10
	.defw	13
	.defw	0

	.end