view release on metacpan or  search on metacpan

brotli/c/enc/backward_references_hq.c  view on Meta::CPAN

    const PosData* posdata = StartPosQueueAt(queue, k);
    const size_t start = posdata->pos;
    const uint16_t inscode = GetInsertLengthCode(pos - start);
    const float start_costdiff = posdata->costdiff;
    const float base_cost = start_costdiff + (float)GetInsertExtra(inscode) +
        ZopfliCostModelGetLiteralCosts(model, 0, pos);

    /* Look for last distance matches using the distance cache from this
       starting position. */
    size_t best_len = min_len - 1;
    size_t j = 0;
    for (; j < BROTLI_NUM_DISTANCE_SHORT_CODES && best_len < max_len; ++j) {
      const size_t idx = kDistanceCacheIndex[j];
      const size_t backward =
          (size_t)(posdata->distance_cache[idx] + kDistanceCacheOffset[j]);
      size_t prev_ix = cur_ix - backward;
      size_t len = 0;
      uint8_t continuation = ringbuffer[cur_ix_masked + best_len];
      if (cur_ix_masked + best_len > ringbuffer_mask) {
        break;
      }
      if (BROTLI_PREDICT_FALSE(backward > max_distance + gap)) {
        continue;
      }
      if (backward <= max_distance) {
        if (prev_ix >= cur_ix) {
          continue;
        }

        prev_ix &= ringbuffer_mask;
        if (prev_ix + best_len > ringbuffer_mask ||
            continuation != ringbuffer[prev_ix + best_len]) {
          continue;
        }
        len = FindMatchLengthWithLimit(&ringbuffer[prev_ix],
                                       &ringbuffer[cur_ix_masked],
                                       max_len);
      } else {
        continue;
      }
      {
        const float dist_cost = base_cost +
            ZopfliCostModelGetDistanceCost(model, j);
        size_t l;
        for (l = best_len + 1; l <= len; ++l) {
          const uint16_t copycode = GetCopyLengthCode(l);
          const uint16_t cmdcode =
              CombineLengthCodes(inscode, copycode, j == 0);
          const float cost = (cmdcode < 128 ? base_cost : dist_cost) +
              (float)GetCopyExtra(copycode) +
              ZopfliCostModelGetCommandCost(model, cmdcode);
          if (cost < nodes[pos + l].u.cost) {
            UpdateZopfliNode(nodes, pos, start, l, l, backward, j + 1, cost);
            result = BROTLI_MAX(size_t, result, l);
          }
          best_len = l;
        }
      }
    }

    /* At higher iterations look only for new last distance matches, since
       looking only for new command start positions with the same distances
       does not help much. */
    if (k >= 2) continue;

    {
      /* Loop through all possible copy lengths at this position. */
      size_t len = min_len;
      for (j = 0; j < num_matches; ++j) {
        BackwardMatch match = matches[j];
        size_t dist = match.distance;
        BROTLI_BOOL is_dictionary_match =
            TO_BROTLI_BOOL(dist > max_distance + gap);
        /* We already tried all possible last distance matches, so we can use
           normal distance code here. */
        size_t dist_code = dist + BROTLI_NUM_DISTANCE_SHORT_CODES - 1;
        uint16_t dist_symbol;
        uint32_t distextra;
        uint32_t distnumextra;
        float dist_cost;
        size_t max_match_len;
        PrefixEncodeCopyDistance(
            dist_code, params->dist.num_direct_distance_codes,
            params->dist.distance_postfix_bits, &dist_symbol, &distextra);
        distnumextra = dist_symbol >> 10;
        dist_cost = base_cost + (float)distnumextra +
            ZopfliCostModelGetDistanceCost(model, dist_symbol & 0x3FF);

        /* Try all copy lengths up until the maximum copy length corresponding
           to this distance. If the distance refers to the static dictionary, or
           the maximum length is long enough, try only one maximum length. */
        max_match_len = BackwardMatchLength(&match);
        if (len < max_match_len &&
            (is_dictionary_match || max_match_len > max_zopfli_len)) {
          len = max_match_len;
        }
        for (; len <= max_match_len; ++len) {
          const size_t len_code =
              is_dictionary_match ? BackwardMatchLengthCode(&match) : len;
          const uint16_t copycode = GetCopyLengthCode(len_code);
          const uint16_t cmdcode = CombineLengthCodes(inscode, copycode, 0);
          const float cost = dist_cost + (float)GetCopyExtra(copycode) +
              ZopfliCostModelGetCommandCost(model, cmdcode);
          if (cost < nodes[pos + len].u.cost) {
            UpdateZopfliNode(nodes, pos, start, len, len_code, dist, 0, cost);
            result = BROTLI_MAX(size_t, result, len);
          }
        }
      }
    }
  }
  return result;
}

static size_t ComputeShortestPathFromNodes(size_t num_bytes,
    ZopfliNode* nodes) {
  size_t index = num_bytes;
  size_t num_commands = 0;
  while ((nodes[index].dcode_insert_length & 0x7FFFFFF) == 0 &&
      nodes[index].length == 1) --index;
  nodes[index].u.next = BROTLI_UINT32_MAX;