Today we continue to explore how we can store values in less than a byte. We’ll expand the BitStream struct with the capability to write values in addition to just reading them. Read on to see how to implement this functionality and for the full source code which you can use in your projects.

Status

When we left off last time, we had built a BitStream struct that looks like this:

public struct BitStream
{
   public interface IByteStream
   {
      byte Read(int index);
   }
 
   public int BitIndex;
 
   public byte ReadUpTo8<TByteStream>(in TByteStream stream, int num)
      where TByteStream : IByteStream
   {
      // ...
   }
 
   public ushort ReadUpTo16<TByteStream>(in TByteStream stream, int num)
      where TByteStream : IByteStream
   {
      // ...
   }
 
   public uint ReadUpTo32<TByteStream>(in TByteStream stream, int num)
      where TByteStream : IByteStream
   {
      // ...
   }
 
   public ulong ReadUpTo64<TByteStream>(in TByteStream stream, int num)
      where TByteStream : IByteStream
   {
      // ...
   }
}

This allows us to write to streams of bits regardless of their underlying collection type: NativeArray<byte>, byte[], etc. The contents of those bit streams can be whatever the user of BitStream wants. For example, here’s an array of four 4-bit integers a, b, c, and d that get packed into a bit stream of 2 bytes (16 bits):

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
a a a a b b b b c c c c d d d d
Code Design

We’ll continue to use the same three main goals that we had from last time:

  • Efficiency: Only the minimum number of memory accesses, branches, and bitwise operations should be performed.
  • Burst Support: All accesses should be able to be compiled by Burst.
  • Code Reuse: The container of the bits should be abstracted from the code that accesses the bits.

We’ll also add one more:

  • Read-Only: Read-only bit streams should be supported.

We’re already set up for success on the first three goals, but the last will require a change to our current design. If we simply added a Write method to IByteStream then we wouldn’t support read-only bit streams very cleanly. Sure, Write could be implemented to throw an exception or otherwise error, but it’s better to check for problems at compile time than at runtime if possible.

So for today’s version, we’ll rename IByteStream to IByteReader and add an IByteWriter interface with the Write method for writing:

public interface IByteWriter
{
    void Write(byte value, int index);
}

Finally, we’ll add the writing methods to mirror the reading methods we already have:

public void WriteUpTo8<TByteReader, TByteWriter>(
    in TByteReader reader,
    in TByteWriter writer,
    byte value,
    int num)
    where TByteReader : IByteReader
    where TByteWriter : IByteWriter
{
    // ...
}
 
public void WriteUpTo16<TByteReader, TByteWriter>(
    in TByteReader reader,
    in TByteWriter writer,
    ushort value,
    int num)
    where TByteReader : IByteReader
    where TByteWriter : IByteWriter
{
    // ...
}
 
public void WriteUpTo32<TByteReader, TByteWriter>(
    in TByteReader reader,
    in TByteWriter writer,
    uint value,
    int num)
    where TByteReader : IByteReader
    where TByteWriter : IByteWriter
{
    // ...
}
 
public void WriteUpTo64<TByteReader, TByteWriter>(
    in TByteReader reader,
    in TByteWriter writer,
    ulong value,
    int num)
    where TByteReader : IByteReader
    where TByteWriter : IByteWriter
{
    // ...
}

Notice that writing methods require an IByteReader. This may seem strange at first, but this is necessary when writing only some of the bits of a byte. There’s no way to write less than a byte, so we must first read the byte and mix in the bits to write before writing out the whole byte.

Implementation

As with reading, WriteUpTo8 contains the trickiest bitwise work. The methods that write more bits (WriteUpTo16, WriteUpTo32, and WriteUpTo64) are all written in terms of WriteUpTo8 so they’re just as simple as their reading equivalents. Here is the full source code:

/// <summary>
/// Reader and writer of a stream of bits, which can be stored in any indexed
/// container type. This allows for accessing the bits regardless of their size
/// (up to 64 bits) even if the accesses cross one or more byte boundaries. This
/// can be used to efficiently pack bits such that individual values can be
/// stored in less than one bit. For example, a boolean can take up only one bit
/// and a 3-bit integer is possible.
/// </summary>
///
/// <author>
/// Jackson Dunstan, https://JacksonDunstan.com/articles/5429
/// </author>
///
/// <license>
/// MIT
/// </license>
public struct BitStream
{
    /// <summary>
    /// A reader of bytes. Used to abstract reading from underlying collection
    /// types such as managed arrays.
    /// </summary>
    public interface IByteReader
    {
        /// <summary>
        /// Read a byte at a given index.
        /// </summary>
        /// 
        /// <param name="index">
        /// Index of the byte to read.
        /// </param>
        /// 
        /// <returns>
        /// The byte at the given index.
        /// </returns>
        byte Read(int index);
    }
 
    /// <summary>
    /// A writer of bytes. Used to abstract writing to underlying collection
    /// types such as managed arrays.
    /// </summary>
    public interface IByteWriter
    {
        /// <summary>
        /// Write a byte at a given index.
        /// </summary>
        /// 
        /// <param name="value">
        /// Byte to write.
        /// </param>
        /// 
        /// <param name="index">
        /// Index of the byte to write.
        /// </param>
        void Write(byte value, int index);
    }
 
    /// <summary>
    /// Index of the next bit to access
    /// </summary>
    public int BitIndex;
 
    /// <summary>
    /// Read up to 8 bits starting at <see cref="BitIndex"/>.
    /// </summary>
    /// 
    /// <param name="reader">
    /// Byte reader to read from.
    /// </param>
    /// 
    /// <param name="num">
    /// Number of bits to read.
    /// </param>
    /// 
    /// <typeparam name="TByteReader">
    /// Type of byte reader to read with.
    /// </typeparam>
    /// 
    /// <returns>
    /// The read value, stored in the least-significant bits.
    /// </returns>
    public byte ReadUpTo8<TByteReader>(in TByteReader reader, int num)
        where TByteReader : IByteReader
    {
        // Calculate where we are in the stream and advance
        int bitIndex = BitIndex;
        int localByteIndex = bitIndex / 8;
        int localBitIndex = bitIndex % 8;
        BitIndex = bitIndex + num;
 
        // Read the byte with the high bits and decide if that's the only byte
        byte high = reader.Read(localByteIndex);
        int numHighBitsAvailable = 8 - localBitIndex;
        int numExcessHighBitsAvailable = numHighBitsAvailable - num;
        int highMask;
        if (numExcessHighBitsAvailable >= 0)
        {
            highMask = ((1 << num) - 1) << numExcessHighBitsAvailable;
            return (byte)((high & highMask) >> numExcessHighBitsAvailable);
        }
 
        // Read the low byte and combine with the high byte
        byte low = reader.Read(localByteIndex + 1);
        highMask = (1 << numHighBitsAvailable) - 1;
        int numLowBits = num - numHighBitsAvailable;
        int lowShift = 8 - numLowBits;
        int lowMask = ((1 << numLowBits) - 1) << lowShift;
        int highPart = (high & highMask) << numLowBits;
        int lowPart = (low & lowMask) >> lowShift;
        int result = highPart | lowPart;
        return (byte)result;
    }
 
    /// <summary>
    /// Read up to 16 bits starting at <see cref="BitIndex"/>.
    /// </summary>
    /// 
    /// <param name="reader">
    /// Byte reader to read from.
    /// </param>
    /// 
    /// <param name="num">
    /// Number of bits to read.
    /// </param>
    /// 
    /// <typeparam name="TByteReader">
    /// Type of byte reader to read with.
    /// </typeparam>
    /// 
    /// <returns>
    /// The read value, stored in the least-significant bits.
    /// </returns>
    public ushort ReadUpTo16<TByteReader>(in TByteReader reader, int num)
        where TByteReader : IByteReader
    {
        if (num <= 8)
        {
            return ReadUpTo8(reader, num);
        }
        byte high = ReadUpTo8(reader, 8);
        int numLowBits = num - 8;
        byte low = ReadUpTo8(reader, numLowBits);
        return (ushort)((high << numLowBits) | low);
    }
 
