Anonymous user
Sprite decompression (Generation I): Difference between revisions
→Run-length decoding: Added details (maybe too much details).
(It's only R/B that doesn't unlock the SRAM after sprite decompression; Yellow does lock the SRAM.) |
(→Run-length decoding: Added details (maybe too much details).) |
||
Line 44:
== Run-length decoding ==
The rest of the input stream is consumed as individual bits, in big endian order (i.e. the most significant bit of each byte comes first in the stream)<ref>[https://github.com/pret/pokered/blob/e076ee0a40b2a21183e2cc535519e64b706b5407/home/uncompress.asm#L236-L250 The function to read the next input bit] (note that the <code>rlca</code> instruction rotates the input byte left ''before'' taking its least significant bit)</ref>. The overall layout of the data is:
* A single bit, indicating which sprite buffer to use first: 0 means that <code>sSpriteBuffer1</code> should be used first, and 1 means <code>sSpriteBuffer2</code> should be used first<ref>[https://github.com/pret/pokered/blob/e076ee0a40b2a21183e2cc535519e64b706b5407/home/uncompress.asm#L49-L52 The lines of code to read and store this bit from the input stream]</ref>. (As mentioned above, this will affect the differential decoding procedure later.)
* A ''data chunk'', which is the run-length encoding of a bit plane.
* Either 1 or 2 bits, indicating the unpacking mode to use later: "0" for mode 0, "10" for mode 1, and "11" for mode 2<ref>[https://github.com/pret/pokered/blob/e076ee0a40b2a21183e2cc535519e64b706b5407/home/uncompress.asm#L69-L75 The lines of code to read and store the unpacking mode (before decoding the second chunk)]</ref>.
* Another data chunk, encoding a second bit plane.
=== Chunk format ===
The run-length encoding works on pairs of bits from each bit plane. There are 4 possible bit pairs — 00, 01, 10, and 11 — and the differential encoding is designed to make 00 appear far more often than the other bit pairs, and mostly in long "runs". Therefore, each sequence of 00 pairs is encoded as a single 00 pair followed by a special encoding indicating the number of 00 pairs in the sequence, while the other three bit pairs are just encoded as themselves. As a small optimization, since the data is more likely than not to start with a run of 00 pairs, the first single bit of each chunk is special: A single 0 indicates that what follows should be interpreted as an encoded number of 00 pairs, while a single 1 indicates that the bit plane starts with non-00 bit pairs.<ref>An alternative interpretation is that the chunk consists of two kinds of alternating "packets": ''RLE packets'' that include only the encoded number of 00 pairs, and ''data packets'' that include any number of non-00 bit pairs and are terminated by 00. The first bit of each chunk then just indicates whether the chuck starts with a RLE packet or a data packet.</ref>
The special encoding for the number of 00 pairs is designed to be able to represent both small numbers and large numbers relatively efficiently. Each encoded number consists of two parts: The first part is any number (0 or more) of "1" bits followed by a "0" bit, and the second part is any bit string of the same length as the first part. The second part is interpreted as a binary number, with an offset added so that each positive integer is uniquely representable<ref>The offset is always 2<sup>''n''</sup>-1 where ''n'' is the length of each part, or alternatively ''L''+1 where ''L'' is the first part interpreted as a binary number, but the implementation in Generation I Pokémon games uses a [https://github.com/pret/pokered/blob/e076ee0a40b2a21183e2cc535519e64b706b5407/home/uncompress.asm#L267-L284 lookup table] to store the offset values up to ''n''=16.</ref>. For example, the bit string "{{color|red|0}}{{color|blue|0}}" encodes 1, "{{color|red|0}}{{color|blue|1}}" encodes 2, "{{color|red|10}}{{color|blue|00}}" encodes 3, "{{color|red|10}}{{color|blue|01}}" encodes 4, etc.
There is no terminator within the chunk itself; a chunk terminates when the decoder has written enough bits to fill the bit plane (the size of which being the same as the size of the sprite in pixels).
=== Bit order ===
The output of the decoder is written to the current sprite buffer in a peculiar order, presumably because the Game Boy hardware requires all graphics data to be in the format of 8×8 tiles. Specifically, this means:
* Each byte contains data for 8 contiguous pixels in the same ''row'' of pixels.
* Those bytes are best stored in ''column''-major order (i.e. bytes from the same 8-pixel column should be contiguous in memory). This ensures that the 8 bytes of data for the same tile are stored together.
On the other hand, the compression algorithm works best on unbroken rows or columns of pixels. Therefore, the compromise solution used in Generation I Pokémon games is:
* Each bit pair corresponds to two horizontally adjacent pixels (so that it falls in the same byte and is easier to write).
* The bit pairs are processed in vertical 2-pixel columns that span the height of the entire sprite. This means that as long as the decoder is processing the same 2-pixel column, after writing the same bit pair, the output pointer (<code>wSpriteOutputPtr</code>) only needs to be increased by 1. However, when moving from one 2-pixel column to the next, the decoder needs to adjust an "offset" variable (<code>wSpriteOutputBitOffset</code>) that controls which two bits of a byte should be written to, and either move the output pointer back to the start of the column, or move forward normally every time four 2-pixel columns (sharing the same bytes) have been processed.
Within each byte, all bits are written in big endian order, which corresponds to a left-to-right pixel order (although there are subroutines to flip the bit order in case the entire sprite needs to be flipped). This means both that within each non-00 bit pair, the bit read first is written in a higher bit<ref>[https://github.com/pret/pokered/blob/e076ee0a40b2a21183e2cc535519e64b706b5407/home/uncompress.asm#L81-L85 The lines of code to read a bit pair] (the bit read first is stored in register <code>c</code>, shifted left once, then combined with the bit read second with bitwise OR)</ref>, and that <code>wSpriteOutputBitOffset</code> counts down from 3 to 0<ref>The variable <code>wSpriteOutputBitOffset</code> is [https://github.com/pret/pokered/blob/e076ee0a40b2a21183e2cc535519e64b706b5407/home/uncompress.asm#L29-L30 initialized to 3], [https://github.com/pret/pokered/blob/e076ee0a40b2a21183e2cc535519e64b706b5407/home/uncompress.asm#L167-L171 decreased for each 2-pixel column], and [https://github.com/pret/pokered/blob/e076ee0a40b2a21183e2cc535519e64b706b5407/home/uncompress.asm#L179-L180 reset to 3 if it was already 0].</ref>, where a higher value means that the decoder writes to a higher bit pair within the byte<ref>[https://github.com/pret/pokered/blob/e076ee0a40b2a21183e2cc535519e64b706b5407/home/uncompress.asm#L211-L225 The lines of code handling each possible value of <code>wSpriteOutputBitOffset</code>]</ref>.
All write operations are done with the bitwise OR operation. This works fine for valid sprites because both sprite buffers are filled with zeros beforehand. For glitch sprites that cause memory corruptions, this means that they don't cleanly overwrite the memory regions corrupted, but instead allow the original values in those memory region to play a part in the corruption during the following differential decoding step.
== Differential decoding ==
| |||