This is a personal blog. The opinions expressed here represent my own and not those of any of my employers or customers.

Except if stated otherwise, all the code shared is reusable under a MIT/X11 licence. If a picture is missing a copyright notice, it's probably because I'm owning it.

Friday, March 13, 2009

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.

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

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):

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 .

1 comment:

  1. Nice! This is an interesting post and reminds me of the time I found the sitepoint article on modified pre-order tree traversal. Could you post a couple of usage scenarios? I've vowed never to install Microsoft Silverlight so I can't see the implementation you posted, but maybe just explaining how these numbers correlate to images/pixels/etc would be cool. Also, could you go over the bit shifting a bit more, I'm not sure what you mean when you say "take the even/odd bits of the number and remove the white spaces."

    Great post!