simd_brotli/enc/backward_references/

mod.rs

mod benchmark;
pub mod hash_to_binary_tree;
pub mod hq;
mod tagged;
mod test;

use core::cmp::{max, min};

use super::super::alloc::{Allocator, SliceWrapper, SliceWrapperMut};
use super::command::{BrotliDistanceParams, Command, ComputeDistanceCode};
use super::dictionary_hash::kStaticDictionaryHash;
use super::hash_to_binary_tree::{H10, H10Buckets, H10DefaultParams, ZopfliNode};
use super::static_dict::{
    BROTLI_UNALIGNED_LOAD32, BROTLI_UNALIGNED_LOAD64, BrotliDictionary, FindMatchLengthWithLimit,
    FindMatchLengthWithLimitMin4,
};
use super::util::{Log2FloorNonZero, floatX};
use crate::enc::combined_alloc::allocate;
use crate::enc::vectorization::detect_level;

pub use tagged::{H58Sub, H68Sub, TaggedHasher, TaggedHasherSimd};

pub static kInvalidMatch: u32 = 0x0fff_ffff;
static kCutoffTransformsCount: u32 = 10;
static kCutoffTransforms: u64 = 0x071b_520a_da2d_3200;
pub static kHashMul32: u32 = 0x1e35_a7bd;
pub static kHashMul64: u64 = 0x1e35_a7bd_1e35_a7bd;
pub static kHashMul64Long: u64 = 0x1fe3_5a7b_d357_9bd3;

#[derive(PartialEq, Eq, Copy, Clone, Debug)]
#[repr(C)]
pub enum BrotliEncoderMode {
    BROTLI_MODE_GENERIC = 0,
    BROTLI_MODE_TEXT = 1,
    BROTLI_MODE_FONT = 2,
    BROTLI_FORCE_LSB_PRIOR = 3,
    BROTLI_FORCE_MSB_PRIOR = 4,
    BROTLI_FORCE_UTF8_PRIOR = 5,
    BROTLI_FORCE_SIGNED_PRIOR = 6,
}

/// This code takes a length and checks if there's an "end of dictionary" marker at the
///  "ring_buffer_break"point. This marks where a backwards reference cannot pull data through.
/// A match must stop at the end of the dictionary and cannot span the end of the dictionary
/// and beginning of the file.  ring_buffer_break is only set true for custom LZ77 dictionary.
fn fix_unbroken_len(
    unbroken_len: usize,
    prev_ix: usize,
    _cur_ix_masked: usize,
    ring_buffer_break: Option<core::num::NonZeroUsize>,
) -> usize {
    if let Some(br) = ring_buffer_break {
        if prev_ix < usize::from(br) && prev_ix + unbroken_len > usize::from(br) {
            return usize::from(br) - prev_ix;
        }
    }
    return unbroken_len;
}
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct BrotliHasherParams {
    /// type of hasher to use (default: type 6, but others have tradeoffs of speed/memory)
    pub type_: i32,
    /// number of the number of buckets to have in the hash table (defaults to quality - 1)
    pub bucket_bits: i32,
    /// number of potential matches to hold per bucket (hash collisions)
    pub block_bits: i32,
    /// number of bytes of a potential match to hash
    pub hash_len: i32,
    /// number of previous distance matches to check for future matches (defaults to 16)
    pub num_last_distances_to_check: i32,
    /// how much to weigh distance vs an extra byte of copy match when comparing possible copy srcs
    pub literal_byte_score: i32,
}

#[derive(Clone, Debug)]
pub struct BrotliEncoderParams {
    pub dist: BrotliDistanceParams,
    /// if this brotli file is generic, font or specifically text
    pub mode: BrotliEncoderMode,
    /// quality param between 0 and 11 (11 is smallest but takes longest to encode)
    pub quality: i32,
    pub q9_5: bool,
    /// log of how big the ring buffer should be for copying prior data
    pub lgwin: i32,
    /// log of how often metablocks should be serialized
    pub lgblock: i32,
    /// how big the source file is (or 0 if no hint is provided)
    pub size_hint: usize,
    // FIXME: this should be bool
    /// avoid serializing out priors for literal sections in the favor of decode speed
    pub disable_literal_context_modeling: i32,
    pub hasher: BrotliHasherParams,
    /// produce an IR of the compression file
    pub log_meta_block: bool,
    /// attempt to detect how many bytes before the current byte generates the best prediction of it
    /// * 0 = off (stride 1 always)
    /// * 1 = on per 16th of a file
    /// * 2 = on per block type switch
    pub stride_detection_quality: u8,
    /// if nonzero, will search for high entropy strings and log them differently to the IR
    pub high_entropy_detection_quality: u8,
    /// if nonzero it will search for the temporal locality and effectiveness of the priors
    /// for literals. The best adaptation and forgetfulness will be logged per metablock to the IR
    pub cdf_adaptation_detection: u8,
    /// whether to search for whether the previous byte or the context_map are better predictors on a per-context-map basis
    pub prior_bitmask_detection: u8,
    /// for prior bitmask detection: stride_low, stride_speed, cm_low, cm_speed
    pub literal_adaptation: [(u16, u16); 4],
    pub large_window: bool,
    /// avoid search for the best ndirect vs npostfix parameters for distance
    pub avoid_distance_prefix_search: bool,
    /// inserts an extra empty metadata block before the final empty metablock in
    /// catable/appendable mode so concatination tools can just remove the last byte
    pub byte_align: bool,
    /// do not emit a empty last block at end of data - if not appendable, this
    /// will also supress the stream header
    pub bare_stream: bool,
    /// construct brotli in such a way that it may be concatenated with another brotli file using appropriate bit ops
    pub catable: bool,
    /// can use the dictionary (default yes unless catable is set)
    pub use_dictionary: bool,
    /// construct brotli in such a way that another concatable brotli file may be appended
    pub appendable: bool,
    /// include a magic number and version number and size_hint at the beginning
    pub magic_number: bool,
    /// prefer to compute the map of previously seen strings
    /// just once for all the threads at the beginning, since they overlap significantly
    pub favor_cpu_efficiency: bool,
}

impl Default for BrotliEncoderParams {
    fn default() -> BrotliEncoderParams {
        super::encode::BrotliEncoderInitParams()
    }
}

#[derive(Clone, Copy, Default, PartialEq)]
pub struct H9Opts {
    pub literal_byte_score: u32,
}
pub enum HowPrepared {
    ALREADY_PREPARED,
    NEWLY_PREPARED,
}
#[derive(Clone, PartialEq)]
pub struct Struct1 {
    pub params: BrotliHasherParams,
    /// FIXME: this should be bool
    pub is_prepared_: i32,
    pub dict_num_lookups: usize,
    pub dict_num_matches: usize,
}

fn LiteralSpreeLengthForSparseSearch(params: &BrotliEncoderParams) -> usize {
    (if params.quality < 9 { 64i32 } else { 512i32 }) as usize
}

pub struct HasherSearchResult {
    pub len: usize,
    pub len_x_code: usize,
    pub distance: usize,
    pub score: u64,
}

pub trait CloneWithAlloc<Alloc: alloc::Allocator<u16> + alloc::Allocator<u32>> {
    fn clone_with_alloc(&self, m: &mut Alloc) -> Self;
}

pub trait AnyHasher {
    fn Opts(&self) -> H9Opts;
    fn GetHasherCommon(&mut self) -> &mut Struct1;
    fn HashBytes(&self, data: &[u8]) -> usize;
    fn HashTypeLength(&self) -> usize;
    fn StoreLookahead(&self) -> usize;
    fn PrepareDistanceCache(&self, distance_cache: &mut [i32]);
    fn FindLongestMatch(
        &mut self,
        dictionary: Option<&BrotliDictionary>,
        dictionary_hash: &[u16],
        data: &[u8],
        ring_buffer_mask: usize,
        ring_buffer_break: Option<core::num::NonZeroUsize>,
        distance_cache: &[i32],
        cur_ix: usize,
        max_length: usize,
        max_backward: usize,
        gap: usize,
        max_distance: usize,
        out: &mut HasherSearchResult,
    ) -> bool;
    fn Store(&mut self, data: &[u8], mask: usize, ix: usize);
    fn Store4Vec4(&mut self, data: &[u8], mask: usize, ix: usize) {
        for i in 0..4 {
            self.Store(data, mask, ix + i * 4);
        }
    }
    fn StoreEvenVec4(&mut self, data: &[u8], mask: usize, ix: usize) {
        for i in 0..4 {
            self.Store(data, mask, ix + i * 2);
        }
    }
    fn StoreRange(&mut self, data: &[u8], mask: usize, ix_start: usize, ix_end: usize);
    fn BulkStoreRange(&mut self, data: &[u8], mask: usize, ix_start: usize, ix_end: usize);
    fn Prepare(&mut self, one_shot: bool, input_size: usize, data: &[u8]) -> HowPrepared;
    fn StitchToPreviousBlock(
        &mut self,
        num_bytes: usize,
        position: usize,
        ringbuffer: &[u8],
        ringbuffer_mask: usize,
    );
}

pub fn StitchToPreviousBlockInternal<T: AnyHasher>(
    handle: &mut T,
    num_bytes: usize,
    position: usize,
    ringbuffer: &[u8],
    ringbuffer_mask: usize,
) {
    if num_bytes >= handle.HashTypeLength().wrapping_sub(1) && (position >= 3) {
        handle.Store(ringbuffer, ringbuffer_mask, position.wrapping_sub(3));
        handle.Store(ringbuffer, ringbuffer_mask, position.wrapping_sub(2));
        handle.Store(ringbuffer, ringbuffer_mask, position.wrapping_sub(1));
    }
}

pub fn StoreLookaheadThenStore<T: AnyHasher>(hasher: &mut T, size: usize, dict: &[u8]) {
    let overlap = hasher.StoreLookahead().wrapping_sub(1);
    if size > overlap {
        hasher.BulkStoreRange(dict, usize::MAX, 0, size - overlap);
    }
}

pub trait BasicHashComputer {
    fn HashBytes(&self, data: &[u8]) -> u32;
    fn BUCKET_BITS(&self) -> i32;
    fn USE_DICTIONARY(&self) -> i32;
    fn BUCKET_SWEEP(&self) -> i32;
}
pub struct BasicHasher<Buckets: SliceWrapperMut<u32> + SliceWrapper<u32> + BasicHashComputer> {
    pub GetHasherCommon: Struct1,
    pub buckets_: Buckets,
    pub h9_opts: H9Opts,
}

impl<A: SliceWrapperMut<u32> + SliceWrapper<u32> + BasicHashComputer> PartialEq<BasicHasher<A>>
    for BasicHasher<A>
{
    fn eq(&self, other: &BasicHasher<A>) -> bool {
        self.GetHasherCommon == other.GetHasherCommon
            && self.h9_opts == other.h9_opts
            && self.buckets_.slice() == other.buckets_.slice()
    }
}

impl<T: SliceWrapperMut<u32> + SliceWrapper<u32> + BasicHashComputer> BasicHasher<T> {
    fn StoreRangeOptBasic(
        &mut self,
        data: &[u8],
        mask: usize,
        ix_start: usize,
        ix_end: usize,
    ) -> usize {
        let lookahead = 8;
        if ix_end >= ix_start + lookahead * 2 {
            let chunk_count = (ix_end - ix_start) / 4;
            for chunk_id in 0..chunk_count {
                let i = (ix_start + chunk_id * 4) & mask;
                let word11 = data.split_at(i).1.split_at(11).0;
                let mixed0 = self.HashBytes(word11);
                let mixed1 = self.HashBytes(word11.split_at(1).1);
                let mixed2 = self.HashBytes(word11.split_at(2).1);
                let mixed3 = self.HashBytes(word11.split_at(3).1);
                let off: u32 = (i >> 3).wrapping_rem(self.buckets_.BUCKET_SWEEP() as usize) as u32;
                let offset0: usize = mixed0 + off as usize;
                let offset1: usize = mixed1 + off as usize;
                let offset2: usize = mixed2 + off as usize;
                let offset3: usize = mixed3 + off as usize;
                self.buckets_.slice_mut()[offset0] = i as u32;
                self.buckets_.slice_mut()[offset1] = i as u32 + 1;
                self.buckets_.slice_mut()[offset2] = i as u32 + 2;
                self.buckets_.slice_mut()[offset3] = i as u32 + 3;
            }
            return ix_start + chunk_count * 4;
        }
        ix_start
    }
}
pub struct H2Sub<AllocU32: alloc::Allocator<u32>> {
    pub buckets_: AllocU32::AllocatedMemory, // 65537
}
impl<T: SliceWrapperMut<u32> + SliceWrapper<u32> + BasicHashComputer> AnyHasher for BasicHasher<T> {
    #[inline(always)]
    fn Opts(&self) -> H9Opts {
        self.h9_opts
    }
    #[allow(unused_variables)]
    fn PrepareDistanceCache(&self, distance_cache: &mut [i32]) {}
    #[inline(always)]
    fn HashTypeLength(&self) -> usize {
        8
    }
    #[inline(always)]
    fn StoreLookahead(&self) -> usize {
        8
    }
    fn StitchToPreviousBlock(
        &mut self,
        num_bytes: usize,
        position: usize,
        ringbuffer: &[u8],
        ringbuffer_mask: usize,
    ) {
        StitchToPreviousBlockInternal(self, num_bytes, position, ringbuffer, ringbuffer_mask);
    }
    #[inline(always)]
    fn GetHasherCommon(&mut self) -> &mut Struct1 {
        &mut self.GetHasherCommon
    }
    #[inline(always)]
    fn HashBytes(&self, data: &[u8]) -> usize {
        self.buckets_.HashBytes(data) as usize
    }
    fn Store(&mut self, data: &[u8], mask: usize, ix: usize) {
        let (_, data_window) = data.split_at((ix & mask));
        let key: u32 = self.HashBytes(data_window) as u32;
        let off: u32 = (ix >> 3).wrapping_rem(self.buckets_.BUCKET_SWEEP() as usize) as u32;
        self.buckets_.slice_mut()[key.wrapping_add(off) as usize] = ix as u32;
    }
    fn StoreRange(&mut self, data: &[u8], mask: usize, ix_start: usize, ix_end: usize) {
        for i in self.StoreRangeOptBasic(data, mask, ix_start, ix_end)..ix_end {
            self.Store(data, mask, i);
        }
    }
    fn BulkStoreRange(&mut self, data: &[u8], mask: usize, ix_start: usize, ix_end: usize) {
        self.StoreRange(data, mask, ix_start, ix_end);
    }
    fn Prepare(&mut self, one_shot: bool, input_size: usize, data: &[u8]) -> HowPrepared {
        if self.GetHasherCommon.is_prepared_ != 0 {
            return HowPrepared::ALREADY_PREPARED;
        }
        let partial_prepare_threshold = (4 << self.buckets_.BUCKET_BITS()) >> 7;
        if one_shot && input_size <= partial_prepare_threshold {
            for i in 0..input_size {
                let key = self.HashBytes(&data[i..]);
                let bs = self.buckets_.BUCKET_SWEEP() as usize;
                for item in self.buckets_.slice_mut()[key..(key + bs)].iter_mut() {
                    *item = 0;
                }
            }
        } else {
            for item in self.buckets_.slice_mut().iter_mut() {
                *item = 0;
            }
        }
        self.GetHasherCommon.is_prepared_ = 1;
        HowPrepared::NEWLY_PREPARED
    }

    fn FindLongestMatch(
        &mut self,
        dictionary: Option<&BrotliDictionary>,
        dictionary_hash: &[u16],
        data: &[u8],
        ring_buffer_mask: usize,
        ring_buffer_break: Option<core::num::NonZeroUsize>,
        distance_cache: &[i32],
        cur_ix: usize,
        max_length: usize,
        max_backward: usize,
        gap: usize,
        max_distance: usize,
        out: &mut HasherSearchResult,
    ) -> bool {
        let opts = self.Opts();
        let best_len_in: usize = out.len;
        let cur_ix_masked: usize = cur_ix & ring_buffer_mask;
        let key: u32 = self.HashBytes(&data[cur_ix_masked..]) as u32;
        let mut compare_char: i32 = data[cur_ix_masked.wrapping_add(best_len_in)] as i32;
        let mut best_score: u64 = out.score;
        let mut best_len: usize = best_len_in;
        let cached_backward: usize = distance_cache[0] as usize;
        let mut prev_ix: usize = cur_ix.wrapping_sub(cached_backward);
        let mut is_match_found = false;
        out.len_x_code = 0usize;
        if prev_ix < cur_ix {
            prev_ix &= ring_buffer_mask as u32 as usize;
            if compare_char == data[prev_ix.wrapping_add(best_len)] as i32 {
                let unbroken_len: usize = FindMatchLengthWithLimitMin4(
                    &data[prev_ix..],
                    &data[cur_ix_masked..],
                    max_length,
                );
                if unbroken_len != 0 {
                    let len =
                        fix_unbroken_len(unbroken_len, prev_ix, cur_ix_masked, ring_buffer_break);
                    best_score = BackwardReferenceScoreUsingLastDistance(len, opts);
                    best_len = len;
                    out.len = len;
                    out.distance = cached_backward;
                    out.score = best_score;
                    compare_char = data[cur_ix_masked.wrapping_add(best_len)] as i32;
                    if self.buckets_.BUCKET_SWEEP() == 1i32 {
                        self.buckets_.slice_mut()[key as usize] = cur_ix as u32;
                        return true;
                    } else {
                        is_match_found = true;
                    }
                }
            }
        }
        let bucket_sweep = self.buckets_.BUCKET_SWEEP();
        if bucket_sweep == 1i32 {
            prev_ix = self.buckets_.slice()[key as usize] as usize;
            self.buckets_.slice_mut()[key as usize] = cur_ix as u32;
            let backward: usize = cur_ix.wrapping_sub(prev_ix);
            prev_ix &= ring_buffer_mask as u32 as usize;
            if compare_char != data[prev_ix.wrapping_add(best_len_in)] as i32 {
                return false;
            }
            if backward == 0usize || backward > max_backward {
                return false;
            }
            let unbroken_len: usize =
                FindMatchLengthWithLimitMin4(&data[prev_ix..], &data[cur_ix_masked..], max_length);
            if unbroken_len != 0 {
                let len = fix_unbroken_len(unbroken_len, prev_ix, cur_ix_masked, ring_buffer_break);
                out.len = len;
                out.distance = backward;
                out.score = BackwardReferenceScore(len, backward, opts);
                return true;
            }
        } else {
            for prev_ix_ref in
                self.buckets_.slice().split_at(key as usize).1[..bucket_sweep as usize].iter()
            {
                let mut prev_ix = *prev_ix_ref as usize;
                let backward: usize = cur_ix.wrapping_sub(prev_ix);
                prev_ix &= ring_buffer_mask as u32 as usize;
                if compare_char != data[prev_ix.wrapping_add(best_len)] as i32 {
                    continue;
                }
                if backward == 0usize || backward > max_backward {
                    continue;
                }
                let unbroken_len = FindMatchLengthWithLimitMin4(
                    &data[prev_ix..],
                    &data[cur_ix_masked..],
                    max_length,
                );

                if unbroken_len != 0 {
                    let len =
                        fix_unbroken_len(unbroken_len, prev_ix, cur_ix_masked, ring_buffer_break);
                    let score: u64 = BackwardReferenceScore(len, backward, opts);
                    if best_score < score {
                        best_score = score;
                        best_len = len;
                        out.len = best_len;
                        out.distance = backward;
                        out.score = score;
                        compare_char = data[cur_ix_masked.wrapping_add(best_len)] as i32;
                        is_match_found = true;
                    }
                }
            }
        }
        if dictionary.is_some() && self.buckets_.USE_DICTIONARY() != 0 && !is_match_found {
            is_match_found = SearchInStaticDictionary(
                dictionary.unwrap(),
                dictionary_hash,
                self,
                &data[cur_ix_masked..],
                max_length,
                max_backward.wrapping_add(gap),
                max_distance,
                out,
                true,
            );
        }
        self.buckets_.slice_mut()
            [(key as usize).wrapping_add((cur_ix >> 3).wrapping_rem(bucket_sweep as usize))] =
            cur_ix as u32;
        is_match_found
    }
}
impl<AllocU32: alloc::Allocator<u32>> BasicHashComputer for H2Sub<AllocU32> {
    fn HashBytes(&self, data: &[u8]) -> u32 {
        let h: u64 =
            (BROTLI_UNALIGNED_LOAD64(data) << (64i32 - 8i32 * 5i32)).wrapping_mul(kHashMul64);
        (h >> (64i32 - 16i32)) as u32
    }
    fn BUCKET_BITS(&self) -> i32 {
        16
    }
    fn BUCKET_SWEEP(&self) -> i32 {
        1
    }
    fn USE_DICTIONARY(&self) -> i32 {
        1
    }
}
impl<AllocU32: alloc::Allocator<u32>> SliceWrapperMut<u32> for H2Sub<AllocU32> {
    fn slice_mut(&mut self) -> &mut [u32] {
        return self.buckets_.slice_mut();
    }
}
impl<AllocU32: alloc::Allocator<u32>> SliceWrapper<u32> for H2Sub<AllocU32> {
    fn slice(&self) -> &[u32] {
        return self.buckets_.slice();
    }
}
pub struct H3Sub<AllocU32: alloc::Allocator<u32>> {
    pub buckets_: AllocU32::AllocatedMemory, // 65538
}
impl<AllocU32: alloc::Allocator<u32>> SliceWrapperMut<u32> for H3Sub<AllocU32> {
    fn slice_mut(&mut self) -> &mut [u32] {
        return self.buckets_.slice_mut();
    }
}
impl<AllocU32: alloc::Allocator<u32>> SliceWrapper<u32> for H3Sub<AllocU32> {
    fn slice(&self) -> &[u32] {
        return self.buckets_.slice();
    }
}
impl<AllocU32: alloc::Allocator<u32>> BasicHashComputer for H3Sub<AllocU32> {
    fn BUCKET_BITS(&self) -> i32 {
        16
    }
    fn BUCKET_SWEEP(&self) -> i32 {
        2
    }
    fn USE_DICTIONARY(&self) -> i32 {
        0
    }
    fn HashBytes(&self, data: &[u8]) -> u32 {
        let h: u64 =
            (BROTLI_UNALIGNED_LOAD64(data) << (64i32 - 8i32 * 5i32)).wrapping_mul(kHashMul64);
        (h >> (64i32 - 16i32)) as u32
    }
}
pub struct H4Sub<AllocU32: alloc::Allocator<u32>> {
    pub buckets_: AllocU32::AllocatedMemory, // 131076
}
impl<AllocU32: alloc::Allocator<u32>> BasicHashComputer for H4Sub<AllocU32> {
    fn BUCKET_BITS(&self) -> i32 {
        17
    }
    fn BUCKET_SWEEP(&self) -> i32 {
        4
    }
    fn USE_DICTIONARY(&self) -> i32 {
        1
    }
    fn HashBytes(&self, data: &[u8]) -> u32 {
        let h: u64 =
            (BROTLI_UNALIGNED_LOAD64(data) << (64i32 - 8i32 * 5i32)).wrapping_mul(kHashMul64);
        (h >> (64i32 - 17i32)) as u32
    }
}
impl<AllocU32: alloc::Allocator<u32>> SliceWrapperMut<u32> for H4Sub<AllocU32> {
    fn slice_mut(&mut self) -> &mut [u32] {
        return self.buckets_.slice_mut();
    }
}
impl<AllocU32: alloc::Allocator<u32>> SliceWrapper<u32> for H4Sub<AllocU32> {
    fn slice(&self) -> &[u32] {
        return self.buckets_.slice();
    }
}
pub struct H54Sub<AllocU32: alloc::Allocator<u32>> {
    pub buckets_: AllocU32::AllocatedMemory,
}
impl<AllocU32: alloc::Allocator<u32>> BasicHashComputer for H54Sub<AllocU32> {
    fn BUCKET_BITS(&self) -> i32 {
        20
    }
    fn BUCKET_SWEEP(&self) -> i32 {
        4
    }
    fn USE_DICTIONARY(&self) -> i32 {
        0
    }
    fn HashBytes(&self, data: &[u8]) -> u32 {
        let h: u64 =
            (BROTLI_UNALIGNED_LOAD64(data) << (64i32 - 8i32 * 7i32)).wrapping_mul(kHashMul64);
        (h >> (64i32 - 20i32)) as u32
    }
}

impl<AllocU32: alloc::Allocator<u32>> SliceWrapperMut<u32> for H54Sub<AllocU32> {
    fn slice_mut(&mut self) -> &mut [u32] {
        return self.buckets_.slice_mut();
    }
}
impl<AllocU32: alloc::Allocator<u32>> SliceWrapper<u32> for H54Sub<AllocU32> {
    fn slice(&self) -> &[u32] {
        return self.buckets_.slice();
    }
}
pub const H9_BUCKET_BITS: usize = 15;
pub const H9_BLOCK_BITS: usize = 8;
pub const H9_NUM_LAST_DISTANCES_TO_CHECK: usize = 16;
pub const H9_BLOCK_SIZE: usize = 1 << H9_BLOCK_BITS;
const H9_BLOCK_MASK: usize = (1 << H9_BLOCK_BITS) - 1;

impl H9Opts {
    pub fn new(params: &BrotliHasherParams) -> H9Opts {
        H9Opts {
            literal_byte_score: if params.literal_byte_score != 0 {
                params.literal_byte_score as u32
            } else {
                540
            },
        }
    }
}

pub struct H9<Alloc: alloc::Allocator<u16> + alloc::Allocator<u32>> {
    pub num_: <Alloc as Allocator<u16>>::AllocatedMemory, //[u16;1 << H9_BUCKET_BITS],
    pub buckets_: <Alloc as Allocator<u32>>::AllocatedMemory, //[u32; H9_BLOCK_SIZE << H9_BUCKET_BITS],
    pub dict_search_stats_: Struct1,
    pub h9_opts: H9Opts,
}

impl<Alloc: alloc::Allocator<u16> + alloc::Allocator<u32>> PartialEq<H9<Alloc>> for H9<Alloc> {
    fn eq(&self, other: &H9<Alloc>) -> bool {
        self.dict_search_stats_ == other.dict_search_stats_
            && self.num_.slice() == other.num_.slice()
            && self.buckets_.slice() == other.buckets_.slice()
            && self.h9_opts == other.h9_opts
    }
}

fn adv_prepare_distance_cache(distance_cache: &mut [i32], num_distances: i32) {
    if num_distances > 4i32 {
        let last_distance: i32 = distance_cache[0];
        distance_cache[4] = last_distance - 1i32;
        distance_cache[5] = last_distance + 1i32;
        distance_cache[6] = last_distance - 2i32;
        distance_cache[7] = last_distance + 2i32;
        distance_cache[8] = last_distance - 3i32;
        distance_cache[9] = last_distance + 3i32;
        if num_distances > 10i32 {
            let next_last_distance: i32 = distance_cache[1];
            distance_cache[10] = next_last_distance - 1i32;
            distance_cache[11] = next_last_distance + 1i32;
            distance_cache[12] = next_last_distance - 2i32;
            distance_cache[13] = next_last_distance + 2i32;
            distance_cache[14] = next_last_distance - 3i32;
            distance_cache[15] = next_last_distance + 3i32;
        }
    }
}

pub const kDistanceCacheIndex: [u8; 16] = [0, 1, 2, 3, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1];

pub const kDistanceCacheOffset: [i8; 16] = [0, 0, 0, 0, -1, 1, -2, 2, -3, 3, -1, 1, -2, 2, -3, 3];

//const BROTLI_LITERAL_BYTE_SCORE: u64 = 540;
const BROTLI_DISTANCE_BIT_PENALTY: u32 = 120;

// Score must be positive after applying maximal penalty.
const BROTLI_SCORE_BASE: u32 = (BROTLI_DISTANCE_BIT_PENALTY * 8 * 8/* sizeof usize*/);
const kDistanceShortCodeCost: [u32; 16] = [
    /* Repeat last */
    BROTLI_SCORE_BASE + 60,
    /* 2nd, 3rd, 4th last */
    BROTLI_SCORE_BASE - 95,
    BROTLI_SCORE_BASE - 117,
    BROTLI_SCORE_BASE - 127,
    /* Last with offset */
    BROTLI_SCORE_BASE - 93,
    BROTLI_SCORE_BASE - 93,
    BROTLI_SCORE_BASE - 96,
    BROTLI_SCORE_BASE - 96,
    BROTLI_SCORE_BASE - 99,
    BROTLI_SCORE_BASE - 99,
    /* 2nd last with offset */
    BROTLI_SCORE_BASE - 105,
    BROTLI_SCORE_BASE - 105,
    BROTLI_SCORE_BASE - 115,
    BROTLI_SCORE_BASE - 115,
    BROTLI_SCORE_BASE - 125,
    BROTLI_SCORE_BASE - 125,
];

fn BackwardReferenceScoreH9(
    copy_length: usize,
    backward_reference_offset: usize,
    h9_opts: H9Opts,
) -> u64 {
    (u64::from(BROTLI_SCORE_BASE)
        .wrapping_add((h9_opts.literal_byte_score as u64).wrapping_mul(copy_length as u64))
        .wrapping_sub(
            (BROTLI_DISTANCE_BIT_PENALTY as u64)
                .wrapping_mul(Log2FloorNonZero(backward_reference_offset as u64) as u64),
        ))
        >> 2
}

fn BackwardReferenceScoreUsingLastDistanceH9(
    copy_length: usize,
    distance_short_code: usize,
    h9_opts: H9Opts,
) -> u64 {
    ((h9_opts.literal_byte_score as u64)
        .wrapping_mul(copy_length as u64)
        .wrapping_add(u64::from(kDistanceShortCodeCost[distance_short_code])))
        >> 2
}

