// WebP lossless (VP8L) decoder: prefix codes, LZ77 backward references,
// color cache, meta prefix codes, and the four inverse transforms
// (predictor, cross-color, subtract-green, color indexing).
// Pixels are kept as packed ARGB in Int (0xAARRGGBB).

///|
/// LSB-first bit reader over `data[start:end]`. Reading past the end
/// yields zero bits; consuming any of them raises CorruptData.
priv struct VP8LReader {
  data : Bytes
  end : Int32
  mut pos : Int32
  mut val : UInt32 // 32-bit window (UInt64 is slow on the js target)
  mut nbits : Int32
  mut pad : Int32 // zero bits appended past the end, at the top of `val`
}

///|
fn VP8LReader::new(data : Bytes, start : Int32, end : Int32) -> VP8LReader {
  { data, end, pos: start, val: 0, nbits: 0, pad: 0, }
}

///|
fn VP8LReader::fill(self : VP8LReader) -> Unit {
  // Keep 25..32 bits buffered; no VP8L read is longer than 18 bits.
  while self.nbits <= 24 {
    if self.pos < self.end {
      self.val = self.val | (self.data[self.pos].to_uint() << self.nbits)
      self.pos += 1
    } else {
      self.pad += 8
    }
    self.nbits += 8
  }
}

///|
fn VP8LReader::peek(self : VP8LReader, n : Int32) -> Int32 {
  if self.nbits < n {
    self.fill()
  }
  (self.val & ((1U << n) - 1)).reinterpret_as_int()
}

///|
fn VP8LReader::skip(self : VP8LReader, n : Int32) -> Unit raise DecodeError {
  self.val = self.val >> n
  self.nbits -= n
  if self.nbits < self.pad {
    raise CorruptData("truncated WebP lossless data")
  }
}

///|
fn VP8LReader::read(self : VP8LReader, n : Int32) -> Int32 raise DecodeError {
  if n == 0 {
    return 0
  }
  let v = self.peek(n)
  self.skip(n)
  v
}

///|
/// Canonical prefix code. `single >= 0` is a zero-bit code. Codes up to
/// `lut_bits` (<= 8) bits are looked up in `lut` (entry = symbol << 4 |
/// length); longer
/// ones are decoded bit by bit from `counts` / `sorted`.
priv struct VP8LHuff {
  single : Int32
  lut_bits : Int32
  lut : FixedArray[Int32]
  counts : FixedArray[Int32]
  sorted : FixedArray[Int32]
}

///|
fn vp8l_build_huff(lengths : FixedArray[Int32]) -> VP8LHuff raise DecodeError {
  let counts = FixedArray::make(16, 0)
  let mut used = 0
  let mut last = 0
  for s in 0.. 15 {
      raise CorruptData("invalid WebP code length")
    }
    if l > 0 {
      counts[l] += 1
      used += 1
      last = s
    }
  }
  if used == 0 {
    raise CorruptData("empty WebP prefix code")
  }
  if used == 1 {
    return { single: last, lut_bits: 0, lut: [], counts, sorted: [], }
  }
  // The code must be complete (Kraft sum exactly 1).
  let mut left = 1
  for l in 1..<16 {
    left = (left << 1) - counts[l]
    if left < 0 {
      raise CorruptData("over-subscribed WebP prefix code")
    }
  }
  if left != 0 {
    raise CorruptData("incomplete WebP prefix code")
  }
  let offsets = FixedArray::make(16, 0)
  for l in 1..<15 {
    offsets[l + 1] = offsets[l] + counts[l]
  }
  let sorted = FixedArray::make(used, 0)
  let next = offsets.copy()
  for s in 0.. 0 {
      sorted[next[l]] = s
      next[l] += 1
    }
  }
  let mut max_len = 0
  for l in 1..<16 {
    if counts[l] > 0 {
      max_len = l
    }
  }
  let lut_bits = if max_len < 8 { max_len } else { 8 }
  let lut_size = 1 << lut_bits
  let lut = FixedArray::make(lut_size, -1)
  let mut code = 0
  let mut idx = 0
  for l in 1..<16 {
    for _ in 0..> b) & 1) << (l - 1 - b))
        }
        let entry = (sorted[idx] << 4) | l
        let mut j = rev
        while j < lut_size {
          lut[j] = entry
          j += 1 << l
        }
      }
      code += 1
      idx += 1
    }
    code = code << 1
  }
  { single: -1, lut_bits, lut, counts, sorted, }
}

