///|
let png_signature : FixedArray[Byte] = [
  b'\x89', b'\x50', b'\x4E', b'\x47', b'\x0D', b'\x0A', b'\x1A', b'\x0A',
]

///|
fn read_u32be(data : Bytes, offset : Int32) -> UInt32 {
  let b0 = data[offset].to_int() & 0xFF
  let b1 = data[offset + 1].to_int() & 0xFF
  let b2 = data[offset + 2].to_int() & 0xFF
  let b3 = data[offset + 3].to_int() & 0xFF
  (b0 << 24).lor(b1 << 16).lor(b2 << 8).lor(b3).reinterpret_as_uint()
}

///|
fn read_i32be(data : Bytes, offset : Int32) -> Int32 {
  let b0 = data[offset].to_int() & 0xFF
  let b1 = data[offset + 1].to_int() & 0xFF
  let b2 = data[offset + 2].to_int() & 0xFF
  let b3 = data[offset + 3].to_int() & 0xFF
  (b0 << 24) | (b1 << 16) | (b2 << 8) | b3
}

///|
fn chunk_type_str(data : Bytes, offset : Int32) -> String {
  String::from_array([
    data[offset].to_int().unsafe_to_char(),
    data[offset + 1].to_int().unsafe_to_char(),
    data[offset + 2].to_int().unsafe_to_char(),
    data[offset + 3].to_int().unsafe_to_char(),
  ])
}

///|
fn parse_ihdr(data : Bytes) -> IhdrData raise DecodeError {
  if data.length() < 13 {
    raise CorruptData("IHDR too short")
  }
  let width = read_i32be(data, 0)
  let height = read_i32be(data, 4)
  let bit_depth = data[8].to_int()
  let ct = color_type_from_png(data[9].to_int())
  let compression = data[10].to_int()
  let filter = data[11].to_int()
  let interlace = data[12].to_int()
  check_decode_size(width, height)
  validate_png_bit_depth(ct, bit_depth)
  if interlace != 0 && interlace != 1 {
    raise CorruptData("invalid interlace method: " + interlace.to_string())
  }
  { width, height, bit_depth, color_type: ct, compression, filter, interlace, }
}

///|
priv struct PngChunk {
  chunk_type : String
  data : Bytes
}

///|
fn parse_chunks(raw : Bytes) -> Array[PngChunk] raise DecodeError {
  if raw.length() < 8 {
    raise InvalidSignature("not a PNG file")
  }
  // Verify signature
  for i in 0..<8 {
    if raw[i] != png_signature[i] {
      raise InvalidSignature("not a PNG file")
    }
  }
  let chunks : Array[PngChunk] = []
  let mut pos = 8
  while pos + 12 <= raw.length() {
    let length = read_u32be(raw, pos).reinterpret_as_int()
    let ct = chunk_type_str(raw, pos + 4)
    // Lengths >= 2^31 read as negative; compare without overflowing.
    if length < 0 || length > raw.length() - pos - 12 {
      raise CorruptData("chunk extends beyond file")
    }
    // CRC covers chunk type + data
    let crc_data_len = 4 + length
    let crc_buf = FixedArray::make(crc_data_len, b'\x00')
    crc_buf.blit_from_bytes(0, raw, pos + 4, crc_data_len)
    let computed_crc = @zlib.crc32_fixed(crc_buf)
    let stored_crc = read_u32be(raw, pos + 8 + length)
    if computed_crc != stored_crc {
      raise InvalidChunkCrc(ct)
    }
    // Extract chunk data
    let chunk_data = if length > 0 {
      let buf = FixedArray::make(length, b'\x00')
      buf.blit_from_bytes(0, raw, pos + 8, length)
      Bytes::from_array(buf)
    } else {
      Bytes::new(0)
    }
    chunks.push({ chunk_type: ct, data: chunk_data, })
    pos = pos + 12 + length
    if ct == "IEND" {
      break
    }
  }
  chunks
}

///|
fn parse_png_ihdr(chunks : Array[PngChunk]) -> IhdrData raise DecodeError {
  if chunks.is_empty() {
    raise MissingChunk("IHDR")
  }
  match chunks[0] {
    { chunk_type: "IHDR", data, } => parse_ihdr(data)
    _ => raise MissingChunk("IHDR must be first chunk")
  }
}

///|
fn collect_png_image_data(
  chunks : Array[PngChunk],
) -> (Array[Bytes], Bytes?, Bytes?) raise DecodeError {
  let idat_parts : Array[Bytes] = []
  let mut palette : Bytes? = None
  let mut trns : Bytes? = None
  for chunk in chunks {
    match chunk.chunk_type {
      "IDAT" => idat_parts.push(chunk.data)
      "PLTE" => palette = Some(chunk.data)
      "tRNS" => trns = Some(chunk.data)
      _ => ()
    }
  }
  if idat_parts.is_empty() {
    raise MissingChunk("IDAT")
  }
  (idat_parts, palette, trns)
}

///|
/// Exact size of the decompressed image data for `ihdr` (filter bytes
/// included), for normal and Adam7-interlaced images.
fn png_expected_data_len(ihdr : IhdrData) -> Int32 {
  let w = ihdr.width
  let h = ihdr.height
  let len = fn(pw : Int32, ph : Int32) -> Int64 {
    if pw <= 0 || ph <= 0 {
      0L
    } else {
      ph.to_int64() *
      (1 + png_row_bytes(pw, ihdr.color_type, ihdr.bit_depth)).to_int64()
    }
  }
  let total = if ihdr.interlace == 1 {
    let mut t = 0L
    for p in adam7_passes {
      let (x0, y0, dx, dy) = p
      t += len((w - x0 + dx - 1) / dx, (h - y0 + dy - 1) / dy)
    }
    t
  } else {
    len(w, h)
  }
  if total > 0x7FFFFFFFL {
    0x7FFFFFFF
  } else {
    total.to_int()
  }
}

///|
fn decode_png_scanlines(
  ihdr : IhdrData,
  idat_parts : Array[Bytes],
  palette : Bytes?,
  trns : Bytes?,
  on_row : (Int32, Bytes) -> Unit,
) -> Unit raise DecodeError {
  // Concatenate IDAT data
  let total_idat_len = idat_parts.fold(init=0, fn(acc, b) { acc + b.length() })
  let idat_buf = FixedArray::make(total_idat_len, b'\x00')
  let mut offset = 0
  for part in idat_parts {
    idat_buf.blit_from_bytes(offset, part, 0, part.length())
    offset += part.length()
  }
  let compressed = Bytes::from_array(idat_buf)
  // Decompress, never beyond the size the header implies (guards against
  // decompression bombs; the exact size is checked below).
  let decompressed = @zlib.zlib_decompress(
    compressed,
    max_size=png_expected_data_len(ihdr),
  ) catch {
    _ => raise CorruptData("zlib decompression failed or exceeds image size")
  }
  if ihdr.interlace == 1 {
    decode_png_adam7(ihdr, decompressed, palette, trns, on_row)
    return
  }
  // Reconstruct image
  let stride = png_row_bytes(ihdr.width, ihdr.color_type, ihdr.bit_depth)
  let expected_len = ihdr.height * (1 + stride)
  if decompressed.length() != expected_len {
    raise CorruptData(
      "decompressed size mismatch: expected " +
      expected_len.to_string() +
      " got " +
      decompressed.length().to_string(),
    )
  }
  ignore(
    decode_png_pass(
      ihdr,
      decompressed,
      0,
      ihdr.width,
      ihdr.height,
      palette,
      trns,
      on_row,
    ),
  )
}

///|
/// Defilter and convert `rows` scanlines of `width` pixels starting at byte
/// `offset` of the decompressed stream. Returns the offset after the pass.
fn decode_png_pass(
  ihdr : IhdrData,
  decompressed : Bytes,
  offset : Int32,
  width : Int32,
  rows : Int32,
  palette : Bytes?,
  trns : Bytes?,
  on_row : (Int32, Bytes) -> Unit,
) -> Int32 raise DecodeError {
  let bpp = bytes_per_pixel(ihdr.color_type, ihdr.bit_depth)
  let stride = png_row_bytes(width, ihdr.color_type, ihdr.bit_depth)
  let converter = PngRowConverter::new(
    width,
    ihdr.color_type,
    ihdr.bit_depth,
    palette,
    trns,
  )
  let mut prev_row = Bytes::new(stride)
  for y in 0.. Unit,
) -> Unit raise DecodeError {
  let width = ihdr.width
  let height = ihdr.height
  let pass_size = fn(
    x0 : Int32,
    y0 : Int32,
    dx : Int32,
    dy : Int32,
  ) -> (Int32, Int32) {
    let pw = if width > x0 { (width - x0 + dx - 1) / dx } else { 0 }
    let ph = if height > y0 { (height - y0 + dy - 1) / dy } else { 0 }
    if pw == 0 || ph == 0 {
      (0, 0)
    } else {
      (pw, ph)
    }
  }
  let mut expected_len = 0
  for p in adam7_passes {
    let (pw, ph) = pass_size(p.0, p.1, p.2, p.3)
    expected_len += ph *
      (1 + png_row_bytes(pw, ihdr.color_type, ihdr.bit_depth))
  }
  if decompressed.length() != expected_len {
    raise CorruptData(
      "decompressed size mismatch: expected " +
      expected_len.to_string() +
      " got " +
      decompressed.length().to_string(),
    )
  }
  let rgba = FixedArray::make(width * height * 4, b'\x00')
  let mut offset = 0
  for p in adam7_passes {
    let (x0, y0, dx, dy) = p
    let (pw, ph) = pass_size(x0, y0, dx, dy)
    if pw == 0 {
      continue
    }
    offset = decode_png_pass(
      ihdr,
      decompressed,
      offset,
      pw,
      ph,
      palette,
      trns,
      fn(r, row) {
        let base = (y0 + r * dy) * width
        for i in 0.. Unit,
) -> IhdrData raise DecodeError {
  let chunks = parse_chunks(raw)
  let ihdr = parse_png_ihdr(chunks)
  let (idat_parts, palette, trns) = collect_png_image_data(chunks)
  decode_png_scanlines(ihdr, idat_parts, palette, trns, on_row)
  ihdr
}

///|
pub fn decode_png(raw : Bytes) -> ImageData raise DecodeError {
  let chunks = parse_chunks(raw)
  let ihdr = parse_png_ihdr(chunks)
  let (idat_parts, palette, trns) = collect_png_image_data(chunks)
  // Allocate the output only once the first row arrives, i.e. after the
  // decompressed size has been checked against the header, so that a
  // corrupt header cannot make us allocate a huge buffer up front.
  let mut rgba_buf : FixedArray[Byte] = []
  decode_png_scanlines(ihdr, idat_parts, palette, trns, fn(y, row) {
    if y == 0 {
      rgba_buf = FixedArray::make(ihdr.width * ihdr.height * 4, b'\x00')
    }
    let dst_offset = y * ihdr.width * 4
    rgba_buf.blit_from_bytes(dst_offset, row, 0, ihdr.width * 4)
  })
  { width: ihdr.width, height: ihdr.height, data: Bytes::from_array(rgba_buf), }
}

///|
test "read_u32be" {
  let data = b"\x00\x00\x00\x0D"
  assert_eq(read_u32be(data, 0), 13U)
}

///|
test "read_i32be" {
  let data = b"\x00\x00\x00\x01"
  assert_eq(read_i32be(data, 0), 1)
}