contrib/xz/src/liblzma/lzma/lzma_encoder_optimum_fast.c

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 /// \file       lzma_encoder_optimum_fast.c
   4 //
   5 //  Author:     Igor Pavlov
   6 //
   7 //  This file has been put into the public domain.
   8 //  You can do whatever you want with this file.
   9 //
  10 ///////////////////////////////////////////////////////////////////////////////
  11
  12 #include "lzma_encoder_private.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_coder *restrict coder, lzma_mf *restrict mf,
  21                 uint32_t *restrict back_res, uint32_t *restrict len_res)
  22 {
  23         const uint32_t nice_len = mf->nice_len;
  24
  25         uint32_t len_main;
  26         uint32_t matches_count;
  27         if (mf->read_ahead == 0) {
  28                 len_main = mf_find(mf, &matches_count, coder->matches);
  29         } else {
  30                 assert(mf->read_ahead == 1);
  31                 len_main = coder->longest_match_length;
  32                 matches_count = coder->matches_count;
  33         }
  34
  35         const uint8_t *buf = mf_ptr(mf) - 1;
  36         const uint32_t buf_avail = my_min(mf_avail(mf) + 1, MATCH_LEN_MAX);
  37
  38         if (buf_avail < 2) {
  39                 // There's not enough input left to encode a match.
  40                 *back_res = UINT32_MAX;
  41                 *len_res = 1;
  42                 return;
  43         }
  44
  45         // Look for repeated matches; scan the previous four match distances
  46         uint32_t rep_len = 0;
  47         uint32_t rep_index = 0;
  48
  49         for (uint32_t i = 0; i < REP_DISTANCES; ++i) {
  50                 // Pointer to the beginning of the match candidate
  51                 const uint8_t *const buf_back = buf - coder->reps[i] - 1;
  52
  53                 // If the first two bytes (2 == MATCH_LEN_MIN) do not match,
  54                 // this rep is not useful.
  55                 if (not_equal_16(buf, buf_back))
  56                         continue;
  57
  58                 // The first two bytes matched.
  59                 // Calculate the length of the match.
  60                 uint32_t len;
  61                 for (len = 2; len < buf_avail
  62                                 && buf[len] == buf_back[len]; ++len) ;
  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
  83                                 + REP_DISTANCES;
  84                 *len_res = len_main;
  85                 mf_skip(mf, len_main - 1);
  86                 return;
  87         }
  88
  89         uint32_t back_main = 0;
  90         if (len_main >= 2) {
  91                 back_main = coder->matches[matches_count - 1].dist;
  92
  93                 while (matches_count > 1 && len_main ==
  94                                 coder->matches[matches_count - 2].len + 1) {
  95                         if (!change_pair(coder->matches[
  96                                                 matches_count - 2].dist,
  97                                         back_main))
  98                                 break;
  99
 100                         --matches_count;
 101                         len_main = coder->matches[matches_count - 1].len;
 102                         back_main = coder->matches[matches_count - 1].dist;
 103                 }
 104
 105                 if (len_main == 2 && back_main >= 0x80)
 106                         len_main = 1;
 107         }
 108
 109         if (rep_len >= 2) {
 110                 if (rep_len + 1 >= len_main
 111                                 || (rep_len + 2 >= len_main
 112                                         && back_main > (UINT32_C(1) << 9))
 113                                 || (rep_len + 3 >= len_main
 114                                         && back_main > (UINT32_C(1) << 15))) {
 115                         *back_res = rep_index;
 116                         *len_res = rep_len;
 117                         mf_skip(mf, rep_len - 1);
 118                         return;
 119                 }
 120         }
 121
 122         if (len_main < 2 || buf_avail <= 2) {
 123                 *back_res = UINT32_MAX;
 124                 *len_res = 1;
 125                 return;
 126         }
 127
 128         // Get the matches for the next byte. If we find a better match,
 129         // the current byte is encoded as a literal.
 130         coder->longest_match_length = mf_find(mf,
 131                         &coder->matches_count, coder->matches);
 132
 133         if (coder->longest_match_length >= 2) {
 134                 const uint32_t new_dist = coder->matches[
 135                                 coder->matches_count - 1].dist;
 136
 137                 if ((coder->longest_match_length >= len_main
 138                                         && new_dist < back_main)
 139                                 || (coder->longest_match_length == len_main + 1
 140                                         && !change_pair(back_main, new_dist))
 141                                 || (coder->longest_match_length > len_main + 1)
 142                                 || (coder->longest_match_length + 1 >= len_main
 143                                         && len_main >= 3
 144                                         && change_pair(new_dist, back_main))) {
 145                         *back_res = UINT32_MAX;
 146                         *len_res = 1;
 147                         return;
 148                 }
 149         }
 150
 151         // In contrast to LZMA SDK, dictionary could not have been moved
 152         // between mf_find() calls, thus it is safe to just increment
 153         // the old buf pointer instead of recalculating it with mf_ptr().
 154         ++buf;
 155
 156         const uint32_t limit = len_main - 1;
 157
 158         for (uint32_t i = 0; i < REP_DISTANCES; ++i) {
 159                 const uint8_t *const buf_back = buf - coder->reps[i] - 1;
 160
 161                 if (not_equal_16(buf, buf_back))
 162                         continue;
 163
 164                 uint32_t len;
 165                 for (len = 2; len < limit
 166                                 && buf[len] == buf_back[len]; ++len) ;
 167
 168                 if (len >= limit) {
 169                         *back_res = UINT32_MAX;
 170                         *len_res = 1;
 171                         return;
 172                 }
 173         }
 174
 175         *back_res = back_main + REP_DISTANCES;
 176         *len_res = len_main;
 177         mf_skip(mf, len_main - 2);
 178         return;
 179 }