#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
 
 


int dec_to_gf[16];  // globe parameters; store the gf_exp (see figure 1)
int p_vect[80];     // arrays for transforming form GF to Dec and Dec
int gf_to_dec[16];  // to GF. they initial in funciont initial().
int *Temp,*Result,*EncodeOut;

        
void initial(int m)  // when you want to use RS prog , this one must run first.
{
	//生成函數 f(D)=D^3+D+1; GF(2^3)
	// for different m there are different f(D).
	int gd[8][5]={{0,1,3},{0,1,4},{0,2,5},{0,1,6},{0,3,7},{0,2,3,4,8},{0,4,9},{0,3,10}};  
	//本原多項式
    int gd_len[8]={3,3,3,3,3,5,3,3};
    int pow2=(int)pow(2,m);	
    	
	int gf_vect[16],gf_exp[16];            // 用矢量表示。
    int i,j;
    int gf_temp[80];   // 存放多項式[000],按二進制表示。1表示此系數有=[pow2][m+1]

	int h;
	int sum;
	int k;

	// allocate the memory  
	// for example 
	// when m=3      
	//        index = 0,1,2
	// the gf_temp ={1,0,0
	//               0,1,0
	//               0,0,1 
	//               1,1,0 
	//                ...}
    //gf_temp=(int *)calloc(pow2*(m+1),sizeof(int));  
    //gf_vect=(int *)calloc(pow2,sizeof(int));
	//gf_exp= (int *)calloc(pow2,sizeof(int));
		//             THE GF(2^3)
	    //        gf_exp              gf_temp
		// ═══╤═══╤═════╤═══
		//   i   │gf_exp│polynomial│vector
		// ───┼───┼─────┼───
		//   0   │ a^0  │        1 │ 001 
		//   1   │ a^1  │     a    │ 010 
		//   2   │ a^2  │ a^2      │ 100 
		//   3   │ a^3  │     a +1 │ 011 
		//   4   │ a^4  │ a^2 +a   │ 110 
		//   5   │ a^5  │ a^2 +a+1 │ 111  
		//   6   │ a^6  │ a^2   +1 │ 101   
		//   7   │ a^7  │      0   │ 000  
		// ═══╧═══╧═════╧═══
	    //           figure 1
   // there are the py's coefficient stored in gf_temp[][],for example 
   //if shi vecotor expression is [001] then gf_temp[][]={1,0,0,0} 
   // the gf_temp[][m+1] is to judge if the expression is exceed the
   // GF(2^3), for an instance ,if the gf_temp[][]={0,0,0,1},this is 
   //to say that it is exceed the domain of GF, the max bit 1 should 
   //be replaced by 1+a, the program should to adjust this instance.
   //becasue a^3=a+1(it is depended on the f(D)=D^3+D+1),so the gf_temp[][]
   //={0,0,0,1} should be rewritted as gf_temp[][]={1,1,0,0}; 
   // initial the array gf_temp.
	gf_temp[0]=1;
   for(j=1;j<m+1;j++)
   {
     gf_temp[j]=0;
   }
   for(i=1;i<pow2;i++)
   {
        gf_temp[m*i+0]=0;     
		 // the LSB is initial to 0;
		 // then we left shift 1 bit.that is equal to multiply by 2
		 //  the now value is equal to the last value mult by 2
		 //  for example the last valuse is 010,the now value should be 100,
		 //  all those are expressed by vector.		 
         for (j=m+1;j>0;j--)
         {
			 if (i!=pow2-1) gf_temp[m*i+j]=gf_temp[(i-1)*m+j-1];
		     else gf_temp[m*i+j]=0;
         }
		 
         // just as tell above , when the value is exceed the GF domain 
		 // we shoud adjust this value.
		 h=0;
		 if (gf_temp[m*i+m]==1)
         {
           for(k=0;k<m;k++)
           {
              if(k==gd[m-3][h] && h!=gd_len[m-3])
			  {
				  gf_temp[m*i+k]=(1+gf_temp[m*i+k]) % 2;
				  h++;
			  }
           }
		 }
   }
   ///////////////////////////////////////////////////////////////////////////////////////
/*   for (i=0;i<pow2*m;i++)
   {
   cout<<gf_temp[i]<<"  ";
    if((i+1)%m==0)
	   cout<<endl;
   }*/
   ///////////////////////////////////////////////////////////////////////////////////////
   sum=0;   
   // now the importance process is completed
   // this step is just to count the decimal value.
   for(i=0;i<pow2;i++)
   {
     for (j=0;j<m;j++)
        sum+=(int)(gf_temp[m*i+j]*pow(2,j));
	 gf_vect[i]=sum;
	
	 gf_exp[sum]=i;
     if ( sum==0)
  	 gf_exp[sum]=pow2-1;
	 sum=0;
    }

   for(i=0;i<16;i++)
	   dec_to_gf[i]=gf_exp[i];
   for(i=0;i<80;i++)
	   p_vect[i]=gf_temp[i];
   for(i=0;i<16;i++)
	   gf_to_dec[i]=gf_vect[i];

   //dec_to_gf=gf_exp;
   //p_vect=gf_temp;
   //gf_to_dec=gf_vect;

   //free(gf_exp);
   //free(gf_temp);
   //free(gf_vect);
}

