Understanding bit-manipulation function in Python

Question

I'd really need some help understanding this piece of code: as far as I can see it is inserting a value in an array of bytes in the middle of a byte, but, as I need to reimplement this in Javascript, I'd like to fully understand it.

Array = [0] * 256
Bit_Offset = 0

[...]

def AddBits(byte_offset, bit_offset, bits, value):
    global Bit_Offset
    global Array

    for i in range(bits):
        if(value & 0x01):
            Array[(byte_offset + ((bit_offset + Bit_Offset + i)/ 8))] |= (0x01 << ((bit_offset + Bit_Offset + i) % 8));
        value /=2
    Bit_Offset += bits

And it's used like this:

AddBits(3, 0, 8, 0xaa)
AddBits(3, 0, 3, 0xbb)

EDIT: Ok, it does insert values at custom offsets in a byte, but it looks like a very poor algorithm to me (a cycle on every bit to insert, really?). There has to be a better way to do it!

I'm not so good at binary math, but I came up with the idea of shifting the value of something like 8 - bit_offset (so that the first bit it's at the correct offset in a byte), then splitting it in parts if it spans multiple bytes and finally ORing it with the byte in the array. Is this correct? How can I implement the splitting part?

Answer 1

I will just go over the bit type operators.

if(value & 0x01):

This checks to see if the least significant bit is a 1 or 0. If it is a zero we don't do anything.

Array[(byte_offset + ((bit_offset + Bit_Offset + i)/ 8))]

Since all values in the array are a single byte, byte_offset is the index of where we are going to OR the bit. Added to byte_offset is an additional offset of bits from the local bit counter and the global bit counter that are then converted to bytes with the division by 8. Finally we get the index of the byte where we are going to put this bit.

((bit_offset + Bit_Offset + i) % 8)

This is calculating the bit position we are going to OR.

|= (0x01 << 

This takes our bit position and shifts a 1 to that position then ORs it with whatever is already there. We know we can use a 1 here, because the if statement will filter any 0's.

value /=2

This effectively does a bit shift to the right putting the next bit into the LSB. (Could be replaced with value >>=1 )

Bit_Offset += bits

At the end we add the bits that we added to the global offset.

What it does

This function takes Array (an array of bytes) and bit wise ORs in a value at the bit position defined by the global bit offset, argument bit offset, and the argument byte offset. The reason it does it one bit at a time is because you can potentially need to set more than one index of Array (try AddBits(3, 4, 8, 0xaa) and see what I mean).

One improvement would be to change the for loop to:

for i in range(bits):
    Array[(byte_offset + ((bit_offset + Bit_Offset + i)/ 8))] |= ((value & 1) << ((bit_offset + Bit_Offset + i) % 8));
    value >>=1

Edit: You could also do one byte at a time like this

def AddBits2(byte_offset, bit_offset, bits, value):
    global Bit_Offset
    global Array

    # precompute offsets
    bit_offset += Bit_Offset
    byte_offset += bit_offset / 8
    Bit_Offset += bits

    # Mask out any extra bits in value and adjust value to align to byte
    value = (((1 << bits) - 1) & value) << (bit_offset % 8)

    # go through bytes and OR them in one byte at a time
    for i in range((bits + 7) / 8) :
        Array[byte_offset + i] |= (value & 0xff) 
        value >>=8