Sprite decompression (Generation I)

This article is incomplete. Please feel free to add any missing information about the subject. It is missing: details of important steps.

In Pokémon Red, Blue, and Yellow, all front and back sprites of Pokémon and Trainers are stored in a compressed form in the ROM, and are decompressed only when used. The compression format first uses one of several different forms of differential encoding to increase the number of zero bits in the data, then encodes the data using a run-length encoding (RLE) on zero bits. The decompression routine makes use of part of SRAM bank 0 as a buffer, meaning that it needs to unlock the SRAM beforehand, but it never locks the SRAM afterwards, making it easier for glitches to corrupt SRAM bank 0 (and to a lesser extent, the SRAM in general). Furthermore, the decompression routine does not check the size of the sprite adequately, so when decompressing sprites of glitch Pokémon or Trainers, the routine itself can easily overflow the buffer and cause various memory corruptions, most famously in the Hall of Fame (which is stored in SRAM bank 0 after the buffer), but also in the WRAM if the sprite is large enough.

Overview

Buffer usage

The sprite decompression routine makes use of a region at the beginning of SRAM bank 0 as a buffer, which is further divided into three buffers, each of size 7×7×8 = 392 bytes (0x188 bytes in hexadecimal), meaning that each is able to hold (7×8)×(7×8) bits, which is equal to the number of pixels in the largest valid sprite (with 7×7 tiles) in the game. Since Game Boy sprites are in 4 colors (i.e. 2 bits of data per pixel), it takes two such buffers to hold the complete decompressed data for a sprite, and a third buffer is used to facilitate manipulation of the decompressed data. Furthermore, there is an unused 256-byte space after the buffers and before the Hall of Fame data, which means that some glitch sprites with size only slightly larger than 7×7 won't corrupt the Hall of Fame. The memory addresses of these buffers are shown below:

sSpriteBuffer0	sSpriteBuffer1	sSpriteBuffer2	Unused space
$A000 – $A187	$A188 – $A30F	$A310 – $A497	$A498 – $A597

Steps

The decompression routine works on a stream of input bytes (which is for the most part regarded as a stream of bits), and consists of the following steps:

0. Clear sSpriteBuffer1 and sSpriteBuffer2, filling them with zeros.
• This step is important because the run-length decoding procedure writes bits to the buffers in a peculiar order (the data is stored in vertical columns of 2 pixels each, but each byte represents a horizontal row of 8 pixels, so only 2 bits out of 8 in a byte is written each time) with bitwise OR, which assumes that those buffers start with zeros.
1. Determine the size of the sprite in pixels from the first byte of the input stream.
   • Notably, this is different from the byte indicating the sprite size in the base stats data structure (the latter byte is loaded into the RAM in wMonHSpriteDim), which is used only for centering the decompressed front sprite, as mentioned below.
2. Use a run-length decoding procedure to decode input data into two bit planes, each with the same number of bits as the number of pixels in the sprite.
   • The two bit planes are stored in sSpriteBuffer1 and sSpriteBuffer2 respectively. Which buffer is used first depends on a bit in the input stream.
   • For each bit plane, the decoding algorithm runs as an endless loop, consuming bits from the input stream, and writing bits to the buffer by calling the functions WriteSpriteBitsToBuffer and MoveToNextBufferPosition. The latter function is responsible for checking the current position against the sprite size, and when the appropriate number of bits are written to the buffer, it forcibly terminates the endless loop by removing the return address from the stack, and instead jumping to either the beginning of this step (to decode a second bit plane), or the beginning of the next step.
3. "Unpack" the two bit planes with a differential decoding procedure, which depends on a "unpacking mode" read from the input stream to the RAM incidentally in the previous step.
   • There are three different unpacking modes, but whether sSpriteBuffer1 or sSpriteBuffer2 is used first in the previous step will also affect the unpacking procedure, making 6 different ways of unpacking in total.

Immediately after decompression, the sprite is post-processed into an appropriate format, and loaded into the VRAM. This is not technically part of the decompression routine, but is so closely related that in practice it is an important part of the process:

4. Move the bit planes from sSpriteBuffer1 and sSpriteBuffer2 to sSpriteBuffer0 and sSpriteBuffer1 respectively, and in the process resizing them to 7×7 in a way depending on the type of the sprite:
• For front sprites, this involves putting them in the bottom center of the available 7×7 space. All valid front sprites are either 5×5, 6×6, or 7×7 (6×6 sprites are right aligned), which is also reflected in the aforementioned byte loaded into wMonHSpriteDim. The amount of empty space to add is computed with a formula, but the computation is prone to arithmetic overflow for invalid sprite sizes, which is responsible for the characteristic backwards "L" shape of the front sprite of MissingNo. and some other glitch Pokémon.
• For back sprites, this involves scaling them up by 2 (which causes back sprites to have a lower resolution than front sprites). All valid back sprites are 4×4, and when scaled up the last row and the last column of tiles in the result are discarded, resulting in a 7×7 size. (All those sizes are hardcoded in the function doing the scaling.)
5. Merge the 7×7 bit planes in sSpriteBuffer0 and sSpriteBuffer1 into a single chunk by interlacing the bytes, resulting in a format recognized by the Game Boy, and load the result into the VRAM.
   • The result of this step is stored in the buffers sSpriteBuffer1 and sSpriteBuffer2 concatenated. The function works backwards from the ends of the buffers, so that the output pointer only "catches up with" with the second input pointer at the end of the process, and will not overwrite input bytes prematurely.

YouTube videos

YouTube video by Retro Game Mechanics Explained

YouTube video by Retro Game Mechanics Explained