Added simple WCSA

[SXSI/TextCollection.git] / swcsa / utils / huff.h

diff --git a/swcsa/utils/huff.h b/swcsa/utils/huff.h
new file mode 100755 (executable)
index 0000000..060570c
--- /dev/null
+++ b/swcsa/utils/huff.h
@@ -0,0 +1,80 @@
+
+// implements canonical Huffman 
+
+#ifndef HUFFINCLUDED
+#define HUFFINCLUDED
+
+#include "basics.h"
+#define SORTED 1
+#define UNSORTED 0
+
+typedef struct
+   { uint max,lim;   // maximum symbol (0..max), same excluding zero freqs
+     uint depth; // max symbol length
+     union
+       { uint *spos; // symbol positions after sorting by decr freq (enc)
+        uint *symb; // symbols sorted by freq (dec)
+       } s;
+     uint *num;  // first pos of each length (dec), number of each length (enc)
+     uint *fst;  // first code (numeric) of each length (dec)
+     uint total; // total length to achieve, in bits
+   } THuff;
+
+       // Creates Huffman encoder given symbols 0..lim with frequencies 
+       // freq[i], ready for compression
+       // sorted --> are the symbols already sorted ?
+
+THuff createHuff (uint *freq, uint lim, uint sorted);
+
+       // Encodes symb using H, over stream[ptr...lim] (ptr and lim are
+       // bit positions of stream). Returns the new ptr.
+       
+int encodeHuff (THuff H, uint symb, uint *stream, uint ptr);
+
+       // Decodes *symb using H, over stream[ptr...lim] (ptr and lim are
+       // bit positions of stream). Returns the new ptr.
+       
+int decodeHuff (THuff *H, uint *symb, uint *stream, uint ptr);
+
+       //Prepares a Huffman tree for decoding (changes in spos & symb)
+       
+void prepareToDecode(THuff *H);
+
+       // Writes H in file f
+       
+void saveHuff (THuff H, FILE *f);
+
+       // Size of H written on file
+       
+uint sizeHuffDisk (THuff H);
+
+       //Size of H in memory
+uint sizeHuff (THuff H);
+       
+       // Frees H
+       
+void freeHuff (THuff H);
+
+       // Loads H from file f, prepared for encoding or decoding depending
+       // on enc
+       
+THuff loadHuff (FILE *f, int enc);
+
+//Decodes a code starting in position ptr from stream. Returns the ranking in the
+//vector of symbols.
+
+#define decodeNormalHuffMacro(H, symbol, stream, ptr) \
+   { uint pos; \
+     int d; \
+     pos = 0; \
+     d = 0; \
+     while (pos < H->fst[d]) \
+        { pos = (pos << 1) | bitget(stream,ptr); \
+          ptr++; d++; \
+        } \
+    symbol = (H->s.symb[ H->num[d] + pos - H->fst[d] ]); \
+   }
+
+
+#endif
+