5.2 Compression

Compression is seen in all areas of ROM hacking and will continue to be seen as developers brush up against limits of bandwidth and storage space all while having more CPU cycles at their disposal. There are countless permutations and implementations but broadly speaking the two basic types will be lossless and lossy. Both types are named for their dominant characteristic; lossless able to compress and reconstruct an exact copy of the original file and lossy taking an original and losing some hopefully irrelevant or less noticeable information in an attempt to make the data smaller (in sound for instance the human ear will certainly not be able to hear above 30KHz so if you had captured everything up to 50KHz and then lose all the sound above 30KHz16 you will save some space at the cost of lost data). There are things aimed at real time compression (real time communications of data generated on the spot such as a voice call) and things aimed at compression for storage and later transfer and the latter is what ROM hacking tends to deal with the most.

Compression is not perfect so if you find yourself reverse engineering compression do not be surprised to see a compressed section that is the same length as the piece it compresses (although this can also be a technique to allow a bigger range by means of a double reference) and equally do not be surprised if you see a way the compression could be further improved both within and outside the limits of the format.

5.2.1 Lossy

Various DS games have been seen to use lossy methods to encode audio, graphics and sometimes video. For the most part these will be known methods like JPEG for images, various audio formats and game related video formats (although a complete description of the VX and mods video formats aka act imagine/mobiclip is still pending) with the most complex part of it being if the existing format is wrapped in something. This is probably for the best as lossy compression draws from a whole host of fields including things as far afield as psychology and biology and tends to make for complex formats.

5.2.2 Lossless

Lossless compression will manifest in one of four basic ways, although the first three will be the most common.

Dictionary

(sometimes called referencing) - here the compression will reference an earlier part of the file (be it the whole file or a “sliding window”). LZ compression and the special case of it known as run length encoding (RLE), which was popular back on earlier systems, are the two main types. Here the file will reference a premade dictionary of terms (rare in modern implementations) or use the file itself to generate a dictionary which, depending upon the method, will either be the file itself or shipped with the file.

Statistical

Huffman is the main type of compression to use this sort of technique. The idea is the compression uses reference values of various lengths to refer to sections of original file with the most common types getting shorter values and the less common types getting longer values.

Filtering

depending upon how you look at it this is not really a compression and more of an encoding but the GBA and DS hardware treat a version of it much like compression (BIOS functions to handle it) so it is here. The graphics format known as NDS 1bpp (1 bit per pixel) uses the idea that even if it eventually gets turned to 4bpp if you have a two colour image (usually a font) you can be assured that each pixel be one of two values and as such can be turned into a simple 1 or 0.

Predictive

Technically another statistical method but it relies on the idea that certain parts of the file might be predictable and is usually very application specific.

Christina Zeeh’s introduction to compression has a fair amount of background information on the history and background of the LZ compression family and others.

Additionally, and as has hopefully be made clear by this point, game developers and coders in general are encouraged to reuse existing concepts and values so tiles may get used repeatedly (half a body might have twenty versions of the top half for various animations), 3d in general is well suited to it, pointer level text compression was mentioned, dual tile encoding does have uses, fonts have been seen to reuse parts, the whole notion of the palette/texture/material swap… so although these general use compression methods are a key concept in hacking, especially of modern handheld games, be prepared to encounter methods more useful to games in general.

5.2.3 Basic theory of the actual implementations

This section will detail the basics behind the most common compression methods seen on the GBA and DS and some techniques that can be used to handle them. Actual programming level discussion is reserved for the next section. Note that custom compression has been seen several times in the wild but it is usually not that different to regular compression (it is hard to define a useful type of compression that is truly new), this means that even though most existing tools will fail if they are set upon custom compression that as most are open source it should not be that hard to get them running again once you figure out the minor differences between the methods.

GBA compression More so than the earlier consoles, which tended to have the occasion bit of RLE and later on some LZ, the GBA took to compression in a big way and it became a fixture of the system. Various things were made to handle it in the hardware side of things and from the hacker perspective. headspin’s guide details a lot about compression and how it can be used on the GBA and that feeds quite a bit into the DS as well.

SWI calls (BIOS supported compression) The GBA (and DS for that matter) feature some basic decompression algorithms as part of the readily accessible BIOS, this means anything can call the BIOS functions to decompress the files into memory. Naturally the debugging grade (and for that matter some more general use) emulators can watch and list any BIOS calls and allow you to get a rough idea of where files are, how they are compressed and even when in the game they are reached for, many tools compression tools can then use these lists to extract files.

VRAM and WRAM safe The VRAM is the video ram and the WRAM is otherwise known as the main memory or work ram. With the GBA cart being memory mapped on the GBA things could be copied right into the VRAM by various methods but the VRAM carried a restriction that all destination addresses had to be aligned to 16 bit aligned (WRAM could do 8 bit). This also meant that any writing, say from decompression, had to occur 16 bits at a time and necessitated VRAM safe compression methods be devised and implemented.

Searching and dealing with compression There are three methods of dealing with compression on the GBA

  1. SWI logs
  2. Assembly/known locations
  3. Compression searching

