File-Compression/decoder.cpp at master · hooman96/File-Compression · 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
113
114
115
116
117
118
119
//  Author: Matthew Kotila & Hooman Mohammadi

#include "decoder.h"
#include <iostream>
#include "BinaryHeap.h"
// constant
#define EMPTY -1
using namespace std;


Decoder::Decoder()
{
} // Decoder()


Decoder::~Decoder()
{
} // ~Decoder()


class node {
public:
  node(): ascii(EMPTY), freq(0), left(NULL), right(NULL) {}
  short ascii;
  int freq;
  node * left;
  node * right;
};


int outputDecoding(const unsigned char* encodedMessage, unsigned char* decodedMessage, node * root, int bitSize) {
  node * oldRoot = root;
  int dSize = 0;
  for (int i = 0, j = 0, k = 0; k < bitSize; i++)
  {
    for(int l = 128; l > 0 && k++ < bitSize; l >>= 1)
    {
      if(encodedMessage[i] & l)
      {
        root = root->right;
        if (root->ascii != EMPTY)
        {
          decodedMessage[j++] = root->ascii;
          dSize++;
          root = oldRoot;
        }
      }
      else
      {
        root = root->left;
        if (root->ascii != EMPTY)
        {
          decodedMessage[j++] = root->ascii;
          dSize++;
          root = oldRoot;
        }
      }
    }
  }
  return dSize;
}  // outputDecoding()


void Decoder::decode(const unsigned char* encodedMessage, const int encodedSize,
  unsigned char* decodedMessage, int *decodedSize)
{
  // constructs leaves from encodedMessage
  node leaves[256];
  int start = 0;
  int bitSize = 0;
  for (; ; )
  {
    int asciiVal = encodedMessage[start];
    leaves[asciiVal].ascii = asciiVal;
    leaves[asciiVal].freq = encodedMessage[start + 1] - '0';
    int j = start + 2;
    for (; encodedMessage[j] != ',' && encodedMessage[j] != ':'; j++)
    {
      leaves[asciiVal].freq *= 10;
      leaves[asciiVal].freq += (encodedMessage[j] - '0');
    }
    start = j + 1;
    if (encodedMessage[start - 1] == ':')
    {
      bitSize = encodedMessage[start] - '0';
      int k = start + 1;
      for (; encodedMessage[k] != ':'; k++)
      {
        bitSize *= 10;
        bitSize += (encodedMessage[k] - '0');
       }
      start = k + 1;
      break;
    }
  }

  // inserts leaves into heap based on frequency
  BinaryHeap<node*> heap;
  for (int i = 0; i < 256; i++)
    if (leaves[i].ascii != EMPTY)
      heap.insert(&leaves[i]);

  // constructs huffman tree based on frequency
  node * root = NULL;
  while (heap.currentSize > 1)
  {
    node * iNode = new node;
    iNode->left = new node;
    iNode->right = new node;
    *iNode->left = *heap.findMin(); heap.deleteMin();
    *iNode->right = *heap.findMin(); heap.deleteMin();
    iNode->freq = iNode->left->freq + iNode->right->freq;
    heap.insert(iNode);
    root = iNode;
  }

  // traverses tree to fill decodedMessage with original message
  *decodedSize = outputDecoding(encodedMessage + start, decodedMessage, root, bitSize);
} // decode()