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 };
  96
  97 typedef struct _bs_decode_t_ {
  98         char c;
  99         Uint32 sig;
 100 } t_BlockSortDecode;
 101
 102 char es_menor(char *data, t_BlockSort *bs, int i, int j);
 103
 104 int _compare(const void *d1, const void *d2) {
 105         t_BlockSortDecode *s1, *s2;
 106
 107         s1 = (t_BlockSortDecode *)d1;
 108         s2 = (t_BlockSortDecode *)d2;
 109
 110         /* Hack si es el mismo caracter, dejo como mejor la de menor sig */
 111         if (s1->c == s2->c) {
 112                 return (s1->sig - s2->sig);
 113         }
 114
 115         return (s1->c - s2->c);
 116 }
 117
 118 int __compare(const void *d1, const void *d2) {
 119         t_BlockSortData *s1, *s2;
 120
 121         s1 = (t_BlockSortData *)d1;
 122         s2 = (t_BlockSortData *)d2;
 123
 124         return  es_menor(s1->bs->data, s1->bs, s1->pos_inicial, s2->pos_inicial);
 125 }
 126
 127 char es_menor(char *data, t_BlockSort *bs, int i, int j)
 128 {
 129         Uint32 pi, pj, k;
 130
 131         for(k=0; k<bs->len; k++) {
 132                 pi = (i+k)%bs->len;
 133                 pj = (j+k)%bs->len;
 134
 135                 if (data[pi] > data[pj]) return 1; /* El primero es mayor */
 136                 if (data[pi] < data[pj]) return -1; /* El primero es menor */
 137         }
 138
 139         /* Son iguales! */
 140         return 0;
 141 }
 142
 143 void generar_array(char *data, t_BlockSort *bs)
 144 {
 145         int i;
 146         for(i=0; i<bs->len; i++) {
 147                 bs->array[i].pos_inicial = i;
 148                 bs->array[i].pos_final = (i+bs->len-1)%bs->len;
 149                 bs->array[i].ord = (i==0)?1:0;
 150                 bs->array[i].bs = bs;
 151         }
 152 }
 153
 154 void ordenar_array(char *data, t_BlockSort *bs)
 155 {
 156         qsort(bs->array, bs->len, sizeof(t_BlockSortData), __compare);
 157 }
 158
 159 int generar_salida(char *data, t_BlockSort *bs, char *salida)
 160 {
 161         Uint32 i, k;
 162         char *out;
 163
 164         /* Dejo lugar para guardar el K */
 165         out = salida + sizeof(Uint32);
 166
 167         k=-1;
 168         for(i=0; i<bs->len; i++) {
 169                 out[i] = data[bs->array[i].pos_final];
 170                 if (bs->array[i].ord == 1) k = i;
 171         }
 172         return k;
 173 }
 174
 175 void bs_solve(char *in, char *out, t_BlockSort *bs, Uint32 *k, Uint32 leido)
 176 {
 177         unsigned int l;
 178         l = bs->len;
 179         /* Hack para pedasos menores a la pagina */
 180         if (leido < bs->len) bs->len = leido;
 181         bs->data = in;
 182
 183         generar_array(in, bs);
 184         ordenar_array(in, bs);
 185         (*k) = generar_salida(in, bs, out);
 186
 187         /* Guardo el k y el tamaño en el array */
 188         memcpy(out, k, sizeof(Uint32));
 189         bs->len = l;
 190 }
 191
 192 void bs_restore(char *dst, char *c, Uint32 k, Uint32 len)
 193 {
 194         Uint32 i, current;
 195         t_BlockSortDecode *in;
 196
 197         in = malloc(sizeof(t_BlockSortDecode)*len);
 198
 199         for(i=0; i<len; i++) {
 200                 in[i].c = c[i];
 201                 in[i].sig = i;
 202         }
 203
 204         qsort(in, len, sizeof(t_BlockSortDecode), _compare);
 205
 206         current = k;
 207         i=0;
 208         do {
 209                 dst[i++] = in[current].c;
 210                 current = in[current].sig;
 211         } while (current != k);
 212         free(in);
 213 }
 214
 215 t_BlockSort *bs_create(Uint32 len)
 216 {
 217         t_BlockSort *tmp;
 218
 219         tmp = malloc(sizeof(t_BlockSort));
 220         tmp->array = malloc(sizeof(t_BlockSortData)*len);
 221         tmp->len = len;
 222
 223         return tmp;
 224 }
 225
 226
 227 void bs_destroy(t_BlockSort *bs)
 228 {
 229         free(bs->array);
 230         free(bs);
 231 }
 232
 233
 234 void bs_EOL(char *data, Uint32 pagesize, Uint32 *j)
 235 {
 236         /* Trato de agregar 4 espacios antes y 4 despues de un \n */
 237         int i = (*j);
 238
 239         /* Verifico poder hacerlo */
 240         if ((i+9) >= pagesize) return; /* No pude! */
 241
 242         data[i++] = ' ';
 243         data[i++] = ' ';
 244         data[i++] = ' ';
 245         data[i++] = ' ';
 246         data[i++] = ' ';
 247         data[i++] = ' ';
 248         data[i++] = ' ';
 249         data[i++] = ' ';
 250         data[i++] = ' ';
 251
 252         (*j) += 9;
 253 }
 254
 255 char check_hint(char c)
 256 {
 257         static int current_pos = 0;
 258         char hits = 0;
 259         int i;
 260         char hit_pos = -1;
 261
 262         for(i=0; i<DICT_SIZE; i++) {
 263                 /* Veo de no pasarme */
 264                 if (current_pos < dic[i].len) {
 265                         /* Si la palabra tiene suficientes hints */
 266                         if (dic[i].hits == current_pos) {
 267                                 if (dic[i].word[current_pos] == c) {
 268                                         dic[i].hits++;
 269                                         hits++;
 270                                         if (dic[i].hits == dic[i].len) {
 271                                                 hit_pos = i;
 272                                         }
 273                                 } else {
 274                                         /* Esta palabra ya no tiene posibilidades */
 275                                         dic[i].hits = 0;
 276                                 }
 277                         }
 278                 } else {
 279                         dic[i].hits = 0;
 280                 }
 281         }
 282
 283         current_pos++;
 284
 285         if (hits == 0) {
 286                 current_pos = 0;
 287                 return -1; /* No hay hints ! */
 288         }
 289         if (hits > 1) return -2; /* Tengo mas de 1 hint! */
 290
 291         if (hit_pos == -1) return -2; /* Tengo 1 solo hit pero no es completo */
 292
 293         /* Tengo 1 solo hint !!!! */
 294         current_pos = 0;
 295         return hit_pos;
 296 }
 297
 298 void bs_clean_dic()
 299 {
 300         int i;
 301         for(i=0; i<DICT_SIZE; i++) {
 302                 dic[i].hits = 0;
 303         }
 304 }
 305
 306 int bs_readblock(FILE *fp, char *data, Uint32 pagesize, int usar_dic)
 307 {
 308         Uint32 i=0;
 309         char c, hint;
 310         char buffer[100];
 311         int j, buffer_pos=0;
 312
 313         while ((!feof(fp)) && ((i+buffer_pos) < pagesize)) {
 314                 c = fgetc(fp);
 315
 316                 if (c == ESCAPE_CHARACTER) {
 317                         data[i++] = c;
 318                         data[i++] = 0xF;
 319                         bs_clean_dic();
 320                         continue;
 321                 }
 322
 323                 hint = check_hint(c);
 324
 325                 if (usar_dic != 1) {
 326                         data[i++] = c;
 327                         continue;
 328                 }
 329
 330                 switch (hint) {
 331                         case -1:
 332                                 /* No hay hints, vacio el buffer y luego saco el c */
 333                                 for(j=0; j<buffer_pos; j++)
 334                                         data[i++] = buffer[j];
 335
 336                                 data[i++] = c;
 337                                 buffer_pos = 0;
 338                                 bs_clean_dic();
 339                         break;
 340                         case -2:
 341                                 /* Tengo mas de 1 hit, tengo posibilidades, guardo este char en el buffer */
 342                                 buffer[buffer_pos++] = c;
 343                         break;
 344                         default:
 345                                 /* Me retornaron un numero positivo!!, eso quiere decir que ese numero
 346                                  * es la posicion dentro del diccionario de la palabra que puedo reemplazar
 347                                  */
 348                                 data[i++] = ESCAPE_CHARACTER;
 349                                 /* Trato de hacer que el caracter sea comun en textos, para que no me rompa
 350                                  * la localidad
 351                                  */
 352                                 data[i++] = hint+32;
 353                                 bs_clean_dic();
 354                                 /* El buffer no lo necesito mas */
 355                                 buffer_pos = 0;
 356                 }
 357         }
 358
 359         for(j=0; j<buffer_pos; j++)
 360                 data[i++] = buffer[j];
 361         /* Saco un EOF que lee de mas */
 362         if (i<pagesize) i--;
 363
 364         return i;
 365 }
 366