GIF image decoder
28th April 2025
This is a uLisp program to load a GIF image from memory or from an SD card, and display it on a TFT or OLED display:
The GIF image decoder takes about 9500 Lisp objects, and will run on boards with about 15000 Lisp objects, such as those based on the ATSAMD51, nRF52840, RP2040, RP2350, or ESP32-S3. I tested the program on the RP2040-based PicoCalc Lisp Machine shown above.
Here's the complete program: GIF image decoder program.
Introduction
When I was looking for Lisp applications to try out on the PicoCalc I remembered a GIF decoder I wrote a while ago [1], and tried porting it to the PicoCalc. In the process I ended up rewriting it to make it more elegant, and to ignore an unrecognised GIF extension that caused problems with some images I tried.
The GIF format
The GIF image format is ideal for storing images to be displayed on a small TFT or OLED display. It uses the LZW compression algorithm which provides efficient compression of many types of images, and the code to decode LZW-compressed images can be made relatively compact. It's also well supported by image editors.
Displaying a GIF image
To display a GIF image from SD card call:
(display-gif filename)
You can display a GIF image at a particular screen position by giving the coordinates; for example:
(display-gif filename x y)
LZW compression
The GIF format treats the image as a linear stream of pixel colour values. The LZW compression it uses works by finding a sequence of pixels it has already encountered, and it encodes each sequence as a variable-length code of from 3 to 12 bits. These codes are then output as a continuous stream of bits.
Decoding a GIF requires the decoder to divide the input stream into codes containing the correct number of bits. These codes are then looked up in a 4096-element array, to translate them into the appropriate sequence of one or more pixels represented by that code.
It would be very memory intensive if we had to store the complete pixel sequence corresponding to every code in the table. Fortunately, every sequence is equivalent to an earlier sequence extended by the addition of one pixel. We can therefore represent the sequence as a pointer to the earlier sequence in the table, plus the additional pixel. Each entry in the lookup table therefore needs to store a 12-bit pointer to an earlier entry in the table, plus an 8-bit byte for the colour of the additional pixel in the sequence.
The clever thing about LZW compression is that the lookup table doesn't need to be included with the GIF image, because it is reconstructed dynamically as the code values are read in from the input stream. For a full description of how the GIF format works see the Wikipedia page [2]. I also got a lot of help from articles by Joshua Davies [3] [4] and Larry Bank [5].
Colour table
A GIF image can contain a colour table of up to 256 colours, so there also needs to be a 256-byte array to store this colour table. Each colour is defined by three bytes, giving the colour's R, G, and B components. Since this GIF decoder is intended for displaying images on a TFT display with a 5-6-5 colour space, each colour is encoded into a single entry in the table.
Restrictions
This decoder doesn't support: the older GIF87a format, animated GIFs, local colour tables, transparency, or interlaced GIFs.
The program
The GIF decoder
Each element in the compression table used by the GIF decoder is defined by a two-dimensional array table, defined with:
(let ((table (make-array '(4096 2))))
In each table entry (aref table n 0) is a pointer to an earlier entry, and (aref table n 1) is the pixel colour of the last pixel in the sequence encoded by this table entry.
Reading the bit stream
The problem of reading variable-length codes from the input file is handled by the routine get-n-bits:
(defun get-n-bits (n str)
(loop
(unless (< *nbuf* n) (return))
;; Enough left in block?
(when (zerop *block*)
(setq *block* (read-byte str)))
(setq *buf* (logior (ash (read-byte str) *nbuf*) *buf*))
(decf *block*)
(incf *nbuf* 8))
(let ((result (logand *buf* (1- (ash 1 n)))))
(setq *buf* (ash *buf* (- n)))
(decf *nbuf* n)
result))
A call to get-n-bits returns the next n-bit code from the file. It maintains a bit buffer in the global variable *buf*, and *nbuf* specifies how many significant bits are still available in *buf*. If there are fewer than n bits in the buffer, read-byte is called to read in another 8 bits and append them to the end of the buffer.
A further complication is that the bit stream is divided into blocks of up to 255 bytes, with each block preceded by a length byte. The global variable *block* stores the number of bytes remaining in the current block. If this reaches zero, it is reset by reading in another length byte.
Getting the first character of a sequence
Given a compression table element c, first-pixel follows the pointers to find the first pixel colour in the sequence it represents:
(defun first-pixel (table c)
(let ((rest (aref table c 0))
(this (aref table c 1)))
(cond
((= -1 rest) this)
(t (first-pixel table rest)))))
Outputting a sequence
The routine plot-sequence plots the sequence of pixels represented by the compression table element c.
The function plot-sequence could be defined recursively as:
(defun plot-sequence (table c)
(let ((rest (aref table c 0))
(this (aref table c 1)))
(unless (= -1 rest) (plot-sequence table rest))
(plot this)))
This effectively finds the first pixel in the sequence, by following the pointers back until a -1 pointer is reached, then finds the next pixel in the sequence, and so on, ending with the last pixel, (aref table c 1).
Although this version works perfectly, Iong sequences could require a lot of stack space. Fortunately, it's possible to write it to avoid the need for recursion altogether, taking advantage of the fact that we can plot pixels in any order:
(defun plot-sequence (table c)
; Measure backtrack
(let ((rest c) (i 0))
(loop
(when (= rest -1) (return))
(setq rest (aref table rest 0))
(incf i))
; Plot backwards
(setq *pixel* (+ *pixel* i -1))
(setq rest c)
(loop
(when (= rest -1) (return))
(draw-pixel (+ *x* (mod *pixel* *width*))
(+ *y* (truncate *pixel* *width*))
(aref colour-table (aref table rest 1)))
(decf *pixel*)
(setq rest (aref table rest 0)))
(setq *pixel* (+ *pixel* i 1))))
This first measures how long the sequence is, in i, by counting the number of steps until a -1 pointer is reached. It then plots the pixels in reverse order, starting with the last one, thus avoiding the need for recursion.
Skipping bytes
The function skip-n-bytes is called to skip a series of unneeded bytes in the input file:
(defun skip-n-bytes (n str) (dotimes (x n) (read-byte str)))
Power of two test
The function power-2-p checks that its argument is a power of two. It is used to increase the bit length of codes being read when the size of the compression table reaches a power of two:
(defun power-2-p (x) (zerop (logand x (1- x))))
Displaying the GIF image
Finally, here's the definition of display-gif:
(defun display-gif (filename &optional (x 0) (y 0))
(with-sd-card (str filename)
(skip-n-bytes 6 str) ; id and version
(let* ((width (+ (read-byte str) (ash (read-byte str) 8)))
(height (+ (read-byte str) (ash (read-byte str) 8)))
(fld (read-byte str))
(bk (read-byte str))
(aspect (read-byte str))
(colbits (max (1+ (logand fld 7)) 2))
(colours (ash 1 colbits))
(colour-table (make-array colours)))
(setq *x* x *y* y)
(setq *width* width)
(setq *pixel* 0)
;; Initialise colour table
(dotimes (colour colours)
(setf (aref colour-table colour)
(rgb (read-byte str) (read-byte str) (read-byte str))))
;; Make and initialise the compression table
(let ((table (make-array '(4096 2))))
(dotimes (n colours) (setf (aref table n 0) -1 (aref table n 1) n))
;; Parse blocks
(loop
(let ((header (read-byte str)))
(case header
;; Parse image descriptor
(#x2c (image-descriptor str colbits colours table))
;; Skip extension block
(#x21 (extension-block str))
;; Terminating byte
(#x3b (return))
(t (error "Unknown header ~x" header)))))))))
The function display-gif first reads in the GIF header, which specifies the width and height of the image, and the global colour table. If the image has c colours it then initialises the first c entries in the compression table, table, with the corresponding colour index, c. A further two entries are reserved for two special codes: clear, which resets the compression table if it is full, and end which indicates the end of the image block. The first free entry in the table is therefore at c+2.
The function display-gif then checks for three types of block: an image block, prefixed by 0x2C, an extension block prefixed by 0x21 which is ignored, and a terminating byte 0x3B that ends the file.
Image descriptor block
Here's the definition of image-descriptor:
(defun image-descriptor (str colbits colours table)
(let* ((bits (1+ colbits))
(end (1+ colours))
(free (1+ end))
(clr colours)
stop)
(skip-n-bytes 10 str)
(setq *nbuf* 0 *buf* 0 *block* 0)
(let ((code -1) (last -1))
(loop
(setq last code)
(setq code (get-n-bits bits str))
(cond
((= code clr)
(setq free (1+ end))
(setq bits (1+ colbits))
(setq code -1))
((= code end)
(setq stop t))
((= last -1)
(plot-sequence table code))
((<= code free) ; Found in table
(when (< free 4096)
(setf (aref table free 0) last)
(setf (aref table free 1)
(first-pixel table
(if (= code free) last code)))
(incf free)
(when (and (power-2-p free) (< free 4096)) (incf bits)))
(plot-sequence table code)))
(when stop (return)))
(unless (zerop (read-byte str)) (error "Bad block end")))))
In the image block the most important variables are free, that specifies the index of the next free element in the compression table, and bits, that specifies the current size of the variable-length codes.
The compression table is extended as follows, based on each code that is read in from the input file:
- If code < free the code is already in the table. A new entry is added to the table consisting of a pointer to the last sequence, followed by the first pixel in the current sequence.
- If code = free the code is not already in the table. A new entry is added to the table consisting of a pointer to the last sequence, followed by the first pixel in the last sequence.
In each case the sequence corresponding to code is output.
This continues until either a clear code is encountered, in which case the compression table is cleared and processing continues, or an end code is encountered, in which case the image is finished.
Extension block
GIF files often contain extension blocks, not relevant to simply displaying the GIF, and these are skipped by the function extension-block:
(defun extension-block (str)
(let ((gce (read-byte str)))
(case gce
(#xff
(let ((length (read-byte str)))
(skip-n-bytes length str)
;; Go past extension
(loop
(let ((length (read-byte str)))
(when (zerop length) (return))
(dotimes (x length) (read-byte str))))))
(t
(let ((length (read-byte str)))
(skip-n-bytes (1+ length) str))))))
Clear code
When the lookup table is full the GIF being decoded normally sends a clear code, causing the table to be cleared and built from scratch. This is the approach taken by most GIF programs, such as Photoshop.
An alternative, described in the GIF89a specification [6], is for the GIF not to send a clear code when the table is full, but just to continue to use the existing table for subsequent processing. This can sometimes result in a smaller file. The GIF Decoder supports GIFs encoded in this way.
Here is an example. The GIF on the left is encoded in the conventional way, with a clear code when the table is full, and it's 8750 bytes. The one on the right looks identical, but doesn't clear the table, and is 7833 bytes:
Resources
Here's the complete program: GIF image decoder program.
Here's the image plotted in the photograph at the start of the article: cards.gif.
- ^ A minimal GIF decoder on Lispology.
- ^ GIF on Wikipedia.
- ^ How LZW (GIF) Compression Works on Command Line Fanatic.
- ^ Inside the GIF File Format on Command Line Fanatic.
- ^ A Low Memory GIF Decoder on Follow me down the optimization rabbit hole.
- ^ GIF89a Specification on w3.org.