# Difference between revisions of "Pre-calculated cycles for 8x3 matrix transpose"

### From Just in Time

m |
|||

(One intermediate revision by the same user not shown) | |||

Line 10: | Line 10: | ||

<source lang="cpp"> | <source lang="cpp"> | ||

+ | #include <iostream> | ||

/** | /** | ||

− | * calculate cycles along which values should be rotated in | + | * calculate cycles along which values should be rotated in an array to perform |

+ | * a 8x3 matrix transformation. See: | ||

* https://en.wikipedia.org/wiki/In-place_matrix_transposition#Non-square_matrices:_Following_the_cycles | * https://en.wikipedia.org/wiki/In-place_matrix_transposition#Non-square_matrices:_Following_the_cycles | ||

* | * | ||

Line 32: | Line 34: | ||

}; | }; | ||

+ | // keep on looping until all elements are at | ||

+ | // their destination position | ||

while (true) | while (true) | ||

{ | { | ||

− | // find the starting point of | + | // find the starting point of a cycle |

int seed = 0; | int seed = 0; | ||

for (;seed<24;++seed) | for (;seed<24;++seed) | ||

Line 40: | Line 44: | ||

if (positions[seed] != seed) break; | if (positions[seed] != seed) break; | ||

} | } | ||

− | if (seed == 24) break; // everything in | + | if (seed == 24) break; // everything in place |

+ | // seed is the first element of the cycle | ||

// now walk the cycle | // now walk the cycle | ||

std::cout << seed << ": "; | std::cout << seed << ": "; | ||

Line 54: | Line 59: | ||

std::cout << '\n'; | std::cout << '\n'; | ||

} | } | ||

+ | } | ||

+ | |||

+ | int main() | ||

+ | { | ||

+ | findCycles(); | ||

} | } | ||

</source> | </source> | ||

+ | |||

+ | This [http://coliru.stacked-crooked.com/a/abaa4da1abfdae00 returns] the following: | ||

+ | |||

+ | <pre> | ||

+ | 1: 8 18 6 2 16 13 12 4 9 3 1 | ||

+ | 5: 17 21 7 10 11 19 14 20 22 15 5 | ||

+ | </pre> |

## Latest revision as of 07:40, 30 September 2017

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">

- include <iostream>

/**

* calculate cycles along which values should be rotated in an array to perform * a 8x3 matrix transformation. 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 };

// keep on looping until all elements are at // their destination position while (true) { // find the starting point of a cycle int seed = 0; for (;seed<24;++seed) { if (positions[seed] != seed) break; } if (seed == 24) break; // everything in place

// seed is the first element of the cycle // 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'; }

}

int main() {

findCycles();

} </source>

This returns the following:

1: 8 18 6 2 16 13 12 4 9 3 1 5: 17 21 7 10 11 19 14 20 22 15 5