Subversion Repositories Kolibri OS

Compare Revisions

Regard whitespace Rev 9069 → Rev 9070

/programs/network/ssh/mpint.inc
1,6 → 1,6
; mpint.inc - Multi precision integer procedures
;
; Copyright (C) 2015-2017 Jeffrey Amelynck
; Copyright (C) 2015-2021 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
19,7 → 19,6
;
; 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!
 
27,16 → 26,18
 
 
;;===========================================================================;;
proc mpint_to_little_endian uses esi edi ecx ;///////////////////////////////;;
proc mpint_to_little_endian uses esi edi ecx, dst, src ;/////////////////////;;
;;---------------------------------------------------------------------------;;
;? Convert big endian MPINT to little endian MPINT. ;;
;;---------------------------------------------------------------------------;;
;> esi = pointer to big endian MPINT ;;
;> edi = pointer to buffer for little endian MPINT ;;
;> src = pointer to big endian MPINT ;;
;> dst = pointer to buffer for little endian MPINT ;;
;;---------------------------------------------------------------------------;;
;< eax = MPINT number length ;;
;;===========================================================================;;
 
mov esi, [src]
mov edi, [dst]
; Load length dword
lodsd
; Convert to little endian
47,7 → 48,6
; Copy data, convert to little endian meanwhile
push eax
add esi, eax
push esi
dec esi
mov ecx, eax
std
57,8 → 57,9
inc edi
dec ecx
jnz @r
 
cld
pop esi eax
pop eax
.zero:
ret
 
65,16 → 66,18
endp
 
;;===========================================================================;;
proc mpint_to_big_endian uses esi edi ecx ;//////////////////////////////////;;
proc mpint_to_big_endian uses esi edi ecx, dst, src ;////////////////////////;;
;;---------------------------------------------------------------------------;;
;? Convert little endian MPINT to big endian MPINT. ;;
;;---------------------------------------------------------------------------;;
;> esi = pointer to little endian MPINT ;;
;> edi = pointer to buffer for big endian MPINT ;;
;> src = pointer to little endian MPINT ;;
;> dst = pointer to buffer for big endian MPINT ;;
;;---------------------------------------------------------------------------;;
;< eax = MPINT number length ;;
;;===========================================================================;;
 
mov esi, [src]
mov edi, [dst]
; Load length dword
lodsd
test eax, eax
138,65 → 141,119
endp
 
;;===========================================================================;;
proc mpint_hob uses edi ecx eax, dst ;///////////////////////////////////////;;
proc mpint_bits uses esi ecx, dst ;//////////////////////////////////////////;;
;;---------------------------------------------------------------------------;;
;? Return an index number giving the position of the highest order bit. ;;
;? Count the number of bits in the MPINT ;;
;;---------------------------------------------------------------------------;;
;> src = pointer to little endian MPINT ;;
;> dst = pointer to little endian MPINT ;;
;;---------------------------------------------------------------------------;;
;< eax = highest order bit number ;;
;< eax = highest order bit number + 1 ;;
;;===========================================================================;;
 
mov edi, [dst]
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
DEBUGF 1, "mpint_bits(0x%x): ", [dst]
 
mov esi, [dst]
mov eax, [esi]
test eax, eax
jz .zero
add esi, 4-1
; Find highest order byte
.byteloop:
cmp byte[esi+eax], 0
jne .nz
dec eax
jnz .byteloop
.zero:
DEBUGF 1, "%u\n", eax
ret
.nz:
mov cl, byte[esi+eax]
; multiply (eax - 1) by 8 to get nr of bits before this byte
dec eax
shl eax, 3
; Now shift bits of the highest order byte right, until the byte reaches zero, counting bits meanwhile
test cl, cl
jz .end
@@:
.bitloop:
inc eax
shr cl, 1
jnz @r
.end:
jnz .bitloop
DEBUGF 1, "%u\n", eax
ret
 
endp
 
 
;;===========================================================================;;
proc mpint_cmp uses esi edi ecx eax, dst, src ;//////////////////////////////;;
proc mpint_bytes uses esi, dst ;/////////////////////////////////////////////;;
;;---------------------------------------------------------------------------;;
;? Compare two mpints. ;;
;? Count the number of bytes in the MPINT ;;
;;---------------------------------------------------------------------------;;
;> dst = pointer to little endian MPINT ;;
;;---------------------------------------------------------------------------;;
;< eax = highest order byte number + 1 ;;
;;===========================================================================;;
 
DEBUGF 1, "mpint_bytes(0x%x): ", [dst]
 
mov esi, [dst]
mov eax, [esi]
test eax, eax
jz .done
add esi, 4-1
; Find highest order byte
.byteloop:
cmp byte[esi+eax], 0
jne .done
dec eax
jnz .byteloop
.done:
DEBUGF 1, "%u\n", eax
ret
 