The GBA has several decompression algorithms built into the BIOS and by watching when they are called (logging of SWI calls is available in VBA among other things) the locations in the ROM will tend to included. Not all compression is BIOS compatible and not all BIOS compatible compression uses the BIOS functions to decompress it (being housed in the BIOS they are something of a tradeoff between size and speed so developers sometimes wrote their own functions). Should SWI logs be available then several of the tools mentioned in the compression tools section will be able to parse them and extract things accordingly (GBA Multi DeCompressor being one of the main ones), or you can hand parse them and direct a tool to do it.

Known locations is fairly obvious and the idea runs if someone before you has found the locations it is fairly simple to direct a tool at them (or in the case of some games the tool may have already been made). Assembly may well have been used to get to know locations though and it is usually a minor tweak on the standard tracing technique (tracing is covered in a little while) of finding something in ram and working backwards from there to see what put it in there and if it had a stop for or did decompression along the way. This way if a custom decompression method is used then the basic idea will be apparent to person doing the tracing (custom usually means a slightly different flag, flag meanings and number of bits over which it operates rather than a whole new method of compression).

Compression searching will probably become more obvious after the worked example and relies on the idea that the compressed file will usually start with 10 hex in the case of GBA/DS BIOS compatible LZ and after that there will be flags and similar mechanisms the compression method uses to function/allow decompression. Various tools have been made but as far as most people working in GBA are concerned

NLZ-GBA Advance (which doubles up as a graphics editor)

PIC

unLZ-GBA

PIC

Crystaltile2

Crystaltile2 also features compression searching support and can do it for custom flags of various forms as well. It is available on the tools pulldown menu of the hex editor window but be warned that mass decompression has a tendency to make the program crash if it encounters too many false hits for compression.

PIC

PIC

Lz77Restructor 2

A relatively new tool but a nice one; you may want to play with the filters option as it can restrict by pointers, widths, sizes and as well as deal with text (using custom tables if necessary).

PIC

GBACrusher Decompression tools were fairly common and they did a fair bit of compression as well but for most the dominant tool for generated compressed files was known as GBA Crusher. It should be able to do all the BIOS compatible methods.

DS compression Compression took off on the DS but owing to it being reasonably well implemented few companies ever made their own custom compression formats in the traditional sense and just used ones from the SDK or other known formats so it went from being the bane of ROM hackers to just a minor irritation.

SWI aka BIOS calls The DS BIOS has support for various forms of compression and new to the DS compared to the GBA was the idea of callback which helped work around the DS ROM not being mapped to memory (gbatek calls it slow but it allows larger files to be decompressed without the developer having to provide a checking function to see when parts have been decompressed and the next one can be fed into it).

DS firmware compression Not really relevant to ROM hacking but the DS firmware has all sorts of compression stacked together in it and the source code makes for nice reading.

Download from Chishm’s website

Types You will often see mention of types of compression in DS ROM hacking discussion and this refers mainly to various implementations of LZ compression seen on the DS. They are so named because the files using the type of compression usually start with the number (in hexadecimal) but it is also worth noting compression will often also be indicated by the file name (typically LZ in the name or the name/extension ending with an underscore).

  • LZSS - more or less what the GBA/DS BIOS use and other common compression methods seen on both the GBA and DS use.
  • Type 10 - this is the classic GBA WRAM safe LZSS based BIOS compression and only one supported by SWI calls.
  • Type 11 - another LZSS based compression which appeared a few years into the DS lifetime and is capable of achieving better compression than type 10 at the cost of some speed.
  • Type 40 - probably the newest type of LZSS compression seen on the DS. The first notable use was in Golden Sun Dark Dawn although 11 is still used extensively.
  • Type 30 - this tends to indicate RLE
  • LZE- mainly seen in a couple of games in the Luminous Arc series.
  • LZ77 - not seen so much any more (the 77 referring to the year in which it was cooked up) but some people erroneously refer to all LZ or LZSS compression as LZ77, it is very similar to LZSS though and nobody really gets confused if you conflate the two.
  • Binary/backwards/bottom compression (sometimes dubbed BLZ and not to be confused with LZB)- DS binaries (mainly just the ARM9 and ARM9 overlays unless it is a download play component) use a file end first compression that is still LZ but done in reverse for various reasons. Decompression is widely supported nowadays and compression can be done too. This compression is file wide but there have been instances of compressed files included within the DS binaries.
  • Huffman - (tends to be 20 to start) where LZ and most others are concerned with the immediate value in front of them and if it is related to an earlier section this considers the file as a whole and assigns the more common sections a shorter reference value and the less common ones a longer reference value.
  • RLE. A special/simple case of LZ that works on a given string or section and just compresses repeated values for as long as they run. Not as effective as LZ and others but very fast and so quite common on older systems.
  • Yaz0. Named for the ASCII magic stamp it starts with and one not tending to be seen on the DS. It is in many ways a slightly enhanced version of RLE (not quite enough to be called proper LZ) but it is seen quite a lot on the gamecube, wii and later Nintendo handhelds. Quite often used with the u8 archive format that u8tool can parse. There is a related format for the BIOS called Yay0.
  • Packing and filtering. As mentioned in graphics the GBA and DS BIOS allows for filtering of data to make 1BPP and runs where there is a single value increase each length a run of the same value which compresses far more with conventional compression methods.

