// Run length encoding
//
// Simplified code as example for the run length encoding.
//
// by feyd//godX.de
#include <cstdint>
#include <vector>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
class CRLE
{
public:
CRLE() {}
virtual ~CRLE() {}
std::vector<uint8_t> Compress(const std::vector<uint8_t>& data)
{
std::vector<uint8_t> compressed;
compressed.reserve(data.size()*2);
size_t nLastPos = 0;
for(size_t nPos=0; nPos<=data.size();)
{
// find same symbols from current position
size_t nRepeat = 0;
if(nPos>0)
for(nRepeat=0; nRepeat<127 && nPos+nRepeat<data.size(); nRepeat++)
if(data[nPos-1]!=data[nPos+nRepeat])
break;
// output uncompressed symbols (if repetition is found or uncompressed length exceeded limit)
// with lengthfield (highest bit not set)
if(nRepeat>3 || (nPos-nLastPos)>126 || nPos==data.size())
{
if(nPos!=nLastPos)
compressed.push_back((uint8_t)(nPos-nLastPos));
while(nLastPos<nPos)
compressed.push_back(data[nLastPos++]);
}
// output number of compressed symbols (highest bit set)
if(nRepeat>3)
{
compressed.push_back((uint8_t)nRepeat+0x80);
nLastPos = nPos = nPos+nRepeat;
} else {
nPos++;
}
}
return compressed;
}
std::vector<uint8_t> Decompress(const std::vector<uint8_t>& data)
{
std::vector<uint8_t> uncompressed;
uncompressed.reserve(data.size()*4);
for(size_t nPos=0; nPos<data.size();)
{
// read length field
uint8_t nMetadata = data[nPos++];
if(nMetadata<0x80)
{
// read/write uncompressed block
for(uint8_t nCopy=0; nCopy<nMetadata && nPos<data.size(); nCopy++)
uncompressed.push_back(data[nPos++]);
} else {
// write repetition
if(uncompressed.size()>0)
for(uint8_t nLength=0; nLength<nMetadata-0x80; nLength++)
uncompressed.push_back(uncompressed[uncompressed.size()-1]);
}
}
return uncompressed;
}
};
void OutputVector(const std::vector<uint8_t>& data)
{
printf(" (%d)", (int)data.size());
for(size_t n=0; n<data.size(); n++)
printf(" %02x", (int)data[n]);
printf("\r\n");
}
// Application entry point (from libc)
int main(int argc, const char* argv[])
{
printf("Run length encoding test...\r\n\r\n");
if(argc<2)
{
printf("Not enough parameters.\r\n");
return -1;
}
std::vector<uint8_t> data;
for(int n=1; n<argc; n++)
for(size_t m=0; m<strlen(argv[n]); m++)
data.push_back((uint8_t)argv[n][m]);
CRLE rle;
printf(" Orginal:\r\n");
OutputVector(data);
std::vector<uint8_t> compressed = rle.Compress(data);
printf(" Compressed:\r\n");
OutputVector(compressed);
std::vector<uint8_t> uncompressed = rle.Decompress(compressed);
printf(" Uncompressed:\r\n");
OutputVector(uncompressed);
return 0;
}
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