How can I elegantly take advantage of ARM instructions like REV and RBIT when writing C code?

Question

I am writing C code which may be compiled for the Arm Cortex-M3 microcontroller.

This microcontroller supports several useful instructions for efficiently manipulating bits in registers, including REV*, RBIT, SXT*.

When writing C code, how can I take advantage of these instructions if I need those specific functions? For example, how can I complete this code?

#define REVERSE_BIT_ORDER(x)    {  /* what to write here? */ }

I would like to do this without using inline assembler so that this code is both portable, and readable.

Added:

In part, I am asking how to express such a function in C elegantly. For example, it's easy to express bit shifting in C, because it's built into the language. Likewise, setting or clearing bits. But bit reversal is unknown in C, and so is very hard to express. For example, this is how I would reverse bits:

unsigned int ReverseBits(unsigned int x)
{
    unsigned int ret = 0;
    for (int i=0; i<32; i++)
    {
        ret <<= 1;
        if (x & (1<<i))
            ret |= 1;
    }
    return ret;
}

Would the compiler recognise this as bit reversal, and issue the correct instruction?

Answer 1

Reversing bits in a 32 bit integer is such an exotic instruction so that might be why you can't reproduce it. I was able to generate code that utilizes REV (reverse byte order) however, which is a far more common use-case:

#include <stdint.h>

uint32_t endianize (uint32_t input)
{
  return ((input >> 24) & 0x000000FF) |
         ((input >>  8) & 0x0000FF00) |
         ((input <<  8) & 0x00FF0000) |
         ((input << 24) & 0xFF000000) ;
}

With gcc -O3 -mcpu=cortex-m3 -ffreestanding (for ARM32, vers 11.2.1 "none"):

endianize:
        rev     r0, r0
        bx      lr

https://godbolt.org/z/odGqzjTGz

It works for clang armv7-a 15.0.0 too, long as you use -mcpu=cortex-m3.

So this would support the idea of avoiding manual optimizations and let the compiler worry about such.

Answer 2

It would be best if you used CMSIS intrinsic.

__REV, __REV16 etc. Those CMSIS header files contain much much more.

You can get them from here:

https://github.com/ARM-software/CMSIS_5

and you are looking for cmsis_gcc.h file (or similar if you use another compiler).

Answer 3

@Lundin's answer shows a pure-C shift/mask bithack that clang recognizes and compiles to a single rev instruction. (Or presumably to x86 bswap if targeting x86, or equivalent instructions on other ISAs that have them.)

In portable ISO C, hoping for pattern-recognition is unfortunately the best you can do, because they haven't added portable ways to expose CPU functionality; even C++ took until C++20 to add the <bit> header for things like std::popcount and C++23 std::byteswap.

(Some fairly-portable C libraries / headers have byte-reversal, e.g. as part of networking there's ntohl net-to-host which is an endian-swap on little-endian machines. Or there's GCC's (or glibc's?) endian.h, with htobe32 being host to big-endian 32-bit. Man page. These are usually implemented with intrinsics that compile to a single instruction in good-quality implementations.

