/*
 * @(#) arthpack.java - Simple demo Arithmetic compression utility.
 * (c) 1998 Ivan Maidanski <ivmai@chat.ru> http://ivmai.chat.ru
 * Freeware program source. All rights reserved.
 **
 * Language: Java [pure]
 * Tested with: JDK v1.1.6
 * Last modified: 1998-11-17 10:50:00 GMT+03:00
 */

/*
 * This software is the proprietary information of the author.
 **
 * Permission to use, copy, and distribute this software and its
 * documentation for non-commercial purposes and without fee is
 * hereby granted provided that this copyright notice appears in all
 * copies.
 **
 * This software should not be modified in any way; any found bug
 * should be reported to the author.
 **
 * The author disclaims all warranties with regard to this software,
 * including all implied warranties of merchantability and fitness.
 * In no event shall the author be liable for any special, indirect
 * or consequential damages or any damages whatsoever resulting from
 * loss of use, data or profits, whether in an action of contract,
 * negligence or other tortuous action, arising out of or in
 * connection with the use or performance of this software.
 */

import java.io.*;

import ivmai.util.JavaConsts;
import ivmai.util.UnsignedInt;

/**
 * Simple demo Arithmetic compression utility.
 **
 * @version 2.0
 * @author Ivan Maidanski
 */
public final class arthpack
{

 public static final String NAME = "arthpack";

 public static final String VERSION = "2.0";

 public static final String DESCRIPTION =
  "Simple demo Arithmetic compression utility";

 public static final String COPYRIGHT =
  "(c) 1998 Ivan Maidanski <ivmai@chat.ru> http://ivmai.chat.ru";

 public static final String LICENSE =
  "Freeware demo program. No warranty or liability." +
  " All rights reserved.";

 public static final String ARGS_INFO =
  "[e|d] <input_file> <output_file>";

 protected static final int FREQ_INC_VALUE = 3;

 private arthpack() {}

 public static final void main(String[] args)
  throws NullPointerException
 {
  int exitCode;
  try
  {
   exitCode = intMain(args);
  }
  catch (OutOfMemoryError e)
  {
   System.err.println("Out of memory!");
   exitCode = 255;
  }
  try
  {
   Runtime.getRuntime().exit(exitCode);
  }
  catch (SecurityException e) {}
  exitCode = 0;
 }

 public static int intMain(String[] args)
  throws NullPointerException
 {
  if (args.length != 3 || args[0].length() != 1)
  {
   System.out.println(NAME + " v" + VERSION + " - " + DESCRIPTION);
   System.out.println(COPYRIGHT);
   System.out.println(LICENSE);
   System.out.println("");
   System.out.println("Usage: " + NAME + " " + ARGS_INFO);
   return 1;
  }
  char cmdCh = args[0].charAt(0);
  boolean compression = true;
  if (cmdCh == 'D' || cmdCh == 'd')
   compression = false;
  InputStream in;
  try
  {
   in = new BufferedInputStream(new FileInputStream(args[1]));
  }
  catch (IOException e)
  {
   System.err.println("Cannot open input file: " + args[1]);
   return 2;
  }
  catch (SecurityException e)
  {
   return 2;
  }
  OutputStream out;
  try
  {
   out = new BufferedOutputStream(new FileOutputStream(args[2]));
  }
  catch (IOException e)
  {
   System.err.println("Cannot create output file: " + args[2]);
   return 3;
  }
  catch (SecurityException e)
  {
   return 3;
  }
  try
  {
   if (compression)
    out = new ChecksummedOutputStream(new arthpack1(out));
    else in = new ChecksummedInputStream(new arthpack2(in));
   for (int v; (v = in.read()) >= 0; out.write(v));
   try
   {
    in.close();
   }
   catch (IOException e) {}
   out.close();
  }
  catch (StreamCorruptedException e)
  {
   System.err.println("Error: CRC32 checksum failed");
   return 6;
  }
  catch (IOException e)
  {
   System.err.println("Error: I/O exception detected");
   return 5;
  }
  return 0;
 }
}

/**
 * Basis class for int-value-oriented output streams.
 **
 * @version 1.1
 * @author Ivan Maidanski
 */
class IntDataOutputStream extends OutputStream
 implements DataOutput
{

 protected static final int UTF_MAX_LEN =
  ~(-1 << JavaConsts.SHORT_SIZE);

 protected static final int UTF_MIN_SECOND =
  1 << (JavaConsts.BYTE_SIZE - 1);

 protected static final int UTF_MIN_THIRD =
  1 << ((JavaConsts.BYTE_SIZE << 1) - 5);

 protected static final int UTF_THIRD_TAG = UTF_MIN_SECOND;

 protected static final int UTF_THIRD_MASK =
  (UTF_THIRD_TAG >>> 1) - 1;

 protected static final int UTF_SECOND_SHIFT =
  JavaConsts.BYTE_SIZE - 2;

 protected static final int UTF_SECOND_TAG =
  UTF_THIRD_TAG | (UTF_THIRD_TAG >>> 1);

 protected static final int UTF_FIRST_SHIFT =
  JavaConsts.CHAR_SIZE - JavaConsts.BYTE_SIZE + 4;

 protected static final int UTF_FIRST_TAG =
  UTF_THIRD_TAG | (UTF_SECOND_TAG >>> 1);

 protected static final int UTF_MIDDLE_SHIFT = UTF_SECOND_SHIFT;

 protected static final int UTF_MIDDLE_TAG =
  1 << (JavaConsts.CHAR_SIZE - (JavaConsts.BYTE_SIZE << 1) + 7);

 protected static final int UTF_MIDDLE_MASK =
  (UTF_MIDDLE_TAG >>> 1) - 1;

 protected static final int UTF_MIDDLE_MAX =
  (UTF_MIDDLE_TAG << 1) - 1;

 protected final OutputStream out;

 public IntDataOutputStream(OutputStream out)
  throws NullPointerException
 {
  (this.out = out).equals(out);
 }

 public final void write(int value)
  throws IOException
 {
  writeInt(value & JavaConsts.BYTE_MASK, JavaConsts.BYTE_MASK);
 }

 public final void write(byte[] bytes)
  throws NullPointerException, IOException
 {
  write(bytes, 0, bytes.length);
 }

 public final void write(byte[] bytes, int offset, int len)
  throws NullPointerException, ArrayIndexOutOfBoundsException,
         IOException
 {
  int value = bytes.length;
  if (len > 0)
  {
   value = bytes[offset] | bytes[offset + len - 1];
   do
   {
    writeInt(bytes[offset++] & JavaConsts.BYTE_MASK,
     JavaConsts.BYTE_MASK);
   } while (--len > 0);
  }
 }

 public final void flush()
  throws IOException
 {
  this.out.flush();
 }

 public final void close()
  throws IOException
 {
  finish();
  this.out.close();
 }

 public final void writeBoolean(boolean v)
  throws IOException
 {
  writeInt(v ? 1 : 0, 1);
 }

 public final void writeByte(int v)
  throws IOException
 {
  writeInt(v & JavaConsts.BYTE_MASK, JavaConsts.BYTE_MASK);
 }

 public final void writeShort(int v)
  throws IOException
 {
  writeInt(v & JavaConsts.SHORT_MASK, JavaConsts.SHORT_MASK);
 }

 public final void writeChar(int v)
  throws IOException
 {
  writeInt(v & JavaConsts.CHAR_MASK, JavaConsts.CHAR_MASK);
 }

 public final void writeInt(int v)
  throws IOException
 {
  writeInt(v, -1);
 }

 public final void writeLong(long v)
  throws IOException
 {
  writeLong(v, -1L);
 }

 public final void writeFloat(float v)
  throws IOException
 {
  writeInt(Float.floatToIntBits(v), -1);
 }

 public final void writeDouble(double v)
  throws IOException
 {
  writeLong(Double.doubleToLongBits(v), -1L);
 }

 public final void writeBytes(String s)
  throws NullPointerException, IOException
 {
  for (int index = 0, len = s.length(); len-- > 0; index++)
   writeInt(s.charAt(index) & JavaConsts.BYTE_MASK,
    JavaConsts.BYTE_MASK);
 }

 public final void writeChars(String s)
  throws NullPointerException, IOException
 {
  for (int index = 0, len = s.length(); len-- > 0; index++)
   writeInt(s.charAt(index), JavaConsts.CHAR_MASK);
 }

 public final void writeUTF(String str)
  throws NullPointerException, IOException
 {
  int strlen = str.length(), utflen = strlen;
  if (utflen <= UTF_MAX_LEN)
  {
   int c, len = strlen;
   utflen <<= 1;
   while (len-- > 0)
    if ((c = str.charAt(len)) != 0 && c < UTF_MIN_SECOND)
     utflen--;
     else if (c >= UTF_MIN_THIRD)
      utflen++;
  }
  if (utflen > UTF_MAX_LEN)
   throw new UTFDataFormatException();
  writeInt(utflen, UTF_MAX_LEN);
  for (int c, index = 0; index < strlen; index++)
   if ((c = str.charAt(index)) != 0 && c < UTF_MIN_SECOND)
    writeInt(c, JavaConsts.BYTE_MASK);
    else
    {
     if (c >= UTF_MIN_THIRD)
     {
      writeInt((c >>> UTF_FIRST_SHIFT) | UTF_FIRST_TAG,
       JavaConsts.BYTE_MASK);
      writeInt((c >>> UTF_MIDDLE_SHIFT) & UTF_MIDDLE_MASK |
       UTF_MIDDLE_TAG, UTF_MIDDLE_MAX);
     }
      else writeInt((c >>> UTF_SECOND_SHIFT) | UTF_SECOND_TAG,
            JavaConsts.BYTE_MASK);
     writeInt(c & UTF_THIRD_MASK | UTF_THIRD_TAG,
      JavaConsts.BYTE_MASK);
    }
 }

 public final void writeBits(int v, int count)
  throws IOException
 {
  if (count > 0)
  {
   count = count < JavaConsts.INT_SIZE ? ~(-1 << count) : -1;
   writeInt(v & count, count);
  }
 }

 public final void writeLongBits(long v, int count)
  throws IOException
 {
  if (count > 0)
  {
   long mask = -1L;
   if (count < JavaConsts.LONG_SIZE)
    mask = ~(-1L << count);
   writeLong(v & mask, mask);
  }
 }

 public void writeLong(long unsignedValue, long unsignedMax)
  throws IllegalArgumentException, IOException
 {
  if (JavaConsts.INT_SIZE < JavaConsts.LONG_SIZE)
  {
   if (((unsignedMax ^ unsignedValue) >= 0L ?
       unsignedMax - unsignedValue : unsignedValue) < 0L)
    throw new IllegalArgumentException(
               "unsignedValue > unsignedMax");
   int shift = 0, val, max;
   for (long limit = unsignedMax; limit != 0L;
        limit >>>= JavaConsts.INT_SIZE,
        shift += JavaConsts.INT_SIZE);
   while ((shift -= JavaConsts.INT_SIZE) >= 0)
   {
    writeInt(val = (int)(unsignedValue >>> shift),
     max = (int)(unsignedMax >>> shift));
    if (max != val)
     unsignedMax = -1L;
   }
  }
   else writeInt((int)unsignedValue, (int)unsignedMax);
 }

/**
 * This is a core write function.
 */
 public void writeInt(int unsignedValue, int unsignedMax)
  throws IllegalArgumentException, IOException
 {
  if (((unsignedMax ^ unsignedValue) >= 0 ?
      unsignedMax - unsignedValue : unsignedValue) < 0)
   throw new IllegalArgumentException(
              "unsignedValue > unsignedMax");
  int shift = 0;
  while (unsignedMax != 0)
  {
   unsignedMax >>>= JavaConsts.BYTE_SIZE;
   shift += JavaConsts.BYTE_SIZE;
  }
  OutputStream out = this.out;
  while ((shift -= JavaConsts.BYTE_SIZE) >= 0)
   out.write(unsignedValue >>> shift);
 }

 public boolean finish()
  throws IOException
 {
  return false;
 }
}

