1 ///////////////////////////////////////////////////////////////////////////////
3 /// \file lzma_encoder_optimum_fast.c
7 // This file has been put into the public domain.
8 // You can do whatever you want with this file.
10 ///////////////////////////////////////////////////////////////////////////////
12 #include "lzma_encoder_private.h"
15 #define change_pair(small_dist, big_dist) \
16 (((big_dist) >> 7) > (small_dist))
20 lzma_lzma_optimum_fast(lzma_coder *restrict coder, lzma_mf *restrict mf,
21 uint32_t *restrict back_res, uint32_t *restrict len_res)
23 const uint32_t nice_len = mf->nice_len;
26 uint32_t matches_count;
27 if (mf->read_ahead == 0) {
28 len_main = mf_find(mf, &matches_count, coder->matches);
30 assert(mf->read_ahead == 1);
31 len_main = coder->longest_match_length;
32 matches_count = coder->matches_count;
35 const uint8_t *buf = mf_ptr(mf) - 1;
36 const uint32_t buf_avail = my_min(mf_avail(mf) + 1, MATCH_LEN_MAX);
39 // There's not enough input left to encode a match.
40 *back_res = UINT32_MAX;
45 // Look for repeated matches; scan the previous four match distances
47 uint32_t rep_index = 0;
49 for (uint32_t i = 0; i < REPS; ++i) {
50 // Pointer to the beginning of the match candidate
51 const uint8_t *const buf_back = buf - coder->reps[i] - 1;
53 // If the first two bytes (2 == MATCH_LEN_MIN) do not match,
54 // this rep is not useful.
55 if (not_equal_16(buf, buf_back))
58 // The first two bytes matched.
59 // Calculate the length of the match.
61 for (len = 2; len < buf_avail
62 && buf[len] == buf_back[len]; ++len) ;
64 // If we have found a repeated match that is at least
65 // nice_len long, return it immediately.
66 if (len >= nice_len) {
79 // We didn't find a long enough repeated match. Encode it as a normal
80 // match if the match length is at least nice_len.
81 if (len_main >= nice_len) {
82 *back_res = coder->matches[matches_count - 1].dist + REPS;
84 mf_skip(mf, len_main - 1);
88 uint32_t back_main = 0;
90 back_main = coder->matches[matches_count - 1].dist;
92 while (matches_count > 1 && len_main ==
93 coder->matches[matches_count - 2].len + 1) {
94 if (!change_pair(coder->matches[
95 matches_count - 2].dist,
100 len_main = coder->matches[matches_count - 1].len;
101 back_main = coder->matches[matches_count - 1].dist;
104 if (len_main == 2 && back_main >= 0x80)
109 if (rep_len + 1 >= len_main
110 || (rep_len + 2 >= len_main
111 && back_main > (UINT32_C(1) << 9))
112 || (rep_len + 3 >= len_main
113 && back_main > (UINT32_C(1) << 15))) {
114 *back_res = rep_index;
116 mf_skip(mf, rep_len - 1);
121 if (len_main < 2 || buf_avail <= 2) {
122 *back_res = UINT32_MAX;
127 // Get the matches for the next byte. If we find a better match,
128 // the current byte is encoded as a literal.
129 coder->longest_match_length = mf_find(mf,
130 &coder->matches_count, coder->matches);
132 if (coder->longest_match_length >= 2) {
133 const uint32_t new_dist = coder->matches[
134 coder->matches_count - 1].dist;
136 if ((coder->longest_match_length >= len_main
137 && new_dist < back_main)
138 || (coder->longest_match_length == len_main + 1
139 && !change_pair(back_main, new_dist))
140 || (coder->longest_match_length > len_main + 1)
141 || (coder->longest_match_length + 1 >= len_main
143 && change_pair(new_dist, back_main))) {
144 *back_res = UINT32_MAX;
150 // In contrast to LZMA SDK, dictionary could not have been moved
151 // between mf_find() calls, thus it is safe to just increment
152 // the old buf pointer instead of recalculating it with mf_ptr().
155 const uint32_t limit = len_main - 1;
157 for (uint32_t i = 0; i < REPS; ++i) {
158 const uint8_t *const buf_back = buf - coder->reps[i] - 1;
160 if (not_equal_16(buf, buf_back))
164 for (len = 2; len < limit
165 && buf[len] == buf_back[len]; ++len) ;
168 *back_res = UINT32_MAX;
174 *back_res = back_main + REPS;
176 mf_skip(mf, len_main - 2);