6
\$\begingroup\$

Part 2 here.

I wrote this class for packing data.

Would it benefit from being named BitPacker rather than BitStream (and change write/read to pack/unpack), or it works as is?

How can I improve it? Any way to make it more efficient? How can I reduce the amount of code? I have a lot of copy/pasted code with minor things changed that I'm not sure how (if?) I can condense.

And, of course, any other comments.

using System;
using System.Collections;
using System.Collections.Generic;

/// <summary>
/// Used to store data as bits. Acts as a queue - first data added is the first data removed.
/// Data should be read in the same order it is written. If read in a different order, it gives undefined results.
/// Reading from an empty BitStream returns 0.
/// </summary>
public class BitStream
{
    ulong scratch_write;
    int scratch_write_bits;
    ulong scratch_read;
    int scratch_read_bits;
    Queue<ulong> buffer;

    /// <summary>
    /// How many bits are currently in the BitStream
    /// </summary>
    public long StoredBits
    {
        get;
        private set;
    }

    #region Constructors
    /// <summary>
    /// Make a new BitStream
    /// </summary>
    public BitStream()
    {
        scratch_write = 0;
        scratch_write_bits = 0;
        scratch_read = 0;
        scratch_read_bits = 0;
        buffer = new Queue<ulong>();
    }

    /// <summary>
    /// Make a new BitStream
    /// </summary>
    /// <param name="bitCount">How many bits you expect this stream will hold. A closer value nets increased performance.</param>
    public BitStream( long bitCount )
    {
        scratch_write = 0;
        scratch_write_bits = 0;
        scratch_read = 0;
        scratch_read_bits = 0;
        buffer = new Queue<ulong>( (int) IntDivideRoundUp( bitCount, 64 ) );
    }

    /// <summary>
    /// Make a new BitStream containing bits from the byte array
    /// NOTE: StoredBits may return a higher count than there are actual bits to read if the byte array came from another BitStream.
    /// </summary>
    /// <param name="bits">contains bits to be stored in the bitstream</param>
    public BitStream( byte[] bits )
    {
        scratch_write = 0;
        scratch_write_bits = 0;
        scratch_read = 0;
        scratch_read_bits = 0;
        buffer = new Queue<ulong>();
        foreach ( var bite in bits )
        {
            Write( bite, byte.MinValue, byte.MaxValue );
        }
    }
    #endregion

    /// <summary>
    /// Get the bits stored in a ulong array (left-endian)
    /// </summary>
    /// <returns>ulong array of bits</returns>
    public ulong[] GetUlongArray()
    {
        ResetBuffer();

        if ( scratch_write_bits > 0 )
        {
            ulong[] result = new ulong[ buffer.Count + 1 ];
            Array.Copy( buffer.ToArray(), result, buffer.Count );
            result[ buffer.Count ] = scratch_write;
            return result;
        }
        return buffer.ToArray();
    }

    /// <summary>
    /// Get the bits stored in a byte array (left-endian)
    /// </summary>
    /// <returns>byte array of bits</returns>
    public byte[] GetByteArray()
    {
        ResetBuffer();

        int extraBytes = (int) IntDivideRoundUp( scratch_write_bits, 8 );
        byte[] result = new byte[ buffer.Count * 8 + extraBytes ];
        Buffer.BlockCopy( buffer.ToArray(), 0, result, 0, result.Length - extraBytes );

        int index = buffer.Count * 8;
        int bits = scratch_write_bits;
        ulong scratch = scratch_write;
        while ( bits > 0 )
        {
            int bitsToStore = bits >= 8 ? 8 : bits;
            result[ index ] = (byte) ( scratch >> ( 64 - bitsToStore ) );
            scratch <<= bitsToStore;
            bits -= bitsToStore;
            index++;
        }
        return result;
    }

    /// <summary>
    /// Get the bits stored in a BitArray
    /// </summary>
    /// <returns>all bits in the stream in a BitArray</returns>
    public BitArray GetBitArray()
    {
        ResetBuffer();

        BitArray ba = new BitArray( buffer.Count * 64 + scratch_write_bits );
        var tempBuf = buffer.ToArray();
        int counter = 0;
        for ( int i = 0; i < ba.Count; i++ )
        {
            for ( int j = 0; j < 64; j++ )
            {
                ba[ counter ] = ( tempBuf[ i ] & ( (ulong) 1 << ( 63 - j ) ) ) > 0;
                counter++;
            }
        }

        for ( int i = 0; i < scratch_write_bits; i++ )
        {
            ba[ counter ] = ( scratch_write & ( (ulong) 1 << ( 63 - i ) ) ) > 0;
            counter++;
        }

        return ba;
    }

