Debian Codegraph @

CorsixTH/Src/run_length_encoder.cpp

raw
1 /*
2 Copyright (c) 2010 Peter "Corsix" Cawley
3
4 Permission is hereby granted, free of charge, to any person obtaining a copy of
5 this software and associated documentation files (the "Software"), to deal in
6 the Software without restriction, including without limitation the rights to
7 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
8 of the Software, and to permit persons to whom the Software is furnished to do
9 so, subject to the following conditions:
10
11 The above copyright notice and this permission notice shall be included in all
12 copies or substantial portions of the Software.
13
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
20 SOFTWARE.
21 */
22
23 #include "run_length_encoder.h"
24
25 #include <algorithm>
26 #include <cstdio>
27 #include <new>
28
29 #include "persist_lua.h"
30
31 integer_run_length_encoder::integer_run_length_encoder(size_t iRecordSize)
32 : buffer(iRecordSize * 8 * 4),
33 output(iRecordSize * 8 * 4),
34 record_size(iRecordSize) {}
35
36 void integer_run_length_encoder::write(uint32_t iValue) {
37 buffer[(buffer_offset + buffer_size) % buffer.size()] = iValue;
38 if (++buffer_size == buffer.size()) flush(false);
39 }
40
41 void integer_run_length_encoder::finish() {
42 if (buffer_size != 0) flush(true);
43 }
44
45 void integer_run_length_encoder::flush(bool bAll) {
46 do {
47 if (object_size == 0) {
48 // Decide on the size of the next object
49 // Want the object size which gives most object repeats, then for
50 // two sizes with the same repeat count, the smaller size.
51 size_t iBestRepeats = 0;
52 size_t iBestSize = 0;
53 size_t iBestOffset = 0;
54 for (size_t iNumRecords = 1; iNumRecords <= 8; ++iNumRecords) {
55 for (size_t iOffset = 0; iOffset < iNumRecords; ++iOffset) {
56 size_t iNumRepeats = 0;
57 size_t iObjSize = iNumRecords * record_size;
58 while (iObjSize * (iOffset + iNumRepeats + 1) <= buffer_size &&
59 are_ranges_equal(0, iNumRepeats, iOffset, iObjSize)) {
60 ++iNumRepeats;
61 }
62 if (iNumRepeats > iBestRepeats ||
63 (iNumRepeats == iBestRepeats && iObjSize < iBestSize)) {
64 iBestRepeats = iNumRepeats;
65 iBestSize = iObjSize;
66 iBestOffset = iOffset;
67 }
68 }
69 }
70 if (iBestRepeats == 1) {
71 // No repeats were found, so the best we can do is output
72 // a large non-repeating blob.
73 move_object_to_output(std::min(buffer_size, 8 * record_size), 1);
74 } else {
75 if (iBestOffset != 0)
76 move_object_to_output(iBestOffset * record_size, 1);
77 // Mark the object as the current one, and remove all but the
78 // last instance of it from the buffer. On the next flush, the
79 // new data might continue the same object, hence why the
80 // object isn't output just yet.
81 object_size = iBestSize;
82 object_copies = iBestRepeats - 1;
83 buffer_offset =
84 (buffer_offset + object_size * object_copies) % buffer.size();
85 buffer_size -= object_size * object_copies;
86 }
87 } else {
88 // Try to match more of the current object
89 while (object_size * 2 <= buffer_size &&
90 are_ranges_equal(0, 1, 0, object_size)) {
91 ++object_copies;
92 buffer_offset = (buffer_offset + object_size) % buffer.size();
93 buffer_size -= object_size;
94 }
95 // Write data
96 if (object_size * 2 <= buffer_size || bAll) {
97 move_object_to_output(object_size, object_copies + 1);
98 object_size = 0;
99 object_copies = 0;
100 }
101 }
102 } while (bAll && buffer_size != 0);
103 }
104
105 bool integer_run_length_encoder::are_ranges_equal(size_t iObjIdx1,
106 size_t iObjIdx2,
107 size_t iOffset,
108 size_t iObjSize) const {
109 iObjIdx1 = buffer_offset + iOffset * record_size + iObjIdx1 * iObjSize;
110 iObjIdx2 = buffer_offset + iOffset * record_size + iObjIdx2 * iObjSize;
111 for (size_t i = 0; i < iObjSize; ++i) {
112 if (buffer[(iObjIdx1 + i) % buffer.size()] !=
113 buffer[(iObjIdx2 + i) % buffer.size()]) {
114 return false;
115 }
116 }
117 return true;
118 }
119
120 bool integer_run_length_encoder::move_object_to_output(size_t iObjSize,
121 size_t iObjCount) {
122 // Grow the output array if needed
123 if (output.size() - output_size <= iObjSize) {
124 size_t iNewSize = (output.size() + iObjSize) * 2;
125 output.resize(iNewSize);
126 }
127 size_t iHeader = (iObjSize / record_size - 1) + 8 * (iObjCount - 1);
128 output[output_size++] = static_cast<uint32_t>(iHeader);
129 // Move the object from the buffer to the output
130 for (size_t i = 0; i < iObjSize; ++i) {
131 output[output_size++] = buffer[buffer_offset];
132 buffer_offset = (buffer_offset + 1) % buffer.size();
133 }
134 buffer_size -= iObjSize;
135 return true;
136 }
137
138 const uint32_t* integer_run_length_encoder::get_output(size_t* pCount) const {
139 if (pCount) *pCount = output_size;
140 return output.data();
141 }
142
143 void integer_run_length_encoder::pump_output(
144 lua_persist_writer* pWriter) const {
145 pWriter->write_uint(output_size);
146 for (size_t i = 0; i < output_size; ++i) {
147 pWriter->write_uint(output[i]);
148 }
149 }
150
151 integer_run_length_decoder::integer_run_length_decoder(
152 size_t iRecordSize, lua_persist_reader* pReader)
153 : buffer(9 * iRecordSize), reader(pReader), record_size(iRecordSize) {
154 pReader->read_uint(reads_remaining);
155 }
156
157 uint32_t integer_run_length_decoder::read() {
158 if (object_copies == 0) {
159 uint32_t iHeader = 0;
160 reader->read_uint(iHeader);
161 --reads_remaining;
162 object_size = record_size * (1 + (iHeader & 7));
163 object_copies = (iHeader / 8) + 1;
164 for (size_t i = 0; i < object_size; ++i) {
165 reader->read_uint(buffer[i]);
166 --reads_remaining;
167 }
168 }
169
170 uint32_t iValue = buffer[object_index];
171 if (++object_index == object_size) {
172 object_index = 0;
173 --object_copies;
174 }
175 return iValue;
176 }
177
178 bool integer_run_length_decoder::is_finished() const {
179 return reads_remaining == 0 && object_copies == 0;
180 }