// The encoder's parameters for each level, transcribed from the reference
// implementation: facebook/zstd v1.5.7, lib/compress/clevels.h,
// `ZSTD_defaultCParameters` (BSD license; see NOTICE), levels 1 to 12 of
// its four tables and the row the negative levels start from. Tree rows use lazy2 with the same adjusted numbers:
// binary trees and optimal parsing are outside this encoder's scope.

///|
/// The match-finding strategy of a level, as `ZSTD_strategy` names it.
/// `Btlazy2` and `Btopt` appear in the tables for small inputs at levels 9
/// to 12; the encoder maps these to Lazy2, retaining their numeric row.
priv enum Strategy {
  Fast
  Dfast
  Greedy
  Lazy
  Lazy2
  Btlazy2
  Btopt
}

///|
/// One row of `ZSTD_defaultCParameters`: the logs of the window, the chain
/// table and the hash table, the search depth (log), the shortest match,
/// the target length and the strategy. Fast reads window_log, hash_log,
/// min_match (hash width) and target_length (acceleration).
/// Double-fast additionally uses chain_log for its short hash table and
/// always hashes eight bytes in its long table.
priv struct Params {
  window_log : Int32
  chain_log : Int32
  hash_log : Int32
  search_log : Int32
  min_match : Int32
  target_length : Int32
  strategy : Strategy
  // Whether greedy, lazy and lazy2 search rows of tags instead of hash
  // chains; set by `encoder_params`.
  row_finder : Bool
}

///|
/// The highest level implemented; higher ones act as this one.
const MAX_LEVEL : Int32 = 12

///|
/// The level `Encoder` and `compress` use by default, as zstd's.
const DEFAULT_LEVEL : Int32 = 3

///|
/// The lowest level, zstd's `ZSTD_minCLevel()`: minus the largest block,
/// the most acceleration a target length can ask for.
const MIN_LEVEL : Int32 = -131072

///|
/// The level an encoder works at for `level`: 0 is the default, as in zstd,
/// and the rest is clamped to `MIN_LEVEL` to `MAX_LEVEL`.
fn effective_level(level : Int32) -> Int32 {
  if level == 0 {
    DEFAULT_LEVEL
  } else {
    level.clamp(min=MIN_LEVEL, max=MAX_LEVEL)
  }
}

///|
fn row(
  window_log : Int32,
  chain_log : Int32,
  hash_log : Int32,
  search_log : Int32,
  min_match : Int32,
  target_length : Int32,
  strategy : Strategy,
) -> Params {
  {
    window_log,
    chain_log,
    hash_log,
    search_log,
    min_match,
    target_length,
    strategy,
    row_finder: false,
  }
}

///|
/// The four tables, each for levels 1 to 12 (index `level - 1`): for any
/// input larger than 256 KiB or of unknown size, and for inputs of at most
/// 256 KiB, 128 KiB and 16 KiB.
let level_tables : FixedArray[FixedArray[Params]] = [
  [
    row(19, 13, 14, 1, 7, 0, Fast),
    row(20, 15, 16, 1, 6, 0, Fast),
    row(21, 16, 17, 1, 5, 0, Dfast),
    row(21, 18, 18, 1, 5, 0, Dfast),
    row(21, 18, 19, 3, 5, 2, Greedy),
    row(21, 18, 19, 3, 5, 4, Lazy),
    row(21, 19, 20, 4, 5, 8, Lazy),
    row(21, 19, 20, 4, 5, 16, Lazy2),
    row(22, 20, 21, 4, 5, 16, Lazy2),
    row(22, 21, 22, 5, 5, 16, Lazy2),
    row(22, 21, 22, 6, 5, 16, Lazy2),
    row(22, 22, 23, 6, 5, 32, Lazy2),
  ],
  [
    row(18, 13, 14, 1, 6, 0, Fast),
    row(18, 14, 14, 1, 5, 0, Dfast),
    row(18, 16, 16, 1, 4, 0, Dfast),
    row(18, 16, 17, 3, 5, 2, Greedy),
    row(18, 17, 18, 5, 5, 2, Greedy),
    row(18, 18, 19, 3, 5, 4, Lazy),
    row(18, 18, 19, 4, 4, 4, Lazy),
    row(18, 18, 19, 4, 4, 8, Lazy2),
    row(18, 18, 19, 5, 4, 8, Lazy2),
    row(18, 18, 19, 6, 4, 8, Lazy2),
    row(18, 18, 19, 5, 4, 12, Btlazy2),
    row(18, 19, 19, 7, 4, 12, Btlazy2),
  ],
  [
    row(17, 12, 13, 1, 6, 0, Fast),
    row(17, 13, 15, 1, 5, 0, Fast),
    row(17, 15, 16, 2, 5, 0, Dfast),
    row(17, 17, 17, 2, 4, 0, Dfast),
    row(17, 16, 17, 3, 4, 2, Greedy),
    row(17, 16, 17, 3, 4, 4, Lazy),
    row(17, 16, 17, 3, 4, 8, Lazy2),
    row(17, 16, 17, 4, 4, 8, Lazy2),
    row(17, 16, 17, 5, 4, 8, Lazy2),
    row(17, 16, 17, 6, 4, 8, Lazy2),
    row(17, 17, 17, 5, 4, 8, Btlazy2),
    row(17, 18, 17, 7, 4, 12, Btlazy2),
  ],
  [
    row(14, 14, 15, 1, 5, 0, Fast),
    row(14, 14, 15, 1, 4, 0, Fast),
    row(14, 14, 15, 2, 4, 0, Dfast),
    row(14, 14, 14, 4, 4, 2, Greedy),
    row(14, 14, 14, 3, 4, 4, Lazy),
    row(14, 14, 14, 4, 4, 8, Lazy2),
    row(14, 14, 14, 6, 4, 8, Lazy2),
    row(14, 14, 14, 8, 4, 8, Lazy2),
    row(14, 15, 14, 5, 4, 8, Btlazy2),
    row(14, 15, 14, 9, 4, 8, Btlazy2),
    row(14, 15, 14, 3, 4, 12, Btopt),
    row(14, 15, 14, 4, 3, 24, Btopt),
  ],
]

///|
/// Row 0 of each table, "base for negative levels": fast rows that a
/// negative level gives its acceleration, as the target length.
let negative_rows : FixedArray[Params] = [
  row(19, 12, 13, 1, 6, 1, Fast),
  row(18, 12, 13, 1, 5, 1, Fast),
  row(17, 12, 12, 1, 5, 1, Fast),
  row(14, 12, 13, 1, 5, 1, Fast),
]

///|
/// The row of `table` for `level`, from `MIN_LEVEL` to 12 but not 0: a
/// negative level takes row 0 with its acceleration, `-level`, as the
/// target length, as `ZSTD_getCParams_internal` does.
fn level_row(table : Int32, level : Int32) -> Params {
  if level < 0 {
    { ..negative_rows[table], target_length: -level, }
  } else {
    level_tables[table][level - 1]
  }
}

///|
/// Whether a block's literals are Huffman-coded at all: not for a fast
/// level that accelerates, a negative one, as `ZSTD_literalsCompressionIsDisabled`
/// decides by default. No level from 1 up is such a row.
fn compresses_literals(params : Params) -> Bool {
  !(params.strategy is Fast && params.target_length > 0)
}

///|
/// The parameters for `level` (already made `effective_level`) and an input
/// of `size` bytes, or of unknown size, after a dictionary of `dict_size`
/// bytes (0 for none) put in the window before it.
///
/// As `ZSTD_getCParams` does, a known size picks the table for its size
/// class, and the window and tables then shrink as `ZSTD_adjustCParams`
/// does (without a dictionary); an unknown size
/// takes the table for large inputs as it is. The size is known only when
/// the caller states it, so the parameters, and the output, never depend on
/// how the input is split.
///
/// With a dictionary, as for zstd's dictionary copied into the window
/// (`ZSTD_cpm_noAttachDict`): the table is that for the input and the
/// dictionary together, or for the dictionary and 499 bytes when the size is
/// unknown (`ZSTD_getCParamRowSize` adds 500 to the unknown size,
/// `UINT64_MAX`, which wraps around to the dictionary and 499); a known size shrinks the window to
/// hold both, and the tables to the dictionary and the window
/// (`ZSTD_dictAndWindowLog`).
fn params_for(level : Int32, size : Int64?, dict_size~ : Int32 = 0) -> Params {
  let dict = dict_size.to_int64()
  let row_size = match size {
    Some(size) => Some(size + dict)
    None if dict > 0 => Some(499L + dict)
    None => None
  }
  let table = match row_size {
    Some(rsize) =>
      (if rsize <= 256 * 1024 { 1 } else { 0 }) +
      (if rsize <= 128 * 1024 { 1 } else { 0 }) +
      (if rsize <= 16 * 1024 { 1 } else { 0 })
    None => 0
  }
  let params = level_row(table, level)
  guard size is Some(size) else { return params }
  // The smallest log whose power of 2 holds `size` and the dictionary, at
  // least 6 (the smallest hash log), as `ZSTD_adjustCParams_internal`
  // computes it; sizes above 2^30 are not resized.
  let window_log = if size <= 1L << 30 && dict <= 1L << 30 {
    let total = size + dict
    let size_log = if total < 64 { 6 } else { 64 - (total - 1).clz() }
    params.window_log.min(size_log)
  } else {
    params.window_log
  }
  // The tables' log: the window's, or one that holds the dictionary and the
  // window when the window does not hold the dictionary and the input
  // (`ZSTD_dictAndWindowLog`; 31 is zstd's largest window log).
  let table_log = if dict == 0 || 1L << window_log >= dict + size {
    window_log
  } else if dict + (1L << window_log) >= 1L << 31 {
    31
  } else {
    64 - (dict + (1L << window_log) - 1).clz()
  }
  let bt_scale = match params.strategy {
    Btlazy2 | Btopt => 1
    _ => 0
  }
  let cycle_log = params.chain_log - bt_scale
  // Reduce the tables BEFORE restoring the frame's minimum windowLog.
  // Otherwise tiny inputs retain tables sized for 1 KiB instead of 64 B.
  // Dictionary tagging is inapplicable, and the row-finder hash cap (28
  // or more) cannot reduce any of the level 1..12 rows (at most 23).
  {
    ..params,
    window_log: window_log.max(10),
    hash_log: params.hash_log.min(table_log + 1),
    chain_log: params.chain_log - (cycle_log - table_log).max(0),
  }
}

///|
/// Selects by the adjusted row's strategy, and for greedy, lazy and lazy2
/// whether to search rows (windows over 2^14 bytes). Tree rows retain every numeric
/// parameter and use Lazy2 because binary trees/optimal parsing are outside
/// the supported strategies. Adjustment precedes mapping so the reference
/// tree cycle bit still governs the table sizes.
fn encoder_params(
  level : Int32,
  size : Int64?,
  dict_size~ : Int32 = 0,
) -> Params {
  let params = params_for(level, size, dict_size~)
  match params.strategy {
    Btlazy2 | Btopt => { ..params, strategy: Lazy2, }
    // As ZSTD_resolveRowMatchFinderMode decides by default, from the
    // adjusted window. Tree rows keep hash chains: the reference searches
    // them harder than a row's at most 64 candidates.
    Greedy | Lazy | Lazy2 => { ..params, row_finder: params.window_log > 14, }
    _ => params
  }
}