WebSVN – Kolibri OS – Diff – /programs/network/ssh/mpint.inc

 ;    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
 ;    the Free Software Foundation, either version 3 of the License, or
 ;    (at your option) any later version.
 ;    GNU General Public License for more details.
+;
 ;    You should have received a copy of the GNU General Public License
 ;    along with this program.  If not, see .
+; 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
+MPINT_MAX_LEN = MAX_BITS/8
+;;===========================================================================;;
+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                           ;;
-; TODO: make procedures use real number length instead of hardcoded maximum length (MPINT_MAX_LEN)
+;;---------------------------------------------------------------------------;;
 ;< eax = MPINT number length                                                 ;;
-mpint_to_little_endian:
+;;===========================================================================;;
         inc     edi
         dec     ecx
         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
+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                                                 ;;
-mpint_to_big_endian:
+;;===========================================================================;;
 ; 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
-  @@:
+        dec     esi
-        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
+; Copy data, convert to big endian meanwhile
-        inc     edi
+        std
   @@:
         lodsb
         mov     byte[edi], al
         cld
         pop     eax
         ret
-  .zero:
-        stosd
-        ret
-proc mpint_length uses edi eax ecx, mpint
-        mov     edi, [mpint]
-        mov     ecx, MPINT_MAX_LEN
-        push    edi
+  .zero:
-        lea     edi, [edi + ecx + 4 - 1]
-        xor     al, al
-        std
-        repe scasb
-        cld
-        je      @f
-        inc     ecx
-  @@:
-        pop     edi
-        mov     [edi], ecx
         stosd           ; Number 0 has 0 data bytes
         ret
+endp
+;;===========================================================================;;
+proc mpint_print uses ecx esi eax, src ;/////////////////////////////////////;;
+;;---------------------------------------------------------------------------;;
+;? Print MPINT to the debug board.                                           ;;
+;;---------------------------------------------------------------------------;;
+;> src = pointer to little endian MPINT                                      ;;
-endp
+;;---------------------------------------------------------------------------;;
 ;< -                                                                         ;;
-proc mpint_print uses ecx esi eax, src
+;;===========================================================================;;
         DEBUGF  1, "00\n"
         ret
+endp
-endp
-proc mpint_zero uses edi ecx eax, dst
+;;===========================================================================;;
+proc mpint_hob uses edi ecx eax, dst ;///////////////////////////////////////;;
-        mov     edi, [dst]
+;;---------------------------------------------------------------------------;;
-        xor     eax, eax
-        mov     ecx, MPINT_MAX_LEN/4+1
-        rep stosd
-        ret
-endp
+;? Return an index number giving the position of the highest order bit.      ;;
-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
+;> src = pointer to little endian MPINT                                      ;;
+;;---------------------------------------------------------------------------;;
-; return an index number giving the position of the highest order bit
+;< eax = highest order bit number                                            ;;
-proc mpint_hob uses edi ecx, dst
+;;===========================================================================;;
         mov     edi, [dst]
-        ; start from the high order byte
-        add     edi, MPINT_MAX_LEN+4-1
+        lodsd
-        mov     ecx, MPINT_MAX_LEN
-        xor     eax, eax
-        ; scan byte by byte for the first non-zero byte
+        dec     eax                     ; total length minus one
-        std
-        repe scasb
+        mov     cl, [edi+eax]           ; load the highest order byte
-        cld
+        shl     eax, 3                  ; multiply eax by 8 to get nr of bits
-        je      .zero
-        ; calculate how many bits this is, plus 7
-        lea     eax, [ecx*8-1]
-        ; load this high order byte into cl
+; Now shift bits of the highest order byte right, until the byte reaches zero, counting bits meanwhile
-        mov     cl, [edi+1]
+        test    cl, cl
-        ; shift bits of this byte right, until the byte reaches zero, counting bits meanwhile
+        jz      .end
   @@:
         inc     eax
         shr     cl, 1
         jnz     @r
+  .end:
-  .zero:
+        ret
+endp
+;;===========================================================================;;
+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                                      ;;
-        ret
+;;---------------------------------------------------------------------------;;
 ;< flags are set as for single precision CMP instruction                     ;;
-endp
+;;===========================================================================;;
+; First, check if number of significant bytes is the same
+; If not, number with more bytes is bigger
+        mov     esi, [src]
-proc mpint_cmp uses esi edi ecx, dst, src
+        mov     edi, [dst]
+        mov     ecx, [esi]
-        mov     esi, [src]
+        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
-        mov     edi, [dst]
+        jmp     .do_byte
+  .do_dword:
-        ; start from the high order byte
+        shr     ecx, 2
-        add     esi, MPINT_MAX_LEN+4-4
+        jz      .got_answer
-        add     edi, MPINT_MAX_LEN+4-4
+        sub     esi, 4
+        sub     edi, 4
-        mov     ecx, MPINT_MAX_LEN/4
+        repe cmpsd
-        std
+  .got_answer:
-        repe cmpsd
+        cld
+        ret
-        cld
-        ret
+endp
+;;===========================================================================;;
-endp
-proc mpint_mov uses esi edi ecx, dst, src
-        mov     esi, [src]
-        mov     edi, [dst]
+proc mpint_mov uses esi edi ecx, dst, src ;//////////////////////////////////;;
-        mov     ecx, MPINT_MAX_LEN/4+1
+;;---------------------------------------------------------------------------;;
-        rep movsd
+;? Copy mpint.                                                               ;;
 ;;---------------------------------------------------------------------------;;
-        ret
+;> dst = pointer to buffer for little endian MPINT                           ;;
+;> src = pointer to little endian MPINT                                      ;;
-endp
+;;---------------------------------------------------------------------------;;
+;< dst = src                                                                 ;;
-proc mpint_mov0 uses esi edi ecx eax, dst, src
+;;===========================================================================;;
         mov     esi, [src]
-        mov     edi, [dst]
-        mov     ecx, [esi]
-        mov     eax, ecx
+        mov     edi, [dst]
-        neg     eax
+        mov     ecx, [esi]
-        add     esi, 4
+        push    ecx
-        add     edi, 4
+        shr     ecx, 2
+        inc     ecx             ; for length dword
-        rep movsb
+        rep movsd
+        pop     ecx
+        and     ecx, 11b
+        jz      @f
+        rep movsb
+  @@:
+        ret
-        add     eax, MPINT_MAX_LEN
-        jz      @f
+endp
-        mov     ecx, eax
+;;===========================================================================;;
+proc mpint_shl1 uses esi ecx, dst ;//////////////////////////////////////////;;
+;;---------------------------------------------------------------------------;;
-        xor     eax, eax
+;? Shift little endian MPINT one bit to the left.                            ;;
-        rep stosb
+;;---------------------------------------------------------------------------;;
+;> dst = pointer to little endian MPINT                                      ;;
+;;---------------------------------------------------------------------------;;
+;< dst = dst SHL 1                                                           ;;
+;;===========================================================================;;
-  @@:
+        mov     esi, [dst]
+        mov     ecx, [esi]
+        test    ecx, ecx
+        jz      .done
-        ret
+; Test if high order byte will overflow
+; Remember: highest bit must never be set for positive numbers!
+        test    byte[esi+ecx+3], 11000000b
-endp
+        jz      @f
+; We must grow a byte in size!
 ; TODO: check for overflow
-proc mpint_shl1 uses edi ecx eax, dst
+        inc     ecx
+        mov     [esi], ecx
-        mov     edi, [dst]
-        add     edi, 4
+        mov     byte[esi+ecx+3], 0        ; Add the new MSB
-        mov     ecx, MPINT_MAX_LEN/4-1
+  @@:
+        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
-        shl     dword[edi], 1
+        dec     ecx
-        lahf
+        jnz     @r
-  @@:
+  .done:
+        ret
-        add     edi, 4
-        sahf
-        rcl     dword[edi], 1
-        lahf
-        dec     ecx
-        jnz     @r
-        sahf
 endp
+;;===========================================================================;;
+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]
+        mov     ecx, [edi]
+        test    ecx, ecx
+        jz      .done
         ret
+; Do the highest order byte first
-endp
         dec     ecx
-proc mpint_shr1 uses edi ecx eax, dst
+        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
-        mov     edi, [dst]
+  @@:
-        add     edi, MPINT_MAX_LEN+4-4
+        dec     edi
-        mov     ecx, MPINT_MAX_LEN/4-1
+        rcr     byte[edi], 1
         dec     ecx             ; does not affect carry flag, hooray!
   @@:
         cld
         ret
   .zero:
+        mov     eax, [dst]
-        stdcall mpint_zero, [dst]
+        mov     dword[eax], 0
         ret
 endp
+;;===========================================================================;;
+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                     ;;
 ;;---------------------------------------------------------------------------;;
-; Left shift and copy
+;< dst = src SHL shift                                                       ;;
-proc mpint_shlmov uses eax ebx ecx edx esi edi, dst, src, shift
+;;===========================================================================;;
   @@:
         cld
         ret
   .zero:
+        mov     eax, [dst]
-        stdcall mpint_zero, [dst]
+        mov     dword[eax], 0
         ret
+endp
+;;===========================================================================;;
+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                                      ;;
-endp
+;;---------------------------------------------------------------------------;;
-proc mpint_add uses esi edi ecx eax, dst, src
+;< dst = dst + src                                                           ;;
+;;===========================================================================;;
+        mov     esi, [src]
+        mov     edi, [dst]
+        mov     ecx, [esi]      ; source number length
         sub     ecx, [dst]
-        mov     esi, [src]
+        jbe     .length_ok
-        add     esi, 4
-        mov     edi, [dst]
+; Length of the destination is currently smaller then the source, pad with 0 bytes
-        add     edi, 4
+        add     edi, [edi]
-        mov     ecx, MPINT_MAX_LEN/4
+        add     edi, 4
-        xor     ah, ah          ; clear flags (Carry flag most importantly)
+        mov     al, 0
-  @@:
+        rep stosb
-        sahf
+  .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
-        lodsd
+  @@:
-        adc     [edi], eax
+        inc     edi
+        lodsb
+        adc     byte[edi], al
+        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
-        lahf
+        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:
-        add     edi, 4
+        inc     edi
-        dec     ecx
+        mov     byte[edi], 0
+        mov     eax, [dst]
-        jnz     @r
+        inc     dword[eax]
+        ret
+endp
+;;===========================================================================;;
+proc mpint_sub uses eax esi edi ecx, dst, src ;//////////////////////////////;;
+;;---------------------------------------------------------------------------;;
-        sahf
+;? Subtract a little endian MPINT to another little endian MPINT.            ;;
-        ret
+;;---------------------------------------------------------------------------;;
+;> src = pointer to little endian MPINT                                      ;;
+;> dst = pointer to little endian MPINT                                      ;;
+;;---------------------------------------------------------------------------;;
+;< dst = dst - src                                                           ;;
+;;===========================================================================;;
-endp
+        mov     esi, [src]
-proc mpint_sub uses eax esi edi ecx, dst, src
+        mov     edi, [dst]
+        mov     ecx, [esi]      ; destination number length
-        mov     esi, [src]
+        cmp     ecx, [edi]
-        add     esi, 4
+        ja      .overflow
-        mov     edi, [dst]
+        add     esi, 4
         add     edi, 4
