Insertion into a bit stream

Question

I am looking for a way to effectively insert bits into a bitstream and overflow it by filling in 0.

So, for example, if you had an array of bytes with 2 bytes: 231 and 109 (11100111 01101101), and BitInsert (byteArray, 4.00), it would insert two bits into bit 4 offsets, making 11100001 11011011 01000000 (225 219, 24). It would be nice, even the method allowed only 1-bit inserts, for example. BitInsert (byteArray, 4, true) or BitInsert (byteArray, 4, false), but the method must be independent of the length of the bit stream (the stream may take several hundred bytes).

I have one way to do this, but it should go downstream with a bitmask by bits, so I wonder if there is a simpler approach ...

Assembly responses or derivatives of C will be appreciated.

Edit: A specific use case is to implement a coding scheme that reads a byte array 6 bits at a time and encodes them (with 2-bit padding) into one byte. Therefore, every 6 bits you insert 2 bits. {33.66.99}, which as bitstream 001000010100001001100011 becomes 00001000000101000000100100100100011 notices the insert as xx: xx001000xx010100xx001001xx100011

I am hoping for a way to do this without a bit walk ... (Also, if someone knows the official name of this encoding scheme, it would be useful since I have not identified it yet ... it appeared when porting an old program from C to C #)

Answer 1

I had an hour to kill by guilty of a test, and here is 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 will not process an insert with an index beyond the existing boundaries of the internal array, but otherwise it will correctly handle my unofficial smoke tests.

Answer 2

If you know that your output will fit into something like int32 or int64, you can probably use the bithift → operator.

• Use a predefined set of masks to split the input stream into 2 parts.
• Use → to move the end of the tail by the number of bits equal to the length of the desired insert.
• Do the same with your insert part.
• Use | operator combine all 3 parts back.

Answer 3

The effective choice will depend on where your bottleneck is. Since you are specifically asking about inserts, I assume that your application needs to do a lot of random access inserts, and in fact you only need to read the full stream from time to time in order. If this is the case, here are a few options:

Option 1: Linked Byte List

 struct BitStreamNode; { Byte size; Byte bits; BitStreamNode * next; }; 

This will work best in cases where you can maintain a pointer to the node into which you want to insert the bit. If you need to specify the insertion point as a numeric index, see Option 2. Note that I have included the size element. This will allow you to insert two bits as follows:

 BitStreamNode newNode; newNode.bits = 0x02; // for example newNode.size = 2; newNode.next = nodeToInsertAfter.next; nodeToInsertAfter.next = newNode; 

Inserting in the middle of an existing node, of course, will require splitting the node into two parts. Again, let me emphasize that this will only be more efficient than shuffling the entire array to the right if you a) do it quite often and b) get a large number of bits in your stream.

Option 2: Balanced Tree Structure

This method will use a similar node, as indicated in option 1, but will include a numerical index in each node and a link to nodes with a higher and lower index. The main idea is a binary search tree tree , which reduces the time required to find the exact location of a particular node in the stream, but with the addition of links in order to the next and previous nodes (in order to be able to read the stream in order).

Update: The exact definition looks like a threaded tree . "

This will require a lot of work on the correct implementation, so I would recommend to go only along this route, if you are absolutely sure that the increase in speed will be worth it. that is, the profile of the main brute force decision, and then evaluate the pros and cons to make additional efforts and complexity.