Newer
Older
#pragma once
#include "../custom_types.h"
#include "../utilities/vector_utilities.h"
#include "../image/z_order.h"
constexpr size_t MAX_LITERAL_COUNT = 255;
constexpr size_t MAX_RUN_COUNT = 255;
inline float compression_ratio(float uncompressedSize, float compressedSize)
{
return (uncompressedSize / compressedSize);
}
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
// Run-Length encode bytes and return compressed bytes.
std::vector<byte> rle_encode(const std::vector<byte> &bytes)
{
std::vector<byte> compressed;
byte literalBuffer[MAX_LITERAL_COUNT];
size_t literalCount = 0;
size_t runCount = 0;
size_t uncompresseddBufferSize = bytes.size();
for (size_t bufferIndex = 0; bufferIndex < uncompresseddBufferSize;)
{
byte symbol = bytes[bufferIndex];
runCount = 1;
// Encode run.
while ((runCount < MAX_RUN_COUNT) &&
(bytes[bufferIndex + runCount] == symbol) &&
(runCount < (uncompresseddBufferSize - bufferIndex)))
{
++runCount;
}
if ((runCount > 1) ||
(literalCount == MAX_LITERAL_COUNT) ||
((bufferIndex == (uncompresseddBufferSize - 1)) && literalCount > 0))
{
// Write literal buffer.
byte literalCountBYTE = (byte)literalCount;
always_assert(literalCountBYTE == literalCount);
compressed.push_back(literalCountBYTE);
for (size_t literalBufferIndex = 0; literalBufferIndex < literalCount; literalBufferIndex++)
{
compressed.push_back(literalBuffer[literalBufferIndex]);
}
literalCount = 0;
// Write run sequence.
byte runCountBYTE = (byte)runCount;
always_assert(runCountBYTE == runCount);
compressed.push_back(runCountBYTE);
compressed.push_back(symbol);
bufferIndex += runCount;
}
else
{
// Encode literal symbol.
literalBuffer[literalCount++] = symbol;
++bufferIndex;
}
}
return compressed;
}
// Decode Run-Length encoded bytes.
std::vector<byte> rle_decode(const std::vector<byte> &compressed)
{
std::vector<byte> uncompressed;
uncompressed.reserve(compressed.size());
size_t compressedBufferSize = compressed.size();
size_t bufferIndex = 0;
byte literalCount, runCount, runSymbol;
while (bufferIndex < compressedBufferSize)
{
literalCount = compressed[bufferIndex++];
while (literalCount--)
{
uncompressed.push_back(compressed[bufferIndex++]);
}
runCount = compressed[bufferIndex++];
runSymbol = compressed[bufferIndex++];
while (runCount--)
{
uncompressed.push_back(runSymbol);
}
}
return uncompressed;
}
void rle_test()
{
std::vector<byte> data = {10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
20, 30, 40, 45, 48, 46, 50, 50, 50, 50, 50, 50, 50, 50, 50,
50, 0, 0, 1, 2, 3, 8, 8, 8, 8, 9, 6, 5, 4};
// 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 20, 30, 40, 45, 48, 46, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 0, 0, 1, 2, 3, 8, 8, 8, 8, 9, 6, 5, 4
// 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 20, 30, 40, 45, 48, 46, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 0, 0, 1, 2, 3, 8, 8, 8, 8, 9, 6, 5, 4
auto compressed = rle_encode(data);
auto uncompressed = rle_decode(compressed);
bool same = vecUtil::vector_eq(data, uncompressed);