impl<Alloc: alloc::Allocator<u16> + alloc::Allocator<u32>> AnyHasher for H9<Alloc> {
    #[inline(always)]
    fn Opts(&self) -> H9Opts {
        self.h9_opts
    }
    #[inline(always)]
    fn GetHasherCommon(&mut self) -> &mut Struct1 {
        &mut self.dict_search_stats_
    }
    #[inline(always)]
    fn HashBytes(&self, data: &[u8]) -> usize {
        let h: u32 = BROTLI_UNALIGNED_LOAD32(data).wrapping_mul(kHashMul32);
        let thirty_two: usize = 32;
        (h >> (thirty_two.wrapping_sub(H9_BUCKET_BITS))) as usize
    }
    #[inline(always)]
    fn HashTypeLength(&self) -> usize {
        4
    }
    #[inline(always)]
    fn StoreLookahead(&self) -> usize {
        4
    }
    fn PrepareDistanceCache(&self, distance_cache: &mut [i32]) {
        let num_distances = H9_NUM_LAST_DISTANCES_TO_CHECK as i32;
        adv_prepare_distance_cache(distance_cache, num_distances);
    }
    fn FindLongestMatch(
        &mut self,
        dictionary: Option<&BrotliDictionary>,
        dictionary_hash: &[u16],
        data: &[u8],
        ring_buffer_mask: usize,
        ring_buffer_break: Option<core::num::NonZeroUsize>,
        distance_cache: &[i32],
        cur_ix: usize,
        max_length: usize,
        max_backward: usize,
        gap: usize,
        max_distance: usize,
        out: &mut HasherSearchResult,
    ) -> bool {
        let best_len_in: usize = out.len;
        let cur_ix_masked: usize = cur_ix & ring_buffer_mask;
        let mut best_score: u64 = out.score;
        let mut best_len: usize = best_len_in;
        let mut is_match_found = false;
        out.len_x_code = 0usize;
        for i in 0..H9_NUM_LAST_DISTANCES_TO_CHECK {
            let idx = kDistanceCacheIndex[i] as usize;
            let backward =
                (distance_cache[idx] as usize).wrapping_add(kDistanceCacheOffset[i] as usize);
            let mut prev_ix = cur_ix.wrapping_sub(backward);
            if prev_ix >= cur_ix {
                continue;
            }
            if backward > max_backward {
                continue;
            }
            prev_ix &= ring_buffer_mask;
            if cur_ix_masked.wrapping_add(best_len) > ring_buffer_mask
                || prev_ix.wrapping_add(best_len) > ring_buffer_mask
                || data[cur_ix_masked.wrapping_add(best_len)]
                    != data[prev_ix.wrapping_add(best_len)]
            {
                continue;
            }
            {
                let unbroken_len: usize =
                    FindMatchLengthWithLimit(&data[prev_ix..], &data[cur_ix_masked..], max_length);
                if unbroken_len >= 3 || (unbroken_len == 2 && i < 2) {
                    let len =
                        fix_unbroken_len(unbroken_len, prev_ix, cur_ix_masked, ring_buffer_break);
                    let score = BackwardReferenceScoreUsingLastDistanceH9(len, i, self.h9_opts);
                    if best_score < score {
                        best_score = score;
                        best_len = len;
                        out.len = best_len;
                        out.distance = backward;
                        out.score = best_score;
                        is_match_found = true;
                    }
                }
            }
        }
        if max_length >= 4 && cur_ix_masked.wrapping_add(best_len) <= ring_buffer_mask {
            let key = self.HashBytes(data.split_at(cur_ix_masked).1);
            let bucket = &mut self
                .buckets_
                .slice_mut()
                .split_at_mut(key << H9_BLOCK_BITS)
                .1
                .split_at_mut(H9_BLOCK_SIZE)
                .0;
            assert!(bucket.len() > H9_BLOCK_MASK);
            assert_eq!(bucket.len(), H9_BLOCK_MASK + 1);
            let self_num_key = &mut self.num_.slice_mut()[key];
            let down = if *self_num_key > H9_BLOCK_SIZE as u16 {
                (*self_num_key as usize) - H9_BLOCK_SIZE
            } else {
                0usize
            };
            let mut i: usize = *self_num_key as usize;
            let mut prev_best_val = data[cur_ix_masked.wrapping_add(best_len)];
            while i > down {
                i -= 1;
                let mut prev_ix = bucket[i & H9_BLOCK_MASK] as usize;
                let backward = cur_ix.wrapping_sub(prev_ix);
                if (backward > max_backward) {
                    break;
                }
                prev_ix &= ring_buffer_mask;
                if (prev_ix.wrapping_add(best_len) > ring_buffer_mask
                    || prev_best_val != data[prev_ix.wrapping_add(best_len)])
                {
                    continue;
                }
                {
                    let unbroken_len = FindMatchLengthWithLimit(
                        data.split_at(prev_ix).1,
                        data.split_at(cur_ix_masked).1,
                        max_length,
                    );
                    if (unbroken_len >= 4) {
                        let len = fix_unbroken_len(
                            unbroken_len,
                            prev_ix,
                            cur_ix_masked,
                            ring_buffer_break,
                        );
                        /* Comparing for >= 3 does not change the semantics, but just saves
                        for a few unnecessary binary logarithms in backward reference
                        score, since we are not interested in such short matches. */
                        let score = BackwardReferenceScoreH9(len, backward, self.h9_opts);
                        if (best_score < score) {
                            best_score = score;
                            best_len = len;
                            out.len = best_len;
                            out.distance = backward;
                            out.score = best_score;
                            is_match_found = true;
                            if cur_ix_masked.wrapping_add(best_len) > ring_buffer_mask {
                                break;
                            }
                            prev_best_val = data[cur_ix_masked.wrapping_add(best_len)];
                        }
                    }
                }
            }
            bucket[*self_num_key as usize & H9_BLOCK_MASK] = cur_ix as u32;
            *self_num_key = self_num_key.wrapping_add(1);
        }
        if !is_match_found && dictionary.is_some() {
            let (_, cur_data) = data.split_at(cur_ix_masked);
            is_match_found = SearchInStaticDictionary(
                dictionary.unwrap(),
                dictionary_hash,
                self,
                cur_data,
                max_length,
                max_backward.wrapping_add(gap),
                max_distance,
                out,
                false,
            );
        }
        is_match_found
    }

    fn Store(&mut self, data: &[u8], mask: usize, ix: usize) {
        let (_, data_window) = data.split_at((ix & mask));
        let key: u32 = self.HashBytes(data_window) as u32;
        let self_num_key = &mut self.num_.slice_mut()[key as usize];
        let minor_ix: usize = (*self_num_key as usize & H9_BLOCK_MASK);
        self.buckets_.slice_mut()[minor_ix.wrapping_add((key as usize) << H9_BLOCK_BITS)] =
            ix as u32;
        *self_num_key = self_num_key.wrapping_add(1);
    }
    fn StoreRange(&mut self, data: &[u8], mask: usize, ix_start: usize, ix_end: usize) {
        for i in ix_start..ix_end {
            self.Store(data, mask, i);
        }
    }
    fn BulkStoreRange(&mut self, data: &[u8], mask: usize, ix_start: usize, ix_end: usize) {
        for i in ix_start..ix_end {
            self.Store(data, mask, i);
        }
    }
    fn Prepare(&mut self, _one_shot: bool, _input_size: usize, _data: &[u8]) -> HowPrepared {
        if self.GetHasherCommon().is_prepared_ != 0 {
            return HowPrepared::ALREADY_PREPARED;
        }
        for item in self.num_.slice_mut().iter_mut() {
            *item = 0;
        }
        self.GetHasherCommon().is_prepared_ = 1;
        HowPrepared::NEWLY_PREPARED
    }
    fn StitchToPreviousBlock(
        &mut self,
        num_bytes: usize,
        position: usize,
        ringbuffer: &[u8],
        ringbuffer_mask: usize,
    ) {
        StitchToPreviousBlockInternal(self, num_bytes, position, ringbuffer, ringbuffer_mask)
    }
}

pub trait AdvHashSpecialization: PartialEq<Self> {
    fn get_hash_mask(&self) -> u64;
    fn set_hash_mask(&mut self, params_hash_len: i32);
    fn get_k_hash_mul(&self) -> u64;
    fn HashTypeLength(&self) -> usize;
    fn StoreLookahead(&self) -> usize;
    fn load_and_mix_word(&self, data: &[u8]) -> u64;
    fn hash_shift(&self) -> i32;
    fn bucket_size(&self) -> u32;
    fn block_mask(&self) -> u32;
    fn block_size(&self) -> u32;
    fn block_bits(&self) -> i32;
}
pub struct AdvHasher<
    Specialization: AdvHashSpecialization + Sized + Clone,
    Alloc: alloc::Allocator<u16> + alloc::Allocator<u32>,
> {
    pub GetHasherCommon: Struct1,
    pub specialization: Specialization, // contains hash_mask_
    pub num: <Alloc as Allocator<u16>>::AllocatedMemory,
    pub buckets: <Alloc as Allocator<u32>>::AllocatedMemory,
    pub h9_opts: H9Opts,
}

impl<
    Specialization: AdvHashSpecialization + Sized + Clone,
    Alloc: alloc::Allocator<u16> + alloc::Allocator<u32>,
> PartialEq<AdvHasher<Specialization, Alloc>> for AdvHasher<Specialization, Alloc>
{
    fn eq(&self, other: &Self) -> bool {
        self.GetHasherCommon == other.GetHasherCommon
            && self.specialization == other.specialization
            && self.num.slice() == other.num.slice()
            && self.buckets.slice() == other.buckets.slice()
            && self.h9_opts == other.h9_opts
    }
}

#[derive(Clone, PartialEq)]
pub struct HQ5Sub {}
impl AdvHashSpecialization for HQ5Sub {
    #[inline(always)]
    fn hash_shift(&self) -> i32 {
        32i32 - 14 // 32 - bucket_bits
    }
    #[inline(always)]
    fn bucket_size(&self) -> u32 {
        1 << 14
    }
    #[inline(always)]
    fn block_bits(&self) -> i32 {
        4
    }
    #[inline(always)]
    fn block_size(&self) -> u32 {
        1 << 4
    }
    #[inline(always)]
    fn block_mask(&self) -> u32 {
        (1 << 4) - 1
    }
    #[inline(always)]
    fn get_hash_mask(&self) -> u64 {
        //return 0xffff_ffff_ffff_ffff;
        0xffff_ffff // make it 32 bit
    }
    #[inline(always)]
    fn get_k_hash_mul(&self) -> u64 {
        kHashMul32 as u64
    }
    #[inline(always)]
    fn load_and_mix_word(&self, data: &[u8]) -> u64 {
        (BROTLI_UNALIGNED_LOAD32(data) as u64 * self.get_k_hash_mul()) & self.get_hash_mask()
    }
    #[inline(always)]
    fn set_hash_mask(&mut self, _params_hash_len: i32) {}
    fn HashTypeLength(&self) -> usize {
        4
    }
    #[inline(always)]
    fn StoreLookahead(&self) -> usize {
        4
    }
}

#[derive(Clone, PartialEq)]
pub struct HQ7Sub {}
impl AdvHashSpecialization for HQ7Sub {
    #[inline(always)]
    fn hash_shift(&self) -> i32 {
        32i32 - 15 // 32 - bucket_bits
    }
    #[inline(always)]
    fn bucket_size(&self) -> u32 {
        1 << 15
    }
    #[inline(always)]
    fn block_bits(&self) -> i32 {
        6
    }
    #[inline(always)]
    fn block_size(&self) -> u32 {
        1 << 6
    }
    #[inline(always)]
    fn block_mask(&self) -> u32 {
        (1 << 6) - 1
    }
    #[inline(always)]
    fn get_hash_mask(&self) -> u64 {
        //return 0xffff_ffff_ffff_ffff;
        0xffff_ffff // make it 32 bit
    }
    #[inline(always)]
    fn get_k_hash_mul(&self) -> u64 {
        kHashMul32 as u64
    }
    #[inline(always)]
    fn load_and_mix_word(&self, data: &[u8]) -> u64 {
        (BROTLI_UNALIGNED_LOAD32(data) as u64 * self.get_k_hash_mul()) & self.get_hash_mask()
    }
    #[inline(always)]
    fn set_hash_mask(&mut self, _params_hash_len: i32) {}
    fn HashTypeLength(&self) -> usize {
        4
    }
    #[inline(always)]
    fn StoreLookahead(&self) -> usize {
        4
    }
}

#[derive(Clone, PartialEq)]
pub struct H5Sub {
    pub hash_shift_: i32,
    pub bucket_size_: u32,
    pub block_mask_: u32,
    pub block_bits_: i32,
}

impl AdvHashSpecialization for H5Sub {
    #[inline(always)]
    fn hash_shift(&self) -> i32 {
        self.hash_shift_
    }
    fn bucket_size(&self) -> u32 {
        self.bucket_size_
    }
    fn block_bits(&self) -> i32 {
        self.block_bits_
    }
    fn block_size(&self) -> u32 {
        1 << self.block_bits_
    }
    fn block_mask(&self) -> u32 {
        self.block_mask_
    }
    fn get_hash_mask(&self) -> u64 {
        //return 0xffff_ffff_ffff_ffff;
        0xffff_ffff // make it 32 bit
    }
    fn get_k_hash_mul(&self) -> u64 {
        kHashMul32 as u64
    }
    fn load_and_mix_word(&self, data: &[u8]) -> u64 {
        (BROTLI_UNALIGNED_LOAD32(data) as u64 * self.get_k_hash_mul()) & self.get_hash_mask()
    }
    #[allow(unused_variables)]
    fn set_hash_mask(&mut self, params_hash_len: i32) {}
    fn HashTypeLength(&self) -> usize {
        4
    }
    fn StoreLookahead(&self) -> usize {
        4
    }
}

#[derive(Clone, PartialEq)]
pub struct H6Sub {
    pub hash_mask: u64,
    pub hash_shift_: i32,
    pub bucket_size_: u32,
    pub block_mask_: u32,
    pub block_bits_: i32,
}

impl AdvHashSpecialization for H6Sub {
    #[inline(always)]
    fn hash_shift(&self) -> i32 {
        self.hash_shift_
    }
    #[inline(always)]
    fn bucket_size(&self) -> u32 {
        self.bucket_size_
    }
    fn block_bits(&self) -> i32 {
        self.block_bits_
    }
    fn block_size(&self) -> u32 {
        1 << self.block_bits_
    }
    #[inline(always)]
    fn block_mask(&self) -> u32 {
        self.block_mask_
    }
    #[inline(always)]
    fn get_hash_mask(&self) -> u64 {
        self.hash_mask
    }
    #[inline(always)]
    fn set_hash_mask(&mut self, params_hash_len: i32) {
        // FIXME: this assumes params_hash_len is fairly small, or else it may result in a negative shift value
        self.hash_mask = u64::MAX >> (64i32 - 8i32 * params_hash_len);
    }
    #[inline(always)]
    fn get_k_hash_mul(&self) -> u64 {
        kHashMul64Long
    }
    #[inline(always)]
    fn load_and_mix_word(&self, data: &[u8]) -> u64 {
        (BROTLI_UNALIGNED_LOAD64(data) & self.get_hash_mask()).wrapping_mul(self.get_k_hash_mul())
    }
    #[inline(always)]
    fn HashTypeLength(&self) -> usize {
        8
    }
    #[inline(always)]
    fn StoreLookahead(&self) -> usize {
        8
    }
}

fn BackwardReferencePenaltyUsingLastDistance(distance_short_code: usize) -> u64 {
    // FIXME?: double bitwise AND with the same value?
    (39u64).wrapping_add((0x0001_ca10_u64 >> (distance_short_code & 0x0e) & 0x0e))
}

impl<
    Specialization: AdvHashSpecialization + Clone,
    Alloc: alloc::Allocator<u16> + alloc::Allocator<u32>,
