outputbitstream.java

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

		if ( x < MAX_PRECOMPUTED ) return writeInt( SHIFTED_GAMMA[ x ], SHIFTED_GAMMA[ x ] >>> 26 );

		final int msb = Fast.mostSignificantBit( x );
		final int l = writeUnary( msb + 1 );
		return l + ( msb > 0 ? writeInt( x, msb ) : 0 );
	}

	/** Writes a long natural number in shifted &gamma; coding.
	 *
	 * @param x a natural number.
	 * @return the number of bits written.
	 * @throws IllegalArgumentException if you try to write a negative number.
	 * @see #writeShiftedGamma(int)
	 */

	public int writeLongShiftedGamma( long x ) throws IOException {
		if ( x < 0 ) throw new IllegalArgumentException( "The argument " + x + " is negative" );
		if ( x < MAX_PRECOMPUTED ) return writeInt( SHIFTED_GAMMA[ (int)x ], SHIFTED_GAMMA[ (int)x ] >>> 26 );

		final int msb = Fast.mostSignificantBit( x );
		final int l = writeUnary( msb + 1 );
		return l + ( msb > 0 ? writeLong( x, msb ) : 0 );
	}


	/** Writes a natural number in &delta; coding.
	 *
	 * The &delta; coding of a positive number of <var>k</var> bits is
	 * obtained writing <var>k</var>-1 in &gamma; coding, followed by the
	 * lower <var>k</var>-1 bits of the number. The coding of a natural
	 * number is obtained by adding one and coding.
	 *
	 * @param x a natural number.
	 * @return the number of bits written.
	 * @throws IllegalArgumentException if you try to write a negative number.
	 */

	public int writeDelta( int x ) throws IOException {
		if ( x < 0 ) throw new IllegalArgumentException( "The argument " + x + " is negative" );
		if ( x < MAX_PRECOMPUTED ) return writeInt( DELTA[ x ], DELTA[ x ] >>> 26 );

		final int msb = Fast.mostSignificantBit( ++x );
		final int l = writeGamma( msb );
		return l + ( msb != 0 ? writeInt( x, msb ) : 0 );
	}

	/** Writes a long natural number in &delta; coding.
	 *
	 * @param x a long natural number.
	 * @return the number of bits written.
	 * @throws IllegalArgumentException if you try to write a negative number.
	 * @see #writeDelta(int)
	 */

	public int writeLongDelta( long x ) throws IOException {
		if ( x < 0 ) throw new IllegalArgumentException( "The argument " + x + " is negative" );
		if ( x < MAX_PRECOMPUTED ) return writeInt( DELTA[ (int)x ], DELTA[ (int)x ] >>> 26 );

		final int msb = Fast.mostSignificantBit( ++x );
		final int l = writeGamma( msb );
		return l + ( msb != 0 ? writeLong( x, msb ) : 0 );
	}

	/** Writes a natural number in a limited range using a minimal binary coding.
	 * 
	 * <p>A minimal binary code is an optimal code for the uniform distribution.
	 * This method uses an optimal code in which shorter words are assigned to 
	 * smaller integers.
	 *
	 * @param x a natural number.
	 * @param b a strict upper bound for <code>x</code>.
	 * @return the number of bits written.
	 * @throws IllegalArgumentException if you try to write a negative number or use a nonpositive base.
	 */

	public int writeMinimalBinary( final int x, final int b ) throws IOException {
		if ( b < 1 ) throw new IllegalArgumentException( "The bound " + b + " is not positive" );

		return writeMinimalBinary( x, b, Fast.mostSignificantBit( b ) );
	}

	/** Writes a natural number in a limited range using a minimal binary coding.
	 *
	 * This method is faster than {@link #writeMinimalBinary(int,int)} because it does not
	 * have to compute <code>log2b</code>.
	 *
	 * @param x a natural number.
	 * @param b a strict upper bound for <code>x</code>.
	 * @param log2b the floor of the base-2 logarithm of the bound.
	 * @return the number of bits written.
	 * @throws IllegalArgumentException if you try to write a negative number or use a nonpositive base.
	 * @see #writeMinimalBinary(int, int)
	 */

	public int writeMinimalBinary( final int x, final int b, final int log2b ) throws IOException {
		if ( x < 0 ) throw new IllegalArgumentException( "The argument " + x + " is negative" );
		if ( b < 1 ) throw new IllegalArgumentException( "The bound " + b + " is not positive" );
		if ( x >= b ) throw new IllegalArgumentException( "The argument " + x + " exceeds the bound " + b );

		// Numbers smaller than m are encoded in log2b bits.
		final int m = ( 1 << log2b + 1 ) - b; 

		if ( x < m ) return writeInt( x, log2b );
		else return writeInt( m + x, log2b + 1 );
	}


	/** Writes a long natural number in a limited range using a minimal binary coding.
	 *
	 * @param x a natural number.
	 * @param b a strict upper bound for <code>x</code>.
	 * @return the number of bits written.
	 * @throws IllegalArgumentException if you try to write a negative number or use a nonpositive base.
	 * @see #writeMinimalBinary(int, int)
	 */

	public int writeLongMinimalBinary( final long x, final long b ) throws IOException {
		if ( b < 1 ) throw new IllegalArgumentException( "The bound " + b + " is not positive" );

		return writeLongMinimalBinary( x, b, Fast.mostSignificantBit( b ) );
	}


	/** Writes a long natural number in a limited range using a minimal binary coding.
	 *
	 * This method is faster than {@link #writeLongMinimalBinary(long,long)} because it does not
	 * have to compute <code>log2b</code>.
	 *
	 * @param x a long natural number.
	 * @param b a strict upper bound for <code>x</code>.
	 * @param log2b the floor of the base-2 logarithm of the bound.
	 * @return the number of bits written.
	 * @throws IllegalArgumentException if you try to write a negative number or use a nonpositive base.
	 * @see #writeMinimalBinary(int, int)
	 */

	public int writeLongMinimalBinary( final long x, final long b, final int log2b ) throws IOException {
		if ( x < 0 ) throw new IllegalArgumentException( "The argument " + x + " is negative" );
		if ( b < 1 ) throw new IllegalArgumentException( "The bound " + b + " is not positive" );
		if ( x >= b ) throw new IllegalArgumentException( "The argument " + x + " exceeds the bound " + b );

		// Numbers smaller than m are encoded in log2b bits.
		final long m = ( 1 << log2b + 1 ) - b; 

		if ( x < m ) return writeLong( x, log2b );
		else return writeLong( m + x, log2b + 1 );
	}



	/** Writes a natural number in Golomb coding.
	 * 
	 * <p>Golomb coding with modulo <var>b</var> writes a natural number <var>x</var> as the quotient of
	 * the division of <var>x</var> and <var>b</var> in {@linkplain #writeUnary(int) unary}, 
	 * followed by the remainder in {@linkplain #writeMinimalBinary(int, int) minimal binary code}.
	 *
	 * <P>This method implements also the case in which <code>b</code> is 0: in this case,
	 * the argument <code>x</code> may only be zero, and nothing will be written. 
	 *
	 * @param x a natural number.
	 * @param b the modulus for the coding.
	 * @return the number of bits written.
	 * @throws IllegalArgumentException if you try to write a negative number or use a negative modulus.
	 */

	public int writeGolomb( final int x, final int b ) throws IOException {
		return writeGolomb( x, b, Fast.mostSignificantBit( b ) );
	}

	/** Writes a natural number in Golomb coding.
	 *
	 * This method is faster than {@link #writeGolomb(int,int)} because it does not
	 * have to compute <code>log2b</code>.
	 *
	 * @param x a natural number.
	 * @param b the modulus for the coding.
	 * @param log2b the floor of the base-2 logarithm of the coding modulus (it is irrelevant when <code>b</code> is zero).
	 * @return the number of bits written.
	 * @throws IllegalArgumentException if you try to write a negative number or use a negative modulus.
	 * @see #writeGolomb(int, int)
	 */

	public int writeGolomb( final int x, final int b, final int log2b ) throws IOException {
		if ( x < 0 ) throw new IllegalArgumentException( "The argument " + x + " is negative" );
		if ( b < 0 ) throw new IllegalArgumentException( "The modulus " + b + " is negative" );
		if ( b == 0 ) {
			if ( x != 0 ) throw new IllegalArgumentException( "The modulus is 0, but the argument is " + x );
			return 0;
		}

		final int l = writeUnary( x / b );

		// The remainder to be encoded.
		return l + writeMinimalBinary( x % b, b, log2b );
	}



	/** Writes a long natural number in Golomb coding.
	 *
	 * @param x a long natural number.
	 * @param b the modulus for the coding.
	 * @return the number of bits written.
	 * @throws IllegalArgumentException if you try to write a negative number or use a negative modulus.
	 * @see #writeGolomb(int, int)
	 */

	public long writeLongGolomb( final long x, final long b ) throws IOException {
		return writeLongGolomb( x, b, Fast.mostSignificantBit( b ) );
	}

	/** Writes a long natural number in Golomb coding.
	 *
	 * This method is faster than {@link #writeLongGolomb(long,long)} because it does not
	 * have to compute <code>log2b</code>.
	 *
	 * @param x a long natural number.
	 * @param b the modulus for the coding.
	 * @param log2b the floor of the base-2 logarithm of the coding modulus (it is irrelevant when <code>b</code> is zero).
	 * @return the number of bits written.
	 * @throws IllegalArgumentException if you try to write a negative number or use a negative modulus.
	 * @see #writeGolomb(int, int)
	 */

	public long writeLongGolomb( final long x, final long b, final int log2b ) throws IOException {

		if ( x < 0 ) throw new IllegalArgumentException( "The argument " + x + " is negative" );
		if ( b < 1 ) throw new IllegalArgumentException( "The modulus " + b + " is not positive" );
		if ( b == 0 ) {
			if ( x != 0 ) throw new IllegalArgumentException( "The modulus is 0, but the argument is " + x );
			return 0;
		}

		final long l = writeLongUnary( x / b );

		// The remainder to be encoded.
		return l + writeLongMinimalBinary( x % b, b, log2b );
	}


	/** Writes a natural number in skewed Golomb coding.
	 *
	 * <P>This method implements also the case in which <code>b</code> is 0: in this case,
	 * the argument <code>x</code> may only be zero, and nothing will be written. 
	 *
	 * @param x a natural number.
	 * @param b the modulus for the coding.
	 * @return the number of bits written.
	 * @throws IllegalArgumentException if you try to write a negative number or use a negative modulus.
	 */

	public int writeSkewedGolomb( final int x, final int b ) throws IOException {
		if ( x < 0 ) throw new IllegalArgumentException( "The argument " + x + " is negative" );
		if ( b < 0 ) throw new IllegalArgumentException( "The modulus " + b + " is negative" );
		if ( b == 0 ) {
			if ( x != 0 ) throw new IllegalArgumentException( "The modulus is 0, but the argument is " + x );
			return 0;
		}

		final int i = Fast.mostSignificantBit( x / b + 1 );
		final int l = writeUnary( i );
		final int M = ( ( 1 << i + 1 ) - 1 ) * b;
		final int m = ( M / ( 2 * b ) ) * b;

		return l + writeMinimalBinary( x - m, M - m );
	}

	/** Writes a long natural number in skewed Golomb coding.
	 * 
	 * <P>This method implements also the case in which <code>b</code> is 0: in this case,
	 * the argument <code>x</code> may only be zero, and nothing will be written. 
	 *
	 * @param x a long natural number.
	 * @param b the modulus for the coding.
	 * @return the number of bits written.
	 * @throws IllegalArgumentException if you try to write a negative number or use a negative modulus.
	 * @see #writeSkewedGolomb(int, int)
	 */

	public long writeLongSkewedGolomb( final long x, final long b ) throws IOException {
		if ( x < 0 ) throw new IllegalArgumentException( "The argument " + x + " is negative" );
		if ( b < 0 ) throw new IllegalArgumentException( "The modulus " + b + " is negative" );
		if ( b == 0 ) {
			if ( x != 0 ) throw new IllegalArgumentException( "The modulus is 0, but the argument is " + x );
			return 0;
		}

		final long i = Fast.mostSignificantBit( x / b + 1 );
		final long l = writeLongUnary( i );
		final long M = ( ( 1 << i + 1 ) - 1 ) * b;
		final long m = ( M / ( 2 * b ) ) * b;

		return l + writeLongMinimalBinary( x - m, M - m );
	}


	/** Writes a natural number in &zeta; coding.
	 *
	 * <P>&zeta; coding (with modulo <var>k</var>) records positive numbers in
	 * the intervals
	 * [1,2<sup><var>k</var></sup>-1],[2<sup><var>k</var></sup>,2<sup><var>k</var>+1</sup>-1],&hellip;,[2<sup><var>hk</var></sup>,2<sup>(<var>h</var>+1)<var>k</var></sup>-1]
	 * by coding <var>h</var> in unary, followed by a minimal binary coding of
	 * the offset in the interval.  The coding of a natural number is obtained
	 * by adding one and coding.
	 * 
	 * <P>&zeta; codes were defined by 
	 * Paolo Boldi and Sebastiano Vigna in 
	 * &ldquo;<a href="http://vigna.dsi.unimi.it/papers.php#BoVCWWW">Codes for the World&minus;Wide Web</a>&rdquo;,
 	 * <i>Internet Math.</i>, 2(4):405-427, 2005. The paper contains also a detailed analysis.
	 * 
	 * @param x a natural number.
	 * @param k the shrinking factor.
	 * @return the number of bits written.
	 * @throws IllegalArgumentException if you try to write a negative number or use a nonpositive shrinking factor.
	 */

	public int writeZeta( int x, final int k ) throws IOException {
		if ( x < 0 ) throw new IllegalArgumentException( "The argument " + x + " is negative" );
		if ( k < 1 ) throw new IllegalArgumentException( "The shrinking factor " + k + " is not positive" );
		if ( k == 3 && x < MAX_PRECOMPUTED ) return writeInt( ZETA_3[ x ], ZETA_3[ x ] >>> 26 );

		final int msb = Fast.mostSignificantBit( ++x );
		final int h = msb / k;
		final int l = writeUnary( h );
		final int left = 1 << h * k;
		return l + ( x - left < left 
			? writeInt( x - left, h * k + k - 1 ) 
			: writeInt( x, h * k + k ) );
	}

	/** Writes a long natural number in &zeta; coding.
	 *
	 * @param x a long natural number.
	 * @param k the shrinking factor.
	 * @return the number of bits written.
	 * @throws IllegalArgumentException if you try to write a negative number or use a nonpositive shrinking factor.
	 * @see #writeZeta(int, int)
	 */

	public long writeLongZeta( long x, final int k ) throws IOException {
		if ( x < 0 ) throw new IllegalArgumentException( "The argument " + x + " is negative" );
		if ( k < 1 ) throw new IllegalArgumentException( "The shrinking factor " + k + " is not positive" );
		if ( k == 3 && x < MAX_PRECOMPUTED ) return writeInt( ZETA_3[ (int)x ], ZETA_3[ (int)x ] >>> 26 );

		final int msb = Fast.mostSignificantBit( ++x );
		final int h = msb / k;
		final int l = writeUnary( h );
		final long left = 1 << h * k;
		return l + ( x - left < left 
			? writeLong( x - left, h * k + k - 1 ) 
			: writeLong( x, h * k + k ) );
	}
	

	/** Writes a natural number in variable-length nibble coding.
	 *
	 * <P>Variable-length nibble coding records a natural number by padding its binary
	 * representation to the left using zeroes, until its length is a multiple of three.
	 * Then, the resulting string is
     * broken in blocks of 3 bits, and each block is prefixed with a bit, which is
     * zero for all blocks except for the last one. 
	 * @param x a natural number.
	 * @return the number of bits written.
	 * @throws IllegalArgumentException if you try to write a negative number.
	 */

	public int writeNibble( final int x ) throws IOException {
		if ( x < 0 ) throw new IllegalArgumentException( "The argument " + x + " is negative" );

		if ( x == 0 ) return writeInt( 8, 4 );
		final int msb = Fast.mostSignificantBit( x );
		int h = msb / 3;
		do {
			writeBit( h == 0 );
			writeInt( x >> h * 3 , 3 );
		} while( h-- != 0 );
		return ( ( msb / 3 ) + 1 ) << 2;
	}
	
	/** Writes a long natural number in variable-length nibble coding.
	 *
	 * @param x a long natural number.
	 * @return the number of bits written.
	 * @throws IllegalArgumentException if you try to write a negative number.
	 * @see #writeNibble(int)
	 */

	public int writeLongNibble( final long x ) throws IOException {
		if ( x < 0 ) throw new IllegalArgumentException( "The argument " + x + " is negative" );

		if ( x == 0 ) return writeInt( 8, 4 );
		final int msb = Fast.mostSignificantBit( x );
		int h = msb / 3;
		do {
			writeBit( h == 0 );
			writeInt( (int)( x >> h * 3 ) , 3 );
		} while( h-- != 0 );
		return ( ( msb / 3 ) + 1 ) << 2;
	}
	
}