1*3b35e7eeSXin LI // SPDX-License-Identifier: 0BSD
2*3b35e7eeSXin LI
381ad8388SMartin Matuska ///////////////////////////////////////////////////////////////////////////////
481ad8388SMartin Matuska //
581ad8388SMartin Matuska /// \file lzma_encoder_optimum_fast.c
681ad8388SMartin Matuska //
781ad8388SMartin Matuska // Author: Igor Pavlov
881ad8388SMartin Matuska //
981ad8388SMartin Matuska ///////////////////////////////////////////////////////////////////////////////
1081ad8388SMartin Matuska
1181ad8388SMartin Matuska #include "lzma_encoder_private.h"
1253200025SRui Paulo #include "memcmplen.h"
1381ad8388SMartin Matuska
1481ad8388SMartin Matuska
1581ad8388SMartin Matuska #define change_pair(small_dist, big_dist) \
1681ad8388SMartin Matuska (((big_dist) >> 7) > (small_dist))
1781ad8388SMartin Matuska
1881ad8388SMartin Matuska
1981ad8388SMartin Matuska extern void
lzma_lzma_optimum_fast(lzma_lzma1_encoder * restrict coder,lzma_mf * restrict mf,uint32_t * restrict back_res,uint32_t * restrict len_res)201456f0f9SXin LI lzma_lzma_optimum_fast(lzma_lzma1_encoder *restrict coder,
211456f0f9SXin LI lzma_mf *restrict mf,
2281ad8388SMartin Matuska uint32_t *restrict back_res, uint32_t *restrict len_res)
2381ad8388SMartin Matuska {
2481ad8388SMartin Matuska const uint32_t nice_len = mf->nice_len;
2581ad8388SMartin Matuska
2681ad8388SMartin Matuska uint32_t len_main;
2781ad8388SMartin Matuska uint32_t matches_count;
2881ad8388SMartin Matuska if (mf->read_ahead == 0) {
2981ad8388SMartin Matuska len_main = mf_find(mf, &matches_count, coder->matches);
3081ad8388SMartin Matuska } else {
3181ad8388SMartin Matuska assert(mf->read_ahead == 1);
3281ad8388SMartin Matuska len_main = coder->longest_match_length;
3381ad8388SMartin Matuska matches_count = coder->matches_count;
3481ad8388SMartin Matuska }
3581ad8388SMartin Matuska
3681ad8388SMartin Matuska const uint8_t *buf = mf_ptr(mf) - 1;
37e0f0e66dSMartin Matuska const uint32_t buf_avail = my_min(mf_avail(mf) + 1, MATCH_LEN_MAX);
3881ad8388SMartin Matuska
3981ad8388SMartin Matuska if (buf_avail < 2) {
4081ad8388SMartin Matuska // There's not enough input left to encode a match.
4181ad8388SMartin Matuska *back_res = UINT32_MAX;
4281ad8388SMartin Matuska *len_res = 1;
4381ad8388SMartin Matuska return;
4481ad8388SMartin Matuska }
4581ad8388SMartin Matuska
4681ad8388SMartin Matuska // Look for repeated matches; scan the previous four match distances
4781ad8388SMartin Matuska uint32_t rep_len = 0;
4881ad8388SMartin Matuska uint32_t rep_index = 0;
4981ad8388SMartin Matuska
5053200025SRui Paulo for (uint32_t i = 0; i < REPS; ++i) {
5181ad8388SMartin Matuska // Pointer to the beginning of the match candidate
5281ad8388SMartin Matuska const uint8_t *const buf_back = buf - coder->reps[i] - 1;
5381ad8388SMartin Matuska
5481ad8388SMartin Matuska // If the first two bytes (2 == MATCH_LEN_MIN) do not match,
5581ad8388SMartin Matuska // this rep is not useful.
5681ad8388SMartin Matuska if (not_equal_16(buf, buf_back))
5781ad8388SMartin Matuska continue;
5881ad8388SMartin Matuska
5981ad8388SMartin Matuska // The first two bytes matched.
6081ad8388SMartin Matuska // Calculate the length of the match.
6153200025SRui Paulo const uint32_t len = lzma_memcmplen(
6253200025SRui Paulo buf, buf_back, 2, buf_avail);
6381ad8388SMartin Matuska
6481ad8388SMartin Matuska // If we have found a repeated match that is at least
6581ad8388SMartin Matuska // nice_len long, return it immediately.
6681ad8388SMartin Matuska if (len >= nice_len) {
6781ad8388SMartin Matuska *back_res = i;
6881ad8388SMartin Matuska *len_res = len;
6981ad8388SMartin Matuska mf_skip(mf, len - 1);
7081ad8388SMartin Matuska return;
7181ad8388SMartin Matuska }
7281ad8388SMartin Matuska
7381ad8388SMartin Matuska if (len > rep_len) {
7481ad8388SMartin Matuska rep_index = i;
7581ad8388SMartin Matuska rep_len = len;
7681ad8388SMartin Matuska }
7781ad8388SMartin Matuska }
7881ad8388SMartin Matuska
7981ad8388SMartin Matuska // We didn't find a long enough repeated match. Encode it as a normal
8081ad8388SMartin Matuska // match if the match length is at least nice_len.
8181ad8388SMartin Matuska if (len_main >= nice_len) {
8253200025SRui Paulo *back_res = coder->matches[matches_count - 1].dist + REPS;
8381ad8388SMartin Matuska *len_res = len_main;
8481ad8388SMartin Matuska mf_skip(mf, len_main - 1);
8581ad8388SMartin Matuska return;
8681ad8388SMartin Matuska }
8781ad8388SMartin Matuska
8881ad8388SMartin Matuska uint32_t back_main = 0;
8981ad8388SMartin Matuska if (len_main >= 2) {
9081ad8388SMartin Matuska back_main = coder->matches[matches_count - 1].dist;
9181ad8388SMartin Matuska
9281ad8388SMartin Matuska while (matches_count > 1 && len_main ==
9381ad8388SMartin Matuska coder->matches[matches_count - 2].len + 1) {
9481ad8388SMartin Matuska if (!change_pair(coder->matches[
9581ad8388SMartin Matuska matches_count - 2].dist,
9681ad8388SMartin Matuska back_main))
9781ad8388SMartin Matuska break;
9881ad8388SMartin Matuska
9981ad8388SMartin Matuska --matches_count;
10081ad8388SMartin Matuska len_main = coder->matches[matches_count - 1].len;
10181ad8388SMartin Matuska back_main = coder->matches[matches_count - 1].dist;
10281ad8388SMartin Matuska }
10381ad8388SMartin Matuska
10481ad8388SMartin Matuska if (len_main == 2 && back_main >= 0x80)
10581ad8388SMartin Matuska len_main = 1;
10681ad8388SMartin Matuska }
10781ad8388SMartin Matuska
10881ad8388SMartin Matuska if (rep_len >= 2) {
10981ad8388SMartin Matuska if (rep_len + 1 >= len_main
11081ad8388SMartin Matuska || (rep_len + 2 >= len_main
11181ad8388SMartin Matuska && back_main > (UINT32_C(1) << 9))
11281ad8388SMartin Matuska || (rep_len + 3 >= len_main
11381ad8388SMartin Matuska && back_main > (UINT32_C(1) << 15))) {
11481ad8388SMartin Matuska *back_res = rep_index;
11581ad8388SMartin Matuska *len_res = rep_len;
11681ad8388SMartin Matuska mf_skip(mf, rep_len - 1);
11781ad8388SMartin Matuska return;
11881ad8388SMartin Matuska }
11981ad8388SMartin Matuska }
12081ad8388SMartin Matuska
12181ad8388SMartin Matuska if (len_main < 2 || buf_avail <= 2) {
12281ad8388SMartin Matuska *back_res = UINT32_MAX;
12381ad8388SMartin Matuska *len_res = 1;
12481ad8388SMartin Matuska return;
12581ad8388SMartin Matuska }
12681ad8388SMartin Matuska
12781ad8388SMartin Matuska // Get the matches for the next byte. If we find a better match,
12881ad8388SMartin Matuska // the current byte is encoded as a literal.
12981ad8388SMartin Matuska coder->longest_match_length = mf_find(mf,
13081ad8388SMartin Matuska &coder->matches_count, coder->matches);
13181ad8388SMartin Matuska
13281ad8388SMartin Matuska if (coder->longest_match_length >= 2) {
13381ad8388SMartin Matuska const uint32_t new_dist = coder->matches[
13481ad8388SMartin Matuska coder->matches_count - 1].dist;
13581ad8388SMartin Matuska
13681ad8388SMartin Matuska if ((coder->longest_match_length >= len_main
13781ad8388SMartin Matuska && new_dist < back_main)
13881ad8388SMartin Matuska || (coder->longest_match_length == len_main + 1
13981ad8388SMartin Matuska && !change_pair(back_main, new_dist))
14081ad8388SMartin Matuska || (coder->longest_match_length > len_main + 1)
14181ad8388SMartin Matuska || (coder->longest_match_length + 1 >= len_main
14281ad8388SMartin Matuska && len_main >= 3
14381ad8388SMartin Matuska && change_pair(new_dist, back_main))) {
14481ad8388SMartin Matuska *back_res = UINT32_MAX;
14581ad8388SMartin Matuska *len_res = 1;
14681ad8388SMartin Matuska return;
14781ad8388SMartin Matuska }
14881ad8388SMartin Matuska }
14981ad8388SMartin Matuska
15081ad8388SMartin Matuska // In contrast to LZMA SDK, dictionary could not have been moved
15181ad8388SMartin Matuska // between mf_find() calls, thus it is safe to just increment
15281ad8388SMartin Matuska // the old buf pointer instead of recalculating it with mf_ptr().
15381ad8388SMartin Matuska ++buf;
15481ad8388SMartin Matuska
155342bcb12SXin LI const uint32_t limit = my_max(2, len_main - 1);
15681ad8388SMartin Matuska
15753200025SRui Paulo for (uint32_t i = 0; i < REPS; ++i) {
15853200025SRui Paulo if (memcmp(buf, buf - coder->reps[i] - 1, limit) == 0) {
15981ad8388SMartin Matuska *back_res = UINT32_MAX;
16081ad8388SMartin Matuska *len_res = 1;
16181ad8388SMartin Matuska return;
16281ad8388SMartin Matuska }
16381ad8388SMartin Matuska }
16481ad8388SMartin Matuska
16553200025SRui Paulo *back_res = back_main + REPS;
16681ad8388SMartin Matuska *len_res = len_main;
16781ad8388SMartin Matuska mf_skip(mf, len_main - 2);
16881ad8388SMartin Matuska return;
16981ad8388SMartin Matuska }
170