/* deflate_fast.c -- compress data using the fast strategy of deflation algorithm

 *

 * Copyright (C) 1995-2024 Jean-loup Gailly and Mark Adler

 * For conditions of distribution and use, see copyright notice in zlib.h

 */

#include "zbuild.h"

#include "zmemory.h"

#include "deflate.h"

#include "deflate_p.h"

#include "functable.h"

#include "insert_string_p.h"

/* ===========================================================================

 * Compress as much as possible from the input stream, return the current

 * block state.

 * This function does not perform lazy evaluation of matches and inserts

 * new strings in the dictionary only for unmatched strings or for short

 * matches. It is used only for the fast compression options.

 */

Z_INTERNAL block_state deflate_fast(deflate_state *s, int flush) {

    unsigned char *window = s->window;

    uint32_t max_inserts = MAX(2, s->max_insert_count); // spread insert requires min 2

    int bflush = 0;       /* set if current block must be flushed */

    uint32_t match_len = 0;

    for (;;) {

        uint8_t lc;

        /* Make sure that we always have enough lookahead, except

         * at the end of the input file. We need STD_MAX_MATCH bytes

         * for the next match, plus WANT_MIN_MATCH bytes to insert the

         * string following the next match.

         */

        if (UNLIKELY(s->lookahead < MIN_LOOKAHEAD)) {

            PREFIX(fill_window)(s);

            if (UNLIKELY(s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH)) {

                return need_more;

            }

            if (UNLIKELY(s->lookahead == 0))

                break; /* flush the current block */

        }

        /* Insert the string window[strstart .. strstart+2] in the

         * dictionary, and set hash_head to the head of the hash chain:

         */

        if (LIKELY(s->lookahead >= WANT_MIN_MATCH)) {

            uint32_t str_val = Z_U32_FROM_LE(zng_memread_4(window + s->strstart));

            uint32_t hash_head = insert_knuth_val(s, s->strstart, str_val);

            int64_t dist = (int64_t)s->strstart - hash_head;

            lc = (uint8_t)str_val;

            /* Find the longest match.

             * At this point we have always match length < WANT_MIN_MATCH

             */

            if (dist <= MAX_DIST(s) && dist > 0 && hash_head != 0) {

                /* To simplify the code, we prevent matches with the string

                 * of window index 0 (in particular we have to avoid a match

                 * of the string with itself at the start of the input file).

                 */

                match_len = FUNCTABLE_CALL(longest_match)(s, (uint32_t)hash_head);

                /* longest_match() sets match_start */

            }

        } else {

            lc = window[s->strstart];

        }

        if (match_len >= WANT_MIN_MATCH) {

            Assert(s->strstart <= UINT16_MAX, "strstart should fit in uint16_t");

            Assert(s->match_start <= UINT16_MAX, "match_start should fit in uint16_t");

            check_match(s, s->strstart, s->match_start, match_len);

            const uint32_t cont_dist = s->strstart - s->match_start;

            bflush = zng_tr_tally_dist(s, cont_dist, match_len - STD_MIN_MATCH);

            s->lookahead -= match_len;

            /* Insert new strings in the hash table using a stepped hashing function, saving time */

            if (LIKELY(s->lookahead >= WANT_MIN_MATCH)) {

                insert_knuth_spread_static(s, window, s->strstart + 1, match_len - 1 , max_inserts);

            } else {

                insert_knuth(s, window, s->strstart + 2 - STD_MIN_MATCH + match_len);

                /* If lookahead < WANT_MIN_MATCH, ins_h is garbage, but it does not

                 * matter since it will be recomputed at next deflate call.

                 */

            }

            s->strstart += match_len;

            /* A max-length match might continue: keep emitting continuations at the same

             * distance without a full search as long as possible. */

            if (UNLIKELY(match_len == STD_MAX_MATCH && s->lookahead >= MIN_LOOKAHEAD)) {

                for (;;) {

                    // Check for continuing match

                    uint32_t cont_len = max_match_continues(window, s->strstart, cont_dist);

                    if (UNLIKELY(cont_len < 8))

                        break;

                    check_match(s, s->strstart, s->strstart - cont_dist, cont_len);

                    // Insert match

                    insert_knuth_spread_static(s, window, s->strstart, cont_len, max_inserts);

                    s->strstart += cont_len;

                    s->lookahead -= cont_len;

                    // Emit match

                    bflush |= zng_tr_tally_dist(s, cont_dist, cont_len - STD_MIN_MATCH);

                    if (UNLIKELY(bflush)) {

                        FLUSH_BLOCK(s, window, 0);

                        bflush = 0;

                    }

                    if (UNLIKELY(s->lookahead < MIN_LOOKAHEAD)) {

                        break; /* not enough lookahead, return to the main loop */

                    }

                }

            }

            match_len = 0;

        } else {

            /* No match, output a literal byte */

            bflush = zng_tr_tally_lit(s, lc);

            s->lookahead--;

            s->strstart++;

        }

        if (UNLIKELY(bflush))

            FLUSH_BLOCK(s, window, 0);

    }

    s->insert = s->strstart < (STD_MIN_MATCH - 1) ? s->strstart : (STD_MIN_MATCH - 1);

    if (UNLIKELY(flush == Z_FINISH)) {

        FLUSH_BLOCK(s, window, 1);

        return finish_done;

    }

    if (UNLIKELY(s->sym_next))

        FLUSH_BLOCK(s, window, 0);

    return block_done;

}