|
0
|
1 def decompress(bitstream, size, dictionary_size=0x2000,
|
|
|
2 offset_size=13, length_size=4, minimum_match_length=3):
|
|
|
3 out_data = []
|
|
|
4 dictionary = [0] * dictionary_size
|
|
|
5 dictionary_head = 1
|
|
|
6 while len(out_data) < size:
|
|
|
7 flag = bitstream.read_bit()
|
|
|
8 if flag:
|
|
|
9 # The `flag` bit is set, indicating the upcoming chunk of data is a literal
|
|
|
10 # Add it to the uncompressed file, and store it in the dictionary
|
|
|
11 byte = bitstream.read(8)
|
|
|
12 dictionary[dictionary_head] = byte
|
|
|
13 dictionary_head = (dictionary_head + 1) % dictionary_size
|
|
|
14 out_data.append(byte)
|
|
|
15 else:
|
|
|
16 # The `flag` bit is not set, the upcoming chunk is a (offset, length) tuple
|
|
|
17 offset = bitstream.read(offset_size)
|
|
|
18 length = bitstream.read(length_size) + minimum_match_length
|
|
|
19 if (offset, length) == (0, 0):
|
|
|
20 break
|
|
|
21 for i in range(offset, offset + length):
|
|
|
22 out_data.append(dictionary[i % dictionary_size])
|
|
|
23 dictionary[dictionary_head] = dictionary[i % dictionary_size]
|
|
|
24 dictionary_head = (dictionary_head + 1) % dictionary_size
|
|
|
25 return b''.join(chr(byte) for byte in out_data)
|
