Assembly Language Programming

October 21, 2012

FASM – Prime Number Tester

This program uses Fermats Primality Test to test whether an input number is prime or not. It was written in x86 assembly language using the Flat Assembler (FASM).

Fermats Primality Test

For a number p to be considered prime, it must pass the following tests for some integer a:

GCD(a,p) = 1

ap-1 mod p = 1

This test is not perfect. So called base-a pseudoprimes will pass for certain values of a. However these values are rare and can be eliminated by testing against multiple values of a. There is also a class of numbers known as Carmichael Numbers which are not prime, but which will pass the above tests for all possible values of a. However, the probability of encountering Carmichael Numbers is very low.

Usage

Enter the value to be tested in either decimal or hexadecimal form. Then press the [Test Decimal] or [Test Hexadecimal] button. These buttons can be pressed multiple times for the same input to test against multiple values of a.

The x86 Source Code

To grab this code, select it with the mouse and copy it. It can then be pasted directly into the FASM IDE.

; -------------------------------------------------------------------------------------

 format PE GUI 4.0

 entry start

 include 'win32a.inc'

; -------------------------------------------------------------------------------------

 IDD_THE_DIALOG = 102

 IDC_INPUT = 1000
 IDC_OUTPUT = 1001

 IDC_BTN_TEST_DEC = 1002
 IDC_BTN_TEST_HEX = 1003

; -------------------------------------------------------------------------------------

 HEX_LEN = 400

 DBL_HEX_LEN = 2*HEX_LEN

; -------------------------------------------------------------------------------------

 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_INPUT,""
	invoke SetDlgItemText,[hwnddlg],IDC_OUTPUT,""

	jmp .done

  .wmcommand:

	cmp [wparam], BN_CLICKED shl 16 + IDC_BTN_TEST_DEC
	je .TEST_DEC

	cmp [wparam], BN_CLICKED shl 16 + IDC_BTN_TEST_HEX
	je .TEST_HEX

    jmp .done

  .TEST_DEC:

	invoke GetDlgItemText,[hwnddlg],IDC_INPUT,bfDisplay,1200

	stdcall GetTestPrimeDecimal

	invoke SetDlgItemText,[hwnddlg],IDC_INPUT,bfDisplay

	stdcall Test_Prime

	stdcall PrintResult

	invoke SetDlgItemText,[hwnddlg],IDC_OUTPUT,bfDisplay

	jmp .done

  .TEST_HEX:

	invoke GetDlgItemText,[hwnddlg],IDC_INPUT,bfDisplay,1200

	stdcall GetTestPrime

	stdcall PrintTestPrime

	invoke SetDlgItemText,[hwnddlg],IDC_INPUT,bfDisplay

	stdcall Test_Prime

	stdcall PrintResult

	invoke SetDlgItemText,[hwnddlg],IDC_OUTPUT,bfDisplay

	jmp .done

  .wmclose:

	invoke EndDialog,[hwnddlg],0

  .done:

	mov eax,1

  .quit:

	ret

endp

; -------------------------------------------------------------------------------------

macro PRINT_CRLF
{
  mov [edi],byte 13
  inc edi

  mov [edi],byte 10
  inc edi
}

; -------------------------------------------------------------------------------------

proc GetTestPrime

  ; get the input value

	stdcall FilterNonHex

	stdcall HexStrToNumber

	ret

endp

; -------------------------------------------------------------------------------------

proc GetTestPrimeDecimal

  ; get the decimal input value

	stdcall FilterNonDec

	stdcall DecStrToNumber

	ret

endp

; -------------------------------------------------------------------------------------

proc PrintTestPrime

  ; print the test prime

	lea edi,[bfDisplay]

	lea esi,[TestPrime]

	stdcall PrintHexValue

	mov [edi],byte 0

	ret

endp

; -------------------------------------------------------------------------------------

proc PrintResult

  ; print the results

	lea edi,[bfDisplay]

	; print the random base value

	lea esi,[szMsg_1]

	stdcall AddStringToEDI

	PRINT_CRLF
	PRINT_CRLF

	lea esi,[BaseBf]

	stdcall PrintHexValue

	PRINT_CRLF
	PRINT_CRLF

	; print result of GCD test

	lea esi,[szMsg_2]

	stdcall AddStringToEDI

	lea esi,[szPassed]

	cmp [GCD_Passed],byte 1

	je .GCD

	lea esi,[szFailed]

  .GCD:

	stdcall AddStringToEDI

	PRINT_CRLF
	PRINT_CRLF

	; print result of mod exp test

	lea esi,[szMsg_3]

	stdcall AddStringToEDI

	lea esi,[szPassed]

	cmp [MEXP_Passed],byte 1

	je .MEXP

	lea esi,[szFailed]

  .MEXP:

	stdcall AddStringToEDI

	PRINT_CRLF
	PRINT_CRLF

	; null terminate bfDisplay

	mov [edi],byte 0

	ret

endp

; -------------------------------------------------------------------------------------

proc PrintHexValue uses ecx eax

  ; ESI and EDI set outside of this procedure

	locals

	  count db 0

	endl

	; find the first non zero dword in the hex value

	; starting from the high dword

	mov cx,HEX_LEN-4

	add esi,HEX_LEN-4

  .FIND:

	mov eax,[esi]

	cmp eax,0

	jne .PRINT

	sub esi,4

	sub cx,4

	jcxz .PRINT

	jmp .FIND

  .PRINT:

	mov eax,[esi]

	; dword to 8 digits

	stdcall DWordToStr

	jcxz .DONE

	sub cx,4

	sub esi,4

	inc [count]

	; add a CRLF to the output string after every 8 dwords

	cmp [count],byte 8

	je .ADD_CRLF

	jmp .PRINT

  .ADD_CRLF:

	mov [count],byte 0

	PRINT_CRLF

	jmp .PRINT

  .DONE:

	ret

