// Lossy WebP (VP8 key frame) encoder. Each macroblock picks a 16x16 or
// 4x4 intra prediction and a chroma mode by prediction error; residuals go
// through the forward DCT / WHT and a dead-zone quantizer, and are coded
// with the default token probabilities. The reconstruction uses the
// decoder's own prediction and inverse transforms (on unfiltered pixels,
// like the decoder), so encoder and decoder stay in sync.

///|
/// VP8 boolean encoder (libwebp's VP8BitWriter).
priv struct VP8BoolWriter {
  mut range : Int32 // range - 1
  mut value : Int32
  mut run : Int32 // pending 0xFF bytes (carry propagation)
  mut nb_bits : Int32
  bytes : Array[Byte]
}

///|
fn VP8BoolWriter::new() -> VP8BoolWriter {
  { range: 254, value: 0, run: 0, nb_bits: -8, bytes: [], }
}

///|
fn VP8BoolWriter::flush(self : VP8BoolWriter) -> Unit {
  let s = 8 + self.nb_bits
  let bits = self.value >> s
  self.value -= bits << s
  self.nb_bits -= 8
  if (bits & 0xff) != 0xff {
    if (bits & 0x100) != 0 && self.bytes.length() > 0 {
      let i = self.bytes.length() - 1
      self.bytes[i] = (self.bytes[i].to_int() + 1).to_byte()
    }
    let fill = if (bits & 0x100) != 0 { b'\x00' } else { b'\xFF' }
    while self.run > 0 {
      self.bytes.push(fill)
      self.run -= 1
    }
    self.bytes.push((bits & 0xff).to_byte())
  } else {
    self.run += 1
  }
}

///|
fn VP8BoolWriter::put_bit(
  self : VP8BoolWriter,
  bit : Bool,
  prob : Int32,
) -> Bool {
  let split = (self.range * prob) >> 8
  if bit {
    self.value += split + 1
    self.range -= split + 1
  } else {
    self.range = split
  }
  if self.range < 127 {
    // Renormalize: shift so that range >= 127 again.
    let shift = (self.range + 1).clz() - 24
    self.range = ((self.range + 1) << shift) - 1
    self.value = self.value << shift
    self.nb_bits += shift
    if self.nb_bits > 0 {
      self.flush()
    }
  }
  bit
}

///|
fn VP8BoolWriter::put_bits(
  self : VP8BoolWriter,
  value : Int32,
  n : Int32,
) -> Unit {
  for i = n - 1; i >= 0; i = i - 1 {
    ignore(self.put_bit(((value >> i) & 1) == 1, 0x80))
  }
}

///|
/// Optional signed header value: presence flag, magnitude, sign.
fn VP8BoolWriter::put_signed(
  self : VP8BoolWriter,
  value : Int32,
  n : Int32,
) -> Unit {
  if !self.put_bit(value != 0, 0x80) {
    return
  }
  let m = if value < 0 { -value } else { value }
  self.put_bits(m, n)
  ignore(self.put_bit(value < 0, 0x80))
}

///|
fn VP8BoolWriter::finish(self : VP8BoolWriter) -> Bytes {
  self.put_bits(0, 9 - self.nb_bits)
  self.nb_bits = 0
  self.flush()
  Bytes::from_array(FixedArray::from_array(self.bytes))
}

///|
/// Scratch for `vp8_fdct` / `vp8_fwht` (encoding is single-threaded).
let vp8_fdct_tmp : FixedArray[Int32] = FixedArray::make(16, 0)

///|
/// Forward 4x4 DCT of `src - ref` (both 32-stride) into `out` (libwebp's
/// FTransform).
fn vp8_fdct(
  src : FixedArray[Int32],
  s : Int32,
  pred : FixedArray[Int32],
  p : Int32,
  out : FixedArray[Int32],
  o : Int32,
) -> Unit {
  let tmp = vp8_fdct_tmp
  for i in 0..<4 {
    let d0 = src[s + i * 32] - pred[p + i * 32]
    let d1 = src[s + i * 32 + 1] - pred[p + i * 32 + 1]
    let d2 = src[s + i * 32 + 2] - pred[p + i * 32 + 2]
    let d3 = src[s + i * 32 + 3] - pred[p + i * 32 + 3]
    let a0 = d0 + d3
    let a1 = d1 + d2
    let a2 = d1 - d2
    let a3 = d0 - d3
    tmp[i * 4] = (a0 + a1) * 8
    tmp[i * 4 + 1] = (a2 * 2217 + a3 * 5352 + 1812) >> 9
    tmp[i * 4 + 2] = (a0 - a1) * 8
    tmp[i * 4 + 3] = (a3 * 2217 - a2 * 5352 + 937) >> 9
  }
  for i in 0..<4 {
    let a0 = tmp[i] + tmp[12 + i]
    let a1 = tmp[4 + i] + tmp[8 + i]
    let a2 = tmp[4 + i] - tmp[8 + i]
    let a3 = tmp[i] - tmp[12 + i]
    out[o + i] = (a0 + a1 + 7) >> 4
    out[o + 4 + i] = ((a2 * 2217 + a3 * 5352 + 12000) >> 16) +
      (if a3 != 0 { 1 } else { 0 })
    out[o + 8 + i] = (a0 - a1 + 7) >> 4
    out[o + 12 + i] = (a3 * 2217 - a2 * 5352 + 51000) >> 16
  }
}

