include/big.h.in

/*
	Licensed to the Apache Software Foundation (ASF) under one
	or more contributor license agreements.  See the NOTICE file
	distributed with this work for additional information
	regarding copyright ownership.  The ASF licenses this file
	to you under the Apache License, Version 2.0 (the
	"License"); you may not use this file except in compliance
	with the License.  You may obtain a copy of the License at

	http://www.apache.org/licenses/LICENSE-2.0

	Unless required by applicable law or agreed to in writing,
	software distributed under the License is distributed on an
	"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
	KIND, either express or implied.  See the License for the
	specific language governing permissions and limitations
	under the License.
*/

/**
 * @file big_XXX.h
 * @author Mike Scott
 * @brief BIG Header File
 *
 */

#ifndef BIG_XXX_H
#define BIG_XXX_H

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include "arch.h"
#include "amcl.h"
#include "config_big_XXX.h"

//#define UNWOUND

#define BIGBITS_XXX (8*MODBYTES_XXX) /**< Length in bits */
#define NLEN_XXX (1+((8*MODBYTES_XXX-1)/BASEBITS_XXX)) /**< length in bytes */
#define DNLEN_XXX 2*NLEN_XXX /**< Double length in bytes */
#define BMASK_XXX (((chunk)1<<BASEBITS_XXX)-1) /**< Mask = 2^BASEBITS-1 */
#define NEXCESS_XXX (1<<(CHUNK-BASEBITS_XXX-1))           /**< 2^(CHUNK-BASEBITS-1) - digit cannot be multiplied by more than this before normalisation */

#define HBITS_XXX (BASEBITS_XXX/2)      /**< Number of bits in number base divided by 2 */
#define HMASK_XXX (((chunk)1<<HBITS_XXX)-1)    /**< Mask = 2^HBITS-1 */

//#define DEBUG_NORM

#ifdef DEBUG_NORM  /* Add an extra location to track chunk extension */
#define MPV_XXX NLEN_XXX
#define MNV_XXX (NLEN_XXX+1)
typedef chunk BIG_XXX[NLEN_XXX+2];   /**< Define type BIG as array of chunks */
#define DMPV_XXX DNLEN_XXX
#define DMNV_XXX (DNLEN_XXX+1)
typedef chunk DBIG_XXX[DNLEN_XXX+2]; /**< Define type DBIG as array of chunks */
#else
typedef chunk BIG_XXX[NLEN_XXX];     /**< Define type BIG as array of chunks */
typedef chunk DBIG_XXX[DNLEN_XXX];   /**< Define type DBIG as array of chunks */
#endif

/* BIG number prototypes */

/**	@brief Tests for BIG equal to zero - input must be normalised
 *
	@param x a BIG number
	@return 1 if zero, else returns 0
 */
extern int BIG_XXX_iszilch(const BIG_XXX x);
/**	@brief Tests for BIG equal to one - input must be normalised
 *
	@param x a BIG number
	@return 1 if one, else returns 0
 */
extern int BIG_XXX_isunity(const BIG_XXX x);
/**	@brief Tests for DBIG equal to zero - input must be normalised
 *
	@param x a DBIG number
	@return 1 if zero, else returns 0
 */
extern int BIG_XXX_diszilch(const DBIG_XXX x);
/**	@brief Outputs a BIG number to the console
 *
	@param x a BIG number
 */
extern void BIG_XXX_output(const BIG_XXX x);
/**	@brief Outputs a BIG number to the console in raw form (for debugging)
 *
	@param x a BIG number
 */
extern void BIG_XXX_rawoutput(const BIG_XXX x);
/**	@brief Conditional constant time swap of two BIG numbers
 *
	Conditionally swaps parameters in constant time (without branching)
	@param x a BIG number
	@param y another BIG number
	@param s swap takes place if not equal to 0
 */
