const MAX_BITS = 15;
const ZLIB_HEADER_BYTES = 2;
const ADLER_BYTES = 4;
const END_OF_BLOCK = 256;
const REPEAT_PREVIOUS = 16;
const REPEAT_ZERO_SHORT = 17;
const LENGTH_BASE = [
  3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258,
];
const LENGTH_EXTRA = [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];
const DIST_BASE = [
  1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
  8193, 12289, 16385, 24577,
];
const DIST_EXTRA = [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];
const CODE_LENGTH_ORDER = [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15];

type Huffman = { counts: Uint16Array; symbols: Uint16Array };

function buildHuffman(lengths: Uint8Array, offset: number, count: number): Huffman {
  const counts = new Uint16Array(MAX_BITS + 1);
  for (let index = 0; index < count; index++) counts[lengths[offset + index]]++;
  counts[0] = 0;
  const offsets = new Uint16Array(MAX_BITS + 1);
  for (let bits = 1; bits < MAX_BITS; bits++) offsets[bits + 1] = offsets[bits] + counts[bits];
  const symbols = new Uint16Array(count);
  for (let index = 0; index < count; index++) {
    const length = lengths[offset + index];
    if (length) symbols[offsets[length]++] = index;
  }
  return { counts, symbols };
}

const FIXED = (() => {
  const lengths = new Uint8Array(288 + 30);
  lengths.fill(8, 0, 144);
  lengths.fill(9, 144, 256);
  lengths.fill(7, 256, 280);
  lengths.fill(8, 280, 288);
  lengths.fill(5, 288, 318);
  return { lit: buildHuffman(lengths, 0, 288), dist: buildHuffman(lengths, 288, 30) };
})();

class Output {
  bytes = new Uint8Array(1024);
  length = 0;
  constructor(private readonly limit: number) {}
  ensure(extra: number) {
    const needed = this.length + extra;
    if (needed > this.limit) throw new Error("Inflated object exceeds size limit");
    if (needed <= this.bytes.byteLength) return;
    const grown = new Uint8Array(Math.max(needed, this.bytes.byteLength * 2));
    grown.set(this.bytes.subarray(0, this.length));
    this.bytes = grown;
  }
  push(byte: number) {
    this.ensure(1);
    this.bytes[this.length++] = byte;
  }
}

class BitReader {
  bitBuffer = 0;
  bitCount = 0;
  constructor(
    private readonly input: Uint8Array,
    public position: number,
  ) {}
  bits(count: number): number {
    while (this.bitCount < count) {
      if (this.position >= this.input.byteLength) throw new Error("Unexpected end of deflate stream");
      this.bitBuffer |= this.input[this.position++] << this.bitCount;
      this.bitCount += 8;
    }
    const value = this.bitBuffer & ((1 << count) - 1);
    this.bitBuffer >>>= count;
    this.bitCount -= count;
    return value;
  }
  align() {
    this.bitBuffer = 0;
    this.bitCount = 0;
  }
  decode(table: Huffman): number {
    let code = 0;
    let first = 0;
    let index = 0;
    for (let length = 1; length <= MAX_BITS; length++) {
      code |= this.bits(1);
      const count = table.counts[length];
      if (code - count < first) return table.symbols[index + (code - first)];
      index += count;
      first = (first + count) << 1;
      code <<= 1;
    }
    throw new Error("Invalid Huffman code");
  }
}

function inflateBlock(reader: BitReader, out: Output, lit: Huffman, dist: Huffman) {
  while (true) {
    const symbol = reader.decode(lit);
    if (symbol === END_OF_BLOCK) return;
    if (symbol < END_OF_BLOCK) {
      out.push(symbol);
      continue;
    }
    const lengthIndex = symbol - 257;
    if (lengthIndex >= LENGTH_BASE.length) throw new Error("Invalid length symbol");
    const length = LENGTH_BASE[lengthIndex] + reader.bits(LENGTH_EXTRA[lengthIndex]);
    const distIndex = reader.decode(dist);
    if (distIndex >= DIST_BASE.length) throw new Error("Invalid distance symbol");
    const distance = DIST_BASE[distIndex] + reader.bits(DIST_EXTRA[distIndex]);
    if (distance > out.length) throw new Error("Invalid back-reference distance");
    out.ensure(length);
    for (let index = 0; index < length; index++) {
      out.bytes[out.length] = out.bytes[out.length - distance];
      out.length++;
    }
  }
}

function dynamicTables(reader: BitReader): { lit: Huffman; dist: Huffman } {
  const literalCount = reader.bits(5) + 257;
  const distanceCount = reader.bits(5) + 1;
  const codeLengthCount = reader.bits(4) + 4;
  const codeLengths = new Uint8Array(19);
  for (let index = 0; index < codeLengthCount; index++) codeLengths[CODE_LENGTH_ORDER[index]] = reader.bits(3);
  const codeTable = buildHuffman(codeLengths, 0, 19);
  const lengths = new Uint8Array(literalCount + distanceCount);
  let index = 0;
  while (index < literalCount + distanceCount) {
    const symbol = reader.decode(codeTable);
    if (symbol < REPEAT_PREVIOUS) {
      lengths[index++] = symbol;
      continue;
    }
    let repeat: number;
    let value = 0;
    if (symbol === REPEAT_PREVIOUS) {
      if (index === 0) throw new Error("Invalid code length repeat");
      value = lengths[index - 1];
      repeat = 3 + reader.bits(2);
    } else if (symbol === REPEAT_ZERO_SHORT) {
      repeat = 3 + reader.bits(3);
    } else {
      repeat = 11 + reader.bits(7);
    }
    if (index + repeat > lengths.byteLength) throw new Error("Invalid code length repeat");
    lengths.fill(value, index, index + repeat);
    index += repeat;
  }
  return { lit: buildHuffman(lengths, 0, literalCount), dist: buildHuffman(lengths, literalCount, distanceCount) };
}

/**
 * Inflates one zlib stream starting at `offset` and reports how many input bytes it consumed.
 * Packfiles concatenate zlib streams without length prefixes, so the consumed count is what
 * locates the next object; platform decompressors do not expose it.
 */
export function inflateZlib(input: Uint8Array, offset: number, maxOutput: number): { data: Uint8Array; next: number } {
  const reader = new BitReader(input, offset + ZLIB_HEADER_BYTES);
  const out = new Output(maxOutput);
  let final = 0;
  while (!final) {
    final = reader.bits(1);
    const type = reader.bits(2);
    if (type === 0) {
      reader.align();
      const position = reader.position;
      if (position + 4 > input.byteLength) throw new Error("Unexpected end of deflate stream");
      const length = input[position] | (input[position + 1] << 8);
      const start = position + 4;
      if (start + length > input.byteLength) throw new Error("Unexpected end of deflate stream");
      out.ensure(length);
      out.bytes.set(input.subarray(start, start + length), out.length);
      out.length += length;
      reader.position = start + length;
    } else if (type === 1) {
      inflateBlock(reader, out, FIXED.lit, FIXED.dist);
    } else if (type === 2) {
      const tables = dynamicTables(reader);
      inflateBlock(reader, out, tables.lit, tables.dist);
    } else {
      throw new Error("Invalid deflate block type");
    }
  }
  return { data: out.bytes.slice(0, out.length), next: reader.position + ADLER_BYTES };
}