title	Das Sieb des Eratosthenes
	name	('SIEVE')

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

	entry	$memry

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

.conout	equ	2
.string	equ	9

N	equ	100

noprime	equ	0
prime	equ	1

colmax	equ	10

null	equ	00h
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
$memry:
	ds	2
tentbl:
	dw	10000
	dw	1000
	dw	100
	dw	10
j:
	ds	2
p:
	ds	2
col:
	ds	1
Array:
	ds	2
	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
;
; =================================================================
;
; 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,N-2
	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,N
	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,N
	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,N-1		; Set length of array
	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:
	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
	ld	de,N
	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,N
	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