/*
 * by pavle michko, february 2014
 * a naive code to generate optimal
 * sequences
 */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include<omp.h>


typedef unsigned long long seq;

int alpha = 5;

int weight( seq x )
{ int r = 0;
  while ( x ) {
     x &= (x-1);
     r++;
  }
  return r;
}
int acorr( seq x, seq m , int L)
{ seq y;
  int i, w;
  y = x;
  for ( i = 1; i < L ; i++ ) {
     y = ( 2 * y ) % m;
     w = abs( L - 2 * weight( x ^ y ) );
     if ( w > alpha  ) return 0;
  };
  return 1;
}

int leader( seq x , seq m )
{ seq y = x, z;
  do {
     y = ( y * 2 ) % m;
     if  ( y < x ) return 0; 
  } while ( y != x );
  z = (~x) & m;
  y = z;
  do {
     y = ( y * 2 ) % m;
     if  ( y < x ) return 0;
  } while ( y != z );
  return 1;
}
void print( seq s , int L )
{
int i;
printf("\n");
for( i = 0; i < L; i++ , s >>=1)
   if ( s&1 ) printf(" -"); else printf(" +");
}

int main( int argc, char* argv[] )
{
FILE *dst;
char fn[64];
seq s, m;
int L = 0, Q = -1;
int opt;
int good=0;
while ((opt = getopt(argc, argv, "L:Q:")) != -1) {
               switch (opt) {
               case 'L':
                   L = atoi( optarg );
                   break;
               case 'Q':
                   Q = atoi( optarg );
                   break;
               default: /* '?' */
                   fprintf(stderr, "Usage: %s [-Quantity][-Length]\n",
                           argv[0]);
                   exit(EXIT_FAILURE);
               }
           }
if ( L == 0 ) {
   printf("\nargument L is missing");
   return 1;
}
if ( Q < 0 ) {
   printf("\nargument Q is missing");
   return 1;
}
sprintf( fn, "data/opt-%d.dat", L );
dst = fopen( fn, "w" );

switch ( L % 4 ) {
  case 0 : alpha = 4; break;
  case 1 : alpha = 3; break;
  case 2 : alpha = 2; break;
  case 3 : alpha = 1; break;
}
m = (((seq ) 1) << L) - 1; 
{ 
  #pragma omp parallel for  reduction(+:good) 
  for( s = 1; s < m; s++ ) {
     if ( leader(s, m) ) {
	if ( acorr( s , m,  L ) ){ 
            good++; 
            fprintf( dst, "%Ld\n", s );
        }
    }
  } // end of for
} // end of mic
fprintf(stdout, "\nL=%d status= %d\n", L, good==Q);
fclose(dst); 
return 0;
}