endp

; -------------------------------------------------------------------------------------

proc WordToStr uses edx

  ; print a word (2 bytes) to a string

  ; word passed in AX
  ; EDI set outside of this function

	mov dx,ax
	mov al,ah

	stdcall ByteToDigits

	mov [edi],ah
	inc edi

	mov [edi],al
	inc edi

	mov al,dl

	stdcall ByteToDigits

	mov [edi],ah
	inc edi

	mov [edi],al
	inc edi

	ret

endp

; -------------------------------------------------------------------------------------

proc DWordToStr

  ; print a dword (4 bytes) to a string

  ; word passed in EAX
  ; EDI set outside of this function

	locals

	  tmp dw 0

	endl

	mov word [tmp],ax

	shr eax,16

	stdcall WordToStr

	mov ax,word [tmp]

	stdcall WordToStr

	; add a space

	mov [edi],byte 32
	inc edi

	ret

endp

; -------------------------------------------------------------------------------------

proc HexDigitToValue

  ; convert a hex digit to a 4 bit value

  ; input in AL - output in AL

	; is AL in the range: 48 - 57 (0 - 9) ?

	cmp al,48

	jl .NOT_HEX

	cmp al,57

	jg .A_Z

	sub al,48

	jmp .DONE

  .A_Z:

	; is AL in the range: 65 - 70 (A - B) ?

	cmp al,65

	jl .NOT_HEX

	cmp al,70

	jg .a_z

	sub al,55

	jmp .DONE

  .a_z:

	; is AL in the range: 97 - 102 (a - b) ?

	cmp al,97

	jl .NOT_HEX

	cmp al,102

	jg .NOT_HEX

	sub al,87

	jmp .DONE

  .NOT_HEX:

	; set EAX to 0xffff if input is not a valid hex digit

	mov eax,0xffff

  .DONE:

	ret

endp

; -------------------------------------------------------------------------------------

proc ByteToDigits

  ; convert 1 byte to 2 hex digits

  ; input in AL - output in AX

	; copy AL to AH

	mov ah,al

	; AH: get the upper 4 bits of the byte

	shr ah,4

	; nibble to hex digit

	add ah,48

	cmp ah,57

	jle .NEXT

	add ah,7

  .NEXT:

	; AL: get the lower 4 bits of the byte

	and al,0xf

	; nibble to hex digit

	add al,48

	cmp al,57

	jle .DONE

	add al,7

  .DONE:

	; output is in AX

	ret

endp

; -------------------------------------------------------------------------------------

proc HexStrToNumber uses esi edi ecx

  ; convert the hex string in bfDisplay to a hex value

	lea esi,[bfDisplay]

	lea edi,[TestPrime]

	stdcall ClearTestPrime

	; count the digits in bfDisplay and save to AX

	stdcall CountDigits

	; check if bfDisplay is empty

	cmp ax,0

	je .DONE

	; calculate the offset in bytes from the start of EDI

	; based on the number of digits in bfDisplay (given by AX)

	xor ecx,ecx

	mov cx,ax

	shr cx,1

	test ax,1

	jnz .ODD

  .EVEN:

	; bfDisplay contains an even number of hex digits

	; offset = (nDigits/2) - 1

	dec cx

	add edi,ecx

	jmp .GET_DIGITS

  .ODD:

	; bfDisplay contains an odd number of hex digits

	; offset = nDigits/2

	; convert the first digit

	add edi,ecx

	mov al,[esi]

	stdcall HexDigitToValue

	mov [edi],al

	inc esi

	dec edi

	dec cx

	cmp cx,0

	jl .DONE

  .GET_DIGITS:

	; convert 2 hex digits to 1 byte

	mov al,[esi]

	stdcall HexDigitToValue

	shl al,4

	mov [edi],al

	inc esi

	mov al,[esi]

	stdcall HexDigitToValue

	or [edi],al

	inc esi

	dec cx

	cmp cx,0

	jl .DONE

	dec edi

	jmp .GET_DIGITS

  .DONE:

	ret

endp

; -------------------------------------------------------------------------------------

proc CountDigits uses esi ecx

  ; count the number of hex digits in the bfDisplay string

	mov ax,0

	xor ecx,ecx

	lea esi,[bfDisplay]

  .COUNT:

	mov dl,[esi]

	cmp dl,0

	je .DONE

	inc cx

	inc esi

	jmp .COUNT

  .DONE:

	; return the digit count in AX

	mov ax,cx

	ret

endp

; -------------------------------------------------------------------------------------

proc FilterNonHex uses esi edi ecx

  ; filter out any non hex digit characters from bfDisplay

	lea esi,[bfDisplay]

	lea edi,[bfDisplay]

	xor ecx,ecx

  .FILTER:

	mov al,[esi]

	; 0 = null terminator

	cmp al,0

	je .DONE

	cmp al,48

	jl .NOT_HEX

	cmp al,57

	jle .COPY

	cmp al,65

	jl .NOT_HEX

	cmp al,70

	jle .COPY

	cmp al,97

	jl .NOT_HEX

	cmp al,102

	jg .NOT_HEX

  .COPY:

	mov [edi],al

	inc edi

	inc ecx

	cmp ecx,800

	jge .DONE

  .NOT_HEX:

	inc esi

	jmp .FILTER

  .DONE:

	; null terminate the new string

	mov [edi],byte 0

	ret

endp

; -------------------------------------------------------------------------------------

