How do I add bits to a MemoryStream

Question

So I've been trying to add bits of a value to a MemoryStream but the issue is I have no idea how. I've seen that it's used for performance when it comes to networking.

I know I want a function that takes the bit value and how many bits it takes to store that value. So for instance, to store the value 3 I would need to allocate 2 bits 0000 0000 0000 0011. I would essentially pack the bits into a byte array and then add that byte array to the MemoryStream

var ms = new MemoryStream();
ms.WriteByte(1);
ms.WriteByte(1);
ms.WriteByte(1);
ms.WriteByte(1);
ms.WriteByte(1);

WriteBits(2, 3);
WriteBits(1, 1);

void WriteBits(int numbBits, int value)
{
    /* Convert the "value" to a byte or bytes and add it to the MemoryStream */
}

How do I properly implement this?

Java Example

public void writeBits(int numBits, int value) {
    int bytePos = bitPosition >> 3;
    int bitOffset = 8 - (bitPosition & 7);
    bitPosition += numBits;
    for (; numBits > bitOffset; bitOffset = 8) {
        buffer[bytePos] &= ~bitMaskOut[bitOffset]; // mask out the desired area
        buffer[bytePos++] |= (value >> (numBits - bitOffset))
                & bitMaskOut[bitOffset];
        numBits -= bitOffset;
    }
    if (numBits == bitOffset) {
        buffer[bytePos] &= ~bitMaskOut[bitOffset];
        buffer[bytePos] |= value & bitMaskOut[bitOffset];
    } else {
        buffer[bytePos] &= ~(bitMaskOut[numBits] << (bitOffset - numBits));
        buffer[bytePos] |= (value & bitMaskOut[numBits]) << (bitOffset - numBits);
    }
}

Answer 1

So I've been trying to add bits of a value to a MemoryStream

You don't, MemoryStream only handles bytes.

So for instance, to store the value 3 I would need to allocate 2 bits

This would only be true if the range of values you want to store is [0, 3]. If you want the possibility of storing any larger value you need more bits.

How do I properly implement this?

you would need to implement your own bit-stream. The java example looks like it has a byte[] buffer, and a bitPosition. You would need to implement this. The bif-fiddeling code looks like it should work just about the same in c#. Once you have a byte[] it is trivial to write this out to whatever stream you want, and usually possible to send directly over the network.

I've seen that it's used for performance when it comes to networking

I think there is a significant misunderstanding here. While you could manually manipulate individual bits, in most cases it would just be a waste of (development) time.

In general, a better way to get good performance is to use existing, well optimized and designed libraries. And there are a variety of serialization libraries that converts objects to byte-streams for you. An example would be protobuf (.net), this actually encodes numbers with a variable number of bytes.

If you still need smaller data it is usually more efficient to use some form of compression. The old classic deflate usually gives good compromise between size and performance, while algorithms like lz4 prioritizes speed over compression ratio.

Answer 2

I had exactly the same problem and wrote an entire BitStream library which can handle any reads and writes of an arbitrary number of bits to a MemoryStream (and any other stream, too). The library is open-source, MIT-licensed and fast (https://github.com/martinweihrauch/BitStream).

Writing bits to a MemoryStream.

These are the steps to write a value to a certain number of bits to a specific position in the MemoryStream:

1. Have a Stream available, e. g. a MemoryStream(), to which you want to write.
2. Connect this Stream to a new Bitstream

using SharpBitStream;

uint[] testDataUnsigned = { 5, 62, 17, 50, 33 };
var ms = new MemoryStream();
var bs = new BitStream(ms);

3. Now, you can start writing to the BitStream like this:

foreach(var bits in testDataUnsigned)
{
    bs.WriteUnsigned(6, (ulong)bits);
}

Writing can be done as above by only providing the bitlength and the value, but you of course also have full controll of exactly where to write the bits like so:

bs.WriteUnsigned(3, 2, 4, 5);
// Overloaded signature of WriteUnsigned:
// public void WriteUnsigned(long offsetByteStream, int offsetBit, int bitLength, ulong value)
// For signed numbers (e. g. -17), use
// bs.WriteSigned(3, 2, 4, -5);

This means, you can control that you write to the 4th byte (3, because starting at 0) in the underlying byte Stream, starting from the the 3rd (=2) position of the byte with a length of 6 bits and the value 5 (=0b0101);

Reading works similarly:

1. Just read the next 6 bits, wherever your byte and bit position is (e. g. for loops, etc):

ulong number = bs.ReadUnsigned(6);
// For Signed, use 
// long number = bs.ReadSigned(6);

2. Read a specific position, in this example read 4 bits from 3rd byte in Stream (2= 3rd position), starting with bit #0:

ulong number = bs.ReadUnsigned(2, 0, 4);
// For signed, use
// long number = bs.ReadSigned(2, 0, 4);

Note: The bit offset is always counting from 0 from the left-most position.