int  AddInGf(int TheDataWantToAddA,int TheDataWantToAddB,int m) //GF域的加法
{

	int sumret[4];
	int i;
//	int pow2;
    int sum=0;
	//sumret=(int*)calloc(m,sizeof(int));
//    pow2=pow(2,m);
	for (i=0;i<m;i++)
	{
		if((m*TheDataWantToAddA+i)>=80)
			return 0;
		sumret[i]=(p_vect[m*TheDataWantToAddA+i]+p_vect[TheDataWantToAddB*m+i])%2;
	}   
	for (i=0;i<m;i++)
	{
		sum+=(int)(sumret[i]*pow(2,i));
	}
	// the output is in form of exponent.
	// when return's value is 3, represent it is a^3
    //free(sumret);	
	return dec_to_gf[sum];    //dec_to_gf=gf_exp;  gf_exp[sum]=i
}


int MultInGf(int dataA, int dataB, int N)   // GF 域的乘法
{
   int GiMultInput;
   if (dataA!=N && dataB!=N)
		GiMultInput=(dataA+dataB) % N;  // a^i * a^j = a^(i+j)
   else
  		GiMultInput=N;
      return GiMultInput;
}


int DivInGf(int dataA,int dataB, int N )/* N=2^m */
{
	int sign,result;
	sign=dataA-dataB;
	if(sign>=0)
		result=sign;
	else
		result=N+sign;
	return result;
}


 int * Encode(int data[], int g[],int m /*2^m*/,int N,int L)
 {
	 // the datas to encode stored in data[] should like following
	 // length(data) must = L;     
	 // for example: if you want to encode 3, 4, 6 in decadal.
	 // you should let data[]={3,4,6} the 3 is first bit.L=3;
	 /////////////////////////////////////////////////////////////
	 // the length of g must eq to N-L+1;
	 // ohterwire there will be error.
     // g is the exponent of create polynomial.
	 // if g=a^2 X^2+ X+ a^4
	 // then g[]={4,0,2}
	 /////////////////////////////////////////////////////////////
	 /* the return value is also in form of exponent*/
	 int i, j;	
	 int a,GiMultInput;
	// int *p;
	/*
		  +-------------+-------------------------+---------------------+                                                                  
		  |             |                         |                     |                                             
	g0-->(*)      g1-->(*)              gN-L-1-->(*)                    |                                                            
		  |             |                         |                     |                                             
		  | +------+    |    +------+             |     +----------+    |                                                                          
		  ->| R[0] |---(+)-> | R[1] |-(+)->....--(+)->  | R[N-L-1] |-->(+)                                                                                
			+------+         +------+                   +----------+ |  |                                                                       
																	 +--|--->the remain N-L number                                                                    
							                          --input->---------+--->first L number

	                          figure 2*/
	 int *R;//,*EncodeOut;
	 R=(int *)calloc(N-L,sizeof(int)); // in form of exponent.a^(pow2-1)=000.
     EncodeOut=(int *)calloc(N,sizeof(int));
	 // initial the array R
	 for (i=0;i<N-L;i++)
		 R[i]=N;
	 /*in this prog the pow2-1 is a special number. it denote the zero in decimal*/
	 /* the num (pow2-1) represent zero [00..0]*/
	 
	 for (j=0;j<L;j++)
	 {
		a=AddInGf(R[N-L-1],data[j],m);  // a^i +a ^j     N+data[j]
		//cout<<a<<endlR;
		for(i=N-L-1;i>0;i--)
		{
		 // a^i * a^j = a^(i+j)
		 GiMultInput=MultInGf(g[i],a,N);
		 R[i]=AddInGf(GiMultInput ,R[i-1],m);
		}
     	R[0]=MultInGf(g[0],a,N);
	 }
	 
	 for(i=0;i<N;i++)
	 {
		 if (i<N-L)
			 EncodeOut[i]=R[i];
		 else
			 EncodeOut[i]=data[N-i-1];
	 }
	 
	// p=EncodeOut;
	 //free(p);
	 
	 free(R);
	 //return p;
	 return EncodeOut;

}

int *GenGx(int m,int N,int L)  //generation polynomial.(m=4,N=15;L=9)
{
	int d=N-L+1;
	int *gx=(int *)calloc((d-1)*2,sizeof(int));
	int Row=2;
    int *addtemp=(int *) calloc(d,sizeof(int));
    int *multtemp=(int *) calloc(d,sizeof(int));
	//int *
		
    int i,j;
    Temp=(int *)calloc(d,sizeof(int));
	for (i=0;i<d-1;i++ )    
	{
		gx[Row*i]=i+1;
		gx[Row*i+1]=0;
		Temp[i]=N;
	}
        Temp[d-1]=N;
	
	Temp[0]=gx[0];
	Temp[1]=gx[1];
	for(i=1;i<d-1;i++)
	{
       for(j=1;j<=d-1;j++) //(a+x)(a^2+x)=a(a^2+x)+x(a^2+x)
		{
		   addtemp[j]=MultInGf(gx[Row*i],Temp[j],N); ///a(a^2+x)
		   multtemp[j]=Temp[j-1];
		}
		addtemp[0]=MultInGf(gx[Row*i],Temp[0],N);
		multtemp[0]=N;
		for(j=0;j<=d-1;j++)
		{
			Temp[j]=AddInGf(addtemp[j],multtemp[j],m);
		}
	}