// The LZ77 layer and the base64 text layer of the compact language format
// (see compact.mbt).
//
// LZ77 stream: a sequence of `u` literal count, that many literal bytes, then
// (unless the output is complete) `u` (match length - lz_min_match) and `u`
// (distance - 1); a match copies `length` bytes starting `distance` bytes
// back in the output, possibly overlapping the bytes it writes. The stream
// ends when the output has the declared raw length, after a literal run.

///|
let lz_min_match : Int = 4

///|
let lz_hash_bits : Int = 16

///|
/// Maximum number of earlier positions tried per position. Fixed, so the
/// output is a deterministic function of the input.
let lz_max_chain : Int = 32

///|
let lz_max_distance : Int = 1 << 22

///|
let lz_max_match : Int = 1 << 16

///|
fn lz_write_uint(buf : @buffer.Buffer, value : Int) -> Unit {
  let mut v = value
  while v >= 0x80 {
    buf.write_byte(((v & 0x7f) | 0x80).to_byte())
    v = v >> 7
  }
  buf.write_byte(v.to_byte())
}

///|
fn lz_hash(data : Bytes, i : Int) -> Int {
  let v = data[i].to_uint() |
    (data[i + 1].to_uint() << 8) |
    (data[i + 2].to_uint() << 16) |
    (data[i + 3].to_uint() << 24)
  ((v * 2654435761U) >> (32 - lz_hash_bits)).reinterpret_as_int()
}

///|
/// Compress `data` with a greedy LZ77 over hash chains.
fn lz_compress(data : Bytes) -> Bytes {
  let n = data.length()
  let out = @buffer.Buffer(size_hint=n / 4 + 16)
  let head = FixedArray::make(1 << lz_hash_bits, -1)
  let prev = FixedArray::make(n, -1)
  fn insert(p : Int) {
    if p + lz_min_match <= n {
      let h = lz_hash(data, p)
      prev[p] = head[h]
      head[h] = p
    }
  }

  let mut i = 0
  let mut literal_start = 0
  while i < n {
    let mut best_length = 0
    let mut best_distance = 0
    if i + lz_min_match <= n {
      let limit = if n - i < lz_max_match { n - i } else { lz_max_match }
      let mut candidate = head[lz_hash(data, i)]
      let mut depth = 0
      while candidate >= 0 &&
            depth < lz_max_chain &&
            i - candidate <= lz_max_distance {
        let mut length = 0
        while length < limit && data[candidate + length] == data[i + length] {
          length += 1
        }
        if length > best_length {
          best_length = length
          best_distance = i - candidate
          if length == limit {
            break
          }
        }
        candidate = prev[candidate]
        depth += 1
      }
    }
    if best_length >= lz_min_match {
      lz_write_uint(out, i - literal_start)
      out.write_bytes(data[literal_start:i])
      lz_write_uint(out, best_length - lz_min_match)
      lz_write_uint(out, best_distance - 1)
      for p in i..<(i + best_length) {
        insert(p)
      }
      i += best_length
      literal_start = i
    } else {
      insert(i)
      i += 1
    }
  }
  lz_write_uint(out, n - literal_start)
  out.write_bytes(data[literal_start:n])
  out.to_bytes()
}

///|
/// Decompress the LZ77 stream starting at `data[start]` into `raw_length`
/// bytes.
fn lz_decompress(
  data : FixedArray[Byte],
  start : Int,
  raw_length : Int,
) -> FixedArray[Byte] raise CompactError {
  let out : FixedArray[Byte] = FixedArray::make(raw_length, 0)
  let r = CompactReader::{ data, pos: start, }
  let mut o = 0
  for ;; {
    let literals = r.uint()
    if literals > raw_length - o || literals > data.length() - r.pos {
      raise CompactError("literal run out of range")
    }
    FixedArray::unsafe_blit(out, o, data, r.pos, literals)
    r.pos += literals
    o += literals
    if o == raw_length {
      break
    }
    let length = r.uint() + lz_min_match
    let distance = r.uint() + 1
    if distance > o || length > raw_length - o {
      raise CompactError("match out of range")
    }
    let from = o - distance
    if distance >= length {
      FixedArray::unsafe_blit(out, o, out, from, length)
    } else {
      for k in 0.. String {
  let n = data.length()
  let sb = StringBuilder(size_hint=(n + 2) / 3 * 4)
  let mut i = 0
  while i + 3 <= n {
    let v = (data[i].to_int() << 16) |
      (data[i + 1].to_int() << 8) |
      data[i + 2].to_int()
    sb.write_char(base64_alphabet[(v >> 18) & 63].unsafe_to_char())
    sb.write_char(base64_alphabet[(v >> 12) & 63].unsafe_to_char())
    sb.write_char(base64_alphabet[(v >> 6) & 63].unsafe_to_char())
    sb.write_char(base64_alphabet[v & 63].unsafe_to_char())
    i += 3
  }
  let rest = n - i
  if rest > 0 {
    let v = (data[i].to_int() << 16) |
      (if rest == 2 { data[i + 1].to_int() << 8 } else { 0 })
    sb.write_char(base64_alphabet[(v >> 18) & 63].unsafe_to_char())
    sb.write_char(base64_alphabet[(v >> 12) & 63].unsafe_to_char())
    if rest == 2 {
      sb.write_char(base64_alphabet[(v >> 6) & 63].unsafe_to_char())
    } else {
      sb.write_char('=')
    }
    sb.write_char('=')
  }
  sb.to_string()
}

///|
fn base64_digit(c : UInt16) -> Int {
  match c {
    'A'..<='Z' => c.to_int() - 'A'.to_int()
    'a'..<='z' => c.to_int() - 'a'.to_int() + 26
    '0'..<='9' => c.to_int() - '0'.to_int() + 52
    '+' => 62
    '/' => 63
    ' ' | '\n' | '\r' | '\t' => -1
    '=' => -2
    _ => -3
  }
}

///|
fn base64_decode(text : StringView) -> FixedArray[Byte] raise CompactError {
  let out = @buffer.Buffer(size_hint=text.length() / 4 * 3)
  let mut acc = 0
  let mut count = 0
  let mut padding = 0
  for i in 0..= 0 && padding > 0) {
      raise CompactError("invalid base64 text")
    }
    if d == -2 {
      padding += 1
      acc = acc << 6
    } else {
      acc = (acc << 6) | d
    }
    count += 1
    if count == 4 {
      out.write_byte((acc >> 16).to_byte())
      if padding < 2 {
        out.write_byte((acc >> 8).to_byte())
      }
      if padding < 1 {
        out.write_byte(acc.to_byte())
      }
      acc = 0
      count = 0
    }
  }
  if count != 0 || padding > 2 {
    raise CompactError("truncated base64 text")
  }
  FixedArray::from_iter(out.to_bytes().iter())
}