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