#include "Stream.h"

#include <iostream>
using namespace std;

#include <memory.h>

/* Max size = 32 bits */


/* Some primitive polys
     Includes all of degree 4, 5 and 6

  x^4+x+1
  x^4+x^3+1

  x^5+x^2+1
  x^5+x^3+1
  x^5+x^3+x^2+x+1
  x^5+x^4+x^2+x+1
  x^5+x^4+x^3+x+1
  x^5+x^4+x^3+x^2+1

  x^6+x+1
  x^6+x^4+x^3+x+1
  x^6+x^5+1
  x^6+x^5+x^2+x+1
  x^6+x^5+x^3+x^2+1
  x^6+x^5+x^4+x+1

  x^11+x^2+1
  x^11+x^4+x^2+x+1
  x^14+x^5+x^3+x+1
  x^15+x+1
  x^15+x^4+1

  x^29+x^2+1
  x^29+x^4+x^2+x+1
  x^28+x^3+1
  x^28+x^9+1
  x^31+x^7+1
  x^31+x^3+1

  
*/


ulong table[num_pp][2] = {
  {4,  1+(1UL<<(4-1)) },
  {4,  1+(1UL<<(4-3)) },

  {5,  1+(1UL<<(5-2)) },
  {5,  1+(1UL<<(5-3)) },
  {5,  1+(1UL<<(5-3))+(1UL<<(5-2))+(1UL<<(5-1)) },
  {5,  1+(1UL<<(5-4))+(1UL<<(5-2))+(1UL<<(5-1)) },
  {5,  1+(1UL<<(5-4))+(1UL<<(5-3))+(1UL<<(5-1)) },
  {5,  1+(1UL<<(5-4))+(1UL<<(5-3))+(1UL<<(5-2)) },

  {6,  1+(1UL<<(6-1)) },
  {6,  1+(1UL<<(6-4))+(1UL<<(6-3))+(1UL<<(6-1)) },
  {6,  1+(1UL<<(6-5)) },
  {6,  1+(1UL<<(6-5))+(1UL<<(6-2))+(1UL<<(6-1)) },
  {6,  1+(1UL<<(6-5))+(1UL<<(6-3))+(1UL<<(6-2)) },
  {6,  1+(1UL<<(6-5))+(1UL<<(6-4))+(1UL<<(6-1)) },

  {11, 1+(1UL<<(11-2)) },
  {11, 1+(1UL<<(11-4))+(1UL<<(11-2))+(1UL<<(11-1)) },
  {14, 1+(1UL<<(14-5))+(1UL<<(14-3))+(1UL<<(14-1)) },
  {15, 1+(1UL<<(15-1)) },
  {15, 1+(1UL<<(15-4)) },

  {29, 1+(1UL<<(29-2)) },
  {29, 1+(1UL<<(29-4))+(1UL<<(29-2))+(1UL<<(29-1)) },
  {28, 1+(1UL<<(28-3)) },
  {28, 1+(1UL<<(28-9)) },
  {31, 1+(1UL<<(31-7)) },
  {31, 1+(1UL<<(31-3)) }
  };


/* Output a bit and update the register */
int get_bit(ulong& reg,ulong connections,int L)
{
  int output=reg&1;

  /* Get the tapped bits */
  ulong t=reg&connections;

  /* Collapse t down into one bit */
  t=(t>>16)^(t&0xFFFF);
  t=(t>>8)^(t&0xFF);
  t=(t>>4)^(t&0xF);
  t=(t>>2)^(t&0x3);
  t=(t>>1)^(t&0x1);
  reg>>=1;
  reg^=(t<<(L-1));
  
  return output;
}


int* get_stream(ulong& reg,ulong connections,int L,int N)
{
  int *ans=new int[N];
  for (int i=0; i<N; i++)
    { ans[i]=get_bit(reg,connections,L); }
  return ans;
}


/* Follows P-Code from HAC 6.30 
   C is assumed of length >= n+1
*/
int Berlekamp_Massey(int* s,int n,int *C)
{
  /* Create Polys C,T,B */
  int degC=0;
  C[0]=1;   memset(C+1,0,n*sizeof(int));

  int *T=new int[n+1];
  int *B=new int[n+1];
  int degT=-1,degB=-1;

  int L=0,m=-1,N=0,i;

  while (N<n)
    { /* Compute next discrepancy */
      int d=s[N];
      for (i=1; i<=L; i++)
        { d+=C[i]*s[N-i];  d&=1; }

      if (d==1)
        { memcpy(T,C,(n+1)*sizeof(ulong));
          degT=degC;
          
          if (degC<=(degB+N-m))
            { degC=degB+N-m; }
          for (i=0; i<=degB; i++)
            { C[i+N-m]+=B[i];  C[i+N-m]&=1; }

          if (L<=(N/2))
            { L=N+1-L; 
              m=N;
              memcpy(B,T,(n+1)*sizeof(ulong));
              degB=degT;
            }
        }
      N++;
    }

  delete[] T;
  delete[] B;

  return L;
}