1///////////////////////////////////////////////////////////////////////////////
2//
3/// \file lz_encoder_mf.c
4/// \brief Match finders
5///
6// Authors: Igor Pavlov
7// Lasse Collin
8//
9// This file has been put into the public domain.
10// You can do whatever you want with this file.
11//
12///////////////////////////////////////////////////////////////////////////////
13
14#include "lz_encoder.h"
15#include "lz_encoder_hash.h"
16
17
18/// \brief Find matches starting from the current byte
19///
20/// \return The length of the longest match found
21extern uint32_t
22lzma_mf_find(lzma_mf *mf, uint32_t *count_ptr, lzma_match *matches)
23{
24 // Call the match finder. It returns the number of length-distance
25 // pairs found.
26 // FIXME: Minimum count is zero, what _exactly_ is the maximum?
27 const uint32_t count = mf->find(mf, matches);
28
29 // Length of the longest match; assume that no matches were found
30 // and thus the maximum length is zero.
31 uint32_t len_best = 0;
32
33 if (count > 0) {
34#ifndef NDEBUG
35 // Validate the matches.
36 for (uint32_t i = 0; i < count; ++i) {
37 assert(matches[i].len <= mf->nice_len);
38 assert(matches[i].dist < mf->read_pos);
39 assert(memcmp(mf_ptr(mf) - 1,
40 mf_ptr(mf) - matches[i].dist - 2,
41 matches[i].len) == 0);
42 }
43#endif
44
45 // The last used element in the array contains
46 // the longest match.
47 len_best = matches[count - 1].len;
48
49 // If a match of maximum search length was found, try to
50 // extend the match to maximum possible length.
51 if (len_best == mf->nice_len) {
52 // The limit for the match length is either the
53 // maximum match length supported by the LZ-based
54 // encoder or the number of bytes left in the
55 // dictionary, whichever is smaller.
56 uint32_t limit = mf_avail(mf) + 1;
57 if (limit > mf->match_len_max)
58 limit = mf->match_len_max;
59
60 // Pointer to the byte we just ran through
61 // the match finder.
62 const uint8_t *p1 = mf_ptr(mf) - 1;
63
64 // Pointer to the beginning of the match. We need -1
65 // here because the match distances are zero based.
66 const uint8_t *p2 = p1 - matches[count - 1].dist - 1;
67
68 while (len_best < limit
69 && p1[len_best] == p2[len_best])
70 ++len_best;
71 }
72 }
73
74 *count_ptr = count;
75
76 // Finally update the read position to indicate that match finder was
77 // run for this dictionary offset.
78 ++mf->read_ahead;
79
80 return len_best;
81}
82
83
84/// Hash value to indicate unused element in the hash. Since we start the
85/// positions from dict_size + 1, zero is always too far to qualify
86/// as usable match position.
87#define EMPTY_HASH_VALUE 0
88
89
90/// Normalization must be done when lzma_mf.offset + lzma_mf.read_pos
91/// reaches MUST_NORMALIZE_POS.
92#define MUST_NORMALIZE_POS UINT32_MAX
93
94
95/// \brief Normalizes hash values
96///
97/// The hash arrays store positions of match candidates. The positions are
98/// relative to an arbitrary offset that is not the same as the absolute
99/// offset in the input stream. The relative position of the current byte
100/// is lzma_mf.offset + lzma_mf.read_pos. The distances of the matches are
101/// the differences of the current read position and the position found from
102/// the hash.
103///
104/// To prevent integer overflows of the offsets stored in the hash arrays,
105/// we need to "normalize" the stored values now and then. During the
106/// normalization, we drop values that indicate distance greater than the
107/// dictionary size, thus making space for new values.
108static void
109normalize(lzma_mf *mf)
110{
111 assert(mf->read_pos + mf->offset == MUST_NORMALIZE_POS);
112
113 // In future we may not want to touch the lowest bits, because there
114 // may be match finders that use larger resolution than one byte.
115 const uint32_t subvalue
116 = (MUST_NORMALIZE_POS - mf->cyclic_size);
117 // & (~(UINT32_C(1) << 10) - 1);
118
119 const uint32_t count = mf->hash_size_sum + mf->sons_count;
120 uint32_t *hash = mf->hash;
121
122 for (uint32_t i = 0; i < count; ++i) {
123 // If the distance is greater than the dictionary size,
124 // we can simply mark the hash element as empty.
125 //
126 // NOTE: Only the first mf->hash_size_sum elements are
127 // initialized for sure. There may be uninitialized elements
128 // in mf->son. Since we go through both mf->hash and
129 // mf->son here in normalization, Valgrind may complain
130 // that the "if" below depends on uninitialized value. In
131 // this case it is safe to ignore the warning. See also the
132 // comments in lz_encoder_init() in lz_encoder.c.
133 if (hash[i] <= subvalue)
134 hash[i] = EMPTY_HASH_VALUE;
135 else
136 hash[i] -= subvalue;
137 }
138
139 // Update offset to match the new locations.
140 mf->offset -= subvalue;
141
142 return;
143}
144
145
146/// Mark the current byte as processed from point of view of the match finder.
147static void
148move_pos(lzma_mf *mf)
149{
150 if (++mf->cyclic_pos == mf->cyclic_size)
151 mf->cyclic_pos = 0;
152
153 ++mf->read_pos;
154 assert(mf->read_pos <= mf->write_pos);
155
156 if (unlikely(mf->read_pos + mf->offset == UINT32_MAX))
157 normalize(mf);
158}
159
160
161/// When flushing, we cannot run the match finder unless there is nice_len
162/// bytes available in the dictionary. Instead, we skip running the match
163/// finder (indicating that no match was found), and count how many bytes we
164/// have ignored this way.
165///
166/// When new data is given after the flushing was completed, the match finder
167/// is restarted by rewinding mf->read_pos backwards by mf->pending. Then
168/// the missed bytes are added to the hash using the match finder's skip
169/// function (with small amount of input, it may start using mf->pending
170/// again if flushing).
171///
172/// Due to this rewinding, we don't touch cyclic_pos or test for
173/// normalization. It will be done when the match finder's skip function
174/// catches up after a flush.
175static void
176move_pending(lzma_mf *mf)
177{
178 ++mf->read_pos;
179 assert(mf->read_pos <= mf->write_pos);
180 ++mf->pending;
181}
182
183
184/// Calculate len_limit and determine if there is enough input to run
185/// the actual match finder code. Sets up "cur" and "pos". This macro
186/// is used by all find functions and binary tree skip functions. Hash
187/// chain skip function doesn't need len_limit so a simpler code is used
188/// in them.
189#define header(is_bt, len_min, ret_op) \
190 uint32_t len_limit = mf_avail(mf); \
191 if (mf->nice_len <= len_limit) { \
192 len_limit = mf->nice_len; \
193 } else if (len_limit < (len_min) \
194 || (is_bt && mf->action == LZMA_SYNC_FLUSH)) { \
195 assert(mf->action != LZMA_RUN); \
196 move_pending(mf); \
197 ret_op; \
198 } \
199 const uint8_t *cur = mf_ptr(mf); \
200 const uint32_t pos = mf->read_pos + mf->offset
201
202
203/// Header for find functions. "return 0" indicates that zero matches
204/// were found.
205#define header_find(is_bt, len_min) \
206 header(is_bt, len_min, return 0); \
207 uint32_t matches_count = 0
208
209
210/// Header for a loop in a skip function. "continue" tells to skip the rest
211/// of the code in the loop.
212#define header_skip(is_bt, len_min) \
213 header(is_bt, len_min, continue)
214
215
216/// Calls hc_find_func() or bt_find_func() and calculates the total number
217/// of matches found. Updates the dictionary position and returns the number
218/// of matches found.
219#define call_find(func, len_best) \
220do { \
221 matches_count = func(len_limit, pos, cur, cur_match, mf->depth, \
222 mf->son, mf->cyclic_pos, mf->cyclic_size, \
223 matches + matches_count, len_best) \
224 - matches; \
225 move_pos(mf); \
226 return matches_count; \
227} while (0)
228
229
230////////////////
231// Hash Chain //
232////////////////
233
234#if defined(HAVE_MF_HC3) || defined(HAVE_MF_HC4)
235///
236///
237/// \param len_limit Don't look for matches longer than len_limit.
238/// \param pos lzma_mf.read_pos + lzma_mf.offset
239/// \param cur Pointer to current byte (mf_ptr(mf))
240/// \param cur_match Start position of the current match candidate
241/// \param depth Maximum length of the hash chain
242/// \param son lzma_mf.son (contains the hash chain)
243/// \param cyclic_pos
244/// \param cyclic_size
245/// \param matches Array to hold the matches.
246/// \param len_best The length of the longest match found so far.
247static lzma_match *
248hc_find_func(
249 const uint32_t len_limit,
250 const uint32_t pos,
251 const uint8_t *const cur,
252 uint32_t cur_match,
253 uint32_t depth,
254 uint32_t *const son,
255 const uint32_t cyclic_pos,
256 const uint32_t cyclic_size,
257 lzma_match *matches,
258 uint32_t len_best)
259{
260 son[cyclic_pos] = cur_match;
261
262 while (true) {
263 const uint32_t delta = pos - cur_match;
264 if (depth-- == 0 || delta >= cyclic_size)
265 return matches;
266
267 const uint8_t *const pb = cur - delta;
268 cur_match = son[cyclic_pos - delta
269 + (delta > cyclic_pos ? cyclic_size : 0)];
270
271 if (pb[len_best] == cur[len_best] && pb[0] == cur[0]) {
272 uint32_t len = 0;
273 while (++len != len_limit)
274 if (pb[len] != cur[len])
275 break;
276
277 if (len_best < len) {
278 len_best = len;
279 matches->len = len;
280 matches->dist = delta - 1;
281 ++matches;
282
283 if (len == len_limit)
284 return matches;
285 }
286 }
287 }
288}
289
290
291#define hc_find(len_best) \
292 call_find(hc_find_func, len_best)
293
294
295#define hc_skip() \
296do { \
297 mf->son[mf->cyclic_pos] = cur_match; \
298 move_pos(mf); \
299} while (0)
300
301#endif
302
303
304#ifdef HAVE_MF_HC3
305extern uint32_t
306lzma_mf_hc3_find(lzma_mf *mf, lzma_match *matches)
307{
308 header_find(false, 3);
309
310 hash_3_calc();
311
312 const uint32_t delta2 = pos - mf->hash[hash_2_value];
313 const uint32_t cur_match = mf->hash[FIX_3_HASH_SIZE + hash_value];
314
315 mf->hash[hash_2_value] = pos;
316 mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
317
318 uint32_t len_best = 2;
319
320 if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) {
321 for ( ; len_best != len_limit; ++len_best)
322 if (*(cur + len_best - delta2) != cur[len_best])
323 break;
324
325 matches[0].len = len_best;
326 matches[0].dist = delta2 - 1;
327 matches_count = 1;
328
329 if (len_best == len_limit) {
330 hc_skip();
331 return 1; // matches_count
332 }
333 }
334
335 hc_find(len_best);
336}
337
338
339extern void
340lzma_mf_hc3_skip(lzma_mf *mf, uint32_t amount)
341{
342 do {
343 if (mf_avail(mf) < 3) {
344 move_pending(mf);
345 continue;
346 }
347
348 const uint8_t *cur = mf_ptr(mf);
349 const uint32_t pos = mf->read_pos + mf->offset;
350
351 hash_3_calc();
352
353 const uint32_t cur_match
354 = mf->hash[FIX_3_HASH_SIZE + hash_value];
355
356 mf->hash[hash_2_value] = pos;
357 mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
358
359 hc_skip();
360
361 } while (--amount != 0);
362}
363#endif
364
365
366#ifdef HAVE_MF_HC4
367extern uint32_t
368lzma_mf_hc4_find(lzma_mf *mf, lzma_match *matches)
369{
370 header_find(false, 4);
371
372 hash_4_calc();
373
374 uint32_t delta2 = pos - mf->hash[hash_2_value];
375 const uint32_t delta3
376 = pos - mf->hash[FIX_3_HASH_SIZE + hash_3_value];
377 const uint32_t cur_match = mf->hash[FIX_4_HASH_SIZE + hash_value];
378
379 mf->hash[hash_2_value ] = pos;
380 mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
381 mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
382
383 uint32_t len_best = 1;
384
385 if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) {
386 len_best = 2;
387 matches[0].len = 2;
388 matches[0].dist = delta2 - 1;
389 matches_count = 1;
390 }
391
392 if (delta2 != delta3 && delta3 < mf->cyclic_size
393 && *(cur - delta3) == *cur) {
394 len_best = 3;
395 matches[matches_count++].dist = delta3 - 1;
396 delta2 = delta3;
397 }
398
399 if (matches_count != 0) {
400 for ( ; len_best != len_limit; ++len_best)
401 if (*(cur + len_best - delta2) != cur[len_best])
402 break;
403
404 matches[matches_count - 1].len = len_best;
405
406 if (len_best == len_limit) {
407 hc_skip();
408 return matches_count;
409 }
410 }
411
412 if (len_best < 3)
413 len_best = 3;
414
415 hc_find(len_best);
416}
417
418
419extern void
420lzma_mf_hc4_skip(lzma_mf *mf, uint32_t amount)
421{
422 do {
423 if (mf_avail(mf) < 4) {
424 move_pending(mf);
425 continue;
426 }
427
428 const uint8_t *cur = mf_ptr(mf);
429 const uint32_t pos = mf->read_pos + mf->offset;
430
431 hash_4_calc();
432
433 const uint32_t cur_match
434 = mf->hash[FIX_4_HASH_SIZE + hash_value];
435
436 mf->hash[hash_2_value] = pos;
437 mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
438 mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
439
440 hc_skip();
441
442 } while (--amount != 0);
443}
444#endif
445
446
447/////////////////
448// Binary Tree //
449/////////////////
450
451#if defined(HAVE_MF_BT2) || defined(HAVE_MF_BT3) || defined(HAVE_MF_BT4)
452static lzma_match *
453bt_find_func(
454 const uint32_t len_limit,
455 const uint32_t pos,
456 const uint8_t *const cur,
457 uint32_t cur_match,
458 uint32_t depth,
459 uint32_t *const son,
460 const uint32_t cyclic_pos,
461 const uint32_t cyclic_size,
462 lzma_match *matches,
463 uint32_t len_best)
464{
465 uint32_t *ptr0 = son + (cyclic_pos << 1) + 1;
466 uint32_t *ptr1 = son + (cyclic_pos << 1);
467
468 uint32_t len0 = 0;
469 uint32_t len1 = 0;
470
471 while (true) {
472 const uint32_t delta = pos - cur_match;
473 if (depth-- == 0 || delta >= cyclic_size) {
474 *ptr0 = EMPTY_HASH_VALUE;
475 *ptr1 = EMPTY_HASH_VALUE;
476 return matches;
477 }
478
479 uint32_t *const pair = son + ((cyclic_pos - delta
480 + (delta > cyclic_pos ? cyclic_size : 0))
481 << 1);
482
483 const uint8_t *const pb = cur - delta;
| 1///////////////////////////////////////////////////////////////////////////////
2//
3/// \file lz_encoder_mf.c
4/// \brief Match finders
5///
6// Authors: Igor Pavlov
7// Lasse Collin
8//
9// This file has been put into the public domain.
10// You can do whatever you want with this file.
11//
12///////////////////////////////////////////////////////////////////////////////
13
14#include "lz_encoder.h"
15#include "lz_encoder_hash.h"
16
17
18/// \brief Find matches starting from the current byte
19///
20/// \return The length of the longest match found
21extern uint32_t
22lzma_mf_find(lzma_mf *mf, uint32_t *count_ptr, lzma_match *matches)
23{
24 // Call the match finder. It returns the number of length-distance
25 // pairs found.
26 // FIXME: Minimum count is zero, what _exactly_ is the maximum?
27 const uint32_t count = mf->find(mf, matches);
28
29 // Length of the longest match; assume that no matches were found
30 // and thus the maximum length is zero.
31 uint32_t len_best = 0;
32
33 if (count > 0) {
34#ifndef NDEBUG
35 // Validate the matches.
36 for (uint32_t i = 0; i < count; ++i) {
37 assert(matches[i].len <= mf->nice_len);
38 assert(matches[i].dist < mf->read_pos);
39 assert(memcmp(mf_ptr(mf) - 1,
40 mf_ptr(mf) - matches[i].dist - 2,
41 matches[i].len) == 0);
42 }
43#endif
44
45 // The last used element in the array contains
46 // the longest match.
47 len_best = matches[count - 1].len;
48
49 // If a match of maximum search length was found, try to
50 // extend the match to maximum possible length.
51 if (len_best == mf->nice_len) {
52 // The limit for the match length is either the
53 // maximum match length supported by the LZ-based
54 // encoder or the number of bytes left in the
55 // dictionary, whichever is smaller.
56 uint32_t limit = mf_avail(mf) + 1;
57 if (limit > mf->match_len_max)
58 limit = mf->match_len_max;
59
60 // Pointer to the byte we just ran through
61 // the match finder.
62 const uint8_t *p1 = mf_ptr(mf) - 1;
63
64 // Pointer to the beginning of the match. We need -1
65 // here because the match distances are zero based.
66 const uint8_t *p2 = p1 - matches[count - 1].dist - 1;
67
68 while (len_best < limit
69 && p1[len_best] == p2[len_best])
70 ++len_best;
71 }
72 }
73
74 *count_ptr = count;
75
76 // Finally update the read position to indicate that match finder was
77 // run for this dictionary offset.
78 ++mf->read_ahead;
79
80 return len_best;
81}
82
83
84/// Hash value to indicate unused element in the hash. Since we start the
85/// positions from dict_size + 1, zero is always too far to qualify
86/// as usable match position.
87#define EMPTY_HASH_VALUE 0
88
89
90/// Normalization must be done when lzma_mf.offset + lzma_mf.read_pos
91/// reaches MUST_NORMALIZE_POS.
92#define MUST_NORMALIZE_POS UINT32_MAX
93
94
95/// \brief Normalizes hash values
96///
97/// The hash arrays store positions of match candidates. The positions are
98/// relative to an arbitrary offset that is not the same as the absolute
99/// offset in the input stream. The relative position of the current byte
100/// is lzma_mf.offset + lzma_mf.read_pos. The distances of the matches are
101/// the differences of the current read position and the position found from
102/// the hash.
103///
104/// To prevent integer overflows of the offsets stored in the hash arrays,
105/// we need to "normalize" the stored values now and then. During the
106/// normalization, we drop values that indicate distance greater than the
107/// dictionary size, thus making space for new values.
108static void
109normalize(lzma_mf *mf)
110{
111 assert(mf->read_pos + mf->offset == MUST_NORMALIZE_POS);
112
113 // In future we may not want to touch the lowest bits, because there
114 // may be match finders that use larger resolution than one byte.
115 const uint32_t subvalue
116 = (MUST_NORMALIZE_POS - mf->cyclic_size);
117 // & (~(UINT32_C(1) << 10) - 1);
118
119 const uint32_t count = mf->hash_size_sum + mf->sons_count;
120 uint32_t *hash = mf->hash;
121
122 for (uint32_t i = 0; i < count; ++i) {
123 // If the distance is greater than the dictionary size,
124 // we can simply mark the hash element as empty.
125 //
126 // NOTE: Only the first mf->hash_size_sum elements are
127 // initialized for sure. There may be uninitialized elements
128 // in mf->son. Since we go through both mf->hash and
129 // mf->son here in normalization, Valgrind may complain
130 // that the "if" below depends on uninitialized value. In
131 // this case it is safe to ignore the warning. See also the
132 // comments in lz_encoder_init() in lz_encoder.c.
133 if (hash[i] <= subvalue)
134 hash[i] = EMPTY_HASH_VALUE;
135 else
136 hash[i] -= subvalue;
137 }
138
139 // Update offset to match the new locations.
140 mf->offset -= subvalue;
141
142 return;
143}
144
145
146/// Mark the current byte as processed from point of view of the match finder.
147static void
148move_pos(lzma_mf *mf)
149{
150 if (++mf->cyclic_pos == mf->cyclic_size)
151 mf->cyclic_pos = 0;
152
153 ++mf->read_pos;
154 assert(mf->read_pos <= mf->write_pos);
155
156 if (unlikely(mf->read_pos + mf->offset == UINT32_MAX))
157 normalize(mf);
158}
159
160
161/// When flushing, we cannot run the match finder unless there is nice_len
162/// bytes available in the dictionary. Instead, we skip running the match
163/// finder (indicating that no match was found), and count how many bytes we
164/// have ignored this way.
165///
166/// When new data is given after the flushing was completed, the match finder
167/// is restarted by rewinding mf->read_pos backwards by mf->pending. Then
168/// the missed bytes are added to the hash using the match finder's skip
169/// function (with small amount of input, it may start using mf->pending
170/// again if flushing).
171///
172/// Due to this rewinding, we don't touch cyclic_pos or test for
173/// normalization. It will be done when the match finder's skip function
174/// catches up after a flush.
175static void
176move_pending(lzma_mf *mf)
177{
178 ++mf->read_pos;
179 assert(mf->read_pos <= mf->write_pos);
180 ++mf->pending;
181}
182
183
184/// Calculate len_limit and determine if there is enough input to run
185/// the actual match finder code. Sets up "cur" and "pos". This macro
186/// is used by all find functions and binary tree skip functions. Hash
187/// chain skip function doesn't need len_limit so a simpler code is used
188/// in them.
189#define header(is_bt, len_min, ret_op) \
190 uint32_t len_limit = mf_avail(mf); \
191 if (mf->nice_len <= len_limit) { \
192 len_limit = mf->nice_len; \
193 } else if (len_limit < (len_min) \
194 || (is_bt && mf->action == LZMA_SYNC_FLUSH)) { \
195 assert(mf->action != LZMA_RUN); \
196 move_pending(mf); \
197 ret_op; \
198 } \
199 const uint8_t *cur = mf_ptr(mf); \
200 const uint32_t pos = mf->read_pos + mf->offset
201
202
203/// Header for find functions. "return 0" indicates that zero matches
204/// were found.
205#define header_find(is_bt, len_min) \
206 header(is_bt, len_min, return 0); \
207 uint32_t matches_count = 0
208
209
210/// Header for a loop in a skip function. "continue" tells to skip the rest
211/// of the code in the loop.
212#define header_skip(is_bt, len_min) \
213 header(is_bt, len_min, continue)
214
215
216/// Calls hc_find_func() or bt_find_func() and calculates the total number
217/// of matches found. Updates the dictionary position and returns the number
218/// of matches found.
219#define call_find(func, len_best) \
220do { \
221 matches_count = func(len_limit, pos, cur, cur_match, mf->depth, \
222 mf->son, mf->cyclic_pos, mf->cyclic_size, \
223 matches + matches_count, len_best) \
224 - matches; \
225 move_pos(mf); \
226 return matches_count; \
227} while (0)
228
229
230////////////////
231// Hash Chain //
232////////////////
233
234#if defined(HAVE_MF_HC3) || defined(HAVE_MF_HC4)
235///
236///
237/// \param len_limit Don't look for matches longer than len_limit.
238/// \param pos lzma_mf.read_pos + lzma_mf.offset
239/// \param cur Pointer to current byte (mf_ptr(mf))
240/// \param cur_match Start position of the current match candidate
241/// \param depth Maximum length of the hash chain
242/// \param son lzma_mf.son (contains the hash chain)
243/// \param cyclic_pos
244/// \param cyclic_size
245/// \param matches Array to hold the matches.
246/// \param len_best The length of the longest match found so far.
247static lzma_match *
248hc_find_func(
249 const uint32_t len_limit,
250 const uint32_t pos,
251 const uint8_t *const cur,
252 uint32_t cur_match,
253 uint32_t depth,
254 uint32_t *const son,
255 const uint32_t cyclic_pos,
256 const uint32_t cyclic_size,
257 lzma_match *matches,
258 uint32_t len_best)
259{
260 son[cyclic_pos] = cur_match;
261
262 while (true) {
263 const uint32_t delta = pos - cur_match;
264 if (depth-- == 0 || delta >= cyclic_size)
265 return matches;
266
267 const uint8_t *const pb = cur - delta;
268 cur_match = son[cyclic_pos - delta
269 + (delta > cyclic_pos ? cyclic_size : 0)];
270
271 if (pb[len_best] == cur[len_best] && pb[0] == cur[0]) {
272 uint32_t len = 0;
273 while (++len != len_limit)
274 if (pb[len] != cur[len])
275 break;
276
277 if (len_best < len) {
278 len_best = len;
279 matches->len = len;
280 matches->dist = delta - 1;
281 ++matches;
282
283 if (len == len_limit)
284 return matches;
285 }
286 }
287 }
288}
289
290
291#define hc_find(len_best) \
292 call_find(hc_find_func, len_best)
293
294
295#define hc_skip() \
296do { \
297 mf->son[mf->cyclic_pos] = cur_match; \
298 move_pos(mf); \
299} while (0)
300
301#endif
302
303
304#ifdef HAVE_MF_HC3
305extern uint32_t
306lzma_mf_hc3_find(lzma_mf *mf, lzma_match *matches)
307{
308 header_find(false, 3);
309
310 hash_3_calc();
311
312 const uint32_t delta2 = pos - mf->hash[hash_2_value];
313 const uint32_t cur_match = mf->hash[FIX_3_HASH_SIZE + hash_value];
314
315 mf->hash[hash_2_value] = pos;
316 mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
317
318 uint32_t len_best = 2;
319
320 if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) {
321 for ( ; len_best != len_limit; ++len_best)
322 if (*(cur + len_best - delta2) != cur[len_best])
323 break;
324
325 matches[0].len = len_best;
326 matches[0].dist = delta2 - 1;
327 matches_count = 1;
328
329 if (len_best == len_limit) {
330 hc_skip();
331 return 1; // matches_count
332 }
333 }
334
335 hc_find(len_best);
336}
337
338
339extern void
340lzma_mf_hc3_skip(lzma_mf *mf, uint32_t amount)
341{
342 do {
343 if (mf_avail(mf) < 3) {
344 move_pending(mf);
345 continue;
346 }
347
348 const uint8_t *cur = mf_ptr(mf);
349 const uint32_t pos = mf->read_pos + mf->offset;
350
351 hash_3_calc();
352
353 const uint32_t cur_match
354 = mf->hash[FIX_3_HASH_SIZE + hash_value];
355
356 mf->hash[hash_2_value] = pos;
357 mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
358
359 hc_skip();
360
361 } while (--amount != 0);
362}
363#endif
364
365
366#ifdef HAVE_MF_HC4
367extern uint32_t
368lzma_mf_hc4_find(lzma_mf *mf, lzma_match *matches)
369{
370 header_find(false, 4);
371
372 hash_4_calc();
373
374 uint32_t delta2 = pos - mf->hash[hash_2_value];
375 const uint32_t delta3
376 = pos - mf->hash[FIX_3_HASH_SIZE + hash_3_value];
377 const uint32_t cur_match = mf->hash[FIX_4_HASH_SIZE + hash_value];
378
379 mf->hash[hash_2_value ] = pos;
380 mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
381 mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
382
383 uint32_t len_best = 1;
384
385 if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) {
386 len_best = 2;
387 matches[0].len = 2;
388 matches[0].dist = delta2 - 1;
389 matches_count = 1;
390 }
391
392 if (delta2 != delta3 && delta3 < mf->cyclic_size
393 && *(cur - delta3) == *cur) {
394 len_best = 3;
395 matches[matches_count++].dist = delta3 - 1;
396 delta2 = delta3;
397 }
398
399 if (matches_count != 0) {
400 for ( ; len_best != len_limit; ++len_best)
401 if (*(cur + len_best - delta2) != cur[len_best])
402 break;
403
404 matches[matches_count - 1].len = len_best;
405
406 if (len_best == len_limit) {
407 hc_skip();
408 return matches_count;
409 }
410 }
411
412 if (len_best < 3)
413 len_best = 3;
414
415 hc_find(len_best);
416}
417
418
419extern void
420lzma_mf_hc4_skip(lzma_mf *mf, uint32_t amount)
421{
422 do {
423 if (mf_avail(mf) < 4) {
424 move_pending(mf);
425 continue;
426 }
427
428 const uint8_t *cur = mf_ptr(mf);
429 const uint32_t pos = mf->read_pos + mf->offset;
430
431 hash_4_calc();
432
433 const uint32_t cur_match
434 = mf->hash[FIX_4_HASH_SIZE + hash_value];
435
436 mf->hash[hash_2_value] = pos;
437 mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
438 mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
439
440 hc_skip();
441
442 } while (--amount != 0);
443}
444#endif
445
446
447/////////////////
448// Binary Tree //
449/////////////////
450
451#if defined(HAVE_MF_BT2) || defined(HAVE_MF_BT3) || defined(HAVE_MF_BT4)
452static lzma_match *
453bt_find_func(
454 const uint32_t len_limit,
455 const uint32_t pos,
456 const uint8_t *const cur,
457 uint32_t cur_match,
458 uint32_t depth,
459 uint32_t *const son,
460 const uint32_t cyclic_pos,
461 const uint32_t cyclic_size,
462 lzma_match *matches,
463 uint32_t len_best)
464{
465 uint32_t *ptr0 = son + (cyclic_pos << 1) + 1;
466 uint32_t *ptr1 = son + (cyclic_pos << 1);
467
468 uint32_t len0 = 0;
469 uint32_t len1 = 0;
470
471 while (true) {
472 const uint32_t delta = pos - cur_match;
473 if (depth-- == 0 || delta >= cyclic_size) {
474 *ptr0 = EMPTY_HASH_VALUE;
475 *ptr1 = EMPTY_HASH_VALUE;
476 return matches;
477 }
478
479 uint32_t *const pair = son + ((cyclic_pos - delta
480 + (delta > cyclic_pos ? cyclic_size : 0))
481 << 1);
482
483 const uint8_t *const pb = cur - delta;
|
550
551 if (pb[len] == cur[len]) {
552 while (++len != len_limit)
553 if (pb[len] != cur[len])
554 break;
555
556 if (len == len_limit) {
557 *ptr1 = pair[0];
558 *ptr0 = pair[1];
559 return;
560 }
561 }
562
563 if (pb[len] < cur[len]) {
564 *ptr1 = cur_match;
565 ptr1 = pair + 1;
566 cur_match = *ptr1;
567 len1 = len;
568 } else {
569 *ptr0 = cur_match;
570 ptr0 = pair;
571 cur_match = *ptr0;
572 len0 = len;
573 }
574 }
575}
576
577
578#define bt_find(len_best) \
579 call_find(bt_find_func, len_best)
580
581#define bt_skip() \
582do { \
583 bt_skip_func(len_limit, pos, cur, cur_match, mf->depth, \
584 mf->son, mf->cyclic_pos, \
585 mf->cyclic_size); \
586 move_pos(mf); \
587} while (0)
588
589#endif
590
591
592#ifdef HAVE_MF_BT2
593extern uint32_t
594lzma_mf_bt2_find(lzma_mf *mf, lzma_match *matches)
595{
596 header_find(true, 2);
597
598 hash_2_calc();
599
600 const uint32_t cur_match = mf->hash[hash_value];
601 mf->hash[hash_value] = pos;
602
603 bt_find(1);
604}
605
606
607extern void
608lzma_mf_bt2_skip(lzma_mf *mf, uint32_t amount)
609{
610 do {
611 header_skip(true, 2);
612
613 hash_2_calc();
614
615 const uint32_t cur_match = mf->hash[hash_value];
616 mf->hash[hash_value] = pos;
617
618 bt_skip();
619
620 } while (--amount != 0);
621}
622#endif
623
624
625#ifdef HAVE_MF_BT3
626extern uint32_t
627lzma_mf_bt3_find(lzma_mf *mf, lzma_match *matches)
628{
629 header_find(true, 3);
630
631 hash_3_calc();
632
633 const uint32_t delta2 = pos - mf->hash[hash_2_value];
634 const uint32_t cur_match = mf->hash[FIX_3_HASH_SIZE + hash_value];
635
636 mf->hash[hash_2_value] = pos;
637 mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
638
639 uint32_t len_best = 2;
640
641 if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) {
642 for ( ; len_best != len_limit; ++len_best)
643 if (*(cur + len_best - delta2) != cur[len_best])
644 break;
645
646 matches[0].len = len_best;
647 matches[0].dist = delta2 - 1;
648 matches_count = 1;
649
650 if (len_best == len_limit) {
651 bt_skip();
652 return 1; // matches_count
653 }
654 }
655
656 bt_find(len_best);
657}
658
659
660extern void
661lzma_mf_bt3_skip(lzma_mf *mf, uint32_t amount)
662{
663 do {
664 header_skip(true, 3);
665
666 hash_3_calc();
667
668 const uint32_t cur_match
669 = mf->hash[FIX_3_HASH_SIZE + hash_value];
670
671 mf->hash[hash_2_value] = pos;
672 mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
673
674 bt_skip();
675
676 } while (--amount != 0);
677}
678#endif
679
680
681#ifdef HAVE_MF_BT4
682extern uint32_t
683lzma_mf_bt4_find(lzma_mf *mf, lzma_match *matches)
684{
685 header_find(true, 4);
686
687 hash_4_calc();
688
689 uint32_t delta2 = pos - mf->hash[hash_2_value];
690 const uint32_t delta3
691 = pos - mf->hash[FIX_3_HASH_SIZE + hash_3_value];
692 const uint32_t cur_match = mf->hash[FIX_4_HASH_SIZE + hash_value];
693
694 mf->hash[hash_2_value] = pos;
695 mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
696 mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
697
698 uint32_t len_best = 1;
699
700 if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) {
701 len_best = 2;
702 matches[0].len = 2;
703 matches[0].dist = delta2 - 1;
704 matches_count = 1;
705 }
706
707 if (delta2 != delta3 && delta3 < mf->cyclic_size
708 && *(cur - delta3) == *cur) {
709 len_best = 3;
710 matches[matches_count++].dist = delta3 - 1;
711 delta2 = delta3;
712 }
713
714 if (matches_count != 0) {
715 for ( ; len_best != len_limit; ++len_best)
716 if (*(cur + len_best - delta2) != cur[len_best])
717 break;
718
719 matches[matches_count - 1].len = len_best;
720
721 if (len_best == len_limit) {
722 bt_skip();
723 return matches_count;
724 }
725 }
726
727 if (len_best < 3)
728 len_best = 3;
729
730 bt_find(len_best);
731}
732
733
734extern void
735lzma_mf_bt4_skip(lzma_mf *mf, uint32_t amount)
736{
737 do {
738 header_skip(true, 4);
739
740 hash_4_calc();
741
742 const uint32_t cur_match
743 = mf->hash[FIX_4_HASH_SIZE + hash_value];
744
745 mf->hash[hash_2_value] = pos;
746 mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
747 mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
748
749 bt_skip();
750
751 } while (--amount != 0);
752}
753#endif
| 550
551 if (pb[len] == cur[len]) {
552 while (++len != len_limit)
553 if (pb[len] != cur[len])
554 break;
555
556 if (len == len_limit) {
557 *ptr1 = pair[0];
558 *ptr0 = pair[1];
559 return;
560 }
561 }
562
563 if (pb[len] < cur[len]) {
564 *ptr1 = cur_match;
565 ptr1 = pair + 1;
566 cur_match = *ptr1;
567 len1 = len;
568 } else {
569 *ptr0 = cur_match;
570 ptr0 = pair;
571 cur_match = *ptr0;
572 len0 = len;
573 }
574 }
575}
576
577
578#define bt_find(len_best) \
579 call_find(bt_find_func, len_best)
580
581#define bt_skip() \
582do { \
583 bt_skip_func(len_limit, pos, cur, cur_match, mf->depth, \
584 mf->son, mf->cyclic_pos, \
585 mf->cyclic_size); \
586 move_pos(mf); \
587} while (0)
588
589#endif
590
591
592#ifdef HAVE_MF_BT2
593extern uint32_t
594lzma_mf_bt2_find(lzma_mf *mf, lzma_match *matches)
595{
596 header_find(true, 2);
597
598 hash_2_calc();
599
600 const uint32_t cur_match = mf->hash[hash_value];
601 mf->hash[hash_value] = pos;
602
603 bt_find(1);
604}
605
606
607extern void
608lzma_mf_bt2_skip(lzma_mf *mf, uint32_t amount)
609{
610 do {
611 header_skip(true, 2);
612
613 hash_2_calc();
614
615 const uint32_t cur_match = mf->hash[hash_value];
616 mf->hash[hash_value] = pos;
617
618 bt_skip();
619
620 } while (--amount != 0);
621}
622#endif
623
624
625#ifdef HAVE_MF_BT3
626extern uint32_t
627lzma_mf_bt3_find(lzma_mf *mf, lzma_match *matches)
628{
629 header_find(true, 3);
630
631 hash_3_calc();
632
633 const uint32_t delta2 = pos - mf->hash[hash_2_value];
634 const uint32_t cur_match = mf->hash[FIX_3_HASH_SIZE + hash_value];
635
636 mf->hash[hash_2_value] = pos;
637 mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
638
639 uint32_t len_best = 2;
640
641 if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) {
642 for ( ; len_best != len_limit; ++len_best)
643 if (*(cur + len_best - delta2) != cur[len_best])
644 break;
645
646 matches[0].len = len_best;
647 matches[0].dist = delta2 - 1;
648 matches_count = 1;
649
650 if (len_best == len_limit) {
651 bt_skip();
652 return 1; // matches_count
653 }
654 }
655
656 bt_find(len_best);
657}
658
659
660extern void
661lzma_mf_bt3_skip(lzma_mf *mf, uint32_t amount)
662{
663 do {
664 header_skip(true, 3);
665
666 hash_3_calc();
667
668 const uint32_t cur_match
669 = mf->hash[FIX_3_HASH_SIZE + hash_value];
670
671 mf->hash[hash_2_value] = pos;
672 mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
673
674 bt_skip();
675
676 } while (--amount != 0);
677}
678#endif
679
680
681#ifdef HAVE_MF_BT4
682extern uint32_t
683lzma_mf_bt4_find(lzma_mf *mf, lzma_match *matches)
684{
685 header_find(true, 4);
686
687 hash_4_calc();
688
689 uint32_t delta2 = pos - mf->hash[hash_2_value];
690 const uint32_t delta3
691 = pos - mf->hash[FIX_3_HASH_SIZE + hash_3_value];
692 const uint32_t cur_match = mf->hash[FIX_4_HASH_SIZE + hash_value];
693
694 mf->hash[hash_2_value] = pos;
695 mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
696 mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
697
698 uint32_t len_best = 1;
699
700 if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) {
701 len_best = 2;
702 matches[0].len = 2;
703 matches[0].dist = delta2 - 1;
704 matches_count = 1;
705 }
706
707 if (delta2 != delta3 && delta3 < mf->cyclic_size
708 && *(cur - delta3) == *cur) {
709 len_best = 3;
710 matches[matches_count++].dist = delta3 - 1;
711 delta2 = delta3;
712 }
713
714 if (matches_count != 0) {
715 for ( ; len_best != len_limit; ++len_best)
716 if (*(cur + len_best - delta2) != cur[len_best])
717 break;
718
719 matches[matches_count - 1].len = len_best;
720
721 if (len_best == len_limit) {
722 bt_skip();
723 return matches_count;
724 }
725 }
726
727 if (len_best < 3)
728 len_best = 3;
729
730 bt_find(len_best);
731}
732
733
734extern void
735lzma_mf_bt4_skip(lzma_mf *mf, uint32_t amount)
736{
737 do {
738 header_skip(true, 4);
739
740 hash_4_calc();
741
742 const uint32_t cur_match
743 = mf->hash[FIX_4_HASH_SIZE + hash_value];
744
745 mf->hash[hash_2_value] = pos;
746 mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
747 mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
748
749 bt_skip();
750
751 } while (--amount != 0);
752}
753#endif
|