Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/harfbuzz/src/graph/serialize.hh @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
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
30 namespace graph {
31
32 struct 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
55 inline
56 int64_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
78 inline
79 bool 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 */
107 inline bool
108 will_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[parent_idx].obj.real_links)
120 {
121 int64_t offset = compute_offset (graph, parent_idx, link);
122 if (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
141 inline
142 void 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 "%4d (%4d in, %4d out, space %2d) => "
157 "%4d (%4d in, %4d out, space %2d)",
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 %d more overflows.", overflows.length - 10);
169 }
170 }
171
172 template <typename O> inline void
173 serialize_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
187 inline
188 void 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 */
225 inline 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 if (!buffer.alloc (size)) {
230 DEBUG_MSG (SUBSET_REPACK, nullptr, "Unable to allocate output buffer.");
231 return nullptr;
232 }
233 hb_serialize_context_t c((void *) buffer, size);
234
235 c.start_serialize<void> ();
236 const auto& vertices = graph.vertices_;
237 for (unsigned i = 0; i < vertices.length; i++) {
238 c.push ();
239
240 size_t size = vertices[i].obj.tail - vertices[i].obj.head;
241 char* start = c.allocate_size <char> (size);
242 if (!start) {
243 DEBUG_MSG (SUBSET_REPACK, nullptr, "Buffer out of space.");
244 return nullptr;
245 }
246
247 hb_memcpy (start, vertices[i].obj.head, size);
248
249 // Only real links needs to be serialized.
250 for (const auto& link : vertices[i].obj.real_links)
251 serialize_link (link, start, &c);
252
253 // All duplications are already encoded in the graph, so don't
254 // enable sharing during packing.
255 c.pop_pack (false);
256 }
257 c.end_serialize ();
258
259 if (c.in_error ()) {
260 DEBUG_MSG (SUBSET_REPACK, nullptr, "Error during serialization. Err flag: %d",
261 c.errors);
262 return nullptr;
263 }
264
265 return c.copy_blob ();
266 }
267
268 } // namespace graph
269
270 #endif // GRAPH_SERIALIZE_HH