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