1,6 → 1,6 |
; mpint.inc - Multi precision integer procedures |
; |
; Copyright (C) 2015-2016 Jeffrey Amelynck |
; Copyright (C) 2015-2017 Jeffrey Amelynck |
; |
; This program is free software: you can redistribute it and/or modify |
; it under the terms of the GNU General Public License as published by |
15,11 → 15,27 |
; You should have received a copy of the GNU General Public License |
; along with this program. If not, see <http://www.gnu.org/licenses/>. |
|
; Notes: |
; |
; These procedures work only with positive integers. |
; For compatibility reasons, the highest bit must always be 0. |
; However, leading 0 bytes MUST at all other times be omitted. |
; |
; You have been warned! |
|
MPINT_MAX_LEN = MAX_BITS/8 |
|
; TODO: make procedures use real number length instead of hardcoded maximum length (MPINT_MAX_LEN) |
|
mpint_to_little_endian: |
;;===========================================================================;; |
proc mpint_to_little_endian uses esi edi ecx ;///////////////////////////////;; |
;;---------------------------------------------------------------------------;; |
;? Convert big endian MPINT to little endian MPINT. ;; |
;;---------------------------------------------------------------------------;; |
;> esi = pointer to big endian MPINT ;; |
;> edi = pointer to buffer for little endian MPINT ;; |
;;---------------------------------------------------------------------------;; |
;< eax = MPINT number length ;; |
;;===========================================================================;; |
|
; Load length dword |
lodsd |
43,38 → 59,34 |
jnz @r |
cld |
pop esi eax |
; Fill the rest of the buffer with zeros. |
.zero: |
mov ecx, MAX_BITS/8 |
sub ecx, eax |
xor al, al |
rep stosb |
|
ret |
|
mpint_to_big_endian: |
endp |
|
;;===========================================================================;; |
proc mpint_to_big_endian uses esi edi ecx ;//////////////////////////////////;; |
;;---------------------------------------------------------------------------;; |
;? Convert little endian MPINT to big endian MPINT. ;; |
;;---------------------------------------------------------------------------;; |
;> esi = pointer to little endian MPINT ;; |
;> edi = pointer to buffer for big endian MPINT ;; |
;;---------------------------------------------------------------------------;; |
;< eax = MPINT number length ;; |
;;===========================================================================;; |
|
; Load length dword |
lodsd |
test eax, eax |
jz .zero |
mov ecx, eax |
add esi, ecx |
add esi, eax |
dec esi |
test byte[esi], 0x80 ; Is the highest bit set? |
jz @f |
inc eax |
@@: |
push eax |
push eax ; we'll return length to the caller later |
bswap eax |
stosd |
; Copy data, convert to big endian meanwhile |
std |
; Append zero byte if highest bit is 0 |
test byte[esi], 0x80 |
jz @f |
mov byte[edi], 0 |
inc edi |
@@: |
lodsb |
mov byte[edi], al |
86,30 → 98,20 |
ret |
|
.zero: |
stosd |
stosd ; Number 0 has 0 data bytes |
ret |
|
proc mpint_length uses edi eax ecx, mpint |
|
mov edi, [mpint] |
mov ecx, MPINT_MAX_LEN |
push edi |
lea edi, [edi + ecx + 4 - 1] |
xor al, al |
std |
repe scasb |
cld |
je @f |
inc ecx |
@@: |
pop edi |
mov [edi], ecx |
|
ret |
|
endp |
|
proc mpint_print uses ecx esi eax, src |
;;===========================================================================;; |
proc mpint_print uses ecx esi eax, src ;/////////////////////////////////////;; |
;;---------------------------------------------------------------------------;; |
;? Print MPINT to the debug board. ;; |
;;---------------------------------------------------------------------------;; |
;> src = pointer to little endian MPINT ;; |
;;---------------------------------------------------------------------------;; |
;< - ;; |
;;===========================================================================;; |
|
DEBUGF 1, "0x" |
mov esi, [src] |
135,96 → 137,100 |
|
endp |
|
proc mpint_zero uses edi ecx eax, dst |
;;===========================================================================;; |
proc mpint_hob uses edi ecx eax, dst ;///////////////////////////////////////;; |
;;---------------------------------------------------------------------------;; |
;? Return an index number giving the position of the highest order bit. ;; |
;;---------------------------------------------------------------------------;; |
;> src = pointer to little endian MPINT ;; |
;;---------------------------------------------------------------------------;; |
;< eax = highest order bit number ;; |
;;===========================================================================;; |
|
mov edi, [dst] |
xor eax, eax |
mov ecx, MPINT_MAX_LEN/4+1 |
rep stosd |
lodsd |
dec eax ; total length minus one |
mov cl, [edi+eax] ; load the highest order byte |
shl eax, 3 ; multiply eax by 8 to get nr of bits |
|
ret |
|
endp |
|
proc mpint_zero? uses edi ecx eax, dst |
|
mov edi, [dst] |
add edi, 4 |
mov ecx, MPINT_MAX_LEN/4 |
xor eax, eax |
repe scasd |
ret |
|
endp |
|
; return an index number giving the position of the highest order bit |
proc mpint_hob uses edi ecx, dst |
|
mov edi, [dst] |
; start from the high order byte |
add edi, MPINT_MAX_LEN+4-1 |
mov ecx, MPINT_MAX_LEN |
xor eax, eax |
; scan byte by byte for the first non-zero byte |
std |
repe scasb |
cld |
je .zero |
; calculate how many bits this is, plus 7 |
lea eax, [ecx*8-1] |
; load this high order byte into cl |
mov cl, [edi+1] |
; shift bits of this byte right, until the byte reaches zero, counting bits meanwhile |
; Now shift bits of the highest order byte right, until the byte reaches zero, counting bits meanwhile |
test cl, cl |
jz .end |
@@: |
inc eax |
shr cl, 1 |
jnz @r |
.zero: |
.end: |
ret |
|
endp |
|
proc mpint_cmp uses esi edi ecx, dst, src |
;;===========================================================================;; |
proc mpint_cmp uses esi edi ecx eax, dst, src ;//////////////////////////////;; |
;;---------------------------------------------------------------------------;; |
;? Compare two mpints. ;; |
;;---------------------------------------------------------------------------;; |
;> dst = pointer to little endian MPINT ;; |
;> src = pointer to little endian MPINT ;; |
;;---------------------------------------------------------------------------;; |
;< flags are set as for single precision CMP instruction ;; |
;;===========================================================================;; |
|
; First, check if number of significant bytes is the same |
; If not, number with more bytes is bigger |
mov esi, [src] |
mov edi, [dst] |
; start from the high order byte |
add esi, MPINT_MAX_LEN+4-4 |
add edi, MPINT_MAX_LEN+4-4 |
mov ecx, MPINT_MAX_LEN/4 |
mov ecx, [esi] |
cmp ecx, [edi] |
jne .got_answer |
|
; Numbers have equal amount of bytes, compare starting from the high order byte |
add edi, ecx |
add esi, ecx |
std |
.do_byte: |
test ecx, 11b |
jz .do_dword |
dec esi |
dec edi |
cmpsb |
jne .got_answer |
dec ecx |
jmp .do_byte |
.do_dword: |
shr ecx, 2 |
jz .got_answer |
sub esi, 4 |
sub edi, 4 |
repe cmpsd |
.got_answer: |
cld |
ret |
|
endp |
|
proc mpint_mov uses esi edi ecx, dst, src |
;;===========================================================================;; |
proc mpint_mov uses esi edi ecx, dst, src ;//////////////////////////////////;; |
;;---------------------------------------------------------------------------;; |
;? Copy mpint. ;; |
;;---------------------------------------------------------------------------;; |
;> dst = pointer to buffer for little endian MPINT ;; |
;> src = pointer to little endian MPINT ;; |
;;---------------------------------------------------------------------------;; |
;< dst = src ;; |
;;===========================================================================;; |
|
mov esi, [src] |
mov edi, [dst] |
mov ecx, MPINT_MAX_LEN/4+1 |
mov ecx, [esi] |
push ecx |
shr ecx, 2 |
inc ecx ; for length dword |
rep movsd |
|
ret |
|
endp |
|
proc mpint_mov0 uses esi edi ecx eax, dst, src |
|
mov esi, [src] |
mov edi, [dst] |
mov ecx, [esi] |
mov eax, ecx |
neg eax |
add esi, 4 |
add edi, 4 |
pop ecx |
and ecx, 11b |
jz @f |
rep movsb |
add eax, MPINT_MAX_LEN |
jz @f |
mov ecx, eax |
xor eax, eax |
rep stosb |
@@: |
|
ret |
231,49 → 237,95 |
|
endp |
|
proc mpint_shl1 uses edi ecx eax, dst |
;;===========================================================================;; |
proc mpint_shl1 uses esi ecx, dst ;//////////////////////////////////////////;; |
;;---------------------------------------------------------------------------;; |
;? Shift little endian MPINT one bit to the left. ;; |
;;---------------------------------------------------------------------------;; |
;> dst = pointer to little endian MPINT ;; |
;;---------------------------------------------------------------------------;; |
;< dst = dst SHL 1 ;; |
;;===========================================================================;; |
|
mov edi, [dst] |
add edi, 4 |
mov ecx, MPINT_MAX_LEN/4-1 |
mov esi, [dst] |
mov ecx, [esi] |
test ecx, ecx |
jz .done |
|
shl dword[edi], 1 |
lahf |
; Test if high order byte will overflow |
; Remember: highest bit must never be set for positive numbers! |
test byte[esi+ecx+3], 11000000b |
jz @f |
; We must grow a byte in size! |
; TODO: check for overflow |
inc ecx |
mov [esi], ecx |
mov byte[esi+ecx+3], 0 ; Add the new MSB |
@@: |
add edi, 4 |
sahf |
rcl dword[edi], 1 |
lahf |
add esi, 4 |
; Do the lowest order byte first |
shl byte[esi], 1 |
dec ecx |
jz .done |
; And the remaining bytes |
@@: |
inc esi |
rcl byte[esi], 1 |
dec ecx |
jnz @r |
sahf |
|
.done: |
ret |
|
endp |
|
proc mpint_shr1 uses edi ecx eax, dst |
;;===========================================================================;; |
proc mpint_shr1 uses edi ecx, dst ;//////////////////////////////////////////;; |
;;---------------------------------------------------------------------------;; |
;? Shift little endian MPINT one bit to the right. ;; |
;;---------------------------------------------------------------------------;; |
;> dst = pointer to little endian MPINT ;; |
;;---------------------------------------------------------------------------;; |
;< dst = dst SHR 1 ;; |
;;===========================================================================;; |
|
mov edi, [dst] |
add edi, MPINT_MAX_LEN+4-4 |
mov ecx, MPINT_MAX_LEN/4-1 |
mov ecx, [edi] |
test ecx, ecx |
jz .done |
|
shr dword[edi], 1 |
lahf |
; Do the highest order byte first |
dec ecx |
shr byte[edi+ecx+3], 1 |
; Was it 0? If so, we must decrement total length |
jnz @f |
jc @f |
mov [edi], ecx |
@@: |
sub edi, 4 |
sahf |
rcr dword[edi], 1 |
lahf |
dec ecx |
test ecx, ecx |
jz .done |
; Now do the trailing bytes |
add edi, 4 |
add edi, ecx |
@@: |
dec edi |
rcr byte[edi], 1 |
dec ecx ; does not affect carry flag, hooray! |
jnz @r |
sahf |
|
.done: |
ret |
|
endp |
|
proc mpint_shl uses eax ebx ecx edx esi edi, dst, shift |
;;===========================================================================;; |
proc mpint_shl uses eax ebx ecx edx esi edi, dst, shift ;////////////////////;; |
;;---------------------------------------------------------------------------;; |
;? Left shift little endian MPINT by x bits. ;; |
;;---------------------------------------------------------------------------;; |
;> dst = pointer to little endian MPINT ;; |
;> shift = number of bits to shift the MPINT ;; |
;;---------------------------------------------------------------------------;; |
;< - ;; |
;;===========================================================================;; |
|
mov ecx, [shift] |
shr ecx, 3 ; 8 bits in one byte |
313,13 → 365,23 |
ret |
|
.zero: |
stdcall mpint_zero, [dst] |
mov eax, [dst] |
mov dword[eax], 0 |
ret |
|
endp |
|
; Left shift and copy |
proc mpint_shlmov uses eax ebx ecx edx esi edi, dst, src, shift |
;;===========================================================================;; |
proc mpint_shlmov uses eax ebx ecx edx esi edi, dst, src, shift ;////////////;; |
;;---------------------------------------------------------------------------;; |
;? Left shift by x bits and copy little endian MPINT. ;; |
;;---------------------------------------------------------------------------;; |
;> src = pointer to little endian MPINT ;; |
;> dst = pointer to little endian MPINT ;; |
;> shift = number of bits to shift the MPINT to the left ;; |
;;---------------------------------------------------------------------------;; |
;< dst = src SHL shift ;; |
;;===========================================================================;; |
|
mov ecx, [shift] |
shr ecx, 3 ; 8 bits in one byte |
360,67 → 422,170 |
ret |
|
.zero: |
stdcall mpint_zero, [dst] |
mov eax, [dst] |
mov dword[eax], 0 |
ret |
|
endp |
|
proc mpint_add uses esi edi ecx eax, dst, src |
;;===========================================================================;; |
proc mpint_add uses esi edi ecx eax, dst, src ;//////////////////////////////;; |
;;---------------------------------------------------------------------------;; |
;? Add a little endian MPINT to another little endian MPINT. ;; |
;;---------------------------------------------------------------------------;; |
;> src = pointer to little endian MPINT ;; |
;> dst = pointer to little endian MPINT ;; |
;;---------------------------------------------------------------------------;; |
;< dst = dst + src ;; |
;;===========================================================================;; |
|
mov esi, [src] |
add esi, 4 |
mov edi, [dst] |
mov ecx, [esi] ; source number length |
sub ecx, [dst] |
jbe .length_ok |
; Length of the destination is currently smaller then the source, pad with 0 bytes |
add edi, [edi] |
add edi, 4 |
mov ecx, MPINT_MAX_LEN/4 |
xor ah, ah ; clear flags (Carry flag most importantly) |
@@: |
sahf |
lodsd |
adc [edi], eax |
lahf |
mov al, 0 |
rep stosb |
.length_ok: |
mov ecx, [esi] |
mov edi, [dst] |
add esi, 4 |
add edi, 4 |
; Add the first byte |
lodsb |
add byte[edi], al |
dec ecx |
jz .done |
; Add the other bytes |
@@: |
inc edi |
lodsb |
adc byte[edi], al |
dec ecx |
jnz @r |
sahf |
.done: |
; check if highest bit OR carry flag is set |
; if so, add a byte if we have the buffer space |
; TODO: check if we have the buffer space |
jc .carry |
cmp byte[edi], 0x80 |
jnz .high_bit_set |
|
ret |
|
.carry: |
inc edi |
mov byte[edi], 1 |
mov eax, [dst] |
inc dword[eax] |
|
ret |
|
.high_bit_set: |
inc edi |
mov byte[edi], 0 |
mov eax, [dst] |
inc dword[eax] |
|
ret |
|
endp |
|
proc mpint_sub uses eax esi edi ecx, dst, src |
;;===========================================================================;; |
proc mpint_sub uses eax esi edi ecx, dst, src ;//////////////////////////////;; |
;;---------------------------------------------------------------------------;; |
;? Subtract a little endian MPINT to another little endian MPINT. ;; |
;;---------------------------------------------------------------------------;; |
;> src = pointer to little endian MPINT ;; |
;> dst = pointer to little endian MPINT ;; |
;;---------------------------------------------------------------------------;; |
;< dst = dst - src ;; |
;;===========================================================================;; |
|
mov esi, [src] |
mov edi, [dst] |
mov ecx, [esi] ; destination number length |
cmp ecx, [edi] |
ja .overflow |
|
add esi, 4 |
mov edi, [dst] |
add edi, 4 |
mov ecx, MPINT_MAX_LEN/4 |
.loop: |
lodsd |
sub [edi], eax |
jnc @f |
dec dword [edi+4] |
; Subtract the first byte |
lodsb |
sub byte[edi], al |
dec ecx |
jz .done |
; Subtract the other bytes |
@@: |
add edi, 4 |
inc edi |
lodsb |
sbb byte[edi], al |
dec ecx |
jnz .loop |
jnz @r |
.done: |
stdcall mpint_shrink, [dst] |
ret |
|
.overflow: |
mov dword[edi], 0 |
stc |
ret |
|
endp |
|
proc mpint_mul uses esi edi ecx ebx eax, dst, A, B |
|
stdcall mpint_zero, [dst] |
;;===========================================================================;; |
proc mpint_shrink uses eax edi ecx, dst ;////////////////////////////////////;; |
;;---------------------------------------------------------------------------;; |
;? Get rid of leading zeroes on a little endian MPINT. ;; |
;;---------------------------------------------------------------------------;; |
;> src = pointer to little endian MPINT ;; |
;;---------------------------------------------------------------------------;; |
;< ;; |
;;===========================================================================;; |
|
; first, find the byte in A containing the highest order bit |
mov ecx, MPINT_MAX_LEN |
mov edi, [A] |
add edi, MPINT_MAX_LEN+4-1 |
mov edi, [dst] |
lodsd |
std |
mov ecx, eax |
dec eax ; total length minus one |
add edi, eax |
xor al, al |
repe scasb |
repe cmpsb |
inc ecx |
mov edi, [dst] |
mov [edi], ecx |
cld |
je .zero |
inc ecx |
|
ret |
|
endp |
|
;;===========================================================================;; |
proc mpint_mul uses esi edi ecx ebx eax, dst, A, B ;/////////////////////////;; |
;;---------------------------------------------------------------------------;; |
;? Multiply to little endian MPINTS and store them in a new one. ;; |
;;---------------------------------------------------------------------------;; |
;> A = pointer to little endian MPINT ;; |
;> B = pointer to little endian MPINT ;; |
;> dst = pointer to buffer for little endian MPINT ;; |
;;---------------------------------------------------------------------------;; |
;< dst = A * B ;; |
;;===========================================================================;; |
|
; Set result to zero |
mov eax, [dst] |
mov dword[eax], 0 |
|
; first, find the byte in A containing the highest order bit |
mov edi, [A] |
mov eax, [edi] |
test eax, eax |
jz .zero |
add edi, eax |
mov al, [edi+1] |
mov esi, edi |
mov bl, 8 |
452,50 → 617,83 |
|
endp |
|
proc mpint_mod uses eax ecx, dst, mod |
;;===========================================================================;; |
proc mpint_mod uses eax ebx ecx, dst, mod ;//////////////////////////////////;; |
;;---------------------------------------------------------------------------;; |
;? Find the modulo (remainder after division) of dst by mod. ;; |
;;---------------------------------------------------------------------------;; |
;> dst = pointer to little endian MPINT ;; |
;> mod = pointer to little endian MPINT ;; |
;;---------------------------------------------------------------------------;; |
;< dst = dst MOD mod ;; |
;;===========================================================================;; |
|
locals |
mpint_tmp rb MPINT_MAX_LEN+4 |
endl |
|
; if mod is zero, return |
stdcall mpint_zero?, [mod] |
jz .zero |
mov eax, [mod] |
cmp dword[eax], 0 |
je .zero |
|
stdcall mpint_cmp, [mod], [dst] |
stdcall mpint_cmp, eax, [dst] |
jb .done ; if dst < mod, dst = dst |
je .zero ; if dst == mod, dst = 0 |
|
lea ebx, [mpint_tmp] |
|
; left shift mod until the high order bits of mod and dst are aligned |
stdcall mpint_hob, [dst] |
mov ecx, eax |
stdcall mpint_hob, [mod] |
sub ecx, eax |
stdcall mpint_shlmov, mpint_tmp, [mod], ecx |
stdcall mpint_shlmov, ebx, [mod], ecx |
inc ecx |
|
; For every bit in dst (starting from the high order bit): |
.loop: |
; determine if dst is bigger than mpint_tmp |
stdcall mpint_cmp, [dst], mpint_tmp |
stdcall mpint_cmp, [dst], ebx |
ja @f |
; if so, subtract mpint_tmp from dst |
stdcall mpint_sub, [dst], mpint_tmp |
stdcall mpint_sub, [dst], ebx |
@@: |
dec ecx |
jz .done |
; shift mpint_tmp right by 1 |
stdcall mpint_shr1, mpint_tmp |
stdcall mpint_shr1, ebx |
jmp .loop |
|
.zero: |
stdcall mpint_zero, [dst] |
mov eax, [dst] |
mov dword[eax], 0 |
.done: |
ret |
|
endp |
|
proc mpint_modexp uses edi eax ebx ecx, dst, base, exp, mod |
;;===========================================================================;; |
proc mpint_modexp uses edi eax ebx ecx edx, dst, base, exp, mod ;////////////;; |
;;---------------------------------------------------------------------------;; |
;? Find the modulo (remainder after division) of dst by mod. ;; |
;;---------------------------------------------------------------------------;; |
;> dst = pointer to buffer for little endian MPINT ;; |
;> base = pointer to little endian MPINT ;; |
;> exp = pointer to little endian MPINT ;; |
;> mod = pointer to little endian MPINT ;; |
;;---------------------------------------------------------------------------;; |
;< dst = base ** exp MOD mod ;; |
;;===========================================================================;; |
|
locals |
mpint_tmp rb MPINT_MAX_LEN+4 |
endl |
|
; If mod is zero, return |
stdcall mpint_zero?, [mod] |
jz .mod_zero |
mov eax, [mod] |
cmp dword[eax], 0 |
je .mod_zero |
|
; Find the highest order byte in exponent |
mov edi, [exp] |
511,21 → 709,22 |
shl al, 1 |
jnc @r |
|
lea edx, [mpint_tmp] |
; Initialise result to base, to take care of the highest order bit |
stdcall mpint_mov0, [dst], [base] |
stdcall mpint_mov, [dst], [base] |
dec bl |
jz .next_byte |
.bit_loop: |
; For each bit, square result |
stdcall mpint_mov, mpint_tmp, [dst] |
stdcall mpint_mul, [dst], mpint_tmp, mpint_tmp |
stdcall mpint_mov, edx, [dst] |
stdcall mpint_mul, [dst], edx, edx |
stdcall mpint_mod, [dst], [mod] |
|
; If the bit is set, multiply result by the base |
shl al, 1 |
jnc .next_bit |
stdcall mpint_mov, mpint_tmp, [dst] |
stdcall mpint_mul, [dst], [base], mpint_tmp |
stdcall mpint_mov, edx, [dst] |
stdcall mpint_mul, [dst], [base], edx |
stdcall mpint_mod, [dst], [mod] |
.next_bit: |
dec bl |
543,15 → 742,15 |
.mod_zero: |
DEBUGF 3, "modexp with modulo 0\n" |
; if mod is zero, result = 0 |
stdcall mpint_zero, [dst] |
mov eax, [dst] |
mov dword[eax], 0 |
ret |
|
.exp_zero: |
DEBUGF 3, "modexp with exponent 0\n" |
; if exponent is zero, result = 1 |
stdcall mpint_zero, [dst] |
mov eax, [dst] |
mov byte[eax], 1 |
mov dword[eax], 1 |
mov byte[eax+4], 1 |
ret |
|