    /// <summary>
    /// Read up to 32 bits starting at <see cref="BitIndex"/>.
    /// </summary>
    /// 
    /// <param name="reader">
    /// Byte reader to read from.
    /// </param>
    /// 
    /// <param name="num">
    /// Number of bits to read.
    /// </param>
    /// 
    /// <typeparam name="TByteReader">
    /// Type of byte reader to read with.
    /// </typeparam>
    /// 
    /// <returns>
    /// The read value, stored in the least-significant bits.
    /// </returns>
    public uint ReadUpTo32<TByteReader>(in TByteReader reader, int num)
        where TByteReader : IByteReader
    {
        if (num <= 16)
        {
            return ReadUpTo16(reader, num);
        }
        uint high = ReadUpTo16(reader, 16);
        int numLowBits = num - 16;
        uint low = ReadUpTo16(reader, numLowBits);
        return (high << numLowBits) | low;
    }
 
    /// <summary>
    /// Read up to 64 bits starting at <see cref="BitIndex"/>.
    /// </summary>
    /// 
    /// <param name="reader">
    /// Byte reader to read from.
    /// </param>
    /// 
    /// <param name="num">
    /// Number of bits to read.
    /// </param>
    /// 
    /// <typeparam name="TByteReader">
    /// Type of byte reader to read with.
    /// </typeparam>
    /// 
    /// <returns>
    /// The read value, stored in the least-significant bits.
    /// </returns>
    public ulong ReadUpTo64<TByteReader>(in TByteReader reader, int num)
        where TByteReader : IByteReader
    {
        if (num <= 32)
        {
            return ReadUpTo32(reader, num);
        }
        ulong high = ReadUpTo32(reader, 32);
        int numLowBits = num - 32;
        ulong low = ReadUpTo32(reader, numLowBits);
        return (high << numLowBits) | low;
    }
 
    /// <summary>
    /// Write up to 8 bits starting at <see cref="BitIndex"/>.
    /// </summary>
    /// 
    /// <param name="reader">
    /// Byte reader to read from.
    /// </param>
    /// 
    /// <param name="writer">
    /// Byte writer to read from.
    /// </param>
    /// 
    /// <param name="value">
    /// Value to write
    /// </param>
    /// 
    /// <param name="num">
    /// Number of bits to write.
    /// </param>
    /// 
    /// <typeparam name="TByteReader">
    /// Type of byte reader to read with.
    /// </typeparam>
    /// 
    /// <typeparam name="TByteWriter">
    /// Type of byte writer to writer with.
    /// </typeparam>
    public void WriteUpTo8<TByteReader, TByteWriter>(
        in TByteReader reader,
        in TByteWriter writer,
        byte value,
        int num)
        where TByteReader : IByteReader
        where TByteWriter : IByteWriter
    {
        // Calculate where we are in the stream and advance
        int bitIndex = BitIndex;
        int localByteIndex = bitIndex / 8;
        int localBitIndex = bitIndex % 8;
        BitIndex = bitIndex + num;
 
        // When overwriting a whole byte, there's no need to read existing
        // bytes and mix in the written bits.
        if (localBitIndex == 0 && num == 8)
        {
            writer.Write(value, localByteIndex);
            return;
        }
 
        // Read the first byte and decide if that's the only byte
        byte first = reader.Read(localByteIndex);
        int numFirstBitsAvailable = 8 - localBitIndex;
        int numExcessFirstBitsAvailable = numFirstBitsAvailable - num;
        int valueMask;
        int firstMask;
        if (numExcessFirstBitsAvailable >= 0)
        {
            firstMask = (((1 << localBitIndex) - 1) << numFirstBitsAvailable)
                | (1 << numExcessFirstBitsAvailable) - 1;
            valueMask = (1 << num) - 1;
            writer.Write(
                (byte)((first & firstMask)
                    | ((value & valueMask) << numExcessFirstBitsAvailable)),
                localByteIndex);
            return;
        }
 
        // Combine the high bits of the value to write with the high bits of the
        // first byte and write them out
        int numRemain = num - numFirstBitsAvailable;
        valueMask = (1 << numFirstBitsAvailable) - 1;
        firstMask = ~valueMask;
        writer.Write(
            (byte)((first & firstMask) | ((value >> numRemain) & valueMask))),
            localByteIndex);
 
