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