src/graph/classdef-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 #include "graph.hh"
  28 #include "../hb-ot-layout-common.hh"
  29
  30 #ifndef GRAPH_CLASSDEF_GRAPH_HH
  31 #define GRAPH_CLASSDEF_GRAPH_HH
  32
  33 namespace graph {
  34
  35 struct ClassDefFormat1 : public OT::ClassDefFormat1_3<SmallTypes>
  36 {
  37   bool sanitize (graph_t::vertex_t& vertex) const
  38   {
  39     int64_t vertex_len = vertex.obj.tail - vertex.obj.head;
  40     constexpr unsigned min_size = OT::ClassDefFormat1_3<SmallTypes>::min_size;
  41     if (vertex_len < min_size) return false;
  42     return vertex_len >= min_size + classValue.get_size () - classValue.len.get_size ();
  43   }
  44 };
  45
  46 struct ClassDefFormat2 : public OT::ClassDefFormat2_4<SmallTypes>
  47 {
  48   bool sanitize (graph_t::vertex_t& vertex) const
  49   {
  50     int64_t vertex_len = vertex.obj.tail - vertex.obj.head;
  51     constexpr unsigned min_size = OT::ClassDefFormat2_4<SmallTypes>::min_size;
  52     if (vertex_len < min_size) return false;
  53     return vertex_len >= min_size + rangeRecord.get_size () - rangeRecord.len.get_size ();
  54   }
  55 };
  56
  57 struct ClassDef : public OT::ClassDef
  58 {
  59   template<typename It>
  60   static bool add_class_def (gsubgpos_graph_context_t& c,
  61                              unsigned parent_id,
  62                              unsigned link_position,
  63                              It glyph_and_class,
  64                              unsigned max_size)
  65   {
  66     unsigned class_def_prime_id = c.graph.new_node (nullptr, nullptr);
  67     auto& class_def_prime_vertex = c.graph.vertices_[class_def_prime_id];
  68     if (!make_class_def (c, glyph_and_class, class_def_prime_id, max_size))
  69       return false;
  70
  71     auto* class_def_link = c.graph.vertices_[parent_id].obj.real_links.push ();
  72     class_def_link->width = SmallTypes::size;
  73     class_def_link->objidx = class_def_prime_id;
  74     class_def_link->position = link_position;
  75     class_def_prime_vertex.add_parent (parent_id);
  76
  77     return true;
  78   }
  79
  80   template<typename It>
  81   static bool make_class_def (gsubgpos_graph_context_t& c,
  82                               It glyph_and_class,
  83                               unsigned dest_obj,
  84                               unsigned max_size)
  85   {
  86     char* buffer = (char*) hb_calloc (1, max_size);
  87     hb_serialize_context_t serializer (buffer, max_size);
  88     OT::ClassDef_serialize (&serializer, glyph_and_class);
  89     serializer.end_serialize ();
  90     if (serializer.in_error ())
  91     {
  92       hb_free (buffer);
  93       return false;
  94     }
  95
  96     hb_bytes_t class_def_copy = serializer.copy_bytes ();
  97     if (!class_def_copy.arrayZ) return false;
  98     // Give ownership to the context, it will cleanup the buffer.
  99     if (!c.add_buffer ((char *) class_def_copy.arrayZ))
 100     {
 101       hb_free ((char *) class_def_copy.arrayZ);
 102       return false;
 103     }
 104
 105     auto& obj = c.graph.vertices_[dest_obj].obj;
 106     obj.head = (char *) class_def_copy.arrayZ;
 107     obj.tail = obj.head + class_def_copy.length;
 108
 109     hb_free (buffer);
 110     return true;
 111   }
 112
 113   bool sanitize (graph_t::vertex_t& vertex) const
 114   {
 115     int64_t vertex_len = vertex.obj.tail - vertex.obj.head;
 116     if (vertex_len < OT::ClassDef::min_size) return false;
 117     switch (u.format)
 118     {
 119     case 1: return ((ClassDefFormat1*)this)->sanitize (vertex);
 120     case 2: return ((ClassDefFormat2*)this)->sanitize (vertex);
 121 #ifndef HB_NO_BEYOND_64K
 122     // Not currently supported
 123     case 3:
 124     case 4:
 125 #endif
 126     default: return false;
 127     }
 128   }
 129 };
 130
 131
 132 struct class_def_size_estimator_t
 133 {
 134   template<typename It>
 135   class_def_size_estimator_t (It glyph_and_class)
 136       : gids_consecutive (true), num_ranges_per_class (), glyphs_per_class ()
 137   {
 138     unsigned last_gid = (unsigned) -1;
 139     for (auto p : + glyph_and_class)
 140     {
 141       unsigned gid = p.first;
 142       unsigned klass = p.second;
 143
 144       if (last_gid != (unsigned) -1 && gid != last_gid + 1)
 145         gids_consecutive = false;
 146       last_gid = gid;
 147
 148       hb_set_t* glyphs;
 149       if (glyphs_per_class.has (klass, &glyphs) && glyphs) {
 150         glyphs->add (gid);
 151         continue;
 152       }
 153
 154       hb_set_t new_glyphs;
 155       new_glyphs.add (gid);
 156       glyphs_per_class.set (klass, std::move (new_glyphs));
 157     }
 158
 159     if (in_error ()) return;
 160
 161     for (unsigned klass : glyphs_per_class.keys ())
 162     {
 163       if (!klass) continue; // class 0 doesn't get encoded.
 164
 165       const hb_set_t& glyphs = glyphs_per_class.get (klass);
 166       hb_codepoint_t start = HB_SET_VALUE_INVALID;
 167       hb_codepoint_t end = HB_SET_VALUE_INVALID;
 168
 169       unsigned count = 0;
 170       while (glyphs.next_range (&start, &end))
 171         count++;
 172
 173       num_ranges_per_class.set (klass, count);
 174     }
 175   }
 176
 177   // Incremental increase in the Coverage and ClassDef table size
 178   // (worst case) if all glyphs associated with 'klass' were added.
 179   unsigned incremental_coverage_size (unsigned klass) const
 180   {
 181     // Coverage takes 2 bytes per glyph worst case,
 182     return 2 * glyphs_per_class.get (klass).get_population ();
 183   }
 184
 185   // Incremental increase in the Coverage and ClassDef table size
 186   // (worst case) if all glyphs associated with 'klass' were added.
 187   unsigned incremental_class_def_size (unsigned klass) const
 188   {
 189     // ClassDef takes 6 bytes per range
 190     unsigned class_def_2_size = 6 * num_ranges_per_class.get (klass);
 191     if (gids_consecutive)
 192     {
 193       // ClassDef1 takes 2 bytes per glyph, but only can be used
 194       // when gids are consecutive.
 195       return hb_min (2 * glyphs_per_class.get (klass).get_population (), class_def_2_size);
 196     }
 197
 198     return class_def_2_size;
 199   }
 200
 201   bool in_error ()
 202   {
 203     if (num_ranges_per_class.in_error ()) return true;
 204     if (glyphs_per_class.in_error ()) return true;
 205
 206     for (const hb_set_t& s : glyphs_per_class.values ())
 207     {
 208       if (s.in_error ()) return true;
 209     }
 210     return false;
 211   }
 212
 213  private:
 214   bool gids_consecutive;
 215   hb_hashmap_t<unsigned, unsigned> num_ranges_per_class;
 216   hb_hashmap_t<unsigned, hb_set_t> glyphs_per_class;
 217 };
 218
 219
 220 }
 221
 222 #endif  // GRAPH_CLASSDEF_GRAPH_HH