;-----------------------------------------------------------------------
; Dense Sieve of Eratosthenes program - by Tenie Remmel
;
; Calculates all primes up to limit of available memory, 16 per byte
; Goes up to 9M (9437184) if there is more than 576K of free memory.
;
; Requires 80186, DOS 2.0, 70K free memory
;-----------------------------------------------------------------------
.Model Tiny
.186
.Code
Org 100h
Start: jmp Main
;-----------------------------------------------------------------------
NoMem$ db 'Out of memory.',13,10,'$'
CalcMsg$ db 'Calculating primes to '
SegChar db '0M...$'
OutMsg$ db 13,10,13,10,'Output values (Y/N)? $'
Number$ db ' 2',13,10,'$'
TotalMsg$ db 13,10
Total$ db ' 0 total primes',13,10,'$'
NumSegs dw 0
;-----------------------------------------------------------------------
; Main routine
;-----------------------------------------------------------------------
Main: mov sp,1000h ;Set new stack position
mov ah,4Ah ;Shrink code segment to 4K
mov bx,100h
int 21h
jc NoMem
mov bp,0A000h ;BP = 0A000h (640K)
MemLoop: mov bx,bp ;BX = buffer size
mov ah,48h ;Attempt to allocate buffer
int 21h
jnc MemOK ;Jump if successful
sub bp,1000h ;Shrink by 64K
jnz MemLoop ;Loop back
NoMem: mov dx,offset NoMem$ ;Display 'Out of memory.'
call PrtStr
mov ax,4C01h ;Exit to DOS
int 21h
;---------------------------------------
MemOK: mov es,ax ;ES = buffer segment
mov bx,bp ;BX = buffer size
xchg bp,ax ;BP = first segment
shr bx,12 ;BX = buffer size / 64K
mov [NumSegs],bx ;Set max segment
add [SegChar],bl ;Set ASCII segment char
push es ;Save ES
ClrLoop: mov es,bp ;ES = this segment
xor ax,ax ;Clear the buffer
xor di,di
mov cx,8000h
rep stosw
add bp,1000h ;Next segment
dec bx ;Loop back
jnz ClrLoop
pop es ;Restore ES
;---------------------------------------
mov dx,offset CalcMsg$ ;Display 'Calculating primes...'
call PrtStr
call Sieve ;Perform the sieve
mov dx,offset OutMsg$ ;Display 'Output values (Y/N)? '
call PrtStr
mov ah,0 ;Get a key
int 16h
int 29h ;Display the key
cmp al,'Y' ;'Y' = print
je Print
cmp al,'y'
jne Finish
Print: call PrintOut ;Print out all primes
Finish: call DispCount ;Display total prime count
mov ah,49h ;Release the memory
int 21h
mov ax,4C00h ;Exit to DOS
int 21h
;-----------------------------------------------------------------------
; Sieve - Perform Sieve of Eratosthenes - ES = buffer (cleared to 0)
;-----------------------------------------------------------------------
Sieve: mov bp,es ;BP = buffer segment
mov byte ptr es:[0],80h ;Set first bit (1 is not prime)
xor bx,bx ;BX:CL = 0:1 (first number = 1)
xor cl,cl
mov al,80h ;AL = bit mask for CL
S_loop: inc cx ;Next number
and cl,7
ror al,1
adc bx,0
cmp bx,181 ;If BX:CL > Sqrt(8388608) = 2896,
jae S_done ;then we're done
test es:[bx],al ;If this number is not prime, then loop
jnz S_loop
pusha ;Save all registers
;---------------------------------------
mov dx,bx ;DX = high 16 bits
shl cl,5 ;Shift low 3 bits to top
add cl,cl ;Multiply DX:CL by 2, then
adc dx,dx ;shift CL back down and add 1
shr cl,5
inc cx ;Now DX:CL is the increment needed
;to move to each multiple
mov si,bp ;SI = buffer segment
mov di,[NumSegs] ;DI = num. of segments
S_iloop: mov ah,al ;AH = old bit mask
ror al,cl ;Rotate bit mask
cmp ah,al ;Set carry (JB=JC) if bit wrapped
adc bx,dx ;Add 1 to offset if bit wrapped
jnc S_ilb ;If segment wrapped, then
add si,1000h ;Add 1000h to segment
dec di ;Exit if last segment
jz S_idone
mov es,si ;ES = new segment
S_ilb: or es:[bx],al ;Set this bit to indicate non-prime
jmp S_iloop ;Loop back
;---------------------------------------
S_idone: popa ;Restore registers
mov es,bp ;Restore ES
jmp S_loop ;Loop back
S_done: ret ;Return
;-----------------------------------------------------------------------
; PrintOut - Print out all primes - ES = buffer
;-----------------------------------------------------------------------
PrintOut: push es ;Save all registers
pusha
mov bp,es ;BP = buffer segment
mov di,[NumSegs] ;DI = num. of segments
mov ah,9 ;AH = 9 for string output
mov dx,offset Number$ ;DX = offset of number string
mov cx,8 ;CX = length of number string
int 21h ;Output first prime (2)
call IncString ;Number now contains 3
xor bx,bx ;BX:AL = position of 3 in buffer
mov al,40h
P_loop: test es:[bx],al ;Check for prime
jnz P_cont ;Jump if not a prime
push ax ;Save AX
int 21h ;Output the number
pop ax ;Restore AX
P_cont: call IncString ;Add 2 to the number
call IncString
ror al,1 ;Next bit in buffer
adc bx,0
jnc P_loop ;Loop while no wrqp
add bp,1000h ;Next segment
mov es,bp
dec di ;Loop back
jnz P_loop
popa ;Restore registers
pop es
ret ;Return
;-----------------------------------------------------------------------
; DispCount - Display total count - ES = buffer
;-----------------------------------------------------------------------
DispCount: push es ;Save all registers
pusha
mov bp,es ;BP = buffer segment
mov di,[NumSegs] ;DI = num. of segments
mov dx,offset Total$ ;DX = offset of total string
mov cx,8 ;CX = length of number string
call IncString ;Account for first prime (2)
xor bx,bx ;BX:AL = position of 3 in buffer
mov al,40h
D_loop: test es:[bx],al ;Check for prime
jnz D_cont ;Jump if not a prime
call IncString ;Increment the string
D_cont: ror al,1 ;Next bit in buffer
adc bx,0
jnc D_loop ;Loop while no wrqp
add bp,1000h ;Next segment
mov es,bp
dec di ;Loop back
jnz D_loop
mov dx,offset TotalMsg$ ;Display total prime count
call PrtStr
popa ;Restore registers
pop es
ret ;Return
;-----------------------------------------------------------------------
; IncString - Increment a string - DS:SI = string, CX = length
;-----------------------------------------------------------------------
IncString: pusha ;Save registers
mov si,dx ;SI = string
mov bx,cx ;BX = end of string
dec bx
IS_loop: mov al,[si+bx] ;Get char
or al,30h ;Space --> Zero
inc ax ;Increment & set char
mov [si+bx],al
cmp al,'9' ;If no carry, then quit
jbe IS_done
mov byte ptr [si+bx],'0';Otherwise, set to 0,
dec bx ;and continue
jnl IS_loop
IS_done: popa ;Restore registers and return
ret
;-----------------------------------------------------------------------
; PrtStr - Print a string w/o redirection - DS:DX = string
;-----------------------------------------------------------------------
PrtStr: pusha ;Save registers
mov si,dx ;DS:SI = string
PS_loop: lodsb ;Get char
cmp al,'$' ;Exit if '$'
je PS_done
int 29h ;Output to screen
jmp PS_loop ;Loop back
PS_done: popa ;Restore registers and return
ret
;-----------------------------------------------------------------------
End Start
