src/blocksorting/bs.c

   1
   2 #include "bs.h"
   3 #include <stdlib.h>
   4 #include <ctype.h>
   5
   6 /* Block Sorting Optimizado en memoria! */
   7
   8 typedef struct _dict_ {
   9         char *word;
  10         int len;
  11         int hits;
  12 } t_Diccionario;
  13
  14 #define PALABRA(a) {a, sizeof(a)-1, 0}
  15
  16 #define DICT_SIZE sizeof(dic)/sizeof(t_Diccionario)
  17
  18 /* ASCII Numero 3 como caracter de escape */
  19 #define ESCAPE_CHARACTER 0x3
  20
  21 /* Diccionario */
  22 t_Diccionario dic[] = {
  23         /* Preposiciones (no todas) */
  24         PALABRA(" ante"),
  25         PALABRA(" bajo"),
  26         PALABRA(" cabe"),
  27         PALABRA(" con"),
  28         PALABRA(" contra"),
  29         /* PALABRA(" de"),  XXX No se si conviene, solo ahorra 1 byte y puede romper localidad */
  30         PALABRA(" desde"),
  31         PALABRA(" hasta"),
  32         PALABRA(" hacia"),
  33         PALABRA(" para"),
  34         PALABRA(" por"),
  35         PALABRA(" según"),
  36         PALABRA(" sin"),
  37         PALABRA(" sobre"),
  38         PALABRA(" tras"),
  39         PALABRA(" mediante"),
  40         PALABRA(" durante"),
  41
  42         /* Articulos */
  43         PALABRA(" el "),
  44         PALABRA(" la "),
  45         PALABRA(" ella "),
  46         PALABRA(" del "),
  47         PALABRA(" los "),
  48         PALABRA(" las "),
  49         PALABRA(" lo "),
  50         PALABRA(" que"),
  51         PALABRA(" una "),
  52         PALABRA(" también"),
  53         PALABRA(" tambien"),
  54         PALABRA(" cuando"),
  55         PALABRA(" pero"),
  56         PALABRA(" todo"),
  57         /* Otras de test */
  58         PALABRA(" si "),
  59         PALABRA(" mas "),
  60         PALABRA(" más "),
  61         PALABRA(" porque"),
  62         PALABRA(" entonces"),
  63         PALABRA(" siempre"),
  64         PALABRA(" segundo"),
  65         PALABRA(" programa"),
  66         PALABRA(" existe"),
  67         PALABRA(" recien"),
  68         PALABRA(" máximo"),
  69         PALABRA(" mínimo"),
  70         PALABRA(" casi"),
  71         PALABRA(" sección"),
  72         PALABRA(" informe"),
  73         PALABRA(" Informe"),
  74         PALABRA(" acción"),
  75         PALABRA(" perdedor"),
  76         PALABRA(" existencia"),
  77         PALABRA(" aire"),
  78         PALABRA(" árbol"),
  79         PALABRA(" prueba"),
  80         PALABRA(" muestra"),
  81         PALABRA(" animal"),
  82         PALABRA(" suerte"),
  83         PALABRA(" portador"),
  84         PALABRA(" molesto"),
  85         PALABRA(" cielo"),
  86         PALABRA(" impulso"),
  87         PALABRA(" alcohol"),
  88         PALABRA(" seguido"),
  89         PALABRA(" permiso"),
  90         PALABRA(" cuarto"),
  91         PALABRA(" brillante"),
  92         PALABRA(" tener"),
  93         PALABRA(" ningún"),
  94         PALABRA(" fácil"),
  95         /* Algunas cosas de ingles para mejorar otros textos */
  96         PALABRA(" as "),
  97         PALABRA(" will "),
  98         PALABRA(" with "),
  99         PALABRA(" this "),
 100         PALABRA(" program "),
 101         PALABRA(" are "),
 102         PALABRA(" The "),
 103         PALABRA(" it "),
 104         PALABRA(" which "),
 105         PALABRA(" for "),
 106         PALABRA(" be "),
 107         PALABRA(" that "),
 108         PALABRA(" is "),
 109         PALABRA(" and "),
 110         PALABRA(" to "),
 111         PALABRA(" of "),
 112         PALABRA(" the ")
 113 };
 114
 115 typedef struct _bs_decode_t_ {
 116         char c;
 117         Uint32 sig;
 118 } t_BlockSortDecode;
 119
 120 char es_menor(char *data, t_BlockSort *bs, int i, int j);
 121
 122 int _compare(const void *d1, const void *d2) {
 123         t_BlockSortDecode *s1, *s2;
 124
 125         s1 = (t_BlockSortDecode *)d1;
 126         s2 = (t_BlockSortDecode *)d2;
 127
 128         /* Hack si es el mismo caracter, dejo como mejor la de menor sig */
 129         if (s1->c == s2->c) {
 130                 return (s1->sig - s2->sig);
 131         }
 132
 133         return (s1->c - s2->c);
 134 }
 135
 136 int __compare(const void *d1, const void *d2) {
 137         t_BlockSortData *s1, *s2;
 138
 139         s1 = (t_BlockSortData *)d1;
 140         s2 = (t_BlockSortData *)d2;
 141
 142         return  es_menor(s1->bs->data, s1->bs, s1->pos_inicial, s2->pos_inicial);
 143 }
 144
 145 char es_menor(char *data, t_BlockSort *bs, int i, int j)
 146 {
 147         Uint32 pi, pj, k;
 148
 149         for(k=0; k<bs->len; k++) {
 150                 pi = (i+k)%bs->len;
 151                 pj = (j+k)%bs->len;
 152
 153                 if (data[pi] > data[pj]) return 1; /* El primero es mayor */
 154                 if (data[pi] < data[pj]) return -1; /* El primero es menor */
 155         }
 156
 157         /* Son iguales! */
 158         return 0;
 159 }
 160
 161 void generar_array(char *data, t_BlockSort *bs)
 162 {
 163         int i;
 164         for(i=0; i<bs->len; i++) {
 165                 bs->array[i].pos_inicial = i;
 166                 bs->array[i].pos_final = (i+bs->len-1)%bs->len;
 167                 bs->array[i].ord = (i==0)?1:0;
 168                 bs->array[i].bs = bs;
 169         }
 170 }
 171
 172 void ordenar_array(char *data, t_BlockSort *bs)
 173 {
 174         qsort(bs->array, bs->len, sizeof(t_BlockSortData), __compare);
 175 }
 176
 177 int generar_salida(char *data, t_BlockSort *bs, char *salida)
 178 {
 179         Uint32 i, k;
 180         char *out;
 181
 182         /* Dejo lugar para guardar el K */
 183         out = salida + sizeof(Uint32);
 184
 185         k=-1;
 186         for(i=0; i<bs->len; i++) {
 187                 out[i] = data[bs->array[i].pos_final];
 188                 if (bs->array[i].ord == 1) k = i;
 189         }
 190         return k;
 191 }
 192
 193 void bs_solve(char *in, char *out, t_BlockSort *bs, Uint32 *k, Uint32 leido)
 194 {
 195         unsigned int l;
 196         l = bs->len;
 197         /* Hack para pedasos menores a la pagina */
 198         if (leido < bs->len) bs->len = leido;
 199         bs->data = in;
 200
 201         generar_array(in, bs);
 202         ordenar_array(in, bs);
 203         (*k) = generar_salida(in, bs, out);
 204
 205         /* Guardo el k y el tamaño en el array */
 206         memcpy(out, k, sizeof(Uint32));
 207         bs->len = l;
 208 }
 209
 210 void bs_restore(char *dst, char *c, Uint32 k, Uint32 len)
 211 {
 212         Uint32 i, current;
 213         t_BlockSortDecode *in;
 214
 215         in = malloc(sizeof(t_BlockSortDecode)*len);
 216
 217         for(i=0; i<len; i++) {
 218                 in[i].c = c[i];
 219                 in[i].sig = i;
 220         }
 221
 222         qsort(in, len, sizeof(t_BlockSortDecode), _compare);
 223
 224         current = k;
 225         i=0;
 226         do {
 227                 dst[i++] = in[current].c;
 228                 current = in[current].sig;
 229         } while (current != k);
 230         free(in);
 231 }
 232
 233 t_BlockSort *bs_create(Uint32 len)
 234 {
 235         t_BlockSort *tmp;
 236
 237         tmp = malloc(sizeof(t_BlockSort));
 238         tmp->array = malloc(sizeof(t_BlockSortData)*len);
 239         tmp->len = len;
 240
 241         return tmp;
 242 }
 243
 244
 245 void bs_destroy(t_BlockSort *bs)
 246 {
 247         free(bs->array);
 248         free(bs);
 249 }
 250
 251
 252 void bs_EOL(char *data, Uint32 pagesize, Uint32 *j)
 253 {
 254         /* Trato de agregar 4 espacios antes y 4 despues de un \n */
 255         int i = (*j);
 256
 257         /* Verifico poder hacerlo */
 258         if ((i+9) >= pagesize) return; /* No pude! */
 259
 260         data[i++] = ' ';
 261         data[i++] = ' ';
 262         data[i++] = ' ';
 263         data[i++] = ' ';
 264         data[i++] = ' ';
 265         data[i++] = ' ';
 266         data[i++] = ' ';
 267         data[i++] = ' ';
 268         data[i++] = ' ';
 269
 270         (*j) += 9;
 271 }
 272
 273 char check_hint(char c)
 274 {
 275         static int current_pos = 0;
 276         char hits = 0;
 277         int i;
 278         char hit_pos = -1;
 279
 280         for(i=0; i<DICT_SIZE; i++) {
 281                 /* Veo de no pasarme */
 282                 if (current_pos < dic[i].len) {
 283                         /* Si la palabra tiene suficientes hints */
 284                         if (dic[i].hits == current_pos) {
 285                                 if (dic[i].word[current_pos] == c) {
 286                                         dic[i].hits++;
 287                                         hits++;
 288                                         if (dic[i].hits == dic[i].len) {
 289                                                 hit_pos = i;
 290                                         }
 291                                 } else {
 292                                         /* Esta palabra ya no tiene posibilidades */
 293                                         dic[i].hits = 0;
 294                                 }
 295                         }
 296                 } else {
 297                         dic[i].hits = 0;
 298                 }
 299         }
 300
 301         current_pos++;
 302
 303         if (hits == 0) {
 304                 current_pos = 0;
 305                 return -1; /* No hay hints ! */
 306         }
 307         if (hits > 1) return -2; /* Tengo mas de 1 hint! */
 308
 309         if (hit_pos == -1) return -2; /* Tengo 1 solo hit pero no es completo */
 310
 311         /* Tengo 1 solo hint !!!! */
 312         current_pos = 0;
 313         return hit_pos;
 314 }
 315
 316 void bs_clean_dic()
 317 {
 318         int i;
 319         for(i=0; i<DICT_SIZE; i++) {
 320                 dic[i].hits = 0;
 321         }
 322 }
 323
 324 int bs_readblock(FILE *fp, char *data, Uint32 pagesize, int usar_dic)
 325 {
 326         Uint32 i=0;
 327         char c, hint;
 328         char buffer[100];
 329         int j, buffer_pos=0;
 330
 331         while ((!feof(fp)) && ((i+buffer_pos) < pagesize)) {
 332                 c = fgetc(fp);
 333
 334                 if (usar_dic != 1) {
 335                         data[i++] = c;
 336                         continue;
 337                 }
 338
 339                 if (c == ESCAPE_CHARACTER) {
 340                         data[i++] = c;
 341                         data[i++] = 0xF;
 342                         bs_clean_dic();
 343                         continue;
 344                 }
 345
 346                 hint = check_hint(c);
 347
 348                 switch (hint) {
 349                         case -1:
 350                                 /* No hay hints, vacio el buffer y luego saco el c */
 351                                 for(j=0; j<buffer_pos; j++)
 352                                         data[i++] = buffer[j];
 353
 354                                 data[i++] = c;
 355                                 buffer_pos = 0;
 356                                 bs_clean_dic();
 357                         break;
 358                         case -2:
 359                                 /* Tengo mas de 1 hit, tengo posibilidades, guardo este char en el buffer */
 360                                 buffer[buffer_pos++] = c;
 361                         break;
 362                         default:
 363                                 /* Me retornaron un numero positivo!!, eso quiere decir que ese numero
 364                                  * es la posicion dentro del diccionario de la palabra que puedo reemplazar
 365                                  */
 366                                 data[i++] = ESCAPE_CHARACTER;
 367                                 /* Trato de hacer que el caracter sea comun en textos, para que no me rompa
 368                                  * la localidad
 369                                  */
 370                                 data[i++] = hint;
 371                                 bs_clean_dic();
 372                                 /* El buffer no lo necesito mas */
 373                                 buffer_pos = 0;
 374                 }
 375         }
 376
 377         for(j=0; j<buffer_pos; j++)
 378                 data[i++] = buffer[j];
 379         /* Saco un EOF que lee de mas */
 380         if (i<pagesize) i--;
 381
 382         return i;
 383 }
 384
 385 char *bs_finalblock(char *data, Uint32 len, Uint32 *new_size)
 386 {
 387         Uint32 size=0, i, j;
 388         char *out = NULL;
 389         unsigned char tmp;
 390
 391         for(i=0; i < len; i++) {
 392                 if (data[i] == ESCAPE_CHARACTER) {
 393                         i++;
 394                         if (data[i] == 0xF) {
 395                                 /* Solo tengo que dejar el ESCAPE_CHARACTER */
 396                                 size++;
 397                                 out = (char *)realloc(out, size*sizeof(char));
 398                                 out[size-1] = data[i];
 399                                 /* Salteo ese caracter */
 400                         } else {
 401                                 /* Va una palabra!! */
 402                                 tmp = data[i];
 403                                 size += dic[(size_t)tmp].len;
 404                                 out = (char *)realloc(out, size*sizeof(char));
 405                                 for(j=0; j<dic[(size_t)tmp].len; j++) {
 406                                         out[size-dic[(size_t)tmp].len+j] = dic[(size_t)tmp].word[j];
 407                                 }
 408                                 /* Salteo el caracter siguiente al de escape */
 409                         }
 410                 } else {
 411                         size++;
 412                         out = (char *)realloc(out, size*sizeof(char));
 413                         out[size-1] = data[i];
 414                 }
 415         }
 416
 417         (*new_size) = size;
 418         return out;
 419 }
 420