/src/ghostpdl/brotli/c/enc/backward_references_inc.h

Source
/* NOLINT(build/header_guard) */
/* Copyright 2013 Google Inc. All Rights Reserved.

   Distributed under MIT license.
   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
*/

/* template parameters: EXPORT_FN, FN */

static BROTLI_NOINLINE void EXPORT_FN(CreateBackwardReferences)(
    size_t num_bytes, size_t position,
    const uint8_t* ringbuffer, size_t ringbuffer_mask,
    ContextLut literal_context_lut, const BrotliEncoderParams* params,
    Hasher* hasher, int* dist_cache, size_t* last_insert_len,
    Command* commands, size_t* num_commands, size_t* num_literals) {
  HASHER()* privat = &hasher->privat.FN(_);
  /* Set maximum distance, see section 9.1. of the spec. */
  const size_t max_backward_limit = BROTLI_MAX_BACKWARD_LIMIT(params->lgwin);
  const size_t position_offset = params->stream_offset;

  const Command* const orig_commands = commands;
  size_t insert_length = *last_insert_len;
  const size_t pos_end = position + num_bytes;
  const size_t store_end = num_bytes >= FN(StoreLookahead)() ?
      position + num_bytes - FN(StoreLookahead)() + 1 : position;

  /* For speed up heuristics for random data. */
  const size_t random_heuristics_window_size =
      LiteralSpreeLengthForSparseSearch(params);
  size_t apply_random_heuristics = position + random_heuristics_window_size;
  const size_t gap = params->dictionary.compound.total_size;

  /* Minimum score to accept a backward reference. */
  const score_t kMinScore = BROTLI_SCORE_BASE + 100;
  size_t next_base64_pos = pos_end;
  /* End of a payload whose trigger was covered by a backward reference. */
  size_t base64_end = 0;

  FN(PrepareDistanceCache)(privat, dist_cache);

  if (params->base64_mode &&
      hasher->common.num_base64_regions < params->max_base64_regions) {
    next_base64_pos =
        FindNextBase64Trigger(ringbuffer, ringbuffer_mask, position, pos_end);
  }
  while (position + FN(HashTypeLength)() < pos_end) {
    size_t max_length;
    size_t max_distance;
    size_t dictionary_start;
    HasherSearchResult sr;
    int dict_id;
    uint8_t p1;
    uint8_t p2;
    if (position >= next_base64_pos) {
      size_t scan_pos;
      size_t first_equal_pos;
      size_t start_pos;
      size_t length;
      BROTLI_BOOL is_dupe;
      size_t copy_len;
      size_t dupe_dist;
      if (position > next_base64_pos) {
        /* A previous backward match jumped over the trigger position. Note
           where that payload ends, then find the next trigger. */
        size_t payload_end = next_base64_pos + kBase64TriggerLen;
        while (payload_end < pos_end &&
               IsBase64Char(ringbuffer[payload_end & ringbuffer_mask])) {
          payload_end++;
        }
        if (payload_end - (next_base64_pos + kBase64TriggerLen) >=
            params->min_base64_region_len) {
          base64_end = payload_end;
        }
        next_base64_pos = FindNextBase64Trigger(ringbuffer, ringbuffer_mask,
            BROTLI_MAX(size_t, position, payload_end), pos_end);
        if (position < next_base64_pos) {
          goto skip_base64_trigger;
        }
      }
      /* Find where it ends */
      scan_pos = position + kBase64TriggerLen;
      first_equal_pos = 0;
      while (scan_pos < pos_end) {
        uint8_t c = ringbuffer[scan_pos & ringbuffer_mask];
        if (IsBase64Char(c)) {
          if (first_equal_pos != 0) {
            scan_pos = first_equal_pos;
            break;
          }
          scan_pos++;
        } else if (c == '=') {
          if (first_equal_pos == 0) {
            first_equal_pos = scan_pos;
          }
          scan_pos++;
        } else {
          break;
        }
      }
      /* Jump directly to the end of base64 block */
      start_pos = position + kBase64TriggerLen;
      length = scan_pos - start_pos;
      /* Exclude '=' characters from the flat 6-bit entropy block */
      while (length > 0 &&
             ringbuffer[(start_pos + length - 1) & ringbuffer_mask] == '=') {
        length--;
      }
      is_dupe = BROTLI_FALSE;
      copy_len = scan_pos - position;
      dupe_dist = 0;
      if (length > 0 && hasher->common.num_base64_regions > 0) {
        size_t r = hasher->common.num_base64_regions;
        while (r > 0) {
          size_t prev_start =
              hasher->common.base64_regions[--r].start_literal_pos;
          size_t prev_length = hasher->common.base64_regions[r].length;
          size_t prev_pos;
          size_t distance;
          if (prev_length != length) {
            continue;
          }
          prev_pos = prev_start - kBase64TriggerLen;
          distance = position - prev_pos;
          if (distance == 0 || distance > max_backward_limit) {
            continue;
          }
          if (CompareRingbuffer(ringbuffer, ringbuffer_mask, prev_pos, position,
                                copy_len)) {
            is_dupe = BROTLI_TRUE;
            dupe_dist = distance;
            break;
          }
        }
      }
      if (is_dupe) {
        size_t dictionary_start =
            BROTLI_MIN(size_t, position + position_offset, max_backward_limit);
        size_t distance_code =
            ComputeDistanceCode(dupe_dist, dictionary_start + gap, dist_cache);
        if ((dupe_dist <= (dictionary_start + gap)) && distance_code > 0) {
          dist_cache[3] = dist_cache[2];
          dist_cache[2] = dist_cache[1];
          dist_cache[1] = dist_cache[0];
          dist_cache[0] = (int)dupe_dist;
          FN(PrepareDistanceCache)(privat, dist_cache);
        }
        InitCommand(commands++, &params->dist, insert_length, copy_len, 0,
                    distance_code);
        *num_literals += insert_length;
        insert_length = 0;
        position = scan_pos;
        apply_random_heuristics =
            position + 2 * copy_len + random_heuristics_window_size;
        if (hasher->common.num_base64_regions < params->max_base64_regions) {
          next_base64_pos = FindNextBase64Trigger(ringbuffer, ringbuffer_mask,
                                                  position, pos_end);
        } else {
          next_base64_pos = pos_end;
        }
        continue;
      }
      if (length >= params->min_base64_region_len && length > 0) {
        hasher->common.base64_regions[hasher->common.num_base64_regions]
            .start_literal_pos = start_pos;
        hasher->common.base64_regions[hasher->common.num_base64_regions]
            .length = length;
        hasher->common.num_base64_regions++;
        insert_length += (scan_pos - position);
        position = scan_pos;
        if (hasher->common.num_base64_regions < params->max_base64_regions) {
          next_base64_pos = FindNextBase64Trigger(ringbuffer, ringbuffer_mask,
                                                  position, pos_end);
        } else {
          next_base64_pos = pos_end;
        }
        continue;
      } else {
        next_base64_pos = FindNextBase64Trigger(ringbuffer, ringbuffer_mask,
                                                position + 1, pos_end);
        goto skip_base64_trigger;
      }
    }
  skip_base64_trigger:;
    if (position < base64_end && position > apply_random_heuristics) {
      /* No backward reference for a while inside the payload: the rest of it
         is high-entropy (e.g. image data). Emit it as literals without
         searching. */
      insert_length += base64_end - position;
      position = base64_end;
      continue;
    }
    max_length = pos_end - position;
    max_distance = BROTLI_MIN(size_t, position, max_backward_limit);
    dictionary_start = BROTLI_MIN(size_t,
        position + position_offset, max_backward_limit);
    dict_id = 0;
    p1 = 0;
    p2 = 0;
    if (params->dictionary.contextual.context_based) {
      p1 = position >= 1 ?
          ringbuffer[(size_t)(position - 1) & ringbuffer_mask] : 0;
      p2 = position >= 2 ?
          ringbuffer[(size_t)(position - 2) & ringbuffer_mask] : 0;
      dict_id = params->dictionary.contextual.context_map[
          BROTLI_CONTEXT(p1, p2, literal_context_lut)];
    }
    sr.len = 0;
    sr.len_code_delta = 0;
    sr.distance = 0;
    sr.score = kMinScore;
    FN(FindLongestMatch)(privat, params->dictionary.contextual.dict[dict_id],
        ringbuffer, ringbuffer_mask, dist_cache, position, max_length,
        max_distance, dictionary_start + gap, params->dist.max_distance, &sr);
    if (ENABLE_COMPOUND_DICTIONARY && position >= base64_end) {
      LookupCompoundDictionaryMatch(&params->dictionary.compound, ringbuffer,
          ringbuffer_mask, dist_cache, position, max_length,
          dictionary_start, params->dist.max_distance, &sr);
    }
    if (sr.score > kMinScore) {
      /* Found a match. Let's look for something even better ahead. */
      int delayed_backward_references_in_row = 0;
      --max_length;
      for (;; --max_length) {
        const score_t cost_diff_lazy = 175;
        HasherSearchResult sr2;
        sr2.len = params->quality < MIN_QUALITY_FOR_EXTENSIVE_REFERENCE_SEARCH ?
            BROTLI_MIN(size_t, sr.len - 1, max_length) : 0;
        sr2.len_code_delta = 0;
        sr2.distance = 0;
        sr2.score = kMinScore;
        max_distance = BROTLI_MIN(size_t, position + 1, max_backward_limit);
        dictionary_start = BROTLI_MIN(size_t,
            position + 1 + position_offset, max_backward_limit);
        if (params->dictionary.contextual.context_based) {
          p2 = p1;
          p1 = ringbuffer[position & ringbuffer_mask];
          dict_id = params->dictionary.contextual.context_map[
              BROTLI_CONTEXT(p1, p2, literal_context_lut)];
        }
        FN(FindLongestMatch)(privat,
            params->dictionary.contextual.dict[dict_id],
            ringbuffer, ringbuffer_mask, dist_cache, position + 1, max_length,
            max_distance, dictionary_start + gap, params->dist.max_distance,
            &sr2);
        if (ENABLE_COMPOUND_DICTIONARY && position + 1 >= base64_end) {
          LookupCompoundDictionaryMatch(
              &params->dictionary.compound, ringbuffer,
              ringbuffer_mask, dist_cache, position + 1, max_length,
              dictionary_start, params->dist.max_distance, &sr2);
        }
        if (sr2.score >= sr.score + cost_diff_lazy) {
          /* Ok, let's just write one byte for now and start a match from the
             next byte. */
          ++position;
          ++insert_length;
          sr = sr2;
          if (++delayed_backward_references_in_row < 4 &&
              position + FN(HashTypeLength)() < pos_end) {
            continue;
          }
        }
        break;
      }
      apply_random_heuristics =
          position + 2 * sr.len + random_heuristics_window_size;
      dictionary_start = BROTLI_MIN(size_t,
          position + position_offset, max_backward_limit);
      {
        /* The first 16 codes are special short-codes,
           and the minimum offset is 1. */
        size_t distance_code = ComputeDistanceCode(
            sr.distance, dictionary_start + gap, dist_cache);
        if ((sr.distance <= (dictionary_start + gap)) && distance_code > 0) {
          dist_cache[3] = dist_cache[2];
          dist_cache[2] = dist_cache[1];
          dist_cache[1] = dist_cache[0];
          dist_cache[0] = (int)sr.distance;
          FN(PrepareDistanceCache)(privat, dist_cache);
        }
        InitCommand(commands++, &params->dist, insert_length,
            sr.len, sr.len_code_delta, distance_code);
      }
      *num_literals += insert_length;
      insert_length = 0;
      /* Put the hash keys into the table, if there are enough bytes left.
         Depending on the hasher implementation, it can push all positions
         in the given range or only a subset of them.
         Avoid hash poisoning with RLE data. */
      {
        size_t range_start = position + 2;
        size_t range_end = BROTLI_MIN(size_t, position + sr.len, store_end);
        if (sr.distance < (sr.len >> 2)) {
          range_start = BROTLI_MIN(size_t, range_end, BROTLI_MAX(size_t,
              range_start, position + sr.len - (sr.distance << 2)));
        }
        FN(StoreRange)(privat, ringbuffer, ringbuffer_mask, range_start,
                       range_end);
      }
      position += sr.len;
    } else {
      ++insert_length;
      ++position;
      /* If we have not seen matches for a long time, we can skip some
         match lookups. Unsuccessful match lookups are very very expensive
         and this kind of a heuristic speeds up compression quite
         a lot. */
      if (position > apply_random_heuristics) {
        /* Going through uncompressible data, jump. */
        if (position >
            apply_random_heuristics + 4 * random_heuristics_window_size) {
          /* It is quite a long time since we saw a copy, so we assume
             that this data is not compressible, and store hashes less
             often. Hashes of non compressible data are less likely to
             turn out to be useful in the future, too, so we store less of
             them to not to flood out the hash table of good compressible
             data. */
          const size_t kMargin =
              BROTLI_MAX(size_t, FN(StoreLookahead)() - 1, 4);
          size_t pos_jump =
              BROTLI_MIN(size_t, position + 16, pos_end - kMargin);
          for (; position < pos_jump; position += 4) {
            FN(Store)(privat, ringbuffer, ringbuffer_mask, position);
            insert_length += 4;
          }
        } else {
          const size_t kMargin =
              BROTLI_MAX(size_t, FN(StoreLookahead)() - 1, 2);
          size_t pos_jump =
              BROTLI_MIN(size_t, position + 8, pos_end - kMargin);
          for (; position < pos_jump; position += 2) {
            FN(Store)(privat, ringbuffer, ringbuffer_mask, position);
            insert_length += 2;
          }
        }
      }
    }
  }
  insert_length += pos_end - position;
  *last_insert_len = insert_length;
  *num_commands += (size_t)(commands - orig_commands);
}

Coverage Report

Created: 2026-10-28 08:05

Line	Count	Source
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: EXPORT_FN, FN */
9
10		static BROTLI_NOINLINE void EXPORT_FN(CreateBackwardReferences)(
11		size_t num_bytes, size_t position,
12		const uint8_t* ringbuffer, size_t ringbuffer_mask,
13		ContextLut literal_context_lut, const BrotliEncoderParams* params,
14		Hasher* hasher, int* dist_cache, size_t* last_insert_len,
15	0	Command* commands, size_t* num_commands, size_t* num_literals) {
16	0	HASHER()* privat = &hasher->privat.FN(_);
17		/* Set maximum distance, see section 9.1. of the spec. */
18	0	const size_t max_backward_limit = BROTLI_MAX_BACKWARD_LIMIT(params->lgwin);
19	0	const size_t position_offset = params->stream_offset;
20
21	0	const Command* const orig_commands = commands;
22	0	size_t insert_length = *last_insert_len;
23	0	const size_t pos_end = position + num_bytes;
24	0	const size_t store_end = num_bytes >= FN(StoreLookahead)() ?
25	0	position + num_bytes - FN(StoreLookahead)() + 1 : position;
26
27		/* For speed up heuristics for random data. */
28	0	const size_t random_heuristics_window_size =
29	0	LiteralSpreeLengthForSparseSearch(params);
30	0	size_t apply_random_heuristics = position + random_heuristics_window_size;
31	0	const size_t gap = params->dictionary.compound.total_size;
32
33		/* Minimum score to accept a backward reference. */
34	0	const score_t kMinScore = BROTLI_SCORE_BASE + 100;
35	0	size_t next_base64_pos = pos_end;
36		/* End of a payload whose trigger was covered by a backward reference. */
37	0	size_t base64_end = 0;
38
39	0	FN(PrepareDistanceCache)(privat, dist_cache);
40
41	0	if (params->base64_mode &&
42	0	hasher->common.num_base64_regions < params->max_base64_regions) {
43	0	next_base64_pos =
44	0	FindNextBase64Trigger(ringbuffer, ringbuffer_mask, position, pos_end);
45	0	}
46	0	while (position + FN(HashTypeLength)() < pos_end) {
47	0	size_t max_length;
48	0	size_t max_distance;
49	0	size_t dictionary_start;
50	0	HasherSearchResult sr;
51	0	int dict_id;
52	0	uint8_t p1;
53	0	uint8_t p2;
54	0	if (position >= next_base64_pos) {
55	0	size_t scan_pos;
56	0	size_t first_equal_pos;
57	0	size_t start_pos;
58	0	size_t length;
59	0	BROTLI_BOOL is_dupe;
60	0	size_t copy_len;
61	0	size_t dupe_dist;
62	0	if (position > next_base64_pos) {
63		/* A previous backward match jumped over the trigger position. Note
64		where that payload ends, then find the next trigger. */
65	0	size_t payload_end = next_base64_pos + kBase64TriggerLen;
66	0	while (payload_end < pos_end &&
67	0	IsBase64Char(ringbuffer[payload_end & ringbuffer_mask])) {
68	0	payload_end++;
69	0	}
70	0	if (payload_end - (next_base64_pos + kBase64TriggerLen) >=
71	0	params->min_base64_region_len) {
72	0	base64_end = payload_end;
73	0	}
74	0	next_base64_pos = FindNextBase64Trigger(ringbuffer, ringbuffer_mask,
75	0	BROTLI_MAX(size_t, position, payload_end), pos_end);
76	0	if (position < next_base64_pos) {
77	0	goto skip_base64_trigger;
78	0	}
79	0	}
80		/* Find where it ends */
81	0	scan_pos = position + kBase64TriggerLen;
82	0	first_equal_pos = 0;
83	0	while (scan_pos < pos_end) {
84	0	uint8_t c = ringbuffer[scan_pos & ringbuffer_mask];
85	0	if (IsBase64Char(c)) {
86	0	if (first_equal_pos != 0) {
87	0	scan_pos = first_equal_pos;
88	0	break;
89	0	}
90	0	scan_pos++;
91	0	} else if (c == '=') {
92	0	if (first_equal_pos == 0) {
93	0	first_equal_pos = scan_pos;
94	0	}
95	0	scan_pos++;
96	0	} else {
97	0	break;
98	0	}
99	0	}
100		/* Jump directly to the end of base64 block */
101	0	start_pos = position + kBase64TriggerLen;
102	0	length = scan_pos - start_pos;
103		/* Exclude '=' characters from the flat 6-bit entropy block */
104	0	while (length > 0 &&
105	0	ringbuffer[(start_pos + length - 1) & ringbuffer_mask] == '=') {
106	0	length--;
107	0	}
108	0	is_dupe = BROTLI_FALSE;
109	0	copy_len = scan_pos - position;
110	0	dupe_dist = 0;
111	0	if (length > 0 && hasher->common.num_base64_regions > 0) {
112	0	size_t r = hasher->common.num_base64_regions;
113	0	while (r > 0) {
114	0	size_t prev_start =
115	0	hasher->common.base64_regions[--r].start_literal_pos;
116	0	size_t prev_length = hasher->common.base64_regions[r].length;
117	0	size_t prev_pos;
118	0	size_t distance;
119	0	if (prev_length != length) {
120	0	continue;
121	0	}
122	0	prev_pos = prev_start - kBase64TriggerLen;
123	0	distance = position - prev_pos;
124	0	if (distance == 0 \|\| distance > max_backward_limit) {
125	0	continue;
126	0	}
127	0	if (CompareRingbuffer(ringbuffer, ringbuffer_mask, prev_pos, position,
128	0	copy_len)) {
129	0	is_dupe = BROTLI_TRUE;
130	0	dupe_dist = distance;
131	0	break;
132	0	}
133	0	}
134	0	}
135	0	if (is_dupe) {
136	0	size_t dictionary_start =
137	0	BROTLI_MIN(size_t, position + position_offset, max_backward_limit);
138	0	size_t distance_code =
139	0	ComputeDistanceCode(dupe_dist, dictionary_start + gap, dist_cache);
140	0	if ((dupe_dist <= (dictionary_start + gap)) && distance_code > 0) {
141	0	dist_cache[3] = dist_cache[2];
142	0	dist_cache[2] = dist_cache[1];
143	0	dist_cache[1] = dist_cache[0];
144	0	dist_cache[0] = (int)dupe_dist;
145	0	FN(PrepareDistanceCache)(privat, dist_cache);
146	0	}
147	0	InitCommand(commands++, &params->dist, insert_length, copy_len, 0,
148	0	distance_code);
149	0	*num_literals += insert_length;
150	0	insert_length = 0;
151	0	position = scan_pos;
152	0	apply_random_heuristics =
153	0	position + 2 * copy_len + random_heuristics_window_size;
154	0	if (hasher->common.num_base64_regions < params->max_base64_regions) {
155	0	next_base64_pos = FindNextBase64Trigger(ringbuffer, ringbuffer_mask,
156	0	position, pos_end);
157	0	} else {
158	0	next_base64_pos = pos_end;
159	0	}
160	0	continue;
161	0	}
162	0	if (length >= params->min_base64_region_len && length > 0) {
163	0	hasher->common.base64_regions[hasher->common.num_base64_regions]
164	0	.start_literal_pos = start_pos;
165	0	hasher->common.base64_regions[hasher->common.num_base64_regions]
166	0	.length = length;
167	0	hasher->common.num_base64_regions++;
168	0	insert_length += (scan_pos - position);
169	0	position = scan_pos;
170	0	if (hasher->common.num_base64_regions < params->max_base64_regions) {
171	0	next_base64_pos = FindNextBase64Trigger(ringbuffer, ringbuffer_mask,
172	0	position, pos_end);
173	0	} else {
174	0	next_base64_pos = pos_end;
175	0	}
176	0	continue;
177	0	} else {
178	0	next_base64_pos = FindNextBase64Trigger(ringbuffer, ringbuffer_mask,
179	0	position + 1, pos_end);
180	0	goto skip_base64_trigger;
181	0	}
182	0	}
183	0	skip_base64_trigger:;
184	0	if (position < base64_end && position > apply_random_heuristics) {
185		/* No backward reference for a while inside the payload: the rest of it
186		is high-entropy (e.g. image data). Emit it as literals without
187		searching. */
188	0	insert_length += base64_end - position;
189	0	position = base64_end;
190	0	continue;
191	0	}
192	0	max_length = pos_end - position;
193	0	max_distance = BROTLI_MIN(size_t, position, max_backward_limit);
194	0	dictionary_start = BROTLI_MIN(size_t,
195	0	position + position_offset, max_backward_limit);
196	0	dict_id = 0;
197	0	p1 = 0;
198	0	p2 = 0;
199	0	if (params->dictionary.contextual.context_based) {
200	0	p1 = position >= 1 ?
201	0	ringbuffer[(size_t)(position - 1) & ringbuffer_mask] : 0;
202	0	p2 = position >= 2 ?
203	0	ringbuffer[(size_t)(position - 2) & ringbuffer_mask] : 0;
204	0	dict_id = params->dictionary.contextual.context_map[
205	0	BROTLI_CONTEXT(p1, p2, literal_context_lut)];
206	0	}
207	0	sr.len = 0;
208	0	sr.len_code_delta = 0;
209	0	sr.distance = 0;
210	0	sr.score = kMinScore;
211	0	FN(FindLongestMatch)(privat, params->dictionary.contextual.dict[dict_id],
212	0	ringbuffer, ringbuffer_mask, dist_cache, position, max_length,
213	0	max_distance, dictionary_start + gap, params->dist.max_distance, &sr);
214	0	if (ENABLE_COMPOUND_DICTIONARY && position >= base64_end) {
215	0	LookupCompoundDictionaryMatch(&params->dictionary.compound, ringbuffer,
216	0	ringbuffer_mask, dist_cache, position, max_length,
217	0	dictionary_start, params->dist.max_distance, &sr);
218	0	}
219	0	if (sr.score > kMinScore) {
220		/* Found a match. Let's look for something even better ahead. */
221	0	int delayed_backward_references_in_row = 0;
222	0	--max_length;
223	0	for (;; --max_length) {
224	0	const score_t cost_diff_lazy = 175;
225	0	HasherSearchResult sr2;
226	0	sr2.len = params->quality < MIN_QUALITY_FOR_EXTENSIVE_REFERENCE_SEARCH ?
227	0	BROTLI_MIN(size_t, sr.len - 1, max_length) : 0;
228	0	sr2.len_code_delta = 0;
229	0	sr2.distance = 0;
230	0	sr2.score = kMinScore;
231	0	max_distance = BROTLI_MIN(size_t, position + 1, max_backward_limit);
232	0	dictionary_start = BROTLI_MIN(size_t,
233	0	position + 1 + position_offset, max_backward_limit);
234	0	if (params->dictionary.contextual.context_based) {
235	0	p2 = p1;
236	0	p1 = ringbuffer[position & ringbuffer_mask];
237	0	dict_id = params->dictionary.contextual.context_map[
238	0	BROTLI_CONTEXT(p1, p2, literal_context_lut)];
239	0	}
240	0	FN(FindLongestMatch)(privat,
241	0	params->dictionary.contextual.dict[dict_id],
242	0	ringbuffer, ringbuffer_mask, dist_cache, position + 1, max_length,
243	0	max_distance, dictionary_start + gap, params->dist.max_distance,
244	0	&sr2);
245	0	if (ENABLE_COMPOUND_DICTIONARY && position + 1 >= base64_end) {
246	0	LookupCompoundDictionaryMatch(
247	0	&params->dictionary.compound, ringbuffer,
248	0	ringbuffer_mask, dist_cache, position + 1, max_length,
249	0	dictionary_start, params->dist.max_distance, &sr2);
250	0	}
251	0	if (sr2.score >= sr.score + cost_diff_lazy) {
252		/* Ok, let's just write one byte for now and start a match from the
253		next byte. */
254	0	++position;
255	0	++insert_length;
256	0	sr = sr2;
257	0	if (++delayed_backward_references_in_row < 4 &&
258	0	position + FN(HashTypeLength)() < pos_end) {
259	0	continue;
260	0	}
261	0	}
262	0	break;
263	0	}
264	0	apply_random_heuristics =
265	0	position + 2 * sr.len + random_heuristics_window_size;
266	0	dictionary_start = BROTLI_MIN(size_t,
267	0	position + position_offset, max_backward_limit);
268	0	{
269		/* The first 16 codes are special short-codes,
270		and the minimum offset is 1. */
271	0	size_t distance_code = ComputeDistanceCode(
272	0	sr.distance, dictionary_start + gap, dist_cache);
273	0	if ((sr.distance <= (dictionary_start + gap)) && distance_code > 0) {
274	0	dist_cache[3] = dist_cache[2];
275	0	dist_cache[2] = dist_cache[1];
276	0	dist_cache[1] = dist_cache[0];
277	0	dist_cache[0] = (int)sr.distance;
278	0	FN(PrepareDistanceCache)(privat, dist_cache);
279	0	}
280	0	InitCommand(commands++, &params->dist, insert_length,
281	0	sr.len, sr.len_code_delta, distance_code);
282	0	}
283	0	*num_literals += insert_length;
284	0	insert_length = 0;
285		/* Put the hash keys into the table, if there are enough bytes left.
286		Depending on the hasher implementation, it can push all positions
287		in the given range or only a subset of them.
288		Avoid hash poisoning with RLE data. */
289	0	{
290	0	size_t range_start = position + 2;
291	0	size_t range_end = BROTLI_MIN(size_t, position + sr.len, store_end);
292	0	if (sr.distance < (sr.len >> 2)) {
293	0	range_start = BROTLI_MIN(size_t, range_end, BROTLI_MAX(size_t,
294	0	range_start, position + sr.len - (sr.distance << 2)));
295	0	}
296	0	FN(StoreRange)(privat, ringbuffer, ringbuffer_mask, range_start,
297	0	range_end);
298	0	}
299	0	position += sr.len;
300	0	} else {
301	0	++insert_length;
302	0	++position;
303		/* If we have not seen matches for a long time, we can skip some
304		match lookups. Unsuccessful match lookups are very very expensive
305		and this kind of a heuristic speeds up compression quite
306		a lot. */
307	0	if (position > apply_random_heuristics) {
308		/* Going through uncompressible data, jump. */
309	0	if (position >
310	0	apply_random_heuristics + 4 * random_heuristics_window_size) {
311		/* It is quite a long time since we saw a copy, so we assume
312		that this data is not compressible, and store hashes less
313		often. Hashes of non compressible data are less likely to
314		turn out to be useful in the future, too, so we store less of
315		them to not to flood out the hash table of good compressible
316		data. */
317	0	const size_t kMargin =
318	0	BROTLI_MAX(size_t, FN(StoreLookahead)() - 1, 4);
319	0	size_t pos_jump =
320	0	BROTLI_MIN(size_t, position + 16, pos_end - kMargin);
321	0	for (; position < pos_jump; position += 4) {
322	0	FN(Store)(privat, ringbuffer, ringbuffer_mask, position);
323	0	insert_length += 4;
324	0	}
325	0	} else {
326	0	const size_t kMargin =
327	0	BROTLI_MAX(size_t, FN(StoreLookahead)() - 1, 2);
328	0	size_t pos_jump =
329	0	BROTLI_MIN(size_t, position + 8, pos_end - kMargin);
330	0	for (; position < pos_jump; position += 2) {
331	0	FN(Store)(privat, ringbuffer, ringbuffer_mask, position);
332	0	insert_length += 2;
333	0	}
334	0	}
335	0	}
336	0	}
337	0	}
338	0	insert_length += pos_end - position;
339	0	*last_insert_len = insert_length;
340	0	*num_commands += (size_t)(commands - orig_commands);
341	0	} Unexecuted instantiation: backward_references.c:CreateBackwardReferencesDH3 Unexecuted instantiation: backward_references.c:CreateBackwardReferencesDH4 Unexecuted instantiation: backward_references.c:CreateBackwardReferencesDH5 Unexecuted instantiation: backward_references.c:CreateBackwardReferencesDH6 Unexecuted instantiation: backward_references.c:CreateBackwardReferencesDH58 Unexecuted instantiation: backward_references.c:CreateBackwardReferencesDH68 Unexecuted instantiation: backward_references.c:CreateBackwardReferencesDH40 Unexecuted instantiation: backward_references.c:CreateBackwardReferencesDH41 Unexecuted instantiation: backward_references.c:CreateBackwardReferencesDH42 Unexecuted instantiation: backward_references.c:CreateBackwardReferencesDH55 Unexecuted instantiation: backward_references.c:CreateBackwardReferencesDH65 Unexecuted instantiation: backward_references.c:CreateBackwardReferencesNH2 Unexecuted instantiation: backward_references.c:CreateBackwardReferencesNH3 Unexecuted instantiation: backward_references.c:CreateBackwardReferencesNH4 Unexecuted instantiation: backward_references.c:CreateBackwardReferencesNH5 Unexecuted instantiation: backward_references.c:CreateBackwardReferencesNH6 Unexecuted instantiation: backward_references.c:CreateBackwardReferencesNH40 Unexecuted instantiation: backward_references.c:CreateBackwardReferencesNH41 Unexecuted instantiation: backward_references.c:CreateBackwardReferencesNH42 Unexecuted instantiation: backward_references.c:CreateBackwardReferencesNH54 Unexecuted instantiation: backward_references.c:CreateBackwardReferencesNH58 Unexecuted instantiation: backward_references.c:CreateBackwardReferencesNH68 Unexecuted instantiation: backward_references.c:CreateBackwardReferencesNH35 Unexecuted instantiation: backward_references.c:CreateBackwardReferencesNH55 Unexecuted instantiation: backward_references.c:CreateBackwardReferencesNH65