I am interested in optimizing my diagonal iterator. For background on the problem see StackOverflow question Traverse Matrix in Diagonal strips from 2009. In the code below, I use a different approach than the solutions found in that topic. The idea is to create sort of a gray code-like iterator that steps through the diagonals using only a single boolean control variable (whether columns are increasing, zColumnIncrease). This methodology creates a state machine with 7 possible states:
// z - boolean type indicator
// ct - count (number of rows or columns)
// x - index (the one-based index of the row or column)
zColumnIncrease = true;
....
if( xRow == ctRows && xColumn == ctColumns ) break;
if( zColumnIncrease ){
if( xColumn < ctColumns ){
xColumn++;
if( xRow > 1 ){
xRow--;
} else {
zColumnIncrease = false;
}
} else {
zColumnIncrease = false;
xRow++;
}
} else {
if( xColumn > 1 ){
if( xRow < ctRows ){
xColumn--;
xRow++;
} else {
zColumnIncrease = true;
xColumn++;
}
} else {
zColumnIncrease = true;
if( xRow < ctRows ){
xRow++;
} else {
xColumn++;
}
}
}
Note that this state machine (which is normally at the end of some work loop) iterates the diagonals in boustrophedon order. For example, for a 5x5 column-ordered matrix the iteration of the cells is as follows:
11
21 12
13 22 31
41 32 23 14
15 24 33 42 51
52 43 34 25
35 44 53
54 45
55
What I would like to do is optimize this state machine. I see two main types of optimization: logical expression compression and predication. In the first case it may be possible to combine the logic in some way so that the code is more efficient. A much bigger win would be to replace the if-statements with predicated instructions. This is ideally what I would like to do, so that a resulting assembly language translation would be unbranched. Therefore, I am interested in optimizations to this code and specifically would like to know how I can predicate the code so that it becomes unbranched.
