Reversing bits in a byte with AVR

The naive solution is to loop through the bits with the shift operator and check. But be aware that AVR doesn't have a barrel shifter so it can only shift by 1, any other shift counts need more than 1 instruction. Here's one obvious solution from the famous bithacks page

uint8_t reverse_obvious(uint8_t v)
{
    uint8_t r = v & 1; // r will be reversed bits of v; first get LSB of v
    uint8_t s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end

    for (v >>= 1; v; v >>= 1)
    {   
        r <<= 1;
        r |= v & 1;
        s--;
    }
    r <<= s; // shift when v's highest bits are zero
    return r;
}

The above snippet uses only shifts by 1 except the last r <<= s which needs a loop in AVR. You can avoid that by always running 8 loops

uint8_t reverse(uint8_t x)
{
    uint8_t mask_up = 0x01;
    uint8_t mask_down = 0x80;
    uint8_t result = 0;
    for (; mask_down; mask_down >>= 1, mask_up <<= 1)
    {
        if (x & mask_up)
            result |= mask_down;
    }
    return result;
}

Another alternative that has shift by 2, but I guess it's the best way you can do without a lookup table. AVR has plenty of available ROM for the table so it should be a lot more efficient that way

uint8_t reverse(uint8_t x)
{
    x = (((x & 0xaaU) >> 1) | ((x & 0x55U) << 1));
    x = (((x & 0xccU) >> 2) | ((x & 0x33U) << 2));
    x = (((x & 0xf0U) >> 4) | ((x & 0x0fU) << 4));
    return x;
}

Some compilers also have built-ins to reverse bits. For example Clang has __builtin_bitreverse8() and GCC has __builtin_avr_insert_bits() which can be used to reverse bits:

// reverse the bit order of bits
__builtin_avr_insert_bits (0x01234567, bits, 0)

Unfortunately their outputs are terrible

There are also lots of questions with good answers on SO about reversing bits. Try converting the C code to assembly and compare with the result on compiler explorer

• Efficient Algorithm for Bit Reversal (from MSB->LSB to LSB->MSB) in C
• In C/C++ what's the simplest way to reverse the order of bits in a byte?

AVR has swap instruction which allows to swap 4bit nibbles in a register. You can use it to make the code shorter.

mov r17, r16
ror r16  // rotate right, pushing bit 0 out to C flag
rol r17  // rotate left, moving C flag into bit 0 and pushing bit 7 out to C flag
ror r16
rol r17
ror r16
rol r17
ror r16
rol r17
ror r16
andi r16, 0xF0 // isolating bit 4 to 7
andi r17, 0x0F // isolating bit 0 to 3
or r16, r17    // combining
swap r16       // swapping the nibbles

You can do that using rol and ror opcodes (rotates left and right through carry).

ldi  r16,0b10101000   // value to reverse
push r17
rol  r16        // this push r16 msb bit in carry in left direction
ror  r17        // this push carry to r17 in right direction
rol  r16
ror  r17
rol  r16
ror  r17
rol  r16
ror  r17
rol  r16
ror  r17
rol  r16
ror  r17
rol  r16
ror  r17
rol  r16
ror  r17       // now r17 is reversed value
mov  r16,r17   // now r16 is reversed value
pop  r17

** not tested, but should work ;-) **

You can also improve this with a loop !