proc DecStrToNumber uses esi edi ecx

  ; convert the hex string in bfDisplay to a hex value

	locals

	  ndigits dw 0

	endl

	lea esi,[bfDisplay]

	lea edi,[TestPrime]

	stdcall ClearTestPrime

	xor ecx,ecx

  .GET_DIGITS:

	mov dl,[esi+ecx]

	cmp dl,0

	; exit when the null terminator is found

	je .DONE

	stdcall TestPrimex10

	sub dl,48

	stdcall AddDecimalDigit

	inc word [ndigits]

	; read a maximum of 963 decimal digits

	cmp [ndigits],word 963

	je .DONE

	inc cx

	jmp .GET_DIGITS

  .DONE:

	ret

endp

; -------------------------------------------------------------------------------------

proc FilterNonDec uses esi edi ecx

  ; filter out any non decimal digit characters from bfDisplay

	lea esi,[bfDisplay]

	lea edi,[bfDisplay]

	xor ecx,ecx

  .FILTER:

	mov al,[esi]

	; 0 = null terminator

	cmp al,0

	je .DONE

	cmp al,48

	jl .NOT_DEC

	cmp al,57

	jg .NOT_DEC

  .COPY:

	mov [edi],al

	inc edi

	inc ecx

	cmp ecx,963

	jge .DONE

  .NOT_DEC:

	inc esi

	jmp .FILTER

  .DONE:

	; null terminate the new string

	mov [edi],byte 0

	ret

endp

; -------------------------------------------------------------------------------------

proc AddDecimalDigit uses edi ecx

  ; add a decimal digit to the TestPrime value

  ; digit is passed in DL

	lea edi,[TestPrime]

	add [edi],dl

	jnc .DONE

	xor ecx,ecx

	mov cx,1

  .ADD_C:

	add [edi+ecx],byte 1

	jnc .DONE

	inc cx

	cmp cx,HEX_LEN

	jl .ADD_C

  .DONE:

	ret

endp

; -------------------------------------------------------------------------------------

proc TestPrimex10 uses esi edi ecx

  ; multiply the TestPrime buffer by 10

	lea esi,[TestPrime]

	lea edi,[TempBf]

	; copy TestPrime to TempBf

	xor ecx,ecx

  .COPY:

	mov al,[esi+ecx]

	mov [edi+ecx],al

	inc cx

	cmp cx,HEX_LEN

	jl .COPY

	; shift TempBf by 3

	add edi,HEX_LEN-4

	mov cx,HEX_LEN-4

  .SHL_3:

	mov eax,dword [edi-4]

	shld dword [edi],eax,3

	sub edi,4

	sub cx,4

	cmp cx,0

	jg .SHL_3

	shl dword [edi],3

	; shift TestPrime by 1

	lea edi,[TestPrime]

	add edi,HEX_LEN-4

	mov cx,HEX_LEN-4

  .SHL_1:

	mov eax,dword [edi-4]

	shld dword [edi],eax,1

	sub edi,4

	sub cx,4

	cmp cx,0

	jg .SHL_1

	shl dword [edi],1

	; add TempBf to TestPrime

	lea esi,[TempBf]

	lea edi,[TestPrime]

	xor ecx,ecx

	; save CF from iteration to iteration

	; init CF = 0

	clc

	; push flags register to the stack

	pushf

  .ADD:

	mov eax,dword [esi]

	; get the flags register from the stack

	popf

	; [EDI] = [EDI] + [ESI] + CF

	adc dword [edi],eax

	; save the flags register to the stack, for the next iteration

	pushf

	; these affect the CF, which is why it has to be saved to the stack

	add esi,4
	add edi,4

	add cx,4

	; cmp also affects the CF

	cmp cx,HEX_LEN

	jl .ADD

	; clean up the stack

	popf

	ret

endp

; -------------------------------------------------------------------------------------

proc ClearTestPrime uses edi ecx

  ; zero the test prime

	lea edi,[TestPrime]

	xor ecx,ecx

  .CLEAR:

	mov [edi+ecx],byte 0

	inc cx

	cmp cx,400

	jl .CLEAR

	ret

endp

; -------------------------------------------------------------------------------------

proc Test_Prime uses esi edi

  ; test the candidate

	lea esi,[TestPrime]

	; copy test prime to ModBf

	stdcall CopyToModBf

	; copy test prime to ExpBf and decrement

	stdcall CopyToExpBf

	lea edi,[ExpBf]

	stdcall Decrement

	; set BaseBf to a random value

	stdcall GetRandomBase

	; the GCD test

	stdcall Calc_GCD

	stdcall Check_GCD_Passed

	; the mod_exp test

	stdcall Mod_Exp

	stdcall Check_MEXP_Passed

	ret

endp

; -------------------------------------------------------------------------------------

proc GetRandomBase uses esi edi ecx

	; zero the Base

	lea edi,[BaseBf]

	xor ecx,ecx

  .ZERO:

	mov [edi+ecx],byte 0

	inc cx

	cmp cx,HEX_LEN

	jl .ZERO

  .SEED:

	; read the time stamp counter (into EDX:EAX)

	rdtsc

	; use RNG Linear Congruential Generator

	; X(n+1) = (aX(n) + c) mod m

	; a = 0x19660D, c = 0x3C6EF35F, m = 0x100000000

	; X(0) = EAX - from rdtsc

	xor ecx,ecx

  .RAND:

	mov edx,dword 0x19660D

	; multiply EAX by EDX

	mul edx

	; result in EDX:EAX

	add eax,0x3C6EF35F

	; copy to BaseBf

	mov [edi+ecx],eax

	add cx,4

	cmp cx,HEX_LEN

	jl .RAND

	; set BaseBf = BaseBf mod TestPrime

	lea esi,[BaseBf]

	stdcall CopyToProductBf

	lea esi,[TestPrime]

	stdcall CopyToShiftBf

	stdcall Modulus

	lea edi,[BaseBf]

	stdcall CopyFromProductBf

	stdcall CheckBaseBf

	ret

endp

; -------------------------------------------------------------------------------------

