Mercurial > touhou
annotate pytouhou/utils/lzss.py @ 130:11ab06f4c4c6
Introduce characters!
| author | Thibaut Girka <thib@sitedethib.com> |
|---|---|
| date | Sat, 10 Sep 2011 22:48:56 +0200 |
| parents | ab826bc29aa2 |
| children |
| rev | line source |
|---|---|
|
52
ab826bc29aa2
Add some documentation, GPLv3 headers, README and COPYING file.
Thibaut Girka <thib@sitedethib.com>
parents:
0
diff
changeset
|
1 # -*- encoding: utf-8 -*- |
|
ab826bc29aa2
Add some documentation, GPLv3 headers, README and COPYING file.
Thibaut Girka <thib@sitedethib.com>
parents:
0
diff
changeset
|
2 ## |
|
ab826bc29aa2
Add some documentation, GPLv3 headers, README and COPYING file.
Thibaut Girka <thib@sitedethib.com>
parents:
0
diff
changeset
|
3 ## Copyright (C) 2011 Thibaut Girka <thib@sitedethib.com> |
|
ab826bc29aa2
Add some documentation, GPLv3 headers, README and COPYING file.
Thibaut Girka <thib@sitedethib.com>
parents:
0
diff
changeset
|
4 ## |
|
ab826bc29aa2
Add some documentation, GPLv3 headers, README and COPYING file.
Thibaut Girka <thib@sitedethib.com>
parents:
0
diff
changeset
|
5 ## This program is free software; you can redistribute it and/or modify |
|
ab826bc29aa2
Add some documentation, GPLv3 headers, README and COPYING file.
Thibaut Girka <thib@sitedethib.com>
parents:
0
diff
changeset
|
6 ## it under the terms of the GNU General Public License as published |
|
ab826bc29aa2
Add some documentation, GPLv3 headers, README and COPYING file.
Thibaut Girka <thib@sitedethib.com>
parents:
0
diff
changeset
|
7 ## by the Free Software Foundation; version 3 only. |
|
ab826bc29aa2
Add some documentation, GPLv3 headers, README and COPYING file.
Thibaut Girka <thib@sitedethib.com>
parents:
0
diff
changeset
|
8 ## |
|
ab826bc29aa2
Add some documentation, GPLv3 headers, README and COPYING file.
Thibaut Girka <thib@sitedethib.com>
parents:
0
diff
changeset
|
9 ## This program is distributed in the hope that it will be useful, |
|
ab826bc29aa2
Add some documentation, GPLv3 headers, README and COPYING file.
Thibaut Girka <thib@sitedethib.com>
parents:
0
diff
changeset
|
10 ## but WITHOUT ANY WARRANTY; without even the implied warranty of |
|
ab826bc29aa2
Add some documentation, GPLv3 headers, README and COPYING file.
Thibaut Girka <thib@sitedethib.com>
parents:
0
diff
changeset
|
11 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
|
ab826bc29aa2
Add some documentation, GPLv3 headers, README and COPYING file.
Thibaut Girka <thib@sitedethib.com>
parents:
0
diff
changeset
|
12 ## GNU General Public License for more details. |
|
ab826bc29aa2
Add some documentation, GPLv3 headers, README and COPYING file.
Thibaut Girka <thib@sitedethib.com>
parents:
0
diff
changeset
|
13 ## |
|
ab826bc29aa2
Add some documentation, GPLv3 headers, README and COPYING file.
Thibaut Girka <thib@sitedethib.com>
parents:
0
diff
changeset
|
14 |
| 0 | 15 def decompress(bitstream, size, dictionary_size=0x2000, |
| 16 offset_size=13, length_size=4, minimum_match_length=3): | |
| 17 out_data = [] | |
| 18 dictionary = [0] * dictionary_size | |
| 19 dictionary_head = 1 | |
| 20 while len(out_data) < size: | |
| 21 flag = bitstream.read_bit() | |
| 22 if flag: | |
| 23 # The `flag` bit is set, indicating the upcoming chunk of data is a literal | |
| 24 # Add it to the uncompressed file, and store it in the dictionary | |
| 25 byte = bitstream.read(8) | |
| 26 dictionary[dictionary_head] = byte | |
| 27 dictionary_head = (dictionary_head + 1) % dictionary_size | |
| 28 out_data.append(byte) | |
| 29 else: | |
| 30 # The `flag` bit is not set, the upcoming chunk is a (offset, length) tuple | |
| 31 offset = bitstream.read(offset_size) | |
| 32 length = bitstream.read(length_size) + minimum_match_length | |
| 33 if (offset, length) == (0, 0): | |
| 34 break | |
| 35 for i in range(offset, offset + length): | |
| 36 out_data.append(dictionary[i % dictionary_size]) | |
| 37 dictionary[dictionary_head] = dictionary[i % dictionary_size] | |
| 38 dictionary_head = (dictionary_head + 1) % dictionary_size | |
| 39 return b''.join(chr(byte) for byte in out_data) |