        // Read the second byte and combine its low bits with the low bits of
        // the value to write
        byte second = reader.Read(localByteIndex + 1);
        int numRemain = num - numFirstBitsAvailable;
        valueMask = (1 << numRemain) - 1;
        int numSecond = 8 - numRemain;
        int secondMask = (1 << numSecond) - 1;
        writer.Write(
            (byte)(((value & valueMask) << numSecond) | (second & secondMask)),
            localByteIndex + 1);
    }
 
    /// <summary>
    /// Write up to 16 bits starting at <see cref="BitIndex"/>.
    /// </summary>
    /// 
    /// <param name="reader">
    /// Byte reader to read from.
    /// </param>
    /// 
    /// <param name="writer">
    /// Byte writer to read from.
    /// </param>
    /// 
    /// <param name="value">
    /// Value to write
    /// </param>
    /// 
    /// <param name="num">
    /// Number of bits to write.
    /// </param>
    /// 
    /// <typeparam name="TByteReader">
    /// Type of byte reader to read with.
    /// </typeparam>
    /// 
    /// <typeparam name="TByteWriter">
    /// Type of byte writer to writer with.
    /// </typeparam>
    public void WriteUpTo16<TByteReader, TByteWriter>(
        in TByteReader reader,
        in TByteWriter writer,
        ushort value,
        int num)
        where TByteReader : IByteReader
        where TByteWriter : IByteWriter
    {
        if (num <= 8)
        {
            WriteUpTo8(reader, writer, (byte)value, num);
            return;
        }
 
        int numLow = num - 8;
        WriteUpTo8(
            reader,
            writer,
            (byte)((value & (0xff << numLow)) >> numLow),
            8);
        WriteUpTo8(
            reader,
            writer,
            (byte)(value & ((1 << numLow) - 1)),
            numLow);
    }
 
    /// <summary>
    /// Write up to 32 bits starting at <see cref="BitIndex"/>.
    /// </summary>
    /// 
    /// <param name="reader">
    /// Byte reader to read from.
    /// </param>
    /// 
    /// <param name="writer">
    /// Byte writer to read from.
    /// </param>
    /// 
    /// <param name="value">
    /// Value to write
    /// </param>
    /// 
    /// <param name="num">
    /// Number of bits to write.
    /// </param>
    /// 
    /// <typeparam name="TByteReader">
    /// Type of byte reader to read with.
    /// </typeparam>
    /// 
    /// <typeparam name="TByteWriter">
    /// Type of byte writer to writer with.
    /// </typeparam>
    public void WriteUpTo32<TByteReader, TByteWriter>(
        in TByteReader reader,
        in TByteWriter writer,
        uint value,
        int num)
        where TByteReader : IByteReader
        where TByteWriter : IByteWriter
    {
        if (num <= 16)
        {
            WriteUpTo16(reader, writer, (ushort)value, num);
            return;
        }
 
        int numLow = num - 16;
        WriteUpTo16(
            reader,
            writer,
            (ushort)((value & (0xffff << numLow)) >> numLow),
            16);
        WriteUpTo16(
            reader,
            writer,
            (ushort)(value & ((1 << numLow) - 1)),
            numLow);
    }
 
    /// <summary>
    /// Write up to 32 bits starting at <see cref="BitIndex"/>.
    /// </summary>
    /// 
    /// <param name="reader">
    /// Byte reader to read from.
    /// </param>
    /// 
    /// <param name="writer">
    /// Byte writer to read from.
    /// </param>
    /// 
    /// <param name="value">
    /// Value to write
    /// </param>
    /// 
    /// <param name="num">
    /// Number of bits to write.
    /// </param>
    /// 
    /// <typeparam name="TByteReader">
    /// Type of byte reader to read with.
    /// </typeparam>
    /// 
    /// <typeparam name="TByteWriter">
    /// Type of byte writer to writer with.
    /// </typeparam>
    public void WriteUpTo64<TByteReader, TByteWriter>(
        in TByteReader reader,
        in TByteWriter writer,
        ulong value,
        int num)
        where TByteReader : IByteReader
        where TByteWriter : IByteWriter
    {
        if (num <= 32)
        {
            WriteUpTo32(reader, writer, (uint)value, num);
            return;
        }
 
        int numLow = num - 32;
        WriteUpTo32(
            reader,
            writer,
            (uint)((value & (0xffffffff << numLow)) >> numLow),
            32);
        WriteUpTo32(
            reader,
            writer,
            (uint)(value & (ulong)((1 << numLow) - 1)),
            numLow);
    }
}