    #region Write

    /// <summary>
    /// Write bits to the stream
    /// </summary>
    /// <param name="data">bits to be written</param>
    /// <param name="bits">how many bits</param>
    protected void Write( ulong data, int bits )
    {
        if ( bits == 0 )
            return;
        scratch_write |= ( ( data << ( 64 - bits ) ) >> scratch_write_bits );
        scratch_write_bits += bits;

        if ( scratch_write_bits >= 64 )
        {
            buffer.Enqueue( scratch_write );
            scratch_write = 0;
            scratch_write_bits -= 64;
            if ( scratch_write_bits > 0 )
                scratch_write |= ( data << ( 64 - scratch_write_bits ) );
        }
        StoredBits += bits;
    }

    /// <summary>
    /// Write 1 bit to the stream
    /// </summary>
    /// <param name="data">bit to be written</param>
    public void Write( bool data )
    {
        Write( BitConverter.GetBytes( data )[ 0 ], 1 );
    }

    /// <summary>
    /// Write bits to the stream
    /// </summary>
    /// <param name="data">bits to be written</param>
    /// <param name="min">the minimum number that can be written</param>
    /// <param name="max">the maximum number that can be written</param>
    public void Write( byte data, byte min, byte max )
    {
        if ( min > max )
            swap( min, max );
        if ( data < min || data > max )
            throw new ArgumentOutOfRangeException( "data", data, "must be between min and max" );

        Write( data, BitsRequired( max ) );
    }

    /// <summary>
    /// Write bits to the stream
    /// </summary>
    /// <param name="data">bits to be written</param>
    /// <param name="min">the minimum number that can be written</param>
    /// <param name="max">the maximum number that can be written</param>
    public void Write( sbyte data, sbyte min, sbyte max )
    {
        if ( min > max )
            swap( min, max );
        if ( data < min || data > max )
            throw new ArgumentOutOfRangeException( "data", data, "must be between min and max" );

        if ( data == sbyte.MinValue )
        {
            Write( (ulong) data, 64 );
            return;
        }

        long data2 = data;
        int bits = BitsRequired( min, max );

        if ( data2 < 0 )
        {
            data2 = ~data2 | ( 1L << ( bits - 1 ) );
        }
        Write( (ulong) data2, bits );
    }

    /// <summary>
    /// Write bits to the stream
    /// </summary>
    /// <param name="data">bits to be written</param>
    /// <param name="min">the minimum number that can be written</param>
    /// <param name="max">the maximum number that can be written</param>
    public void Write( char data, char min, char max )
    {
        if ( min > max )
            swap( min, max );
        if ( data < min || data > max )
            throw new ArgumentOutOfRangeException( "data", data, "must be between min and max" );

        int bits = BitsRequired( min, max );
        Write( (ulong) data, bits );
    }

    /// <summary>
    /// Write bits to the stream
    /// </summary>
    /// <param name="data">bits to be written</param>
    /// <param name="min">the minimum number that can be written</param>
    /// <param name="max">the maximum number that can be written</param>
    public void Write( short data, short min, short max )
    {
        if ( min > max )
            swap( min, max );
        if ( data < min || data > max )
            throw new ArgumentOutOfRangeException( "data", data, "must be between min and max" );

        if ( data == short.MinValue )
        {
            Write( (ulong) data, 64 );
            return;
        }

        long data2 = data;
        int bits = BitsRequired( min, max );

        if ( data2 < 0 )
        {
            data2 = ~data2 | ( 1L << ( bits - 1 ) );
        }
        Write( (ulong) data2, bits );
    }

    /// <summary>
    /// Write bits to the stream
    /// </summary>
    /// <param name="data">bits to be written</param>
    /// <param name="min">the minimum number that can be written</param>
    /// <param name="max">the maximum number that can be written</param>
    public void Write( ushort data, ushort min, ushort max )
    {
        if ( min > max )
            swap( min, max );
        if ( data < min || data > max )
            throw new ArgumentOutOfRangeException( "data", data, "must be between min and max" );

        Write( data, BitsRequired( max ) );
    }

