BaseTools/Source/C/BrotliCompress/enc/backward_references_inc.h

   1 /* NOLINT(build/header_guard) */
   2 /* Copyright 2013 Google Inc. All Rights Reserved.
   3
   4    Distributed under MIT license.
   5    See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
   6 */
   7
   8 /* template parameters: FN */
   9
  10 #define Hasher HASHER()
  11
  12 static BROTLI_NOINLINE void FN(CreateBackwardReferences)(
  13     MemoryManager* m, size_t num_bytes, size_t position, BROTLI_BOOL is_last,
  14     const uint8_t* ringbuffer, size_t ringbuffer_mask,
  15     const BrotliEncoderParams* params, Hasher* hasher, int* dist_cache,
  16     size_t* last_insert_len, Command* commands, size_t* num_commands,
  17     size_t* num_literals) {
  18   /* Set maximum distance, see section 9.1. of the spec. */
  19   const size_t max_backward_limit = MaxBackwardLimit(params->lgwin);
  20
  21   const Command* const orig_commands = commands;
  22   size_t insert_length = *last_insert_len;
  23   const size_t pos_end = position + num_bytes;
  24   const size_t store_end = num_bytes >= FN(StoreLookahead)() ?
  25       position + num_bytes - FN(StoreLookahead)() + 1 : position;
  26
  27   /* For speed up heuristics for random data. */
  28   const size_t random_heuristics_window_size =
  29       LiteralSpreeLengthForSparseSearch(params);
  30   size_t apply_random_heuristics = position + random_heuristics_window_size;
  31
  32   /* Minimum score to accept a backward reference. */
  33   const score_t kMinScore = BROTLI_SCORE_BASE + 400;
  34
  35   FN(Init)(m, hasher, ringbuffer, params, position, num_bytes, is_last);
  36   if (BROTLI_IS_OOM(m)) return;
  37   FN(StitchToPreviousBlock)(hasher, num_bytes, position,
  38                             ringbuffer, ringbuffer_mask);
  39
  40   while (position + FN(HashTypeLength)() < pos_end) {
  41     size_t max_length = pos_end - position;
  42     size_t max_distance = BROTLI_MIN(size_t, position, max_backward_limit);
  43     HasherSearchResult sr;
  44     sr.len = 0;
  45     sr.len_x_code = 0;
  46     sr.distance = 0;
  47     sr.score = kMinScore;
  48     if (FN(FindLongestMatch)(hasher, ringbuffer, ringbuffer_mask, dist_cache,
  49                              position, max_length, max_distance, &sr)) {
  50       /* Found a match. Let's look for something even better ahead. */
  51       int delayed_backward_references_in_row = 0;
  52       --max_length;
  53       for (;; --max_length) {
  54         const score_t cost_diff_lazy = 700;
  55         BROTLI_BOOL is_match_found;
  56         HasherSearchResult sr2;
  57         sr2.len = params->quality < MIN_QUALITY_FOR_EXTENSIVE_REFERENCE_SEARCH ?
  58             BROTLI_MIN(size_t, sr.len - 1, max_length) : 0;
  59         sr2.len_x_code = 0;
  60         sr2.distance = 0;
  61         sr2.score = kMinScore;
  62         max_distance = BROTLI_MIN(size_t, position + 1, max_backward_limit);
  63         is_match_found = FN(FindLongestMatch)(hasher, ringbuffer,
  64             ringbuffer_mask, dist_cache, position + 1, max_length, max_distance,
  65             &sr2);
  66         if (is_match_found && sr2.score >= sr.score + cost_diff_lazy) {
  67           /* Ok, let's just write one byte for now and start a match from the
  68              next byte. */
  69           ++position;
  70           ++insert_length;
  71           sr = sr2;
  72           if (++delayed_backward_references_in_row < 4 &&
  73               position + FN(HashTypeLength)() < pos_end) {
  74             continue;
  75           }
  76         }
  77         break;
  78       }
  79       apply_random_heuristics =
  80           position + 2 * sr.len + random_heuristics_window_size;
  81       max_distance = BROTLI_MIN(size_t, position, max_backward_limit);
  82       {
  83         /* The first 16 codes are special shortcodes,
  84            and the minimum offset is 1. */
  85         size_t distance_code =
  86             ComputeDistanceCode(sr.distance, max_distance, dist_cache);
  87         if (sr.distance <= max_distance && distance_code > 0) {
  88           dist_cache[3] = dist_cache[2];
  89           dist_cache[2] = dist_cache[1];
  90           dist_cache[1] = dist_cache[0];
  91           dist_cache[0] = (int)sr.distance;
  92         }
  93         InitCommand(commands++, insert_length, sr.len, sr.len ^ sr.len_x_code,
  94             distance_code);
  95       }
  96       *num_literals += insert_length;
  97       insert_length = 0;
  98       /* Put the hash keys into the table, if there are enough bytes left.
  99          Depending on the hasher implementation, it can push all positions
 100          in the given range or only a subset of them. */
 101       FN(StoreRange)(hasher, ringbuffer, ringbuffer_mask, position + 2,
 102                      BROTLI_MIN(size_t, position + sr.len, store_end));
 103       position += sr.len;
 104     } else {
 105       ++insert_length;
 106       ++position;
 107       /* If we have not seen matches for a long time, we can skip some
 108          match lookups. Unsuccessful match lookups are very very expensive
 109          and this kind of a heuristic speeds up compression quite
 110          a lot. */
 111       if (position > apply_random_heuristics) {
 112         /* Going through uncompressible data, jump. */
 113         if (position >
 114             apply_random_heuristics + 4 * random_heuristics_window_size) {
 115           /* It is quite a long time since we saw a copy, so we assume
 116              that this data is not compressible, and store hashes less
 117              often. Hashes of non compressible data are less likely to
 118              turn out to be useful in the future, too, so we store less of
 119              them to not to flood out the hash table of good compressible
 120              data. */
 121           const size_t kMargin =
 122               BROTLI_MAX(size_t, FN(StoreLookahead)() - 1, 4);
 123           size_t pos_jump =
 124               BROTLI_MIN(size_t, position + 16, pos_end - kMargin);
 125           for (; position < pos_jump; position += 4) {
 126             FN(Store)(hasher, ringbuffer, ringbuffer_mask, position);
 127             insert_length += 4;
 128           }
 129         } else {
 130           const size_t kMargin =
 131               BROTLI_MAX(size_t, FN(StoreLookahead)() - 1, 2);
 132           size_t pos_jump =
 133               BROTLI_MIN(size_t, position + 8, pos_end - kMargin);
 134           for (; position < pos_jump; position += 2) {
 135             FN(Store)(hasher, ringbuffer, ringbuffer_mask, position);
 136             insert_length += 2;
 137           }
 138         }
 139       }
 140     }
 141   }
 142   insert_length += pos_end - position;
 143   *last_insert_len = insert_length;
 144   *num_commands += (size_t)(commands - orig_commands);
 145 }
 146
 147 #undef Hasher