/**
 * A minimal animated GIF (GIF89a) encoder: one global palette of 256 colors,
 * frames of palette indices, LZW compression, and an infinite loop.
 */

/** Encode frames (width x height palette indices each) with palette (256 x RGB) and a delay per frame in 1/100 s. */
export function encodeGif(width: number, height: number, palette: Uint8Array, frames: Uint8Array[], delayCs: number): Uint8Array {
  const out = new ByteWriter();
  out.str('GIF89a');
  out.u16(width);
  out.u16(height);
  out.byte(0xf7); // global color table, 8 bits per color, 256 entries
  out.byte(0); // background color index
  out.byte(0); // pixel aspect ratio
  for (let i = 0; i < 768; i++) out.byte(palette[i] ?? 0);
  if (frames.length > 1) {
    // NETSCAPE2.0 application extension: loop forever
    out.bytes([0x21, 0xff, 0x0b]);
    out.str('NETSCAPE2.0');
    out.bytes([0x03, 0x01, 0x00, 0x00, 0x00]);
  }
  for (const f of frames) {
    out.bytes([0x21, 0xf9, 0x04, 0x00]); // graphic control extension, no transparency
    out.u16(delayCs);
    out.bytes([0x00, 0x00]);
    out.byte(0x2c); // image descriptor
    out.u16(0);
    out.u16(0);
    out.u16(width);
    out.u16(height);
    out.byte(0); // no local color table, not interlaced
    lzw(f, 8, out);
  }
  out.byte(0x3b);
  return out.result();
}

class ByteWriter {
  private buf = new Uint8Array(1 << 16);
  private n = 0;

  byte(b: number) {
    if (this.n === this.buf.length) {
      const nb = new Uint8Array(2 * this.buf.length);
      nb.set(this.buf);
      this.buf = nb;
    }
    this.buf[this.n++] = b;
  }
  bytes(bs: number[]) {
    for (const b of bs) this.byte(b);
  }
  u16(v: number) {
    this.byte(v & 0xff);
    this.byte((v >> 8) & 0xff);
  }
  str(s: string) {
    for (let i = 0; i < s.length; i++) this.byte(s.charCodeAt(i));
  }
  result(): Uint8Array {
    return this.buf.slice(0, this.n);
  }
}

/** LZW-compress indices into GIF image data sub-blocks. */
function lzw(indices: Uint8Array, minCodeSize: number, out: ByteWriter) {
  out.byte(minCodeSize);
  const clear = 1 << minCodeSize;
  const eoi = clear + 1;
  let codeSize = minCodeSize + 1;
  let next = eoi + 1;
  // dictionary: (prefix code << 8 | byte) -> code
  const dict = new Map<number, number>();
  const block: number[] = [];
  let acc = 0;
  let nbits = 0;
  const emit = (code: number) => {
    acc |= code << nbits;
    nbits += codeSize;
    while (nbits >= 8) {
      block.push(acc & 0xff);
      acc >>>= 8;
      nbits -= 8;
      if (block.length === 255) {
        out.byte(255);
        out.bytes(block);
        block.length = 0;
      }
    }
  };
  emit(clear);
  let prefix = indices[0];
  for (let i = 1; i < indices.length; i++) {
    const c = indices[i];
    const key = (prefix << 8) | c;
    const code = dict.get(key);
    if (code !== undefined) {
      prefix = code;
      continue;
    }
    emit(prefix);
    if (next < 4096) {
      dict.set(key, next++);
      // the decoder widens its codes one code later than the encoder adds the entry
      if (next > 1 << codeSize && codeSize < 12) codeSize++;
    } else {
      emit(clear);
      dict.clear();
      codeSize = minCodeSize + 1;
      next = eoi + 1;
    }
    prefix = c;
  }
  emit(prefix);
  emit(eoi);
  if (nbits > 0) block.push(acc & 0xff);
  if (block.length) {
    out.byte(block.length);
    out.bytes(block);
  }
  out.byte(0);
}