#include <stdio.h> 
#include "minwise.h"
#include "assert.h"

irreduciblePolynomial::irreduciblePolynomial(int n_){
	n=n_;
	f=new char[n+1];
#ifdef DEBUG
	printf("Generating Irreducible_polynomial of degree %d\n",n);
	int count=0;
#endif
	for(int i=1;i<n-1;i++){
		f[i]=RANDOMBIT();
	}
	f[0]=f[n-1]=1;
	if(n==2)
		f[0]=RANDOMBIT(); //special for degree 2
	while(!iptest(f,n)){

#ifdef DEBUG
	count++;
#endif
		for(int i=1;i<n-1;i++){
			f[i]=RANDOMBIT();
		}
	}
#ifdef DEBUG
	printf("Done after %d trials.\n",count);
#endif
}

char* irreduciblePolynomial::getBits(){
	return f;
}

irreduciblePolynomial::~irreduciblePolynomial(){
	delete []f;
}

int irreduciblePolynomial::iptest(char *x, int dx){
	char *u=new char[dx*2+1];
	int du;
	char *t=new char[dx*2+1];
	int dt;
	char *c=new char[dx+1];
	int dc;

	assert(u&&t&&c&&x);

	for(int i=0;i<dx*2;i++)u[i]=0;

	//u=2;
	u[1]=1;
	du=2;
	for(int i=1;i<dx-1;i++){

		// t=u*u
		dt=du*2-1;
		for(int j=0;j<dt;j++) t[j]=0;
		for(int j=0;j<du;j++)
			if(u[j]) for(int k=0;k<du;k++)
			t[k+j]^=u[k];
			
		//t=t%x
		while(dt>=dx){
			for(int j=0;j<dx;j++)
				t[j+dt-dx]^=x[j];		
			while(dt>1&&t[dt-1]==0)dt--;
		}


		/* notice t might be 0 with dt=1 t[0]=0 */
		//u=t
		du=dt;
		for(int j=0;j<du;j++)
			u[j]=t[j];

		//t=t XOR 2
		t[1]^=1; 	
		if(dt<=2){
			dt=2; 
			while(dt>1&&t[dt-1]==0)dt--;
		}

		/* if t=0 , gcd(0,x) will be 0 */
		if(dt==1&&t[0]==0){
			delete []u;
			delete []t;
			delete []c;
			return 0; /* blow it! */
		}

		//c=x;
		dc=dx;
		for(int j=0;j<dx;j++)c[j]=x[j];

		//gcd(t,c);
		int sw=(dc>=dt);
		while(dc>0&&dt>0){
			if(sw){//dc>=dt c=c%t
				while(dc>=dt){
					for(int j=0;j<dt;j++)
						c[j+dc-dt]^=t[j];		
					while(dc>0&&c[dc-1]==0)dc--;
				}
			}else{//dc<=dt  t=t%c;
				while(dt>=dc){
					for(int j=0;j<dc;j++)
						t[j+dt-dc]^=c[j];		
					while(dt>0&&t[dt-1]==0)dt--;
				}
			}
			sw=!sw;
		}

		if(dt>1||dc>1){	 //gcd(t,x)=1;
			delete []u;
			delete []t;
			delete []c;
			return 0;
		}
	}
	delete []u;
	delete []t;
	delete []c;
	return 1;
}

LFSR::LFSR(int m_){
	m=m_;

	s=new char[m+1];
	for(int i=0;i<m;i++){
		s[i]=RANDOMBIT();
	}

	ip=new irreduciblePolynomial(m+1);
	f=(ip->getBits()+1);

	r=new char[m+1];
	for(int i=0;i<m;i++)
		r[i]=s[i];
	t=m;
}

LFSR::~LFSR(){
	delete [] r;
	delete ip;
	delete [] s;
}

void LFSR::getBits(INTTYPE pos, int len, char *buf){ //return len bits from bit pos

	int count=0;
	
	for(int i=0;i<m;i++)
		r[i]=s[i];
	INTTYPE t=m;

	while(pos>=t){
		char b=0;
		for(int i=0;i<m;i++)
			b=b^(r[(i+t)%m]&f[i]);
		r[(t++)%m]=b;
	}

	while(count<len){
		for(;pos<t && count<len;pos++){
			buf[count++]=r[pos%m];
		}
		char b=0;
		for(int i=0;i<m && count <len ;i++)
			b=b^(r[(i+t)%m]&f[i]);
		r[(t++)%m]=b;
	}

	return; 
}