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
    ;[clr][sp][sp][sp]
         .byte $93,$20,$20,$20

    ;[sp][sp][sp][sp]
         .byte $20,$20,$20,$20

    ;[sp]eig
         .byte $20,$45,$49,$47

    ;ht[sp]b
         .byte $48,$54,$20,$42

    ;it[sp]p
         .byte $49,$54,$20,$50

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

    ;[sp]num
         .byte $20,$4e,$55,$4d

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

    ;[cr][sp][sp][sp]
         .byte $0d,$20,$20,$20

    ;[sp][sp][sp][sp]
         .byte $20,$20,$20,$20

    ;by[sp]a
         .byte $42,$59,$20,$41

    ;[sp]sie
         .byte $20,$53,$49,$45

    ;ve[sp]o
         .byte $56,$45,$20,$4f

    ;f[sp]er
         .byte $46,$20,$45,$52

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

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

    ;es[cr][cr]
         .byte $45,$53,$0d,$0d


         *= $1000

         jmp main

mult10   ; multiply by 10 subroutine

         asl a
         sta w1
         asl a
         asl a
         adc w1
         rts

    ; 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

gethundig

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

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

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

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

tryaten
         txa
         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
         sec
         sbc w3
         rts  ; we've found the digit,
              ; and left the ones place
              ; in a - so return

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

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

getdigs
         jsr gethundig
         jsr gettendig
         jsr getonedig
         rts

printdigs
         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
         rts

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

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

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

nextpass

         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
         rts

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

nextstep

         lda w1
         txa
         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


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

main
         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

probesieve

         lda sieve,y
         beq movetonext
         tya
         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

movetonext
         iny
         bne probesieve
         lda #$0d
         jsr chrout
         jsr chrout
         rts

 

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