5
\$\begingroup\$

For some memory masking operations I need a bitwise-rotation functionality for unsigned integral types. I came across solutions based on the wiki article, but have not found a variation for a function for bitwise-rotation within an "arbitrary" field of bits. Therefore, I have extended the solution of John Regehr, and now I want some feedback from you. I would also appreciate any advice on using mechanisms provided by the C++ core language up to C++14 (without the use of the std namespace).

#include <iostream>
#include <vector>
#include <bitset>

uint64_t CircShift (uint64_t x, uint8_t n, uint8_t bitwidth)
{
  return ((x<<n)&((1<<bitwidth)-1)) | (x>>(bitwidth-n));
}

int main()
{
    uint64_t var=0b000110100110;
    var=CircShift(var,2,9);
    std::cout<<std::bitset<12>(var);

}
\$\endgroup\$
  • 1
    \$\begingroup\$ uint64_t and other such types are defined inside the std namespace, which makes me wonder why you're only looking for "core" language features? \$\endgroup\$ – papagaga Aug 16 '18 at 7:59
  • \$\begingroup\$ @papagaga because most of the std-functions are not certified for our use-case in our department, types like uint64_t are part of our certified header-list. \$\endgroup\$ – mbed_dev Aug 16 '18 at 8:04
  • \$\begingroup\$ Could you also elaborate on what n and bandwidth mean? I've run your program and got 000010011011 as a result, is it what's intended? \$\endgroup\$ – papagaga Aug 16 '18 at 8:09
  • 1
    \$\begingroup\$ @papagaga The behavior for numbers with bits set higher than the bitwidth, the function does not behave properly. You could solve this by masking the original number in the right shift. \$\endgroup\$ – maxb Aug 16 '18 at 8:31
  • 1
    \$\begingroup\$ @Mast I see, thank you very much for the info \$\endgroup\$ – mbed_dev Aug 16 '18 at 11:16
4
\$\begingroup\$

I think the function looks good. It does what it's supposed to do when the input is correct. However, if the input number x is larger or equal to 1<<bitwidth, the behavior is undefined. To rectify this, I suggest:

uint64_t CircShift(uint64_t x, uint8_t n, uint8_t bitwidth)
{
    return ((x<<n)&((1<<bitwidth)-1)) | 
           ((x&((1<<bitwidth)-1))>>(bitwidth-n));
}

Just add another mask to the right-shifted part. Also note that for shifts that are bigger than 64 bits, both your original function and my new function behave strangely. To rectify this, you can use the fact that a circular shift by bitlength steps simply give you the original number:

uint64_t CircShift(uint64_t x, uint8_t n, uint8_t bitwidth)
{
    return ((x<<(n%bitwidth))&((1<<bitwidth)-1)) 
        | ((x&((1<<bitwidth)-1))>>(bitwidth-(n%bitwidth)));
}
\$\endgroup\$
  • 1
    \$\begingroup\$ "Behaves strangely" is a quite reasonable outcome of undefined behaviour. Good job for pointing it out and how to avoid it. You still have implementation-defined behaviour for negative shifts, though (due to the annoying round-to-zero nature of / and %). \$\endgroup\$ – Toby Speight Aug 16 '18 at 8:45
  • \$\begingroup\$ I'd suggest starting with x &= (1<<bitwidth)-1); and if ((n %= bitwidth) < 0) n += bitwidth;, to keep a simple return statement. \$\endgroup\$ – Toby Speight Aug 16 '18 at 8:47
  • \$\begingroup\$ great answer. Thank you for pointing out the issue with "undefined behaviour". \$\endgroup\$ – mbed_dev Aug 16 '18 at 9:06
  • \$\begingroup\$ Great points about the negative shifts. @TobySpeight I'd refrain from using an if statement in this case simply because of the branch. However, the input is specified as an unsigned integer, shouldn't this avoid the negative cases? \$\endgroup\$ – maxb Aug 16 '18 at 10:37
  • \$\begingroup\$ Good point - I should have read the argument list more carefully. (I do like the way you've simplified the argument names - the originals were very cluttered and hard to read. Perhaps you should mention that as part of the review?). \$\endgroup\$ – Toby Speight Aug 16 '18 at 10:44
3
\$\begingroup\$

The function always gives the same results for a given input (it's a pure function of the inputs). That means that we can declare it constexpr, allowing the computation of results at compile-time, when the arguments are constants:

constexpr std::uint64_t CircShift(std::uint64_t x, std::uint8_t n,
                                  std::uint8_t bitwidth);

If your bit width isn't truly (run-time) variable, but has different values in different parts of the code, then you might want to make that a template argument:

template<std::uint8_t Bitwidth>
constexpr uint64_t CircShift(std::uint64_t x, std::uint8_t n);

Again, that can help your compiler to optimize.

While we're talking templates, you might want a version that doesn't use a std::uint64_t if n fits a smaller type (and for portability, prefer std::uint_fast64_t).

A further thought - you might want to make n a signed type, to allow both left and right rotation (right rotation is simply a left rotation of n + bitwidth, when n is less than zero).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.