///|
pub(all) struct Checksum {
  algorithm : String
  value : Int
  bytes : Int
} derive(Debug, Eq)

///|
pub(all) struct Hash32 {
  algorithm : String
  value : Int
  bytes : Int
} derive(Debug, Eq)

///|
pub(all) struct ChunkFingerprint {
  start : Int
  length : Int
  hash : Int
} derive(Debug, Eq)

///|
pub(all) struct FingerprintBucket {
  hash : Int
  length : Int
  starts : Array[Int]
} derive(Debug)

///|
pub(all) struct DuplicateGroup {
  hash : Int
  length : Int
  occurrences : Int
  first_start : Int
} derive(Debug, Eq)

///|
pub(all) struct HashIndex {
  chunk_size : Int
  buckets : Array[FingerprintBucket]
} derive(Debug)

///|
pub(all) struct ContentSummary {
  bytes : Int
  checksum8 : Int
  hash32 : Int
  chunks : Int
  duplicate_pairs : Int
} derive(Debug, Eq)

///|
pub(all) struct CompareResult {
  same_length : Bool
  same_checksum : Bool
  same_hash : Bool
} derive(Debug, Eq)

///|
/// A content match that has been verified byte-for-byte after fingerprint
/// lookup. Hash equality alone is deliberately not treated as proof of
/// equality by this type.
pub(all) struct VerifiedChunkMatch {
  left_start : Int
  right_start : Int
  length : Int
} derive(Debug, Eq)

///|
/// Two independent polynomial fingerprints for a byte sequence.
///
/// This reduces accidental candidate collisions during transport planning, but
/// is still not a cryptographic digest. Use `byte_ranges_equal` before treating
/// untrusted content as identical.
pub(all) struct DualFingerprint {
  primary : Int
  secondary : Int
  bytes : Int
} derive(Debug, Eq)

///|
/// A serializable entry in a fixed-size or CDC chunk manifest.
pub(all) struct ManifestEntry {
  start : Int
  length : Int
  fingerprint : DualFingerprint
} derive(Debug)

///|
/// A deterministic chunk manifest suitable for backup or synchronization
/// metadata. It stores offsets and fingerprints, not source bytes.
pub(all) struct ChunkManifest {
  bytes : Int
  entries : Array[ManifestEntry]
} derive(Debug)

///|
pub fn normalize_byte(value : Int) -> Int {
  if value < 0 {
    0
  } else if value > 255 {
    255
  } else {
    value
  }
}

///|
pub fn checksum8_value(bytes : Array[Int]) -> Int {
  let mut sum = 0
  for byte in bytes {
    sum = (sum + normalize_byte(byte)) % 256
  }
  sum
}

///|
pub fn checksum8(bytes : Array[Int]) -> Checksum {
  {
    algorithm: "checksum8",
    value: checksum8_value(bytes),
    bytes: bytes.length(),
  }
}

///|
pub fn Checksum::to_json(self : Checksum) -> String {
  "{\"algorithm\":\"\{self.algorithm}\",\"value\":\{self.value},\"bytes\":\{self.bytes}}"
}

///|
fn normalize_modulo(value : Int) -> Int {
  if value <= 1 {
    1000000007
  } else {
    value
  }
}

///|
pub fn polynomial_hash_value(
  bytes : Array[Int],
  base? : Int = 257,
  modulo? : Int = 1000000007,
) -> Int {
  let m = normalize_modulo(modulo)
  let normalized_base = normalize_base(base, m)
  let mut value = 0L
  let m64 = m.to_int64()
  for byte in bytes {
    value = (
        value * normalized_base.to_int64() +
        (normalize_byte(byte) + 1).to_int64()
      ) %
      m64
  }
  value.to_int()
}

///|
fn normalize_base(base : Int, modulo : Int) -> Int {
  let positive = if base < 0 { -base } else { base }
  let reduced = positive % modulo
  if reduced < 2 {
    257 % modulo
  } else {
    reduced
  }
}

