Eine GIF-Datei decodieren

1. Grundlagen

Ein GIF-Bild speichert für jedes Pixel keine Farbe, sondern eine Nummer. Welche Farbe zu welcher Nummer gehört, steht einmal in einer Farbtabelle am Anfang der Datei, mit höchstens 256 Einträgen. Das kennst du aus PixelRAM: Im Modus pixel_indexed8 ist jedes Pixel eine Nummer in der Palette. Ein GIF passt deshalb genau in diesen Modus.

Die Nummern der Pixel sind mit LZW komprimiert, benannt nach Abraham Lempel, Jacob Ziv und Terry Welch. Während der Decoder liest, baut er sich eine Tabelle von Pixelfolgen, die schon einmal vorkamen, und genau dieselbe Tabelle hat vorher der Encoder gebaut. Mitgeschickt wird die Tabelle nie. Wie das geht, ist das Herzstück dieses Labors.

Das Format ist in einem einzigen Text beschrieben, den die Firma CompuServe 1990 auf der Schreibmaschine verfasst hat: der Spezifikation GIF89a. Sie ist gut lesbar und erstaunlich kurz. Die Diagramme der Blöcke auf dieser Seite stammen von dort, und unter jeder Überschrift steht, wo der Block in der Spezifikation beschrieben ist.

2. Vorbereitung

Die PixelRAM-Vorlage

Dein Decoder ist ein Programm für PixelRAM. Hast du Echtzeitgrafik mit C schon bearbeitet, öffne einfach den Ordner /workspace/pixelram-starter mit StrgK StrgO. Sonst klone die Vorlage:

Stelle zuerst sicher, dass du keinen Ordner geöffnet hast. Um sicherzugehen, drücke einfach den Shortcut für »Ordner schließen«: StrgK und dann F. Dein Workspace sollte jetzt ungefähr so aussehen:

Klicke auf »Clone Repository« und füge die Adresse der Vorlage ein:

https://github.com/specht/pixelram-starter.git

Bestätige mit Enter. Danach wählst du das Verzeichnis, in dem das Repository gespeichert werden soll: den Ordner /workspace.

Das Repository wird jetzt in einen Unterordner von /workspace geklont, der so heißt wie das Repository. Beantworte die Frage, ob es jetzt geöffnet werden soll, mit »Open«:

Im Handbuch nachschlagen

Die Beispieldateien

Lade im Terminal drei GIF-Dateien in den Ordner der Vorlage:

wget https://workspace.hackschule.de/gif/diskette.gif
wget https://workspace.hackschule.de/gif/markt.gif
wget https://workspace.hackschule.de/gif/markt-interlaced.gif

diskette.gif ist eine Diskette mit 16 × 16 Pixeln und 4 Farben, nur 106 Bytes groß. Sie ist so klein, dass die ganze Datei auf diese Seite passt, und an ihr gehen wir jeden Block durch. markt.gif ist ein Foto mit 640 × 427 Pixeln und 256 Farben, markt-interlaced.gif dasselbe Foto in einer anderen Reihenfolge der Zeilen. Die beiden brauchst du später.

Sieh dir die Diskette Byte für Byte an:

hexdump -C diskette.gif

