vmbigintegersclass.h

TOOL (Tiny Object Oriented Language) is an easily-embedded, object-oriented, C++-like-language inter

#ifndef VM_BIG_DIGITS_H_INCLUDED
#define VM_BIG_DIGITS_H_INCLUDED
/*****************************************************************************/
/*                              HEADER FILE                                  */
/*****************************************************************************/
/*
       $Archive:   $

      $Revision:   $
          $Date:   $
        $Author:   $

    Description:   Declaration of a CPP class wrapper over the BigDigits.
                   Library. This work was done to provide a C++ version of this
                   library and also to reduce the number of files that need to
                   be pulled into the project to gain usage of this library.
                   
                   As such, this file may not have a lot of resemblance to the
                   original files. Original authors comments are below.

                   This source code is part of the BigDigits multiple-precision
                   arithmetic library Version 1.0 originally written by David 
                   Ireland, copyright (c) 2001 D.I. Management Services Pty 
                   Limited, all rights reserved. 

                   It is provided "as is" with no warranties. You may use this
                   software under the terms of the full copyright notice 
                   "bigdigitsCopyright.txt" that should have been included with
                   this library. 

                   To obtain a copy send an email to <[e-mail]> or visit 
                   <www.di-mgt.com.au/crypto.html>.

                   This notice must be retained in any copy.

                   Text from "bigdigitsCopyright.txt" follows:

                   This source code is part of the BigDigits multiple-precision
                   arithmetic library Version 1.0 originally written by David Ireland,
                   copyright (c) 2001 D.I. Management Services Pty Limited, all rights
                   reserved. 

                   You are permitted to use compiled versions of this code as part of
                   your own executable files and to distribute unlimited copies of such
                   executable files for any purposes including commercial ones provided
                   you keep the copyright notices intact in the source code and that you
                   ensure that the following characters remain in any object or executable
                   files you distribute:

                   "Contains multiple-precision arithmetic code originally written
                   by David Ireland, copyright (c) 2001 by D.I. Management Services
                   Pty Limited <www.di-mgt.com.au>, and is used with permission."

                   David Ireland and DI Management Services Pty Limited make no
                   representations concerning either the merchantability of this
                   software or the suitability of this software for any particular
                   purpose. It is provided "as is" without express or implied warranty
                   of any kind.

                   Please forward any comments and bug reports to <[e-mail]>.
                   The latest version of the source code can be downloaded from
                   www.di-mgt.com.au/crypto.html.
*/
/*****************************************************************************/


// Define type of DIGIT here 
//
typedef unsigned long  VM_DIGIT_T;
typedef unsigned short VM_HALF_DIGIT_T;


// Sizes to suit your machine
//
#define VM_MAX_DIGIT      0xffffffff
#define VM_MAX_HALF_DIGIT 0xffff
#define VM_BITS_PER_DIGIT 32
#define VM_HIBITMASK      0x80000000


// Max number of digits expected in a mp array
//
#define VM_MAX_DIG_LEN 51

/*	This is required for temp storage only in:
	mpModulo, mpShortMod, mpModMult, mpGcd,
	mpModInv, mpIsPrime
*/

// Useful macros 
//
#define VM_LOHALF(x)      ((VM_DIGIT_T)((x) & 0xffff))
#define VM_HIHALF(x)      ((VM_DIGIT_T)((x) >> 16 & 0xffff))
#define VM_TOHIGH(x)      ((VM_DIGIT_T)((x) << 16))
#define VM_ISODD(x)       ((x) & 0x1)
#define VM_ISEVEN(x)      (!VM_ISODD(x))
#define VM_mpISODD(x, n)  (x[0] & 0x1)
#define VM_mpISEVEN(x, n) (!(x[0] & 0x1))

#define VM_mpNEXTBITMASK(mask, n) if(mask==1){mask=VM_HIBITMASK;n--;}else{mask>>=1;}


///////////////////////////////////////////////////////////////////////////////
//
// "BigDigits" with memory management - not complete yet
//
typedef struct
{
  VM_DIGIT_T*     digits;	    // Ptr to array of digits, least sig. first 
  unsigned int ndigits;	    // No of non-zero significant digits 
  unsigned int maxdigits;	 // Max size allocated 
} BIGD_T;


class VMBigIntegers
{
public:

///////////////////////////////////////////////////////////////////////////////
//
//	Multiple precision calculations Using known, equal ndigits except where noted

///////////////////////////////////////////////////////////////////////////////
//
// Computes w = u + v, returns carry 
//
static VM_DIGIT_T mpAdd( VM_DIGIT_T w[], VM_DIGIT_T u[], VM_DIGIT_T v[], unsigned int ndigits );


///////////////////////////////////////////////////////////////////////////////
//
// Computes w = u - v, returns borrow
//
static VM_DIGIT_T mpSubtract( VM_DIGIT_T w[], VM_DIGIT_T u[], VM_DIGIT_T v[], unsigned int ndigits );


///////////////////////////////////////////////////////////////////////////////
//
// Computes product w = u * v  
// u, v = ndigits long; w = 2 * ndigits long
//
static int mpMultiply(VM_DIGIT_T w[], VM_DIGIT_T u[], VM_DIGIT_T v[], unsigned int ndigits );


///////////////////////////////////////////////////////////////////////////////
//
// Computes quotient q = u / v and remainder r = u mod v 
//	q, r, u = udigits long; v = vdigits long
//	Warning: Trashes q and r first
//
static int mpDivide( VM_DIGIT_T q[], VM_DIGIT_T r[], VM_DIGIT_T u[], unsigned int udigits, 
                     VM_DIGIT_T v[], unsigned int vdigits );


///////////////////////////////////////////////////////////////////////////////
//
// Computes r = u mod v 
// u = udigits long; r, v = vdigits long
//
static int mpModulo( VM_DIGIT_T r[], VM_DIGIT_T u[], unsigned int udigits, 
                     VM_DIGIT_T v[], unsigned int vdigits );


///////////////////////////////////////////////////////////////////////////////
//
// Computes a = (x * y) mod m
//
static int mpModMult( VM_DIGIT_T a[], VM_DIGIT_T x[], VM_DIGIT_T y[], VM_DIGIT_T m[], unsigned int ndigits );


///////////////////////////////////////////////////////////////////////////////
//
// Computes y = x^n mod d
//
static int mpModExp( VM_DIGIT_T y[], VM_DIGIT_T x[], VM_DIGIT_T n[], VM_DIGIT_T d[], unsigned int ndigits );


///////////////////////////////////////////////////////////////////////////////
//
// Computes inv = u^-1 mod v
//
static int mpModInv(VM_DIGIT_T inv[], VM_DIGIT_T u[], VM_DIGIT_T v[], unsigned int ndigits );


///////////////////////////////////////////////////////////////////////////////
//
// Computes g = gcd(x, y)
//
static int mpGcd( VM_DIGIT_T g[], VM_DIGIT_T x[], VM_DIGIT_T y[], unsigned int ndigits );


///////////////////////////////////////////////////////////////////////////////
//
// Returns true if a == b, else false 
//
static int mpEqual( VM_DIGIT_T a[], VM_DIGIT_T b[], unsigned int ndigits );


///////////////////////////////////////////////////////////////////////////////
//
// Returns sign of (a - b)
//
static int mpCompare( VM_DIGIT_T a[], VM_DIGIT_T b[], unsigned int ndigits );


///////////////////////////////////////////////////////////////////////////////
//
// Returns true if a == 0, else false
//
static int mpIsZero( VM_DIGIT_T a[], unsigned int ndigits );


///////////////////////////////////////////////////////////////////////////////
//
// Bitwise operations 

///////////////////////////////////////////////////////////////////////////////
//
// Computes a = b << x, x < VM_BITS_PER_DIGIT 
//
static VM_DIGIT_T mpShiftLeft( VM_DIGIT_T a[], VM_DIGIT_T b[], unsigned int x, unsigned int ndigits );


///////////////////////////////////////////////////////////////////////////////
//
// Computes a = b >> x, x < VM_BITS_PER_DIGIT
//
static VM_DIGIT_T mpShiftRight( VM_DIGIT_T a[], VM_DIGIT_T b[], unsigned int x, unsigned int ndigits );


///////////////////////////////////////////////////////////////////////////////
//
// Other mp utilities 

///////////////////////////////////////////////////////////////////////////////
//
// Sets a = 0
//
static void mpSetZero( VM_DIGIT_T a[], unsigned int ndigits );


///////////////////////////////////////////////////////////////////////////////
//
// Sets a = d where d is a single digit
//
static void mpSetDigit( VM_DIGIT_T a[], VM_DIGIT_T d, unsigned int ndigits );


///////////////////////////////////////////////////////////////////////////////
//
// Sets a = b
//
static void mpSetEqual( VM_DIGIT_T a[], VM_DIGIT_T b[], unsigned int ndigits );


///////////////////////////////////////////////////////////////////////////////
//
// Returns size of significant non-zero digits in a
//
static unsigned int mpSizeof( VM_DIGIT_T a[], unsigned int ndigits );


///////////////////////////////////////////////////////////////////////////////