    /// <summary>
    /// Write bits to the stream
    /// </summary>
    /// <param name="data">bits to be written</param>
    /// <param name="min">the minimum number that can be written</param>
    /// <param name="max">the maximum number that can be written</param>
    public void Write( int data, int min, int max )
    {
        if ( min > max )
            swap( min, max );
        if ( data < min || data > max )
            throw new ArgumentOutOfRangeException( "data", data, "must be between min and max" );

        if ( data == int.MinValue )
        {
            Write( (ulong) data, 64 );
            return;
        }

        long data2 = data;
        int bits = BitsRequired( min, max );

        if ( data2 < 0 )
        {
            data2 = ~data2 | ( 1L << ( bits - 1 ) );
        }
        Write( (ulong) data2, bits );
    }

    /// <summary>
    /// Write bits to the stream
    /// </summary>
    /// <param name="data">bits to be written</param>
    /// <param name="min">the minimum number that can be written</param>
    /// <param name="max">the maximum number that can be written</param>
    public void Write( uint data, uint min, uint max )
    {
        if ( min > max )
            swap( min, max );
        if ( data < min || data > max )
            throw new ArgumentOutOfRangeException( "data", data, "must be between min and max" );

        Write( data, BitsRequired( max ) );
    }

    /// <summary>
    /// Write bits to the stream
    /// </summary>
    /// <param name="data">bits to be written</param>
    /// <param name="min">the minimum number that can be written</param>
    /// <param name="max">the maximum number that can be written</param>
    public void Write( long data, long min, long max )
    {
        if ( min > max )
            swap( min, max );
        if ( data < min || data > max )
            throw new ArgumentOutOfRangeException( "data", data, "must be between min and max" );

        if ( data == long.MinValue )
        {
            Write( (ulong) data, 64 );
            return;
        }

        int bits = BitsRequired( min, max );

        if ( data < 0 )
        {
            data = ~data | ( 1L << ( bits - 1 ) );
        }
        Write( (ulong) data, bits );
    }

    /// <summary>
    /// Write bits to the stream
    /// </summary>
    /// <param name="data">bits to be written</param>
    /// <param name="min">the minimum number that can be written</param>
    /// <param name="max">the maximum number that can be written</param>
    public void Write( ulong data, ulong min, ulong max )
    {
        if ( min > max )
            swap( min, max );
        if ( data < min || data > max )
            throw new ArgumentOutOfRangeException( "data", data, "must be between min and max" );

        Write( data, BitsRequired( max ) );
    }

    /// <summary>
    /// Write bits to the stream
    /// </summary>
    /// <param name="data">bits to be written</param>
    /// <param name="min">the minimum number that can be written</param>
    /// <param name="max">the maximum number that can be written</param>
    /// <param name="precision">how many digits after the decimal</param>
    public void Write( float data, float min, float max, byte precision )
    {
        if ( min > max )
            swap( min, max );
        if ( data < min || data > max )
            throw new ArgumentOutOfRangeException( "data", data, "must be between min and max" );

        int mult = IntPow( 10, precision );
        double infoMax = Math.Round( max * mult, MidpointRounding.AwayFromZero );
        double infoMin = Math.Round( min * mult, MidpointRounding.AwayFromZero );
        if ( infoMax > uint.MaxValue || -infoMax > uint.MaxValue || infoMin > uint.MaxValue || -infoMin > uint.MaxValue )
        {
            Write( (ulong) BitConverter.DoubleToInt64Bits( data ), 32 );
            return;
        }

        int info = (int) Math.Round( data * mult, MidpointRounding.AwayFromZero );
        Write( info, (int) infoMin, (int) infoMax );
    }

    /// <summary>
    /// Write bits to the stream
    /// </summary>
    /// <param name="data">bits to be written</param>
    /// <param name="min">the minimum number that can be written</param>
    /// <param name="max">the maximum number that can be written</param>
    /// <param name="precision">how many digits after the decimal</param>
    public void Write( double data, double min, double max, byte precision )
    {
        if ( min > max )
            swap( min, max );
        if ( data < min || data > max )
            throw new ArgumentOutOfRangeException( "data", data, "must be between min and max" );

        int mult = IntPow( 10, precision );
        double infoMax = Math.Round( max * mult, MidpointRounding.AwayFromZero );
        double infoMin = Math.Round( min * mult, MidpointRounding.AwayFromZero );
        if ( infoMax > ulong.MaxValue || -infoMax > ulong.MaxValue || infoMin > ulong.MaxValue || -infoMin > ulong.MaxValue )
        {
            Write( (ulong) BitConverter.DoubleToInt64Bits( data ), 64 );
            return;
        }

        long info = (long) Math.Round( data * mult, MidpointRounding.AwayFromZero );
        Write( info, (long) infoMin, (long) infoMax );
    }
    #endregion

