links

< home >
< unix stuff >
< code >
< writing >
< archive >
< music >
< photos >
< recipes >
< site map >
< about badcomputer >

sieve of eratosthenes

X86 Assembly

; Sieve of Eratosthenes in x86 assembly for Linux (NASM)
; Written by Robert Hoelz

; To assemble:
;   nasm -f elf sieve.s
;   ld -o sieve -s sieve.o

; Right now this program can only generate primes up to
; 1 million; if you want to use a higher limit, adjust
; max_primes accordingly.

; This implementation uses an array of bytes with no special
; bitwise arithmetic to conserve space.

section .data
    space:      db      ' '
    nl:         db 10
    sieves:     dw 0
section .bss
    int_string: resb 20

section .text

strlen:
    push    ebp
    mov     ebp, esp
    push    ebx
    push    ecx

    mov     ebx, [ebp+8]
    mov     eax, 0

__strlen_loop:
    movzx   ecx, byte [ebx]
    cmp     ecx, 0
    je      __strlen_loop_end

    inc     eax
    inc     ebx
    jmp     __strlen_loop
__strlen_loop_end:

    pop     ecx
    pop     ebx
    leave
    ret

; End strlen

atoi:
    push    ebp
    mov     ebp, esp
    push    ebx
    push    ecx
    push    esi
    push    edi

    mov     ebx, [ebp+8]
    mov     eax, 0
    mov     edx, 0

__atoi_loop:
    movzx   ecx, byte [ebx]
    cmp     ecx, 0
    je      __atoi_loop_end

    mov     ecx, 10

    mov     esi, eax
    mov     eax, edx
    mul     ecx
    mov     edi, eax
    mov     eax, esi
    mul     ecx
    add     edx, edi

    movzx   ecx, byte [ebx]
    sub     ecx, 0x30
    add     eax, ecx
    adc     edx, 0

    inc     ebx
    jmp     __atoi_loop
__atoi_loop_end:

    pop     edi
    pop     esi
    pop     ecx
    pop     ebx
    leave
    ret

; End atoi

print:
    push    ebp
    mov     ebp, esp
    push    eax
    push    ebx
    push    ecx
    push    edx

    push    dword [ebp+8]
    call    strlen
    pop     edx

    mov     edx, eax
    mov     eax, 4
    mov     ebx, 1
    mov     ecx, [ebp+8]
    int     0x80

    mov     eax, 4
    mov     ecx, space
    mov     edx, 1
    int     0x80

    pop     edx
    pop     ecx
    pop     ebx
    pop     eax
    leave
    ret

; End print

print_int:
    push    ebp
    mov     ebp, esp
    push    eax
    push    ebx
    push    ecx
    push    edx
    push    esi

    mov     eax, [ebp+8]
    mov     ebx, int_string
    add     ebx, 19
    mov     ecx, 0

__print_int_loop:
    mov     esi, 10
    mov     edx, 0

    div     esi
    add     edx, 48
    mov     [ebx+ecx], dl

    dec     ecx
    cmp     eax, 0
    jne     __print_int_loop

    mov     eax, int_string

__print_int_reverse:
    mov     dl, [ebx+ecx+1]
    mov     [eax], dl

    inc     eax
    inc     ecx

    cmp     ecx, 0
    jne     __print_int_reverse

    mov     [eax], byte 0
    sub     ebx, 19

    push    ebx
    call    print
    pop     ebx

    pop     esi
    pop     edx
    pop     ecx
    pop     ebx
    pop     eax

    leave
    ret
; End print_int

allocate:
    push    ebp
    mov     ebp, esp
    push    eax
    push    ebx

    mov     eax, 45
    mov     ebx, 0
    int     0x80

    mov     ebx, sieves
    mov     [ebx], eax
    mov     ebx, [ebp+8]
    add     ebx, eax
    mov     eax, 45
    int     0x80

    pop     ebx
    pop     eax
    leave
    ret

; End allocate

