Branch data Line data Source code
1 : : /*
2 : : ===============================================================================
3 : :
4 : : FILE: model.hpp
5 : :
6 : : CONTENTS:
7 : :
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 : : #ifndef __model_hpp__
32 : : #define __model_hpp__
33 : :
34 : : #include "common/types.hpp"
35 : : #include "util.hpp"
36 : :
37 : : #include <stdexcept>
38 : :
39 : : namespace laszip {
40 : : namespace models {
41 : : struct arithmetic {
42 : 0 : arithmetic(U32 syms, bool com = false, U32 *initTable = nullptr) :
43 : 0 : symbols(syms), compress(com),
44 : 0 : distribution(nullptr), symbol_count(nullptr), decoder_table(nullptr) {
45 : 0 : if ( (symbols < 2) || (symbols > (1 << 11)) ) {
46 : 0 : throw std::runtime_error("Invalid number of symbols");
47 : : }
48 : :
49 : 0 : last_symbol = symbols - 1;
50 : 0 : if ((!compress) && (symbols > 16)) {
51 : 0 : U32 table_bits = 3;
52 : 0 : while (symbols > (1U << (table_bits + 2))) ++table_bits;
53 : 0 : table_size = 1 << table_bits;
54 : 0 : table_shift = DM__LengthShift - table_bits;
55 : 0 : decoder_table = reinterpret_cast<U32*>(utils::aligned_malloc(sizeof(U32) * (table_size + 2)));
56 : 0 : }
57 : : else { // small alphabet: no table needed
58 : 0 : decoder_table = 0;
59 : 0 : table_size = table_shift = 0;
60 : : }
61 : :
62 : 0 : distribution = reinterpret_cast<U32*>(utils::aligned_malloc(symbols * sizeof(U32)));
63 : 0 : symbol_count = reinterpret_cast<U32*>(utils::aligned_malloc(symbols * sizeof(U32)));
64 : :
65 : 0 : total_count = 0;
66 : 0 : update_cycle = symbols;
67 : :
68 : 0 : if (initTable)
69 : 0 : for (U32 k = 0; k < symbols; k++) symbol_count[k] = initTable[k];
70 : : else
71 : 0 : for (U32 k = 0; k < symbols; k++) symbol_count[k] = 1;
72 : :
73 : 0 : update();
74 : 0 : symbols_until_update = update_cycle = (symbols + 6) >> 1;
75 : 0 : }
76 : :
77 : 0 : ~arithmetic() {
78 : 0 : if (distribution) utils::aligned_free(distribution);
79 : 0 : if (symbol_count) utils::aligned_free(symbol_count);
80 : 0 : if (decoder_table) utils::aligned_free(decoder_table);
81 : 0 : }
82 : :
83 : 0 : arithmetic(const arithmetic& other)
84 : 0 : : symbols(other.symbols), compress(other.compress),
85 : 0 : total_count(other.total_count), update_cycle(other.update_cycle),
86 : 0 : symbols_until_update(other.symbols_until_update), last_symbol(other.last_symbol),
87 : 0 : table_size(other.table_size), table_shift(other.table_shift)
88 : : {
89 : 0 : size_t size(symbols * sizeof(U32));
90 : 0 : distribution = reinterpret_cast<U32*>(utils::aligned_malloc(size));
91 : 0 : std::copy(other.distribution, other.distribution + symbols, distribution);
92 : :
93 : 0 : symbol_count = reinterpret_cast<U32*>(utils::aligned_malloc(size));
94 : 0 : std::copy(other.symbol_count, other.symbol_count + symbols, symbol_count);
95 : :
96 : 0 : if (table_size)
97 : : {
98 : 0 : size = (table_size + 2) * sizeof(U32);
99 : 0 : decoder_table = reinterpret_cast<U32*>(utils::aligned_malloc(size));
100 : 0 : std::copy(other.decoder_table, other.decoder_table + (table_size + 2), decoder_table);
101 : 0 : }
102 : : else
103 : 0 : decoder_table = nullptr;
104 : 0 : }
105 : :
106 : 0 : arithmetic(arithmetic&& other) : symbols(other.symbols), compress(other.compress),
107 : 0 : distribution(other.distribution), symbol_count(other.symbol_count),
108 : 0 : decoder_table(other.decoder_table),
109 : 0 : total_count(other.total_count), update_cycle(other.update_cycle),
110 : 0 : symbols_until_update(other.symbols_until_update), last_symbol(other.last_symbol),
111 : 0 : table_size(other.table_size), table_shift(other.table_shift)
112 : : {
113 : 0 : other.distribution = other.decoder_table = other.symbol_count = NULL;
114 : 0 : other.symbol_count = 0;
115 : 0 : }
116 : :
117 : : arithmetic& operator = (arithmetic&& other) {
118 : : if (this != &other) {
119 : : if (distribution) utils::aligned_free(distribution);
120 : : if (symbol_count) utils::aligned_free(symbol_count);
121 : : if (decoder_table) utils::aligned_free(decoder_table);
122 : :
123 : : symbols = other.symbols;
124 : : compress = other.compress;
125 : :
126 : : distribution = other.distribution;
127 : : symbol_count = other.symbol_count;
128 : : decoder_table = other.decoder_table;
129 : :
130 : : total_count = other.total_count;
131 : : update_cycle = other.update_cycle;
132 : : symbols_until_update = other.symbols_until_update;
133 : : last_symbol = other.last_symbol;
134 : : table_size = other.table_size;
135 : : table_shift = other.table_shift;
136 : :
137 : : other.distribution = other.symbol_count = other.decoder_table = nullptr;
138 : : other.total_count = other.update_cycle = other.symbols_until_update =
139 : : other.last_symbol = other.table_size = other.table_shift = 0;
140 : : }
141 : :
142 : : return *this;
143 : : }
144 : :
145 : 0 : inline void update() {
146 : : // halve counts when a threshold is reached
147 : 0 : if ((total_count += update_cycle) > DM__MaxCount) {
148 : 0 : total_count = 0;
149 : 0 : for (U32 n = 0; n < symbols; n++)
150 : : {
151 : 0 : total_count += (symbol_count[n] = (symbol_count[n] + 1) >> 1);
152 : 0 : }
153 : 0 : }
154 : :
155 : : // compute cumulative distribution, decoder table
156 : 0 : U32 k, sum = 0, s = 0;
157 : 0 : U32 scale = 0x80000000U / total_count;
158 : :
159 : 0 : if (compress || (table_size == 0)) {
160 : 0 : for (k = 0; k < symbols; k++)
161 : : {
162 : 0 : distribution[k] = (scale * sum) >> (31 - DM__LengthShift);
163 : 0 : sum += symbol_count[k];
164 : 0 : }
165 : 0 : }
166 : : else {
167 : 0 : for (k = 0; k < symbols; k++)
168 : : {
169 : 0 : distribution[k] = (scale * sum) >> (31 - DM__LengthShift);
170 : 0 : sum += symbol_count[k];
171 : 0 : U32 w = distribution[k] >> table_shift;
172 : 0 : while (s < w) decoder_table[++s] = k - 1;
173 : 0 : }
174 : 0 : decoder_table[0] = 0;
175 : 0 : while (s <= table_size) decoder_table[++s] = symbols - 1;
176 : : }
177 : :
178 : : // set frequency of model updates
179 : 0 : update_cycle = (5 * update_cycle) >> 2;
180 : 0 : U32 max_cycle = (symbols + 6) << 3;
181 : :
182 : 0 : if (update_cycle > max_cycle) update_cycle = max_cycle;
183 : 0 : symbols_until_update = update_cycle;
184 : 0 : }
185 : :
186 : : U32 symbols;
187 : : bool compress;
188 : :
189 : : U32 * distribution, * symbol_count, * decoder_table;
190 : :
191 : : U32 total_count, update_cycle, symbols_until_update;
192 : : U32 last_symbol, table_size, table_shift;
193 : : };
194 : :
195 : : struct arithmetic_bit {
196 : 0 : arithmetic_bit() {
197 : : // initialization to equiprobable model
198 : 0 : bit_0_count = 1;
199 : 0 : bit_count = 2;
200 : 0 : bit_0_prob = 1U << (BM__LengthShift - 1);
201 : : // start with frequent updates
202 : 0 : update_cycle = bits_until_update = 4;
203 : 0 : }
204 : :
205 : : arithmetic_bit(arithmetic_bit&& other):
206 : : update_cycle(other.update_cycle), bits_until_update(other.bits_until_update),
207 : : bit_0_prob(other.bit_0_prob), bit_0_count(other.bit_0_count), bit_count(other.bit_count) {
208 : : }
209 : :
210 : : arithmetic_bit& operator = (arithmetic_bit&& other) {
211 : : if (this != &other) {
212 : : update_cycle = other.update_cycle;
213 : : bits_until_update = other.bits_until_update;
214 : : bit_0_prob = other.bit_0_prob;
215 : : bit_0_count = other.bit_0_count;
216 : : bit_count = other.bit_count;
217 : :
218 : : other.update_cycle = other.bits_until_update =
219 : : other.bit_0_prob = other.bit_0_count = other.bit_count = 0;
220 : : }
221 : :
222 : : return *this;
223 : : }
224 : :
225 : 0 : void update() {
226 : : // halve counts when a threshold is reached
227 : 0 : if ((bit_count += update_cycle) > BM__MaxCount)
228 : : {
229 : 0 : bit_count = (bit_count + 1) >> 1;
230 : 0 : bit_0_count = (bit_0_count + 1) >> 1;
231 : 0 : if (bit_0_count == bit_count) ++bit_count;
232 : 0 : }
233 : :
234 : : // compute scaled bit 0 probability
235 : 0 : U32 scale = 0x80000000U / bit_count;
236 : 0 : bit_0_prob = (bit_0_count * scale) >> (31 - BM__LengthShift);
237 : :
238 : : // set frequency of model updates
239 : 0 : update_cycle = (5 * update_cycle) >> 2;
240 : 0 : if (update_cycle > 64) update_cycle = 64;
241 : 0 : bits_until_update = update_cycle;
242 : 0 : }
243 : :
244 : : U32 update_cycle, bits_until_update;
245 : : U32 bit_0_prob, bit_0_count, bit_count;
246 : : };
247 : : }
248 : : }
249 : :
250 : : #endif // __model_hpp__
|
