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.

Sprite size

As mentioned above, the size of each valid Pokémon sprite is stored in two ways:

• As the first byte of the compressed data stream, with the high nybble indicating the width and the low nybble indicating the height. For example, for a 5×5 sprite, the value of this byte will be 0x55.
• For front sprites, there is a byte indicating the sprite size in the base stats data structure, with the high nybble indicating the height and the low nybble indicating the width (this is the opposite way around compared to the other byte, although for valid Pokémon sprites this does not actually matter since they all have equal width and height). Back sprites are always assumed to be 4×4 before scaling.

For glitch Pokémon, those two sizes often mismatch. The size indicated first byte of the compressed data stream is often called the actual sprite size, and the size indicated by the byte in the base stats data structure is often called the base stats sprite size. The front and back sprites for a glitch Pokémon each has its own actual sprite size, but there is only one base stats sprite size for the front sprite. Pokémon from the same family always share the same base stats sprite size, but their sprites may be different since those sprite data may be in different banks (even though they share the same two-byte pointer), in which case each sprite will have its own actual size.

The actual sprite size determines whether the sprite causes memory corruption, and how much. For an actual sprite size of w×h, the sprite decompression routine will always read data from the input stream until it has output (w×8)×(h×8) bits, i.e., w×h×8 bytes, for each of the two bit planes. Each bit plane is written to a contiguous region in the memory, starting from sSpriteBuffer1 and sSpriteBuffer2 respectively, meaning that they will overlap each other if w×h > 49. Then the bit planes are unpacked by operating on the same memory regions. Both decoding and unpacking are handled with double loops, and both w and h must be in the range of 0–15 since they are nybbles, so the only relevant possibility of arithmetic overflow is that when (w×8) and/or (h×8) are 0, they are treated as if they were 256, or equivalently that when w and/or h are 0, they are treated as if they were 32.

Since the distance between sSpriteBuffer2 and the start of the Hall of Fame data is 392+256 = 648, Hall of Fame corruption will happen when w×h×8 > 648, i.e., w×h > 81. Meanwhile, WRAM corruption will only happen when w×h > 926, which is only possible for a sprite with actual size 0×0 (e.g., Yellow MissingNo.), where both w and h are treated as 32. If WRAM corruption does happen, it will affect WRAM addresses up to $C30F, which contain variables used by the sound engine as well as some sprite data. Corruption of those data is the causes of sound and/or sound bank corruption and the walking characters effect respectively.

YouTube videos

YouTube video by Retro Game Mechanics Explained

YouTube video by Retro Game Mechanics Explained