#include <cassert>
#include "gf28.h"

using namespace std;

int GF28::reduce(int v,int m){
	assert(m);
	while(true){
		int sh=__builtin_clz(m)-__builtin_clz(v);
		if(sh<0)break;
		v^=m<<sh;
		if(v==0)break;
	}
	return v;
}

uint8_t GF28::multiply(uint8_t x,uint8_t y){
	if(x==0||y==0)return 0;
	int res=0;
	int addend=x;
	while(y){
		if(y&1)res^=addend;
		addend<<=1;
		if(addend&0x100)addend^=modulus;
		y>>=1;
	}
	return res;
}

GF28::GF28()
	:value(0){}

GF28::GF28(int v)
	:value(reduce(v,modulus)){}

GF28::operator uint8_t() const {
	return value;
}

GF28& GF28::operator+=(GF28 o){
	value^=o.value;
	return *this;
}

GF28& GF28::operator-=(GF28 o){
	value^=o.value;
	return *this;
}

GF28& GF28::operator<<=(int n){ //multiplication by x^n
	assert(n>=0);
	value<<=n;
	if(value&0x100)value^=modulus;
	return *this;
}

GF28 GF28::operator+(GF28 o) const {
	return GF28(value^o.value);
}

GF28 GF28::operator-(GF28 o) const {
	return GF28(value^o.value);
}

GF28 GF28::operator*(GF28 o) const {
	if(value==0||o.value==0)return GF28(0);
	GF28 res;
	GF28 addend(*this);
	while(o.value){
		if(o.value&1)res+=addend;
		addend<<=1;
		o.value>>=1;
	}
	return res;
}
GF28 GF28::operator<<(int n) const {
	return GF28(*this)<<=n;
}

bool GF28::operator==(GF28 o) const {
	return value==o.value;
}

GF28 GF28::inverse() const {
	if(value==0)return *this;
	int x=1,y=0,x2=0,y2=1,r=modulus,r2=value;
	while(r2!=0){
		assert(r!=0);
		int ex=__builtin_clz(r2)-__builtin_clz(r);
		if(ex<0){
			swap(x,x2);
			swap(y,y2);
			swap(r,r2);
		} else {
			int xn=x^(x2<<ex); x=x2; x2=xn;
			int yn=y^(y2<<ex); y=y2; y2=yn;
			int rn=r^(r2<<ex); r=r2; r2=rn;
		}
	}
	assert(r==1);
	return GF28(y);
}

ostream& operator<<(ostream &os,GF28 p){
	if(os.flags()&ios_base::hex){
		return os<<p.value;
	}
	if(p.value==0)return os<<'0';
	bool first=true;
	for(int m=1<<16,i=16;m!=0;m>>=1,i--){
		if(p.value&m){
			if(!first)os<<'+';
			first=false;
			if(i==0)os<<'1';
			else os<<"x^"<<i;
		}
	}
	return os;
}