/*
  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;

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);
      }
  }
}

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;

  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;
}