Created
February 23, 2022 13:16
-
-
Save MineRobber9000/bdc3ce6c73b32cb1e4a56817eb392222 to your computer and use it in GitHub Desktop.
LibDeflate (by Haoqian He/SafeteeWoW), pared down for ComputerCraft usage. Use `LibDeflate_min.lua` as LibDeflate to save space.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
--[[-- | |
LibDeflate 1.0.2-release <br> | |
Pure Lua compressor and decompressor with high compression ratio using | |
DEFLATE/zlib format. | |
Based on the original by Haoqian He, pared down for ComputerCraft usage | |
by Robert "khuxkm/minerobber" Miles | |
]] --[[ | |
zlib License | |
(C) 2018-2021 Haoqian He | |
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. | |
License History: | |
1. GNU General Public License Version 3 in v1.0.0 and earlier versions. | |
2. GNU Lesser General Public License Version 3 in v1.0.1 | |
3. the zlib License since v1.0.2 | |
Credits and Disclaimer: | |
This library rewrites the code from the algorithm | |
and the ideas of the following projects, | |
and uses their code to help to test the correctness of this library, | |
but their code is not included directly in the library itself. | |
Their original licenses shall be comply when used. | |
1. zlib, by Jean-loup Gailly (compression) and Mark Adler (decompression). | |
http://www.zlib.net/ | |
Licensed under zlib License. http://www.zlib.net/zlib_license.html | |
For the compression algorithm. | |
2. puff, by Mark Adler. https://github.com/madler/zlib/tree/master/contrib/puff | |
Licensed under zlib License. http://www.zlib.net/zlib_license.html | |
For the decompression algorithm. | |
3. LibCompress, by jjsheets and Galmok of European Stormrage (Horde) | |
https://www.wowace.com/projects/libcompress | |
Licensed under GPLv2. | |
https://www.gnu.org/licenses/old-licenses/gpl-2.0.html | |
For the code to create customized codec. | |
4. WeakAuras2, | |
https://github.com/WeakAuras/WeakAuras2 | |
Licensed under GPLv2. | |
For the 6bit encoding and decoding. | |
]] | |
local LibDeflate | |
do | |
-- Semantic version. all lowercase. | |
-- Suffix can be alpha1, alpha2, beta1, beta2, rc1, rc2, etc. | |
-- NOTE: Two version numbers needs to modify. | |
-- 1. On the top of LibDeflate.lua | |
-- 2. _VERSION | |
-- 3. _MINOR | |
-- version to store the official version of LibDeflate | |
local _VERSION = "1.0.2-release" | |
local _COPYRIGHT = "LibDeflate " .. _VERSION .. | |
" Copyright (C) 2018-2021 Haoqian He." .. | |
" Modifications (c) 2022 minerobber".. | |
" Licensed under the zlib License" | |
LibDeflate = {} | |
LibDeflate._VERSION = _VERSION | |
LibDeflate._COPYRIGHT = _COPYRIGHT | |
end | |
-- localize Lua api for faster access. | |
local assert = assert | |
local error = error | |
local pairs = pairs | |
local string_byte = string.byte | |
local string_char = string.char | |
local string_find = string.find | |
local string_gsub = string.gsub | |
local string_sub = string.sub | |
local table_concat = table.concat | |
local table_sort = table.sort | |
local tostring = tostring | |
local type = type | |
-- Converts i to 2^i, (0<=i<=32) | |
-- This is used to implement bit left shift and bit right shift. | |
-- "x >> y" in C: "(x-x%_pow2[y])/_pow2[y]" in Lua | |
-- "x << y" in C: "x*_pow2[y]" in Lua | |
local _pow2 = {} | |
-- Converts any byte to a character, (0<=byte<=255) | |
local _byte_to_char = {} | |
-- _reverseBitsTbl[len][val] stores the bit reverse of | |
-- the number with bit length "len" and value "val" | |
-- For example, decimal number 6 with bits length 5 is binary 00110 | |
-- It's reverse is binary 01100, | |
-- which is decimal 12 and 12 == _reverseBitsTbl[5][6] | |
-- 1<=len<=9, 0<=val<=2^len-1 | |
-- The reason for 1<=len<=9 is that the max of min bitlen of huffman code | |
-- of a huffman alphabet is 9? | |
local _reverse_bits_tbl = {} | |
-- Convert a LZ77 length (3<=len<=258) to | |
-- a deflate literal/LZ77_length code (257<=code<=285) | |
local _length_to_deflate_code = {} | |
-- convert a LZ77 length (3<=len<=258) to | |
-- a deflate literal/LZ77_length code extra bits. | |
local _length_to_deflate_extra_bits = {} | |
-- Convert a LZ77 length (3<=len<=258) to | |
-- a deflate literal/LZ77_length code extra bit length. | |
local _length_to_deflate_extra_bitlen = {} | |
-- Convert a small LZ77 distance (1<=dist<=256) to a deflate code. | |
local _dist256_to_deflate_code = {} | |
-- Convert a small LZ77 distance (1<=dist<=256) to | |
-- a deflate distance code extra bits. | |
local _dist256_to_deflate_extra_bits = {} | |
-- Convert a small LZ77 distance (1<=dist<=256) to | |
-- a deflate distance code extra bit length. | |
local _dist256_to_deflate_extra_bitlen = {} | |
-- Convert a literal/LZ77_length deflate code to LZ77 base length | |
-- The key of the table is (code - 256), 257<=code<=285 | |
local _literal_deflate_code_to_base_len = | |
{ | |
3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, | |
83, 99, 115, 131, 163, 195, 227, 258 | |
} | |
-- Convert a literal/LZ77_length deflate code to base LZ77 length extra bits | |
-- The key of the table is (code - 256), 257<=code<=285 | |
local _literal_deflate_code_to_extra_bitlen = | |
{ | |
0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, | |
5, 5, 5, 0 | |
} | |
-- Convert a distance deflate code to base LZ77 distance. (0<=code<=29) | |
local _dist_deflate_code_to_base_dist = { | |
[0] = 1, | |
2, | |
3, | |
4, | |
5, | |
7, | |
9, | |
13, | |
17, | |
25, | |
33, | |
49, | |
65, | |
97, | |
129, | |
193, | |
257, | |
385, | |
513, | |
769, | |
1025, | |
1537, | |
2049, | |
3073, | |
4097, | |
6145, | |
8193, | |
12289, | |
16385, | |
24577 | |
} | |
-- Convert a distance deflate code to LZ77 bits length. (0<=code<=29) | |
local _dist_deflate_code_to_extra_bitlen = | |
{ | |
[0] = 0, | |
0, | |
0, | |
0, | |
1, | |
1, | |
2, | |
2, | |
3, | |
3, | |
4, | |
4, | |
5, | |
5, | |
6, | |
6, | |
7, | |
7, | |
8, | |
8, | |
9, | |
9, | |
10, | |
10, | |
11, | |
11, | |
12, | |
12, | |
13, | |
13 | |
} | |
-- The code order of the first huffman header in the dynamic deflate block. | |
-- See the page 12 of RFC1951 | |
local _rle_codes_huffman_bitlen_order = { | |
16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 | |
} | |
-- The following tables are used by fixed deflate block. | |
-- The value of these tables are assigned at the bottom of the source. | |
-- The huffman code of the literal/LZ77_length deflate codes, | |
-- in fixed deflate block. | |
local _fix_block_literal_huffman_code | |
-- Convert huffman code of the literal/LZ77_length to deflate codes, | |
-- in fixed deflate block. | |
local _fix_block_literal_huffman_to_deflate_code | |
-- The bit length of the huffman code of literal/LZ77_length deflate codes, | |
-- in fixed deflate block. | |
local _fix_block_literal_huffman_bitlen | |
-- The count of each bit length of the literal/LZ77_length deflate codes, | |
-- in fixed deflate block. | |
local _fix_block_literal_huffman_bitlen_count | |
-- The huffman code of the distance deflate codes, | |
-- in fixed deflate block. | |
local _fix_block_dist_huffman_code | |
-- Convert huffman code of the distance to deflate codes, | |
-- in fixed deflate block. | |
local _fix_block_dist_huffman_to_deflate_code | |
-- The bit length of the huffman code of the distance deflate codes, | |
-- in fixed deflate block. | |
local _fix_block_dist_huffman_bitlen | |
-- The count of each bit length of the huffman code of | |
-- the distance deflate codes, | |
-- in fixed deflate block. | |
local _fix_block_dist_huffman_bitlen_count | |
for i = 0, 255 do _byte_to_char[i] = string_char(i) end | |
do | |
local pow = 1 | |
for i = 0, 32 do | |
_pow2[i] = pow | |
pow = pow * 2 | |
end | |
end | |
for i = 1, 9 do | |
_reverse_bits_tbl[i] = {} | |
for j = 0, _pow2[i + 1] - 1 do | |
local reverse = 0 | |
local value = j | |
for _ = 1, i do | |
-- The following line is equivalent to "res | (code %2)" in C. | |
reverse = reverse - reverse % 2 + | |
(((reverse % 2 == 1) or (value % 2) == 1) and 1 or 0) | |
value = (value - value % 2) / 2 | |
reverse = reverse * 2 | |
end | |
_reverse_bits_tbl[i][j] = (reverse - reverse % 2) / 2 | |
end | |
end | |
-- The source code is written according to the pattern in the numbers | |
-- in RFC1951 Page10. | |
do | |
local a = 18 | |
local b = 16 | |
local c = 265 | |
local bitlen = 1 | |
for len = 3, 258 do | |
if len <= 10 then | |
_length_to_deflate_code[len] = len + 254 | |
_length_to_deflate_extra_bitlen[len] = 0 | |
elseif len == 258 then | |
_length_to_deflate_code[len] = 285 | |
_length_to_deflate_extra_bitlen[len] = 0 | |
else | |
if len > a then | |
a = a + b | |
b = b * 2 | |
c = c + 4 | |
bitlen = bitlen + 1 | |
end | |
local t = len - a - 1 + b / 2 | |
_length_to_deflate_code[len] = (t - (t % (b / 8))) / (b / 8) + c | |
_length_to_deflate_extra_bitlen[len] = bitlen | |
_length_to_deflate_extra_bits[len] = t % (b / 8) | |
end | |
end | |
end | |
-- The source code is written according to the pattern in the numbers | |
-- in RFC1951 Page11. | |
do | |
_dist256_to_deflate_code[1] = 0 | |
_dist256_to_deflate_code[2] = 1 | |
_dist256_to_deflate_extra_bitlen[1] = 0 | |
_dist256_to_deflate_extra_bitlen[2] = 0 | |
local a = 3 | |
local b = 4 | |
local code = 2 | |
local bitlen = 0 | |
for dist = 3, 256 do | |
if dist > b then | |
a = a * 2 | |
b = b * 2 | |
code = code + 2 | |
bitlen = bitlen + 1 | |
end | |
_dist256_to_deflate_code[dist] = (dist <= a) and code or (code + 1) | |
_dist256_to_deflate_extra_bitlen[dist] = (bitlen < 0) and 0 or bitlen | |
if b >= 8 then | |
_dist256_to_deflate_extra_bits[dist] = (dist - b / 2 - 1) % (b / 4) | |
end | |
end | |
end | |
--- Calculate the Adler-32 checksum of the string. <br> | |
-- See RFC1950 Page 9 https://tools.ietf.org/html/rfc1950 for the | |
-- definition of Adler-32 checksum. | |
-- @param str [string] the input string to calcuate its Adler-32 checksum. | |
-- @return [integer] The Adler-32 checksum, which is greater or equal to 0, | |
-- and less than 2^32 (4294967296). | |
function LibDeflate:Adler32(str) | |
-- This function is loop unrolled by better performance. | |
-- | |
-- Here is the minimum code: | |
-- | |
-- local a = 1 | |
-- local b = 0 | |
-- for i=1, #str do | |
-- local s = string.byte(str, i, i) | |
-- a = (a+s)%65521 | |
-- b = (b+a)%65521 | |
-- end | |
-- return b*65536+a | |
if type(str) ~= "string" then | |
error(("Usage: LibDeflate:Adler32(str):" .. | |
" 'str' - string expected got '%s'."):format(type(str)), 2) | |
end | |
local strlen = #str | |
local i = 1 | |
local a = 1 | |
local b = 0 | |
while i <= strlen - 15 do | |
local x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16 = | |
string_byte(str, i, i + 15) | |
b = | |
(b + 16 * a + 16 * x1 + 15 * x2 + 14 * x3 + 13 * x4 + 12 * x5 + 11 * x6 + | |
10 * x7 + 9 * x8 + 8 * x9 + 7 * x10 + 6 * x11 + 5 * x12 + 4 * x13 + 3 * | |
x14 + 2 * x15 + x16) % 65521 | |
a = | |
(a + x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10 + x11 + x12 + x13 + | |
x14 + x15 + x16) % 65521 | |
i = i + 16 | |
end | |
while (i <= strlen) do | |
local x = string_byte(str, i, i) | |
a = (a + x) % 65521 | |
b = (b + a) % 65521 | |
i = i + 1 | |
end | |
return (b * 65536 + a) % 4294967296 | |
end | |
-- Compare adler32 checksum. | |
-- adler32 should be compared with a mod to avoid sign problem | |
-- 4072834167 (unsigned) is the same adler32 as -222133129 | |
local function IsEqualAdler32(actual, expected) | |
return (actual % 4294967296) == (expected % 4294967296) | |
end | |
--- Create a preset dictionary. | |
-- | |
-- This function is not fast, and the memory consumption of the produced | |
-- dictionary is about 50 times of the input string. Therefore, it is suggestted | |
-- to run this function only once in your program. | |
-- | |
-- It is very important to know that if you do use a preset dictionary, | |
-- compressors and decompressors MUST USE THE SAME dictionary. That is, | |
-- dictionary must be created using the same string. If you update your program | |
-- with a new dictionary, people with the old version won't be able to transmit | |
-- data with people with the new version. Therefore, changing the dictionary | |
-- must be very careful. | |
-- | |
-- The parameters "strlen" and "adler32" add a layer of verification to ensure | |
-- the parameter "str" is not modified unintentionally during the program | |
-- development. | |
-- | |
-- @usage local dict_str = "1234567890" | |
-- | |
-- -- print(dict_str:len(), LibDeflate:Adler32(dict_str)) | |
-- -- Hardcode the print result below to verify it to avoid acciently | |
-- -- modification of 'str' during the program development. | |
-- -- string length: 10, Adler-32: 187433486, | |
-- -- Don't calculate string length and its Adler-32 at run-time. | |
-- | |
-- local dict = LibDeflate:CreateDictionary(dict_str, 10, 187433486) | |
-- | |
-- @param str [string] The string used as the preset dictionary. <br> | |
-- You should put stuffs that frequently appears in the dictionary | |
-- string and preferablely put more frequently appeared stuffs toward the end | |
-- of the string. <br> | |
-- Empty string and string longer than 32768 bytes are not allowed. | |
-- @param strlen [integer] The length of 'str'. Please pass in this parameter | |
-- as a hardcoded constant, in order to verify the content of 'str'. The value | |
-- of this parameter should be known before your program runs. | |
-- @param adler32 [integer] The Adler-32 checksum of 'str'. Please pass in this | |
-- parameter as a hardcoded constant, in order to verify the content of 'str'. | |
-- The value of this parameter should be known before your program runs. | |
-- @return [table] The dictionary used for preset dictionary compression and | |
-- decompression. | |
-- @raise error if 'strlen' does not match the length of 'str', | |
-- or if 'adler32' does not match the Adler-32 checksum of 'str'. | |
function LibDeflate:CreateDictionary(str, strlen, adler32) | |
if type(str) ~= "string" then | |
error(("Usage: LibDeflate:CreateDictionary(str, strlen, adler32):" .. | |
" 'str' - string expected got '%s'."):format(type(str)), 2) | |
end | |
if type(strlen) ~= "number" then | |
error(("Usage: LibDeflate:CreateDictionary(str, strlen, adler32):" .. | |
" 'strlen' - number expected got '%s'."):format(type(strlen)), 2) | |
end | |
if type(adler32) ~= "number" then | |
error(("Usage: LibDeflate:CreateDictionary(str, strlen, adler32):" .. | |
" 'adler32' - number expected got '%s'."):format(type(adler32)), 2) | |
end | |
if strlen ~= #str then | |
error(("Usage: LibDeflate:CreateDictionary(str, strlen, adler32):" .. | |
" 'strlen' does not match the actual length of 'str'." .. | |
" 'strlen': %u, '#str': %u ." .. | |
" Please check if 'str' is modified unintentionally."):format( | |
strlen, #str)) | |
end | |
if strlen == 0 then | |
error(("Usage: LibDeflate:CreateDictionary(str, strlen, adler32):" .. | |
" 'str' - Empty string is not allowed."), 2) | |
end | |
if strlen > 32768 then | |
error(("Usage: LibDeflate:CreateDictionary(str, strlen, adler32):" .. | |
" 'str' - string longer than 32768 bytes is not allowed." .. | |
" Got %d bytes."):format(strlen), 2) | |
end | |
local actual_adler32 = self:Adler32(str) | |
if not IsEqualAdler32(adler32, actual_adler32) then | |
error(("Usage: LibDeflate:CreateDictionary(str, strlen, adler32):" .. | |
" 'adler32' does not match the actual adler32 of 'str'." .. | |
" 'adler32': %u, 'Adler32(str)': %u ." .. | |
" Please check if 'str' is modified unintentionally."):format( | |
adler32, actual_adler32)) | |
end | |
local dictionary = {} | |
dictionary.adler32 = adler32 | |
dictionary.hash_tables = {} | |
dictionary.string_table = {} | |
dictionary.strlen = strlen | |
local string_table = dictionary.string_table | |
local hash_tables = dictionary.hash_tables | |
string_table[1] = string_byte(str, 1, 1) | |
string_table[2] = string_byte(str, 2, 2) | |
if strlen >= 3 then | |
local i = 1 | |
local hash = string_table[1] * 256 + string_table[2] | |
while i <= strlen - 2 - 3 do | |
local x1, x2, x3, x4 = string_byte(str, i + 2, i + 5) | |
string_table[i + 2] = x1 | |
string_table[i + 3] = x2 | |
string_table[i + 4] = x3 | |
string_table[i + 5] = x4 | |
hash = (hash * 256 + x1) % 16777216 | |
local t = hash_tables[hash] | |
if not t then | |
t = {}; | |
hash_tables[hash] = t | |
end | |
t[#t + 1] = i - strlen | |
i = i + 1 | |
hash = (hash * 256 + x2) % 16777216 | |
t = hash_tables[hash] | |
if not t then | |
t = {}; | |
hash_tables[hash] = t | |
end | |
t[#t + 1] = i - strlen | |
i = i + 1 | |
hash = (hash * 256 + x3) % 16777216 | |
t = hash_tables[hash] | |
if not t then | |
t = {}; | |
hash_tables[hash] = t | |
end | |
t[#t + 1] = i - strlen | |
i = i + 1 | |
hash = (hash * 256 + x4) % 16777216 | |
t = hash_tables[hash] | |
if not t then | |
t = {}; | |
hash_tables[hash] = t | |
end | |
t[#t + 1] = i - strlen | |
i = i + 1 | |
end | |
while i <= strlen - 2 do | |
local x = string_byte(str, i + 2) | |
string_table[i + 2] = x | |
hash = (hash * 256 + x) % 16777216 | |
local t = hash_tables[hash] | |
if not t then | |
t = {}; | |
hash_tables[hash] = t | |
end | |
t[#t + 1] = i - strlen | |
i = i + 1 | |
end | |
end | |
return dictionary | |
end | |
-- Check if the dictionary is valid. | |
-- @param dictionary The preset dictionary for compression and decompression. | |
-- @return true if valid, false if not valid. | |
-- @return if not valid, the error message. | |
local function IsValidDictionary(dictionary) | |
if type(dictionary) ~= "table" then | |
return false, | |
("'dictionary' - table expected got '%s'."):format(type(dictionary)) | |
end | |
if type(dictionary.adler32) ~= "number" or type(dictionary.string_table) ~= | |
"table" or type(dictionary.strlen) ~= "number" or dictionary.strlen <= 0 or | |
dictionary.strlen > 32768 or dictionary.strlen ~= #dictionary.string_table or | |
type(dictionary.hash_tables) ~= "table" then | |
return false, | |
("'dictionary' - corrupted dictionary."):format(type(dictionary)) | |
end | |
return true, "" | |
end | |
--[[ | |
key of the configuration table is the compression level, | |
and its value stores the compression setting. | |
These numbers come from zlib source code. | |
Higher compression level usually means better compression. | |
(Because LibDeflate uses a simplified version of zlib algorithm, | |
there is no guarantee that higher compression level does not create | |
bigger file than lower level, but I can say it's 99% likely) | |
Be careful with the high compression level. This is a pure lua | |
implementation compressor/decompressor, which is significant slower than | |
a C/C++ equivalant compressor/decompressor. Very high compression level | |
costs significant more CPU time, and usually compression size won't be | |
significant smaller when you increase compression level by 1, when the | |
level is already very high. Benchmark yourself if you can afford it. | |
See also https://github.com/madler/zlib/blob/master/doc/algorithm.txt, | |
https://github.com/madler/zlib/blob/master/deflate.c for more information. | |
The meaning of each field: | |
@field 1 use_lazy_evaluation: | |
true/false. Whether the program uses lazy evaluation. | |
See what is "lazy evaluation" in the link above. | |
lazy_evaluation improves ratio, but relatively slow. | |
@field 2 good_prev_length: | |
Only effective if lazy is set, Only use 1/4 of max_chain, | |
if prev length of lazy match is above this. | |
@field 3 max_insert_length/max_lazy_match: | |
If not using lazy evaluation, | |
insert new strings in the hash table only if the match length is not | |
greater than this length. | |
If using lazy evaluation, only continue lazy evaluation, | |
if previous match length is strictly smaller than this value. | |
@field 4 nice_length: | |
Number. Don't continue to go down the hash chain, | |
if match length is above this. | |
@field 5 max_chain: | |
Number. The maximum number of hash chains we look. | |
--]] | |
local _compression_level_configs = { | |
[0] = {false, nil, 0, 0, 0}, -- level 0, no compression | |
[1] = {false, nil, 4, 8, 4}, -- level 1, similar to zlib level 1 | |
[2] = {false, nil, 5, 18, 8}, -- level 2, similar to zlib level 2 | |
[3] = {false, nil, 6, 32, 32}, -- level 3, similar to zlib level 3 | |
[4] = {true, 4, 4, 16, 16}, -- level 4, similar to zlib level 4 | |
[5] = {true, 8, 16, 32, 32}, -- level 5, similar to zlib level 5 | |
[6] = {true, 8, 16, 128, 128}, -- level 6, similar to zlib level 6 | |
[7] = {true, 8, 32, 128, 256}, -- (SLOW) level 7, similar to zlib level 7 | |
[8] = {true, 32, 128, 258, 1024}, -- (SLOW) level 8,similar to zlib level 8 | |
[9] = {true, 32, 258, 258, 4096} | |
-- (VERY SLOW) level 9, similar to zlib level 9 | |
} | |
-- Check if the compression/decompression arguments is valid | |
-- @param str The input string. | |
-- @param check_dictionary if true, check if dictionary is valid. | |
-- @param dictionary The preset dictionary for compression and decompression. | |
-- @param check_configs if true, check if config is valid. | |
-- @param configs The compression configuration table | |
-- @return true if valid, false if not valid. | |
-- @return if not valid, the error message. | |
local function IsValidArguments(str, check_dictionary, dictionary, | |
check_configs, configs) | |
if type(str) ~= "string" then | |
return false, ("'str' - string expected got '%s'."):format(type(str)) | |
end | |
if check_dictionary then | |
local dict_valid, dict_err = IsValidDictionary(dictionary) | |
if not dict_valid then return false, dict_err end | |
end | |
if check_configs then | |
local type_configs = type(configs) | |
if type_configs ~= "nil" and type_configs ~= "table" then | |
return false, ("'configs' - nil or table expected got '%s'."):format( | |
type(configs)) | |
end | |
if type_configs == "table" then | |
for k, v in pairs(configs) do | |
if k ~= "level" and k ~= "strategy" then | |
return false, | |
("'configs' - unsupported table key in the configs: '%s'."):format( | |
k) | |
elseif k == "level" and not _compression_level_configs[v] then | |
return false, | |
("'configs' - unsupported 'level': %s."):format(tostring(v)) | |
elseif k == "strategy" and v ~= "fixed" and v ~= "huffman_only" and v ~= | |
"dynamic" then | |
-- random_block_type is for testing purpose | |
return false, ("'configs' - unsupported 'strategy': '%s'."):format( | |
tostring(v)) | |
end | |
end | |
end | |
end | |
return true, "" | |
end | |
--[[ -------------------------------------------------------------------------- | |
Compress code | |
--]] -------------------------------------------------------------------------- | |
-- partial flush to save memory | |
local _FLUSH_MODE_MEMORY_CLEANUP = 0 | |
-- full flush with partial bytes | |
local _FLUSH_MODE_OUTPUT = 1 | |
-- write bytes to get to byte boundary | |
local _FLUSH_MODE_BYTE_BOUNDARY = 2 | |
-- no flush, just get num of bits written so far | |
local _FLUSH_MODE_NO_FLUSH = 3 | |
--[[ | |
Create an empty writer to easily write stuffs as the unit of bits. | |
Return values: | |
1. WriteBits(code, bitlen): | |
2. WriteString(str): | |
3. Flush(mode): | |
--]] | |
local function CreateWriter() | |
local buffer_size = 0 | |
local cache = 0 | |
local cache_bitlen = 0 | |
local total_bitlen = 0 | |
local buffer = {} | |
-- When buffer is big enough, flush into result_buffer to save memory. | |
local result_buffer = {} | |
-- Write bits with value "value" and bit length of "bitlen" into writer. | |
-- @param value: The value being written | |
-- @param bitlen: The bit length of "value" | |
-- @return nil | |
local function WriteBits(value, bitlen) | |
cache = cache + value * _pow2[cache_bitlen] | |
cache_bitlen = cache_bitlen + bitlen | |
total_bitlen = total_bitlen + bitlen | |
-- Only bulk to buffer every 4 bytes. This is quicker. | |
if cache_bitlen >= 32 then | |
buffer_size = buffer_size + 1 | |
buffer[buffer_size] = _byte_to_char[cache % 256] .. | |
_byte_to_char[((cache - cache % 256) / 256 % 256)] .. | |
_byte_to_char[((cache - cache % 65536) / 65536 % | |
256)] .. | |
_byte_to_char[((cache - cache % 16777216) / | |
16777216 % 256)] | |
local rshift_mask = _pow2[32 - cache_bitlen + bitlen] | |
cache = (value - value % rshift_mask) / rshift_mask | |
cache_bitlen = cache_bitlen - 32 | |
end | |
end | |
-- Write the entire string into the writer. | |
-- @param str The string being written | |
-- @return nil | |
local function WriteString(str) | |
for _ = 1, cache_bitlen, 8 do | |
buffer_size = buffer_size + 1 | |
buffer[buffer_size] = string_char(cache % 256) | |
cache = (cache - cache % 256) / 256 | |
end | |
cache_bitlen = 0 | |
buffer_size = buffer_size + 1 | |
buffer[buffer_size] = str | |
total_bitlen = total_bitlen + #str * 8 | |
end | |
-- Flush current stuffs in the writer and return it. | |
-- This operation will free most of the memory. | |
-- @param mode See the descrtion of the constant and the source code. | |
-- @return The total number of bits stored in the writer right now. | |
-- for byte boundary mode, it includes the padding bits. | |
-- for output mode, it does not include padding bits. | |
-- @return Return the outputs if mode is output. | |
local function FlushWriter(mode) | |
if mode == _FLUSH_MODE_NO_FLUSH then return total_bitlen end | |
if mode == _FLUSH_MODE_OUTPUT or mode == _FLUSH_MODE_BYTE_BOUNDARY then | |
-- Full flush, also output cache. | |
-- Need to pad some bits if cache_bitlen is not multiple of 8. | |
local padding_bitlen = (8 - cache_bitlen % 8) % 8 | |
if cache_bitlen > 0 then | |
-- padding with all 1 bits, mainly because "\000" is not | |
-- good to be tranmitted. I do this so "\000" is a little bit | |
-- less frequent. | |
cache = cache - _pow2[cache_bitlen] + | |
_pow2[cache_bitlen + padding_bitlen] | |
for _ = 1, cache_bitlen, 8 do | |
buffer_size = buffer_size + 1 | |
buffer[buffer_size] = _byte_to_char[cache % 256] | |
cache = (cache - cache % 256) / 256 | |
end | |
cache = 0 | |
cache_bitlen = 0 | |
end | |
if mode == _FLUSH_MODE_BYTE_BOUNDARY then | |
total_bitlen = total_bitlen + padding_bitlen | |
return total_bitlen | |
end | |
end | |
local flushed = table_concat(buffer) | |
buffer = {} | |
buffer_size = 0 | |
result_buffer[#result_buffer + 1] = flushed | |
if mode == _FLUSH_MODE_MEMORY_CLEANUP then | |
return total_bitlen | |
else | |
return total_bitlen, table_concat(result_buffer) | |
end | |
end | |
return WriteBits, WriteString, FlushWriter | |
end | |
-- Push an element into a max heap | |
-- @param heap A max heap whose max element is at index 1. | |
-- @param e The element to be pushed. Assume element "e" is a table | |
-- and comparison is done via its first entry e[1] | |
-- @param heap_size current number of elements in the heap. | |
-- NOTE: There may be some garbage stored in | |
-- heap[heap_size+1], heap[heap_size+2], etc.. | |
-- @return nil | |
local function MinHeapPush(heap, e, heap_size) | |
heap_size = heap_size + 1 | |
heap[heap_size] = e | |
local value = e[1] | |
local pos = heap_size | |
local parent_pos = (pos - pos % 2) / 2 | |
while (parent_pos >= 1 and heap[parent_pos][1] > value) do | |
local t = heap[parent_pos] | |
heap[parent_pos] = e | |
heap[pos] = t | |
pos = parent_pos | |
parent_pos = (parent_pos - parent_pos % 2) / 2 | |
end | |
end | |
-- Pop an element from a max heap | |
-- @param heap A max heap whose max element is at index 1. | |
-- @param heap_size current number of elements in the heap. | |
-- @return the poped element | |
-- Note: This function does not change table size of "heap" to save CPU time. | |
local function MinHeapPop(heap, heap_size) | |
local top = heap[1] | |
local e = heap[heap_size] | |
local value = e[1] | |
heap[1] = e | |
heap[heap_size] = top | |
heap_size = heap_size - 1 | |
local pos = 1 | |
local left_child_pos = pos * 2 | |
local right_child_pos = left_child_pos + 1 | |
while (left_child_pos <= heap_size) do | |
local left_child = heap[left_child_pos] | |
if (right_child_pos <= heap_size and heap[right_child_pos][1] < | |
left_child[1]) then | |
local right_child = heap[right_child_pos] | |
if right_child[1] < value then | |
heap[right_child_pos] = e | |
heap[pos] = right_child | |
pos = right_child_pos | |
left_child_pos = pos * 2 | |
right_child_pos = left_child_pos + 1 | |
else | |
break | |
end | |
else | |
if left_child[1] < value then | |
heap[left_child_pos] = e | |
heap[pos] = left_child | |
pos = left_child_pos | |
left_child_pos = pos * 2 | |
right_child_pos = left_child_pos + 1 | |
else | |
break | |
end | |
end | |
end | |
return top | |
end | |
-- Deflate defines a special huffman tree, which is unique once the bit length | |
-- of huffman code of all symbols are known. | |
-- @param bitlen_count Number of symbols with a specific bitlen | |
-- @param symbol_bitlen The bit length of a symbol | |
-- @param max_symbol The max symbol among all symbols, | |
-- which is (number of symbols - 1) | |
-- @param max_bitlen The max huffman bit length among all symbols. | |
-- @return The huffman code of all symbols. | |
local function GetHuffmanCodeFromBitlen(bitlen_counts, symbol_bitlens, | |
max_symbol, max_bitlen) | |
local huffman_code = 0 | |
local next_codes = {} | |
local symbol_huffman_codes = {} | |
for bitlen = 1, max_bitlen do | |
huffman_code = (huffman_code + (bitlen_counts[bitlen - 1] or 0)) * 2 | |
next_codes[bitlen] = huffman_code | |
end | |
for symbol = 0, max_symbol do | |
local bitlen = symbol_bitlens[symbol] | |
if bitlen then | |
huffman_code = next_codes[bitlen] | |
next_codes[bitlen] = huffman_code + 1 | |
-- Reverse the bits of huffman code, | |
-- because most signifant bits of huffman code | |
-- is stored first into the compressed data. | |
-- @see RFC1951 Page5 Section 3.1.1 | |
if bitlen <= 9 then -- Have cached reverse for small bitlen. | |
symbol_huffman_codes[symbol] = _reverse_bits_tbl[bitlen][huffman_code] | |
else | |
local reverse = 0 | |
for _ = 1, bitlen do | |
reverse = reverse - reverse % 2 + | |
(((reverse % 2 == 1) or (huffman_code % 2) == 1) and 1 or | |
0) | |
huffman_code = (huffman_code - huffman_code % 2) / 2 | |
reverse = reverse * 2 | |
end | |
symbol_huffman_codes[symbol] = (reverse - reverse % 2) / 2 | |
end | |
end | |
end | |
return symbol_huffman_codes | |
end | |
-- A helper function to sort heap elements | |
-- a[1], b[1] is the huffman frequency | |
-- a[2], b[2] is the symbol value. | |
local function SortByFirstThenSecond(a, b) | |
return a[1] < b[1] or (a[1] == b[1] and a[2] < b[2]) | |
end | |
-- Calculate the huffman bit length and huffman code. | |
-- @param symbol_count: A table whose table key is the symbol, and table value | |
-- is the symbol frenquency (nil means 0 frequency). | |
-- @param max_bitlen: See description of return value. | |
-- @param max_symbol: The maximum symbol | |
-- @return a table whose key is the symbol, and the value is the huffman bit | |
-- bit length. We guarantee that all bit length <= max_bitlen. | |
-- For 0<=symbol<=max_symbol, table value could be nil if the frequency | |
-- of the symbol is 0 or nil. | |
-- @return a table whose key is the symbol, and the value is the huffman code. | |
-- @return a number indicating the maximum symbol whose bitlen is not 0. | |
local function GetHuffmanBitlenAndCode(symbol_counts, max_bitlen, max_symbol) | |
local heap_size | |
local max_non_zero_bitlen_symbol = -1 | |
local leafs = {} | |
local heap = {} | |
local symbol_bitlens = {} | |
local symbol_codes = {} | |
local bitlen_counts = {} | |
--[[ | |
tree[1]: weight, temporarily used as parent and bitLengths | |
tree[2]: symbol | |
tree[3]: left child | |
tree[4]: right child | |
--]] | |
local number_unique_symbols = 0 | |
for symbol, count in pairs(symbol_counts) do | |
number_unique_symbols = number_unique_symbols + 1 | |
leafs[number_unique_symbols] = {count, symbol} | |
end | |
if (number_unique_symbols == 0) then | |
-- no code. | |
return {}, {}, -1 | |
elseif (number_unique_symbols == 1) then | |
-- Only one code. In this case, its huffman code | |
-- needs to be assigned as 0, and bit length is 1. | |
-- This is the only case that the return result | |
-- represents an imcomplete huffman tree. | |
local symbol = leafs[1][2] | |
symbol_bitlens[symbol] = 1 | |
symbol_codes[symbol] = 0 | |
return symbol_bitlens, symbol_codes, symbol | |
else | |
table_sort(leafs, SortByFirstThenSecond) | |
heap_size = number_unique_symbols | |
for i = 1, heap_size do heap[i] = leafs[i] end | |
while (heap_size > 1) do | |
-- Note: pop does not change table size of heap | |
local leftChild = MinHeapPop(heap, heap_size) | |
heap_size = heap_size - 1 | |
local rightChild = MinHeapPop(heap, heap_size) | |
heap_size = heap_size - 1 | |
local newNode = {leftChild[1] + rightChild[1], -1, leftChild, rightChild} | |
MinHeapPush(heap, newNode, heap_size) | |
heap_size = heap_size + 1 | |
end | |
-- Number of leafs whose bit length is greater than max_len. | |
local number_bitlen_overflow = 0 | |
-- Calculate bit length of all nodes | |
local fifo = {heap[1], 0, 0, 0} -- preallocate some spaces. | |
local fifo_size = 1 | |
local index = 1 | |
heap[1][1] = 0 | |
while (index <= fifo_size) do -- Breath first search | |
local e = fifo[index] | |
local bitlen = e[1] | |
local symbol = e[2] | |
local left_child = e[3] | |
local right_child = e[4] | |
if left_child then | |
fifo_size = fifo_size + 1 | |
fifo[fifo_size] = left_child | |
left_child[1] = bitlen + 1 | |
end | |
if right_child then | |
fifo_size = fifo_size + 1 | |
fifo[fifo_size] = right_child | |
right_child[1] = bitlen + 1 | |
end | |
index = index + 1 | |
if (bitlen > max_bitlen) then | |
number_bitlen_overflow = number_bitlen_overflow + 1 | |
bitlen = max_bitlen | |
end | |
if symbol >= 0 then | |
symbol_bitlens[symbol] = bitlen | |
max_non_zero_bitlen_symbol = (symbol > max_non_zero_bitlen_symbol) and | |
symbol or max_non_zero_bitlen_symbol | |
bitlen_counts[bitlen] = (bitlen_counts[bitlen] or 0) + 1 | |
end | |
end | |
-- Resolve bit length overflow | |
-- @see ZLib/trees.c:gen_bitlen(s, desc), for reference | |
if (number_bitlen_overflow > 0) then | |
repeat | |
local bitlen = max_bitlen - 1 | |
while ((bitlen_counts[bitlen] or 0) == 0) do bitlen = bitlen - 1 end | |
-- move one leaf down the tree | |
bitlen_counts[bitlen] = bitlen_counts[bitlen] - 1 | |
-- move one overflow item as its brother | |
bitlen_counts[bitlen + 1] = (bitlen_counts[bitlen + 1] or 0) + 2 | |
bitlen_counts[max_bitlen] = bitlen_counts[max_bitlen] - 1 | |
number_bitlen_overflow = number_bitlen_overflow - 2 | |
until (number_bitlen_overflow <= 0) | |
index = 1 | |
for bitlen = max_bitlen, 1, -1 do | |
local n = bitlen_counts[bitlen] or 0 | |
while (n > 0) do | |
local symbol = leafs[index][2] | |
symbol_bitlens[symbol] = bitlen | |
n = n - 1 | |
index = index + 1 | |
end | |
end | |
end | |
symbol_codes = GetHuffmanCodeFromBitlen(bitlen_counts, symbol_bitlens, | |
max_symbol, max_bitlen) | |
return symbol_bitlens, symbol_codes, max_non_zero_bitlen_symbol | |
end | |
end | |
-- Calculate the first huffman header in the dynamic huffman block | |
-- @see RFC1951 Page 12 | |
-- @param lcode_bitlen: The huffman bit length of literal/LZ77_length. | |
-- @param max_non_zero_bitlen_lcode: The maximum literal/LZ77_length symbol | |
-- whose huffman bit length is not zero. | |
-- @param dcode_bitlen: The huffman bit length of LZ77 distance. | |
-- @param max_non_zero_bitlen_dcode: The maximum LZ77 distance symbol | |
-- whose huffman bit length is not zero. | |
-- @return The run length encoded codes. | |
-- @return The extra bits. One entry for each rle code that needs extra bits. | |
-- (code == 16 or 17 or 18). | |
-- @return The count of appearance of each rle codes. | |
local function RunLengthEncodeHuffmanBitlen(lcode_bitlens, | |
max_non_zero_bitlen_lcode, | |
dcode_bitlens, | |
max_non_zero_bitlen_dcode) | |
local rle_code_tblsize = 0 | |
local rle_codes = {} | |
local rle_code_counts = {} | |
local rle_extra_bits_tblsize = 0 | |
local rle_extra_bits = {} | |
local prev = nil | |
local count = 0 | |
-- If there is no distance code, assume one distance code of bit length 0. | |
-- RFC1951: One distance code of zero bits means that | |
-- there are no distance codes used at all (the data is all literals). | |
max_non_zero_bitlen_dcode = (max_non_zero_bitlen_dcode < 0) and 0 or | |
max_non_zero_bitlen_dcode | |
local max_code = max_non_zero_bitlen_lcode + max_non_zero_bitlen_dcode + 1 | |
for code = 0, max_code + 1 do | |
local len = (code <= max_non_zero_bitlen_lcode) and | |
(lcode_bitlens[code] or 0) or ((code <= max_code) and | |
(dcode_bitlens[code - max_non_zero_bitlen_lcode - 1] or 0) or | |
nil) | |
if len == prev then | |
count = count + 1 | |
if len ~= 0 and count == 6 then | |
rle_code_tblsize = rle_code_tblsize + 1 | |
rle_codes[rle_code_tblsize] = 16 | |
rle_extra_bits_tblsize = rle_extra_bits_tblsize + 1 | |
rle_extra_bits[rle_extra_bits_tblsize] = 3 | |
rle_code_counts[16] = (rle_code_counts[16] or 0) + 1 | |
count = 0 | |
elseif len == 0 and count == 138 then | |
rle_code_tblsize = rle_code_tblsize + 1 | |
rle_codes[rle_code_tblsize] = 18 | |
rle_extra_bits_tblsize = rle_extra_bits_tblsize + 1 | |
rle_extra_bits[rle_extra_bits_tblsize] = 127 | |
rle_code_counts[18] = (rle_code_counts[18] or 0) + 1 | |
count = 0 | |
end | |
else | |
if count == 1 then | |
rle_code_tblsize = rle_code_tblsize + 1 | |
rle_codes[rle_code_tblsize] = prev | |
rle_code_counts[prev] = (rle_code_counts[prev] or 0) + 1 | |
elseif count == 2 then | |
rle_code_tblsize = rle_code_tblsize + 1 | |
rle_codes[rle_code_tblsize] = prev | |
rle_code_tblsize = rle_code_tblsize + 1 | |
rle_codes[rle_code_tblsize] = prev | |
rle_code_counts[prev] = (rle_code_counts[prev] or 0) + 2 | |
elseif count >= 3 then | |
rle_code_tblsize = rle_code_tblsize + 1 | |
local rleCode = (prev ~= 0) and 16 or (count <= 10 and 17 or 18) | |
rle_codes[rle_code_tblsize] = rleCode | |
rle_code_counts[rleCode] = (rle_code_counts[rleCode] or 0) + 1 | |
rle_extra_bits_tblsize = rle_extra_bits_tblsize + 1 | |
rle_extra_bits[rle_extra_bits_tblsize] = | |
(count <= 10) and (count - 3) or (count - 11) | |
end | |
prev = len | |
if len and len ~= 0 then | |
rle_code_tblsize = rle_code_tblsize + 1 | |
rle_codes[rle_code_tblsize] = len | |
rle_code_counts[len] = (rle_code_counts[len] or 0) + 1 | |
count = 0 | |
else | |
count = 1 | |
end | |
end | |
end | |
return rle_codes, rle_extra_bits, rle_code_counts | |
end | |
-- Load the string into a table, in order to speed up LZ77. | |
-- Loop unrolled 16 times to speed this function up. | |
-- @param str The string to be loaded. | |
-- @param t The load destination | |
-- @param start str[index] will be the first character to be loaded. | |
-- @param end str[index] will be the last character to be loaded | |
-- @param offset str[index] will be loaded into t[index-offset] | |
-- @return t | |
local function LoadStringToTable(str, t, start, stop, offset) | |
local i = start - offset | |
while i <= stop - 15 - offset do | |
t[i], t[i + 1], t[i + 2], t[i + 3], t[i + 4], t[i + 5], t[i + 6], t[i + 7], t[i + | |
8], t[i + 9], t[i + 10], t[i + 11], t[i + 12], t[i + 13], t[i + 14], t[i + | |
15] = string_byte(str, i + offset, i + 15 + offset) | |
i = i + 16 | |
end | |
while (i <= stop - offset) do | |
t[i] = string_byte(str, i + offset, i + offset) | |
i = i + 1 | |
end | |
return t | |
end | |
-- Do LZ77 process. This function uses the majority of the CPU time. | |
-- @see zlib/deflate.c:deflate_fast(), zlib/deflate.c:deflate_slow() | |
-- @see https://github.com/madler/zlib/blob/master/doc/algorithm.txt | |
-- This function uses the algorithms used above. You should read the | |
-- algorithm.txt above to understand what is the hash function and the | |
-- lazy evaluation. | |
-- | |
-- The special optimization used here is hash functions used here. | |
-- The hash function is just the multiplication of the three consective | |
-- characters. So if the hash matches, it guarantees 3 characters are matched. | |
-- This optimization can be implemented because Lua table is a hash table. | |
-- | |
-- @param level integer that describes compression level. | |
-- @param string_table table that stores the value of string to be compressed. | |
-- The index of this table starts from 1. | |
-- The caller needs to make sure all values needed by this function | |
-- are loaded. | |
-- Assume "str" is the origin input string into the compressor | |
-- str[block_start]..str[block_end+3] needs to be loaded into | |
-- string_table[block_start-offset]..string_table[block_end-offset] | |
-- If dictionary is presented, the last 258 bytes of the dictionary | |
-- needs to be loaded into sing_table[-257..0] | |
-- (See more in the description of offset.) | |
-- @param hash_tables. The table key is the hash value (0<=hash<=16777216=256^3) | |
-- The table value is an array0 that stores the indexes of the | |
-- input data string to be compressed, such that | |
-- hash == str[index]*str[index+1]*str[index+2] | |
-- Indexes are ordered in this array. | |
-- @param block_start The indexes of the input data string to be compressed. | |
-- that starts the LZ77 block. | |
-- @param block_end The indexes of the input data string to be compressed. | |
-- that stores the LZ77 block. | |
-- @param offset str[index] is stored in string_table[index-offset], | |
-- This offset is mainly an optimization to limit the index | |
-- of string_table, so lua can access this table quicker. | |
-- @param dictionary See LibDeflate:CreateDictionary | |
-- @return literal/LZ77_length deflate codes. | |
-- @return the extra bits of literal/LZ77_length deflate codes. | |
-- @return the count of each literal/LZ77 deflate code. | |
-- @return LZ77 distance deflate codes. | |
-- @return the extra bits of LZ77 distance deflate codes. | |
-- @return the count of each LZ77 distance deflate code. | |
local function GetBlockLZ77Result(level, string_table, hash_tables, block_start, | |
block_end, offset, dictionary) | |
local config = _compression_level_configs[level] | |
local config_use_lazy, config_good_prev_length, config_max_lazy_match, | |
config_nice_length, config_max_hash_chain = config[1], config[2], | |
config[3], config[4], | |
config[5] | |
local config_max_insert_length = (not config_use_lazy) and | |
config_max_lazy_match or 2147483646 | |
local config_good_hash_chain = | |
(config_max_hash_chain - config_max_hash_chain % 4 / 4) | |
local hash | |
local dict_hash_tables | |
local dict_string_table | |
local dict_string_len = 0 | |
if dictionary then | |
dict_hash_tables = dictionary.hash_tables | |
dict_string_table = dictionary.string_table | |
dict_string_len = dictionary.strlen | |
assert(block_start == 1) | |
if block_end >= block_start and dict_string_len >= 2 then | |
hash = dict_string_table[dict_string_len - 1] * 65536 + | |
dict_string_table[dict_string_len] * 256 + string_table[1] | |
local t = hash_tables[hash] | |
if not t then | |
t = {}; | |
hash_tables[hash] = t | |
end | |
t[#t + 1] = -1 | |
end | |
if block_end >= block_start + 1 and dict_string_len >= 1 then | |
hash = | |
dict_string_table[dict_string_len] * 65536 + string_table[1] * 256 + | |
string_table[2] | |
local t = hash_tables[hash] | |
if not t then | |
t = {}; | |
hash_tables[hash] = t | |
end | |
t[#t + 1] = 0 | |
end | |
end | |
local dict_string_len_plus3 = dict_string_len + 3 | |
hash = (string_table[block_start - offset] or 0) * 256 + | |
(string_table[block_start + 1 - offset] or 0) | |
local lcodes = {} | |
local lcode_tblsize = 0 | |
local lcodes_counts = {} | |
local dcodes = {} | |
local dcodes_tblsize = 0 | |
local dcodes_counts = {} | |
local lextra_bits = {} | |
local lextra_bits_tblsize = 0 | |
local dextra_bits = {} | |
local dextra_bits_tblsize = 0 | |
local match_available = false | |
local prev_len | |
local prev_dist | |
local cur_len = 0 | |
local cur_dist = 0 | |
local index = block_start | |
local index_end = block_end + (config_use_lazy and 1 or 0) | |
-- the zlib source code writes separate code for lazy evaluation and | |
-- not lazy evaluation, which is easier to understand. | |
-- I put them together, so it is a bit harder to understand. | |
-- because I think this is easier for me to maintain it. | |
while (index <= index_end) do | |
local string_table_index = index - offset | |
local offset_minus_three = offset - 3 | |
prev_len = cur_len | |
prev_dist = cur_dist | |
cur_len = 0 | |
hash = (hash * 256 + (string_table[string_table_index + 2] or 0)) % 16777216 | |
local chain_index | |
local cur_chain | |
local hash_chain = hash_tables[hash] | |
local chain_old_size | |
if not hash_chain then | |
chain_old_size = 0 | |
hash_chain = {} | |
hash_tables[hash] = hash_chain | |
if dict_hash_tables then | |
cur_chain = dict_hash_tables[hash] | |
chain_index = cur_chain and #cur_chain or 0 | |
else | |
chain_index = 0 | |
end | |
else | |
chain_old_size = #hash_chain | |
cur_chain = hash_chain | |
chain_index = chain_old_size | |
end | |
if index <= block_end then hash_chain[chain_old_size + 1] = index end | |
if (chain_index > 0 and index + 2 <= block_end and | |
(not config_use_lazy or prev_len < config_max_lazy_match)) then | |
local depth = | |
(config_use_lazy and prev_len >= config_good_prev_length) and | |
config_good_hash_chain or config_max_hash_chain | |
local max_len_minus_one = block_end - index | |
max_len_minus_one = (max_len_minus_one >= 257) and 257 or | |
max_len_minus_one | |
max_len_minus_one = max_len_minus_one + string_table_index | |
local string_table_index_plus_three = string_table_index + 3 | |
while chain_index >= 1 and depth > 0 do | |
local prev = cur_chain[chain_index] | |
if index - prev > 32768 then break end | |
if prev < index then | |
local sj = string_table_index_plus_three | |
if prev >= -257 then | |
local pj = prev - offset_minus_three | |
while (sj <= max_len_minus_one and string_table[pj] == | |
string_table[sj]) do | |
sj = sj + 1 | |
pj = pj + 1 | |
end | |
else | |
local pj = dict_string_len_plus3 + prev | |
while (sj <= max_len_minus_one and dict_string_table[pj] == | |
string_table[sj]) do | |
sj = sj + 1 | |
pj = pj + 1 | |
end | |
end | |
local j = sj - string_table_index | |
if j > cur_len then | |
cur_len = j | |
cur_dist = index - prev | |
end | |
if cur_len >= config_nice_length then break end | |
end | |
chain_index = chain_index - 1 | |
depth = depth - 1 | |
if chain_index == 0 and prev > 0 and dict_hash_tables then | |
cur_chain = dict_hash_tables[hash] | |
chain_index = cur_chain and #cur_chain or 0 | |
end | |
end | |
end | |
if not config_use_lazy then prev_len, prev_dist = cur_len, cur_dist end | |
if ((not config_use_lazy or match_available) and | |
(prev_len > 3 or (prev_len == 3 and prev_dist < 4096)) and cur_len <= | |
prev_len) then | |
local code = _length_to_deflate_code[prev_len] | |
local length_extra_bits_bitlen = _length_to_deflate_extra_bitlen[prev_len] | |
local dist_code, dist_extra_bits_bitlen, dist_extra_bits | |
if prev_dist <= 256 then -- have cached code for small distance. | |
dist_code = _dist256_to_deflate_code[prev_dist] | |
dist_extra_bits = _dist256_to_deflate_extra_bits[prev_dist] | |
dist_extra_bits_bitlen = _dist256_to_deflate_extra_bitlen[prev_dist] | |
else | |
dist_code = 16 | |
dist_extra_bits_bitlen = 7 | |
local a = 384 | |
local b = 512 | |
while true do | |
if prev_dist <= a then | |
dist_extra_bits = (prev_dist - (b / 2) - 1) % (b / 4) | |
break | |
elseif prev_dist <= b then | |
dist_extra_bits = (prev_dist - (b / 2) - 1) % (b / 4) | |
dist_code = dist_code + 1 | |
break | |
else | |
dist_code = dist_code + 2 | |
dist_extra_bits_bitlen = dist_extra_bits_bitlen + 1 | |
a = a * 2 | |
b = b * 2 | |
end | |
end | |
end | |
lcode_tblsize = lcode_tblsize + 1 | |
lcodes[lcode_tblsize] = code | |
lcodes_counts[code] = (lcodes_counts[code] or 0) + 1 | |
dcodes_tblsize = dcodes_tblsize + 1 | |
dcodes[dcodes_tblsize] = dist_code | |
dcodes_counts[dist_code] = (dcodes_counts[dist_code] or 0) + 1 | |
if length_extra_bits_bitlen > 0 then | |
local lenExtraBits = _length_to_deflate_extra_bits[prev_len] | |
lextra_bits_tblsize = lextra_bits_tblsize + 1 | |
lextra_bits[lextra_bits_tblsize] = lenExtraBits | |
end | |
if dist_extra_bits_bitlen > 0 then | |
dextra_bits_tblsize = dextra_bits_tblsize + 1 | |
dextra_bits[dextra_bits_tblsize] = dist_extra_bits | |
end | |
for i = index + 1, index + prev_len - (config_use_lazy and 2 or 1) do | |
hash = (hash * 256 + (string_table[i - offset + 2] or 0)) % 16777216 | |
if prev_len <= config_max_insert_length then | |
hash_chain = hash_tables[hash] | |
if not hash_chain then | |
hash_chain = {} | |
hash_tables[hash] = hash_chain | |
end | |
hash_chain[#hash_chain + 1] = i | |
end | |
end | |
index = index + prev_len - (config_use_lazy and 1 or 0) | |
match_available = false | |
elseif (not config_use_lazy) or match_available then | |
local code = string_table[config_use_lazy and (string_table_index - 1) or | |
string_table_index] | |
lcode_tblsize = lcode_tblsize + 1 | |
lcodes[lcode_tblsize] = code | |
lcodes_counts[code] = (lcodes_counts[code] or 0) + 1 | |
index = index + 1 | |
else | |
match_available = true | |
index = index + 1 | |
end | |
end | |
-- Write "end of block" symbol | |
lcode_tblsize = lcode_tblsize + 1 | |
lcodes[lcode_tblsize] = 256 | |
lcodes_counts[256] = (lcodes_counts[256] or 0) + 1 | |
return lcodes, lextra_bits, lcodes_counts, dcodes, dextra_bits, dcodes_counts | |
end | |
-- Get the header data of dynamic block. | |
-- @param lcodes_count The count of each literal/LZ77_length codes. | |
-- @param dcodes_count The count of each Lz77 distance codes. | |
-- @return a lots of stuffs. | |
-- @see RFC1951 Page 12 | |
local function GetBlockDynamicHuffmanHeader(lcodes_counts, dcodes_counts) | |
local lcodes_huffman_bitlens, lcodes_huffman_codes, max_non_zero_bitlen_lcode = | |
GetHuffmanBitlenAndCode(lcodes_counts, 15, 285) | |
local dcodes_huffman_bitlens, dcodes_huffman_codes, max_non_zero_bitlen_dcode = | |
GetHuffmanBitlenAndCode(dcodes_counts, 15, 29) | |
local rle_deflate_codes, rle_extra_bits, rle_codes_counts = | |
RunLengthEncodeHuffmanBitlen(lcodes_huffman_bitlens, | |
max_non_zero_bitlen_lcode, | |
dcodes_huffman_bitlens, | |
max_non_zero_bitlen_dcode) | |
local rle_codes_huffman_bitlens, rle_codes_huffman_codes = | |
GetHuffmanBitlenAndCode(rle_codes_counts, 7, 18) | |
local HCLEN = 0 | |
for i = 1, 19 do | |
local symbol = _rle_codes_huffman_bitlen_order[i] | |
local length = rle_codes_huffman_bitlens[symbol] or 0 | |
if length ~= 0 then HCLEN = i end | |
end | |
HCLEN = HCLEN - 4 | |
local HLIT = max_non_zero_bitlen_lcode + 1 - 257 | |
local HDIST = max_non_zero_bitlen_dcode + 1 - 1 | |
if HDIST < 0 then HDIST = 0 end | |
return HLIT, HDIST, HCLEN, rle_codes_huffman_bitlens, rle_codes_huffman_codes, | |
rle_deflate_codes, rle_extra_bits, lcodes_huffman_bitlens, | |
lcodes_huffman_codes, dcodes_huffman_bitlens, dcodes_huffman_codes | |
end | |
-- Get the size of dynamic block without writing any bits into the writer. | |
-- @param ... Read the source code of GetBlockDynamicHuffmanHeader() | |
-- @return the bit length of the dynamic block | |
local function GetDynamicHuffmanBlockSize(lcodes, dcodes, HCLEN, | |
rle_codes_huffman_bitlens, | |
rle_deflate_codes, | |
lcodes_huffman_bitlens, | |
dcodes_huffman_bitlens) | |
local block_bitlen = 17 -- 1+2+5+5+4 | |
block_bitlen = block_bitlen + (HCLEN + 4) * 3 | |
for i = 1, #rle_deflate_codes do | |
local code = rle_deflate_codes[i] | |
block_bitlen = block_bitlen + rle_codes_huffman_bitlens[code] | |
if code >= 16 then | |
block_bitlen = block_bitlen + | |
((code == 16) and 2 or (code == 17 and 3 or 7)) | |
end | |
end | |
local length_code_count = 0 | |
for i = 1, #lcodes do | |
local code = lcodes[i] | |
local huffman_bitlen = lcodes_huffman_bitlens[code] | |
block_bitlen = block_bitlen + huffman_bitlen | |
if code > 256 then -- Length code | |
length_code_count = length_code_count + 1 | |
if code > 264 and code < 285 then -- Length code with extra bits | |
local extra_bits_bitlen = _literal_deflate_code_to_extra_bitlen[code - | |
256] | |
block_bitlen = block_bitlen + extra_bits_bitlen | |
end | |
local dist_code = dcodes[length_code_count] | |
local dist_huffman_bitlen = dcodes_huffman_bitlens[dist_code] | |
block_bitlen = block_bitlen + dist_huffman_bitlen | |
if dist_code > 3 then -- dist code with extra bits | |
local dist_extra_bits_bitlen = (dist_code - dist_code % 2) / 2 - 1 | |
block_bitlen = block_bitlen + dist_extra_bits_bitlen | |
end | |
end | |
end | |
return block_bitlen | |
end | |
-- Write dynamic block. | |
-- @param ... Read the source code of GetBlockDynamicHuffmanHeader() | |
local function CompressDynamicHuffmanBlock(WriteBits, is_last_block, lcodes, | |
lextra_bits, dcodes, dextra_bits, | |
HLIT, HDIST, HCLEN, | |
rle_codes_huffman_bitlens, | |
rle_codes_huffman_codes, | |
rle_deflate_codes, rle_extra_bits, | |
lcodes_huffman_bitlens, | |
lcodes_huffman_codes, | |
dcodes_huffman_bitlens, | |
dcodes_huffman_codes) | |
WriteBits(is_last_block and 1 or 0, 1) -- Last block identifier | |
WriteBits(2, 2) -- Dynamic Huffman block identifier | |
WriteBits(HLIT, 5) | |
WriteBits(HDIST, 5) | |
WriteBits(HCLEN, 4) | |
for i = 1, HCLEN + 4 do | |
local symbol = _rle_codes_huffman_bitlen_order[i] | |
local length = rle_codes_huffman_bitlens[symbol] or 0 | |
WriteBits(length, 3) | |
end | |
local rleExtraBitsIndex = 1 | |
for i = 1, #rle_deflate_codes do | |
local code = rle_deflate_codes[i] | |
WriteBits(rle_codes_huffman_codes[code], rle_codes_huffman_bitlens[code]) | |
if code >= 16 then | |
local extraBits = rle_extra_bits[rleExtraBitsIndex] | |
WriteBits(extraBits, (code == 16) and 2 or (code == 17 and 3 or 7)) | |
rleExtraBitsIndex = rleExtraBitsIndex + 1 | |
end | |
end | |
local length_code_count = 0 | |
local length_code_with_extra_count = 0 | |
local dist_code_with_extra_count = 0 | |
for i = 1, #lcodes do | |
local deflate_codee = lcodes[i] | |
local huffman_code = lcodes_huffman_codes[deflate_codee] | |
local huffman_bitlen = lcodes_huffman_bitlens[deflate_codee] | |
WriteBits(huffman_code, huffman_bitlen) | |
if deflate_codee > 256 then -- Length code | |
length_code_count = length_code_count + 1 | |
if deflate_codee > 264 and deflate_codee < 285 then | |
-- Length code with extra bits | |
length_code_with_extra_count = length_code_with_extra_count + 1 | |
local extra_bits = lextra_bits[length_code_with_extra_count] | |
local extra_bits_bitlen = | |
_literal_deflate_code_to_extra_bitlen[deflate_codee - 256] | |
WriteBits(extra_bits, extra_bits_bitlen) | |
end | |
-- Write distance code | |
local dist_deflate_code = dcodes[length_code_count] | |
local dist_huffman_code = dcodes_huffman_codes[dist_deflate_code] | |
local dist_huffman_bitlen = dcodes_huffman_bitlens[dist_deflate_code] | |
WriteBits(dist_huffman_code, dist_huffman_bitlen) | |
if dist_deflate_code > 3 then -- dist code with extra bits | |
dist_code_with_extra_count = dist_code_with_extra_count + 1 | |
local dist_extra_bits = dextra_bits[dist_code_with_extra_count] | |
local dist_extra_bits_bitlen = (dist_deflate_code - dist_deflate_code % | |
2) / 2 - 1 | |
WriteBits(dist_extra_bits, dist_extra_bits_bitlen) | |
end | |
end | |
end | |
end | |
-- Get the size of fixed block without writing any bits into the writer. | |
-- @param lcodes literal/LZ77_length deflate codes | |
-- @param decodes LZ77 distance deflate codes | |
-- @return the bit length of the fixed block | |
local function GetFixedHuffmanBlockSize(lcodes, dcodes) | |
local block_bitlen = 3 | |
local length_code_count = 0 | |
for i = 1, #lcodes do | |
local code = lcodes[i] | |
local huffman_bitlen = _fix_block_literal_huffman_bitlen[code] | |
block_bitlen = block_bitlen + huffman_bitlen | |
if code > 256 then -- Length code | |
length_code_count = length_code_count + 1 | |
if code > 264 and code < 285 then -- Length code with extra bits | |
local extra_bits_bitlen = _literal_deflate_code_to_extra_bitlen[code - | |
256] | |
block_bitlen = block_bitlen + extra_bits_bitlen | |
end | |
local dist_code = dcodes[length_code_count] | |
block_bitlen = block_bitlen + 5 | |
if dist_code > 3 then -- dist code with extra bits | |
local dist_extra_bits_bitlen = (dist_code - dist_code % 2) / 2 - 1 | |
block_bitlen = block_bitlen + dist_extra_bits_bitlen | |
end | |
end | |
end | |
return block_bitlen | |
end | |
-- Write fixed block. | |
-- @param lcodes literal/LZ77_length deflate codes | |
-- @param decodes LZ77 distance deflate codes | |
local function CompressFixedHuffmanBlock(WriteBits, is_last_block, lcodes, | |
lextra_bits, dcodes, dextra_bits) | |
WriteBits(is_last_block and 1 or 0, 1) -- Last block identifier | |
WriteBits(1, 2) -- Fixed Huffman block identifier | |
local length_code_count = 0 | |
local length_code_with_extra_count = 0 | |
local dist_code_with_extra_count = 0 | |
for i = 1, #lcodes do | |
local deflate_code = lcodes[i] | |
local huffman_code = _fix_block_literal_huffman_code[deflate_code] | |
local huffman_bitlen = _fix_block_literal_huffman_bitlen[deflate_code] | |
WriteBits(huffman_code, huffman_bitlen) | |
if deflate_code > 256 then -- Length code | |
length_code_count = length_code_count + 1 | |
if deflate_code > 264 and deflate_code < 285 then | |
-- Length code with extra bits | |
length_code_with_extra_count = length_code_with_extra_count + 1 | |
local extra_bits = lextra_bits[length_code_with_extra_count] | |
local extra_bits_bitlen = | |
_literal_deflate_code_to_extra_bitlen[deflate_code - 256] | |
WriteBits(extra_bits, extra_bits_bitlen) | |
end | |
-- Write distance code | |
local dist_code = dcodes[length_code_count] | |
local dist_huffman_code = _fix_block_dist_huffman_code[dist_code] | |
WriteBits(dist_huffman_code, 5) | |
if dist_code > 3 then -- dist code with extra bits | |
dist_code_with_extra_count = dist_code_with_extra_count + 1 | |
local dist_extra_bits = dextra_bits[dist_code_with_extra_count] | |
local dist_extra_bits_bitlen = (dist_code - dist_code % 2) / 2 - 1 | |
WriteBits(dist_extra_bits, dist_extra_bits_bitlen) | |
end | |
end | |
end | |
end | |
-- Get the size of store block without writing any bits into the writer. | |
-- @param block_start The start index of the origin input string | |
-- @param block_end The end index of the origin input string | |
-- @param Total bit lens had been written into the compressed result before, | |
-- because store block needs to shift to byte boundary. | |
-- @return the bit length of the fixed block | |
local function GetStoreBlockSize(block_start, block_end, total_bitlen) | |
assert(block_end - block_start + 1 <= 65535) | |
local block_bitlen = 3 | |
total_bitlen = total_bitlen + 3 | |
local padding_bitlen = (8 - total_bitlen % 8) % 8 | |
block_bitlen = block_bitlen + padding_bitlen | |
block_bitlen = block_bitlen + 32 | |
block_bitlen = block_bitlen + (block_end - block_start + 1) * 8 | |
return block_bitlen | |
end | |
-- Write the store block. | |
-- @param ... lots of stuffs | |
-- @return nil | |
local function CompressStoreBlock(WriteBits, WriteString, is_last_block, str, | |
block_start, block_end, total_bitlen) | |
assert(block_end - block_start + 1 <= 65535) | |
WriteBits(is_last_block and 1 or 0, 1) -- Last block identifer. | |
WriteBits(0, 2) -- Store block identifier. | |
total_bitlen = total_bitlen + 3 | |
local padding_bitlen = (8 - total_bitlen % 8) % 8 | |
if padding_bitlen > 0 then | |
WriteBits(_pow2[padding_bitlen] - 1, padding_bitlen) | |
end | |
local size = block_end - block_start + 1 | |
WriteBits(size, 16) | |
-- Write size's one's complement | |
local comp = (255 - size % 256) + (255 - (size - size % 256) / 256) * 256 | |
WriteBits(comp, 16) | |
WriteString(str:sub(block_start, block_end)) | |
end | |
-- Do the deflate | |
-- Currently using a simple way to determine the block size | |
-- (This is why the compression ratio is little bit worse than zlib when | |
-- the input size is very large | |
-- The first block is 64KB, the following block is 32KB. | |
-- After each block, there is a memory cleanup operation. | |
-- This is not a fast operation, but it is needed to save memory usage, so | |
-- the memory usage does not grow unboundly. If the data size is less than | |
-- 64KB, then memory cleanup won't happen. | |
-- This function determines whether to use store/fixed/dynamic blocks by | |
-- calculating the block size of each block type and chooses the smallest one. | |
local function Deflate(configs, WriteBits, WriteString, FlushWriter, str, | |
dictionary) | |
local string_table = {} | |
local hash_tables = {} | |
local is_last_block = nil | |
local block_start | |
local block_end | |
local bitlen_written | |
local total_bitlen = FlushWriter(_FLUSH_MODE_NO_FLUSH) | |
local strlen = #str | |
local offset | |
local level | |
local strategy | |
if configs then | |
if configs.level then level = configs.level end | |
if configs.strategy then strategy = configs.strategy end | |
end | |
if not level then | |
if strlen < 2048 then | |
level = 7 | |
elseif strlen > 65536 then | |
level = 3 | |
else | |
level = 5 | |
end | |
end | |
while not is_last_block do | |
if not block_start then | |
block_start = 1 | |
block_end = 64 * 1024 - 1 | |
offset = 0 | |
else | |
block_start = block_end + 1 | |
block_end = block_end + 32 * 1024 | |
offset = block_start - 32 * 1024 - 1 | |
end | |
if block_end >= strlen then | |
block_end = strlen | |
is_last_block = true | |
else | |
is_last_block = false | |
end | |
local lcodes, lextra_bits, lcodes_counts, dcodes, dextra_bits, dcodes_counts | |
local HLIT, HDIST, HCLEN, rle_codes_huffman_bitlens, | |
rle_codes_huffman_codes, rle_deflate_codes, rle_extra_bits, | |
lcodes_huffman_bitlens, lcodes_huffman_codes, dcodes_huffman_bitlens, | |
dcodes_huffman_codes | |
local dynamic_block_bitlen | |
local fixed_block_bitlen | |
local store_block_bitlen | |
if level ~= 0 then | |
-- GetBlockLZ77 needs block_start to block_end+3 to be loaded. | |
LoadStringToTable(str, string_table, block_start, block_end + 3, offset) | |
if block_start == 1 and dictionary then | |
local dict_string_table = dictionary.string_table | |
local dict_strlen = dictionary.strlen | |
for i = 0, (-dict_strlen + 1) < -257 and -257 or (-dict_strlen + 1), -1 do | |
string_table[i] = dict_string_table[dict_strlen + i] | |
end | |
end | |
if strategy == "huffman_only" then | |
lcodes = {} | |
LoadStringToTable(str, lcodes, block_start, block_end, block_start - 1) | |
lextra_bits = {} | |
lcodes_counts = {} | |
lcodes[block_end - block_start + 2] = 256 -- end of block | |
for i = 1, block_end - block_start + 2 do | |
local code = lcodes[i] | |
lcodes_counts[code] = (lcodes_counts[code] or 0) + 1 | |
end | |
dcodes = {} | |
dextra_bits = {} | |
dcodes_counts = {} | |
else | |
lcodes, lextra_bits, lcodes_counts, dcodes, dextra_bits, dcodes_counts = | |
GetBlockLZ77Result(level, string_table, hash_tables, block_start, | |
block_end, offset, dictionary) | |
end | |
-- LuaFormatter off | |
HLIT, HDIST, HCLEN, rle_codes_huffman_bitlens, rle_codes_huffman_codes, rle_deflate_codes, | |
rle_extra_bits, lcodes_huffman_bitlens, lcodes_huffman_codes, dcodes_huffman_bitlens, dcodes_huffman_codes = | |
-- LuaFormatter on | |
GetBlockDynamicHuffmanHeader(lcodes_counts, dcodes_counts) | |
dynamic_block_bitlen = GetDynamicHuffmanBlockSize(lcodes, dcodes, HCLEN, | |
rle_codes_huffman_bitlens, | |
rle_deflate_codes, | |
lcodes_huffman_bitlens, | |
dcodes_huffman_bitlens) | |
fixed_block_bitlen = GetFixedHuffmanBlockSize(lcodes, dcodes) | |
end | |
store_block_bitlen = GetStoreBlockSize(block_start, block_end, total_bitlen) | |
local min_bitlen = store_block_bitlen | |
min_bitlen = (fixed_block_bitlen and fixed_block_bitlen < min_bitlen) and | |
fixed_block_bitlen or min_bitlen | |
min_bitlen = | |
(dynamic_block_bitlen and dynamic_block_bitlen < min_bitlen) and | |
dynamic_block_bitlen or min_bitlen | |
if level == 0 or | |
(strategy ~= "fixed" and strategy ~= "dynamic" and store_block_bitlen == | |
min_bitlen) then | |
CompressStoreBlock(WriteBits, WriteString, is_last_block, str, | |
block_start, block_end, total_bitlen) | |
total_bitlen = total_bitlen + store_block_bitlen | |
elseif strategy ~= "dynamic" and | |
(strategy == "fixed" or fixed_block_bitlen == min_bitlen) then | |
CompressFixedHuffmanBlock(WriteBits, is_last_block, lcodes, lextra_bits, | |
dcodes, dextra_bits) | |
total_bitlen = total_bitlen + fixed_block_bitlen | |
elseif strategy == "dynamic" or dynamic_block_bitlen == min_bitlen then | |
CompressDynamicHuffmanBlock(WriteBits, is_last_block, lcodes, lextra_bits, | |
dcodes, dextra_bits, HLIT, HDIST, HCLEN, | |
rle_codes_huffman_bitlens, | |
rle_codes_huffman_codes, rle_deflate_codes, | |
rle_extra_bits, lcodes_huffman_bitlens, | |
lcodes_huffman_codes, dcodes_huffman_bitlens, | |
dcodes_huffman_codes) | |
total_bitlen = total_bitlen + dynamic_block_bitlen | |
end | |
if is_last_block then | |
bitlen_written = FlushWriter(_FLUSH_MODE_NO_FLUSH) | |
else | |
bitlen_written = FlushWriter(_FLUSH_MODE_MEMORY_CLEANUP) | |
end | |
assert(bitlen_written == total_bitlen) | |
-- Memory clean up, so memory consumption does not always grow linearly | |
-- , even if input string is > 64K. | |
-- Not a very efficient operation, but this operation won't happen | |
-- when the input data size is less than 64K. | |
if not is_last_block then | |
local j | |
if dictionary and block_start == 1 then | |
j = 0 | |
while (string_table[j]) do | |
string_table[j] = nil | |
j = j - 1 | |
end | |
end | |
dictionary = nil | |
j = 1 | |
for i = block_end - 32767, block_end do | |
string_table[j] = string_table[i - offset] | |
j = j + 1 | |
end | |
for k, t in pairs(hash_tables) do | |
local tSize = #t | |
if tSize > 0 and block_end + 1 - t[1] > 32768 then | |
if tSize == 1 then | |
hash_tables[k] = nil | |
else | |
local new = {} | |
local newSize = 0 | |
for i = 2, tSize do | |
j = t[i] | |
if block_end + 1 - j <= 32768 then | |
newSize = newSize + 1 | |
new[newSize] = j | |
end | |
end | |
hash_tables[k] = new | |
end | |
end | |
end | |
end | |
end | |
end | |
--- The description to compression configuration table. <br> | |
-- Any field can be nil to use its default. <br> | |
-- Table with keys other than those below is an invalid table. | |
-- @class table | |
-- @name compression_configs | |
-- @field level The compression level ranged from 0 to 9. 0 is no compression. | |
-- 9 is the slowest but best compression. Use nil for default level. | |
-- @field strategy The compression strategy. "fixed" to only use fixed deflate | |
-- compression block. "dynamic" to only use dynamic block. "huffman_only" to | |
-- do no LZ77 compression. Only do huffman compression. | |
-- @see LibDeflate:CompressDeflate(str, configs) | |
-- @see LibDeflate:CompressDeflateWithDict(str, dictionary, configs) | |
local function CompressDeflateInternal(str, dictionary, configs) | |
local WriteBits, WriteString, FlushWriter = CreateWriter() | |
Deflate(configs, WriteBits, WriteString, FlushWriter, str, dictionary) | |
local total_bitlen, result = FlushWriter(_FLUSH_MODE_OUTPUT) | |
local padding_bitlen = (8 - total_bitlen % 8) % 8 | |
return result, padding_bitlen | |
end | |
-- @see LibDeflate:CompressZlib | |
-- @see LibDeflate:CompressZlibWithDict | |
local function CompressZlibInternal(str, dictionary, configs) | |
local WriteBits, WriteString, FlushWriter = CreateWriter() | |
local CM = 8 -- Compression method | |
local CINFO = 7 -- Window Size = 32K | |
local CMF = CINFO * 16 + CM | |
WriteBits(CMF, 8) | |
local FDIST = dictionary and 1 or 0 | |
local FLEVEL = 2 -- Default compression | |
local FLG = FLEVEL * 64 + FDIST * 32 | |
local FCHECK = (31 - (CMF * 256 + FLG) % 31) | |
-- The FCHECK value must be such that CMF and FLG, | |
-- when viewed as a 16-bit unsigned integer stored | |
-- in MSB order (CMF*256 + FLG), is a multiple of 31. | |
FLG = FLG + FCHECK | |
WriteBits(FLG, 8) | |
if FDIST == 1 then | |
local adler32 = dictionary.adler32 | |
local byte0 = adler32 % 256 | |
adler32 = (adler32 - byte0) / 256 | |
local byte1 = adler32 % 256 | |
adler32 = (adler32 - byte1) / 256 | |
local byte2 = adler32 % 256 | |
adler32 = (adler32 - byte2) / 256 | |
local byte3 = adler32 % 256 | |
WriteBits(byte3, 8) | |
WriteBits(byte2, 8) | |
WriteBits(byte1, 8) | |
WriteBits(byte0, 8) | |
end | |
Deflate(configs, WriteBits, WriteString, FlushWriter, str, dictionary) | |
FlushWriter(_FLUSH_MODE_BYTE_BOUNDARY) | |
local adler32 = LibDeflate:Adler32(str) | |
-- Most significant byte first | |
local byte3 = adler32 % 256 | |
adler32 = (adler32 - byte3) / 256 | |
local byte2 = adler32 % 256 | |
adler32 = (adler32 - byte2) / 256 | |
local byte1 = adler32 % 256 | |
adler32 = (adler32 - byte1) / 256 | |
local byte0 = adler32 % 256 | |
WriteBits(byte0, 8) | |
WriteBits(byte1, 8) | |
WriteBits(byte2, 8) | |
WriteBits(byte3, 8) | |
local total_bitlen, result = FlushWriter(_FLUSH_MODE_OUTPUT) | |
local padding_bitlen = (8 - total_bitlen % 8) % 8 | |
return result, padding_bitlen | |
end | |
--- Compress using the raw deflate format. | |
-- @param str [string] The data to be compressed. | |
-- @param configs [table/nil] The configuration table to control the compression | |
-- . If nil, use the default configuration. | |
-- @return [string] The compressed data. | |
-- @return [integer] The number of bits padded at the end of output. | |
-- 0 <= bits < 8 <br> | |
-- This means the most significant "bits" of the last byte of the returned | |
-- compressed data are padding bits and they don't affect decompression. | |
-- You don't need to use this value unless you want to do some postprocessing | |
-- to the compressed data. | |
-- @see compression_configs | |
-- @see LibDeflate:DecompressDeflate | |
function LibDeflate:CompressDeflate(str, configs) | |
local arg_valid, arg_err = IsValidArguments(str, false, nil, true, configs) | |
if not arg_valid then | |
error(("Usage: LibDeflate:CompressDeflate(str, configs): " .. arg_err), 2) | |
end | |
return CompressDeflateInternal(str, nil, configs) | |
end | |
--- Compress using the raw deflate format with a preset dictionary. | |
-- @param str [string] The data to be compressed. | |
-- @param dictionary [table] The preset dictionary produced by | |
-- LibDeflate:CreateDictionary | |
-- @param configs [table/nil] The configuration table to control the compression | |
-- . If nil, use the default configuration. | |
-- @return [string] The compressed data. | |
-- @return [integer] The number of bits padded at the end of output. | |
-- 0 <= bits < 8 <br> | |
-- This means the most significant "bits" of the last byte of the returned | |
-- compressed data are padding bits and they don't affect decompression. | |
-- You don't need to use this value unless you want to do some postprocessing | |
-- to the compressed data. | |
-- @see compression_configs | |
-- @see LibDeflate:CreateDictionary | |
-- @see LibDeflate:DecompressDeflateWithDict | |
function LibDeflate:CompressDeflateWithDict(str, dictionary, configs) | |
local arg_valid, arg_err = IsValidArguments(str, true, dictionary, true, | |
configs) | |
if not arg_valid then | |
error(("Usage: LibDeflate:CompressDeflateWithDict" .. | |
"(str, dictionary, configs): " .. arg_err), 2) | |
end | |
return CompressDeflateInternal(str, dictionary, configs) | |
end | |
--- Compress using the zlib format. | |
-- @param str [string] the data to be compressed. | |
-- @param configs [table/nil] The configuration table to control the compression | |
-- . If nil, use the default configuration. | |
-- @return [string] The compressed data. | |
-- @return [integer] The number of bits padded at the end of output. | |
-- Should always be 0. | |
-- Zlib formatted compressed data never has padding bits at the end. | |
-- @see compression_configs | |
-- @see LibDeflate:DecompressZlib | |
function LibDeflate:CompressZlib(str, configs) | |
local arg_valid, arg_err = IsValidArguments(str, false, nil, true, configs) | |
if not arg_valid then | |
error(("Usage: LibDeflate:CompressZlib(str, configs): " .. arg_err), 2) | |
end | |
return CompressZlibInternal(str, nil, configs) | |
end | |
--- Compress using the zlib format with a preset dictionary. | |
-- @param str [string] the data to be compressed. | |
-- @param dictionary [table] A preset dictionary produced | |
-- by LibDeflate:CreateDictionary() | |
-- @param configs [table/nil] The configuration table to control the compression | |
-- . If nil, use the default configuration. | |
-- @return [string] The compressed data. | |
-- @return [integer] The number of bits padded at the end of output. | |
-- Should always be 0. | |
-- Zlib formatted compressed data never has padding bits at the end. | |
-- @see compression_configs | |
-- @see LibDeflate:CreateDictionary | |
-- @see LibDeflate:DecompressZlibWithDict | |
function LibDeflate:CompressZlibWithDict(str, dictionary, configs) | |
local arg_valid, arg_err = IsValidArguments(str, true, dictionary, true, | |
configs) | |
if not arg_valid then | |
error(("Usage: LibDeflate:CompressZlibWithDict" .. | |
"(str, dictionary, configs): " .. arg_err), 2) | |
end | |
return CompressZlibInternal(str, dictionary, configs) | |
end | |
--[[ -------------------------------------------------------------------------- | |
Decompress code | |
--]] -------------------------------------------------------------------------- | |
--[[ | |
Create a reader to easily reader stuffs as the unit of bits. | |
Return values: | |
1. ReadBits(bitlen) | |
2. ReadBytes(bytelen, buffer, buffer_size) | |
3. Decode(huffman_bitlen_count, huffman_symbol, min_bitlen) | |
4. ReaderBitlenLeft() | |
5. SkipToByteBoundary() | |
--]] | |
local function CreateReader(input_string) | |
local input = input_string | |
local input_strlen = #input_string | |
local input_next_byte_pos = 1 | |
local cache_bitlen = 0 | |
local cache = 0 | |
-- Read some bits. | |
-- To improve speed, this function does not | |
-- check if the input has been exhausted. | |
-- Use ReaderBitlenLeft() < 0 to check it. | |
-- @param bitlen the number of bits to read | |
-- @return the data is read. | |
local function ReadBits(bitlen) | |
local rshift_mask = _pow2[bitlen] | |
local code | |
if bitlen <= cache_bitlen then | |
code = cache % rshift_mask | |
cache = (cache - code) / rshift_mask | |
cache_bitlen = cache_bitlen - bitlen | |
else -- Whether input has been exhausted is not checked. | |
local lshift_mask = _pow2[cache_bitlen] | |
local byte1, byte2, byte3, byte4 = | |
string_byte(input, input_next_byte_pos, input_next_byte_pos + 3) | |
-- This requires lua number to be at least double () | |
cache = cache + | |
((byte1 or 0) + (byte2 or 0) * 256 + (byte3 or 0) * 65536 + | |
(byte4 or 0) * 16777216) * lshift_mask | |
input_next_byte_pos = input_next_byte_pos + 4 | |
cache_bitlen = cache_bitlen + 32 - bitlen | |
code = cache % rshift_mask | |
cache = (cache - code) / rshift_mask | |
end | |
return code | |
end | |
-- Read some bytes from the reader. | |
-- Assume reader is on the byte boundary. | |
-- @param bytelen The number of bytes to be read. | |
-- @param buffer The byte read will be stored into this buffer. | |
-- @param buffer_size The buffer will be modified starting from | |
-- buffer[buffer_size+1], ending at buffer[buffer_size+bytelen-1] | |
-- @return the new buffer_size | |
local function ReadBytes(bytelen, buffer, buffer_size) | |
assert(cache_bitlen % 8 == 0) | |
local byte_from_cache = | |
(cache_bitlen / 8 < bytelen) and (cache_bitlen / 8) or bytelen | |
for _ = 1, byte_from_cache do | |
local byte = cache % 256 | |
buffer_size = buffer_size + 1 | |
buffer[buffer_size] = string_char(byte) | |
cache = (cache - byte) / 256 | |
end | |
cache_bitlen = cache_bitlen - byte_from_cache * 8 | |
bytelen = bytelen - byte_from_cache | |
if (input_strlen - input_next_byte_pos - bytelen + 1) * 8 + cache_bitlen < 0 then | |
return -1 -- out of input | |
end | |
for i = input_next_byte_pos, input_next_byte_pos + bytelen - 1 do | |
buffer_size = buffer_size + 1 | |
buffer[buffer_size] = string_sub(input, i, i) | |
end | |
input_next_byte_pos = input_next_byte_pos + bytelen | |
return buffer_size | |
end | |
-- Decode huffman code | |
-- To improve speed, this function does not check | |
-- if the input has been exhausted. | |
-- Use ReaderBitlenLeft() < 0 to check it. | |
-- Credits for Mark Adler. This code is from puff:Decode() | |
-- @see puff:Decode(...) | |
-- @param huffman_bitlen_count | |
-- @param huffman_symbol | |
-- @param min_bitlen The minimum huffman bit length of all symbols | |
-- @return The decoded deflate code. | |
-- Negative value is returned if decoding fails. | |
local function Decode(huffman_bitlen_counts, huffman_symbols, min_bitlen) | |
local code = 0 | |
local first = 0 | |
local index = 0 | |
local count | |
if min_bitlen > 0 then | |
if cache_bitlen < 15 and input then | |
local lshift_mask = _pow2[cache_bitlen] | |
local byte1, byte2, byte3, byte4 = | |
string_byte(input, input_next_byte_pos, input_next_byte_pos + 3) | |
-- This requires lua number to be at least double () | |
cache = cache + | |
((byte1 or 0) + (byte2 or 0) * 256 + (byte3 or 0) * 65536 + | |
(byte4 or 0) * 16777216) * lshift_mask | |
input_next_byte_pos = input_next_byte_pos + 4 | |
cache_bitlen = cache_bitlen + 32 | |
end | |
local rshift_mask = _pow2[min_bitlen] | |
cache_bitlen = cache_bitlen - min_bitlen | |
code = cache % rshift_mask | |
cache = (cache - code) / rshift_mask | |
-- Reverse the bits | |
code = _reverse_bits_tbl[min_bitlen][code] | |
count = huffman_bitlen_counts[min_bitlen] | |
if code < count then return huffman_symbols[code] end | |
index = count | |
first = count * 2 | |
code = code * 2 | |
end | |
for bitlen = min_bitlen + 1, 15 do | |
local bit | |
bit = cache % 2 | |
cache = (cache - bit) / 2 | |
cache_bitlen = cache_bitlen - 1 | |
code = (bit == 1) and (code + 1 - code % 2) or code | |
count = huffman_bitlen_counts[bitlen] or 0 | |
local diff = code - first | |
if diff < count then return huffman_symbols[index + diff] end | |
index = index + count | |
first = first + count | |
first = first * 2 | |
code = code * 2 | |
end | |
-- invalid literal/length or distance code | |
-- in fixed or dynamic block (run out of code) | |
return -10 | |
end | |
local function ReaderBitlenLeft() | |
return (input_strlen - input_next_byte_pos + 1) * 8 + cache_bitlen | |
end | |
local function SkipToByteBoundary() | |
local skipped_bitlen = cache_bitlen % 8 | |
local rshift_mask = _pow2[skipped_bitlen] | |
cache_bitlen = cache_bitlen - skipped_bitlen | |
cache = (cache - cache % rshift_mask) / rshift_mask | |
end | |
return ReadBits, ReadBytes, Decode, ReaderBitlenLeft, SkipToByteBoundary | |
end | |
-- Create a deflate state, so I can pass in less arguments to functions. | |
-- @param str the whole string to be decompressed. | |
-- @param dictionary The preset dictionary. nil if not provided. | |
-- This dictionary should be produced by LibDeflate:CreateDictionary(str) | |
-- @return The decomrpess state. | |
local function CreateDecompressState(str, dictionary) | |
local ReadBits, ReadBytes, Decode, ReaderBitlenLeft, SkipToByteBoundary = | |
CreateReader(str) | |
local state = { | |
ReadBits = ReadBits, | |
ReadBytes = ReadBytes, | |
Decode = Decode, | |
ReaderBitlenLeft = ReaderBitlenLeft, | |
SkipToByteBoundary = SkipToByteBoundary, | |
buffer_size = 0, | |
buffer = {}, | |
result_buffer = {}, | |
dictionary = dictionary | |
} | |
return state | |
end | |
-- Get the stuffs needed to decode huffman codes | |
-- @see puff.c:construct(...) | |
-- @param huffman_bitlen The huffman bit length of the huffman codes. | |
-- @param max_symbol The maximum symbol | |
-- @param max_bitlen The min huffman bit length of all codes | |
-- @return zero or positive for success, negative for failure. | |
-- @return The count of each huffman bit length. | |
-- @return A table to convert huffman codes to deflate codes. | |
-- @return The minimum huffman bit length. | |
local function GetHuffmanForDecode(huffman_bitlens, max_symbol, max_bitlen) | |
local huffman_bitlen_counts = {} | |
local min_bitlen = max_bitlen | |
for symbol = 0, max_symbol do | |
local bitlen = huffman_bitlens[symbol] or 0 | |
min_bitlen = (bitlen > 0 and bitlen < min_bitlen) and bitlen or min_bitlen | |
huffman_bitlen_counts[bitlen] = (huffman_bitlen_counts[bitlen] or 0) + 1 | |
end | |
if huffman_bitlen_counts[0] == max_symbol + 1 then -- No Codes | |
return 0, huffman_bitlen_counts, {}, 0 -- Complete, but decode will fail | |
end | |
local left = 1 | |
for len = 1, max_bitlen do | |
left = left * 2 | |
left = left - (huffman_bitlen_counts[len] or 0) | |
if left < 0 then | |
return left -- Over-subscribed, return negative | |
end | |
end | |
-- Generate offsets info symbol table for each length for sorting | |
local offsets = {} | |
offsets[1] = 0 | |
for len = 1, max_bitlen - 1 do | |
offsets[len + 1] = offsets[len] + (huffman_bitlen_counts[len] or 0) | |
end | |
local huffman_symbols = {} | |
for symbol = 0, max_symbol do | |
local bitlen = huffman_bitlens[symbol] or 0 | |
if bitlen ~= 0 then | |
local offset = offsets[bitlen] | |
huffman_symbols[offset] = symbol | |
offsets[bitlen] = offsets[bitlen] + 1 | |
end | |
end | |
-- Return zero for complete set, positive for incomplete set. | |
return left, huffman_bitlen_counts, huffman_symbols, min_bitlen | |
end | |
-- Decode a fixed or dynamic huffman blocks, excluding last block identifier | |
-- and block type identifer. | |
-- @see puff.c:codes() | |
-- @param state decompression state that will be modified by this function. | |
-- @see CreateDecompressState | |
-- @param ... Read the source code | |
-- @return 0 on success, other value on failure. | |
local function DecodeUntilEndOfBlock(state, lcodes_huffman_bitlens, | |
lcodes_huffman_symbols, | |
lcodes_huffman_min_bitlen, | |
dcodes_huffman_bitlens, | |
dcodes_huffman_symbols, | |
dcodes_huffman_min_bitlen) | |
local buffer, buffer_size, ReadBits, Decode, ReaderBitlenLeft, result_buffer = | |
state.buffer, state.buffer_size, state.ReadBits, state.Decode, | |
state.ReaderBitlenLeft, state.result_buffer | |
local dictionary = state.dictionary | |
local dict_string_table | |
local dict_strlen | |
local buffer_end = 1 | |
if dictionary and not buffer[0] then | |
-- If there is a dictionary, copy the last 258 bytes into | |
-- the string_table to make the copy in the main loop quicker. | |
-- This is done only once per decompression. | |
dict_string_table = dictionary.string_table | |
dict_strlen = dictionary.strlen | |
buffer_end = -dict_strlen + 1 | |
for i = 0, (-dict_strlen + 1) < -257 and -257 or (-dict_strlen + 1), -1 do | |
buffer[i] = _byte_to_char[dict_string_table[dict_strlen + i]] | |
end | |
end | |
repeat | |
local symbol = Decode(lcodes_huffman_bitlens, lcodes_huffman_symbols, | |
lcodes_huffman_min_bitlen) | |
if symbol < 0 or symbol > 285 then | |
-- invalid literal/length or distance code in fixed or dynamic block | |
return -10 | |
elseif symbol < 256 then -- Literal | |
buffer_size = buffer_size + 1 | |
buffer[buffer_size] = _byte_to_char[symbol] | |
elseif symbol > 256 then -- Length code | |
symbol = symbol - 256 | |
local bitlen = _literal_deflate_code_to_base_len[symbol] | |
bitlen = (symbol >= 8) and | |
(bitlen + | |
ReadBits(_literal_deflate_code_to_extra_bitlen[symbol])) or | |
bitlen | |
symbol = Decode(dcodes_huffman_bitlens, dcodes_huffman_symbols, | |
dcodes_huffman_min_bitlen) | |
if symbol < 0 or symbol > 29 then | |
-- invalid literal/length or distance code in fixed or dynamic block | |
return -10 | |
end | |
local dist = _dist_deflate_code_to_base_dist[symbol] | |
dist = (dist > 4) and | |
(dist + ReadBits(_dist_deflate_code_to_extra_bitlen[symbol])) or | |
dist | |
local char_buffer_index = buffer_size - dist + 1 | |
if char_buffer_index < buffer_end then | |
-- distance is too far back in fixed or dynamic block | |
return -11 | |
end | |
if char_buffer_index >= -257 then | |
for _ = 1, bitlen do | |
buffer_size = buffer_size + 1 | |
buffer[buffer_size] = buffer[char_buffer_index] | |
char_buffer_index = char_buffer_index + 1 | |
end | |
else | |
char_buffer_index = dict_strlen + char_buffer_index | |
for _ = 1, bitlen do | |
buffer_size = buffer_size + 1 | |
buffer[buffer_size] = | |
_byte_to_char[dict_string_table[char_buffer_index]] | |
char_buffer_index = char_buffer_index + 1 | |
end | |
end | |
end | |
if ReaderBitlenLeft() < 0 then | |
return 2 -- available inflate data did not terminate | |
end | |
if buffer_size >= 65536 then | |
result_buffer[#result_buffer + 1] = table_concat(buffer, "", 1, 32768) | |
for i = 32769, buffer_size do buffer[i - 32768] = buffer[i] end | |
buffer_size = buffer_size - 32768 | |
buffer[buffer_size + 1] = nil | |
-- NOTE: buffer[32769..end] and buffer[-257..0] are not cleared. | |
-- This is why "buffer_size" variable is needed. | |
end | |
until symbol == 256 | |
state.buffer_size = buffer_size | |
return 0 | |
end | |
-- Decompress a store block | |
-- @param state decompression state that will be modified by this function. | |
-- @return 0 if succeeds, other value if fails. | |
local function DecompressStoreBlock(state) | |
local buffer, buffer_size, ReadBits, ReadBytes, ReaderBitlenLeft, | |
SkipToByteBoundary, result_buffer = state.buffer, state.buffer_size, | |
state.ReadBits, state.ReadBytes, | |
state.ReaderBitlenLeft, | |
state.SkipToByteBoundary, | |
state.result_buffer | |
SkipToByteBoundary() | |
local bytelen = ReadBits(16) | |
if ReaderBitlenLeft() < 0 then | |
return 2 -- available inflate data did not terminate | |
end | |
local bytelenComp = ReadBits(16) | |
if ReaderBitlenLeft() < 0 then | |
return 2 -- available inflate data did not terminate | |
end | |
if bytelen % 256 + bytelenComp % 256 ~= 255 then | |
return -2 -- Not one's complement | |
end | |
if (bytelen - bytelen % 256) / 256 + (bytelenComp - bytelenComp % 256) / 256 ~= | |
255 then | |
return -2 -- Not one's complement | |
end | |
-- Note that ReadBytes will skip to the next byte boundary first. | |
buffer_size = ReadBytes(bytelen, buffer, buffer_size) | |
if buffer_size < 0 then | |
return 2 -- available inflate data did not terminate | |
end | |
-- memory clean up when there are enough bytes in the buffer. | |
if buffer_size >= 65536 then | |
result_buffer[#result_buffer + 1] = table_concat(buffer, "", 1, 32768) | |
for i = 32769, buffer_size do buffer[i - 32768] = buffer[i] end | |
buffer_size = buffer_size - 32768 | |
buffer[buffer_size + 1] = nil | |
end | |
state.buffer_size = buffer_size | |
return 0 | |
end | |
-- Decompress a fixed block | |
-- @param state decompression state that will be modified by this function. | |
-- @return 0 if succeeds other value if fails. | |
local function DecompressFixBlock(state) | |
return DecodeUntilEndOfBlock(state, _fix_block_literal_huffman_bitlen_count, | |
_fix_block_literal_huffman_to_deflate_code, 7, | |
_fix_block_dist_huffman_bitlen_count, | |
_fix_block_dist_huffman_to_deflate_code, 5) | |
end | |
-- Decompress a dynamic block | |
-- @param state decompression state that will be modified by this function. | |
-- @return 0 if success, other value if fails. | |
local function DecompressDynamicBlock(state) | |
local ReadBits, Decode = state.ReadBits, state.Decode | |
local nlen = ReadBits(5) + 257 | |
local ndist = ReadBits(5) + 1 | |
local ncode = ReadBits(4) + 4 | |
if nlen > 286 or ndist > 30 then | |
-- dynamic block code description: too many length or distance codes | |
return -3 | |
end | |
local rle_codes_huffman_bitlens = {} | |
for i = 1, ncode do | |
rle_codes_huffman_bitlens[_rle_codes_huffman_bitlen_order[i]] = ReadBits(3) | |
end | |
local rle_codes_err, rle_codes_huffman_bitlen_counts, | |
rle_codes_huffman_symbols, rle_codes_huffman_min_bitlen = | |
GetHuffmanForDecode(rle_codes_huffman_bitlens, 18, 7) | |
if rle_codes_err ~= 0 then -- Require complete code set here | |
-- dynamic block code description: code lengths codes incomplete | |
return -4 | |
end | |
local lcodes_huffman_bitlens = {} | |
local dcodes_huffman_bitlens = {} | |
-- Read length/literal and distance code length tables | |
local index = 0 | |
while index < nlen + ndist do | |
local symbol -- Decoded value | |
local bitlen -- Last length to repeat | |
symbol = Decode(rle_codes_huffman_bitlen_counts, rle_codes_huffman_symbols, | |
rle_codes_huffman_min_bitlen) | |
if symbol < 0 then | |
return symbol -- Invalid symbol | |
elseif symbol < 16 then | |
if index < nlen then | |
lcodes_huffman_bitlens[index] = symbol | |
else | |
dcodes_huffman_bitlens[index - nlen] = symbol | |
end | |
index = index + 1 | |
else | |
bitlen = 0 | |
if symbol == 16 then | |
if index == 0 then | |
-- dynamic block code description: repeat lengths | |
-- with no first length | |
return -5 | |
end | |
if index - 1 < nlen then | |
bitlen = lcodes_huffman_bitlens[index - 1] | |
else | |
bitlen = dcodes_huffman_bitlens[index - nlen - 1] | |
end | |
symbol = 3 + ReadBits(2) | |
elseif symbol == 17 then -- Repeat zero 3..10 times | |
symbol = 3 + ReadBits(3) | |
else -- == 18, repeat zero 11.138 times | |
symbol = 11 + ReadBits(7) | |
end | |
if index + symbol > nlen + ndist then | |
-- dynamic block code description: | |
-- repeat more than specified lengths | |
return -6 | |
end | |
while symbol > 0 do -- Repeat last or zero symbol times | |
symbol = symbol - 1 | |
if index < nlen then | |
lcodes_huffman_bitlens[index] = bitlen | |
else | |
dcodes_huffman_bitlens[index - nlen] = bitlen | |
end | |
index = index + 1 | |
end | |
end | |
end | |
if (lcodes_huffman_bitlens[256] or 0) == 0 then | |
-- dynamic block code description: missing end-of-block code | |
return -9 | |
end | |
local lcodes_err, lcodes_huffman_bitlen_counts, lcodes_huffman_symbols, | |
lcodes_huffman_min_bitlen = GetHuffmanForDecode(lcodes_huffman_bitlens, | |
nlen - 1, 15) | |
-- dynamic block code description: invalid literal/length code lengths, | |
-- Incomplete code ok only for single length 1 code | |
if (lcodes_err ~= 0 and | |
(lcodes_err < 0 or nlen ~= (lcodes_huffman_bitlen_counts[0] or 0) + | |
(lcodes_huffman_bitlen_counts[1] or 0))) then return -7 end | |
local dcodes_err, dcodes_huffman_bitlen_counts, dcodes_huffman_symbols, | |
dcodes_huffman_min_bitlen = GetHuffmanForDecode(dcodes_huffman_bitlens, | |
ndist - 1, 15) | |
-- dynamic block code description: invalid distance code lengths, | |
-- Incomplete code ok only for single length 1 code | |
if (dcodes_err ~= 0 and | |
(dcodes_err < 0 or ndist ~= (dcodes_huffman_bitlen_counts[0] or 0) + | |
(dcodes_huffman_bitlen_counts[1] or 0))) then return -8 end | |
-- Build buffman table for literal/length codes | |
return DecodeUntilEndOfBlock(state, lcodes_huffman_bitlen_counts, | |
lcodes_huffman_symbols, | |
lcodes_huffman_min_bitlen, | |
dcodes_huffman_bitlen_counts, | |
dcodes_huffman_symbols, dcodes_huffman_min_bitlen) | |
end | |
-- Decompress a deflate stream | |
-- @param state: a decompression state | |
-- @return the decompressed string if succeeds. nil if fails. | |
local function Inflate(state) | |
local ReadBits = state.ReadBits | |
local is_last_block | |
while not is_last_block do | |
is_last_block = (ReadBits(1) == 1) | |
local block_type = ReadBits(2) | |
local status | |
if block_type == 0 then | |
status = DecompressStoreBlock(state) | |
elseif block_type == 1 then | |
status = DecompressFixBlock(state) | |
elseif block_type == 2 then | |
status = DecompressDynamicBlock(state) | |
else | |
return nil, -1 -- invalid block type (type == 3) | |
end | |
if status ~= 0 then return nil, status end | |
end | |
state.result_buffer[#state.result_buffer + 1] = | |
table_concat(state.buffer, "", 1, state.buffer_size) | |
local result = table_concat(state.result_buffer) | |
return result | |
end | |
-- @see LibDeflate:DecompressDeflate(str) | |
-- @see LibDeflate:DecompressDeflateWithDict(str, dictionary) | |
local function DecompressDeflateInternal(str, dictionary) | |
local state = CreateDecompressState(str, dictionary) | |
local result, status = Inflate(state) | |
if not result then return nil, status end | |
local bitlen_left = state.ReaderBitlenLeft() | |
local bytelen_left = (bitlen_left - bitlen_left % 8) / 8 | |
return result, bytelen_left | |
end | |
-- @see LibDeflate:DecompressZlib(str) | |
-- @see LibDeflate:DecompressZlibWithDict(str) | |
local function DecompressZlibInternal(str, dictionary) | |
local state = CreateDecompressState(str, dictionary) | |
local ReadBits = state.ReadBits | |
local CMF = ReadBits(8) | |
if state.ReaderBitlenLeft() < 0 then | |
return nil, 2 -- available inflate data did not terminate | |
end | |
local CM = CMF % 16 | |
local CINFO = (CMF - CM) / 16 | |
if CM ~= 8 then | |
return nil, -12 -- invalid compression method | |
end | |
if CINFO > 7 then | |
return nil, -13 -- invalid window size | |
end | |
local FLG = ReadBits(8) | |
if state.ReaderBitlenLeft() < 0 then | |
return nil, 2 -- available inflate data did not terminate | |
end | |
if (CMF * 256 + FLG) % 31 ~= 0 then | |
return nil, -14 -- invalid header checksum | |
end | |
local FDIST = ((FLG - FLG % 32) / 32 % 2) | |
local FLEVEL = ((FLG - FLG % 64) / 64 % 4) -- luacheck: ignore FLEVEL | |
if FDIST == 1 then | |
if not dictionary then | |
return nil, -16 -- need dictonary, but dictionary is not provided. | |
end | |
local byte3 = ReadBits(8) | |
local byte2 = ReadBits(8) | |
local byte1 = ReadBits(8) | |
local byte0 = ReadBits(8) | |
local actual_adler32 = byte3 * 16777216 + byte2 * 65536 + byte1 * 256 + | |
byte0 | |
if state.ReaderBitlenLeft() < 0 then | |
return nil, 2 -- available inflate data did not terminate | |
end | |
if not IsEqualAdler32(actual_adler32, dictionary.adler32) then | |
return nil, -17 -- dictionary adler32 does not match | |
end | |
end | |
local result, status = Inflate(state) | |
if not result then return nil, status end | |
state.SkipToByteBoundary() | |
local adler_byte0 = ReadBits(8) | |
local adler_byte1 = ReadBits(8) | |
local adler_byte2 = ReadBits(8) | |
local adler_byte3 = ReadBits(8) | |
if state.ReaderBitlenLeft() < 0 then | |
return nil, 2 -- available inflate data did not terminate | |
end | |
local adler32_expected = adler_byte0 * 16777216 + adler_byte1 * 65536 + | |
adler_byte2 * 256 + adler_byte3 | |
local adler32_actual = LibDeflate:Adler32(result) | |
if not IsEqualAdler32(adler32_expected, adler32_actual) then | |
return nil, -15 -- Adler32 checksum does not match | |
end | |
local bitlen_left = state.ReaderBitlenLeft() | |
local bytelen_left = (bitlen_left - bitlen_left % 8) / 8 | |
return result, bytelen_left | |
end | |
--- Decompress a raw deflate compressed data. | |
-- @param str [string] The data to be decompressed. | |
-- @return [string/nil] If the decompression succeeds, return the decompressed | |
-- data. If the decompression fails, return nil. You should check if this return | |
-- value is non-nil to know if the decompression succeeds. | |
-- @return [integer] If the decompression succeeds, return the number of | |
-- unprocessed bytes in the input compressed data. This return value is a | |
-- positive integer if the input data is a valid compressed data appended by an | |
-- arbitary non-empty string. This return value is 0 if the input data does not | |
-- contain any extra bytes.<br> | |
-- If the decompression fails (The first return value of this function is nil), | |
-- this return value is undefined. | |
-- @see LibDeflate:CompressDeflate | |
function LibDeflate:DecompressDeflate(str) | |
local arg_valid, arg_err = IsValidArguments(str) | |
if not arg_valid then | |
error(("Usage: LibDeflate:DecompressDeflate(str): " .. arg_err), 2) | |
end | |
return DecompressDeflateInternal(str) | |
end | |
--- Decompress a raw deflate compressed data with a preset dictionary. | |
-- @param str [string] The data to be decompressed. | |
-- @param dictionary [table] The preset dictionary used by | |
-- LibDeflate:CompressDeflateWithDict when the compressed data is produced. | |
-- Decompression and compression must use the same dictionary. | |
-- Otherwise wrong decompressed data could be produced without generating any | |
-- error. | |
-- @return [string/nil] If the decompression succeeds, return the decompressed | |
-- data. If the decompression fails, return nil. You should check if this return | |
-- value is non-nil to know if the decompression succeeds. | |
-- @return [integer] If the decompression succeeds, return the number of | |
-- unprocessed bytes in the input compressed data. This return value is a | |
-- positive integer if the input data is a valid compressed data appended by an | |
-- arbitary non-empty string. This return value is 0 if the input data does not | |
-- contain any extra bytes.<br> | |
-- If the decompression fails (The first return value of this function is nil), | |
-- this return value is undefined. | |
-- @see LibDeflate:CompressDeflateWithDict | |
function LibDeflate:DecompressDeflateWithDict(str, dictionary) | |
local arg_valid, arg_err = IsValidArguments(str, true, dictionary) | |
if not arg_valid then | |
error(("Usage: LibDeflate:DecompressDeflateWithDict(str, dictionary): " .. | |
arg_err), 2) | |
end | |
return DecompressDeflateInternal(str, dictionary) | |
end | |
--- Decompress a zlib compressed data. | |
-- @param str [string] The data to be decompressed | |
-- @return [string/nil] If the decompression succeeds, return the decompressed | |
-- data. If the decompression fails, return nil. You should check if this return | |
-- value is non-nil to know if the decompression succeeds. | |
-- @return [integer] If the decompression succeeds, return the number of | |
-- unprocessed bytes in the input compressed data. This return value is a | |
-- positive integer if the input data is a valid compressed data appended by an | |
-- arbitary non-empty string. This return value is 0 if the input data does not | |
-- contain any extra bytes.<br> | |
-- If the decompression fails (The first return value of this function is nil), | |
-- this return value is undefined. | |
-- @see LibDeflate:CompressZlib | |
function LibDeflate:DecompressZlib(str) | |
local arg_valid, arg_err = IsValidArguments(str) | |
if not arg_valid then | |
error(("Usage: LibDeflate:DecompressZlib(str): " .. arg_err), 2) | |
end | |
return DecompressZlibInternal(str) | |
end | |
--- Decompress a zlib compressed data with a preset dictionary. | |
-- @param str [string] The data to be decompressed | |
-- @param dictionary [table] The preset dictionary used by | |
-- LibDeflate:CompressDeflateWithDict when the compressed data is produced. | |
-- Decompression and compression must use the same dictionary. | |
-- Otherwise wrong decompressed data could be produced without generating any | |
-- error. | |
-- @return [string/nil] If the decompression succeeds, return the decompressed | |
-- data. If the decompression fails, return nil. You should check if this return | |
-- value is non-nil to know if the decompression succeeds. | |
-- @return [integer] If the decompression succeeds, return the number of | |
-- unprocessed bytes in the input compressed data. This return value is a | |
-- positive integer if the input data is a valid compressed data appended by an | |
-- arbitary non-empty string. This return value is 0 if the input data does not | |
-- contain any extra bytes.<br> | |
-- If the decompression fails (The first return value of this function is nil), | |
-- this return value is undefined. | |
-- @see LibDeflate:CompressZlibWithDict | |
function LibDeflate:DecompressZlibWithDict(str, dictionary) | |
local arg_valid, arg_err = IsValidArguments(str, true, dictionary) | |
if not arg_valid then | |
error(("Usage: LibDeflate:DecompressZlibWithDict(str, dictionary): " .. | |
arg_err), 2) | |
end | |
return DecompressZlibInternal(str, dictionary) | |
end | |
-- Calculate the huffman code of fixed block | |
do | |
_fix_block_literal_huffman_bitlen = {} | |
for sym = 0, 143 do _fix_block_literal_huffman_bitlen[sym] = 8 end | |
for sym = 144, 255 do _fix_block_literal_huffman_bitlen[sym] = 9 end | |
for sym = 256, 279 do _fix_block_literal_huffman_bitlen[sym] = 7 end | |
for sym = 280, 287 do _fix_block_literal_huffman_bitlen[sym] = 8 end | |
_fix_block_dist_huffman_bitlen = {} | |
for dist = 0, 31 do _fix_block_dist_huffman_bitlen[dist] = 5 end | |
local status | |
status, _fix_block_literal_huffman_bitlen_count, _fix_block_literal_huffman_to_deflate_code = | |
GetHuffmanForDecode(_fix_block_literal_huffman_bitlen, 287, 9) | |
assert(status == 0) | |
status, _fix_block_dist_huffman_bitlen_count, _fix_block_dist_huffman_to_deflate_code = | |
GetHuffmanForDecode(_fix_block_dist_huffman_bitlen, 31, 5) | |
assert(status == 0) | |
_fix_block_literal_huffman_code = GetHuffmanCodeFromBitlen( | |
_fix_block_literal_huffman_bitlen_count, | |
_fix_block_literal_huffman_bitlen, 287, 9) | |
_fix_block_dist_huffman_code = GetHuffmanCodeFromBitlen( | |
_fix_block_dist_huffman_bitlen_count, | |
_fix_block_dist_huffman_bitlen, 31, 5) | |
end | |
-- While the codec stuff is neat, it's unnecessary for ComputerCraft files | |
-- which can store and transmit data of any type with no restrictions on | |
-- content. | |
-- For test. Don't use the functions in this table for real application. | |
-- Stuffs in this table is subject to change. | |
-- Since you aren't supposed to use this stuff anyways, I'm just gonna comment | |
-- it out. | |
--[[LibDeflate.internals = { | |
LoadStringToTable = LoadStringToTable, | |
IsValidDictionary = IsValidDictionary, | |
IsEqualAdler32 = IsEqualAdler32, | |
_byte_to_6bit_char = _byte_to_6bit_char, | |
_6bit_to_byte = _6bit_to_byte, | |
InternalClearCache = InternalClearCache | |
}]] | |
-- Also removed the command line thing | |
return LibDeflate |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
--[[-- | |
LibDeflate 1.0.2-release <br> | |
Pure Lua compressor and decompressor with high compression ratio using | |
DEFLATE/zlib format. | |
Based on the original by Haoqian He, pared down for ComputerCraft usage | |
by Robert "khuxkm/minerobber" Miles | |
]] --[[ | |
zlib License | |
(C) 2018-2021 Haoqian He | |
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. | |
License History: | |
1. GNU General Public License Version 3 in v1.0.0 and earlier versions. | |
2. GNU Lesser General Public License Version 3 in v1.0.1 | |
3. the zlib License since v1.0.2 | |
Credits and Disclaimer: | |
This library rewrites the code from the algorithm | |
and the ideas of the following projects, | |
and uses their code to help to test the correctness of this library, | |
but their code is not included directly in the library itself. | |
Their original licenses shall be comply when used. | |
1. zlib, by Jean-loup Gailly (compression) and Mark Adler (decompression). | |
http://www.zlib.net/ | |
Licensed under zlib License. http://www.zlib.net/zlib_license.html | |
For the compression algorithm. | |
2. puff, by Mark Adler. https://github.com/madler/zlib/tree/master/contrib/puff | |
Licensed under zlib License. http://www.zlib.net/zlib_license.html | |
For the decompression algorithm. | |
3. LibCompress, by jjsheets and Galmok of European Stormrage (Horde) | |
https://www.wowace.com/projects/libcompress | |
Licensed under GPLv2. | |
https://www.gnu.org/licenses/old-licenses/gpl-2.0.html | |
For the code to create customized codec. | |
4. WeakAuras2, | |
https://github.com/WeakAuras/WeakAuras2 | |
Licensed under GPLv2. | |
For the 6bit encoding and decoding. | |
]] | |
local JtAjijkG | |
do local YKA7cU="1.0.2-release" | |
local mCsewfX="LibDeflate "..YKA7cU.. | |
" Copyright (C) 2018-2021 Haoqian He.".." Modifications (c) 2022 minerobber".. | |
" Licensed under the zlib License"JtAjijkG={}JtAjijkG._VERSION=YKA7cU;JtAjijkG._COPYRIGHT=mCsewfX end;local s=assert;local YAtG_LV3=error;local LfEJbh_=pairs;local JD=string.byte;local u=string.char | |
local pzDMZwG=string.find;local XPoQB=string.gsub;local XxJ=string.sub;local o5sms=table.concat | |
local JQi1jg=table.sort;local wVzn=tostring;local pE=type;local RSjapQ={}local QJf={}local zC={}local pfZ3SPy_={}local pDNa2ox6={}local Do6yo7nm={} | |
local y06X3k={}local ivnJjrA={}local d3fMjkg={} | |
local el={3,4,5,6,7,8,9,10,11,13,15,17,19,23,27,31,35,43,51,59,67,83,99,115,131,163,195,227,258} | |
local Wu_uIt={0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0} | |
local w={[0]=1,2,3,4,5,7,9,13,17,25,33,49,65,97,129,193,257,385,513,769,1025,1537,2049,3073,4097,6145,8193,12289,16385,24577} | |
local sgeP={[0]=0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13}local CM={16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15}local Qlmlet | |
local _;local RkGFh6;local hw18;local nvCiFt7r;local xSebv5Jc;local mMp;local rDtVf;for yY=0,255 do QJf[yY]=u(yY)end | |
do local Xf=1;for UlFdiZ7v=0,32 | |
do RSjapQ[UlFdiZ7v]=Xf;Xf=Xf*2 end end | |
for U=1,9 do zC[U]={} | |
for wFeA=0,RSjapQ[U+1]-1 do local JQgI=0;local N=wFeA;for fs52REi=1,U do JQgI=JQgI-JQgI%2+ | |
(( | |
(JQgI%2 ==1)or(N%2)==1)and 1 or 0)N=(N-N%2)/2;JQgI= | |
JQgI*2 end;zC[U][wFeA]=(JQgI- | |
JQgI%2)/2 end end | |
do local PUNkgaiM=18;local s6FbB=16;local X=265;local dc61=1 | |
for aguhyl=3,258 do | |
if aguhyl<=10 then | |
pfZ3SPy_[aguhyl]=aguhyl+254;Do6yo7nm[aguhyl]=0 elseif aguhyl==258 then pfZ3SPy_[aguhyl]=285 | |
Do6yo7nm[aguhyl]=0 else if aguhyl>PUNkgaiM then PUNkgaiM=PUNkgaiM+s6FbB;s6FbB=s6FbB*2;X=X+4 | |
dc61=dc61+1 end | |
local p=aguhyl-PUNkgaiM-1+s6FbB/2;pfZ3SPy_[aguhyl]= | |
(p- (p% (s6FbB/8)))/ (s6FbB/8)+X;Do6yo7nm[aguhyl]=dc61;pDNa2ox6[aguhyl]= | |
p% (s6FbB/8)end end end | |
do y06X3k[1]=0;y06X3k[2]=1;d3fMjkg[1]=0;d3fMjkg[2]=0;local gOPDv=3;local aSdZU3=4 | |
local YKDL=2;local oFyb6OLp=0 | |
for oGdh_mv=3,256 do if oGdh_mv>aSdZU3 then gOPDv=gOPDv*2;aSdZU3=aSdZU3*2;YKDL=YKDL+2;oFyb6OLp= | |
oFyb6OLp+1 end | |
y06X3k[oGdh_mv]=( | |
oGdh_mv<=gOPDv)and YKDL or(YKDL+1) | |
d3fMjkg[oGdh_mv]=(oFyb6OLp<0)and 0 or oFyb6OLp;if aSdZU3 >=8 then | |
ivnJjrA[oGdh_mv]=(oGdh_mv-aSdZU3/2-1)% (aSdZU3/4)end end end | |
function JtAjijkG:Adler32(WjvvK)if pE(WjvvK)~="string"then | |
YAtG_LV3(("Usage: LibDeflate:Adler32(str):".." 'str' - string expected got '%s'."):format(pE(WjvvK)),2)end | |
local TASVwBgU=#WjvvK;local KjUncMB=1;local XkT=1;local c3dr=0 | |
while KjUncMB<=TASVwBgU-15 do | |
local NGH,tIc,MD2O,HQ,cng,lE,nI2F0id,N4aMD_P,pCi,NzeoQJ,AwGfFV,wCRY,d0uKSVw1,lNOqUk8,YAnZNei,h8YWR44E=JD(WjvvK,KjUncMB,KjUncMB+15) | |
c3dr= | |
( | |
c3dr+16*XkT+16*NGH+15*tIc+14*MD2O+13*HQ+12*cng+11*lE+10*nI2F0id+9*N4aMD_P+8*pCi+7*NzeoQJ+6*AwGfFV+5*wCRY+4*d0uKSVw1+3*lNOqUk8+2* | |
YAnZNei+h8YWR44E)%65521 | |
XkT= | |
( | |
XkT+NGH+tIc+MD2O+HQ+cng+lE+nI2F0id+N4aMD_P+pCi+NzeoQJ+AwGfFV+wCRY+d0uKSVw1+lNOqUk8+YAnZNei+h8YWR44E)%65521;KjUncMB=KjUncMB+16 end;while(KjUncMB<=TASVwBgU)do local VF=JD(WjvvK,KjUncMB,KjUncMB)XkT= | |
(XkT+VF)%65521;c3dr=(c3dr+XkT)%65521 | |
KjUncMB=KjUncMB+1 end;return | |
(c3dr*65536+XkT)%4294967296 end;local function vj(fTrMe,ypDndT8) | |
return(fTrMe%4294967296)== (ypDndT8%4294967296)end | |
function JtAjijkG:CreateDictionary(MV65,Y3D66Ym9,q) | |
if | |
pE(MV65)~="string"then | |
YAtG_LV3(("Usage: LibDeflate:CreateDictionary(str, strlen, adler32):".." 'str' - string expected got '%s'."):format(pE(MV65)),2)end | |
if pE(Y3D66Ym9)~="number"then | |
YAtG_LV3(("Usage: LibDeflate:CreateDictionary(str, strlen, adler32):".. | |
" 'strlen' - number expected got '%s'."):format(pE(Y3D66Ym9)),2)end | |
if pE(q)~="number"then | |
YAtG_LV3(("Usage: LibDeflate:CreateDictionary(str, strlen, adler32):".." 'adler32' - number expected got '%s'."):format(pE(q)),2)end | |
if Y3D66Ym9 ~=#MV65 then | |
YAtG_LV3(("Usage: LibDeflate:CreateDictionary(str, strlen, adler32):".. | |
" 'strlen' does not match the actual length of 'str'.".. | |
" 'strlen': %u, '#str': %u .".." Please check if 'str' is modified unintentionally."):format(Y3D66Ym9, | |
#MV65))end;if Y3D66Ym9 ==0 then | |
YAtG_LV3(("Usage: LibDeflate:CreateDictionary(str, strlen, adler32):".." 'str' - Empty string is not allowed."),2)end | |
if Y3D66Ym9 > | |
32768 then | |
YAtG_LV3(("Usage: LibDeflate:CreateDictionary(str, strlen, adler32):".." 'str' - string longer than 32768 bytes is not allowed.".. | |
" Got %d bytes."):format(Y3D66Ym9),2)end;local PhJ=self:Adler32(MV65) | |
if not vj(q,PhJ)then | |
YAtG_LV3(( | |
"Usage: LibDeflate:CreateDictionary(str, strlen, adler32):".. | |
" 'adler32' does not match the actual adler32 of 'str'.".. | |
" 'adler32': %u, 'Adler32(str)': %u .".." Please check if 'str' is modified unintentionally."):format(q,PhJ))end;local h={}h.adler32=q;h.hash_tables={}h.string_table={}h.strlen=Y3D66Ym9 | |
local j2K=h.string_table;local r8hgwQ=h.hash_tables;j2K[1]=JD(MV65,1,1)j2K[2]=JD(MV65,2,2) | |
if | |
Y3D66Ym9 >=3 then local _6U=1;local GLSzBQs=j2K[1]*256+j2K[2] | |
while _6U<=Y3D66Ym9-2-3 do local c,xg,Id2KoP_G,Y2or=JD(MV65, | |
_6U+2,_6U+5)j2K[_6U+2]=c | |
j2K[_6U+3]=xg;j2K[_6U+4]=Id2KoP_G;j2K[_6U+5]=Y2or;GLSzBQs=(GLSzBQs*256+c)% | |
16777216;local zN8ASHV5=r8hgwQ[GLSzBQs]if not zN8ASHV5 then | |
zN8ASHV5={}r8hgwQ[GLSzBQs]=zN8ASHV5 end;zN8ASHV5[#zN8ASHV5+1]= | |
_6U-Y3D66Ym9;_6U=_6U+1 | |
GLSzBQs=(GLSzBQs*256+xg)%16777216;zN8ASHV5=r8hgwQ[GLSzBQs]if not zN8ASHV5 then zN8ASHV5={} | |
r8hgwQ[GLSzBQs]=zN8ASHV5 end | |
zN8ASHV5[#zN8ASHV5+1]=_6U-Y3D66Ym9;_6U=_6U+1 | |
GLSzBQs=(GLSzBQs*256+Id2KoP_G)%16777216;zN8ASHV5=r8hgwQ[GLSzBQs]if not zN8ASHV5 then zN8ASHV5={} | |
r8hgwQ[GLSzBQs]=zN8ASHV5 end | |
zN8ASHV5[#zN8ASHV5+1]=_6U-Y3D66Ym9;_6U=_6U+1 | |
GLSzBQs=(GLSzBQs*256+Y2or)%16777216;zN8ASHV5=r8hgwQ[GLSzBQs]if not zN8ASHV5 then zN8ASHV5={} | |
r8hgwQ[GLSzBQs]=zN8ASHV5 end | |
zN8ASHV5[#zN8ASHV5+1]=_6U-Y3D66Ym9;_6U=_6U+1 end | |
while _6U<=Y3D66Ym9-2 do local iju=JD(MV65,_6U+2)j2K[_6U+2]=iju;GLSzBQs=( | |
GLSzBQs*256+iju)%16777216 | |
local XsWgh=r8hgwQ[GLSzBQs]if not XsWgh then XsWgh={}r8hgwQ[GLSzBQs]=XsWgh end;XsWgh[#XsWgh+ | |
1]=_6U-Y3D66Ym9;_6U=_6U+1 end end;return h end | |
local function z(l4Hdz) | |
if pE(l4Hdz)~="table"then return false, | |
("'dictionary' - table expected got '%s'."):format(pE(l4Hdz))end | |
if | |
pE(l4Hdz.adler32)~="number"or | |
pE(l4Hdz.string_table)~="table"or pE(l4Hdz.strlen)~="number"or l4Hdz.strlen<=0 or | |
l4Hdz.strlen>32768 or l4Hdz.strlen~=#l4Hdz.string_table or pE(l4Hdz.hash_tables)~="table"then return false, | |
("'dictionary' - corrupted dictionary."):format(pE(l4Hdz))end;return true,""end | |
local Zg={[0]={false,nil,0,0,0},[1]={false,nil,4,8,4},[2]={false,nil,5,18,8},[3]={false,nil,6,32,32},[4]={true,4,4,16,16},[5]={true,8,16,32,32},[6]={true,8,16,128,128},[7]={true,8,32,128,256},[8]={true,32,128,258,1024},[9]={true,32,258,258,4096}} | |
local function ykRppH(NSXCgSH,Wq,SbOQ,IiuHGo,cGqxtYr) | |
if pE(NSXCgSH)~="string"then return false, | |
("'str' - string expected got '%s'."):format(pE(NSXCgSH))end | |
if Wq then local bgJFKeeZ,yu9fg0nN=z(SbOQ)if not bgJFKeeZ then return false,yu9fg0nN end end | |
if IiuHGo then local wgx=pE(cGqxtYr) | |
if wgx~="nil"and wgx~="table"then return false, | |
("'configs' - nil or table expected got '%s'."):format(pE(cGqxtYr))end | |
if wgx=="table"then | |
for zlU7X,t in LfEJbh_(cGqxtYr)do | |
if zlU7X~="level"and zlU7X~="strategy"then return false, | |
("'configs' - unsupported table key in the configs: '%s'."):format(zlU7X)elseif | |
zlU7X=="level"and not Zg[t]then return false, | |
("'configs' - unsupported 'level': %s."):format(wVzn(t))elseif | |
zlU7X=="strategy"and t~="fixed"and t~="huffman_only"and t~="dynamic"then return false, | |
("'configs' - unsupported 'strategy': '%s'."):format(wVzn(t))end end end end;return true,""end;local WQ6=0;local y36Aetn=1;local iPL3B4cr=2;local GI2hz6SK=3 | |
local function Oh()local f6qbO=0;local kk=0;local QrubIAv=0;local bLHDW=0;local YjFd7b={} | |
local jZgPYb={} | |
local function zN2(OWJ,WtalJw)kk=kk+OWJ*RSjapQ[QrubIAv] | |
QrubIAv=QrubIAv+WtalJw;bLHDW=bLHDW+WtalJw | |
if QrubIAv>=32 then f6qbO=f6qbO+1 | |
YjFd7b[f6qbO]=QJf[kk%256]..QJf[(( | |
kk-kk%256)/256%256)].. | |
QJf[( | |
(kk-kk%65536)/65536%256)]..QJf[( | |
(kk-kk%16777216)/16777216%256)]local JYrf2=RSjapQ[32-QrubIAv+WtalJw]kk= | |
(OWJ-OWJ%JYrf2)/JYrf2;QrubIAv=QrubIAv-32 end end | |
local function IN69pa5(KHDOUlRY)for I0JvPpn=1,QrubIAv,8 do f6qbO=f6qbO+1;YjFd7b[f6qbO]=u(kk%256) | |
kk=(kk-kk%256)/256 end;QrubIAv=0;f6qbO=f6qbO+1 | |
YjFd7b[f6qbO]=KHDOUlRY;bLHDW=bLHDW+#KHDOUlRY*8 end | |
local function U(Ce4ZE)if Ce4ZE==GI2hz6SK then return bLHDW end | |
if | |
Ce4ZE==y36Aetn or Ce4ZE==iPL3B4cr then local lB=(8-QrubIAv%8)%8 | |
if QrubIAv>0 then kk=kk-RSjapQ[QrubIAv]+RSjapQ[ | |
QrubIAv+lB] | |
for byE=1,QrubIAv,8 do | |
f6qbO=f6qbO+1;YjFd7b[f6qbO]=QJf[kk%256]kk=(kk-kk%256)/256 end;kk=0;QrubIAv=0 end;if Ce4ZE==iPL3B4cr then bLHDW=bLHDW+lB;return bLHDW end end;local OVx_mN=o5sms(YjFd7b)YjFd7b={}f6qbO=0 | |
jZgPYb[#jZgPYb+1]=OVx_mN | |
if Ce4ZE==WQ6 then return bLHDW else return bLHDW,o5sms(jZgPYb)end end;return zN2,IN69pa5,U end | |
local function PG(bITCI,K,F5dtVpnN)F5dtVpnN=F5dtVpnN+1;bITCI[F5dtVpnN]=K;local kxeBp=K[1]local a=F5dtVpnN;local kQ= | |
(a-a%2)/2 | |
while(kQ>=1 and bITCI[kQ][1]>kxeBp)do | |
local EE9LAE=bITCI[kQ]bITCI[kQ]=K;bITCI[a]=EE9LAE;a=kQ;kQ=(kQ-kQ%2)/2 end end | |
local function n(iVx,eg)local AQviNt=iVx[1]local T6=iVx[eg]local NviN0i=T6[1]iVx[1]=T6;iVx[eg]=AQviNt | |
eg=eg-1;local BlMQce=1;local o=BlMQce*2;local dpRE=o+1 | |
while(o<=eg)do local fEiXwWq=iVx[o] | |
if(dpRE<=eg and | |
iVx[dpRE][1]<fEiXwWq[1])then | |
local r3JzMga6=iVx[dpRE]if r3JzMga6[1]<NviN0i then iVx[dpRE]=T6;iVx[BlMQce]=r3JzMga6;BlMQce=dpRE;o=BlMQce* | |
2;dpRE=o+1 else break end else if | |
fEiXwWq[1]<NviN0i then iVx[o]=T6;iVx[BlMQce]=fEiXwWq;BlMQce=o;o=BlMQce*2;dpRE=o+1 else | |
break end end end;return AQviNt end | |
local function O(Tuyw,FYLcr2nu,ioS69,AiP)local S2jwpoi=0;local _WX9u={}local u0riyU={} | |
for U=1,AiP do S2jwpoi= | |
(S2jwpoi+ (Tuyw[U-1]or 0))*2;_WX9u[U]=S2jwpoi end | |
for H=0,ioS69 do local WNph=FYLcr2nu[H] | |
if WNph then S2jwpoi=_WX9u[WNph] | |
_WX9u[WNph]=S2jwpoi+1 | |
if WNph<=9 then u0riyU[H]=zC[WNph][S2jwpoi]else local ytF=0 | |
for d=1,WNph do ytF=ytF-ytF%2+ | |
(( | |
(ytF%2 ==1)or(S2jwpoi%2)==1)and 1 or 0)S2jwpoi= | |
(S2jwpoi-S2jwpoi%2)/2;ytF=ytF*2 end;u0riyU[H]=(ytF-ytF%2)/2 end end end;return u0riyU end | |
local function N5UjTN(gRm,LPX0)return gRm[1]<LPX0[1]or | |
(gRm[1]==LPX0[1]and gRm[2]<LPX0[2])end | |
local function qLH5(g,_l,qao)local ipUPIzc;local N8=-1;local Gzk={}local J7nsK={}local dXbd={}local vQj={}local sVBxyy={}local N9d=0;for S7,bJtvRSR in LfEJbh_(g)do | |
N9d=N9d+1;Gzk[N9d]={bJtvRSR,S7}end | |
if(N9d==0)then | |
return{},{},-1 elseif(N9d==1)then local aBhZK5=Gzk[1][2]dXbd[aBhZK5]=1;vQj[aBhZK5]=0 | |
return dXbd,vQj,aBhZK5 else JQi1jg(Gzk,N5UjTN)ipUPIzc=N9d | |
for UYQF=1,ipUPIzc do J7nsK[UYQF]=Gzk[UYQF]end | |
while(ipUPIzc>1)do local WXx=n(J7nsK,ipUPIzc)ipUPIzc=ipUPIzc-1 | |
local W4EuxJXi=n(J7nsK,ipUPIzc)ipUPIzc=ipUPIzc-1 | |
local BlYNd61h={WXx[1]+W4EuxJXi[1],-1,WXx,W4EuxJXi}PG(J7nsK,BlYNd61h,ipUPIzc)ipUPIzc=ipUPIzc+1 end;local Jz8JUscj=0;local OtGmbAgE={J7nsK[1],0,0,0}local oU_r=1;local n_lv=1;J7nsK[1][1]=0 | |
while( | |
n_lv<=oU_r)do local XDPndG=OtGmbAgE[n_lv]local sJYFQIP4=XDPndG[1] | |
local Ogq0S2=XDPndG[2]local n8Cw3SR=XDPndG[3]local GJqd7gt=XDPndG[4]if n8Cw3SR then oU_r=oU_r+1 | |
OtGmbAgE[oU_r]=n8Cw3SR;n8Cw3SR[1]=sJYFQIP4+1 end | |
if GJqd7gt then | |
oU_r=oU_r+1;OtGmbAgE[oU_r]=GJqd7gt;GJqd7gt[1]=sJYFQIP4+1 end;n_lv=n_lv+1 | |
if(sJYFQIP4 >_l)then Jz8JUscj=Jz8JUscj+1;sJYFQIP4=_l end;if Ogq0S2 >=0 then dXbd[Ogq0S2]=sJYFQIP4 | |
N8=(Ogq0S2 >N8)and Ogq0S2 or N8 | |
sVBxyy[sJYFQIP4]=(sVBxyy[sJYFQIP4]or 0)+1 end end | |
if(Jz8JUscj>0)then | |
repeat local slE5aDm2=_l-1;while | |
((sVBxyy[slE5aDm2]or 0)==0)do slE5aDm2=slE5aDm2-1 end;sVBxyy[slE5aDm2]= | |
sVBxyy[slE5aDm2]-1;sVBxyy[slE5aDm2+1]= | |
(sVBxyy[slE5aDm2+1]or 0)+2;sVBxyy[_l]=sVBxyy[_l]-1;Jz8JUscj= | |
Jz8JUscj-2 until(Jz8JUscj<=0)n_lv=1;for aL_g=_l,1,-1 do local IMUI10L=sVBxyy[aL_g]or 0 | |
while(IMUI10L>0)do | |
local vPA=Gzk[n_lv][2]dXbd[vPA]=aL_g;IMUI10L=IMUI10L-1;n_lv=n_lv+1 end end end;vQj=O(sVBxyy,dXbd,qao,_l)return dXbd,vQj,N8 end end | |
local function tE(pUXZ6G4,mk,OeQex1U4,i0cV9)local EGD=0;local VWiGCreH={}local B_kkL={}local uEO6Y=0;local i_053JPY={}local l=nil;local UK=0;i0cV9=(i0cV9 <0)and 0 or | |
i0cV9;local NzaICo=mk+i0cV9+1 | |
for k1X83nYm=0,NzaICo+1 do | |
local xxzxfj= | |
(k1X83nYm<=mk)and(pUXZ6G4[k1X83nYm]or 0)or( | |
(k1X83nYm<=NzaICo)and(OeQex1U4[k1X83nYm-mk-1]or 0)or nil) | |
if xxzxfj==l then UK=UK+1 | |
if xxzxfj~=0 and UK==6 then EGD=EGD+1;VWiGCreH[EGD]=16 | |
uEO6Y=uEO6Y+1;i_053JPY[uEO6Y]=3 | |
B_kkL[16]=(B_kkL[16]or 0)+1;UK=0 elseif xxzxfj==0 and UK==138 then EGD=EGD+1;VWiGCreH[EGD]=18;uEO6Y=uEO6Y+1 | |
i_053JPY[uEO6Y]=127;B_kkL[18]=(B_kkL[18]or 0)+1;UK=0 end else | |
if UK==1 then EGD=EGD+1;VWiGCreH[EGD]=l | |
B_kkL[l]=(B_kkL[l]or 0)+1 elseif UK==2 then EGD=EGD+1;VWiGCreH[EGD]=l;EGD=EGD+1;VWiGCreH[EGD]=l;B_kkL[l]=( | |
B_kkL[l]or 0)+2 elseif UK>=3 then EGD=EGD+1;local _ad1m4I=(l~=0)and 16 or( | |
UK<=10 and 17 or 18) | |
VWiGCreH[EGD]=_ad1m4I | |
B_kkL[_ad1m4I]=(B_kkL[_ad1m4I]or 0)+1;uEO6Y=uEO6Y+1 | |
i_053JPY[uEO6Y]=(UK<=10)and(UK-3)or(UK-11)end;l=xxzxfj | |
if xxzxfj and xxzxfj~=0 then EGD=EGD+1;VWiGCreH[EGD]=xxzxfj;B_kkL[xxzxfj]=( | |
B_kkL[xxzxfj]or 0)+1;UK=0 else UK=1 end end end;return VWiGCreH,i_053JPY,B_kkL end | |
local function VcV0EuD(H1QsS,rIMx,TiA,Y51P,ichL)local NOK=TiA-ichL | |
while NOK<=Y51P-15-ichL do | |
rIMx[NOK],rIMx[NOK+1],rIMx[NOK+2],rIMx[ | |
NOK+3],rIMx[NOK+4],rIMx[NOK+5],rIMx[NOK+6],rIMx[NOK+7],rIMx[NOK+8],rIMx[NOK+9],rIMx[ | |
NOK+10],rIMx[NOK+11],rIMx[NOK+12],rIMx[NOK+13],rIMx[NOK+14],rIMx[NOK+15]=JD(H1QsS, | |
NOK+ichL,NOK+15+ichL)NOK=NOK+16 end;while(NOK<=Y51P-ichL)do | |
rIMx[NOK]=JD(H1QsS,NOK+ichL,NOK+ichL)NOK=NOK+1 end;return rIMx end | |
local function pX4gCR(Alv,YeLO2,CkrmO,ooovsSJe,s5IsD,KvYEVoXt,VWWD_P)local zsMuNkv=Zg[Alv] | |
local aXxi,Q18a7QTy,K5Rp6,GTIA,gdPUe=zsMuNkv[1],zsMuNkv[2],zsMuNkv[3],zsMuNkv[4],zsMuNkv[5]local _bxEn=(not aXxi)and K5Rp6 or 2147483646;local pcN_ceXY=(gdPUe- | |
gdPUe%4/4)local _P;local rq;local mo;local I=0 | |
if VWWD_P then | |
rq=VWWD_P.hash_tables;mo=VWWD_P.string_table;I=VWWD_P.strlen;s(ooovsSJe==1)if | |
s5IsD>=ooovsSJe and I>=2 then | |
_P=mo[I-1]*65536+mo[I]*256+YeLO2[1]local r3=CkrmO[_P]if not r3 then r3={}CkrmO[_P]=r3 end | |
r3[#r3+1]=-1 end | |
if s5IsD>= | |
ooovsSJe+1 and I>=1 then _P=mo[I]*65536+YeLO2[1]*256+ | |
YeLO2[2]local p=CkrmO[_P] | |
if not p then p={}CkrmO[_P]=p end;p[#p+1]=0 end end;local RAAJAsR=I+3 | |
_P= | |
(YeLO2[ooovsSJe-KvYEVoXt]or 0)*256+ (YeLO2[ooovsSJe+1-KvYEVoXt]or 0)local c1pjj7={}local BMv=0;local NQh8={}local P={}local bkTe=0;local ohmPbyDd={}local D={}local DfDLWkT=0;local MTU8HP4d={} | |
local hIM_cG0i=0;local jD=false;local me;local sgU5HAMG;local FDydY=0;local PEZ_=0;local c=ooovsSJe | |
local ElbTbcZG=s5IsD+ (aXxi and 1 or 0) | |
while(c<=ElbTbcZG)do local UiVYRok=c-KvYEVoXt;local jvPsY9=KvYEVoXt-3;me=FDydY | |
sgU5HAMG=PEZ_;FDydY=0;_P= | |
(_P*256+ (YeLO2[UiVYRok+2]or 0))%16777216;local tEBmuypm;local hW | |
local iOcgdUx=CkrmO[_P]local kCwLIk | |
if not iOcgdUx then kCwLIk=0;iOcgdUx={}CkrmO[_P]=iOcgdUx;if rq then hW=rq[_P]tEBmuypm= | |
hW and#hW or 0 else tEBmuypm=0 end else | |
kCwLIk=#iOcgdUx;hW=iOcgdUx;tEBmuypm=kCwLIk end;if c<=s5IsD then iOcgdUx[kCwLIk+1]=c end | |
if | |
(tEBmuypm>0 and | |
c+2 <=s5IsD and(not aXxi or me<K5Rp6))then | |
local _l=(aXxi and me>=Q18a7QTy)and pcN_ceXY or gdPUe;local rjQ=s5IsD-c;rjQ=(rjQ>=257)and 257 or rjQ | |
rjQ=rjQ+UiVYRok;local Euo0=UiVYRok+3 | |
while tEBmuypm>=1 and _l>0 do local LIV=hW[tEBmuypm]if | |
c-LIV>32768 then break end | |
if LIV<c then local vydlAbZ3=Euo0 | |
if LIV>=-257 then local mKLU=LIV-jvPsY9 | |
while | |
(vydlAbZ3 <=rjQ and | |
YeLO2[mKLU]==YeLO2[vydlAbZ3])do vydlAbZ3=vydlAbZ3+1;mKLU=mKLU+1 end else local Him=RAAJAsR+LIV | |
while | |
(vydlAbZ3 <=rjQ and mo[Him]==YeLO2[vydlAbZ3])do vydlAbZ3=vydlAbZ3+1;Him=Him+1 end end;local BXxv5z=vydlAbZ3-UiVYRok | |
if BXxv5z>FDydY then FDydY=BXxv5z;PEZ_=c-LIV end;if FDydY>=GTIA then break end end;tEBmuypm=tEBmuypm-1;_l=_l-1;if tEBmuypm==0 and LIV>0 and rq then | |
hW=rq[_P]tEBmuypm=hW and#hW or 0 end end end;if not aXxi then me,sgU5HAMG=FDydY,PEZ_ end | |
if | |
( | |
(not aXxi or jD)and(me>3 or( | |
me==3 and sgU5HAMG<4096))and FDydY<=me)then local cPDhu=pfZ3SPy_[me]local UQnOS=Do6yo7nm[me]local tRWU,X2Zy_nb,ITtw3N7E | |
if sgU5HAMG<=256 then | |
tRWU=y06X3k[sgU5HAMG]ITtw3N7E=ivnJjrA[sgU5HAMG]X2Zy_nb=d3fMjkg[sgU5HAMG]else tRWU=16 | |
X2Zy_nb=7;local yozOp=384;local wxU=512 | |
while true do | |
if sgU5HAMG<=yozOp then ITtw3N7E= | |
(sgU5HAMG- (wxU/2)-1)% (wxU/4)break elseif sgU5HAMG<=wxU then ITtw3N7E=( | |
sgU5HAMG- (wxU/2)-1)% (wxU/4) | |
tRWU=tRWU+1;break else tRWU=tRWU+2;X2Zy_nb=X2Zy_nb+1;yozOp=yozOp*2;wxU=wxU*2 end end end;BMv=BMv+1;c1pjj7[BMv]=cPDhu | |
NQh8[cPDhu]=(NQh8[cPDhu]or 0)+1;bkTe=bkTe+1;P[bkTe]=tRWU | |
ohmPbyDd[tRWU]=(ohmPbyDd[tRWU]or 0)+1 | |
if UQnOS>0 then local kOmS5sy=pDNa2ox6[me]DfDLWkT=DfDLWkT+1;D[DfDLWkT]=kOmS5sy end | |
if X2Zy_nb>0 then hIM_cG0i=hIM_cG0i+1;MTU8HP4d[hIM_cG0i]=ITtw3N7E end | |
for CLSdD=c+1,c+me- (aXxi and 2 or 1)do | |
_P=(_P*256+ ( | |
YeLO2[CLSdD-KvYEVoXt+2]or 0))%16777216 | |
if me<=_bxEn then iOcgdUx=CkrmO[_P] | |
if not iOcgdUx then iOcgdUx={}CkrmO[_P]=iOcgdUx end;iOcgdUx[#iOcgdUx+1]=CLSdD end end;c=c+me- (aXxi and 1 or 0)jD=false elseif | |
(not aXxi)or jD then | |
local Fh=YeLO2[aXxi and(UiVYRok-1)or UiVYRok]BMv=BMv+1;c1pjj7[BMv]=Fh | |
NQh8[Fh]=(NQh8[Fh]or 0)+1;c=c+1 else jD=true;c=c+1 end end;BMv=BMv+1;c1pjj7[BMv]=256 | |
NQh8[256]=(NQh8[256]or 0)+1;return c1pjj7,D,NQh8,P,MTU8HP4d,ohmPbyDd end | |
local function gad4ZcL(IlAPA,jLKMpQuK)local sUQpby,mbA,_qPhpaFx=qLH5(IlAPA,15,285) | |
local zex,pPGcdu,rjp=qLH5(jLKMpQuK,15,29)local cT2z,zke1tWps,gRFA=tE(sUQpby,_qPhpaFx,zex,rjp) | |
local jX9a0tJX,YFy4TGc=qLH5(gRFA,7,18)local YjpbYkCb=0 | |
for WpOZ=1,19 do local fD2289=CM[WpOZ]local folfO=jX9a0tJX[fD2289]or 0;if | |
folfO~=0 then YjpbYkCb=WpOZ end end;YjpbYkCb=YjpbYkCb-4;local L1p7luJ=_qPhpaFx+1-257;local eH=rjp+1-1;if eH<0 then | |
eH=0 end | |
return L1p7luJ,eH,YjpbYkCb,jX9a0tJX,YFy4TGc,cT2z,zke1tWps,sUQpby,mbA,zex,pPGcdu end | |
local function dk(vtsK,E1p4Mv,IHap,rDvV,RX1L2q,bCBtWguf,q)local e1sXUN4f=17;e1sXUN4f=e1sXUN4f+ (IHap+4)*3 | |
for VP=1,#RX1L2q do | |
local IQwqq=RX1L2q[VP]e1sXUN4f=e1sXUN4f+rDvV[IQwqq] | |
if IQwqq>=16 then e1sXUN4f=e1sXUN4f+ | |
( | |
(IQwqq==16)and 2 or(IQwqq==17 and 3 or 7))end end;local x=0 | |
for Xcc4=1,#vtsK do local fqw5=vtsK[Xcc4]local qnVfOeRE=bCBtWguf[fqw5] | |
e1sXUN4f=e1sXUN4f+qnVfOeRE | |
if fqw5 >256 then x=x+1;if fqw5 >264 and fqw5 <285 then local qeJtG=Wu_uIt[fqw5-256]e1sXUN4f= | |
e1sXUN4f+qeJtG end | |
local YIiSKsxK=E1p4Mv[x]local Ua=q[YIiSKsxK]e1sXUN4f=e1sXUN4f+Ua;if YIiSKsxK>3 then local pdpNgBcZ= | |
(YIiSKsxK-YIiSKsxK%2)/2-1 | |
e1sXUN4f=e1sXUN4f+pdpNgBcZ end end end;return e1sXUN4f end | |
local function E(wV,rLd,z8oF,DB6A7N,VhYX,Ha7ErH,rjU95v,sxBl,m,nD4LhX6z,iN,Lq,s9tW,R61K,Jf4os,a4xc,e)wV(rLd and 1 or 0,1)wV(2,2)wV(rjU95v,5)wV(sxBl,5) | |
wV(m,4)for Yw8Yxix=1,m+4 do local iVoXG=CM[Yw8Yxix]local JL0I04c=nD4LhX6z[iVoXG]or 0 | |
wV(JL0I04c,3)end;local la5=1 | |
for En6r_K97=1,#Lq do | |
local T4AA=Lq[En6r_K97]wV(iN[T4AA],nD4LhX6z[T4AA])if T4AA>=16 then local VnuCKTdu=s9tW[la5] | |
wV(VnuCKTdu,( | |
T4AA==16)and 2 or(T4AA==17 and 3 or 7))la5=la5+1 end end;local i=0;local R=0;local xWVu=0 | |
for XnNgn=1,#z8oF do local H1JD=z8oF[XnNgn]local gEEa9I=Jf4os[H1JD] | |
local ULLLDUm=R61K[H1JD]wV(gEEa9I,ULLLDUm) | |
if H1JD>256 then i=i+1 | |
if H1JD>264 and H1JD<285 then R=R+1 | |
local YWPfQKb2=DB6A7N[R]local r=Wu_uIt[H1JD-256]wV(YWPfQKb2,r)end;local e4F3=VhYX[i]local GsfNt7=e[e4F3]local fF0=a4xc[e4F3]wV(GsfNt7,fF0)if | |
e4F3 >3 then xWVu=xWVu+1;local OS0Zp3i=Ha7ErH[xWVu] | |
local BK=(e4F3-e4F3%2)/2-1;wV(OS0Zp3i,BK)end end end end | |
local function OO(Idjbe70,B)local nDjt=3;local NVWt=0 | |
for efuUGMh=1,#Idjbe70 do local p4nNp=Idjbe70[efuUGMh]local VW=RkGFh6[p4nNp]nDjt= | |
nDjt+VW | |
if p4nNp>256 then NVWt=NVWt+1;if p4nNp>264 and p4nNp<285 then | |
local V=Wu_uIt[p4nNp-256]nDjt=nDjt+V end;local Zt=B[NVWt] | |
nDjt=nDjt+5 | |
if Zt>3 then local mzeTI=(Zt-Zt%2)/2-1;nDjt=nDjt+mzeTI end end end;return nDjt end | |
local function y(sy4J,ztJhP_u8,D,XIcl,ys,rMQ1um8)sy4J(ztJhP_u8 and 1 or 0,1)sy4J(1,2)local U2=0;local X=0 | |
local zLtWO09=0 | |
for Z=1,#D do local ZDICnKE=D[Z]local L=Qlmlet[ZDICnKE]local B58=RkGFh6[ZDICnKE] | |
sy4J(L,B58) | |
if ZDICnKE>256 then U2=U2+1 | |
if ZDICnKE>264 and ZDICnKE<285 then X=X+1;local Pa=XIcl[X]local bmK=Wu_uIt[ | |
ZDICnKE-256]sy4J(Pa,bmK)end;local PYVzrNl=ys[U2]local KTVmRC=nvCiFt7r[PYVzrNl]sy4J(KTVmRC,5) | |
if PYVzrNl>3 then zLtWO09= | |
zLtWO09+1;local OJPc3R=rMQ1um8[zLtWO09]local j= | |
(PYVzrNl-PYVzrNl%2)/2-1;sy4J(OJPc3R,j)end end end end | |
local function cR6rJlAl(vMgKnGj,M9K,Zeu)s(M9K-vMgKnGj+1 <=65535)local Q2_d=3;Zeu=Zeu+3;local W0iTcMIt=(8- | |
Zeu%8)%8;Q2_d=Q2_d+W0iTcMIt;Q2_d=Q2_d+32;Q2_d=Q2_d+ (M9K- | |
vMgKnGj+1)*8;return Q2_d end | |
local function M6ilzGJ(N,Hald6SO,Dq,y3Ur,GL70F7uL,lqANrrJA,WUFTXBy6)s(lqANrrJA-GL70F7uL+1 <=65535)N( | |
Dq and 1 or 0,1)N(0,2)WUFTXBy6=WUFTXBy6+3;local aEZf= | |
(8-WUFTXBy6%8)%8 | |
if aEZf>0 then N(RSjapQ[aEZf]-1,aEZf)end;local QjQ_o=lqANrrJA-GL70F7uL+1;N(QjQ_o,16)local wDiq_= | |
(255-QjQ_o%256)+ | |
(255- (QjQ_o-QjQ_o%256)/256)*256;N(wDiq_,16) | |
Hald6SO(y3Ur:sub(GL70F7uL,lqANrrJA))end | |
local function iW6CD(QYA5WJOY,yliV8,rjpKFl,YUGQovw,XZt7GyF,Zn3SC)local D4={}local crA9EKx={}local IcsJ=nil;local A;local Wp9xT;local P;local o0_XG8FI=YUGQovw(GI2hz6SK) | |
local jLsxpw=#XZt7GyF;local x;local AXNfV;local cX | |
if QYA5WJOY then if QYA5WJOY.level then AXNfV=QYA5WJOY.level end;if | |
QYA5WJOY.strategy then cX=QYA5WJOY.strategy end end;if not AXNfV then | |
if jLsxpw<2048 then AXNfV=7 elseif jLsxpw>65536 then AXNfV=3 else AXNfV=5 end end | |
while not IcsJ do | |
if not A then A=1 | |
Wp9xT=64*1024-1;x=0 else A=Wp9xT+1;Wp9xT=Wp9xT+32*1024;x=A-32*1024-1 end;if Wp9xT>=jLsxpw then Wp9xT=jLsxpw;IcsJ=true else IcsJ=false end | |
local iyx,bxvn,mWYrzB,O7kX,Q4XSpdY,fzTyrQ9F;local fAumJ0i,i0,tZliF4,jlmopoj,R,uS_N6,o5SLRA,ztwXaCR,M2WtMgiq,FgfME,ylH9o;local CC4Kfjh;local k;local eUQ0x | |
if AXNfV~=0 then | |
VcV0EuD(XZt7GyF,D4,A,Wp9xT+3,x) | |
if A==1 and Zn3SC then local pYHkv=Zn3SC.string_table;local hxZHlgP=Zn3SC.strlen;for zct=0, | |
(-hxZHlgP+1)<-257 and-257 or(-hxZHlgP+1),-1 do D4[zct]=pYHkv[ | |
hxZHlgP+zct]end end | |
if cX=="huffman_only"then iyx={}VcV0EuD(XZt7GyF,iyx,A,Wp9xT,A-1)bxvn={} | |
mWYrzB={}iyx[Wp9xT-A+2]=256 | |
for WQk6Wkd=1,Wp9xT-A+2 do local t=iyx[WQk6Wkd]mWYrzB[t]=( | |
mWYrzB[t]or 0)+1 end;O7kX={}Q4XSpdY={}fzTyrQ9F={}else | |
iyx,bxvn,mWYrzB,O7kX,Q4XSpdY,fzTyrQ9F=pX4gCR(AXNfV,D4,crA9EKx,A,Wp9xT,x,Zn3SC)end | |
fAumJ0i,i0,tZliF4,jlmopoj,R,uS_N6,o5SLRA,ztwXaCR,M2WtMgiq,FgfME,ylH9o=gad4ZcL(mWYrzB,fzTyrQ9F)CC4Kfjh=dk(iyx,O7kX,tZliF4,jlmopoj,uS_N6,ztwXaCR,FgfME) | |
k=OO(iyx,O7kX)end;eUQ0x=cR6rJlAl(A,Wp9xT,o0_XG8FI)local r0OR=eUQ0x;r0OR= | |
(k and k<r0OR)and k or r0OR;r0OR=(CC4Kfjh and CC4Kfjh<r0OR)and | |
CC4Kfjh or r0OR | |
if AXNfV==0 or | |
( | |
cX~="fixed"and cX~="dynamic"and eUQ0x==r0OR)then | |
M6ilzGJ(yliV8,rjpKFl,IcsJ,XZt7GyF,A,Wp9xT,o0_XG8FI)o0_XG8FI=o0_XG8FI+eUQ0x elseif cX~="dynamic"and | |
(cX=="fixed"or k==r0OR)then y(yliV8,IcsJ,iyx,bxvn,O7kX,Q4XSpdY)o0_XG8FI= | |
o0_XG8FI+k elseif cX=="dynamic"or CC4Kfjh==r0OR then | |
E(yliV8,IcsJ,iyx,bxvn,O7kX,Q4XSpdY,fAumJ0i,i0,tZliF4,jlmopoj,R,uS_N6,o5SLRA,ztwXaCR,M2WtMgiq,FgfME,ylH9o)o0_XG8FI=o0_XG8FI+CC4Kfjh end;if IcsJ then P=YUGQovw(GI2hz6SK)else P=YUGQovw(WQ6)end;s(P== | |
o0_XG8FI) | |
if not IcsJ then local pRCHPl | |
if Zn3SC and A==1 then pRCHPl=0;while(D4[pRCHPl])do D4[pRCHPl]= | |
nil;pRCHPl=pRCHPl-1 end end;Zn3SC=nil;pRCHPl=1;for sCffg4HK=Wp9xT-32767,Wp9xT do D4[pRCHPl]=D4[sCffg4HK-x] | |
pRCHPl=pRCHPl+1 end | |
for EyljhkFp,uGDn542 in LfEJbh_(crA9EKx)do local DQ=#uGDn542 | |
if DQ>0 and | |
Wp9xT+1-uGDn542[1]>32768 then | |
if DQ==1 then | |
crA9EKx[EyljhkFp]=nil else local s6Ahlni_={}local T6dNu=0 | |
for H=2,DQ do pRCHPl=uGDn542[H]if Wp9xT+1-pRCHPl<=32768 then | |
T6dNu=T6dNu+1;s6Ahlni_[T6dNu]=pRCHPl end end;crA9EKx[EyljhkFp]=s6Ahlni_ end end end end end end | |
local function wZdg(YlzZm,vj9879b5,cotcYZ1f)local FRcmT,zfl,itxD=Oh() | |
iW6CD(cotcYZ1f,FRcmT,zfl,itxD,YlzZm,vj9879b5)local JPHs7A,yzYgnMtr=itxD(y36Aetn)local o=(8-JPHs7A%8)%8 | |
return yzYgnMtr,o end | |
local function BaX(wmkJ,I1,gXu5hG)local R60Ru4bj,eQWRf,WT2AX=Oh()local _AvO=8;local qEO=7;local q=qEO*16+_AvO;R60Ru4bj(q,8)local WUY7= | |
I1 and 1 or 0;local _puepou=2;local DYLeJ=_puepou*64+WUY7*32;local udbF=(31- (q*256+ | |
DYLeJ)%31) | |
DYLeJ=DYLeJ+udbF;R60Ru4bj(DYLeJ,8) | |
if WUY7 ==1 then local IPPy=I1.adler32;local zYGA2q2=IPPy%256;IPPy= | |
(IPPy-zYGA2q2)/256;local I9Mw=IPPy%256;IPPy=(IPPy-I9Mw)/256;local e= | |
IPPy%256;IPPy=(IPPy-e)/256;local BUtIET=IPPy%256 | |
R60Ru4bj(BUtIET,8)R60Ru4bj(e,8)R60Ru4bj(I9Mw,8)R60Ru4bj(zYGA2q2,8)end;iW6CD(gXu5hG,R60Ru4bj,eQWRf,WT2AX,wmkJ,I1) | |
WT2AX(iPL3B4cr)local dt1=JtAjijkG:Adler32(wmkJ)local V7eMEiVW=dt1%256;dt1= | |
(dt1-V7eMEiVW)/256;local Co1tUVas=dt1%256 | |
dt1=(dt1-Co1tUVas)/256;local B=dt1%256;dt1=(dt1-B)/256;local UjlBMb=dt1%256 | |
R60Ru4bj(UjlBMb,8)R60Ru4bj(B,8)R60Ru4bj(Co1tUVas,8)R60Ru4bj(V7eMEiVW,8) | |
local PKWIJ9,rQYWEt=WT2AX(y36Aetn)local nCwsa=(8-PKWIJ9%8)%8;return rQYWEt,nCwsa end | |
function JtAjijkG:CompressDeflate(NvAj,Icg)local PzMsk,axLuO=ykRppH(NvAj,false,nil,true,Icg)if | |
not PzMsk then | |
YAtG_LV3(("Usage: LibDeflate:CompressDeflate(str, configs): "..axLuO),2)end;return wZdg(NvAj,nil,Icg)end | |
function JtAjijkG:CompressDeflateWithDict(j,As,JmCzKm)local Mwhc,A6z=ykRppH(j,true,As,true,JmCzKm)if not Mwhc then | |
YAtG_LV3(( | |
"Usage: LibDeflate:CompressDeflateWithDict".."(str, dictionary, configs): "..A6z),2)end | |
return wZdg(j,As,JmCzKm)end | |
function JtAjijkG:CompressZlib(_Mk,PXrrrSid)local L9,_KZPScl=ykRppH(_Mk,false,nil,true,PXrrrSid)if | |
not L9 then | |
YAtG_LV3(("Usage: LibDeflate:CompressZlib(str, configs): ".._KZPScl),2)end | |
return BaX(_Mk,nil,PXrrrSid)end | |
function JtAjijkG:CompressZlibWithDict(dbTwy,R4f819q,Kj1I) | |
local nTUMgqomA,Id5sIM=ykRppH(dbTwy,true,R4f819q,true,Kj1I)if not nTUMgqomA then | |
YAtG_LV3(("Usage: LibDeflate:CompressZlibWithDict".."(str, dictionary, configs): "..Id5sIM),2)end;return | |
BaX(dbTwy,R4f819q,Kj1I)end | |
local function SJsW11k(gZM2ANLt)local aC72qEnu=gZM2ANLt;local B60J=#gZM2ANLt;local Y4=1;local f=0;local yeCnvcd6=0 | |
local function Iq93c6cA(m54tY2) | |
local WJWMdKI=RSjapQ[m54tY2]local AhbP | |
if m54tY2 <=f then AhbP=yeCnvcd6%WJWMdKI | |
yeCnvcd6=(yeCnvcd6-AhbP)/WJWMdKI;f=f-m54tY2 else local QHFgYUN=RSjapQ[f] | |
local RoEsr7So,dX,Rz,j177r=JD(aC72qEnu,Y4,Y4+3) | |
yeCnvcd6=yeCnvcd6+ | |
((RoEsr7So or 0)+ (dX or 0)*256+ | |
(Rz or 0)*65536+ (j177r or 0)*16777216)*QHFgYUN;Y4=Y4+4;f=f+32-m54tY2;AhbP=yeCnvcd6%WJWMdKI;yeCnvcd6= | |
(yeCnvcd6-AhbP)/WJWMdKI end;return AhbP end | |
local function nsM0h(j,qCaFw,syvPi)s(f%8 ==0)local NrgSK2=(f/8 <j)and(f/8)or j | |
for wIH=1,NrgSK2 do local TYWkpc=yeCnvcd6% | |
256;syvPi=syvPi+1;qCaFw[syvPi]=u(TYWkpc)yeCnvcd6=(yeCnvcd6- | |
TYWkpc)/256 end;f=f-NrgSK2*8;j=j-NrgSK2;if | |
(B60J-Y4-j+1)*8+f<0 then return-1 end;for k=Y4,Y4+j-1 do syvPi=syvPi+1 | |
qCaFw[syvPi]=XxJ(aC72qEnu,k,k)end;Y4=Y4+j;return syvPi end | |
local function Czi(J,gtlO9,Lun)local beUJXhjw=0;local zY7adu=0;local Nlvw=0;local K55 | |
if Lun>0 then | |
if f<15 and aC72qEnu then local f1MKKJ=RSjapQ[f] | |
local nFf,EIqL41,iv,rfmMR4=JD(aC72qEnu,Y4,Y4+3) | |
yeCnvcd6=yeCnvcd6+ | |
((nFf or 0)+ (EIqL41 or 0)*256+ | |
(iv or 0)*65536+ (rfmMR4 or 0)*16777216)*f1MKKJ;Y4=Y4+4;f=f+32 end;local BJcMTdMi=RSjapQ[Lun]f=f-Lun;beUJXhjw=yeCnvcd6%BJcMTdMi;yeCnvcd6=(yeCnvcd6- | |
beUJXhjw)/BJcMTdMi | |
beUJXhjw=zC[Lun][beUJXhjw]K55=J[Lun]if beUJXhjw<K55 then return gtlO9[beUJXhjw]end | |
Nlvw=K55;zY7adu=K55*2;beUJXhjw=beUJXhjw*2 end | |
for Tq2I=Lun+1,15 do local GNo;GNo=yeCnvcd6%2;yeCnvcd6=(yeCnvcd6-GNo)/2 | |
f=f-1 | |
beUJXhjw=(GNo==1)and(beUJXhjw+1-beUJXhjw%2)or beUJXhjw;K55=J[Tq2I]or 0;local e5x=beUJXhjw-zY7adu;if e5x<K55 then | |
return gtlO9[Nlvw+e5x]end;Nlvw=Nlvw+K55;zY7adu=zY7adu+K55 | |
zY7adu=zY7adu*2;beUJXhjw=beUJXhjw*2 end;return-10 end;local function IlxN()return(B60J-Y4+1)*8+f end | |
local function EA_3x01A() | |
local QrONvWGq=f%8;local D94fnZaa=RSjapQ[QrONvWGq]f=f-QrONvWGq;yeCnvcd6= | |
(yeCnvcd6-yeCnvcd6%D94fnZaa)/D94fnZaa end;return Iq93c6cA,nsM0h,Czi,IlxN,EA_3x01A end | |
local function Ki1HJT(XI,FNi)local pRW2nEmK,OR,Arww,BYH,o7E8TLH=SJsW11k(XI) | |
local N5N27Jd={ReadBits=pRW2nEmK,ReadBytes=OR,Decode=Arww,ReaderBitlenLeft=BYH,SkipToByteBoundary=o7E8TLH,buffer_size=0,buffer={},result_buffer={},dictionary=FNi}return N5N27Jd end | |
local function wjim8xCV(m,nK,_zr)local f5={}local UAc=_zr | |
for GYVN=0,nK do local DNlB1V=m[GYVN]or 0;UAc= | |
(DNlB1V>0 and DNlB1V<UAc)and DNlB1V or UAc;f5[DNlB1V]=( | |
f5[DNlB1V]or 0)+1 end;if f5[0]==nK+1 then return 0,f5,{},0 end;local Ef=1 | |
for erb6G_E=1,_zr do Ef=Ef*2;Ef=Ef- | |
(f5[erb6G_E]or 0)if Ef<0 then return Ef end end;local P={}P[1]=0;for QFUU10K=1,_zr-1 do | |
P[QFUU10K+1]=P[QFUU10K]+ (f5[QFUU10K]or 0)end;local F4AWvI={}for xNPDtul=0,nK do local k8=m[xNPDtul]or 0 | |
if | |
k8 ~=0 then local HmgRk=P[k8]F4AWvI[HmgRk]=xNPDtul;P[k8]=P[k8]+1 end end | |
return Ef,f5,F4AWvI,UAc end | |
local function EQLam(UuCdpVi,fghe,vFXf,CA0uX7n,ze5Vpc3,vwK8,Sk_SiC) | |
local X0bgPvA,M9CyqH,z0x4qSAN,X0GTupeV,rQ,k=UuCdpVi.buffer,UuCdpVi.buffer_size,UuCdpVi.ReadBits,UuCdpVi.Decode,UuCdpVi.ReaderBitlenLeft,UuCdpVi.result_buffer;local Oc=UuCdpVi.dictionary;local IHovU;local e_wDQjk;local ClglY=1 | |
if Oc and not X0bgPvA[0]then | |
IHovU=Oc.string_table;e_wDQjk=Oc.strlen;ClglY=-e_wDQjk+1;for S=0,(-e_wDQjk+1)<-257 and | |
-257 or(-e_wDQjk+1),-1 do | |
X0bgPvA[S]=QJf[IHovU[e_wDQjk+S]]end end | |
repeat local NKetZhs=X0GTupeV(fghe,vFXf,CA0uX7n) | |
if | |
NKetZhs<0 or NKetZhs>285 then return-10 elseif NKetZhs<256 then M9CyqH=M9CyqH+1;X0bgPvA[M9CyqH]=QJf[NKetZhs]elseif | |
NKetZhs>256 then NKetZhs=NKetZhs-256;local EFLZ0N1=el[NKetZhs]EFLZ0N1= | |
(NKetZhs>=8)and( | |
EFLZ0N1+z0x4qSAN(Wu_uIt[NKetZhs]))or EFLZ0N1 | |
NKetZhs=X0GTupeV(ze5Vpc3,vwK8,Sk_SiC)if NKetZhs<0 or NKetZhs>29 then return-10 end | |
local gL=w[NKetZhs]gL= | |
(gL>4)and(gL+z0x4qSAN(sgeP[NKetZhs]))or gL;local m4=M9CyqH-gL+1;if | |
m4 <ClglY then return-11 end | |
if m4 >=-257 then for rNOL8G=1,EFLZ0N1 do M9CyqH=M9CyqH+1 | |
X0bgPvA[M9CyqH]=X0bgPvA[m4]m4=m4+1 end else m4=e_wDQjk+m4 | |
for q=1,EFLZ0N1 do | |
M9CyqH=M9CyqH+1;X0bgPvA[M9CyqH]=QJf[IHovU[m4]]m4=m4+1 end end end;if rQ()<0 then return 2 end | |
if M9CyqH>=65536 then | |
k[#k+1]=o5sms(X0bgPvA,"",1,32768) | |
for lKO=32769,M9CyqH do X0bgPvA[lKO-32768]=X0bgPvA[lKO]end;M9CyqH=M9CyqH-32768;X0bgPvA[M9CyqH+1]=nil end until NKetZhs==256;UuCdpVi.buffer_size=M9CyqH;return 0 end | |
local function qTDt(hcwgu) | |
local omgCdqp8,X17eHTx,SGF,myIHU,xxNCdF,_cl1b,Xz18nk=hcwgu.buffer,hcwgu.buffer_size,hcwgu.ReadBits,hcwgu.ReadBytes,hcwgu.ReaderBitlenLeft,hcwgu.SkipToByteBoundary,hcwgu.result_buffer;_cl1b()local P=SGF(16)if xxNCdF()<0 then return 2 end;local sTX4=SGF(16)if | |
xxNCdF()<0 then return 2 end | |
if P%256+sTX4%256 ~=255 then return-2 end;if | |
(P-P%256)/256+ (sTX4-sTX4%256)/256 ~=255 then return-2 end | |
X17eHTx=myIHU(P,omgCdqp8,X17eHTx)if X17eHTx<0 then return 2 end | |
if X17eHTx>=65536 then | |
Xz18nk[#Xz18nk+1]=o5sms(omgCdqp8,"",1,32768) | |
for A0TJx=32769,X17eHTx do omgCdqp8[A0TJx-32768]=omgCdqp8[A0TJx]end;X17eHTx=X17eHTx-32768;omgCdqp8[X17eHTx+1]=nil end;hcwgu.buffer_size=X17eHTx;return 0 end | |
local function v(Nqdkw)return EQLam(Nqdkw,hw18,_,7,rDtVf,xSebv5Jc,5)end | |
local function Ta(t)local QbMO,wYZ=t.ReadBits,t.Decode;local aMd=QbMO(5)+257;local o0pf=QbMO(5)+1;local tx1LD= | |
QbMO(4)+4;if aMd>286 or o0pf>30 then return-3 end;local N3ROeR={}for LOBqxO=1,tx1LD do | |
N3ROeR[CM[LOBqxO]]=QbMO(3)end;local I1oQVnUd,oTX,WZlF4,IxqPDOWH=wjim8xCV(N3ROeR,18,7)if | |
I1oQVnUd~=0 then return-4 end;local GZqV={}local OVubrDw_={}local G2_TeR8=0 | |
while G2_TeR8 <aMd+o0pf do | |
local m8;local mcoAHO;m8=wYZ(oTX,WZlF4,IxqPDOWH) | |
if m8 <0 then return m8 elseif m8 <16 then if G2_TeR8 <aMd then | |
GZqV[G2_TeR8]=m8 else OVubrDw_[G2_TeR8-aMd]=m8 end;G2_TeR8= | |
G2_TeR8+1 else mcoAHO=0 | |
if m8 ==16 then if G2_TeR8 ==0 then return-5 end;if | |
G2_TeR8-1 <aMd then mcoAHO=GZqV[G2_TeR8-1]else | |
mcoAHO=OVubrDw_[G2_TeR8-aMd-1]end;m8=3+QbMO(2)elseif m8 ==17 then | |
m8=3+QbMO(3)else m8=11+QbMO(7)end;if G2_TeR8+m8 >aMd+o0pf then return-6 end | |
while m8 >0 do m8=m8-1 | |
if | |
G2_TeR8 <aMd then GZqV[G2_TeR8]=mcoAHO else OVubrDw_[G2_TeR8-aMd]=mcoAHO end;G2_TeR8=G2_TeR8+1 end end end;if(GZqV[256]or 0)==0 then return-9 end | |
local yk,OPSPMfr_,QnNOl,aQs=wjim8xCV(GZqV,aMd-1,15)if | |
(yk~=0 and(yk<0 or aMd~= | |
(OPSPMfr_[0]or 0)+ (OPSPMfr_[1]or 0)))then return-7 end | |
local uow_0tb,tykg,C_pPyW,mgb4b=wjim8xCV(OVubrDw_,o0pf-1,15)if | |
(uow_0tb~=0 and(uow_0tb<0 or | |
o0pf~= (tykg[0]or 0)+ (tykg[1]or 0)))then return-8 end;return | |
EQLam(t,OPSPMfr_,QnNOl,aQs,tykg,C_pPyW,mgb4b)end | |
local function unArcvQl(d3gFWO)local D=d3gFWO.ReadBits;local obodPKnu | |
while not obodPKnu do obodPKnu=(D(1)==1)local oVSp=D(2) | |
local uBJ;if oVSp==0 then uBJ=qTDt(d3gFWO)elseif oVSp==1 then uBJ=v(d3gFWO)elseif oVSp==2 then uBJ=Ta(d3gFWO)else | |
return nil,-1 end;if uBJ~=0 then | |
return nil,uBJ end end | |
d3gFWO.result_buffer[#d3gFWO.result_buffer+1]=o5sms(d3gFWO.buffer,"",1,d3gFWO.buffer_size)local kgdzk=o5sms(d3gFWO.result_buffer)return kgdzk end | |
local function h6Ub7U(A,MP)local jb=Ki1HJT(A,MP)local uKSj,YXgXQB=unArcvQl(jb) | |
if not uKSj then return nil,YXgXQB end;local bvL1X4=jb.ReaderBitlenLeft() | |
local PPNahh=(bvL1X4-bvL1X4%8)/8;return uKSj,PPNahh end | |
local function Gm(z2g,m9JTkVv6)local Q=Ki1HJT(z2g,m9JTkVv6)local bWkP=Q.ReadBits;local JtFj=bWkP(8)if | |
Q.ReaderBitlenLeft()<0 then return nil,2 end;local PQ3=JtFj%16 | |
local _xCtN=(JtFj-PQ3)/16;if PQ3 ~=8 then return nil,-12 end;if _xCtN>7 then return nil,-13 end | |
local JVpe=bWkP(8)if Q.ReaderBitlenLeft()<0 then return nil,2 end;if | |
(JtFj*256+JVpe)%31 ~=0 then return nil,-14 end;local nG36XmZC=( | |
(JVpe-JVpe%32)/32%2)local Vf26=( | |
(JVpe-JVpe%64)/64%4) | |
if nG36XmZC==1 then | |
if not m9JTkVv6 then return nil,-16 end;local I7=bWkP(8)local Upw=bWkP(8)local nqBfKL=bWkP(8)local gs3a=bWkP(8) | |
local AkKaBC=I7*16777216+ | |
Upw*65536+nqBfKL*256+gs3a;if Q.ReaderBitlenLeft()<0 then return nil,2 end;if not | |
vj(AkKaBC,m9JTkVv6.adler32)then return nil,-17 end end;local xUGt,_U=unArcvQl(Q)if not xUGt then return nil,_U end | |
Q.SkipToByteBoundary()local hkI39=bWkP(8)local MwwN=bWkP(8)local oZ9=bWkP(8)local OXlT0=bWkP(8)if | |
Q.ReaderBitlenLeft()<0 then return nil,2 end;local V= | |
hkI39*16777216+MwwN*65536+oZ9*256+OXlT0 | |
local zIYNIXy1=JtAjijkG:Adler32(xUGt)if not vj(V,zIYNIXy1)then return nil,-15 end | |
local c=Q.ReaderBitlenLeft()local mReHt4h=(c-c%8)/8;return xUGt,mReHt4h end | |
function JtAjijkG:DecompressDeflate(OmRH8)local GY,oukM79R=ykRppH(OmRH8)if not GY then | |
YAtG_LV3(("Usage: LibDeflate:DecompressDeflate(str): ".. | |
oukM79R),2)end;return h6Ub7U(OmRH8)end | |
function JtAjijkG:DecompressDeflateWithDict(D_j,mZPe4w)local OvZ,cBOpf=ykRppH(D_j,true,mZPe4w)if not OvZ then | |
YAtG_LV3(( | |
"Usage: LibDeflate:DecompressDeflateWithDict(str, dictionary): "..cBOpf),2)end | |
return h6Ub7U(D_j,mZPe4w)end | |
function JtAjijkG:DecompressZlib(KZYA5y)local YoCAN7OU,FoP=ykRppH(KZYA5y)if not YoCAN7OU then | |
YAtG_LV3(( | |
"Usage: LibDeflate:DecompressZlib(str): "..FoP),2)end;return Gm(KZYA5y)end | |
function JtAjijkG:DecompressZlibWithDict(jqtWXY,XgRb)local G3e,GoP6=ykRppH(jqtWXY,true,XgRb)if not G3e then | |
YAtG_LV3(( | |
"Usage: LibDeflate:DecompressZlibWithDict(str, dictionary): "..GoP6),2)end;return Gm(jqtWXY,XgRb)end | |
do RkGFh6={}for NYc8=0,143 do RkGFh6[NYc8]=8 end | |
for Dff8=144,255 do RkGFh6[Dff8]=9 end;for lEYwsOG9=256,279 do RkGFh6[lEYwsOG9]=7 end | |
for M=280,287 do RkGFh6[M]=8 end;mMp={}for Vt95q2G=0,31 do mMp[Vt95q2G]=5 end;local cZ_ | |
cZ_,hw18,_=wjim8xCV(RkGFh6,287,9)s(cZ_==0)cZ_,rDtVf,xSebv5Jc=wjim8xCV(mMp,31,5)s(cZ_==0) | |
Qlmlet=O(hw18,RkGFh6,287,9)nvCiFt7r=O(rDtVf,mMp,31,5)end;return JtAjijkG |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment