1 #!/usr/bin/python
2 # -*- coding: utf-8 -*-
3
4from __future__ import division
5from __future__ import unicode_literals
6from __future__ import print_function
7from __future__ import absolute_import
8from builtins import range
9from builtins import int
10from builtins import chr
11from future import standard_library
12standard_library.install_aliases()
13from builtins import object
14import math
15import re
16
17
18keyStrBase64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/="
19keyStrUriSafe = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+-$"
20baseReverseDic = {};
21
22class Object(object):
23    def __init__(self, **kwargs):
24        for k, v in kwargs.items():
25            setattr(self, k, v)
26
27
28def getBaseValue(alphabet, character):
29    if alphabet not in baseReverseDic:
30        baseReverseDic[alphabet] = {}
31    for i in range(len(alphabet)):
32        baseReverseDic[alphabet][alphabet[i]] = i
33    return baseReverseDic[alphabet][character]
34
35
36def _compress(uncompressed, bitsPerChar, getCharFromInt):
37    if (uncompressed is None):
38        return ""
39
40    context_dictionary = {}
41    context_dictionaryToCreate= {}
42    context_c = ""
43    context_wc = ""
44    context_w = ""
45    context_enlargeIn = 2 # Compensate for the first entry which should not count
46    context_dictSize = 3
47    context_numBits = 2
48    context_data = []
49    context_data_val = 0
50    context_data_position = 0
51
52    for ii in range(len(uncompressed)):
53        context_c = uncompressed[ii]
54        if context_c not in context_dictionary:
55            context_dictionary[context_c] = context_dictSize
56            context_dictSize += 1
57            context_dictionaryToCreate[context_c] = True
58
59        context_wc = context_w + context_c
60        if context_wc in context_dictionary:
61            context_w = context_wc
62        else:
63            if context_w in context_dictionaryToCreate:
64                if ord(context_w[0]) < 256:
65                    for i in range(context_numBits):
66                        context_data_val = (context_data_val << 1)
67                        if context_data_position == bitsPerChar-1:
68                            context_data_position = 0
69                            context_data.append(getCharFromInt(context_data_val))
70                            context_data_val = 0
71                        else:
72                            context_data_position += 1
73                    value = ord(context_w[0])
74                    for i in range(8):
75                        context_data_val = (context_data_val << 1) | (value & 1)
76                        if context_data_position == bitsPerChar - 1:
77                            context_data_position = 0
78                            context_data.append(getCharFromInt(context_data_val))
79                            context_data_val = 0
80                        else:
81                            context_data_position += 1
82                        value = value >> 1
83
84                else:
85                    value = 1
86                    for i in range(context_numBits):
87                        context_data_val = (context_data_val << 1) | value
88                        if context_data_position == bitsPerChar - 1:
89                            context_data_position = 0
90                            context_data.append(getCharFromInt(context_data_val))
91                            context_data_val = 0
92                        else:
93                            context_data_position += 1
94                        value = 0
95                    value = ord(context_w[0])
96                    for i in range(16):
97                        context_data_val = (context_data_val << 1) | (value & 1)
98                        if context_data_position == bitsPerChar - 1:
99                            context_data_position = 0
100                            context_data.append(getCharFromInt(context_data_val))
101                            context_data_val = 0
102                        else:
103                            context_data_position += 1
104                        value = value >> 1
105                context_enlargeIn -= 1
106                if context_enlargeIn == 0:
107                    context_enlargeIn = math.pow(2, context_numBits)
108                    context_numBits += 1
109                del context_dictionaryToCreate[context_w]
110            else:
111                value = context_dictionary[context_w]
112                for i in range(context_numBits):
113                    context_data_val = (context_data_val << 1) | (value & 1)
114                    if context_data_position == bitsPerChar - 1:
115                        context_data_position = 0
116                        context_data.append(getCharFromInt(context_data_val))
117                        context_data_val = 0
118                    else:
119                        context_data_position += 1
120                    value = value >> 1
121
122            context_enlargeIn -= 1
123            if context_enlargeIn == 0:
124                context_enlargeIn = math.pow(2, context_numBits)
125                context_numBits += 1
126
127            # Add wc to the dictionary.
128            context_dictionary[context_wc] = context_dictSize
129            context_dictSize += 1
130            context_w = str(context_c)
131
132    # Output the code for w.
133    if context_w != "":
134        if context_w in context_dictionaryToCreate:
135            if ord(context_w[0]) < 256:
136                for i in range(context_numBits):
137                    context_data_val = (context_data_val << 1)
138                    if context_data_position == bitsPerChar-1:
139                        context_data_position = 0
140                        context_data.append(getCharFromInt(context_data_val))
141                        context_data_val = 0
142                    else:
143                        context_data_position += 1
144                value = ord(context_w[0])
145                for i in range(8):
146                    context_data_val = (context_data_val << 1) | (value & 1)
147                    if context_data_position == bitsPerChar - 1:
148                        context_data_position = 0
149                        context_data.append(getCharFromInt(context_data_val))
150                        context_data_val = 0
151                    else:
152                        context_data_position += 1
153                    value = value >> 1
154            else:
155                value = 1
156                for i in range(context_numBits):
157                    context_data_val = (context_data_val << 1) | value
158                    if context_data_position == bitsPerChar - 1:
159                        context_data_position = 0
160                        context_data.append(getCharFromInt(context_data_val))
161                        context_data_val = 0
162                    else:
163                        context_data_position += 1
164                    value = 0
165                value = ord(context_w[0])
166                for i in range(16):
167                    context_data_val = (context_data_val << 1) | (value & 1)
168                    if context_data_position == bitsPerChar - 1:
169                        context_data_position = 0
170                        context_data.append(getCharFromInt(context_data_val))
171                        context_data_val = 0
172                    else:
173                        context_data_position += 1
174                    value = value >> 1
175            context_enlargeIn -= 1
176            if context_enlargeIn == 0:
177                context_enlargeIn = math.pow(2, context_numBits)
178                context_numBits += 1
179            del context_dictionaryToCreate[context_w]
180        else:
181            value = context_dictionary[context_w]
182            for i in range(context_numBits):
183                context_data_val = (context_data_val << 1) | (value & 1)
184                if context_data_position == bitsPerChar - 1:
185                    context_data_position = 0
186                    context_data.append(getCharFromInt(context_data_val))
187                    context_data_val = 0
188                else:
189                    context_data_position += 1
190                value = value >> 1
191
192    context_enlargeIn -= 1
193    if context_enlargeIn == 0:
194        context_enlargeIn = math.pow(2, context_numBits)
195        context_numBits += 1
196
197    # Mark the end of the stream
198    value = 2
199    for i in range(context_numBits):
200        context_data_val = (context_data_val << 1) | (value & 1)
201        if context_data_position == bitsPerChar - 1:
202            context_data_position = 0
203            context_data.append(getCharFromInt(context_data_val))
204            context_data_val = 0
205        else:
206            context_data_position += 1
207        value = value >> 1
208
209    # Flush the last char
210    while True:
211        context_data_val = (context_data_val << 1)
212        if context_data_position == bitsPerChar - 1:
213            context_data.append(getCharFromInt(context_data_val))
214            break
215        else:
216           context_data_position += 1
217
218    return "".join(context_data)
219
220
221def _decompress(length, resetValue, getNextValue):
222    dictionary = {}
223    enlargeIn = 4
224    dictSize = 4
225    numBits = 3
226    entry = ""
227    result = []
228
229    data = Object(
230        val=getNextValue(0),
231        position=resetValue,
232        index=1
233    )
234
235    for i in range(3):
236        dictionary[i] = i
237
238    bits = 0
239    maxpower = math.pow(2, 2)
240    power = 1
241
242    while power != maxpower:
243        resb = data.val & data.position
244        data.position >>= 1
245        if data.position == 0:
246            data.position = resetValue
247            data.val = getNextValue(data.index)
248            data.index += 1
249
250        bits |= power if resb > 0 else 0
251        power <<= 1;
252
253    next = bits
254    if next == 0:
255        bits = 0
256        maxpower = math.pow(2, 8)
257        power = 1
258        while power != maxpower:
259            resb = data.val & data.position
260            data.position >>= 1
261            if data.position == 0:
262                data.position = resetValue
263                data.val = getNextValue(data.index)
264                data.index += 1
265            bits |= power if resb > 0 else 0
266            power <<= 1
267        c = chr(bits)
268    elif next == 1:
269        bits = 0
270        maxpower = math.pow(2, 16)
271        power = 1
272        while power != maxpower:
273            resb = data.val & data.position
274            data.position >>= 1
275            if data.position == 0:
276                data.position = resetValue;
277                data.val = getNextValue(data.index)
278                data.index += 1
279            bits |= power if resb > 0 else 0
280            power <<= 1
281        c = chr(bits)
282    elif next == 2:
283        return ""
284
285    dictionary[3] = c
286    w = c
287    result.append(c)
288    counter = 0
289    while True:
290        counter += 1
291        if data.index > length:
292            return ""
293
294        bits = 0
295        maxpower = math.pow(2, numBits)
296        power = 1
297        while power != maxpower:
298            resb = data.val & data.position
299            data.position >>= 1
300            if data.position == 0:
301                data.position = resetValue;
302                data.val = getNextValue(data.index)
303                data.index += 1
304            bits |= power if resb > 0 else 0
305            power <<= 1
306
307        c = bits
308        if c == 0:
309            bits = 0
310            maxpower = math.pow(2, 8)
311            power = 1
312            while power != maxpower:
313                resb = data.val & data.position
314                data.position >>= 1
315                if data.position == 0:
316                    data.position = resetValue
317                    data.val = getNextValue(data.index)
318                    data.index += 1
319                bits |= power if resb > 0 else 0
320                power <<= 1
321
322            dictionary[dictSize] = chr(bits)
323            dictSize += 1
324            c = dictSize - 1
325            enlargeIn -= 1
326        elif c == 1:
327            bits = 0
328            maxpower = math.pow(2, 16)
329            power = 1
330            while power != maxpower:
331                resb = data.val & data.position
332                data.position >>= 1
333                if data.position == 0:
334                    data.position = resetValue;
335                    data.val = getNextValue(data.index)
336                    data.index += 1
337                bits |= power if resb > 0 else 0
338                power <<= 1
339            dictionary[dictSize] = chr(bits)
340            dictSize += 1
341            c = dictSize - 1
342            enlargeIn -= 1
343        elif c == 2:
344            return "".join(result)
345
346
347        if enlargeIn == 0:
348            enlargeIn = math.pow(2, numBits)
349            numBits += 1
350
351        if c in dictionary:
352            entry = dictionary[c]
353        else:
354            if c == dictSize:
355                entry = w + w[0]
356            else:
357                return None
358        result.append(entry)
359
360        # Add w+entry[0] to the dictionary.
361        dictionary[dictSize] = w + entry[0]
362        dictSize += 1
363        enlargeIn -= 1
364
365        w = entry
366        if enlargeIn == 0:
367            enlargeIn = math.pow(2, numBits)
368            numBits += 1
369
370
371class LZString(object):
372    @staticmethod
373    def compress(uncompressed):
374        return _compress(uncompressed, 16, chr)
375
376    @staticmethod
377    def compressToUTF16(uncompressed):
378        if uncompressed is None:
379            return ""
380        return _compress(uncompressed, 15, lambda a: chr(a+32)) + " "
381
382    @staticmethod
383    def compressToBase64(uncompressed):
384        if uncompressed is None:
385            return ""
386        res = _compress(uncompressed, 6, lambda a: keyStrBase64[a])
387        # To produce valid Base64
388        end = len(res) % 4
389        if end > 0:
390            res += "="*(4 - end)
391        return res
392
393    @staticmethod
394    def compressToEncodedURIComponent(uncompressed):
395        if uncompressed is None:
396            return ""
397        return _compress(uncompressed, 6, lambda a: keyStrUriSafe[a])
398
399    @staticmethod
400    def decompress(compressed):
401        if compressed is None:
402            return ""
403        if compressed == "":
404            return None
405        return _decompress(len(compressed), 32768, lambda index: ord(compressed[index]))
406
407    @staticmethod
408    def decompressFromUTF16(compressed):
409        if compressed is None:
410            return ""
411        if compressed == "":
412            return None
413        return _decompress(len(compressed), 16384, lambda index: compressed[index] - 32)
414
415    @staticmethod
416    def decompressFromBase64(compressed):
417        if compressed is None:
418            return ""
419        if compressed == "":
420            return None
421        return _decompress(len(compressed), 32, lambda index: getBaseValue(keyStrBase64, compressed[index]))
422
423    @staticmethod
424    def decompressFromEncodedURIComponent(compressed):
425        if compressed is None:
426            return ""
427        if compressed == "":
428            return None
429        compressed = compressed.replace(" ", "+")
430        return _decompress(len(compressed), 32, lambda index: getBaseValue(keyStrUriSafe, compressed[index]))
431