src/graph/markbasepos-graph.hh

   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_MARKBASEPOS_GRAPH_HH
  28 #define GRAPH_MARKBASEPOS_GRAPH_HH
  29
  30 #include "split-helpers.hh"
  31 #include "coverage-graph.hh"
  32 #include "../OT/Layout/GPOS/MarkBasePos.hh"
  33 #include "../OT/Layout/GPOS/PosLookupSubTable.hh"
  34
  35 namespace graph {
  36
  37 struct AnchorMatrix : public OT::Layout::GPOS_impl::AnchorMatrix
  38 {
  39   bool sanitize (graph_t::vertex_t& vertex, unsigned class_count) const
  40   {
  41     int64_t vertex_len = vertex.obj.tail - vertex.obj.head;
  42     if (vertex_len < AnchorMatrix::min_size) return false;
  43
  44     return vertex_len >= AnchorMatrix::min_size +
  45         OT::Offset16::static_size * class_count * this->rows;
  46   }
  47
  48   bool shrink (gsubgpos_graph_context_t& c,
  49                unsigned this_index,
  50                unsigned old_class_count,
  51                unsigned new_class_count)
  52   {
  53     if (new_class_count >= old_class_count) return false;
  54     auto& o = c.graph.vertices_[this_index].obj;
  55     unsigned base_count = rows;
  56     o.tail = o.head +
  57              AnchorMatrix::min_size +
  58              OT::Offset16::static_size * base_count * new_class_count;
  59
  60     // Reposition links into the new indexing scheme.
  61     for (auto& link : o.real_links.writer ())
  62     {
  63       unsigned index = (link.position - 2) / 2;
  64       unsigned base = index / old_class_count;
  65       unsigned klass = index % old_class_count;
  66       if (klass >= new_class_count)
  67         // should have already been removed
  68         return false;
  69
  70       unsigned new_index = base * new_class_count + klass;
  71
  72       link.position = (char*) &(this->matrixZ[new_index]) - (char*) this;
  73     }
  74
  75     return true;
  76   }
  77
  78   unsigned clone (gsubgpos_graph_context_t& c,
  79                   unsigned this_index,
  80                   unsigned start,
  81                   unsigned end,
  82                   unsigned class_count)
  83   {
  84     unsigned base_count = rows;
  85     unsigned new_class_count = end - start;
  86     unsigned size = AnchorMatrix::min_size +
  87                     OT::Offset16::static_size * new_class_count * rows;
  88     unsigned prime_id = c.create_node (size);
  89     if (prime_id == (unsigned) -1) return -1;
  90     AnchorMatrix* prime = (AnchorMatrix*) c.graph.object (prime_id).head;
  91     prime->rows = base_count;
  92
  93     auto& o = c.graph.vertices_[this_index].obj;
  94     int num_links = o.real_links.length;
  95     for (int i = 0; i < num_links; i++)
  96     {
  97       const auto& link = o.real_links[i];
  98       unsigned old_index = (link.position - 2) / OT::Offset16::static_size;
  99       unsigned klass = old_index % class_count;
 100       if (klass < start || klass >= end) continue;
 101
 102       unsigned base = old_index / class_count;
 103       unsigned new_klass = klass - start;
 104       unsigned new_index = base * new_class_count + new_klass;
 105
 106
 107       unsigned child_idx = link.objidx;
 108       c.graph.add_link (&(prime->matrixZ[new_index]),
 109                         prime_id,
 110                         child_idx);
 111
 112       auto& child = c.graph.vertices_[child_idx];
 113       child.remove_parent (this_index);
 114
 115       o.real_links.remove_unordered (i);
 116       num_links--;
 117       i--;
 118     }
 119
 120     return prime_id;
 121   }
 122 };
 123
 124 struct MarkArray : public OT::Layout::GPOS_impl::MarkArray
 125 {
 126   bool sanitize (graph_t::vertex_t& vertex) const
 127   {
 128     int64_t vertex_len = vertex.obj.tail - vertex.obj.head;
 129     unsigned min_size = MarkArray::min_size;
 130     if (vertex_len < min_size) return false;
 131
 132     return vertex_len >= get_size ();
 133   }
 134
 135   bool shrink (gsubgpos_graph_context_t& c,
 136                const hb_hashmap_t<unsigned, unsigned>& mark_array_links,
 137                unsigned this_index,
 138                unsigned new_class_count)
 139   {
 140     auto& o = c.graph.vertices_[this_index].obj;
 141     for (const auto& link : o.real_links)
 142       c.graph.vertices_[link.objidx].remove_parent (this_index);
 143     o.real_links.reset ();
 144
 145     unsigned new_index = 0;
 146     for (const auto& record : this->iter ())
 147     {
 148       unsigned klass = record.klass;
 149       if (klass >= new_class_count) continue;
 150
 151       (*this)[new_index].klass = klass;
 152       unsigned position = (char*) &record.markAnchor - (char*) this;
 153       unsigned* objidx;
 154       if (!mark_array_links.has (position, &objidx))
 155       {
 156         new_index++;
 157         continue;
 158       }
 159
 160       c.graph.add_link (&(*this)[new_index].markAnchor, this_index, *objidx);
 161       new_index++;
 162     }
 163
 164     this->len = new_index;
 165     o.tail = o.head + MarkArray::min_size +
 166              OT::Layout::GPOS_impl::MarkRecord::static_size * new_index;
 167     return true;
 168   }
 169
 170   unsigned clone (gsubgpos_graph_context_t& c,
 171                   unsigned this_index,
 172                   const hb_hashmap_t<unsigned, unsigned>& pos_to_index,
 173                   hb_set_t& marks,
 174                   unsigned start_class)
 175   {
 176     unsigned size = MarkArray::min_size +
 177                     OT::Layout::GPOS_impl::MarkRecord::static_size *
 178                     marks.get_population ();
 179     unsigned prime_id = c.create_node (size);
 180     if (prime_id == (unsigned) -1) return -1;
 181     MarkArray* prime = (MarkArray*) c.graph.object (prime_id).head;
 182     prime->len = marks.get_population ();
 183
 184
 185     unsigned i = 0;
 186     for (hb_codepoint_t mark : marks)
 187     {
 188       (*prime)[i].klass = (*this)[mark].klass - start_class;
 189       unsigned offset_pos = (char*) &((*this)[mark].markAnchor) - (char*) this;
 190       unsigned* anchor_index;
 191       if (pos_to_index.has (offset_pos, &anchor_index))
 192         c.graph.move_child (this_index,
 193                             &((*this)[mark].markAnchor),
 194                             prime_id,
 195                             &((*prime)[i].markAnchor));
 196
 197       i++;
 198     }
 199
 200     return prime_id;
 201   }
 202 };
 203
 204 struct MarkBasePosFormat1 : public OT::Layout::GPOS_impl::MarkBasePosFormat1_2<SmallTypes>
 205 {
 206   bool sanitize (graph_t::vertex_t& vertex) const
 207   {
 208     int64_t vertex_len = vertex.obj.tail - vertex.obj.head;
 209     return vertex_len >= MarkBasePosFormat1::static_size;
 210   }
 211
 212   hb_vector_t<unsigned> split_subtables (gsubgpos_graph_context_t& c,
 213                                          unsigned parent_index,
 214                                          unsigned this_index)
 215   {
 216     hb_set_t visited;
 217
 218     const unsigned base_coverage_id = c.graph.index_for_offset (this_index, &baseCoverage);
 219     const unsigned base_size =
 220         OT::Layout::GPOS_impl::MarkBasePosFormat1_2<SmallTypes>::min_size +
 221         MarkArray::min_size +
 222         AnchorMatrix::min_size +
 223         c.graph.vertices_[base_coverage_id].table_size ();
 224
 225     hb_vector_t<class_info_t> class_to_info = get_class_info (c, this_index);
 226
 227     unsigned class_count = classCount;
 228     auto base_array = c.graph.as_table<AnchorMatrix> (this_index,
 229                                                       &baseArray,
 230                                                       class_count);
 231     if (!base_array) return hb_vector_t<unsigned> ();
 232     unsigned base_count = base_array.table->rows;
 233
 234     unsigned partial_coverage_size = 4;
 235     unsigned accumulated = base_size;
 236     hb_vector_t<unsigned> split_points;
 237
 238     for (unsigned klass = 0; klass < class_count; klass++)
 239     {
 240       class_info_t& info = class_to_info[klass];
 241       partial_coverage_size += OT::HBUINT16::static_size * info.marks.get_population ();
 242       unsigned accumulated_delta =
 243           OT::Layout::GPOS_impl::MarkRecord::static_size * info.marks.get_population () +
 244           OT::Offset16::static_size * base_count;
 245
 246       for (unsigned objidx : info.child_indices)
 247         accumulated_delta += c.graph.find_subgraph_size (objidx, visited);
 248
 249       accumulated += accumulated_delta;
 250       unsigned total = accumulated + partial_coverage_size;
 251
 252       if (total >= (1 << 16))
 253       {
 254         split_points.push (klass);
 255         accumulated = base_size + accumulated_delta;
 256         partial_coverage_size = 4 + OT::HBUINT16::static_size * info.marks.get_population ();
 257         visited.clear (); // node sharing isn't allowed between splits.
 258       }
 259     }
 260
 261
 262     const unsigned mark_array_id = c.graph.index_for_offset (this_index, &markArray);
 263     split_context_t split_context {
 264       c,
 265       this,
 266       c.graph.duplicate_if_shared (parent_index, this_index),
 267       std::move (class_to_info),
 268       c.graph.vertices_[mark_array_id].position_to_index_map (),
 269     };
 270
 271     return actuate_subtable_split<split_context_t> (split_context, split_points);
 272   }
 273
 274  private:
 275
 276   struct class_info_t {
 277     hb_set_t marks;
 278     hb_vector_t<unsigned> child_indices;
 279   };
 280
 281   struct split_context_t {
 282     gsubgpos_graph_context_t& c;
 283     MarkBasePosFormat1* thiz;
 284     unsigned this_index;
 285     hb_vector_t<class_info_t> class_to_info;
 286     hb_hashmap_t<unsigned, unsigned> mark_array_links;
 287
 288     hb_set_t marks_for (unsigned start, unsigned end)
 289     {
 290       hb_set_t marks;
 291       for (unsigned klass = start; klass < end; klass++)
 292       {
 293         + class_to_info[klass].marks.iter ()
 294         | hb_sink (marks)
 295         ;
 296       }
 297       return marks;
 298     }
 299
 300     unsigned original_count ()
 301     {
 302       return thiz->classCount;
 303     }
 304
 305     unsigned clone_range (unsigned start, unsigned end)
 306     {
 307       return thiz->clone_range (*this, this->this_index, start, end);
 308     }
 309
 310     bool shrink (unsigned count)
 311     {
 312       return thiz->shrink (*this, this->this_index, count);
 313     }
 314   };
 315
 316   hb_vector_t<class_info_t> get_class_info (gsubgpos_graph_context_t& c,
 317                                             unsigned this_index)
 318   {
 319     hb_vector_t<class_info_t> class_to_info;
 320
 321     unsigned class_count = classCount;
 322     if (!class_count) return class_to_info;
 323
 324     if (!class_to_info.resize (class_count))
 325       return hb_vector_t<class_info_t>();
 326
 327     auto mark_array = c.graph.as_table<MarkArray> (this_index, &markArray);
 328     if (!mark_array) return hb_vector_t<class_info_t> ();
 329     unsigned mark_count = mark_array.table->len;
 330     for (unsigned mark = 0; mark < mark_count; mark++)
 331     {
 332       unsigned klass = (*mark_array.table)[mark].get_class ();
 333       if (klass >= class_count) continue;
 334       class_to_info[klass].marks.add (mark);
 335     }
 336
 337     for (const auto& link : mark_array.vertex->obj.real_links)
 338     {
 339       unsigned mark = (link.position - 2) /
 340                      OT::Layout::GPOS_impl::MarkRecord::static_size;
 341       unsigned klass = (*mark_array.table)[mark].get_class ();
 342       if (klass >= class_count) continue;
 343       class_to_info[klass].child_indices.push (link.objidx);
 344     }
 345
 346     unsigned base_array_id =
 347         c.graph.index_for_offset (this_index, &baseArray);
 348     auto& base_array_v = c.graph.vertices_[base_array_id];
 349
 350     for (const auto& link : base_array_v.obj.real_links)
 351     {
 352       unsigned index = (link.position - 2) / OT::Offset16::static_size;
 353       unsigned klass = index % class_count;
 354       class_to_info[klass].child_indices.push (link.objidx);
 355     }
 356
 357     return class_to_info;
 358   }
 359
 360   bool shrink (split_context_t& sc,
 361                unsigned this_index,
 362                unsigned count)
 363   {
 364     DEBUG_MSG (SUBSET_REPACK, nullptr,
 365                "  Shrinking MarkBasePosFormat1 (%u) to [0, %u).",
 366                this_index,
 367                count);
 368
 369     unsigned old_count = classCount;
 370     if (count >= old_count)
 371       return true;
 372
 373     classCount = count;
 374
 375     auto mark_coverage = sc.c.graph.as_mutable_table<Coverage> (this_index,
 376                                                                 &markCoverage);
 377     if (!mark_coverage) return false;
 378     hb_set_t marks = sc.marks_for (0, count);
 379     auto new_coverage =
 380         + hb_enumerate (mark_coverage.table->iter ())
 381         | hb_filter (marks, hb_first)
 382         | hb_map_retains_sorting (hb_second)
 383         ;
 384     if (!Coverage::make_coverage (sc.c, + new_coverage,
 385                                   mark_coverage.index,
 386                                   4 + 2 * marks.get_population ()))
 387       return false;
 388
 389
 390     auto base_array = sc.c.graph.as_mutable_table<AnchorMatrix> (this_index,
 391                                                                  &baseArray,
 392                                                                  old_count);
 393     if (!base_array || !base_array.table->shrink (sc.c,
 394                                                   base_array.index,
 395                                                   old_count,
 396                                                   count))
 397       return false;
 398
 399     auto mark_array = sc.c.graph.as_mutable_table<MarkArray> (this_index,
 400                                                               &markArray);
 401     if (!mark_array || !mark_array.table->shrink (sc.c,
 402                                                   sc.mark_array_links,
 403                                                   mark_array.index,
 404                                                   count))
 405       return false;
 406
 407     return true;
 408   }
 409
 410   // Create a new MarkBasePos that has all of the data for classes from [start, end).
 411   unsigned clone_range (split_context_t& sc,
 412                         unsigned this_index,
 413                         unsigned start, unsigned end) const
 414   {
 415     DEBUG_MSG (SUBSET_REPACK, nullptr,
 416                "  Cloning MarkBasePosFormat1 (%u) range [%u, %u).", this_index, start, end);
 417
 418     graph_t& graph = sc.c.graph;
 419     unsigned prime_size = OT::Layout::GPOS_impl::MarkBasePosFormat1_2<SmallTypes>::static_size;
 420
 421     unsigned prime_id = sc.c.create_node (prime_size);
 422     if (prime_id == (unsigned) -1) return -1;
 423
 424     MarkBasePosFormat1* prime = (MarkBasePosFormat1*) graph.object (prime_id).head;
 425     prime->format = this->format;
 426     unsigned new_class_count = end - start;
 427     prime->classCount = new_class_count;
 428
 429     unsigned base_coverage_id =
 430         graph.index_for_offset (sc.this_index, &baseCoverage);
 431     graph.add_link (&(prime->baseCoverage), prime_id, base_coverage_id);
 432     graph.duplicate (prime_id, base_coverage_id);
 433
 434     auto mark_coverage = sc.c.graph.as_table<Coverage> (this_index,
 435                                                         &markCoverage);
 436     if (!mark_coverage) return false;
 437     hb_set_t marks = sc.marks_for (start, end);
 438     auto new_coverage =
 439         + hb_enumerate (mark_coverage.table->iter ())
 440         | hb_filter (marks, hb_first)
 441         | hb_map_retains_sorting (hb_second)
 442         ;
 443     if (!Coverage::add_coverage (sc.c,
 444                                  prime_id,
 445                                  2,
 446                                  + new_coverage,
 447                                  marks.get_population () * 2 + 4))
 448       return -1;
 449
 450     auto mark_array =
 451         graph.as_table <MarkArray> (sc.this_index, &markArray);
 452     if (!mark_array) return -1;
 453     unsigned new_mark_array =
 454         mark_array.table->clone (sc.c,
 455                                  mark_array.index,
 456                                  sc.mark_array_links,
 457                                  marks,
 458                                  start);
 459     graph.add_link (&(prime->markArray), prime_id, new_mark_array);
 460
 461     unsigned class_count = classCount;
 462     auto base_array =
 463         graph.as_table<AnchorMatrix> (sc.this_index, &baseArray, class_count);
 464     if (!base_array) return -1;
 465     unsigned new_base_array =
 466         base_array.table->clone (sc.c,
 467                                  base_array.index,
 468                                  start, end, this->classCount);
 469     graph.add_link (&(prime->baseArray), prime_id, new_base_array);
 470
 471     return prime_id;
 472   }
 473 };
 474
 475
 476 struct MarkBasePos : public OT::Layout::GPOS_impl::MarkBasePos
 477 {
 478   hb_vector_t<unsigned> split_subtables (gsubgpos_graph_context_t& c,
 479                                          unsigned parent_index,
 480                                          unsigned this_index)
 481   {
 482     switch (u.format) {
 483     case 1:
 484       return ((MarkBasePosFormat1*)(&u.format1))->split_subtables (c, parent_index, this_index);
 485 #ifndef HB_NO_BEYOND_64K
 486     case 2: HB_FALLTHROUGH;
 487       // Don't split 24bit MarkBasePos's.
 488 #endif
 489     default:
 490       return hb_vector_t<unsigned> ();
 491     }
 492   }
 493
 494   bool sanitize (graph_t::vertex_t& vertex) const
 495   {
 496     int64_t vertex_len = vertex.obj.tail - vertex.obj.head;
 497     if (vertex_len < u.format.get_size ()) return false;
 498
 499     switch (u.format) {
 500     case 1:
 501       return ((MarkBasePosFormat1*)(&u.format1))->sanitize (vertex);
 502 #ifndef HB_NO_BEYOND_64K
 503     case 2: HB_FALLTHROUGH;
 504 #endif
 505     default:
 506       // We don't handle format 3 and 4 here.
 507       return false;
 508     }
 509   }
 510 };
 511
 512
 513 }
 514
 515 #endif  // GRAPH_MARKBASEPOS_GRAPH_HH