Difference between revisions of "SCI/Specifications/Resource files/Decompression algorithms/DCL-EXPLODE"
< SCI | Specifications | Resource files | Decompression algorithms
Jump to navigation
Jump to search
(Merging of the SCI documentation) |
m (Improved table formatting) |
||
| Line 55: | Line 55: | ||
The first huffman tree (Section 2.3.2) contains the length values. It is described by the following table: | The first huffman tree (Section 2.3.2) contains the length values. It is described by the following table: | ||
{| border="1" | {| border="1" cellspacing="0" cellpadding="5" | ||
|+ | |||
|'''value (hex)''' | |'''value (hex)''' | ||
|'''code (binary)''' | |'''code (binary)''' | ||
| Line 114: | Line 115: | ||
The second huffman code tree contains the distance values. It can be built from the following table: | The second huffman code tree contains the distance values. It can be built from the following table: | ||
{| border="1" | {| border="1" cellspacing="0" cellpadding="5" | ||
|+ | |||
|'''value (hex)''' | |'''value (hex)''' | ||
|'''code (binary)''' | |'''code (binary)''' | ||
| Line 315: | Line 317: | ||
This tree describes literal values for ASCII mode, which adds another compression step to the algorithm. | This tree describes literal values for ASCII mode, which adds another compression step to the algorithm. | ||
{|border="1" | {| border="1" cellspacing="0" cellpadding="5" | ||
|+ | |||
|'''value (hex)''' | |'''value (hex)''' | ||
|'''code (binary)''' | |'''code (binary)''' | ||
Latest revision as of 09:16, 31 January 2009
Decompression algorithm DCL-EXPLODE
Originally by Petr Vyhnak
This algorithm matches one or more of the UNKNOWN algorithms.
This algorithm is based on the Deflate algorithm described in the Internet RFC 1951 (see also RFC 1950 for related material).
The algorithm is quite similar to the explode algorithm (ZIP method #6 - implode ) but there are differences.
<syntax type="C">
/* The first 2 bytes are parameters */
P1 = ReadByte(); /* 0 or 1 */
/* I think this means 0=binary and 1=ascii file, but in RESOURCEs I saw always 0 */
P2 = ReadByte();
/* must be 4,5 or 6 and it is a parameter for the decompression algorithm */
/* Now, a bit stream follows, which is decoded as described below:
LOOP:
read 1 bit (take bits from the lowest value (LSB) to the MSB i.e. bit 0, bit 1 etc ...)
- if the bit is 0 read 8 bits and write it to the output as it is.
- if the bit is 1 we have here a length/distance pair:
- decode a number with Hufmman Tree #1; variable bit length, result is 0x00 .. 0x0F -> L1 */
if L1 <= 7:
LENGTH = L1 + 2
if L1 > 7
read more (L1-7) bits -> L2
LENGTH = L2 + M[L1-7] + 2
// decode another number with Hufmann Tree #2 giving result 0x00..0x3F -> D1
if LENGTH == 2
D1 = D1 << 2
read 2 bits -> D2
else
D1 = D1 << P2 // the parameter 2
read P2 bits -> D2
DISTANCE = (D1 | D2) + 1
// now copy LENGTH bytes from (output_ptr-DISTANCE) to output_ptr
END LOOP </syntax>
M
M is a constant array defined as M[0] = 7, M[n+1] = M[n]+ 2ˆn. That means M[1] = 8, M[2] = 0x0A, M[3] = 0x0E, M[4] = 0x16, M[5] = 0x26, etc.
Huffman Tree #1
The first huffman tree (Section 2.3.2) contains the length values. It is described by the following table:
| value (hex) | code (binary) |
| 0 | 101 |
| 1 | 11 |
| 2 | 100 |
| 3 | 011 |
| 4 | 0101 |
| 5 | 0100 |
| 6 | 0011 |
| 7 | 0010 1 |
| 8 | 0010 0 |
| 9 | 0001 1 |
| a | 0001 0 |
| b | 0000 11 |
| c | 0000 10 |
| d | 0000 01 |
| e | 0000 001 |
| f | 0000 000 |
(where bits should be read from the left to the right)
Huffman Tree #2
The second huffman code tree contains the distance values. It can be built from the following table:
| value (hex) | code (binary) |
| 00 | 11 |
| 01 | 1011 |
| 02 | 1010 |
| 03 | 1001 1 |
| 04 | 1001 0 |
| 05 | 1000 1 |
| 06 | 1000 0 |
| 07 | 0111 11 |
| 08 | 0111 10 |
| 09 | 0111 01 |
| 0a | 0111 00 |
| 0b | 0110 11 |
| 0c | 0110 10 |
| 0d | 0110 01 |
| 0e | 0110 00 |
| 0f | 0101 11 |
| 10 | 0101 10 |
| 11 | 0101 01 |
| 12 | 0101 00 |
| 13 | 0100 11 |
| 14 | 0100 10 |
| 15 | 0100 01 |
| 16 | 0100 001 |
| 17 | 0100 000 |
| 18 | 0011 111 |
| 19 | 0011 110 |
| 1a | 0011 101 |
| 1b | 0011 100 |
| 1c | 0011 011 |
| 1d | 0011 010 |
| 1e | 0011 001 |
| 1f | 0011 000 |
| 20 | 0010 111 |
| 21 | 0010 110 |
| 22 | 0010 101 |
| 23 | 0010 100 |
| 24 | 0010 011 |
| 25 | 0010 010 |
| 26 | 0010 001 |
| 27 | 0010 000 |
| 28 | 0001 111 |
| 29 | 0001 110 |
| 2a | 0001 101 |
| 2b | 0001 100 |
| 2c | 0001 011 |
| 2d | 0001 010 |
| 2e | 0001 001 |
| 2f | 0001 000 |
| 30 | 0000 1111 |
| 31 | 0000 1110 |
| 32 | 0000 1101 |
| 33 | 0000 1100 |
| 34 | 0000 1011 |
| 35 | 0000 1010 |
| 36 | 0000 1001 |
| 37 | 0000 1000 |
| 38 | 0000 0111 |
| 39 | 0000 0110 |
| 3a | 0000 0101 |
| 3b | 0000 0100 |
| 3c | 0000 0011 |
| 3d | 0000 0010 |
| 3e | 0000 0001 |
| 3f | 0000 0000 |
Huffman Tree #3
This tree describes literal values for ASCII mode, which adds another compression step to the algorithm.
| value (hex) | code (binary) |
| 00 | 0000 1001 001 |
| 01 | 0000 0111 1111 |
| 02 | 0000 0111 1110 |
| 03 | 0000 0111 1101 |
| 04 | 0000 0111 1100 |
| 05 | 0000 0111 1011 |
| 06 | 0000 0111 1010 |
| 07 | 0000 0111 1001 |
| 08 | 0000 0111 1000 |
| 09 | 0001 1101 |
| 0a | 0100 O11 |
| Ob | 0000 0111 0111 |
| Oc | 0000 0111 0110 |
| Od | 0100 010 |
| Oe | 0000 0111 0101 |
| Of | 0000 0111 0100 |
| 10 | 0000 0111 0011 |
| 11 | 0000 0111 0010 |
| 12 | 0000 0111 0001 |
| 13 | 0000 0111 0000 |
| 14 | 0000 0110 1111 |
| 15 | 0000 0110 1110 |
| 16 | 0000 0110 1101 |
| 17 | 0000 0110 1100 |
| 18 | 0000 0110 1011 |
| 19 | 0000 0110 1010 |
| 1a | 0000 0010 0100 1 |
| 1b | 0000 0110 1001 |
| 1c | 0000 0110 1000 |
| 1d | 0000 0110 0111 |
| 1e | 0000 0110 0110 |
| 1f | 0000 0110 0101 |
| 20 | 1111 |
| 21 | 0000 1010 01 |
| 22 | 0001 1100 |
| 23 | 0000 0110 0100 |
| 24 | 0000 1010 00 |
| 25 | 0000 0110 0011 |
| 26 | 0000 1001 11 |
| 27 | 0001 1011 |
| 28 | 0100 001 |
| 29 | 0100 000 |
| 2a | 0001 1010 |
| 2b | 0000 1101 1 |
| 2c | 0011 111 |
| 2d | 1001 01 |
| 2e | 0011 110 |
| 2f | 0001 1001 |
| 30 | 0011 101 |
| 31 | 1001 00 |
| 32 | 0011 100 |
| 33 | 0011 O11 |
| 34 | 0011 010 |
| 35 | 0011 001 |
| 36 | 0001 1000 |
| 37 | 0011 000 |
| 38 | 0010 111 |
| 39 | 0001 0111 |
| 3a | 0001 0110 |
| 3b | 0000 0110 0010 |
| 3c | 0000 1001 000 |
| 3d | 0010 110 |
| 3e | 0000 1101 0 |
| 3f | 0000 1000 111 |
| 40 | 0000 0110 0001 |
| 41 | 1000 11 |
| 42 | 0010 101 |
| 43 | 1000 10 |
| 44 | 1000 01 |
| 45 | 1110 1 |
| 46 | 0010 100 |
| 47 | 0001 0101 |
| 48 | 0001 0100 |
| 49 | 1000 00 |
| 4a | 0000 1000 110 |
| 4b | 0000 1100 1 |
| 4c | 0111 11 |
| 4d | 0010 Oil |
| 4e | 0111 10 |
| 4f | 0111 01 |
| 50 | 0010 010 |
| 51 | 0000 1000 101 |
| 52 | 0111 00 |
| 53 | 0110 11 |
| 54 | 0110 10 |
| 55 | 0010 001 |
| 56 | 0000 1100 0 |
| 57 | 0001 0011 |
| 58 | 0000 1011 1 |
| 59 | 0000 1011 0 |
| 5a | 0000 1000 100 |
| 5b | 0001 0010 |
| 5c | 0000 1000 O11 |
| 5d | 0000 1010 1 |
| 5e | 0000 0110 0000 |
| 5f | 0001 0001 |
| 60 | 0000 0101 1111 |
| 61 | 1110 0 |
| 62 | 0110 01 |
| 63 | 0110 00 |
| 64 | 0101 11 |
| 65 | 1101 1 |
| 66 | 0101 10 |
| 67 | 0101 01 |
| 68 | 0101 00 |
| 69 | 1101 0 |
| 6a | 0000 1000 010 |
| 6b | 0010 000 |
| 6c | 1100 1 |
| 6d | 0100 11 |
| 6e | 1100 0 |
| 6f | 1011 1 |
| 70 | 0100 10 |
| 71 | 0000 1001 10 |
| 72 | 1011 0 |
| 73 | 1010 1 |
| 74 | 1010 0 |
| 75 | 1001 1 |
| 76 | 0001 0000 |
| 77 | 0001 111 |
| 78 | 0000 1111 |
| 79 | 0000 1110 |
| 7a | 0000 1001 01 |
| 7b | 0000 1000 001 |
| 7c | 0000 1000 000 |
| 7d | 0000 0101 1110 |
| 7e | 0000 0101 1101 |
| 7t | 0000 0101 1100 |
| 80 | 0000 0010 0100 0 |
| 81 | 0000 0010 0011 1 |
| 82 | 0000 0010 0011 0 |
| 83 | 0000 0010 0010 1 |
| 84 | 0000 0010 0010 0 |
| 85 | 0000 0010 0001 1 |
| 86 | 0000 0010 0001 0 |
| 87 | 0000 0010 0000 1 |
| 88 | 0000 0010 0000 0 |
| 89 | 0000 0001 1111 1 |
| 8a | 0000 0001 1111 0 |
| 8b | 0000 0001 1110 1 |
| 8c | 0000 0001 1110 0 |
| 8d | 0000 0001 1101 1 |
| 8e | 0000 0001 1101 0 |
| 8f | 0000 0001 1100 1 |
| 90 | 0000 0001 1100 0 |
| 91 | 0000 0001 1011 1 |
| 92 | 0000 0001 1011 0 |
| 93 | 0000 0001 1010 1 |
| 94 | 0000 0001 1010 0 |
| 95 | 0000 0001 1001 1 |
| 96 | 0000 0001 1001 0 |
| 97 | 0000 0001 1000 1 |
| 98 | 0000 0001 1000 0 |
| 99 | 0000 0001 0111 1 |
| 9a | 0000 0001 0111 0 |
| 9b | 0000 0001 0110 1 |
| 9c | 0000 0001 0110 0 |
| 9d | 0000 0001 0101 1 |
| 9e | 0000 0001 0101 0 |
| 9f | 0000 0001 0100 1 |
| aO | 0000 0001 0100 0 |
| a1 | 0000 0001 0011 1 |
| a2 | 0000 0001 0011 0 |
| a3 | 0000 0001 0010 1 |
| a4 | 0000 0001 0010 0 |
| a5 | 0000 0001 0001 1 |
| a6 | 0000 0001 0001 0 |
| a7 | 0000 0001 0000 1 |
| a8 | 0000 0001 0000 0 |
| a9 | 0000 0000 1111 1 |
| aa | 0000 0000 1111 |
| ab | OOOO 0000 1110 1 |
| ac | 0000 0000 1110 0 |
| ad | 0000 0000 1101 1 |
| ae | 0000 0000 1101 0 |
| af | 0000 0000 1100 1 |
| bO | 0000 0101 1011 |
| b1 | 0000 0101 1010 |
| b2 | 0000 0101 1001 |
| b3 | 0000 0101 1000 |
| b4 | 0000 0101 0111 |
| b5 | 0000 0101 0110 |
| b6 | 0000 0101 0101 |
| b7 | 0000 0101 0100 |
| b8 | 0000 0101 0011 |
| b9 | 0000 0101 0010 |
| ba | 0000 0101 0001 |
| bb | 0000 0101 0000 |
| be | 0000 0100 1111 |
| bd | 0000 0100 1110 |
| be | 0000 0100 1101 |
| bf | 0000 0100 1100 |
| cO | 0000 0100 1011 |
| c1 | 0000 0100 1010 |
| c2 | 0000 0100 1001 |
| c3 | 0000 0100 1000 |
| c4 | 0000 0100 0111 |
| c5 | 0000 0100 0110 |
| c6 | 0000 0100 0101 |
| c7 | 0000 0100 0100 |
| c8 | 0000 0100 0011 |
| c9 | 0000 0100 0010 |
| ca | 0000 0100 0001 |
| cb | 0000 0100 0000 |
| cc | 0000 0011 1111 |
| cd | 0000 0011 1110 |
| ce | 0000 0011 1101 |
| cf | 0000 0011 1100 |
| dO | 0000 0011 1011 |
| d1 | 0000 0011 1010 |
| d2 | 0000 0011 1001 |
| d3 | 0000 0011 1000 |
| d4 | 0000 0011 0111 |
| d5 | 0000 0011 0110 |
| d6 | 0000 0011 0101 |
| d7 | 0000 0011 0100 |
| d8 | 0000 0011 0011 |
| d9 | 0000 0011 0010 |
| da | 0000 0011 0001 |
| db | 0000 0011 0000 |
| dc | 0000 0010 1111 |
| dd | 0000 0010 1110 |
| de | 0000 0010 1101 |
| df | 0000 0010 1100 |
| eO | 0000 0000 1100 0 |
| e1 | 0000 0010 1011 |
| e2 | 0000 0000 1011 |
| e3 | 0000 0000 1011 0 |
| e4 | 0000 0000 1010 1 |
| e5 | 0000 0010 1010 |
| e6 | 0000 0000 1010 0 |
| e7 | 0000 0000 1001 1 |
| e8 | 0000 0000 1001 0 |
| e9 | 0000 0010 1001 |
| ea | 0000 0000 1000 1 |
| eb | 0000 0000 1000 0 |
| ec | 0000 0000 0111 1 |
| ed | 0000 0000 0111 0 |
| ee | 0000 0010 1000 |
| ef | 0000 0000 0110 1 |
| f0 | 0000 0000 0110 0 |
| f1 | 0000 0000 0101 1 |
| f2 | 0000 0010 0111 |
| f3 | 0000 0010 0110 |
| f4 | 0000 0010 0101 |
| f5 | 0000 0000 0101 0 |
| f6 | 0000 0000 0100 1 |
| f7 | 0000 0000 0100 0 |
| f8 | 0000 0000 0011 1 |
| f9 | 0000 0000 0011 0 |
| fa | 0000 0000 0010 1 |
| fb | 0000 0000 0010 0 |
| fc | 0000 0000 0001 1 |
| fd | 0000 0000 0001 0 |
| fe | 0000 0000 0000 1 |
| ff | 0000 0000 0000 0 |