///|
fn VP8LHuff::decode(
  self : VP8LHuff,
  br : VP8LReader,
) -> Int32 raise DecodeError {
  if self.single >= 0 {
    return self.single
  }
  let e = self.lut[br.peek(self.lut_bits)]
  if e >= 0 {
    br.skip(e & 15)
    return e >> 4
  }
  let mut code = 0
  let mut first = 0
  let mut index = 0
  for l in 1..<16 {
    code = code | br.read(1)
    let count = self.counts[l]
    if code - first < count {
      return self.sorted[index + code - first]
    }
    index += count
    first = (first + count) << 1
    code = code << 1
  }
  raise CorruptData("invalid WebP prefix code")
}

///|
let vp8l_code_length_order : FixedArray[Int32] = [
  17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
]

///|
fn vp8l_read_huff(
  br : VP8LReader,
  alphabet : Int32,
) -> VP8LHuff raise DecodeError {
  let lengths = FixedArray::make(alphabet, 0)
  if br.read(1) == 1 {
    // Simple code: one or two symbols.
    let num = br.read(1) + 1
    let first_bits = if br.read(1) == 0 { 1 } else { 8 }
    let s0 = br.read(first_bits)
    if s0 >= alphabet {
      raise CorruptData("WebP prefix symbol out of range")
    }
    lengths[s0] = 1
    if num == 2 {
      let s1 = br.read(8)
      if s1 >= alphabet {
        raise CorruptData("WebP prefix symbol out of range")
      }
      lengths[s1] = 1
    }
  } else {
    let cl_lengths = FixedArray::make(19, 0)
    let num_codes = br.read(4) + 4
    for i in 0.. alphabet {
        raise CorruptData("WebP code length count too large")
      }
      m
    } else {
      alphabet
    }
    let mut remaining = max_symbol
    let mut symbol = 0
    let mut prev = 8
    while symbol < alphabet {
      if remaining == 0 {
        break
      }
      remaining -= 1
      let c = cl.decode(br)
      if c < 16 {
        lengths[symbol] = c
        symbol += 1
        if c != 0 {
          prev = c
        }
      } else {
        let (extra, offset, value) = match c {
          16 => (2, 3, prev)
          17 => (3, 3, 0)
          _ => (7, 11, 0)
        }
        let repeat = br.read(extra) + offset
        if symbol + repeat > alphabet {
          raise CorruptData("WebP code length repeat overflows")
        }
        for _ in 0.. VP8LGroup raise DecodeError {
  let green = vp8l_read_huff(br, 256 + 24 + cache_size)
  let red = vp8l_read_huff(br, 256)
  let blue = vp8l_read_huff(br, 256)
  let alpha = vp8l_read_huff(br, 256)
  let dist = vp8l_read_huff(br, 40)
  { green, red, blue, alpha, dist, }
}

///|
fn vp8l_subsample(size : Int32, bits : Int32) -> Int32 {
  (size + (1 << bits) - 1) >> bits
}

///|
fn vp8l_prefix_value(
  prefix : Int32,
  br : VP8LReader,
) -> Int32 raise DecodeError {
  if prefix < 4 {
    return prefix + 1
  }
  let extra = (prefix - 2) >> 1
  let offset = (2 + (prefix & 1)) << extra
  offset + br.read(extra) + 1
}

///|
let vp8l_code_to_plane : FixedArray[Int32] = [
  0x18, 0x07, 0x17, 0x19, 0x28, 0x06, 0x27, 0x29, 0x16, 0x1a, 0x26, 0x2a, 0x38, 0x05,
  0x37, 0x39, 0x15, 0x1b, 0x36, 0x3a, 0x25, 0x2b, 0x48, 0x04, 0x47, 0x49, 0x14, 0x1c,
  0x35, 0x3b, 0x46, 0x4a, 0x24, 0x2c, 0x58, 0x45, 0x4b, 0x34, 0x3c, 0x03, 0x57, 0x59,
  0x13, 0x1d, 0x56, 0x5a, 0x23, 0x2d, 0x44, 0x4c, 0x55, 0x5b, 0x33, 0x3d, 0x68, 0x02,
  0x67, 0x69, 0x12, 0x1e, 0x66, 0x6a, 0x22, 0x2e, 0x54, 0x5c, 0x43, 0x4d, 0x65, 0x6b,
  0x32, 0x3e, 0x78, 0x01, 0x77, 0x79, 0x53, 0x5d, 0x11, 0x1f, 0x64, 0x6c, 0x42, 0x4e,
  0x76, 0x7a, 0x21, 0x2f, 0x75, 0x7b, 0x31, 0x3f, 0x63, 0x6d, 0x52, 0x5e, 0x00, 0x74,
  0x7c, 0x41, 0x4f, 0x10, 0x20, 0x62, 0x6e, 0x30, 0x73, 0x7d, 0x51, 0x5f, 0x40, 0x72,
  0x7e, 0x61, 0x6f, 0x50, 0x71, 0x7f, 0x60, 0x70,
]

///|
fn vp8l_plane_distance(xsize : Int32, code : Int32) -> Int32 {
  if code > 120 {
    code - 120
  } else {
    let d = vp8l_code_to_plane[code - 1]
    let dist = (d >> 4) * xsize + (8 - (d & 0xf))
    if dist >= 1 {
      dist
    } else {
      1
    }
  }
}

///|
fn vp8l_cache_key(argb : Int32, bits : Int32) -> Int32 {
  ((argb.reinterpret_as_uint() * 0x1e35a7bdU) >> (32 - bits)).reinterpret_as_int()
}

///|
/// Decode one entropy-coded image of `xsize` x `ysize` pixels. Only the
/// main image (`level0`) may use meta prefix codes.
fn vp8l_decode_entropy_image(
  br : VP8LReader,
  xsize : Int32,
  ysize : Int32,
  level0 : Bool,
) -> FixedArray[Int32] raise DecodeError {
  let cache_bits = if br.read(1) == 1 {
    let b = br.read(4)
    if b < 1 || b > 11 {
      raise CorruptData("invalid WebP color cache size")
    }
    b
  } else {
    0
  }
  let cache_size = if cache_bits > 0 { 1 << cache_bits } else { 0 }
  let mut meta_bits = 0
  let mut meta_w = 0
  let mut meta : FixedArray[Int32] = []
  let mut num_groups = 1
  if level0 && br.read(1) == 1 {
    meta_bits = br.read(3) + 2
    meta_w = vp8l_subsample(xsize, meta_bits)
    let mh = vp8l_subsample(ysize, meta_bits)
    meta = vp8l_decode_entropy_image(br, meta_w, mh, false)
    for i in 0..> 8) & 0xffff
      meta[i] = g
      if g >= num_groups {
        num_groups = g + 1
      }
    }
  }
  let groups : Array[VP8LGroup] = []
  for _ in 0.. 0
  while pos < total {
    let g = if has_meta {
      groups[meta[(y >> meta_bits) * meta_w + (x >> meta_bits)]]
    } else {
      groups[0]
    }
    let s = g.green.decode(br)
    if s < 256 {
      let r = g.red.decode(br)
      let b = g.blue.decode(br)
      let a = g.alpha.decode(br)
      data[pos] = (a << 24) | (r << 16) | (s << 8) | b
      pos += 1
      x += 1
      if x == xsize {
        x = 0
        y += 1
      }
    } else if s < 280 {
      let length = vp8l_prefix_value(s - 256, br)
      let dsym = g.dist.decode(br)
      let dist = vp8l_plane_distance(xsize, vp8l_prefix_value(dsym, br))
      if dist > pos || total - pos < length {
        raise CorruptData("invalid WebP backward reference")
      }
      for i in 0..= xsize {
        x -= xsize
        y += 1
      }
    } else {
      let idx = s - 280
      if idx >= cache_size {
        raise CorruptData("invalid WebP color cache index")
      }
      data[pos] = cache[idx]
      pos += 1
      x += 1
      if x == xsize {
        x = 0
        y += 1
      }
    }
    if cache_bits > 0 {
      while last_cached < pos {
        let c = data[last_cached]
        cache[vp8l_cache_key(c, cache_bits)] = c
        last_cached += 1
      }
    }
  }
  data
}

///|
priv enum VP8LTransform {
  Predictor(Int32, Int32, FixedArray[Int32]) // xsize, bits, sub-image
  CrossColor(Int32, Int32, FixedArray[Int32])
  SubtractGreen
  ColorIndexing(Int32, Int32, FixedArray[Int32]) // xsize, bits, palette
}

///|
fn vp8l_add_pixels(a : Int32, b : Int32) -> Int32 {
  let ag = (a & 0xff00ff00) + (b & 0xff00ff00)
  let rb = (a & 0x00ff00ff) + (b & 0x00ff00ff)
  (ag & 0xff00ff00) | (rb & 0x00ff00ff)
}

///|
fn vp8l_average2(a : Int32, b : Int32) -> Int32 {
  (((a ^ b) & 0xfefefefe).reinterpret_as_uint() >> 1).reinterpret_as_int() +
  (a & b)
}

///|
fn vp8l_clip255(v : Int32) -> Int32 {
  if v < 0 {
    0
  } else if v > 255 {
    255
  } else {
    v
  }
}

///|
fn vp8l_select(t : Int32, l : Int32, tl : Int32) -> Int32 {
  let mut diff = 0
  for k in 0..<4 {
    let sh = k * 8
    let tc = (t >> sh) & 0xff
    let lc = (l >> sh) & 0xff
    let tlc = (tl >> sh) & 0xff
    let pb = lc - tlc
    let pa = tc - tlc
    diff += pb.abs() - pa.abs()
  }
  if diff <= 0 {
    t
  } else {
    l
  }
}

///|
fn vp8l_clamp_full(a : Int32, b : Int32, c : Int32) -> Int32 {
  let mut out = 0
  for k in 0..<4 {
    let sh = k * 8
    let v = ((a >> sh) & 0xff) + ((b >> sh) & 0xff) - ((c >> sh) & 0xff)
    out = out | (vp8l_clip255(v) << sh)
  }
  out
}

///|
fn vp8l_clamp_half(a : Int32, b : Int32, c : Int32) -> Int32 {
  let ave = vp8l_average2(a, b)
  let mut out = 0
  for k in 0..<4 {
    let sh = k * 8
    let x = (ave >> sh) & 0xff
    let y = (c >> sh) & 0xff
    out = out | (vp8l_clip255(x + (x - y) / 2) << sh)
  }
  out
}

///|
fn vp8l_predict(
  mode : Int32,
  px : FixedArray[Int32],
  pos : Int32,
  xsize : Int32,
) -> Int32 {
  let l = px[pos - 1]
  let t = px[pos - xsize]
  match mode {
    0 => 0xff000000
    1 => l
    2 => t
    3 => px[pos - xsize + 1]
    4 => px[pos - xsize - 1]
    5 => vp8l_average2(vp8l_average2(l, px[pos - xsize + 1]), t)
    6 => vp8l_average2(l, px[pos - xsize - 1])
    7 => vp8l_average2(l, t)
    8 => vp8l_average2(px[pos - xsize - 1], t)
    9 => vp8l_average2(t, px[pos - xsize + 1])
    10 =>
      vp8l_average2(
        vp8l_average2(l, px[pos - xsize - 1]),
        vp8l_average2(t, px[pos - xsize + 1]),
      )
    11 => vp8l_select(t, l, px[pos - xsize - 1])
    12 => vp8l_clamp_full(l, t, px[pos - xsize - 1])
    13 => vp8l_clamp_half(l, t, px[pos - xsize - 1])
    _ => 0xff000000
  }
}

///|
fn vp8l_inverse_predictor(
  px : FixedArray[Int32],
  xsize : Int32,
  ysize : Int32,
  bits : Int32,
  modes : FixedArray[Int32],
) -> Unit {
  if px.length() == 0 {
    return
  }
  px[0] = vp8l_add_pixels(px[0], 0xff000000)
  for x in 1..> bits) * tiles_w
    for x in 1..> bits)] >> 8) & 0xf
      let pos = row + x
      px[pos] = vp8l_add_pixels(px[pos], vp8l_predict(mode, px, pos, xsize))
    }
  }
}

