/*

Doppia cifratura (IOI 2001)
Copyright (C) 2001 Alessandro Maconi

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA


(Come per tutti i problemi del 2001, è utile leggere il libretto distribuito
dagli organizzatori, e disponibile nella sezione "Materiale didattico" della
home page http://ioi.dsi.unimi.it/.)

Questa soluzione calcola prima tutti i testi in cifra possibili con la prima
chiave, li inserisce in una tabella di hashing, e quindi tenta tutti i testi
in cifra possibili con la seconda chiave, cercando ciascuno di essi nella
tabella.

*/


#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <stdio.h>
#include "aeslibc.h" /* per utilizzare le funzioni fornite per cifrare e decifrare */
#define LNG 20 /* lunghezza max nome del file (potrebbe essere 13, ma meglio abbondare) */
#define NF 10
#define MX 250000 /* dimensione tabella di hash */

typedef struct str
{
  HexStr ris;
  char key[6];
  struct str *next;
}str;

int nbit;                           /* num di cifre su cui lavorare */
HexStr chiaro,cifrata,tmp,key;     /* le due stringhe su cui lavorare  */
Block  bch,bcr,btmp,bkey;           /* x lavorare bisogna utilizzare le chiavi codificate */
char chiave[6];

void conv(int x);                   /* converte il numero passato come argomento nella chiave da utilizzare */
int hash(char *stringa);

str *z;

int main()
{
  int i,j;
  FILE *fin,*fout;
  char nomef[LNG];                    /* per tenere il nome del file su cui si sta lavorando */
  str **table;                        /* tabella di hash */
  str *aux;
  int lungh;                          /* num chiavi possibili */
  int ind;

  z=(str*)malloc(sizeof(str));
  z->next=z;
  strcpy(z->ris,"");
  strcpy(z->key,"");

  for(i=0;i<=NF;i++) /* lavoriamo su 10 file con nomi da 1 a 10 */
    {
      table=(str**)calloc(MX,sizeof(str*));
      
      for(j=0;j<MX;j++)
	{
	  table[j]=(str*)malloc(sizeof(str));
	  table[j]->next=z;
	}
      
      sprintf(nomef,"double%d.in",i);
      fin=fopen(nomef,"r");
      fscanf(fin,"%d",&nbit);
      fscanf(fin,"%s",chiaro);
      fscanf(fin,"%s",cifrata);
      hexstr2block(chiaro,bch);
      hexstr2block(cifrata,bcr);
      lungh=(long)powl(16,nbit);
            
      for(j=0;j<lungh;j++)                      /* cifriamo con tutte le chiavi possibili la stringa in chiaro */
	{                                       /* e salviamo il risultato nella tabella di hash   */
	  conv(j);
	  hexstr2block(key,bkey);
	  encrypt(bch,bkey,btmp);
	  block2hexstr(btmp,tmp);
	  ind=hash(tmp);
	  for(aux=table[ind];aux->next!=z;aux=aux->next);
	  aux->next=(str*)malloc(sizeof(str));
	  aux->next->next=z;
	  strcpy(aux->next->key,chiave);
	  strcpy(aux->next->ris,tmp);
	}
      
      for(j=0;j<lungh;j++)                    /* decifriamo la stringa cifrata e cerchiamo se abbiamo gia' */
	{                                     /* ottenuto un risultato uguale */
	  conv(j);
	  hexstr2block(key,bkey);
	  decrypt(bcr,bkey,btmp);
	  block2hexstr(btmp,tmp);
	  ind=hash(tmp);
	  for(aux=table[ind]->next;aux!=z;aux=aux->next)
	    if(strcmp(aux->ris,tmp)==0)
	      {
		j=lungh;
		break;
	      }
	}
      printf("Finito file n.%d\n",i);
      sprintf(nomef,"double%d.out",i);
      fout=fopen(nomef,"w");
      fprintf(fout,"#FILE double %d\n",i);
      fprintf(fout,"%s000000000000000000000000000\n",aux->key);
      fprintf(fout,"%s\n",key);
      fclose(fin);
      fclose(fout);
      if(i!=10)
	for(j=0;j<MX;j++)
	  {
	    str *aux2; 
	    for(aux=table[j],aux2=aux->next;aux!=z;aux=aux2,aux2=aux->next)
	      free(aux);
	  }
      free(table);
    }
  return 0;
}

void conv(int x)
{
  int i,n;
  for(i=0;i<5;i++)
    {
      n=x%16;
      x/=16;
      switch(n)
	{
	case 0:
	  chiave[i]='0';
	  break;
	case 1:
	  chiave[i]='1';
	  break;
	case 2:
	  chiave[i]='2';
	  break;
	case 3:
	  chiave[i]='3';
	  break;
	case 4:
	  chiave[i]='4';
	  break;
	case 5:
	  chiave[i]='5';
	  break;
	case 6:
	  chiave[i]='6';
	  break;
	case 7:
	  chiave[i]='7';
	  break;
	case 8:
	  chiave[i]='8';
	  break;
	case 9:
	  chiave[i]='9';
	  break;
	case 10:
	  chiave[i]='A';
	  break;
	case 11:
	  chiave[i]='B';
	  break;
	case 12:
	  chiave[i]='C';
	  break;
	case 13:
	  chiave[i]='D';
	  break;
	case 14:
	  chiave[i]='E';
	  break;
	case 15:
	  chiave[i]='F';
	  break;
	}
    }
  chiave[i]='\0';
  sprintf(key,"%s000000000000000000000000000",chiave);
}


int hash(char *stringa)
{
  int h=0,cst=31;
  while(*stringa)
    {
      h=(h*cst+(*stringa))%MX;
      stringa++;
    }
  return h;
}