/*

* Copyright (c) 2003-2009 Nokia Corporation and/or its subsidiary(-ies).

* All rights reserved.

* This component and the accompanying materials are made available

* under the terms of the License "Eclipse Public License v1.0"

* which accompanies this distribution, and is available

* at the URL "http://www.eclipse.org/legal/epl-v10.html".

*

* Initial Contributors:

* Nokia Corporation - initial contribution.

*

* Contributors:

*

* Description: 

*

*/

#include "words.h"

#include "algorithms.h"

word Add(word *C, const word *A, const word *B, unsigned int N)

{

	assert (N%2 == 0);

	word carry = 0;

	for (unsigned int i = 0; i < N; i+=2)

	{

		dword u = (dword) carry + A[i] + B[i];

		C[i] = LOW_WORD(u);

		u = (dword) HIGH_WORD(u) + A[i+1] + B[i+1];

		C[i+1] = LOW_WORD(u);

		carry = HIGH_WORD(u);

	}

	return carry;

}

word Subtract(word *C, const word *A, const word *B, unsigned int N)

{

	assert (N%2 == 0);

	word borrow=0;

	for (unsigned i = 0; i < N; i+=2)

	{

		dword u = (dword) A[i] - B[i] - borrow;

		C[i] = LOW_WORD(u);

		u = (dword) A[i+1] - B[i+1] - (word)(0-HIGH_WORD(u));

		C[i+1] = LOW_WORD(u);

		borrow = 0-HIGH_WORD(u);

	}

	return borrow;

}

int Compare(const word *A, const word *B, unsigned int N)

{

	while (N--)

		if (A[N] > B[N])

			return 1;

		else if (A[N] < B[N])

			return -1;

	return 0;

}

// It is the job of the calling code to ensure that this won't carry.

// If you aren't sure, use the next version that will tell you if you need to

// grow your integer.

// Having two of these creates ever so slightly more code but avoids having

// ifdefs all over the rest of the code checking the following type stuff which

// causes warnings in certain compilers about unused parameters in release

// builds.  We can't have that can we!

/*

Allows avoid this all over bigint.cpp and primes.cpp

ifdef _DEBUG

	TUint carry = Increment(Ptr(), Size());

	assert(!carry);

else

	Increment(Ptr(), Size())

endif

*/

void IncrementNoCarry(word *A, unsigned int N, word B)

{

	assert(N);

	word t = A[0];

	A[0] = t+B;

	if (A[0] >= t)

		return;

	for (unsigned i=1; i<N; i++)

		if (++A[i])

			return;

	assert(0);

}

word Increment(word *A, unsigned int N, word B)

{

	assert(N);

	word t = A[0];

	A[0] = t+B;

	if (A[0] >= t)

		return 0;

	for (unsigned i=1; i<N; i++)

		if (++A[i])

			return 0;

	return 1;

}

//See commments above about IncrementNoCarry

void DecrementNoCarry(word *A, unsigned int N, word B)

{

	assert(N);

	word t = A[0];

	A[0] = t-B;

	if (A[0] <= t)

		return;

	for (unsigned i=1; i<N; i++)

		if (A[i]--)

			return;

	assert(0);

}

word Decrement(word *A, unsigned int N, word B)

{

	assert(N);

	word t = A[0];

	A[0] = t-B;

	if (A[0] <= t)

		return 0;

	for (unsigned i=1; i<N; i++)

		if (A[i]--)

			return 0;

	return 1;

}

void TwosComplement(word *A, unsigned int N)

{

	Decrement(A, N);

	for (unsigned i=0; i<N; i++)

		A[i] = ~A[i];

}

static word LinearMultiply(word *C, const word *A, word B, unsigned int N)

{

	word carry=0;

	for(unsigned i=0; i<N; i++)

	{

		dword p = (dword)A[i] * B + carry;

		C[i] = LOW_WORD(p);

		carry = HIGH_WORD(p);

	}

	return carry;

}

static void AtomicMultiply(word *C, const word *A, const word *B)

