1
2 #include "zbuild.h"
3 #include "deflate.h"
4 #include "functable.h"
5
6 #ifndef MATCH_TPL_H
7 #define MATCH_TPL_H
8
9 #ifdef UNALIGNED_OK
10 # ifdef UNALIGNED64_OK
11 typedef uint64_t bestcmp_t;
12 # else
13 typedef uint32_t bestcmp_t;
14 # endif
15 #else
16 typedef uint8_t bestcmp_t;
17 #endif
18
19 #define EARLY_EXIT_TRIGGER_LEVEL 5
20
21 #endif
22
23 /* Set match_start to the longest match starting at the given string and
24 * return its length. Matches shorter or equal to prev_length are discarded,
25 * in which case the result is equal to prev_length and match_start is garbage.
26 *
27 * IN assertions: cur_match is the head of the hash chain for the current
28 * string (strstart) and its distance is <= MAX_DIST, and prev_length >=1
29 * OUT assertion: the match length is not greater than s->lookahead
30 */
LONGEST_MATCH(deflate_state * const s,Pos cur_match)31 Z_INTERNAL uint32_t LONGEST_MATCH(deflate_state *const s, Pos cur_match) {
32 unsigned int strstart = s->strstart;
33 const unsigned wmask = s->w_mask;
34 unsigned char *window = s->window;
35 unsigned char *scan = window + strstart;
36 Z_REGISTER unsigned char *mbase_start = window;
37 Z_REGISTER unsigned char *mbase_end;
38 const Pos *prev = s->prev;
39 Pos limit;
40 uint32_t chain_length, nice_match, best_len, offset;
41 uint32_t lookahead = s->lookahead;
42 bestcmp_t scan_end;
43 #ifndef UNALIGNED_OK
44 bestcmp_t scan_end0;
45 #else
46 bestcmp_t scan_start;
47 #endif
48
49 #define GOTO_NEXT_CHAIN \
50 if (--chain_length && (cur_match = prev[cur_match & wmask]) > limit) \
51 continue; \
52 return best_len;
53
54 /* The code is optimized for MAX_MATCH-2 multiple of 16. */
55 Assert(MAX_MATCH == 258, "Code too clever");
56
57 best_len = s->prev_length ? s->prev_length : 1;
58
59 /* Calculate read offset which should only extend an extra byte
60 * to find the next best match length.
61 */
62 offset = best_len-1;
63 #ifdef UNALIGNED_OK
64 if (best_len >= sizeof(uint32_t)) {
65 offset -= 2;
66 #ifdef UNALIGNED64_OK
67 if (best_len >= sizeof(uint64_t))
68 offset -= 4;
69 #endif
70 }
71 #endif
72
73 scan_end = *(bestcmp_t *)(scan+offset);
74 #ifndef UNALIGNED_OK
75 scan_end0 = *(bestcmp_t *)(scan+offset+1);
76 #else
77 scan_start = *(bestcmp_t *)(scan);
78 #endif
79 mbase_end = (mbase_start+offset);
80
81 /* Do not waste too much time if we already have a good match */
82 chain_length = s->max_chain_length;
83 if (best_len >= s->good_match)
84 chain_length >>= 2;
85 nice_match = (uint32_t)s->nice_match;
86
87 /* Stop when cur_match becomes <= limit. To simplify the code,
88 * we prevent matches with the string of window index 0
89 */
90 limit = strstart > MAX_DIST(s) ? (Pos)(strstart - MAX_DIST(s)) : 0;
91
92 Assert((unsigned long)strstart <= s->window_size - MIN_LOOKAHEAD, "need lookahead");
93 for (;;) {
94 if (cur_match >= strstart)
95 break;
96
97 /* Skip to next match if the match length cannot increase or if the match length is
98 * less than 2. Note that the checks below for insufficient lookahead only occur
99 * occasionally for performance reasons.
100 * Therefore uninitialized memory will be accessed and conditional jumps will be made
101 * that depend on those values. However the length of the match is limited to the
102 * lookahead, so the output of deflate is not affected by the uninitialized values.
103 */
104 #ifdef UNALIGNED_OK
105 if (best_len < sizeof(uint32_t)) {
106 for (;;) {
107 if (*(uint16_t *)(mbase_end+cur_match) == (uint16_t)scan_end &&
108 *(uint16_t *)(mbase_start+cur_match) == (uint16_t)scan_start)
109 break;
110 GOTO_NEXT_CHAIN;
111 }
112 # ifdef UNALIGNED64_OK
113 } else if (best_len >= sizeof(uint64_t)) {
114 for (;;) {
115 if (*(uint64_t *)(mbase_end+cur_match) == (uint64_t)scan_end &&
116 *(uint64_t *)(mbase_start+cur_match) == (uint64_t)scan_start)
117 break;
118 GOTO_NEXT_CHAIN;
119 }
120 # endif
121 } else {
122 for (;;) {
123 if (*(uint32_t *)(mbase_end+cur_match) == (uint32_t)scan_end &&
124 *(uint32_t *)(mbase_start+cur_match) == (uint32_t)scan_start)
125 break;
126 GOTO_NEXT_CHAIN;
127 }
128 }
129 #else
130 for (;;) {
131 if (mbase_end[cur_match] == scan_end && mbase_end[cur_match+1] == scan_end0 &&
132 mbase_start[cur_match] == scan[0] && mbase_start[cur_match+1] == scan[1])
133 break;
134 GOTO_NEXT_CHAIN;
135 }
136 #endif
137 uint32_t len = COMPARE256(scan+2, mbase_start+cur_match+2) + 2;
138 Assert(scan+len <= window+(unsigned)(s->window_size-1), "wild scan");
139
140 if (len > best_len) {
141 s->match_start = cur_match;
142 /* Do not look for matches beyond the end of the input. */
143 if (len > lookahead)
144 return lookahead;
145 best_len = len;
146 if (best_len >= nice_match)
147 return best_len;
148
149 offset = best_len-1;
150 #ifdef UNALIGNED_OK
151 if (best_len >= sizeof(uint32_t)) {
152 offset -= 2;
153 #ifdef UNALIGNED64_OK
154 if (best_len >= sizeof(uint64_t))
155 offset -= 4;
156 #endif
157 }
158 #endif
159 scan_end = *(bestcmp_t *)(scan+offset);
160 #ifndef UNALIGNED_OK
161 scan_end0 = *(bestcmp_t *)(scan+offset+1);
162 #endif
163 mbase_end = (mbase_start+offset);
164 } else if (UNLIKELY(s->level < EARLY_EXIT_TRIGGER_LEVEL)) {
165 /* The probability of finding a match later if we here is pretty low, so for
166 * performance it's best to outright stop here for the lower compression levels
167 */
168 break;
169 }
170 GOTO_NEXT_CHAIN;
171 }
172
173 return best_len;
174 }
175
176 #undef LONGEST_MATCH
177 #undef COMPARE256
178 #undef COMPARE258
179