/*
  Questo programma fa parte di una libreria messa a disposizione dei
  lettori del libro
  Alessandro Languasco & Alessandro Zaccagnini,
  Introduzione alla Crittografia, Ulrico Hoepli Editore, Milano, 2004.

  Ricerca di pattern in un testo,
  Didascalia della Figura 5.3, Paragrafo 5.3
*/

#include <iostream>
#include <string.h>

static const
unsigned MAX_DIV = 61;

static const
unsigned alpha = 26;

bool divisori[MAX_DIV];

/*
  Questa funzione esamina gli interi "n" da 1 a "MAX_DIV - 1" ed
  elimina quelli per cui il testo dato nel corpo del programma
  presenta una ripetizione ad una distanza di "n" o di un suo
  divisore.
  Lo scopo è quello di fornire a chi deve crittografare il testo dato
  le lunghezze delle chiavi che permettono di evitare la presenza di
  pattern significative nel testo cifrato, nascondendo eventuali
  "debolezze" del testo da cifrare.
*/
void
elimina_divisori(unsigned n) {

  for(unsigned i = 1; i < MAX_DIV; i++)
    if(!divisori[i])
      if(n % i == 0)
	divisori[i] = true;
}

/*
  Questa funzione ricerca le occorrenze di "pattern" all'interno del
  testo "plaintext", cioè di occorrenze ripetute di gruppi di
  caratteri vicini (non necessariamente adiacenti).
  "pattern" è una stringa di caratteri con il seguente significato:
  - "x" sta per "carattere uguale in entrambe le sotto-stringhe del
    messaggio";
  - qualunque altro carattere sta per "non importa".
  Per esempio se "pattern" = "xxx" vuol dire che si stanno cercando
  le occorrenze multiple di 3 caratteri consecutivi, mentre se
  "pattern" = "x.x" vuol dire che si cercano le occorrenze multiple di
  coppie di caratteri uguali intercalate da caratteri (eventualmente)
  diversi.
*/
void
search_pattern(std::string& plaintext, std::string& pattern) {

  unsigned str_len = plaintext.length();
  unsigned pat_len = pattern.length();
  unsigned matches = 0;

  // Conta il numero di "x" in "pattern"
  for(unsigned i = 0; i < pat_len; i++)
    if (pattern[i] == 'x')
      matches++;
  std::cout << "Pattern: " << pattern;
  std::cout << "   Lunghezza testo: " << str_len;
  std::cout << "   Lunghezza pattern: " << pat_len << std::endl;
  for(unsigned i = 0; i < str_len - pat_len; ++i)
    for (unsigned j = i + 1; j < str_len - pat_len; ++j) {
      unsigned m = 0;
      for(unsigned n = 0; n < pat_len; ++n) {
	if(pattern[n] == 'x' && plaintext[i + n] == plaintext[j + n])
	  m++;
      }
      if(m == matches) {
	// Se si entra qui, allora c'è un'occorrenza multipla: stampa
	// i due frammenti di testo corrispondenti
	for(unsigned m = 0; m < pat_len; ++m)
	  std::cout << plaintext[i + m];
	std::cout << " -- ";
	for(unsigned m = 0; m < pat_len; ++m)
	  std::cout << plaintext[j + m];
	std::cout << ":  Inizio primo: " << i;
	std::cout << "   Inizio secondo: " << j;
	std::cout << "   Distanza: " << j - i << std::endl;
	elimina_divisori(j - i);
      }
    }
}

/*
  Ricerca i "poligrafi", cioè occorrenze di "k" caratteri consecutivi
  uguali nel testo "plaintext".
  Lo stesso risultato si può ottenere chiamando la funzione
  "search_pattern()" dove l'argomento "pattern" è una stringa di "k"
  caratteri "x".
*/
void
polygraphs(std::string& plaintext, unsigned k) {

  unsigned len = plaintext.length();
  std::cout << "Lunghezza del testo: " << len;
  std::cout << "   Lunghezza del poligrafo: " << k << std::endl;
  for(unsigned i = 0; i < len - k; i++)
    for (unsigned j = i + 1; j < len - k; j++) {
      unsigned n = 0;
      while((plaintext[i + n] == plaintext[j + n]) && n < k)
	n++;
      if(n == k) {
	for(unsigned m = 0; m < k; m++)
	  std::cout << plaintext[i + m];
	std::cout << ":  Inizio primo: " << i;
	std::cout << "   Inizio secondo: " << j;
	std::cout << "   Distanza: " << j - i << std::endl;
	elimina_divisori(j - i);
      }
  }
}

