This repository has been archived by the owner on Nov 22, 2020. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 3
/
unlzw.py
181 lines (149 loc) · 6.7 KB
/
unlzw.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
def unlzw(data):
# This function was adapted for Python from Mark Adler's C implementation
# https://github.com/umeat/unlzw
# Decompress compressed data generated by the Unix compress utility (LZW
# compression, files with .Z suffix). Input can be given as any type which
# can be 'converted' to a bytearray (e.g. string, or bytearray). Returns
# decompressed data as string, or raises error.
# Written by Brandon Owen, May 2016, brandon.owen@hotmail.com
# Adapted from original work by Mark Adler - orginal copyright notice below
# Copyright (C) 2014, 2015 Mark Adler
# This software is provided 'as-is', without any express or implied
# warranty. In no event will the authors be held liable for any damages
# arising from the use of this software.
# Permission is granted to anyone to use this software for any purpose,
# including commercial applications, and to alter it and redistribute it
# freely, subject to the following restrictions:
# 1. The origin of this software must not be misrepresented; you must not
# claim that you wrote the original software. If you use this software
# in a product, an acknowledgment in the product documentation would be
# appreciated but is not required.
# 2. Altered source versions must be plainly marked as such, and must not be
# misrepresented as being the original software.
# 3. This notice may not be removed or altered from any source distribution.
# Mark Adler
# madler@alumni.caltech.edu
# Convert input data stream to byte array, and get length of that array
try:
ba_in = bytearray(data)
except ValueError:
raise TypeError("Unable to convert inputted data to bytearray")
inlen = len(ba_in)
prefix = [None] * 65536 # index to LZW prefix string
suffix = [None] * 65536 # one-character LZW suffix
# Process header
if inlen < 3:
raise ValueError("Invalid Input: Length of input too short for processing")
if (ba_in[0] != 0x1f) or (ba_in[1] != 0x9d):
raise ValueError("Invalid Header Flags Byte: Incorrect magic bytes")
flags = ba_in[2]
if flags & 0x60:
raise ValueError("Invalid Header Flags Byte: Flag byte contains invalid data")
max_ = flags & 0x1f
if (max_ < 9) or (max_ > 16):
raise ValueError("Invalid Header Flags Byte: Max code size bits out of range")
if (max_ == 9): max_ = 10 # 9 doesn't really mean 9
flags &= 0x80 # true if block compressed
# Clear table, start at nine bits per symbol
bits = 9
mask = 0x1ff
end = 256 if flags else 255
# Ensure stream is initially valid
if inlen == 3: return 0 # zero-length input is permitted
if inlen == 4: # a partial code is not okay
raise ValueError("Invalid Data: Stream ended in the middle of a code")
# Set up: get the first 9-bit code, which is the first decompressed byte,
# but don't create a table entry until the next code
buf = ba_in[3]
buf += ba_in[4] << 8
final = prev = buf & mask # code
buf >>= bits
left = 16 - bits
if prev > 255:
raise ValueError("Invalid Data: First code must be a literal")
# We have output - allocate and set up an output buffer with first byte
put = [final]
# Decode codes
mark = 3 # start of compressed data
nxt = 5 # consumed five bytes so far
while nxt < inlen:
# If the table will be full after this, increment the code size
if (end >= mask) and (bits < max_):
# Flush unused input bits and bytes to next 8*bits bit boundary
# (this is a vestigial aspect of the compressed data format
# derived from an implementation that made use of a special VAX
# machine instruction!)
rem = (nxt - mark) % bits
if (rem):
rem = bits - rem
if rem >= inlen - nxt:
break
nxt += rem
buf = 0
left = 0
# mark this new location for computing the next flush
mark = nxt
# increment the number of bits per symbol
bits += 1
mask <<= 1
mask += 1
# Get a code of bits bits
buf += ba_in[nxt] << left
nxt += 1
left += 8
if left < bits:
if nxt == inlen:
raise ValueError("Invalid Data: Stream ended in the middle of a code")
buf += ba_in[nxt] << left
nxt += 1
left += 8
code = buf & mask
buf >>= bits
left -= bits
# process clear code (256)
if (code == 256) and flags:
# Flush unused input bits and bytes to next 8*bits bit boundary
rem = (nxt - mark) % bits
if rem:
rem = bits - rem
if rem > inlen - nxt:
break
nxt += rem
buf = 0
left = 0
# Mark this location for computing the next flush
mark = nxt
# Go back to nine bits per symbol
bits = 9 # initialize bits and mask
mask = 0x1ff
end = 255 # empty table
continue # get next code
# Process LZW code
temp = code # save the current code
stack = [] # buffer for reversed match - empty stack
# Special code to reuse last match
if code > end:
# Be picky on the allowed code here, and make sure that the
# code we drop through (prev) will be a valid index so that
# random input does not cause an exception
if (code != end + 1) or (prev > end):
raise ValueError("Invalid Data: Invalid code detected")
stack.append(final)
code = prev
# Walk through linked list to generate output in reverse order
while code >= 256:
stack.append(suffix[code])
code = prefix[code]
stack.append(code)
final = code
# Link new table entry
if end < mask:
end += 1
prefix[end] = prev
suffix[end] = final
# Set previous code for next iteration
prev = temp
# Write stack to output in forward order
put += stack[::-1]
# Return the decompressed data as string
return bytes(bytearray(put))