extern void BIG_XXX_cswap(BIG_XXX x,BIG_XXX y,int s);
/**	@brief Conditional copy of BIG number
 *
	Conditionally copies second parameter to the first (without branching)
	@param x a BIG number
	@param y another BIG number
	@param s copy takes place if not equal to 0
 */
extern void BIG_XXX_cmove(BIG_XXX x,const BIG_XXX y,int s);
/**	@brief Conditional copy of DBIG number
 *
	Conditionally copies second parameter to the first (without branching)
	@param x a DBIG number
	@param y another DBIG number
	@param s copy takes place if not equal to 0
 */
extern void BIG_XXX_dcmove(DBIG_XXX x,const DBIG_XXX y,int s);
/**	@brief Convert from BIG number to byte array
 *
	@param a byte array
	@param x BIG number
 */
extern void BIG_XXX_toBytes(char *a,const BIG_XXX x);
/**	@brief Convert to BIG number from byte array
 *
	@param x BIG number
	@param a byte array
 */
extern void BIG_XXX_fromBytes(BIG_XXX x,const char *a);
/**	@brief Convert to BIG number from byte array of given length
 *
	@param x BIG number
	@param a byte array
	@param s byte array length
 */
extern void BIG_XXX_fromBytesLen(BIG_XXX x,const char *a,int s);
/**@brief Convert to DBIG number from byte array of given length
 *
   @param x DBIG number
   @param a byte array
   @param s byte array length
 */
extern void BIG_XXX_dfromBytesLen(DBIG_XXX x,const char *a,int s);
/**	@brief Outputs a DBIG number to the console
 *
	@param x a DBIG number
 */
extern void BIG_XXX_doutput(DBIG_XXX x);

/**	@brief Outputs a DBIG number to the console
 *
	@param x a DBIG number
 */
extern void BIG_XXX_drawoutput(const DBIG_XXX x);

/**	@brief Copy BIG from Read-Only Memory to a BIG
 *
	@param x BIG number
	@param y BIG number in ROM
 */
extern void BIG_XXX_rcopy(BIG_XXX x,const BIG_XXX y);
/**	@brief Copy BIG to another BIG
 *
	@param x BIG number
	@param y BIG number to be copied
 */
extern void BIG_XXX_copy(BIG_XXX x,const BIG_XXX y);
/**	@brief Copy DBIG to another DBIG
 *
	@param x DBIG number
	@param y DBIG number to be copied
 */
extern void BIG_XXX_dcopy(DBIG_XXX x,const DBIG_XXX y);
/**	@brief Copy BIG to upper half of DBIG
 *
	@param x DBIG number
	@param y BIG number to be copied
 */
extern void BIG_XXX_dsucopy(DBIG_XXX x,const BIG_XXX y);
/**	@brief Copy BIG to lower half of DBIG
 *
	@param x DBIG number
	@param y BIG number to be copied
 */
extern void BIG_XXX_dscopy(DBIG_XXX x,const BIG_XXX y);
/**	@brief Copy lower half of DBIG to a BIG
 *
	@param x BIG number
	@param y DBIG number to be copied
 */
extern void BIG_XXX_sdcopy(BIG_XXX x,const DBIG_XXX y);
/**	@brief Copy upper half of DBIG to a BIG
 *
	@param x BIG number
	@param y DBIG number to be copied
 */
extern void BIG_XXX_sducopy(BIG_XXX x,const DBIG_XXX y);
/**	@brief Set BIG to zero
 *
	@param x BIG number to be set to zero
 */
extern void BIG_XXX_zero(BIG_XXX x);
/**	@brief Set DBIG to zero
 *
	@param x DBIG number to be set to zero
 */
extern void BIG_XXX_dzero(DBIG_XXX x);
/**	@brief Set BIG to one (unity)
 *
	@param x BIG number to be set to one.
 */
extern void BIG_XXX_one(BIG_XXX x);
/**	@brief Set BIG to inverse mod 2^256
 *
	@param x BIG number to be inverted
 */