00000000  47 49 46 38 39 61 10 00  10 00 91 00 00 10 10 20  |GIF89a......... |
00000010  2a 6f b0 f4 f1 e8 c8 ce  d6 21 f9 04 00 00 00 00  |*o.......!......|
00000020  00 21 fe 0a 48 61 63 6b  73 63 68 75 6c 65 00 2c  |.!..Hackschule.,|
00000030  00 00 00 00 10 00 10 00  00 02 2d 8c 87 99 06 60  |..........-....`|
00000040  a1 e2 73 47 c2 87 e3 38  f8 69 de 41 1a 12 96 66  |..sG...8.i.A...f|
00000050  20 a4 ea 9a 62 ec 2b b8  67 fb c0 ac 1c ae ae ad  | ...b.+.g.......|
00000060  ee 7c 5c fb 01 4f a5 02  00 3b                    |.|\..O...;|

Das sind alle 106 Bytes. Die Farben zeigen die Blöcke, aus denen eine GIF-Datei besteht: Header, Logical Screen Descriptor, Global Color Table, Graphic Control Extension, Comment Extension, Image Descriptor, Bilddaten und Trailer. Fast die Hälfte der Datei sind die komprimierten Bilddaten.

Das Programm

Lege im Ordner der Vorlage die Datei gif.c an. Der Anfang liest die ganze Datei in den Speicher, und drei kleine Funktionen lesen daraus, immer an der Stelle pos, die dabei weiterwandert:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include "pixelram.h"

// Die ganze Datei im Speicher, und wo wir gerade lesen
uint8_t *file;
long file_size;
long pos = 0;

void fail(const char *message)
{
    printf("Fehler bei Byte %ld: %s\n", pos, message);
    exit(1);
}

uint8_t read_byte(void)
{
    if (pos >= file_size)
        fail("Die Datei ist zu Ende.");
    return file[pos++];
}

// GIF speichert Zahlen mit zwei Bytes im Little Endian: das niedrige Byte zuerst
int read_word(void)
{
    int low = read_byte();
    int high = read_byte();
    return low | (high << 8);
}

void read_file(const char *path)
{
    FILE *f = fopen(path, "rb");
    if (!f)
    {
        printf("Kann %s nicht öffnen.\n", path);
        exit(1);
    }
    fseek(f, 0, SEEK_END);
    file_size = ftell(f);
    fseek(f, 0, SEEK_SET);
    file = malloc(file_size);
    fread(file, 1, file_size, f);
    fclose(f);
}

int main(int argc, char **argv)
{
    if (argc < 2)
    {
        printf("Welche Datei? make PROGRAM=gif ARGS=diskette.gif\n");
        return 1;
    }
    read_file(argv[1]);
    printf("%s: %ld Bytes\n", argv[1], file_size);
    return 0;
}

• read_file öffnet die Datei, springt mit fseek ans Ende, um mit ftell die Größe zu erfahren, und liest dann alles auf einmal in file.
• read_byte gibt das Byte an der Stelle pos zurück und rückt pos eins weiter. Ist die Datei schon zu Ende, bricht fail das Programm mit einer Meldung ab, statt hinter der Datei weiterzulesen.
• read_word liest zwei Bytes und setzt sie zu einer Zahl zusammen, das erste ist das niedrige. Darauf kommen wir gleich beim Logical Screen Descriptor zurück.

Übersetze das Programm mit dem Namen der Datei, die es lesen soll:

make PROGRAM=gif ARGS=diskette.gif

make macht aus gif.c die Seite gif.html. Was hinter ARGS= steht, bekommt dein Programm als argv[1], und PixelRAM lädt eine Datei dieses Namens aus demselben Ordner mit, damit fopen sie findet. Öffne gif.html mit »Go Live« und dann die Konsole: Fahre mit der Maus über das Bild und klicke unten rechts auf das Terminal-Symbol oder drücke `. Dort steht diskette.gif: 106 Bytes.

3. Grober Ablauf eines GIF-Decoders

Eine GIF-Datei ist eine Folge von Blöcken, und dein Decoder liest sie der Reihe nach:

1. Header: Prüfe, ob die Datei mit GIF87a oder GIF89a beginnt.
2. Logical Screen Descriptor: Lies Breite und Höhe und öffne einen Bildschirm dieser Größe.
3. Global Color Table: Lies die Farben in die Palette von PixelRAM.
4. Blöcke bis zum Ende: Lies das erste Byte jedes Blocks. Eine Extension (0x21) überspringst du, auf einen Image Descriptor (0x2C) folgen Bilddaten, der Trailer (0x3B) beendet die Datei.
5. Bilddaten: Setze die Sub-blocks zusammen, lies daraus die Codes und entpacke sie mit LZW zu Pixelnummern.
6. Pixel setzen: Schreibe die Nummern Zeile für Zeile in den Bildschirm, bei Interlacing in einer anderen Reihenfolge der Zeilen.

Anders als JPEG speichert GIF Zahlen mit zwei Bytes im Little Endian: zuerst das niedrige Byte, dann das hohe. Auch die Bits der Codes werden andersherum gelesen als bei JPEG, vom niedrigsten Bit eines Bytes an. Beides war auf den PCs von 1987 die natürliche Reihenfolge.

4. Die Blöcke der Datei

Header

GIF89a, Abschnitt 17, Seite 7

Jede GIF-Datei beginnt mit sechs Zeichen: der Signatur GIF und der Version, 87a oder 89a. Die Version sagt, welche Blöcke vorkommen können; ein Decoder für 89a liest auch jede Datei von 1987.

      7 6 5 4 3 2 1 0        Field Name                    Type
     +---------------+
   0 |               |       Signature                     3 Bytes
     +-             -+
   1 |               |
     +-             -+
   2 |               |
     +---------------+
   3 |               |       Version                       3 Bytes
     +-             -+
   4 |               |
     +-             -+
   5 |               |
     +---------------+

