libcds/src/coders/huff.h

   1 /* huff.h
   2    Copyright (C) 2008, Gonzalo Navarro, all rights reserved.
   3
   4    Canonical Huffman
   5
   6    This library is free software; you can redistribute it and/or
   7    modify it under the terms of the GNU Lesser General Public
   8    License as published by the Free Software Foundation; either
   9    version 2.1 of the License, or (at your option) any later version.
  10
  11    This library is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14    Lesser General Public License for more details.
  15
  16    You should have received a copy of the GNU Lesser General Public
  17    License along with this library; if not, write to the Free Software
  18    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  19
  20 */
  21
  22 #ifndef HUFFINCLUDED
  23 #define HUFFINCLUDED
  24
  25 #include <basics.h>
  26
  27 typedef struct
  28    { uint max,lim;   // maximum symbol (0..max), same excluding zero freqs
  29      uint depth; // max symbol length
  30      union
  31        { uint *spos; // symbol positions after sorting by decr freq (enc)
  32          uint *symb; // symbols sorted by freq (dec)
  33        } s;
  34      uint *num;  // first pos of each length (dec), number of each length (enc)
  35      uint *fst;  // first code (numeric) of each length (dec)
  36      ulong total; // total length to achieve, in bits
  37    } THuff;
  38
  39
  40 /** Creates Huffman encoder given symbols 0..lim with frequencies
  41  *  freq[i], ready for compression
  42  *
  43  *  @author Gonzalo Navarro
  44  */
  45 THuff createHuff (uint *freq, uint lim);
  46
  47 /** Encodes symb using H, over stream[ptr...lim] (ptr and lim are
  48  *  bit positions of stream). Returns the new ptr.
  49  *
  50  *  @author Gonzalo Navarro
  51  */
  52 ulong encodeHuff (THuff H, uint symb, uint *stream, ulong ptr);
  53
  54 /** Decodes *symb using H, over stream[ptr...lim] (ptr and lim are
  55  *  bit positions of stream). Returns the new ptr.
  56  *
  57  *  @author Gonzalo Navarro
  58  */
  59 ulong decodeHuff (THuff H, uint *symb, uint *stream, ulong ptr);
  60
  61 /** Writes H in file f
  62  *
  63  *  @author Gonzalo Navarro
  64  */
  65 void saveHuff (THuff H, FILE *f);
  66
  67 /** Size of H written on file
  68  *
  69  *  @author Gonzalo Navarro
  70  */
  71 uint sizeHuff (THuff H);
  72
  73 /** Frees H
  74  *
  75  *  @author Gonzalo Navarro
  76  */
  77 void freeHuff (THuff H);
  78
  79 /** Loads H from file f, prepared for encoding or decoding depending
  80  *  on enc
  81  *
  82  *  @author Gonzalo Navarro
  83  */
  84 THuff loadHuff (FILE *f, int enc);
  85
  86 #endif