title	Das Sieb des Eratosthenes
	name	('SIEVE')

; The Sieve of Eratosthenes in Assembler
; Algorithm based upon an article from the Internet

; This version allowes the dynamic assignment of the top value 2..N

	entry	$memry

OS	equ	0000h
BDOS	equ	0005h
TPATOP	equ	BDOS+1
CCP	equ	0080h

.conout	equ	2
.string	equ	9

NDEF	equ	100		; Default max

noprime	equ	0
prime	equ	1

colmax	equ	10

null	equ	00h
tab	equ	09h
lf	equ	0ah
cr	equ	0dh
eot	equ	'$'

	dseg
$TRAILER:
	db	'      ',eot
$DELIM:
	db	'  ',eot
$HEAD1:
	db	'Das Sieb des Eratosthenes 2-',eot
$HEAD2:
	db	'Primzahlen:',cr,lf
	db	'-----------',cr,lf,eot
$NOMEM:
	db	'Nicht genug Speicher - Abbruch'
	db	cr,lf,eot
$NON:
	db	'Falsche Eingabe fuer N - Abbruch'
	db	cr,lf,eot
$memry:
	ds	2
tentbl:
	dw	10000
	dw	1000
	dw	100
	dw	10
j:
	ds	2		; Working variable
p:
	ds	2		; Working variable
col:
	ds	1		; Console column
Array:
	ds	2		; Prime number array
NVAL:
	ds	2		; Max prime number
	cseg

;
; =========================== OS Support ===========================
;
; Print string ^DE on console
;
String:
	push	bc
	push	de
	push	hl
	ld	c,.string
	call	BDOS		; Print
	pop	hl
	pop	de
	pop	bc
	ret
;
; Put new line to console
;
PrNL:
	ld	a,cr
	call	Conout
	ld	a,lf
;
; Put character in Accu to console
;
Conout:
	push	bc
	push	de
	push	hl
	ld	c,.conout
	ld	e,a		; Get character
	call	BDOS		; Put to console
	pop	hl
	pop	de
	pop	bc
	ret
;
; Convert hex number in HL to ASCII decimal string with B places
;
PrDec:
	call	decout		; Convert to ASCII
	ld	hl,($memry)	; Get ASCII pointer
	inc	b
	dec	b		; Test places defined
	call	nz,Place	; Yeap
noPlace:
	ld	a,(hl)		; Get character
	or	a		; Test end
	ret	z		; Yeap
	call	Conout		; Print it
	inc	hl
	jr	noPlace
;
; Fix places
;
Place:
	push	hl		; Save base
	ld	c,0		; Init count
getLen:
	ld	a,(hl)		; Get character
	or	a		; Test end
	jr	z,gotLen	; Yeap
	inc	hl		; Point to next
	inc	c		; Count up
	jr	getLen
gotLen:
	pop	hl		; Get back base
	ld	a,b		; Get place count
	sub	c		; Get difference
	ret	z		; Nothing to do
	ret	c
	ld	b,a
PrSpc:
	ld	a,' '
	call	Conout		; Print leading spaces
	djnz	PrSpc
	ret
;
; The conversion routine
;
decout:
	push	bc		; Save digit count
	push	ix
	ld	ix,($memry)	; Get ASCII pointer
	ld	de,tentbl	; Point to table
	push	de		; Onto stack
	ld	c,1		; Set zero flag
dotpos:
	ex	(sp),hl
	ld	e,(hl)		; Get pointer
	inc	hl
	ld	d,(hl)
	inc	hl
	ex	(sp),hl
	ld	b,-1		; Clear digit
dotdiv:
	inc	b		; Count digits
	or	a
	sbc	hl,de		; Get difference
	jr	nc,dotdiv	; Test < 0
	add	hl,de		; Make > 0
	xor	a		; Clear result
	or	b		; Test zero digit
	jr	nz,dotstr
	or	c		; Clear leading zero
	jr	nz,dotbyp
dotstr:
	ld	c,0		; Clear zero flag
	or	'0'		; Make ASCII
	ld	(ix),a		; Save digit
	inc	ix
dotbyp:
	ld	a,e		; Test end of table
	cp	10
	jr	nz,dotpos
	ld	a,l		; Get LSD
	or	'0'		; Make ASCII
	pop	de
	push	ix
	pop	hl		; Get back pointer
	ld	(hl),a		; Set last digit
	inc	hl
	ld	(hl),null	; Set end character
	pop	ix
	pop	bc
	ret
;
; Multiply signed integers HL:=HL*DE
;
Multiply:
	ld	c,e		; Copy multiplicand
	ld	b,d
	ex	de,hl
	ld	hl,0		; Init product
	ld	a,d
	or	a		; Test word
	ld	a,16
	jr	nz,MultLoop	; Yeap, set bit count
	ld	d,e
	ld	a,8		; Change bit count
MultLoop:
	add	hl,hl		; Do the multiplication
	ex	de,hl
	add	hl,hl
	ex	de,hl
	jr	nc,MultNC
	add	hl,bc
MultNC:
	dec	a
	jr	nz,MultLoop
	ret
;
; Kill leading and trailing blanks in command line
;
noblnk:
	ld	ix,CCP		; Load command line
	ld	iy,CCP+1	; Point to start
headoff:
	ld	a,(iy)		; Get leading character
	call	isblank		; Test blank
	jr	nz,trailoff	; No, all killed
	dec	(ix)		; Shrink the length
	inc	iy		; Point to next
	jr	headoff
trailoff:
	ld	c,(ix)		; Get remaining length of line
	ld	b,0
	add	ix,bc		; Point to end
	ld	b,c
