Topics

► Games

► Sound & Music

► Watches & Clocks

► GPS

► Power Supplies

► Computers

► Graphics

► Thermometers

► Wearables

► Test Equipment

► Tutorials

► Libraries

► PCB-Based Projects

By processor

AVR ATtiny

► ATtiny10

► ATtiny2313

► ATtiny84

► ATtiny841

► ATtiny85

► ATtiny861

► ATtiny88

AVR ATmega

► ATmega328

► ATmega1284

AVR 0-series and 1-series

► ATmega4809

► ATtiny1604

► ATtiny1614

► ATtiny3216

► ATtiny3227

► ATtiny402

► ATtiny404

► ATtiny414

► ATtiny814

AVR DA/DB-series

► AVR128DA28

► AVR128DA32

► AVR128DA48

► AVR128DB28

ARM

► ATSAMD21

► RP2040

About me

  • About me
  • Twitter
  • Mastodon

Feeds

RSS feed

Minimal GIF Decoder

15th December 2022

This is a GIF image decoder designed to allow GIF images to be read and displayed by a small microcontroller:

TinyGIFDecoder.jpg

Using the Minimal GIF Decoder to display a slide show of GIF images from the flash memory on an AVR128DA28.

It's useful if you want to decode GIF images from the flash memory on the processor, or from an SD card, and display them on a TFT or OLED display. The Minimal GIF Decoder takes about 1K bytes of program memory, and requires just over 12K bytes of RAM, so it will run on any processor with at least 16K bytes of RAM. I used an AVR128DA28.

As a demonstration of the GIF encoder I've included a slide-show application that displays a sequence of different images read from the processor's flash memory. I also give details of how to display GIF images from an SD card.

Update: Now supports GIFs encoded without sending a clear code; see Update.

Introduction

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.

I needed a GIF display routine for a project and couldn't find a GIF decoder aimed at microcontrollers with a relatively small amount of RAM, so I decided to try and write one. The result is a decoder that uses just over 12K bytes, and is therefore suitable for AVR processors with at least 16K bytes of RAM such as the AVR128DA28 or ATmega1284P. It will also run on 32-bit processors such as the ATSAMD21 and ATSAMD51, and I include an example of it running on the ATSAMD51-based Adafruit PyBadge.

These processors have plenty of flash, so you could store several compressed GIF images in flash and display them using the decoder, for a stand-alone slide-show project. Alternatively you can read GIF images from an SD card and display them.

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 table, 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 can be 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 [1]. I also got a lot of help from articles by Joshua Davies [2] [3] and Larry Bank [4].

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 TFT displays with a 5-6-5 colour space, we can reduce each entry in the colour table to 16 bits.

Memory requirement

The total RAM requirement is therefore 4096 x 3 + 256 bytes, or just over 12Kbytes. There are ways of reducing the RAM requirements with a bit more programming, but to keep the decoder as simple as possible I've avoided these; see Further suggestions for details of how these could work.

The compression table and colour table are allocated as fixed arrays, and the program doesn't use malloc for dynamic memory allocation.

Restrictions

This decoder doesn't support: the older GIF87a format, animated GIFs, local colour tables, transparency, interlaced GIFs, or other extensions. If it encounters an unknown format it flashes an LED with an error code. However it should work with standard GIFs created by a range of image editors, and I've tested it with images from several editors.

The circuit

Here's the circuit I used to develop the Minimal GIF Decoder:

GIFDecoder.gif

Circuit used to demonstrate the Minimal GIF Decoder on an AVR128DA28.

I built it on a couple of mini breadboards [5]. For the processor I used an AVR128DA28 in a PDIP package, but the AVR128DB28 would be equally suitable.

For the display I used the Adafruit 160x120 1.8" colour TFT display [6], but it should work with any display. The program includes settings for the other displays supported by the graphics library; uncomment the one you want to use. Note that on this display the LITE pin must be connected to Vcc for the backlight to work.

I also included an LED on the LED_BUILTIN output to allow the program to signal errors. 

The program

To drive the TFT display I used my Compact TFT Graphics Library, which uses standard Arduino SPI calls. The Arduino display provides an SD card socket, and you can use the same SPI interface to read GIF images from the SD card. I've removed routines from my library that are not needed by this application.

Alternatively you could also use my Tiny TFT Graphics Library 2, which uses direct bit manipulations on the AVR128DA28 port to drive the display as fast as possible. Both TFT libraries supports a wide range of displays; uncomment the parameters for the display you want to use.

The GIF decoder

Each element in the compression table used by the GIF decoder is defined by a struct, cell_t:

typedef struct {
  int16_t rest;
  uint8_t last;
} cell_t;

In each table entry rest is a pointer to an earlier entry, and last is the pixel colour of the last pixel in the sequence encoded by this table entry.

Here's the definition of the compression table array, and the GIF colour table:

cell_t Table[4096];
uint16_t ColourTable[256];

Reading the bit stream

The problem of reading variable-length codes from the input file is handled by the routine GetNBits():

int GetNBits (int n) {
  while (Nbuf < n) {
    if (Block == 0) Block = ReadByte();
    Buf = ((uint32_t)ReadByte() << Nbuf) | Buf;
    Block--; Nbuf = Nbuf + 8;
  }
  int result = ((1 << n) - 1) & Buf;
  Buf = Buf >> n; Nbuf = Nbuf - n;
  return result;
}

A call to GetNBits(n) returns the next n-bit code from the file. This 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, ReadByte() 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, FirstPixel() follows the pointers to find the first pixel colour in the sequence it represents:

uint8_t FirstPixel (int c) {
  uint8_t last;
  do {
    last = Table[c].last;
    c = Table[c].rest;
  } while (c != -1);
  return last;
}

Outputting a sequence

The routine PlotSequence() plots the sequence of pixels represented by the compression table element c.

PlotSequence() could be defined recursively as:

void PlotSequence (int c) {
  int rest = Table[c].rest;
  if (rest != -1) PlotSequence(rest);
  fore = ColourTable[Table[c].last];
  PlotPoint (Pixel%Width, ysize - Pixel/Width - 1);
  Pixel++;
}

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, Table[c].last.

Although this version worked perfectly, I was a bit unhappy about using it as long sequences could require a lot of stack space. Fortunately, I found a way of writing it that avoids the need for recursion altogether, taking advantage of the fact that we can plot pixels in any order:

void PlotSequence (int c) {
  // Measure backtrack
  int i = 0, rest = c;
  while (rest != -1) {
    rest = Table[rest].rest;
    i++;
  }
  // Plot backwards
  Pixel = Pixel + i - 1;
  rest = c;
  while (rest != -1) {
    fore = ColourTable[Table[rest].last];
    PlotPoint (Pixel%Width, ysize - Pixel/Width - 1);
    Pixel--;
    rest = Table[rest].rest;
  }
  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 routine SkipNBytes() is called to skip a series of unneeded bytes in the input file:

void SkipNBytes (int n) {
  for (int i=0; i<n; i++) ReadByte();
}

Power of two test

The routine Power2() 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:

boolean Power2 (int x) {
  return (x & (x - 1)) == 0;
}

Error checking

The routine Error() flashes the LED_BUILTIN a specified number of times to signal an error:

void Error (int err) {
  for (int i=0; i<err; i++) {
    digitalWrite(LED_BUILTIN, HIGH); delay(200);
    digitalWrite(LED_BUILTIN, LOW); delay(200);
  }
  for(;;);
}

The following errors can be indicated:

Flashes Error
2 Invalid GIF file, or file not found on SD card
3 Transparency/local colour table not supported
4 Last byte of a block is not zero

Displaying the GIF image

Finally, here's the definition of ShowGif():

void ShowGif (const uint8_t *filename) {
  OpenFile(filename);
  const char *head = "GIF89a";
  for (int p=0; head[p]; p++) if (ReadByte() != head[p]) Error(2);
  int width = ReadInt();
  ReadInt(); // Height
  uint8_t field = ReadByte();
  SkipNBytes(2); // background, and aspect
  uint8_t colbits = max(1 + (field & 7), 2);
  int colours = 1<<colbits;
  int clr = colours;
  int end = 1 + colours;
  int free = 1 + end;
  uint8_t bits = 1 + colbits;
  Width = width;
  Pixel = 0;

  // Parse colour table
  for (int c = 0; c<colours; c++) {
    ColourTable[c] = Colour(ReadByte(), ReadByte(), ReadByte());
  }
  
  // Initialise table
  for (int c = 0; c<colours; c++) {
    Table[c].rest = -1; Table[c].last = c;
  }
  
  // Parse blocks
  do {
    uint8_t header = ReadByte();
    if (header == 0x2C) { // Image block
      SkipNBytes(8);
      if (ReadByte() != 0) Error(3); // Not interlaced/local
      SkipNBytes(1);
      Nbuf = 0;
      Buf = 0;
      Block = 0;
      boolean stop = false;
      int code = -1, last = -1;
      do {
        last = code;
        code = GetNBits(bits);
        if (code == clr) {
          free = 1 + end;
          bits = 1 + colbits;
          code = -1;
        } else if (code == end) {
          stop = true;
        } else if (last == -1) {
          PlotSequence(code);
        } else if (code <= free) {
          if (free < 4096) {
            Table[free].rest = last;
            if (code == free) Table[free].last = FirstPixel(last);
            else Table[free].last = FirstPixel(code);
            free++;
            if (Power2(free) && (free < 4096)) bits++;
          }
          PlotSequence(code); 
        }
      } while(!stop);
      if (ReadByte() != 0) Error(4);
    } else if (header == 0x21) { // Extension block
      SkipNBytes(1); // GCE
      int length = ReadByte();
      SkipNBytes(1 + length);
    } else if (header == 0x3b) { // Terminating byte
      CloseFile();
      return;
    }
  } while (true);
}

ShowGif() 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.

ShowGif() 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.

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.

Displaying GIF images from program memory

To demonstrate the Minimal GIF Decoder the flash slide-show version of the program displays a sequence of GIF images from the AVR128DA28's flash memory. The following four sample 160x128 images are provided:

Image Colours Size (bytes) Description
cards2_gif 2 1324 Six monochrome playing cards
cards8_gif 8 2232 Six colour playing cards
flags32_gif 32 2348 Flags of twelve countries
logo256_gif 256 8569 Technoblogy logo

The uncompressed size of a 160x128 image is 160x128x2 or 40960 bytes, so for these images the GIF compression reduces the size by a factor of between 5 and 30. On an AVR128DA28 you could fit approximately 40 images with a size of 3 Kbytes.

The images take about four seconds to load on a 24MHz AVR128DA28. If you don't want to show the progressive loading you could use a spare I/O line to toggle the backlight LITE input off while loading.

Incorporating your own GIF images

On a Mac or Unix computer you can dump a GIF image in a C-friendly text format using the built-in xxd command in a Terminal window:

  • Copy the GIF image file to your home directory.
  • Open the Terminal application.
  • Type the following command, substituting the name of your GIF file:
xxd -i cards.gif

The -i parameter tells xxd to output the data in C include format, and the output will look something like:

unsigned char cards8_gif[] = {
  0x47, 0x49, 0x46, 0x38, 0x39, 0x61, 0xa0, 0x00, 0x80, 0x00, 0xa2, 0x00,
  0x00, 0x00, 0xff, 0xff, 0xff, 0x00, 0xff, 0xbd, 0xbd, 0xbd, 0xff, 0xff,
  ...
  0xb7, 0x6d, 0x82, 0x31, 0x2d, 0xfb, 0xdb, 0x4e, 0x48, 0x00, 0x00, 0x3b
};
unsigned int cards8_gif_len = 2232;

The first six bytes should be the GIF header bytes, ASCII "GIF89a", and the last byte should be the file end byte 0x3b.

Copy the listing, excluding the last line, and paste it into the program file. Add PROGMEM to the first line by changing it to:

const uint8_t cards8_gif[] PROGMEM = {

This ensures that the data is stored in program memory on the chip.

You can now display the file by calling ShowGif() with the name of the data array; for example:

ShowGif(cards8_gif);

Displaying GIF images from an SD Card

Most of the Adafruit displays include an SD card socket, and you can use the Minimal GIF Decoder to display GIF images from an SD card.

Use the SD card version of the Minimal GIF Decoder, and display images by calling ShowGif() with the filename, such as:

ShowGif("cat.gif");

Compiling the program

Compile the program using Spence Konde's Dx Core on GitHub. Choose the AVR DA-series (no bootloader) or AVR DB-series (no bootloader) option as appropriate under the DxCore heading on the Board menu. Check that the subsequent options are set as follows (ignore any other options):

Chip: "AVR128DA28" or "AVR128DB28"
Clock Speed: "24 MHz internal"

Then upload the program to the processor on the breadboard using a UPDI programmer connected to the GND, +5V, and UPDI pins.

The recommended option is to use a USB to Serial board, such as the SparkFun FTDI Basic board [7], or a USB to Serial cable [8], connected with a 4.7kΩ resistor as follows:

SerialUPDIProgrammer.gif

  • Set Programmer to the first of the "SerialUPDI - 230400 baud" options.
  • Select the USB port corresponding to the USB to Serial board in the Port menu.
  • Choose Upload from the Arduino IDE Tools menu to upload the program.

The Arduino IDE gives a low memory warning because this program uses slightly more than 75% of the RAM, but you can ignore this.

Other processors

I've also tested the Minimal GIF Decoder running a slide show on an Adafruit PyBadge [9], which is based on the ATSAMD51:

PyBadgeSlideShow.jpg

Using the Minimal GIF Decoder to display a slide show of GIF images on an Adafruit PyBadge.

Resources

Here's the Minimal GIF Decoder with a slide-show from flash: Minimal GIF Decoder Flash Version.

And here's the version that displays GIF images from an SD card: Minimal GIF Decoder SD Card Version.

Here's the version for the Adafruit PyBadge/PyGamer: Minimal GIF Decoder PyBadge Version.

Or get them all from GitHub: https://github.com/technoblogy/minimal-gif-decoder.

Further suggestions

The RAM requirement could be reduced, at the cost of slight extra complexity, by packing each pair of 12-bit pointers in the compression table into three bytes. This would reduce the total size to 10K bytes.

If your application needs at most 16-colour GIFs you could represent each pixel colour with four bits, and so fit each table entry into two bytes, reducing the RAM requirement further to 8K bytes.

If you can think of any other ways to reduce the RAM requirement please let me know.

Update

4th January 2023: 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 [10], is for the GIF not to send a clear code when the table is full, and just to use the table as it is for subsequent processing. This can sometimes result in a smaller file. I've updated the Minimal GIF Decoder to support GIFs encoded in this way.

Here are some examples. The GIF on the left is encoded in the conventional way, with a clear code when the table is full, and is 8750 bytes. The one on the right doesn't clear the table, and is 7833 bytes:

EllipseC.gif    EllipseN.gif


  1. ^ GIF on Wikipedia.
  2. ^ How LZW (GIF) Compression Works on Command Line Fanatic.
  3. ^ Inside the GIF File Format on Command Line Fanatic.
  4. ^ A Low Memory GIF Decoder on Follow me down the optimization rabbit hole.
  5. ^ Breadboard - Mini Modular on SparkFun.
  6. ^ 1.8" Colour TFT Display with MicroSD Breakout on Adafruit.
  7. ^ SparkFun FTDI Basic Breakout - 5V on Sparkfun.
  8. ^ FTDI Serial TTL-232 USB Cable on Adafruit.
  9. ^ Adafruit PyBadge on Adafruit.
  10. ^ GIF89a Specification on w3.org.

Next: Number Maze Game

Previous: Lisp Star


blog comments powered by Disqus