/****************************************************************************/
/**                                                                        **/
/**  crackvig.c -- breaks vignere encryption, retrieves keyword            **/
/**                                                                        **/
/**  to compile:  gcc -ansi -o crackvig crackvig.c                         **/
/**  to run:  ./crackvig -4 < ciphertext.txt                               **/
/**                                                                        **/
/**  The supplied number (4) is your guess for the keyword length.         **/
/**                                                                        **/
/**  The code uses a likelihood ratio test; it includes functions for      **/
/**  other tests, like entropy and index of coincidence (inferior!)        **/
/**                                                                        **/
/****************************************************************************/

#define TEST_FUN test_using_LR

/** Replace this ^^^^^^^^^^^^^ with test_using_IC, or test_using_Entropy **/
/****************************************************************************/

#include <stdio.h>
#include <ctype.h>
#include <math.h>
#define INDEX(c) ( ((c)|' ')-'a' )

unsigned int guess=3;
unsigned int * histogram;
int everything_is_cool( int argc, char ** argv );
double test_using_LR( int * hist, int * feedback );
double test_using_IC( int * hist, int * feedback );
double test_using_Entropy( int * hist, int * feedback );

double (*test_function)( int * hist, int * feedback );


/**********************************************************************/

int main( int argc, char ** argv ) {

	int i,j,pos=0;

	char ch;
	double confidence;

	test_function = TEST_FUN;
	
	if( everything_is_cool( argc, argv ) ) {

		ch = getchar();           /** Read in text **/
		while( !feof(stdin) ) {  
	   	   if( isalpha(ch) ) {
		      histogram[ INDEX(ch) + 26*pos ]++;
		      pos++; if(pos>=guess) pos-=guess;
		   }
		   ch = getchar();
		}

		printf( "Guessing key:  " );

		confidence=0.0;
		for( i=0; i<guess; i++ ) {
			confidence += 
				test_function(histogram+i*26, &j ); 

			putchar( 'A'+j );
		}
		printf( " --- confidence %f\n", confidence );
		free( histogram );
	}
	return 0;
}


/****** Distribution of letters in Moby Dick **************************/

int moby[26] =  {
        76492, 16603, 22143, 37658, 115029, 20477, 20495, 61780, 64384, 
        1062, 7938, 42051, 22905, 64556, 68139, 16962, 1544, 51160, 
        63106, 86557, 26317, 8419, 21774, 1007, 16604, 623
};
int mobysize = 935785;

double P_eng[26];  /*** we'll just set P_eng == the type T_mobydick ***/
 
void compute_Peng( void ) {
	int i;
	for( i=0; i<26; i++ ) P_eng[i] = ((double) moby[i])/mobysize;
}

/**********************************************************************/
/***  Here is the code to compute likelihood ratio test.    ***********/

double LLR( int * hist, int shift ) {

	int i,j;
	double sum=0.0, llr;

	for( i=0; i<26; i++ )  {

		j = (i+shift) % 26;
		llr = log( P_eng[i] ) + log(26.0);
		llr *= hist[j];
		sum += llr;
	}
	return sum;
}

/**********************************************************************/
/***  I've added some extra functions you can call instead, ***********/
/***  If you want to compare performance.                   ***********/

double test_using_LR( int * hist, int * feedback ) {

	int shift, bestshift;
	double confidence, max;
	
	max = LLR( hist, bestshift=0 );

	for( shift=1; shift<26; shift++ ) {
		confidence = LLR( hist, shift );
		if( confidence > max ) {
			max = confidence;
			bestshift = shift;
		}
	}	
	bestshift = (bestshift+25)%26; /* set 0-->z, 1-->a, 2-->b... */

	*feedback = bestshift;
	return max;
}

double test_using_Entropy( int * hist, int * feedback ) {
	int i, total=0;
        double x,sum=0.0;

	for( i=0; i<26; i++ ) { total += hist[i]; }

	if( total ) { 
		for( i=0; i<26; i++ )  {
		   x = ((double) hist[i])/total;
		   if( x!=0.0 )  sum -= x * log(x);
		}
	}

	*feedback=-1;  /** No estimate of key **/
	return ( log(26.0)-sum )/guess; 
}

double test_using_IC( int * hist, int * feedback ) {
	int i, total=0;
        double x,sum=0.0;

	for( i=0; i<26; i++ ) { total += hist[i]; }

	if( total ) { 
		for( i=0; i<26; i++ ) {
		   x = ((double) hist[i])/total;
		   sum += x*x;
		}
	}

	*feedback=-1;  /** No estimate of key **/
	return sum/guess;
}


/**********************************************************************/

int everything_is_cool( int argc, char ** argv ) 
{
	int i, coolness=0;

	compute_Peng();  /** Set up values of P_E ***/

        if( argc != 2 ) /* only one extra argument allowed */
        { 
	      printf( "\nUsage:  %s -[guess].\n", argv[0] );
	      printf( "\"guess\" is your guess for the keylength.\n" );
	} 
        else {
            if( argv[1][0] == '-' ) /* Look for a hyphen */
            {
                sscanf( argv[1]+1, "%d", &guess );
                fprintf( stderr, "Guess key length = %d\n", guess );
		coolness=1;
            }
            else
		fprintf( stderr, "%s is an invalid argument.\n", argv[1] );
	}
	
	histogram = (int *) malloc( guess*26*sizeof(int) );
	if( histogram==NULL ) {
		fprintf( stderr, "Failed to allocate memory.\n" );
		coolness=0;
	} else {
		for( i=0; i<guess*26; i++ ) histogram[i]=0;
	}
	return coolness;
}