{

/*

	word s;

	dword d;

	if (A1 >= A0)

		if (B0 >= B1)

		{

			s = 0;

			d = (dword)(A1-A0)*(B0-B1);

		}

		else

		{

			s = (A1-A0);

			d = (dword)s*(word)(B0-B1);

		}

	else

		if (B0 > B1)

		{

			s = (B0-B1);

			d = (word)(A1-A0)*(dword)s;

		}

		else

		{

			s = 0;

			d = (dword)(A0-A1)*(B1-B0);

		}

*/

	// this segment is the branchless equivalent of above

	word D[4] = {A[1]-A[0], A[0]-A[1], B[0]-B[1], B[1]-B[0]};

	unsigned int ai = A[1] < A[0];

	unsigned int bi = B[0] < B[1];

	unsigned int di = ai & bi;

	dword d = (dword)D[di]*D[di+2];

	D[1] = D[3] = 0;

	unsigned int si = ai + !bi;

	word s = D[si];

	dword A0B0 = (dword)A[0]*B[0];

	C[0] = LOW_WORD(A0B0);

	dword A1B1 = (dword)A[1]*B[1];

	dword t = (dword) HIGH_WORD(A0B0) + LOW_WORD(A0B0) + LOW_WORD(d) + LOW_WORD(A1B1);

	C[1] = LOW_WORD(t);

	t = A1B1 + HIGH_WORD(t) + HIGH_WORD(A0B0) + HIGH_WORD(d) + HIGH_WORD(A1B1) - s;

	C[2] = LOW_WORD(t);

	C[3] = HIGH_WORD(t);

}

static word AtomicMultiplyAdd(word *C, const word *A, const word *B)

{

	word D[4] = {A[1]-A[0], A[0]-A[1], B[0]-B[1], B[1]-B[0]};

	unsigned int ai = A[1] < A[0];

	unsigned int bi = B[0] < B[1];

	unsigned int di = ai & bi;

	dword d = (dword)D[di]*D[di+2];

	D[1] = D[3] = 0;

	unsigned int si = ai + !bi;

	word s = D[si];

	dword A0B0 = (dword)A[0]*B[0];

	dword t = A0B0 + C[0];

	C[0] = LOW_WORD(t);

	dword A1B1 = (dword)A[1]*B[1];

	t = (dword) HIGH_WORD(t) + LOW_WORD(A0B0) + LOW_WORD(d) + LOW_WORD(A1B1) + C[1];

	C[1] = LOW_WORD(t);

	t = (dword) HIGH_WORD(t) + LOW_WORD(A1B1) + HIGH_WORD(A0B0) + HIGH_WORD(d) + HIGH_WORD(A1B1) - s + C[2];

	C[2] = LOW_WORD(t);

	t = (dword) HIGH_WORD(t) + HIGH_WORD(A1B1) + C[3];

	C[3] = LOW_WORD(t);

	return HIGH_WORD(t);

}

static inline void AtomicMultiplyBottom(word *C, const word *A, const word *B)

{

	dword t = (dword)A[0]*B[0];

	C[0] = LOW_WORD(t);

	C[1] = HIGH_WORD(t) + A[0]*B[1] + A[1]*B[0];

}

#define MulAcc(x, y)								\

	p = (dword)A[x] * B[y] + c; 					\

	c = LOW_WORD(p);								\

	p = (dword)d + HIGH_WORD(p);					\

	d = LOW_WORD(p);								\

	e += HIGH_WORD(p);

#define SaveMulAcc(s, x, y) 						\

	R[s] = c;										\

	p = (dword)A[x] * B[y] + d; 					\

	c = LOW_WORD(p);								\

	p = (dword)e + HIGH_WORD(p);					\

	d = LOW_WORD(p);								\

	e = HIGH_WORD(p);

#define MulAcc1(x, y)								\

	p = (dword)A[x] * A[y] + c; 					\

	c = LOW_WORD(p);								\

	p = (dword)d + HIGH_WORD(p);					\

	d = LOW_WORD(p);								\

	e += HIGH_WORD(p);

