mx3r.c

   1 /*
   2         Prueba de concepto de buscador de diferencias por bloques.
   3 */
   4
   5 #include <gcrypt.h>
   6 #include <stdio.h>
   7 #include <stdlib.h>
   8 #include <ctype.h>
   9 #include <string.h>
  10 // Tipos de hashes :
  11 // GCRY_MD_CRC32 - CRC32, sencillo, rápido.
  12 // GCRY_MD_SHA1 - SHA1 potente y seguro.
  13 #define HASH_TYPE GCRY_MD_SHA1
  14
  15
  16 // Establece cual es el ancho máximo de línea para trabajar.
  17 // Establecer como mínimo a 90. Recomendado 128 o 256.
  18 #define MAX_LINE 1024
  19 #define MAX_LOADED_LINES 8096
  20
  21 int block_size=15; // Valor recomendado: SQRT(min_lines).
  22 // Versión 2: Multipasada en cascada: 63,31,15,7,3
  23
  24 unsigned int ihash(char *txt);
  25 unsigned int *hash_loadfile(char *filename, int *size);
  26
  27 typedef struct structhashblock {
  28         int line1;
  29         int line2;
  30         int size;
  31 } hashblock;
  32
  33 int main(int argc, char **argv) {
  34         // Comprobar la entrada de argumentos.
  35         if ( argc < 2 ) {
  36                 fprintf( stderr, "Usage: %s <string>\n", argv[0] );
  37                 fprintf( stderr, "Usage: %s --blr <base-filename> <local-filename> <remote-filename>\n", argv[0] );
  38                 exit( 1 );
  39         }
  40
  41         if (argc > 4 && strcmp(argv[1],"--blr")==0)
  42         {
  43                 int *base_file=NULL, base_file_size=0;
  44                 base_file=hash_loadfile(argv[2],&base_file_size);
  45                 if (!base_file) exit( 0 ); // Error de memoria.
  46                 fprintf( stderr, "Base File: %d lines loaded\n",base_file_size);
  47
  48                 int *local_file=NULL, local_file_size=0;
  49                 local_file=hash_loadfile(argv[3],&local_file_size);
  50                 if (!local_file) exit( 0 ); // Error de memoria.
  51                 fprintf( stderr, "Local File: %d lines loaded\n",local_file_size);
  52
  53                 int *remote_file=NULL, remote_file_size=0;
  54                 remote_file=hash_loadfile(argv[4],&remote_file_size);
  55                 if (!remote_file) exit( 0 ); // Error de memoria.
  56                 fprintf( stderr, "Remote File: %d lines loaded\n",remote_file_size);
  57
  58                 int line_base,line_local,size;
  59                 int maxsize=1,total=0;
  60                 int i,k,m;
  61                 hashblock bloque[64];
  62                 int nbloques=0;
  63                 int lbb=0;
  64                 int conf_pasada[]={256,128,64,32,16,8,4,2,1,0};
  65                 int p;
  66                 int min_bloque=0;
  67                 for (p=0;min_bloque=conf_pasada[p];p++)
  68                 {
  69
  70                         for (i=0;i<base_file_size;i+=maxsize) {
  71                                 maxsize=1;
  72                                 int j;
  73                                 for (j=0;j<nbloques;j++)
  74                                 {
  75                                         if (i>=bloque[j].line1 && i<=bloque[j].line1+bloque[j].size) break;
  76                                 }
  77                                 if (j<nbloques)
  78                                 {
  79                                         i=bloque[j].line1+bloque[j].size; continue;
  80                                 }
  81
  82
  83                                 for (k=0;k<local_file_size;k++)
  84                                 {
  85                                         int j;
  86                                         for (j=0;j<nbloques;j++)
  87                                         {
  88                                                 if (k>=bloque[j].line2 && k<=bloque[j].line2+bloque[j].size) break;
  89                                         }
  90                                         if (j<nbloques)
  91                                         {
  92                                                 k=bloque[j].line2+bloque[j].size; continue;
  93                                         }
  94
  95                                         if (base_file[i]==local_file[k])
  96                                         {
  97                                                 int nz=0,nzbl=0;
  98
  99                                                 for(m=0;k+m<local_file_size && i+m<base_file_size;m++)
 100                                                 {
 101                                                         for (j=0;j<nbloques;j++)
 102                                                         {
 103                                                                 if (k+m>=bloque[j].line2 && k+m<=bloque[j].line2+bloque[j].size) break;
 104                                                                 if (i+m>=bloque[j].line1 && i+m<=bloque[j].line1+bloque[j].size) break;
 105                                                         }
 106                                                         if (j<nbloques) break;
 107                                                         if (base_file[i+m]!=local_file[k+m])
 108                                                         {
 109                                                                 nz++;
 110                                                                 if (nz>size/4) break;
 111                                                                 continue;
 112                                                         }
 113                                                         if (nz==0) size=m;
 114                                                         else
 115                                                         {
 116                                                                 nzbl++;
 117                                                                 if (nzbl>2)
 118                                                                 {
 119                                                                         nzbl=0;
 120                                                                         nz--;
 121                                                                 }
 122
 123                                                         }
 124                                                 }
 125
 126                                                 if (size>maxsize)
 127                                                 {
 128                                                         maxsize=size;
 129                                                         line_base=i;
 130                                                         line_local=k;
 131                                                 }
 132                                         }
 133                                 }
 134
 135                                 if (maxsize>min_bloque)
 136                                 {
 137                                         if (nbloques<64)
 138                                         {
 139                                         bloque[nbloques].line1=line_base;
 140                                         bloque[nbloques].line2=line_local;
 141                                         bloque[nbloques].size=maxsize;
 142                                         nbloques++;
 143                                         } else printf( "Error: OUT OF BLOCKS. \n");
 144
 145
 146                                         printf("%d+%d:%d, ",maxsize,line_base-lbb,line_local-line_base);
 147         //                              printf("BASE  - From: %d .. To: %d\n",line_base,line_base+maxsize);
 148                 //                      printf("LOCAL - From: %d .. To: %d\n",line_local,line_local+maxsize);
 149                                         lbb=line_base+maxsize;
 150                                         total+=maxsize;
 151                                 }
 152
 153                         }
 154
 155                 }
 156                 printf("FIN.\n\n");
 157
 158                 int j;
 159                 {
 160                         hashblock auxbloque[64];
 161                         int minline=0, min_j=0;
 162                         for (p=0;p<nbloques;p++)
 163                         {
 164                                 minline=base_file_size;
 165                                 for (j=0;j<64 && j<nbloques;j++)
 166                                 {
 167                                         if (bloque[j].line1<minline)
 168                                         {
 169                                                 minline=bloque[j].line1;
 170                                                 min_j=j;
 171                                         }
 172                                 }
 173                                 auxbloque[p]=bloque[min_j];
 174                                 bloque[min_j].line1=base_file_size;
 175                         }
 176                         memcpy(bloque,auxbloque,64*sizeof(hashblock));
 177                 }
 178                 lbb=0;
 179                 int l2bb=0;
 180                 int total_huerfanas=base_file_size-total;
 181                 int total_huerfanas2=0;
 182
 183                 for (j=0;j<nbloques;j++)
 184                 {
 185                         total_huerfanas2+=bloque[j].line2-l2bb;
 186                         printf("\t-- %d -> %d lineas huerfanas -- \n",bloque[j].line1-lbb, bloque[j].line2-l2bb);
 187
 188                         printf("BLOQUE %d:  @%d:%d \t--> \t%d:%d  \t(%d:%d)\n", j, bloque[j].line1,bloque[j].line2, bloque[j].line1+bloque[j].size,bloque[j].line2+bloque[j].size,bloque[j].line2-bloque[j].line1,bloque[j].size);
 189
 190                         lbb=bloque[j].line1+bloque[j].size+1;
 191                         l2bb=bloque[j].line2+bloque[j].size+1;
 192                 }
 193                 if (base_file_size!=lbb+1 || local_file_size!=l2bb+1)
 194                 {
 195                         total_huerfanas2+=local_file_size-l2bb-1;
 196                         printf("\t-- %d -> %d lineas huerfanas -- \n",base_file_size-lbb-1, local_file_size-l2bb-1);
 197                 }
 198                 float p100_found=100*total/(float)base_file_size;
 199                 float p100_obsolete=100*(total_huerfanas)/(float)base_file_size;
 200                 float p100_new=100*total_huerfanas2/(float)local_file_size;
 201                 float p100_probability=100-p100_obsolete-p100_new;
 202
 203                 printf("\n\nRESUMEN: %d lineas encontradas en %d bloques (%.2f%% del total)\n",
 204                                                 total,nbloques, p100_found);
 205                 printf("\t(Total: %d lineas huerfanas. %.2f%% del fichero base es obsoleto)\n", total_huerfanas,p100_obsolete);
 206                 printf("\t(Total: %d lineas nuevas. %.2f%% del fichero local es nuevo)\n",total_huerfanas2,p100_new);
 207                 printf(" -- %.2f%% de probabilidad de completar el merge correctamente -- \n",p100_probability);
 208
 209
 210
 211
 212                 free(base_file);
 213                 free(local_file);
 214                 exit( 1 );
 215         }
 216
 217         int i,b;
 218         int nhashes=argc-1;
 219         unsigned int *int_hash=malloc((nhashes)*sizeof(unsigned int));
 220         fprintf( stderr, "nhashes: %d\n",nhashes );
 221         for (i=1;i<argc;i++)
 222         {
 223                 int_hash[i-1]=ihash(argv[i]);
 224         }
 225
 226         for (i=0;i<nhashes-block_size+1;i++)
 227         {
 228                 for (b=0;b<block_size;b++)
 229                 {
 230                         printf( "%08X", int_hash[i+b]);
 231                 }
 232                 printf( "\n");
 233         }
 234         free(int_hash);
 235         return 1;
 236 }
 237
 238 void reducetext(char * txt) {
 239
 240         int n=0, nn=0;
 241         char newline[256];
 242         char lastc=0;
 243         char c=txt[n];
 244         char type=0; // Tipos de palabras o grupos:
 245         // a -> texto, variable.
 246         // 1 -> números, con, sin decimales.
 247         // % -> símbolos unarios, binarios.
 248         // 0 -> huecos y espacios
 249
 250         for (n=0;n<MAX_LINE;n++) {
 251                 c=tolower(txt[n]); // Captura del carácter en minúscula.
 252
 253                 // Traducción del carácter.
 254                 switch(c)
 255                 {
 256                         // Retonos de carro y fin de fichero: salir de la función.
 257                         case 10:
 258                         case 13:
 259                         case 0:
 260                                 n=MAX_LINE; continue;
 261                         // Tabuladores y espacios: cuentan como espacio.
 262                         case ' ':
 263                         case '\t':
 264                                 c=' '; break;
 265                         // Acentos.
 266                         case 'á': c='a'; break;
 267                         case 'é': c='e'; break;
 268                         case 'í': c='i'; break;
 269                         case 'ó': c='o'; break;
 270                         case 'ú': c='u'; break;
 271                 }
 272
 273                 switch(type) // Cambios de tipos según algunos datos.
 274                 {
 275                         case 0: // Segun si estábamos en un espacio.
 276                                 if (c>='0' && c<='9') {
 277                                         type='1';
 278                                 } else if (isalpha(c)) {
 279                                         type='a';
 280                                 } else type='%';
 281                         break;
 282                         case '1': // Segun si estábamos en un espacio.
 283                                 if (c>='0' && c<='9') {
 284                                         type='1';
 285                                 } else if (c=='.') {
 286                                         type='1';
 287                                 } else if (isalpha(c)) {
 288                                         type='a';
 289                                 } else type='%';
 290                         break;
 291                         case 'a': // Segun si estábamos en un espacio.
 292                                 if (c>='0' && c<='9') {
 293                                         type='a';
 294                                 } else if (isalpha(c)) {
 295                                         type='a';
 296                                 } else type='%';
 297                         break;
 298                         default:
 299                         case '%':
 300                                 if (c==' ') {
 301                                         continue;
 302                                 } else
 303                                 if (c>='0' && c<='9') {
 304                                         type='1';
 305                                 } else if (isalpha(c)) {
 306                                         type='a';
 307                                 } else type='%';
 308                         break;
 309                 }
 310                 if (c==' ') type=0;
 311                 if (!nn && c==' ') continue; // Si está tabulando al inicio, tampoco tiene efecto.
 312                 if (c==lastc && (type=='a' || type==0)) continue; // Desperdiciar letras repetidas.
 313
 314                 if (type=='%' && newline[nn-1]==' ') nn--;
 315                 newline[nn]=c;
 316
 317                 nn++;
 318                 lastc=c;
 319         }
 320         newline[nn]=0;
 321         strcpy(txt,newline);
 322
 323 }
 324
 325 unsigned int *hash_loadfile(char *filename, int *size) {
 326         char *nombre=filename, linea[MAX_LINE];
 327         FILE *fichero;
 328         fichero = fopen( nombre, "r" );
 329
 330         if( !fichero ) {
 331                 printf( "Error (NO ABIERTO)\n" );
 332                 return NULL;
 333         }
 334         char *txt;
 335
 336         int lines;
 337         for (lines=0;fgets(linea, MAX_LINE, fichero); lines++);
 338         rewind(fichero);
 339         *size=lines;
 340         unsigned int *data=malloc(lines*sizeof(unsigned int*));
 341         int line=0;
 342         while (txt=fgets(linea, MAX_LINE, fichero)) {
 343                 reducetext(txt);
 344                 data[line++]=ihash(txt);
 345         }
 346
 347         if( fclose(fichero)!=0 ) {
 348                 printf( "\nError: fichero NO CERRADO\n" );
 349                 return NULL;
 350         }
 351
 352         return data;
 353
 354 }
 355
 356 // ihash calcula un hash de 32 bits para un texto.
 357 unsigned int ihash(char *txt) {
 358         // Longitud del mensaje a cifrar
 359         int msg_len = strlen( txt );
 360
 361         //  Longitud del hash resultante - gcry_md_get_algo_dlen
 362         // devuelve la longitud del resumen hash para un algoritmo
 363         int hash_len = gcry_md_get_algo_dlen( HASH_TYPE );
 364
 365         // Salida del hash SHA1 - esto serán datos binarios
 366         unsigned char hash[ hash_len ];
 367
 368         // Calcular el resumen SHA1. Esto es una especie de función-atajo,
 369         // ya que la mayoría de funciones gcrypt requieren
 370         // la creación de un handle, etc.
 371         gcry_md_hash_buffer( HASH_TYPE, hash, txt, msg_len );
 372
 373         //      unsigned int ihash=*((unsigned int *)hash);
 374         return *((unsigned int *)hash);
 375 }