///|
priv suberror AvifError {
  Invalid
  Unsupported
  Diagnostic(DecodeError)
}

///|
pub struct AvifContainer {
  width : Int
  height : Int
  bit_depth : Int
  monochrome : Bool
  /// Chroma subsampling from the `av1C` box. `yuv420` is both flags set; a
  /// 4:2:2 stream sets x only and a 4:4:4 stream sets neither.
  subsampling_x : Bool
  subsampling_y : Bool
  yuv420 : Bool
  has_alpha : Bool
  // A grid inherits this configuration from its validated coded cells.
  av1c : Array[Byte]
  payload : Array[Byte]
  /// Layer selection for the primary coded item; absent properties select
  /// operating point zero and its highest presented spatial layer.
  operating_point : Int
  spatial_layer : Int?
  nclx_primaries : Int?
  nclx_transfer : Int?
  nclx_matrix : Int?
  nclx_full_range : Bool?
}

///|
priv struct Box {
  typ : Int
  start : Int
  payload : Int
  end : Int
  parent : Int
}

///|
priv struct Item {
  id : Int
  typ : Int
  mut method_id : Int
  mut base : Int
  offs : Array[Int]
  lens : Array[Int]
  props : Array[Int]
}

///|
priv struct Prop {
  kind : Int
  width : Int
  height : Int
  data : Array[Byte]
  p : Int
  t : Int
  m : Int
  full_range : Bool
}

///|
let t_meta = 0x6D657461

///|
let t_iprp = 0x69707270

///|
let t_ipco = 0x6970636F

///|
let t_pitm = 0x7069746D

///|
let t_iinf = 0x69696E66

///|
let t_infe = 0x696E6665

///|
let t_iloc = 0x696C6F63

///|
let t_idat = 0x69646174

///|
let t_ipma = 0x69706D61

///|
let t_ispe = 0x69737065

///|
let t_av1c = 0x61763143

///|
let t_colr = 0x636F6C72

///|
let t_nclx = 0x6E636C78

///|
let t_auxc = 0x61757843

///|
let t_a1op = 0x61316F70

///|
let t_lsel = 0x6C73656C

///|
let t_av01 = 0x61763031

///|
fn u8(d : Array[Byte], p : Int, e : Int) -> Int raise AvifError {
  if p < 0 || p >= e || p >= d.length() {
    raise AvifError::Diagnostic(
      decode_error(
        TruncatedInput,
        "container",
        "Container field extends beyond the available bytes",
        offset=Some(p),
      ),
    )
  }
  d[p].to_int()
}

///|
fn u16(d : Array[Byte], p : Int, e : Int) -> Int raise AvifError {
  u8(d, p, e) * 256 + u8(d, p + 1, e)
}

///|
fn u32(d : Array[Byte], p : Int, e : Int) -> Int raise AvifError {
  u8(d, p, e) * 16777216 +
  u8(d, p + 1, e) * 65536 +
  u8(d, p + 2, e) * 256 +
  u8(d, p + 3, e)
}

///|
fn u64(d : Array[Byte], p : Int, e : Int) -> Int raise AvifError {
  // Box sizes and array offsets must fit Int before any arithmetic.
  for i in 0..<4 {
    if u8(d, p + i, e) != 0 {
      raise AvifError::Unsupported
    }
  }
  if u8(d, p + 4, e) > 127 {
    raise AvifError::Unsupported
  }
  u32(d, p + 4, e)
}

