A Sieve of Eratosthenes in Assembler

I wrote a short program in assembler, using Turbo Macro Pro, to implement a Sieve of Eratosthenes to find the 8 bit prime numbers.

Right click here to download the disk image:  tmpsieve

Here is the screenshot:

The ML program places a basic program in memory that is just:

10 SYS 4096

So, once SIEVE is loaded, (LOAD “SIEVE”,8,1), all one has to do is type RUN to run the sieve.

chrout   = $ffd2

sieve    = $0900   ; 8 bit sieve

         *= $0800

    ;the 00 byte that starts basic

         .byte $00

    ; pointer to the next basic line
    ; which is at $080c
         .byte $0c,$08

    ; line 10
         .byte $0a,$00

    ; the basic token for sys
         .byte $9e

    ; a space
         .byte $20

    ; "4096"
         .byte $34,$30,$39,$36

    ; 00 for the end of the basic line
         .byte $00

    ; 00 00 for the end of the basic
    ; program
         .byte $00,$00

w1       = $0880; working variable
w2       = $0881; working variable
w3       = $0882; working variable
w4       = $0883; working variable
w5       = $0884; working variable
hx       = $0885; holder for x
hy       = $0886; holder for y
hdig     = $0887; hundreds digit
tdig     = $0888; tens digit
odig     = $0889; ones digit

head     = $0890  ; header

    ; this is the header
    ; it is 68 bytes

         *= $0890
         .byte $93,$20,$20,$20

         .byte $20,$20,$20,$20

         .byte $20,$45,$49,$47

         .byte $48,$54,$20,$42

         .byte $49,$54,$20,$50

         .byte $52,$49,$4d,$45

         .byte $20,$4e,$55,$4d

         .byte $42,$45,$52,$53

         .byte $0d,$20,$20,$20

         .byte $20,$20,$20,$20

         .byte $42,$59,$20,$41

         .byte $20,$53,$49,$45

         .byte $56,$45,$20,$4f

         .byte $46,$20,$45,$52

         .byte $41,$54,$4f,$53

         .byte $54,$48,$45,$4e

         .byte $45,$53,$0d,$0d

         *= $1000

         jmp main

mult10   ; multiply by 10 subroutine

         asl a
         sta w1
         asl a
         asl a
         adc w1

    ; now, in order to output base-10
    ; values to the screen we need
    ; to get a char which represents
    ; each digit in the base-10
    ; representation of the 8-bit
    ; number to be output

    ; we will store the hundreds place
    ; digit in hdig, the tens plae
    ; digit in tdig, and the ones
    ; place digit in odig

    ; get hundreds digit subroutine


         cmp #$c8  ; is a gt 200?
         bcc hless200
         ldx #$02  ; if here, hdig is
         stx hdig  ; 2 so store it
         sbc #$c8  ; subtract 200 from
         rts       ; a and return

         cmp #$64  ; is a gt 100?
         bcc hless100
         ldx #$01  ; if here, hdig is
         stx hdig  ; 1 so store it
         sbc #$64  ; subtract 100 from
         rts       ; a and return

         ldx #$00  ; if here, hdig is
         stx hdig  ; 0 so store it

    ; when this sub is run, a is 0-99

    ; start by putting a 9 in x,
    ; multiplying that by 10, then
    ; seeing if 90 is higher than the
    ; test number - if not, tdig is 9,
    ; and so on

         sta w2; preserve a
         ldx #$09

         jsr mult10
         sta w3; w3 = 90,80,70,etc

         lda w2
         cmp w3
         bcc tennotfound
         txa  ; we hav found our ten
         sta tdig
         lda w2
         sbc w3
         rts  ; we've found the digit,
              ; and left the ones place
              ; in a - so return

         dex  ; try the next lower
         bne tryaten
         ldy #$00; if here, tdig=0
         sty tdig
         lda w2

         sta odig; by this time, the
              ; ones digit is all that
              ; is left in a

         jsr gethundig
         jsr gettendig
         jsr getonedig

         jsr getdigs
         lda hdig
         ora #$30; convert to ascii
         jsr chrout
         lda tdig
         ora #$30
         jsr chrout
         lda odig
         ora #$30
         jsr chrout
         lda #$20; two spaces
         jsr chrout
         jsr chrout

         ldx #$00; use x to index loop1
         lda #$01
         sta sieve,x; fill the sieve wit
         bne loop1

         lda #$00
         ldx #$00
         sta sieve,x; 0 is not prime
         sta sieve,x; 1 is not prime

    ; w1 is counter as we step
    ; w2 is step size
         lda #$01
         sta w1
         sta w2


         inc w2; if we are on first pass
           ; through sieve, we just
           ; increased step from 1 to 2
           ; which is what we want

         lda w2; the step size is also
           ; the first element in
           ; any pass
         sta w1

         cmp #$10; have we reached 16?
               ; if so, we ar done
         bne not16

         ldx w2
         lda sieve,x; does x point to a
                 ; zero in the sieve?
         beq nextpass ; ifso x composite
                      ; so move on


         lda w1
         beq nextpass; we've stepped all
                 ; the way through
                 ; sieve so increase
                 ; step

         lda w1
         adc w2  ; add the step
         bcs nextpass; if the carry flag
                 ; is set we're past
                 ; the end of the
                 ; sieve so nextpass

         sta w1
         tax     ; update x pointer

         lda #$00
         sta sieve,x; x not prime so
                 ; mark with a zero
         jmp nextstep

         ldx #$00
         lda head,x
         jsr chrout
         cpx #$44
         bne phloop

         jsr dosieve
         jsr printheader

    ;sieve now marks primes
    ;with a 1 - step and
    ;print primes

         ldy #$00
         sty w5; w5 is primes on
           ; this current line


         lda sieve,y
         beq movetonext
         stx hx
         sty hy
         jsr printdigs
         ldy hy
         ldx hx

         inc w5
         lda w5
         cmp #$08; end of line?
         bne movetonext
         lda #$0d
         jsr chrout
         lda #$00
         sta w5; reset line index

         bne probesieve
         lda #$0d
         jsr chrout
         jsr chrout


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s