LinearComplexity

lincomp.c

# include <stdio.h>
# include <stdlib.h>
# include <time.h>


int random_in_range (unsigned int min, unsigned int max)
{    
  int range       = max - min,
      remainder   = RAND_MAX % range,
      bucket      = RAND_MAX / range;  
  int base_random = rand(); /* in [0, RAND_MAX] */
  if (RAND_MAX == base_random) return random_in_range(min, max);
  /* now guaranteed to be in [0, RAND_MAX) */
  
  /* There are range buckets, plus one smaller interval
     within remainder of RAND_MAX */
  if (base_random < RAND_MAX - remainder) {
    return min + base_random/bucket;
  } else {
    return random_in_range (min, max);
  }
}

void arrayCopy(int * source, int * target, int len){
    int i = 0;
    while( i  < len ){
        source[i] = target[i];
        i++;         
    }   
}


int main(int argc, char *argv[]){
    int  l=0, m=0, i=0, len = 0, acc = 0,n=0, d = 0;
    int *u = NULL,*c = NULL, *b = NULL, *pinit = NULL, *tmp=NULL, *cplusp=NULL;

    clock_t uptime;     

    if(argc != 2){
        printf(" Expected a single command line argument");
        return EXIT_FAILURE;           
    }
    len = atoi(argv[1]);
    if(len < 0 ){
        puts(" The length of the sequence must be a positive integer ");
        return EXIT_FAILURE;
    }
    
    u = (int*)malloc(len * sizeof(int));
    

    if(!u){
        puts(" Memory allocation error ");
        return EXIT_FAILURE;
    }

    for(i=0;i<len;i++){
        u[i]= random_in_range(0,2);
    }
  
    uptime = clock () / (CLOCKS_PER_SEC / 1000);

    c = (int*)malloc(len * sizeof(int));
    b = (int*)malloc(len * sizeof(int));
    pinit = (int*)malloc(len * sizeof(int));
    tmp = (int*)malloc(len * sizeof(int));
    cplusp = (int*)malloc(len * sizeof(int));

    if(!(c && b && pinit && tmp && cplusp)){
        puts(" Memory allocation error ");
        return EXIT_FAILURE;
    }

    tmp[0]=c[0]=b[0]=1;
  
    for(n=0;n<len;n++){
        acc = u[n];
        for(i=0;i<l;i++){
            acc+=c[1+i]*u[n-i-1];   
        }
        d = acc % 2;
        if(d == 1){
            arrayCopy(c,tmp, len);
            for(i=0;i<n-m;i++){
                cplusp[i] = pinit[i]+c[i];    
            }
            for(i=n-m+1;i<l+1;i++){
                cplusp[i] = b[i]+c[i];     
            }
            for(i=0;i<len;i++){
                c[i] = cplusp[i] % 2;    
            }
            if(2 * l < n){
                l = n-l;
                m=n;
                arrayCopy(tmp, b, len);               
            }           
        }       
    }
  

  free(u);
  free(c);
  free(b);
  free(pinit);
  free(tmp);
  free(cplusp);

  printf(" Result: % d, time in milliseconds: % d \n ",l+1, (int) clock () / (CLOCKS_PER_SEC / 1000) - uptime );
  
  return 0;
}