View source for Enigma compression

'''Enigma compression''' is a compression format used in [[Mega Drive]] games. It is a variant of run length encoding, and is used primarily to compress plane mappings, which usually contain long sequences of repeated words.

== Compression Theory ==
Enigma-compressed data begins with a 6-byte header:
*Byte 0: The number of bits in an inline copy value (explained later)
*Byte 1: Bitfield of the form 000PCCVH, where P is the high priority flag, CC is added on to the base palette line to give the resultant palette line, V is the vertical flip flag and H is the horizontal flip flag. The number of bits set in this bitfield determines the length of the inline render flags bitfield (explained later). Note that this bitfield merely indicates to the decompressor that these bits may be set, it does not force them to be set by itself.
*Word 2: Incremental copy word (explained later)
*Word 4: Literal copy word (explained later)

Following this header is the format list. Each entry in this list consists of two or three type bits followed by four repeat count bits, and possibly one or more inline render flags bitfield and copy value pairs. The first bit of each list entry determines the number of type bits - if it's clear, the first two bits are interpreted as type bits and the next four as repeat count bits, and if it's set, the first three bits are interpreted as type bits and the next four as repeat count bits. The type bits are as follows:
*00  - copy the incremental copy word repeat count + 1 times, add 1 to the word after each copy
*01  - copy the literal copy word repeat count + 1 times
*100 - copy inline value repeat count + 1 times
*101 - copy inline value repeat count + 1 times, add 1 to value after each copy
*110 - copy inline value repeat count + 1 times, subtract 1 from value after each copy
*111 - if repeat count is $F (%1111), terminate decompression. Otherwise, copy the next inline value and repeat repeat count + 1 times

When the type is 100, 101 or 110, the repeat count bits will be followed by a single inline render flags bitfield and copy value pair. When the type is 111, the repeat count bits will be followed by repeat count + 1 inline render flags bitfield and copy value pairs. The length of the inline render flags bitfield in bits is the same as the number of bits set in byte 1 of the header. This bitfield is used in conjunction with byte 1 of the header to determine the upper five bits of the inline copy value. As an example, if byte 1 is $13, it indicates that the high priority, vertical flip and horizontal flip flags may be set, and therefore the inline render flags bitfield will be three bits long. If the inline render flags bitfield is %001, only the horizontal flip flag will be set, if it's %010, only the vertical flip flag will be set, if it's %011, both flip flags will be set, and so on and so forth. After this bitfield is the actual copy value, the length (in bits) of which is determined by byte 0 of the header. This copy value is combined with its render bits to form the final copy value.

Because Enigma compression is usually used on plane maps, the decompressor also takes an additional parameter - the starting art tile. Like all Mega Drive VDP pattern indices, this is a bitfield of the form PCCV HAAA AAAA AAAA, where P is the priority flag, CC is the base palette line, V is the vertical flip flag, H is the horizontal flip flag and AAA AAAA AAAA is the starting tile index, i.e. the VRAM offset of the starting pattern divided by $20. The starting art tile is added to each decompressed word before it is copied to the output buffer.

As an example, consider the following compressed data, when the starting art tile is 0:

07 0C 00 00 00 10 05 3D 11 8F E0

The header indicates that each inline copy value is 7 bits long, each inline render flags bitfield is 2 bits long and determines the palette line bits, the incremental copy word is $0000, and the literal copy word is $0010. The format list, when expressed in bits, one entry at a time, is:

*%000001: Type bits are %00, repeat count is 1. Copy the incremental copy word twice, increment after each copy
*%010011: Type bits are %01, repeat count is 3. Copy the literal copy word four times
*%1101000100011000: Type bits are %110, repeat count is 8. Inline render flags bitfield is %10, indicating that 2 should be added to the base palette line (in this case 0), and inline copy value is $18. Combine the two and copy it nine times, decrementing after each copy.
*%1111111: Type bits are %111, repeat count is $F. Terminate decompression.

The final decompressed data is thus:

00 00 00 01 00 10 00 10 00 10 00 10 40 18 40 17 40 16 40 15 40 14 40 13 40 12 40 11 40 10

If the starting art tile had instead been $1000, the data would have been:

10 00 10 01 10 10 10 10 10 10 10 10 50 18 50 17 50 16 50 15 50 14 50 13 50 12 50 11 50 10

== Uses ==
Enigma compression is used to compress:
*Various Mega Drive games, including all Sonic games - plane maps 
*''[[Sonic the Hedgehog]]'' - 16x16 [[block mappings]]
*''[[Sonic the Hedgehog]]'' - special stage layouts

[[Category:Data Formats]]