outputbitstream.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.BooleanIterator;
import it.unimi.dsi.fastutil.io.RepositionableStream;

import java.io.Closeable;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.Flushable;
import java.io.IOException;
import java.io.OutputStream;
import java.nio.channels.FileChannel;


/** Bit-level output stream.
 *
 * <P>This class wraps any {@link OutputStream} so that you can treat it as
 * <em>bit</em> stream. Constructors and methods closely resemble those of
 * {@link OutputStream}. Data can be added to such a stream in several ways:
 * writing an integer or long in fixed-width, unary, &gamma;, &delta;, &zeta; and Golomb
 * coding, or providing a vector of bytes.
 * 
 * <P>This class can also {@linkplain #OutputBitStream(byte[]) wrap a byte
 * array}; this is much more lightweight than wrapping a {@link
 * FastByteArrayOutputStream} wrapping the array, but overflowing the array
 * will cause an {@link java.io.IOException}.
 * 
 * <P>Note that when writing using a vector of bytes bits are written in the natural
 * way: the first bit is bit 7 of the first byte, the eightth bit is bit 0 of
 * the first byte, the ninth bit is bit 7 of the second byte and so on. When
 * writing integers using some coding, instead, the <em>lower</em> bits are considered
 * for coding (in the fixed-width case, the given number of bits, otherwise
 * the lower bits starting from the most significant one).
 *
 * <h3>The bit stream format</h3>
 *
 * <P>The bit streams written by this class are <em>big endian</em>. That is, 
 * the first bit of the stream is bit 7 of the first byte, the eightth bit
 * is bit 0 of the first byte, the ninth bit is bit 7 of the second byte and so on.
 *
 * <P>Blocks of bits (such as coded integers) are written <em>starting from the
 * most significant bit</em>. In other words, if you take the first bytes of a stream
 * and print them in binary you will see exactly the sequence of bits you have
 * written. In particular, if you write 32-bit integers you will get a stream
 * which is identical to the one produced by a {@link java.io.DataOutput}.
 *
 * <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 byte-aligns the streams, flushes to the underlying byte stream
 * all data and resets the internal state. At this point, you can safely reposition
 * the underlying stream and write again afterwards. For instance, this is safe
 * and will perform as expected:
 * <PRE>
 * FileOutputStream fos = new FileOutputStream( ... );
 * OutputBitStream obs = new OutputBitStream( fos );
 * ... write operations on obs ...
 * obs.flush();
 * fos.getChannel().position( ... );
 * ... other write operations on obs ...
 * </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 output 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).  The
 * specified position must be byte aligned, as there is no clean way of reading
 * a fraction of a byte with the current APIs.
 *
 * </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.OutputStream
 * @see it.unimi.dsi.mg4j.io.InputBitStream
 * @author Sebastiano Vigna
 * @since 0.1
 * @deprecated Moved to <code>dsiutils</code>.
 */

@Deprecated
public class OutputBitStream implements Flushable, Closeable {
	 
	final static int MAX_PRECOMPUTED = 4096;
	
	private final static boolean DEBUG = false;

	/* Precomputed tables: the lower 24 bits contain the (right-aligned) code,
	 * the upper 8 bits contain the code length. */
	final static int[] GAMMA = new int[ MAX_PRECOMPUTED ], DELTA = new int[ MAX_PRECOMPUTED ], ZETA_3 = new int[ MAX_PRECOMPUTED ],
	SHIFTED_GAMMA = new int[ MAX_PRECOMPUTED ];

	static {
		/* We load all precomputed arrays from resource files, 
		 * to work around the limit on static initialiser code. */
		try {
			InputBitStream.fillArrayFromResource( "gamma.out.12", GAMMA );
			InputBitStream.fillArrayFromResource( "delta.out.12", DELTA );
			InputBitStream.fillArrayFromResource( "zeta3.out.12", ZETA_3 );
			InputBitStream.fillArrayFromResource( "shiftedgamma.out.12", SHIFTED_GAMMA );
		}
		catch ( IOException e ) {
			throw new RuntimeException( e );
		}
	}
	
