Skip to content

Instantly share code, notes, and snippets.

@lshifr
Last active December 14, 2015 20:19
Show Gist options
  • Save lshifr/5142849 to your computer and use it in GitHub Desktop.
Save lshifr/5142849 to your computer and use it in GitHub Desktop.
LinearComplexity
# 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment