inflate.js

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
}

pooled.js

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()
    }
  }
}