    #region Read

    /// <summary>
    /// Read bits from the stream
    /// </summary>
    /// <param name="bits">How many bits to read</param>
    /// <returns>bits read in ulong form</returns>
    protected ulong Read( int bits )
    {
        StoredBits -= bits;

        if ( buffer.Count == 0 )
        {
            scratch_read = scratch_write;
            scratch_read_bits = scratch_write_bits;
        }

        if ( bits == 0 || ( buffer.Count == 0 && scratch_write_bits == 0 ) )
            return 0;

        ulong data = scratch_read >> ( 64 - bits );
        if ( scratch_read_bits < bits )
        {
            bits -= scratch_read_bits;
            if ( buffer.Count == 0 )
            {
                scratch_read = scratch_write;
                scratch_read_bits = scratch_write_bits;
                data |= ( scratch_read >> ( 64 - bits ) );
                scratch_read <<= bits;
                scratch_read_bits -= bits;
                scratch_write = scratch_read;
                scratch_write_bits = scratch_read_bits;
            }
            else
            {
                scratch_read = buffer.Dequeue();
                scratch_read_bits = 64;
                data |= ( scratch_read >> ( 64 - bits ) );
                scratch_read <<= bits;
                scratch_read_bits -= bits;
            }
        }
        else
        {
            scratch_read <<= bits;
            scratch_read_bits -= bits;
            if ( buffer.Count == 0 )
            {
                scratch_write = scratch_read;
                scratch_write_bits = scratch_read_bits;
            }
        }
        if ( StoredBits <= 0 ) // handle the case of asking for more bits than exist in the stream
        {
            StoredBits = 0;
            scratch_write = 0;
            scratch_write_bits = 0;
            scratch_read = 0;
            scratch_read_bits = 0;
        }

        return data;
    }

    /// <summary>
    /// Read a bit from the stream and write it to data
    /// </summary>
    /// <param name="data">the variable to be written to</param>
    public void Read( out bool data )
    {
        data = Read( 1 ) > 0;
    }

    /// <summary>
    /// Read bits from the stream and write that information to data.
    /// WARNING: If you read data in a different order than written, there is a possibility that the actual number written to data is outside of the given range. In such a case, you may want to check the bounds yourself.
    /// </summary>
    /// <param name="data">the variable to be written to</param>
    /// <param name="min">the smallest possible number that could have been written</param>
    /// <param name="max">the largest possible number that could have been written</param>
    public void Read( out ulong data, ulong min, ulong max )
    {
        if ( min > max )
            swap( min, max );

        int bits = BitsRequired( max );
        data = Read( bits );
    }

    /// <summary>
    /// Read bits from the stream and write that information to data.
    /// WARNING: If you read data in a different order than written, there is a possibility that the actual number written to data is outside of the given range. In such a case, you may want to check the bounds yourself.
    /// </summary>
    /// <param name="data">the variable to be written to</param>
    /// <param name="min">the smallest possible number that could have been written</param>
    /// <param name="max">the largest possible number that could have been written</param>
    public void Read( out uint data, uint min, uint max )
    {
        if ( min > max )
            swap( min, max );

        int bits = BitsRequired( max );
        data = (uint) Read( bits );
    }

    /// <summary>
    /// Read bits from the stream and write that information to data.
    /// WARNING: If you read data in a different order than written, there is a possibility that the actual number written to data is outside of the given range. In such a case, you may want to check the bounds yourself.
    /// </summary>
    /// <param name="data">the variable to be written to</param>
    /// <param name="min">the smallest possible number that could have been written</param>
    /// <param name="max">the largest possible number that could have been written</param>
    public void Read( out ushort data, ushort min, ushort max )
    {
        if ( min > max )
            swap( min, max );

        int bits = BitsRequired( max );
        data = (ushort) Read( bits );
    }

