This note’s for you

These days I did finally some more Classpath hacking. The last couple of months, the Classpath project was seemingly undead. That left me in some kind of coding depression But I think that Classpath has it’s own right for existence. There are several reasons why I will continue (and re-energize) my support for this project:

• The process is completely open for anybody. There are almost no constraints, except for contributors to produce quality code and sign the copyright assignment with the FSF. I understand that it’s necessary for OpenJDK to have a lot of constraints, after all, this is the reference and they have a _much_ broader userbase than Classpath. Also, they don’t seem to believe in free, self-regulating processes, but more in governed, regulated-from-the-top processes.
• Several projects are using GNU Classpath, and probably will do so for a long time. From the top of my head, there’s GCJ, Kaffe, JamVM, JNode, Jalimo. Cacao has some support for OpenJDK, but this seems very early still.
• I really have no idea what to hack on OpenJDK. Of course, there’s the occasional bug that I care about, sometimes a fix for something that I come over when trying to intergrate with Jamaica, but that’s pretty much it. It is not really possible for me to add cool new features or something similar, that’s completely caught in complicated processes AFAICS (see above).
• It’s not really possible to fix bugs quickly, because things are hidden away. Nobody knows what’s already done behind Sun’s walls. Every week or two they throw over code that’s finished, but it’s hard to take part in any development.
• I believe the Classpath code is slimmer than OpenJDK, and (in my experience) the inter-package-dependencies are not so twisted as in OpenJDK. This seems to make it more suitable for small-footprint and embedded scenarios.
• Hacking Classpath is so much fun. Even if nobody cares about it, it’s still a satisfying feeling to implement some missing classes here, fix a bug there and be useful for the one user that might be left After all, the ‘Free’ in Classpath means really Free, not the semi-Free of OpenJDK (cool: the code is under a Free license, uncool: most things else is still behind closed doors, and some will surely remain so forever, just because it is OpenJDK and Sun).

In this spirit, I started to implement javax.tools for Classpath. In the next couple of days we try to get back our JAPI pages, that appear to be broken or at least not updated since over a year (ugh). Also, Andrew announced today the creation of another hybrid project called BrandWeg, that combines Classpath with OpenJDK pieces. Kindof like inverse IcedTea. Also, Andrew continued with his JMX implementation which is really cool. Stefan Huehner seems to contribute lots of cleanup patches and Mario works on his sound API. We are not dead yet! Long live Classpath! Yay!

.. I’m working on a couple of things in parallel:

On one front I’m trying to provide a replacement for the graphics rasterizer in OpenJDK. As far as I can see to this point, the rasterizer I implemented for GNU Classpath should be fine for a start. I offered this to OpenJDK, but there seem to be a couple of legal and organizational hurdles to take. I am discussing how to best solve these issues and move forward with the code. It looks like going through the copyright grantback procedure with the FSF for the code in question is hard to avoid. In the meantime, Jim from the Java2D team has factored out a preliminary interface for the rasterizer, and Mark Reinhold offered to provide early read-only VCS access to the Java2D workspace. Thanks!

Then I am working on integrating the OpenJDK class library into the JamaicaVM. It turned out that the package-after-package approach is much more painful than expected, due to massivly intertwined dependencies. I even spotted a couple of places where private methods in ‘alien’ packages are called via reflection (urgs). I wonder how that went through QA, and I wonder what happens when one such method changes… Anyway, with the release of IcedTea I switched to importing all classes at once, with the help of the IcedTea classes this was surprisingly painless. Now I’m working with my collegues to get the native things done. So far we found that they even have some kind of VM/native interface in place, at least for the classes that I looked at so far. Basically, platform dependend syscalls are abstracted out as JVM_* functions. I hope to get a HelloWorld running this week.

Related to the OpenJDK/JamaicaVM porting work, I am working to get the Classpath GTK peers, and the other AWT backends in Jamaica to work with the JDK. The biggest problem here seem to be the differences in Image and Font handling, which are abstracted out in a backend-independent way in GNU Classpath, but seem to be implemented rather monolithically in OpenJDK. Dunno how to solve that. It might be possible to use the OpenJDK implementations when the encumbered pieces in the font and graphics rasterizer are solved. So far I think we have to go with a bunch of GNU Classpath classes in java.awt.***.

These days I did what I wanted to do for a long time, that is implement an efficient anti-aliasing for the rasterizer of the Escher peers (this rasterizer can be used in arbitrary other scenarios as well though). This was mainly triggered by OpenJDK’s need for a replacement for their encumbered rasterizer, and I hope that mine is probably a good fit. Let me outline how it works.

Before doing anti-aliasing, let me show how shapes are generally rendered to a raster in general:

Basically, we scan the shape line by line, and at the intersection points we ‘turn on’ or ‘turn off’ the pixel at that intersection point. In order to do this efficiently, we first sort the edges of the shape according to their Y and X coordinates.

Ok, but what about anti-aliasing? Basically it’s the same, only that we scan each line more than once. Usually each line is scanned a -power-of-2 times, for example 8. Depending on how often we intersect the shape in a pixel, we can calculate a coverage value. This coverage value is then used as alpha value when filling the actual pixel.

The interesting part here is how the coverage values are managed.  A simple and naive approach is of course to store them in an array, one entry for each pixel. Now if we scan a line we proceed just like in non-AA rasterization and turn on (add 1) to the entry in this array that corresponds to the pixel when we ‘enter’ the shape, do the same for all pixel entries in between until we ‘leave’ the shape for that scanline. This is repeated for the same pixel line 2^N times. In the end we have an array that has the correct coverage values for each pixel.

Of course, iterating over the array and adding up the coverage entries isn’t exactly efficient. A better idea is to only store deltas. So, instead of adding 1 to all the pixel entries ‘inside’ the shape, we only add 1 at the entry pixel and substract 1 at the exit pixel. This is much better.

We must still iterate over the whole array though when we want to display it to the destination surface, to find consecutive chunks of equal pixels. Imagine that for a simple 600 pixels wide rectangle. Pretty bad. So what I did today and the last couple of days is design a datastructure that manages the coverage values in a much more efficient way. Basically, it is a simple linked list of deltas together with their X coordinates. This list is always sorted according to the X coordinates. Each time we scan a line, we insert one entry into that list for each intersection point. In order to find the insertion point, we do a linear search. A linear search? Haven’t we all learned that this is pretty inefficient. Yes. But here we make use of the fact that the scanline is always scanned in a linear fashion, from left to right, and that the list is always sorted. The data structure has a pointer to the last item that got inserted, and starting from there, it is not possible (or at least highly unlikely) that the next insertion point is more than 2 items away. When the next scanline inside the same Y pixel row is scanned, we ‘rewind’ the data structure to point to the first item again, and start searching there. Finally, when doing the actual rendering, we can simply iterate this list, and fill complete segments in one go. This can be quite efficiently implemented on most backends (for example, for a framebuffer it’s basically a simple memset operation when the color is opaque).

A nice side effect of this technique is that non-anti-aliased rendering can now be handled as a special case of anti-aliased rendering, with no performance penalty. Another little detail of the implementation is that the datastructure doesn’t throw away and re-allocate its entries, but keeps unused items for later reuse. This way, the scanline converter usually needs allocation, after some initial setup of its tables and structures.

I did a run of GNU Classpath’s AWT and J2D benchmarks. The results are more fair now (JDK6 vs Cairo vs X/Escher). Cairo now beats the X peers, but the overall speed is still impressive given that it’s done all in java. I guess my own small benchmark was a nuance too artificial

Some more numbers for you as followup to my last measurements:

• jdk6: ~750ms
• my latest improved Escher/Java peers on Cacao: ~200ms

I wonder what Sun did to the shape renderer in jdk6. It’s quite slow compared to JDK5 and even much slower than the Escher peers. And that is without antialiasing just like the Java renderer. Probably this has to do with their work on the text renderer (which is even slower - ~1600ms - as it uses AA by default now).

It would be interesting to see how fast the Escher peers would run on hotspot. I’m thinking that a significant part of the performance gap between jdk5 and the escher peers is due to the performance of the VM itself as the escher peers and the shape renderer run comletely in java. Unfortunately it’s not trivial to port the peers to Sun’s JDK due to the few differences on the peer API. I’m still hoping that somebody will get hotspot running with GNU Classpath.

I rewrote the java based rasterizer that is used in the X peers of GNU Classpath. Heres some interesting numbers. Rendering a relatively complex shape (actually, the outline of a glyph vector) 250 times takes:

• ~60ms on JDK1.5
• ~780 ms on Cacao with the Cairo peers
• ~350 ms on Cacao with the X peers and the new Rasterizer

Learned lesson: native code is not necessarily faster than java code. The whole rendering pipeline of the X peers is implemented in plain java. X only draws horizontal lines here.

The comparison with the JDK is not necessarily fair but gives an interesting impression what should be possible.

Find the test program here. Yes it is a microbenchmark that highlights one particular case (rendering complex shapes). I will make more interesting and comprehensive benchmarks as soon as I am able to run the Java2D and AWT benchmarks that ship with GNU Classpath.

Last time around we were able to detect edges and link them in order to detect stems and serifs. In the meantime I have made another nice picture of the glyph ‘C’ with its segments:

The last thing we need to do before we can actually hint our glyphs is to detect edges. Edges are sets of 1 or more segments that are positioned (approximately) at the same position. For the vertical direction and the glyph ‘M’ this would look like this (every edge marked with another color):

