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_SERIALIZE_HH
28#define GRAPH_SERIALIZE_HH
29
30namespace graph {
31
32struct overflow_record_t
33{
34 unsigned parent;
35 unsigned child;
36
37 bool operator != (const overflow_record_t o) const
38 { return !(*this == o); }
39
40 inline bool operator == (const overflow_record_t& o) const
41 {
42 return parent == o.parent &&
43 child == o.child;
44 }
45
46 inline uint32_t hash () const
47 {
48 uint32_t current = 0;
49 current = current * 31 + hb_hash (parent);
50 current = current * 31 + hb_hash (child);
51 return current;
52 }
53};
54
55inline
56int64_t compute_offset (
57 const graph_t& graph,
58 unsigned parent_idx,
59 const hb_serialize_context_t::object_t::link_t& link)
60{
61 const auto& parent = graph.vertices_[parent_idx];
62 const auto& child = graph.vertices_[link.objidx];
63 int64_t offset = 0;
64 switch ((hb_serialize_context_t::whence_t) link.whence) {
65 case hb_serialize_context_t::whence_t::Head:
66 offset = child.start - parent.start; break;
67 case hb_serialize_context_t::whence_t::Tail:
68 offset = child.start - parent.end; break;
69 case hb_serialize_context_t::whence_t::Absolute:
70 offset = child.start; break;
71 }
72
73 assert (offset >= link.bias);
74 offset -= link.bias;
75 return offset;
76}
77
78inline
79bool is_valid_offset (int64_t offset,
80 const hb_serialize_context_t::object_t::link_t& link)
81{
82 if (unlikely (!link.width))
83 // Virtual links can't overflow.
84 return link.is_signed || offset >= 0;
85
86 if (link.is_signed)
87 {
88 if (link.width == 4)
89 return offset >= -((int64_t) 1 << 31) && offset < ((int64_t) 1 << 31);
90 else
91 return offset >= -(1 << 15) && offset < (1 << 15);
92 }
93 else
94 {
95 if (link.width == 4)
96 return offset >= 0 && offset < ((int64_t) 1 << 32);
97 else if (link.width == 3)
98 return offset >= 0 && offset < ((int32_t) 1 << 24);
99 else
100 return offset >= 0 && offset < (1 << 16);
101 }
102}
103
104/*
105 * Will any offsets overflow on graph when it's serialized?
106 */
107inline bool
108will_overflow (graph_t& graph,
109 hb_vector_t<overflow_record_t>* overflows = nullptr)
110{
111 if (overflows) overflows->resize (0);
112 graph.update_positions ();
113
114 hb_hashmap_t<overflow_record_t*, bool> record_set;
115 const auto& vertices = graph.vertices_;
116 for (int parent_idx = vertices.length - 1; parent_idx >= 0; parent_idx--)
117 {
118 // Don't need to check virtual links for overflow
119 for (const auto& link : vertices.arrayZ[parent_idx].obj.real_links)
120 {
121 int64_t offset = compute_offset (graph, parent_idx, link);
122 if (likely (is_valid_offset (offset, link)))
123 continue;
124
125 if (!overflows) return true;
126
127 overflow_record_t r;
128 r.parent = parent_idx;
129 r.child = link.objidx;
130 if (record_set.has(&r)) continue; // don't keep duplicate overflows.
131
132 overflows->push (r);
133 record_set.set(&r, true);
134 }
135 }
136
137 if (!overflows) return false;
138 return overflows->length;
139}
140
141inline
142void print_overflows (graph_t& graph,
143 const hb_vector_t<overflow_record_t>& overflows)
144{
145 if (!DEBUG_ENABLED(SUBSET_REPACK)) return;
146
147 graph.update_parents ();
148 int limit = 10;
149 for (const auto& o : overflows)
150 {
151 if (!limit--) break;
152 const auto& parent = graph.vertices_[o.parent];
153 const auto& child = graph.vertices_[o.child];
154 DEBUG_MSG (SUBSET_REPACK, nullptr,
155 " overflow from "
156 "%4u (%4u in, %4u out, space %2u) => "
157 "%4u (%4u in, %4u out, space %2u)",
158 o.parent,
159 parent.incoming_edges (),
160 parent.obj.real_links.length + parent.obj.virtual_links.length,
161 graph.space_for (o.parent),
162 o.child,
163 child.incoming_edges (),
164 child.obj.real_links.length + child.obj.virtual_links.length,
165 graph.space_for (o.child));
166 }
167 if (overflows.length > 10) {
168 DEBUG_MSG (SUBSET_REPACK, nullptr, " ... plus %u more overflows.", overflows.length - 10);
169 }
170}
171
172template <typename O> inline void
173serialize_link_of_type (const hb_serialize_context_t::object_t::link_t& link,
174 char* head,
175 hb_serialize_context_t* c)
176{
177 OT::Offset<O>* offset = reinterpret_cast<OT::Offset<O>*> (head + link.position);
178 *offset = 0;
179 c->add_link (*offset,
180 // serializer has an extra nil object at the start of the
181 // object array. So all id's are +1 of what our id's are.
182 link.objidx + 1,
183 (hb_serialize_context_t::whence_t) link.whence,
184 link.bias);
185}
186
187inline
188void serialize_link (const hb_serialize_context_t::object_t::link_t& link,
189 char* head,
190 hb_serialize_context_t* c)
191{
192 switch (link.width)
193 {
194 case 0:
195 // Virtual links aren't serialized.
196 return;
197 case 4:
198 if (link.is_signed)
199 {
200 serialize_link_of_type<OT::HBINT32> (link, head, c);
201 } else {
202 serialize_link_of_type<OT::HBUINT32> (link, head, c);
203 }
204 return;
205 case 2:
206 if (link.is_signed)
207 {
208 serialize_link_of_type<OT::HBINT16> (link, head, c);
209 } else {
210 serialize_link_of_type<OT::HBUINT16> (link, head, c);
211 }
212 return;
213 case 3:
214 serialize_link_of_type<OT::HBUINT24> (link, head, c);
215 return;
216 default:
217 // Unexpected link width.
218 assert (0);
219 }
220}
221
222/*
223 * serialize graph into the provided serialization buffer.
224 */
225inline hb_blob_t* serialize (const graph_t& graph)
226{
227 hb_vector_t<char> buffer;
228 size_t size = graph.total_size_in_bytes ();
229
230 if (!size) return hb_blob_get_empty ();
231
232 if (!buffer.alloc (size)) {
233 DEBUG_MSG (SUBSET_REPACK, nullptr, "Unable to allocate output buffer.");
234 return nullptr;
235 }
236 hb_serialize_context_t c((void *) buffer, size);
237
238 c.start_serialize<void> ();
239 const auto& vertices = graph.vertices_;
240 for (unsigned i = 0; i < vertices.length; i++) {
241 c.push ();
242
243 size_t size = vertices[i].obj.tail - vertices[i].obj.head;
244 char* start = c.allocate_size <char> (size);
245 if (!start) {
246 DEBUG_MSG (SUBSET_REPACK, nullptr, "Buffer out of space.");
247 return nullptr;
248 }
249
250 hb_memcpy (start, vertices[i].obj.head, size);
251
252 // Only real links needs to be serialized.
253 for (const auto& link : vertices[i].obj.real_links)
254 serialize_link (link, start, &c);
255
256 // All duplications are already encoded in the graph, so don't
257 // enable sharing during packing.
258 c.pop_pack (false);
259 }
260 c.end_serialize ();
261
262 if (c.in_error ()) {
263 DEBUG_MSG (SUBSET_REPACK, nullptr, "Error during serialization. Err flag: %d",
264 c.errors);
265 return nullptr;
266 }
267
268 return c.copy_blob ();
269}
270
271} // namespace graph
272
273#endif // GRAPH_SERIALIZE_HH
274