    /// <summary>
    /// Read bits from the stream and write that information to data.
    /// WARNING: If you read data in a different order than written, there is a possibility that the actual number written to data is outside of the given range. In such a case, you may want to check the bounds yourself.
    /// </summary>
    /// <param name="data">the variable to be written to</param>
    /// <param name="min">the smallest possible number that could have been written</param>
    /// <param name="max">the largest possible number that could have been written</param>
    public void Read( out byte data, byte min, byte max )
    {
        if ( min > max )
            swap( min, max );

        int bits = BitsRequired( max );
        data = (byte) Read( bits );
    }

    /// <summary>
    /// Read bits from the stream and write that information to data.
    /// WARNING: If you read data in a different order than written, there is a possibility that the actual number written to data is outside of the given range. In such a case, you may want to check the bounds yourself.
    /// </summary>
    /// <param name="data">the variable to be written to</param>
    /// <param name="min">the smallest possible number that could have been written</param>
    /// <param name="max">the largest possible number that could have been written</param>
    public void Read( out char data, char min, char max )
    {
        if ( min > max )
            swap( min, max );

        int bits = BitsRequired( max );
        data = (char) Read( bits );
    }

    /// <summary>
    /// Read bits from the stream and write that information to data.
    /// WARNING: If you read data in a different order than written, there is a possibility that the actual number written to data is outside of the given range. In such a case, you may want to check the bounds yourself.
    /// </summary>
    /// <param name="data">the variable to be written to</param>
    /// <param name="min">the smallest possible number that could have been written</param>
    /// <param name="max">the largest possible number that could have been written</param>
    public void Read( out long data, long min, long max )
    {
        if ( min > max )
            swap( min, max );

        int bits = BitsRequired( min, max );

        ulong readBits = Read( bits );

        if ( (long) readBits == long.MinValue )
        {
            data = (long) readBits;
            return;
        }

        if ( min < 0 || max < 0 )
        {
            ulong negative = readBits >> ( bits - 1 );
            if ( negative > 0 )
            {
                readBits ^= ( negative << ( bits - 1 ) );
                readBits = ~readBits;
                readBits |= ( negative << 63 );
            }
        }
        data = (long) readBits;
    }

    /// <summary>
    /// Read bits from the stream and write that information to data.
    /// WARNING: If you read data in a different order than written, there is a possibility that the actual number written to data is outside of the given range. In such a case, you may want to check the bounds yourself.
    /// </summary>
    /// <param name="data">the variable to be written to</param>
    /// <param name="min">the smallest possible number that could have been written</param>
    /// <param name="max">the largest possible number that could have been written</param>
    public void Read( out int data, int min, int max )
    {
        if ( min > max )
            swap( min, max );

        int bits = BitsRequired( min, max );

        uint readBits = (uint) Read( bits );

        if ( (int) readBits == int.MinValue )
        {
            data = (int) readBits;
            return;
        }

        if ( min < 0 || max < 0 )
        {
            uint negative = readBits >> ( bits - 1 );
            if ( negative > 0 )
            {
                readBits ^= ( negative << ( bits - 1 ) );
                readBits = ~readBits;
                readBits |= ( negative << 31 );
            }
        }
        data = (int) readBits;
    }

    /// <summary>
    /// Read bits from the stream and write that information to data.
    /// WARNING: If you read data in a different order than written, there is a possibility that the actual number written to data is outside of the given range. In such a case, you may want to check the bounds yourself.
    /// </summary>
    /// <param name="data">the variable to be written to</param>
    /// <param name="min">the smallest possible number that could have been written</param>
    /// <param name="max">the largest possible number that could have been written</param>
    public void Read( out short data, short min, short max )
    {
        if ( min > max )
            swap( min, max );

        int bits = BitsRequired( min, max );

        ushort readBits = (ushort) Read( bits );

        if ( (short) readBits == short.MinValue )
        {
            data = (short) readBits;
            return;
        }

        if ( min < 0 || max < 0 )
        {
            uint negative = (uint) readBits >> ( bits - 1 );
            if ( negative > 0 )
            {
                readBits ^= (ushort) ( negative << ( bits - 1 ) );
                readBits = (ushort) ~readBits;
                readBits |= (ushort) ( negative << 63 );
            }
        }
        data = (short) readBits;
    }

