/src/zlib-ng/deflate_medium.c

Source (jump to first uncovered line)
/* deflate_medium.c -- The deflate_medium deflate strategy
 *
 * Copyright (C) 2013 Intel Corporation. All rights reserved.
 * Authors:
 *  Arjan van de Ven    <arjan@linux.intel.com>
 *
 * For conditions of distribution and use, see copyright notice in zlib.h
 */
#ifndef NO_MEDIUM_STRATEGY
#include "zbuild.h"
#include "deflate.h"
#include "deflate_p.h"
#include "functable.h"

struct match {
    uint16_t match_start;
    uint16_t match_length;
    uint16_t strstart;
    uint16_t orgstart;
};

static int emit_match(deflate_state *s, struct match match) {
    int bflush = 0;

    /* matches that are not long enough we need to emit as literals */
    if (match.match_length < WANT_MIN_MATCH) {
        while (match.match_length) {
            bflush += zng_tr_tally_lit(s, s->window[match.strstart]);
            s->lookahead--;
            match.strstart++;
            match.match_length--;
        }
        return bflush;
    }

    check_match(s, match.strstart, match.match_start, match.match_length);

    bflush += zng_tr_tally_dist(s, match.strstart - match.match_start, match.match_length - STD_MIN_MATCH);

    s->lookahead -= match.match_length;
    return bflush;
}

static void insert_match(deflate_state *s, struct match match) {
    if (UNLIKELY(s->lookahead <= (unsigned int)(match.match_length + WANT_MIN_MATCH)))
        return;

    /* string at strstart already in table */
    match.strstart++;
    match.match_length--;

    /* matches that are not long enough we need to emit as literals */
    if (LIKELY(match.match_length < WANT_MIN_MATCH - 1)) {
        if (UNLIKELY(match.match_length > 0)) {
            if (match.strstart >= match.orgstart) {
                if (match.strstart + match.match_length - 1 >= match.orgstart) {
                    insert_string(s, match.strstart, match.match_length);
                } else {
                    insert_string(s, match.strstart, match.orgstart - match.strstart + 1);
                }
                match.strstart += match.match_length;
                match.match_length = 0;
            }
        }
        return;
    }

    /* Insert into hash table. */
    if (LIKELY(match.strstart >= match.orgstart)) {
        if (LIKELY(match.strstart + match.match_length - 1 >= match.orgstart)) {
            insert_string(s, match.strstart, match.match_length);
        } else {
            insert_string(s, match.strstart, match.orgstart - match.strstart + 1);
        }
    } else if (match.orgstart < match.strstart + match.match_length) {
        insert_string(s, match.orgstart, match.strstart + match.match_length - match.orgstart);
    }
    match.strstart += match.match_length;
    match.match_length = 0;
}

static void fizzle_matches(deflate_state *s, struct match *current, struct match *next) {
    Pos limit;
    unsigned char *match, *orig;
    int changed = 0;
    struct match c, n;
    /* step zero: sanity checks */

    if (current->match_length <= 1)
        return;

    if (UNLIKELY(current->match_length > 1 + next->match_start))
        return;

    if (UNLIKELY(current->match_length > 1 + next->strstart))
        return;

    match = s->window - current->match_length + 1 + next->match_start;
    orig  = s->window - current->match_length + 1 + next->strstart;

    /* quick exit check.. if this fails then don't bother with anything else */
    if (LIKELY(*match != *orig))
        return;

    c = *current;
    n = *next;

    /* step one: try to move the "next" match to the left as much as possible */
    limit = next->strstart > MAX_DIST(s) ? next->strstart - (Pos)MAX_DIST(s) : 0;

    match = s->window + n.match_start - 1;
    orig = s->window + n.strstart - 1;

    while (*match == *orig) {
        if (UNLIKELY(c.match_length < 1))
            break;
        if (UNLIKELY(n.strstart <= limit))
            break;
        if (UNLIKELY(n.match_length >= 256))
            break;
        if (UNLIKELY(n.match_start <= 1))
            break;

        n.strstart--;
        n.match_start--;
        n.match_length++;
        c.match_length--;
        match--;
        orig--;
        changed++;
    }

    if (!changed)
        return;

    if (c.match_length <= 1 && n.match_length != 2) {
        n.orgstart++;
        *current = c;
        *next = n;
    } else {
        return;
    }
}

Z_INTERNAL block_state deflate_medium(deflate_state *s, int flush) {
    /* Align the first struct to start on a new cacheline, this allows us to fit both structs in one cacheline */
    ALIGNED_(16) struct match current_match;
                 struct match next_match;

    /* For levels below 5, don't check the next position for a better match */
    int early_exit = s->level < 5;

    memset(&current_match, 0, sizeof(struct match));
    memset(&next_match, 0, sizeof(struct match));

    for (;;) {
        Pos hash_head = 0;    /* head of the hash chain */
        int bflush = 0;       /* set if current block must be flushed */
        int64_t dist;

        /* 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 current_match.
         */
        if (s->lookahead < MIN_LOOKAHEAD) {
            PREFIX(fill_window)(s);
            if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
                return need_more;
            }
            if (UNLIKELY(s->lookahead == 0))
                break; /* flush the current block */
            next_match.match_length = 0;
        }

        /* Insert the string window[strstart .. strstart+2] in the
         * dictionary, and set hash_head to the head of the hash chain:
         */

        /* If we already have a future match from a previous round, just use that */
        if (!early_exit && next_match.match_length > 0) {
            current_match = next_match;
            next_match.match_length = 0;
        } else {
            hash_head = 0;
            if (s->lookahead >= WANT_MIN_MATCH) {
                hash_head = quick_insert_string(s, s->strstart);
            }

            current_match.strstart = (uint16_t)s->strstart;
            current_match.orgstart = current_match.strstart;

            /* Find the longest match, discarding those <= prev_length.
             * At this point we have always match_length < WANT_MIN_MATCH
             */

            dist = (int64_t)s->strstart - hash_head;
            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).
                 */
                current_match.match_length = (uint16_t)FUNCTABLE_CALL(longest_match)(s, hash_head);
                current_match.match_start = (uint16_t)s->match_start;
                if (UNLIKELY(current_match.match_length < WANT_MIN_MATCH))
                    current_match.match_length = 1;
                if (UNLIKELY(current_match.match_start >= current_match.strstart)) {
                    /* this can happen due to some restarts */
                    current_match.match_length = 1;
                }
            } else {
                /* Set up the match to be a 1 byte literal */
                current_match.match_start = 0;
                current_match.match_length = 1;
            }
        }

        insert_match(s, current_match);

        /* now, look ahead one */
        if (LIKELY(!early_exit && s->lookahead > MIN_LOOKAHEAD && (uint32_t)(current_match.strstart + current_match.match_length) < (s->window_size - MIN_LOOKAHEAD))) {
            s->strstart = current_match.strstart + current_match.match_length;
            hash_head = quick_insert_string(s, s->strstart);

            next_match.strstart = (uint16_t)s->strstart;
            next_match.orgstart = next_match.strstart;

            /* Find the longest match, discarding those <= prev_length.
             * At this point we have always match_length < WANT_MIN_MATCH
             */

            dist = (int64_t)s->strstart - hash_head;
            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).
                 */
                next_match.match_length = (uint16_t)FUNCTABLE_CALL(longest_match)(s, hash_head);
                next_match.match_start = (uint16_t)s->match_start;
                if (UNLIKELY(next_match.match_start >= next_match.strstart)) {
                    /* this can happen due to some restarts */
                    next_match.match_length = 1;
                }
                if (next_match.match_length < WANT_MIN_MATCH)
                    next_match.match_length = 1;
                else
                    fizzle_matches(s, &current_match, &next_match);
            } else {
                /* Set up the match to be a 1 byte literal */
                next_match.match_start = 0;
                next_match.match_length = 1;
            }

            s->strstart = current_match.strstart;
        } else {
            next_match.match_length = 0;
        }

        /* now emit the current match */
        bflush = emit_match(s, current_match);

        /* move the "cursor" forward */
        s->strstart += current_match.match_length;

        if (UNLIKELY(bflush))
            FLUSH_BLOCK(s, 0);
    }
    s->insert = s->strstart < (STD_MIN_MATCH - 1) ? s->strstart : (STD_MIN_MATCH - 1);
    if (flush == Z_FINISH) {
        FLUSH_BLOCK(s, 1);
        return finish_done;
    }
    if (UNLIKELY(s->sym_next))
        FLUSH_BLOCK(s, 0);

    return block_done;
}
#endif

Coverage Report

Created: 2025-07-11 06:15

Line	Count	Source (jump to first uncovered line)
1		/* deflate_medium.c -- The deflate_medium deflate strategy
2		*
3		* Copyright (C) 2013 Intel Corporation. All rights reserved.
4		* Authors:
5		* Arjan van de Ven <arjan@linux.intel.com>
6		*
7		* For conditions of distribution and use, see copyright notice in zlib.h
8		*/
9		#ifndef NO_MEDIUM_STRATEGY
10		#include "zbuild.h"
11		#include "deflate.h"
12		#include "deflate_p.h"
13		#include "functable.h"
14
15		struct match {
16		uint16_t match_start;
17		uint16_t match_length;
18		uint16_t strstart;
19		uint16_t orgstart;
20		};
21
22	1.92M	static int emit_match(deflate_state *s, struct match match) {
23	1.92M	int bflush = 0;
24
25		/* matches that are not long enough we need to emit as literals */
26	1.92M	if (match.match_length < WANT_MIN_MATCH) {
27	3.40M	while (match.match_length) {
28	1.70M	bflush += zng_tr_tally_lit(s, s->window[match.strstart]);
29	1.70M	s->lookahead--;
30	1.70M	match.strstart++;
31	1.70M	match.match_length--;
32	1.70M	}
33	1.70M	return bflush;
34	1.70M	}
35
36	215k	check_match(s, match.strstart, match.match_start, match.match_length);
37
38	215k	bflush += zng_tr_tally_dist(s, match.strstart - match.match_start, match.match_length - STD_MIN_MATCH);
39
40	215k	s->lookahead -= match.match_length;
41	215k	return bflush;
42	1.92M	}
43
44	1.92M	static void insert_match(deflate_state *s, struct match match) {
45	1.92M	if (UNLIKELY(s->lookahead <= (unsigned int)(match.match_length + WANT_MIN_MATCH)))
46	4.16k	return;
47
48		/* string at strstart already in table */
49	1.91M	match.strstart++;
50	1.91M	match.match_length--;
51
52		/* matches that are not long enough we need to emit as literals */
53	1.91M	if (LIKELY(match.match_length < WANT_MIN_MATCH - 1)) {
54	1.69M	if (UNLIKELY(match.match_length > 0)) {
55	0	if (match.strstart >= match.orgstart) {
56	0	if (match.strstart + match.match_length - 1 >= match.orgstart) {
57	0	insert_string(s, match.strstart, match.match_length);
58	0	} else {
59	0	insert_string(s, match.strstart, match.orgstart - match.strstart + 1);
60	0	}
61	0	match.strstart += match.match_length;
62	0	match.match_length = 0;
63	0	}
64	0	}
65	1.69M	return;
66	1.69M	}
67
68		/* Insert into hash table. */
69	222k	if (LIKELY(match.strstart >= match.orgstart)) {
70	214k	if (LIKELY(match.strstart + match.match_length - 1 >= match.orgstart)) {
71	214k	insert_string(s, match.strstart, match.match_length);
72	214k	} else {
73	0	insert_string(s, match.strstart, match.orgstart - match.strstart + 1);
74	0	}
75	214k	} else if (match.orgstart < match.strstart + match.match_length) {
76	8.05k	insert_string(s, match.orgstart, match.strstart + match.match_length - match.orgstart);
77	8.05k	}
78	222k	match.strstart += match.match_length;
79	222k	match.match_length = 0;
80	222k	}
81
82	137k	static void fizzle_matches(deflate_state s, struct match current, struct match *next) {
83	137k	Pos limit;
84	137k	unsigned char match, orig;
85	137k	int changed = 0;
86	137k	struct match c, n;
87		/* step zero: sanity checks */
88
89	137k	if (current->match_length <= 1)
90	70.4k	return;
91
92	66.7k	if (UNLIKELY(current->match_length > 1 + next->match_start))
93	70	return;
94
95	66.6k	if (UNLIKELY(current->match_length > 1 + next->strstart))
96	0	return;
97
98	66.6k	match = s->window - current->match_length + 1 + next->match_start;
99	66.6k	orig = s->window - current->match_length + 1 + next->strstart;
100
101		/* quick exit check.. if this fails then don't bother with anything else */
102	66.6k	if (LIKELY(match != orig))
103	39.8k	return;
104
105	26.7k	c = *current;
106	26.7k	n = *next;
107
108		/* step one: try to move the "next" match to the left as much as possible */
109	26.7k	limit = next->strstart > MAX_DIST(s) ? next->strstart - (Pos)MAX_DIST(s) : 0;
110
111	26.7k	match = s->window + n.match_start - 1;
112	26.7k	orig = s->window + n.strstart - 1;
113
114	480k	while (match == orig) {
115	461k	if (UNLIKELY(c.match_length < 1))
116	1.10k	break;
117	459k	if (UNLIKELY(n.strstart <= limit))
118	206	break;
119	459k	if (UNLIKELY(n.match_length >= 256))
120	5.43k	break;
121	454k	if (UNLIKELY(n.match_start <= 1))
122	103	break;
123
124	454k	n.strstart--;
125	454k	n.match_start--;
126	454k	n.match_length++;
127	454k	c.match_length--;
128	454k	match--;
129	454k	orig--;
130	454k	changed++;
131	454k	}
132
133	26.7k	if (!changed)
134	9.00k	return;
135
136	17.7k	if (c.match_length <= 1 && n.match_length != 2) {
137	8.05k	n.orgstart++;
138	8.05k	*current = c;
139	8.05k	*next = n;
140	9.73k	} else {
141	9.73k	return;
142	9.73k	}
143	17.7k	}
144
145	1.53k	Z_INTERNAL block_state deflate_medium(deflate_state *s, int flush) {
146		/* Align the first struct to start on a new cacheline, this allows us to fit both structs in one cacheline */
147	1.53k	ALIGNED_(16) struct match current_match;
148	1.53k	struct match next_match;
149
150		/* For levels below 5, don't check the next position for a better match */
151	1.53k	int early_exit = s->level < 5;
152
153	1.53k	memset(&current_match, 0, sizeof(struct match));
154	1.53k	memset(&next_match, 0, sizeof(struct match));
155
156	1.92M	for (;;) {
157	1.92M	Pos hash_head = 0; /* head of the hash chain */
158	1.92M	int bflush = 0; /* set if current block must be flushed */
159	1.92M	int64_t dist;
160
161		/* Make sure that we always have enough lookahead, except
162		* at the end of the input file. We need STD_MAX_MATCH bytes
163		* for the next match, plus WANT_MIN_MATCH bytes to insert the
164		* string following the next current_match.
165		*/
166	1.92M	if (s->lookahead < MIN_LOOKAHEAD) {
167	88.8k	PREFIX(fill_window)(s);
168	88.8k	if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
169	0	return need_more;
170	0	}
171	88.8k	if (UNLIKELY(s->lookahead == 0))
172	1.53k	break; /* flush the current block */
173	87.3k	next_match.match_length = 0;
174	87.3k	}
175
176		/* Insert the string window[strstart .. strstart+2] in the
177		* dictionary, and set hash_head to the head of the hash chain:
178		*/
179
180		/* If we already have a future match from a previous round, just use that */
181	1.92M	if (!early_exit && next_match.match_length > 0) {
182	1.24M	current_match = next_match;
183	1.24M	next_match.match_length = 0;
184	1.24M	} else {
185	678k	hash_head = 0;
186	678k	if (s->lookahead >= WANT_MIN_MATCH) {
187	676k	hash_head = quick_insert_string(s, s->strstart);
188	676k	}
189
190	678k	current_match.strstart = (uint16_t)s->strstart;
191	678k	current_match.orgstart = current_match.strstart;
192
193		/* Find the longest match, discarding those <= prev_length.
194		* At this point we have always match_length < WANT_MIN_MATCH
195		*/
196
197	678k	dist = (int64_t)s->strstart - hash_head;
198	678k	if (dist <= MAX_DIST(s) && dist > 0 && hash_head != 0) {
199		/* To simplify the code, we prevent matches with the string
200		* of window index 0 (in particular we have to avoid a match
201		* of the string with itself at the start of the input file).
202		*/
203	90.0k	current_match.match_length = (uint16_t)FUNCTABLE_CALL(longest_match)(s, hash_head);
204	90.0k	current_match.match_start = (uint16_t)s->match_start;
205	90.0k	if (UNLIKELY(current_match.match_length < WANT_MIN_MATCH))
206	3.10k	current_match.match_length = 1;
207	90.0k	if (UNLIKELY(current_match.match_start >= current_match.strstart)) {
208		/* this can happen due to some restarts */
209	0	current_match.match_length = 1;
210	0	}
211	588k	} else {
212		/* Set up the match to be a 1 byte literal */
213	588k	current_match.match_start = 0;
214	588k	current_match.match_length = 1;
215	588k	}
216	678k	}
217
218	1.92M	insert_match(s, current_match);
219
220		/* now, look ahead one */
221	1.92M	if (LIKELY(!early_exit && s->lookahead > MIN_LOOKAHEAD && (uint32_t)(current_match.strstart + current_match.match_length) < (s->window_size - MIN_LOOKAHEAD))) {
222	1.24M	s->strstart = current_match.strstart + current_match.match_length;
223	1.24M	hash_head = quick_insert_string(s, s->strstart);
224
225	1.24M	next_match.strstart = (uint16_t)s->strstart;
226	1.24M	next_match.orgstart = next_match.strstart;
227
228		/* Find the longest match, discarding those <= prev_length.
229		* At this point we have always match_length < WANT_MIN_MATCH
230		*/
231
232	1.24M	dist = (int64_t)s->strstart - hash_head;
233	1.24M	if (dist <= MAX_DIST(s) && dist > 0 && hash_head != 0) {
234		/* To simplify the code, we prevent matches with the string
235		* of window index 0 (in particular we have to avoid a match
236		* of the string with itself at the start of the input file).
237		*/
238	153k	next_match.match_length = (uint16_t)FUNCTABLE_CALL(longest_match)(s, hash_head);
239	153k	next_match.match_start = (uint16_t)s->match_start;
240	153k	if (UNLIKELY(next_match.match_start >= next_match.strstart)) {
241		/* this can happen due to some restarts */
242	0	next_match.match_length = 1;
243	0	}
244	153k	if (next_match.match_length < WANT_MIN_MATCH)
245	16.1k	next_match.match_length = 1;
246	137k	else
247	137k	fizzle_matches(s, &current_match, &next_match);
248	1.08M	} else {
249		/* Set up the match to be a 1 byte literal */
250	1.08M	next_match.match_start = 0;
251	1.08M	next_match.match_length = 1;
252	1.08M	}
253
254	1.24M	s->strstart = current_match.strstart;
255	1.24M	} else {
256	678k	next_match.match_length = 0;
257	678k	}
258
259		/* now emit the current match */
260	1.92M	bflush = emit_match(s, current_match);
261
262		/* move the "cursor" forward */
263	1.92M	s->strstart += current_match.match_length;
264
265	1.92M	if (UNLIKELY(bflush))
266	1.92M	FLUSH_BLOCK(s, 0);
267	1.92M	}
268	1.53k	s->insert = s->strstart < (STD_MIN_MATCH - 1) ? s->strstart : (STD_MIN_MATCH - 1);
269	1.53k	if (flush == Z_FINISH) {
270	1.53k	FLUSH_BLOCK(s, 1);
271	1.53k	return finish_done;
272	1.53k	}
273	0	if (UNLIKELY(s->sym_next))
274	0	FLUSH_BLOCK(s, 0);
275
276	0	return block_done;
277	0	}
278		#endif