libcds/src/coders/huff.h

   1
   2 // implements canonical Huffman
   3
   4 #ifndef HUFFINCLUDED
   5 #define HUFFINCLUDED
   6
   7 #include <basics.h>
   8
   9 typedef struct
  10    { uint max,lim;   // maximum symbol (0..max), same excluding zero freqs
  11      uint depth; // max symbol length
  12      union
  13        { uint *spos; // symbol positions after sorting by decr freq (enc)
  14          uint *symb; // symbols sorted by freq (dec)
  15        } s;
  16      uint *num;  // first pos of each length (dec), number of each length (enc)
  17      uint *fst;  // first code (numeric) of each length (dec)
  18      ulong total; // total length to achieve, in bits
  19    } THuff;
  20
  21         // Creates Huffman encoder given symbols 0..lim with frequencies
  22         // freq[i], ready for compression
  23
  24 THuff createHuff (uint *freq, uint lim);
  25
  26         // Encodes symb using H, over stream[ptr...lim] (ptr and lim are
  27         // bit positions of stream). Returns the new ptr.
  28
  29 ulong encodeHuff (THuff H, uint symb, uint *stream, ulong ptr);
  30
  31         // Decodes *symb using H, over stream[ptr...lim] (ptr and lim are
  32         // bit positions of stream). Returns the new ptr.
  33
  34 ulong decodeHuff (THuff H, uint *symb, uint *stream, ulong ptr);
  35
  36         // Writes H in file f
  37
  38 void saveHuff (THuff H, FILE *f);
  39
  40         // Size of H written on file
  41
  42 uint sizeHuff (THuff H);
  43
  44         // Frees H
  45
  46 void freeHuff (THuff H);
  47
  48         // Loads H from file f, prepared for encoding or decoding depending
  49         // on enc
  50
  51 THuff loadHuff (FILE *f, int enc);
  52
  53 #endif