Actions

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...")
 
 
(2 intermediate revisions by the same user not shown)
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:
  
<code lang="cpp">
+
<source lang="cpp">
 +
#include <iostream>
 
/**
 
/**
  * calculate cycles along which values should be rotated in the array. See:
+
  * 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 the cycle
+
         // 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 order
+
         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 55: Line 60:
 
     }
 
     }
 
}
 
}
</code>
+
 
 +
int main()
 +
{
 +
    findCycles();
 +
}
 +
</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">

  1. 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