///|
fn idx_box(bs : Array[Box], s : Int) -> Int {
  for i in 0.. Box? {
  for b in bs {
    if b.parent == parent && b.typ == typ {
      return Some(b)
    }
  }
  None
}

///|
fn idx_item(xs : Array[Item], id : Int) -> Int {
  for i in 0.. Array[Byte] raise AvifError {
  if a < 0 || b < a || b > d.length() {
    raise AvifError::Invalid
  }
  let x : Array[Byte] = []
  for i in a.. Unit raise AvifError {
  if depth > AVIF_MAX_BOX_DEPTH {
    raise AvifError::Diagnostic(
      decode_error(
        LimitExceeded,
        "container",
        "Container nesting exceeds 64 levels",
        offset=Some(from),
      ),
    )
  }
  let mut p = from
  while p < to {
    if to - p < 8 {
      raise AvifError::Diagnostic(
        decode_error(
          TruncatedInput,
          "container",
          "Incomplete box header",
          offset=Some(p),
        ),
      )
    }
    let s32 = u32(d, p, to)
    let typ = u32(d, p + 4, to)
    let mut h = 8
    let mut size = s32
    if s32 == 1 {
      h = 16
      size = u64(d, p + 8, to)
    } else if s32 == 0 {
      size = to - p
    }
    if size < h {
      raise AvifError::Diagnostic(
        decode_error(
          InvalidData,
          "container",
          "Box size is smaller than its header",
          offset=Some(p),
        ),
      )
    }
    if size > to - p {
      raise AvifError::Diagnostic(
        decode_error(
          TruncatedInput,
          "container",
          "Box payload extends beyond its parent",
          offset=Some(p),
        ),
      )
    }
    let end = p + size
    let payload = p + h
    let bi = out.length()
    out.push({ typ, start: p, payload, end, parent, })
    if typ == t_meta {
      if end - payload < 4 {
        raise AvifError::Invalid
      }
      walk(d, payload + 4, end, bi, out, depth=depth + 1)
    } else if typ == t_iprp || typ == t_ipco {
      walk(d, payload, end, bi, out, depth=depth + 1)
    } else if typ == t_iinf {
      let version = u8(d, payload, end)
      let child_start = if version == 0 { payload + 6 } else { payload + 8 }
      if child_start > end {
        raise AvifError::Invalid
      }
      walk(d, child_start, end, bi, out, depth=depth + 1)
    }
    p = end
  }
}

///|
/// `av1C` configuration. Returns (bit depth, monochrome, subsampling_x,
/// subsampling_y); byte 2 stores monochrome at bit 4 and the two subsampling
/// flags at bits 3 and 2 (AV1 ISOBMFF binding §2.3.3).
fn parse_av1c(
  _d : Array[Byte],
  p : Prop,
) -> (Int, Bool, Bool, Bool) raise AvifError {
  if p.data.length() < 3 {
    raise AvifError::Invalid
  }
  let b0 = p.data[0].to_int()
  if (b0 & 0x80) == 0 || (b0 & 0x7F) != 1 {
    raise AvifError::Unsupported
  }
  let f = p.data[2].to_int()
  let depth = if (f & 0x40) == 0 {
    8
  } else if (f & 0x20) != 0 {
    12
  } else {
    10
  }
  (depth, (f & 0x10) != 0, ((f >> 3) & 1) != 0, ((f >> 2) & 1) != 0)
}

///|
fn avif_container_parse_limited(
  data : Array[Byte],
  limits? : DecodeLimits? = None,
  diagnostic? : DecodeDiagnostic? = None,
) -> AvifContainer? {
  if !decode_input_allowed(data.length(), limits) {
    return None
  }
  try {
    let bs : Array[Box] = []
    walk(data, 0, data.length(), -1, bs)
    let meta = match find_box(bs, -1, t_meta) {
      Some(x) => x
      None => raise AvifError::Invalid
    }
    let mi = idx_box(bs, meta.start)
    let pitm = match find_box(bs, mi, t_pitm) {
      Some(x) => x
      None => raise AvifError::Invalid
    }
    let pv = u8(data, pitm.payload, pitm.end)
    let primary = if pv == 0 {
      u16(data, pitm.payload + 4, pitm.end)
    } else {
      u32(data, pitm.payload + 4, pitm.end)
    }
    let iinf = match find_box(bs, mi, t_iinf) {
      Some(x) => x
      None => raise AvifError::Invalid
    }
    let ii = idx_box(bs, iinf.start)
    let items : Array[Item] = []
    for b in bs {
      if b.parent == ii && b.typ == t_infe {
        let v = u8(data, b.payload, b.end)
        if v < 2 {
          raise AvifError::Unsupported
        }
        let id = if v >= 3 {
          u32(data, b.payload + 4, b.end)
        } else {
          u16(data, b.payload + 4, b.end)
        }
        items.push({
          id,
          typ: u32(data, b.payload + (if v >= 3 { 10 } else { 8 }), b.end),
          method_id: 0,
          base: 0,
          offs: [],
          lens: [],
          props: [],
        })
      }
    }
    let iloc = match find_box(bs, mi, t_iloc) {
      Some(x) => x
      None => raise AvifError::Invalid
    }
    parse_iloc(data, iloc, items)
    let iprp = find_box(bs, mi, t_iprp)
    parse_ipma(data, bs, iprp, items)
    let props = parse_props(data, bs, iprp)
    let pi = idx_item(items, primary)
    if pi < 0 || (items[pi].typ != t_av01 && items[pi].typ != 0x67726964) {
      raise AvifError::Invalid
    }
    let it = items[pi]
    let (operating_point, spatial_layer) = avif_layer_selection(props, it.props)
    let mut w = 0
    let mut h = 0
    let mut depth = 8
    let mut mono = false
    let mut sub_x = false
    let mut sub_y = false
    let mut av1 : Array[Byte]? = None
    let mut np : Int? = None
    let mut nt : Int? = None
    let mut nm : Int? = None
    let mut nr : Bool? = None
    for ai in it.props {
      if ai <= 0 || ai > props.length() {
        raise AvifError::Invalid
      }
      let q = props[ai - 1]
      if q.kind == t_ispe {
        w = q.width
        h = q.height
      }
      if q.kind == t_av1c {
        av1 = Some(q.data)
        let parsed = parse_av1c(data, q)
        depth = parsed.0
        mono = parsed.1
        sub_x = parsed.2
        sub_y = parsed.3
      }
      if q.kind == t_colr {
        np = Some(q.p)
        nt = Some(q.t)
        nm = Some(q.m)
        nr = Some(q.full_range)
      }
    }
    if it.typ == 0x67726964 {
      if av1 is Some(_) {
        raise AvifError::Invalid
      }
      let grid = match avif_grid_descriptor_for_item(data, Some(it.id)) {
        Some(value) => value
        None => raise AvifError::Invalid
      }
      if !avif_grid_properties_match(data, grid, limits~) {
        raise AvifError::Invalid
      }
      let first = idx_item(items, grid.tiles[0].item_id)
      if first < 0 {
        raise AvifError::Invalid
      }
      for ai in items[first].props {
        if ai <= 0 || ai > props.length() {
          raise AvifError::Invalid
        }
        let property = props[ai - 1]
        if property.kind == t_av1c {
          av1 = Some(property.data)
          let parsed = parse_av1c(data, property)
          depth = parsed.0
          mono = parsed.1
          sub_x = parsed.2
          sub_y = parsed.3
        }
      }
    }
    if w <= 0 || h <= 0 || av1 is None || it.offs.length() == 0 {
      raise AvifError::Invalid
    }
    let idat = find_box(bs, mi, t_idat)
    let payload : Array[Byte] = []
    for i in 0.. (x.payload, x.end)
          None => raise AvifError::Invalid
        }
      } else {
        (0, data.length())
      }
      let len = it.lens[i]
      if !decode_payload_allowed(payload.length(), len, limits) {
        raise AvifError::Diagnostic(
          decode_error(
            LimitExceeded,
            "container",
            "Assembled item payload exceeds the byte budget",
          ),
        )
      }
      if len < 0 ||
        it.base < 0 ||
        it.offs[i] < 0 ||
        base > bound - len ||
        it.base > bound - len - base ||
        it.offs[i] > bound - len - base - it.base {
        raise AvifError::Invalid
      }
      let off = base + it.base + it.offs[i]
      for j in off..<(off + len) {
        payload.push(data[j])
      }
    }
    Some({
      width: w,
      height: h,
      bit_depth: depth,
      monochrome: mono,
      subsampling_x: sub_x,
      subsampling_y: sub_y,
      yuv420: sub_x && sub_y,
      has_alpha: avif_alpha_descriptor_checked(data, limits~) is Some(_),
      av1c: av1.unwrap(),
      payload,
      operating_point,
      spatial_layer,
      nclx_primaries: np,
      nclx_transfer: nt,
      nclx_matrix: nm,
      nclx_full_range: nr,
    })
  } catch {
    AvifError::Diagnostic(error) => {
      decode_trace_error(diagnostic, error)
      None
    }
    AvifError::Unsupported => {
      decode_trace_error(
        diagnostic,
        decode_error(
          Unsupported,
          "container",
          "Unsupported container field or construction method",
        ),
      )
      None
    }
    _ => {
      decode_trace_error(
        diagnostic,
        decode_error(
          InvalidData,
          "container",
          "Invalid AVIF item, property or extent",
        ),
      )
      None
    }
  }
}

///|
/// Parse AVIF 2.3.2's descriptive operating-point and layer selectors.
/// lsel is a two-byte property, not a FullBox; 0xffff means no fixed layer.
fn avif_layer_selection(
  properties : Array[Prop],
  associations : Array[Int],
) -> (Int, Int?) raise AvifError {
  let mut operating_point = 0
  let mut spatial_layer : Int? = None
  let mut seen_op = false
  let mut seen_layer = false
  for index in associations {
    if index <= 0 || index > properties.length() {
      raise AvifError::Invalid
    }
    let property = properties[index - 1]
    if property.kind == t_a1op {
      if seen_op ||
        property.data.length() != 1 ||
        property.data[0].to_int() > 31 {
        raise AvifError::Invalid
      }
      seen_op = true
      operating_point = property.data[0].to_int()
    } else if property.kind == t_lsel {
      if seen_layer || property.data.length() != 2 {
        raise AvifError::Invalid
      }
      seen_layer = true
      let layer = property.data[0].to_int() * 256 + property.data[1].to_int()
      if layer != 65535 {
        if layer > 3 {
          raise AvifError::Invalid
        }
        spatial_layer = Some(layer)
      }
    }
  }
  (operating_point, spatial_layer)
}

///|
/// Resolve selectors on a coded color, alpha, or grid-cell item. Metadata
/// readers share this with the primary container parser so no entry point
/// can silently decode an associated essential selector as the default.
fn avif_item_layer_selection(data : Array[Byte], item_id : Int) -> (Int, Int?)? {
  match avif_item_decode_config(data, item_id) {
    Some((_, _, operating_point, spatial_layer)) =>
      Some((operating_point, spatial_layer))
    None => None
  }
}