    /// <summary>
    /// Read bits from the stream and write that information to data.
    /// WARNING: If you read data in a different order than written, there is a possibility that the actual number written to data is outside of the given range. In such a case, you may want to check the bounds yourself.
    /// </summary>
    /// <param name="data">the variable to be written to</param>
    /// <param name="min">the smallest possible number that could have been written</param>
    /// <param name="max">the largest possible number that could have been written</param>
    public void Read( out sbyte data, sbyte min, sbyte max )
    {
        if ( min > max )
            swap( min, max );

        int bits = BitsRequired( min, max );

        byte readBits = (byte) Read( bits );

        if ( (sbyte) readBits == sbyte.MinValue )
        {
            data = (sbyte) readBits;
            return;
        }

        if ( min < 0 || max < 0 )
        {
            uint negative = (uint) readBits >> ( bits - 1 );
            if ( negative > 0 )
            {
                readBits ^= (byte) ( negative << ( bits - 1 ) );
                readBits = (byte) ~readBits;
                readBits |= (byte) ( negative << 63 );
            }
        }
        data = (sbyte) readBits;
    }


    /// <summary>
    /// Read bits from the stream and write that information to data.
    /// WARNING: If you read data in a different order than written, there is a possibility that the actual number written to data is outside of the given range. In such a case, you may want to check the bounds yourself.
    /// </summary>
    /// <param name="data">the variable to be written to</param>
    /// <param name="min">the smallest possible number that could have been written</param>
    /// <param name="max">the largest possible number that could have been written</param>
    /// <param name="precision">how many digits after the decimal</param>
    public void Read( out double data, double min, double max, byte precision )
    {
        if ( min > max )
            swap( min, max );

        int mult = IntPow( 10, precision );
        double infoMax = Math.Round( max * mult, MidpointRounding.AwayFromZero );
        double infoMin = Math.Round( min * mult, MidpointRounding.AwayFromZero );

        if ( infoMax > ulong.MaxValue || -infoMax > ulong.MaxValue || infoMin > ulong.MaxValue || -infoMin > ulong.MaxValue )
        {
            data = BitConverter.Int64BitsToDouble( (long) Read( 64 ) );
            return;
        }

        long readBits;
        Read( out readBits, (long) infoMax, (long) infoMin );
        data = readBits / (double) mult;
    }


    /// <summary>
    /// Read bits from the stream and write that information to data.
    /// WARNING: If you read data in a different order than written, there is a possibility that the actual number written to data is outside of the given range. In such a case, you may want to check the bounds yourself.
    /// </summary>
    /// <param name="data">the variable to be written to</param>
    /// <param name="min">the smallest possible number that could have been written</param>
    /// <param name="max">the largest possible number that could have been written</param>
    /// <param name="precision">how many digits after the decimal</param>
    public void Read( out float data, float min, float max, byte precision )
    {
        if ( min > max )
            swap( min, max );

        int mult = IntPow( 10, precision );
        float infoMax = (float) Math.Round( max * mult, MidpointRounding.AwayFromZero );
        float infoMin = (float) Math.Round( min * mult, MidpointRounding.AwayFromZero );

        if ( infoMax > uint.MaxValue || -infoMax > uint.MaxValue || infoMin > uint.MaxValue || -infoMin > uint.MaxValue )
        {
            data = (float) BitConverter.Int64BitsToDouble( (int) Read( 32 ) );
            return;
        }

        int readBits;
        Read( out readBits, (int) infoMax, (int) infoMin );
        data = readBits / (float) mult;
    }
    #endregion

    #region Helpers
    /// <summary>
    /// 
    /// </summary>
    /// <param name="max">the maximum number that will be written</param>
    /// <returns>how many bits are needed</returns>
    protected int BitsRequired( ulong max )
    {
        if ( max == 0 )
            return 1;
        for ( int i = 1; i < 64; i++ )
        {
            if ( max < ( (ulong) 1 << i ) )
                return i;
        }
        return 64;
    }

    /// <summary>
    /// 
    /// </summary>
    /// <param name="min">the minimum number that will be written</param>
    /// <param name="max">the maximum number that will be written</param>
    /// <returns>how many bits are needed</returns>
    protected int BitsRequired( sbyte min, sbyte max )
    {
        if ( min > max )
            swap( min, max );

        if ( min == sbyte.MinValue )
            return 8;

        int signBit = 0;
        if ( min < 0 )
        {
            min = (sbyte) ~min;
            signBit = 1;
        }
        if ( max < 0 )
        {
            max = (sbyte) ~max;
            signBit = 1;
        }
        return BitsRequired( ( max > min ) ? (ulong) max : (ulong) min ) + signBit;
    }

