6
\$\begingroup\$

For a recent project I was in need of excessive bit manipulation. Specifically, I had to write to or read from a variable number of bits up from the least significant bit towards the most significant bit.

I created the following helper class since I had spare time and wanted to learn something. I made it work but feel very unsure about whether it's performance might be sub optimal.

/*
 * This class provides functions to read or write 1 to 8 bits to a stream at a time
 * The bits a read from the least significant to the most significant
 * 
 */
public class BitStreamer : IDisposable {
    /*
     * Initializes a BitStreamer on a source Stream with a bps of 1
     */
    public BitStreamer(Stream source) : base(source, 1) { }

    public BitStreamer(Stream source, int bps) {
        if(bps <= 0 | bps > 8) 
            throw new ArgumentException("The bits per sample has to be in the range of a byte (1 to 8)");
        m_strSource = source;
        m_iBitsPerSample = bps;
        m_iPosition = 0;
        m_iLength = source.Length;
        m_bEndOfStream = false;
    }
    /* Bits per sample */
    private int m_iBitsPerSample;

    /* Base stream */
    private Stream m_strSource;

    /* Binary stream helpers */
    private BinaryReader m_bstrSrc;
    private BinaryWriter m_bstwSrc;

    /* Byte stream fields */
    private bool m_bEndOfStream;
    private long m_iPosition;
    private long m_iLength;

    /* Bit stream fields */
    private byte m_bCurrentByte;
    private byte m_bInBytePosition;
    private byte m_bCurrentBits;

Methods for bit writing

    /*
     * Write up to 8 bits to the current buffer
     */
    public void WriteBits(byte b) {
        m_bCurrentBits = 0;
        for(int i = 0; i < m_iBitsPerSample; i++) {
            byte bit = (byte)(b & (1 << i));
            m_bCurrentBits = (byte)(m_bCurrentBits | bit);
            WriteBit(bit);
        }
    }

    /*
     * Write a bit to the current byte buffer
     */
    public void WriteBit(byte bit) {
        if(m_bInBytePosition > 7) 
            WriteCurrentByte();                         

        byte tar = m_bCurrentByte;
        byte nbt = (byte)((tar & ~(1 << m_bInBytePosition)) | (bit << m_bInBytePosition));
        m_bCurrentByte = nbt;
        m_bInBytePosition += 1;
    }

    /*
     * Writes the current byte and starts a new one
     */
    protected void WriteCurrentByte() {
        if(m_bstwSrc == null) m_bstwSrc = new BinaryWriter(m_strSource);
        m_bstwSrc.Write(m_bCurrentByte);
        m_bCurrentByte = 0;
        m_bInBytePosition = 0;
        m_iPosition += 1;
        m_iLength = m_iPosition;
    }

Methods for bit reading

    /*
     * Get up to 8 bits at a time within a byte 
     */
    public byte GetNextBits() {
        byte result = GetNextBit();         
        for(int i = 1; i < m_iBitsPerSample; i++) {             
            result = (byte)((1 << result) & GetNextBit());              
        }
        m_bCurrentBits = result;            
        return result;
    }       

    /* 
     * Get the next bit of the stream OR 0xFF on EndOfStreamException
     * Advance in byte stream if current byte is exhausted
     */
    public byte GetNextBit() {
        if(m_bInBytePosition > 7) // ReadNextByte does have side effects!
            if(!ReadNextByte()) return 0xFF;

        m_bCurrentBits = (byte)((m_bCurrentByte & (1 << m_bInBytePosition)) >> m_bInBytePosition);
        m_bInBytePosition += 1;
        return m_bCurrentBits;
    }

    /* 
     * Gets next byte of the stream and put's it into the buffer.
     * Returns false on EndOfStreamException
     */
    protected bool ReadNextByte() {
        if(m_bEndOfStream) return false;

        try {
            if(m_bstrSrc == null) m_bstrSrc = new BinaryReader(m_strSource);
            m_bCurrentByte = m_bstrSrc.ReadByte();          
        } catch(EndOfStreamException) {
            m_bEndOfStream = true;
            return false;
        }
        m_bInBytePosition = 0;
        if(++m_iPosition >= m_iLength) m_bEndOfStream = true;
        return true;
    }

Some Properties

    public bool AtEndOfStream { get { return m_bEndOfStream; } }
    public long Position { get { return m_iPosition; } }
    public long Length { get { return m_iLength; } }
    public byte InBytePosition { get { return m_bInBytePosition; } }
    public byte CurrentByte { get { return m_bCurrentByte; } }
    public int BitsPerSample { get { return m_iBitsPerSample; } }
    public Stream BaseStream { get { return m_strSource; } }
    public virtual string Status { 
        get {
            return String.Format("Current byte (0x{0}) = {1,8} and current bit(s) ({2}): {3,8}",
                    m_iPosition.ToString("X4"),
                    Convert.ToString(m_bCurrentByte, 2),
                    m_bInBytePosition.ToString(),
                    Convert.ToString(m_bCurrentBits, 2)
                );
        }
    }

Handle IDisposable

    public void Close() {
        this.Dispose();
    }
    public void Dispose() {
        Dispose(true);
        GC.SuppressFinalize(this);
    }
    protected virtual void Dispose(bool disposing) {
        if (disposed) return; 

        if (disposing) {
            if(m_strSource != null) {
                m_strSource.Close();
                m_bstrSrc = null;
                m_bstwSrc = null;
                m_strSource = null;
            }
        }
        disposed = true;
    }
    private bool disposed = false;
}
\$\endgroup\$
4
\$\begingroup\$

Here are my suggestions:

Basic stuff

  • favor naming conventions beginning by an underscore instead of the C++ m_
  • stay away from that practice of specifying the type in 1st letter like iBitsPerSample
  • not sure you really need that IDisposable pattern, Stream is a managed object
  • this can be an endless debate but there's no real need to nullify fields, throwing a ObjectDisposedException is simpler and more informative to the user
  • using try ... catch is probably overkill
  • IMO there are twice as much properties/fields as one might ever need
  • you should not restrain the user to be able to read only 1 to 8 bits at a times

Intermediate

By trying to code some implementation for you I first thought deriving from Stream but this proved to not be the best approach since the lowest common denominator for all its derived is byte, but you want bits.

Thinking a bit, following idea came out, do like BinaryReader.

This has many advantages :

  • you offload the reading/writing to any possible type of stream (memory, network, file etc ...)
  • the reading/writing logic is separated from any stream implementation
  • makes things simpler in the end

In short, craft BitReader/Writer classes !

Here's my code, feel free to improve it:

public class BitReader : IDisposable
{
    private readonly bool _leaveOpen;
    private readonly Stream _stream;
    private int _byte;
    private bool _canRead;
    private int _counter;

    public BitReader(Stream stream, bool leaveOpen = true)
    {
        if (stream == null) throw new ArgumentNullException("stream");
        _stream = stream;
        _leaveOpen = leaveOpen;
    }

    public void Dispose()
    {
        if (!_leaveOpen)
        {
            _stream.Dispose();
        }
    }

    public int Read(byte[] buffer, int count)
    {
        // simple wrapper to read many bits at once
        var bits = Math.Min(count, buffer.Length);
        for (var i = 0; i < bits; i++)
        {
            byte bit;

            if (!Read(out bit))
            {
                return i;
            }

            buffer[i] = bit;
        }
        return bits;
    }

    public bool Read(out byte bit)
    {
        // do we need to provision our bit buffer ?
        if (!_canRead)
        {
            _byte = _stream.ReadByte();
            _canRead = true;
        }

        // we are at EOF
        if (_byte == -1)
        {
            bit = 0;
            return false;
        }

        // get current bit and update our counter
        var value = (_byte >> _counter) & 1;
        _counter++;
        if (_counter > 7)
        {
            _counter = 0;
            _canRead = false;
        }

        bit = (byte) value;
        return true;
    }
}

Notes:

  • i use like Stream.Read, an integer to tell how many bits have been read into user's buffer
  • i use a bool to signal whether a bit read has been successful or not

Now some demo :D

public class Demo
{
    public Demo()
    {
        var random = new Random(0);
        var buffer = new byte[100];
        random.NextBytes(buffer);

        using (var stream = new MemoryStream(buffer))
        using (var reader = new BitReader(stream))
        {
            // read bits one by one
            var bits = new List<byte>();
            for (var i = 0; i < buffer.Length*8; i++)
            {
                byte bit;
                if (reader.Read(out bit))
                {
                    bits.Add(bit);
                }
            }

            // check that our thing worked
            var verify = new List<byte>();
            for (var i = 0; i < 100; i++)
            {
                var value = 0;
                bits.Skip(i*8).Take(8).Select((s, t) => value |= s << t).ToArray(); // lazy way :)
                verify.Add((byte) value);
            }

            var sequenceEqual = verify.SequenceEqual(buffer);
            if (!sequenceEqual)
            {
                throw new InvalidDataException();
            }
        }
    }
}

TODO:

  • code a writer !
  • implement some useful properties you'd like to have like BitsRead etc ...

Advice

Code only what you really need, do not try to think for the future but only about what you need right now.

Optimization should take place at the end and only if really needed (do some profiling first).

Learn to be lazy when programming, often it leads to better solutions by their simplicity yet highly efficient. Overthinking is not always the best thing to do.

Bonus:

Here's some endianness-aware reader I needed for a game, in the beginning it was bulky/inefficient then I started it from scratch by simply implementing what I really needed. Over time I upgraded it by adding overloads, until some pattern came out. As you can see there are hub methods that do most of the work.

This is not a direct help to your current work but a hint of how laziness and clarity is helpful, by being lazy you won't waste more time than a thing deserves and by being clear your code can be upgraded more easily.

using System;
using System.Collections.Generic;
using System.IO;
using System.Text;

// ReSharper disable RedundantTypeArgumentsOfMethod

namespace Assets.Scripts.Extensions
{
    public static class BinaryReaderExtensions
    {
        public enum Endianness
        {
            LittleEndian,
            BigEndian
        }

        private static readonly Endianness PlatformEndianness = BitConverter.IsLittleEndian
            ? Endianness.LittleEndian
            : Endianness.BigEndian;

        public static string ReadStringAscii(this BinaryReader reader, int length)
        {
            var bytes = reader.ReadBytes(length);
            var s = Encoding.ASCII.GetString(bytes);
            return s;
        }

        public static string ReadStringAsciiNullTerminated(this BinaryReader reader)
        {
            var list = new List<byte>();
            byte b;
            while ((b = reader.ReadByte()) != 0)
            {
                list.Add(b);
            }
            var s = Encoding.ASCII.GetString(list.ToArray());
            return s;
        }

        #region Numbers (with offset)

        private static uint ReadUInt32(BinaryReader reader, Endianness endianness, long offset)
        {
            return ReadAt(reader, offset, () => reader.ReadUInt32(endianness));
        }

        public static uint ReadUInt32BE(this BinaryReader reader, long offset)
        {
            return ReadUInt32(reader, Endianness.BigEndian, offset);
        }

        public static uint ReadUInt32LE(this BinaryReader reader, long offset)
        {
            return ReadUInt32(reader, Endianness.LittleEndian, offset);
        }

        public static void SetPosition(this BinaryReader reader, long offset)
        {
            reader.BaseStream.Position = offset;
        }

        private static T ReadAt<T>(BinaryReader reader, long offset, Func<T> func)
        {
            reader.SetPosition(offset);
            var t = func();
            return t;
        }

        #endregion

        #region Numbers (with endianness)

        public static short ReadInt16(this BinaryReader reader, Endianness endianness)
        {
            var i = reader.ReadInt16();
            return Convert(i, endianness);
        }

        public static int ReadInt32(this BinaryReader reader, Endianness endianness)
        {
            var i = reader.ReadInt32();
            return Convert(i, endianness);
        }

        public static ushort ReadUInt16(this BinaryReader reader, Endianness endianness)
        {
            var i = reader.ReadUInt16();
            return Convert(i, endianness);
        }

        public static uint ReadUInt32(this BinaryReader reader, Endianness endianness)
        {
            var i = reader.ReadUInt32();
            return Convert(i, endianness);
        }

        private static short Convert(short i, Endianness endianness)
        {
            return endianness == PlatformEndianness ? i : Reverse(i);
        }

        private static int Convert(int i, Endianness endianness)
        {
            return endianness == PlatformEndianness ? i : Reverse(i);
        }

        private static ushort Convert(ushort i, Endianness endianness)
        {
            return endianness == PlatformEndianness ? i : Reverse(i);
        }

        private static uint Convert(uint i, Endianness endianness)
        {
            return endianness == PlatformEndianness ? i : Reverse(i);
        }

        private static short Reverse(short i)
        {
            return (short) (((i & 0xFF00) >> 8) |
                            ((i & 0x00FF) << 8));
        }

        public static int SwapEndianness(int value)
        {
            var b1 = (value >> 0) & 0xff;
            var b2 = (value >> 8) & 0xff;
            var b3 = (value >> 16) & 0xff;
            var b4 = (value >> 24) & 0xff;

            return b1 << 24 | b2 << 16 | b3 << 8 | b4 << 0;
        }

        private static int Reverse(int i)
        {
            return SwapEndianness(i);
        }

        private static ushort Reverse(ushort i)
        {
            return (ushort) (((i & 0xFF00) >> 8) |
                             ((i & 0x00FF) << 8));
        }

        private static uint Reverse(uint i)
        {
            return ((i & 0xFF000000) >> 24) |
                   ((i & 0x00FF0000) >> 8) |
                   ((i & 0x0000FF00) << 8) |
                   ((i & 0x000000FF) << 24);
        }

        #endregion

        #region Numbers (single)

        public static short ReadInt16BE(this BinaryReader reader)
        {
            return ReadInt16(reader, Endianness.BigEndian);
        }

        public static int ReadInt32BE(this BinaryReader reader)
        {
            return ReadInt32(reader, Endianness.BigEndian);
        }

        public static int ReadInt32LE(this BinaryReader reader)
        {
            return ReadInt32(reader, Endianness.LittleEndian);
        }

        public static ushort ReadUInt16BE(this BinaryReader reader)
        {
            return ReadUInt16(reader, Endianness.BigEndian);
        }

        public static ushort ReadUInt16LE(this BinaryReader reader)
        {
            return ReadUInt16(reader, Endianness.LittleEndian);
        }

        public static uint ReadUInt32BE(this BinaryReader reader)
        {
            return ReadUInt32(reader, Endianness.BigEndian);
        }

        public static uint ReadUInt32LE(this BinaryReader reader)
        {
            return ReadUInt32(reader, Endianness.LittleEndian);
        }

        #endregion

        #region Numbers (array)

        public static short[] ReadInt16BEs(this BinaryReader reader, int count)
        {
            return Read<short>(count, reader.ReadInt16BE);
        }

        public static int[] ReadInt32BEs(this BinaryReader reader, int count)
        {
            return Read<int>(count, reader.ReadInt32BE);
        }

        public static int[] ReadInt32LEs(this BinaryReader reader, int count)
        {
            return Read<int>(count, reader.ReadInt32LE);
        }

        public static ushort[] ReadUInt16BEs(this BinaryReader reader, int count)
        {
            return Read<ushort>(count, reader.ReadUInt16BE);
        }

        public static ushort[] ReadUInt16LEs(this BinaryReader reader, int count)
        {
            return Read<ushort>(count, reader.ReadUInt16LE);
        }

        public static uint[] ReadUInt32BEs(this BinaryReader reader, int count)
        {
            return Read<uint>(count, reader.ReadUInt32BE);
        }

        public static uint[] ReadUInt32LEs(this BinaryReader reader, int count)
        {
            return Read<uint>(count, reader.ReadUInt32LE);
        }

        private static T[] Read<T>(int count, Func<T> func)
        {
            if (count <= 0) throw new ArgumentOutOfRangeException("count");
            if (func == null) throw new ArgumentNullException("func");
            var t = new T[count];
            for (var i = 0; i < t.Length; i++)
            {
                t[i] = func();
            }
            return t;
        }

        #endregion
    }
}
\$\endgroup\$
  • \$\begingroup\$ I really like your BitReader approach, as it seems much cleaner and obviously more scalable. I restricted the user to 1 to 8 bits since I didn't care about reading more than 8 bits at a time and it seemed easier this way. So slight 'under-thinking' there. The overthinking part of implementing so many properties was due to me debugging the class. My class actually looks a little more like yours now. In large part thanks to your effort! \$\endgroup\$ – MrPaulch Aug 15 '15 at 19:49
  • \$\begingroup\$ Trivia: I know the usage of the hungarian notation is not recommended for C# but in my workflow it's pretty established (unconsciously prefixing the type and then using intelli-sense) I do restrain the usage of that notation to private fields (not even protected/internals) \$\endgroup\$ – MrPaulch Aug 15 '15 at 19:50
  • \$\begingroup\$ Thanks, glad to see it helped ! You're right by the way, such notation can be preferred at times, even with C# :D \$\endgroup\$ – Aybe Aug 16 '15 at 12:04

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.