Beispiel:

00000000  47 49 46 38 39 61 10 00  10 00 91 00 00 10 10 20  |GIF89a......... |

Ersetze in main die Zeile mit printf durch eine Prüfung: Sind die ersten drei Bytes nicht 'G', 'I' und 'F', beendet fail das Programm mit »Das ist keine GIF-Datei.«. Die Version brauchst du nicht, also überspringst du ihre drei Bytes. Probier es aus, indem du statt diskette.gif einmal Makefile als Argument angibst.

Logical Screen Descriptor

GIF89a, Abschnitt 18, Seite 8

Der Logical Screen ist die Fläche, auf der die Bilder der Datei erscheinen. Meistens ist es ein einziges Bild, genau so groß wie die Fläche. Eine Animation besteht dagegen aus vielen Bildern, die nacheinander auf dieselbe Fläche gezeichnet werden, manche nur auf einen Teil davon.

      7 6 5 4 3 2 1 0        Field Name                    Type
     +---------------+
  0  |               |       Logical Screen Width          Unsigned
     +-             -+
  1  |               |
     +---------------+
  2  |               |       Logical Screen Height         Unsigned
     +-             -+
  3  |               |
     +---------------+
  4  | |     | |     |       <Packed Fields>               See below
     +---------------+
  5  |               |       Background Color Index        Byte
     +---------------+
  6  |               |       Pixel Aspect Ratio            Byte
     +---------------+

     <Packed Fields>  =      Global Color Table Flag       1 Bit
                             Color Resolution              3 Bits
                             Sort Flag                     1 Bit
                             Size of Global Color Table    3 Bits

Beispiel:

00000000  47 49 46 38 39 61 10 00  10 00 91 00 00 10 10 20  |GIF89a......... |

Die Farbtabelle hat immer 2ⁿ⁺¹ Farben, wenn n in den letzten drei Bits steht: 2, 4, 8 und so weiter bis 256. In C ist das 2 << n. Jede Farbe sind drei Bytes, Rot, Grün und Blau.

Lies den Logical Screen Descriptor in main, direkt nach dem Header, Feld für Feld mit read_word und read_byte. Dann öffnest du einen Bildschirm in derselben Größe, mit screen_open(width, height, pixel_indexed8, argv[1]).

Für die Packed Fields brauchst du einzelne Bits: packed & 0x80 ist das höchste Bit, die Flagge für die Global Color Table, und packed & 7 sind die letzten drei Bits, ihre Größe. Mit & behältst du von einer Zahl nur die Bits, die in der Maske gesetzt sind: 0x80 ist 1000 0000, 7 ist 0000 0111.

Global Color Table

GIF89a, Abschnitt 19, Seite 10

Direkt nach dem Logical Screen Descriptor folgt die Global Color Table, wenn die Flagge gesetzt ist: für jede Farbe drei Bytes, Rot, Grün und Blau.

      7 6 5 4 3 2 1 0        Field Name                    Type
     +===============+
  0  |               |       Red 0                         Byte
     +-             -+
  1  |               |       Green 0                       Byte
     +-             -+
  2  |               |       Blue 0                        Byte
     +-             -+
  3  |               |       Red 1                         Byte
     +-             -+
     |               |       Green 1                       Byte
     +-             -+
 up  |               |
     +-   . . . .   -+       ...
 to  |               |
     +-             -+
     |               |       Green 255                     Byte
     +-             -+
767  |               |       Blue 255                      Byte
     +===============+

Beispiel:

00000000  47 49 46 38 39 61 10 00  10 00 91 00 00 10 10 20  |GIF89a......... |
00000010  2a 6f b0 f4 f1 e8 c8 ce  d6 21 f9 04 00 00 00 00  |*o.......!......|

Die Farben kommen gleich in die Palette von PixelRAM. Ein Image Descriptor kann später eine eigene Tabelle mitbringen, deshalb bekommt das Lesen eine eigene Funktion:

void read_color_table(int count)

Sie liest count Farben, je drei Bytes, und gibt jeder ihre Nummer in der Palette, mit set_palette(i, r, g, b). In main rufst du sie nach screen_open auf, wenn die Flagge gesetzt ist. Danach füllst du den Bildschirm mit clear in der Hintergrundfarbe.

Extensions

