HarfBuzz Study: Building the Indic Shaper
Behdad Esfahbod
October 2014
Back when I was at Red Hat, I was responsible for maintaining the text rendering stack on Linux desktop. Part of the job involved maintaining the text shaping engine, which is the piece of code that decides what to show on the screen, given a font and piece of Unicode text. While shaping sounds trivial for Latin and other simple scripts (you just stack individual letters next to each other), it is a much more complex process for written scripts like Arabic, or the scripts of India and South-East Asia (Devanagari, Bengali, Malayalam, Telegu, Khmer, Burmese, etc).
A recurring pain point was when the i18n at Red Hat reported bugs with the Indic shaper: a font they developed would render incorrectly given a sequence of characters, and they wanted me to fix the shaper to address that. I had not originally written the shaper. In fact, we had three shapers: in GNOME/Pango, KDE/Qt, and ICU. I mostly maintained one of them only, but had to keep things in sync with the other ones when possible. The Indic shaper I had to maintain was originally designed as a state machine. But as time went on and the original states deemed insufficient, crude “if” statements were added to fix things up. It was a mess beyond repair. It didn’t help that I understood little about the Indic script shaping logic. I had to fix this mess. I was already experimenting with rewriting layers below the shaper, in what became to be known as HarfBuzz, and rewriting all shapers in HarfBuzz came as a natural solution. How to do it to avoid creating the same mess was however not very clear.
Our shaping engines were based on OpenType, which is technology developed by Adobe and Microsoft. The script-specific parts of the specification were lightly documented in a “specification”, and the Microsoft implementation of them, Uniscribe, was infamous for its quirks and departures from the words of the specification. I knew enough about Unicode and OpenType to know exactly what to do in HarfBuzz for Latin and other simple scripts as well as Arabic and similar scripts. However, the Indic-like scripts were still a problem and I needed a concrete plan to tackle them. How I did that is the subject of the rest of this writeup. Around this time, I moved to Google, and picked up the Indic challenge more seriously.
I decided to start by studying and implementing Devanagari first, but with an outlook at being able to adapt the same shaper to handle all Indic-like scripts. As such, I started by studying everything Unicode and OpenType had to say about Devanagari. I then studied the three existing shapers, as well as a newer one I found in the wine Windows emulator software. Each implementation had a different design, advantages, and limitations. I learned a lot about what I needed for the job, and managed to put the pieces of the puzzle together enough to get a big picture of how the Indic shaping works. So I started designing my new implementation.
The Indic shaping starts with breaking text into clusters. The clusters follow a loose grammar that is specified in the spec. It wasn’t hard to see however that the spec leaves a lot of details unspecified, so I had to make sure my design was flexible enough to allow adjustments later. That is exactly why the Pango and ICU implementations failed: they had a hardcoded state machine in terms of tables, which was very hard to modify. The Qt and wine implementations on the other hand, open-coded the logic, skipping the formal grammar. That has its own limitations in that it was hard to verify the logic or extend it without forgetting about multiple corner cases. I knew what I needed. I had a grammar, so I needed a parser-generator so I could keep my grammar in a readable form and adjust in the most convenient source form. I didn’t want to settle for anything short of an excellent solution, so I spent a month trying out various solutions. I prototyped the grammar in antlr, bison, and flex. I tried parsing back to front instead of front to back. None of the solutions quite satisfied my needs. All three could do the parsing, but didn’t have the flexibility for input and output structures I needed. I searched some more, and I finally found ragel, which had all the flexibility I needed. The grammar that I wrote then is still at the core of HarfBuzz Indic shaper, and is as compact and readable as it can get. The parsing problem was solved.
With the parser under my belt, I put together the body of the shaper from scratch, according to my understanding of the specification. I used Unicode Character Database Indic datafiles to drive my state machine, instead of hardcoding character properties which is what ICU, Pango, and Qt implementations did. This gave me a significant edge in eventually supporting every Indic-like script (over 25 of them supported currently) with little effort.
I had a small prototype of a shaper now, and it was time to test it. I repurposed the test suite from Qt, and started fixing trivial pieces and learning how Indic shaping details work at the same time. Soon I found myself in a position that I questioned the test suite expectations and thought it might be wrong after all. I was stuck again. I had four implementations of the same concept, and they all disagreed at many many corner cases. I didn’t know how to move forward. At that point I had an aha moment: there is no point in adhering to a standard, OpenType in this case, if my code is not compatible with the most commonly used implementation, Uniscribe.
This awakening helped shape the mandate for HarfBuzz: produce the same results as Uniscribe, unless Uniscribe behavior didn’t make sense / was bogus and we could do a better job. A lot of the quirks in Uniscribe however, we decided to match, because we really want the same font and text combination to render the same on every platform, and we should move towards that goal.
Now I had a mandate. It was easy to use the mandate to arbitrate individual failures: if my shaper’s behavior matched Uniscribe, my results are correct and the test suite expectations have to be adjusted. Otherwise, it’s my bug and I’ll try to understand what Uniscribe is doing and replicate. However, I also knew that fixing one issue can open up another ten. My test suite of ~200 tests was far from enough to ensure I keep improving shaper quality over time. And adding new tests as I went on while useful, was not going to get me close to what I needed: an exhaustive test suite. So I set out to address that systematically.
To get there, I first developed a Uniscribe backend to HarfBuzz, such that I could use the same command-line tools (hb-view and hb-shape) to produce output from my shaper as well as Uniscribe shaper as long as I was building and running in a Windows environment. I managed to relax the final requirement by using the Uniscribe DLL from a real Windows installation under the wine emulator on Linux, allowing me to use my Linux-based workflow while comparing my shaper’s output to Uniscribe. And I wrote small tools to help diff the output from the two shapers in a meaningful way and to summarize failures.
With the test environment ready, I just needed test data. The nice thing about having a fully automated test suite like this is that 1. it does not require tagged test data. Ie. inputs to the test system do not include the correct output. And 2. there is no manual intervention, so the cost per test is negligible. Which means, I could afford millions of tests if I wanted to. I also figured out that sooner or later failures will come up that I have to ignore, for I cannot and do not want to match every quirk in Uniscribe exactly, just to the extent that it makes sense. With all these requirements in mind, I figured that what I really wanted was to test every single word on the web for correct rendering. While that sounds feasible at Google scale, I wanted to keep things simple to run (on my laptop), so I settled for all of Wikipedia instead: With help from a Roozbeh Pournader, we downloaded all of different languages of Wikipedia and produced a word-list per language, with accompanying word frequency data, and released this corpus.
It turns out, for many of the scripts we are interested in (Indic-like ones), we have to deal with a word list of around a million items or less to cover all of Wikipedia! That was great, because now I could run the entire test suite for, say, Hindi, and it would take 10 seconds to run and compare all my shaper results to that of Uniscribe, and summarize the number of failures. Then review the failures in a visual listing ordered by word frequency, find common patterns for failures, analyze them, come up with a possible fix, and rerun the test suite to see how it affects the number of failures. Does it fix what we wanted it to fix? Did it break other things? I could not only do this for one language at a time, but after making changes that had a broad effect, I could run every Indic-related language through the test suite again to see the effects of my change. It was extremely empowering. For the two years since we have use this test-driven methodology for all changes to the Indic-related shaping logic and has been able to constantly improve the quality of the shaper release after release. Mozilla even set up a cloud-based continuous-integration system testing the Wikipedia corpus against a wide variety of fonts, and they use this to make sure rolling their copy of HarfBuzz forward doesn’t regress their shaping.
Since then, this new HarfBuzz has rolled out to be used by both Firefox and Chrome on all platforms, as well as in Android, GNOME, LibreOffice, XeTeX, KDE, PlayStation, and other platforms, improving the mobile and web experience of hundreds of millions of users in India and South-East Asia among other places. According to Chrome developer Emil Eklund: “when Chrome Windows switched shaping from Uniscribe to HarfBuzz, it immediately saw a 4x speedup (of the entire page layout!) on international websites and we received zero complaints from users.” I believe that summarizes why I think this is the most impactful thing I made to date. I would not have been able to solve this problem without taking a systematic approach to understanding the problem, finding the right tools to attack it, and building an extensive test-driven development strategy.