SCI/Specifications/Resource files/Decompression algorithms/DCL-EXPLODE

From ScummVM :: Wiki
< SCI‎ | Specifications‎ | Resource files‎ | Decompression algorithms
Revision as of 08:06, 6 January 2009 by Timofonic (talk | contribs) (Merging of the SCI documentation)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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