How can I rotate to left/right all the bits in a byte array by some amount

Question

I can rotate a word to left or right by a certain amount like this:

#define ROR(x, r) ((x >> r) | (x << (64 - r)))
#define ROL(x, r) ((x << r) | (x >> (64 - r)))

[...]

ROR(var1, 11);
ROL(var1, 11);

How can I do the same but with an entire array of bytes (I mean: all the bits in array sequence)? An array like this:

uint32_t somearray[12] = {
    0xd1310ba6, 0x98dfb5ac, 0x2ffd72db, 0xd01adfb7, 0xb8e1afed, 0x6a267e96,
    0xba7c9045, 0xf12c7f99, 0x24a19947, 0xb3916cf7, 0x0801f2e2, 0x858efc16,
};

PS: There is a similar question here, but I need to know how to do it with some amount.

There is no easy way to do it. You will have to loop over the array, shift each element and carry over the shifted out portion to the next element. — Eugene Sh., Apr 11 '22 at 17:04
But depending on the usage you might not to have to perform any "physical" shifting at all, just move indices around.. — Eugene Sh., Apr 11 '22 at 17:10
Then you should follow the usual guidelines - show your attempt and explain what is wrong with it. — Eugene Sh., Apr 11 '22 at 17:12
Your `ROR` and `ROL` macros seem to expect a 64-bit operand, but if so, they invoke undefined behavior when `r` is `0`, since left- and right-shifts by 64 are undefined for a 64-bit integer type. Also, you forgot to parenthesize the macro arguments in the macro body, so if an expression is passed, you will likely fall victim to unintended associations. — Tom Karzes, Apr 11 '22 at 17:41
Your question title says 'byte array' but the code shows an array of `uint32_t`. Which are you interested in rotating? Do you want to rotate by more than 32 bits so that data doesn't just move to adjacent `uint32_t` values? — Jonathan Leffler, Apr 11 '22 at 18:04
Your array is 32 bits per element so `64` does not work too well. In your macros replace it with `(sizeof(x) * 8)`. You still have to loop through the array. — Craig Estey, Apr 11 '22 at 18:04

chqrlie · Answer 1 · 2022-04-11T23:10:19.173

There are 2 problems with the ROR and ROL macros:

the macro assumes that the argument x is a uint64_t.
shifting a uint64_t by 64 positions has undefined behavior. If the number of shifts r can be null, you should modify the expression to avoid shifting by 64.
the macro arguments should be parenthesized in the expansion to avoid precedence issues.

Here is a modified version:

// assuming x is a uint64_t and r in the range 0..63
#define ROR64(x, n) (((x) >> (n)) | ((x) << (63 - (n)) << 1))
#define ROL64(x, n) (((x) << (n)) | ((x) >> (63 - (n)) >> 1))

Note that it is recommended to use inline functions instead of macros to avoid problems with operands with side effects and enforce operand sizes:

// assuming r in the range 0..63
static inline uint64_t ror64(uint64_t x, int n) {
    return (x >> n) | (x << (63 - n) << 1);
}
static inline uint64_t rol64(uint64_t x, int n) {
    return (x << n) | (x >> (63 - n) >> 1);
}

To rotate a full array of words, it is simpler to use a different array as the source and destination and write a loop:

void ror32_array(uint32_t *dst, const uint32_t *src, size_t size, size_t n) {
    size_t dist = n / 32 % size;
    int shift = n % 32;
    for (size_t i = 0; i < size; i++) {
        dst[(i + dist) % size] = src[i] >> shift;
    }
    if (shift) {
        for (size_t i = 0; i < size; i++) {
            dst[(i + dist + 1) % size] |= src[i] << (32 - shift);
        }
    }
}

void rol32_array(uint32_t *dst, const uint32_t *src, size_t size, size_t n) {
    size_t dist = n / 32 % size;
    int shift = n % 32;
    for (size_t i = 0; i < size; i++) {
        dst[(i + size - dist) % size] = src[i] << shift;
    }
    if (shift) {
        for (size_t i = 0; i < size; i++) {
            dst[(i + size - dist - 1) % size] |= src[i] >> (32 - shift);
        }
    }
}

Here is a test program:

#include <stdarg.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>

[...]


void print(const char *fmt, ...) {
    va_list ap;
    va_start(ap, fmt);
    while (*fmt) {
        if (*fmt == '%') {
            if (fmt[1] == 'd') {
                printf("%d", va_arg(ap, int));
                fmt += 2;
                continue;
            } else
            if (fmt[1] == 'p') {
                const uint32_t *src = va_arg(ap, uint32_t *);
                size_t size = va_arg(ap, size_t);
                for (size_t i = 0; i < size; i++) {
                    printf("%08lX%c", (long)src[i], " "[i + 1 == size]);
                }
                fmt += 2;
                continue;
            }
        }
        putchar(*fmt++);
    }
    va_end(ap);
}

int main() {
    uint32_t array[] = { 0, 1, 2, 4, 8, 16 };
    size_t size = sizeof(array) / sizeof(*array);
    uint32_t dest_array[size];
    int i, n, shift[] = { 0, 1, 2, 3, 8, 15, 24, 32, 48, 64, -1 };

    print("array = { %p }\n", array, size);
    for (i = 0; (n = shift[i]) >= 0; i++) {
        ror32_array(dest_array, array, size, n);
        memcpy(array, dest_array, sizeof(array));
        print("ror(array, %d) = { %p }\n", n, array, size);
    }
    while ((n = shift[--i]) != 0) {
        rol32_array(dest_array, array, size, n);
        memcpy(array, dest_array, sizeof(array));
        print("rol(array, %d) = { %p }\n", n, array, size);
    }
    return 0;
}

Have you tested this code? I put together a test so that I'd be able to upvote, but I am not getting good results. In the "rotate right" code, is the loop after `if (shift)` meant to transfer bits from one element to the next? Should it be using `dst[(i + dist + 1) % size] |= src[i] << (32 - shift);` so that the other data is preserved? Even with that change, I'm not getting the results I'd expect. — Jonathan Leffler, Apr 11 '22 at 19:35
The loops `for (int i = 0; i < n; i++)` should be `for (int i = 0; i < size; i++)`. The value in `size` is the number of elements in the array; `n` is the bit shift. — Jonathan Leffler, Apr 11 '22 at 20:02
@JonathanLeffler: you are absolutely correct on all counts. Answer amended with bug fixes and a test program. — chqrlie, Apr 11 '22 at 23:10
I used a couple more parentheses in `size_t dist = (n / 32) % size;`, but you seem to have the fixes I'd worked out as being necessary. The `+ size` in the `rol` code is important. I changed `int shift` to `size_t shift` too, primarily for consistency rather than necessity. My main problem now is verifying the code — I need the answers to rotating the numbers. However, your code is essentially what I'm using, and I think my code is giving the correct answers. — Jonathan Leffler, Apr 11 '22 at 23:22
And now I've written some different code to generate the results, I'm pretty confident that the code really does work. And your code and my code produce the same output in my test harness. This is good to go! — Jonathan Leffler, Apr 12 '22 at 00:30

score 0 · Answer 2 · answered Apr 11 '22 at 18:20

To rotate all the bits in an array, create a function that takes a size, a pointer to the data, and a shift amount.

void rotate_right(size_t sz, void *a, unsigned shift);
#define ROR_ARRAY(a, sh) rotate_right((sizeof (a)), (a), (sh))

For an array of 32-bit values, the bit shift of the array may be be the same arithmetically as some_32_bit >> sh due to endian. More advanced use of macros with _Generic solve solve that.

How can I rotate to left/right all the bits in a byte array by some amount

2 Answers2