proc CheckBaseBf uses edi ecx

  ; if BaseBf is less than 2, set it to 2

	lea edi,[BaseBf]

	xor ecx,ecx

	mov cx,HEX_LEN-1

  .TEST:

	cmp [edi+ecx],byte 0

	jne .DONE

	dec cx

	cmp cx,0

	jg .TEST

	cmp [edi],byte 2

	jge .DONE

	mov [edi],byte 2

  .DONE:

	ret

endp

; -------------------------------------------------------------------------------------

proc CalcSum uses ecx

  ; Add two double sized hex numbers

  ; ESI and EDI are set outside of this procedure

	mov cx,0

	; save CF from iteration to iteration

	; init CF = 0

	clc

	; push flags register to the stack

	pushf

  .SUM:

	mov eax,dword [esi]

	; get the flags register from the stack

	popf

	; [EDI] = [EDI] + [ESI] + CF

	adc dword [edi],eax

	; save the flags register to the stack, for the next iteration

	pushf

	; these affect the CF, which is why it has to be saved to the stack

	add esi,4
	add edi,4

	add cx,4

	; cmp also affects the CF

	cmp cx,DBL_HEX_LEN

	jl .SUM

	; clean up the stack

	popf

	ret

endp

; -------------------------------------------------------------------------------------

proc CalcDiff uses ecx

  ; Calc difference between two double sized hex numbers

  ; diff = dest - src

  ; ESI and EDI are set outside of this procedure

	mov cx,0

	; compute diff as: diff = dest + ~src + 1

	; the 1 is introduced by initialising CF to 1

	; save CF from iteration to iteration

	; init CF = 1

	stc

	; push flags register to the stack

	pushf

  .SUB:

	mov eax,dword [esi]

	; ~src here:

	not eax

	; get the flags register from the stack

	popf

	; [EDI] = [EDI] + ~[ESI] + CF

	adc dword [edi],eax

	; save the flags register to the stack, for the next iteration

	pushf

	; these affect the CF, which is why it has to be saved to the stack

	add esi,4
	add edi,4

	add cx,4

	; cmp also affects the CF

	cmp cx,DBL_HEX_LEN

	jl .SUB

	; clean up the stack

	popf

	ret

endp

; -------------------------------------------------------------------------------------

proc ShiftLeft uses ecx

  ; Shift dest number left by 1 bit

  ; EDI is set outside of this procedure

	; start from the high order double word in the dest

	add edi,DBL_HEX_LEN-4

	mov cx,DBL_HEX_LEN-4

  .SHIFT:

	mov eax,dword [edi-4]

	shld dword [edi],eax,1

	sub edi,4

	sub cx,4

	cmp cx,0

	jg .SHIFT

	shl dword [edi],1

	ret

endp

; -------------------------------------------------------------------------------------

proc ShiftRight uses ecx

  ; Shift dest number right by 1 bit

  ; EDI is set outside of this procedure

	mov cx,0

  .SHIFT:

	mov eax,dword [edi+4]

	shrd dword [edi],eax,1

	add edi,4

	add cx,4

	cmp cx,DBL_HEX_LEN-4

	jl .SHIFT

	shr dword [edi],1

	ret

endp

; -------------------------------------------------------------------------------------

proc Multiply uses edi ecx

  ; calculate ProductBf = ESI * ShiftBf

  ; ESI is set outside of this procedure

	locals

	  nBit db 0

	endl

	; zero ProductBf

	stdcall ZeroProductBf

	; ESI is a hex value of length HEX_LEN

	; Algorithm:

	; first find the byte in ESI containing the high order bit

	; then starting from this byte, iterate through the bits in ESI
	; start from the high order bit down to the low order bit

	; for each iteration:

	; (1) left shift ProductBf by 1 bit
	; (2) test the bit
	; (3) if the bit is set, add ShiftBf to ProductBf

	mov cx,HEX_LEN

	; start from end of ESI (the highest byte)

	add esi,HEX_LEN-1

  .FIND_HOB:

	cmp byte [esi],0

	jne .FOUND

	dec esi

	dec cx

	cmp cx,0

	je .QUIT

	jmp .FIND_HOB

  .FOUND:

	; ESI now points to the byte that has the high order bit

	; cx contains the byte number (index into A)

	mov [nBit],byte 7

	; load the byte at address ESI into BL for testing

	mov bl,byte [esi]

  .FIND_BIT:

	test bl,0x80

	jnz .HO_BIT

	shl bl,1

	dec [nBit]

	cmp [nBit],byte 0

	jl .QUIT

	jmp .FIND_BIT

  .HO_BIT:

	; the high order bit has been found

	; initialise ProductBf

	stdcall AddShiftBfToProductBf

  .NEXT_BIT:

	; get the next bit

	shl bl,1

	dec [nBit]

	cmp [nBit],byte 0

	jl .NEXT_BYTE

	jmp .SHIFT

  .NEXT_BYTE:

	; get the next byte

	dec esi

	dec cx

	; no more bytes when cx = 0

	cmp cx,0

	jle .QUIT

	mov [nBit],byte 7

	mov bl,byte [esi]

  .SHIFT:

	; shift ProductBf 1 bit to the left

	lea edi,[ProductBf]

	stdcall ShiftLeft

	; test the current bit to see if an addition is required

	test bl,0x80

	jz .NEXT_BIT

  .ADD:

	; add to ProductBf

	stdcall AddShiftBfToProductBf

	jmp .NEXT_BIT

  .QUIT:

	ret

endp

; -------------------------------------------------------------------------------------

proc AddShiftBfToProductBf uses esi edi ecx

  ; add ShiftBf to ProductBf

	lea esi,[ShiftBf]

	lea edi,[ProductBf]

	stdcall CalcSum

	ret

endp

; -------------------------------------------------------------------------------------

