import java.io.*;

/**
 This class is a buffered input stream that allows for users to easily read
 bits and bytes from the underlying stream.  All methods use computer arithmetic
 to maipulate the bits, and have a default buffer of 64 bits (long).

 <pre>
 Usage: Identical to the BufferedInputStream.
 	ie.  BitInputStream out = new BitInputStream(new FileInputStream(file));
 </pre>

 @version		0.1, 11/09/04
 @author 		Winson Chung
 */
public class BitInputStream extends InputStream {

	/** The input stream to read from. */
	private BufferedInputStream in;
	/** The 'long' buffer that stores the bits. */
	protected long buf;
	/** A 'long' is represented by 64 bits, thus the length of the buffer is 64 bits. */
	protected int bufLength = 64, curBufLength = 0;
	/** The current location in the buffer. */
	protected int count;
	/** The reduce arrays used to reduce large values. */
	protected long[] byteLReduce, longLReduce, outReduce;

	public BitInputStream(InputStream is) throws IOException {
		// init vars
		buf 	= 0L;
		count 	= 0;
		in	 	= new BufferedInputStream(is);

		// build other reduce arrays (used for overflow handling)
		byteLReduce = lReduce(8, 0);

		// build other long reduce arrays
		longLReduce = lReduce(64, 56);

		// build the array to reduce output
		//  	ie. 0xFF0000..0, 0x00FF000..0, ...
		outReduce 	= new long[8];
		for (int i = 0; i < 8; i++)
			outReduce[i] = (long) ((long)255 << (i*8));

		// first fill of buffer
		curBufLength = Math.min(8, in.available());
		long byt = 0L;
		for (int i = 0; i < curBufLength; i++) {
			byt = in.read() & 0xFF;
			buf |= byt << (8 * (7-i));
		}
		curBufLength *= 8;
	}

	/** Creates an array of left-aligned reduce int values.  From 'start' to
	 	'end', including 'end'.  'start' MUST be > 'end'.
	  		ie. 10000000, 11000000, 11100000, ... , 11111111
	  	@param length the length of the array to be made. */
	private long[] lReduce(int start, int end) {
		if (start <= end)
			return new long[0];

		long[] red = new long[start-end];
		for (int i = (start-1); i >= end; i--) {
			red[start-(i+1)] |= ((long)1 << i);
			if (i > end)
				red[start-(i)] = red[start-(i+1)];
		}
		return red;
	}

	/** Tests if this input stream supports the mark and reset methods.
	    @MARK NOT SUPPORTED@ */
	public boolean markSupported() { return false; }

	/** Returns the number of bytes that can be read (or skipped over) from this
	 	input stream without blocking by the next caller of a method for this
	 	input stream.  HALF-BYTES are NOT counted. ie. 9 bits -> 1 byte
	 	available. */
	public int available() throws IOException {
		return in.available() + ((curBufLength-count)/8);
	}

	/** Returns the number of bits that can be read (or skipped over) from this
	 	input stream without blocking by the next caller of a method for this
	 	input stream. */
	public long availableBits() throws IOException {
		return ((long)(in.available()*8)) + (curBufLength-count);
	}

	/** Closes this input stream and releases any system resources associated
	 	with the stream. */
	public void close() throws IOException {
		in.close();
	}

	/** Skips over and discards n bytes of data from this input stream INCLUDING
	 	any half bits that are currently being read in the buffer. */
	public long skip(long n) throws IOException {
		// only skip all available bytes
		if (n > this.available())
			n = this.available();
		// read and discard 'n' bytes
		long cnt = 0L;
		while (cnt < n) {
			this.readByte();
			cnt++;
		}
		return n;
	}

	public long skipBits(long n) throws IOException {
		// only skip all available bits
		if (n > this.availableBits())
			n = this.availableBits();
		// remove by bytes until you can remove bits
		long byteCnt = (n/8);
		for (long i = 0; i < byteCnt; i++)
			this.readByte();
		// remove remaining bits
		long bitCnt = (n%8);
		for (long i = 0; i < bitCnt; i++)
			this.readBit();
		return n;
	}

	/** Reads the next byte of data from the input stream. */
	public int read() throws IOException {
		return this.readByte();
	}

	/** Reads some number of bytes from the input stream and stores them into
	 	the buffer array b. */
	public int read(byte[] b) throws IOException {
		return this.readBytes(b, 0, b.length);
	}

	/** Reads up to len bytes of data from the input stream into an array of
	 	bytes. */
	public int read(byte[] b, int off, int len) throws IOException {
		return this.readBytes(b, off, len);
	}

