Subversion Repositories Kolibri OS

;    mpint.inc - Multi precision integer procedures

;

;    Copyright (C) 2015-2016 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.

;

;    This program is distributed in the hope that it will be useful,

;    but WITHOUT ANY WARRANTY; without even the implied warranty of

;    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

;    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 .

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:

; Load length dword

        lodsd

; Convert to little endian

        bswap   eax

        stosd

        test    eax, eax

        jz      .zero

; Copy data, convert to little endian meanwhile

        push    eax

        add     esi, eax

        push    esi

        dec     esi

        mov     ecx, eax

        std

  @@:

        lodsb

        mov     byte[edi], al

        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

mpint_to_big_endian:

; Load length dword

        lodsd

        test    eax, eax

        jz      .zero

        mov     ecx, eax

        add     esi, ecx

        dec     esi

        test    byte[esi], 0x80   ; Is the highest bit set?

        jz      @f

        inc     eax

  @@:

        push    eax

        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

        inc     edi

        dec     ecx

        jnz     @r

        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

        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

        DEBUGF  1, "0x"

        mov     esi, [src]

        mov     ecx, [esi]

        test    ecx, ecx

        jz      .zero

        lea     esi, [esi + ecx + 4 - 1]

        pushf

        std

  .loop:

        lodsb

        DEBUGF  1, "%x", eax:2

        dec     ecx

        jnz     .loop

        DEBUGF  1, "\n"

        popf

        ret

  .zero:

        DEBUGF  1, "00\n"

        ret

endp

proc mpint_zero uses edi ecx eax, dst

        mov     edi, [dst]

        xor     eax, eax

        mov     ecx, MPINT_MAX_LEN/4+1

        rep stosd

        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

  @@:

        inc     eax

        shr     cl, 1

        jnz     @r

  .zero:

        ret

endp

proc mpint_cmp uses esi edi ecx, dst, src

        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

        std

        repe cmpsd

        cld

        ret

endp

proc mpint_mov uses esi edi ecx, dst, src

        mov     esi, [src]

        mov     edi, [dst]

        mov     ecx, MPINT_MAX_LEN/4+1

        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

        rep movsb

        add     eax, MPINT_MAX_LEN

        jz      @f

        mov     ecx, eax

        xor     eax, eax

        rep stosb

  @@:

        ret

endp

proc mpint_shl1 uses edi ecx eax, dst

        mov     edi, [dst]

        add     edi, 4

        mov     ecx, MPINT_MAX_LEN/4-1

        shl     dword[edi], 1

        lahf

  @@:

        add     edi, 4

        sahf

        rcl     dword[edi], 1

        lahf

        dec     ecx

        jnz     @r

        sahf

        ret

endp

proc mpint_shr1 uses edi ecx eax, dst

        mov     edi, [dst]

        add     edi, MPINT_MAX_LEN+4-4

        mov     ecx, MPINT_MAX_LEN/4-1

        shr     dword[edi], 1

        lahf

  @@:

        sub     edi, 4

        sahf

        rcr     dword[edi], 1

        lahf

        dec     ecx

        jnz     @r

        sahf

        ret

endp

proc mpint_shl uses eax ebx ecx edx esi edi, dst, shift

        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

        sub     esi, ecx

        mov     edx, MPINT_MAX_LEN/4-1

        shr     ecx, 2                  ; 4 bytes in one dword

        push    ecx

        sub     edx, ecx

        mov     ecx, [shift]

        and     ecx, 11111b

        std

  .loop:

        lodsd

        mov     ebx, [esi]

        shld    eax, ebx, cl

        stosd

        dec     edx

        jnz     .loop

        lodsd

        shl     eax, cl

        stosd

        ; fill the lsb bytes with zeros

        pop     ecx

        test    ecx, ecx

        jz      @f

        xor     eax, eax

        rep stosd

  @@:

        cld

        ret

  .zero:

        stdcall mpint_zero, [dst]

        ret

endp

; Left shift and copy

