Made of little things.

/**
 * A bounded bzip2 decoder, for reading Powder Toy saves that arrive from relays.
 *
 * Saves are untrusted input: anyone can publish one. The decoder therefore
 * refuses rather than trusts. It stops at `maxOutput` bytes, never lets a
 * block grow past the size its stream header announces, throws when it reads
 * past the end of the input instead of spinning on missing bits, and checks
 * every block CRC. A hostile save costs at most one bounded decode and an
 * exception, never a hung frame.
 *
 * Format reference: Julian Seward's bzip2 1.0.x (decompress.c), written out
 * again here from the format, not copied.
 */

const BLOCK_MAGIC_HI = 0x314159, BLOCK_MAGIC_LO = 0x265359;
const END_MAGIC_HI = 0x177245, END_MAGIC_LO = 0x385090;
const MAX_GROUPS = 6, MIN_GROUPS = 2, GROUP_SIZE = 50, MAX_CODE_LEN = 20;

/** bzip2 uses the big-endian CRC-32 (polynomial 0x04C11DB7), unlike zlib. */
const CRC_TABLE = (() => {
  const table = new Uint32Array(256);
  for (let i = 0; i < 256; i++) {
    let c = i << 24;
    for (let k = 0; k < 8; k++) c = (c & 0x80000000) ? ((c << 1) ^ 0x04c11db7) : (c << 1);
    table[i] = c >>> 0;
  }
  return table;
})();

export class Bzip2Error extends Error {
  constructor(message) {
    super(message);
    this.name = 'Bzip2Error';
  }
}

function bitReader(bytes) {
  let index = 0, bitBuffer = 0, bitCount = 0;
  return {
    bits(n) {
      // n <= 24 per call keeps the buffer inside 32 bits.
      while (bitCount < n) {
        if (index >= bytes.length) throw new Bzip2Error('Unexpected end of data');
        bitBuffer = ((bitBuffer << 8) | bytes[index++]) >>> 0;
        bitCount += 8;
      }
      bitCount -= n;
      const value = (bitBuffer >>> bitCount) & ((1 << n) - 1);
      bitBuffer &= (1 << bitCount) - 1;
      return value;
    },
    bit() { return this.bits(1); },
  };
}

/** Canonical Huffman table as bzip2 builds it: limit/base/perm per code length. */
function huffmanTable(lengths, alphaSize) {
  let minLen = 32, maxLen = 0;
  for (let i = 0; i < alphaSize; i++) {
    if (lengths[i] > maxLen) maxLen = lengths[i];
    if (lengths[i] < minLen) minLen = lengths[i];
  }
  const perm = new Int32Array(alphaSize);
  let pp = 0;
  for (let len = minLen; len <= maxLen; len++) {
    for (let s = 0; s < alphaSize; s++) if (lengths[s] === len) perm[pp++] = s;
  }
  const base = new Int32Array(MAX_CODE_LEN + 2);
  for (let s = 0; s < alphaSize; s++) base[lengths[s] + 1]++;
  for (let i = 1; i < base.length; i++) base[i] += base[i - 1];
  const limit = new Int32Array(MAX_CODE_LEN + 1).fill(-1);
  let vec = 0;
  for (let len = minLen; len <= maxLen; len++) {
    vec += base[len + 1] - base[len];
    limit[len] = vec - 1;
    vec <<= 1;
  }
  for (let len = minLen + 1; len <= maxLen; len++) {
    base[len] = ((limit[len - 1] + 1) << 1) - base[len];
  }
  return { minLen, maxLen, limit, base, perm };
}

function decodeSymbol(reader, table) {
  let len = table.minLen;
  let code = reader.bits(len);
  while (true) {
    if (len > table.maxLen) throw new Bzip2Error('Bad Huffman code');
    if (code <= table.limit[len]) {
      const index = code - table.base[len];
      if (index < 0 || index >= table.perm.length) throw new Bzip2Error('Bad Huffman code');
      return table.perm[index];
    }
    len++;
    code = (code << 1) | reader.bit();
  }
}

/**
 * Decompress a complete bzip2 stream.
 * @param {Uint8Array} input
 * @param {{ maxOutput?: number }} [options] maxOutput defaults to 16 MiB.
 * @returns {Uint8Array}
 */
export function decompress(input, { maxOutput = 16 * 1024 * 1024 } = {}) {
  if (!(input instanceof Uint8Array)) throw new TypeError('bzip2 input must be a Uint8Array');
  const reader = bitReader(input);
  if (reader.bits(8) !== 0x42 || reader.bits(8) !== 0x5a || reader.bits(8) !== 0x68) {
    throw new Bzip2Error('Not a bzip2 stream');
  }
  const level = reader.bits(8) - 0x30;
  if (level < 1 || level > 9) throw new Bzip2Error('Bad block size');
  const blockMax = level * 100000;

  let out = new Uint8Array(Math.min(maxOutput, Math.max(1024, input.length * 4)));
  let outLength = 0;
  const grow = (need) => {
    if (need > maxOutput) throw new Bzip2Error('Decompressed data is larger than allowed');
    if (need <= out.length) return;
    const next = new Uint8Array(Math.min(maxOutput, Math.max(need, out.length * 2)));
    next.set(out.subarray(0, outLength));
    out = next;
  };

  const tt = new Uint32Array(blockMax);
  let combinedCrc = 0;

  while (true) {
    const magicHi = reader.bits(24), magicLo = reader.bits(24);
    const storedCrc = ((reader.bits(16) << 16) | reader.bits(16)) >>> 0;
    if (magicHi === END_MAGIC_HI && magicLo === END_MAGIC_LO) {
      if (storedCrc !== combinedCrc) throw new Bzip2Error('Stream CRC mismatch');
      break;
    }
    if (magicHi !== BLOCK_MAGIC_HI || magicLo !== BLOCK_MAGIC_LO) throw new Bzip2Error('Bad block header');
    if (reader.bit()) throw new Bzip2Error('Randomised blocks are not supported');
    const origPtr = reader.bits(24);

    // Which byte values occur in this block.
    const seqToUnseq = new Uint8Array(256);
    let inUse = 0;
    const groupsUsed = reader.bits(16);
    for (let i = 0; i < 16; i++) {
      if (!(groupsUsed & (0x8000 >>> i))) continue;
      const used = reader.bits(16);
      for (let j = 0; j < 16; j++) if (used & (0x8000 >>> j)) seqToUnseq[inUse++] = i * 16 + j;
    }
    if (inUse === 0) throw new Bzip2Error('Block uses no symbols');
    const alphaSize = inUse + 2;

    const groups = reader.bits(3);
    if (groups < MIN_GROUPS || groups > MAX_GROUPS) throw new Bzip2Error('Bad Huffman group count');
    const selectorCount = reader.bits(15);
    if (selectorCount < 1) throw new Bzip2Error('No selectors');
    const selectorMtf = [0, 1, 2, 3, 4, 5].slice(0, groups);
    const selectors = new Uint8Array(selectorCount);
    for (let i = 0; i < selectorCount; i++) {
      let j = 0;
      while (reader.bit()) {
        if (++j >= groups) throw new Bzip2Error('Bad selector');
      }
      const value = selectorMtf[j];
      for (; j > 0; j--) selectorMtf[j] = selectorMtf[j - 1];
      selectorMtf[0] = value;
      selectors[i] = value;
    }

    const tables = [];
    const lengths = new Uint8Array(alphaSize);
    for (let t = 0; t < groups; t++) {
      let length = reader.bits(5);
      for (let s = 0; s < alphaSize; s++) {
        while (true) {
          if (length < 1 || length > MAX_CODE_LEN) throw new Bzip2Error('Bad code length');
          if (!reader.bit()) break;
          length += reader.bit() ? -1 : 1;
        }
        lengths[s] = length;
      }
      tables.push(huffmanTable(lengths, alphaSize));
    }

    // Huffman -> RUNA/RUNB and MTF indices -> block bytes, counted per value.
    const mtf = new Uint8Array(256);
    for (let i = 0; i < 256; i++) mtf[i] = i;
    const counts = new Uint32Array(256);
    const eob = inUse + 1;
    let nblock = 0, groupIndex = -1, groupLeft = 0, table = null;
    let runLength = 0, runWeight = 1;
    const flushRun = () => {
      if (runLength === 0) return;
      if (nblock + runLength > blockMax) throw new Bzip2Error('Block is larger than announced');
      const byte = seqToUnseq[mtf[0]];
      counts[byte] += runLength;
      tt.fill(byte, nblock, nblock + runLength);
      nblock += runLength;
      runLength = 0;
      runWeight = 1;
    };
    while (true) {
      if (groupLeft === 0) {
        if (++groupIndex >= selectorCount) throw new Bzip2Error('Ran out of selectors');
        table = tables[selectors[groupIndex]];
        groupLeft = GROUP_SIZE;
      }
      groupLeft--;
      const symbol = decodeSymbol(reader, table);
      if (symbol <= 1) {
        // RUNA = 1*weight, RUNB = 2*weight, weights double: bijective base 2.
        runLength += (symbol + 1) * runWeight;
        runWeight *= 2;
        if (runLength > blockMax) throw new Bzip2Error('Run is longer than a block');
        continue;
      }
      flushRun();
      if (symbol === eob) break;
      if (nblock >= blockMax) throw new Bzip2Error('Block is larger than announced');
      const position = symbol - 1;
      const value = mtf[position];
      mtf.copyWithin(1, 0, position);
      mtf[0] = value;
      const byte = seqToUnseq[value];
      counts[byte]++;
      tt[nblock++] = byte;
    }
    if (origPtr >= nblock) throw new Bzip2Error('Bad BWT origin');

    // Inverse BWT with the T-vector packed into the high bits of tt.
    const cumulative = new Uint32Array(256);
    for (let i = 0, sum = 0; i < 256; i++) { cumulative[i] = sum; sum += counts[i]; }
    for (let i = 0; i < nblock; i++) {
      const byte = tt[i] & 0xff;
      tt[cumulative[byte]++] |= i << 8;
    }

    // Undo the initial run-length step (4 equal bytes, then a repeat count) while emitting.
    let pos = tt[origPtr] >>> 8;
    let crc = 0xffffffff;
    let last = -1, same = 0;
    const emit = (byte, times) => {
      grow(outLength + times);
      out.fill(byte, outLength, outLength + times);
      outLength += times;
      for (let k = 0; k < times; k++) crc = ((crc << 8) ^ CRC_TABLE[((crc >>> 24) ^ byte) & 0xff]) >>> 0;
    };
    for (let k = 0; k < nblock; k++) {
      const entry = tt[pos];
      const byte = entry & 0xff;
      pos = entry >>> 8;
      if (same === 4) {
        emit(last, byte);
        same = 0;
        last = -1;
        continue;
      }
      if (byte === last) same++;
      else { last = byte; same = 1; }
      emit(byte, 1);
    }
    crc = (~crc) >>> 0;
    if (crc !== storedCrc) throw new Bzip2Error('Block CRC mismatch');
    combinedCrc = (((combinedCrc << 1) | (combinedCrc >>> 31)) ^ crc) >>> 0;
    tt.fill(0, 0, nblock);
  }
  return out.slice(0, outLength);
}