///|
fn modular_power(base : Int, exponent : Int, modulo : Int) -> Int {
  let mut result = 1L
  let factor = base.to_int64()
  let m = modulo.to_int64()
  for _i = 0; _i < exponent; _i = _i + 1 {
    result = result * factor % m
  }
  result.to_int()
}

///|
pub fn polynomial_hash(
  bytes : Array[Int],
  base? : Int = 257,
  modulo? : Int = 1000000007,
) -> Hash32 {
  {
    algorithm: "poly32",
    value: polynomial_hash_value(bytes, base~, modulo~),
    bytes: bytes.length(),
  }
}

///|
pub fn Hash32::to_json(self : Hash32) -> String {
  "{\"algorithm\":\"\{self.algorithm}\",\"value\":\{self.value},\"bytes\":\{self.bytes}}"
}

///|
pub fn ascii_code(ch : Char) -> Int {
  match ch {
    '0' => 48
    '1' => 49
    '2' => 50
    '3' => 51
    '4' => 52
    '5' => 53
    '6' => 54
    '7' => 55
    '8' => 56
    '9' => 57
    'A' => 65
    'B' => 66
    'C' => 67
    'D' => 68
    'E' => 69
    'F' => 70
    'G' => 71
    'H' => 72
    'I' => 73
    'J' => 74
    'K' => 75
    'L' => 76
    'M' => 77
    'N' => 78
    'O' => 79
    'P' => 80
    'Q' => 81
    'R' => 82
    'S' => 83
    'T' => 84
    'U' => 85
    'V' => 86
    'W' => 87
    'X' => 88
    'Y' => 89
    'Z' => 90
    'a' => 97
    'b' => 98
    'c' => 99
    'd' => 100
    'e' => 101
    'f' => 102
    'g' => 103
    'h' => 104
    'i' => 105
    'j' => 106
    'k' => 107
    'l' => 108
    'm' => 109
    'n' => 110
    'o' => 111
    'p' => 112
    'q' => 113
    'r' => 114
    's' => 115
    't' => 116
    'u' => 117
    'v' => 118
    'w' => 119
    'x' => 120
    'y' => 121
    'z' => 122
    ' ' => 32
    '-' => 45
    '_' => 95
    '.' => 46
    '/' => 47
    ':' => 58
    _ => 63
  }
}

///|
pub fn ascii_bytes(text : String) -> Array[Int] {
  let bytes : Array[Int] = []
  for i = 0; i < text.length(); i = i + 1 {
    match text.get_char(i) {
      Some(ch) => bytes.push(ascii_code(ch))
      None => ()
    }
  }
  bytes
}

///|
pub fn hash_ascii(text : String) -> Hash32 {
  polynomial_hash(ascii_bytes(text))
}

///|
pub fn window_hashes(
  bytes : Array[Int],
  window_size : Int,
  base? : Int = 257,
  modulo? : Int = 1000000007,
) -> Array[Hash32] {
  let result : Array[Hash32] = []
  if window_size <= 0 || bytes.length() < window_size {
    return result
  }
  let m = normalize_modulo(modulo)
  let normalized_base = normalize_base(base, m)
  let highest = modular_power(normalized_base, window_size - 1, m)
  let first : Array[Int] = []
  for i = 0; i < window_size; i = i + 1 {
    first.push(bytes[i])
  }
  let mut value = polynomial_hash_value(first, base=normalized_base, modulo=m)
  result.push({ algorithm: "poly32-window", value, bytes: window_size })
  for start = 1; start + window_size <= bytes.length(); start = start + 1 {
    let removed = normalize_byte(bytes[start - 1]) + 1
    let added = normalize_byte(bytes[start + window_size - 1]) + 1
    let without_old = (
        value.to_int64() -
        removed.to_int64() * highest.to_int64() % m.to_int64() +
        m.to_int64()
      ) %
      m.to_int64()
    value = ((without_old * normalized_base.to_int64() + added.to_int64()) %
    m.to_int64()).to_int()
    result.push({ algorithm: "poly32-window", value, bytes: window_size })
  }
  result
}

///|
pub fn ascii_window_hashes(text : String, window_size : Int) -> Array[Hash32] {
  window_hashes(ascii_bytes(text), window_size)
}

///|
pub fn chunk_fingerprints(
  bytes : Array[Int],
  chunk_size : Int,
) -> Array[ChunkFingerprint] {
  let result : Array[ChunkFingerprint] = []
  if chunk_size <= 0 {
    return result
  }
  let mut start = 0
  while start < bytes.length() {
    let chunk : Array[Int] = []
    let mut offset = 0
    while offset < chunk_size && start + offset < bytes.length() {
      chunk.push(bytes[start + offset])
      offset = offset + 1
    }
    result.push({
      start,
      length: chunk.length(),
      hash: polynomial_hash_value(chunk),
    })
    start = start + chunk_size
  }
  result
}

///|
pub fn ChunkFingerprint::to_json(self : ChunkFingerprint) -> String {
  "{\"start\":\{self.start},\"length\":\{self.length},\"hash\":\{self.hash}}"
}

///|
pub fn FingerprintBucket::new(chunk : ChunkFingerprint) -> FingerprintBucket {
  { hash: chunk.hash, length: chunk.length, starts: [chunk.start] }
}

///|
pub fn FingerprintBucket::add_start(
  self : FingerprintBucket,
  start : Int,
) -> Unit {
  self.starts.push(start)
}

///|
pub fn FingerprintBucket::occurrences(self : FingerprintBucket) -> Int {
  self.starts.length()
}

///|
pub fn FingerprintBucket::to_json(self : FingerprintBucket) -> String {
  "{\"hash\":\{self.hash},\"length\":\{self.length},\"occurrences\":\{self.occurrences()}}"
}

///|
pub fn DuplicateGroup::to_json(self : DuplicateGroup) -> String {
  "{\"hash\":\{self.hash},\"length\":\{self.length},\"occurrences\":\{self.occurrences},\"first_start\":\{self.first_start}}"
}

///|
pub fn HashIndex::new(chunk_size : Int) -> HashIndex {
  { chunk_size, buckets: [] }
}

///|
fn HashIndex::find_bucket(self : HashIndex, hash : Int, length : Int) -> Int {
  for i = 0; i < self.buckets.length(); i = i + 1 {
    if self.buckets[i].hash == hash && self.buckets[i].length == length {
      return i
    }
  }
  -1
}

///|
pub fn HashIndex::add_chunk(self : HashIndex, chunk : ChunkFingerprint) -> Unit {
  let index = self.find_bucket(chunk.hash, chunk.length)
  if index < 0 {
    self.buckets.push(FingerprintBucket::new(chunk))
  } else {
    self.buckets[index].add_start(chunk.start)
  }
}

///|
pub fn build_hash_index(bytes : Array[Int], chunk_size : Int) -> HashIndex {
  let index = HashIndex::new(chunk_size)
  let chunks = chunk_fingerprints(bytes, chunk_size)
  for chunk in chunks {
    index.add_chunk(chunk)
  }
  index
}

///|
pub fn HashIndex::bucket_count(self : HashIndex) -> Int {
  self.buckets.length()
}

///|
pub fn HashIndex::total_chunks(self : HashIndex) -> Int {
  let mut total = 0
  for bucket in self.buckets {
    total = total + bucket.occurrences()
  }
  total
}

///|
pub fn HashIndex::duplicate_group_count(self : HashIndex) -> Int {
  let mut count = 0
  for bucket in self.buckets {
    if bucket.occurrences() > 1 {
      count = count + 1
    }
  }
  count
}

///|
pub fn HashIndex::duplicate_groups(self : HashIndex) -> Array[DuplicateGroup] {
  let groups : Array[DuplicateGroup] = []
  for bucket in self.buckets {
    if bucket.occurrences() > 1 {
      groups.push({
        hash: bucket.hash,
        length: bucket.length,
        occurrences: bucket.occurrences(),
        first_start: bucket.starts[0],
      })
    }
  }
  groups
}

///|
pub fn HashIndex::candidate_starts(
  self : HashIndex,
  hash : Int,
  length : Int,
) -> Array[Int] {
  let index = self.find_bucket(hash, length)
  if index < 0 {
    []
  } else {
    self.buckets[index].starts
  }
}

///|
pub fn HashIndex::to_json(self : HashIndex) -> String {
  "{\"chunk_size\":\{self.chunk_size},\"buckets\":\{self.bucket_count()},\"chunks\":\{self.total_chunks()},\"duplicate_groups\":\{self.duplicate_group_count()}}"
}

///|
/// Compares two byte ranges without allocating slice arrays.
///
/// Inputs are normalized in the same way as the polynomial fingerprint APIs,
/// so a caller cannot accidentally accept bytes that hash differently from
/// their verification representation.
pub fn byte_ranges_equal(
  left : Array[Int],
  left_start : Int,
  right : Array[Int],
  right_start : Int,
  length : Int,
) -> Bool {
  if left_start < 0 ||
    right_start < 0 ||
    length < 0 ||
    left_start + length > left.length() ||
    right_start + length > right.length() {
    return false
  }
  for offset = 0; offset < length; offset = offset + 1 {
    if normalize_byte(left[left_start + offset]) !=
      normalize_byte(right[right_start + offset]) {
      return false
    }
  }
  true
}

///|
/// Finds equal fixed-size chunks in two contents.
///
/// The right-side index narrows the search by fingerprint and length; every
/// candidate is then checked with `byte_ranges_equal`, avoiding false-positive
/// deduplication when a non-cryptographic fingerprint collides.
pub fn verified_fixed_chunk_matches(
  left : Array[Int],
  right : Array[Int],
  chunk_size : Int,
) -> Array[VerifiedChunkMatch] {
  let matches : Array[VerifiedChunkMatch] = []
  if chunk_size <= 0 {
    return matches
  }
  let right_index = build_hash_index(right, chunk_size)
  for chunk in chunk_fingerprints(left, chunk_size) {
    for right_start in right_index.candidate_starts(chunk.hash, chunk.length) {
      if byte_ranges_equal(left, chunk.start, right, right_start, chunk.length) {
        matches.push({
          left_start: chunk.start,
          right_start,
          length: chunk.length,
        })
      }
    }
  }
  matches
}

///|
/// Verifies matches between arbitrary chunk layouts, including CDC manifests.
/// It is intentionally straightforward so callers can apply their own index
/// strategy when processing very large manifests.
pub fn verified_chunk_matches(
  left : Array[Int],
  left_chunks : Array[ChunkFingerprint],
  right : Array[Int],
  right_chunks : Array[ChunkFingerprint],
) -> Array[VerifiedChunkMatch] {
  let matches : Array[VerifiedChunkMatch] = []
  for left_chunk in left_chunks {
    for right_chunk in right_chunks {
      if left_chunk.hash == right_chunk.hash &&
        left_chunk.length == right_chunk.length &&
        byte_ranges_equal(
          left,
          left_chunk.start,
          right,
          right_chunk.start,
          left_chunk.length,
        ) {
        matches.push({
          left_start: left_chunk.start,
          right_start: right_chunk.start,
          length: left_chunk.length,
        })
      }
    }
  }
  matches
}

///|
pub fn VerifiedChunkMatch::to_json(self : VerifiedChunkMatch) -> String {
  "{\"left_start\":\{self.left_start},\"right_start\":\{self.right_start},\"length\":\{self.length}}"
}

///|
pub fn dual_fingerprint(bytes : Array[Int]) -> DualFingerprint {
  {
    primary: polynomial_hash_value(bytes, base=257, modulo=1000000007),
    secondary: polynomial_hash_value(bytes, base=263, modulo=1000000009),
    bytes: bytes.length(),
  }
}

///|
pub fn DualFingerprint::to_json(self : DualFingerprint) -> String {
  "{\"primary\":\{self.primary},\"secondary\":\{self.secondary},\"bytes\":\{self.bytes}}"
}

///|
fn fingerprint_chunk_range(
  bytes : Array[Int],
  chunk : ChunkFingerprint,
) -> DualFingerprint {
  let values : Array[Int] = []
  for offset = 0; offset < chunk.length; offset = offset + 1 {
    values.push(bytes[chunk.start + offset])
  }
  dual_fingerprint(values)
}