proc mpint_shlmov uses eax ebx ecx edx esi edi, dst, src, shift

        mov     ecx, [shift]

        shr     ecx, 3                  ; 8 bits in one byte

        cmp     ecx, MPINT_MAX_LEN

        jge     .zero

        mov     esi, [src]

        add     esi, MPINT_MAX_LEN+4-4

        mov     edi, [dst]

        add     edi, MPINT_MAX_LEN+4-4

        and     ecx, not 11b

        sub     esi, ecx

        mov     edx, MPINT_MAX_LEN/4-1

        shr     ecx, 2                  ; 4 bytes in one dword

        push    ecx

        sub     edx, ecx

        mov     ecx, [shift]

        and     ecx, 11111b

        std

  .loop:

        lodsd

        mov     ebx, [esi]

        shld    eax, ebx, cl

        stosd

        dec     edx

        jnz     .loop

        lodsd

        shl     eax, cl

        stosd

        ; fill the lsb bytes with zeros

        pop     ecx

        test    ecx, ecx

        jz      @f

        xor     eax, eax

        rep stosd

  @@:

        cld

        ret

  .zero:

        stdcall mpint_zero, [dst]

        ret

endp

proc mpint_add uses esi edi ecx eax, dst, src

        mov     esi, [src]

        add     esi, 4

        mov     edi, [dst]

        add     edi, 4

        mov     ecx, MPINT_MAX_LEN/4

        xor     ah, ah          ; clear flags (Carry flag most importantly)

  @@:

        sahf

        lodsd

        adc     [edi], eax

        lahf

        add     edi, 4

        dec     ecx

        jnz     @r

        sahf

        ret

endp

proc mpint_sub uses eax esi edi ecx, dst, src

        mov     esi, [src]

        add     esi, 4

        mov     edi, [dst]

        add     edi, 4

        mov     ecx, MPINT_MAX_LEN/4

        ; dst = dst + (NOT src) + 1

        stc                     ; Setting CF takes care of the +1

        pushf

  @@:

        lodsd

        not     eax

        popf

        adc     [edi], eax

        pushf

        add     edi, 4

        dec     ecx

        jnz     @r

        popf

        ret

endp

proc mpint_mul uses esi edi ecx ebx eax, dst, A, B

        stdcall mpint_zero, [dst]

        ; 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

        std

        xor     al, al

        repe scasb

        cld

        je      .zero

        inc     ecx

        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,

        ; starting from the highest order bit down to the lowest order bit.

  .next_byte:

        mov     al, [edi]

        dec     edi

        mov     bl, 8

  .next_bit:

        stdcall mpint_shl1, [dst]

        shl     al, 1

        jnc     .zero_bit

  .first_hit:

        stdcall mpint_add, [dst], [B]

  .zero_bit:

        dec     bl

        jnz     .next_bit

        dec     ecx

        jnz     .next_byte

  .zero:

        ret

endp

proc mpint_mod uses eax ecx, dst, mod

        ; if mod is zero, return

        stdcall mpint_zero?, [mod]

        jz      .zero

        stdcall mpint_cmp, [mod], [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

        stdcall mpint_hob, [dst]

        mov     ecx, eax

        stdcall mpint_hob, [mod]

        sub     ecx, eax

        stdcall mpint_shlmov, mpint_tmp, [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

        ja      @f

        ;   if so, subtract mpint_tmp from dst

        stdcall mpint_sub, [dst], mpint_tmp

  @@:

        dec     ecx

        jz      .done

        ;   shift mpint_tmp right by 1

        stdcall mpint_shr1, mpint_tmp

        jmp     .loop

  .zero:

        stdcall mpint_zero, [dst]

  .done:

        ret

endp

proc mpint_modexp uses edi eax ebx ecx, dst, base, exp, mod

        ; If mod is zero, return

        stdcall mpint_zero?, [mod]

        jz      .mod_zero

        ; Find the highest order byte in exponent

        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

        jz      .invalid

        mov     bl, 9

  @@:

        dec     bl

        shl     al, 1

        jnc     @r

        ; Initialise result to base, to take care of the highest order bit

        stdcall mpint_mov0, [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_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_mod, [dst], [mod]

  .next_bit:

        dec     bl

        jnz     .bit_loop

  .next_byte:

        dec     ecx

        jz      .done

        dec     edi

        mov     al, [edi]

        mov     bl, 8

        jmp     .bit_loop

  .done:

        ret

  .mod_zero:

        DEBUGF  1, "modexp with modulo 0\n"

        ; if mod is zero, result = 0

        stdcall mpint_zero, [dst]

        ret

  .exp_zero:

        DEBUGF  1, "modexp with exponent 0\n"

        ; if exponent is zero, result = 1

        stdcall mpint_zero, [dst]

        mov     eax, [dst]

        mov     byte[eax], 1

        mov     byte[eax+4], 1

        ret

  .invalid:

        DEBUGF  1, "modexp: Invalid input!\n"

        ret

endp