Huge number module

[coco2]

A module for working with integers of any length. Useful for encryption eg- RSA
I use this module in my PureBasic RSA module: http://www.purebasic.fr/english/viewtop ... 12&t=60682

Uses memory module: http://www.purebasic.fr/english/viewtop ... 12&t=61103
And debug macros:

Code: Select all

Macro DebugOut(DebugText)
  Debug #PB_Compiler_Module+"::"+#PB_Compiler_Procedure+": "+DebugText
EndMacro

Macro DebugPrintN (DebugText)
  PrintN(#PB_Compiler_Module+"::"+#PB_Compiler_Procedure+": "+DebugText)
EndMacro

Release history:
1.0 - 2014-Oct-03 - initial release (positive numbers only)
1.1 - 2014-Nov-21 - bug fix in Load(), would not load into an existing
1.2 - 2014-Nov-28 - fixed bugs, added self test and module name changed to Cc2Huge
1.3 - 2014-Dec-01 - bug fix in unload

Code: Select all

; cc2huge.pbi==================================================================
; Huge number module
; Module version: 1.3
; Description: Manipulate huge numbers, with basic arithmetic. Numbers can
;   be any length in multiples of 8 bits.
; TODO: implement byte alignment for 4 bytes to optimise speed
; TODO: implement negatives
; Platform: Windows, Linux, Mac
; CPU architechtures: x86, x64
; Requirements (includes): none
; Limitations: only works with positive numbers
; Developed on: PB 5.30 Beta 4 x64; Windows 7 x64
; Author: coco2
; Credit: wilbert for some help with assembly,
;   also see "further reading" list below
; Created:  06-Jun-2014
; License: open
; Release history:
;   1.0    - 2014-Oct-03 - initial release
;   1.1    - 2014-Nov-21 - bug fix in Load(), would not load into an already
;                          loaded huge number
;   1.2    - 2014-Nov-28 - fixed bugs, added self test and module name
;                          changed to Cc2Huge
;   1.3    - 2014-Dec-01 - bug fix in unload
;
; Provided "as is" with no warranty and no liability.
;
; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
; AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
; IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
; ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
; LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
; CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
; SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
; INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
; CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
; ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
; POSSIBILITY OF SUCH DAMAGE.
;
; Notes:
; 1. The authors/copyright holder(s) of this module are not affiliated with
;    the PureBasic software authors/copyright holders.
; ==========================================================================
; 
; Further reading:
; 
; - Implementing SSL / TLS Using Cryptography and PKI
;   (ISBN: 978-0-470-92041-1)
; - http://en.wikipedia.org/wiki/Exponentiation_by_squaring
;
; ==========================================================================


;- Module includes
  
XIncludeFile("../../mem/cc2mem.pbi")        ; memory formatting (for debugging)


DeclareModule Cc2Huge
  
  CompilerIf #PB_Compiler_IsMainFile
    EnableExplicit
  CompilerEndIf   
  
  ;- Public structures
  
  Structure huge_type
    sign.i ; 0 = positive, 1 = negative
    size.i ; length in bytes of the number
    *num   ; the array of uint8 (ASCII) to hold the number in base 2 binary format
  EndStructure
  
  Structure AArray
    a.a[0]
  EndStructure   
  
  ;- Procedure declares
  
  Declare New(size.i=1)
  Declare Destroy(*h.huge_type)
  Declare Copy(*Src.huge_type, *Dest.huge_Type)
  Declare Load(*h.huge_type, *buffer, length.i)
  Declare Unload(*h.huge_type, *buffer, length.i)
  Declare Compare(*h1.huge_type, *h2.huge_type)
  Declare Set(*h.huge_type, val.a, pos.i)
  Declare SetInt32(*h.huge_type, value.i)
  Declare Add(*h1.huge_type, *h2.huge_type)
  Declare Subtract(*h1.huge_type, *h2.huge_type)
  Declare Multiply(*h1.huge_type, *h2.huge_type)
  Declare Divide(*dividend.huge_type, *divisor.huge_type, *quotient.huge_type=0)
  Declare Exponentiate(*h.huge_type, *exp.huge_type)
  Declare ModPow(*h1.huge_type, *exp.huge_type, *n.huge_type, *h2.huge_type)
  
EndDeclareModule

Module Cc2Huge
  
  CompilerIf #PB_Compiler_IsMainFile
    EnableExplicit
  CompilerEndIf 
  
  ;- Includes - macros
  ; make sure this is before Module includes And Not xinclude
  
  IncludeFile("../../debug/cc2debug.pbi") ; macros for formatting debug output  
  
  Procedure.i Expand(*h.huge_type)
    ; expands by one byte (needed after an addition or left shift that overflows)
    Define *temp, result.i=0
    *temp = ReAllocateMemory(*h\num, *h\size+1)
    If *temp
      ; successfully resized
      MoveMemory(*temp, *temp + 1, *h\size)
      *h\size = *h\size + 1
      *h\num = *temp
      *temp = 0
      PokeA(*h\num, 1) ; add carry bit
      result = 1
    EndIf
    ProcedureReturn result
  EndProcedure
  
  Procedure Contract(*h.huge_type)
    ; remove most significant zeros
    Define failed.i=0
    Define *temp
    Define i.i=0, new_size.i=0
    While PeekA(*h\num+i)=0 And (i < *h\size)
      i = i + 1
    Wend
    If i And i < *h\size
      new_size  = *h\size - i
      *temp = AllocateMemory(new_size)
      If *temp
        CopyMemory(*h\num+i, *temp, new_size)
        *h\num = *temp ; reassign the pointer
        *h\size = new_size
        *temp=0
      Else
        failed=1
      EndIf
    EndIf
    ProcedureReturn 1 - failed
  EndProcedure
  
  Procedure ShiftLeftBuffer(*data, length.l)
    !xor eax, eax
    !mov ecx, [p.v_length]
    !dec ecx
    !jc slb_exit
    CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
      !mov rdx, [p.p_data]
      !slb_loop:  
      !mov ah, [rdx + rcx]
      !shl eax, 1
      !mov [rdx + rcx], ah
    CompilerElse
      !mov edx, [p.p_data]
      !slb_loop:  
      !mov ah, [edx + ecx]
      !shl eax, 1
      !mov [edx + ecx], ah
    CompilerEndIf
    !shr eax, 9
    !sub ecx, 1
    !jnc slb_loop
    !slb_exit:
    !shr eax, 7
    ProcedureReturn
  EndProcedure
  
  Procedure ShiftRightBuffer(*data, length.l)
    !xor eax, eax
    !mov ecx, [p.v_length]
    !and ecx, ecx
    !jz srb_exit
    CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
      !mov rdx, [p.p_data]
      !srb_loop:  
      !mov ah, [rdx]
      !shr eax, 1
      !mov [rdx], ah
      !inc rdx
    CompilerElse
      !mov edx, [p.p_data]
      !srb_loop:  
      !mov ah, [edx]
      !shr eax, 1
      !mov [edx], ah
      !inc edx
    CompilerEndIf  
    !shl eax, 9
    !dec ecx
    !jnz srb_loop
    !srb_exit:
    !shr eax, 16
    !and eax, 1
    ProcedureReturn
  EndProcedure
  
  Procedure ShiftLeftBufferOld(*data, length.l)
    !clc                                                         ; clear carry flag
    !mov ecx, [p.v_length]                                       ; set counter
    !jecxz slb_exit                                              ; if ecx zero jump to slb_exit
    CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
      !mov rdx, [p.p_data]                                       ; x64: move the pointer into rdx
      !slb_loop:
      !rcl byte [rdx + rcx - 1], 1                               ; rotate the byte with the last bit placed in carry
    CompilerElse
      !mov edx, [p.p_data]                                       ; x84: move the pointer into edx
      !slb_loop:
      !rcl byte [edx + ecx - 1], 1                               ; rotate the byte with the last bit placed in carry
    CompilerEndIf
    !dec ecx                                                     ; decrement ecx
    !jnz slb_loop
    !slb_exit:
    !sbb eax, eax                                                ; move carry into eax
    !neg eax                                                     ; eax = 0 - eax
    ProcedureReturn
  EndProcedure
  
  Procedure ShiftRightBufferOld(*data, length.l)
    !clc                                                         ; clear carry flag
    !mov ecx, [p.v_length]                                       ; set counter
    !jecxz srb_exit                                              ; if ecx zero jump to slb_exit
    !xor eax, eax                                                ; set eax to zero
    CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
      !mov rdx, [p.p_data]                                       ; x64: move the pointer into rdx
      !srb_loop:
      !rcr byte [rdx + rax], 1                                   ; rotate the byte with the last bit placed in carry
    CompilerElse
      !mov edx, [p.p_data]                                       ; x84: move the pointer into edx
      !srb_loop:
      !rcr byte [edx + eax], 1                                   ; rotate the byte with the last bit placed in carry
    CompilerEndIf
    !inc eax                                                     ; increment eax
    !dec ecx                                                     ; decrement ecx  
    !jnz srb_loop
    !srb_exit:
    !sbb eax, eax                                                ; move carry into eax
    !neg eax                                                     ; eax = 0 - eax
    ProcedureReturn                                            ; return eax
  EndProcedure 
  
  ;- Declared Procedures
  
  Procedure New(size.i=1)
    ; Usage:
    ;   Define *h.Huge::huge_type ; create the pointer to a structure
    ;   *h = Cc2Huge::New()       ; allocate memory to thew pointer
    ;
    ;   result = Destroy(*h)      ; free memory
    ;
    ; returns zero if failed
    ; size in bytes
    ; 
    Define *new_huge.Huge_Type
    *new_huge = AllocateMemory(SizeOf(Huge_Type))
    If *new_huge
      *new_huge\num = AllocateMemory(size)
      If *new_huge\num
        FillMemory(*new_huge\num, size, 0)
        *new_huge\size = size
      EndIf
    EndIf
    ProcedureReturn *new_huge ; returns zero if failed to allocate memory
  EndProcedure
  
  Procedure Destroy(*h.huge_type)
    ; Free memory of a huge_type
    Define failed.i=0
    If *h
      If *h\num
        FreeMemory(*h\num)
      Else
        failed = 1
      EndIf
      FreeMemory(*h)
    Else
      failed = 1      
    EndIf
    ProcedureReturn 1 - failed
  EndProcedure
  
  Procedure.i Copy(*src.huge_type, *dest.huge_Type)
    Define failed.i=0
    If *dest
      If *dest\num
        FreeMemory(*dest\num)
        *dest\num = AllocateMemory(*src\size)
        If *dest\num
          CopyMemory(*src\num, *dest\num, *src\size)
          *dest\size = *src\size
        Else
          failed = 1
        EndIf
      Else
        failed = 1 ; can't copy to a null pointer
      EndIf      
    Else
      failed = 1 ; can't copy to a null pointer
    EndIf  
    ProcedureReturn 1 - failed
  EndProcedure
  
  Procedure.i Load(*h.huge_type, *buffer, length.i)
    ; Returns 0 - fail, 1 - success
    Define i.i=0, new_length.i
    Define failed.i=0
    Define *temp
    ; check for valid parametres
    If *h And *buffer And length > 0
      If *h\num
        ; Skip leading zeros
        While (PeekA(*buffer+i) = 0) And (i < length) ; skip leading zeros, but if last byte is zero, use it
          i = i + 1
        Wend
        new_length = length - i
        If *h\size <> new_length ; reallocate *h\num
          *temp = ReAllocateMemory(*h\num, new_length)
          If *temp
            *h\num = *temp
            *h\size = new_length
            *temp = 0
            CopyMemory(*buffer+i, *h\num, new_length)
          Else
            failed = 1
          EndIf
        Else
          ; copy without reallocating
          CopyMemory(*buffer+i, *h\num, new_length)
        EndIf
      Else
        failed = 1
      EndIf
    Else
      failed = 1
    EndIf
    ProcedureReturn 1 - failed
  EndProcedure
  
  Procedure.i Unload(*h.huge_type, *buffer, length.i)
    Define failed.i=0
    ; check for valid parametres
    If *h And *buffer And length > 0
      If *h\num
        ;CopyMemory(*h\num+(length-*h\size), *buffer, length)
        CopyMemory(*h\num, *buffer, length)
      Else
        failed = 1
      EndIf
    Else
      failed = 1
    EndIf
    ProcedureReturn 1 - failed
  EndProcedure  
  
  
  Procedure Compare(*h1.huge_type, *h2.huge_type)
    ; returns 0 if equal
    ; positive number if h1 > h2
    ; negative number if h1 < h2
    Define i.i, j.i, v1.i, v2.i
    Define Result.i=0
    If *h1\size > *h2\size
      result = 1      
    EndIf
    If *h1\size < *h2\size
      result = -1
    EndIf
    If result = 0
      i=0: j=0
      While (i < *h1\size) And (j < *h2\size)
        v1 = PeekA(*h1\num+i)
        v2 = PeekA(*h2\num+j)
        If v1 < v2
          result = -1
          Break
        ElseIf v1 > v2
          result = 1
          Break
        EndIf
        i = i + 1 : j = j + 1
      Wend
    EndIf
    ProcedureReturn result
  EndProcedure
  
  Procedure.i Set(*h.huge_type, value.a, pos.i)
    ; pos: 0 = LSB
    Define failed.i=0
    If *h\size > pos
      PokeA(*h\num+*h\size-1-pos, value)
    Else
      failed = 1
    EndIf
    ProcedureReturn 1 - failed
  EndProcedure  
  
  Procedure.i SetInt32(*h.huge_type, value.i)
    Define failed.i = 0
    Define mask.l, i.l, shift.l, new_val.l
    *h\size = 4
    mask = $FF000000
    While mask > $000000FF ; skip the LSB
      If value & mask
        Break
      EndIf
      *h\size = *h\size - 1
      ; logical shift right by one byte
      !mov edx, dword [p.v_mask]
      !shr edx, 8
      !mov dword [p.v_mask], edx      
    Wend
    If *h\num
      FreeMemory(*h\num)
      *h\num = AllocateMemory(*h\size)
      If *h\num
        mask = $000000FF
        shift = 0
        i = *h\size
        While i
          new_val = (value & mask)
          ; logical shift right new_val by shift amount
          !mov edx, dword [p.v_new_val]
          !mov ecx, dword [p.v_shift]
          !shr edx, cl
          !mov dword [p.v_new_val], edx         
          PokeA(*h\num+i-1, new_val)
          mask = mask << 8
          shift = shift + 8
          i = i - 1
        Wend
        Contract(*h)
      Else
        failed = 1
      EndIf
    Else
      failed = 1
    EndIf    
    ProcedureReturn 1 - failed
  EndProcedure
  
  Procedure.i Add(*h1.huge_type, *h2.huge_type)
    ; Result stored in h1
    Define *temp
    Define failed.i=0
    Define i.i, j.i, k.i, sum.i, carry.i=0
    If *h2\size > *h1\size
      ; resize h1
      k = *h2\size - *h1\size
      *temp = ReAllocateMemory(*h1\num, *h2\size)
      If *temp
        MoveMemory(*temp, *temp + k, *h1\size)
        FillMemory(*temp, k, 0)
        *h1\size + k
        *h1\num = *temp ; reassign the pointer
        *temp = 0
      Else
        ; resize failed
        failed = 1        
      EndIf
    EndIf
    If Not failed
      i = *h1\size
      j = *h2\size
      ;- TODO - optimise the following:
      While i
        i=i-1
        If j
          j=j-1
          sum = PeekA(*h1\num+i) + PeekA(*h2\num+j) + carry
        Else
          sum = PeekA(*h1\num+i) + carry
        EndIf
        If sum > $FF : carry = 1 : Else : carry = 0 : EndIf
        PokeA(*h1\num+i, sum)
      Wend
      ; *** end optimise ***
      If carry ; check if the huge needs expanding by 1
        If Not Expand(*h1)
          ; Unable to expand, add fails
          failed=1
        EndIf
      EndIf
      ; all completed successfully
    EndIf
    ProcedureReturn 1 - failed
  EndProcedure
  
  Procedure.i Subtract(*h1.huge_type, *h2.huge_type)
    ; Result stored in h1
    Define failed.i=0
    Define i.i, j.i
    Define difference.i
    Define borrow.i=0
    i = *h1\size
    j = *h2\size
    ;- TODO optimise the following
    While i
      i = i - 1
      If j
        j = j - 1
        difference = PeekA(*h1\num+i) - PeekA(*h2\num+j) - borrow
      Else
        difference = PeekA(*h1\num+i) - borrow
      EndIf
      If difference < 0 : borrow = 1 : Else : borrow = 0 : EndIf
      PokeA(*h1\num+i, difference)
    Wend
    ; *** end optimise ***
    If borrow
      If ~PeekA(*h1\num+i-1)
        ; negative
        failed = 1 ; fail as can't handle negatives
      Else
        PokeA(*h1\num+i-1, (*h1\num+i-1)-1)
      EndIf
    EndIf
    If Not failed
      Contract(*h1)
    EndIf
    ProcedureReturn 1 - failed
  EndProcedure
  
  Procedure.i Multiply(*h1.huge_type, *h2.huge_type)
    ; Result stored in h1
    Define failed.i=0
    Define mask.a
    Define i.i
    Define *temp.huge_type
    *temp.huge_type = New()  
    If *temp
      Copy(*h1, *temp)
      SetInt32(*h1, 0)
      i = *h2\size
      While i
        i = i - 1
        mask = 1
        While mask > 0
          If (mask & PeekA(*h2\num+i))
            Add(*h1, *temp)
          EndIf
          If ShiftLeftBuffer(*temp\num, *temp\size) : Expand(*temp) : EndIf
          mask = mask << 1
        Wend
      Wend
      Contract(*h1) ; remove most significant zeros (these can cause problems)
      FreeMemory(*temp)
    EndIf
    ProcedureReturn 1 - failed
  EndProcedure
  
  Procedure Divide(*dividend.huge_type, *divisor.huge_type, *quotient.huge_type=0)
    ; dividend = the number to divide
    ; divisor = the amount to divide by
    ; quotient becomes the result of the division (can be ignored if only the remainder is needed)
    ; dividend becomes the remainder
    Define failed.i=0
    Define bit_size.i=0, bit_position.i=0
    Define *temp
    Define v.i
    While Compare(*divisor, *dividend) < 0 ; 
      If ShiftLeftBuffer(*divisor\num, *divisor\size) : Expand(*divisor) : EndIf
      bit_size = bit_size + 1
    Wend
    If *quotient
      If *quotient\num
        *quotient\size = (bit_size / 8) + 1
        *temp = ReAllocateMemory(*quotient\num, *quotient\size)
      EndIf
      If *temp
        *quotient\num = *temp
        *temp = 0
      Else
        failed = 1
      EndIf
    EndIf
    bit_position = 8 - (bit_size % 8) - 1
    Repeat
      If Compare(*divisor, *dividend) <= 0
        subtract(*dividend, *divisor)
        If *quotient And Not failed ; only calculate quotient if memory was allocated
          v = PeekA(*quotient\num+(bit_position / 8))
          PokeA(*quotient\num+(bit_position / 8), v | ($80 >> (bit_position % 8)))
        EndIf
      EndIf
      If bit_size
        ShiftRightBuffer(*divisor\num, *divisor\size)
        Contract(*divisor)
      EndIf
      bit_position = bit_position + 1
      bit_size = bit_size - 1
    Until bit_size < 0
    ProcedureReturn 1 - failed
  EndProcedure
  
  Procedure.i Exponentiate(*h.huge_type, *exp.huge_type)
    ; very slow, only included for educational purposes
    ; result stored in *h
    Define failed.i=0
    Define i.i = *exp\size
    Define mask.a
    Define *temp1.huge_type = New()
    Define *temp2.huge_type = New()
    If *temp1 And *temp2
      SetInt32(*temp1, 0)
      SetInt32(*temp2, 0)
      Copy(*h, *temp1)
      SetInt32(*h, 1)
      Repeat
        i = i - 1
        mask = $01
        While mask > 0
          If PeekA(*exp\num+i) & mask
            Multiply(*h, *temp1)
          EndIf
          Copy(*temp1, *temp2)
          Multiply(*temp1, *temp2)
          mask = mask << 1
        Wend
      Until i = 0
      Destroy(*temp1)
      Destroy(*temp2)
    Else
      failed = 1
    EndIf
    ProcedureReturn 1 - failed
  EndProcedure
  
  Procedure ModPow(*h1.huge_type, *exp.huge_type, *n.huge_type, *h2.huge_type)
    ; Compute *h2 = *h1^*exp mod *n
    ;
    ; RSA usage:
    ; Encrypt: c = m^e % n
    ; Decrypt: m = c^d % n
    Define failed.i=0
    Define i.i = *exp\size
    Define mask.a
    Define *temp1.huge_type = New()
    Define *temp2.huge_type = New()
    If *temp1 And *temp2 ; make sure temp variables were created successfully
      SetInt32(*temp1, 0); set them to zero
      SetInt32(*temp2, 0)
      Copy(*h1, *temp1)
      SetInt32(*h2, 1) ; set destination to 1
      Repeat
        i = i - 1
        DebugOut("Processing byte: " + i)
        mask = $01 ; set bit mask to 00000000 00000001
        While mask > 0 ; process all bits
          If PeekA(*exp\num+i) & mask ; if bit is set on the mask
            Multiply(*h2, *temp1)
            Divide(*h2, *n)
          EndIf
          Copy(*temp1, *temp2)
          Multiply(*temp1, *temp2)
          Divide(*temp1, *n)
          mask = mask << 1
        Wend
      Until i = 0
      Destroy(*temp1)
      Destroy(*temp2)
    Else
      failed = 1
    EndIf
    ProcedureReturn 1 - failed    
  EndProcedure
  
  Procedure SelfTest()
    OpenConsole()
    DebugPrintN("running self test")
    DebugOut("running self test")
    
    Define showNum.i = 0 ; Show memory as 0-hex 1-dec 2-bin
    
    Define *dbuffer = AllocateMemory(?EndofHuge1-?Huge1) ; load however much data is in the data section
    
    Define *h1.Cc2Huge::huge_type = New()
    Define *h2.Cc2Huge::huge_type = New()
    Define *h3.Cc2Huge::huge_type = New()
    Define *h4.Cc2Huge::huge_type = New() 
    Define *h5.Cc2Huge::huge_type = New()
        
    CopyMemory(?Huge1, *dbuffer, ?EndofHuge1-?Huge1)
    Load(*h1, *dbuffer, MemorySize(*dbuffer))
    CopyMemory(?Huge2, *dbuffer, ?EndofHuge2-?Huge2)
    Load(*h2, *dbuffer, MemorySize(*dbuffer))
    
    ; Addition test(s)
    DebugPrintN("Addition: " + Cc2Mem::DebugMemory(*h1\num, MemorySize(*h1\num), showNum) + "+ " + Cc2Mem::DebugMemory(*h2\num, MemorySize(*h2\num), showNum))
    DebugOut("Addition: " + Cc2Mem::DebugMemory(*h1\num, MemorySize(*h1\num), showNum) + "+ " + Cc2Mem::DebugMemory(*h2\num, MemorySize(*h2\num), showNum))
    Add(*h1, *h2)
    DebugPrintN("= " + Cc2Mem::DebugMemory(*h1\num, MemorySize(*h1\num), showNum))
    DebugOut("= " + Cc2Mem::DebugMemory(*h1\num, MemorySize(*h1\num), showNum))
    
    ; Subtraction test(s)
    DebugPrintN("Subtraction: " + Cc2Mem::DebugMemory(*h1\num, MemorySize(*h1\num), showNum) + "- " + Cc2Mem::DebugMemory(*h2\num, MemorySize(*h2\num), showNum))
    DebugOut("Subtraction: " + Cc2Mem::DebugMemory(*h1\num, MemorySize(*h1\num), showNum) + "- " + Cc2Mem::DebugMemory(*h2\num, MemorySize(*h2\num), showNum))
    Subtract(*h1, *h2)
    DebugPrintN("= " + Cc2Mem::DebugMemory(*h1\num, MemorySize(*h1\num), showNum))
    DebugOut("= " + Cc2Mem::DebugMemory(*h1\num, MemorySize(*h1\num), showNum))
    
    ; Multiplication test(s)
    DebugPrintN("Multiplication: " + Cc2Mem::DebugMemory(*h1\num, MemorySize(*h1\num), showNum) + "* " + Cc2Mem::DebugMemory(*h2\num, MemorySize(*h2\num), showNum))
    DebugOut("Multiplication: " + Cc2Mem::DebugMemory(*h1\num, MemorySize(*h1\num), showNum) + "* " + Cc2Mem::DebugMemory(*h2\num, MemorySize(*h2\num), showNum))
    Multiply(*h1, *h2)
    DebugPrintN("= " + Cc2Mem::DebugMemory(*h1\num, MemorySize(*h1\num), showNum))
    DebugOut("= " + Cc2Mem::DebugMemory(*h1\num, MemorySize(*h1\num), showNum))    
    
    ; Division test(s)
    DebugPrintN("Division: " + Cc2Mem::DebugMemory(*h1\num, MemorySize(*h1\num), showNum) + "/ " + Cc2Mem::DebugMemory(*h2\num, MemorySize(*h2\num), showNum))
    DebugOut("Division: " + Cc2Mem::DebugMemory(*h1\num, MemorySize(*h1\num), showNum) + "/ " + Cc2Mem::DebugMemory(*h2\num, MemorySize(*h2\num), showNum))
    Divide(*h1, *h2, *h3)
    DebugPrintN("= " + Cc2Mem::DebugMemory(*h3\num, MemorySize(*h3\num), showNum))
    DebugOut("= " + Cc2Mem::DebugMemory(*h3\num, MemorySize(*h3\num), showNum))      
    
    ; Exponentiation test(s)
    ;CopyMemory(?Huge1, *dbuffer, ?EndofHuge1-?Huge1)
    ;Load(*h1, *dbuffer, MemorySize(*dbuffer))
    ;CopyMemory(?Huge2, *dbuffer, ?EndofHuge2-?Huge2)
    
    SetInt32(*h1, 8457)
    SetInt32(*h2, 2)
    DebugPrintN("Exponentiation: " + Cc2Mem::DebugMemory(*h1\num, MemorySize(*h1\num), showNum) + "^ " + Cc2Mem::DebugMemory(*h2\num, MemorySize(*h2\num), showNum))
    DebugOut("Exponentiation: " + Cc2Mem::DebugMemory(*h1\num, MemorySize(*h1\num), showNum) + "^ " + Cc2Mem::DebugMemory(*h2\num, MemorySize(*h2\num), showNum))
    Exponentiate(*h1, *h2)
    DebugPrintN("= " + Cc2Mem::DebugMemory(*h1\num, MemorySize(*h1\num), showNum))
    DebugOut("= " + Cc2Mem::DebugMemory(*h1\num, MemorySize(*h1\num), showNum))      
    
    ; Modulus Exponentiation test(s) 
    ;
    ; Compute *h2 = *h1^*exp mod *n
    ;
    ; RSA usage:
    ; Encrypt: c = m^e % n
    ; Decrypt: m = c^d % n    
    ;
    SetInt32(*h1, 79)   ; e
    SetInt32(*h2, 1019) ; d
    SetInt32(*h3, 3337) ; n
    SetInt32(*h4, 688)  ; m
    SetInt32(*h5, 0)    ; c
    DebugPrintN("Modulus Exponentiation: " + Cc2Mem::DebugMemory(*h4\num, MemorySize(*h4\num), showNum) + "^ " + Cc2Mem::DebugMemory(*h1\num, MemorySize(*h1\num), showNum) + "mod " + Cc2Mem::DebugMemory(*h3\num, MemorySize(*h3\num), showNum))
    DebugOut("Modulus Exponentiation: " + Cc2Mem::DebugMemory(*h4\num, MemorySize(*h4\num), showNum) + "^ " + Cc2Mem::DebugMemory(*h1\num, MemorySize(*h1\num), showNum) + "mod " + Cc2Mem::DebugMemory(*h3\num, MemorySize(*h3\num), showNum))
    ModPow(*h4, *h1, *h3, *h5)
    DebugPrintN("= " + Cc2Mem::DebugMemory(*h5\num, MemorySize(*h5\num), showNum))
    DebugOut("= " + Cc2Mem::DebugMemory(*h5\num, MemorySize(*h5\num), showNum))
    DebugPrintN("Modulus Exponentiation: " + Cc2Mem::DebugMemory(*h5\num, MemorySize(*h5\num), showNum) + "^ " + Cc2Mem::DebugMemory(*h2\num, MemorySize(*h2\num), showNum) + "mod " + Cc2Mem::DebugMemory(*h3\num, MemorySize(*h3\num), showNum))
    DebugOut("Modulus Exponentiation: " + Cc2Mem::DebugMemory(*h5\num, MemorySize(*h5\num), showNum) + "^ " + Cc2Mem::DebugMemory(*h2\num, MemorySize(*h2\num), showNum) + "mod " + Cc2Mem::DebugMemory(*h3\num, MemorySize(*h3\num), showNum))
    ModPow(*h5, *h2, *h3, *h4)
    DebugPrintN("= " + Cc2Mem::DebugMemory(*h4\num, MemorySize(*h4\num), showNum))
    DebugOut("= " + Cc2Mem::DebugMemory(*h4\num, MemorySize(*h4\num), showNum))
    Destroy(*h1)
    Destroy(*h2)
    Destroy(*h3)
    Destroy(*h4)
    Destroy(*h5)
    FreeMemory(*dbuffer)
    DebugPrintN("self test finished")
    DebugOut("self test finished")    
    
    Print("Press ESC To exit")
    Repeat: Delay(20): Until Inkey() = Chr(27) ; wait until ESC pressed
    CloseConsole()
  EndProcedure
  
  CompilerIf #PB_Compiler_IsMainFile
    SelfTest()
  CompilerEndIf  
  
  ;- Data section
  
  DataSection
    Huge1:
    Data.a $28, $AF, $43, $32, $A1, $37, $07
    EndofHuge1:
    Huge2:
    Data.a $04, $03, $14, $E4, $34, $C7, $7D
    EndofHuge2:
    
  EndDataSection  
  
  
EndModule

[STARGÅTE]

Can you post an example how to use your procedures?
I can't see a procedure to output my huge number.

I see some comments like: ; TODO - optimise the following:
If you want to optimize, I think you have to use ASM only.
I have wrote an include for unlimited integers too, and a addition or multiplication in asm much faster.

[ts-soft]

Code: Select all

CompilerIf #PB_Compiler_IsMainFile
  EnableExplicit
CompilerEndIf 

This doesn't work for the module! A module have a separate EnableExplicit only for the module!
Put this in the module to work.

[coco2]

My rsa.pbi module shows how to use the huge numbers, I only made this so I could make an RSA module.

Also here is some test code:

Code: Select all

XIncludeFile("huge.pbi")

Procedure.s DebugMemory(*b,length.i, type.i=0)
  Protected i.i, l.i, s.s=""
  If *b
    l.i=length-1
    Select type
      Case 0 ; hex
        For i=0 To l
          s = s + RSet(Hex(PeekA(*b+i)),2,"0")+" "
        Next i
      Case 1 ;dec
        For i=0 To l
          s = s + RSet(Str(PeekA(*b+i)),3,"0")+" "
        Next i
      Case 2 ;bin
        For i=0 To l
          s = s + RSet(Bin(PeekA(*b+i),#PB_Ascii),8,"0")+" "
        Next i          
    EndSelect 
  Else
    s="DebugMemory Error: null pointer passed"
  EndIf
  ProcedureReturn S  
EndProcedure

Define *n1.Huge::huge_type, *n2.Huge::huge_type, *n3.Huge::huge_type, *n4.Huge::huge_type

*n1 = Huge::New(1)
*n2 = Huge::New(1)
*n3 = Huge::New(1)

Huge::SetInt32(*n1, 6)
Huge::SetInt32(*n2, 2)

Debug "-------Addition---------------------------"
Debug DebugMemory(*n1\num, *n1\size, 2)
Debug "+"
Debug DebugMemory(*n2\num, *n2\size, 2)
Debug "="
If Not Huge::Add(*n1, *n2)
  Debug "Fail"
Else
  Debug DebugMemory(*n1\num, *n1\size, 2)
EndIf
Huge::SetInt32(*n1, 6)
Huge::SetInt32(*n2, 2)
Debug "-------Multiplication---------------------"
Debug DebugMemory(*n1\num, *n1\size, 2)
Debug "*"
Debug DebugMemory(*n2\num, *n2\size, 2)
Debug "="
If Not Huge::Multiply(*n1, *n2)
  Debug "Fail"
Else
  Debug DebugMemory(*n1\num, *n1\size, 2)
EndIf
Huge::SetInt32(*n1, 6)
Huge::SetInt32(*n2, 2)
Debug "-------Subtraction-(with trim)------------"
Debug DebugMemory(*n1\num, *n1\size, 2)
Debug "-"
Debug DebugMemory(*n2\num, *n2\size, 2)
Debug "="
If Not Huge::Subtract(*n1, *n2)
  Debug "Fail"
Else
  Debug DebugMemory(*n1\num, *n1\size, 2)
EndIf
Huge::SetInt32(*n1, 6)
Huge::SetInt32(*n2, 2)
Debug "-------Division-(with trim)---------------"
Debug DebugMemory(*n1\num, *n1\size, 2)
Debug "/"
Debug DebugMemory(*n2\num, *n2\size, 2)
Debug "="
If Not Huge::Divide(*n1, *n2, *n3)
  Debug "Fail"
Else
  Debug DebugMemory(*n3\num, *n3\size, 2)
EndIf

Huge::Destroy(*n1)
Huge::Destroy(*n2)
Huge::Destroy(*n3)

[coco2]

This doesn't work for the module! A module have a separate EnableExplicit only for the module!
Put this in the module to work.

I only use this while developing the module so I don't make a mistake. I disable it when called from a parent to speed up compile time. Am I doing it right?

[ts-soft]

The enableexplicit works only on his namespace, that is mainscope, not the module.
Use it inside the module and it works for module! (Only for Module)

Code: Select all

Module bla
  EnableExplicit
  
  ....
EndModule

http://www.purebasic.com/documentation/ ... odule.html

When the statements Define, EnableExplicit, EnableASM are used inside a module, they have no effect outside the respective module, and vice versa.

[blueb]

Hi Coco2.

Ran your test code above and got these results:

-------Addition---------------------------
00000000 00000000 00000000 00000110
+
00000000 00000000 00000000 00000010
=
00000000 00000000 00000000 00001000


Shouldn't I get: 00000000 00000000 00000000 00000120

[wilbert]

After seeing your module, I updated the shift buffer procedures
http://www.purebasic.fr/english/viewtop ... 20#p454120
The new ones are significantly faster.

[coco2]

Shouldn't I get: 00000000 00000000 00000000 00000120

Hi blueb, my test code displays the output in binary (because the module uses binary arithmetic), you could change the DebugMemory parameter to a 1 to show decimal:

Code: Select all

Debug "-------Addition---------------------------"
Debug DebugMemory(*n1\num, *n1\size, 1)
Debug "+"
Debug DebugMemory(*n2\num, *n2\size, 1)
Debug "="
If Not Huge::Add(*n1, *n2)
  Debug "Fail"
Else
  Debug DebugMemory(*n1\num, *n1\size, 1)
EndIf

Produces this:

-------Addition---------------------------
000 000 000 006
+
000 000 000 002
=
000 000 000 008

@Wilbert: thanks I'll take a look

[coco2]

The enableexplicit works only on his namespace, that is mainscope, not the module.
Use it inside the module and it works for module! (Only for Module)

thanks ts-soft

[pcfreak]

Why reinventing the wheel?
There are a lot of working big number implementations in the net.
For example gmp.
Here is an example using gmp with PureBasic x86
http://www.filedropper.com/gmp-431-purebasic
I have compiled the gmp library with GCC.

Feel free to use it according GNU LGPL v3.
For further information see https://gmplib.org/.

[coco2]

I like writing in pure PureBasic as it makes long term development easier and less complex

[coco2]

It's more like making the "wheel" nicer and educational because now it runs in native PB. I've added a self test now so you can run the module and see it in action. I've flattened the source code too so now you can paste it in to PB and run it as it is. Feel free to do whatever you want with it, or just keep it as a reference in your source codes.

Just had a look at GMP, seems like a good open source project. Only issue I have with it this statement:

GMP's main target platforms are Unix-type systems, such as GNU/Linux, Solaris, HP-UX, Mac OS X/Darwin, BSD, AIX, etc. It also is known to work on Windows in both 32-bit and 64-bit mode.

The whole reason I use PB is because it's not "known" to work on Windows, it's MADE to work on Windows, and Linux and Mac, thanks to hard work by the developers.