#include <stdio.h>
#include <stdlib.h>
#include <getopt.h>
#include <string.h>

void vigenere_enc(char *in, char *out, const char*key, const int key_len);
void vigenere_dec(char *in, char *out, const char*key, const int key_len);
char plus(char a, char b);
char minus(char a, char b);
char inv(char a);
int filter_char(char *c);

int try_key(int i, char* key, int key_len, char* w_text);

void help_and_exit(int ret);

char exp_c = 'e';		//carattere più probabile
int top_cs = 3;			//numero di caratteri più frequenti considerati
int max_key = 30;		//lunghezza massima delle chiavi considerate
int max_text = 2048;	//limite massimo del testo

int flag_shortcut = 1;	//Termina la ricerca alla prima occorrenza di un elemento di test_str[]


char** test_str;		//stringhe da ricercare nelle decifrazioni
int	test_str_len;		//lunghezza del vettore test_str

char* in_text;			//testo in ingresso

char** hints;			//caratteri più probabili per la chiave

FILE* out;				//output stream

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

	FILE* in = NULL;
	out = NULL;
	
	// LETTURA ARGOMENTI	
	while (1){
		static struct option long_options[] = {
			{"help",		no_argument,		0, 'h'},
			{"in",  		required_argument,	0, 'i'},
			{"out",  		required_argument, 	0, 'o'},
			{"most-freq",	required_argument, 	0, 'm'},
			{"top-freq",	required_argument, 	0, 'q'},
			{"key-size",	required_argument, 	0, 'k'},
			{"text-size",	required_argument, 	0, 't'},
			{"find-first",	no_argument,		0, '1'},
			{"find-all",	no_argument,		0, 'a'},
			{0, 0, 0, 0}
		};
		int option_index = 0;
		int c = getopt_long_only (argc, argv, "hi:o:m:q:k:ta1",long_options, &option_index);
		if (c == -1)
			break;
		switch (c) {
			case 'h':
				help_and_exit(0);
				break;
			case 'i':
				if(in != NULL) fclose(in);
				in = fopen(optarg, "r");
				if(in == NULL) 
					fprintf(stderr, "impossibile accedere in lettura al file '%s'.\n", optarg);
				break;
			case 'o':
				if(out != NULL) fclose(out);
				out = fopen(optarg, "w");
				if(out == NULL) 
					fprintf(stderr, "impossibile accedere in scrittura al file '%s'.\n", optarg);
				break;
			case 'm':
				exp_c = *optarg;
				break;
			case 'q':
				top_cs = atoi(optarg);
				break;
			case 't':
				max_text = atoi(optarg);
				break;
			case 'k':
				max_key = atoi(optarg);
				break;
			case 'a':
				flag_shortcut = 0;
				break;
			case '1':
				flag_shortcut = 1;
				break;
			case '?':
				break;
			default:
				help_and_exit(1);
		}
	}
	// CONTROLLO DEI PARAMETRI
	if(max_key < 1){
		fprintf(stderr,	"--key-size (-k) richiede un argomento un naturale maggiore di 0.\n");
		help_and_exit(1);}
	if(max_text < 1){
		fprintf(stderr,	"--text-size (-t) richiede un argomento un naturale maggiore di 0.\n");
		help_and_exit(1);}
	if(exp_c < 'a' || exp_c > 'z'){
		fprintf(stderr, "--most-freq (-m) richiede come argomento una lettera minuscola.\n");	
		help_and_exit(1);}
	if(top_cs < 1 || top_cs > 26) {
		fprintf(stderr, "--top-freq (-q) richiede come argomento un naturale tra 1 e 26.\n");
		help_and_exit(1);}
	// FINE CONTROLLO
	
	/* i restanti argomenti sono le parole da ricercare nei testi decifrati per
	 * automatizzarne il riconoscimento. */
	if((test_str_len = argc - optind ) > 0)
		test_str = argv + optind;
	
	/* se non specificato diversamente lavora su I/O standard 
	 * è possibile modificare input e output mediante i parametri --in --out */
	if(in == NULL) in = stdin;
	if(out == NULL) out = stdout;
	
	/* alloca e ripulisce spazio per max_text caratteri.
	 * in_text conterrà il testo da decifrare
	 * è possibile modificare il valore di max_text mediante --text-size. */
	in_text = (char*)malloc(max_text);
	memset(in_text, '\0', max_text);
	
	//leggi testo e best_align	
	char c;		//um pò di variabili ausiliarie
	int i,j,k;	
	
	/* La tecnica del miglior allineamento consente di ottenere informazioni 
	 * sulla lunghezza della chiave.
	 *  
	 * for(int i = 0; i < lunghezza_testo - scostamento; i++)
	 *    corrispondenze += testo[i] == testo[i + scostamento];
	 *
	 * La dimensione della chiave è un sottomultiplo del minor scostamento che
	 * massimizza il numero di corrispondenze tra testo originale e scostato
	 */
	 
	//lunghezza del testo letto. inizialmente 0, incrementata a ogni carattere
	int text_len = 0;	
	//lunghezza della chiave. calcolata mediante miglior allineamento
	int key_len = 0; 
	// un contatore delle corrispondenze per ogni scostamento da 1 fino a max_key
	int* matches = (int*)malloc((++max_key)*sizeof(int)); 
	// azzera i contatori
	for(i = 0;i<max_key;i++) matches[i] = 0;
	
	// legge e filtra il testo in ingresso calcolando il miglior allineamento
	while((c = fgetc(in)) != EOF && text_len < max_text - 1)		
		// i caratteri non alfabetici sono ignorati e quelli maiuscoli ridotti
		if(filter_char(&c)){
			// copia il carattere letto
			in_text[text_len++] = c;
			/* Controlla rispetto a quali scostamenti il carattere appena letto
			 * comporti una corrispondenza e incrementa il contatore relativo a
			 * tale scostamento 
			 * durante la lettura dei primi max_key caratteri non è possibile
			 * controlalre tutti gli scostamenti da 1 a max_key, ma solo
			 * quelli da 1 a text_len
			 * m è il minimo tra max_key e text_len */
			int m = (max_key > text_len) ? text_len : max_key;
			for( i = 1;i < m ;i++)
				matches[i] += in_text[text_len-i-1] == c;
		}
	
	// L'indice di matches contenente il valore massimo è lo scostamento migliore
	for( i = 1;i<max_key;i++)
		if(matches[i] > matches[key_len]) key_len = i;
	
	/* Determinata la possibile (le possibili) lunghezza della chiave si procede
	 * considerando separatamente i vari cifrari mono-alfabetici utilizzati.
	 * Questi non sono forzati singolarmente per forza bruta, ma si utilizza la
	 * statistica linguistica per ridurre il numero di chiavi da provare.
	 * Tale tecnica si basa sull'assunto che nel testo in chiaro vi siano 
	 * dei caratteri più frequenti di altri.
	 * La cifratura mono alfabetica, cambia il simbolo, ma mantiene le frequenze
	 * Se la 'i' è la più frequente nel testo in chiaro e viene cifrata in 'z',
	 * allora 'z' sarà la più frequente nel testo cifrato.
     * L'osservazione coinvolge il testo in chiaro, ma è generalmente valida:
	 * si utilizzano le probabilità dei vari caratteri rispetto alla lingua in 
	 * in cui sospettiamo sia scritto il testo.
	 * Trattandosi di un metodo statistico la corrispondenza tra carattere più
	 * probabile nella lingua e la sua frequenza nel caso particolare di un singolo
	 * testo non è esatta.
	 * Tuttavia, è molto probabile che tale carattere sia tra i più frequenti.
	 * Pertanto si considerano un certo numero di caratteri più frequenti nel 
	 * testo ottenendo più di una chiave da provare, ma sicuramente meno di 
	 * tutte quelle possibili.
	 * Il numero di caratteri più frequenti da considerare è specificato da top_cs,
	 * mentre exp_c contiene il carattere atteso.
	 * La matrice hints conterrà, per ogni cifrario mono alfabetico (ovvero key_len)
	 * top_cs suggerimenti per la decodifica.
	 */
	 
	hints = (char**)malloc(key_len*sizeof(char*));	
	int a[26];	// un contatore per ogni carattere dell'alfabeto
	int max;	// ausiliaria per trovare i massimi in a[]
	for( i = 0;i < key_len;i++){
		// alloca lo spazio per top_cs suggerimenti per il cifrario i-esimo
		hints[i] = malloc(top_cs);
		// azzera i contatori
		for( j = 0; j < 26; j++) a[j] = 0;
		//conta le istanze dei caratteri nelle posizioni i+n*key_len
		for( j = i; j < text_len; j += key_len) a[in_text[j]-97]++;
		//trova quelli più frequenti
		for( k = 0 ; k < top_cs; k++){
			max = 0;
			for( j = 0; j < 26; j++)
				if(a[j] > a[max])
					max = j;
			hints[i][k] = max+97;
			a[max] = -1;
		}
	}
	
	for( i = 0;i < key_len;i++)
		for( j = 0; j < top_cs; j++)
			/* calcola il carattere che servirebbe per cifrare exp_c in hints[i][j]
			 * se exp_c = 'e' = 101 e hints[i][j] = 'g' = 103 allora 'e' + 'c' = 'g'
			 * e hints[i][j] diventa 'c' = 99 */
			hints[i][j] = minus(hints[i][j],exp_c);
			
	/* Prova ricorsivamente le combinazioni dei suggerimenti contenuti in hints.
	 * Per ogni chiave generata tenta la decifrazione del testo.
	 * Se sono specificate delle parole da ricercare nel testo decifrato produce
	 * in output solo quelli che ne contengono almeno una. */
	try_key(0, malloc(key_len), key_len, malloc(text_len));
		
	exit(0);
}