extern void BIG_XXX_invmod2m(BIG_XXX x);
/**	@brief Set BIG to sum of two BIGs - output not normalised
 *
	@param x BIG number, sum of other two
	@param y BIG number
	@param z BIG number
 */
extern void BIG_XXX_add(BIG_XXX x,const BIG_XXX y,const BIG_XXX z);

/**	@brief Set BIG to logical or of two BIGs - output normalised
 *
	@param x BIG number, or of other two
	@param y BIG number
	@param z BIG number
 */
extern void BIG_XXX_or(BIG_XXX x,BIG_XXX y,BIG_XXX z);

/**	@brief Increment BIG by a small integer - output not normalised
 *
	@param x BIG number to be incremented
	@param i integer
 */
extern void BIG_XXX_inc(BIG_XXX x,int i);
/**	@brief Set BIG to difference of two BIGs
 *
	@param x BIG number, difference of other two - output not normalised
	@param y BIG number
	@param z BIG number
 */
extern void BIG_XXX_sub(BIG_XXX x,const BIG_XXX y,const BIG_XXX z);
/**	@brief Decrement BIG by a small integer - output not normalised
 *
	@param x BIG number to be decremented
	@param i integer
 */
extern void BIG_XXX_dec(BIG_XXX x,int i);
/**	@brief Set DBIG to sum of two DBIGs
 *
	@param x DBIG number, sum of other two - output not normalised
	@param y DBIG number
	@param z DBIG number
 */
extern void BIG_XXX_dadd(DBIG_XXX x,const DBIG_XXX y,const DBIG_XXX z);
/**	@brief Set DBIG to difference of two DBIGs
 *
	@param x DBIG number, difference of other two - output not normalised
	@param y DBIG number
	@param z DBIG number
 */
extern void BIG_XXX_dsub(DBIG_XXX x,const DBIG_XXX y,const DBIG_XXX z);
/**	@brief Multiply BIG by a small integer - output not normalised
 *
	@param x BIG number, product of other two
	@param y BIG number
	@param i small integer
 */
extern void BIG_XXX_imul(BIG_XXX x,const BIG_XXX y,int i);
/**	@brief Multiply BIG by not-so-small small integer - output normalised
 *
	@param x BIG number, product of other two
	@param y BIG number
	@param i small integer
	@return Overflowing bits
 */
extern chunk BIG_XXX_pmul(BIG_XXX x,const BIG_XXX y,int i);
/**	@brief Divide BIG by 3 - output normalised
 *
	@param x BIG number
	@return Remainder
 */
extern int BIG_XXX_div3(BIG_XXX x);
/**	@brief Multiply BIG by even bigger small integer resulting in a DBIG - output normalised
 *
	@param x DBIG number, product of other two
	@param y BIG number
	@param i small integer
 */
extern void BIG_XXX_pxmul(DBIG_XXX x,const BIG_XXX y,int i);
/**	@brief Multiply BIG by another BIG resulting in DBIG - inputs normalised and output normalised
 *
	@param x DBIG number, product of other two
	@param y BIG number
	@param z BIG number
 */
extern void BIG_XXX_mul(DBIG_XXX x,const BIG_XXX y,const BIG_XXX z);
/**	@brief Multiply BIG by another BIG resulting in another BIG - inputs normalised and output normalised
 *
	Note that the product must fit into a BIG, and x must be distinct from y and z
	@param x BIG number, product of other two
	@param y BIG number
	@param z BIG number
 */
extern void BIG_XXX_smul(BIG_XXX x,const BIG_XXX y,const BIG_XXX z);
/**	@brief Square BIG resulting in a DBIG - input normalised and output normalised
 *
	@param x DBIG number, square of a BIG
	@param y BIG number to be squared
 */
extern void BIG_XXX_sqr(DBIG_XXX x,const BIG_XXX y);

/**	@brief Montgomery reduction of a DBIG to a BIG  - input normalised and output normalised
 *
	@param a BIG number, reduction of a BIG
	@param md BIG number, the modulus
	@param MC the Montgomery Constant
	@param d DBIG number to be reduced
 */
