--[[ zlib-deflate.lua Version: 0.2.0 LastModified: September 13 2015 Copyright (C) 2014 David McWilliams This library is a Lua implementation of zlib deflate. Based on zlib-js (Javascript implementation) http://www.onicos.com/staff/iz/release/zlib-js/zlib-js.html Copyright (C) 2012 Masanao Izumo Based on zlib (Original implementation) http://www.zlib.net/ Copyright (C) 1995-2013 Jean-loup Gailly and Mark Adler This software is provided 'as-is', without any express or implied warranty. In no event will the authors be held liable for any damages arising from the use of this software. Permission is granted to anyone to use this software for any purpose, including commercial applications, and to alter it and redistribute it freely, subject to the following restrictions: 1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required. 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software. 3. This notice may not be removed or altered from any source distribution. ]]-- function requireany(...) -- (c) 2011-2012 David Manura. Licensed under Lua 5.1 terms (MIT license). local errs = {} for i = 1, select('#', ...) do local name = select(i, ...) if type(name) ~= 'string' then return name, nil end local ok, mod = pcall(require, name) if ok then return mod, name end errs[#errs+1] = mod end error(table.concat(errs, '\n'), 2) end local crc32 = require 'crc32lua' . crc32_byte -- local bit, name_ = requireany('bit', 'bit32', 'bit.numberlua') local bnot = bit32.bnot local band, bor, bxor = bit32.band, bit32.bor, bit32.bxor local lshift, rshift = bit32.lshift, bit32.rshift -- common definitions local ZLIB = {} -- Allowed flush values; see deflate() and inflate() below for details ZLIB.Z_NO_FLUSH = 0 ZLIB.Z_PARTIAL_FLUSH = 1 ZLIB.Z_SYNC_FLUSH = 2 ZLIB.Z_FULL_FLUSH = 3 ZLIB.Z_FINISH = 4 ZLIB.Z_BLOCK = 5 ZLIB.Z_TREES = 6 -- Return codes for the compression/decompression functions. Negative values are errors, positive values are used for special but normal events. ZLIB.Z_OK = 0 ZLIB.Z_STREAM_END = 1 ZLIB.Z_NEED_DICT = 2 ZLIB.Z_ERRNO = (-1) ZLIB.Z_STREAM_ERROR = (-2) ZLIB.Z_DATA_ERROR = (-3) ZLIB.Z_MEM_ERROR = (-4) ZLIB.Z_BUF_ERROR = (-5) ZLIB.Z_VERSION_ERROR = (-6) -- compression levels ZLIB.Z_NO_COMPRESSION = 0 ZLIB.Z_BEST_SPEED = 1 ZLIB.Z_BEST_COMPRESSION = 9 ZLIB.Z_DEFAULT_COMPRESSION = (-1) -- compression strategy; see deflateInit2() below for details ZLIB.Z_FILTERED = 1 ZLIB.Z_HUFFMAN_ONLY = 2 ZLIB.Z_RLE = 3 ZLIB.Z_FIXED = 4 ZLIB.Z_DEFAULT_STRATEGY = 0 -- Possible values of the data_type field (though see inflate()) ZLIB.Z_BINARY = 0 ZLIB.Z_TEXT = 1 ZLIB.Z_ASCII = ZLIB.Z_TEXT -- for compatibility with 1.2.2 and earlier ZLIB.Z_UNKNOWN = 2 -- The deflate compression method (the only one supported in this version) ZLIB.Z_DEFLATED = 8 -- Maximum value for memLevel in deflateInit2 ZLIB.MAX_MEM_LEVEL = 9 -- z_stream constructor ZLIB.z_stream = function() local s = {} s.next_in = 0 -- next input byte s.avail_in = 0 -- number of bytes available in input_data s.total_in = 0 -- total number of input bytes read so far s.next_out = 0 -- next output byte s.avail_out = 0 -- remaining free space at next_out s.total_out = 0 -- total number of bytes output so far s.msg = nil -- last error message, nil if no error s.state = nil -- not visible by applications s.data_type = 0 -- best guess about the data type: binary or text s.input_data = '' -- input data s.output_data = '' -- output data s.error = 0 -- error code s.checksum_function = nil -- crc32(for gzip) or adler32(for zlib) return s end ZLIB.crc32 = function(crc, buf, offset, len) if (buf == nil) then return 0 end while (len > 0) do crc = crc32(buf[offset], crc) offset = offset + 1 len = len - 1 end return crc end -- Maximum value for windowBits in deflateInit2 and inflateInit2. -- WARNING: reducing MAX_WBITS makes minigzip unable to extract .gz files created by gzip. -- (Files created by minigzip can still be extracted by gzip.) ZLIB.MAX_WBITS = 15 ZLIB.OS_CODE = 0xff -- unknown -- default memLevel local DEF_MEM_LEVEL if (ZLIB.MAX_MEM_LEVEL >= 8) then DEF_MEM_LEVEL = 8 else DEF_MEM_LEVEL = ZLIB.MAX_MEM_LEVEL end -- The three kinds of block type local STORED_BLOCK = 0 local STATIC_TREES = 1 local DYN_TREES = 2 -- The minimum and maximum match lengths local MIN_MATCH = 3 local MAX_MATCH = 258 -- preset dictionary flag in zlib header local PRESET_DICT = 0x20 -- =========================================================================== -- Internal compression state. -- number of length codes, not counting the special END_BLOCK code local LENGTH_CODES = 29 -- number of literal bytes 0..255 local LITERALS = 256 -- number of Literal or Length codes, including the END_BLOCK code local L_CODES = (LITERALS+1+LENGTH_CODES) -- number of distance codes local D_CODES = 30 -- number of codes used to transfer the bit lengths local BL_CODES = 19 -- maximum heap size local HEAP_SIZE = (2*L_CODES+1) -- All codes must not exceed MAX_BITS bits local MAX_BITS = 15 -- size of bit buffer in bi_buf local Buf_size = 16 -- Stream status local INIT_STATE = 42 local EXTRA_STATE = 69 local NAME_STATE = 73 local COMMENT_STATE = 91 local HCRC_STATE = 103 local BUSY_STATE = 113 local FINISH_STATE = 666 function new_array(size) local ary = {} for i = 0, size-1 do ary[i] = 0 end return ary end function new_ct_array(count) local ary = {} for i = 0, count-1 do ary[i] = {fc=0, dl=0} end return ary end function getarg(opts, name, def_value) if (opts and opts[name]) then return opts[name] end return def_value end function checksum_none() return 0 end -- constructor function tree_desc() local this = {} this.dyn_tree = nil -- the dynamic tree this.max_code = 0 -- largest code with non zero frequency this.stat_desc = nil -- the corresponding static tree return this end -- constructor function deflate_state() local this = {} this.strm = nil -- pointer back to this zlib stream (TODO remove: cross reference) this.status = 0 -- as the name implies this.pending_buf = '' -- output still pending this.pending_buf_size = 0 -- size of pending_buf this.wrap = 0 -- bit 0 true for zlib, bit 1 true for gzip this.gzhead = nil -- TODO: gzip header information to write this.gzindex = 0 -- TODO: where in extra, name, or comment this.method = 0 -- STORED (for zip only) or DEFLATED this.last_flush = 0 -- value of flush param for previous deflate call -- used by deflate.c: this.w_size = 0 -- LZ77 window size (32K by default) this.w_bits = 0 -- log2(w_size) (8..16) this.w_mask = 0 -- w_size - 1 -- Sliding window. Input bytes are read into the second half of the window, and move to the first half later to keep a dictionary of at least wSize bytes. With this organization, matches are limited to a distance of wSize-MAX_MATCH bytes, but this ensures that IO is always performed with a length multiple of the block size. Also, it limits the window size to 64K, which is quite useful on MSDOS. To do: use the user input buffer as sliding window. this.window = nil -- Actual size of window: 2*wSize, except when the user input buffer is directly used as sliding window. this.window_size = 0 -- Link to older string with same hash index. To limit the size of this array to 64K, this link is maintained only for the last 32K strings. An index in this array is thus a window index modulo 32K. this.prev = nil this.head = nil -- Heads of the hash chains or NIL. this.ins_h = 0 -- hash index of string to be inserted this.hash_size = 0 -- number of elements in hash table this.hash_bits = 0 -- log2(hash_size) this.hash_mask = 0 -- hash_size-1 -- Number of bits by which ins_h must be shifted at each input step. It must be such that after MIN_MATCH steps, the oldest byte no longer takes part in the hash key, that is: hash_shift * MIN_MATCH >= hash_bits this.hash_shift = 0 -- Window position at the beginning of the current output block. Gets negative when the window is moved backwards. this.block_start = 0 this.match_length = 0 -- length of best match this.prev_match = 0 -- previous match this.match_available = false -- set if previous match exists this.strstart = 0 -- start of string to insert this.match_start = 0 -- start of matching string this.lookahead = 0 -- number of valid bytes ahead in window -- Length of the best match at previous step. Matches not greater than this are discarded. This is used in the lazy match evaluation. this.prev_length = 0 this.max_chain_length = 0 -- To speed up deflation, hash chains are never searched beyond this length. A higher limit improves compression ratio but degrades the speed. -- Attempt to find a better match only when the current match is strictly smaller than this value. This mechanism is used only for compression levels >= 4. this.max_lazy_match = 0 this.level = 0 -- compression level (1..9) this.strategy = 0 -- favor or force Huffman coding -- Use a faster search when the previous match is longer than this this.good_match = 0 this.nice_match = 0 -- Stop searching when current match exceeds this -- used by trees.c: -- Didn't use ct_data typedef below to suppress compiler warning this.dyn_ltree = new_ct_array(HEAP_SIZE) -- literal and length tree this.dyn_dtree = new_ct_array(2*D_CODES+1) -- distance tree this.bl_tree = new_ct_array(2*BL_CODES+1) -- Huffman tree for bit lengths this.l_desc = tree_desc() -- desc. for literal tree this.d_desc = tree_desc() -- desc. for distance tree this.bl_desc = tree_desc() -- desc. for bit length tree -- number of codes at each bit length for an optimal tree this.bl_count = new_array(MAX_BITS+1) -- The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used. -- The same heap array is used to build all trees. this.heap = new_array(2*L_CODES+1) -- heap used to build the Huffman trees this.heap_len = 0 -- number of elements in the heap this.heap_max = 0 -- element of largest frequency -- Depth of each subtree used as tie breaker for trees of equal frequency this.depth = new_array(2*L_CODES+1) this.l_buf = nil -- buffer for literals or lengths -- Size of match buffer for literals/lengths this.lit_bufsize = 0 this.last_lit = 0 -- running index in l_buf -- Buffer for distances. To simplify the code, d_buf and l_buf have the same number of elements. To use different lengths, an extra flag array would be necessary. this.d_buf = nil this.opt_len = 0 -- bit length of current block with optimal trees this.static_len = 0 -- bit length of current block with static trees this.matches = 0 -- number of string matches in current block this.insert = 0 -- bytes at end of window left to insert --this.compressed_len = 0 -- total bit length of compressed file mod 2^32 this.bits_sent = 0 -- bit length of compressed data sent mod 2^32 -- Output buffer. bits are inserted starting at the bottom (least significant bits). this.bi_buf = 0 -- Number of valid bits in bi_buf. All bits above the last valid bit are always zero. this.bi_valid = 0 -- High water mark offset in window for initialized bytes -- bytes above this are set to zero in order to avoid memory check warnings when longest match routines access bytes past the input. This is then updated to the new high water mark. this.high_water = 0 return this end -- Minimum amount of lookahead, except at the end of the input file. See deflate.c for comments about the MIN_MATCH+1. local MIN_LOOKAHEAD = (MAX_MATCH+MIN_MATCH+1) -- In order to simplify the code, particularly on 16 bit machines, match distances are limited to MAX_DIST instead of WSIZE. function MAX_DIST(s) return s.w_size - MIN_LOOKAHEAD end -- Number of bytes after end of data in window to initialize in order to avoid memory checker errors from longest match routines local WIN_INIT = MAX_MATCH -- =========================================================================== -- trees.c -- output deflated data using Huffman coding -- Constants -- Bit length codes must not exceed MAX_BL_BITS bits local MAX_BL_BITS = 7 -- end of block literal code local END_BLOCK = 256 -- repeat previous bit length 3-6 times (2 bits of repeat count) local REP_3_6 = 16 -- repeat a zero length 3-10 times (3 bits of repeat count) local REPZ_3_10 = 17 -- repeat a zero length 11-138 times (7 bits of repeat count) local REPZ_11_138 = 18 -- extra bits for each length code local extra_lbits = {0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0} extra_lbits[0] = 0 -- extra bits for each distance code local extra_dbits = {0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13} extra_dbits[0] = 0 -- extra bits for each bit length code local extra_blbits = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7} extra_blbits[0] = 0 -- The lengths of the bit length codes are sent in order of decreasing probability, to avoid transmitting the lengths for unused bit length codes. local bl_order = {17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15} bl_order[0] = 16 -- see definition of array dist_code below local DIST_CODE_LEN = 512 local static_ltree = { {fc=140, dl=8}, {fc= 76, dl=8}, {fc=204, dl=8}, {fc= 44, dl=8}, {fc=172, dl=8}, {fc=108, dl=8}, {fc=236, dl=8}, {fc= 28, dl=8}, {fc=156, dl=8}, {fc= 92, dl=8}, {fc=220, dl=8}, {fc= 60, dl=8}, {fc=188, dl=8}, {fc=124, dl=8}, {fc=252, dl=8}, {fc= 2, dl=8}, {fc=130, dl=8}, {fc= 66, dl=8}, {fc=194, dl=8}, {fc= 34, dl=8}, {fc=162, dl=8}, {fc= 98, dl=8}, {fc=226, dl=8}, {fc= 18, dl=8}, {fc=146, dl=8}, {fc= 82, dl=8}, {fc=210, dl=8}, {fc= 50, dl=8}, {fc=178, dl=8}, {fc=114, dl=8}, {fc=242, dl=8}, {fc= 10, dl=8}, {fc=138, dl=8}, {fc= 74, dl=8}, {fc=202, dl=8}, {fc= 42, dl=8}, {fc=170, dl=8}, {fc=106, dl=8}, {fc=234, dl=8}, {fc= 26, dl=8}, {fc=154, dl=8}, {fc= 90, dl=8}, {fc=218, dl=8}, {fc= 58, dl=8}, {fc=186, dl=8}, {fc=122, dl=8}, {fc=250, dl=8}, {fc= 6, dl=8}, {fc=134, dl=8}, {fc= 70, dl=8}, {fc=198, dl=8}, {fc= 38, dl=8}, {fc=166, dl=8}, {fc=102, dl=8}, {fc=230, dl=8}, {fc= 22, dl=8}, {fc=150, dl=8}, {fc= 86, dl=8}, {fc=214, dl=8}, {fc= 54, dl=8}, {fc=182, dl=8}, {fc=118, dl=8}, {fc=246, dl=8}, {fc= 14, dl=8}, {fc=142, dl=8}, {fc= 78, dl=8}, {fc=206, dl=8}, {fc= 46, dl=8}, {fc=174, dl=8}, {fc=110, dl=8}, {fc=238, dl=8}, {fc= 30, dl=8}, {fc=158, dl=8}, {fc= 94, dl=8}, {fc=222, dl=8}, {fc= 62, dl=8}, {fc=190, dl=8}, {fc=126, dl=8}, {fc=254, dl=8}, {fc= 1, dl=8}, {fc=129, dl=8}, {fc= 65, dl=8}, {fc=193, dl=8}, {fc= 33, dl=8}, {fc=161, dl=8}, {fc= 97, dl=8}, {fc=225, dl=8}, {fc= 17, dl=8}, {fc=145, dl=8}, {fc= 81, dl=8}, {fc=209, dl=8}, {fc= 49, dl=8}, {fc=177, dl=8}, {fc=113, dl=8}, {fc=241, dl=8}, {fc= 9, dl=8}, {fc=137, dl=8}, {fc= 73, dl=8}, {fc=201, dl=8}, {fc= 41, dl=8}, {fc=169, dl=8}, {fc=105, dl=8}, {fc=233, dl=8}, {fc= 25, dl=8}, {fc=153, dl=8}, {fc= 89, dl=8}, {fc=217, dl=8}, {fc= 57, dl=8}, {fc=185, dl=8}, {fc=121, dl=8}, {fc=249, dl=8}, {fc= 5, dl=8}, {fc=133, dl=8}, {fc= 69, dl=8}, {fc=197, dl=8}, {fc= 37, dl=8}, {fc=165, dl=8}, {fc=101, dl=8}, {fc=229, dl=8}, {fc= 21, dl=8}, {fc=149, dl=8}, {fc= 85, dl=8}, {fc=213, dl=8}, {fc= 53, dl=8}, {fc=181, dl=8}, {fc=117, dl=8}, {fc=245, dl=8}, {fc= 13, dl=8}, {fc=141, dl=8}, {fc= 77, dl=8}, {fc=205, dl=8}, {fc= 45, dl=8}, {fc=173, dl=8}, {fc=109, dl=8}, {fc=237, dl=8}, {fc= 29, dl=8}, {fc=157, dl=8}, {fc= 93, dl=8}, {fc=221, dl=8}, {fc= 61, dl=8}, {fc=189, dl=8}, {fc=125, dl=8}, {fc=253, dl=8}, {fc= 19, dl=9}, {fc=275, dl=9}, {fc=147, dl=9}, {fc=403, dl=9}, {fc= 83, dl=9}, {fc=339, dl=9}, {fc=211, dl=9}, {fc=467, dl=9}, {fc= 51, dl=9}, {fc=307, dl=9}, {fc=179, dl=9}, {fc=435, dl=9}, {fc=115, dl=9}, {fc=371, dl=9}, {fc=243, dl=9}, {fc=499, dl=9}, {fc= 11, dl=9}, {fc=267, dl=9}, {fc=139, dl=9}, {fc=395, dl=9}, {fc= 75, dl=9}, {fc=331, dl=9}, {fc=203, dl=9}, {fc=459, dl=9}, {fc= 43, dl=9}, {fc=299, dl=9}, {fc=171, dl=9}, {fc=427, dl=9}, {fc=107, dl=9}, {fc=363, dl=9}, {fc=235, dl=9}, {fc=491, dl=9}, {fc= 27, dl=9}, {fc=283, dl=9}, {fc=155, dl=9}, {fc=411, dl=9}, {fc= 91, dl=9}, {fc=347, dl=9}, {fc=219, dl=9}, {fc=475, dl=9}, {fc= 59, dl=9}, {fc=315, dl=9}, {fc=187, dl=9}, {fc=443, dl=9}, {fc=123, dl=9}, {fc=379, dl=9}, {fc=251, dl=9}, {fc=507, dl=9}, {fc= 7, dl=9}, {fc=263, dl=9}, {fc=135, dl=9}, {fc=391, dl=9}, {fc= 71, dl=9}, {fc=327, dl=9}, {fc=199, dl=9}, {fc=455, dl=9}, {fc= 39, dl=9}, {fc=295, dl=9}, {fc=167, dl=9}, {fc=423, dl=9}, {fc=103, dl=9}, {fc=359, dl=9}, {fc=231, dl=9}, {fc=487, dl=9}, {fc= 23, dl=9}, {fc=279, dl=9}, {fc=151, dl=9}, {fc=407, dl=9}, {fc= 87, dl=9}, {fc=343, dl=9}, {fc=215, dl=9}, {fc=471, dl=9}, {fc= 55, dl=9}, {fc=311, dl=9}, {fc=183, dl=9}, {fc=439, dl=9}, {fc=119, dl=9}, {fc=375, dl=9}, {fc=247, dl=9}, {fc=503, dl=9}, {fc= 15, dl=9}, {fc=271, dl=9}, {fc=143, dl=9}, {fc=399, dl=9}, {fc= 79, dl=9}, {fc=335, dl=9}, {fc=207, dl=9}, {fc=463, dl=9}, {fc= 47, dl=9}, {fc=303, dl=9}, {fc=175, dl=9}, {fc=431, dl=9}, {fc=111, dl=9}, {fc=367, dl=9}, {fc=239, dl=9}, {fc=495, dl=9}, {fc= 31, dl=9}, {fc=287, dl=9}, {fc=159, dl=9}, {fc=415, dl=9}, {fc= 95, dl=9}, {fc=351, dl=9}, {fc=223, dl=9}, {fc=479, dl=9}, {fc= 63, dl=9}, {fc=319, dl=9}, {fc=191, dl=9}, {fc=447, dl=9}, {fc=127, dl=9}, {fc=383, dl=9}, {fc=255, dl=9}, {fc=511, dl=9}, {fc= 0, dl=7}, {fc= 64, dl=7}, {fc= 32, dl=7}, {fc= 96, dl=7}, {fc= 16, dl=7}, {fc= 80, dl=7}, {fc= 48, dl=7}, {fc=112, dl=7}, {fc= 8, dl=7}, {fc= 72, dl=7}, {fc= 40, dl=7}, {fc=104, dl=7}, {fc= 24, dl=7}, {fc= 88, dl=7}, {fc= 56, dl=7}, {fc=120, dl=7}, {fc= 4, dl=7}, {fc= 68, dl=7}, {fc= 36, dl=7}, {fc=100, dl=7}, {fc= 20, dl=7}, {fc= 84, dl=7}, {fc= 52, dl=7}, {fc=116, dl=7}, {fc= 3, dl=8}, {fc=131, dl=8}, {fc= 67, dl=8}, {fc=195, dl=8}, {fc= 35, dl=8}, {fc=163, dl=8}, {fc= 99, dl=8}, {fc=227, dl=8} } static_ltree[0] = {fc=12, dl=8} local static_dtree = { {fc=16, dl=5}, {fc= 8, dl=5}, {fc=24, dl=5}, {fc= 4, dl=5}, {fc=20, dl=5}, {fc=12, dl=5}, {fc=28, dl=5}, {fc= 2, dl=5}, {fc=18, dl=5}, {fc=10, dl=5}, {fc=26, dl=5}, {fc= 6, dl=5}, {fc=22, dl=5}, {fc=14, dl=5}, {fc=30, dl=5}, {fc= 1, dl=5}, {fc=17, dl=5}, {fc= 9, dl=5}, {fc=25, dl=5}, {fc= 5, dl=5}, {fc=21, dl=5}, {fc=13, dl=5}, {fc=29, dl=5}, {fc= 3, dl=5}, {fc=19, dl=5}, {fc=11, dl=5}, {fc=27, dl=5}, {fc= 7, dl=5}, {fc=23, dl=5} } static_dtree[0] = {fc=0, dl=5} local _dist_code = { 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 0, 0, 16, 17, 18, 18, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29 } _dist_code[0] = 0 local _length_code = { 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28 } _length_code[0] = 0 local base_length = { 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 20, 24, 28, 32, 40, 48, 56, 64, 80, 96, 112, 128, 160, 192, 224, 0 } base_length[0] = 0 local base_dist = { 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576 } base_dist[0] = 0 local static_l_desc = { static_tree = static_ltree, extra_bits = extra_lbits, extra_base = LITERALS+1, elems = L_CODES, max_length = MAX_BITS } local static_d_desc = { static_tree = static_dtree, extra_bits = extra_dbits, extra_base = 0, elems = D_CODES, max_length = MAX_BITS } local static_bl_desc = { static_tree = nil, extra_bits = extra_blbits, extra_base = 0, elems = BL_CODES, max_length = MAX_BL_BITS } -- Mapping from a distance to a distance code. dist is the distance - 1 and must not have side effects. _dist_code[256] and _dist_code[257] are never used. function d_code(dist) if (dist < 256) then return _dist_code[dist] end return _dist_code[256 + rshift(dist, 7)] end -- Send a code of the given tree. c and tree must not have side effects function send_code(s, c, tree) return send_bits(s, tree[c].fc, tree[c].dl) end -- Output a byte on the stream. -- IN assertion: there is enough room in pending_buf. function put_byte(s, c) s.pending_buf = s.pending_buf .. string.char(c) end -- Output a short LSB first on the stream. -- IN assertion: there is enough room in pendingBuf. function put_short(s, w) s.pending_buf = s.pending_buf .. string.char(band(w, 0xff)) s.pending_buf = s.pending_buf .. string.char(band(rshift(w, 8), 0xff)) end function send_bits(s, value, length) s.bits_sent = s.bits_sent + length -- If not enough room in bi_buf, use (valid) bits from bi_buf and (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) unused bits in value. if (s.bi_valid > Buf_size - length) then s.bi_buf = bor(s.bi_buf, lshift(value, s.bi_valid)) put_short(s, s.bi_buf) s.bi_buf = rshift(value, Buf_size - s.bi_valid) s.bi_valid = s.bi_valid + length - Buf_size else s.bi_buf = bor(s.bi_buf, lshift(value, s.bi_valid)) s.bi_valid = s.bi_valid + length end end -- Initialize the tree data structures for a new zlib stream. function _tr_init(s) s.l_desc.dyn_tree = s.dyn_ltree s.l_desc.stat_desc = static_l_desc s.d_desc.dyn_tree = s.dyn_dtree s.d_desc.stat_desc = static_d_desc s.bl_desc.dyn_tree = s.bl_tree s.bl_desc.stat_desc = static_bl_desc s.bi_buf = 0 s.bi_valid = 0 --s.compressed_len = 0 --s.bits_sent = 0 -- Initialize the first block of the first file: init_block(s) end -- Initialize a new block. function init_block(s) -- Initialize the trees. for n = 0, L_CODES-1 do s.dyn_ltree[n].fc = 0 end for n = 0, D_CODES-1 do s.dyn_dtree[n].fc = 0 end for n = 0, BL_CODES-1 do s.bl_tree[n].fc = 0 end s.dyn_ltree[END_BLOCK].fc = 1 s.opt_len = 0 s.static_len = 0 s.last_lit = 0 s.matches = 0 end -- Index within the heap array of least frequent node in the Huffman tree local SMALLEST = 1 -- Remove the smallest element from the heap and recreate the heap with one less element. Updates heap and heap_len. function pqremove(s, tree) local top = s.heap[SMALLEST] s.heap[SMALLEST] = s.heap[s.heap_len] s.heap_len = s.heap_len - 1 pqdownheap(s, tree, SMALLEST) return top end -- Compares to subtrees, using the tree depth as tie breaker when the subtrees have equal frequency. This minimizes the worst case length. function smaller(tree, n, m, depth) return tree[n].fc < tree[m].fc or (tree[n].fc == tree[m].fc and depth[n] <= depth[m]) end -- Restore the heap property by moving down the tree starting at node k, exchanging a node with the smallest of its two sons if necessary, stopping when the heap property is re-established (each father smaller than its two sons). function pqdownheap(s, tree, k) local v = s.heap[k] local j = lshift(k, 1) -- left son of k while (j <= s.heap_len) do -- Set j to the smallest of the two sons: if (j < s.heap_len and smaller(tree, s.heap[j+1], s.heap[j], s.depth)) then j = j + 1 end -- Exit if v is smaller than both sons if (smaller(tree, v, s.heap[j], s.depth)) then break end -- Exchange v with the smallest son s.heap[k] = s.heap[j] k = j -- And continue down the tree, setting j to the left son of k j = lshift(j, 1) end s.heap[k] = v end -- Compute the optimal bit lengths for a tree and update the total bit length for the current block. -- IN assertion: the fields freq and dad are set, heap[heap_max] and above are the tree nodes sorted by increasing frequency. -- OUT assertions: the field len is set to the optimal bit length, the array bl_count contains the frequencies for each bit length. The length opt_len is updated; static_len is also updated if stree is not null. function gen_bitlen(s, desc) local tree = desc.dyn_tree local max_code = desc.max_code local stree = desc.stat_desc.static_tree local extra = desc.stat_desc.extra_bits local base = desc.stat_desc.extra_base local max_length = desc.stat_desc.max_length local h -- heap index local n, m -- iterate over the tree elements local bits -- bit length local xbits -- extra bits local f -- frequency local overflow = 0 -- number of elements with bit length too large for bits = 0, MAX_BITS do s.bl_count[bits] = 0 end -- In a first pass, compute the optimal bit lengths (which may overflow in the case of the bit length tree). tree[s.heap[s.heap_max]].dl = 0 -- root of the heap h = s.heap_max+1 while (h < HEAP_SIZE) do n = s.heap[h] bits = tree[tree[n].dl].dl + 1 if (bits > max_length) then bits = max_length overflow = overflow + 1 end -- We overwrite tree[n].Dad which is no longer needed tree[n].dl = bits if (n > max_code) then -- not a leaf node -- continue else s.bl_count[bits] = s.bl_count[bits] + 1 xbits = 0 if (n >= base) then xbits = extra[n-base] end f = tree[n].fc s.opt_len = s.opt_len + f * (bits + xbits) if (stree) then s.static_len = s.static_len + f * (stree[n].dl + xbits) end end h = h + 1 end if (overflow == 0) then return end --Trace((stderr,"\nbit length overflow\n")); -- This happens for example on obj2 and pic of the Calgary corpus -- Find the first bit length which could increase: while (overflow > 0) do bits = max_length-1 while (s.bl_count[bits] == 0) do bits = bits - 1 end s.bl_count[bits] = s.bl_count[bits] - 1 -- move one leaf down the tree s.bl_count[bits+1] = s.bl_count[bits+1] + 2 -- move one overflow item as its brother s.bl_count[max_length] = s.bl_count[max_length] - 1 -- The brother of the overflow item also moves one step up, but this does not affect bl_count[max_length] overflow = overflow - 2 end -- Now recompute all bit lengths, scanning in increasing frequency. h is still equal to HEAP_SIZE. (It is simpler to reconstruct all lengths instead of fixing only the wrong ones. This idea is taken from 'ar' written by Haruhiko Okumura.) for bits = max_length, 1, -1 do n = s.bl_count[bits] while (n ~= 0) do h = h - 1 m = s.heap[h] if (m > max_code) then -- continue else if (tree[m].dl ~= bits) then --Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits)); s.opt_len = s.opt_len + (bits - tree[m].dl) * tree[m].fc tree[m].dl = bits end n = n - 1 end end end end -- Generate the codes for a given tree and bit counts (which need not be optimal). -- IN assertion: the array bl_count contains the bit length statistics for the given tree and the field len is set for all tree elements. -- OUT assertion: the field code is set for all tree elements of non zero code length. function gen_codes (tree, max_code, bl_count) local next_code = {} local code = 0 -- The distribution counts are first used to generate the code values without bit reversal. for bits = 1, MAX_BITS do code = lshift(code + bl_count[bits-1], 1) next_code[bits] = code end -- Check that the bit counts in bl_count are consistent. The last code must be all ones. assert(code + bl_count[MAX_BITS]-1 == lshift(1, MAX_BITS)-1, "inconsistent bit counts") --Tracev((stderr,"\ngen_codes: max_code %d ", max_code)); for n = 0, max_code do local len = tree[n].dl if (len == 0) then -- continue else -- Now reverse the bits tree[n].fc = bi_reverse(next_code[len], len) next_code[len] = next_code[len] + 1 --Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ", -- n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1)); end end end -- Construct one Huffman tree and assigns the code bit strings and lengths. Update the total bit length for the current block. -- IN assertion: the field freq is set for all tree elements. -- OUT assertions: the fields len and code are set to the optimal bit length and corresponding code. The length opt_len is updated; static_len is also updated if stree is not null. The field max_code is set. function build_tree(s, desc) local tree = desc.dyn_tree local stree = desc.stat_desc.static_tree local elems = desc.stat_desc.elems local n, m -- iterate over heap elements local max_code = -1 -- largest code with non zero frequency local node -- new node being created -- Construct the initial heap, with least frequent element in heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used. s.heap_len = 0 s.heap_max = HEAP_SIZE for n = 0, elems-1 do if (tree[n].fc ~= 0) then s.heap_len = s.heap_len + 1 max_code = n s.heap[s.heap_len] = n s.depth[n] = 0 else tree[n].dl = 0 end end -- The pkzip format requires that at least one distance code exists, and that at least one bit should be sent even if there is only one possible code. So to avoid special checks later on we force at least two codes of non zero frequency. while (s.heap_len < 2) do s.heap_len = s.heap_len + 1 if (max_code < 2) then max_code = max_code + 1 s.heap[s.heap_len] = max_code else s.heap[s.heap_len] = 0 end node = s.heap[s.heap_len] tree[node].fc = 1 s.depth[node] = 0 s.opt_len = s.opt_len - 1 if (stree) then s.static_len = s.static_len - stree[node].dl end -- node is 0 or 1 so it does not have extra bits end desc.max_code = max_code -- The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, establish sub-heaps of increasing lengths: for n = rshift(s.heap_len, 1), 1, -1 do pqdownheap(s, tree, n) end -- Construct the Huffman tree by repeatedly combining the least two frequent nodes. node = elems -- next internal node of the tree while (s.heap_len >= 2) do n = pqremove(s, tree) -- n = node of least frequency m = s.heap[SMALLEST] -- m = node of next least frequency -- keep the nodes sorted by frequency s.heap_max = s.heap_max - 1 s.heap[s.heap_max] = n s.heap_max = s.heap_max - 1 s.heap[s.heap_max] = m -- Create a new node father of n and m tree[node].fc = tree[n].fc + tree[m].fc if (s.depth[n] >= s.depth[m]) then s.depth[node] = s.depth[n] else s.depth[node] = s.depth[m] + 1 end tree[n].dl = node tree[m].dl = node --#ifdef DUMP_BL_TREE -- if (tree == s->bl_tree) { -- fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)", -- node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq); -- } --#endif -- and insert the new node in the heap s.heap[SMALLEST] = node node = node + 1 pqdownheap(s, tree, SMALLEST) end s.heap_max = s.heap_max - 1 s.heap[s.heap_max] = s.heap[SMALLEST] -- At this point, the fields freq and dad are set. We can now generate the bit lengths. gen_bitlen(s, desc) -- The field len is now set, we can generate the bit codes gen_codes(tree, max_code, s.bl_count) end -- Scan a literal or distance tree to determine the frequencies of the codes in the bit length tree. function scan_tree (s, tree, max_code) local prevlen = -1 -- last emitted length local curlen -- length of current code local nextlen = tree[0].dl -- length of next code local count = 0 -- repeat count of the current code local max_count = 7 -- max repeat count local min_count = 4 -- min repeat count if (nextlen == 0) then max_count = 138; min_count = 3 end tree[max_code+1].dl = 0xffff -- guard for n = 0, max_code do curlen = nextlen; nextlen = tree[n+1].dl count = count + 1 if (count < max_count and curlen == nextlen) then -- continue else if (count < min_count) then s.bl_tree[curlen].fc = s.bl_tree[curlen].fc + count elseif (curlen ~= 0) then if (curlen ~= prevlen) then s.bl_tree[curlen].fc = s.bl_tree[curlen].fc + 1 end s.bl_tree[REP_3_6].fc = s.bl_tree[REP_3_6].fc + 1 elseif (count <= 10) then s.bl_tree[REPZ_3_10].fc = s.bl_tree[REPZ_3_10].fc + 1 else s.bl_tree[REPZ_11_138].fc = s.bl_tree[REPZ_11_138].fc + 1 end count = 0; prevlen = curlen if (nextlen == 0) then max_count = 138; min_count = 3 elseif (curlen == nextlen) then max_count = 6; min_count = 3 else max_count = 7; min_count = 4 end end end end -- Send a literal or distance tree in compressed form, using the codes in bl_tree. function send_tree (s, tree, max_code) local prevlen = -1 -- last emitted length local curlen -- length of current code local nextlen = tree[0].dl -- length of next code local count = 0 -- repeat count of the current code local max_count = 7 -- max repeat count local min_count = 4 -- min repeat count -- tree[max_code+1].Len = -1 -- guard already set if (nextlen == 0) then max_count = 138; min_count = 3 end for n = 0, max_code do curlen = nextlen; nextlen = tree[n+1].dl count = count + 1 if (count < max_count and curlen == nextlen) then -- continue else if (count < min_count) then while count ~= 0 do send_code(s, curlen, s.bl_tree) count = count - 1 end elseif (curlen ~= 0) then if (curlen ~= prevlen) then send_code(s, curlen, s.bl_tree) count = count - 1 end assert(count >= 3 and count <= 6, " 3_6?") send_code(s, REP_3_6, s.bl_tree); send_bits(s, count-3, 2) elseif (count <= 10) then send_code(s, REPZ_3_10, s.bl_tree); send_bits(s, count-3, 3) else send_code(s, REPZ_11_138, s.bl_tree); send_bits(s, count-11, 7) end count = 0; prevlen = curlen if (nextlen == 0) then max_count = 138; min_count = 3 elseif (curlen == nextlen) then max_count = 6; min_count = 3 else max_count = 7; min_count = 4 end end end end -- Construct the Huffman tree for the bit lengths and return the index in bl_order of the last bit length code to send. function build_bl_tree(s) local max_blindex -- index of last bit length code of non zero freq -- Determine the bit length frequencies for literal and distance trees scan_tree(s, s.dyn_ltree, s.l_desc.max_code) scan_tree(s, s.dyn_dtree, s.d_desc.max_code) -- Build the bit length tree: build_tree(s, s.bl_desc) -- opt_len now includes the length of the tree representations, except the lengths of the bit lengths codes and the 5+5+4 bits for the counts. -- Determine the number of bit length codes to send. The pkzip format requires that at least 4 bit length codes be sent. (appnote.txt says 3 but the actual value used is 4.) max_blindex = BL_CODES-1 while (max_blindex >= 3) do if (s.bl_tree[bl_order[max_blindex]].dl ~= 0) then break end max_blindex = max_blindex - 1 end -- Update opt_len to include the bit length tree and counts s.opt_len = s.opt_len + 3*(max_blindex+1) + 5+5+4 --Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", -- s->opt_len, s->static_len)); return max_blindex end -- Send the header for a block using dynamic Huffman trees: the counts, the lengths of the bit length codes, the literal tree and the distance tree. -- IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4. function send_all_trees(s, lcodes, dcodes, blcodes) assert(lcodes >= 257 and dcodes >= 1 and blcodes >= 4, "not enough codes") assert(lcodes <= L_CODES and dcodes <= D_CODES and blcodes <= BL_CODES, "too many codes") --Tracev((stderr, "\nbl counts: ")); send_bits(s, lcodes-257, 5) -- not +255 as stated in appnote.txt send_bits(s, dcodes-1, 5) send_bits(s, blcodes-4, 4) -- not -3 as stated in appnote.txt for rank = 0, blcodes - 1 do --Tracev((stderr, "\nbl code %2d ", bl_order[rank])); send_bits(s, s.bl_tree[bl_order[rank]].dl, 3) end --Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent)); send_tree(s, s.dyn_ltree, lcodes-1) -- literal tree --Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent)); send_tree(s, s.dyn_dtree, dcodes-1) -- distance tree --Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent)); end -- Send a stored block function _tr_stored_block(s, buf, stored_len, last) send_bits(s, lshift(STORED_BLOCK, 1)+last, 3) -- send block type --s.compressed_len = band(s.compressed_len + 3 + 7, 0xfffffff8) --s.compressed_len = s.compressed_len + lshift(stored_len + 4, 3) copy_block(s, buf, stored_len, 1) -- with header end -- Flush the bits in the bit buffer to pending output (leaves at most 7 bits) function _tr_flush_bits(s) bi_flush(s) end -- Send one empty static block to give enough lookahead for inflate. This takes 10 bits, of which 7 may remain in the bit buffer. function _tr_align(s) send_bits(s, lshift(STATIC_TREES, 1), 3) send_code(s, END_BLOCK, static_ltree) --s.compressed_len = s.compressed_len + 10 -- 3 for block type, 7 for EOB bi_flush(s) end -- Determine the best encoding for the current block: dynamic trees, static trees or store, and output the encoded block to the zip file. function _tr_flush_block(s, buf, stored_len, last) local opt_lenb, static_lenb -- opt_len and static_len in bytes local max_blindex = 0 -- index of last bit length code of non zero freq -- Build the Huffman trees unless a stored block is forced if (s.level > 0) then -- Check if the file is binary or text if (s.strm.data_type == ZLIB.Z_UNKNOWN) then s.strm.data_type = detect_data_type(s) end -- Construct the literal and distance trees build_tree(s, s.l_desc) --Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len, -- s->static_len)); build_tree(s, s.d_desc) --Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len, -- s->static_len)); -- At this point, opt_len and static_len are the total bit lengths of the compressed block data, excluding the tree representations. -- Build the bit length tree for the above two trees, and get the index in bl_order of the last bit length code to send. max_blindex = build_bl_tree(s) -- Determine the best encoding. Compute the block lengths in bytes. opt_lenb = rshift(s.opt_len+3+7, 3) static_lenb = rshift(s.static_len+3+7, 3) --Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ", -- opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len, -- s->last_lit)); if (static_lenb <= opt_lenb) then opt_lenb = static_lenb end else --Assert(buf != (char*)0, "lost buf"); static_lenb = stored_len + 5 -- force a stored block opt_lenb = static_lenb end if (stored_len+4 <= opt_lenb and buf ~= nil) then -- 4: two words for the lengths -- The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE. -- Otherwise we can't have processed more than WSIZE input bytes since the last block flush, because compression would have been successful. If LIT_BUFSIZE <= WSIZE, it is never too late to transform a block into a stored block. _tr_stored_block(s, buf, stored_len, last) elseif (s.strategy == ZLIB.Z_FIXED or static_lenb == opt_lenb) then send_bits(s, lshift(STATIC_TREES, 1)+last, 3) compress_block(s, static_ltree, static_dtree) --s.compressed_len = s.compressed_len + 3 + s.static_len else send_bits(s, lshift(DYN_TREES, 1)+last, 3) send_all_trees(s, s.l_desc.max_code+1, s.d_desc.max_code+1, max_blindex+1) compress_block(s, s.dyn_ltree, s.dyn_dtree) --s.compressed_len = s.compressed_len + 3 + s.opt_len end --assert(s.compressed_len == s.bits_sent, "bad compressed size") -- The above check is made mod 2^32, for files larger than 512 MB and uLong implemented on 32 bits. init_block(s) if (last > 0) then bi_windup(s) --s.compressed_len = s.compressed_len + 7 -- align on byte boundary end --Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3, -- s->compressed_len-7*last)); end -- Save the match info and tally the frequency counts. Return true if the current block must be flushed. function _tr_tally (s, dist, lc) s.d_buf[s.last_lit] = dist s.l_buf[s.last_lit] = lc s.last_lit = s.last_lit + 1 if (dist == 0) then -- lc is the unmatched char s.dyn_ltree[lc].fc = s.dyn_ltree[lc].fc + 1 else s.matches = s.matches + 1 -- Here, lc is the match length - MIN_MATCH dist = dist - 1 -- dist = match distance - 1 assert(dist < MAX_DIST(s) and lc <= MAX_MATCH-MIN_MATCH and d_code(dist) < D_CODES, "_tr_tally: bad match") s.dyn_ltree[_length_code[lc]+LITERALS+1].fc = s.dyn_ltree[_length_code[lc]+LITERALS+1].fc + 1 s.dyn_dtree[d_code(dist)].fc = s.dyn_dtree[d_code(dist)].fc + 1 end return (s.last_lit == s.lit_bufsize-1) -- We avoid equality with lit_bufsize because of wraparound at 64K on 16 bit machines and because stored blocks are restricted to 64K-1 bytes. end function _tr_tally_lit(s, c) return _tr_tally(s, 0, c) end function _tr_tally_dist(s, distance, length) return _tr_tally(s, distance, length) end -- Send the block data compressed using the given Huffman trees function compress_block(s, ltree, dtree) local dist -- distance of matched string local lc -- match length or unmatched char (if dist == 0) local lx = 0 -- running index in l_buf local code -- the code to send local extra -- number of extra bits to send while (lx < s.last_lit) do dist = s.d_buf[lx] lc = s.l_buf[lx] lx = lx + 1 if (dist == 0) then send_code(s, lc, ltree) -- send a literal byte --Tracecv(isgraph(lc), (stderr," '%c' ", lc)); else -- Here, lc is the match length - MIN_MATCH code = _length_code[lc] send_code(s, code+LITERALS+1, ltree) -- send the length code extra = extra_lbits[code] if (extra ~= 0) then lc = lc - base_length[code] send_bits(s, lc, extra) -- send the extra length bits end dist = dist - 1 -- dist is now the match distance - 1 code = d_code(dist) assert(code < D_CODES, "bad d_code") send_code(s, code, dtree) -- send the distance code extra = extra_dbits[code] if (extra ~= 0) then dist = dist - base_dist[code] send_bits(s, dist, extra) -- send the extra distance bits end end -- literal or match pair ? -- Check that the overlay between pending_buf and d_buf+l_buf is ok: assert(s.pending_buf:len() < s.lit_bufsize + 2*lx, "pendingBuf overflow") end send_code(s, END_BLOCK, ltree) end -- Check if the data type is TEXT or BINARY, using the following algorithm: -- - TEXT if the two conditions below are satisfied: -- a) There are no non-portable control characters belonging to the "black list" (0..6, 14..25, 28..31). -- b) There is at least one printable character belonging to the "white list" (9 {TAB}, 10 {LF}, 13 {CR}, 32..255). -- - BINARY otherwise. -- - The following partially-portable control characters form a "gray list" that is ignored in this detection algorithm: -- (7 {BEL}, 8 {BS}, 11 {VT}, 12 {FF}, 26 {SUB}, 27 {ESC}). -- IN assertion: the fields Freq of dyn_ltree are set. function detect_data_type(s) -- black_mask is the bit mask of black-listed bytes -- set bits 0..6, 14..25, and 28..31 -- 0xf3ffc07f = binary 11110011111111111100000001111111 local black_mask = 0xf3ffc07f -- Check for non-textual ("black-listed") bytes. for n = 0, 31 do black_mask = rshift(black_mask, 1) if (band(black_mask, 1) and (s.dyn_ltree[n].fc ~= 0)) then return ZLIB.Z_BINARY end end -- Check for textual ("white-listed") bytes. if (s.dyn_ltree[9].fc ~= 0 or s.dyn_ltree[10].fc ~= 0 or s.dyn_ltree[13].fc ~= 0) then return ZLIB.Z_TEXT end for n = 32, LITERALS-1 do if (s.dyn_ltree[n].fc ~= 0) then return ZLIB.Z_TEXT end end -- There are no "black-listed" or "white-listed" bytes: -- this stream either is empty or has tolerated ("gray-listed") bytes only. return ZLIB.Z_BINARY end -- Reverse the first len bits of a code, using straightforward code (a faster method would use a table) -- IN assertion: 1 <= len <= 15 function bi_reverse(code, len) local res = 0 while (len > 0) do res = bor(res, band(code, 1)) code = rshift(code, 1) res = lshift(res, 1) len = len - 1 end return rshift(res, 1) end -- Flush the bit buffer, keeping at most 7 bits in it. function bi_flush(s) if (s.bi_valid == 16) then put_short(s, s.bi_buf) s.bi_buf = 0 s.bi_valid = 0 elseif (s.bi_valid >= 8) then put_byte(s, band(s.bi_buf, 0xff)) s.bi_buf = rshift(s.bi_buf, 8) s.bi_valid = s.bi_valid - 8 end end -- Flush the bit buffer and align the output on a byte boundary function bi_windup(s) if (s.bi_valid > 8) then put_short(s, s.bi_buf) elseif (s.bi_valid > 0) then put_byte(s, s.bi_buf) end s.bi_buf = 0 s.bi_valid = 0 end -- Copy a stored block, storing first the length and its one's complement if requested. function copy_block(s, buf, len, header) bi_windup(s) -- align on byte boundary if (header) then put_short(s, len) put_short(s, bnot(len)) end local window = s.window while (len > 0) do len = len - 1 put_byte(s, window[buf]) buf = buf + 1 end end -- =========================================================================== -- deflate.c -- compress data using the deflation algorithm -- enum block_state local need_more = 0 -- block not completed, need more input or more output local block_done = 1 -- block flush performed local finish_started = 2 -- finish started, need only more output at next deflate local finish_done = 3 -- finish done, accept no more input or output local TOO_FAR = 4096 -- Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 -- For deflate_fast() (levels <= 3) good is ignored and lazy has a different meaning. local configuration_table = { {good_length=4, max_lazy=4, nice_length=8, max_chain=4, func=deflate_fast}, -- max speed, no lazy matches {good_length=4, max_lazy=5, nice_length=16, max_chain=8, func=deflate_fast}, {good_length=4, max_lazy=6, nice_length=32, max_chain=32, func=deflate_fast}, {good_length=4, max_lazy=4, nice_length=16, max_chain=16, func=deflate_slow}, -- lazy matches {good_length=8, max_lazy=16, nice_length=32, max_chain=32, func=deflate_slow}, {good_length=8, max_lazy=16, nice_length=128, max_chain=128, func=deflate_slow}, {good_length=8, max_lazy=32, nice_length=128, max_chain=256, func=deflate_slow}, {good_length=32, max_lazy=128, nice_length=258, max_chain=1024, func=deflate_slow}, {good_length=32, max_lazy=258, nice_length=258, max_chain=4096, func=deflate_slow}, } configuration_table[0] = {good_length=0, max_lazy=0, nice_length=0, max_chain=0, func=deflate_stored} -- store only -- rank Z_BLOCK between Z_NO_FLUSH and Z_PARTIAL_FLUSH function RANK(f) if (f > 4) then return lshift(f, 1) - 9 end return lshift(f, 1) end -- Update a hash value with the given input byte -- IN assertion: all calls to to UPDATE_HASH are made with consecutive input characters, so that a running hash key can be computed from the previous key instead of complete recalculation each time. function UPDATE_HASH(s,c) s.ins_h = band(bxor(lshift(s.ins_h, s.hash_shift), c), s.hash_mask) end -- Insert string str in the dictionary and set match_head to the previous head of the hash chain (the most recent string with same hash key). Return the previous length of the hash chain. -- IN assertion: all calls to to INSERT_STRING are made with consecutive input characters and the first MIN_MATCH bytes of str are valid (except for the last MIN_MATCH-1 bytes of the input file). function INSERT_STRING(s) local str = s.strstart UPDATE_HASH(s, s.window[str + (MIN_MATCH-1)]) local match_head = s.head[s.ins_h] s.prev[band(str, s.w_mask)] = s.head[s.ins_h] s.head[s.ins_h] = str return match_head end -- Initialize the hash table (avoiding 64K overflow for 16 bit systems). -- prev[] will be initialized on the fly. function CLEAR_HASH(s) for i = 0, s.hash_size-1 do s.head[i] = 0 end end ZLIB.deflateInit = function(opts) local level = getarg(opts, 'level', ZLIB.Z_DEFAULT_COMPRESSION) local method = getarg(opts, 'method', ZLIB.Z_DEFLATED) local windowBits = getarg(opts, 'windowBits', ZLIB.MAX_WBITS) local memLevel = getarg(opts, 'memLevel', DEF_MEM_LEVEL) local strategy = getarg(opts, 'strategy', ZLIB.Z_DEFAULT_STRATEGY) return deflateInit2(level, method, windowBits, memLevel, strategy) end function deflateInit2(level, method, windowBits, memLevel, strategy) local s -- deflate_state local wrap = 1 local strm = ZLIB.z_stream() if (level == ZLIB.Z_DEFAULT_COMPRESSION) then level = 6 end if (windowBits < 0) then -- suppress zlib wrapper wrap = 0 windowBits = -windowBits elseif (windowBits > 15) then wrap = 2 -- write gzip wrapper instead windowBits = windowBits - 16 end if (wrap == 1 and ZLIB.adler32) then strm.checksum_function = ZLIB.adler32 elseif (wrap == 2 and ZLIB.crc32) then strm.checksum_function = ZLIB.crc32 else strm.checksum_function = checksum_none end if (memLevel < 1 or memLevel > ZLIB.MAX_MEM_LEVEL or method ~= ZLIB.Z_DEFLATED or windowBits < 8 or windowBits > 15 or level < 0 or level > 9 or strategy < 0 or strategy > ZLIB.Z_FIXED) then return nil -- ZLIB.Z_STREAM_ERROR end if (windowBits == 8) then windowBits = 9 end -- until 256-byte window bug fixed s = deflate_state() strm.state = s s.strm = strm s.wrap = wrap s.gzhead = nil s.w_bits = windowBits s.w_size = lshift(1, s.w_bits) s.w_mask = s.w_size - 1 s.hash_bits = memLevel + 7 s.hash_size = lshift(1, s.hash_bits) s.hash_mask = s.hash_size - 1 s.hash_shift = band((s.hash_bits+MIN_MATCH-1)/MIN_MATCH, 0xffffffff) s.window = new_array(s.w_size) s.prev = new_array(s.w_size) s.head = new_array(s.hash_size) s.high_water = 0 -- nothing written to s->window yet s.lit_bufsize = lshift(1, memLevel + 6) -- 16K elements by default s.pending_buf = '' s.pending_buf_size = s.lit_bufsize * 4 s.d_buf = new_array(s.lit_bufsize) s.l_buf = new_array(s.lit_bufsize) s.level = level s.strategy = strategy s.method = method ZLIB.deflateReset(strm) return strm end ZLIB.deflateResetKeep = function(strm) local s if (not strm or not strm.state) then return ZLIB.Z_STREAM_ERROR end strm.total_in = 0 strm.total_out = 0 strm.msg = nil -- use zfree if we ever allocate msg dynamically strm.data_type = ZLIB.Z_UNKNOWN s = strm.state s.pending_buf = '' if (s.wrap < 0) then s.wrap = -s.wrap -- was made negative by deflate(..., Z_FINISH) end if (s.wrap ~= 0) then s.status = INIT_STATE else s.status = BUSY_STATE end strm.adler = strm.checksum_function(0, nil, 0, 0) s.last_flush = ZLIB.Z_NO_FLUSH _tr_init(s) return ZLIB.Z_OK end ZLIB.deflateReset = function(strm) local ret ret = ZLIB.deflateResetKeep(strm) if (ret == ZLIB.Z_OK) then lm_init(strm.state) end return ret end -- For the default windowBits of 15 and memLevel of 8, this function returns a close to exact, as well as small, upper bound on the compressed size. They are coded as constants here for a reason--if the #define's are changed, then this function needs to be changed as well. The return value for 15 and 8 only works for those exact settings. -- For any setting other than those defaults for windowBits and memLevel, the value returned is a conservative worst case for the maximum expansion resulting from using fixed blocks instead of stored blocks, which deflate can emit on compressed data for some combinations of the parameters. -- This function could be more sophisticated to provide closer upper bounds for every combination of windowBits and memLevel. But even the conservative upper bound of about 14% expansion does not seem onerous for output buffer allocation. ZLIB.deflateBound = function(strm, sourceLen) local s local complen, wraplen local str -- conservative upper bound for compressed data complen = sourceLen + rshift(sourceLen + 7, 3) + rshift(sourceLen + 63, 6) + 5 -- if can't get parameters, return conservative bound plus zlib wrapper if (not strm or not strm.state) then return complen + 6 end -- compute wrapper length s = strm.state if (s.wrap == 0) then -- raw deflate wraplen = 0 elseif (s.wrap == 1) then -- zlib wrapper if (s.strstart ~= 0) then wraplen = 6 + 4 else wraplen = 6 end elseif (s.wrap == 2) then -- gzip wrapper wraplen = 18 if (s.gzhead ~= nil) then -- user-supplied gzip header if (s.gzhead.extra ~= nil) then wraplen = wraplen + 2 + s.gzhead.extra:len() end str = s.gzhead.name if (str ~= nil) then local len = 0 repeat len = len + 1 wraplen = wraplen + 1 until (len >= str:len() or str:byte(len,len) == 0) end str = s.gzhead.comment if (str ~= nil) then local len = 0 repeat len = len + 1 wraplen = wraplen + 1 until (len >= str:len() or str:byte(len,len) == 0) end if (s.gzhead.hcrc) then wraplen = wraplen + 2 end end else -- for compiler happiness wraplen = 6 end -- if not default parameters, return conservative bound if (s.w_bits ~= 15 or s.hash_bits ~= 8 + 7) then return complen + wraplen end -- default settings: return tight bound for that case return sourceLen + rshift(sourceLen, 12) + rshift(sourceLen, 14) + rshift(sourceLen, 25) + 13 - 6 + wraplen end -- Put a short in the pending buffer. The 16-bit value is put in MSB order. -- IN assertion: the stream state is correct and there is enough room in pending_buf. function putShortMSB (s, b) s.pending_buf = s.pending_buf .. string.char(band(rshift(b, 8), 0xff)) s.pending_buf = s.pending_buf .. string.char(band(b, 0xff)) end -- Flush as much pending output as possible. All deflate() output goes through this function so some applications may wish to modify it to avoid allocating a large strm->next_out buffer and copying into it. -- (See also read_buf()). function flush_pending(strm) local len local s = strm.state _tr_flush_bits(s) len = s.pending_buf:len() if (len > strm.avail_out) then len = strm.avail_out end if (len == 0) then return end strm.output_data = strm.output_data .. s.pending_buf:sub(1, len) s.pending_buf = s.pending_buf:sub(len + 1) strm.total_out = strm.total_out + len strm.avail_out = strm.avail_out - len end local z_errmsg = { 'need dictionary', -- Z_NEED_DICT 2 'stream end', -- Z_STREAM_END 1 '', -- Z_OK 0 'file error', -- Z_ERRNO (-1) 'stream error', -- Z_STREAM_ERROR (-2) 'data error', -- Z_DATA_ERROR (-3) 'insufficient memory', -- Z_MEM_ERROR (-4) 'buffer error', -- Z_BUF_ERROR (-5) 'incompatible version', -- Z_VERSION_ERROR (-6) '' } function ERR_MSG(err) return z_errmsg[3 - err] end function ERR_RETURN(strm, err) strm.msg = ERR_MSG(err) return err end ZLIB.deflate = function(strm, flush) local old_flush -- value of flush param for previous deflate call local s if (not strm or not strm.state or flush > ZLIB.Z_BLOCK or flush < 0) then return ZLIB.Z_STREAM_ERROR end s = strm.state if (strm.output_data == nil or (strm.input_data == nil and strm.avail_in ~= 0) or (s.status == FINISH_STATE and flush ~= ZLIB.Z_FINISH)) then return ERR_RETURN(strm, ZLIB.Z_STREAM_ERROR) end if (strm.avail_out == 0) then return ERR_RETURN(strm, ZLIB.Z_BUF_ERROR) end s.strm = strm -- just in case old_flush = s.last_flush s.last_flush = flush -- Write the header if (s.status == INIT_STATE) then if (s.wrap == 2) then strm.adler = strm.checksum_function(0, nil, 0, 0) put_byte(s, 31) put_byte(s, 139) put_byte(s, 8) if (s.gzhead == nil) then put_byte(s, 0) put_byte(s, 0) put_byte(s, 0) put_byte(s, 0) put_byte(s, 0) if (s.level == 9) then put_byte(s, 2) elseif (s.strategy >= ZLIB.Z_HUFFMAN_ONLY or s.level < 2) then put_byte(s, 4) else put_byte(s, 0) end put_byte(s, ZLIB.OS_CODE) s.status = BUSY_STATE else local flags = 0 if (s.gzhead.text) then flags = flags + 1 end if (s.gzhead.hcrc) then flags = flags + 2 end if (s.gzhead.extra) then flags = flags + 4 end if (s.gzhead.name) then flags = flags + 8 end if (s.gzhead.comment) then flags = flags + 16 end put_byte(s, flags) put_byte(s, band(s.gzhead.time, 0xff)) put_byte(s, band(rshift(s.gzhead.time, 8), 0xff)) put_byte(s, band(rshift(s.gzhead.time, 16), 0xff)) put_byte(s, band(rshift(s.gzhead.time, 24), 0xff)) if (s.level == 9) then put_byte(s, 2) elseif (s.strategy >= ZLIB.Z_HUFFMAN_ONLY or s.level < 2) then put_byte(s, 4) else put_byte(s, 0) end put_byte(s, band(s.gzhead.os, 0xff)) if (s.gzhead.extra ~= nil) then put_byte(s, band(s.gzhead.extra:len(), 0xff)) put_byte(s, band(rshift(s.gzhead.extra:len(), 8), 0xff)) end if (s.gzhead.hcrc) then strm.adler = strm.checksum_function(strm.adler, s.pending_buf, s.pending) end s.gzindex = 0 s.status = EXTRA_STATE end else local header = lshift(ZLIB.Z_DEFLATED + lshift(s.w_bits-8, 4), 8) local level_flags if (s.strategy >= ZLIB.Z_HUFFMAN_ONLY or s.level < 2) then level_flags = 0 elseif (s.level < 6) then level_flags = 1 elseif (s.level == 6) then level_flags = 2 else level_flags = 3 end header = bor(header, lshift(level_flags, 6)) if (s.strstart ~= 0) then header = bor(header, PRESET_DICT) end header = header + 31 - (header % 31) s.status = BUSY_STATE putShortMSB(s, header) -- Save the adler32 of the preset dictionary: if (s.strstart ~= 0) then putShortMSB(s, rshift(strm.adler, 16)) putShortMSB(s, band(strm.adler, 0xffff)) end strm.adler = strm.checksum_function(0, nil, 0, 0) end end if (s.status == EXTRA_STATE) then if (s.gzhead.extra ~= nil) then local beg = s.pending_buf:len() -- start of bytes to update crc local extra_len = s.gzhead.extra:len() while (s.gzindex < band(extra_len, 0xffff)) do if (s.pending_buf:len() == s.pending_buf_size) then if (s.gzhead.hcrc and s.pending_buf:len() > beg) then strm.adler = strm.checksum_function(strm.adler, s.pending_buf, beg, s.pending_buf:len() - beg) end flush_pending(strm) beg = s.pending_buf:len() if (s.pending_buf:len() == s.pending_buf_size) then break end end s.gzindex = s.gzindex + 1 put_byte(s, band(s.gzhead.extra:byte(s.gzindex,s.gzindex), 0xff)) end if (s.gzhead.hcrc and s.pending_buf:len() > beg) then strm.adler = strm.checksum_function(strm.adler, s.pending_buf, beg, s.pending_buf:len() - beg) end if (s.gzindex == extra_len) then s.gzindex = 0 s.status = NAME_STATE end else s.status = NAME_STATE end end if (s.status == NAME_STATE) then if (s.gzhead.name ~= nil) then local beg = s.pending_buf:len() -- start of bytes to update crc local val = 1 while (val ~= 0) do if (s.pending_buf:len() == s.pending_buf_size) then if (s.gzhead.hcrc and s.pending_buf:len() > beg) then strm.adler = strm.checksum_function(strm.adler, s.pending_buf + beg, s.pending_buf:len() - beg) end flush_pending(strm) beg = s.pending_buf:len() if (s.pending_buf:len() == s.pending_buf_size) then val = 1 break end end if (s.gzindex == s.gzhead.name:len()) then val = 0 else s.gzindex = s.gzindex + 1 val = band(s.gzhead.name:byte(s.gzindex,s.gzindex), 0xff) end put_byte(s, val) end if (s.gzhead.hcrc and s.pending_buf:len() > beg) then strm.adler = strm.checksum_function(strm.adler, s.pending_buf, beg, s.pending_buf:len() - beg) end if (val == 0) then s.gzindex = 0 s.status = COMMENT_STATE end else s.status = COMMENT_STATE end end if (s.status == COMMENT_STATE) then if (s.gzhead.comment ~= nil) then local beg = s.pending_buf:len() -- start of bytes to update crc local val = 1 while (val ~= 0) do if (s.pending_buf:len() == s.pending_buf_size) then if (s.gzhead.hcrc and s.pending_buf:len() > beg) then strm.adler = strm.checksum_function(strm.adler, s.pending_buf, beg, s.pending_buf:len() - beg) end flush_pending(strm) beg = s.pending_buf:len() if (s.pending_buf:len() == s.pending_buf_size) then val = 1 break end end if (s.gzhead.comment:len() == s.gzindex) then val = 0 else s.gzindex = s.gzindex + 1 val = band(s.gzhead.comment:byte(s.gzindex,s.gzindex), 0xff) end put_byte(s, val) end if (s.gzhead.hcrc and s.pending_buf:len() > beg) then strm.adler = strm.checksum_function(strm.adler, s.pending_buf, beg, s.pending_buf:len() - beg) end if (val == 0) then s.status = HCRC_STATE end else s.status = HCRC_STATE end end if (s.status == HCRC_STATE) then if (s.gzhead.hcrc) then if (s.pending_buf:len() + 2 > s.pending_buf_size) then flush_pending(strm) end if (s.pending_buf:len() + 2 <= s.pending_buf_size) then put_byte(s, band(strm.adler, 0xff)) put_byte(s, band(rshift(strm.adler, 8), 0xff)) strm.adler = strm.checksum_function(0, nil, 0, 0) s.status = BUSY_STATE end else s.status = BUSY_STATE end end -- Flush as much pending output as possible if (s.pending_buf:len() ~= 0) then flush_pending(strm) if (strm.avail_out == 0) then -- Since avail_out is 0, deflate will be called again with more output space, but possibly with both pending and avail_in equal to zero. There won't be anything to do, but this is not an error situation so make sure we return OK instead of BUF_ERROR at next call of deflate: s.last_flush = -1 return ZLIB.Z_OK end -- Make sure there is something to do and avoid duplicate consecutive flushes. For repeated and useless calls with Z_FINISH, we keep returning Z_STREAM_END instead of Z_BUF_ERROR. elseif (strm.avail_in == 0 and RANK(flush) <= RANK(old_flush) and flush ~= ZLIB.Z_FINISH) then return ERR_RETURN(strm, ZLIB.Z_BUF_ERROR) end -- User must not provide more input after the first FINISH: if (s.status == FINISH_STATE and strm.avail_in ~= 0) then return ERR_RETURN(strm, ZLIB.Z_BUF_ERROR) end -- Start a new block or continue the current one. if (strm.avail_in ~= 0 or s.lookahead ~= 0 or (flush ~= ZLIB.Z_NO_FLUSH and s.status ~= FINISH_STATE)) then local bstate if (s.strategy == ZLIB.Z_HUFFMAN_ONLY) then bstate = deflate_huff(s, flush) elseif (s.strategy == ZLIB.Z_RLE) then bstate = deflate_rle(s, flush) else if (s.level >= 4) then bstate = deflate_slow(s, flush) elseif (s.level >= 1) then bstate = deflate_fast(s, flush) else bstate = deflate_stored(s, flush) end --bstate = (configuration_table[s.level].func)(s, flush) end if (bstate == finish_started or bstate == finish_done) then s.status = FINISH_STATE end if (bstate == need_more or bstate == finish_started) then if (strm.avail_out == 0) then s.last_flush = -1 -- avoid BUF_ERROR next call, see above end return ZLIB.Z_OK -- If flush != Z_NO_FLUSH && avail_out == 0, the next call of deflate should use the same flush parameter to make sure that the flush is complete. So we don't have to output an empty block here, this will be done at next call. This also ensures that for a very small output buffer, we emit at most one empty block. end if (bstate == block_done) then if (flush == ZLIB.Z_PARTIAL_FLUSH) then _tr_align(s) elseif (flush ~= ZLIB.Z_BLOCK) then -- FULL_FLUSH or SYNC_FLUSH _tr_stored_block(s, nil, 0, 0) -- For a full flush, this empty block will be recognized as a special marker by inflate_sync(). if (flush == ZLIB.Z_FULL_FLUSH) then CLEAR_HASH(s) -- forget history if (s.lookahead == 0) then s.strstart = 0 s.block_start = 0 s.insert = 0 end end end flush_pending(strm) if (strm.avail_out == 0) then s.last_flush = -1 -- avoid BUF_ERROR at next call, see above return ZLIB.Z_OK end end end assert(s.strm.avail_out > 0, "bug2") if (flush ~= ZLIB.Z_FINISH) then return ZLIB.Z_OK end if (s.wrap <= 0) then return ZLIB.Z_STREAM_END end -- Write the trailer if (s.wrap == 2) then put_byte(s, band(strm.adler, 0xff)) put_byte(s, band(rshift(strm.adler, 8), 0xff)) put_byte(s, band(rshift(strm.adler, 16), 0xff)) put_byte(s, band(rshift(strm.adler, 24), 0xff)) put_byte(s, band(strm.total_in, 0xff)) put_byte(s, band(rshift(strm.total_in, 8), 0xff)) put_byte(s, band(rshift(strm.total_in, 16), 0xff)) put_byte(s, band(rshift(strm.total_in, 24), 0xff)) else putShortMSB(s, rshift(strm.adler, 16)) putShortMSB(s, band(strm.adler, 0xffff)) end flush_pending(strm) -- If avail_out is zero, the application will call deflate again to flush the rest. if (s.wrap > 0) then s.wrap = -s.wrap end -- write the trailer only once! if (s.pending_buf:len() ~= 0) then return ZLIB.Z_OK else return ZLIB.Z_STREAM_END end end ZLIB.deflateEnd = function(strm) local status if (not strm or not strm.state) then return ZLIB.Z_STREAM_ERROR end status = strm.state.status if (status ~= INIT_STATE and status ~= EXTRA_STATE and status ~= NAME_STATE and status ~= COMMENT_STATE and status ~= HCRC_STATE and status ~= BUSY_STATE and status ~= FINISH_STATE) then return ZLIB.Z_STREAM_ERROR end -- Deallocate in reverse order of allocations: strm.state.pending_buf = nil strm.state.head = nil strm.state.prev = nil strm.state.window = nil strm.state = nil if (status == BUSY_STATE) then return ZLIB.Z_DATA_ERROR else return ZLIB.Z_OK end end -- Read a new buffer from the current input stream, update the adler32 and total number of bytes read. All deflate() input goes through this function so some applications may wish to modify it to avoid allocating a large strm.input_data buffer and copying from it. -- (See also flush_pending()). function read_buf(strm, buf, offset, size) local len = strm.avail_in if (len > size) then len = size end if (len == 0) then return 0 end strm.avail_in = strm.avail_in - len local src_i = strm.next_in for i = 1, len do buf[offset + i - 1] = band(strm.input_data:byte(src_i + i, src_i + i), 0xff) end if (strm.state.wrap ~= 0) then strm.adler = strm.checksum_function(strm.adler, buf, offset, len) end strm.next_in = strm.next_in + len strm.total_in = strm.total_in + len return len end -- Initialize the "longest match" routines for a new zlib stream function lm_init (s) s.window_size = 2*s.w_size CLEAR_HASH(s) -- Set the default configuration parameters: s.max_lazy_match = configuration_table[s.level].max_lazy s.good_match = configuration_table[s.level].good_length s.nice_match = configuration_table[s.level].nice_length s.max_chain_length = configuration_table[s.level].max_chain s.strstart = 0 s.block_start = 0 s.lookahead = 0 s.insert = 0 s.match_length = MIN_MATCH-1 s.prev_length = s.match_length s.match_available = false s.ins_h = 0 end -- Set match_start to the longest match starting at the given string and return its length. Matches shorter or equal to prev_length are discarded, in which case the result is equal to prev_length and match_start is garbage. -- IN assertions: cur_match is the head of the hash chain for the current string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 -- OUT assertion: the match length is not greater than s->lookahead. function longest_match(s, cur_match) local window = s.window local chain_length = s.max_chain_length -- max hash chain length -- zlib.js: scan -> window[scan], match -> window[match] local scan = s.strstart -- current string local match -- matched string local len -- length of current match local best_len = s.prev_length -- best match length so far local nice_match = s.nice_match -- stop if match long enough local limit = 0 if (s.strstart > MAX_DIST(s)) then limit = s.strstart - MAX_DIST(s) end -- Stop when cur_match becomes <= limit. To simplify the code, we prevent matches with the string of window index 0. local prev = s.prev local wmask = s.w_mask -- zlib.js: strend -> window[strend] local strend = s.strstart + MAX_MATCH local scan_end1 = window[scan+best_len-1] local scan_end = window[scan+best_len] -- The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. -- It is easy to get rid of this optimization if necessary. assert(s.hash_bits >= 8 and MAX_MATCH == 258, "Code too clever") -- Do not waste too much time if we already have a good match: if (s.prev_length >= s.good_match) then chain_length = rshift(chain_length, 2) end -- Do not look for matches beyond the end of the input. This is necessary to make deflate deterministic. if (nice_match > s.lookahead) then nice_match = s.lookahead end assert(s.strstart <= s.window_size-MIN_LOOKAHEAD, "need lookahead") repeat assert(cur_match < s.strstart, "no future") match = cur_match -- Skip to next match if the match length cannot increase or if the match length is less than 2. Note that the checks below for insufficient lookahead only occur occasionally for performance reasons. Therefore uninitialized memory will be accessed, and conditional jumps will be made that depend on those values. However the length of the match is limited to the lookahead, so the output of deflate is not affected by the uninitialized values. if (window[match+best_len] ~= scan_end or window[match+best_len-1] ~= scan_end1 or window[match] ~= window[scan] or window[match+1] ~= window[scan+1]) then match = match + 1 -- continue else match = match + 1 -- The check at best_len-1 can be removed because it will be made again later. (This heuristic is not always a win.) -- It is not necessary to compare scan[2] and match[2] since they are always equal when the other bytes match, given that the hash keys are equal and that HASH_BITS >= 8. scan = scan + 2; match = match + 1 assert(window[scan] == window[match], "match[2]?") -- We check for insufficient lookahead only every 8th comparison; the 256th check will be made at strstart+258. while (scan < strend) do scan = scan + 1; match = match + 1; if (window[scan] ~= window[match]) then break end scan = scan + 1; match = match + 1; if (window[scan] ~= window[match]) then break end scan = scan + 1; match = match + 1; if (window[scan] ~= window[match]) then break end scan = scan + 1; match = match + 1; if (window[scan] ~= window[match]) then break end scan = scan + 1; match = match + 1; if (window[scan] ~= window[match]) then break end scan = scan + 1; match = match + 1; if (window[scan] ~= window[match]) then break end scan = scan + 1; match = match + 1; if (window[scan] ~= window[match]) then break end scan = scan + 1; match = match + 1; if (window[scan] ~= window[match]) then break end end --Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); len = MAX_MATCH - (strend - scan) scan = strend - MAX_MATCH if (len > best_len) then s.match_start = cur_match best_len = len if (len >= nice_match) then break end scan_end1 = window[scan+best_len-1] scan_end = window[scan+best_len] end end cur_match = prev[band(cur_match, wmask)] chain_length = chain_length - 1 until (cur_match <= limit or chain_length == 0) if (best_len <= s.lookahead) then return best_len end return s.lookahead end -- Check that the match at match_start is indeed a match. function check_match(s, start, match, length) end -- Fill the window when the lookahead becomes insufficient. -- Updates strstart and lookahead. -- IN assertion: lookahead < MIN_LOOKAHEAD -- OUT assertions: strstart <= window_size-MIN_LOOKAHEAD -- At least one byte has been read, or avail_in == 0; reads are performed for at least two bytes (required for the zip translate_eol option -- not supported here). function fill_window(s) local n, m local p, ary -- Posf * local more -- Amount of free space at the end of the window. local wsize = s.w_size assert(s.lookahead < MIN_LOOKAHEAD, "already enough lookahead") repeat more = s.window_size - s.lookahead - s.strstart -- If the window is almost full and there is insufficient lookahead, move the upper half to the lower one to make room in the upper half. if (s.strstart >= wsize+MAX_DIST(s)) then for i = 0, wsize-1 do s.window[i] = s.window[wsize + i] end s.match_start = s.match_start - wsize s.strstart = s.strstart - wsize -- we now have strstart >= MAX_DIST s.block_start = s.block_start - wsize -- Slide the hash table (could be avoided with 32 bit values at the expense of memory usage). We slide even when level == 0 to keep the hash table consistent if we switch back to level > 0 later. (Using level 0 permanently is not an optimal usage of zlib, so we don't care about this pathological case.) n = s.hash_size -- p = &s->head[n]; ary = s.head p = n repeat p = p - 1 m = ary[p] if (m >= wsize) then ary[p] = m-wsize else ary[p] = 0 end n = n - 1 until (n == 0) n = wsize -- p = &s->prev[n]; ary = s.prev p = n repeat p = p - 1 m = ary[p] if (m >= wsize) then ary[p] = m-wsize else ary[p] = 0 end -- If n is not on any hash chain, prev[n] is garbage but its value will never be used. n = n - 1 until (n == 0) more = more + wsize end if (s.strm.avail_in == 0) then break end -- If there was no sliding: -- strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && more == window_size - lookahead - strstart => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1) => more >= window_size - 2*WSIZE + 2 -- In the BIG_MEM or MMAP case (not yet supported), -- window_size == input_size + MIN_LOOKAHEAD && strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD. -- Otherwise, window_size == 2*WSIZE so more >= 2. -- If there was sliding, more >= WSIZE. So in all cases, more >= 2. assert(more >= 2, "more < 2") n = read_buf(s.strm, s.window, s.strstart + s.lookahead, more) s.lookahead = s.lookahead + n -- Initialize the hash value now that we have some input: if (s.lookahead + s.insert >= MIN_MATCH) then local str = s.strstart - s.insert s.ins_h = s.window[str] UPDATE_HASH(s, s.window[str + 1]) while (s.insert > 0) do UPDATE_HASH(s, s.window[str + MIN_MATCH-1]) s.prev[band(str, s.w_mask)] = s.head[s.ins_h] s.head[s.ins_h] = str str = str + 1 s.insert = s.insert - 1 if (s.lookahead + s.insert < MIN_MATCH) then break end end end -- If the whole input has less than MIN_MATCH bytes, ins_h is garbage, but this is not important since only literal bytes will be emitted. until (s.lookahead >= MIN_LOOKAHEAD or s.strm.avail_in == 0) -- If the WIN_INIT bytes after the end of the current data have never been written, then zero those bytes in order to avoid memory check reports of the use of uninitialized (or uninitialised as Julian writes) bytes by the longest match routines. Update the high water mark for the next time through here. WIN_INIT is set to MAX_MATCH since the longest match routines allow scanning to strstart + MAX_MATCH, ignoring lookahead. if (s.high_water < s.window_size) then local curr = s.strstart + s.lookahead local init if (s.high_water < curr) then -- Previous high water mark below current data -- zero WIN_INIT bytes or up to end of window, whichever is less. init = s.window_size - curr if (init > WIN_INIT) then init = WIN_INIT end for i = 0, init-1 do s.window[i + curr] = 0 end s.high_water = curr + init elseif (s.high_water < curr + WIN_INIT) then -- High water mark at or above current data, but below current data plus WIN_INIT -- zero out to current data plus WIN_INIT, or up to end of window, whichever is less. init = curr + WIN_INIT - s.high_water if (init > s.window_size - s.high_water) then init = s.window_size - s.high_water end for i = 0, init-1 do s.window[s.high_water + i] = 0 end s.high_water = s.high_water + init end end assert(s.strstart <= s.window_size - MIN_LOOKAHEAD, "not enough room for search") end -- Flush the current block, with given end-of-file flag. -- IN assertion: strstart is set to the end of the current match. function FLUSH_BLOCK_ONLY(s, last) local buf = nil if (s.block_start >= 0) then buf = s.block_start end _tr_flush_block(s, buf, s.strstart - s.block_start, last) s.block_start = s.strstart flush_pending(s.strm) --Tracev((stderr,"[FLUSH]")); end -- Copy without compression as much as possible from the input stream, return the current block state. -- This function does not insert new strings in the dictionary since uncompressible data is probably not useful. This function is used only for the level=0 compression option. -- NOTE: this function should be optimized to avoid extra copying from window to pending_buf. function deflate_stored(s, flush) -- Stored blocks are limited to 0xffff bytes, pending_buf is limited to pending_buf_size, and each stored block has a 5 byte header: local max_block_size = 0xffff local max_start if (max_block_size > s.pending_buf_size - 5) then max_block_size = s.pending_buf_size - 5 end -- Copy as much as possible from input to output: while (true) do -- Fill the window as much as possible: if (s.lookahead <= 1) then assert(s.strstart < s.w_size+MAX_DIST(s) or s.block_start >= s.w_size, "slide too late") fill_window(s) if (s.lookahead == 0 and flush == ZLIB.Z_NO_FLUSH) then return need_more end if (s.lookahead == 0) then break end -- flush the current block end assert(s.block_start >= 0, "block gone") s.strstart = s.strstart + s.lookahead s.lookahead = 0 -- Emit a stored block if pending_buf will be full: max_start = s.block_start + max_block_size if (s.strstart == 0 or s.strstart >= max_start) then -- strstart == 0 is possible when wraparound on 16-bit machine s.lookahead = s.strstart - max_start s.strstart = max_start FLUSH_BLOCK_ONLY(s, 0); if (s.strm.avail_out == 0) then return need_more end end -- Flush if we may have to slide, otherwise block_start may become negative and the data will be gone: if (s.strstart - s.block_start >= MAX_DIST(s)) then FLUSH_BLOCK_ONLY(s, 0); if (s.strm.avail_out == 0) then return need_more end end end s.insert = 0 if (flush == ZLIB.Z_FINISH) then FLUSH_BLOCK_ONLY(s, 1); if (s.strm.avail_out == 0) then return finish_started end return finish_done end if (s.strstart > s.block_start) then FLUSH_BLOCK_ONLY(s, 0); if (s.strm.avail_out == 0) then return need_more end end return block_done end -- Compress as much as possible from the input stream, return the current block state. -- This function does not perform lazy evaluation of matches and inserts new strings in the dictionary only for unmatched strings or for short matches. It is used only for the fast compression options. function deflate_fast(s, flush) local hash_head -- head of the hash chain local bflush -- set if current block must be flushed while (true) do -- Make sure that we always have enough lookahead, except at the end of the input file. We need MAX_MATCH bytes for the next match, plus MIN_MATCH bytes to insert the string following the next match. if (s.lookahead < MIN_LOOKAHEAD) then fill_window(s) if (s.lookahead < MIN_LOOKAHEAD and flush == ZLIB.Z_NO_FLUSH) then return need_more end if (s.lookahead == 0) then break end -- flush the current block end -- Insert the string window[strstart .. strstart+2] in the dictionary, and set hash_head to the head of the hash chain: hash_head = 0 if (s.lookahead >= MIN_MATCH) then hash_head = INSERT_STRING(s) end -- Find the longest match, discarding those <= prev_length. -- At this point we have always match_length < MIN_MATCH if (hash_head ~= 0 and s.strstart - hash_head <= MAX_DIST(s)) then -- To simplify the code, we prevent matches with the string of window index 0 (in particular we have to avoid a match of the string with itself at the start of the input file). s.match_length = longest_match(s, hash_head) -- longest_match() sets match_start end if (s.match_length >= MIN_MATCH) then check_match(s, s.strstart, s.match_start, s.match_length) bflush = _tr_tally_dist(s, s.strstart - s.match_start, s.match_length - MIN_MATCH) s.lookahead = s.lookahead - s.match_length -- Insert new strings in the hash table only if the match length is not too large. This saves time but degrades compression. if (s.match_length <= s.max_insert_length and s.lookahead >= MIN_MATCH) then s.match_length = s.match_length - 1 -- string at strstart already in table repeat s.strstart = s.strstart + 1 hash_head = INSERT_STRING(s) -- strstart never exceeds WSIZE-MAX_MATCH, so there are always MIN_MATCH bytes ahead. s.match_length = s.match_length - 1 until (s.match_length == 0) s.strstart = s.strstart + 1 else s.strstart = s.strstart + s.match_length s.match_length = 0 s.ins_h = s.window[s.strstart] UPDATE_HASH(s, s.window[s.strstart+1]) -- If lookahead < MIN_MATCH, ins_h is garbage, but it does not matter since it will be recomputed at next deflate call. end else -- No match, output a literal byte --Tracevv((stderr,"%c", s->window[s->strstart])); bflush = _tr_tally_lit (s, s.window[s.strstart]) s.lookahead = s.lookahead - 1 s.strstart = s.strstart + 1 end if (bflush) then FLUSH_BLOCK_ONLY(s, 0); if (s.strm.avail_out == 0) then return need_more end end end if (s.strstart < MIN_MATCH-1) then s.insert = s.strstart else s.insert = MIN_MATCH-1 end if (flush == ZLIB.Z_FINISH) then FLUSH_BLOCK_ONLY(s, 1); if (s.strm.avail_out == 0) then return finish_started end return finish_done end if (s.last_lit ~= 0) then FLUSH_BLOCK_ONLY(s, 0); if (s.strm.avail_out == 0) then return need_more end end return block_done end -- Same as above, but achieves better compression. We use a lazy evaluation for matches: a match is finally adopted only if there is no better match at the next window position. function deflate_slow(s, flush) local hash_head -- head of hash chain local bflush -- set if current block must be flushed -- Process the input block. while (true) do -- Make sure that we always have enough lookahead, except at the end of the input file. We need MAX_MATCH bytes for the next match, plus MIN_MATCH bytes to insert the string following the next match. if (s.lookahead < MIN_LOOKAHEAD) then fill_window(s) if (s.lookahead < MIN_LOOKAHEAD and flush == ZLIB.Z_NO_FLUSH) then return need_more end if (s.lookahead == 0) then break end -- flush the current block end -- Insert the string window[strstart .. strstart+2] in the dictionary, and set hash_head to the head of the hash chain: hash_head = 0 if (s.lookahead >= MIN_MATCH) then hash_head = INSERT_STRING(s) end -- Find the longest match, discarding those <= prev_length. s.prev_length = s.match_length; s.prev_match = s.match_start s.match_length = MIN_MATCH-1 if (hash_head ~= 0 and s.prev_length < s.max_lazy_match and s.strstart - hash_head <= MAX_DIST(s)) then -- To simplify the code, we prevent matches with the string of window index 0 (in particular we have to avoid a match of the string with itself at the start of the input file). s.match_length = longest_match(s, hash_head) -- longest_match() sets match_start if (s.match_length <= 5 and (s.strategy == ZLIB.Z_FILTERED or (s.match_length == MIN_MATCH and s.strstart - s.match_start > TOO_FAR) ) ) then -- If prev_match is also MIN_MATCH, match_start is garbage but we will ignore the current match anyway. s.match_length = MIN_MATCH-1 end end -- If there was a match at the previous step and the current match is not better, output the previous match: if (s.prev_length >= MIN_MATCH and s.match_length <= s.prev_length) then local max_insert = s.strstart + s.lookahead - MIN_MATCH -- Do not insert strings in hash table beyond this. check_match(s, s.strstart-1, s.prev_match, s.prev_length) bflush = _tr_tally_dist(s, s.strstart-1 - s.prev_match, s.prev_length - MIN_MATCH) -- Insert in hash table all strings up to the end of the match. -- strstart-1 and strstart are already inserted. If there is not enough lookahead, the last two strings are not inserted in the hash table. s.lookahead = s.lookahead - (s.prev_length-1) s.prev_length = s.prev_length - 2 repeat s.strstart = s.strstart + 1 if (s.strstart <= max_insert) then hash_head = INSERT_STRING(s) end s.prev_length = s.prev_length - 1 until (s.prev_length == 0) s.match_available = false s.match_length = MIN_MATCH-1 s.strstart = s.strstart + 1 if (bflush) then FLUSH_BLOCK_ONLY(s, 0); if (s.strm.avail_out == 0) then return need_more end end elseif (s.match_available) then -- If there was no match at the previous position, output a single literal. If there was a match but the current match is longer, truncate the previous match to a single literal. --Tracevv((stderr,"%c", s->window[s->strstart-1])); bflush = _tr_tally_lit(s, s.window[s.strstart-1]) if (bflush) then FLUSH_BLOCK_ONLY(s, 0); if (s.strm.avail_out == 0) then return need_more end end s.strstart = s.strstart + 1 s.lookahead = s.lookahead - 1 if (s.strm.avail_out == 0) then return need_more end else -- There is no previous match to compare with, wait for the next step to decide. s.match_available = true s.strstart = s.strstart + 1 s.lookahead = s.lookahead - 1 end end --assert (flush ~= Z_NO_FLUSH, "no flush?") if (s.match_available) then --Tracevv((stderr,"%c", s->window[s->strstart-1])); bflush = _tr_tally_lit(s, s.window[s.strstart-1]) s.match_available = false end if (s.strstart < MIN_MATCH-1) then s.insert = s.strstart else s.insert = MIN_MATCH-1 end if (flush == ZLIB.Z_FINISH) then FLUSH_BLOCK_ONLY(s, 1); if (s.strm.avail_out == 0) then return finish_started end return finish_done end if (s.last_lit ~= 0) then FLUSH_BLOCK_ONLY(s, 0); if (s.strm.avail_out == 0) then return need_more end end return block_done end -- For Z_RLE, simply look for runs of bytes, generate matches only of distance one. Do not maintain a hash table. (It will be regenerated if this run of deflate switches away from Z_RLE.) function deflate_rle(s, flush) local bflush -- set if current block must be flushed local prev -- byte at distance one to match -- window[scan], window[strend] local scan, strend -- scan goes up to strend for length of run local window = s.window while (true) do -- Make sure that we always have enough lookahead, except at the end of the input file. We need MAX_MATCH bytes for the longest run, plus one for the unrolled loop. if (s.lookahead <= MAX_MATCH) then fill_window(s) if (s.lookahead <= MAX_MATCH and flush == ZLIB.Z_NO_FLUSH) then return need_more end if (s.lookahead == 0) then break end -- flush the current block end -- See how many times the previous byte repeats s.match_length = 0 if (s.lookahead >= MIN_MATCH and s.strstart > 0) then scan = s.strstart - 1 prev = window[scan] if (prev == window[scan+1] and prev == window[scan+2] and prev == window[scan+3]) then scan = scan + 3 strend = s.strstart + MAX_MATCH while (scan < strend) do scan = scan + 1; if (prev ~= window[scan]) then break end scan = scan + 1; if (prev ~= window[scan]) then break end scan = scan + 1; if (prev ~= window[scan]) then break end scan = scan + 1; if (prev ~= window[scan]) then break end scan = scan + 1; if (prev ~= window[scan]) then break end scan = scan + 1; if (prev ~= window[scan]) then break end scan = scan + 1; if (prev ~= window[scan]) then break end scan = scan + 1; if (prev ~= window[scan]) then break end end s.match_length = MAX_MATCH - (strend - scan) if (s.match_length > s.lookahead) then s.match_length = s.lookahead end end --Assert(scan <= s->window+(uInt)(s->window_size-1), "wild scan"); end -- Emit match if have run of MIN_MATCH or longer, else emit literal if (s.match_length >= MIN_MATCH) then check_match(s, s.strstart, s.strstart - 1, s.match_length) bflush = _tr_tally_dist(s, 1, s.match_length - MIN_MATCH) s.lookahead = s.lookahead - s.match_length s.strstart = s.strstart + s.match_length s.match_length = 0 else -- No match, output a literal byte --Tracevv((stderr,"%c", s->window[s->strstart])); bflush = _tr_tally_lit (s, s.window[s.strstart]) s.lookahead = s.lookahead - 1 s.strstart = s.strstart + 1 end if (bflush) then FLUSH_BLOCK_ONLY(s, 0); if (s.strm.avail_out == 0) then return need_more end end end s.insert = 0 if (flush == ZLIB.Z_FINISH) then FLUSH_BLOCK_ONLY(s, 1); if (s.strm.avail_out == 0) then return finish_started end return finish_done end if (s.last_lit ~= 0) then FLUSH_BLOCK_ONLY(s, 0); if (s.strm.avail_out == 0) then return need_more end end return block_done end -- For Z_HUFFMAN_ONLY, do not look for matches. Do not maintain a hash table. (It will be regenerated if this run of deflate switches away from Huffman.) function deflate_huff(s, flush) local bflush -- set if current block must be flushed while (true) do -- Make sure that we have a literal to write. if (s.lookahead == 0) then fill_window(s) if (s.lookahead == 0) then if (flush == ZLIB.Z_NO_FLUSH) then return need_more end break -- flush the current block end end -- Output a literal byte s.match_length = 0 --Tracevv((stderr,"%c", s->window[s->strstart])); bflush = _tr_tally_lit (s, s.window[s.strstart]) s.lookahead = s.lookahead - 1 s.strstart = s.strstart + 1 if (bflush) then FLUSH_BLOCK_ONLY(s, 0); if (s.strm.avail_out == 0) then return need_more end end end s.insert = 0 if (flush == ZLIB.Z_FINISH) then FLUSH_BLOCK_ONLY(s, 1); if (s.strm.avail_out == 0) then return finish_started end return finish_done end if (s.last_lit ~= 0) then FLUSH_BLOCK_ONLY(s, 0); if (s.strm.avail_out == 0) then return need_more end end return block_done end -- =========================================================================== -- Public API local M = {} M.deflate = function(input_string, opts) local DEFAULT_BUFFER_SIZE = 4000000000 -- 4 GB local this = ZLIB.deflateInit(opts) this.input_data = input_string this.next_in = getarg(opts, 'next_in', 0) this.avail_in = getarg(opts, 'avail_in', input_string:len() - this.next_in) local flush = getarg(opts, 'flush', ZLIB.Z_SYNC_FLUSH) local avail_out = getarg(opts, 'avail_out', -1) local result = '' repeat if (avail_out >= 0) then this.avail_out = avail_out else this.avail_out = DEFAULT_BUFFER_SIZE end this.output_data = '' this.next_out = 0 this.error = ZLIB.deflate(this, flush) if (avail_out >= 0) then return this.output_data end result = result .. this.output_data if (this.avail_out > 0) then break end until (this.error ~= ZLIB.Z_OK) return result end M.gzip = function(input_string, opts) if (not opts or type(opts) ~= 'table') then opts = {} end opts.windowBits = 15 + 16 opts.flush = ZLIB.Z_FINISH return M.deflate(input_string, opts) end return M