public class BitStreamException extends RuntimeException
{
    private static final long serialVersionUID = 7279737120722476336L;

    public static final int UNDEFINED = 0;
    public static final int INPUT_OUTPUT   = 1;
    public static final int END_OF_STREAM  = 2;
    public static final int INVALID_STREAM = 3;
    public static final int STREAM_CLOSED  = 4;

    private final int code;


    protected BitStreamException()
    {
        this.code = UNDEFINED;
    }


    public BitStreamException(String message, int code)
    {
        super(message);
        this.code = code;
    }


    public BitStreamException(String message, Throwable cause, int code)
    {
        super(message, cause);
        this.code = code;
    }


    public BitStreamException(Throwable cause, int code)
    {
        super(cause);
        this.code = code;
    }


    public int getErrorCode()
    {
        return this.code;
    }
} public class BinaryEntropyDecoder implements EntropyDecoder
{
   private static final long TOP        = 0x00FFFFFFFFFFFFFFL;
   private static final long MASK_24_56 = 0x00FFFFFFFF000000L;
   private static final long MASK_0_56  = 0x00FFFFFFFFFFFFFFL;
   private static final long MASK_0_32  = 0x00000000FFFFFFFFL;
   private static final int MAX_BLOCK_SIZE = 1 << 30;
   private static final int MAX_CHUNK_SIZE = 1 << 26;

   private final Predictor predictor;
   private long low;
   private long high;
   private long current;
   private final InputBitStream bitstream;
   private SliceByteArray sba;


   public BinaryEntropyDecoder(InputBitStream bitstream, Predictor predictor)
   {
      if (bitstream == null)
         throw new NullPointerException("BinaryEntropy codec: Invalid null bitstream parameter");

      if (predictor == null)
         throw new NullPointerException("BinaryEntropy codec: Invalid null predictor parameter");

      // Defer stream reading. We are creating the object, we should not do any I/O
      this.low = 0L;
      this.high = TOP;
      this.bitstream = bitstream;
      this.predictor = predictor;
      this.sba = new SliceByteArray(new byte[0], 0);
   }


   @Override
   public int decode(byte[] block, int blkptr, int count)
   {
      if ((block == null) || (blkptr+count > block.length) || (blkptr < 0) || (count < 0) || (count > MAX_BLOCK_SIZE))
         return -1;

      if (count == 0)
         return 0;

      int startChunk = blkptr;
      final int end = blkptr + count;
      int length = (count < 64) ? 64 : count;

      if (count >= MAX_CHUNK_SIZE)
      {
         // If the block is big (>=64MB), split the decoding to avoid allocating
         // too much memory.
         length = (count < 8*MAX_CHUNK_SIZE) ? count>>3 : count>>4;
      }

      // Split block into chunks, read bit array from bitstream and decode chunk
      while (startChunk < end)
      {
         final int chunkSize = Math.min(length, end-startChunk);

         if (this.sba.array.length < (chunkSize+(chunkSize>>3)))
            this.sba.array = new byte[chunkSize+(chunkSize>>3)];

         final int szBytes = EntropyUtils.readVarInt(this.bitstream);
         this.current = this.bitstream.readBits(56);

         if (szBytes != 0)
            this.bitstream.readBits(this.sba.array, 0, 8*szBytes);

         this.sba.index = 0;
         final int endChunk = startChunk + chunkSize;

         for (int i=startChunk; i<endChunk; i++)
            block[i] = this.decodeByte();

         startChunk = endChunk;
      }

      return count;
   }


   public final byte decodeByte()
   {
      return (byte) ((this.decodeBit(this.predictor.get()) << 7)
            | (this.decodeBit(this.predictor.get()) << 6)
            | (this.decodeBit(this.predictor.get()) << 5)
            | (this.decodeBit(this.predictor.get()) << 4)
            | (this.decodeBit(this.predictor.get()) << 3)
            | (this.decodeBit(this.predictor.get()) << 2)
            | (this.decodeBit(this.predictor.get()) << 1)
            |  this.decodeBit(this.predictor.get()));
   }


   public int decodeBit(int pred)
   {
      // Calculate interval split
      // Written in a way to maximize accuracy of multiplication/division
      final long split = ((((this.high - this.low) >>> 4) * pred) >>> 8) + this.low;
      int bit;

      if (split >= this.current)
      {
         bit = 1;
         this.high = split;
      }
      else
      {
         bit = 0;
         this.low = -~split;
      }

       // Update predictor
      this.predictor.update(bit);

      // Read 32 bits from bitstream
      while (((this.low ^ this.high) & MASK_24_56) == 0)
         this.read();

      return bit;
   }


   protected void read()
   {
      this.low = (this.low<<32) & MASK_0_56;
      this.high = ((this.high<<32) | MASK_0_32) & MASK_0_56;
      final long val = Memory.BigEndian.readInt32(this.sba.array, this.sba.index) & 0xFFFFFFFFL;
      this.current = ((this.current<<32) | val) & MASK_0_56;
      this.sba.index += 4;
   }


   @Override
   public InputBitStream getBitStream()
   {
      return this.bitstream;
   }


   @Override
   public void dispose()
   {
   }
} public class BinaryEntropyEncoder implements EntropyEncoder
{
   private static final long TOP        = 0x00FFFFFFFFFFFFFFL;
   private static final long MASK_24_56 = 0x00FFFFFFFF000000L;
   private static final long MASK_0_24  = 0x0000000000FFFFFFL;
   private static final long MASK_0_32  = 0x00000000FFFFFFFFL;
   private static final int MAX_BLOCK_SIZE = 1 << 30;
   private static final int MAX_CHUNK_SIZE = 1 << 26;

   private final Predictor predictor;
   private long low;
   private long high;
   private final OutputBitStream bitstream;
   private boolean disposed;
   private SliceByteArray sba;


   public BinaryEntropyEncoder(OutputBitStream bitstream, Predictor predictor)
   {
      if (bitstream == null)
         throw new NullPointerException("BinaryEntropy codec: Invalid null bitstream parameter");

      if (predictor == null)
         throw new NullPointerException("BinaryEntropy codec: Invalid null predictor parameter");

      this.low = 0L;
      this.high = TOP;
      this.bitstream = bitstream;
      this.predictor = predictor;
      this.sba = new SliceByteArray(new byte[0], 0);
   }


   @Override
   public int encode(byte[] block, int blkptr, int count)
   {
      if ((block == null) || (blkptr+count > block.length) || (blkptr < 0) || (count < 0) || (count > MAX_BLOCK_SIZE))
         return -1;

      if (count == 0)
         return 0;

      int startChunk = blkptr;
      final int end = blkptr + count;
      int length = (count < 64) ? 64 : count;

      if (count >= MAX_CHUNK_SIZE)
      {
         // If the block is big (>=64MB), split the encoding to avoid allocating
         // too much memory.
         length = (count < 8*MAX_CHUNK_SIZE) ? count>>3 : count>>4;
      }

      // Split block into chunks, encode chunk and write bit array to bitstream
      while (startChunk < end)
      {
         final int chunkSize = Math.min(length, end-startChunk);

         if (this.sba.array.length < (chunkSize+(chunkSize>>3)))
            this.sba.array = new byte[chunkSize+(chunkSize>>3)];

         this.sba.index = 0;
         final int endChunk = startChunk + chunkSize;

         for (int i=startChunk; i<endChunk; i++)
            this.encodeByte(block[i]);

         EntropyUtils.writeVarInt(this.bitstream, this.sba.index);
         this.bitstream.writeBits(this.sba.array, 0, 8*this.sba.index);
         startChunk = endChunk;

         if (startChunk < end)
            this.bitstream.writeBits(this.low | MASK_0_24, 56);
      }

      return count;
   }


   public final void encodeByte(byte val)
   {
      this.encodeBit((val >> 7) & 1, this.predictor.get());
      this.encodeBit((val >> 6) & 1, this.predictor.get());
      this.encodeBit((val >> 5) & 1, this.predictor.get());
      this.encodeBit((val >> 4) & 1, this.predictor.get());
      this.encodeBit((val >> 3) & 1, this.predictor.get());
      this.encodeBit((val >> 2) & 1, this.predictor.get());
      this.encodeBit((val >> 1) & 1, this.predictor.get());
      this.encodeBit(val & 1, this.predictor.get());
   }


   public void encodeBit(int bit, int pred)
   {
      // Calculate interval split
      // Written in a way to maximize accuracy of multiplication/division
      final long split = (((this.high - this.low) >>> 4) * pred) >>> 8;

      // Update fields with new interval bounds
      if (bit == 0)
         this.low += (split + 1);
      else
         this.high = this.low + split;
	
      // Update predictor
      this.predictor.update(bit);

      // Write unchanged first 32 bits to bitstream
      while (((this.low ^ this.high) & MASK_24_56) == 0)
         this.flush();
   }


   private void flush()
   {
      Memory.BigEndian.writeInt32(this.sba.array, this.sba.index, (int) (this.high>>>24));
      this.sba.index += 4;
      this.low <<= 32;
      this.high = (this.high<<32) | MASK_0_32;
   }


   @Override
   public OutputBitStream getBitStream()
   {
      return this.bitstream;
   }


   @Override
   public void dispose()
   {
      if (this.disposed == true)
         return;

      this.disposed = true;
      this.bitstream.writeBits(this.low | MASK_0_24, 56);
   }
} public interface EntropyDecoder
{
    // Decode the next chunk of data from the bitstream and return in the
    // provided buffer.
    public int decode(byte[] buffer, int blkptr, int len);

    // Must be called before getting rid of the entropy coder
    public void dispose();

    // Return the underlying bitstream
    public InputBitStream getBitStream();
} public interface EntropyEncoder
{
    // Encode the array provided into the bitstream. Return the number of bytes
    // written to the bitstream
    public int encode(byte[] array, int blkptr, int len);

    // Return the underlying bitstream
    public OutputBitStream getBitStream();

    // Must be called before getting rid of the entropy coder
    // Trying to encode after a call to dispose gives undefined behavior
    public void dispose();
} public interface InputBitStream
{
   // Return 1 or 0
   public int readBit() throws BitStreamException;

   // Length is the number of bits in [1..64]. Return the bits read as a long
   // Throws if the stream is closed.
   public long readBits(int length) throws BitStreamException;

   // Read bits and put them in the byte array at index 'start'.
   // Length is the number of bits
   // Return the number of bits read.
   // Throws if the stream is closed.
   public int readBits(byte[] bits, int start, int length) throws BitStreamException;

   public void close() throws BitStreamException;

   // Number of bits read
   public long read();

   // Return false when the bitstream is closed or the End-Of-Stream has been reached
   public boolean hasMoreToRead();
} public interface OutputBitStream
{
   // Write the least significant bit of the input integer
   // Throws if the stream is closed.
   public void writeBit(int bit) throws BitStreamException;

   // Length is the number of bits in [1..64]. Return the number of bits written.
   // Throws if the stream is closed.
   public int writeBits(long bits, int length) throws BitStreamException;

   // Write bits ouf of the byte array at index 'start'.
   // Length is the number of bits.
   // Return the number of bits written.
   // Throws if the stream is closed.
   public int writeBits(byte[] bits, int start, int nbBits) throws BitStreamException;

   public void close() throws BitStreamException;

   // Number of bits written
   public long written();
} public final class DebugOutputBitStream implements OutputBitStream
{
   private final OutputBitStream delegate;
   private final PrintStream out;
   private final int width;
   private int lineIndex;
   private boolean mark;
   private boolean hexa;
   private byte current;


   public DebugOutputBitStream(OutputBitStream bitstream)
   {
      this(bitstream, System.out, 80);
   }


   public DebugOutputBitStream(OutputBitStream bitstream, PrintStream out)
   {
      this(bitstream, out, 80);
   }


   public DebugOutputBitStream(OutputBitStream bitstream, PrintStream out, int width)
   {
      if (bitstream == null)
         throw new NullPointerException("Invalid null bitstream parameter");

      if (out == null)
         throw new NullPointerException("Invalid null print stream parameter");

      if ((width != -1) && (width < 8))
         width = 8;

      if (width != -1)
         width &= 0xFFFFFFF8;

      this.width = width;
      this.delegate = bitstream;
      this.out = out;
   }


   public synchronized void setMark(boolean mark)
   {
      this.mark = mark;
   }


   public synchronized boolean mark()
   {
      return this.mark;
   }


   public synchronized void showByte(boolean hex)
   {
      this.hexa = hex;
   }


   public synchronized boolean showByte()
   {
      return this.hexa;
   }


   protected synchronized void printByte(byte val)
   {
      if ((val >= 0) && (val < 10))
         this.out.print(" [00" + (val & 0xFF) + "] ");
      else if ((val >= 0) && (val < 100))
         this.out.print(" [0" + (val & 0xFF) + "] ");
      else
         this.out.print(" [" + (val & 0xFF) + "] ");
   }


   // Processes the least significant bit of the input integer
   @Override
   public synchronized void writeBit(int bit) throws BitStreamException
   {
      bit &= 1;
      this.out.print((bit == 1) ? "1" : "0");
      this.current <<= 1;
      this.current |= bit;
      this.lineIndex++;

      if (this.mark == true)
         this.out.print("w");

      if (this.width != -1)
      {
         if ((this.lineIndex-1) % this.width == this.width-1)
         {
            if (this.showByte())
               this.printByte(this.current);

            this.out.println();
            this.lineIndex = 0;
         }
         else if ((this.lineIndex & 7) == 0)
         {
            if (this.showByte())
               this.printByte(this.current);
            else
               this.out.print(" ");
         }
      }
      else if ((this.lineIndex & 7) == 0)
      {
         if (this.showByte())
            this.printByte(this.current);
         else
            this.out.print(" ");
      }

      this.delegate.writeBit(bit);
   }


   @Override
   public synchronized int writeBits(long bits, int length) throws BitStreamException
   {
      int res = this.delegate.writeBits(bits, length);

      for (int i=1; i<=res; i++)
      {
         long bit = (bits >>> (res-i)) & 1;
         this.current <<= 1;
         this.current |= bit;
         this.lineIndex++;
         this.out.print((bit == 1) ? "1" : "0");

         if ((this.mark == true) && (i == res))
            this.out.print("w");

         if (this.width != -1)
         {
            if (this.lineIndex % this.width == 0)
            {
               if (this.showByte())
                  this.printByte(this.current);

               this.out.println();
               this.lineIndex = 0;
            }
            else if ((this.lineIndex & 7) == 0)
            {
               if (this.showByte())
                  this.printByte(this.current);
               else
                  this.out.print(" ");
            }
         }
         else if ((this.lineIndex & 7) == 0)
         {
            if (this.showByte())
               this.printByte(this.current);
            else
               this.out.print(" ");
         }
      }

      return res;
   }


   @Override
   public synchronized int writeBits(byte[] bits, int start, int count) throws BitStreamException
   {
      int res = this.delegate.writeBits(bits, start, count);

      for (int i=start; i<start+(count>>3); i++)
      {
         for (int j=7; j>=0; j--)
         {
            byte bit = (byte) ((bits[i] >>> j) & 1);
            this.current <<= 1;
            this.current |= bit;
            this.lineIndex++;
            this.out.print((bit == 1) ? "1" : "0");

            if ((this.mark == true) && (i == res))
               this.out.print("w");

            if (this.width != -1)
            {
               if (this.lineIndex % this.width == 0)
               {
                  if (this.showByte())
                     this.printByte(this.current);

                  this.out.println();
                  this.lineIndex = 0;
               }
               else if ((this.lineIndex & 7) == 0)
               {
                  if (this.showByte())
                     this.printByte(this.current);
                  else
                     this.out.print(" ");
               }
            }
            else if ((this.lineIndex & 7) == 0)
            {
               if (this.showByte())
                  this.printByte(this.current);
               else
                  this.out.print(" ");
         }
         }
      }

      return res;
   }


   @Override
   public void close() throws BitStreamException
   {
      this.delegate.close();
   }


   @Override
   public long written()
   {
      return this.delegate.written();
   }
} public final class DefaultInputBitStream implements InputBitStream
{
   private final InputStream is;
   private final byte[] buffer;
   private int position;  // index of current byte (consumed if bitIndex == -1)
   private int availBits; // bits not consumed in current
   private long read;
   private boolean closed;
   private int maxPosition;
   private long current;


   public DefaultInputBitStream(InputStream is, int bufferSize)
   {
      if (is == null)
         throw new NullPointerException("Invalid null input stream parameter");

      if (bufferSize < 1024)
         throw new IllegalArgumentException("Invalid buffer size (must be at least 1024)");

      if (bufferSize > 1<<28)
         throw new IllegalArgumentException("Invalid buffer size (must be at most 268435456)");

      if ((bufferSize & 7) != 0)
         throw new IllegalArgumentException("Invalid buffer size (must be a multiple of 8)");

      this.is = is;
      this.buffer = new byte[bufferSize];
      this.availBits = 0;
      this.maxPosition = -1;
   }


   // Return 1 or 0. Trigger exception if stream is closed
   @Override
   public int readBit() throws BitStreamException
   {
      if (this.availBits == 0)
         this.pullCurrent(); // Triggers an exception if stream is closed

      this.availBits--;
      return (int) (this.current >> this.availBits) & 1;
   }


   private int readFromInputStream(int count) throws BitStreamException
   {
      if (this.isClosed() == true)
         throw new BitStreamException("Stream closed", BitStreamException.STREAM_CLOSED);

      if (count == 0)
         return 0;

      int size = -1;

      try
      {
         size = this.is.read(this.buffer, 0, count);

         if (size <= 0)
         {
            throw new BitStreamException("No more data to read in the bitstream",
                    BitStreamException.END_OF_STREAM);
         }

         return size;
      }
      catch (IOException e)
      {
         throw new BitStreamException(e.getMessage(), BitStreamException.END_OF_STREAM);
      }
      finally
      {
         this.position = 0;
         this.read += (((long) this.maxPosition+1) << 3);
         this.maxPosition = (size <= 0) ? -1 : size - 1;
      }
   }


   // Return value of 'count' next bits as a long. Trigger exception if stream is closed
   @Override
   public long readBits(int count) throws BitStreamException
   {
      if (((count-1) & -64) != 0)
         throw new IllegalArgumentException("Invalid bit count: "+count+" (must be in [1..64])");

      if (count <= this.availBits)
      {
         // Enough spots available in 'current'
         this.availBits -= count;
         return (this.current >>> this.availBits) & (-1L >>> -count);
      }

      // Not enough spots available in 'current'
      count -= this.availBits;
      final long res = this.current & ((1L << this.availBits) - 1);
      this.pullCurrent();
      this.availBits -= count;
      return (res << count) | (this.current >>> this.availBits);
   }


   @Override
   public int readBits(byte[] bits, int start, int count) throws BitStreamException
   {
      if (this.isClosed() == true)
         throw new BitStreamException("Stream closed", BitStreamException.STREAM_CLOSED);

      if ((count < 0) || ((count>>3) > bits.length-start))
         throw new IllegalArgumentException("Invalid bit count: "+count+" (must be in [1.." +
           (((long)(bits.length-start))<<3) + "])");

      if (count == 0)
         return 0;

      int remaining = count;

      // Byte aligned cursor ?
      if ((this.availBits & 7) == 0)
      {
         if (this.availBits == 0)
            this.pullCurrent();

         // Empty this.current
         while ((this.availBits > 0) && (remaining >= 8))
         {
            bits[start] = (byte) this.readBits(8);
            start++;
            remaining -= 8;
         }

         // Copy internal buffer to bits array
         while ((remaining>>3) > this.maxPosition+1-this.position)
         {
            System.arraycopy(this.buffer, this.position, bits, start, this.maxPosition+1-this.position);
            start += (this.maxPosition+1-this.position);
            remaining -= ((this.maxPosition+1-this.position)<<3);
            this.readFromInputStream(this.buffer.length);
         }

         final int r = (remaining>>6) << 3;

         if (r > 0)
         {
            System.arraycopy(this.buffer, this.position, bits, start, r);
            this.position += r;
            start += r;
            remaining -= (r<<3);
         }
      }
      else
      {
         // Not byte aligned
         final int r = 64 - this.availBits;

         while (remaining >= 64)
         {
            final long v = this.current & ((1L<<this.availBits)-1);
            this.pullCurrent();
            this.availBits -= r;
            Memory.BigEndian.writeLong64(bits, start, (v<<r) | (this.current>>>this.availBits));
            start += 8;
            remaining -= 64;
         }
      }

      // Last bytes
      while (remaining >= 8)
      {
         bits[start] = (byte) this.readBits(8);
         start++;
         remaining -= 8;
      }

      if (remaining > 0)
         bits[start] = (byte) (this.readBits(remaining)<<(8-remaining));

      return count;
   }


   // Pull 64 bits of current value from buffer.
   private void pullCurrent()
   {
      if (this.position > this.maxPosition)
         this.readFromInputStream(this.buffer.length);

      if (this.position+7 > this.maxPosition)
      {
         // End of stream: overshoot max position => adjust bit index
         int shift = (this.maxPosition - this.position) << 3;
         this.availBits = shift + 8;
         long val = 0;

         while (this.position <= this.maxPosition)
         {
            val |= (((long) (this.buffer[this.position++] & 0xFF)) << shift);
            shift -= 8;
         }

         this.current = val;
      }
      else
      {
         // Regular processing, buffer length is multiple of 8
         this.current = Memory.BigEndian.readLong64(this.buffer, this.position);
         this.availBits = 64;
         this.position += 8;
      }
   }


   @Override
   public void close()
   {
      if (this.isClosed() == true)
         return;

      this.closed = true;

      // Reset fields to force a readFromInputStream() and trigger an exception
      // on readBit() or readBits()
      this.read -= this.availBits;
      this.availBits = 0;
      this.maxPosition = -1;
   }


   // Return number of bits read so far
   @Override
   public long read()
   {
      return this.read + (this.position<<3) - this.availBits;
   }


   @Override
   public boolean hasMoreToRead()
   {
      if (this.isClosed() == true)
         return false;

      if ((this.position < this.maxPosition) || (this.availBits > 0))
         return true;

      try
      {
         this.readFromInputStream(this.buffer.length);
      }
      catch (BitStreamException e)
      {
         return false;
      }

      return true;
   }


   public boolean isClosed()
   {
      return this.closed;
   }
} public final class DefaultOutputBitStream implements OutputBitStream
{
   private final OutputStream os;
   private byte[] buffer;
   private boolean closed;
   private int position;  // index of current byte in buffer
   private int availBits; // bits not consumed in current
   private long written;
   private long current;  // cached bits


   public DefaultOutputBitStream(OutputStream os, int bufferSize)
   {
      if (os == null)
         throw new NullPointerException("Invalid null output stream parameter");

      if (bufferSize < 1024)
         throw new IllegalArgumentException("Invalid buffer size (must be at least 1024)");

      if (bufferSize > 1<<28)
         throw new IllegalArgumentException("Invalid buffer size (must be at most 268435456)");

      if ((bufferSize & 7) != 0)
         throw new IllegalArgumentException("Invalid buffer size (must be a multiple of 8)");

      this.os = os;
      this.buffer = new byte[bufferSize];
      this.availBits = 64;
   }


   // Write least significant bit of the input integer. Trigger exception if stream is closed
   @Override
   public void writeBit(int bit)
   {
      if (this.availBits <= 1) // availBits = 0 if stream is closed => force pushCurrent()
      {
         this.current |= (bit & 1);
         this.pushCurrent();
      }
      else
      {
         this.availBits--;
         this.current |= ((long) (bit & 1) << this.availBits);
      }
   }


   // Write 'count' (in [1..64]) bits. Trigger exception if stream is closed
   @Override
   public int writeBits(long value, int count)
   {
      if (count == 0)
         return 0;

      if (count > 64)
         throw new IllegalArgumentException("Invalid bit count: "+count+" (must be in [1..64])");

      this.current |= ((value << (64 - count)) >>> (64 - this.availBits));
      int remaining = count;

      if (count >= this.availBits) {
         remaining -= this.availBits;
         pushCurrent();

         if (remaining != 0)
            this.current = value << (64 - remaining);
      }

      this.availBits -= remaining;
      return count;
   }


   @Override
   public int writeBits(byte[] bits, int start, int count)
   {
      if (this.isClosed() == true)
         throw new BitStreamException("Stream closed", BitStreamException.STREAM_CLOSED);

      if ((count>>3) > bits.length-start)
         throw new IllegalArgumentException("Invalid length: "+count+" (must be in [1.." +
            (((long)(bits.length-start))<<3) + "])");

      int remaining = count;

      // Byte aligned cursor ?
      if ((this.availBits & 7) == 0)
      {
         // Fill up this.current
         while ((this.availBits != 64) && (remaining >= 8))
         {
            this.writeBits((long) bits[start], 8);
            start++;
            remaining -= 8;
         }

         // Copy bits array to internal buffer
         final int maxPos = this.buffer.length - 8;
         
         while ((remaining>>3) >= maxPos-this.position)
         {
            System.arraycopy(bits, start, this.buffer, this.position, maxPos-this.position);
            start += (maxPos-this.position);
            remaining -= ((maxPos-this.position)<<3);
            this.position = maxPos;
            this.flush();
         }

         final int r = (remaining>>6) << 3;

         if (r > 0)
         {
            System.arraycopy(bits, start, this.buffer, this.position, r);
            this.position += r;
            start += r;
            remaining -= (r<<3);
         }
      }
      else
      {
         // Not byte aligned
         if (remaining >= 64)
         {
            final int r = 64 - this.availBits;

            while (remaining >= 64)
            {
               final long value = Memory.BigEndian.readLong64(bits, start);
               this.current |= (value >>> r);
               this.pushCurrent();
               this.current = (value << -r);
               start += 8;
               remaining -= 64;
            }

            this.availBits -= r;
         }
      }

      // Last bytes
      while (remaining >= 8)
      {
         this.writeBits((long) (bits[start]&0xFF), 8);
         start++;
         remaining -= 8;
      }

      if (remaining > 0)
         this.writeBits((long) (bits[start]>>>(8-remaining)), remaining);

      return count;
   }


   // Push 64 bits of current value into buffer.
   private void pushCurrent()
   {
      Memory.BigEndian.writeLong64(this.buffer, this.position, this.current);
      this.availBits = 64;
      this.current = 0;
      this.position += 8;

      if (this.position >= this.buffer.length - 8)
         this.flush();
   }


   // Write buffer to underlying stream
   private void flush() throws BitStreamException
   {
      if (this.isClosed() == true)
         throw new BitStreamException("Stream closed", BitStreamException.STREAM_CLOSED);

      try
      {
         if (this.position > 0)
         {
            this.os.write(this.buffer, 0, this.position);
            this.written += (this.position << 3);
            this.position = 0;
         }
      }
      catch (IOException e)
      {
         throw new BitStreamException(e.getMessage(), BitStreamException.INPUT_OUTPUT);
      }
   }


   @Override
   public void close()
   {
      if (this.isClosed() == true)
         return;

      final int savedBitIndex = this.availBits;
      final int savedPosition = this.position;
      final long savedCurrent = this.current;

      try
      {
         // Push last bytes (the very last byte may be incomplete)
         for (int shift=56; this.availBits<64; shift-=8)
         {
            this.buffer[this.position++] = (byte) (this.current>>shift);
            this.availBits += 8;
         }

         this.written -= (this.availBits-64);
         this.availBits = 64;
         this.flush();
      }
      catch (BitStreamException e)
      {
         // Revert fields to allow subsequent attempts in case of transient failure
         this.position = savedPosition;
         this.availBits = savedBitIndex;
         this.current = savedCurrent;
         throw e;
      }

      try
      {
         this.os.flush();
      }
      catch (IOException e)
      {
         throw new BitStreamException(e, BitStreamException.INPUT_OUTPUT);
      }

      this.closed = true;
      this.position = 0;
      this.availBits = 0;
      this.written -= 64; // adjust because this.availBits = 0

      // Reset fields to force a flush() and trigger an exception
      // on writeBit() or writeBits()
      this.buffer = new byte[8];
   }


   // Return number of bits written so far
   @Override
   public long written()
   {
      // Number of bits flushed + bytes written in memory + bits written in memory
      return this.written + (this.position<<3) + (64-this.availBits);
   }


   public boolean isClosed()
   {
      return this.closed;
   }
} public class ANSRangeDecoder implements EntropyDecoder
{
   private static final int ANS_TOP = 1 << 15; // max possible for ANS_TOP=1<23
   private static final int DEFAULT_ANS0_CHUNK_SIZE = 1 << 15; // 32 KB by default
   private static final int DEFAULT_LOG_RANGE = 12;
   private static final int MIN_CHUNK_SIZE = 1024;
   private static final int MAX_CHUNK_SIZE = 1 << 27; // 8*MAX_CHUNK_SIZE must not overflow

   private final InputBitStream bitstream;
   private final int[][] freqs;
   private final byte[][] f2s; // mapping frequency -> symbol
   private final Symbol[][] symbols;
   private byte[] buffer;
   private final int chunkSize;
   private final int order;
   private int logRange;
   private boolean isBsVersion1;


   public ANSRangeDecoder(InputBitStream bs)
   {
      this(bs, 0, DEFAULT_ANS0_CHUNK_SIZE);
   }


   public ANSRangeDecoder(InputBitStream bs, int order)
   {
      this(bs, order, DEFAULT_ANS0_CHUNK_SIZE);
   }


   // The chunk size indicates how many bytes are encoded (per block) before
   // resetting the frequency stats.
   public ANSRangeDecoder(InputBitStream bs, int order, int chunkSize)
   {
      if (bs == null)
         throw new NullPointerException("ANS Codec: Invalid null bitstream parameter");

      if ((order != 0) && (order != 1))
         throw new IllegalArgumentException("ANS Codec: The order must be 0 or 1");

      if (chunkSize < MIN_CHUNK_SIZE)
         throw new IllegalArgumentException("ANS Codec: The chunk size must be at least "+MIN_CHUNK_SIZE);

      if (chunkSize > MAX_CHUNK_SIZE)
         throw new IllegalArgumentException("ANS Codec: The chunk size must be at most "+MAX_CHUNK_SIZE);

      this.bitstream = bs;
      this.chunkSize = Math.min(chunkSize << (8*order), MAX_CHUNK_SIZE);
      this.order = order;
      final int dim = 255*order + 1;
      this.freqs = new int[dim][256];
      this.f2s = new byte[dim][256];
      this.symbols = new Symbol[dim][256];
      this.buffer = new byte[0];
      this.logRange = DEFAULT_LOG_RANGE;
      this.isBsVersion1 = false; // old encoding

      for (int i=0; i<dim; i++)
      {
         this.freqs[i] = new int[256];
         this.f2s[i] = new byte[0];
         this.symbols[i] = new Symbol[256];
      }
   }

   public ANSRangeDecoder(InputBitStream bs, int order, Map<String, Object> ctx)
   {
      if (bs == null)
         throw new NullPointerException("ANS Codec: Invalid null bitstream parameter");

      if ((order != 0) && (order != 1))
         throw new IllegalArgumentException("ANS Codec: The order must be 0 or 1");

      final int bsVersion = (ctx == null) ? -1 : (Integer) ctx.getOrDefault("bsVersion", -1);
      this.bitstream = bs;
      this.chunkSize = Math.min(DEFAULT_ANS0_CHUNK_SIZE << (8*order), MAX_CHUNK_SIZE);
      this.order = order;
      final int dim = 255*order + 1;
      this.freqs = new int[dim][256];
      this.f2s = new byte[dim][256];
      this.symbols = new Symbol[dim][256];
      this.buffer = new byte[0];
      this.logRange = DEFAULT_LOG_RANGE;
      this.isBsVersion1 = bsVersion == 1; // old encoding

      for (int i=0; i<dim; i++)
      {
         this.freqs[i] = new int[256];
         this.f2s[i] = new byte[0];
         this.symbols[i] = new Symbol[256];
      }
   }

   
   @Override
   public int decode(byte[] block, int blkptr, int count)
   {
      if ((block == null) || (blkptr+count > block.length) || (blkptr < 0) || (count < 0))
         return -1;

      if (count == 0)
         return 0;

      final int end = blkptr + count;
      int sizeChunk = this.chunkSize;
      int startChunk = blkptr;
      final int endk = 255*this.order + 1;

      for (int k=0; k<endk; k++)
      {
         Symbol[] syms = this.symbols[k];

         for (int i=0; i<256; i++)
            syms[i] = new Symbol();
      }

      final int[] alphabet = new int[256];

      while (startChunk < end)
      {
         final int endChunk = Math.min(startChunk+sizeChunk, end);
         final int alphabetSize = this.decodeHeader(this.freqs, alphabet);

         if (alphabetSize == 0)
            return startChunk - blkptr;

         if ((this.order == 0) && (alphabetSize == 1))
         {
            // Shortcut for chunks with only one symbol
            for (int i=startChunk; i<endChunk; i++)
               block[i] = (byte) alphabet[0];
         }
         else
         {
            if (this.isBsVersion1)
               this.decodeChunkV1(block, startChunk, endChunk);
            else
               this.decodeChunkV2(block, startChunk, endChunk);
         }

         startChunk = endChunk;
      }

      return count;
   }


   protected void decodeChunkV1(byte[] block, final int start, final int end)
   {
      // Read chunk size
      final int sz = EntropyUtils.readVarInt(this.bitstream) & (MAX_CHUNK_SIZE-1);

      // Read initial ANS state
      int st0 = (int) this.bitstream.readBits(32);
      int st1 = (this.order == 0) ? (int) this.bitstream.readBits(32) : 0;

      if (sz != 0)
      {
         // Add some padding
         if (this.buffer.length < sz)
            this.buffer = new byte[sz+(sz>>3)];

         this.bitstream.readBits(this.buffer, 0, 8*sz);
      }

      int n = 0;
      final int mask = (1<<this.logRange) - 1;

      if (this.order == 0)
      {
         final byte[] freq2sym = this.f2s[0];
         final Symbol[] symb = this.symbols[0];
         final int end2 = (end & -2) - 1;

         for (int i=start; i<end2; i+=2)
         {
            final byte cur1 = freq2sym[st1&mask];
            block[i] = cur1;
            final byte cur0 = freq2sym[st0&mask];
            block[i+1] = cur0;
            final Symbol sym1 = symb[cur1&0xFF];
            final Symbol sym0 = symb[cur0&0xFF];

            // Compute next ANS state
            // D(x) = (s, q_s (x/M) + mod(x,M) - b_s) where s is such b_s <= x mod M < b_{s+1}
            st1 = sym1.freq * (st1>>>this.logRange) + (st1&mask) - sym1.cumFreq;
            st0 = sym0.freq * (st0>>>this.logRange) + (st0&mask) - sym0.cumFreq;

            // Normalize
            while (st1 < ANS_TOP)
            {
               st1 = (st1<<8) | (this.buffer[n] & 0xFF);
               st1 = (st1<<8) | (this.buffer[n+1] & 0xFF);
               n += 2;
            }

            while (st0 < ANS_TOP)
            {
               st0 = (st0<<8) | (this.buffer[n] & 0xFF);
               st0 = (st0<<8) | (this.buffer[n+1] & 0xFF);
               n += 2;
            }
         }

         if ((end & 1) != 0)
            block[end - 1] = this.buffer[sz-1];
      }
      else
      {
         int prv = 0;

         for (int i=start; i<end; i++)
         {
            final int cur = this.f2s[prv][st0&mask] & 0xFF;
            block[i] = (byte) cur;
            final Symbol sym = this.symbols[prv][cur];

            // Compute next ANS state
            // D(x) = (s, q_s (x/M) + mod(x,M) - b_s) where s is such b_s <= x mod M < b_{s+1}
            st0 = sym.freq * (st0>>>this.logRange) + (st0&mask) - sym.cumFreq;

            // Normalize
            while (st0 < ANS_TOP)
            {
               st0 = (st0<<8) | (this.buffer[n] & 0xFF);
               st0 = (st0<<8) | (this.buffer[n+1] & 0xFF);
               n += 2;
            }

            prv = cur;
         }
      }
   }
   
   
   private int decodeSymbol(int[] idx, int st, Symbol sym, final int mask)
   {
      // Compute next ANS state
      // D(x) = (s, q_s (x/M) + mod(x,M) - b_s) where s is such b_s <= x mod M < b_{s+1}
      st = sym.freq * (st>>>this.logRange) + (st&mask) - sym.cumFreq;

      // Normalize
      if (st < ANS_TOP)
      {
         st = (st<<8) | (this.buffer[idx[0]] & 0xFF);
         st = (st<<8) | (this.buffer[idx[0]+1] & 0xFF);
         idx[0] += 2;
      }   
      
      return st;
   }

   
   protected void decodeChunkV2(byte[] block, final int start, final int end)
   {
      // Read chunk size
      final int sz = EntropyUtils.readVarInt(this.bitstream) & (MAX_CHUNK_SIZE-1);

      // Read initial ANS states
      int st0 = (int) this.bitstream.readBits(32);
      int st1 = (int) this.bitstream.readBits(32);
      int st2 = (int) this.bitstream.readBits(32);
      int st3 = (int) this.bitstream.readBits(32);

      // Read encoded data from bitstream
      if (sz != 0)
      {
         // Add some padding
         if (this.buffer.length < sz)
            this.buffer = new byte[sz+(sz>>3)];

         this.bitstream.readBits(this.buffer, 0, 8*sz);
      }

      int n = 0;      
      final int mask = (1<<this.logRange) - 1;
      final int end4 = start + ((end-start) & -4);
      final int[] idx = new int[] { n } ;

      if (this.order == 0) 
      {
         final byte[] freq2sym = this.f2s[0];
         final Symbol[] symb = this.symbols[0];

         for (int i=start; i<end4; i+=4) 
         {
            final int cur3 = freq2sym[st3 & mask] & 0xFF;
            block[i] = (byte) cur3;
            st3 = decodeSymbol(idx, st3, symb[cur3], mask);
            final int cur2 = freq2sym[st2 & mask] & 0xFF;
            block[i+1] = (byte) cur2;
            st2 = decodeSymbol(idx, st2, symb[cur2], mask);
            final int cur1 = freq2sym[st1 & mask] & 0xFF;
            block[i+2] = (byte) cur1;
            st1 = decodeSymbol(idx, st1, symb[cur1], mask);
            final int cur0 = freq2sym[st0 & mask] & 0xFF;
            block[i+3] = (byte) cur0;
            st0 = decodeSymbol(idx, st0, symb[cur0], mask);
         }
      }
      else 
      {
         final int quarter = (end4-start) >> 2;
         int i0 = start;
         int i1 = start + 1*quarter;
         int i2 = start + 2*quarter;
         int i3 = start + 3*quarter;
         int prv0 = 0, prv1 = 0, prv2 = 0, prv3 = 0;

         for ( ; i0 < start+quarter; i0++, i1++, i2++, i3++) 
         {
            final int cur3 = this.f2s[prv3][st3&mask] & 0xFF;
            block[i3] = (byte) cur3;
            st3 = decodeSymbol(idx, st3, this.symbols[prv3][cur3], mask);
            final int cur2 = this.f2s[prv2][st2&mask] & 0xFF;
            block[i2] = (byte) cur2;
            st2 = decodeSymbol(idx, st2, this.symbols[prv2][cur2], mask);
            final int cur1 = this.f2s[prv1][st1&mask] & 0xFF;
            block[i1] = (byte) cur1;
            st1 = decodeSymbol(idx, st1, this.symbols[prv1][cur1], mask);
            final int cur0 = this.f2s[prv0][st0&mask] & 0xFF;
            block[i0] = (byte) cur0;
            st0 = decodeSymbol(idx, st0, this.symbols[prv0][cur0], mask);
            prv3 = cur3;
            prv2 = cur2;
            prv1 = cur1;
            prv0 = cur0;
         }
      }

      n = idx[0];
      
      for (int i=end4; i<end; i++)
         block[i] = this.buffer[n++];
   }

   
   // Decode alphabet and frequencies
   protected int decodeHeader(int[][] frequencies, int[] alphabet)
   {
      this.logRange = (int) (8 + this.bitstream.readBits(3));

      if ((this.logRange < 8) || (this.logRange > 16))
         throw new BitStreamException("Invalid bitstream: range = "+this.logRange+
            " (must be in [8..16])", BitStreamException.INVALID_STREAM);

      int res = 0;
      final int dim = 255*this.order + 1;
      final int scale = 1 << this.logRange;

      for (int k=0; k<dim; k++)
      {
         final int[] f = frequencies[k];
         int alphabetSize = EntropyUtils.decodeAlphabet(this.bitstream, alphabet);

         if (alphabetSize == 0)
            continue;

         if (alphabetSize != f.length)
         {
            for (int i=f.length-1; i>=0; i--)
               f[i] = 0;
         }

         if (this.f2s[k].length < scale)
            this.f2s[k] = new byte[scale];

         final int chkSize = (alphabetSize >= 64) ? 8 : 6;
         int sum = 0;
         int llr = 3;

         while (1<<llr <= this.logRange)
            llr++;

         // Decode all frequencies (but the first one) by chunks
         for (int i=1; i<alphabetSize; i+=chkSize)
         {
            // Read frequencies size for current chunk
            final int logMax = (int) this.bitstream.readBits(llr);

            if (1<<logMax > scale)
            {
               throw new BitStreamException("Invalid bitstream: incorrect frequency size " +
                       logMax + " in ANS range decoder", BitStreamException.INVALID_STREAM);
            }

            final int endj = (i+chkSize < alphabetSize) ? i + chkSize : alphabetSize;

            // Read frequencies
            for (int j=i; j<endj; j++)
            {
               final int freq = (logMax == 0) ? 1 : (int) (1+this.bitstream.readBits(logMax));

               if ((freq <= 0) || (freq >= scale))
               {
                  throw new BitStreamException("Invalid bitstream: incorrect frequency " +
                          freq + " for symbol '" + alphabet[j] + "' in ANS range decoder",
                          BitStreamException.INVALID_STREAM);
               }

               f[alphabet[j]] = freq;
               sum += freq;
            }
         }

         // Infer first frequency
         if (scale <= sum)
         {
            throw new BitStreamException("Invalid bitstream: incorrect frequency " +
                    f[alphabet[0]] + " for symbol '" + alphabet[0] +
                    "' in ANS range decoder", BitStreamException.INVALID_STREAM);
         }

         f[alphabet[0]] = scale - sum;
         sum = 0;
         final Symbol[] symb = this.symbols[k];
         final byte[] freq2sym = this.f2s[k];

         // Create reverse mapping
         for (int i=0; i<f.length; i++)
         {
            if (f[i] == 0)
               continue;

            for (int j=f[i]-1; j>=0; j--)
               freq2sym[sum+j] = (byte) i;

            symb[i].reset(sum, f[i], this.logRange);
            sum += f[i];
         }

         res += alphabetSize;
      }

      return res;
   }


   @Override
   public InputBitStream getBitStream()
   {
      return this.bitstream;
   }


   @Override
   public void dispose()
   {
   }


   static class Symbol
   {
      int cumFreq;
      int freq;


      public void reset(int cumFreq, int freq, int logRange)
      {
         this.cumFreq = cumFreq;
         this.freq = (freq >= 1<<logRange) ? (1<<logRange) - 1 : freq; // Mirror encoder
      }
   }
} public class ANSRangeEncoder implements EntropyEncoder
{
   private static final int ANS_TOP = 1 << 15; // max possible for ANS_TOP=1<<23
   private static final int DEFAULT_ANS0_CHUNK_SIZE = 1 << 15; // 32 KB by default
   private static final int DEFAULT_LOG_RANGE = 12;
   private static final int MIN_CHUNK_SIZE = 1024;
   private static final int MAX_CHUNK_SIZE = 1 << 27; // 8*MAX_CHUNK_SIZE must not overflow

   private final OutputBitStream bitstream;
   private final int[][] freqs;
   private final Symbol[][] symbols;
   private byte[] buffer;
   private final int chunkSize;
   private final int order;
   private int logRange;


   public ANSRangeEncoder(OutputBitStream bs)
   {
      this(bs, 0, DEFAULT_ANS0_CHUNK_SIZE, DEFAULT_LOG_RANGE);
   }


   public ANSRangeEncoder(OutputBitStream bs, int order)
   {
      this(bs, order, DEFAULT_ANS0_CHUNK_SIZE, DEFAULT_LOG_RANGE);
   }


   // The chunk size indicates how many bytes are encoded (per block) before
   // resetting the frequency stats.
   public ANSRangeEncoder(OutputBitStream bs, int order, int chunkSize, int logRange)
   {
      if (bs == null)
         throw new NullPointerException("ANS Codec: Invalid null bitstream parameter");

      if ((order != 0) && (order != 1))
         throw new IllegalArgumentException("ANS Codec: The order must be 0 or 1");

      if (chunkSize < MIN_CHUNK_SIZE)
         throw new IllegalArgumentException("ANS Codec: The chunk size must be at least "+MIN_CHUNK_SIZE);

      if (chunkSize > MAX_CHUNK_SIZE)
         throw new IllegalArgumentException("ANS Codec: The chunk size must be at most "+MAX_CHUNK_SIZE);

      if ((logRange < 8) || (logRange > 16))
         throw new IllegalArgumentException("ANS Codec: Invalid range: "+logRange+" (must be in [8..16])");

      this.bitstream = bs;
      this.order = order;
      final int dim = 255*order + 1;
      this.freqs = new int[dim][257]; // freqs[x][256] = total(freqs[x][0..255])
      this.symbols = new Symbol[dim][256];
      this.buffer = new byte[0];
      this.logRange = logRange;
      this.chunkSize = Math.min(chunkSize << (8*order), MAX_CHUNK_SIZE);

      for (int i=0; i<dim; i++)
      {
         this.freqs[i] = new int[257];
         this.symbols[i] = new Symbol[256];
      }
   }


   public ANSRangeEncoder(OutputBitStream bs, int order, Map<String, Object> ctx)
   {
      if (bs == null)
         throw new NullPointerException("ANS Codec: Invalid null bitstream parameter");

      if ((order != 0) && (order != 1))
         throw new IllegalArgumentException("ANS Codec: The order must be 0 or 1");

      this.bitstream = bs;
      this.order = order;
      final int dim = 255*order + 1;
      this.freqs = new int[dim][257]; // freqs[x][256] = total(freqs[x][0..255])
      this.symbols = new Symbol[dim][256];
      this.buffer = new byte[0];
      this.logRange = DEFAULT_LOG_RANGE;
      this.chunkSize = Math.min(DEFAULT_ANS0_CHUNK_SIZE << (8*order), MAX_CHUNK_SIZE);

      for (int i=0; i<dim; i++)
      {
         this.freqs[i] = new int[257];
         this.symbols[i] = new Symbol[256];
      }
   }

      
   // Compute cumulated frequencies and encode header
   private int updateFrequencies(int[][] frequencies, int lr)
   {
      int res = 0;
      final int endk = 255*this.order + 1;
      this.bitstream.writeBits(lr-8, 3); // logRange
      final int[] alphabet = new int[256];

      for (int k=0; k<endk; k++)
      {
         final int[] f = frequencies[k];
         final Symbol[] symb = this.symbols[k];
         final int alphabetSize = EntropyUtils.normalizeFrequencies(f, alphabet, f[256], 1<<lr);

         if (alphabetSize > 0)
         {
            int sum = 0;

            for (int i=0; i<256; i++)
            {
               if (f[i] == 0)
                  continue;

               symb[i].reset(sum, f[i], lr);
               sum += f[i];
            }
         }

         this.encodeHeader(alphabetSize, alphabet, f, lr);
         res += alphabetSize;
      }

      return res;
   }


   // Encode alphabet and frequencies
   protected boolean encodeHeader(int alphabetSize, int[] alphabet, int[] frequencies, int lr)
   {
      final int encoded = EntropyUtils.encodeAlphabet(this.bitstream, alphabet, alphabetSize);

      if (encoded < 0)
         return false;

      if (encoded == 0)
         return true;

      final int chkSize = (alphabetSize >= 64) ? 8 : 6;
      int llr = 3;

      while (1<<llr <= lr)
         llr++;

      // Encode all frequencies (but the first one) by chunks
      for (int i=1; i<alphabetSize; i+=chkSize)
      {
         int max = frequencies[alphabet[i]] - 1;
         int logMax = 0;
         final int endj = (i+chkSize < alphabetSize) ? i+chkSize : alphabetSize;

         // Search for max frequency log size in next chunk
         for (int j=i+1; j<endj; j++)
         {
            if (frequencies[alphabet[j]]-1 > max)
               max = frequencies[alphabet[j]]-1;
         }

         while (1<<logMax <= max)
            logMax++;

         this.bitstream.writeBits(logMax, llr);

         if (logMax == 0) // all frequencies equal one in this chunk
            continue;

         // Write frequencies
         for (int j=i; j<endj; j++)
            this.bitstream.writeBits(frequencies[alphabet[j]]-1, logMax);
      }

      return true;
   }


   // Dynamically compute the frequencies for every chunk of data in the block
   @Override
   public int encode(byte[] block, int blkptr, int count)
   {
      if ((block == null) || (blkptr+count > block.length) || (blkptr < 0) || (count < 0))
         return -1;

      if (count == 0)
         return 0;

      final int end = blkptr + count;
      int sizeChunk = this.chunkSize;
      int startChunk = blkptr;
      final int endk = 255*this.order + 1;

      for (int k=0; k<endk; k++)
      {
         Symbol[] syms = this.symbols[k];

         for (int i=0; i<256; i++)
            syms[i] = new Symbol();
      }

      final int size = Math.max(Math.min(sizeChunk+(sizeChunk>>3), 2*count), 65536);

      // Add some padding
      if (this.buffer.length < size)
         this.buffer = new byte[size];

      while (startChunk < end)
      {
         final int endChunk = Math.min(startChunk+sizeChunk, end);
         int lr = this.logRange;

         // Lower log range if the size of the data chunk is small
         while ((lr > 8) && (1<<lr > endChunk-startChunk))
            lr--;

         final int alphabetSize = this.rebuildStatistics(block, startChunk, endChunk, lr);

         // Skip chunk if only one symbol
         if ((alphabetSize <= 1) && (this.order == 0))
         {
            startChunk = endChunk;
            continue;
         }

         this.encodeChunk(block, startChunk, endChunk);
         startChunk = endChunk;
      }

      return count;
   }

   private int encodeSymbol(int[] idx, int st, Symbol sym)
   {
      if (st >= sym.xMax) 
      {
         this.buffer[idx[0]--] = (byte) st;
         st >>= 8;
         this.buffer[idx[0]--] = (byte) (st);
         st >>= 8;
      }

      // Compute next ANS state
      // C(s,x) = M floor(x/q_s) + mod(x,q_s) + b_s where b_s = q_0 + ... + q_{s-1}
      // st = ((st / freq) << lr) + (st % freq) + cumFreq[prv];
      final int q = (int)((st*sym.invFreq) >> sym.invShift);
      return st + sym.bias + q*sym.cmplFreq;
   }
   

   private void encodeChunk(byte[] block, int start, int end)
   {
      int st0 = ANS_TOP;
      int st1 = ANS_TOP;
      int st2 = ANS_TOP;
      int st3 = ANS_TOP;
      int n = this.buffer.length - 1;
      final int end4 = start + ((end-start) & -4);

      for (int i=end-1; i>=end4; i--)
         this.buffer[n--] = block[i];
      
      final int[] idx = new int[] { n };

      if (this.order == 0) 
      {
         final Symbol[] symb = this.symbols[0];

         for (int i=end4-1; i>start; i-=4) 
         {
            st0 = encodeSymbol(idx, st0, symb[block[i] & 0xFF]);
            st1 = encodeSymbol(idx, st1, symb[block[i-1] & 0xFF]);
            st2 = encodeSymbol(idx, st2, symb[block[i-2] & 0xFF]);
            st3 = encodeSymbol(idx, st3, symb[block[i-3] & 0xFF]);
         }
      }
      else 
      {  // order 1
         final int quarter = (end4-start) >> 2;
         int i0 = start + 1*quarter - 2;
         int i1 = start + 2*quarter - 2;
         int i2 = start + 3*quarter - 2;
         int i3 = end4 - 2;
         int prv0 = block[i0+1] & 0xFF;
         int prv1 = block[i1+1] & 0xFF;
         int prv2 = block[i2+1] & 0xFF;
         int prv3 = block[i3+1] & 0xFF;

         for ( ; i0>=start; i0--, i1--, i2--, i3--) 
         {
            final int cur0 = block[i0] & 0xFF;
            st0 = encodeSymbol(idx, st0, this.symbols[cur0][prv0]);
            final int cur1 = block[i1] & 0xFF;
            st1 = encodeSymbol(idx, st1, this.symbols[cur1][prv1]);
            final int cur2 = block[i2] & 0xFF;
            st2 = encodeSymbol(idx, st2, this.symbols[cur2][prv2]);
            final int cur3 = block[i3] & 0xFF;
            st3 = encodeSymbol(idx, st3, this.symbols[cur3][prv3]);
            prv0 = cur0;
            prv1 = cur1;
            prv2 = cur2;
            prv3 = cur3;
         }

         // Last symbols
         st0 = encodeSymbol(idx, st0, this.symbols[0][prv0]);
         st1 = encodeSymbol(idx, st1, this.symbols[0][prv1]);
         st2 = encodeSymbol(idx, st2, this.symbols[0][prv2]);
         st3 = encodeSymbol(idx, st3, this.symbols[0][prv3]);
      }

      n = idx[0];
      n++;

      // Write chunk size
      EntropyUtils.writeVarInt(this.bitstream, this.buffer.length-n);

      // Write final ANS state
      this.bitstream.writeBits(st0, 32);
      this.bitstream.writeBits(st1, 32);
      this.bitstream.writeBits(st2, 32);
      this.bitstream.writeBits(st3, 32);

      // Write encoded data to bitstream
      if (this.buffer.length != n)
         this.bitstream.writeBits(this.buffer, n, 8*(this.buffer.length-n));
   }


   // Compute chunk frequencies, cumulated frequencies and encode chunk header
   private int rebuildStatistics(byte[] block, int start, int end, int lr)
   {
      final int dim = 255*this.order + 1;
      
      for (int i=0; i<dim; i++)
      {
         final int[] f = this.freqs[i];
         
         for (int j=0; j<f.length; j++)
            f[j] = 0;
      }
      
      if (this.order == 0)
      {
         Global.computeHistogramOrder0(block, start, end, this.freqs[0], true);
      }
      else 
      {
         final int quarter = (end-start) >> 2;
         Global.computeHistogramOrder1(block, start+0*quarter, start+1*quarter, this.freqs, true);
         Global.computeHistogramOrder1(block, start+1*quarter, start+2*quarter, this.freqs, true);
         Global.computeHistogramOrder1(block, start+2*quarter, start+3*quarter, this.freqs, true);
         Global.computeHistogramOrder1(block, start+3*quarter, start+4*quarter, this.freqs, true);
      }
    
      return this.updateFrequencies(this.freqs, lr);
   }


   @Override
   public OutputBitStream getBitStream()
   {
      return this.bitstream;
   }


   @Override
   public void dispose()
   {
   }



   static class Symbol
   {
      int xMax; // (Exclusive) upper bound of pre-normalization interval
      int bias; // Bias
      int cmplFreq; // Complement of frequency: (1 << scale_bits) - freq
      int invShift; // Reciprocal shift
      long invFreq; // Fixed-point reciprocal frequency


      public void reset(int cumFreq, int freq, int logRange)
      {
         // Make sure xMax is a positive int32
         if (freq >= 1<<logRange)
            freq = (1<<logRange) - 1;

         this.xMax = ((ANS_TOP>>>logRange) << 16) * freq;
         this.cmplFreq = (1<<logRange) - freq;

         if (freq < 2)
         {
            this.invFreq = 0xFFFFFFFFL;
            this.invShift = 32;
            this.bias = cumFreq + (1<<logRange) - 1;
         }
         else
         {
            int shift = 0;

            while (freq > (1<<shift))
                shift++;

            // Alverson, "Integer Division using reciprocals"
            this.invFreq = (((1L<<(shift+31))+freq-1) / freq) & 0xFFFFFFFFL;
            this.invShift = 32 + shift - 1;
            this.bias = cumFreq;
         }
      }
   }
} public class CMPredictor implements Predictor
{
   private static final int FAST_RATE   = 2;
   private static final int MEDIUM_RATE = 4;
   private static final int SLOW_RATE   = 6;
   private static final int PSCALE      = 65536;

   private int c1;
   private int c2;
   private int ctx;
   private int idx;
   private int runMask;
   private final int[][] counter1;
   private final int[][] counter2;


   public CMPredictor()
   {
      this.ctx = 1;
      this.idx = 0;
      this.counter1 = new int[256][257];
      this.counter2 = new int[512][17];

      for (int i=0; i<256; i++)
      {
         Arrays.fill(this.counter1[i], PSCALE>>1);

         for (int j=0; j<16; j++)
         {
            this.counter2[i+i][j]   = j << 12;
            this.counter2[i+i+1][j] = j << 12;
         }

         this.counter2[i+i][16]   = 15 << 12;
         this.counter2[i+i+1][16] = 15 << 12;
      }
   }


   // Update the probability model
   @Override
   public void update(int bit)
   {
      final int[] counter1_ = this.counter1[this.ctx];
      final int[] counter2_ = this.counter2[this.ctx|this.runMask];
      this.ctx <<= 1;

      if (bit == 0)
      {
         counter1_[256]      -= (counter1_[256]      >> FAST_RATE);
         counter1_[this.c1]  -= (counter1_[this.c1]  >> MEDIUM_RATE);
         counter2_[this.idx] -= (counter2_[this.idx] >> SLOW_RATE);
         counter2_[this.idx+1] -= (counter2_[this.idx+1] >> SLOW_RATE);
      }
      else
      {
         counter1_[256]      -= ((counter1_[256]-PSCALE+16)      >> FAST_RATE);
         counter1_[this.c1]  -= ((counter1_[this.c1]-PSCALE+16)  >> MEDIUM_RATE);
         counter2_[this.idx] -= ((counter2_[this.idx]-PSCALE+16) >> SLOW_RATE);
         counter2_[this.idx+1] -= ((counter2_[this.idx+1]-PSCALE+16) >> SLOW_RATE);
         this.ctx++;
      }

      if (this.ctx > 255)
      {
         this.c2 = this.c1;
         this.c1 = this.ctx & 0xFF;
         this.ctx = 1;
         this.runMask = (this.c1 == this.c2) ? 0x100 : 0;
      }
   }


   // Return the split value representing the probability of 1 in the [0..4095] range.
   @Override
   public int get()
   {
      final int[] pc1 = this.counter1[this.ctx];
      final int p = (13*(pc1[256]+pc1[this.c1])+6*pc1[this.c2]) >> 5;
      this.idx = p >>> 12;
      final int[] pc2 = this.counter2[this.ctx|this.runMask];
      final int x1 = pc2[this.idx];
      final int x2 = pc2[this.idx+1];
      final int ssep = x1 + (((x2-x1)*(p&4095)) >> 12);
      return (p + 3*ssep + 32) >>> 6; // rescale to [0..4095]
   }
} public final class ExpGolombDecoder implements EntropyDecoder
{
   private final boolean signed;
   private final InputBitStream bitstream;


   public ExpGolombDecoder(InputBitStream bitstream, boolean signed)
   {
      if (bitstream == null)
         throw new NullPointerException("ExpGolomb codec: Invalid null bitstream parameter");

      this.signed = signed;
      this.bitstream = bitstream;
   }


   public boolean isSigned()
   {
      return this.signed;
   }


   public byte decodeByte()
   {
      if (this.bitstream.readBit() == 1)
         return 0;

      int log2 = 1;

      while (this.bitstream.readBit() == 0)
         log2++;

      if (this.signed == true)
      {
         // Decode signed: read value + sign
         long res = this.bitstream.readBits(log2+1);
         final long sgn = res & 1;
         res = (res >>> 1) + (1 << log2) - 1;
         return (byte) ((res - sgn) ^ -sgn); // res or -res
      }

      // Decode unsigned
      return (byte) ((1 << log2) - 1 + this.bitstream.readBits(log2));
   }


   @Override
   public InputBitStream getBitStream()
   {
      return this.bitstream;
   }


   @Override
   public int decode(byte[] block, int blkptr, int count)
   {
      if ((block == null) || (blkptr+count > block.length) || (blkptr < 0) || (count < 0))
         return -1;

      final int end = blkptr + count;

      for (int i=blkptr; i<end; i++)
         block[i] = this.decodeByte();

      return count;
   }


   @Override
   public void dispose()
   {
   }
} public final class ExpGolombEncoder implements EntropyEncoder
{
    private static final int[][] CACHE = new int[][]
    {
       // Unsigned
       new int[]
       {
          513, 1538, 1539, 2564, 2565, 2566, 2567, 3592, 3593, 3594, 3595, 3596, 3597, 3598, 3599, 4624,
         4625, 4626, 4627, 4628, 4629, 4630, 4631, 4632, 4633, 4634, 4635, 4636, 4637, 4638, 4639, 5664,
         5665, 5666, 5667, 5668, 5669, 5670, 5671, 5672, 5673, 5674, 5675, 5676, 5677, 5678, 5679, 5680,
         5681, 5682, 5683, 5684, 5685, 5686, 5687, 5688, 5689, 5690, 5691, 5692, 5693, 5694, 5695, 6720,
         6721, 6722, 6723, 6724, 6725, 6726, 6727, 6728, 6729, 6730, 6731, 6732, 6733, 6734, 6735, 6736,
         6737, 6738, 6739, 6740, 6741, 6742, 6743, 6744, 6745, 6746, 6747, 6748, 6749, 6750, 6751, 6752,
         6753, 6754, 6755, 6756, 6757, 6758, 6759, 6760, 6761, 6762, 6763, 6764, 6765, 6766, 6767, 6768,
         6769, 6770, 6771, 6772, 6773, 6774, 6775, 6776, 6777, 6778, 6779, 6780, 6781, 6782, 6783, 7808,
         7809, 7808, 6783, 6782, 6781, 6780, 6779, 6778, 6777, 6776, 6775, 6774, 6773, 6772, 6771, 6770,
         6769, 6768, 6767, 6766, 6765, 6764, 6763, 6762, 6761, 6760, 6759, 6758, 6757, 6756, 6755, 6754,
         6753, 6752, 6751, 6750, 6749, 6748, 6747, 6746, 6745, 6744, 6743, 6742, 6741, 6740, 6739, 6738,
         6737, 6736, 6735, 6734, 6733, 6732, 6731, 6730, 6729, 6728, 6727, 6726, 6725, 6724, 6723, 6722,
         6721, 6720, 5695, 5694, 5693, 5692, 5691, 5690, 5689, 5688, 5687, 5686, 5685, 5684, 5683, 5682,
         5681, 5680, 5679, 5678, 5677, 5676, 5675, 5674, 5673, 5672, 5671, 5670, 5669, 5668, 5667, 5666,
         5665, 5664, 4639, 4638, 4637, 4636, 4635, 4634, 4633, 4632, 4631, 4630, 4629, 4628, 4627, 4626,
         4625, 4624, 3599, 3598, 3597, 3596, 3595, 3594, 3593, 3592, 2567, 2566, 2565, 2564, 1539, 1538
      },
      // Signed
      new int[]
      {
          513, 2052, 2054, 3080, 3082, 3084, 3086, 4112, 4114, 4116, 4118, 4120, 4122, 4124, 4126, 5152,
         5154, 5156, 5158, 5160, 5162, 5164, 5166, 5168, 5170, 5172, 5174, 5176, 5178, 5180, 5182, 6208,
         6210, 6212, 6214, 6216, 6218, 6220, 6222, 6224, 6226, 6228, 6230, 6232, 6234, 6236, 6238, 6240,
         6242, 6244, 6246, 6248, 6250, 6252, 6254, 6256, 6258, 6260, 6262, 6264, 6266, 6268, 6270, 7296,
         7298, 7300, 7302, 7304, 7306, 7308, 7310, 7312, 7314, 7316, 7318, 7320, 7322, 7324, 7326, 7328,
         7330, 7332, 7334, 7336, 7338, 7340, 7342, 7344, 7346, 7348, 7350, 7352, 7354, 7356, 7358, 7360,
         7362, 7364, 7366, 7368, 7370, 7372, 7374, 7376, 7378, 7380, 7382, 7384, 7386, 7388, 7390, 7392,
         7394, 7396, 7398, 7400, 7402, 7404, 7406, 7408, 7410, 7412, 7414, 7416, 7418, 7420, 7422, 8448,
         8451, 8449, 7423, 7421, 7419, 7417, 7415, 7413, 7411, 7409, 7407, 7405, 7403, 7401, 7399, 7397,
         7395, 7393, 7391, 7389, 7387, 7385, 7383, 7381, 7379, 7377, 7375, 7373, 7371, 7369, 7367, 7365,
         7363, 7361, 7359, 7357, 7355, 7353, 7351, 7349, 7347, 7345, 7343, 7341, 7339, 7337, 7335, 7333,
         7331, 7329, 7327, 7325, 7323, 7321, 7319, 7317, 7315, 7313, 7311, 7309, 7307, 7305, 7303, 7301,
         7299, 7297, 6271, 6269, 6267, 6265, 6263, 6261, 6259, 6257, 6255, 6253, 6251, 6249, 6247, 6245,
         6243, 6241, 6239, 6237, 6235, 6233, 6231, 6229, 6227, 6225, 6223, 6221, 6219, 6217, 6215, 6213,
         6211, 6209, 5183, 5181, 5179, 5177, 5175, 5173, 5171, 5169, 5167, 5165, 5163, 5161, 5159, 5157,
         5155, 5153, 4127, 4125, 4123, 4121, 4119, 4117, 4115, 4113, 3087, 3085, 3083, 3081, 2055, 2053
      }
    };

    private final int[] cache;
    private final int signed;
    private final OutputBitStream bitstream;


    public ExpGolombEncoder(OutputBitStream bitstream, boolean signed)
    {
       if (bitstream == null)
          throw new NullPointerException("ExpGolomb codec: Invalid null bitstream parameter");

       this.signed = (signed == true) ? 1 : 0;
       this.cache = CACHE[this.signed];
       this.bitstream = bitstream;
    }


    public boolean isSigned()
    {
       return this.signed == 1;
    }


    @Override
    public int encode(byte[] block, int blkptr, int count)
    {
      if ((block == null) || (blkptr+count > block.length) || (blkptr < 0) || (count < 0))
         return -1;

      final int end = blkptr + count;

      for (int i = blkptr; i<end; i++)
         this.encodeByte(block[i]);

      return count;
    }


    public void encodeByte(byte val)
    {
       if (val == 0)
       {
          // shortcut when input is 0
          this.bitstream.writeBit(1);
          return;
       }

       final int emit = this.cache[val&0xFF];
       this.bitstream.writeBits(emit&0x1FF, emit>>>9);
    }


    @Override
    public OutputBitStream getBitStream()
    {
       return this.bitstream;
    }


    @Override
    public void dispose()
    {
    }
} public class HuffmanDecoder implements EntropyDecoder
{
   private static final int DECODING_BATCH_SIZE = 14; // ensures decoding table fits in L1 cache
   private static final int TABLE_MASK = (1<<DECODING_BATCH_SIZE) - 1;

   private final InputBitStream bs;
   private final int[] codes;
   private final int[] alphabet;
   private final short[] sizes;
   private final short[] table; // decoding table: code -> size, symbol
   private final int chunkSize;
   private long state; // holds bits read from bitstream
   private int bits; // holds number of unused bits in 'state'


   public HuffmanDecoder(InputBitStream bitstream) throws BitStreamException
   {
      this(bitstream, HuffmanCommon.MAX_CHUNK_SIZE);
   }


   // The chunk size indicates how many bytes are encoded (per block) before
   // resetting the frequency stats.
   public HuffmanDecoder(InputBitStream bitstream, int chunkSize) throws BitStreamException
   {
      if (bitstream == null)
          throw new NullPointerException("Huffman codec: Invalid null bitstream parameter");

      if (chunkSize < 1024)
         throw new IllegalArgumentException("Huffman codec: The chunk size must be at least 1024");

      if (chunkSize > HuffmanCommon.MAX_CHUNK_SIZE)
         throw new IllegalArgumentException("Huffman codec: The chunk size must be at most "+HuffmanCommon.MAX_CHUNK_SIZE);

      this.bs = bitstream;
      this.sizes = new short[256];
      this.alphabet = new int[256];
      this.codes = new int[256];
      this.table = new short[TABLE_MASK+1];
      this.chunkSize = chunkSize;

      // Default lengths & canonical codes
      for (int i=0; i<256; i++)
      {
         this.sizes[i] = 8;
         this.codes[i] = i;
      }
   }


   // readLengths decodes the code lengths from the bitstream and generates
   // the Huffman codes for decoding.
   public int readLengths() throws BitStreamException
   {
      final int count = EntropyUtils.decodeAlphabet(this.bs, this.alphabet);

      if (count == 0)
         return 0;

      ExpGolombDecoder egdec = new ExpGolombDecoder(this.bs, true);
      int curSize = 2;

      // Decode lengths
      for (int i=0; i<count; i++)
      {
         final int s = this.alphabet[i];

         if ((s&0xFF) != s)
         {
            throw new BitStreamException("Invalid bitstream: incorrect Huffman symbol " + s,
               BitStreamException.INVALID_STREAM);
         }

         this.codes[s] = 0;
         curSize += egdec.decodeByte();

         if ((curSize <= 0) || (curSize > HuffmanCommon.MAX_SYMBOL_SIZE))
         {
            throw new BitStreamException("Invalid bitstream: incorrect size " + curSize +
                    " for Huffman symbol " + s, BitStreamException.INVALID_STREAM);
         }

         this.sizes[s] = (short) curSize;
      }

      // Create canonical codes
      if (HuffmanCommon.generateCanonicalCodes(this.sizes, this.codes, this.alphabet, count) < 0)
      {
         throw new BitStreamException("Could not generate Huffman codes: max code length (" +
                 HuffmanCommon.MAX_SYMBOL_SIZE + " bits) exceeded", BitStreamException.INVALID_STREAM);
      }

      this.buildDecodingTables(count);
      return count;
   }


   // max(CodeLen) must be <= MAX_SYMBOL_SIZE
   private void buildDecodingTables(int count)
   {
      for (int i=0; i<this.table.length; i++)
         this.table[i] = 0;

      int length = 0;

      for (int i=0; i<count; i++)
      {
         final int s = this.alphabet[i];

         if (this.sizes[s] > length)
            length = this.sizes[s];

         // code -> size, symbol
         final short val = (short) ((this.sizes[s]<<8) | s);
         final int code = this.codes[s];

         // All DECODING_BATCH_SIZE bit values read from the bit stream and
         // starting with the same prefix point to symbol s
         int idx = code << (DECODING_BATCH_SIZE-length);
         final int end = (code+1) << (DECODING_BATCH_SIZE-length);

         while (idx < end)
            this.table[idx++] = val;
      }
   }


   @Override
   public int decode(byte[] block, int blkptr, int count)
   {
      if ((block == null) || (blkptr+count > block.length) || (blkptr < 0) || (count < 0))
        return -1;

      if (count == 0)
         return 0;

      int startChunk = blkptr;
      final int end = blkptr + count;

      while (startChunk < end)
      {
         final int endChunk = Math.min(startChunk+this.chunkSize, end);

         // For each chunk, read code lengths, rebuild codes, rebuild decoding table
         final int alphabetSize = this.readLengths();

         if (alphabetSize <= 0)
            return startChunk - blkptr;

         if (alphabetSize == 1)
         {
            // Shortcut for chunks with only one symbol
            for (int i=startChunk; i<endChunk; i++)
               block[i] = (byte) this.alphabet[0];

            startChunk = endChunk;
            continue;
        }

         // Compute minimum number of bits required in bitstream for fast decoding
         final int minCodeLen = this.sizes[this.alphabet[0]]; // not 0
         int padding = 64 / minCodeLen;

         if (minCodeLen * padding != 64)
            padding++;

         final int endChunk4 = startChunk + Math.max(((endChunk-startChunk-padding)&-4), 0);

         for (int i=startChunk; i<endChunk4; i+=4)
         {
            this.fetchBits();
            block[i]   = this.decodeByte();
            block[i+1] = this.decodeByte();
            block[i+2] = this.decodeByte();
            block[i+3] = this.decodeByte();
         }

         // Fallback to regular decoding
         for (int i=endChunk4; i<endChunk; i++)
            block[i] = this.slowDecodeByte();

         startChunk = endChunk;
      }

      return count;
   }


   private byte slowDecodeByte()
   {
      int code = 0;
      int codeLen = 0;

      while (codeLen < HuffmanCommon.MAX_SYMBOL_SIZE)
      {
         codeLen++;
         code <<= 1;

         if (this.bits == 0)
         {
            code |= this.bs.readBit();
         }
         else
         {
            this.bits--;
            code |= ((this.state >>> this.bits) & 1);
         }

         final int idx = code << (DECODING_BATCH_SIZE-codeLen);

         if ((this.table[idx] >>> 8) == codeLen)
            return (byte) this.table[idx];
      }

      throw new BitStreamException("Invalid bitstream: incorrect Huffman code",
         BitStreamException.INVALID_STREAM);
   }


   private void fetchBits()
   {
      this.state = (this.bits == 0) ? this.bs.readBits(64) :
         (this.state << -this.bits) | this.bs.readBits(64-this.bits);
      this.bits = 64;
   }


   private byte decodeByte()
   {
      final int idx = (int) (this.state >>> (this.bits-DECODING_BATCH_SIZE));
      final int val = this.table[idx&TABLE_MASK];
      this.bits -= (val >>> 8);
      return (byte) val;
   }


   @Override
   public InputBitStream getBitStream()
   {
      return this.bs;
   }


   @Override
   public void dispose()
   {
   }
} public class HuffmanEncoder implements EntropyEncoder
{
   private final OutputBitStream bs;
   private final int[] freqs;
   private final int[] codes;
   private final int[] alphabet;
   private final int[] sranks;  // sorted ranks
   private final int[] buffer;  // temporary data
   private final short[] sizes;
   private final int chunkSize;
   private int maxCodeLen;


   public HuffmanEncoder(OutputBitStream bitstream) throws BitStreamException
   {
      this(bitstream, HuffmanCommon.MAX_CHUNK_SIZE);
   }


    // The chunk size indicates how many bytes are encoded (per block) before
    // resetting the frequency stats.
   public HuffmanEncoder(OutputBitStream bitstream, int chunkSize) throws BitStreamException
   {
      if (bitstream == null)
         throw new NullPointerException("Huffman codec: Invalid null bitstream parameter");

      if (chunkSize < 1024)
         throw new IllegalArgumentException("Huffman codec: The chunk size must be at least 1024");

      if (chunkSize > HuffmanCommon.MAX_CHUNK_SIZE)
         throw new IllegalArgumentException("Huffman codec: The chunk size must be at most "+HuffmanCommon.MAX_CHUNK_SIZE);

      this.bs = bitstream;
      this.freqs = new int[256];
      this.sizes = new short[256];
      this.alphabet = new int[256];
      this.sranks = new int[256];
      this.buffer = new int[256];
      this.codes = new int[256];
      this.chunkSize = chunkSize;

      // Default frequencies, sizes and codes
      for (int i=0; i<256; i++)
      {
         this.freqs[i] = 1;
         this.sizes[i] = 8;
         this.codes[i] = i;
      }
   }


   // Rebuild Huffman codes
   private int updateFrequencies(int[] frequencies) throws BitStreamException
   {
      if ((frequencies == null) || (frequencies.length != 256))
         return -1;

      int count = 0;

      for (int i=0; i<256; i++)
      {
         this.sizes[i] = 0;
         this.codes[i] = 0;

         if (frequencies[i] > 0)
            this.alphabet[count++] = i;
      }

      EntropyUtils.encodeAlphabet(this.bs, this.alphabet, count);
      int retries = 0;

      while (true)
      {
         this.computeCodeLengths(frequencies, count);

         if (this.maxCodeLen <= HuffmanCommon.MAX_SYMBOL_SIZE)
         {
            // Usual case
            HuffmanCommon.generateCanonicalCodes(this.sizes, this.codes, this.sranks, count);
            break;
         }

         // Rare: some codes exceed the budget for the max code length => normalize
         // frequencies (it boosts the smallest frequencies) and try once more.
         if (retries > 2)
            throw new IllegalArgumentException("Could not generate Huffman codes: max code length (" +
               HuffmanCommon.MAX_SYMBOL_SIZE + " bits) exceeded");

         int[] f = new int[count];
         int totalFreq = 0;

         for (int i=0; i<count; i++)
         {
            f[i] = frequencies[this.alphabet[i]];
            totalFreq += f[i];
         }

         // Copy alphabet (modified by normalizeFrequencies)
         int[] symbols = new int[count];
         System.arraycopy(this.alphabet, 0, symbols, 0, count);
         retries++;

         // Normalize to a smaller scale
         EntropyUtils.normalizeFrequencies(f, symbols, totalFreq,
              HuffmanCommon.MAX_CHUNK_SIZE>>(2*retries));

         for (int i=0; i<count; i++)
            frequencies[this.alphabet[i]] = f[i];
      }

      // Transmit code lengths only, frequencies and codes do not matter
      ExpGolombEncoder egenc = new ExpGolombEncoder(this.bs, true);
      short prevSize = 2;

      // Pack size and code (size <= MAX_SYMBOL_SIZE bits)
      // Unary encode the length differences
      for (int i=0; i<count; i++)
      {
         final int s = this.alphabet[i];
         final short currSize = this.sizes[s];
         this.codes[s] |= (currSize<<24);
         egenc.encodeByte((byte) (currSize - prevSize));
         prevSize = currSize;
      }

      return count;
   }


   private void computeCodeLengths(int[] frequencies, int count)
   {
      if (count == 1)
      {
         this.sranks[0] = this.alphabet[0];
         this.sizes[this.alphabet[0]] = 1;
         this.maxCodeLen = 1;
         return;
      }

      // Sort ranks by increasing frequencies (first key) and increasing value (second key)
      for (int i=0; i<count; i++)
         this.sranks[i] = (frequencies[this.alphabet[i]]<<8) | this.alphabet[i];

      Arrays.sort(this.sranks, 0, count);

      for (int i=0; i<count; i++)
      {
         this.buffer[i] = this.sranks[i] >>> 8;
         this.sranks[i] &= 0xFF;
      }

      // See [In-Place Calculation of Minimum-Redundancy Codes]
      // by Alistair Moffat & Jyrki Katajainen
      computeInPlaceSizesPhase1(this.buffer, count);
      computeInPlaceSizesPhase2(this.buffer, count);
      this.maxCodeLen = 0;

      for (int i=0; i<count; i++)
      {
         short codeLen = (short) this.buffer[i];

         if (codeLen == 0)
            throw new IllegalArgumentException("Could not generate Huffman codes: invalid code length 0");

         if (this.maxCodeLen < codeLen)
            this.maxCodeLen = codeLen;

         this.sizes[this.sranks[i]] = codeLen;
      }
   }


   static void computeInPlaceSizesPhase1(int[] data, int n)
   {
      for (int s=0, r=0, t=0; t<n-1; t++)
      {
         int sum = 0;

         for (int i=0; i<2; i++)
         {
            if ((s>=n) || ((r<t) && (data[r]<data[s])))
            {
               sum += data[r];
               data[r] = t;
               r++;
               continue;
            }

            sum += data[s];

            if (s > t)
               data[s] = 0;

            s++;
         }

         data[t] = sum;
      }
   }


   static void computeInPlaceSizesPhase2(int[] data, int n)
   {
      int levelTop = n - 2; //root
      int depth = 1;
      int i = n;
      int totalNodesAtLevel =  2;

      while (i > 0)
      {
         int k = levelTop;

         while ((k>0) && (data[k-1]>=levelTop))
            k--;

         final int internalNodesAtLevel = levelTop - k;
         final int leavesAtLevel = totalNodesAtLevel - internalNodesAtLevel;

         for (int j=0; j<leavesAtLevel; j++)
            data[--i] = depth;

         totalNodesAtLevel = internalNodesAtLevel << 1;
         levelTop = k;
         depth++;
      }
   }


   // Dynamically compute the frequencies for every chunk of data in the block
   @Override
   public int encode(byte[] block, int blkptr, int count)
   {
      if ((block == null) || (blkptr+count > block.length) || (blkptr < 0) || (count < 0))
         return -1;

      if (count == 0)
         return 0;

      final int end = blkptr + count;
      int startChunk = blkptr;

      while (startChunk < end)
      {
         // Update frequencies and rebuild Huffman codes
         final int endChunk = Math.min(startChunk+this.chunkSize, end);
         Global.computeHistogramOrder0(block, startChunk, endChunk, this.freqs, false);

         if (this.updateFrequencies(this.freqs) <= 1)
         {
            // Skip chunk if only one symbol
            startChunk = endChunk;
            continue;
         }

         final OutputBitStream bitstream = this.bs;
         final int[] c = this.codes;
         final int endChunk4 = ((endChunk-startChunk) & -4) + startChunk;

         for (int i=startChunk; i<endChunk4; i+=4)
         {
            // Pack 4 codes into 1 long
            int code = c[block[i]&0xFF];
            final int codeLen0 = code >>> 24;
            long st = code & 0xFFFFFF;
            code = c[block[i+1]&0xFF];
            final int codeLen1 = code >>> 24;
            st = (st<<codeLen1) | (code&0xFFFFFF);
            code = c[block[i+2]&0xFF];
            final int codeLen2 = code >>> 24;
            st = (st<<codeLen2) | (code&0xFFFFFF);
            code = c[block[i+3]&0xFF];
            final int codeLen3 = code >>> 24;
            st = (st<<codeLen3) | (code&0xFFFFFF);
            bitstream.writeBits(st, codeLen0+codeLen1+codeLen2+codeLen3);
         }

         for (int i=endChunk4; i<endChunk; i++)
         {
            final int code = c[block[i]&0xFF];
            bitstream.writeBits(code, code>>>24);
         }

         startChunk = endChunk;
      }

      return count;
   }


   @Override
   public OutputBitStream getBitStream()
   {
      return this.bs;
   }


   @Override
   public void dispose()
   {
   }
} public interface Predictor
{
    // Update the probability model
    public void update(int bit);


    // Return the split value representing the probability of 1 in the [0..4095] range.
    // E.G. 410 represents roughly a probability of 10% for 1
    public int get();
} public class FPAQDecoder implements EntropyDecoder
{
   private static final long TOP        = 0x00FFFFFFFFFFFFFFL;
   private static final long MASK_24_56 = 0x00FFFFFFFF000000L;
   private static final long MASK_0_56  = 0x00FFFFFFFFFFFFFFL;
   private static final long MASK_0_32  = 0x00000000FFFFFFFFL;
   private static final int DEFAULT_CHUNK_SIZE = 4*1024*1024;
   private static final int MAX_BLOCK_SIZE = 1 << 30;
   private static final int PSCALE = 65536;

   private long low;
   private long high;
   private long current;
   private final InputBitStream bitstream;
   private SliceByteArray sba;
   private final int[][] probs; // probability of bit=1
   private int[] p; // pointer to current prob
   private int ctx; // previous bits


   public FPAQDecoder(InputBitStream bitstream)
   {
      if (bitstream == null)
         throw new NullPointerException("FPAQ codec: Invalid null bitstream parameter");

      // Defer stream reading. We are creating the object, we should not do any I/O
      this.low = 0L;
      this.high = TOP;
      this.bitstream = bitstream;
      this.sba = new SliceByteArray(new byte[0], 0);
      this.ctx = 1;
      this.probs = new int[4][256];
      this.p = this.probs[0];

      for (int i=0; i<4; i++)
         Arrays.fill(this.probs[i], PSCALE>>1);
   }


   @Override
   public int decode(byte[] block, int blkptr, int count)
   {
      if ((block == null) || (blkptr+count > block.length) || (blkptr < 0) || (count < 0) || (count > MAX_BLOCK_SIZE))
         return -1;

      if (count == 0)
         return 0;

      int startChunk = blkptr;
      final int end = blkptr + count;

      // Split block into chunks, read bit array from bitstream and decode chunk
      while (startChunk < end)
      {
         final int chunkSize = Math.min(DEFAULT_CHUNK_SIZE, end-startChunk);
         final int szBytes = EntropyUtils.readVarInt(this.bitstream);
         this.current = this.bitstream.readBits(56);

         if (szBytes == 0)
            break;

         if (this.sba.array.length < szBytes)
            this.sba.array = new byte[szBytes+(szBytes>>3)];

         this.bitstream.readBits(this.sba.array, 0, 8*szBytes);
         this.sba.index = 0;
         final int endChunk = startChunk + chunkSize;
         this.p = this.probs[0];

         for (int i=startChunk; i<endChunk; i++)
         {
            this.ctx = 1;
            this.decodeBit(this.p[this.ctx]>>>4);
            this.decodeBit(this.p[this.ctx]>>>4);
            this.decodeBit(this.p[this.ctx]>>>4);
            this.decodeBit(this.p[this.ctx]>>>4);
            this.decodeBit(this.p[this.ctx]>>>4);
            this.decodeBit(this.p[this.ctx]>>>4);
            this.decodeBit(this.p[this.ctx]>>>4);
            this.decodeBit(this.p[this.ctx]>>>4);
            block[i] = (byte) this.ctx;
            this.p = this.probs[(this.ctx&0xFF)>>>6];
         }

         startChunk = endChunk;
      }

      return count;
   }


   private int decodeBit(int pred)
   {
      // Calculate interval split
      // Written in a way to maximize accuracy of multiplication/division
      final long split = ((((this.high-this.low) >>> 4) * pred) >>> 8) + this.low;
      int bit;

      // Update probabilities
      if (split >= this.current)
      {
         bit = 1;
         this.high = split;
         this.p[this.ctx] -= ((this.p[this.ctx]-PSCALE+64) >> 6);
         this.ctx = (this.ctx<<1) + 1;
      }
      else
      {
         bit = 0;
         this.low = -~split;
         this.p[this.ctx] -= (this.p[this.ctx] >> 6);
         this.ctx = this.ctx << 1;
      }

      // Read 32 bits from bitstream
      while (((this.low ^ this.high) & MASK_24_56) == 0)
         this.read();

      return bit;
   }


   protected void read()
   {
      this.low = (this.low<<32) & MASK_0_56;
      this.high = ((this.high<<32) | MASK_0_32) & MASK_0_56;
      final long val = Memory.BigEndian.readInt32(this.sba.array, this.sba.index) & 0xFFFFFFFFL;
      this.current = ((this.current<<32) | val) & MASK_0_56;
      this.sba.index += 4;
   }


   @Override
   public InputBitStream getBitStream()
   {
      return this.bitstream;
   }


   @Override
   public void dispose()
   {
   }
} public class FPAQEncoder implements EntropyEncoder
{
   private static final long TOP        = 0x00FFFFFFFFFFFFFFL;
   private static final long MASK_24_56 = 0x00FFFFFFFF000000L;
   private static final long MASK_0_24  = 0x0000000000FFFFFFL;
   private static final long MASK_0_32  = 0x00000000FFFFFFFFL;
   private static final int DEFAULT_CHUNK_SIZE = 4*1024*1024;
   private static final int MAX_BLOCK_SIZE = 1 << 30;
   private static final int PSCALE = 65536;

   private long low;
   private long high;
   private final OutputBitStream bitstream;
   private boolean disposed;
   private SliceByteArray sba;
   private final int[][] probs; // probability of bit=1
   private int[] p; // pointer to current prob


   public FPAQEncoder(OutputBitStream bitstream)
   {
      if (bitstream == null)
         throw new NullPointerException("FPAQ codec: Invalid null bitstream parameter");

      this.low = 0L;
      this.high = TOP;
      this.bitstream = bitstream;
      this.sba = new SliceByteArray(new byte[0], 0);
      this.probs = new int[4][256];
      this.p = this.probs[0];

      for (int i=0; i<4; i++)
         Arrays.fill(this.probs[i], PSCALE>>1);
   }


   @Override
   public int encode(byte[] block, int blkptr, int count)
   {
      if ((block == null) || (blkptr+count > block.length) || (blkptr < 0) || (count < 0) || (count > MAX_BLOCK_SIZE))
         return -1;

      if (count == 0)
         return 0;

      int startChunk = blkptr;
      final int end = blkptr + count;

      // Split block into chunks, encode chunk and write bit array to bitstream
      while (startChunk < end)
      {
         final int chunkSize = Math.min(DEFAULT_CHUNK_SIZE, end-startChunk);

         if (this.sba.array.length < (chunkSize+(chunkSize>>3)))
            this.sba.array = new byte[chunkSize+(chunkSize>>3)];

         this.sba.index = 0;
         final int endChunk = startChunk + chunkSize;
         this.p = this.probs[0];

         for (int i=startChunk; i<endChunk; i++)
         {
            final byte val = block[i];
            final int bits = (val&0xFF) + 256;
            this.encodeBit(val&0x80, 1);
            this.encodeBit(val&0x40, bits>>7);
            this.encodeBit(val&0x20, bits>>6);
            this.encodeBit(val&0x10, bits>>5);
            this.encodeBit(val&0x08, bits>>4);
            this.encodeBit(val&0x04, bits>>3);
            this.encodeBit(val&0x02, bits>>2);
            this.encodeBit(val&0x01, bits>>1);
            this.p = this.probs[(val&0xFF)>>>6];
         }

         EntropyUtils.writeVarInt(this.bitstream, this.sba.index);
         this.bitstream.writeBits(this.sba.array, 0, 8*this.sba.index);
         startChunk += chunkSize;

         if (startChunk < end)
            this.bitstream.writeBits(this.low | MASK_0_24, 56);
      }

      return count;
   }


   private void encodeBit(int bit, int pIdx)
   {
      // Calculate interval split
      // Written in a way to maximize accuracy of multiplication/division
      final long split = (((this.high-this.low) >>> 4) * (this.p[pIdx]>>>4)) >>> 8;

      // Update probabilities
      if (bit == 0)
      {
         this.low += (split + 1);
         this.p[pIdx] -= (this.p[pIdx] >> 6);
      }
      else
      {
         this.high = this.low + split;
         this.p[pIdx] -= ((this.p[pIdx]-PSCALE+64) >> 6);
      }

      // Write unchanged first 32 bits to bitstream
      while (((this.low ^ this.high) & MASK_24_56) == 0)
         this.flush();
   }


   private void flush()
   {
      Memory.BigEndian.writeInt32(this.sba.array, this.sba.index, (int) (this.high>>>24));
      this.sba.index += 4;
      this.low <<= 32;
      this.high = (this.high<<32) | MASK_0_32;
   }


   @Override
   public OutputBitStream getBitStream()
   {
      return this.bitstream;
   }


   @Override
   public void dispose()
   {
      if (this.disposed == true)
         return;

      this.disposed = true;
      this.bitstream.writeBits(this.low | MASK_0_24, 56);
   }
} public final class RangeDecoder implements EntropyDecoder
{
    private static final long TOP_RANGE    = 0x0FFFFFFFFFFFFFFFL;
    private static final long BOTTOM_RANGE = 0x000000000000FFFFL;
    private static final long RANGE_MASK   = 0x0FFFFFFF00000000L;
    private static final int DEFAULT_CHUNK_SIZE = 1 << 15; // 32 KB by default
    private static final int MAX_CHUNK_SIZE = 1 << 30;

    private long code;
    private long low;
    private long range;
    private final int[] alphabet;
    private final int[] freqs;
    private final long[] cumFreqs;
    private short[] f2s; // mapping frequency -> symbol
    private final InputBitStream bitstream;
    private final int chunkSize;
    private int shift;


    public RangeDecoder(InputBitStream bitstream)
    {
       this(bitstream, DEFAULT_CHUNK_SIZE);
    }


    // The chunk size indicates how many bytes are encoded (per block) before
    // resetting the frequency stats.
    public RangeDecoder(InputBitStream bitstream, int chunkSize)
    {
        if (bitstream == null)
            throw new NullPointerException("Range codec: Invalid null bitstream parameter");

        if (chunkSize < 1024)
           throw new IllegalArgumentException("Range codec: The chunk size must be at least 1024");

        if (chunkSize > MAX_CHUNK_SIZE)
           throw new IllegalArgumentException("Range codec: The chunk size must be at most "+MAX_CHUNK_SIZE);

        this.range = TOP_RANGE;
        this.bitstream = bitstream;
        this.chunkSize = chunkSize;
        this.cumFreqs = new long[257];
        this.freqs = new int[256];
        this.alphabet = new int[256];
        this.f2s = new short[0];
    }


    protected int decodeHeader(int[] frequencies)
    {
      int alphabetSize = EntropyUtils.decodeAlphabet(this.bitstream, this.alphabet);

      if (alphabetSize == 0)
         return 0;

      if (alphabetSize != 256)
      {
         for (int i=0; i<256; i++)
            frequencies[i] = 0;
      }

      final int logRange = (int) (8 + this.bitstream.readBits(3));
      final int scale = 1 << logRange;
      this.shift = logRange;
      int sum = 0;
      final int chkSize = (alphabetSize >= 64) ? 8 : 6;
      int llr = 3;

      while (1<<llr <= logRange)
         llr++;

      // Decode all frequencies (but the first one) by chunks of size 'inc'
      for (int i=1; i<alphabetSize; i+=chkSize)
      {
         final int logMax = (int) this.bitstream.readBits(llr);

         if (1<<logMax > scale)
         {
            throw new BitStreamException("Invalid bitstream: incorrect frequency size " +
                    logMax + " in range decoder", BitStreamException.INVALID_STREAM);
         }

         final int endj = (i+chkSize < alphabetSize) ? i + chkSize : alphabetSize;

         // Read frequencies
         for (int j=i; j<endj; j++)
         {
            int freq = (logMax == 0) ? 1 : (int) (1+this.bitstream.readBits(logMax));

            if ((freq <= 0) || (freq >= scale))
            {
               throw new BitStreamException("Invalid bitstream: incorrect frequency " +
                       freq + " for symbol '" + this.alphabet[j] + "' in range decoder",
                       BitStreamException.INVALID_STREAM);
            }

            frequencies[this.alphabet[j]] = freq;
            sum += freq;
         }
      }

      // Infer first frequency
      if (scale <= sum)
      {
         throw new BitStreamException("Invalid bitstream: incorrect frequency " +
                 frequencies[this.alphabet[0]] + " for symbol '" + this.alphabet[0] +
                 "' in range decoder", BitStreamException.INVALID_STREAM);
      }

      frequencies[this.alphabet[0]] = scale - sum;
      this.cumFreqs[0] = 0;

      if (this.f2s.length < scale)
         this.f2s = new short[scale];

      // Create histogram of frequencies scaled to 'range' and reverse mapping
      for (int i=0; i<256; i++)
      {
         this.cumFreqs[i+1] = this.cumFreqs[i] + frequencies[i];
         final int base = (int) this.cumFreqs[i];

         for (int j=frequencies[i]-1; j>=0; j--)
            this.f2s[base+j] = (short) i;
      }

      return alphabetSize;
    }


    // Initialize once (if necessary) at the beginning, the use the faster decodeByte_()
    // Reset frequency stats for each chunk of data in the block
    @Override
    public int decode(byte[] block, int blkptr, int count)
    {
      if ((block == null) || (blkptr+count > block.length) || (blkptr < 0) || (count < 0))
         return -1;

      if (count == 0)
         return 0;

      final int end = blkptr + count;
      final int sz = this.chunkSize;
      int startChunk = blkptr;

      while (startChunk < end)
      {
         final int endChunk = (startChunk + sz < end) ? startChunk + sz : end;
         final int alphabetSize = this.decodeHeader(this.freqs);

        if (alphabetSize == 0)
            return startChunk - blkptr;

        if (alphabetSize == 1)
        {
            // Shortcut for chunks with only one symbol
            for (int i=startChunk; i<endChunk; i++)
               block[i] = (byte) this.alphabet[0];

            startChunk = endChunk;
            continue;
        }


         this.range = TOP_RANGE;
         this.low = 0;
         this.code = this.bitstream.readBits(60);

         for (int i=startChunk; i<endChunk; i++)
            block[i] = this.decodeByte();

         startChunk = endChunk;
      }

      return count;
    }


    protected byte decodeByte()
    {
       // Compute next low and range
       this.range >>>= this.shift;
       final int count = (int) ((this.code - this.low) / this.range);
       final int symbol = this.f2s[count];
       final long cumFreq = this.cumFreqs[symbol];
       final long freq = this.cumFreqs[symbol+1] - cumFreq;
       this.low += (cumFreq * this.range);
       this.range *= freq;

       // If the left-most digits are the same throughout the range, read bits from bitstream
       while (true)
       {
          if (((this.low ^ (this.low + this.range)) & RANGE_MASK) != 0)
          {
             if (this.range > BOTTOM_RANGE)
                break;

             // Normalize
             this.range = -this.low & BOTTOM_RANGE;
          }

          this.code = (this.code << 28) | this.bitstream.readBits(28);
          this.range <<= 28;
          this.low <<= 28;
       }

       return (byte) symbol;
    }


    @Override
    public InputBitStream getBitStream()
    {
       return this.bitstream;
    }


    @Override
    public void dispose()
    {
    }
} public final class RangeEncoder implements EntropyEncoder
{
    private static final long TOP_RANGE    = 0x0FFFFFFFFFFFFFFFL;
    private static final long BOTTOM_RANGE = 0x000000000000FFFFL;
    private static final long RANGE_MASK   = 0x0FFFFFFF00000000L;
    private static final int DEFAULT_CHUNK_SIZE = 1 << 15; // 32 KB by default
    private static final int DEFAULT_LOG_RANGE = 12;
    private static final int MAX_CHUNK_SIZE = 1 << 30;

    private long low;
    private long range;
    private final int[] alphabet;
    private final int[] freqs;
    private final long[] cumFreqs;
    private final OutputBitStream bitstream;
    private final int chunkSize;
    private final int logRange;
    private int shift;


    public RangeEncoder(OutputBitStream bitstream)
    {
       this(bitstream, DEFAULT_CHUNK_SIZE, DEFAULT_LOG_RANGE);
    }


    // The chunk size indicates how many bytes are encoded (per block) before
    // resetting the frequency stats.
    public RangeEncoder(OutputBitStream bs, int chunkSize, int logRange)
    {
      if (bs == null)
         throw new NullPointerException("Range codec: Invalid null bitstream parameter");

      if (chunkSize < 1024)
         throw new IllegalArgumentException("Range codec: The chunk size must be at least 1024");

      if (chunkSize > MAX_CHUNK_SIZE)
         throw new IllegalArgumentException("Range codec: The chunk size must be at most "+MAX_CHUNK_SIZE);

      if ((logRange < 8) || (logRange > 16))
         throw new IllegalArgumentException("Range codec: Invalid range parameter: "+
            logRange+" (must be in [8..16])");

      this.bitstream = bs;
      this.alphabet = new int[256];
      this.freqs = new int[256];
      this.cumFreqs = new long[257];
      this.logRange = logRange;
      this.chunkSize = chunkSize;
    }


   private int updateFrequencies(int[] frequencies, int size, int lr)
   {
      if ((frequencies == null) || (frequencies.length != 256))
         return -1;

      int alphabetSize = EntropyUtils.normalizeFrequencies(frequencies, this.alphabet, size, 1<<lr);

      if (alphabetSize > 0)
      {
         this.cumFreqs[0] = 0;

         // Create histogram of frequencies scaled to 'range'
         for (int i=0; i<256; i++)
            this.cumFreqs[i+1] = this.cumFreqs[i] + frequencies[i];
      }

      this.encodeHeader(alphabetSize, this.alphabet, frequencies, lr);
      return alphabetSize;
   }


   protected boolean encodeHeader(int alphabetSize, int[] alphabet, int[] frequencies, int lr)
   {
      final int encoded = EntropyUtils.encodeAlphabet(this.bitstream, alphabet, alphabetSize);

      if (encoded < 0)
         return false;

      if (encoded == 0)
         return true;

      this.bitstream.writeBits(lr-8, 3); // logRange
      final int chkSize = (alphabetSize >= 64) ? 8 : 6;
      int llr = 3;

      while (1<<llr <= lr)
         llr++;

      // Encode all frequencies (but the first one) by chunks of size 'inc'
      for (int i=1; i<alphabetSize; i+=chkSize)
      {
         int max = frequencies[alphabet[i]] - 1;
         int logMax = 0;
         final int endj = (i+chkSize < alphabetSize) ? i+chkSize : alphabetSize;

         // Search for max frequency log size in next chunk
         for (int j=i+1; j<endj; j++)
         {
            if (frequencies[alphabet[j]]-1 > max)
               max = frequencies[alphabet[j]]-1;
         }

         while (1<<logMax <= max)
            logMax++;

         this.bitstream.writeBits(logMax, llr);

         if (logMax == 0) // all frequencies equal one in this chunk
            continue;

         // Write frequencies
         for (int j=i; j<endj; j++)
            this.bitstream.writeBits(frequencies[alphabet[j]]-1, logMax);
      }

      return true;
   }


    // Reset frequency stats for each chunk of data in the block
    @Override
    public int encode(byte[] block, int blkptr, int count)
    {
       if ((block == null) || (blkptr+count > block.length) || (blkptr < 0) || (count < 0))
          return -1;

       if (count == 0)
          return 0;

       final int end = blkptr + count;
       final int sz = this.chunkSize;
       int startChunk = blkptr;

       while (startChunk < end)
       {
           final int endChunk = (startChunk+sz < end) ? startChunk+sz : end;
           this.range = TOP_RANGE;
           this.low = 0;
           int lr = this.logRange;

           // Lower log range if the size of the data chunk is small
           while ((lr > 8) && (1<<lr > endChunk-startChunk))
              lr--;

           if (this.rebuildStatistics(block, startChunk, endChunk, lr) <= 1)
           {
               // Skip chunk if only one symbol
               startChunk = endChunk;
               continue;
           }

           this.shift = lr;

           for (int i=startChunk; i<endChunk; i++)
              this.encodeByte(block[i]);

           // Flush 'low'
           this.bitstream.writeBits(this.low, 60);
           startChunk = endChunk;
       }

       return count;
    }


    protected void encodeByte(byte b)
    {
        // Compute next low and range
        final int symbol = b & 0xFF;
        final long cumFreq = this.cumFreqs[symbol];
        final long freq = this.cumFreqs[symbol+1] - cumFreq;
        this.range >>>= this.shift;
        this.low += (cumFreq * this.range);
        this.range *= freq;

        // If the left-most digits are the same throughout the range, write bits to bitstream
        while (true)
        {
            if (((this.low ^ (this.low + this.range)) & RANGE_MASK) != 0)
            {
               if (this.range > BOTTOM_RANGE)
                  break;

               // Normalize
               this.range = -this.low & BOTTOM_RANGE;
            }

            this.bitstream.writeBits(this.low >>> 32, 28);
            this.range <<= 28;
            this.low <<= 28;
        }
    }


   // Compute chunk frequencies, cumulated frequencies and encode chunk header
   private int rebuildStatistics(byte[] block, int start, int end, int lr)
   {
      Global.computeHistogramOrder0(block, start, end, this.freqs, false);
      return this.updateFrequencies(this.freqs, end-start, lr);
   }


   @Override
    public OutputBitStream getBitStream()
    {
       return this.bitstream;
    }


    @Override
    public void dispose()
    {
    }
} public final class RiceGolombDecoder implements EntropyDecoder
{
    private final boolean signed;
    private final InputBitStream bitstream;
    private final int logBase;


    public RiceGolombDecoder(InputBitStream bitstream, boolean signed, int logBase)
    {
        if (bitstream == null)
           throw new NullPointerException("RiceGolomb codec: Invalid null bitstream parameter");

        if ((logBase < 1) || (logBase > 12))
           throw new IllegalArgumentException("RiceGolomb codec: Invalid logBase parameter: "+
             logBase+" (must be in [1..12])");

        this.signed = signed;
        this.bitstream = bitstream;
        this.logBase = logBase;
    }


    public boolean isSigned()
    {
        return this.signed;
    }


    public byte decodeByte()
    {
       long q = 0;

       // quotient is unary encoded
       while (this.bitstream.readBit() == 0)
          q++;

       // remainder is binary encoded
       final long res = (q << this.logBase) | this.bitstream.readBits(this.logBase);

       if ((res != 0) && (this.signed == true))
       {
          if (this.bitstream.readBit() == 1)
             return (byte) -res;
       }

       return (byte) res;
    }


    @Override
    public InputBitStream getBitStream()
    {
       return this.bitstream;
    }


    @Override
    public int decode(byte[] block, int blkptr, int count)
    {
      if ((block == null) || (blkptr+count > block.length) || (blkptr < 0) || (count < 0))
         return -1;

      final int end = blkptr + count;

      for (int i=blkptr; i<end; i++)
         block[i] = this.decodeByte();

      return count;
    }


    @Override
    public void dispose()
    {
    }
} public final class RiceGolombEncoder implements EntropyEncoder
{
    private final boolean signed;
    private final OutputBitStream bitstream;
    private final int logBase;
    private final int base;


    public RiceGolombEncoder(OutputBitStream bitstream, boolean signed, int logBase)
    {
        if (bitstream == null)
           throw new NullPointerException("RiceGolomb codec: Invalid null bitstream parameter");

        if ((logBase < 1) || (logBase > 12))
           throw new IllegalArgumentException("RiceGolomb codec: Invalid logBase parameter: "+
             logBase+" (must be in [1..12])");

        this.signed = signed;
        this.bitstream = bitstream;
        this.logBase = logBase;
        this.base = 1 << this.logBase;
    }


    public boolean isSigned()
    {
       return this.signed;
    }


    public void encodeByte(byte val)
    {
       if (val == 0)
       {
          this.bitstream.writeBits(this.base, this.logBase+1);
          return;
       }

       int iVal = val;
       iVal = (iVal + (iVal >> 31)) ^ (iVal >> 31); // abs(val2)

        // quotient is unary encoded, remainder is binary encoded
       int emit = this.base | (iVal & (this.base-1));
       int n = (1 + (iVal >> this.logBase)) + this.logBase;

       if (this.signed == true)
       {
          // Add 0 for positive and 1 for negative sign
          n++;
          emit = (emit << 1) | (((int) val) >>> 31);
       }

       this.bitstream.writeBits(emit, n);
    }


    @Override
    public OutputBitStream getBitStream()
    {
       return this.bitstream;
    }


    @Override
    public int encode(byte[] block, int blkptr, int count)
    {
       if ((block == null) || (blkptr+count > block.length) || (blkptr < 0) || (count < 0))
          return -1;

       final int end = blkptr + count;

       for (int i = blkptr; i<end; i++)
          this.encodeByte(block[i]);

       return count;
    }


    @Override
    public void dispose()
    {
    }
} public class TPAQPredictor implements Predictor
{
   private static final int MAX_LENGTH = 88;
   private static final int BUFFER_SIZE = 64*1024*1024;
   private static final int HASH_SIZE = 16*1024*1024;
   private static final int MASK_80808080 = 0x80808080;
   private static final int MASK_F0F0F000 = 0xF0F0F000;
   private static final int MASK_4F4FFFFF = 0x4F4FFFFF;
   private static final int MASK_FFFF0000 = 0xFFFF0000;
   private static final int HASH = 0x7FEB352D;

   ///////////////////////// state table ////////////////////////
   // States represent a bit history within some context.
   // State 0 is the starting state (no bits seen).
   // States 1-30 represent all possible sequences of 1-4 bits.
   // States 31-252 represent a pair of counts, (n0,n1), the number
   //   of 0 and 1 bits respectively.  If n0+n1 < 16 then there are
   //   two states for each pair, depending on if a 0 or 1 was the last
   //   bit seen.
   // If n0 and n1 are too large, then there is no state to represent this
   // pair, so another state with about the same ratio of n0/n1 is substituted.
   // Also, when a bit is observed and the count of the opposite bit is large,
   // then part of this count is discarded to favor newer data over old.
   private static final byte[][] STATE_TRANSITIONS =
   {
      // Bit 0
      {
            1,     3,  -113,     4,     5,     6,     7,     8,     9,    10,
           11,    12,    13,    14,    15,    16,    17,    18,    19,    20,
           21,    22,    23,    24,    25,    26,    27,    28,    29,    30,
           31,    32,    33,    34,    35,    36,    37,    38,    39,    40,
           41,    42,    43,    44,    45,    46,    47,    48,    49,    50,
           51,    52,    47,    54,    55,    56,    57,    58,    59,    60,
           61,    62,    63,    64,    65,    66,    67,    68,    69,     6,
           71,    71,    71,    61,    75,    56,    77,    78,    77,    80,
           81,    82,    83,    84,    85,    86,    87,    88,    77,    90,
           91,    92,    80,    94,    95,    96,    97,    98,    99,    90,
          101,    94,   103,   101,   102,   104,   107,   104,   105,   108,
          111,   112,   113,   114,   115,   116,    92,   118,    94,   103,
          119,   122,   123,    94,   113,   126,   113,  -128,  -127,   114,
         -125,  -124,   112,  -122,   111,  -122,   110,  -122,  -122,  -128,
         -128,  -114,  -113,   115,   113,  -114,  -128,  -108,  -107,    79,
         -108,  -114,  -108,  -106,  -101,  -107,   -99,  -107,   -97,  -107,
         -125,   101,    98,   115,   114,    91,    79,    58,     1,   -86,
         -127,  -128,   110,   -82,  -128,   -80,  -127,   -82,   -77,   -82,
          -80,  -115,   -99,   -77,   -71,   -99,   -69,   -68,   -88,  -105,
          -65,   -64,   -68,   -69,   -84,   -81,   -86,  -104,   -71,   -86,
          -80,   -86,   -53,  -108,   -71,   -53,   -71,   -64,   -47,   -68,
          -45,   -64,   -43,   -42,   -68,   -40,   -88,    84,    54,    54,
          -35,    54,    55,    85,    69,    63,    56,    86,    58,   -26,
          -25,    57,   -27,    56,   -32,    54,    54,    66,    58,    54,
           61,    57,   -34,    78,    85,    82,     0,     0,     0,     0,
            0,     0,     0,     0,     0,     0
      },
      // Bit 1
      {
            2,   -93,   -87,   -93,   -91,    89,   -11,   -39,   -11,   -11,
          -23,   -12,   -29,    74,   -35,   -35,   -38,   -30,   -13,   -38,
          -18,   -14,    74,   -18,   -15,   -16,   -17,   -32,   -31,   -35,
          -24,    72,   -32,   -28,   -33,   -31,   -18,    73,   -89,    76,
          -19,   -22,   -25,    72,    31,    63,   -31,   -19,   -20,   -21,
           53,   -22,    53,   -22,   -27,   -37,   -27,   -23,   -24,   -28,
          -30,    72,    74,   -34,    75,   -36,   -89,    57,   -38,    70,
          -88,    72,    73,    74,   -39,    76,   -89,    79,    79,   -90,
          -94,   -94,   -94,   -94,   -91,    89,    89,   -91,    89,   -94,
           93,    93,    93,   -95,   100,    93,    93,    93,    93,    93,
          -95,   102,   120,   104,   105,   106,   108,   106,   109,   110,
          -96,  -122,   108,   108,   126,   117,   117,   121,   119,   120,
          107,   124,   117,   117,   125,   127,   124,  -117,  -126,   124,
         -123,   109,   110,  -121,   110,  -120,  -119,  -118,   127,  -116,
         -115,  -111,  -112,   124,   125,  -110,  -109,  -105,   125,  -106,
          127,  -104,  -103,  -102,  -100,  -117,   -98,  -117,  -100,  -117,
         -126,   117,   -93,   -92,  -115,   -93,  -109,     2,     2,   -57,
          -85,   -84,   -83,   -79,   -81,   -85,   -85,   -78,   -76,   -84,
          -75,   -74,   -73,   -72,   -70,   -78,   -67,   -75,   -75,   -66,
          -63,   -74,   -74,   -62,   -61,   -60,   -59,   -58,   -87,   -56,
          -55,   -54,   -52,   -76,   -51,   -50,   -49,   -48,   -46,   -62,
          -44,   -72,   -41,   -63,   -72,   -48,   -63,   -93,   -37,   -88,
           94,   -39,   -33,   -32,   -31,    76,   -29,   -39,   -27,   -37,
           79,    86,   -91,   -39,   -42,   -31,   -40,   -40,   -22,    75,
          -42,   -19,    74,    74,   -93,   -39,     0,     0,     0,     0,
            0,     0,     0,     0,     0,     0
      }
   };


   private static final int[] STATE_MAP =
   {
      -31,  -400,   406,  -547,  -642,  -743,  -827,  -901,
     -901,  -974,  -945,  -955, -1060, -1031, -1044,  -956,
     -994, -1035, -1147, -1069, -1111, -1145, -1096, -1084,
    -1171, -1199, -1062, -1498, -1199, -1199, -1328, -1405,
    -1275, -1248, -1167, -1448, -1441, -1199, -1357, -1160,
    -1437, -1428, -1238, -1343, -1526, -1331, -1443, -2047,
    -2047, -2044, -2047, -2047, -2047,  -232,  -414,  -573,
     -517,  -768,  -627,  -666,  -644,  -740,  -721,  -829,
     -770,  -963,  -863, -1099,  -811,  -830,  -277, -1036,
     -286,  -218,   -42,  -411,   141, -1014, -1028,  -226,
     -469,  -540,  -573,  -581,  -594,  -610,  -628,  -711,
     -670,  -144,  -408,  -485,  -464,  -173,  -221,  -310,
     -335,  -375,  -324,  -413,   -99,  -179,  -105,  -150,
      -63,    -9,    56,    83,   119,   144,   198,   118,
      -42,   -96,  -188,  -285,  -376,   107,  -138,    38,
      -82,   186,  -114,  -190,   200,   327,    65,   406,
      108,   -95,   308,   171,   -18,   343,   135,   398,
      415,   464,   514,   494,   508,   519,    92,  -123,
      343,   575,   585,   516,    -7,  -156,   209,   574,
      613,   621,   670,   107,   989,   210,   961,   246,
      254,   -12,  -108,    97,   281,  -143,    41,   173,
     -209,   583,   -55,   250,   354,   558,    43,   274,
       14,   488,   545,    84,   528,   519,   587,   634,
      663,    95,   700,    94,  -184,   730,   742,   162,
      -10,   708,   692,   773,   707,   855,   811,   703,
      790,   871,   806,     9,   867,   840,   990,  1023,
     1409,   194,  1397,   183,  1462,   178,   -23,  1403,
      247,   172,     1,   -32,  -170,    72,  -508,   -46,
     -365,   -26,  -146,   101,   -18,  -163,  -422,  -461,
     -146,   -69,   -78,  -319,  -334,  -232,   -99,     0,
       47,   -74,     0,  -452,    14,   -57,     1,     1,
        1,     1,     1,     1,     1,     1,     1,     1,
   };


   private static final int[] MATCH_PRED =
   {
        0,    64,   128,   192,   256,   320,   384,   448,
      512,   576,   640,   704,   768,   832,   896,   960,
     1024,  1038,  1053,  1067,  1082,  1096,  1111,  1125,
     1139,  1154,  1168,  1183,  1197,  1211,  1226,  1240,
     1255,  1269,  1284,  1298,  1312,  1327,  1341,  1356,
     1370,  1385,  1399,  1413,  1428,  1442,  1457,  1471,
     1486,  1500,  1514,  1529,  1543,  1558,  1572,  1586,
     1601,  1615,  1630,  1644,  1659,  1673,  1687,  1702,
     1716,  1731,  1745,  1760,  1774,  1788,  1803,  1817,
     1832,  1846,  1861,  1875,  1889,  1904,  1918,  1933,
     1947,  1961,  1976,  1990,  2005,  2019,  2034,  2047,
   };


   static int hash(int x, int y)
   {
      final int h = x*HASH ^ y*HASH;
      return (h>>1) ^ (h>>9) ^ (x>>2) ^ (y>>3) ^ HASH;
   }



   private int pr;                     // next predicted value (0-4095)
   private int c0;                     // bitwise context: last 0-7 bits with a leading 1 (1-255)
   private int c4;                     // last 4 whole bytes, last is in low 8 bits
   private int c8;                     // last 8 to 4 whole bytes, last is in low 8 bits
   private int bpos;                   // number of bits in c0 (0-7)
   private int pos;
   private int binCount;
   private int matchLen;
   private int matchPos;
   private int hash;
   private final int statesMask;
   private final int mixersMask;
   private final int hashMask;
   private final int bufferMask;
   private final LogisticAdaptiveProbMap sse0;
   private final LogisticAdaptiveProbMap sse1;
   private final Mixer[] mixers;
   private Mixer mixer;                  // current mixer
   private final byte[] buffer;
   private final int[] hashes;           // hash table(context, buffer position)
   private final byte[] bigStatesMap;    // hash table(context, prediction)
   private final byte[] smallStatesMap0; // hash table(context, prediction)
   private final byte[] smallStatesMap1; // hash table(context, prediction)
   private int cp0;                      // context pointers
   private int cp1;
   private int cp2;
   private int cp3;
   private int cp4;
   private int cp5;
   private int cp6;
   private int ctx0;                     // contexts
   private int ctx1;
   private int ctx2;
   private int ctx3;
   private int ctx4;
   private int ctx5;
   private int ctx6;
   private boolean extra;


   public TPAQPredictor()
   {
      this(null); // 256 MB
   }


   public TPAQPredictor(Map<String, Object> ctx)
   {
      int statesSize = 1 << 28;
      int mixersSize = 1 << 12;
      int hashSize = HASH_SIZE;
      int extraMem = 0;
      int bufferSize = BUFFER_SIZE;

      if (ctx != null)
      {
         // If extra mode, add more memory for states table, hash table
         // and add second SSE
         String codec = (String) ctx.getOrDefault("codec", "NONE");
         this.extra = "TPAQX".equals(codec);
         extraMem = (this.extra == true) ? 1 : 0;

         // Block size requested by the user
         // The user can request a big block size to force more states
         final int rbsz = (Integer) ctx.getOrDefault("blockSize", 32768);

         if (rbsz >= 64*1024*1024)
            statesSize = 1 << 28;
         else if (rbsz >= 16*1024*1024)
            statesSize = 1 << 27;
         else if (rbsz >= 4*1024*1024)
            statesSize = 1 << 26;
         else statesSize = (rbsz >= 1024*1024) ? 1 << 24 : 1 << 22;

         // Actual size of the current block
         // Too many mixers hurts compression for small blocks.
         // Too few mixers hurts compression for big blocks.
         final int absz = (Integer) ctx.getOrDefault("size", rbsz);

         if (absz >= 32*1024*1024)
            mixersSize = 1 << 16;
         else if (absz >= 16*1024*1024)
            mixersSize = 1 << 15;
         else if (absz >= 8*1024*1024)
            mixersSize = 1 << 14;
         else if (absz >= 4*1024*1024)
            mixersSize = 1 << 13;
         else
            mixersSize = (absz >= 1024*1024) ? 1 << 11 : 1 << 8;

         bufferSize = Math.min(BUFFER_SIZE, rbsz);
         hashSize = Math.min(hashSize, 16*absz);
      }

      mixersSize <<= (2*extraMem);
      statesSize <<= (2*extraMem);
      hashSize <<= (2*extraMem);

      this.pr = 2048;
      this.c0 = 1;
      this.bpos = 8;
      this.mixers = new Mixer[mixersSize];

      for (int i=0; i<this.mixers.length; i++)
         this.mixers[i] = new Mixer();

      this.mixer = this.mixers[0];
      this.bigStatesMap = new byte[statesSize];
      this.smallStatesMap0 = new byte[1<<16];
      this.smallStatesMap1 = new byte[1<<24];
      this.hashes = new int[hashSize];
      this.buffer = new byte[bufferSize];
      this.statesMask = this.bigStatesMap.length - 1;
      this.mixersMask = (this.mixers.length - 1) & ~1;
      this.hashMask = this.hashes.length - 1;
      this.bufferMask = this.buffer.length - 1;
      this.sse0 = (this.extra == true) ? new LogisticAdaptiveProbMap(256, 6) :
         new LogisticAdaptiveProbMap(256, 7);
      this.sse1 = (this.extra == true) ? new LogisticAdaptiveProbMap(65536, 7) : null;
   }


   // Update the probability model
   @Override
   public void update(int bit)
   {
     this.mixer.update(bit);
     this.bpos--;
     this.c0 = (this.c0 << 1) | bit;

     if (this.c0 > 255)
     {
        this.buffer[this.pos&this.bufferMask] = (byte) this.c0;
        this.pos++;
        this.c8 = (this.c8<<8) | (this.c4>>>24);
        this.c4 = (this.c4<<8) | (this.c0&0xFF);
        this.hash = (((this.hash*HASH)<<4) + this.c4) & this.hashMask;
        this.c0 = 1;
        this.bpos = 8;
        this.binCount += ((this.c4>>7) & 1);

        // Select Neural Net
        this.mixer = this.mixers[(this.c4&this.mixersMask) | ((this.matchLen!=0) ? 1 : 0)];

        // Add contexts to NN
        this.ctx0 = (this.c4&0xFF) << 8;
        this.ctx1 = (this.c4&0xFFFF) << 8;
        this.ctx2 = createContext(2, this.c4&0x00FFFFFF);
        this.ctx3 = createContext(3, this.c4);

        if (this.binCount < (this.pos>>2))
        {
           // Mostly text or mixed
           this.ctx4 = createContext(this.ctx1, this.c4^(this.c8&0xFFFF));
           this.ctx5 = (this.c8&MASK_F0F0F000) | ((this.c4&MASK_F0F0F000)>>4);

           if (this.extra == true)
           {
               final int h1 = ((this.c4&MASK_80808080) == 0) ? this.c4&MASK_4F4FFFFF : this.c4&MASK_80808080;
               final int h2 = ((this.c8&MASK_80808080) == 0) ? this.c8&MASK_4F4FFFFF : this.c8&MASK_80808080;
               this.ctx6 = hash(h1<<2, h2>>2);
           }
        }
        else
        {
           // Mostly binary
           this.ctx4 = createContext(HASH+this.matchLen, this.c4^(this.c4&0x000FFFFF));
           this.ctx5 = this.ctx0 | (this.c8<<16);

           if (this.extra == true)
               this.ctx6 = hash(this.c4&MASK_FFFF0000, this.c8>>16);
        }

        this.findMatch();

        // Keep track of current position
        this.hashes[this.hash] = this.pos;
      }

      // Get initial predictions
      // It has been observed that accessing memory via [ctx ^ c] is significantly faster
      // on SandyBridge/Windows and slower on SkyLake/Linux except when [ctx & 255 == 0]
      // (with c < 256). Hence, use XOR for _ctx5 which is the only context that fulfills
      // the condition.
      final int c = this.c0;
      final int mask = this.statesMask;
      final byte[] bst = this.bigStatesMap;
      final byte[] sst0 = this.smallStatesMap0;
      final byte[] sst1 = this.smallStatesMap1;
      final byte[] table = STATE_TRANSITIONS[bit];
      sst0[this.cp0] = table[sst0[this.cp0]&0xFF];
      sst1[this.cp1] = table[sst1[this.cp1]&0xFF];
      bst[this.cp2] = table[bst[this.cp2]&0xFF];
      bst[this.cp3] = table[bst[this.cp3]&0xFF];
      bst[this.cp4] = table[bst[this.cp4]&0xFF];
      bst[this.cp5] = table[bst[this.cp5]&0xFF];
      this.cp0 = this.ctx0 + c;
      final int p0 = STATE_MAP[sst0[this.cp0]&0xFF];
      this.cp1 = this.ctx1 + c;
      final int p1 = STATE_MAP[sst1[this.cp1]&0xFF];
      this.cp2 = (this.ctx2 + c) & mask;
      final int p2 = STATE_MAP[bst[this.cp2]&0xFF];
      this.cp3 = (this.ctx3 + c) & mask;
      final int p3 = STATE_MAP[bst[this.cp3]&0xFF];
      this.cp4 = (this.ctx4 + c) & mask;
      final int p4 = STATE_MAP[bst[this.cp4]&0xFF];
      this.cp5 = (this.ctx5 ^ c) & mask;
      final int p5 = STATE_MAP[bst[this.cp5]&0xFF];

      final int p7 = (this.matchLen == 0) ? 0 : this.getMatchContextPred();
      int p;

      if (this.extra == false)
      {
         // Mix predictions using NN
         p = this.mixer.get(p0, p1, p2, p3, p4, p5, p7, p7);

         // SSE (Secondary Symbol Estimation)
         if (this.binCount < (this.pos>>3))
            p = (3*this.sse0.get(bit, p, this.c0) + p) >> 2;
      }
      else
      {
         // One more prediction
         bst[this.cp6] = table[bst[this.cp6]&0xFF];
         this.cp6 = (this.ctx6 + c) & mask;
         final int p6 = STATE_MAP[bst[this.cp6]&0xFF];

         // Mix predictions using NN
         p = this.mixer.get(p0, p1, p2, p3, p4, p5, p6, p7);

         // SSE (Secondary Symbol Estimation)
         if (this.binCount < (this.pos>>3))
         {
            p = this.sse1.get(bit, p, this.ctx0+c);
         }
         else
         {
            if (this.binCount >= (this.pos>>2))
               p = (3*this.sse0.get(bit, p, this.c0) + p) >> 2;

            p = (3*this.sse1.get(bit, p, this.ctx0+c) + p) >> 2;
         }
      }

      this.pr = p + ((p-2048) >>> 31);
   }


   private void findMatch()
   {
      // Update ongoing sequence match or detect match in the buffer (LZ like)
      if (this.matchLen > 0)
      {
         this.matchLen += ((this.matchLen - MAX_LENGTH) >>> 31);
         this.matchPos++;
      }
      else
      {
         // Retrieve match position
         this.matchPos = this.hashes[this.hash];

         // Detect match
         if ((this.matchPos != 0) && (this.pos - this.matchPos <= this.bufferMask))
         {
            int r = this.matchLen + 2;
            int s = this.pos - r;
            int t = this.matchPos - r;

            while (r <= MAX_LENGTH)
            {
               if (this.buffer[(s-1)&this.bufferMask] != this.buffer[(t-1)&this.bufferMask])
                  break;

               if (this.buffer[s&this.bufferMask] != this.buffer[t&this.bufferMask])
                  break;

               r += 2;
               s -= 2;
               t -= 2;
            }

            this.matchLen = r - 2;
         }
      }
   }


   // Get a prediction from the match model in [-2047..2048]
   private int getMatchContextPred()
   {
      if (this.c0 == ((this.buffer[this.matchPos&this.bufferMask]&0xFF) | 256) >> this.bpos)
      {
         return (((this.buffer[this.matchPos&this.bufferMask] >> (this.bpos-1)) & 1) != 0) ?
            MATCH_PRED[this.matchLen-1] : -MATCH_PRED[this.matchLen-1];
      }

      this.matchLen = 0;
      return 0;
   }


   private static int createContext(int ctxId, int cx)
   {
      cx = cx*987654323 + ctxId;
      cx = (cx << 16) | (cx >>> 16);
      return cx*123456791 + ctxId;
   }


   // Return the split value representing the probability of 1 in the [0..4095] range.
   @Override
   public int get()
   {
      return this.pr;
   }


   // Mixer combines models using a neural network with 8 inputs.
   static class Mixer
   {
      private static final int BEGIN_LEARN_RATE = 60 << 7;
      static final int END_LEARN_RATE = 11 << 7;  // 8 << 7 for text, else 14 << 7

      private int pr;  // squashed prediction
      private int skew;
      private int w0, w1, w2, w3, w4, w5, w6, w7;
      private int p0, p1, p2, p3, p4, p5, p6, p7;
      private int learnRate;


      Mixer()
      {
         this.pr = 2048;
         this.w0 = this.w1 = this.w2 = this.w3 = 32768;
         this.w4 = this.w5 = this.w6 = this.w7 = 32768;
         this.learnRate = BEGIN_LEARN_RATE;
      }


      // Adjust weights to minimize coding cost of last prediction
      void update(int bit)
      {
         final int err = (((bit<<12) - this.pr) * this.learnRate) >> 10;

         if (err == 0)
            return;

         // Quickly decaying learn rate
         this.learnRate += ((END_LEARN_RATE-this.learnRate)>>31);
         this.skew += err;

         // Train Neural Network: update weights
         this.w0 += ((this.p0*err + 0) >> 12);
         this.w1 += ((this.p1*err + 0) >> 12);
         this.w2 += ((this.p2*err + 0) >> 12);
         this.w3 += ((this.p3*err + 0) >> 12);
         this.w4 += ((this.p4*err + 0) >> 12);
         this.w5 += ((this.p5*err + 0) >> 12);
         this.w6 += ((this.p6*err + 0) >> 12);
         this.w7 += ((this.p7*err + 0) >> 12);
      }


      public int get(int p0, int p1, int p2, int p3, int p4, int p5, int p6, int p7)
      {
         this.p0 = p0;
         this.p1 = p1;
         this.p2 = p2;
         this.p3 = p3;
         this.p4 = p4;
         this.p5 = p5;
         this.p6 = p6;
         this.p7 = p7;

         // Neural Network dot product (sum weights*inputs)
         this.pr = Global.squash((this.w0*p0 + this.w1*p1 + this.w2*p2 + this.w3*p3 +
                                  this.w4*p4 + this.w5*p5 + this.w6*p6 + this.w7*p7 +
                                  this.skew  + 65536) >> 17);

         return this.pr;
      }
   }

}
import kanzi.BitStreamException;
import kanzi.entropy.BinaryEntropyDecoder;
import kanzi.entropy.BinaryEntropyEncoder;
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.util.Random;
import kanzi.EntropyDecoder;
import kanzi.EntropyEncoder;
import kanzi.InputBitStream;
import kanzi.OutputBitStream;
import kanzi.bitstream.DebugOutputBitStream;
import kanzi.bitstream.DefaultInputBitStream;
import kanzi.bitstream.DefaultOutputBitStream;
import kanzi.entropy.ANSRangeDecoder;
import kanzi.entropy.ANSRangeEncoder;
import kanzi.entropy.CMPredictor;
import kanzi.entropy.ExpGolombDecoder;
import kanzi.entropy.ExpGolombEncoder;
import kanzi.entropy.HuffmanDecoder;
import kanzi.entropy.HuffmanEncoder;
import kanzi.Predictor;
import kanzi.entropy.FPAQDecoder;
import kanzi.entropy.FPAQEncoder;
import kanzi.entropy.RangeDecoder;
import kanzi.entropy.RangeEncoder;
import kanzi.entropy.RiceGolombDecoder;
import kanzi.entropy.RiceGolombEncoder;
import kanzi.entropy.TPAQPredictor;
import org.junit.Assert;
import org.junit.Test;
/*
Copyright 2011-2021 Frederic Langlet
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
you may obtain a copy of the License at

                http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/

package kanzi.test;



public class TestEntropyCodec
{
    public static void main(String[] args)
    {
       if (args.length == 0)
       {
          args = new String[] { "-TYPE=ALL" };
       }

       String type = args[0].toUpperCase();

       if (type.startsWith("-TYPE="))
       {
           type = type.substring(6);
           System.out.println("Codec: " + type);

           if (type.equals("ALL"))
           {
              System.out.println("\n\nTest Huffman Codec");

              if (testCorrectness("HUFFMAN") == false)
                System.exit(1);

              testSpeed("HUFFMAN", 200);
              System.out.println("\n\nTest ANS0 Codec");

              if (testCorrectness("ANS0") == false)
                System.exit(1);

              testSpeed("ANS0", 200);
              System.out.println("\n\nTest ANS1 Codec");

              if (testCorrectness("ANS1") == false)
                System.exit(1);

              testSpeed("ANS1", 150);
              System.out.println("\n\nTest Range Codec");

              if (testCorrectness("RANGE")== false)
                System.exit(1);

              testSpeed("RANGE", 150);
              System.out.println("\n\nTest FPAQ Codec");

              if (testCorrectness("FPAQ") == false)
                System.exit(1);

              testSpeed("FPAQ", 120);
              System.out.println("\n\nTest CM Codec");

              if (testCorrectness("CM") == false)
                System.exit(1);

              testSpeed("CM", 100);
              System.out.println("\n\nTestTPAQCodec");

              if (testCorrectness("TPAQ") == false)
                System.exit(1);

              testSpeed("TPAQ", 75);
              System.out.println("\n\nTestExpGolombCodec");

              if (testCorrectness("EXPGOLOMB") == false)
                System.exit(1);

              testSpeed("EXPGOLOMB", 150);
              System.out.println("\n\nTestRiceGolombCodec");

              if (testCorrectness("RICEGOLOMB") == false)
                System.exit(1);

              testSpeed("RICEGOLOMB", 150);
           }
           else
           {
              System.out.println("Test " + type + " Codec");
              testCorrectness(type);
              testSpeed(type, 100);
           }
       }
    }

   @Test
   public void testEntropy()
   {
      System.out.println("\n\nTest Huffman Codec");
      Assert.assertTrue(testCorrectness("HUFFMAN"));
      //testSpeed("HUFFMAN");
      System.out.println("\n\nTest ANS0 Codec");
      Assert.assertTrue(testCorrectness("ANS0"));
      //testSpeed("ANS0");
      System.out.println("\n\nTest ANS1 Codec");
      Assert.assertTrue(testCorrectness("ANS1"));
      //testSpeed("ANS1");
      System.out.println("\n\nTest Range Codec");
      Assert.assertTrue(testCorrectness("RANGE"));
      //testSpeed("RANGE");
      System.out.println("\n\nTest FPAQ Codec");
      Assert.assertTrue(testCorrectness("FPAQ"));
      //testSpeed("FPAQ");
      System.out.println("\n\nTest CM Codec");
      Assert.assertTrue(testCorrectness("CM"));
      //testSpeed("CM");
      System.out.println("\n\nTest TPAQ Codec");
      Assert.assertTrue(testCorrectness("TPAQ"));
      //testSpeed("TPAQ");
      System.out.println("\n\nTest ExpGolomb Codec");
      Assert.assertTrue(testCorrectness("EXPGOLOMB"));
      //testSpeed("EXPGOLOMB");
      System.out.println("\n\nTest RiceGolomb Codec");
      Assert.assertTrue(testCorrectness("RICEGOLOMB"));
      //testSpeed("RICEGOLOMB");
   }


   private static Predictor getPredictor(String type)
   {
      if (type.equals("TPAQ"))
         return new TPAQPredictor(null);

      if (type.equals("CM"))
         return new CMPredictor();

      return null;
   }


   private static EntropyEncoder getEncoder(String name, OutputBitStream obs)
   {
      switch(name)
      {
         case "CM":
         case "TPAQ":
            return new BinaryEntropyEncoder(obs, getPredictor(name));

         case "FPAQ":
            return new FPAQEncoder(obs);

         case "HUFFMAN":
            return new HuffmanEncoder(obs);

         case "ANS0":
            return new ANSRangeEncoder(obs, 0);

         case "ANS1":
            return new ANSRangeEncoder(obs, 1);

         case "RANGE":
            return new RangeEncoder(obs);