extern void BIG_XXX_monty(BIG_XXX a,const BIG_XXX md,chunk MC,const DBIG_XXX d);

/**	@brief Shifts a BIG left by any number of bits - input must be normalised, output normalised
 *
	@param x BIG number to be shifted
	@param s Number of bits to shift
 */
extern void BIG_XXX_shl(BIG_XXX x,int s);
/**	@brief Fast shifts a BIG left by a small number of bits - input must be normalised, output will be normalised
 *
	The number of bits to be shifted must be less than BASEBITS
	@param x BIG number to be shifted
	@param s Number of bits to shift
	@return Overflow bits
 */
extern int BIG_XXX_fshl(BIG_XXX x,int s);
/**	@brief Shifts a DBIG left by any number of bits - input must be normalised, output normalised
 *
	@param x DBIG number to be shifted
	@param s Number of bits to shift
 */
extern void BIG_XXX_dshl(DBIG_XXX x,int s);
/**	@brief Shifts a BIG right by any number of bits - input must be normalised, output normalised
 *
	@param x BIG number to be shifted
	@param s Number of bits to shift
 */
extern void BIG_XXX_shr(BIG_XXX x,int s);

/**	@brief Fast time-critical combined shift by 1 bit, subtract and normalise
 *
	@param r BIG number normalised output
	@param a BIG number to be subtracted from
	@param m BIG number to be shifted and subtracted
	@return sign of r
 */
extern int BIG_XXX_ssn(BIG_XXX r,const BIG_XXX a, BIG_XXX m);

/**	@brief Fast shifts a BIG right by a small number of bits - input must be normalised, output will be normalised
 *
	The number of bits to be shifted must be less than BASEBITS
	@param x BIG number to be shifted
	@param s Number of bits to shift
	@return Shifted out bits
 */
extern int BIG_XXX_fshr(BIG_XXX x,int s);
/**	@brief Shifts a DBIG right by any number of bits - input must be normalised, output normalised
 *
	@param x DBIG number to be shifted
	@param s Number of bits to shift
 */
extern void BIG_XXX_dshr(DBIG_XXX x,int s);
/**	@brief Splits a DBIG into two BIGs - input must be normalised, outputs normalised
 *
	Internal function. The value of s must be approximately in the middle of the DBIG.
	Typically used to extract z mod 2^MODBITS and z/2^MODBITS
	@param x BIG number, top half of z
	@param y BIG number, bottom half of z
	@param z DBIG number to be split in two.
	@param s Bit position at which to split
	@return carry-out from top half
 */
extern chunk BIG_XXX_split(BIG_XXX x,BIG_XXX y,const DBIG_XXX z,int s);
/**	@brief Normalizes a BIG number - output normalised
 *
	All digits of the input BIG are reduced mod 2^BASEBITS
	@param x BIG number to be normalised
 */
extern chunk BIG_XXX_norm(BIG_XXX x);
/**	@brief Normalizes a DBIG number - output normalised
 *
	All digits of the input DBIG are reduced mod 2^BASEBITS
	@param x DBIG number to be normalised
 */
extern void BIG_XXX_dnorm(DBIG_XXX x);
/**	@brief Compares two BIG numbers. Inputs must be normalised externally
 *
	@param x first BIG number to be compared
	@param y second BIG number to be compared
	@return -1 is x<y, 0 if x=y, 1 if x>y
 */
extern int BIG_XXX_comp(const BIG_XXX x,const BIG_XXX y);
/**	@brief Compares two DBIG numbers. Inputs must be normalised externally
 *
	@param x first DBIG number to be compared
	@param y second DBIG number to be compared
	@return -1 is x<y, 0 if x=y, 1 if x>y
 */
extern int BIG_XXX_dcomp(const DBIG_XXX x,const DBIG_XXX y);
/**	@brief Calculate number of bits in a BIG - output normalised - leaks log2(x)
 *
	@param x BIG number
	@return Number of bits in x
 */