proc Modulus uses edi esi eax ecx

  ; calculate ProductBf mod ShiftBf

  ; ProductBf is of length DBL_HEX_LEN

  ; ShiftBf is of length DBL_HEX_LEN

  ; length of value in ShiftBf is up to HEX_LEN

  ; the remainder is left in ProductBf

  ; length of remainder is less than or equal to HEX_LEN

	; if ShiftBf is zero, do nothing

	stdcall IsShiftBfZero

	cmp al,1

	je .QUIT

	; if ProductBf is less than ShiftBf, do nothing

	stdcall IsProductBfLessThanShiftBf

	cmp al,1

	je .QUIT

	; left shift ShiftBf to align the high order bits with ProductBf

	locals

	  hob_PBf dw 0
	  hob_SBf dw 0

	  shift dw 0

	endl

	; find the high order bit in ProductBf

	lea eax,[ProductBf]

	stdcall FindHighOrderBit

	; check if the high order bit was found

	cmp eax,0xffffffff

	je .QUIT

	mov word [hob_PBf],ax

	; find the high order bit in ShiftBf

	lea eax,[ShiftBf]

	stdcall FindHighOrderBit

	; check if the high order bit was found

	cmp eax,0xffffffff

	je .QUIT

	mov word [hob_SBf],ax

	; compute how much to shift ShiftBf by

	mov ax,[hob_PBf]
	sub ax,[hob_SBf]
	mov word [shift],ax

	; do the shift

	lea eax,[ShiftBf]
	xor edx,edx
	mov dx,word [shift]

	stdcall BigLeftShift

	; the high order bits of ProductBf and ShiftBf are now aligned

	; Algorithm:

	; for (shift + 1) bits in ProductBf starting from the high order bit:

	; (1) determine if ProductBf is less than ShiftBf
	; (2) if false, subtract ShiftBf from ProductBf
	; (3) right shift ShiftBf by 1 bit
	; (4) repeat from (1)

	mov cx,word [shift]

  .CALC_MOD:

	lea eax,[ProductBf]
	lea edx,[ShiftBf]

	stdcall IsLessThan

	test al,1

	jnz .SHIFT

	lea edi,[ProductBf]
	lea esi,[ShiftBf]

	stdcall CalcDiff

  .SHIFT:

	; want to retain the original value of ShiftBf
	; so when cx reaches 0, quit before the final shift

	cmp cx,0

	jle .QUIT

	; right shift ShiftBf

	lea edi,[ShiftBf]

	stdcall ShiftRight

	dec cx

	jmp .CALC_MOD

	; the result is now in A

  .QUIT:

	ret

endp

; -------------------------------------------------------------------------------------

proc BigLeftShift uses esi edi ecx

  ; left shift a double hex value by more than 1 bit

  ; address is passed in EAX
  ; size of shift passed in EDX

	mov edi,eax
	mov esi,eax

	locals

	  nBytes dw 0
	  nBits db 0

	  addr dd ?

	endl

	; save the address for later

	mov dword [addr],eax

	; size of shift = 8 * nBytes + nBits

	; get nBits

	mov al,dl

	and al,7

	mov byte [nBits],al

	; get nBytes

	shr dx,3

	mov word [nBytes],dx

	cmp word [nBytes],0

	je .BITS

	cmp word [nBytes],DBL_HEX_LEN

	jge .ZERO_HEX

	; copy up the bytes in the hex value by nBytes

	add edi,DBL_HEX_LEN-1
	add esi,DBL_HEX_LEN-1

	sub si,word [nBytes]

	mov cx,DBL_HEX_LEN
	sub cx,word [nBytes]

	; copy up (DBL_HEX_LEN - nBytes) bytes

  .COPY_UP:

	mov al,[esi]
	mov [edi],al

	dec esi
	dec edi

	dec cx

	cmp cx,0

	jg .COPY_UP

	mov cx,word [nBytes]

	; fill the rest of the hex array with zero bytes

  .FILL_0:

	mov [edi],byte 0

	dec edi

	dec cx

	cmp cx,0

	jg .FILL_0

	; all done if nBits is zero

	cmp byte [nBits],0

	je .DONE

  .BITS:

	; set edi back to the high order dword in the hex value

	mov edi,dword [addr]

	add edi,DBL_HEX_LEN-4

	mov cx,DBL_HEX_LEN-4

  .SHIFT_BITS:

	mov eax,[edi-4]

	push cx

	mov cl,byte [nBits]

	shld dword [edi],eax,cl

	pop cx

	sub edi,4

	sub cx,4

	cmp cx,0

	jg .SHIFT_BITS

	mov cl,byte [nBits]

	shl dword [edi],cl

	jmp .DONE

  .ZERO_HEX:

	; shift is greater than the size of the hex value, just set to zero

	stdcall ZeroDoubleHexBuffer

  .DONE:

	ret

endp

; -------------------------------------------------------------------------------------

proc FindHighOrderBit uses esi ecx

  ; scan a double hex length value for the high order bit

  ; return an index number giving the position of the high order bit

  ; address passed in EAX

  ; index returned in EAX

	mov esi,eax

	; start from the high order byte

	add esi,DBL_HEX_LEN-1

	mov cx,DBL_HEX_LEN

	mov eax,DBL_HEX_LEN-1

	; scan byte by byte for the first non-zero byte

  .SCAN:

	cmp byte [esi],0

	jne .FOUND

	dec cx

	cmp cx,0

	; not found if cx = 0, so quit

	jle .NOT_FOUND

	dec esi
	dec eax

	jmp .SCAN

  .FOUND:

	; multiply EAX by 8

	shl eax,3

	mov ebx,7

	mov dl,byte [esi]

  .FIND_BIT:

	test dl,0x80

	jnz .FINISH

	shl dl,1

	dec bl

	cmp bl,0

	jl .NOT_FOUND

	jmp .FIND_BIT

  .FINISH:

	; add the bit position to get the final index value

	add eax,ebx

	jmp .DONE

  .NOT_FOUND:

	mov eax,0xffffffff

  .DONE:

	ret

