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 { integerlaszip::compressors::integer44 integer(U32 bits = 16, U32 contexts = 1, U32 bits_high = 8, U32 range = 0): 45 bits(bits), contexts(contexts), bits_high(bits_high), range(range) { 46 47 if (range) { // the corrector's significant bits and range 48 corr_bits = 0; 49 corr_range = range; 50 while (range) 51 { 52 range = range >> 1; 53 corr_bits++; 54 } 55 if (corr_range == (1u << (corr_bits-1))) { 56 corr_bits--; 57 } 58 59 // the corrector must fall into this interval 60 corr_min = -((I32)(corr_range/2)); 61 corr_max = corr_min + corr_range - 1; 62 } 63 else if (bits && bits < 32) { 64 corr_bits = bits; 65 corr_range = 1u << bits; 66 67 // the corrector must fall into this interval 68 corr_min = -((I32)(corr_range/2)); 69 corr_max = corr_min + corr_range - 1; 70 } 71 else { 72 corr_bits = 32; 73 corr_range = 0; 74 // the corrector must fall into this interval 75 corr_min = I32_MIN; 76 corr_max = I32_MAX; 77 } 78 79 k = 0; 80 } 81 ~integerlaszip::compressors::integer82 ~integer() { 83 mBits.clear(); 84 mCorrector.clear(); 85 } 86 initlaszip::compressors::integer87 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 getKlaszip::compressors::integer108 unsigned int getK() const { return k; } 109 110 template< 111 typename TEncoder 112 > compresslaszip::compressors::integer113 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 > writeCorrectorlaszip::compressors::integer127 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__ 243