extern int BIG_XXX_nbits(const BIG_XXX x);
/**	@brief Calculate number of bits in a DBIG - output normalised - leaks log2(x)
 *
	@param x DBIG number
	@return Number of bits in x
 */
extern int BIG_XXX_dnbits(const DBIG_XXX x);
/**	@brief Reduce x mod n - input and output normalised - leaks log2(x)-log2(n)
 *
	Slow but rarely used
	@param x BIG number to be reduced mod n
	@param n The modulus
 */
extern void BIG_XXX_mod(BIG_XXX x,const BIG_XXX n);
/**	@brief Divide x by n - output normalised - leaks log2(x)-log2(n)
 *
	Slow but rarely used
	@param x BIG number to be divided by n
	@param n The Divisor
 */
extern void BIG_XXX_sdiv(BIG_XXX x,const BIG_XXX n);
/**	@brief  x=y mod n - output normalised - leaks log2(y)-log2(n)
 *
	Slow but rarely used. y is destroyed.
	@param x BIG number, on exit = y mod n
	@param y DBIG number
	@param n Modulus
 */
extern void BIG_XXX_dmod(BIG_XXX x,DBIG_XXX y,const BIG_XXX n);
/**	@brief  x=y/n - output normalised - leaks log2(y)-log2(n)
 *
	Slow but rarely used. y is destroyed.
	@param x BIG number, on exit = y/n
	@param y DBIG number
	@param n Modulus
 */
extern void BIG_XXX_ddiv(BIG_XXX x,DBIG_XXX y,const BIG_XXX n);
/**	@brief  return parity of BIG, that is the least significant bit
 *
	@param x BIG number
	@return 0 or 1
 */
extern int BIG_XXX_parity(const BIG_XXX x);
/**	@brief  return i-th of BIG
 *
	@param x BIG number
	@param i the bit of x to be returned
	@return 0 or 1
 */
extern int BIG_XXX_bit(const BIG_XXX x,int i);
/**	@brief  return i-th of BIG
 *
	@param x BIG number
	@param i the first bit of x to be returned
	@param w the width of the window to return
	@return bits in the window as an integer
 */
int BIG_XXX_bits(const BIG_XXX x, int i, int w);
/**	@brief  return least significant bits of a BIG
 *
	@param x BIG number
	@param n number of bits to return. Assumed to be less than BASEBITS.
	@return least significant n bits as an integer
 */
extern int BIG_XXX_lastbits(BIG_XXX x,int n);
/**	@brief  Create a random BIG from a random number generator
 *
	Assumes that the random number generator has been suitably initialised
	@param x BIG number, on exit a random number
	@param r A pointer to a Cryptographically Secure Random Number Generator
 */
extern void BIG_XXX_random(BIG_XXX x,csprng *r);
/**	@brief  Create an unbiased random BIG from a random number generator, reduced with respect to a modulus - leaks log2(n)
 *
	Assumes that the random number generator has been suitably initialised
	@param x BIG number, on exit a random number
	@param n The modulus
	@param r A pointer to a Cryptographically Secure Random Number Generator
 */
extern void BIG_XXX_randomnum(BIG_XXX x,const BIG_XXX n,csprng *r);
/**	brief  return NAF (Non-Adjacent-Form) value as +/- 1, 3 or 5, inputs must be normalised
 *
	Given x and 3*x extracts NAF value from given bit position, and returns number of bits processed, and number of trailing zeros detected if any
	param x BIG number
	param x3 BIG number, three times x
	param i bit position
	param nbs pointer to integer returning number of bits processed
	param nzs pointer to integer returning number of trailing 0s
	return + or - 1, 3 or 5
*/

/**	@brief  Calculate x=y*z mod n - leaks log2(x)-log2(n)
 *
	Slow method for modular multiplication
	@param x BIG number, on exit = y*z mod n
	@param y BIG number
	@param z BIG number
	@param n The BIG Modulus
 */