/**
 * Basis class for int-value-oriented input streams.
 **
 * @version 1.1
 * @author Ivan Maidanski
 */
class IntDataInputStream extends InputStream
 implements DataInput
{

 protected static final int UTF_FIRST_TAG_MASK =
  IntDataOutputStream.UTF_THIRD_TAG |
  (IntDataOutputStream.UTF_FIRST_TAG >>> 1);

 protected static final int UTF_MIDDLE_TAG_MASK =
  IntDataOutputStream.UTF_MIDDLE_TAG |
  (IntDataOutputStream.UTF_MIDDLE_TAG >>> 1);

 protected final InputStream in;

 public IntDataInputStream(InputStream in)
  throws NullPointerException
 {
  (this.in = in).equals(in);
 }

 public final int read()
  throws IOException
 {
  int value = -1;
  try
  {
   value = readInt(JavaConsts.BYTE_MASK);
  }
  catch (EOFException e) {}
  return value;
 }

 public final int read(byte[] bytes)
  throws NullPointerException, IOException
 {
  return read(bytes, 0, bytes.length);
 }

 public final int read(byte[] bytes, int offset, int len)
  throws NullPointerException, ArrayIndexOutOfBoundsException,
         IOException
 {
  int res = 0, value = bytes.length;
  if (len > 0)
  {
   value = bytes[offset] | bytes[offset + len - 1];
   try
   {
    while (len-- > 0)
    {
     bytes[offset++] = (byte)readInt(JavaConsts.BYTE_MASK);
     res++;
    }
   }
   catch (EOFException e)
   {
    if (res == 0)
     res--;
   }
   catch (IOException e)
   {
    if (res == 0)
     throw e;
   }
  }
  return res;
 }

 public final long skip(long n)
  throws IOException
 {
  long res = 0;
  try
  {
   while (n-- > 0L)
   {
    readInt(JavaConsts.BYTE_MASK);
    res++;
   }
  }
  catch (EOFException e) {}
  catch (IOException e)
  {
   if (res == 0)
    throw e;
  }
  return res;
 }

 public final int available()
  throws IOException
 {
  return this.in.available();
 }

 public void mark(int readlimit)
 {
  this.in.mark(readlimit);
 }

 public void reset()
  throws IOException
 {
  this.in.reset();
 }

 public final boolean markSupported()
 {
  return this.in.markSupported();
 }

 public final void close()
  throws IOException
 {
  this.in.close();
 }

 public final void readFully(byte[] bytes)
  throws NullPointerException, IOException
 {
  readFully(bytes, 0, bytes.length);
 }

 public final void readFully(byte[] bytes, int offset, int len)
  throws NullPointerException, ArrayIndexOutOfBoundsException,
         IOException
 {
  int value = bytes.length;
  if (len > 0)
  {
   value = bytes[offset] | bytes[offset + len - 1];
   do
   {
    bytes[offset++] = (byte)readInt(JavaConsts.BYTE_MASK);
   } while (--len > 0);
  }
 }

 public final int skipBytes(int n)
  throws IOException
 {
  int res = 0;
  while (n-- > 0)
  {
   readInt(JavaConsts.BYTE_MASK);
   res++;
  }
  return res;
 }

 public final boolean readBoolean()
  throws IOException
 {
  return readInt(1) != 0;
 }

 public final byte readByte()
  throws IOException
 {
  return (byte)readInt(JavaConsts.BYTE_MASK);
 }

 public final int readUnsignedByte()
  throws IOException
 {
  return readInt(JavaConsts.BYTE_MASK);
 }

 public final short readShort()
  throws IOException
 {
  return (short)readInt(JavaConsts.SHORT_MASK);
 }

 public final int readUnsignedShort()
  throws IOException
 {
  return readInt(JavaConsts.SHORT_MASK);
 }

 public final char readChar()
  throws IOException
 {
  return (char)readInt(JavaConsts.CHAR_MASK);
 }

 public final int readInt()
  throws IOException
 {
  return readInt(-1);
 }

 public final long readLong()
  throws IOException
 {
  return readLong(-1L);
 }

 public final float readFloat()
  throws IOException
 {
  return Float.intBitsToFloat(readInt(-1));
 }

 public final double readDouble()
  throws IOException
 {
  return Double.longBitsToDouble(readLong(-1L));
 }

 public final String readLine()
  throws IOException
 {
  int offset = 0, len;
  char[] chars = new char[len = 80];
  try
  {
   for (char ch; (ch = (char)readInt(JavaConsts.BYTE_MASK)) != '\n';
        chars[offset++] = ch)
    if (offset >= len)
    {
     if ((len += len >> 1) <= 0)
      len = -1 >>> 1;
     char[] newChars;
     System.arraycopy(chars, 0,
      newChars = new char[len], 0, offset);
     chars = newChars;
    }
  }
  catch (EOFException e)
  {
   if (offset == 0)
    return null;
  }
  if (offset > 0 && chars[offset - 1] == '\r')
   offset--;
  return new String(chars, 0, offset);
 }

 public final String readUTF()
  throws IOException
 {
  boolean error = false;
  int utflen = readInt(IntDataOutputStream.UTF_MAX_LEN), strlen = 0;
  char[] str = new char[utflen];
  for (int c; utflen > 0; str[strlen++] = (char)c, utflen--)
   if ((c = readInt(JavaConsts.BYTE_MASK)) == 0 ||
       c >= IntDataOutputStream.UTF_MIN_SECOND)
    if ((c & IntDataOutputStream.UTF_FIRST_TAG) ==
        IntDataOutputStream.UTF_SECOND_TAG)
    {
     if (utflen < 2)
      break;
     int c2 = readInt(JavaConsts.BYTE_MASK);
     if ((c2 & IntDataOutputStream.UTF_SECOND_TAG) !=
         IntDataOutputStream.UTF_THIRD_TAG)
      error = true;
     c = ((c - IntDataOutputStream.UTF_SECOND_TAG) <<
      IntDataOutputStream.UTF_SECOND_SHIFT) |
      (c2 & IntDataOutputStream.UTF_THIRD_MASK);
     utflen--;
    }
     else if ((c & UTF_FIRST_TAG_MASK) ==
              IntDataOutputStream.UTF_FIRST_TAG)
     {
      if (utflen < 3)
       break;
      int c2 = readInt(IntDataOutputStream.UTF_MIDDLE_MAX);
      int c3 = readInt(JavaConsts.BYTE_MASK);
      if ((c2 & UTF_MIDDLE_TAG_MASK) !=
          IntDataOutputStream.UTF_MIDDLE_TAG ||
          (c3 & IntDataOutputStream.UTF_SECOND_TAG) !=
          IntDataOutputStream.UTF_THIRD_TAG)
       error = true;
      c = ((c - IntDataOutputStream.UTF_FIRST_TAG) <<
       IntDataOutputStream.UTF_FIRST_SHIFT) |
       ((c2 - IntDataOutputStream.UTF_MIDDLE_TAG) <<
       IntDataOutputStream.UTF_MIDDLE_SHIFT) |
       (c3 & IntDataOutputStream.UTF_THIRD_MASK);
      utflen -= 2;
     }
      else error = true;
  if (error || utflen != 0)
   throw new UTFDataFormatException();
  return new String(str, 0, strlen);
 }

 public final int readBits(int count)
  throws IOException
 {
  int bits = 0;
  if (count > 0)
  {
   bits = -1;
   if (count < JavaConsts.INT_SIZE)
    bits = ~(-1 << count);
   bits = readInt(bits);
  }
  return bits;
 }

 public final long readLongBits(int count)
  throws IOException
 {
  long bits = 0L;
  if (count > 0)
  {
   bits = -1L;
   if (count < JavaConsts.LONG_SIZE)
    bits = ~(-1L << count);
   bits = readLong(bits);
  }
  return bits;
 }

 public long readLong(long unsignedMax)
  throws IOException
 {
  if (JavaConsts.INT_SIZE >= JavaConsts.LONG_SIZE)
   return readInt((int)unsignedMax) & JavaConsts.INT_LMASK;
  long unsignedValue = unsignedMax;
  int shift = 0;
  while (unsignedValue != 0L)
  {
   unsignedValue >>>= JavaConsts.INT_SIZE;
   shift += JavaConsts.INT_SIZE;
  }
  while ((shift -= JavaConsts.INT_SIZE) >= 0)
  {
   int val, max = (int)(unsignedMax >>> shift);
   if ((val = readInt(max)) != max)
    unsignedMax = -1L;
   unsignedValue = val & JavaConsts.INT_LMASK |
    (unsignedValue << JavaConsts.INT_SIZE);
  }
  return unsignedValue;
 }

/**
 * This is a core read function.
 */
 public int readInt(int unsignedMax)
  throws IOException
 {
  int unsignedValue = 0;
  InputStream in = this.in;
  for (int v, max = unsignedMax; max != 0; unsignedValue =
       v & JavaConsts.BYTE_MASK | (unsignedValue <<
       JavaConsts.BYTE_SIZE), max >>>= JavaConsts.BYTE_SIZE)
   if ((v = in.read()) < 0)
    throw new EOFException();
  if (((unsignedMax ^ unsignedValue) >= 0 ?
      unsignedMax - unsignedValue : unsignedValue) < 0)
   unsignedValue = unsignedMax;
  return unsignedValue;
 }

 public boolean finish()
 {
  return false;
 }
}