int try_key(int i, char* key, int key_len, char* w_text){
	/* i contiene la profondità della chiamata, e corrisponde alla porzione
	 * della chiave che è già stata generata.
	 * key è il vettore contenente la chiave che si sta generando; è utilizzato 
	 * come uno stack.
	 * key_len è la lunghezza della chiave
	 * w_text è un vettore di caratteri da utilizzarsi per la decifirazione;
	 * è condiviso tra le varie chiamate (come key) ma la loro sequenzialità 
	 * esclude conflitti. */
	int j, k;
	if(i < key_len)
		/* La chiave non è stata generata completamente
		 * Prova iterativamente ogni suggerimento per il carattere i-esimo della
		 * chiave.
		 * Qualora la ricerca non debba esser esaustiva, e una chiave abbia 
		 * prodotto una soluzione positiva, termina l'esplorazione restituendo 1
		 * In questo modo anche i chiamanti termineranno l'esplorazione.*/
		for(j = 0;j < top_cs;j++){
			key[i] = hints[i][j];
			if(try_key(i+1, key, key_len, w_text) && flag_shortcut)
				return 1;
		}
	else{
		// key contiene una chiave completa, tenta la decifrazione
		vigenere_dec(in_text, w_text, key, key_len);
		/* cerca occorrenze delle parole sentinella (test_str) nel testo decifrato
		 * se ve ne è almeno una stampa la soluzione e comunica il risultato 
		 * positivo al chiamante restituendo 1 */
		for(j = 0;j < test_str_len; j++)
			if(strstr(w_text, test_str[j]) != NULL){
				fprintf(out, "CHIAVE: %s\n%s\n", key, w_text);
				return 1;
			}
		// Se non sono specificate parole da ricercare stampa ogni soluzione
		if(test_str_len == 0)
			fprintf(out, "CHIAVE: %s\n%s\n", key, w_text);
	}
	return 0;
}

