EXPLAIN EXTENDED

As readers of my blog know, SQL is a wonderful tool for graphics processing. You can use it to draw Mandelbrot sets, table game boards and even snowflakes, all in a single query.

As I was preparing this year's entry, I found myself all out of ideas. What image shall we be generating this year? A cat? A pig? A winter scenery? It's all doable in SQL (or course), however I couldn't make myself pick anything in particular. And frankly speaking, even with all the power of SQL at my hands, I'm a lousy artist.

Then an idea struck me. Why try and create art when there's so many excellent artists out there on the Internet, whose work I could just steal put to fair use? And my phone camera makes better pictures than I could ever aspire to create myself.

Images that come out of the camera or from the Internet are all digital and compressed. Digital is of course a good thing when it comes to computer processing, but compressed is a challenge. And challenges is something I like.

So this year, we will be creating a GIF decoder in SQL.

GIF is one of the earliest compressed image storage formats, famous for its early adoption by the World Wide Web and for being named with an acronym no one can agree how to pronounce correctly. At its core lies LZW, a lossless compression algorithm which uses dictionary tables to encode repeating patterns of data. GIF is not the best format out there, of course, and it has fallen out of use in the last years (or even decades). Its algorithm, however, is not particularly memory or CPU intensive and as the image compression algorithms go, its implementation is quite simple. In other words, it makes a perfect SQL exercise.

To become familiar with GIF, I used an excellent GIF tutorial called What's in a GIF? by Eric. S Raymond and Mike Flickinger. This tutorial is built around explanation of contents of a tiny sample GIF file:

and this file is what we will be using during the first part of our journey.

Let's get started!