///|
fn manifest_from_chunks(
  bytes : Array[Int],
  chunks : Array[ChunkFingerprint],
) -> ChunkManifest {
  let entries : Array[ManifestEntry] = []
  for chunk in chunks {
    entries.push({
      start: chunk.start,
      length: chunk.length,
      fingerprint: fingerprint_chunk_range(bytes, chunk),
    })
  }
  { bytes: bytes.length(), entries }
}

///|
/// Builds a manifest for fixed-size chunking.
pub fn fixed_chunk_manifest(
  bytes : Array[Int],
  chunk_size : Int,
) -> ChunkManifest {
  manifest_from_chunks(bytes, chunk_fingerprints(bytes, chunk_size))
}

///|
/// Builds a manifest for content-defined chunks.
pub fn cdc_chunk_manifest(
  bytes : Array[Int],
  config : CdcConfig,
) -> ChunkManifest {
  manifest_from_chunks(bytes, content_defined_chunks(bytes, config))
}

///|
pub fn ChunkManifest::entry_count(self : ChunkManifest) -> Int {
  self.entries.length()
}

///|
pub fn ChunkManifest::to_json(self : ChunkManifest) -> String {
  "{\"bytes\":\{self.bytes},\"entries\":\{self.entry_count()}}"
}

///|
/// Returns source chunks not present in a destination under byte-for-byte
/// verification. This is a transport plan, not a copy operation.
pub fn missing_fixed_chunks(
  source : Array[Int],
  destination : Array[Int],
  chunk_size : Int,
) -> Array[ChunkFingerprint] {
  let missing : Array[ChunkFingerprint] = []
  let matches = verified_fixed_chunk_matches(source, destination, chunk_size)
  for chunk in chunk_fingerprints(source, chunk_size) {
    let mut found = false
    for matched in matches {
      if matched.left_start == chunk.start && matched.length == chunk.length {
        found = true
        break
      }
    }
    if !found {
      missing.push(chunk)
    }
  }
  missing
}

///|
pub fn has_duplicate_hashes(chunks : Array[ChunkFingerprint]) -> Bool {
  for i = 0; i < chunks.length(); i = i + 1 {
    for j = i + 1; j < chunks.length(); j = j + 1 {
      if chunks[i].hash == chunks[j].hash &&
        chunks[i].length == chunks[j].length {
        return true
      }
    }
  }
  false
}

///|
pub fn duplicate_hash_count(chunks : Array[ChunkFingerprint]) -> Int {
  let mut count = 0
  for i = 0; i < chunks.length(); i = i + 1 {
    for j = i + 1; j < chunks.length(); j = j + 1 {
      if chunks[i].hash == chunks[j].hash &&
        chunks[i].length == chunks[j].length {
        count = count + 1
      }
    }
  }
  count
}

///|
pub fn summarize_content(
  bytes : Array[Int],
  chunk_size? : Int = 4,
) -> ContentSummary {
  let chunks = chunk_fingerprints(bytes, chunk_size)
  {
    bytes: bytes.length(),
    checksum8: checksum8_value(bytes),
    hash32: polynomial_hash_value(bytes),
    chunks: chunks.length(),
    duplicate_pairs: duplicate_hash_count(chunks),
  }
}

///|
pub fn ContentSummary::to_json(self : ContentSummary) -> String {
  "{\"bytes\":\{self.bytes},\"checksum8\":\{self.checksum8},\"hash32\":\{self.hash32},\"chunks\":\{self.chunks},\"duplicate_pairs\":\{self.duplicate_pairs}}"
}

///|
pub fn compare_content(left : Array[Int], right : Array[Int]) -> CompareResult {
  {
    same_length: left.length() == right.length(),
    same_checksum: checksum8_value(left) == checksum8_value(right),
    same_hash: polynomial_hash_value(left) == polynomial_hash_value(right),
  }
}

///|
pub fn CompareResult::is_probable_match(self : CompareResult) -> Bool {
  self.same_length && self.same_checksum && self.same_hash
}