GIF89a, Abschnitte 15, 23 und 24, Seiten 5, 15 und 17

Mit der Version 89a kamen Extensions dazu: Blöcke, die einem Bild etwas hinzufügen, etwa eine Wartezeit für Animationen, eine durchsichtige Farbe oder einen Kommentar. Alle sind gleich gebaut. Sie beginnen mit dem Extension Introducer 0x21 und einem Label, das sagt, welche Extension es ist. Danach kommen ihre Daten in Data Sub-blocks: ein Byte mit einer Länge von 1 bis 255, dann so viele Bytes, dann wieder eine Länge, und so weiter, bis eine Länge 0 kommt, der Block Terminator.

      7 6 5 4 3 2 1 0        Field Name                    Type
     +---------------+
  0  |               |       Block Size                    Byte
     +---------------+
  1  |               |
     +-             -+
  2  |               |
     +-             -+
  3  |               |
     +-             -+
     |               |       Data Values                   Byte
     +-             -+
 up  |               |
     +-   . . . .   -+
 to  |               |
     +-             -+
     |               |
     +-             -+
255  |               |
     +---------------+

Dank dieser Form kann ein Decoder jede Extension überspringen, auch eine, die es 1990 noch gar nicht gab: Er liest Längen und springt weiter, bis die 0 kommt. Die Diskette hat zwei Extensions:

00000010  2a 6f b0 f4 f1 e8 c8 ce  d6 21 f9 04 00 00 00 00  |*o.......!......|
00000020  00 21 fe 0a 48 61 63 6b  73 63 68 75 6c 65 00 2c  |.!..Hackschule.,|

Für ein einzelnes Bild brauchst du keine Extension. Eine Funktion, die Sub-blocks liest, brauchst du trotzdem, denn auch die Bilddaten kommen gleich in Sub-blocks:

long read_sub_blocks(uint8_t *data)

Sie liest eine Länge, dann so viele Bytes, dann wieder eine Länge, bis die Länge 0 kommt. Die Bytes schreibt sie hintereinander in den Speicher data, ohne die Längen, und gibt zurück, wie viele es insgesamt waren. Ist data gleich NULL, zählt sie nur. So kann dieselbe Funktion eine Extension überspringen und Bilddaten lesen.

Image Descriptor

GIF89a, Abschnitte 20 und 21, Seiten 11 und 13

Jedes Bild beginnt mit einem Image Descriptor: dem Image Separator 0x2C, der Position des Bildes auf dem Logical Screen und seiner Größe.

      7 6 5 4 3 2 1 0        Field Name                    Type
     +---------------+
  0  |               |       Image Separator               Byte
     +---------------+
  1  |               |       Image Left Position           Unsigned
     +-             -+
  2  |               |
     +---------------+
  3  |               |       Image Top Position            Unsigned
     +-             -+
  4  |               |
     +---------------+
  5  |               |       Image Width                   Unsigned
     +-             -+
  6  |               |
     +---------------+
  7  |               |       Image Height                  Unsigned
     +-             -+
  8  |               |
     +---------------+
  9  | | | |   |     |       <Packed Fields>               See below
     +---------------+

     <Packed Fields>  =      Local Color Table Flag        1 Bit
                             Interlace Flag                1 Bit
                             Sort Flag                     1 Bit
                             Reserved                      2 Bits
                             Size of Local Color Table     3 Bits

Beispiel:

00000020  00 21 fe 0a 48 61 63 6b  73 63 68 75 6c 65 00 2c  |.!..Hackschule.,|
00000030  00 00 00 00 10 00 10 00  00 02 2d 8c 87 99 06 60  |..........-....`|

Table Based Image Data

GIF89a, Abschnitte 22 und 27, Seiten 14 und 23

Hinter dem Image Descriptor (und einer Local Color Table, falls es eine gibt) stehen die Bilddaten: ein Byte, die LZW Minimum Code Size, und dann die komprimierten Daten in Sub-blocks. Nach dem letzten Bild steht der Trailer, ein einzelnes Byte 0x3B.

      7 6 5 4 3 2 1 0        Field Name                    Type
     +---------------+
     |               |       LZW Minimum Code Size         Byte
     +---------------+

     +===============+
     |               |
     /               /       Image Data                    Data Sub-blocks
     |               |
     +===============+

Beispiel:

00000030  00 00 00 00 10 00 10 00  00 02 2d 8c 87 99 06 60  |..........-....`|
00000040  a1 e2 73 47 c2 87 e3 38  f8 69 de 41 1a 12 96 66  |..sG...8.i.A...f|
00000050  20 a4 ea 9a 62 ec 2b b8  67 fb c0 ac 1c ae ae ad  | ...b.+.g.......|
00000060  ee 7c 5c fb 01 4f a5 02  00 3b                    |.|\..O...;|

