src/liblzma/lzma/lzma_encoder_getoptimumfast.c

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 /// \file       lzma_encoder_getoptimumfast.c
   4 //
   5 //  Copyright (C) 1999-2006 Igor Pavlov
   6 //  Copyright (C) 2007 Lasse Collin
   7 //
   8 //  This library is free software; you can redistribute it and/or
   9 //  modify it under the terms of the GNU Lesser General Public
  10 //  License as published by the Free Software Foundation; either
  11 //  version 2.1 of the License, or (at your option) any later version.
  12 //
  13 //  This library is distributed in the hope that it will be useful,
  14 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16 //  Lesser General Public License for more details.
  17 //
  18 ///////////////////////////////////////////////////////////////////////////////
  19
  20 // NOTE: If you want to keep the line length in 80 characters, set
  21 //       tab width to 4 or less in your editor when editing this file.
  22
  23
  24 #include "lzma_encoder_private.h"
  25
  26
  27 #define change_pair(small_dist, big_dist) \
  28         (((big_dist) >> 7) > (small_dist))
  29
  30
  31 extern void
  32 lzma_get_optimum_fast(lzma_coder *restrict coder,
  33                 uint32_t *restrict back_res, uint32_t *restrict len_res)
  34 {
  35         // Local copies
  36         const uint32_t fast_bytes = coder->fast_bytes;
  37
  38         uint32_t len_main;
  39         uint32_t num_distance_pairs;
  40         if (!coder->longest_match_was_found) {
  41                 lzma_read_match_distances(coder, &len_main, &num_distance_pairs);
  42         } else {
  43                 len_main = coder->longest_match_length;
  44                 num_distance_pairs = coder->num_distance_pairs;
  45                 coder->longest_match_was_found = false;
  46         }
  47
  48         const uint8_t *buf = coder->lz.buffer + coder->lz.read_pos - 1;
  49         uint32_t num_available_bytes
  50                         = coder->lz.write_pos - coder->lz.read_pos + 1;
  51
  52         if (num_available_bytes < 2) {
  53                 // There's not enough input left to encode a match.
  54                 *back_res = UINT32_MAX;
  55                 *len_res = 1;
  56                 return;
  57         }
  58
  59         if (num_available_bytes > MATCH_MAX_LEN)
  60                 num_available_bytes = MATCH_MAX_LEN;
  61
  62
  63         // Look for repetitive matches; scan the previous four match distances
  64         uint32_t rep_lens[REP_DISTANCES];
  65         uint32_t rep_max_index = 0;
  66
  67         for (uint32_t i = 0; i < REP_DISTANCES; ++i) {
  68                 const uint32_t back_offset = coder->rep_distances[i] + 1;
  69
  70                 // If the first two bytes (2 == MATCH_MIN_LEN) do not match,
  71                 // this rep_distance[i] is not useful. This is indicated
  72                 // using zero as the length of the repetitive match.
  73                 if (buf[0] != *(buf - back_offset)
  74                                 || buf[1] != *(buf + 1 - back_offset)) {
  75                         rep_lens[i] = 0;
  76                         continue;
  77                 }
  78
  79                 // The first two bytes matched.
  80                 // Calculate the length of the match.
  81                 uint32_t len;
  82                 for (len = 2; len < num_available_bytes
  83                                 && buf[len] == *(buf + len - back_offset);
  84                                 ++len) ;
  85
  86                 // If we have found a repetitive match that is at least
  87                 // as long as fast_bytes, return it immediatelly.
  88                 if (len >= fast_bytes) {
  89                         *back_res = i;
  90                         *len_res = len;
  91                         move_pos(len - 1);
  92                         return;
  93                 }
  94
  95                 rep_lens[i] = len;
  96
  97                 // After this loop, rep_lens[rep_max_index] is the biggest
  98                 // value of all values in rep_lens[].
  99                 if (len > rep_lens[rep_max_index])
 100                         rep_max_index = i;
 101         }
 102
 103
 104         if (len_main >= fast_bytes) {
 105                 *back_res = coder->match_distances[num_distance_pairs]
 106                                 + REP_DISTANCES;
 107                 *len_res = len_main;
 108                 move_pos(len_main - 1);
 109                 return;
 110         }
 111
 112         uint32_t back_main = 0;
 113         if (len_main >= 2) {
 114                 back_main = coder->match_distances[num_distance_pairs];
 115
 116                 while (num_distance_pairs > 2 && len_main ==
 117                                 coder->match_distances[num_distance_pairs - 3] + 1) {
 118                         if (!change_pair(coder->match_distances[
 119                                         num_distance_pairs - 2], back_main))
 120                                 break;
 121
 122                         num_distance_pairs -= 2;
 123                         len_main = coder->match_distances[num_distance_pairs - 1];
 124                         back_main = coder->match_distances[num_distance_pairs];
 125                 }
 126
 127                 if (len_main == 2 && back_main >= 0x80)
 128                         len_main = 1;
 129         }
 130
 131         if (rep_lens[rep_max_index] >= 2) {
 132                 if (rep_lens[rep_max_index] + 1 >= len_main
 133                                 || (rep_lens[rep_max_index] + 2 >= len_main
 134                                         && (back_main > (1 << 9)))
 135                                 || (rep_lens[rep_max_index] + 3 >= len_main
 136                                         && (back_main > (1 << 15)))) {
 137                         *back_res = rep_max_index;
 138                         *len_res = rep_lens[rep_max_index];
 139                         move_pos(*len_res - 1);
 140                         return;
 141                 }
 142         }
 143
 144         if (len_main >= 2 && num_available_bytes > 2) {
 145                 lzma_read_match_distances(coder, &coder->longest_match_length,
 146                                 &coder->num_distance_pairs);
 147
 148                 if (coder->longest_match_length >= 2) {
 149                         const uint32_t new_distance = coder->match_distances[
 150                                         coder->num_distance_pairs];
 151
 152                         if ((coder->longest_match_length >= len_main
 153                                                 && new_distance < back_main)
 154                                         || (coder->longest_match_length == len_main + 1
 155                                                 && !change_pair(back_main, new_distance))
 156                                         || (coder->longest_match_length > len_main + 1)
 157                                         || (coder->longest_match_length + 1 >= len_main
 158                                                 && len_main >= 3
 159                                                 && change_pair(new_distance, back_main))) {
 160                                 coder->longest_match_was_found = true;
 161                                 *back_res = UINT32_MAX;
 162                                 *len_res = 1;
 163                                 return;
 164                         }
 165                 }
 166
 167                 ++buf;
 168                 --num_available_bytes;
 169
 170                 for (uint32_t i = 0; i < REP_DISTANCES; ++i) {
 171                         const uint32_t back_offset = coder->rep_distances[i] + 1;
 172
 173                         if (buf[1] != *(buf + 1 - back_offset)
 174                                         || buf[2] != *(buf + 2 - back_offset)) {
 175                                 rep_lens[i] = 0;
 176                                 continue;
 177                         }
 178
 179                         uint32_t len;
 180                         for (len = 2; len < num_available_bytes
 181                                         && buf[len] == *(buf + len - back_offset);
 182                                         ++len) ;
 183
 184                         if (len + 1 >= len_main) {
 185                                 coder->longest_match_was_found = true;
 186                                 *back_res = UINT32_MAX;
 187                                 *len_res = 1;
 188                                 return;
 189                         }
 190                 }
 191
 192                 *back_res = back_main + REP_DISTANCES;
 193                 *len_res = len_main;
 194                 move_pos(len_main - 2);
 195                 return;
 196         }
 197
 198         *back_res = UINT32_MAX;
 199         *len_res = 1;
 200         return;
 201 }