Inserting into a bitstream

Question

I'm looking for a way to efficiently insert bits into a bitstream and have it 'overflow', padding with 0's.

So for example if you had a byte array with 2 bytes: 231 and 109 (11100111 01101101), and did BitInsert(byteArray,4,00) it would insert two bits at bit offset 4 making 11100001 11011011 01000000 (225,219,24). It would be ok even the method only allowed 1 bit insertions e.g. BitInsert(byteArray,4,true) or BitInsert(byteArray,4,false), but the method must be independent of bitstream length (the stream could span several hundred bytes worth).

I have one method of doing it, but it has to walk the stream with a bitmask bit by bit, so I'm wondering if there's a simpler approach...

Answers in assembly or a C derivative would be appreciated.

Edit: The particular use case is an implementation of an encoding scheme which reads a byte array 6 bits at a time, and encodes them (with 2 bit padding) into single byte. So every 6 bits, you insert 2 bits. {33,66,99} which as a bit stream is 001000010100001001100011 becomes 00001000000101000000100100100011 notice the inserts as xx: xx001000xx010100xx001001xx100011

I'm hoping for a way to do this without bit-walking... (Also if anyone knows an official name for this encoding scheme it would be helpful, as I've yet to identify it...it came up when porting an older C program into C#)

Answer 1

If you know your output will fit into something like an int32 or int64 you could probably use the bitshift operator >>.

1. Use a predefined set of masks to split your input stream into 2 parts.
2. Use the >> to move the tail end a number of bits equal to the length of your desired insertion.
3. Do the same thing to your insertion piece.
4. Use the | operator to combine all 3 pieces back together.

Answer 2

I had an hour to kill while proctoring a test, and here's the result:

class BitStream
{
    private List<byte> _bytes;

    public BitStream()
    {
        _bytes = new List<byte>();
        _bytes.Add(0);
    }

    public byte[] Data
    {
        get { return _bytes.ToArray(); }
    }

    public void Insert(int index, int value)
    {
        if (value < 0)
            value *= -1;

        int bit = value % 2;

        byte bitmask = GetBitmask(index, bit);

        // perform the right-shift operation
        int active_byte = index / 8;

        bool padded = PadIfNecessary();

        int i;
        if (padded)
            i = _bytes.Count - 2;
        else
            i = _bytes.Count - 1;

        for ( ; i > active_byte; --i)
        {
            _bytes[i] = (byte)(_bytes[i] << 1);

            // carry from earlier byte if necessary
            if ((_bytes[i - 1] & 128) == 128)
                _bytes[i] |= 1;
        }

        // now shift within the target byte
        _bytes[active_byte] = ShiftActiveByte(_bytes[active_byte], index);

        _bytes[active_byte] |= GetBitmask(index, bit);
    }

    protected byte ShiftActiveByte(byte b, int index)
    {
        index = index % 8;
        byte low_mask = 0;
        byte high_mask = 255;

        for (int i=0; i<index; ++i)
        {
            low_mask = (byte)((low_mask << 1) | 1);
            high_mask = (byte)(high_mask << 1);
        }

        byte low_part = (byte)(b & low_mask);
        byte high_part = (byte)(b & high_mask);

        high_part <<= 1;

        return (byte)(low_part | high_part);
    }

    protected byte GetBitmask(int index, int value)
    {
        return (byte)(value << (index % 8));
    }

    protected bool PadIfNecessary()
    {
        if ((_bytes[_bytes.Count - 1] & 128) == 128)
        {
            _bytes.Add(1);
            return true;
        }
        else return false;
    }
}

It won't handle inserting at an index beyond the existing bounds of the internal array, but otherwise handles itself properly in my informal smoke tests.