Mercurial > touhou

annotate pytouhou/utils/lzss.pyx @ 264:3ac8b135592c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Homogenise score increase in item collection, in prevision for text handling.
author Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
date Sun, 15 Jan 2012 19:39:01 +0100
parents b5c7369abd7c
children 2674c789e0c3
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
252
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
15 from libc.stdlib cimport calloc, malloc, free
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
16
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
17
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
18 cpdef bytes decompress(object bitstream,
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
19 Py_ssize_t size,
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
20 unsigned int dictionary_size=0x2000,
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
21 unsigned int offset_size=13,
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
22 unsigned int length_size=4,
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
23 unsigned int minimum_match_length=3):
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
24 cdef unsigned int i, ptr, dictionary_head, offset, length
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
25 cdef unsigned char flag, byte, *out_data, *dictionary
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
26 cdef bytes _out_data
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
27
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
28 out_data = <unsigned char*> malloc(size)
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
29 dictionary = <unsigned char*> calloc(dictionary_size, 1)
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
30 dictionary_head, ptr = 1, 0
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
31
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
32 while ptr < size:
0
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
33 flag = bitstream.read_bit()
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
34 if flag:
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
35 # 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
36 # Add it to the uncompressed file, and store it in the dictionary
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
37 byte = bitstream.read(8)
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
38 dictionary[dictionary_head] = byte
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
39 dictionary_head = (dictionary_head + 1) % dictionary_size
252
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
40 out_data[ptr] = byte
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
41 ptr += 1
0
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
42 else:
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
43 # 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
44 offset = bitstream.read(offset_size)
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
45 length = bitstream.read(length_size) + minimum_match_length
252
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
46 if offset == 0 and length == 0:
0
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
47 break
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
48 for i in range(offset, offset + length):
252
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
49 out_data[ptr % size] = dictionary[i % dictionary_size]
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
50 ptr += 1
0
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
51 dictionary[dictionary_head] = dictionary[i % dictionary_size]
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
52 dictionary_head = (dictionary_head + 1) % dictionary_size
252
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
53
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
54 _out_data = out_data[:size]
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
55 free(out_data)
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
56 free(dictionary)
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
57 return _out_data
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
58