Of course, if you definitely want a byte swap regardless of host endianness, you could do htole32(be32toh(x)) because one of them's a no-op and the other's a byte-swap, since ARM is either big or little endian. (It's still a byte-swap even if neither of them are NOPs, even on PDP or other mixed-endian machines, but there might be more efficient ways to do it.)

There are also some "collections of useful functions" headers with intrinsics for different compilers, with functions like byte swap. These can be of varying quality in terms of efficiency and maybe even correctness.

---

You can see that no, neither GCC nor clang optimize your code to rbit for ARM or AArch64. https://godbolt.org/z/Y7noP61dE . Presumably looping over bits in the other direction isn't any better. Perhaps a bithack as in In C/C++ what's the simplest way to reverse the order of bits in a byte? or Efficient Algorithm for Bit Reversal (from MSB->LSB to LSB->MSB) in C .

CC and clang recognize the standard bithack for popcount, but I didn't check any of the answers on the bit-reverse questions.

---

Some languages, notably Rust, do care more about making it possible to portably express what modern CPUs can do. foo.reverse_bits() (since Rust 1.37) and foo.swap_bytes() just work for any type on any ISA. For u32 specifically, https://doc.rust-lang.org/std/primitive.u32.html#method.reverse_bits (That's Rust's equivalent of C uint32_t.)

---

Most mainstream C implementations have portable (across ISAs) builtins or (target-specific) intrinsics (like __REV() or __REV16() for stuff like this.

The GNU dialect of C (GCC/clang/ICC and some others) includes __builtin_bswap32(input). See Does ARM GCC have a builtin function for the assembly 'REV' instruction?. It's named after the x86 bswap instruction, but it's just a byte-reverse that GCC / clang compile to whatever instructions can do it efficiently on the target ISA.

There's also a __builtin_bswap16(uint16_t) for swapping the bytes of a 16-bit integer, like revsh except the C semantics don't include preserving the upper 16 bits of a 32-bit integer. (Because normally you don't care about that part.) See the GCC manual for the available GNU C builtins that aren't target-specific.

There isn't a GNU C builtin or intrinsic for bitwise reverse that I could find in the manual or GCC arm-none-eabi 12.2 headers.

---

ARM documents an __rbit() intrinsic for their own compiler, but I think that's Keil's ARMCC, so there might not be any equivalent of that for GCC/clang.

@0___________ suggests https://github.com/ARM-software/CMSIS_5 for headers that define a function for that.

---

If worst comes to worst, GNU C inline asm is possible for GCC/clang, given appropriate #ifdefs. You might also want if (__builtin_constant_p(x)) to use a pure-C bit-reversal so constant-propagation can happen on compile-time constants, only using inline asm on runtime-variable values.

   uint32_t output, input=...;
#if defined(__arm__) || defined (__aarch64__)
   // same instruction is valid for both
   asm("rbit %0,%1" : "=r"(output) : "r"(input));
#else 
 ...  // pure C fallback or something
#endif

Note that it doesn't need to be volatile because rbit is a pure function of the input operand. It's a good thing if GCC/clang are able to hoist this out of a loop. And it's a single asm instruction so we don't need an early-clobber.

This has the downside that the compiler can't fold a shift into it, e.g. if you wanted a byte-reverse, __rbit(x) >> 24 equals __rbit(x<<24), which could be done with rbit r0, r1, lsl #24. (I think).

With inline asm I don't think there's a way to tell the compiler that a r1, lsl #24 is a valid expansion for the %1 input operand. Hmm, unless there's a machine-specific constraint for that? https://gcc.gnu.org/onlinedocs/gcc/Machine-Constraints.html - no, no mention of "shifted" or "flexible" source operand in the ARM section.

Efficient Algorithm for Bit Reversal (from MSB->LSB to LSB->MSB) in C shows an #ifdefed version with a working fallback that uses a bithack to reverse bits within a byte, then __builtin_bswap32 or MSVC _byteswap_ulong to reverse bytes.

Answer 4

Interestingly, ARM gcc seems to have improved its detection of byte order reversing recently. With version 11, it would detect byte reversal if done by bit shifting, or by byte swapping through a pointer. However, from version 10 and backwards, the pointer method failed to issue the REV instruction.

    uint32_t endianize1 (uint32_t input)
    {
      return ((input >> 24) & 0x000000FF) |
             ((input >>  8) & 0x0000FF00) |
             ((input <<  8) & 0x00FF0000) |
             ((input << 24) & 0xFF000000) ;
    }

    uint32_t endianize2 (uint32_t input)
    {
        uint32_t output;
        uint8_t *in8  = (uint8_t*)&input;
        uint8_t *out8 = (uint8_t*)&output;

        out8[0] = in8[3];
        out8[1] = in8[2];
        out8[2] = in8[1];
        out8[3] = in8[0];
        return output;
    }

endianize1:
    rev     r0, r0
    bx      lr
endianize2:
    mov     r3, r0
    movs    r0, #0
    lsrs    r2, r3, #24
    bfi     r0, r2, #0, #8
    ubfx    r2, r3, #16, #8
    bfi     r0, r2, #8, #8
    ubfx    r2, r3, #8, #8
    bfi     r0, r2, #16, #8
    bfi     r0, r3, #24, #8
    bx      lr

https://godbolt.org/z/E3xGvG9qq

So, as we wait for optimisers to improve, there are certainly ways you can help the compiler understand your intent and take good advantage of the instruction set (without resorting to micro optimisations or inline assembler). But it's likely that this will involve a good understanding of the architecture by the programmer, and examination of the output assembler.

Take advantage of http://godbolt.org to help examine the compiler output, and see what produces the best output.