compiled in a way it doesn't needs a dll in Windows and works with PureBasic. I'm still not able to compile
the GMP Library that way with MinGW but I don't have the time anymore to play with such things.
Maybe someone else wants to make use of the functions I already wrote. Anyway, here are some
procedures to make calculations with large numbers in PureBasic x86 but only with positive integers.
If anyone improves this or makes extensions I'd be glad if it could be shared here, too.
As for this code here it's free to use and modify.
Have fun with it. :)
BigNumbers.pbi
Code: Select all
;Internal ASM Macros (don't change)
!macro BNPV_PUSH [register]
!{
! BNPV_VARC = 0
! if ~ defined BNPV_OFFSET
! BNPV_OFFSET = 0
! end if
! if ~ register eq
! PUSH register
! BNPV_OFFSET = BNPV_OFFSET+4
! end if
!}
!macro BNPV_POP [register]
!{
! if ~ register eq
! reverse POP register
! BNPV_OFFSET = 0
! end if
!}
!macro BNPV_VARS [varName]
!{
! common
! BNPV_VARC = -4
! forward
! BNPV_VARC = BNPV_VARC+4
! BNPV_OFFSET = BNPV_OFFSET+4
! if ~ varName eq
! local varOffset
! varOffset = BNPV_VARC
! varName equ esp+varOffset
! PUSH 0
! end if
!}
!macro BNPV_FREEVARS
!{
! if BNPV_VARC <> -4
! ADD esp, BNPV_VARC+4
! BNPV_OFFSET = BNPV_OFFSET-(BNPV_VARC+4)
! end if
!}
Macro _bn_qt()
"
EndMacro
;MAIN_MACRO
;
; - contains all functions
; - call with or without special naming
; -> names will be added to the size constant, the structure name and behind the BN of every function
; - disable check weather 0 was passed as memory pointer or not (little speed increase, but not always)
; - compile optimized for size rather than speed or leave it default
Macro InitBigNumbers(_bn_bits, _bn_naming=, _bn_checkmem=#True, _bn_size_optimized=#False) ;_bn_bits must be a multiple of 32
#BIG_NUMBER#_bn_naming#_LONGS = _bn_bits/32
!BIG_NUMBER#_bn_naming#_LONGS = _bn_bits/32
Structure BIG_NUMBER#_bn_naming#
n.l[#BIG_NUMBER#_bn_naming#_LONGS]
EndStructure
Declare.l BN#_bn_naming#_INT(*dest.BIG_NUMBER#_bn_naming#, b.l)
Declare.l BN#_bn_naming#_VAL(*dest.BIG_NUMBER#_bn_naming#, a.s)
Declare.s BN#_bn_naming#_STR(*a.BIG_NUMBER#_bn_naming#)
Declare.s BN#_bn_naming#_HEX(*a.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_ADD(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_ADDINT(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
Declare.l BN#_bn_naming#_SUB(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_SUBINT(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
Declare.l BN#_bn_naming#_MUL(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#, dwordsA.l = -1, dwordsB.l = -1)
Declare.l BN#_bn_naming#_KARATSUBA(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_MULINT(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
Declare.l BN#_bn_naming#_POW(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_POWINT(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
Declare.l BN#_bn_naming#_POW_MOD(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#, *m.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_POW_MODINT(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#, m.l)
Declare.l BN#_bn_naming#_SQR(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_DIV(*dest.BIG_NUMBER#_bn_naming#, *destRem.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_DIVINT(*dest.BIG_NUMBER#_bn_naming#, *destRem.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
Declare.l BN#_bn_naming#_MOD(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_MODINT(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
Declare.l BN#_bn_naming#_GCD(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_INV_MOD(*dest.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#, *n.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_RND(*dest.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_RND_MAX(*dest.BIG_NUMBER#_bn_naming#, bits.l)
Declare.l BN#_bn_naming#_MOV(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_NOT(*dest.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_AND(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_OR(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_XOR(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_SHL(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
Declare.l BN#_bn_naming#_SHL1(*dest.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_SHR(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
Declare.l BN#_bn_naming#_SHR1(*dest.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_CMP(*a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_CMPINT(*a.BIG_NUMBER#_bn_naming#, b.l)
Declare.l BN#_bn_naming#_IS_EVEN(*a.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_IS_PRIME(*a.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_NEXT_PRIME(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_USED_BITS(*a.BIG_NUMBER#_bn_naming#)
Declare.l BN#_bn_naming#_USED_LONGS(*a.BIG_NUMBER#_bn_naming#)
;- BN_INT(*dest.BIG_NUMBER, b.l)
Procedure.l BN#_bn_naming#_INT(*dest.BIG_NUMBER#_bn_naming#, b.l)
CompilerIf _bn_checkmem=#True
If *dest=0
ProcedureReturn 0
EndIf
CompilerEndIf
!BNPV_PUSH esi,edi
!MOV edi, dword [p.p_dest+BNPV_OFFSET]
!XOR eax, eax
CompilerIf _bn_size_optimized
!if BIG_NUMBER#_bn_naming#_LONGS > 1
!MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
!@@:
!MOV dword [edi+ecx*4], eax
!DEC ecx
!JNZ @b
!end if
CompilerElse
!repeat BIG_NUMBER#_bn_naming#_LONGS-1
!MOV dword [edi+(%)*4], eax
!end repeat
CompilerEndIf
!MOV eax, dword [p.v_b+BNPV_OFFSET]
!MOV dword [edi], eax
!BNPV_POP esi,edi
ProcedureReturn *dest
EndProcedure
;- BN_VAL(*dest.BIG_NUMBER, a.s)
Procedure.l BN#_bn_naming#_VAL(*dest.BIG_NUMBER#_bn_naming#, a.s)
Protected *tmp.BIG_NUMBER#_bn_naming#, *char.CHARACTER
CompilerIf _bn_checkmem=#True
If *dest=0
ProcedureReturn 0
EndIf
CompilerEndIf
*tmp = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#))
If *tmp=0
ProcedureReturn 0
EndIf
!MOV edx, dword [p.p_dest+BNPV_OFFSET]
!XOR eax, eax
CompilerIf _bn_size_optimized
!MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
!@@:
!MOV dword [edx+ecx*4], eax
!DEC ecx
!JNS @b
CompilerElse
!repeat BIG_NUMBER#_bn_naming#_LONGS
!MOV dword [edx+(%-1)*4], eax
!end repeat
CompilerEndIf
*char = @a
While *char\c
If *char\c >= '0' And *char\c <= '9'
If *char <> @a
BN#_bn_naming#_MULINT(*tmp, *dest, 10)
EndIf
BN#_bn_naming#_ADDINT(*dest, *tmp, *char\c - '0')
EndIf
*char + 1 + #PB_Compiler_Unicode
Wend
FreeMemory(*tmp)
ProcedureReturn *dest
EndProcedure
;- BN_STR(*a.BIG_NUMBER)
Procedure.s BN#_bn_naming#_STR(*a.BIG_NUMBER#_bn_naming#)
Protected *div.BIG_NUMBER#_bn_naming#, *mod.BIG_NUMBER#_bn_naming#, *tmp.BIG_NUMBER#_bn_naming#, Buf$, i.l
CompilerIf _bn_checkmem=#True
If *a=0
ProcedureReturn ""
EndIf
CompilerEndIf
*div = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#)*3)
*mod = *div+SizeOf(BIG_NUMBER#_bn_naming#)
*tmp = *mod+SizeOf(BIG_NUMBER#_bn_naming#)
If *div=0
ProcedureReturn ""
EndIf
BN#_bn_naming#_MOV(*tmp, *a)
Repeat
BN#_bn_naming#_DIVINT(*div, *mod, *tmp, 10)
Buf$ = Str(*mod\n[0] & $F) + Buf$
BN#_bn_naming#_MOV(*tmp, *div)
Until BN#_bn_naming#_CMPINT(*div, 0) = 0
FreeMemory(*div)
ProcedureReturn Buf$
EndProcedure
;- BN_HEX(*a.BIG_NUMBER)
Procedure.s BN#_bn_naming#_HEX(*a.BIG_NUMBER#_bn_naming#)
Protected Buf$, i.l
CompilerIf _bn_checkmem=#True
If *a=0
ProcedureReturn ""
EndIf
CompilerEndIf
For i=#BIG_NUMBER#_bn_naming#_LONGS-1 To 0 Step -1
Buf$ + RSet(Hex(*a\n[i] & $FFFFFFFF),8,"0")
Next
ProcedureReturn Buf$
EndProcedure
;- BN_ADD(*dest.BIG_NUMBER, *a.BIG_NUMBER, *b.BIG_NUMBER)
Procedure.l BN#_bn_naming#_ADD(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
CompilerIf _bn_checkmem=#True
If *dest=0 Or *a=0 Or *b=0
ProcedureReturn 0
EndIf
CompilerEndIf
!BNPV_PUSH esi,edi
!MOV esi, dword [p.p_a+BNPV_OFFSET]
!MOV ecx, dword [p.p_b+BNPV_OFFSET]
!MOV edi, dword [p.p_dest+BNPV_OFFSET]
!MOV eax, dword [esi]
!ADD eax, dword [ecx]
!MOV dword [edi], eax
CompilerIf _bn_size_optimized
!MOV edx, 1
!if BIG_NUMBER#_bn_naming#_LONGS > 1
!PUSHFD
!@@:
!POPFD
!MOV eax, dword [esi+edx*4]
!ADC eax, dword [ecx+edx*4]
!MOV dword [edi+edx*4], eax
!PUSHFD
!INC edx
!CMP edx, BIG_NUMBER#_bn_naming#_LONGS
!JB @b
!POPFD
!end if
CompilerElse
!if BIG_NUMBER#_bn_naming#_LONGS > 1
!repeat BIG_NUMBER#_bn_naming#_LONGS-1
!MOV eax, dword [esi+%*4]
!ADC eax, dword [ecx+%*4]
!MOV dword [edi+%*4], eax
!end repeat
!end if
CompilerEndIf
!BNPV_POP esi,edi
CompilerIf #PB_Compiler_Debugger
!JNC @f
Debug _bn_qt()BN#_bn_naming#_ADD Overflow#_bn_qt()
!@@:
CompilerEndIf
ProcedureReturn *dest
EndProcedure
;- BN_ADDINT(*dest.BIG_NUMBER, *a.BIG_NUMBER, b.l)
Procedure.l BN#_bn_naming#_ADDInt(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
CompilerIf _bn_checkmem=#True
If *dest=0 Or *a=0
ProcedureReturn 0
EndIf
CompilerEndIf
!BNPV_PUSH esi,edi
!MOV esi, dword [p.p_a+BNPV_OFFSET]
!MOV edi, dword [p.p_dest+BNPV_OFFSET]
!MOV eax, dword [esi]
!ADD eax, dword [p.v_b+BNPV_OFFSET]
!MOV dword [edi], eax
!JNC @@BN#_bn_naming#_ADDINT_procend
!if BIG_NUMBER#_bn_naming#_LONGS > 1
!repeat BIG_NUMBER#_bn_naming#_LONGS-1
!MOV eax, dword [esi+%*4]
!ADC eax, 0
!MOV dword [edi+%*4], eax
!if % < BIG_NUMBER#_bn_naming#_LONGS-1
!JNC @@BN#_bn_naming#_ADDINT_procend
!end if
!end repeat
!end if
!JMP @@BN#_bn_naming#_ADDINT_procend2
!@@BN#_bn_naming#_ADDINT_procend:
!if BIG_NUMBER#_bn_naming#_LONGS > 1
!repeat BIG_NUMBER#_bn_naming#_LONGS-1
!MOV eax, dword [esi+%*4]
!MOV dword [edi+%*4], eax
!end repeat
!end if
!@@BN#_bn_naming#_ADDINT_procend2:
!BNPV_POP esi,edi
CompilerIf #PB_Compiler_Debugger
!JNC @f
Debug _bn_qt()BN#_bn_naming#_ADDINT Overflow#_bn_qt()
!@@:
CompilerEndIf
ProcedureReturn *dest
EndProcedure
;- BN_SUB(*dest.BIG_NUMBER, *a.BIG_NUMBER, *b.BIG_NUMBER)
Procedure.l BN#_bn_naming#_SUB(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
CompilerIf _bn_checkmem=#True
If *dest=0 Or *a=0 Or *b=0
ProcedureReturn 0
EndIf
CompilerEndIf
!BNPV_PUSH esi,edi
!MOV esi, dword [p.p_a+BNPV_OFFSET]
!MOV ecx, dword [p.p_b+BNPV_OFFSET]
!MOV edi, dword [p.p_dest+BNPV_OFFSET]
!MOV eax, dword [esi]
!SUB eax, dword [ecx]
!MOV dword [edi], eax
CompilerIf _bn_size_optimized
!MOV edx, 1
!if BIG_NUMBER#_bn_naming#_LONGS > 1
!PUSHFD
!@@:
!POPFD
!MOV eax, dword [esi+edx*4]
!SBB eax, dword [ecx+edx*4]
!MOV dword [edi+edx*4], eax
!PUSHFD
!INC edx
!CMP edx, BIG_NUMBER#_bn_naming#_LONGS
!JB @b
!POPFD
!end if
CompilerElse
!if BIG_NUMBER#_bn_naming#_LONGS > 1
!repeat BIG_NUMBER#_bn_naming#_LONGS-1
!MOV eax, dword [esi+%*4]
!SBB eax, dword [ecx+%*4]
!MOV dword [edi+%*4], eax
!end repeat
!end if
CompilerEndIf
!BNPV_POP esi,edi
CompilerIf #PB_Compiler_Debugger
!JNC @f
Debug _bn_qt()BN#_bn_naming#_SUB Underflow#_bn_qt()
!@@:
CompilerEndIf
ProcedureReturn *dest
EndProcedure
;- BN_SUBINT(*dest.BIG_NUMBER, *a.BIG_NUMBER, b.l)
Procedure.l BN#_bn_naming#_SUBINT(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
CompilerIf _bn_checkmem=#True
If *dest=0 Or *a=0
ProcedureReturn 0
EndIf
CompilerEndIf
!BNPV_PUSH esi,edi
!MOV esi, dword [p.p_a+BNPV_OFFSET]
!MOV edi, dword [p.p_dest+BNPV_OFFSET]
!MOV eax, dword [esi]
!SUB eax, dword [p.v_b+BNPV_OFFSET]
!JNC @@BN#_bn_naming#_SUBINT_procend
!if BIG_NUMBER#_bn_naming#_LONGS > 1
!MOV ecx, 1
!@@BN#_bn_naming#_SUBINT_for1:
!DEC ecx
!MOV dword [edi+ecx*4], eax
!INC ecx
!MOV eax, dword [esi+ecx*4]
!SUB eax, 1
!JNC @@BN#_bn_naming#_SUBINT_copyRem
!INC ecx
!CMP ecx, BIG_NUMBER#_bn_naming#_LONGS-1
!JB @@BN#_bn_naming#_SUBINT_for1
!@@BN#_bn_naming#_SUBINT_next1:
!JMP @@BN#_bn_naming#_SUBINT_endCopyRem
!@@BN#_bn_naming#_SUBINT_copyRem:
!MOV dword [edi+ecx*4], eax
!CMP ecx, BIG_NUMBER#_bn_naming#_LONGS
!JB @@BN#_bn_naming#_SUBINT_endCopyRem
!@@:
!MOV eax, dword [esi+ecx*4]
!MOV dword [edi+ecx*4], eax
!INC ecx
!CMP ecx, BIG_NUMBER#_bn_naming#_LONGS
!JB @b
!@@BN#_bn_naming#_SUBINT_endCopyRem:
!end if
!BNPV_POP esi,edi
ProcedureReturn *dest
!@@BN#_bn_naming#_SUBINT_procend:
!MOV dword [edi], eax
!if BIG_NUMBER#_bn_naming#_LONGS > 1
!repeat BIG_NUMBER#_bn_naming#_LONGS-1
!MOV eax, dword [esi+%*4]
!MOV dword [edi+%*4], eax
!end repeat
!end if
!BNPV_POP esi,edi
ProcedureReturn *dest
EndProcedure
;____________________
; 9 9 9
; 9 9 9
;=-------------------
; 81 81 81
; 81 81 81
;+ 81 81 81
;=-------------------
; 81 162 243 162 81
;= 99 8 0 0 1
;____________________
;____________________
;
; 1 2 3
; 6 5 4
;=-------------------
; 4 8 12
; 5 10 15
;+ 6 12 18
;=-------------------
; 6 17 32 23 12
;= 8 0 4 4 2
;____________________
;- BN_MUL(*dest.BIG_NUMBER, *a.BIG_NUMBER, *b.BIG_NUMBER)
;- TODO: try Karatsuba algorithm or Schoenhage-Strassen-Algorithm if possible
Procedure.l BN#_bn_naming#_MUL(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#, dwordsA.l = -1, dwordsB.l = -1)
; Protected dwordsA.l, dwordsB.l
CompilerIf _bn_checkmem=#True
If *dest=0 Or *a=0 Or *b=0
ProcedureReturn 0
EndIf
CompilerEndIf
If dwordsA < 0
dwordsA = BN#_bn_naming#_USED_LONGS(*a)
EndIf
If dwordsB < 0
dwordsB = BN#_bn_naming#_USED_LONGS(*b)
EndIf
If dwordsA<dwordsB
Swap dwordsA, dwordsB
Swap *a, *b
EndIf
!BNPV_PUSH ebx,esi,edi,ebp
!BNPV_VARS p.v_iA, p.v_iB
!MOV esi, dword [p.p_a+BNPV_OFFSET]
!MOV ebp, dword [p.p_b+BNPV_OFFSET]
!MOV edi, dword [p.p_dest+BNPV_OFFSET]
!XOR eax, eax
!MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
!@@:
!MOV dword [edi+ecx*4], eax
!DEC ecx
!JNS @b
!CMP dword [p.v_dwordsA+BNPV_OFFSET], 0
!JBE @@BN#_bn_naming#_MUL_next1
!CMP dword [p.v_dwordsB+BNPV_OFFSET], 0
!JBE @@BN#_bn_naming#_MUL_next1
!@@BN#_bn_naming#_MUL_for1:
!MOV dword [p.v_iA], 0
!@@BN#_bn_naming#_MUL_for2:
!MOV ecx, dword [p.v_iA]
!ADD ecx, dword [p.v_iB] ;ecx = iA+iB
!CMP ecx, BIG_NUMBER#_bn_naming#_LONGS
!JAE @@BN#_bn_naming#_MUL_endif1
!MOV edx, dword [p.v_iB]
!MOV eax, dword [ebp+edx*4]
!MOV ebx, dword [p.v_iA]
!MUL dword [esi+ebx*4]
!ADD dword [edi+ecx*4], eax
!LAHF
!INC ecx
!CMP ecx, BIG_NUMBER#_bn_naming#_LONGS
!JAE @@BN#_bn_naming#_MUL_else2
!SAHF
!ADC dword [edi+ecx*4], edx
!JNC @@BN#_bn_naming#_MUL_endif2
!LAHF
!INC ecx
!@@:
!CMP ecx, BIG_NUMBER#_bn_naming#_LONGS
!JAE @f
!SAHF
!ADC dword [edi+ecx*4], 0
!LAHF
!INC ecx
!JC @b
!@@:
!SAHF
!JC @@BN#_bn_naming#_MUL_overflow
!JMP @@BN#_bn_naming#_MUL_endif2
!@@BN#_bn_naming#_MUL_else2:
!SAHF
!JC @@BN#_bn_naming#_MUL_overflow
!@@BN#_bn_naming#_MUL_endif2:
!@@BN#_bn_naming#_MUL_endif1:
!INC dword [p.v_iA]
!MOV eax, dword [p.v_iA]
!CMP dword [p.v_dwordsA+BNPV_OFFSET], eax
!JA @@BN#_bn_naming#_MUL_for2
!@@BN#_bn_naming#_MUL_next2:
!INC dword [p.v_iB]
!MOV eax, dword [p.v_iB]
!CMP dword [p.v_dwordsB+BNPV_OFFSET], eax
!JA @@BN#_bn_naming#_MUL_for1
!@@BN#_bn_naming#_MUL_next1:
!BNPV_FREEVARS
!BNPV_POP ebx,esi,edi,ebp
ProcedureReturn *dest
!@@BN#_bn_naming#_MUL_overflow:
!BNPV_FREEVARS
!BNPV_POP ebx,esi,edi,ebp
Debug _bn_qt()BN#_bn_naming#_MUL Overflow#_bn_qt()
ProcedureReturn 0
EndProcedure
;- BN_KARATSUBA(*dest.BIG_NUMBER, *a.BIG_NUMBER, *b.BIG_NUMBER)
;- TODO: rewrite optimized in asm
Procedure.l BN#_bn_naming#_KARATSUBA(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Protected *xH.BIG_NUMBER#_bn_naming#, *xL.BIG_NUMBER#_bn_naming#, *yH.BIG_NUMBER#_bn_naming#, *hL.BIG_NUMBER#_bn_naming#
Protected *P1.BIG_NUMBER#_bn_naming#, *P2.BIG_NUMBER#_bn_naming#, *P3.BIG_NUMBER#_bn_naming#
Protected dwordsA.l, dwordsB.l, n.l;, range.l
CompilerIf _bn_checkmem=#True
If *dest=0 Or *a=0 Or *b=0
ProcedureReturn 0
EndIf
CompilerEndIf
dwordsA = BN#_bn_naming#_USED_LONGS(*a)
dwordsB = BN#_bn_naming#_USED_LONGS(*b)
If dwordsA < dwordsB
n = dwordsB
Else
n = dwordsA
EndIf
range = Log(Sqr(#BIG_NUMBER#_bn_naming#_LONGS)) / Log(3)
If n <= #BIG_NUMBER#_bn_naming#_LONGS >> range Or n < 18
*dest = BN#_bn_naming#_MUL(*dest, *a, *b, dwordsA, dwordsB)
ElseIf n * 2 <= #BIG_NUMBER#_bn_naming#_LONGS
*xH = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#) * 7)
*xL = *xH + SizeOf(BIG_NUMBER#_bn_naming#)
*yH = *xL + SizeOf(BIG_NUMBER#_bn_naming#)
*yL = *yH + SizeOf(BIG_NUMBER#_bn_naming#)
*P1 = *yL + SizeOf(BIG_NUMBER#_bn_naming#)
*P2 = *P1 + SizeOf(BIG_NUMBER#_bn_naming#)
*P3 = *P2 + SizeOf(BIG_NUMBER#_bn_naming#)
If *xH = 0
ProcedureReturn 0
EndIf
n = n / 2
!BNPV_PUSH esi,edi
!MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
!@@BN#_bn_naming#_KARATSUBA_for1:
!CMP ecx, dword [p.v_n+BNPV_OFFSET]
!JB @f
!MOV edx, ecx
!SUB edx, dword [p.v_n+BNPV_OFFSET]
!MOV esi, dword [p.p_a+BNPV_OFFSET]
!MOV edi, dword [p.p_xH+BNPV_OFFSET]
!MOV eax, dword [esi+ecx*4]
!MOV dword [edi+edx*4], eax
!MOV esi, dword [p.p_b+BNPV_OFFSET]
!MOV edi, dword [p.p_yH+BNPV_OFFSET]
!MOV eax, dword [esi+ecx*4]
!MOV dword [edi+edx*4], eax
!@@:
!CMP ecx, dword [p.v_n+BNPV_OFFSET]
!JAE @f
!MOV esi, dword [p.p_a+BNPV_OFFSET]
!MOV edi, dword [p.p_xL+BNPV_OFFSET]
!MOV eax, dword [esi+ecx*4]
!MOV dword [edi+ecx*4], eax
!MOV esi, dword [p.p_b+BNPV_OFFSET]
!MOV edi, dword [p.p_yL+BNPV_OFFSET]
!MOV eax, dword [esi+ecx*4]
!MOV dword [edi+ecx*4], eax
!@@:
!DEC ecx
!JNS @@BN#_bn_naming#_KARATSUBA_for1
!BNPV_POP esi,edi
BN#_bn_naming#_KARATSUBA(*P1, *xH, *yH)
BN#_bn_naming#_KARATSUBA(*P2, *xL, *yL)
BN#_bn_naming#_ADD(*xL, *xL, *xH)
BN#_bn_naming#_ADD(*yL, *yL, *yH)
BN#_bn_naming#_KARATSUBA(*P3, *xL, *yL)
BN#_bn_naming#_SHL(*xH, *P1, 2 * n * 32)
BN#_bn_naming#_SUB(*xL, *P3, *P1) ;*
BN#_bn_naming#_SUB(*P3, *xL, *P2)
BN#_bn_naming#_SHL(*xL, *P3, n * 32)
BN#_bn_naming#_ADD(*P1, *xH, *xL) ;*
BN#_bn_naming#_ADD(*dest, *P1, *P2)
FreeMemory(*xH)
Else
*dest = 0
Debug _bn_qt()BN#_bn_naming#_KARATSUBA Overflow#_bn_qt()
EndIf
ProcedureReturn *dest
EndProcedure
;- BN_MULINT(*dest.BIG_NUMBER, *a.BIG_NUMBER, b.l)
Procedure.l BN#_bn_naming#_MULINT(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
Protected dwordsA.l
CompilerIf _bn_checkmem=#True
If *dest=0 Or *a=0
ProcedureReturn 0
EndIf
CompilerEndIf
dwordsA = BN#_bn_naming#_USED_LONGS(*a)
!BNPV_PUSH ebx,esi,edi
!BNPV_VARS p.v_iA
!MOV esi, dword [p.p_a+BNPV_OFFSET]
!MOV edi, dword [p.p_dest+BNPV_OFFSET]
!XOR eax, eax
!MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
!@@:
!MOV dword [edi+ecx*4], eax
!DEC ecx
!JNS @b
!CMP dword [p.v_b+BNPV_OFFSET], 0
!JBE @@BN#_bn_naming#_MULINT_endif0
!CMP dword [p.v_dwordsA+BNPV_OFFSET], 0
!JE @@BN#_bn_naming#_MULINT_endif0
!MOV dword [p.v_iA], 0
!@@BN#_bn_naming#_MULINT_for1:
!MOV ecx, dword [p.v_iA] ;ecx = iA
!CMP ecx, BIG_NUMBER#_bn_naming#_LONGS
!JAE @@BN#_bn_naming#_MULINT_endif1
!MOV eax, dword [p.v_b+BNPV_OFFSET]
!MOV ebx, dword [p.v_iA]
!MUL dword [esi+ebx*4]
!ADD dword [edi+ecx*4], eax
!LAHF
!INC ecx
!CMP ecx, BIG_NUMBER#_bn_naming#_LONGS
!JAE @@BN#_bn_naming#_MULINT_else2
!SAHF
!ADC dword [edi+ecx*4], edx
!JNC @@BN#_bn_naming#_MULINT_endif2
!LAHF
!INC ecx
!@@:
!CMP ecx, BIG_NUMBER#_bn_naming#_LONGS
!JAE @f
!SAHF
!ADC dword [edi+ecx*4], 0
!LAHF
!INC ecx
!JC @b
!@@:
!SAHF
!JC @@BN#_bn_naming#_MULINT_overflow
!JMP @@BN#_bn_naming#_MULINT_endif2
!@@BN#_bn_naming#_MULINT_else2:
!SAHF
!JC @@BN#_bn_naming#_MULINT_overflow
!@@BN#_bn_naming#_MULINT_endif2:
!@@BN#_bn_naming#_MULINT_endif1:
!INC dword [p.v_iA]
!MOV eax, dword [p.v_iA]
!CMP dword [p.v_dwordsA+BNPV_OFFSET], eax
!JA @@BN#_bn_naming#_MULINT_for1
!@@BN#_bn_naming#_MULINT_next2:
!@@BN#_bn_naming#_MULINT_endif0:
!BNPV_FREEVARS
!BNPV_POP ebx,esi,edi
ProcedureReturn *dest
!@@BN#_bn_naming#_MULINT_overflow:
!BNPV_FREEVARS
!BNPV_POP ebx,esi,edi
Debug _bn_qt()BN#_bn_naming#_MULINT Overflow#_bn_qt()
ProcedureReturn 0
EndProcedure
; base.l = 7
; exp.l = 13
;
; seed.l = exp
; result.q = 1
; tmp.q = base
; While seed>0
; Debug Bin(seed)
; If seed&1
; result*tmp
; EndIf
; tmp*tmp
; seed>>1
; Wend
;
; Debug Str(base)+"^"+Str(exp)+" = "+StrU(result,4)
;96889010407
;- BN_POW(*dest.BIG_NUMBER, *a.BIG_NUMBER, *b.BIG_NUMBER)
Procedure.l BN#_bn_naming#_POW(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Protected *seed.BIG_NUMBER#_bn_naming#, *tmp1.BIG_NUMBER#_bn_naming#, *tmp2.BIG_NUMBER#_bn_naming#, bits.l, i.l
CompilerIf _bn_checkmem=#True
If *dest=0 Or *a=0 Or *b=0
ProcedureReturn 0
EndIf
CompilerEndIf
BN#_bn_naming#_INT(*dest, 0)
If BN#_bn_naming#_CMPINT(*b, 0)=0
BN#_bn_naming#_INT(*dest, 1)
ElseIf BN#_bn_naming#_CMPINT(*a, 0)=1
*seed = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#)*3)
*tmp1 = *seed+SizeOf(BIG_NUMBER#_bn_naming#)
*tmp2 = *tmp1+SizeOf(BIG_NUMBER#_bn_naming#)
If *seed=0
ProcedureReturn 0
EndIf
bits = BN#_bn_naming#_USED_BITS(*b)
BN#_bn_naming#_MOV(*seed, *b)
BN#_bn_naming#_INT(*dest, 1)
BN#_bn_naming#_MOV(*tmp1, *a)
For i = 1 To bits
If *seed\n[0] & 1
BN#_bn_naming#_MUL(*tmp2, *dest, *tmp1)
BN#_bn_naming#_MOV(*dest, *tmp2)
EndIf
If i<>bits
BN#_bn_naming#_MUL(*tmp2, *tmp1, *tmp1)
BN#_bn_naming#_MOV(*tmp1, *tmp2)
BN#_bn_naming#_SHR1(*seed)
EndIf
Next
FreeMemory(*seed)
EndIf
ProcedureReturn *dest
EndProcedure
;- BN_POWINT(*dest.BIG_NUMBER, *a.BIG_NUMBER, b.l)
Procedure.l BN#_bn_naming#_POWINT(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
Protected *tmp1.BIG_NUMBER#_bn_naming#, *tmp2.BIG_NUMBER#_bn_naming#, seed.l
CompilerIf _bn_checkmem=#True
If *dest=0 Or *a=0 Or b<0
ProcedureReturn 0
EndIf
CompilerEndIf
BN#_bn_naming#_INT(*dest, 0)
If b=0
BN#_bn_naming#_INT(*dest, 1)
ElseIf BN#_bn_naming#_CMPINT(*a, 0)=1
*tmp1 = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#)*2)
*tmp2 = *tmp1+SizeOf(BIG_NUMBER#_bn_naming#)
If *tmp1=0
ProcedureReturn 0
EndIf
bits = BN#_bn_naming#_USED_BITS(*b)
seed = b
BN#_bn_naming#_INT(*dest, 1)
BN#_bn_naming#_MOV(*tmp1, *a)
While seed>0
If seed&1
BN#_bn_naming#_MUL(*tmp2, *dest, *tmp1)
BN#_bn_naming#_MOV(*dest, *tmp2)
EndIf
seed>>1
If seed
BN#_bn_naming#_MUL(*tmp2, *tmp1, *tmp1)
BN#_bn_naming#_MOV(*tmp1, *tmp2)
EndIf
Wend
FreeMemory(*tmp1)
EndIf
ProcedureReturn *dest
EndProcedure
;- BN_POW_MOD(*dest.BIG_NUMBER, *a.BIG_NUMBER, *b.BIG_NUMBER, *m.BIG_NUMBER)
Procedure.l BN#_bn_naming#_POW_MOD(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#, *m.BIG_NUMBER#_bn_naming#)
Protected *seed.BIG_NUMBER#_bn_naming#, *tmp1.BIG_NUMBER#_bn_naming#, *tmp2.BIG_NUMBER#_bn_naming#, bits.l, i.l
CompilerIf _bn_checkmem=#True
If *dest=0 Or *a=0 Or *b=0 Or *m=0
ProcedureReturn 0
EndIf
CompilerEndIf
BN#_bn_naming#_INT(*dest, 0)
If BN#_bn_naming#_CMPINT(*b, 0)=0
If BN#_bn_naming#_CMPINT(*m, 1)=1
BN#_bn_naming#_INT(*dest, 1)
EndIf
ElseIf BN#_bn_naming#_CMPINT(*a, 0)=1
*seed = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#)*3)
*tmp1 = *seed+SizeOf(BIG_NUMBER#_bn_naming#)
*tmp2 = *tmp1+SizeOf(BIG_NUMBER#_bn_naming#)
If *seed=0
ProcedureReturn 0
EndIf
bits = BN#_bn_naming#_USED_BITS(*b)
BN#_bn_naming#_MOV(*seed, *b)
BN#_bn_naming#_INT(*dest, 1)
BN#_bn_naming#_MOV(*tmp1, *a)
For i = 1 To bits
If *seed\n[0] & 1
BN#_bn_naming#_MUL(*tmp2, *dest, *tmp1)
BN#_bn_naming#_MOD(*dest, *tmp2, *m)
EndIf
If i<>bits
BN#_bn_naming#_MUL(*tmp2, *tmp1, *tmp1)
BN#_bn_naming#_MOD(*tmp1, *tmp2, *m)
BN#_bn_naming#_SHR1(*seed)
EndIf
Next
FreeMemory(*seed)
EndIf
ProcedureReturn *dest
EndProcedure
;- BN_POW_MODINT(*dest.BIG_NUMBER, *a.BIG_NUMBER, *b.BIG_NUMBER, m.l)
Procedure.l BN#_bn_naming#_POW_MODINT(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#, m.l)
Protected *seed.BIG_NUMBER#_bn_naming#, *tmp1.BIG_NUMBER#_bn_naming#, *tmp2.BIG_NUMBER#_bn_naming#, bits.l, i.l
CompilerIf _bn_checkmem=#True
If *dest=0 Or *a=0 Or *b=0
ProcedureReturn 0
EndIf
CompilerEndIf
BN#_bn_naming#_INT(*dest, 0)
If BN#_bn_naming#_CMPINT(*b, 0)=0
If m>1
BN#_bn_naming#_INT(*dest, 1)
EndIf
ElseIf BN#_bn_naming#_CMPINT(*a, 0)=1
*seed = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#)*3)
*tmp1 = *seed+SizeOf(BIG_NUMBER#_bn_naming#)
*tmp2 = *tmp1+SizeOf(BIG_NUMBER#_bn_naming#)
If *seed=0
ProcedureReturn 0
EndIf
bits = BN#_bn_naming#_USED_BITS(*b)
BN#_bn_naming#_MOV(*seed, *b)
BN#_bn_naming#_INT(*dest, 1)
BN#_bn_naming#_MOV(*tmp1, *a)
For i = 1 To bits
If *seed\n[0] & 1
BN#_bn_naming#_MUL(*tmp2, *dest, *tmp1)
BN#_bn_naming#_MODINT(*dest, *tmp2, m)
EndIf
If i<>bits
BN#_bn_naming#_MUL(*tmp2, *tmp1, *tmp1)
BN#_bn_naming#_MODINT(*tmp1, *tmp2, m)
BN#_bn_naming#_SHR1(*seed)
EndIf
Next
FreeMemory(*seed)
EndIf
ProcedureReturn *dest
EndProcedure
;- BN_SQR(*dest.BIG_NUMBER, *a.BIG_NUMBER)
Procedure.l BN#_bn_naming#_SQR(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#)
Protected *last.BIG_NUMBER#_bn_naming#, *rem.BIG_NUMBER#_bn_naming#, *tmp.BIG_NUMBER#_bn_naming#, Result.q, Last.q, n.q
CompilerIf _bn_checkmem=#True
If *dest=0 Or *a=0
ProcedureReturn 0
EndIf
CompilerEndIf
If BN#_bn_naming#_USED_LONGS(*a) = 1
!MOV dword [p.v_n+4], 0
!MOV dword [p.v_Result+4], 0
!MOV edx, dword [p.p_a]
!MOV eax, dword [edx]
!MOV dword [p.v_n], eax
!SHR eax, 1
!MOV dword [p.v_Result], eax
If Result < 2
If Result < 1
BN#_bn_naming#_INT(*dest, 0)
Else
BN#_bn_naming#_INT(*dest, 1)
EndIf
ProcedureReturn *dest
EndIf
Repeat
Last = Result
Result = (Result + (n / Result)) / 2
Until Last <= Result
BN#_bn_naming#_INT(*dest, Last)
Else
*last = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#) * 3)
*rem = *last + SizeOf(BIG_NUMBER#_bn_naming#)
*tmp = *rem + SizeOf(BIG_NUMBER#_bn_naming#)
If *last = 0
ProcedureReturn 0
EndIf
BN#_bn_naming#_MOV(*dest, *a)
BN#_bn_naming#_SHR1(*dest)
Repeat
BN#_bn_naming#_MOV(*last, *dest)
BN#_bn_naming#_DIV(*tmp, *rem, *a, *dest)
BN#_bn_naming#_ADD(*dest, *dest, *tmp)
BN#_bn_naming#_SHR1(*dest)
Until BN#_bn_naming#_CMP(*last, *dest) <= 0
BN#_bn_naming#_MOV(*dest, *last)
FreeMemory(*last)
EndIf
ProcedureReturn *dest
EndProcedure
;div as you know from school.. just with binary numbers
;- BN_DIV(*dest.BIG_NUMBER, *destRem.BIG_NUMBER, *a.BIG_NUMBER, *b.BIG_NUMBER)
;- TODO: rewrite in assembler (IMPORTANT)
Procedure.l BN#_bn_naming#_DIV(*dest.BIG_NUMBER#_bn_naming#, *destRem.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Protected *seed.BIG_NUMBER#_bn_naming#, *tmp.BIG_NUMBER#_bn_naming#, i.l, offset.l, bitsInB.l
CompilerIf _bn_checkmem=#True
If *dest=0 Or *destRem=0 Or *a=0 Or *b=0
ProcedureReturn 0
EndIf
CompilerEndIf
!BNPV_PUSH esi,edi
!MOV esi, dword [p.p_destRem+BNPV_OFFSET]
!MOV edi, dword [p.p_dest+BNPV_OFFSET]
!XOR eax, eax
CompilerIf _bn_size_optimized
!MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
!@@:
!MOV dword [esi+ecx*4], eax
!MOV dword [edi+ecx*4], eax
!DEC ecx
!JNS @b
CompilerElse
!repeat BIG_NUMBER#_bn_naming#_LONGS
!MOV dword [esi+(%-1)*4], eax
!MOV dword [edi+(%-1)*4], eax
!end repeat
CompilerEndIf
!BNPV_POP esi,edi
If BN#_bn_naming#_CMPINT(*a, 0)=0
ProcedureReturn *dest
ElseIf BN#_bn_naming#_CMPINT(*b, 0)=0
ProcedureReturn 0
EndIf
Select BN#_bn_naming#_CMP(*a, *b)
Case -1 ;a<b
BN#_bn_naming#_MOV(*destRem, *a)
ProcedureReturn *dest
Case 0 ;a=b
*dest\n[0] = 1
ProcedureReturn *dest
Case 1 ;a>b
bitsInB = BN#_bn_naming#_USED_BITS(*b)
If bitsInB<=32
ProcedureReturn BN#_bn_naming#_DIVINT(*dest, *destRem, *a, *b\n[0])
Else
*seed = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#)*2)
*tmp = *seed+SizeOf(BIG_NUMBER#_bn_naming#)
If *seed=0
ProcedureReturn 0
EndIf
offset = BN#_bn_naming#_USED_BITS(*a) - bitsInB
BN#_bn_naming#_SHL(*seed, *b, offset)
BN#_bn_naming#_MOV(*destRem, *a)
For i=0 To offset
BN#_bn_naming#_SHL1(*dest)
If BN#_bn_naming#_CMP(*seed, *destRem)<=0
BN#_bn_naming#_SUB(*tmp, *destRem, *seed)
BN#_bn_naming#_MOV(*destRem, *tmp)
*dest\n[0] | 1
EndIf
BN#_bn_naming#_SHR1(*seed)
Next
FreeMemory(*seed)
EndIf
EndSelect
ProcedureReturn *dest
EndProcedure
;- BN_DIVINT(*dest.BIG_NUMBER, *destRem.BIG_NUMBER, *a.BIG_NUMBER, b.l)
Procedure.l BN#_bn_naming#_DIVINT(*dest.BIG_NUMBER#_bn_naming#, *destRem.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
CompilerIf _bn_checkmem=#True
If *dest=0 Or *destRem=0 Or *a=0
ProcedureReturn 0
EndIf
CompilerEndIf
!BNPV_PUSH esi,edi
!MOV esi, dword [p.p_destRem+BNPV_OFFSET]
!MOV edi, dword [p.p_dest+BNPV_OFFSET]
!XOR eax, eax
CompilerIf _bn_size_optimized
!MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
!@@:
!MOV dword [esi+ecx*4], eax
!MOV dword [edi+ecx*4], eax
!DEC ecx
!JNS @b
CompilerElse
!repeat BIG_NUMBER#_bn_naming#_LONGS
!MOV dword [esi+(%-1)*4], eax
!MOV dword [edi+(%-1)*4], eax
!end repeat
CompilerEndIf
!BNPV_POP esi,edi
If BN#_bn_naming#_CMPINT(*a, 0)=0
ProcedureReturn *dest
ElseIf b=0
ProcedureReturn 0
EndIf
Select BN#_bn_naming#_CMPINT(*a, b)
Case -1 ;a<b
BN#_bn_naming#_MOV(*destRem, *a)
ProcedureReturn *dest
Case 0 ;a=b
*dest\n[0] = 1
ProcedureReturn *dest
Case 1 ;a>b
!BNPV_PUSH esi,edi,ebx
!MOV esi, dword [p.p_a+BNPV_OFFSET]
!MOV edi, dword [p.p_dest+BNPV_OFFSET]
!MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
!@@:
!CMP dword [esi+ecx*4], 0
!JNE @f
!DEC ecx
!JNS @b
!@@:
!CMP ecx, 0
!JL @@BN#_bn_naming#_DIVINT_endif1
!XOR eax, eax
!XOR edx, edx
!MOV ebx, dword [p.v_b+BNPV_OFFSET]
!@@:
!MOV eax, dword [esi+ecx*4]
!DIV ebx
!MOV dword [edi+ecx*4], eax
!MOV eax, edx
!DEC ecx
!JNS @b
!MOV edi, dword [p.p_destRem+BNPV_OFFSET]
!MOV dword [edi], edx
!@@BN#_bn_naming#_DIVINT_endif1:
!BNPV_POP esi,edi,ebx
EndSelect
ProcedureReturn *dest
EndProcedure
;- BN_MOD(*dest.BIG_NUMBER, *a.BIG_NUMBER, *b.BIG_NUMBER)
Procedure.l BN#_bn_naming#_MOD(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Protected *tmp.BIG_NUMBER#_bn_naming#, result.l
CompilerIf _bn_checkmem=#True
If *dest=0 Or *a=0 Or *b=0
ProcedureReturn 0
EndIf
CompilerEndIf
*tmp = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#))
If *tmp=0 : ProcedureReturn 0 : EndIf
result = BN#_bn_naming#_DIV(*tmp, *dest, *a, *b)
FreeMemory(*tmp)
If result=0
ProcedureReturn 0
Else
ProcedureReturn *dest
EndIf
EndProcedure
;- BN_MODINT(*dest.BIG_NUMBER, *a.BIG_NUMBER, b.l)
Procedure.l BN#_bn_naming#_MODINT(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
CompilerIf _bn_checkmem=#True
If *dest=0 Or *a=0
ProcedureReturn 0
EndIf
CompilerEndIf
!BNPV_PUSH edi
!MOV edi, dword [p.p_dest+BNPV_OFFSET]
!XOR eax, eax
CompilerIf _bn_size_optimized
!MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
!@@:
!MOV dword [edi+ecx*4], eax
!DEC ecx
!JNS @b
CompilerElse
!repeat BIG_NUMBER#_bn_naming#_LONGS
!MOV dword [edi+(%-1)*4], eax
!end repeat
CompilerEndIf
!BNPV_POP edi
If BN#_bn_naming#_CMPINT(*a, 0)=0
ProcedureReturn *dest
ElseIf b=0
ProcedureReturn 0
EndIf
Select BN#_bn_naming#_CMPINT(*a, b)
Case -1 ;a<b
BN#_bn_naming#_MOV(*dest, *a)
ProcedureReturn *dest
Case 0 ;a=b
ProcedureReturn *dest
Case 1 ;a>b
!BNPV_PUSH esi,edi,ebx
!MOV esi, dword [p.p_a+BNPV_OFFSET]
!MOV edi, dword [p.p_dest+BNPV_OFFSET]
!MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
!@@:
!CMP dword [esi+ecx*4], 0
!JNE @f
!DEC ecx
!JNS @b
!@@:
!CMP ecx, 0
!JL @@BN#_bn_naming#_MODINT_endif1
!XOR eax, eax
!XOR edx, edx
!MOV ebx, dword [p.v_b+BNPV_OFFSET]
!@@:
!MOV eax, dword [esi+ecx*4]
!DIV ebx
!MOV eax, edx
!DEC ecx
!JNS @b
!MOV dword [edi], edx
!@@BN#_bn_naming#_MODINT_endif1:
!BNPV_POP esi,edi,ebx
EndSelect
ProcedureReturn *dest
EndProcedure
; Procedure.q GCD(a.q, b.q)
; Protected shift.l, diff.q
; If a=0 Or b=0
; ProcedureReturn a | b
; EndIf
; shift = 0
; While ((a | b) & 1) = 0
; a >> 1
; b >> 1
; shift + 1
; Wend
; While (a & 1) = 0
; a >> 1
; Wend
; Repeat
; While (b & 1) = 0
; b >> 1
; Wend
; If a <= b
; b - a
; Else
; diff = a - b
; a = b
; b = diff
; EndIf
; b >> 1
; Until b = 0
; ProcedureReturn a << shift
; EndProcedure
;- BN_GCD(*dest.BIG_NUMBER, *b.BIG_NUMBER, *n.BIG_NUMBER)
Procedure.l BN#_bn_naming#_GCD(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
Protected shift.l, *atmp.BIG_NUMBER#_bn_naming#, *btmp.BIG_NUMBER#_bn_naming#
CompilerIf _bn_checkmem=#True
If *dest=0 Or *a=0 Or *b=0
ProcedureReturn 0
EndIf
CompilerEndIf
If BN#_bn_naming#_CMPINT(*a, 0)=0
BN#_bn_naming#_MOV(*dest, *b)
ProcedureReturn *dest
ElseIf BN#_bn_naming#_CMPINT(*b, 0)=0
BN#_bn_naming#_MOV(*dest, *a)
ProcedureReturn *dest
EndIf
*atmp = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#)*2)
*btmp = *atmp+SizeOf(BIG_NUMBER#_bn_naming#)
If *atmp=0
ProcedureReturn 0
EndIf
shift = 0
BN#_bn_naming#_MOV(*atmp, *a)
BN#_bn_naming#_MOV(*btmp, *b)
While ((*atmp\n[0] | *btmp\n[0]) & 1) = 0
BN#_bn_naming#_SHR1(*atmp)
BN#_bn_naming#_SHR1(*btmp)
shift + 1
Wend
While (*atmp\n[0] & 1) = 0
BN#_bn_naming#_SHR1(*atmp)
Wend
Repeat
While (*btmp\n[0] & 1) = 0
BN#_bn_naming#_SHR1(*btmp)
Wend
If BN#_bn_naming#_CMP(*atmp, *btmp)<=0
BN#_bn_naming#_SUB(*dest, *btmp, *atmp)
BN#_bn_naming#_MOV(*btmp, *dest)
Else
BN#_bn_naming#_SUB(*dest, *atmp, *btmp)
BN#_bn_naming#_MOV(*atmp, *btmp)
BN#_bn_naming#_MOV(*btmp, *dest)
EndIf
Until BN#_bn_naming#_CMPINT(*btmp, 0)=0
BN#_bn_naming#_SHL(*dest, *atmp, shift)
FreeMemory(*atmp)
ProcedureReturn *dest
EndProcedure
; Procedure.q invMod(b.q, n.q)
; Protected b0.q, n0.q, t0.q, t.q, q.q, r.q, temp.q
; b0 = b
; n0 = n
; t0 = 0
; t = 1
; q = Round(n0 / b0,0)
; r = n0 % b0
; While r > 0
; If t0 >= q * t
; temp = (t0 - (q * t)) % n
; Else
; temp = n - (((q * t) - t0) % n)
; EndIf
; t0 = t
; t = temp
; n0 = b0
; b0 = r
; q = Round(n0 / b0,0)
; r = n0 % b0
; Wend
; If b0 <> 1
; ProcedureReturn -1 ;b has no inverse to modulo n
; Else
; ProcedureReturn t % n
; EndIf
; EndProcedure
;- BN_INV_MOD(*dest.BIG_NUMBER, *b.BIG_NUMBER, *n.BIG_NUMBER)
Procedure.l BN#_bn_naming#_INV_MOD(*dest.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#, *n.BIG_NUMBER#_bn_naming#)
Protected *b0.BIG_NUMBER#_bn_naming#, *n0.BIG_NUMBER#_bn_naming#, *t0.BIG_NUMBER#_bn_naming#, *t.BIG_NUMBER#_bn_naming#, *q.BIG_NUMBER#_bn_naming#, *r.BIG_NUMBER#_bn_naming#, *tmp.BIG_NUMBER#_bn_naming#, Result.l
CompilerIf _bn_checkmem=#True
If *dest=0 Or *b=0 Or *n=0
ProcedureReturn 0
EndIf
CompilerEndIf
*b0 = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#)*7)
*n0 = *b0+SizeOf(BIG_NUMBER#_bn_naming#)
*t0 = *n0+SizeOf(BIG_NUMBER#_bn_naming#)
*t = *t0+SizeOf(BIG_NUMBER#_bn_naming#)
*q = *t+SizeOf(BIG_NUMBER#_bn_naming#)
*r = *q+SizeOf(BIG_NUMBER#_bn_naming#)
*tmp = *r+SizeOf(BIG_NUMBER#_bn_naming#)
If *b0=0
ProcedureReturn 0
EndIf
BN#_bn_naming#_MOV(*b0, *b)
BN#_bn_naming#_MOV(*n0, *n)
BN#_bn_naming#_INT(*t0, 0)
BN#_bn_naming#_INT(*t, 1)
BN#_bn_naming#_DIV(*q, *r, *n0, *b0)
While BN#_bn_naming#_CMPINT(*r,0)=1
BN#_bn_naming#_MUL(*tmp, *q, *t)
If BN#_bn_naming#_CMP(*t0, *tmp)>=0
BN#_bn_naming#_SUB(*dest, *t0, *tmp)
BN#_bn_naming#_MOD(*tmp, *dest, *n)
Else
BN#_bn_naming#_SUB(*dest, *tmp, *t0)
BN#_bn_naming#_MOD(*tmp, *dest, *n)
BN#_bn_naming#_SUB(*dest, *n, *tmp)
BN#_bn_naming#_MOV(*tmp, *dest)
EndIf
BN#_bn_naming#_MOV(*t0, *t)
BN#_bn_naming#_MOV(*t, *tmp)
BN#_bn_naming#_MOV(*n0, *b0)
BN#_bn_naming#_MOV(*b0, *r)
BN#_bn_naming#_DIV(*q, *r, *n0, *b0)
Wend
If BN#_bn_naming#_CMPINT(*b0, 1)=1
Result = 0
Else
Result = *dest
BN#_bn_naming#_MOD(*dest, *t, *n)
EndIf
FreeMemory(*b0)
ProcedureReturn Result
EndProcedure
;- BN_RND(*dest.BIG_NUMBER)
Procedure.l BN#_bn_naming#_RND(*dest.BIG_NUMBER#_bn_naming#)
!if 0 ;make pb include the lib for Random()
Random(1)
!end if
CompilerIf _bn_checkmem=#True
If *dest=0
ProcedureReturn 0
EndIf
CompilerEndIf
CompilerIf _bn_size_optimized
Protected i.l
!MOV dword [p.v_i], BIG_NUMBER#_bn_naming#_LONGS-1
!@@:
; !MOV eax, $FFFF
; !CALL PB_Random
!PUSH $FFFF
!CALL _PB_Random@4
!MOV edx, dword [p.p_dest]
!MOV ecx, dword [p.v_i]
!MOV word [edx+ecx*4], ax
; !MOV eax, $FFFF
; !CALL PB_Random
!PUSH $FFFF
!CALL _PB_Random@4
!MOV edx, dword [p.p_dest]
!MOV ecx, dword [p.v_i]
!MOV word [edx+ecx*4+2], ax
!DEC dword [p.v_i]
!JNS @b
CompilerElse
!repeat BIG_NUMBER#_bn_naming#_LONGS*2
; !MOV eax, $FFFF
; !CALL PB_Random
!PUSH $FFFF
!CALL _PB_Random@4
!MOV edx, dword [p.p_dest]
!MOV word [edx+(%-1)*2], ax
!end repeat
CompilerEndIf
ProcedureReturn *dest
EndProcedure
;- BN_RND_MAX(*dest.BIG_NUMBER, bits.l)
Procedure.l BN#_bn_naming#_RND_MAX(*dest.BIG_NUMBER#_bn_naming#, bits.l)
!if 0 ;make pb include the lib for Random()
Random(1)
!end if
CompilerIf _bn_checkmem=#True
If *dest=0
ProcedureReturn 0
EndIf
CompilerEndIf
!MOV ecx, dword [p.v_bits]
!SHR ecx, 5
!CMP ecx, BIG_NUMBER#_bn_naming#_LONGS-1
!JA @@BN#_bn_naming#_RND_MAX_next1
!XOR eax, eax
!MOV edx, dword [p.p_dest]
!@@:
!MOV dword [edx+ecx*4], eax
!INC ecx
!CMP ecx, BIG_NUMBER#_bn_naming#_LONGS-1
!JBE @b
!@@BN#_bn_naming#_RND_MAX_next1:
!MOV ecx, dword [p.v_bits]
!SHR ecx, 4
!JZ @@BN#_bn_naming#_RND_MAX_endif1
!DEC ecx
!@@:
!PUSH ecx
; !MOV eax, $FFFF
; !CALL PB_Random
!PUSH $FFFF
!CALL _PB_Random@4
!POP ecx
!MOV edx, dword [p.p_dest]
!MOV word [edx+ecx*2], ax
!DEC ecx
!JNS @b
!@@BN#_bn_naming#_RND_MAX_endif1:
; !MOV eax, $FFFF
; !CALL PB_Random
!PUSH $FFFF
!CALL _PB_Random@4
!MOV edx, eax
!MOV eax, dword [p.v_bits]
!MOV ecx, eax
!SHR eax, 4
!AND ecx, $0000000F
!JZ @@BN#_bn_naming#_RND_MAX_endif2
!NEG ecx
!ADD ecx, $00000010
!SHR edx, cl
!MOV ecx, dword [p.p_dest]
!MOV word [ecx+eax*2], dx
!@@BN#_bn_naming#_RND_MAX_endif2:
ProcedureReturn *dest
EndProcedure
;- BN_MOV(*dest.BIG_NUMBER, *a.BIG_NUMBER)
Procedure.l BN#_bn_naming#_MOV(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#)
CompilerIf _bn_checkmem=#True
If *dest=0 Or *a=0
ProcedureReturn 0
EndIf
CompilerEndIf
!BNPV_PUSH esi,edi
!MOV esi, dword [p.p_a+BNPV_OFFSET]
!MOV edi, dword [p.p_dest+BNPV_OFFSET]
CompilerIf _bn_size_optimized
!MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
!@@:
!MOV eax, dword [esi+ecx*4]
!MOV dword [edi+ecx*4], eax
!DEC ecx
!JNS @b
CompilerElse
!repeat BIG_NUMBER#_bn_naming#_LONGS
!MOV eax, dword [esi+(%-1)*4]
!MOV dword [edi+(%-1)*4], eax
!end repeat
CompilerEndIf
!BNPV_POP esi,edi
ProcedureReturn *dest
EndProcedure
;- BN_NOT(*dest.BIG_NUMBER)
Procedure.l BN#_bn_naming#_NOT(*dest.BIG_NUMBER#_bn_naming#)
CompilerIf _bn_checkmem=#True
If *dest=0
ProcedureReturn 0
EndIf
CompilerEndIf
!BNPV_PUSH edi
!MOV edi, dword [p.p_dest+BNPV_OFFSET]
CompilerIf _bn_size_optimized
!MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
!@@:
!NOT dword [edi+ecx*4]
!DEC ecx
!JNS @b
CompilerElse
!repeat BIG_NUMBER#_bn_naming#_LONGS
!NOT dword [edi+(%-1)*4]
!end repeat
CompilerEndIf
!BNPV_POP edi
ProcedureReturn *dest
EndProcedure
;- BN_AND(*dest.BIG_NUMBER, *a.BIG_NUMBER, *b.BIG_NUMBER)
Procedure.l BN#_bn_naming#_AND(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
CompilerIf _bn_checkmem=#True
If *dest=0 Or *a=0 Or *b=0
ProcedureReturn 0
EndIf
CompilerEndIf
!BNPV_PUSH esi,edi
!MOV esi, dword [p.p_a+BNPV_OFFSET]
!MOV edx, dword [p.p_b+BNPV_OFFSET]
!MOV edi, dword [p.p_dest+BNPV_OFFSET]
CompilerIf _bn_size_optimized
!MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
!@@:
!MOV eax, dword [esi+ecx*4]
!AND eax, dword [edx+ecx*4]
!MOV dword [edi+ecx*4], eax
!DEC ecx
!JNS @b
CompilerElse
!repeat BIG_NUMBER#_bn_naming#_LONGS
!MOV eax, dword [esi+(%-1)*4]
!AND eax, dword [edx+(%-1)*4]
!MOV dword [edi+(%-1)*4], eax
!end repeat
CompilerEndIf
!BNPV_POP esi,edi
ProcedureReturn *dest
EndProcedure
;- BN_OR(*dest.BIG_NUMBER, *a.BIG_NUMBER, *b.BIG_NUMBER)
Procedure.l BN#_bn_naming#_OR(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
CompilerIf _bn_checkmem=#True
If *dest=0 Or *a=0 Or *b=0
ProcedureReturn 0
EndIf
CompilerEndIf
!BNPV_PUSH esi,edi
!MOV esi, dword [p.p_a+BNPV_OFFSET]
!MOV edx, dword [p.p_b+BNPV_OFFSET]
!MOV edi, dword [p.p_dest+BNPV_OFFSET]
CompilerIf _bn_size_optimized
!MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
!@@:
!MOV eax, dword [esi+ecx*4]
!OR eax, dword [edx+ecx*4]
!MOV dword [edi+ecx*4], eax
!DEC ecx
!JNS @b
CompilerElse
!repeat BIG_NUMBER#_bn_naming#_LONGS
!MOV eax, dword [esi+(%-1)*4]
!OR eax, dword [edx+(%-1)*4]
!MOV dword [edi+(%-1)*4], eax
!end repeat
CompilerEndIf
!BNPV_POP esi,edi
ProcedureReturn *dest
EndProcedure
;- BN_XOR(*dest.BIG_NUMBER, *a.BIG_NUMBER, *b.BIG_NUMBER)
Procedure.l BN#_bn_naming#_XOR(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
CompilerIf _bn_checkmem=#True
If *dest=0 Or *a=0 Or *b=0
ProcedureReturn 0
EndIf
CompilerEndIf
!BNPV_PUSH esi,edi
!MOV esi, dword [p.p_a+BNPV_OFFSET]
!MOV edx, dword [p.p_b+BNPV_OFFSET]
!MOV edi, dword [p.p_dest+BNPV_OFFSET]
CompilerIf _bn_size_optimized
!MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
!@@:
!MOV eax, dword [esi+ecx*4]
!XOR eax, dword [edx+ecx*4]
!MOV dword [edi+ecx*4], eax
!DEC ecx
!JNS @b
CompilerElse
!repeat BIG_NUMBER#_bn_naming#_LONGS
!MOV eax, dword [esi+(%-1)*4]
!XOR eax, dword [edx+(%-1)*4]
!MOV dword [edi+(%-1)*4], eax
!end repeat
CompilerEndIf
!BNPV_POP esi,edi
ProcedureReturn *dest
EndProcedure
;- BN_SHL(*dest.BIG_NUMBER, *a.BIG_NUMBER, b.l)
Procedure.l BN#_bn_naming#_SHL(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
CompilerIf _bn_checkmem=#True
If *dest=0 Or *a=0
ProcedureReturn 0
EndIf
CompilerEndIf
!BNPV_PUSH ebx,esi,edi
!MOV esi, dword [p.p_a+BNPV_OFFSET]
!MOV edi, dword [p.p_dest+BNPV_OFFSET]
!CMP dword [p.v_b+BNPV_OFFSET], 32
!JB @@BN#_bn_naming#_SHL_endif1
!XOR eax, eax
CompilerIf _bn_size_optimized
!MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
!@@:
!MOV dword [edi+ecx*4], eax
!DEC ecx
!JNS @b
CompilerElse
!repeat BIG_NUMBER#_bn_naming#_LONGS
!MOV dword [edi+(%-1)*4], eax
!end repeat
CompilerEndIf
!@@BN#_bn_naming#_SHL_endif1:
!XOR edx, edx
!MOV eax, dword [p.v_b+BNPV_OFFSET]
!SHR eax, 5
!MOV ebx, BIG_NUMBER#_bn_naming#_LONGS-1
!MOV ecx, ebx
!SUB ecx, eax
!JS @@BN#_bn_naming#_SHL_next1
!@@BN#_bn_naming#_SHL_for1:
!MOV eax, dword [esi+ecx*4]
!MOV dword [edi+ebx*4], eax
!DEC ebx
!DEC ecx
!JNS @@BN#_bn_naming#_SHL_for1
!@@BN#_bn_naming#_SHL_next1:
;progress edx (= b mod 32)
!MOV edx, dword [p.v_b+BNPV_OFFSET]
!AND edx, $0000001F
!MOV ecx, edx
!CMP ecx, 0
!JE @@BN#_bn_naming#_SHL_endproc
!BN#_bn_naming#_SHL_a = BIG_NUMBER#_bn_naming#_LONGS-1
!MOV edx, dword [edi+BN#_bn_naming#_SHL_a*4]
!while BN#_bn_naming#_SHL_a > 0
!MOV eax, dword [edi+BN#_bn_naming#_SHL_a*4-4]
!SHLD edx, eax, cl
!MOV dword [edi+BN#_bn_naming#_SHL_a*4], edx
!MOV edx, eax
!BN#_bn_naming#_SHL_a = BN#_bn_naming#_SHL_a - 1
!end while
!MOV eax, dword [edi]
!SHL eax, cl
!MOV dword [edi], eax
!@@BN#_bn_naming#_SHL_endproc:
!BNPV_POP ebx,esi,edi
ProcedureReturn *dest
EndProcedure
;- BN_SHL1(*dest.BIG_NUMBER)
Procedure.l BN#_bn_naming#_SHL1(*dest.BIG_NUMBER#_bn_naming#)
CompilerIf _bn_checkmem=#True
If *dest=0
ProcedureReturn 0
EndIf
CompilerEndIf
!MOV eax, dword [p.p_dest]
!SHL dword [eax], 1
!if BIG_NUMBER#_bn_naming#_LONGS>1
CompilerIf _bn_size_optimized
!MOV ecx, 1
!@@:
!RCL dword [eax+ecx*4], 1
!INC ecx
!CMP ecx, BIG_NUMBER#_bn_naming#_LONGS-1
!JBE @b
CompilerElse
!repeat BIG_NUMBER#_bn_naming#_LONGS-1
!RCL dword [eax+%*4], 1
!end repeat
CompilerEndIf
!end if
ProcedureReturn *dest
EndProcedure
;- BN_SHR(*dest.BIG_NUMBER, *a.BIG_NUMBER, b.l)
Procedure.l BN#_bn_naming#_SHR(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#, b.l)
CompilerIf _bn_checkmem=#True
If *dest=0 Or *a=0
ProcedureReturn 0
EndIf
CompilerEndIf
!BNPV_PUSH ebx,esi,edi
!MOV esi, dword [p.p_a+BNPV_OFFSET]
!MOV edi, dword [p.p_dest+BNPV_OFFSET]
!CMP dword [p.v_b+BNPV_OFFSET], 32
!JB @@BN#_bn_naming#_SHR_endif1
!XOR eax, eax
!repeat BIG_NUMBER#_bn_naming#_LONGS
!MOV dword [edi+(%-1)*4], eax
!end repeat
!@@BN#_bn_naming#_SHR_endif1:
!XOR edx, edx
!MOV eax, dword [p.v_b+BNPV_OFFSET]
!SHR eax, 5
!XOR ecx, ecx
!MOV ebx, eax
!CMP ebx, BIG_NUMBER#_bn_naming#_LONGS-1
!JA @@BN#_bn_naming#_SHR_next1
!@@BN#_bn_naming#_SHR_for1:
!MOV eax, dword [esi+ebx*4]
!MOV dword [edi+ecx*4], eax
!INC ecx
!INC ebx
!CMP ebx, BIG_NUMBER#_bn_naming#_LONGS-1
!JBE @@BN#_bn_naming#_SHR_for1
!@@BN#_bn_naming#_SHR_next1:
;progress edx (= b mod 32)
!MOV edx, dword [p.v_b+BNPV_OFFSET]
!AND edx, $0000001F
!MOV ecx, edx
!CMP ecx, 0
!JE @@BN#_bn_naming#_SHR_endproc
!BN#_bn_naming#_SHR_a = 0
!MOV eax, dword [edi]
!while BN#_bn_naming#_SHR_a < BIG_NUMBER#_bn_naming#_LONGS-1
!MOV edx, dword [edi+BN#_bn_naming#_SHR_a*4+4]
!SHRD eax, edx, cl
!MOV dword [edi+BN#_bn_naming#_SHR_a*4], eax
!MOV eax, edx
!BN#_bn_naming#_SHR_a = BN#_bn_naming#_SHR_a + 1
!end while
!MOV eax, dword [edi+(BIG_NUMBER#_bn_naming#_LONGS-1)*4]
!SHR eax, cl
!MOV dword [edi+(BIG_NUMBER#_bn_naming#_LONGS-1)*4], eax
!@@BN#_bn_naming#_SHR_endproc:
!BNPV_POP ebx,esi,edi
ProcedureReturn *dest
EndProcedure
;- BN_SHR1(*dest.BIG_NUMBER)
Procedure.l BN#_bn_naming#_SHR1(*dest.BIG_NUMBER#_bn_naming#)
CompilerIf _bn_checkmem=#True
If *dest=0
ProcedureReturn 0
EndIf
CompilerEndIf
!MOV eax, dword [p.p_dest]
!SHR dword [eax+BIG_NUMBER#_bn_naming#_LONGS*4-4], 1
!if BIG_NUMBER#_bn_naming#_LONGS>1
CompilerIf _bn_size_optimized
!MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-2
!@@:
!RCR dword [eax+ecx*4], 1
!DEC ecx
!JNS @b
CompilerElse
!repeat BIG_NUMBER#_bn_naming#_LONGS-1
!RCR dword [eax+BIG_NUMBER#_bn_naming#_LONGS*4-%*4-4], 1
!end repeat
CompilerEndIf
!end if
ProcedureReturn *dest
EndProcedure
;- BN_CMP(*a.BIG_NUMBER, *b.BIG_NUMBER)
Procedure.l BN#_bn_naming#_CMP(*a.BIG_NUMBER#_bn_naming#, *b.BIG_NUMBER#_bn_naming#)
CompilerIf _bn_checkmem=#True
If *a=0 Or *b=0
ProcedureReturn -2
EndIf
CompilerEndIf
!BNPV_PUSH esi,edi
!MOV esi, dword [p.p_a+BNPV_OFFSET]
!MOV edi, dword [p.p_b+BNPV_OFFSET]
CompilerIf _bn_size_optimized
!MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
!@@:
!MOV eax, dword [esi+ecx*4]
!CMP eax, dword [edi+ecx*4]
!JB @@BN#_bn_naming#_CMP_aLTb
!JA @@BN#_bn_naming#_CMP_aGTb
!DEC ecx
!JNS @b
CompilerElse
!repeat BIG_NUMBER#_bn_naming#_LONGS
!MOV eax, dword [esi+(BIG_NUMBER#_bn_naming#_LONGS-%)*4]
!CMP eax, dword [edi+(BIG_NUMBER#_bn_naming#_LONGS-%)*4]
!JB @@BN#_bn_naming#_CMP_aLTb
!JA @@BN#_bn_naming#_CMP_aGTb
!end repeat
CompilerEndIf
!@@BN#_bn_naming#_CMP_aEQb:
!BNPV_POP esi,edi
ProcedureReturn 0
!@@BN#_bn_naming#_CMP_aLTb:
!BNPV_POP esi,edi
ProcedureReturn -1
!@@BN#_bn_naming#_CMP_aGTb:
!BNPV_POP esi,edi
ProcedureReturn 1
EndProcedure
;- BN_CMPINT(*a.BIG_NUMBER, b.l)
Procedure.l BN#_bn_naming#_CMPINT(*a.BIG_NUMBER#_bn_naming#, b.l)
CompilerIf _bn_checkmem=#True
If *a=0
ProcedureReturn -2
EndIf
CompilerEndIf
!BNPV_PUSH esi
!MOV esi, dword [p.p_a+BNPV_OFFSET]
!XOR eax, eax
CompilerIf _bn_size_optimized
!MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
!MOV edx, 1
!@@:
!CMP dword [esi+edx*4], eax
!JNE @@BN#_bn_naming#_CMPINT_aGTb
!INC edx
!DEC ecx
!JNZ @b
CompilerElse
!repeat BIG_NUMBER#_bn_naming#_LONGS-1
!CMP dword [esi+%*4], eax
!JNE @@BN#_bn_naming#_CMPINT_aGTb
!end repeat
CompilerEndIf
!MOV eax, dword [p.v_b+BNPV_OFFSET]
!CMP dword [esi], eax
!JB @@BN#_bn_naming#_CMPINT_aLTb
!JA @@BN#_bn_naming#_CMPINT_aGTb
!@@BN#_bn_naming#_CMPINT_aEQb:
!BNPV_POP esi
ProcedureReturn 0
!@@BN#_bn_naming#_CMPINT_aLTb:
!BNPV_POP esi
ProcedureReturn -1
!@@BN#_bn_naming#_CMPINT_aGTb:
!BNPV_POP esi
ProcedureReturn 1
EndProcedure
;- BN_IS_EVEN(*a.BIG_NUMBER)
Procedure.l BN#_bn_naming#_IS_EVEN(*a.BIG_NUMBER#_bn_naming#)
CompilerIf _bn_checkmem=#True
If *a=0
ProcedureReturn -1
EndIf
CompilerEndIf
!MOV eax, dword [p.p_a]
!BT word [eax], 0
!JNC @@BN#_bn_naming#_ISEVEN_Even
!@@BN#_bn_naming#_ISEVEN_Odd:
ProcedureReturn 0
!@@BN#_bn_naming#_ISEVEN_Even:
ProcedureReturn 1
EndProcedure
; Procedure.l Witness(A.q, i.q, N.q)
; Protected X.q, Y.q, j.q, k.l
; If i = 0
; ProcedureReturn 1
; EndIf
;
; k = 0
; Repeat
; k + 1
; j = ($FFFFFFFFFFFFFFFF & i >> k)
; Until j = 0
; k - 1
;
; X = 1
; j = ($FFFFFFFFFFFFFFFF & i) >> k
; While k+1 <> 0 And X <> 0
; Y = ( X * X ) % N
; If Y = 1 And X <> 1 And X <> N - 1
; ProcedureReturn 0
; EndIf
;
; If j % 2 <> 0
; Y = ( A * Y ) % N
; EndIf
;
; k - 1
; j = ($FFFFFFFFFFFFFFFF & i) >> k
;
; X = Y
; Wend
; ProcedureReturn X
; EndProcedure
;
; Procedure.l CheckPrime(N.q)
; If Witness(RandInt(2, N-2), N-1, N) = 1
; ProcedureReturn 1
; Else
; ProcedureReturn 0
; EndIf
; EndProcedure
;- BN_IS_PRIME(*N.BIG_NUMBER)
Procedure.l BN#_bn_naming#_IS_PRIME(*N.BIG_NUMBER#_bn_naming#)
Protected *A.BIG_NUMBER#_bn_naming#, *i.BIG_NUMBER#_bn_naming#, *X.BIG_NUMBER#_bn_naming#, *Y.BIG_NUMBER#_bn_naming#, *tmp.BIG_NUMBER#_bn_naming#, k.l, w.l
CompilerIf _bn_checkmem=#True
If *N=0
ProcedureReturn -1
EndIf
CompilerEndIf
If BN#_bn_naming#_CMPINT(*N,100)>0
*A = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#)*5)
*i = *A+SizeOf(BIG_NUMBER#_bn_naming#)
*X = *i+SizeOf(BIG_NUMBER#_bn_naming#)
*Y = *X+SizeOf(BIG_NUMBER#_bn_naming#)
*tmp = *Y+SizeOf(BIG_NUMBER#_bn_naming#)
If *A=0
ProcedureReturn -1
EndIf
BN#_bn_naming#_SUBINT(*i, *N, 1)
k = BN#_bn_naming#_USED_BITS(*i) - 1
BN#_bn_naming#_SUBINT(*tmp, *i, 1)
BN#_bn_naming#_RND_MAX(*A, (#BIG_NUMBER#_bn_naming#_LONGS*32)-(k+3))
;; While BN#_bn_naming#_CMP(*A, *tmp)=1
;; BN#_bn_naming#_SHR(*X, *A, 1)
;; BN#_bn_naming#_MOV(*A, *X)
;; Wend
BN#_bn_naming#_INT(*X, 1)
w = #True
While k+1 <> 0 And BN#_bn_naming#_CMPINT(*X, 0) <> 0
BN#_bn_naming#_MUL(*tmp, *X, *X)
BN#_bn_naming#_MOD(*Y, *tmp, *N)
If BN#_bn_naming#_CMPINT(*Y, 1)=0 And BN#_bn_naming#_CMPINT(*X, 1)<>0 And BN#_bn_naming#_CMP(*X, *i)<>0
w = #False
Break
EndIf
BN#_bn_naming#_SHR(*tmp, *i, k)
If *tmp\n[0] & 1
BN#_bn_naming#_MUL(*tmp, *A, *Y)
BN#_bn_naming#_MOD(*Y, *tmp, *N)
EndIf
k - 1
BN#_bn_naming#_MOV(*X, *Y)
Wend
If BN#_bn_naming#_CMPINT(*X, 1)<>0
w = #False
EndIf
FreeMemory(*A)
ProcedureReturn w
Else ;fast check for small primes
Select *N\n[0]
Case 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
ProcedureReturn #True
Default
ProcedureReturn #False
EndSelect
EndIf
EndProcedure
;- BN_NEXT_PRIME(*dest.BIG_NUMBER, *a.BIG_NUMBER)
Procedure.l BN#_bn_naming#_NEXT_PRIME(*dest.BIG_NUMBER#_bn_naming#, *a.BIG_NUMBER#_bn_naming#)
Protected *tmp.BIG_NUMBER#_bn_naming#, scrTmp.l
CompilerIf _bn_checkmem=#True
If *dest=0 Or *a=0
ProcedureReturn 0
EndIf
CompilerEndIf
*tmp = AllocateMemory(SizeOf(BIG_NUMBER#_bn_naming#))
If *tmp=0 : ProcedureReturn -1 : EndIf
BN#_bn_naming#_MOV(*dest, *a)
*dest\n[0] | 1
scrTmp = #False
Repeat
BN#_bn_naming#_ADDINT(*tmp, *dest, 2)
Swap *tmp, *dest
scrTmp ! #True
Until BN#_bn_naming#_IS_PRIME(*dest)
If scrTmp
Swap *tmp, *dest
BN#_bn_naming#_MOV(*dest, *tmp)
EndIf
; scrTmp=BN#_bn_naming#_USED_BITS(*a)
; Repeat
; BN#_bn_naming#_RND_MAX(*dest, scrTmp)
; *dest\n[0] | 1
; Until BN#_bn_naming#_IS_PRIME(*dest)
FreeMemory(*tmp)
ProcedureReturn *dest
EndProcedure
;- BN_USED_BITS(*a.BIG_NUMBER)
Procedure.l BN#_bn_naming#_USED_BITS(*a.BIG_NUMBER#_bn_naming#)
CompilerIf _bn_checkmem=#True
If *a=0
ProcedureReturn 0
EndIf
CompilerEndIf
!MOV eax, BIG_NUMBER#_bn_naming#_LONGS*32
!MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
!MOV edx, dword [p.p_a]
!@@:
!CMP dword [edx+ecx*4], 0
!JNE @f
!SUB eax, 32
!DEC ecx
!JNS @b
!@@:
!CMP eax, 0
!JE @@BN#_bn_naming#_USED_BITS_endproc
!SUB eax, 31
!PUSH eax
!BSR eax, dword [edx+ecx*4]
!POP edx
!ADD eax, edx
!@@BN#_bn_naming#_USED_BITS_endproc:
ProcedureReturn
EndProcedure
;- BN_USED_LONGS(*a.BIG_NUMBER)
Procedure.l BN#_bn_naming#_USED_LONGS(*a.BIG_NUMBER#_bn_naming#)
CompilerIf _bn_checkmem=#True
If *a=0
ProcedureReturn 0
EndIf
CompilerEndIf
!MOV edx, dword [p.p_a]
!MOV ecx, BIG_NUMBER#_bn_naming#_LONGS-1
!@@:
!CMP dword [edx+ecx*4], 0
!JNE @@BN#_bn_naming#_USED_LONGS_endproc
!DEC ecx
!JNS @b
!@@BN#_bn_naming#_USED_LONGS_endproc:
!MOV eax, ecx
!INC eax
ProcedureReturn
EndProcedure
EndMacro