Reversing bits in a byte with AVR

Question

I am currently working on a problem that wants me to build a subroutine that will reverse the bits in R16.

00000011 => 11000000
or
10101000 => 00010101

For the class we are using the AVR subset and the subroutine needs to work in norfair.

This is what I have so far, any help would be appreciated!

ldi r16,3 ;00000011

Can you use a lookup table? e.g. for 4-bit halves. That's usually fastest on ISAs without a bit-reverse instruction. — Peter Cordes
Do you have any ideas of what algorithm to do? How about for starters, I suggest you right-shift R16, figure out what bit got shifted off the end of it, and then left-shift a temporary register and place that bit in the least-significant position. Can you see what to do after that to finish the program? — David Grayson

phuclv phuclv · Accepted Answer · 2020-04-14T08:30:06

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

Reversing bits in a byte with AVR

3 Answers