/src/zlib-ng/deflate_slow.c

Source
/* deflate_slow.c -- compress data using the slow strategy of deflation algorithm
 *
 * Copyright (C) 1995-2024 Jean-loup Gailly and Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

#include "zbuild.h"
#include "deflate.h"
#include "deflate_p.h"
#include "functable.h"
#include "insert_string_p.h"

/* ===========================================================================
 * Same as deflate_medium, but achieves better compression. We use a lazy
 * evaluation for matches: a match is finally adopted only if there is
 * no better match at the next window position.
 */
Z_INTERNAL block_state deflate_slow(deflate_state *s, int flush) {
    match_func longest_match;
    insert_string_cb insert_string_func;
    unsigned char *window = s->window;
    int bflush;              /* set if current block must be flushed */
    int level = s->level;

    if (level >= 9) {
        longest_match = FUNCTABLE_FPTR(longest_match_slow);
        insert_string_func = insert_string_roll;
    } else {
        longest_match = FUNCTABLE_FPTR(longest_match);
        insert_string_func = insert_string;
    }

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

        /* Insert the string window[strstart .. strstart+2] in the
         * dictionary, and set hash_head to the head of the hash chain:
         */
        uint32_t hash_head = 0;
        if (LIKELY(s->lookahead >= WANT_MIN_MATCH)) {
            if (level >= 9)
                hash_head = quick_insert_string_roll(s, s->strstart);
            else
                hash_head = quick_insert_string(s, s->strstart);
        }

        /* Find the longest match, discarding those <= prev_length.
         */
        s->prev_match = s->match_start;
        uint32_t match_len = STD_MIN_MATCH - 1;
        int64_t dist = (int64_t)s->strstart - hash_head;

        if (dist <= MAX_DIST(s) && dist > 0 && s->prev_length < s->max_lazy_match && 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).
             */
            match_len = longest_match(s, hash_head);
            /* longest_match() sets match_start */

            if (match_len <= 5 && (s->strategy == Z_FILTERED)) {
                /* If prev_match is also WANT_MIN_MATCH, match_start is garbage
                 * but we will ignore the current match anyway.
                 */
                match_len = STD_MIN_MATCH - 1;
            }
        }
        /* If there was a match at the previous step and the current
         * match is not better, output the previous match:
         */
        if (s->prev_length >= STD_MIN_MATCH && match_len <= s->prev_length) {
            unsigned int max_insert = s->strstart + s->lookahead - STD_MIN_MATCH;
            /* Do not insert strings in hash table beyond this. */

            Assert((s->strstart-1) <= UINT16_MAX, "strstart-1 should fit in uint16_t");
            check_match(s, s->strstart - 1, s->prev_match, s->prev_length);

            bflush = zng_tr_tally_dist(s, s->strstart -1 - s->prev_match, s->prev_length - STD_MIN_MATCH);

            /* Insert in hash table all strings up to the end of the match.
             * strstart-1 and strstart are already inserted. If there is not
             * enough lookahead, the last two strings are not inserted in
             * the hash table.
             */
            s->prev_length -= 1;
            s->lookahead -= s->prev_length;

            unsigned int mov_fwd = s->prev_length - 1;
            if (max_insert > s->strstart) {
                unsigned int insert_cnt = mov_fwd;
                if (UNLIKELY(insert_cnt > max_insert - s->strstart))
                    insert_cnt = max_insert - s->strstart;
                insert_string_func(s, s->strstart + 1, insert_cnt);
            }
            s->prev_length = 0;
            s->match_available = 0;
            s->strstart += mov_fwd + 1;

            if (UNLIKELY(bflush))
                FLUSH_BLOCK(s, 0);

        } else if (s->match_available) {
            /* If there was no match at the previous position, output a
             * single literal. If there was a match but the current match
             * is longer, truncate the previous match to a single literal.
             */
            bflush = zng_tr_tally_lit(s, window[s->strstart-1]);
            if (UNLIKELY(bflush))
                FLUSH_BLOCK_ONLY(s, 0);
            s->prev_length = match_len;
            s->strstart++;
            s->lookahead--;
            if (UNLIKELY(s->strm->avail_out == 0))
                return need_more;
        } else {
            /* There is no previous match to compare with, wait for
             * the next step to decide.
             */
            s->prev_length = match_len;
            s->match_available = 1;
            s->strstart++;
            s->lookahead--;
        }
    }
    Assert(flush != Z_NO_FLUSH, "no flush?");
    if (UNLIKELY(s->match_available)) {
        Z_UNUSED(zng_tr_tally_lit(s, window[s->strstart-1]));
        s->match_available = 0;
    }
    s->insert = s->strstart < (STD_MIN_MATCH - 1) ? s->strstart : (STD_MIN_MATCH - 1);
    if (UNLIKELY(flush == Z_FINISH)) {
        FLUSH_BLOCK(s, 1);
        return finish_done;
    }
    if (UNLIKELY(s->sym_next))
        FLUSH_BLOCK(s, 0);
    return block_done;
}

Line	Count	Source
1		/* deflate_slow.c -- compress data using the slow strategy of deflation algorithm
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
7		#include "zbuild.h"
8		#include "deflate.h"
9		#include "deflate_p.h"
10		#include "functable.h"
11		#include "insert_string_p.h"
12
13		/* ===========================================================================
14		* Same as deflate_medium, but achieves better compression. We use a lazy
15		* evaluation for matches: a match is finally adopted only if there is
16		* no better match at the next window position.
17		*/
18	0	Z_INTERNAL block_state deflate_slow(deflate_state *s, int flush) {
19	0	match_func longest_match;
20	0	insert_string_cb insert_string_func;
21	0	unsigned char *window = s->window;
22	0	int bflush; /* set if current block must be flushed */
23	0	int level = s->level;
24
25	0	if (level >= 9) {
26	0	longest_match = FUNCTABLE_FPTR(longest_match_slow);
27	0	insert_string_func = insert_string_roll;
28	0	} else {
29	0	longest_match = FUNCTABLE_FPTR(longest_match);
30	0	insert_string_func = insert_string;
31	0	}
32
33		/* Process the input block. */
34	0	for (;;) {
35		/* Make sure that we always have enough lookahead, except
36		* at the end of the input file. We need STD_MAX_MATCH bytes
37		* for the next match, plus WANT_MIN_MATCH bytes to insert the
38		* string following the next match.
39		*/
40	0	if (s->lookahead < MIN_LOOKAHEAD) {
41	0	PREFIX(fill_window)(s);
42	0	if (UNLIKELY(s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH)) {
43	0	return need_more;
44	0	}
45	0	if (UNLIKELY(s->lookahead == 0))
46	0	break; /* flush the current block */
47	0	}
48
49		/* Insert the string window[strstart .. strstart+2] in the
50		* dictionary, and set hash_head to the head of the hash chain:
51		*/
52	0	uint32_t hash_head = 0;
53	0	if (LIKELY(s->lookahead >= WANT_MIN_MATCH)) {
54	0	if (level >= 9)
55	0	hash_head = quick_insert_string_roll(s, s->strstart);
56	0	else
57	0	hash_head = quick_insert_string(s, s->strstart);
58	0	}
59
60		/* Find the longest match, discarding those <= prev_length.
61		*/
62	0	s->prev_match = s->match_start;
63	0	uint32_t match_len = STD_MIN_MATCH - 1;
64	0	int64_t dist = (int64_t)s->strstart - hash_head;
65
66	0	if (dist <= MAX_DIST(s) && dist > 0 && s->prev_length < s->max_lazy_match && hash_head != 0) {
67		/* To simplify the code, we prevent matches with the string
68		* of window index 0 (in particular we have to avoid a match
69		* of the string with itself at the start of the input file).
70		*/
71	0	match_len = longest_match(s, hash_head);
72		/* longest_match() sets match_start */
73
74	0	if (match_len <= 5 && (s->strategy == Z_FILTERED)) {
75		/* If prev_match is also WANT_MIN_MATCH, match_start is garbage
76		* but we will ignore the current match anyway.
77		*/
78	0	match_len = STD_MIN_MATCH - 1;
79	0	}
80	0	}
81		/* If there was a match at the previous step and the current
82		* match is not better, output the previous match:
83		*/
84	0	if (s->prev_length >= STD_MIN_MATCH && match_len <= s->prev_length) {
85	0	unsigned int max_insert = s->strstart + s->lookahead - STD_MIN_MATCH;
86		/* Do not insert strings in hash table beyond this. */
87
88	0	Assert((s->strstart-1) <= UINT16_MAX, "strstart-1 should fit in uint16_t");
89	0	check_match(s, s->strstart - 1, s->prev_match, s->prev_length);
90
91	0	bflush = zng_tr_tally_dist(s, s->strstart -1 - s->prev_match, s->prev_length - STD_MIN_MATCH);
92
93		/* Insert in hash table all strings up to the end of the match.
94		* strstart-1 and strstart are already inserted. If there is not
95		* enough lookahead, the last two strings are not inserted in
96		* the hash table.
97		*/
98	0	s->prev_length -= 1;
99	0	s->lookahead -= s->prev_length;
100
101	0	unsigned int mov_fwd = s->prev_length - 1;
102	0	if (max_insert > s->strstart) {
103	0	unsigned int insert_cnt = mov_fwd;
104	0	if (UNLIKELY(insert_cnt > max_insert - s->strstart))
105	0	insert_cnt = max_insert - s->strstart;
106	0	insert_string_func(s, s->strstart + 1, insert_cnt);
107	0	}
108	0	s->prev_length = 0;
109	0	s->match_available = 0;
110	0	s->strstart += mov_fwd + 1;
111
112	0	if (UNLIKELY(bflush))
113	0	FLUSH_BLOCK(s, 0);
114
115	0	} else if (s->match_available) {
116		/* If there was no match at the previous position, output a
117		* single literal. If there was a match but the current match
118		* is longer, truncate the previous match to a single literal.
119		*/
120	0	bflush = zng_tr_tally_lit(s, window[s->strstart-1]);
121	0	if (UNLIKELY(bflush))
122	0	FLUSH_BLOCK_ONLY(s, 0);
123	0	s->prev_length = match_len;
124	0	s->strstart++;
125	0	s->lookahead--;
126	0	if (UNLIKELY(s->strm->avail_out == 0))
127	0	return need_more;
128	0	} else {
129		/* There is no previous match to compare with, wait for
130		* the next step to decide.
131		*/
132	0	s->prev_length = match_len;
133	0	s->match_available = 1;
134	0	s->strstart++;
135	0	s->lookahead--;
136	0	}
137	0	}
138	0	Assert(flush != Z_NO_FLUSH, "no flush?");
139	0	if (UNLIKELY(s->match_available)) {
140	0	Z_UNUSED(zng_tr_tally_lit(s, window[s->strstart-1]));
141	0	s->match_available = 0;
142	0	}
143	0	s->insert = s->strstart < (STD_MIN_MATCH - 1) ? s->strstart : (STD_MIN_MATCH - 1);
144	0	if (UNLIKELY(flush == Z_FINISH)) {
145	0	FLUSH_BLOCK(s, 1);
146	0	return finish_done;
147	0	}
148	0	if (UNLIKELY(s->sym_next))
149	0	FLUSH_BLOCK(s, 0);
150	0	return block_done;
151	0	}

Coverage Report

Created: 2026-02-14 07:07