Compression - Revision history

Dstien: /* Huffman coding */ Emphasis on the codebook being canonical.

2024-01-23T17:23:17Z

Huffman coding: Emphasis on the codebook being canonical.

← Older revision		Revision as of 19:23, 23 January 2024
Line 92:		Line 92:
	Huffman coding uses a binary tree to store data. When Huffman codes are read, each bit tells which branch to take when traversing the tree. If a leaf node is hit, we have found the code's symbol and can proceed with the next code. Frequently used symbols have shorter paths and thus takes up fewer bits in the source file.		Huffman coding uses a binary tree to store data. When Huffman codes are read, each bit tells which branch to take when traversing the tree. If a leaf node is hit, we have found the code's symbol and can proceed with the next code. Frequently used symbols have shorter paths and thus takes up fewer bits in the source file.

	The tree is stored by having two lists, one with symbols per level, and one with the alphabet. The alphabet is every possible symbol in the order they appear in the tree. The tree is built by going through each <tt>symbols_per_level</tt>. If there are symbols at the current level, consume them from <tt>alphabet</tt> and create leaf nodes. If there are no symbols, and there still are more levels to create, proceed to create left and right children nodes for the next level.		The tree is stored by having two lists, one with symbols per level, and one with the alphabet. The alphabet is every possible symbol in the order they appear in the tree. The tree is built by going through each <tt>symbols_per_level</tt>. If there are symbols at the current level, consume them from <tt>alphabet</tt> and create leaf nodes. If there are no symbols, and there still are more levels to create, proceed to create left and right children nodes for the next level. The codes are arranged [https://en.wikipedia.org/wiki/Canonical_Huffman_code canonically], meaning that the symbols in the alphabet are sorted by code length and symbol value. This makes it possible to decode the data without constructing and traversing the tree structure, instead relying on an offset table.

	The remaining data is the Huffman codes. Bit by bit is read to find leaf nodes in the Huffman tree whose symbols are appended to the output buffer. This is repeated until the output buffer has reached <tt>uncompressed_size</tt>.		The remaining data is the Huffman codes. Bit by bit is read to find leaf nodes in the Huffman tree whose symbols are appended to the output buffer. This is repeated until the output buffer has reached <tt>uncompressed_size</tt>.
Line 108:		Line 108:

	===== Offset table =====		===== Offset table =====
	As Stunts limits the prefix tables to 8 bit wide Huffman codes to save RAM, another ~~novel~~ optimisation is applied for codes that exceeds 8 bits. Prefixes for longer codes have the value <tt>0x40</tt> in the <tt>widths</tt> array, indicating that the current code is a prefix that needs further expansion. ~~For this purpose~~ Stunts uses two additional helper arrays: <tt>total_codes[tree_levels]</tt>, which has the total number of leaf nodes that exists in the tree up to each level, and <tt>code_offsets[tree_levels]</tt>, which for each level has a value that can be added to a code with the same level in order to get its index in the alphabet~~. This works because the codes are arranged [https://en.wikipedia.org/wiki/Canonical_Huffman_code canonically]~~. As a code's bit width corresponds to the code's level in the Huffman tree, the width can be used to compare the current code with the level's total by getting <tt>total_codes[current_width]</tt> for each extra bit read. If the code is smaller than the total number of codes encountered, it is a leaf node, and we get the symbol by adding the level's code offset to the code with <tt>alphabet[code + code_offsets[width]]</tt>. This is more laborious than the use of prefix tables for direct lookup, but it only applies to codes that are occurring less frequently in the input file.		As Stunts limits the prefix tables to 8 bit wide Huffman codes to save RAM, another optimisation is applied for codes that exceeds 8 bits. Prefixes for longer codes have the value <tt>0x40</tt> in the <tt>widths</tt> array, indicating that the current code is a prefix that needs further expansion. Benefiting from the canonical nature of the codebook, Stunts uses two additional helper arrays: <tt>total_codes[tree_levels]</tt>, which has the total number of leaf nodes that exists in the tree up to each level, and <tt>code_offsets[tree_levels]</tt>, which for each level has a value that is the level's offset in the alphabet minus the tree's total capacity up to each level, and thus can be added to a code with the same level in order to get its index in the alphabet. As a code's bit width corresponds to the code's level in the Huffman tree, the width can be used to compare the current code with the level's total by getting <tt>total_codes[current_width]</tt> for each extra bit read. If the code is smaller than the total number of codes encountered, it is a leaf node, and we get the symbol by adding the level's code offset to the code with <tt>alphabet[code + code_offsets[width]]</tt>. This is more laborious than the use of prefix tables for direct lookup, but it only applies to codes that are occurring less frequently in the input file, and it is still far more efficient than traversing a binary tree.

	==== Version differences ====		==== Version differences ====

Dstien: Rename formats to "DSI packing" and "EAC packing" as these specifications are valid for many DSI/EA games.

2024-01-23T16:46:08Z

Rename formats to "DSI packing" and "EAC packing" as these specifications are valid for many DSI/EA games.

← Older revision		Revision as of 18:46, 23 January 2024
Line 3:		Line 3:
	== Formats by game version ==		== Formats by game version ==
	{\| class="wikitable"		{\| class="wikitable"
	! rowspan=3 colspan=3 \| Game version !! colspan=4 \| ~~Stunts~~ packing !! rowspan=2 colspan=2 \| ~~Barchard~~ !! rowspan=3 \| RPck		! rowspan=3 colspan=3 \| Game version !! colspan=4 \| DSI packing !! rowspan=2 colspan=2 \| EAC packing !! rowspan=3 \| RPck
	\|-		\|-
	! rowspan=2 \| RLE !! colspan=3 \| Huffman		! rowspan=2 \| RLE !! colspan=3 \| Huffman
Line 31:		Line 31:
	\|}		\|}

	== ~~MS DOS~~ ==		== DSI packing ==
	The original release of Stunts uses a custom data compression format not found in the ports to other platforms. The code may have been hand-crafted for 16-bit x86 since other options were favoured in the later ports.		The original release of Stunts for MS DOS uses a custom data compression format not found in the ports to other platforms. The code may have been hand-crafted for 16-bit x86 since other options were favoured in the later ports. The format does not have any identification bytes, so we will refer to it as ''DSI packing'' as it appeared in several DSI games in the late 80's and early 90's.

	The data format supports both [https://en.wikipedia.org/wiki/Run-length_encoding run-length encoding] (RLE) and [https://en.wikipedia.org/wiki/Huffman_coding Huffman coding]. They can be combined in multiple passes. The data format and the decompression code don't require any particular order or combination of algorithms. Every compressed file shipped with the game use Huffman coding, and when combined with RLE, the RLE pass is applied before Huffman.		The data format supports both [https://en.wikipedia.org/wiki/Run-length_encoding run-length encoding] (RLE) and [https://en.wikipedia.org/wiki/Huffman_coding Huffman coding]. They can be combined in multiple passes. The data format and the decompression code don't require any particular order or combination of algorithms. Every compressed file shipped with the game use Huffman coding, and when combined with RLE, the RLE pass is applied before Huffman.
Line 113:		Line 113:
	The Huffman decompression in the game code of Stunts 1.0 differs from the one in its LOAD.EXE and later versions of the game. The Huffman codes are written with the least significant bit first, as opposed to the other versions that has the codes written with the opposite orientation. The game code of Stunts 1.0 also does not use a prefix table, and the bit-stream orientation was likely changed with the introduction of this optimisation.		The Huffman decompression in the game code of Stunts 1.0 differs from the one in its LOAD.EXE and later versions of the game. The Huffman codes are written with the least significant bit first, as opposed to the other versions that has the codes written with the opposite orientation. The game code of Stunts 1.0 also does not use a prefix table, and the bit-stream orientation was likely changed with the introduction of this optimisation.

	== ~~Amiga~~ ==		== EAC packing ==
	~~The Amiga~~ port ~~uses two unrelated compression formats.~~		Pixel graphics in the PC98 port and non-3d shape resource files in the Amiga port uses another in-house format that is characterized by the identification byte <tt>0xFB</tt>, assumed to be the initials of its author, [https://www.mobygames.com/person/7186/frank-barchard/ Frank Barchard]. This format supports a suite of different compression methods and it evolved through the 90's and early 2000's as a part of EA Canada's internal engine libraries. Whereas later games tended to use the [https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Storer%E2%80%93Szymanski LZSS]-based [https://github.com/lingeringwillx/Refpack-QFS-Resources RefPack] algorithm, the Stunts ports uses other methods. We will therefore refer to these compressions as ''EAC packing'' to distinguish them from the ubiquitous RefPack.

	~~=== Barchard ===~~
	~~Non~~-3d shape resource files uses another ~~Distinctive Software~~ in-house format that is characterized by the identification byte <tt>0xFB</tt>, assumed to be the initials of its author, [https://www.mobygames.com/person/7186/frank-barchard/ Frank Barchard]. This format supports a suite of different compression methods and it evolved through the 90's and early 2000's as a part of EA's internal engine libraries. Whereas later games tended to use the [https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Storer%E2%80%93Szymanski LZSS]-based [https://github.com/lingeringwillx/Refpack-QFS-Resources RefPack] algorithm, the Stunts ports uses other methods. We will therefore refer to these compressions as ''~~"Barchard"~~'' to distinguish them from the ubiquitous RefPack.

	This is the currently assumed header structure:		This is the currently assumed header structure:
Line 197:		Line 194:
	Data is embedded without any transformations.		Data is embedded without any transformations.

	=== RPck ===		== RPck ==
	3-d shapes are compressed with RPck, a simple byte-oriented [https://en.wikipedia.org/wiki/Run-length_encoding RLE]-based format also found in earlier Amiga games from DSI. Compression ratio is inferior to ~~Barchard~~'s ~~byte pair encoding~~. RPck may have been kept for performance reasons or deadline constraints.		3-d shapes in the Amiga port are compressed with RPck, a simple byte-oriented [https://en.wikipedia.org/wiki/Run-length_encoding RLE]-based format also found in earlier Amiga games from DSI. Compression ratio is inferior to EAC's BPE or Huffman compression. RPck may have been kept for performance reasons or deadline constraints.

	<span class="hlC">// Big endian byte ordering.</span>		<span class="hlC">// Big endian byte ordering.</span>
Line 211:		Line 208:
	After the header comes a one-byte control code treated as a signed integer. If the value is negative, it is negated and this number of bytes is read and copied directly to the output. Since the maximum length is 128, another control code is needed if there are more than 128 consecutive bytes without repetition. If the control byte value is positive, the following byte is copied to the output and then duplicated the number of times specified in the control byte. This is repeated until <tt>uncompressed_size</tt> is reached or there is no more data in the source buffer.		After the header comes a one-byte control code treated as a signed integer. If the value is negative, it is negated and this number of bytes is read and copied directly to the output. Since the maximum length is 128, another control code is needed if there are more than 128 consecutive bytes without repetition. If the control byte value is positive, the following byte is copied to the output and then duplicated the number of times specified in the control byte. This is repeated until <tt>uncompressed_size</tt> is reached or there is no more data in the source buffer.

	The game is also shipped with two files, ''stdapmin.psh'' and ''stdbaudi.psh'', which appears to be wrapped in another variant of this format. The header is "<tt>PPkc</tt>" [''sic.''] and the contents are stored without compression, but the length header is stripped from the wrapped resource files.		The game is also shipped with two files, ''stdapmin.psh'' and ''stdbaudi.psh'', which appears to be wrapped in another variant of this format. The header is "<tt>PPkc</tt>" [''sic.''] and the contents are stored without compression, but the length header is stripped from the wrapped resource files. Yet another possibly related format appears in the DSI game [https://www.mobygames.com/game/107/test-drive/ Test Drive] with the header "<tt>Pckd</tt>".

	~~== PC98 ==~~
	~~The PC98 port of~~ the game ~~uses~~ [~~[#Barchard\|Barchard~~]~~] to compress some of the bitmap image resource files. See~~ the ~~Amiga section for more details~~.

	== FM Towns ==		== FM Towns ==

Dstien: /* Barchard */ Identified Huffman method.

2024-01-18T14:28:57Z

Barchard: Identified Huffman method.

Dstien: /* RPck */ Format description.

2024-01-12T13:16:45Z

RPck: Format description.

@@ Line 195: / Line 195: @@
 === RPck ===
--d shapes are compressed with RPck, a simple [https://en.wikipedia.org/wiki/Run-length_encoding RLE]-based format found in some Amiga file archiving software. Compression ratio is inferior to RefPack, but the code is simpler and faster, which may explain why it was chosen for these files.
+-d shapes are compressed with RPck, a simple byte-oriented [https://en.wikipedia.org/wiki/Run-length_encoding RLE]-based format also found in earlier Amiga games from DSI. Compression ratio is inferior to Barchard's byte pair encoding. RPck may have been kept for performance reasons or deadline constraints.
 == PC98 ==

Dstien: /* Barchard */ Store

2024-01-11T17:40:58Z

Barchard: Store

← Older revision		Revision as of 19:40, 11 January 2024
Line 181:		Line 181:
	\| <tt>0x66</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1100</span><span style="color:green">100</span></tt> \|\| style=text-align:center \| X \|\| style=text-align:center \| X \|\| style=text-align:center \| X		\| <tt>0x66</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1100</span><span style="color:green">100</span></tt> \|\| style=text-align:center \| X \|\| style=text-align:center \| X \|\| style=text-align:center \| X
	\|-		\|-
	\| 0xD		\| 0xD Store
	\| <tt>0x6B \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1101</span><span style="color:green">011</span></tt> \|\| style=text-align:center \| \|\| style=text-align:center \| X \|\| style=text-align:center \| X		\| <tt>0x6B \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1101</span><span style="color:green">011</span></tt> \|\| style=text-align:center \| \|\| style=text-align:center \| X \|\| style=text-align:center \| X
	\|}		\|}
Line 190:		Line 190:
	==== 0xC Obfuscation ====		==== 0xC Obfuscation ====
	Very simple data obfuscation scheme where each byte is subtracted from the previous. The process is reversed by adding running bytes as they are copied.		Very simple data obfuscation scheme where each byte is subtracted from the previous. The process is reversed by adding running bytes as they are copied.

			==== 0xC Store ====
			Data is embedded without any transformations.

	=== RPck ===		=== RPck ===

Dstien: /* Barchard */ Identified obfuscation method.

2024-01-11T17:22:47Z

Barchard: Identified obfuscation method.

← Older revision		Revision as of 19:22, 11 January 2024
Line 141:		Line 141:
	\|-		\|-
	\| Stunts Amiga Method 1 \|\| <tt>0x26</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">0100</span><span style="color:green">110</span></tt>		\| Stunts Amiga Method 1 \|\| <tt>0x26</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">0100</span><span style="color:green">110</span></tt>
			\|-
			\| Stunts Amiga Method 1 \|\| <tt>0x27</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">0100</span><span style="color:green">111</span></tt>
	\|-		\|-
	\| Stunts Amiga BPE \|\| <tt>0x42</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">010</span></tt>		\| Stunts Amiga BPE \|\| <tt>0x42</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">010</span></tt>
Line 152:		Line 154:
	! Method !! Hex !! Bits !! Amiga !! PC98 !! Mickey		! Method !! Hex !! Bits !! Amiga !! PC98 !! Mickey
	\|-		\|-
	\| rowspan=2 \| ~~Method 1~~		\| rowspan=2 \| 0x4
	\| <tt>0x26</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">0100</span><span style="color:green">110</span></tt> \|\| style=text-align:center \| X \|\| style=text-align:center \| \|\| style=text-align:center \|		\| <tt>0x26</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">0100</span><span style="color:green">110</span></tt> \|\| style=text-align:center \| X \|\| style=text-align:center \| \|\| style=text-align:center \|
	\|-		\|-
	\| <tt>0x27</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">0100</span><span style="color:green">111</span></tt> \|\| style=text-align:center \| X \|\| style=text-align:center \| \|\| style=text-align:center \|		\| <tt>0x27</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">0100</span><span style="color:green">111</span></tt> \|\| style=text-align:center \| X \|\| style=text-align:center \| \|\| style=text-align:center \|
	\|-		\|-
	\| rowspan=7 \| ~~[https://en.wikipedia.org/wiki/Byte_pair_encoding~~ Byte pair encoding]		\| rowspan=7 \| 0x8 Byte pair encoding
	\| <tt>0x40</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">000</span></tt> \|\| style=text-align:center \| X \|\| style=text-align:center \| \|\| style=text-align:center \| X		\| <tt>0x40</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">000</span></tt> \|\| style=text-align:center \| X \|\| style=text-align:center \| \|\| style=text-align:center \| X
	\|-		\|-
Line 172:		Line 174:
	\| <tt>0x47</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">111</span></tt> \|\| style=text-align:center \| \|\| style=text-align:center \| X \|\| style=text-align:center \|		\| <tt>0x47</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">111</span></tt> \|\| style=text-align:center \| \|\| style=text-align:center \| X \|\| style=text-align:center \|
	\|-		\|-
	\| rowspan=3 \| ~~Method 3~~		\| rowspan=3 \| 0xC Obfuscation
	\| <tt>0x60</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1100</span><span style="color:green">000</span></tt> \|\| style=text-align:center \| X \|\| style=text-align:center \| X \|\| style=text-align:center \| X		\| <tt>0x60</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1100</span><span style="color:green">000</span></tt> \|\| style=text-align:center \| X \|\| style=text-align:center \| X \|\| style=text-align:center \| X
	\|-		\|-
Line 179:		Line 181:
	\| <tt>0x66</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1100</span><span style="color:green">100</span></tt> \|\| style=text-align:center \| X \|\| style=text-align:center \| X \|\| style=text-align:center \| X		\| <tt>0x66</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1100</span><span style="color:green">100</span></tt> \|\| style=text-align:center \| X \|\| style=text-align:center \| X \|\| style=text-align:center \| X
	\|-		\|-
	\| ~~Method 4~~		\| 0xD
	\| <tt>0x6B \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1101</span><span style="color:green">011</span></tt> \|\| style=text-align:center \| X \|\| style=text-align:center \| X \|\| style=text-align:center \| X		\| <tt>0x6B \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1101</span><span style="color:green">011</span></tt> \|\| style=text-align:center \| \|\| style=text-align:center \| X \|\| style=text-align:center \| X
	\|}		\|}

	~~A strong hypothesis suggests~~ that the ~~compression methods found here~~ are ~~related~~ to the ~~EA formats from PSX games~~ [https://problemkaputt.de/psxspx-cdrom-file-compression-ea-methods.htm documented by Martin Korth]. ~~Further analysis~~ is ~~required to verify this~~.		==== 0x8 - Byte pair encoding ====
			[https://en.wikipedia.org/wiki/Byte_pair_encoding Byte pair encoding] replaces frequently occurring byte pairs with a single byte that is not used elsewhere in the data. The process is repeated recursively until there are no more repeated byte pairs or available code bytes. Appears to be the same format as [https://problemkaputt.de/psxspx-cdrom-file-compression-ea-methods-bpe.htm documented by Martin Korth].

			==== 0xC Obfuscation ====
			Very simple data obfuscation scheme where each byte is subtracted from the previous. The process is reversed by adding running bytes as they are copied.

	=== RPck ===		=== RPck ===

Dstien: /* Barchard */ Methods recognised by Amiga port

2024-01-11T16:39:03Z

Barchard: Methods recognised by Amiga port

← Older revision		Revision as of 18:39, 11 January 2024
Line 138:		Line 138:
	! Game !! Hex !! Bits		! Game !! Hex !! Bits
	\|-		\|-
	\| Mickey's ABC \|\| <tt>0x44</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">100</span></tt>		\| Mickey's ABC BPE \|\| <tt>0x44</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">100</span></tt>
	\|-		\|-
	\| Stunts Amiga ~~type~~ 1 \|\| <tt>0x26</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">0100</span><span style="color:green">110</span></tt>		\| Stunts Amiga Method 1 \|\| <tt>0x26</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">0100</span><span style="color:green">110</span></tt>
	\|-		\|-
	\| Stunts Amiga ~~type 2~~ \|\| <tt>0x42</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">010</span></tt>		\| Stunts Amiga BPE \|\| <tt>0x42</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">010</span></tt>
	\|-		\|-
	\| Stunts PC98 \|\| <tt>0x46</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">110</span></tt>		\| Stunts PC98 BPE \|\| <tt>0x46</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">110</span></tt>
	\|}		\|}

	The game code appears to support several other methods that are not used by the shipped files~~. This analysis does not include the Amiga port, as this code has not been dissected yet~~.		The game code appears to support several other methods that are not used by the shipped files.

	{\| class="wikitable"		{\| class="wikitable"
	! Method !! Hex !! Bits		! Method !! Hex !! Bits !! Amiga !! PC98 !! Mickey
	\|-		\|-
	\| rowspan=4 \| ~~Mickey type~~ 1		\| rowspan=2 \| Method 1
	\| <tt>~~0x40~~</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">~~1000~~</span><span style="color:green">~~000~~</span></tt>		\| <tt>0x26</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">0100</span><span style="color:green">110</span></tt> \|\| style=text-align:center \| X \|\| style=text-align:center \| \|\| style=text-align:center \|
	\|-		\|-
	\| <tt>~~0x41~~</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">~~1000~~</span><span style="color:green">~~001~~</span></tt>		\| <tt>0x27</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">0100</span><span style="color:green">111</span></tt> \|\| style=text-align:center \| X \|\| style=text-align:center \| \|\| style=text-align:center \|
	\|-		\|-
	\| <tt>~~0x42~~</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">~~010~~</span></tt>		\| rowspan=7 \| [https://en.wikipedia.org/wiki/Byte_pair_encoding Byte pair encoding]
			\| <tt>0x40</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">000</span></tt> \|\| style=text-align:center \| X \|\| style=text-align:center \| \|\| style=text-align:center \| X
	\|-		\|-
	\| <tt>~~0x44~~</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">~~100~~</span></tt>		\| <tt>0x41</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">001</span></tt> \|\| style=text-align:center \| X \|\| style=text-align:center \| \|\| style=text-align:center \| X
	\|-		\|-
	~~\| rowspan=2 \| Stunts type 1~~		\| <tt>0x42</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">010</span></tt> \|\| style=text-align:center \| X \|\| style=text-align:center \| \|\| style=text-align:center \| X
	\| <tt>~~0x46~~</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">~~110~~</span></tt>
	\|-		\|-
	\| <tt>~~0x47~~</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">~~111~~</span></tt>		\| <tt>0x44</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">100</span></tt> \|\| style=text-align:center \| \|\| style=text-align:center \| \|\| style=text-align:center \| X
	\|-		\|-
	~~\| rowspan=3 \| Stunts PC98 and Mickey type 2~~		\| <tt>0x45</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">101</span></tt> \|\| style=text-align:center \| \|\| style=text-align:center \| \|\| style=text-align:center \| X
	\| <tt>~~0x60~~</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">~~1100~~</span><span style="color:green">~~000~~</span></tt>
	\|-		\|-
	\| <tt>~~0x62~~</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">~~1100~~</span><span style="color:green">~~010~~</span></tt>		\| <tt>0x46</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">110</span></tt> \|\| style=text-align:center \| \|\| style=text-align:center \| X \|\| style=text-align:center \|
	\|-		\|-
	\| <tt>~~0x66~~</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">~~1100~~</span><span style="color:green">~~100~~</span></tt>		\| <tt>0x47</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">111</span></tt> \|\| style=text-align:center \| \|\| style=text-align:center \| X \|\| style=text-align:center \|
	\|-		\|-
	\| ~~Stunts PC98 and Mickey type~~ 3		\| rowspan=3 \| Method 3
	\| <tt>0x6B \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1101</span><span style="color:green">011</span></tt>		\| <tt>0x60</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1100</span><span style="color:green">000</span></tt> \|\| style=text-align:center \| X \|\| style=text-align:center \| X \|\| style=text-align:center \| X
			\|-
			\| <tt>0x62</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1100</span><span style="color:green">010</span></tt> \|\| style=text-align:center \| X \|\| style=text-align:center \| X \|\| style=text-align:center \| X
			\|-
			\| <tt>0x66</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1100</span><span style="color:green">100</span></tt> \|\| style=text-align:center \| X \|\| style=text-align:center \| X \|\| style=text-align:center \| X
			\|-
			\| Method 4
			\| <tt>0x6B \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1101</span><span style="color:green">011</span></tt> \|\| style=text-align:center \| X \|\| style=text-align:center \| X \|\| style=text-align:center \| X
	\|}		\|}

Dstien: /* PC98 */ s/RefPack/Barchard/

2024-01-09T17:11:32Z

PC98: s/RefPack/Barchard/

← Older revision		Revision as of 19:11, 9 January 2024
Line 183:		Line 183:

	== PC98 ==		== PC98 ==
	The PC98 port of the game uses [~~http://wiki.niotso.org/RefPack RefPack~~] to compress some of the bitmap image resource files. See the Amiga section for more details.		The PC98 port of the game uses [[#Barchard\|Barchard]] to compress some of the bitmap image resource files. See the Amiga section for more details.

	== FM Towns ==		== FM Towns ==

Dstien: Replaced disproved RefPack speculation with updated research.

2024-01-09T17:00:19Z

Replaced disproved RefPack speculation with updated research.

@@ Line 3: / Line 3: @@
 == Formats by game version ==
 {| class="wikitable"
-! rowspan=3 colspan=3 | Game version !! colspan=4 | Stunts packing !! rowspan=3 | RefPack !! rowspan=3 | RPck
+! rowspan=3 colspan=3 | Game version !! colspan=4 | Stunts packing !! rowspan=3 | Barchard !! rowspan=3 | RPck
 |-
 ! rowspan=2 | RLE !! colspan=3 | Huffman
@@ Line 116: / Line 116: @@
 The Amiga port uses two unrelated compression formats.
-=== RefPack ===
+=== Barchard ===
-Non-3d shape resource files uses the Electronic Arts in-house [https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Storer%E2%80%93Szymanski LZSS]-based compression format [http://wiki.niotso.org/RefPack RefPack]. This may be one of the first known uses of RefPack which since became part of EA's internal engine libraries and has been used in many games through the 90's and early 2000's. The bit stream format is fully documented and has multiple implementations available, but the header flags have either changed, or the unofficial implementations make incorrect assumptions about them, causing the decompressors to wrongfully assume that the 4D Sports Driving files are not compressed due to not having the <tt>0x01</tt> flag set.
+Non-3d shape resource files uses another Distinctive Software in-house format that is characterized by the identification byte <tt>0xFB</tt>, assumed to be the initials of its author, [https://www.mobygames.com/person/7186/frank-barchard/ Frank Barchard]. This format supports a suite of different compression methods and it evolved through the 90's and early 2000's as a part of EA's internal engine libraries. Whereas later games tended to use the [https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Storer%E2%80%93Szymanski LZSS]-based [https://github.com/lingeringwillx/Refpack-QFS-Resources RefPack] algorithm, the Stunts ports uses other methods. We will therefore refer to these compressions as ''"Barchard"'' to distinguish them from the ubiquitous RefPack.
 === RPck ===

Dstien: /* Run-length encoding */ Typos.

2023-06-29T10:29:36Z

Run-length encoding: Typos.

← Older revision		Revision as of 12:29, 29 June 2023
Line 55:		Line 55:
	If the most significant bit of the first byte of the file is set, this is a multi-pass file and the remaining 7 bits are the number of passes to be processed recursively. If the <tt>multi_pass</tt> flag is not set, we are only doing a single pass and the first byte is the compression type. The next three bytes make up the uncompressed size. If the <tt>multi_pass</tt> flag was set, this is the final uncompressed size. When the <tt>multi_pass</tt> flag is not set, this is the uncompressed size of the current pass. The remaining data is processed recursively. The <tt>compression_type</tt> field decides how it is decoded.		If the most significant bit of the first byte of the file is set, this is a multi-pass file and the remaining 7 bits are the number of passes to be processed recursively. If the <tt>multi_pass</tt> flag is not set, we are only doing a single pass and the first byte is the compression type. The next three bytes make up the uncompressed size. If the <tt>multi_pass</tt> flag was set, this is the final uncompressed size. When the <tt>multi_pass</tt> flag is not set, this is the uncompressed size of the current pass. The remaining data is processed recursively. The <tt>compression_type</tt> field decides how it is decoded.

	=== Run length ~~coding~~ ===		=== Run-length encoding ===

	<span class="hlP">struct</span> RLE <span class="hlB">{</span>		<span class="hlP">struct</span> RLE <span class="hlB">{</span>
	~~<span class="hlP">uint8</span> unknown <span class="hlC">// Always 0x00, value is ignored by the game</span>~~
	<span class="hlP">uint32</span> compressed_size : 24		<span class="hlP">uint32</span> compressed_size : 24
			<span class="hlP">uint8</span> reserved <span class="hlC">// Always 0x00, value is ignored by the game</span>
	<span class="hlP">uint8</span> escape_length : 7		<span class="hlP">uint8</span> escape_length : 7
	<span class="hlP">uint8</span> no_sequence : 1		<span class="hlP">uint8</span> no_sequence : 1

← Older revision		Revision as of 16:28, 18 January 2024
Line 3:		Line 3:
	== Formats by game version ==		== Formats by game version ==
	{\| class="wikitable"		{\| class="wikitable"
	! rowspan=3 colspan=3 \| Game version !! colspan=4 \| Stunts packing !! rowspan=3 \| Barchard !! rowspan=3 \| RPck		! rowspan=3 colspan=3 \| Game version !! colspan=4 \| Stunts packing !! rowspan=2 colspan=2 \| Barchard !! rowspan=3 \| RPck
	\|-		\|-
	! rowspan=2 \| RLE !! colspan=3 \| Huffman		! rowspan=2 \| RLE !! colspan=3 \| Huffman
	\|-		\|-
	! Supported !! Prefix table !! Code endianness		! Supported !! Prefix table !! Code endianness !! Huffman !! BPE
	\|-		\|-
	! rowspan=4 style=text-align:left \| MS DOS !! rowspan=2 \| BB 1.0 !! style=text-align:left \| Game		! rowspan=4 style=text-align:left \| MS DOS !! rowspan=2 \| BB 1.0 !! style=text-align:left \| Game
	\| style=text-align:center \| X \|\| style=text-align:center \| X \|\| \|\| Big \|\| \|\|		\| style=text-align:center \| X \|\| style=text-align:center \| X \|\| \|\| Big \|\| \|\| \|\|
	\|-		\|-
	! style=text-align:left \| Loader		! style=text-align:left \| Loader
	\| \|\| style=text-align:center \| X \|\| style=text-align:center \| X \|\| Little \|\| \|\|		\| \|\| style=text-align:center \| X \|\| style=text-align:center \| X \|\| Little \|\| \|\| \|\|
	\|-		\|-
	! rowspan=2 \| BB 1.1/MS 1.1 !! style=text-align:left \| Game		! rowspan=2 \| BB 1.1/MS 1.1 !! style=text-align:left \| Game
	\| style=text-align:center \| X \|\| style=text-align:center \| X \|\| style=text-align:center \| X \|\| Little \|\| \|\|		\| style=text-align:center \| X \|\| style=text-align:center \| X \|\| style=text-align:center \| X \|\| Little \|\| \|\| \|\|
	\|-		\|-
	! style=text-align:left \| Loader		! style=text-align:left \| Loader
	\| \|\| style=text-align:center \| X \|\| style=text-align:center \| X \|\| Little \|\| \|\|		\| \|\| style=text-align:center \| X \|\| style=text-align:center \| X \|\| Little \|\| \|\| \|\|
	\|-		\|-
	! colspan=3 style=text-align:left \| Amiga		! colspan=3 style=text-align:left \| Amiga
	\| \|\| \|\| \|\| \|\| style=text-align:center \| X \|\| style=text-align:center \| X		\| \|\| \|\| \|\| \|\| style=text-align:center \| X \|\| style=text-align:center \| X \|\| style=text-align:center \| X
	\|-		\|-
	! colspan=3 style=text-align:left \| PC98		! colspan=3 style=text-align:left \| PC98
	\| \|\| \|\| \|\| \|\| style=text-align:center \| X \|\|		\| \|\| \|\| \|\| \|\| \|\| style=text-align:center \| X \|\|
	\|-		\|-
	! colspan=3 style=text-align:left \| FM Towns		! colspan=3 style=text-align:left \| FM Towns
	\| \|\| \|\| \|\| \|\| \|\|		\| \|\| \|\| \|\| \|\| \|\| \|\|
	\|}		\|}

Line 140:		Line 140:
	\| Mickey's ABC BPE \|\| <tt>0x44</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">100</span></tt>		\| Mickey's ABC BPE \|\| <tt>0x44</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">100</span></tt>
	\|-		\|-
	\| Stunts Amiga ~~Method 1~~ \|\| <tt>0x26</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">0100</span><span style="color:green">110</span></tt>		\| Stunts Amiga Huffman \|\| <tt>0x26</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">0100</span><span style="color:green">110</span></tt>
	\|-		\|-
	\| Stunts Amiga ~~Method 1~~ \|\| <tt>0x27</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">0100</span><span style="color:green">111</span></tt>		\| Stunts Amiga Huffman \|\| <tt>0x27</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">0100</span><span style="color:green">111</span></tt>
	\|-		\|-
	\| Stunts Amiga BPE \|\| <tt>0x42</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">010</span></tt>		\| Stunts Amiga BPE \|\| <tt>0x42</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">1000</span><span style="color:green">010</span></tt>
Line 154:		Line 154:
	! Method !! Hex !! Bits !! Amiga !! PC98 !! Mickey		! Method !! Hex !! Bits !! Amiga !! PC98 !! Mickey
	\|-		\|-
	\| rowspan=2 \| 0x4		\| rowspan=2 \| 0x4 Huffman coding
	\| <tt>0x26</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">0100</span><span style="color:green">110</span></tt> \|\| style=text-align:center \| X \|\| style=text-align:center \| \|\| style=text-align:center \|		\| <tt>0x26</tt> \|\| <tt><span style="color:lightgray">0</span><span style="color:red">0100</span><span style="color:green">110</span></tt> \|\| style=text-align:center \| X \|\| style=text-align:center \| \|\| style=text-align:center \|
	\|-		\|-
Line 185:		Line 185:
	\|}		\|}

	==== 0x8 - Byte pair encoding ====		==== 0x4 Huffman coding ====
			Similar to, but incompatible with the Huffman coding used in later EA games as method 0x6 and [https://problemkaputt.de/psxspx-cdrom-file-compression-ea-methods-huffman.htm documented by Martin Korth].

			==== 0x8 Byte pair encoding ====
	[https://en.wikipedia.org/wiki/Byte_pair_encoding Byte pair encoding] replaces frequently occurring byte pairs with a single byte that is not used elsewhere in the data. The process is repeated recursively until there are no more repeated byte pairs or available code bytes. Appears to be the same format as [https://problemkaputt.de/psxspx-cdrom-file-compression-ea-methods-bpe.htm documented by Martin Korth].		[https://en.wikipedia.org/wiki/Byte_pair_encoding Byte pair encoding] replaces frequently occurring byte pairs with a single byte that is not used elsewhere in the data. The process is repeated recursively until there are no more repeated byte pairs or available code bytes. Appears to be the same format as [https://problemkaputt.de/psxspx-cdrom-file-compression-ea-methods-bpe.htm documented by Martin Korth].

Line 191:		Line 194:
	Very simple data obfuscation scheme where each byte is subtracted from the previous. The process is reversed by adding running bytes as they are copied.		Very simple data obfuscation scheme where each byte is subtracted from the previous. The process is reversed by adding running bytes as they are copied.

	==== ~~0xC~~ Store ====		==== 0xD Store ====
	Data is embedded without any transformations.		Data is embedded without any transformations.

Line 208:		Line 211:
	After the header comes a one-byte control code treated as a signed integer. If the value is negative, it is negated and this number of bytes is read and copied directly to the output. Since the maximum length is 128, another control code is needed if there are more than 128 consecutive bytes without repetition. If the control byte value is positive, the following byte is copied to the output and then duplicated the number of times specified in the control byte. This is repeated until <tt>uncompressed_size</tt> is reached or there is no more data in the source buffer.		After the header comes a one-byte control code treated as a signed integer. If the value is negative, it is negated and this number of bytes is read and copied directly to the output. Since the maximum length is 128, another control code is needed if there are more than 128 consecutive bytes without repetition. If the control byte value is positive, the following byte is copied to the output and then duplicated the number of times specified in the control byte. This is repeated until <tt>uncompressed_size</tt> is reached or there is no more data in the source buffer.

	The game is also shipped with two files, ''stdapmin.psh'' and ''stdbaudi.psh'', which appears to be wrapped in another variant of this format. The header is "<tt>PPkc</tt>" and the contents are stored without compression, but the length header is stripped from the wrapped resource files.		The game is also shipped with two files, ''stdapmin.psh'' and ''stdbaudi.psh'', which appears to be wrapped in another variant of this format. The header is "<tt>PPkc</tt>" [''sic.''] and the contents are stored without compression, but the length header is stripped from the wrapped resource files.

	== PC98 ==		== PC98 ==