/**
 * Class for bit-oriented output stream.
 **
 * @version 1.1
 * @author Ivan Maidanski
 */
class OutputBitStream extends IntDataOutputStream
{

 protected byte bits;

 public OutputBitStream(OutputStream out)
  throws NullPointerException
 {
  super(out);
 }

 public void writeInt(int unsignedValue, int unsignedMax)
  throws IllegalArgumentException, IOException
 {
  if (((unsignedMax ^ unsignedValue) >= 0 ?
      unsignedMax - unsignedValue : unsignedValue) < 0)
   throw new IllegalArgumentException(
              "unsignedValue > unsignedMax");
  int size = 0;
  for (int max = unsignedMax; max != 0; max >>>= 1, size++);
  unsignedValue <<= JavaConsts.INT_SIZE - size;
  unsignedMax <<= JavaConsts.INT_SIZE - size;
  byte bits;
  if ((bits = this.bits) == 0)
   bits = 1;
  OutputStream out = this.out;
  while (size-- > 0)
  {
   if (unsignedMax < 0)
   {
    byte oldBits = bits;
    bits <<= 1;
    if (unsignedValue >= 0)
     unsignedMax = -1;
     else bits++;
    if (oldBits < 0)
    {
     out.write(bits);
     bits = 1;
    }
   }
   unsignedValue <<= 1;
   unsignedMax <<= 1;
  }
  this.bits = bits;
 }

 public boolean finish()
  throws IOException
 {
  byte bits;
  if ((bits = this.bits) == 0)
   return false;
  byte oldBits = bits;
  bits <<= 1;
  for (bits++; oldBits > 0; bits <<= 1)
   oldBits = bits;
  this.out.write(bits);
  this.bits = 0;
  return true;
 }
}

/**
 * Class for bit-oriented input stream.
 **
 * @version 1.1
 * @author Ivan Maidanski
 */
class InputBitStream extends IntDataInputStream
{

 protected byte bits;

 protected byte next;

 protected byte markbits;

 protected byte marknext;

 public InputBitStream(InputStream in)
  throws NullPointerException
 {
  super(in);
 }

 public void mark(int readlimit)
 {
  this.in.mark(readlimit);
  this.markbits = this.bits;
  this.marknext = this.next;
 }

 public void reset()
  throws IOException
 {
  this.in.reset();
  this.bits = this.markbits;
  this.next = this.marknext;
 }

 public int readInt(int unsignedMax)
  throws IOException
 {
  byte bits = this.bits, next = this.next;
  int unsignedValue, size = 0;
  if ((unsignedValue = unsignedMax) != 0)
   do
   {
    size++;
   } while ((unsignedValue >>>= 1) != 0);
  InputStream in = this.in;
  if ((bits | next) == 0)
  {
   next = (byte)(1 << (JavaConsts.BYTE_SIZE - 1));
   int v;
   if ((v = in.read()) < 0)
   {
    bits = next;
    next = 0;
   }
    else bits = (byte)v;
  }
  for (unsignedMax <<= JavaConsts.INT_SIZE - size;
       size-- > 0; unsignedMax <<= 1)
  {
   unsignedValue <<= 1;
   if (unsignedMax < 0)
   {
    int v = -1;
    if ((byte)(next << 1) == 0 && next < 0)
    {
     next = 0;
     if ((v = in.read()) >= 0)
      next = (byte)v;
    }
    if (v < 0 && (byte)((bits << 1) | next) == 0)
    {
     this.bits = (byte)(1 << (JavaConsts.BYTE_SIZE - 1));
     this.next = 0;
     throw new EOFException();
    }
    if (bits >= 0)
     unsignedMax = -1;
     else unsignedValue++;
    bits <<= 1;
    if (next < 0)
     bits++;
    next <<= 1;
    if (v >= 0)
     next++;
   }
  }
  this.bits = bits;
  this.next = next;
  return unsignedValue;
 }

/**
 * Finishes bit-stream. One additional raw byte is read here (to
 * detect end-of-stream properly), so if desired to continue reading
 * from the wrapped stream outside this class then one byte should
 * be unread manually (if and after finish() returns true).
 */
 public boolean finish()
 {
  byte bits, next = this.next;
  if (((bits = this.bits) | next) == 0)
   return false;
  if ((byte)(next << 1) == 0)
   bits = next = 0;
   else do
   {
    bits <<= 1;
    if (next < 0)
     bits++;
    next <<= 1;
   } while ((byte)(next << 1) != 0);
  this.bits = bits;
  this.next = next;
  return true;
 }
}

/**
 * Class for stream arithmetic encoding.
 **
 * @version 1.1
 * @author Ivan Maidanski
 */
class ArithEncoderStream extends IntDataOutputStream
{

 protected int low;

 protected int high;

 protected byte bits;

 protected boolean upper;

 public ArithEncoderStream(OutputStream out)
  throws NullPointerException
 {
  super(out);
 }

 public void writeInt(int unsignedValue, int unsignedMax)
  throws IllegalArgumentException, IOException
 {
  writeRange(unsignedValue, unsignedValue, unsignedMax);
 }

 public final void writeRange(int unsignedLow, int unsignedHigh,
         int unsignedMax)
  throws IllegalArgumentException, IOException
 {
  if ((((unsignedHigh ^ unsignedLow) >= 0 ?
      unsignedHigh - unsignedLow : unsignedLow) |
      ((unsignedMax ^ unsignedHigh) >= 0 ?
      unsignedMax - unsignedHigh : unsignedHigh)) < 0)
   throw new IllegalArgumentException(
              "Bad unsignedLow, unsignedHigh or unsignedMax");
  int low = this.low, high = this.high, range;
  OutputStream out = this.out;
  byte bits, oldBits;
  if ((bits = this.bits) == 0)
  {
   low = 0;
   high = -1;
   bits = 1;
  }
  low ^= ~high;
  do
  {
   while (low < 0)
   {
    oldBits = bits;
    bits <<= 1;
    if (high < 0)
     bits++;
    if (oldBits < 0)
    {
     this.low = ~(this.high = high) ^ low;
     this.bits = oldBits;
     out.write(bits);
     bits = 1;
    }
    low <<= 1;
    high <<= 1;
    high++;
   }
   if ((((range = high - (low ^= ~high)) ^ unsignedMax) >= 0 ?
       range - unsignedMax : unsignedMax) >= 0)
    break;
   high = ~high;
   for (range = ~(-1 >>> 1); ((low <<= 1) & (high <<= 1)) < 0;
        range >>= 1);
   if (high == 0)
    low = range;
    else if (low != 0)
    {
     low = range >>= 1;
     if (high < 0)
      low = 0;
    }
   high = low ^ (-1 >>> 1);
   low = range;
  } while (true);
  high = UnsignedInt.mulDiv(++range, unsignedHigh + 1,
   ++unsignedMax, false) + low - 1;
  this.upper = true;
  if (unsignedLow != 0)
  {
   this.upper = false;
   low += UnsignedInt.mulDiv(range, unsignedLow,
    unsignedMax, false);
  }
  this.low = low;
  this.high = high;
  this.bits = bits;
 }

 public boolean finish()
  throws IOException
 {
  if (this.bits == 0)
   return false;
  if (this.upper)
   this.low = this.high;
  this.high = this.low;
  writeRange(0, 0, 0);
  byte bits;
  byte oldBits = bits = this.bits;
  bits <<= 1;
  for (bits++; oldBits > 0; bits <<= 1)
   oldBits = bits;
  this.out.write(bits);
  this.bits = 0;
  return true;
 }
}

/**
 * Class for stream arithmetic decoding.
 **
 * @version 1.1
 * @author Ivan Maidanski
 */
class ArithDecoderStream extends IntDataInputStream
{

 protected int low;

 protected int code;

 protected int high;

 protected int marklow;

 protected int markcode;

 protected int markhigh;

 protected byte bits;

 protected byte next;

 protected byte markbits;

 protected byte marknext;

 protected boolean full;

 protected boolean markfull;

 public ArithDecoderStream(InputStream in)
  throws NullPointerException
 {
  super(in);
 }

 public void mark(int readlimit)
 {
  this.in.mark(readlimit);
  this.marklow = this.low;
  this.markcode = this.code;
  this.markhigh = this.high;
  this.markbits = this.bits;
  this.marknext = this.next;
  this.markfull = this.full;
 }

 public void reset()
  throws IOException
 {
  this.in.reset();
  this.low = this.marklow;
  this.code = this.markcode;
  this.high = this.markhigh;
  this.bits = this.markbits;
  this.next = this.marknext;
  this.full = this.markfull;
 }

 public int readInt(int unsignedMax)
  throws IOException
 {
  int unsignedValue = readRange(unsignedMax);
  updateRange(unsignedValue, unsignedValue, unsignedMax);
  return unsignedValue;
 }

 public final int readRange(int unsignedMax)
  throws IOException
 {
  int low = this.low, code = this.code, high = this.high, range;
  byte bits = this.bits, next = this.next;
  boolean full = this.full;
  InputStream in = this.in;
  if ((bits | next) == 0 && !full)
  {
   bits = (byte)(range = in.read());
   next = (byte)(1 << (JavaConsts.BYTE_SIZE - 1));
   if (range < 0)
   {
    bits = next;
    next = 0;
   }
   low = high = 0;
  }
  if ((byte)((bits | next) << 1) == 0 &&
      !full && (low == code || high == code))
  {
   range = -1;
   if (next != 0)
    range = in.read();
   if (range < 0)
   {
    this.bits = (byte)(1 << (JavaConsts.BYTE_SIZE - 1));
    this.next = 0;
    this.full = false;
    throw new EOFException();
   }
   next = (byte)range;
   full = true;
  }
  low ^= ~high;
  do
  {
   while (low < 0)
   {
    range = -1;
    if (full)
    {
     full = false;
     range = 0;
    }
    if ((byte)(next << 1) == 0 && (next & range) < 0)
    {
     this.low = ~(this.high = high) ^ low;
     this.code = code;
     this.bits = bits;
     this.next = next;
     this.full = false;
     next = 0;
     if ((range = in.read()) >= 0)
      next = (byte)range;
    }
    if ((byte)((bits << 1) | next) == 0 && range < 0)
    {
     this.bits = (byte)(1 << (JavaConsts.BYTE_SIZE - 1));
     this.next = 0;
     this.full = false;
     throw new EOFException();
    }
    code <<= 1;
    low <<= 1;
    high <<= 1;
    if (bits < 0)
     code++;
    high++;
    bits <<= 1;
    if (next < 0)
     bits++;
    next <<= 1;
    if (range >= 0)
     next++;
   }
   range = high - (low ^= ~high);
   if (((range ^ unsignedMax) >= 0 ?
       range - unsignedMax : unsignedMax) >= 0)
    break;
   high = ~high;
   for (range = ~(-1 >>> 1); ((low <<= 1) & (high <<= 1)) < 0;
        range >>= 1);
   if (low != 0 && high != 0)
    range >>= 1;
   high = -1 >>> 1;
   low = range;
  } while (true);
  this.low = low;
  this.code = code;
  this.high = high;
  this.bits = bits;
  this.next = next;
  this.full = full;
  return UnsignedInt.mulDiv(unsignedMax + 1, code - low + 1,
   range + 1, true) - 1;
 }

 public final void updateRange(int unsignedLow, int unsignedHigh,
         int unsignedMax)
  throws IllegalArgumentException
 {
  if ((((unsignedHigh ^ unsignedLow) >= 0 ?
      unsignedHigh - unsignedLow : unsignedLow) |
      ((unsignedMax ^ unsignedHigh) >= 0 ?
      unsignedMax - unsignedHigh : unsignedHigh)) >= 0)
  {
   int low = this.low, high, range;
   high = UnsignedInt.mulDiv(range = this.high - low + 1,
    unsignedHigh + 1, ++unsignedMax, false) + low - 1;
   if (unsignedLow != 0)
    low += UnsignedInt.mulDiv(range, unsignedLow,
     unsignedMax, false);
   range = this.code;
   if ((((range ^ low) >= 0 ? range - low : low) |
       ((high ^ range) >= 0 ? high - range : range)) >= 0)
   {
    this.low = low;
    this.high = high;
    return;
   }
  }
  throw new IllegalArgumentException(
             "Bad unsignedLow, unsignedHigh or unsignedMax");
 }

/**
 * Finishes decoder. One additional raw byte is read (to detect
 * end-of-stream properly), so if desired to continue reading from
 * the wrapped stream outside this class then one dummy byte should
 * be unread manually (if and after finish() returns true).
 */
 public boolean finish()
 {
  byte bits, next = this.next;
  if (((bits = this.bits) | next) == 0)
   return false;
  if (this.full)
  {
   bits = next;
   next = (byte)(1 << (JavaConsts.BYTE_SIZE - 1));
  }
   else if ((byte)(next << 1) == 0)
    bits = next = 0;
    else do
    {
     bits <<= 1;
     if (next < 0)
      bits++;
     next <<= 1;
    } while ((byte)(next << 1) != 0);
  this.low = this.high = 0;
  this.bits = bits;
  this.next = next;
  this.full = false;
  return true;
 }
}

/**
 * Class for CRC32 checksum calculations.
 **
 * @version 2.0
 * @author Ivan Maidanski
 */
final class CRC32Checksum
 implements Cloneable, Serializable
// java.util.Checksum
{

/**
 * The class version unique identifier for serialization
 * interoperability.
 **
 * @since 1.1
 */
 private static final long serialVersionUID = 844516443182505881L;

 public static final int SIZE = 32;

 public static final int POLYNOME = 0xEDB88320;

 private static final int[] TABLE =
  new int[JavaConsts.BYTE_MASK + 1];

 static
 {
  int[] table = TABLE;
  for (int crc, count, index = table.length;
       index-- > 0; table[index] = crc ^
       (JavaConsts.BYTE_MASK << (SIZE - JavaConsts.BYTE_SIZE)))
   for (crc = index, count = JavaConsts.BYTE_SIZE; count-- > 0;
        crc = (crc & 1) != 0 ? (crc >>> 1) ^ POLYNOME : crc >>> 1);
 }

/**
 * The current checksum value.
 **
 * @serial
 */
 protected int checksum;

 public CRC32Checksum() {}

 public static final int nextValue(int checksum, byte value)
 {
  return TABLE[(~value ^ checksum) & JavaConsts.BYTE_MASK] ^
   (checksum >>> JavaConsts.BYTE_SIZE);
 }

 public static final int nextValueInt(int checksum, int intValue)
 {
  int shift = JavaConsts.INT_SIZE;
  int[] table = TABLE;
  intValue = ~intValue;
  while ((shift -= JavaConsts.BYTE_SIZE) >= 0)
   checksum = table[((intValue >>> shift) ^ checksum) &
    JavaConsts.BYTE_MASK] ^ (checksum >>> JavaConsts.BYTE_SIZE);
  return checksum;
 }

/**
 * Resets checksum. Must be synchronized outside.
 */
 public void reset()
 {
  this.checksum = 0;
 }

/**
 * Updates checksum for a given byte. Must be synchronized outside.
 */
 public void update(int b)
 {
  this.checksum = nextValue(this.checksum, (byte)b);
 }

/**
 * Updates checksum for a given bytes region. bytes must not be
 * null. If exception is thrown then checksum is unchanged.
 * Negative len is treated as zero. bytes is not changed. Must be
 * synchronized outside.
 */
 public void update(byte[] bytes, int offset, int len)
  throws NullPointerException, ArrayIndexOutOfBoundsException
 {
  int checksum = bytes.length;
  if (len > 0)
  {
   checksum = this.checksum;
   do checksum = nextValue(checksum, bytes[offset++]);
    while (--len > 0);
   this.checksum = checksum;
  }
 }

 public final long getValue()
 {
  return this.checksum & JavaConsts.INT_LMASK;
 }

 public Object clone()
 {
  Object obj;
  try
  {
   if ((obj = super.clone()) instanceof CRC32Checksum &&
       obj != this)
    return obj;
  }
  catch (CloneNotSupportedException e) {}
  throw new InternalError("CloneNotSupportedException");
 }

 public int hashCode()
 {
  return this.checksum;
 }

 public boolean equals(Object obj)
 {
  return this == obj || obj instanceof CRC32Checksum &&
   ((CRC32Checksum)obj).checksum == this.checksum;
 }

 public String toString()
 {
  int digit, offset, checksum = this.checksum;
  char[] chars = new char[offset = ((SIZE - 1) >> 2) + 3];
  do
  {
   if ((digit = checksum & ((1 << 4) - 1)) > '9' - '0')
    digit += 'A' - '9' - 1;
   chars[--offset] = (char)(digit + '0');
   checksum >>>= 4;
  } while (offset > 2);
  chars[1] = 'x';
  chars[0] = '0';
  return new String(chars);
 }
}

/**
 * Class for output stream with CRC32 built-in checking.
 **
 * @version 1.1
 * @author Ivan Maidanski
 */
final class ChecksummedOutputStream extends FilterOutputStream
{

 protected int checksum;

 protected boolean finished;

 public ChecksummedOutputStream(OutputStream out)
  throws NullPointerException
 {
  super(out);
  out.equals(out);
 }

 public void write(int b)
  throws IOException
 {
  if (this.finished)
   throw new IOException("stream finished");
  this.out.write(b);
  this.checksum = CRC32Checksum.nextValue(this.checksum, (byte)b);
 }

 public void write(byte[] bytes, int offset, int len)
  throws NullPointerException, IndexOutOfBoundsException,
         IOException
 {
  if (this.finished)
   throw new IOException("stream finished");
  this.out.write(bytes, offset, len);
  while (len-- > 0)
   this.checksum =
    CRC32Checksum.nextValue(this.checksum, bytes[offset++]);
 }

 public final void close()
  throws IOException
 {
  finish();
  this.out.close();
 }

 public int finish()
  throws IOException
 {
  int checksum = this.checksum;
  if (!this.finished)
  {
   UnsignedInt.writeBits(this.out, checksum, CRC32Checksum.SIZE);
   this.finished = true;
  }
  return checksum;
 }
}

/**
 * Class for input stream with CRC32 built-in checking.
 **
 * @version 1.1
 * @author Ivan Maidanski
 */
final class ChecksummedInputStream extends FilterInputStream
{

 protected static final int SKIP_BUF_SIZE = 2048;

 protected int value;

 protected int checksum;

 protected int markvalue;

 protected int markchecksum;

 public ChecksummedInputStream(InputStream in)
  throws NullPointerException, IOException
 {
  super(in);
  this.markvalue = this.value =
   UnsignedInt.readBits(in, CRC32Checksum.SIZE);
 }

 public int read()
  throws IOException
 {
  int b;
  if ((b = this.in.read()) >= 0)
  {
   int v = b;
   b = (this.value >>> (CRC32Checksum.SIZE -
    JavaConsts.BYTE_SIZE)) & JavaConsts.BYTE_MASK;
   this.checksum = CRC32Checksum.nextValue(this.checksum, (byte)b);
   this.value = (this.value << JavaConsts.BYTE_SIZE) |
    v & JavaConsts.BYTE_MASK;
  }
   else finish();
  return b;
 }

 public int read(byte[] bytes, int offset, int len)
  throws NullPointerException, IndexOutOfBoundsException,
         IOException
 {
  if ((len = this.in.read(bytes, offset, len)) >= 0)
  {
   int value = this.value, checksum = this.checksum, count = len;
   while (count-- > 0)
   {
    byte v = bytes[offset];
    checksum = CRC32Checksum.nextValue(checksum, bytes[offset++] =
     (byte)(value >>> (CRC32Checksum.SIZE - JavaConsts.BYTE_SIZE)));
    value = (value << JavaConsts.BYTE_SIZE) |
     v & JavaConsts.BYTE_MASK;
   }
   this.value = value;
   this.checksum = checksum;
  }
   else finish();
  return len;
 }

 public final long skip(long n)
  throws IOException
 {
  if (n <= 0L)
   return 0L;
  int res;
  byte[] skipBuffer = new byte[SKIP_BUF_SIZE];
  long remaining = n;
  while ((res = read(skipBuffer, 0,
         remaining >= SKIP_BUF_SIZE ? SKIP_BUF_SIZE :
         (int)remaining)) >= 0 && (remaining -= res) > 0L);
  return n - remaining;
 }

 public void mark(int readlimit)
 {
  this.in.mark(readlimit);
  this.markvalue = this.value;
  this.markchecksum = this.checksum;
 }

 public void reset()
  throws IOException
 {
  this.in.reset();
  this.value = this.markvalue;
  this.checksum = this.markchecksum;
 }

 public int finish()
  throws IOException
 {
  int checksum;
  if ((checksum = this.checksum) != this.value)
   throw new StreamCorruptedException("CRC32 wrong");
  return checksum;
 }
}

/**
 * Class for vectors of cumulative integer sums.
 **
 * Cumulative vector is a special unsigned <CODE>int</CODE>
 * resizable array with the efficient (logarithmic) implementation
 * of cumulative partial summing. That is, it is possible to modify
 * or get any value (element) of this vector and to calculate the
 * sum of any its first elements or find out how many its first
 * elements should be summed to get a specified sum value (inverse
 * problem), using only special algorithms of logarithmic cost
 * ('binary tree'). This class is useful for representing frequency
 * tables (addition overflows are internally handled correctly by
 * halving each value of the cumulative vector). An object of this
 * class may be cloned and compactly serialized.
 **
 * @version 2.0
 * @author Ivan Maidanski
 */
final class CumVector
 implements Serializable, Cloneable
