Skip to content

Instantly share code, notes, and snippets.

@chrisdickinson chrisdickinson/inflate.js Secret
Created Apr 14, 2013

Embed
What would you like to do?
module.exports = inflate
var pooled = require('./pooled')
, Buffer = require('buffer').Buffer
var MAXBITS = 15
, MAXLCODES = 286
, MAXDCODES = 30
, MAXCODES = (MAXLCODES+MAXDCODES)
, FIXLCODES = 288
var lens = [
3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258
]
var lext = [
0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0
]
var dists = [
1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
8193, 12289, 16385, 24577
]
var dext = [
0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
12, 12, 13, 13
]
var order = [
16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
]
var spare_byte = new Buffer(1)
function inflate() {
var stream = pooled(start)
, should_break = false
, is_final = false
, waiting = true
, output = []
, input = []
, got = 0
var fixed_codes
, read
, err
var adler_s1 = 1
, adler_s2 = 0
var on_got_block_header = bitwise(on_got_block_header_inner)
var decode_len = 1
, decode_first
, decode_count
, decode_index
, decode_code
, decode_take
, decode_huffman
, decode_done
return stream
function bitwise(fn) {
var have = 0
, bitbuf = 0
, bitcnt = 0
, need
, next
, val
return receive
function receive(buf) {
// preload the next buffer.
bitbuf = buf.readUInt8(0)
bitcnt = 8
fn(take)
}
function take(_need, _next) {
// read a byte at a time,
val = bitbuf
need = _need
next = _next
return void iter_take()
}
function iter_take() {
if(bitcnt >= need) {
return iter_done()
}
return void read(1, iter_take_next)
}
function iter_take_next(buf) {
val = (val | (buf.readUInt8(0) << bitcnt)) >>> 0
bitcnt += 8
return void iter_take()
}
function iter_done() {
bitbuf = val >>> need
bitcnt -= need
next((val & ((1 << need) - 1)) >>> 0)
}
}
function start(_read) {
read = _read
read(2, on_got_header)
}
function on_got_header(buf) {
var cmf = buf.readUInt8(0)
, flg = buf.readUInt8(1)
if(flg & 32) {
return read(4, on_got_fdict)
}
return read(1, on_got_block_header)
}
function on_got_fdict(buf) {
return read(1, on_got_block_header)
}
function on_got_block_header_inner(take) {
take(1, got_is_final)
function got_is_final(_is_final) {
is_final = _is_final
take(2, got_type)
}
function got_type(type) {
if(type === 0) {
return read(4, on_got_len)
}
if(type === 1) {
return read_fixed(take)
}
return read_dynamic(take)
}
}
function on_got_len(buf) {
var want = buf.readUInt16LE(0)
, nlen = buf.readUInt16LE(2)
if((~nlen & 0xFFFF) !== want) {
return void stream.emit('error', new Error(
'failed len / nlen check'
))
}
if(!want) {
return read(1, on_got_block_header)
}
return read(want, on_got_stored_data)
}
function on_got_stored_data(buf) {
update_adler(buf)
stream.queue(buf)
return is_final ? read(4, on_got_adler) : read(1, on_got_block_header)
}
function on_got_adler(buf) {
if(buf.readUInt32BE(0) !== ((adler_s2 << 16) | adler_s1) >>> 0) {
return void stream.emit('error', new Error('failed adler check'))
}
stream.release()
}
function read_fixed(take) {
fixed_codes = fixed_codes || build_fixed()
codes(take, fixed_codes.lencode, fixed_codes.distcode)
}
function read_dynamic(take) {
var nlen
, ndist
, ncode
, index
, err
, lengths = []
, lencnt = []
, lensym = []
, distcnt = []
, distsym = []
, lencode
, distcode
lencode = {
count: lencnt
, symbol: lensym
}
distcode = {
count: distcnt
, symbol: distsym
}
take(5, function get_nlen(_nlen) {
nlen = _nlen + 257
got_nlen()
})
function got_nlen() {
take(5, function get_ndist(_ndist) {
ndist = _ndist + 1
got_ndist()
})
}
function got_ndist() {
take(4, function get_ncode(_ncode) {
ncode = _ncode + 4
got_ncode()
})
}
function got_ncode() {
if(nlen > MAXLCODES || ndist > MAXDCODES) {
stream.emit('error', new Error('bad counts'))
return
}
index = 0
iter_ncode()
function iter_ncode() {
if(index >= ncode) {
return got_lengths()
}
take(3, function build_lengths(c) {
lengths[order[index++]] = c
iter_ncode()
})
}
}
function got_lengths() {
for(; index < 19; ++index) {
lengths[order[index]] = 0
}
if(0 !== construct(lencode, lengths, 19)) {
return void stream.emit('error', new Error('require complete code set'))
}
index = 0
iter_ndist()
}
function iter_ndist() {
if(index >= nlen + ndist) {
return done()
}
var symbol
, len
decode(take, lencode, function decoded(_symbol) {
symbol = _symbol
if(symbol < 16) {
lengths[index++] = symbol
return void iter_ndist()
}
len = 0
if(symbol === 16) {
if(index === 0) {
return void stream.emit('error', new Error('no last length'))
}
len = lengths[index - 1]
return void take(2, function tiny_one(c) {
symbol = 3 + c
check()
})
}
if(symbol === 17) {
return void take(3, function tiny_two(c) {
symbol = 3 + c
check()
})
}
take(7, function tiny_three(c) {
symbol = 11 + c
check()
})
})
function check() {
if(index + symbol > nlen + ndist) {
return void stream.emit('error', new Error('too many lengths'))
}
while(symbol--) {
lengths[index++] = len
}
iter_ndist()
}
}
function done() {
construct(lencode, lengths, nlen)
construct(distcode, lengths.slice(nlen), ndist)
return codes(take, lencode, distcode)
}
}
function codes(take, lencode, distcode) {
var dist
, len
, buf
, sym
return void iter_codes()
function iter_codes() {
decode(take, lencode, inner_iter_codes)
}
function inner_iter_codes(symbol) {
sym = symbol
if(sym < 0) {
return void stream.emit('error', new Error('invalid sym'))
}
if(sym < 256) {
var buf = new Buffer([sym])
update_adler(buf)
stream.queue(buf)
return void iter_codes()
}
if(sym === 256) {
return void (is_final ? read(4, on_got_adler) : on_got_block_header_inner(take))
}
sym -= 257
if(sym >= 29) {
return void stream.emit('error', new Error('invalid fixed code'))
}
take(lext[sym], iter_codes_lext)
}
function iter_codes_lext(extra) {
len = lens[sym] + extra
decode(take, distcode, iter_codes_distcode)
}
function iter_codes_distcode(symbol) {
sym = symbol
if(symbol < 0) {
return void stream.emit('error', new Error('invalid symbol'))
}
take(dext[sym], iter_codes_dext)
}
function iter_codes_dext(extra) {
dist = dists[sym] + extra
var out = new Buffer(len)
, idx = 0
, tmp
while(len--) {
spare_byte.writeUInt8(tmp = read_output(dist), 0)
out.writeUInt8(tmp, idx)
update_adler(spare_byte)
++idx
}
stream.queue(out)
return void iter_codes()
}
}
function read_output(from) {
return output[output.length - from]
}
function update_adler(buf) {
var len
, byt
, olen
olen = output.length
for(var i = 0, len = buf.length; i < len; ++i) {
byt = buf.readUInt8(i)
adler_s1 = (adler_s1 + byt) % 65521
adler_s2 = (adler_s2 + adler_s1) % 65521
output.push(byt)
++olen
if(olen > 32768) {
output.shift()
}
}
}
function decode(take, huffman, done) {
var len = 1
, first
, count
, index
, code
decode_len = 1
decode_code = decode_first = decode_index = 0
decode_take = take
decode_huffman = huffman
decode_done = done
return void iter_decode()
}
function iter_decode() {
if(decode_len > MAXBITS) {
stream.emit('error', new Error('ran out of codes'))
return
}
decode_take(1, decodeiter)
}
function decodeiter(decode_input) {
decode_code = (decode_code | decode_input) >>> 0
decode_count = decode_huffman.count[decode_len]
if(decode_code < decode_first + decode_count) {
return decode_done(decode_huffman.symbol[decode_index + (decode_code - decode_first)])
}
decode_index += decode_count
decode_first += decode_count
decode_first <<= 1
decode_code = (decode_code << 1) >>> 0
++decode_len
iter_decode()
}
}
function build_fixed() {
var lencnt = []
, lensym = []
, distcnt = []
, distsym = []
var lencode = {
count: lencnt
, symbol: lensym
}
var distcode = {
count: distcnt
, symbol: distsym
}
var lengths = []
, symbol
for(symbol = 0; symbol < 144; ++symbol) {
lengths[symbol] = 8
}
for(; symbol < 256; ++symbol) {
lengths[symbol] = 9
}
for(; symbol < 280; ++symbol) {
lengths[symbol] = 7
}
for(; symbol < FIXLCODES; ++symbol) {
lengths[symbol] = 8
}
construct(lencode, lengths, FIXLCODES)
for(symbol = 0; symbol < MAXDCODES; ++symbol) {
lengths[symbol] = 5
}
construct(distcode, lengths, MAXDCODES)
return {lencode: lencode, distcode: distcode}
}
function construct(huffman, lengths, num) {
var symbol
, left
, offs
, len
offs = []
for(len = 0; len <= MAXBITS; ++len) {
huffman.count[len] = 0
}
for(symbol = 0; symbol < num; ++symbol) {
huffman.count[lengths[symbol]] += 1
}
if(huffman.count[0] === num) {
return
}
left = 1
for(len = 1; len <= MAXBITS; ++len) {
left <<= 1
left -= huffman.count[len]
if(left < 0) {
return left
}
}
offs[1] = 0
for(len = 1; len < MAXBITS; ++len) {
offs[len + 1] = offs[len] + huffman.count[len]
}
for(symbol = 0; symbol < num; ++symbol) {
if(lengths[symbol] !== 0) {
huffman.symbol[offs[lengths[symbol]]++] = symbol
}
}
return left
}
module.exports = pooled
var through = require('through')
, Buffer = require('buffer').Buffer
var next_tick = typeof setImmediate !== 'undefined' ? setImmediate : function nexttick(fn) {
process.nextTick(fn)
}
function pooled(fn, should_release) {
var stream = through(write, end)
, flushing = false
, recursed = 0
, pool = []
, want = 0
, got = 0
, pooloffs = 0
, ondrain
, onread
fn(read)
should_release = should_release === undefined ? true : should_release
stream.release = release
return stream
function write(buf) {
pool.push(buf)
got += buf.length
if(flushing) {
return
}
if(stream.paused && !ondrain) {
ondrain = true
return stream.once('drain', function drained() {
ondrain = false
exec()
})
}
return exec()
}
function release() {
if(should_release) {
if(pooloffs && pool.length) {
pool[0] = pool[0].slice(pooloffs)
}
if(pool.length) {
stream.emit('unused', pool)
}
}
pool.length = 0
stream.queue(null)
}
function exec() {
var input
, had
had = got
got -= want
if(got < 0) {
got = 0
return
}
input = build_buffer(had - got)
++recursed
if(recursed > 300) {
flushing = true
return next_tick(function on_next_tick() {
recursed = 0
flushing = false
onread.call(stream, input)
})
}
onread.call(stream, input)
}
function build_buffer(num) {
var out = new Buffer(num)
, offset = 0
, tocopy
, tmp
for(var i = 0, len = pool.length; i < len; ++i) {
tocopy = Math.min(pool[i].length - pooloffs, num)
pool[i].copy(out, offset, pooloffs, tocopy + pooloffs)
offset += tocopy
if(offset === num) {
break
}
pooloffs = 0
}
if(i === len) {
// exhausted pool entirely
pool.length = 0
} else if(tocopy < pool[i].length) {
// partially exhausted last member,
// keep it around but discard the rest.
pooloffs += tocopy
tmp = pool[i]
pool.splice(0, i + 1, tmp)
} else {
// completely exhausted last member,
// discard everything up to and including
// that member.
pool.splice(0, i + 1)
}
return out
}
function end() {
if(got < want) {
stream.emit('error', new Error('not enough bytes'))
return
}
stream.queue(null)
}
function read(num, _onread) {
want = num
onread = _onread
if(want <= got) {
exec()
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.