//======================
// XXXXXXXXXXXX 
// XXXXXXXXXXXX Written by a Former CMSC 443 Student
// Kasiski's Method   
// Project 1         
// CMSC 443 
//======================

// This program runs at an O(n^2).  It is inefficient, but on the small
// amount of ciphertext given to us to decipher, it is applicable.

// Everything is written in void functions, which is also inefficient, but
// all operations are implemented.  It does have redundancies.  For instance,
// if a 4-long run is located, it will be listed twice, in two 3-long runs.

// Also, if a sequence appears more than once, it will appear more than once
// in the output.  In fact, for 1 instance of repetition, 1  list
// of possible divisors is output.  For 2 instances of repeated ciphertext
// 3 are shown. For 3, 6 will be shown.  This program assumes that a
// particular sequence will appear more than 3 times.  It will work for those
// appearances numbering above 3, but it will be overly redundant and
// therefore difficult to sift through.
// Compile using CC..e.g. IF you have named this .C file kasis.C then
// use CC kasis.C -o kasis
// kasis 'name of file containing ciphertext'
// begin 

#include <iostream.h>         // for cout, cin
#include <stdio.h>            // for fscanf, fopen, fclose
#include <string.h>           // for strlen
#include <stdlib.h>           // for exit


#define LEN 300               // the maximum length of the ciphertext


void goto_menu();	      // The options routine
void output_cipher(char *);   // output ciphertext (C)
void run_kasiski(char *);     // The main Kasiski loop (k(C))
void prime_factors(int);      // outputs the prime factors of (int)
int is_prime(int);            // boolean test for prime
int find_most_active();       // finds most common prime as a prime factor


// global file pointer
FILE *fp;	              // global so both MAIN and GOTO_MENU have access.
int primes[300];              // keeps track of the # of times a prime arises.


//----------------------------------------------------------------------------
// MAIN
// this function deals with the initialization of files, by opening the one
// sent it for input.  Then it calls the menu GOTO_MENU().  It closes the
// input file and outputs an exit message on output.

void main (int argc,char **argv)
{
	char input_file[13];
        int i;
       
        for (i=0;i<LEN;i++)  // clear primes count
          primes[i] = 0;

	// check for proper usage of program or return error 
	if (argc < 2) {
		cout << "USAGE: " << argv[0] << " file" << endl;
		exit(1);
	}
	else
		strcpy(input_file,argv[1]);

	fp = fopen(input_file,"r");
	cout << "Kasiski's Method" << endl;

	goto_menu();          // call the menu subroutine

	cout << endl << endl << "end Kasiski's Method." << endl;

	fclose(fp);

} // end MAIN()


//----------------------------------------------------------------------------
// GOTO_MENU()
// this function reads in the data into a string called 's' and then runs a
// while loop, thus imitating a menu.  It ends on an input of 3.

void goto_menu()
{
	int choice;  // menu choice
	char s[LEN]; // ciphertext
	int i;

	// read data from input file
	i=0;
	while (!feof(fp))
	  fscanf(fp,"%c", &s[i++]); // input one character at a time
	s[--i] = '\0';		    // then add EOS to prevent overflow of data

	// main control loop -- continue until quit

        choice = 1;
	while ((choice == 1) || (choice == 2)) {
	  cout << endl << "1) Output ciphertext." << endl;
	  cout << "2) Run Kasiski's Method on ciphertext." << endl;
	  cout << "3) Quit." << endl;

		cin >> choice;

		cout << endl;

		if (choice == 1)
			output_cipher(s);
		if (choice == 2)
			run_kasiski(s);
	}
}


//----------------------------------------------------------------------------
// OUTPUT_CIPHER()
// this function outputs the ciphertext by means of a for loop.  It outputs
// one character at a time, in case spaces are included in the ciphertext.

void output_cipher(char *s)
{
	int i;

	for (i=0;i<strlen(s);i++)   // output one character at a time
		cout << s[i];
	cout << endl;		    // then endline
}


//----------------------------------------------------------------------------
// RUN_KASISKI()
// this function actually implements Kasiski's method.  It copies 3 characters
// into a string called 'store' and checks the values against a 'dummy' string.
// If they match, then 2+ occurrences have arisen.  It will output some more
// than once, if they show up more than twice.

void run_kasiski(char *s)
{
	char store[4]; 	  // only holds for cases of 3 length (string 1)
	char dummy[4];	  // (string 2)
	int i;		  // counter for string searched
	int j;	       	  // counter for search routine

	// take first 3 and compare them with all other combos.
	i=0;

	for (i=0;i<strlen(s);i++) {	 // loop keeps track of string 1 (i)
		store[0] = s[i];	 // copy 3 characters to check
		store[1] = s[i+1];
		store[2] = s[i+2];
		store[3] = '\0';
		for (j=i+1;j<strlen(s);j++) { //loop keeps track of string 2(j)
		  dummy[0] = s[j];            // copy 3 characters to check
		  dummy[1] = s[j+1];
		  dummy[2] = s[j+2];
		  dummy[3] = '\0';
		  if (!strcmp(dummy,store)) { // test the two, if match, output
                                              // it, else continue
		     cout << "match of " << dummy << " with a distance of "
                          << j-i << " with prime factors of: ";
		     prime_factors(j-i);
		  } // match loop
		} // string 2 loop (i)
	} // string 1 loop (j)

        cout << endl<< "The most commonly occuring prime factor is " << 
                find_most_active() << endl;

} // end RUN_KASISKI()


//----------------------------------------------------------------------------
// PRIME_FACTORS()
// runs a loop (i) to half of a, checking for primes.  If it finds one,
// it outputs it.

void prime_factors(int a)
{
  int i;

  for (i=2;i<=a;i++)
    if ((a % i == 0) && (is_prime(i))) {  // if i divides a and i is prime
      cout << i << " ";                   // output i
      primes[i]++;                        // then update prime occurrences
    }
  cout << endl;

} // end PRIME_FACTORS()


//-----------------------------------------------------------------------------
// IS_PRIME()
// A boolean check for primes.  This function returns a 1 if the input is
// prime, and a 0 if the input is not prime.  It runs up to half of the number
// and checks for a mod of 0 (division check).

int is_prime (int a)
{
  int half = a/2;  // only run to half of input
  int i;

  for (i=2;i<=half;i++)
    if (a % i == 0) // check for a mod of 0
      return (0);   // if an integer 2+ divides it, it is not prime (0)

  return (1);       // if no integer divides it, it is prime (1)

}  // end IS_PRIME()


//-----------------------------------------------------------------------------
// FIND_MOST_ACTIVE()
// Finds the prime factor that showed up the most as an indication of the
// possible keylength.

int find_most_active()
{
  int i;
  int most = 0;

  for (i=0;i<LEN;i++)
    if (primes[i] > primes[most]) // if the current prime showed up more often
                                  // than the most common prime, mcp = current
      most = i;

  return (most);

}  // end FIND_MOST_ACTIVE()


// end KASISKI.C==============================================================