///|
const MATCH_BUCKET_COUNT : Int = 4096

///|
priv struct MatchCandidate {
  address : Int
  size : Int
}

///|
priv struct MatchFinder {
  source : Bytes
  target : Bytes
  window_offset : Int
  window_size : Int
  bucket_heads : Array[Int]
  previous : Array[Int]
}

///|
fn hash_four_bytes(bytes : Bytes, offset : Int) -> Int {
  let a = bytes[offset].to_int()
  let b = bytes[offset + 1].to_int()
  let c = bytes[offset + 2].to_int()
  let d = bytes[offset + 3].to_int()
  (((a * 257 + b) * 257 + c) * 257 + d) & (MATCH_BUCKET_COUNT - 1)
}

///|
fn MatchFinder::new(
  source : Bytes,
  target : Bytes,
  window_offset : Int,
  window_size : Int,
) -> MatchFinder raise VcdiffError {
  if source.length() > MAX_PORTABLE_INT - window_size {
    raise IntegerOverflow(offset=-1)
  }
  let finder = {
    source,
    target,
    window_offset,
    window_size,
    bucket_heads: Array::make(MATCH_BUCKET_COUNT, -1),
    previous: Array::make(source.length() + window_size, -1),
  }
  if source.length() >= 4 {
    for position = 0; position <= source.length() - 4; position = position + 1 {
      finder.insert_source(position)
    }
  }
  finder
}

///|
fn MatchFinder::insert_source(self : MatchFinder, position : Int) -> Unit {
  let bucket = hash_four_bytes(self.source, position)
  self.previous[position] = self.bucket_heads[bucket]
  self.bucket_heads[bucket] = position
}

///|
fn MatchFinder::target_has_hash(self : MatchFinder, position : Int) -> Bool {
  position >= 0 && position + 4 <= self.window_size
}

///|
fn MatchFinder::target_hash(self : MatchFinder, position : Int) -> Int {
  hash_four_bytes(self.target, self.window_offset + position)
}

///|
fn MatchFinder::insert_target(self : MatchFinder, position : Int) -> Unit {
  if !self.target_has_hash(position) {
    return
  }
  let combined = self.source.length() + position
  let bucket = self.target_hash(position)
  self.previous[combined] = self.bucket_heads[bucket]
  self.bucket_heads[bucket] = combined
}

///|
fn MatchFinder::source_match_length(
  self : MatchFinder,
  source_position : Int,
  target_local : Int,
) -> Int {
  let source_remaining = self.source.length() - source_position
  let target_remaining = self.window_size - target_local
  let limit = if source_remaining < target_remaining {
    source_remaining
  } else {
    target_remaining
  }
  let mut length = 0
  while length < limit &&
        self.source[source_position + length] ==
        self.target[self.window_offset + target_local + length] {
    length += 1
  }
  length
}

///|
fn MatchFinder::target_match_length(
  self : MatchFinder,
  candidate_local : Int,
  target_local : Int,
) -> Int {
  let available_history = target_local - candidate_local
  let target_remaining = self.window_size - target_local
  let limit = if available_history < target_remaining {
    available_history
  } else {
    target_remaining
  }
  let mut length = 0
  while length < limit &&
        self.target[self.window_offset + candidate_local + length] ==
        self.target[self.window_offset + target_local + length] {
    length += 1
  }
  length
}

///|
fn MatchFinder::candidate_length(
  self : MatchFinder,
  address : Int,
  target_local : Int,
  enable_target_matches : Bool,
) -> Int {
  if address < self.source.length() {
    self.source_match_length(address, target_local)
  } else if enable_target_matches {
    let candidate_local = address - self.source.length()
    if candidate_local < target_local {
      self.target_match_length(candidate_local, target_local)
    } else {
      0
    }
  } else {
    0
  }
}

///|
fn MatchFinder::find_best(
  self : MatchFinder,
  target_local : Int,
  minimum_match : Int,
  max_candidate_chain : Int,
  enable_target_matches : Bool,
) -> MatchCandidate {
  if !self.target_has_hash(target_local) {
    return { address: -1, size: 0 }
  }
  let bucket = self.target_hash(target_local)
  let mut candidate = self.bucket_heads[bucket]
  let mut visited = 0
  let mut best_address = -1
  let mut best_size = 0
  while candidate >= 0 && visited < max_candidate_chain {
    let size = self.candidate_length(
      candidate, target_local, enable_target_matches,
    )
    if size > best_size || (size == best_size && candidate < best_address) {
      best_address = candidate
      best_size = size
    }
    candidate = self.previous[candidate]
    visited += 1
  }
  if best_size < minimum_match {
    { address: -1, size: 0 }
  } else {
    { address: best_address, size: best_size }
  }
}

///|
fn run_length(target : Bytes, offset : Int, limit : Int) -> Int {
  if offset >= limit {
    return 0
  }
  let byte = target[offset]
  let mut length = 1
  while offset + length < limit && target[offset + length] == byte {
    length += 1
  }
  length
}