Mercurial > touhou

annotate pytouhou/utils/lzss.py @ 131:fab7ad2f0d8b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Use Cython, improve performances!
author Thibaut Girka <thib@sitedethib.com>
date Sun, 11 Sep 2011 02:02:59 +0200
parents ab826bc29aa2
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
15 def decompress(bitstream, size, dictionary_size=0x2000,
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
16 offset_size=13, length_size=4, minimum_match_length=3):
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
17 out_data = []
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
18 dictionary = [0] * dictionary_size
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
19 dictionary_head = 1
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
20 while len(out_data) < size:
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
21 flag = bitstream.read_bit()
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
22 if flag:
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
23 # The `flag` bit is set, indicating the upcoming chunk of data is a literal
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
24 # Add it to the uncompressed file, and store it in the dictionary
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
25 byte = bitstream.read(8)
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
26 dictionary[dictionary_head] = byte
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
27 dictionary_head = (dictionary_head + 1) % dictionary_size
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
28 out_data.append(byte)
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
29 else:
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
30 # The `flag` bit is not set, the upcoming chunk is a (offset, length) tuple
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
31 offset = bitstream.read(offset_size)
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
32 length = bitstream.read(length_size) + minimum_match_length
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
33 if (offset, length) == (0, 0):
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
34 break
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
35 for i in range(offset, offset + length):
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
36 out_data.append(dictionary[i % dictionary_size])
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
37 dictionary[dictionary_head] = dictionary[i % dictionary_size]
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
38 dictionary_head = (dictionary_head + 1) % dictionary_size
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
39 return b''.join(chr(byte) for byte in out_data)