source: tags/greenstone-3_01-distribution/mgpp/lib/bitio_m_abstract.h@ 10896

#ifndef H_BITIO_ABSTRACT
#define H_BITIO_ABSTRACT

class bitio_buffer {
public:
  virtual int bit() = 0;
  virtual void encodeBit(int bit) = 0;
  virtual void seek(unsigned long topos) = 0;
  
  static inline void check_positive(char *type, unsigned long x) {
    if (x <= 0) {
      fprintf(stderr, "Error: Cannot %s encode %lu\n", type, x);
      exit(1);
    }
  }

  static inline int floor_log2(unsigned long x) {
    unsigned long  _B_x = x;
    int reply;
    
    reply = -1;
    while (_B_x != 0) {
      _B_x >>= 1;
      ++reply;
    }
    return reply;
  }
  
  static inline int ceil_log2(unsigned long x) {
    register int _B_x;
    unsigned long reply;
    
    _B_x = x - 1;
    reply = 0;
    while (_B_x != 0) {
      _B_x >>= 1;
      ++reply;
    }
    return reply;
  }

  inline unsigned long unary_decode(unsigned long *count) {
    unsigned long x;
    
    x = 1;
    while (!this->bit()) ++x;
    if (count != NULL) {
      *count += x;
    }
    return x;
  }

  inline void unary_encode(unsigned long x, unsigned long *count) {
    register unsigned long _B_x = x;
    check_positive("unary", _B_x);
    if (count != NULL) {
      *count += _B_x;
    }
    while(--_B_x) 
      encodeBit(0);
    encodeBit(1);
  }


  inline unsigned long binary_decode(unsigned long b, unsigned long *count) {
    register unsigned long _B_x = 0;
    register unsigned long _B_b = b;
    register int _B_i, _B_logofb, _B_thresh;
    register unsigned long reply;
    
    if (_B_b != 1) {                    
      _B_logofb = ceil_log2(_B_b);
      _B_thresh = (1<<_B_logofb) - _B_b;
      --_B_logofb;
      
      if (count != NULL) {
    *count += _B_logofb;
      }
      
      for (_B_i=0; _B_i < _B_logofb; ++_B_i) {
    _B_x += _B_x + this->bit();
      }

      if ((int)_B_x >= _B_thresh) {
    _B_x += _B_x + this->bit();
    _B_x -= _B_thresh;
    if (count != NULL) {
      *count = *count + 1;
    }
      }
      reply = _B_x+1;
      
    } else reply = 1;
    
    return reply;
  }

  inline void binary_encode(unsigned long x, unsigned long b, unsigned long *count) {
    register unsigned long _B_x = (x);
    register unsigned long _B_b = (b);
    register int _B_nbits, _B_logofb, _B_thresh;
    
    check_positive("binary", _B_x);
    _B_logofb = ceil_log2(_B_b);
    
    _B_thresh = (1<<_B_logofb) - _B_b;
    if ((int)(--_B_x) < _B_thresh) _B_nbits = _B_logofb-1;
    else {
      _B_nbits = _B_logofb;
      _B_x += _B_thresh;
    }
    if (count != NULL) {
      *count += _B_nbits;
    }
    while (--_B_nbits>=0)
      encodeBit((_B_x>>_B_nbits) & 0x1);
  }

  inline unsigned long bblock_decode(unsigned long b, unsigned long *count) {
    register unsigned long _B_x1, _B_xx = 0;
    register unsigned long _B_bb = (b);
    register int _B_xdivb;
    
    _B_xdivb = this->unary_decode(count);
    --_B_xdivb;                    
    while (_B_xdivb--) {
      _B_xx += _B_bb;
    }
    _B_x1 = this->binary_decode(_B_bb, count);
    return (_B_xx + _B_x1);
  }
  
  inline void bblock_encode(unsigned long x, unsigned long b, unsigned long *count) {
    register unsigned long _B_xx = (x);
    register unsigned long _B_bb = (b);
    register int _B_xdivb = 0;
    check_positive("bblock", _B_xx);
    --_B_xx;
    while (_B_xx >= _B_bb) {
      ++_B_xdivb;
      _B_xx -= _B_bb;
    }
    unary_encode(_B_xdivb+1, count);
    binary_encode(_B_xx+1, _B_bb, count);
  }

  inline unsigned long elias_decode(unsigned long b, double s, unsigned long *count) {
    register unsigned long _B_xx;
    register unsigned long _B_b = b;
    register double _B_s = s;
    register int _B_lower=1, _B_upper=1;
    register int _B_k;
    register double _B_pow=1.0;
    
    _B_k = this->unary_decode(count);
    --_B_k;
    while (_B_k--) {
      _B_lower = _B_upper+1;
      _B_pow *= _B_s;
      _B_upper += (int) (_B_b*_B_pow);
    }
    _B_xx = this->binary_decode(_B_upper-_B_lower+1, count);
    --_B_xx;
    check_positive("gamma", _B_xx+_B_lower);
    return _B_xx+_B_lower;
  }
  
  inline void elias_encode(unsigned long x, unsigned long b, double s, unsigned long *count) {
    register unsigned long _B_xx = x;
    register unsigned long _B_b = b;
    register double _B_s = s;
    register int _B_lower=1, _B_upper=1;
    register int _B_k=0;
    register double _B_pow=1.0;
    
    check_positive("elias", _B_xx);
    
    while ((int)_B_xx>_B_upper) {
      ++_B_k;
      _B_lower = _B_upper+1;
      _B_pow *= _B_s;
      _B_upper += (int) (_B_b*_B_pow);
    }
    unary_encode(_B_k+1, count);
    binary_encode(_B_xx-_B_lower+1, _B_upper-_B_lower+1, count);
  }
  