///|
fn vp8l_color_delta(t : Int32, c : Int32) -> Int32 {
  let ts = if t >= 128 { t - 256 } else { t }
  let cs = if c >= 128 { c - 256 } else { c }
  (ts * cs) >> 5
}

///|
fn vp8l_inverse_cross_color(
  px : FixedArray[Int32],
  xsize : Int32,
  ysize : Int32,
  bits : Int32,
  mult : FixedArray[Int32],
) -> Unit {
  let tiles_w = vp8l_subsample(xsize, bits)
  for y in 0..> bits) * tiles_w
    for x in 0..> bits)]
      let g2r = m & 0xff
      let g2b = (m >> 8) & 0xff
      let r2b = (m >> 16) & 0xff
      let pos = y * xsize + x
      let argb = px[pos]
      let green = (argb >> 8) & 0xff
      let red = ((argb >> 16) & 0xff) + vp8l_color_delta(g2r, green)
      let red = red & 0xff
      let blue = (argb & 0xff) +
        vp8l_color_delta(g2b, green) +
        vp8l_color_delta(r2b, red)
      px[pos] = (argb & 0xff00ff00) | (red << 16) | (blue & 0xff)
    }
  }
}

///|
fn vp8l_inverse_subtract_green(px : FixedArray[Int32]) -> Unit {
  for i in 0..> 8) & 0xff
    let rb = (argb & 0x00ff00ff) + ((g << 16) | g)
    px[i] = (argb & 0xff00ff00) | (rb & 0x00ff00ff)
  }
}

