// gf2n.cpp - written and placed in the public domain by Wei Dai

#include "pch.h"

#ifndef CRYPTOPP_IMPORTS

#include "gf2n.h"
#include "algebra.h"
#include "words.h"
#include "randpool.h"
#include "asn.h"
#include "oids.h"

#include <iostream>

NAMESPACE_BEGIN(CryptoPP)

PolynomialMod2::PolynomialMod2()
{
}

PolynomialMod2::PolynomialMod2(word value, unsigned int bitLength)
	: reg(BitsToWords(bitLength))
{
	assert(value==0 || reg.size()>0);

	if (reg.size() > 0)
	{
		reg[0] = value;
		SetWords(reg+1, 0, reg.size()-1);
	}
}

PolynomialMod2::PolynomialMod2(const PolynomialMod2& t)
	: reg(t.reg.size())
{
	CopyWords(reg, t.reg, reg.size());
}

void PolynomialMod2::Randomize(RandomNumberGenerator &rng, unsigned int nbits)
{
	const unsigned int nbytes = nbits/8 + 1;
	SecByteBlock buf(nbytes);
	rng.GenerateBlock(buf, nbytes);
	buf[0] = (byte)Crop(buf[0], nbits % 8);
	Decode(buf, nbytes);
}

PolynomialMod2 PolynomialMod2::AllOnes(unsigned int bitLength)
{
	PolynomialMod2 result((word)0, bitLength);
	SetWords(result.reg, ~(word)0, result.reg.size());
	if (bitLength%WORD_BITS)
		result.reg[result.reg.size()-1] = (word)Crop(result.reg[result.reg.size()-1], bitLength%WORD_BITS);
	return result;
}

void PolynomialMod2::SetBit(unsigned int n, int value)
{
	if (value)
	{
		reg.CleanGrow(n/WORD_BITS + 1);
		reg[n/WORD_BITS] |= (word(1) << (n%WORD_BITS));
	}
	else
	{
		if (n/WORD_BITS < reg.size())
			reg[n/WORD_BITS] &= ~(word(1) << (n%WORD_BITS));
	}
}

byte PolynomialMod2::GetByte(unsigned int n) const
{
	if (n/WORD_SIZE >= reg.size())
		return 0;
	else
		return byte(reg[n/WORD_SIZE] >> ((n%WORD_SIZE)*8));
}

void PolynomialMod2::SetByte(unsigned int n, byte value)
{
	reg.CleanGrow(BytesToWords(n+1));
	reg[n/WORD_SIZE] &= ~(word(0xff) << 8*(n%WORD_SIZE));
	reg[n/WORD_SIZE] |= (word(value) << 8*(n%WORD_SIZE));
}

PolynomialMod2 PolynomialMod2::Monomial(unsigned i) 
{
	PolynomialMod2 r((word)0, i+1); 
	r.SetBit(i); 
	return r;
}

PolynomialMod2 PolynomialMod2::Trinomial(unsigned t0, unsigned t1, unsigned t2) 
{
	PolynomialMod2 r((word)0, t0+1);
	r.SetBit(t0);
	r.SetBit(t1);
	r.SetBit(t2);
	return r;
}

PolynomialMod2 PolynomialMod2::Pentanomial(unsigned t0, unsigned t1, unsigned t2, unsigned int t3, unsigned int t4)
{
	PolynomialMod2 r((word)0, t0+1);
	r.SetBit(t0);
	r.SetBit(t1);
	r.SetBit(t2);
	r.SetBit(t3);
	r.SetBit(t4);
	return r;
}

template <word i>
struct NewPolynomialMod2
{
	PolynomialMod2 * operator()() const
	{
		return new PolynomialMod2(i);
	}
};

const PolynomialMod2 &PolynomialMod2::Zero()
{
	return Singleton<PolynomialMod2>().Ref();
}

const PolynomialMod2 &PolynomialMod2::One()
{
	return Singleton<PolynomialMod2, NewPolynomialMod2<1> >().Ref();
}

void PolynomialMod2::Decode(const byte *input, unsigned int inputLen)
{
	StringStore store(input, inputLen);
	Decode(store, inputLen);
}

unsigned int PolynomialMod2::Encode(byte *output, unsigned int outputLen) const
{
	ArraySink sink(output, outputLen);
	return Encode(sink, outputLen);
}

