inputbitstream.java

MG4J (Managing Gigabytes for Java) is a free full-text search engine for large document collections

package it.unimi.dsi.mg4j.io;

/*		 
* MG4J: Managing Gigabytes for Java
*
* Copyright (C) 2002-2007 Sebastiano Vigna 
*
*  This library is free software; you can redistribute it and/or modify it
*  under the terms of the GNU Lesser General Public License as published by the Free
*  Software Foundation; either version 2.1 of the License, or (at your option)
*  any later version.
*
*  This library is distributed in the hope that it will be useful, but
*  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
*  or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
*  for more details.
*
*  You should have received a copy of the GNU Lesser General Public License
*  along with this program; if not, write to the Free Software
*  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*
*/

import it.unimi.dsi.bits.Fast;
import it.unimi.dsi.fastutil.booleans.AbstractBooleanIterator;
import it.unimi.dsi.fastutil.booleans.BooleanIterator;
import it.unimi.dsi.fastutil.ints.IntIterators;
import it.unimi.dsi.fastutil.io.BinIO;
import it.unimi.dsi.fastutil.io.FastBufferedInputStream;
import it.unimi.dsi.fastutil.io.RepositionableStream;

import java.io.Closeable;
import java.io.DataInputStream;
import java.io.EOFException;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.Flushable;
import java.io.IOException;
import java.io.InputStream;
import java.nio.channels.FileChannel;


/** Bit-level input stream.
 *
 * <p><strong>Warning</strong>: for simplicity, efficiency and lack of usefulness
 * overflowing and unget features have been removed in MG4J 1.1. If you feel they 
 * should be put back, write to the authors.
 *
 * <P>This class wraps any {@link InputStream} so that you can treat it as
 * <em>bit</em> stream.  Constructors and methods closely resemble those of
 * {@link InputStream}. Data can be read from such a stream in several ways:
 * reading an integer or long in fixed-width, unary, &gamma;, shifted &gamma;, &delta;, &zeta; and (skewed) 
 * Golomb coding, or reading a number of bits that will be stored in a vector of
 * bytes. There is limited support for {@link #mark(int)}/{@link #reset()}
 * operations.
 *
 * <P>This class can also {@linkplain #InputBitStream(byte[]) wrap a byte
 * array}; this is much more lightweight than wrapping a {@link
 * FastByteArrayInputStream} wrapping the array. Overflowing the array
 * will cause an {@link java.io.EOFException}.
 * 
 * <P>Note that when reading using a vector of bytes bits are read in the
 * stream format (see {@link OutputBitStream}): the first bit is bit 7 of the
 * first byte, the eighth bit is bit 0 of the first byte, the ninth bit is bit
 * 7 of the second byte and so on. When reading integers using some coding,
 * instead, they are stored in the standard way, that is, in the <strong>lower</strong>
 * bits.
 *
 * <P>Additional features:
 * 
 * <UL>
 *
 * <LI>This class provides an internal buffer. By setting a buffer of
 * length 0 at creation time, you can actually bypass the buffering system:
 * Note, however, that several classes providing buffering have synchronised
 * methods, so using a wrapper instead of the internal buffer is likely to lead
 * to a performance drop.
 *
 * <LI>To work around the schizophrenic relationship between streams and random
 * access files in {@link java.io}, this class provides a {@link #flush()}
 * method that resets the internal state. At this point, you can safely reposition
 * the underlying stream and read again afterwards. For instance, this is safe
 * and will perform as expected:
 * <PRE>
 * FileInputStream fis = new FileInputStream( ... );
 * InputBitStream ibs = new InputBitStream( fis );
 * ... read operations on ibs ...
 * ibs.flush();
 * fis.getChannel().position( ... );
 * ... other read operations on ibs ...
 * </PRE>
 *
 * <P>As a commodity, an instance of this class will try to cast the underlying byte
 * stream to a {@link RepositionableStream} and to fetch by reflection the {@link
 * java.nio.channels.FileChannel} underlying the given input stream, in this
 * order.  If either reference can be successfully fetched, you can use
 * directly the {@link #position(long) position()} method with argument
 * <code>pos</code> with the same semantics of a {@link #flush()}, followed by
 * a call to <code>position(pos / 8)</code> (where the latter method belongs
 * either to the underlying stream or to its underlying file channel), followed
 * by a {@link #skip(long) skip(pos % 8)}.
 *
 * <li>Finally, this class implements partially the interface of a boolean iterator.
 * More precisely, {@link #nextBoolean()} will return the same bit as {@link #readBit()},
 * and also the same exceptions, whereas <em>{@link #hasNext()} will always return true</em>:
 * you must be prepared to catch a {@link java.lang.RuntimeException} wrapping an {@link IOException}
 * in case the file ends. It
 * is very difficult to implement completely an eager operator using a input-stream
 * based model.
 *
 * </ul>
 *
 * <P><STRONG>This class is not synchronised</STRONG>. If multiple threads
 * access an instance of this class concurrently, they must be synchronised externally.
 *
 * @see java.io.InputStream
 * @see it.unimi.dsi.mg4j.io.OutputBitStream
 * @author Sebastiano Vigna
 * @since 0.1
 * @deprecated Moved to <code>dsiutils</code>.
 */

