[3365] | 1 | #ifndef H_BITIO_ABSTRACT
|
---|
| 2 | #define H_BITIO_ABSTRACT
|
---|
[25147] | 3 | #include "mglong.h"
|
---|
[18716] | 4 | #include <cstdlib>
|
---|
[3365] | 5 | class bitio_buffer {
|
---|
| 6 | public:
|
---|
| 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
|
---|