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 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
push edx
mov eax, [ebp+8]
mov edx, 0
mov ebx, 8
div ebx
inc eax
mov edx, eax
mov eax, 45
mov ebx, 0
int 0x80
mov ebx, sieves
mov [ebx], eax
mov ebx, edx
add ebx, eax
mov eax, 45
int 0x80
pop edx
pop ebx
pop eax
leave
ret
; End allocate
init_sieves:
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, 8
mov edx, 1
mov [ebx], byte 0x3f
__init_loop:
cmp ecx, eax
jg __init_loop_end
mov [ebx+edx], byte 0xff
inc edx
add ecx, 8
jmp __init_loop
__init_loop_end:
pop edx
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
push esi
push edi
mov ebx, 0 ; Current byte
mov ecx, 7 ; Current bit
mov esi, 0 ; Current index
mov eax, sieves
mov edi, [eax] ; Sieves
mov edx, [ebp+8] ; Limit
__print_prime_loop:
cmp esi, edx
jg __print_prime_end
mov eax, [edi+ebx]
sar eax, cl
and eax, 1
cmp eax, 1
jne __dont_print
push esi
call print_int
pop esi
__dont_print:
; Increment
inc esi
dec ecx
cmp ecx, -1
jne __print_prime_loop
mov ecx, 7
inc ebx
jmp __print_prime_loop
__print_prime_end:
mov eax, 4
mov ebx, 1
mov ecx, nl
mov edx, 1
int 0x80
pop edi
pop esi
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
push esi
push edi
mov eax, sieves
mov ebx, [eax]
mov esi, [ebp+8]
add esi, esi
__remove_multiples_loop:
cmp esi, [ebp+12]
jg __remove_multiples_end
mov eax, esi
mov ecx, 8
mov edx, 0
div ecx
mov ecx, edx
movzx edx, byte [ebx+eax]
mov edi, 0x80
sar edi, cl
not edi
and edx, edi
mov [ebx+eax], dl
add esi, [ebp+8]
jmp __remove_multiples_loop
__remove_multiples_end:
pop edi
pop esi
pop edx
pop ecx
pop ebx
pop eax
leave
ret
; End remove_multiples
next_prime:
push ebp
mov ebp, esp
push ebx
push ecx
push edx
push esi
push edi
mov esi, [ebp+8]
mov eax, sieves
mov edi, [eax]
mov edx, 0
mov eax, esi
mov ebx, 8
div ebx
mov ebx, eax
mov ecx, edx
mov edx, [ebp+12]
inc esi
inc ecx
cmp ecx, 8
jne __next_prime_loop
mov ecx, 0
inc ebx
__next_prime_loop:
cmp esi, edx
jg __print_prime_end
mov eax, 0x80
sar eax, cl
and eax, [edi+ebx]
cmp eax, 0
jne __next_prime_end
inc esi
inc ecx
cmp ecx, 8
jne __next_prime_loop
mov ecx, 0
inc ebx
jmp __next_prime_loop
__next_prime_end:
mov eax, esi
pop edi
pop esi
pop edx
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
stats
It is
Saturday May 17, 2008 10:54 am
This page served 575 times
This page last modified: April 14, 2008 11:28 am
Your IP address is: 38.103.63.17
You are browsing using: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)
You are browsing from: United States.
badcomputer.org's uptime: 10:54:39 up 23 days, 11:36, 0 users, load average: 0.00, 0.00, 0.00
local
home | unix stuff | dir2ogg | sneetchalizer | wmainfo | q&d guide to permissions | q&d guide to tar and gzip | code | MS rant | browser shootout | linux & iAudio X5 | photos | music | programming poetry | sieve of Eratosthenes | plea | rain | suffer | archive | about | recipes | compaqr3000 | sitemap
search
credits
This page, and all pages on this site were created and are maintained by Darren Kirby using valid XHTML 1.0 and CSS, and are ©copyright 2002 - 2008. The Penguin image was created by Tukka, and is used by permission. Inspiration for the look of this site was provided by Eric A. Meyer's CSS gallery. This website runs on Gentoo Linux. It is served by Apache. PHP and MySQL hold together the backend.