// ReallyCloneable, Indexable, Sortable, TrimToSizeable, Verifiable
{

/**
 * The class version unique identifier for serialization
 * interoperability.
 **
 * @since 1.8
 */
 private static final long serialVersionUID = 1771806595944220734L;

/**
 * An array containing partial sums (represented in a special form).
 **
 * <VAR>array</VAR> must be non-<CODE>null</CODE> and its
 * <CODE>length</CODE> must be a power of two. <VAR>array</VAR>
 * elements and capacity are serialized manually and cloned.
 **
 * @see CumVector#CumVector()
 * @see CumVector#CumVector(int)
 * @see #clone()
 * @see #integrityCheck()
 * @see #trimToSize()
 * @see #clear()
 * @see #clearAt(int)
 * @see #addAt(int, int)
 * @see #getIntAt(int)
 * @see #getCumSum(int)
 * @see #findSum(int)
 */
 private transient int[] array;

/**
 * Constructs an empty cumulative vector.
 **
 * All values in the constructed vector are set to zero.
 **
 * @exception OutOfMemoryError
 * if there is not enough memory.
 **
 * @see CumVector#CumVector(int)
 * @see #clone()
 * @see #trimToSize()
 * @see #clear()
 * @see #length()
 * @see #getTotalSum()
 * @see #addAt(int, int)
 * @see #getIntAt(int)
 * @see #getCumSum(int)
 * @see #findSum(int)
 */
 public CumVector()
 {
  this.array = new int[1 << 4];
 }

/**
 * Constructs an empty cumulative vector with the specified initial
 * capacity.
 **
 * All values in the constructed vector are set to zero (so, vector
 * 'size' is zero too). Important notes: negative or zero
 * <VAR>initialCapacity</VAR> is treated as 1.
 **
 * @param initialCapacity
 * the initial capacity minimal requirements for the vector being
 * created.
 * @exception OutOfMemoryError
 * if there is not enough memory.
 **
 * @see CumVector#CumVector()
 * @see #clone()
 * @see #trimToSize()
 * @see #clear()
 * @see #length()
 * @see #getTotalSum()
 * @see #addAt(int, int)
 * @see #getIntAt(int)
 * @see #getCumSum(int)
 * @see #findSum(int)
 */
 public CumVector(int initialCapacity)
 {
  int capacity = 1;
  if (initialCapacity > 1)
   if (--initialCapacity << 1 <= 0)
    capacity = -1 >>> 1;
    else while ((capacity <<= 1) <= initialCapacity);
  this.array = new int[capacity];
 }

/**
 * Frees extra memory.
 **
 * This method re-allocates <VAR>array</VAR>, setting its hidden
 * <CODE>length</CODE> (capacity of the vector) to the current
 * possible minimum (a power of two). This method must be
 * synchronized outside.
 **
 * @see CumVector#CumVector(int)
 * @see #clone()
 * @see #integrityCheck()
 * @see #clear()
 * @see #addAt(int, int)
 * @see #length()
 */
 public void trimToSize()
 {
  int[] array = this.array;
  int capacity, unsignedSum = array[capacity = array.length - 1];
  while (capacity > 0 && array[capacity >> 1] == unsignedSum)
   capacity >>= 1;
  if (++capacity < array.length)
  {
   try
   {
    int[] newArray;
    System.arraycopy(array, 0,
     newArray = new int[capacity], 0, capacity);
    this.array = newArray;
   }
   catch (OutOfMemoryError e) {}
   capacity = array.length;
  }
 }

/**
 * Returns the current vector size.
 **
 * The result is the same as of <CODE>findSum(-1)</CODE>. Important
 * notes: if the result is positive then
 * <CODE>getIntAt(result - 1)</CODE> is non-zero. The algorithm used
 * here is of logarithmic cost. This method must be synchronized
 * outside.
 **
 * @return
 * the current size (non-negative) of <CODE>this</CODE> vector.
 **
 * @see CumVector#CumVector(int)
 * @see #findSum(int)
 * @see #clear()
 * @see #addAt(int, int)
 * @see #getIntAt(int)
 * @see #getAt(int)
 * @see #getTotalSum()
 **
 * @since 1.8
 */
 public int length()
 {
  return findSum(-1);
 }

/**
 * Returns the wrapped value of the element at the specified index.
 **
 * @param index
 * the index (must be in the range) at which to return an element.
 * @return
 * an element (instance of <CODE>UnsignedInt</CODE>) at
 * <VAR>index</VAR>.
 * @exception ArrayIndexOutOfBoundsException
 * if <VAR>index</VAR> is negative or is greater or equal to
 * <CODE>length()</CODE>.
 * @exception OutOfMemoryError
 * if there is not enough memory.
 **
 * @see #getIntAt(int)
 * @see #length()
 **
 * @since 1.8
 */
 public Object getAt(int index)
  throws ArrayIndexOutOfBoundsException
 {
  int value;
  if ((value = getIntAt(index)) != 0 ||
      index >= 0 && findSum(-1) > index)
   return new UnsignedInt(value);
  throw new ArrayIndexOutOfBoundsException(index);
 }

/**
 * Clears <CODE>this</CODE> cumulative vector.
 **
 * All values are set to zero (as if <CODE>this</CODE> vector is
 * just constructed). Its capacity remains unchanged (but
 * <CODE>length()</CODE> for <CODE>this</CODE> vector becomes zero).
 * This method alters vector state. This method must be synchronized
 * outside.
 **
 * @see CumVector#CumVector(int)
 * @see #trimToSize()
 * @see #length()
 * @see #clearAt(int)
 * @see #addAt(int, int)
 * @see #getIntAt(int)
 **
 * @since 1.1
 */
 public void clear()
 {
  int[] array = this.array;
  int capacity = array.length, index = 0;
  do
  {
   array[index++] = 0;
  } while (index < capacity);
 }

/**
 * Resets value at the specified index of <CODE>this</CODE>
 * cumulative vector.
 **
 * A value at <VAR>index</vAR> is set to zero. This method alters
 * vector state (if an exception is thrown then the vector remains
 * unchanged). The algorithm used here is of logarithmic cost. This
 * method must be synchronized outside.
 **
 * @param index
 * the index (must be non-negative) at which to clear.
 * @exception ArrayIndexOutOfBoundsException
 * if <VAR>index</VAR> is negative.
 **
 * @see #clear()
 * @see #addAt(int, int)
 * @see #getIntAt(int)
 **
 * @since 1.1
 */
 public void clearAt(int index)
  throws ArrayIndexOutOfBoundsException
 {
  if (index < 0)
   throw new ArrayIndexOutOfBoundsException(index);
  int[] array = this.array;
  int unsignedValue, base, capacity;
  if ((capacity = array.length - 1) >= index &&
      (unsignedValue = array[index]) != 0)
  {
   for (base = 1; (index & base) != 0; base <<= 1)
    if ((unsignedValue -= array[index ^ base]) == 0)
     return;
   array[index] -= unsignedValue;
   for (base = 1; index < capacity; base <<= 1)
    if ((index & base) == 0)
     array[index ^= base] -= unsignedValue;
  }
 }

/**
 * Adds or subtracts a given value to/from the value at the
 * specified index.
 **
 * This is a core method of this cumulative vector. First of all
 * (after index check), enough capacity is ensured (even if
 * <VAR>incValue</VAR> is zero). Then, if <VAR>incValue</VAR> is
 * negative then subtraction is performed (if underflow occurs then
 * the resulting value is set to zero), else value addition is
 * performed (if addition overflow may occurs then all values in the
 * vector are divided by two (rounding towards greater value) before
 * performing addition). This method alters vector state (if an
 * exception is thrown then the vector remains unchanged). The
 * algorithm used here is of logarithmic cost (except for halving,
 * which is rather rare). This method must be synchronized outside.
 **
 * @param index
 * the index (must be non-negative) at which to add
 * <VAR>incValue</VAR>.
 * @param incValue
 * the signed value to be added.
 * @return
 * <CODE>true</CODE> if and only if <CODE>this</CODE> cumulative
 * vector has been halved (one or more times) before addition.
 * @exception ArrayIndexOutOfBoundsException
 * if <VAR>index</VAR> is negative.
 * @exception OutOfMemoryError
 * if there is not enough memory.
 **
 * @see #clearAt(int)
 * @see #getIntAt(int)
 * @see #getCumSum(int)
 * @see #findSum(int)
 * @see #clear()
 * @see #trimToSize()
 */
 public boolean addAt(int index, int incValue)
  throws ArrayIndexOutOfBoundsException
 {
  if (index < 0)
   throw new ArrayIndexOutOfBoundsException(index);
  int[] array = this.array;
  int capacity, unsignedValue;
  if ((capacity = array.length) <= index)
  {
   int last = capacity;
   if (index << 1 <= 0)
    capacity = -1 >>> 1;
    else while ((capacity <<= 1) <= index);
   int[] newArray;
   System.arraycopy(array, 0,
    newArray = new int[capacity], 0, last);
   unsignedValue = (array = newArray)[last - 1];
   do
   {
    array[(last <<= 1) - 1] = unsignedValue;
   } while (last < capacity);
   this.array = array;
  }
  capacity--;
  boolean isHalved = false;
  if (incValue <= 0)
  {
   if (incValue == 0 || (unsignedValue = array[index]) == 0)
    return false;
   for (int base = 1; (index & base) != 0; base <<= 1)
    if ((unsignedValue -= array[index ^ base]) == 0)
     return false;
   if (((-unsignedValue - incValue) | unsignedValue) >= 0)
    incValue = -unsignedValue;
  }
   else while ((unsignedValue = array[capacity]) < 0 &&
               unsignedValue + incValue >= 0)
   {
    int last = capacity;
    while (last > 0 && array[last >> 1] == unsignedValue)
     last >>= 1;
    do
    {
     unsignedValue = array[last];
     for (int base = 1; (last & base) != 0; base <<= 1)
      unsignedValue -= array[last ^ base];
     if ((unsignedValue >>>= 1) != 0)
     {
      array[last] -= unsignedValue;
      for (int pos = last, base = 1; pos < capacity; base <<= 1)
       if ((pos & base) == 0)
        array[pos ^= base] -= unsignedValue;
     }
    } while (last-- > 0);
    isHalved = true;
   }
  array[index] += incValue;
  for (unsignedValue = 1; index < capacity; unsignedValue <<= 1)
   if ((index & unsignedValue) == 0)
    array[index ^= unsignedValue] += incValue;
  return isHalved;
 }

/**
 * Returns an unsigned <CODE>int</CODE> value at the specified
 * index.
 **
 * This is a core 'get value' method of this cumulative vector. The
 * algorithm used here is of logarithmic cost. Important notes: if
 * <VAR>index</VAR> is out of range then zero is returned. This
 * method must be synchronized outside.
 **
 * @param index
 * the index at which to get a value.
 * @return
 * the current unsigned value at <VAR>index</VAR>.
 **
 * @see #clear()
 * @see #clearAt(int)
 * @see #addAt(int, int)
 * @see #getCumSum(int)
 * @see #length()
 * @see #toIntArray()
 **
 * @since 1.8
 */
 public int getIntAt(int index)
 {
  int unsignedValue = 0;
  int[] array = this.array;
  if (((array.length - index - 1) | index) >= 0)
  {
   unsignedValue = array[index];
   for (int base = 1; (index & base) != 0; base <<= 1)
    unsignedValue -= array[index ^ base];
  }
  return unsignedValue;
 }

/**
 * Returns an unsigned <CODE>int</CODE> cumulative partial sum of
 * the specified amount of the first values in the vector.
 **
 * This is a core 'get partial sum' method of this cumulative
 * vector. The algorithm used here is of logarithmic cost. Important
 * notes: negative <VAR>count</VAR> is treated as zero; if
 * <VAR>count</VAR> is greater then <CODE>length()</CODE> then
 * <CODE>getTotalSum()</CODE> is returned. This method must be
 * synchronized outside.
 **
 * @param count
 * the amount of values to be summed in the result.
 * @return
 * the unsigned partial sum of the first <VAR>count</VAR> values.
 **
 * @see #length()
 * @see #getTotalSum()
 * @see #clear()
 * @see #clearAt(int)
 * @see #addAt(int, int)
 * @see #getIntAt(int)
 * @see #findSum(int)
 * @see #toCumSumArray()
 */
 public int getCumSum(int count)
 {
  int unsignedCumSum = 0;
  if (count > 0)
  {
   int[] array = this.array;
   if (count >= array.length)
    return array[array.length - 1];
   unsignedCumSum = array[--count];
   int base = 1;
   do
   {
    if ((count & base) == 0)
     if ((count -= base) >= 0)
      unsignedCumSum += array[count];
      else break;
    base <<= 1;
   } while (true);
  }
  return unsignedCumSum;
 }

/**
 * Returns an unsigned total cumulative sum of all values in the
 * vector.
 **
 * @return
 * the unsigned total sum of all the values.
 **
 * @see #length()
 * @see #clear()
 * @see #getCumSum(int)
 */
 public int getTotalSum()
 {
  int[] array = this.array;
  return array[array.length - 1];
 }

/**
 * Finds the specified partial sum in <CODE>this</CODE> cumulative
 * vector.
 **
 * This is the inverse operation for <CODE>getCumSum(count)</CODE>.
 * The result is minimum <VAR>count</VAR> that satisfies
 * <CODE>getCumSum(count) == unsignedCumSum</CODE> and
 * <CODE>getCumSum(count + 1) == unsignedCumSum</CODE> if it is
 * possible, else the result is <VAR>count</VAR> that satisfies
 * <CODE>getCumSum(count + 1) > unsignedCumSum</CODE> and
 * <CODE>unsignedCumSum >= getCumSum(count)</CODE> if it is
 * possible, else the result is minimum <VAR>count</VAR> that
 * satisfies <CODE>getCumSum(count) == getTotalSum()</CODE>. The
 * algorithm used here is of logarithmic cost. This method must be
 * synchronized outside.
 **
 * @param unsignedCumSum
 * the unsigned partial sum to find.
 * @return
 * the amount (a non-negative value) of values to be summed.
 **
 * @see #length()
 * @see #getCumSum(int)
 * @see #getTotalSum()
 * @see #getIntAt(int)
 */
 public int findSum(int unsignedCumSum)
 {
  int[] array = this.array;
  int count, value = array[count = array.length - 1];
  if (((value ^ unsignedCumSum) >= 0 ?
      value - unsignedCumSum : unsignedCumSum) < 0)
   unsignedCumSum = value;
  if (unsignedCumSum != 0)
  {
   int base = (count >>= 1) + 1, delta = value - unsignedCumSum;
   do
   {
    if ((((value = array[count]) ^ unsignedCumSum) >= 0 ?
        value - unsignedCumSum : unsignedCumSum) < 0)
    {
     if ((base >>= 1) == 0)
     {
      count++;
      break;
     }
     unsignedCumSum -= value;
     count += base;
    }
     else
     {
      delta = value - unsignedCumSum;
      if ((base >>= 1) == 0)
       break;
      count -= base;
     }
   } while (true);
   if (delta == 0)
    count++;
  }
   else count = 0;
  return count;
 }

/**
 * Returns unsigned <CODE>int</CODE> array of the current values of
 * <CODE>this</CODE> vector.
 **
 * Result[index] is the same as of <CODE>getIntAt(index)</CODE> for
 * any index. This method must be synchronized outside.
 **
 * @return
 * a newly created array (not <CODE>null</CODE>, with
 * <CODE>length</CODE> equals <CODE>length()</CODE> of
 * <CODE>this</CODE>) filled with the current (unsigned) values of
 * <CODE>this</CODE> vector.
 * @exception OutOfMemoryError
 * if there is not enough memory.
 **
 * @see #length()
 * @see #getIntAt(int)
 * @see #toCumSumArray()
 **
 * @since 2.0
 */
 public int[] toIntArray()
 {
  int size = findSum(-1);
  int[] values = new int[size];
  for (int index = 0; index < size; index++)
   values[index] = getIntAt(index);
  return values;
 }

/**
 * Returns unsigned <CODE>int</CODE> array of the current partial
 * cumulative sums.
 **
 * Result[index] is the same as of <CODE>getCumSum(index + 1)</CODE>
 * for any index. This method must be synchronized outside.
 **
 * @return
 * a newly created array (not <CODE>null</CODE>, with
 * <CODE>length</CODE> equals <CODE>length()</CODE> of
 * <CODE>this</CODE>) filled with the sequential cumulative
 * (unsigned) sums of <CODE>this</CODE> vector.
 * @exception OutOfMemoryError
 * if there is not enough memory.
 **
 * @see #length()
 * @see #getCumSum(int)
 * @see #toIntArray()
 */
 public int[] toCumSumArray()
 {
  int size = findSum(-1);
  int[] sums = new int[size];
  for (int index = 0; index < size; index++)
   sums[index] = getCumSum(index + 1);
  return sums;
 }

/**
 * Creates and returns a copy of <CODE>this</CODE> object.
 **
 * This method creates a new instance of the class of this object
 * and initializes its <VAR>array</VAR> with a copy of
 * <VAR>array</VAR> value of <CODE>this</CODE> object. This method
 * must be synchronized outside.
 **
 * @return
 * a copy (not <CODE>null</CODE> and != <CODE>this</CODE>) of
 * <CODE>this</CODE> instance.
 * @exception OutOfMemoryError
 * if there is not enough memory.
 **
 * @see CumVector#CumVector(int)
 * @see #getIntAt(int)
 * @see #equals(java.lang.Object)
 */
 public Object clone()
 {
  Object obj;
  try
  {
   if ((obj = super.clone()) instanceof CumVector && obj != this)
   {
    CumVector vector = (CumVector)obj;
    vector.array = (int[])vector.array.clone();
    return obj;
   }
  }
  catch (CloneNotSupportedException e) {}
  throw new InternalError("CloneNotSupportedException");
 }

/**
 * Computes and returns a hash code value for the object.
 **
 * This method hashes all elements of <CODE>this</CODE> vector and
 * mixes them all to produce a single hash code value. This method
 * must be synchronized outside.
 **
 * @return
 * a hash code value for <CODE>this</CODE> object.
 **
 * @see #length()
 * @see #equals(java.lang.Object)
 */
 public int hashCode()
 {
  int[] array = this.array;
  int index, code = array[index = array.length - 1];
  while (index > 0 && array[index >> 1] == code)
   index >>= 1;
  int len = index;
  while (index-- > 0)
   code = ((code << 5) - code) ^ array[index];
  return ((code << 5) - code) ^ len;
 }

/**
 * Indicates whether <CODE>this</CODE> object is equal to the
 * specified one.
 **
 * This method returns <CODE>true</CODE> if and only if
 * <VAR>obj</VAR> is instance of this class and all values of
 * <CODE>this</CODE> vector are equal to the corresponding values of
 * <VAR>obj</VAR> vector. This method must be synchronized outside.
 **
 * @param obj
 * the object (may be <CODE>null</CODE>) with which to compare.
 * @return
 * <CODE>true</CODE> if and only if <CODE>this</CODE> value is the
 * same as <VAR>obj</VAR> value.
 **
 * @see #length()
 * @see #getIntAt(int)
 * @see CumVector#CumVector()
 * @see #clone()
 * @see #hashCode()
 * @see #greaterThan(java.lang.Object)
 */
 public boolean equals(Object obj)
 {
  if (obj != this)
  {
   if (!(obj instanceof CumVector))
    return false;
   int[] array = this.array;
   int index, unsignedSum = array[index = array.length - 1];
   int[] vectorArray = ((CumVector)obj).array;
   if (vectorArray[vectorArray.length - 1] != unsignedSum)
    return false;
   while (index > 0 && array[index >> 1] == unsignedSum)
    index >>= 1;
   if (vectorArray.length <= index)
    return false;
   do
   {
    if (array[index] != vectorArray[index])
     return false;
   } while (index-- > 0);
  }
  return true;
 }

/**
 * Tests for being semantically greater than the argument.
 **
 * The result is <CODE>true</CODE> if and only if <VAR>obj</VAR> is
 * instance of <CODE>this</CODE> class and <CODE>this</CODE> object
 * is greater than the specified object. Values of this vector are
 * compared in the unsigned manner, starting at index 0. This method
 * must be synchronized outside.
 **
 * @param obj
 * the second compared object (may be <CODE>null</CODE>).
 * @return
 * <CODE>true</CODE> if <VAR>obj</VAR> is comparable with
 * <CODE>this</CODE> and <CODE>this</CODE> object is greater than
 * <VAR>obj</VAR>, else <CODE>false</CODE>.
 **
 * @see #length()
 * @see #getIntAt(int)
 * @see #equals(java.lang.Object)
 **
 * @since 2.0
 */
 public boolean greaterThan(Object obj)
 {
  int index, len, value;
  boolean isGreater = false;
  if (obj != this && obj instanceof CumVector)
  {
   int[] array = this.array, vectorArray = ((CumVector)obj).array;
   for (value = array[index = array.length - 1];
        index > 0 && array[index >> 1] == value; index >>= 1);
   len = index;
   for (value = vectorArray[index = vectorArray.length - 1];
        index > 0 && vectorArray[index >> 1] == value; index >>= 1);
   if (index < len)
   {
    isGreater = true;
    len = index;
   }
   index = 0;
   do
   {
    int vectorValue = vectorArray[index];
    if ((value = array[index]) != vectorValue)
    {
     if ((vectorValue ^ value) >= 0)
      value = vectorValue - value;
     isGreater = false;
     if (value < 0)
      isGreater = true;
     break;
    }
   } while (++index <= len);
  }
  return isGreater;
 }

/**
 * Converts <CODE>this</CODE> object to its 'in-line' string
 * representation.
 **
 * The decimal string representations of the unsigned
 * <CODE>int</CODE> values (of the vector) are placed into the
 * resulting string in the direct index order, delimited by a space.
 * This method must be synchronized outside.
 **
 * @return
 * the string representation (not <CODE>null</CODE>) of
 * <CODE>this</CODE> object.
 * @exception OutOfMemoryError
 * if there is not enough memory.
 **
 * @see #length()
 * @see #getIntAt(int)
 * @see #toIntArray()
 */
 public String toString()
 {
  int index = 0, size;
  if ((size = findSum(-1)) > 0 && (index = size << 2) <= 24)
   index = 24;
  StringBuffer sBuf = new StringBuffer(index);
  if (size > 0)
  {
   index = 0;
   do
   {
    sBuf.append(UnsignedInt.toString(getIntAt(index), true));
    if (++index >= size)
     break;
    sBuf.append(' ');
   } while (true);
  }
  return new String(sBuf);
 }

/**
 * Verifies <CODE>this</CODE> object for its integrity.
 **
 * This method must be synchronized outside. For debug purpose only.
 **
 * @exception InternalError
 * if integrity violation is detected.
 **
 * @see CumVector#CumVector(int)
 * @see #getIntAt(int)
 **
 * @since 2.0
 */
 public void integrityCheck()
 {
  int[] array;
  if ((array = this.array) == null)
   throw new InternalError("array: null");
  int capacity;
  if ((capacity = array.length) <= 0 ||
      (-capacity & capacity) != capacity)
   throw new InternalError("capacity: " +
              UnsignedInt.toString(capacity, false));
  for (capacity--; capacity > 0; capacity -= 2)
  {
   int value, predSum = 0;
   for (value = 1; (capacity & value) != 0; value <<= 1)
    predSum += array[capacity ^ value];
   if ((((value = array[capacity]) ^ predSum) >= 0 ?
       value - predSum : predSum) < 0)
    throw new InternalError("array[" +
               UnsignedInt.toString(capacity, false) + "]: " +
               UnsignedInt.toString(value, true) + ", predSum: " +
               UnsignedInt.toString(predSum, true));
  }
 }

/**
 * Serializes <CODE>this</CODE> object to a given stream.
 **
 * This method is responsible for writing the state of
 * <CODE>this</CODE> object to <VAR>out</VAR> stream so that
 * corresponding <CODE>readObject(ObjectInputStream)</CODE> method
 * can restore it. First of all, it calls
 * <CODE>defaultWriteObject()</CODE> for <VAR>out</VAR> to invoke
 * the default serialization mechanism. Then, it manually saves the
 * state of <CODE>transient</CODE> fields. This method is used only
 * internally by <CODE>ObjectOutputStream</CODE> class. This method
 * must be synchronized outside.
 **
 * @serialData
 * a negative value (<CODE>byte</CODE>) of the binary logarithm of
 * <CODE>length</CODE> of <VAR>array</VAR>,
 * <CODE>getTotalSum()</CODE> value (<CODE>int</CODE>), and all the
 * elements of <VAR>array</VAR> in a compact bit-form.
 **
 * @param out
 * the stream (must be non-<CODE>null</CODE>) to write data to in
 * order to save the state of the object.
 * @exception NullPointerException
 * if <VAR>out</VAR> is <CODE>null</CODE>.
 * @exception IOException
 * if any I/O error occurs.
 * @exception OutOfMemoryError
 * if there is not enough memory.
 **
 * @see CumVector#CumVector()
 * @see #clone()
 * @see #getTotalSum()
 */
 private void writeObject(ObjectOutputStream out)
  throws IOException
 {
  out.defaultWriteObject();
  int[] array = this.array;
  int value = 0, maxValue = array.length, capacity = maxValue - 1;
  do
  {
   value--;
  } while ((maxValue >>= 1) != 0);
  out.write(value);
  value = array[capacity];
  maxValue = ((JavaConsts.INT_SIZE - 1) /
   JavaConsts.BYTE_SIZE) * JavaConsts.BYTE_SIZE;
  do
  {
   out.write(value >>> maxValue);
  } while ((maxValue -= JavaConsts.BYTE_SIZE) >= 0);
  byte bits = 1;
  for (int step = capacity; step > 0; step >>= 1)
  {
   int index = step >> 1, base;
   do
   {
    for (base = 1; (index & base) != 0; base <<= 1);
    maxValue = array[value = index ^ base];
    while (((base <<= 1) & index) != 0)
     maxValue -= array[value ^ base];
    base = 0;
    for (value = maxValue; value != 0; value >>>= 1, base++);
    value = array[index] << (JavaConsts.INT_SIZE - base);
    for (maxValue <<= JavaConsts.INT_SIZE - base;
         base-- > 0; value <<= 1, maxValue <<= 1)
     if (maxValue < 0)
     {
      byte oldBits = bits;
      bits <<= 1;
      if (value >= 0)
       maxValue = -1;
       else bits++;
      if (oldBits < 0)
      {
       out.write(bits);
       bits = 1;
      }
     }
    index++;
   } while ((index += step) < capacity);
  }
  if (bits != 1)
  {
   while (bits > 0)
    bits <<= 1;
   out.write(bits << 1);
  }
 }

/**
 * Deserializes an object of this class from a given stream.
 **
 * This method is responsible for reading from <VAR>in</VAR> stream,
 * restoring the classes fields, and verifying that the serialized
 * object is not corrupted. First of all, it calls
 * <CODE>defaultReadObject()</CODE> for <VAR>in</VAR> to invoke the
 * default deserialization mechanism. Then, it restores the state of
 * <CODE>transient</CODE> fields and performs additional
 * verification of the deserialized object. This method is used only
 * internally by <CODE>ObjectInputStream</CODE> class.
 **
 * @param in
 * the stream (must be non-<CODE>null</CODE>) to read data from in
 * order to restore the object.
 * @exception NullPointerException
 * if <VAR>in</VAR> is <CODE>null</CODE>.
 * @exception IOException
 * if any I/O error occurs or the serialized object is corrupted.
 * @exception ClassNotFoundException
 * if the class for an object being restored cannot be found.
 * @exception OutOfMemoryError
 * if there is not enough memory.
 **
 * @see CumVector#CumVector()
 * @see #integrityCheck()
 */
 private void readObject(ObjectInputStream in)
  throws IOException, ClassNotFoundException
 {
  in.defaultReadObject();
  int value, maxValue, capacity = 1;
  if ((value = in.read()) < 0)
   throw new EOFException();
  value = (byte)value;
  while (++value != 0)
   if ((capacity <<= 1) <= 0)
    throw new InvalidObjectException("Invalid capacity");
  int[] array = new int[capacity];
  maxValue = (JavaConsts.INT_SIZE - 1) / JavaConsts.BYTE_SIZE;
  int bits, oldBits;
  do
  {
   if ((bits = in.read()) < 0)
    throw new EOFException();
   value = bits & JavaConsts.BYTE_MASK |
    (value << JavaConsts.BYTE_SIZE);
  } while (maxValue-- > 0);
  array[--capacity] = value;
  bits = 0;
  for (int step = capacity; step > 0; step >>= 1)
  {
   int index = step >> 1, base;
   do
   {
    for (base = 1; (index & base) != 0; base <<= 1);
    maxValue = array[value = index ^ base];
    while (((base <<= 1) & index) != 0)
     maxValue -= array[value ^ base];
    base = 0;
    for (value = maxValue; value != 0; value >>>= 1, base++);
    for (maxValue <<= JavaConsts.INT_SIZE - base;
         base-- > 0; maxValue <<= 1)
    {
     value <<= 1;
     if (maxValue < 0)
     {
      if ((oldBits = (byte)(bits << 1)) == 0 &&
          (bits = in.read()) < 0)
       throw new EOFException();
      if ((byte)bits >= 0)
       maxValue = -1;
       else value++;
      bits <<= 1;
      if (oldBits == 0)
       bits++;
     }
    }
    array[index++] = value;
   } while ((index += step) < capacity);
  }
  this.array = array;
 }
}