> AdvHasher<Specialization, Alloc>
{
    // 7 opt
    // returns a new ix_start
    fn StoreRangeOptBatch(
        &mut self,
        data: &[u8],
        mask: usize,
        ix_start: usize,
        ix_end: usize,
    ) -> usize {
        let lookahead = self.specialization.StoreLookahead();
        if ix_end >= ix_start + lookahead * 2 && lookahead == 4 {
            let num = self.num.slice_mut();
            let buckets = self.buckets.slice_mut();
            assert_eq!(num.len(), self.specialization.bucket_size() as usize);
            assert_eq!(
                buckets.len(),
                self.specialization.bucket_size() as usize
                    * self.specialization.block_size() as usize
            );
            let shift = self.specialization.hash_shift();
            let chunk_count = (ix_end - ix_start) / 4;
            for chunk_id in 0..chunk_count {
                let i = (ix_start + chunk_id * 4) & mask;
                let ffffffff = 0xffff_ffff;
                let word = u64::from(data[i])
                    | (u64::from(data[i + 1]) << 8)
                    | (u64::from(data[i + 2]) << 16)
                    | (u64::from(data[i + 3]) << 24)
                    | (u64::from(data[i + 4]) << 32)
                    | (u64::from(data[i + 5]) << 40)
                    | (u64::from(data[i + 6]) << 48);
                let mixed0 = ((((word & ffffffff) * self.specialization.get_k_hash_mul())
                    & self.specialization.get_hash_mask())
                    >> shift) as usize;
                let mixed1 = (((((word >> 8) & ffffffff) * self.specialization.get_k_hash_mul())
                    & self.specialization.get_hash_mask())
                    >> shift) as usize;
                let mixed2 = (((((word >> 16) & ffffffff) * self.specialization.get_k_hash_mul())
                    & self.specialization.get_hash_mask())
                    >> shift) as usize;
                let mixed3 = (((((word >> 24) & ffffffff) * self.specialization.get_k_hash_mul())
                    & self.specialization.get_hash_mask())
                    >> shift) as usize;
                let mut num_ref0 = u32::from(num[mixed0]);
                num[mixed0] = num_ref0.wrapping_add(1) as u16;
                num_ref0 &= self.specialization.block_mask();
                let mut num_ref1 = u32::from(num[mixed1]);
                num[mixed1] = num_ref1.wrapping_add(1) as u16;
                num_ref1 &= self.specialization.block_mask();
                let mut num_ref2 = u32::from(num[mixed2]);
                num[mixed2] = num_ref2.wrapping_add(1) as u16;
                num_ref2 &= self.specialization.block_mask();
                let mut num_ref3 = u32::from(num[mixed3]);
                num[mixed3] = num_ref3.wrapping_add(1) as u16;
                num_ref3 &= self.specialization.block_mask();
                let offset0: usize =
                    (mixed0 << self.specialization.block_bits()) + num_ref0 as usize;
                let offset1: usize =
                    (mixed1 << self.specialization.block_bits()) + num_ref1 as usize;
                let offset2: usize =
                    (mixed2 << self.specialization.block_bits()) + num_ref2 as usize;
                let offset3: usize =
                    (mixed3 << self.specialization.block_bits()) + num_ref3 as usize;
                buckets[offset0] = (i) as u32;
                buckets[offset1] = (i + 1) as u32;
                buckets[offset2] = (i + 2) as u32;
                buckets[offset3] = (i + 3) as u32;
            }
            return ix_start + chunk_count * 4;
        }
        ix_start
    }

    fn BulkStoreRangeOptMemFetch(
        &mut self,
        data: &[u8],
        mask: usize,
        ix_start: usize,
        ix_end: usize,
    ) -> usize {
        const REG_SIZE: usize = 32usize;
        let lookahead = self.specialization.StoreLookahead();
        if mask == usize::MAX && ix_end > ix_start + REG_SIZE && lookahead == 4 {
            const lookahead4: usize = 4;
            assert_eq!(lookahead4, lookahead);
            let mut data64 = [0u8; REG_SIZE + lookahead4 - 1];
            let del = (ix_end - ix_start) / REG_SIZE;
            let num = self.num.slice_mut();
            let buckets = self.buckets.slice_mut();
            assert_eq!(num.len(), self.specialization.bucket_size() as usize);
            assert_eq!(
                buckets.len(),
                self.specialization.bucket_size() as usize
                    * self.specialization.block_size() as usize
            );
            let shift = self.specialization.hash_shift();
            for chunk_id in 0..del {
                let ix_offset = ix_start + chunk_id * REG_SIZE;
                data64[..REG_SIZE + lookahead4 - 1].copy_from_slice(
                    data.split_at(ix_offset)
                        .1
                        .split_at(REG_SIZE + lookahead4 - 1)
                        .0,
                );
                for quad_index in 0..(REG_SIZE >> 2) {
                    let i = quad_index << 2;
                    let ffffffff = 0xffff_ffff;
                    let word = u64::from(data64[i])
                        | (u64::from(data64[i + 1]) << 8)
                        | (u64::from(data64[i + 2]) << 16)
                        | (u64::from(data64[i + 3]) << 24)
                        | (u64::from(data64[i + 4]) << 32)
                        | (u64::from(data64[i + 5]) << 40)
                        | (u64::from(data64[i + 6]) << 48);
                    let mixed0 = ((((word & ffffffff) * self.specialization.get_k_hash_mul())
                        & self.specialization.get_hash_mask())
                        >> shift) as usize;
                    let mixed1 = (((((word >> 8) & ffffffff)
                        * self.specialization.get_k_hash_mul())
                        & self.specialization.get_hash_mask())
                        >> shift) as usize;
                    let mixed2 = (((((word >> 16) & ffffffff)
                        * self.specialization.get_k_hash_mul())
                        & self.specialization.get_hash_mask())
                        >> shift) as usize;
                    let mixed3 = (((((word >> 24) & ffffffff)
                        * self.specialization.get_k_hash_mul())
                        & self.specialization.get_hash_mask())
                        >> shift) as usize;
                    let mut num_ref0 = u32::from(num[mixed0]);
                    num[mixed0] = num_ref0.wrapping_add(1) as u16;
                    num_ref0 &= self.specialization.block_mask();
                    let mut num_ref1 = u32::from(num[mixed1]);
                    num[mixed1] = num_ref1.wrapping_add(1) as u16;
                    num_ref1 &= self.specialization.block_mask();
                    let mut num_ref2 = u32::from(num[mixed2]);
                    num[mixed2] = num_ref2.wrapping_add(1) as u16;
                    num_ref2 &= self.specialization.block_mask();
                    let mut num_ref3 = u32::from(num[mixed3]);
                    num[mixed3] = num_ref3.wrapping_add(1) as u16;
                    num_ref3 &= self.specialization.block_mask();
                    let offset0: usize =
                        (mixed0 << self.specialization.block_bits()) + num_ref0 as usize;
                    let offset1: usize =
                        (mixed1 << self.specialization.block_bits()) + num_ref1 as usize;
                    let offset2: usize =
                        (mixed2 << self.specialization.block_bits()) + num_ref2 as usize;
                    let offset3: usize =
                        (mixed3 << self.specialization.block_bits()) + num_ref3 as usize;
                    buckets[offset0] = (ix_offset + i) as u32;
                    buckets[offset1] = (ix_offset + i + 1) as u32;
                    buckets[offset2] = (ix_offset + i + 2) as u32;
                    buckets[offset3] = (ix_offset + i + 3) as u32;
                }
            }
            return ix_start + del * REG_SIZE;
        }
        ix_start
    }

    #[cfg(feature = "benchmark")]
    fn BulkStoreRangeOptMemFetchLazyDupeUpdate(
        &mut self,
        data: &[u8],
        mask: usize,
        ix_start: usize,
        ix_end: usize,
    ) -> usize {
        const REG_SIZE: usize = 32usize;
        let lookahead = self.specialization.StoreLookahead();
        if mask == usize::MAX && ix_end > ix_start + REG_SIZE && lookahead == 4 {
            const lookahead4: usize = 4;
            assert_eq!(lookahead4, lookahead);
            let mut data64 = [0u8; REG_SIZE + lookahead4];
            let del = (ix_end - ix_start) / REG_SIZE;
            let num = self.num.slice_mut();
            let buckets = self.buckets.slice_mut();
            assert_eq!(num.len(), self.specialization.bucket_size() as usize);
            assert_eq!(
                buckets.len(),
                self.specialization.bucket_size() as usize
                    * self.specialization.block_size() as usize
            );
            let shift = self.specialization.hash_shift();
            for chunk_id in 0..del {
                let ix_offset = ix_start + chunk_id * REG_SIZE;
                data64[..REG_SIZE + lookahead4]
                    .copy_from_slice(data.split_at(ix_offset).1.split_at(REG_SIZE + lookahead4).0);
                for quad_index in 0..(REG_SIZE >> 2) {
                    let i = quad_index << 2;
                    let ffffffff = 0xffff_ffff;
                    let word = u64::from(data64[i])
                        | (u64::from(data64[i + 1]) << 8)
                        | (u64::from(data64[i + 2]) << 16)
                        | (u64::from(data64[i + 3]) << 24)
                        | (u64::from(data64[i + 4]) << 32)
                        | (u64::from(data64[i + 5]) << 40)
                        | (u64::from(data64[i + 6]) << 48);
                    let mixed0 = ((((word & ffffffff) * self.specialization.get_k_hash_mul())
                        & self.specialization.get_hash_mask())
                        >> shift) as usize;
                    let mixed1 = (((((word >> 8) & ffffffff)
                        * self.specialization.get_k_hash_mul())
                        & self.specialization.get_hash_mask())
                        >> shift) as usize;
                    let mixed2 = (((((word >> 16) & ffffffff)
                        * self.specialization.get_k_hash_mul())
                        & self.specialization.get_hash_mask())
                        >> shift) as usize;
                    let mixed3 = (((((word >> 24) & ffffffff)
                        * self.specialization.get_k_hash_mul())
                        & self.specialization.get_hash_mask())
                        >> shift) as usize;
                    let mut num_ref0 = u32::from(num[mixed0]);
                    let mut num_ref1 = u32::from(num[mixed1]);
                    let mut num_ref2 = u32::from(num[mixed2]);
                    let mut num_ref3 = u32::from(num[mixed3]);
                    num[mixed0] = num_ref0.wrapping_add(1) as u16;
                    num[mixed1] = num_ref1.wrapping_add(1) as u16;
                    num[mixed2] = num_ref2.wrapping_add(1) as u16;
                    num[mixed3] = num_ref3.wrapping_add(1) as u16;
                    num_ref0 &= self.specialization.block_mask();
                    num_ref1 &= self.specialization.block_mask();
                    num_ref2 &= self.specialization.block_mask();
                    num_ref3 &= self.specialization.block_mask();
                    let offset0: usize =
                        (mixed0 << self.specialization.block_bits()) + num_ref0 as usize;
                    let offset1: usize =
                        (mixed1 << self.specialization.block_bits()) + num_ref1 as usize;
                    let offset2: usize =
                        (mixed2 << self.specialization.block_bits()) + num_ref2 as usize;
                    let offset3: usize =
                        (mixed3 << self.specialization.block_bits()) + num_ref3 as usize;
                    buckets[offset0] = (ix_offset + i) as u32;
                    buckets[offset1] = (ix_offset + i + 1) as u32;
                    buckets[offset2] = (ix_offset + i + 2) as u32;
                    buckets[offset3] = (ix_offset + i + 3) as u32;
                }
            }
            return ix_start + del * REG_SIZE;
        }
        ix_start
    }

    #[cfg(feature = "benchmark")]
    fn BulkStoreRangeOptRandomDupeUpdate(
        &mut self,
        data: &[u8],
        mask: usize,
        ix_start: usize,
        ix_end: usize,
    ) -> usize {
        const REG_SIZE: usize = 32usize;
        let lookahead = self.specialization.StoreLookahead();
        if mask == usize::MAX && ix_end > ix_start + REG_SIZE && lookahead == 4 {
            const lookahead4: usize = 4;
            assert_eq!(lookahead4, lookahead);
            let mut data64 = [0u8; REG_SIZE + lookahead4];
            let del = (ix_end - ix_start) / REG_SIZE;
            let num = self.num.slice_mut();
            let buckets = self.buckets.slice_mut();
            assert_eq!(num.len(), self.specialization.bucket_size() as usize);
            assert_eq!(
                buckets.len(),
                self.specialization.bucket_size() as usize
                    * self.specialization.block_size() as usize
            );
            let shift = self.specialization.hash_shift();
            for chunk_id in 0..del {
                let ix_offset = ix_start + chunk_id * REG_SIZE;
                data64[..REG_SIZE + lookahead4]
                    .copy_from_slice(data.split_at(ix_offset).1.split_at(REG_SIZE + lookahead4).0);
                for i in 0..REG_SIZE {
                    let mixed_word = ((u32::from(data64[i])
                        | (u32::from(data64[i + 1]) << 8)
                        | (u32::from(data64[i + 2]) << 16)
                        | (u32::from(data64[i + 3]) << 24))
                        as u64
                        * self.specialization.get_k_hash_mul())
                        & self.specialization.get_hash_mask();
                    let key = mixed_word >> shift;
                    let minor_ix: usize = chunk_id & self.specialization.block_mask() as usize; //   *num_ref as usize & self.specialization.block_mask() as usize; //GIGANTIC HAX: overwrite firsst option
                    let offset: usize =
                        minor_ix + (key << self.specialization.block_bits()) as usize;
                    buckets[offset] = (ix_offset + i) as u32;
                }
            }
            for (bucket_index, num_ref) in num.iter_mut().enumerate() {
                let region = buckets
                    .split_at_mut(bucket_index << self.specialization.block_bits())
                    .1
                    .split_at_mut(self.specialization.block_size() as usize)
                    .0;
                let mut lnum = 0usize;
                for block_index in 0..self.specialization.block_size() as usize {
                    if region[block_index] != 0 {
                        let byte_addr = region[block_index];
                        region[lnum] = byte_addr;
                        lnum += 1;
                    }
                }
                *num_ref = lnum as u16;
            }
            return ix_start + del * REG_SIZE;
        }
        ix_start
    }
}

impl<
    Specialization: AdvHashSpecialization + Clone,
    Alloc: alloc::Allocator<u16> + alloc::Allocator<u32>,
