Home | History | Annotate | Line # | Download | only in lzma 
      1 // SPDX-License-Identifier: 0BSD
      2 
      3 ///////////////////////////////////////////////////////////////////////////////
      4 //
      5 /// \file       lzma_encoder_optimum_fast.c
      6 //
      7 //  Author:     Igor Pavlov
      8 //
      9 ///////////////////////////////////////////////////////////////////////////////
     10 
     11 #include "lzma_encoder_private.h"
     12 #include "memcmplen.h"
     13 
     14 
     15 #define change_pair(small_dist, big_dist) \
     16 	(((big_dist) >> 7) > (small_dist))
     17 
     18 
     19 extern void
     20 lzma_lzma_optimum_fast(lzma_lzma1_encoder *restrict coder,
     21 		lzma_mf *restrict mf,
     22 		uint32_t *restrict back_res, uint32_t *restrict len_res)
     23 {
     24 	const uint32_t nice_len = mf->nice_len;
     25 
     26 	uint32_t len_main;
     27 	uint32_t matches_count;
     28 	if (mf->read_ahead == 0) {
     29 		len_main = mf_find(mf, &matches_count, coder->matches);
     30 	} else {
     31 		assert(mf->read_ahead == 1);
     32 		len_main = coder->longest_match_length;
     33 		matches_count = coder->matches_count;
     34 	}
     35 
     36 	const uint8_t *buf = mf_ptr(mf) - 1;
     37 	const uint32_t buf_avail = my_min(mf_avail(mf) + 1, MATCH_LEN_MAX);
     38 
     39 	if (buf_avail < 2) {
     40 		// There's not enough input left to encode a match.
     41 		*back_res = UINT32_MAX;
     42 		*len_res = 1;
     43 		return;
     44 	}
     45 
     46 	// Look for repeated matches; scan the previous four match distances
     47 	uint32_t rep_len = 0;
     48 	uint32_t rep_index = 0;
     49 
     50 	for (uint32_t i = 0; i < REPS; ++i) {
     51 		// Pointer to the beginning of the match candidate
     52 		const uint8_t *const buf_back = buf - coder->reps[i] - 1;
     53 
     54 		// If the first two bytes (2 == MATCH_LEN_MIN) do not match,
     55 		// this rep is not useful.
     56 		if (not_equal_16(buf, buf_back))
     57 			continue;
     58 
     59 		// The first two bytes matched.
     60 		// Calculate the length of the match.
     61 		const uint32_t len = lzma_memcmplen(
     62 				buf, buf_back, 2, buf_avail);
     63 
     64 		// If we have found a repeated match that is at least
     65 		// nice_len long, return it immediately.
     66 		if (len >= nice_len) {
     67 			*back_res = i;
     68 			*len_res = len;
     69 			mf_skip(mf, len - 1);
     70 			return;
     71 		}
     72 
     73 		if (len > rep_len) {
     74 			rep_index = i;
     75 			rep_len = len;
     76 		}
     77 	}
     78 
     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;
     83 		*len_res = len_main;
     84 		mf_skip(mf, len_main - 1);
     85 		return;
     86 	}
     87 
     88 	uint32_t back_main = 0;
     89 	if (len_main >= 2) {
     90 		back_main = coder->matches[matches_count - 1].dist;
     91 
     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,
     96 					back_main))
     97 				break;
     98 
     99 			--matches_count;
    100 			len_main = coder->matches[matches_count - 1].len;
    101 			back_main = coder->matches[matches_count - 1].dist;
    102 		}
    103 
    104 		if (len_main == 2 && back_main >= 0x80)
    105 			len_main = 1;
    106 	}
    107 
    108 	if (rep_len >= 2) {
    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;
    115 			*len_res = rep_len;
    116 			mf_skip(mf, rep_len - 1);
    117 			return;
    118 		}
    119 	}
    120 
    121 	if (len_main < 2 || buf_avail <= 2) {
    122 		*back_res = UINT32_MAX;
    123 		*len_res = 1;
    124 		return;
    125 	}
    126 
    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);
    131 
    132 	if (coder->longest_match_length >= 2) {
    133 		const uint32_t new_dist = coder->matches[
    134 				coder->matches_count - 1].dist;
    135 
    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
    142 					&& len_main >= 3
    143 					&& change_pair(new_dist, back_main))) {
    144 			*back_res = UINT32_MAX;
    145 			*len_res = 1;
    146 			return;
    147 		}
    148 	}
    149 
    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().
    153 	++buf;
    154 
    155 	const uint32_t limit = my_max(2, len_main - 1);
    156 
    157 	for (uint32_t i = 0; i < REPS; ++i) {
    158 		if (memcmp(buf, buf - coder->reps[i] - 1, limit) == 0) {
    159 			*back_res = UINT32_MAX;
    160 			*len_res = 1;
    161 			return;
    162 		}
    163 	}
    164 
    165 	*back_res = back_main + REPS;
    166 	*len_res = len_main;
    167 	mf_skip(mf, len_main - 2);
    168 	return;
    169 }
    170