Insert a bit in a byte at pos n with Assembly

user_9204005 0
Viewed 155

Is there a faster way to do this with assembly than with normal C?

This is a prototype of the function in C:

uint8_t InsertBit(uint8_t input, uint16_t idx, uint8_t insbit)

The function should return the new value. I work on embedded arm cortex M. The C routine has around 18 instructions.

The C routine:

__attribute__((optimize("O1")))
uint8_t InsertBit(uint8_t input, uint16_t idx, uint8_t insbit)
{
    //Split the input into two parts, one shifted and one not
    uint8_t bottom = input;
    uint8_t top = (input << 1);
    //insert a '0' or '1' before the shifted part
    if (insbit)
        top |= (1 << idx);
    else
        top &= (~(1 << idx));
    //keep the top bits of top
    top &= (-1 << idx);
    //keep the bottom bits of bottom
    bottom &= ~(-1 << idx);
    //combine the two parts.
    return (bottom | top);
}
cortex-m arm micro-optimization assembly
2 Answers

The approach of Erik (shift the bits above the insertion point left by adding a masked version of the input) can be expressed as

uint8_t InsertBit(uint8_t input, uint16_t idx, uint8_t insbit)
{
    return ((insbit + (input >> idx)) << idx) + input;
}

which compiles to basically two instructions on ARM due to free shifts:

add     r2, r2, r0, lsr r1
add     r0, r0, r2, lsl r1
and     r0, r0, #255
bx      lr
user_3783600 
uint8_t InsertBit(uint8_t input, uint16_t idx, uint8_t insbit)
{
    return (input + (input & (-1 << idx))) | (insbit << idx);
}

NOTES:

  • x+x multiplies x by 2, same as shift it left by 1
  • we want to insert a bit, so we add just the top bits of x to the original x.
     abcdefgh    x
     abc00000    x & (-1 << 5)  // idx is 5
     --------(+)
    abc0defgh    <--- one bit inserted at position 5

  • here abc + abc results in abc0, i.e. abc shifted left by 1 bit

  • while leaving defgh alone, unshifted

  • then just or in the desired bit in the proper position.

  • fairly simple and without conditional logic

user_4711290
Related