swcsa/intIndex/psiGonzalo.c

   1
   2 #include "psiGonzalo.h"
   3
   4
   5 // IMPLEMENTACI�N DAS FUNCI�NS
   6
   7 void destroyGonzaloCompressedPsi(GonzaloCompressedPsi *compressedPsi) {
   8
   9         //free(compressedPsi->Hlen.s.spos);
  10         //free(compressedPsi->Hacc.s.spos);
  11         freeHuff2(compressedPsi->Hlen);
  12         freeHuff2(compressedPsi->Hacc);
  13         free(compressedPsi->cPsi);
  14         free(compressedPsi->bposS);
  15 }
  16
  17
  18 GonzaloCompressedPsi gonzaloCompressPsi(uint *Psi, uint psiSize, uint T, uint HUFF) {
  19
  20         GonzaloCompressedPsi compressedPsi;
  21
  22         register uint i;
  23         uint oi,j;
  24         int ok,k;
  25         register uint _cptr;
  26
  27         uint *_cPsi;
  28         uint *_bposS;
  29
  30         uint links = psiSize;
  31         uint samplen = T;
  32         uint _bplen;
  33         uint pslen;
  34         uint totexc;
  35
  36         uint *acc,*lacc;
  37         THuff Hacc, Hlen;
  38
  39         uint totalSize;
  40
  41         // Construe os arboles de huffman, o dos valores directos
  42         // e o das lonxitudes dos runs. Usa como vectores auxiliares de frecuencias
  43         // a acc e lacc, que finalmente libera.
  44         acc = (uint *)malloc (HUFF*sizeof(uint));
  45         lacc = (uint *)malloc ((samplen-1)*sizeof(uint));
  46         for (k=0;k<HUFF;k++) acc[k]=0;
  47         for (k=0;k<samplen-1;k++) lacc[k]=0;
  48
  49         ok = 0;
  50         k = Psi[0];
  51         for (i=0;i<=links;i++) {
  52                 if ((k == 1) && (i % samplen)) { if (ok != 1) oi = i; }
  53                 else {
  54                         if (ok == 1) {
  55                                 acc[1]++;
  56                             lacc[i-oi-1]++;
  57                         }
  58                     if (i % samplen)
  59                                 if ((k < 1) || (k >= HUFF)) acc[0]++;
  60                         else acc[k]++;
  61                 }
  62             ok = (i % samplen) ? k : 0;
  63                 k = Psi[i+1]-Psi[i];
  64         }
  65
  66         if (ok == 1) {
  67                 acc[1]++;
  68                 lacc[i-oi-1]++;
  69         }
  70
  71         Hacc = createHuff (acc,HUFF-1, UNSORTED);
  72         Hlen = createHuff (lacc,samplen-2, UNSORTED);
  73         totexc = acc[0];
  74         pslen = _bits(psiSize+1);
  75         _bplen = _bits(Hacc.total+Hlen.total+(1+links/samplen+totexc)*pslen);
  76         _bposS = (uint *)malloc ((((1+links/samplen)*_bplen+W-1)/W)*sizeof(uint));
  77         _cPsi  = (uint *)malloc (((Hacc.total+Hlen.total+(1+links/samplen+totexc)*pslen+W-1)/W)*sizeof(uint));
  78
  79         _cptr = 0;
  80         ok = 0;
  81         k = Psi[0];
  82
  83         for (i=0;i<=links;i++) {
  84
  85                 if ((k == 1) && (i % samplen)) { if (ok != 1) oi = i; }
  86                 else {
  87                         if (ok == 1) {
  88                                 _cptr = encodeHuff (Hacc,1,_cPsi,_cptr);
  89                             _cptr = encodeHuff(Hlen,i-oi-1,_cPsi,_cptr);
  90                         }
  91                         if (i % samplen) {
  92                                 if ((k > 1) && (k < HUFF)) _cptr = encodeHuff (Hacc,k,_cPsi,_cptr);
  93                         else {
  94                                         _cptr = encodeHuff (Hacc,0,_cPsi,_cptr);
  95                                 bitwrite (_cPsi,_cptr,pslen,Psi[i]);
  96                                         _cptr += pslen;
  97                                 }
  98                         }
  99                         else {
 100                                 bitwrite (_bposS,(i/samplen)*_bplen,_bplen,_cptr);
 101                             bitwrite (_cPsi,_cptr,pslen,Psi[i]);
 102                             _cptr += pslen;
 103                         }
 104                 }
 105                 ok = (i % samplen) ? k : 0;
 106                 k = Psi[i+1]-Psi[i];
 107         }
 108
 109         if (ok == 1) {
 110                 _cptr = encodeHuff (Hacc,1,_cPsi,_cptr);
 111                 _cptr = encodeHuff(Hlen,i-oi-1,_cPsi,_cptr);
 112         }
 113
 114         // Calculamos o espacio total
 115         totalSize = (((1+links/samplen)*_bplen+W-1)/W)*sizeof(uint) +
 116                 ((Hacc.total+Hlen.total+(1+links/samplen+totexc)*pslen+W-1)/W)*sizeof(uint) +
 117                 5*sizeof(int) + sizeHuff2(Hacc) + sizeHuff2(Hlen);
 118         printf("\n\tCompressed Psi size = %d bytes\n", totalSize);
 119
 120         // Necesario antes de decodificar
 121         prepareToDecode(&Hacc);
 122         prepareToDecode(&Hlen);
 123
 124         // Asignamos os valores e devolvemos psi comprimido
 125         compressedPsi.links = psiSize;
 126         compressedPsi.totexc = totexc;
 127         compressedPsi.cPsi = _cPsi;
 128         compressedPsi.samplen = samplen;
 129         compressedPsi.bposS = _bposS;
 130         compressedPsi.bplen = _bplen;
 131         compressedPsi.pslen = pslen;
 132         compressedPsi.Hacc = Hacc;
 133         compressedPsi.Hlen = Hlen;
 134         compressedPsi.totalMem = totalSize;
 135
 136         free(acc);
 137         free(lacc);
 138
 139         return compressedPsi;
 140 }
 141
 142
 143
 144 int getGonzaloPsiValue(GonzaloCompressedPsi *compressedPsi, unsigned int position) {
 145
 146         uint *cPsi = compressedPsi->cPsi;
 147         uint samplen = compressedPsi->samplen;
 148         uint *bposS = compressedPsi->bposS;
 149         uint bplen = compressedPsi->bplen;
 150         uint pslen = compressedPsi->pslen;
 151         THuff *Hacc = &compressedPsi->Hacc;
 152         THuff *Hlen = &compressedPsi->Hlen;
 153
 154         uint sampj,cptr,val,dval,rlen,head,hlen;
 155
 156         sampj = (position/samplen)*samplen;
 157         cptr = bitread(bposS,(sampj/samplen)*bplen,bplen);
 158         head = cptr;
 159         val = bitread(cPsi,head,pslen);
 160         head += pslen;
 161
 162         while (sampj < position) {
 163
 164                 head = decodeHuff(Hacc,&dval,cPsi,head);
 165
 166                 if (dval == 0) {
 167
 168                         val = bitread(cPsi,head,pslen);
 169                         head += pslen;
 170                         sampj++;
 171                 }
 172                 else
 173                         if (dval == 1) {
 174                                 head = decodeHuff(Hlen,&rlen,cPsi,head);
 175                                 rlen++;
 176                         if (sampj + rlen >= position) return val + (position-sampj);
 177                         val += rlen;
 178                         sampj += rlen;
 179                         }
 180                         else {
 181                                 val += dval;
 182                         sampj++;
 183                         }
 184
 185         }
 186
 187         return val;
 188
 189 }
 190
 191
 192 void storeGonzaloCompressedPsi(GonzaloCompressedPsi *compressedPsi, char *filename) {
 193
 194         int file;
 195         THuff Hacc;
 196         THuff Hlen;
 197
 198         if( (file = open(filename, O_WRONLY|O_CREAT, 0700)) < 0) {
 199                 printf("Cannot open file %s\n", filename);
 200                 exit(0);
 201         }
 202
 203         // Copias locales dos arboles de HUFFMAN
 204         Hacc = compressedPsi->Hacc;
 205         Hlen = compressedPsi->Hlen;
 206
 207         write(file, &(compressedPsi->links), sizeof(int));
 208         write(file, &(compressedPsi->totexc), sizeof(int));
 209         write(file, &(compressedPsi->samplen), sizeof(int));
 210         write(file, &(compressedPsi->bplen), sizeof(int));
 211         write(file, &(compressedPsi->pslen), sizeof(int));
 212         // Almacenar o arbol de huffman principal
 213         write(file, &Hacc.max, sizeof(int));
 214         write(file, &Hacc.lim, sizeof(int));
 215         write(file, &Hacc.depth, sizeof(int));
 216 //      write(file, Hacc.s.spos, (Hacc.lim+1)*sizeof(int));
 217         write(file, Hacc.s.symb, (Hacc.lim+1)*sizeof(int));
 218         write(file, Hacc.num, (Hacc.depth+1)*sizeof(int));
 219         write(file, Hacc.fst, (Hacc.depth+1)*sizeof(int));
 220         // Fin de almacenar o arbol de huffman principal
 221         // Almacenar o arbol de huffman das lonxitudes dos runs
 222         write(file, &Hlen.max, sizeof(int));
 223         write(file, &Hlen.lim, sizeof(int));
 224         write(file, &Hlen.depth, sizeof(int));
 225 //      write(file, Hlen.s.spos, (Hlen.lim+1)*sizeof(int));
 226         write(file, Hlen.s.symb, (Hlen.lim+1)*sizeof(int));
 227         write(file, Hlen.num, (Hlen.depth+1)*sizeof(int));
 228         write(file, Hlen.fst, (Hlen.depth+1)*sizeof(int));
 229         // Fin de almacenar o arbol de huffman das lonxitudes dos runs
 230         write(file,     compressedPsi->bposS, ((compressedPsi->bplen*(1+compressedPsi->links/compressedPsi->samplen)+W-1)/W)*sizeof(uint));
 231         write(file,     compressedPsi->cPsi, ((Hacc.total+Hlen.total+(1+compressedPsi->links/compressedPsi->samplen+compressedPsi->totexc)*compressedPsi->pslen+W-1)/W)*sizeof(int));
 232
 233         write(file, &(compressedPsi->totalMem), sizeof(int));
 234
 235         close(file);
 236
 237 }
 238
 239
 240 GonzaloCompressedPsi loadGonzaloCompressedPsi(char *filename) {
 241
 242         GonzaloCompressedPsi compressedPsi;
 243
 244         THuff Hacc;
 245         THuff Hlen;
 246
 247         int file;
 248
 249         if( (file = open(filename, O_RDONLY)) < 0) {
 250                 printf("Cannot read file %s\n", filename);
 251                 exit(0);
 252         }
 253         read(file, &(compressedPsi.links), sizeof(int));
 254         read(file, &(compressedPsi.totexc), sizeof(int));
 255         read(file, &(compressedPsi.samplen), sizeof(int));
 256         read(file, &(compressedPsi.bplen), sizeof(int));
 257         read(file, &(compressedPsi.pslen), sizeof(int));
 258         // Cargamos o arbol de Huffman principal
 259         read(file, &Hacc.max, sizeof(int));
 260         read(file, &Hacc.lim, sizeof(int));
 261         read(file, &Hacc.depth, sizeof(int));
 262         //Hacc.s.spos = (unsigned int *) malloc((Hacc.lim+1)*sizeof(int));
 263         Hacc.s.symb = (unsigned int *) malloc((Hacc.lim+1)*sizeof(int));
 264         Hacc.num = (unsigned int *) malloc((Hacc.depth+1)*sizeof(int));
 265         Hacc.fst = (unsigned int *) malloc((Hacc.depth+1)*sizeof(int));
 266         //read(file, Hacc.s.spos, (Hacc.lim+1)*sizeof(int));
 267         read(file, Hacc.s.symb, (Hacc.lim+1)*sizeof(int));
 268         read(file, Hacc.num, (Hacc.depth+1)*sizeof(int));
 269         read(file, Hacc.fst, (Hacc.depth+1)*sizeof(int));
 270         compressedPsi.Hacc = Hacc;
 271         // Fin da carga do arbol de Huffman     principal
 272         // Cargamos o arbol de Huffman coas lonxitudes dos runs
 273         read(file, &Hlen.max, sizeof(int));
 274         read(file, &Hlen.lim, sizeof(int));
 275         read(file, &Hlen.depth, sizeof(int));
 276         //Hlen.s.spos = (unsigned int *) malloc((Hlen.lim+1)*sizeof(int));
 277         Hlen.s.symb = (unsigned int *) malloc((Hlen.lim+1)*sizeof(int));
 278         Hlen.num = (unsigned int *) malloc((Hlen.depth+1)*sizeof(int));
 279         Hlen.fst = (unsigned int *) malloc((Hlen.depth+1)*sizeof(int));
 280         //read(file, Hlen.s.spos, (Hlen.lim+1)*sizeof(int));
 281         read(file, Hlen.s.symb, (Hlen.lim+1)*sizeof(int));
 282         read(file, Hlen.num, (Hlen.depth+1)*sizeof(int));
 283         read(file, Hlen.fst, (Hlen.depth+1)*sizeof(int));
 284         compressedPsi.Hlen = Hlen;
 285         // Fin da carga do arbol de Huffman     coas lonxitudes dos runs
 286         compressedPsi.bposS = (uint *) malloc (((compressedPsi.bplen*(1+compressedPsi.links/compressedPsi.samplen)+W-1)/W)*sizeof(uint));
 287         read(file, compressedPsi.bposS, ((compressedPsi.bplen*(1+compressedPsi.links/compressedPsi.samplen)+W-1)/W)*sizeof(uint));
 288         compressedPsi.cPsi = (uint *) malloc (((Hacc.total+Hlen.total+(1+compressedPsi.links/compressedPsi.samplen+compressedPsi.totexc)*compressedPsi.pslen+W-1)/W)*sizeof(uint));
 289         read(file, compressedPsi.cPsi, ((Hacc.total+Hlen.total+(1+compressedPsi.links/compressedPsi.samplen+compressedPsi.totexc)*compressedPsi.pslen+W-1)/W)*sizeof(uint));
 290
 291         read(file, &(compressedPsi.totalMem), sizeof(int));
 292         close(file);
 293
 294         return compressedPsi;
 295
 296 }