Branch data Line data Source code
1 : : /*
2 : : ===============================================================================
3 : :
4 : : FILE: decoder.hpp
5 : :
6 : : CONTENTS:
7 : : Decoder stuff
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 : : // -
33 : : // **************************** -
34 : : // ARITHMETIC CODING EXAMPLES -
35 : : // **************************** -
36 : : // -
37 : : // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
38 : : // -
39 : : // Fast arithmetic coding implementation -
40 : : // -> 32-bit variables, 32-bit product, periodic updates, table decoding -
41 : : // -
42 : : // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
43 : : // -
44 : : // Version 1.00 - April 25, 2004 -
45 : : // -
46 : : // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
47 : : // -
48 : : // WARNING -
49 : : // ========= -
50 : : // -
51 : : // The only purpose of this program is to demonstrate the basic principles -
52 : : // of arithmetic coding. The original version of this code can be found in -
53 : : // Digital Signal Compression: Principles and Practice -
54 : : // (Cambridge University Press, 2011, ISBN: 9780511984655) -
55 : : // -
56 : : // Copyright (c) 2019 by Amir Said (said@ieee.org) & -
57 : : // William A. Pearlman (pearlw@ecse.rpi.edu) -
58 : : // -
59 : : // Redistribution and use in source and binary forms, with or without -
60 : : // modification, are permitted provided that the following conditions are -
61 : : // met: -
62 : : // -
63 : : // 1. Redistributions of source code must retain the above copyright notice, -
64 : : // this list of conditions and the following disclaimer. -
65 : : // -
66 : : // 2. Redistributions in binary form must reproduce the above copyright -
67 : : // notice, this list of conditions and the following disclaimer in the -
68 : : // documentation and/or other materials provided with the distribution. -
69 : : // -
70 : : // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS -
71 : : // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED -
72 : : // TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A -
73 : : // PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER -
74 : : // OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, -
75 : : // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, -
76 : : // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR -
77 : : // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF -
78 : : // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING -
79 : : // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS -
80 : : // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -
81 : : // -
82 : : // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
83 : : // -
84 : : // A description of the arithmetic coding method used here is available in -
85 : : // -
86 : : // Lossless Compression Handbook, ed. K. Sayood -
87 : : // Chapter 5: Arithmetic Coding (A. Said), pp. 101-152, Academic Press, 2003 -
88 : : // -
89 : : // A. Said, Introduction to Arithetic Coding Theory and Practice -
90 : : // HP Labs report HPL-2004-76 - http://www.hpl.hp.com/techreports/ -
91 : : // -
92 : : // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
93 : :
94 : :
95 : : #ifndef __decoder_hpp__
96 : : #define __decoder_hpp__
97 : :
98 : : #include <cassert>
99 : :
100 : : #include "common/types.hpp"
101 : :
102 : : namespace laszip {
103 : : namespace decoders {
104 : : template<
105 : : typename TInputStream
106 : : >
107 : : struct arithmetic {
108 : 0 : arithmetic(TInputStream& in) :
109 : 0 : instream(in), value(0) {
110 : 0 : length = AC__MaxLength;
111 : 0 : }
112 : :
113 : 0 : ~arithmetic() {
114 : 0 : }
115 : :
116 : 0 : void readInitBytes() {
117 : 0 : value =
118 : 0 : (instream.getByte() << 24) |
119 : 0 : (instream.getByte() << 16) |
120 : 0 : (instream.getByte() << 8) |
121 : 0 : instream.getByte();
122 : 0 : }
123 : :
124 : : template<typename TEntropyModel>
125 : 0 : U32 decodeBit(TEntropyModel& m) {
126 : 0 : U32 x = m.bit_0_prob * (length >> BM__LengthShift); // product l x p0
127 : 0 : U32 sym = (value >= x); // decision
128 : : // update & shift interval
129 : 0 : if (sym == 0) {
130 : 0 : length = x;
131 : 0 : ++m.bit_0_count;
132 : 0 : }
133 : : else {
134 : 0 : value -= x; // shifted interval base = 0
135 : 0 : length -= x;
136 : : }
137 : :
138 : 0 : if (length < AC__MinLength) renorm_dec_interval(); // renormalization
139 : 0 : if (--m.bits_until_update == 0) m.update(); // periodic model update
140 : :
141 : 0 : return sym; // return data bit value
142 : : }
143 : :
144 : : template<typename TEntropyModel>
145 : 0 : U32 decodeSymbol(TEntropyModel& m) {
146 : 0 : U32 n, sym, x, y = length;
147 : :
148 : 0 : if (m.decoder_table) { // use table look-up for faster decoding
149 : 0 : unsigned dv = value / (length >>= DM__LengthShift);
150 : 0 : unsigned t = dv >> m.table_shift;
151 : :
152 : 0 : sym = m.decoder_table[t]; // initial decision based on table look-up
153 : 0 : n = m.decoder_table[t+1] + 1;
154 : :
155 : 0 : while (n > sym + 1) { // finish with bisection search
156 : 0 : U32 k = (sym + n) >> 1;
157 : 0 : if (m.distribution[k] > dv) n = k; else sym = k;
158 : : }
159 : :
160 : : // compute products
161 : 0 : x = m.distribution[sym] * length;
162 : 0 : if (sym != m.last_symbol) y = m.distribution[sym+1] * length;
163 : 0 : }
164 : : else { // decode using only multiplications
165 : 0 : x = sym = 0;
166 : 0 : length >>= DM__LengthShift;
167 : 0 : U32 k = (n = m.symbols) >> 1;
168 : : // decode via bisection search
169 : 0 : do {
170 : 0 : U32 z = length * m.distribution[k];
171 : 0 : if (z > value) {
172 : 0 : n = k;
173 : 0 : y = z; // value is smaller
174 : 0 : }
175 : : else {
176 : 0 : sym = k;
177 : 0 : x = z; // value is larger or equal
178 : : }
179 : 0 : } while ((k = (sym + n) >> 1) != sym);
180 : : }
181 : :
182 : 0 : value -= x; // update interval
183 : 0 : length = y - x;
184 : :
185 : 0 : if (length < AC__MinLength) renorm_dec_interval(); // renormalization
186 : :
187 : 0 : ++m.symbol_count[sym];
188 : 0 : if (--m.symbols_until_update == 0) m.update(); // periodic model update
189 : :
190 : 0 : return sym;
191 : : }
192 : :
193 : : U32 readBit() {
194 : : U32 sym = value / (length >>= 1); // decode symbol, change length
195 : : value -= length * sym; // update interval
196 : :
197 : : if (length < AC__MinLength) renorm_dec_interval(); // renormalization
198 : :
199 : : return sym;
200 : : }
201 : :
202 : 0 : U32 readBits(U32 bits) {
203 : 0 : assert(bits && (bits <= 32));
204 : :
205 : 0 : if (bits > 19) {
206 : 0 : U32 tmp = readShort();
207 : 0 : bits = bits - 16;
208 : 0 : U32 tmp1 = readBits(bits) << 16;
209 : 0 : return (tmp1|tmp);
210 : : }
211 : :
212 : 0 : U32 sym = value / (length >>= bits);// decode symbol, change length
213 : 0 : value -= length * sym; // update interval
214 : :
215 : 0 : if (length < AC__MinLength) renorm_dec_interval(); // renormalization
216 : 0 : return sym;
217 : 0 : }
218 : :
219 : : U8 readByte() {
220 : : U32 sym = value / (length >>= 8); // decode symbol, change length
221 : : value -= length * sym; // update interval
222 : :
223 : : if (length < AC__MinLength) renorm_dec_interval(); // renormalization
224 : :
225 : : assert(sym < (1<<8));
226 : :
227 : : return (U8)sym;
228 : : }
229 : :
230 : 0 : U16 readShort() {
231 : 0 : U32 sym = value / (length >>= 16); // decode symbol, change length
232 : 0 : value -= length * sym; // update interval
233 : :
234 : 0 : if (length < AC__MinLength) renorm_dec_interval(); // renormalization
235 : :
236 : 0 : assert(sym < (1<<16));
237 : :
238 : 0 : return (U16)sym;
239 : : }
240 : :
241 : 0 : U32 readInt() {
242 : 0 : U32 lowerInt = readShort();
243 : 0 : U32 upperInt = readShort();
244 : 0 : return (upperInt<<16)|lowerInt;
245 : : }
246 : :
247 : : F32 readFloat() { /* danger in float reinterpretation */
248 : : U32I32F32 u32i32f32;
249 : : u32i32f32.u32 = readInt();
250 : : return u32i32f32.f32;
251 : : }
252 : :
253 : : U64 readInt64() {
254 : : U64 lowerInt = readInt();
255 : : U64 upperInt = readInt();
256 : : return (upperInt<<32)|lowerInt;
257 : : }
258 : :
259 : : F64 readDouble() { /* danger in float reinterpretation */
260 : : U64I64F64 u64i64f64;
261 : : u64i64f64.u64 = readInt64();
262 : : return u64i64f64.f64;
263 : : }
264 : :
265 : 0 : TInputStream& getInStream() {
266 : 0 : return instream;
267 : : }
268 : :
269 : :
270 : : arithmetic<TInputStream>(const arithmetic<TInputStream>&) = delete;
271 : : arithmetic<TInputStream>& operator = (const arithmetic<TInputStream>&) = delete;
272 : :
273 : : private:
274 : 0 : void renorm_dec_interval() {
275 : 0 : do { // read least-significant byte
276 : 0 : value = (value << 8) | instream.getByte();
277 : 0 : } while ((length <<= 8) < AC__MinLength); // length multiplied by 256
278 : 0 : }
279 : :
280 : : TInputStream& instream;
281 : : U32 value, length;
282 : : };
283 : : }
284 : : }
285 : :
286 : : #endif // __decoder_hpp__
|
