pairpos-graph.hh (23496B)
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 #ifndef GRAPH_PAIRPOS_GRAPH_HH 28 #define GRAPH_PAIRPOS_GRAPH_HH 29 30 #include "split-helpers.hh" 31 #include "coverage-graph.hh" 32 #include "classdef-graph.hh" 33 #include "../OT/Layout/GPOS/PairPos.hh" 34 #include "../OT/Layout/GPOS/PosLookupSubTable.hh" 35 36 namespace graph { 37 38 struct PairPosFormat1 : public OT::Layout::GPOS_impl::PairPosFormat1_3<SmallTypes> 39 { 40 bool sanitize (graph_t::vertex_t& vertex) const 41 { 42 int64_t vertex_len = vertex.obj.tail - vertex.obj.head; 43 unsigned min_size = OT::Layout::GPOS_impl::PairPosFormat1_3<SmallTypes>::min_size; 44 if (vertex_len < min_size) return false; 45 hb_barrier (); 46 47 return vertex_len >= 48 min_size + pairSet.get_size () - pairSet.len.get_size(); 49 } 50 51 hb_vector_t<unsigned> split_subtables (gsubgpos_graph_context_t& c, 52 unsigned this_index) 53 { 54 hb_set_t visited; 55 56 const unsigned coverage_id = c.graph.index_for_offset (this_index, &coverage); 57 const unsigned coverage_size = c.graph.vertices_[coverage_id].table_size (); 58 const unsigned base_size = OT::Layout::GPOS_impl::PairPosFormat1_3<SmallTypes>::min_size; 59 60 unsigned partial_coverage_size = 4; 61 unsigned accumulated = base_size; 62 hb_vector_t<unsigned> split_points; 63 for (unsigned i = 0; i < pairSet.len; i++) 64 { 65 unsigned pair_set_index = pair_set_graph_index (c, this_index, i); 66 unsigned accumulated_delta = 67 c.graph.find_subgraph_size (pair_set_index, visited) + 68 SmallTypes::size; // for PairSet offset. 69 partial_coverage_size += OT::HBUINT16::static_size; 70 71 accumulated += accumulated_delta; 72 unsigned total = accumulated + hb_min (partial_coverage_size, coverage_size); 73 74 if (total >= (1 << 16)) 75 { 76 split_points.push (i); 77 accumulated = base_size + accumulated_delta; 78 partial_coverage_size = 6; 79 visited.clear (); // node sharing isn't allowed between splits. 80 } 81 } 82 83 split_context_t split_context { 84 c, 85 this, 86 this_index, 87 }; 88 89 return actuate_subtable_split<split_context_t> (split_context, split_points); 90 } 91 92 private: 93 94 struct split_context_t { 95 gsubgpos_graph_context_t& c; 96 PairPosFormat1* thiz; 97 unsigned this_index; 98 99 unsigned original_count () 100 { 101 return thiz->pairSet.len; 102 } 103 104 unsigned clone_range (unsigned start, unsigned end) 105 { 106 return thiz->clone_range (this->c, this->this_index, start, end); 107 } 108 109 bool shrink (unsigned count) 110 { 111 return thiz->shrink (this->c, this->this_index, count); 112 } 113 }; 114 115 bool shrink (gsubgpos_graph_context_t& c, 116 unsigned this_index, 117 unsigned count) 118 { 119 DEBUG_MSG (SUBSET_REPACK, nullptr, 120 " Shrinking PairPosFormat1 (%u) to [0, %u).", 121 this_index, 122 count); 123 unsigned old_count = pairSet.len; 124 if (count >= old_count) 125 return true; 126 127 pairSet.len = count; 128 c.graph.vertices_[this_index].obj.tail -= (old_count - count) * SmallTypes::size; 129 130 auto coverage = c.graph.as_mutable_table<Coverage> (this_index, &this->coverage); 131 if (!coverage) return false; 132 133 unsigned coverage_size = coverage.vertex->table_size (); 134 auto new_coverage = 135 + hb_zip (coverage.table->iter (), hb_range ()) 136 | hb_filter ([&] (hb_pair_t<unsigned, unsigned> p) { 137 return p.second < count; 138 }) 139 | hb_map_retains_sorting (hb_first) 140 ; 141 142 return Coverage::make_coverage (c, new_coverage, coverage.index, coverage_size); 143 } 144 145 // Create a new PairPos including PairSet's from start (inclusive) to end (exclusive). 146 // Returns object id of the new object. 147 unsigned clone_range (gsubgpos_graph_context_t& c, 148 unsigned this_index, 149 unsigned start, unsigned end) const 150 { 151 DEBUG_MSG (SUBSET_REPACK, nullptr, 152 " Cloning PairPosFormat1 (%u) range [%u, %u).", this_index, start, end); 153 154 unsigned num_pair_sets = end - start; 155 unsigned prime_size = OT::Layout::GPOS_impl::PairPosFormat1_3<SmallTypes>::min_size 156 + num_pair_sets * SmallTypes::size; 157 158 unsigned pair_pos_prime_id = c.create_node (prime_size); 159 if (pair_pos_prime_id == (unsigned) -1) return -1; 160 161 PairPosFormat1* pair_pos_prime = (PairPosFormat1*) c.graph.object (pair_pos_prime_id).head; 162 pair_pos_prime->format = this->format; 163 pair_pos_prime->valueFormat[0] = this->valueFormat[0]; 164 pair_pos_prime->valueFormat[1] = this->valueFormat[1]; 165 pair_pos_prime->pairSet.len = num_pair_sets; 166 167 for (unsigned i = start; i < end; i++) 168 { 169 c.graph.move_child<> (this_index, 170 &pairSet[i], 171 pair_pos_prime_id, 172 &pair_pos_prime->pairSet[i - start]); 173 } 174 175 unsigned coverage_id = c.graph.index_for_offset (this_index, &coverage); 176 if (!Coverage::clone_coverage (c, 177 coverage_id, 178 pair_pos_prime_id, 179 2, 180 start, end)) 181 return -1; 182 183 return pair_pos_prime_id; 184 } 185 186 187 188 unsigned pair_set_graph_index (gsubgpos_graph_context_t& c, unsigned this_index, unsigned i) const 189 { 190 return c.graph.index_for_offset (this_index, &pairSet[i]); 191 } 192 }; 193 194 struct PairPosFormat2 : public OT::Layout::GPOS_impl::PairPosFormat2_4<SmallTypes> 195 { 196 bool sanitize (graph_t::vertex_t& vertex) const 197 { 198 size_t vertex_len = vertex.table_size (); 199 unsigned min_size = OT::Layout::GPOS_impl::PairPosFormat2_4<SmallTypes>::min_size; 200 if (vertex_len < min_size) return false; 201 hb_barrier (); 202 203 const unsigned class1_count = class1Count; 204 return vertex_len >= 205 min_size + class1_count * get_class1_record_size (); 206 } 207 208 hb_vector_t<unsigned> split_subtables (gsubgpos_graph_context_t& c, 209 unsigned this_index) 210 { 211 const unsigned base_size = OT::Layout::GPOS_impl::PairPosFormat2_4<SmallTypes>::min_size; 212 const unsigned class_def_2_size = size_of (c, this_index, &classDef2); 213 const Coverage* coverage = get_coverage (c, this_index); 214 const ClassDef* class_def_1 = get_class_def_1 (c, this_index); 215 auto gid_and_class = 216 + coverage->iter () 217 | hb_map_retains_sorting ([&] (hb_codepoint_t gid) { 218 return hb_codepoint_pair_t (gid, class_def_1->get_class (gid)); 219 }) 220 ; 221 class_def_size_estimator_t estimator (gid_and_class); 222 223 const unsigned class1_count = class1Count; 224 const unsigned class2_count = class2Count; 225 const unsigned class1_record_size = get_class1_record_size (); 226 227 const unsigned value_1_len = valueFormat1.get_len (); 228 const unsigned value_2_len = valueFormat2.get_len (); 229 const unsigned total_value_len = value_1_len + value_2_len; 230 231 unsigned accumulated = base_size; 232 unsigned coverage_size = 4; 233 unsigned class_def_1_size = 4; 234 unsigned max_coverage_size = coverage_size; 235 unsigned max_class_def_1_size = class_def_1_size; 236 237 hb_vector_t<unsigned> split_points; 238 239 hb_hashmap_t<unsigned, unsigned> device_tables = get_all_device_tables (c, this_index); 240 hb_vector_t<unsigned> format1_device_table_indices = valueFormat1.get_device_table_indices (); 241 hb_vector_t<unsigned> format2_device_table_indices = valueFormat2.get_device_table_indices (); 242 bool has_device_tables = bool(format1_device_table_indices) || bool(format2_device_table_indices); 243 244 hb_set_t visited; 245 for (unsigned i = 0; i < class1_count; i++) 246 { 247 unsigned accumulated_delta = class1_record_size; 248 class_def_1_size = estimator.add_class_def_size (i); 249 coverage_size = estimator.coverage_size (); 250 max_coverage_size = hb_max (max_coverage_size, coverage_size); 251 max_class_def_1_size = hb_max (max_class_def_1_size, class_def_1_size); 252 253 if (has_device_tables) { 254 for (unsigned j = 0; j < class2_count; j++) 255 { 256 unsigned value1_index = total_value_len * (class2_count * i + j); 257 unsigned value2_index = value1_index + value_1_len; 258 accumulated_delta += size_of_value_record_children (c, 259 device_tables, 260 format1_device_table_indices, 261 value1_index, 262 visited); 263 accumulated_delta += size_of_value_record_children (c, 264 device_tables, 265 format2_device_table_indices, 266 value2_index, 267 visited); 268 } 269 } 270 271 accumulated += accumulated_delta; 272 unsigned total = accumulated 273 + coverage_size + class_def_1_size + class_def_2_size 274 // The largest object will pack last and can exceed the size limit. 275 - hb_max (hb_max (coverage_size, class_def_1_size), class_def_2_size); 276 if (total >= (1 << 16)) 277 { 278 split_points.push (i); 279 // split does not include i, so add the size for i when we reset the size counters. 280 accumulated = base_size + accumulated_delta; 281 282 estimator.reset(); 283 class_def_1_size = estimator.add_class_def_size(i); 284 coverage_size = estimator.coverage_size(); 285 visited.clear (); // node sharing isn't allowed between splits. 286 } 287 } 288 289 split_context_t split_context { 290 c, 291 this, 292 this_index, 293 class1_record_size, 294 total_value_len, 295 value_1_len, 296 value_2_len, 297 max_coverage_size, 298 max_class_def_1_size, 299 device_tables, 300 format1_device_table_indices, 301 format2_device_table_indices 302 }; 303 304 return actuate_subtable_split<split_context_t> (split_context, split_points); 305 } 306 private: 307 308 struct split_context_t 309 { 310 gsubgpos_graph_context_t& c; 311 PairPosFormat2* thiz; 312 unsigned this_index; 313 unsigned class1_record_size; 314 unsigned value_record_len; 315 unsigned value1_record_len; 316 unsigned value2_record_len; 317 unsigned max_coverage_size; 318 unsigned max_class_def_size; 319 320 const hb_hashmap_t<unsigned, unsigned>& device_tables; 321 const hb_vector_t<unsigned>& format1_device_table_indices; 322 const hb_vector_t<unsigned>& format2_device_table_indices; 323 324 unsigned original_count () 325 { 326 return thiz->class1Count; 327 } 328 329 unsigned clone_range (unsigned start, unsigned end) 330 { 331 return thiz->clone_range (*this, start, end); 332 } 333 334 bool shrink (unsigned count) 335 { 336 return thiz->shrink (*this, count); 337 } 338 }; 339 340 size_t get_class1_record_size () const 341 { 342 const size_t class2_count = class2Count; 343 return 344 class2_count * (valueFormat1.get_size () + valueFormat2.get_size ()); 345 } 346 347 unsigned clone_range (split_context_t& split_context, 348 unsigned start, unsigned end) const 349 { 350 DEBUG_MSG (SUBSET_REPACK, nullptr, 351 " Cloning PairPosFormat2 (%u) range [%u, %u).", split_context.this_index, start, end); 352 353 graph_t& graph = split_context.c.graph; 354 355 unsigned num_records = end - start; 356 unsigned prime_size = OT::Layout::GPOS_impl::PairPosFormat2_4<SmallTypes>::min_size 357 + num_records * split_context.class1_record_size; 358 359 unsigned pair_pos_prime_id = split_context.c.create_node (prime_size); 360 if (pair_pos_prime_id == (unsigned) -1) return -1; 361 362 PairPosFormat2* pair_pos_prime = 363 (PairPosFormat2*) graph.object (pair_pos_prime_id).head; 364 pair_pos_prime->format = this->format; 365 pair_pos_prime->valueFormat1 = this->valueFormat1; 366 pair_pos_prime->valueFormat2 = this->valueFormat2; 367 pair_pos_prime->class1Count = num_records; 368 pair_pos_prime->class2Count = this->class2Count; 369 clone_class1_records (split_context, 370 pair_pos_prime_id, 371 start, 372 end); 373 374 unsigned coverage_id = 375 graph.index_for_offset (split_context.this_index, &coverage); 376 unsigned class_def_1_id = 377 graph.index_for_offset (split_context.this_index, &classDef1); 378 auto& coverage_v = graph.vertices_[coverage_id]; 379 auto& class_def_1_v = graph.vertices_[class_def_1_id]; 380 Coverage* coverage_table = (Coverage*) coverage_v.obj.head; 381 ClassDef* class_def_1_table = (ClassDef*) class_def_1_v.obj.head; 382 if (!coverage_table 383 || !coverage_table->sanitize (coverage_v) 384 || !class_def_1_table 385 || !class_def_1_table->sanitize (class_def_1_v)) 386 return -1; 387 388 auto klass_map = 389 + coverage_table->iter () 390 | hb_map_retains_sorting ([&] (hb_codepoint_t gid) { 391 return hb_codepoint_pair_t (gid, class_def_1_table->get_class (gid)); 392 }) 393 | hb_filter ([&] (hb_codepoint_t klass) { 394 return klass >= start && klass < end; 395 }, hb_second) 396 | hb_map_retains_sorting ([&] (hb_codepoint_pair_t gid_and_class) { 397 // Classes must be from 0...N so subtract start 398 return hb_codepoint_pair_t (gid_and_class.first, gid_and_class.second - start); 399 }) 400 ; 401 402 if (!Coverage::add_coverage (split_context.c, 403 pair_pos_prime_id, 404 2, 405 + klass_map | hb_map_retains_sorting (hb_first), 406 split_context.max_coverage_size)) 407 return -1; 408 409 // classDef1 410 if (!ClassDef::add_class_def (split_context.c, 411 pair_pos_prime_id, 412 8, 413 + klass_map, 414 split_context.max_class_def_size)) 415 return -1; 416 417 // classDef2 418 unsigned class_def_2_id = 419 graph.index_for_offset (split_context.this_index, &classDef2); 420 auto* class_def_link = graph.vertices_[pair_pos_prime_id].obj.real_links.push (); 421 class_def_link->width = SmallTypes::size; 422 class_def_link->objidx = class_def_2_id; 423 class_def_link->position = 10; 424 graph.vertices_[class_def_2_id].add_parent (pair_pos_prime_id, false); 425 graph.duplicate (pair_pos_prime_id, class_def_2_id); 426 427 return pair_pos_prime_id; 428 } 429 430 void clone_class1_records (split_context_t& split_context, 431 unsigned pair_pos_prime_id, 432 unsigned start, unsigned end) const 433 { 434 PairPosFormat2* pair_pos_prime = 435 (PairPosFormat2*) split_context.c.graph.object (pair_pos_prime_id).head; 436 437 char* start_addr = ((char*)&values[0]) + start * split_context.class1_record_size; 438 unsigned num_records = end - start; 439 hb_memcpy (&pair_pos_prime->values[0], 440 start_addr, 441 num_records * split_context.class1_record_size); 442 443 if (!split_context.format1_device_table_indices 444 && !split_context.format2_device_table_indices) 445 // No device tables to move over. 446 return; 447 448 unsigned class2_count = class2Count; 449 for (unsigned i = start; i < end; i++) 450 { 451 for (unsigned j = 0; j < class2_count; j++) 452 { 453 unsigned value1_index = split_context.value_record_len * (class2_count * i + j); 454 unsigned value2_index = value1_index + split_context.value1_record_len; 455 456 unsigned new_value1_index = split_context.value_record_len * (class2_count * (i - start) + j); 457 unsigned new_value2_index = new_value1_index + split_context.value1_record_len; 458 459 transfer_device_tables (split_context, 460 pair_pos_prime_id, 461 split_context.format1_device_table_indices, 462 value1_index, 463 new_value1_index); 464 465 transfer_device_tables (split_context, 466 pair_pos_prime_id, 467 split_context.format2_device_table_indices, 468 value2_index, 469 new_value2_index); 470 } 471 } 472 } 473 474 void transfer_device_tables (split_context_t& split_context, 475 unsigned pair_pos_prime_id, 476 const hb_vector_t<unsigned>& device_table_indices, 477 unsigned old_value_record_index, 478 unsigned new_value_record_index) const 479 { 480 PairPosFormat2* pair_pos_prime = 481 (PairPosFormat2*) split_context.c.graph.object (pair_pos_prime_id).head; 482 483 for (unsigned i : device_table_indices) 484 { 485 OT::Offset16* record = (OT::Offset16*) &values[old_value_record_index + i]; 486 unsigned record_position = ((char*) record) - ((char*) this); 487 if (!split_context.device_tables.has (record_position)) continue; 488 489 split_context.c.graph.move_child ( 490 split_context.this_index, 491 record, 492 pair_pos_prime_id, 493 (OT::Offset16*) &pair_pos_prime->values[new_value_record_index + i]); 494 } 495 } 496 497 bool shrink (split_context_t& split_context, 498 unsigned count) 499 { 500 DEBUG_MSG (SUBSET_REPACK, nullptr, 501 " Shrinking PairPosFormat2 (%u) to [0, %u).", 502 split_context.this_index, 503 count); 504 unsigned old_count = class1Count; 505 if (count >= old_count) 506 return true; 507 508 graph_t& graph = split_context.c.graph; 509 class1Count = count; 510 graph.vertices_[split_context.this_index].obj.tail -= 511 (old_count - count) * split_context.class1_record_size; 512 513 auto coverage = 514 graph.as_mutable_table<Coverage> (split_context.this_index, &this->coverage); 515 if (!coverage) return false; 516 517 auto class_def_1 = 518 graph.as_mutable_table<ClassDef> (split_context.this_index, &classDef1); 519 if (!class_def_1) return false; 520 521 auto klass_map = 522 + coverage.table->iter () 523 | hb_map_retains_sorting ([&] (hb_codepoint_t gid) { 524 return hb_codepoint_pair_t (gid, class_def_1.table->get_class (gid)); 525 }) 526 | hb_filter ([&] (hb_codepoint_t klass) { 527 return klass < count; 528 }, hb_second) 529 ; 530 531 auto new_coverage = + klass_map | hb_map_retains_sorting (hb_first); 532 if (!Coverage::make_coverage (split_context.c, 533 + new_coverage, 534 coverage.index, 535 // existing ranges my not be kept, worst case size is a format 1 536 // coverage table. 537 4 + new_coverage.len() * 2)) 538 return false; 539 540 return ClassDef::make_class_def (split_context.c, 541 + klass_map, 542 class_def_1.index, 543 class_def_1.vertex->table_size ()); 544 } 545 546 hb_hashmap_t<unsigned, unsigned> 547 get_all_device_tables (gsubgpos_graph_context_t& c, 548 unsigned this_index) const 549 { 550 const auto& v = c.graph.vertices_[this_index]; 551 return v.position_to_index_map (); 552 } 553 554 const Coverage* get_coverage (gsubgpos_graph_context_t& c, 555 unsigned this_index) const 556 { 557 unsigned coverage_id = c.graph.index_for_offset (this_index, &coverage); 558 auto& coverage_v = c.graph.vertices_[coverage_id]; 559 560 Coverage* coverage_table = (Coverage*) coverage_v.obj.head; 561 if (!coverage_table || !coverage_table->sanitize (coverage_v)) 562 return &Null(Coverage); 563 return coverage_table; 564 } 565 566 const ClassDef* get_class_def_1 (gsubgpos_graph_context_t& c, 567 unsigned this_index) const 568 { 569 unsigned class_def_1_id = c.graph.index_for_offset (this_index, &classDef1); 570 auto& class_def_1_v = c.graph.vertices_[class_def_1_id]; 571 572 ClassDef* class_def_1_table = (ClassDef*) class_def_1_v.obj.head; 573 if (!class_def_1_table || !class_def_1_table->sanitize (class_def_1_v)) 574 return &Null(ClassDef); 575 return class_def_1_table; 576 } 577 578 unsigned size_of_value_record_children (gsubgpos_graph_context_t& c, 579 const hb_hashmap_t<unsigned, unsigned>& device_tables, 580 const hb_vector_t<unsigned> device_table_indices, 581 unsigned value_record_index, 582 hb_set_t& visited) 583 { 584 unsigned size = 0; 585 for (unsigned i : device_table_indices) 586 { 587 OT::Layout::GPOS_impl::Value* record = &values[value_record_index + i]; 588 unsigned record_position = ((char*) record) - ((char*) this); 589 unsigned* obj_idx; 590 if (!device_tables.has (record_position, &obj_idx)) continue; 591 size += c.graph.find_subgraph_size (*obj_idx, visited); 592 } 593 return size; 594 } 595 596 unsigned size_of (gsubgpos_graph_context_t& c, 597 unsigned this_index, 598 const void* offset) const 599 { 600 const unsigned id = c.graph.index_for_offset (this_index, offset); 601 return c.graph.vertices_[id].table_size (); 602 } 603 }; 604 605 struct PairPos : public OT::Layout::GPOS_impl::PairPos 606 { 607 hb_vector_t<unsigned> split_subtables (gsubgpos_graph_context_t& c, 608 unsigned this_index) 609 { 610 switch (u.format.v) { 611 case 1: 612 return ((PairPosFormat1*)(&u.format1))->split_subtables (c, this_index); 613 case 2: 614 return ((PairPosFormat2*)(&u.format2))->split_subtables (c, this_index); 615 #ifndef HB_NO_BEYOND_64K 616 case 3: HB_FALLTHROUGH; 617 case 4: HB_FALLTHROUGH; 618 // Don't split 24bit PairPos's. 619 #endif 620 default: 621 return hb_vector_t<unsigned> (); 622 } 623 } 624 625 bool sanitize (graph_t::vertex_t& vertex) const 626 { 627 int64_t vertex_len = vertex.obj.tail - vertex.obj.head; 628 if (vertex_len < u.format.v.get_size ()) return false; 629 hb_barrier (); 630 631 switch (u.format.v) { 632 case 1: 633 return ((PairPosFormat1*)(&u.format1))->sanitize (vertex); 634 case 2: 635 return ((PairPosFormat2*)(&u.format2))->sanitize (vertex); 636 #ifndef HB_NO_BEYOND_64K 637 case 3: HB_FALLTHROUGH; 638 case 4: HB_FALLTHROUGH; 639 #endif 640 default: 641 // We don't handle format 3 and 4 here. 642 return false; 643 } 644 } 645 }; 646 647 } 648 649 #endif // GRAPH_PAIRPOS_GRAPH_HH