#include<iostream>
#include<ctype.h>
#include<math.h>
#include <iomanip>
#include<fstream>

using namespace std;

int input(void);
int index_coincidence(void);
int remove_factors(int);
void analyse(int);
int frequency_analyse(int,char[]);
int chi_squared(int,float[]);
void decode(int,int,char[]);

/*************************************/
/* Various Global variables it was   */
/* useful to declare. Kept to a min. */
/* for tidiness's sake               */
/*************************************/
int size=26;
float final_check,chi_tollerance,ic_tollerance;
char* code= new char[size]; 
float* index = NULL;
int* kwlengths = NULL;
char* decoded_slice = NULL;

int main()
{
  char i;
  int total;
 
/***********************************/
/* Infinite loop at the 'top' of   */ 
/* code - can be broken by user    */
/* input after each decoding       */
/*                                 */
/* main function then calls        */
/* succcesive functions to perform */
/* the decryption, first finding   */
/* keyword length, and then        */
/* performing frequency analysis   */
/***********************************/
  for(;;)
    {
      size=input();  

      cout<<"Enter acceptance level for plaintext (chi-squared) (90): ";
      cin>>chi_tollerance;
      cout<<"Enter tolerance for index of coincidence (5.2) :";
      cin>>ic_tollerance;
      
      total=index_coincidence();
      total=remove_factors(total);
      analyse(total);
      
      cout<<endl<<"Y to try again, N to quit: ";
      cin>>i;
      i=toupper(i);
      
      while(i!='Y' && i!='N')
	{
	  cout<<"Unrecognised input - try again :";
	  cin>>i;
	  i=toupper(i);
	}
      
      if(i=='N')
	{
	  break;
	}
      
    }
  return 0;
}

/***************************************/
/* This function will read in the code */
/* from a text file into a dynamically */
/* allocated array (dynamic arrays     */
/* used throughout for same reasons),  */ 
/* so as to be as                      */
/* flexible as possible.               */
/* All inputed code is also converted  */
/* to uppercase for consistency, and   */
/* a check is made to ensure the       */
/* character is a letter               */
/* To determine the number of          */
/* characters, the next character to   */
/* be read in is always checked for    */
/* the end of file flag. If present,   */
/* file input stops.                   */
/*                                     */
/* The function returns the number of  */
/* characters to the main function for */
/* use elswhere in the program         */
/***************************************/
int input(void)
{
  char filename[50];
  int tally=0,i=0,j=0;
  int check;
  char input;
  
  ifstream fin;
  
  cout<<"Enter name of code file: ";
  cin>>filename;
  
  fin.open(filename);
  
  while(fin.good() ==false)					
    {
      cout<<"File not found. Try again"<<endl;
      cout<<"Enter code filename: ";
      cin>>filename;
      
      fin.open(filename);
      
    }
  
  while(fin.eof()==false)
    {
      
      input=fin.get();
      input=toupper(input);
      check=static_cast<int>( input );
      
      if(check>=65 && check <=90)
	{
	  code[i]=input;
	  i++;

	  if(i>=size)
	    {
	      size*=2;
	      
	      char* temp = new char [size];
              for(j=0;j<i;j++)
		{
		  temp[j]=code[j];
		}
	      
	      delete [] code;
	      code=temp;
	    }
	}
    }
  size=i;
  char* temp = new char [size];
  
  for(j=0;j<size;j++)
   {
      temp[j]=code[j];
    }
 delete [] code;
 code=temp;
  
  fin.close();
  
  return(size);
}
/****************************************/
/* This function calculates the index   */
/* of coincidence of the ciphertext for */
/* each possible codeword length up to  */
/* size/2 (where size is the length of  */
/* the ciphertext - any longer it would */
/* be very hard tyo crack               */
/* English text (or english text that   */
/* has merely been shifted x places     */
/* will have an index of coincidence of */
/* around 5, wheras random text (i.e    */
/* where each letter has been shifted   */
/* by a different amount) should have a */
/* lower index of about 3. By looking   */
/* any index of coincidences >5ish      */
/* a set of possible keylengths can be  */
/* obtained.                            */
/****************************************/
int index_coincidence(void)
{
  int total=0;
  int i,j,b=0;
  
  index = new float[size/2];
  
  for(i=0;i<(size/2);i++)
    { 
      index[i]=0;
    }
  for(i=1;i<(size/2);i++)
    {    
      for(j=0;j<(size-i);j++)
        {
	  if(code[j]==code[j+i])
	    index[i]++;            
        }
    }  
  for(i=0;i<(size/2);i++)
    {
      index[i]=(index[i]/size)*100;
    }
  
  for(i=0;i<(size/2);i++)
    {
      if(index[i]>ic_tollerance)
	{
	  total++;
	}
    }
  kwlengths=new int[total];
  
  for(i=0;i<(size/2);i++)
   {
      if(index[i]>ic_tollerance)
	{
	  kwlengths[b]=i;
	  b++;
	}
    }
 return(total);
}