To test this, we’ll need to add on to the unit tests to exhaustively run through every combination of bit offset and number of bits to write. These write a series of ones into a bit stream of alternating ones and zeroes then use the read methods to check if the written value, bits before, and bits after are correct:

using NUnit.Framework;
using Unity.Collections;
 
/// <summary>
/// Unit tests for <see cref="BitStream"/>.
/// </summary>
///
/// <author>
/// Jackson Dunstan, https://JacksonDunstan.com/articles/5429
/// </author>
///
/// <license>
/// MIT
/// </license>
public class BitStreamTests
{
    private struct NativeArrayByteReader : BitStream.IByteReader
    {
        public NativeArray<byte> Array;
 
        public byte Read(int index)
        {
            return Array[index];
        }
    }
 
    private struct NativeArrayByteWriter : BitStream.IByteWriter
    {
        public NativeArray<byte> Array;
 
        public void Write(byte value, int index)
        {
            Array[index] = value;
        }
    }
 
    private const byte PatternByte = 0b10101010;
 
    private static NativeArray<byte> CreateArray()
    {
        NativeArray<byte> array = new NativeArray<byte>(9, Allocator.Temp);
        ResetArray(array);
        return array;
    }
 
    private static void ResetArray(NativeArray<byte> array)
    {
        for (int i = 0; i < array.Length; ++i)
        {
            array[i] = PatternByte;
        }
    }
 
    private static BitStream CreateStream(int bitIndex)
    {
        return new BitStream { BitIndex = bitIndex };
    }
 
    private static byte MakeHighPatternBits(int num)
    {
        int remain = 8 - num;
        return (byte)((PatternByte & ((1 << num) - 1) << remain) >> remain);
    }
 
    private static byte MakeLowPatternBits(int num)
    {
        return (byte)(PatternByte & ((1 << num) - 1));
    }
 
    [Test]
    public void ReadUpTo8()
    {
        using (NativeArray<byte> array = CreateArray())
        {
            NativeArrayByteReader byteReader = new NativeArrayByteReader
            {
                Array = array
            };
            for (int bitIndex = 0; bitIndex < 8; ++bitIndex)
            {
                int expected = 0;
                int next = bitIndex & 1;
                for (int numBits = 1; numBits <= 8; ++numBits)
                {
                    next = ~next & 1;
                    expected = (expected << 1) | next;
                    BitStream stream = CreateStream(bitIndex);
                    Assert.That(
                        stream.ReadUpTo8(byteReader, numBits),
                        Is.EqualTo(expected),
                        $"Bit index: {bitIndex}. Num bits: {numBits}");
                }
            }
        }
    }
 
