/*
 * by pavle michko, february 2014
 * a naive code to look for binary
 * sequences with minimal autocorrelation
 */

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


typedef unsigned long long seq;

#ifdef MIC 
__attribute__ ((target (mic)))
#endif
int alpha = 5;

#ifdef MIC 
__attribute__ ((target (mic)))
#endif
int weight( seq x )
{ int r = 0;
  while ( x ) {
     x &= (x-1);
     r++;
  }
  return r;
}
#ifdef MIC 
__attribute__ ((target (mic)))
#endif
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;
}

#ifdef MIC 
__attribute__ ((target (mic)))
#endif
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 = stdout;
seq s, m;
int L = 0;
int opt;
int good=0;
while ((opt = getopt(argc, argv, "d:L:")) != -1) {
               switch (opt) {
               case 'L':
                   L = atoi( optarg );
                   break;
               case 'd':
                   dst = fopen( optarg, "a");
                   if ( !dst) 
                      exit(1);
                   break;
               default: /* '?' */
                   fprintf(stderr, "Usage: %s [-directory] [-Length]\n",
                           argv[0]);
                   exit(EXIT_FAILURE);
               }
           }
if ( L == 0 ) {
   printf("\nargument L is missing");
   return 1;
}
#ifdef MIC
#pragma offload target (mic)
#endif
{
  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++; 
    }
  } // end of for
} // end of mic
fprintf(stdout, "\nL=%d (%d) alpha=%d opt=%d\n", L, L%4, alpha, good);
fprintf(dst, "L=%d (%d) alpha=%d opt=%d\n", L, L%4, alpha, good);
fclose(dst); 
return 0;
}