00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042 #ifndef __PCL_IO_RANGECODING__HPP
00043 #define __PCL_IO_RANGECODING__HPP
00044
00045 #include <pcl/compression/entropy_range_coder.h>
00046 #include <map>
00047 #include <iostream>
00048 #include <vector>
00049 #include <string.h>
00050 #include <algorithm>
00051 #include <stdio.h>
00052
00054 unsigned long
00055 pcl::AdaptiveRangeCoder::encodeCharVectorToStream (const std::vector<char>& inputByteVector_arg,
00056 std::ostream& outputByteStream_arg)
00057 {
00058 DWord freq[257];
00059 uint8_t ch;
00060 unsigned int i, j, f;
00061 char out;
00062
00063
00064 const DWord top = static_cast<DWord> (1) << 24;
00065 const DWord bottom = static_cast<DWord> (1) << 16;
00066 const DWord maxRange = static_cast<DWord> (1) << 16;
00067
00068 DWord low, range;
00069
00070 unsigned int readPos;
00071 unsigned int input_size;
00072
00073 input_size = static_cast<unsigned> (inputByteVector_arg.size ());
00074
00075
00076 outputCharVector_.clear ();
00077 outputCharVector_.reserve (sizeof(char) * input_size);
00078
00079 readPos = 0;
00080
00081 low = 0;
00082 range = static_cast<DWord> (-1);
00083
00084
00085 for (i = 0; i < 257; i++)
00086 freq[i] = i;
00087
00088
00089 while (readPos < input_size)
00090 {
00091
00092
00093 ch = inputByteVector_arg[readPos++];
00094
00095
00096 low += freq[ch] * (range /= freq[256]);
00097 range *= freq[ch + 1] - freq[ch];
00098
00099
00100 while ((low ^ (low + range)) < top || ((range < bottom) && ((range = -int (low) & (bottom - 1)), 1)))
00101 {
00102 out = static_cast<char> (low >> 24);
00103 range <<= 8;
00104 low <<= 8;
00105 outputCharVector_.push_back (out);
00106 }
00107
00108
00109 for (j = ch + 1; j < 257; j++)
00110 freq[j]++;
00111
00112
00113 if (freq[256] >= maxRange)
00114 {
00115
00116 for (f = 1; f <= 256; f++)
00117 {
00118 freq[f] /= 2;
00119 if (freq[f] <= freq[f - 1])
00120 freq[f] = freq[f - 1] + 1;
00121 }
00122 }
00123
00124 }
00125
00126
00127 for (i = 0; i < 4; i++)
00128 {
00129 out = static_cast<char> (low >> 24);
00130 outputCharVector_.push_back (out);
00131 low <<= 8;
00132 }
00133
00134
00135 outputByteStream_arg.write (&outputCharVector_[0], outputCharVector_.size ());
00136
00137 return (static_cast<unsigned long> (outputCharVector_.size ()));
00138
00139 }
00140
00142 unsigned long
00143 pcl::AdaptiveRangeCoder::decodeStreamToCharVector (std::istream& inputByteStream_arg,
00144 std::vector<char>& outputByteVector_arg)
00145 {
00146 uint8_t ch;
00147 DWord freq[257];
00148 unsigned int i, j, f;
00149
00150
00151 const DWord top = static_cast<DWord> (1) << 24;
00152 const DWord bottom = static_cast<DWord> (1) << 16;
00153 const DWord maxRange = static_cast<DWord> (1) << 16;
00154
00155 DWord low, range;
00156 DWord code;
00157
00158 unsigned int outputBufPos;
00159 unsigned int output_size = static_cast<unsigned> (outputByteVector_arg.size ());
00160
00161 unsigned long streamByteCount;
00162
00163 streamByteCount = 0;
00164
00165 outputBufPos = 0;
00166
00167 code = 0;
00168 low = 0;
00169 range = static_cast<DWord> (-1);
00170
00171
00172 for (i = 0; i < 4; i++)
00173 {
00174 inputByteStream_arg.read (reinterpret_cast<char*> (&ch), sizeof(char));
00175 streamByteCount += sizeof(char);
00176 code = (code << 8) | ch;
00177 }
00178
00179
00180 for (i = 0; i <= 256; i++)
00181 freq[i] = i;
00182
00183
00184 for (i = 0; i < output_size; i++)
00185 {
00186 uint8_t symbol = 0;
00187 uint8_t sSize = 256 / 2;
00188
00189
00190 DWord count = (code - low) / (range /= freq[256]);
00191
00192
00193 while (sSize > 0)
00194 {
00195 if (freq[symbol + sSize] <= count)
00196 {
00197 symbol = static_cast<uint8_t> (symbol + sSize);
00198 }
00199 sSize /= 2;
00200 }
00201
00202
00203 outputByteVector_arg[outputBufPos++] = symbol;
00204
00205
00206 low += freq[symbol] * range;
00207 range *= freq[symbol + 1] - freq[symbol];
00208
00209
00210 while ((low ^ (low + range)) < top || ((range < bottom) && ((range = -int (low) & (bottom - 1)), 1)))
00211 {
00212 inputByteStream_arg.read (reinterpret_cast<char*> (&ch), sizeof(char));
00213 streamByteCount += sizeof(char);
00214 code = code << 8 | ch;
00215 range <<= 8;
00216 low <<= 8;
00217 }
00218
00219
00220 for (j = symbol + 1; j < 257; j++)
00221 freq[j]++;
00222
00223
00224 if (freq[256] >= maxRange)
00225 {
00226
00227 for (f = 1; f <= 256; f++)
00228 {
00229 freq[f] /= 2;
00230 if (freq[f] <= freq[f - 1])
00231 freq[f] = freq[f - 1] + 1;
00232 }
00233 }
00234 }
00235
00236 return (streamByteCount);
00237
00238 }
00239
00241 unsigned long
00242 pcl::StaticRangeCoder::encodeIntVectorToStream (std::vector<unsigned int>& inputIntVector_arg,
00243 std::ostream& outputByteStream_arg)
00244 {
00245
00246 unsigned int inputsymbol;
00247 unsigned int i, f;
00248 char out;
00249
00250 uint64_t frequencyTableSize;
00251 uint8_t frequencyTableByteSize;
00252
00253
00254 const uint64_t top = static_cast<uint64_t> (1) << 56;
00255 const uint64_t bottom = static_cast<uint64_t> (1) << 48;
00256 const uint64_t maxRange = static_cast<uint64_t> (1) << 48;
00257
00258 unsigned long input_size = static_cast<unsigned long> (inputIntVector_arg.size ());
00259 uint64_t low, range;
00260
00261 unsigned int inputSymbol;
00262
00263 unsigned int readPos;
00264
00265 unsigned long streamByteCount;
00266
00267 streamByteCount = 0;
00268
00269
00270 outputCharVector_.clear ();
00271 outputCharVector_.reserve ((sizeof(char) * input_size * 2));
00272
00273 frequencyTableSize = 1;
00274
00275 readPos = 0;
00276
00277
00278 cFreqTable_[0] = cFreqTable_[1] = 0;
00279 while (readPos < input_size)
00280 {
00281 inputSymbol = inputIntVector_arg[readPos++];
00282
00283 if (inputSymbol + 1 >= frequencyTableSize)
00284 {
00285
00286 uint64_t oldfrequencyTableSize;
00287 oldfrequencyTableSize = frequencyTableSize;
00288
00289 do
00290 {
00291
00292 frequencyTableSize <<= 1;
00293 } while (inputSymbol + 1 > frequencyTableSize);
00294
00295 if (cFreqTable_.size () < frequencyTableSize + 1)
00296 {
00297
00298 cFreqTable_.resize (static_cast<std::size_t> (frequencyTableSize + 1));
00299 }
00300
00301
00302 memset (&cFreqTable_[static_cast<std::size_t> (oldfrequencyTableSize + 1)], 0,
00303 sizeof(uint64_t) * static_cast<std::size_t> (frequencyTableSize - oldfrequencyTableSize));
00304 }
00305 cFreqTable_[inputSymbol + 1]++;
00306 }
00307 frequencyTableSize++;
00308
00309
00310 for (f = 1; f < frequencyTableSize; f++)
00311 {
00312 cFreqTable_[f] = cFreqTable_[f - 1] + cFreqTable_[f];
00313 if (cFreqTable_[f] <= cFreqTable_[f - 1])
00314 cFreqTable_[f] = cFreqTable_[f - 1] + 1;
00315 }
00316
00317
00318 while (cFreqTable_[static_cast<std::size_t> (frequencyTableSize - 1)] >= maxRange)
00319 {
00320 for (f = 1; f < cFreqTable_.size (); f++)
00321 {
00322 cFreqTable_[f] /= 2;
00323 ;
00324 if (cFreqTable_[f] <= cFreqTable_[f - 1])
00325 cFreqTable_[f] = cFreqTable_[f - 1] + 1;
00326 }
00327 }
00328
00329
00330 frequencyTableByteSize = static_cast<uint8_t> (ceil (
00331 Log2 (static_cast<double> (cFreqTable_[static_cast<std::size_t> (frequencyTableSize - 1)])) / 8.0));
00332
00333
00334 outputByteStream_arg.write (reinterpret_cast<const char*> (&frequencyTableSize), sizeof(frequencyTableSize));
00335 outputByteStream_arg.write (reinterpret_cast<const char*> (&frequencyTableByteSize), sizeof(frequencyTableByteSize));
00336
00337 streamByteCount += sizeof(frequencyTableSize) + sizeof(frequencyTableByteSize);
00338
00339
00340 for (f = 1; f < frequencyTableSize; f++)
00341 {
00342 outputByteStream_arg.write (reinterpret_cast<const char*> (&cFreqTable_[f]), frequencyTableByteSize);
00343 streamByteCount += frequencyTableByteSize;
00344 }
00345
00346 readPos = 0;
00347 low = 0;
00348 range = static_cast<uint64_t> (-1);
00349
00350
00351 while (readPos < input_size)
00352 {
00353
00354
00355 inputsymbol = inputIntVector_arg[readPos++];
00356
00357
00358 low += cFreqTable_[inputsymbol] * (range /= cFreqTable_[static_cast<std::size_t> (frequencyTableSize - 1)]);
00359 range *= cFreqTable_[inputsymbol + 1] - cFreqTable_[inputsymbol];
00360
00361
00362 while ((low ^ (low + range)) < top || ((range < bottom) && ((range = -low & (bottom - 1)), 1)))
00363 {
00364 out = static_cast<char> (low >> 56);
00365 range <<= 8;
00366 low <<= 8;
00367 outputCharVector_.push_back (out);
00368 }
00369
00370 }
00371
00372
00373 for (i = 0; i < 8; i++)
00374 {
00375 out = static_cast<char> (low >> 56);
00376 outputCharVector_.push_back (out);
00377 low <<= 8;
00378 }
00379
00380
00381 outputByteStream_arg.write (&outputCharVector_[0], outputCharVector_.size ());
00382
00383 streamByteCount += static_cast<unsigned long> (outputCharVector_.size ());
00384
00385 return (streamByteCount);
00386 }
00387
00389 unsigned long
00390 pcl::StaticRangeCoder::decodeStreamToIntVector (std::istream& inputByteStream_arg,
00391 std::vector<unsigned int>& outputIntVector_arg)
00392 {
00393 uint8_t ch;
00394 unsigned int i, f;
00395
00396
00397 const uint64_t top = static_cast<uint64_t> (1) << 56;
00398 const uint64_t bottom = static_cast<uint64_t> (1) << 48;
00399
00400 uint64_t low, range;
00401 uint64_t code;
00402
00403 unsigned int outputBufPos;
00404 unsigned long output_size;
00405
00406 uint64_t frequencyTableSize;
00407 unsigned char frequencyTableByteSize;
00408
00409 unsigned long streamByteCount;
00410
00411 streamByteCount = 0;
00412
00413 outputBufPos = 0;
00414 output_size = static_cast<unsigned long> (outputIntVector_arg.size ());
00415
00416
00417 inputByteStream_arg.read (reinterpret_cast<char*> (&frequencyTableSize), sizeof(frequencyTableSize));
00418 inputByteStream_arg.read (reinterpret_cast<char*> (&frequencyTableByteSize), sizeof(frequencyTableByteSize));
00419
00420 streamByteCount += sizeof(frequencyTableSize) + sizeof(frequencyTableByteSize);
00421
00422
00423 if (cFreqTable_.size () < frequencyTableSize)
00424 {
00425 cFreqTable_.resize (static_cast<std::size_t> (frequencyTableSize));
00426 }
00427
00428
00429 memset (&cFreqTable_[0], 0, sizeof(uint64_t) * static_cast<std::size_t> (frequencyTableSize));
00430
00431
00432 for (f = 1; f < frequencyTableSize; f++)
00433 {
00434 inputByteStream_arg.read (reinterpret_cast<char *> (&cFreqTable_[f]), frequencyTableByteSize);
00435 streamByteCount += frequencyTableByteSize;
00436 }
00437
00438
00439 code = 0;
00440 low = 0;
00441 range = static_cast<uint64_t> (-1);
00442
00443
00444 for (i = 0; i < 8; i++)
00445 {
00446 inputByteStream_arg.read (reinterpret_cast<char*> (&ch), sizeof(char));
00447 streamByteCount += sizeof(char);
00448 code = (code << 8) | ch;
00449 }
00450
00451
00452 for (i = 0; i < output_size; i++)
00453 {
00454 uint64_t count = (code - low) / (range /= cFreqTable_[static_cast<std::size_t> (frequencyTableSize - 1)]);
00455
00456
00457 uint64_t symbol = 0;
00458 uint64_t sSize = (frequencyTableSize - 1) / 2;
00459 while (sSize > 0)
00460 {
00461 if (cFreqTable_[static_cast<std::size_t> (symbol + sSize)] <= count)
00462 {
00463 symbol += sSize;
00464 }
00465 sSize /= 2;
00466 }
00467
00468
00469 outputIntVector_arg[outputBufPos++] = static_cast<unsigned int> (symbol);
00470
00471
00472 low += cFreqTable_[static_cast<std::size_t> (symbol)] * range;
00473 range *= cFreqTable_[static_cast<std::size_t> (symbol + 1)] - cFreqTable_[static_cast<std::size_t> (symbol)];
00474
00475
00476 while ((low ^ (low + range)) < top || ((range < bottom) && ((range = -low & (bottom - 1)), 1)))
00477 {
00478 inputByteStream_arg.read (reinterpret_cast<char*> (&ch), sizeof(char));
00479 streamByteCount += sizeof(char);
00480 code = code << 8 | ch;
00481 range <<= 8;
00482 low <<= 8;
00483 }
00484
00485 }
00486
00487 return streamByteCount;
00488 }
00489
00491 unsigned long
00492 pcl::StaticRangeCoder::encodeCharVectorToStream (const std::vector<char>& inputByteVector_arg,
00493 std::ostream& outputByteStream_arg)
00494 {
00495 DWord freq[257];
00496 uint8_t ch;
00497 int i, f;
00498 char out;
00499
00500
00501 const DWord top = static_cast<DWord> (1) << 24;
00502 const DWord bottom = static_cast<DWord> (1) << 16;
00503 const DWord maxRange = static_cast<DWord> (1) << 16;
00504
00505 DWord low, range;
00506
00507 unsigned int input_size;
00508 input_size = static_cast<unsigned int> (inputByteVector_arg.size ());
00509
00510 unsigned int readPos;
00511
00512 unsigned long streamByteCount;
00513
00514 streamByteCount = 0;
00515
00516
00517 outputCharVector_.clear ();
00518 outputCharVector_.reserve (sizeof(char) * input_size);
00519
00520 uint64_t FreqHist[257];
00521
00522
00523 memset (FreqHist, 0, sizeof(FreqHist));
00524 readPos = 0;
00525 while (readPos < input_size)
00526 {
00527 uint8_t symbol = static_cast<uint8_t> (inputByteVector_arg[readPos++]);
00528 FreqHist[symbol + 1]++;
00529 }
00530
00531
00532 freq[0] = 0;
00533 for (f = 1; f <= 256; f++)
00534 {
00535 freq[f] = freq[f - 1] + static_cast<DWord> (FreqHist[f]);
00536 if (freq[f] <= freq[f - 1])
00537 freq[f] = freq[f - 1] + 1;
00538 }
00539
00540
00541 while (freq[256] >= maxRange)
00542 {
00543 for (f = 1; f <= 256; f++)
00544 {
00545 freq[f] /= 2;
00546 ;
00547 if (freq[f] <= freq[f - 1])
00548 freq[f] = freq[f - 1] + 1;
00549 }
00550 }
00551
00552
00553 outputByteStream_arg.write (reinterpret_cast<const char*> (&freq[0]), sizeof(freq));
00554 streamByteCount += sizeof(freq);
00555
00556 readPos = 0;
00557
00558 low = 0;
00559 range = static_cast<DWord> (-1);
00560
00561
00562 while (readPos < input_size)
00563 {
00564
00565
00566 ch = inputByteVector_arg[readPos++];
00567
00568
00569 low += freq[ch] * (range /= freq[256]);
00570 range *= freq[ch + 1] - freq[ch];
00571
00572
00573 while ((low ^ (low + range)) < top || ((range < bottom) && ((range = -int (low) & (bottom - 1)), 1)))
00574 {
00575 out = static_cast<char> (low >> 24);
00576 range <<= 8;
00577 low <<= 8;
00578 outputCharVector_.push_back (out);
00579 }
00580
00581 }
00582
00583
00584 for (i = 0; i < 4; i++)
00585 {
00586 out = static_cast<char> (low >> 24);
00587 outputCharVector_.push_back (out);
00588 low <<= 8;
00589 }
00590
00591
00592 outputByteStream_arg.write (&outputCharVector_[0], outputCharVector_.size ());
00593
00594 streamByteCount += static_cast<unsigned long> (outputCharVector_.size ());
00595
00596 return (streamByteCount);
00597 }
00598
00600 unsigned long
00601 pcl::StaticRangeCoder::decodeStreamToCharVector (std::istream& inputByteStream_arg,
00602 std::vector<char>& outputByteVector_arg)
00603 {
00604 uint8_t ch;
00605 DWord freq[257];
00606 unsigned int i;
00607
00608
00609 const DWord top = static_cast<DWord> (1) << 24;
00610 const DWord bottom = static_cast<DWord> (1) << 16;
00611
00612 DWord low, range;
00613 DWord code;
00614
00615 unsigned int outputBufPos;
00616 unsigned int output_size;
00617
00618 unsigned long streamByteCount;
00619
00620 streamByteCount = 0;
00621
00622 output_size = static_cast<unsigned int> (outputByteVector_arg.size ());
00623
00624 outputBufPos = 0;
00625
00626
00627 inputByteStream_arg.read (reinterpret_cast<char*> (&freq[0]), sizeof(freq));
00628 streamByteCount += sizeof(freq);
00629
00630 code = 0;
00631 low = 0;
00632 range = static_cast<DWord> (-1);
00633
00634
00635 for (i = 0; i < 4; i++)
00636 {
00637 inputByteStream_arg.read (reinterpret_cast<char*> (&ch), sizeof(char));
00638 streamByteCount += sizeof(char);
00639 code = (code << 8) | ch;
00640 }
00641
00642
00643 for (i = 0; i < output_size; i++)
00644 {
00645
00646 uint8_t symbol = 0;
00647 uint8_t sSize = 256 / 2;
00648
00649 DWord count = (code - low) / (range /= freq[256]);
00650
00651 while (sSize > 0)
00652 {
00653 if (freq[symbol + sSize] <= count)
00654 {
00655 symbol = static_cast<uint8_t> (symbol + sSize);
00656 }
00657 sSize /= 2;
00658 }
00659
00660
00661 outputByteVector_arg[outputBufPos++] = symbol;
00662
00663 low += freq[symbol] * range;
00664 range *= freq[symbol + 1] - freq[symbol];
00665
00666
00667 while ((low ^ (low + range)) < top || ((range < bottom) && ((range = -int (low) & (bottom - 1)), 1)))
00668 {
00669 inputByteStream_arg.read (reinterpret_cast<char*> (&ch), sizeof(char));
00670 streamByteCount += sizeof(char);
00671 code = code << 8 | ch;
00672 range <<= 8;
00673 low <<= 8;
00674 }
00675
00676 }
00677
00678 return (streamByteCount);
00679 }
00680
00681 #endif
00682