content: package btools.util;
  
  
  public class BitCoderContext {
    private byte[] ab;
    private int idxMax;
    private int idx = -1;
    private int bits; // bits left in buffer
    private int b; // buffer word
  
    public static final int[] vl_values = new int[4096];
    public static final int[] vl_length = new int[4096];
  
    private static final int[] vc_values = new int[4096];
    private static final int[] vc_length = new int[4096];
  
    private static final int[] reverse_byte = new int[256];
  
    private static final int[] bm2bits = new int[256];
  
    static {
      // fill varbits lookup table
  
      BitCoderContext bc = new BitCoderContext(new byte[4]);
      for (int i = 0; i < 4096; i++) {
        bc.reset();
        bc.bits = 14;
        bc.b = 0x1000 + i;
  
        int b0 = bc.getReadingBitPosition();
        vl_values[i] = bc.decodeVarBits2();
        vl_length[i] = bc.getReadingBitPosition() - b0;
      }
      for (int i = 0; i < 4096; i++) {
        bc.reset();
        int b0 = bc.getWritingBitPosition();
        bc.encodeVarBits2(i);
        vc_values[i] = bc.b;
        vc_length[i] = bc.getWritingBitPosition() - b0;
      }
      for (int i = 0; i < 1024; i++) {
        bc.reset();
        bc.bits = 14;
        bc.b = 0x1000 + i;
  
        int b0 = bc.getReadingBitPosition();
        vl_values[i] = bc.decodeVarBits2();
        vl_length[i] = bc.getReadingBitPosition() - b0;
      }
      for (int b = 0; b < 256; b++) {
        int r = 0;
        for (int i = 0; i < 8; i++) {
          if ((b & (1 << i)) != 0) r |= 1 << (7 - i);
        }
        reverse_byte[b] = r;
      }
      for (int b = 0; b < 8; b++) {
        bm2bits[1 << b] = b;
      }
    }
  
  
    public BitCoderContext(byte[] ab) {
      this.ab = ab;
      idxMax = ab.length - 1;
    }
  
    public final void reset(byte[] ab) {
      this.ab = ab;
      idxMax = ab.length - 1;
      reset();
    }
  
    public final void reset() {
      idx = -1;
      bits = 0;
      b = 0;
    }
  
    /**
     * encode a distance with a variable bit length
     * (poor mans huffman tree)
     * {@code 1 -> 0}
     * {@code 01 -> 1} + following 1-bit word ( 1..2 )
     * {@code 001 -> 3} + following 2-bit word ( 3..6 )
     * {@code 0001 -> 7} + following 3-bit word ( 7..14 ) etc.
     *
     * @see #decodeVarBits
     */
    public final void encodeVarBits2(int value) {
      int range = 0;
      while (value > range) {
        encodeBit(false);
        value -= range + 1;
        range = 2 * range + 1;
      }
      encodeBit(true);
      encodeBounded(range, value);
    }
  
    public final void encodeVarBits(int value) {
      if ((value & 0xfff) == value) {
        flushBuffer();
        b |= vc_values[value] << bits;
        bits += vc_length[value];
      } else {
        encodeVarBits2(value); // slow fallback for large values
      }
    }
  
    /**
     * @see #encodeVarBits
     */
    public final int decodeVarBits2() {
      int range = 0;
      while (!decodeBit()) {
        range = 2 * range + 1;
      }
      return range + decodeBounded(range);
    }
  
    public final int decodeVarBits() {
      fillBuffer();
      int b12 = b & 0xfff;
      int len = vl_length[b12];
      if (len <= 12) {
        b >>>= len;
        bits -= len;
        return vl_values[b12]; // full value lookup
      }
      if (len <= 23) { // // only length lookup
        int len2 = len >> 1;
        b >>>= (len2 + 1);
        int mask = 0xffffffff >>> (32 - len2);
        mask += b & mask;
        b >>>= len2;
        bits -= len;
        return mask;
      }
      if ((b & 0xffffff) != 0) {
        // here we just know len in [25..47]
        // ( fillBuffer guarantees only 24 bits! )
        b >>>= 12;
        int len3 = 1 + (vl_length[b & 0xfff] >> 1);
        b >>>= len3;
        int len2 = 11 + len3;
        bits -= len2 + 1;
        fillBuffer();
        int mask = 0xffffffff >>> (32 - len2);
        mask += b & mask;
        b >>>= len2;
        bits -= len2;
        return mask;
      }
      return decodeVarBits2(); // no chance, use the slow one
    }
  
  
    public final void encodeBit(boolean value) {
      if (bits > 31) {
        ab[++idx] = (byte) (b & 0xff);
        b >>>= 8;
        bits -= 8;
      }
      if (value) {
        b |= 1 << bits;
      }
      bits++;
    }
  
    public final boolean decodeBit() {
      if (bits == 0) {
        bits = 8;
        b = ab[++idx] & 0xff;
      }
      boolean value = ((b & 1) != 0);
      b >>>= 1;
      bits--;
      return value;
    }
  
    /**
     * encode an integer in the range 0..max (inclusive).
     * For max = 2^n-1, this just encodes n bits, but in general
     * this is variable length encoding, with the shorter codes
     * for the central value range
     */
    public final void encodeBounded(int max, int value) {
      int im = 1; // integer mask
      while (im <= max) {
        if ((value & im) != 0) {
          encodeBit(true);
          max -= im;
        } else {
          encodeBit(false);
        }
        im <<= 1;
      }
    }
  
    /**
     * decode an integer in the range 0..max (inclusive).
     *
     * @see #encodeBounded
     */
    public final int decodeBounded(int max) {
      int value = 0;
      int im = 1; // integer mask
      while ((value | im) <= max) {
        if (bits == 0) {
          bits = 8;
          b = ab[++idx] & 0xff;
        }
        if ((b & 1) != 0)
          value |= im;
        b >>>= 1;
        bits--;
        im <<= 1;
      }
      return value;
    }
  
    public final int decodeBits(int count) {
      fillBuffer();
      int mask = 0xffffffff >>> (32 - count);
      int value = b & mask;
      b >>>= count;
      bits -= count;
      return value;
    }
  
    public final int decodeBitsReverse(int count) {
      fillBuffer();
      int value = 0;
      while (count > 8) {
        value = (value << 8) | reverse_byte[b & 0xff];
        b >>= 8;
        count -= 8;
        bits -= 8;
        fillBuffer();
      }
      value = (value << count) | reverse_byte[b & 0xff] >> (8 - count);
      bits -= count;
      b >>= count;
      return value;
    }
  
    private void fillBuffer() {
      while (bits < 24) {
        if (idx++ < idxMax) {
          b |= (ab[idx] & 0xff) << bits;
        }
        bits += 8;
      }
    }
  
    private void flushBuffer() {
      while (bits > 7) {
        ab[++idx] = (byte) (b & 0xff);
        b >>>= 8;
        bits -= 8;
      }
    }
  
    /**
     * flushes and closes the (write-mode) context
     *
     * @return the encoded length in bytes
     */
    public final int closeAndGetEncodedLength() {
      flushBuffer();
      if (bits > 0) {
        ab[++idx] = (byte) (b & 0xff);
      }
      return idx + 1;
    }
  
    /**
     * @return the encoded length in bits
     */
    public final int getWritingBitPosition() {
      return (idx << 3) + 8 + bits;
    }
  
    public final int getReadingBitPosition() {
      return (idx << 3) + 8 - bits;
    }
  
    public final void setReadingBitPosition(int pos) {
      idx = pos >>> 3;
      bits = (idx << 3) + 8 - pos;
      b = ab[idx] & 0xff;
      b >>>= (8 - bits);
    }
  
    public static void main(String[] args) {
      byte[] ab = new byte[581969];
      BitCoderContext ctx = new BitCoderContext(ab);
      for (int i = 0; i < 31; i++) {
        ctx.encodeVarBits((1 << i) + 3);
      }
      for (int i = 0; i < 100000; i += 13) {
        ctx.encodeVarBits(i);
      }
      ctx.closeAndGetEncodedLength();
      ctx = new BitCoderContext(ab);
  
      for (int i = 0; i < 31; i++) {
        int value = ctx.decodeVarBits();
        int v0 = (1 << i) + 3;
        if (v0 != value)
          throw new RuntimeException("value mismatch value=" + value + "v0=" + v0);
      }
      for (int i = 0; i < 100000; i += 13) {
        int value = ctx.decodeVarBits();
        if (value != i)
          throw new RuntimeException("value mismatch i=" + i + "v=" + value);
      }
    }
  }
  