pub/archive/lib/src/zlib/deflate.dart

part of archive;


class Deflate {
  // enum CompressionLevel
  static const int DEFAULT_COMPRESSION = 6;
  static const int BEST_COMPRESSION = 9;
  static const int BEST_SPEED = 1;
  static const int NO_COMPRESSION = 0;

  // enum FlushMode
  static const int NO_FLUSH = 0;
  static const int PARTIAL_FLUSH = 1;
  static const int SYNC_FLUSH = 2;
  static const int FULL_FLUSH = 3;
  static const int FINISH = 4;

  Deflate(List<int> bytes, {int level: DEFAULT_COMPRESSION,
           int flush: FINISH}) :
    _input = new InputStream(bytes) {
    _init(level);
    _deflate(flush);
  }

  Deflate.buffer(this._input, {int level: DEFAULT_COMPRESSION,
                  int flush: FINISH}) {
    _init(level);
    _deflate(flush);
  }

  /**
   * Get the resulting compressed bytes.
   */
  List<int> getBytes() {
    _flushPending();
    return _output.getBytes();
  }

  /**
   * Get the resulting compressed bytes without storing the resulting data to
   * minimize memory usage.
   */
  List<int> takeBytes() {
    _flushPending();
    List<int> bytes = _output.getBytes();
    _output.clear();
    return bytes;
  }

  /**
   * Add more data to be deflated.
   */
  void addBytes(List<int> bytes, {int flush: FINISH}) {
    _input = new InputStream(bytes);
    _deflate(flush);
  }

  /**
   * Add more data to be deflated.
   */
  void addBuffer(InputStream buffer, {int flush: FINISH}) {
    _input = buffer;
    _deflate(flush);
  }

  /**
   * Compression level used (1..9)
   */
  int get level => _level;

  /**
   * Initialize the deflate structures for the given parameters.
   */
  void _init(int level,
             {int method: Z_DEFLATED,
             int windowBits: MAX_WBITS,
             int memLevel: DEF_MEM_LEVEL,
             int strategy: Z_DEFAULT_STRATEGY}) {
    if (level == null || level == Z_DEFAULT_COMPRESSION) {
      level = 6;
    }

    _config = _getConfig(level);

    if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||
        windowBits < 9 || windowBits > 15 || level < 0 || level > 9 ||
        strategy < 0 || strategy > Z_HUFFMAN_ONLY) {
      throw new ArchiveException('Invalid Deflate parameter');
    }

    _dynamicLengthTree = new Uint16List(HEAP_SIZE * 2);
    _dynamicDistTree = new Uint16List((2 * D_CODES + 1) * 2);
    _bitLengthTree = new Uint16List((2 * BL_CODES + 1) * 2);

    _windowBits = windowBits;
    _windowSize = 1 << _windowBits;
    _windowMask = _windowSize - 1;

    _hashBits = memLevel + 7;
    _hashSize = 1 << _hashBits;
    _hashMask = _hashSize - 1;
    _hashShift = ((_hashBits + MIN_MATCH - 1) ~/ MIN_MATCH);

    _window = new Uint8List(_windowSize * 2);
    _prev = new Uint16List(_windowSize);
    _head = new Uint16List(_hashSize);

    _litBufferSize = 1 << (memLevel + 6); // 16K elements by default

    // We overlay pending_buf and d_buf+l_buf. This works since the average
    // output size for (length,distance) codes is <= 24 bits.
    _pendingBuffer = new Uint8List(_litBufferSize * 4);
    _pendingBufferSize = _litBufferSize * 4;

    _dbuf = _litBufferSize;
    _lbuf = (1 + 2) * _litBufferSize;

    _level = level;

    _strategy = strategy;
    _method = method;

    _pending = 0;
    _pendingOut = 0;

    _status = BUSY_STATE;

    _lastFlush = NO_FLUSH;