#define SaveMulAcc1(s, x, y) 						\

	R[s] = c;										\

	p = (dword)A[x] * A[y] + d; 					\

	c = LOW_WORD(p);								\

	p = (dword)e + HIGH_WORD(p);					\

	d = LOW_WORD(p);								\

	e = HIGH_WORD(p);

#define SquAcc(x, y)								\

	p = (dword)A[x] * A[y];	\

	p = p + p + c; 					\

	c = LOW_WORD(p);								\

	p = (dword)d + HIGH_WORD(p);					\

	d = LOW_WORD(p);								\

	e += HIGH_WORD(p);

#define SaveSquAcc(s, x, y) 						\

	R[s] = c;										\

	p = (dword)A[x] * A[y];	\

	p = p + p + d; 					\

	c = LOW_WORD(p);								\

	p = (dword)e + HIGH_WORD(p);					\

	d = LOW_WORD(p);								\

	e = HIGH_WORD(p);

// VC60 workaround: MSVC 6.0 has an optimization problem that makes

// (dword)A*B where either A or B has been cast to a dword before

// very expensive. Revisit a CombaSquare4() function when this

// problem is fixed.               

// WARNING: KeithR.  05/08/03 This routine doesn't work with gcc on hardware

// either.  I've completely removed it.  It may be worth looking into sometime

// in the future.

/*#ifndef __WINS__

static void CombaSquare4(word *R, const word *A)

{

	dword p;

	word c, d, e;

	p = (dword)A[0] * A[0];

	R[0] = LOW_WORD(p);

	c = HIGH_WORD(p);

	d = e = 0;

	SquAcc(0, 1);

	SaveSquAcc(1, 2, 0);

	MulAcc1(1, 1);

	SaveSquAcc(2, 0, 3);

	SquAcc(1, 2);

	SaveSquAcc(3, 3, 1);

	MulAcc1(2, 2);

	SaveSquAcc(4, 2, 3);

	R[5] = c;

	p = (dword)A[3] * A[3] + d;

	R[6] = LOW_WORD(p);

	R[7] = e + HIGH_WORD(p);

}

#endif */

static void CombaMultiply4(word *R, const word *A, const word *B)

{

	dword p;

	word c, d, e;

	p = (dword)A[0] * B[0];

	R[0] = LOW_WORD(p);

	c = HIGH_WORD(p);

	d = e = 0;

	MulAcc(0, 1);

	MulAcc(1, 0);

	SaveMulAcc(1, 2, 0);

	MulAcc(1, 1);

	MulAcc(0, 2);

	SaveMulAcc(2, 0, 3);

	MulAcc(1, 2);

	MulAcc(2, 1);

	MulAcc(3, 0);

	SaveMulAcc(3, 3, 1);

	MulAcc(2, 2);

	MulAcc(1, 3);

	SaveMulAcc(4, 2, 3);

	MulAcc(3, 2);

	R[5] = c;

	p = (dword)A[3] * B[3] + d;

	R[6] = LOW_WORD(p);

	R[7] = e + HIGH_WORD(p);

}

static void CombaMultiply8(word *R, const word *A, const word *B)

