Line data Source code
1 : /*
2 : Copyright 2015 Esri
3 :
4 : Licensed under the Apache License, Version 2.0 (the "License");
5 : you may not use this file except in compliance with the License.
6 : You may obtain a copy of the License at
7 :
8 : http://www.apache.org/licenses/LICENSE-2.0
9 :
10 : Unless required by applicable law or agreed to in writing, software
11 : distributed under the License is distributed on an "AS IS" BASIS,
12 : WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 : See the License for the specific language governing permissions and
14 : limitations under the License.
15 :
16 : A local copy of the license and additional notices are located with the
17 : source distribution at:
18 :
19 : http://github.com/Esri/lerc/
20 :
21 : Contributors: Thomas Maurer
22 : */
23 :
24 : #include "Defines.h"
25 : #include "RLE.h"
26 : #include <cstring>
27 :
28 : USING_NAMESPACE_LERC
29 :
30 : // -------------------------------------------------------------------------- ;
31 :
32 18 : size_t RLE::computeNumBytesRLE(const Byte* arr, size_t numBytes) const
33 : {
34 18 : if (arr == nullptr || numBytes == 0)
35 0 : return 0;
36 :
37 18 : const Byte* ptr = arr;
38 18 : size_t sum = 0;
39 18 : size_t cntOdd = 0;
40 18 : size_t cntEven = 0;
41 18 : size_t cntTotal = 0;
42 18 : bool bOdd = true;
43 :
44 210 : while (cntTotal < numBytes - 1)
45 : {
46 192 : if (*ptr != *(ptr + 1))
47 : {
48 0 : if (bOdd)
49 : {
50 0 : cntOdd++;
51 : }
52 : else // switch to odd mode
53 : {
54 0 : sum += 2 + 1;
55 0 : bOdd = true;
56 0 : cntOdd = 0;
57 0 : cntEven = 0;
58 : }
59 : }
60 : else
61 : {
62 192 : if (!bOdd)
63 : {
64 184 : cntEven++;
65 : }
66 : else
67 : {
68 : // count if we have enough equal bytes so it is worth switching to even
69 8 : bool foundEnough = false;
70 8 : if (cntTotal + m_minNumEven < numBytes)
71 : {
72 8 : int i = 1;
73 40 : while (i < m_minNumEven && ptr[i] == ptr[0]) i++;
74 8 : foundEnough = i < m_minNumEven ? false : true;
75 : }
76 :
77 8 : if (!foundEnough) // stay in odd mode
78 : {
79 0 : cntOdd++;
80 : }
81 : else // switch to even mode
82 : {
83 8 : if (cntOdd > 0)
84 0 : sum += 2 + cntOdd;
85 8 : bOdd = false;
86 8 : cntOdd = 0;
87 8 : cntEven = 0;
88 8 : cntEven++;
89 : }
90 : }
91 : }
92 192 : ptr++;
93 192 : cntTotal++;
94 :
95 192 : if (cntOdd == 32767) // prevent short counters from overflow
96 : {
97 0 : sum += 2 + 32767;
98 0 : cntOdd = 0;
99 : }
100 192 : if (cntEven == 32767)
101 : {
102 0 : sum += 2 + 1;
103 0 : cntEven = 0;
104 : }
105 : }
106 :
107 : // don't forget the last byte
108 18 : if (bOdd)
109 : {
110 10 : cntOdd++;
111 10 : sum += 2 + cntOdd;
112 : }
113 : else
114 : {
115 8 : sum += 2 + 1;
116 : }
117 :
118 18 : return sum + 2; // EOF short
119 : }
120 :
121 : // -------------------------------------------------------------------------- ;
122 :
123 9 : bool RLE::compress(const Byte* arr, size_t numBytes,
124 : Byte** arrRLE, size_t& numBytesRLE, bool verify) const
125 : {
126 9 : if (arr == nullptr || numBytes == 0)
127 0 : return false;
128 :
129 9 : numBytesRLE = computeNumBytesRLE(arr, numBytes);
130 :
131 9 : *arrRLE = new Byte[numBytesRLE];
132 9 : if (!*arrRLE)
133 0 : return false;
134 :
135 9 : const Byte* srcPtr = arr;
136 9 : Byte* cntPtr = *arrRLE;
137 9 : Byte* dstPtr = cntPtr + 2;
138 : //size_t sum = 0;
139 9 : size_t cntOdd = 0;
140 9 : size_t cntEven = 0;
141 9 : size_t cntTotal = 0;
142 9 : bool bOdd = true;
143 :
144 105 : while (cntTotal < numBytes - 1)
145 : {
146 96 : if (*srcPtr != *(srcPtr + 1))
147 : {
148 0 : *dstPtr++ = *srcPtr;
149 0 : if (bOdd)
150 : {
151 0 : cntOdd++;
152 : }
153 : else // switch to odd mode
154 : {
155 0 : cntEven++;
156 0 : writeCount(-(short)cntEven, &cntPtr, &dstPtr); // - sign for even cnts
157 : //sum += 2 + 1;
158 0 : bOdd = true;
159 0 : cntOdd = 0;
160 0 : cntEven = 0;
161 : }
162 : }
163 : else
164 : {
165 96 : if (!bOdd)
166 : {
167 92 : cntEven++;
168 : }
169 : else
170 : {
171 : // count if we have enough equal bytes so it is worth switching to even
172 4 : bool foundEnough = false;
173 4 : if (cntTotal + m_minNumEven < numBytes)
174 : {
175 4 : int i = 1;
176 20 : while (i < m_minNumEven && srcPtr[i] == srcPtr[0]) i++;
177 4 : foundEnough = i < m_minNumEven ? false : true;
178 : }
179 :
180 4 : if (!foundEnough) // stay in odd mode
181 : {
182 0 : *dstPtr++ = *srcPtr;
183 0 : cntOdd++;
184 : }
185 : else // switch to even mode
186 : {
187 4 : if (cntOdd > 0)
188 : {
189 0 : writeCount((short)cntOdd, &cntPtr, &dstPtr); // + sign for odd cnts
190 : //sum += 2 + cntOdd;
191 : }
192 4 : bOdd = false;
193 4 : cntOdd = 0;
194 4 : cntEven = 0;
195 4 : cntEven++;
196 : }
197 : }
198 : }
199 :
200 96 : if (cntOdd == 32767) // prevent short counters from overflow
201 : {
202 0 : writeCount((short)cntOdd, &cntPtr, &dstPtr);
203 : //sum += 2 + 32767;
204 0 : cntOdd = 0;
205 : }
206 96 : if (cntEven == 32767)
207 : {
208 0 : *dstPtr++ = *srcPtr;
209 0 : writeCount(-(short)cntEven, &cntPtr, &dstPtr);
210 : //sum += 2 + 1;
211 0 : cntEven = 0;
212 : }
213 :
214 96 : srcPtr++;
215 96 : cntTotal++;
216 : }
217 :
218 : // don't forget the last byte
219 9 : *dstPtr++ = *srcPtr;
220 9 : if (bOdd)
221 : {
222 5 : cntOdd++;
223 5 : writeCount((short)cntOdd, &cntPtr, &dstPtr);
224 : //sum += 2 + cntOdd;
225 : }
226 : else
227 : {
228 4 : cntEven++;
229 4 : writeCount(-(short)cntEven, &cntPtr, &dstPtr);
230 : //sum += 2 + 1;
231 : }
232 :
233 9 : writeCount(-32768, &cntPtr, &dstPtr); // write end of stream symbol
234 : //sum += 2;
235 :
236 9 : if (verify)
237 : {
238 0 : Byte* arr2 = nullptr;
239 0 : size_t numBytes2 = 0;
240 0 : if (!decompress(*arrRLE, numBytesRLE, &arr2, numBytes2) || numBytes2 != numBytes)
241 : {
242 0 : delete[] arr2;
243 0 : return false;
244 : }
245 0 : int nCheck = memcmp(arr, arr2, numBytes);
246 0 : delete[] arr2;
247 0 : if (nCheck != 0)
248 0 : return false;
249 : }
250 :
251 9 : return true;
252 : }
253 :
254 : // -------------------------------------------------------------------------- ;
255 :
256 0 : bool RLE::decompress(const Byte* arrRLE, size_t nBytesRemainingIn, Byte** arr, size_t& numBytes)
257 : {
258 0 : if (!arrRLE || nBytesRemainingIn < 2)
259 0 : return false;
260 :
261 : // first count the encoded bytes
262 0 : const Byte* srcPtr = arrRLE;
263 0 : size_t nBytesRemaining = nBytesRemainingIn - 2;
264 0 : size_t sum = 0;
265 :
266 0 : short cnt = readCount(&srcPtr);
267 0 : while (cnt != -32768)
268 : {
269 0 : sum += cnt < 0 ? -cnt : cnt;
270 0 : size_t n = cnt > 0 ? cnt : 1;
271 :
272 0 : if (nBytesRemaining < n + 2)
273 0 : return false;
274 :
275 0 : srcPtr += n;
276 0 : cnt = readCount(&srcPtr);
277 :
278 0 : nBytesRemaining -= n + 2;
279 : }
280 :
281 0 : numBytes = sum;
282 :
283 0 : if (numBytes == 0)
284 : {
285 0 : *arr = nullptr;
286 0 : return false;
287 : }
288 :
289 0 : *arr = new Byte[numBytes];
290 0 : if (!*arr)
291 0 : return false;
292 :
293 0 : return decompress(arrRLE, nBytesRemainingIn, *arr, numBytes);
294 : }
295 :
296 : // -------------------------------------------------------------------------- ;
297 :
298 9 : bool RLE::decompress(const Byte* arrRLE, size_t nBytesRemaining, Byte* arr, size_t arrSize)
299 : {
300 9 : if (!arrRLE || !arr || nBytesRemaining < 2)
301 0 : return false;
302 :
303 9 : const Byte* srcPtr = arrRLE;
304 9 : size_t arrIdx = 0;
305 9 : nBytesRemaining -= 2;
306 :
307 9 : short cnt = readCount(&srcPtr);
308 18 : while (cnt != -32768)
309 : {
310 9 : int i = (cnt <= 0) ? -cnt : cnt;
311 9 : size_t m = (cnt <= 0) ? 1 : (size_t)i; // <= not < to fail gracefully in case of corrupted blob for old version <= 2 which had no checksum
312 :
313 9 : if (nBytesRemaining < m + 2 || arrIdx + i > arrSize)
314 0 : return false;
315 :
316 9 : if (cnt > 0)
317 : {
318 10 : while (i--) arr[arrIdx++] = *srcPtr++;
319 : }
320 : else
321 : {
322 4 : Byte b = *srcPtr++;
323 104 : while (i--) arr[arrIdx++] = b;
324 : }
325 :
326 9 : nBytesRemaining -= m + 2;
327 9 : cnt = readCount(&srcPtr);
328 : }
329 :
330 9 : return true;
331 : }
332 :
333 : // -------------------------------------------------------------------------- ;
334 :
335 18 : void RLE::writeCount(short cnt, Byte** ppCnt, Byte** ppDst)
336 : {
337 : SWAP_2(cnt); // write short's in little endian byte order, always
338 : #ifdef CSA_BUILD
339 : (*ppCnt)[0] = static_cast<Byte>(cnt);
340 : (*ppCnt)[1] = static_cast<Byte>(cnt >> 8);
341 : #else
342 18 : memcpy(*ppCnt, &cnt, sizeof(short));
343 : #endif
344 18 : *ppCnt = *ppDst;
345 18 : *ppDst += 2;
346 18 : }
347 :
348 : // -------------------------------------------------------------------------- ;
349 :
350 18 : short RLE::readCount(const Byte** ppCnt)
351 : {
352 : short cnt;
353 18 : memcpy(&cnt, *ppCnt, sizeof(short));
354 : SWAP_2(cnt);
355 18 : *ppCnt += 2;
356 18 : return cnt;
357 : }
358 :
359 : // -------------------------------------------------------------------------- ;
360 :
|
