1 /* -*- mode: C; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 // vim: expandtab:ts=8:sw=4:softtabstop=4:
3 ///////////////////////////////////////////////////////////////////////////////
4 //
5 /// \file lzma_encoder_optimum_fast.c
6 //
7 // Author: Igor Pavlov
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 "lzma_encoder_private.h"
15
16
17 #define change_pair(small_dist, big_dist) \
18 (((big_dist) >> 7) > (small_dist))
19
20
21 extern void
lzma_lzma_optimum_fast(lzma_coder * restrict coder,lzma_mf * restrict mf,uint32_t * restrict back_res,uint32_t * restrict len_res)22 lzma_lzma_optimum_fast(lzma_coder *restrict coder, lzma_mf *restrict mf,
23 uint32_t *restrict back_res, uint32_t *restrict len_res)
24 {
25 const uint32_t nice_len = mf->nice_len;
26
27 uint32_t len_main;
28 uint32_t matches_count;
29 if (mf->read_ahead == 0) {
30 len_main = mf_find(mf, &matches_count, coder->matches);
31 } else {
32 assert(mf->read_ahead == 1);
33 len_main = coder->longest_match_length;
34 matches_count = coder->matches_count;
35 }
36
37 const uint8_t *buf = mf_ptr(mf) - 1;
38 const uint32_t buf_avail = MIN(mf_avail(mf) + 1, MATCH_LEN_MAX);
39
40 if (buf_avail < 2) {
41 // There's not enough input left to encode a match.
42 *back_res = UINT32_MAX;
43 *len_res = 1;
44 return;
45 }
46
47 // Look for repeated matches; scan the previous four match distances
48 uint32_t rep_len = 0;
49 uint32_t rep_index = 0;
50
51 for (uint32_t i = 0; i < REP_DISTANCES; ++i) {
52 // Pointer to the beginning of the match candidate
53 const uint8_t *const buf_back = buf - coder->reps[i] - 1;
54
55 // If the first two bytes (2 == MATCH_LEN_MIN) do not match,
56 // this rep is not useful.
57 if (not_equal_16(buf, buf_back))
58 continue;
59
60 // The first two bytes matched.
61 // Calculate the length of the match.
62 uint32_t len;
63 for (len = 2; len < buf_avail
64 && buf[len] == buf_back[len]; ++len) ;
65
66 // If we have found a repeated match that is at least
67 // nice_len long, return it immediatelly.
68 if (len >= nice_len) {
69 *back_res = i;
70 *len_res = len;
71 mf_skip(mf, len - 1);
72 return;
73 }
74
75 if (len > rep_len) {
76 rep_index = i;
77 rep_len = len;
78 }
79 }
80
81 // We didn't find a long enough repeated match. Encode it as a normal
82 // match if the match length is at least nice_len.
83 if (len_main >= nice_len) {
84 *back_res = coder->matches[matches_count - 1].dist
85 + REP_DISTANCES;
86 *len_res = len_main;
87 mf_skip(mf, len_main - 1);
88 return;
89 }
90
91 uint32_t back_main = 0;
92 if (len_main >= 2) {
93 back_main = coder->matches[matches_count - 1].dist;
94
95 while (matches_count > 1 && len_main ==
96 coder->matches[matches_count - 2].len + 1) {
97 if (!change_pair(coder->matches[
98 matches_count - 2].dist,
99 back_main))
100 break;
101
102 --matches_count;
103 len_main = coder->matches[matches_count - 1].len;
104 back_main = coder->matches[matches_count - 1].dist;
105 }
106
107 if (len_main == 2 && back_main >= 0x80)
108 len_main = 1;
109 }
110
111 if (rep_len >= 2) {
112 if (rep_len + 1 >= len_main
113 || (rep_len + 2 >= len_main
114 && back_main > (UINT32_C(1) << 9))
115 || (rep_len + 3 >= len_main
116 && back_main > (UINT32_C(1) << 15))) {
117 *back_res = rep_index;
118 *len_res = rep_len;
119 mf_skip(mf, rep_len - 1);
120 return;
121 }
122 }
123
124 if (len_main < 2 || buf_avail <= 2) {
125 *back_res = UINT32_MAX;
126 *len_res = 1;
127 return;
128 }
129
130 // Get the matches for the next byte. If we find a better match,
131 // the current byte is encoded as a literal.
132 coder->longest_match_length = mf_find(mf,
133 &coder->matches_count, coder->matches);
134
135 if (coder->longest_match_length >= 2) {
136 const uint32_t new_dist = coder->matches[
137 coder->matches_count - 1].dist;
138
139 if ((coder->longest_match_length >= len_main
140 && new_dist < back_main)
141 || (coder->longest_match_length == len_main + 1
142 && !change_pair(back_main, new_dist))
143 || (coder->longest_match_length > len_main + 1)
144 || (coder->longest_match_length + 1 >= len_main
145 && len_main >= 3
146 && change_pair(new_dist, back_main))) {
147 *back_res = UINT32_MAX;
148 *len_res = 1;
149 return;
150 }
151 }
152
153 // In contrast to LZMA SDK, dictionary could not have been moved
154 // between mf_find() calls, thus it is safe to just increment
155 // the old buf pointer instead of recalculating it with mf_ptr().
156 ++buf;
157
158 const uint32_t limit = len_main - 1;
159
160 for (uint32_t i = 0; i < REP_DISTANCES; ++i) {
161 const uint8_t *const buf_back = buf - coder->reps[i] - 1;
162
163 if (not_equal_16(buf, buf_back))
164 continue;
165
166 uint32_t len;
167 for (len = 2; len < limit
168 && buf[len] == buf_back[len]; ++len) ;
169
170 if (len >= limit) {
171 *back_res = UINT32_MAX;
172 *len_res = 1;
173 return;
174 }
175 }
176
177 *back_res = back_main + REP_DISTANCES;
178 *len_res = len_main;
179 mf_skip(mf, len_main - 2);
180 return;
181 }
182