/src/c-blosc2/_deps/zlib_ng-src/match_tpl.h
Line | Count | Source |
1 | | /* match_tpl.h -- find longest match template for compare256 variants |
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 | | * Portions copyright (C) 2014-2021 Konstantin Nosov |
7 | | * Fast-zlib optimized longest_match |
8 | | * https://github.com/gildor2/fast_zlib |
9 | | */ |
10 | | |
11 | | #ifndef MATCH_TPL_H |
12 | | #define MATCH_TPL_H |
13 | | |
14 | 3.15M | #define EARLY_EXIT_TRIGGER_LEVEL 5 |
15 | | |
16 | | #endif |
17 | | |
18 | | /* Set match_start to the longest match starting at the given string and |
19 | | * return its length. Matches shorter or equal to prev_length are discarded, |
20 | | * in which case the result is equal to prev_length and match_start is garbage. |
21 | | * |
22 | | * IN assertions: cur_match is the head of the hash chain for the current |
23 | | * string (strstart) and its distance is <= MAX_DIST, and prev_length >=1 |
24 | | * OUT assertion: the match length is not greater than s->lookahead |
25 | | * |
26 | | * The LONGEST_MATCH_SLOW variant spends more time to attempt to find longer |
27 | | * matches once a match has already been found. |
28 | | */ |
29 | 5.21M | Z_INTERNAL uint32_t LONGEST_MATCH(deflate_state *const s, Pos cur_match) { |
30 | 5.21M | unsigned int strstart = s->strstart; |
31 | 5.21M | const unsigned wmask = s->w_mask; |
32 | 5.21M | unsigned char *window = s->window; |
33 | 5.21M | unsigned char *scan = window + strstart; |
34 | 5.21M | Z_REGISTER unsigned char *mbase_start = window; |
35 | 5.21M | Z_REGISTER unsigned char *mbase_end; |
36 | 5.21M | const Pos *prev = s->prev; |
37 | 5.21M | Pos limit; |
38 | | #ifdef LONGEST_MATCH_SLOW |
39 | | Pos limit_base; |
40 | | #else |
41 | | int32_t early_exit; |
42 | | #endif |
43 | 5.21M | uint32_t chain_length, nice_match, best_len, offset; |
44 | 5.21M | uint32_t lookahead = s->lookahead; |
45 | 5.21M | Pos match_offset = 0; |
46 | 5.21M | uint64_t scan_start; |
47 | 5.21M | uint64_t scan_end; |
48 | | |
49 | 5.21M | #define GOTO_NEXT_CHAIN \ |
50 | 62.5M | if (--chain_length && (cur_match = prev[cur_match & wmask]) > limit) \ |
51 | 58.0M | continue; \ |
52 | 4.50M | return best_len; |
53 | | |
54 | | /* The code is optimized for STD_MAX_MATCH-2 multiple of 16. */ |
55 | 5.21M | Assert(STD_MAX_MATCH == 258, "Code too clever"); |
56 | | |
57 | 5.21M | best_len = s->prev_length ? s->prev_length : STD_MIN_MATCH-1; |
58 | | |
59 | | /* Calculate read offset which should only extend an extra byte |
60 | | * to find the next best match length. |
61 | | */ |
62 | 5.21M | offset = best_len-1; |
63 | 5.21M | if (best_len >= sizeof(uint32_t)) { |
64 | 531k | offset -= 2; |
65 | 531k | if (best_len >= sizeof(uint64_t)) |
66 | 131k | offset -= 4; |
67 | 531k | } |
68 | | |
69 | 5.21M | scan_start = zng_memread_8(scan); |
70 | 5.21M | scan_end = zng_memread_8(scan+offset); |
71 | 5.21M | mbase_end = (mbase_start+offset); |
72 | | |
73 | | /* Do not waste too much time if we already have a good match */ |
74 | 5.21M | chain_length = s->max_chain_length; |
75 | 5.21M | if (best_len >= s->good_match) |
76 | 48.7k | chain_length >>= 2; |
77 | 5.21M | nice_match = (uint32_t)s->nice_match; |
78 | | |
79 | | /* Stop when cur_match becomes <= limit. To simplify the code, |
80 | | * we prevent matches with the string of window index 0 |
81 | | */ |
82 | 5.21M | limit = strstart > MAX_DIST(s) ? (Pos)(strstart - MAX_DIST(s)) : 0; |
83 | | #ifdef LONGEST_MATCH_SLOW |
84 | | limit_base = limit; |
85 | 2.06M | if (best_len >= STD_MIN_MATCH) { |
86 | | /* We're continuing search (lazy evaluation). */ |
87 | 485k | uint32_t i, hash; |
88 | 485k | Pos pos; |
89 | | |
90 | | /* Find a most distant chain starting from scan with index=1 (index=0 corresponds |
91 | | * to cur_match). We cannot use s->prev[strstart+1,...] immediately, because |
92 | | * these strings are not yet inserted into the hash table. |
93 | | */ |
94 | | hash = s->update_hash(0, scan[1]); |
95 | | hash = s->update_hash(hash, scan[2]); |
96 | | |
97 | 4.77M | for (i = 3; i <= best_len; i++) { |
98 | 4.29M | hash = s->update_hash(hash, scan[i]); |
99 | | |
100 | | /* If we're starting with best_len >= 3, we can use offset search. */ |
101 | 4.29M | pos = s->head[hash]; |
102 | 4.29M | if (pos < cur_match) { |
103 | 461k | match_offset = (Pos)(i - 2); |
104 | 461k | cur_match = pos; |
105 | 461k | } |
106 | 4.29M | } |
107 | | |
108 | | /* Update offset-dependent variables */ |
109 | 485k | limit = limit_base+match_offset; |
110 | 485k | if (cur_match <= limit) |
111 | 323k | goto break_matching; |
112 | 162k | mbase_start -= match_offset; |
113 | 162k | mbase_end -= match_offset; |
114 | 162k | } |
115 | | #else |
116 | 3.15M | early_exit = s->level < EARLY_EXIT_TRIGGER_LEVEL; |
117 | | #endif |
118 | 1.74M | Assert((unsigned long)strstart <= s->window_size - MIN_LOOKAHEAD, "need lookahead"); |
119 | 9.04M | for (;;) { |
120 | 9.04M | if (cur_match >= strstart) |
121 | 0 | break; |
122 | | |
123 | | /* Skip to next match if the match length cannot increase or if the match length is |
124 | | * less than 2. Note that the checks below for insufficient lookahead only occur |
125 | | * occasionally for performance reasons. |
126 | | * Therefore uninitialized memory will be accessed and conditional jumps will be made |
127 | | * that depend on those values. However the length of the match is limited to the |
128 | | * lookahead, so the output of deflate is not affected by the uninitialized values. |
129 | | */ |
130 | 9.04M | if (best_len < sizeof(uint32_t)) { |
131 | 16.6M | for (;;) { |
132 | 16.6M | if (zng_memcmp_2(mbase_end+cur_match, &scan_end) == 0 && |
133 | 3.77M | zng_memcmp_2(mbase_start+cur_match, &scan_start) == 0) |
134 | 1.83M | break; |
135 | 14.8M | GOTO_NEXT_CHAIN; |
136 | 14.8M | } |
137 | 4.91M | } else if (best_len >= sizeof(uint64_t)) { |
138 | 26.2M | for (;;) { |
139 | 26.2M | if (zng_memcmp_8(mbase_end+cur_match, &scan_end) == 0 && |
140 | 3.21M | zng_memcmp_8(mbase_start+cur_match, &scan_start) == 0) |
141 | 2.64M | break; |
142 | 23.5M | GOTO_NEXT_CHAIN; |
143 | 23.5M | } |
144 | 2.91M | } else { |
145 | 21.0M | for (;;) { |
146 | 21.0M | if (zng_memcmp_4(mbase_end+cur_match, &scan_end) == 0 && |
147 | 841k | zng_memcmp_4(mbase_start+cur_match, &scan_start) == 0) |
148 | 606k | break; |
149 | 20.4M | GOTO_NEXT_CHAIN; |
150 | 20.4M | } |
151 | 1.22M | } |
152 | 5.08M | uint32_t len = COMPARE256(scan+2, mbase_start+cur_match+2) + 2; |
153 | 5.08M | Assert(scan+len <= window+(unsigned)(s->window_size-1), "wild scan"); |
154 | | |
155 | 5.08M | if (len > best_len) { |
156 | 4.12M | uint32_t match_start = cur_match - match_offset; |
157 | 4.12M | s->match_start = match_start; |
158 | | |
159 | | /* Do not look for better matches if the current match reaches |
160 | | * or exceeds the end of the input. |
161 | | */ |
162 | 4.12M | if (len >= lookahead) |
163 | 21.3k | return lookahead; |
164 | 4.10M | best_len = len; |
165 | 4.10M | if (best_len >= nice_match) |
166 | 255k | return best_len; |
167 | | |
168 | 3.85M | offset = best_len-1; |
169 | 3.85M | if (best_len >= sizeof(uint32_t)) { |
170 | 3.48M | offset -= 2; |
171 | 3.48M | if (best_len >= sizeof(uint64_t)) |
172 | 2.00M | offset -= 4; |
173 | 3.48M | } |
174 | | |
175 | 3.85M | scan_end = zng_memread_8(scan+offset); |
176 | | |
177 | | #ifdef LONGEST_MATCH_SLOW |
178 | | /* Look for a better string offset */ |
179 | 1.51M | if (UNLIKELY(len > STD_MIN_MATCH && match_start + len < strstart)) { |
180 | 1.09M | Pos pos, next_pos; |
181 | 1.09M | uint32_t i, hash; |
182 | 1.09M | unsigned char *scan_endstr; |
183 | | |
184 | | /* Go back to offset 0 */ |
185 | | cur_match -= match_offset; |
186 | | match_offset = 0; |
187 | | next_pos = cur_match; |
188 | 44.1M | for (i = 0; i <= len - STD_MIN_MATCH; i++) { |
189 | 43.1M | pos = prev[(cur_match + i) & wmask]; |
190 | 43.1M | if (pos < next_pos) { |
191 | | /* Hash chain is more distant, use it */ |
192 | 1.24M | if (pos <= limit_base + i) |
193 | 112k | goto break_matching; |
194 | 1.13M | next_pos = pos; |
195 | 1.13M | match_offset = (Pos)i; |
196 | 1.13M | } |
197 | 43.1M | } |
198 | | /* Switch cur_match to next_pos chain */ |
199 | 979k | cur_match = next_pos; |
200 | | |
201 | | /* Try hash head at len-(STD_MIN_MATCH-1) position to see if we could get |
202 | | * a better cur_match at the end of string. Using (STD_MIN_MATCH-1) lets |
203 | | * us include one more byte into hash - the byte which will be checked |
204 | | * in main loop now, and which allows to grow match by 1. |
205 | | */ |
206 | 979k | scan_endstr = scan + len - (STD_MIN_MATCH+1); |
207 | | |
208 | 979k | hash = s->update_hash(0, scan_endstr[0]); |
209 | 979k | hash = s->update_hash(hash, scan_endstr[1]); |
210 | 979k | hash = s->update_hash(hash, scan_endstr[2]); |
211 | | |
212 | 979k | pos = s->head[hash]; |
213 | 979k | if (pos < cur_match) { |
214 | 0 | match_offset = (Pos)(len - (STD_MIN_MATCH+1)); |
215 | 0 | if (pos <= limit_base + match_offset) |
216 | 0 | goto break_matching; |
217 | 0 | cur_match = pos; |
218 | 0 | } |
219 | | |
220 | | /* Update offset-dependent variables */ |
221 | 979k | limit = limit_base+match_offset; |
222 | 979k | mbase_start = window-match_offset; |
223 | 979k | mbase_end = (mbase_start+offset); |
224 | 979k | continue; |
225 | 979k | } |
226 | 418k | #endif |
227 | 418k | mbase_end = (mbase_start+offset); |
228 | 418k | } |
229 | | #ifndef LONGEST_MATCH_SLOW |
230 | 378k | else if (UNLIKELY(early_exit)) { |
231 | | /* The probability of finding a match later if we here is pretty low, so for |
232 | | * performance it's best to outright stop here for the lower compression levels |
233 | | */ |
234 | 343 | break; |
235 | 343 | } |
236 | 2.71M | #endif |
237 | 3.71M | GOTO_NEXT_CHAIN; |
238 | 3.71M | } |
239 | 343 | return best_len; |
240 | | |
241 | | #ifdef LONGEST_MATCH_SLOW |
242 | 436k | break_matching: |
243 | | |
244 | 436k | if (best_len < s->lookahead) |
245 | 432k | return best_len; |
246 | | |
247 | 3.26k | return s->lookahead; |
248 | | #endif |
249 | 436k | } Unexecuted instantiation: longest_match_sse2 Unexecuted instantiation: longest_match_slow_sse2 Line | Count | Source | 29 | 3.15M | Z_INTERNAL uint32_t LONGEST_MATCH(deflate_state *const s, Pos cur_match) { | 30 | 3.15M | unsigned int strstart = s->strstart; | 31 | 3.15M | const unsigned wmask = s->w_mask; | 32 | 3.15M | unsigned char *window = s->window; | 33 | 3.15M | unsigned char *scan = window + strstart; | 34 | 3.15M | Z_REGISTER unsigned char *mbase_start = window; | 35 | 3.15M | Z_REGISTER unsigned char *mbase_end; | 36 | 3.15M | const Pos *prev = s->prev; | 37 | 3.15M | Pos limit; | 38 | | #ifdef LONGEST_MATCH_SLOW | 39 | | Pos limit_base; | 40 | | #else | 41 | 3.15M | int32_t early_exit; | 42 | 3.15M | #endif | 43 | 3.15M | uint32_t chain_length, nice_match, best_len, offset; | 44 | 3.15M | uint32_t lookahead = s->lookahead; | 45 | 3.15M | Pos match_offset = 0; | 46 | 3.15M | uint64_t scan_start; | 47 | 3.15M | uint64_t scan_end; | 48 | | | 49 | 3.15M | #define GOTO_NEXT_CHAIN \ | 50 | 3.15M | if (--chain_length && (cur_match = prev[cur_match & wmask]) > limit) \ | 51 | 3.15M | continue; \ | 52 | 3.15M | return best_len; | 53 | | | 54 | | /* The code is optimized for STD_MAX_MATCH-2 multiple of 16. */ | 55 | 3.15M | Assert(STD_MAX_MATCH == 258, "Code too clever"); | 56 | | | 57 | 3.15M | best_len = s->prev_length ? s->prev_length : STD_MIN_MATCH-1; | 58 | | | 59 | | /* Calculate read offset which should only extend an extra byte | 60 | | * to find the next best match length. | 61 | | */ | 62 | 3.15M | offset = best_len-1; | 63 | 3.15M | if (best_len >= sizeof(uint32_t)) { | 64 | 95.0k | offset -= 2; | 65 | 95.0k | if (best_len >= sizeof(uint64_t)) | 66 | 43.9k | offset -= 4; | 67 | 95.0k | } | 68 | | | 69 | 3.15M | scan_start = zng_memread_8(scan); | 70 | 3.15M | scan_end = zng_memread_8(scan+offset); | 71 | 3.15M | mbase_end = (mbase_start+offset); | 72 | | | 73 | | /* Do not waste too much time if we already have a good match */ | 74 | 3.15M | chain_length = s->max_chain_length; | 75 | 3.15M | if (best_len >= s->good_match) | 76 | 23.0k | chain_length >>= 2; | 77 | 3.15M | nice_match = (uint32_t)s->nice_match; | 78 | | | 79 | | /* Stop when cur_match becomes <= limit. To simplify the code, | 80 | | * we prevent matches with the string of window index 0 | 81 | | */ | 82 | 3.15M | limit = strstart > MAX_DIST(s) ? (Pos)(strstart - MAX_DIST(s)) : 0; | 83 | | #ifdef LONGEST_MATCH_SLOW | 84 | | limit_base = limit; | 85 | | if (best_len >= STD_MIN_MATCH) { | 86 | | /* We're continuing search (lazy evaluation). */ | 87 | | uint32_t i, hash; | 88 | | Pos pos; | 89 | | | 90 | | /* Find a most distant chain starting from scan with index=1 (index=0 corresponds | 91 | | * to cur_match). We cannot use s->prev[strstart+1,...] immediately, because | 92 | | * these strings are not yet inserted into the hash table. | 93 | | */ | 94 | | hash = s->update_hash(0, scan[1]); | 95 | | hash = s->update_hash(hash, scan[2]); | 96 | | | 97 | | for (i = 3; i <= best_len; i++) { | 98 | | hash = s->update_hash(hash, scan[i]); | 99 | | | 100 | | /* If we're starting with best_len >= 3, we can use offset search. */ | 101 | | pos = s->head[hash]; | 102 | | if (pos < cur_match) { | 103 | | match_offset = (Pos)(i - 2); | 104 | | cur_match = pos; | 105 | | } | 106 | | } | 107 | | | 108 | | /* Update offset-dependent variables */ | 109 | | limit = limit_base+match_offset; | 110 | | if (cur_match <= limit) | 111 | | goto break_matching; | 112 | | mbase_start -= match_offset; | 113 | | mbase_end -= match_offset; | 114 | | } | 115 | | #else | 116 | 3.15M | early_exit = s->level < EARLY_EXIT_TRIGGER_LEVEL; | 117 | 3.15M | #endif | 118 | 3.15M | Assert((unsigned long)strstart <= s->window_size - MIN_LOOKAHEAD, "need lookahead"); | 119 | 5.44M | for (;;) { | 120 | 5.44M | if (cur_match >= strstart) | 121 | 0 | break; | 122 | | | 123 | | /* Skip to next match if the match length cannot increase or if the match length is | 124 | | * less than 2. Note that the checks below for insufficient lookahead only occur | 125 | | * occasionally for performance reasons. | 126 | | * Therefore uninitialized memory will be accessed and conditional jumps will be made | 127 | | * that depend on those values. However the length of the match is limited to the | 128 | | * lookahead, so the output of deflate is not affected by the uninitialized values. | 129 | | */ | 130 | 5.44M | if (best_len < sizeof(uint32_t)) { | 131 | 3.14M | for (;;) { | 132 | 3.14M | if (zng_memcmp_2(mbase_end+cur_match, &scan_end) == 0 && | 133 | 1.07M | zng_memcmp_2(mbase_start+cur_match, &scan_start) == 0) | 134 | 1.07M | break; | 135 | 2.06M | GOTO_NEXT_CHAIN; | 136 | 2.06M | } | 137 | 3.05M | } else if (best_len >= sizeof(uint64_t)) { | 138 | 13.9M | for (;;) { | 139 | 13.9M | if (zng_memcmp_8(mbase_end+cur_match, &scan_end) == 0 && | 140 | 1.74M | zng_memcmp_8(mbase_start+cur_match, &scan_start) == 0) | 141 | 1.49M | break; | 142 | 12.4M | GOTO_NEXT_CHAIN; | 143 | 12.4M | } | 144 | 1.67M | } else { | 145 | 3.95M | for (;;) { | 146 | 3.95M | if (zng_memcmp_4(mbase_end+cur_match, &scan_end) == 0 && | 147 | 396k | zng_memcmp_4(mbase_start+cur_match, &scan_start) == 0) | 148 | 395k | break; | 149 | 3.55M | GOTO_NEXT_CHAIN; | 150 | 3.55M | } | 151 | 713k | } | 152 | 2.96M | uint32_t len = COMPARE256(scan+2, mbase_start+cur_match+2) + 2; | 153 | 2.96M | Assert(scan+len <= window+(unsigned)(s->window_size-1), "wild scan"); | 154 | | | 155 | 2.96M | if (len > best_len) { | 156 | 2.58M | uint32_t match_start = cur_match - match_offset; | 157 | 2.58M | s->match_start = match_start; | 158 | | | 159 | | /* Do not look for better matches if the current match reaches | 160 | | * or exceeds the end of the input. | 161 | | */ | 162 | 2.58M | if (len >= lookahead) | 163 | 14.8k | return lookahead; | 164 | 2.57M | best_len = len; | 165 | 2.57M | if (best_len >= nice_match) | 166 | 232k | return best_len; | 167 | | | 168 | 2.34M | offset = best_len-1; | 169 | 2.34M | if (best_len >= sizeof(uint32_t)) { | 170 | 2.34M | offset -= 2; | 171 | 2.34M | if (best_len >= sizeof(uint64_t)) | 172 | 1.35M | offset -= 4; | 173 | 2.34M | } | 174 | | | 175 | 2.34M | scan_end = zng_memread_8(scan+offset); | 176 | | | 177 | | #ifdef LONGEST_MATCH_SLOW | 178 | | /* Look for a better string offset */ | 179 | | if (UNLIKELY(len > STD_MIN_MATCH && match_start + len < strstart)) { | 180 | | Pos pos, next_pos; | 181 | | uint32_t i, hash; | 182 | | unsigned char *scan_endstr; | 183 | | | 184 | | /* Go back to offset 0 */ | 185 | | cur_match -= match_offset; | 186 | | match_offset = 0; | 187 | | next_pos = cur_match; | 188 | | for (i = 0; i <= len - STD_MIN_MATCH; i++) { | 189 | | pos = prev[(cur_match + i) & wmask]; | 190 | | if (pos < next_pos) { | 191 | | /* Hash chain is more distant, use it */ | 192 | | if (pos <= limit_base + i) | 193 | | goto break_matching; | 194 | | next_pos = pos; | 195 | | match_offset = (Pos)i; | 196 | | } | 197 | | } | 198 | | /* Switch cur_match to next_pos chain */ | 199 | | cur_match = next_pos; | 200 | | | 201 | | /* Try hash head at len-(STD_MIN_MATCH-1) position to see if we could get | 202 | | * a better cur_match at the end of string. Using (STD_MIN_MATCH-1) lets | 203 | | * us include one more byte into hash - the byte which will be checked | 204 | | * in main loop now, and which allows to grow match by 1. | 205 | | */ | 206 | | scan_endstr = scan + len - (STD_MIN_MATCH+1); | 207 | | | 208 | | hash = s->update_hash(0, scan_endstr[0]); | 209 | | hash = s->update_hash(hash, scan_endstr[1]); | 210 | | hash = s->update_hash(hash, scan_endstr[2]); | 211 | | | 212 | | pos = s->head[hash]; | 213 | | if (pos < cur_match) { | 214 | | match_offset = (Pos)(len - (STD_MIN_MATCH+1)); | 215 | | if (pos <= limit_base + match_offset) | 216 | | goto break_matching; | 217 | | cur_match = pos; | 218 | | } | 219 | | | 220 | | /* Update offset-dependent variables */ | 221 | | limit = limit_base+match_offset; | 222 | | mbase_start = window-match_offset; | 223 | | mbase_end = (mbase_start+offset); | 224 | | continue; | 225 | | } | 226 | | #endif | 227 | 2.34M | mbase_end = (mbase_start+offset); | 228 | 2.34M | } | 229 | 378k | #ifndef LONGEST_MATCH_SLOW | 230 | 378k | else if (UNLIKELY(early_exit)) { | 231 | | /* The probability of finding a match later if we here is pretty low, so for | 232 | | * performance it's best to outright stop here for the lower compression levels | 233 | | */ | 234 | 343 | break; | 235 | 343 | } | 236 | 2.71M | #endif | 237 | 2.71M | GOTO_NEXT_CHAIN; | 238 | 2.71M | } | 239 | 343 | return best_len; | 240 | | | 241 | | #ifdef LONGEST_MATCH_SLOW | 242 | | break_matching: | 243 | | | 244 | | if (best_len < s->lookahead) | 245 | | return best_len; | 246 | | | 247 | | return s->lookahead; | 248 | | #endif | 249 | 3.15M | } |
Line | Count | Source | 29 | 2.06M | Z_INTERNAL uint32_t LONGEST_MATCH(deflate_state *const s, Pos cur_match) { | 30 | 2.06M | unsigned int strstart = s->strstart; | 31 | 2.06M | const unsigned wmask = s->w_mask; | 32 | 2.06M | unsigned char *window = s->window; | 33 | 2.06M | unsigned char *scan = window + strstart; | 34 | 2.06M | Z_REGISTER unsigned char *mbase_start = window; | 35 | 2.06M | Z_REGISTER unsigned char *mbase_end; | 36 | 2.06M | const Pos *prev = s->prev; | 37 | 2.06M | Pos limit; | 38 | 2.06M | #ifdef LONGEST_MATCH_SLOW | 39 | 2.06M | Pos limit_base; | 40 | | #else | 41 | | int32_t early_exit; | 42 | | #endif | 43 | 2.06M | uint32_t chain_length, nice_match, best_len, offset; | 44 | 2.06M | uint32_t lookahead = s->lookahead; | 45 | 2.06M | Pos match_offset = 0; | 46 | 2.06M | uint64_t scan_start; | 47 | 2.06M | uint64_t scan_end; | 48 | | | 49 | 2.06M | #define GOTO_NEXT_CHAIN \ | 50 | 2.06M | if (--chain_length && (cur_match = prev[cur_match & wmask]) > limit) \ | 51 | 2.06M | continue; \ | 52 | 2.06M | return best_len; | 53 | | | 54 | | /* The code is optimized for STD_MAX_MATCH-2 multiple of 16. */ | 55 | 2.06M | Assert(STD_MAX_MATCH == 258, "Code too clever"); | 56 | | | 57 | 2.06M | best_len = s->prev_length ? s->prev_length : STD_MIN_MATCH-1; | 58 | | | 59 | | /* Calculate read offset which should only extend an extra byte | 60 | | * to find the next best match length. | 61 | | */ | 62 | 2.06M | offset = best_len-1; | 63 | 2.06M | if (best_len >= sizeof(uint32_t)) { | 64 | 436k | offset -= 2; | 65 | 436k | if (best_len >= sizeof(uint64_t)) | 66 | 87.4k | offset -= 4; | 67 | 436k | } | 68 | | | 69 | 2.06M | scan_start = zng_memread_8(scan); | 70 | 2.06M | scan_end = zng_memread_8(scan+offset); | 71 | 2.06M | mbase_end = (mbase_start+offset); | 72 | | | 73 | | /* Do not waste too much time if we already have a good match */ | 74 | 2.06M | chain_length = s->max_chain_length; | 75 | 2.06M | if (best_len >= s->good_match) | 76 | 25.6k | chain_length >>= 2; | 77 | 2.06M | nice_match = (uint32_t)s->nice_match; | 78 | | | 79 | | /* Stop when cur_match becomes <= limit. To simplify the code, | 80 | | * we prevent matches with the string of window index 0 | 81 | | */ | 82 | 2.06M | limit = strstart > MAX_DIST(s) ? (Pos)(strstart - MAX_DIST(s)) : 0; | 83 | 2.06M | #ifdef LONGEST_MATCH_SLOW | 84 | 2.06M | limit_base = limit; | 85 | 2.06M | if (best_len >= STD_MIN_MATCH) { | 86 | | /* We're continuing search (lazy evaluation). */ | 87 | 485k | uint32_t i, hash; | 88 | 485k | Pos pos; | 89 | | | 90 | | /* Find a most distant chain starting from scan with index=1 (index=0 corresponds | 91 | | * to cur_match). We cannot use s->prev[strstart+1,...] immediately, because | 92 | | * these strings are not yet inserted into the hash table. | 93 | | */ | 94 | 485k | hash = s->update_hash(0, scan[1]); | 95 | 485k | hash = s->update_hash(hash, scan[2]); | 96 | | | 97 | 4.77M | for (i = 3; i <= best_len; i++) { | 98 | 4.29M | hash = s->update_hash(hash, scan[i]); | 99 | | | 100 | | /* If we're starting with best_len >= 3, we can use offset search. */ | 101 | 4.29M | pos = s->head[hash]; | 102 | 4.29M | if (pos < cur_match) { | 103 | 461k | match_offset = (Pos)(i - 2); | 104 | 461k | cur_match = pos; | 105 | 461k | } | 106 | 4.29M | } | 107 | | | 108 | | /* Update offset-dependent variables */ | 109 | 485k | limit = limit_base+match_offset; | 110 | 485k | if (cur_match <= limit) | 111 | 323k | goto break_matching; | 112 | 162k | mbase_start -= match_offset; | 113 | 162k | mbase_end -= match_offset; | 114 | 162k | } | 115 | | #else | 116 | | early_exit = s->level < EARLY_EXIT_TRIGGER_LEVEL; | 117 | | #endif | 118 | 1.74M | Assert((unsigned long)strstart <= s->window_size - MIN_LOOKAHEAD, "need lookahead"); | 119 | 3.59M | for (;;) { | 120 | 3.59M | if (cur_match >= strstart) | 121 | 0 | break; | 122 | | | 123 | | /* Skip to next match if the match length cannot increase or if the match length is | 124 | | * less than 2. Note that the checks below for insufficient lookahead only occur | 125 | | * occasionally for performance reasons. | 126 | | * Therefore uninitialized memory will be accessed and conditional jumps will be made | 127 | | * that depend on those values. However the length of the match is limited to the | 128 | | * lookahead, so the output of deflate is not affected by the uninitialized values. | 129 | | */ | 130 | 3.59M | if (best_len < sizeof(uint32_t)) { | 131 | 13.5M | for (;;) { | 132 | 13.5M | if (zng_memcmp_2(mbase_end+cur_match, &scan_end) == 0 && | 133 | 2.69M | zng_memcmp_2(mbase_start+cur_match, &scan_start) == 0) | 134 | 758k | break; | 135 | 12.7M | GOTO_NEXT_CHAIN; | 136 | 12.7M | } | 137 | 1.85M | } else if (best_len >= sizeof(uint64_t)) { | 138 | 12.3M | for (;;) { | 139 | 12.3M | if (zng_memcmp_8(mbase_end+cur_match, &scan_end) == 0 && | 140 | 1.46M | zng_memcmp_8(mbase_start+cur_match, &scan_start) == 0) | 141 | 1.15M | break; | 142 | 11.1M | GOTO_NEXT_CHAIN; | 143 | 11.1M | } | 144 | 1.23M | } else { | 145 | 17.1M | for (;;) { | 146 | 17.1M | if (zng_memcmp_4(mbase_end+cur_match, &scan_end) == 0 && | 147 | 445k | zng_memcmp_4(mbase_start+cur_match, &scan_start) == 0) | 148 | 210k | break; | 149 | 16.8M | GOTO_NEXT_CHAIN; | 150 | 16.8M | } | 151 | 506k | } | 152 | 2.12M | uint32_t len = COMPARE256(scan+2, mbase_start+cur_match+2) + 2; | 153 | 2.12M | Assert(scan+len <= window+(unsigned)(s->window_size-1), "wild scan"); | 154 | | | 155 | 2.12M | if (len > best_len) { | 156 | 1.54M | uint32_t match_start = cur_match - match_offset; | 157 | 1.54M | s->match_start = match_start; | 158 | | | 159 | | /* Do not look for better matches if the current match reaches | 160 | | * or exceeds the end of the input. | 161 | | */ | 162 | 1.54M | if (len >= lookahead) | 163 | 6.51k | return lookahead; | 164 | 1.53M | best_len = len; | 165 | 1.53M | if (best_len >= nice_match) | 166 | 23.2k | return best_len; | 167 | | | 168 | 1.51M | offset = best_len-1; | 169 | 1.51M | if (best_len >= sizeof(uint32_t)) { | 170 | 1.14M | offset -= 2; | 171 | 1.14M | if (best_len >= sizeof(uint64_t)) | 172 | 648k | offset -= 4; | 173 | 1.14M | } | 174 | | | 175 | 1.51M | scan_end = zng_memread_8(scan+offset); | 176 | | | 177 | 1.51M | #ifdef LONGEST_MATCH_SLOW | 178 | | /* Look for a better string offset */ | 179 | 1.51M | if (UNLIKELY(len > STD_MIN_MATCH && match_start + len < strstart)) { | 180 | 1.09M | Pos pos, next_pos; | 181 | 1.09M | uint32_t i, hash; | 182 | 1.09M | unsigned char *scan_endstr; | 183 | | | 184 | | /* Go back to offset 0 */ | 185 | 1.09M | cur_match -= match_offset; | 186 | 1.09M | match_offset = 0; | 187 | 1.09M | next_pos = cur_match; | 188 | 44.1M | for (i = 0; i <= len - STD_MIN_MATCH; i++) { | 189 | 43.1M | pos = prev[(cur_match + i) & wmask]; | 190 | 43.1M | if (pos < next_pos) { | 191 | | /* Hash chain is more distant, use it */ | 192 | 1.24M | if (pos <= limit_base + i) | 193 | 112k | goto break_matching; | 194 | 1.13M | next_pos = pos; | 195 | 1.13M | match_offset = (Pos)i; | 196 | 1.13M | } | 197 | 43.1M | } | 198 | | /* Switch cur_match to next_pos chain */ | 199 | 979k | cur_match = next_pos; | 200 | | | 201 | | /* Try hash head at len-(STD_MIN_MATCH-1) position to see if we could get | 202 | | * a better cur_match at the end of string. Using (STD_MIN_MATCH-1) lets | 203 | | * us include one more byte into hash - the byte which will be checked | 204 | | * in main loop now, and which allows to grow match by 1. | 205 | | */ | 206 | 979k | scan_endstr = scan + len - (STD_MIN_MATCH+1); | 207 | | | 208 | 979k | hash = s->update_hash(0, scan_endstr[0]); | 209 | 979k | hash = s->update_hash(hash, scan_endstr[1]); | 210 | 979k | hash = s->update_hash(hash, scan_endstr[2]); | 211 | | | 212 | 979k | pos = s->head[hash]; | 213 | 979k | if (pos < cur_match) { | 214 | 0 | match_offset = (Pos)(len - (STD_MIN_MATCH+1)); | 215 | 0 | if (pos <= limit_base + match_offset) | 216 | 0 | goto break_matching; | 217 | 0 | cur_match = pos; | 218 | 0 | } | 219 | | | 220 | | /* Update offset-dependent variables */ | 221 | 979k | limit = limit_base+match_offset; | 222 | 979k | mbase_start = window-match_offset; | 223 | 979k | mbase_end = (mbase_start+offset); | 224 | 979k | continue; | 225 | 979k | } | 226 | 418k | #endif | 227 | 418k | mbase_end = (mbase_start+offset); | 228 | 418k | } | 229 | | #ifndef LONGEST_MATCH_SLOW | 230 | | else if (UNLIKELY(early_exit)) { | 231 | | /* The probability of finding a match later if we here is pretty low, so for | 232 | | * performance it's best to outright stop here for the lower compression levels | 233 | | */ | 234 | | break; | 235 | | } | 236 | | #endif | 237 | 1.00M | GOTO_NEXT_CHAIN; | 238 | 1.00M | } | 239 | 0 | return best_len; | 240 | | | 241 | 0 | #ifdef LONGEST_MATCH_SLOW | 242 | 436k | break_matching: | 243 | | | 244 | 436k | if (best_len < s->lookahead) | 245 | 432k | return best_len; | 246 | | | 247 | 3.26k | return s->lookahead; | 248 | 436k | #endif | 249 | 436k | } |
Unexecuted instantiation: longest_match_avx512 Unexecuted instantiation: longest_match_slow_avx512 |
250 | | |
251 | | #undef LONGEST_MATCH_SLOW |
252 | | #undef LONGEST_MATCH |