	/** The default size of the byte buffer in bytes (16Ki). */
	public final static int DEFAULT_BUFFER_SIZE = 16 * 1024;
	/** The underlying {@link OutputStream}. */
	protected OutputStream os;
	/** The number of bits written to this bit stream. */
	private long writtenBits;
	/** Current bit buffer. */
	private int current;
	/** The stream buffer. */
	protected byte[] buffer;
	/** Current number of free bits in the bit buffer (the bits in the buffer are stored high). */
	protected int free;
	/** Current position in the byte buffer. */
	protected int pos;
	/** Current position of the underlying output stream. */
	protected long position;
	/** Current number of bytes available in the byte buffer. */
	protected int avail;
	/** Size of the small buffer for temporary usage. */
	final static int TEMP_BUFFER_SIZE = 128;
	/** The cached file channel underlying {@link #os}. */
	protected FileChannel fileChannel;
	/** {@link #os} cast to a positionable stream. */
	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 DebugOutputBitStream}.
	 */
	protected OutputBitStream() {}


	/** Creates a new output bit stream wrapping a given output stream using a buffer of size {@link #DEFAULT_BUFFER_SIZE}.
	 *
	 * @param os the output stream to wrap.
	 */
	public OutputBitStream( final OutputStream os ) {
		this( os, DEFAULT_BUFFER_SIZE );
	}



	/** Creates a new output bit stream wrapping a given output stream with a specified buffer size.
	 *
	 * @param os the output stream to wrap.
	 * @param bufSize the size in byte of the buffer; it may be 0, denoting no buffering.
	 */
	public OutputBitStream( final OutputStream os, final int bufSize ) {
		this.os = os;
		if ( bufSize != 0 ) {
			this.buffer = new byte[ bufSize ];
			avail = bufSize;
		}
		free = 8;

		if ( os instanceof RepositionableStream ) repositionableStream = (RepositionableStream)os;
		
		if ( repositionableStream == null ) {
			try {
				fileChannel = (FileChannel)( os.getClass().getMethod( "getChannel", new Class[] {} ) ).invoke( os, new Object[] {} );
			}
			catch( IllegalAccessException e ) {}
			catch( IllegalArgumentException e ) {}
			catch( NoSuchMethodException e ) {}
			catch( java.lang.reflect.InvocationTargetException e ) {}
			catch( ClassCastException e ) {}
		}
	}


	/** Creates a new output bit stream wrapping a given byte array.
	 *
	 * @param a the byte array to wrap.
	 */
	public OutputBitStream( final byte[] a ) {
		free = 8;
		buffer = a;
		avail = a.length;
		wrapping = true;
	}

	/** Creates a new output bit stream writing to 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 OutputBitStream( final String name, final int bufSize ) throws FileNotFoundException {
		this( new FileOutputStream( name ), bufSize );
	}

	/** Creates a new output bit stream writing to a file.
	 *
	 * @param name the name of the file.
	 */
	public OutputBitStream( final String name ) throws FileNotFoundException {
		this( new FileOutputStream( name ), DEFAULT_BUFFER_SIZE );
	}


	/** Creates a new output bit stream writing to file.
	 *
	 * @param file the file.
	 * @param bufSize the size in byte of the buffer; it may be 0, denoting no buffering.
	 */
	public OutputBitStream( final File file, final int bufSize ) throws FileNotFoundException {
		this( new FileOutputStream( file ), bufSize );
	}

	/** Creates a new output bit stream writing to a file.
	 *
	 * @param file the file.
	 */
	public OutputBitStream( final File file ) throws FileNotFoundException {
		this( new FileOutputStream( file ), DEFAULT_BUFFER_SIZE );
	}


	/** Flushes the bit stream.
	 *
	 * <P>This method will align the stream, write the bit buffer, empty the
	 * byte buffer and delegate to the {@link OutputStream#flush()} method of
	 * the underlying output stream.
	 *
	 * <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}). <P> It is guaranteed that after calling
	 * this method the underlying stream can be repositioned, and that the next
	 * write to the underlying output stream will start with the content of the
	 * first write method called afterwards.
	 */

	public void flush() throws IOException {
		align();
		if ( os != null ) {
			if ( buffer != null ) {
				os.write( buffer, 0, pos );
				position += pos;
				pos = 0;
				avail = buffer.length;
			}
			os.flush();
		}
	}


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

	public void close() throws IOException {
		if ( os == null ) return;
		flush();
		if ( os != System.out && os != System.err ) os.close();
		os = null;
		buffer = null;
	}

	/** Returns the number of bits written to this bit stream.
	 *
	 * @return the number of bits written so far.
	 */
	public long writtenBits() {
		return writtenBits;
	}

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

	/** Writes a byte to the stream.
	 *
	 * <P>This method takes care of managing the buffering logic transparently.
	 *
	 * <P>However, this method does <em>not</em> update {@link #writtenBits}.
	 * The caller should increment {@link #writtenBits} by 8 at each call.
	 */

	private void write( final int b ) throws IOException {
		if ( avail-- == 0 ) {
			if ( os == null ) {
				avail = 0;
				throw new IOException( "Array full" );
			}

			if ( buffer == null ) {
				os.write( b );
				position++;
				avail = 0;
				return;
			}
			os.write( buffer );
			position += buffer.length;
			avail = buffer.length - 1;
			pos = 0;
		}

		buffer[ pos++ ] = (byte)b;
	}


	/** Writes bits in the bit buffer, possibly flushing it.
	 *
	 * You cannot write more than {@link #free} bits with this method. However,
	 * after having written {@link #free} bits the bit buffer will be empty. In
	 * particular, there should never be 0 free bits in the buffer.
	 *
	 * @param b the bits to write in the <strong>lower</strong> positions; the remaining positions must be zero.
	 * @param len the number of bits to write (0 is safe and causes no action).
	 * @return the number of bits written.
	 * @throws IllegalArgumentException if one tries to write more bits than available in the buffer and debug is enabled.
	 */

	private int writeInCurrent( final int b, final int len ) throws IOException {

		//System.err.println("Writing " + len + " bits out of " + Fast.binary( b ) );

		if ( DEBUG ) if ( len > free ) throw new IllegalArgumentException( Integer.toString( len ) + " bit(s) to write, " + free + " available." );

		current |= ( b & ( ( 1 << len ) - 1 ) ) << ( free -= len );
		if ( free == 0 ) {
			write( current );
			free = 8;
			current = 0;
		}

		writtenBits += len;
		return len;
	}



	/** Aligns the stream.
	 *
	 * After a call to this method, the stream is byte aligned. Zeroes
	 * are used to pad it if necessary.
	 *
	 * @return the number of padding bits.
	 */

	public int align() throws IOException {
		if ( free != 8 ) return writeInCurrent( 0, free );
		else return 0;
	}

	/** Sets this stream bit position, if it is based  on a {@link RepositionableStream} or on a {@link java.nio.channels.FileChannel}. 
	 *
	 * <P>Given an underlying stream that implements {@link
	 * RepositionableStream} or that can provide a {@link
	 * java.nio.channels.FileChannel} via the <code>getChannel()</code> method,
	 * a call to this method has the same semantics of a {@link #flush()},
	 * followed by a call to {@link