Point Cloud Library (PCL) 1.15.0
Loading...
Searching...
No Matches
entropy_range_coder.hpp
1/*
2 * Software License Agreement (BSD License)
3 *
4 * Point Cloud Library (PCL) - www.pointclouds.org
5 * Copyright (c) 2010-2012, Willow Garage, Inc.
6 *
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 *
13 * * Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * * Redistributions in binary form must reproduce the above
16 * copyright notice, this list of conditions and the following
17 * disclaimer in the documentation and/or other materials provided
18 * with the distribution.
19 * * Neither the name of Willow Garage, Inc. nor the names of its
20 * contributors may be used to endorse or promote products derived
21 * from this software without specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
26 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
27 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
28 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
29 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
30 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
31 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
33 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
34 * POSSIBILITY OF SUCH DAMAGE.
35 *
36 *
37 * range coder based on Dmitry Subbotin's carry-less implementation (http://www.compression.ru/ds/)
38 * Added optimized symbol lookup and fixed/static frequency tables
39 *
40 */
41#pragma once
42
43#include <pcl/compression/entropy_range_coder.h>
44#include <iostream>
45#include <vector>
46#include <cstring>
47#include <algorithm>
48
49//////////////////////////////////////////////////////////////////////////////////////////////
50unsigned long
51pcl::AdaptiveRangeCoder::encodeCharVectorToStream (const std::vector<char>& inputByteVector_arg,
52 std::ostream& outputByteStream_arg)
53{
54 DWord freq[257];
55
56 // define limits
57 constexpr DWord top = static_cast<DWord>(1) << 24;
58 constexpr DWord bottom = static_cast<DWord>(1) << 16;
59 constexpr DWord maxRange = static_cast<DWord>(1) << 16;
60
61 auto input_size = static_cast<unsigned> (inputByteVector_arg.size ());
62
63 // init output vector
64 outputCharVector_.clear ();
65 outputCharVector_.reserve (sizeof(char) * input_size);
66
67 unsigned int readPos = 0;
68
69 DWord low = 0;
70 DWord range = static_cast<DWord> (-1);
71
72 // initialize cumulative frequency table
73 for (unsigned int i = 0; i < 257; i++)
74 freq[i] = i;
75
76 // scan input
77 while (readPos < input_size)
78 {
79 // read byte
80 std::uint8_t ch = inputByteVector_arg[readPos++];
81
82 // map range
83 low += freq[ch] * (range /= freq[256]);
84 range *= freq[ch + 1] - freq[ch];
85
86 // check range limits
87 while ((low ^ (low + range)) < top || ((range < bottom) && ((range = -static_cast<int>(low) & (bottom - 1)), 1)))
88 {
89 char out = static_cast<char> (low >> 24);
90 range <<= 8;
91 low <<= 8;
92 outputCharVector_.push_back (out);
93 }
94
95 // update frequency table
96 for (unsigned int j = ch + 1; j < 257; j++)
97 freq[j]++;
98
99 // detect overflow
100 if (freq[256] >= maxRange)
101 {
102 // rescale
103 for (unsigned int f = 1; f <= 256; f++)
104 {
105 freq[f] /= 2;
106 if (freq[f] <= freq[f - 1])
107 freq[f] = freq[f - 1] + 1;
108 }
109 }
110
111 }
112
113 // flush remaining data
114 for (unsigned int i = 0; i < 4; i++)
115 {
116 char out = static_cast<char> (low >> 24);
117 outputCharVector_.push_back (out);
118 low <<= 8;
119 }
120
121 // write to stream
122 outputByteStream_arg.write (outputCharVector_.data(), outputCharVector_.size ());
123
124 return (static_cast<unsigned long> (outputCharVector_.size ()));
125}
126
127//////////////////////////////////////////////////////////////////////////////////////////////
128unsigned long
129pcl::AdaptiveRangeCoder::decodeStreamToCharVector (std::istream& inputByteStream_arg,
130 std::vector<char>& outputByteVector_arg)
131{
132 DWord freq[257];
133
134 // define limits
135 constexpr DWord top = static_cast<DWord>(1) << 24;
136 constexpr DWord bottom = static_cast<DWord>(1) << 16;
137 constexpr DWord maxRange = static_cast<DWord>(1) << 16;
138
139 auto output_size = static_cast<unsigned> (outputByteVector_arg.size ());
140
141 unsigned long streamByteCount = 0;
142
143 unsigned int outputBufPos = 0;
144
145 DWord code = 0;
146 DWord low = 0;
147 DWord range = static_cast<DWord> (-1);
148
149 // init decoding
150 for (unsigned int i = 0; i < 4; i++)
151 {
152 std::uint8_t ch;
153 inputByteStream_arg.read (reinterpret_cast<char*> (&ch), sizeof(char));
154 streamByteCount += sizeof(char);
155 code = (code << 8) | ch;
156 }
157
158 // init cumulative frequency table
159 for (unsigned int i = 0; i <= 256; i++)
160 freq[i] = i;
161
162 // decoding loop
163 for (unsigned int i = 0; i < output_size; i++)
164 {
165 std::uint8_t symbol = 0;
166 std::uint8_t sSize = 256 / 2;
167
168 // map code to range
169 DWord count = (code - low) / (range /= freq[256]);
170
171 // find corresponding symbol
172 while (sSize > 0)
173 {
174 if (freq[symbol + sSize] <= count)
175 {
176 symbol = static_cast<std::uint8_t> (symbol + sSize);
177 }
178 sSize /= 2;
179 }
180
181 // output symbol
182 outputByteVector_arg[outputBufPos++] = symbol;
183
184 // update range limits
185 low += freq[symbol] * range;
186 range *= freq[symbol + 1] - freq[symbol];
187
188 // decode range limits
189 while ((low ^ (low + range)) < top || ((range < bottom) && ((range = -static_cast<int>(low) & (bottom - 1)), 1)))
190 {
191 std::uint8_t ch;
192 inputByteStream_arg.read (reinterpret_cast<char*> (&ch), sizeof(char));
193 streamByteCount += sizeof(char);
194 code = code << 8 | ch;
195 range <<= 8;
196 low <<= 8;
197 }
198
199 // update cumulative frequency table
200 for (unsigned int j = symbol + 1; j < 257; j++)
201 freq[j]++;
202
203 // detect overflow
204 if (freq[256] >= maxRange)
205 {
206 // rescale
207 for (unsigned int f = 1; f <= 256; f++)
208 {
209 freq[f] /= 2;
210 if (freq[f] <= freq[f - 1])
211 freq[f] = freq[f - 1] + 1;
212 }
213 }
214 }
215
216 return (streamByteCount);
217}
218
219//////////////////////////////////////////////////////////////////////////////////////////////
220unsigned long
221pcl::StaticRangeCoder::encodeIntVectorToStream (std::vector<unsigned int>& inputIntVector_arg,
222 std::ostream& outputByteStream_arg)
223{
224 // define numerical limits
225 constexpr std::uint64_t top = static_cast<std::uint64_t>(1) << 56;
226 constexpr std::uint64_t bottom = static_cast<std::uint64_t>(1) << 48;
227 constexpr std::uint64_t maxRange = static_cast<std::uint64_t>(1) << 48;
228
229 auto input_size = static_cast<unsigned long> (inputIntVector_arg.size ());
230
231 // init output vector
232 outputCharVector_.clear ();
233 outputCharVector_.reserve ((sizeof(char) * input_size * 2));
234
235 std::uint64_t frequencyTableSize = 1;
236
237 unsigned int readPos = 0;
238
239 // calculate frequency table
240 cFreqTable_[0] = cFreqTable_[1] = 0;
241 while (readPos < input_size)
242 {
243 unsigned int inputSymbol = inputIntVector_arg[readPos++];
244
245 if (inputSymbol + 1 >= frequencyTableSize)
246 {
247 // frequency table is to small -> adaptively extend it
248 std::uint64_t oldfrequencyTableSize;
249 oldfrequencyTableSize = frequencyTableSize;
250
251 do
252 {
253 // increase frequency table size by factor 2
254 frequencyTableSize <<= 1;
255 } while (inputSymbol + 1 > frequencyTableSize);
256
257 if (cFreqTable_.size () < frequencyTableSize + 1)
258 {
259 // resize frequency vector
260 cFreqTable_.resize (static_cast<std::size_t> (frequencyTableSize + 1));
261 }
262
263 // init new frequency range with zero
264 std::fill_n(&cFreqTable_[oldfrequencyTableSize + 1],
265 frequencyTableSize - oldfrequencyTableSize, 0);
266 }
267 cFreqTable_[inputSymbol + 1]++;
268 }
269 frequencyTableSize++;
270
271 // convert to cumulative frequency table
272 for (std::uint64_t f = 1; f < frequencyTableSize; f++)
273 {
274 cFreqTable_[f] = cFreqTable_[f - 1] + cFreqTable_[f];
275 if (cFreqTable_[f] <= cFreqTable_[f - 1])
276 cFreqTable_[f] = cFreqTable_[f - 1] + 1;
277 }
278
279 // rescale if numerical limits are reached
280 while (cFreqTable_[static_cast<std::size_t> (frequencyTableSize - 1)] >= maxRange)
281 {
282 for (std::size_t f = 1; f < cFreqTable_.size (); f++)
283 {
284 cFreqTable_[f] /= 2;
285 ;
286 if (cFreqTable_[f] <= cFreqTable_[f - 1])
287 cFreqTable_[f] = cFreqTable_[f - 1] + 1;
288 }
289 }
290
291 // calculate amount of bytes per frequency table entry
292 auto frequencyTableByteSize = static_cast<std::uint8_t> (std::ceil (
293 std::log2 (static_cast<double> (cFreqTable_[static_cast<std::size_t> (frequencyTableSize - 1)] + 1)) / 8.0));
294
295 // write size of frequency table to output stream
296 outputByteStream_arg.write (reinterpret_cast<const char*> (&frequencyTableSize), sizeof(frequencyTableSize));
297 outputByteStream_arg.write (reinterpret_cast<const char*> (&frequencyTableByteSize), sizeof(frequencyTableByteSize));
298
299 unsigned long streamByteCount = sizeof(frequencyTableSize) + sizeof(frequencyTableByteSize);
300
301 // write cumulative frequency table to output stream
302 for (std::uint64_t f = 1; f < frequencyTableSize; f++)
303 {
304 outputByteStream_arg.write (reinterpret_cast<const char*> (&cFreqTable_[f]), frequencyTableByteSize);
305 streamByteCount += frequencyTableByteSize;
306 }
307
308 readPos = 0;
309 std::uint64_t low = 0;
310 auto range = static_cast<std::uint64_t> (-1);
311
312 // start encoding
313 while (readPos < input_size)
314 {
315
316 // read symbol
317 unsigned int inputsymbol = inputIntVector_arg[readPos++];
318
319 // map to range
320 low += cFreqTable_[inputsymbol] * (range /= cFreqTable_[static_cast<std::size_t> (frequencyTableSize - 1)]);
321 range *= cFreqTable_[inputsymbol + 1] - cFreqTable_[inputsymbol];
322
323 // check range limits
324 while ((low ^ (low + range)) < top || ((range < bottom) && ((range = -low & (bottom - 1)), 1)))
325 {
326 char out = static_cast<char> (low >> 56);
327 range <<= 8;
328 low <<= 8;
329 outputCharVector_.push_back (out);
330 }
331
332 }
333
334 // flush remaining data
335 for (unsigned int i = 0; i < 8; i++)
336 {
337 char out = static_cast<char> (low >> 56);
338 outputCharVector_.push_back (out);
339 low <<= 8;
340 }
341
342 // write encoded data to stream
343 outputByteStream_arg.write (outputCharVector_.data(), outputCharVector_.size ());
344
345 streamByteCount += static_cast<unsigned long> (outputCharVector_.size ());
346
347 return (streamByteCount);
348}
349
350//////////////////////////////////////////////////////////////////////////////////////////////
351unsigned long
352pcl::StaticRangeCoder::decodeStreamToIntVector (std::istream& inputByteStream_arg,
353 std::vector<unsigned int>& outputIntVector_arg)
354{
355 // define range limits
356 constexpr std::uint64_t top = static_cast<std::uint64_t>(1) << 56;
357 constexpr std::uint64_t bottom = static_cast<std::uint64_t>(1) << 48;
358
359 std::uint64_t frequencyTableSize;
360 unsigned char frequencyTableByteSize;
361
362 unsigned int outputBufPos = 0;
363 std::size_t output_size = outputIntVector_arg.size ();
364
365 // read size of cumulative frequency table from stream
366 inputByteStream_arg.read (reinterpret_cast<char*> (&frequencyTableSize), sizeof(frequencyTableSize));
367 inputByteStream_arg.read (reinterpret_cast<char*> (&frequencyTableByteSize), sizeof(frequencyTableByteSize));
368
369 unsigned long streamByteCount = sizeof(frequencyTableSize) + sizeof(frequencyTableByteSize);
370
371 // check size of frequency table vector
372 if (cFreqTable_.size () < frequencyTableSize)
373 {
374 cFreqTable_.resize (static_cast<std::size_t> (frequencyTableSize));
375 }
376
377 // init with zero
378 std::fill(cFreqTable_.begin(), cFreqTable_.end(), 0);
379
380 // read cumulative frequency table
381 for (std::uint64_t f = 1; f < frequencyTableSize; f++)
382 {
383 inputByteStream_arg.read (reinterpret_cast<char *> (&cFreqTable_[f]), frequencyTableByteSize);
384 streamByteCount += frequencyTableByteSize;
385 }
386
387 // initialize range & code
388 std::uint64_t code = 0;
389 std::uint64_t low = 0;
390 auto range = static_cast<std::uint64_t> (-1);
391
392 // init code vector
393 for (unsigned int i = 0; i < 8; i++)
394 {
395 std::uint8_t ch;
396 inputByteStream_arg.read (reinterpret_cast<char*> (&ch), sizeof(char));
397 streamByteCount += sizeof(char);
398 code = (code << 8) | ch;
399 }
400
401 // decoding
402 for (std::size_t i = 0; i < output_size; i++)
403 {
404 std::uint64_t count = (code - low) / (range /= cFreqTable_[static_cast<std::size_t> (frequencyTableSize - 1)]);
405
406 // symbol lookup in cumulative frequency table
407 std::uint64_t symbol = 0;
408 std::uint64_t sSize = (frequencyTableSize - 1) / 2;
409 while (sSize > 0)
410 {
411 if (cFreqTable_[static_cast<std::size_t> (symbol + sSize)] <= count)
412 {
413 symbol += sSize;
414 }
415 sSize /= 2;
416 }
417
418 // write symbol to output stream
419 outputIntVector_arg[outputBufPos++] = static_cast<unsigned int> (symbol);
420
421 // map to range
422 low += cFreqTable_[static_cast<std::size_t> (symbol)] * range;
423 range *= cFreqTable_[static_cast<std::size_t> (symbol + 1)] - cFreqTable_[static_cast<std::size_t> (symbol)];
424
425 // check range limits
426 while ((low ^ (low + range)) < top || ((range < bottom) && ((range = -low & (bottom - 1)), 1)))
427 {
428 std::uint8_t ch;
429 inputByteStream_arg.read (reinterpret_cast<char*> (&ch), sizeof(char));
430 streamByteCount += sizeof(char);
431 code = code << 8 | ch;
432 range <<= 8;
433 low <<= 8;
434 }
435 }
436
437 return streamByteCount;
438}
439
440//////////////////////////////////////////////////////////////////////////////////////////////
441unsigned long
442pcl::StaticRangeCoder::encodeCharVectorToStream (const std::vector<char>& inputByteVector_arg,
443 std::ostream& outputByteStream_arg)
444{
445 DWord freq[257];
446
447 // define numerical limits
448 constexpr DWord top = static_cast<DWord>(1) << 24;
449 constexpr DWord bottom = static_cast<DWord>(1) << 16;
450 constexpr DWord maxRange = static_cast<DWord>(1) << 16;
451
452 DWord low, range;
453
454 unsigned int input_size;
455 input_size = static_cast<unsigned int> (inputByteVector_arg.size ());
456
457 // init output vector
458 outputCharVector_.clear ();
459 outputCharVector_.reserve (sizeof(char) * input_size);
460
461 std::uint64_t FreqHist[257]{};
462
463 // calculate frequency table
464 unsigned int readPos = 0;
465 while (readPos < input_size)
466 {
467 auto symbol = static_cast<std::uint8_t> (inputByteVector_arg[readPos++]);
468 FreqHist[symbol + 1]++;
469 }
470
471 // convert to cumulative frequency table
472 freq[0] = 0;
473 for (int f = 1; f <= 256; f++)
474 {
475 freq[f] = freq[f - 1] + static_cast<DWord> (FreqHist[f]);
476 if (freq[f] <= freq[f - 1])
477 freq[f] = freq[f - 1] + 1;
478 }
479
480 // rescale if numerical limits are reached
481 while (freq[256] >= maxRange)
482 {
483 for (int f = 1; f <= 256; f++)
484 {
485 freq[f] /= 2;
486 ;
487 if (freq[f] <= freq[f - 1])
488 freq[f] = freq[f - 1] + 1;
489 }
490 }
491
492 // write cumulative frequency table to output stream
493 outputByteStream_arg.write (reinterpret_cast<const char*> (&freq[0]), sizeof(freq));
494 unsigned long streamByteCount = sizeof(freq);
495
496 readPos = 0;
497
498 low = 0;
499 range = static_cast<DWord> (-1);
500
501 // start encoding
502 while (readPos < input_size)
503 {
504 // read symbol
505 std::uint8_t ch = inputByteVector_arg[readPos++];
506
507 // map to range
508 low += freq[ch] * (range /= freq[256]);
509 range *= freq[ch + 1] - freq[ch];
510
511 // check range limits
512 while ((low ^ (low + range)) < top || ((range < bottom) && ((range = -static_cast<int>(low) & (bottom - 1)), 1)))
513 {
514 char out = static_cast<char> (low >> 24);
515 range <<= 8;
516 low <<= 8;
517 outputCharVector_.push_back (out);
518 }
519
520 }
521
522 // flush remaining data
523 for (int i = 0; i < 4; i++)
524 {
525 char out = static_cast<char> (low >> 24);
526 outputCharVector_.push_back (out);
527 low <<= 8;
528 }
529
530 // write encoded data to stream
531 outputByteStream_arg.write (outputCharVector_.data(), outputCharVector_.size ());
532
533 streamByteCount += static_cast<unsigned long> (outputCharVector_.size ());
534
535 return (streamByteCount);
536}
537
538//////////////////////////////////////////////////////////////////////////////////////////////
539unsigned long
540pcl::StaticRangeCoder::decodeStreamToCharVector (std::istream& inputByteStream_arg,
541 std::vector<char>& outputByteVector_arg)
542{
543 DWord freq[257];
544
545 // define range limits
546 constexpr DWord top = static_cast<DWord>(1) << 24;
547 constexpr DWord bottom = static_cast<DWord>(1) << 16;
548
549 DWord low, range;
550 DWord code;
551
552 unsigned int outputBufPos;
553 unsigned int output_size;
554
555 unsigned long streamByteCount;
556
557 streamByteCount = 0;
558
559 output_size = static_cast<unsigned int> (outputByteVector_arg.size ());
560
561 outputBufPos = 0;
562
563 // read cumulative frequency table
564 inputByteStream_arg.read (reinterpret_cast<char*> (&freq[0]), sizeof(freq));
565 streamByteCount += sizeof(freq);
566
567 code = 0;
568 low = 0;
569 range = static_cast<DWord> (-1);
570
571 // init code
572 for (unsigned int i = 0; i < 4; i++)
573 {
574 std::uint8_t ch;
575 inputByteStream_arg.read (reinterpret_cast<char*> (&ch), sizeof(char));
576 streamByteCount += sizeof(char);
577 code = (code << 8) | ch;
578 }
579
580 // decoding
581 for (unsigned int i = 0; i < output_size; i++)
582 {
583 // symbol lookup in cumulative frequency table
584 std::uint8_t symbol = 0;
585 std::uint8_t sSize = 256 / 2;
586
587 DWord count = (code - low) / (range /= freq[256]);
588
589 while (sSize > 0)
590 {
591 if (freq[symbol + sSize] <= count)
592 {
593 symbol = static_cast<std::uint8_t> (symbol + sSize);
594 }
595 sSize /= 2;
596 }
597
598 // write symbol to output stream
599 outputByteVector_arg[outputBufPos++] = symbol;
600
601 low += freq[symbol] * range;
602 range *= freq[symbol + 1] - freq[symbol];
603
604 // check range limits
605 while ((low ^ (low + range)) < top || ((range < bottom) && ((range = -static_cast<int>(low) & (bottom - 1)), 1)))
606 {
607 std::uint8_t ch;
608 inputByteStream_arg.read (reinterpret_cast<char*> (&ch), sizeof(char));
609 streamByteCount += sizeof(char);
610 code = code << 8 | ch;
611 range <<= 8;
612 low <<= 8;
613 }
614
615 }
616
617 return (streamByteCount);
618}
619
unsigned long decodeStreamToCharVector(std::istream &inputByteStream_arg, std::vector< char > &outputByteVector_arg)
Decode char stream to output vector.
unsigned long encodeCharVectorToStream(const std::vector< char > &inputByteVector_arg, std::ostream &outputByteStream_arg)
Encode char vector to output stream.
unsigned long decodeStreamToIntVector(std::istream &inputByteStream_arg, std::vector< unsigned int > &outputIntVector_arg)
Decode stream to output integer vector.
unsigned long encodeCharVectorToStream(const std::vector< char > &inputByteVector_arg, std::ostream &outputByteStream_arg)
Encode char vector to output stream.
unsigned long decodeStreamToCharVector(std::istream &inputByteStream_arg, std::vector< char > &outputByteVector_arg)
Decode char stream to output vector.
unsigned long encodeIntVectorToStream(std::vector< unsigned int > &inputIntVector_arg, std::ostream &outputByterStream_arg)
Encode integer vector to output stream.