1 | /* |
2 | * Copyright © 2022 Google, Inc. |
3 | * |
4 | * This is part of HarfBuzz, a text shaping library. |
5 | * |
6 | * Permission is hereby granted, without written agreement and without |
7 | * license or royalty fees, to use, copy, modify, and distribute this |
8 | * software and its documentation for any purpose, provided that the |
9 | * above copyright notice and the following two paragraphs appear in |
10 | * all copies of this software. |
11 | * |
12 | * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR |
13 | * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES |
14 | * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN |
15 | * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH |
16 | * DAMAGE. |
17 | * |
18 | * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, |
19 | * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND |
20 | * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS |
21 | * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO |
22 | * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. |
23 | * |
24 | * Google Author(s): Garret Rieger |
25 | */ |
26 | |
27 | #include "graph.hh" |
28 | #include "../hb-ot-layout-gsubgpos.hh" |
29 | #include "../OT/Layout/GSUB/ExtensionSubst.hh" |
30 | #include "gsubgpos-context.hh" |
31 | #include "pairpos-graph.hh" |
32 | #include "markbasepos-graph.hh" |
33 | |
34 | #ifndef GRAPH_GSUBGPOS_GRAPH_HH |
35 | #define GRAPH_GSUBGPOS_GRAPH_HH |
36 | |
37 | namespace graph { |
38 | |
39 | struct Lookup; |
40 | |
41 | template<typename T> |
42 | struct ExtensionFormat1 : public OT::ExtensionFormat1<T> |
43 | { |
44 | void reset(unsigned type) |
45 | { |
46 | this->format = 1; |
47 | this->extensionLookupType = type; |
48 | this->extensionOffset = 0; |
49 | } |
50 | |
51 | bool sanitize (graph_t::vertex_t& vertex) const |
52 | { |
53 | int64_t vertex_len = vertex.obj.tail - vertex.obj.head; |
54 | return vertex_len >= OT::ExtensionFormat1<T>::static_size; |
55 | } |
56 | |
57 | unsigned get_lookup_type () const |
58 | { |
59 | return this->extensionLookupType; |
60 | } |
61 | |
62 | unsigned get_subtable_index (graph_t& graph, unsigned this_index) const |
63 | { |
64 | return graph.index_for_offset (this_index, &this->extensionOffset); |
65 | } |
66 | }; |
67 | |
68 | struct Lookup : public OT::Lookup |
69 | { |
70 | unsigned number_of_subtables () const |
71 | { |
72 | return subTable.len; |
73 | } |
74 | |
75 | bool sanitize (graph_t::vertex_t& vertex) const |
76 | { |
77 | int64_t vertex_len = vertex.obj.tail - vertex.obj.head; |
78 | if (vertex_len < OT::Lookup::min_size) return false; |
79 | return vertex_len >= this->get_size (); |
80 | } |
81 | |
82 | bool is_extension (hb_tag_t table_tag) const |
83 | { |
84 | return lookupType == extension_type (table_tag); |
85 | } |
86 | |
87 | bool make_extension (gsubgpos_graph_context_t& c, |
88 | unsigned this_index) |
89 | { |
90 | unsigned type = lookupType; |
91 | unsigned ext_type = extension_type (c.table_tag); |
92 | if (!ext_type || is_extension (c.table_tag)) |
93 | { |
94 | // NOOP |
95 | return true; |
96 | } |
97 | |
98 | DEBUG_MSG (SUBSET_REPACK, nullptr, |
99 | "Promoting lookup type %u (obj %u) to extension." , |
100 | type, |
101 | this_index); |
102 | |
103 | for (unsigned i = 0; i < subTable.len; i++) |
104 | { |
105 | unsigned subtable_index = c.graph.index_for_offset (this_index, &subTable[i]); |
106 | if (!make_subtable_extension (c, |
107 | this_index, |
108 | subtable_index)) |
109 | return false; |
110 | } |
111 | |
112 | lookupType = ext_type; |
113 | return true; |
114 | } |
115 | |
116 | bool split_subtables_if_needed (gsubgpos_graph_context_t& c, |
117 | unsigned this_index) |
118 | { |
119 | unsigned type = lookupType; |
120 | bool is_ext = is_extension (c.table_tag); |
121 | |
122 | if (c.table_tag != HB_OT_TAG_GPOS) |
123 | return true; |
124 | |
125 | if (!is_ext && |
126 | type != OT::Layout::GPOS_impl::PosLookupSubTable::Type::Pair && |
127 | type != OT::Layout::GPOS_impl::PosLookupSubTable::Type::MarkBase) |
128 | return true; |
129 | |
130 | hb_vector_t<hb_pair_t<unsigned, hb_vector_t<unsigned>>> all_new_subtables; |
131 | for (unsigned i = 0; i < subTable.len; i++) |
132 | { |
133 | unsigned subtable_index = c.graph.index_for_offset (this_index, &subTable[i]); |
134 | unsigned parent_index = this_index; |
135 | if (is_ext) { |
136 | unsigned ext_subtable_index = subtable_index; |
137 | parent_index = ext_subtable_index; |
138 | ExtensionFormat1<OT::Layout::GSUB_impl::ExtensionSubst>* extension = |
139 | (ExtensionFormat1<OT::Layout::GSUB_impl::ExtensionSubst>*) |
140 | c.graph.object (ext_subtable_index).head; |
141 | if (!extension || !extension->sanitize (c.graph.vertices_[ext_subtable_index])) |
142 | continue; |
143 | |
144 | subtable_index = extension->get_subtable_index (c.graph, ext_subtable_index); |
145 | type = extension->get_lookup_type (); |
146 | if (type != OT::Layout::GPOS_impl::PosLookupSubTable::Type::Pair |
147 | && type != OT::Layout::GPOS_impl::PosLookupSubTable::Type::MarkBase) |
148 | continue; |
149 | } |
150 | |
151 | hb_vector_t<unsigned> new_sub_tables; |
152 | switch (type) |
153 | { |
154 | case 2: |
155 | new_sub_tables = split_subtable<PairPos> (c, parent_index, subtable_index); break; |
156 | case 4: |
157 | new_sub_tables = split_subtable<MarkBasePos> (c, parent_index, subtable_index); break; |
158 | default: |
159 | break; |
160 | } |
161 | if (new_sub_tables.in_error ()) return false; |
162 | if (!new_sub_tables) continue; |
163 | hb_pair_t<unsigned, hb_vector_t<unsigned>>* entry = all_new_subtables.push (); |
164 | entry->first = i; |
165 | entry->second = std::move (new_sub_tables); |
166 | } |
167 | |
168 | if (all_new_subtables) { |
169 | return add_sub_tables (c, this_index, type, all_new_subtables); |
170 | } |
171 | |
172 | return true; |
173 | } |
174 | |
175 | template<typename T> |
176 | hb_vector_t<unsigned> split_subtable (gsubgpos_graph_context_t& c, |
177 | unsigned parent_idx, |
178 | unsigned objidx) |
179 | { |
180 | T* sub_table = (T*) c.graph.object (objidx).head; |
181 | if (!sub_table || !sub_table->sanitize (c.graph.vertices_[objidx])) |
182 | return hb_vector_t<unsigned> (); |
183 | |
184 | return sub_table->split_subtables (c, parent_idx, objidx); |
185 | } |
186 | |
187 | bool add_sub_tables (gsubgpos_graph_context_t& c, |
188 | unsigned this_index, |
189 | unsigned type, |
190 | hb_vector_t<hb_pair_t<unsigned, hb_vector_t<unsigned>>>& subtable_ids) |
191 | { |
192 | bool is_ext = is_extension (c.table_tag); |
193 | auto& v = c.graph.vertices_[this_index]; |
194 | fix_existing_subtable_links (c, this_index, subtable_ids); |
195 | |
196 | unsigned new_subtable_count = 0; |
197 | for (const auto& p : subtable_ids) |
198 | new_subtable_count += p.second.length; |
199 | |
200 | size_t new_size = v.table_size () |
201 | + new_subtable_count * OT::Offset16::static_size; |
202 | char* buffer = (char*) hb_calloc (1, new_size); |
203 | if (!buffer) return false; |
204 | if (!c.add_buffer (buffer)) |
205 | { |
206 | hb_free (buffer); |
207 | return false; |
208 | } |
209 | hb_memcpy (buffer, v.obj.head, v.table_size()); |
210 | |
211 | v.obj.head = buffer; |
212 | v.obj.tail = buffer + new_size; |
213 | |
214 | Lookup* new_lookup = (Lookup*) buffer; |
215 | |
216 | unsigned shift = 0; |
217 | new_lookup->subTable.len = subTable.len + new_subtable_count; |
218 | for (const auto& p : subtable_ids) |
219 | { |
220 | unsigned offset_index = p.first + shift + 1; |
221 | shift += p.second.length; |
222 | |
223 | for (unsigned subtable_id : p.second) |
224 | { |
225 | if (is_ext) |
226 | { |
227 | unsigned ext_id = create_extension_subtable (c, subtable_id, type); |
228 | c.graph.vertices_[subtable_id].add_parent (ext_id); |
229 | subtable_id = ext_id; |
230 | } |
231 | |
232 | auto* link = v.obj.real_links.push (); |
233 | link->width = 2; |
234 | link->objidx = subtable_id; |
235 | link->position = (char*) &new_lookup->subTable[offset_index++] - |
236 | (char*) new_lookup; |
237 | c.graph.vertices_[subtable_id].add_parent (this_index); |
238 | } |
239 | } |
240 | |
241 | // Repacker sort order depends on link order, which we've messed up so resort it. |
242 | v.obj.real_links.qsort (); |
243 | |
244 | // The head location of the lookup has changed, invalidating the lookups map entry |
245 | // in the context. Update the map. |
246 | c.lookups.set (this_index, new_lookup); |
247 | return true; |
248 | } |
249 | |
250 | void fix_existing_subtable_links (gsubgpos_graph_context_t& c, |
251 | unsigned this_index, |
252 | hb_vector_t<hb_pair_t<unsigned, hb_vector_t<unsigned>>>& subtable_ids) |
253 | { |
254 | auto& v = c.graph.vertices_[this_index]; |
255 | Lookup* lookup = (Lookup*) v.obj.head; |
256 | |
257 | unsigned shift = 0; |
258 | for (const auto& p : subtable_ids) |
259 | { |
260 | unsigned insert_index = p.first + shift; |
261 | unsigned pos_offset = p.second.length * OT::Offset16::static_size; |
262 | unsigned insert_offset = (char*) &lookup->subTable[insert_index] - (char*) lookup; |
263 | shift += p.second.length; |
264 | |
265 | for (auto& l : v.obj.all_links_writer ()) |
266 | { |
267 | if (l.position > insert_offset) l.position += pos_offset; |
268 | } |
269 | } |
270 | } |
271 | |
272 | unsigned create_extension_subtable (gsubgpos_graph_context_t& c, |
273 | unsigned subtable_index, |
274 | unsigned type) |
275 | { |
276 | unsigned extension_size = OT::ExtensionFormat1<OT::Layout::GSUB_impl::ExtensionSubst>::static_size; |
277 | |
278 | unsigned ext_index = c.create_node (extension_size); |
279 | if (ext_index == (unsigned) -1) |
280 | return -1; |
281 | |
282 | auto& ext_vertex = c.graph.vertices_[ext_index]; |
283 | ExtensionFormat1<OT::Layout::GSUB_impl::ExtensionSubst>* extension = |
284 | (ExtensionFormat1<OT::Layout::GSUB_impl::ExtensionSubst>*) ext_vertex.obj.head; |
285 | extension->reset (type); |
286 | |
287 | // Make extension point at the subtable. |
288 | auto* l = ext_vertex.obj.real_links.push (); |
289 | |
290 | l->width = 4; |
291 | l->objidx = subtable_index; |
292 | l->position = 4; |
293 | |
294 | return ext_index; |
295 | } |
296 | |
297 | bool make_subtable_extension (gsubgpos_graph_context_t& c, |
298 | unsigned lookup_index, |
299 | unsigned subtable_index) |
300 | { |
301 | unsigned type = lookupType; |
302 | |
303 | unsigned ext_index = create_extension_subtable(c, subtable_index, type); |
304 | if (ext_index == (unsigned) -1) |
305 | return false; |
306 | |
307 | auto& lookup_vertex = c.graph.vertices_[lookup_index]; |
308 | for (auto& l : lookup_vertex.obj.real_links.writer ()) |
309 | { |
310 | if (l.objidx == subtable_index) |
311 | // Change lookup to point at the extension. |
312 | l.objidx = ext_index; |
313 | } |
314 | |
315 | // Make extension point at the subtable. |
316 | auto& ext_vertex = c.graph.vertices_[ext_index]; |
317 | auto& subtable_vertex = c.graph.vertices_[subtable_index]; |
318 | ext_vertex.add_parent (lookup_index); |
319 | subtable_vertex.remap_parent (lookup_index, ext_index); |
320 | |
321 | return true; |
322 | } |
323 | |
324 | private: |
325 | unsigned extension_type (hb_tag_t table_tag) const |
326 | { |
327 | switch (table_tag) |
328 | { |
329 | case HB_OT_TAG_GPOS: return 9; |
330 | case HB_OT_TAG_GSUB: return 7; |
331 | default: return 0; |
332 | } |
333 | } |
334 | }; |
335 | |
336 | template <typename T> |
337 | struct LookupList : public OT::LookupList<T> |
338 | { |
339 | bool sanitize (const graph_t::vertex_t& vertex) const |
340 | { |
341 | int64_t vertex_len = vertex.obj.tail - vertex.obj.head; |
342 | if (vertex_len < OT::LookupList<T>::min_size) return false; |
343 | return vertex_len >= OT::LookupList<T>::item_size * this->len; |
344 | } |
345 | }; |
346 | |
347 | struct GSTAR : public OT::GSUBGPOS |
348 | { |
349 | static GSTAR* graph_to_gstar (graph_t& graph) |
350 | { |
351 | const auto& r = graph.root (); |
352 | |
353 | GSTAR* gstar = (GSTAR*) r.obj.head; |
354 | if (!gstar || !gstar->sanitize (r)) |
355 | return nullptr; |
356 | |
357 | return gstar; |
358 | } |
359 | |
360 | const void* get_lookup_list_field_offset () const |
361 | { |
362 | switch (u.version.major) { |
363 | case 1: return u.version1.get_lookup_list_offset (); |
364 | #ifndef HB_NO_BEYOND_64K |
365 | case 2: return u.version2.get_lookup_list_offset (); |
366 | #endif |
367 | default: return 0; |
368 | } |
369 | } |
370 | |
371 | bool sanitize (const graph_t::vertex_t& vertex) |
372 | { |
373 | int64_t len = vertex.obj.tail - vertex.obj.head; |
374 | if (len < OT::GSUBGPOS::min_size) return false; |
375 | return len >= get_size (); |
376 | } |
377 | |
378 | void find_lookups (graph_t& graph, |
379 | hb_hashmap_t<unsigned, Lookup*>& lookups /* OUT */) |
380 | { |
381 | switch (u.version.major) { |
382 | case 1: find_lookups<SmallTypes> (graph, lookups); break; |
383 | #ifndef HB_NO_BEYOND_64K |
384 | case 2: find_lookups<MediumTypes> (graph, lookups); break; |
385 | #endif |
386 | } |
387 | } |
388 | |
389 | unsigned get_lookup_list_index (graph_t& graph) |
390 | { |
391 | return graph.index_for_offset (graph.root_idx (), |
392 | get_lookup_list_field_offset()); |
393 | } |
394 | |
395 | template<typename Types> |
396 | void find_lookups (graph_t& graph, |
397 | hb_hashmap_t<unsigned, Lookup*>& lookups /* OUT */) |
398 | { |
399 | unsigned lookup_list_idx = get_lookup_list_index (graph); |
400 | const LookupList<Types>* lookupList = |
401 | (const LookupList<Types>*) graph.object (lookup_list_idx).head; |
402 | if (!lookupList || !lookupList->sanitize (graph.vertices_[lookup_list_idx])) |
403 | return; |
404 | |
405 | for (unsigned i = 0; i < lookupList->len; i++) |
406 | { |
407 | unsigned lookup_idx = graph.index_for_offset (lookup_list_idx, &(lookupList->arrayZ[i])); |
408 | Lookup* lookup = (Lookup*) graph.object (lookup_idx).head; |
409 | if (!lookup || !lookup->sanitize (graph.vertices_[lookup_idx])) continue; |
410 | lookups.set (lookup_idx, lookup); |
411 | } |
412 | } |
413 | }; |
414 | |
415 | |
416 | |
417 | |
418 | } |
419 | |
420 | #endif /* GRAPH_GSUBGPOS_GRAPH_HH */ |
421 | |