1 /* Copyright 2013 Google Inc. All Rights Reserved.
2
3 Distributed under MIT license.
4 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
5 */
6
7 #include "static_dict.h"
8
9 #include "../common/dictionary.h"
10 #include "../common/platform.h"
11 #include "../common/transform.h"
12 #include "encoder_dict.h"
13 #include "find_match_length.h"
14
15 #if defined(__cplusplus) || defined(c_plusplus)
16 extern "C" {
17 #endif
18
Hash(const uint8_t * data)19 static BROTLI_INLINE uint32_t Hash(const uint8_t* data) {
20 uint32_t h = BROTLI_UNALIGNED_LOAD32LE(data) * kDictHashMul32;
21 /* The higher bits contain more mixture from the multiplication,
22 so we take our results from there. */
23 return h >> (32 - kDictNumBits);
24 }
25
AddMatch(size_t distance,size_t len,size_t len_code,uint32_t * matches)26 static BROTLI_INLINE void AddMatch(size_t distance, size_t len, size_t len_code,
27 uint32_t* matches) {
28 uint32_t match = (uint32_t)((distance << 5) + len_code);
29 matches[len] = BROTLI_MIN(uint32_t, matches[len], match);
30 }
31
DictMatchLength(const BrotliDictionary * dictionary,const uint8_t * data,size_t id,size_t len,size_t maxlen)32 static BROTLI_INLINE size_t DictMatchLength(const BrotliDictionary* dictionary,
33 const uint8_t* data,
34 size_t id,
35 size_t len,
36 size_t maxlen) {
37 const size_t offset = dictionary->offsets_by_length[len] + len * id;
38 return FindMatchLengthWithLimit(&dictionary->data[offset], data,
39 BROTLI_MIN(size_t, len, maxlen));
40 }
41
IsMatch(const BrotliDictionary * dictionary,DictWord w,const uint8_t * data,size_t max_length)42 static BROTLI_INLINE BROTLI_BOOL IsMatch(const BrotliDictionary* dictionary,
43 DictWord w, const uint8_t* data, size_t max_length) {
44 if (w.len > max_length) {
45 return BROTLI_FALSE;
46 } else {
47 const size_t offset = dictionary->offsets_by_length[w.len] +
48 (size_t)w.len * (size_t)w.idx;
49 const uint8_t* dict = &dictionary->data[offset];
50 if (w.transform == 0) {
51 /* Match against base dictionary word. */
52 return
53 TO_BROTLI_BOOL(FindMatchLengthWithLimit(dict, data, w.len) == w.len);
54 } else if (w.transform == 10) {
55 /* Match against uppercase first transform.
56 Note that there are only ASCII uppercase words in the lookup table. */
57 return TO_BROTLI_BOOL(dict[0] >= 'a' && dict[0] <= 'z' &&
58 (dict[0] ^ 32) == data[0] &&
59 FindMatchLengthWithLimit(&dict[1], &data[1], w.len - 1u) ==
60 w.len - 1u);
61 } else {
62 /* Match against uppercase all transform.
63 Note that there are only ASCII uppercase words in the lookup table. */
64 size_t i;
65 for (i = 0; i < w.len; ++i) {
66 if (dict[i] >= 'a' && dict[i] <= 'z') {
67 if ((dict[i] ^ 32) != data[i]) return BROTLI_FALSE;
68 } else {
69 if (dict[i] != data[i]) return BROTLI_FALSE;
70 }
71 }
72 return BROTLI_TRUE;
73 }
74 }
75 }
76
77 /* Finds matches for a single static dictionary */
BrotliFindAllStaticDictionaryMatchesFor(const BrotliEncoderDictionary * dictionary,const uint8_t * data,size_t min_length,size_t max_length,uint32_t * matches)78 static BROTLI_BOOL BrotliFindAllStaticDictionaryMatchesFor(
79 const BrotliEncoderDictionary* dictionary, const uint8_t* data,
80 size_t min_length, size_t max_length, uint32_t* matches) {
81 BROTLI_BOOL has_found_match = BROTLI_FALSE;
82 if (dictionary->has_words_heavy) {
83 const BrotliTrieNode* node = &dictionary->trie.root;
84 size_t l = 0;
85 while (node && l < max_length) {
86 uint8_t c;
87 if (l >= min_length && node->len_) {
88 AddMatch(node->idx_, l, node->len_, matches);
89 has_found_match = BROTLI_TRUE;
90 }
91 c = data[l++];
92 node = BrotliTrieSub(&dictionary->trie, node, c);
93 }
94 return has_found_match;
95 }
96 {
97 size_t offset = dictionary->buckets[Hash(data)];
98 BROTLI_BOOL end = !offset;
99 while (!end) {
100 DictWord w = dictionary->dict_words[offset++];
101 const size_t l = w.len & 0x1F;
102 const size_t n = (size_t)1 << dictionary->words->size_bits_by_length[l];
103 const size_t id = w.idx;
104 end = !!(w.len & 0x80);
105 w.len = (uint8_t)l;
106 if (w.transform == 0) {
107 const size_t matchlen =
108 DictMatchLength(dictionary->words, data, id, l, max_length);
109 const uint8_t* s;
110 size_t minlen;
111 size_t maxlen;
112 size_t len;
113 /* Transform "" + BROTLI_TRANSFORM_IDENTITY + "" */
114 if (matchlen == l) {
115 AddMatch(id, l, l, matches);
116 has_found_match = BROTLI_TRUE;
117 }
118 /* Transforms "" + BROTLI_TRANSFORM_OMIT_LAST_1 + "" and
119 "" + BROTLI_TRANSFORM_OMIT_LAST_1 + "ing " */
120 if (matchlen >= l - 1) {
121 AddMatch(id + 12 * n, l - 1, l, matches);
122 if (l + 2 < max_length &&
123 data[l - 1] == 'i' && data[l] == 'n' && data[l + 1] == 'g' &&
124 data[l + 2] == ' ') {
125 AddMatch(id + 49 * n, l + 3, l, matches);
126 }
127 has_found_match = BROTLI_TRUE;
128 }
129 /* Transform "" + BROTLI_TRANSFORM_OMIT_LAST_# + "" (# = 2 .. 9) */
130 minlen = min_length;
131 if (l > 9) minlen = BROTLI_MAX(size_t, minlen, l - 9);
132 maxlen = BROTLI_MIN(size_t, matchlen, l - 2);
133 for (len = minlen; len <= maxlen; ++len) {
134 size_t cut = l - len;
135 size_t transform_id = (cut << 2) +
136 (size_t)((dictionary->cutoffTransforms >> (cut * 6)) & 0x3F);
137 AddMatch(id + transform_id * n, len, l, matches);
138 has_found_match = BROTLI_TRUE;
139 }
140 if (matchlen < l || l + 6 >= max_length) {
141 continue;
142 }
143 s = &data[l];
144 /* Transforms "" + BROTLI_TRANSFORM_IDENTITY + <suffix> */
145 if (s[0] == ' ') {
146 AddMatch(id + n, l + 1, l, matches);
147 if (s[1] == 'a') {
148 if (s[2] == ' ') {
149 AddMatch(id + 28 * n, l + 3, l, matches);
150 } else if (s[2] == 's') {
151 if (s[3] == ' ') AddMatch(id + 46 * n, l + 4, l, matches);
152 } else if (s[2] == 't') {
153 if (s[3] == ' ') AddMatch(id + 60 * n, l + 4, l, matches);
154 } else if (s[2] == 'n') {
155 if (s[3] == 'd' && s[4] == ' ') {
156 AddMatch(id + 10 * n, l + 5, l, matches);
157 }
158 }
159 } else if (s[1] == 'b') {
160 if (s[2] == 'y' && s[3] == ' ') {
161 AddMatch(id + 38 * n, l + 4, l, matches);
162 }
163 } else if (s[1] == 'i') {
164 if (s[2] == 'n') {
165 if (s[3] == ' ') AddMatch(id + 16 * n, l + 4, l, matches);
166 } else if (s[2] == 's') {
167 if (s[3] == ' ') AddMatch(id + 47 * n, l + 4, l, matches);
168 }
169 } else if (s[1] == 'f') {
170 if (s[2] == 'o') {
171 if (s[3] == 'r' && s[4] == ' ') {
172 AddMatch(id + 25 * n, l + 5, l, matches);
173 }
174 } else if (s[2] == 'r') {
175 if (s[3] == 'o' && s[4] == 'm' && s[5] == ' ') {
176 AddMatch(id + 37 * n, l + 6, l, matches);
177 }
178 }
179 } else if (s[1] == 'o') {
180 if (s[2] == 'f') {
181 if (s[3] == ' ') AddMatch(id + 8 * n, l + 4, l, matches);
182 } else if (s[2] == 'n') {
183 if (s[3] == ' ') AddMatch(id + 45 * n, l + 4, l, matches);
184 }
185 } else if (s[1] == 'n') {
186 if (s[2] == 'o' && s[3] == 't' && s[4] == ' ') {
187 AddMatch(id + 80 * n, l + 5, l, matches);
188 }
189 } else if (s[1] == 't') {
190 if (s[2] == 'h') {
191 if (s[3] == 'e') {
192 if (s[4] == ' ') AddMatch(id + 5 * n, l + 5, l, matches);
193 } else if (s[3] == 'a') {
194 if (s[4] == 't' && s[5] == ' ') {
195 AddMatch(id + 29 * n, l + 6, l, matches);
196 }
197 }
198 } else if (s[2] == 'o') {
199 if (s[3] == ' ') AddMatch(id + 17 * n, l + 4, l, matches);
200 }
201 } else if (s[1] == 'w') {
202 if (s[2] == 'i' && s[3] == 't' && s[4] == 'h' && s[5] == ' ') {
203 AddMatch(id + 35 * n, l + 6, l, matches);
204 }
205 }
206 } else if (s[0] == '"') {
207 AddMatch(id + 19 * n, l + 1, l, matches);
208 if (s[1] == '>') {
209 AddMatch(id + 21 * n, l + 2, l, matches);
210 }
211 } else if (s[0] == '.') {
212 AddMatch(id + 20 * n, l + 1, l, matches);
213 if (s[1] == ' ') {
214 AddMatch(id + 31 * n, l + 2, l, matches);
215 if (s[2] == 'T' && s[3] == 'h') {
216 if (s[4] == 'e') {
217 if (s[5] == ' ') AddMatch(id + 43 * n, l + 6, l, matches);
218 } else if (s[4] == 'i') {
219 if (s[5] == 's' && s[6] == ' ') {
220 AddMatch(id + 75 * n, l + 7, l, matches);
221 }
222 }
223 }
224 }
225 } else if (s[0] == ',') {
226 AddMatch(id + 76 * n, l + 1, l, matches);
227 if (s[1] == ' ') {
228 AddMatch(id + 14 * n, l + 2, l, matches);
229 }
230 } else if (s[0] == '\n') {
231 AddMatch(id + 22 * n, l + 1, l, matches);
232 if (s[1] == '\t') {
233 AddMatch(id + 50 * n, l + 2, l, matches);
234 }
235 } else if (s[0] == ']') {
236 AddMatch(id + 24 * n, l + 1, l, matches);
237 } else if (s[0] == '\'') {
238 AddMatch(id + 36 * n, l + 1, l, matches);
239 } else if (s[0] == ':') {
240 AddMatch(id + 51 * n, l + 1, l, matches);
241 } else if (s[0] == '(') {
242 AddMatch(id + 57 * n, l + 1, l, matches);
243 } else if (s[0] == '=') {
244 if (s[1] == '"') {
245 AddMatch(id + 70 * n, l + 2, l, matches);
246 } else if (s[1] == '\'') {
247 AddMatch(id + 86 * n, l + 2, l, matches);
248 }
249 } else if (s[0] == 'a') {
250 if (s[1] == 'l' && s[2] == ' ') {
251 AddMatch(id + 84 * n, l + 3, l, matches);
252 }
253 } else if (s[0] == 'e') {
254 if (s[1] == 'd') {
255 if (s[2] == ' ') AddMatch(id + 53 * n, l + 3, l, matches);
256 } else if (s[1] == 'r') {
257 if (s[2] == ' ') AddMatch(id + 82 * n, l + 3, l, matches);
258 } else if (s[1] == 's') {
259 if (s[2] == 't' && s[3] == ' ') {
260 AddMatch(id + 95 * n, l + 4, l, matches);
261 }
262 }
263 } else if (s[0] == 'f') {
264 if (s[1] == 'u' && s[2] == 'l' && s[3] == ' ') {
265 AddMatch(id + 90 * n, l + 4, l, matches);
266 }
267 } else if (s[0] == 'i') {
268 if (s[1] == 'v') {
269 if (s[2] == 'e' && s[3] == ' ') {
270 AddMatch(id + 92 * n, l + 4, l, matches);
271 }
272 } else if (s[1] == 'z') {
273 if (s[2] == 'e' && s[3] == ' ') {
274 AddMatch(id + 100 * n, l + 4, l, matches);
275 }
276 }
277 } else if (s[0] == 'l') {
278 if (s[1] == 'e') {
279 if (s[2] == 's' && s[3] == 's' && s[4] == ' ') {
280 AddMatch(id + 93 * n, l + 5, l, matches);
281 }
282 } else if (s[1] == 'y') {
283 if (s[2] == ' ') AddMatch(id + 61 * n, l + 3, l, matches);
284 }
285 } else if (s[0] == 'o') {
286 if (s[1] == 'u' && s[2] == 's' && s[3] == ' ') {
287 AddMatch(id + 106 * n, l + 4, l, matches);
288 }
289 }
290 } else {
291 /* Set is_all_caps=0 for BROTLI_TRANSFORM_UPPERCASE_FIRST and
292 is_all_caps=1 otherwise (BROTLI_TRANSFORM_UPPERCASE_ALL)
293 transform. */
294 const BROTLI_BOOL is_all_caps =
295 TO_BROTLI_BOOL(w.transform != BROTLI_TRANSFORM_UPPERCASE_FIRST);
296 const uint8_t* s;
297 if (!IsMatch(dictionary->words, w, data, max_length)) {
298 continue;
299 }
300 /* Transform "" + kUppercase{First,All} + "" */
301 AddMatch(id + (is_all_caps ? 44 : 9) * n, l, l, matches);
302 has_found_match = BROTLI_TRUE;
303 if (l + 1 >= max_length) {
304 continue;
305 }
306 /* Transforms "" + kUppercase{First,All} + <suffix> */
307 s = &data[l];
308 if (s[0] == ' ') {
309 AddMatch(id + (is_all_caps ? 68 : 4) * n, l + 1, l, matches);
310 } else if (s[0] == '"') {
311 AddMatch(id + (is_all_caps ? 87 : 66) * n, l + 1, l, matches);
312 if (s[1] == '>') {
313 AddMatch(id + (is_all_caps ? 97 : 69) * n, l + 2, l, matches);
314 }
315 } else if (s[0] == '.') {
316 AddMatch(id + (is_all_caps ? 101 : 79) * n, l + 1, l, matches);
317 if (s[1] == ' ') {
318 AddMatch(id + (is_all_caps ? 114 : 88) * n, l + 2, l, matches);
319 }
320 } else if (s[0] == ',') {
321 AddMatch(id + (is_all_caps ? 112 : 99) * n, l + 1, l, matches);
322 if (s[1] == ' ') {
323 AddMatch(id + (is_all_caps ? 107 : 58) * n, l + 2, l, matches);
324 }
325 } else if (s[0] == '\'') {
326 AddMatch(id + (is_all_caps ? 94 : 74) * n, l + 1, l, matches);
327 } else if (s[0] == '(') {
328 AddMatch(id + (is_all_caps ? 113 : 78) * n, l + 1, l, matches);
329 } else if (s[0] == '=') {
330 if (s[1] == '"') {
331 AddMatch(id + (is_all_caps ? 105 : 104) * n, l + 2, l, matches);
332 } else if (s[1] == '\'') {
333 AddMatch(id + (is_all_caps ? 116 : 108) * n, l + 2, l, matches);
334 }
335 }
336 }
337 }
338 }
339 /* Transforms with prefixes " " and "." */
340 if (max_length >= 5 && (data[0] == ' ' || data[0] == '.')) {
341 BROTLI_BOOL is_space = TO_BROTLI_BOOL(data[0] == ' ');
342 size_t offset = dictionary->buckets[Hash(&data[1])];
343 BROTLI_BOOL end = !offset;
344 while (!end) {
345 DictWord w = dictionary->dict_words[offset++];
346 const size_t l = w.len & 0x1F;
347 const size_t n = (size_t)1 << dictionary->words->size_bits_by_length[l];
348 const size_t id = w.idx;
349 end = !!(w.len & 0x80);
350 w.len = (uint8_t)l;
351 if (w.transform == 0) {
352 const uint8_t* s;
353 if (!IsMatch(dictionary->words, w, &data[1], max_length - 1)) {
354 continue;
355 }
356 /* Transforms " " + BROTLI_TRANSFORM_IDENTITY + "" and
357 "." + BROTLI_TRANSFORM_IDENTITY + "" */
358 AddMatch(id + (is_space ? 6 : 32) * n, l + 1, l, matches);
359 has_found_match = BROTLI_TRUE;
360 if (l + 2 >= max_length) {
361 continue;
362 }
363 /* Transforms " " + BROTLI_TRANSFORM_IDENTITY + <suffix> and
364 "." + BROTLI_TRANSFORM_IDENTITY + <suffix>
365 */
366 s = &data[l + 1];
367 if (s[0] == ' ') {
368 AddMatch(id + (is_space ? 2 : 77) * n, l + 2, l, matches);
369 } else if (s[0] == '(') {
370 AddMatch(id + (is_space ? 89 : 67) * n, l + 2, l, matches);
371 } else if (is_space) {
372 if (s[0] == ',') {
373 AddMatch(id + 103 * n, l + 2, l, matches);
374 if (s[1] == ' ') {
375 AddMatch(id + 33 * n, l + 3, l, matches);
376 }
377 } else if (s[0] == '.') {
378 AddMatch(id + 71 * n, l + 2, l, matches);
379 if (s[1] == ' ') {
380 AddMatch(id + 52 * n, l + 3, l, matches);
381 }
382 } else if (s[0] == '=') {
383 if (s[1] == '"') {
384 AddMatch(id + 81 * n, l + 3, l, matches);
385 } else if (s[1] == '\'') {
386 AddMatch(id + 98 * n, l + 3, l, matches);
387 }
388 }
389 }
390 } else if (is_space) {
391 /* Set is_all_caps=0 for BROTLI_TRANSFORM_UPPERCASE_FIRST and
392 is_all_caps=1 otherwise (BROTLI_TRANSFORM_UPPERCASE_ALL)
393 transform. */
394 const BROTLI_BOOL is_all_caps =
395 TO_BROTLI_BOOL(w.transform != BROTLI_TRANSFORM_UPPERCASE_FIRST);
396 const uint8_t* s;
397 if (!IsMatch(dictionary->words, w, &data[1], max_length - 1)) {
398 continue;
399 }
400 /* Transforms " " + kUppercase{First,All} + "" */
401 AddMatch(id + (is_all_caps ? 85 : 30) * n, l + 1, l, matches);
402 has_found_match = BROTLI_TRUE;
403 if (l + 2 >= max_length) {
404 continue;
405 }
406 /* Transforms " " + kUppercase{First,All} + <suffix> */
407 s = &data[l + 1];
408 if (s[0] == ' ') {
409 AddMatch(id + (is_all_caps ? 83 : 15) * n, l + 2, l, matches);
410 } else if (s[0] == ',') {
411 if (!is_all_caps) {
412 AddMatch(id + 109 * n, l + 2, l, matches);
413 }
414 if (s[1] == ' ') {
415 AddMatch(id + (is_all_caps ? 111 : 65) * n, l + 3, l, matches);
416 }
417 } else if (s[0] == '.') {
418 AddMatch(id + (is_all_caps ? 115 : 96) * n, l + 2, l, matches);
419 if (s[1] == ' ') {
420 AddMatch(id + (is_all_caps ? 117 : 91) * n, l + 3, l, matches);
421 }
422 } else if (s[0] == '=') {
423 if (s[1] == '"') {
424 AddMatch(id + (is_all_caps ? 110 : 118) * n, l + 3, l, matches);
425 } else if (s[1] == '\'') {
426 AddMatch(id + (is_all_caps ? 119 : 120) * n, l + 3, l, matches);
427 }
428 }
429 }
430 }
431 }
432 if (max_length >= 6) {
433 /* Transforms with prefixes "e ", "s ", ", " and "\xC2\xA0" */
434 if ((data[1] == ' ' &&
435 (data[0] == 'e' || data[0] == 's' || data[0] == ',')) ||
436 (data[0] == 0xC2 && data[1] == 0xA0)) {
437 size_t offset = dictionary->buckets[Hash(&data[2])];
438 BROTLI_BOOL end = !offset;
439 while (!end) {
440 DictWord w = dictionary->dict_words[offset++];
441 const size_t l = w.len & 0x1F;
442 const size_t n = (size_t)1 << dictionary->words->size_bits_by_length[l];
443 const size_t id = w.idx;
444 end = !!(w.len & 0x80);
445 w.len = (uint8_t)l;
446 if (w.transform == 0 &&
447 IsMatch(dictionary->words, w, &data[2], max_length - 2)) {
448 if (data[0] == 0xC2) {
449 AddMatch(id + 102 * n, l + 2, l, matches);
450 has_found_match = BROTLI_TRUE;
451 } else if (l + 2 < max_length && data[l + 2] == ' ') {
452 size_t t = data[0] == 'e' ? 18 : (data[0] == 's' ? 7 : 13);
453 AddMatch(id + t * n, l + 3, l, matches);
454 has_found_match = BROTLI_TRUE;
455 }
456 }
457 }
458 }
459 }
460 if (max_length >= 9) {
461 /* Transforms with prefixes " the " and ".com/" */
462 if ((data[0] == ' ' && data[1] == 't' && data[2] == 'h' &&
463 data[3] == 'e' && data[4] == ' ') ||
464 (data[0] == '.' && data[1] == 'c' && data[2] == 'o' &&
465 data[3] == 'm' && data[4] == '/')) {
466 size_t offset = dictionary->buckets[Hash(&data[5])];
467 BROTLI_BOOL end = !offset;
468 while (!end) {
469 DictWord w = dictionary->dict_words[offset++];
470 const size_t l = w.len & 0x1F;
471 const size_t n = (size_t)1 << dictionary->words->size_bits_by_length[l];
472 const size_t id = w.idx;
473 end = !!(w.len & 0x80);
474 w.len = (uint8_t)l;
475 if (w.transform == 0 &&
476 IsMatch(dictionary->words, w, &data[5], max_length - 5)) {
477 AddMatch(id + (data[0] == ' ' ? 41 : 72) * n, l + 5, l, matches);
478 has_found_match = BROTLI_TRUE;
479 if (l + 5 < max_length) {
480 const uint8_t* s = &data[l + 5];
481 if (data[0] == ' ') {
482 if (l + 8 < max_length &&
483 s[0] == ' ' && s[1] == 'o' && s[2] == 'f' && s[3] == ' ') {
484 AddMatch(id + 62 * n, l + 9, l, matches);
485 if (l + 12 < max_length &&
486 s[4] == 't' && s[5] == 'h' && s[6] == 'e' && s[7] == ' ') {
487 AddMatch(id + 73 * n, l + 13, l, matches);
488 }
489 }
490 }
491 }
492 }
493 }
494 }
495 }
496 return has_found_match;
497 }
498
499 /* Finds matches for one or more dictionaries, if multiple are present
500 in the contextual dictionary */
BrotliFindAllStaticDictionaryMatches(const BrotliEncoderDictionary * dictionary,const uint8_t * data,size_t min_length,size_t max_length,uint32_t * matches)501 BROTLI_BOOL BrotliFindAllStaticDictionaryMatches(
502 const BrotliEncoderDictionary* dictionary, const uint8_t* data,
503 size_t min_length, size_t max_length, uint32_t* matches) {
504 BROTLI_BOOL has_found_match =
505 BrotliFindAllStaticDictionaryMatchesFor(
506 dictionary, data, min_length, max_length, matches);
507
508 if (!!dictionary->parent && dictionary->parent->num_dictionaries > 1) {
509 uint32_t matches2[BROTLI_MAX_STATIC_DICTIONARY_MATCH_LEN + 1];
510 int l;
511 const BrotliEncoderDictionary* dictionary2 = dictionary->parent->dict[0];
512 if (dictionary2 == dictionary) {
513 dictionary2 = dictionary->parent->dict[1];
514 }
515
516 for (l = 0; l < BROTLI_MAX_STATIC_DICTIONARY_MATCH_LEN + 1; l++) {
517 matches2[l] = kInvalidMatch;
518 }
519
520 has_found_match |= BrotliFindAllStaticDictionaryMatchesFor(
521 dictionary2, data, min_length, max_length, matches2);
522
523 for (l = 0; l < BROTLI_MAX_STATIC_DICTIONARY_MATCH_LEN + 1; l++) {
524 if (matches2[l] != kInvalidMatch) {
525 uint32_t dist = (uint32_t)(matches2[l] >> 5);
526 uint32_t len_code = matches2[l] & 31;
527 uint32_t skipdist = (uint32_t)((uint32_t)(1 << dictionary->words->
528 size_bits_by_length[len_code]) & ~1u) *
529 (uint32_t)dictionary->num_transforms;
530 /* TODO(lode): check for dist overflow */
531 dist += skipdist;
532 AddMatch(dist, (size_t)l, len_code, matches);
533 }
534 }
535 }
536 return has_found_match;
537 }
538 #if defined(__cplusplus) || defined(c_plusplus)
539 } /* extern "C" */
540 #endif
541