classdef-graph.hh (7965B)
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 hb_barrier (); 43 return vertex_len >= min_size + classValue.get_size () - classValue.len.get_size (); 44 } 45 }; 46 47 struct ClassDefFormat2 : public OT::ClassDefFormat2_4<SmallTypes> 48 { 49 bool sanitize (graph_t::vertex_t& vertex) const 50 { 51 int64_t vertex_len = vertex.obj.tail - vertex.obj.head; 52 constexpr unsigned min_size = OT::ClassDefFormat2_4<SmallTypes>::min_size; 53 if (vertex_len < min_size) return false; 54 hb_barrier (); 55 return vertex_len >= min_size + rangeRecord.get_size () - rangeRecord.len.get_size (); 56 } 57 }; 58 59 struct ClassDef : public OT::ClassDef 60 { 61 template<typename It> 62 static bool add_class_def (gsubgpos_graph_context_t& c, 63 unsigned parent_id, 64 unsigned link_position, 65 It glyph_and_class, 66 unsigned max_size) 67 { 68 unsigned class_def_prime_id = c.graph.new_node (nullptr, nullptr); 69 auto& class_def_prime_vertex = c.graph.vertices_[class_def_prime_id]; 70 if (!make_class_def (c, glyph_and_class, class_def_prime_id, max_size)) 71 return false; 72 73 auto* class_def_link = c.graph.vertices_[parent_id].obj.real_links.push (); 74 class_def_link->width = SmallTypes::size; 75 class_def_link->objidx = class_def_prime_id; 76 class_def_link->position = link_position; 77 class_def_prime_vertex.add_parent (parent_id, false); 78 79 return true; 80 } 81 82 template<typename It> 83 static bool make_class_def (gsubgpos_graph_context_t& c, 84 It glyph_and_class, 85 unsigned dest_obj, 86 unsigned max_size) 87 { 88 char* buffer = (char*) hb_calloc (1, max_size); 89 hb_serialize_context_t serializer (buffer, max_size); 90 OT::ClassDef_serialize (&serializer, glyph_and_class); 91 serializer.end_serialize (); 92 if (serializer.in_error ()) 93 { 94 hb_free (buffer); 95 return false; 96 } 97 98 hb_bytes_t class_def_copy = serializer.copy_bytes (); 99 if (!class_def_copy.arrayZ) return false; 100 // Give ownership to the context, it will cleanup the buffer. 101 if (!c.add_buffer ((char *) class_def_copy.arrayZ)) 102 { 103 hb_free ((char *) class_def_copy.arrayZ); 104 return false; 105 } 106 107 auto& obj = c.graph.vertices_[dest_obj].obj; 108 obj.head = (char *) class_def_copy.arrayZ; 109 obj.tail = obj.head + class_def_copy.length; 110 111 hb_free (buffer); 112 return true; 113 } 114 115 bool sanitize (graph_t::vertex_t& vertex) const 116 { 117 int64_t vertex_len = vertex.obj.tail - vertex.obj.head; 118 if (vertex_len < OT::ClassDef::min_size) return false; 119 hb_barrier (); 120 switch (u.format.v) 121 { 122 case 1: return ((ClassDefFormat1*)this)->sanitize (vertex); 123 case 2: return ((ClassDefFormat2*)this)->sanitize (vertex); 124 #ifndef HB_NO_BEYOND_64K 125 // Not currently supported 126 case 3: 127 case 4: 128 #endif 129 default: return false; 130 } 131 } 132 }; 133 134 135 struct class_def_size_estimator_t 136 { 137 // TODO(garretrieger): update to support beyond64k coverage/classdef tables. 138 constexpr static unsigned class_def_format1_base_size = 6; 139 constexpr static unsigned class_def_format2_base_size = 4; 140 constexpr static unsigned coverage_base_size = 4; 141 constexpr static unsigned bytes_per_range = 6; 142 constexpr static unsigned bytes_per_glyph = 2; 143 144 template<typename It> 145 class_def_size_estimator_t (It glyph_and_class) 146 : num_ranges_per_class (), glyphs_per_class () 147 { 148 reset(); 149 for (auto p : + glyph_and_class) 150 { 151 unsigned gid = p.first; 152 unsigned klass = p.second; 153 154 hb_set_t* glyphs; 155 if (glyphs_per_class.has (klass, &glyphs) && glyphs) { 156 glyphs->add (gid); 157 continue; 158 } 159 160 hb_set_t new_glyphs; 161 new_glyphs.add (gid); 162 glyphs_per_class.set (klass, std::move (new_glyphs)); 163 } 164 165 if (in_error ()) return; 166 167 for (unsigned klass : glyphs_per_class.keys ()) 168 { 169 if (!klass) continue; // class 0 doesn't get encoded. 170 171 const hb_set_t& glyphs = glyphs_per_class.get (klass); 172 hb_codepoint_t start = HB_SET_VALUE_INVALID; 173 hb_codepoint_t end = HB_SET_VALUE_INVALID; 174 175 unsigned count = 0; 176 while (glyphs.next_range (&start, &end)) 177 count++; 178 179 num_ranges_per_class.set (klass, count); 180 } 181 } 182 183 void reset() { 184 class_def_1_size = class_def_format1_base_size; 185 class_def_2_size = class_def_format2_base_size; 186 included_glyphs.clear(); 187 included_classes.clear(); 188 } 189 190 // Compute the size of coverage for all glyphs added via 'add_class_def_size'. 191 unsigned coverage_size () const 192 { 193 unsigned format1_size = coverage_base_size + bytes_per_glyph * included_glyphs.get_population(); 194 unsigned format2_size = coverage_base_size + bytes_per_range * num_glyph_ranges(); 195 return hb_min(format1_size, format2_size); 196 } 197 198 // Compute the new size of the ClassDef table if all glyphs associated with 'klass' were added. 199 unsigned add_class_def_size (unsigned klass) 200 { 201 if (!included_classes.has(klass)) { 202 hb_set_t* glyphs = nullptr; 203 if (glyphs_per_class.has(klass, &glyphs)) { 204 included_glyphs.union_(*glyphs); 205 } 206 207 class_def_1_size = class_def_format1_base_size; 208 if (!included_glyphs.is_empty()) { 209 unsigned min_glyph = included_glyphs.get_min(); 210 unsigned max_glyph = included_glyphs.get_max(); 211 class_def_1_size += bytes_per_glyph * (max_glyph - min_glyph + 1); 212 } 213 214 class_def_2_size += bytes_per_range * num_ranges_per_class.get (klass); 215 216 included_classes.add(klass); 217 } 218 219 return hb_min (class_def_1_size, class_def_2_size); 220 } 221 222 unsigned num_glyph_ranges() const { 223 hb_codepoint_t start = HB_SET_VALUE_INVALID; 224 hb_codepoint_t end = HB_SET_VALUE_INVALID; 225 226 unsigned count = 0; 227 while (included_glyphs.next_range (&start, &end)) { 228 count++; 229 } 230 return count; 231 } 232 233 bool in_error () 234 { 235 if (num_ranges_per_class.in_error ()) return true; 236 if (glyphs_per_class.in_error ()) return true; 237 238 for (const hb_set_t& s : glyphs_per_class.values ()) 239 { 240 if (s.in_error ()) return true; 241 } 242 return false; 243 } 244 245 private: 246 hb_hashmap_t<unsigned, unsigned> num_ranges_per_class; 247 hb_hashmap_t<unsigned, hb_set_t> glyphs_per_class; 248 hb_set_t included_classes; 249 hb_set_t included_glyphs; 250 unsigned class_def_1_size; 251 unsigned class_def_2_size; 252 }; 253 254 255 } 256 257 #endif // GRAPH_CLASSDEF_GRAPH_HH