endp

; -------------------------------------------------------------------------------------

proc IsLessThan uses esi edi ecx

  ; is A less than B ?

  ; A and B are treated as unsigned values

  ; address of A passed in EAX
  ; address of B passed in EDX

	mov edi,eax
	mov esi,edx

	; start from the high order bytes

	add esi,DBL_HEX_LEN-4
	add edi,DBL_HEX_LEN-4

	mov cx,0

	; result is returned in AL

	xor al,al

  .CHECK_LT:

	mov edx,dword [edi]
	cmp edx,dword [esi]

	jb .LESS_THAN

	jnbe .QUIT

	add cx,4

	cmp cx,DBL_HEX_LEN

	jge .QUIT

	sub esi,4
	sub edi,4

	jmp .CHECK_LT

	; AL = true if less than

  .LESS_THAN:

	mov al,1

  .QUIT:

	ret

endp

; -------------------------------------------------------------------------------------

proc Mod_Exp uses esi edi

  ; compute Mod_Exp = pow(A,B) mod C

  ; A is in BaseBf
  ; B is in ExpBf
  ; C is in ModBf

  ; result in ProductBf

	locals

	  nBit db 0

	  index dw 0

	  bits db 0

	endl

	stdcall ZeroProductBf

	; if C is zero, do nothing

	stdcall IsModBfZero

	cmp al,1

	je .QUIT

	; init ProductBf to 1

	lea edi,[ProductBf]

	mov [edi],byte 1

	; if B is zero, do nothing

	stdcall IsExpBfZero

	cmp al,1

	je .QUIT

	; ProductBf is now 1

  .START:

	; find the first non zero byte in ExpBf

	lea esi,[ExpBf]

	xor ecx,ecx

	mov cx,HEX_LEN-1

  .FIND:

	cmp [esi+ecx],byte 0

	jne .FOUND

	dec cx

	cmp cx,0

	jge .FIND

	; if the loop exits here, ExpBf is zero

	jmp .QUIT

  .FOUND:

	; save the index

	mov [index],cx

	; save the byte

	mov al,byte [esi+ecx]

	mov [bits],al

	; set the bit index

	mov [nBit],byte 8

	; start processing

  .SQUARE:

	; always square, whether the bit is 0 or 1

	; square the value in ProductBf

	stdcall CopyProductBfToShiftBf

	stdcall CopyProductBfToTempBf

	stdcall ZeroProductBf

	lea esi,[TempBf]

	stdcall Multiply

	stdcall CopyModBfToShiftBf

	stdcall Modulus

  .TEST:

	; only multiply if the bit is 1

	; decrement the bit index

	dec [nBit]

	; test the bit in [bits]

	shl byte [bits],1

	jnc .NEXT_BIT

  .MULTIPLY:

	; multiply ProductBf by BaseBf

	stdcall CopyProductBfToShiftBf

	stdcall ZeroProductBf

	lea esi,[BaseBf]

	stdcall Multiply

	stdcall CopyModBfToShiftBf

	stdcall Modulus

  .NEXT_BIT:

	; if nBit = 0, will need to get the next byte

	cmp [nBit],byte 0

	jg .SQUARE

  .NEXT_BYTE:

	; get the next byte

	; if index = 0, there is no next byte, so quit

	cmp [index],word 0

	je .QUIT

	dec word [index]

	mov [nBit],byte 8

	; make sure ESI points to ExpBf

	lea esi,[ExpBf]

	xor ecx,ecx

	mov cx,[index]

	mov al,byte [esi+ecx]

	mov [bits],al

	jmp .SQUARE

  .QUIT:

	ret

endp

; -------------------------------------------------------------------------------------

proc CopyToBaseBf uses edi ecx

  ; copy ESI to BaseBf

  ; ESI is set outside of this procedure

	lea edi,[BaseBf]

	xor ecx,ecx

  .COPY:

	mov dl,[esi+ecx]

	mov [edi+ecx],dl

	inc cx

	cmp cx,HEX_LEN

	jl .COPY

	ret

endp

; -------------------------------------------------------------------------------------

proc CopyToExpBf uses edi ecx

  ; copy ESI to ExpBf

  ; ESI is set outside of this procedure

	lea edi,[ExpBf]

	xor ecx,ecx

  .COPY:

	mov dl,[esi+ecx]

	mov [edi+ecx],dl

	inc cx

	cmp cx,HEX_LEN

	jl .COPY

	ret

endp

; -------------------------------------------------------------------------------------

proc CopyToModBf uses edi ecx

  ; copy ESI to ModBf

  ; ESI is set outside of this procedure

	lea edi,[ModBf]

	xor ecx,ecx

  .COPY:

	mov dl,[esi+ecx]

	mov [edi+ecx],dl

	inc cx

	cmp cx,HEX_LEN

	jl .COPY

	ret

endp

; -------------------------------------------------------------------------------------

proc Calc_GCD uses esi edi ecx

  ; calc GCD of TestPrime with BaseBf

	lea esi,[TestPrime]

	stdcall CopyToProductBf

	lea esi,[BaseBf]

	stdcall CopyToShiftBf

  .GCD:

	stdcall Modulus

	stdcall XchgProductBfShiftBf

	stdcall IsShiftBfZero

	cmp al,1

	je .DONE

	jmp .GCD

  .DONE:

	ret

endp

; -------------------------------------------------------------------------------------

