/*****************線性序列寄存器綜合內核函數************************/
/**************北京郵電大學信息安全中心***************/
/*****李武軍(lwj707@163.com,hotmail.com;QQ11604612)***/
/*算法基本原理：
	參考資料：代數和編碼（修訂版），萬哲先編或講課筆記
表示方法：對于多項式fx，只保存其系數cn于p_cn,保存序列a于sequence中
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h> 
#include<math.h>
char sequence[]="00100011101";
				//"000100110101111";
int n,dn,N,ln,m;
int *p_cn,*p_cm;
int Getdn(int n);
void FindMinNumRegister();
void PrintRegisterFunc();
void main()
{
	int i;
	N=strlen(sequence);
	ln=0;
	p_cm=new int[N+1];
	p_cn=new int[N+1];
	p_cn[0]=p_cm[0]=1;
	for(i=1;i<=N;i++)
		p_cn[i]=p_cm[i]=0;
	printf("a=%s\n",sequence);
	printf("n\tdn-1\tln\tfn(x)\n");
	FindMinNumRegister();
	//PrintRegisterFunc();

	delete []p_cn,p_cm;
}
void FindMinNumRegister()
{
	int i,temp;
	int *p_c_temp=new int[N+1];
	p_c_temp[0]=1;
	for(i=1;i<=N;i++)
		p_c_temp[i]=0;
	for(n=0,m=-1;n<N;n++,PrintRegisterFunc())
	{
		if(!(dn=Getdn(n)))//dn=0
			continue;
		else//dn!=0
		{	
			temp=__max(ln,n+1-ln);
			if(ln!=temp)//ln與當前的最大ln不等，應該保存作為lm
				memcpy(p_c_temp,p_cn,(n+1)*sizeof(int));//先暫存原來的fn
			if(m==-1)//第一次，即m等于初始值
				p_cn[n+1]=1;//fn+1=1+x^(n+1)
			else
			{
				for(i=n-m;i<=n;i++)
					p_cn[i]=p_cn[i]^p_cm[i-(n-m)];//fn+1=fn+（fm右移n-m)
			}
			if(ln!=temp)
			{
				ln=temp;//保存出當前的寄存器長度
				m=n;	//得到當前的最小的n作為lm中的m
				memcpy(p_cm,p_c_temp,(n+1)*sizeof(int));//保存fm
			}
		}
		
	}

}
int Getdn(int n)
{
	int i, result=0;
	for(i=0;i<=ln;i++)
		if(p_cn[i])
			result^=sequence[n-i]&1;
	return result;
}
void PrintRegisterFunc()
{
	char buffer[1024]="";
	char buff_num[10];
	_itoa(n,buff_num,10);
	printf("%s\t",buff_num);
	_itoa(dn,buff_num,10);
	printf("%s\t",buff_num);
	_itoa(ln,buff_num,10);
	printf("%s\t",buff_num);
	for(int i=0;i<=ln;i++)
	{
		if(p_cn[i])
			sprintf(&buffer[strlen(buffer)],"x^%d+",i);
	}
	if(buffer[2]=='0')//將x^0替換為1
	{
		buffer[2]='1';
		strcpy(buffer,&buffer[2]);
	}
	if(buffer[strlen(buffer)-1]=='+')// 去掉最后一個+;
		buffer[strlen(buffer)-1]='\0';	
	printf("%s\n",buffer);
}