    _trInit();
    _lmInit();
  }

  /**
   * Compress the current input buffer.
   */
  int _deflate(int flush) {
    if (flush > FINISH || flush < 0) {
      throw new ArchiveException('Invalid Deflate Parameter');
    }

    _lastFlush = flush;

    // Flush as much pending output as possible
    if (_pending != 0) {
      // Make sure there is something to do and avoid duplicate consecutive
      // flushes. For repeated and useless calls with FINISH, we keep
      // returning Z_STREAM_END instead of Z_BUFF_ERROR.
      _flushPending();
    }

    // Start a new block or continue the current one.
    if (!_input.isEOS || _lookAhead != 0 ||
        (flush != NO_FLUSH && _status != FINISH_STATE)) {
      int bstate = -1;
      switch (_config.function) {
        case STORED:
          bstate = _deflateStored(flush);
          break;
        case FAST:
          bstate = _deflateFast(flush);
          break;
        case SLOW:
          bstate = _deflateSlow(flush);
          break;
        default:
          break;
      }

      if (bstate == FINISH_STARTED || bstate == FINISH_DONE) {
        _status = FINISH_STATE;
      }

      if (bstate == NEED_MORE || bstate == FINISH_STARTED) {
        // 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.
        return Z_OK;
      }

      if (bstate == BLOCK_DONE) {
        if (flush == PARTIAL_FLUSH) {
          _trAlign();
        } else {
          // FULL_FLUSH or SYNC_FLUSH
          _trStoredBlock(0, 0, false);
          // For a full flush, this empty block will be recognized
          // as a special marker by inflate_sync().
          if (flush == FULL_FLUSH) {
            for (int i = 0; i < _hashSize; i++) {
              // forget history
              _head[i] = 0;
            }
          }
        }

        _flushPending();
      }
    }

    if (flush != FINISH) {
      return Z_OK;
    }

    return Z_STREAM_END;
  }

  void _lmInit() {
    _actualWindowSize = 2 * _windowSize;

    _head[_hashSize - 1] = 0;
    for (int i = 0; i < _hashSize - 1; i++) {
      _head[i] = 0;
    }

    _strStart = 0;
    _blockStart = 0;
    _lookAhead = 0;
    _matchLength = _prevLength = MIN_MATCH - 1;
    _matchAvailable = 0;
    _insertHash = 0;
  }

  /**
   * Initialize the tree data structures for a new zlib stream.
   */
  void _trInit() {
    _lDesc.dynamicTree = _dynamicLengthTree;
    _lDesc.staticDesc = _StaticTree.staticLDesc;

    _dDesc.dynamicTree = _dynamicDistTree;
    _dDesc.staticDesc = _StaticTree.staticDDesc;

    _blDesc.dynamicTree = _bitLengthTree;
    _blDesc.staticDesc = _StaticTree.staticBlDesc;

    _bitBuffer = 0;
    _numValidBits = 0;
    _lastEOBLen = 8; // enough lookahead for inflate

    // Initialize the first block of the first file:
    _initBlock();
  }

  void _initBlock() {
    // Initialize the trees.
    for (int i = 0; i < L_CODES; i++) {
      _dynamicLengthTree[i * 2] = 0;
    }
    for (int i = 0; i < D_CODES; i++) {
      _dynamicDistTree[i * 2] = 0;
    }
    for (int i = 0; i < BL_CODES; i++) {
      _bitLengthTree[i * 2] = 0;
    }

    _dynamicLengthTree[END_BLOCK * 2] = 1;
    _optimalLen = _staticLen = 0;
    _lastLit = _matches = 0;
  }

  /**
   * 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).
   */
  void _pqdownheap(Uint16List tree, int k) {
    int v = _heap[k];
    int j = k << 1; // left son of k
    while (j <= _heapLen) {
      // Set j to the smallest of the two sons:
      if (j < _heapLen && _smaller(tree, _heap[j + 1], _heap[j], _depth)) {
        j++;
      }
      // Exit if v is smaller than both sons
      if (_smaller(tree, v, _heap[j], _depth)) {
        break;
      }

      // Exchange v with the smallest son
      _heap[k] = _heap[j]; k = j;
      // And continue down the tree, setting j to the left son of k
      j <<= 1;
    }
    _heap[k] = v;
  }

  static bool _smaller(Uint16List tree, int n, int m,
                       Uint8List depth) {
    return (tree[n * 2] < tree[m * 2] ||
            (tree[n * 2] == tree[m * 2] && depth[n] <= depth[m]));
  }

  /**
   * Scan a literal or distance tree to determine the frequencies of the codes
   * in the bit length tree.
   */
  void _scanTree(Uint16List tree, int max_code) {
    int n; // iterates over all tree elements
    int prevlen = - 1; // last emitted length
    int curlen; // length of current code
    int nextlen = tree[0 * 2 + 1]; // length of next code
    int count = 0; // repeat count of the current code
    int max_count = 7; // max repeat count
    int min_count = 4; // min repeat count

    if (nextlen == 0) {
      max_count = 138; min_count = 3;
    }
    tree[(max_code + 1) * 2 + 1] = 0xffff; // guard

    for (n = 0; n <= max_code; n++) {
      curlen = nextlen; nextlen = tree[(n + 1) * 2 + 1];
      if (++count < max_count && curlen == nextlen) {
        continue;
      } else if (count < min_count) {
        _bitLengthTree[curlen * 2] = (_bitLengthTree[curlen * 2] + count);
      } else if (curlen != 0) {
        if (curlen != prevlen) {
          _bitLengthTree[curlen * 2]++;
        }
        _bitLengthTree[REP_3_6 * 2]++;
      } else if (count <= 10) {
        _bitLengthTree[REPZ_3_10 * 2]++;
      } else {
        _bitLengthTree[REPZ_11_138 * 2]++;
      }
      count = 0; prevlen = curlen;
      if (nextlen == 0) {
        max_count = 138; min_count = 3;
      } else if (curlen == nextlen) {
        max_count = 6; min_count = 3;
      } else {
        max_count = 7; min_count = 4;
      }
    }
  }

  // Construct the Huffman tree for the bit lengths and return the index in
  // bl_order of the last bit length code to send.
  int _buildBitLengthTree() {
    int max_blindex; // index of last bit length code of non zero freq

    // Determine the bit length frequencies for literal and distance trees
    _scanTree(_dynamicLengthTree, _lDesc.maxCode);
    _scanTree(_dynamicDistTree, _dDesc.maxCode);

    // Build the bit length tree:
    _blDesc._buildTree(this);
    // 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.)
    for (max_blindex = BL_CODES - 1; max_blindex >= 3; max_blindex--) {
      if (_bitLengthTree[_HuffmanTree.BL_ORDER[max_blindex] * 2 + 1] != 0) {
        break;
      }
    }

    // Update opt_len to include the bit length tree and counts
    _optimalLen += 3 * (max_blindex + 1) + 5 + 5 + 4;

    return max_blindex;
  }


  /**
   * 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.
   */
  void _sendAllTrees(int lcodes, int dcodes, int blcodes) {
    int rank; // index in bl_order

    _sendBits(lcodes - 257, 5); // not +255 as stated in appnote.txt
    _sendBits(dcodes - 1, 5);
    _sendBits(blcodes - 4, 4); // not -3 as stated in appnote.txt
    for (rank = 0; rank < blcodes; rank++) {
      _sendBits(_bitLengthTree[_HuffmanTree.BL_ORDER[rank] * 2 + 1], 3);
    }
    _sendTree(_dynamicLengthTree, lcodes - 1); // literal tree
    _sendTree(_dynamicDistTree, dcodes - 1); // distance tree
  }

  /**
   * Send a literal or distance tree in compressed form, using the codes in
   * bl_tree.
   */
  void _sendTree(Uint16List tree, int max_code) {
    int n; // iterates over all tree elements
    int prevlen = - 1; // last emitted length
    int curlen; // length of current code
    int nextlen = tree[0 * 2 + 1]; // length of next code
    int count = 0; // repeat count of the current code
    int max_count = 7; // max repeat count
    int min_count = 4; // min repeat count

    if (nextlen == 0) {
      max_count = 138; min_count = 3;
    }

    for (n = 0; n <= max_code; n++) {
      curlen = nextlen; nextlen = tree[(n + 1) * 2 + 1];
      if (++count < max_count && curlen == nextlen) {
        continue;
      } else if (count < min_count) {
        do {
          _sendCode(curlen, _bitLengthTree);
        } while (--count != 0);
      } else if (curlen != 0) {
        if (curlen != prevlen) {
          _sendCode(curlen, _bitLengthTree);
          count--;
        }
        _sendCode(REP_3_6, _bitLengthTree);
        _sendBits(count - 3, 2);
      } else if (count <= 10) {
        _sendCode(REPZ_3_10, _bitLengthTree);
        _sendBits(count - 3, 3);
      } else {
        _sendCode(REPZ_11_138, _bitLengthTree);
        _sendBits(count - 11, 7);
      }
      count = 0;
      prevlen = curlen;
      if (nextlen == 0) {
        max_count = 138;
        min_count = 3;
      } else if (curlen == nextlen) {
        max_count = 6;
        min_count = 3;
      } else {
        max_count = 7;
        min_count = 4;
      }
    }
  }

  /**
   * Output a byte on the stream.
   * IN assertion: there is enough room in pending_buf.
   */
  void _putBytes(Uint8List p, int start, int len) {
    if (len == 0) {
      return;
    }
    _pendingBuffer.setRange(_pending, _pending + len, p, start);
    _pending += len;
  }

  void _putByte(int c) {
    _pendingBuffer[_pending++] = c;
  }

  void _putShort(int w) {
    _putByte((w));
    _putByte((_rshift(w, 8)));
  }

  void _sendCode(int c, List<int> tree) {
    _sendBits((tree[c * 2] & 0xffff), (tree[c * 2 + 1] & 0xffff));
  }

  void _sendBits(int value_Renamed, int length) {
    int len = length;
    if (_numValidBits > BUF_SIZE - len) {
      int val = value_Renamed;
      _bitBuffer = (_bitBuffer | (((val << _numValidBits) & 0xffff)));
      _putShort(_bitBuffer);
      _bitBuffer = (_rshift(val, (BUF_SIZE - _numValidBits)));
      _numValidBits += len - BUF_SIZE;
    } else {
      _bitBuffer = (_bitBuffer | ((((value_Renamed) << _numValidBits) & 0xffff)));
      _numValidBits += len;
    }
  }

  /**
   * Send one empty static block to give enough lookahead for inflate.
   * This takes 10 bits, of which 7 may remain in the bit buffer.
   * The current inflate code requires 9 bits of lookahead. If the
   * last two codes for the previous block (real code plus EOB) were coded
   * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode
   * the last real code. In this case we send two empty static blocks instead
   * of one. (There are no problems if the previous block is stored or fixed.)
   * To simplify the code, we assume the worst case of last real code encoded
   * on one bit only.
   */
  void _trAlign() {
    _sendBits(STATIC_TREES << 1, 3);
    _sendCode(END_BLOCK, _StaticTree.STATIC_LTREE);

    biFlush();

    // Of the 10 bits for the empty block, we have already sent
    // (10 - bi_valid) bits. The lookahead for the last real code (before
    // the EOB of the previous block) was thus at least one plus the length
    // of the EOB plus what we have just sent of the empty static block.
    if (1 + _lastEOBLen + 10 - _numValidBits < 9) {
      _sendBits(STATIC_TREES << 1, 3);
      _sendCode(END_BLOCK, _StaticTree.STATIC_LTREE);
      biFlush();
    }

    _lastEOBLen = 7;
  }


  /**
   * Save the match info and tally the frequency counts. Return true if
   * the current block must be flushed.
   */
  bool _trTally(int dist, int lc) {
    _pendingBuffer[_dbuf + _lastLit * 2] = (_rshift(dist, 8));
    _pendingBuffer[_dbuf + _lastLit * 2 + 1] = dist;

    _pendingBuffer[_lbuf + _lastLit] = lc;
    _lastLit++;

    if (dist == 0) {
      // lc is the unmatched char
      _dynamicLengthTree[lc * 2]++;
    } else {
      _matches++;
      // Here, lc is the match length - MIN_MATCH
      dist--; // dist = match distance - 1
      _dynamicLengthTree[(_HuffmanTree.LENGTH_CODE[lc] + LITERALS + 1) * 2]++;
      _dynamicDistTree[_HuffmanTree._dCode(dist) * 2]++;
    }

    if ((_lastLit & 0x1fff) == 0 && _level > 2) {
      // Compute an upper bound for the compressed length
      int out_length = _lastLit * 8;
      int in_length = _strStart - _blockStart;
      int dcode;
      for (dcode = 0; dcode < D_CODES; dcode++) {
        out_length = (out_length + _dynamicDistTree[dcode * 2] * (5 + _HuffmanTree.EXTRA_D_BITS[dcode]));
      }
      out_length = _rshift(out_length, 3);
      if ((_matches < (_lastLit / 2)) && out_length < in_length / 2) {
        return true;
      }
    }

    return (_lastLit == _litBufferSize - 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.
  }

  /**
   * Send the block data compressed using the given Huffman trees
   */
  void _compressBlock(List<int> ltree, List<int> dtree) {
    int dist; // distance of matched string
    int lc; // match length or unmatched char (if dist == 0)
    int lx = 0; // running index in l_buf
    int code; // the code to send
    int extra; // number of extra bits to send

    if (_lastLit != 0) {
      do {
        dist = ((_pendingBuffer[_dbuf + lx * 2] << 8) & 0xff00) |
                (_pendingBuffer[_dbuf + lx * 2 + 1] & 0xff);
        lc = (_pendingBuffer[_lbuf + lx]) & 0xff;
        lx++;

        if (dist == 0) {
          _sendCode(lc, ltree); // send a literal byte
        } else {
          // Here, lc is the match length - MIN_MATCH
          code = _HuffmanTree.LENGTH_CODE[lc];

          _sendCode(code + LITERALS + 1, ltree); // send the length code
          extra = _HuffmanTree.EXTRA_L_BITS[code];
          if (extra != 0) {
            lc -= _HuffmanTree.BASE_LENGTH[code];
            _sendBits(lc, extra); // send the extra length bits
          }
          dist--; // dist is now the match distance - 1
          code = _HuffmanTree._dCode(dist);

          _sendCode(code, dtree); // send the distance code
          extra = _HuffmanTree.EXTRA_D_BITS[code];
          if (extra != 0) {
            dist -= _HuffmanTree.BASE_DIST[code];
            _sendBits(dist, extra); // send the extra distance bits
          }
        } // literal or match pair ?

        // Check that the overlay between pending_buf and d_buf+l_buf is ok:
      } while (lx < _lastLit);
    }

    _sendCode(END_BLOCK, ltree);
    _lastEOBLen = ltree[END_BLOCK * 2 + 1];
  }

  /**
   * Set the data type to ASCII or BINARY, using a crude approximation:
   * binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise.
   * IN assertion: the fields freq of dyn_ltree are set and the total of all
   * frequencies does not exceed 64K (to fit in an int on 16 bit machines).
   */
  void setDataType() {
    int n = 0;
    int ascii_freq = 0;
    int bin_freq = 0;
    while (n < 7) {
      bin_freq += _dynamicLengthTree[n * 2]; n++;
    }
    while (n < 128) {
      ascii_freq += _dynamicLengthTree[n * 2]; n++;
    }
    while (n < LITERALS) {
      bin_freq += _dynamicLengthTree[n * 2]; n++;
    }
    _dataType = (bin_freq > (_rshift(ascii_freq, 2)) ?
                Z_BINARY : Z_ASCII);
  }

  /**
   * Flush the bit buffer, keeping at most 7 bits in it.
   */
  void biFlush() {
    if (_numValidBits == 16) {
      _putShort(_bitBuffer);
      _bitBuffer = 0;
      _numValidBits = 0;
    } else if (_numValidBits >= 8) {
      _putByte(_bitBuffer);
      _bitBuffer = (_rshift(_bitBuffer, 8));
      _numValidBits -= 8;
    }
  }

  /**
   * Flush the bit buffer and align the output on a byte boundary
   */
  void _biWindup() {
    if (_numValidBits > 8) {
      _putShort(_bitBuffer);
    } else if (_numValidBits > 0) {
      _putByte(_bitBuffer);
    }
    _bitBuffer = 0;
    _numValidBits = 0;
  }

  /**
   * Copy a stored block, storing first the length and its
   * one's complement if requested.
   */
  void _copyBlock(int buf, int len, bool header) {
    _biWindup(); // align on byte boundary
    _lastEOBLen = 8; // enough lookahead for inflate

    if (header) {
      _putShort(len);
      _putShort((~len + 0x10000) & 0xffff);
    }

    _putBytes(_window, buf, len);
  }

  void _flushBlockOnly(bool eof) {
    _trFlushBlock(_blockStart >= 0 ? _blockStart : -1,
                  _strStart - _blockStart, eof);
    _blockStart = _strStart;
    _flushPending();
  }

  /**
   * 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.
   */
  int _deflateStored(int 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:
    int maxBlockSize = 0xffff;

    if (maxBlockSize > _pendingBufferSize - 5) {
      maxBlockSize = _pendingBufferSize - 5;
    }

    // Copy as much as possible from input to output:
    while (true) {
      // Fill the window as much as possible:
      if (_lookAhead <= 1) {
        _fillWindow();

        if (_lookAhead == 0 && flush == NO_FLUSH) {
          return NEED_MORE;
        }

        if (_lookAhead == 0) {
          break; // flush the current block
        }
      }

      _strStart += _lookAhead;
      _lookAhead = 0;

      // Emit a stored block if pendingBuffer will be full:
      int maxStart = _blockStart + maxBlockSize;

      if (_strStart >= maxStart) {
        _lookAhead = (_strStart - maxStart);
        _strStart = maxStart;
        _flushBlockOnly(false);
      }

      // Flush if we may have to slide, otherwise block_start may become
      // negative and the data will be gone:
      if (_strStart - _blockStart >= _windowSize - MIN_LOOKAHEAD) {
        _flushBlockOnly(false);
      }
    }

    _flushBlockOnly(flush == FINISH);

    return (flush == FINISH) ? FINISH_DONE : BLOCK_DONE;
  }

  /**
   * Send a stored block
   */
  void _trStoredBlock(int buf, int storedLen, bool eof) {
    _sendBits((STORED_BLOCK << 1) + (eof ? 1 : 0), 3); // send block type
    _copyBlock(buf, storedLen, true); // with header
  }

  /**
   * Determine the best encoding for the current block: dynamic trees, static
   * trees or store, and output the encoded block to the zip file.
   */
  void _trFlushBlock(int buf, int storedLen, bool eof) {
    int optLenb;
    int staticLenb;
    int max_blindex = 0; // index of last bit length code of non zero freq

    // Build the Huffman trees unless a stored block is forced
    if (_level > 0) {
      // Check if the file is ascii or binary
      if (_dataType == Z_UNKNOWN) {
        setDataType();
      }

      // Construct the literal and distance trees
      _lDesc._buildTree(this);

      _dDesc._buildTree(this);

      // 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 = _buildBitLengthTree();

      // Determine the best encoding. Compute first the block length in bytes
      optLenb = _rshift((_optimalLen + 3 + 7), 3);
      staticLenb = _rshift((_staticLen + 3 + 7), 3);

      if (staticLenb <= optLenb) {
        optLenb = staticLenb;
      }
    } else {
      optLenb = staticLenb = storedLen + 5; // force a stored block
    }

    if (storedLen + 4 <= optLenb && buf != -1) {
      // 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.
      _trStoredBlock(buf, storedLen, eof);
    } else if (staticLenb == optLenb) {
      _sendBits((STATIC_TREES << 1) + (eof ? 1 : 0), 3);
      _compressBlock(_StaticTree.STATIC_LTREE, _StaticTree.STATIC_DTREE);
    } else {
      _sendBits((DYN_TREES << 1) + (eof ? 1 : 0), 3);
      _sendAllTrees(_lDesc.maxCode + 1, _dDesc.maxCode + 1, max_blindex + 1);
      _compressBlock(_dynamicLengthTree, _dynamicDistTree);
    }

    // The above check is made mod 2^32, for files larger than 512 MB
    // and uLong implemented on 32 bits.

    _initBlock();

    if (eof) {
      _biWindup();
    }
  }

  /**
   * 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).
   */
  void _fillWindow() {
    do {
      // Amount of free space at the end of the window.
      int more = (_actualWindowSize - _lookAhead - _strStart);

      // Deal with 64K limit:
      if (more == 0 && _strStart == 0 && _lookAhead == 0) {
        more = _windowSize;
      } else if (_strStart >= _windowSize + _windowSize - MIN_LOOKAHEAD) {
        // 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.

        _window.setRange(0, _windowSize, _window, _windowSize);

        _matchStart -= _windowSize;
        _strStart -= _windowSize; // we now have strstart >= MAX_DIST
        _blockStart -= _windowSize;

        // 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.)

        int n = _hashSize;
        int p = n;
        do {
          int m = (_head[--p] & 0xffff);
          _head[p] = (m >= _windowSize?(m - _windowSize) : 0);
        } while (--n != 0);

        n = _windowSize;
        p = n;
        do {
          int m = (_prev[--p] & 0xffff);
          _prev[p] = (m >= _windowSize ? (m - _windowSize) : 0);
          // If n is not on any hash chain, prev[n] is garbage but
          // its value will never be used.
        } while (--n != 0);

        more += _windowSize;
      }

      if (_input.isEOS) {
        return;
      }

      // 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.

      int n = _readBuf(_window, _strStart + _lookAhead, more);
      _lookAhead += n;

      // Initialize the hash value now that we have some input:
      if (_lookAhead >= MIN_MATCH) {
        _insertHash = _window[_strStart] & 0xff;
        _insertHash = (((_insertHash) << _hashShift) ^
                 (_window[_strStart + 1] & 0xff)) & _hashMask;
      }

      // 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.
    } while (_lookAhead < MIN_LOOKAHEAD && !_input.isEOS);
  }

  /**
   * 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.
   */
  int _deflateFast(int flush) {
    int hash_head = 0; // head of the hash chain
    bool bflush; // set if current block must be flushed

    while (true) {
      // 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 (_lookAhead < MIN_LOOKAHEAD) {
        _fillWindow();
        if (_lookAhead < MIN_LOOKAHEAD && flush == NO_FLUSH) {
          return NEED_MORE;
        }
        if (_lookAhead == 0) {
          break; // flush the current block
        }
      }

      // Insert the string window[strstart .. strstart+2] in the
      // dictionary, and set hash_head to the head of the hash chain:
      if (_lookAhead >= MIN_MATCH) {
        _insertHash = (((_insertHash) << _hashShift) ^
                 (_window[(_strStart) + (MIN_MATCH - 1)] & 0xff)) & _hashMask;

        hash_head = (_head[_insertHash] & 0xffff);
        _prev[_strStart & _windowMask] = _head[_insertHash];
        _head[_insertHash] = _strStart;
      }

      // Find the longest match, discarding those <= prev_length.
      // At this point we have always match_length < MIN_MATCH

      if (hash_head != 0 &&
          ((_strStart - hash_head) & 0xffff) <= _windowSize - MIN_LOOKAHEAD) {
        // 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).
        if (_strategy != Z_HUFFMAN_ONLY) {
          _matchLength = _longestMatch(hash_head);
        }

        // longest_match() sets match_start
      }

      if (_matchLength >= MIN_MATCH) {
        bflush = _trTally(_strStart - _matchStart, _matchLength - MIN_MATCH);

        _lookAhead -= _matchLength;

        // Insert new strings in the hash table only if the match length
        // is not too large. This saves time but degrades compression.
        if (_matchLength <= _config.maxLazy && _lookAhead >= MIN_MATCH) {
          _matchLength--; // string at strstart already in hash table
          do {
            _strStart++;

            _insertHash = ((_insertHash << _hashShift) ^
                           (_window[(_strStart) + (MIN_MATCH - 1)] & 0xff)) &
                           _hashMask;

            hash_head = (_head[_insertHash] & 0xffff);
            _prev[_strStart & _windowMask] = _head[_insertHash];
            _head[_insertHash] = _strStart;

            // strstart never exceeds WSIZE-MAX_MATCH, so there are
            // always MIN_MATCH bytes ahead.
          } while (--_matchLength != 0);
          _strStart++;
        } else {
          _strStart += _matchLength;
          _matchLength = 0;
          _insertHash = _window[_strStart] & 0xff;

          _insertHash = (((_insertHash) << _hashShift) ^
                         (_window[_strStart + 1] & 0xff)) & _hashMask;
          // If lookahead < MIN_MATCH, ins_h is garbage, but it does not
          // matter since it will be recomputed at next deflate call.
        }
      } else {
        // No match, output a literal byte

        bflush = _trTally(0, _window[_strStart] & 0xff);
        _lookAhead--;
        _strStart++;
      }

      if (bflush) {
        _flushBlockOnly(false);
      }
    }

    _flushBlockOnly(flush == FINISH);

    return flush == FINISH ? FINISH_DONE : BLOCK_DONE;
  }

  /**
   * 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.
   */
  int _deflateSlow(int flush) {
    int hash_head = 0; // head of hash chain
    bool bflush; // set if current block must be flushed

    // Process the input block.
    while (true) {
      // 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 (_lookAhead < MIN_LOOKAHEAD) {
        _fillWindow();

        if (_lookAhead < MIN_LOOKAHEAD && flush == NO_FLUSH) {
          return NEED_MORE;
        }

        if (_lookAhead == 0) {
          break; // flush the current block
        }
      }

      // Insert the string window[strstart .. strstart+2] in the
      // dictionary, and set hash_head to the head of the hash chain:

      if (_lookAhead >= MIN_MATCH) {
        _insertHash = (((_insertHash) << _hashShift) ^
                 (_window[(_strStart) + (MIN_MATCH - 1)] & 0xff)) & _hashMask;
        hash_head = (_head[_insertHash] & 0xffff);
        _prev[_strStart & _windowMask] = _head[_insertHash];
        _head[_insertHash] = _strStart;
      }

      // Find the longest match, discarding those <= prev_length.
      _prevLength = _matchLength;
      _prevMatch = _matchStart;
      _matchLength = MIN_MATCH - 1;

      if (hash_head != 0 && _prevLength < _config.maxLazy &&
          ((_strStart - hash_head) & 0xffff) <= _windowSize - MIN_LOOKAHEAD) {
        // 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).

        if (_strategy != Z_HUFFMAN_ONLY) {
          _matchLength = _longestMatch(hash_head);
        }
        // longest_match() sets match_start

        if (_matchLength <= 5 &&
            (_strategy == Z_FILTERED ||
             (_matchLength == MIN_MATCH && _strStart - _matchStart > 4096))) {
          // If prev_match is also MIN_MATCH, match_start is garbage
          // but we will ignore the current match anyway.
          _matchLength = MIN_MATCH - 1;
        }
      }

      // If there was a match at the previous step and the current
      // match is not better, output the previous match:
      if (_prevLength >= MIN_MATCH && _matchLength <= _prevLength) {
        int max_insert = _strStart + _lookAhead - MIN_MATCH;
        // Do not insert strings in hash table beyond this.

        bflush = _trTally(_strStart - 1 - _prevMatch, _prevLength - 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.
        _lookAhead -= (_prevLength - 1);
        _prevLength -= 2;

        do {
          if (++_strStart <= max_insert) {
            _insertHash = (((_insertHash) << _hashShift) ^
                     (_window[(_strStart) + (MIN_MATCH - 1)] & 0xff)) & _hashMask;
            hash_head = (_head[_insertHash] & 0xffff);
            _prev[_strStart & _windowMask] = _head[_insertHash];
            _head[_insertHash] = _strStart;
          }
        } while (--_prevLength != 0);

        _matchAvailable = 0;
        _matchLength = MIN_MATCH - 1;
        _strStart++;

        if (bflush) {
          _flushBlockOnly(false);
        }
      } else if (_matchAvailable != 0) {

        // 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.

        bflush = _trTally(0, _window[_strStart - 1] & 0xff);

        if (bflush) {
          _flushBlockOnly(false);
        }
        _strStart++;
        _lookAhead--;
      } else {
        // There is no previous match to compare with, wait for
        // the next step to decide.
        _matchAvailable = 1;
        _strStart++;
        _lookAhead--;
      }
    }

    if (_matchAvailable != 0) {
      bflush = _trTally(0, _window[_strStart - 1] & 0xff);
      _matchAvailable = 0;
    }
    _flushBlockOnly(flush == FINISH);

    return flush == FINISH ? FINISH_DONE : BLOCK_DONE;
  }

  int _longestMatch(int cur_match) {
    int chain_length = _config.maxChain; // max hash chain length
    int scan = _strStart; // current string
    int match; // matched string
    int len; // length of current match
    int best_len = _prevLength; // best match length so far
    int limit = _strStart > (_windowSize - MIN_LOOKAHEAD) ?
                _strStart - (_windowSize - MIN_LOOKAHEAD) : 0;
    int nice_match = _config.niceLength;

    // Stop when cur_match becomes <= limit. To simplify the code,
    // we prevent matches with the string of window index 0.

    int wmask = _windowMask;

    int strend = _strStart + MAX_MATCH;
    int scan_end1 = _window[scan + best_len - 1];
    int 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.

    // Do not waste too much time if we already have a good match:
    if (_prevLength >= _config.goodLength) {
      chain_length >>= 2;
    }

    // Do not look for matches beyond the end of the input. This is necessary
    // to make deflate deterministic.
    if (nice_match > _lookAhead) {
      nice_match = _lookAhead;
    }

    do {
      match = cur_match;

      // Skip to next match if the match length cannot increase
      // or if the match length is less than 2:
      if (_window[match + best_len] != scan_end ||
          _window[match + best_len - 1] != scan_end1 ||
          _window[match] != _window[scan] ||
          _window[++match] != _window[scan + 1]) {
        continue;
      }

      // 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 += 2;
      match++;

      // We check for insufficient lookahead only every 8th comparison;
      // the 256th check will be made at strstart+258.
      do {
      } while (_window[++scan] == _window[++match] &&
               _window[++scan] == _window[++match] &&
               _window[++scan] == _window[++match] &&
               _window[++scan] == _window[++match] &&
               _window[++scan] == _window[++match] &&
               _window[++scan] == _window[++match] &&
               _window[++scan] == _window[++match] &&
               _window[++scan] == _window[++match] &&
               scan < strend);

      len = MAX_MATCH - (strend - scan);
      scan = strend - MAX_MATCH;

      if (len > best_len) {
        _matchStart = cur_match;
        best_len = len;
        if (len >= nice_match) {
          break;
        }
        scan_end1 = _window[scan + best_len - 1];
        scan_end = _window[scan + best_len];
      }
    } while ((cur_match = (_prev[cur_match & wmask] & 0xffff)) > limit &&
              --chain_length != 0);

    if (best_len <= _lookAhead) {
      return best_len;
    }

    return _lookAhead;
  }

  /**
   * 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->next_in buffer and copying from it.
   * (See also flush_pending()).
   */
  int _readBuf(Uint8List buf, int start, int size) {
    int len = _input.length;

    if (len > size) {
      len = size;
    }

    if (len == 0) {
      return 0;
    }

    InputStream bytes = _input.readBytes(len);
    buf.setRange(start, start + len, bytes.toUint8List());

    return len;
  }

  /**
   * 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.
   */
  void _flushPending() {
    int len = _pending;

    _output.writeBytes(_pendingBuffer, len);

    _pendingOut += len;
    _pending -= len;
    if (_pending == 0) {
      _pendingOut = 0;
    }
  }

  _DeflaterConfig _getConfig(int level) {
    switch (level) {
      //                             good  lazy  nice  chain
      case 0: return new _DeflaterConfig(0, 0, 0, 0, STORED);
      case 1: return new _DeflaterConfig(4, 4, 8, 4, FAST);
      case 2: return new _DeflaterConfig(4, 5, 16, 8, FAST);
      case 3: return new _DeflaterConfig(4, 6, 32, 32, FAST);

      case 4: return new _DeflaterConfig(4, 4, 16, 16, SLOW);
      case 5: return new _DeflaterConfig(8, 16, 32, 32, SLOW);
      case 6: return new _DeflaterConfig(8, 16, 128, 128, SLOW);
      case 7: return new _DeflaterConfig(8, 32, 128, 256, SLOW);
      case 8: return new _DeflaterConfig(32, 128, 258, 1024, SLOW);
      case 9: return new _DeflaterConfig(32, 258, 258, 4096, SLOW);
    }
    return null;
  }

  static const int MAX_MEM_LEVEL = 9;

  static const int Z_DEFAULT_COMPRESSION = - 1;

  /// 32K LZ77 window
  static const int MAX_WBITS = 15;
  static const int DEF_MEM_LEVEL = 8;

  static const int STORED = 0;
  static const int FAST = 1;
  static const int SLOW = 2;
  static _DeflaterConfig _config;

  /// block not completed, need more input or more output
  static const int NEED_MORE = 0;

  /// block flush performed
  static const int BLOCK_DONE = 1;

  /// finish started, need only more output at next deflate
  static const int FINISH_STARTED = 2;

  /// finish done, accept no more input or output
  static const int FINISH_DONE = 3;

  static const int Z_FILTERED = 1;
  static const int Z_HUFFMAN_ONLY = 2;
  static const int Z_DEFAULT_STRATEGY = 0;

  static const int Z_OK = 0;
  static const int Z_STREAM_END = 1;
  static const int Z_NEED_DICT = 2;
  static const int Z_ERRNO = - 1;
  static const int Z_STREAM_ERROR = - 2;
  static const int Z_DATA_ERROR = - 3;
  static const int Z_MEM_ERROR = - 4;
  static const int Z_BUF_ERROR = - 5;
  static const int Z_VERSION_ERROR = - 6;

  static const int INIT_STATE = 42;
  static const int BUSY_STATE = 113;
  static const int FINISH_STATE = 666;

  /// The deflate compression method
  static const int Z_DEFLATED = 8;

  static const int STORED_BLOCK = 0;
  static const int STATIC_TREES = 1;
  static const int DYN_TREES = 2;

  // The three kinds of block type
  static const int Z_BINARY = 0;
  static const int Z_ASCII = 1;
  static const int Z_UNKNOWN = 2;

  static const int BUF_SIZE = 8 * 2;

  /// repeat previous bit length 3-6 times (2 bits of repeat count)
  static const int REP_3_6 = 16;

  /// repeat a zero length 3-10 times  (3 bits of repeat count)
  static const int REPZ_3_10 = 17;

  /// repeat a zero length 11-138 times  (7 bits of repeat count)
  static const int REPZ_11_138 = 18;

  static const int MIN_MATCH = 3;
  static const int MAX_MATCH = 258;
  static const int MIN_LOOKAHEAD = (MAX_MATCH + MIN_MATCH + 1);

  static const int MAX_BITS = 15;
  static const int D_CODES = 30;
  static const int BL_CODES = 19;
  static const int LENGTH_CODES = 29;
  static const int LITERALS = 256;
  static const int L_CODES = (LITERALS + 1 + LENGTH_CODES);
  static const int HEAP_SIZE = (2 * L_CODES + 1);

  static const int END_BLOCK = 256;

  InputStream _input;
  OutputStream _output = new OutputStream();

  int _status;
  /// output still pending
  Uint8List _pendingBuffer;
  /// size of pending_buf
  int _pendingBufferSize;
  /// next pending byte to output to the stream
  int _pendingOut; // ignore: unused_field
  /// nb of bytes in the pending buffer
  int _pending;
  /// UNKNOWN, BINARY or ASCII
  int _dataType;
  /// STORED (for zip only) or DEFLATED
  int _method; // ignore: unused_field
  /// value of flush param for previous deflate call
  int _lastFlush; // ignore: unused_field

  /// LZ77 window size (32K by default)
  int _windowSize;
  /// log2(w_size)  (8..16)
  int _windowBits;
  /// w_size - 1
  int _windowMask;

  /// 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.
  Uint8List _window;

  /// Actual size of window: 2*wSize, except when the user input buffer
  /// is directly used as sliding window.
  int _actualWindowSize;

  /// 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.
  Uint16List _prev;

  /// Heads of the hash chains or NIL.
  Uint16List _head;

  /// hash index of string to be inserted
  int _insertHash;
  /// number of elements in hash table
  int _hashSize;
  /// log2(hash_size)
  int _hashBits;
  /// hash_size-1
  int _hashMask;

  /// 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
  int _hashShift;

  /// Window position at the beginning of the current output block. Gets
  /// negative when the window is moved backwards.
  int _blockStart;

  /// length of best match
  int _matchLength;
  /// previous match
  int _prevMatch;
  /// set if previous match exists
  int _matchAvailable;
  /// start of string to insert
  int _strStart;
  /// start of matching string
  int _matchStart = 0;
  /// number of valid bytes ahead in window
  int _lookAhead;

  /// Length of the best match at previous step. Matches not greater than this
  /// are discarded. This is used in the lazy match evaluation.
  int _prevLength;

  // Insert new strings in the hash table only if the match length is not
  // greater than this length. This saves time but degrades compression.
  // max_insert_length is used only for compression levels <= 3.

  /// compression level (1..9)
  int _level;
  /// favor or force Huffman coding
  int _strategy;

  /// literal and length tree
  Uint16List _dynamicLengthTree;
  /// distance tree
  Uint16List _dynamicDistTree;
  /// Huffman tree for bit lengths
  Uint16List _bitLengthTree;

  /// desc for literal tree
  _HuffmanTree _lDesc = new _HuffmanTree();
  /// desc for distance tree
  _HuffmanTree _dDesc = new _HuffmanTree();
  /// desc for bit length tree
  _HuffmanTree _blDesc = new _HuffmanTree();

  /// number of codes at each bit length for an optimal tree
  Uint16List _bitLengthCount = new Uint16List(MAX_BITS + 1);

  /// heap used to build the Huffman trees
  Uint32List _heap = new Uint32List(2 * L_CODES + 1);

  /// number of elements in the heap
  int _heapLen;
  /// element of largest frequency
  int _heapMax;
  // 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.

  /// Depth of each subtree used as tie breaker for trees of equal frequency
  Uint8List _depth = new Uint8List(2 * L_CODES + 1);

  /// index for literals or lengths
  int _lbuf;

  /// Size of match buffer for literals/lengths.  There are 4 reasons for
  /// limiting lit_bufsize to 64K:
  ///   - frequencies can be kept in 16 bit counters
  ///   - if compression is not successful for the first block, all input
  ///     data is still in the window so we can still emit a stored block even
  ///     when input comes from standard input.  (This can also be done for
  ///     all blocks if lit_bufsize is not greater than 32K.)
  ///   - if compression is not successful for a file smaller than 64K, we can
  ///     even emit a stored file instead of a stored block (saving 5 bytes).
  ///     This is applicable only for zip (not gzip or zlib).
  ///   - creating new Huffman trees less frequently may not provide fast
  ///     adaptation to changes in the input data statistics. (Take for
  ///     example a binary file with poorly compressible code followed by
  ///     a highly compressible string table.) Smaller buffer sizes give
  ///     fast adaptation but have of course the overhead of transmitting
  ///     trees more frequently.
  ///   - I can't count above 4
  int _litBufferSize;

  /// running index in l_buf
  int _lastLit;

  // 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.

  /// index of pendig_buf
  int _dbuf;

  /// bit length of current block with optimal trees
  int _optimalLen;
  /// bit length of current block with static trees
  int _staticLen;
  /// number of string matches in current block
  int _matches;
  /// bit length of EOB code for last block
  int _lastEOBLen;

  /// Output buffer. bits are inserted starting at the bottom (least
  /// significant bits).
  int _bitBuffer;

  /// Number of valid bits in bi_buf.  All bits above the last valid bit
  /// are always zero.
  int _numValidBits;
}

