decode method

List<int> decode(List<int> encoded, List<int> alphabet, List<int> freqs, int outLen,)

Implementation

List<int> decode(
  List<int> encoded,
  List<int> alphabet,
  List<int> freqs,
  int outLen,
) {
  if (encoded.isEmpty) return [];

  final counts = List<int>.from(freqs);
  final total = counts.fold<int>(0, (p, e) => p + e);
  final cum = <int>[0];
  for (var c in counts) {
    cum.add(cum.last + c);
  }

  var low = 0;
  var high = _maxvalue;

  // bit reader
  var bytePos = 0;
  var currentByte = (bytePos < encoded.length) ? encoded[bytePos++] : 0;
  var bitsRemaining = 8;

  int getBit() {
    if (bitsRemaining == 0) {
      currentByte = (bytePos < encoded.length) ? encoded[bytePos++] : 0;
      bitsRemaining = 8;
    }
    final bit = (currentByte >> (bitsRemaining - 1)) & 1;
    bitsRemaining--;
    return bit;
  }

  // initialize value with _CODE_BITS bits
  var value = 0;
  for (var i = 0; i < _codeBits; i++) {
    value = (value << 1) | getBit();
  }

  final res = <int>[];
  for (var i = 0; i < outLen; i++) {
    final range = high - low + 1;
    final scaled = ((value - low + 1) * total - 1) ~/ range;

    // find symbol index
    var idx = 0;
    for (var j = 0; j < alphabet.length; j++) {
      if (cum[j] <= scaled && scaled < cum[j + 1]) {
        idx = j;
        break;
      }
    }
    final sym = alphabet[idx];
    res.add(sym);

    final symLow = cum[idx];
    final symHigh = cum[idx + 1];
    high = low + (range * symHigh ~/ total) - 1;
    low = low + (range * symLow ~/ total);

    // renormalize
    while (true) {
      if (high < _half) {
        // do nothing
      } else if (low >= _half) {
        value -= _half;
        low -= _half;
        high -= _half;
      } else if (low >= _firstqtr && high < _thirdqtr) {
        value -= _firstqtr;
        low -= _firstqtr;
        high -= _firstqtr;
      } else {
        break;
      }
      low = low << 1;
      high = (high << 1) | 1;
      value = (value << 1) | getBit();
    }
  }

  return res;
}