swcsa/utils/huff.h

   1
   2 // implements canonical Huffman
   3
   4 #ifndef HUFFINCLUDED
   5 #define HUFFINCLUDED
   6
   7 #include "basics.h"
   8 #define SORTED 1
   9 #define UNSORTED 0
  10
  11 typedef struct
  12    { uint max,lim;   // maximum symbol (0..max), same excluding zero freqs
  13      uint depth; // max symbol length
  14      union
  15        { uint *spos; // symbol positions after sorting by decr freq (enc)
  16          uint *symb; // symbols sorted by freq (dec)
  17        } s;
  18      uint *num;  // first pos of each length (dec), number of each length (enc)
  19      uint *fst;  // first code (numeric) of each length (dec)
  20      uint total; // total length to achieve, in bits
  21    } THuff;
  22
  23         // Creates Huffman encoder given symbols 0..lim with frequencies
  24         // freq[i], ready for compression
  25         // sorted --> are the symbols already sorted ?
  26
  27 THuff createHuff (uint *freq, uint lim, uint sorted);
  28
  29         // Encodes symb using H, over stream[ptr...lim] (ptr and lim are
  30         // bit positions of stream). Returns the new ptr.
  31
  32 int encodeHuff (THuff H, uint symb, uint *stream, uint ptr);
  33
  34         // Decodes *symb using H, over stream[ptr...lim] (ptr and lim are
  35         // bit positions of stream). Returns the new ptr.
  36
  37 int decodeHuff (THuff *H, uint *symb, uint *stream, uint ptr);
  38
  39         //Prepares a Huffman tree for decoding (changes in spos & symb)
  40
  41 void prepareToDecode(THuff *H);
  42
  43         // Writes H in file f
  44
  45 void saveHuff2 (THuff H, FILE *f);
  46
  47         // Size of H written on file
  48
  49 uint sizeHuffDisk (THuff H);
  50
  51         //Size of H in memory
  52 uint sizeHuff2 (THuff H);
  53
  54         // Frees H
  55
  56 void freeHuff2 (THuff H);
  57
  58         // Loads H from file f, prepared for encoding or decoding depending
  59         // on enc
  60
  61 THuff loadHuff2 (FILE *f, int enc);
  62
  63 //Decodes a code starting in position ptr from stream. Returns the ranking in the
  64 //vector of symbols.
  65
  66 #define decodeNormalHuffMacro(H, symbol, stream, ptr) \
  67    { uint pos; \
  68      int d; \
  69      pos = 0; \
  70      d = 0; \
  71      while (pos < H->fst[d]) \
  72         { pos = (pos << 1) | bitget(stream,ptr); \
  73           ptr++; d++; \
  74         } \
  75     symbol = (H->s.symb[ H->num[d] + pos - H->fst[d] ]); \
  76    }
  77
  78
  79 #endif
  80