/**
 * A helper class for output.
 */
final class arthpack1 extends ArithEncoderStream
{

 protected CumVector vector;

 public arthpack1(OutputStream out)
 {
  super(out);
  CumVector vector = new CumVector(JavaConsts.BYTE_MASK + 1);
  for (int index = 0; index <= JavaConsts.BYTE_MASK; index++)
   vector.addAt(index, 1);
  this.vector = vector;
 }

 public void writeInt(int unsignedValue, int unsignedMax)
  throws IllegalArgumentException, IOException
 {
  CumVector vector = this.vector;
  int cumLower = vector.getCumSum(unsignedValue);
  writeRange(cumLower, cumLower +
   vector.getIntAt(unsignedValue) - 1,
   vector.getCumSum(unsignedMax + 1) - 1);
  vector.addAt(unsignedValue, arthpack.FREQ_INC_VALUE);
 }
}

/**
 * A helper class for input.
 */
final class arthpack2 extends ArithDecoderStream
{

 protected CumVector vector;

 public arthpack2(InputStream in)
 {
  super(in);
  CumVector vector = new CumVector(JavaConsts.BYTE_MASK + 1);
  for (int index = 0; index <= JavaConsts.BYTE_MASK; index++)
   vector.addAt(index, 1);
  this.vector = vector;
 }

 public int readInt(int unsignedMax)
  throws IOException
 {
  CumVector vector = this.vector;
  unsignedMax = vector.getCumSum(unsignedMax + 1) - 1;
  int unsignedValue = vector.findSum(readRange(unsignedMax));
  int cumLower = vector.getCumSum(unsignedValue);
  updateRange(cumLower, cumLower +
   vector.getIntAt(unsignedValue) - 1, unsignedMax);
  vector.addAt(unsignedValue, arthpack.FREQ_INC_VALUE);
  return unsignedValue;
 }
}