These edges are then associated with our Blue Zones (where possible). Later we will move these edges around to fit on the grid (rather than moving single points).

Next time it will become interesting: Then we will start the actual grid-fitting process.

Let me insert a small break in my series of font lectures to show the latest and greatest screenshots. Just today I got the first hinted text rendered (left without hinting, right with hinting):

Both are rendered using Sun’s Graphics2D impl with anti-aliasing turned on (via Graphics2D.fill(Shape) ). The outcome is quite similar with Cairo though. Unfortunately I haven’t found a rasterizer yet that can render this thing properly without AA. Classpath’s Cairo backend doesn’t support turning off AA right now and Sun’s rasterizer fails to render this nicely without AA, although I’m sure that the outlines are ok now. But Graphis2D.fill(Shape) is not exactly a font renderer though. I haven’t tried the X peers with the Java-only rasterizer yet. I will try this soon though.

Update:

Francis was so kind to quickly implement support for non-AA rendering. Here comes the comparison for rendering hinted text without AA. Left Sun, right Cairo (yes!):

This seems to confirm that the general hinting is mostly ok. The missing curve segments in the e and o are quite certainly to blame to Sun’s rasterizer. However, there are definitely small glitches in the hinting still, visible in the W, r and d glyphs.

Here are some more unsorted screenshots on my way to a hinting implementation:

A little accident:

Some glyph outlines with the original (red) and hinted (green) shapes magnified to show the grid-fit:

Again, the ‘e’ glyph, where hinting was a work in progress. I made this screenshot for debugging purposes. Notice how the middle horizontal stem got accidentally collapsed:

While working with this I stumbled over a bug in Classpath’s Cairo peers when trying to render a shape magnified. Is this abstract art? (This should have been the ‘e’ glyph above).

We finished the global feature analysis last time and now get into the local (outline-specific) feature analysis. As a first step we detect so called segments. A segment is a set of consecutive points that form a approx horizontal or vertical line. The detection of segments is not too complicated. Simply iterate over the points of an outline and find points that have an in or out direction close to one of the major directions (up,down,right,left). The deviation of the angle must not be > arctan(1/12). Then group consecutive points with the same direction into segments.

Where it gets interesting is, when segments get linked to each other. Every segment can have zero or one ‘opposite’ segment. To find these linked segments, we compare each segment with every other segment to see if they are sufficiently close to each other and have a certain overlap in their major direction. The outcome of this is that we can now easily detect stems and serifs. We have a stem segment when s1->link == s2 and s2->link == s1. OTOH, we have a serif segment when s1->link == s2 and s2->link != s1. Look at the following diagram, which shows a typical serif. Segment A is linked to segment B (because that’s closest to A). But Segment B is NOT linked to segment A. So the segment A is forming a serif. The same is true for segment D. OTOH, segment B and C are linked to each other. They are forming a stem. This information is important for the hinting process; serifs and stems have to be rendered at a certain span, and all serifs and stems in a text should be the same width usually.

BTW. This is a good time to give some credits. This hinting implementation has been developed by David Turner and Werner Lemberg of the FreeType project. I am only studying their code, preparing a(nother) paper and doing a presentation about it and adapting it to Java. I have to say that I am really impressed by this work of genius! If this interests you, the original paper has a nice high-level overview.

Last time we looked at the blue zones. The other characteristic property of Latin fonts are the standard stem widths. Stems are the (basically) horizontal and (basically) vertical lines in a glyph. I.e. the glyph for ‘l’ normally has one vertical stem. In order to render glyphs smoothly, it must be assured that all stems are ’snapped’ to approximately the same width (normally one pixel; unhinted glyphs tend to show 0 - 2 pixels instead).

So, in order to find out the standard width of the stems, we analyse the glyph for the character ‘o’ which proves to be very reliable for stem width detection. The diagram below shows how this glyph is represented as set of bezier points and control-points that ultimately span up the glyph.

Our algorithm first runs the local feature detection on this outline (explained later) which yields the segments of this glyph. Segments are sets of consecutive points that align approx. horizontally or vertically. The glyph ‘o’ below has 8 segments, each made up of 3 points. The local feature detection also ‘links’ pairs of segments to each other. Two linked segments form a stem. We have 4 stems in the ‘o’ glyph, which are highlighted in the diagram. Now it’s easy to get the standard stem widths, which is the distance between the segments that form the stems of our test glyph ‘o’.

BTW: If you don’t know what I’m talking about. I made two interesting screenshots that show how unhinted text is rendered. Left is without anti-aliasing (horrible) and right is with anti-aliasing (ok-ish but way to blurry). These screenshots are made with Classpath’s Java-only-TrueType implementation rendered with the Cairo backend.