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?

What's the "endianness of an integer"? What's the endianness of 15? — Kerrek SB, Apr 29 '16 at 11:10
@KerrekSB Whatever it is. I didn't ask that question. My question is how to swap big-endian to little-endian and vice versa. — user1095108, Apr 29 '16 at 11:20
@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? — Benjamin Lindley, Apr 29 '16 at 11:22
@BenjaminLindley: Of course. I just find the question vastly underspecified. — Kerrek SB, Apr 29 '16 at 13:16
@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. — M.M, May 11 '16 at 05:31
@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? — Benjamin Lindley, May 11 '16 at 05:43
@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 — M.M, May 11 '16 at 06:15
@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. — Benjamin Lindley, May 11 '16 at 06:22

ecatmur · Accepted Answer · 2016-04-29T14:02:51.347

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.

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). — Qix - MONICA WAS MISTREATED, May 16 '20 at 23:13
Wasn't me, but thanks for pointing it out - it's nice to have an example that isn't just sum. — ecatmur, May 17 '20 at 20:42
Came here because of the cppreference fold docs, and definitely appreciated it too! — Steve Lorimer, Dec 18 '20 at 16:01

Wolfgang Brehm · Answer 2 · 2022-02-06T12:21:24.143

4

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.

edited Feb 06 '22 at 12:21

answered Apr 17 '17 at 21:53

Wolfgang Brehm

1,491
18
21

1

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. – Arne Vogel Feb 05 '18 at 14:44
@ArneVogel this is true, I just assumed that the bitmasks will be compile time constants as the function that generates them is a constexpr. – Wolfgang Brehm Feb 23 '18 at 12:48
1

This code does not compile (since `digits` is not defined). Upon replacing `digits` by `std::numeric_limits::digits` from `limits.h`, the code compiles starting at C++14 and DOES NOT swap the bytes. https://godbolt.org/z/YfhETebM3 – Adomas Baliuka Feb 06 '22 at 02:04
1

@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: https://gcc.godbolt.org/z/5Mozedzvo – Wolfgang Brehm Feb 06 '22 at 12:27

score 1 · Answer 3 · answered May 13 '22 at 11:52

1

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

answered May 13 '22 at 11:52

Holger Strauss

225
2
10

Not the first nor last instance of the c++ standard taking inspiration from SO. – user1095108 May 14 '22 at 05:52

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

3 Answers3

Linked