/*********************************************/
/* Many of the keylengths calculated in the  */
/* previous function will have been          */
/* multiples of each other. This is to be    */
/* expected - if the keyword is 'KING', then */
/* the extra numbers correspond to keys      */
/* 'KINGKINGKING.....' - valid but           */
/* unneccesary                               */
/*********************************************/
int remove_factors(int total)
{
  int i,j,tally=0,number,b=0;
  int* temp=NULL;
  
  for(i=0;i<total;i++)
    {
      for(j=0;j<total;j++)
	{
	  if(kwlengths[i]%kwlengths[j]==0 && kwlengths[i]!=kwlengths[j])
	    {
	      kwlengths[i]=666;
	    }
	  
	}
    }
  
  for(j=0;j<total;j++)
    {
    if(kwlengths[j]==666)
      tally++;
    }
  
  
  number=total-tally;
  
  temp = new int [number];
  
  for(i=0;i<total;i++)
    {
      if(kwlengths[i]!=666)
	{
	  temp[b]=kwlengths[i];
	  b++;
	}
    }
  delete [] kwlengths;
  kwlengths=temp;
  
  return(number);
}

/***********************************************/
/* This function looks at all of the possible  */
/* keyword lengths, and for each one splits the*/
/* ciphertect up into slices, with each slice  */
/* consisting of letters encoded by the same   */
/* letter of the proposed key. These 'mini     */
/* codes' are then run throught a frequency    */
/* analysis function, using the very reliable  */
/* chi squared statistic to work out the shift.*/
/* At the same time, the corresponding         */
/* key is constructed, and each 'mini code' is */
/* decoded according to the proposed shift.    */
/* the full code is then reconstructed. Finally*/
/* a chi squared analysis is run on the        */
/* proposed plaintext. If the value is below a */
/* certain threshold, indicating a good match  */
/* with english, then the result is output to  */
/* screen/file/wherever needed.                */
/* otherwise, the next key is tried, and so    */
/* on. If no solutions are found, a consoling  */
/* message is output to screen along with some */
/* suggestions ....                            */
/***********************************************/
void analyse(int total)
{
  int i,j,k,a,d;
  int samples;
  int b=0;
  int c=0;
  int shift;
  
  bool answer=false;
  
  char* split = NULL;
  char* decoded = NULL;
  char* keyword = NULL;

  cout<<endl<<endl;
  for(i=0;i<total;i++)
    {
	  samples = size/kwlengths[i];

	  split = new char[samples];
	  decoded=new char[size];
	  keyword=new char[size/2];
          decoded_slice = new char[samples];
      
	  for(k=0;k<kwlengths[i];k++)
	    {
	      for(j=k;j<size;j+=kwlengths[i])
		{
		  split[b]=code[j];
		  b++;
		}
	      shift=frequency_analyse(samples,split);
	      decode(shift,samples,split);
	      shift+=65;
	      keyword[k]=static_cast<char>(shift);
                 
	      for(a=k;a<size;a+=kwlengths[i])
	      {
		  decoded[a]=decoded_slice[c];
		  c++; 
	      }
	      b=0;
	      c=0;
	    }

          shift=frequency_analyse(size,decoded);
	 
	  if(final_check<=chi_tollerance)
	    {
   	      answer=true;
	      cout<<"Keyword: ";
	      for(d=0;d<kwlengths[i];d++)
		{
		  cout<<keyword[d];
		}
	      cout<<endl<<endl<<"Plaintext: "<<endl;
	      for(d=0;d<size;d++)
		{
		  cout<<decoded[d];
		}
	    } 
	  cout<<endl;
	   
    }
  
  if(answer==false)
    {
      cout<<"No possible solutions found.\n"<<endl;
      cout<<"Is the plaintext in English?"<<endl;
      cout<<"Try tweaking the default settings...."<<endl;
    }
  
  return;  
}