@Deprecated
public class InputBitStream extends AbstractBooleanIterator implements Flushable, Closeable {
	private final static boolean DEBUG = false;
	private final static boolean ASSERTS = false;

	/* Precomputed tables: the i-th entry decodes the stream fragment of 16 bits given by the binary reprentation of i.
	 * The upper 16 bits contain code lengths, the lower 16 bits decoded values. 0 means undecodable. */
	final private static int[] GAMMA = new int[ 256 * 256 ], DELTA = new int[ 256 * 256 ], ZETA_3 = new int[ 256 * 256 ], SHIFTED_GAMMA = new int[ 256 * 256 ];

	static void fillArrayFromResource( final String resource, final int array[] ) throws IOException {
		final String resouceFullPath = "/it/unimi/dsi/mg4j/io/" + resource;
        final InputStream ris = InputBitStream.class.getResourceAsStream( resouceFullPath );
        if ( ris == null ) throw new IOException( "Cannot open resource " + resouceFullPath );
        DataInputStream dis = new DataInputStream( new FastBufferedInputStream( ris ) ); 
		BinIO.loadInts( dis, array, 0, array.length );
		dis.close();
		if ( ASSERTS ) {
			final int actualLength = IntIterators.unwrap( BinIO.asIntIterator( new DataInputStream( InputBitStream.class.getResourceAsStream( resouceFullPath ) ) ) ).length;
			assert array.length == actualLength : resource + " is long " + actualLength + " but we think it should rather be " + array.length;
		}
	}
	
	static {
		/* We load all precomputed arrays from resource files, 
		 * to work around the limit on static initialiser code. */
		try {
			fillArrayFromResource( "gamma.in.16", GAMMA );
			fillArrayFromResource( "delta.in.16", DELTA );
			fillArrayFromResource( "zeta3.in.16", ZETA_3 );
			fillArrayFromResource( "shiftedgamma.in.16", SHIFTED_GAMMA );
		}
		catch ( IOException e ) {
			throw new RuntimeException( e );
		}
	}
	
	/** The default size of the byte buffer in bytes (8Ki). */
	public final static int DEFAULT_BUFFER_SIZE = 8 * 1024;
	/** The underlying {@link InputStream}. */
	protected InputStream is;
	/** The number of bits actually read from this bit stream. */
	private long readBits;
	/** Current bit buffer: the lowest {@link #fill} bits represent the current content (the remaining bits are undefined). */
	private int current;
	/** The stream buffer. */
	protected byte[] buffer;
	/** Whether we should use the byte buffer. */
	private final boolean noBuffer;
	/** Current number of bits in the bit buffer (stored low). */
	protected int fill;
	/** Current position in the byte buffer. */
	protected int pos;
	/** Current number of bytes available in the byte buffer. */
	protected int avail;
	/** Current position of the first byte in the byte buffer. */
	protected long position;
	/** The cached file channel underlying {@link #is}, if any. */
	protected FileChannel fileChannel;
	/** {@link #is} cast to a positionable stream, if possible. */
	protected RepositionableStream repositionableStream;
	/** True if we are wrapping an array. */
	protected boolean wrapping;

	
	/** This (non-public) constructor exists just to provide fake initialisation for classes such as {@link DebugInputBitStream}.
	 */
	protected InputBitStream() {
		noBuffer = true;
	}

	/** Creates a new input bit stream wrapping a given input stream using a buffer of size {@link #DEFAULT_BUFFER_SIZE}.
	 *
	 * @param is the input stream to wrap.
	 */
	public InputBitStream( final InputStream is ) {
		this( is, DEFAULT_BUFFER_SIZE );
	}


