L9pjaDJW

1print("Loading installer...")
2--[[--
3LibDeflate 1.0.0-release <br>
4Pure Lua compressor and decompressor with high compression ratio using
5DEFLATE/zlib format.
6
7@file LibDeflate.lua
8@author Haoqian He (Github: SafeteeWoW; World of Warcraft: Safetyy-Illidan(US))
9@copyright LibDeflate <2018> Haoqian He
10@license GNU General Public License Version 3 or later
11
12This library is implemented according to the following specifications. <br>
13Report a bug if LibDeflate is not fully compliant with those specs. <br>
14Both compressors and decompressors have been implemented in the library.<br>
151. RFC1950: DEFLATE Compressed Data Format Specification version 1.3 <br>
16https://tools.ietf.org/html/rfc1951 <br>
172. RFC1951: ZLIB Compressed Data Format Specification version 3.3 <br>
18https://tools.ietf.org/html/rfc1950 <br>
19
20This library requires Lua 5.1/5.2/5.3 interpreter or LuaJIT v2.0+. <br>
21This library does not have any dependencies. <br>
22<br>
23This file "LibDeflate.lua" is the only source file of
24the library. <br>
25Submit suggestions or report bugs to
26https://github.com/safeteeWow/LibDeflate/issues
27]]
28
29--[[
30This program is free software: you can redistribute it and/or modify
31it under the terms of the GNU General Public License as published by
32the Free Software Foundation, either version 3 of the License, or
33any later version.
34
35This program is distributed in the hope that it will be useful,
36but WITHOUT ANY WARRANTY; without even the implied warranty of
37MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
38GNU General Public License for more details.
39
40You should have received a copy of the GNU General Public License
41along with this program.  If not, see https://www.gnu.org/licenses/.
42
43Credits:
441. zlib, by Jean-loup Gailly (compression) and Mark Adler (decompression).
45	http://www.zlib.net/
46	Licensed under zlib License. http://www.zlib.net/zlib_license.html
47	For the compression algorithm.
482. puff, by Mark Adler. https://github.com/madler/zlib/tree/master/contrib/puff
49	Licensed under zlib License. http://www.zlib.net/zlib_license.html
50	For the decompression algorithm.
513. LibCompress, by jjsheets and Galmok of European Stormrage (Horde)
52	https://www.wowace.com/projects/libcompress
53	Licensed under GPLv2.
54	https://www.gnu.org/licenses/old-licenses/gpl-2.0.html
55	For the code to create customized codec.
564. WeakAuras2,
57	https://github.com/WeakAuras/WeakAuras2
58	Licensed under GPLv2.
59	For the 6bit encoding and decoding.
60]]
61
62--[[
63	Curseforge auto-packaging replacements:
64
65	Project Date: @project-date-iso@
66	Project Hash: @project-hash@
67	Project Version: @project-version@
68--]]
69
70local LibDeflate
71
72do
73	-- Semantic version. all lowercase.
74	-- Suffix can be alpha1, alpha2, beta1, beta2, rc1, rc2, etc.
75	-- NOTE: Two version numbers needs to modify.
76	-- 1. On the top of LibDeflate.lua
77	-- 2. HERE
78	local _VERSION = "1.0.0-release"
79
80	local _COPYRIGHT =
81	"LibDeflate ".._VERSION
82	.." Copyright (C) 2018 Haoqian He."
83	.." License GPLv3+: GNU GPL version 3 or later"
84
85	-- Register in the World of Warcraft library "LibStub" if detected.
86	if LibStub then
87		local MAJOR, MINOR = "LibDeflate", -1
88		-- When MAJOR is changed, I should name it as LibDeflate2
89		local lib, minor = LibStub:GetLibrary(MAJOR, true)
90		if lib and minor and minor >= MINOR then -- No need to update.
91			return lib
92		else -- Update or first time register
93			LibDeflate = LibStub:NewLibrary(MAJOR, _VERSION)
94			-- NOTE: It is important that new version has implemented
95			-- all exported APIs and tables in the old version,
96			-- so the old library is fully garbage collected,
97			-- and we 100% ensure the backward compatibility.
98		end
99	else -- "LibStub" is not detected.
100		LibDeflate = {}
101	end
102
103	LibDeflate._VERSION = _VERSION
104	LibDeflate._COPYRIGHT = _COPYRIGHT
105end
106
107-- localize Lua api for faster access.
108local assert = assert
109local error = error
110local pairs = pairs
111local string_byte = string.byte
112local string_char = string.char
113local string_find = string.find
114local string_gsub = string.gsub
115local string_sub = string.sub
116local table_concat = table.concat
117local table_sort = table.sort
118local tostring = tostring
119local type = type
120
121-- Converts i to 2^i, (0<=i<=32)
122-- This is used to implement bit left shift and bit right shift.
123-- "x >> y" in C:   "(x-x%_pow2[y])/_pow2[y]" in Lua
124-- "x << y" in C:   "x*_pow2[y]" in Lua
125local _pow2 = {}
126
127-- Converts any byte to a character, (0<=byte<=255)
128local _byte_to_char = {}
129
130-- _reverseBitsTbl[len][val] stores the bit reverse of
131-- the number with bit length "len" and value "val"
132-- For example, decimal number 6 with bits length 5 is binary 00110
133-- It's reverse is binary 01100,
134-- which is decimal 12 and 12 == _reverseBitsTbl[5][6]
135-- 1<=len<=9, 0<=val<=2^len-1
136-- The reason for 1<=len<=9 is that the max of min bitlen of huffman code
137-- of a huffman alphabet is 9?
138local _reverse_bits_tbl = {}
139
140-- Convert a LZ77 length (3<=len<=258) to
141-- a deflate literal/LZ77_length code (257<=code<=285)
142local _length_to_deflate_code = {}
143
144-- convert a LZ77 length (3<=len<=258) to
145-- a deflate literal/LZ77_length code extra bits.
146local _length_to_deflate_extra_bits = {}
147
148-- Convert a LZ77 length (3<=len<=258) to
149-- a deflate literal/LZ77_length code extra bit length.
150local _length_to_deflate_extra_bitlen = {}
151
152-- Convert a small LZ77 distance (1<=dist<=256) to a deflate code.
153local _dist256_to_deflate_code = {}
154
155-- Convert a small LZ77 distance (1<=dist<=256) to
156-- a deflate distance code extra bits.
157local _dist256_to_deflate_extra_bits = {}
158
159-- Convert a small LZ77 distance (1<=dist<=256) to
160-- a deflate distance code extra bit length.
161local _dist256_to_deflate_extra_bitlen = {}
162
163-- Convert a literal/LZ77_length deflate code to LZ77 base length
164-- The key of the table is (code - 256), 257<=code<=285
165local _literal_deflate_code_to_base_len = {
166	3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
167	35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258,
168}
169
170-- Convert a literal/LZ77_length deflate code to base LZ77 length extra bits
171-- The key of the table is (code - 256), 257<=code<=285
172local _literal_deflate_code_to_extra_bitlen = {
173	0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
174	3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0,
175}
176
177-- Convert a distance deflate code to base LZ77 distance. (0<=code<=29)
178local _dist_deflate_code_to_base_dist = {
179	[0] = 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
180	257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
181	8193, 12289, 16385, 24577,
182}
183
184-- Convert a distance deflate code to LZ77 bits length. (0<=code<=29)
185local _dist_deflate_code_to_extra_bitlen = {
186	[0] = 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
187	7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13,
188}
189
190-- The code order of the first huffman header in the dynamic deflate block.
191-- See the page 12 of RFC1951
192local _rle_codes_huffman_bitlen_order = {16, 17, 18,
193	0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15,
194}
195
196-- The following tables are used by fixed deflate block.
197-- The value of these tables are assigned at the bottom of the source.
198
199-- The huffman code of the literal/LZ77_length deflate codes,
200-- in fixed deflate block.
201local _fix_block_literal_huffman_code
202
203-- Convert huffman code of the literal/LZ77_length to deflate codes,
204-- in fixed deflate block.
205local _fix_block_literal_huffman_to_deflate_code
206
207-- The bit length of the huffman code of literal/LZ77_length deflate codes,
208-- in fixed deflate block.
209local _fix_block_literal_huffman_bitlen
210
211-- The count of each bit length of the literal/LZ77_length deflate codes,
212-- in fixed deflate block.
213local _fix_block_literal_huffman_bitlen_count
214
215-- The huffman code of the distance deflate codes,
216-- in fixed deflate block.
217local _fix_block_dist_huffman_code
218
219-- Convert huffman code of the distance to deflate codes,
220-- in fixed deflate block.
221local _fix_block_dist_huffman_to_deflate_code
222
223-- The bit length of the huffman code of the distance deflate codes,
224-- in fixed deflate block.
225local _fix_block_dist_huffman_bitlen
226
227-- The count of each bit length of the huffman code of
228-- the distance deflate codes,
229-- in fixed deflate block.
230local _fix_block_dist_huffman_bitlen_count
231
232for i = 0, 255 do
233	_byte_to_char[i] = string_char(i)
234end
235
236do
237	local pow = 1
238	for i = 0, 32 do
239		_pow2[i] = pow
240		pow = pow * 2
241	end
242end
243
244for i = 1, 9 do
245	_reverse_bits_tbl[i] = {}
246	for j=0, _pow2[i+1]-1 do
247		local reverse = 0
248		local value = j
249		for _ = 1, i do
250			-- The following line is equivalent to "res | (code %2)" in C.
251			reverse = reverse - reverse%2
252				+ (((reverse%2==1) or (value % 2) == 1) and 1 or 0)
253			value = (value-value%2)/2
254			reverse = reverse * 2
255		end
256		_reverse_bits_tbl[i][j] = (reverse-reverse%2)/2
257	end
258end
259
260-- The source code is written according to the pattern in the numbers
261-- in RFC1951 Page10.
262do
263	local a = 18
264	local b = 16
265	local c = 265
266	local bitlen = 1
267	for len = 3, 258 do
268		if len <= 10 then
269			_length_to_deflate_code[len] = len + 254
270			_length_to_deflate_extra_bitlen[len] = 0
271		elseif len == 258 then
272			_length_to_deflate_code[len] = 285
273			_length_to_deflate_extra_bitlen[len] = 0
274		else
275			if len > a then
276				a = a + b
277				b = b * 2
278				c = c + 4
279				bitlen = bitlen + 1
280			end
281			local t = len-a-1+b/2
282			_length_to_deflate_code[len] = (t-(t%(b/8)))/(b/8) + c
283			_length_to_deflate_extra_bitlen[len] = bitlen
284			_length_to_deflate_extra_bits[len] = t % (b/8)
285		end
286	end
287end
288
289-- The source code is written according to the pattern in the numbers
290-- in RFC1951 Page11.
291do
292	_dist256_to_deflate_code[1] = 0
293	_dist256_to_deflate_code[2] = 1
294	_dist256_to_deflate_extra_bitlen[1] = 0
295	_dist256_to_deflate_extra_bitlen[2] = 0
296
297	local a = 3
298	local b = 4
299	local code = 2
300	local bitlen = 0
301	for dist = 3, 256 do
302		if dist > b then
303			a = a * 2
304			b = b * 2
305			code = code + 2
306			bitlen = bitlen + 1
307		end
308		_dist256_to_deflate_code[dist] = (dist <= a) and code or (code+1)
309		_dist256_to_deflate_extra_bitlen[dist] = (bitlen < 0) and 0 or bitlen
310		if b >= 8 then
311			_dist256_to_deflate_extra_bits[dist] = (dist-b/2-1) % (b/4)
312		end
313	end
314end
315
316-- CRC-16/CRC-32 computation
317local xor
318
319if bit ~= nil then xor = bit.bxor
320elseif bit32 ~= nil then xor = bit32.bxor 
321else xor = function(a, b)
322    local calc = 0    
323
324    for i = 32, 0, -1 do
325        local val = 2 ^ i
326        local aa = false
327        local bb = false
328    
329        if a == 0 then
330            calc = calc + b
331            break
332        end
333    
334        if b == 0 then
335            calc = calc + a
336            break
337        end
338    
339        if a >= val then
340            aa = true
341            a = a - val
342        end
343    
344        if b >= val then
345            bb = true
346            b = b - val
347        end
348    
349        if not (aa and bb) and (aa or bb) then
350            calc = calc + val
351        end
352    end
353
354    return calc
355end end
356
357-- CRC-32-IEEE 802.3 (V.42)
358local POLY = 0xEDB88320
359
360-- Memoize function pattern (like http://lua-users.org/wiki/FuncTables ).
361local function memoize(f)
362  local mt = {}
363  local t = setmetatable({}, mt)
364  function mt:__index(k)
365    local v = f(k); t[k] = v
366    return v
367  end
368  return t
369end
370
371-- CRC table.
372local crc_table = memoize(function(i)
373  local crc = i
374  for _=1,8 do
375    local b = crc % 2 ~= 0 and 1 or 0
376    crc = math.floor(crc / 2)
377    if b == 1 then crc = xor(crc, POLY) end
378  end
379  return crc
380end)
381
382
383local function crc32_byte(byte, crc)
384  crc = xor(crc or 0, 0xFFFFFFFF)
385  local v1 = math.floor(crc / 256)
386  local v2 = crc_table[xor(crc % 256, byte)]
387  return xor(xor(v1, v2), 0xFFFFFFFF)
388end
389
390
391local function crc32_string(s, crc)
392  crc = crc or 0
393  for i=1,#s do
394    crc = crc32_byte(s:byte(i), crc)
395  end
396  return crc
397end
398
399--- Calculate the CRC-32 checksum of the string.
400-- @param s [string] the input string to calculate its CRC-32 checksum.
401-- @return [integer] The CRC-32 checksum, which is greater or equal to 0,
402-- and less than 2^32 (4294967296).
403function LibDeflate:CRC32(s, crc)
404  if type(s) == 'string' then
405    return crc32_string(s, crc)
406  else
407    return crc32_byte(s, crc)
408  end
409end
410
411--- Calculate the Adler-32 checksum of the string. <br>
412-- See RFC1950 Page 9 https://tools.ietf.org/html/rfc1950 for the
413-- definition of Adler-32 checksum.
414-- @param str [string] the input string to calcuate its Adler-32 checksum.
415-- @return [integer] The Adler-32 checksum, which is greater or equal to 0,
416-- and less than 2^32 (4294967296).
417function LibDeflate:Adler32(str)
418	-- This function is loop unrolled by better performance.
419	--
420	-- Here is the minimum code:
421	--
422	-- local a = 1
423	-- local b = 0
424	-- for i=1, #str do
425	-- 		local s = string.byte(str, i, i)
426	-- 		a = (a+s)%65521
427	-- 		b = (b+a)%65521
428	-- 		end
429	-- return b*65536+a
430	if type(str) ~= "string" then
431		error(("Usage: LibDeflate:Adler32(str):"
432			.." 'str' - string expected got '%s'."):format(type(str)), 2)
433	end
434	local strlen = #str
435
436	local i = 1
437	local a = 1
438	local b = 0
439	while i <= strlen - 15 do
440		local x1, x2, x3, x4, x5, x6, x7, x8,
441			x9, x10, x11, x12, x13, x14, x15, x16 = string_byte(str, i, i+15)
442		b = (b+16*a+16*x1+15*x2+14*x3+13*x4+12*x5+11*x6+10*x7+9*x8+8*x9
443			+7*x10+6*x11+5*x12+4*x13+3*x14+2*x15+x16)%65521
444		a = (a+x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16)%65521
445		i =  i + 16
446	end
447	while (i <= strlen) do
448		local x = string_byte(str, i, i)
449		a = (a + x) % 65521
450		b = (b + a) % 65521
451		i = i + 1
452	end
453	return (b*65536+a) % 4294967296
454end
455
456-- Compare adler32 checksum.
457-- adler32 should be compared with a mod to avoid sign problem
458-- 4072834167 (unsigned) is the same adler32 as -222133129
459local function IsEqualAdler32(actual, expected)
460	return (actual % 4294967296) == (expected % 4294967296)
461end
462
463--- Create a preset dictionary.
464--
465-- This function is not fast, and the memory consumption of the produced
466-- dictionary is about 50 times of the input string. Therefore, it is suggestted
467-- to run this function only once in your program.
468--
469-- It is very important to know that if you do use a preset dictionary,
470-- compressors and decompressors MUST USE THE SAME dictionary. That is,
471-- dictionary must be created using the same string. If you update your program
472-- with a new dictionary, people with the old version won't be able to transmit
473-- data with people with the new version. Therefore, changing the dictionary
474-- must be very careful.
475--
476-- The parameters "strlen" and "adler32" add a layer of verification to ensure
477-- the parameter "str" is not modified unintentionally during the program
478-- development.
479--
480-- @usage local dict_str = "1234567890"
481--
482-- -- print(dict_str:len(), LibDeflate:Adler32(dict_str))
483-- -- Hardcode the print result below to verify it to avoid acciently
484-- -- modification of 'str' during the program development.
485-- -- string length: 10, Adler-32: 187433486,
486-- -- Don't calculate string length and its Adler-32 at run-time.
487--
488-- local dict = LibDeflate:CreateDictionary(dict_str, 10, 187433486)
489--
490-- @param str [string] The string used as the preset dictionary. <br>
491-- You should put stuffs that frequently appears in the dictionary
492-- string and preferablely put more frequently appeared stuffs toward the end
493-- of the string. <br>
494-- Empty string and string longer than 32768 bytes are not allowed.
495-- @param strlen [integer] The length of 'str'. Please pass in this parameter
496-- as a hardcoded constant, in order to verify the content of 'str'. The value
497-- of this parameter should be known before your program runs.
498-- @param adler32 [integer] The Adler-32 checksum of 'str'. Please pass in this
499-- parameter as a hardcoded constant, in order to verify the content of 'str'.
500-- The value of this parameter should be known before your program runs.
501-- @return  [table] The dictionary used for preset dictionary compression and
502-- decompression.
503-- @raise error if 'strlen' does not match the length of 'str',
504-- or if 'adler32' does not match the Adler-32 checksum of 'str'.
505function LibDeflate:CreateDictionary(str, strlen, adler32)
506	if type(str) ~= "string" then
507		error(("Usage: LibDeflate:CreateDictionary(str, strlen, adler32):"
508			.." 'str' - string expected got '%s'."):format(type(str)), 2)
509	end
510	if type(strlen) ~= "number" then
511		error(("Usage: LibDeflate:CreateDictionary(str, strlen, adler32):"
512			.." 'strlen' - number expected got '%s'."):format(
513			type(strlen)), 2)
514	end
515	if type(adler32) ~= "number" then
516		error(("Usage: LibDeflate:CreateDictionary(str, strlen, adler32):"
517			.." 'adler32' - number expected got '%s'."):format(
518			type(adler32)), 2)
519	end
520	if strlen ~= #str then
521		error(("Usage: LibDeflate:CreateDictionary(str, strlen, adler32):"
522				.." 'strlen' does not match the actual length of 'str'."
523				.." 'strlen': %u, '#str': %u ."
524				.." Please check if 'str' is modified unintentionally.")
525			:format(strlen, #str))
526	end
527	if strlen == 0 then
528		error(("Usage: LibDeflate:CreateDictionary(str, strlen, adler32):"
529			.." 'str' - Empty string is not allowed."), 2)
530	end
531	if strlen > 32768 then
532		error(("Usage: LibDeflate:CreateDictionary(str, strlen, adler32):"
533			.." 'str' - string longer than 32768 bytes is not allowed."
534			 .." Got %d bytes."):format(strlen), 2)
535	end
536	local actual_adler32 = self:Adler32(str)
537	if not IsEqualAdler32(adler32, actual_adler32) then
538		error(("Usage: LibDeflate:CreateDictionary(str, strlen, adler32):"
539				.." 'adler32' does not match the actual adler32 of 'str'."
540				.." 'adler32': %u, 'Adler32(str)': %u ."
541				.." Please check if 'str' is modified unintentionally.")
542			:format(adler32, actual_adler32))
543	end
544
545	local dictionary = {}
546	dictionary.adler32 = adler32
547	dictionary.hash_tables = {}
548	dictionary.string_table = {}
549	dictionary.strlen = strlen
550	local string_table = dictionary.string_table
551	local hash_tables = dictionary.hash_tables
552	string_table[1] = string_byte(str, 1, 1)
553	string_table[2] = string_byte(str, 2, 2)
554	if strlen >= 3 then
555		local i = 1
556		local hash = string_table[1]*256+string_table[2]
557		while i <= strlen - 2 - 3 do
558			local x1, x2, x3, x4 = string_byte(str, i+2, i+5)
559			string_table[i+2] = x1
560			string_table[i+3] = x2
561			string_table[i+4] = x3
562			string_table[i+5] = x4
563			hash = (hash*256+x1)%16777216
564			local t = hash_tables[hash]
565			if not t then t = {}; hash_tables[hash] = t end
566			t[#t+1] = i-strlen
567			i = i + 1
568			hash = (hash*256+x2)%16777216
569			t = hash_tables[hash]
570			if not t then t = {}; hash_tables[hash] = t end
571			t[#t+1] = i-strlen
572			i = i + 1
573			hash = (hash*256+x3)%16777216
574			t = hash_tables[hash]
575			if not t then t = {}; hash_tables[hash] = t end
576			t[#t+1] = i-strlen
577			i = i + 1
578			hash = (hash*256+x4)%16777216
579			t = hash_tables[hash]
580			if not t then t = {}; hash_tables[hash] = t end
581			t[#t+1] = i-strlen
582			i = i + 1
583		end
584		while i <= strlen - 2 do
585			local x = string_byte(str, i+2)
586			string_table[i+2] = x
587			hash = (hash*256+x)%16777216
588			local t = hash_tables[hash]
589			if not t then t = {}; hash_tables[hash] = t end
590			t[#t+1] = i-strlen
591			i = i + 1
592		end
593	end
594	return dictionary
595end
596
597-- Check if the dictionary is valid.
598-- @param dictionary The preset dictionary for compression and decompression.
599-- @return true if valid, false if not valid.
600-- @return if not valid, the error message.
601local function IsValidDictionary(dictionary)
602	if type(dictionary) ~= "table" then
603		return false, ("'dictionary' - table expected got '%s'.")
604			:format(type(dictionary))
605	end
606	if type(dictionary.adler32) ~= "number"
607		or type(dictionary.string_table) ~= "table"
608		or type(dictionary.strlen) ~= "number"
609		or dictionary.strlen <= 0
610		or dictionary.strlen > 32768
611		or dictionary.strlen ~= #dictionary.string_table
612		or type(dictionary.hash_tables) ~= "table"
613		then
614		return false, ("'dictionary' - corrupted dictionary.")
615			:format(type(dictionary))
616	end
617	return true, ""
618end
619
620--[[
621	key of the configuration table is the compression level,
622	and its value stores the compression setting.
623	These numbers come from zlib source code.
624
625	Higher compression level usually means better compression.
626	(Because LibDeflate uses a simplified version of zlib algorithm,
627	there is no guarantee that higher compression level does not create
628	bigger file than lower level, but I can say it's 99% likely)
629
630	Be careful with the high compression level. This is a pure lua
631	implementation compressor/decompressor, which is significant slower than
632	a C/C++ equivalant compressor/decompressor. Very high compression level
633	costs significant more CPU time, and usually compression size won't be
634	significant smaller when you increase compression level by 1, when the
635	level is already very high. Benchmark yourself if you can afford it.
636
637	See also https://github.com/madler/zlib/blob/master/doc/algorithm.txt,
638	https://github.com/madler/zlib/blob/master/deflate.c for more information.
639
640	The meaning of each field:
641	@field 1 use_lazy_evaluation:
642		true/false. Whether the program uses lazy evaluation.
643		See what is "lazy evaluation" in the link above.
644		lazy_evaluation improves ratio, but relatively slow.
645	@field 2 good_prev_length:
646		Only effective if lazy is set, Only use 1/4 of max_chain,
647		if prev length of lazy match is above this.
648	@field 3 max_insert_length/max_lazy_match:
649		If not using lazy evaluation,
650		insert new strings in the hash table only if the match length is not
651		greater than this length.
652		If using lazy evaluation, only continue lazy evaluation,
653		if previous match length is strictly smaller than this value.
654	@field 4 nice_length:
655		Number. Don't continue to go down the hash chain,
656		if match length is above this.
657	@field 5 max_chain:
658		Number. The maximum number of hash chains we look.
659--]]
660local _compression_level_configs = {
661	[0] = {false, nil, 0, 0, 0}, -- level 0, no compression
662	[1] = {false, nil, 4, 8, 4}, -- level 1, similar to zlib level 1
663	[2] = {false, nil, 5, 18, 8}, -- level 2, similar to zlib level 2
664	[3] = {false, nil, 6, 32, 32},	-- level 3, similar to zlib level 3
665	[4] = {true, 4,	4, 16, 16},	-- level 4, similar to zlib level 4
666	[5] = {true, 8,	16,	32,	32}, -- level 5, similar to zlib level 5
667	[6] = {true, 8,	16,	128, 128}, -- level 6, similar to zlib level 6
668	[7] = {true, 8,	32,	128, 256}, -- (SLOW) level 7, similar to zlib level 7
669	[8] = {true, 32, 128, 258, 1024} , --(SLOW) level 8,similar to zlib level 8
670	[9] = {true, 32, 258, 258, 4096},
671		-- (VERY SLOW) level 9, similar to zlib level 9
672}
673
674-- Check if the compression/decompression arguments is valid
675-- @param str The input string.
676-- @param check_dictionary if true, check if dictionary is valid.
677-- @param dictionary The preset dictionary for compression and decompression.
678-- @param check_configs if true, check if config is valid.
679-- @param configs The compression configuration table
680-- @return true if valid, false if not valid.
681-- @return if not valid, the error message.
682local function IsValidArguments(str,
683	check_dictionary, dictionary,
684	check_configs, configs)
685
686	if type(str) ~= "string" then
687		return false,
688			("'str' - string expected got '%s'."):format(type(str))
689	end
690	if check_dictionary then
691		local dict_valid, dict_err = IsValidDictionary(dictionary)
692		if not dict_valid then
693			return false, dict_err
694		end
695	end
696	if check_configs then
697		local type_configs = type(configs)
698		if type_configs ~= "nil" and type_configs ~= "table" then
699			return false,
700			("'configs' - nil or table expected got '%s'.")
701				:format(type(configs))
702		end
703		if type_configs == "table" then
704			for k, v in pairs(configs) do
705				if k ~= "level" and k ~= "strategy" then
706					return false,
707					("'configs' - unsupported table key in the configs: '%s'.")
708					:format(k)
709				elseif k == "level" and not _compression_level_configs[v] then
710					return false,
711					("'configs' - unsupported 'level': %s."):format(tostring(v))
712				elseif k == "strategy" and v ~= "fixed" and v ~= "huffman_only"
713						and v ~= "dynamic" then
714						-- random_block_type is for testing purpose
715					return false, ("'configs' - unsupported 'strategy': '%s'.")
716						:format(tostring(v))
717				end
718			end
719		end
720	end
721	return true, ""
722end
723
724
725
726--[[ --------------------------------------------------------------------------
727	Compress code
728--]] --------------------------------------------------------------------------
729
730-- partial flush to save memory
731local _FLUSH_MODE_MEMORY_CLEANUP = 0
732-- full flush with partial bytes
733local _FLUSH_MODE_OUTPUT = 1
734-- write bytes to get to byte boundary
735local _FLUSH_MODE_BYTE_BOUNDARY = 2
736-- no flush, just get num of bits written so far
737local _FLUSH_MODE_NO_FLUSH = 3
738
739--[[
740	Create an empty writer to easily write stuffs as the unit of bits.
741	Return values:
742	1. WriteBits(code, bitlen):
743	2. WriteString(str):
744	3. Flush(mode):
745--]]
746local function CreateWriter()
747	local buffer_size = 0
748	local cache = 0
749	local cache_bitlen = 0
750	local total_bitlen = 0
751	local buffer = {}
752	-- When buffer is big enough, flush into result_buffer to save memory.
753	local result_buffer = {}
754
755	-- Write bits with value "value" and bit length of "bitlen" into writer.
756	-- @param value: The value being written
757	-- @param bitlen: The bit length of "value"
758	-- @return nil
759	local function WriteBits(value, bitlen)
760		cache = cache + value * _pow2[cache_bitlen]
761		cache_bitlen = cache_bitlen + bitlen
762		total_bitlen = total_bitlen + bitlen
763		-- Only bulk to buffer every 4 bytes. This is quicker.
764		if cache_bitlen >= 32 then
765			buffer_size = buffer_size + 1
766			buffer[buffer_size] =
767				_byte_to_char[cache % 256]
768				.._byte_to_char[((cache-cache%256)/256 % 256)]
769				.._byte_to_char[((cache-cache%65536)/65536 % 256)]
770				.._byte_to_char[((cache-cache%16777216)/16777216 % 256)]
771			local rshift_mask = _pow2[32 - cache_bitlen + bitlen]
772			cache = (value - value%rshift_mask)/rshift_mask
773			cache_bitlen = cache_bitlen - 32
774		end
775	end
776
777	-- Write the entire string into the writer.
778	-- @param str The string being written
779	-- @return nil
780	local function WriteString(str)
781		for _ = 1, cache_bitlen, 8 do
782			buffer_size = buffer_size + 1
783			buffer[buffer_size] = string_char(cache % 256)
784			cache = (cache-cache%256)/256
785		end
786		cache_bitlen = 0
787		buffer_size = buffer_size + 1
788		buffer[buffer_size] = str
789		total_bitlen = total_bitlen + #str*8
790	end
791
792	-- Flush current stuffs in the writer and return it.
793	-- This operation will free most of the memory.
794	-- @param mode See the descrtion of the constant and the source code.
795	-- @return The total number of bits stored in the writer right now.
796	-- for byte boundary mode, it includes the padding bits.
797	-- for output mode, it does not include padding bits.
798	-- @return Return the outputs if mode is output.
799	local function FlushWriter(mode)
800		if mode == _FLUSH_MODE_NO_FLUSH then
801			return total_bitlen
802		end
803
804		if mode == _FLUSH_MODE_OUTPUT
805			or mode == _FLUSH_MODE_BYTE_BOUNDARY then
806			-- Full flush, also output cache.
807			-- Need to pad some bits if cache_bitlen is not multiple of 8.
808			local padding_bitlen = (8 - cache_bitlen % 8) % 8
809
810			if cache_bitlen > 0 then
811				-- padding with all 1 bits, mainly because "\000" is not
812				-- good to be tranmitted. I do this so "\000" is a little bit
813				-- less frequent.
814				cache = cache - _pow2[cache_bitlen]
815					+ _pow2[cache_bitlen+padding_bitlen]
816				for _ = 1, cache_bitlen, 8 do
817					buffer_size = buffer_size + 1
818					buffer[buffer_size] = _byte_to_char[cache % 256]
819					cache = (cache-cache%256)/256
820				end
821
822				cache = 0
823				cache_bitlen = 0
824			end
825			if mode == _FLUSH_MODE_BYTE_BOUNDARY then
826				total_bitlen = total_bitlen + padding_bitlen
827				return total_bitlen
828			end
829		end
830
831		local flushed = table_concat(buffer)
832		buffer = {}
833		buffer_size = 0
834		result_buffer[#result_buffer+1] = flushed
835
836		if mode == _FLUSH_MODE_MEMORY_CLEANUP then
837			return total_bitlen
838		else
839			return total_bitlen, table_concat(result_buffer)
840		end
841	end
842
843	return WriteBits, WriteString, FlushWriter
844end
845
846-- Push an element into a max heap
847-- @param heap A max heap whose max element is at index 1.
848-- @param e The element to be pushed. Assume element "e" is a table
849--  and comparison is done via its first entry e[1]
850-- @param heap_size current number of elements in the heap.
851--  NOTE: There may be some garbage stored in
852--  heap[heap_size+1], heap[heap_size+2], etc..
853-- @return nil
854local function MinHeapPush(heap, e, heap_size)
855	heap_size = heap_size + 1
856	heap[heap_size] = e
857	local value = e[1]
858	local pos = heap_size
859	local parent_pos = (pos-pos%2)/2
860
861	while (parent_pos >= 1 and heap[parent_pos][1] > value) do
862		local t = heap[parent_pos]
863		heap[parent_pos] = e
864		heap[pos] = t
865		pos = parent_pos
866		parent_pos = (parent_pos-parent_pos%2)/2
867	end
868end
869
870-- Pop an element from a max heap
871-- @param heap A max heap whose max element is at index 1.
872-- @param heap_size current number of elements in the heap.
873-- @return the poped element
874-- Note: This function does not change table size of "heap" to save CPU time.
875local function MinHeapPop(heap, heap_size)
876	local top = heap[1]
877	local e = heap[heap_size]
878	local value = e[1]
879	heap[1] = e
880	heap[heap_size] = top
881	heap_size = heap_size - 1
882
883	local pos = 1
884	local left_child_pos = pos * 2
885	local right_child_pos = left_child_pos + 1
886
887	while (left_child_pos <= heap_size) do
888		local left_child = heap[left_child_pos]
889		if (right_child_pos <= heap_size
890			and heap[right_child_pos][1] < left_child[1]) then
891			local right_child = heap[right_child_pos]
892			if right_child[1] < value then
893				heap[right_child_pos] = e
894				heap[pos] = right_child
895				pos = right_child_pos
896				left_child_pos = pos * 2
897				right_child_pos = left_child_pos + 1
898			else
899				break
900			end
901		else
902			if left_child[1] < value then
903				heap[left_child_pos] = e
904				heap[pos] = left_child
905				pos = left_child_pos
906				left_child_pos = pos * 2
907				right_child_pos = left_child_pos + 1
908			else
909				break
910			end
911		end
912	end
913
914	return top
915end
916
917-- Deflate defines a special huffman tree, which is unique once the bit length
918-- of huffman code of all symbols are known.
919-- @param bitlen_count Number of symbols with a specific bitlen
920-- @param symbol_bitlen The bit length of a symbol
921-- @param max_symbol The max symbol among all symbols,
922--		which is (number of symbols - 1)
923-- @param max_bitlen The max huffman bit length among all symbols.
924-- @return The huffman code of all symbols.
925local function GetHuffmanCodeFromBitlen(bitlen_counts, symbol_bitlens
926		, max_symbol, max_bitlen)
927	local huffman_code = 0
928	local next_codes = {}
929	local symbol_huffman_codes = {}
930	for bitlen = 1, max_bitlen do
931		huffman_code = (huffman_code+(bitlen_counts[bitlen-1] or 0))*2
932		next_codes[bitlen] = huffman_code
933	end
934	for symbol = 0, max_symbol do
935		local bitlen = symbol_bitlens[symbol]
936		if bitlen then
937			huffman_code = next_codes[bitlen]
938			next_codes[bitlen] = huffman_code + 1
939
940			-- Reverse the bits of huffman code,
941			-- because most signifant bits of huffman code
942			-- is stored first into the compressed data.
943			-- @see RFC1951 Page5 Section 3.1.1
944			if bitlen <= 9 then -- Have cached reverse for small bitlen.
945				symbol_huffman_codes[symbol] =
946					_reverse_bits_tbl[bitlen][huffman_code]
947			else
948				local reverse = 0
949				for _ = 1, bitlen do
950					reverse = reverse - reverse%2
951						+ (((reverse%2==1)
952							or (huffman_code % 2) == 1) and 1 or 0)
953					huffman_code = (huffman_code-huffman_code%2)/2
954					reverse = reverse*2
955				end
956				symbol_huffman_codes[symbol] = (reverse-reverse%2)/2
957			end
958		end
959	end
960	return symbol_huffman_codes
961end
962
963-- A helper function to sort heap elements
964-- a[1], b[1] is the huffman frequency
965-- a[2], b[2] is the symbol value.
966local function SortByFirstThenSecond(a, b)
967	return a[1] < b[1] or
968		(a[1] == b[1] and a[2] < b[2])
969end
970
971-- Calculate the huffman bit length and huffman code.
972-- @param symbol_count: A table whose table key is the symbol, and table value
973--		is the symbol frenquency (nil means 0 frequency).
974-- @param max_bitlen: See description of return value.
975-- @param max_symbol: The maximum symbol
976-- @return a table whose key is the symbol, and the value is the huffman bit
977--		bit length. We guarantee that all bit length <= max_bitlen.
978--		For 0<=symbol<=max_symbol, table value could be nil if the frequency
979--		of the symbol is 0 or nil.
980-- @return a table whose key is the symbol, and the value is the huffman code.
981-- @return a number indicating the maximum symbol whose bitlen is not 0.
982local function GetHuffmanBitlenAndCode(symbol_counts, max_bitlen, max_symbol)
983	local heap_size
984	local max_non_zero_bitlen_symbol = -1
985	local leafs = {}
986	local heap = {}
987	local symbol_bitlens = {}
988	local symbol_codes = {}
989	local bitlen_counts = {}
990
991	--[[
992		tree[1]: weight, temporarily used as parent and bitLengths
993		tree[2]: symbol
994		tree[3]: left child
995		tree[4]: right child
996	--]]
997	local number_unique_symbols = 0
998	for symbol, count in pairs(symbol_counts) do
999		number_unique_symbols = number_unique_symbols + 1
1000		leafs[number_unique_symbols] = {count, symbol}
1001	end
1002
1003	if (number_unique_symbols == 0) then
1004		-- no code.
1005		return {}, {}, -1
1006	elseif (number_unique_symbols == 1) then
1007		-- Only one code. In this case, its huffman code
1008		-- needs to be assigned as 0, and bit length is 1.
1009		-- This is the only case that the return result
1010		-- represents an imcomplete huffman tree.
1011		local symbol = leafs[1][2]
1012		symbol_bitlens[symbol] = 1
1013		symbol_codes[symbol] = 0
1014		return symbol_bitlens, symbol_codes, symbol
1015	else
1016		table_sort(leafs, SortByFirstThenSecond)
1017		heap_size = number_unique_symbols
1018		for i = 1, heap_size do
1019			heap[i] = leafs[i]
1020		end
1021
1022		while (heap_size > 1) do
1023			-- Note: pop does not change table size of heap
1024			local leftChild = MinHeapPop(heap, heap_size)
1025			heap_size = heap_size - 1
1026			local rightChild = MinHeapPop(heap, heap_size)
1027			heap_size = heap_size - 1
1028			local newNode =
1029				{leftChild[1]+rightChild[1], -1, leftChild, rightChild}
1030			MinHeapPush(heap, newNode, heap_size)
1031			heap_size = heap_size + 1
1032		end
1033
1034		-- Number of leafs whose bit length is greater than max_len.
1035		local number_bitlen_overflow = 0
1036
1037		-- Calculate bit length of all nodes
1038		local fifo = {heap[1], 0, 0, 0} -- preallocate some spaces.
1039		local fifo_size = 1
1040		local index = 1
1041		heap[1][1] = 0
1042		while (index <= fifo_size) do -- Breath first search
1043			local e = fifo[index]
1044			local bitlen = e[1]
1045			local symbol = e[2]
1046			local left_child = e[3]
1047			local right_child = e[4]
1048			if left_child then
1049				fifo_size = fifo_size + 1
1050				fifo[fifo_size] = left_child
1051				left_child[1] = bitlen + 1
1052			end
1053			if right_child then
1054				fifo_size = fifo_size + 1
1055				fifo[fifo_size] = right_child
1056				right_child[1] = bitlen + 1
1057			end
1058			index = index + 1
1059
1060			if (bitlen > max_bitlen) then
1061				number_bitlen_overflow = number_bitlen_overflow + 1
1062				bitlen = max_bitlen
1063			end
1064			if symbol >= 0 then
1065				symbol_bitlens[symbol] = bitlen
1066				max_non_zero_bitlen_symbol =
1067					(symbol > max_non_zero_bitlen_symbol)
1068					and symbol or max_non_zero_bitlen_symbol
1069				bitlen_counts[bitlen] = (bitlen_counts[bitlen] or 0) + 1
1070			end
1071		end
1072
1073		-- Resolve bit length overflow
1074		-- @see ZLib/trees.c:gen_bitlen(s, desc), for reference
1075		if (number_bitlen_overflow > 0) then
1076			repeat
1077				local bitlen = max_bitlen - 1
1078				while ((bitlen_counts[bitlen] or 0) == 0) do
1079					bitlen = bitlen - 1
1080				end
1081				-- move one leaf down the tree
1082				bitlen_counts[bitlen] = bitlen_counts[bitlen] - 1
1083				-- move one overflow item as its brother
1084				bitlen_counts[bitlen+1] = (bitlen_counts[bitlen+1] or 0) + 2
1085				bitlen_counts[max_bitlen] = bitlen_counts[max_bitlen] - 1
1086				number_bitlen_overflow = number_bitlen_overflow - 2
1087			until (number_bitlen_overflow <= 0)
1088
1089			index = 1
1090			for bitlen = max_bitlen, 1, -1 do
1091				local n = bitlen_counts[bitlen] or 0
1092				while (n > 0) do
1093					local symbol = leafs[index][2]
1094					symbol_bitlens[symbol] = bitlen
1095					n = n - 1
1096					index = index + 1
1097				end
1098			end
1099		end
1100
1101		symbol_codes = GetHuffmanCodeFromBitlen(bitlen_counts, symbol_bitlens,
1102				max_symbol, max_bitlen)
1103		return symbol_bitlens, symbol_codes, max_non_zero_bitlen_symbol
1104	end
1105end
1106
1107-- Calculate the first huffman header in the dynamic huffman block
1108-- @see RFC1951 Page 12
1109-- @param lcode_bitlen: The huffman bit length of literal/LZ77_length.
1110-- @param max_non_zero_bitlen_lcode: The maximum literal/LZ77_length symbol
1111--		whose huffman bit length is not zero.
1112-- @param dcode_bitlen: The huffman bit length of LZ77 distance.
1113-- @param max_non_zero_bitlen_dcode: The maximum LZ77 distance symbol
1114--		whose huffman bit length is not zero.
1115-- @return The run length encoded codes.
1116-- @return The extra bits. One entry for each rle code that needs extra bits.
1117--		(code == 16 or 17 or 18).
1118-- @return The count of appearance of each rle codes.
1119local function RunLengthEncodeHuffmanBitlen(
1120		lcode_bitlens,
1121		max_non_zero_bitlen_lcode,
1122		dcode_bitlens,
1123		max_non_zero_bitlen_dcode)
1124	local rle_code_tblsize = 0
1125	local rle_codes = {}
1126	local rle_code_counts = {}
1127	local rle_extra_bits_tblsize = 0
1128	local rle_extra_bits = {}
1129	local prev = nil
1130	local count = 0
1131
1132	-- If there is no distance code, assume one distance code of bit length 0.
1133	-- RFC1951: One distance code of zero bits means that
1134	-- there are no distance codes used at all (the data is all literals).
1135	max_non_zero_bitlen_dcode = (max_non_zero_bitlen_dcode < 0)
1136			and 0 or max_non_zero_bitlen_dcode
1137	local max_code = max_non_zero_bitlen_lcode+max_non_zero_bitlen_dcode+1
1138
1139	for code = 0, max_code+1 do
1140		local len = (code <= max_non_zero_bitlen_lcode)
1141			and (lcode_bitlens[code] or 0)
1142			or ((code <= max_code)
1143			and (dcode_bitlens[code-max_non_zero_bitlen_lcode-1] or 0) or nil)
1144		if len == prev then
1145			count = count + 1
1146			if len ~= 0 and count == 6 then
1147				rle_code_tblsize = rle_code_tblsize + 1
1148				rle_codes[rle_code_tblsize] = 16
1149				rle_extra_bits_tblsize = rle_extra_bits_tblsize + 1
1150				rle_extra_bits[rle_extra_bits_tblsize] = 3
1151				rle_code_counts[16] = (rle_code_counts[16] or 0) + 1
1152				count = 0
1153			elseif len == 0 and count == 138 then
1154				rle_code_tblsize = rle_code_tblsize + 1
1155				rle_codes[rle_code_tblsize] = 18
1156				rle_extra_bits_tblsize = rle_extra_bits_tblsize + 1
1157				rle_extra_bits[rle_extra_bits_tblsize] = 127
1158				rle_code_counts[18] = (rle_code_counts[18] or 0) + 1
1159				count = 0
1160			end
1161		else
1162			if count == 1 then
1163				rle_code_tblsize = rle_code_tblsize + 1
1164				rle_codes[rle_code_tblsize] = prev
1165				rle_code_counts[prev] = (rle_code_counts[prev] or 0) + 1
1166			elseif count == 2 then
1167				rle_code_tblsize = rle_code_tblsize + 1
1168				rle_codes[rle_code_tblsize] = prev
1169				rle_code_tblsize = rle_code_tblsize + 1
1170				rle_codes[rle_code_tblsize] = prev
1171				rle_code_counts[prev] = (rle_code_counts[prev] or 0) + 2
1172			elseif count >= 3 then
1173				rle_code_tblsize = rle_code_tblsize + 1
1174				local rleCode = (prev ~= 0) and 16 or (count <= 10 and 17 or 18)
1175				rle_codes[rle_code_tblsize] = rleCode
1176				rle_code_counts[rleCode] = (rle_code_counts[rleCode] or 0) + 1
1177				rle_extra_bits_tblsize = rle_extra_bits_tblsize + 1
1178				rle_extra_bits[rle_extra_bits_tblsize] =
1179					(count <= 10) and (count - 3) or (count - 11)
1180			end
1181
1182			prev = len
1183			if len and len ~= 0 then
1184				rle_code_tblsize = rle_code_tblsize + 1
1185				rle_codes[rle_code_tblsize] = len
1186				rle_code_counts[len] = (rle_code_counts[len] or 0) + 1
1187				count = 0
1188			else
1189				count = 1
1190			end
1191		end
1192	end
1193
1194	return rle_codes, rle_extra_bits, rle_code_counts
1195end
1196
1197-- Load the string into a table, in order to speed up LZ77.
1198-- Loop unrolled 16 times to speed this function up.
1199-- @param str The string to be loaded.
1200-- @param t The load destination
1201-- @param start str[index] will be the first character to be loaded.
1202-- @param end str[index] will be the last character to be loaded
1203-- @param offset str[index] will be loaded into t[index-offset]
1204-- @return t
1205local function LoadStringToTable(str, t, start, stop, offset)
1206	local i = start - offset
1207	while i <= stop - 15 - offset do
1208		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],
1209		t[i+9], t[i+10], t[i+11], t[i+12], t[i+13], t[i+14], t[i+15] =
1210			string_byte(str, i + offset, i + 15 + offset)
1211		i = i + 16
1212	end
1213	while (i <= stop - offset) do
1214		t[i] = string_byte(str, i + offset, i + offset)
1215		i = i + 1
1216	end
1217	return t
1218end
1219
1220-- Do LZ77 process. This function uses the majority of the CPU time.
1221-- @see zlib/deflate.c:deflate_fast(), zlib/deflate.c:deflate_slow()
1222-- @see https://github.com/madler/zlib/blob/master/doc/algorithm.txt
1223-- This function uses the algorithms used above. You should read the
1224-- algorithm.txt above to understand what is the hash function and the
1225-- lazy evaluation.
1226--
1227-- The special optimization used here is hash functions used here.
1228-- The hash function is just the multiplication of the three consective
1229-- characters. So if the hash matches, it guarantees 3 characters are matched.
1230-- This optimization can be implemented because Lua table is a hash table.
1231--
1232-- @param level integer that describes compression level.
1233-- @param string_table table that stores the value of string to be compressed.
1234--			The index of this table starts from 1.
1235--			The caller needs to make sure all values needed by this function
1236--			are loaded.
1237--			Assume "str" is the origin input string into the compressor
1238--			str[block_start]..str[block_end+3] needs to be loaded into
1239--			string_table[block_start-offset]..string_table[block_end-offset]
1240--			If dictionary is presented, the last 258 bytes of the dictionary
1241--			needs to be loaded into sing_table[-257..0]
1242--			(See more in the description of offset.)
1243-- @param hash_tables. The table key is the hash value (0<=hash<=16777216=256^3)
1244--			The table value is an array0 that stores the indexes of the
1245--			input data string to be compressed, such that
1246--			hash == str[index]*str[index+1]*str[index+2]
1247--			Indexes are ordered in this array.
1248-- @param block_start The indexes of the input data string to be compressed.
1249--				that starts the LZ77 block.
1250-- @param block_end The indexes of the input data string to be compressed.
1251--				that stores the LZ77 block.
1252-- @param offset str[index] is stored in string_table[index-offset],
1253--			This offset is mainly an optimization to limit the index
1254--			of string_table, so lua can access this table quicker.
1255-- @param dictionary See LibDeflate:CreateDictionary
1256-- @return literal/LZ77_length deflate codes.
1257-- @return the extra bits of literal/LZ77_length deflate codes.
1258-- @return the count of each literal/LZ77 deflate code.
1259-- @return LZ77 distance deflate codes.
1260-- @return the extra bits of LZ77 distance deflate codes.
1261-- @return the count of each LZ77 distance deflate code.
1262local function GetBlockLZ77Result(level, string_table, hash_tables, block_start,
1263		block_end, offset, dictionary)
1264	local config = _compression_level_configs[level]
1265	local config_use_lazy
1266		, config_good_prev_length
1267		, config_max_lazy_match
1268		, config_nice_length
1269		, config_max_hash_chain =
1270			config[1], config[2], config[3], config[4], config[5]
1271
1272	local config_max_insert_length = (not config_use_lazy)
1273		and config_max_lazy_match or 2147483646
1274	local config_good_hash_chain =
1275		(config_max_hash_chain-config_max_hash_chain%4/4)
1276
1277	local hash
1278
1279	local dict_hash_tables
1280	local dict_string_table
1281	local dict_string_len = 0
1282
1283	if dictionary then
1284		dict_hash_tables = dictionary.hash_tables
1285		dict_string_table = dictionary.string_table
1286		dict_string_len = dictionary.strlen
1287		assert(block_start == 1)
1288		if block_end >= block_start and dict_string_len >= 2 then
1289			hash = dict_string_table[dict_string_len-1]*65536
1290				+ dict_string_table[dict_string_len]*256 + string_table[1]
1291			local t = hash_tables[hash]
1292			if not t then t = {}; hash_tables[hash] = t end
1293			t[#t+1] = -1
1294		end
1295		if block_end >= block_start+1 and dict_string_len >= 1 then
1296			hash = dict_string_table[dict_string_len]*65536
1297				+ string_table[1]*256 + string_table[2]
1298			local t = hash_tables[hash]
1299			if not t then t = {}; hash_tables[hash] = t end
1300			t[#t+1] = 0
1301		end
1302	end
1303
1304	hash = (string_table[block_start-offset] or 0)*256
1305		+ (string_table[block_start+1-offset] or 0)
1306
1307	local lcodes = {}
1308	local lcode_tblsize = 0
1309	local lcodes_counts = {}
1310	local dcodes = {}
1311	local dcodes_tblsize = 0
1312	local dcodes_counts = {}
1313
1314	local lextra_bits = {}
1315	local lextra_bits_tblsize = 0
1316	local dextra_bits = {}
1317	local dextra_bits_tblsize = 0
1318
1319	local match_available = false
1320	local prev_len
1321	local prev_dist
1322	local cur_len = 0
1323	local cur_dist = 0
1324
1325	local index = block_start
1326	local index_end = block_end + (config_use_lazy and 1 or 0)
1327
1328	-- the zlib source code writes separate code for lazy evaluation and
1329	-- not lazy evaluation, which is easier to understand.
1330	-- I put them together, so it is a bit harder to understand.
1331	-- because I think this is easier for me to maintain it.
1332	while (index <= index_end) do
1333		local string_table_index = index - offset
1334		prev_len = cur_len
1335		prev_dist = cur_dist
1336		cur_len = 0
1337
1338		hash = (hash*256+(string_table[string_table_index+2] or 0))%16777216
1339
1340		local chain_index
1341		local cur_chain
1342		local hash_chain = hash_tables[hash]
1343		local chain_old_size
1344		if not hash_chain then
1345			chain_old_size = 0
1346			hash_chain = {}
1347			hash_tables[hash] = hash_chain
1348			if dict_hash_tables then
1349				cur_chain = dict_hash_tables[hash]
1350				chain_index = cur_chain and #cur_chain or 0
1351			else
1352				chain_index = 0
1353			end
1354		else
1355			chain_old_size = #hash_chain
1356			cur_chain = hash_chain
1357			chain_index = chain_old_size
1358		end
1359
1360		if index <= block_end then
1361			hash_chain[chain_old_size+1] = index
1362		end
1363
1364		if (chain_index > 0 and index + 2 <= block_end
1365			and (not config_use_lazy or prev_len < config_max_lazy_match)) then
1366
1367			local depth =
1368				(config_use_lazy and prev_len >= config_good_prev_length)
1369				and config_good_hash_chain or config_max_hash_chain
1370
1371			while chain_index >= 1 and depth > 0 do
1372				local prev = cur_chain[chain_index]
1373
1374				if index - prev > 32768 then
1375					break
1376				end
1377				if prev < index then
1378					local j = 3
1379
1380					if prev >= -257 then
1381						local prev_table_index = prev-offset
1382						-- NOTE for author:
1383						-- j < 258 and index + j <= block_end
1384						-- This is the right condition
1385						while (j < 258 and index + j <= block_end) do
1386							if (string_table[prev_table_index+j]
1387								== string_table[string_table_index+j]) then
1388								j = j + 1
1389							else
1390								break
1391							end
1392						end
1393					else
1394						local prev_table_index = dict_string_len+prev
1395						-- NOTE for author:
1396						-- j < 258 and index + j <= block_end
1397						-- This is the right condition
1398						while (j < 258 and index + j <= block_end) do
1399							if (dict_string_table[prev_table_index+j]
1400								== string_table[string_table_index+j]) then
1401								j = j + 1
1402							else
1403								break
1404							end
1405						end
1406					end
1407					if j > cur_len then
1408						cur_len = j
1409						cur_dist = index - prev
1410					end
1411					if cur_len >= config_nice_length then
1412						break
1413					end
1414				end
1415
1416				chain_index = chain_index - 1
1417				depth = depth - 1
1418				if chain_index == 0 and prev > 0 and dict_hash_tables then
1419					cur_chain = dict_hash_tables[hash]
1420					chain_index = cur_chain and #cur_chain or 0
1421				end
1422			end
1423		end
1424
1425		if not config_use_lazy then
1426			prev_len, prev_dist = cur_len, cur_dist
1427		end
1428		if ((not config_use_lazy or match_available)
1429			and (prev_len > 3 or (prev_len == 3 and prev_dist < 4096))
1430			and cur_len <= prev_len )then
1431			local code = _length_to_deflate_code[prev_len]
1432			local length_extra_bits_bitlen =
1433				_length_to_deflate_extra_bitlen[prev_len]
1434			local dist_code, dist_extra_bits_bitlen, dist_extra_bits
1435			if prev_dist <= 256 then -- have cached code for small distance.
1436				dist_code = _dist256_to_deflate_code[prev_dist]
1437				dist_extra_bits = _dist256_to_deflate_extra_bits[prev_dist]
1438				dist_extra_bits_bitlen =
1439					_dist256_to_deflate_extra_bitlen[prev_dist]
1440			else
1441				dist_code = 16
1442				dist_extra_bits_bitlen = 7
1443				local a = 384
1444				local b = 512
1445
1446				while true do
1447					if prev_dist <= a then
1448						dist_extra_bits = (prev_dist-(b/2)-1) % (b/4)
1449						break
1450					elseif prev_dist <= b then
1451						dist_extra_bits = (prev_dist-(b/2)-1) % (b/4)
1452						dist_code = dist_code + 1
1453						break
1454					else
1455						dist_code = dist_code + 2
1456						dist_extra_bits_bitlen = dist_extra_bits_bitlen + 1
1457						a = a*2
1458						b = b*2
1459					end
1460				end
1461			end
1462			lcode_tblsize = lcode_tblsize + 1
1463			lcodes[lcode_tblsize] = code
1464			lcodes_counts[code] = (lcodes_counts[code] or 0) + 1
1465
1466			dcodes_tblsize = dcodes_tblsize + 1
1467			dcodes[dcodes_tblsize] = dist_code
1468			dcodes_counts[dist_code] = (dcodes_counts[dist_code] or 0) + 1
1469
1470			if length_extra_bits_bitlen > 0 then
1471				local lenExtraBits = _length_to_deflate_extra_bits[prev_len]
1472				lextra_bits_tblsize = lextra_bits_tblsize + 1
1473				lextra_bits[lextra_bits_tblsize] = lenExtraBits
1474			end
1475			if dist_extra_bits_bitlen > 0 then
1476				dextra_bits_tblsize = dextra_bits_tblsize + 1
1477				dextra_bits[dextra_bits_tblsize] = dist_extra_bits
1478			end
1479
1480			for i=index+1, index+prev_len-(config_use_lazy and 2 or 1) do
1481				hash = (hash*256+(string_table[i-offset+2] or 0))%16777216
1482				if prev_len <= config_max_insert_length then
1483					hash_chain = hash_tables[hash]
1484					if not hash_chain then
1485						hash_chain = {}
1486						hash_tables[hash] = hash_chain
1487					end
1488					hash_chain[#hash_chain+1] = i
1489				end
1490			end
1491			index = index + prev_len - (config_use_lazy and 1 or 0)
1492			match_available = false
1493		elseif (not config_use_lazy) or match_available then
1494			local code = string_table[config_use_lazy
1495				and (string_table_index-1) or string_table_index]
1496			lcode_tblsize = lcode_tblsize + 1
1497			lcodes[lcode_tblsize] = code
1498			lcodes_counts[code] = (lcodes_counts[code] or 0) + 1
1499			index = index + 1
1500		else
1501			match_available = true
1502			index = index + 1
1503		end
1504	end
1505
1506	-- Write "end of block" symbol
1507	lcode_tblsize = lcode_tblsize + 1
1508	lcodes[lcode_tblsize] = 256
1509	lcodes_counts[256] = (lcodes_counts[256] or 0) + 1
1510
1511	return lcodes, lextra_bits, lcodes_counts, dcodes, dextra_bits
1512		, dcodes_counts
1513end
1514
1515-- Get the header data of dynamic block.
1516-- @param lcodes_count The count of each literal/LZ77_length codes.
1517-- @param dcodes_count The count of each Lz77 distance codes.
1518-- @return a lots of stuffs.
1519-- @see RFC1951 Page 12
1520local function GetBlockDynamicHuffmanHeader(lcodes_counts, dcodes_counts)
1521	local lcodes_huffman_bitlens, lcodes_huffman_codes
1522		, max_non_zero_bitlen_lcode =
1523		GetHuffmanBitlenAndCode(lcodes_counts, 15, 285)
1524	local dcodes_huffman_bitlens, dcodes_huffman_codes
1525		, max_non_zero_bitlen_dcode =
1526		GetHuffmanBitlenAndCode(dcodes_counts, 15, 29)
1527
1528	local rle_deflate_codes, rle_extra_bits, rle_codes_counts =
1529		RunLengthEncodeHuffmanBitlen(lcodes_huffman_bitlens
1530		,max_non_zero_bitlen_lcode, dcodes_huffman_bitlens
1531		, max_non_zero_bitlen_dcode)
1532
1533	local rle_codes_huffman_bitlens, rle_codes_huffman_codes =
1534		GetHuffmanBitlenAndCode(rle_codes_counts, 7, 18)
1535
1536	local HCLEN = 0
1537	for i = 1, 19 do
1538		local symbol = _rle_codes_huffman_bitlen_order[i]
1539		local length = rle_codes_huffman_bitlens[symbol] or 0
1540		if length ~= 0 then
1541			HCLEN = i
1542		end
1543	end
1544
1545	HCLEN = HCLEN - 4
1546	local HLIT = max_non_zero_bitlen_lcode + 1 - 257
1547	local HDIST = max_non_zero_bitlen_dcode + 1 - 1
1548	if HDIST < 0 then HDIST = 0 end
1549
1550	return HLIT, HDIST, HCLEN, rle_codes_huffman_bitlens
1551		, rle_codes_huffman_codes, rle_deflate_codes, rle_extra_bits
1552		, lcodes_huffman_bitlens, lcodes_huffman_codes
1553		, dcodes_huffman_bitlens, dcodes_huffman_codes
1554end
1555
1556-- Get the size of dynamic block without writing any bits into the writer.
1557-- @param ... Read the source code of GetBlockDynamicHuffmanHeader()
1558-- @return the bit length of the dynamic block
1559local function GetDynamicHuffmanBlockSize(lcodes, dcodes, HCLEN
1560	, rle_codes_huffman_bitlens, rle_deflate_codes
1561	, lcodes_huffman_bitlens, dcodes_huffman_bitlens)
1562
1563	local block_bitlen = 17 -- 1+2+5+5+4
1564	block_bitlen = block_bitlen + (HCLEN+4)*3
1565
1566	for i = 1, #rle_deflate_codes do
1567		local code = rle_deflate_codes[i]
1568		block_bitlen = block_bitlen + rle_codes_huffman_bitlens[code]
1569		if code >= 16 then
1570			block_bitlen = block_bitlen +
1571			((code == 16) and 2 or (code == 17 and 3 or 7))
1572		end
1573	end
1574
1575	local length_code_count = 0
1576	for i = 1, #lcodes do
1577		local code = lcodes[i]
1578		local huffman_bitlen = lcodes_huffman_bitlens[code]
1579		block_bitlen = block_bitlen + huffman_bitlen
1580		if code > 256 then -- Length code
1581			length_code_count = length_code_count + 1
1582			if code > 264 and code < 285 then -- Length code with extra bits
1583				local extra_bits_bitlen =
1584					_literal_deflate_code_to_extra_bitlen[code-256]
1585				block_bitlen = block_bitlen + extra_bits_bitlen
1586			end
1587			local dist_code = dcodes[length_code_count]
1588			local dist_huffman_bitlen = dcodes_huffman_bitlens[dist_code]
1589			block_bitlen = block_bitlen + dist_huffman_bitlen
1590
1591			if dist_code > 3 then -- dist code with extra bits
1592				local dist_extra_bits_bitlen = (dist_code-dist_code%2)/2 - 1
1593				block_bitlen = block_bitlen + dist_extra_bits_bitlen
1594			end
1595		end
1596	end
1597	return block_bitlen
1598end
1599
1600-- Write dynamic block.
1601-- @param ... Read the source code of GetBlockDynamicHuffmanHeader()
1602local function CompressDynamicHuffmanBlock(WriteBits, is_last_block
1603		, lcodes, lextra_bits, dcodes, dextra_bits, HLIT, HDIST, HCLEN
1604		, rle_codes_huffman_bitlens, rle_codes_huffman_codes
1605		, rle_deflate_codes, rle_extra_bits
1606		, lcodes_huffman_bitlens, lcodes_huffman_codes
1607		, dcodes_huffman_bitlens, dcodes_huffman_codes)
1608
1609	WriteBits(is_last_block and 1 or 0, 1) -- Last block identifier
1610	WriteBits(2, 2) -- Dynamic Huffman block identifier
1611
1612	WriteBits(HLIT, 5)
1613	WriteBits(HDIST, 5)
1614	WriteBits(HCLEN, 4)
1615
1616	for i = 1, HCLEN+4 do
1617		local symbol = _rle_codes_huffman_bitlen_order[i]
1618		local length = rle_codes_huffman_bitlens[symbol] or 0
1619		WriteBits(length, 3)
1620	end
1621
1622	local rleExtraBitsIndex = 1
1623	for i=1, #rle_deflate_codes do
1624		local code = rle_deflate_codes[i]
1625		WriteBits(rle_codes_huffman_codes[code]
1626			, rle_codes_huffman_bitlens[code])
1627		if code >= 16 then
1628			local extraBits = rle_extra_bits[rleExtraBitsIndex]
1629			WriteBits(extraBits, (code == 16) and 2 or (code == 17 and 3 or 7))
1630			rleExtraBitsIndex = rleExtraBitsIndex + 1
1631		end
1632	end
1633
1634	local length_code_count = 0
1635	local length_code_with_extra_count = 0
1636	local dist_code_with_extra_count = 0
1637
1638	for i=1, #lcodes do
1639		local deflate_codee = lcodes[i]
1640		local huffman_code = lcodes_huffman_codes[deflate_codee]
1641		local huffman_bitlen = lcodes_huffman_bitlens[deflate_codee]
1642		WriteBits(huffman_code, huffman_bitlen)
1643		if deflate_codee > 256 then -- Length code
1644			length_code_count = length_code_count + 1
1645			if deflate_codee > 264 and deflate_codee < 285 then
1646				-- Length code with extra bits
1647				length_code_with_extra_count = length_code_with_extra_count + 1
1648				local extra_bits = lextra_bits[length_code_with_extra_count]
1649				local extra_bits_bitlen =
1650					_literal_deflate_code_to_extra_bitlen[deflate_codee-256]
1651				WriteBits(extra_bits, extra_bits_bitlen)
1652			end
1653			-- Write distance code
1654			local dist_deflate_code = dcodes[length_code_count]
1655			local dist_huffman_code = dcodes_huffman_codes[dist_deflate_code]
1656			local dist_huffman_bitlen =
1657				dcodes_huffman_bitlens[dist_deflate_code]
1658			WriteBits(dist_huffman_code, dist_huffman_bitlen)
1659
1660			if dist_deflate_code > 3 then -- dist code with extra bits
1661				dist_code_with_extra_count = dist_code_with_extra_count + 1
1662				local dist_extra_bits = dextra_bits[dist_code_with_extra_count]
1663				local dist_extra_bits_bitlen =
1664					(dist_deflate_code-dist_deflate_code%2)/2 - 1
1665				WriteBits(dist_extra_bits, dist_extra_bits_bitlen)
1666			end
1667		end
1668	end
1669end
1670
1671-- Get the size of fixed block without writing any bits into the writer.
1672-- @param lcodes literal/LZ77_length deflate codes
1673-- @param decodes LZ77 distance deflate codes
1674-- @return the bit length of the fixed block
1675local function GetFixedHuffmanBlockSize(lcodes, dcodes)
1676	local block_bitlen = 3
1677	local length_code_count = 0
1678	for i=1, #lcodes do
1679		local code = lcodes[i]
1680		local huffman_bitlen = _fix_block_literal_huffman_bitlen[code]
1681		block_bitlen = block_bitlen + huffman_bitlen
1682		if code > 256 then -- Length code
1683			length_code_count = length_code_count + 1
1684			if code > 264 and code < 285 then -- Length code with extra bits
1685				local extra_bits_bitlen =
1686					_literal_deflate_code_to_extra_bitlen[code-256]
1687				block_bitlen = block_bitlen + extra_bits_bitlen
1688			end
1689			local dist_code = dcodes[length_code_count]
1690			block_bitlen = block_bitlen + 5
1691
1692			if dist_code > 3 then -- dist code with extra bits
1693				local dist_extra_bits_bitlen =
1694					(dist_code-dist_code%2)/2 - 1
1695				block_bitlen = block_bitlen + dist_extra_bits_bitlen
1696			end
1697		end
1698	end
1699	return block_bitlen
1700end
1701
1702-- Write fixed block.
1703-- @param lcodes literal/LZ77_length deflate codes
1704-- @param decodes LZ77 distance deflate codes
1705local function CompressFixedHuffmanBlock(WriteBits, is_last_block,
1706		lcodes, lextra_bits, dcodes, dextra_bits)
1707	WriteBits(is_last_block and 1 or 0, 1) -- Last block identifier
1708	WriteBits(1, 2) -- Fixed Huffman block identifier
1709	local length_code_count = 0
1710	local length_code_with_extra_count = 0
1711	local dist_code_with_extra_count = 0
1712	for i=1, #lcodes do
1713		local deflate_code = lcodes[i]
1714		local huffman_code = _fix_block_literal_huffman_code[deflate_code]
1715		local huffman_bitlen = _fix_block_literal_huffman_bitlen[deflate_code]
1716		WriteBits(huffman_code, huffman_bitlen)
1717		if deflate_code > 256 then -- Length code
1718			length_code_count = length_code_count + 1
1719			if deflate_code > 264 and deflate_code < 285 then
1720				-- Length code with extra bits
1721				length_code_with_extra_count = length_code_with_extra_count + 1
1722				local extra_bits = lextra_bits[length_code_with_extra_count]
1723				local extra_bits_bitlen =
1724					_literal_deflate_code_to_extra_bitlen[deflate_code-256]
1725				WriteBits(extra_bits, extra_bits_bitlen)
1726			end
1727			-- Write distance code
1728			local dist_code = dcodes[length_code_count]
1729			local dist_huffman_code = _fix_block_dist_huffman_code[dist_code]
1730			WriteBits(dist_huffman_code, 5)
1731
1732			if dist_code > 3 then -- dist code with extra bits
1733				dist_code_with_extra_count = dist_code_with_extra_count + 1
1734				local dist_extra_bits = dextra_bits[dist_code_with_extra_count]
1735				local dist_extra_bits_bitlen = (dist_code-dist_code%2)/2 - 1
1736				WriteBits(dist_extra_bits, dist_extra_bits_bitlen)
1737			end
1738		end
1739	end
1740end
1741
1742-- Get the size of store block without writing any bits into the writer.
1743-- @param block_start The start index of the origin input string
1744-- @param block_end The end index of the origin input string
1745-- @param Total bit lens had been written into the compressed result before,
1746-- because store block needs to shift to byte boundary.
1747-- @return the bit length of the fixed block
1748local function GetStoreBlockSize(block_start, block_end, total_bitlen)
1749	assert(block_end-block_start+1 <= 65535)
1750	local block_bitlen = 3
1751	total_bitlen = total_bitlen + 3
1752	local padding_bitlen = (8-total_bitlen%8)%8
1753	block_bitlen = block_bitlen + padding_bitlen
1754	block_bitlen = block_bitlen + 32
1755	block_bitlen = block_bitlen + (block_end - block_start + 1) * 8
1756	return block_bitlen
1757end
1758
1759-- Write the store block.
1760-- @param ... lots of stuffs
1761-- @return nil
1762local function CompressStoreBlock(WriteBits, WriteString, is_last_block, str
1763	, block_start, block_end, total_bitlen)
1764	assert(block_end-block_start+1 <= 65535)
1765	WriteBits(is_last_block and 1 or 0, 1) -- Last block identifer.
1766	WriteBits(0, 2) -- Store block identifier.
1767	total_bitlen = total_bitlen + 3
1768	local padding_bitlen = (8-total_bitlen%8)%8
1769	if padding_bitlen > 0 then
1770		WriteBits(_pow2[padding_bitlen]-1, padding_bitlen)
1771	end
1772	local size = block_end - block_start + 1
1773	WriteBits(size, 16)
1774
1775	-- Write size's one's complement
1776	local comp = (255 - size % 256) + (255 - (size-size%256)/256)*256
1777	WriteBits(comp, 16)
1778
1779	WriteString(str:sub(block_start, block_end))
1780end
1781
1782-- Do the deflate
1783-- Currently using a simple way to determine the block size
1784-- (This is why the compression ratio is little bit worse than zlib when
1785-- the input size is very large
1786-- The first block is 64KB, the following block is 32KB.
1787-- After each block, there is a memory cleanup operation.
1788-- This is not a fast operation, but it is needed to save memory usage, so
1789-- the memory usage does not grow unboundly. If the data size is less than
1790-- 64KB, then memory cleanup won't happen.
1791-- This function determines whether to use store/fixed/dynamic blocks by
1792-- calculating the block size of each block type and chooses the smallest one.
1793local function Deflate(configs, WriteBits, WriteString, FlushWriter, str
1794	, dictionary)
1795	local string_table = {}
1796	local hash_tables = {}
1797	local is_last_block = nil
1798	local block_start
1799	local block_end
1800	local bitlen_written
1801	local total_bitlen = FlushWriter(_FLUSH_MODE_NO_FLUSH)
1802	local strlen = #str
1803	local offset
1804
1805	local level
1806	local strategy
1807	if configs then
1808		if configs.level then
1809			level = configs.level
1810		end
1811		if configs.strategy then
1812			strategy = configs.strategy
1813		end
1814	end
1815
1816	if not level then
1817		if strlen < 2048 then
1818			level = 7
1819		elseif strlen > 65536 then
1820			level = 3
1821		else
1822			level = 5
1823		end
1824	end
1825
1826	os.queueEvent("nosleep")
1827    os.pullEvent()
1828
1829	while not is_last_block do
1830		if not block_start then
1831			block_start = 1
1832			block_end = 64*1024 - 1
1833			offset = 0
1834		else
1835			block_start = block_end + 1
1836			block_end = block_end + 32*1024
1837			offset = block_start - 32*1024 - 1
1838		end
1839
1840		if block_end >= strlen then
1841			block_end = strlen
1842			is_last_block = true
1843		else
1844			is_last_block = false
1845        end
1846
1847		local lcodes, lextra_bits, lcodes_counts, dcodes, dextra_bits
1848			, dcodes_counts
1849
1850		local HLIT, HDIST, HCLEN, rle_codes_huffman_bitlens
1851			, rle_codes_huffman_codes, rle_deflate_codes
1852			, rle_extra_bits, lcodes_huffman_bitlens, lcodes_huffman_codes
1853			, dcodes_huffman_bitlens, dcodes_huffman_codes
1854
1855		local dynamic_block_bitlen
1856		local fixed_block_bitlen
1857		local store_block_bitlen
1858
1859		if level ~= 0 then
1860
1861			-- GetBlockLZ77 needs block_start to block_end+3 to be loaded.
1862			LoadStringToTable(str, string_table, block_start, block_end + 3
1863				, offset)
1864			if block_start == 1 and dictionary then
1865				local dict_string_table = dictionary.string_table
1866				local dict_strlen = dictionary.strlen
1867				for i=0, (-dict_strlen+1)<-257
1868					and -257 or (-dict_strlen+1), -1 do
1869					string_table[i] = dict_string_table[dict_strlen+i]
1870				end
1871			end
1872
1873			if strategy == "huffman_only" then
1874				lcodes = {}
1875				LoadStringToTable(str, lcodes, block_start, block_end
1876					, block_start-1)
1877				lextra_bits = {}
1878				lcodes_counts = {}
1879				lcodes[block_end - block_start+2] = 256 -- end of block
1880				for i=1, block_end - block_start+2 do
1881					local code = lcodes[i]
1882					lcodes_counts[code] = (lcodes_counts[code] or 0) + 1
1883				end
1884				dcodes = {}
1885				dextra_bits = {}
1886				dcodes_counts = {}
1887			else
1888				lcodes, lextra_bits, lcodes_counts, dcodes, dextra_bits
1889				, dcodes_counts = GetBlockLZ77Result(level, string_table
1890				, hash_tables, block_start, block_end, offset, dictionary
1891				)
1892			end
1893
1894			HLIT, HDIST, HCLEN, rle_codes_huffman_bitlens
1895				, rle_codes_huffman_codes, rle_deflate_codes
1896				, rle_extra_bits, lcodes_huffman_bitlens, lcodes_huffman_codes
1897				, dcodes_huffman_bitlens, dcodes_huffman_codes =
1898				GetBlockDynamicHuffmanHeader(lcodes_counts, dcodes_counts)
1899			dynamic_block_bitlen = GetDynamicHuffmanBlockSize(
1900					lcodes, dcodes, HCLEN, rle_codes_huffman_bitlens
1901					, rle_deflate_codes, lcodes_huffman_bitlens
1902					, dcodes_huffman_bitlens)
1903			fixed_block_bitlen = GetFixedHuffmanBlockSize(lcodes, dcodes)
1904		end
1905
1906		store_block_bitlen = GetStoreBlockSize(block_start, block_end
1907			, total_bitlen)
1908
1909		local min_bitlen = store_block_bitlen
1910		min_bitlen = (fixed_block_bitlen and fixed_block_bitlen < min_bitlen)
1911			and fixed_block_bitlen or min_bitlen
1912		min_bitlen = (dynamic_block_bitlen
1913			and dynamic_block_bitlen < min_bitlen)
1914			and dynamic_block_bitlen or min_bitlen
1915
1916		if level == 0 or (strategy ~= "fixed" and strategy ~= "dynamic" and
1917			store_block_bitlen == min_bitlen) then
1918			CompressStoreBlock(WriteBits, WriteString, is_last_block
1919				, str, block_start, block_end, total_bitlen)
1920			total_bitlen = total_bitlen + store_block_bitlen
1921		elseif strategy ~= "dynamic" and (
1922			strategy == "fixed" or fixed_block_bitlen == min_bitlen) then
1923			CompressFixedHuffmanBlock(WriteBits, is_last_block,
1924					lcodes, lextra_bits, dcodes, dextra_bits)
1925			total_bitlen = total_bitlen + fixed_block_bitlen
1926		elseif strategy == "dynamic" or dynamic_block_bitlen == min_bitlen then
1927			CompressDynamicHuffmanBlock(WriteBits, is_last_block, lcodes
1928				, lextra_bits, dcodes, dextra_bits, HLIT, HDIST, HCLEN
1929				, rle_codes_huffman_bitlens, rle_codes_huffman_codes
1930				, rle_deflate_codes, rle_extra_bits
1931				, lcodes_huffman_bitlens, lcodes_huffman_codes
1932				, dcodes_huffman_bitlens, dcodes_huffman_codes)
1933			total_bitlen = total_bitlen + dynamic_block_bitlen
1934		end
1935
1936		if is_last_block then
1937			bitlen_written = FlushWriter(_FLUSH_MODE_NO_FLUSH)
1938		else
1939			bitlen_written = FlushWriter(_FLUSH_MODE_MEMORY_CLEANUP)
1940		end
1941
1942		assert(bitlen_written == total_bitlen)
1943
1944		-- Memory clean up, so memory consumption does not always grow linearly
1945		-- , even if input string is > 64K.
1946		-- Not a very efficient operation, but this operation won't happen
1947		-- when the input data size is less than 64K.
1948		if not is_last_block then
1949			local j
1950			if dictionary and block_start == 1 then
1951				j = 0
1952				while (string_table[j]) do
1953					string_table[j] = nil
1954					j = j - 1
1955				end
1956			end
1957			dictionary = nil
1958			j = 1
1959			for i = block_end-32767, block_end do
1960				string_table[j] = string_table[i-offset]
1961				j = j + 1
1962            end
1963            local delete = {}
1964			for k, t in pairs(hash_tables) do
1965				local tSize = #t
1966				if tSize > 0 and block_end+1 - t[1] > 32768 then
1967                    if tSize == 1 then
1968                        if _G.os and _G.os.pullEvent then table.insert(delete, k)
1969						else hash_tables[k] = nil end
1970					else
1971						local new = {}
1972						local newSize = 0
1973						for i = 2, tSize do
1974							j = t[i]
1975							if block_end+1 - j <= 32768 then
1976								newSize = newSize + 1
1977								new[newSize] = j
1978							end
1979						end
1980						hash_tables[k] = new
1981					end
1982				end
1983            end
1984            if #delete > 0 then 
1985                for _,k in pairs(delete) do hash_tables[k] = nil end 
1986            end
1987        end
1988
1989        if _G.os and _G.os.pullEvent then -- ComputerCraft requires this for long-running processes
1990			write(".")
1991			os.queueEvent("nosleep")
1992            os.pullEvent()
1993        end
1994	end
1995	print()
1996end
1997
1998--- The description to compression configuration table. <br>
1999-- Any field can be nil to use its default. <br>
2000-- Table with keys other than those below is an invalid table.
2001-- @class table
2002-- @name compression_configs
2003-- @field level The compression level ranged from 0 to 9. 0 is no compression.
2004-- 9 is the slowest but best compression. Use nil for default level.
2005-- @field strategy The compression strategy. "fixed" to only use fixed deflate
2006-- compression block. "dynamic" to only use dynamic block. "huffman_only" to
2007-- do no LZ77 compression. Only do huffman compression.
2008
2009
2010-- @see LibDeflate:CompressDeflate(str, configs)
2011-- @see LibDeflate:CompressDeflateWithDict(str, dictionary, configs)
2012local function CompressDeflateInternal(str, dictionary, configs)
2013	local WriteBits, WriteString, FlushWriter = CreateWriter()
2014	Deflate(configs, WriteBits, WriteString, FlushWriter, str, dictionary)
2015	local total_bitlen, result = FlushWriter(_FLUSH_MODE_OUTPUT)
2016	local padding_bitlen = (8-total_bitlen%8)%8
2017	return result, padding_bitlen
2018end
2019
2020-- @see LibDeflate:CompressZlib
2021-- @see LibDeflate:CompressZlibWithDict
2022local function CompressZlibInternal(str, dictionary, configs)
2023	local WriteBits, WriteString, FlushWriter = CreateWriter()
2024
2025	local CM = 8 -- Compression method
2026	local CINFO = 7 --Window Size = 32K
2027	local CMF = CINFO*16+CM
2028	WriteBits(CMF, 8)
2029
2030	local FDIST = dictionary and 1 or 0
2031	local FLEVEL = 2 -- Default compression
2032	local FLG = FLEVEL*64+FDIST*32
2033	local FCHECK = (31-(CMF*256+FLG)%31)
2034	-- The FCHECK value must be such that CMF and FLG,
2035	-- when viewed as a 16-bit unsigned integer stored
2036	-- in MSB order (CMF*256 + FLG), is a multiple of 31.
2037	FLG = FLG + FCHECK
2038	WriteBits(FLG, 8)
2039
2040	if FDIST == 1 then
2041		local adler32 = dictionary.adler32
2042		local byte0 = adler32 % 256
2043		adler32 = (adler32 - byte0) / 256
2044		local byte1 = adler32 % 256
2045		adler32 = (adler32 - byte1) / 256
2046		local byte2 = adler32 % 256
2047		adler32 = (adler32 - byte2) / 256
2048		local byte3 = adler32 % 256
2049		WriteBits(byte3, 8)
2050		WriteBits(byte2, 8)
2051		WriteBits(byte1, 8)
2052		WriteBits(byte0, 8)
2053	end
2054
2055	Deflate(configs, WriteBits, WriteString, FlushWriter, str, dictionary)
2056	FlushWriter(_FLUSH_MODE_BYTE_BOUNDARY)
2057
2058	local adler32 = LibDeflate:Adler32(str)
2059
2060	-- Most significant byte first
2061	local byte3 = adler32%256
2062	adler32 = (adler32 - byte3) / 256
2063	local byte2 = adler32%256
2064	adler32 = (adler32 - byte2) / 256
2065	local byte1 = adler32%256
2066	adler32 = (adler32 - byte1) / 256
2067	local byte0 = adler32%256
2068
2069	WriteBits(byte0, 8)
2070	WriteBits(byte1, 8)
2071	WriteBits(byte2, 8)
2072	WriteBits(byte3, 8)
2073	local total_bitlen, result = FlushWriter(_FLUSH_MODE_OUTPUT)
2074	local padding_bitlen = (8-total_bitlen%8)%8
2075	return result, padding_bitlen
2076end
2077
2078--- Compress using the raw deflate format.
2079-- @param str [string] The data to be compressed.
2080-- @param configs [table/nil] The configuration table to control the compression
2081-- . If nil, use the default configuration.
2082-- @return [string] The compressed data.
2083-- @return [integer] The number of bits padded at the end of output.
2084-- 0 <= bits < 8  <br>
2085-- This means the most significant "bits" of the last byte of the returned
2086-- compressed data are padding bits and they don't affect decompression.
2087-- You don't need to use this value unless you want to do some postprocessing
2088-- to the compressed data.
2089-- @see compression_configs
2090-- @see LibDeflate:DecompressDeflate
2091function LibDeflate:CompressDeflate(str, configs)
2092	local arg_valid, arg_err = IsValidArguments(str, false, nil, true, configs)
2093	if not arg_valid then
2094		error(("Usage: LibDeflate:CompressDeflate(str, configs): "
2095			..arg_err), 2)
2096	end
2097	return CompressDeflateInternal(str, nil, configs)
2098end
2099
2100--- Compress using the raw deflate format with a preset dictionary.
2101-- @param str [string] The data to be compressed.
2102-- @param dictionary [table] The preset dictionary produced by
2103-- LibDeflate:CreateDictionary
2104-- @param configs [table/nil] The configuration table to control the compression
2105-- . If nil, use the default configuration.
2106-- @return [string] The compressed data.
2107-- @return [integer] The number of bits padded at the end of output.
2108-- 0 <= bits < 8  <br>
2109-- This means the most significant "bits" of the last byte of the returned
2110-- compressed data are padding bits and they don't affect decompression.
2111-- You don't need to use this value unless you want to do some postprocessing
2112-- to the compressed data.
2113-- @see compression_configs
2114-- @see LibDeflate:CreateDictionary
2115-- @see LibDeflate:DecompressDeflateWithDict
2116function LibDeflate:CompressDeflateWithDict(str, dictionary, configs)
2117	local arg_valid, arg_err = IsValidArguments(str, true, dictionary
2118		, true, configs)
2119	if not arg_valid then
2120		error(("Usage: LibDeflate:CompressDeflateWithDict"
2121			.."(str, dictionary, configs): "
2122			..arg_err), 2)
2123	end
2124	return CompressDeflateInternal(str, dictionary, configs)
2125end
2126
2127--- Compress using the zlib format.
2128-- @param str [string] the data to be compressed.
2129-- @param configs [table/nil] The configuration table to control the compression
2130-- . If nil, use the default configuration.
2131-- @return [string] The compressed data.
2132-- @return [integer] The number of bits padded at the end of output.
2133-- Should always be 0.
2134-- Zlib formatted compressed data never has padding bits at the end.
2135-- @see compression_configs
2136-- @see LibDeflate:DecompressZlib
2137function LibDeflate:CompressZlib(str, configs)
2138	local arg_valid, arg_err = IsValidArguments(str, false, nil, true, configs)
2139	if not arg_valid then
2140		error(("Usage: LibDeflate:CompressZlib(str, configs): "
2141			..arg_err), 2)
2142	end
2143	return CompressZlibInternal(str, nil, configs)
2144end
2145
2146--- Compress using the zlib format with a preset dictionary.
2147-- @param str [string] the data to be compressed.
2148-- @param dictionary [table] A preset dictionary produced
2149-- by LibDeflate:CreateDictionary()
2150-- @param configs [table/nil] The configuration table to control the compression
2151-- . If nil, use the default configuration.
2152-- @return [string] The compressed data.
2153-- @return [integer] The number of bits padded at the end of output.
2154-- Should always be 0.
2155-- Zlib formatted compressed data never has padding bits at the end.
2156-- @see compression_configs
2157-- @see LibDeflate:CreateDictionary
2158-- @see LibDeflate:DecompressZlibWithDict
2159function LibDeflate:CompressZlibWithDict(str, dictionary, configs)
2160	local arg_valid, arg_err = IsValidArguments(str, true, dictionary
2161		, true, configs)
2162	if not arg_valid then
2163		error(("Usage: LibDeflate:CompressZlibWithDict"
2164			.."(str, dictionary, configs): "
2165			..arg_err), 2)
2166	end
2167	return CompressZlibInternal(str, dictionary, configs)
2168end
2169
2170local function time()
2171    if os == nil then return 0
2172    elseif os.epoch ~= nil then return math.floor(os.epoch("utc") / 1000)
2173        -- ComputerCraft's os.time() gives in-game time, os.epoch gives POSIX time in ms
2174    elseif os.time() < 30 then return 0 -- ComputerCraft 1.79 and below don't have os.epoch(), so no time.
2175    else return os.time() end -- All other Luas.
2176end
2177
2178local function byte(num, b) return math.floor(num / math.pow(2, b*8)) % 0x100 end
2179
2180--- Compress using the gzip format.
2181-- @param str [string] the data to be compressed.
2182-- @param configs [table/nil] The configuration table to control the compression
2183-- . If nil, use the default configuration.
2184-- @return [string] The compressed data with gzip headers.
2185-- @see compression_configs
2186-- @see LibDeflate:DecompressGzip
2187function LibDeflate:CompressGzip(str, configs)
2188    local arg_valid, arg_err = IsValidArguments(str, false, nil, true, configs)
2189	if not arg_valid then
2190		error(("Usage: LibDeflate:CompressGzip(str, configs): "
2191			..arg_err), 2)
2192    end
2193    local res, err = CompressDeflateInternal(str, nil, configs)
2194    if res == nil then return res, err end
2195    local t = time()
2196    local cf = 0
2197    local crc = self:CRC32(str)
2198    local len = string.len(str)
2199    if configs ~= nil and configs.level ~= nil then
2200        if configs.level == 0 then cf = 0x04
2201        elseif configs.level == 9 then cf = 0x02 end
2202    end
2203    return string_char(0x1f, 0x8b, 8, 0, byte(t, 0), byte(t, 1), byte(t, 2), 
2204        byte(t, 3), cf, 0xFF) .. res .. string_char(byte(crc, 0), byte(crc, 1),
2205        byte(crc, 2), byte(crc, 3), byte(len, 0), byte(len, 1), byte(len, 2), byte(len, 3)), 0
2206end
2207
2208--[[ --------------------------------------------------------------------------
2209	Decompress code
2210--]] --------------------------------------------------------------------------
2211
2212--[[
2213	Create a reader to easily reader stuffs as the unit of bits.
2214	Return values:
2215	1. ReadBits(bitlen)
2216	2. ReadBytes(bytelen, buffer, buffer_size)
2217	3. Decode(huffman_bitlen_count, huffman_symbol, min_bitlen)
2218	4. ReaderBitlenLeft()
2219	5. SkipToByteBoundary()
2220--]]
2221local function CreateReader(input_string)
2222	local input = input_string
2223	local input_strlen = #input_string
2224	local input_next_byte_pos = 1
2225	local cache_bitlen = 0
2226	local cache = 0
2227
2228	-- Read some bits.
2229	-- To improve speed, this function does not
2230	-- check if the input has been exhausted.
2231	-- Use ReaderBitlenLeft() < 0 to check it.
2232	-- @param bitlen the number of bits to read
2233	-- @return the data is read.
2234	local function ReadBits(bitlen)
2235		local rshift_mask = _pow2[bitlen]
2236		local code
2237		if bitlen <= cache_bitlen then
2238			code = cache % rshift_mask
2239			cache = (cache - code) / rshift_mask
2240			cache_bitlen = cache_bitlen - bitlen
2241		else -- Whether input has been exhausted is not checked.
2242			local lshift_mask = _pow2[cache_bitlen]
2243			local byte1, byte2, byte3, byte4 = string_byte(input
2244				, input_next_byte_pos, input_next_byte_pos+3)
2245			-- This requires lua number to be at least double ()
2246			cache = cache + ((byte1 or 0)+(byte2 or 0)*256
2247				+ (byte3 or 0)*65536+(byte4 or 0)*16777216)*lshift_mask
2248			input_next_byte_pos = input_next_byte_pos + 4
2249			cache_bitlen = cache_bitlen + 32 - bitlen
2250			code = cache % rshift_mask
2251			cache = (cache - code) / rshift_mask
2252		end
2253		return code
2254	end
2255
2256	-- Read some bytes from the reader.
2257	-- Assume reader is on the byte boundary.
2258	-- @param bytelen The number of bytes to be read.
2259	-- @param buffer The byte read will be stored into this buffer.
2260	-- @param buffer_size The buffer will be modified starting from
2261	--	buffer[buffer_size+1], ending at buffer[buffer_size+bytelen-1]
2262	-- @return the new buffer_size
2263	local function ReadBytes(bytelen, buffer, buffer_size)
2264		assert(cache_bitlen % 8 == 0)
2265
2266		local byte_from_cache = (cache_bitlen/8 < bytelen)
2267			and (cache_bitlen/8) or bytelen
2268		for _=1, byte_from_cache do
2269			local _byte = cache % 256
2270			buffer_size = buffer_size + 1
2271			buffer[buffer_size] = string_char(_byte)
2272			cache = (cache - _byte) / 256
2273		end
2274		cache_bitlen = cache_bitlen - byte_from_cache*8
2275		bytelen = bytelen - byte_from_cache
2276		if (input_strlen - input_next_byte_pos - bytelen + 1) * 8
2277			+ cache_bitlen < 0 then
2278			return -1 -- out of input
2279		end
2280		for i=input_next_byte_pos, input_next_byte_pos+bytelen-1 do
2281			buffer_size = buffer_size + 1
2282			buffer[buffer_size] = string_sub(input, i, i)
2283		end
2284
2285		input_next_byte_pos = input_next_byte_pos + bytelen
2286		return buffer_size
2287	end
2288
2289	-- Decode huffman code
2290	-- To improve speed, this function does not check
2291	-- if the input has been exhausted.
2292	-- Use ReaderBitlenLeft() < 0 to check it.
2293	-- Credits for Mark Adler. This code is from puff:Decode()
2294	-- @see puff:Decode(...)
2295	-- @param huffman_bitlen_count
2296	-- @param huffman_symbol
2297	-- @param min_bitlen The minimum huffman bit length of all symbols
2298	-- @return The decoded deflate code.
2299	--	Negative value is returned if decoding fails.
2300	local function Decode(huffman_bitlen_counts, huffman_symbols, min_bitlen)
2301		local code = 0
2302		local first = 0
2303		local index = 0
2304		local count
2305		if min_bitlen > 0 then
2306			if cache_bitlen < 15 and input then
2307				local lshift_mask = _pow2[cache_bitlen]
2308				local byte1, byte2, byte3, byte4 =
2309					string_byte(input, input_next_byte_pos
2310					, input_next_byte_pos+3)
2311				-- This requires lua number to be at least double ()
2312				cache = cache + ((byte1 or 0)+(byte2 or 0)*256
2313					+(byte3 or 0)*65536+(byte4 or 0)*16777216)*lshift_mask
2314				input_next_byte_pos = input_next_byte_pos + 4
2315				cache_bitlen = cache_bitlen + 32
2316			end
2317
2318			local rshift_mask = _pow2[min_bitlen]
2319			cache_bitlen = cache_bitlen - min_bitlen
2320			code = cache % rshift_mask
2321			cache = (cache - code) / rshift_mask
2322			-- Reverse the bits
2323			code = _reverse_bits_tbl[min_bitlen][code]
2324
2325			count = huffman_bitlen_counts[min_bitlen]
2326			if code < count then
2327				return huffman_symbols[code]
2328			end
2329			index = count
2330			first = count * 2
2331			code = code * 2
2332		end
2333
2334		for bitlen = min_bitlen+1, 15 do
2335			local bit
2336			bit = cache % 2
2337			cache = (cache - bit) / 2
2338			cache_bitlen = cache_bitlen - 1
2339
2340			code = (bit==1) and (code + 1 - code % 2) or code
2341			count = huffman_bitlen_counts[bitlen] or 0
2342			local diff = code - first
2343			if diff < count then
2344				return huffman_symbols[index + diff]
2345			end
2346			index = index + count
2347			first = first + count
2348			first = first * 2
2349			code = code * 2
2350		end
2351		-- invalid literal/length or distance code
2352		-- in fixed or dynamic block (run out of code)
2353		return -10
2354	end
2355
2356	local function ReaderBitlenLeft()
2357		return (input_strlen - input_next_byte_pos + 1) * 8 + cache_bitlen
2358	end
2359
2360	local function SkipToByteBoundary()
2361		local skipped_bitlen = cache_bitlen%8
2362		local rshift_mask = _pow2[skipped_bitlen]
2363		cache_bitlen = cache_bitlen - skipped_bitlen
2364		cache = (cache - cache % rshift_mask) / rshift_mask
2365	end
2366
2367	return ReadBits, ReadBytes, Decode, ReaderBitlenLeft, SkipToByteBoundary
2368end
2369
2370-- Create a deflate state, so I can pass in less arguments to functions.
2371-- @param str the whole string to be decompressed.
2372-- @param dictionary The preset dictionary. nil if not provided.
2373--		This dictionary should be produced by LibDeflate:CreateDictionary(str)
2374-- @return The decomrpess state.
2375local function CreateDecompressState(str, dictionary)
2376	local ReadBits, ReadBytes, Decode, ReaderBitlenLeft
2377		, SkipToByteBoundary = CreateReader(str)
2378	local state =
2379	{
2380		ReadBits = ReadBits,
2381		ReadBytes = ReadBytes,
2382		Decode = Decode,
2383		ReaderBitlenLeft = ReaderBitlenLeft,
2384		SkipToByteBoundary = SkipToByteBoundary,
2385		buffer_size = 0,
2386		buffer = {},
2387		result_buffer = {},
2388		dictionary = dictionary,
2389	}
2390	return state
2391end
2392
2393-- Get the stuffs needed to decode huffman codes
2394-- @see puff.c:construct(...)
2395-- @param huffman_bitlen The huffman bit length of the huffman codes.
2396-- @param max_symbol The maximum symbol
2397-- @param max_bitlen The min huffman bit length of all codes
2398-- @return zero or positive for success, negative for failure.
2399-- @return The count of each huffman bit length.
2400-- @return A table to convert huffman codes to deflate codes.
2401-- @return The minimum huffman bit length.
2402local function GetHuffmanForDecode(huffman_bitlens, max_symbol, max_bitlen)
2403	local huffman_bitlen_counts = {}
2404	local min_bitlen = max_bitlen
2405	for symbol = 0, max_symbol do
2406		local bitlen = huffman_bitlens[symbol] or 0
2407		min_bitlen = (bitlen > 0 and bitlen < min_bitlen)
2408			and bitlen or min_bitlen
2409		huffman_bitlen_counts[bitlen] = (huffman_bitlen_counts[bitlen] or 0)+1
2410	end
2411
2412	if huffman_bitlen_counts[0] == max_symbol+1 then -- No Codes
2413		return 0, huffman_bitlen_counts, {}, 0 -- Complete, but decode will fail
2414	end
2415
2416	local left = 1
2417	for len = 1, max_bitlen do
2418		left = left * 2
2419		left = left - (huffman_bitlen_counts[len] or 0)
2420		if left < 0 then
2421			return left -- Over-subscribed, return negative
2422		end
2423	end
2424
2425	-- Generate offsets info symbol table for each length for sorting
2426	local offsets = {}
2427	offsets[1] = 0
2428	for len = 1, max_bitlen-1 do
2429		offsets[len + 1] = offsets[len] + (huffman_bitlen_counts[len] or 0)
2430	end
2431
2432	local huffman_symbols = {}
2433	for symbol = 0, max_symbol do
2434		local bitlen = huffman_bitlens[symbol] or 0
2435		if bitlen ~= 0 then
2436			local offset = offsets[bitlen]
2437			huffman_symbols[offset] = symbol
2438			offsets[bitlen] = offsets[bitlen] + 1
2439		end
2440	end
2441
2442	-- Return zero for complete set, positive for incomplete set.
2443	return left, huffman_bitlen_counts, huffman_symbols, min_bitlen
2444end
2445
2446-- Decode a fixed or dynamic huffman blocks, excluding last block identifier
2447-- and block type identifer.
2448-- @see puff.c:codes()
2449-- @param state decompression state that will be modified by this function.
2450--	@see CreateDecompressState
2451-- @param ... Read the source code
2452-- @return 0 on success, other value on failure.
2453local function DecodeUntilEndOfBlock(state, lcodes_huffman_bitlens
2454	, lcodes_huffman_symbols, lcodes_huffman_min_bitlen
2455	, dcodes_huffman_bitlens, dcodes_huffman_symbols
2456	, dcodes_huffman_min_bitlen)
2457	local buffer, buffer_size, ReadBits, Decode, ReaderBitlenLeft
2458		, result_buffer =
2459		state.buffer, state.buffer_size, state.ReadBits, state.Decode
2460		, state.ReaderBitlenLeft, state.result_buffer
2461	local dictionary = state.dictionary
2462	local dict_string_table
2463	local dict_strlen
2464
2465	local buffer_end = 1
2466	if dictionary and not buffer[0] then
2467		-- If there is a dictionary, copy the last 258 bytes into
2468		-- the string_table to make the copy in the main loop quicker.
2469		-- This is done only once per decompression.
2470		dict_string_table = dictionary.string_table
2471		dict_strlen = dictionary.strlen
2472		buffer_end = -dict_strlen + 1
2473		for i=0, (-dict_strlen+1)<-257 and -257 or (-dict_strlen+1), -1 do
2474			buffer[i] = _byte_to_char[dict_string_table[dict_strlen+i]]
2475		end
2476	end
2477
2478	repeat
2479		local symbol = Decode(lcodes_huffman_bitlens
2480			, lcodes_huffman_symbols, lcodes_huffman_min_bitlen)
2481		if symbol < 0 or symbol > 285 then
2482		-- invalid literal/length or distance code in fixed or dynamic block
2483			return -10
2484		elseif symbol < 256 then -- Literal
2485			buffer_size = buffer_size + 1
2486			buffer[buffer_size] = _byte_to_char[symbol]
2487		elseif symbol > 256 then -- Length code
2488			symbol = symbol - 256
2489			local bitlen = _literal_deflate_code_to_base_len[symbol]
2490			bitlen = (symbol >= 8)
2491				 and (bitlen
2492				 + ReadBits(_literal_deflate_code_to_extra_bitlen[symbol]))
2493					or bitlen
2494			symbol = Decode(dcodes_huffman_bitlens, dcodes_huffman_symbols
2495				, dcodes_huffman_min_bitlen)
2496			if symbol < 0 or symbol > 29 then
2497			-- invalid literal/length or distance code in fixed or dynamic block
2498				return -10
2499			end
2500			local dist = _dist_deflate_code_to_base_dist[symbol]
2501			dist = (dist > 4) and (dist
2502				+ ReadBits(_dist_deflate_code_to_extra_bitlen[symbol])) or dist
2503
2504			local char_buffer_index = buffer_size-dist+1
2505			if char_buffer_index < buffer_end then
2506			-- distance is too far back in fixed or dynamic block
2507				return -11
2508			end
2509			if char_buffer_index >= -257 then
2510				for _=1, bitlen do
2511					buffer_size = buffer_size + 1
2512					buffer[buffer_size] = buffer[char_buffer_index]
2513					char_buffer_index = char_buffer_index + 1
2514				end
2515			else
2516				char_buffer_index = dict_strlen + char_buffer_index
2517				for _=1, bitlen do
2518					buffer_size = buffer_size + 1
2519					buffer[buffer_size] =
2520					_byte_to_char[dict_string_table[char_buffer_index]]
2521					char_buffer_index = char_buffer_index + 1
2522				end
2523			end
2524		end
2525
2526		if ReaderBitlenLeft() < 0 then
2527			return 2 -- available inflate data did not terminate
2528		end
2529
2530		if buffer_size >= 65536 then
2531			result_buffer[#result_buffer+1] =
2532				table_concat(buffer, "", 1, 32768)
2533			for i=32769, buffer_size do
2534				buffer[i-32768] = buffer[i]
2535			end
2536			buffer_size = buffer_size - 32768
2537			buffer[buffer_size+1] = nil
2538			-- NOTE: buffer[32769..end] and buffer[-257..0] are not cleared.
2539			-- This is why "buffer_size" variable is needed.
2540		end
2541	until symbol == 256
2542
2543	state.buffer_size = buffer_size
2544
2545	return 0
2546end
2547
2548-- Decompress a store block
2549-- @param state decompression state that will be modified by this function.
2550-- @return 0 if succeeds, other value if fails.
2551local function DecompressStoreBlock(state)
2552	local buffer, buffer_size, ReadBits, ReadBytes, ReaderBitlenLeft
2553		, SkipToByteBoundary, result_buffer =
2554		state.buffer, state.buffer_size, state.ReadBits, state.ReadBytes
2555		, state.ReaderBitlenLeft, state.SkipToByteBoundary, state.result_buffer
2556
2557	SkipToByteBoundary()
2558	local bytelen = ReadBits(16)
2559	if ReaderBitlenLeft() < 0 then
2560		return 2 -- available inflate data did not terminate
2561	end
2562	local bytelenComp = ReadBits(16)
2563	if ReaderBitlenLeft() < 0 then
2564		return 2 -- available inflate data did not terminate
2565	end
2566
2567	if bytelen % 256 + bytelenComp % 256 ~= 255 then
2568		return -2 -- Not one's complement
2569	end
2570	if (bytelen-bytelen % 256)/256
2571		+ (bytelenComp-bytelenComp % 256)/256 ~= 255 then
2572		return -2 -- Not one's complement
2573	end
2574
2575	-- Note that ReadBytes will skip to the next byte boundary first.
2576	buffer_size = ReadBytes(bytelen, buffer, buffer_size)
2577	if buffer_size < 0 then
2578		return 2 -- available inflate data did not terminate
2579	end
2580
2581	-- memory clean up when there are enough bytes in the buffer.
2582	if buffer_size >= 65536 then
2583		result_buffer[#result_buffer+1] = table_concat(buffer, "", 1, 32768)
2584		for i=32769, buffer_size do
2585			buffer[i-32768] = buffer[i]
2586		end
2587		buffer_size = buffer_size - 32768
2588		buffer[buffer_size+1] = nil
2589	end
2590	state.buffer_size = buffer_size
2591	return 0
2592end
2593
2594-- Decompress a fixed block
2595-- @param state decompression state that will be modified by this function.
2596-- @return 0 if succeeds other value if fails.
2597local function DecompressFixBlock(state)
2598	return DecodeUntilEndOfBlock(state
2599		, _fix_block_literal_huffman_bitlen_count
2600		, _fix_block_literal_huffman_to_deflate_code, 7
2601		, _fix_block_dist_huffman_bitlen_count
2602		, _fix_block_dist_huffman_to_deflate_code, 5)
2603end
2604
2605-- Decompress a dynamic block
2606-- @param state decompression state that will be modified by this function.
2607-- @return 0 if success, other value if fails.
2608local function DecompressDynamicBlock(state)
2609	local ReadBits, Decode = state.ReadBits, state.Decode
2610	local nlen = ReadBits(5) + 257
2611	local ndist = ReadBits(5) + 1
2612	local ncode = ReadBits(4) + 4
2613	if nlen > 286 or ndist > 30 then
2614		-- dynamic block code description: too many length or distance codes
2615		return -3
2616	end
2617
2618	local rle_codes_huffman_bitlens = {}
2619
2620	for i = 1, ncode do
2621		rle_codes_huffman_bitlens[_rle_codes_huffman_bitlen_order[i]] =
2622			ReadBits(3)
2623	end
2624
2625	local rle_codes_err, rle_codes_huffman_bitlen_counts,
2626		rle_codes_huffman_symbols, rle_codes_huffman_min_bitlen =
2627		GetHuffmanForDecode(rle_codes_huffman_bitlens, 18, 7)
2628	if rle_codes_err ~= 0 then -- Require complete code set here
2629		-- dynamic block code description: code lengths codes incomplete
2630		return -4
2631	end
2632
2633	local lcodes_huffman_bitlens = {}
2634	local dcodes_huffman_bitlens = {}
2635	-- Read length/literal and distance code length tables
2636	local index = 0
2637	while index < nlen + ndist do
2638		local symbol -- Decoded value
2639		local bitlen -- Last length to repeat
2640
2641		symbol = Decode(rle_codes_huffman_bitlen_counts
2642			, rle_codes_huffman_symbols, rle_codes_huffman_min_bitlen)
2643
2644		if symbol < 0 then
2645			return symbol -- Invalid symbol
2646		elseif symbol < 16 then
2647			if index < nlen then
2648				lcodes_huffman_bitlens[index] = symbol
2649			else
2650				dcodes_huffman_bitlens[index-nlen] = symbol
2651			end
2652			index = index + 1
2653		else
2654			bitlen = 0
2655			if symbol == 16 then
2656				if index == 0 then
2657					-- dynamic block code description: repeat lengths
2658					-- with no first length
2659					return -5
2660				end
2661				if index-1 < nlen then
2662					bitlen = lcodes_huffman_bitlens[index-1]
2663				else
2664					bitlen = dcodes_huffman_bitlens[index-nlen-1]
2665				end
2666				symbol = 3 + ReadBits(2)
2667			elseif symbol == 17 then -- Repeat zero 3..10 times
2668				symbol = 3 + ReadBits(3)
2669			else -- == 18, repeat zero 11.138 times
2670				symbol = 11 + ReadBits(7)
2671			end
2672			if index + symbol > nlen + ndist then
2673				-- dynamic block code description:
2674				-- repeat more than specified lengths
2675				return -6
2676			end
2677			while symbol > 0 do -- Repeat last or zero symbol times
2678				symbol = symbol - 1
2679				if index < nlen then
2680					lcodes_huffman_bitlens[index] = bitlen
2681				else
2682					dcodes_huffman_bitlens[index-nlen] = bitlen
2683				end
2684				index = index + 1
2685			end
2686		end
2687	end
2688
2689	if (lcodes_huffman_bitlens[256] or 0) == 0 then
2690		-- dynamic block code description: missing end-of-block code
2691		return -9
2692	end
2693
2694	local lcodes_err, lcodes_huffman_bitlen_counts
2695		, lcodes_huffman_symbols, lcodes_huffman_min_bitlen =
2696		GetHuffmanForDecode(lcodes_huffman_bitlens, nlen-1, 15)
2697	--dynamic block code description: invalid literal/length code lengths,
2698	-- Incomplete code ok only for single length 1 code
2699	if (lcodes_err ~=0 and (lcodes_err < 0
2700		or nlen ~= (lcodes_huffman_bitlen_counts[0] or 0)
2701			+(lcodes_huffman_bitlen_counts[1] or 0))) then
2702		return -7
2703	end
2704
2705	local dcodes_err, dcodes_huffman_bitlen_counts
2706		, dcodes_huffman_symbols, dcodes_huffman_min_bitlen =
2707		GetHuffmanForDecode(dcodes_huffman_bitlens, ndist-1, 15)
2708	-- dynamic block code description: invalid distance code lengths,
2709	-- Incomplete code ok only for single length 1 code
2710	if (dcodes_err ~=0 and (dcodes_err < 0
2711		or ndist ~= (dcodes_huffman_bitlen_counts[0] or 0)
2712			+ (dcodes_huffman_bitlen_counts[1] or 0))) then
2713		return -8
2714	end
2715
2716	-- Build buffman table for literal/length codes
2717	return DecodeUntilEndOfBlock(state, lcodes_huffman_bitlen_counts
2718		, lcodes_huffman_symbols, lcodes_huffman_min_bitlen
2719		, dcodes_huffman_bitlen_counts, dcodes_huffman_symbols
2720		, dcodes_huffman_min_bitlen)
2721end
2722
2723-- Decompress a deflate stream
2724-- @param state: a decompression state
2725-- @return the decompressed string if succeeds. nil if fails.
2726local function Inflate(state)
2727	local ReadBits = state.ReadBits
2728
2729	local is_last_block
2730	while not is_last_block do
2731		is_last_block = (ReadBits(1) == 1)
2732		local block_type = ReadBits(2)
2733		local status
2734		if block_type == 0 then
2735			status = DecompressStoreBlock(state)
2736		elseif block_type == 1 then
2737			status = DecompressFixBlock(state)
2738		elseif block_type == 2 then
2739			status = DecompressDynamicBlock(state)
2740		else
2741			return nil, -1 -- invalid block type (type == 3)
2742		end
2743		if status ~= 0 then
2744			return nil, status
2745        end
2746        -- ComputerCraft requires this for long-running processes
2747        if os and os.pullEvent then
2748            os.queueEvent("nosleep")
2749            os.pullEvent()
2750        end
2751	end
2752
2753	state.result_buffer[#state.result_buffer+1] =
2754		table_concat(state.buffer, "", 1, state.buffer_size)
2755	local result = table_concat(state.result_buffer)
2756	return result
2757end
2758
2759-- @see LibDeflate:DecompressDeflate(str)
2760-- @see LibDeflate:DecompressDeflateWithDict(str, dictionary)
2761local function DecompressDeflateInternal(str, dictionary)
2762	local state = CreateDecompressState(str, dictionary)
2763	local result, status = Inflate(state)
2764	if not result then
2765		return nil, status
2766	end
2767
2768	local bitlen_left = state.ReaderBitlenLeft()
2769	local bytelen_left = (bitlen_left - bitlen_left % 8) / 8
2770	return result, bytelen_left
2771end
2772
2773-- @see LibDeflate:DecompressZlib(str)
2774-- @see LibDeflate:DecompressZlibWithDict(str)
2775local function DecompressZlibInternal(str, dictionary)
2776	local state = CreateDecompressState(str, dictionary)
2777	local ReadBits = state.ReadBits
2778
2779	local CMF = ReadBits(8)
2780	if state.ReaderBitlenLeft() < 0 then
2781		return nil, 2 -- available inflate data did not terminate
2782	end
2783	local CM = CMF % 16
2784	local CINFO = (CMF - CM) / 16
2785	if CM ~= 8 then
2786		return nil, -12 -- invalid compression method
2787	end
2788	if CINFO > 7 then
2789		return nil, -13 -- invalid window size
2790	end
2791
2792	local FLG = ReadBits(8)
2793	if state.ReaderBitlenLeft() < 0 then
2794		return nil, 2 -- available inflate data did not terminate
2795	end
2796	if (CMF*256+FLG)%31 ~= 0 then
2797		return nil, -14 -- invalid header checksum
2798	end
2799
2800	local FDIST = ((FLG-FLG%32)/32 % 2)
2801	local FLEVEL = ((FLG-FLG%64)/64 % 4) -- luacheck: ignore FLEVEL
2802
2803	if FDIST == 1 then
2804		if not dictionary then
2805			return nil, -16 -- need dictonary, but dictionary is not provided.
2806		end
2807		local byte3 = ReadBits(8)
2808		local byte2 = ReadBits(8)
2809		local byte1 = ReadBits(8)
2810		local byte0 = ReadBits(8)
2811		local actual_adler32 = byte3*16777216+byte2*65536+byte1*256+byte0
2812		if state.ReaderBitlenLeft() < 0 then
2813			return nil, 2 -- available inflate data did not terminate
2814		end
2815		if not IsEqualAdler32(actual_adler32, dictionary.adler32) then
2816			return nil, -17 -- dictionary adler32 does not match
2817		end
2818	end
2819	local result, status = Inflate(state)
2820	if not result then
2821		return nil, status
2822	end
2823	state.SkipToByteBoundary()
2824
2825	local adler_byte0 = ReadBits(8)
2826	local adler_byte1 = ReadBits(8)
2827	local adler_byte2 = ReadBits(8)
2828	local adler_byte3 = ReadBits(8)
2829	if state.ReaderBitlenLeft() < 0 then
2830		return nil, 2 -- available inflate data did not terminate
2831	end
2832
2833	local adler32_expected = adler_byte0*16777216
2834		+ adler_byte1*65536 + adler_byte2*256 + adler_byte3
2835	local adler32_actual = LibDeflate:Adler32(result)
2836	if not IsEqualAdler32(adler32_expected, adler32_actual) then
2837		return nil, -15 -- Adler32 checksum does not match
2838	end
2839
2840	local bitlen_left = state.ReaderBitlenLeft()
2841	local bytelen_left = (bitlen_left - bitlen_left % 8) / 8
2842	return result, bytelen_left
2843end
2844
2845--- Decompress a raw deflate compressed data.
2846-- @param str [string] The data to be decompressed.
2847-- @return [string/nil] If the decompression succeeds, return the decompressed
2848-- data. If the decompression fails, return nil. You should check if this return
2849-- value is non-nil to know if the decompression succeeds.
2850-- @return [integer] If the decompression succeeds, return the number of
2851-- unprocessed bytes in the input compressed data. This return value is a
2852-- positive integer if the input data is a valid compressed data appended by an
2853-- arbitary non-empty string. This return value is 0 if the input data does not
2854-- contain any extra bytes.<br>
2855-- If the decompression fails (The first return value of this function is nil),
2856-- this return value is undefined.
2857-- @see LibDeflate:CompressDeflate
2858function LibDeflate:DecompressDeflate(str)
2859	local arg_valid, arg_err = IsValidArguments(str)
2860	if not arg_valid then
2861		error(("Usage: LibDeflate:DecompressDeflate(str): "
2862			..arg_err), 2)
2863	end
2864	return DecompressDeflateInternal(str)
2865end
2866
2867--- Decompress a raw deflate compressed data with a preset dictionary.
2868-- @param str [string] The data to be decompressed.
2869-- @param dictionary [table] The preset dictionary used by
2870-- LibDeflate:CompressDeflateWithDict when the compressed data is produced.
2871-- Decompression and compression must use the same dictionary.
2872-- Otherwise wrong decompressed data could be produced without generating any
2873-- error.
2874-- @return [string/nil] If the decompression succeeds, return the decompressed
2875-- data. If the decompression fails, return nil. You should check if this return
2876-- value is non-nil to know if the decompression succeeds.
2877-- @return [integer] If the decompression succeeds, return the number of
2878-- unprocessed bytes in the input compressed data. This return value is a
2879-- positive integer if the input data is a valid compressed data appended by an
2880-- arbitary non-empty string. This return value is 0 if the input data does not
2881-- contain any extra bytes.<br>
2882-- If the decompression fails (The first return value of this function is nil),
2883-- this return value is undefined.
2884-- @see LibDeflate:CompressDeflateWithDict
2885function LibDeflate:DecompressDeflateWithDict(str, dictionary)
2886	local arg_valid, arg_err = IsValidArguments(str, true, dictionary)
2887	if not arg_valid then
2888		error(("Usage: LibDeflate:DecompressDeflateWithDict(str, dictionary): "
2889			..arg_err), 2)
2890	end
2891	return DecompressDeflateInternal(str, dictionary)
2892end
2893
2894--- Decompress a zlib compressed data.
2895-- @param str [string] The data to be decompressed
2896-- @return [string/nil] If the decompression succeeds, return the decompressed
2897-- data. If the decompression fails, return nil. You should check if this return
2898-- value is non-nil to know if the decompression succeeds.
2899-- @return [integer] If the decompression succeeds, return the number of
2900-- unprocessed bytes in the input compressed data. This return value is a
2901-- positive integer if the input data is a valid compressed data appended by an
2902-- arbitary non-empty string. This return value is 0 if the input data does not
2903-- contain any extra bytes.<br>
2904-- If the decompression fails (The first return value of this function is nil),
2905-- this return value is undefined.
2906-- @see LibDeflate:CompressZlib
2907function LibDeflate:DecompressZlib(str)
2908	local arg_valid, arg_err = IsValidArguments(str)
2909	if not arg_valid then
2910		error(("Usage: LibDeflate:DecompressZlib(str): "
2911			..arg_err), 2)
2912	end
2913	return DecompressZlibInternal(str)
2914end
2915
2916--- Decompress a zlib compressed data with a preset dictionary.
2917-- @param str [string] The data to be decompressed
2918-- @param dictionary [table] The preset dictionary used by
2919-- LibDeflate:CompressDeflateWithDict when the compressed data is produced.
2920-- Decompression and compression must use the same dictionary.
2921-- Otherwise wrong decompressed data could be produced without generating any
2922-- error.
2923-- @return [string/nil] If the decompression succeeds, return the decompressed
2924-- data. If the decompression fails, return nil. You should check if this return
2925-- value is non-nil to know if the decompression succeeds.
2926-- @return [integer] If the decompression succeeds, return the number of
2927-- unprocessed bytes in the input compressed data. This return value is a
2928-- positive integer if the input data is a valid compressed data appended by an
2929-- arbitary non-empty string. This return value is 0 if the input data does not
2930-- contain any extra bytes.<br>
2931-- If the decompression fails (The first return value of this function is nil),
2932-- this return value is undefined.
2933-- @see LibDeflate:CompressZlibWithDict
2934function LibDeflate:DecompressZlibWithDict(str, dictionary)
2935	local arg_valid, arg_err = IsValidArguments(str, true, dictionary)
2936	if not arg_valid then
2937		error(("Usage: LibDeflate:DecompressZlibWithDict(str, dictionary): "
2938			..arg_err), 2)
2939	end
2940	return DecompressZlibInternal(str, dictionary)
2941end
2942
2943-- Calculate the huffman code of fixed block
2944do
2945	_fix_block_literal_huffman_bitlen = {}
2946	for sym=0, 143 do
2947		_fix_block_literal_huffman_bitlen[sym] = 8
2948	end
2949	for sym=144, 255 do
2950		_fix_block_literal_huffman_bitlen[sym] = 9
2951	end
2952	for sym=256, 279 do
2953	    _fix_block_literal_huffman_bitlen[sym] = 7
2954	end
2955	for sym=280, 287 do
2956		_fix_block_literal_huffman_bitlen[sym] = 8
2957	end
2958
2959	_fix_block_dist_huffman_bitlen = {}
2960	for dist=0, 31 do
2961		_fix_block_dist_huffman_bitlen[dist] = 5
2962	end
2963	local status
2964	status, _fix_block_literal_huffman_bitlen_count
2965		, _fix_block_literal_huffman_to_deflate_code =
2966		GetHuffmanForDecode(_fix_block_literal_huffman_bitlen, 287, 9)
2967	assert(status == 0)
2968	status, _fix_block_dist_huffman_bitlen_count,
2969		_fix_block_dist_huffman_to_deflate_code =
2970		GetHuffmanForDecode(_fix_block_dist_huffman_bitlen, 31, 5)
2971	assert(status == 0)
2972
2973	_fix_block_literal_huffman_code =
2974		GetHuffmanCodeFromBitlen(_fix_block_literal_huffman_bitlen_count
2975		, _fix_block_literal_huffman_bitlen, 287, 9)
2976	_fix_block_dist_huffman_code =
2977		GetHuffmanCodeFromBitlen(_fix_block_dist_huffman_bitlen_count
2978		, _fix_block_dist_huffman_bitlen, 31, 5)
2979end
2980
2981-- Returns a table with info about the gzip
2982local function GetGzipInfo(str)
2983    local arg_valid, arg_err = IsValidArguments(str)
2984	if not arg_valid then
2985		error(("Usage: GetGzipInfo(str): "..arg_err), 2)
2986    end
2987    local retval = {}
2988	if string_byte(str, 1) ~= 31 or string_byte(str, 2) ~= 139 then
2989		return nil, -1
2990    end
2991    if string_byte(str, 4) > 0x1f then
2992        return nil, -3
2993    end
2994    if string_byte(str, 3) ~= 8 then
2995        return nil, -4
2996    else retval.method = "deflate" end
2997    retval.uncompressed_name = "stdout"
2998    local offset = 10
2999	if (string_byte(str, 4) / 4) % 2 ~= 0 then 
3000		offset = offset + string_byte(str, 11) * 256 + string_byte(str, 12) 
3001    end
3002    if (string_byte(str, 4) / 8) % 2 ~= 0 then
3003        local start_offset = offset
3004        while string_byte(str, offset) ~= 0 do offset = offset + 1 end
3005        retval.uncompressed_name = string.sub(str, start_offset, offset - 1)
3006    end
3007    if (string_byte(str, 4) / 16) % 2 ~= 0 then
3008        while string_byte(str, offset) ~= 0 do offset = offset + 1 end
3009    end
3010    if (string_byte(str, 4) / 2) % 2 ~= 0 then
3011        local src_checksum = string_byte(str, offset + 1) * 256
3012                             + string_byte(str, offset) 
3013        local target_checksum = self:CRC32(string.sub(str, 1, offset - 1)) % 0x10000
3014        if xor(src_checksum, target_checksum) ~= 0xFFFF then return nil, -5 end
3015        offset = offset + 2
3016    end
3017    retval.crc = string_byte(str, -5) * 0x1000000 + string_byte(str, -6) * 0x10000 + string_byte(str, -7) * 256 + string_byte(str, -8)
3018    retval.uncompressed = string_byte(str, -1) * 0x1000000 + string_byte(str, -2) * 0x10000 + string_byte(str, -3) * 256 + string_byte(str, -4)
3019    retval.compressed = string.len(str)
3020    retval.timestamp = string_byte(str, 8) * 0x1000000 + string_byte(str, 7) * 0x10000 + string_byte(str, 6) * 0x100 + string_byte(str, 5)
3021    retval.ratio = (1 - (retval.compressed / retval.uncompressed)) * 100
3022    retval.offset = offset
3023    return retval
3024end
3025
3026--- Decompress a gzip compressed data.
3027-- @param str [string] The data to be decompressed
3028-- @return [string/nil] If the decompression succeeds, return the decompressed
3029-- data. If the decompression fails, return nil. You should check if this return
3030-- value is non-nil to know if the decompression succeeds.
3031-- @return [integer] If the decompression succeeds, return the number of
3032-- unprocessed bytes in the input compressed data. This return value is a
3033-- positive integer if the input data is a valid compressed data appended by an
3034-- arbitary non-empty string. This return value is 0 if the input data does not
3035-- contain any extra bytes.<br>
3036-- If the decompression fails (The first return value of this function is nil),
3037-- this return value is undefined.
3038function LibDeflate:DecompressGzip(str)
3039	local arg_valid, arg_err = IsValidArguments(str)
3040	if not arg_valid then
3041		error(("Usage: LibDeflate:DecompressGzip(str): "..arg_err), 2)
3042	end
3043    local info, err = GetGzipInfo(str)
3044    if info == nil then return info, err end
3045    local res, err = DecompressDeflateInternal(string.sub(str, info.offset + 1, -8))
3046    if res == nil then return res, err end
3047    if string.len(res) ~= info.uncompressed then return nil, -6 end
3048    local target_checksum = xor(self:CRC32(res), 0xFFFFFFFF)
3049    if xor(info.crc, target_checksum) ~= 0xFFFFFFFF then return nil, -2 end
3050    return res, 0
3051end
3052
3053-- Encoding algorithms
3054-- Prefix encoding algorithm
3055-- implemented by Galmok of European Stormrage (Horde), galmok@gmail.com
3056-- From LibCompress <https://www.wowace.com/projects/libcompress>,
3057-- which is licensed under GPLv2
3058-- The code has been modified by the author of LibDeflate.
3059------------------------------------------------------------------------------
3060
3061-- to be able to match any requested byte value, the search
3062-- string must be preprocessed characters to escape with %:
3063-- ( ) . % + - * ? [ ] ^ $
3064-- "illegal" byte values:
3065-- 0 is replaces %z
3066local _gsub_escape_table = {
3067	["\000"] = "%z", ["("] = "%(", [")"] = "%)", ["."] = "%.",
3068	["%"] = "%%", ["+"] = "%+", ["-"] = "%-", ["*"] = "%*",
3069	["?"] = "%?", ["["] = "%[", ["]"] = "%]", ["^"] = "%^",
3070	["$"] = "%$",
3071}
3072
3073local function escape_for_gsub(str)
3074	return str:gsub("([%z%(%)%.%%%+%-%*%?%[%]%^%$])", _gsub_escape_table)
3075end
3076
3077--- Create a custom codec with encoder and decoder. <br>
3078-- This codec is used to convert an input string to make it not contain
3079-- some specific bytes.
3080-- This created codec and the parameters of this function do NOT take
3081-- localization into account. One byte (0-255) in the string is exactly one
3082-- character (0-255).
3083-- Credits to LibCompress.
3084-- @param reserved_chars [string] The created encoder will ensure encoded
3085-- data does not contain any single character in reserved_chars. This parameter
3086-- should be non-empty.
3087-- @param escape_chars [string] The escape character(s) used in the created
3088-- codec. The codec converts any character included in reserved\_chars /
3089-- escape\_chars / map\_chars to (one escape char + one character not in
3090-- reserved\_chars / escape\_chars / map\_chars).
3091-- You usually only need to provide a length-1 string for this parameter.
3092-- Length-2 string is only needed when
3093-- reserved\_chars + escape\_chars + map\_chars is longer than 127.
3094-- This parameter should be non-empty.
3095-- @param map_chars [string] The created encoder will map every
3096-- reserved\_chars:sub(i, i) (1 <= i <= #map\_chars) to map\_chars:sub(i, i).
3097-- This parameter CAN be empty string.
3098-- @return [table/nil] If the codec cannot be created, return nil.<br>
3099-- If the codec can be created according to the given
3100-- parameters, return the codec, which is a encode/decode table.
3101-- The table contains two functions: <br>
3102-- t:Encode(str) returns the encoded string. <br>
3103-- t:Decode(str) returns the decoded string if succeeds. nil if fails.
3104-- @return [nil/string] If the codec is successfully created, return nil.
3105-- If not, return a string that describes the reason why the codec cannot be
3106-- created.
3107-- @usage
3108-- -- Create an encoder/decoder that maps all "\000" to "\003",
3109-- -- and escape "\001" (and "\002" and "\003") properly
3110-- local codec = LibDeflate:CreateCodec("\000\001", "\002", "\003")
3111--
3112-- local encoded = codec:Encode(SOME_STRING)
3113-- -- "encoded" does not contain "\000" or "\001"
3114-- local decoded = codec:Decode(encoded)
3115-- -- assert(decoded == SOME_STRING)
3116function LibDeflate:CreateCodec(reserved_chars, escape_chars
3117	, map_chars)
3118	-- select a default escape character
3119	if type(reserved_chars) ~= "string"
3120		or type(escape_chars) ~= "string"
3121		or type(map_chars) ~= "string" then
3122			error(
3123				"Usage: LibDeflate:CreateCodec(reserved_chars,"
3124				.." escape_chars, map_chars):"
3125				.." All arguments must be string.", 2)
3126	end
3127
3128	if escape_chars == "" then
3129		return nil, "No escape characters supplied."
3130	end
3131	if #reserved_chars < #map_chars then
3132		return nil, "The number of reserved characters must be"
3133			.." at least as many as the number of mapped chars."
3134	end
3135	if reserved_chars == "" then
3136		return nil, "No characters to encode."
3137	end
3138
3139	local encode_bytes = reserved_chars..escape_chars..map_chars
3140	-- build list of bytes not available as a suffix to a prefix byte
3141	local taken = {}
3142	for i = 1, #encode_bytes do
3143		local _byte = string_byte(encode_bytes, i, i)
3144		if taken[_byte] then -- Modified by LibDeflate:
3145			return nil, "There must be no duplicate characters in the"
3146				.." concatenation of reserved_chars, escape_chars and"
3147				.." map_chars."
3148		end
3149		taken[_byte] = true
3150	end
3151
3152	-- Modified by LibDeflate:
3153	-- Store the patterns and replacement in tables for later use.
3154	-- This function is modified that loadstring() lua api is no longer used.
3155	local decode_patterns = {}
3156	local decode_repls = {}
3157
3158	-- the encoding can be a single gsub
3159	-- , but the decoding can require multiple gsubs
3160	local encode_search = {}
3161	local encode_translate = {}
3162
3163	-- map single byte to single byte
3164	if #map_chars > 0 then
3165		local decode_search = {}
3166		local decode_translate = {}
3167		for i = 1, #map_chars do
3168			local from = string_sub(reserved_chars, i, i)
3169			local to = string_sub(map_chars, i, i)
3170			encode_translate[from] = to
3171			encode_search[#encode_search+1] = from
3172			decode_translate[to] = from
3173			decode_search[#decode_search+1] = to
3174		end
3175		decode_patterns[#decode_patterns+1] =
3176			"([".. escape_for_gsub(table_concat(decode_search)).."])"
3177		decode_repls[#decode_repls+1] = decode_translate
3178	end
3179
3180	local escape_char_index = 1
3181	local escape_char = string_sub(escape_chars
3182		, escape_char_index, escape_char_index)
3183	-- map single byte to double-byte
3184	local r = 0 -- suffix char value to the escapeChar
3185
3186	local decode_search = {}
3187	local decode_translate = {}
3188	for i = 1, #encode_bytes do
3189		local c = string_sub(encode_bytes, i, i)
3190		if not encode_translate[c] then
3191			-- this loop will update escapeChar and r
3192			while r >= 256 or taken[r] do
3193			-- Bug in LibCompress r81
3194			-- while r < 256 and taken[r] do
3195				r = r + 1
3196				if r > 255 then -- switch to next escapeChar
3197					decode_patterns[#decode_patterns+1] =
3198						escape_for_gsub(escape_char)
3199						.."(["
3200						.. escape_for_gsub(table_concat(decode_search)).."])"
3201					decode_repls[#decode_repls+1] = decode_translate
3202
3203					escape_char_index = escape_char_index + 1
3204					escape_char = string_sub(escape_chars, escape_char_index
3205						, escape_char_index)
3206					r = 0
3207					decode_search = {}
3208					decode_translate = {}
3209
3210					-- Fixes Another bug in LibCompress r82.
3211					-- LibCompress checks this error condition
3212					-- right after "if r > 255 then"
3213					-- This is why error case should also be tested.
3214					if not escape_char or escape_char == "" then
3215						-- actually I don't need to check
3216						-- "not ecape_char", but what if Lua changes
3217						-- the behavior of string.sub() in the future?
3218						-- we are out of escape chars and we need more!
3219						return nil, "Out of escape characters."
3220					end
3221				end
3222			end
3223
3224			local char_r = _byte_to_char[r]
3225			encode_translate[c] = escape_char..char_r
3226			encode_search[#encode_search+1] = c
3227			decode_translate[char_r] = c
3228			decode_search[#decode_search+1] = char_r
3229			r = r + 1
3230		end
3231		if i == #encode_bytes then
3232			decode_patterns[#decode_patterns+1] =
3233				escape_for_gsub(escape_char).."(["
3234				.. escape_for_gsub(table_concat(decode_search)).."])"
3235			decode_repls[#decode_repls+1] = decode_translate
3236		end
3237	end
3238
3239	local codec = {}
3240
3241	local encode_pattern = "(["
3242		.. escape_for_gsub(table_concat(encode_search)).."])"
3243	local encode_repl = encode_translate
3244
3245	function codec:Encode(str)
3246		if type(str) ~= "string" then
3247			error(("Usage: codec:Encode(str):"
3248				.." 'str' - string expected got '%s'."):format(type(str)), 2)
3249		end
3250		return string_gsub(str, encode_pattern, encode_repl)
3251	end
3252
3253	local decode_tblsize = #decode_patterns
3254	local decode_fail_pattern = "(["
3255		.. escape_for_gsub(reserved_chars).."])"
3256
3257	function codec:Decode(str)
3258		if type(str) ~= "string" then
3259			error(("Usage: codec:Decode(str):"
3260				.." 'str' - string expected got '%s'."):format(type(str)), 2)
3261		end
3262		if string_find(str, decode_fail_pattern) then
3263			return nil
3264		end
3265		for i = 1, decode_tblsize do
3266			str = string_gsub(str, decode_patterns[i], decode_repls[i])
3267		end
3268		return str
3269	end
3270
3271	return codec
3272end
3273
3274local _addon_channel_codec
3275
3276local function GenerateWoWAddonChannelCodec()
3277	return LibDeflate:CreateCodec("\000", "\001", "")
3278end
3279
3280--- Encode the string to make it ready to be transmitted in World of
3281-- Warcraft addon channel. <br>
3282-- The encoded string is guaranteed to contain no NULL ("\000") character.
3283-- @param str [string] The string to be encoded.
3284-- @return The encoded string.
3285-- @see LibDeflate:DecodeForWoWAddonChannel
3286function LibDeflate:EncodeForWoWAddonChannel(str)
3287	if type(str) ~= "string" then
3288		error(("Usage: LibDeflate:EncodeForWoWAddonChannel(str):"
3289			.." 'str' - string expected got '%s'."):format(type(str)), 2)
3290	end
3291	if not _addon_channel_codec then
3292		_addon_channel_codec = GenerateWoWAddonChannelCodec()
3293	end
3294	return _addon_channel_codec:Encode(str)
3295end
3296
3297--- Decode the string produced by LibDeflate:EncodeForWoWAddonChannel
3298-- @param str [string] The string to be decoded.
3299-- @return [string/nil] The decoded string if succeeds. nil if fails.
3300-- @see LibDeflate:EncodeForWoWAddonChannel
3301function LibDeflate:DecodeForWoWAddonChannel(str)
3302	if type(str) ~= "string" then
3303		error(("Usage: LibDeflate:DecodeForWoWAddonChannel(str):"
3304			.." 'str' - string expected got '%s'."):format(type(str)), 2)
3305	end
3306	if not _addon_channel_codec then
3307		_addon_channel_codec = GenerateWoWAddonChannelCodec()
3308	end
3309	return _addon_channel_codec:Decode(str)
3310end
3311
3312-- For World of Warcraft Chat Channel Encoding
3313-- implemented by Galmok of European Stormrage (Horde), galmok@gmail.com
3314-- From LibCompress <https://www.wowace.com/projects/libcompress>,
3315-- which is licensed under GPLv2
3316-- The code has been modified by the author of LibDeflate.
3317-- Following byte values are not allowed:
3318-- \000, s, S, \010, \013, \124, %
3319-- Because SendChatMessage will error
3320-- if an UTF8 multibyte character is incomplete,
3321-- all character values above 127 have to be encoded to avoid this.
3322-- This costs quite a bit of bandwidth (about 13-14%)
3323-- Also, because drunken status is unknown for the received
3324-- , strings used with SendChatMessage should be terminated with
3325-- an identifying byte value, after which the server MAY add "...hic!"
3326-- or as much as it can fit(!).
3327-- Pass the identifying byte as a reserved character to this function
3328-- to ensure the encoding doesn't contain that value.
3329-- or use this: local message, match = arg1:gsub("^(.*)\029.-$", "%1")
3330-- arg1 is message from channel, \029 is the string terminator
3331-- , but may be used in the encoded datastream as well. :-)
3332-- This encoding will expand data anywhere from:
3333-- 0% (average with pure ascii text)
3334-- 53.5% (average with random data valued zero to 255)
3335-- 100% (only encoding data that encodes to two bytes)
3336local function GenerateWoWChatChannelCodec()
3337	local r = {}
3338	for i = 128, 255 do
3339		r[#r+1] = _byte_to_char[i]
3340	end
3341
3342	local reserved_chars = "sS\000\010\013\124%"..table_concat(r)
3343	return LibDeflate:CreateCodec(reserved_chars
3344		, "\029\031", "\015\020")
3345end
3346
3347local _chat_channel_codec
3348
3349--- Encode the string to make it ready to be transmitted in World of
3350-- Warcraft chat channel. <br>
3351-- See also https://wow.gamepedia.com/ValidChatMessageCharacters
3352-- @param str [string] The string to be encoded.
3353-- @return [string] The encoded string.
3354-- @see LibDeflate:DecodeForWoWChatChannel
3355function LibDeflate:EncodeForWoWChatChannel(str)
3356	if type(str) ~= "string" then
3357		error(("Usage: LibDeflate:EncodeForWoWChatChannel(str):"
3358			.." 'str' - string expected got '%s'."):format(type(str)), 2)
3359	end
3360	if not _chat_channel_codec then
3361		_chat_channel_codec = GenerateWoWChatChannelCodec()
3362	end
3363	return _chat_channel_codec:Encode(str)
3364end
3365
3366--- Decode the string produced by LibDeflate:EncodeForWoWChatChannel.
3367-- @param str [string] The string to be decoded.
3368-- @return [string/nil] The decoded string if succeeds. nil if fails.
3369-- @see LibDeflate:EncodeForWoWChatChannel
3370function LibDeflate:DecodeForWoWChatChannel(str)
3371	if type(str) ~= "string" then
3372		error(("Usage: LibDeflate:DecodeForWoWChatChannel(str):"
3373			.." 'str' - string expected got '%s'."):format(type(str)), 2)
3374	end
3375	if not _chat_channel_codec then
3376		_chat_channel_codec = GenerateWoWChatChannelCodec()
3377	end
3378	return _chat_channel_codec:Decode(str)
3379end
3380
3381-- Credits to WeakAuras <https://github.com/WeakAuras/WeakAuras2>,
3382-- and Galmok (galmok@gmail.com) for the 6 bit encoding algorithm.
3383-- The result of encoding will be 25% larger than the
3384-- origin string, but every single byte of the encoding result will be
3385-- printable characters as the following.
3386local _byte_to_6bit_char = {
3387	[0]="a", "b", "c", "d", "e", "f", "g", "h",
3388	"i", "j", "k", "l", "m", "n", "o", "p",
3389	"q", "r", "s", "t", "u", "v", "w", "x",
3390	"y", "z", "A", "B", "C", "D", "E", "F",
3391	"G", "H", "I", "J", "K", "L", "M", "N",
3392	"O", "P", "Q", "R", "S", "T", "U", "V",
3393	"W", "X", "Y", "Z", "0", "1", "2", "3",
3394	"4", "5", "6", "7", "8", "9", "(", ")",
3395}
3396
3397local _6bit_to_byte = {
3398	[97]=0,[98]=1,[99]=2,[100]=3,[101]=4,[102]=5,[103]=6,[104]=7,
3399	[105]=8,[106]=9,[107]=10,[108]=11,[109]=12,[110]=13,[111]=14,[112]=15,
3400	[113]=16,[114]=17,[115]=18,[116]=19,[117]=20,[118]=21,[119]=22,[120]=23,
3401	[121]=24,[122]=25,[65]=26,[66]=27,[67]=28,[68]=29,[69]=30,[70]=31,
3402	[71]=32,[72]=33,[73]=34,[74]=35,[75]=36,[76]=37,[77]=38,[78]=39,
3403	[79]=40,[80]=41,[81]=42,[82]=43,[83]=44,[84]=45,[85]=46,[86]=47,
3404	[87]=48,[88]=49,[89]=50,[90]=51,[48]=52,[49]=53,[50]=54,[51]=55,
3405	[52]=56,[53]=57,[54]=58,[55]=59,[56]=60,[57]=61,[40]=62,[41]=63,
3406}
3407
3408--- Encode the string to make it printable. <br>
3409--
3410-- Credis to WeakAuras2, this function is equivalant to the implementation
3411-- it is using right now. <br>
3412-- The encoded string will be 25% larger than the origin string. However, every
3413-- single byte of the encoded string will be one of 64 printable ASCII
3414-- characters, which are can be easier copied, pasted and displayed.
3415-- (26 lowercase letters, 26 uppercase letters, 10 numbers digits,
3416-- left parenthese, or right parenthese)
3417-- @param str [string] The string to be encoded.
3418-- @return [string] The encoded string.
3419function LibDeflate:EncodeForPrint(str)
3420	if type(str) ~= "string" then
3421		error(("Usage: LibDeflate:EncodeForPrint(str):"
3422			.." 'str' - string expected got '%s'."):format(type(str)), 2)
3423	end
3424	local strlen = #str
3425	local strlenMinus2 = strlen - 2
3426	local i = 1
3427	local buffer = {}
3428	local buffer_size = 0
3429	while i <= strlenMinus2 do
3430		local x1, x2, x3 = string_byte(str, i, i+2)
3431		i = i + 3
3432		local cache = x1+x2*256+x3*65536
3433		local b1 = cache % 64
3434		cache = (cache - b1) / 64
3435		local b2 = cache % 64
3436		cache = (cache - b2) / 64
3437		local b3 = cache % 64
3438		local b4 = (cache - b3) / 64
3439		buffer_size = buffer_size + 1
3440		buffer[buffer_size] =
3441			_byte_to_6bit_char[b1].._byte_to_6bit_char[b2]
3442			.._byte_to_6bit_char[b3].._byte_to_6bit_char[b4]
3443	end
3444
3445	local cache = 0
3446	local cache_bitlen = 0
3447	while i <= strlen do
3448		local x = string_byte(str, i, i)
3449		cache = cache + x * _pow2[cache_bitlen]
3450		cache_bitlen = cache_bitlen + 8
3451		i = i + 1
3452	end
3453	while cache_bitlen > 0 do
3454		local bit6 = cache % 64
3455		buffer_size = buffer_size + 1
3456		buffer[buffer_size] = _byte_to_6bit_char[bit6]
3457		cache = (cache - bit6) / 64
3458		cache_bitlen = cache_bitlen - 6
3459	end
3460
3461	return table_concat(buffer)
3462end
3463
3464--- Decode the printable string produced by LibDeflate:EncodeForPrint.
3465-- "str" will have its prefixed and trailing control characters or space
3466-- removed before it is decoded, so it is easier to use if "str" comes form
3467-- user copy and paste with some prefixed or trailing spaces.
3468-- Then decode fails if the string contains any characters cant be produced by
3469-- LibDeflate:EncodeForPrint. That means, decode fails if the string contains a
3470-- characters NOT one of 26 lowercase letters, 26 uppercase letters,
3471-- 10 numbers digits, left parenthese, or right parenthese.
3472-- @param str [string] The string to be decoded
3473-- @return [string/nil] The decoded string if succeeds. nil if fails.
3474function LibDeflate:DecodeForPrint(str)
3475	if type(str) ~= "string" then
3476		error(("Usage: LibDeflate:DecodeForPrint(str):"
3477			.." 'str' - string expected got '%s'."):format(type(str)), 2)
3478	end
3479	str = str:gsub("^[%c ]+", "")
3480	str = str:gsub("[%c ]+$", "")
3481
3482	local strlen = #str
3483	if strlen == 1 then
3484		return nil
3485	end
3486	local strlenMinus3 = strlen - 3
3487	local i = 1
3488	local buffer = {}
3489	local buffer_size = 0
3490	while i <= strlenMinus3 do
3491		local x1, x2, x3, x4 = string_byte(str, i, i+3)
3492		x1 = _6bit_to_byte[x1]
3493		x2 = _6bit_to_byte[x2]
3494		x3 = _6bit_to_byte[x3]
3495		x4 = _6bit_to_byte[x4]
3496		if not (x1 and x2 and x3 and x4) then
3497			return nil
3498		end
3499		i = i + 4
3500		local cache = x1+x2*64+x3*4096+x4*262144
3501		local b1 = cache % 256
3502		cache = (cache - b1) / 256
3503		local b2 = cache % 256
3504		local b3 = (cache - b2) / 256
3505		buffer_size = buffer_size + 1
3506		buffer[buffer_size] =
3507			_byte_to_char[b1].._byte_to_char[b2].._byte_to_char[b3]
3508	end
3509
3510	local cache  = 0
3511	local cache_bitlen = 0
3512	while i <= strlen do
3513		local x = string_byte(str, i, i)
3514		x =  _6bit_to_byte[x]
3515		if not x then
3516			return nil
3517		end
3518		cache = cache + x * _pow2[cache_bitlen]
3519		cache_bitlen = cache_bitlen + 6
3520		i = i + 1
3521	end
3522
3523	while cache_bitlen >= 8 do
3524		local _byte = cache % 256
3525		buffer_size = buffer_size + 1
3526		buffer[buffer_size] = _byte_to_char[_byte]
3527		cache = (cache - _byte) / 256
3528		cache_bitlen = cache_bitlen - 8
3529	end
3530
3531	return table_concat(buffer)
3532end
3533
3534local function InternalClearCache()
3535	_chat_channel_codec = nil
3536	_addon_channel_codec = nil
3537end
3538
3539-- For test. Don't use the functions in this table for real application.
3540-- Stuffs in this table is subject to change.
3541LibDeflate.internals = {
3542	LoadStringToTable = LoadStringToTable,
3543	IsValidDictionary = IsValidDictionary,
3544	IsEqualAdler32 = IsEqualAdler32,
3545	_byte_to_6bit_char = _byte_to_6bit_char,
3546	_6bit_to_byte = _6bit_to_byte,
3547    InternalClearCache = InternalClearCache,
3548    GetGzipInfo = GetGzipInfo,
3549}
3550
3551-- Archive library
3552compression_level = nil -- compression level (nil for default)
3553
3554local function split(inputstr, sep)
3555    if sep == nil then
3556        sep = "%s"
3557    end
3558    local t={}
3559    for str in string.gmatch(inputstr, "([^"..sep.."]+)") do
3560        table.insert(t, str)
3561    end
3562    return t
3563end
3564
3565local function getComponent(tab, keys)
3566    if #keys == 0 then return tab end
3567    local k = table.remove(keys, 1)
3568    if tab[k] == nil then return nil
3569    elseif type(tab[k]) ~= "table" then return tab[k]
3570    elseif k == "." then return getComponent(tab, keys)
3571    else return getComponent(tab[k], keys) end
3572end
3573
3574local function extract(data, path)
3575    if string.sub(path, 1, 1) == "/" then path = string.sub(path, 2) end
3576    fs.makeDir(path)
3577    for k,v in pairs(data) do
3578        if type(v) == "table" then extract(v, path .. "/" .. k) else
3579            local file = fs.open(path .. "/" .. k, "wb")
3580            for s in string.gmatch(v, ".") do file.write(string.byte(s)) end
3581            file.close()
3582        end
3583    end
3584end
3585
3586local function import(path)
3587    local retval = {}
3588    if path == nil then error("Path is nil", 2) end
3589    if not fs.isDir(path) then error(path .. ": Not a directory", 2) end
3590    for k,v in pairs(fs.list(path)) do
3591        if fs.isDir(path .. "/" .. v) then retval[v] = import(path .. "/" .. v) else
3592            local file = fs.open(path .. "/" .. v, "rb")
3593            local r = ""
3594            local b = file.read()
3595            while b ~= nil do
3596                r = r .. string.char(b)
3597                b = file.read()
3598            end
3599            file.close()
3600            retval[v] = r
3601        end
3602    end
3603    return retval
3604end
3605
3606local function create(data, size)
3607    local retval = {}
3608    retval.data = data
3609    retval.size = size
3610
3611    function retval.write(path)
3612        local str = LibDeflate:CompressGzip(textutils.serialize(retval.data), compression_level and {level=compression_level})
3613        local file = fs.open(path, "wb")
3614        for s in string.gmatch(str, ".") do file.write(string.byte(s)) end
3615        file.close()
3616    end
3617
3618    function retval.readFile(realPath, pkgPath)
3619        local realFile = fs.open(realPath, "r")
3620        if not realFile then error(realPath .. ": File not found", 2) end
3621        retval.makeDir(fs.getDir(pkgPath))
3622        local dir = getComponent(retval.data, split(fs.getDir(pkgPath), "/"))
3623        if type(dir) ~= "table" then error(fs.getDir(pkgPath) .. ": Directory not found", 2) end
3624        dir[fs.getName(pkgPath)] = realFile.readAll()
3625        realFile.close()
3626    end
3627
3628    function retval.readDir(realPath, pkgPath)
3629        if not fs.isDir(realPath) then error(realPath .. ": Not a directory", 2) end
3630        retval.makeDir(fs.getDir(pkgPath))
3631        local dir = getComponent(retval.data, split(fs.getDir(pkgPath), "/"))
3632        dir[fs.getName(pkgPath)] = import(realPath)
3633    end
3634
3635    function retval.writeFile(pkgPath, realPath)
3636        local pkgFile = getComponent(retval.data, split(pkgPath, "/"))
3637        if type(pkgFile) ~= "string" then error(pkgPath .. ": File not found", 2) end
3638        if fs.getDir(fs.getDir(realPath)) ~= ".." then fs.makeDir(fs.getDir(realPath)) end
3639        local realFile = fs.open(realPath, "w")
3640        realFile.write(pkgFile)
3641        realFile.close()
3642    end
3643
3644    function retval.writeDir(pkgPath, realPath)
3645        local dir = getComponent(retval.data, split(pkgPath, "/"))
3646        if type(dir) ~= "table" then error(pkgPath .. ": Directory not found", 2) end
3647        extract(dir, realPath)
3648    end
3649
3650    function retval.extract(path) extract(retval.data, path) end
3651
3652    function retval.list(path)
3653        if string.sub(path, 1, 1) == "/" then path = string.sub(path, 2) end
3654        local dir = getComponent(retval.data, split(path, "/"))
3655        if type(dir) ~= "table" then error(path .. ": Directory not found", 2) end
3656        local retval = {}
3657        for k,v in pairs(dir) do table.insert(retval, k) end
3658        return retval
3659    end
3660
3661    function retval.exists(path)
3662        if string.sub(path, 1, 1) == "/" then path = string.sub(path, 2) end
3663        return getComponent(retval.data, split(path, "/")) ~= nil
3664    end
3665
3666    function retval.isDir(path)
3667        if string.sub(path, 1, 1) == "/" then path = string.sub(path, 2) end
3668        return type(getComponent(retval.data, split(path, "/"))) == "table"
3669    end
3670
3671    function retval.isReadOnly() return false end
3672
3673    function retval.getSize(path)
3674        if string.sub(path, 1, 1) == "/" then path = string.sub(path, 2) end
3675        local file = getComponent(retval.data, split(path, "/"))
3676        if type(file) ~= "string" then error(path .. ": File not found", 2) end
3677        return string.len(file)
3678    end
3679
3680    function retval.getFreeSpace() return math.huge end
3681
3682    function retval.makeDir(path)
3683        if string.sub(path, 1, 1) == "/" then path = string.sub(path, 2) end
3684        local dir = getComponent(retval.data, split(fs.getDir(path), "/"))
3685        if type(dir) ~= "table" then 
3686            retval.makeDir(fs.getDir(path))
3687            dir = getComponent(retval.data, split(fs.getDir(path), "/"))
3688            if type(dir) ~= "table" then error(fs.getDir(path) .. ": Directory not found", 2) end
3689        end
3690        if type(dir[fs.getName(path)]) == "table" then return
3691        elseif type(dir[fs.getName(path)]) == "file" then error(path .. ": File already exists") end
3692        dir[fs.getName(path)] = {}
3693    end
3694
3695    function retval.move(path, toPath)
3696        retval.copy(path, toPath, 1)
3697        retval.delete(path, 1)
3698    end
3699
3700    function retval.copy(path, toPath, offset)
3701        offset = offset or 0
3702        if string.sub(path, 1, 1) == "/" then path = string.sub(path, 2 + offset) end
3703        local file = getComponent(retval.data, split(path, "/"))
3704        if type(file) ~= "string" then error(path .. ": File not found", 2 + offset) end
3705        local toDir = getComponent(retval.data, split(fs.getDir(toPath), "/"))
3706        if type(toDir) ~= "table" then error(fs.getDir(toPath) .. ": Directory not found", 2 + offset) end
3707        toDir[fs.getName(toPath)] = file
3708    end
3709
3710    function retval.delete(path, offset)
3711        offset = offset or 0
3712        if string.sub(path, 1, 1) == "/" then path = string.sub(path, 2) end
3713        local fromDir = getComponent(retval.data, split(fs.getDir(path), "/"))
3714        if type(fromDir) ~= "table" then error(fs.getDir(path) .. ": Directory not found", 2 + offset) end
3715        fromDir[fs.getName(path)] = nil
3716    end
3717
3718    function retval.open(path, mode)
3719        if string.sub(path, 1, 1) == "/" then path = string.sub(path, 2) end
3720        local file = getComponent(retval.data, split(path, "/"))
3721        if type(file) ~= "string" and not string.find(mode, "w") then error(path .. ": File not found", 2) end
3722        if string.find(mode, "w") then file = "" end
3723        local retval = {close = function() if retval.flush ~= nil then retval.flush() end end}
3724        local pos = string.find(mode, "a") and string.len(file) or 1
3725        if string.find(mode, "b") then
3726            if string.find(mode, "r") then
3727                retval.read = function()
3728                    pos = pos + 1
3729                    return string.byte(string.sub(file, pos - 1, pos - 1))
3730                end
3731            elseif string.find(mode, "w") or string.find(mode, "a") then
3732                retval.write = function(c)
3733                    if pos > string.len(file) then file = file .. string.char(c)
3734                    else file = string.sub(file, 1, pos - 1) .. string.char(c) .. string.sub(file, pos + 1) end
3735                    pos = pos + 1
3736                end
3737                retval.flush = function()
3738                    local dir = getComponent(retval.data, split(fs.getDir(path), "/"))
3739                    dir[fs.getName(path)] = file
3740                end
3741            end
3742        else
3743            if string.find(mode, "r") then
3744                retval.readLine = function()
3745                    if pos > string.len(file) then return nil end
3746                    local retval = ""
3747                    local c = string.sub(file, pos, pos)
3748                    pos = pos + 1
3749                    while c ~= "\n" and pos <= string.len(file) do
3750                        retval = retval .. c
3751                        c = string.sub(file, pos, pos)
3752                        pos = pos + 1
3753                    end
3754                    return retval
3755                end
3756                retval.readAll = function()
3757                    if pos > string.len(file) then return nil end
3758                    pos = string.len(file) + 1
3759                    return file
3760                end
3761            elseif string.find(mode, "w") or string.find(mode, "a") then
3762                retval.write = function(text)
3763                    if pos > string.len(file) then file = file .. text 
3764                    else file = string.sub(file, 1, pos - 1) .. text .. string.sub(file, pos + string.len(text)) end
3765                    pos = pos + string.len(text)
3766                end
3767                retval.writeLine = function(text) retval.write(text .. "\n") end
3768                retval.flush = function()
3769                    local dir = getComponent(retval.data, split(fs.getDir(path), "/"))
3770                    dir[fs.getName(path)] = file
3771                end
3772            end
3773        end
3774        return retval
3775    end
3776
3777    -- for CCKernel2
3778    function retval.getPermissions() return 15 end
3779    function retval.setPermissions() end
3780    function retval.getOwner() return 0 end
3781    function retval.setOwner() end
3782
3783    return retval
3784end
3785
3786function new() return create({}) end
3787
3788function load(path) return create(import(path)) end
3789
3790function read(path)
3791    local file = fs.open(path, "rb")
3792    if not file then error(path .. ": File not found", 2) end
3793    local retval = ""
3794    local b = file.read()
3795    while b ~= nil do
3796        retval = retval .. string.char(b)
3797        b = file.read()
3798    end
3799    file.close()
3800    local gz = LibDeflate:DecompressGzip(retval)
3801    os.queueEvent("nosleep")
3802    os.pullEvent()
3803    return create(textutils.unserialize(gz), string.len(gz))
3804end
3805
3806function readstring(retval)
3807    local gz = LibDeflate:DecompressGzip(retval)
3808    os.queueEvent("nosleep")
3809    os.pullEvent()
3810    return create(textutils.unserialize(gz), string.len(gz))
3811end
3812
3813function setCompressionLevel(level) compression_level = level end
3814
3815local archive = {new = new, load = load, read = read, setCompressionLevel = setCompressionLevel}
3816setmetatable(archive, {__call = function(self, path) if path ~= nil and fs.exists(path) then if fs.isDir(path) then return load(path) else return read(path) end else return new() end end})
3817
3818local base64 = {}
3819
3820local extract = _G.bit32 and _G.bit32.extract
3821if not extract then
3822	if _G.bit then
3823		local shl, shr, band = _G.bit.blshift, _G.bit.brshift, _G.bit.band
3824		extract = function( v, from, width )
3825			return band( shr( v, from ), shl( 1, width ) - 1 )
3826		end
3827	elseif _G._VERSION >= "Lua 5.3" then
3828		extract = load[[return function( v, from, width )
3829			return ( v >> from ) & ((1 << width) - 1)
3830		end]]()
3831	else
3832		extract = function( v, from, width )
3833			local w = 0
3834			local flag = 2^from
3835			for i = 0, width-1 do
3836				local flag2 = flag + flag
3837				if v % flag2 >= flag then
3838					w = w + 2^i
3839				end
3840				flag = flag2
3841			end
3842			return w
3843		end
3844	end
3845end
3846
3847
3848function base64.makeencoder( s62, s63, spad )
3849	local encoder = {}
3850	for b64code, char in pairs{[0]='A','B','C','D','E','F','G','H','I','J',
3851		'K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y',
3852		'Z','a','b','c','d','e','f','g','h','i','j','k','l','m','n',
3853		'o','p','q','r','s','t','u','v','w','x','y','z','0','1','2',
3854		'3','4','5','6','7','8','9',s62 or '+',s63 or'/',spad or'='} do
3855		encoder[b64code] = char:byte()
3856	end
3857	return encoder
3858end
3859
3860function base64.makedecoder( s62, s63, spad )
3861	local decoder = {}
3862	for b64code, charcode in pairs( base64.makeencoder( s62, s63, spad )) do
3863		decoder[charcode] = b64code
3864	end
3865	return decoder
3866end
3867
3868local DEFAULT_ENCODER = base64.makeencoder()
3869local DEFAULT_DECODER = base64.makedecoder()
3870
3871local char, concat = string.char, table.concat
3872
3873function base64.encode( str, encoder, usecaching )
3874	encoder = encoder or DEFAULT_ENCODER
3875	local t, k, n = {}, 1, #str
3876	local lastn = n % 3
3877	local cache = {}
3878	for i = 1, n-lastn, 3 do
3879		local a, b, c = str:byte( i, i+2 )
3880		local v = a*0x10000 + b*0x100 + c
3881		local s
3882		if usecaching then
3883			s = cache[v]
3884			if not s then
3885				s = char(encoder[extract(v,18,6)], encoder[extract(v,12,6)], encoder[extract(v,6,6)], encoder[extract(v,0,6)])
3886				cache[v] = s
3887			end
3888		else
3889			s = char(encoder[extract(v,18,6)], encoder[extract(v,12,6)], encoder[extract(v,6,6)], encoder[extract(v,0,6)])
3890		end
3891		t[k] = s
3892		k = k + 1
3893	end
3894	if lastn == 2 then
3895		local a, b = str:byte( n-1, n )
3896		local v = a*0x10000 + b*0x100
3897		t[k] = char(encoder[extract(v,18,6)], encoder[extract(v,12,6)], encoder[extract(v,6,6)], encoder[64])
3898	elseif lastn == 1 then
3899		local v = str:byte( n )*0x10000
3900		t[k] = char(encoder[extract(v,18,6)], encoder[extract(v,12,6)], encoder[64], encoder[64])
3901	end
3902	return concat( t )
3903end
3904
3905function base64.decode( b64, decoder, usecaching )
3906	decoder = decoder or DEFAULT_DECODER
3907	local cache = usecaching and {}
3908	local t, k = {}, 1
3909	local n = #b64
3910	local padding = b64:sub(-2) == '==' and 2 or b64:sub(-1) == '=' and 1 or 0
3911	for i = 1, padding > 0 and n-4 or n, 4 do
3912		local a, b, c, d = b64:byte( i, i+3 )
3913		local s
3914		if usecaching then
3915			local v0 = a*0x1000000 + b*0x10000 + c*0x100 + d
3916			s = cache[v0]
3917			if not s then
3918				local v = decoder[a]*0x40000 + decoder[b]*0x1000 + decoder[c]*0x40 + decoder[d]
3919				s = char( extract(v,16,8), extract(v,8,8), extract(v,0,8))
3920				cache[v0] = s
3921			end
3922		else
3923			local v = decoder[a]*0x40000 + decoder[b]*0x1000 + decoder[c]*0x40 + decoder[d]
3924			s = char( extract(v,16,8), extract(v,8,8), extract(v,0,8))
3925		end
3926		t[k] = s
3927		k = k + 1
3928	end
3929	if padding == 1 then
3930		local a, b, c = b64:byte( n-3, n-1 )
3931		local v = decoder[a]*0x40000 + decoder[b]*0x1000 + decoder[c]*0x40
3932		t[k] = char( extract(v,16,8), extract(v,8,8))
3933	elseif padding == 2 then
3934		local a, b = b64:byte( n-3, n-2 )
3935		local v = decoder[a]*0x40000 + decoder[b]*0x1000
3936		t[k] = char( extract(v,16,8))
3937	end
3938	return concat( t )
3939end
3940
3941local pkg
3942if not fs.exists(shell.resolve("CCKernel2.cpkg")) then
3943    local get = http.get("http://cppconsole.bruienne.com/base64get.php?url=https://raw.githubusercontent.com/MCJack123/CCKernel2/master/CCKernel2.cpkg")
3944    os.queueEvent("nosleep")
3945    os.pullEvent()
3946    pkg = readstring(base64.decode(get.readAll()))
3947    get.close()
3948else pkg = archive(shell.resolve("CCKernel2.cpkg")) end
3949if not pkg then error("Could not find package") end
3950pkg.writeFile("CCKit.lua", "/CCKit.lua")
3951pkg.writeFile("CCLog.lua", "/CCLog.lua")
3952pkg.writeFile("CCOSCrypto.lua", "/CCOSCrypto.lua")
3953_G.CCLog = dofile("/CCLog.lua")
3954if not CCLog then return end
3955if not os.loadAPI("CCKit.lua") then return end
3956if not os.loadAPI("CCOSCrypto.lua") then return end
3957
3958local function WelcomeViewController()
3959    local retval = CCKit.CCViewController()
3960    retval.back = CCKit.CCButton(5, 14, 8, 1)
3961    retval.next = CCKit.CCButton(19, 14, 8, 1)
3962    function retval:exit()
3963        self.application:deregisterObject(self.back.name)
3964        self.application:deregisterObject(self.next.name)
3965        self.window:close()
3966    end
3967    function retval:continue()
3968        local vc = ReadmeViewController()
3969        self.application:deregisterObject(self.back.name)
3970        self.application:deregisterObject(self.next.name)
3971        self.window:setViewController(vc, self.application)
3972    end
3973    function retval:viewDidLoad()
3974        local title = CCKit.CCLabel(1, 1, "* Welcome")
3975        self.view:addSubview(title)
3976        local text = CCKit.CCTextView(1, 3, 30, 10)
3977        text:setText("Welcome to the setup program for CCKernel2. You will be guided through the steps necessary to install CCKernel2.")
3978        self.view:addSubview(text)
3979        self.back:setText("Cancel")
3980        self.back:setAction(self.exit, self)
3981        self.view:addSubview(self.back)
3982        self.next:setText("Next")
3983        self.next:setAction(self.continue, self)
3984        self.view:addSubview(self.next)
3985    end
3986    return retval
3987end
3988
3989function ReadmeViewController()
3990    local retval = CCKit.CCViewController()
3991    retval.back = CCKit.CCButton(5, 14, 8, 1)
3992    retval.next = CCKit.CCButton(19, 14, 8, 1)
3993    function retval:goback()
3994        self.application:deregisterObject(self.back.name)
3995        self.application:deregisterObject(self.next.name)
3996        self.window:setViewController(WelcomeViewController(), self.application)
3997    end
3998    function retval:continue()
3999        self.application:deregisterObject(self.back.name)
4000        self.application:deregisterObject(self.next.name)
4001        self.window:setViewController(ConfigureViewController(), self.application)
4002    end
4003    function retval:viewDidLoad()
4004        local title = CCKit.CCLabel(1, 1, "* Readme")
4005        self.view:addSubview(title)
4006        local text = CCKit.CCTextView(0, 0, 30, 55)
4007        text:setText([[CCKernel2 is the most advanced extension to CraftOS ever made. It adds a significant number of new features, including:
4008* Cooperative multiprocessing
4009* Native IPC calls
4010* Process signaling
4011* A built-in Lua debugger
4012* A multi-user system
4013* File permissions
4014* Device files (/dev)
4015* Eight virtual terminals
4016* A Built-in logger
4017* A Unix-style file hierarchy
4018* `os.loadAPI` resolution paths
4019* Process I/O pipes
4020* A systemd-like init program
4021* Many new shell programs
4022CCKernel2 is designed to complement the existing CraftOS shell while rewriting much of its functionality. The fs API has been completely rewritten from the ground up to support user permissions.
4023On the next page, you will be asked to create a new user. You will log in with the short name and password you set, while the full name is used in supported applications. You can also let CCKernel2 run at startup, or you can choose to run CCKernel2 manually.
4024CCKernel2's API reference can be viewed through the built-in help articles that will be installed.
4025
4026CCKernel2 was made by JackMacWindows (GitHub: MCJack123), available as a free and open-source project on GitHub. Feel free to submit any issues with the program.]])
4027        local scroll = CCKit.CCScrollView(1, 3, 31, 10, 55)
4028        self.view:addSubview(scroll)
4029        scroll:addSubview(text)
4030        self.back:setText("Back")
4031        self.back:setAction(self.goback, self)
4032        self.view:addSubview(self.back)
4033        self.next:setText("Next")
4034        self.next:setAction(self.continue, self)
4035        self.view:addSubview(self.next)
4036    end
4037    return retval
4038end
4039
4040local fullName, shortName, password, startup
4041
4042function ConfigureViewController()
4043    local retval = CCKit.CCViewController()
4044    retval.back = CCKit.CCButton(5, 14, 8, 1)
4045    retval.next = CCKit.CCButton(19, 14, 8, 1)
4046    retval.fullNameBox = CCKit.CCTextField(12, 3, 18)
4047    retval.shortNameBox = CCKit.CCTextField(13, 5, 17)
4048    retval.passwordBox = CCKit.CCTextField(11, 7, 19)
4049    retval.startup = CCKit.CCCheckbox(1, 9, "Run CCKernel2 at startup")
4050    function retval:goback()
4051        local vc = ReadmeViewController()
4052        self.application:deregisterObject(self.back.name)
4053        self.application:deregisterObject(self.next.name)
4054        self.application:deregisterObject(self.fullNameBox.name)
4055        self.application:deregisterObject(self.shortNameBox.name)
4056        self.application:deregisterObject(self.passwordBox.name)
4057        self.application:deregisterObject(self.startup.name)
4058        self.window:setViewController(vc, self.application)
4059    end
4060    function retval:continue()
4061        if self.fullNameBox.text == "" or self.shortNameBox.text == "" or self.passwordBox.text == "" then
4062            local alert = CCKit.CCAlertWindow(2, 2, 10, 5, "Alert", "Please fill in all fields.", self.application)
4063            self.window:present(alert)
4064            return
4065        end
4066        fullName = self.fullNameBox.text
4067        shortName = self.shortNameBox.text
4068        password = self.passwordBox.text
4069        startup = self.startup.isOn
4070        self.application:deregisterObject(self.back.name)
4071        self.application:deregisterObject(self.next.name)
4072        self.application:deregisterObject(self.fullNameBox.name)
4073        self.application:deregisterObject(self.shortNameBox.name)
4074        self.application:deregisterObject(self.passwordBox.name)
4075        self.application:deregisterObject(self.startup.name)
4076        self.window:setViewController(InstallViewController(), self.application)
4077    end
4078    function retval:viewDidLoad()
4079        local title = CCKit.CCLabel(1, 1, "* Configuration")
4080        self.view:addSubview(title)
4081        local fullNameLabel = CCKit.CCLabel(1, 3, "Full Name: ")
4082        self.view:addSubview(fullNameLabel)
4083        self.fullNameBox.placeholderText = "Full name"
4084        self.view:addSubview(self.fullNameBox)
4085        local shortNameLabel = CCKit.CCLabel(1, 5, "Short Name: ")
4086        self.view:addSubview(shortNameLabel)
4087        self.shortNameBox.placeholderText = "Short name"
4088        self.view:addSubview(self.shortNameBox)
4089        local passwordLabel = CCKit.CCLabel(1, 7, "Password: ")
4090        self.view:addSubview(passwordLabel)
4091        self.passwordBox.placeholderText = "Password"
4092        self.passwordBox.textReplacement = "*"
4093        self.view:addSubview(self.passwordBox)
4094        self.startup.isOn = true
4095        self.view:addSubview(self.startup)
4096        self.back:setText("Back")
4097        self.back:setAction(self.goback, self)
4098        self.view:addSubview(self.back)
4099        self.next:setText("Next")
4100        self.next:setAction(self.continue, self)
4101        self.view:addSubview(self.next)
4102    end
4103    return retval
4104end
4105
4106function InstallViewController()
4107    local retval = CCKit.CCViewController()
4108    retval.back = CCKit.CCButton(5, 14, 8, 1)
4109    retval.next = CCKit.CCButton(19, 14, 8, 1)
4110    function retval:goback()
4111        local vc = ReadmeViewController()
4112        self.application:deregisterObject(self.back.name)
4113        self.application:deregisterObject(self.next.name)
4114        self.window:setViewController(vc, self.application)
4115    end
4116    function retval:continue()
4117        local newwin = CCKit.CCWindow(14, 5, 22, 5)
4118        newwin:setTitle("Installing")
4119        local newvc = ProgressViewController()
4120        newwin:setViewController(newvc, self.application)
4121        self.window:close()
4122        self.window:present(newwin)
4123    end
4124    function retval:viewDidLoad()
4125        local title = CCKit.CCLabel(1, 1, "* Ready to Install")
4126        self.view:addSubview(title)
4127        local text = CCKit.CCTextView(1, 3, 30, 10)
4128        text:setText("The files will be installed to /. CCKernel2 will take up " .. pkg.size .. " bytes of space. Click Install to start the installation.")
4129        self.view:addSubview(text)
4130        self.back:setText("Back")
4131        self.back:setAction(self.goback, self)
4132        self.view:addSubview(self.back)
4133        self.next:setText("Install")
4134        self.next:setAction(self.continue, self)
4135        self.view:addSubview(self.next)
4136    end
4137    return retval
4138end
4139
4140function ProgressViewController()
4141    local retval = CCKit.multipleInheritance(CCKit.CCViewController(), CCKit.CCEventHandler("ProgressViewController"))
4142    retval.progressBar = CCKit.CCProgressBar(1, 2, 20)
4143    retval.name = "PVC"
4144    retval.status = CCKit.CCTextView(1, 1, 20, 1)
4145    retval.started = false
4146    function retval:exit()
4147        newwin = CCKit.CCWindow(11, 5, 28, 9)
4148        newwin:setTitle("Complete")
4149        local newvc = CompleteViewController()
4150        newwin:setViewController(newvc, self.application)
4151        self.window:present(newwin)
4152        self.window:close()
4153        self.application:deregisterObject(self.name)
4154        return true
4155        --os.queueEvent("redraw_window", newwin.name)
4156    end
4157    function retval:install()
4158        if not retval.started then
4159            retval.started = true
4160            os.queueEvent("installing")
4161            return
4162        end
4163        local manifest_file = pkg.open("manifest.ltn", "r")
4164        local manifest = textutils.unserialize(manifest_file.readAll())
4165        manifest_file.close()
4166        local filecount = 0
4167        for k,v in pairs(manifest.files) do filecount = filecount + 1 end
4168        self.status:setText("Preparing...")
4169        for k,v in pairs(manifest.directories) do fs.makeDir(v) end
4170        self.progressBar:setIndeterminate(false)
4171        self.progressBar:setProgress(0.0)
4172        local completed = 0
4173        for src,dest in pairs(manifest.files) do
4174            self.status:setText("Installing (" .. completed + 1 .. "/" .. filecount .. ")")
4175            pkg.writeFile(src, dest)
4176            completed = completed + 1
4177            self.progressBar:setProgress(completed / filecount)
4178            self.view:draw()
4179            os.queueEvent("nosleep")
4180            os.pullEvent()
4181        end
4182        self.status:setText("Setting up...")
4183        self.progressBar:setIndeterminate(true)
4184        local file = fs.open("/etc/passwd", "w")
4185        file.write(textutils.serialize({
4186            [-1] = {name = "superroot", fullName = "Kernel Process", password = nil},
4187            [0] = {name = "root", fullName = "Superuser", password = nil},
4188            [1] = {name = shortName, fullName = fullName, password = CCOSCrypto.sha256(password)}
4189        }))
4190        file.close()
4191        if startup then
4192            local file = fs.open("/startup.lua", fs.exists("/startup.lua") and "a" or "w")
4193            file.writeLine("os.queueEvent(\"start\")")
4194            file.writeLine("shell.run(\"/kernel.lua\")")
4195            file.writeLine("os.shutdown()")
4196            file.close()
4197        end
4198        os.queueEvent("finished")
4199    end
4200    function retval:viewDidLoad()
4201        self.maximizable = false
4202        self.status.text = "Loading manifest..."
4203        self.progressBar.isIndeterminate = true
4204        self.view:addSubview(self.status)
4205        self.view:addSubview(self.progressBar)
4206        self.view:draw()
4207        self.window:redraw()
4208        self:addEvent("installing", self.install)
4209        self:addEvent("finished", self.exit)
4210        self.window:registerObject(self)
4211        os.queueEvent("installing")
4212    end
4213    return retval
4214end
4215
4216function CompleteViewController()
4217    local retval = CCKit.CCViewController()
4218    function retval:exit()
4219        self.window:close()
4220        fs.delete("/CCKit.lua")
4221        fs.delete("/CCLog.lua")
4222        fs.delete("/CCOSCrypto.lua")
4223        if fs.exists("/install.lua") then fs.delete("/install.lua") end
4224        os.reboot()
4225    end
4226    function retval:viewDidLoad()
4227        local text = CCKit.CCTextView(1, 1, self.view.frame.width - 2, 4)
4228        text:setText("Installation is complete. You must restart your computer for changes to take effect.")
4229        self.view:addSubview(text)
4230        local button = CCKit.CCButton(9, 6, 8, 1)
4231        button:setText("Reboot")
4232        button:setAction(self.exit, self)
4233        self.view:addSubview(button)
4234    end
4235    return retval
4236end
4237
4238CCKit.CCMain(10, 2, 32, 17, "CCKernel2 Installer", WelcomeViewController, colors.blue, "CCKernel2 Installer", true)
4239fs.delete("/CCKit.lua")
4240fs.delete("/CCLog.lua")
4241fs.delete("/CCOSCrypto.lua")
4242if fs.exists("/install.lua") then fs.delete("/install.lua") end