endp
 
;;===========================================================================;;
proc mpint_cmp uses esi edi ecx eax, src, dst ;//////////////////////////////;;
;;---------------------------------------------------------------------------;;
;? 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
DEBUGF 1, "mpint_cmp(0x%x, 0x%x)\n", [dst], [src]
 
; First, check the size of both numbers
stdcall mpint_bytes, [dst]
mov ecx, eax
stdcall mpint_bytes, [src]
; If one number has more bytes, it is bigger
cmp eax, ecx
jne .got_answer
; If both numbers have 0 bytes, they are equal
test ecx, ecx
jz .got_answer
; Numbers have equal amount of bytes
; Start comparing from the MSB towards the LSB
mov esi, [src]
mov edi, [dst]
mov ecx, [esi]
cmp ecx, [edi]
jne .got_answer
 
; Numbers have equal amount of bytes, compare starting from the high order byte
add esi, ecx
add edi, ecx
add esi, ecx
add esi, 4
add edi, 4
std
; If remaining bytes is not divisible by 4, compare only one byte at a time
.do_byte:
test ecx, 11b
test ecx, 1b
jz .do_dword
dec esi
dec edi
cmpsb
mov al, byte[esi]
cmp al, byte[edi]
jne .got_answer
dec ecx
jmp .do_byte
; Remaining bytes is divisable by 4, compare dwords
.do_dword:
shr ecx, 2
jz .got_answer
212,7 → 269,7
;;===========================================================================;;
proc mpint_mov uses esi edi ecx, dst, src ;//////////////////////////////////;;
;;---------------------------------------------------------------------------;;
;? Copy mpint. ;;
;? Copy MPINT. ;;
;;---------------------------------------------------------------------------;;
;> dst = pointer to buffer for little endian MPINT ;;
;> src = pointer to little endian MPINT ;;
220,6 → 277,8
;< dst = src ;;
;;===========================================================================;;
 
DEBUGF 1, "mpint_mov(0x%x, 0x%x)\n", [dst], [src]
 
mov esi, [src]
mov edi, [dst]
mov ecx, [esi]
247,6 → 306,8
;< dst = dst SHL 1 ;;
;;===========================================================================;;
 
DEBUGF 1, "mpint_shl1(0x%x)\n", [dst]
 
mov esi, [dst]
mov ecx, [esi]
test ecx, ecx
288,6 → 349,8
;< dst = dst SHR 1 ;;
;;===========================================================================;;
 
DEBUGF 1, "mpint_shr1(0x%x)\n", [dst]
 
mov edi, [dst]
mov ecx, [edi]
test ecx, ecx
294,18 → 357,12
jz .done
 
; Do the highest order byte first
add edi, 4-1
add edi, ecx
shr byte[edi], 1
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
@@:
test ecx, ecx
jz .done
; Now do the trailing bytes
add edi, 4
add edi, ecx
@@:
dec edi
rcr byte[edi], 1
327,11 → 384,20
;< - ;;
;;===========================================================================;;
 
DEBUGF 1, "mpint_shl(0x%x, %u)\n", [dst], [shift]
 
; Calculate new size
stdcall mpint_bits, [dst]
add eax, [shift]
shr eax, 3
cmp eax, MPINT_MAX_LEN
jae .overflow ;;
inc eax
mov esi, [dst]
mov [esi], eax
 
mov ecx, [shift]
shr ecx, 3 ; 8 bits in one byte
cmp ecx, MPINT_MAX_LEN
jge .zero
mov esi, [dst]
add esi, MPINT_MAX_LEN+4-4
mov edi, esi
and ecx, not 11b
354,7 → 420,7
shl eax, cl
stosd
 
; fill the lsb bytes with zeros
; fill the LSBs with zeros
pop ecx
test ecx, ecx
jz @f
369,6 → 435,10
mov dword[eax], 0
ret
 
.overflow:
int3
ret
 
endp
 
;;===========================================================================;;
383,14 → 453,25
;< dst = src SHL shift ;;
;;===========================================================================;;
 
mov ecx, [shift]
shr ecx, 3 ; 8 bits in one byte
cmp ecx, MPINT_MAX_LEN
jge .zero
DEBUGF 1, "mpint_shlmov(0x%x, 0x%x, %u)\n", [dst], [src], [shift]
 
stdcall mpint_bits, [src]
test eax, eax
jz .zero
add eax, [shift]
shr eax, 3
inc eax
mov edi, [dst]
mov [edi], eax
 
cmp eax, MPINT_MAX_LEN
jae .overflow ;;;;
 
mov esi, [src]
add esi, MPINT_MAX_LEN+4-4
mov edi, [dst]
add edi, MPINT_MAX_LEN+4-4
mov ecx, [shift]
shr ecx, 3 ; 8 bits in one byte
and ecx, not 11b
sub esi, ecx
mov edx, MPINT_MAX_LEN/4-1
426,6 → 507,10
mov dword[eax], 0
ret
 
.overflow:
int3
ret
 
endp
 
;;===========================================================================;;
439,19 → 524,21
;< dst = dst + src ;;
;;===========================================================================;;
 
DEBUGF 1, "mpint_add(0x%x, 0x%x)\n", [dst], [src]
 
mov esi, [src]
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 al, 0
rep stosb
stdcall mpint_bytes, esi
mov ecx, eax
stdcall mpint_bytes, edi
cmp ecx, eax
jb .grow_src
ja .grow_dst
test ecx, ecx
jz .done
 
.length_ok:
mov ecx, [esi]
mov edi, [dst]
push ecx
add esi, 4
add edi, 4
; Add the first byte
467,9 → 554,11
dec ecx
jnz @r
.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
pop ecx
jc .carry
cmp byte[edi], 0x80
jnz .high_bit_set
477,21 → 566,32
ret
 
.carry:
inc edi
mov byte[edi], 1
mov eax, [dst]
cmp [eax], ecx
ja @f
inc dword[eax]
 
@@:
mov byte[edi+1], 1
ret
 
.high_bit_set:
inc edi
mov byte[edi], 0
mov eax, [dst]
cmp [eax], ecx
ja @f
inc dword[eax]
 
@@:
mov byte[edi+1], 0
ret
 
.grow_dst:
stdcall mpint_grow, edi, ecx
jmp .length_ok
 
.grow_src:
mov ecx, eax
stdcall mpint_grow, esi, ecx
jmp .length_ok
 
endp
 
;;===========================================================================;;
505,12 → 605,20
;< dst = dst - src ;;
;;===========================================================================;;
 
DEBUGF 1, "mpint_sub(0x%x, 0x%x)\n", [dst], [src]
 
mov esi, [src]
mov edi, [dst]
mov ecx, [esi] ; destination number length
cmp ecx, [edi]
ja .overflow
stdcall mpint_bytes, esi
mov ecx, eax
stdcall mpint_bytes, edi
cmp ecx, eax
jb .grow_src
ja .grow_dst
test ecx, ecx
jz .done
 
.length_ok:
add esi, 4
add edi, 4
; Subtract the first byte
526,7 → 634,6
dec ecx
jnz @r
.done:
stdcall mpint_shrink, [dst]
ret
 
.overflow:
534,13 → 641,22
stc
ret
 
.grow_dst:
stdcall mpint_grow, edi, ecx
jmp .length_ok
 
.grow_src:
mov ecx, eax
stdcall mpint_grow, esi, ecx
jmp .length_ok
 
endp
 
 
;;===========================================================================;;
proc mpint_shrink uses eax edi ecx, dst ;////////////////////////////////////;;
proc mpint_shrink uses eax edi, dst ;////////////////////////////////////////;;
;;---------------------------------------------------------------------------;;
;? Get rid of leading zeroes on a little endian MPINT. ;;
;? Get rid of unnescessary leading zeroes on a little endian MPINT. ;;
;;---------------------------------------------------------------------------;;
;> src = pointer to little endian MPINT ;;
;;---------------------------------------------------------------------------;;
547,19 → 663,61
;< ;;
;;===========================================================================;;
 
DEBUGF 1, "mpint_shrink(0x%x)\n", [dst]
 
; mov edi, [dst]
; lodsd
; std
; mov ecx, eax
; dec eax ; total length minus one
; add edi, eax
; xor al, al
; repe cmpsb
; inc ecx
; mov edi, [dst]
; mov [edi], ecx
; cld
 
stdcall mpint_bits, [dst]
shr eax, 3
inc eax
mov edi, [dst]
lodsd
std
mov ecx, eax
dec eax ; total length minus one
add edi, eax
mov [edi], eax
 
ret
 
endp
 
 
;;===========================================================================;;
proc mpint_grow uses eax edi ecx, dst, length ;//////////////////////////////;;
;;---------------------------------------------------------------------------;;
;? Add leading zeroes on a little endian MPINT. ;;
;;---------------------------------------------------------------------------;;
;> src = pointer to little endian MPINT ;;
;> length = total length of the new MPINT in bytes ;;
;;---------------------------------------------------------------------------;;
;< ;;
;;===========================================================================;;
 
DEBUGF 1, "mpint_grow(0x%x, %u): ", [dst], [length]
 