proc XchgProductBfShiftBf uses esi edi ecx

  ; swap the values in ProductBf and ShiftBf

	lea esi,[ProductBf]

	lea edi,[ShiftBf]

	xor ecx,ecx

  .SWAP:

	mov dl,[esi+ecx]

	mov bl,[edi+ecx]

	mov [edi+ecx],dl

	mov [esi+ecx],bl

	inc cx

	cmp cx,DBL_HEX_LEN

	jl .SWAP

	ret

endp

; -------------------------------------------------------------------------------------

proc ZeroDoubleHexBuffer uses ecx

  ; zero the double hex value in memory

	mov cx,0

  .ZERO:

	mov [edi],byte 0

	inc edi
	inc cx

	cmp cx,DBL_HEX_LEN

	jne .ZERO

	ret

endp

; -------------------------------------------------------------------------------------

proc IsHexZero uses ecx

  ; is a hex number of length HEX_LEN equal to zero ?

  ; EDI is set outside of this procedure

  ; EDI is not modifed by this procedure

	xor ecx,ecx

  .TEST:

	cmp [edi+ecx],byte 0

	jne .NON_ZERO

	inc cx

	cmp cx,HEX_LEN

	jl .TEST

	; if the loop exits here, the value is zero

	mov al,1

	jmp .DONE

  .NON_ZERO:

	xor eax,eax

  .DONE:

	ret

endp

; -------------------------------------------------------------------------------------

proc IsDblHexZero uses ecx

  ; is a double hex number of length DBL_HEX_LEN equal to zero ?

  ; EDI is set outside of this procedure

  ; EDI is not modifed by this procedure

	xor ecx,ecx

  .TEST:

	cmp [edi+ecx],byte 0

	jne .NON_ZERO

	inc cx

	cmp cx,DBL_HEX_LEN

	jl .TEST

	; if the loop exits here, the value is zero

	mov al,1

	jmp .DONE

  .NON_ZERO:

	xor eax,eax

  .DONE:

	ret

endp

; -------------------------------------------------------------------------------------

proc IsExpBfZero uses edi

  ; is ExpBf equal to zero ?

	lea edi,[ExpBf]

	stdcall IsHexZero

	ret

endp

; -------------------------------------------------------------------------------------

proc IsModBfZero uses edi

  ; is ModBf equal to zero ?

	lea edi,[ModBf]

	stdcall IsHexZero

	ret

endp

; -------------------------------------------------------------------------------------

proc CopyProductBfToShiftBf uses esi edi ecx

  ; copy ProductBf to ShiftBf

	lea esi,[ProductBf]

	lea edi,[ShiftBf]

	xor ecx,ecx

  .COPY:

	mov dl,[esi+ecx]

	mov [edi+ecx],dl

	inc cx

	cmp cx,DBL_HEX_LEN

	jl .COPY

	ret

endp

; -------------------------------------------------------------------------------------

proc CopyProductBfToTempBf uses esi edi ecx

  ; copy ProductBf to TempBf

	lea esi,[ProductBf]

	lea edi,[TempBf]

	xor ecx,ecx

  .COPY:

	mov dl,[esi+ecx]

	mov [edi+ecx],dl

	inc cx

	cmp cx,HEX_LEN

	jl .COPY

	ret

endp

; -------------------------------------------------------------------------------------

proc ZeroShiftBf uses edi ecx

  ; zero the shift buffer

	lea edi,[ShiftBf]

	xor ecx,ecx

  .CLEAR:

	mov [edi+ecx],byte 0

	inc cx

	cmp cx,DBL_HEX_LEN

	jl .CLEAR

	ret

endp

; -------------------------------------------------------------------------------------

proc CopyModBfToShiftBf uses esi

  ; copy ModBf to ShiftBf

	lea esi,[ModBf]

	stdcall CopyToShiftBf

	ret

endp

; -------------------------------------------------------------------------------------

proc CopyBaseBfToProductBf uses esi

  ; copy BaseBf to ProductBf

	lea esi,[BaseBf]

	stdcall CopyToProductBf

	ret

endp

; -------------------------------------------------------------------------------------

proc CopyToShiftBf uses edi ecx

  ; copy ESI to ShiftBf

  ; ESI is of length HEX_LEN

  ; ESI is set outside of this procedure

	lea edi,[ShiftBf]

	xor ecx,ecx

  .COPY:

	mov dl,[esi+ecx]

	mov [edi+ecx],dl

	inc cx

	cmp cx,HEX_LEN

	jl .COPY

  .ZERO:

	; zero the upper bytes of ShiftBf

	mov [edi+ecx],byte 0

	inc cx

	cmp cx,DBL_HEX_LEN

	jl .ZERO

	ret

endp

; -------------------------------------------------------------------------------------

proc ZeroProductBf uses edi ecx

  ; zero the product buffer

	lea edi,[ProductBf]

	xor ecx,ecx

  .CLEAR:

	mov [edi+ecx],byte 0

	inc cx

	cmp cx,DBL_HEX_LEN

	jl .CLEAR

	ret

endp

; -------------------------------------------------------------------------------------

proc CopyToProductBf uses edi ecx

  ; copy ESI to ProductBf

  ; ESI is of length HEX_LEN

  ; ESI is set outside of this procedure

	lea edi,[ProductBf]

	xor ecx,ecx

  .COPY:

	mov dl,[esi+ecx]

	mov [edi+ecx],dl

	inc cx

	cmp cx,HEX_LEN

	jl .COPY

  .ZERO:

	; zero the upper bytes of ProductBf

	mov [edi+ecx],byte 0

	inc cx

	cmp cx,DBL_HEX_LEN

	jl .ZERO

	ret

endp

; -------------------------------------------------------------------------------------

