Hi all,

I have an index into a 2D array with power-of-two dimensions and I need the indexes of the neightboring elements, with wraparound. So for example for a [128][64] array the index is of the binary form 0000000000000000000vvvvvvvuuuuuu. So to get to the index of the next element in the u-direction I currently use code like this:

; mov eax, index
mov ebx, eax
and ebx, 00000000000000000001111111000000b
add eax, 1
and eax, 00000000000000000000000000111111b
or eax, ebx

For the next element in the v-direction this is:

; mov eax, index
add eax, 00000000000000000000000001000000b
and eax, 00000000000000000001111111111111b

Now I was wondering whether there's any faster way to do this? Maybe using MMX?


Posted on 2006-05-22 16:02:25 by C0D1F1ED
I found one crazy way to speed up the indexing. 8)

By inserting a 0 bit in the index between the u and v parts of the index (so it becomes 000000000000000000vvvvvvv0uuuuuu for the example), I can increment the u or v part (or both) and then mask with 00000000000000000011111110111111 to avoid propagating the overflow bit. So when moving in either direction it takes only two instructions to compute the new index.

Obviously this changes my data layout. It's like a [128][128] array (for the example) with every even 'line' unused. So it clearly doubles memory requirement. It's possible to 'interlace' it with another array of the same size but that's impractical for dynamically managed 2D arrays (images in practice).

So, I'm still wondering if anyone ever dealt with a similar situation and found a fast way. All ideas and inspiration is very welcome!
Posted on 2006-05-23 11:05:10 by C0D1F1ED
Okay, after another day of breaking my head on this I found yet another way.

By storing the u and v parts in separate registers (e.g. eax and ebx) I can increment and mask them separately, and then simply use to address the element.

So now the increment in either direction takes two operations, and there's no extra memory required. It uses two registers all the time but that's a reasonable payoff.

I'm still open for other suggestions! ;)
Posted on 2006-05-24 04:51:07 by C0D1F1ED