Index: trunk/Mars/mcore/huffman.h
===================================================================
--- trunk/Mars/mcore/huffman.h	(revision 14795)
+++ trunk/Mars/mcore/huffman.h	(revision 14795)
@@ -0,0 +1,388 @@
+#ifndef FACT_huffman
+#define FACT_huffman
+
+#include <string.h>
+#include <stdint.h>
+
+#include <set>
+#include <string>
+#include <vector>
+
+#define MAX_SYMBOLS (1<<16)
+
+// ================================================================
+
+namespace Huffman
+{
+    static unsigned long numbytes_from_numbits(unsigned long numbits)
+    {
+        return numbits / 8 + (numbits % 8 ? 1 : 0);
+    }
+
+    struct TreeNode
+    {
+        TreeNode *parent;
+        union
+        {
+            struct
+            {
+                TreeNode *zero, *one;
+            };
+            uint16_t symbol;
+        };
+
+        size_t count;
+        bool isLeaf;
+
+        TreeNode(uint16_t sym, size_t cnt=0) : parent(0), isLeaf(true)
+        {
+            symbol = sym;
+            count  = cnt;
+        }
+
+        TreeNode(TreeNode *n0=0, TreeNode *n1=0) : parent(0), isLeaf(false)
+        {
+            count = n0 && n1 ?  n0->count + n1->count : 0;
+            zero  = n0 && n1 ? (n0->count > n1->count ? n0 : n1) : NULL;
+            one   = n0 && n1 ? (n0->count > n1->count ? n1 : n0) : NULL;
+
+            if (n0)
+                n0->parent = this;
+
+            if (n1)
+                n1->parent = this;
+        }
+
+        ~TreeNode()
+        {
+            if (isLeaf)
+                return;
+
+            if (zero)
+                delete zero;
+            if (one)
+                delete one;
+        }
+
+        bool operator() (const TreeNode *hn1, const TreeNode *hn2) const
+        {
+            return hn1->count < hn2->count;
+        }
+    };
+
+
+    struct Encoder
+    {
+        struct Code
+        {
+            size_t bits;
+            uint8_t numbits;
+
+            Code() : numbits(0) { }
+        };
+
+        size_t count;
+        Code lut[1<<16];
+
+        void CreateEncoder(const TreeNode *n, size_t bits=0, uint8_t nbits=0)
+        {
+            if (n->isLeaf)
+            {
+                if (nbits>sizeof(size_t)*8)
+                    throw std::runtime_error("Too many different symbols - this should not happen!");
+
+                lut[n->symbol].bits    = bits;
+                lut[n->symbol].numbits = nbits==0 ? 1 : nbits;
+                count++;
+                return;
+            }
+
+            CreateEncoder(n->zero, bits,              nbits+1);
+            CreateEncoder(n->one,  bits | (1<<nbits), nbits+1);
+        }
+
+        void WriteCodeTable(std::string &out) const
+        {
+            out.append((char*)&count, sizeof(size_t));
+
+            for (uint32_t i=0; i<MAX_SYMBOLS; i++)
+            {
+                const Code &n = lut[i];
+                if (n.numbits==0)
+                    continue;
+
+                // Write the 2 byte symbol.
+                out.append((char*)&i, sizeof(uint16_t));
+                if (count==1)
+                    return;
+
+                // Write the 1 byte code bit length.
+                out.append((char*)&n.numbits, sizeof(uint8_t));
+
+                // Write the code bytes.
+                uint32_t numbytes = numbytes_from_numbits(n.numbits);
+                out.append((char*)&n.bits, numbytes);
+            }
+        }
+
+        void Encode(std::string &out, const uint16_t *bufin, size_t bufinlen) const
+        {
+            if (count==1)
+                return;
+
+            uint8_t curbyte = 0;
+            uint8_t curbit  = 0;
+
+            for (uint32_t i=0; i<bufinlen; ++i)
+            {
+                const uint16_t &symbol = bufin[i];
+
+                const Code *code = lut+symbol;
+
+                uint8_t nbits = code->numbits;
+                const uint8_t *bits = (uint8_t*)&code->bits;
+
+                while (nbits>0)
+                {
+                    // Number of bits available in the current byte
+                    const uint8_t free_bits = 8 - curbit;
+
+                    // Write bits to current byte
+                    curbyte |= *bits<<curbit;
+
+                    // If the byte has been filled, put it into the output buffer
+                    // If the bits exceed the current byte step to the next byte
+                    // and fill it properly
+                    if (nbits>=free_bits)
+                    {
+                        out += curbyte;
+                        curbyte = *bits>>free_bits;
+
+                        bits++;
+                    }
+
+                    // Adapt the number of available bits, the number of consumed bits
+                    // and the bit-pointer accordingly
+                    const uint8_t consumed = nbits>8 ? 8 : nbits;
+                    nbits  -= consumed;
+                    curbit += consumed;
+                    curbit %= 8;
+                }
+            }
+
+            // If the buffer-byte is half-full, also add it to the output buffer
+            if (curbit>0)
+                out += curbyte;
+        }
+
+        Encoder(const uint16_t *bufin, size_t bufinlen) : count(0)
+        {
+            uint16_t counts[MAX_SYMBOLS];
+            memset(counts, 0, sizeof(uint16_t)*MAX_SYMBOLS);
+
+            // Count occurances
+            for (const uint16_t *p=bufin; p<bufin+bufinlen; p++)
+                counts[*p]++;
+
+            // Copy all occuring symbols into a sorted list
+            std::multiset<TreeNode*, TreeNode> set;
+            for (int i=0; i<MAX_SYMBOLS; i++)
+                if (counts[i])
+                    set.insert(new TreeNode(i, counts[i]));
+
+            // Create the tree bottom-up
+            while (set.size()>1)
+            {
+                auto it = set.begin();
+
+                auto it1 = it++;
+                auto it2 = it;
+
+                TreeNode *nn = new TreeNode(*it1, *it2);
+
+                set.erase(it1, ++it2);
+
+                set.insert(nn);
+            }
+
+            // get the root of the tree
+            const TreeNode *root = *set.begin();
+
+            CreateEncoder(root);
+
+            // This will delete the whole tree
+            delete root;
+        }
+
+    };
+
+
+
+    struct Decoder
+    {
+        uint16_t symbol;
+        uint8_t nbits;
+        bool isLeaf;
+
+        Decoder *lut;
+
+        Decoder() : isLeaf(false), lut(NULL)
+        {
+        }
+
+        ~Decoder()
+        {
+            if (lut)
+                delete [] lut;
+        }
+
+        void Set(uint16_t sym, uint8_t n=0, size_t bits=0)
+        {
+            if (!lut)
+                lut = new Decoder[256];
+
+            if (n>8)
+            {
+                lut[bits&0xff].Set(sym, n-8, bits>>8);
+                return;
+            }
+
+            const int nn = 1<<(8-n);
+
+            for (int i=0; i<nn; i++)
+            {
+                const uint8_t key = bits | (i<<n);
+
+                lut[key].symbol = sym;
+                lut[key].isLeaf = true;
+                lut[key].nbits  = n;
+            }
+        }
+
+        void Build(const TreeNode &p, uint64_t bits=0, uint8_t n=0)
+        {
+            if (p.isLeaf)
+            {
+                Set(p.symbol, n, bits);
+                return;
+            }
+
+            Build(*p.zero, bits,          n+1);
+            Build(*p.one,  bits | (1<<n), n+1);
+        }
+
+        Decoder(const TreeNode &p) : symbol(0), isLeaf(false), lut(NULL)
+        {
+            Build(p);
+        }
+
+        const uint8_t *Decode(const uint8_t *in_ptr, const uint8_t *in_end,
+                              uint16_t *out_ptr, const uint16_t *out_end) const
+        {
+            Decoder const *p = this;
+
+            uint8_t curbit = 0;
+            while (in_ptr<in_end && out_ptr<out_end)
+            {
+                const uint16_t *two = (uint16_t*)in_ptr;
+
+                const uint8_t curbyte = (*two >> curbit);
+
+                if (!p->lut)
+                    throw std::runtime_error("Unknown bitcode in stream!");
+                p = p->lut + curbyte;
+                if (!p->isLeaf)
+                {
+                    in_ptr++;
+                    continue;
+                }
+
+                *out_ptr++ = p->symbol;
+                curbit += p->nbits;
+
+                p = this;
+
+                if (curbit>=8)
+                {
+                    curbit %= 8;
+                    in_ptr++;
+                }
+
+            }
+
+            return curbit ? in_ptr+1 : in_ptr;
+        }
+
+        Decoder(const uint8_t* bufin, unsigned int &pindex) : isLeaf(false), lut(NULL)
+        {
+            // FIXME: Sanity check for size missing....
+
+            // Read the number of entries.
+            size_t count=0;
+            memcpy(&count, bufin + pindex, sizeof(count));
+            pindex += sizeof(count);
+
+            // Read the entries.
+            for (size_t i=0; i<count; i++)
+            {
+                uint16_t sym;
+                memcpy(&sym, bufin + pindex, sizeof(uint16_t));
+                pindex += sizeof(uint16_t);
+
+                if (count==1)
+                {
+                    Set(sym);
+                    break;
+                }
+
+                uint8_t numbits;
+                memcpy(&numbits, bufin + pindex, sizeof(uint8_t));
+                pindex += sizeof(uint8_t);
+
+                const uint8_t numbytes = numbytes_from_numbits(numbits);
+                if (numbytes>sizeof(size_t))
+                    throw std::runtime_error("Number of bytes for a single symbol exceeds maximum.");
+
+                size_t bits=0;
+                memcpy(&bits, bufin+pindex, numbytes);
+                pindex += numbytes;
+
+                Set(sym, numbits, bits);
+            }
+        }
+    };
+
+    void Encode(std::string &bufout, const uint16_t *bufin, size_t bufinlen)
+    {
+        bufout.append((char*)&bufinlen, sizeof(size_t));
+
+        const Encoder encoder(bufin, bufinlen);
+        encoder.WriteCodeTable(bufout);
+        encoder.Encode(bufout, bufin, bufinlen);
+    }
+
+    int Decode(const uint8_t *bufin,
+               size_t         bufinlen,
+               std::vector<uint16_t> &pbufout)
+    {
+        unsigned int i = 0;
+
+        // Read the number of data bytes this encoding represents.
+        size_t data_count = 0;
+        memcpy(&data_count, bufin, sizeof(size_t));
+        i += sizeof(size_t);
+
+
+        pbufout.resize(data_count);
+
+        const Decoder decoder(bufin, i);
+
+        const uint8_t *in_ptr =
+            decoder.Decode(bufin+i, bufin+bufinlen,
+                           pbufout.data(), pbufout.data()+data_count);
+
+        return in_ptr-bufin;
+    }
+};
+
+#endif