/src/zlib-ng/deflate_medium.c

Source
/* 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"
#include "insert_string_p.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;

    /* matches that are not long enough we need to emit as literals */
    if (LIKELY(match.match_length < WANT_MIN_MATCH)) {
        match.strstart++;
        match.match_length--;
        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 new strings in the hash table only if the match length
     * is not too large. This saves time but degrades compression.
     */
    if (match.match_length <= 16 * s->max_insert_length && s->lookahead >= WANT_MIN_MATCH) {
        match.match_length--; /* string at strstart already in table */
        match.strstart++;

        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;
    } else {
        match.strstart += match.match_length;
        match.match_length = 0;

        if (match.strstart >= (STD_MIN_MATCH - 2))
            quick_insert_string(s, match.strstart + 2 - STD_MIN_MATCH);

        /* If lookahead < WANT_MIN_MATCH, ins_h is garbage, but it does not
         * matter since it will be recomputed at next deflate call.
         */
    }
}

static void fizzle_matches(deflate_state *s, struct match *current, struct match *next) {
    unsigned char *window;
    unsigned char *match, *orig;
    struct match c, n;
    int changed = 0;
    Pos limit;
    /* 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;

    window = s->window;

    match = window - current->match_length + 1 + next->match_start;
    orig  = 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 = window + n.match_start - 1;
    orig = 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 (;;) {
        uint32_t 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-12-28 06:36

Line	Count	Source
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		#include "insert_string_p.h"
15
16		struct match {
17		uint16_t match_start;
18		uint16_t match_length;
19		uint16_t strstart;
20		uint16_t orgstart;
21		};
22
23	19.0M	static int emit_match(deflate_state *s, struct match match) {
24	19.0M	int bflush = 0;
25
26		/* matches that are not long enough we need to emit as literals */
27	19.0M	if (match.match_length < WANT_MIN_MATCH) {
28	34.2M	while (match.match_length) {
29	17.0M	bflush += zng_tr_tally_lit(s, s->window[match.strstart]);
30	17.0M	s->lookahead--;
31	17.0M	match.strstart++;
32	17.0M	match.match_length--;
33	17.0M	}
34	17.1M	return bflush;
35	17.1M	}
36
37	1.94M	check_match(s, match.strstart, match.match_start, match.match_length);
38
39	1.94M	bflush += zng_tr_tally_dist(s, match.strstart - match.match_start, match.match_length - STD_MIN_MATCH);
40
41	1.94M	s->lookahead -= match.match_length;
42	1.94M	return bflush;
43	19.0M	}
44
45	19.0M	static void insert_match(deflate_state *s, struct match match) {
46	19.0M	if (UNLIKELY(s->lookahead <= (unsigned int)(match.match_length + WANT_MIN_MATCH)))
47	2.28k	return;
48
49		/* matches that are not long enough we need to emit as literals */
50	19.0M	if (LIKELY(match.match_length < WANT_MIN_MATCH)) {
51	17.0M	match.strstart++;
52	17.0M	match.match_length--;
53	17.0M	if (UNLIKELY(match.match_length > 0)) {
54	0	if (match.strstart >= match.orgstart) {
55	0	if (match.strstart + match.match_length - 1 >= match.orgstart) {
56	0	insert_string(s, match.strstart, match.match_length);
57	0	} else {
58	0	insert_string(s, match.strstart, match.orgstart - match.strstart + 1);
59	0	}
60	0	match.strstart += match.match_length;
61	0	match.match_length = 0;
62	0	}
63	0	}
64	17.0M	return;
65	17.0M	}
66
67		/* Insert new strings in the hash table only if the match length
68		* is not too large. This saves time but degrades compression.
69		*/
70	1.97M	if (match.match_length <= 16 * s->max_insert_length && s->lookahead >= WANT_MIN_MATCH) {
71	1.92M	match.match_length--; /* string at strstart already in table */
72	1.92M	match.strstart++;
73
74	1.92M	if (LIKELY(match.strstart >= match.orgstart)) {
75	1.89M	if (LIKELY(match.strstart + match.match_length - 1 >= match.orgstart)) {
76	1.89M	insert_string(s, match.strstart, match.match_length);
77	1.89M	} else {
78	0	insert_string(s, match.strstart, match.orgstart - match.strstart + 1);
79	0	}
80	1.89M	} else if (match.orgstart < match.strstart + match.match_length) {
81	31.1k	insert_string(s, match.orgstart, match.strstart + match.match_length - match.orgstart);
82	31.1k	}
83	1.92M	match.strstart += match.match_length;
84	1.92M	match.match_length = 0;
85	1.92M	} else {
86	49.2k	match.strstart += match.match_length;
87	49.2k	match.match_length = 0;
88
89	49.2k	if (match.strstart >= (STD_MIN_MATCH - 2))
90	49.2k	quick_insert_string(s, match.strstart + 2 - STD_MIN_MATCH);
91
92		/* If lookahead < WANT_MIN_MATCH, ins_h is garbage, but it does not
93		* matter since it will be recomputed at next deflate call.
94		*/
95	49.2k	}
96	1.97M	}
97
98	1.31M	static void fizzle_matches(deflate_state s, struct match current, struct match *next) {
99	1.31M	unsigned char *window;
100	1.31M	unsigned char match, orig;
101	1.31M	struct match c, n;
102	1.31M	int changed = 0;
103	1.31M	Pos limit;
104		/* step zero: sanity checks */
105
106	1.31M	if (current->match_length <= 1)
107	747k	return;
108
109	565k	if (UNLIKELY(current->match_length > 1 + next->match_start))
110	204	return;
111
112	565k	if (UNLIKELY(current->match_length > 1 + next->strstart))
113	0	return;
114
115	565k	window = s->window;
116
117	565k	match = window - current->match_length + 1 + next->match_start;
118	565k	orig = window - current->match_length + 1 + next->strstart;
119
120		/* quick exit check.. if this fails then don't bother with anything else */
121	565k	if (LIKELY(match != orig))
122	454k	return;
123
124	110k	c = *current;
125	110k	n = *next;
126
127		/* step one: try to move the "next" match to the left as much as possible */
128	110k	limit = next->strstart > MAX_DIST(s) ? next->strstart - (Pos)MAX_DIST(s) : 0;
129
130	110k	match = window + n.match_start - 1;
131	110k	orig = window + n.strstart - 1;
132
133	1.19M	while (match == orig) {
134	1.11M	if (UNLIKELY(c.match_length < 1))
135	4.73k	break;
136	1.10M	if (UNLIKELY(n.strstart <= limit))
137	0	break;
138	1.10M	if (UNLIKELY(n.match_length >= 256))
139	19.7k	break;
140	1.08M	if (UNLIKELY(n.match_start <= 1))
141	18	break;
142
143	1.08M	n.strstart--;
144	1.08M	n.match_start--;
145	1.08M	n.match_length++;
146	1.08M	c.match_length--;
147	1.08M	match--;
148	1.08M	orig--;
149	1.08M	changed++;
150	1.08M	}
151
152	110k	if (!changed)
153	54.3k	return;
154
155	56.5k	if (c.match_length <= 1 && n.match_length != 2) {
156	31.1k	n.orgstart++;
157	31.1k	*current = c;
158	31.1k	*next = n;
159	31.1k	} else {
160	25.4k	return;
161	25.4k	}
162	56.5k	}
163
164	1.08k	Z_INTERNAL block_state deflate_medium(deflate_state *s, int flush) {
165		/* Align the first struct to start on a new cacheline, this allows us to fit both structs in one cacheline */
166	1.08k	ALIGNED_(16) struct match current_match;
167	1.08k	struct match next_match;
168
169		/* For levels below 5, don't check the next position for a better match */
170	1.08k	int early_exit = s->level < 5;
171
172	1.08k	memset(&current_match, 0, sizeof(struct match));
173	1.08k	memset(&next_match, 0, sizeof(struct match));
174
175	19.0M	for (;;) {
176	19.0M	uint32_t hash_head = 0; /* head of the hash chain */
177	19.0M	int bflush = 0; /* set if current block must be flushed */
178	19.0M	int64_t dist;
179
180		/* Make sure that we always have enough lookahead, except
181		* at the end of the input file. We need STD_MAX_MATCH bytes
182		* for the next match, plus WANT_MIN_MATCH bytes to insert the
183		* string following the next current_match.
184		*/
185	19.0M	if (s->lookahead < MIN_LOOKAHEAD) {
186	44.8k	PREFIX(fill_window)(s);
187	44.8k	if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
188	283	return need_more;
189	283	}
190	44.6k	if (UNLIKELY(s->lookahead == 0))
191	705	break; /* flush the current block */
192	43.9k	next_match.match_length = 0;
193	43.9k	}
194
195		/* Insert the string window[strstart .. strstart+2] in the
196		* dictionary, and set hash_head to the head of the hash chain:
197		*/
198
199		/* If we already have a future match from a previous round, just use that */
200	19.0M	if (!early_exit && next_match.match_length > 0) {
201	11.0M	current_match = next_match;
202	11.0M	next_match.match_length = 0;
203	11.0M	} else {
204	8.04M	hash_head = 0;
205	8.04M	if (s->lookahead >= WANT_MIN_MATCH) {
206	8.04M	hash_head = quick_insert_string(s, s->strstart);
207	8.04M	}
208
209	8.04M	current_match.strstart = (uint16_t)s->strstart;
210	8.04M	current_match.orgstart = current_match.strstart;
211
212		/* Find the longest match, discarding those <= prev_length.
213		* At this point we have always match_length < WANT_MIN_MATCH
214		*/
215
216	8.04M	dist = (int64_t)s->strstart - hash_head;
217	8.04M	if (dist <= MAX_DIST(s) && dist > 0 && hash_head != 0) {
218		/* To simplify the code, we prevent matches with the string
219		* of window index 0 (in particular we have to avoid a match
220		* of the string with itself at the start of the input file).
221		*/
222	3.02M	current_match.match_length = (uint16_t)FUNCTABLE_CALL(longest_match)(s, hash_head);
223	3.02M	current_match.match_start = (uint16_t)s->match_start;
224	3.02M	if (UNLIKELY(current_match.match_length < WANT_MIN_MATCH))
225	2.36M	current_match.match_length = 1;
226	3.02M	if (UNLIKELY(current_match.match_start >= current_match.strstart)) {
227		/* this can happen due to some restarts */
228	129	current_match.match_length = 1;
229	129	}
230	5.02M	} else {
231		/* Set up the match to be a 1 byte literal */
232	5.02M	current_match.match_start = 0;
233	5.02M	current_match.match_length = 1;
234	5.02M	}
235	8.04M	}
236
237	19.0M	insert_match(s, current_match);
238
239		/* now, look ahead one */
240	19.0M	if (LIKELY(!early_exit && s->lookahead > MIN_LOOKAHEAD && (uint32_t)(current_match.strstart + current_match.match_length) < (s->window_size - MIN_LOOKAHEAD))) {
241	11.0M	s->strstart = current_match.strstart + current_match.match_length;
242	11.0M	hash_head = quick_insert_string(s, s->strstart);
243
244	11.0M	next_match.strstart = (uint16_t)s->strstart;
245	11.0M	next_match.orgstart = next_match.strstart;
246
247		/* Find the longest match, discarding those <= prev_length.
248		* At this point we have always match_length < WANT_MIN_MATCH
249		*/
250
251	11.0M	dist = (int64_t)s->strstart - hash_head;
252	11.0M	if (dist <= MAX_DIST(s) && dist > 0 && hash_head != 0) {
253		/* To simplify the code, we prevent matches with the string
254		* of window index 0 (in particular we have to avoid a match
255		* of the string with itself at the start of the input file).
256		*/
257	3.96M	next_match.match_length = (uint16_t)FUNCTABLE_CALL(longest_match)(s, hash_head);
258	3.96M	next_match.match_start = (uint16_t)s->match_start;
259	3.96M	if (UNLIKELY(next_match.match_start >= next_match.strstart)) {
260		/* this can happen due to some restarts */
261	80	next_match.match_length = 1;
262	80	}
263	3.96M	if (next_match.match_length < WANT_MIN_MATCH)
264	2.64M	next_match.match_length = 1;
265	1.31M	else
266	1.31M	fizzle_matches(s, &current_match, &next_match);
267	7.04M	} else {
268		/* Set up the match to be a 1 byte literal */
269	7.04M	next_match.match_start = 0;
270	7.04M	next_match.match_length = 1;
271	7.04M	}
272
273	11.0M	s->strstart = current_match.strstart;
274	11.0M	} else {
275	8.04M	next_match.match_length = 0;
276	8.04M	}
277
278		/* now emit the current match */
279	19.0M	bflush = emit_match(s, current_match);
280
281		/* move the "cursor" forward */
282	19.0M	s->strstart += current_match.match_length;
283
284	19.0M	if (UNLIKELY(bflush))
285	19.0M	FLUSH_BLOCK(s, 0);
286	19.0M	}
287	705	s->insert = s->strstart < (STD_MIN_MATCH - 1) ? s->strstart : (STD_MIN_MATCH - 1);
288	705	if (flush == Z_FINISH) {
289	705	FLUSH_BLOCK(s, 1);
290	684	return finish_done;
291	705	}
292	0	if (UNLIKELY(s->sym_next))
293	0	FLUSH_BLOCK(s, 0);
294
295	0	return block_done;
296	0	}
297		#endif