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