/*
 * mp.h
 *
 * This code is in the public domain. I would appreciate bug reports and
 * enhancements.
 *
 * Duncan S Wong <swong@ieee.org>
 *
 * Feb 11, 2001 - v0.2 - CRT special case of two moduli (MP_crt2)
 *                     - Primality test algorithm (MP_probab_prime)
 * Dec 14, 2000 - v0.1 - Initial Version
 */
#ifndef __MP_H__
#define __MP_H__

#include <PalmOS.h>

#define MP_DEFAULT_BITS 1280

// Only one for the following should be defined.
#undef THIRTY_TWO_BIT
#define SIXTEEN_BIT  // so far this one gives the fastest result on my Palm III, remember to add CodeWarrior Runtime (2i) library
#undef EIGHT_BIT

#ifdef THIRTY_TWO_BIT
#define DIGIT         unsigned long       // the radix is 4294967296  (32 bits)
#define DOUBLE_DIGIT  unsigned long long  // 64 bits
#define DIGIT_BITS    32
#define DIGIT_BITSl   16
#define DIGIT_BYTES   4
#define DIGIT_MASK    (0xffffffffL)
#define DIGIT_MASKl   (0xffff)
#define DIGIT_HBIT		(0x80000000L)
#define DOUBLE_DIGIT_HBIT  (0x8000000000000000)
#endif

#ifdef SIXTEEN_BIT
#define DIGIT         unsigned short     // the radix is 65536  (16 bits)
#define DOUBLE_DIGIT  unsigned long      // 32 bits
#define TETRA_DIGIT   unsigned long long // 64 bits
#define DIGIT_BITS    16
#define DIGIT_BITSl   8
#define DIGIT_BYTES   2
#define DIGIT_MASK    (0xffff)
#define DIGIT_MASKl   (0xff)
#define DIGIT_HBIT		(0x8000)
#define DOUBLE_DIGIT_MASK  (0xffffffffL)
#define DOUBLE_DIGIT_HBIT  (0x80000000L)
#endif

#ifdef EIGHT_BIT
#define DIGIT         unsigned char    // the radix is 256  (8 bits)
#define DOUBLE_DIGIT  unsigned short   // 16 bits
#define TETRA_DIGIT   unsigned long    // 32 bits
#define DIGIT_BITS    8
#define DIGIT_BITSl   4
#define DIGIT_BYTES   1
#define DIGIT_MASK    (0xff)
#define DIGIT_MASKl   (0xf)
#define DIGIT_HBIT    (0x80)
#define DOUBLE_DIGIT_MASK  (0xffff)
#define DOUBLE_DIGIT_HBIT  (0x8000)
#endif

typedef struct strutINT
{
	DIGIT *d;
	Int16 top;	// Index of last used digit + 1 (Int16 limits the max # digits that this MP library can support to 32767 digits)
	Int16 max;	// Size of the d array          (Int16 limits the max # digits that this MP library can support to 32767 digits)
	Int16 neg;	// one if the number is negative
} INT;

// Used as temp buffers
#define MP_CTX_NUM	12
typedef struct structMP_CTX
{
	Int16 tos;
	INT *t[MP_CTX_NUM+1];
} MP_CTX;

// Used for Montgomery multiplication
typedef struct structMP_MONT_CTX
{
  Int16 n;     // R = b^n where b = 2^ DIGIT_BITS, the radix
  INT *R_m;    // R mod m
  INT *R2_m;   // R^2 mod m
  INT *m;      // The modulus
  DIGIT mi;    // -m^{-1} mod b where b = 2^DIGIT_BITS
} MP_MONT_CTX;


/****************************************
 * Functions Exported to MPLib Interface
 ****************************************/
// Initialization Functions
INT *MP_new(void);
void MP_clear(INT *integer);
void MP_free(INT *integer);
void MP_clear_free(INT *integer);
MP_CTX *MP_CTX_new(void);
void MP_CTX_free(MP_CTX *c);
MP_MONT_CTX *MP_MONT_CTX_new(void );
void MP_MONT_CTX_free(MP_MONT_CTX *mont);
Int16 MP_MONT_CTX_set(MP_MONT_CTX *mont, INT *modulus, MP_CTX *ctx);

// Assignment Functions
Int16 MP_mask_bits(INT *a, Int16 n);
INT *MP_copy(INT *dest, INT *src);

// Arithmetic Functions
Int16 MP_add(INT *s, INT *a, INT *b);
void MP_qadd(INT *s, INT *a, INT *b);
Int16 MP_sub(INT *r, INT *a, INT *b);
void MP_qsub(INT *r, INT *a, INT *b);
Int16 MP_mul(INT *r, INT *a, INT *b);
DIGIT MP_mul_digit(DIGIT *rp, DIGIT *ap, Int16 num, DIGIT w);
DIGIT MP_mul_add_digit(DIGIT *rp, DIGIT *ap, Int16 num, DIGIT w);
Int16 MP_sqr(INT *r, INT *a);
Int16 MP_div(INT *q, INT *r, INT *dividend, INT *divisor, MP_CTX *ctx);

// Logical Functions
Int16 MP_lshift(INT *to, INT *from, Int16 n);
Int16 MP_lshift1(INT *r, INT *a);
Int16 MP_rshift(INT *r, INT *a, Int16 n);
Int16 MP_rshift1(INT *r, INT *a);

// Comparison Functions
Int16 MP_cmp(INT *a, INT *b);
Int16 MP_ucmp(INT *a, INT *b);
Int16 MP_is_bit_set(INT *a, Int16 n);

// Number Theoretic Functions
Int16 MP_mod_mul(INT *r, INT *a, INT *b, INT *m, MP_CTX *ctx);
Int16 MP_mont_mul(INT *r, INT *a, INT *b, MP_MONT_CTX *mont, MP_CTX *ctx);
INT *MP_mod_inverse(INT *a, INT *n, MP_CTX *ctx);
Int16 MP_mod_exp(INT *r, INT *a, INT *b, INT *m, MP_CTX *ctx);
Int16 MP_mont_exp(INT *r, INT *a, INT *e, MP_MONT_CTX *mont, MP_CTX *ctx);
Int16 MP_gcd(INT *d, INT *a, INT *b, MP_CTX *ctx);
Int16 MP_binary_gcd(INT *d, INT *a, INT *b, MP_CTX *ctx);
Int16 MP_crt2(INT *x, INT *v1, INT *v2, INT *p, INT *q, MP_CTX *ctx);
Int16 MP_probab_prime(INT *n, UInt16 reps, MP_CTX *ctx);

// Conversion Functions
INT *MP_bin2bn(UInt8 *s, UInt16 len);
UInt16 MP_bn2bin(INT *a, UInt8 *to);
INT *MP_ascii2bn(Char *str);
Char *MP_bn2ascii(INT *a);
UInt32 MP_num_bits(INT *a);
UInt16 MP_num_bits_digit(DIGIT l);


/****************
 * Macros
 ****************/
#define MP_is_zero(a)  (((a)->top <= 1) && ((a)->d[0] == (DIGIT)0))
#define MP_is_one(a)   (((a)->top == 1) && ((a)->d[0] == (DIGIT)1))
#define MP_is_odd(a)	 ((a)->d[0] & 1)
#define MP_zero(a)     { (a)->top = 0; (a)->d[0] = (DIGIT)0; }
#define MP_one(a)      { (a)->top = 1; (a)->d[0] = (DIGIT)1; }

#endif