Pixelgrafik
Deine Aufgabe ist es, ein Bild zu decodieren. Du bekommst einen Strom einzelner Bytes und daraus ein Bild erstellen.
Im Gegensatz zur Pixelflut kannst du hier Pixel nicht auf beliebige RGB-Farben setzen, sondern nur einfache, ganze Zahlen als Farben verwenden. Dafür gibt es in jeder Aufgabe eine vordefinierte Palette, die einer Handvoll Zahlen jeweils eine Farbe zuordnet.
Deine Aufgabe ist es, ein codiertes Bild zu decodieren. Die Art der Decodierung ist abhängig von der Aufgabenstellung, die du ganz oben findest (es geht einfach los und wird später schwieriger).
Die codierten Zahlen findest du im Parameter data deiner run-Methode. Für diese Variable stehen dir folgende Methoden zur Vefügung:
next() |
gibt das nächste Byte zurück |
length() |
gibt die Länge des Datenstroms in Bytes zurück |
eof() |
gibt an, ob wir am Ende des Datenstroms angelangt sind (eof = »end of file«) |
reset() |
springt zurück zum Anfang des Datenstroms |
read() |
liefert alle Bytes in einer Liste zurück |
Du kannst also, solange du nicht am Ende des Datenstroms angelangt bist, immer das nächste Byte mit Hilfe der next-Methode lesen und dann dieses Byte untersuchen. Je nach Aufgabenstellung musst du nun aus jedem Byte ableiten, wie viele und welche Pixel du setzen musste. Am Ende soll ein fertiges Bild entstehen.
Um Pixel zu setzen, kannst du die folgende Methode verwenden:
set_pixel(x, y, c) |
Pixel an Position (x, y) auf Farbe c setzen |
In dieser Aufgabe entspricht jedes Byte einem Pixel. Die einzelnen Pixel sind zeilenweise von oben nach unten und in jeder Zeile von links nach rechts codiert. Lies alle Bytes hintereinander und setze den entsprechenden Pixel auf die jeweilge Farbe.
In dieser Aufgabe werden immer zwei Pixel in einem Byte komprimiert. Da es nicht mehr als 16 Farben gibt, können immer zwei Pixel zu einem Byte zusammengefasst werden. Dabei bezeichnen die unteren 4 Bits den ersten Pixel, und die oberen 4 Bits den zweiten Pixel:
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|
| 2. Pixel | 1. Pixel | ||||||
In dieser Aufgabe werden Pixel derselben Farbe zusammengefasst. Dies spart viel Speicherplatz, wenn mehrmals hintereinander dieselbe Farbe im Bild vorkommt. Dieses Verfahren heisst »RLE-Komprimierung« (RLE = Run Length Encoding, auf deutsch »Lauflängencodierung«). Dabei müssen immer zwei Bytes gelesen werden. Das erste Byte gibt an, wie oft die im darauffolgenden Byte codierte Farbe wiederholt wird.
In dieser Aufgabe wird wieder die RLE-Komprimierung verwendet. Allerdings wird dieses Verfahren hier nur angewendet, wenn ein Pixel mehr als zweimal wiederholt wird, um weiteren Speicherplatz zu sparen.
Dass ein Pixel wiederholt werden soll, wird dadurch signalisiert, dass in einem Byte das höchste Bit gesetzt ist. Wenn es gesetzt ist, wird die Anzahl der Wiederholungen in den unteren 7 Bits angegeben und die Farbe im darauffolgenden Byte. Ist das höchste Bit nicht gesetzt, repräsentiert dieses Byte einfach die Farbe des nächsten Pixels.
Es werden also die folgenden zwei Fälle unterschieden (je nachdem ob das höchste Bit gesetzt ist oder nicht):
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | |
|---|---|---|---|---|---|---|---|---|
| 1. Byte | 1 | Anzahl der Wiederholungen | ||||||
| 2. Byte | Farbe, die wiederholt werden soll | |||||||
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | |
| 1. Byte | 0 | Farbe des Pixels | ||||||
In dieser Aufgabe wird wieder die RLE-Komprimierung verwendet. Hier wird wieder jeder Pixel lauflängencodiert, allerdings werden die Anzahl der Wiederholungen und die Farbe in einem Byte gespeichert:
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|
| Anzahl der Wiederholungen - 1 | Farbe, die wiederholt werden soll | ||||||
Da kein Pixel 0 mal wiederholt wird, sondern mindestens immer einmal, wird die Anzahl der Wiederholungen subtrahiert um 1 abgespeichert.
In dieser Aufgabe wird die Deflate-Komprimierung verwendet, das in vielen Dateiformaten (wie z. B. ZIP, PNG, PDF, ODT und TIFF) zum Einsatz kommt.
Da es nicht trivial ist, einen mit Deflate komprimierten Datenstrom zu dekomprimieren, bietet es sich an, auf die zlib-Bibliothek und die darin enthaltene Methode zlib.decompress zurückzugreifen.