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