  inline unsigned long gamma_decode(unsigned long *count) {
    register unsigned long _B_xx = 1;
    register int _B_nbits = 0;
    
    while(!this->bit()) ++_B_nbits;
    if (count != NULL) {
      *count += _B_nbits*2+1;
    }
    while (_B_nbits-- > 0)
      _B_xx += _B_xx + this->bit();
    return _B_xx;
  }

  inline void gamma_encode(unsigned long x, unsigned long *count) {
    register unsigned long _B_xx = x;
    register int _B_logofb;
    register int _B_nbits;
    
    check_positive("gamma", _B_xx);
    _B_logofb = floor_log2(_B_xx);
    _B_nbits = _B_logofb+1;
    
    if (count != NULL) { 
      *count += _B_logofb*2+1;
    }
    while(_B_logofb--) encodeBit(0);
    while (--_B_nbits>=0) encodeBit((_B_xx>>_B_nbits) & 0x1);
  }
  
  inline unsigned long delta_decode(unsigned long *count) {
    register unsigned long _B_xxx;
    register int _B_logx;
    _B_logx = gamma_decode(count);
    --_B_logx;
    _B_xxx = binary_decode(1<<_B_logx, count); 
    --_B_xxx;
    return (_B_xxx + (1<<_B_logx));
  }

  inline void delta_encode(unsigned long x, unsigned long *count) {
    register unsigned long _B_xxx = x;
    register int _B_logx;
    _B_logx = floor_log2(_B_xxx);
    gamma_encode(_B_logx+1, count);
    binary_encode(_B_xxx+1, 1<<_B_logx, count);
  }

  inline unsigned long huff_decode(unsigned long *mcodes, unsigned long **values,
                   unsigned long *count = NULL) {
    register unsigned long *__min_code = mcodes;
    register unsigned long *__mclen    = mcodes;
    register unsigned long **__values  = values;
    register unsigned long __code = 0;
    do {
      __code += __code + bit();
      if (count != NULL) ++(*count);
    } while (__code < *++__mclen);
    
    return __values[__mclen - __min_code][__code - *__mclen];
  }

  inline void huff_encode(unsigned long x, unsigned long *codes, char *lens,
              unsigned long *count = NULL) {
    register int __i;
    register int __clen = lens[x];
    register unsigned long __code = codes[x];
    for (__i=__clen-1; __i>=0; --__i) {
      encodeBit((__code >> __i) & 1);
    }
    if (count != NULL) {
      *count += lens[x];
    }
  }

  static inline unsigned long unary_length(unsigned long x) {
    check_positive("unary", x);
    return x;
  }

  static inline int binary_length(unsigned long x, unsigned long b) {
    register unsigned long _B_x = (x);
    register unsigned long _B_b = (b);
    register int _B_nbits, _B_logofb, _B_thresh;
    
    check_positive("binary", _B_x);
    _B_logofb = ceil_log2(_B_b);
    _B_thresh = (1<<_B_logofb) - _B_b;
    if ((int)(--_B_x) < _B_thresh) _B_nbits = _B_logofb-1;
    else _B_nbits = _B_logofb;
    return _B_nbits;
  }

  static inline unsigned long bblock_length(unsigned long x, unsigned long b) {
    register unsigned long _B_bcount, count, _B_xx = (x);
    register unsigned long _B_bb = (b);
    register int _B_xdivb = 0;
    
    check_positive("bblock", _B_xx);
    --_B_xx;
    while (_B_xx >= _B_bb) {
      ++_B_xdivb;
      _B_xx -= _B_bb;
    }
    count = unary_length(_B_xdivb+1);
    _B_bcount = binary_length(_B_xx+1, _B_bb);
    count += _B_bcount;
    return count;
  }
  
  static inline unsigned long elias_length(unsigned long x, unsigned long b, 
                       double s) {
    register unsigned long _B_xx = x;
    register unsigned long _B_b = b;
    register double _B_s = s;
    register int _B_lower=1, _B_upper=1;
    register int _B_k=0, _B_ecount;
    register double _B_pow=1.0;
    register unsigned long count;
    check_positive("gamma", _B_xx);
    
    while ((int)(_B_xx)>_B_upper) {
      ++_B_k;
      _B_lower = _B_upper+1;
      _B_pow *= _B_s;
      _B_upper += (int) (_B_b*_B_pow);
    }
    count = unary_length(_B_k+1);
    _B_ecount = binary_length(_B_xx-_B_lower+1, _B_upper-_B_lower+1);
    count += _B_ecount;
    return count;
  }
  
  static inline unsigned long gamma_length(unsigned long x) {
    register unsigned long _B_xx = x;
    register int _B_logofb;
    check_positive("gamma", _B_xx);
    _B_logofb = floor_log2(_B_xx);
    return _B_logofb*2+1;
  }

  static inline unsigned long delta_length(unsigned long x) {
    register unsigned long _B_xxx = x;
    register int _B_logx, _B_dcount;
    register unsigned long count;
    _B_logx = floor_log2 (_B_xxx);
    count = gamma_length(_B_logx+1);
    _B_dcount = binary_length (_B_xxx+1, 1<<_B_logx);
    count += _B_dcount;
    return count;
  }
};

#endif