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 _bs_decode_t_ {
   9         char c;
  10         Uint32 sig;
  11 } t_BlockSortDecode;
  12
  13 char es_menor(char *data, t_BlockSort *bs, int i, int j);
  14
  15 int _compare(const void *d1, const void *d2) {
  16         t_BlockSortDecode *s1, *s2;
  17
  18         s1 = (t_BlockSortDecode *)d1;
  19         s2 = (t_BlockSortDecode *)d2;
  20
  21         /* Hack si es el mismo caracter, dejo como mejor la de menor sig */
  22         if (s1->c == s2->c) {
  23                 return (s1->sig - s2->sig);
  24         }
  25
  26         return (s1->c - s2->c);
  27 }
  28
  29 int __compare(const void *d1, const void *d2) {
  30         t_BlockSortData *s1, *s2;
  31
  32         s1 = (t_BlockSortData *)d1;
  33         s2 = (t_BlockSortData *)d2;
  34
  35         return  es_menor(s1->bs->data, s1->bs, s1->pos_inicial, s2->pos_inicial);
  36 }
  37
  38 char es_menor(char *data, t_BlockSort *bs, int i, int j)
  39 {
  40         Uint32 pi, pj, k;
  41
  42         for(k=0; k<bs->len; k++) {
  43                 pi = (i+k)%bs->len;
  44                 pj = (j+k)%bs->len;
  45
  46                 if (data[pi] > data[pj]) return 1; /* El primero es mayor */
  47                 if (data[pi] < data[pj]) return -1; /* El primero es menor */
  48         }
  49
  50         /* Son iguales! */
  51         return 0;
  52 }
  53
  54 void generar_array(char *data, t_BlockSort *bs)
  55 {
  56         int i;
  57         for(i=0; i<bs->len; i++) {
  58                 bs->array[i].pos_inicial = i;
  59                 bs->array[i].pos_final = (i+bs->len-1)%bs->len;
  60                 bs->array[i].ord = (i==0)?1:0;
  61                 bs->array[i].bs = bs;
  62         }
  63 }
  64
  65 void ordenar_array(char *data, t_BlockSort *bs)
  66 {
  67         qsort(bs->array, bs->len, sizeof(t_BlockSortData), __compare);
  68 }
  69
  70 int generar_salida(char *data, t_BlockSort *bs, char *salida)
  71 {
  72         Uint32 i, k;
  73         char *out;
  74
  75         /* Dejo lugar para guardar el K */
  76         out = salida + sizeof(Uint32);
  77
  78         k=-1;
  79         for(i=0; i<bs->len; i++) {
  80                 out[i] = data[bs->array[i].pos_final];
  81                 if (bs->array[i].ord == 1) k = i;
  82         }
  83         return k;
  84 }
  85
  86 void bs_solve(char *in, char *out, t_BlockSort *bs, Uint32 *k, Uint32 leido)
  87 {
  88         unsigned int l;
  89         l = bs->len;
  90         /* Hack para pedasos menores a la pagina */
  91         if (leido < bs->len) bs->len = leido;
  92         bs->data = in;
  93
  94         generar_array(in, bs);
  95         ordenar_array(in, bs);
  96         (*k) = generar_salida(in, bs, out);
  97
  98         /* Guardo el k y el tamaño en el array */
  99         memcpy(out, k, sizeof(Uint32));
 100         bs->len = l;
 101 }
 102
 103 void bs_restore(char *dst, char *c, Uint32 k, Uint32 len)
 104 {
 105         Uint32 i, current;
 106         t_BlockSortDecode *in;
 107
 108         in = malloc(sizeof(t_BlockSortDecode)*len);
 109
 110         for(i=0; i<len; i++) {
 111                 in[i].c = c[i];
 112                 in[i].sig = i;
 113         }
 114
 115         qsort(in, len, sizeof(t_BlockSortDecode), _compare);
 116
 117         current = k;
 118         i=0;
 119         do {
 120                 dst[i++] = in[current].c;
 121                 current = in[current].sig;
 122         } while (current != k);
 123         free(in);
 124 }
 125
 126 t_BlockSort *bs_create(Uint32 len)
 127 {
 128         t_BlockSort *tmp;
 129
 130         tmp = malloc(sizeof(t_BlockSort));
 131         tmp->array = malloc(sizeof(t_BlockSortData)*len);
 132         tmp->len = len;
 133
 134         return tmp;
 135 }
 136
 137
 138 void bs_destroy(t_BlockSort *bs)
 139 {
 140         free(bs->array);
 141         free(bs);
 142 }
 143
 144
 145 void bs_EOL(char *data, Uint32 pagesize, Uint32 *j)
 146 {
 147         /* Trato de agregar 4 espacios antes y 4 despues de un \n */
 148         int i = (*j);
 149
 150         /* Verifico poder hacerlo */
 151         if ((i+9) >= pagesize) return; /* No pude! */
 152
 153         data[i++] = ' ';
 154         data[i++] = ' ';
 155         data[i++] = ' ';
 156         data[i++] = ' ';
 157         data[i++] = ' ';
 158         data[i++] = ' ';
 159         data[i++] = ' ';
 160         data[i++] = ' ';
 161         data[i++] = ' ';
 162
 163         (*j) += 9;
 164 }
 165
 166 int bs_readblock(FILE *fp, char *data, Uint32 pagesize)
 167 {
 168         Uint32 i=0;
 169         char c;
 170         while ((!feof(fp)) && (i < pagesize)) {
 171                 c = fgetc(fp);
 172 /*              if (c != '\n')*/
 173                 if (c == 0x01) {
 174                         /* Debo encodear el \0 para que no complique */
 175                         data[i++] = 0x01;
 176                         data[i++] = 0xFF;
 177                 }
 178                 if (isupper(c)) {
 179                         data[i++] = 0x01;
 180                         data[i++] = tolower(c);
 181                 } else {
 182                         data[i++] = c;
 183                 }
 184 /*              else
 185                         bs_EOL(data, pagesize, &i);*/
 186         }
 187
 188         /* Saco un EOF que lee de mas */
 189         if (i<pagesize) i--;
 190
 191         return i;
 192 }
 193