///|
/// Forward WHT of the 16 DC coefficients (at `coeffs[n * 16]`).
fn vp8_fwht(coeffs : FixedArray[Int32], out : FixedArray[Int32]) -> Unit {
  let tmp = vp8_fdct_tmp
  for i in 0..<4 {
    let a0 = coeffs[(i * 4 + 0) * 16] + coeffs[(i * 4 + 2) * 16]
    let a1 = coeffs[(i * 4 + 1) * 16] + coeffs[(i * 4 + 3) * 16]
    let a2 = coeffs[(i * 4 + 1) * 16] - coeffs[(i * 4 + 3) * 16]
    let a3 = coeffs[(i * 4 + 0) * 16] - coeffs[(i * 4 + 2) * 16]
    tmp[i * 4] = a0 + a1
    tmp[i * 4 + 1] = a3 + a2
    tmp[i * 4 + 2] = a3 - a2
    tmp[i * 4 + 3] = a0 - a1
  }
  for i in 0..<4 {
    let a0 = tmp[i] + tmp[8 + i]
    let a1 = tmp[4 + i] + tmp[12 + i]
    let a2 = tmp[4 + i] - tmp[12 + i]
    let a3 = tmp[i] - tmp[8 + i]
    out[i] = (a0 + a1) >> 1
    out[4 + i] = (a3 + a2) >> 1
    out[8 + i] = (a3 - a2) >> 1
    out[12 + i] = (a0 - a1) >> 1
  }
}

///|
/// Quantize 16 coefficients (raster order) to zigzag-ordered levels with a
/// dead zone, and write the dequantized values back (raster order) for the
/// reconstruction. Returns the zigzag index of the last non-zero level.
fn vp8_quantize(
  coeffs : FixedArray[Int32],
  o : Int32,
  dc_q : Int32,
  ac_q : Int32,
  first : Int32,
  levels : FixedArray[Int32],
  lo : Int32,
) -> Int32 {
  let mut last = -1
  // Rounding bias: a bit under 1/2 (DC) or 1/3 (AC) of a step. Levels
  // below the zero threshold skip the division.
  let ac_bias = ac_q * 11 / 32
  let ac_zero = ac_q - ac_bias
  if first == 0 {
    let c = coeffs[o]
    let a = if c < 0 { -c } else { c }
    let dc_bias = dc_q * 7 / 16
    if a + dc_bias < dc_q {
      levels[lo] = 0
      coeffs[o] = 0
    } else {
      let l = vp8_min_int((a + dc_bias) / dc_q, 2047)
      let v = if c < 0 { -l } else { l }
      levels[lo] = v
      coeffs[o] = v * dc_q
      last = 0
    }
  } else {
    // The DC position belongs to the Y2 block; the caller keeps it.
    levels[lo] = 0
  }
  for n in 1..<16 {
    let pos = vp8_zigzag[n]
    let c = coeffs[o + pos]
    let a = if c < 0 { -c } else { c }
    if a < ac_zero {
      levels[lo + n] = 0
      coeffs[o + pos] = 0
      continue
    }
    let l = vp8_min_int((a + ac_bias) / ac_q, 2047)
    let v = if c < 0 { -l } else { l }
    levels[lo + n] = v
    coeffs[o + pos] = v * ac_q
    last = n
  }
  last
}

///|
fn vp8_min_int(a : Int32, b : Int32) -> Int32 {
  if a < b {
    a
  } else {
    b
  }
}

///|
/// Record one token bit: `code` < 1056 is an (updatable) coefficient
/// probability index, otherwise a fixed probability 1056 + p.
fn vp8_rec(ev : Array[Int32], bit : Bool, code : Int32) -> Bool {
  ev.push(code * 2 + (if bit { 1 } else { 0 }))
  bit
}

///|
/// log2(x) * 256 for 1 <= x <= 256 (fixed point).
fn vp8_log2_fix(x : Int32) -> Int32 {
  let mut ip = 0
  while 2 << ip <= x {
    ip += 1
  }
  // Mantissa in [1, 2) as 16.16, refined by squaring.
  let mut m = x << 16 >> ip
  let mut frac = 0
  for k in 0..<8 {
    m = ((m.to_int64() * m.to_int64()) >> 16).to_int()
    if m >= 2 << 16 {
      m = m >> 1
      frac = frac | (1 << (7 - k))
    }
  }
  ip * 256 + frac
}

///|
/// Cost (in 1/256 bit) of coding `bit` with probability `p` / 256 of 0.
fn vp8_bit_cost(bit : Bool, p : Int32) -> Int32 {
  if bit {
    2048 - vp8_log2_fix(256 - p)
  } else {
    2048 - vp8_log2_fix(p)
  }
}

///|
/// Record the tokens of one block (zigzag levels, from `first`). Returns
/// whether any coefficient was coded (the neighbor context).
fn vp8_put_coeffs(
  ev : Array[Int32],
  t : Int32,
  ctx : Int32,
  levels : FixedArray[Int32],
  lo : Int32,
  first : Int32,
  last : Int32,
) -> Bool {
  let base = t * 8 * 33
  let mut n = first
  let mut p = base + vp8_bands[n] * 33 + ctx * 11
  if !vp8_rec(ev, last >= 0, p) {
    return false
  }
  while n < 16 {
    let c = levels[lo + n]
    n += 1
    let v = if c < 0 { -c } else { c }
    if !vp8_rec(ev, v != 0, p + 1) {
      p = base + vp8_bands[n] * 33
      continue
    }
    if !vp8_rec(ev, v > 1, p + 2) {
      p = base + vp8_bands[n] * 33 + 11
    } else {
      if !vp8_rec(ev, v > 4, p + 3) {
        if vp8_rec(ev, v != 2, p + 4) {
          ignore(vp8_rec(ev, v == 4, p + 5))
        }
      } else if !vp8_rec(ev, v > 10, p + 6) {
        if !vp8_rec(ev, v > 6, p + 7) {
          ignore(vp8_rec(ev, v == 6, 1056 + 159))
        } else {
          ignore(vp8_rec(ev, v >= 9, 1056 + 165))
          ignore(vp8_rec(ev, (v & 1) == 0, 1056 + 145))
        }
      } else {
        let (cat, rest) = if v < 3 + (8 << 1) {
          ignore(vp8_rec(ev, false, p + 8))
          ignore(vp8_rec(ev, false, p + 9))
          (0, v - (3 + (8 << 0)))
        } else if v < 3 + (8 << 2) {
          ignore(vp8_rec(ev, false, p + 8))
          ignore(vp8_rec(ev, true, p + 9))
          (1, v - (3 + (8 << 1)))
        } else if v < 3 + (8 << 3) {
          ignore(vp8_rec(ev, true, p + 8))
          ignore(vp8_rec(ev, false, p + 10))
          (2, v - (3 + (8 << 2)))
        } else {
          ignore(vp8_rec(ev, true, p + 8))
          ignore(vp8_rec(ev, true, p + 10))
          (3, v - (3 + (8 << 3)))
        }
        let tab = vp8_cat3456[cat]
        for k in 0..> (tab.length() - 1 - k)) & 1
          ignore(vp8_rec(ev, bit == 1, 1056 + tab[k]))
        }
      }
      p = base + vp8_bands[n] * 33 + 22
    }
    ignore(vp8_rec(ev, c < 0, 1056 + 0x80))
    if n == 16 || !vp8_rec(ev, n <= last, p) {
      return true
    }
  }
  true
}

///|
/// (probability index, bit) path of every 4x4 intra mode in the mode tree.
let vp8_bmode_paths : FixedArray[Array[(Int32, Int32)]] = {
  let paths = FixedArray::make(10, [])
  fn walk(node : Int32, path : Array[(Int32, Int32)]) -> Unit {
    for bit in 0..<2 {
      let v = vp8_ymodes_intra4[2 * node + bit]
      let p = path.copy()
      p.push((node, bit))
      if v <= 0 {
        paths[-v] = p
      } else {
        walk(v, p)
      }
    }
  }
  walk(0, [])
  paths
}

///|
fn vp8_sse(
  a : FixedArray[Int32],
  ao : Int32,
  b : FixedArray[Int32],
  bo : Int32,
  size : Int32,
) -> Int32 {
  let mut s = 0
  for y in 0.. Int32 {
  vp8_quality_q[quality.clamp(min=0, max=100)]
}

///|
/// Encode a lossy WebP (VP8). `quality` is 0-100 (higher = better and
/// larger). Alpha, when present, is stored losslessly in an ALPH chunk.
pub fn encode_webp_lossy(
  img : ImageData,
  quality~ : Int32 = 75,
) -> Bytes raise EncodeError {
  validate_rgba8_image(img)
  let w = img.width
  let h = img.height
  if w > 16383 || h > 16383 {
    raise InvalidDimensions(
      "WebP lossy dimensions must be <= 16383: " +
      w.to_string() +
      "x" +
      h.to_string(),
    )
  }
  let vp8 = vp8_encode_frame(img, vp8_quality_to_q(quality))
  let mut has_alpha = false
  for i in 0..<(w * h) {
    if img.data[i * 4 + 3] != b'\xFF' {
      has_alpha = true
      break
    }
  }
  let body = Buffer()
  for c in "WEBP" {
    body.write_byte(c.to_int().to_byte())
  }
  if has_alpha {
    let vp8x = Buffer()
    vp8x.write_byte(b'\x10')
    webp_put_le(vp8x, 0, 3)
    webp_put_le(vp8x, w - 1, 3)
    webp_put_le(vp8x, h - 1, 3)
    webp_put_chunk(body, "VP8X", vp8x.to_bytes())
    webp_put_chunk(body, "ALPH", webp_encode_alpha(img))
  }
  webp_put_chunk(body, "VP8 ", vp8)
  let b = body.to_bytes()
  let out = Buffer()
  for c in "RIFF" {
    out.write_byte(c.to_int().to_byte())
  }
  webp_put_le(out, b.length(), 4)
  out.write_bytes(b)
  out.to_bytes()
}

///|
/// ALPH chunk payload: lossless (VP8L, alpha in the green channel) after
/// the spatial filter (none / horizontal / vertical / gradient) that gives
/// the smallest stream.
fn webp_encode_alpha(img : ImageData) -> Bytes {
  let w = img.width
  let h = img.height
  let a = FixedArray::makei(w * h, fn(i) { img.data[i * 4 + 3].to_int() })
  let mut best : Bytes? = None
  for filter in 0..<4 {
    let argb = FixedArray::make(w * h, 0)
    for y in 0.. ()
      _ => best = Some(b)
    }
  }
  best.unwrap()
}

///|
/// libwebp's RGB -> YUV (16-bit fixed point; U / V from 2x2 sums).
fn vp8_rgb_to_yuv(
  img : ImageData,
  mb_w : Int32,
  mb_h : Int32,
) -> (FixedArray[Int32], FixedArray[Int32], FixedArray[Int32]) {
  let w = img.width
  let h = img.height
  let ys = mb_w * 16
  let uvs = mb_w * 8
  let yp = FixedArray::make(ys * mb_h * 16, 0)
  let up = FixedArray::make(uvs * mb_h * 8, 0)
  let vp = FixedArray::make(uvs * mb_h * 8, 0)
  // Edge pixels are replicated into the macroblock padding.
  let px = fn(x : Int32, y : Int32, c : Int32) -> Int32 {
    let xx = if x < w { x } else { w - 1 }
    let yy = if y < h { y } else { h - 1 }
    img.data[(yy * w + xx) * 4 + c].to_int()
  }
  for y in 0..<(mb_h * 16) {
    for x in 0..<(mb_w * 16) {
      let r = px(x, y, 0)
      let g = px(x, y, 1)
      let b = px(x, y, 2)
      yp[y * ys + x] = (
          16839 * r + 33059 * g + 6420 * b + (1 << 15) + (16 << 16)
        ) >>
        16
    }
  }
  for y in 0..<(mb_h * 8) {
    for x in 0..<(mb_w * 8) {
      let mut r = 0
      let mut g = 0
      let mut b = 0
      for dy in 0..<2 {
        for dx in 0..<2 {
          r += px(x * 2 + dx, y * 2 + dy, 0)
          g += px(x * 2 + dx, y * 2 + dy, 1)
          b += px(x * 2 + dx, y * 2 + dy, 2)
        }
      }
      let clip_uv = fn(v : Int32) {
        vp8_clip((v + (1 << 17) + (128 << 18)) >> 18, 255)
      }
      up[y * uvs + x] = clip_uv(-9719 * r - 19081 * g + 28800 * b)
      vp[y * uvs + x] = clip_uv(28800 * r - 24116 * g - 4684 * b)
    }
  }
  (yp, up, vp)
}

///|
/// 16x16 / chroma modes (best by prediction error) that get the full RD
/// evaluation.
let vp8_mode_candidates = 4

///|
/// Modes 0..n-1 sorted by `err(mode)` (ascending).
fn vp8_rank_modes(n : Int32, err : (Int32) -> Int32) -> Array[Int32] {
  let e = FixedArray::makei(n, fn(m) { err(m) })
  let r = Array::makei(n, fn(i) { i })
  r.sort_by(fn(a, b) { e[a] - e[b] })
  r
}

///|
/// 4x4 modes (best by prediction error) that get the full RD evaluation.
let vp8_i4_candidates = 4

///|
/// Lambda scale for the rate-distortion mode decisions.
let vp8_lambda_scale = 4

///|
/// Approximate bits (1/256) of each 16x16 / chroma mode in its tree.
let vp8_i16_mode_bits : FixedArray[Int32] = [512, 512, 512, 512]

///|
let vp8_uv_mode_bits : FixedArray[Int32] = [256, 768, 512, 768]

///|
/// Cost tables (1/256 bit) of coding 0 / 1 with probability p / 256.
let vp8_cost0 : FixedArray[Int32] = FixedArray::makei(256, fn(p) {
  vp8_bit_cost(false, if p < 1 { 1 } else { p })
})

///|
let vp8_cost1 : FixedArray[Int32] = FixedArray::makei(256, fn(p) {
  vp8_bit_cost(true, if p < 1 { 1 } else { p })
})

///|
/// Bits (1/256) to code one block with the default probabilities: the
/// token tree of `vp8_put_coeffs`, summing costs instead of recording.
fn vp8_token_cost(
  levels : FixedArray[Int32],
  lo : Int32,
  t : Int32,
  ctx : Int32,
  first : Int32,
  last : Int32,
) -> Int32 {
  let proba = vp8_coeffs_proba0
  let c0 = vp8_cost0
  let c1 = vp8_cost1
  let base = t * 8 * 33
  let mut n = first
  let mut p = base + vp8_bands[n] * 33 + ctx * 11
  if last < 0 {
    return c0[proba[p]]
  }
  let mut cost = c1[proba[p]]
  while n < 16 {
    let c = levels[lo + n]
    n += 1
    let v = if c < 0 { -c } else { c }
    if v == 0 {
      cost += c0[proba[p + 1]]
      p = base + vp8_bands[n] * 33
      continue
    }
    cost += c1[proba[p + 1]]
    if v == 1 {
      cost += c0[proba[p + 2]]
      p = base + vp8_bands[n] * 33 + 11
    } else {
      cost += c1[proba[p + 2]]
      if v <= 4 {
        cost += c0[proba[p + 3]]
        if v == 2 {
          cost += c0[proba[p + 4]]
        } else {
          cost += c1[proba[p + 4]] +
            (if v == 4 { c1[proba[p + 5]] } else { c0[proba[p + 5]] })
        }
      } else if v <= 10 {
        cost += c1[proba[p + 3]] + c0[proba[p + 6]]
        if v <= 6 {
          cost += c0[proba[p + 7]] + (if v == 6 { c1[159] } else { c0[159] })
        } else {
          cost += c1[proba[p + 7]] +
            (if v >= 9 { c1[165] } else { c0[165] }) +
            (if (v & 1) == 0 { c1[145] } else { c0[145] })
        }
      } else {
        cost += c1[proba[p + 3]] + c1[proba[p + 6]]
        // Extra bits of the categories (about one bit each, plus the
        // category bits).
        let (cat_cost, nbits) = if v < 3 + (8 << 1) {
          (c0[proba[p + 8]] + c0[proba[p + 9]], 3)
        } else if v < 3 + (8 << 2) {
          (c0[proba[p + 8]] + c1[proba[p + 9]], 4)
        } else if v < 3 + (8 << 3) {
          (c1[proba[p + 8]] + c0[proba[p + 10]], 5)
        } else {
          (c1[proba[p + 8]] + c1[proba[p + 10]], 11)
        }
        cost += cat_cost + nbits * 256
      }
      p = base + vp8_bands[n] * 33 + 22
    }
    cost += 256 // sign
    if n == 16 {
      return cost
    }
    if n > last {
      return cost + c0[proba[p]]
    }
    cost += c1[proba[p]]
  }
  cost
}

///|
/// Token bits of an i16 macroblock (Y2 + 16 AC blocks), propagating the
/// non-zero contexts like the decoder. `ctx_y`: 4 top + 4 left flags.
fn vp8_cost_i16(
  levels : FixedArray[Int32],
  lasts : FixedArray[Int32],
  ctx_y : FixedArray[Int32],
  dc_ctx : Int32,
) -> Int32 {
  let mut c = vp8_token_cost(levels, 0, 1, dc_ctx, 0, lasts[0])
  let t = ctx_y.copy()
  for n in 0..<16 {
    let bx = n & 3
    let by = n >> 2
    let last = if lasts[n + 1] >= 1 { lasts[n + 1] } else { -1 }
    c += vp8_token_cost(levels, (n + 1) * 16, 0, t[bx] + t[4 + by], 1, last)
    let f = if last >= 1 { 1 } else { 0 }
    t[bx] = f
    t[4 + by] = f
  }
  c
}

///|
/// Token bits of the 8 chroma blocks.
fn vp8_cost_uv(
  levels : FixedArray[Int32],
  lasts : FixedArray[Int32],
  top_nz : FixedArray[Int32],
  left_nz : FixedArray[Int32],
  mb_x : Int32,
) -> Int32 {
  let t = FixedArray::make(8, 0)
  for k in 0..<4 {
    t[k] = top_nz[mb_x * 9 + 4 + k]
    t[4 + k] = left_nz[4 + k]
  }
  let mut c = 0
  for k in 0..<8 {
    let ch = k >> 2
    let kk = k & 3
    let ti = ch * 2 + (kk & 1)
    let li = 4 + ch * 2 + (kk >> 1)
    c += vp8_token_cost(
      levels,
      (17 + k) * 16,
      2,
      t[ti] + t[li],
      0,
      lasts[17 + k],
    )
    let f = if lasts[17 + k] >= 0 { 1 } else { 0 }
    t[ti] = f
    t[li] = f
  }
  c
}

///|
/// Work buffers for the residual coders, allocated once per frame.
priv struct VP8EncScratch {
  blk : FixedArray[Int32]
  tmp : FixedArray[Int32]
  wht : FixedArray[Int32]
  whtl : FixedArray[Int32]
  cb : FixedArray[Int32]
}

///|
fn VP8EncScratch::new() -> VP8EncScratch {
  {
    blk: FixedArray::make(256, 0),
    tmp: FixedArray::make(256, 0),
    wht: FixedArray::make(16, 0),
    whtl: FixedArray::make(256, 0),
    cb: FixedArray::make(128, 0),
  }
}

///|
/// Code the 16x16 luma residual of `buf` (holding the prediction): forward
/// DCT / WHT, quantization into `levels[0..17*16)` / `lasts[0..17)`, and the
/// decoder's reconstruction back into `buf`. `qm`: y1 dc / ac, y2 dc / ac,
/// uv dc / ac.
fn vp8_code_i16(
  src : FixedArray[Int32],
  buf : FixedArray[Int32],
  yd : Int32,
  qm : Array[Int32],
  levels : FixedArray[Int32],
  lasts : FixedArray[Int32],
  ws : VP8EncScratch,
) -> Unit {
  let blk = ws.blk
  for n in 0..<16 {
    let d = yd + (n & 3) * 4 + (n >> 2) * 128
    vp8_fdct(src, d, buf, d, blk, n * 16)
  }
  let tmp = ws.tmp
  for n in 0..<16 {
    tmp[n * 16] = blk[n * 16]
  }
  let wht = ws.wht
  vp8_fwht(tmp, wht)
  lasts[0] = vp8_quantize(wht, 0, qm[2], qm[3], 0, levels, 0)
  for n in 0..<16 {
    lasts[n + 1] = vp8_quantize(
      blk,
      n * 16,
      qm[0],
      qm[1],
      1,
      levels,
      (n + 1) * 16,
    )
  }
  // Reconstruct exactly like the decoder.
  if lasts[0] > 0 {
    let whtl = ws.whtl
    vp8_transform_wht(wht, whtl)
    for n in 0..<16 {
      blk[n * 16] = whtl[n * 16]
    }
  } else {
    let dc0 = (wht[0] + 3) >> 3
    for n in 0..<16 {
      blk[n * 16] = dc0
    }
  }
  for n in 0..<16 {
    let d = yd + (n & 3) * 4 + (n >> 2) * 128
    if lasts[n + 1] >= 1 || blk[n * 16] != 0 {
      vp8_transform(blk, n * 16, buf, d)
    }
  }
}

///|
/// Code the U / V residuals of `buf` (holding the predictions) into
/// `levels[17*16..)` / `lasts[17..25)` and reconstruct them.
fn vp8_code_uv(
  src : FixedArray[Int32],
  buf : FixedArray[Int32],
  qm : Array[Int32],
  levels : FixedArray[Int32],
  lasts : FixedArray[Int32],
  ws : VP8EncScratch,
) -> Unit {
  let cb = ws.cb
  for k in 0..<8 {
    let base = if k < 4 { vp8_u_off } else { vp8_v_off }
    let kk = k & 3
    let d = base + (kk & 1) * 4 + (kk >> 1) * 128
    vp8_fdct(src, d, buf, d, cb, k * 16)
    lasts[17 + k] = vp8_quantize(
      cb,
      k * 16,
      qm[4],
      qm[5],
      0,
      levels,
      (17 + k) * 16,
    )
  }
  let any_u = lasts[17] >= 0 ||
    lasts[18] >= 0 ||
    lasts[19] >= 0 ||
    lasts[20] >= 0
  let any_v = lasts[21] >= 0 ||
    lasts[22] >= 0 ||
    lasts[23] >= 0 ||
    lasts[24] >= 0
  for k in 0..<8 {
    let base = if k < 4 { vp8_u_off } else { vp8_v_off }
    let kk = k & 3
    let d = base + (kk & 1) * 4 + (kk >> 1) * 128
    if (k < 4 && any_u) || (k >= 4 && any_v) {
      vp8_transform(cb, k * 16, buf, d)
    }
  }
}

///|
fn vp8_encode_frame(img : ImageData, q : Int32) -> Bytes {
  let w = img.width
  let h = img.height
  let mb_w = (w + 15) >> 4
  let mb_h = (h + 15) >> 4
  let (sy, su, sv) = vp8_rgb_to_yuv(img, mb_w, mb_h)
  let ys = mb_w * 16
  let uvs = mb_w * 8
  // Dequantization steps, as the decoder computes them for base index q.
  let y1_dc = vp8_dc_table[q]
  let y1_ac = vp8_ac_table[q]
  let y2_dc = vp8_dc_table[q] * 2
  let y2_ac = {
    let v = (vp8_ac_table[q] * 101581) >> 16
    if v < 8 {
      8
    } else {
      v
    }
  }
  let uv_dc = vp8_dc_table[if q > 117 { 117 } else { q }]
  let uv_ac = vp8_ac_table[q]
  // Rate-distortion lambda (squared error per bit).
  let lambda = vp8_lambda_scale * y1_ac * y1_ac / 128 + 1
  let qm = [y1_dc, y1_ac, y2_dc, y2_ac, uv_dc, uv_ac]
  let tlevels = FixedArray::make(25 * 16, 0)
  let tlasts = FixedArray::make(25, -1)
  let ws = VP8EncScratch::new()
  let modes_bw = VP8BoolWriter::new()
  let events : Array[Int32] = []
  // Decoder-identical working state.
  let yuv = FixedArray::make(32 * 17 + 32 * 9, 0)
  let top = FixedArray::make(mb_w * 32, 0)
  let top_nz = FixedArray::make(mb_w * 9, 0) // 4 Y + 2 U + 2 V + DC
  let left_nz = FixedArray::make(9, 0)
  let src = FixedArray::make(32 * 17 + 32 * 9, 0)
  let pred = FixedArray::make(32 * 17 + 32 * 9, 0)
  let coeffs = FixedArray::make(384, 0)
  let levels = FixedArray::make(25 * 16, 0)
  let lasts = FixedArray::make(25, -1)
  let yd = vp8_y_off
  let ud = vp8_u_off
  let vd = vp8_v_off
  let imodes = FixedArray::make(16, 0)
  // Pass 1 collects per-macroblock decisions and tokens into two writers;
  // the frame header (with the skip probability) is written afterwards,
  // so record the mode data and replay it.
  let mb_info : Array[(Bool, Int32, FixedArray[Int32], Int32, Bool)] = []
  for mb_y in 0.. 0 {
      yuv[yd - 33] = 129
      yuv[ud - 33] = 129
      yuv[vd - 33] = 129
    } else {
      for i in 0..<21 {
        yuv[yd - 33 + i] = 127
      }
      for i in 0..<9 {
        yuv[ud - 33 + i] = 127
        yuv[vd - 33 + i] = 127
      }
    }
    left_nz.fill(0)
    for mb_x in 0.. 0 {
        for j in -1..<16 {
          for i in 0..<4 {
            yuv[yd + j * 32 - 4 + i] = yuv[yd + j * 32 + 12 + i]
          }
        }
        for j in -1..<8 {
          for i in 0..<4 {
            yuv[ud + j * 32 - 4 + i] = yuv[ud + j * 32 + 4 + i]
            yuv[vd + j * 32 - 4 + i] = yuv[vd + j * 32 + 4 + i]
          }
        }
      }
      let tb = mb_x * 32
      if mb_y > 0 {
        for i in 0..<16 {
          yuv[yd - 32 + i] = top[tb + i]
        }
        for i in 0..<8 {
          yuv[ud - 32 + i] = top[tb + 16 + i]
          yuv[vd - 32 + i] = top[tb + 24 + i]
        }
        let tr = yd - 32 + 16
        if mb_x >= mb_w - 1 {
          for i in 0..<4 {
            yuv[tr + i] = top[tb + 15]
          }
        } else {
          for i in 0..<4 {
            yuv[tr + i] = top[tb + 32 + i]
          }
        }
      }
      let tr = yd - 32 + 16
      for k in 1..<4 {
        for i in 0..<4 {
          yuv[tr + k * 128 + i] = yuv[tr + i]
        }
      }
      // Source block in the same layout.
      for j in 0..<16 {
        for i in 0..<16 {
          src[yd + j * 32 + i] = sy[(mb_y * 16 + j) * ys + mb_x * 16 + i]
        }
      }
      for j in 0..<8 {
        for i in 0..<8 {
          src[ud + j * 32 + i] = su[(mb_y * 8 + j) * uvs + mb_x * 8 + i]
          src[vd + j * 32 + i] = sv[(mb_y * 8 + j) * uvs + mb_x * 8 + i]
        }
      }
      // Mode decisions are rate-distortion optimized: each candidate is
      // quantized and reconstructed (in `pred`, which shares the borders
      // with `yuv`) and scored as SSE * 256 + lambda * token bits (1/256).
      yuv.blit_to(pred, len=yuv.length())
      let ctx_y = FixedArray::make(8, 0) // 4 top + 4 left non-zero flags
      let load_ctx = fn() {
        for k in 0..<4 {
          ctx_y[k] = top_nz[mb_x * 9 + k]
          ctx_y[4 + k] = left_nz[k]
        }
      }
      // --- Luma 16x16.
      let r16 = vp8_rank_modes(4, fn(mode) {
        vp8_predict_block(pred, yd, 16, vp8_check_mode(mb_x, mb_y, mode))
        vp8_sse(src, yd, pred, yd, 16)
      })
      let mut best16 = 0
      let mut best16_cost = 0x7fffffffffffffffL
      for ri in 0..> 2) * 128
        let bx = n & 3
        let by = n >> 2
        let ctx = ctx_y[bx] + ctx_y[4 + by]
        // Rank the modes by prediction error; the best few get the full
        // rate-distortion evaluation.
        for mode in 0..<10 {
          vp8_predict4(pred, d, mode)
          let e = vp8_sse(src, d, pred, d, 4) * 256 +
            lambda * vp8_bmode_paths[mode].length() * 256
          rank_cost[mode] = e
          rank[mode] = mode
        }
        rank.sort_by(fn(a, b) { rank_cost[a] - rank_cost[b] })
        let mut best = 0
        let mut best_cost = 0x7fffffffffffffffL
        for ri in 0..= 0 {
            vp8_transform(coeffs, 0, pred, d)
          }
          let r = vp8_token_cost(tl, 0, 3, ctx, 0, last) +
            vp8_bmode_paths[mode].length() * 256
          let c = vp8_sse(src, d, pred, d, 4).to_int64() * 256L +
            lambda.to_int64() * r.to_int64()
          if c < best_cost {
            best_cost = c
            best = mode
          }
        }
        imodes[n] = best
        cost4 += best_cost
        vp8_predict4(yuv, d, best)
        vp8_fdct(src, d, yuv, d, coeffs, 0)
        last4[n] = vp8_quantize(coeffs, 0, y1_dc, y1_ac, 0, lv4, n * 16)
        if last4[n] >= 0 {
          vp8_transform(coeffs, 0, yuv, d)
        }
        let f = if last4[n] >= 0 { 1 } else { 0 }
        ctx_y[bx] = f
        ctx_y[4 + by] = f
        // Later subblocks predict from this reconstruction.
        for yy in 0..<4 {
          for xx in 0..<4 {
            pred[d + yy * 32 + xx] = yuv[d + yy * 32 + xx]
          }
        }
        if cost4 >= best16_cost {
          break
        }
      }
      let use_i4 = cost4 < best16_cost
      if !use_i4 {
        save.blit_to(yuv, len=yuv.length())
      }
      levels.fill(0)
      lasts.fill(-1)
      if use_i4 {
        for n in 0..<16 {
          for k in 0..<16 {
            levels[(n + 1) * 16 + k] = lv4[n * 16 + k]
          }
          lasts[n + 1] = last4[n]
        }
      } else {
        vp8_predict_block(yuv, yd, 16, vp8_check_mode(mb_x, mb_y, best16))
        vp8_code_i16(src, yuv, yd, qm, levels, lasts, ws)
      }
      // --- Chroma (U and V share the mode).
      let ruv = vp8_rank_modes(4, fn(mode) {
        let m = vp8_check_mode(mb_x, mb_y, mode)
        vp8_predict_block(pred, ud, 8, m)
        vp8_predict_block(pred, vd, 8, m)
        vp8_sse(src, ud, pred, ud, 8) + vp8_sse(src, vd, pred, vd, 8)
      })
      let mut best_uv = 0
      let mut best_uv_cost = 0x7fffffffffffffffL
      for ri in 0..= (if b >= 1 && b <= 16 { first_y } else { 0 }) {
          coded = true
        }
      }
      let skip = !coded
      if skip {
        // Decoder: skipped macroblocks reset the contexts.
        for k in 0..<8 {
          top_nz[mb_x * 9 + k] = 0
          left_nz[k] = 0
        }
        if !use_i4 {
          top_nz[mb_x * 9 + 8] = 0
          left_nz[8] = 0
        }
      } else {
        if !use_i4 {
          let ctx = top_nz[mb_x * 9 + 8] + left_nz[8]
          let nz = vp8_put_coeffs(events, 1, ctx, levels, 0, 0, lasts[0])
          let f = if nz { 1 } else { 0 }
          top_nz[mb_x * 9 + 8] = f
          left_nz[8] = f
        }
        let ty = if use_i4 { 3 } else { 0 }
        for n in 0..<16 {
          let bx = n & 3
          let by = n >> 2
          let ctx = top_nz[mb_x * 9 + bx] + left_nz[by]
          let last = if lasts[n + 1] >= first_y { lasts[n + 1] } else { -1 }
          let nz = vp8_put_coeffs(
            events,
            ty,
            ctx,
            levels,
            (n + 1) * 16,
            first_y,
            last,
          )
          let f = if nz { 1 } else { 0 }
          top_nz[mb_x * 9 + bx] = f
          left_nz[by] = f
        }
        for k in 0..<8 {
          let ch = k >> 2 // 0 = U, 1 = V
          let kk = k & 3
          let bx = kk & 1
          let by = kk >> 1
          let ti = mb_x * 9 + 4 + ch * 2 + bx
          let li = 4 + ch * 2 + by
          let ctx = top_nz[ti] + left_nz[li]
          let nz = vp8_put_coeffs(
            events,
            2,
            ctx,
            levels,
            (17 + k) * 16,
            0,
            lasts[17 + k],
          )
          let f = if nz { 1 } else { 0 }
          top_nz[ti] = f
          left_nz[li] = f
        }
      }
      // Mode data is written once the skip probability is known.
      mb_info.push((use_i4, best16, imodes.copy(), best_uv, skip))
      // Stash the unfiltered bottom row for the next macroblock row.
      if mb_y < mb_h - 1 {
        for i in 0..<16 {
          top[tb + i] = yuv[yd + 15 * 32 + i]
        }
        for i in 0..<8 {
          top[tb + 16 + i] = yuv[ud + 7 * 32 + i]
          top[tb + 24 + i] = yuv[vd + 7 * 32 + i]
        }
      }
    }
  }
  // Frame header + per-macroblock modes (partition 0).
  let mut skipped = 0
  for m in mb_info {
    if m.4 {
      skipped += 1
    }
  }
  let total = mb_info.length()
  let skip_p = vp8_clip(255 - skipped * 255 / total, 255)
  let skip_p = if skip_p < 1 { 1 } else { skip_p }
  let use_skip = skipped > 0
  let bw = modes_bw
  ignore(bw.put_bit(false, 0x80)) // color space
  ignore(bw.put_bit(false, 0x80)) // clamping
  ignore(bw.put_bit(false, 0x80)) // no segmentation
  ignore(bw.put_bit(false, 0x80)) // normal loop filter
  let level = vp8_clip(q * 2 / 5 + (if q > 0 { 2 } else { 0 }), 63)
  bw.put_bits(level, 6)
  bw.put_bits(0, 3) // sharpness
  ignore(bw.put_bit(false, 0x80)) // no loop filter deltas
  bw.put_bits(0, 2) // one token partition
  bw.put_bits(q, 7)
  for _ in 0..<5 {
    bw.put_signed(0, 4)
  }
  ignore(bw.put_bit(false, 0x80)) // refresh entropy probabilities
  // Token probabilities: update those whose savings beat the update cost.
  let n0 = FixedArray::make(1056, 0)
  let n1 = FixedArray::make(1056, 0)
  for e in events {
    let code = e >> 1
    if code < 1056 {
      if (e & 1) == 1 {
        n1[code] += 1
      } else {
        n0[code] += 1
      }
    }
  }
  let proba = vp8_coeffs_proba0.copy()
  for i in 0..<1056 {
    let total = n0[i] + n1[i]
    let up = vp8_coeffs_update_proba[i]
    let mut updated = false
    if total > 0 {
      let np = vp8_clip(255 - n1[i] * 255 / total, 255)
      let np = if np < 1 { 1 } else { np }
      let old = proba[i]
      let old_cost = n0[i] * vp8_cost0[old] +
        n1[i] * vp8_cost1[old] +
        vp8_cost0[up]
      let new_cost = n0[i] * vp8_cost0[np] +
        n1[i] * vp8_cost1[np] +
        vp8_cost1[up] +
        8 * 256
      if np != old && new_cost < old_cost {
        ignore(bw.put_bit(true, up))
        bw.put_bits(np, 8)
        proba[i] = np
        updated = true
      }
    }
    if !updated {
      ignore(bw.put_bit(false, up))
    }
  }
  ignore(bw.put_bit(use_skip, 0x80))
  if use_skip {
    bw.put_bits(skip_p, 8)
  }
  // Modes, replaying the decoder's 4x4 mode contexts.
  let it = FixedArray::make(4 * mb_w, 0)
  let il = FixedArray::make(4, 0)
  for i, m in mb_info {
    let mb_x = i % mb_w
    if mb_x == 0 {
      il.fill(0)
    }
    let (use_i4, m16, m4, muv, skip) = m
    if use_skip {
      ignore(bw.put_bit(skip, skip_p))
    }
    ignore(bw.put_bit(!use_i4, 145))
    if !use_i4 {
      match m16 {
        0 => {
          ignore(bw.put_bit(false, 156))
          ignore(bw.put_bit(false, 163))
        }
        2 => {
          ignore(bw.put_bit(false, 156))
          ignore(bw.put_bit(true, 163))
        }
        3 => {
          ignore(bw.put_bit(true, 156))
          ignore(bw.put_bit(false, 128))
        }
        _ => {
          ignore(bw.put_bit(true, 156))
          ignore(bw.put_bit(true, 128))
        }
      }
      for k in 0..<4 {
        it[mb_x * 4 + k] = m16
        il[k] = m16
      }
    } else {
      for y in 0..<4 {
        let mut left = il[y]
        for x in 0..<4 {
          let mode = m4[y * 4 + x]
          let prob = (it[mb_x * 4 + x] * 10 + left) * 9
          for step in vp8_bmode_paths[mode] {
            ignore(bw.put_bit(step.1 == 1, vp8_bmodes_proba[prob + step.0]))
          }
          it[mb_x * 4 + x] = mode
          left = mode
        }
        il[y] = left
      }
    }
    match muv {
      0 => ignore(bw.put_bit(false, 142))
      2 => {
        ignore(bw.put_bit(true, 142))
        ignore(bw.put_bit(false, 114))
      }
      1 => {
        ignore(bw.put_bit(true, 142))
        ignore(bw.put_bit(true, 114))
        ignore(bw.put_bit(true, 183))
      }
      _ => {
        ignore(bw.put_bit(true, 142))
        ignore(bw.put_bit(true, 114))
        ignore(bw.put_bit(false, 183))
      }
    }
  }
  let part0 = bw.finish()
  let tokens_bw = VP8BoolWriter::new()
  for e in events {
    let code = e >> 1
    let prob = if code < 1056 { proba[code] } else { code - 1056 }
    ignore(tokens_bw.put_bit((e & 1) == 1, prob))
  }
  let part1 = tokens_bw.finish()
  // Frame tag, start code, dimensions.
  let out = Buffer()
  let tag = (part0.length() << 5) | 0x10 // key frame, profile 0, shown
  out.write_byte(tag.to_byte())
  out.write_byte((tag >> 8).to_byte())
  out.write_byte((tag >> 16).to_byte())
  out.write_byte(b'\x9d')
  out.write_byte(b'\x01')
  out.write_byte(b'\x2a')
  out.write_byte(w.to_byte())
  out.write_byte((w >> 8).to_byte())
  out.write_byte(h.to_byte())
  out.write_byte((h >> 8).to_byte())
  out.write_bytes(part0)
  out.write_bytes(part1)
  out.to_bytes()
}