1 /******************************************************************************
2 *
3 * Project: integrating laszip into liblas - http://liblas.org -
4 * Purpose:
5 * Author: Martin Isenburg
6 * isenburg at cs.unc.edu
7 *
8 ******************************************************************************
9 * Copyright (c) 2010, Martin Isenburg
10 *
11 * This is free software; you can redistribute and/or modify it under
12 * the terms of the GNU Lesser General Licence as published
13 * by the Free Software Foundation.
14 *
15 * See the COPYING file for more information.
16 *
17 ****************************************************************************/
18
19 /*
20 ===============================================================================
21
22 FILE: rangemodel.cpp
23
24 CONTENTS:
25
26 see header file
27
28 PROGRAMMERS:
29
30 martin isenburg@cs.unc.edu
31
32 COPYRIGHT:
33
34 copyright (C) 2003 martin isenburg (isenburg@cs.unc.edu)
35
36 This software is distributed in the hope that it will be useful,
37 but WITHOUT ANY WARRANTY; without even the implied warranty of
38 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
39
40 CHANGE HISTORY:
41
42 see header file
43
44 ===============================================================================
45 */
46 #include "rangemodel.hpp"
47
48 #include <stdio.h>
49 #include <stdlib.h>
50
51 #include <stdexcept>
52
53 /* initialisation of model */
54 /* n number of symbols in that model */
55 /* compress set to 1 on compression, 0 on decompression */
56 /* targetrescale desired rescaling interval, should be < 1<<(lg_totf+1) */
57 /* lg_totf base2 log of total frequency count */
RangeModel(U32 n,BOOL compress,I32 targetrescale,I32 lg_totf)58 RangeModel::RangeModel(U32 n, BOOL compress, I32 targetrescale, I32 lg_totf)
59 {
60 this->n = n;
61 this->targetrescale = targetrescale;
62 this->lg_totf = lg_totf;
63 cf = new U16[n+1];
64 newf = new U16[n+1];
65 if (lg_totf == 16)
66 {
67 cf[n] = 65535;
68 }
69 else
70 {
71 cf[n] = (1<<lg_totf);
72 }
73 cf[0] = 0;
74 if (compress)
75 {
76 search = NULL;
77 }
78 else
79 {
80 searchshift = lg_totf - TBLSHIFT;
81 search = new U16[(1<<TBLSHIFT)+1];
82 search[1<<TBLSHIFT] = n-1;
83 }
84 }
85
86 /* deletion */
~RangeModel()87 RangeModel::~RangeModel()
88 {
89 delete [] cf;
90 delete [] newf;
91 if (search) delete [] search;
92 }
93
94 /* rescale frequency counts */
dorescale()95 void RangeModel::dorescale()
96 {
97 I32 i, c, missing;
98 if (nextleft) /* we have some more before actual rescaling */
99 {
100 incr++;
101 left = nextleft;
102 nextleft = 0;
103 return;
104 }
105 if (rescale != targetrescale) /* double rescale interval if needed */
106 {
107 rescale <<= 1;
108 if (rescale > targetrescale)
109 {
110 rescale = targetrescale;
111 }
112 }
113 c = missing = cf[n]; /* do actual rescaling */
114 for(i=n-1; i; i--)
115 {
116 I32 tmp = newf[i];
117 c -= tmp;
118 cf[i] = c;
119 tmp = tmp>>1 | 1;
120 missing -= tmp;
121 newf[i] = tmp;
122 }
123 if (c!=newf[0])
124 {
125 // fprintf(stderr,"BUG: rescaling left %d total frequency\n",c);
126 // exit(1);
127 throw std::runtime_error("internal error: RangeModel::dorescale()");
128 }
129 newf[0] = newf[0]>>1 | 1;
130 missing -= newf[0];
131 incr = missing / rescale;
132 nextleft = missing % rescale;
133 left = rescale - nextleft;
134 if (search != NULL)
135 {
136 i=n;
137 while (i)
138 {
139 I32 start, end;
140 end = (cf[i]-1) >> searchshift;
141 i--;
142 start = cf[i] >> searchshift;
143 while (start<=end)
144 {
145 search[start] = i;
146 start++;
147 }
148 }
149 }
150 }
151
152 /* reinitialisation of qsmodel */
153 /* table array of int's to be used for initialisation (NULL ok) */
init(U32 * table)154 void RangeModel::init(U32 *table)
155 {
156 U32 i, end, initval;
157 rescale = n >> 4 | 2;
158 nextleft = 0;
159 if (table)
160 {
161 I32 tmpn = 0;
162 for(i=0; i<n; i++)
163 {
164 if (table[i])
165 {
166 tmpn++;
167 }
168 }
169 initval = cf[n] / tmpn;
170 end = cf[n] % tmpn;
171 for (i=0; i<n; i++)
172 {
173 if (table[i])
174 {
175 if (end)
176 {
177 newf[i] = initval+1;
178 end--;
179 }
180 else
181 {
182 newf[i] = initval;
183 }
184 }
185 else
186 {
187 newf[i] = 0;
188 }
189 }
190 }
191 else
192 {
193 initval = cf[n] / n;
194 end = cf[n] % n;
195 for (i=0; i<end; i++)
196 {
197 newf[i] = initval+1;
198 }
199 for (; i<n; i++)
200 {
201 newf[i] = initval;
202 }
203 }
204 dorescale();
205 }
206
207 /* retrieval of estimated frequencies for a symbol */
208 /* sym symbol for which data is desired; must be <n */
209 /* sy_f frequency of that symbol */
210 /* lt_f frequency of all smaller symbols together */
211 /* the total frequency is 1<<LG_TOTF */
getfreq(U32 sym,U32 * sy_f,U32 * lt_f)212 void RangeModel::getfreq(U32 sym, U32 *sy_f, U32 *lt_f )
213 {
214 *sy_f = cf[sym+1] - (*lt_f = cf[sym]);
215 }
216
217 /* find out symbol for a given cumulative frequency */
218 /* lt_f cumulative frequency */
getsym(U32 lt_f)219 U32 RangeModel::getsym(U32 lt_f)
220 {
221 U32 lo, hi;
222 U16 *tmp;
223 tmp = search+(lt_f>>searchshift);
224 lo = *tmp;
225 hi = *(tmp+1) + 1;
226 while (lo+1 < hi )
227 {
228 I32 mid = (lo+hi)>>1;
229 if (lt_f < cf[mid])
230 {
231 hi = mid;
232 }
233 else
234 {
235 lo = mid;
236 }
237 }
238 return lo;
239 }
240
241 /* update model */
242 /* sym symbol that occurred (must be <n from init) */
update(U32 sym)243 void RangeModel::update(U32 sym)
244 {
245 if (left <= 0)
246 {
247 dorescale();
248 }
249 left--;
250 newf[sym] += incr;
251 }
252