Branch data     Line data    Source code

       1                 :            : /*
       2                 :            : ===============================================================================
       3                 :            : 
       4                 :            :   FILE:  decompressor.hpp
       5                 :            :   
       6                 :            :   CONTENTS:
       7                 :            :     Integer decompressor
       8                 :            : 
       9                 :            :   PROGRAMMERS:
      10                 :            : 
      11                 :            :     martin.isenburg@rapidlasso.com  -  http://rapidlasso.com
      12                 :            :     uday.karan@gmail.com - Hobu, Inc.
      13                 :            :   
      14                 :            :   COPYRIGHT:
      15                 :            :   
      16                 :            :     (c) 2007-2014, martin isenburg, rapidlasso - tools to catch reality
      17                 :            :     (c) 2014, Uday Verma, Hobu, Inc.
      18                 :            : 
      19                 :            :     This is free software; you can redistribute and/or modify it under the
      20                 :            :     terms of the GNU Lesser General Licence as published by the Free Software
      21                 :            :     Foundation. See the COPYING file for more information.
      22                 :            : 
      23                 :            :     This software is distributed WITHOUT ANY WARRANTY and without even the
      24                 :            :     implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
      25                 :            :   
      26                 :            :   CHANGE HISTORY:
      27                 :            :   
      28                 :            : ===============================================================================
      29                 :            : */
      30                 :            : 
      31                 :            : 
      32                 :            : #ifndef __decompressor_hpp__
      33                 :            : #define __decompressor_hpp__
      34                 :            : 
      35                 :            : #include "model.hpp"
      36                 :            : 
      37                 :            : #include <vector>
      38                 :            : #include <memory>
      39                 :            : #include <cassert>
      40                 :            : 
      41                 :            : namespace laszip {
      42                 :            :         namespace decompressors {
      43                 :          0 :                 struct integer {
      44                 :          0 :                         integer(U32 bits = 16, U32 contexts = 1, U32 bits_high = 8, U32 range = 0):
      45                 :          0 :                                 bits(bits), contexts(contexts), bits_high(bits_high), range(range) {
      46                 :          0 :                                 if (range) { // the corrector's significant bits and range
      47                 :          0 :                                         corr_bits = 0;
      48                 :          0 :                                         corr_range = range;
      49                 :          0 :                                         while (range)
      50                 :            :                                         {
      51                 :          0 :                                                 range = range >> 1;
      52                 :          0 :                                                 corr_bits++;
      53                 :            :                                         }
      54                 :          0 :                                         if (corr_range == (1u << (corr_bits-1)))
      55                 :            :                                         {
      56                 :          0 :                                                 corr_bits--;
      57                 :          0 :                                         }
      58                 :            :                                         // the corrector must fall into this interval
      59                 :          0 :                                         corr_min = -((I32)(corr_range/2));
      60                 :          0 :                                         corr_max = corr_min + corr_range - 1;
      61                 :          0 :                                 }
      62                 :          0 :                                 else if (bits && bits < 32) {
      63                 :          0 :                                         corr_bits = bits;
      64                 :          0 :                                         corr_range = 1u << bits;
      65                 :            :                                         // the corrector must fall into this interval
      66                 :          0 :                                         corr_min = -((I32)(corr_range/2));
      67                 :          0 :                                         corr_max = corr_min + corr_range - 1;
      68                 :          0 :                                 }
      69                 :            :                                 else {
      70                 :          0 :                                         corr_bits = 32;
      71                 :          0 :                                         corr_range = 0;
      72                 :            :                                         // the corrector must fall into this interval
      73                 :          0 :                                         corr_min = I32_MIN;
      74                 :          0 :                                         corr_max = I32_MAX;
      75                 :            :                                 }
      76                 :            : 
      77                 :          0 :                                 k = 0;
      78                 :          0 :                         }
      79                 :            : 
      80                 :          0 :                         void init() {
      81                 :            :                                 using laszip::models::arithmetic;
      82                 :            :                                 using laszip::models::arithmetic_bit;
      83                 :            : 
      84                 :            :                                 U32 i;
      85                 :            : 
      86                 :            :                                 // maybe create the models
      87                 :          0 :                                 if (mBits.empty()) {
      88                 :          0 :                                         for (i = 0; i < contexts; i++)
      89                 :          0 :                                                 mBits.push_back(arithmetic(corr_bits+1));
      90                 :            : 
      91                 :            : #ifndef COMPRESS_ONLY_K
      92                 :            :                                         // mcorrector0 is already initialized
      93                 :          0 :                                         for (i = 1; i <= corr_bits; i++) {
      94                 :          0 :                                                 U32 v = i <= bits_high ? 1 << i : 1 << bits_high;
      95                 :          0 :                                                 mCorrector.push_back(arithmetic(v));
      96                 :          0 :                                         }
      97                 :            : #endif
      98                 :          0 :                                 }
      99                 :          0 :                         }
     100                 :            : 
     101                 :            :                         template<
     102                 :            :                                 typename TDecoder
     103                 :            :                         >
     104                 :          0 :                         I32 decompress(TDecoder& dec, I32 pred, U32 context) {
     105                 :          0 :                                 I32 real = pred + readCorrector(dec, mBits[context]);
     106                 :          0 :                                 if (real < 0) real += corr_range;
     107                 :          0 :                                 else if ((U32)(real) >= corr_range) real -= corr_range;
     108                 :            : 
     109                 :          0 :                                 return real;
     110                 :            :                         }
     111                 :            : 
     112                 :          0 :                         inline unsigned int getK() const { return k; }
     113                 :            : 
     114                 :            :                         template<
     115                 :            :                                 typename TDecoder,
     116                 :            :                                 typename TEntroyModel
     117                 :            :                         >
     118                 :          0 :                         I32 readCorrector(TDecoder& dec, TEntroyModel& mBits) {
     119                 :            :                                 I32 c;
     120                 :            : 
     121                 :            :                                 // decode within which interval the corrector is falling
     122                 :            : 
     123                 :          0 :                                 k = dec.decodeSymbol(mBits);
     124                 :            : 
     125                 :            :                                 // decode the exact location of the corrector within the interval
     126                 :            : 
     127                 :            : #ifdef COMPRESS_ONLY_K
     128                 :            :                                 if (k) // then c is either smaller than 0 or bigger than 1
     129                 :            :                                 {
     130                 :            :                                         if (k < 32)
     131                 :            :                                         {
     132                 :            :                                                 c = dec.readBits(k);
     133                 :            : 
     134                 :            :                                                 if (c >= (1<<(k-1))) // if c is in the interval [ 2^(k-1)  ...  + 2^k - 1 ]
     135                 :            :                                                 {
     136                 :            :                                                         // so we translate c back into the interval [ 2^(k-1) + 1  ...  2^k ] by adding 1 
     137                 :            :                                                         c += 1;
     138                 :            :                                                 }
     139                 :            :                                                 else // otherwise c is in the interval [ 0 ...  + 2^(k-1) - 1 ]
     140                 :            :                                                 {
     141                 :            :                                                         // so we translate c back into the interval [ - (2^k - 1)  ...  - (2^(k-1)) ] by subtracting (2^k - 1)
     142                 :            :                                                         c -= ((1<<k) - 1);
     143                 :            :                                                 }
     144                 :            :                                         }
     145                 :            :                                         else
     146                 :            :                                         {
     147                 :            :                                                 c = corr_min;
     148                 :            :                                         }
     149                 :            :                                 }
     150                 :            :                                 else // then c is either 0 or 1
     151                 :            :                                 {
     152                 :            :                                         c = dec.readBit();
     153                 :            :                                 }
     154                 :            : #else // COMPRESS_ONLY_K
     155                 :          0 :                                 if (k) // then c is either smaller than 0 or bigger than 1
     156                 :            :                                 {
     157                 :          0 :                                         if (k < 32)
     158                 :            :                                         {
     159                 :          0 :                                                 if (k <= bits_high) // for small k we can do this in one step
     160                 :            :                                                 {
     161                 :            :                                                         // decompress c with the range coder
     162                 :          0 :                                                         c = dec.decodeSymbol(mCorrector[k-1]);
     163                 :          0 :                                                 }
     164                 :            :                                                 else
     165                 :            :                                                 {
     166                 :            :                                                         // for larger k we need to do this in two steps
     167                 :          0 :                                                         int k1 = k-bits_high;
     168                 :            :                                                         // decompress higher bits with table
     169                 :          0 :                                                         c = dec.decodeSymbol(mCorrector[k-1]);
     170                 :            :                                                         // read lower bits raw
     171                 :          0 :                                                         int c1 = dec.readBits(k1);
     172                 :            :                                                         // put the corrector back together
     173                 :          0 :                                                         c = (c << k1) | c1;
     174                 :            :                                                 }
     175                 :            :                                                 // translate c back into its correct interval
     176                 :          0 :                                                 if (c >= (1<<(k-1))) // if c is in the interval [ 2^(k-1)  ...  + 2^k - 1 ]
     177                 :            :                                                 {
     178                 :            :                                                         // so we translate c back into the interval [ 2^(k-1) + 1  ...  2^k ] by adding 1 
     179                 :          0 :                                                         c += 1;
     180                 :          0 :                                                 }
     181                 :            :                                                 else // otherwise c is in the interval [ 0 ...  + 2^(k-1) - 1 ]
     182                 :            :                                                 {
     183                 :            :                                                         // so we translate c back into the interval [ - (2^k - 1)  ...  - (2^(k-1)) ] by subtracting (2^k - 1)
     184                 :          0 :                                                         c -= ((1<<k) - 1);
     185                 :            :                                                 }
     186                 :          0 :                                         }
     187                 :            :                                         else
     188                 :            :                                         {
     189                 :          0 :                                                 c = corr_min;
     190                 :            :                                         }
     191                 :          0 :                                 }
     192                 :            :                                 else // then c is either 0 or 1
     193                 :            :                                 {
     194                 :          0 :                                         c = dec.decodeBit(mCorrector0);
     195                 :            :                                 }
     196                 :            : #endif // COMPRESS_ONLY_K
     197                 :            : 
     198                 :          0 :                                 return c;
     199                 :            :                         }
     200                 :            : 
     201                 :            :                         U32 k;
     202                 :            : 
     203                 :            :                         U32 bits;
     204                 :            : 
     205                 :            :                         U32 contexts;
     206                 :            :                         U32 bits_high;
     207                 :            :                         U32 range;
     208                 :            : 
     209                 :            :                         U32 corr_bits;
     210                 :            :                         U32 corr_range;
     211                 :            :                         I32 corr_min;
     212                 :            :                         I32 corr_max;
     213                 :            : 
     214                 :            : 
     215                 :            :                         std::vector<laszip::models::arithmetic> mBits;
     216                 :            : 
     217                 :            :                         laszip::models::arithmetic_bit mCorrector0;
     218                 :            :                         std::vector<laszip::models::arithmetic> mCorrector;
     219                 :            :                 };
     220                 :            :         }
     221                 :            : }
     222                 :            : 
     223                 :            : #endif // __decompressor_hpp__