Sieve of Eratosthenes:
Algorithm for finding all prime numbers up to MAX LIMIT (2^32 - 1). (ASM implementation).
Reference:
http://www.algorithmist.com/index.php/Prime_Sieve_of_Eratosthenes.cppReference for Integer sqroot:
http://www.azillionmonkeys.com/qed/sqroot.htmlUsage : Sieve <integer>
eg:
C:\NASM> Sieve 13
2
3
5
7
11
13
Number of Primes = 6
;;;;C++ Version for Reference
;;;;http://www.algorithmist.com/index.php/Prime_Sieve_of_Eratosthenes.cpp
;;;;#include <cmath>
;;;;#include <vector>
;;;;
;;;;/*primes is a list of primes, n is all the primes you want to generate.. from 2 to n*/
;;;;void genPrimes(vector<int>&primes,int n){
;;;; for(int i=2;i<=n;i++){
;;;; int root=int(sqrt(i))+1; /*remember the square root*/
;;;; bool found=false; /*prime found?*/
;;;; for(vector<int>::const_iterator it = primes.begin();it!=primes.end()&& *it<root;it++){
;;;; if(i% *it==0){found=true;break;} /*this is not prime*/
;;;; }
;;;; if(!found)primes.push_back(i); /*this is a prime*/
;;;; }
;;;;}
;;;; Reference for isqrt
;;;; http://www.azillionmonkeys.com/qed/sqroot.html
;;;;*********************
;;;;Assemble with :
;;;;nasm -fobj Sieve.asm
;;;;Link with
;;;;alink -c -oPE -subsys con Sieve
;;;;Usage eg: Sieve 2000
;;;;*********************
%include "win32n.inc"
;;================================
;; MACRO str2int int2str by Written by mastercpp.
;;================================
%macro str2int 1
push ebx ;
push esi ;
push edi ;
mov ebx, 0
mov ecx, 0
xor eax,eax
mov ebx,0000000Ah
mov esi, %1
%%ConvertLoop:
movzx ecx,byte [esi] ;Zeichen laden.
test ecx,ecx
jz short %%ExitConvertLoop ;0 => Exit
inc esi
sub cl,30h ;0-9...
mul ebx ;Ergebnis * 10
add eax,ecx ;+ nächste Ziffer
jmp short %%ConvertLoop
%%ExitConvertLoop:
pop edi
pop esi
pop ebx
%endmacro
%macro int2str 2
push ebx ;
push esi ;
push edi ;
%%start:
mov eax, %1
xor ecx, ecx
mov ebx, 000ah
%%DecConvert:
xor edx, edx
div ebx
add edx, 0030h
push edx
inc ecx
or eax, eax
jnz short %%DecConvert
mov edi, %2
mov edx,ecx
%%SortDec:
pop eax
stosb
loop %%SortDec
mov eax, 0h
stosb
pop edi
pop esi
pop ebx
%endmacro
;;================================
;; mastercpp end macros
;;================================
extern GlobalAlloc
import GlobalAlloc kernel32.dll
extern GlobalFree
import GlobalFree kernel32.dll
extern ExitProcess
import ExitProcess kernel32.dll
extern GetStdHandle
import GetStdHandle kernel32.dll
extern WriteFile
import WriteFile kernel32.dll
extern GetCommandLineA
import GetCommandLineA kernel32.dll
global ..start
segment .bss USE32
buffer resb 32
segment .data USE32
PrimeListHdl dd 0;
Root dd 0;
FoundFactor dd 0
input1 db "1000",0
value dd 0
consolehdl dd 0
byteswritten dd 0
noofprimes dd 0
newline db 10
newlineLEN equ 1
message1 db "Number of Primes = "
MSG1_LEN equ $-message1
message2 db "Usage : Sieve <integer> ",13,10,"MAX 2^32 - 1 ",13,10
MSG2_LEN equ $-message2
segment .code USE32 class=code
..start:
; hStdOut = GetstdHandle( STD_OUTPUT_HANDLE)
push dword STD_OUTPUT_HANDLE
call [GetStdHandle]
mov [consolehdl], eax
;; Command line parsing - START
call [GetCommandLineA]
mov esi,eax
NextChar:
lodsb
cmp al,' '
jnz CheckNull
jmp SkipSpaces
CheckNull:
cmp al,0
jnz NextChar
;;; No Parameter - print usage text
push dword 0
push dword byteswritten
push MSG2_LEN
push dword message2
push dword [consolehdl]
call [WriteFile]
push dword 0
call [ExitProcess]
SkipSpaces:
lodsb
cmp al,' '
jz SkipSpaces
dec esi
;; Command line parsing - END
str2int esi
mov [value],eax
push eax
call IntegerLn ;;calculate Integer Logarithm.
add esp,4
mov ebx,eax
mov eax, 2
test ebx,ebx
jz AllocateMemory
xor edx,edx
mov eax,[value]
div ebx ;;; EAX stores the quotient of N/Ln(N)
AllocateMemory:
shl eax,1 ;;;Multiply by 2. Just to make sure we have enough memory
imul eax,4 ;;; N number of DWORDS
push eax
push dword GPTR
call [GlobalAlloc]
mov [PrimeListHdl],eax
mov edi,eax
mov ecx,2
StartDivisorLoop:
cmp ecx,[value]
jg ExitDivisorsLoop
push edi ;;; Save EDI
push ecx ;;; Save ECX
mov eax,ecx
push eax
call IntegerSqrt
add esp,4
inc eax
mov [Root],eax
mov dword[FoundFactor],0
pop ecx ;;; Restore ECX
pop edi
mov esi,[PrimeListHdl]
StartInnerLoop:
lodsd
test eax,eax
jnz CheckLessThanRoot
jmp CheckFoundFactor
CheckLessThanRoot:
cmp eax,[Root]
jge CheckFoundFactor
push ecx
xchg eax,ecx
xor edx,edx
div ecx
pop ecx
test edx,edx
jnz NotFactor
mov dword[FoundFactor],1
jmp CheckFoundFactor
NotFactor:
jmp StartInnerLoop
CheckFoundFactor:
cmp dword[FoundFactor],1
jz NotPrime
mov eax,ecx
stosd
NotPrime:
inc ecx
jmp StartDivisorLoop
ExitDivisorsLoop:
mov eax,0
stosd
mov esi,[PrimeListHdl]
xor ebx,ebx
PrintLoop:
lodsd
test eax,eax
jz ExitOut
int2str eax,buffer
pusha
; WriteFile( hstdOut, message, length(message), &bytes, 0);
push dword 0
push dword byteswritten
push edx
push buffer
push dword [consolehdl]
call [WriteFile]
; WriteFile( hstdOut, "\n", 2, &bytes, 0);
push dword 0
push dword byteswritten
push dword 1
push newline
push dword [consolehdl]
call [WriteFile]
popa
inc ebx
jmp PrintLoop
ExitOut:
mov [noofprimes],ebx
push dword 0
push dword byteswritten
push MSG1_LEN
push message1
push dword [consolehdl]
call [WriteFile]
int2str [noofprimes],buffer
push dword 0
push dword byteswritten
push edx
push buffer
push dword [consolehdl]
call [WriteFile]
push dword [PrimeListHdl]
call [GlobalFree]
push dword 0
call [ExitProcess]
IntegerLn:
push ebp
mov ebp,esp
xor ecx,ecx
mov eax,[ebp+8]
DivideBy2:
shr eax,1
test eax,eax
jz IntegerLn_exit
inc ecx
jmp DivideBy2
IntegerLn_exit:
mov eax,ecx
leave
ret
IntegerSqrt:
push ebp
mov ebp,esp
xor edi,edi
mov ebx,0x8000
mov ecx,15
startloop:
mov esi,edi
shl esi,1
mov edx,esi
add edx,ebx
shl edx,cl
dec ecx
cmp eax,edx
jl shiftrightb
add edi,ebx
sub eax,edx
shiftrightb:
shr ebx,1
cmp ebx,0
jg startloop
mov eax,edi
leave
ret
I have attached a version using nagoa macros too.