class _DeflaterConfig {
  /// Use a faster search when the previous match is longer than this
  int goodLength;
  /// 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.
  int maxLazy;
  /// Stop searching when current match exceeds this
  int niceLength;
  /// To speed up deflation, hash chains are never searched beyond this
  /// length. A higher limit improves compression ratio but degrades the speed.
  int maxChain;
  /// STORED, FAST, or SLOW
  int function;

  _DeflaterConfig(this.goodLength, this.maxLazy, this.niceLength,
                  this.maxChain, this.function);
}

class _HuffmanTree {
  static const int MAX_BITS = 15;
  static const int BL_CODES = 19;
  static const int D_CODES = 30;
  static const int LITERALS = 256;
  static const int LENGTH_CODES = 29;
  static const int L_CODES = (LITERALS + 1 + LENGTH_CODES);
  static const int HEAP_SIZE = (2 * L_CODES + 1);

  /// Bit length codes must not exceed MAX_BL_BITS bits
  static const int MAX_BL_BITS = 7;

  /// end of block literal code
  static const int END_BLOCK = 256;

  /// repeat previous bit length 3-6 times (2 bits of repeat count)
  static const int REP_3_6 = 16;

  /// repeat a zero length 3-10 times  (3 bits of repeat count)
  static const int REPZ_3_10 = 17;

