rle.cpp

// 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