    /// <summary>
    /// 
    /// </summary>
    /// <param name="min">the minimum number that will be written</param>
    /// <param name="max">the maximum number that will be written</param>
    /// <returns>how many bits are needed</returns>
    protected int BitsRequired( short min, short max )
    {
        if ( min > max )
            swap( min, max );

        if ( min == short.MinValue )
            return 16;

        int signBit = 0;
        if ( min < 0 )
        {
            min = (short) ~min;
            signBit = 1;
        }
        if ( max < 0 )
        {
            max = (short) ~max;
            signBit = 1;
        }
        return BitsRequired( ( max > min ) ? (ulong) max : (ulong) min ) + signBit;
    }

    /// <summary>
    /// 
    /// </summary>
    /// <param name="min">the minimum number that will be written</param>
    /// <param name="max">the maximum number that will be written</param>
    /// <returns>how many bits are needed</returns>
    protected int BitsRequired( int min, int max )
    {
        if ( min > max )
            swap( min, max );

        if ( min == int.MinValue )
            return 32;

        int signBit = 0;
        if ( min < 0 )
        {
            min = ~min;
            signBit = 1;
        }
        if ( max < 0 )
        {
            max = ~max;
            signBit = 1;
        }
        return BitsRequired( ( max > min ) ? (ulong) max : (ulong) min ) + signBit;
    }

    /// <summary>
    /// 
    /// </summary>
    /// <param name="min">the minimum number that will be written</param>
    /// <param name="max">the maximum number that will be written</param>
    /// <returns>how many bits are needed</returns>
    protected int BitsRequired( long min, long max )
    {
        if ( min > max )
            swap( min, max );

        if ( min == long.MinValue )
            return 64;

        int signBit = 0;
        if ( min < 0 )
        {
            min = ~min;
            signBit = 1;
        }
        if ( max < 0 )
        {
            max = ~max;
            signBit = 1;
        }
        return BitsRequired( ( max > min ) ? (ulong) max : (ulong) min ) + signBit;
    }

    /// <summary>
    /// If scratch_read contains any bits, moves them to the head of the buffer.
    /// NOTE: Not a short operation, use only when necessary!
    /// </summary>
    protected void ResetBuffer()
    {
        if ( scratch_read_bits > 0 && scratch_read != scratch_write )
        {
            if ( scratch_write_bits > 0 )
                buffer.Enqueue( scratch_write );
            var oldBuf = buffer.ToArray();
            buffer.Clear();
            int tempBits = scratch_write_bits;
            scratch_write = 0;
            scratch_write_bits = 0;
            Write( scratch_read, scratch_read_bits );
            scratch_read = 0;
            scratch_read_bits = 0;
            for ( int i = 0; i < oldBuf.Length - 1; i++ )
                Write( oldBuf[ i ], 64 );
            Write( oldBuf[ oldBuf.Length - 1 ], tempBits );
        }
    }

    void swap<T>( T obj1, T obj2 )
    {
        T temp = obj1;
        obj1 = obj2;
        obj2 = temp;
    }

    long IntDivideRoundUp( long upper, long lower )
    {
        return ( upper + lower - 1 ) / lower;
    }

    int IntPow( int x, uint pow )
    {
        int ret = 1;
        while ( pow != 0 )
        {
            if ( ( pow & 1 ) == 1 )
                ret *= x;
            x *= x;
            pow >>= 1;
        }
        return ret;
    }
    #endregion
}

It works by determining how many bits are actually required to store a number based on the min and max (e.g. 63 needs 6 bits, 64 needs 7 bits).

Example use (as requested):

BitStream bs = new BitStream();
int min1 = -1000, max1 = 1000, num1 = 287;
float min2 = 0f, max2 = 50f, num2 = 16.78634f;
double min3 = double.MinValue, max3 = double.MaxValue, num3 = 9845216.1916526;
byte fltPrec = 2;
byte dblPrec = 0;

