#include "zbuild.h"

#include "deflate.h"

#include "functable.h"

#ifndef MATCH_TPL_H

#define MATCH_TPL_H

#ifdef UNALIGNED_OK

#  ifdef UNALIGNED64_OK

typedef uint64_t        bestcmp_t;

#  else

typedef uint32_t        bestcmp_t;

#  endif

#else

typedef uint8_t         bestcmp_t;

#endif

#define EARLY_EXIT_TRIGGER_LEVEL 5

#endif

/* Set match_start to the longest match starting at the given string and

 * return its length. Matches shorter or equal to prev_length are discarded,

 * in which case the result is equal to prev_length and match_start is garbage.

 *

 * IN assertions: cur_match is the head of the hash chain for the current

 * string (strstart) and its distance is <= MAX_DIST, and prev_length >=1

 * OUT assertion: the match length is not greater than s->lookahead

 */

Z_INTERNAL uint32_t LONGEST_MATCH(deflate_state *const s, Pos cur_match) {

    unsigned int strstart = s->strstart;

    const unsigned wmask = s->w_mask;

    unsigned char *window = s->window;

    unsigned char *scan = window + strstart;

    Z_REGISTER unsigned char *mbase_start = window;

    Z_REGISTER unsigned char *mbase_end;

    const Pos *prev = s->prev;

    Pos limit;

    int32_t early_exit;

    uint32_t chain_length, nice_match, best_len, offset;

    uint32_t lookahead = s->lookahead;

    bestcmp_t scan_end;

#ifndef UNALIGNED_OK

    bestcmp_t scan_end0;

#else

    bestcmp_t scan_start;

#endif

#define GOTO_NEXT_CHAIN \

    if (--chain_length && (cur_match = prev[cur_match & wmask]) > limit) \

        continue; \

    return best_len;

    /* The code is optimized for MAX_MATCH-2 multiple of 16. */

    Assert(MAX_MATCH == 258, "Code too clever");

    best_len = s->prev_length ? s->prev_length : 1;

    /* Calculate read offset which should only extend an extra byte

     * to find the next best match length.

     */

    offset = best_len-1;

#ifdef UNALIGNED_OK

    if (best_len >= sizeof(uint32_t)) {

        offset -= 2;

#ifdef UNALIGNED64_OK

        if (best_len >= sizeof(uint64_t))

            offset -= 4;

#endif

    }

#endif

    scan_end   = *(bestcmp_t *)(scan+offset);

#ifndef UNALIGNED_OK

    scan_end0  = *(bestcmp_t *)(scan+offset+1);

#else

    scan_start = *(bestcmp_t *)(scan);

#endif

    mbase_end  = (mbase_start+offset);

    /* Do not waste too much time if we already have a good match */

    chain_length = s->max_chain_length;

    early_exit = s->level < EARLY_EXIT_TRIGGER_LEVEL;

    if (best_len >= s->good_match)

        chain_length >>= 2;

    nice_match = (uint32_t)s->nice_match;

    /* Stop when cur_match becomes <= limit. To simplify the code,

     * we prevent matches with the string of window index 0

     */

    limit = strstart > MAX_DIST(s) ? (Pos)(strstart - MAX_DIST(s)) : 0;

    Assert((unsigned long)strstart <= s->window_size - MIN_LOOKAHEAD, "need lookahead");

    for (;;) {

        if (cur_match >= 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.

         */

#ifdef UNALIGNED_OK

        if (best_len < sizeof(uint32_t)) {

            for (;;) {

                if (*(uint16_t *)(mbase_end+cur_match) == (uint16_t)scan_end &&

                    *(uint16_t *)(mbase_start+cur_match) == (uint16_t)scan_start)

                    break;

                GOTO_NEXT_CHAIN;

            }

#  ifdef UNALIGNED64_OK

        } else if (best_len >= sizeof(uint64_t)) {

            for (;;) {

                if (*(uint64_t *)(mbase_end+cur_match) == (uint64_t)scan_end &&

                    *(uint64_t *)(mbase_start+cur_match) == (uint64_t)scan_start)

                    break;

                GOTO_NEXT_CHAIN;

            }

#  endif

        } else {

            for (;;) {

                if (*(uint32_t *)(mbase_end+cur_match) == (uint32_t)scan_end &&

                    *(uint32_t *)(mbase_start+cur_match) == (uint32_t)scan_start)

                    break;

                GOTO_NEXT_CHAIN;

            }

        }

#else

        for (;;) {

            if (mbase_end[cur_match] == scan_end && mbase_end[cur_match+1] == scan_end0 &&

                mbase_start[cur_match] == scan[0] && mbase_start[cur_match+1] == scan[1])

                break;

            GOTO_NEXT_CHAIN;

        }

#endif

        uint32_t len = COMPARE256(scan+2, mbase_start+cur_match+2) + 2;

        Assert(scan+len <= window+(unsigned)(s->window_size-1), "wild scan");

        if (len > best_len) {

            s->match_start = cur_match;

            /* Do not look for matches beyond the end of the input. */

            if (len > lookahead)

                return lookahead;

            best_len = len;

            if (best_len >= nice_match)

                return best_len;

            offset = best_len-1;

#ifdef UNALIGNED_OK

            if (best_len >= sizeof(uint32_t)) {

                offset -= 2;

#ifdef UNALIGNED64_OK

                if (best_len >= sizeof(uint64_t))

                    offset -= 4;

#endif

            }

#endif

            scan_end = *(bestcmp_t *)(scan+offset);

#ifndef UNALIGNED_OK

            scan_end0 = *(bestcmp_t *)(scan+offset+1);

#endif

            mbase_end = (mbase_start+offset);

        } else if (UNLIKELY(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_CHAIN;

    }

    return best_len;

}

#undef LONGEST_MATCH

#undef COMPARE256

#undef COMPARE258