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