title 'Eratosthenes Sieve for 80386'
name sieve
page 50,132
;
; Eratosthenes Sieve for 80386 32-bit protected mode
; Implemented by Ray Duncan, April 1987
; After Gilbreath, Byte September 1981, and January 1983
;
; Here is the MAKE file for this program:
;
; sieve386.obj : sieve386.asm
; 386asm sieve386
;
; sieve386.exe : sieve386.obj
; 386link sieve386 start386 -exe sieve386 -map sieve386
;
; To run the program with PharLap DOS|EXTENDER:
; C>RUN386 SIEVE386
;
niter equ 100 ; number of iterations
asize equ 8190 ; size of array "flags"
cr equ 0dh ; ASCII carriage return
lf equ 0ah ; ASCII line feed
stdin equ 0 ; handle for standard input
stdout equ 1 ; handle for standard output
_TEXT segment para public use32 'CODE'
assume cs:_TEXT,ds:_DATA,es:_DATA
public _start_ ; magic name for RUN386 entry
_start_ proc near
xor edx,edx ; convert number of iterations
mov eax,niter ; for output
mov ecx,10
mov esi,offset msg1a+3
call binasc
mov edx,offset msg1 ; display message
mov ecx,msg1_len ; "Starting N iterations of sieve"
call pmsg
call getmsec ; get current time in msec
push eax ; and save it...
mov counter,niter ; initialize iterations counter
sieve1: ; a sieve iteration starts here...
mov edi,offset flags ; initialize flags array
mov ecx,asize ; to all bytes = TRUE
mov al,1
cld
rep stosb
xor esi,esi ; ESI = index to flags array
xor edi,edi ; EDI = primes counter
sieve2: ; main loop of sieve
test byte ptr flags[esi],1 ; is this a prime?
jnz short sieve4 ; jump if prime
sieve3: inc esi ; bump to next slot in "flags"
cmp esi,asize
jle sieve2 ; loop until array exhausted
dec counter ; count off sieve iterations
jnz sieve1 ; jump, another iteration needed.
jmp sieve7 ; jump, all iterations finished.
sieve4: ; prime found, zap its multiples
mov ebx,esi ; copy i
mov edx,ebx ; EDX = prime = i + i + 3
add edx,edx
add edx,3
xor al,al
jmp short sieve6
sieve5: mov byte ptr flags[ebx],al ; zero this multiple
sieve6: add ebx,edx ; find next multiple of prime
cmp ebx,asize ; have we exhausted the array?
jle sieve5 ; not yet, zap it
inc edi ; count primes and try next
jmp sieve3
sieve7: call getmsec ; all done, get current time
push eax
mov eax,edi ; convert number of primes
mov edx,0 ; found on last iteration
mov ecx,10
mov esi,offset msg2a+4
call binasc
mov edx,offset msg2 ; display "Number of primes: "
mov ecx,msg2_len
call pmsg
pop eax ; calculate total elapsed msec.
pop ebx
sub eax,ebx
mov edx,0 ; divide by number of iterations
mov ecx,niter ; to get msec per iteration
idiv ecx
mov edx,0 ; convert msec to ASCII
mov ecx,10
mov esi,offset msg3a+4
call binasc
mov edx,offset msg3 ; display "Elapsed time:"
mov ecx,msg3_len
call pmsg
mov ax,04C00h ; final exit, return code = 0
int 21H
_start_ endp
getmsec proc near ; Return EAX = current time in msec.
mov ah,2ch ; read time
int 21h
movzx eax,ch ; EAX := hours
imul eax,60 ; hours -> minutes
and ecx,0ffh ; isolate system minutes
add eax,ecx ; and find total minutes
imul eax,60 ; minutes -> seconds
movzx ecx,dh ; isolate system seconds
add eax,ecx ; and find total seconds
and edx,0ffh ; isolate hundredths
imul eax,100 ; seconds -> hundredths
add eax,edx ; find total hundredths
imul eax,10 ; hundredths -> msec
ret
getmsec endp
;
; BINASC: Convert 64 bit binary value to ASCII string.
;
; Call with EDX:EAX = signed 64 bit value
; ECX = radix
; DS:ESI = last byte of area to store resulting string
; (make sure enough room is available to store
; the string in the radix you have selected.)
;
; Destroys EAX, EBX, ECX, EDX, and ESI.
;
binasc proc near ; convert EDX:EAX to ASCII.
mov byte ptr [esi],'0' ; force storage of at least 1 digit.
or edx,edx ; test sign of 64 bit value,
pushf ; and save sign on stack.
jns bin1 ; jump if it was positive.
not edx ; negative, take 2's complement
not eax ; of the value.
add eax,1
adc edx,0
bin1: ; divide 64 bit value by the radix
; to extract next digit for the
; forming string.
mov ebx,eax ; is the value zero yet?
or ebx,edx
jz bin3 ; yes, we are done converting.
call divide ; no, divide by radix.
add bl,'0' ; convert remainder to ASCII digit.
cmp bl,'9' ; might be converting hex ASCII,
jle bin2 ; jump if in range 0-9,
add bl,'A'-'9'-1 ; correct it if in range A-F.
bin2: mov [esi],bl ; store this character into string.
dec esi ; back up through string,
jmp bin1 ; and do it again.
bin3: ; restore sign flag,
popf ; was original value negative?
jns bin4 ; no, jump
mov byte ptr [esi],'-' ; yes,store sign into output string.
bin4: ret ; back to caller.
binasc endp
;
; General purpose 64 bit by 32 bit unsigned divide.
; This must be used instead of the plain machine unsigned divide
; for cases where the quotient may overflow 32 bits. If called with
; zero divisor, this routine returns the dividend unchanged and gives
; no warning.
;
; Call with EDX:EAX = 64 bit dividend
; ECX = divisor
;
; Returns EDX:EAX = quotient
; EBX = remainder
; ECX = divisor (unchanged)
;
divide proc near ; Divide EDX:EAX by ECX
jecxz div1 ; exit if divide by zero
push eax ; 0:dividend_upper/divisor
mov eax,edx
xor edx,edx
div ecx
mov ebx,eax ; EBX = quotient1
pop eax ; remainder1:dividend_lower/divisor
div ecx
xchg ebx,edx ; EDX:EAX = quotient1:quotient2
div1: ret ; EBX = remainder2
divide endp
pmsg proc near ; print a message on std output
; call with DS:EDX = address
; ECX = length
mov ah,40h
mov bx,stdout
int 21h
ret
pmsg endp
_TEXT ends
_DATA segment para public use32 'DATA'
flags db asize+1 dup (?)
counter dd ? ; sieve iteration counter
msg1 db cr,lf,'Starting '
msg1a db ' iterations of Sieve...',cr,lf
msg1_len equ $-msg1
msg2 db cr,lf,'Primes found: '
msg2a db ' ',cr,lf
msg2_len equ $-msg2
msg3 db cr,lf,'Elapsed time: '
msg3a db ' msec. per iteration',cr,lf
msg3_len equ $-msg3
_DATA ends
_STACK segment byte stack use32 'stack'
db 4096 dup (?)
_STACK ends
end
