Skip to content

Instantly share code, notes, and snippets.

@magical
Last active April 20, 2020 08:41
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save magical/272f5d329d65c1fca1706b6fa175fe4d to your computer and use it in GitHub Desktop.
<?xml version="1.0" encoding="UTF-8" ?>
<mediawiki version="0.1" xml:lang="de">
<page>
<title>Grafikkomprimierung PKMN RGBY</title>
<revision>
<timestamp>2006-05-21T08:40:04Z</timestamp>
<contributor><username>Tauwasser</username></contributor>
<minor/>
<comment>/* Genereller Vorgang */</comment>
<text>Die Grafikkompression in Pokémon Rot, Grün, Blau und Gelb ist eine Kombination aus unkomprimierten Daten und einem RLE-Befehl, der nur 0-Bits schreibt.
==Überblick==
Die Kompression benutzt eine Bitstream-Architektur in der nur der Header, das sind in diesem Fall die ersten 9 [[Bits_und_Bytes|Bits]] der Daten, sowie 1 bzw. 2 spezielle [[Bits_und_Bytes|Bits]] fest mit Funktionen belegt sind. Der Rest ist variabel in Bit-Pakete geteilt. Das sind also Pakete, die je nach den vorangehenden Bits andere Eigenschaften und Funktionen zugeschrieben kriegen.&lt;br&gt;
Ebenfalls erwähnenswert ist, dass diese Kompression im Gegensatz zu z.B. der Kompression in Pokémon Gold und Silber keinen festen Beenden-Code aufweist. Wie das funktioniert wird in einer der nächsten Sektion erklärt.&lt;br&gt;
Das besondere an der Kompression ist, dass die eigentlichen Bilddaten gar nicht komprimiert sind, sondern [[Meta]]-Codes, die dann im zweiten Schritt der Dekompression benutzt werden um die Bilddaten herzustellen. Der besondere Vorteil dieser Art der Kompression ist, dass sehr wenig Daten komprimiert werden müssen, da die [[Meta]]-Codes relativ klein gehalten sind. Ein weiterer Vorteil ist, dass so alle komprimierten Daten spiegelbar sind, d.h. die ausgegebenen Daten ohne großen [[CPU]]-Aufwand gedreht werden können.
==Genereller Vorgang==
Der Dekompressionsvorgang spielt sich in etwa folgendermaßen ab. Zunächst einmal sind 2 feste Rambereiche von je 0x188 Bytes in Größe vorgegeben. Daraus ergibt sich schon die erste ''Limitation'' der Kompression, nämlich die Begrenzung auf '''maximal 0x31 [[Tile|Tiles]]''' pro komprimierten Daten.&lt;br&gt;
Zuerst wird der eine Rambereich vollgeschrieben, danach der andere. Die Rambereiche werden vorher festgelegt anhand des Headers.&lt;br&gt;
Nachdem dieses geschehen ist, wird anhand der Festlegung im Header diese [[Meta]]-Codemasse ausgewertet und verarbeitet. Hier wird dann auch (falls nötig) die Spiegelung vorgenommen. Die Rambereiche spielen in der Auswertung eine wichtige Rolle, da beide Rambereiche von je 0x188 Bytes zu einer kompletten Datenmasse zusammengefügt werden. Dies geschieht über eine von 3 Methoden, die im Header festgelegt ist.
==Der Header==
Wie oben erwähnt, besteht der feste Header aus 9 [[Bits_und_Bytes|Bits]]. Das erste [[Bits_und_Bytes|Byte]] gibt die Ausmaße an. Es ist in zweimal 4-Bit getrennt. Die Bits 0-3 geben die Breite in Anzahl Bytes / 8 an. Die Bits 4-7 geben die Höhe in Anzahl X-Reihen an.&lt;br&gt;
[Byte]
[Y |X]
Keinesfalls sollten diese Werte mit Ausmaßen verwechselt werden. Die Ausmaße sind frei bestimmbar durch die jeweiligen [[Tile|Tiles]] auf dem Bildschirm. Y ist eigentlich bloß ein Zähler wie viele Male X vorkommt. Durch diese Verkettung kann noch einmal optimiert werden.&lt;br&gt;
Das erste Bit nach dem Byte, also das 7. Bit des Folgebytes, gibt einen Rückschluss auf den Rambereich, der zuerst benutzt werden soll. Der Einfachheit halber werden sie hier als RAM1 und RAM2 betitelt. Die Aussagen 1.RAM und 2.RAM hingegen beziehen sich auf die Reihenfolge der Beschreibung. Wenn also z.B. RAM2 als zuerst zu benutzender RAM festgelegt wurde, dann ist er auch der 1.RAM. Natürlich gilt dies auch umgedreht.
Die Festlegung ist denkbar einfach:
(Bit7)
0 = RAM1
1 = RAM2
'''Zusammenfassung'''
[Byte ] (Bit7)
[X-Reihen|X-Breite] 0 = RAM1
1 = RAM2
==Die restlichen Bits==
Jetzt fehlen nur noch die anderen 1 bzw. 2 fest vergebenen [[Bits_und_Bytes|Bits]], dann sind alle fest vergebenen Bits geklärt.&lt;br&gt;
Diese [[Bits_und_Bytes|Bits]] folgen auf das Ende der ersten Daten, das heißt wenn der 1. RAM vollgeschrieben ist, werden sie ausgelesen und danach mit den Daten für den 2. RAM weiter gelesen.&lt;br&gt;Jedoch sind diese Bit schon ein kleines Paket für sich: Ist nämlich das 1. Bit auf 1 gesetzt, so wird ein weiteres Bit, nämlich das 2. Bit desselben Bytes, genommen und anhand dessen ausgewertet. Diese Bits entscheidet auf welche Art und Weise die [[Meta]]-Codes zusammengefügt und ausgewertet werden.
(Bit1)''(Bit2)''
0 = Auswertung 1
1 = werte Bit2 aus:
0 = Auswertung 2
1 = Auswertung 3
Das 2. Bit des Bytes wird also nur dann zur Bestimmung der Auswertungsmethode genommen, wenn das 1. Bit des Bytes ungleich 0, also 1 ist!
&lt;div style=&quot;background:#f9f9f9;border:1px solid #2f6fab;border-collapse:collapse;margin:10px 0;padding:5px;font-family:monospace;font-size:95%;&quot;&gt;
Kurze Zeichenerklärung:
Terme in eckigen Klammern [] sind Bytes, in runden Klammern () Bits. Wenn sie ''kursiv'' geschrieben sind, sind sie optional und an eine Bedingung eines vorigen Bits gekoppelt.
&lt;/div&gt;
==Die Bitgruppen==
Eine weitere Spezialität ist, dass die [[Meta]]-Codes bitgruppenweise geschrieben werden. Die Bitgruppen sind wie folgt aufgeteilt:
Bits 76 54 32 10
Gruppe 3 2 1 0
Es werden zuerst in jeder X-Reihe die Bitgruppe 3 geschrieben. Am Ende der Reihe angekommen wird angefangen Bitgruppe 2 zu beschreiben usw. Erst beim Wechsel von Gruppe 0 zu Gruppe 3 wird die Y-Zeile angepasst. Die Pakete schreiben wie gesagt immer diese Bitgruppen voll anstatt ganze Bytes.
==Die Pakete==
Da es bloß 2 Arten von Codes gibt, nämlich den RLE-Befehl, der 0-Bits schreibt und den Code, der unkomprimiert Bits schreibt, gibt es auch bloß 2 Arten von Paketen.
Die Pakete starten direkt nach dem Header und werden solange fortgesetzt bis alle Daten einmal geschrieben sind. Danach wird automatisch der bisher nicht benutzte RAM genommen und dort wird nocheinmal dieselbe Datenmenge geschrieben.
===Das RLE-Paket===
Das RLE-Paket kann bis zu 0xFFFF mal Bitgruppen mit 00 füllen. Der Befehl selbst kann auf 2 verschiedene Arten aktiviert werden. Entweder gleich zu Beginn, also ab dem Header, oder aber durch Abbruch des Daten-Pakets, das die unkomprimierten Daten in die Bitgruppen schreibt. Folgt der Befehl direkt auf den Header, so braucht er als Unterscheidung zum anderen Paket ein vorangestelltes Bit 0.&lt;br&gt;
Ansonsten besteht er aus 1 bis maximal 31 Bits und folgt immer dann, wenn das Daten-Paket abgebrochen wurde. Es bedient sich einer ein Zählmethode und einer Tabelle um zu bestimmen, wieviele 00-Bitgruppen geschrieben werden sollen.&lt;br&gt;
Zunächst wird ausgezählt wieviele Male Bit auf 1 gesetzt folgen. Das können um den Rahmen nicht zu sprengen maximal 15 aufeinanderfolgende sein. Nach diesen Bits werden nochmal genau soviele Bits und eins mehr gelesen. Dann wird der Tabelleneintrag und die gelesene Zahl addiert und das bestimmt die Anzahl der zu schreibenden 00-Bitgruppen.&lt;br&gt;
Die Tabelle sieht wie folgt aus:
{|border=&quot;2&quot; cellspacing=&quot;0&quot; cellpadding=&quot;4&quot; rules=&quot;all&quot; style=&quot;margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse; background-color:#F9F9F9; font-size:95%; empty-cells:show; text-align: center&quot;
!Anzahl Bits&lt;br&gt; &quot;1&quot;
!Anzahl Bits&lt;br&gt; zu addieren
!Tabellenwert
!Maximalwert
| bgcolor=&quot;#8A8A97&quot; |
!Anzahl Bits&lt;br&gt; &quot;1&quot;
!Anzahl Bits&lt;br&gt; zu addieren
!Tabellenwert
!Maximalwert
|-
|0x00
|0x01
|0001
|0002
| bgcolor=&quot;#8A8A97&quot; |
|0x08
|0x09
|01FF
|03FE
|-
|0x01
|0x02
|0003
|0006
| bgcolor=&quot;#8A8A97&quot; |
|0x09
|0x0A
|03FF
|07FE
|-
|0x02
|0x03
|0007
|000E
| bgcolor=&quot;#8A8A97&quot; |
|0x0A
|0x0B
|07FF
|0FFE
|-
|0x03
|0x04
|000F
|001E
| bgcolor=&quot;#8A8A97&quot; |
|0x0B
|0x0C
|0FFF
|1FFE
|-
|0x04
|0x05
|001F
|003E
| bgcolor=&quot;#8A8A97&quot; |
|0x0C
|0x0D
|1FFF
|3FFE
|-
|0x05
|0x06
|003F
|007E
| bgcolor=&quot;#8A8A97&quot; |
|0x0D
|0x0E
|3FFF
|7FFE
|-
|0x06
|0x07
|007F
|00FE
| bgcolor=&quot;#8A8A97&quot; |
|0x0E
|0x0F
|7FFF
|FFFE
|-
|0x07
|0x08
|00FF
|01FE
| bgcolor=&quot;#8A8A97&quot; |
|0x0F
|0x10
|FFFF
|FFFF
|}
Beispielrechnung:
Bitstream ''(0)'' (111110) (000001)
Opt. Bit 5 Bit &quot;1&quot; +1
nach Header
Tabelleneintrag 0x003F
Additiver Wert 0x0001
----------------------
Endwert 0x0040
===Das Daten-Paket===
Das Datenpaket füllt eine Bitgruppe komplett mit 2 Bits die in keinster Weise in reduzierten Platzverbrauch gespeichert sind. Soll gleich nach dem Header das Daten-Paket folgen, so muss ihm ein Bit &quot;1&quot; vorangestellt werden. Dieser Befehl liest dann immer 2 Bits ein und schreibt diese in die jeweilige Bitgruppe. Einzige Ausnahme ist die Bitgruppe &quot;00&quot;. Sie stellt das Ende eines Daten-Paketes dar und wird demzufolge auch nicht geschrieben. Nach der Bitgruppe &quot;00&quot; folgt das RLE-Paket.
Beispiel:
Bitstream ''(1)'' (01)(10)(11)(01)(00)
Opt. Bit 4 Bitgruppen und die
nach Header abschließende 00-Gruppe
Es werden die Bitgruppen &quot;01&quot;, &quot;10&quot;, &quot;11&quot; und &quot;01&quot; geschrieben.
===Beispiele===
Da nun auf ein Paket das jeweilig andere immer folgt, kann man diese Pakete natürlich optimal kombinieren. Es folgen zwei Beispiele, eins mit dem RLE-Paket anfangend, eins mit dem Daten-Paket anfangen.
'''Beispiel: RLE-Paket'''
[17](X)(0) (11110)(00110) (10)(10)(01)(11)(01)(00) (110)(111)
Opt. Bit RLE-Paket----- Daten-Paket------------- RLE-Paket-
0x1F + 0x06 0x07 + 0x07
-1 Reihe mit 7 Bytes, d.h. 0x38 Bitgruppen
-1. RLE-Paket : 0x1F + 0x06 = 0x25
-1. Daten-Paket: 0x05 Bitgruppen
-2. RLE-Paket : 0x07 + 0x07 = 0x0E
-----------------------------------
0x25 + 0x05 + 0x0E = 0x38; Bitgruppen sind erfüllt
'''Beispiel: Daten-Paket'''
[11](X)(1) (10)(11)(01)(11)(10)(11)(00) (0)(1)
Opt. Bit Daten-Paket--------------- RLE-Paket
0x01 + 0x01
-1 Reihe mit 1 Byte, d.h. 0x08 Bitgruppen
-1. Daten-Paket: 0x06 Bitgruppen
-1. RLE-Paket : 0x01 + 0x01 = 0x02
-----------------------------------
0x06 + 0x02 = 0x08; Bitgruppen sind erfüllt
==Auswertung==
In der Auswertung gibt es zusätzlich zu den drei Auswertungsmethoden noch zwei unterschiedliche Arten die Daten abzugleichen. Die Abgleichungsarten werden zuerst erläutert, dann bei welcher Auswertung (eins, zwei oder drei) sie eingesetzt werden.
===Abgleichungsart 1===
Diese Abgleichung benutzt zweimal 2 Tabellen um auszuwerten. Eine Tabelle für die Spiegelung und eine ohne Spiegelung. Der Ablauf ist num immer folgender: Es werden der Reihe nach immer 4 Bit aus dem abzugleichenden RAM ausgelesen, zuerst die hohen 4 Bit eines Bytes, danach die unteren 4 Bit. Wichtig ist, dass vertikal gelesen wird, also immer erst alle vollen Bytes einer vertikalen &quot;Spalte&quot; des jeweiligen RAMs, danach erst das jeweils zweite Byte usw.&lt;br&gt;
Das [[Meta]]-Codebyte im Ram ist so verschlüsselt, dass es sich aus zweimal 4 Bit so zusammensetzt, dass jeweils ''3 Bit'', die 4 Bit Grafikdaten bestimmen, und ''1 Bit'', das die zu wählende Bytehälfte vorbestimmt.
[Meta-Codebyte]
(4 Bit) (4 Bit)
(XXXY) (XXXY)
--------------&gt; Leserichtung
XXX ist der Index in der Tabelle und Y verweist auf die unteren/oberen 4 Bit aus der Tabelle bei Bit &quot;0&quot;/&quot;1&quot;.
Die Tabelle wird anhand der zuletzt geschriebenen 4 Bit ermittelt. Ist dieses für ungespiegelte Grafiken ungerade bzw. für gespiegelte Grafiken größer als 8, so wird die Tabelle 2 anstelle von Tabelle 1 genommen. Für den ersten eingelesenen Wert ist der zuletzt geschriebene Wert auf 00 voreingestellt.
{|
!Tabelle 1&lt;br&gt;ungespiegelt
|
{|border=&quot;2&quot; cellspacing=&quot;0&quot; cellpadding=&quot;4&quot; rules=&quot;all&quot; style=&quot;margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse; background-color:#F9F9F9; font-size:95%; empty-cells:show; text-align: center&quot;
|'''Index'''
| 0x00
| 0x01
| 0x02
| 0x03
| 0x04
| 0x05
| 0x06
| 0x07
|-
|'''Byte'''
| 0x'''0'''1
| 0x'''3'''2
| 0x'''7'''6
| 0x'''4'''5
| 0x'''F'''E
| 0x'''C'''D
| 0x'''8'''9
| 0x'''B'''A
|}
!Tabelle 1&lt;br&gt;gespiegelt
|
{|border=&quot;2&quot; cellspacing=&quot;0&quot; cellpadding=&quot;4&quot; rules=&quot;all&quot; style=&quot;margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse; background-color:#F9F9F9; font-size:95%; empty-cells:show; text-align: center&quot;
|'''Index'''
| 0x00
| 0x01
| 0x02
| 0x03
| 0x04
| 0x05
| 0x06
| 0x07
|-
|'''Byte'''
| 0x'''0'''8
| 0x'''C'''4
| 0x'''E'''6
| 0x'''2'''A
| 0x'''F'''7
| 0x'''3'''B
| 0x'''1'''9
| 0x'''D'''5
|}
|-
!Tabelle 2&lt;br&gt;ungespiegelt
|
{|border=&quot;2&quot; cellspacing=&quot;0&quot; cellpadding=&quot;4&quot; rules=&quot;all&quot; style=&quot;margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse; background-color:#F9F9F9; font-size:95%; empty-cells:show; text-align: center&quot;
|'''Index'''
| 0x00
| 0x01
| 0x02
| 0x03
| 0x04
| 0x05
| 0x06
| 0x07
|-
|'''Byte'''
| 0x'''F'''E
| 0x'''C'''D
| 0x'''8'''9
| 0x'''B'''A
| 0x'''0'''1
| 0x'''3'''2
| 0x'''7'''6
| 0x'''4'''5
|}
!Tabelle 2&lt;br&gt;gespiegelt
|
{|border=&quot;2&quot; cellspacing=&quot;0&quot; cellpadding=&quot;4&quot; rules=&quot;all&quot; style=&quot;margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse; background-color:#F9F9F9; font-size:95%; empty-cells:show; text-align: center&quot;
|'''Index'''
| 0x00
| 0x01
| 0x02
| 0x03
| 0x04
| 0x05
| 0x06
| 0x07
|-
|'''Byte'''
| 0x'''F'''7
| 0x'''3'''B
| 0x'''1'''9
| 0x'''D'''5
| 0x'''0'''8
| 0x'''C'''4
| 0x'''E'''6
| 0x'''2'''A
|}
|}
Die Werte, die gelesen werden, wenn Y im Code (siehe oben) gesetzt, also &quot;1&quot; ist, sind '''fett''' markiert.
===Abgleichungsart 2===
Die zweite Abgleichungsart ist etwas einfacher als die erste, jedoch wird hier im Gegensatz Zeilenweise, also nicht vertikal in den &quot;Spalten&quot; gelesen. Hinzu kommt, dass die [[Meta]]-Codebytes in keinster Weise verschlüsselt sind, sondern bloß einen Index in der Spezial-Tabelle für diese Abgleichungsart darstellen.
[Meta-Codebyte]
(4 Bit) (4 Bit]
(XXXX) (XXXX)
--------------&gt; Leserichtung
XXXX ist der Index in der Tabelle.
Beim Lesen der Tabelle ist folgendes zu beachten: Für die ersten aus dem RAM gelesenen 4 Bit werden die niedrigwertigen 4 Bits der Listenausgabe die höchstwertigen Bits des zu setzenden Grafikbytes. Für die zweiten aus dem RAM gelesenen 4 Bit werden zwar auch nur 4 Bits gelesen, diese werden aber auch zu den niederwertigen 4 Bits der Ausgabe.
{|
!Tabelle
|
{|border=&quot;2&quot; cellspacing=&quot;0&quot; cellpadding=&quot;4&quot; rules=&quot;all&quot; style=&quot;margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse; background-color:#F9F9F9; font-size:95%; empty-cells:show; text-align: center&quot;
|'''Index'''
| 0x00
| 0x01
| 0x02
| 0x03
| 0x04
| 0x05
| 0x06
| 0x07
| 0x08
| 0x09
| 0x0A
| 0x0B
| 0x0C
| 0x0D
| 0x0E
| 0x0F
|-
|'''Byte'''
| 0x00
| 0x08
| 0x04
| 0x0C
| 0x02
| 0x0A
| 0x06
| 0x0E
| 0x01
| 0x09
| 0x05
| 0x0D
| 0x03
| 0x0B
| 0x07
| 0x0F
|}
|}
===Auswertung 1===
Bei der Auswertung 1 wird denkbar einfach lediglich zunächst RAM1, danach RAM2 mit der Abgleichungsart 1 abgeglichen.
===Auswertung 2===
Es wird der zuerstverwendete Ram, also 1.RAM mit Abgleichungsart 1 ausgewertet, danach wird 2.RAM [[Binäre_Operatoren#Xor|XOR]] 1.RAM an den Platz des 2.RAM geschrieben. Sollte die Spiegelung aktiviert sein, so wird vor dem [[Binäre_Operatoren#Xor|XOR]] der 2.RAM mit Abgleichungsart 2 ausgewertet und dann ge[[Binäre_Operatoren#Xor|XOR]]t.
===Auswertung 3===
Bei der Auswertung 3 wird zunächst der 2.RAM so mit Abgleichungsart 1 verarbeitet, als ob keine Spiegelung aktiv wäre (also ungeachtet ob die Spiegelung aktiviert ist). Danach wird wie in Auswertung 2 verfahren, also inklusive der Spiegelung.
[[Kategorie:Technik]]</text>
</revision>
</page>
</mediawiki>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment