1 ///////////////////////////////////////////////////////////////////////////////
3 /// \file lzma_encoder_getoptimumfast.c
5 // Copyright (C) 1999-2006 Igor Pavlov
6 // Copyright (C) 2007 Lasse Collin
8 // This library is free software; you can redistribute it and/or
9 // modify it under the terms of the GNU Lesser General Public
10 // License as published by the Free Software Foundation; either
11 // version 2.1 of the License, or (at your option) any later version.
13 // This library is distributed in the hope that it will be useful,
14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 // Lesser General Public License for more details.
18 ///////////////////////////////////////////////////////////////////////////////
20 // NOTE: If you want to keep the line length in 80 characters, set
21 // tab width to 4 or less in your editor when editing this file.
24 #include "lzma_encoder_private.h"
27 #define change_pair(small_dist, big_dist) \
28 (((big_dist) >> 7) > (small_dist))
32 lzma_get_optimum_fast(lzma_coder *restrict coder,
33 uint32_t *restrict back_res, uint32_t *restrict len_res)
36 const uint32_t fast_bytes = coder->fast_bytes;
39 uint32_t num_distance_pairs;
40 if (!coder->longest_match_was_found) {
41 lzma_read_match_distances(coder, &len_main, &num_distance_pairs);
43 len_main = coder->longest_match_length;
44 num_distance_pairs = coder->num_distance_pairs;
45 coder->longest_match_was_found = false;
48 const uint8_t *buf = coder->lz.buffer + coder->lz.read_pos - 1;
49 uint32_t num_available_bytes
50 = coder->lz.write_pos - coder->lz.read_pos + 1;
52 if (num_available_bytes < 2) {
53 // There's not enough input left to encode a match.
54 *back_res = UINT32_MAX;
59 if (num_available_bytes > MATCH_MAX_LEN)
60 num_available_bytes = MATCH_MAX_LEN;
63 // Look for repetitive matches; scan the previous four match distances
64 uint32_t rep_lens[REP_DISTANCES];
65 uint32_t rep_max_index = 0;
67 for (uint32_t i = 0; i < REP_DISTANCES; ++i) {
68 const uint32_t back_offset = coder->rep_distances[i] + 1;
70 // If the first two bytes (2 == MATCH_MIN_LEN) do not match,
71 // this rep_distance[i] is not useful. This is indicated
72 // using zero as the length of the repetitive match.
73 if (buf[0] != *(buf - back_offset)
74 || buf[1] != *(buf + 1 - back_offset)) {
79 // The first two bytes matched.
80 // Calculate the length of the match.
82 for (len = 2; len < num_available_bytes
83 && buf[len] == *(buf + len - back_offset);
86 // If we have found a repetitive match that is at least
87 // as long as fast_bytes, return it immediatelly.
88 if (len >= fast_bytes) {
97 // After this loop, rep_lens[rep_max_index] is the biggest
98 // value of all values in rep_lens[].
99 if (len > rep_lens[rep_max_index])
104 if (len_main >= fast_bytes) {
105 *back_res = coder->match_distances[num_distance_pairs]
108 move_pos(len_main - 1);
112 uint32_t back_main = 0;
114 back_main = coder->match_distances[num_distance_pairs];
116 while (num_distance_pairs > 2 && len_main ==
117 coder->match_distances[num_distance_pairs - 3] + 1) {
118 if (!change_pair(coder->match_distances[
119 num_distance_pairs - 2], back_main))
122 num_distance_pairs -= 2;
123 len_main = coder->match_distances[num_distance_pairs - 1];
124 back_main = coder->match_distances[num_distance_pairs];
127 if (len_main == 2 && back_main >= 0x80)
131 if (rep_lens[rep_max_index] >= 2) {
132 if (rep_lens[rep_max_index] + 1 >= len_main
133 || (rep_lens[rep_max_index] + 2 >= len_main
134 && (back_main > (1 << 9)))
135 || (rep_lens[rep_max_index] + 3 >= len_main
136 && (back_main > (1 << 15)))) {
137 *back_res = rep_max_index;
138 *len_res = rep_lens[rep_max_index];
139 move_pos(*len_res - 1);
144 if (len_main >= 2 && num_available_bytes > 2) {
145 lzma_read_match_distances(coder, &coder->longest_match_length,
146 &coder->num_distance_pairs);
148 if (coder->longest_match_length >= 2) {
149 const uint32_t new_distance = coder->match_distances[
150 coder->num_distance_pairs];
152 if ((coder->longest_match_length >= len_main
153 && new_distance < back_main)
154 || (coder->longest_match_length == len_main + 1
155 && !change_pair(back_main, new_distance))
156 || (coder->longest_match_length > len_main + 1)
157 || (coder->longest_match_length + 1 >= len_main
159 && change_pair(new_distance, back_main))) {
160 coder->longest_match_was_found = true;
161 *back_res = UINT32_MAX;
168 --num_available_bytes;
170 for (uint32_t i = 0; i < REP_DISTANCES; ++i) {
171 const uint32_t back_offset = coder->rep_distances[i] + 1;
173 if (buf[1] != *(buf + 1 - back_offset)
174 || buf[2] != *(buf + 2 - back_offset)) {
180 for (len = 2; len < num_available_bytes
181 && buf[len] == *(buf + len - back_offset);
184 if (len + 1 >= len_main) {
185 coder->longest_match_was_found = true;
186 *back_res = UINT32_MAX;
192 *back_res = back_main + REP_DISTANCES;
194 move_pos(len_main - 2);
198 *back_res = UINT32_MAX;