swcsa/utils/huff.c

   1
   2 // implements canonical Huffman
   3
   4 #include "huff.h"
   5
   6 typedef struct
   7    { uint freq;
   8      uint symb;
   9      union
  10        { int prev;
  11          int depth;
  12        } h;
  13      int ch1,ch2;
  14    } Ttree;
  15
  16 static void sort (Ttree *tree, int lo, int up)
  17
  18    { int i, j;
  19      Ttree temp;
  20      while (up>lo)
  21         { i = lo;
  22           j = up;
  23           temp = tree[lo];
  24           while (i<j)
  25              { while (tree[j].freq > temp.freq) j--;
  26                tree[i] = tree[j];
  27                while (i<j && tree[i].freq <= temp.freq) i++;
  28                tree[j] = tree[i];
  29              }
  30           tree[i] = temp;
  31           if (i-lo < up-i) { sort(tree,lo,i-1); lo = i+1; }
  32           else { sort(tree,i+1,up); up = i-1; }
  33         }
  34    }
  35
  36 static void setdepths (Ttree *tree, uint node, int depth)
  37
  38    { if (tree[node].ch1 == -1) // leaf
  39         { tree[node].h.depth = depth;
  40           return;
  41         }
  42      setdepths (tree,tree[node].ch1,depth+1);
  43      setdepths (tree,tree[node].ch2,depth+1);
  44    }
  45
  46
  47 THuff createHuff (uint *freq, uint lim, uint sorted)
  48
  49    { THuff H;
  50      int i,j,d;
  51      Ttree *tree;
  52      int ptr,last,fre;
  53          // remove zero frequencies
  54      H.max = lim;
  55      H.total = 0;
  56
  57      int onlyOneSymbol = (lim ==0);
  58
  59         //     tree = malloc((2*(lim+1)-1)*sizeof(Ttree));
  60                 /*** BEG FARI... para solucionar caso en que s�lo hubiese un �nico s�mbolo a codificar ****/
  61                  if (onlyOneSymbol) {
  62                         tree = (Ttree *)malloc(3*sizeof(Ttree));  //root, the valid node (pos 0) and the "zeroNode" (pos 1)
  63                         H.max =  lim+1;
  64                 }
  65                  else
  66                         tree =  (Ttree *)malloc((2*(lim+1)-1)*sizeof(Ttree));
  67         /*** END FARI... para solucionar caso en que s�lo hubiese un �nico s�mbolo a codificar ****/
  68
  69      //fprintf(stderr,"\n **** CALLED CREATE_HUFF WITH  lim = %ld, freq[0]=%ld",lim,freq[0]);
  70      j = 0;
  71      for (i=0;i<=lim;i++)
  72         { if (freq[i]>0)
  73              { tree[j].freq = freq[i];
  74                tree[j].symb = i;
  75                j++;
  76                //fprintf(stderr,"\n freq[%d] = [%d], para s�mbolo %d, now j=%ld",i,freq[i],tree[j-1].symb,j);
  77              }
  78         }
  79
  80         /*** BEG FARI... para solucionar caso en que s�lo hubiese un �nico s�mbolo a codificar ****/
  81                 if (onlyOneSymbol){
  82                         tree[j].freq = 0;
  83                         tree[j++].symb = 1; //<--- !!!!!!!!! (incrementa j !!!)
  84
  85                         //H.total -=1 * 1;     //we will add 1*1 at the end of this function.
  86
  87                 }
  88                  //fprintf(stderr,"\n");
  89
  90         /*** END FARI... para solucionar caso en que s�lo hubiese un �nico s�mbolo a codificar ****/
  91
  92         H.lim = lim = j-1;
  93
  94
  95         // now run Huffman algorithm
  96      if (!sorted) sort (tree,0,lim);
  97
  98      for (i=0;i<=lim;i++) {
  99        //fprintf(stderr,"\n    XX freq[%d] = [%d], para symbolo %d",i,tree[i].freq,tree[i].symb);
 100        tree[i].h.prev = i+1;
 101            tree[i].ch1 = tree[i].ch2 = -1;
 102          }
 103      tree[lim].h.prev = -1;
 104     // last = next node to process, ptr = search point, fre = next free cell
 105         // leaves are in 0..lim in decreasing freq order
 106         // internal nodes are in lim+1.. 2*lim, created in incr. fre order
 107      last=0; ptr = 0; fre = lim+1;
 108      for (i=0;i<lim;i++)
 109         { tree[fre].ch1 = last;
 110           last = tree[last].h.prev;
 111           tree[fre].ch2 = last;
 112           tree[fre].freq = tree[tree[fre].ch1].freq+tree[tree[fre].ch2].freq;
 113           while ((tree[ptr].h.prev != -1) &&
 114                  (tree[tree[ptr].h.prev].freq <= tree[fre].freq))
 115               ptr = tree[ptr].h.prev;
 116           tree[fre].h.prev = tree[ptr].h.prev;
 117           tree[ptr].h.prev = fre;
 118           last = tree[last].h.prev;
 119           fre++;
 120         }
 121         // now assign depths recursively
 122      setdepths (tree,2*lim,0);
 123      H.s.spos = (uint *)malloc ((H.max+1)*sizeof(uint));
 124      for (i=0;i<=H.max;i++) H.s.spos[i] = ~0;
 125      H.num = (uint *)malloc ((lim+1)*sizeof(uint)); // max possible depth
 126      d=0;
 127      for (i=lim;i>=0;i--)
 128         { H.s.spos[tree[i].symb] = i;
 129           while (tree[i].h.depth > d)
 130               { H.num[d] = i+1; d++; }
 131         }
 132      H.num[d] = 0;
 133      H.depth = d;
 134      for (d=H.depth;d>0;d--) H.num[d] = H.num[d-1] - H.num[d];
 135      H.num[0] = (lim == 0);
 136      H.num = (uint *) realloc(H.num,(H.depth+1)*sizeof(uint));
 137      //H.total = 0;
 138
 139
 140
 141
 142      if (onlyOneSymbol){        H.total += freq[tree[0].symb] * tree[0].h.depth;}
 143      else {
 144              for (i=0;i<=lim;i++) {
 145                H.total += freq[tree[i].symb] * tree[i].h.depth;
 146                //fprintf(stderr,"\n         ****tota[%d] = %d x %d =%d",i,freq[tree[i].symb],tree[i].h.depth,H.total);
 147             }
 148         }
 149      free (tree);
 150
 151      //fprintf(stderr,"\n **** CALL ENDS CREATE_HUFF WITH  lim = %ld, freq[0]=%ld, Huffsize=%ld",lim,freq[0],H.total);
 152
 153      return H;
 154    }
 155
 156 int encodeHuff (THuff H, uint symb, uint *stream, uint ptr)
 157
 158    { uint pos;
 159      uint code;
 160      int d;
 161      pos = H.s.spos[symb];
 162      code = 0;
 163      d = H.depth;
 164      while (pos >= H.num[d])
 165        { code = (code + H.num[d]) >> 1;
 166          pos -= H.num[d--];
 167        }
 168      code += pos;
 169      if (d > W) { bitzero2(stream,ptr,d-W); ptr += d-W; d = W; }
 170      while (d--)
 171         { if ((code >> d) & 1) bitset(stream,ptr);
 172           else bitclean(stream,ptr);
 173           ptr++;
 174         }
 175      return ptr;
 176    }
 177
 178 void printCodeHuff (THuff H, uint symb)
 179
 180    { uint pos;
 181      uint code;
 182      int d;
 183      pos = H.s.spos[symb];
 184      code = 0;
 185      d = H.depth;
 186
 187     // fprintf(stderr,"\n H.depth= %ld and pos is %ld\n",H.depth,pos);
 188      while (pos >= H.num[d])
 189        { code = (code + H.num[d]) >> 1;
 190          pos -= H.num[d--];
 191        }
 192      code += pos;
 193      if (d > W) {fprintf(stderr,"code larger than W"); d=W;}
 194
 195          //show the code.
 196      while (d--)
 197         { if ((code >> d) & 1)
 198                 fprintf(stderr,"1");
 199               else fprintf(stderr,"0");
 200                 }
 201    }
 202
 203
 204
 205 int decodeHuff (THuff *H, uint *symb, uint *stream, uint ptr)
 206
 207    { uint pos;
 208      int d;
 209      pos = 0;
 210      d = 0;
 211      while (pos < H->fst[d])
 212         { pos = (pos << 1) | bitget(stream,ptr);
 213           ptr++; d++;
 214         }
 215      *symb = H->s.symb[H->num[d]+pos-H->fst[d]];
 216      return ptr;
 217    }
 218
 219
 220
 221
 222 /*   { uint pos;  // This "improved" code is actually slower!
 223      int d;
 224      uint wrd,off;
 225      stream += ptr/W;
 226      off = ptr & (W-1);
 227      wrd = *stream >> off;
 228      pos = 0;
 229      d = 0;
 230      while (pos < H.fst[d])
 231        { pos = (pos << 1) | (wrd & 1);
 232          d++; wrd >>= 1; off++;
 233          if (off == W) { wrd = *++stream; off = 0; }
 234        }
 235      *symb = H.s.symb[H.num[d]+pos-H.fst[d]];
 236      return ptr+d;
 237    }
 238 */
 239 void saveHuff2 (THuff H, FILE *f)
 240
 241    { uint *symb = (uint *)malloc((H.lim+1)*sizeof(uint));
 242      int i;
 243      for (i=0;i<=H.max;i++)
 244                 if (H.s.spos[i] != ~0) symb[H.s.spos[i]] = i;
 245      fwrite (&H.max,sizeof(uint),1,f);
 246      fwrite (&H.lim,sizeof(uint),1,f);
 247      fwrite (&H.depth,sizeof(uint),1,f);
 248      fwrite (symb,sizeof(uint),H.lim+1,f);
 249      fwrite (H.num,sizeof(uint),H.depth+1,f);
 250      free (symb);
 251    }
 252
 253 uint sizeHuff2 (THuff H)
 254
 255    { return (4 +(H.lim+1)+2*(H.depth+1))*sizeof(uint);
 256    }
 257
 258 uint sizeHuffDisk (THuff H)
 259
 260    { return ( sizeof(THuff) + ((H.lim+1)+(H.depth+1))*sizeof(uint) );
 261    }
 262
 263 void freeHuff2 (THuff H)
 264
 265   { free (H.s.spos);  free (H.num); free (H.fst);
 266   }
 267
 268
 269 THuff loadHuff2 (FILE *f, int enc)   //enc (0/1)-> do you only  want to perform encoding ??
 270
 271    { THuff H;
 272      uint *symb;
 273      uint *num;
 274      int i,d,dold,dact;
 275      fread (&H.max,sizeof(uint),1,f);
 276      fread (&H.lim,sizeof(uint),1,f);
 277      fread (&H.depth,sizeof(uint),1,f);
 278      symb = (uint *) malloc ((H.lim+1)*sizeof(uint));
 279      fread (symb,sizeof(uint),H.lim+1,f);
 280      if (enc)
 281           { H.s.spos = (uint *) malloc ((H.max+1)*sizeof(uint));
 282             for (i=0;i<=H.max;i++) H.s.spos[i] = ~0;
 283             for (i=0;i<=H.lim;i++) H.s.spos[symb[i]] = i;
 284             free (symb);
 285           }
 286      else H.s.symb = symb;
 287
 288      H.num = (uint *) malloc ((H.depth+1)*sizeof(uint));
 289      fread (H.num,sizeof(uint),H.depth+1,f);
 290      if (!enc)
 291           { H.fst = (uint *) malloc ((H.depth+1)*sizeof(uint));
 292             H.fst[H.depth] = 0; dold = 0;
 293             for (d=H.depth-1;d>=0;d--)
 294                 { dact = H.num[d+1];
 295                   H.fst[d] = (H.fst[d+1]+dact) >> 1;
 296                   H.num[d+1] = dold;
 297                   dold += dact;
 298                 }
 299             H.num[0] = dold;
 300           }
 301      return H;
 302    }
 303
 304
 305
 306
 307
 308 /***************************************************************/
 309 void prepareToDecode(THuff *H)
 310 //***///**//  //by fari !!
 311
 312    { uint *symb = (uint *) malloc((H->lim+1)*sizeof(uint));
 313      uint *num;
 314      int i,d,dold,dact;
 315
 316      for (i=0;i<=H->max;i++)
 317                 if (H->s.spos[i] != ~0)
 318                         symb[H->s.spos[i]] = i;
 319
 320          for (i=0;i<=H->lim;i++)
 321                 H->s.symb[i] = symb[i];
 322
 323      //H.num = malloc ((H.depth+1)*sizeof(uint));
 324      {
 325                 H->fst = (uint *)malloc ((H->depth+1)*sizeof(uint));
 326                 H->fst[H->depth] = 0; dold = 0;
 327                 for (d=H->depth-1;d>=0;d--)
 328                 {       dact = H->num[d+1];
 329                         H->fst[d] = (H->fst[d+1]+dact) >> 1;
 330                         H->num[d+1] = dold;
 331                         dold += dact;
 332                 }
 333             H->num[0] = dold;
 334          }
 335      free (symb);
 336 }
 337
 338
 339 ////////////
 340 void saveHuffAfterDecode (THuff H, FILE *f)
 341    {
 342      fwrite (&H.max,sizeof(uint),1,f);
 343      fwrite (&H.lim,sizeof(uint),1,f);
 344      fwrite (&H.depth,sizeof(uint),1,f);
 345      fwrite (H.s.symb,sizeof(uint),H.lim+1,f);
 346
 347      fwrite (H.fst,sizeof(uint),H.depth+1,f);
 348      fwrite (H.num,sizeof(uint),H.depth+1,f);
 349    }
 350
 351
 352 THuff loadHuffAfterDecode (FILE *f, int enc)   //enc (0/1)-> do you only  want to perform encoding ??
 353
 354    { THuff H;
 355 //     int i,d,dold,dact;
 356 //
 357 //     fread (&H.max,sizeof(uint),1,f);
 358 //     fread (&H.lim,sizeof(uint),1,f);
 359 //     fread (&H.depth,sizeof(uint),1,f);
 360 //
 361 //     H.s.symb = malloc ((H.lim+1)*sizeof(uint));
 362 //     fread (H.s.symb,sizeof(uint),H.lim+1,f);
 363 //
 364 //     H.fst = malloc ((H.depth+1)*sizeof(uint));
 365 //     fread (H.fst,sizeof(uint),H.depth+1,f);
 366 //
 367 //     H.num = malloc ((H.depth+1)*sizeof(uint));
 368 //     fread (H.num,sizeof(uint),H.depth+1,f);
 369 //
 370      return H;
 371    }
 372
 373
 374
 375 void loadHuffAfterDecode2 (THuff *H, FILE *f, int enc)   //enc (0/1)-> do you only  want to perform encoding ??
 376
 377    {
 378      int i,d,dold,dact;
 379
 380      fread (&H->max,sizeof(uint),1,f);
 381      fread (&H->lim,sizeof(uint),1,f);
 382      fread (&H->depth,sizeof(uint),1,f);
 383
 384      H->s.symb = (uint *) malloc ((H->lim+1)*sizeof(uint));
 385      fread (H->s.symb,sizeof(uint),H->lim+1,f);
 386
 387      H->fst = (uint *) malloc ((H->depth+1)*sizeof(uint));
 388      fread (H->fst,sizeof(uint),H->depth+1,f);
 389
 390      H->num = (uint *) malloc ((H->depth+1)*sizeof(uint));
 391      fread (H->num,sizeof(uint),H->depth+1,f);
 392    }
 393
 394
 395
 396