    [Test]
    public void ReadUpTo16()
    {
        using (NativeArray<byte> array = CreateArray())
        {
            NativeArrayByteReader byteReader = new NativeArrayByteReader
            {
                Array = array
            };
            for (ushort bitIndex = 0; bitIndex < 8; ++bitIndex)
            {
                ushort expected = 0;
                ushort next = (ushort)(bitIndex & 1);
                for (int numBits = 1; numBits <= 16; ++numBits)
                {
                    next = (ushort)(~next & 1);
                    expected = (ushort)((expected << 1) | next);
                    BitStream stream = CreateStream(bitIndex);
                    Assert.That(
                        stream.ReadUpTo16(byteReader, numBits),
                        Is.EqualTo(expected),
                        $"Bit index: {bitIndex}. Num bits: {numBits}");
                }
            }
        }
    }
 
    [Test]
    public void ReadUpTo32()
    {
        using (NativeArray<byte> array = CreateArray())
        {
            NativeArrayByteReader byteReader = new NativeArrayByteReader
            {
                Array = array
            };
            for (int bitIndex = 0; bitIndex < 8; ++bitIndex)
            {
                uint expected = 0;
                uint next = (uint)bitIndex & 1;
                for (int numBits = 1; numBits <= 32; ++numBits)
                {
                    next = ~next & 1;
                    expected = (expected << 1) | next;
                    BitStream stream = CreateStream(bitIndex);
                    uint actual = stream.ReadUpTo32(byteReader, numBits);
                    Assert.That(
                        actual,
                        Is.EqualTo(expected),
                        $"Bit index: {bitIndex}. Num bits: {numBits}.");
                }
            }
        }
    }
 
    [Test]
    public void ReadUpTo64()
    {
        using (NativeArray<byte> array = CreateArray())
        {
            NativeArrayByteReader byteReader = new NativeArrayByteReader
            {
                Array = array
            };
            for (int bitIndex = 0; bitIndex < 8; ++bitIndex)
            {
                ulong expected = 0;
                ulong next = (ulong)bitIndex & 1;
                for (int numBits = 1; numBits <= 64; ++numBits)
                {
                    next = ~next & 1;
                    expected = (expected << 1) | next;
                    BitStream stream = CreateStream(bitIndex);
                    ulong actual = stream.ReadUpTo64(byteReader, numBits);
                    Assert.That(
                        actual,
                        Is.EqualTo(expected),
                        $"Bit index: {bitIndex}. Num bits: {numBits}.");
                }
            }
        }
    }
 
    [Test]
    public void WriteUpTo8()
    {
        using (NativeArray<byte> array = CreateArray())
        {
            NativeArrayByteReader byteReader = new NativeArrayByteReader
            {
                Array = array
            };
            NativeArrayByteWriter byteWriter = new NativeArrayByteWriter
            {
                Array = array
            };
            for (int bitIndex = 0; bitIndex < 8; ++bitIndex)
            {
                for (int numBits = 1; numBits <= 8; ++numBits)
                {
                    ResetArray(array);
                    BitStream stream = CreateStream(bitIndex);
                    byte value = (byte)((1 << numBits) - 1);
                    stream.WriteUpTo8(byteReader, byteWriter, value, numBits);
                    if (bitIndex > 0)
                    {
                        stream.BitIndex = 0;
                        Assert.That(
                            stream.ReadUpTo8(byteReader, bitIndex),
                            Is.EqualTo(MakeHighPatternBits(bitIndex)),
                            $"Before. Bit index: {bitIndex}. Num bits: {numBits}");
                    }
                    stream.BitIndex = bitIndex;
                    Assert.That(
                        stream.ReadUpTo8(byteReader, numBits),
                        Is.EqualTo(value),
                        $"Written. Bit index: {bitIndex}. Num bits: {numBits}");
                    int afterBitIndex = bitIndex + numBits;
                    int afterLocalBitIndex = afterBitIndex % 8;
                    if (afterLocalBitIndex != 0)
                    {
                        stream.BitIndex = afterBitIndex;
                        int numLowBits = 8 - afterLocalBitIndex;
                        Assert.That(
                            stream.ReadUpTo8(byteReader, numLowBits),
                            Is.EqualTo(MakeLowPatternBits(numLowBits)),
                            $"After. Bit index: {bitIndex}. Num bits: {numBits}");
                    }
                }
            }
        }
    }
 
