Power-Programmierung/CD1.mdf/assemblr/library/sampler0/sieve386.asm

Assembly Source File | 1987-04-03 | 6.5 KB | 261 lines

    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