Assembly Language Programming

October 9, 2012

FASM – Prime Number Generator

Filed under: Assembly Language, Mathematics — Tags: , , — programmer209 @ 3:43 pm

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

; -------------------------------------------------------------------------------------
Advertisements

Create a free website or blog at WordPress.com.

%d bloggers like this: