src/statichuff/statichuff.c

   1
   2 #include "statichuff.h"
   3
   4 void putbit(char bit, char restart, char flush, FILE *fp)
   5 {
   6         static unsigned long int bits_buffer = 0;
   7         static unsigned char bits_used = 0;
   8
   9         /* me obligan a emitir el output */
  10         if ((flush == 1) && (bits_used > 0)) {
  11                 bits_buffer = bits_buffer << ((sizeof(unsigned long int)*8) - bits_used);
  12                 fwrite(&bits_buffer,sizeof(unsigned long int),1,fp);
  13                 bits_buffer = 0;
  14                 bits_used = 0;
  15                 return;
  16         }
  17         /* me indican que comienza un nuevo output */
  18         if (restart) {
  19                 bits_buffer = 0;
  20                 bits_used = 0;
  21         }
  22         /* inserto el bit en el buffer */
  23         bits_buffer = bits_buffer << 1;
  24         bits_buffer |= bit;
  25         bits_used++;
  26
  27         /* lleno el buffer, escribo */
  28         if (bits_used == 32) {
  29                 fwrite(&bits_buffer,sizeof(unsigned long int),1,fp);
  30                 bits_buffer = 0;
  31                 bits_used = 0;
  32         }
  33         return;
  34 }
  35
  36 void shuff_cpynode(SHUFFNODE *node1, SHUFFNODE *node2)
  37 {
  38         node1->symbol = node2->symbol;
  39         node1->freq = node2->freq;
  40         node1->lchild = node2->lchild;
  41         node1->rchild = node2->rchild;
  42 }
  43
  44 int shuff_compnode(const void *node1, const void *node2)
  45 {
  46         if (((SHUFFNODE*)node1)->freq < ((SHUFFNODE*)node2)->freq) return 1;
  47         if (((SHUFFNODE*)node1)->freq > ((SHUFFNODE*)node2)->freq) return -1;
  48         return 0;
  49 }
  50
  51 int shuff_rescalefreq(t_freq *freqtable)
  52 {
  53         int i;
  54         t_freq totalfreq = 0;
  55
  56         /* Divido por la mitad las frecuencias, asegurando de no perder */
  57         /* frequencias en 1, por ello le sumo 1 antes de partir */
  58         for (i = 0; i < 256; i++) {
  59                 freqtable[i] = (freqtable[i] << 2) | 1;
  60                 totalfreq += freqtable[i];
  61         }
  62
  63         return totalfreq;
  64 }
  65
  66 int shuff_scanfreq(char *inputfile, t_freq *freqtable)
  67 {
  68         /* Locals */
  69         FILE *fp;
  70         t_freq sumfreq = 0;
  71         int i,symbol;
  72
  73         /* Inicializamos la tabla de frecuencias */
  74         for (i = 0; i < 256; ++i) freqtable[i] = 0;
  75
  76         /* Abrimos el file */
  77         if ((fp = fopen(inputfile,"rb")) == NULL) return 0;
  78         while (!feof(fp)) {
  79                 /* Contamos las frecuencias */
  80                 symbol = fgetc(fp);
  81                 if (symbol == EOF) continue;
  82
  83                 freqtable[symbol]++;
  84                 ++sumfreq;
  85
  86                 /* Si llegue al tope de freq acumulada, halve em */
  87                 if (sumfreq == 14930352)
  88                         sumfreq = shuff_rescalefreq(freqtable);
  89         }
  90
  91         fclose(fp);
  92         return 1;
  93 }
  94
  95 SHUFFNODE *shuff_buildlist(t_freq *freqtable, int *nonzerofreqs)
  96 {
  97         int i,j = 0,nonzero = 0;
  98         SHUFFNODE *inputlist;
  99
 100         /* Calculo cuantas frequencias > 0 hay y creo la tabla */
 101         for (i = 0; i < 256; ++i) if (freqtable[i] > 0) nonzero++;
 102         inputlist = (SHUFFNODE*)malloc(sizeof(SHUFFNODE)*nonzero);
 103
 104         /* Cargo la inputlist del huffman solo con freqs > 0 */
 105         for (i = 0; i < 256; ++i)
 106                 if (freqtable[i] > 0) {
 107                         inputlist[j].symbol = i;
 108                         inputlist[j].freq = freqtable[i];
 109                         inputlist[j].lchild = NULL;
 110                         inputlist[j].rchild = NULL;
 111                         j++;
 112                 }
 113
 114         *nonzerofreqs = nonzero;
 115         return inputlist;
 116 }
 117
 118 SHUFFNODE *shuff_buildtree(SHUFFNODE *list, int listcount)
 119 {
 120         SHUFFNODE *lastsymbol = list+(listcount-1);
 121         SHUFFNODE *node1,*node2;
 122
 123         while (lastsymbol > list) {
 124                 /* Ordeno la lista por frecuencia descendente */
 125                 qsort(list,listcount,sizeof(SHUFFNODE),shuff_compnode);
 126                 /* Tomo los ultimos dos elementos, generando dos nodos del arbol */
 127                 node1 = (SHUFFNODE*)malloc(sizeof(SHUFFNODE));
 128                 node2 = (SHUFFNODE*)malloc(sizeof(SHUFFNODE));
 129                 shuff_cpynode(node1,lastsymbol-1);
 130                 shuff_cpynode(node2,lastsymbol);
 131                 lastsymbol -= 1;
 132                 /* Nodo ficticio con la suma de las probs y los ptros a childs */
 133                 lastsymbol->symbol = 256;
 134                 lastsymbol->freq = node1->freq + node2->freq;
 135                 lastsymbol->lchild = node1;
 136                 lastsymbol->rchild = node2;
 137                 --listcount;
 138         }
 139
 140         /* Devuelvo el puntero a la raiz del arbol de huffman */
 141         return lastsymbol;
 142 }
 143
 144 void shuff_printcodes(SHUFFCODE *codetable,t_freq *freqtable)
 145 {
 146         int i,j;
 147         unsigned short int auxcode;
 148         unsigned char bit;
 149
 150         for (i = 0; i < 256; ++i) {
 151                 if (codetable[i].codelength > 0) {
 152                         auxcode = codetable[i].code;
 153                         printf("Symbol:%i  Freq: %li  Code:",i,freqtable[i]);
 154                         for (j = codetable[i].codelength-1; j >= 0; --j) {
 155                                 auxcode = codetable[i].code;
 156                                 auxcode = auxcode >> j;
 157                                 bit = auxcode & 1;
 158                                 printf("%i",bit);
 159                         }
 160                         printf("  Length:%i\n",codetable[i].codelength);
 161                 }
 162         }
 163 }
 164
 165 void shuff_zerocodes(SHUFFCODE *table)
 166 {
 167         int i;
 168
 169         /* Inicializo los codigos prefijos */
 170         for (i = 0; i < 256; ++i) {
 171                 table[i].code = 0;
 172                 table[i].codelength = 0;
 173         }
 174 }
 175
 176 void shuff_buildcodes(SHUFFCODE *table, SHUFFNODE *node, int level, int code)
 177 {
 178         if (node->symbol < 256) {
 179                 /* Guardo el codigo en la tabla */
 180                 table[node->symbol].code = code;
 181                 table[node->symbol].codelength = level;
 182         }
 183         else {
 184                 code = code << 1;
 185                 shuff_buildcodes(table,node->lchild,level+1,code);
 186                 code |= 1;
 187                 shuff_buildcodes(table,node->rchild,level+1,code);
 188         }
 189 }
 190
 191
 192
 193 int shuff_encode_symbols(t_freq *ftable, SHUFFCODE *ctable, char* inputfile, char *outputfile) {
 194
 195         FILE *fpsource,*fpdest;
 196         int symbol,i;
 197         unsigned long int sourcesize;
 198         char bit;
 199         SHUFFCODE symbolcode;
 200
 201         /* Abrimos el file */
 202         if ((fpsource = fopen(inputfile,"rb")) == NULL) return 0;
 203         if ((fpdest = fopen(outputfile,"wb")) == NULL) return 0;
 204
 205         /* Guardamos el size el archivo original e inputlist como header */
 206         fseek(fpsource,0,SEEK_END);
 207         sourcesize = ftell(fpsource);
 208         fwrite(&sourcesize,sizeof(unsigned long int),1,fpdest);
 209         fwrite(ftable,sizeof(t_freq),256,fpdest);
 210
 211         /* Encodeo */
 212         fseek(fpsource,0,SEEK_SET);
 213         while (!feof(fpsource)) {
 214                 /* Levanto un symbolo (byte) */
 215                 symbol = fgetc(fpsource);
 216                 if (symbol == EOF) continue;
 217
 218                 /* Cargamos el codigo y lo emitimos */
 219                 symbolcode = ctable[symbol];
 220                 for (i = symbolcode.codelength; i > 0; --i) {
 221                         bit = (symbolcode.code >> (i-1)) & 1;
 222                         putbit(bit,0,0,fpdest);
 223                 }
 224         }
 225
 226         /* Hacemos un flush de lo que haya quedado en el buffer de salida */
 227         putbit(0,0,1,fpdest);
 228         fclose(fpsource);
 229         fclose(fpdest);
 230         return 1;
 231 }
 232
 233 int shuff_encode_file(char *inputfile, char *outputfile)
 234 {
 235         /* Locals */
 236         t_freq *freqtable = (t_freq*)malloc(sizeof(t_freq)*256);
 237         SHUFFNODE *inputlist;
 238         SHUFFNODE *codetree;
 239         SHUFFCODE *codetable = (SHUFFCODE*)malloc(sizeof(SHUFFCODE)*256);
 240         int freqcount = 0;
 241
 242         /* Armamos la tabla de frecuencias */
 243         if (!shuff_scanfreq(inputfile,freqtable)) return 0;
 244
 245         /* Armo el input list y genero el arbol de huffman */
 246         inputlist = shuff_buildlist(freqtable, &freqcount);
 247         codetree = shuff_buildtree(inputlist,freqcount);
 248
 249         /* Armo la tabla de codigos prefijos para el encoder */
 250         shuff_zerocodes(codetable);
 251         shuff_buildcodes(codetable,codetree,0,0);
 252         /*shuff_printcodes(codetable,freqtable);*/
 253
 254         /* Encodeo byte per byte */
 255         shuff_encode_symbols(freqtable,codetable,inputfile,outputfile);
 256
 257         /* Free up memory baby yeah */
 258         free(freqtable);
 259         free(inputlist);
 260         free(codetable);
 261
 262         return 1;
 263 }
 264
 265 SHUFFNODE *shuff_decode_symbols(SHUFFNODE *entrynode, unsigned long int buffer,
 266                                                          int *bitsleft, unsigned short int *symbol)
 267 {
 268         char bit = 0;
 269
 270         /* Levanto el symbolo y si es uno valido, devuelvo */
 271         *symbol = entrynode->symbol;
 272         if (*symbol != 256) return entrynode;
 273         if (*bitsleft == 0) return entrynode;
 274
 275         /* Obtengo otro bit a procesar y me muevo en el arbol */
 276         bit = (buffer >> ((*bitsleft)-1)) & 1;
 277         --(*bitsleft);
 278         if (bit == 0) return shuff_decode_symbols(entrynode->lchild,buffer,bitsleft,symbol);
 279         else return shuff_decode_symbols(entrynode->rchild,buffer,bitsleft,symbol);
 280 }
 281
 282 int shuff_decode_file(char *inputfile, char *outputfile)
 283 {
 284         SHUFFNODE *inputlist;
 285         SHUFFNODE *codetree,*currnode;
 286         t_freq *ftable = (t_freq*)malloc(sizeof(t_freq)*256);
 287         unsigned long int bytesleft,codebuffer;
 288         FILE *fpsource;
 289         FILE *fpdest;
 290         unsigned short int decoded_symbol;
 291         int bitsleft,freqcount = 0;
 292
 293         /* Levanto cuantos bytes decodeo y la freq table */
 294         if ((fpsource = fopen(inputfile,"rb")) == NULL) return 0;
 295         if ((fpdest = fopen(outputfile,"wb")) == NULL) return 0;
 296         fread(&bytesleft,sizeof(unsigned long int),1,fpsource);
 297         fread(ftable,sizeof(unsigned long int),256,fpsource);
 298         inputlist = shuff_buildlist(ftable, &freqcount);
 299         codetree = shuff_buildtree(inputlist,freqcount);
 300         currnode = codetree;
 301
 302         while (!feof(fpsource) && (bytesleft > 0)) {
 303
 304                 /* Leo un buffer de 32 bits */
 305                 if (fread(&codebuffer,sizeof(unsigned long int),1,fpsource) != 1) continue;
 306                 bitsleft = sizeof(unsigned long int) * 8;
 307
 308                 /* Proceso el buffer sacando simbolos hasta que se me agote */
 309                 while ((bitsleft > 0) && (bytesleft > 0)) {
 310                         currnode = shuff_decode_symbols(currnode,codebuffer,&bitsleft,&decoded_symbol);
 311                         /* Si obtuve un symbolo valido lo emito*/
 312                         if (decoded_symbol != 256) {
 313                                 fputc(decoded_symbol,fpdest);
 314                                 currnode = codetree;
 315                                 --bytesleft;
 316                         }
 317                 }
 318         }
 319
 320         fclose(fpsource);
 321         fclose(fpdest);
 322
 323         /* Free up memory baby yeah */
 324         free(ftable);
 325         free(inputlist);
 326
 327         return 1;
 328 }
 329