/src/zlib-ng/match_tpl.h

Source
/* match_tpl.h -- find longest match template for compare256 variants
 *
 * Copyright (C) 1995-2024 Jean-loup Gailly and Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h
 *
 * Portions copyright (C) 2014-2021 Konstantin Nosov
 *  Fast-zlib optimized longest_match
 *  https://github.com/gildor2/fast_zlib
 */

#include "insert_string_p.h"

#define GOTO_NEXT_CHAIN \
    if (--chain_length && (cur_match = prev[cur_match & wmask]) > limit) \
        continue; \
    return best_len;

/* 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, uint32_t cur_match) {
    const unsigned wmask = W_MASK(s);
    unsigned int strstart = s->strstart;
    const unsigned char *window = s->window;
    const Pos *prev = s->prev;
#ifdef LONGEST_MATCH_SLOW
    const Pos *head = s->head;
#endif
    const unsigned char *scan;
    const unsigned char *mbase_start = window;
    const unsigned char *mbase_end;
    uint32_t limit;
#ifdef LONGEST_MATCH_SLOW
    uint32_t limit_base;
#endif
    uint32_t chain_length = s->max_chain_length;
    uint32_t nice_match = (uint32_t)s->nice_match;
    uint32_t best_len, offset;
    uint32_t lookahead = s->lookahead;
    uint32_t match_offset = 0;
    uint64_t scan_start;
    uint64_t scan_end;

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

#ifdef LONGEST_MATCH_SLOW
    best_len = s->prev_length ? s->prev_length : STD_MIN_MATCH-1;
    if (UNLIKELY(best_len >= lookahead))
        return lookahead;
#else
    best_len = STD_MIN_MATCH-1;
#endif

#ifdef LONGEST_MATCH_SLOW
#  ifdef LONGEST_MATCH_SLOW_ROLL
    /* Rolling-hash variant always runs the post-match offset search; the
     * compiler folds the constant away below.
     */
    const int offset_search = 1;
#  else
    /* The post-match offset search only pays off when we entered with a
     * prior best_len from lazy evaluation, so gate on it at function entry.
     */
    const int offset_search = (best_len >= STD_MIN_MATCH);
#  endif
#endif

    /* Calculate read offset which should only extend an extra byte to find the
     * next best match length. When best_len is shorter than the read width, we
     * diff the mismatched bytes instead.
     */
    offset = best_len >= sizeof(uint64_t) ? best_len - 7 : 0;

    scan = window + strstart;
    scan_start = zng_memread_8(scan);
    scan_end = zng_memread_8(scan+offset);
    mbase_end = (mbase_start+offset);

    /* Do not waste too much time if we already have a good match */
    if (UNLIKELY(best_len >= s->good_match))
        chain_length >>= 2;

    /* 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) ? (strstart - MAX_DIST(s)) : 0;
#ifdef LONGEST_MATCH_SLOW
    limit_base = limit;
    if (best_len >= STD_MIN_MATCH) {
        /* We're continuing search (lazy evaluation). Find a most distant
         * chain by hashing substrings within the match area. We cannot use
         * s->prev[strstart+1,...] immediately because those strings are not
         * yet inserted into the hash table.
         */
#  ifdef LONGEST_MATCH_SLOW_ROLL
        uint32_t hash;
        uint32_t pos;

        hash = update_hash_roll(0, scan[1]);
        hash = update_hash_roll(hash, scan[2]);

        for (uint32_t i = 3; i <= best_len; i++) {
            hash = update_hash_roll(hash, scan[i]);
            pos = head[hash];
            if (UNLIKELY(pos < cur_match)) {
                match_offset = i - 2;
                cur_match = pos;
            }
        }
#  else /* 4-byte Knuth hash, fresh lookup per offset */
        for (uint32_t i = 1; i + (WANT_MIN_MATCH - 1) <= best_len; i++) {
            uint32_t val = Z_U32_FROM_LE(zng_memread_4(scan + i));
            uint32_t hash;
            UPDATE_HASH_KNUTH(hash, val);
            uint32_t pos = head[hash];
            if (pos < cur_match) {
                match_offset = i;
                cur_match = pos;
            }
        }
#  endif

        /* Update offset-dependent variables */
        limit = limit_base+match_offset;
        if (UNLIKELY(cur_match <= limit))
            return best_len;
        mbase_start -= match_offset;
        mbase_end -= match_offset;
    }