/* Somma, sottrazione e inverso di caratteri a-z
 * Visti come elementi 0-25 implementa operazioni modulo 26
 * 'c' + 'x' = 3 + 23 = 26 mod 26 = 0  = 'a' = 97
 * 'c' - 'x' = 3 - 23 = 20 mod 26 = 20 = 'u' = 117
 * -'c' = -3 = 0-3 mod 26 = 23 = 'x' =  120
 * Il tutto è allineato all'intervallo 97-122 del codice ASCII*/
char plus(char a, char b){
	return (a- 97 + b -97) % 26 + 97;
}
char minus(char a, char b){
	return (a - b + 26) % 26 + 97;
}
char inv(char a){
	return minus('a',a);
}

/* Resituisce 1 se il contenuto di c è una lettera, altrimenti 0;
 * qualora questa sia maiuscola la converte in minuscolo */
int filter_char(char *c){
	if(*c >= 97 && *c <= 122)
		// c è nell'intervallo a-z
		return 1;
	else if(*c >= 65 && *c <= 90){
		// c è nell'intervallo A-Z, va convertito in minuscolo
		*c = *c + 32;
		return 1;
	}else
		// gli altri caratteri vengono ignorati
		return 0;
}

/* Codifica usando il cifrario di vigenére.
 * in è il testo in ingresso e out punta alla locazione ove scrivere il
 * testo cifrato.
 * key punta alla chiave e key_len è la sua lunghezza */
void vigenere_enc(char *in, char *out, const char*key, const int key_len){
	int key_i = 0;
	while(*in != '\0'){
		*out = plus(*in,key[key_i]);
		in++; out++;
		key_i = ++key_i % key_len; 
	}	
}

/* Decodifica usando il cifrario di vigenére.
 * in è il testo in ingresso e out punta alla locazione ove scrivere il
 * testo decifrato.
 * key punta alla chiave e key_len è la sua lunghezza.
 * La decifrazione avviene cifrando il testo con l'inversa della chiave */
void vigenere_dec(char *in, char *out, const char*key, const int key_len){
	char* inv_key = malloc(key_len);
	int i;
	for(i=0;i<key_len;i++)
		inv_key[i] = inv(key[i]);
	vigenere_enc(in,out,inv_key,key_len);
	free(inv_key);	
}

void help_and_exit(int ret){
	printf("Utilizzo: atk [opzioni] [parole]\n");
	printf("  - [parole] è una lista di parole da ricercarsi nel testo forzato al fine\n");
	printf("    di automatizzare il riconoscimento dei casi positivi.\n");
	printf("    Le parole devono essere in minuscolo e separate da spazi.\n");
	printf("Opzioni:\n");
	printf("  --in <file>\t\t(-i) File di input, se omesso utilizza stdin\n");
	printf("  --out <file>\t\t(-o) File di output, se omesso utilizza stdout\n");
	printf("  --key-size <int>\t(-k) Dimensione massima delle chiavi considerate\n");
	printf("  --text-size <int>\t(-t) Lunghezza massima del testo letto\n");
	printf("  --most-freq <char>\t(-m) Carattere più probabile nel testo in chiaro\n");
	printf("  --top-freq <char>\t(-q) Numero di caratteri più frequenti considerati\n");
	printf("  --help\t\t(-h) Visualizza questo messaggio\n");
	printf("  --find-first\t\t(-1) Se [parole] contiene almeno un elemento, termina la\n");
	printf("              \t\t     ricerca al primo caso positivo\n");
	printf("  --find-all\t\t(-a) Prova tutte le chiavi suggerite.\n");
	exit(ret);
}