1 ///////////////////////////////////////////////////////////////////////////////
3 /// \file lz_encoder_mf.c
4 /// \brief Match finders
6 // Copyright (C) 1999-2008 Igor Pavlov
7 // Copyright (C) 2008 Lasse Collin
9 // This library is free software; you can redistribute it and/or
10 // modify it under the terms of the GNU Lesser General Public
11 // License as published by the Free Software Foundation; either
12 // version 2.1 of the License, or (at your option) any later version.
14 // This library is distributed in the hope that it will be useful,
15 // but WITHOUT ANY WARRANTY; without even the implied warranty of
16 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 // Lesser General Public License for more details.
19 ///////////////////////////////////////////////////////////////////////////////
21 #include "lz_encoder.h"
22 #include "lz_encoder_hash.h"
26 /// \brief Find matches starting from the current byte
28 /// \return The length of the longest match found
30 lzma_mf_find(lzma_mf *mf, uint32_t *count_ptr, lzma_match *matches)
32 // Call the match finder. It returns the number of length-distance
34 // FIXME: Minimum count is zero, what _exactly_ is the maximum?
35 const uint32_t count = mf->find(mf, matches);
37 // Length of the longest match; assume that no matches were found
38 // and thus the maximum length is zero.
39 uint32_t len_best = 0;
43 // Validate the matches.
44 for (uint32_t i = 0; i < count; ++i) {
45 assert(matches[i].len <= mf->find_len_max);
46 assert(matches[i].dist < mf->read_pos);
47 assert(memcmp(mf_ptr(mf) - 1,
48 mf_ptr(mf) - matches[i].dist - 2,
49 matches[i].len) == 0);
53 // The last used element in the array contains
55 len_best = matches[count - 1].len;
57 // If a match of maximum search length was found, try to
58 // extend the match to maximum possible length.
59 if (len_best == mf->find_len_max) {
60 // The limit for the match length is either the
61 // maximum match length supported by the LZ-based
62 // encoder or the number of bytes left in the
63 // dictionary, whichever is smaller.
64 uint32_t limit = mf_avail(mf) + 1;
65 if (limit > mf->match_len_max)
66 limit = mf->match_len_max;
68 // Pointer to the byte we just ran through
70 const uint8_t *p1 = mf_ptr(mf) - 1;
72 // Pointer to the beginning of the match. We need -1
73 // here because the match distances are zero based.
74 const uint8_t *p2 = p1 - matches[count - 1].dist - 1;
76 while (len_best < limit
77 && p1[len_best] == p2[len_best])
84 // Finally update the read position to indicate that match finder was
85 // run for this dictionary offset.
92 /// Hash value to indicate unused element in the hash. Since we start the
93 /// positions from dictionary_size + 1, zero is always too far to qualify
94 /// as usable match position.
95 #define EMPTY_HASH_VALUE 0
98 /// Normalization must be done when lzma_mf.offset + lzma_mf.read_pos
99 /// reaches MUST_NORMALIZE_POS.
100 #define MUST_NORMALIZE_POS UINT32_MAX
103 /// \brief Normalizes hash values
105 /// The hash arrays store positions of match candidates. The positions are
106 /// relative to an arbitrary offset that is not the same as the absolute
107 /// offset in the input stream. The relative position of the current byte
108 /// is lzma_mf.offset + lzma_mf.read_pos. The distances of the matches are
109 /// the differences of the current read position and the position found from
112 /// To prevent integer overflows of the offsets stored in the hash arrays,
113 /// we need to "normalize" the stored values now and then. During the
114 /// normalization, we drop values that indicate distance greater than the
115 /// dictionary size, thus making space for new values.
117 normalize(lzma_mf *mf)
119 assert(mf->read_pos + mf->offset == MUST_NORMALIZE_POS);
121 // In future we may not want to touch the lowest bits, because there
122 // may be match finders that use larger resolution than one byte.
123 const uint32_t subvalue
124 = (MUST_NORMALIZE_POS - mf->cyclic_size);
125 // & (~(UINT32_C(1) << 10) - 1);
127 const uint32_t count = mf->hash_size_sum + mf->sons_count;
128 uint32_t *hash = mf->hash;
130 for (uint32_t i = 0; i < count; ++i) {
131 // If the distance is greater than the dictionary size,
132 // we can simply mark the hash element as empty.
134 // NOTE: Only the first mf->hash_size_sum elements are
135 // initialized for sure. There may be uninitialized elements
136 // in mf->son. Since we go through both mf->hash and
137 // mf->son here in normalization, Valgrind may complain
138 // that the "if" below depends on uninitialized value. In
139 // this case it is safe to ignore the warning. See also the
140 // comments in lz_encoder_init() in lz_encoder.c.
141 if (hash[i] <= subvalue)
142 hash[i] = EMPTY_HASH_VALUE;
147 // Update offset to match the new locations.
148 mf->offset -= subvalue;
154 /// Mark the current byte as processed from point of view of the match finder.
156 move_pos(lzma_mf *mf)
158 if (++mf->cyclic_pos == mf->cyclic_size)
162 assert(mf->read_pos <= mf->write_pos);
164 if (unlikely(mf->read_pos + mf->offset == UINT32_MAX))
169 /// When flushing, we cannot run the match finder unless there is find_len_max
170 /// bytes available in the dictionary. Instead, we skip running the match
171 /// finder (indicating that no match was found), and count how many bytes we
172 /// have ignored this way.
174 /// When new data is given after the flushing was completed, the match finder
175 /// is restarted by rewinding mf->read_pos backwards by mf->pending. Then
176 /// the missed bytes are added to the hash using the match finder's skip
177 /// function (with small amount of input, it may start using mf->pending
178 /// again if flushing).
180 /// Due to this rewinding, we don't touch cyclic_pos or test for
181 /// normalization. It will be done when the match finder's skip function
182 /// catches up after a flush.
184 move_pending(lzma_mf *mf)
187 assert(mf->read_pos <= mf->write_pos);
192 /// Calculate len_limit and determine if there is enough input to run
193 /// the actual match finder code. Sets up "cur" and "pos". This macro
194 /// is used by all find functions and binary tree skip functions. Hash
195 /// chain skip function doesn't need len_limit so a simpler code is used
197 #define header(is_bt, len_min, ret_op) \
198 uint32_t len_limit = mf_avail(mf); \
199 if (mf->find_len_max <= len_limit) { \
200 len_limit = mf->find_len_max; \
201 } else if (len_limit < (len_min) \
202 || (is_bt && mf->action == LZMA_SYNC_FLUSH)) { \
203 assert(mf->action != LZMA_RUN); \
207 const uint8_t *cur = mf_ptr(mf); \
208 const uint32_t pos = mf->read_pos + mf->offset
211 /// Header for find functions. "return 0" indicates that zero matches
213 #define header_find(is_bt, len_min) \
214 header(is_bt, len_min, return 0); \
215 uint32_t matches_count = 0
218 /// Header for a loop in a skip function. "continue" tells to skip the rest
219 /// of the code in the loop.
220 #define header_skip(is_bt, len_min) \
221 header(is_bt, len_min, continue)
224 /// Calls hc_find_func() or bt_find_func() and calculates the total number
225 /// of matches found. Updates the dictionary position and returns the number
226 /// of matches found.
227 #define call_find(func, len_best) \
229 matches_count = func(len_limit, pos, cur, cur_match, mf->loops, \
230 mf->son, mf->cyclic_pos, mf->cyclic_size, \
231 matches + matches_count, len_best) \
234 return matches_count; \
242 #if defined(HAVE_MF_HC3) || defined(HAVE_MF_HC4)
245 /// \param len_limit Don't look for matches longer than len_limit.
246 /// \param pos lzma_mf.read_pos + lzma_mf.offset
247 /// \param cur Pointer to current byte (lzma_dict_ptr(mf))
248 /// \param cur_match Start position of the current match candidate
249 /// \param loops Maximum length of the hash chain
250 /// \param son lzma_mf.son (contains the hash chain)
251 /// \param cyclic_pos
252 /// \param cyclic_size
253 /// \param matches Array to hold the matches.
254 /// \param len_best The length of the longest match found so far.
257 const uint32_t len_limit,
259 const uint8_t *const cur,
263 const uint32_t cyclic_pos,
264 const uint32_t cyclic_size,
268 son[cyclic_pos] = cur_match;
271 const uint32_t delta = pos - cur_match;
272 if (loops-- == 0 || delta >= cyclic_size)
275 const uint8_t *const pb = cur - delta;
276 cur_match = son[cyclic_pos - delta
277 + (delta > cyclic_pos ? cyclic_size : 0)];
279 if (pb[len_best] == cur[len_best] && pb[0] == cur[0]) {
281 while (++len != len_limit)
282 if (pb[len] != cur[len])
285 if (len_best < len) {
288 matches->dist = delta - 1;
291 if (len == len_limit)
299 #define hc_find(len_best) \
300 call_find(hc_find_func, len_best)
305 mf->son[mf->cyclic_pos] = cur_match; \
314 lzma_mf_hc3_find(lzma_mf *mf, lzma_match *matches)
316 header_find(false, 3);
320 const uint32_t delta2 = pos - mf->hash[hash_2_value];
321 const uint32_t cur_match = mf->hash[FIX_3_HASH_SIZE + hash_value];
323 mf->hash[hash_2_value] = pos;
324 mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
326 uint32_t len_best = 2;
328 if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) {
329 for ( ; len_best != len_limit; ++len_best)
330 if (*(cur + len_best - delta2) != cur[len_best])
333 matches[0].len = len_best;
334 matches[0].dist = delta2 - 1;
337 if (len_best == len_limit) {
339 return 1; // matches_count
348 lzma_mf_hc3_skip(lzma_mf *mf, uint32_t amount)
351 if (mf_avail(mf) < 3) {
356 const uint8_t *cur = mf_ptr(mf);
357 const uint32_t pos = mf->read_pos + mf->offset;
361 const uint32_t cur_match
362 = mf->hash[FIX_3_HASH_SIZE + hash_value];
364 mf->hash[hash_2_value] = pos;
365 mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
369 } while (--amount != 0);
376 lzma_mf_hc4_find(lzma_mf *mf, lzma_match *matches)
378 header_find(false, 4);
382 uint32_t delta2 = pos - mf->hash[hash_2_value];
383 const uint32_t delta3
384 = pos - mf->hash[FIX_3_HASH_SIZE + hash_3_value];
385 const uint32_t cur_match = mf->hash[FIX_4_HASH_SIZE + hash_value];
387 mf->hash[hash_2_value ] = pos;
388 mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
389 mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
391 uint32_t len_best = 1;
393 if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) {
396 matches[0].dist = delta2 - 1;
400 if (delta2 != delta3 && delta3 < mf->cyclic_size
401 && *(cur - delta3) == *cur) {
403 matches[matches_count++].dist = delta3 - 1;
407 if (matches_count != 0) {
408 for ( ; len_best != len_limit; ++len_best)
409 if (*(cur + len_best - delta2) != cur[len_best])
412 matches[matches_count - 1].len = len_best;
414 if (len_best == len_limit) {
416 return matches_count;
428 lzma_mf_hc4_skip(lzma_mf *mf, uint32_t amount)
431 if (mf_avail(mf) < 4) {
436 const uint8_t *cur = mf_ptr(mf);
437 const uint32_t pos = mf->read_pos + mf->offset;
441 const uint32_t cur_match
442 = mf->hash[FIX_4_HASH_SIZE + hash_value];
444 mf->hash[hash_2_value] = pos;
445 mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
446 mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
450 } while (--amount != 0);
459 #if defined(HAVE_MF_BT2) || defined(HAVE_MF_BT3) || defined(HAVE_MF_BT4)
462 const uint32_t len_limit,
464 const uint8_t *const cur,
468 const uint32_t cyclic_pos,
469 const uint32_t cyclic_size,
473 uint32_t *ptr0 = son + (cyclic_pos << 1) + 1;
474 uint32_t *ptr1 = son + (cyclic_pos << 1);
480 const uint32_t delta = pos - cur_match;
481 if (loops-- == 0 || delta >= cyclic_size) {
482 *ptr0 = EMPTY_HASH_VALUE;
483 *ptr1 = EMPTY_HASH_VALUE;
487 uint32_t *const pair = son + ((cyclic_pos - delta
488 + (delta > cyclic_pos ? cyclic_size : 0))
491 const uint8_t *const pb = cur - delta;
492 uint32_t len = MIN(len0, len1);
494 if (pb[len] == cur[len]) {
495 while (++len != len_limit)
496 if (pb[len] != cur[len])
499 if (len_best < len) {
502 matches->dist = delta - 1;
505 if (len == len_limit) {
513 if (pb[len] < cur[len]) {
530 const uint32_t len_limit,
532 const uint8_t *const cur,
536 const uint32_t cyclic_pos,
537 const uint32_t cyclic_size)
539 uint32_t *ptr0 = son + (cyclic_pos << 1) + 1;
540 uint32_t *ptr1 = son + (cyclic_pos << 1);
546 const uint32_t delta = pos - cur_match;
547 if (loops-- == 0 || delta >= cyclic_size) {
548 *ptr0 = EMPTY_HASH_VALUE;
549 *ptr1 = EMPTY_HASH_VALUE;
553 uint32_t *pair = son + ((cyclic_pos - delta
554 + (delta > cyclic_pos ? cyclic_size : 0))
556 const uint8_t *pb = cur - delta;
557 uint32_t len = MIN(len0, len1);
559 if (pb[len] == cur[len]) {
560 while (++len != len_limit)
561 if (pb[len] != cur[len])
564 if (len == len_limit) {
571 if (pb[len] < cur[len]) {
586 #define bt_find(len_best) \
587 call_find(bt_find_func, len_best)
591 bt_skip_func(len_limit, pos, cur, cur_match, mf->loops, \
592 mf->son, mf->cyclic_pos, \
602 lzma_mf_bt2_find(lzma_mf *mf, lzma_match *matches)
604 header_find(true, 2);
608 const uint32_t cur_match = mf->hash[hash_value];
609 mf->hash[hash_value] = pos;
616 lzma_mf_bt2_skip(lzma_mf *mf, uint32_t amount)
619 header_skip(true, 2);
623 const uint32_t cur_match = mf->hash[hash_value];
624 mf->hash[hash_value] = pos;
628 } while (--amount != 0);
635 lzma_mf_bt3_find(lzma_mf *mf, lzma_match *matches)
637 header_find(true, 3);
641 const uint32_t delta2 = pos - mf->hash[hash_2_value];
642 const uint32_t cur_match = mf->hash[FIX_3_HASH_SIZE + hash_value];
644 mf->hash[hash_2_value] = pos;
645 mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
647 uint32_t len_best = 2;
649 if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) {
650 for ( ; len_best != len_limit; ++len_best)
651 if (*(cur + len_best - delta2) != cur[len_best])
654 matches[0].len = len_best;
655 matches[0].dist = delta2 - 1;
658 if (len_best == len_limit) {
660 return 1; // matches_count
669 lzma_mf_bt3_skip(lzma_mf *mf, uint32_t amount)
672 header_skip(true, 3);
676 const uint32_t cur_match
677 = mf->hash[FIX_3_HASH_SIZE + hash_value];
679 mf->hash[hash_2_value] = pos;
680 mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
684 } while (--amount != 0);
691 lzma_mf_bt4_find(lzma_mf *mf, lzma_match *matches)
693 header_find(true, 4);
697 uint32_t delta2 = pos - mf->hash[hash_2_value];
698 const uint32_t delta3
699 = pos - mf->hash[FIX_3_HASH_SIZE + hash_3_value];
700 const uint32_t cur_match = mf->hash[FIX_4_HASH_SIZE + hash_value];
702 mf->hash[hash_2_value] = pos;
703 mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
704 mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
706 uint32_t len_best = 1;
708 if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) {
711 matches[0].dist = delta2 - 1;
715 if (delta2 != delta3 && delta3 < mf->cyclic_size
716 && *(cur - delta3) == *cur) {
718 matches[matches_count++].dist = delta3 - 1;
722 if (matches_count != 0) {
723 for ( ; len_best != len_limit; ++len_best)
724 if (*(cur + len_best - delta2) != cur[len_best])
727 matches[matches_count - 1].len = len_best;
729 if (len_best == len_limit) {
731 return matches_count;
743 lzma_mf_bt4_skip(lzma_mf *mf, uint32_t amount)
746 header_skip(true, 4);
750 const uint32_t cur_match
751 = mf->hash[FIX_4_HASH_SIZE + hash_value];
753 mf->hash[hash_2_value] = pos;
754 mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
755 mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
759 } while (--amount != 0);