Wire it at the processor level

[Update Mar 17. Fixed the cp/paste issues in code snippets]

«Wire it at the processor level» said my wife when I asked her how she'd compute indices of Morton's Layout.

A morton layout is a way of arranging tiles that grew up in a fractal way. It's pretty neat, doesn't waste too much space, and he's extensively used by DeepZoom/SeaDragon/MultiScaleImage in Silverlight.

It looks like this:

0 1 4 5 16 17
2 3 6 7 18 ..
8 9 12 13
10 11 14 15


One way to compute the position (x, y) of each tile is to take the even/odd bits of the number and remove the white spaces. e.g., 14 is 1110 so x will be 10 and y 11. Got it ?

First approach:
my first implementation was looking for the x, y values in 2 tables of 256 items. Easy and Fast. But sites like Memorabilia uses way more than 256 images. That's the point of using DeepZoom technology, displaying tons of stuff and zoom on the interesting parts.

Looping:
My second attempt was using a loop, some masks and shifts. Not as nice as it could.



void
morton (int n, int *x, int *y){
*x = *y = 0;
int i;
for (i=0; i <>> (2*i) & 0x00000001) <<>> (2*i + 1) & 0x00000001) <<>


One Step, No Loop:

And here's my current implementation, could you find a better way ? (yes, I know, I could save 4 masking operations):



void
morton (int n, int *x, int *y) {
n = (n & 0x99999999) + ((n & 0x22222222) <<>> 1);
n = (n & 0xc3c3c3c3) + ((n & 0x0c0c0c0c) <<>> 2);
n = (n & 0xf00ff00f) + ((n & 0x00f000f0) <<>> 4);
n = (n & 0xff0000ff) + ((n & 0x0000ff00) <<>> 8);
*x = n & 0x0000ffff;
*y = n >> 16;
}



That was a fun evening. And thanks to my wife for challenging me to do this as close to the wire as possible .