	/** Creates a new input bit stream wrapping a given input stream with a specified buffer size.
	 *
	 * @param is the input stream to wrap.
	 * @param bufSize the size in byte of the buffer; it may be 0, denoting no buffering.
	 */
	public InputBitStream( final InputStream is, final int bufSize ) {
		this.is = is;
		if ( ! ( this.noBuffer = bufSize == 0 ) ) this.buffer = new byte[ bufSize ];

		if ( is instanceof RepositionableStream ) repositionableStream = (RepositionableStream)is;
			
		if ( repositionableStream == null ) {
			try {
				fileChannel = (FileChannel)( is.getClass().getMethod( "getChannel" ) ).invoke( is );
			}
			catch( IllegalAccessException e ) {}
			catch( IllegalArgumentException e ) {}
			catch( NoSuchMethodException e ) {}
			catch( java.lang.reflect.InvocationTargetException e ) {}
			catch( ClassCastException e ) {}
		}
	}

	/** Creates a new input bit stream wrapping a given byte array.
	 *
	 * @param a the byte array to wrap.
	 */
	public InputBitStream( final byte[] a ) {
		is = NullInputStream.getInstance();
		if ( a.length > 0 ) {
			buffer = a;
			avail = a.length;
			wrapping = true;
			noBuffer = false;
		}
		else {
			// A zero-length buffer is like having no buffer
			buffer = null;
			avail = 0;
			wrapping = false;
			noBuffer = true;
		}
	}

	/** Creates a new input bit stream reading from a file.
	 *
	 * @param name the name of the file.
	 * @param bufSize the size in byte of the buffer; it may be 0, denoting no buffering.
	 */
	public InputBitStream( final String name, final int bufSize ) throws FileNotFoundException {
		this( new FileInputStream( name ), bufSize );
	}

	/** Creates a new input bit stream reading from a file.
	 *
	 * @param name the name of the file.
	 */
	public InputBitStream( final String name ) throws FileNotFoundException {
		this( new FileInputStream( name ), DEFAULT_BUFFER_SIZE );
	}

	/** Creates a new input bit stream reading from a file.
	 *
	 * @param file the file.
	 */
	public InputBitStream( final File file ) throws FileNotFoundException {
		this( new FileInputStream( file ), DEFAULT_BUFFER_SIZE );
	}

	/** Creates a new input bit stream reading from a file.
	 *
	 * @param file the file.
	 * @param bufSize the size in byte of the buffer; it may be 0, denoting no buffering.
	 */
	public InputBitStream( final File file, final int bufSize ) throws FileNotFoundException {
		this( new FileInputStream( file ), bufSize );
	}


	/** Flushes the bit stream. All state information associated to the stream is reset. This
	 * includes bytes prefetched from the stream, bits in the bit buffer and unget'd bits.
	 *
	 * <P>This method is provided so that users of this class can easily wrap repositionable
	 * streams (for instance, file-based streams, which can be repositioned using
	 * the underlying {@link java.nio.channels.FileChannel}). It is guaranteed that after calling
	 * this method the underlying stream can be repositioned, and that the next read
	 * will draw data from the stream.
	 */

	public void flush() {
		if ( ! wrapping ) {
			position += pos;
			avail = 0;
			pos = 0;
		}
		fill = 0;
	}

	/** Closes the bit stream. All resources associated to the stream are released.
	 */

	public void close() throws IOException {
		if ( is == null ) return;
		if ( is != System.in ) is.close();
		is = null;
		buffer = null;
	}

	/** Returns the number of bits that can be read (or skipped over) from this
	 * bit stream without blocking by the next caller of a method.
	 *
	 * @return the number of bits that can be read from this bit stream without blocking.
	 */

	public long available() throws IOException {
		return ( is.available() + avail ) * 8 + fill;
	}


	/** Returns the number of bits read from this bit stream.
	 *
	 * @return the number of bits read so far.
	 */
	public long readBits() {
		return readBits;
	}

	/** Sets the number of bits read from this bit stream.
	 *
	 * <P>This method is provided so that, for instance, the 
	 * user can reset via <code>readBits(0)</code> the read-bits count
	 * after a {@link #flush()}.
	 *
	 * @param readBits the new value for the number of bits read so far.
	 */
	public void readBits( final long readBits ) {
		this.readBits = readBits;
	}

	/** Reads the next byte from the stream.
	 *
	 * <P>This method takes care of managing the buffering logic
	 * transparently.
	 *
	 * <P>However, this method does <em>not</em> update {@link #readBits}.
	 * The caller should increment {@link #readBits} by 8 at each call, unless
	 * the bit are used to load {@link #current}.
	 */

	private final int read() throws IOException {
		if ( noBuffer ) {
			final int t = is.read();
			if ( t == -1 ) throw new EOFException();
			else position++;
			return t;
		}

		if ( avail == 0 ) {
			avail = is.read( buffer );
			if ( avail == -1 ) {
				avail = 0;
				throw new EOFException();
			}
			else {
				position += pos;
				pos = 0;
			}
		}

		avail--;
		return buffer[ pos++ ] & 0xFF;