> AnyHasher for AdvHasher<Specialization, Alloc>
{
    fn Opts(&self) -> H9Opts {
        self.h9_opts
    }
    fn PrepareDistanceCache(&self, distance_cache: &mut [i32]) {
        let num_distances = self.GetHasherCommon.params.num_last_distances_to_check;
        adv_prepare_distance_cache(distance_cache, num_distances);
    }
    fn StitchToPreviousBlock(
        &mut self,
        num_bytes: usize,
        position: usize,
        ringbuffer: &[u8],
        ringbuffer_mask: usize,
    ) {
        StitchToPreviousBlockInternal(self, num_bytes, position, ringbuffer, ringbuffer_mask);
    }
    fn Prepare(&mut self, one_shot: bool, input_size: usize, data: &[u8]) -> HowPrepared {
        if self.GetHasherCommon.is_prepared_ != 0 {
            return HowPrepared::ALREADY_PREPARED;
        }
        let partial_prepare_threshold = self.specialization.bucket_size() as usize >> 6;
        if one_shot && input_size <= partial_prepare_threshold {
            for i in 0..input_size {
                let key = self.HashBytes(&data[i..]);
                self.num.slice_mut()[key] = 0;
            }
        } else {
            for item in
                self.num.slice_mut()[..(self.specialization.bucket_size() as usize)].iter_mut()
            {
                *item = 0;
            }
        }
        self.GetHasherCommon.is_prepared_ = 1;
        HowPrepared::NEWLY_PREPARED
    }

    fn GetHasherCommon(&mut self) -> &mut Struct1 {
        &mut self.GetHasherCommon
    }
    fn HashTypeLength(&self) -> usize {
        self.specialization.HashTypeLength()
    }
    fn StoreLookahead(&self) -> usize {
        self.specialization.StoreLookahead()
    }
    fn HashBytes(&self, data: &[u8]) -> usize {
        let shift = self.specialization.hash_shift();
        let h: u64 = self.specialization.load_and_mix_word(data);
        (h >> shift) as u32 as usize
    }
    fn StoreEvenVec4(&mut self, data: &[u8], mask: usize, ix: usize) {
        if self.specialization.StoreLookahead() != 4 {
            for i in 0..4 {
                self.Store(data, mask, ix + i * 2);
            }
            return;
        }
        let shift = self.specialization.hash_shift();
        let num = self.num.slice_mut();
        let buckets = self.buckets.slice_mut();
        let li = ix & mask;
        let lword = u64::from(data[li])
            | (u64::from(data[li + 1]) << 8)
            | (u64::from(data[li + 2]) << 16)
            | (u64::from(data[li + 3]) << 24)
            | (u64::from(data[li + 4]) << 32)
            | (u64::from(data[li + 5]) << 40)
            | (u64::from(data[li + 6]) << 48)
            | (u64::from(data[li + 7]) << 56);
        let hi = (ix + 8) & mask;
        let hword = u64::from(data[hi]) | (u64::from(data[hi + 1]) << 8);
        let mixed0 = ((((lword & 0xffff_ffff) * self.specialization.get_k_hash_mul())
            & self.specialization.get_hash_mask())
            >> shift) as usize;
        let mixed1 = (((((lword >> 16) & 0xffff_ffff) * self.specialization.get_k_hash_mul())
            & self.specialization.get_hash_mask())
            >> shift) as usize;
        let mixed2 = (((((lword >> 32) & 0xffff_ffff) * self.specialization.get_k_hash_mul())
            & self.specialization.get_hash_mask())
            >> shift) as usize;
        let mixed3 = ((((((hword & 0xffff) << 16) | ((lword >> 48) & 0xffff))
            * self.specialization.get_k_hash_mul())
            & self.specialization.get_hash_mask())
            >> shift) as usize;
        let mut num_ref0 = u32::from(num[mixed0]);
        num[mixed0] = num_ref0.wrapping_add(1) as u16;
        num_ref0 &= self.specialization.block_mask();
        let mut num_ref1 = u32::from(num[mixed1]);
        num[mixed1] = num_ref1.wrapping_add(1) as u16;
        num_ref1 &= self.specialization.block_mask();
        let mut num_ref2 = u32::from(num[mixed2]);
        num[mixed2] = num_ref2.wrapping_add(1) as u16;
        num_ref2 &= self.specialization.block_mask();
        let mut num_ref3 = u32::from(num[mixed3]);
        num[mixed3] = num_ref3.wrapping_add(1) as u16;
        num_ref3 &= self.specialization.block_mask();
        let offset0: usize = (mixed0 << self.specialization.block_bits()) + num_ref0 as usize;
        let offset1: usize = (mixed1 << self.specialization.block_bits()) + num_ref1 as usize;
        let offset2: usize = (mixed2 << self.specialization.block_bits()) + num_ref2 as usize;
        let offset3: usize = (mixed3 << self.specialization.block_bits()) + num_ref3 as usize;
        buckets[offset0] = ix as u32;
        buckets[offset1] = (ix + 2) as u32;
        buckets[offset2] = (ix + 4) as u32;
        buckets[offset3] = (ix + 6) as u32;
    }
    fn Store4Vec4(&mut self, data: &[u8], mask: usize, ix: usize) {
        if self.specialization.StoreLookahead() != 4 {
            for i in 0..4 {
                self.Store(data, mask, ix + i * 4);
            }
            return;
        }
        let shift = self.specialization.hash_shift();
        let num = self.num.slice_mut();
        let buckets = self.buckets.slice_mut();
        let li = ix & mask;
        let llword = u32::from(data[li])
            | (u32::from(data[li + 1]) << 8)
            | (u32::from(data[li + 2]) << 16)
            | (u32::from(data[li + 3]) << 24);
        let luword = u32::from(data[li + 4])
            | (u32::from(data[li + 5]) << 8)
            | (u32::from(data[li + 6]) << 16)
            | (u32::from(data[li + 7]) << 24);
        let ui = (ix + 8) & mask;
        let ulword = u32::from(data[ui])
            | (u32::from(data[ui + 1]) << 8)
            | (u32::from(data[ui + 2]) << 16)
            | (u32::from(data[ui + 3]) << 24);

        let uuword = u32::from(data[ui + 4])
            | (u32::from(data[ui + 5]) << 8)
            | (u32::from(data[ui + 6]) << 16)
            | (u32::from(data[ui + 7]) << 24);

        let mixed0 = (((u64::from(llword) * self.specialization.get_k_hash_mul())
            & self.specialization.get_hash_mask())
            >> shift) as usize;
        let mixed1 = (((u64::from(luword) * self.specialization.get_k_hash_mul())
            & self.specialization.get_hash_mask())
            >> shift) as usize;
        let mixed2 = (((u64::from(ulword) * self.specialization.get_k_hash_mul())
            & self.specialization.get_hash_mask())
            >> shift) as usize;
        let mixed3 = (((u64::from(uuword) * self.specialization.get_k_hash_mul())
            & self.specialization.get_hash_mask())
            >> shift) as usize;
        let mut num_ref0 = u32::from(num[mixed0]);
        num[mixed0] = num_ref0.wrapping_add(1) as u16;
        num_ref0 &= self.specialization.block_mask();
        let mut num_ref1 = u32::from(num[mixed1]);
        num[mixed1] = num_ref1.wrapping_add(1) as u16;
        num_ref1 &= self.specialization.block_mask();
        let mut num_ref2 = u32::from(num[mixed2]);
        num[mixed2] = num_ref2.wrapping_add(1) as u16;
        num_ref2 &= self.specialization.block_mask();
        let mut num_ref3 = u32::from(num[mixed3]);
        num[mixed3] = num_ref3.wrapping_add(1) as u16;
        num_ref3 &= self.specialization.block_mask();
        let offset0: usize = (mixed0 << self.specialization.block_bits()) + num_ref0 as usize;
        let offset1: usize = (mixed1 << self.specialization.block_bits()) + num_ref1 as usize;
        let offset2: usize = (mixed2 << self.specialization.block_bits()) + num_ref2 as usize;
        let offset3: usize = (mixed3 << self.specialization.block_bits()) + num_ref3 as usize;
        buckets[offset0] = ix as u32;
        buckets[offset1] = (ix + 4) as u32;
        buckets[offset2] = (ix + 8) as u32;
        buckets[offset3] = (ix + 12) as u32;
    }
    fn Store(&mut self, data: &[u8], mask: usize, ix: usize) {
        let (_, data_window) = data.split_at((ix & mask));
        let key: u32 = self.HashBytes(data_window) as u32;
        let minor_ix: usize =
            (self.num.slice()[(key as usize)] as u32 & self.specialization.block_mask()) as usize;
        let offset: usize =
            minor_ix.wrapping_add((key << self.specialization.block_bits()) as usize);
        self.buckets.slice_mut()[offset] = ix as u32;
        {
            let _lhs = &mut self.num.slice_mut()[(key as usize)];
            *_lhs = (*_lhs as i32 + 1) as u16;
        }
    }
    fn StoreRange(&mut self, data: &[u8], mask: usize, ix_start: usize, ix_end: usize) {
        for i in self.StoreRangeOptBatch(data, mask, ix_start, ix_end)..ix_end {
            self.Store(data, mask, i);
        }
    }
    fn BulkStoreRange(&mut self, data: &[u8], mask: usize, mut ix_start: usize, ix_end: usize) {
        /*
        if ix_start + 4096 < ix_end {
          for vec_offset in 0..(ix_end - ix_start - 4096) / 16 {
            self.Store4Vec4(data, mask, ix_start + vec_offset * 16);
          }
          ix_start += 16 * ((ix_end - ix_start - 4096) / 16);
        }
        if ix_start + 512 < ix_end {
          for vec_offset in 0..(ix_end - ix_start - 512) / 8 {
            self.StoreEvenVec4(data, mask, ix_start + vec_offset * 8);
            //self.StoreRange(data, mask, ix_start + vec_offset * 8, ix_start + (1+ vec_offset) * 8);
          }
          ix_start += 8 * ((ix_end - ix_start - 512) / 8);
        }
         */
        ix_start = self.BulkStoreRangeOptMemFetch(data, mask, ix_start, ix_end);
        for i in ix_start..ix_end {
            self.Store(data, mask, i);
        }
    }

    #[cfg_attr(feature = "hotpath", hotpath::measure)]
    fn FindLongestMatch(
        &mut self,
        dictionary: Option<&BrotliDictionary>,
        dictionary_hash: &[u16],
        data: &[u8],
        ring_buffer_mask: usize,
        ring_buffer_break: Option<core::num::NonZeroUsize>,
        distance_cache: &[i32],
        cur_ix: usize,
        max_length: usize,
        max_backward: usize,
        gap: usize,
        max_distance: usize,
        out: &mut HasherSearchResult,
    ) -> bool {
        let opts = self.Opts();
        let cur_ix_masked: usize = cur_ix & ring_buffer_mask;
        let mut is_match_found = false;
        let mut best_score: u64 = out.score;
        let mut best_len: usize = out.len;
        out.len = 0usize;
        out.len_x_code = 0usize;
        let cur_data = data.split_at(cur_ix_masked).1;
        for i in 0..self.GetHasherCommon.params.num_last_distances_to_check as usize {
            let backward: usize = distance_cache[i] as usize;
            let mut prev_ix: usize = cur_ix.wrapping_sub(backward);
            if prev_ix >= cur_ix || backward > max_backward {
                continue;
            }
            prev_ix &= ring_buffer_mask;
            if (cur_ix_masked.wrapping_add(best_len) > ring_buffer_mask
                || prev_ix.wrapping_add(best_len) > ring_buffer_mask
                || cur_data[best_len] != data[prev_ix.wrapping_add(best_len)])
            {
                continue;
            }
            let prev_data = data.split_at(prev_ix).1;

            let unbroken_len = FindMatchLengthWithLimit(prev_data, cur_data, max_length);
            if unbroken_len >= 3 || (unbroken_len == 2 && i < 2) {
                let len = fix_unbroken_len(unbroken_len, prev_ix, cur_ix_masked, ring_buffer_break);
                let mut score: u64 = BackwardReferenceScoreUsingLastDistance(len, opts);
                if best_score < score {
                    if i != 0 {
                        score = score.wrapping_sub(BackwardReferencePenaltyUsingLastDistance(i));
                    }
                    if best_score < score {
                        best_score = score;
                        best_len = len;
                        out.len = best_len;
                        out.distance = backward;
                        out.score = best_score;
                        is_match_found = true;
                    }
                }
            }
        }

        let key: u32 = self.HashBytes(cur_data) as u32;
        let common_block_bits = self.specialization.block_bits();
        let num_ref_mut = &mut self.num.slice_mut()[key as usize];
        let num_copy = *num_ref_mut;
        let bucket: &mut [u32] = self
            .buckets
            .slice_mut()
            .split_at_mut((key << common_block_bits) as usize)
            .1
            .split_at_mut(self.specialization.block_size() as usize)
            .0;
        assert!(bucket.len() > self.specialization.block_mask() as usize);
        if num_copy != 0 {
            let down: usize = max(
                i32::from(num_copy) - self.specialization.block_size() as i32,
                0,
            ) as usize;
            let mut i = num_copy as usize;
            while i > down {
                i -= 1;
                let mut prev_ix = bucket[i & self.specialization.block_mask() as usize] as usize;
                let backward = cur_ix.wrapping_sub(prev_ix);
                prev_ix &= ring_buffer_mask;
                if (cur_ix_masked.wrapping_add(best_len) > ring_buffer_mask
                    || prev_ix.wrapping_add(best_len) > ring_buffer_mask
                    || cur_data[best_len] != data[prev_ix.wrapping_add(best_len)])
                {
                    if backward > max_backward {
                        break;
                    }
                    continue;
                }
                if backward > max_backward {
                    break;
                }
                let prev_data = data.split_at(prev_ix).1;
                let unbroken_len = FindMatchLengthWithLimitMin4(prev_data, cur_data, max_length);
                if unbroken_len != 0 {
                    let len =
                        fix_unbroken_len(unbroken_len, prev_ix, cur_ix_masked, ring_buffer_break);
                    let score: u64 = BackwardReferenceScore(len, backward, opts);
                    if best_score < score {
                        best_score = score;
                        best_len = len;
                        out.len = best_len;
                        out.distance = backward;
                        out.score = best_score;
                        is_match_found = true;
                    }
                }
            }
        }
        bucket[(num_copy as u32 & self.specialization.block_mask()) as usize] = cur_ix as u32;
        *num_ref_mut = num_ref_mut.wrapping_add(1);

        if !is_match_found && dictionary.is_some() {
            let (_, cur_data) = data.split_at(cur_ix_masked);
            is_match_found = SearchInStaticDictionary(
                dictionary.unwrap(),
                dictionary_hash,
                self,
                cur_data,
                max_length,
                max_backward.wrapping_add(gap),
                max_distance,
                out,
                false,
            );
        }
        is_match_found
    }
}

const FORGETFUL_BUCKET_BITS: usize = 15;
const FORGETFUL_BUCKET_SIZE: usize = 1 << FORGETFUL_BUCKET_BITS;
const FORGETFUL_TINY_HASH_SIZE: usize = 1 << 16;

/// Google's forgetful-chain match finder. The three C specializations only
/// differ in bank layout and in how many recent distances they inspect, so a
/// const-generic implementation keeps their behavior in one place.
pub struct ForgetfulHasher<
    Alloc: alloc::Allocator<u8> + alloc::Allocator<u16> + alloc::Allocator<u32>,
    const NUM_BANKS: usize,
    const BANK_BITS: usize,
    const NUM_LAST_DISTANCES_TO_CHECK: usize,
> {
    pub common: Struct1,
    pub addr: <Alloc as alloc::Allocator<u32>>::AllocatedMemory,
    pub head: <Alloc as alloc::Allocator<u16>>::AllocatedMemory,
    pub tiny_hash: <Alloc as alloc::Allocator<u8>>::AllocatedMemory,
    /// A slot is packed as `delta | (next << 16)`.
    pub slots: <Alloc as alloc::Allocator<u32>>::AllocatedMemory,
    pub free_slot_idx: <Alloc as alloc::Allocator<u16>>::AllocatedMemory,
    pub max_hops: usize,
    pub h9_opts: H9Opts,
}

pub type H40<Alloc> = ForgetfulHasher<Alloc, 1, 16, 4>;
pub type H41<Alloc> = ForgetfulHasher<Alloc, 1, 16, 10>;
pub type H42<Alloc> = ForgetfulHasher<Alloc, 512, 9, 16>;

impl<
    Alloc: alloc::Allocator<u8> + alloc::Allocator<u16> + alloc::Allocator<u32>,
    const NUM_BANKS: usize,
    const BANK_BITS: usize,
    const NUM_LAST_DISTANCES_TO_CHECK: usize,
> PartialEq for ForgetfulHasher<Alloc, NUM_BANKS, BANK_BITS, NUM_LAST_DISTANCES_TO_CHECK>
{
    fn eq(&self, other: &Self) -> bool {
        self.common == other.common
            && self.addr.slice() == other.addr.slice()
            && self.head.slice() == other.head.slice()
            && self.tiny_hash.slice() == other.tiny_hash.slice()
            && self.slots.slice() == other.slots.slice()
            && self.free_slot_idx.slice() == other.free_slot_idx.slice()
            && self.max_hops == other.max_hops
            && self.h9_opts == other.h9_opts
    }
}

impl<
    Alloc: alloc::Allocator<u8> + alloc::Allocator<u16> + alloc::Allocator<u32>,
    const NUM_BANKS: usize,
    const BANK_BITS: usize,
    const NUM_LAST_DISTANCES_TO_CHECK: usize,
> ForgetfulHasher<Alloc, NUM_BANKS, BANK_BITS, NUM_LAST_DISTANCES_TO_CHECK>
{
    pub fn new(alloc: &mut Alloc, params: &BrotliEncoderParams) -> Self {
        let mut addr = allocate::<u32, _>(alloc, FORGETFUL_BUCKET_SIZE);
        addr.slice_mut().fill(0xcccc_cccc);
        let mut head = allocate::<u16, _>(alloc, FORGETFUL_BUCKET_SIZE);
        head.slice_mut().fill(0);
        let mut tiny_hash = allocate::<u8, _>(alloc, FORGETFUL_TINY_HASH_SIZE);
        tiny_hash.slice_mut().fill(0);
        let mut free_slot_idx = allocate::<u16, _>(alloc, NUM_BANKS);
        free_slot_idx.slice_mut().fill(0);
        Self {
            common: Struct1 {
                params: params.hasher,
                is_prepared_: 1,
                dict_num_lookups: 0,
                dict_num_matches: 0,
            },
            addr,
            head,
            tiny_hash,
            slots: allocate::<u32, _>(alloc, NUM_BANKS << BANK_BITS),
            free_slot_idx,
            max_hops: (if params.quality > 6 { 7 } else { 8 })
                << params.quality.saturating_sub(4) as usize,
            h9_opts: H9Opts::new(&params.hasher),
        }
    }

    pub fn free(&mut self, alloc: &mut Alloc) {
        <Alloc as Allocator<u32>>::free_cell(alloc, core::mem::take(&mut self.addr));
        <Alloc as Allocator<u16>>::free_cell(alloc, core::mem::take(&mut self.head));
        <Alloc as Allocator<u8>>::free_cell(alloc, core::mem::take(&mut self.tiny_hash));
        <Alloc as Allocator<u32>>::free_cell(alloc, core::mem::take(&mut self.slots));
        <Alloc as Allocator<u16>>::free_cell(alloc, core::mem::take(&mut self.free_slot_idx));
    }

    #[inline(always)]
    fn store(&mut self, data: &[u8], mask: usize, ix: usize) {
        let key = self.HashBytes(&data[ix & mask..]);
        let bank = key & (NUM_BANKS - 1);
        let bank_size = 1usize << BANK_BITS;
        let idx = self.free_slot_idx.slice()[bank] as usize & (bank_size - 1);
        let next_free_slot = self.free_slot_idx.slice()[bank].wrapping_add(1);
        self.free_slot_idx.slice_mut()[bank] = next_free_slot;
        let delta = ix
            .wrapping_sub(self.addr.slice()[key] as usize)
            .min(u16::MAX as usize) as u16;
        let next = self.head.slice()[key];
        self.tiny_hash.slice_mut()[ix as u16 as usize] = key as u8;
        self.slots.slice_mut()[bank * bank_size + idx] = u32::from(delta) | (u32::from(next) << 16);
        self.addr.slice_mut()[key] = ix as u32;
        self.head.slice_mut()[key] = idx as u16;
    }
}

