src/statichuff/statichuff.c

   1
   2 #include <stdio.h>
   3
   4 typedef unsigned long int t_freq;
   5
   6 typedef struct t_freqnode {
   7         unsigned short int symbol;
   8         t_freq freq;
   9         struct t_freqnode *lchild;
  10         struct t_freqnode *rchild;
  11 } HUFFNODE;
  12
  13 typedef struct t_code {
  14         unsigned long int code;
  15         unsigned char codelength;
  16 } CODE;
  17
  18 void putbit(char bit, char restart, char flush, FILE *fp)
  19 {
  20         static unsigned long int bits_buffer = 0;
  21         static unsigned char bits_used = 0;
  22
  23         /* me obligan a tirar el output */
  24         if ((flush == 1) && (bits_used > 0)) {
  25                 fwrite(&bits_buffer,sizeof(unsigned long int),1,fp);
  26                 bits_buffer = 0;
  27                 bits_used = 0;
  28                 return;
  29         }
  30         /* me indican que comienza un nuevo output */
  31         if (restart) {
  32                 bits_buffer = 0;
  33                 bits_used = 0;
  34         }
  35         /* inserto el bit en el buffer */
  36         bits_buffer = bits_buffer << 1;
  37         bits_buffer |= bit;
  38         bits_used++;
  39
  40         /* lleno el buffer, escribo */
  41         if (bits_used == 32) {
  42                 fwrite(&bits_buffer,sizeof(unsigned long int),1,fp);
  43                 bits_buffer = 0;
  44                 bits_used = 0;
  45         }
  46         return;
  47 }
  48
  49 void cpynode(HUFFNODE *node1, HUFFNODE *node2)
  50 {
  51         node1->symbol = node2->symbol;
  52         node1->freq = node2->freq;
  53         node1->lchild = node2->lchild;
  54         node1->rchild = node2->rchild;
  55 }
  56
  57 int compnode(HUFFNODE *node1, HUFFNODE *node2)
  58 {
  59         if (node1->freq < node2->freq) return 1;
  60         if (node1->freq > node2->freq) return -1;
  61         return 0;
  62 }
  63
  64 HUFFNODE *buildlist(t_freq *freqtable, int *nonzerofreqs)
  65 {
  66         int i,j = 0,nonzero = 0;
  67         HUFFNODE *inputlist;
  68
  69         /* Calculo cuantas frequencias > 0 hay y creo la tabla */
  70         for (i = 0; i < 256; ++i) if (freqtable[i] > 0) nonzero++;
  71         inputlist = (HUFFNODE*)malloc(sizeof(HUFFNODE)*nonzero);
  72
  73         /* Cargo la inputlist del huffman solo con freqs > 0 */
  74         for (i = 0; i < 256; ++i)
  75                 if (freqtable[i] > 0) {
  76                         inputlist[j].symbol = i;
  77                         inputlist[j].freq = freqtable[i];
  78                         inputlist[j].lchild = NULL;
  79                         inputlist[j].rchild = NULL;
  80                         j++;
  81                 }
  82
  83         *nonzerofreqs = nonzero;
  84         return inputlist;
  85 }
  86
  87 int rescalefreq(t_freq *freqtable)
  88 {
  89         int i;
  90         t_freq totalfreq = 0;
  91
  92         /* Divido por la mitad las frecuencias, asegurando de no perder */
  93         /* frequencias en 1, por ello le sumo 1 antes de partir */
  94         for (i = 0; i < 256; i++) {
  95                 freqtable[i] = (freqtable[i] << 2) | 1;
  96                 totalfreq += freqtable[i];
  97         }
  98
  99         return totalfreq;
 100 }
 101
 102 int scanfreq(char *inputfile, t_freq *freqtable)
 103 {
 104         /* Locals */
 105         FILE *fp;
 106         t_freq sumfreq = 0;
 107         int i,symbol;
 108
 109         /* Inicializamos la tabla de frecuencias */
 110         for (i = 0; i < 256; ++i) freqtable[i] = 0;
 111
 112         /* Abrimos el file */
 113         if ((fp = fopen(inputfile,"rb")) == NULL) return 0;
 114         while (!feof(fp)) {
 115                 /* Contamos las frecuencias */
 116                 symbol = fgetc(fp);
 117                 if (symbol == EOF) continue;
 118
 119                 freqtable[symbol]++;
 120                 ++sumfreq;
 121
 122                 /* Si llegue al tope de freq acumulada, halve em */
 123                 if (sumfreq == 14930352)
 124                         sumfreq = rescalefreq(freqtable);
 125         }
 126
 127         fclose(fp);
 128         return 1;
 129 }
 130
 131 void printcodes(CODE *codetable,t_freq *freqtable)
 132 {
 133         int i,j;
 134         unsigned short int auxcode;
 135         unsigned char bit;
 136
 137         for (i = 0; i < 256; ++i) {
 138                 if (codetable[i].codelength > 0) {
 139                         auxcode = codetable[i].code;
 140                         printf("Symbol:%i  Freq: %li  Code:",i,freqtable[i]);
 141                         for (j = codetable[i].codelength-1; j >= 0; --j) {
 142                                 auxcode = codetable[i].code;
 143                                 auxcode = auxcode >> j;
 144                                 bit = auxcode & 1;
 145                                 printf("%i",bit);
 146                         }
 147                         printf("  Length:%i\n",codetable[i].codelength);
 148                 }
 149         }
 150 }
 151
 152 void zerocodes(CODE *table)
 153 {
 154         int i;
 155
 156         /* Inicializo los codigos prefijos */
 157         for (i = 0; i < 256; ++i) {
 158                 table[i].code = 0;
 159                 table[i].codelength = 0;
 160         }
 161 }
 162
 163 void buildcodes(CODE *table, HUFFNODE *node, int level, int code)
 164 {
 165         if (node->symbol < 256) {
 166                 /* Guardo el codigo en la tabla */
 167                 table[node->symbol].code = code;
 168                 table[node->symbol].codelength = level;
 169         }
 170         else {
 171                 code = code << 1;
 172                 buildcodes(table,node->lchild,level+1,code);
 173                 code |= 1;
 174                 buildcodes(table,node->rchild,level+1,code);
 175         }
 176 }
 177
 178 HUFFNODE *buildtree(HUFFNODE *list, int listcount)
 179 {
 180         HUFFNODE *lastsymbol = list+(listcount-1);
 181         HUFFNODE *node1,*node2,*fictnode;
 182
 183         /* Ordenamos inicialmente la inputlist para tomar las dos freqs min */
 184         while (lastsymbol > list) {
 185                 /* Ordeno la lista por frecuencia descendente */
 186                 qsort(list,listcount,sizeof(HUFFNODE),compnode);
 187                 /* Tomo los ultimos dos elementos, generando dos nodos del arbol */
 188                 node1 = (HUFFNODE*)malloc(sizeof(HUFFNODE));
 189                 node2 = (HUFFNODE*)malloc(sizeof(HUFFNODE));
 190                 cpynode(node1,lastsymbol-1);
 191                 cpynode(node2,lastsymbol);
 192                 lastsymbol -= 1;
 193                 /* Nodo ficticio con la suma de las probs y los ptros a childs */
 194                 lastsymbol->symbol = 256;
 195                 lastsymbol->freq = node1->freq + node2->freq;
 196                 lastsymbol->lchild = node1;
 197                 lastsymbol->rchild = node2;
 198                 --listcount;
 199         }
 200
 201         /* Devuelvo el puntero a la raiz del arbol de huffman */
 202         return lastsymbol;
 203 }
 204
 205 int encode(CODE *table, char* inputfile, char *outputfile) {
 206
 207         FILE *fpsource,*fpdest;
 208         int symbol,i;
 209         char bit;
 210         CODE symbolcode;
 211
 212         /* Abrimos el file */
 213         if ((fpsource = fopen(inputfile,"rb")) == NULL) return 0;
 214         if ((fpdest = fopen(outputfile,"wb")) == NULL) return 0;
 215
 216         while (!feof(fpsource)) {
 217                 /* Levanto un symbolo (byte) */
 218                 symbol = fgetc(fpsource);
 219                 if (symbol == EOF) continue;
 220
 221                 /* Cargamos el codigo y lo emitimos */
 222                 symbolcode = table[symbol];
 223                 for (i = symbolcode.codelength; i > 0; --i) {
 224                         bit = (symbolcode.code >> (i-1)) & 1;
 225                         putbit(bit,0,0,fpdest);
 226                 }
 227         }
 228
 229         /* Hacemos un flush de lo que haya quedado en el buffer de salida */
 230         putbit(0,0,1,fpdest);
 231         fclose(fpsource);
 232         fclose(fpdest);
 233         return 1;
 234 }
 235
 236 int main(int argc, char* argv[])
 237 {
 238         /* Locals */
 239         t_freq *freqtable = (t_freq*)malloc(sizeof(t_freq)*256);
 240         HUFFNODE *inputlist;
 241         HUFFNODE *codetree;
 242         CODE *codetable = (CODE*)malloc(sizeof(CODE)*256);
 243         int freqcount = 0,i;
 244
 245         if (argc == 1) return -1;
 246
 247         /* Armamos la tabla de frecuencias */
 248         if (!scanfreq(argv[1],freqtable)) return -1;
 249
 250         /* Armo el input list y genero el arbol de huffman */
 251         inputlist = buildlist(freqtable, &freqcount);
 252         codetree = buildtree(inputlist,freqcount);
 253         /* Armo la tabla de codigos prefijos para el encoder */
 254         zerocodes(codetable);
 255         buildcodes(codetable,codetree,0,0);
 256         printcodes(codetable,freqtable);
 257         encode(codetable,argv[1],"output.dat");
 258
 259         return 0;
 260 }