This demo program finds the first n prime numbers using a fast algorithm with x86 32-bit assembly language.
This project has been tested with Visual Studio .Net 2008 (C++)
There are two constants rows (preset to 20) and cols (preset to 10) to make a tabular display. The number
of prime numbers to find is n = rows * cols (here, 200). We could modify these values to change
the tabular display rows and cols as well as the number of prime numbers
to find.
We have used the same algorithm already introduced for C++ and Java
languages. See the notes for these articles:
“Fast Algorithm to Find the First n Prime Numbers” (C++)
“Java (1) ArrayList: Fast Algorithm to Find the First n Prime Numbers”
“Java (2) Array: Fast Algorithm to Find the First n Prime Numbers”
We have used the algorithm given in the C++ version. The code given
in that article could be considered as the pseudo algorithm used to
write the equivalent assembly program.
You may download the full project source file in ZIP format from the FileFactory site:
Download Source Project
The main program for this demo is main.cpp:
// main.cpp
// The main program for fast prime algorithm
/*
This demo program finds the first n prime numbers using
a fast algorithm with x86 32-bit assembly language.
There are two constants rows (preset to 20) and cols (preset to 10)
to make a tabular display. The number of prime numbers to find is
n = rows * cols (here, 200). We could modify these values to change
the tabular display rows and cols as well as the number of prime numbers
to find.
We have used the same algorithm already introduced for C++ and Java
languages. See the notes for these articles:
"Fast Algorithm to Find the First n Prime Numbers" (C++)
Link: https://911programming.wordpress.com/2010/05/10/fast-algorithm-to-find-the-first-n-prime-numbers/
"Java (1) ArrayList: Fast Algorithm to Find the First n Prime Numbers"
Link: https://911programming.wordpress.com/2010/05/20/java-1-arraylist-fast-algorithm-to-find-the-first-n-prime-numbers/
"Java (2) Array: Fast Algorithm to Find the First n Prime Numbers"
Link: https://911programming.wordpress.com/2010/05/21/java-2-array-fast-algorithm-to-find-the-first-n-prime-numbers/
We have used the algorithm given in the C++ version. The code given
in that article could be considered as the pseudo algorithm used to
write the equivalent assembly program.
*/
#include <iostream>
using namespace std;
extern "C" int fastprime (int *, int);
int main ()
{
const int rows = 20;
const int cols = 10;
// n is automatically adjusted with rows and cols
const int n = rows * cols;
int table [n];
// Find the prime numbers.
int count = fastprime (table, n);
if (count <= 0)
{
cerr << "*** fastprime: returned unexpected value: " << count << endl;
return 1;
}
// display result in tabular format:
// for rows row
for (int i = 0; i < rows; i++)
{
// for cols column
for (int j = 0; j < cols; j++)
{
cout << table [i * cols + j] << '\t';
}
cout << "\n";
}
// print the number of prime numbers evaluated:
cout << "\nThe number of evaulated prime numbers: " << count << "\n" <<endl;
return 0;
}
The fastprime function is in the assembly file prime.asm:
; prime.asm
; The source assembly file for function fastprime.
; The code provided for assembly function fastprime
; finds (evaluates) the first n prime numbers.
; This function is meant to be linked to a C/C++.
; The C/C++ code performs the invoke or call.
; This functions uses the standard C calling convention and linkage.
; we have used a fair advantage of 32-bit memory addressing modes.
.386
.model flat, C
; Dummy!; simply a decorative declaration. Not used in this code.
public globData
.data
; Dummy!; simply a decorative global variable definition.
; Not used in this code.
globData dd 1134
; C function declaration:
; int fastprime (int * prime_table, int prime_count);
; C function paramter prime_table: array (pointer to DWORD)
; to save the evaluated prime numbers:
; It is the location in stack where this argument passed to the function.
prime_table textequ <DWORD PTR [ebp + 8]>
; C function paramter prime_count: the number of prime numbers to find.
; It is the location in stack where this argument passed to the function.
prime_count textequ <DWORD PTR [ebp + 12]>
; C function local variable: number
; declared like: int number;
; It is the location in stack where this local variable placed.
number textequ <DWORD PTR [ebp - 4]>
; C function local variable: prime_bool
; declared like: bool prime_bool;
; For simplicity, we used DWORD (Int32) to represent bool data type.
; It is the location in stack where this local variable placed.
prime_bool textequ <DWORD PTR [ebp - 8]>
; The role of registers used in this algorithm
; EAX : general purpose use. Finally, it contains the number of
; prime numbers evaluated. No need tp preseve and retrieve.
;
; EBX : The base address of the array in which the prime numbers
; are saved.
; EDX : Used in MUL and DIV operations. In DIV it contains the
; remainder of division (result of %).
; ESI : Offset to array (DWORD aligned) where the next evaluated
; prime number should be saved. It also denotes the number
; of prime numbers evaluated so far at any time.
; The return value is evantually the value of this register
; which is saved in EAX.
; EDI : When looking for a divisor, it is the offset of the next
; prime number in table (among those already evaluated) which
; is to be examined for the next number to evaluate as prime.
.code
; C function definition:
; int fastprime (int * prime_table, int prime_count);
; { //...
fastprime proc
; Complete creating high-level language stack frame.
; The first half is done by caller code, pushing function args
; into stack.
push ebp
mov ebp, esp
; Reserve space for local variables
sub esp, 8
; Preserve used registers.
push ebx
push edx
push esi
push edi
; Set the number of already evaluated prime numbers to zero.
mov esi, 0
; Check if the requested number of prime numbers is positive
mov eax, prime_count
cmp eax, 0
jle L100
; Set the base address of the array
mov ebx, prime_table
; Check if it is not NULL
cmp ebx, 0
je L100
; Set the first prime number: 2, manually
mov DWORD PTR [ebx][esi], 2
; Inc count
inc esi
; Perform the for loop for number(s).
; for number = 3
mov number, 3
jmp L4
L3:
; Step of loop: number += 2
add number, 2
L4:
; condition of loop: while (current_count < final_count)
cmp esi, prime_count
jae L100 ; if consition failed exit for loop.
; Make ready for return
; First, assume this number is prime
; prime_bool = true;
mov prime_bool, 1
; Perform the for loop for divisor(s).
; Divisor to test is picked from the prime numbers already evaluated.
; for divisor = table [0]
; that is index is set to 0
mov edi, 0
jmp L6
L5:
; Step of loop: edi++ (for table [edi])
inc edi
L6:
; loop condition: while (table [edi] * table [edi] <= number)
mov eax, [ebx][edi * 4]
mul eax
cmp eax, number
ja L7 ; if condition failed, exit for loop
; Make ready to report as prime
; Set High DWORD to 0. make ready for evaluating number % table [edi]
mov edx, 0
mov eax, number
div DWORD PTR [ebx][edi * 4]
; EDX contains the remainder, check if table [edi] is a
; divisor of number
cmp edx, 0
jne L5 ; If it is not a divisor, check next
; prime number.
; Otherwise, report it as NOT prime
mov prime_bool, 0
L7:
; the flow of program comes here in two cases:
; 1) We have found a divisor, and therefore, this number is NOT prime.
; 2) We have tested all possible prime numbers in table, and none is
; a divisor for this number. Therefore, this number is prime.
; prime_bool value denotes which one is the case:
; Check if it is 0 (false) or non-zero (true).
mov eax, prime_bool
; and instruction is the most efficient way to check it:
and eax, eax
jz L3 ; If zero (false), the number is NOT prime.
; Skip it (don't write it in table).
; Otherwise, it is a prime number; save it in table
mov eax, number
mov [ebx][esi * 4], eax
; update current count and table index;
inc esi
; Go for next number.
jmp L3
L100:
; Get ready for return:
; Set the return value (the number of prime numbers evaluated so far).
mov eax, esi
; Retrieve used registers:
pop edi
pop esi
pop edx
pop ebx
; remove / destruct high-level language stack frame.
mov esp, ebp
pop ebp
ret
fastprime endp
end
911 programming 