impl<
    Alloc: alloc::Allocator<u8> + alloc::Allocator<u16> + alloc::Allocator<u32>,
    const NUM_BANKS: usize,
    const BANK_BITS: usize,
    const NUM_LAST_DISTANCES_TO_CHECK: usize,
> AnyHasher for ForgetfulHasher<Alloc, NUM_BANKS, BANK_BITS, NUM_LAST_DISTANCES_TO_CHECK>
{
    fn Opts(&self) -> H9Opts {
        self.h9_opts
    }

    fn GetHasherCommon(&mut self) -> &mut Struct1 {
        &mut self.common
    }

    fn HashBytes(&self, data: &[u8]) -> usize {
        (BROTLI_UNALIGNED_LOAD32(data).wrapping_mul(kHashMul32) >> (32 - FORGETFUL_BUCKET_BITS))
            as usize
    }

    fn HashTypeLength(&self) -> usize {
        4
    }

    fn StoreLookahead(&self) -> usize {
        4
    }

    fn PrepareDistanceCache(&self, distance_cache: &mut [i32]) {
        adv_prepare_distance_cache(distance_cache, NUM_LAST_DISTANCES_TO_CHECK as i32);
    }

    fn FindLongestMatch(
        &mut self,
        dictionary: Option<&BrotliDictionary>,
        dictionary_hash: &[u16],
        data: &[u8],
        ring_buffer_mask: usize,
        ring_buffer_break: Option<core::num::NonZeroUsize>,
        distance_cache: &[i32],
        cur_ix: usize,
        max_length: usize,
        max_backward: usize,
        gap: usize,
        max_distance: usize,
        out: &mut HasherSearchResult,
    ) -> bool {
        let cur_ix_masked = cur_ix & ring_buffer_mask;
        let cur_data = &data[cur_ix_masked..];
        let min_score = out.score;
        let mut best_score = out.score;
        let mut best_len = out.len;
        let key = self.HashBytes(cur_data);
        let tiny_hash = key as u8;
        out.len = 0;
        out.len_x_code = 0;

        for (i, distance) in distance_cache
            .iter()
            .take(NUM_LAST_DISTANCES_TO_CHECK)
            .enumerate()
        {
            let backward = *distance as usize;
            let mut prev_ix = cur_ix.wrapping_sub(backward);
            if i > 0 && self.tiny_hash.slice()[prev_ix as u16 as usize] != tiny_hash {
                continue;
            }
            if prev_ix >= cur_ix || backward > max_backward {
                continue;
            }
            prev_ix &= ring_buffer_mask;
            let unbroken_len = FindMatchLengthWithLimit(&data[prev_ix..], cur_data, max_length);
            if unbroken_len >= 2 {
                let len = fix_unbroken_len(unbroken_len, prev_ix, cur_ix_masked, ring_buffer_break);
                let mut score = BackwardReferenceScoreUsingLastDistance(len, self.h9_opts);
                if best_score < score {
                    if i != 0 {
                        score = score.wrapping_sub(BackwardReferencePenaltyUsingLastDistance(i));
                    }
                    if best_score < score {
                        best_score = score;
                        best_len = len;
                        out.len = len;
                        out.distance = backward;
                        out.score = score;
                    }
                }
            }
        }

        best_len = best_len.max(3);
        let bank = key & (NUM_BANKS - 1);
        let bank_size = 1usize << BANK_BITS;
        let mut backward = 0usize;
        let mut delta = cur_ix.wrapping_sub(self.addr.slice()[key] as usize);
        let mut slot = self.head.slice()[key] as usize;
        for _ in 0..self.max_hops {
            let last = slot;
            backward = backward.wrapping_add(delta);
            if backward > max_backward {
                break;
            }
            let prev_ix = cur_ix.wrapping_sub(backward) & ring_buffer_mask;
            let packed = self.slots.slice()[bank * bank_size + last];
            slot = (packed >> 16) as usize;
            delta = (packed & 0xffff) as usize;
            if cur_ix_masked + best_len > ring_buffer_mask
                || prev_ix + best_len > ring_buffer_mask
                || BROTLI_UNALIGNED_LOAD32(&cur_data[best_len - 3..])
                    != BROTLI_UNALIGNED_LOAD32(&data[prev_ix + best_len - 3..])
            {
                continue;
            }
            let unbroken_len = FindMatchLengthWithLimit(&data[prev_ix..], cur_data, max_length);
            if unbroken_len >= 4 {
                let len = fix_unbroken_len(unbroken_len, prev_ix, cur_ix_masked, ring_buffer_break);
                let score = BackwardReferenceScore(len, backward, self.h9_opts);
                if best_score < score {
                    best_score = score;
                    best_len = len;
                    out.len = len;
                    out.distance = backward;
                    out.score = score;
                }
            }
        }
        self.store(data, ring_buffer_mask, cur_ix);

        let mut found = out.score != min_score;
        if !found && dictionary.is_some() {
            found = SearchInStaticDictionary(
                dictionary.unwrap(),
                dictionary_hash,
                self,
                cur_data,
                max_length,
                max_backward.wrapping_add(gap),
                max_distance,
                out,
                false,
            );
        }
        found
    }

    fn Store(&mut self, data: &[u8], mask: usize, ix: usize) {
        self.store(data, mask, ix);
    }

    fn StoreRange(&mut self, data: &[u8], mask: usize, ix_start: usize, ix_end: usize) {
        for ix in ix_start..ix_end {
            self.store(data, mask, ix);
        }
    }

    fn BulkStoreRange(&mut self, data: &[u8], mask: usize, ix_start: usize, ix_end: usize) {
        self.StoreRange(data, mask, ix_start, ix_end);
    }

    fn Prepare(&mut self, one_shot: bool, input_size: usize, data: &[u8]) -> HowPrepared {
        if self.common.is_prepared_ != 0 {
            return HowPrepared::ALREADY_PREPARED;
        }
        if one_shot && input_size <= (FORGETFUL_BUCKET_SIZE >> 6) {
            for ix in 0..input_size {
                let key = self.HashBytes(&data[ix..]);
                self.addr.slice_mut()[key] = 0xcccc_cccc;
                self.head.slice_mut()[key] = 0xcccc;
            }
        } else {
            self.addr.slice_mut().fill(0xcccc_cccc);
            self.head.slice_mut().fill(0);
        }
        self.tiny_hash.slice_mut().fill(0);
        self.free_slot_idx.slice_mut().fill(0);
        self.common.is_prepared_ = 1;
        HowPrepared::NEWLY_PREPARED
    }

    fn StitchToPreviousBlock(
        &mut self,
        num_bytes: usize,
        position: usize,
        ringbuffer: &[u8],
        ringbuffer_mask: usize,
    ) {
        StitchToPreviousBlockInternal(self, num_bytes, position, ringbuffer, ringbuffer_mask);
    }
}

fn BackwardReferenceScoreUsingLastDistance(copy_length: usize, h9_opts: H9Opts) -> u64 {
    ((h9_opts.literal_byte_score as u64) >> 2)
        .wrapping_mul(copy_length as u64)
        .wrapping_add((30u64 * 8u64).wrapping_mul(::core::mem::size_of::<u64>() as u64))
        .wrapping_add(15)
}

fn BackwardReferenceScore(
    copy_length: usize,
    backward_reference_offset: usize,
    h9_opts: H9Opts,
) -> u64 {
    (30u64 * 8u64)
        .wrapping_mul(::core::mem::size_of::<u64>() as u64)
        .wrapping_add(((h9_opts.literal_byte_score as usize) >> 2).wrapping_mul(copy_length) as u64)
        .wrapping_sub(
            (30u64).wrapping_mul(Log2FloorNonZero(backward_reference_offset as u64) as u64),
        )
}

fn Hash14(data: &[u8]) -> u32 {
    let h: u32 = BROTLI_UNALIGNED_LOAD32(data).wrapping_mul(kHashMul32);
    h >> (32i32 - 14i32)
}

fn TestStaticDictionaryItem(
    dictionary: &BrotliDictionary,
    item: usize,
    data: &[u8],
    max_length: usize,
    max_backward: usize,
    max_distance: usize,
    h9_opts: H9Opts,
    out: &mut HasherSearchResult,
) -> i32 {
    let backward: usize;

    let len: usize = item & 0x1fusize;
    let dist: usize = item >> 5;
    let offset: usize =
        (dictionary.offsets_by_length[len] as usize).wrapping_add(len.wrapping_mul(dist));
    if len > max_length {
        return 0i32;
    }
    let matchlen: usize = FindMatchLengthWithLimit(data, &dictionary.data[offset..], len);
    if matchlen.wrapping_add(kCutoffTransformsCount as usize) <= len || matchlen == 0usize {
        return 0i32;
    }
    {
        let cut: u64 = len.wrapping_sub(matchlen) as u64;
        let transform_id: usize =
            (cut << 2).wrapping_add(kCutoffTransforms >> cut.wrapping_mul(6) & 0x3f) as usize;
        backward = max_backward
            .wrapping_add(dist)
            .wrapping_add(1)
            .wrapping_add(transform_id << dictionary.size_bits_by_length[len] as i32);
    }
    if backward > max_distance {
        return 0i32;
    }
    let score: u64 = BackwardReferenceScore(matchlen, backward, h9_opts);
    if score < out.score {
        return 0i32;
    }
    out.len = matchlen;
    out.len_x_code = len ^ matchlen;
    out.distance = backward;
    out.score = score;
    1i32
}

fn SearchInStaticDictionary<HasherType: AnyHasher>(
    dictionary: &BrotliDictionary,
    dictionary_hash: &[u16],
    handle: &mut HasherType,
    data: &[u8],
    max_length: usize,
    max_backward: usize,
    max_distance: usize,
    out: &mut HasherSearchResult,
    shallow: bool,
) -> bool {
    let mut key: usize;
    let mut i: usize;
    let mut is_match_found = false;
    let opts = handle.Opts();
    let xself: &mut Struct1 = handle.GetHasherCommon();
    if xself.dict_num_matches < xself.dict_num_lookups >> 7 {
        return false;
    }
    key = (Hash14(data) << 1) as usize; //FIXME: works for any kind of hasher??
    i = 0usize;
    while i < if shallow { 1 } else { 2 } {
        {
            let item: usize = dictionary_hash[key] as usize;
            xself.dict_num_lookups = xself.dict_num_lookups.wrapping_add(1);
            if item != 0usize {
                let item_matches: i32 = TestStaticDictionaryItem(
                    dictionary,
                    item,
                    data,
                    max_length,
                    max_backward,
                    max_distance,
                    opts,
                    out,
                );
                if item_matches != 0 {
                    xself.dict_num_matches = xself.dict_num_matches.wrapping_add(1);
                    is_match_found = true;
                }
            }
        }
        i = i.wrapping_add(1);
        key = key.wrapping_add(1);
    }
    is_match_found
}

impl<Alloc: alloc::Allocator<u16> + alloc::Allocator<u32>> CloneWithAlloc<Alloc>
    for BasicHasher<H2Sub<Alloc>>
{
    fn clone_with_alloc(&self, m: &mut Alloc) -> Self {
        let mut ret = BasicHasher::<H2Sub<Alloc>> {
            GetHasherCommon: self.GetHasherCommon.clone(),
            buckets_: H2Sub {
                buckets_: allocate::<u32, _>(m, self.buckets_.buckets_.len()),
            },
            h9_opts: self.h9_opts,
        };
        ret.buckets_
            .buckets_
            .slice_mut()
            .copy_from_slice(self.buckets_.buckets_.slice());
        ret
    }
}
impl<Alloc: alloc::Allocator<u16> + alloc::Allocator<u32>> CloneWithAlloc<Alloc>
    for BasicHasher<H3Sub<Alloc>>
{
    fn clone_with_alloc(&self, m: &mut Alloc) -> Self {
        let mut ret = BasicHasher::<H3Sub<Alloc>> {
            GetHasherCommon: self.GetHasherCommon.clone(),
            buckets_: H3Sub::<Alloc> {
                buckets_: allocate::<u32, _>(m, self.buckets_.buckets_.len()),
            },
            h9_opts: self.h9_opts,
        };
        ret.buckets_
            .buckets_
            .slice_mut()
            .copy_from_slice(self.buckets_.buckets_.slice());
        ret
    }
}
impl<Alloc: alloc::Allocator<u16> + alloc::Allocator<u32>> CloneWithAlloc<Alloc>
    for BasicHasher<H4Sub<Alloc>>
{
    fn clone_with_alloc(&self, m: &mut Alloc) -> Self {
        let mut ret = BasicHasher::<H4Sub<Alloc>> {
            GetHasherCommon: self.GetHasherCommon.clone(),
            buckets_: H4Sub::<Alloc> {
                buckets_: allocate::<u32, _>(m, self.buckets_.buckets_.len()),
            },
            h9_opts: self.h9_opts,
        };
        ret.buckets_
            .buckets_
            .slice_mut()
            .copy_from_slice(self.buckets_.buckets_.slice());
        ret
    }
}
impl<Alloc: alloc::Allocator<u16> + alloc::Allocator<u32>> CloneWithAlloc<Alloc>
    for BasicHasher<H54Sub<Alloc>>
{
    fn clone_with_alloc(&self, m: &mut Alloc) -> Self {
        let mut ret = BasicHasher::<H54Sub<Alloc>> {
            GetHasherCommon: self.GetHasherCommon.clone(),
            buckets_: H54Sub::<Alloc> {
                buckets_: allocate::<u32, _>(m, self.buckets_.len()),
            },
            h9_opts: self.h9_opts,
        };
        ret.buckets_
            .buckets_
            .slice_mut()
            .copy_from_slice(self.buckets_.buckets_.slice());
        ret
    }
}
impl<Alloc: alloc::Allocator<u16> + alloc::Allocator<u32>> CloneWithAlloc<Alloc> for H9<Alloc> {
    fn clone_with_alloc(&self, m: &mut Alloc) -> Self {
        let mut num = allocate::<u16, _>(m, self.num_.len());
        num.slice_mut().copy_from_slice(self.num_.slice());
        let mut buckets = allocate::<u32, _>(m, self.buckets_.len());
        buckets.slice_mut().copy_from_slice(self.buckets_.slice());
        H9::<Alloc> {
            num_: num,
            buckets_: buckets,
            dict_search_stats_: self.dict_search_stats_.clone(),
            h9_opts: self.h9_opts,
        }
    }
}
impl<
    Alloc: alloc::Allocator<u16> + alloc::Allocator<u32>,
    Special: AdvHashSpecialization + Sized + Clone,
> CloneWithAlloc<Alloc> for AdvHasher<Special, Alloc>
{
    fn clone_with_alloc(&self, m: &mut Alloc) -> Self {
        let mut num = allocate::<u16, _>(m, self.num.len());
        num.slice_mut().copy_from_slice(self.num.slice());
        let mut buckets = allocate::<u32, _>(m, self.buckets.len());
        buckets.slice_mut().copy_from_slice(self.buckets.slice());
        AdvHasher::<Special, Alloc> {
            GetHasherCommon: self.GetHasherCommon.clone(),
            specialization: self.specialization.clone(),
            num,
            buckets,
            h9_opts: self.h9_opts,
        }
    }
}

impl<
    Alloc: alloc::Allocator<u8> + alloc::Allocator<u16> + alloc::Allocator<u32>,
    const NUM_BANKS: usize,
    const BANK_BITS: usize,
    const NUM_LAST_DISTANCES_TO_CHECK: usize,