proc CopyFromProductBf uses esi ecx

  ; copy from ProductBf to EDI

  ; EDI is of length HEX_LEN

  ; EDI is set outside of this procedure

	lea esi,[ProductBf]

	xor ecx,ecx

  .COPY:

	mov dl,[esi+ecx]

	mov [edi+ecx],dl

	inc cx

	cmp cx,HEX_LEN

	jl .COPY

	ret

endp

; -------------------------------------------------------------------------------------

proc IsProductBfLessThanShiftBf uses esi edi ecx

  ; is ProductBf less than ShiftBf

	lea esi,[ShiftBf]

	lea edi,[ProductBf]

	xor ecx,ecx

	mov cx,DBL_HEX_LEN-1

  .COMPARE:

	mov dl,[esi+ecx]

	cmp [edi+ecx],dl

	jb .LT

	ja .GTE

	dec cx

	cmp cx,0

	jge .COMPARE

	; if the loop exits here, the values are equal

  .GTE:

	xor eax,eax

	jmp .DONE

  .LT:

	mov al,1

  .DONE:

	ret

endp

; -------------------------------------------------------------------------------------

proc IsShiftBfZero uses edi

  ; is ShiftBf zero ?

	lea edi,[ShiftBf]

	stdcall IsDblHexZero

	ret

endp

; -------------------------------------------------------------------------------------

proc Decrement uses ecx

  ; decrement the value in EDI

  ; EDI is set outside of this procedure

	sub [edi],byte 1

	jnc .DONE

	xor ecx,ecx

	mov cx,1

  .SUB_B:

	sub [edi+ecx],byte 1

	jnc .DONE

	inc cx

	cmp cx,HEX_LEN

	jl .SUB_B

  .DONE:

	ret

endp

; -------------------------------------------------------------------------------------

proc AddStringToEDI

  ; print a string to the EDI buffer

  ; ESI and EDI are set outside of this procedure

  .PRINT:

	mov dl,[esi]

	cmp dl,0

	je .DONE

	mov [edi],dl

	inc esi
	inc edi

	jmp .PRINT

  .DONE:

	ret

endp

; -------------------------------------------------------------------------------------

proc Check_GCD_Passed uses esi ecx

  ; did the test prime pass the GCD test ?

	lea esi,[ProductBf]

	xor ecx,ecx

	mov cx,DBL_HEX_LEN-1

  .TEST:

	cmp [esi+ecx],byte 0

	jne .FAILED

	dec cx

	cmp cx,0

	jg .TEST

	; test [esi]

	cmp [esi],byte 1

	jne .FAILED

  .PASSED:

	mov [GCD_Passed],byte 1

	jmp .DONE

  .FAILED:

	mov [GCD_Passed],byte 0

  .DONE:

	ret

endp

; -------------------------------------------------------------------------------------

proc Check_MEXP_Passed uses esi ecx

  ; did the test prime pass the mod exp test ?

	lea esi,[ProductBf]

	xor ecx,ecx

	mov cx,DBL_HEX_LEN-1

  .TEST:

	cmp [esi+ecx],byte 0

	jne .FAILED

	dec cx

	cmp cx,0

	jg .TEST

	; test [esi]

	cmp [esi],byte 1

	jne .FAILED

  .PASSED:

	mov [MEXP_Passed],byte 1

	jmp .DONE

  .FAILED:

	mov [MEXP_Passed],byte 0

  .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',\
	 GetDlgItemText,'GetDlgItemTextA',\
	 EndDialog,'EndDialog'

; -------------------------------------------------------------------------------------

section '.data' readable writeable

  bfDisplay rb 1200

  TestPrime rb 400

  ShiftBf rb DBL_HEX_LEN
  ProductBf rb DBL_HEX_LEN

  TempBf rb HEX_LEN

  BaseBf rb HEX_LEN
  ExpBf rb HEX_LEN
  ModBf rb HEX_LEN

  szMsg_1 db "The input number was tested with the random integer:",0
  szMsg_2 db "TEST: GCD(a,p) = 1 --> ",0
  szMsg_3 db "TEST: a^(p-1) mod p = 1 --> ",0

  szFailed db "FAILED",0
  szPassed db "PASSED",0

  GCD_Passed db 0
  MEXP_Passed db 0

; -------------------------------------------------------------------------------------

section '.rc' resource data readable

  directory RT_DIALOG,dialogs

  resource dialogs,IDD_THE_DIALOG,LANG_ENGLISH+SUBLANG_DEFAULT,the_dialog

  dialog the_dialog,\
  'FASM - Prime Number Test',50,50,360,396,\
  DS_MODALFRAME+WS_MINIMIZEBOX+WS_POPUP+WS_VISIBLE+WS_CAPTION+WS_SYSMENU,\
  0,0,"Lucida Console",11

  dialogitem 'BUTTON','Input',-1,7,5,346,180,BS_GROUPBOX+WS_VISIBLE,0
  dialogitem 'BUTTON',"Output",-1,7,190,346,180,BS_GROUPBOX+WS_VISIBLE,0

  dialogitem 'EDIT',0,IDC_INPUT,13,18,335,160,ES_MULTILINE+ES_AUTOVSCROLL+ES_WANTRETURN+WS_VSCROLL+WS_BORDER+WS_VISIBLE,0
  dialogitem 'EDIT',0,IDC_OUTPUT,13,203,335,160,ES_MULTILINE+ES_AUTOVSCROLL+ES_WANTRETURN+WS_VSCROLL+WS_BORDER+WS_VISIBLE,0

  dialogitem 'BUTTON',"Test Decimal",IDC_BTN_TEST_DEC,7,375,80,14,BS_PUSHBUTTON+WS_VISIBLE,0
  dialogitem 'BUTTON',"Test Hexadecimal",IDC_BTN_TEST_HEX,89,375,80,14,BS_PUSHBUTTON+WS_VISIBLE,0

  enddialog

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

Blog at WordPress.com.

%d bloggers like this: