X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=swcsa%2Futils%2Fhuff.h;fp=swcsa%2Futils%2Fhuff.h;h=060570c959be90d71cdd8e52fba448bdaf445599;hb=102e33b134075765e6d4e0c38bc1307568ce5602;hp=0000000000000000000000000000000000000000;hpb=ed61d2042a7ad7dd83bae32d7c31e69504dafa80;p=SXSI%2FTextCollection.git

diff --git a/swcsa/utils/huff.h b/swcsa/utils/huff.h
new file mode 100755
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
+