Coverage Report

Created: 2026-11-19 07:17

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/src/c-blosc2/_deps/zlib_ng-src/match_tpl.h
Line
Count
Source
1
/* match_tpl.h -- find longest match template for compare256 variants
2
 *
3
 * Copyright (C) 1995-2024 Jean-loup Gailly and Mark Adler
4
 * For conditions of distribution and use, see copyright notice in zlib.h
5
 *
6
 * Portions copyright (C) 2014-2021 Konstantin Nosov
7
 *  Fast-zlib optimized longest_match
8
 *  https://github.com/gildor2/fast_zlib
9
 */
10
11
#ifndef MATCH_TPL_H
12
#define MATCH_TPL_H
13
14
3.15M
#define EARLY_EXIT_TRIGGER_LEVEL 5
15
16
#endif
17
18
/* Set match_start to the longest match starting at the given string and
19
 * return its length. Matches shorter or equal to prev_length are discarded,
20
 * in which case the result is equal to prev_length and match_start is garbage.
21
 *
22
 * IN assertions: cur_match is the head of the hash chain for the current
23
 * string (strstart) and its distance is <= MAX_DIST, and prev_length >=1
24
 * OUT assertion: the match length is not greater than s->lookahead
25
 *
26
 * The LONGEST_MATCH_SLOW variant spends more time to attempt to find longer
27
 * matches once a match has already been found.
28
 */
