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 |
223 | |