void PolynomialMod2::Decode(BufferedTransformation &bt, unsigned int inputLen)
{
	reg.CleanNew(BytesToWords(inputLen));

	for (unsigned int i=inputLen; i > 0; i--)
	{
		byte b;
		bt.Get(b);
		reg[(i-1)/WORD_SIZE] |= word(b) << ((i-1)%WORD_SIZE)*8;
	}
}

unsigned int PolynomialMod2::Encode(BufferedTransformation &bt, unsigned int outputLen) const
{
	for (unsigned int i=outputLen; i > 0; i--)
		bt.Put(GetByte(i-1));
	return outputLen;
}

void PolynomialMod2::DEREncodeAsOctetString(BufferedTransformation &bt, unsigned int length) const
{
	DERGeneralEncoder enc(bt, OCTET_STRING);
	Encode(enc, length);
	enc.MessageEnd();
}

void PolynomialMod2::BERDecodeAsOctetString(BufferedTransformation &bt, unsigned int length)
{
	BERGeneralDecoder dec(bt, OCTET_STRING);
	if (!dec.IsDefiniteLength() || dec.RemainingLength() != length)
		BERDecodeError();
	Decode(dec, length);
	dec.MessageEnd();
}

unsigned int PolynomialMod2::WordCount() const
{
	return CountWords(reg, reg.size());
}

unsigned int PolynomialMod2::ByteCount() const
{
	unsigned wordCount = WordCount();
	if (wordCount)
		return (wordCount-1)*WORD_SIZE + BytePrecision(reg[wordCount-1]);
	else
		return 0;
}

unsigned int PolynomialMod2::BitCount() const
{
	unsigned wordCount = WordCount();
	if (wordCount)
		return (wordCount-1)*WORD_BITS + BitPrecision(reg[wordCount-1]);
	else
		return 0;
}

unsigned int PolynomialMod2::Parity() const
{
	unsigned i;
	word temp=0;
	for (i=0; i<reg.size(); i++)
		temp ^= reg[i];
	return CryptoPP::Parity(temp);
}

PolynomialMod2& PolynomialMod2::operator=(const PolynomialMod2& t)
{
	reg.Assign(t.reg);
	return *this;
}

PolynomialMod2& PolynomialMod2::operator^=(const PolynomialMod2& t)
{
	reg.CleanGrow(t.reg.size());
	XorWords(reg, t.reg, t.reg.size());
	return *this;
}

PolynomialMod2 PolynomialMod2::Xor(const PolynomialMod2 &b) const
{
	if (b.reg.size() >= reg.size())
	{
		PolynomialMod2 result((word)0, b.reg.size()*WORD_BITS);
		XorWords(result.reg, reg, b.reg, reg.size());
		CopyWords(result.reg+reg.size(), b.reg+reg.size(), b.reg.size()-reg.size());
		return result;
	}
	else
	{
		PolynomialMod2 result((word)0, reg.size()*WORD_BITS);
		XorWords(result.reg, reg, b.reg, b.reg.size());
		CopyWords(result.reg+b.reg.size(), reg+b.reg.size(), reg.size()-b.reg.size());
		return result;
	}
}

PolynomialMod2 PolynomialMod2::And(const PolynomialMod2 &b) const
{
	PolynomialMod2 result((word)0, WORD_BITS*STDMIN(reg.size(), b.reg.size()));
	AndWords(result.reg, reg, b.reg, result.reg.size());
	return result;
}

PolynomialMod2 PolynomialMod2::Times(const PolynomialMod2 &b) const
{
	PolynomialMod2 result((word)0, BitCount() + b.BitCount());

	for (int i=b.Degree(); i>=0; i--)
	{
		result <<= 1;
		if (b[i])
			XorWords(result.reg, reg, reg.size());
	}
	return result;
}

PolynomialMod2 PolynomialMod2::Squared() const
{
	static const word map[16] = {0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85};

	PolynomialMod2 result((word)0, 2*reg.size()*WORD_BITS);

	for (unsigned i=0; i<reg.size(); i++)
	{
		unsigned j;

		for (j=0; j<WORD_BITS; j+=8)
			result.reg[2*i] |= map[(reg[i] >> (j/2)) % 16] << j;

		for (j=0; j<WORD_BITS; j+=8)
			result.reg[2*i+1] |= map[(reg[i] >> (j/2 + WORD_BITS/2)) % 16] << j;
	}

	return result;
}

