;-----------------------------------------------------------------------
; 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
