decompress function

List<int>? decompress(Uint8List x, int slen, int n)

Decompress x (of nominal length slen) into a vector of exactly n coefficients.

Returns null for any invalid encoding: input longer than slen, a non-canonical "negative zero", running off the end of the bit string, or not yielding exactly n coefficients.

Implementation

List<int>? decompress(Uint8List x, int slen, int n) {
  if (x.length > slen) {
    return null;
  }

  // Expand bytes to a bit list, MSB-first.
  final List<int> bits = <int>[];
  for (final int elt in x) {
    for (int i = 7; i >= 0; i--) {
      bits.add((elt >> i) & 1);
    }
  }

  // Strip trailing zero bits (the padding from compress).
  int end = bits.length;
  while (end > 0 && bits[end - 1] == 0) {
    end--;
  }

  final List<int> v = <int>[];
  int pos = 0;

  while (pos < end && v.length < n) {
    // Need at least a sign bit + 7 low bits before scanning the unary part.
    if (pos + 8 > end) {
      return null;
    }

    // Sign of the coefficient.
    final int sign = bits[pos] == 1 ? -1 : 1;

    // 7 low bits of abs(coef), MSB-first.
    int low = 0;
    for (int i = 1; i <= 7; i++) {
      low = (low << 1) | bits[pos + i];
    }

    // Count zeros for the unary high part; the loop stops on the first '1'.
    int i = 8;
    int high = 0;
    while (true) {
      if (pos + i >= end) {
        // Ran past the end without a terminating '1' (reference IndexError).
        return null;
      }
      if (bits[pos + i] != 0) {
        break;
      }
      i++;
      high++;
    }

    final int coef = sign * (low + (high << 7));

    // Enforce a unique encoding for coef == 0 (reject negative zero).
    if (coef == 0 && sign == -1) {
      return null;
    }

    v.add(coef);
    // Advance past the consumed bits, including the terminating '1' at `i`.
    pos += i + 1;
  }

  // The encoding must yield exactly n coefficients.
  if (v.length != n) {
    return null;
  }
  return v;
}