use crate::deflate::{Pos, State, MIN_LOOKAHEAD, STD_MAX_MATCH, STD_MIN_MATCH};

const EARLY_EXIT_TRIGGER_LEVEL: i8 = 5;

/// Find the (length, offset) in the window of the longest match for the string
/// at offset cur_match
pub fn longest_match(state: &crate::deflate::State, cur_match: u16) -> (usize, u16) {
    longest_match_help::<false>(state, cur_match)
}

pub fn longest_match_slow(state: &crate::deflate::State, cur_match: u16) -> (usize, u16) {
    longest_match_help::<true>(state, cur_match)
}

fn longest_match_help<const SLOW: bool>(
    state: &crate::deflate::State,
    mut cur_match: u16,
) -> (usize, u16) {
    let mut match_start = state.match_start;

    let strstart = state.strstart;
    let wmask = state.w_mask;
    let window = state.window.filled();
    let scan = &window[strstart..];
    let mut limit: Pos;
    let limit_base: Pos;
    let early_exit: bool;

    let mut chain_length: u16;
    let mut best_len: usize;

    let lookahead = state.lookahead;
    let mut match_offset = 0;

    macro_rules! goto_next_in_chain {
        () => {
            chain_length -= 1;
            if chain_length > 0 {
                cur_match = state.prev.as_slice()[cur_match as usize & wmask];

                if cur_match > limit {
                    continue;
                }
            }

            return (best_len, match_start);
        };
    }

    // The code is optimized for STD_MAX_MATCH-2 multiple of 16.
    assert_eq!(STD_MAX_MATCH, 258, "Code too clever");

    // length of the previous match (if any), hence <= STD_MAX_MATCH
    best_len = if state.prev_length > 0 {
        state.prev_length as usize
    } else {
        STD_MIN_MATCH - 1
    };

    // Calculate read offset which should only extend an extra byte to find the next best match length.
    let mut offset = best_len - 1;
    if best_len >= core::mem::size_of::<u32>() {
        offset -= 2;
        if best_len >= core::mem::size_of::<u64>() {
            offset -= 4;
        }
    }

    let mut mbase_start = window.as_ptr();
    let mut mbase_end = window[offset..].as_ptr();

    // Don't waste too much time by following a chain if we already have a good match
    chain_length = state.max_chain_length;
    if best_len >= state.good_match as usize {
        chain_length >>= 2;
    }
    let nice_match = state.nice_match;

    // Stop when cur_match becomes <= limit. To simplify the code,
    // we prevent matches with the string of window index 0
    limit = strstart.saturating_sub(state.max_dist()) as Pos;

    // look for a better string offset
    if SLOW {
        limit_base = limit;

        if best_len >= STD_MIN_MATCH {
            /* We're continuing search (lazy evaluation). */
            let mut pos: Pos;

            // Find a most distant chain starting from scan with index=1 (index=0 corresponds
            // to cur_match). We cannot use s->prev[strstart+1,...] immediately, because
            // these strings are not yet inserted into the hash table.
            let Some([_cur_match, scan1, scan2, scanrest @ ..]) = scan.get(..best_len + 1) else {
                panic!("invalid scan");
            };

            let mut hash = 0;
            hash = state.update_hash(hash, *scan1 as u32);
            hash = state.update_hash(hash, *scan2 as u32);

            for (i, b) in scanrest.iter().enumerate() {
                hash = state.update_hash(hash, *b as u32);

                /* If we're starting with best_len >= 3, we can use offset search. */
                pos = state.head.as_slice()[hash as usize];
                if pos < cur_match {
                    match_offset = (i + 1) as Pos;
                    cur_match = pos;
                }
            }

            /* Update offset-dependent variables */
            limit = limit_base + match_offset;
            if cur_match <= limit {
                return break_matching(state, best_len, match_start);
            }

            mbase_start = mbase_start.wrapping_sub(match_offset as usize);
            mbase_end = mbase_end.wrapping_sub(match_offset as usize);
        }

        early_exit = false;
    } else {
        // must initialize this variable
        limit_base = 0;
        early_exit = state.level < EARLY_EXIT_TRIGGER_LEVEL;
    }

    let scan_start = window[strstart..].as_ptr();
    let mut scan_end = window[strstart + offset..].as_ptr();

    assert!(
        strstart <= state.window_size.saturating_sub(MIN_LOOKAHEAD),
        "need lookahead"
    );

    loop {
        if cur_match as usize >= strstart {
            break;
        }

        // Skip to next match if the match length cannot increase or if the match length is
        // less than 2. Note that the checks below for insufficient lookahead only occur
        // occasionally for performance reasons.
        // Therefore uninitialized memory will be accessed and conditional jumps will be made
        // that depend on those values. However the length of the match is limited to the
        // lookahead, so the output of deflate is not affected by the uninitialized values.

        /// # Safety
        ///
        /// The two pointers must be valid for reads of N bytes.
        #[inline(always)]
        unsafe fn memcmp_n_ptr<const N: usize>(src0: *const u8, src1: *const u8) -> bool {
            unsafe {
                let src0_cmp = core::ptr::read(src0 as *const [u8; N]);
                let src1_cmp = core::ptr::read(src1 as *const [u8; N]);
                src0_cmp == src1_cmp
            }
        }

        /// # Safety
        ///
        /// scan_start and scan_end must be valid for reads of N bytes. mbase_end and mbase_start
        /// must be valid for reads of N + cur_match bytes.
        #[inline(always)]
        unsafe fn is_match<const N: usize>(
            cur_match: u16,
            mbase_start: *const u8,
            mbase_end: *const u8,
            scan_start: *const u8,
            scan_end: *const u8,
        ) -> bool {
            let be = mbase_end.wrapping_add(cur_match as usize);
            let bs = mbase_start.wrapping_add(cur_match as usize);
            unsafe { memcmp_n_ptr::<N>(be, scan_end) && memcmp_n_ptr::<N>(bs, scan_start) }
        }

        // first, do a quick check on the start and end bytes. Go to the next item in the chain if
        // these bytes don't match.
        // SAFETY: we read up to 8 bytes in this block.
        // Note that scan_start >= mbase_start and scan_end >= mbase_end.
        // the surrounding loop breaks before cur_match gets past strstart, which is bounded by
        // `window_size - 258 + 3 + 1` (`window_size - MIN_LOOKAHEAD`).
        //
        // With 262 bytes of space at the end, and 8 byte reads of scan_start is always in-bounds.
        //
        // scan_end is a bit trickier: it reads at a bounded offset from scan_start:
        //
        // - >= 8: scan_end is bounded by `258 - (4 + 2 + 1)`, so an 8-byte read is in-bounds
        // - >= 4: scan_end is bounded by `258 - (2 + 1)`, so a 4-byte read is in-bounds
        // - >= 2: scan_end is bounded by `258 - 1`, so a 2-byte read is in-bounds
        let mut len = 0;
        unsafe {
            if best_len < core::mem::size_of::<u64>() {
                let scan_val = u64::from_ne_bytes(
                    core::slice::from_raw_parts(scan_start, 8).try_into().unwrap());
                loop {
                    let bs = mbase_start.wrapping_add(cur_match as usize);
                    let match_val = u64::from_ne_bytes(
                        core::slice::from_raw_parts(bs, 8).try_into().unwrap());
                    let cmp = scan_val ^ match_val;
                    if cmp == 0 {
                        // The first 8 bytes all matched. Additional scanning will be needed
                        // (the compare256 call below) to determine the full match length.
                        break;
                    }
                    // Compute the number of leading bytes that match.
                    let cmp_len = cmp.to_le().trailing_zeros() as usize / 8;
                    if cmp_len > best_len {
                        // The match is fully contained within the 8 bytes just compared,
                        // so we know the match length without needing to do the more
                        // expensive compare256 operation.
                        len = cmp_len;
                        break;
                    }
                    goto_next_in_chain!();
                }
            } else {
                loop {
                    if is_match::<8>(cur_match, mbase_start, mbase_end, scan_start, scan_end) {
                        break;
                    }

                    goto_next_in_chain!();
                }
            }
        }

        // we know that there is at least some match. Now count how many bytes really match
        if len == 0 {
            len = {
                // SAFETY: cur_match is bounded by window_size - MIN_LOOKAHEAD, where MIN_LOOKAHEAD
                // is 258 + 3 + 1, so 258-byte reads of mbase_start are in-bounds.
                let src1 = unsafe {
                    core::slice::from_raw_parts(mbase_start.wrapping_add(cur_match as usize + 2), 256)
                };

                crate::deflate::compare256::compare256_slice(&scan[2..], src1) + 2
            };
        }

        assert!(
            scan.as_ptr() as usize + len <= window.as_ptr() as usize + (state.window_size - 1),
            "wild scan"
        );

        if len > best_len {
            match_start = cur_match - match_offset;

            /* Do not look for matches beyond the end of the input. */
            if len > lookahead {
                return (lookahead, match_start);
            }
            best_len = len;
            if best_len >= nice_match as usize {
                return (best_len, match_start);
            }

            offset = best_len - 1;
            if best_len >= core::mem::size_of::<u32>() {
                offset -= 2;
                if best_len >= core::mem::size_of::<u64>() {
                    offset -= 4;
                }
            }

            scan_end = window[strstart + offset..].as_ptr();

            // Look for a better string offset
            if SLOW && len > STD_MIN_MATCH && match_start as usize + len < strstart {
                let mut pos: Pos;
                // uint32_t i, hash;
                // unsigned char *scan_endstr;

                /* Go back to offset 0 */
                cur_match -= match_offset;
                match_offset = 0;
                let mut next_pos = cur_match;

                for i in 0..=len - STD_MIN_MATCH {
                    pos = state.prev.as_slice()[(cur_match as usize + i) & wmask];
                    if pos < next_pos {
                        /* Hash chain is more distant, use it */
                        if pos <= limit_base + i as Pos {
                            return break_matching(state, best_len, match_start);
                        }
                        next_pos = pos;
                        match_offset = i as Pos;
                    }
                }
                /* Switch cur_match to next_pos chain */
                cur_match = next_pos;

                /* Try hash head at len-(STD_MIN_MATCH-1) position to see if we could get
                 * a better cur_match at the end of string. Using (STD_MIN_MATCH-1) lets
                 * us include one more byte into hash - the byte which will be checked
                 * in main loop now, and which allows to grow match by 1.
                 */
                let [scan0, scan1, scan2, ..] = scan[len - (STD_MIN_MATCH + 1)..] else {
                    panic!("index out of bounds");
                };

                let mut hash = 0;
                hash = state.update_hash(hash, scan0 as u32);
                hash = state.update_hash(hash, scan1 as u32);
                hash = state.update_hash(hash, scan2 as u32);

                pos = state.head.as_slice()[hash as usize];
                if pos < cur_match {
                    match_offset = (len - (STD_MIN_MATCH + 1)) as Pos;
                    if pos <= limit_base + match_offset {
                        return break_matching(state, best_len, match_start);
                    }
                    cur_match = pos;
                }

                /* Update offset-dependent variables */
                limit = limit_base + match_offset;
                mbase_start = window.as_ptr().wrapping_sub(match_offset as usize);
                mbase_end = mbase_start.wrapping_add(offset);
                continue;
            }

            mbase_end = mbase_start.wrapping_add(offset);
        } else if !SLOW && early_exit {
            // The probability of finding a match later if we here is pretty low, so for
            // performance it's best to outright stop here for the lower compression levels
            break;
        }

        goto_next_in_chain!();
    }

    (best_len, match_start)
}

fn break_matching(state: &State, best_len: usize, match_start: u16) -> (usize, u16) {
    (Ord::min(best_len, state.lookahead), match_start)
}