I rewrote Firefox’s BMP decoder

Recently I’ve been deliberately working on some areas of Firefox I’m unfamiliar with, particular relating to graphics. This led me to rewriting Firefox’s BMP decoder and learn a number of interesting things along the way.

Image decoding

Image decoding is basically the process of taking an image encoded in a file and extracting its pixels. In principle it’s simple. You start by reading some information about the image, such as its size and colour depth, which typically comes in some kind of fixed-size header. Then you read the pixel data, which is variable-sized.

This isn’t hard if you have all the data available at the start. But in the context of a browser it makes sense to decode incrementally as data comes in over the network. In that situation you have to be careful and constantly check if you have enough data yet to safely read the next chunk of data. This checking is error-prone and tends to spread itself all over the image decoder.

For this reason, Seth Fowler recently wrote a new class called StreamingLexer that encapsulates this checking and exposes a nice state-based interface to image decoders. When a decoder changes state (e.g. it finishes reading the header) it tells StreamingLexer how many bytes it needs to safely enter the next state (e.g. to read the first row of pixels) and StreamingLexer won’t return control to the decoder until that many bytes are available.

Another consideration when decoding images is that you can’t trust them. E.g. an image might claim to be 100 x 100 pixels but actually contain less data than that. If you’re not careful you could easily read memory you shouldn’t, which could cause crashes or security problems. StreamingLexer helps with this, too.

StreamingLexer makes image decoders simpler and safer, and converting the BMP decoder to use it was my starting point.

The BMP format

The BMP format comes from Windows. On the web it’s mostly used on the web for favicons though it can be used for normal images.

There’s no specification for BMP. There are eight in-use versions of the format that I know of, with later versions mostly(!) extending earlier versions. If you’re interested, you can read the brief description of all these versions that I wrote in a big comment at the top of nsBMPDecoder.cpp.

Because the format is so gnarly I started getting nervous that my rewrite might  introduce bugs in some of the darker corners, especially once Seth told me that our BMP test coverage wasn’t that good.

So I searched around and found Jason Summers’ wonderful BMP Suite, which exercises pretty much every corner of the BMP format. Version 2.3 of the BMP Suite contains 57 images, 23 of which are “good” (obviously valid), 14 of which are “bad” (obviously invalid) and 20 of which are “questionable” (not obviously valid or invalid). The presence of this last category demonstrates just how ill-specified BMP is as a format, and some of the “questionable” tests have two or three reference images, any of which could be considered a correct rendering. (Furthermore, it’s possible to render a number of the “bad” images in a reasonable way.)

This test suite was enormously helpful. As well as giving me greater confidence in my changes, it immediately showed that we had several defects in the existing BMP decoder, particular relating to the scaling of 16-bit colors and an almost complete lack of transparency handling. In comparison, Chrome rendered pretty much all the images in BMP suite reasonably, and Safari and Edge got a few wrong but still did better than Firefox.

Fixing the problems

So I fixed these problems as part of my rewrite. The following images show a number of test images that Firefox used to render incorrectly; in each case a correct rendering is on the left, and our old incorrect rendering is on the right.

bad-bmp-2 bad-bmp-3 bad-bmp-4 bad-bmp-5

It’s clear that the old defects were mostly related to colour-handling, though the first pair of images shows a problem relating to the starting point of the pixel data.

(These images are actually from an old version of Firefox with version 2.4 of BMP Suite, which I just discovered was released only a few days ago. I just filed a bug to update the copy we use in automated testing. Happily, it looks like the new code does reasonable things with all the images added in v2.4.)

These improvements will ship in Firefox 44, which is scheduled to be released in late January, 2016. And with that done I now need to start thinking about rewriting the GIF decoder

11 Responses to I rewrote Firefox’s BMP decoder

  1. Thank you for having properly checked that the BMP test suite you added had a license that allowed it and that we’re fine with 🙂

  2. Peter Kasting

    Howdy fellow BMP decoder author! I wrote Chrome’s decoder from scratch (as well as the ICO decoder), and continue to be its maintainer.

    Thanks for the link to that test suite, which I’ve not seen before. You might also look at http://pxd.me/dompdf/www/test/image_bmp.html . There’s at least one other suite I’ve used which has some good OS/2 BMPs, but I can’t find it now. I also found http://sourceforge.net/projects/bmptestsuite/files/bmptestsuite/bmptestsuite-0.9/ but have not downloaded it to look at its coverage.

    I’d like to find some Huffman 1D images; that’s the only major compression method Chrome doesn’t support at this point.

    Be careful with alpha; as far as I can tell, there’s basically no way to handle it that doesn’t break at least _some_ images on the web, so it’s really a matter of picking what you want to break. If you haven’t, you might want to read through Chrome’s BMP decoder comments ( https://chromium.googlesource.com/chromium/src/+/master/third_party/WebKit/Source/platform/image-decoders/bmp/BMPImageReader.cpp ) to see if there are any interesting things we do that you haven’t already considered.

    I’m pretty proud of the Chrome decoder; at least as of when I wrote it it was by far the most comprehensive BMP decoder in a web browser. Hopefully with your rewrite that is no longer true, or won’t be true soon 🙂

    • I was curious so I read your code. It is extremely clear and well-written! If more code was written as cleanly, my job would be far less painful. Great job!

  3. With the intent to include more of the code in Firefox, I think there was once floated the idea of rewriting the BMP decoder in Rust (probably in a Servo meeting).
    How about making the GIF rewrite in Rust?

  4. This is pretty cool! I wish our Rust-in-Firefox story had been farther along so that you could have written this in Rust instead, but having a good test suite will certainly make that more viable in the future.

  5. Thanks for your work! Test-driven improvement of pieces of a huge codebase FTW

  6. Neil Rashbrook

    I think your screenshot is a bit misleading since even your latest code still renders some of those test bitmaps incorrectly; in fact, comparing with Firefox 3, I could only find eight bitmaps with corrected rendering, one whose rendering is less wrong, plus five (of which three “not confirmed correct”) that trunk code now correctly refuses to render. Trunk code also now attempts to render six of the “invalid” bitmaps.

    • Nicholas Nethercote

      Which images does Nightly render incorrectly?

      I got the screenshots from Firefox 42. It’s possible that Firefox 3 gives different results.

      • Neil Rashbrook

        Sorry for misreading your post; although I’d checked that the build I was using had your first patch I hadn’t noticed that there were two other bugs and it turns out that I was missing one.

  7. Goes to show there’s always room for improvement. Thanks for the rewrite. Where do I send the beer? =)