deltrail:
	ld	(ix+2),null	; Force end of string
	dec	ix		; Get previous one
	ld	a,(ix+2)
	call	isblank		; Test blank
	ret	nz		; Nope, let's go
	djnz	deltrail	; Go thru the line
	jr	illdig
;
; Test white space, Z set says yes
;
isblank:
	cp	' '		; Simple test
	ret	z
	cp	tab
	ret
;
; Convert possible command input string to "N"
; Take default if not defined
;
Nin:
	ld	a,(CCP)
	or	a		; Test any input
	ld	hl,NDEF
	ret	z		; Nope, take default
	call	getN		; Get value
	dec	hl
	ld	a,l		; 1 is invalid
	or	h
	jr	z,illdig
	inc	hl
	ld	a,l		; 0 is too
	or	h
	ret	nz
	jr	illdig
;
; Convert ASCII to hex in reg HL
;
getN:
	call	noblnk		; Kill leading and trailing blanks
	ld	hl,0		; Init decimal
getdig:
	ld	a,(iy)		; Get character
	or	a		; Test end
	ret	z		; Yeap, got it
	sub	'0'		; Verify correct range
	jr	c,illdig
	cp	'9'+1-'0'
	jr	nc,illdig
	ld	c,l
	ld	b,h
	add	hl,hl		; * 2
	add	hl,hl		; * 4
	add	hl,bc		; * 5
	add	hl,hl		; *10
	ld	c,a
	ld	b,0
	add	hl,bc		; Insert new digit
	inc	iy
	jr	getdig
illdig:
	ld	de,$NON
	call	String		; Invalid digit
	jp	OS
;
; =================================================================
;
; Clear the prime number field
;
inifield:
	ld	hl,(Array)
	ld	(hl),noprime	; Set first to non prime
	inc	hl
	ld	(hl),prime	; Set next to prime
	ld	e,l
	ld	d,h
	inc	de
	ld	bc,(NVAL)	; Get value for length
	ldir			; Prime to the rest
	ret
;
; Calculate prime numbers
;
Sieve:
	ld	hl,2
	ld	(p),hl		; Init first number
SieveMain:
	ld	hl,(p)
	ld	e,l
	ld	d,h
	call	Multiply	; Build square
	ex	de,hl
	ld	hl,(NVAL)	; Get pointer to array
	or	a
	sbc	hl,de		; Test in range
	ret	c		; Nope, done
	ld	hl,(p)
	ld	e,l
	ld	d,h
	call	Multiply	; Build square
	ld	(j),hl
SieveLoop:
	ex	de,hl
	ld	hl,(NVAL)	; Get pointer to array
	or	a
	sbc	hl,de		; Test in range
	jr	c,SieveNoprime	; Nope
	ld	de,(Array)
	dec	de
	ld	hl,(j)
	add	hl,de
	ld	(hl),noprime	; Set no prime
	ld	hl,(j)
	ld	de,(p)
	add	hl,de
	ld	(j),hl		; Update index
	jr	SieveLoop
SieveNoprime:
	ld	hl,(p)
	inc	hl
	ld	(p),hl
	ld	de,(Array)
	dec	de
	add	hl,de
	ld	a,(hl)
	cp	prime		; Find prime
	jr	nz,SieveNoprime
	jr	SieveMain
;
; Display prime numbers
;
ShowPrime:
	ld	a,2
	ld	(col),a		; Init column
	ld	de,$TRAILER
	call	String		; Print trailer
	ld	hl,2		; Set first prime number
	ld	bc,(NVAL)	; Set length of array
	dec	bc
	ld	de,(Array)
	inc	de		; Point to first prime
ShowLoop:
	push	bc
	push	de
	push	hl
	ld	a,(de)
	cp	prime		; Test prime
	jr	nz,ShowOn	; Nope
	ld	b,4
	call	PrDec		; Print four places
	ld	hl,col
	inc	(hl)		; Update column
	ld	a,(hl)
	cp	colmax+1	; Test max reached
	jr	nz,ShowDelim	; Nope
	call	PrNL		; Give new line
	ld	a,1
	ld	(col),a		; Reset column
	jr	ShowOn
ShowDelim:
	ld	de,$DELIM
	call	String		; Give delimiter
ShowOn:
	pop	hl
	pop	de
	pop	bc
	inc	de
	inc	hl		; Update prime number
	dec	bc
	ld	a,c
	or	b
	jr	nz,ShowLoop
	ret
;
; Start of Sieve
;
EnterSieve:
	call	Nin		; Load N from CCP line
	ld	(NVAL),hl	; For array base
	ex	de,hl
	ld	hl,($memry)	; Get pointer to free memory
	inc	h		; Allow one free page
	inc	hl
	inc	hl
	ld	(Array),hl	; Set base of Array field
	inc	hl
	inc	hl
	add	hl,de		; Point to top of field
	ld	de,(TPATOP)	; Get top of memory
	dec	d		; One free page
	or	a
	sbc	hl,de		; Test free space
	jr	nc,NoMem	; Nope
	ld	sp,(TPATOP)	; Get stack
	ld	de,$HEAD1
	call	String		; Give some info
	ld	hl,(NVAL)	; Get pointer to array
	ld	b,0
	call	PrDec		; Print number range
	call	PrNL
	ld	de,$HEAD2
	call	String
	call	inifield	; Clear the prime number field
	call	Sieve		; Calculate prime numbers
	call	ShowPrime	; Display prime numbers
	jp	OS		; End of program
NoMem:
	ld	de,$NOMEM
	call	String		; Not enough memory
	jp	OS

	end	EnterSieve