I saw a TED video years ago about a guy who went about building his own toaster from scratch. It was a great amount of effort and research to build something that most people have in their kitchen. I was reminded of that video when I decided to build my own JPEG decoder. I would be creating something to solve a problem that others with more expertise had already solved but I would be learning something new along the way. Unlike building my own toaster, there was less risk of setting my home on fire.

Each image file format has pros and cons. Bitmaps are simple, load very quickly, and support a variety of bits-per-pixel but their file size is usually larger and they don't support alpha. PNG files support alpha and different qualities of the same image which made them popular years ago when Internet connections were much slower. JPEG files are great because they compress the image data and look better than PNG files when storing photographic images.

I had considered using the Developer's Image Library(DevIL) which supports a wide variety of image formats but the license would require me to provide all of the source code to my game engine with each game copy sold. This is the related portion of the license that concerned me:

For an executable, the required form of the "work that uses the Library" must include any data and utility programs needed for reproducing the executable from it.

Simple OpenGL Image Library(SOIL) is another great image library that supports a variety of image formats and is cross-platform. Strangely, SOIL doesn't support 1bpp bitmaps. I wrote my own bitmap loader a long time ago and supporting 1bpp was very simple. SOIL hasn't been updated since 2008 but it is public domain which makes it very attractive for my needs. I will need to spend more time with SOIL to determine if it's right for me. I have plans to update my rendering engine to support DirectX as well and I need to be sure the "OpenGL" part of SOIL won't hinder those plans.

Getting started with writing your own JPEG decoder is not hard. The ITU-T81 document linked below will make the process fairly easy in the beginning. The biggest difficulty from my experience is the step involving decoding the scan data. This step involves traversing binary data, matching the bits to Huffman codes, detecting Zero Run-Lengths, and building Minimum Coded Units. This is where the links below to the JPEG Wikipedia decoding steps and the Impulse Adventure page really saved the day. The ITU-T81 document is 186 pages and it contains everything you need but I found the information from Wikipedia and Impulse Adventure easier to absorb.

The great thing about the data format is that you can translate each MCU's samples into YCbCr values and then into a finalized block of RGB pixels even before the complete scan data has been processed. This is a great place to hand off converting each MCU's samples to a separate thread. Decoding scan data can be computationally expensive and any opportunities for speed gains should be tested.

After everything appeared to be working as expected, I began experimenting with large JPEGs. I was looking for ways to refactor the code to use less memory or improve performance. One test involved collecting the entire scan data, converting it to a binary string, and then trying to work with that instead of collecting small chunks of the scan data and processing it a bit at a time. This test revealed that a large JPEG took an incredible amount of time to decode. After collecting a few metrics the problem was clear. There was a spot where I was using the StartsWith() function in my string class and it was extremely slow when dealing with very large strings. It turns out I was trying to use IndexOf() and check if it returned zero, indicating the string to find was at the front. Using IndexOf() inside of StartsWith() was a bad idea because, even if the string being searched didn't start with the string we were looking for, it would still scan the rest of the string trying to find the first instance. I double checked the EndsWith() function too just to be sure that function wasn't written in a similar fashion. After some minor changes to my string class, the decode test was back to being fast again and I had some new test cases for my string class.