Asobo Arithmetic Coding Compression

Asobo uses Arithmetic Coding (AC) to compress save game data. RTTI indicates that the AC implementation in FUEL is a modification of the one presented at the end of "Arithmetic Coding revealed - A guided tour from theory to praxis". Both Order 0 and Order 1 AC are present in the executable; however, the Order 0 model appears to be unused as the value which selects between the two when saving and loading is hardcoded to use the Order 1 model when handling save games.

There are several major differences between Asobo's implementation and the one presented in "Arithmetic Coding revealed - A guided tour from theory to praxis". The most notable of which is that the paper only implements the Order 0 model. Less notably, Asobo does not use a sentinel symbol to represent the end of the input. Instead, the compressed data is prefixed with the decompressed size and execution completes when that number of bytes has been written to the output. However, the sentinel check is still present in the decoder even though the encoder never writes it. This is potentially a holdover from the paper's implementation. Other minor differences include different constant values for the ranges and multiple frequency count arrays.

The last byte written to the output when compressing is uninitialized garbage. Therefore, the compression algorithm is nondeterministic. i.e. decompressing and recompressing the same file may yield different results due to this last byte being garbage. This is due to an off-by-one error. The size of the output buffer should be the size of the compressed data plus 8 to accommodate the size information prefix. However, it is actually the size of the compressed data plus 9. When copying the compressed data into this buffer the number of bytes copied is the size of the output buffer minus 8 which should be the size of the compressed data. However, it is actually the size of the compressed data plus 1 due to the previous error. This leads to an out-of-bounds read of uninitialized data. Additionally, the error was perpetuated in the loader which expects this extra byte to be there but does not care about its value. It is unclear if this was intentional, but since there is an out-of-bounds read, I am content with calling it an error. The reference implementations append a null byte to the end of the output instead of a garbage value. This does not affect the game's ability to load the save file since it is truly a garbage byte.

Reference Implementations

The Asobo-ArithmeticCoderC repository contains a minimal C++ implementation of Asobo's Arithmetic Coding Compression. The fuel-save-editor repository contains a Nim implementation of the algorithm as part of the save editing functionality.

References

• Arithmetic Coding revealed - A guided tour from theory to praxis