This x86 assembly language program uses the Sieve of Eratosthenes to generate a list of all the prime numbers starting from 3 that are less than 65536. It was written using FASM – the Flat Assembler.
The algorithm used by the program is as follows:
- An array of 4096 bytes is used to represent all of the odd numbers from 1 to 65535. - Each bit in the array represents an odd number. - The bits in the array are indexed from 0 up to 32767. - The numerical value associated with each bit is calculated as: number = 1 + (2 x bit_index) - All of the bits in the array are initialised to 0. - Then the first bit in the array (representing the number 1) is set to 1. - Each subsequent bit in the array represents a potential prime number p. - For each p, all of the bits that represent multiples of p (2p, 3p, 4p etc) are set to 1. - At the end of the process, those bits which are still 0 represent prime numbers. - Pseudo-code: for(bit_index = 1 up to bit_index = 32767) { p = 1 + (2 x bit_index) composite = 2 x p while(composite is less than 65536) { set_bit(composite) composite += p } } |
The x86 Source Code
; ------------------------------------------------------------------------------------- format PE GUI 4.0 entry start include 'win32a.inc' ; ------------------------------------------------------------------------------------- IDD_THE_DIALOG = 102 IDC_OUTPUT = 1000 IDC_BTN_CALC = 1001 IDC_BTN_RESET = 1002 ; ------------------------------------------------------------------------------------- section '.code' code readable executable start: invoke GetModuleHandle,0 invoke DialogBoxParam,eax,IDD_THE_DIALOG,0,DialogProc,0 exit: invoke ExitProcess,0 ; ------------------------------------------------------------------------------------- proc DialogProc uses esi edi ebx,hwnddlg,msg,wparam,lparam cmp [msg],WM_INITDIALOG je .wminitdialog cmp [msg],WM_COMMAND je .wmcommand cmp [msg],WM_CLOSE je .wmclose xor eax,eax jmp .quit .wminitdialog: invoke SetDlgItemText,[hwnddlg],IDC_OUTPUT,"" jmp .done .wmcommand: cmp [wparam], BN_CLICKED shl 16 + IDC_BTN_CALC je .CALC cmp [wparam], BN_CLICKED shl 16 + IDC_BTN_RESET je .RESET jmp .done .CALC: stdcall CalcSieve stdcall PrintPrimes invoke SetDlgItemText,[hwnddlg],IDC_OUTPUT,bfDisplay jmp .done .RESET: invoke SetDlgItemText,[hwnddlg],IDC_OUTPUT,"" jmp .done .wmclose: invoke EndDialog,[hwnddlg],0 .done: mov eax,1 .quit: ret endp ; ------------------------------------------------------------------------------------- proc CalcSieve uses esi edi ebx ecx ; generate the prime number sieve lea esi,[FactorBase] lea edi,[FactorBase] xor ecx,ecx .CLEAR: mov [edi+ecx],byte 0 inc cx cmp cx,4096 jl .CLEAR ; Factor Base array: 4096 bytes = 32768 bits ; all the odd numbers from 1 to 65535 ; bit_index = 0 to 32767 ; 1 at bit_index 0 divides everything: mov [edi],byte 1 ; EBX = bit_index ; number = 1 + (2 x bit_index) xor ebx,ebx ; start at bit_index = 1 (3) inc ebx .SIEVE: mov edx,ebx ; EAX = 1 + (bit_index x 2) mov eax,ebx shl eax,1 inc eax .SET_1: ; mark as composite by setting the bit to 1 add edx,eax cmp edx,32767 jg .NEXT ; EDX gives the bit index, set the bit at this index to 1 ; get the byte index mov ecx,edx shr ecx,3 mov edi,esi add edi,ecx ; get the bit index mov ecx,edx and ecx,7 mov ch,1 shl ch,cl ; set the bit or [edi],ch jmp .SET_1 .NEXT: inc ebx cmp ebx,32767 jl .SIEVE ret endp ; ------------------------------------------------------------------------------------- proc PrintPrimes uses esi edi ecx ; identify all of the numbers in FactorBase that are prime and print them locals bit db 0 bit_index dw 0 endl lea esi,[FactorBase] lea edi,[bfDisplay] xor ecx,ecx .NEXT: ; get the byte mov dl,[esi+ecx] .PRINT: ; test each bit in the byte shr dl,1 jc .NEXT_BIT ; the bit is 0, so print the number ; number = 1 + (2 x bit_index) xor eax,eax mov ax,[bit_index] shl eax,1 inc eax ; print as a decimal number stdcall HexToDec .NEXT_BIT: ; get the next bit inc word [bit_index] inc byte [bit] cmp [bit],8 jl .PRINT .NEXT_BYTE: mov [bit],byte 0 inc cx cmp cx,4096 jl .NEXT .DONE: mov [edi],byte 0 ret endp ; ------------------------------------------------------------------------------------- proc HexToDec uses ecx edx ; convert the hex number in AX to a decimal string ; EDI is the destination string ; EDI is set outside of this procedure locals power db 4 digit db 0 endl ; the largest number that AX can hold is 65536 ; so start with 10 to the power of 4 .CONVERT: xor cx,cx mov cl,[power] stdcall Power_of_Ten mov [digit],byte 0 .SUB: ; subtract powers of ten to get the left most decimal digit cmp eax,edx jl .NEXT sub eax,edx inc [digit] jmp .SUB .NEXT: ; add the digit to the output string mov bl,[digit] mov [edi],bl add [edi],byte 48 inc edi dec [power] cmp [power],0 jge .CONVERT mov [edi],byte 32 inc edi ret endp ; ------------------------------------------------------------------------------------- proc Power_of_Ten ; the power of ten is in CL mov edx,1 .x10: cmp cx,0 je .DONE ; multiply EDX by 10 mov ebx,edx shl edx,3 shl ebx,1 add edx,ebx dec cx jmp .x10 .DONE: ret endp ; ------------------------------------------------------------------------------------- section '.idata' import data readable writeable library kernel,'KERNEL32.DLL',\ user,'USER32.DLL' import kernel,\ GetModuleHandle,'GetModuleHandleA',\ ExitProcess,'ExitProcess' import user,\ DialogBoxParam,'DialogBoxParamA',\ SetDlgItemText,'SetDlgItemTextA',\ EndDialog,'EndDialog' ; ------------------------------------------------------------------------------------- section '.data' readable writeable bfDisplay rb 64000 FactorBase rb 4096 ; ------------------------------------------------------------------------------------- section '.rc' resource data readable directory RT_DIALOG,dialogs resource dialogs,IDD_THE_DIALOG,LANG_ENGLISH+SUBLANG_DEFAULT,the_dialog dialog the_dialog,\ 'Prime Number Sieve',50,50,360,396,\ DS_MODALFRAME+WS_MINIMIZEBOX+WS_POPUP+WS_VISIBLE+WS_CAPTION+WS_SYSMENU,\ 0,0,"Lucida Console",11 dialogitem 'BUTTON',"Output",-1,7,7,346,360,BS_GROUPBOX+WS_VISIBLE,0 dialogitem 'EDIT',0,IDC_OUTPUT,13,18,335,340,ES_MULTILINE+ES_AUTOVSCROLL+ES_WANTRETURN+WS_VSCROLL+WS_BORDER+WS_VISIBLE,0 dialogitem 'BUTTON',"CALC",IDC_BTN_CALC,7,375,80,14,BS_PUSHBUTTON+WS_VISIBLE,0 dialogitem 'BUTTON',"RESET",IDC_BTN_RESET,89,375,80,14,BS_PUSHBUTTON+WS_VISIBLE,0 enddialog ; ------------------------------------------------------------------------------------- |