    [Test]
    public void WriteUpTo16()
    {
        using (NativeArray<byte> array = CreateArray())
        {
            NativeArrayByteReader byteReader = new NativeArrayByteReader
            {
                Array = array
            };
            NativeArrayByteWriter byteWriter = new NativeArrayByteWriter
            {
                Array = array
            };
            for (int bitIndex = 0; bitIndex < 8; ++bitIndex)
            {
                for (int numBits = 1; numBits <= 16; ++numBits)
                {
                    ResetArray(array);
                    BitStream stream = CreateStream(bitIndex);
                    ushort value = (ushort)((1 << numBits) - 1);
                    stream.WriteUpTo16(byteReader, byteWriter, value, numBits);
                    if (bitIndex > 0)
                    {
                        stream.BitIndex = 0;
                        Assert.That(
                            stream.ReadUpTo8(byteReader, bitIndex),
                            Is.EqualTo(MakeHighPatternBits(bitIndex)),
                            $"Before. Bit index: {bitIndex}. Num bits: {numBits}");
                    }
                    stream.BitIndex = bitIndex;
                    Assert.That(
                        stream.ReadUpTo16(byteReader, numBits),
                        Is.EqualTo(value),
                        $"Written. Bit index: {bitIndex}. Num bits: {numBits}");
                    int afterBitIndex = bitIndex + numBits;
                    int afterLocalBitIndex = afterBitIndex % 8;
                    if (afterLocalBitIndex != 0)
                    {
                        stream.BitIndex = afterBitIndex;
                        int numLowBits = 8 - afterLocalBitIndex;
                        Assert.That(
                            stream.ReadUpTo8(byteReader, numLowBits),
                            Is.EqualTo(MakeLowPatternBits(numLowBits)),
                            $"After. Bit index: {bitIndex}. Num bits: {numBits}");
                    }
                }
            }
        }
    }
 
    [Test]
    public void WriteUpTo32()
    {
        using (NativeArray<byte> array = CreateArray())
        {
            NativeArrayByteReader byteReader = new NativeArrayByteReader
            {
                Array = array
            };
            NativeArrayByteWriter byteWriter = new NativeArrayByteWriter
            {
                Array = array
            };
            for (int bitIndex = 0; bitIndex < 8; ++bitIndex)
            {
                for (int numBits = 1; numBits <= 32; ++numBits)
                {
                    ResetArray(array);
                    BitStream stream = CreateStream(bitIndex);
                    uint value = (uint)((1 << numBits) - 1);
                    stream.WriteUpTo32(byteReader, byteWriter, value, numBits);
                    if (bitIndex > 0)
                    {
                        stream.BitIndex = 0;
                        Assert.That(
                            stream.ReadUpTo8(byteReader, bitIndex),
                            Is.EqualTo(MakeHighPatternBits(bitIndex)),
                            $"Before. Bit index: {bitIndex}. Num bits: {numBits}");
                    }
                    stream.BitIndex = bitIndex;
                    Assert.That(
                        stream.ReadUpTo32(byteReader, numBits),
                        Is.EqualTo(value),
                        $"Written. Bit index: {bitIndex}. Num bits: {numBits}");
                    int afterBitIndex = bitIndex + numBits;
                    int afterLocalBitIndex = afterBitIndex % 8;
                    if (afterLocalBitIndex != 0)
                    {
                        stream.BitIndex = afterBitIndex;
                        int numLowBits = 8 - afterLocalBitIndex;
                        Assert.That(
                            stream.ReadUpTo8(byteReader, numLowBits),
                            Is.EqualTo(MakeLowPatternBits(numLowBits)),
                            $"After. Bit index: {bitIndex}. Num bits: {numBits}");
                    }
                }
            }
        }
    }
 
