/*
	big integer class for RSA calculation
	Numbers stored in big endian order.
*/

/*
 * Includes
 */
#include <stdio.h>
#include <string.h>
#include "bigint.h"

/*
 * Sub
 * Subtract (shifted) b from a.
 */
int BigInt::Sub(BigInt &a, BigInt &b, int b_shift)
{
	unsigned int b_byte = sizeof(data) - 1 + (b_shift / 8);
	int b_bit = (b_shift % 8);
	int carry = 0;
	for (int ia=sizeof(data)-1; ia>=0; ia--)
	{
		unsigned char b_data_shifted = 0;
		if (b_byte + 1 < sizeof(b.data)) b_data_shifted |= b.data[b_byte + 1] >> (8 - b_bit);
		if (b_byte + 0 < sizeof(b.data)) b_data_shifted |= b.data[b_byte + 0] << b_bit;
		b_byte--;
		int r = a.data[ia] - b_data_shifted + carry;
		data[ia] = r;
		carry = r>>8;
	}
	return carry;
}

/*
 * MulMod
 * Multiply two numbers and perform modulo.
 */
void BigInt::MulMod(BigInt &a, BigInt &b, BigInt &m)
{
	memset(this, 0, sizeof(*this));
	for (unsigned int ia=sizeof(data) - 1; ia>=sizeof(data)/2; ia--)
	{
		int carry = 0;
		for (unsigned int ib=sizeof(data) - 1; ib>=sizeof(data)/2; ib--)
		{
			int iab = ia + ib - sizeof(data) + 1;
			unsigned int r = a.data[ia] * b.data[ib] + carry + data[iab];
			data[iab] = r;
			carry = r>>8;
		}
	}

	for (int shift=sizeof(data)/2*8; shift>=0; shift--)
	{
		BigInt subbed;
		if (!subbed.Sub(*this, m, shift))	// positive?
		{
			memcpy(this, &subbed, sizeof(*this));
		}
	}
}

/*
 * PowMod
 * Raise to power 65537 and perform modulo.
 */
void BigInt::PowMod(BigInt &n, BigInt &m)
{
	BigInt n65536;
	memcpy(&n65536, &n, sizeof(n));
	for (int i=0; i<16; i++)	// 16 times n^2 = n^65536
	{
		BigInt tmp;
		tmp.MulMod(n65536, n65536, m);
		memcpy(&n65536, &tmp, sizeof(n));
	}
	MulMod(n, n65536, m);	// final result: n^1 * n^65536
}

/*
 * print
 */
void BigInt::print()
{
	printf("0x");
	bool show = false;
	for (unsigned int i=0; i<sizeof(data); i++)
	{
		if (data[i]) show = true;
		if (show) printf("%02X", data[i]);
	}
	printf(show ? "\n" : "0\n");
}

/*
 * Set
 */
void BigInt::Set(unsigned char *data, unsigned int length)
{
	memset(this, 0, sizeof(*this));
	memcpy(this->data + sizeof(this->data) - length, data, length);
}

/*
 * Get
 */
void BigInt::Get(unsigned char *data, unsigned int length)
{
	memcpy(data, this->data + sizeof(this->data) - length, length);
}