SHARE
TWEET

Untitled

a guest Nov 14th, 2019 95 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "Huffman.h"
  2. #include <queue>
  3. #include <unordered_map>
  4. #include <stack>
  5. #include <bitset>
  6.  
  7. struct Node
  8. {
  9.     Node(byte value, long long freq) : value(value), freq(freq), left(nullptr), right(nullptr) {}
  10.     byte value;
  11.     long long freq;
  12.     Node *left;
  13.     Node *right;
  14. };
  15.  
  16. class NodePtrComparator
  17. {
  18. public:
  19.     bool operator()(Node *l, Node *r)
  20.     {
  21.         return l->freq > r->freq;
  22.     }
  23. };
  24.  
  25. void buildCodeTable(Node *root, std::unordered_map<byte, std::vector<unsigned char>> &table, std::vector<unsigned char> path)
  26. {
  27.     if (!root->left && !root->right)
  28.     {
  29.         table[root->value] = path;
  30.     }
  31.     else
  32.     {
  33.         if (root->left)
  34.         {
  35.             std::vector<unsigned char> left(path);
  36.             left.push_back(0);
  37.             buildCodeTable(root->left, table, left);
  38.         }
  39.         if (root->right)
  40.         {
  41.             std::vector<unsigned char> right(path);
  42.             right.push_back(1);
  43.             buildCodeTable(root->right, table, right);
  44.         }
  45.     }
  46. }
  47.  
  48. std::unordered_map<byte, std::vector<unsigned char>> buildCodeTable(Node *root)
  49. {
  50.     std::unordered_map<byte, std::vector<unsigned char>> table;
  51.     buildCodeTable(root, table, {});
  52.     return table;
  53. }
  54.  
  55. class BitWriter
  56. {
  57. public:
  58.     BitWriter() : bitCount(0) {}
  59.  
  60.     void WriteBit(unsigned char bit)
  61.     {
  62.         if (bitCount == buffer.size() * 8)
  63.             buffer.push_back(0);
  64.         if (bit)
  65.             buffer[bitCount/8] |= 1 << (7 - bitCount % 8);
  66.         bitCount++;
  67.     }
  68.  
  69.     void WriteByte(unsigned char byte)
  70.     {
  71.         if (bitCount % 8 == 0)
  72.             buffer.push_back(byte);
  73.         else
  74.         {
  75.             int offset = bitCount % 8;
  76.             buffer[bitCount/8] |= byte >> offset;
  77.             buffer.push_back(byte << (8 - offset));
  78.         }
  79.         bitCount += 8;
  80.     }
  81.  
  82.     const std::vector<unsigned char> &getBuffer() const
  83.     {
  84.         return buffer;
  85.     }
  86.  
  87.     size_t getBitCount() const
  88.     {
  89.         return bitCount;
  90.     }
  91.  
  92.     void visualize() const
  93.     {
  94.         for (auto &b: buffer)
  95.         {
  96.             std::cout << std::bitset<8>(b) << "|";
  97.         }
  98.         std::cout << std::endl;
  99.     }
  100.  
  101. private:
  102.     std::vector<unsigned char> buffer;
  103.     size_t bitCount;
  104. };
  105.  
  106. class BitReader
  107. {
  108. public:
  109.     BitReader(std::vector<unsigned char> &data, size_t bitCount) : bitPos(0), bitCount(bitCount), data(data) {}
  110.     unsigned char readBit()
  111.     {
  112.         auto val = (data[bitPos/8] >> (7 - bitPos % 8)) & 1;
  113.         bitPos++;
  114.         return val;
  115.     }
  116.     unsigned char readByte()
  117.     {
  118.         unsigned char result = 0;
  119.         if (bitPos % 8 == 0)
  120.         {
  121.             result = data[bitPos/8];
  122.         }
  123.         else
  124.         {
  125.             result = data[bitPos/8] << (bitPos % 8);
  126.             result |= data[bitPos/8 + 1] >> (8 - bitPos % 8);
  127.         }
  128.  
  129.         bitPos += 8;
  130.         return result;        
  131.     }
  132.  
  133.     bool hasData() const
  134.     {
  135.         return bitPos < bitCount;
  136.     }
  137. private:
  138.     size_t bitPos;
  139.     size_t bitCount;
  140.     std::vector<unsigned char> &data;
  141. };
  142.  
  143. void serializeTree(Node *root, BitWriter &bw)
  144. {
  145.     if (!root->left && !root->right)
  146.     {
  147.         bw.WriteBit(1);
  148.         bw.WriteByte(root->value);
  149.     }
  150.     else
  151.     {
  152.         if (root->left)
  153.             serializeTree(root->left, bw);
  154.         if (root->right)
  155.             serializeTree(root->right, bw);
  156.         bw.WriteBit(0);
  157.     }
  158. }
  159.  
  160. void printCodeTable(std::unordered_map<byte, std::vector<unsigned char>> &t)
  161. {
  162.     for (auto &pair: t)
  163.     {
  164.         std::cout << pair.first << " = ";
  165.         for (auto &c: pair.second)
  166.             std::cout << (int)c;
  167.         std::cout << std::endl;
  168.     }
  169. }
  170.  
  171.  
  172. void Encode(IInputStream& original, IOutputStream& compressed)
  173. {
  174.     // byte frequencies
  175.     std::vector<unsigned long long> byteValueCounter(256, 0);
  176.     // copy of input data
  177.     std::vector<byte> data;
  178.  
  179.     // copy input and count byte frequencies
  180.     byte value;
  181.     while (original.Read(value))
  182.     {
  183.         byteValueCounter[value]++;
  184.         data.push_back(value);
  185.     }
  186.  
  187.     // initialize the priority queue of Huffman tree nodes
  188.     size_t alphabetSize = 0;
  189.     std::priority_queue<Node*, std::vector<Node*>, NodePtrComparator> nodePriorityQueue;
  190.     for (int i = 0; i < 256; i++)
  191.     {
  192.         // byte value seen at least once
  193.         if (byteValueCounter[i])
  194.         {
  195.             alphabetSize++;
  196.             nodePriorityQueue.push(new Node(i, byteValueCounter[i]));
  197.         }
  198.     }
  199.  
  200.     // Huffman tree construction
  201.     while (nodePriorityQueue.size() > 1)
  202.     {
  203.         Node *r = nodePriorityQueue.top();
  204.         nodePriorityQueue.pop();
  205.  
  206.         Node *l = nodePriorityQueue.top();
  207.         nodePriorityQueue.pop();
  208.  
  209.         Node *root = new Node(0, l->freq + r->freq);
  210.         root->left = l;
  211.         root->right = r;
  212.         nodePriorityQueue.push(root);
  213.     }
  214.  
  215.     // Huffman tree root
  216.     Node *root = nodePriorityQueue.top();
  217.  
  218.     // Hashtable <byte value> --> <Huffman code>
  219.     std::unordered_map<byte, std::vector<unsigned char>> codeTable = buildCodeTable(root);
  220.  
  221.     BitWriter bw;
  222.     bw.WriteByte(alphabetSize);
  223.     serializeTree(root, bw);
  224.     // encoding the input stream copy
  225.     for (auto &byteValue: data)
  226.     {
  227.         for (auto &bit: codeTable[byteValue])
  228.             bw.WriteBit(bit);
  229.     }
  230.  
  231.     // output the encoded data
  232.     for (auto &byteValue: bw.getBuffer())
  233.     {
  234.         compressed.Write(byteValue);
  235.     }
  236.  
  237.     // how many significant bits there are in the last byte of the encoded sequence
  238.     unsigned char significantBitsInLastByte = bw.getBitCount() % 8;
  239.     if (!significantBitsInLastByte)
  240.         significantBitsInLastByte = 8;
  241.     compressed.Write(significantBitsInLastByte);
  242. }
  243.  
  244. byte decodeByte(Node *root, BitReader &bitReader)
  245. {
  246.     while (root->left || root->right)
  247.     {
  248.         switch (bitReader.readBit())
  249.         {
  250.             case 0:
  251.                 root = root->left;
  252.                 break;
  253.             case 1:
  254.                 root = root->right;
  255.                 break;
  256.         }
  257.     }
  258.  
  259.     return root->value;
  260. }
  261.  
  262. void Decode(IInputStream& compressed, IOutputStream& original)
  263. {
  264.     std::vector<byte> data;
  265.  
  266.     byte value;
  267.     while (compressed.Read(value))
  268.     {
  269.         data.push_back(value);
  270.     }
  271.  
  272.     unsigned char significantBitsInLastByte = data[data.size() - 1];
  273.     data.pop_back();
  274.  
  275.     size_t bitCount = (data.size() - 1) * 8 + significantBitsInLastByte;
  276.     BitReader bitReader(data, bitCount);
  277.  
  278.     auto alphabetSize = bitReader.readByte();
  279.     std::stack<Node*> stack;
  280.     size_t lettersRead = 0;
  281.     while (1)
  282.     {
  283.         auto bit = bitReader.readBit();
  284.         if (bit)
  285.         {
  286.             auto letter = bitReader.readByte();
  287.             Node *node = new Node(letter, 0);
  288.             stack.push(node);
  289.             lettersRead++;
  290.         }
  291.         else
  292.         {
  293.             Node *right = stack.top();
  294.             stack.pop();
  295.             Node *left = stack.top();
  296.             stack.pop();
  297.  
  298.             Node *node = new Node(0, 0);
  299.             node->left = left;
  300.             node->right = right;
  301.             stack.push(node);
  302.         }
  303.  
  304.         if (lettersRead == alphabetSize && stack.size() == 1)
  305.             break;
  306.     }
  307.  
  308.     Node *root = stack.top();
  309.     stack.pop();
  310.     std::unordered_map<byte, std::vector<unsigned char>> codeTable = buildCodeTable(root);
  311.  
  312.     while (bitReader.hasData())
  313.     {
  314.         byte decodedByte = decodeByte(root, bitReader);
  315.         original.Write(decodedByte);
  316.     }
  317. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top