ou1z

Untitled

Jul 25th, 2021
764
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. --[[
  2.  
  3. LUA MODULE
  4.  
  5. compress.deflatelua - deflate (and gunzip/zlib) implemented in Lua.
  6.  
  7. SYNOPSIS
  8. local DEFLATE = require 'compress.deflatelua'
  9. -- uncompress gzip file
  10. local fh = assert(io.open'foo.txt.gz', 'rb')
  11. local ofh = assert(io.open'foo.txt', 'wb')
  12. DEFLATE.gunzip {input=fh, output=ofh}
  13. fh:close(); ofh:close()
  14. -- can also uncompress from string including zlib and raw DEFLATE formats.
  15. DESCRIPTION
  16. This is a pure Lua implementation of decompressing the DEFLATE format,
  17. including the related zlib and gzip formats.
  18. Note: This library only supports decompression.
  19. Compression is not currently implemented.
  20.  
  21. API
  22.  
  23. Note: in the following functions, input stream `fh` may be
  24. a file handle, string, or an iterator function that returns strings.
  25. Output stream `ofh` may be a file handle or a function that
  26. consumes one byte (number 0..255) per call.
  27.  
  28. DEFLATE.inflate {input=fh, output=ofh}
  29.  
  30. Decompresses input stream `fh` in the DEFLATE format
  31. while writing to output stream `ofh`.
  32. DEFLATE is detailed in http://tools.ietf.org/html/rfc1951 .
  33. DEFLATE.gunzip {input=fh, output=ofh, disable_crc=disable_crc}
  34. Decompresses input stream `fh` with the gzip format
  35. while writing to output stream `ofh`.
  36. `disable_crc` (defaults to `false`) will disable CRC-32 checking
  37. to increase speed.
  38. gzip is detailed in http://tools.ietf.org/html/rfc1952 .
  39.  
  40. DEFLATE.inflate_zlib {input=fh, output=ofh, disable_crc=disable_crc}
  41. Decompresses input stream `fh` with the zlib format
  42. while writing to output stream `ofh`.
  43. `disable_crc` (defaults to `false`) will disable CRC-32 checking
  44. to increase speed.
  45. zlib is detailed in http://tools.ietf.org/html/rfc1950 .
  46.  
  47. DEFLATE.adler32(byte, crc) --> rcrc
  48. Returns adler32 checksum of byte `byte` (number 0..255) appended
  49. to string with adler32 checksum `crc`. This is internally used by
  50. `inflate_zlib`.
  51. ADLER32 in detailed in http://tools.ietf.org/html/rfc1950 .
  52.  
  53. COMMAND LINE UTILITY
  54.  
  55. A `gunziplua` command line utility (in folder `bin`) is also provided.
  56. This mimicks the *nix `gunzip` utility but is a pure Lua implementation
  57. that invokes this library. For help do
  58. gunziplua -h
  59. DEPENDENCIES
  60.  
  61. Requires 'digest.crc32lua' (used for optional CRC-32 checksum checks).
  62. https://github.com/davidm/lua-digest-crc32lua
  63.  
  64. Will use a bit library ('bit', 'bit32', 'bit.numberlua') if available. This
  65. is not that critical for this library but is required by digest.crc32lua.
  66.  
  67. 'pythonic.optparse' is only required by the optional `gunziplua`
  68. command-line utilty for command line parsing.
  69. https://github.com/davidm/lua-pythonic-optparse
  70.  
  71. INSTALLATION
  72.  
  73. Copy the `compress` directory into your LUA_PATH.
  74. REFERENCES
  75.  
  76. [1] DEFLATE Compressed Data Format Specification version 1.3
  77. http://tools.ietf.org/html/rfc1951
  78. [2] GZIP file format specification version 4.3
  79. http://tools.ietf.org/html/rfc1952
  80. [3] http://en.wikipedia.org/wiki/DEFLATE
  81. [4] pyflate, by Paul Sladen
  82. http://www.paul.sladen.org/projects/pyflate/
  83. [5] Compress::Zlib::Perl - partial pure Perl implementation of
  84. Compress::Zlib
  85. http://search.cpan.org/~nwclark/Compress-Zlib-Perl/Perl.pm
  86.  
  87. LICENSE
  88.  
  89. (c) 2008-2011 David Manura. Licensed under the same terms as Lua (MIT).
  90.  
  91. Permission is hereby granted, free of charge, to any person obtaining a copy
  92. of this software and associated documentation files (the "Software"), to deal
  93. in the Software without restriction, including without limitation the rights
  94. to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  95. copies of the Software, and to permit persons to whom the Software is
  96. furnished to do so, subject to the following conditions:
  97.  
  98. The above copyright notice and this permission notice shall be included in
  99. all copies or substantial portions of the Software.
  100.  
  101. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  102. IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  103. FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  104. AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  105. LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  106. OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  107. THE SOFTWARE.
  108. (end license)
  109. --]]
  110.  
  111. local M = {_TYPE='module', _NAME='compress.deflatelua', _VERSION='0.3.20111128'}
  112.  
  113. local assert = assert
  114. local error = error
  115. local ipairs = ipairs
  116. local pairs = pairs
  117. local print = print
  118. local require = require
  119. local tostring = tostring
  120. local type = type
  121. local setmetatable = setmetatable
  122. local io = io
  123. local math = math
  124. local table_sort = table.sort
  125. local math_max = math.max
  126. local string_char = string.char
  127.  
  128. --[[
  129. Requires the first module listed that exists, else raises like `require`.
  130. If a non-string is encountered, it is returned.
  131. Second return value is module name loaded (or '').
  132. --]]
  133. local function requireany(...)
  134.   local errs = {}
  135.   for i = 1, select('#', ...) do local name = select(i, ...)
  136.     if type(name) ~= 'string' then return name, '' end
  137.     local ok, mod = pcall(require, name)
  138.     if ok then return mod, name end
  139.     errs[#errs+1] = mod
  140.   end
  141.   error(table.concat(errs, '\n'), 2)
  142. end
  143.  
  144.  
  145. --local crc32 = require "digest.crc32lua" . crc32_byte
  146. local bit, name_ = requireany('bit', 'bit32', 'bit.numberlua', nil)
  147.  
  148. local DEBUG = false
  149.  
  150. -- Whether to use `bit` library functions in current module.
  151. -- Unlike the crc32 library, it doesn't make much difference in this module.
  152. local NATIVE_BITOPS = (bit ~= nil)
  153.  
  154. local band, lshift, rshift
  155. if NATIVE_BITOPS then
  156.   band = bit.band
  157.   lshift = bit.lshift
  158.   rshift = bit.rshift
  159. end
  160.  
  161.  
  162. local function warn(s)
  163.   io.stderr:write(s, '\n')
  164. end
  165.  
  166.  
  167. local function debug(...)
  168.   print('DEBUG', ...)
  169. end
  170.  
  171.  
  172. local function runtime_error(s, level)
  173.   level = level or 1
  174.   error({s}, level+1)
  175. end
  176.  
  177.  
  178. local function make_outstate(outbs)
  179.   local outstate = {}
  180.   outstate.outbs = outbs
  181.   outstate.window = {}
  182.   outstate.window_pos = 1
  183.   return outstate
  184. end
  185.  
  186.  
  187. local function output(outstate, byte)
  188.   -- debug('OUTPUT:', s)
  189.   local window_pos = outstate.window_pos
  190.   outstate.outbs(byte)
  191.   outstate.window[window_pos] = byte
  192.   outstate.window_pos = window_pos % 32768 + 1 -- 32K
  193. end
  194.  
  195.  
  196. local function noeof(val)
  197.   return assert(val, 'unexpected end of file')
  198. end
  199.  
  200.  
  201. local function hasbit(bits, bit)
  202.   return bits % (bit + bit) >= bit
  203. end
  204.  
  205.  
  206. local function memoize(f)
  207.   local mt = {}
  208.   local t = setmetatable({}, mt)
  209.   function mt:__index(k)
  210.     local v = f(k)
  211.     t[k] = v
  212.     return v
  213.   end
  214.   return t
  215. end
  216.  
  217.  
  218. -- small optimization (lookup table for powers of 2)
  219. local pow2 = memoize(function(n) return 2^n end)
  220.  
  221. --local tbits = memoize(
  222. -- function(bits)
  223. -- return memoize( function(bit) return getbit(bits, bit) end )
  224. -- end )
  225.  
  226.  
  227. -- weak metatable marking objects as bitstream type
  228. local is_bitstream = setmetatable({}, {__mode='k'})
  229.  
  230.  
  231. -- DEBUG
  232. -- prints LSB first
  233. --[[
  234. local function bits_tostring(bits, nbits)
  235. local s = ''
  236. local tmp = bits
  237. local function f()
  238. local b = tmp % 2 == 1 and 1 or 0
  239. s = s .. b
  240. tmp = (tmp - b) / 2
  241. end
  242. if nbits then
  243. for i=1,nbits do f() end
  244. else
  245. while tmp ~= 0 do f() end
  246. end
  247.  
  248. return s
  249. end
  250. --]]
  251.  
  252. local function bytestream_from_file(fh)
  253.   local o = {}
  254.   function o:read()
  255.     local sb = fh:read(1)
  256.     if sb then return sb:byte() end
  257.   end
  258.   return o
  259. end
  260.  
  261.  
  262. local function bytestream_from_string(s)
  263.   local i = 1
  264.   local o = {}
  265.   function o:read()
  266.     local by
  267.     if i <= #s then
  268.       by = s:byte(i)
  269.       i = i + 1
  270.     end
  271.     return by
  272.   end
  273.   return o
  274. end
  275.  
  276.  
  277. local function bytestream_from_function(f)
  278.   local i = 0
  279.   local buffer = ''
  280.   local o = {}
  281.   function o:read()
  282.     i = i + 1
  283.     if i > #buffer then
  284.       buffer = f()
  285.       if not buffer then return end
  286.       i = 1
  287.     end
  288.     return buffer:byte(i,i)
  289.   end
  290.   return o
  291. end
  292.  
  293.  
  294. local function bitstream_from_bytestream(bys)
  295.   local buf_byte = 0
  296.   local buf_nbit = 0
  297.   local o = {}
  298.  
  299.   function o:nbits_left_in_byte()
  300.     return buf_nbit
  301.   end
  302.  
  303.   if NATIVE_BITOPS then
  304.     function o:read(nbits)
  305.       nbits = nbits or 1
  306.       while buf_nbit < nbits do
  307.         local byte = bys:read()
  308.         if not byte then return end -- note: more calls also return nil
  309.         buf_byte = buf_byte + lshift(byte, buf_nbit)
  310.         buf_nbit = buf_nbit + 8
  311.       end
  312.       local bits
  313.       if nbits == 0 then
  314.         bits = 0
  315.       elseif nbits == 32 then
  316.         bits = buf_byte
  317.         buf_byte = 0
  318.       else
  319.         bits = band(buf_byte, rshift(0xffffffff, 32 - nbits))
  320.         buf_byte = rshift(buf_byte, nbits)
  321.       end
  322.       buf_nbit = buf_nbit - nbits
  323.       return bits
  324.     end
  325.   else
  326.     function o:read(nbits)
  327.       nbits = nbits or 1
  328.       while buf_nbit < nbits do
  329.         local byte = bys:read()
  330.         if not byte then return end -- note: more calls also return nil
  331.         buf_byte = buf_byte + pow2[buf_nbit] * byte
  332.         buf_nbit = buf_nbit + 8
  333.       end
  334.       local m = pow2[nbits]
  335.       local bits = buf_byte % m
  336.       buf_byte = (buf_byte - bits) / m
  337.       buf_nbit = buf_nbit - nbits
  338.       return bits
  339.     end
  340.   end
  341.  
  342.   is_bitstream[o] = true
  343.  
  344.   return o
  345. end
  346.  
  347.  
  348. local function get_bitstream(o)
  349.   local bs
  350.   if is_bitstream[o] then
  351.     return o
  352.   elseif io.type(o) == 'file' then
  353.     bs = bitstream_from_bytestream(bytestream_from_file(o))
  354.   elseif type(o) == 'string' then
  355.     bs = bitstream_from_bytestream(bytestream_from_string(o))
  356.   elseif type(o) == 'function' then
  357.     bs = bitstream_from_bytestream(bytestream_from_function(o))
  358.   else
  359.     runtime_error 'unrecognized type'
  360.   end
  361.   return bs
  362. end
  363.  
  364.  
  365. local function get_obytestream(o)
  366.   local bs
  367.   if io.type(o) == 'file' then
  368.     bs = function(sbyte) o:write(string_char(sbyte)) end
  369.   elseif type(o) == 'function' then
  370.     bs = o
  371.   else
  372.     runtime_error('unrecognized type: ' .. tostring(o))
  373.   end
  374.   return bs
  375. end
  376.  
  377.  
  378. local function HuffmanTable(init, is_full)
  379.   local t = {}
  380.   if is_full then
  381.     for val,nbits in pairs(init) do
  382.       if nbits ~= 0 then
  383.         t[#t+1] = {val=val, nbits=nbits}
  384.         --debug('*',val,nbits)
  385.       end
  386.     end
  387.   else
  388.     for i=1,#init-2,2 do
  389.       local firstval, nbits, nextval = init[i], init[i+1], init[i+2]
  390.       --debug(val, nextval, nbits)
  391.       if nbits ~= 0 then
  392.         for val=firstval,nextval-1 do
  393.           t[#t+1] = {val=val, nbits=nbits}
  394.         end
  395.       end
  396.     end
  397.   end
  398.   table_sort(t, function(a,b)
  399.     return a.nbits == b.nbits and a.val < b.val or a.nbits < b.nbits
  400.   end)
  401.  
  402.   -- assign codes
  403.   local code = 1 -- leading 1 marker
  404.   local nbits = 0
  405.   for i,s in ipairs(t) do
  406.     if s.nbits ~= nbits then
  407.       code = code * pow2[s.nbits - nbits]
  408.       nbits = s.nbits
  409.     end
  410.     s.code = code
  411.     --debug('huffman code:', i, s.nbits, s.val, code, bits_tostring(code))
  412.     code = code + 1
  413.   end
  414.  
  415.   local minbits = math.huge
  416.   local look = {}
  417.   for i,s in ipairs(t) do
  418.     minbits = math.min(minbits, s.nbits)
  419.     look[s.code] = s.val
  420.   end
  421.  
  422.   --for _,o in ipairs(t) do
  423.   -- debug(':', o.nbits, o.val)
  424.   --end
  425.  
  426.   -- function t:lookup(bits) return look[bits] end
  427.  
  428.   local msb = NATIVE_BITOPS and function(bits, nbits)
  429.     local res = 0
  430.     for i=1,nbits do
  431.       res = lshift(res, 1) + band(bits, 1)
  432.       bits = rshift(bits, 1)
  433.     end
  434.     return res
  435.   end or function(bits, nbits)
  436.     local res = 0
  437.     for i=1,nbits do
  438.       local b = bits % 2
  439.       bits = (bits - b) / 2
  440.       res = res * 2 + b
  441.     end
  442.     return res
  443.   end
  444.  
  445.   local tfirstcode = memoize(
  446.     function(bits) return pow2[minbits] + msb(bits, minbits) end)
  447.  
  448.   function t:read(bs)
  449.     local code = 1 -- leading 1 marker
  450.     local nbits = 0
  451.     while 1 do
  452.       if nbits == 0 then -- small optimization (optional)
  453.         code = tfirstcode[noeof(bs:read(minbits))]
  454.         nbits = nbits + minbits
  455.       else
  456.         local b = noeof(bs:read())
  457.         nbits = nbits + 1
  458.         code = code * 2 + b -- MSB first
  459.         --[[NATIVE_BITOPS
  460. code = lshift(code, 1) + b -- MSB first
  461. --]]
  462.       end
  463.       --debug('code?', code, bits_tostring(code))
  464.       local val = look[code]
  465.       if val then
  466.         --debug('FOUND', val)
  467.         return val
  468.       end
  469.     end
  470.   end
  471.  
  472.   return t
  473. end
  474.  
  475.  
  476. local function parse_gzip_header(bs)
  477.   -- local FLG_FTEXT = 2^0
  478.   local FLG_FHCRC = 2^1
  479.   local FLG_FEXTRA = 2^2
  480.   local FLG_FNAME = 2^3
  481.   local FLG_FCOMMENT = 2^4
  482.  
  483.   local id1 = bs:read(8)
  484.   local id2 = bs:read(8)
  485.   if id1 ~= 31 or id2 ~= 139 then
  486.     runtime_error 'not in gzip format'
  487.   end
  488.   local cm = bs:read(8) -- compression method
  489.   local flg = bs:read(8) -- FLaGs
  490.   local mtime = bs:read(32) -- Modification TIME
  491.   local xfl = bs:read(8) -- eXtra FLags
  492.   local os = bs:read(8) -- Operating System
  493.  
  494.   if DEBUG then
  495.     debug("CM=", cm)
  496.     debug("FLG=", flg)
  497.     debug("MTIME=", mtime)
  498.     -- debug("MTIME_str=",os.date("%Y-%m-%d %H:%M:%S",mtime)) -- non-portable
  499.     debug("XFL=", xfl)
  500.     debug("OS=", os)
  501.   end
  502.  
  503.   if not os then runtime_error 'invalid header' end
  504.  
  505.   if hasbit(flg, FLG_FEXTRA) then
  506.     local xlen = bs:read(16)
  507.     local extra = 0
  508.     for i=1,xlen do
  509.       extra = bs:read(8)
  510.     end
  511.     if not extra then runtime_error 'invalid header' end
  512.   end
  513.  
  514.   local function parse_zstring(bs)
  515.     repeat
  516.       local by = bs:read(8)
  517.       if not by then runtime_error 'invalid header' end
  518.     until by == 0
  519.   end
  520.  
  521.   if hasbit(flg, FLG_FNAME) then
  522.     parse_zstring(bs)
  523.   end
  524.  
  525.   if hasbit(flg, FLG_FCOMMENT) then
  526.     parse_zstring(bs)
  527.   end
  528.  
  529.   if hasbit(flg, FLG_FHCRC) then
  530.     local crc16 = bs:read(16)
  531.     if not crc16 then runtime_error 'invalid header' end
  532.     -- IMPROVE: check CRC. where is an example .gz file that
  533.     -- has this set?
  534.     if DEBUG then
  535.       debug("CRC16=", crc16)
  536.     end
  537.   end
  538. end
  539.  
  540. local function parse_zlib_header(bs)
  541.   local cm = bs:read(4) -- Compression Method
  542.   local cinfo = bs:read(4) -- Compression info
  543.   local fcheck = bs:read(5) -- FLaGs: FCHECK (check bits for CMF and FLG)
  544.   local fdict = bs:read(1) -- FLaGs: FDICT (present dictionary)
  545.   local flevel = bs:read(2) -- FLaGs: FLEVEL (compression level)
  546.   local cmf = cinfo * 16 + cm -- CMF (Compresion Method and flags)
  547.   local flg = fcheck + fdict * 32 + flevel * 64 -- FLaGs
  548.  
  549.   if cm ~= 8 then -- not "deflate"
  550.     runtime_error("unrecognized zlib compression method: " .. cm)
  551.   end
  552.   if cinfo > 7 then
  553.     runtime_error("invalid zlib window size: cinfo=" .. cinfo)
  554.   end
  555.   local window_size = 2^(cinfo + 8)
  556.  
  557.   if (cmf*256 + flg) % 31 ~= 0 then
  558.     runtime_error("invalid zlib header (bad fcheck sum)")
  559.   end
  560.  
  561.   if fdict == 1 then
  562.     runtime_error("FIX:TODO - FDICT not currently implemented")
  563.     local dictid_ = bs:read(32)
  564.   end
  565.  
  566.   return window_size
  567. end
  568.  
  569. local function parse_huffmantables(bs)
  570.     local hlit = bs:read(5) -- # of literal/length codes - 257
  571.     local hdist = bs:read(5) -- # of distance codes - 1
  572.     local hclen = noeof(bs:read(4)) -- # of code length codes - 4
  573.  
  574.     local ncodelen_codes = hclen + 4
  575.     local codelen_init = {}
  576.     local codelen_vals = {
  577.       16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}
  578.     for i=1,ncodelen_codes do
  579.       local nbits = bs:read(3)
  580.       local val = codelen_vals[i]
  581.       codelen_init[val] = nbits
  582.     end
  583.     local codelentable = HuffmanTable(codelen_init, true)
  584.  
  585.     local function decode(ncodes)
  586.       local init = {}
  587.       local nbits
  588.       local val = 0
  589.       while val < ncodes do
  590.         local codelen = codelentable:read(bs)
  591.         --FIX:check nil?
  592.         local nrepeat
  593.         if codelen <= 15 then
  594.           nrepeat = 1
  595.           nbits = codelen
  596.           --debug('w', nbits)
  597.         elseif codelen == 16 then
  598.           nrepeat = 3 + noeof(bs:read(2))
  599.           -- nbits unchanged
  600.         elseif codelen == 17 then
  601.           nrepeat = 3 + noeof(bs:read(3))
  602.           nbits = 0
  603.         elseif codelen == 18 then
  604.           nrepeat = 11 + noeof(bs:read(7))
  605.           nbits = 0
  606.         else
  607.           error 'ASSERT'
  608.         end
  609.         for i=1,nrepeat do
  610.           init[val] = nbits
  611.           val = val + 1
  612.         end
  613.       end
  614.       local huffmantable = HuffmanTable(init, true)
  615.       return huffmantable
  616.     end
  617.  
  618.     local nlit_codes = hlit + 257
  619.     local ndist_codes = hdist + 1
  620.  
  621.     local littable = decode(nlit_codes)
  622.     local disttable = decode(ndist_codes)
  623.  
  624.     return littable, disttable
  625. end
  626.  
  627.  
  628. local tdecode_len_base
  629. local tdecode_len_nextrabits
  630. local tdecode_dist_base
  631. local tdecode_dist_nextrabits
  632. local function parse_compressed_item(bs, outstate, littable, disttable)
  633.   local val = littable:read(bs)
  634.   --debug(val, val < 256 and string_char(val))
  635.   if val < 256 then -- literal
  636.     output(outstate, val)
  637.   elseif val == 256 then -- end of block
  638.     return true
  639.   else
  640.     if not tdecode_len_base then
  641.       local t = {[257]=3}
  642.       local skip = 1
  643.       for i=258,285,4 do
  644.         for j=i,i+3 do t[j] = t[j-1] + skip end
  645.         if i ~= 258 then skip = skip * 2 end
  646.       end
  647.       t[285] = 258
  648.       tdecode_len_base = t
  649.       --for i=257,285 do debug('T1',i,t[i]) end
  650.     end
  651.     if not tdecode_len_nextrabits then
  652.       local t = {}
  653.       if NATIVE_BITOPS then
  654.         for i=257,285 do
  655.           local j = math_max(i - 261, 0)
  656.           t[i] = rshift(j, 2)
  657.         end
  658.       else
  659.         for i=257,285 do
  660.           local j = math_max(i - 261, 0)
  661.           t[i] = (j - (j % 4)) / 4
  662.         end
  663.       end
  664.       t[285] = 0
  665.       tdecode_len_nextrabits = t
  666.       --for i=257,285 do debug('T2',i,t[i]) end
  667.     end
  668.     local len_base = tdecode_len_base[val]
  669.     local nextrabits = tdecode_len_nextrabits[val]
  670.     local extrabits = bs:read(nextrabits)
  671.     local len = len_base + extrabits
  672.  
  673.     if not tdecode_dist_base then
  674.       local t = {[0]=1}
  675.       local skip = 1
  676.       for i=1,29,2 do
  677.         for j=i,i+1 do t[j] = t[j-1] + skip end
  678.         if i ~= 1 then skip = skip * 2 end
  679.       end
  680.       tdecode_dist_base = t
  681.       --for i=0,29 do debug('T3',i,t[i]) end
  682.     end
  683.     if not tdecode_dist_nextrabits then
  684.       local t = {}
  685.       if NATIVE_BITOPS then
  686.         for i=0,29 do
  687.           local j = math_max(i - 2, 0)
  688.           t[i] = rshift(j, 1)
  689.         end
  690.       else
  691.         for i=0,29 do
  692.           local j = math_max(i - 2, 0)
  693.           t[i] = (j - (j % 2)) / 2
  694.         end
  695.       end
  696.       tdecode_dist_nextrabits = t
  697.       --for i=0,29 do debug('T4',i,t[i]) end
  698.     end
  699.     local dist_val = disttable:read(bs)
  700.     local dist_base = tdecode_dist_base[dist_val]
  701.     local dist_nextrabits = tdecode_dist_nextrabits[dist_val]
  702.     local dist_extrabits = bs:read(dist_nextrabits)
  703.     local dist = dist_base + dist_extrabits
  704.  
  705.     --debug('BACK', len, dist)
  706.     for i=1,len do
  707.       local pos = (outstate.window_pos - 1 - dist) % 32768 + 1 -- 32K
  708.       output(outstate, assert(outstate.window[pos], 'invalid distance'))
  709.     end
  710.   end
  711.   return false
  712. end
  713.  
  714.  
  715. local function parse_block(bs, outstate)
  716.   local bfinal = bs:read(1)
  717.   local btype = bs:read(2)
  718.  
  719.   local BTYPE_NO_COMPRESSION = 0
  720.   local BTYPE_FIXED_HUFFMAN = 1
  721.   local BTYPE_DYNAMIC_HUFFMAN = 2
  722.   local BTYPE_RESERVED_ = 3
  723.  
  724.   if DEBUG then
  725.     debug('bfinal=', bfinal)
  726.     debug('btype=', btype)
  727.   end
  728.  
  729.   if btype == BTYPE_NO_COMPRESSION then
  730.     bs:read(bs:nbits_left_in_byte())
  731.     local len = bs:read(16)
  732.     local nlen_ = noeof(bs:read(16))
  733.  
  734.     for i=1,len do
  735.       local by = noeof(bs:read(8))
  736.       output(outstate, by)
  737.     end
  738.   elseif btype == BTYPE_FIXED_HUFFMAN or btype == BTYPE_DYNAMIC_HUFFMAN then
  739.     local littable, disttable
  740.     if btype == BTYPE_DYNAMIC_HUFFMAN then
  741.       littable, disttable = parse_huffmantables(bs)
  742.     else
  743.       littable = HuffmanTable {0,8, 144,9, 256,7, 280,8, 288,nil}
  744.       disttable = HuffmanTable {0,5, 32,nil}
  745.     end
  746.  
  747.     repeat
  748.       local is_done = parse_compressed_item(
  749.         bs, outstate, littable, disttable)
  750.     until is_done
  751.   else
  752.     runtime_error 'unrecognized compression type'
  753.   end
  754.  
  755.   return bfinal ~= 0
  756. end
  757.  
  758.  
  759. function M.inflate(t)
  760.   local bs = get_bitstream(t.input)
  761.   local outbs = get_obytestream(t.output)
  762.   local outstate = make_outstate(outbs)
  763.  
  764.   repeat
  765.     local is_final = parse_block(bs, outstate)
  766.   until is_final
  767. end
  768. local inflate = M.inflate
  769.  
  770.  
  771. function M.gunzip(t)
  772.   local bs = get_bitstream(t.input)
  773.   local outbs = get_obytestream(t.output)
  774.   local disable_crc = t.disable_crc
  775.   if disable_crc == nil then disable_crc = false end
  776.  
  777.   parse_gzip_header(bs)
  778.  
  779.   local data_crc32 = 0
  780.  
  781.   inflate{input=bs, output=
  782.     disable_crc and outbs or
  783.       function(byte)
  784.         data_crc32 = crc32(byte, data_crc32)
  785.         outbs(byte)
  786.       end
  787.   }
  788.  
  789.   bs:read(bs:nbits_left_in_byte())
  790.  
  791.   local expected_crc32 = bs:read(32)
  792.   local isize = bs:read(32) -- ignored
  793.   if DEBUG then
  794.     debug('crc32=', expected_crc32)
  795.     debug('isize=', isize)
  796.   end
  797.   if not disable_crc and data_crc32 then
  798.     if data_crc32 ~= expected_crc32 then
  799.       runtime_error('invalid compressed data--crc error')
  800.     end
  801.   end
  802.   if bs:read() then
  803.     warn 'trailing garbage ignored'
  804.   end
  805. end
  806.  
  807.  
  808. function M.adler32(byte, crc)
  809.   local s1 = crc % 65536
  810.   local s2 = (crc - s1) / 65536
  811.   s1 = (s1 + byte) % 65521
  812.   s2 = (s2 + s1) % 65521
  813.   return s2*65536 + s1
  814. end -- 65521 is the largest prime smaller than 2^16
  815.  
  816.  
  817. function M.inflate_zlib(t)
  818.   local bs = get_bitstream(t.input)
  819.   local outbs = get_obytestream(t.output)
  820.   local disable_crc = t.disable_crc
  821.   if disable_crc == nil then disable_crc = false end
  822.  
  823.   local window_size_ = parse_zlib_header(bs)
  824.  
  825.   local data_adler32 = 1
  826.  
  827.   inflate{input=bs, output=
  828.     disable_crc and outbs or
  829.       function(byte)
  830.         data_adler32 = M.adler32(byte, data_adler32)
  831.         outbs(byte)
  832.       end
  833.   }
  834.  
  835.   bs:read(bs:nbits_left_in_byte())
  836.  
  837.   local b3 = bs:read(8)
  838.   local b2 = bs:read(8)
  839.   local b1 = bs:read(8)
  840.   local b0 = bs:read(8)
  841.   local expected_adler32 = ((b3*256 + b2)*256 + b1)*256 + b0
  842.   if DEBUG then
  843.     debug('alder32=', expected_adler32)
  844.   end
  845.   if not disable_crc then
  846.     if data_adler32 ~= expected_adler32 then
  847.       runtime_error('invalid compressed data--crc error')
  848.     end
  849.   end
  850.   if bs:read() then
  851.     warn 'trailing garbage ignored'
  852.   end
  853. end
  854.  
  855.  
  856. return M
RAW Paste Data