mov edi, [dst]
mov eax, [edi]
mov ecx, [length]
sub ecx, eax
jbe .dontgrow
lea edi, [edi + 4 + eax]
xor al, al
repe cmpsb
inc ecx
rep stosb
mov eax, [length]
mov edi, [dst]
mov [edi], ecx
cld
mov [edi], eax
DEBUGF 1, "ok\n"
ret
 
.dontgrow:
DEBUGF 1, "already large enough!\n"
ret
 
endp
567,7 → 725,7
;;===========================================================================;;
proc mpint_mul uses esi edi ecx ebx eax, dst, A, B ;/////////////////////////;;
;;---------------------------------------------------------------------------;;
;? Multiply to little endian MPINTS and store them in a new one. ;;
;? Multiply two little endian MPINTS and store them in a third one. ;;
;;---------------------------------------------------------------------------;;
;> A = pointer to little endian MPINT ;;
;> B = pointer to little endian MPINT ;;
576,26 → 734,20
;< dst = A * B ;;
;;===========================================================================;;
 
DEBUGF 1, "mpint_mul(0x%x, 0x%x, 0x%x)\n", [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]
stdcall mpint_bytes, edi
test eax, eax
jz .zero
add edi, 4-1
add edi, eax
mov al, [edi+1]
mov esi, edi
mov bl, 8
@@:
shl al, 1
jc .first_hit
dec bl
jnz @r
 
; Then, starting from this byte, iterate through the bits in A,
mov ecx, eax
; Iterate through the bits in A,
; starting from the highest order bit down to the lowest order bit.
.next_byte:
mov al, [edi]
605,7 → 757,6
stdcall mpint_shl1, [dst]
shl al, 1
jnc .zero_bit
.first_hit:
stdcall mpint_add, [dst], [B]
.zero_bit:
dec bl
628,43 → 779,40
;< dst = dst MOD mod ;;
;;===========================================================================;;
 
DEBUGF 1, "mpint_mod(0x%x, 0x%x)\n", [dst], [mod]
 
locals
mpint_tmp rb MPINT_MAX_LEN+4
endl
 
; if mod is zero, return
mov eax, [mod]
cmp dword[eax], 0
je .zero
stdcall mpint_cmp, [mod], [dst]
ja .done ; if mod > dst, dst = dst ;;;;;;;
je .zero ; if mod == dst, dst = 0
 
stdcall mpint_cmp, eax, [dst]
jb .done ; if dst < mod, dst = dst
je .zero ; if dst == mod, dst = 0
; left shift mod until the high order bits of mod and dst are aligned
 
lea ebx, [mpint_tmp]
 
; left shift mod until the high order bits of mod and dst are aligned
stdcall mpint_hob, [dst]
stdcall mpint_bits, [dst]
mov ecx, eax
stdcall mpint_hob, [mod]
stdcall mpint_bits, [mod]
test eax, eax
jz .zero ; if mod is zero, return
sub ecx, eax
lea ebx, [mpint_tmp]
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], ebx
ja @f
; if so, subtract mpint_tmp from dst
stdcall mpint_sub, [dst], ebx
.bitloop:
stdcall mpint_cmp, [dst], ebx ; If dst > mpint_tmp
jb @f ;;;;;;;;
stdcall mpint_sub, [dst], ebx ; dst = dst - mpint_tmp
@@:
dec ecx
jz .done
; shift mpint_tmp right by 1
stdcall mpint_shr1, ebx
jmp .loop
 
stdcall mpint_shr1, ebx ; mpint = mpint >> 1
jmp .bitloop
 
.zero:
mov eax, [dst]
mov dword[eax], 0
686,19 → 834,25
;< dst = base ** exp MOD mod ;;
;;===========================================================================;;
 
;DEBUGF 1, "mpint_modexp(0x%x, 0x%x, 0x%x, 0x%x)\n", [dst], [base], [exp], [mod]
 
locals
mpint_tmp rb MPINT_MAX_LEN+4
endl
 
; If mod is zero, return
mov eax, [mod]
cmp dword[eax], 0
je .mod_zero
stdcall mpint_bits, [mod]
test eax, eax
jz .mod_zero
 
; Find the highest order byte in exponent
; Find highest order byte in exponent
stdcall mpint_bytes, [exp]
test eax, eax
jz .exp_zero
mov ecx, eax
mov edi, [exp]
mov ecx, [edi]
lea edi, [edi + 4 + ecx - 1]
 
; Find the highest order bit in this byte
mov al, [edi]
test al, al
709,7 → 863,9
shl al, 1
jnc @r
 
; Make pointer to tmp mpint for convenient access
lea edx, [mpint_tmp]
 
; Initialise result to base, to take care of the highest order bit
stdcall mpint_mov, [dst], [base]
dec bl
737,6 → 893,7
mov bl, 8
jmp .bit_loop
.done:
;stdcall mpint_print, [dst]
ret
 
.mod_zero: