mzstd 0.2.0

//! One block: match finding into a sequence store, then entropy coding
//! (`ZSTD_buildSeqStore`, `ZSTD_entropyCompressSeqStore` and
//! `ZSTD_compressBlock_internal`).

use super::cctx::Engine;
use super::double_fast;
use super::entropy::Tables;
use super::entropy::literals::{self, LiteralsSettings, min_gain};
use super::entropy::sequences;
use super::error::CoreError;
use super::fast;
use super::lazy;
use super::ldm;
use super::match_state::{BlockCompressor, BlockInput};
use super::mem;
use super::opt;
use super::params::{ParamSwitch, Strategy};
use super::seq_store::SeqStore;
use super::window::Segments;
use crate::Backend;
use crate::shared::format::{BLOCK_HEADER_SIZE, LONG_NB_SEQ};

/// Blocks shorter than this are stored without an attempt
/// (`MIN_CBLOCK_SIZE + ZSTD_blockHeaderSize + 1 + 1`).
const MIN_BLOCK_TO_COMPRESS: usize = 2 + BLOCK_HEADER_SIZE + 1 + 1;
/// `SUSPECT_UNCOMPRESSIBLE_LITERAL_RATIO`.
const SUSPECT_UNCOMPRESSIBLE_LITERAL_RATIO: usize = 20;
/// Upper bound on the size of a compressed block worth turning into RLE.
const RLE_MAX_LENGTH: usize = 25;

/// Outcome of match finding (`ZSTD_BuildSeqStore_e`).
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
pub(crate) enum Build {
    Compress,
    NoCompress,
}

/// The block compressor for a strategy and window shape
/// (`ZSTD_selectBlockCompressor`).
fn select_block_compressor(
    strategy: Strategy,
    row: bool,
    ext_dict: bool,
) -> Result<BlockCompressor, CoreError> {
    if row
        && matches!(
            strategy,
            Strategy::Greedy | Strategy::Lazy | Strategy::Lazy2
        )
    {
        return Ok(match (strategy, ext_dict) {
            (Strategy::Greedy, false) => lazy::greedy_row,
            (Strategy::Greedy, true) => lazy::greedy_row_ext,
            (Strategy::Lazy, false) => lazy::lazy_row,
            (Strategy::Lazy, true) => lazy::lazy_row_ext,
            (_, false) => lazy::lazy2_row,
            (_, true) => lazy::lazy2_row_ext,
        });
    }
    match (strategy, ext_dict) {
        (Strategy::Fast, false) => Ok(fast::compress_block),
        (Strategy::Fast, true) => Ok(fast::compress_block_ext_dict),
        (Strategy::DFast, false) => Ok(double_fast::compress_block),
        (Strategy::DFast, true) => Ok(double_fast::compress_block_ext_dict),
        (Strategy::Greedy, false) => Ok(lazy::greedy),
        (Strategy::Greedy, true) => Ok(lazy::greedy_ext),
        (Strategy::Lazy, false) => Ok(lazy::lazy),
        (Strategy::Lazy, true) => Ok(lazy::lazy_ext),
        (Strategy::Lazy2, false) => Ok(lazy::lazy2),
        (Strategy::Lazy2, true) => Ok(lazy::lazy2_ext),
        (Strategy::BtLazy2, false) => Ok(lazy::btlazy2),
        (Strategy::BtLazy2, true) => Ok(lazy::btlazy2_ext),
        (Strategy::BtOpt, false) => Ok(opt::btopt),
        (Strategy::BtOpt, true) => Ok(opt::btopt_ext),
        (Strategy::BtUltra, false) => Ok(opt::btultra),
        (Strategy::BtUltra, true) | (Strategy::BtUltra2, true) => Ok(opt::btultra_ext),
        (Strategy::BtUltra2, false) => Ok(opt::btultra2),
    }
}

/// Runs the match finder over `[start, end)` (`ZSTD_buildSeqStore`).
#[cfg_attr(all(feature = "hotpath", not(feature = "no_std")), hotpath::measure)]
pub(crate) fn build_seq_store(
    engine: &mut Engine,
    segments: &Segments<'_>,
    view: &mem::Window<'_>,
    start: u32,
    end: u32,
) -> Result<Build, CoreError> {
    let src_size = (end - start) as usize;
    if src_size < MIN_BLOCK_TO_COMPRESS {
        return Ok(Build::NoCompress);
    }
    engine.seq_store.reset();
    let ms = &mut engine.ms;
    ms.backend = engine.backend;
    ms.opt.literal_compression = engine.applied.literal_compression;

    // Limited update after a very long match.
    let curr = start;
    if curr > ms.next_to_update + 384 {
        ms.next_to_update = curr - 192.min(curr - ms.next_to_update - 384);
    }

    engine.next.rep = engine.prev.rep;
    let row = engine.applied.use_row_match_finder == ParamSwitch::Enable;
    let compressor = select_block_compressor(
        engine.applied.cparams.strategy,
        row,
        ms.window.has_ext_dict(),
    )?;
    let block = BlockInput {
        window: *view,
        start,
        end,
        backend: engine.backend,
    };
    let last_ll_size = if engine.applied.ldm.enable == ParamSwitch::Enable {
        let store = &mut engine.ldm_store;
        store.seq.clear();
        store.pos = 0;
        store.pos_in_sequence = 0;
        let block_addr = ms.window.base.add(i64::from(start));
        let ldm_start = engine.ldm.window.index_of(block_addr);
        let ldm_end = ldm_start + (end - start);
        engine.ldm.generate_sequences(
            segments,
            store,
            &engine.applied.ldm,
            ldm_start,
            ldm_end,
            engine.backend,
        );
        ldm::block_compress(
            store,
            ms,
            &mut engine.seq_store,
            &mut engine.next.rep,
            compressor,
            &block,
        )
    } else {
        compressor(ms, &mut engine.seq_store, &mut engine.next.rep, &block)
    };
    engine
        .seq_store
        .store_last_literals(view.prefix.slice(end - last_ll_size as u32, end));
    Ok(Build::Compress)
}

