1 | #ifndef H_BITIO_ABSTRACT
|
---|
2 | #define H_BITIO_ABSTRACT
|
---|
3 | #include "mglong.h"
|
---|
4 | #include <cstdlib>
|
---|
5 | class bitio_buffer {
|
---|
6 | public:
|
---|
7 | virtual int bit() = 0;
|
---|
8 | virtual void encodeBit(int bit) = 0;
|
---|
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) {
|
---|
14 | if (x <= 0) {
|
---|
15 | fprintf(stderr, "Error: Cannot %s encode %u\n", type, x);
|
---|
16 | exit(1);
|
---|
17 | }
|
---|
18 | }
|
---|
19 |
|
---|
20 | static inline int floor_log2(mg_u_long x) {
|
---|
21 | mg_u_long _B_x = x;
|
---|
22 | int reply;
|
---|
23 |
|
---|
24 | reply = -1;
|
---|
25 | while (_B_x != 0) {
|
---|
26 | _B_x >>= 1;
|
---|
27 | ++reply;
|
---|
28 | }
|
---|
29 | return reply;
|
---|
30 | }
|
---|
31 |
|
---|
32 | static inline int ceil_log2(mg_u_long x) {
|
---|
33 | register int _B_x;
|
---|
34 | mg_u_long reply;
|
---|
35 |
|
---|
36 | _B_x = x - 1;
|
---|
37 | reply = 0;
|
---|
38 | while (_B_x != 0) {
|
---|
39 | _B_x >>= 1;
|
---|
40 | ++reply;
|
---|
41 | }
|
---|
42 | return reply;
|
---|
43 | }
|
---|
44 |
|
---|
45 | inline mg_u_long unary_decode(mg_u_long *count) {
|
---|
46 | mg_u_long x;
|
---|
47 |
|
---|
48 | x = 1;
|
---|
49 | while (!this->bit()) ++x;
|
---|
50 | if (count != NULL) {
|
---|
51 | *count += x;
|
---|
52 | }
|
---|
53 | return x;
|
---|
54 | }
|
---|
55 |
|
---|
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);
|
---|
59 | if (count != NULL) {
|
---|
60 | *count += _B_x;
|
---|
61 | }
|
---|
62 | while(--_B_x)
|
---|
63 | encodeBit(0);
|
---|
64 | encodeBit(1);
|
---|
65 | }
|
---|
66 |
|
---|
67 |
|
---|
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;
|
---|
71 | register int _B_i, _B_logofb, _B_thresh;
|
---|
72 | register mg_u_long reply;
|
---|
73 |
|
---|
74 | if (_B_b != 1) {
|
---|
75 | _B_logofb = ceil_log2(_B_b);
|
---|
76 | _B_thresh = (1<<_B_logofb) - _B_b;
|
---|
77 | --_B_logofb;
|
---|
78 |
|
---|
79 | if (count != NULL) {
|
---|
80 | *count += _B_logofb;
|
---|
81 | }
|
---|
82 |
|
---|
83 | for (_B_i=0; _B_i < _B_logofb; ++_B_i) {
|
---|
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 |
|
---|
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);
|
---|
104 | register int _B_nbits, _B_logofb, _B_thresh;
|
---|
105 |
|
---|
106 | check_positive((char*)"binary", _B_x);
|
---|
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 |
|
---|
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);
|
---|
125 | register int _B_xdivb;
|
---|
126 |
|
---|
127 | _B_xdivb = this->unary_decode(count);
|
---|
128 | --_B_xdivb;
|
---|
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 |
|
---|
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);
|
---|
139 | register int _B_xdivb = 0;
|
---|
140 | check_positive((char*)"bblock", _B_xx);
|
---|
141 | --_B_xx;
|
---|
142 | while (_B_xx >= _B_bb) {
|
---|
143 | ++_B_xdivb;
|
---|
144 | _B_xx -= _B_bb;
|
---|
145 | }
|
---|
146 | unary_encode(_B_xdivb+1, count);
|
---|
147 | binary_encode(_B_xx+1, _B_bb, count);
|
---|
148 | }
|
---|
149 |
|
---|
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;
|
---|
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);
|
---|
159 | --_B_k;
|
---|
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);
|
---|
166 | --_B_xx;
|
---|
167 | check_positive((char*)"gamma", _B_xx+_B_lower);
|
---|
168 | return _B_xx+_B_lower;
|
---|
169 | }
|
---|
170 |
|
---|
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;
|
---|
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 |
|
---|
179 | check_positive((char*)"elias", _B_xx);
|
---|
180 |
|
---|
181 | while ((int)_B_xx>_B_upper) {
|
---|
182 | ++_B_k;
|
---|
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 |
|
---|
191 | inline mg_u_long gamma_decode(mg_u_long *count) {
|
---|
192 | register mg_u_long _B_xx = 1;
|
---|
193 | register int _B_nbits = 0;
|
---|
194 |
|
---|
195 | while(!this->bit()) ++_B_nbits;
|
---|
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 |
|
---|
204 | inline void gamma_encode(mg_u_long x, mg_u_long *count) {
|
---|
205 | register mg_u_long _B_xx = x;
|
---|
206 | register int _B_logofb;
|
---|
207 | register int _B_nbits;
|
---|
208 |
|
---|
209 | check_positive((char*)"gamma", _B_xx);
|
---|
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 |
|
---|
220 | inline mg_u_long delta_decode(mg_u_long *count) {
|
---|
221 | register mg_u_long _B_xxx;
|
---|
222 | register int _B_logx;
|
---|
223 | _B_logx = gamma_decode(count);
|
---|
224 | --_B_logx;
|
---|
225 | _B_xxx = binary_decode(1<<_B_logx, count);
|
---|
226 | --_B_xxx;
|
---|
227 | return (_B_xxx + (1<<_B_logx));
|
---|
228 | }
|
---|
229 |
|
---|
230 | inline void delta_encode(mg_u_long x, mg_u_long *count) {
|
---|
231 | register mg_u_long _B_xxx = x;
|
---|
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 |
|
---|
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;
|
---|
244 | do {
|
---|
245 | __code += __code + bit();
|
---|
246 | if (count != NULL) ++(*count);
|
---|
247 | } while (__code < *++__mclen);
|
---|
248 |
|
---|
249 | return __values[__mclen - __min_code][__code - *__mclen];
|
---|
250 | }
|
---|
251 |
|
---|
252 | inline void huff_encode(mg_u_long x, mg_u_long *codes, char *lens,
|
---|
253 | mg_u_long *count = NULL) {
|
---|
254 | register int __i;
|
---|
255 | register int __clen = lens[x];
|
---|
256 | register mg_u_long __code = codes[x];
|
---|
257 | for (__i=__clen-1; __i>=0; --__i) {
|
---|
258 | encodeBit((__code >> __i) & 1);
|
---|
259 | }
|
---|
260 | if (count != NULL) {
|
---|
261 | *count += lens[x];
|
---|
262 | }
|
---|
263 | }
|
---|
264 |
|
---|
265 | static inline mg_u_long unary_length(mg_u_long x) {
|
---|
266 | check_positive((char*)"unary", x);
|
---|
267 | return x;
|
---|
268 | }
|
---|
269 |
|
---|
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);
|
---|
273 | register int _B_nbits, _B_logofb, _B_thresh;
|
---|
274 |
|
---|
275 | check_positive((char*)"binary", _B_x);
|
---|
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 |
|
---|
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);
|
---|
286 | register int _B_xdivb = 0;
|
---|
287 |
|
---|
288 | check_positive((char*)"bblock", _B_xx);
|
---|
289 | --_B_xx;
|
---|
290 | while (_B_xx >= _B_bb) {
|
---|
291 | ++_B_xdivb;
|
---|
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 |
|
---|
300 | static inline mg_u_long elias_length(mg_u_long x, mg_u_long b,
|
---|
301 | double s) {
|
---|
302 | register mg_u_long _B_xx = x;
|
---|
303 | register mg_u_long _B_b = b;
|
---|
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;
|
---|
308 | register mg_u_long count;
|
---|
309 | check_positive((char*)"gamma", _B_xx);
|
---|
310 |
|
---|
311 | while ((int)(_B_xx)>_B_upper) {
|
---|
312 | ++_B_k;
|
---|
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 |
|
---|
323 | static inline mg_u_long gamma_length(mg_u_long x) {
|
---|
324 | register mg_u_long _B_xx = x;
|
---|
325 | register int _B_logofb;
|
---|
326 | check_positive((char*)"gamma", _B_xx);
|
---|
327 | _B_logofb = floor_log2(_B_xx);
|
---|
328 | return _B_logofb*2+1;
|
---|
329 | }
|
---|
330 |
|
---|
331 | static inline mg_u_long delta_length(mg_u_long x) {
|
---|
332 | register mg_u_long _B_xxx = x;
|
---|
333 | register int _B_logx, _B_dcount;
|
---|
334 | register mg_u_long count;
|
---|
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
|
---|