file-compressor/Encoder.cpp at main · 637tom/file-compressor · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <set>
#include <utility>
#include <cstdint>
#include "Encoder.h"

void HuffmanEncoder::add(unsigned int freq, uint8_t symbol, Node* left, Node* right) {
    Node* curr = new Node();
    curr->symbol = symbol;
    curr->left = left;
    curr->right = right;
    s.insert({freq, curr});
}

void HuffmanEncoder::remTree(Node* curr) {
    if(curr == nullptr) return;
    remTree(curr->left);
    remTree(curr->right);
    delete curr;
}

HuffmanEncoder::HuffmanEncoder(std::vector<uint8_t> inp) {
    text = inp;
    root = nullptr;
    for(int i = 0; i < 256; i++) {
        freq[i] = 0;
    }
}

HuffmanEncoder::~HuffmanEncoder() {
    remTree(root);
}

void HuffmanEncoder::cntFreq() {
    for(auto ch : text) {
        freq[ch]++;
    }
}

void HuffmanEncoder::buildTree() {
    for(int i = 0; i < 256; i++) {
        if(freq[i] > 0) {
            add(freq[i], i);
        }
    }
    if(s.size() == 0) {
        root = nullptr;
        return;
    }
    if(s.size() == 1) {
        add(0, 0);
    }
    while(s.size() > 1) {
        auto it1 = s.begin();
        auto it2 = std::next(it1);
        add(it1->first + it2->first, 0, it1->second, it2->second);
        s.erase(it1);
        s.erase(it2);
    }
    root = s.begin()->second;
}

void HuffmanEncoder::create_codes(Node* curr, unsigned int len, unsigned int val) {
    if(curr == nullptr) return;
    if(curr->left == nullptr && curr->right == nullptr) {
        codes[curr->symbol].val = val;
        codes[curr->symbol].len = len;
        return;
    }
    create_codes(curr->left, len + 1, (val << 1));
    create_codes(curr->right, len + 1, (val << 1) ^ 1);
}

std::vector<uint8_t> HuffmanEncoder::compress() {
    cntFreq();
    buildTree();
    create_codes(root, 0, 0);

    std::vector<uint8_t> res;
    int tot_len = text.size();
    uint8_t* bytes_tot_len = (uint8_t*)&tot_len;
    for(int i = 0; i < 4; i++) {
        res.push_back(bytes_tot_len[i]);
    }
    for(int i = 0; i < 256; i++) {
        uint8_t* bytes_freq = (uint8_t*)&freq[i];
        for(int j = 0; j < 4; j++) {
            res.push_back(bytes_freq[j]);
        }
    }
    uint8_t buff= 0;
    int bit_cnt = 0;
    for(auto ch : text) {
        for(int i = codes[ch].len - 1; i >= 0; i--) {
            buff <<= 1;
            if((1<<i) & codes[ch].val) {
                buff ^= 1;
            }
            bit_cnt++;
            if(bit_cnt == 8) {
                res.push_back(buff);
                buff = 0;
                bit_cnt = 0;
            }
        }
    }
    if(bit_cnt > 0) {
        buff <<= (8 - bit_cnt);
        res.push_back(buff);
    }
    return res;
}