Difference between revisions of "Pre-calculated cycles for 8x3 matrix transpose"
From Just in Time
(Created page with "When driving 8 WS2811 strips in parallel with an 8Mhz AVR we need to transpose arrays of rgb-values into groups of red-, green- and blue values (rgbrgbrgb... to rrrrrrrrgg...") |
m |
||
| Line 9: | Line 9: | ||
Obviously, when doing this, you'd need a description of the cycles, i.e. which values need to be moved where. For 24 values, finding the cycles could be done with a set of numbered cards. But of course, in about the same time, you could whip up a program that does this. The program looks like this: | Obviously, when doing this, you'd need a description of the cycles, i.e. which values need to be moved where. For 24 values, finding the cycles could be done with a set of numbered cards. But of course, in about the same time, you could whip up a program that does this. The program looks like this: | ||
| − | < | + | <source lang="cpp"> |
/** | /** | ||
* calculate cycles along which values should be rotated in the array. See: | * calculate cycles along which values should be rotated in the array. See: | ||
| Line 55: | Line 55: | ||
} | } | ||
} | } | ||
| − | </ | + | </source> |
Revision as of 11:31, 31 July 2016
When driving 8 WS2811 strips in parallel with an 8Mhz AVR we need to transpose arrays of rgb-values into groups of red-, green- and blue values (rgbrgbrgb... to rrrrrrrrggggggggbbbbbbbb). This boils down to an in-place 8*3 matrix transpose. This again boils down to going through cycles like this:
- pick up the value at position 1
- place the saved value from the previous step at position 8, but first save the value at that location
- place the saved value from the previous step at position 18, but first save the value at that location
- place the saved value from the previous step at position 6, but first save the value at that location
- etc, etc...
Obviously, when doing this, you'd need a description of the cycles, i.e. which values need to be moved where. For 24 values, finding the cycles could be done with a set of numbered cards. But of course, in about the same time, you could whip up a program that does this. The program looks like this:
<source lang="cpp"> /**
* calculate cycles along which values should be rotated in the array. See: * https://en.wikipedia.org/wiki/In-place_matrix_transposition#Non-square_matrices:_Following_the_cycles * */
void findCycles() {
// this array describes for each cell in the array
// where its value should go to.
// e.g. positions[2] == 16 means that the value at
// position 2 needs to move to position 16
int positions[] = {
0, 8, 16,
1, 9, 17,
2, 10, 18,
3, 11, 19,
4, 12, 20,
5, 13, 21,
6, 14, 22,
7, 15, 23
};
while (true)
{
// find the starting point of the cycle
int seed = 0;
for (;seed<24;++seed)
{
if (positions[seed] != seed) break;
}
if (seed == 24) break; // everything in order
// now walk the cycle
std::cout << seed << ": ";
int transfer = positions[seed];
positions[seed] = -1;
while (transfer != -1)
{
std::cout << transfer << " ";
std::swap( positions[transfer], transfer);
}
std::cout << '\n';
}
} </source>