///|
/// Expand packed palette indices of a `packed_w`-wide image into a
/// `xsize`-wide one.
fn vp8l_inverse_color_indexing(
  px : FixedArray[Int32],
  packed_w : Int32,
  xsize : Int32,
  ysize : Int32,
  bits : Int32,
  palette : FixedArray[Int32],
) -> FixedArray[Int32] {
  let out = FixedArray::make(xsize * ysize, 0)
  let bpp = 8 >> bits
  let per = (1 << bits) - 1
  let mask = (1 << bpp) - 1
  for y in 0..> bits)]
      let g = (packed >> 8) & 0xff
      let idx = (g >> ((x & per) * bpp)) & mask
      out[y * xsize + x] = palette[idx]
    }
  }
  out
}

///|
/// Decode a VP8L image stream (after the 5-byte header for full images;
/// ALPH chunks start here directly) into ARGB pixels.
fn vp8l_decode_stream(
  br : VP8LReader,
  width : Int32,
  height : Int32,
) -> FixedArray[Int32] raise DecodeError {
  let transforms : Array[VP8LTransform] = []
  let mut xsize = width
  let mut seen = 0
  while br.read(1) == 1 {
    let ty = br.read(2)
    if (seen & (1 << ty)) != 0 {
      raise CorruptData("repeated WebP transform")
    }
    seen = seen | (1 << ty)
    match ty {
      0 | 1 => {
        let bits = br.read(3) + 2
        let sub = vp8l_decode_entropy_image(
          br,
          vp8l_subsample(xsize, bits),
          vp8l_subsample(height, bits),
          false,
        )
        transforms.push(
          if ty == 0 {
            Predictor(xsize, bits, sub)
          } else {
            CrossColor(xsize, bits, sub)
          },
        )
      }
      2 => transforms.push(SubtractGreen)
      _ => {
        let num = br.read(8) + 1
        let bits = if num > 16 {
          0
        } else if num > 4 {
          1
        } else if num > 2 {
          2
        } else {
          3
        }
        let colors = vp8l_decode_entropy_image(br, num, 1, false)
        // Colors are delta-coded; entries past `num` are transparent black.
        let palette = FixedArray::make(1 << (8 >> bits), 0)
        palette[0] = colors[0]
        for i in 1..= 0; i = i - 1 {
    match transforms[i] {
      Predictor(w, bits, sub) =>
        vp8l_inverse_predictor(px, w, height, bits, sub)
      CrossColor(w, bits, sub) =>
        vp8l_inverse_cross_color(px, w, height, bits, sub)
      SubtractGreen => vp8l_inverse_subtract_green(px)
      ColorIndexing(w, bits, palette) => {
        px = vp8l_inverse_color_indexing(px, cur_w, w, height, bits, palette)
        cur_w = w
      }
    }
  }
  px
}

///|
/// Decode a complete VP8L bitstream (the payload of a `VP8L` chunk).
/// Returns (width, height, alpha_is_used, ARGB pixels).
fn vp8l_decode(
  data : Bytes,
  start : Int32,
  end : Int32,
) -> (Int32, Int32, Bool, FixedArray[Int32]) raise DecodeError {
  if end - start < 5 || data[start] != b'\x2f' {
    raise InvalidSignature("not a WebP lossless bitstream")
  }
  let br = VP8LReader::new(data, start + 1, end)
  let width = br.read(14) + 1
  let height = br.read(14) + 1
  let has_alpha = br.read(1) == 1
  if br.read(3) != 0 {
    raise UnsupportedFeature("unknown WebP lossless version")
  }
  check_decode_size(width, height)
  let px = vp8l_decode_stream(br, width, height)
  (width, height, has_alpha, px)
}