  /// repeat a zero length 11-138 times  (7 bits of repeat count)
  static const int REPZ_11_138 = 18;

  /// extra bits for each length code
  static const List<int> EXTRA_L_BITS = const [
      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];

  /// extra bits for each distance code
  static const List<int> EXTRA_D_BITS = const [
      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];

  /// extra bits for each bit length code
  static const List<int> EXTRA_BL_BITS = const [
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7];

  static const List<int> BL_ORDER = const [
      16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15];


  /// The lengths of the bit length codes are sent in order of decreasing
  /// probability, to avoid transmitting the lengths for unused bit
  /// length codes.
  static const int BUF_SIZE = 8 * 2;

  /// see definition of array dist_code below
  static const int DIST_CODE_LEN = 512;

  static const List<int> _DIST_CODE = const [
      0, 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];

  static const List<int> LENGTH_CODE = const [
      0, 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];

  static const List<int> BASE_LENGTH = const [
      0, 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];

  static const List<int> BASE_DIST = const [
      0, 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];

  /// the dynamic tree
  Uint16List dynamicTree;
  /// largest code with non zero frequency
  int maxCode;
  /// the corresponding static tree
  _StaticTree staticDesc;

  /**
   * 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.
   */
  void _genBitlen(Deflate s) {
    Uint16List tree = dynamicTree;
    List<int> stree = staticDesc.staticTree;
    List<int> extra = staticDesc.extraBits;
    int base_Renamed = staticDesc.extraBase;
    int max_length = staticDesc.maxLength;
    int h; // heap index
    int n, m; // iterate over the tree elements
    int bits; // bit length
    int xbits; // extra bits
    int f; // frequency
    int overflow = 0; // number of elements with bit length too large

    for (bits = 0; bits <= MAX_BITS; bits++) {
      s._bitLengthCount[bits] = 0;
    }

    // In a first pass, compute the optimal bit lengths (which may
    // overflow in the case of the bit length tree).
    tree[s._heap[s._heapMax] * 2 + 1] = 0; // root of the heap

    for (h = s._heapMax + 1; h < HEAP_SIZE; h++) {
      n = s._heap[h];
      bits = tree[tree[n * 2 + 1] * 2 + 1] + 1;
      if (bits > max_length) {
        bits = max_length;
        overflow++;
      }
      tree[n * 2 + 1] = bits;
      // We overwrite tree[n*2+1] which is no longer needed

      if (n > maxCode) {
        continue; // not a leaf node
      }

      s._bitLengthCount[bits]++;
      xbits = 0;
      if (n >= base_Renamed) {
        xbits = extra[n - base_Renamed];
      }
      f = tree[n * 2];
      s._optimalLen += f * (bits + xbits);
      if (stree != null) {
        s._staticLen += f * (stree[n * 2 + 1] + xbits);
      }
    }
    if (overflow == 0) {
      return ;
    }

    // This happens for example on obj2 and pic of the Calgary corpus
    // Find the first bit length which could increase:
    do {
      bits = max_length - 1;
      while (s._bitLengthCount[bits] == 0) {
        bits--;
      }
      s._bitLengthCount[bits]--; // move one leaf down the tree
      // move one overflow item as its brother
      s._bitLengthCount[bits + 1] = (s._bitLengthCount[bits + 1] + 2);
      s._bitLengthCount[max_length]--;
      // The brother of the overflow item also moves one step up,
      // but this does not affect bl_count[max_length]
      overflow -= 2;
    } while (overflow > 0);

    for (bits = max_length; bits != 0; bits--) {
      n = s._bitLengthCount[bits];
      while (n != 0) {
        m = s._heap[--h];
        if (m > maxCode) {
          continue;
        }
        if (tree[m * 2 + 1] != bits) {
          s._optimalLen = (s._optimalLen + (bits - tree[m * 2 + 1]) * tree[m * 2]);
          tree[m * 2 + 1] = bits;
        }
        n--;
      }
    }
  }

  /**
   * 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.
   */
  void _buildTree(Deflate s) {
    Uint16List tree = dynamicTree;
    List<int> stree = staticDesc.staticTree;
    int elems = staticDesc.numElements;
    int n, m; // iterate over heap elements
    int max_code = - 1; // largest code with non zero frequency
    int node; // new node being created

    // Construct the initial heap, with least frequent element in
    // heap[1]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
    // heap[0] is not used.
    s._heapLen = 0;
    s._heapMax = HEAP_SIZE;

    for (n = 0; n < elems; n++) {
      if (tree[n * 2] != 0) {
        s._heap[++s._heapLen] = max_code = n;
        s._depth[n] = 0;
      } else {
        tree[n * 2 + 1] = 0;
      }
    }

    // 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._heapLen < 2) {
      node = s._heap[++s._heapLen] = (max_code < 2?++max_code:0);
      tree[node * 2] = 1;
      s._depth[node] = 0;
      s._optimalLen--;
      if (stree != null) {
        s._staticLen -= stree[node * 2 + 1];
      }
      // node is 0 or 1 so it does not have extra bits
    }
    this.maxCode = max_code;

    // The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
    // establish sub-heaps of increasing lengths:

    for (n = s._heapLen ~/ 2; n >= 1; n--) {
      s._pqdownheap(tree, n);
    }

    // Construct the Huffman tree by repeatedly combining the least two
    // frequent nodes.

    node = elems; // next node of the tree
    do {
      // n = node of least frequency
      n = s._heap[1];
      s._heap[1] = s._heap[s._heapLen--];
      s._pqdownheap(tree, 1);
      m = s._heap[1]; // m = node of next least frequency

      s._heap[--s._heapMax] = n; // keep the nodes sorted by frequency
      s._heap[--s._heapMax] = m;

      // Create a new node father of n and m
      tree[node * 2] = (tree[n * 2] + tree[m * 2]);
      s._depth[node] = (_max(s._depth[n], s._depth[m]) + 1);
      tree[n * 2 + 1] = tree[m * 2 + 1] = node;

      // and insert the new node in the heap
      s._heap[1] = node++;
      s._pqdownheap(tree, 1);
    } while (s._heapLen >= 2);

    s._heap[--s._heapMax] = s._heap[1];

    // At this point, the fields freq and dad are set. We can now
    // generate the bit lengths.

    _genBitlen(s);

    // The field len is now set, we can generate the bit codes
    _genCodes(tree, max_code, s._bitLengthCount);
  }

  static int _max(int a, int b) => a > b ? a : b;

  /**
   * 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.
   */
  static void  _genCodes(Uint16List tree, int max_code, Uint16List bl_count) {
    Uint16List next_code = new Uint16List(MAX_BITS + 1);
    int code = 0; // running code value
    int bits; // bit index
    int n; // code index

    // The distribution counts are first used to generate the code values
    // without bit reversal.
    for (bits = 1; bits <= MAX_BITS; bits++) {
      next_code[bits] = code = ((code + bl_count[bits - 1]) << 1);
    }

    for (n = 0; n <= max_code; n++) {
      int len = tree[n * 2 + 1];
      if (len == 0) {
        continue;
      }

      // Now reverse the bits
      tree[n * 2] = (_reverseBits(next_code[len]++, len));
    }
  }

  /**
   * Reverse the first len bits of a code, using straightforward code (a faster
   * method would use a table)
   * IN assertion: 1 <= len <= 15
   */
  static int _reverseBits(int code, int len) {
    int res = 0;
    do {
      res |= code & 1;
      code = _rshift(code, 1);
      res <<= 1;
    } while (--len > 0);
    return _rshift(res, 1);
  }

  /**
   * 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.
   */
  static int _dCode(int dist) {
    return ((dist) < 256 ? _DIST_CODE[dist] :
           _DIST_CODE[256 + (_rshift((dist), 7))]);
  }
}

class _StaticTree {
  static const int MAX_BITS = 15;

  static const int BL_CODES = 19;
  static const int D_CODES = 30;
  static const int LITERALS = 256;
  static const int LENGTH_CODES = 29;
  static const int L_CODES = (LITERALS + 1 + LENGTH_CODES);

  // Bit length codes must not exceed MAX_BL_BITS bits
  static const int MAX_BL_BITS = 7;

  static const List<int> STATIC_LTREE = const [
      12, 8, 140, 8, 76, 8, 204, 8, 44, 8, 172, 8, 108, 8, 236, 8, 28, 8, 156,
      8, 92, 8, 220, 8, 60, 8, 188, 8, 124, 8, 252, 8, 2, 8, 130, 8, 66, 8, 194,
      8, 34, 8, 162, 8, 98, 8, 226, 8, 18, 8, 146, 8, 82, 8, 210, 8, 50, 8, 178,
      8, 114, 8, 242, 8, 10, 8, 138, 8, 74, 8, 202, 8, 42, 8, 170, 8, 106, 8,
      234, 8, 26, 8, 154, 8, 90, 8, 218, 8, 58, 8, 186, 8, 122, 8, 250, 8, 6, 8,
      134, 8, 70, 8, 198, 8, 38, 8, 166, 8, 102, 8, 230, 8, 22, 8, 150, 8, 86,
      8, 214, 8, 54, 8, 182, 8, 118, 8, 246, 8, 14, 8, 142, 8, 78, 8, 206, 8,
      46, 8, 174, 8, 110, 8, 238, 8, 30, 8, 158, 8, 94, 8, 222, 8, 62, 8, 190,
      8, 126, 8, 254, 8, 1, 8, 129, 8, 65, 8, 193, 8, 33, 8, 161, 8, 97, 8,
      225, 8, 17, 8, 145, 8, 81, 8, 209, 8, 49, 8, 177, 8, 113, 8, 241, 8, 9,
      8, 137, 8, 73, 8, 201, 8, 41, 8, 169, 8, 105, 8, 233, 8, 25, 8, 153, 8,
      89, 8, 217, 8, 57, 8, 185, 8, 121, 8, 249, 8, 5, 8, 133, 8, 69, 8, 197,
      8, 37, 8, 165, 8, 101, 8, 229, 8, 21, 8, 149, 8, 85, 8, 213, 8, 53, 8,
      181, 8, 117, 8, 245, 8, 13, 8, 141, 8, 77, 8, 205, 8, 45, 8, 173, 8, 109,
      8, 237, 8, 29, 8, 157, 8, 93, 8, 221, 8, 61, 8, 189, 8, 125, 8, 253, 8,
      19, 9, 275, 9, 147, 9, 403, 9, 83, 9, 339, 9, 211, 9, 467, 9, 51, 9, 307,
      9, 179, 9, 435, 9, 115, 9, 371, 9, 243, 9, 499, 9, 11, 9, 267, 9, 139, 9,
      395, 9, 75, 9, 331, 9, 203, 9, 459, 9, 43, 9, 299, 9, 171, 9, 427, 9, 107,
      9, 363, 9, 235, 9, 491, 9, 27, 9, 283, 9, 155, 9, 411, 9, 91, 9, 347, 9,
      219, 9, 475, 9, 59, 9, 315, 9, 187, 9, 443, 9, 123, 9, 379, 9, 251, 9,
      507, 9, 7, 9, 263, 9, 135, 9, 391, 9, 71, 9, 327, 9, 199, 9, 455, 9, 39,
      9, 295, 9, 167, 9, 423, 9, 103, 9, 359, 9, 231, 9, 487, 9, 23, 9, 279, 9,
      151, 9, 407, 9, 87, 9, 343, 9, 215, 9, 471, 9, 55, 9, 311, 9, 183, 9, 439,
      9, 119, 9, 375, 9, 247, 9, 503, 9, 15, 9, 271, 9, 143, 9, 399, 9, 79, 9,
      335, 9, 207, 9, 463, 9, 47, 9, 303, 9, 175, 9, 431, 9, 111, 9, 367, 9,
      239, 9, 495, 9, 31, 9, 287, 9, 159, 9, 415, 9, 95, 9, 351, 9, 223, 9, 479,
      9, 63, 9, 319, 9, 191, 9, 447, 9, 127, 9, 383, 9, 255, 9, 511, 9, 0, 7,
      64, 7, 32, 7, 96, 7, 16, 7, 80, 7, 48, 7, 112, 7, 8, 7, 72, 7, 40, 7, 104,
      7, 24, 7, 88, 7, 56, 7, 120, 7, 4, 7, 68, 7, 36, 7, 100, 7, 20, 7, 84, 7,
      52, 7, 116, 7, 3, 8, 131, 8, 67, 8, 195, 8, 35, 8, 163, 8, 99, 8, 227, 8];

  static const List<int> STATIC_DTREE = const [
      0, 5, 16, 5, 8, 5, 24, 5, 4, 5, 20, 5, 12, 5, 28, 5, 2, 5, 18, 5, 10, 5,
      26, 5, 6, 5, 22, 5, 14, 5, 30, 5, 1, 5, 17, 5, 9, 5, 25, 5, 5, 5, 21, 5,
      13, 5, 29, 5, 3, 5, 19, 5, 11, 5, 27, 5, 7, 5, 23, 5];

  static _StaticTree staticLDesc =
      new _StaticTree(STATIC_LTREE, _HuffmanTree.EXTRA_L_BITS, LITERALS + 1,
                      L_CODES, MAX_BITS);

  static _StaticTree staticDDesc =
      new _StaticTree(STATIC_DTREE, _HuffmanTree.EXTRA_D_BITS, 0, D_CODES, MAX_BITS);

  static _StaticTree staticBlDesc =
      new _StaticTree(null, _HuffmanTree.EXTRA_BL_BITS, 0, BL_CODES, MAX_BL_BITS);

  List<int> staticTree; // static tree or null
  List<int> extraBits; // extra bits for each code or null
  int extraBase; // base index for extra_bits
  int numElements; // max number of elements in the tree
  int maxLength; // max bit length for the codes

  _StaticTree(this.staticTree, this.extraBits, this.extraBase,
             this.numElements, this.maxLength);
}

/**
 * Performs an unsigned bitwise right shift with the specified number
 */
int _rshift(int number, int bits) {
  if ( number >= 0) {
    return number >> bits;
  } else {
    int nbits = (~bits + 0x10000) & 0xffff;
    return (number >> bits) + (2 << nbits);
  }
}