Various tools have been made to handle compression with two of the big ones as far as the DS is concerned being DSDecmp and Cues GBA/DS compressors although there are multiple methods to effect decompression on files.

5.2.4 Compression at hexadecimal level

This section will focus mainly on LZ compression as that is the most common and decoding it is fairly illustrative of the techniques and concepts involved. Compression often radically alters the file at hexadecimal level but it will usually be implemented in a given manner.

  • Magic stamp. Mainly on the DS formats or home consoles rather than the older consoles. Can be hexadecimal or ASCII/unicode.
  • Flags. Mainly seen in LZSS these are little flags inserted at compression time to tell the decompression tool if a section is compressed or not.
  • Compression instruction (usually where is the file/what is it called in the dictionary and how long to read the previous reference for).

Some implementations stick flags here and there in the file for various reasons although usually as a message to the decoder to skip this section or note it for later.

The instruction component is usually a two part operation merged into one. One part will be the length of the previously seen string and the next will be the location of it (either as an address or reference). Common deviations from the method discussed above include the order of length and location can be swapped, how many bits will be used for each can be changed, what sort of alignment is used and how things are addressed. Remember LZ is often dubbed a sliding window compression so when operating on a big file (or when limited to a compression instruction with few bits for the location component) the start address can vary throughout decompression and will not always be at the start of the file.

Worked example The following is the text output from simply running the gbacrusher program from WRAM LZ.

PIC

The first part is not strictly necessary for manual decompression but it is nice to have and quite useful when programming a decompression function.

The 10 hex part is a flag which indicates compression and the 4702 part is a flipped version of the length of the original file (247 as you can see from the top window).

A search was done for every 00 value as in LZSS they (usually) correspond to the flags to tell the decompression tool if it needs to do something or not (not for 00). They are every 8 bytes in this instance although some implementations can use 16 bytes or something else entirely. Doing this could well make the file longer but once more compression is far from flawless and the tradeoff is useful for speed and ease of use.

Back on topic the first four sections have no repeats (this is quite common and gives rise to the files getting less readable as time goes on). When decoding delete every 00 flag as you copy it.

The fifth one (highlighted) though has “ersion” from Version repeated. LZSS differs from some other implementations of LZ by having the first non compressed value (in this case a byte) encoded as usual. The 40 is just a flag.

3009 - the first 4 bits of that are how much to decompress less 3

Making the number 3 less means it could theoretically have 3 more bytes one day and as the number will not be less than 3 (2 bytes for the compression flag means a minimum of 3 bytes to be worthwhile) it make sense to start counting from 3.

The second 4 bits are 0, technically these are the most significant bits but as the file is small they are not present yet.

The next 8 bits are one less than the distance to count backwards (in this case 9 meaning A hex) which starts from the compression instruction value (or if you prefer the exact value back from the “next non decoded” symbol.

PIC

The next few blocks are uncompressed but another compressed chunk soon appears

PIC

A020

A bytes + 3 = D hex long

20 = 21h back.

Repeat as appropriate until file is decoded.

An aside on editing and viewing compressed files Editing a compressed file at hexadecimal level is possible and some find it tempting to do however you never know if a fragment will be used later in the file unless you check (which usually means you decompress the whole file anyway) and although it is fairly obvious with text if you are dealing with graphics or a function that operates on an unaligned bit level it is worse so it is usually best to decompress, edit and recompress.

Equally compression when done to text usually means most of it is still fairly readable (especially as it tends to be aligned to bytes or higher) and to a slightly lesser extent so are some levels and early parts of headers (give or take flags) meaning although it renders a lot of graphics near unreadable a lot can be seen and guessed at without having to deal with compression.

Working around compression Just because a file was compressed in the original game does not mean it has to be compressed in the end hack you make. It is not always as simple as just turning up with an uncompressed file, though this can work for proper functions that attempt to detect compression and act accordingly. Sometimes it can be as simple as changing a flag somewhere (recall the example from El Tigre) but it can also be a fairly basic assembly hack, speaking of assembly and binaries the DS binary compression tends to be noted with a flag in the overlay table, to this end you can clear this flag (1 = compressed, 0 = uncompressed http://gbatemp.net/threads/recompressing-an-overlay-file.329576/#post-4387691). In the case of an assembly hack the general idea is compression has a source and a destination with operations beyond straight copying in between but if you replace it with regular copying all will work as it was. The slightly more crude workaround is figure out the uncompressed flags (harder but not impossible with RLE and Huffman) and insert them throughout the file and another take on it can be seen in some of Labmaster’s work in dealing with compression in the GBA game Golden Sun.

Equally if you are dealing with a custom compression the data will usually be uncompressed to run so you can often snatch things from the ram and work around the compression later or use it to help work around the compression for if it is just a slight tweak on an existing method which you already know this can practically give the game away.

  1. Do recall that sampling theory means you sample at twice the rate you want to represent so the sample rate to represent sounds of 30KHz needs to be 60KHz.↩︎