extern void BIG_XXX_modmul(BIG_XXX x,const BIG_XXX y,const BIG_XXX z,const BIG_XXX n);
/**	@brief  Calculate x=y/z mod n - leaks log2(x)-log2(n)
 *
	Slow method for modular division
	@param x BIG number, on exit = y/z mod n
	@param y BIG number
	@param z BIG number
	@param n The BIG Modulus
 */
extern void BIG_XXX_moddiv(BIG_XXX x,const BIG_XXX y,const BIG_XXX z,const BIG_XXX n);
/**	@brief  Calculate x=y^2 mod n - leaks log2(x)-log2(n)
 *
	Slow method for modular squaring
	@param x BIG number, on exit = y^2 mod n
	@param y BIG number
	@param n The BIG Modulus
 */
extern void BIG_XXX_modsqr(BIG_XXX x,const BIG_XXX y,const BIG_XXX n);
/**	@brief  Calculate x=-y mod n - leaks log2(x)-log2(n)
 *
	Modular negation
	@param x BIG number, on exit = -y mod n
	@param y BIG number
	@param n The BIG Modulus
 */
extern void BIG_XXX_modneg(BIG_XXX x,const BIG_XXX y,const BIG_XXX n);
/**	@brief  Calculate jacobi Symbol (x/y) - not constant time
 *
	@param x BIG number
	@param y BIG number
	@return Jacobi symbol, -1,0 or 1
 */
extern int BIG_XXX_jacobi(BIG_XXX x,const BIG_XXX y);
/**	@brief  Calculate x=1/y mod n
 *
	Modular Inversion - This is slow. Uses binary method.
	@param x BIG number, on exit = 1/y mod n
	@param y BIG number
	@param n The BIG Modulus
 */
extern void BIG_XXX_invmodp(BIG_XXX x,const BIG_XXX y,const BIG_XXX n);
/** @brief Calculate x=x mod 2^m
 *
	Truncation
	@param x BIG number, on reduced mod 2^m
	@param m new truncated size
*/
extern void BIG_XXX_mod2m(BIG_XXX x,int m);

/** @brief Calculate x=x mod 2^m
 *
	Truncation
	@param x DBIG number, on reduced mod 2^m
	@param m new truncated size
*/
extern void BIG_XXX_dmod2m(DBIG_XXX x,int m);

/**	@brief Calculates a*b+c+*d
 *
	Calculate partial product of a.b, add in carry c, and add total to d
	@param x multiplier
	@param y multiplicand
	@param c carry
	@param r pointer to accumulated bottom half of result
	@return top half of result
 */

#ifdef dchunk

/* Method required to calculate x*y+c+r, bottom half in r, top half returned */
static inline chunk muladd_XXX(chunk x,chunk y,chunk c,chunk *r)
{
    dchunk prod=(dchunk)x*y+c+*r;
    *r=(chunk)prod&BMASK_XXX;
    return (chunk)(prod>>BASEBITS_XXX);
}

#else

/* No integer type available that can store double the wordlength */
/* accumulate partial products */

static inline chunk muladd_XXX(chunk x,chunk y,chunk c,chunk *r)
{
    chunk x0;
    chunk x1;
    chunk y0;
    chunk y1;
    chunk bot;
    chunk top;
    chunk mid;
    chunk carry;
    x0=x&HMASK_XXX;
    x1=(x>>HBITS_XXX);
    y0=y&HMASK_XXX;
    y1=(y>>HBITS_XXX);
    bot=x0*y0;
    top=x1*y1;
    mid=x0*y1+x1*y0;
    x0=mid&HMASK_XXX;
    x1=(mid>>HBITS_XXX);
    bot+=x0<<HBITS_XXX;
    bot+=*r;
    bot+=c;

    top+=x1;
    carry=bot>>BASEBITS_XXX;
    bot&=BMASK_XXX;
    top+=carry;

    *r=bot;
    return top;
}

#endif


#endif