/// Writes the literals and sequences sections of `store`
/// (`ZSTD_entropyCompressSeqStore_internal`).
///
/// Returns `0` for the reference's "emit an uncompressed block instead".
#[cfg_attr(all(feature = "hotpath", not(feature = "no_std")), hotpath::measure)]
fn entropy_compress_internal(
    store: &mut SeqStore,
    prev: &Tables,
    next: &mut Tables,
    engine_params: &super::cctx::AppliedParams,
    dst: &mut [u8],
    backend: Backend,
) -> Result<usize, CoreError> {
    let strategy = engine_params.cparams.strategy;
    let nb_seq = store.nb_seq();
    let lit_size = store.literals.len();
    let suspect = nb_seq == 0 || lit_size / nb_seq >= SUSPECT_UNCOMPRESSIBLE_LITERAL_RATIO;
    let mut op = literals::compress(
        dst,
        &store.literals,
        &prev.huf,
        &mut next.huf,
        LiteralsSettings {
            strategy,
            disable_compression: engine_params.literals_compression_disabled(),
            suspect_uncompressible: suspect,
            backend,
        },
    )?;

    if dst.len() - op < 3 + 1 {
        return Err(CoreError::DstSizeTooSmall);
    }
    if nb_seq < 128 {
        dst[op] = nb_seq as u8;
        op += 1;
    } else if nb_seq < LONG_NB_SEQ {
        dst[op] = ((nb_seq >> 8) + 0x80) as u8;
        dst[op + 1] = nb_seq as u8;
        op += 2;
    } else {
        dst[op] = 0xFF;
        dst[op + 1..op + 3].copy_from_slice(&((nb_seq - LONG_NB_SEQ) as u16).to_le_bytes());
        op += 3;
    }
    if nb_seq == 0 {
        next.fse.clone_from(&prev.fse);
        return Ok(op);
    }
    let seq_head = op;
    op += 1;
    let stats =
        sequences::build_statistics(store, &prev.fse, &mut next.fse, &mut dst[op..], strategy)?;
    dst[seq_head] =
        ((stats.ll_type as u8) << 6) + ((stats.of_type as u8) << 4) + ((stats.ml_type as u8) << 2);
    op += stats.size;
    let bitstream_size = sequences::encode(&mut dst[op..], &next.fse, store, backend)?;
    op += bitstream_size;
    if stats.last_count_size != 0 && stats.last_count_size + bitstream_size < 4 {
        return Ok(0);
    }
    Ok(op)
}

/// Entropy-codes `store` and decides whether the result is worth keeping
/// (`ZSTD_entropyCompressSeqStore`).
///
/// Returns `0` when the block should be stored uncompressed.
pub(crate) fn entropy_compress(
    store: &mut SeqStore,
    prev: &Tables,
    next: &mut Tables,
    params: &super::cctx::AppliedParams,
    dst: &mut [u8],
    block_size: usize,
    backend: Backend,
) -> Result<usize, CoreError> {
    let capacity = dst.len();
    let c_size = match entropy_compress_internal(store, prev, next, params, dst, backend) {
        Ok(0) => return Ok(0),
        Err(CoreError::DstSizeTooSmall) if block_size <= capacity => return Ok(0),
        other => other?,
    };
    let max_c_size = block_size - min_gain(block_size, params.cparams.strategy);
    if c_size >= max_c_size {
        return Ok(0);
    }
    Ok(c_size)
}

/// Whether every byte of `src` is the same (`ZSTD_isRLE`).
pub(crate) fn is_rle(src: &[u8]) -> bool {
    src.iter().all(|&b| b == src[0])
}

/// Compresses one block body into `dst` (`ZSTD_compressBlock_internal`).
///
/// Returns `0` for "store uncompressed", `1` for an RLE block whose byte is
/// in `dst[0]`, and otherwise the compressed body size.
#[cfg_attr(all(feature = "hotpath", not(feature = "no_std")), hotpath::measure)]
pub(crate) fn compress_block_internal(
    engine: &mut Engine,
    segments: &Segments<'_>,
    view: &mem::Window<'_>,
    start: u32,
    end: u32,
    dst: &mut [u8],
    frame: bool,
) -> Result<usize, CoreError> {
    let src = view.prefix.slice(start, end);
    let c_size = match build_seq_store(engine, segments, view, start, end)? {
        Build::NoCompress => 0,
        Build::Compress => {
            let params = engine.applied;
            let mut c_size = entropy_compress(
                &mut engine.seq_store,
                &engine.prev.entropy,
                &mut engine.next.entropy,
                &params,
                dst,
                src.len(),
                engine.backend,
            )?;
            if frame && !engine.is_first_block && c_size < RLE_MAX_LENGTH && is_rle(src) {
                c_size = 1;
                dst[0] = src[0];
            }
            c_size
        }
    };
    if c_size > 1 {
        engine.confirm_block_state();
    }
    engine.demote_offcode_repeat();
    Ok(c_size)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn rle_detection() {
        assert!(is_rle(&[3]));
        assert!(is_rle(&[3; 100]));
        assert!(!is_rle(&[3, 3, 4]));
    }
}