///|
fn avif_item_decode_config(
  data : Array[Byte],
  item_id : Int,
) -> (Int, Int, Int, Int?)? {
  try {
    let boxes : Array[Box] = []
    walk(data, 0, data.length(), -1, boxes)
    let meta = match find_box(boxes, -1, t_meta) {
      Some(value) => value
      None => return None
    }
    let iprp = find_box(boxes, idx_box(boxes, meta.start), t_iprp)
    let items : Array[Item] = [
      {
        id: item_id,
        typ: t_av01,
        method_id: 0,
        base: 0,
        offs: [],
        lens: [],
        props: [],
      },
    ]
    parse_ipma(data, boxes, iprp, items)
    let props = parse_props(data, boxes, iprp)
    let (operating_point, spatial_layer) = avif_layer_selection(
      props,
      items[0].props,
    )
    let mut width = 0
    let mut height = 0
    for index in items[0].props {
      let prop = props[index - 1]
      if prop.kind == t_ispe {
        if width != 0 || prop.width <= 0 || prop.height <= 0 {
          return None
        }
        width = prop.width
        height = prop.height
      }
    }
    if width == 0 {
      return None
    }
    Some((width, height, operating_point, spatial_layer))
  } catch {
    _ => None
  }
}

///|
fn parse_iloc(
  d : Array[Byte],
  b : Box,
  xs : Array[Item],
) -> Unit raise AvifError {
  let p = b.payload
  let v = u8(d, p, b.end)
  if v > 2 {
    raise AvifError::Unsupported
  }
  let a = u8(d, p + 4, b.end)
  let os = a >> 4
  let ls = a & 15
  let z = u8(d, p + 5, b.end)
  let bs = z >> 4
  let isz = if v >= 1 { z & 15 } else { 0 }
  if (os != 0 && os != 4 && os != 8) ||
    (ls != 0 && ls != 4 && ls != 8) ||
    (bs != 0 && bs != 4 && bs != 8) {
    raise AvifError::Unsupported
  }
  let mut q = p + 6
  let n = if v < 2 { u16(d, q, b.end) } else { u32(d, q, b.end) }
  q = q + (if v < 2 { 2 } else { 4 })
  for _ in 0..= 1 { u16(d, q, b.end) & 15 } else { 0 }
    if method_code != 0 && method_code != 1 {
      raise AvifError::Unsupported
    }
    if v >= 1 {
      q = q + 2
    }
    let data_reference = u16(d, q, b.end)
    if data_reference != 0 {
      raise AvifError::Unsupported
    }
    q = q + 2
    let base = if bs == 0 {
      0
    } else if bs == 4 {
      u32(d, q, b.end)
    } else {
      u64(d, q, b.end)
    }
    q = q + bs
    let ec = u16(d, q, b.end)
    q = q + 2
    let xi = idx_item(xs, id)
    for _ in 0..= 1 && isz != 0 {
        q = q + isz
      }
      let off = if os == 0 {
        0
      } else if os == 4 {
        u32(d, q, b.end)
      } else {
        u64(d, q, b.end)
      }
      q = q + os
      let len = if ls == 0 {
        0
      } else if ls == 4 {
        u32(d, q, b.end)
      } else {
        u64(d, q, b.end)
      }
      q = q + ls
      if xi >= 0 {
        xs[xi].method_id = method_code
        xs[xi].base = base
        xs[xi].offs.push(off)
        xs[xi].lens.push(len)
      }
    }
  }
}

///|
fn parse_ipma(
  d : Array[Byte],
  bs : Array[Box],
  iprp : Box?,
  xs : Array[Item],
  essential? : Array[(Int, Int)]? = None,
) -> Unit raise AvifError {
  let rp = match iprp {
    Some(x) => x
    None => return
  }
  let ri = idx_box(bs, rp.start)
  let b = match find_box(bs, ri, t_ipma) {
    Some(x) => x
    None => return
  }
  let p = b.payload
  let version = u8(d, p, b.end)
  if version > 1 {
    raise AvifError::Unsupported
  }
  let flags = u32(d, p, b.end) & 0xFFFFFF
  let mut q = p + 4
  let n = u32(d, q, b.end)
  q = q + 4
  for _ in 0..= 1 { u32(d, q, b.end) } else { u16(d, q, b.end) }
    q = q + (if version >= 1 { 4 } else { 2 })
    let c = u8(d, q, b.end)
    q = q + 1
    let xi = idx_item(xs, id)
    for _ in 0..= 0 {
        let property = if (flags & 1) != 0 { a & 0x7FFF } else { a & 0x7F }
        if property != 0 {
          xs[xi].props.push(property)
          let mask = if (flags & 1) != 0 { 0x8000 } else { 0x80 }
          if (a & mask) != 0 && essential is Some(entries) {
            entries.push((id, property))
          }
        }
      }
    }
  }
}

///|
fn parse_props(
  d : Array[Byte],
  bs : Array[Box],
  iprp : Box?,
) -> Array[Prop] raise AvifError {
  let out : Array[Prop] = []
  let rp = match iprp {
    Some(x) => x
    None => return out
  }
  let ri = idx_box(bs, rp.start)
  let co = match find_box(bs, ri, t_ipco) {
    Some(x) => x
    None => return out
  }
  let ci = idx_box(bs, co.start)
  for b in bs {
    if b.parent != ci {
      continue
    }
    if b.typ == t_ispe {
      out.push({
        kind: b.typ,
        width: u32(d, b.payload + 4, b.end),
        height: u32(d, b.payload + 8, b.end),
        data: [],
        p: 0,
        t: 0,
        m: 0,
        full_range: false,
      })
    } else if b.typ == t_av1c || b.typ == t_a1op || b.typ == t_lsel {
      out.push({
        kind: b.typ,
        width: 0,
        height: 0,
        data: slice(d, b.payload, b.end),
        p: 0,
        t: 0,
        m: 0,
        full_range: false,
      })
    } else if b.typ == t_colr && u32(d, b.payload, b.end) == t_nclx {
      out.push({
        kind: b.typ,
        width: 0,
        height: 0,
        data: [],
        p: u16(d, b.payload + 4, b.end),
        t: u16(d, b.payload + 6, b.end),
        m: u16(d, b.payload + 8, b.end),
        full_range: (u8(d, b.payload + 10, b.end) & 0x80) != 0,
      })
    } else if b.typ == t_auxc {
      out.push({
        kind: b.typ,
        width: 0,
        height: 0,
        data: [],
        p: 0,
        t: 0,
        m: 0,
        full_range: false,
      })
    } else {
      // ICC ('prof'/'rICC') is not an nclx declaration. Keep its property
      // index without inventing zero-valued CICP fields or a range flag.
      out.push({
        kind: if b.typ == t_colr {
          0
        } else {
          b.typ
        },
        width: 0,
        height: 0,
        data: [],
        p: 0,
        t: 0,
        m: 0,
        full_range: false,
      })
    }
  }
  out
}