src/liblzma/lzma/lzma_encoder_optimum_fast.c

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 /// \file       lzma_encoder_optimum_fast.c
   4 //
   5 //  Copyright (C) 1999-2008 Igor Pavlov
   6 //
   7 //  This library is free software; you can redistribute it and/or
   8 //  modify it under the terms of the GNU Lesser General Public
   9 //  License as published by the Free Software Foundation; either
  10 //  version 2.1 of the License, or (at your option) any later version.
  11 //
  12 //  This library is distributed in the hope that it will be useful,
  13 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 //  Lesser General Public License for more details.
  16 //
  17 ///////////////////////////////////////////////////////////////////////////////
  18
  19 #include "lzma_encoder_private.h"
  20
  21
  22 #define change_pair(small_dist, big_dist) \
  23         (((big_dist) >> 7) > (small_dist))
  24
  25
  26 static inline void
  27 literal(const lzma_coder *restrict coder, const uint8_t *restrict buf,
  28                 uint32_t *restrict back_res, uint32_t *restrict len_res)
  29 {
  30         // Try short rep0 instead of always coding it as a literal.
  31         *back_res = *buf == *(buf - coder->reps[0] - 1) ? 0 : UINT32_MAX;
  32         *len_res = 1;
  33         return;
  34 }
  35
  36
  37 extern void
  38 lzma_lzma_optimum_fast(lzma_coder *restrict coder, lzma_mf *restrict mf,
  39                 uint32_t *restrict back_res, uint32_t *restrict len_res)
  40 {
  41         const uint32_t nice_len = mf->nice_len;
  42
  43         uint32_t len_main;
  44         uint32_t matches_count;
  45         if (mf->read_ahead == 0) {
  46                 len_main = mf_find(mf, &matches_count, coder->matches);
  47         } else {
  48                 assert(mf->read_ahead == 1);
  49                 len_main = coder->longest_match_length;
  50                 matches_count = coder->matches_count;
  51         }
  52
  53         const uint8_t *buf = mf_ptr(mf) - 1;
  54         const uint32_t buf_avail = MIN(mf_avail(mf) + 1, MATCH_LEN_MAX);
  55
  56         if (buf_avail < 2) {
  57                 // There's not enough input left to encode a match.
  58                 literal(coder, buf, back_res, len_res);
  59                 return;
  60         }
  61
  62         // Look for repeated matches; scan the previous four match distances
  63         uint32_t rep_len = 0;
  64         uint32_t rep_index = 0;
  65
  66         for (uint32_t i = 0; i < REP_DISTANCES; ++i) {
  67                 // Pointer to the beginning of the match candidate
  68                 const uint8_t *const buf_back = buf - coder->reps[i] - 1;
  69
  70                 // If the first two bytes (2 == MATCH_LEN_MIN) do not match,
  71                 // this rep is not useful.
  72                 if (not_equal_16(buf, buf_back))
  73                         continue;
  74
  75                 // The first two bytes matched.
  76                 // Calculate the length of the match.
  77                 uint32_t len;
  78                 for (len = 2; len < buf_avail
  79                                 && buf[len] == buf_back[len]; ++len) ;
  80
  81                 // If we have found a repeated match that is at least
  82                 // nice_len long, return it immediatelly.
  83                 if (len >= nice_len) {
  84                         *back_res = i;
  85                         *len_res = len;
  86                         mf_skip(mf, len - 1);
  87                         return;
  88                 }
  89
  90                 if (len > rep_len) {
  91                         rep_index = i;
  92                         rep_len = len;
  93                 }
  94         }
  95
  96         // We didn't find a long enough repeated match. Encode it as a normal
  97         // match if the match length is at least nice_len.
  98         if (len_main >= nice_len) {
  99                 *back_res = coder->matches[matches_count - 1].dist
 100                                 + REP_DISTANCES;
 101                 *len_res = len_main;
 102                 mf_skip(mf, len_main - 1);
 103                 return;
 104         }
 105
 106         uint32_t back_main = 0;
 107         if (len_main >= 2) {
 108                 back_main = coder->matches[matches_count - 1].dist;
 109
 110                 while (matches_count > 1 && len_main ==
 111                                 coder->matches[matches_count - 2].len + 1) {
 112                         if (!change_pair(coder->matches[
 113                                                 matches_count - 2].dist,
 114                                         back_main))
 115                                 break;
 116
 117                         --matches_count;
 118                         len_main = coder->matches[matches_count - 1].len;
 119                         back_main = coder->matches[matches_count - 1].dist;
 120                 }
 121
 122                 if (len_main == 2 && back_main >= 0x80)
 123                         len_main = 1;
 124         }
 125
 126         if (rep_len >= 2) {
 127                 if (rep_len + 1 >= len_main
 128                                 || (rep_len + 2 >= len_main
 129                                         && back_main > (UINT32_C(1) << 9))
 130                                 || (rep_len + 3 >= len_main
 131                                         && back_main > (UINT32_C(1) << 15))) {
 132                         *back_res = rep_index;
 133                         *len_res = rep_len;
 134                         mf_skip(mf, rep_len - 1);
 135                         return;
 136                 }
 137         }
 138
 139         if (len_main < 2 || buf_avail <= 2) {
 140                 literal(coder, buf, back_res, len_res);
 141                 return;
 142         }
 143
 144         // Get the matches for the next byte. If we find a better match,
 145         // the current byte is encoded as a literal.
 146         coder->longest_match_length = mf_find(mf,
 147                         &coder->matches_count, coder->matches);
 148
 149         if (coder->longest_match_length >= 2) {
 150                 const uint32_t new_dist = coder->matches[
 151                                 coder->matches_count - 1].dist;
 152
 153                 if ((coder->longest_match_length >= len_main
 154                                         && new_dist < back_main)
 155                                 || (coder->longest_match_length == len_main + 1
 156                                         && !change_pair(back_main, new_dist))
 157                                 || (coder->longest_match_length > len_main + 1)
 158                                 || (coder->longest_match_length + 1 >= len_main
 159                                         && len_main >= 3
 160                                         && change_pair(new_dist, back_main))) {
 161                         literal(coder, buf, back_res, len_res);
 162                         return;
 163                 }
 164         }
 165
 166         // In contrast to LZMA SDK, dictionary could not have been moved
 167         // between mf_find() calls, thus it is safe to just increment
 168         // the old buf pointer instead of recalculating it with mf_ptr().
 169         ++buf;
 170
 171         const uint32_t limit = len_main - 1;
 172
 173         for (uint32_t i = 0; i < REP_DISTANCES; ++i) {
 174                 const uint8_t *const buf_back = buf - coder->reps[i] - 1;
 175
 176                 if (not_equal_16(buf, buf_back))
 177                         continue;
 178
 179                 uint32_t len;
 180                 for (len = 2; len < limit
 181                                 && buf[len] == buf_back[len]; ++len) ;
 182
 183                 if (len >= limit) {
 184                         literal(coder, buf - 1, back_res, len_res);
 185                         return;
 186                 }
 187         }
 188
 189         *back_res = back_main + REP_DISTANCES;
 190         *len_res = len_main;
 191         mf_skip(mf, len_main - 2);
 192         return;
 193 }