/*
  Questa funzione determina una certa quantità di dati statistici
  relativi al testo passato come parametro.
  Eseguire SOLO su testi che non contengono spazi!
*/
void
statistica(std::string text) {

  long unsigned len = text.length();
  std::cout << "Lunghezza del testo: " << len << std::endl;

  long unsigned conta_caratteri[alpha] = {0 * alpha};
  for (unsigned i = 0; i < len; ++i)
    ++conta_caratteri[text[i] - 'a'];
  for (unsigned i = 0; i < alpha; ++i)
    std::cout << char('a' + i) << " " << conta_caratteri[i] << std::endl;

  long unsigned conta_digrafi[alpha][alpha] = {0};
  for (unsigned i = 0; i < len - 1; ++i) {
    long unsigned pc = text[i] - 'a';
    long unsigned sc = text[i + 1] - 'a';
    ++conta_digrafi[pc][sc];
  }
  for (unsigned i = 0; i < alpha; ++i) {
    for (unsigned j = 0; j < alpha; ++j)
      if (conta_digrafi[i][j] > 0) {
	std::cout << char('a' + i) << char('a' + j) << " ";
	std::cout << conta_digrafi[i][j] << " ";
      }
    std::cout << std::endl;
  }

  long unsigned conta_trigrafi[alpha][alpha][alpha] = {0};
  for (unsigned i = 0; i < len - 2; ++i) {
    long unsigned pc = text[i] - 'a';
    long unsigned sc = text[i + 1] - 'a';
    long unsigned tc = text[i + 2] - 'a';
    ++conta_trigrafi[pc][sc][tc];
  }
  for (unsigned i = 0; i < alpha; ++i) {
    for (unsigned j = 0; j < alpha; ++j)
      for (unsigned k = 0; k < alpha; ++k)
	if (conta_trigrafi[i][j][k] > 0) {
	  std::cout << char('a' + i) << char('a' + j) << char('a' + k);
	  std::cout << " " << conta_trigrafi[i][j][k] << " ";
	}
    std::cout << std::endl;
  }
}

int
main() {
  std::string plaintext="la presenza di digrafi rivela la lunghezza della chiave.";

  polygraphs(plaintext,2);
  polygraphs(plaintext,3);
  polygraphs(plaintext,4);

  std::cout << "Lunghezze della chiave adatte per il plaintext corrente: ";
  std::cout << std::endl;
  for (unsigned i = 1; i < MAX_DIV; i++)
    if(!divisori[i])
      std::cout << i << "  ";
  std::cout << std::endl;

  statistica(plaintext);

//   std::string pattern = "xxx";
//   search_pattern(plaintext, pattern);
//   pattern = "x*x";
//   search_pattern(plaintext, pattern);
//   pattern = "xx*x";
//   search_pattern(plaintext, pattern);
//   pattern = "x**x";
//   search_pattern(plaintext, pattern);
//   pattern = "x*xx";
//   search_pattern(plaintext, pattern);
//   pattern = "xxxx";
//   search_pattern(plaintext, pattern);
//   pattern = "x***x";
//   search_pattern(plaintext, pattern);
//   pattern = "x****x";
//   search_pattern(plaintext, pattern);
//   pattern = "x*a***x";
//   search_pattern(plaintext, pattern);

  std::cout << "Lunghezze della chiave adatte per il plaintext corrente: ";
  std::cout << std::endl;
  for (unsigned i = 1; i < MAX_DIV; i++)
    if(!divisori[i])
      std::cout << i << "  ";
  std::cout << std::endl;
}