source: main/trunk/greenstone2/common-src/indexers/mgpp/lib/bitio_m_abstract.h@ 32210

Last change on this file since 32210 was 25147, checked in by kjdon, 12 years ago

merged 64_bit_Greenstone branch into trunk, rev 25139

  • Property svn:executable set to *
  • Property svn:keywords set to Author Date Id Revision
File size: 8.6 KB
RevLine 
[3365]1#ifndef H_BITIO_ABSTRACT
2#define H_BITIO_ABSTRACT
[25147]3#include "mglong.h"
[18716]4#include <cstdlib>
[3365]5class bitio_buffer {
6public:
7 virtual int bit() = 0;
8 virtual void encodeBit(int bit) = 0;
[25147]9 virtual void seek(mg_u_long topos) = 0;
10
11 virtual ~bitio_buffer() {}
12
13 static inline void check_positive(char *type, mg_u_long x) {
[3365]14 if (x <= 0) {
[25147]15 fprintf(stderr, "Error: Cannot %s encode %u\n", type, x);
[3365]16 exit(1);
17 }
18 }
19
[25147]20 static inline int floor_log2(mg_u_long x) {
21 mg_u_long _B_x = x;
[3365]22 int reply;
23
24 reply = -1;
25 while (_B_x != 0) {
26 _B_x >>= 1;
[9612]27 ++reply;
[3365]28 }
29 return reply;
30 }
31
[25147]32 static inline int ceil_log2(mg_u_long x) {
[3365]33 register int _B_x;
[25147]34 mg_u_long reply;
[3365]35
36 _B_x = x - 1;
37 reply = 0;
38 while (_B_x != 0) {
39 _B_x >>= 1;
[9612]40 ++reply;
[3365]41 }
42 return reply;
43 }
44
[25147]45 inline mg_u_long unary_decode(mg_u_long *count) {
46 mg_u_long x;
[3365]47
48 x = 1;
[9612]49 while (!this->bit()) ++x;
[3365]50 if (count != NULL) {
51 *count += x;
52 }
53 return x;
54 }
55
[25147]56 inline void unary_encode(mg_u_long x, mg_u_long *count) {
57 register mg_u_long _B_x = x;
58 check_positive((char*)"unary", _B_x);
[3365]59 if (count != NULL) {
60 *count += _B_x;
61 }
62 while(--_B_x)
63 encodeBit(0);
64 encodeBit(1);
65 }
66
67
[25147]68 inline mg_u_long binary_decode(mg_u_long b, mg_u_long *count) {
69 register mg_u_long _B_x = 0;
70 register mg_u_long _B_b = b;
[3365]71 register int _B_i, _B_logofb, _B_thresh;
[25147]72 register mg_u_long reply;
[3365]73
74 if (_B_b != 1) {
75 _B_logofb = ceil_log2(_B_b);
76 _B_thresh = (1<<_B_logofb) - _B_b;
[9612]77 --_B_logofb;
[3365]78
79 if (count != NULL) {
80 *count += _B_logofb;
81 }
82
[9612]83 for (_B_i=0; _B_i < _B_logofb; ++_B_i) {
[3365]84 _B_x += _B_x + this->bit();
85 }
86
87 if ((int)_B_x >= _B_thresh) {
88 _B_x += _B_x + this->bit();
89 _B_x -= _B_thresh;
90 if (count != NULL) {
91 *count = *count + 1;
92 }
93 }
94 reply = _B_x+1;
95
96 } else reply = 1;
97
98 return reply;
99 }
100
[25147]101 inline void binary_encode(mg_u_long x, mg_u_long b, mg_u_long *count) {
102 register mg_u_long _B_x = (x);
103 register mg_u_long _B_b = (b);
[3365]104 register int _B_nbits, _B_logofb, _B_thresh;
105
[25147]106 check_positive((char*)"binary", _B_x);
[3365]107 _B_logofb = ceil_log2(_B_b);
108
109 _B_thresh = (1<<_B_logofb) - _B_b;
110 if ((int)(--_B_x) < _B_thresh) _B_nbits = _B_logofb-1;
111 else {
112 _B_nbits = _B_logofb;
113 _B_x += _B_thresh;
114 }
115 if (count != NULL) {
116 *count += _B_nbits;
117 }
118 while (--_B_nbits>=0)
119 encodeBit((_B_x>>_B_nbits) & 0x1);
120 }
121
[25147]122 inline mg_u_long bblock_decode(mg_u_long b, mg_u_long *count) {
123 register mg_u_long _B_x1, _B_xx = 0;
124 register mg_u_long _B_bb = (b);
[3365]125 register int _B_xdivb;
126
127 _B_xdivb = this->unary_decode(count);
[9612]128 --_B_xdivb;
[3365]129 while (_B_xdivb--) {
130 _B_xx += _B_bb;
131 }
132 _B_x1 = this->binary_decode(_B_bb, count);
133 return (_B_xx + _B_x1);
134 }
135
[25147]136 inline void bblock_encode(mg_u_long x, mg_u_long b, mg_u_long *count) {
137 register mg_u_long _B_xx = (x);
138 register mg_u_long _B_bb = (b);
[3365]139 register int _B_xdivb = 0;
[25147]140 check_positive((char*)"bblock", _B_xx);
[9612]141 --_B_xx;
[3365]142 while (_B_xx >= _B_bb) {
[9612]143 ++_B_xdivb;
[3365]144 _B_xx -= _B_bb;
145 }
146 unary_encode(_B_xdivb+1, count);
147 binary_encode(_B_xx+1, _B_bb, count);
148 }
149
[25147]150 inline mg_u_long elias_decode(mg_u_long b, double s, mg_u_long *count) {
151 register mg_u_long _B_xx;
152 register mg_u_long _B_b = b;
[3365]153 register double _B_s = s;
154 register int _B_lower=1, _B_upper=1;
155 register int _B_k;
156 register double _B_pow=1.0;
157
158 _B_k = this->unary_decode(count);
[9612]159 --_B_k;
[3365]160 while (_B_k--) {
161 _B_lower = _B_upper+1;
162 _B_pow *= _B_s;
163 _B_upper += (int) (_B_b*_B_pow);
164 }
165 _B_xx = this->binary_decode(_B_upper-_B_lower+1, count);
[9612]166 --_B_xx;
[25147]167 check_positive((char*)"gamma", _B_xx+_B_lower);
[3365]168 return _B_xx+_B_lower;
169 }
170
[25147]171 inline void elias_encode(mg_u_long x, mg_u_long b, double s, mg_u_long *count) {
172 register mg_u_long _B_xx = x;
173 register mg_u_long _B_b = b;
[3365]174 register double _B_s = s;
175 register int _B_lower=1, _B_upper=1;
176 register int _B_k=0;
177 register double _B_pow=1.0;
178
[25147]179 check_positive((char*)"elias", _B_xx);
[3365]180
181 while ((int)_B_xx>_B_upper) {
[9612]182 ++_B_k;
[3365]183 _B_lower = _B_upper+1;
184 _B_pow *= _B_s;
185 _B_upper += (int) (_B_b*_B_pow);
186 }
187 unary_encode(_B_k+1, count);
188 binary_encode(_B_xx-_B_lower+1, _B_upper-_B_lower+1, count);
189 }
190
[25147]191 inline mg_u_long gamma_decode(mg_u_long *count) {
192 register mg_u_long _B_xx = 1;
[3365]193 register int _B_nbits = 0;
194
[9612]195 while(!this->bit()) ++_B_nbits;
[3365]196 if (count != NULL) {
197 *count += _B_nbits*2+1;
198 }
199 while (_B_nbits-- > 0)
200 _B_xx += _B_xx + this->bit();
201 return _B_xx;
202 }
203
[25147]204 inline void gamma_encode(mg_u_long x, mg_u_long *count) {
205 register mg_u_long _B_xx = x;
[3365]206 register int _B_logofb;
207 register int _B_nbits;
208
[25147]209 check_positive((char*)"gamma", _B_xx);
[3365]210 _B_logofb = floor_log2(_B_xx);
211 _B_nbits = _B_logofb+1;
212
213 if (count != NULL) {
214 *count += _B_logofb*2+1;
215 }
216 while(_B_logofb--) encodeBit(0);
217 while (--_B_nbits>=0) encodeBit((_B_xx>>_B_nbits) & 0x1);
218 }
219
[25147]220 inline mg_u_long delta_decode(mg_u_long *count) {
221 register mg_u_long _B_xxx;
[3365]222 register int _B_logx;
223 _B_logx = gamma_decode(count);
[9612]224 --_B_logx;
[3365]225 _B_xxx = binary_decode(1<<_B_logx, count);
[9612]226 --_B_xxx;
[3365]227 return (_B_xxx + (1<<_B_logx));
228 }
229
[25147]230 inline void delta_encode(mg_u_long x, mg_u_long *count) {
231 register mg_u_long _B_xxx = x;
[3365]232 register int _B_logx;
233 _B_logx = floor_log2(_B_xxx);
234 gamma_encode(_B_logx+1, count);
235 binary_encode(_B_xxx+1, 1<<_B_logx, count);
236 }
237
[25147]238 inline mg_u_long huff_decode(mg_u_long *mcodes, mg_u_long **values,
239 mg_u_long *count = NULL) {
240 register mg_u_long *__min_code = mcodes;
241 register mg_u_long *__mclen = mcodes;
242 register mg_u_long **__values = values;
243 register mg_u_long __code = 0;
[3365]244 do {
245 __code += __code + bit();
[9612]246 if (count != NULL) ++(*count);
[3365]247 } while (__code < *++__mclen);
248
249 return __values[__mclen - __min_code][__code - *__mclen];
250 }
251
[25147]252 inline void huff_encode(mg_u_long x, mg_u_long *codes, char *lens,
253 mg_u_long *count = NULL) {
[3365]254 register int __i;
255 register int __clen = lens[x];
[25147]256 register mg_u_long __code = codes[x];
[9612]257 for (__i=__clen-1; __i>=0; --__i) {
[3365]258 encodeBit((__code >> __i) & 1);
259 }
260 if (count != NULL) {
261 *count += lens[x];
262 }
263 }
264
[25147]265 static inline mg_u_long unary_length(mg_u_long x) {
266 check_positive((char*)"unary", x);
[3365]267 return x;
268 }
269
[25147]270 static inline int binary_length(mg_u_long x, mg_u_long b) {
271 register mg_u_long _B_x = (x);
272 register mg_u_long _B_b = (b);
[3365]273 register int _B_nbits, _B_logofb, _B_thresh;
274
[25147]275 check_positive((char*)"binary", _B_x);
[3365]276 _B_logofb = ceil_log2(_B_b);
277 _B_thresh = (1<<_B_logofb) - _B_b;
278 if ((int)(--_B_x) < _B_thresh) _B_nbits = _B_logofb-1;
279 else _B_nbits = _B_logofb;
280 return _B_nbits;
281 }
282
[25147]283 static inline mg_u_long bblock_length(mg_u_long x, mg_u_long b) {
284 register mg_u_long _B_bcount, count, _B_xx = (x);
285 register mg_u_long _B_bb = (b);
[3365]286 register int _B_xdivb = 0;
287
[25147]288 check_positive((char*)"bblock", _B_xx);
[9612]289 --_B_xx;
[3365]290 while (_B_xx >= _B_bb) {
[9612]291 ++_B_xdivb;
[3365]292 _B_xx -= _B_bb;
293 }
294 count = unary_length(_B_xdivb+1);
295 _B_bcount = binary_length(_B_xx+1, _B_bb);
296 count += _B_bcount;
297 return count;
298 }
299
[25147]300 static inline mg_u_long elias_length(mg_u_long x, mg_u_long b,
[3365]301 double s) {
[25147]302 register mg_u_long _B_xx = x;
303 register mg_u_long _B_b = b;
[3365]304 register double _B_s = s;
305 register int _B_lower=1, _B_upper=1;
306 register int _B_k=0, _B_ecount;
307 register double _B_pow=1.0;
[25147]308 register mg_u_long count;
309 check_positive((char*)"gamma", _B_xx);
[3365]310
311 while ((int)(_B_xx)>_B_upper) {
[9612]312 ++_B_k;
[3365]313 _B_lower = _B_upper+1;
314 _B_pow *= _B_s;
315 _B_upper += (int) (_B_b*_B_pow);
316 }
317 count = unary_length(_B_k+1);
318 _B_ecount = binary_length(_B_xx-_B_lower+1, _B_upper-_B_lower+1);
319 count += _B_ecount;
320 return count;
321 }
322
[25147]323 static inline mg_u_long gamma_length(mg_u_long x) {
324 register mg_u_long _B_xx = x;
[3365]325 register int _B_logofb;
[25147]326 check_positive((char*)"gamma", _B_xx);
[3365]327 _B_logofb = floor_log2(_B_xx);
328 return _B_logofb*2+1;
329 }
330
[25147]331 static inline mg_u_long delta_length(mg_u_long x) {
332 register mg_u_long _B_xxx = x;
[3365]333 register int _B_logx, _B_dcount;
[25147]334 register mg_u_long count;
[3365]335 _B_logx = floor_log2 (_B_xxx);
336 count = gamma_length(_B_logx+1);
337 _B_dcount = binary_length (_B_xxx+1, 1<<_B_logx);
338 count += _B_dcount;
339 return count;
340 }
341};
342
343#endif
Note: See TracBrowser for help on using the repository browser.