1

I'm looking for a way to quickly rotate the bits in a byte array without massive for loops that gets and sets each bit from old to new position. In this particular circumstance I need to rotate by 90 degrees clockwise. So for instance if I have:

unsigned char array[8] = {
0b11110000,
0b10000000,
0b10000000,
0b10000000,
0b00000000,
0b00000000,
0b00000000,
0b00000001
};

I need to get:

unsigned char array[8] = {
0b00001111,
0b00000001,
0b00000001,
0b00000001,
0b00000000,
0b00000000,
0b00000000,
0b10000000
};

Looking for the most efficient way possible to do this ... but it may not always be an 8x8 grid of bits. Will always be power of 2 dimension though (if that helps!)

paulsoulsby
  • 43
  • 6
  • 1
    You will not be able to transform you char array without a for-loop. – Gab Jan 19 '18 at 17:55
  • 1
    There is no built-in support in C or most of the underlying hardware to do it in any easy way. – Eugene Sh. Jan 19 '18 at 17:58
  • I ought to point out that I don't mean "no for loops at all"! Just not the nested for loops required to transform each bit, one by one. – paulsoulsby Jan 19 '18 at 18:01
  • choose C or C++, i suggest C++ since there is no way to do this in C. – Abr001am Jan 19 '18 at 18:02
  • 1
    @Gab: Well of course you can, but that would be unecessarily cumbersome. – Sani Huttunen Jan 19 '18 at 18:02
  • @paulsoulsby If you have an implementation in mind - post it here. It is not clear why nested loops are needed. – Eugene Sh. Jan 19 '18 at 18:03
  • It's for part of a routine to write to an Oled display. I want to create some custom characters on the fly with a canvas that is (e.g.) 64x16 bits. But the routine to write to the oled requires 8x8 blocks, with each block rotated 90s degrees (so that it appears correct on the oled). – paulsoulsby Jan 19 '18 at 18:05
  • 1
    Of course you can do it in C, @Abra. But I'm curious, do you have in mind some easy way to do it in C++ that is not doable in the subset in common with C? – John Bollinger Jan 19 '18 at 18:06
  • @JohnBollinger maybe `std::rotate` in `` – Abr001am Jan 19 '18 at 18:11
  • @JohnBollinger: with template abuse :-) – Jarod42 Jan 19 '18 at 18:12
  • @Abra, `std::rotate` does not do the job the OP wants to do. – John Bollinger Jan 19 '18 at 18:16
  • oh ok i misunderstood the question.sorry. But there is still `for_each` iterator that spares much writing. @JohnBollinger – Abr001am Jan 19 '18 at 18:16
  • @Jarod42, it seems almost anything can be accomplished via template abuse :-). Still, I'm not seeing that it affords any *easy* way to accomplish the OP's objective. – John Bollinger Jan 19 '18 at 18:18
  • @JohnBollinger: I think what SaniSinghHuttunen does manually can be done with template not so hardly. – Jarod42 Jan 19 '18 at 18:28
  • @Jarod42, I don't see that Sani's solution would benefit from a template at all. And I also do not see that it is a complete solution (nor could it be made one by templating, I think), since the OP says the problem size is not fixed at 8 x 8. – John Bollinger Jan 19 '18 at 18:35
  • If speed is more important than memory, create an array of 8 bytes that holds the new bit position for every possible single bit and OR them together with a single loop. – Jongware Jan 20 '18 at 12:27
  • [Rotate a bitmap represented by an array of bytes](https://stackoverflow.com/q/35544172/995714) – phuclv Aug 01 '18 at 06:00

1 Answers1

1

Cumbersome but without for-loops:

rotatedArray[0] = (array[7] & 128) || (array[6] & 128) >> 1 || (array[5] & 128) >> 2 || (array[4] & 128) >> 3 || (array[3] & 128) >> 4 || (array[2] & 128) >> 5 || (array[1] & 128) >> 6 || (array[0] & 128) >> 7;

rotatedArray[1] = (array[7] & 64) << 1 || (array[6] & 64) || (array[5] & 64) >> 1 || (array[4] & 64) >> 2 || (array[3] & 64) >> 3 || (array[2] & 64) >> 4 || (array[1] & 64) >> 5 || (array[0] & 64) >> 6;

rotatedArray[2] = (array[7] & 32) << 2 || (array[6] & 32) << 1|| (array[5] & 32) || (array[4] & 32) >> 1 || (array[3] & 32) >> 2 || (array[2] & 32) >> 3 || (array[1] & 32) >> 4 || (array[0] & 32) >> 5;

...

rotatedArray[7] = (array[7] & 1) << 7 || (array[6] & 1) << 6 || (array[5] & 1) << 5 || (array[4] & 1) << 4 || (array[3] & 1) << 3 || (array[2] & 1) << 2 || (array[1] & 1) << 1 || (array[0] & 1);

Edit

If the canvas is limited to 32x8 (8 32-bit integers) and the result should be 4 8x8 blocks, then without for-loops:

rotatedArray[0][0] = (array[7] & 0x80000000) >> 24 || (array[6] & 0x80000000) >> 25 || (array[5] & 0x80000000) >> 26 || (array[4] & 0x80000000) >> 27 || (array[3] & 0x80000000) >> 28 || (array[2] & 0x80000000) >> 29 || (array[1] & 0x80000000) >> 30 || (array[0] & 0x80000000) >> 31;
rotatedArray[0][1] = (array[7] & 0x40000000) >> 23 || (array[6] & 0x40000000) >> 24 || (array[5] & 0x40000000) >> 25 || (array[4] & 0x40000000) >> 26 || (array[3] & 0x40000000) >> 27 || (array[2] & 0x40000000) >> 28 || (array[1] & 0x40000000) >> 29 || (array[0] & 0x40000000) >> 30;
rotatedArray[0][2] = (array[7] & 0x20000000) >> 22 || (array[6] & 0x2000000) >> 23 || (array[5] & 0x20000000) >> 24 || (array[4] & 0x20000000) >> 25 || (array[3] & 0x20000000) >> 26 || (array[2] & 0x20000000) >> 27 || (array[1] & 0x20000000) >> 28 || (array[0] & 0x20000000) >> 29;
rotatedArray[0][3] = (array[7] & 0x10000000) >> 21 || (array[6] & 0x10000000) >> 22 || (array[5] & 0x10000000) >> 23 || (array[4] & 0x10000000) >> 24 || (array[3] & 0x10000000) >> 25 || (array[2] & 0x10000000) >> 26 || (array[1] & 0x10000000) >> 27 || (array[0] & 0x10000000) >> 28;
rotatedArray[0][4] = (array[7] & 0x8000000) >> 20 || (array[6] & 0x8000000) >> 21 || (array[5] & 0x8000000) >> 22 || (array[4] & 0x8000000) >> 23 || (array[3] & 0x8000000) >> 24 || (array[2] & 0x8000000) >> 25 || (array[1] & 0x8000000) >> 26 || (array[0] & 0x8000000) >> 27;
rotatedArray[0][5] = (array[7] & 0x4000000) >> 19 || (array[6] & 0x4000000) >> 20 || (array[5] & 0x4000000) >> 21 || (array[4] & 0x4000000) >> 22 || (array[3] & 0x4000000) >> 23 || (array[2] & 0x4000000) >> 24 || (array[1] & 0x4000000) >> 25 || (array[0] & 0x4000000) >> 26;
rotatedArray[0][6] = (array[7] & 0x2000000) >> 18 || (array[6] & 0x2000000) >> 19 || (array[5] & 0x2000000) >> 20 || (array[4] & 0x2000000) >> 21 || (array[3] & 0x2000000) >> 22 || (array[2] & 0x2000000) >> 23 || (array[1] & 0x2000000) >> 24 || (array[0] & 0x2000000) >> 25;
rotatedArray[0][7] = (array[7] & 0x1000000) >> 17 || (array[6] & 0x1000000) >> 18 || (array[5] & 0x1000000) >> 19 || (array[4] & 0x1000000) >> 20 || (array[3] & 0x1000000) >> 21 || (array[2] & 0x1000000) >> 22 || (array[1] & 0x1000000) >> 23 || (array[0] & 0x1000000) >> 24;

rotatedArray[1][0] = (array[7] & 0x800000) >> 16 || (array[6] & 0x800000) >> 17 || (array[5] & 0x800000) >> 18 || (array[4] & 0x800000) >> 19 || (array[3] & 0x800000) >> 20 || (array[2] & 0x800000) >> 21 || (array[1] & 0x800000) >> 22 || (array[0] & 0x800000) >> 23;
rotatedArray[1][1] = (array[7] & 0x400000) >> 15 || (array[6] & 0x400000) >> 16 || (array[5] & 0x400000) >> 17 || (array[4] & 0x400000) >> 18 || (array[3] & 0x400000) >> 19 || (array[2] & 0x400000) >> 20 || (array[1] & 0x400000) >> 21 || (array[0] & 0x400000) >> 22;
rotatedArray[1][2] = (array[7] & 0x200000) >> 14 || (array[6] & 0x200000) >> 15 || (array[5] & 0x200000) >> 16 || (array[4] & 0x200000) >> 17 || (array[3] & 0x200000) >> 18 || (array[2] & 0x200000) >> 19 || (array[1] & 0x200000) >> 20 || (array[0] & 0x200000) >> 21;
rotatedArray[1][3] = (array[7] & 0x100000) >> 13 || (array[6] & 0x100000) >> 14 || (array[5] & 0x100000) >> 15 || (array[4] & 0x100000) >> 16 || (array[3] & 0x100000) >> 17 || (array[2] & 0x100000) >> 18 || (array[1] & 0x100000) >> 19 || (array[0] & 0x100000) >> 20;
rotatedArray[1][4] = (array[7] & 0x80000) >> 12 || (array[6] & 0x80000) >> 13 || (array[5] & 0x80000) >> 14 || (array[4] & 0x80000) >> 15 || (array[3] & 0x80000) >> 16 || (array[2] & 0x80000) >> 17 || (array[1] & 0x80000) >> 18 || (array[0] & 0x80000) >> 19;
rotatedArray[1][5] = (array[7] & 0x40000) >> 11 || (array[6] & 0x40000) >> 12 || (array[5] & 0x40000) >> 13 || (array[4] & 0x40000) >> 14 || (array[3] & 0x40000) >> 15 || (array[2] & 0x40000) >> 16 || (array[1] & 0x40000) >> 17 || (array[0] & 0x40000) >> 18;
rotatedArray[1][6] = (array[7] & 0x20000) >> 10 || (array[6] & 0x20000) >> 11 || (array[5] & 0x20000) >> 12 || (array[4] & 0x20000) >> 13 || (array[3] & 0x20000) >> 14 || (array[2] & 0x20000) >> 15 || (array[1] & 0x20000) >> 16 || (array[0] & 0x20000) >> 17;
rotatedArray[1][7] = (array[7] & 0x10000) >> 9 || (array[6] & 0x10000) >> 10 || (array[5] & 0x10000) >> 11 || (array[4] & 0x10000) >> 12 || (array[3] & 0x10000) >> 13 || (array[2] & 0x10000) >> 14 || (array[1] & 0x10000) >> 15 || (array[0] & 0x10000) >> 16;

rotatedArray[2][0] = (array[7] & 0x8000) >> 8 || (array[6] & 0x8000) >> 9 || (array[5] & 0x8000) >> 10 || (array[4] & 0x8000) >> 11 || (array[3] & 0x8000) >> 12 || (array[2] & 0x8000) >> 13 || (array[1] & 0x8000) >> 14 || (array[0] & 0x8000) >> 15;
rotatedArray[2][1] = (array[7] & 0x4000) >> 7 || (array[6] & 0x4000) >> 8 || (array[5] & 0x4000) >> 9 || (array[4] & 0x4000) >> 10 || (array[3] & 0x4000) >> 11 || (array[2] & 0x4000) >> 12 || (array[1] & 0x4000) >> 13 || (array[0] & 0x4000) >> 14;
rotatedArray[2][2] = (array[7] & 0x2000) >> 6 || (array[6] & 0x2000) >> 7 || (array[5] & 0x2000) >> 8 || (array[4] & 0x2000) >> 9 || (array[3] & 0x2000) >> 10 || (array[2] & 0x2000) >> 11 || (array[1] & 0x2000) >> 12 || (array[0] & 0x2000) >> 13;
rotatedArray[2][3] = (array[7] & 0x1000) >> 5 || (array[6] & 0x1000) >> 6 || (array[5] & 0x1000) >> 7 || (array[4] & 0x1000) >> 8 || (array[3] & 0x1000) >> 9 || (array[2] & 0x1000) >> 10 || (array[1] & 0x1000) >> 11 || (array[0] & 0x1000) >> 12;
rotatedArray[2][4] = (array[7] & 0x800) >> 4 || (array[6] & 0x800) >> 5 || (array[5] & 0x800) >> 6 || (array[4] & 0x800) >> 7 || (array[3] & 0x800) >> 8 || (array[2] & 0x800) >> 9 || (array[1] & 0x800) >> 10 || (array[0] & 0x800) >> 11;
rotatedArray[2][5] = (array[7] & 0x400) >> 3 || (array[6] & 0x400) >> 4 || (array[5] & 0x400) >> 5 || (array[4] & 0x400) >> 6 || (array[3] & 0x400) >> 7 || (array[2] & 0x400) >> 8 || (array[1] & 0x400) >> 9 || (array[0] & 0x400) >> 10;
rotatedArray[2][6] = (array[7] & 0x200) >> 2 || (array[6] & 0x200) >> 3 || (array[5] & 0x200) >> 4 || (array[4] & 0x200) >> 5 || (array[3] & 0x200) >> 6 || (array[2] & 0x200) >> 7 || (array[1] & 0x200) >> 8 || (array[0] & 0x200) >> 9;
rotatedArray[2][7] = (array[7] & 0x100) >> 1 || (array[6] & 0x100) >> 2 || (array[5] & 0x100) >> 3 || (array[4] & 0x100) >> 4 || (array[3] & 0x100) >> 5 || (array[2] & 0x100) >> 6 || (array[1] & 0x100) >> 7 || (array[0] & 0x100) >> 8;

rotatedArray[3][0] = (array[7] & 0x80) || (array[6] & 0x80) >> 1 || (array[5] & 0x80) >> 2 || (array[4] & 0x80) >> 3 || (array[3] & 0x80) >> 4 || (array[2] & 0x80) >> 5 || (array[1] & 0x80) >> 6 || (array[0] & 0x80) >> 7;
rotatedArray[3][1] = (array[7] & 0x40) << 1 || (array[6] & 0x40) || (array[5] & 0x40) >> 1 || (array[4] & 0x40) >> 2 || (array[3] & 0x40) >> 3 || (array[2] & 0x40) >> 4 || (array[1] & 0x40) >> 5 || (array[0] & 0x40) >> 6;
rotatedArray[3][2] = (array[7] & 0x20) << 2 || (array[6] & 0x20) << 1 || (array[5] & 0x20) || (array[4] & 0x20) >> 1 || (array[3] & 0x20) >> 2 || (array[2] & 0x20) >> 3 || (array[1] & 0x20) >> 4 || (array[0] & 0x20) >> 5;
rotatedArray[3][3] = (array[7] & 0x10) << 3 || (array[6] & 0x10) << 2 || (array[5] & 0x10) << 1 || (array[4] & 0x10) || (array[3] & 0x10) >> 1 || (array[2] & 0x10) >> 2 || (array[1] & 0x10) >> 3 || (array[0] & 0x10) >> 4;
rotatedArray[3][4] = (array[7] & 0x8) << 4 || (array[6] & 0x8) << 3 || (array[5] & 0x8) << 2 || (array[4] & 0x8) << 1 || (array[3] & 0x8) || (array[2] & 0x8) >> 1 || (array[1] & 0x8) >> 2 || (array[0] & 0x8) >> 3;
rotatedArray[3][5] = (array[7] & 0x4) << 5 || (array[6] & 0x4) << 4 || (array[5] & 0x4) << 3 || (array[4] & 0x4) << 2 || (array[3] & 0x4) << 1 || (array[2] & 0x4) || (array[1] & 0x4) >> 1 || (array[0] & 0x4) >> 2;
rotatedArray[3][6] = (array[7] & 0x2) << 6 || (array[6] & 0x2) << 5 || (array[5] & 0x2) << 4 || (array[4] & 0x2) << 3 || (array[3] & 0x2) << 2 || (array[2] & 0x2) << 1 || (array[1] & 0x2) || (array[0] & 0x2) >> 1;
rotatedArray[3][7] = (array[7] & 0x1) << 7 || (array[6] & 0x1) << 6 || (array[5] & 0x1) << 5 || (array[4] & 0x1) << 4 || (array[3] & 0x1) << 3 || (array[2] & 0x1) << 2 || (array[1] & 0x1) << 1 || (array[0] & 0x1);

Disclaimer: Might be some mistakes but you get the idea.

Sani Huttunen
  • 23,620
  • 6
  • 72
  • 79
  • Yes for the OP's example, but he says the dimensions may not always be 8. – John Bollinger Jan 19 '18 at 18:31
  • Yes , this is essentially manually unrolling the loops. It may be an acceptable route to take if no better solution can be found. I could always break the bigger canvas down in to 8x8 blocks first. – paulsoulsby Jan 19 '18 at 18:38
  • @paulsoulsby, I'm not seeing how breaking a larger canvas into 8x8 blocks would assist you with performing the computation you describe -- unless you meant a collection of blockwise rotations in the first place? – John Bollinger Jan 19 '18 at 18:43
  • Well, actually, I guess it could help, but you would still need to perform a bunch of subsequent *byte*wise rearrangements after the blockwise ones. That might still yield a net win, but you'll have some loop nests. – John Bollinger Jan 19 '18 at 18:55
  • If there are few possible dimensions (like only 8x8, 64x16, 32x32 and 128x64) you could write different functions for each dimension configuration and do without any for-loops. However if the dimensions can be arbitrary (canvas from 8x8 to AxB and any permutation in between) then you'll one way or another end up with nested for-loops. Best bet would be, as you say, to split the canvas into 8x8 blocks with nested for-loops. – Sani Huttunen Jan 19 '18 at 19:26
  • Come to think of it. Only a single for-loop is necessary if you unroll the inner loop and use division and modulus on the counter for indexing. So you COULD do without nesting but hardly worth the effort. – Sani Huttunen Jan 19 '18 at 19:35
  • @JohnBollinger the situation I’m actually requiring will store 8 32-bit ints, ie a 32x8 canvas with each 8x8 block rotated by 90 degrees. I think I may have confused the situation with that part! 8x8 block rotates are fine and I’ll then shift them into correct position in the 32bit int. – paulsoulsby Jan 19 '18 at 19:41