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