// The LZ77 dictionary of Shared Brotli (RFC 9841 section 3.2), as RFC
// 9842's `dcb` coding uses one: bytes outside the window that backward
// distances past the window's reach address, before the static dictionary.

///|
/// A dictionary of raw bytes for `Decoder` and `Encoder`, held by reference
/// (the bytes it is a view of stay alive as long as it does).
pub struct Dictionary {
  priv content : BytesView
  // What encoders search it with, built by the first that needs it.
  priv mut index : DictionaryIndex?
}

///|
/// A dictionary of `content`, as RFC 9841 section 3.2 calls an LZ77
/// dictionary and `brotli -D` takes one.
pub fn Dictionary::Dictionary(content : BytesView) -> Dictionary {
  { content, index: None, }
}

///|
/// Bytes the dictionary holds of its own: once an encoder has used it, the
/// index encoders search it with, shared by every encoder given it: a copy
/// of the dictionary's last 64 MiB at most (the part a distance can reach),
/// four bytes per byte of that, and a table of at most 512 KiB. Its content
/// is the caller's and not counted.
pub fn Dictionary::memory_usage(self : Dictionary) -> Int32 {
  match self.index {
    Some(index) =>
      index.bytes.length() + 4 * (index.head.length() + index.chain.length())
    None => 0
  }
}

///|
/// The dictionary's bytes.
pub fn Dictionary::content(self : Dictionary) -> BytesView {
  self.content
}

///|
/// The dictionary's length in bytes.
pub fn Dictionary::length(self : Dictionary) -> Int32 {
  self.content.length()
}

///|
/// The bytes of a copy from the dictionary, as far as the output allows.
fn Decoder::dictionary_copy(self : Decoder) -> Status? {
  guard self.dictionary is Some(dict) else {
    abort("dictionary_copy without a dictionary")
  }
  let content = dict.content
  while self.copy_remaining > 0 {
    let want = self.copy_remaining.min(1 << 16)
    if self.free_space() < want {
      self.drain()
    }
    let n = want.min(self.free_space())
    if n == 0 {
      return Some(NeedMoreOutput)
    }
    self.ensure_space(n) |> ignore
    // In one copy, or two where the ring wraps.
    let mut done = 0
    while done < n {
      let chunk = (n - done).min(self.ring.length() - self.wpos)
      let at = self.dict_at + done
      self.ring.blit_from_bytesview(self.wpos, content[at:at + chunk])
      self.advance(chunk)
      done += chunk
    }
    self.dict_at += n
    self.copy_remaining -= n
  }
  self.state = if self.meta_remaining == 0 { MetaDone } else { CommandStart }
  None
}

///|
/// How an encoder finds matches in an LZ77 dictionary: every position's
/// four-byte hash chained to the one before with the same hash. Built once,
/// read only after, so encoders share it.
priv struct DictionaryIndex {
  bytes : FixedArray[Byte]
  // For each hash, the latest position with it, plus one (0 for none); for
  // each position, the one before with its hash, plus one.
  head : FixedArray[Int32]
  chain : FixedArray[Int32]
  bits : Int32
}

///|
/// The candidates a search of the dictionary looks at.
const DICTIONARY_ATTEMPTS : Int32 = 16

///|
/// The longest distance with NPOSTFIX and NDIRECT 0 (RFC 7932 section 4):
/// a match into the dictionary further back is not taken.
const MAX_CODED_DISTANCE : Int32 = 67108860

///|
/// The index of `content`'s last `MAX_CODED_DISTANCE` bytes at most: a
/// distance past the window reaches no further into the dictionary, so the
/// rest is never searched, and the sizes stay within 32-bit arithmetic.
/// Positions count from the start of that part, which ends where the
/// dictionary ends, so distances are the same.
fn DictionaryIndex::new(content : BytesView) -> DictionaryIndex {
  let part = content[(content.length() - MAX_CODED_DISTANCE).max(0):]
  let n = part.length()
  let bytes = part.to_fixedarray()
  // A table about as long as the dictionary, of 256 to 2^17 entries.
  let bits = (if n < 2 { 1 } else { 32 - (n - 1).clz() }).clamp(min=8, max=17)
  let head = FixedArray::make(1 << bits, 0)
  let chain = FixedArray::make(n, 0)
  // p + 4 <= n: hash4 reads four bytes of the dictionary.
  for p in 0..<(n - 3) {
    let h = @lz77.hash4(bytes, p, bits)
    chain[p] = head[h]
    head[h] = p + 1
  }
  { bytes, head, chain, bits, }
}

///|
/// The dictionary's index, built the first time.
fn Dictionary::search_index(self : Dictionary) -> DictionaryIndex {
  match self.index {
    Some(index) => index
    None => {
      let index = DictionaryIndex::new(self.content)
      self.index = Some(index)
      index
    }
  }
}

///|
/// The longest match for `data[pos..pos + limit)` in the dictionary longer
/// than `best`, with the distance a decoder reads it from at `reach`, the
/// window's reach (RFC 9841 section 3.2: `reach` plus the bytes from the
/// match to the dictionary's end); `best` if none. A match never runs past
/// the dictionary's end, which the reference decoder refuses. `pos + 4`
/// is within `data` when `limit` is at least 4.
fn Encoder::dictionary_match(
  self : Encoder,
  index : DictionaryIndex,
  pos : Int32,
  limit : Int32,
  reach : Int32,
  best : Int32,
) -> Int32 {
  guard limit >= @lz77.MIN_MATCH else { return best }
  let bytes = index.bytes
  let n = bytes.length()
  let data = self.data
  let mut best = best
  let mut q = index.head[@lz77.hash4(data, pos, index.bits)] - 1
  let mut attempts = DICTIONARY_ATTEMPTS
  while q >= 0 && attempts > 0 {
    // n - q is at most MAX_CODED_DISTANCE and reach at most 2^24, so the sum
    // is checked before it is formed. Older candidates lie further back.
    if n - q > MAX_CODED_DISTANCE - reach {
      break
    }
    let dist = reach + (n - q)
    let most = limit.min(n - q)
    if most > best {
      let mut len = 0
      while len < most && bytes[q + len] == data[pos + len] {
        len += 1
      }
      if len > best && len >= @lz77.MIN_MATCH {
        best = len
        self.found_dist = dist
      }
    }
    q = index.chain[q] - 1
    attempts -= 1
  }
  best
}