> CloneWithAlloc<Alloc>
    for ForgetfulHasher<Alloc, NUM_BANKS, BANK_BITS, NUM_LAST_DISTANCES_TO_CHECK>
{
    fn clone_with_alloc(&self, alloc: &mut Alloc) -> Self {
        let mut addr = allocate::<u32, _>(alloc, self.addr.len());
        addr.slice_mut().copy_from_slice(self.addr.slice());
        let mut head = allocate::<u16, _>(alloc, self.head.len());
        head.slice_mut().copy_from_slice(self.head.slice());
        let mut tiny_hash = allocate::<u8, _>(alloc, self.tiny_hash.len());
        tiny_hash
            .slice_mut()
            .copy_from_slice(self.tiny_hash.slice());
        let mut slots = allocate::<u32, _>(alloc, self.slots.len());
        slots.slice_mut().copy_from_slice(self.slots.slice());
        let mut free_slot_idx = allocate::<u16, _>(alloc, self.free_slot_idx.len());
        free_slot_idx
            .slice_mut()
            .copy_from_slice(self.free_slot_idx.slice());
        Self {
            common: self.common.clone(),
            addr,
            head,
            tiny_hash,
            slots,
            free_slot_idx,
            max_hops: self.max_hops,
            h9_opts: self.h9_opts,
        }
    }
}

#[non_exhaustive]
pub enum UnionHasher<Alloc: alloc::Allocator<u8> + alloc::Allocator<u16> + alloc::Allocator<u32>> {
    Uninit,
    H2(BasicHasher<H2Sub<Alloc>>),
    H3(BasicHasher<H3Sub<Alloc>>),
    H4(BasicHasher<H4Sub<Alloc>>),
    H54(BasicHasher<H54Sub<Alloc>>),
    H5(AdvHasher<H5Sub, Alloc>),
    H5q7(AdvHasher<HQ7Sub, Alloc>),
    H5q5(AdvHasher<HQ5Sub, Alloc>),
    H6(AdvHasher<H6Sub, Alloc>),
    H58(TaggedHasher<H58Sub, Alloc>),
    H68(TaggedHasher<H68Sub, Alloc>),
    H40(H40<Alloc>),
    H41(H41<Alloc>),
    H42(H42<Alloc>),
    H9(H9<Alloc>),
    H10(H10<Alloc, H10Buckets<Alloc>, H10DefaultParams>),
}
impl<Alloc: alloc::Allocator<u8> + alloc::Allocator<u16> + alloc::Allocator<u32>>
    PartialEq<UnionHasher<Alloc>> for UnionHasher<Alloc>
{
    fn eq(&self, other: &UnionHasher<Alloc>) -> bool {
        match *self {
            UnionHasher::H2(ref hasher) => match *other {
                UnionHasher::H2(ref otherh) => *hasher == *otherh,
                _ => false,
            },
            UnionHasher::H3(ref hasher) => match *other {
                UnionHasher::H3(ref otherh) => *hasher == *otherh,
                _ => false,
            },
            UnionHasher::H4(ref hasher) => match *other {
                UnionHasher::H4(ref otherh) => *hasher == *otherh,
                _ => false,
            },
            UnionHasher::H54(ref hasher) => match *other {
                UnionHasher::H54(ref otherh) => *hasher == *otherh,
                _ => false,
            },
            UnionHasher::H5(ref hasher) => match *other {
                UnionHasher::H5(ref otherh) => *hasher == *otherh,
                _ => false,
            },
            UnionHasher::H5q7(ref hasher) => match *other {
                UnionHasher::H5q7(ref otherh) => *hasher == *otherh,
                _ => false,
            },
            UnionHasher::H5q5(ref hasher) => match *other {
                UnionHasher::H5q5(ref otherh) => *hasher == *otherh,
                _ => false,
            },
            UnionHasher::H6(ref hasher) => match *other {
                UnionHasher::H6(ref otherh) => *hasher == *otherh,
                _ => false,
            },
            UnionHasher::H58(ref hasher) => match *other {
                UnionHasher::H58(ref otherh) => *hasher == *otherh,
                _ => false,
            },
            UnionHasher::H68(ref hasher) => match *other {
                UnionHasher::H68(ref otherh) => *hasher == *otherh,
                _ => false,
            },
            UnionHasher::H40(ref hasher) => match *other {
                UnionHasher::H40(ref otherh) => *hasher == *otherh,
                _ => false,
            },
            UnionHasher::H41(ref hasher) => match *other {
                UnionHasher::H41(ref otherh) => *hasher == *otherh,
                _ => false,
            },
            UnionHasher::H42(ref hasher) => match *other {
                UnionHasher::H42(ref otherh) => *hasher == *otherh,
                _ => false,
            },
            UnionHasher::H9(ref hasher) => match *other {
                UnionHasher::H9(ref otherh) => *hasher == *otherh,
                _ => false,
            },
            UnionHasher::H10(ref hasher) => match *other {
                UnionHasher::H10(ref otherh) => *hasher == *otherh,
                _ => false,
            },
            UnionHasher::Uninit => match *other {
                UnionHasher::Uninit => true,
                _ => false,
            },
        }
    }
}
impl<Alloc: alloc::Allocator<u8> + alloc::Allocator<u16> + alloc::Allocator<u32>>
    CloneWithAlloc<Alloc> for UnionHasher<Alloc>
{
    fn clone_with_alloc(&self, m: &mut Alloc) -> Self {
        match *self {
            UnionHasher::H2(ref hasher) => UnionHasher::H2(hasher.clone_with_alloc(m)),
            UnionHasher::H3(ref hasher) => UnionHasher::H3(hasher.clone_with_alloc(m)),
            UnionHasher::H4(ref hasher) => UnionHasher::H4(hasher.clone_with_alloc(m)),
            UnionHasher::H5(ref hasher) => UnionHasher::H5(hasher.clone_with_alloc(m)),
            UnionHasher::H5q7(ref hasher) => UnionHasher::H5q7(hasher.clone_with_alloc(m)),
            UnionHasher::H5q5(ref hasher) => UnionHasher::H5q5(hasher.clone_with_alloc(m)),
            UnionHasher::H6(ref hasher) => UnionHasher::H6(hasher.clone_with_alloc(m)),
            UnionHasher::H58(ref hasher) => UnionHasher::H58(hasher.clone_with_alloc(m)),
            UnionHasher::H68(ref hasher) => UnionHasher::H68(hasher.clone_with_alloc(m)),
            UnionHasher::H40(ref hasher) => UnionHasher::H40(hasher.clone_with_alloc(m)),
            UnionHasher::H41(ref hasher) => UnionHasher::H41(hasher.clone_with_alloc(m)),
            UnionHasher::H42(ref hasher) => UnionHasher::H42(hasher.clone_with_alloc(m)),
            UnionHasher::H54(ref hasher) => UnionHasher::H54(hasher.clone_with_alloc(m)),
            UnionHasher::H9(ref hasher) => UnionHasher::H9(hasher.clone_with_alloc(m)),
            UnionHasher::H10(ref hasher) => UnionHasher::H10(hasher.clone_with_alloc(m)),
            UnionHasher::Uninit => UnionHasher::Uninit,
        }
    }
}
macro_rules! match_all_hashers_mut {
    ($xself : expr_2021, $func_call : ident, $( $args:expr_2021),*) => {
        match $xself {
     &mut UnionHasher::H2(ref mut hasher) => hasher.$func_call($($args),*),
     &mut UnionHasher::H3(ref mut hasher) => hasher.$func_call($($args),*),
     &mut UnionHasher::H4(ref mut hasher) => hasher.$func_call($($args),*),
     &mut UnionHasher::H5(ref mut hasher) => hasher.$func_call($($args),*),
     &mut UnionHasher::H5q7(ref mut hasher) => hasher.$func_call($($args),*),
     &mut UnionHasher::H5q5(ref mut hasher) => hasher.$func_call($($args),*),
     &mut UnionHasher::H6(ref mut hasher) => hasher.$func_call($($args),*),
     &mut UnionHasher::H58(ref mut hasher) => hasher.$func_call($($args),*),
     &mut UnionHasher::H68(ref mut hasher) => hasher.$func_call($($args),*),
     &mut UnionHasher::H40(ref mut hasher) => hasher.$func_call($($args),*),
     &mut UnionHasher::H41(ref mut hasher) => hasher.$func_call($($args),*),
     &mut UnionHasher::H42(ref mut hasher) => hasher.$func_call($($args),*),
     &mut UnionHasher::H54(ref mut hasher) => hasher.$func_call($($args),*),
     &mut UnionHasher::H9(ref mut hasher) => hasher.$func_call($($args),*),
     &mut UnionHasher::H10(ref mut hasher) => hasher.$func_call($($args),*),
     &mut UnionHasher::Uninit => panic!("UNINTIALIZED"),
        }
    };
}
macro_rules! match_all_hashers {
    ($xself : expr_2021, $func_call : ident, $( $args:expr_2021),*) => {
        match $xself {
     &UnionHasher::H2(ref hasher) => hasher.$func_call($($args),*),
     &UnionHasher::H3(ref hasher) => hasher.$func_call($($args),*),
     &UnionHasher::H4(ref hasher) => hasher.$func_call($($args),*),
     &UnionHasher::H5(ref hasher) => hasher.$func_call($($args),*),
     &UnionHasher::H5q7(ref hasher) => hasher.$func_call($($args),*),
     &UnionHasher::H5q5(ref hasher) => hasher.$func_call($($args),*),
     &UnionHasher::H6(ref hasher) => hasher.$func_call($($args),*),
     &UnionHasher::H58(ref hasher) => hasher.$func_call($($args),*),
     &UnionHasher::H68(ref hasher) => hasher.$func_call($($args),*),
     &UnionHasher::H40(ref hasher) => hasher.$func_call($($args),*),
     &UnionHasher::H41(ref hasher) => hasher.$func_call($($args),*),
     &UnionHasher::H42(ref hasher) => hasher.$func_call($($args),*),
     &UnionHasher::H54(ref hasher) => hasher.$func_call($($args),*),
     &UnionHasher::H9(ref hasher) => hasher.$func_call($($args),*),
     &UnionHasher::H10(ref hasher) => hasher.$func_call($($args),*),
     &UnionHasher::Uninit => panic!("UNINTIALIZED"),
        }
    };
}
impl<Alloc: alloc::Allocator<u8> + alloc::Allocator<u16> + alloc::Allocator<u32>> AnyHasher
    for UnionHasher<Alloc>
{
    fn Opts(&self) -> H9Opts {
        match_all_hashers!(self, Opts,)
    }
    fn GetHasherCommon(&mut self) -> &mut Struct1 {
        match_all_hashers_mut!(self, GetHasherCommon,)
    } /*
    fn GetH10Tree(&mut self) -> Option<&mut H10<AllocU32, H10Buckets, H10DefaultParams>> {
    return match_all_hashers_mut!(self, GetH10Tree,);
    }*/
    fn Prepare(&mut self, one_shot: bool, input_size: usize, data: &[u8]) -> HowPrepared {
        match_all_hashers_mut!(self, Prepare, one_shot, input_size, data)
    }
    fn HashBytes(&self, data: &[u8]) -> usize {
        match_all_hashers!(self, HashBytes, data)
    }
    fn HashTypeLength(&self) -> usize {
        match_all_hashers!(self, HashTypeLength,)
    }
    fn StoreLookahead(&self) -> usize {
        match_all_hashers!(self, StoreLookahead,)
    }
    fn PrepareDistanceCache(&self, distance_cache: &mut [i32]) {
        match_all_hashers!(self, PrepareDistanceCache, distance_cache)
    }
    fn StitchToPreviousBlock(
        &mut self,
        num_bytes: usize,
        position: usize,
        ringbuffer: &[u8],
        ringbuffer_mask: usize,
    ) {
        match_all_hashers_mut!(
            self,
            StitchToPreviousBlock,
            num_bytes,
            position,
            ringbuffer,
            ringbuffer_mask
        )
    }
    fn FindLongestMatch(
        &mut self,
        dictionary: Option<&BrotliDictionary>,
        dictionary_hash: &[u16],
        data: &[u8],
        ring_buffer_mask: usize,
        ring_buffer_break: Option<core::num::NonZeroUsize>,
        distance_cache: &[i32],
        cur_ix: usize,
        max_length: usize,
        max_backward: usize,
        gap: usize,
        max_distance: usize,
        out: &mut HasherSearchResult,
    ) -> bool {
        match_all_hashers_mut!(
            self,
            FindLongestMatch,
            dictionary,
            dictionary_hash,
            data,
            ring_buffer_mask,
            ring_buffer_break,
            distance_cache,
            cur_ix,
            max_length,
            max_backward,
            gap,
            max_distance,
            out
        )
    }
    fn Store(&mut self, data: &[u8], mask: usize, ix: usize) {
        match_all_hashers_mut!(self, Store, data, mask, ix)
    }
    fn StoreRange(&mut self, data: &[u8], mask: usize, ix_start: usize, ix_end: usize) {
        match_all_hashers_mut!(self, StoreRange, data, mask, ix_start, ix_end)
    }
    fn BulkStoreRange(&mut self, data: &[u8], mask: usize, ix_start: usize, ix_end: usize) {
        match_all_hashers_mut!(self, BulkStoreRange, data, mask, ix_start, ix_end)
    }
}

impl<Alloc: alloc::Allocator<u8> + alloc::Allocator<u16> + alloc::Allocator<u32>>
    UnionHasher<Alloc>
{
    pub fn free(&mut self, alloc: &mut Alloc) {
        match self {
            &mut UnionHasher::H2(ref mut hasher) => {
                <Alloc as Allocator<u32>>::free_cell(
                    alloc,
                    core::mem::take(&mut hasher.buckets_.buckets_),
                );
            }
            &mut UnionHasher::H3(ref mut hasher) => {
                <Alloc as Allocator<u32>>::free_cell(
                    alloc,
                    core::mem::take(&mut hasher.buckets_.buckets_),
                );
            }
            &mut UnionHasher::H4(ref mut hasher) => {
                <Alloc as Allocator<u32>>::free_cell(
                    alloc,
                    core::mem::take(&mut hasher.buckets_.buckets_),
                );
            }
            &mut UnionHasher::H54(ref mut hasher) => {
                <Alloc as Allocator<u32>>::free_cell(
                    alloc,
                    core::mem::take(&mut hasher.buckets_.buckets_),
                );
            }
            &mut UnionHasher::H5q7(ref mut hasher) => {
                <Alloc as Allocator<u16>>::free_cell(alloc, core::mem::take(&mut hasher.num));
                <Alloc as Allocator<u32>>::free_cell(alloc, core::mem::take(&mut hasher.buckets));
            }
            &mut UnionHasher::H5q5(ref mut hasher) => {
                <Alloc as Allocator<u16>>::free_cell(alloc, core::mem::take(&mut hasher.num));
                <Alloc as Allocator<u32>>::free_cell(alloc, core::mem::take(&mut hasher.buckets));
            }
            &mut UnionHasher::H5(ref mut hasher) => {
                <Alloc as Allocator<u16>>::free_cell(alloc, core::mem::take(&mut hasher.num));
                <Alloc as Allocator<u32>>::free_cell(alloc, core::mem::take(&mut hasher.buckets));
            }
            &mut UnionHasher::H6(ref mut hasher) => {
                <Alloc as Allocator<u16>>::free_cell(alloc, core::mem::take(&mut hasher.num));
                <Alloc as Allocator<u32>>::free_cell(alloc, core::mem::take(&mut hasher.buckets));
            }
            &mut UnionHasher::H58(ref mut hasher) => {
                <Alloc as Allocator<u16>>::free_cell(alloc, core::mem::take(&mut hasher.num));
                <Alloc as Allocator<u8>>::free_cell(alloc, core::mem::take(&mut hasher.tags));
                <Alloc as Allocator<u32>>::free_cell(alloc, core::mem::take(&mut hasher.buckets));
            }
            &mut UnionHasher::H68(ref mut hasher) => {
                <Alloc as Allocator<u16>>::free_cell(alloc, core::mem::take(&mut hasher.num));
                <Alloc as Allocator<u8>>::free_cell(alloc, core::mem::take(&mut hasher.tags));
                <Alloc as Allocator<u32>>::free_cell(alloc, core::mem::take(&mut hasher.buckets));
            }
            &mut UnionHasher::H40(ref mut hasher) => hasher.free(alloc),
            &mut UnionHasher::H41(ref mut hasher) => hasher.free(alloc),
            &mut UnionHasher::H42(ref mut hasher) => hasher.free(alloc),
            &mut UnionHasher::H9(ref mut hasher) => {
                <Alloc as Allocator<u16>>::free_cell(alloc, core::mem::take(&mut hasher.num_));
                <Alloc as Allocator<u32>>::free_cell(alloc, core::mem::take(&mut hasher.buckets_));
            }
            &mut UnionHasher::H10(ref mut hasher) => {
                hasher.free(alloc);
            }
            &mut UnionHasher::Uninit => {}
        }
        *self = UnionHasher::<Alloc>::default();
    }
}

