Array index trick

Oh that's it! Somehow I managed to try everything else but that. Thank you.

Juha

You should endevour to figure things out, not guess. Guessing is dangerous because it can lead to situations where things appear to work correctly but actually don't, and you won't discover that until later. Here's how the indexing "trick" works:

Consider an array of 25 elements.

***** ***** ***** ***** *****01234 56789 ...

Conceptually, we can view that as a linear array of 25 (as above) or as a logical "matrix" or "2D array" 5 units per side:

*****01234*****56789(etc, omitted for brevity)

Note how the indices haven't changed. Also note that the first element of row 1 (zero based) is at index 5, or (width * 1). If you'd continue the diagram you'd see that the second row begins at index 10, or (width * 2). From this it should become clear that translating just the "y" part into a linear index is simply (y * width). This works out for accessing row zero (0 * width == 0) as well. Now that you've managed to calculate the correct "row," finding the exact element is simply a matter of adding the "x" index to the already calculated linear index for the row; the final calculation becomes (y * width + x).

Note that the array, obviously, does not need to be considered logically square for this to work out (a 30-element linear array can be interpreted as a 3x10 grid, for example).

Quote:

Original post by jpetrie You should endevour to figure things out, not guess. Guessing is dangerous because it can lead to situations where things appear to work correctly but actually don't, and you won't discover that until later.

An excellent piece of advice, there.

It's still possible to encounter span/stride issues even today, with certain image formats. It's not terribly hard to deal with; span or stride is often measured as total number of bytes or elements per row, or number of extra bytes/elements per row. The calculation becomes some like (x + y * stride) or (x + y * (width + stride)), respectively. As long as you have the documentation about the nature of the structure of the image or data, and are aware of it, its not too bad.

Yes, that is a good piece of advice, jpetrie. I should really get into that habit. My problem is that I really suck at math (a great trait for a programmer ;)) so sometimes I find guessing easier than just doing the brainwork. But thanks, everybody, for your replies.

Juha

I imagine you might get some speed boost by making width a multiple of the cache line but maybe this is limited to certain situations.