import 'dart:typed_data';
import 'bzip2/bzip2.dart';
import 'bzip2/bz2_bit_writer.dart';
import 'util/archive_exception.dart';
import 'util/byte_order.dart';
import 'util/input_stream.dart';
import 'util/output_stream.dart';

/// Compress data using the BZip2 format.
/// Derived from libbzip2 (http://www.bzip.org).
class BZip2Encoder {
  List<int> encode(List<int> data) {
    input = InputStream(data, byteOrder: BIG_ENDIAN);
    final output = OutputStream(byteOrder: BIG_ENDIAN);

    bw = Bz2BitWriter(output);

    final blockSize100k = 9;

    bw.writeBytes(BZip2.bzhSignature);
    bw.writeByte(BZip2.hdr0 + blockSize100k);

    _nblockMax = 100000 * blockSize100k - 19;
    _workFactor = 30;
    var combinedCRC = 0;

    var n = 100000 * blockSize100k;
    _arr1 = Uint32List(n);
    _arr2 = Uint32List(n + _bzNOvershoot);
    _ftab = Uint32List(65537);
    _block = Uint8List.view(_arr2.buffer);
    _mtfv = Uint16List.view(_arr1.buffer);
    _unseqToSeq = Uint8List(256);
    _blockNo = 0;
    _origPtr = 0;

    _selector = Uint8List(_bzMaxSelectors);
    _selectorMtf = Uint8List(_bzMaxSelectors);
    _len = List<Uint8List>.filled(_bzNGroups, BZip2.emptyUint8List);
    _code = List<Int32List>.filled(_bzNGroups, BZip2.emptyInt32List);
    _rfreq = List<Int32List>.filled(_bzNGroups, BZip2.emptyInt32List);

    for (var i = 0; i < _bzNGroups; ++i) {
      _len[i] = Uint8List(_bzMaxAlphaSize);
      _code[i] = Int32List(_bzMaxAlphaSize);
      _rfreq[i] = Int32List(_bzMaxAlphaSize);
    }

    _lenPack =
        List<Uint32List>.filled(_bzMaxAlphaSize, BZip2.emptyUint32List);
    for (var i = 0; i < _bzMaxAlphaSize; ++i) {
      _lenPack[i] = Uint32List(4);
    }

    // Write blocks
    while (!input.isEOS) {
      var blockCRC = _writeBlock();
      combinedCRC = ((combinedCRC << 1) | (combinedCRC >> 31)) & 0xffffffff;
      combinedCRC ^= blockCRC;
      _blockNo++;
    }

    bw.writeBytes(BZip2.eosMagic);
    bw.writeUint32(combinedCRC);
    bw.flush();

    return output.getBytes();
  }

  int _writeBlock() {
    _inUse = Uint8List(256);

    _nblock = 0;
    _blockCRC = BZip2.initialCrc;

    // copy_input_until_stop
    _stateInCh = 256;
    _stateInLen = 0;
    while (_nblock < _nblockMax && !input.isEOS) {
      _addCharToBlock(input.readByte());
    }

    if (_stateInCh < 256) {
      _addPairToBlock();
    }

    _stateInCh = 256;
    _stateInLen = 0;

    _blockCRC = BZip2.finalizeCrc(_blockCRC);

    _compressBlock();

    return _blockCRC;
  }

  void _compressBlock() {
    if (_nblock > 0) {
      _blockSort();
    }

    if (_nblock > 0) {
      bw.writeBytes(BZip2.compressedMagic);
      bw.writeUint32(_blockCRC);

      bw.writeBits(1, 0); // set randomize to 'no'

      bw.writeBits(24, _origPtr);

      _generateMTFValues();

      _sendMTFValues();
    }
  }

  void _generateMTFValues() {
    final yy = Uint8List(256);

    // After sorting (eg, here),
    // s->arr1 [ 0 .. s->nblock-1 ] holds sorted order,
    // and
    //         ((UChar*)s->arr2) [ 0 .. s->nblock-1 ]
    //         holds the original block data.
    //
    //      The first thing to do is generate the MTF values,
    //      and put them in
    //         ((UInt16*)s->arr1) [ 0 .. s->nblock-1 ].
    //      Because there are strictly fewer or equal MTF values
    //      than block values, ptr values in this area are overwritten
    //      with MTF values only when they are no longer needed.
    //
    //      The final compressed bitstream is generated into the
    //      area starting at
    //         (UChar*) (&((UChar*)s->arr2)[s->nblock])
    _nInUse = 0;
    for (var i = 0; i < 256; i++) {
      if (_inUse[i] != 0) {
        _unseqToSeq[i] = _nInUse;
        _nInUse++;
      }
    }

    final eob = _nInUse + 1;

    _mtfFreq = Int32List(_bzMaxAlphaSize);

    var wr = 0;
    var zPend = 0;
    for (var i = 0; i < _nInUse; i++) {
      yy[i] = i;
    }

    for (var i = 0; i < _nblock; i++) {
      _assert(wr <= i);
      var j = _arr1[i] - 1;
      if (j < 0) {
        j += _nblock;
      }

      var lli = _unseqToSeq[_block[j]];
      _assert(lli < _nInUse);

      if (yy[0] == lli) {
        zPend++;
      } else {
        if (zPend > 0) {
          zPend--;
          while (true) {
            if (zPend & 1 != 0) {
              _mtfv[wr] = _bzRunB;
              wr++;
              _mtfFreq[_bzRunB]++;
            } else {
              _mtfv[wr] = _bzRunA;
              wr++;
              _mtfFreq[_bzRunA]++;
            }

            if (zPend < 2) {
              break;
            }

            zPend = (zPend - 2) ~/ 2;
          }

          zPend = 0;
        }

        var rtmp = yy[1];
        yy[1] = yy[0];
        var ryyj = 1;
        var rlli = lli;
        while (rlli != rtmp) {
          ryyj++;
          var rtmp2 = rtmp;
          rtmp = yy[ryyj];
          yy[ryyj] = rtmp2;
        }

        yy[0] = rtmp;
        j = ryyj;

        _mtfv[wr] = j + 1;
        wr++;
        _mtfFreq[j + 1]++;
      }
    }

    if (zPend > 0) {
      zPend--;
      while (true) {
        if (zPend & 1 != 0) {
          _mtfv[wr] = _bzRunB;
          wr++;
          _mtfFreq[_bzRunB]++;
        } else {
          _mtfv[wr] = _bzRunA;
          wr++;
          _mtfFreq[_bzRunA]++;
        }
        if (zPend < 2) {
          break;
        }

        zPend = (zPend - 2) ~/ 2;
      }

      zPend = 0;
    }

    _mtfv[wr] = eob;
    wr++;
    _mtfFreq[eob]++;

    _nMTF = wr;
  }

  void _sendMTFValues() {
    final cost = Uint16List(_bzNGroups);
    final fave = Int32List(_bzNGroups);
    var nSelectors = 0;

    var alphaSize = _nInUse + 2;
    for (var t = 0; t < _bzNGroups; t++) {
      for (var v = 0; v < alphaSize; v++) {
        _len[t][v] = _bzGreaterICost;
      }
    }

    // Decide how many coding tables to use
    int nGroups;
    _assert(_nMTF > 0);
    if (_nMTF < 200) {
      nGroups = 2;
    } else if (_nMTF < 600) {
      nGroups = 3;
    } else if (_nMTF < 1200) {
      nGroups = 4;
    } else if (_nMTF < 2400) {
      nGroups = 5;
    } else {
      nGroups = 6;
    }

    // Generate an initial set of coding tables
    var nPart = nGroups;
    var remF = _nMTF;
    var gs = 0;
    var ge = 0;

    while (nPart > 0) {
      var tFreq = remF ~/ nPart;
      var aFreq = 0;
      ge = gs - 1;

      while (aFreq < tFreq && ge < alphaSize - 1) {
        ge++;
        aFreq += _mtfFreq[ge];
      }

      if (ge > gs &&
          nPart != nGroups &&
          nPart != 1 &&
          ((nGroups - nPart) % 2 == 1)) {
        aFreq -= _mtfFreq[ge];
        ge--;
      }

      for (var v = 0; v < alphaSize; v++) {
        if (v >= gs && v <= ge) {
          _len[nPart - 1][v] = _bzLesserICost;
        } else {
          _len[nPart - 1][v] = _bzGreaterICost;
        }
      }

      nPart--;
      gs = ge + 1;
      remF -= aFreq;
    }

    // Iterate up to BZ_N_ITERS times to improve the tables.
    for (var iter = 0; iter < _bzNIters; iter++) {
      for (var t = 0; t < nGroups; t++) {
        fave[t] = 0;
      }
      for (var t = 0; t < nGroups; t++) {
        for (var v = 0; v < alphaSize; v++) {
          _rfreq[t][v] = 0;
        }
      }

      // Set up an auxiliary length table which is used to fast-track
      // the common case (nGroups == 6).
      if (nGroups == 6) {
        for (var v = 0; v < alphaSize; v++) {
          _lenPack[v][0] = (_len[1][v] << 16) | _len[0][v];
          _lenPack[v][1] = (_len[3][v] << 16) | _len[2][v];
          _lenPack[v][2] = (_len[5][v] << 16) | _len[4][v];
        }
      }

      nSelectors = 0;
      var totc = 0; // ignore: unused_local_variable
      gs = 0;
      while (true) {
        // Set group start & end marks.
        if (gs >= _nMTF) {
          break;
        }

        var ge = gs + _bzGSize - 1;
        if (ge >= _nMTF) {
          ge = _nMTF - 1;
        }

        // Calculate the cost of this group as coded
        // by each of the coding tables.
        for (var t = 0; t < nGroups; t++) {
          cost[t] = 0;
        }

        if (nGroups == 6 && 50 == ge - gs + 1) {
          // fast track the common case
          var cost01 = 0;
          var cost23 = 0;
          var cost45 = 0;

          void bzIter(int nn) {
            var icv = _mtfv[gs + nn];
            cost01 += _lenPack[icv][0];
            cost23 += _lenPack[icv][1];
            cost45 += _lenPack[icv][2];
          }

          bzIter(0);
          bzIter(1);
          bzIter(2);
          bzIter(3);
          bzIter(4);
          bzIter(5);
          bzIter(6);
          bzIter(7);
          bzIter(8);
          bzIter(9);
          bzIter(10);
          bzIter(11);
          bzIter(12);
          bzIter(13);
          bzIter(14);
          bzIter(15);
          bzIter(16);
          bzIter(17);
          bzIter(18);
          bzIter(19);
          bzIter(20);
          bzIter(21);
          bzIter(22);
          bzIter(23);
          bzIter(24);
          bzIter(25);
          bzIter(26);
          bzIter(27);
          bzIter(28);
          bzIter(29);
          bzIter(30);
          bzIter(31);
          bzIter(32);
          bzIter(33);
          bzIter(34);
          bzIter(35);
          bzIter(36);
          bzIter(37);
          bzIter(38);
          bzIter(39);
          bzIter(40);
          bzIter(41);
          bzIter(42);
          bzIter(43);
          bzIter(44);
          bzIter(45);
          bzIter(46);
          bzIter(47);
          bzIter(48);
          bzIter(49);

          cost[0] = cost01 & 0xffff;
          cost[1] = cost01 >> 16;
          cost[2] = cost23 & 0xffff;
          cost[3] = cost23 >> 16;
          cost[4] = cost45 & 0xffff;
          cost[5] = cost45 >> 16;
        } else {
          // slow version which correctly handles all situations
          for (var i = gs; i <= ge; i++) {
            var icv = _mtfv[i];
            for (var t = 0; t < nGroups; t++) {
              cost[t] += _len[t][icv];
            }
          }
        }

        // Find the coding table which is best for this group,
        // and record its identity in the selector table.
        var bc = 999999999;
        var bt = -1;
        for (var t = 0; t < nGroups; t++) {
          if (cost[t] < bc) {
            bc = cost[t];
            bt = t;
          }
        }

        totc += bc;
        fave[bt]++;
        _selector[nSelectors] = bt;
        nSelectors++;

        // Increment the symbol frequencies for the selected table.
        if (nGroups == 6 && 50 == ge - gs + 1) {
          // fast track the common case
          void bzItur(int nn) {
            _rfreq[bt][_mtfv[gs + nn]]++;
          }

          bzItur(0);
          bzItur(1);
          bzItur(2);
          bzItur(3);
          bzItur(4);
          bzItur(5);
          bzItur(6);
          bzItur(7);
          bzItur(8);
          bzItur(9);
          bzItur(10);
          bzItur(11);
          bzItur(12);
          bzItur(13);
          bzItur(14);
          bzItur(15);
          bzItur(16);
          bzItur(17);
          bzItur(18);
          bzItur(19);
          bzItur(20);
          bzItur(21);
          bzItur(22);
          bzItur(23);
          bzItur(24);
          bzItur(25);
          bzItur(26);
          bzItur(27);
          bzItur(28);
          bzItur(29);
          bzItur(30);
          bzItur(31);
          bzItur(32);
          bzItur(33);
          bzItur(34);
          bzItur(35);
          bzItur(36);
          bzItur(37);
          bzItur(38);
          bzItur(39);
          bzItur(40);
          bzItur(41);
          bzItur(42);
          bzItur(43);
          bzItur(44);
          bzItur(45);
          bzItur(46);
          bzItur(47);
          bzItur(48);
          bzItur(49);
        } else {
          // slow version which correctly handles all situations
          for (var i = gs; i <= ge; i++) {
            _rfreq[bt][_mtfv[i]]++;
          }
        }

        gs = ge + 1;
      }

      // Recompute the tables based on the accumulated frequencies.
      for (var t = 0; t < nGroups; t++) {
        _hbMakeCodeLengths(_len[t], _rfreq[t], alphaSize, 17);
      }
    }

    _assert(nGroups < 8);
    _assert(nSelectors < 32768 && nSelectors <= (2 + (900000 ~/ _bzGSize)));

    // Compute MTF values for the selectors.
    final pos = Uint8List(_bzNGroups);
    for (var i = 0; i < nGroups; i++) {
      pos[i] = i;
    }

    for (var i = 0; i < nSelectors; i++) {
      var lli = _selector[i];
      var j = 0;
      var tmp = pos[j];
      while (lli != tmp) {
        j++;
        var tmp2 = tmp;
        tmp = pos[j];
        pos[j] = tmp2;
      }
      pos[0] = tmp;
      _selectorMtf[i] = j;
    }

    // Assign actual codes for the tables.
    for (var t = 0; t < nGroups; t++) {
      var minLen = 32;
      var maxLen = 0;
      for (var i = 0; i < alphaSize; i++) {
        if (_len[t][i] > maxLen) {
          maxLen = _len[t][i];
        }
        if (_len[t][i] < minLen) {
          minLen = _len[t][i];
        }
      }
      _assert(!(maxLen > 17));
      _assert(!(minLen < 1));
      _hbAssignCodes(_code[t], _len[t], minLen, maxLen, alphaSize);
    }

    // Transmit the mapping table.
    final inUse16 = Uint8List(16);
    for (var i = 0; i < 16; i++) {
      inUse16[i] = 0;
      for (var j = 0; j < 16; j++) {
        if (_inUse[i * 16 + j] != 0) {
          inUse16[i] = 1;
        }
      }
    }

    for (var i = 0; i < 16; i++) {
      if (inUse16[i] != 0) {
        bw.writeBits(1, 1);
      } else {
        bw.writeBits(1, 0);
      }
    }

    for (var i = 0; i < 16; i++) {
      if (inUse16[i] != 0) {
        for (var j = 0; j < 16; j++) {
          if (_inUse[i * 16 + j] != 0) {
            bw.writeBits(1, 1);
          } else {
            bw.writeBits(1, 0);
          }
        }
      }
    }

    // Now the selectors.
    bw.writeBits(3, nGroups);
    bw.writeBits(15, nSelectors);
    for (var i = 0; i < nSelectors; i++) {
      for (var j = 0; j < _selectorMtf[i]; j++) {
        bw.writeBits(1, 1);
      }
      bw.writeBits(1, 0);
    }

    // Now the coding tables.
    for (var t = 0; t < nGroups; t++) {
      var curr = _len[t][0];
      bw.writeBits(5, curr);
      for (var i = 0; i < alphaSize; i++) {
        while (curr < _len[t][i]) {
          bw.writeBits(2, 2);
          curr++; // 10
        }

        while (curr > _len[t][i]) {
          bw.writeBits(2, 3);
          curr--; // 11
        }

        bw.writeBits(1, 0);
      }
    }

    // And finally, the block data proper
    var selCtr = 0;
    gs = 0;
    while (true) {
      if (gs >= _nMTF) {
        break;
      }

      var ge = gs + _bzGSize - 1;
      if (ge >= _nMTF) {
        ge = _nMTF - 1;
      }

      _assert(_selector[selCtr] < nGroups);

      if (nGroups == 6 && 50 == ge - gs + 1) {
        // fast track the common case
        int mtfvi;
        final sLenSelSelCtr = _len[_selector[selCtr]];
        final sCodeSelSelCtr = _code[_selector[selCtr]];

        void bzItah(int nn) {
          mtfvi = _mtfv[gs + nn];
          bw.writeBits(sLenSelSelCtr[mtfvi], sCodeSelSelCtr[mtfvi]);
        }

        bzItah(0);
        bzItah(1);
        bzItah(2);
        bzItah(3);
        bzItah(4);
        bzItah(5);
        bzItah(6);
        bzItah(7);
        bzItah(8);
        bzItah(9);
        bzItah(10);
        bzItah(11);
        bzItah(12);
        bzItah(13);
        bzItah(14);
        bzItah(15);
        bzItah(16);
        bzItah(17);
        bzItah(18);
        bzItah(19);
        bzItah(20);
        bzItah(21);
        bzItah(22);
        bzItah(23);
        bzItah(24);
        bzItah(25);
        bzItah(26);
        bzItah(27);
        bzItah(28);
        bzItah(29);
        bzItah(30);
        bzItah(31);
        bzItah(32);
        bzItah(33);
        bzItah(34);
        bzItah(35);
        bzItah(36);
        bzItah(37);
        bzItah(38);
        bzItah(39);
        bzItah(40);
        bzItah(41);
        bzItah(42);
        bzItah(43);
        bzItah(44);
        bzItah(45);
        bzItah(46);
        bzItah(47);
        bzItah(48);
        bzItah(49);
      } else {
        // slow version which correctly handles all situations
        for (var i = gs; i <= ge; i++) {
          bw.writeBits(_len[_selector[selCtr]][_mtfv[i]],
              _code[_selector[selCtr]][_mtfv[i]]);
        }
      }

      gs = ge + 1;
      selCtr++;
    }

    _assert(selCtr == nSelectors);
  }

  void _hbMakeCodeLengths(
      Uint8List len, Int32List freq, int alphaSize, int maxLen) {
    // Nodes and heap entries run from 1.  Entry 0
    // for both the heap and nodes is a sentinel.
    var heap = Int32List(_bzMaxAlphaSize + 2);
    var weight = Int32List(_bzMaxAlphaSize * 2);
    var parent = Int32List(_bzMaxAlphaSize * 2);
    var nHeap = 0;
    int nNodes;

    for (var i = 0; i < alphaSize; i++) {
      weight[i + 1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
    }

    void upHeap(int z) {
      var zz = z;
      var tmp = heap[zz];
      while (weight[tmp] < weight[heap[zz >> 1]]) {
        heap[zz] = heap[zz >> 1];
        zz >>= 1;
      }
      heap[zz] = tmp;
    }

    void downHeap(int z) {
      var zz = z;
      var tmp = heap[zz];
      while (true) {
        var yy = zz << 1;
        if (yy > nHeap) {
          break;
        }
        if (yy < nHeap && weight[heap[yy + 1]] < weight[heap[yy]]) {
          yy++;
        }
        if (weight[tmp] < weight[heap[yy]]) {
          break;
        }
        heap[zz] = heap[yy];
        zz = yy;
      }
      heap[zz] = tmp;
    }

    int weightOf(int zz0) => ((zz0) & 0xffffff00);
    int depthOf(int zz1) => ((zz1) & 0x000000ff);
    int myMax(int zz2, int zz3) => ((zz2) > (zz3) ? (zz2) : (zz3));
    int addWeights(int zw1, int zw2) =>
        (weightOf(zw1) + weightOf(zw2)) |
        (1 + myMax(depthOf(zw1), depthOf(zw2)));

    while (true) {
      nNodes = alphaSize;
      nHeap = 0;

      heap[0] = 0;
      weight[0] = 0;
      parent[0] = -2;

      for (var i = 1; i <= alphaSize; i++) {
        parent[i] = -1;
        nHeap++;
        heap[nHeap] = i;
        upHeap(nHeap);
      }

      _assert(nHeap < (_bzMaxAlphaSize + 2));

      while (nHeap > 1) {
        var n1 = heap[1];
        heap[1] = heap[nHeap];
        nHeap--;
        downHeap(1);
        var n2 = heap[1];
        heap[1] = heap[nHeap];
        nHeap--;
        downHeap(1);
        nNodes++;
        parent[n1] = parent[n2] = nNodes;
        weight[nNodes] = addWeights(weight[n1], weight[n2]);
        parent[nNodes] = -1;
        nHeap++;
        heap[nHeap] = nNodes;
        upHeap(nHeap);
      }

      _assert(nNodes < (_bzMaxAlphaSize * 2));

      var tooLong = false;
      for (var i = 1; i <= alphaSize; i++) {
        var j = 0;
        var k = i;
        while (parent[k] >= 0) {
          k = parent[k];
          j++;
        }
        len[i - 1] = j;
        if (j > maxLen) {
          tooLong = true;
        }
      }

      if (!tooLong) {
        break;
      }

      for (var i = 1; i <= alphaSize; i++) {
        var j = weight[i] >> 8;
        j = 1 + (j ~/ 2);
        weight[i] = j << 8;
      }
    }
  }

  void _hbAssignCodes(Int32List codes, Uint8List length, int minLen, int maxLen,
      int alphaSize) {
    var vec = 0;
    for (var n = minLen; n <= maxLen; n++) {
      for (var i = 0; i < alphaSize; i++) {
        if (length[i] == n) {
          codes[i] = vec;
          vec++;
        }
      }
      vec <<= 1;
    }
  }

  void _blockSort() {
    if (_nblock < 10000) {
      _fallbackSort(_arr1, _arr2, _ftab, _nblock);
    } else {
      // Calculate the location for quadrant, remembering to get
      // the alignment right.  Assumes that &(block[0]) is at least
      // 2-byte aligned -- this should be ok since block is really
      // the first section of arr2.
      var i = _nblock + _bzNOvershoot;
      if (i & 1 != 0) {
        i++;
      }
      final quadrant = Uint16List.view(_block.buffer, i);

      var wfact = _workFactor;
      // (wfact-1) / 3 puts the default-factor-30
      // transition point at very roughly the same place as
      // with v0.1 and v0.9.0.
      // Not that it particularly matters any more, since the
      // resulting compressed stream is now the same regardless
      // of whether or not we use the main sort or fallback sort.
      if (wfact < 1) {
        wfact = 1;
      }
      if (wfact > 100) {
        wfact = 100;
      }

      var budgetInit = _nblock * ((wfact - 1) ~/ 3);
      _budget = budgetInit;

      _mainSort(_arr1, _block, quadrant, _ftab, _nblock);
      if (_budget < 0) {
        _fallbackSort(_arr1, _arr2, _ftab, _nblock);
      }
    }

    _origPtr = -1;
    for (var i = 0; i < _nblock; i++) {
      if (_arr1[i] == 0) {
        _origPtr = i;
        break;
      }
    }

    _assert(_origPtr != -1);
  }

  void _assert(bool cond) {
    if (!cond) {
      throw ArchiveException('Data error');
    }
  }

  void _fallbackSort(
      Uint32List fmap, Uint32List eclass, Uint32List bhtab, int nblock) {
    final ftab = Int32List(257);
    final ftabCopy = Int32List(256);
    final eclass8 = Uint8List.view(eclass.buffer);

    int setBh(int zz) => bhtab[zz >> 5] |= (1 << (zz & 31));
    int clearBh(int zz) => bhtab[zz >> 5] &= ~(1 << (zz & 31));
    bool isSetBh(int zz) => (bhtab[zz >> 5] & (1 << (zz & 31)) != 0);
    int wordBh(int zz) => bhtab[(zz) >> 5];
    bool unalignedBh(int zz) => ((zz) & 0x01f) != 0;

    // Initial 1-char radix sort to generate
    // initial fmap and initial BH bits.
    for (var i = 0; i < 257; i++) {
      ftab[i] = 0;
    }
    for (var i = 0; i < nblock; i++) {
      ftab[eclass8[i]]++;
    }
    for (var i = 0; i < 256; i++) {
      ftabCopy[i] = ftab[i];
    }
    for (var i = 1; i < 257; i++) {
      ftab[i] += ftab[i - 1];
    }

    for (var i = 0; i < nblock; i++) {
      final j = eclass8[i];
      final k = ftab[j] - 1;
      ftab[j] = k;
      fmap[k] = i;
    }

    final nBhtab = 2 + (nblock ~/ 32);
    for (var i = 0; i < nBhtab; i++) {
      bhtab[i] = 0;
    }

    for (var i = 0; i < 256; i++) {
      setBh(ftab[i]);
    }

    // Inductively refine the buckets.  Kind-of an
    // "exponential radix sort" (!), inspired by the
    // Manber-Myers suffix array construction algorithm.

    // set sentinel bits for block-end detection
    for (var i = 0; i < 32; i++) {
      setBh(nblock + 2 * i);
      clearBh(nblock + 2 * i + 1);
    }

    // the log(N) loop
    var H = 1;
    while (true) {
      var j = 0;
      for (var i = 0; i < nblock; i++) {
        if (isSetBh(i)) {
          j = i;
        }
        var k = fmap[i] - H;
        if (k < 0) {
          k += nblock;
        }
        eclass[k] = j;
      }

      var nNotDone = 0;
      var r = -1;
      while (true) {
        // find the next non-singleton bucket
        var k = r + 1;
        while (isSetBh(k) && unalignedBh(k)) {
          k++;
        }
        if (isSetBh(k)) {
          while (wordBh(k) == 0xffffffff) {
            k += 32;
          }
          while (isSetBh(k)) {
            k++;
          }
        }

        var l = k - 1;
        if (l >= nblock) {
          break;
        }
        while (!isSetBh(k) && unalignedBh(k)) {
          k++;
        }
        if (!isSetBh(k)) {
          while (wordBh(k) == 0x00000000) {
            k += 32;
          }
          while (!isSetBh(k)) {
            k++;
          }
        }

        r = k - 1;
        if (r >= nblock) {
          break;
        }

        // now [l, r] bracket current bucket
        if (r > l) {
          nNotDone += (r - l + 1);
          _fallbackQSort3(fmap, eclass, l, r);

          // scan bucket and generate header bits
          var cc = -1;
          for (var i = l; i <= r; i++) {
            var cc1 = eclass[fmap[i]];
            if (cc != cc1) {
              setBh(i);
              cc = cc1;
            }
          }
        }
      }

      H *= 2;
      if (H > nblock || nNotDone == 0) {
        break;
      }
    }

    // Reconstruct the original block in
    // eclass8 [0 .. nblock-1], since the
    // previous phase destroyed it.
    var j = 0;
    for (var i = 0; i < nblock; i++) {
      while (ftabCopy[j] == 0) {
        j++;
      }
      ftabCopy[j]--;
      eclass8[fmap[i]] = j;
    }
    _assert(j < 256);
  }

  void _fallbackQSort3(Uint32List fmap, Uint32List eclass, int loSt, int hiSt) {
    const fallbackQSortSmallThreshold = 10;
    const fallbackQSortStackSize = 100;

    final stackLo = Int32List(fallbackQSortStackSize);
    final stackHi = Int32List(fallbackQSortStackSize);
    var sp = 0;

    void fpush(int lz, int hz) {
      stackLo[sp] = lz;
      stackHi[sp] = hz;
      sp++;
    }

    int fmin(int a, int b) => ((a) < (b)) ? (a) : (b);

    void fvswap(int yyp1, int yyp2, int yyn) {
      while (yyn > 0) {
        final t = fmap[yyp1];
        fmap[yyp1] = fmap[yyp2];
        fmap[yyp2] = t;
        yyp1++;
        yyp2++;
        yyn--;
      }
    }

    var r = 0;

    fpush(loSt, hiSt);

    while (sp > 0) {
      _assert(sp < fallbackQSortStackSize - 1);

      sp--;
      final lo = stackLo[sp];
      final hi = stackHi[sp];

      if (hi - lo < fallbackQSortSmallThreshold) {
        _fallbackSimpleSort(fmap, eclass, lo, hi);
        continue;
      }

      // Random partitioning.  Median of 3 sometimes fails to
      // avoid bad cases.  Median of 9 seems to help but
      // looks rather expensive.  This too seems to work but
      // is cheaper.  Guidance for the magic constants
      // 7621 and 32768 is taken from Sedgewick's algorithms
      // book, chapter 35.
      r = ((r * 7621) + 1) % 32768;
      var r3 = r % 3;
      int med;
      if (r3 == 0) {
        med = eclass[fmap[lo]];
      } else if (r3 == 1) {
        med = eclass[fmap[(lo + hi) >> 1]];
      } else {
        med = eclass[fmap[hi]];
      }

      var unLo = lo;
      var ltLo = lo;
      var unHi = hi;
      var gtHi = hi;

      while (true) {
        while (true) {
          if (unLo > unHi) {
            break;
          }

          var n = eclass[fmap[unLo]] - med;
          if (n == 0) {
            var t = fmap[unLo];
            fmap[unLo] = fmap[ltLo];
            fmap[ltLo] = t;
            ltLo++;
            unLo++;
            continue;
          }
          if (n > 0) {
            break;
          }
          unLo++;
        }
        while (true) {
          if (unLo > unHi) {
            break;
          }
          var n = eclass[fmap[unHi]] - med;
          if (n == 0) {
            var t = fmap[unHi];
            fmap[unHi] = fmap[gtHi];
            fmap[gtHi] = t;
            gtHi--;
            unHi--;
            continue;
          }
          if (n < 0) {
            break;
          }
          unHi--;
        }
        if (unLo > unHi) {
          break;
        }

        var t = fmap[unLo];
        fmap[unLo] = fmap[unHi];
        fmap[unHi] = t;
        unLo++;
        unHi--;
      }

      _assert(unHi == unLo - 1);

      if (gtHi < ltLo) {
        continue;
      }

      var n = fmin(ltLo - lo, unLo - ltLo);
      fvswap(lo, unLo - n, n);
      var m = fmin(hi - gtHi, gtHi - unHi);
      fvswap(unLo, hi - m + 1, m);

      n = lo + unLo - ltLo - 1;
      m = hi - (gtHi - unHi) + 1;

      if (n - lo > hi - m) {
        fpush(lo, n);
        fpush(m, hi);
      } else {
        fpush(m, hi);
        fpush(lo, n);
      }
    }
  }

  void _fallbackSimpleSort(Uint32List fmap, Uint32List eclass, int lo, int hi) {
    if (lo == hi) {
      return;
    }

    if (hi - lo > 3) {
      for (var i = hi - 4; i >= lo; i--) {
        var tmp = fmap[i];
        var ecTmp = eclass[tmp];
        int j;
        for (j = i + 4; j <= hi && ecTmp > eclass[fmap[j]]; j += 4) {
          fmap[j - 4] = fmap[j];
        }
        fmap[j - 4] = tmp;
      }
    }

    for (var i = hi - 1; i >= lo; i--) {
      var tmp = fmap[i];
      var ecTmp = eclass[tmp];
      int j;
      for (j = i + 1; j <= hi && ecTmp > eclass[fmap[j]]; j++) {
        fmap[j - 1] = fmap[j];
      }
      fmap[j - 1] = tmp;
    }
  }

  void _mainSort(Uint32List ptr, Uint8List block, Uint16List quadrant,
      Uint32List ftab, int nblock) {
    final runningOrder = Int32List(256);
    final bigDone = Uint8List(256);
    final copyStart = Int32List(256);
    final copyEnd = Int32List(256);

    int bigFreq(int b) => (_ftab[((b) + 1) << 8] - _ftab[(b) << 8]);

    const setMask = 2097152;
    const clearMask = 4292870143;

    // set up the 2-byte frequency table
    for (var i = 65536; i >= 0; i--) {
      ftab[i] = 0;
    }

    var j = block[0] << 8;
    var i = nblock - 1;

    for (; i >= 3; i -= 4) {
      quadrant[i] = 0;
      j = (j >> 8) | ((block[i]) << 8);
      ftab[j]++;
      quadrant[i - 1] = 0;
      j = (j >> 8) | ((block[i - 1]) << 8);
      ftab[j]++;
      quadrant[i - 2] = 0;
      j = (j >> 8) | ((block[i - 2]) << 8);
      ftab[j]++;
      quadrant[i - 3] = 0;
      j = (j >> 8) | ((block[i - 3]) << 8);
      ftab[j]++;
    }

    for (; i >= 0; i--) {
      quadrant[i] = 0;
      j = (j >> 8) | ((block[i]) << 8);
      ftab[j]++;
    }

    // (emphasises close relationship of block & quadrant)
    for (i = 0; i < _bzNOvershoot; i++) {
      block[nblock + i] = block[i];
      quadrant[nblock + i] = 0;
    }

    // Complete the initial radix sort
    for (i = 1; i <= 65536; i++) {
      ftab[i] += ftab[i - 1];
    }

    var s = block[0] << 8;
    i = nblock - 1;
    for (; i >= 3; i -= 4) {
      s = (s >> 8) | (block[i] << 8);
      j = ftab[s] - 1;
      ftab[s] = j;
      ptr[j] = i;
      s = (s >> 8) | (block[i - 1] << 8);
      j = ftab[s] - 1;
      ftab[s] = j;
      ptr[j] = i - 1;
      s = (s >> 8) | (block[i - 2] << 8);
      j = ftab[s] - 1;
      ftab[s] = j;
      ptr[j] = i - 2;
      s = (s >> 8) | (block[i - 3] << 8);
      j = ftab[s] - 1;
      ftab[s] = j;
      ptr[j] = i - 3;
    }
    for (; i >= 0; i--) {
      s = (s >> 8) | (block[i] << 8);
      j = ftab[s] - 1;
      ftab[s] = j;
      ptr[j] = i;
    }

    // Now ftab contains the first loc of every small bucket.
    // Calculate the running order, from smallest to largest
    // big bucket.
    for (i = 0; i <= 255; i++) {
      bigDone[i] = 0;
      runningOrder[i] = i;
    }

    var h = 1;
    do {
      h = 3 * h + 1;
    } while (h <= 256);
    do {
      h = h ~/ 3;
      for (i = h; i <= 255; i++) {
        var vv = runningOrder[i];
        j = i;
        while (bigFreq(runningOrder[j - h]) > bigFreq(vv)) {
          runningOrder[j] = runningOrder[j - h];
          j = j - h;
          if (j <= (h - 1)) {
            break;
          }
        }
        runningOrder[j] = vv;
      }
    } while (h != 1);

    // The main sorting loop.

    var numQSorted = 0; // ignore: unused_local_variable

    for (i = 0; i <= 255; i++) {
      // Process big buckets, starting with the least full.
      // Basically this is a 3-step process in which we call
      // mainQSort3 to sort the small buckets [ss, j], but
      // also make a big effort to avoid the calls if we can.
      var ss = runningOrder[i];

      // Step 1:
      // Complete the big bucket [ss] by quicksorting
      // any unsorted small buckets [ss, j], for j != ss.
      // Hopefully previous pointer-scanning phases have already
      // completed many of the small buckets [ss, j], so
      // we don't have to sort them at all.
      for (j = 0; j <= 255; j++) {
        if (j != ss) {
          var sb = (ss << 8) + j;
          if ((_ftab[sb] & setMask) == 0) {
            var lo = _ftab[sb] & clearMask;
            var hi = (_ftab[sb + 1] & clearMask) - 1;
            if (hi > lo) {
              _mainQSort3(ptr, block, quadrant, nblock, lo, hi, _bzNRadix);
              numQSorted += (hi - lo + 1);
              if (_budget < 0) {
                return;
              }
            }
          }
          _ftab[sb] |= setMask;
        }
      }

      _assert(bigDone[ss] == 0);

      // Step 2:
      // Now scan this big bucket [ss] so as to synthesise the
      // sorted order for small buckets [t, ss] for all t,
      // including, magically, the bucket [ss,ss] too.
      // This will avoid doing Real Work in subsequent Step 1's.
      for (j = 0; j <= 255; j++) {
        copyStart[j] = _ftab[(j << 8) + ss] & clearMask;
        copyEnd[j] = (_ftab[(j << 8) + ss + 1] & clearMask) - 1;
      }

      for (j = _ftab[ss << 8] & clearMask; j < copyStart[ss]; j++) {
        var k = ptr[j] - 1;
        if (k < 0) k += nblock;
        var c1 = block[k];
        if (bigDone[c1] == 0) {
          ptr[copyStart[c1]++] = k;
        }
      }

      for (j = (_ftab[(ss + 1) << 8] & clearMask) - 1; j > copyEnd[ss]; j--) {
        var k = ptr[j] - 1;
        if (k < 0) {
          k += nblock;
        }
        var c1 = block[k];
        if (bigDone[c1] == 0) {
          ptr[copyEnd[c1]--] = k;
        }
      }

      _assert((copyStart[ss] - 1 == copyEnd[ss]) ||
          // Extremely rare case missing in bzip2-1.0.0 and 1.0.1.
          // Necessity for this case is demonstrated by compressing
          // a sequence of approximately 48.5 million of character
          // 251; 1.0.0/1.0.1 will then die here.
          (copyStart[ss] == 0 && copyEnd[ss] == nblock - 1));

      for (j = 0; j <= 255; j++) {
        _ftab[(j << 8) + ss] |= setMask;
      }

      // Step 3:
      // The [ss] big bucket is now done.  Record this fact,
      // and update the quadrant descriptors.  Remember to
      // update quadrants in the overshoot area too, if
      // necessary.  The "if (i < 255)" test merely skips
      // this updating for the last bucket processed, since
      // updating for the last bucket is pointless.
      //
      // The quadrant array provides a way to incrementally
      // cache sort orderings, as they appear, so as to
      // make subsequent comparisons in fullGtU() complete
      // faster.  For repetitive blocks this makes a big
      // difference (but not big enough to be able to avoid
      // the fallback sorting mechanism, exponential radix sort).
      //
      // The precise meaning is: at all times:
      //
      //          for 0 <= i < nblock and 0 <= j <= nblock
      //
      //          if block[i] != block[j],
      //
      //             then the relative values of quadrant[i] and
      //                  quadrant[j] are meaningless.
      //
      //             else {
      //                if quadrant[i] < quadrant[j]
      //                   then the string starting at i lexicographically
      //                   precedes the string starting at j
      //
      //                else if quadrant[i] > quadrant[j]
      //                   then the string starting at j lexicographically
      //                   precedes the string starting at i
      //
      //                else
      //                   the relative ordering of the strings starting
      //                   at i and j has not yet been determined.
      //             }
      bigDone[ss] = 1;

      if (i < 255) {
        var bbStart = _ftab[ss << 8] & clearMask;
        var bbSize = (_ftab[(ss + 1) << 8] & clearMask) - bbStart;
        var shifts = 0;

        if (bbSize > 0) {
          while ((bbSize >> shifts) > 65534) {
            shifts++;
          }

          for (j = bbSize - 1; j >= 0; j--) {
            var a2update = ptr[bbStart + j];
            var qVal = (j >> shifts) & 0xffff;
            quadrant[a2update] = qVal;
            if (a2update < _bzNOvershoot) {
              quadrant[a2update + nblock] = qVal;
            }
            _assert(((bbSize - 1) >> shifts) <= 65535);
          }
        }
      }
    }
  }

  void _mainQSort3(Uint32List ptr, Uint8List block, Uint16List quadrant,
      int nblock, int loSt, int hiSt, int dSt) {
    const mainQSortStackSize = 100;
    const mainQSortSmallThreshold = 20;
    const mainQSortDepthThreshold = (_bzNRadix + _bzNQSort);

    final stackLo = Int32List(mainQSortStackSize);
    final stackHi = Int32List(mainQSortStackSize);
    final stackD = Int32List(mainQSortStackSize);

    final nextLo = Int32List(3);
    final nextHi = Int32List(3);
    final nextD = Int32List(3);

    var sp = 0;
    void mpush(int lz, int hz, int dz) {
      stackLo[sp] = lz;
      stackHi[sp] = hz;
      stackD[sp] = dz;
      sp++;
    }

    int mmed3(int a, int b, int c) {
      if (a > b) {
        var t = a;
        a = b;
        b = t;
      }
      if (b > c) {
        b = c;
        if (a > b) {
          b = a;
        }
      }
      return b;
    }

    void mvswap(int yyp1, int yyp2, int yyn) {
      while (yyn > 0) {
        var t = ptr[yyp1];
        ptr[yyp1] = ptr[yyp2];
        ptr[yyp2] = t;
        yyp1++;
        yyp2++;
        yyn--;
      }
    }

    int mmin(int a, int b) => ((a) < (b)) ? (a) : (b);

    int mnextsize(int az) => (nextHi[az] - nextLo[az]);

    void mnextswap(int az, int bz) {
      var tz = nextLo[az];
      nextLo[az] = nextLo[bz];
      nextLo[bz] = tz;
      tz = nextHi[az];
      nextHi[az] = nextHi[bz];
      nextHi[bz] = tz;
      tz = nextD[az];
      nextD[az] = nextD[bz];
      nextD[bz] = tz;
    }

    mpush(loSt, hiSt, dSt);

    while (sp > 0) {
      _assert(sp < mainQSortStackSize - 2);

      sp--;
      var lo = stackLo[sp];
      var hi = stackHi[sp];
      var d = stackD[sp];

      if (hi - lo < mainQSortSmallThreshold || d > mainQSortDepthThreshold) {
        _mainSimpleSort(ptr, block, quadrant, nblock, lo, hi, d);
        if (_budget < 0) {
          return;
        }
        continue;
      }

      var med = mmed3(block[ptr[lo] + d], block[ptr[hi] + d],
          block[ptr[(lo + hi) >> 1] + d]);

      var unLo = lo;
      var ltLo = lo;
      var unHi = hi;
      var gtHi = hi;

      while (true) {
        while (true) {
          if (unLo > unHi) {
            break;
          }

          var n = (block[ptr[unLo] + d]) - med;
          if (n == 0) {
            var t = ptr[unLo];
            ptr[unLo] = ptr[ltLo];
            ptr[ltLo] = t;
            ltLo++;
            unLo++;
            continue;
          }
          if (n > 0) {
            break;
          }
          unLo++;
        }
        while (true) {
          if (unLo > unHi) {
            break;
          }

          var n = (block[ptr[unHi] + d]) - med;
          if (n == 0) {
            var t = ptr[unHi];
            ptr[unHi] = ptr[gtHi];
            ptr[gtHi] = t;
            gtHi--;
            unHi--;
            continue;
          }
          if (n < 0) {
            break;
          }
          unHi--;
        }
        if (unLo > unHi) {
          break;
        }

        var t = ptr[unLo];
        ptr[unLo] = ptr[unHi];
        ptr[unHi] = t;
        unLo++;
        unHi--;
      }

      _assert(unHi == unLo - 1);

      if (gtHi < ltLo) {
        mpush(lo, hi, d + 1);
        continue;
      }

      var n = mmin(ltLo - lo, unLo - ltLo);
      mvswap(lo, unLo - n, n);
      var m = mmin(hi - gtHi, gtHi - unHi);
      mvswap(unLo, hi - m + 1, m);

      n = lo + unLo - ltLo - 1;
      m = hi - (gtHi - unHi) + 1;

      nextLo[0] = lo;
      nextHi[0] = n;
      nextD[0] = d;
      nextLo[1] = m;
      nextHi[1] = hi;
      nextD[1] = d;
      nextLo[2] = n + 1;
      nextHi[2] = m - 1;
      nextD[2] = d + 1;

      if (mnextsize(0) < mnextsize(1)) {
        mnextswap(0, 1);
      }
      if (mnextsize(1) < mnextsize(2)) {
        mnextswap(1, 2);
      }
      if (mnextsize(0) < mnextsize(1)) {
        mnextswap(0, 1);
      }

      _assert(mnextsize(0) >= mnextsize(1));
      _assert(mnextsize(1) >= mnextsize(2));

      mpush(nextLo[0], nextHi[0], nextD[0]);
      mpush(nextLo[1], nextHi[1], nextD[1]);
      mpush(nextLo[2], nextHi[2], nextD[2]);
    }
  }

  void _mainSimpleSort(Uint32List ptr, Uint8List block, Uint16List quadrant,
      int nblock, int lo, int hi, int d) {
    var bigN = hi - lo + 1;
    if (bigN < 2) {
      return;
    }

    const incs = [
      1,
      4,
      13,
      40,
      121,
      364,
      1093,
      3280,
      9841,
      29524,
      88573,
      265720,
      797161,
      2391484
    ];

    var hp = 0;
    while (incs[hp] < bigN) {
      hp++;
    }
    hp--;

    for (; hp >= 0; hp--) {
      var h = incs[hp];

      var i = lo + h;
      while (true) {
        // copy 1
        if (i > hi) {
          break;
        }
        var v = ptr[i];
        var j = i;
        while (_mainGtU(ptr[j - h] + d, v + d, block, quadrant, nblock)) {
          ptr[j] = ptr[j - h];
          j = j - h;
          if (j <= (lo + h - 1)) {
            break;
          }
        }
        ptr[j] = v;
        i++;

        // copy 2
        if (i > hi) {
          break;
        }
        v = ptr[i];
        j = i;
        while (_mainGtU(ptr[j - h] + d, v + d, block, quadrant, nblock)) {
          ptr[j] = ptr[j - h];
          j = j - h;
          if (j <= (lo + h - 1)) {
            break;
          }
        }
        ptr[j] = v;
        i++;

        // copy 3
        if (i > hi) {
          break;
        }
        v = ptr[i];
        j = i;
        while (_mainGtU(ptr[j - h] + d, v + d, block, quadrant, nblock)) {
          ptr[j] = ptr[j - h];
          j = j - h;
          if (j <= (lo + h - 1)) {
            break;
          }
        }
        ptr[j] = v;
        i++;

        if (_budget < 0) {
          return;
        }
      }
    }
  }

  bool _mainGtU(
      int i1, int i2, Uint8List block, Uint16List quadrant, int nblock) {
    _assert(i1 != i2);
    // 1
    var c1 = block[i1];
    var c2 = block[i2];
    if (c1 != c2) {
      return (c1 > c2);
    }
    i1++;
    i2++;
    // 2
    c1 = block[i1];
    c2 = block[i2];
    if (c1 != c2) {
      return (c1 > c2);
    }
    i1++;
    i2++;
    // 3
    c1 = block[i1];
    c2 = block[i2];
    if (c1 != c2) {
      return (c1 > c2);
    }
    i1++;
    i2++;
    // 4
    c1 = block[i1];
    c2 = block[i2];
    if (c1 != c2) {
      return (c1 > c2);
    }
    i1++;
    i2++;
    // 5
    c1 = block[i1];
    c2 = block[i2];
    if (c1 != c2) {
      return (c1 > c2);
    }
    i1++;
    i2++;
    // 6
    c1 = block[i1];
    c2 = block[i2];
    if (c1 != c2) {
      return (c1 > c2);
    }
    i1++;
    i2++;
    // 7
    c1 = block[i1];
    c2 = block[i2];
    if (c1 != c2) {
      return (c1 > c2);
    }
    i1++;
    i2++;
    // 8
    c1 = block[i1];
    c2 = block[i2];
    if (c1 != c2) {
      return (c1 > c2);
    }
    i1++;
    i2++;
    // 9
    c1 = block[i1];
    c2 = block[i2];
    if (c1 != c2) {
      return (c1 > c2);
    }
    i1++;
    i2++;
    // 10
    c1 = block[i1];
    c2 = block[i2];
    if (c1 != c2) {
      return (c1 > c2);
    }
    i1++;
    i2++;
    // 11
    c1 = block[i1];
    c2 = block[i2];
    if (c1 != c2) {
      return (c1 > c2);
    }
    i1++;
    i2++;
    // 12
    c1 = block[i1];
    c2 = block[i2];
    if (c1 != c2) {
      return (c1 > c2);
    }
    i1++;
    i2++;

    var k = nblock + 8;

    do {
      // 1
      c1 = block[i1];
      c2 = block[i2];
      if (c1 != c2) {
        return (c1 > c2);
      }
      var s1 = quadrant[i1];
      var s2 = quadrant[i2];
      if (s1 != s2) {
        return (s1 > s2);
      }
      i1++;
      i2++;
      // 2
      c1 = block[i1];
      c2 = block[i2];
      if (c1 != c2) {
        return (c1 > c2);
      }
      s1 = quadrant[i1];
      s2 = quadrant[i2];
      if (s1 != s2) {
        return (s1 > s2);
      }
      i1++;
      i2++;
      // 3
      c1 = block[i1];
      c2 = block[i2];
      if (c1 != c2) {
        return (c1 > c2);
      }
      s1 = quadrant[i1];
      s2 = quadrant[i2];
      if (s1 != s2) {
        return (s1 > s2);
      }
      i1++;
      i2++;
      // 4
      c1 = block[i1];
      c2 = block[i2];
      if (c1 != c2) {
        return (c1 > c2);
      }
      s1 = quadrant[i1];
      s2 = quadrant[i2];
      if (s1 != s2) {
        return (s1 > s2);
      }
      i1++;
      i2++;
      // 5
      c1 = block[i1];
      c2 = block[i2];
      if (c1 != c2) {
        return (c1 > c2);
      }
      s1 = quadrant[i1];
      s2 = quadrant[i2];
      if (s1 != s2) {
        return (s1 > s2);
      }
      i1++;
      i2++;
      // 6
      c1 = block[i1];
      c2 = block[i2];
      if (c1 != c2) {
        return (c1 > c2);
      }
      s1 = quadrant[i1];
      s2 = quadrant[i2];
      if (s1 != s2) {
        return (s1 > s2);
      }
      i1++;
      i2++;
      // 7
      c1 = block[i1];
      c2 = block[i2];
      if (c1 != c2) {
        return (c1 > c2);
      }
      s1 = quadrant[i1];
      s2 = quadrant[i2];
      if (s1 != s2) {
        return (s1 > s2);
      }
      i1++;
      i2++;
      // 8
      c1 = block[i1];
      c2 = block[i2];
      if (c1 != c2) {
        return (c1 > c2);
      }
      s1 = quadrant[i1];
      s2 = quadrant[i2];
      if (s1 != s2) {
        return (s1 > s2);
      }
      i1++;
      i2++;

      if (i1 >= nblock) {
        i1 -= nblock;
      }
      if (i2 >= nblock) {
        i2 -= nblock;
      }

      k -= 8;
      _budget--;
    } while (k >= 0);

    return false;
  }

  void _addCharToBlock(int b) {
    if (b != _stateInCh && _stateInLen == 1) {
      _blockCRC = BZip2.updateCrc(_stateInCh, _blockCRC);
      _inUse[_stateInCh] = 1;
      _block[_nblock] = _stateInCh;
      _nblock++;
      _stateInCh = b;
    } else {
      if (b != _stateInCh || _stateInLen == 255) {
        if (_stateInCh < 256) {
          _addPairToBlock();
        }
        _stateInCh = b;
        _stateInLen = 1;
      } else {
        _stateInLen++;
      }
    }
  }

  void _addPairToBlock() {
    for (var i = 0; i < _stateInLen; i++) {
      _blockCRC = BZip2.updateCrc(_stateInCh, _blockCRC);
    }
    _inUse[_stateInCh] = 1;
    switch (_stateInLen) {
      case 1:
        _block[_nblock] = _stateInCh;
        _nblock++;
        break;
      case 2:
        _block[_nblock] = _stateInCh;
        _nblock++;
        _block[_nblock] = _stateInCh;
        _nblock++;
        break;
      case 3:
        _block[_nblock] = _stateInCh;
        _nblock++;
        _block[_nblock] = _stateInCh;
        _nblock++;
        _block[_nblock] = _stateInCh;
        _nblock++;
        break;
      default:
        _inUse[_stateInLen - 4] = 1;
        _block[_nblock] = _stateInCh;
        _nblock++;
        _block[_nblock] = _stateInCh;
        _nblock++;
        _block[_nblock] = _stateInCh;
        _nblock++;
        _block[_nblock] = _stateInCh;
        _nblock++;
        _block[_nblock] = _stateInLen - 4;
        _nblock++;
        break;
    }
  }

  late InputStream input;
  late Bz2BitWriter bw;
  late int _nblockMax;
  late int _stateInCh;
  late int _stateInLen;
  late int _nblock;
  late int _blockCRC;
  late int _blockNo; // ignore: unused_field
  late int _workFactor;
  late int _budget;
  late int _origPtr;

  late Uint32List _arr1;
  late Uint32List _arr2;
  late Uint32List _ftab;
  late Uint8List _block;
  late Uint8List _inUse;
  late Uint16List _mtfv;
  late int _nInUse;

  late int _nMTF;
  late Int32List _mtfFreq;
  late Uint8List _unseqToSeq;
  late List<Uint8List> _len;
  late List<Int32List> _code;
  late List<Int32List> _rfreq;
  late List<Uint32List> _lenPack;
  late Uint8List _selector;
  late Uint8List _selectorMtf;

  static const int _bzNRadix = 2;
  static const int _bzNQSort = 12;
  static const int _bzNShell = 18;
  static const int _bzNOvershoot = (_bzNRadix + _bzNQSort + _bzNShell + 2);
  static const int _bzMaxAlphaSize = 258;
  static const int _bzRunA = 0;
  static const int _bzRunB = 1;
  static const int _bzNGroups = 6;
  static const int _bzGSize = 50;
  static const int _bzNIters = 4;
  static const int _bzLesserICost = 0;
  static const int _bzGreaterICost = 15;
  static const int _bzMaxSelectors = (2 + (900000 ~/ _bzGSize));
}