[3365] | 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;
|
---|
[9612] | 24 | ++reply;
|
---|
[3365] | 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;
|
---|
[9612] | 37 | ++reply;
|
---|
[3365] | 38 | }
|
---|
| 39 | return reply;
|
---|
| 40 | }
|
---|
| 41 |
|
---|
| 42 | inline unsigned long unary_decode(unsigned long *count) {
|
---|
| 43 | unsigned long x;
|
---|
| 44 |
|
---|
| 45 | x = 1;
|
---|
[9612] | 46 | while (!this->bit()) ++x;
|
---|
[3365] | 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;
|
---|
[9612] | 74 | --_B_logofb;
|
---|
[3365] | 75 |
|
---|
| 76 | if (count != NULL) {
|
---|
| 77 | *count += _B_logofb;
|
---|
| 78 | }
|
---|
| 79 |
|
---|
[9612] | 80 | for (_B_i=0; _B_i < _B_logofb; ++_B_i) {
|
---|
[3365] | 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);
|
---|
[9612] | 125 | --_B_xdivb;
|
---|
[3365] | 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);
|
---|
[9612] | 138 | --_B_xx;
|
---|
[3365] | 139 | while (_B_xx >= _B_bb) {
|
---|
[9612] | 140 | ++_B_xdivb;
|
---|
[3365] | 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);
|
---|
[9612] | 156 | --_B_k;
|
---|
[3365] | 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);
|
---|
[9612] | 163 | --_B_xx;
|
---|
[3365] | 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) {
|
---|
[9612] | 179 | ++_B_k;
|
---|
[3365] | 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 |
|
---|
[9612] | 192 | while(!this->bit()) ++_B_nbits;
|
---|
[3365] | 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);
|
---|
[9612] | 221 | --_B_logx;
|
---|
[3365] | 222 | _B_xxx = binary_decode(1<<_B_logx, count);
|
---|
[9612] | 223 | --_B_xxx;
|
---|
[3365] | 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();
|
---|
[9612] | 243 | if (count != NULL) ++(*count);
|
---|
[3365] | 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];
|
---|
[9612] | 254 | for (__i=__clen-1; __i>=0; --__i) {
|
---|
[3365] | 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);
|
---|
[9612] | 286 | --_B_xx;
|
---|
[3365] | 287 | while (_B_xx >= _B_bb) {
|
---|
[9612] | 288 | ++_B_xdivb;
|
---|
[3365] | 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) {
|
---|
[9612] | 309 | ++_B_k;
|
---|
[3365] | 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
|
---|