{

	dword p;

	word c, d, e;

	p = (dword)A[0] * B[0];

	R[0] = LOW_WORD(p);

	c = HIGH_WORD(p);

	d = e = 0;

	MulAcc(0, 1);

	MulAcc(1, 0);

	SaveMulAcc(1, 2, 0);

	MulAcc(1, 1);

	MulAcc(0, 2);

	SaveMulAcc(2, 0, 3);

	MulAcc(1, 2);

	MulAcc(2, 1);

	MulAcc(3, 0);

	SaveMulAcc(3, 0, 4);

	MulAcc(1, 3);

	MulAcc(2, 2);

	MulAcc(3, 1);

	MulAcc(4, 0);

	SaveMulAcc(4, 0, 5);

	MulAcc(1, 4);

	MulAcc(2, 3);

	MulAcc(3, 2);

	MulAcc(4, 1);

	MulAcc(5, 0);

	SaveMulAcc(5, 0, 6);

	MulAcc(1, 5);

	MulAcc(2, 4);

	MulAcc(3, 3);

	MulAcc(4, 2);

	MulAcc(5, 1);

	MulAcc(6, 0);

	SaveMulAcc(6, 0, 7);

	MulAcc(1, 6);

	MulAcc(2, 5);

	MulAcc(3, 4);

	MulAcc(4, 3);

	MulAcc(5, 2);

	MulAcc(6, 1);

	MulAcc(7, 0);

	SaveMulAcc(7, 1, 7);

	MulAcc(2, 6);

	MulAcc(3, 5);

	MulAcc(4, 4);

	MulAcc(5, 3);

	MulAcc(6, 2);

	MulAcc(7, 1);

	SaveMulAcc(8, 2, 7);

	MulAcc(3, 6);

	MulAcc(4, 5);

	MulAcc(5, 4);

	MulAcc(6, 3);

	MulAcc(7, 2);

	SaveMulAcc(9, 3, 7);

	MulAcc(4, 6);

	MulAcc(5, 5);

	MulAcc(6, 4);

	MulAcc(7, 3);

	SaveMulAcc(10, 4, 7);

	MulAcc(5, 6);

	MulAcc(6, 5);

	MulAcc(7, 4);

	SaveMulAcc(11, 5, 7);

	MulAcc(6, 6);

	MulAcc(7, 5);

	SaveMulAcc(12, 6, 7);

	MulAcc(7, 6);

	R[13] = c;

	p = (dword)A[7] * B[7] + d;

	R[14] = LOW_WORD(p);

	R[15] = e + HIGH_WORD(p);

}

static void CombaMultiplyBottom4(word *R, const word *A, const word *B)

{

	dword p;

	word c, d, e;

	p = (dword)A[0] * B[0];

	R[0] = LOW_WORD(p);

	c = HIGH_WORD(p);

	d = e = 0;

	MulAcc(0, 1);

	MulAcc(1, 0);

	SaveMulAcc(1, 2, 0);

	MulAcc(1, 1);

	MulAcc(0, 2);

	R[2] = c;

	R[3] = d + A[0] * B[3] + A[1] * B[2] + A[2] * B[1] + A[3] * B[0];

}

static void CombaMultiplyBottom8(word *R, const word *A, const word *B)

{

	dword p;

	word c, d, e;

	p = (dword)A[0] * B[0];

	R[0] = LOW_WORD(p);

	c = HIGH_WORD(p);

	d = e = 0;

	MulAcc(0, 1);

	MulAcc(1, 0);

	SaveMulAcc(1, 2, 0);

	MulAcc(1, 1);

	MulAcc(0, 2);

	SaveMulAcc(2, 0, 3);

	MulAcc(1, 2);

	MulAcc(2, 1);

	MulAcc(3, 0);

	SaveMulAcc(3, 0, 4);

	MulAcc(1, 3);

	MulAcc(2, 2);

	MulAcc(3, 1);

	MulAcc(4, 0);

	SaveMulAcc(4, 0, 5);

	MulAcc(1, 4);

	MulAcc(2, 3);

	MulAcc(3, 2);

	MulAcc(4, 1);

	MulAcc(5, 0);

	SaveMulAcc(5, 0, 6);

	MulAcc(1, 5);

	MulAcc(2, 4);

	MulAcc(3, 3);

	MulAcc(4, 2);

	MulAcc(5, 1);

	MulAcc(6, 0);

	R[6] = c;

	R[7] = d + A[0] * B[7] + A[1] * B[6] + A[2] * B[5] + A[3] * B[4] +

				A[4] * B[3] + A[5] * B[2] + A[6] * B[1] + A[7] * B[0];

}

#undef MulAcc

#undef SaveMulAcc

static void AtomicInverseModPower2(word *C, word A0, word A1)

{

	assert(A0%2==1);

	dword A=MAKE_DWORD(A0, A1), R=A0%8;

	for (unsigned i=3; i<2*WORD_BITS; i*=2)

		R = R*(2-R*A);

	assert(R*A==1);