void PolynomialMod2::Divide(PolynomialMod2 &remainder, PolynomialMod2 &quotient,
				   const PolynomialMod2 &dividend, const PolynomialMod2 &divisor)
{
	if (!divisor)
		throw PolynomialMod2::DivideByZero();

	int degree = divisor.Degree();
	remainder.reg.CleanNew(BitsToWords(degree+1));
	if (dividend.BitCount() >= divisor.BitCount())
		quotient.reg.CleanNew(BitsToWords(dividend.BitCount() - divisor.BitCount() + 1));
	else
		quotient.reg.CleanNew(0);

	for (int i=dividend.Degree(); i>=0; i--)
	{
		remainder <<= 1;
		remainder.reg[0] |= dividend[i];
		if (remainder[degree])
		{
			remainder -= divisor;
			quotient.SetBit(i);
		}
	}
}

PolynomialMod2 PolynomialMod2::DividedBy(const PolynomialMod2 &b) const
{
	PolynomialMod2 remainder, quotient;
	PolynomialMod2::Divide(remainder, quotient, *this, b);
	return quotient;
}

PolynomialMod2 PolynomialMod2::Modulo(const PolynomialMod2 &b) const
{
	PolynomialMod2 remainder, quotient;
	PolynomialMod2::Divide(remainder, quotient, *this, b);
	return remainder;
}

PolynomialMod2& PolynomialMod2::operator<<=(unsigned int n)
{
	if (!reg.size())
		return *this;

	int i;
	word u;
	word carry=0;
	word *r=reg;

	if (n==1)	// special case code for most frequent case
	{
		i = reg.size();
		while (i--)
		{
			u = *r;
			*r = (u << 1) | carry;
			carry = u >> (WORD_BITS-1);
			r++;
		}

		if (carry)
		{
			reg.Grow(reg.size()+1);
			reg[reg.size()-1] = carry;
		}

		return *this;
	}

	int shiftWords = n / WORD_BITS;
	int shiftBits = n % WORD_BITS;

	if (shiftBits)
	{
		i = reg.size();
		while (i--)
		{
			u = *r;
			*r = (u << shiftBits) | carry;
			carry = u >> (WORD_BITS-shiftBits);
			r++;
		}
	}

	if (carry)
	{
		reg.Grow(reg.size()+shiftWords+1);
		reg[reg.size()-1] = carry;
	}
	else
		reg.Grow(reg.size()+shiftWords);

	if (shiftWords)
	{
		for (i = reg.size()-1; i>=shiftWords; i--)
			reg[i] = reg[i-shiftWords];
		for (; i>=0; i--)
			reg[i] = 0;
	}

	return *this;
}

PolynomialMod2& PolynomialMod2::operator>>=(unsigned int n)
{
	if (!reg.size())
		return *this;

	int shiftWords = n / WORD_BITS;
	int shiftBits = n % WORD_BITS;

	unsigned i;
	word u;
	word carry=0;
	word *r=reg+reg.size()-1;

	if (shiftBits)
	{
		i = reg.size();
		while (i--)
		{
			u = *r;
			*r = (u >> shiftBits) | carry;
			carry = u << (WORD_BITS-shiftBits);
			r--;
		}
	}

	if (shiftWords)
	{
		for (i=0; i<reg.size()-shiftWords; i++)
			reg[i] = reg[i+shiftWords];
		for (; i<reg.size(); i++)
			reg[i] = 0;
	}

	return *this;
}

PolynomialMod2 PolynomialMod2::operator<<(unsigned int n) const
{
	PolynomialMod2 result(*this);
	return result<<=n;
}

PolynomialMod2 PolynomialMod2::operator>>(unsigned int n) const
{
	PolynomialMod2 result(*this);
	return result>>=n;
}

bool PolynomialMod2::operator!() const
{
	for (unsigned i=0; i<reg.size(); i++)
		if (reg[i]) return false;
	return true;
}

bool PolynomialMod2::Equals(const PolynomialMod2 &rhs) const