Jetzt kann main alle Blöcke lesen, bis der Trailer kommt. Schreib dafür eine Schleife, die immer das erste Byte eines Blocks liest:

• 0x3B ist der Trailer: Die Schleife ist fertig.
• 0x21 ist eine Extension: Lies das Label und überspringe die Sub-blocks.
• 0x2C ist ein Image Descriptor: Ruf read_image() auf.
• Alles andere ist ein Fehler in der Datei; fail sagt, bei welchem Byte.

Die Funktion void read_image(void) liest den Rest des Image Descriptors, eine Local Color Table, falls es eine gibt, die LZW Minimum Code Size und die Bilddaten. Wie viel Speicher die Bilddaten brauchen, weißt du erst, wenn du sie gelesen hast. Lies die Sub-blocks deshalb zweimal: einmal nur zum Zählen, dann mit einem Speicher aus malloc, der groß genug ist. Dazwischen setzt du pos dorthin zurück, wo die Sub-blocks anfangen.

Lass read_image zum Schluss ausgeben, was es gelesen hat, und übersetze. In der Konsole sollte stehen:

Bild 16 x 16 bei (0, 0), 45 Bytes Daten

Mit markt.gif im Feld der Argumente sind es über 200.000 Bytes, in 814 Sub-blocks.

5. Vom Datenstrom zum Bild

Codes lesen

Die Bilddaten sind eine Folge von Codes. Ein Code ist zu Anfang LZW Minimum Code Size + 1 Bits lang, bei der Diskette also 3 Bits. Später werden die Codes länger, bis höchstens 12 Bits. Codes halten sich nicht an Bytegrenzen: GIF füllt jedes Byte vom niedrigsten Bit an, und ein Code, der nicht mehr hineinpasst, geht im nächsten Byte weiter.

Am einfachsten siehst du das, wenn du die Bytes von rechts nach links schreibst, das erste Byte ganz rechts. Dann stehen die Bits in der Reihenfolge, in der sie gelesen werden, von rechts nach links, und jeder Code steht in einem Stück da:

Byte        06         99         87         8c
Bits     00000110   10011001   10000111   10001100

Von rechts nach links gelesen: 4, 1, 6, 3, 8, 9, 9, 6, 0.

Die ersten vier Codes haben 3 Bits, die nächsten 4 Bits. Warum sie länger werden, kommt gleich.

Schreib einen Bitleser:

int read_code(int size)

Er liest die nächsten size Bits aus den Bilddaten und gibt sie als Zahl zurück. Dafür merkt er sich in einer Variablen bit_pos, beim wievielten Bit er ist. Bit Nummer bit_pos steht im Byte bit_pos / 8 als Bit Nummer bit_pos % 8, und das erste gelesene Bit wird das niedrigste Bit des Codes. Prüf ihn an der Diskette: Mit 3 Bits muss er zuerst 4, dann 1, dann 6 liefern.

LZW-Decodierung

GIF89a, Anhang F, Seite 30, und das Deckblatt

Jeder Code steht für einen Eintrag in einer Tabelle, und jeder Eintrag ist eine Folge von Pixelnummern. Am Anfang enthält die Tabelle nur die einzelnen Farben, bei der Diskette die Einträge 0, 1, 2 und 3. Danach kommen zwei besondere Codes:

• Clear Code: 2ⁿ, wenn n die LZW Minimum Code Size ist, bei der Diskette 2² = 4. Die Tabelle beginnt von vorn, nur mit den Farben, und die Codes haben wieder ihre Anfangslänge. Ein Encoder schickt ihn als ersten Code.
• End of Information, eins mehr, bei der Diskette 5: Die Bilddaten sind zu Ende.

Der nächste freie Eintrag ist also 6. Den Rest baut der Decoder beim Lesen selbst, nach diesen Regeln:

1. Nach dem Clear Code steht ein Code für eine einzelne Farbe. Schreib sie hin. Er ist der vorige Code für den nächsten Schritt.
2. Steht der Code schon in der Tabelle, schreib seinen Eintrag hin. Der neue Eintrag in der Tabelle ist der Eintrag des vorigen Codes und dahinter das erste Pixel des jetzigen.
3. Steht der Code noch nicht in der Tabelle, ist er genau der Eintrag, der jetzt neu entsteht. Er ist der Eintrag des vorigen Codes und dahinter das erste Pixel des vorigen. Trag ihn ein und schreib ihn hin.
4. Hat die Tabelle danach 2^Codelänge Einträge, wird die Codelänge um 1 größer, bis höchstens 12 Bits. Mit 3 Bits gibt es Codes bis 7. Sobald Eintrag 7 da ist, braucht der nächste Code 4 Bits.
5. Hat die Tabelle 4096 Einträge, kommen keine mehr dazu, bis ein Clear Code sie leert.

Regel 5 steht nicht im Text von 1990, sondern auf dem Deckblatt, das CompuServe nachgereicht hat: Ein Encoder muss bei voller Tabelle keinen Clear Code schicken, er darf mit der vollen Tabelle weitermachen. Viele Decoder kamen damit damals nicht zurecht.

Der Encoder hat beim Komprimieren dieselbe Tabelle gebaut, nach denselben Regeln, nur einen Schritt früher. Deshalb muss sie nicht in der Datei stehen. Und deshalb gibt es Regel 3: Der Encoder kann einen Eintrag benutzen, den er gerade erst angelegt hat und den der Decoder noch nicht kennt. Das passiert immer dann, wenn sich eine Folge gleich wiederholt, bei der Diskette schon beim dritten Code.

Probier es mit den Bytes der Diskette aus: Jeder Klick liest einen Code. Das Bild wächst dabei mit, die neuen Pixel sind umrandet. Die Zahlen in den Pixeln sind ihre Nummern in der Farbtabelle.

Nach 66 Codes ist das Bild fertig: 256 Pixel aus 45 Bytes. Gegen Ende stehen in der Tabelle Einträge mit neun und zehn Pixeln, lange Stücke des Etiketts und der Hülle. Je länger ein Bild ist, desto mehr lange Folgen kennt die Tabelle, und desto besser komprimiert LZW.

Die Tabelle im Speicher

Jetzt bist du dran: Schreib eine Funktion, die die Codes liest und die Pixelnummern in einen Speicher pixels schreibt.

long decode_lzw(uint8_t *data, long data_size, int min_code_size, uint8_t *pixels, long pixel_count)

Die Tabelle braucht für 4096 Einträge nicht 4096 Listen. Ein neuer Eintrag ist immer ein Eintrag, den es schon gibt, und ein Pixel dahinter. Speichere also für jeden Eintrag k nur diese zwei Dinge, und dazu, was du beim Schreiben brauchst:

int prefix[4096];      // der Eintrag davor, -1 bei den einzelnen Farben
uint8_t suffix[4096];  // das letzte Pixel
uint8_t first[4096];   // das erste Pixel
int length[4096];      // wie viele Pixel

Um den Eintrag k hinzuschreiben, gehst du die Kette rückwärts: suffix[k] ist das letzte Pixel, suffix[prefix[k]] das vorletzte, und so weiter. Weil length[k] sagt, wie lang der Eintrag ist, kannst du gleich an der richtigen Stelle von hinten nach vorn schreiben.

In read_image rufst du decode_lzw nach dem Lesen der Sub-blocks auf, mit einem Speicher für width * height Pixel. Dann setzt du die Pixel Zeile für Zeile mit set_pixel. Denk an die Position des Bildes: Das Pixel in Spalte x und Zeile y des Bildes gehört nach left + x, top + y.

Wenn alles stimmt, siehst du nach make die Diskette:

Die Prüfsumme

Ob jedes Pixel stimmt, ist mit dem Auge schwer zu sagen, bei einem Foto erst recht. Deshalb rechnet dein Programm am Ende eine Prüfsumme über das ganze Bild aus: über Rot, Grün und Blau jedes Pixels, Zeile für Zeile, mit dem Verfahren Adler-32. Ändert sich nur ein Pixel, ändert sich die Prüfsumme. Schreib die Funktion über main:

// Adler-32 über Rot, Grün und Blau aller Pixel, Zeile für Zeile
uint32_t screen_checksum(void)
{
    uint32_t a = 1, b = 0;
    for (int y = 0; y < screen_height(); y++)
        for (int x = 0; x < screen_width(); x++)
        {
            uint8_t rgb[3];
            get_pixel_rgb(x, y, &rgb[0], &rgb[1], &rgb[2]);
            for (int i = 0; i < 3; i++)
            {
                a = (a + rgb[i]) % 65521;
                b = (b + a) % 65521;
            }
        }
    return (b << 16) | a;
}

