How to write constexpr swap function to change endianess of an integer?

Question

How to write a constexpr function to swap endianess of an integer, without relying on compiler extensions and can you give an example on how to do it?

Mannes

What's the "endianness of an integer"? What's the endianness of 15? – Tassel

@KerrekSB Whatever it is. I didn't ask that question. My question is how to swap big-endian to little-endian and vice versa. – Mannes

@KerrekSB: In the context of C++(and most programming in general), when one says integer, they are usually referring to an integer object. That is, a region in memory used to store integer data, usually one of the fundamental integer types (char, short, int, long and long long, along with their unsigned variants). Have you really never come across that usage? – Amery

@BenjaminLindley: Of course. I just find the question vastly underspecified. – Tassel

@BenjaminLindley values don't have endianness. Endianness refers to representations of values. Integer operations in C++ are specified in terms of values, not representations. It's possible (and in fact, a good idea, and easy) to write code that does not rely on any particular representation. Then your code doesn't break when you run it on a different system. – Raynaraynah

@M.M: C++ allows you to manipulate integers both by their arithmetic value, and by their byte level representation. And by changing one, you change the other. It's really not that hard to understand what the OP is asking is it? – Amery

@BenjaminLindley we can guess, but the question is badly worded, since integers don't have endianness. (which is what Kerrek SB was trying to point out). This is worth mentioning because (judging by questions on here) many people don't grok the distinction between values and representations and write brittle or wrong code as a result – Raynaraynah

@M.M. Well, I disagree, and think the wording is fine. I understand Kerrek's point, but simply think it was needlessly pedantic and dumb. I can't, off the top of my head, think of a better wording for the question, and wouldn't waste my time trying to come up with one, because everybody who knows what endianness is understands it, even Kerrek. – Amery

Answer 1

Yes, it's pretty easy; here's a recursive (C++11-compatible) implementation (unsigned integral types only):

#include <climits>
#include <cstdint>
#include <type_traits>

template<class T>
constexpr typename std::enable_if<std::is_unsigned<T>::value, T>::type
bswap(T i, T j = 0u, std::size_t n = 0u) {
  return n == sizeof(T) ? j :
    bswap<T>(i >> CHAR_BIT, (j << CHAR_BIT) | (i & (T)(unsigned char)(-1)), n + 1);
}

Example.

Here I'm using j as the accumulator and n as the loop counter (indexing bytes).

If you have a compiler supporting C++17 fold expressions, it's possible to write something that expands out into exactly what you'd write by hand:

template<class T, std::size_t... N>
constexpr T bswap_impl(T i, std::index_sequence<N...>) {
  return ((((i >> (N * CHAR_BIT)) & (T)(unsigned char)(-1)) <<
           ((sizeof(T) - 1 - N) * CHAR_BIT)) | ...);
}; //                                        ^~~~~ fold expression
template<class T, class U = typename std::make_unsigned<T>::type>
constexpr U bswap(T i) {
  return bswap_impl<U>(i, std::make_index_sequence<sizeof(T)>{});
}

The advantage of this form is that because it doesn't use loops or recursion, you're pretty much guaranteed to get optimal assembly output - on x86-64, clang even manages to work out to use the bswap instruction.

Ethelred

You might be interested to know this answer is linked to by cppreference's fold expression docs (not sure if you put them there yourself or if someone else did). – Perversity

Wasn't me, but thanks for pointing it out - it's nice to have an example that isn't just sum. – Ethelred

Yeah I definitely appreciated it :) – Perversity

Came here because of the cppreference fold docs, and definitely appreciated it too! – Tivoli

Answer 2

Inspired by ecatmur I suggest the following solution, that has potentially better performance when bswap is not detected by the compiler (O(log(n)) vs O(N)). Given that N is usually <=8 this is probably irrelevant, still:

using std::numeric_limits;

template <typename T>
typename std::enable_if<std::is_unsigned<T>::value,T>::type
constexpr alternating_bitmask(const size_t step){
  T mask(0);
  for (size_t i=0;i<numeric_limits<T>::digits;i+=2*step){
    mask|=(~T(0)>>(numeric_limits<T>::digits-step))<<i;
  }
  return mask;
}

template <typename T>
typename std::enable_if<std::is_unsigned<T>::value,T>::type
constexpr bswap(T n){
  for (size_t i=numeric_limits<unsigned char>::digits;
              i<numeric_limits<T>::digits;
              i*=2) {
    n = ((n&(~(alternating_bitmask<T>(i))))>>i)|
        ((n&( (alternating_bitmask<T>(i))))<<i);
  }
  return n;
}

As this form is more complex than ecatmur's solution the compiler has a harder job optimizing, but clang still finds out that we mean bswap.

Gromyko

This solution actually has a time complexity of Θ(N) as well because the inner loop (not counting optimizations) has an amortized complexity of Θ(N / log N) (per iteration of the outer loop). To get actual Θ(log N), the bitmasks would need to be memoized, e.g. precomputed into an array. – Rodmann

@ArneVogel this is true, I just assumed that the bitmasks will be compile time constants as the function that generates them is a constexpr. – Gromyko

This code does not compile (since digits<T> is not defined). Upon replacing digits<T> by std::numeric_limits<T>::digits from limits.h, the code compiles starting at C++14 and DOES NOT swap the bytes. godbolt.org/z/YfhETebM3 – Deplore

@AdomasBaliuka I fixed the compilation error and tested it. It works, but be careful to use unsigned char , char alone is 7 bit. clang++ even recognizes this as bswap, have a look at the assembler: gcc.godbolt.org/z/5Mozedzvo – Gromyko

Answer 3

Finally, C++23 allows to do this easily with the new function std::byteswap from the Standard Library: https://en.cppreference.com/w/cpp/numeric/byteswap

Socialist

Not the first nor last instance of the c++ standard taking inspiration from SO. – Mannes