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.

       /* 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

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

Contents

Decompression algorithm DCL-EXPLODE

M

Huffman Tree #1

Huffman Tree #2

Huffman Tree #3