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 { resetgraph::ExtensionFormat144 void reset(unsigned type) 45 { 46 this->format = 1; 47 this->extensionLookupType = type; 48 this->extensionOffset = 0; 49 } 50 sanitizegraph::ExtensionFormat151 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 get_lookup_typegraph::ExtensionFormat157 unsigned get_lookup_type () const 58 { 59 return this->extensionLookupType; 60 } 61 get_subtable_indexgraph::ExtensionFormat162 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 { number_of_subtablesgraph::Lookup70 unsigned number_of_subtables () const 71 { 72 return subTable.len; 73 } 74 sanitizegraph::Lookup75 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 hb_barrier (); 80 return vertex_len >= this->get_size (); 81 } 82 is_extensiongraph::Lookup83 bool is_extension (hb_tag_t table_tag) const 84 { 85 return lookupType == extension_type (table_tag); 86 } 87 make_extensiongraph::Lookup88 bool make_extension (gsubgpos_graph_context_t& c, 89 unsigned this_index) 90 { 91 unsigned type = lookupType; 92 unsigned ext_type = extension_type (c.table_tag); 93 if (!ext_type || is_extension (c.table_tag)) 94 { 95 // NOOP 96 return true; 97 } 98 99 DEBUG_MSG (SUBSET_REPACK, nullptr, 100 "Promoting lookup type %u (obj %u) to extension.", 101 type, 102 this_index); 103 104 for (unsigned i = 0; i < subTable.len; i++) 105 { 106 unsigned subtable_index = c.graph.index_for_offset (this_index, &subTable[i]); 107 if (!make_subtable_extension (c, 108 this_index, 109 subtable_index)) 110 return false; 111 } 112 113 lookupType = ext_type; 114 return true; 115 } 116 split_subtables_if_neededgraph::Lookup117 bool split_subtables_if_needed (gsubgpos_graph_context_t& c, 118 unsigned this_index) 119 { 120 unsigned type = lookupType; 121 bool is_ext = is_extension (c.table_tag); 122 123 if (c.table_tag != HB_OT_TAG_GPOS) 124 return true; 125 126 if (!is_ext && 127 type != OT::Layout::GPOS_impl::PosLookupSubTable::Type::Pair && 128 type != OT::Layout::GPOS_impl::PosLookupSubTable::Type::MarkBase) 129 return true; 130 131 hb_vector_t<hb_pair_t<unsigned, hb_vector_t<unsigned>>> all_new_subtables; 132 for (unsigned i = 0; i < subTable.len; i++) 133 { 134 unsigned subtable_index = c.graph.index_for_offset (this_index, &subTable[i]); 135 unsigned parent_index = this_index; 136 if (is_ext) { 137 unsigned ext_subtable_index = subtable_index; 138 parent_index = ext_subtable_index; 139 ExtensionFormat1<OT::Layout::GSUB_impl::ExtensionSubst>* extension = 140 (ExtensionFormat1<OT::Layout::GSUB_impl::ExtensionSubst>*) 141 c.graph.object (ext_subtable_index).head; 142 if (!extension || !extension->sanitize (c.graph.vertices_[ext_subtable_index])) 143 continue; 144 145 subtable_index = extension->get_subtable_index (c.graph, ext_subtable_index); 146 type = extension->get_lookup_type (); 147 if (type != OT::Layout::GPOS_impl::PosLookupSubTable::Type::Pair 148 && type != OT::Layout::GPOS_impl::PosLookupSubTable::Type::MarkBase) 149 continue; 150 } 151 152 hb_vector_t<unsigned> new_sub_tables; 153 switch (type) 154 { 155 case 2: 156 new_sub_tables = split_subtable<PairPos> (c, parent_index, subtable_index); break; 157 case 4: 158 new_sub_tables = split_subtable<MarkBasePos> (c, parent_index, subtable_index); break; 159 default: 160 break; 161 } 162 if (new_sub_tables.in_error ()) return false; 163 if (!new_sub_tables) continue; 164 hb_pair_t<unsigned, hb_vector_t<unsigned>>* entry = all_new_subtables.push (); 165 entry->first = i; 166 entry->second = std::move (new_sub_tables); 167 } 168 169 if (all_new_subtables) { 170 return add_sub_tables (c, this_index, type, all_new_subtables); 171 } 172 173 return true; 174 } 175 176 template<typename T> split_subtablegraph::Lookup177 hb_vector_t<unsigned> split_subtable (gsubgpos_graph_context_t& c, 178 unsigned parent_idx, 179 unsigned objidx) 180 { 181 T* sub_table = (T*) c.graph.object (objidx).head; 182 if (!sub_table || !sub_table->sanitize (c.graph.vertices_[objidx])) 183 return hb_vector_t<unsigned> (); 184 185 return sub_table->split_subtables (c, parent_idx, objidx); 186 } 187 add_sub_tablesgraph::Lookup188 bool add_sub_tables (gsubgpos_graph_context_t& c, 189 unsigned this_index, 190 unsigned type, 191 hb_vector_t<hb_pair_t<unsigned, hb_vector_t<unsigned>>>& subtable_ids) 192 { 193 bool is_ext = is_extension (c.table_tag); 194 auto& v = c.graph.vertices_[this_index]; 195 fix_existing_subtable_links (c, this_index, subtable_ids); 196 197 unsigned new_subtable_count = 0; 198 for (const auto& p : subtable_ids) 199 new_subtable_count += p.second.length; 200 201 size_t new_size = v.table_size () 202 + new_subtable_count * OT::Offset16::static_size; 203 char* buffer = (char*) hb_calloc (1, new_size); 204 if (!buffer) return false; 205 if (!c.add_buffer (buffer)) 206 { 207 hb_free (buffer); 208 return false; 209 } 210 hb_memcpy (buffer, v.obj.head, v.table_size()); 211 212 v.obj.head = buffer; 213 v.obj.tail = buffer + new_size; 214 215 Lookup* new_lookup = (Lookup*) buffer; 216 217 unsigned shift = 0; 218 new_lookup->subTable.len = subTable.len + new_subtable_count; 219 for (const auto& p : subtable_ids) 220 { 221 unsigned offset_index = p.first + shift + 1; 222 shift += p.second.length; 223 224 for (unsigned subtable_id : p.second) 225 { 226 if (is_ext) 227 { 228 unsigned ext_id = create_extension_subtable (c, subtable_id, type); 229 c.graph.vertices_[subtable_id].add_parent (ext_id); 230 subtable_id = ext_id; 231 } 232 233 auto* link = v.obj.real_links.push (); 234 link->width = 2; 235 link->objidx = subtable_id; 236 link->position = (char*) &new_lookup->subTable[offset_index++] - 237 (char*) new_lookup; 238 c.graph.vertices_[subtable_id].add_parent (this_index); 239 } 240 } 241 242 // Repacker sort order depends on link order, which we've messed up so resort it. 243 v.obj.real_links.qsort (); 244 245 // The head location of the lookup has changed, invalidating the lookups map entry 246 // in the context. Update the map. 247 c.lookups.set (this_index, new_lookup); 248 return true; 249 } 250 fix_existing_subtable_linksgraph::Lookup251 void fix_existing_subtable_links (gsubgpos_graph_context_t& c, 252 unsigned this_index, 253 hb_vector_t<hb_pair_t<unsigned, hb_vector_t<unsigned>>>& subtable_ids) 254 { 255 auto& v = c.graph.vertices_[this_index]; 256 Lookup* lookup = (Lookup*) v.obj.head; 257 258 unsigned shift = 0; 259 for (const auto& p : subtable_ids) 260 { 261 unsigned insert_index = p.first + shift; 262 unsigned pos_offset = p.second.length * OT::Offset16::static_size; 263 unsigned insert_offset = (char*) &lookup->subTable[insert_index] - (char*) lookup; 264 shift += p.second.length; 265 266 for (auto& l : v.obj.all_links_writer ()) 267 { 268 if (l.position > insert_offset) l.position += pos_offset; 269 } 270 } 271 } 272 create_extension_subtablegraph::Lookup273 unsigned create_extension_subtable (gsubgpos_graph_context_t& c, 274 unsigned subtable_index, 275 unsigned type) 276 { 277 unsigned extension_size = OT::ExtensionFormat1<OT::Layout::GSUB_impl::ExtensionSubst>::static_size; 278 279 unsigned ext_index = c.create_node (extension_size); 280 if (ext_index == (unsigned) -1) 281 return -1; 282 283 auto& ext_vertex = c.graph.vertices_[ext_index]; 284 ExtensionFormat1<OT::Layout::GSUB_impl::ExtensionSubst>* extension = 285 (ExtensionFormat1<OT::Layout::GSUB_impl::ExtensionSubst>*) ext_vertex.obj.head; 286 extension->reset (type); 287 288 // Make extension point at the subtable. 289 auto* l = ext_vertex.obj.real_links.push (); 290 291 l->width = 4; 292 l->objidx = subtable_index; 293 l->position = 4; 294 295 return ext_index; 296 } 297 make_subtable_extensiongraph::Lookup298 bool make_subtable_extension (gsubgpos_graph_context_t& c, 299 unsigned lookup_index, 300 unsigned subtable_index) 301 { 302 unsigned type = lookupType; 303 unsigned ext_index = -1; 304 unsigned* existing_ext_index = nullptr; 305 if (c.subtable_to_extension.has(subtable_index, &existing_ext_index)) { 306 ext_index = *existing_ext_index; 307 } else { 308 ext_index = create_extension_subtable(c, subtable_index, type); 309 c.subtable_to_extension.set(subtable_index, ext_index); 310 } 311 312 if (ext_index == (unsigned) -1) 313 return false; 314 315 auto& subtable_vertex = c.graph.vertices_[subtable_index]; 316 auto& lookup_vertex = c.graph.vertices_[lookup_index]; 317 for (auto& l : lookup_vertex.obj.real_links.writer ()) 318 { 319 if (l.objidx == subtable_index) { 320 // Change lookup to point at the extension. 321 l.objidx = ext_index; 322 if (existing_ext_index) 323 subtable_vertex.remove_parent(lookup_index); 324 } 325 } 326 327 // Make extension point at the subtable. 328 auto& ext_vertex = c.graph.vertices_[ext_index]; 329 ext_vertex.add_parent (lookup_index); 330 if (!existing_ext_index) 331 subtable_vertex.remap_parent (lookup_index, ext_index); 332 333 return true; 334 } 335 336 private: extension_typegraph::Lookup337 unsigned extension_type (hb_tag_t table_tag) const 338 { 339 switch (table_tag) 340 { 341 case HB_OT_TAG_GPOS: return 9; 342 case HB_OT_TAG_GSUB: return 7; 343 default: return 0; 344 } 345 } 346 }; 347 348 template <typename T> 349 struct LookupList : public OT::LookupList<T> 350 { sanitizegraph::LookupList351 bool sanitize (const graph_t::vertex_t& vertex) const 352 { 353 int64_t vertex_len = vertex.obj.tail - vertex.obj.head; 354 if (vertex_len < OT::LookupList<T>::min_size) return false; 355 hb_barrier (); 356 return vertex_len >= OT::LookupList<T>::item_size * this->len; 357 } 358 }; 359 360 struct GSTAR : public OT::GSUBGPOS 361 { graph_to_gstargraph::GSTAR362 static GSTAR* graph_to_gstar (graph_t& graph) 363 { 364 const auto& r = graph.root (); 365 366 GSTAR* gstar = (GSTAR*) r.obj.head; 367 if (!gstar || !gstar->sanitize (r)) 368 return nullptr; 369 hb_barrier (); 370 371 return gstar; 372 } 373 get_lookup_list_field_offsetgraph::GSTAR374 const void* get_lookup_list_field_offset () const 375 { 376 switch (u.version.major) { 377 case 1: return u.version1.get_lookup_list_offset (); 378 #ifndef HB_NO_BEYOND_64K 379 case 2: return u.version2.get_lookup_list_offset (); 380 #endif 381 default: return 0; 382 } 383 } 384 sanitizegraph::GSTAR385 bool sanitize (const graph_t::vertex_t& vertex) 386 { 387 int64_t len = vertex.obj.tail - vertex.obj.head; 388 if (len < OT::GSUBGPOS::min_size) return false; 389 hb_barrier (); 390 return len >= get_size (); 391 } 392 find_lookupsgraph::GSTAR393 void find_lookups (graph_t& graph, 394 hb_hashmap_t<unsigned, Lookup*>& lookups /* OUT */) 395 { 396 switch (u.version.major) { 397 case 1: find_lookups<SmallTypes> (graph, lookups); break; 398 #ifndef HB_NO_BEYOND_64K 399 case 2: find_lookups<MediumTypes> (graph, lookups); break; 400 #endif 401 } 402 } 403 get_lookup_list_indexgraph::GSTAR404 unsigned get_lookup_list_index (graph_t& graph) 405 { 406 return graph.index_for_offset (graph.root_idx (), 407 get_lookup_list_field_offset()); 408 } 409 410 template<typename Types> find_lookupsgraph::GSTAR411 void find_lookups (graph_t& graph, 412 hb_hashmap_t<unsigned, Lookup*>& lookups /* OUT */) 413 { 414 unsigned lookup_list_idx = get_lookup_list_index (graph); 415 const LookupList<Types>* lookupList = 416 (const LookupList<Types>*) graph.object (lookup_list_idx).head; 417 if (!lookupList || !lookupList->sanitize (graph.vertices_[lookup_list_idx])) 418 return; 419 420 for (unsigned i = 0; i < lookupList->len; i++) 421 { 422 unsigned lookup_idx = graph.index_for_offset (lookup_list_idx, &(lookupList->arrayZ[i])); 423 Lookup* lookup = (Lookup*) graph.object (lookup_idx).head; 424 if (!lookup || !lookup->sanitize (graph.vertices_[lookup_idx])) continue; 425 lookups.set (lookup_idx, lookup); 426 } 427 } 428 }; 429 430 431 432 433 } 434 435 #endif /* GRAPH_GSUBGPOS_GRAPH_HH */ 436