    [Test]
    public void WriteUpTo64()
    {
        using (NativeArray<byte> array = CreateArray())
        {
            NativeArrayByteReader byteReader = new NativeArrayByteReader
            {
                Array = array
            };
            NativeArrayByteWriter byteWriter = new NativeArrayByteWriter
            {
                Array = array
            };
            for (int bitIndex = 0; bitIndex < 8; ++bitIndex)
            {
                for (int numBits = 1; numBits <= 64; ++numBits)
                {
                    ResetArray(array);
                    BitStream stream = CreateStream(bitIndex);
                    ulong value = (ulong)((1 << numBits) - 1);
                    stream.WriteUpTo64(byteReader, byteWriter, value, numBits);
                    if (bitIndex > 0)
                    {
                        stream.BitIndex = 0;
                        Assert.That(
                            stream.ReadUpTo8(byteReader, bitIndex),
                            Is.EqualTo(MakeHighPatternBits(bitIndex)),
                            $"Before. Bit index: {bitIndex}. Num bits: {numBits}");
                    }
                    stream.BitIndex = bitIndex;
                    Assert.That(
                        stream.ReadUpTo64(byteReader, numBits),
                        Is.EqualTo(value),
                        $"Written. Bit index: {bitIndex}. Num bits: {numBits}");
                    int afterBitIndex = bitIndex + numBits;
                    int afterLocalBitIndex = afterBitIndex % 8;
                    if (afterLocalBitIndex != 0)
                    {
                        stream.BitIndex = afterBitIndex;
                        int numLowBits = 8 - afterLocalBitIndex;
                        Assert.That(
                            stream.ReadUpTo8(byteReader, numLowBits),
                            Is.EqualTo(MakeLowPatternBits(numLowBits)),
                            $"After. Bit index: {bitIndex}. Num bits: {numBits}");
                    }
                }
            }
        }
    }
}
Usage

First, we’ll need to implement an IByteWriter to go with our (renamed) IByteReader. Here’s one for NativeArray<T>:

struct NativeArrayByteWriter : BitStream.IByteWriter
{
   public NativeArray<byte> Array;
 
   public void Write(byte value, int index)
   {
      Array[index] = value;
   }
}

Now let’s make a Burst-compiled job that uses it to write a uint to a NativeArray<byte>:

[BurstCompile]
struct BitStreamJob : IJob
{
   public NativeArray<byte> Array;
   public uint Value;
 
   public void Execute()
   {
      new BitStream().WriteUpTo32(
         new NativeArrayByteReader { Array = Array },
         new NativeArrayByteWriter { Array = Array },
         Value,
         32);
   }
}

Then we can run the job from a MonoBehaviour:

class TestScript : MonoBehaviour
{
   void Start()
   {
      using (NativeArray<byte> array = new NativeArray<byte>(4, Allocator.TempJob))
      {
         new BitStreamJob { Array = array, Value = 123 }.Run();
         print(
            new BitStream().ReadUpTo32(
                new NativeArrayByteReader { Array = array },
                32));
      }
   }
}

This prints the correct output: 123. Burst Inspector shows the job being compiled just fine, but the assembly is omitted here for brevity.

Conclusion

Today we were able to add support for writing to a bit stream in addition to just reading from it. We accomplished this without compromising our original goals, and even managed to support read-only bit streams. The resulting BitStream is an efficient and Burst-compatible way to pack multiple sub-byte values into an indexed collection type to reduce our data sizes and save disk space and bandwidth.