und gib sie am Ende von main aus, nach der Schleife über die Blöcke:

    printf("%s: %d x %d, Prüfsumme %08x\n", argv[1], width, height, screen_checksum());

get_pixel_rgb schlägt die Farbe jedes Pixels in der Palette nach. So zählt auch, ob die Farbtabelle richtig gelesen ist.

Ein Foto

Tippe in der Konsole markt.gif in das Feld der Argumente und klicke auf »Run«. Bei diesem Bild kommt alles vor, was die Diskette nicht braucht: 256 Farben, Codes von 9 bis 12 Bits, eine volle Tabelle und viele Clear Codes.

Foto mit freundlicher Genehmigung von Ian Kobylanski · https://koby.photography/

Sieh dir das Bild aus der Nähe an. Hier ist ein Ausschnitt, achtmal vergrößert: links aus dem Original, einem JPEG, das für den Vergleich auf dieselben 640 Pixel Breite verkleinert ist, rechts aus markt.gif:

6. Interlacing

GIF89a, Abschnitt 20, Seite 13, und Anhang E, Seite 29

Über eine Telefonleitung von 1990 dauerte ein Bild wie markt.gif mehrere Minuten. Damit man früh sah, was kommt, kann ein GIF seine Zeilen in einer anderen Reihenfolge speichern: erst jede achte Zeile, dann die dazwischen, bis alle da sind. Ein Programm, das schon beim Laden zeichnet, zeigt so nach einem Achtel der Daten ein grobes Bild, das nach und nach schärfer wird. Gesetzt ist dafür das Interlace Flag im Image Descriptor, packed & 0x40.

An den Daten selbst ändert sich nichts: Die Pixel kommen wie immer heraus, nur gehört die i-te Zeile der Daten nicht in Zeile i des Bildes. Bei einem Bild mit 427 Zeilen hat Durchgang 1 die Zeilen 0 bis 424, das sind 54. Die 55. Zeile der Daten ist also Zeile 4 im Bild.

Schreib eine Funktion int image_row(int i, int height, int interlaced), die für die i-te Zeile der Daten die Zeile im Bild ausrechnet, und benutze sie in read_image beim Setzen der Pixel.

7. Animationen

GIF89a, Abschnitte 23 und 26, Seiten 15 und 21

Eine Animation ist eine GIF-Datei mit vielen Bildern. Vor jedem steht eine Graphic Control Extension, die sagt, wie lange es zu sehen ist und was danach mit ihm passiert. Lade eine:

wget https://workspace.hackschule.de/gif/flug.gif

flug.gif hat 16 Bilder. Das erste ist die Landschaft, so groß wie der Logical Screen. Die übrigen sind nur 16 × 16 Pixel groß: jedes Mal die Diskette, an einer anderen Stelle. Das letzte bringt eine Local Color Table mit, in der die Diskette rot ist. Ganz vorn steht außerdem eine Application Extension mit dem Text NETSCAPE2.0: Sie sagt, dass die Animation sich endlos wiederholt. Erfunden hat sie 1995 der Browser Netscape, in der Spezifikation steht sie nicht. Dein Decoder überspringt sie wie jede Extension.

Graphic Control Extension

      7 6 5 4 3 2 1 0        Field Name                    Type
     +---------------+
  0  |               |       Extension Introducer          Byte
     +---------------+
  1  |               |       Graphic Control Label         Byte
     +---------------+

     +---------------+
  0  |               |       Block Size                    Byte
     +---------------+
  1  |     |     | | |       <Packed Fields>               See below
     +---------------+
  2  |               |       Delay Time                    Unsigned
     +-             -+
  3  |               |
     +---------------+
  4  |               |       Transparent Color Index       Byte
     +---------------+

     +---------------+
  0  |               |       Block Terminator              Byte
     +---------------+

      <Packed Fields>  =     Reserved                      3 Bits
                             Disposal Method               3 Bits
                             User Input Flag               1 Bit
                             Transparent Color Flag        1 Bit

Beispiel: das zweite Bild von flug.gif, die Diskette zum ersten Mal

