// Ed25519 using 32-bit int 
//
// R. Perry, June 2016

/*

Represent a 256-bit value using N B-bit pieces, e.g. 22 12-bit pieces:

22*12 = 264,  21*12 = 252

x = 2^12,  u = u[21]*x^21 + u[20]*x^20 + ... + u[1]*x + u[0]

so only 4 bits are used in u[21]

Multiplying two sums for EdDSA point addition can be done without reducing
the coefficients until the end:

  sum of two 12-bit pieces is 13-bits, product of two 13-bit pieces is
  26-bits per piece, and 22 26-bit pieces have to be added in the worst case
  which is (26+5)-bits = 31-bits which fits in 32-bits.

*/

//------------------------------------------------------------------------------

#define B     12	  // number of bits per piece
#define MASK  ((1<<B)-1)  // mask to select B bits, e.g. 0...0111111111111
#define N     22	  // number of pieces
#define NN    (2*N-1)	  // number of pieces in a multiplication result

#define M     32	  // number of bytes in a 256-bit byte array
#define MM    64	  // number of bytes in a 512-bit byte array

extern int debug;	  // set in impl.c
	
// ***
// Note: some routines are dependent on specific values of B and N
// ***

typedef unsigned int UI; // assume unsigned int is 32 bits

typedef UI C[N];	 // a 256-bit value using N B-bit pieces

typedef UI D[NN];	 // product of two C's

//------------------------------------------------------------------------------

// secret key, private key, exponents, and point multipliers
// are arrays of 32 bytes (256 bits)
//
typedef unsigned char UC;

typedef UC E[M];	// a 256-bit value using M 8-bit pieces

typedef UC EE[MM];	// a 512-bit value using MM 8-bit pieces

//------------------------------------------------------------------------------

// curve point in extended homogeneous coordinates
//
typedef struct point
{
  C x, y, z, t;
}
Point;

//------------------------------------------------------------------------------

// constants, defined in impl.c

// m = 2^255 - 19

// m-1
//
extern C m1;

// m-2
// 
extern E m2;

// m58 = (m-5)/8
//
extern E m58;

// sqrtm1 = 2^((m-1)/4)
//
extern C sqrtm1;

// d
//
extern C d;

// d*2
//
extern C d2;

// curve neutral element and base point
//
extern Point Z, G;

// curve group order 
//
extern C L;

//------------------------------------------------------------------------------

// operations mod 2^255 - 19

// add: w = u+v with no reduction
//
void add( C w, C u, C v);

// neg: u = m - u
//
// *** assumes that B is 12 and N is 22, i.e. 2^255 = 2^3 * (2^12)^21 ***
//
void neg( C u);

// dec: --u
//
// *** assumes that B is 12 and N is 22 ***
//
void dec( C u);

// sub: w = u-v with no reduction
//
// *** assumes that B is 12 and N is 22 ***
//
void sub( C w, C u, C v);

// mul: r = u*v with reduction and mod
//
void mul( C r, C u, C v);

// mul2: r = 2*u*v with reduction and mod
//
void mul2( C r, C u, C v);

// sqr: r = u*u with reduction and mod
//
void sqr( C r, C u);

// sqr2: r = 2*u*u with reduction and mod
//
void sqr2( C r, C u);

// reduce a C or D value by propagating the carries
//
void reduce( UI *w, int n);

// fast_reduce: reduce a C or D value by propagating the carries
// starting at a particular offset and stoping once the carry becomes zero.
//
void fast_reduce( UI *w, int n, int offset);

// mod: u = w mod (2^255)-19
//
// *** assumes that B is 12 and N is 22 ***
//
// NOTE: u may not be fully reduced but will never exceed (2^255 - 1)
//
void mod( C u, D w);

// ltm: returns non-zero if u < m
//
// *** assumes that B is 12 and N is 22 ***
//
// assumes that reduce has already been performed
//
int ltm( C u);

// adjust: if u >= m then subtract m
//
// *** assumes that B is 12 and N is 22 ***
//
// assumes that reduce has already been performed
//
void adjust( C u);

// modPow: u = v^e mod (2^255)-19
//
void modPow( C u, C v, E e);

// modInverse: u = v^(m-2) mod m, m = 2^255 - 19
//
void modInverse( C u, C v);

//------------------------------------------------------------------------------

// curve operations

// Point_add: p3 = p1 + p2
//
void Point_add( Point *p3, Point *p1, Point *p2);

// Point_double: p3 = p1 + p1
//
void Point_double( Point *p3, Point *p1);

// Point_mul: q = e*r
//
void Point_mul( Point *q, E e, Point *r);

// encode point (x,y) values into E value
//
void Point_encode( E e, Point *p, int test_decode);

// decode E value into Point
//
int Point_decode( Point *p, E e);

//------------------------------------------------------------------------------

// operations mod L, the curve group order

// mod_L: e = u mod (2^252 + 27742317777372353535851937790883648493)
//
// *** assumes that B is 12 and N is 22 ***
//
// NOTE: this routine overwrites u
//
void mod_L( E e, D u);

// sign: s = (r + k*a) mod L
//
void sign( E s, E r, E k, E a);

// verify: s*G ?= R + k*A
//
int verify( E s, Point *G, Point *R, E k, Point *A);

//------------------------------------------------------------------------------

// I/O and conversion routines

// print a C or D value, MSB first,  *** assumes that B is 12 ***
//
void print( const char *msg, UI *u, int n);

// print a Point, MSB first,  *** assumes that B is 12 ***
//
void print_P( const char *msg, Point *p);

// print an E value, LSB first
//
void print_E( const char *msg, UC *e, int n);

// convert one hex digit character to an int
//
UI hex2int( int h);

// convert hex string (big-endian) to C value
//
void convert( C u, const char *s);

// convert hex string (big-endian) to D value
//
void convert_D( D w, const char *s);

// convert hex string (little-endian) to E value
//
void convert_E( E e, const char *s);

// CtoE: e = c, convert C value to E value *** assumes that B is 12 ***
//
void CtoE( E e, C c);

// EtoC: c = e, convert E value to C value *** assumes that B is 12 ***
//
void EtoC( C c, E e);

// EEtoD: w = e, convert EE value to D value *** assumes that B is 12 ***
//
void EEtoD( D w, EE e);