impl<Alloc: alloc::Allocator<u8> + alloc::Allocator<u16> + alloc::Allocator<u32>> Default
    for UnionHasher<Alloc>
{
    fn default() -> Self {
        UnionHasher::Uninit
    }
}

/*UnionHasher::H2(BasicHasher {
GetHasherCommon:Struct1{params:BrotliHasherParams{
 type_:2,
 block_bits: 8,
 bucket_bits:16,
 hash_len: 4,
 num_last_distances_to_check:0},
is_prepared_:0,
dict_num_lookups:0,
dict_num_matches:0,
},
buckets_:H2Sub{
buckets_:[0;65537],
},
})
*/
fn CreateBackwardReferences<AH: AnyHasher>(
    dictionary: Option<&BrotliDictionary>,
    dictionary_hash: &[u16],
    num_bytes: usize,
    mut position: usize,
    ringbuffer: &[u8],
    ringbuffer_mask: usize,
    ringbuffer_break: Option<core::num::NonZeroUsize>,
    params: &BrotliEncoderParams,
    hasher: &mut AH,
    dist_cache: &mut [i32],
    last_insert_len: &mut usize,
    mut commands: &mut [Command],
    num_commands: &mut usize,
    num_literals: &mut usize,
) {
    let gap = 0usize;
    let max_backward_limit: usize = (1usize << params.lgwin).wrapping_sub(16);
    let mut new_commands_count: usize = 0;
    let mut insert_length: usize = *last_insert_len;
    let pos_end: usize = position.wrapping_add(num_bytes);
    let store_end: usize = if num_bytes >= hasher.StoreLookahead() {
        position
            .wrapping_add(num_bytes)
            .wrapping_sub(hasher.StoreLookahead())
            .wrapping_add(1)
    } else {
        position
    };
    let random_heuristics_window_size: usize = LiteralSpreeLengthForSparseSearch(params);
    let mut apply_random_heuristics: usize = position.wrapping_add(random_heuristics_window_size);
    let kMinScore: u64 = (30u64 * 8)
        .wrapping_mul(::core::mem::size_of::<u64>() as u64)
        .wrapping_add(100);
    hasher.PrepareDistanceCache(dist_cache);
    while position.wrapping_add(hasher.HashTypeLength()) < pos_end {
        let mut max_length: usize = pos_end.wrapping_sub(position);
        let mut max_distance: usize = min(position, max_backward_limit);
        let mut sr = HasherSearchResult {
            len: 0,
            len_x_code: 0,
            distance: 0,
            score: 0,
        };
        sr.len = 0usize;
        sr.len_x_code = 0usize;
        sr.distance = 0usize;
        sr.score = kMinScore;
        if hasher.FindLongestMatch(
            dictionary,
            dictionary_hash,
            ringbuffer,
            ringbuffer_mask,
            ringbuffer_break,
            dist_cache,
            position,
            max_length,
            max_distance,
            gap,
            params.dist.max_distance,
            &mut sr,
        ) {
            let mut delayed_backward_references_in_row: i32 = 0i32;
            max_length = max_length.wrapping_sub(1);
            loop {
                let cost_diff_lazy: u64 = 175;

                let mut sr2 = HasherSearchResult {
                    len: 0,
                    len_x_code: 0,
                    distance: 0,
                    score: 0,
                };
                sr2.len = if params.quality < 5 {
                    min(sr.len.wrapping_sub(1), max_length)
                } else {
                    0usize
                };
                sr2.len_x_code = 0usize;
                sr2.distance = 0usize;
                sr2.score = kMinScore;
                max_distance = min(position.wrapping_add(1), max_backward_limit);
                let is_match_found: bool = hasher.FindLongestMatch(
                    dictionary,
                    dictionary_hash,
                    ringbuffer,
                    ringbuffer_mask,
                    ringbuffer_break,
                    dist_cache,
                    position.wrapping_add(1),
                    max_length,
                    max_distance,
                    gap,
                    params.dist.max_distance,
                    &mut sr2,
                );
                if is_match_found && (sr2.score >= sr.score.wrapping_add(cost_diff_lazy)) {
                    position = position.wrapping_add(1);
                    insert_length = insert_length.wrapping_add(1);
                    sr = sr2;
                    delayed_backward_references_in_row += 1;
                    if delayed_backward_references_in_row < 4
                        && position.wrapping_add(hasher.HashTypeLength()) < pos_end
                    {
                        max_length = max_length.wrapping_sub(1);
                        continue;
                    }
                }
                break;
            }
            apply_random_heuristics = position
                .wrapping_add((2usize).wrapping_mul(sr.len))
                .wrapping_add(random_heuristics_window_size);
            max_distance = min(position, max_backward_limit);
            {
                let distance_code: usize =
                    ComputeDistanceCode(sr.distance, max_distance, dist_cache);
                if sr.distance <= max_distance && (distance_code > 0usize) {
                    dist_cache[3] = dist_cache[2];
                    dist_cache[2] = dist_cache[1];
                    dist_cache[1] = dist_cache[0];
                    dist_cache[0] = sr.distance as i32;
                    hasher.PrepareDistanceCache(dist_cache);
                }
                new_commands_count += 1;

                let (old, new_commands) = core::mem::take(&mut commands).split_at_mut(1);
                commands = new_commands;
                old[0].init(
                    &params.dist,
                    insert_length,
                    sr.len,
                    sr.len ^ sr.len_x_code,
                    distance_code,
                );
            }
            *num_literals = num_literals.wrapping_add(insert_length);
            insert_length = 0usize;
            hasher.StoreRange(
                ringbuffer,
                ringbuffer_mask,
                position.wrapping_add(2),
                min(position.wrapping_add(sr.len), store_end),
            );
            position = position.wrapping_add(sr.len);
        } else {
            insert_length = insert_length.wrapping_add(1);
            position = position.wrapping_add(1);

            if position > apply_random_heuristics {
                let kMargin: usize = max(hasher.StoreLookahead().wrapping_sub(1), 4);
                if position.wrapping_add(16) >= pos_end.wrapping_sub(kMargin) {
                    insert_length = insert_length.wrapping_add(pos_end - position);
                    position = pos_end;
                } else if position
                    > apply_random_heuristics
                        .wrapping_add((4usize).wrapping_mul(random_heuristics_window_size))
                {
                    hasher.Store4Vec4(ringbuffer, ringbuffer_mask, position);
                    insert_length = insert_length.wrapping_add(16);
                    position = position.wrapping_add(16);
                } else {
                    hasher.StoreEvenVec4(ringbuffer, ringbuffer_mask, position);
                    insert_length = insert_length.wrapping_add(8);
                    position = position.wrapping_add(8);
                }
            }
        }
    }
    insert_length = insert_length.wrapping_add(pos_end.wrapping_sub(position));
    *last_insert_len = insert_length;
    *num_commands = num_commands.wrapping_add(new_commands_count);
}
#[cfg_attr(feature = "hotpath", hotpath::measure)]
pub fn BrotliCreateBackwardReferences<
    Alloc: alloc::Allocator<u8>
        + alloc::Allocator<u16>
        + alloc::Allocator<u32>
        + alloc::Allocator<u64>
        + alloc::Allocator<floatX>
        + alloc::Allocator<ZopfliNode>,
>(
    alloc: &mut Alloc,
    dictionary: &BrotliDictionary,
    num_bytes: usize,
    position: usize,
    ringbuffer: &[u8],
    ringbuffer_mask: usize,
    ringbuffer_break: Option<core::num::NonZeroUsize>,
    params: &BrotliEncoderParams,
    hasher_union: &mut UnionHasher<Alloc>,
    dist_cache: &mut [i32],
    last_insert_len: &mut usize,
    commands: &mut [Command],
    num_commands: &mut usize,
    num_literals: &mut usize,
) {
    match (hasher_union) {
        &mut UnionHasher::Uninit => panic!("working with uninitialized hash map"),
        &mut UnionHasher::H10(ref mut hasher) => {
            if params.quality >= 11 {
                super::backward_references_hq::BrotliCreateHqZopfliBackwardReferences(
                    alloc,
                    if params.use_dictionary {
                        Some(dictionary)
                    } else {
                        None
                    },
                    num_bytes,
                    position,
                    ringbuffer,
                    ringbuffer_mask,
                    ringbuffer_break,
                    params,
                    hasher,
                    dist_cache,
                    last_insert_len,
                    commands,
                    num_commands,
                    num_literals,
                )
            } else {
                super::backward_references_hq::BrotliCreateZopfliBackwardReferences(
                    alloc,
                    if params.use_dictionary {
                        Some(dictionary)
                    } else {
                        None
                    },
                    num_bytes,
                    position,
                    ringbuffer,
                    ringbuffer_mask,
                    ringbuffer_break,
                    params,
                    hasher,
                    dist_cache,
                    last_insert_len,
                    commands,
                    num_commands,
                    num_literals,
                )
            }
        }
        &mut UnionHasher::H2(ref mut hasher) => CreateBackwardReferences(
            if params.use_dictionary {
                Some(dictionary)
            } else {
                None
            },
            &kStaticDictionaryHash[..],
            num_bytes,
            position,
            ringbuffer,
            ringbuffer_mask,
            ringbuffer_break,
            params,
            hasher,
            dist_cache,
            last_insert_len,
            commands,
            num_commands,
            num_literals,
        ),
        &mut UnionHasher::H3(ref mut hasher) => CreateBackwardReferences(
            if params.use_dictionary {
                Some(dictionary)
            } else {
                None
            },
            &kStaticDictionaryHash[..],
            num_bytes,
            position,
            ringbuffer,
            ringbuffer_mask,
            ringbuffer_break,
            params,
            hasher,
            dist_cache,
            last_insert_len,
            commands,
            num_commands,
            num_literals,
        ),
        &mut UnionHasher::H4(ref mut hasher) => CreateBackwardReferences(
            if params.use_dictionary {
                Some(dictionary)
            } else {
                None
            },
            &kStaticDictionaryHash[..],
            num_bytes,
            position,
            ringbuffer,
            ringbuffer_mask,
            ringbuffer_break,
            params,
            hasher,
            dist_cache,
            last_insert_len,
            commands,
            num_commands,
            num_literals,
        ),
        &mut UnionHasher::H5(ref mut hasher) => CreateBackwardReferences(
            if params.use_dictionary {
                Some(dictionary)
            } else {
                None
            },
            &kStaticDictionaryHash[..],
            num_bytes,
            position,
            ringbuffer,
            ringbuffer_mask,
            ringbuffer_break,
            params,
            hasher,
            dist_cache,
            last_insert_len,
            commands,
            num_commands,
            num_literals,
        ),
        &mut UnionHasher::H5q7(ref mut hasher) => CreateBackwardReferences(
            if params.use_dictionary {
                Some(dictionary)
            } else {
                None
            },
            &kStaticDictionaryHash[..],
            num_bytes,
            position,
            ringbuffer,
            ringbuffer_mask,
            ringbuffer_break,
            params,
            hasher,
            dist_cache,
            last_insert_len,
            commands,
            num_commands,
            num_literals,
        ),
        &mut UnionHasher::H5q5(ref mut hasher) => CreateBackwardReferences(
            if params.use_dictionary {
                Some(dictionary)
            } else {
                None
            },
            &kStaticDictionaryHash[..],
            num_bytes,
            position,
            ringbuffer,
            ringbuffer_mask,
            ringbuffer_break,
            params,
            hasher,
            dist_cache,
            last_insert_len,
            commands,
            num_commands,
            num_literals,
        ),
        &mut UnionHasher::H6(ref mut hasher) => CreateBackwardReferences(
            if params.use_dictionary {
                Some(dictionary)
            } else {
                None
            },
            &kStaticDictionaryHash[..],
            num_bytes,
            position,
            ringbuffer,
            ringbuffer_mask,
            ringbuffer_break,
            params,
            hasher,
            dist_cache,
            last_insert_len,
            commands,
            num_commands,
            num_literals,
        ),
        &mut UnionHasher::H40(ref mut hasher) => CreateBackwardReferences(
            if params.use_dictionary {
                Some(dictionary)
            } else {
                None
            },
            &kStaticDictionaryHash[..],
            num_bytes,
            position,
            ringbuffer,
            ringbuffer_mask,
            ringbuffer_break,
            params,
            hasher,
            dist_cache,
            last_insert_len,
            commands,
            num_commands,
            num_literals,
        ),
        &mut UnionHasher::H41(ref mut hasher) => CreateBackwardReferences(
            if params.use_dictionary {
                Some(dictionary)
            } else {
                None
            },
            &kStaticDictionaryHash[..],
            num_bytes,
            position,
            ringbuffer,
            ringbuffer_mask,
            ringbuffer_break,
            params,
            hasher,
            dist_cache,
            last_insert_len,
            commands,
            num_commands,
            num_literals,
        ),
        &mut UnionHasher::H42(ref mut hasher) => CreateBackwardReferences(
            if params.use_dictionary {
                Some(dictionary)
            } else {
                None
            },
            &kStaticDictionaryHash[..],
            num_bytes,
            position,
            ringbuffer,
            ringbuffer_mask,
            ringbuffer_break,
            params,
            hasher,
            dist_cache,
            last_insert_len,
            commands,
            num_commands,
            num_literals,
        ),
        &mut UnionHasher::H58(ref mut hasher) => {
            dispatch!(detect_level(), simd => {
                let mut hasher = TaggedHasherSimd::new(simd, hasher);
                CreateBackwardReferences(
                    if params.use_dictionary { Some(dictionary) } else { None },
                    &kStaticDictionaryHash[..],
                    num_bytes,
                    position,
                    ringbuffer,
                    ringbuffer_mask,
                    ringbuffer_break,
                    params,
                    &mut hasher,
                    dist_cache,
                    last_insert_len,
                    commands,
                    num_commands,
                    num_literals,
                )
            })
        }
        &mut UnionHasher::H68(ref mut hasher) => {
            dispatch!(detect_level(), simd => {
                let mut hasher = TaggedHasherSimd::new(simd, hasher);
                CreateBackwardReferences(
                    if params.use_dictionary { Some(dictionary) } else { None },
                    &kStaticDictionaryHash[..],
                    num_bytes,
                    position,
                    ringbuffer,
                    ringbuffer_mask,
                    ringbuffer_break,
                    params,
                    &mut hasher,
                    dist_cache,
                    last_insert_len,
                    commands,
                    num_commands,
                    num_literals,
                )
            })
        }
        &mut UnionHasher::H9(ref mut hasher) => CreateBackwardReferences(
            if params.use_dictionary {
                Some(dictionary)
            } else {
                None
            },
            &kStaticDictionaryHash[..],
            num_bytes,
            position,
            ringbuffer,
            ringbuffer_mask,
            ringbuffer_break,
            params,
            hasher,
            dist_cache,
            last_insert_len,
            commands,
            num_commands,
            num_literals,
        ),
        &mut UnionHasher::H54(ref mut hasher) => CreateBackwardReferences(
            if params.use_dictionary {
                Some(dictionary)
            } else {
                None
            },
            &kStaticDictionaryHash[..],
            num_bytes,
            position,
            ringbuffer,
            ringbuffer_mask,
            ringbuffer_break,
            params,
            hasher,
            dist_cache,
            last_insert_len,
            commands,
            num_commands,
            num_literals,
        ),
    }
}