Branch data     Line data    Source code

       1                 :            : /*
       2                 :            : ===============================================================================
       3                 :            : 
       4                 :            :   FILE:  compressor.hpp
       5                 :            :   
       6                 :            :   CONTENTS:
       7                 :            :     Integer compressor
       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 __compressor_hpp__
      33                 :            : #define __compressor_hpp__
      34                 :            : 
      35                 :            : #include "model.hpp"
      36                 :            : 
      37                 :            : #include <vector>
      38                 :            : #include <memory>
      39                 :            : #include <cassert>
      40                 :            : 
      41                 :            : namespace laszip {
      42                 :            :         namespace compressors {
      43                 :            :                 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                 :            :                                         
      47                 :          0 :                                 if (range) { // the corrector's significant bits and range
      48                 :          0 :                                         corr_bits = 0;
      49                 :          0 :                                         corr_range = range;
      50                 :          0 :                                         while (range)
      51                 :            :                                         {
      52                 :          0 :                                                 range = range >> 1;
      53                 :          0 :                                                 corr_bits++;
      54                 :            :                                         }
      55                 :          0 :                                         if (corr_range == (1u << (corr_bits-1))) {
      56                 :          0 :                                                 corr_bits--;
      57                 :          0 :                                         }
      58                 :            : 
      59                 :            :                                         // the corrector must fall into this interval
      60                 :          0 :                                         corr_min = -((I32)(corr_range/2));
      61                 :          0 :                                         corr_max = corr_min + corr_range - 1;
      62                 :          0 :                                 }
      63                 :          0 :                                 else if (bits && bits < 32) {
      64                 :          0 :                                         corr_bits = bits;
      65                 :          0 :                                         corr_range = 1u << bits;
      66                 :            : 
      67                 :            :                                         // the corrector must fall into this interval
      68                 :          0 :                                         corr_min = -((I32)(corr_range/2));
      69                 :          0 :                                         corr_max = corr_min + corr_range - 1;
      70                 :          0 :                                 }
      71                 :            :                                 else {
      72                 :          0 :                                         corr_bits = 32;
      73                 :          0 :                                         corr_range = 0;
      74                 :            :                                         // the corrector must fall into this interval
      75                 :          0 :                                         corr_min = I32_MIN;
      76                 :          0 :                                         corr_max = I32_MAX;
      77                 :            :                                 }
      78                 :            : 
      79                 :          0 :                                 k = 0;
      80                 :          0 :                         }
      81                 :            : 
      82                 :          0 :                         ~integer() {
      83                 :          0 :                                 mBits.clear();
      84                 :          0 :                                 mCorrector.clear();
      85                 :          0 :                         }
      86                 :            : 
      87                 :            :                         void init() {
      88                 :            :                                 using laszip::models::arithmetic;
      89                 :            :                                 using laszip::models::arithmetic_bit;
      90                 :            : 
      91                 :            :                                 U32 i;
      92                 :            : 
      93                 :            :                                 // maybe create the models
      94                 :            :                                 if (mBits.empty()) {
      95                 :            :                                         for (i = 0; i < contexts; i++)
      96                 :            :                                                 mBits.push_back(arithmetic(corr_bits+1));
      97                 :            : 
      98                 :            : #ifndef COMPRESS_ONLY_K
      99                 :            :                                         // mcorrector0 is already in init state
     100                 :            :                                         for (i = 1; i <= corr_bits; i++) {
     101                 :            :                                                 U32 v = i <= bits_high ? 1 << i : 1 << bits_high;
     102                 :            :                                                 mCorrector.push_back(arithmetic(v));
     103                 :            :                                         }
     104                 :            : #endif
     105                 :            :                                 }
     106                 :            :                         }
     107                 :            : 
     108                 :            :                         unsigned int getK() const { return k; }
     109                 :            : 
     110                 :            :                         template<
     111                 :            :                                 typename TEncoder
     112                 :            :                         >
     113                 :            :                         void compress(TEncoder& enc, I32 pred, I32 real, U32 context) {
     114                 :            :                                 // the corrector will be within the interval [ - (corr_range - 1)  ...  + (corr_range - 1) ]
     115                 :            :                                 I32 corr = real - pred;
     116                 :            :                                 // we fold the corrector into the interval [ corr_min  ...  corr_max ]
     117                 :            :                                 if (corr < corr_min) corr += corr_range;
     118                 :            :                                 else if (corr > corr_max) corr -= corr_range;
     119                 :            : 
     120                 :            :                                 writeCorrector(enc, corr, mBits[context]);
     121                 :            :                         }
     122                 :            : 
     123                 :            :                         template<
     124                 :            :                                 typename TEncoder,
     125                 :            :                                 typename TEntropyModel
     126                 :            :                         >
     127                 :            :                         void writeCorrector(TEncoder& enc, int c, TEntropyModel& mBits) {
     128                 :            :                                 U32 c1;
     129                 :            : 
     130                 :            :                                 // find the tighest interval [ - (2^k - 1)  ...  + (2^k) ] that contains c
     131                 :            : 
     132                 :            :                                 k = 0;
     133                 :            : 
     134                 :            :                                 // do this by checking the absolute value of c (adjusted for the case that c is 2^k)
     135                 :            : 
     136                 :            :                                 c1 = (c <= 0 ? -c : c-1);
     137                 :            : 
     138                 :            :                                 // this loop could be replaced with more efficient code
     139                 :            : 
     140                 :            :                                 while (c1)
     141                 :            :                                 {
     142                 :            :                                         c1 = c1 >> 1;
     143                 :            :                                         k = k + 1;
     144                 :            :                                 }
     145                 :            : 
     146                 :            :                                 // the number k is between 0 and corr_bits and describes the interval the corrector falls into
     147                 :            :                                 // we can compress the exact location of c within this interval using k bits
     148                 :            : 
     149                 :            :                                 enc.encodeSymbol(mBits, k);
     150                 :            : 
     151                 :            : #ifdef COMPRESS_ONLY_K
     152                 :            :                                 if (k) // then c is either smaller than 0 or bigger than 1
     153                 :            :                                 {
     154                 :            :                                         assert((c != 0) && (c != 1));
     155                 :            :                                         if (k < 32)
     156                 :            :                                         {
     157                 :            :                                                 // translate the corrector c into the k-bit interval [ 0 ... 2^k - 1 ]
     158                 :            :                                                 if (c < 0) // then c is in the interval [ - (2^k - 1)  ...  - (2^(k-1)) ]
     159                 :            :                                                 {
     160                 :            :                                                         // so we translate c into the interval [ 0 ...  + 2^(k-1) - 1 ] by adding (2^k - 1)
     161                 :            :                                                         enc.writeBits(k, c + ((1<<k) - 1));
     162                 :            :                                                 }
     163                 :            :                                                 else // then c is in the interval [ 2^(k-1) + 1  ...  2^k ]
     164                 :            :                                                 {
     165                 :            :                                                         // so we translate c into the interval [ 2^(k-1) ...  + 2^k - 1 ] by subtracting 1
     166                 :            :                                                         enc.writeBits(k, c - 1);
     167                 :            :                                                 }
     168                 :            :                                         }
     169                 :            :                                 }
     170                 :            :                                 else // then c is 0 or 1
     171                 :            :                                 {
     172                 :            :                                         assert((c == 0) || (c == 1));
     173                 :            :                                         enc.writeBit(c);
     174                 :            :                                 }
     175                 :            : #else // COMPRESS_ONLY_K
     176                 :            :                                 if (k) // then c is either smaller than 0 or bigger than 1
     177                 :            :                                 {
     178                 :            :                                         assert((c != 0) && (c != 1));
     179                 :            :                                         if (k < 32)
     180                 :            :                                         {
     181                 :            :                                                 // translate the corrector c into the k-bit interval [ 0 ... 2^k - 1 ]
     182                 :            :                                                 if (c < 0) // then c is in the interval [ - (2^k - 1)  ...  - (2^(k-1)) ]
     183                 :            :                                                 {
     184                 :            :                                                         // so we translate c into the interval [ 0 ...  + 2^(k-1) - 1 ] by adding (2^k - 1)
     185                 :            :                                                         c += ((1<<k) - 1);
     186                 :            :                                                 }
     187                 :            :                                                 else // then c is in the interval [ 2^(k-1) + 1  ...  2^k ]
     188                 :            :                                                 {
     189                 :            :                                                         // so we translate c into the interval [ 2^(k-1) ...  + 2^k - 1 ] by subtracting 1
     190                 :            :                                                         c -= 1;
     191                 :            :                                                 }
     192                 :            :                                                 if (k <= bits_high) // for small k we code the interval in one step
     193                 :            :                                                 {
     194                 :            :                                                         // compress c with the range coder
     195                 :            :                                                         enc.encodeSymbol(mCorrector[k-1], c);
     196                 :            :                                                 }
     197                 :            :                                                 else // for larger k we need to code the interval in two steps
     198                 :            :                                                 {
     199                 :            :                                                         // figure out how many lower bits there are 
     200                 :            :                                                         int k1 = k-bits_high;
     201                 :            :                                                         // c1 represents the lowest k-bits_high+1 bits
     202                 :            :                                                         c1 = c & ((1<<k1) - 1);
     203                 :            :                                                         // c represents the highest bits_high bits
     204                 :            :                                                         c = c >> k1;
     205                 :            :                                                         // compress the higher bits using a context table
     206                 :            :                                                         enc.encodeSymbol(mCorrector[k-1], c);
     207                 :            :                                                         // store the lower k1 bits raw
     208                 :            :                                                         enc.writeBits(k1, c1);
     209                 :            :                                                 }
     210                 :            :                                         }
     211                 :            :                                 }
     212                 :            :                                 else // then c is 0 or 1
     213                 :            :                                 {
     214                 :            :                                         assert((c == 0) || (c == 1));
     215                 :            :                                         enc.encodeBit(mCorrector0,c);
     216                 :            :                                 }
     217                 :            : #endif // COMPRESS_ONLY_K
     218                 :            :                         }
     219                 :            : 
     220                 :            :                         U32 k;
     221                 :            : 
     222                 :            :                         U32 bits;
     223                 :            : 
     224                 :            :                         U32 contexts;
     225                 :            :                         U32 bits_high;
     226                 :            :                         U32 range;
     227                 :            : 
     228                 :            :                         U32 corr_bits;
     229                 :            :                         U32 corr_range;
     230                 :            :                         I32 corr_min;
     231                 :            :                         I32 corr_max;
     232                 :            : 
     233                 :            : 
     234                 :            :                         std::vector<laszip::models::arithmetic> mBits;
     235                 :            : 
     236                 :            :                         laszip::models::arithmetic_bit mCorrector0;
     237                 :            :                         std::vector<laszip::models::arithmetic> mCorrector;
     238                 :            :                 };
     239                 :            :         }
     240                 :            : }
     241                 :            : 
     242                 :            : #endif // __compressor_hpp__