///|
pub struct LocalFileHeader {
  signature : UInt
  version_needed : UInt16
  flags : UInt16
  compression_method : CompressionMethod
  last_mod_time : UInt16
  last_mod_date : UInt16
  crc32 : UInt
  compressed_size : UInt
  uncompressed_size : UInt
  filename_length : UInt16
  extra_field_length : UInt16
  filename : String
  extra_field : Bytes
}

///|
pub struct EndOfCentralDirectoryRecord {
  signature : UInt
  disk_number : UInt16
  cd_start_disk : UInt16
  cd_entries_on_disk : UInt16
  cd_entries_total : UInt16
  cd_size : UInt
  cd_offset : UInt
  comment_length : UInt16
  comment : String
}

///|
pub struct BitReader {
  data : Bytes
  mut pos : Int
  mut buf : UInt64
  mut bits : Int
}

///|
fn BitReader::new(data : Bytes) -> BitReader {
  let br : BitReader = BitReader::{ data, pos: 0, buf: 0, bits: 0 }
  br.refill()
  br
}

///|
fn BitReader::refill(self : BitReader) -> Unit {
  while self.bits <= 56 && self.pos < self.data.length() {
    let byte : UInt64 = self.data[self.pos].to_uint64()
    self.buf = self.buf | (byte << self.bits)
    self.bits = self.bits + 8
    self.pos = self.pos + 1
  }
}

///|
fn BitReader::peek(self : BitReader, n : Int) -> UInt {
  if self.bits < n {
    self.refill()
  }
  let mask : UInt64 = ((1 << n) - 1).to_uint64()
  (self.buf & mask).to_uint()
}

///|
fn BitReader::advance(self : BitReader, n : Int) -> Unit {
  self.buf = self.buf >> n
  self.bits = self.bits - n
}

///|
fn BitReader::read_bits(self : BitReader, n : Int) -> UInt {
  if n <= 0 {
    return 0
  }
  if self.bits < n {
    self.refill()
  }
  let mask : UInt64 = ((1 << n) - 1).to_uint64()
  let result : UInt = (self.buf & mask).to_uint()
  self.buf = self.buf >> n
  self.bits = self.bits - n
  result
}

///|
fn BitReader::align_to_byte(self : BitReader) -> Unit {
  let discard : Int = self.bits % 8
  self.buf = self.buf >> discard
  self.bits = self.bits - discard
}

///|
fn BitReader::read_bytes(self : BitReader, n : Int) -> Bytes {
  self.align_to_byte()
  let result : Array[Byte] = Array::make(n, 0b0)
  let mut i : Int = 0
  while i < n && self.bits >= 8 {
    result[i] = (self.buf & 0xFF).to_byte()
    self.buf = self.buf >> 8
    self.bits = self.bits - 8
    i = i + 1
  }
  while i < n && self.pos < self.data.length() {
    result[i] = self.data[self.pos]
    self.pos = self.pos + 1
    i = i + 1
  }
  Bytes::from_iter(result.iter())
}

///|
pub struct HuffmanTree {
  table : Array[Int]
  table_lens : Array[Int]
  table_bits : Int
  first_code : Array[Int]
  first_symbol : Array[Int]
  sorted_symbols : Array[Int]
  bl_count : Array[Int]
  max_code_len : Int
}

///|
fn HuffmanTree::new(code_lengths : Array[Int], max_code : Int) -> HuffmanTree {
  let len : Int = max_code + 1

  let mut max_code_len : Int = 0
  for i in 0.. max_code_len {
      max_code_len = code_lengths[i]
    }
  }

  let bl_count : Array[Int] = Array::make(max_code_len + 1, 0)
  for i in 0.. 0 {
      bl_count[code_lengths[i]] = bl_count[code_lengths[i]] + 1
    }
  }

  let next_code : Array[Int] = Array::make(max_code_len + 1, 0)
  let mut code : Int = 0
  for bits in 1..<=max_code_len {
    code = (code + bl_count[bits - 1]) << 1
    next_code[bits] = code
  }

  let first_code : Array[Int] = Array::make(max_code_len + 1, 0)
  let first_symbol : Array[Int] = Array::make(max_code_len + 1, 0)
  let codes : Array[Int] = Array::make(len, 0)
  for bits in 1..<=max_code_len {
    first_code[bits] = next_code[bits]
  }

  let mut symbol_count : Int = 0
  for i in 0.. 0 {
      symbol_count = symbol_count + 1
    }
  }

  let sorted_symbols : Array[Int] = Array::make(symbol_count, 0)
  let mut pos : Int = 0
  for bits in 1..<=max_code_len {
    first_symbol[bits] = pos
    for n in 0.. 0 {
      codes[n] = next_code[l]
      next_code[l] = next_code[l] + 1
    }
  }

  let table_bits : Int = if max_code_len < 10 { max_code_len } else { 10 }
  let table_size : Int = 1 << table_bits
  let table : Array[Int] = Array::make(table_size, -1)
  let table_lens : Array[Int] = Array::make(table_size, 0)

  for n in 0.. 0 && l <= table_bits {
      let c : Int = codes[n]
      let rev : Int = reverse_bits(c, l)
      let pad : Int = table_bits - l
      let entries : Int = 1 << pad
      for j in 0.. Int {
  let mut v : Int = value
  let mut r : Int = 0
  for _ in 0..> 1
  }
  r
}

///|
fn HuffmanTree::decode(self : HuffmanTree, br : BitReader) -> Int {
  if self.table_bits == 0 {
    return -1
  }
  let bits : UInt = br.peek(self.table_bits)
  let idx : Int = bits.reinterpret_as_int()
  let symbol : Int = self.table[idx]
  if symbol != -1 {
    let used : Int = self.table_lens[idx]
    br.advance(used)
    return symbol
  }
  let mut len : Int = self.table_bits + 1
  while len <= self.max_code_len {
    let raw : UInt = br.peek(len)
    let code : Int = reverse_bits(raw.reinterpret_as_int(), len)
    let fc : Int = self.first_code[len]
    let fs : Int = self.first_symbol[len]
    let count : Int = self.bl_count[len]
    if count > 0 && code >= fc && code < fc + count {
      br.advance(len)
      return self.sorted_symbols[fs + (code - fc)]
    }
    len = len + 1
  }
  -1
}

///|
pub enum InflateResult {
  Continue
  Done
  Error(String)
}

let length_base : Array[Int] = [
  3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
  35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258
]

let length_extra : Array[Int] = [
  0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
  3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0
]

let dist_base : Array[Int] = [
  1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
  257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577
]

let dist_extra : Array[Int] = [
  0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
  7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13
]

///|
fn inflate_block(br : BitReader, result : Array[Byte], pos : Int) -> (InflateResult, Int) {
  let bfinal : Int = br.read_bits(1).reinterpret_as_int()
  let btype : Int = br.read_bits(2).reinterpret_as_int()
  let mut pos : Int = pos

  if btype == 0 {
    br.align_to_byte()
    let len : UInt16 = br.read_bits(16).to_uint16()
    let nlen : UInt16 = br.read_bits(16).to_uint16()
    if (len ^ 0xFFFF) != nlen {
      (Error("Invalid stored block length"), pos)
    } else {
      let data : Bytes = br.read_bytes(len.to_int())
      for i in 0.. 0 {
            if cl_pos <= hlit {
              literal_code_lengths[cl_pos - 1]
            } else {
              dist_code_lengths[cl_pos - hlit - 1]
            }
          } else {
            0
          }
          for _ in 0..= 0 && i <= 143 {
          literal_code_lengths[i] = 8
        } else if i >= 144 && i <= 255 {
          literal_code_lengths[i] = 9
        } else if i >= 256 && i <= 279 {
          literal_code_lengths[i] = 7
        } else {
          literal_code_lengths[i] = 8
        }
      }
      for i in 0..<32 {
        dist_code_lengths[i] = 5
      }
    }

    let literal_tree : HuffmanTree = HuffmanTree::new(
      literal_code_lengths,
      literal_len_count - 1,
    )
    let dist_tree : HuffmanTree = HuffmanTree::new(
      dist_code_lengths,
      dist_count - 1,
    )

    let keep_going : Bool = true
    while keep_going {
      let code : Int = literal_tree.decode(br)
      if code == -1 {
        return (Error("Failed to decode literal"), pos)
      } else if code == 256 {
        return if bfinal != 0 { (Done, pos) } else { (Continue, pos) }
      } else if code < 256 {
        result[pos] = code.to_byte()
        pos = pos + 1
      } else {
        let len_code : Int = code - 257
        let length : Int = length_base[len_code] + br.read_bits(length_extra[len_code]).reinterpret_as_int()

        let dist_code : Int = dist_tree.decode(br)
        if dist_code == -1 {
          return (Error("Failed to decode distance"), pos)
        } else {
          let dist : Int = dist_base[dist_code] + br.read_bits(dist_extra[dist_code]).reinterpret_as_int()

          let start : Int = pos - dist
          if dist == 1 {
            let byte : Byte = result[start]
            for i in 0.. UInt16 {
  if offset + 1 >= data.length() {
    0
  } else {
    data[offset].to_uint16() | (data[offset + 1].to_uint16() << 8)
  }
}

///|
fn read_u32(data : Bytes, offset : Int) -> UInt {
  if offset + 4 > data.length() {
    0
  } else {
    data[offset].to_uint() |
    (data[offset + 1].to_uint() << 8) |
    (data[offset + 2].to_uint() << 16) |
    (data[offset + 3].to_uint() << 24)
  }
}

///|
fn parse_compression_method(method_val : UInt16) -> CompressionMethod {
  match method_val {
    0 => CompressionMethod::Stored
    8 => CompressionMethod::Deflated
    m => CompressionMethod::Unsupported(m)
  }
}

///|
fn parse_local_file_header(data : Bytes, offset : Int) -> LocalFileHeader? {
  if offset + 30 > data.length() {
    None
  } else {
    let signature : UInt = read_u32(data, offset)
    if signature != 0x04034B50 {
      None
    } else {
      let version_needed : UInt16 = read_u16(data, offset + 4)
      let flags : UInt16 = read_u16(data, offset + 6)
      let compression_method : CompressionMethod = parse_compression_method(
        read_u16(data, offset + 8),
      )
      let last_mod_time : UInt16 = read_u16(data, offset + 10)
      let last_mod_date : UInt16 = read_u16(data, offset + 12)
      let crc32 : UInt = read_u32(data, offset + 14)
      let compressed_size : UInt = read_u32(data, offset + 18)
      let uncompressed_size : UInt = read_u32(data, offset + 22)
      let filename_length : UInt16 = read_u16(data, offset + 26)
      let extra_field_length : UInt16 = read_u16(data, offset + 28)

      let header_size : Int = 30 +
        filename_length.to_int() +
        extra_field_length.to_int()
      if offset + header_size > data.length() {
        None
      } else {
        let filename_view = data.get_view(
          start=offset + 30,
          end=offset + 30 + filename_length.to_int(),
        )
        let extra_field_view = data.get_view(
          start=offset + 30 + filename_length.to_int(),
          end=offset + header_size,
        )

        match (filename_view, extra_field_view) {
          (Some(fv), Some(ev)) =>
            Some(LocalFileHeader::{
              signature,
              version_needed,
              flags,
              compression_method,
              last_mod_time,
              last_mod_date,
              crc32,
              compressed_size,
              uncompressed_size,
              filename_length,
              extra_field_length,
              filename: @utf8.decode_lossy(fv),
              extra_field: ev.to_owned(),
            })
          _ => None
        }
      }
    }
  }
}

///|
fn parse_central_directory_file_header(
  data : Bytes,
  offset : Int,
) -> CentralDirectoryFileHeader? {
  if offset + 46 > data.length() {
    None
  } else {
    let signature : UInt = read_u32(data, offset)
    if signature != 0x02014B50 {
      None
    } else {
      let version_made_by : UInt16 = read_u16(data, offset + 4)
      let version_needed : UInt16 = read_u16(data, offset + 6)
      let flags : UInt16 = read_u16(data, offset + 8)
      let compression_method : CompressionMethod = parse_compression_method(
        read_u16(data, offset + 10),
      )
      let last_mod_time : UInt16 = read_u16(data, offset + 12)
      let last_mod_date : UInt16 = read_u16(data, offset + 14)
      let crc32 : UInt = read_u32(data, offset + 16)
      let compressed_size : UInt = read_u32(data, offset + 20)
      let uncompressed_size : UInt = read_u32(data, offset + 24)
      let filename_length : UInt16 = read_u16(data, offset + 28)
      let extra_field_length : UInt16 = read_u16(data, offset + 30)
      let comment_length : UInt16 = read_u16(data, offset + 32)
      let disk_number_start : UInt16 = read_u16(data, offset + 34)
      let internal_file_attrs : UInt16 = read_u16(data, offset + 36)
      let external_file_attrs : UInt = read_u32(data, offset + 38)
      let local_header_offset : UInt = read_u32(data, offset + 42)

      let header_size : Int = 46 +
        filename_length.to_int() +
        extra_field_length.to_int() +
        comment_length.to_int()
      if offset + header_size > data.length() {
        None
      } else {
        let filename_view = data.get_view(
          start=offset + 46,
          end=offset + 46 + filename_length.to_int(),
        )
        let extra_field_view = data.get_view(
          start=offset + 46 + filename_length.to_int(),
          end=offset +
            46 +
            filename_length.to_int() +
            extra_field_length.to_int(),
        )
        let comment_view = data.get_view(
          start=offset +
            46 +
            filename_length.to_int() +
            extra_field_length.to_int(),
          end=offset + header_size,
        )

        match (filename_view, extra_field_view, comment_view) {
          (Some(fv), Some(ev), Some(cv)) =>
            Some(CentralDirectoryFileHeader::{
              signature,
              version_made_by,
              version_needed,
              flags,
              compression_method,
              last_mod_time,
              last_mod_date,
              crc32,
              compressed_size,
              uncompressed_size,
              filename_length,
              extra_field_length,
              comment_length,
              disk_number_start,
              internal_file_attrs,
              external_file_attrs,
              local_header_offset,
              filename: @utf8.decode_lossy(fv),
              extra_field: ev.to_owned(),
              comment: @utf8.decode_lossy(cv),
            })
          _ => None
        }
      }
    }
  }
}

///|
fn parse_zip64_extra_info(extra_field : Bytes) -> (UInt, UInt, UInt)? {
  let len : Int = extra_field.length()
  let mut offset : Int = 0
  while offset + 4 <= len {
    let header_id : UInt16 = read_u16(extra_field, offset)
    let data_size : UInt16 = read_u16(extra_field, offset + 2)
    let data_end : Int = offset + 4 + data_size.to_int()
    if data_end > len {
      return None
    }
    if header_id == 0x0001 {
      let mut compressed_size : UInt = 0
      let mut uncompressed_size : UInt = 0
      let mut local_header_offset : UInt = 0
      let mut pos : Int = offset + 4
      if pos + 8 <= data_end {
        uncompressed_size = read_u64(extra_field, pos)
        pos = pos + 8
      }
      if pos + 8 <= data_end {
        compressed_size = read_u64(extra_field, pos)
        pos = pos + 8
      }
      if pos + 8 <= data_end {
        local_header_offset = read_u64(extra_field, pos)
      }
      return Some((uncompressed_size, compressed_size, local_header_offset))
    }
    offset = data_end
  }
  None
}

///|
fn read_u64(data : Bytes, offset : Int) -> UInt {
  if offset + 8 > data.length() {
    0
  } else {
    data[offset].to_uint() |
    (data[offset + 1].to_uint() << 8) |
    (data[offset + 2].to_uint() << 16) |
    (data[offset + 3].to_uint() << 24) |
    (data[offset + 4].to_uint() << 32) |
    (data[offset + 5].to_uint() << 40) |
    (data[offset + 6].to_uint() << 48) |
    (data[offset + 7].to_uint() << 56)
  }
}

///|
fn parse_end_of_central_directory_record(
  data : Bytes,
) -> EndOfCentralDirectoryRecord? {
  let len : Int = data.length()

  if len < 22 {
    return None
  }

  let mut offset : Int = if len > 65536 + 22 { len - 65536 - 22 } else { 0 }
  while offset <= len - 22 {
    if read_u32(data, offset) == 0x06054B50 {
      let comment_length : UInt16 = read_u16(data, offset + 20)
      if offset + 22 + comment_length.to_int() == len {
        let signature : UInt = read_u32(data, offset)
        let disk_number : UInt16 = read_u16(data, offset + 4)
        let cd_start_disk : UInt16 = read_u16(data, offset + 6)
        let cd_entries_on_disk : UInt16 = read_u16(data, offset + 8)
        let cd_entries_total : UInt16 = read_u16(data, offset + 10)
        let cd_size : UInt = read_u32(data, offset + 12)
        let cd_offset : UInt = read_u32(data, offset + 16)
        let comment_view = data.get_view(
          start=offset + 22,
          end=offset + 22 + comment_length.to_int(),
        )

        match comment_view {
          Some(cv) =>
            return Some(EndOfCentralDirectoryRecord::{
              signature,
              disk_number,
              cd_start_disk,
              cd_entries_on_disk,
              cd_entries_total,
              cd_size,
              cd_offset,
              comment_length,
              comment: @utf8.decode_lossy(cv),
            })
          None => ()
        }
      }
    }
    offset = offset + 1
  }

  None
}