init_sieves:
    push    ebp
    mov     ebp, esp
    push    eax
    push    ebx
    push    ecx

    mov     eax, sieves
    mov     ebx, [eax]
    mov     eax, [ebp+8]
    mov     ecx, 2

    mov     dword [ebx], 0
    mov     dword [ebx+1], 0

__init_sieves_loop:
    cmp     ecx, eax
    jg      __init_sieves_end_loop

    mov     dword [ebx+ecx], 1

    inc     ecx
    jmp     __init_sieves_loop
__init_sieves_end_loop:

    pop     ecx
    pop     ebx
    pop     eax
    leave
    ret

; End init_sieves

print_primes:
    push    ebp
    mov     ebp, esp
    push    eax
    push    ebx
    push    ecx
    push    edx

    mov     eax, sieves
    mov     ebx, [eax]
    mov     eax, [ebp+8]
    mov     ecx, 0

__print_primes_loop:
    cmp     ecx, eax
    jg      __print_primes_end_loop

    movzx   edx, byte [ebx+ecx]
    cmp     edx, 0
    je      __dont_print

    push    ecx
    call    print_int
    pop     ecx
__dont_print:

    inc     ecx
    jmp     __print_primes_loop
__print_primes_end_loop:

    mov     eax, 4
    mov     ebx, 1
    mov     ecx, nl
    mov     edx, 1
    int     0x80

    pop     edx
    pop     ecx
    pop     ebx
    pop     eax
    leave
    ret

; End print_primes

generate_primes:
    push    ebp
    mov     ebp, esp
    push    eax
    push    ebx
    push    ecx
    push    edx

    mov     eax, [ebp+8]
    mov     ebx, 2

__generate_primes_loop:
    push    eax
    push    ebx

    call    remove_multiples
    call    next_prime

    pop     ebx
    mov     ebx, eax
    mul     eax

    cmp     edx, 0
    jne     __generate_primes_loop_end
    mov     edx, eax
    pop     eax
    cmp     edx, eax
    jg      __generate_primes_loop_end

    jmp     __generate_primes_loop
__generate_primes_loop_end:

    pop     edx
    pop     ecx
    pop     ebx
    pop     eax
    leave
    ret
; End generate_primes

remove_multiples:
    push    ebp
    mov     ebp, esp
    push    eax
    push    ebx
    push    ecx
    push    edx

    mov     eax, sieves
    mov     ecx, [eax]
    mov     eax, [ebp+12]
    mov     ebx, [ebp+8]
    mov     edx, ebx
    add     ebx, ebx

__remove_multiples_loop:
    mov     [ecx+ebx], byte 0
    add     ebx, edx
    cmp     ebx, eax
    jle     __remove_multiples_loop

    pop     edx
    pop     ecx
    pop     ebx
    pop     eax
    leave
    ret
; End remove_multiples

next_prime:
    push    ebp
    mov     ebp, esp
    push    ebx
    push    ecx

    mov     eax, sieves
    mov     ecx, [eax]
    mov     eax, [ebp+12]
    mov     ebx, [ebp+8]
    inc     ebx

__next_prime_loop:
    cmp     ebx, eax
    jge     __next_prime_loop_end

    cmp     [ecx+ebx], byte 1
    je      __next_prime_loop_end

    inc     ebx
    jmp     __next_prime_loop
__next_prime_loop_end:
    mov     eax, ebx

    pop     ecx
    pop     ebx
    leave
    ret
; End next_prime

global _start
_start:
    mov     eax, [esp]
    cmp     eax, 1
    je      __exit

    push    dword [esp+8]
    call    atoi
    pop     ebx

    push    eax
    call    allocate
    call    init_sieves
    call    generate_primes
    call    print_primes
    pop     eax

__exit:
    mov     eax, 1
    mov     ebx, 0
    int     0x80
; End _start

back to Eratosthenes page

stats

It is Monday September 08, 2008 1:24 am
This page served 730 times
This page last modified: April 14, 2008 11:28 am
Your IP address is: 38.103.63.61
You are browsing using: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)
You are browsing from: United States.
badcomputer.org's uptime: 01:24:44 up 39 days, 16:31, 2 users, load average: 0.10, 0.04, 0.01