29
5.21M
Z_INTERNAL uint32_t LONGEST_MATCH(deflate_state *const s, Pos cur_match) {
30
5.21M
    unsigned int strstart = s->strstart;
31
5.21M
    const unsigned wmask = s->w_mask;
32
5.21M
    unsigned char *window = s->window;
33
5.21M
    unsigned char *scan = window + strstart;
34
5.21M
    Z_REGISTER unsigned char *mbase_start = window;
35
5.21M
    Z_REGISTER unsigned char *mbase_end;
36
5.21M
    const Pos *prev = s->prev;
37
5.21M
    Pos limit;
38
#ifdef LONGEST_MATCH_SLOW
39
    Pos limit_base;
40
#else
41
    int32_t early_exit;
42
#endif
43
5.21M
    uint32_t chain_length, nice_match, best_len, offset;
44
5.21M
    uint32_t lookahead = s->lookahead;
45
5.21M
    Pos match_offset = 0;
46
5.21M
    uint64_t scan_start;
47
5.21M
    uint64_t scan_end;
48
49
5.21M
#define GOTO_NEXT_CHAIN \
50
62.5M
    if (--chain_length && (cur_match = prev[cur_match & wmask]) > limit) \
51
58.0M
        continue; \
52
4.50M
    return best_len;
53
54
    /* The code is optimized for STD_MAX_MATCH-2 multiple of 16. */
55
5.21M
    Assert(STD_MAX_MATCH == 258, "Code too clever");
56
57
5.21M
    best_len = s->prev_length ? s->prev_length : STD_MIN_MATCH-1;
58
59
    /* Calculate read offset which should only extend an extra byte
60
     * to find the next best match length.
61
     */
62
5.21M
    offset = best_len-1;
63
5.21M
    if (best_len >= sizeof(uint32_t)) {
64
531k
        offset -= 2;
65
531k
        if (best_len >= sizeof(uint64_t))
66
131k
            offset -= 4;
67
531k
    }
68
69
5.21M
    scan_start = zng_memread_8(scan);
70
5.21M
    scan_end = zng_memread_8(scan+offset);
71
5.21M
    mbase_end  = (mbase_start+offset);
72
73
    /* Do not waste too much time if we already have a good match */
74
5.21M
    chain_length = s->max_chain_length;
75
5.21M
    if (best_len >= s->good_match)
76
48.7k
        chain_length >>= 2;
77
5.21M
    nice_match = (uint32_t)s->nice_match;
78
79
    /* Stop when cur_match becomes <= limit. To simplify the code,
80
     * we prevent matches with the string of window index 0
81
     */
82
5.21M
    limit = strstart > MAX_DIST(s) ? (Pos)(strstart - MAX_DIST(s)) : 0;
83
#ifdef LONGEST_MATCH_SLOW
84
    limit_base = limit;
85
2.06M
    if (best_len >= STD_MIN_MATCH) {
86
        /* We're continuing search (lazy evaluation). */
87
485k
        uint32_t i, hash;
88
485k
        Pos pos;
89
90
        /* Find a most distant chain starting from scan with index=1 (index=0 corresponds
91
         * to cur_match). We cannot use s->prev[strstart+1,...] immediately, because
92
         * these strings are not yet inserted into the hash table.
93
         */
94
        hash = s->update_hash(0, scan[1]);
95
        hash = s->update_hash(hash, scan[2]);
96
97
4.77M
        for (i = 3; i <= best_len; i++) {
98
4.29M
            hash = s->update_hash(hash, scan[i]);
99
100
            /* If we're starting with best_len >= 3, we can use offset search. */
101
4.29M
            pos = s->head[hash];
102
4.29M
            if (pos < cur_match) {
103
461k
                match_offset = (Pos)(i - 2);
104
461k
                cur_match = pos;
105
461k
            }
106
4.29M
        }
107
108
        /* Update offset-dependent variables */
109
485k
        limit = limit_base+match_offset;
110
485k
        if (cur_match <= limit)
111
323k
            goto break_matching;
112
162k
        mbase_start -= match_offset;
113
162k
        mbase_end -= match_offset;
114
162k
    }
115
#else
116
3.15M
    early_exit = s->level < EARLY_EXIT_TRIGGER_LEVEL;
117
#endif
118
1.74M
    Assert((unsigned long)strstart <= s->window_size - MIN_LOOKAHEAD, "need lookahead");
119
9.04M
    for (;;) {
120
9.04M
        if (cur_match >= strstart)
121
0
            break;
122
123
        /* Skip to next match if the match length cannot increase or if the match length is
124
         * less than 2. Note that the checks below for insufficient lookahead only occur
125
         * occasionally for performance reasons.
126
         * Therefore uninitialized memory will be accessed and conditional jumps will be made
127
         * that depend on those values. However the length of the match is limited to the
128
         * lookahead, so the output of deflate is not affected by the uninitialized values.
129
         */
130
9.04M
        if (best_len < sizeof(uint32_t)) {
131
16.6M
            for (;;) {
132
16.6M
                if (zng_memcmp_2(mbase_end+cur_match, &scan_end) == 0 &&
133
3.77M
                    zng_memcmp_2(mbase_start+cur_match, &scan_start) == 0)
134
1.83M
                    break;
135
14.8M
                GOTO_NEXT_CHAIN;
136
14.8M
            }
137
4.91M
        } else if (best_len >= sizeof(uint64_t)) {
138
26.2M
            for (;;) {
139
26.2M
                if (zng_memcmp_8(mbase_end+cur_match, &scan_end) == 0 &&
140
3.21M
                    zng_memcmp_8(mbase_start+cur_match, &scan_start) == 0)
141
2.64M
                    break;
142
23.5M
                GOTO_NEXT_CHAIN;
143
23.5M
            }
144
2.91M
        } else {
145
21.0M
            for (;;) {
146
21.0M
                if (zng_memcmp_4(mbase_end+cur_match, &scan_end) == 0 &&
147
841k
                    zng_memcmp_4(mbase_start+cur_match, &scan_start) == 0)
148
606k
                    break;
149
20.4M
                GOTO_NEXT_CHAIN;
150
20.4M
            }
151
1.22M
        }
152
5.08M
        uint32_t len = COMPARE256(scan+2, mbase_start+cur_match+2) + 2;
153
5.08M
        Assert(scan+len <= window+(unsigned)(s->window_size-1), "wild scan");
154
155
5.08M
        if (len > best_len) {
156
4.12M
            uint32_t match_start = cur_match - match_offset;
157
4.12M
            s->match_start = match_start;
158
159
            /* Do not look for better matches if the current match reaches
160
             * or exceeds the end of the input.
161
             */
162
4.12M
            if (len >= lookahead)
163
21.3k
                return lookahead;
164
4.10M
            best_len = len;
165
4.10M
            if (best_len >= nice_match)
166
255k
                return best_len;
167
168
3.85M
            offset = best_len-1;
169
3.85M
            if (best_len >= sizeof(uint32_t)) {
170
3.48M
                offset -= 2;
171
3.48M
                if (best_len >= sizeof(uint64_t))
172
2.00M
                    offset -= 4;
173
3.48M
            }
174
175
3.85M
            scan_end = zng_memread_8(scan+offset);
176
177
#ifdef LONGEST_MATCH_SLOW
178
            /* Look for a better string offset */
179
1.51M
            if (UNLIKELY(len > STD_MIN_MATCH && match_start + len < strstart)) {
180
1.09M
                Pos pos, next_pos;
181
1.09M
                uint32_t i, hash;
182
1.09M
                unsigned char *scan_endstr;
183
184
                /* Go back to offset 0 */
185
                cur_match -= match_offset;
186
                match_offset = 0;
187
                next_pos = cur_match;
188
44.1M
                for (i = 0; i <= len - STD_MIN_MATCH; i++) {
189
43.1M
                    pos = prev[(cur_match + i) & wmask];
190
43.1M
                    if (pos < next_pos) {
191
                        /* Hash chain is more distant, use it */
192
1.24M
                        if (pos <= limit_base + i)
193
112k
                            goto break_matching;
194
1.13M
                        next_pos = pos;
195
1.13M
                        match_offset = (Pos)i;
196
1.13M
                    }
197
43.1M
                }
198
                /* Switch cur_match to next_pos chain */
199
979k
                cur_match = next_pos;
200
201
                /* Try hash head at len-(STD_MIN_MATCH-1) position to see if we could get
202
                 * a better cur_match at the end of string. Using (STD_MIN_MATCH-1) lets
203
                 * us include one more byte into hash - the byte which will be checked
204
                 * in main loop now, and which allows to grow match by 1.
205
                 */
206
979k
                scan_endstr = scan + len - (STD_MIN_MATCH+1);
207
208
979k
                hash = s->update_hash(0, scan_endstr[0]);
209
979k
                hash = s->update_hash(hash, scan_endstr[1]);
210
979k
                hash = s->update_hash(hash, scan_endstr[2]);
211
212
979k
                pos = s->head[hash];
213
979k
                if (pos < cur_match) {
214
0
                    match_offset = (Pos)(len - (STD_MIN_MATCH+1));
215
0
                    if (pos <= limit_base + match_offset)
216
0
                        goto break_matching;
217
0
                    cur_match = pos;
218
0
                }
219
220
                /* Update offset-dependent variables */
221
979k
                limit = limit_base+match_offset;
222
979k
                mbase_start = window-match_offset;
223
979k
                mbase_end = (mbase_start+offset);
224
979k
                continue;
225
979k
            }
226
418k
#endif
227
418k
            mbase_end = (mbase_start+offset);
228
418k
        }
229
#ifndef LONGEST_MATCH_SLOW
230
378k
        else if (UNLIKELY(early_exit)) {
231
            /* The probability of finding a match later if we here is pretty low, so for
232
             * performance it's best to outright stop here for the lower compression levels
233
             */
234
343
            break;
235
343
        }
236
2.71M
#endif
237
3.71M
        GOTO_NEXT_CHAIN;
238
3.71M
    }
239
343
    return best_len;
240
241
#ifdef LONGEST_MATCH_SLOW
242
436k
break_matching:
243
244
436k
    if (best_len < s->lookahead)
245
432k
        return best_len;
246
247
3.26k
    return s->lookahead;
248
#endif
249
436k
}
Unexecuted instantiation: longest_match_sse2
Unexecuted instantiation: longest_match_slow_sse2
longest_match_avx2
Line
Count
Source
29
3.15M
Z_INTERNAL uint32_t LONGEST_MATCH(deflate_state *const s, Pos cur_match) {
30
3.15M
    unsigned int strstart = s->strstart;
31
3.15M
    const unsigned wmask = s->w_mask;
32
3.15M
    unsigned char *window = s->window;
33
3.15M
    unsigned char *scan = window + strstart;
34
3.15M
    Z_REGISTER unsigned char *mbase_start = window;
35
3.15M
    Z_REGISTER unsigned char *mbase_end;
36
3.15M
    const Pos *prev = s->prev;
37
3.15M
    Pos limit;
38
#ifdef LONGEST_MATCH_SLOW
39
    Pos limit_base;
40
#else
41
3.15M
    int32_t early_exit;
42
3.15M
#endif
43
3.15M
    uint32_t chain_length, nice_match, best_len, offset;
44
3.15M
    uint32_t lookahead = s->lookahead;
45
3.15M
    Pos match_offset = 0;
46
3.15M
    uint64_t scan_start;
47
3.15M
    uint64_t scan_end;
48
49
3.15M
#define GOTO_NEXT_CHAIN \
50
3.15M
    if (--chain_length && (cur_match = prev[cur_match & wmask]) > limit) \
51
3.15M
        continue; \
52
3.15M
    return best_len;
53
54
    /* The code is optimized for STD_MAX_MATCH-2 multiple of 16. */
55
3.15M
    Assert(STD_MAX_MATCH == 258, "Code too clever");
56
57
3.15M
    best_len = s->prev_length ? s->prev_length : STD_MIN_MATCH-1;
58
59
    /* Calculate read offset which should only extend an extra byte
60
     * to find the next best match length.
61
     */
62
3.15M
    offset = best_len-1;
63
3.15M
    if (best_len >= sizeof(uint32_t)) {
64
95.0k
        offset -= 2;
65
95.0k
        if (best_len >= sizeof(uint64_t))
66
43.9k
            offset -= 4;
67
95.0k
    }
68
69
3.15M
    scan_start = zng_memread_8(scan);
70
3.15M
    scan_end = zng_memread_8(scan+offset);
71
3.15M
    mbase_end  = (mbase_start+offset);
72
73
    /* Do not waste too much time if we already have a good match */
74
3.15M
    chain_length = s->max_chain_length;
75
3.15M
    if (best_len >= s->good_match)
76
23.0k
        chain_length >>= 2;
77
3.15M
    nice_match = (uint32_t)s->nice_match;
78
79
    /* Stop when cur_match becomes <= limit. To simplify the code,
80
     * we prevent matches with the string of window index 0
81
     */
82
3.15M
    limit = strstart > MAX_DIST(s) ? (Pos)(strstart - MAX_DIST(s)) : 0;
83
#ifdef LONGEST_MATCH_SLOW
84
    limit_base = limit;
85
    if (best_len >= STD_MIN_MATCH) {
86
        /* We're continuing search (lazy evaluation). */
87
        uint32_t i, hash;
88
        Pos pos;
89
90
        /* Find a most distant chain starting from scan with index=1 (index=0 corresponds
91
         * to cur_match). We cannot use s->prev[strstart+1,...] immediately, because
92
         * these strings are not yet inserted into the hash table.
93
         */
94
        hash = s->update_hash(0, scan[1]);
95
        hash = s->update_hash(hash, scan[2]);
96
97
        for (i = 3; i <= best_len; i++) {
98
            hash = s->update_hash(hash, scan[i]);
99
100
            /* If we're starting with best_len >= 3, we can use offset search. */
101
            pos = s->head[hash];
102
            if (pos < cur_match) {
103
                match_offset = (Pos)(i - 2);
104
                cur_match = pos;
105
            }
106
        }
107
108
        /* Update offset-dependent variables */
109
        limit = limit_base+match_offset;
110
        if (cur_match <= limit)
111
            goto break_matching;
112
        mbase_start -= match_offset;
113
        mbase_end -= match_offset;
114
    }
115
#else
116
3.15M
    early_exit = s->level < EARLY_EXIT_TRIGGER_LEVEL;
117
3.15M
#endif
118
3.15M
    Assert((unsigned long)strstart <= s->window_size - MIN_LOOKAHEAD, "need lookahead");
119
5.44M
    for (;;) {
120
5.44M
        if (cur_match >= strstart)
121
0
            break;
122
123
        /* Skip to next match if the match length cannot increase or if the match length is
124
         * less than 2. Note that the checks below for insufficient lookahead only occur
125
         * occasionally for performance reasons.
126
         * Therefore uninitialized memory will be accessed and conditional jumps will be made
127
         * that depend on those values. However the length of the match is limited to the
128
         * lookahead, so the output of deflate is not affected by the uninitialized values.
129
         */
130
5.44M
        if (best_len < sizeof(uint32_t)) {
131
3.14M
            for (;;) {
132
3.14M
                if (zng_memcmp_2(mbase_end+cur_match, &scan_end) == 0 &&
133
1.07M
                    zng_memcmp_2(mbase_start+cur_match, &scan_start) == 0)
134
1.07M
                    break;
135
2.06M
                GOTO_NEXT_CHAIN;
136
2.06M
            }
137
3.05M
        } else if (best_len >= sizeof(uint64_t)) {
138
13.9M
            for (;;) {
139
13.9M
                if (zng_memcmp_8(mbase_end+cur_match, &scan_end) == 0 &&
140
1.74M
                    zng_memcmp_8(mbase_start+cur_match, &scan_start) == 0)
141
1.49M
                    break;
142
12.4M
                GOTO_NEXT_CHAIN;
143
12.4M
            }
144
1.67M
        } else {
145
3.95M
            for (;;) {
146
3.95M
                if (zng_memcmp_4(mbase_end+cur_match, &scan_end) == 0 &&
147
396k
                    zng_memcmp_4(mbase_start+cur_match, &scan_start) == 0)
148
395k
                    break;
149
3.55M
                GOTO_NEXT_CHAIN;
150
3.55M
            }
151
713k
        }
152
2.96M
        uint32_t len = COMPARE256(scan+2, mbase_start+cur_match+2) + 2;
153
2.96M
        Assert(scan+len <= window+(unsigned)(s->window_size-1), "wild scan");
154
155
2.96M
        if (len > best_len) {
156
2.58M
            uint32_t match_start = cur_match - match_offset;
157
2.58M
            s->match_start = match_start;
158
159
            /* Do not look for better matches if the current match reaches
160
             * or exceeds the end of the input.
161
             */
162
2.58M
            if (len >= lookahead)
163
14.8k
                return lookahead;
164
2.57M
            best_len = len;
165
2.57M
            if (best_len >= nice_match)
166
232k
                return best_len;
167
168
2.34M
            offset = best_len-1;
169
2.34M
            if (best_len >= sizeof(uint32_t)) {
170
2.34M
                offset -= 2;
171
2.34M
                if (best_len >= sizeof(uint64_t))
172
1.35M
                    offset -= 4;
173
2.34M
            }
174
175
2.34M
            scan_end = zng_memread_8(scan+offset);
176
177
#ifdef LONGEST_MATCH_SLOW
178
            /* Look for a better string offset */
179
            if (UNLIKELY(len > STD_MIN_MATCH && match_start + len < strstart)) {
180
                Pos pos, next_pos;
181
                uint32_t i, hash;
182
                unsigned char *scan_endstr;
183
184
                /* Go back to offset 0 */
185
                cur_match -= match_offset;
186
                match_offset = 0;
187
                next_pos = cur_match;
188
                for (i = 0; i <= len - STD_MIN_MATCH; i++) {
189
                    pos = prev[(cur_match + i) & wmask];
190
                    if (pos < next_pos) {
191
                        /* Hash chain is more distant, use it */
192
                        if (pos <= limit_base + i)
193
                            goto break_matching;
194
                        next_pos = pos;
195
                        match_offset = (Pos)i;
196
                    }
197
                }
198
                /* Switch cur_match to next_pos chain */
199
                cur_match = next_pos;
200
201
                /* Try hash head at len-(STD_MIN_MATCH-1) position to see if we could get
202
                 * a better cur_match at the end of string. Using (STD_MIN_MATCH-1) lets
203
                 * us include one more byte into hash - the byte which will be checked
204
                 * in main loop now, and which allows to grow match by 1.
205
                 */
206
                scan_endstr = scan + len - (STD_MIN_MATCH+1);
207
208
                hash = s->update_hash(0, scan_endstr[0]);
209
                hash = s->update_hash(hash, scan_endstr[1]);
210
                hash = s->update_hash(hash, scan_endstr[2]);
211
212
                pos = s->head[hash];
213
                if (pos < cur_match) {
214
                    match_offset = (Pos)(len - (STD_MIN_MATCH+1));
215
                    if (pos <= limit_base + match_offset)
216
                        goto break_matching;
217
                    cur_match = pos;
218
                }
219
220
                /* Update offset-dependent variables */
221
                limit = limit_base+match_offset;
222
                mbase_start = window-match_offset;
223
                mbase_end = (mbase_start+offset);
224
                continue;
225
            }
226
#endif
227
2.34M
            mbase_end = (mbase_start+offset);
228
2.34M
        }
229
378k
#ifndef LONGEST_MATCH_SLOW
230
378k
        else if (UNLIKELY(early_exit)) {
231
            /* The probability of finding a match later if we here is pretty low, so for
232
             * performance it's best to outright stop here for the lower compression levels
233
             */
234
343
            break;
235
343
        }
236
2.71M
#endif
237
2.71M
        GOTO_NEXT_CHAIN;
238
2.71M
    }
239
343
    return best_len;
240
241
#ifdef LONGEST_MATCH_SLOW
242
break_matching:
243
244
    if (best_len < s->lookahead)
245
        return best_len;
246
247
    return s->lookahead;
248
#endif
249
3.15M
}
longest_match_slow_avx2
Line
Count
Source
29
2.06M
Z_INTERNAL uint32_t LONGEST_MATCH(deflate_state *const s, Pos cur_match) {
30
2.06M
    unsigned int strstart = s->strstart;
31
2.06M
    const unsigned wmask = s->w_mask;
32
2.06M
    unsigned char *window = s->window;
33
2.06M
    unsigned char *scan = window + strstart;
34
2.06M
    Z_REGISTER unsigned char *mbase_start = window;
35
2.06M
    Z_REGISTER unsigned char *mbase_end;
36
2.06M
    const Pos *prev = s->prev;
37
2.06M
    Pos limit;
38
2.06M
#ifdef LONGEST_MATCH_SLOW
39
2.06M
    Pos limit_base;
40
#else
41
    int32_t early_exit;
42
#endif
43
2.06M
    uint32_t chain_length, nice_match, best_len, offset;
44
2.06M
    uint32_t lookahead = s->lookahead;
45
2.06M
    Pos match_offset = 0;
46
2.06M
    uint64_t scan_start;
47
2.06M
    uint64_t scan_end;
48
49
2.06M
#define GOTO_NEXT_CHAIN \
50
2.06M
    if (--chain_length && (cur_match = prev[cur_match & wmask]) > limit) \
51
2.06M
        continue; \
52
2.06M
    return best_len;
53
54
    /* The code is optimized for STD_MAX_MATCH-2 multiple of 16. */
55
2.06M
    Assert(STD_MAX_MATCH == 258, "Code too clever");
56
57
2.06M
    best_len = s->prev_length ? s->prev_length : STD_MIN_MATCH-1;
58
59
    /* Calculate read offset which should only extend an extra byte
60
     * to find the next best match length.
61
     */
62
2.06M
    offset = best_len-1;
63
2.06M
    if (best_len >= sizeof(uint32_t)) {
64
436k
        offset -= 2;
65
436k
        if (best_len >= sizeof(uint64_t))
66
87.4k
            offset -= 4;
67
436k
    }
68
69
2.06M
    scan_start = zng_memread_8(scan);
70
2.06M
    scan_end = zng_memread_8(scan+offset);
71
2.06M
    mbase_end  = (mbase_start+offset);
72
73
    /* Do not waste too much time if we already have a good match */
74
2.06M
    chain_length = s->max_chain_length;
75
2.06M
    if (best_len >= s->good_match)
76
25.6k
        chain_length >>= 2;
77
2.06M
    nice_match = (uint32_t)s->nice_match;
78
79
    /* Stop when cur_match becomes <= limit. To simplify the code,
80
     * we prevent matches with the string of window index 0
81
     */
82
2.06M
    limit = strstart > MAX_DIST(s) ? (Pos)(strstart - MAX_DIST(s)) : 0;
83
2.06M
#ifdef LONGEST_MATCH_SLOW
84
2.06M
    limit_base = limit;
85
2.06M
    if (best_len >= STD_MIN_MATCH) {
86
        /* We're continuing search (lazy evaluation). */
87
485k
        uint32_t i, hash;
88
485k
        Pos pos;
89
90
        /* Find a most distant chain starting from scan with index=1 (index=0 corresponds
91
         * to cur_match). We cannot use s->prev[strstart+1,...] immediately, because
92
         * these strings are not yet inserted into the hash table.
93
         */
94
485k
        hash = s->update_hash(0, scan[1]);
95
485k
        hash = s->update_hash(hash, scan[2]);
96
97
4.77M
        for (i = 3; i <= best_len; i++) {
98
4.29M
            hash = s->update_hash(hash, scan[i]);
99
100
            /* If we're starting with best_len >= 3, we can use offset search. */
101
4.29M
            pos = s->head[hash];
102
4.29M
            if (pos < cur_match) {
103
461k
                match_offset = (Pos)(i - 2);
104
461k
                cur_match = pos;
105
461k
            }
106
4.29M
        }
107
108
        /* Update offset-dependent variables */
109
485k
        limit = limit_base+match_offset;
110
485k
        if (cur_match <= limit)
111
323k
            goto break_matching;
112
162k
        mbase_start -= match_offset;
113
162k
        mbase_end -= match_offset;
114
162k
    }
115
#else
116
    early_exit = s->level < EARLY_EXIT_TRIGGER_LEVEL;
117
#endif
118
1.74M
    Assert((unsigned long)strstart <= s->window_size - MIN_LOOKAHEAD, "need lookahead");
119
3.59M
    for (;;) {
120
3.59M
        if (cur_match >= strstart)
121
0
            break;
122
123
        /* Skip to next match if the match length cannot increase or if the match length is
124
         * less than 2. Note that the checks below for insufficient lookahead only occur
125
         * occasionally for performance reasons.
126
         * Therefore uninitialized memory will be accessed and conditional jumps will be made
127
         * that depend on those values. However the length of the match is limited to the
128
         * lookahead, so the output of deflate is not affected by the uninitialized values.
129
         */
130
3.59M
        if (best_len < sizeof(uint32_t)) {
131
13.5M
            for (;;) {
132
13.5M
                if (zng_memcmp_2(mbase_end+cur_match, &scan_end) == 0 &&
133
2.69M
                    zng_memcmp_2(mbase_start+cur_match, &scan_start) == 0)
134
758k
                    break;
135
12.7M
                GOTO_NEXT_CHAIN;
136
12.7M
            }
137
1.85M
        } else if (best_len >= sizeof(uint64_t)) {
138
12.3M
            for (;;) {
139
12.3M
                if (zng_memcmp_8(mbase_end+cur_match, &scan_end) == 0 &&
140
1.46M
                    zng_memcmp_8(mbase_start+cur_match, &scan_start) == 0)
141
1.15M
                    break;
142
11.1M
                GOTO_NEXT_CHAIN;
143
11.1M
            }
144
1.23M
        } else {
145
17.1M
            for (;;) {
146
17.1M
                if (zng_memcmp_4(mbase_end+cur_match, &scan_end) == 0 &&
147
445k
                    zng_memcmp_4(mbase_start+cur_match, &scan_start) == 0)
148
210k
                    break;
149
16.8M
                GOTO_NEXT_CHAIN;
150
16.8M
            }
151
506k
        }
152
2.12M
        uint32_t len = COMPARE256(scan+2, mbase_start+cur_match+2) + 2;
153
2.12M
        Assert(scan+len <= window+(unsigned)(s->window_size-1), "wild scan");
154
155
2.12M
        if (len > best_len) {
156
1.54M
            uint32_t match_start = cur_match - match_offset;
157
1.54M
            s->match_start = match_start;
158
159
            /* Do not look for better matches if the current match reaches
160
             * or exceeds the end of the input.
161
             */
162
1.54M
            if (len >= lookahead)
163
6.51k
                return lookahead;
164
1.53M
            best_len = len;
165
1.53M
            if (best_len >= nice_match)
166
23.2k
                return best_len;
167
168
1.51M
            offset = best_len-1;
169
1.51M
            if (best_len >= sizeof(uint32_t)) {
170
1.14M
                offset -= 2;
171
1.14M
                if (best_len >= sizeof(uint64_t))
172
648k
                    offset -= 4;
173
1.14M
            }
174
175
1.51M
            scan_end = zng_memread_8(scan+offset);
176
177
1.51M
#ifdef LONGEST_MATCH_SLOW
178
            /* Look for a better string offset */
179
1.51M
            if (UNLIKELY(len > STD_MIN_MATCH && match_start + len < strstart)) {
180
1.09M
                Pos pos, next_pos;
181
1.09M
                uint32_t i, hash;
182
1.09M
                unsigned char *scan_endstr;
183
184
                /* Go back to offset 0 */
185
1.09M
                cur_match -= match_offset;
186
1.09M
                match_offset = 0;
187
1.09M
                next_pos = cur_match;
188
44.1M
                for (i = 0; i <= len - STD_MIN_MATCH; i++) {
189
43.1M
                    pos = prev[(cur_match + i) & wmask];
190
43.1M
                    if (pos < next_pos) {
191
                        /* Hash chain is more distant, use it */
192
1.24M
                        if (pos <= limit_base + i)
193
112k
                            goto break_matching;
194
1.13M
                        next_pos = pos;
195
1.13M
                        match_offset = (Pos)i;
196
1.13M
                    }
197
43.1M
                }
198
                /* Switch cur_match to next_pos chain */
199
979k
                cur_match = next_pos;
200
201
                /* Try hash head at len-(STD_MIN_MATCH-1) position to see if we could get
202
                 * a better cur_match at the end of string. Using (STD_MIN_MATCH-1) lets
203
                 * us include one more byte into hash - the byte which will be checked
204
                 * in main loop now, and which allows to grow match by 1.
205
                 */
206
979k
                scan_endstr = scan + len - (STD_MIN_MATCH+1);
207
208
979k
                hash = s->update_hash(0, scan_endstr[0]);
209
979k
                hash = s->update_hash(hash, scan_endstr[1]);
210
979k
                hash = s->update_hash(hash, scan_endstr[2]);
211
212
979k
                pos = s->head[hash];
213
979k
                if (pos < cur_match) {
214
0
                    match_offset = (Pos)(len - (STD_MIN_MATCH+1));
215
0
                    if (pos <= limit_base + match_offset)
216
0
                        goto break_matching;
217
0
                    cur_match = pos;
218
0
                }
219
220
                /* Update offset-dependent variables */
221
979k
                limit = limit_base+match_offset;
222
979k
                mbase_start = window-match_offset;
223
979k
                mbase_end = (mbase_start+offset);
224
979k
                continue;
225
979k
            }
226
418k
#endif
227
418k
            mbase_end = (mbase_start+offset);
228
418k
        }
229
#ifndef LONGEST_MATCH_SLOW
230
        else if (UNLIKELY(early_exit)) {
231
            /* The probability of finding a match later if we here is pretty low, so for
232
             * performance it's best to outright stop here for the lower compression levels
233
             */
234
            break;
235
        }
236
#endif
237
1.00M
        GOTO_NEXT_CHAIN;
238
1.00M
    }
239
0
    return best_len;
240
241
0
#ifdef LONGEST_MATCH_SLOW
242
436k
break_matching:
243
244
436k
    if (best_len < s->lookahead)
245
432k
        return best_len;
246
247
3.26k
    return s->lookahead;
248
436k
#endif
249
436k
}
Unexecuted instantiation: longest_match_avx512
Unexecuted instantiation: longest_match_slow_avx512
250
251
#undef LONGEST_MATCH_SLOW
252
#undef LONGEST_MATCH