Rotate a bitmap represented by an array of bytes

Question

In an AVR, I'm using an array of eight bytes to store a picture displayed on an 8x8 LED matrix. The picture needs to be rotated from time to time. So, given the picture ┘ defined as:

uint8_t rows[8] = {
    0b00000001,
    0b00000001,
    0b00000001,
    0b00000001,
    0b00000001,
    0b00000001,
    0b00000001,
    0b11111111
};

I want to "rotate" this anticlockwise to get ┐ as:

uint8_t rows2[8] = {
    0b11111111,
    0b00000001,
    0b00000001,
    0b00000001,
    0b00000001,
    0b00000001,
    0b00000001,
    0b00000001
};

Or this if done clockwise, └:

uint8_t rows3[8] = {
    0b10000000,
    0b10000000,
    0b10000000,
    0b10000000,
    0b10000000,
    0b10000000,
    0b10000000,
    0b11111111
};

How do I do this in straight C?

rows3[(i+j+8)%8] where i is the element you want to access and j is the amount of shift — user3528438, Feb 22 '16 at 00:57
What is the change with the clockwise rotation? Are you saying no change? — dawg, Feb 22 '16 at 00:57
`rows[]` and `rows3[]` look suspiciously the same, except for the use of `0b` prefix in one and `0x` prefix in the other. Is that what you intended? — njuffa, Feb 22 '16 at 00:58
To make it clearer what I'm trying to accomplish, my AVR is using an array of eight bytes to store what is displayed on an 8x8 LED matrix. The picture being displayed needs to be rotated from time to time. — Frotz, Feb 22 '16 at 00:58
Unclear what you want, but I think you want [memmove](http://pubs.opengroup.org/onlinepubs/009695399/functions/memmove.html) — dawg, Feb 22 '16 at 00:59
Now it is even more unclear what you are looking for. The rotate anti clockwise seems to be bytes in the array and the clockwise seems to be bits in the bytes. What are you looking for specifically? — dawg, Feb 22 '16 at 01:09
I added graphic characters to your post so it makes sense what you're after. However, I cannot add a where-did-you-get-stuck; you will have to do so yourself. — Jongware, Feb 22 '16 at 01:21
One solution might be just to store 4 arrays, one for each frame — M.M, Feb 22 '16 at 02:53
Possible duplicate of [What is the fastest way to rotate the bits in an 8x8 block on bits?](https://stackoverflow.com/questions/6930667/what-is-the-fastest-way-to-rotate-the-bits-in-an-8x8-block-on-bits) — phuclv, Aug 01 '18 at 06:00

score 3 · Accepted Answer · edited May 23 '17 at 12:23

Some bitwise operations can do the trick.

#include <inttypes.h>

int main(){

  uint8_t rows[8] = {
      0b11111111,
      0b00000001,
      0b00000001,
      0b00111111,
      0b00000001,
      0b00000001,
      0b00000001,
      0b11111111
  };


  uint8_t rows2[8] = {0, 0, 0, 0, 0, 0, 0, 0};
  uint8_t rows3[8] = {0, 0, 0, 0, 0, 0, 0, 0};

  int i, j;
  // rotate clockwise
  for(i=0; i<8; ++i){
    for(j=0; j<8; ++j){
      rows3[i] = (  ( (rows[j] & (1 << (7-i) ) ) >> (7-i) ) << j ) | rows3[i];
    }
  }

  // rotate anti-clockwise
  for(i=0; i<8; ++i){
    for(j=0; j<8; ++j){
      rows2[i] = (  ( (rows[j] & (1 << i ) ) >> i ) << (7-j) ) | rows2[i];
    }
  }
}

In the clockwise case, you get each (7-i)-th bit of the j-th original byte with (rows[j] & (1 << (7-i) ) ) >> (7-i) and then shift it to the j-th position. You collect all the bits by doing an "or" (|) with the byte itself, so it is very important to initialize the array with 0s. The anti-clockwise case is analogous, changing the indexing. I used another letter to test it, that let you know for sure if the rotation is working properly. If you need further explanation, please just ask.

If you want to look the result, I'm using the function in this SO question: Is there a printf converter to print in binary format?

I was tearing my hair out in the wee hours over your previous code that resulted in scribbles on the LED matrix. Thanks for fixing that. I found that printf converter independently when I compiled the code on my Linux machine so I could better watch its execution. — Frotz, Feb 25 '16 at 05:13
Sorry for that. The thing is the previous code was functioning correctly for the "L" test case, but then I realized that for complete testing a more complicated shape was needed. Using "E" shape helped me to debug the first version of the code to reach to this. — eguaio, Feb 25 '16 at 12:19

score 1 · Answer 2 · answered Feb 22 '16 at 02:06

uint8_t rows[8] = {
    0b00000001,
    0b00000001,
    0b00000001,
    0b00000001,
    0b00000001,
    0b00000001,
    0b00000001,
    0b11111111
};

uint8_t temp[8];

void anti()
{
    int i, j;

    for(i = 0; i < 8; ++i) temp[i] = 0;

    for(i = 0; i < 8; ++i)
        for(j = 0; j < 8; ++j)
             if(rows[j] & 1<<i) temp[i] |= 1<<(7-j); 

    for(i = 0; i < 8; ++i) row[i] = temp[i];
}

score 1 · Answer 3 · answered Feb 22 '16 at 06:18

This is a simple/standard [square] matrix rotation. I worked this out by hand using graph paper and physically rotating it.

For counterclockwise (rotate left), the equation is:

out[7-x][y] = inp[y][x];

For clockwise (rotate right), the equation is:

out[x][7-y] = inp[y][x];

... except that we have to extract bits in the X dimension, so we need some functions that simulate the matrix access for bits.

Here's a test program with the necessary functions:

#include <stdio.h>

typedef unsigned char byte;

typedef void (*rot_p)(byte *dst,const byte *src);

#define MSK(_shf)       (1 << (7 - (_shf)))

byte result[8];

// original matrix
byte rows[8] = {
    0b00000001,
    0b00000001,
    0b00000001,
    0b00000001,
    0b00000001,
    0b00000001,
    0b00000001,
    0b11111111
};

// counterclockwise (rotate left)
byte rows2[8] = {
    0b11111111,
    0b00000001,
    0b00000001,
    0b00000001,
    0b00000001,
    0b00000001,
    0b00000001,
    0b00000001
};

// clockwise (rotate right)
byte rows3[8] = {
    0b10000000,
    0b10000000,
    0b10000000,
    0b10000000,
    0b10000000,
    0b10000000,
    0b10000000,
    0b11111111
};

// bitget -- get bit from matrix
byte
bitget(const byte *rows,int y,int x)
{
    byte val;

    rows += y;
    val = *rows;
    val &= MSK(x);

    return val;
}

// bitget -- set bit in matrix
void
bitset(byte *rows,int y,int x,byte val)
{
    byte msk;

    rows += y;

    msk = MSK(x);

    if (val)
        *rows |= msk;
    else
        *rows &= ~msk;
}

// rotright -- rotate matrix right (clockwise)
void
rotright(byte *dst,const byte *src)
{
    int x;
    int y;
    byte val;

    for (y = 0;  y < 8;  ++y) {
        for (x = 0;  x < 8;  ++x) {
            val = bitget(src,y,x);
            bitset(dst,x,7 - y,val);
        }
    }
}

// rotleft -- rotate matrix left (counterclockwise)
void
rotleft(byte *dst,const byte *src)
{
    int x;
    int y;
    byte val;

    for (y = 0;  y < 8;  ++y) {
        for (x = 0;  x < 8;  ++x) {
            val = bitget(src,y,x);
            bitset(dst,7 - x,y,val);
        }
    }
}

// mtxshow -- print matrix
void
mtxshow(const byte *mtx,const char *sym,const char *tag)
{
    int y;
    int x;
    byte val;

    printf("%s/%s:\n",sym,tag);
    for (y = 0;  y < 8;  ++y) {
        printf("  ");
        for (x = 0;  x < 8;  ++x) {
            val = bitget(mtx,y,x);
            val = val ? '1' : '0';
            fputc(val,stdout);
        }
        fputc('\n',stdout);
    }
}

// test -- perform test
void
test(const byte *exp,rot_p fnc,const char *tag)
{

    printf("\n");

    mtxshow(exp,tag,"expected");
    fnc(result,rows);
    mtxshow(result,tag,"actual");
}

int
main(void)
{

    mtxshow(rows,"rows","orig");

    test(rows2,rotleft,"rotleft");
    test(rows3,rotright,"rotright");

    return 0;
}

Here's the program output:

rows/orig:
  00000001
  00000001
  00000001
  00000001
  00000001
  00000001
  00000001
  11111111

rotleft/expected:
  11111111
  00000001
  00000001
  00000001
  00000001
  00000001
  00000001
  00000001
rotleft/actual:
  11111111
  00000001
  00000001
  00000001
  00000001
  00000001
  00000001
  00000001

rotright/expected:
  10000000
  10000000
  10000000
  10000000
  10000000
  10000000
  10000000
  11111111
rotright/actual:
  10000000
  10000000
  10000000
  10000000
  10000000
  10000000
  10000000
  11111111

David C. Rankin · Answer 4 · 2016-02-22T12:03:22.943

You can do it with array indexes, but it is far easier to use the tools string.h provides (e.g. memcpy and memmove) to accomplish the rotations. For example if your array is r with sz number of elements that you want to rotate by n positions, your clockwise rotation is simply:

uint8_t i = 0, tmp[n];
...
memcpy  (tmp, &r[sz-n], n);
memmove (&r[n], r, sz-n);
memcpy  (r, tmp, n);
for (; i < sz; i++)
    if (i != n-1 && r[i] != 0x80)
        r[i] ^= 0x81;

Your counter-clockwise rotation is:

memcpy  (tmp, r, n);
memmove (r, &r[n], sz-n);
memcpy  (&r[sz-n], tmp, n);
for (; i < sz; i++)
    if (i != sz-n+1 && r[i] != 0xff)
        r[i] ^= 0x81;

There is nothing to do if (n == 0 || n == sz) and you have to choose what to do if (n > sz) (e.g. throw error, or rotate n % sz positions). It appears you are only concerned with a rotation of 1 in either direction. Putting all the pieces together, a short example would be:

Updated Rotations

#include <stdio.h>
#include <string.h>
#include <inttypes.h>

void rotcw (uint8_t *r, uint8_t sz, uint8_t n);
void rotccw (uint8_t *r, uint8_t sz, uint8_t n);
void prnrows (uint8_t *r, uint8_t sz);

int main (void) {

    uint8_t rows[] = {0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0xff};
    uint8_t sz = sizeof rows / sizeof *rows;

    printf ("\n original array  :");
    prnrows (rows, sz);

    rotcw (rows, sz, 1);
    printf ("\n rotate cw by 1  :");
    prnrows (rows, sz);

    rotccw (rows, sz, 1);
    printf ("\n rotate ccw by 1 :");
    prnrows (rows, sz);

    return 0;
}

void rotcw (uint8_t *r, uint8_t sz, uint8_t n)
{
    if (n == sz ) return;  /* nothing to do */
    if (n > sz)   n %= sz; /* rotate 'n % sz' positions */

    uint8_t i = 0, tmp[n];

    memcpy  (tmp, &r[sz-n], n);
    memmove (&r[n], r, sz-n);
    memcpy  (r, tmp, n);
    for (; i < sz; i++)
        if (i != n-1 && r[i] != 0x80)
            r[i] ^= 0x81;
}

void rotccw (uint8_t *r, uint8_t sz, uint8_t n)
{
    if (n == sz ) return;  /* nothing to do */
    if (n > sz)   n %= sz; /* rotate 'n % sz' positions */

    uint8_t i = 0, tmp[n];

    memcpy  (tmp, r, n);
    memmove (r, &r[n], sz-n);
    memcpy  (&r[sz-n], tmp, n);
    for (; i < sz; i++)
        if (i != sz-n+1 && r[i] != 0xff)
            r[i] ^= 0x81;
}

void prnrows (uint8_t *r, uint8_t sz)
{
    uint8_t i;

    for (i = 0; i < sz; i++)
        printf (" 0x%02" PRIx8, r[i]);
    putchar ('\n');
}

Output

$ ./bin/bytes_rotate

 original array  : 0x01 0x01 0x01 0x01 0x01 0x01 0x01 0xff

 rotate cw by 1  : 0xff 0x80 0x80 0x80 0x80 0x80 0x80 0x80

 rotate ccw by 1 : 0x01 0x01 0x01 0x01 0x01 0x01 0x01 0xff

Perhaps the anonymous downvoter lacks the integrity to explain his vote and point out any technical inaccuracy? — David C. Rankin, Feb 22 '16 at 05:56
Perhaps. But I can tell you that your answer is not related to the question. The mistake is understandable as the original title was not all that clear and you misunderstood what OP meant by "rotation". You had to actually read the question and comments to find out what OP wanted to do. I edited the title to be more clear. — UncleO, Feb 22 '16 at 11:00
You know, that is the crux of it. Originally, and still in his examples he shows doing just exactly what the answer does. So if there is ambiguity or confusion over the term rotation of the array, that's understandable. Because the code above mirrors what he desires, but rather than printing 45 lines of example output to match his vertical format, I showed the same in a condensed 5 horizontal rows of hex rather than the same numbers in binary (since he wasn't rotating bits to begin with). Always a possibility he didn't grasp that as well. The numbers are all stored the same. — David C. Rankin, Feb 22 '16 at 11:05
You need to look a little closer at the question. In clockwise rotation, the 0x01s change to 0x80s. Your answer is not doing that. — UncleO, Feb 22 '16 at 11:26
Now I see it! I Cry "Uncle"! So clockwise all the bits are also shifted by one, but there is no bitwise rotation on the counter rotation. That doesn't make sense, but at least I understand where the issue is. I could have looked all night and not pickup up on it. — David C. Rankin, Feb 22 '16 at 11:32
Shifting only works out because of the particular shape he chose as an example, which was confusing, too. Just having one line instead of an "L" would have been more clear, but the rotation is supposed to work with any picture. Shifting is not going to work with an arbitrary arrangement. I think bit manip is still the easiest way. — UncleO, Feb 22 '16 at 11:39

Rotate a bitmap represented by an array of bytes

4 Answers4

Linked