bs.Write( num1, min1, max1 ); // 12 bits (11 bits for 1000 plus 1 bit for negative sign)
bs.Write( num2, min2, max2, fltPrec ); // converts to 1679 int, 14 bits (maximum converted to int is 5000)
bs.Write( num3, min3, max3, dblPrec ); // precision is ignored here as min/max are too high to try to convert to an integer, so the value is stored using all 64 bits of the double
bs.Write( true ); // 1 bit
int num4;
float num5;
double num6;
bool checker;
bs.Read( out num4, min1, max1 ); // num4 = 287
bs.Read( out num5, min2, max2, fltPrec ); // num5 = 16.79, there is some loss of precision here
bs.Read( out num6, min3, max3, dblPrec ); // num6 = 9845216.1916526, no loss of precision
bs.Read( out checker ); // checker = true
int newNum;
bs.Read( out newNum, -100, 100 ); // newNum = 0 as there are no bits left in the BitStream
\$\endgroup\$
  • 5
    \$\begingroup\$ Could you please add a short example that shows how to use the class? \$\endgroup\$ – JanDotNet Jul 7 '16 at 7:59
  • \$\begingroup\$ So it's like a zip stream? How does the bit packing actually work? \$\endgroup\$ – t3chb0t Jul 7 '16 at 15:00
  • \$\begingroup\$ I added an example to the question. And an explanation for how it works (hope it's good enough). What's a zip stream? I googled that and just saw stuff for zip archive or something about video streaming. \$\endgroup\$ – Tim Jul 8 '16 at 20:05
8
\$\begingroup\$

Bug

The swap<T>() method isn't doing what you think it does, because the passed in T obj1, T obj2 aren't passed with the ref keyword the values ar only changed in that method not targeting the variable values of the calling method.

So this

int min = 10;
int max = 5;
swap(min, max);
Console.WriteLine(String.Format("{0} : {1}", min, max);

will output 10 : 5

But using the ref keyword wouldn't be that good either.


  • using regions is considered to be a antipattern, not only because of the reasons statet in the answer of the link, but also because having 4 regions indicates that your class is doing too much.

  • based on the .NET naming guidelines variables should be named using camelCase instead of snake_case casing.

  • you should always use braces {} although they might be optional. Using them will make your code less error prone.

    The least you should do is that you stick to a choosen style. Right now you are mixing the styles, sometimes using braces and sometimes you don't , e.g

    if ( data2 < 0 )
    {
        data2 = ~data2 | ( 1L << ( bits - 1 ) );
    }
    
  • by using constructor chaining, you can remove some of the duplicated code like so

    public BitStream()
    {
        scratch_write = 0;
        scratch_write_bits = 0;
        scratch_read = 0;
        scratch_read_bits = 0;
        buffer = new Queue<ulong>();
    }
    
    public BitStream(long bitCount)
        : this()
    {
        buffer = new Queue<ulong>((int)IntDivideRoundUp(bitCount, 64));
    }
    
    public BitStream(byte[] bits)
        : this()
    {
        foreach (var bite in bits)
        {
            Write(bite, byte.MinValue, byte.MaxValue);
        }
    }  
    

    or you can just initialize some of the values like so

    ulong scratch_write = 0;
    int scratch_write_bits = 0;
    ulong scratch_read = 0;
    int scratch_read_bits = 0;
    Queue<ulong> buffer = new Queue<ulong>();
    public BitStream()
    { }
    
    public BitStream(long bitCount)
    {
        buffer = new Queue<ulong>((int)IntDivideRoundUp(bitCount, 64));
    }
    
    public BitStream(byte[] bits)
    {
        foreach (var bite in bits)
        {
            Write(bite, byte.MinValue, byte.MaxValue);
        }
    }
    
  • the spaces after opening ( and before the closing ) are looking strange in my eyes. A C# developer wouldn't expect them.

    protected int BitsRequired( long min, long max )
    
\$\endgroup\$
  • \$\begingroup\$ Ah, I didn't even realize that about the swap method using value types, thanks for pointing that out. I like the second way of reducing the amount of code in the constructors. Is there a way I can reduce the code in my other methods where the only thing that's changed is the casted types? \$\endgroup\$ – Tim Jul 8 '16 at 20:11
  • \$\begingroup\$ Also, do you think this class is doing too much? All it's doing is writing and reading. I just used regions around them because it's a lot of code. \$\endgroup\$ – Tim Jul 8 '16 at 20:43
0
\$\begingroup\$

I think a slight improvement on this would be to add the absolute value of a negative min/max to the data and store it that way, rather than always using an extra bit for the negative sign. That way, in some cases it'll use the same amount of bits, where in other cases it could possibly save 1 bit (e.g. -20 to 1000).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.