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

using namespace std;

namespace GF28 {

	const int modulus=0x11b;

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

	uint8_t 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;
	}

	uint8_t inverse(uint8_t value){
		if(value==0)return value;
		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 reduce(y,modulus);
	}

}