src/statichuff/statichuff.c

   1
   2 #include "statichuff.h"
   3 #include "../vfile/vfile.h"
   4 #include <stdlib.h>
   5
   6 void putbit(char bit, char restart, char flush, VFILE *fp)
   7 {
   8         static unsigned long int bits_buffer = 0;
   9         static unsigned char bits_used = 0;
  10
  11         /* me obligan a emitir el output */
  12         if ((flush == 1) && (bits_used > 0)) {
  13                 bits_buffer = bits_buffer << ((sizeof(unsigned long int)*8) - bits_used);
  14                 vfwrite(&bits_buffer,sizeof(unsigned long int),1,fp);
  15                 bits_buffer = 0;
  16                 bits_used = 0;
  17                 return;
  18         }
  19         /* me indican que comienza un nuevo output */
  20         if (restart) {
  21                 bits_buffer = 0;
  22                 bits_used = 0;
  23         }
  24         /* inserto el bit en el buffer */
  25         bits_buffer = bits_buffer << 1;
  26         bits_buffer |= bit;
  27         bits_used++;
  28
  29         /* lleno el buffer, escribo */
  30         if (bits_used == 32) {
  31                 vfwrite(&bits_buffer,sizeof(unsigned long int),1,fp);
  32                 bits_buffer = 0;
  33                 bits_used = 0;
  34         }
  35         return;
  36 }
  37
  38 void shuff_cpynode(SHUFFNODE *node1, SHUFFNODE *node2)
  39 {
  40         node1->symbol = node2->symbol;
  41         node1->freq = node2->freq;
  42         node1->lchild = node2->lchild;
  43         node1->rchild = node2->rchild;
  44 }
  45
  46 int shuff_compnode(const void *node1, const void *node2)
  47 {
  48         if (((SHUFFNODE*)node1)->freq < ((SHUFFNODE*)node2)->freq) return 1;
  49         if (((SHUFFNODE*)node1)->freq > ((SHUFFNODE*)node2)->freq) return -1;
  50         return 0;
  51 }
  52
  53 int shuff_rescalefreq(t_freq *freqtable)
  54 {
  55         int i;
  56         t_freq totalfreq = 0;
  57
  58         /* Divido por la mitad las frecuencias, asegurando de no perder */
  59         for (i = 0; i < 256; i++) {
  60                 freqtable[i] = (freqtable[i] >> 2) | 1;
  61                 totalfreq += freqtable[i];
  62         }
  63
  64         return totalfreq;
  65 }
  66
  67 int shuff_scanfreq_chunk(HUFF_STATE *chunkshuff, char* chunk, int chunksize)
  68 {
  69         /* Locals */
  70         int i = 0;
  71         unsigned char symbol = 0;
  72
  73         /* Contamos las frecuencias del chunk*/
  74         for (i = 0; i < chunksize; ++i) {
  75                 symbol = chunk[i];
  76                 chunkshuff->freqtable[symbol] += 1;
  77                 chunkshuff->sumfreq += 1;
  78
  79                 /* Si llegue al tope de freq acumulada, halve em */
  80                 if (chunkshuff->sumfreq == 14930352)
  81                         chunkshuff->sumfreq = shuff_rescalefreq(chunkshuff->freqtable);
  82         }
  83
  84         return 1;
  85 }
  86
  87 int shuff_scanfreq(char *inputfile, t_freq *freqtable)
  88 {
  89         /* Locals */
  90         FILE *fp;
  91         t_freq sumfreq = 0;
  92         int i,symbol;
  93
  94         /* Inicializamos la tabla de frecuencias */
  95         for (i = 0; i < 256; ++i) freqtable[i] = 0;
  96
  97         /* Abrimos el file */
  98         if ((fp = fopen(inputfile,"r")) == NULL) return 0;
  99         while (!feof(fp)) {
 100                 /* Contamos las frecuencias */
 101                 symbol = fgetc(fp);
 102                 if (symbol == EOF) continue;
 103
 104                 freqtable[symbol]++;
 105                 ++sumfreq;
 106
 107                 /* Si llegue al tope de freq acumulada, halve em */
 108                 if (sumfreq == 14930352)
 109                         sumfreq = shuff_rescalefreq(freqtable);
 110         }
 111
 112         fclose(fp);
 113         return 1;
 114 }
 115
 116 SHUFFNODE *shuff_buildlist(t_freq *freqtable, int *nonzerofreqs)
 117 {
 118         int i,j = 0,nonzero = 0;
 119         SHUFFNODE *inputlist;
 120
 121         /* Calculo cuantas frequencias > 0 hay y creo la tabla */
 122         for (i = 0; i < 256; ++i) if (freqtable[i] > 0) nonzero++;
 123         inputlist = (SHUFFNODE*)malloc(sizeof(SHUFFNODE)*nonzero);
 124
 125         /* Cargo la inputlist del huffman solo con freqs > 0 */
 126         for (i = 0; i < 256; ++i)
 127                 if (freqtable[i] > 0) {
 128                         inputlist[j].symbol = i;
 129                         inputlist[j].freq = freqtable[i];
 130                         inputlist[j].lchild = NULL;
 131                         inputlist[j].rchild = NULL;
 132                         j++;
 133                 }
 134
 135         *nonzerofreqs = nonzero;
 136         return inputlist;
 137 }
 138
 139 SHUFFNODE *shuff_buildtree(t_freq *ftable)
 140 {
 141         SHUFFNODE *lastsymbol;
 142         SHUFFNODE *node1,*node2,*root;
 143         SHUFFNODE *inputlist;
 144         int freqcount = 0;
 145
 146         /* Genero la input list en base a la cual genera el arbol */
 147         inputlist = shuff_buildlist(ftable, &freqcount);
 148         lastsymbol = inputlist+(freqcount-1);
 149
 150         while (lastsymbol > inputlist) {
 151                 /* Ordeno la lista por frecuencia descendente */
 152                 qsort(inputlist,freqcount,sizeof(SHUFFNODE),shuff_compnode);
 153                 /* Tomo los ultimos dos elementos, generando dos nodos del arbol */
 154                 node1 = (SHUFFNODE*)malloc(sizeof(SHUFFNODE));
 155                 node2 = (SHUFFNODE*)malloc(sizeof(SHUFFNODE));
 156                 shuff_cpynode(node1,lastsymbol-1);
 157                 shuff_cpynode(node2,lastsymbol);
 158                 lastsymbol -= 1;
 159                 /* Nodo ficticio con la suma de las probs y los ptros a childs */
 160                 lastsymbol->symbol = 256;
 161                 lastsymbol->freq = node1->freq + node2->freq;
 162                 lastsymbol->lchild = node1;
 163                 lastsymbol->rchild = node2;
 164                 --freqcount;
 165         }
 166
 167         /* Copio la raiz para poder liberar la lista sin perderla */
 168         root = (SHUFFNODE*)malloc(sizeof(SHUFFNODE));
 169         shuff_cpynode(root,lastsymbol);
 170
 171         /* Free up mem */
 172         free(inputlist);
 173
 174         /* Devuelvo el puntero a la raiz del arbol de huffman */
 175         return root;
 176 }
 177
 178 void shuff_printcodes(SHUFFCODE *codetable,t_freq *freqtable)
 179 {
 180         int i,j;
 181         unsigned short int auxcode;
 182         unsigned char bit;
 183
 184         for (i = 0; i < 256; ++i) {
 185                 if (codetable[i].codelength > 0) {
 186                         auxcode = codetable[i].code;
 187                         printf("Symbol:%i  Freq: %li  Code:",i,freqtable[i]);
 188                         for (j = codetable[i].codelength-1; j >= 0; --j) {
 189                                 auxcode = codetable[i].code;
 190                                 auxcode = auxcode >> j;
 191                                 bit = auxcode & 1;
 192                                 printf("%i",bit);
 193                         }
 194                         printf("  Length:%i\n",codetable[i].codelength);
 195                 }
 196         }
 197 }
 198
 199 void shuff_zerocodes(SHUFFCODE *table)
 200 {
 201         int i;
 202
 203         /* Inicializo los codigos prefijos */
 204         for (i = 0; i < 256; ++i) {
 205                 table[i].code = 0;
 206                 table[i].codelength = 0;
 207         }
 208 }
 209
 210 void shuff_buildcodes(SHUFFCODE *table, SHUFFNODE *node, int level, int code)
 211 {
 212         if (node->symbol < 256) {
 213                 /* Guardo el codigo en la tabla */
 214                 table[node->symbol].code = code;
 215                 table[node->symbol].codelength = level;
 216         }
 217         else {
 218                 code = code << 1;
 219                 shuff_buildcodes(table,node->lchild,level+1,code);
 220                 code |= 1;
 221                 shuff_buildcodes(table,node->rchild,level+1,code);
 222         }
 223 }
 224
 225 int shuff_encode_symbols(HUFF_STATE *shuff, SHUFFCODE *ctable)
 226 {
 227         FILE *fpsource;
 228         VFILE *fpdest;
 229         int symbol,i;
 230         unsigned long int sourcesize;
 231         char bit;
 232         SHUFFCODE symbolcode;
 233
 234         /* Abrimos el file */
 235         if ((fpsource = fopen(shuff->sourcefile,"r")) == NULL) return 0;
 236         if ((fpdest = vfopen(shuff->targetfile,"w",shuff->volsize)) == NULL) return 0;
 237
 238         /* Guardamos el size el archivo original e inputlist como header */
 239         fseek(fpsource,0,SEEK_END);
 240         sourcesize = ftell(fpsource);
 241         vfwrite(&sourcesize,sizeof(unsigned long int),1,fpdest);
 242         vfwrite(shuff->freqtable,sizeof(t_freq),256,fpdest);
 243
 244         /* Encodeo */
 245         fseek(fpsource,0,SEEK_SET);
 246         while (!feof(fpsource)) {
 247                 /* Levanto un symbolo (byte) */
 248                 symbol = fgetc(fpsource);
 249                 if (symbol == EOF) continue;
 250
 251                 /* Cargamos el codigo y lo emitimos */
 252                 symbolcode = ctable[symbol];
 253                 for (i = symbolcode.codelength; i > 0; --i) {
 254                         bit = (symbolcode.code >> (i-1)) & 1;
 255                         putbit(bit,0,0,fpdest);
 256                 }
 257         }
 258
 259         /* Hacemos un flush de lo que haya quedado en el buffer de salida */
 260         putbit(0,0,1,fpdest);
 261         fclose(fpsource);
 262         vfclose(fpdest);
 263         return 1;
 264 }
 265
 266 int shuff_encode_chunk(HUFF_STATE *chunkshuff, char *chunk, int chunksize, int process)
 267 {
 268         int i;
 269
 270         if (!process) {
 271                 /* Scaneo las frecuencias de este chunk */
 272                 shuff_scanfreq_chunk(chunkshuff,chunk,chunksize);
 273         }
 274         else {
 275                 /* Ya tengo la tabla y el archivo temporal, paso al huffman by file */
 276                 return 0;
 277         }
 278
 279         return 1;
 280 }
 281
 282 HUFF_STATE *shuff_init_static_byfile(char *inputfile, char *outputfile, long volsize)
 283 {
 284         /* Locals */
 285         HUFF_STATE *fshuff = (HUFF_STATE*)malloc(sizeof(HUFF_STATE));
 286         int i;
 287
 288         /* Inicializo la estructura para trabajar con Huff Static by File */
 289         fshuff->tmpfp = NULL;
 290         fshuff->sourcefile = (char*)malloc(sizeof(char)*(strlen(inputfile)+1));
 291         fshuff->targetfile = (char*)malloc(sizeof(char)*(strlen(outputfile)+1));
 292         strcpy(fshuff->sourcefile,inputfile);
 293         strcpy(fshuff->targetfile,outputfile);
 294         fshuff->preloadfreq = 0;
 295         fshuff->volsize = volsize;
 296         fshuff->sumfreq = 0;
 297         fshuff->freqtable = (t_freq*)malloc(sizeof(t_freq)*256);
 298         for (i = 0; i < 256; ++i) fshuff->freqtable[i] = 0;
 299
 300         return fshuff;
 301 }
 302
 303 HUFF_STATE *shuff_init_static_bychunk(char *outputfile, long volsize)
 304 {
 305         /* Locals */
 306         HUFF_STATE *cshuff = (HUFF_STATE*)malloc(sizeof(HUFF_STATE));
 307         FILE *fp;
 308         int i;
 309
 310         /* Inicializo la estructura para trabajar con Huff Static by Chunks */
 311         cshuff->sourcefile = (char*)malloc(sizeof(char)*(strlen(outputfile)+2));
 312         cshuff->targetfile = (char*)malloc(sizeof(char)*(strlen(outputfile)+1));
 313         strcpy(cshuff->targetfile,outputfile);
 314         strcpy(cshuff->sourcefile,outputfile);
 315         strcat(cshuff->sourcefile,"~");
 316         cshuff->volsize = volsize;
 317         cshuff->preloadfreq = 1;
 318         cshuff->sumfreq = 0;
 319         cshuff->freqtable = (t_freq*)malloc(sizeof(t_freq)*256);
 320         for (i = 0; i < 256; ++i) cshuff->freqtable[i] = 0;
 321
 322         /* Abrimos un archivo temporal para ir tirando los chunks */
 323         if ((cshuff->tmpfp = fopen(cshuff->sourcefile,"w")) == NULL) return NULL;
 324
 325         return cshuff;
 326 }
 327
 328 void shuff_deinit_static_byfile(HUFF_STATE *fshuff)
 329 {
 330         /* Libero mallocs y cierro archivos */
 331         free(fshuff->freqtable);
 332         free(fshuff->sourcefile);
 333         free(fshuff->targetfile);
 334 }
 335
 336 void shuff_deinit_static_bychunk(HUFF_STATE *cshuff)
 337 {
 338         /* Libero mallocs y cierro archivos */
 339         free(cshuff->freqtable);
 340         free(cshuff->sourcefile);
 341         free(cshuff->targetfile);
 342         fclose(cshuff->tmpfp);
 343 }
 344
 345 int shuff_encode_file(HUFF_STATE *shuff)
 346 {
 347         /* Locals */
 348         SHUFFNODE *codetree;
 349         SHUFFCODE *codetable = (SHUFFCODE*)malloc(sizeof(SHUFFCODE)*256);
 350         int i;
 351
 352         /* Veo si debo armar una freqtable o si esta preloaded */
 353         if (!shuff->preloadfreq) if (!shuff_scanfreq(shuff->sourcefile,shuff->freqtable)) return 0;
 354
 355         /* Genero el arbol de huffman */
 356         codetree = shuff_buildtree(shuff->freqtable);
 357
 358         /* Armo la tabla de codigos prefijos para el encoder */
 359         shuff_zerocodes(codetable);
 360         shuff_buildcodes(codetable,codetree,0,0);
 361         /*shuff_printcodes(codetable,shuff->freqtable);*/
 362
 363         /* Encodeo byte per byte */
 364         shuff_encode_symbols(shuff,codetable);
 365
 366         /* Free up memory baby yeah */
 367         free(codetable);
 368
 369         /* Destruyo el arbol recursivamente TODO */
 370
 371         return 1;
 372 }
 373
 374 SHUFFNODE *shuff_decode_symbols(SHUFFNODE *entrynode, unsigned long int buffer,
 375                                                          int *bitsleft, unsigned short int *symbol)
 376 {
 377         char bit = 0;
 378
 379         /* Levanto el symbolo y si es uno valido, devuelvo */
 380         *symbol = entrynode->symbol;
 381         if (*symbol != 256) return entrynode;
 382         if (*bitsleft == 0) return entrynode;
 383
 384         /* Obtengo otro bit a procesar y me muevo en el arbol */
 385         bit = (buffer >> ((*bitsleft)-1)) & 1;
 386         --(*bitsleft);
 387         if (bit == 0) return shuff_decode_symbols(entrynode->lchild,buffer,bitsleft,symbol);
 388         else return shuff_decode_symbols(entrynode->rchild,buffer,bitsleft,symbol);
 389 }
 390
 391 int shuff_decode_file(HUFF_STATE *shuff)
 392 {
 393         SHUFFNODE *codetree,*currnode;
 394         unsigned long int bytesleft,codebuffer;
 395         VFILE *fpsource;
 396         FILE *fpdest;
 397         unsigned short int decoded_symbol;
 398         int bitsleft,freqcount = 0;
 399
 400         /* Levanto cuantos bytes decodeo y la freq table */
 401         if ((fpsource = vfopen(shuff->sourcefile,"r",0)) == NULL) return 0;
 402         if ((fpdest = fopen(shuff->targetfile,"w")) == NULL) return 0;
 403         vfread(&bytesleft,sizeof(unsigned long int),1,fpsource);
 404         vfread(shuff->freqtable,sizeof(unsigned long int),256,fpsource);
 405         codetree = shuff_buildtree(shuff->freqtable);
 406         currnode = codetree;
 407
 408         while (!vfeof(fpsource) && (bytesleft > 0)) {
 409
 410                 /* Leo un buffer de 32 bits */
 411                 if (vfread(&codebuffer,sizeof(unsigned long int),1,fpsource) != 1) continue;
 412                 bitsleft = sizeof(unsigned long int) * 8;
 413
 414                 /* Proceso el buffer sacando simbolos hasta que se me agote */
 415                 while ((bitsleft > 0) && (bytesleft > 0)) {
 416                         currnode = shuff_decode_symbols(currnode,codebuffer,&bitsleft,&decoded_symbol);
 417                         /* Si obtuve un symbolo valido lo emito*/
 418                         if (decoded_symbol != 256) {
 419                                 fputc(decoded_symbol,fpdest);
 420                                 currnode = codetree;
 421                                 --bytesleft;
 422                         }
 423                 }
 424         }
 425
 426         vfclose(fpsource);
 427         fclose(fpdest);
 428
 429         /* Libero el arbol recursivamente TODO */
 430
 431         return 1;
 432 }