	/** Reads the next UNSIGNED byte of data from the input stream.
	 	@returns the next byte of data, including the current (possibly half) byte. */
	public int readByte() throws IOException {
		if (this.available() == 0)
			return -1;

		byte byteLength = 8,
			 start 		= (byte) (bufLength - count - 1),
			 end 		= (byte) (bufLength - (count + byteLength)),
			 total 		= (byte) (count + byteLength);
		int value 		= 0;
		if (total <= bufLength) {
			long byteRed 	= (buf & ((long)0xFF << end)) >> end;
			value 			= (int) byteRed;

			count += byteLength;
			if (count == bufLength)
				curBufLength = this.refillBuffer();
		}else if (total > bufLength) {
			// zeroTo -> # of bits after zero
			byte zeroTo 	= (byte) (total - bufLength);
			value		 	= (int) ((((buf & (byteLReduce[zeroTo-1] ^ 0xFF))) << zeroTo));
			curBufLength 	= this.refillBuffer();
			value 			|= (int) ((buf >> (bufLength - zeroTo)) & (byteLReduce[8-zeroTo-1] ^ 0xFF));
			count 			= zeroTo;
		}
		return (value & 0xFF);
	}

	/** Reads up to len bytes of data from the input stream into an array of
	 	bytes.

	 	@returns the number of bytes read. */
	public int readBytes(byte[] b, int off, int len) throws IOException {
		if (this.available() == 0)
			return -1;

		if (b == null)
			throw new NullPointerException();
		if ((off + len > b.length) || (off < 0) || (len < 0))
			throw new IndexOutOfBoundsException();
		len = Math.min((len-off), (int)this.available());
		for (int i = 0; i < len; i++)
			b[i+off] = (byte) this.readByte();
		return len;
	}

	/** Reads a single bit from the input stream, which is returned.
	 	@returns the logical value of the bit read. */
	public boolean readBit() throws IOException {
		if (this.availableBits() == 0)
			return false;

		byte shift 	= (byte) (bufLength - count - 1);
		byte res	= (byte) ((buf & ((long)1 << shift)) >> shift);
		count++;

		if (count >= bufLength)
			curBufLength = this.refillBuffer();

		return (res == 1);
	}

	/** Reads a series of bits from the input stream, which will then be written
	 	to the boolean array with the specified offset and for the specified
	 	length. It returns the number of bits read.

	 	@returns the number of bits read. */
	public int readBits(boolean[] b, int off, int len) throws IOException {
		if (this.availableBits() == 0)
			return -1;

		if (b == null)
			throw new NullPointerException();
		if ((off + len > b.length) || (off < 0) || (len < 0))
			throw new IndexOutOfBoundsException();
		len = Math.min((len-off), (int)this.availableBits());
		for (int i = 0; i < len; i++)
			b[i+off] = this.readBit();
		return len;
	}

	/** Reads an int value from the input stream, which is 4 bytes.
	 	@returns the int value read. */
	public int readInt() throws IOException {
		int lng = 0, val = 0;
		for (int i = 3; i >= 0; i--) {
			val = this.readByte();
			lng |= val << (8*i);
		}
		return lng;
	}

	/** Reads a long value from the input stream, which is 8 bytes.
	 	@returns the long value read. */
	public long readLong() throws IOException {
		long lng = 0L, val = 0L;
		for (int i = 7; i >= 0; i--) {
			val = this.readByte();
			lng |= val << (8*i);
		}
		return lng;
	}

	/** Refills/replaces the buffer with another 8 bytes from the input stream.
	 	@returns the number of bits read. */
	private int refillBuffer() throws IOException {
		long byt = 0L;
		this.clearBuffer();
		int total = Math.min(8, in.available());
		for (int i = 0; i < total; i++) {
			byt = in.read() & 0xFF;
			buf |= byt << (8 * (7-i));
		}
		return (total*8);
	}

	/** Clears the buffer for new input. */
	private void clearBuffer() {
		buf = 0L;
		count = 0;
	}

	/** Reads a String from the input stream given the expected length of the
	 	String to read.

	 	@param len the length (in bytes) of the String to be read, including the current (possibly half) byte.
	 	@returns the String read. */
	public String readString(int len) throws IOException {
		StringBuffer str 	= new StringBuffer();
		len = Math.min(len, this.available());
		for (int i = 0; i < len; i++) {
			str.append((char) this.readByte());
		}
		return str.toString();
	}

	/** Returns a String representation of the state of the current buffer in
	 	binary form, as well as any variables associated with the buffer. */
	public String toString() {
		String lval = Long.toBinaryString(buf);
		for (int i = lval.length(); i < bufLength; i++)
			lval = '0' + lval;
		lval = lval.substring(0, count) + "^" + lval.substring(count);
		return ("Buffer (" + bufLength + "): " + lval + "\n\tCount: " + count);
	}
}