00000220  00 00 21 f9 04 0d 08 00  00 00 2c 02 00 08 00 10  |..!.......,.....|
00000230  00 10 00 00 04 32 30 c8  41 6b 95 00 c8 60 fb d6  |.....20.Ak...`..|

Die Disposal Method sagt, was mit einem Bild geschieht, wenn seine Zeit um ist und das nächste kommt:

Die Diskette in flug.gif hat Disposal Method 3: Die Landschaft unter ihr kommt zurück, bevor sie an der nächsten Stelle erscheint. Ohne das zöge sie eine Spur hinter sich her.

Farben ohne Palette

Im Modus pixel_indexed8 gibt es eine einzige Palette für den ganzen Bildschirm. Schreibst du die Local Color Table des letzten Bildes mit set_palette hinein, ändern sich auch alle Pixel, die schon dastehen: Der Himmel hat dieselbe Nummer wie die Hülle der Diskette und würde mit ihr rot. Für Animationen öffnest du den Bildschirm deshalb im Modus pixel_rgb24, in dem jedes Pixel seine Farbe selbst trägt. Die Farbtabellen hebst du in Arrays auf, etwa uint8_t global_colors[256][3], und jedes Pixel bekommt mit set_pixel_rgb die Farbe aus der Tabelle, die für sein Bild gilt.

Abspielen

Kopiere deinen Decoder und übersetze die Kopie mit der Animation:

cp gif.c animation.c
make PROGRAM=animation ARGS=flug.gif

Was animation.c zusätzlich braucht:

• Die Graphic Control Extension lesen. Ist das Label einer Extension 0xF9, liest void read_graphic_control(void) Disposal Method, Delay Time und, falls das Flag gesetzt ist, den Transparent Color Index. Die Werte gelten nur für das nächste Bild; danach setzt du sie zurück.
• Durchsichtige Pixel auslassen. Pixel mit dem Transparent Color Index setzt read_image nicht.
• Zeigen und warten. Nach jedem Bild zeigt present() den Bildschirm, sleep_ms wartet die Delay Time ab, in Millisekunden also das Zehnfache. Browser machen aus weniger als 2 Hundertstelsekunden 10; das ist eine gute Regel.
• Wegräumen. Danach gilt die Disposal Method. Für 3 musst du dir vor dem Zeichnen merken, was unter dem Bild war: Lies die Pixel seiner Fläche mit get_pixel_rgb in einen Speicher und schreib sie nach der Wartezeit zurück.
• Von vorn. Kommt der Trailer, springst du mit pos zurück zum ersten Block nach der Global Color Table. Die Schleife über die Blöcke läuft dann, solange should_close() falsch ist.

Ein Streit mit Bugs Bunny

Wie spricht man GIF aus? Steve Wilhite, der das Format bei CompuServe entworfen hat, sagte 2013 bei den Webby Awards: mit weichem G, wie die Erdnussbutter Jif. Viele sehen das anders. Im Netz streiten Bugs Bunny und Daffy Duck darüber, in einer Fan-Montage aus einem alten Looney-Tunes-Cartoon, die bei Know Your Meme liegt. Lade sie und spiel sie mit deinem Decoder ab:

wget -O bugs.gif https://i.kym-cdn.com/photos/images/original/000/996/256/0eb.gif

Sie hat 45 Bilder mit 301 × 221 Pixeln, jedes so groß wie der Logical Screen und nur 3 Hundertstelsekunden lang. Das sind drei Millionen Pixel, und die Datei hat trotzdem keine 500 KB: Die meisten Bilder zeichnen nur die Pixel neu, die sich ändern, im Schnitt sind drei Viertel ihrer Fläche durchsichtig. Lass dir für jedes Bild ausgeben, wie viele seiner Pixel durchsichtig sind, und such die Stellen, an denen der Film einen Schnitt hat.

8. Weiter geht's

Dein Decoder liest und spielt jetzt jedes GIF. Wer weitermachen will:

• Ein Encoder: Schreib das Ganze andersherum, ein Programm, das aus Pixeln eine GIF-Datei macht. Es braucht dieselben Blöcke und dieselbe Tabelle, und dein Decoder sagt dir, ob es funktioniert.
• Plain Text Extension: GIF89a kann Text enthalten, den der Decoder selbst in ein Raster aus Zeichenzellen zeichnen soll, in einer Schrift, die er sich aussucht (Abschnitt 25, Seite 18). Kaum ein Programm hat das je unterstützt. Bau eine Datei mit dieser Extension und zeig ihren Text an.
• GIFs aus dem Netz: Lade GIFs von irgendwoher und finde heraus, was dein Decoder noch nicht kann.