/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, unsigned char *window, struct match match) {
    int bflush = 0;
    uint32_t match_len = match.match_length;

    /* None of the below functions care about s->lookahead, so decrement it early */
    s->lookahead -= match_len;

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

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

    bflush += zng_tr_tally_dist(s, match.strstart - match.match_start, match_len - STD_MIN_MATCH);
    return bflush;
}

/* insert_match assumes: s->lookahead > match.match_length + WANT_MIN_MATCH */
static void insert_match(deflate_state *s, unsigned char *window, struct match match) {
    uint32_t match_len = match.match_length;
    uint32_t strstart = match.strstart;

    /* matches that are not long enough we need to emit as literals */
    if (LIKELY(match_len < WANT_MIN_MATCH)) {
        strstart++;
        match_len--;
        if (UNLIKELY(match_len > 0)) {
            if (strstart >= match.orgstart) {
                if (strstart + match_len - 1 >= match.orgstart) {
                    insert_string(s, window, strstart, match_len);
                } else {
                    insert_string(s, window, strstart, match.orgstart - strstart + 1);
                }
            }
        }
        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_len <= 16 * s->max_insert_length && s->lookahead >= WANT_MIN_MATCH) {
        match_len--; /* string at strstart already in table */
        strstart++;

        if (LIKELY(strstart >= match.orgstart)) {
            if (LIKELY(strstart + match_len - 1 >= match.orgstart)) {
                insert_string(s, window, strstart, match_len);
            } else {
                insert_string(s, window, strstart, match.orgstart - strstart + 1);
            }
        } else if (match.orgstart < strstart + match_len) {
            insert_string(s, window, match.orgstart, strstart + match_len - match.orgstart);
        }
    } else {
        strstart += match_len;
        quick_insert_string(s, window, 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.
         */
    }
}

Z_FORCEINLINE static struct match find_best_match(deflate_state *s, uint32_t hash_head) {
    struct match m;
    int64_t dist;

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

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

    return m;
}

/* fizzle_matches assumes:
 * - current->match_length > 1
 * - (current->match_length - 1) <= next->match_start
 * - (current->match_length - 1) <= next->strstart
 */
static void fizzle_matches(deflate_state *s, unsigned char *window, struct match *current, struct match *next) {
    unsigned char *match, *orig;
    struct match c, n;
    int changed = 0;
    Pos limit;

    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 && 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 = {0};
                 struct match next_match = {0};
    unsigned char *window = s->window;

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

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

        /* 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, window, s->strstart);
            }

            current_match = find_best_match(s, hash_head);
        }

        if (LIKELY(s->lookahead > (unsigned int)(current_match.match_length + WANT_MIN_MATCH)))
            insert_match(s, window, 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, window, s->strstart);

            next_match = find_best_match(s, hash_head);

            uint32_t tmp_cmatch_len_sub = current_match.match_length - 1;
            if (tmp_cmatch_len_sub
                     && next_match.match_length >= WANT_MIN_MATCH
                     && tmp_cmatch_len_sub <= next_match.match_start
                     && tmp_cmatch_len_sub <= next_match.strstart) {
                fizzle_matches(s, window, &current_match, &next_match);
            }

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

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

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

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

    return block_done;
}
#endif

Coverage Report

Created: 2026-05-28 06:48

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	1.95M	static int emit_match(deflate_state s, unsigned char window, struct match match) {
24	1.95M	int bflush = 0;
25	1.95M	uint32_t match_len = match.match_length;
26
27		/* None of the below functions care about s->lookahead, so decrement it early */
28	1.95M	s->lookahead -= match_len;
29
30		/* matches that are not long enough we need to emit as literals */
31	1.95M	if (match_len < WANT_MIN_MATCH) {
32	3.59M	while (match_len) {
33	1.79M	bflush += zng_tr_tally_lit(s, window[match.strstart]);
34	1.79M	match_len--;
35	1.79M	match.strstart++;
36	1.79M	}
37	1.79M	return bflush;
38	1.79M	}
39
40	156k	check_match(s, match.strstart, match.match_start, match_len);
41
42	156k	bflush += zng_tr_tally_dist(s, match.strstart - match.match_start, match_len - STD_MIN_MATCH);
43	156k	return bflush;
44	1.95M	}
45
46		/* insert_match assumes: s->lookahead > match.match_length + WANT_MIN_MATCH */
47	1.95M	static void insert_match(deflate_state s, unsigned char window, struct match match) {
48	1.95M	uint32_t match_len = match.match_length;
49	1.95M	uint32_t strstart = match.strstart;
50
51		/* matches that are not long enough we need to emit as literals */
52	1.95M	if (LIKELY(match_len < WANT_MIN_MATCH)) {
53	1.78M	strstart++;
54	1.78M	match_len--;
55	1.78M	if (UNLIKELY(match_len > 0)) {
56	0	if (strstart >= match.orgstart) {
57	0	if (strstart + match_len - 1 >= match.orgstart) {
58	0	insert_string(s, window, strstart, match_len);
59	0	} else {
60	0	insert_string(s, window, strstart, match.orgstart - strstart + 1);
61	0	}
62	0	}
63	0	}
64	1.78M	return;
65	1.78M	}
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	163k	if (match_len <= 16 * s->max_insert_length && s->lookahead >= WANT_MIN_MATCH) {
71	154k	match_len--; /* string at strstart already in table */
72	154k	strstart++;
73
74	154k	if (LIKELY(strstart >= match.orgstart)) {
75	147k	if (LIKELY(strstart + match_len - 1 >= match.orgstart)) {
76	147k	insert_string(s, window, strstart, match_len);
77	147k	} else {
78	0	insert_string(s, window, strstart, match.orgstart - strstart + 1);
79	0	}
80	147k	} else if (match.orgstart < strstart + match_len) {
81	7.69k	insert_string(s, window, match.orgstart, strstart + match_len - match.orgstart);
82	7.69k	}
83	154k	} else {
84	8.50k	strstart += match_len;
85	8.50k	quick_insert_string(s, window, strstart + 2 - STD_MIN_MATCH);
86
87		/* If lookahead < WANT_MIN_MATCH, ins_h is garbage, but it does not
88		* matter since it will be recomputed at next deflate call.
89		*/
90	8.50k	}
91	163k	}
92
93	1.95M	Z_FORCEINLINE static struct match find_best_match(deflate_state *s, uint32_t hash_head) {
94	1.95M	struct match m;
95	1.95M	int64_t dist;
96
97	1.95M	m.strstart = (uint16_t)s->strstart;
98	1.95M	m.orgstart = m.strstart;
99
100	1.95M	dist = (int64_t)s->strstart - hash_head;
101	1.95M	if (dist <= MAX_DIST(s) && dist > 0 && hash_head != 0) {
102		/* To simplify the code, we prevent matches with the string
103		* of window index 0 (in particular we have to avoid a match
104		* of the string with itself at the start of the input file).
105		*/
106	197k	m.match_length = (uint16_t)FUNCTABLE_CALL(longest_match)(s, hash_head);
107	197k	m.match_start = (uint16_t)s->match_start;
108	197k	if (UNLIKELY(m.match_length < WANT_MIN_MATCH))
109	32.7k	m.match_length = 1;
110	197k	if (UNLIKELY(m.match_start >= m.strstart)) {
111		/* this can happen due to some restarts */
112	0	m.match_length = 1;
113	0	}
114	1.75M	} else {
115		/* Set up the match to be a 1 byte literal */
116	1.75M	m.match_start = 0;
117	1.75M	m.match_length = 1;
118	1.75M	}
119
120	1.95M	return m;
121	1.95M	}
122
123		/* fizzle_matches assumes:
124		* - current->match_length > 1
125		* - (current->match_length - 1) <= next->match_start
126		* - (current->match_length - 1) <= next->strstart
127		*/
128	52.6k	static void fizzle_matches(deflate_state s, unsigned char window, struct match current, struct match next) {
129	52.6k	unsigned char match, orig;
130	52.6k	struct match c, n;
131	52.6k	int changed = 0;
132	52.6k	Pos limit;
133
134	52.6k	match = window - current->match_length + 1 + next->match_start;
135	52.6k	orig = window - current->match_length + 1 + next->strstart;
136
137		/* quick exit check.. if this fails then don't bother with anything else */
138	52.6k	if (LIKELY(match != orig))
139	26.6k	return;
140
141	25.9k	c = *current;
142	25.9k	n = *next;
143
144		/* step one: try to move the "next" match to the left as much as possible */
145	25.9k	limit = next->strstart > MAX_DIST(s) ? next->strstart - (Pos)MAX_DIST(s) : 0;
146
147	25.9k	match = window + n.match_start - 1;
148	25.9k	orig = window + n.strstart - 1;
149
150	590k	while (match == orig) {
151	572k	if (UNLIKELY(c.match_length < 1))
152	1.13k	break;
153	571k	if (UNLIKELY(n.strstart <= limit))
154	205	break;
155	571k	if (UNLIKELY(n.match_length >= 256))
156	6.59k	break;
157	564k	if (UNLIKELY(n.match_start <= 1))
158	95	break;
159
160	564k	n.strstart--;
161	564k	n.match_start--;
162	564k	n.match_length++;
163	564k	c.match_length--;
164	564k	match--;
165	564k	orig--;
166	564k	changed++;
167	564k	}
168
169	25.9k	if (changed && c.match_length <= 1 && n.match_length != 2) {
170	7.69k	n.orgstart++;
171	7.69k	*current = c;
172	7.69k	*next = n;
173	18.2k	} else {
174	18.2k	return;
175	18.2k	}
176	25.9k	}
177
178	1.46k	Z_INTERNAL block_state deflate_medium(deflate_state *s, int flush) {
179		/* Align the first struct to start on a new cacheline, this allows us to fit both structs in one cacheline */
180	1.46k	ALIGNED_(16) struct match current_match = {0};
181	1.46k	struct match next_match = {0};
182	1.46k	unsigned char *window = s->window;
183
184		/* For levels below 5, don't check the next position for a better match */
185	1.46k	int early_exit = s->level < 5;
186
187	1.95M	for (;;) {
188	1.95M	uint32_t hash_head = 0; /* head of the hash chain */
189	1.95M	int bflush = 0; /* set if current block must be flushed */
190
191		/* Make sure that we always have enough lookahead, except
192		* at the end of the input file. We need STD_MAX_MATCH bytes
193		* for the next match, plus WANT_MIN_MATCH bytes to insert the
194		* string following the next current_match.
195		*/
196	1.95M	if (s->lookahead < MIN_LOOKAHEAD) {
197	79.1k	PREFIX(fill_window)(s);
198	79.1k	if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
199	0	return need_more;
200	0	}
201	79.1k	if (UNLIKELY(s->lookahead == 0))
202	1.46k	break; /* flush the current block */
203	77.6k	next_match.match_length = 0;
204	77.6k	}
205
206		/* Insert the string window[strstart .. strstart+2] in the
207		* dictionary, and set hash_head to the head of the hash chain:
208		*/
209
210		/* If we already have a future match from a previous round, just use that */
211	1.95M	if (!early_exit && next_match.match_length > 0) {
212	1.20M	current_match = next_match;
213	1.20M	next_match.match_length = 0;
214	1.20M	} else {
215	752k	hash_head = 0;
216	752k	if (s->lookahead >= WANT_MIN_MATCH) {
217	750k	hash_head = quick_insert_string(s, window, s->strstart);
218	750k	}
219
220	752k	current_match = find_best_match(s, hash_head);
221	752k	}
222
223	1.95M	if (LIKELY(s->lookahead > (unsigned int)(current_match.match_length + WANT_MIN_MATCH)))
224	1.95M	insert_match(s, window, current_match);
225
226		/* now, look ahead one */
227	1.95M	if (LIKELY(!early_exit && s->lookahead > MIN_LOOKAHEAD && (uint32_t)(current_match.strstart + current_match.match_length) < (s->window_size - MIN_LOOKAHEAD))) {
228	1.20M	s->strstart = current_match.strstart + current_match.match_length;
229	1.20M	hash_head = quick_insert_string(s, window, s->strstart);
230
231	1.20M	next_match = find_best_match(s, hash_head);
232
233	1.20M	uint32_t tmp_cmatch_len_sub = current_match.match_length - 1;
234	1.20M	if (tmp_cmatch_len_sub
235	99.3k	&& next_match.match_length >= WANT_MIN_MATCH
236	52.9k	&& tmp_cmatch_len_sub <= next_match.match_start
237	52.6k	&& tmp_cmatch_len_sub <= next_match.strstart) {
238	52.6k	fizzle_matches(s, window, &current_match, &next_match);
239	52.6k	}
240
241	1.20M	s->strstart = current_match.strstart;
242	1.20M	} else {
243	751k	next_match.match_length = 0;
244	751k	}
245
246		/* now emit the current match */
247	1.95M	bflush = emit_match(s, window, current_match);
248
249		/* move the "cursor" forward */
250	1.95M	s->strstart += current_match.match_length;
251
252	1.95M	if (UNLIKELY(bflush))
253	1.95M	FLUSH_BLOCK(s, window, 0);
254	1.95M	}
255	1.46k	s->insert = s->strstart < (STD_MIN_MATCH - 1) ? s->strstart : (STD_MIN_MATCH - 1);
256	1.46k	if (flush == Z_FINISH) {
257	1.46k	FLUSH_BLOCK(s, window, 1);
258	1.46k	return finish_done;
259	1.46k	}
260	0	if (UNLIKELY(s->sym_next))
261	0	FLUSH_BLOCK(s, window, 0);
262
263	0	return block_done;
264	0	}
265		#endif