+; Subtract the first byte
+        lodsb
-        mov     ecx, MPINT_MAX_LEN/4
+        sub     byte[edi], al
-  .loop:
+        dec     ecx
+        jz      .done
+; Subtract the other bytes
+  @@:
+        inc     edi
+        lodsb
+        sbb     byte[edi], al
+        dec     ecx
-        lodsd
+        jnz     @r
-        sub     [edi], eax
+  .done:
-        jnc     @f
+        stdcall mpint_shrink, [dst]
+        ret
-        dec     dword [edi+4]
+  .overflow:
+        mov     dword[edi], 0
+        stc
+        ret
+endp
-  @@:
-        add     edi, 4
-        dec     ecx
-        jnz     .loop
-        ret
+;;===========================================================================;;
+proc mpint_shrink uses eax edi ecx, dst ;////////////////////////////////////;;
+;;---------------------------------------------------------------------------;;
+;? Get rid of leading zeroes on a little endian MPINT.                       ;;
 ;;---------------------------------------------------------------------------;;
-endp
+;> src = pointer to little endian MPINT                                      ;;
-proc mpint_mul uses esi edi ecx ebx eax, dst, A, B
 ;;---------------------------------------------------------------------------;;
+;<                                                                           ;;
+;;===========================================================================;;
+        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
+        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                                                               ;;
-        stdcall mpint_zero, [dst]
+;;===========================================================================;;
-        ; first, find the byte in A containing the highest order bit
+        ; Set result to zero
-        mov     ecx, MPINT_MAX_LEN
+        mov     eax, [dst]
-        mov     edi, [A]
+        mov     dword[eax], 0
   .zero:
         ret
+endp
-endp
+;;===========================================================================;;
+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
-proc mpint_mod uses eax ecx, dst, mod
+endl
+        ; if mod is zero, return
-        ; if mod is zero, return
+        mov     eax, [mod]
-        stdcall mpint_zero?, [mod]
+        cmp     dword[eax], 0
-        jz      .zero
+        je      .zero
+        stdcall mpint_cmp, eax, [dst]
         jb      .done                           ; if dst < mod, dst = dst
-        stdcall mpint_cmp, [mod], [dst]
+        je      .zero                           ; if dst == mod, dst = 0
         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
-        jz      .done
+        ;   shift mpint_tmp right by 1
-        ;   shift mpint_tmp right by 1
+        stdcall mpint_shr1, ebx
-        stdcall mpint_shr1, mpint_tmp
+        jmp     .loop
-        jmp     .loop
+  .zero:
+        mov     eax, [dst]
+        mov     dword[eax], 0
+  .done:
+        ret
+endp
+;;===========================================================================;;
+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                                      ;;
-  .zero:
+;> mod = pointer to little endian MPINT                                      ;;
+;;---------------------------------------------------------------------------;;
-        stdcall mpint_zero, [dst]
+;< dst = base ** exp MOD mod                                                 ;;
-  .done:
+;;===========================================================================;;
         ret
 locals
-endp
+        mpint_tmp       rb MPINT_MAX_LEN+4
   @@:
         dec     bl
         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_mov, edx, [dst]
-        stdcall mpint_mul, [dst], mpint_tmp, mpint_tmp
+        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_mov, edx, [dst]
-        stdcall mpint_mul, [dst], [base], mpint_tmp
+        stdcall mpint_mul, [dst], [base], edx
         stdcall mpint_mod, [dst], [mod]
   .next_bit:
         dec     bl
         ret
   .mod_zero:
         DEBUGF  3, "modexp with modulo 0\n"
         ; if mod is zero, result = 0
+        mov     eax, [dst]
-        stdcall mpint_zero, [dst]
+        mov     dword[eax], 0
         ret
   .exp_zero:
-        DEBUGF  3, "modexp with exponent 0\n"
-        ; if exponent is zero, result = 1
+        DEBUGF  3, "modexp with exponent 0\n"
-        stdcall mpint_zero, [dst]
+        ; if exponent is zero, result = 1
         mov     eax, [dst]
-        mov     byte[eax], 1
+        mov     dword[eax], 1
         mov     byte[eax+4], 1
         ret

Subversion Repositories Kolibri OS

(root)/programs/network/ssh/mpint.inc – Rev 6469 → 6922