Saturday, February 28, 2009

Text Layout Engines

As many of my loyal followers know, I wrote a really fast text layout engine for Moonlight 1.0 which was able to layout text in more-or-less a single pass over the string. Hard to do better than that, especially with my superbly (I'm allowed to stroke my own ego, right?) designed font/glyph caches.

That said, the code had also been superbly disgusting and unmaintainable. Made worse when I had to add hacks to render text selection (Silverlight 1.0's TextBlock is like a GtkLabel in that it just renders text, but Silverlight 2.0's TextBox supports editing and selection and so is therefor more akin to a multi-line GtkEntry widget).

Well, Thursday night, as I was watching House on Hulu, I had one of those "House moments" where he suddenly realizes what the patient is suffering from and how to solve the problem (usually when his friend, Wilson, is talking to him about something random).

I spent all day yesterday (and I mean all day, until 11pm last night) putting together my thoughts for a new design and working out the details and I think I now have a vastly improved solution that not only uses less memory in all but the pathological cases (I now use a UTF-8 string instead of a UCS4 string), but also doesn't require:

  • a pass over the text to break on CR/LF to construct a list of text runs which were what the old TextLayout engine I wrote used instead of a char* (because the layout engine now handles CR/LFs)
  • a whole new set of text runs every time selection boundaries change in a TextBox (because selection is no longer represented by text runs)

Of course, the same brilliance of the old design still apply: no need to re-layout when most text properties (underline, foreground, background, etc) change (obviously we still have to re-layout if font properties change because they change the metrics).

With my new design, my TextLayout class has a Select() method which allows the consumer to change the selected region of text. When you change the selection, my new logic can simply clear the cached glyph clusters for the affected area(s).

A "glyph cluster" is a cached (sub)run of glyphs in a particular text run. A "text run" is a substring of text that share all the same text attributes which does not span across line boundaries.

To break it down, a layout contains a list of lines. Each line contains a list of runs. Each run contains a list of glyph clusters.

Normally, a run will consist of only a single glyph cluster unless it overlaps the selection.

For example, if the first half of the run is within the selection, then the run will contain 2 glyph clusters (one for the selected portion and one for the non-selected portion). However, if the selection is fully contained within a single run but doesn't span the entire run, then it's possible to have up to 3 glyph clusters for that run: pre-selection, selection, post-selection.

The brilliance of doing it this way is that it simplifies keeping track of kerning between selected regions, so that as you drag your selection across some text, the text following your mouse cursor doesn't appear to "jump" to the left or right as you move between characters that are kerned.

Saturday, February 14, 2009

More Exciting Updates on Mono/Android

Looks like Koushik Dutta has been kicking butt getting Mono onto Google's Android platform:

Keep up the awesome hacking, Koushik!

Also of interest is his article on why JNI sucks compared to doing the same thing in .NET: JNI in Android (and a foreword about why JNI sucks)

I never actually used JNI back when I was doing Java development in school, so when people told me it sucked I just took their word for it, but always wondered just how bad it was. Now I know. All I can say is: Ugh.

Hopefully the Java community replaces JNI with something as clean and elegant as what we find in .NET.

Friday, February 13, 2009

Mono 2.0 Wins's Product of the Year Award

I'd just like to congratulate the Mono team on their Product of the Year Award and for a job well done!

Congratulations guys, you deserved this award! You guys kicked ass this past year and we all get to benefit from your awesomeness.

Epic Weekly News for the week of Feb 8th

A lot has happened this week, in particular:

For those in the Cambridge/Boston area, we now give you a word from our sponsor:

Sunday, February 8, 2009

Alleyoop 0.9.4 released

It's been ages since the last release of Alleyoop, but an update has finally arrived. I've just fixed up Alleyoop to build on openSUSE 11.1 (some libbfd stuff has changed, apparently) and so I've dropped the need for libbfd and libiberty completely. The code that used those libraries didn't really gain us any extra information that Valgrind wasn't already giving us anyway, so it as rather pointless.

It looks like a year and a half or so ago I fixed some parser bugs too and just never made a new release with those fixes.

So now Freedom Lovers who prefer a GUI can once again Valgrind their applications 'til their heart is content.

You can download the new Alleyoop 0.9.4 package here.

Oh, also, if there are any bored web developers out there, I'd appreciate it if someone could make a less-ugly website than what is currently at In case you couldn't tell, I'm horrible at website design.

As another fabulous example of my webdesign prowess, take a gander at GMime's website. So yea, that site could also use a make-over.

Update: Thanks to Akos Kemives for his improved website design for Alleyoop!

Code Snippet Licensing

All code posted to this blog is licensed under the MIT/X11 license unless otherwise stated in the post itself.