Mercurial > touhou

annotate pytouhou/utils/lzss.pyx @ 490:1b532e7dd521

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Decrease PBG3 loading time by improving lzss and bitstream integration.
author Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
date Fri, 04 Oct 2013 14:28:49 +0200
parents 71cd4461bb7f
children 53fa73932e9a
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
490
1b532e7dd521 Decrease PBG3 loading time by improving lzss and bitstream integration.
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents: 368
diff changeset
15 cimport cython
252
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
16 from libc.stdlib cimport calloc, malloc, free
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
17
490
1b532e7dd521 Decrease PBG3 loading time by improving lzss and bitstream integration.
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents: 368
diff changeset
18 from .bitstream cimport BitStream
252
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
19
490
1b532e7dd521 Decrease PBG3 loading time by improving lzss and bitstream integration.
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents: 368
diff changeset
20
1b532e7dd521 Decrease PBG3 loading time by improving lzss and bitstream integration.
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents: 368
diff changeset
21 @cython.cdivision(True)
1b532e7dd521 Decrease PBG3 loading time by improving lzss and bitstream integration.
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents: 368
diff changeset
22 cpdef bytes decompress(BitStream bitstream,
252
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
23 Py_ssize_t size,
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
24 unsigned int dictionary_size=0x2000,
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
25 unsigned int offset_size=13,
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
26 unsigned int length_size=4,
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
27 unsigned int minimum_match_length=3):
490
1b532e7dd521 Decrease PBG3 loading time by improving lzss and bitstream integration.
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents: 368
diff changeset
28 cdef Py_ssize_t ptr, length
1b532e7dd521 Decrease PBG3 loading time by improving lzss and bitstream integration.
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents: 368
diff changeset
29 cdef unsigned int dictionary_head
368
71cd4461bb7f Minor optimizations
Thibaut Girka <thib@sitedethib.com>
parents: 367
diff changeset
30 cdef unsigned char byte
71cd4461bb7f Minor optimizations
Thibaut Girka <thib@sitedethib.com>
parents: 367
diff changeset
31 cdef char *out_data, *dictionary
252
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
32
368
71cd4461bb7f Minor optimizations
Thibaut Girka <thib@sitedethib.com>
parents: 367
diff changeset
33 out_data = <char*> malloc(size)
71cd4461bb7f Minor optimizations
Thibaut Girka <thib@sitedethib.com>
parents: 367
diff changeset
34 dictionary = <char*> calloc(dictionary_size, 1)
252
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
35 dictionary_head, ptr = 1, 0
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
36
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
37 while ptr < size:
367
2674c789e0c3 Various optimizations
Thibaut Girka <thib@sitedethib.com>
parents: 252
diff changeset
38 if bitstream.read_bit():
0
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
39 # 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
40 # Add it to the uncompressed file, and store it in the dictionary
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
41 byte = bitstream.read(8)
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
42 dictionary[dictionary_head] = byte
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
43 dictionary_head = (dictionary_head + 1) % dictionary_size
252
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
44 out_data[ptr] = byte
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
45 ptr += 1
0
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
46 else:
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
47 # 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
48 offset = bitstream.read(offset_size)
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
49 length = bitstream.read(length_size) + minimum_match_length
368
71cd4461bb7f Minor optimizations
Thibaut Girka <thib@sitedethib.com>
parents: 367
diff changeset
50 if ptr + length > size:
71cd4461bb7f Minor optimizations
Thibaut Girka <thib@sitedethib.com>
parents: 367
diff changeset
51 raise Exception
252
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
52 if offset == 0 and length == 0:
0
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
53 break
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
54 for i in range(offset, offset + length):
368
71cd4461bb7f Minor optimizations
Thibaut Girka <thib@sitedethib.com>
parents: 367
diff changeset
55 out_data[ptr] = dictionary[i % dictionary_size]
0
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
56 dictionary[dictionary_head] = dictionary[i % dictionary_size]
6b2c7af2384c Hello Gensokyo _o/
Thibaut Girka <thib@sitedethib.com>
parents:
diff changeset
57 dictionary_head = (dictionary_head + 1) % dictionary_size
368
71cd4461bb7f Minor optimizations
Thibaut Girka <thib@sitedethib.com>
parents: 367
diff changeset
58 ptr += 1
252
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
59
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
60 _out_data = out_data[:size]
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
61 free(out_data)
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
62 free(dictionary)
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
63 return _out_data
b5c7369abd7c Improve data reading perfs
Thibaut Girka <thib@sitedethib.com>
parents: 52
diff changeset
64