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 .

Tuesday, March 10, 2009

A gift to the competition

For once, I didn't spend my weekends hacking time on patches for F-Spot. Instead, in my journey addressing an old and vocal request, I ended up writing xcf files support for eog, gthumb, gqview, F-Spot obviously and maybe some more.

The code for this is a GdkPixbuf loader, based on this specification (moved there since) and some xcf hexdumps, meaning it's suitable to be released under the LGPL for gdk-pixbuf inclusion. (Googling around, I found some mail archives stating that the GPL(The Gimp)/LGPL (gdk-pixbuf) issue was preventing the inclusion of a loader based on The Gimp's code in gdk).

  • read xcf files up to v002,
  • compressed and rle-encoded,
  • grayscale and rgb color modes,
  • supports all kinds of layer blending,
  • supports layer masks
  • .xcf.gz and .xcf.bz2 support (for jimmac),
  • indexed mode

Clone this piece of awesomeness from git://gitorious.org/xcf-pixbuf-loader/mainline.git and report bugs by e-mail. Build it, copy the .so next to the others loaders on your system and run gdk-pixbuf-query-loaders[-64].

(Get the sample file I used for those screenshots from there)

Monday, March 9, 2009

ChangeLog entry

2009-03-09 Stephane Delcroix <stephane@delcroix.org>

* Initial revision