#endif
    Assert(strstart <= s->fill_end, "need lookahead");
    for (;;) {
        if (UNLIKELY(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.
         */
        uint32_t len;
        if (best_len < sizeof(uint64_t)) {
            uint64_t cand_start = zng_memread_8(mbase_start + cur_match);
            if (scan_start != cand_start) {
                /* Peel the first candidate out of the loop. A full 8-byte match falls straight
                 * through to compare256, and single-candidate chains (barely-compressible data)
                 * run with no loop overhead. */
                uint64_t first_mask = zng_first_bytes_mask64(best_len + 1);
                uint64_t diff = scan_start ^ cand_start;
                /* A candidate beats best_len only when its first best_len+1 bytes match, i.e.
                 * those bytes of the XOR are zero. The masked test rejects without running ctz. */
                if (UNLIKELY((diff & first_mask) == 0)) {
                    len = zng_first_diff_byte64(diff);
                    goto short_match_accept;
                }
                if (--chain_length == 0 || (cur_match = prev[cur_match & wmask]) <= limit)
                    return best_len;
                cand_start = zng_memread_8(mbase_start + cur_match);
                if (scan_start != cand_start) {
                    /* Walk the remaining candidates with the chain advance kept inline. */
                    for (;;) {
                        diff = scan_start ^ cand_start;
                        if (UNLIKELY((diff & first_mask) == 0)) {
                            len = zng_first_diff_byte64(diff);
                            goto short_match_accept;
                        }
                        if (--chain_length == 0 || (cur_match = prev[cur_match & wmask]) <= limit)
                            return best_len;
                        cand_start = zng_memread_8(mbase_start + cur_match);
                        if (scan_start == cand_start)
                            break;
                    }
                }
            }
            /* All 8 bytes match, fallthrough to compare256 for the tail. */
        } else {
            /* Pre-filter the candidate on the start and end sentinels before compare256 using
             * simple 8-byte comparison since best_len >= 8. */
            for (;;) {
                /* First check the end of the candidate at best_len+1 due to the higher
                 * likelihood of a mismatch. */
                if (zng_memcmp_8(mbase_end+cur_match, &scan_end) == 0 &&
                    zng_memcmp_8(mbase_start+cur_match, &scan_start) == 0)
                    break;
                GOTO_NEXT_CHAIN;
            }
        }

        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)
short_match_accept:
        {
            uint32_t match_start = cur_match - match_offset;
            s->match_start = match_start;

            /* Do not look for better matches if the current match reaches
             * or exceeds the end of the input.
             */
            if (UNLIKELY(len >= lookahead))
                return lookahead;
            if (UNLIKELY(len >= nice_match))
                return len;

            best_len = len;

            offset = best_len >= sizeof(uint64_t) ? best_len - 7 : 0;

            scan_end = zng_memread_8(scan+offset);

#ifdef LONGEST_MATCH_SLOW
            /* Look for a better string offset */
            if (UNLIKELY(offset_search && len > STD_MIN_MATCH && match_start + len < strstart)) {
                const unsigned char *scan_endstr;
                uint32_t hash;
                uint32_t pos, next_pos;

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

                /* Walk prev[] for positions inside the match. The bound keeps
                 * the hash window within the match, so we follow chains that
                 * share bytes with the current match, not data past its end.
                 */
#  ifdef LONGEST_MATCH_SLOW_ROLL
                for (uint32_t i = 0; i <= len - STD_MIN_MATCH; i++) {
#  else /* 4-byte Knuth hash needs len - 4 bound */
                for (uint32_t i = 0; i <= len - WANT_MIN_MATCH; i++) {
#  endif
                    pos = prev[(cur_match + i) & wmask];
                    if (UNLIKELY(pos < next_pos)) {
                        /* Hash chain is more distant, use it */
                        if (UNLIKELY(pos <= limit_base + i))
                            return best_len;
                        next_pos = pos;
                        match_offset = i;
                    }
                }
                /* Switch cur_match to next_pos chain */
                cur_match = next_pos;

                /* Try hash head at a window covering the tail of the current
                 * match to find chains that extend farther back. The window
                 * width differs per variant: 3 bytes for rolling, 4 for Knuth.
                 */
#  ifdef LONGEST_MATCH_SLOW_ROLL
                scan_endstr = scan + len - (STD_MIN_MATCH-1);

                hash = update_hash_roll(0, scan_endstr[0]);
                hash = update_hash_roll(hash, scan_endstr[1]);
                hash = update_hash_roll(hash, scan_endstr[2]);

                pos = head[hash];
                if (UNLIKELY(pos < cur_match)) {
                    match_offset = len - (STD_MIN_MATCH-1);
                    if (pos <= limit_base + match_offset)
                        return best_len;
                    cur_match = pos;
                }
#  else
                scan_endstr = scan + len - WANT_MIN_MATCH;
                uint32_t val = Z_U32_FROM_LE(zng_memread_4(scan_endstr));
                UPDATE_HASH_KNUTH(hash, val);

                pos = head[hash];
                if (pos < cur_match) {
                    match_offset = len - WANT_MIN_MATCH;
                    if (pos <= limit_base + match_offset)
                        return best_len;
                    cur_match = pos;
                }
#  endif

                /* Update offset-dependent variables */
                limit = limit_base+match_offset;
                mbase_start = window-match_offset;
                mbase_end = (mbase_start+offset);
                continue;
            }
#endif
            mbase_end = (mbase_start+offset);
        }
        GOTO_NEXT_CHAIN;
    }
    return best_len;
}

#undef LONGEST_MATCH_SLOW
#undef LONGEST_MATCH_SLOW_ROLL
#undef LONGEST_MATCH

Coverage Report

Created: 2026-11-12 06:21