/********************************************************/
/* This function takes the text, and its length, passed */
/* to it by the calling function, and performs          */
/* frequency analysis on it using the 'chi_squared'     */
/* function to find the most likely shift.              */
/********************************************************/
int frequency_analyse(int size,char code[])
{
  float frequency[26];
  int i,x;
  int shift;
  
  for(i=0;i<26;i++)        
    frequency[i]=0;
  
  for(i=0;i<size;i++)
    {     
      code[i]=toupper(code[i]);
      x=static_cast<int>(code[i]);
      x=x-65;
      
      frequency[x]++;
    }
 
  shift=chi_squared(size,frequency);
  return(shift);
}

/***********************************************/
/* Here is the core of the frequency analysis  */
/* - the chi squared statistic is used to      */
/* find the shift of any text passed, by       */
/* it to the array containing standard english */
/* frequencies (for this reason, at the moment.*/
/* the program will only decode english        */
/* plaintext                                   */
/***********************************************/
int chi_squared(int size,float tally[])
{
  float english_frequency[26]={8.15,1.37,2.21,4.58,12.51,
                               1.86,2.36,6.85,6.97,0.14,
			       1.07,4.37,1.96,6.52,7.58,
			       1.40,0.19,5.02,6.05,9.93,
			       3.22,0.78,2.49,0.13,2.11,
			       0.07};                                 
  int i,j;
  float chi_values[26];
  float x;
  
  int shift,tmp,index=0;
  
  cout.precision(3);
  
  for(i=0;i<26;i++)
    {
      chi_values[i]=0;
      english_frequency[i]=(english_frequency[i]/100)*size;
    }
  
  for(i=0;i<26;i++)
    {
      for(j=0;j<26;j++)
	{
	  x=pow( (tally[(j+i)%26]-english_frequency[j%26] ), 2 );
	  chi_values[i]+= x/(english_frequency[j%27]);
	}   
    }
  final_check = chi_values[0];
  shift = index;
  
  for (tmp = index; tmp <26; tmp++)
    {
      if (chi_values[tmp] < chi_values[shift])
	shift = tmp;
    }
  return(shift); 
}

/*****************************************************/
/* Deceptively simple, this function does the actual */
/* decoding, taking as input the text to be decoded  */
/* and the amount by which it has been shifted.      */
/* It only deals with uppercase, which is why any    */
/* inputed code is first transformed to uppercase    */
/* in the input function (lowercase could have been  */
/* used, but whichever, consistency was needed!      */
/*****************************************************/
void decode(int shift,int size,char code[])
{
  int i,tmp;
  for(i=0;i<size;i++)
    {
      tmp=static_cast<int>(code[i])-64;
      if((tmp-shift)>0)
	tmp=(tmp-shift);
      
      else
	tmp=26+(tmp-shift);
      
      tmp+=64;
      
      decoded_slice[i]=static_cast<char>(tmp);
    }
}