1 ///////////////////////////////////////////////////////////////////////////////
3 /// \file lz_encoder_mf.c
4 /// \brief Match finders
6 // Authors: Igor Pavlov
9 // This file has been put into the public domain.
10 // You can do whatever you want with this file.
12 ///////////////////////////////////////////////////////////////////////////////
14 #include "lz_encoder.h"
15 #include "lz_encoder_hash.h"
18 /// \brief Find matches starting from the current byte
20 /// \return The length of the longest match found
22 lzma_mf_find(lzma_mf
*mf
, uint32_t *count_ptr
, lzma_match
*matches
)
24 // Call the match finder. It returns the number of length-distance
26 // FIXME: Minimum count is zero, what _exactly_ is the maximum?
27 const uint32_t count
= mf
->find(mf
, matches
);
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;
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);
45 // The last used element in the array contains
47 len_best
= matches
[count
- 1].len
;
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
;
60 // Pointer to the byte we just ran through
62 const uint8_t *p1
= mf_ptr(mf
) - 1;
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;
68 while (len_best
< limit
69 && p1
[len_best
] == p2
[len_best
])
76 // Finally update the read position to indicate that match finder was
77 // run for this dictionary offset.
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
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
95 /// \brief Normalizes hash values
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
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.
109 normalize(lzma_mf
*mf
)
111 assert(mf
->read_pos
+ mf
->offset
== MUST_NORMALIZE_POS
);
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);
119 const uint32_t count
= mf
->hash_size_sum
+ mf
->sons_count
;
120 uint32_t *hash
= mf
->hash
;
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.
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
;
139 // Update offset to match the new locations.
140 mf
->offset
-= subvalue
;
146 /// Mark the current byte as processed from point of view of the match finder.
148 move_pos(lzma_mf
*mf
)
150 if (++mf
->cyclic_pos
== mf
->cyclic_size
)
154 assert(mf
->read_pos
<= mf
->write_pos
);
156 if (unlikely(mf
->read_pos
+ mf
->offset
== UINT32_MAX
))
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.
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).
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.
176 move_pending(lzma_mf
*mf
)
179 assert(mf
->read_pos
<= mf
->write_pos
);
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
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); \
199 const uint8_t *cur = mf_ptr(mf); \
200 const uint32_t pos = mf->read_pos + mf->offset
203 /// Header for find functions. "return 0" indicates that zero matches
205 #define header_find(is_bt, len_min) \
206 header(is_bt, len_min, return 0); \
207 uint32_t matches_count = 0
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)
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) \
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) \
226 return matches_count; \
234 #if defined(HAVE_MF_HC3) || defined(HAVE_MF_HC4)
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.
249 const uint32_t len_limit
,
251 const uint8_t *const cur
,
255 const uint32_t cyclic_pos
,
256 const uint32_t cyclic_size
,
260 son
[cyclic_pos
] = cur_match
;
263 const uint32_t delta
= pos
- cur_match
;
264 if (depth
-- == 0 || delta
>= cyclic_size
)
267 const uint8_t *const pb
= cur
- delta
;
268 cur_match
= son
[cyclic_pos
- delta
269 + (delta
> cyclic_pos
? cyclic_size
: 0)];
271 if (pb
[len_best
] == cur
[len_best
] && pb
[0] == cur
[0]) {
273 while (++len
!= len_limit
)
274 if (pb
[len
] != cur
[len
])
277 if (len_best
< len
) {
280 matches
->dist
= delta
- 1;
283 if (len
== len_limit
)
291 #define hc_find(len_best) \
292 call_find(hc_find_func, len_best)
297 mf->son[mf->cyclic_pos] = cur_match; \
306 lzma_mf_hc3_find(lzma_mf
*mf
, lzma_match
*matches
)
308 header_find(false, 3);
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
];
315 mf
->hash
[hash_2_value
] = pos
;
316 mf
->hash
[FIX_3_HASH_SIZE
+ hash_value
] = pos
;
318 uint32_t len_best
= 2;
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
])
325 matches
[0].len
= len_best
;
326 matches
[0].dist
= delta2
- 1;
329 if (len_best
== len_limit
) {
331 return 1; // matches_count
340 lzma_mf_hc3_skip(lzma_mf
*mf
, uint32_t amount
)
343 if (mf_avail(mf
) < 3) {
348 const uint8_t *cur
= mf_ptr(mf
);
349 const uint32_t pos
= mf
->read_pos
+ mf
->offset
;
353 const uint32_t cur_match
354 = mf
->hash
[FIX_3_HASH_SIZE
+ hash_value
];
356 mf
->hash
[hash_2_value
] = pos
;
357 mf
->hash
[FIX_3_HASH_SIZE
+ hash_value
] = pos
;
361 } while (--amount
!= 0);
368 lzma_mf_hc4_find(lzma_mf
*mf
, lzma_match
*matches
)
370 header_find(false, 4);
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
];
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
;
383 uint32_t len_best
= 1;
385 if (delta2
< mf
->cyclic_size
&& *(cur
- delta2
) == *cur
) {
388 matches
[0].dist
= delta2
- 1;
392 if (delta2
!= delta3
&& delta3
< mf
->cyclic_size
393 && *(cur
- delta3
) == *cur
) {
395 matches
[matches_count
++].dist
= delta3
- 1;
399 if (matches_count
!= 0) {
400 for ( ; len_best
!= len_limit
; ++len_best
)
401 if (*(cur
+ len_best
- delta2
) != cur
[len_best
])
404 matches
[matches_count
- 1].len
= len_best
;
406 if (len_best
== len_limit
) {
408 return matches_count
;
420 lzma_mf_hc4_skip(lzma_mf
*mf
, uint32_t amount
)
423 if (mf_avail(mf
) < 4) {
428 const uint8_t *cur
= mf_ptr(mf
);
429 const uint32_t pos
= mf
->read_pos
+ mf
->offset
;
433 const uint32_t cur_match
434 = mf
->hash
[FIX_4_HASH_SIZE
+ hash_value
];
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
;
442 } while (--amount
!= 0);
451 #if defined(HAVE_MF_BT2) || defined(HAVE_MF_BT3) || defined(HAVE_MF_BT4)
454 const uint32_t len_limit
,
456 const uint8_t *const cur
,
460 const uint32_t cyclic_pos
,
461 const uint32_t cyclic_size
,
465 uint32_t *ptr0
= son
+ (cyclic_pos
<< 1) + 1;
466 uint32_t *ptr1
= son
+ (cyclic_pos
<< 1);
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
;
479 uint32_t *const pair
= son
+ ((cyclic_pos
- delta
480 + (delta
> cyclic_pos
? cyclic_size
: 0))
483 const uint8_t *const pb
= cur
- delta
;
484 uint32_t len
= my_min(len0
, len1
);
486 if (pb
[len
] == cur
[len
]) {
487 while (++len
!= len_limit
)
488 if (pb
[len
] != cur
[len
])
491 if (len_best
< len
) {
494 matches
->dist
= delta
- 1;
497 if (len
== len_limit
) {
505 if (pb
[len
] < cur
[len
]) {
522 const uint32_t len_limit
,
524 const uint8_t *const cur
,
528 const uint32_t cyclic_pos
,
529 const uint32_t cyclic_size
)
531 uint32_t *ptr0
= son
+ (cyclic_pos
<< 1) + 1;
532 uint32_t *ptr1
= son
+ (cyclic_pos
<< 1);
538 const uint32_t delta
= pos
- cur_match
;
539 if (depth
-- == 0 || delta
>= cyclic_size
) {
540 *ptr0
= EMPTY_HASH_VALUE
;
541 *ptr1
= EMPTY_HASH_VALUE
;
545 uint32_t *pair
= son
+ ((cyclic_pos
- delta
546 + (delta
> cyclic_pos
? cyclic_size
: 0))
548 const uint8_t *pb
= cur
- delta
;
549 uint32_t len
= my_min(len0
, len1
);
551 if (pb
[len
] == cur
[len
]) {
552 while (++len
!= len_limit
)
553 if (pb
[len
] != cur
[len
])
556 if (len
== len_limit
) {
563 if (pb
[len
] < cur
[len
]) {
578 #define bt_find(len_best) \
579 call_find(bt_find_func, len_best)
583 bt_skip_func(len_limit, pos, cur, cur_match, mf->depth, \
584 mf->son, mf->cyclic_pos, \
594 lzma_mf_bt2_find(lzma_mf
*mf
, lzma_match
*matches
)
596 header_find(true, 2);
600 const uint32_t cur_match
= mf
->hash
[hash_value
];
601 mf
->hash
[hash_value
] = pos
;
608 lzma_mf_bt2_skip(lzma_mf
*mf
, uint32_t amount
)
611 header_skip(true, 2);
615 const uint32_t cur_match
= mf
->hash
[hash_value
];
616 mf
->hash
[hash_value
] = pos
;
620 } while (--amount
!= 0);
627 lzma_mf_bt3_find(lzma_mf
*mf
, lzma_match
*matches
)
629 header_find(true, 3);
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
];
636 mf
->hash
[hash_2_value
] = pos
;
637 mf
->hash
[FIX_3_HASH_SIZE
+ hash_value
] = pos
;
639 uint32_t len_best
= 2;
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
])
646 matches
[0].len
= len_best
;
647 matches
[0].dist
= delta2
- 1;
650 if (len_best
== len_limit
) {
652 return 1; // matches_count
661 lzma_mf_bt3_skip(lzma_mf
*mf
, uint32_t amount
)
664 header_skip(true, 3);
668 const uint32_t cur_match
669 = mf
->hash
[FIX_3_HASH_SIZE
+ hash_value
];
671 mf
->hash
[hash_2_value
] = pos
;
672 mf
->hash
[FIX_3_HASH_SIZE
+ hash_value
] = pos
;
676 } while (--amount
!= 0);
683 lzma_mf_bt4_find(lzma_mf
*mf
, lzma_match
*matches
)
685 header_find(true, 4);
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
];
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
;
698 uint32_t len_best
= 1;
700 if (delta2
< mf
->cyclic_size
&& *(cur
- delta2
) == *cur
) {
703 matches
[0].dist
= delta2
- 1;
707 if (delta2
!= delta3
&& delta3
< mf
->cyclic_size
708 && *(cur
- delta3
) == *cur
) {
710 matches
[matches_count
++].dist
= delta3
- 1;
714 if (matches_count
!= 0) {
715 for ( ; len_best
!= len_limit
; ++len_best
)
716 if (*(cur
+ len_best
- delta2
) != cur
[len_best
])
719 matches
[matches_count
- 1].len
= len_best
;
721 if (len_best
== len_limit
) {
723 return matches_count
;
735 lzma_mf_bt4_skip(lzma_mf
*mf
, uint32_t amount
)
738 header_skip(true, 4);
742 const uint32_t cur_match
743 = mf
->hash
[FIX_4_HASH_SIZE
+ hash_value
];
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
;
751 } while (--amount
!= 0);