Byte buffer writer

Question

This is a fraction of the binary writer I'm writing, and I'm trying find some way to improve it.

using System;
using System.Collections.Generic;
public class ByteBuffer
{
 // List used to hold all bytes that will be read
 private List<byte> buffer = new List<byte>(32);
 private int bitIndex = 0;
 /// <summary>
 /// Writes an n bits byte onto the buffer.
 /// </summary>
 public void Write(byte source, int n)
 {
 if ((n + bitIndex) / 8 > buffer.Count)
 {
 buffer.AddRange(new byte[(n + bitIndex) / 8 - buffer.Count]);
 }
 for (int i = 0; i < n; i++)
 {
 buffer[(bitIndex + i) / 8] |= (byte)(((source >> (n - 1 - i)) & 1) << (int)(7 - (bitIndex + i) % 8));
 }
 bitIndex += n;
 }
}

• Jeff Mercado: For what you're doing here, working with data at the bit level is overkill IMHO. The intrinsic type is the byte so you should work at that level at a minimum. You won't gain much in terms of efficiency and maintainability, in fact, it's quite the opposite. You're making it harder on yourself unnecessarily. Besides, that's why there's the BitArray type.
• svick: @JeffMercado In some cases, this is exactly what you need to do. For example, when implementing Huffman coding or some other compression algorithm.

Answer 1

I'm going to go out on a limb, not knowing the full extent of the use cases of the class, but there's a pretty decent class, BitArray that might handle your needs as such:

using System;
using System.Collections;
public class ByteBuffer
{
 // List used to hold all bytes that will be read
 private BitArray buffer;
 /// <summary>
 /// Writes an n bits byte onto the buffer.
 /// </summary>
 public void Write(byte source, int n)
 {
 buffer = Append(buffer, source, n);
 }
 private static BitArray Append(BitArray current, byte source, int n)
 {
 var count = current == null ? 0 : current.Count;
 var bools = new bool[count + n];
 if (count > 0)
 {
 current.CopyTo(bools, 0);
 }
 if (n > 0)
 {
 var after = new BitArray(new[] { source });
 for (int i = 0; i < n; i++)
 {
 bools[count + i] = after[i];
 }
 }
 return new BitArray(bools);
 }
}

Answer 2

If you're after efficiency, you shouldn't write bit by bit. For example, if bitIndex is currently 3 and you're writing the full 8 bits, just two steps are necessary: writing 5 bits to one byte and then the remaining 3 bits to another byte.

And depending on what you do, writing directly to some Stream might make more sense than using a List<byte>.

Also, you should probably check the input and throw and exception if n is not between 1 and 8.

• user15111: Well, about using a stream, I'm only using the List<byte> because of the automatic expansion and Add/AddRange, to exclude the need of a WriteIndex field. Would the stream overhead, in fact, worth it?
• svick: I mean, you're most likely going to write the result to a file or network anyway in the end, no? If that's the case, it would be more efficient to write it there as soon as possible.

Answer 3

I ended up with an implementation that looks like this:

using System.Diagnostics;
public class ByteBuffer
{
 public byte[] tempBuffer = new byte[16];
 public int tempIndex = 0;
 /// <summary>
 /// Writes the given number of bits.
 /// </summary>
 public void Write(byte value, int bits)
 {
 Debug.Assert(bits > 0 && bits < 9, "Number of bits must be between 1 and 8.");
 int localBitLen = (tempIndex % 8);
 if (localBitLen == 0)
 {
 tempBuffer[tempIndex >> 3] = value;
 tempIndex += bits;
 return;
 }
 tempBuffer[tempIndex >> 3] &= (byte)(255 >> (8 - localBitLen)); // clear before writing
 tempBuffer[tempIndex >> 3] |= (byte)(value << localBitLen); // write first half
 // need write into next byte?
 if (localBitLen + bits > 8)
 {
 tempBuffer[(tempIndex >> 3) + 1] &= (byte)(255 << localBitLen); // clear before writing
 tempBuffer[(tempIndex >> 3) + 1] |= (byte)(value >> (8 - localBitLen)); // write second half
 }
 tempIndex += bits;
 }
}

I was able to do it with the help of some calculators (I just hate being bad with bitwise operations).

I had to use a byte[] rather than a stream since I can't write directly on the stream back-buffer. I might implement the Read, and exponential expansion for the buffer tomorrow.