1 /*
2 * Copyright © 2020 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 <string>
28
29 #include "hb-repacker.hh"
30 #include "hb-open-type.hh"
31
start_object(const char * tag,unsigned len,hb_serialize_context_t * c)32 static void start_object(const char* tag,
33 unsigned len,
34 hb_serialize_context_t* c)
35 {
36 c->push ();
37 char* obj = c->allocate_size<char> (len);
38 strncpy (obj, tag, len);
39 }
40
41
add_object(const char * tag,unsigned len,hb_serialize_context_t * c)42 static unsigned add_object(const char* tag,
43 unsigned len,
44 hb_serialize_context_t* c)
45 {
46 start_object (tag, len, c);
47 return c->pop_pack (false);
48 }
49
50
add_offset(unsigned id,hb_serialize_context_t * c)51 static void add_offset (unsigned id,
52 hb_serialize_context_t* c)
53 {
54 OT::Offset16* offset = c->start_embed<OT::Offset16> ();
55 c->extend_min (offset);
56 c->add_link (*offset, id);
57 }
58
59 static void
populate_serializer_simple(hb_serialize_context_t * c)60 populate_serializer_simple (hb_serialize_context_t* c)
61 {
62 c->start_serialize<char> ();
63
64 unsigned obj_1 = add_object ("ghi", 3, c);
65 unsigned obj_2 = add_object ("def", 3, c);
66
67 start_object ("abc", 3, c);
68 add_offset (obj_2, c);
69 add_offset (obj_1, c);
70 c->pop_pack ();
71
72 c->end_serialize();
73 }
74
75 static void
populate_serializer_with_overflow(hb_serialize_context_t * c)76 populate_serializer_with_overflow (hb_serialize_context_t* c)
77 {
78 std::string large_string(50000, 'a');
79 c->start_serialize<char> ();
80
81 unsigned obj_1 = add_object (large_string.c_str(), 10000, c);
82 unsigned obj_2 = add_object (large_string.c_str(), 20000, c);
83 unsigned obj_3 = add_object (large_string.c_str(), 50000, c);
84
85 start_object ("abc", 3, c);
86 add_offset (obj_3, c);
87 add_offset (obj_2, c);
88 add_offset (obj_1, c);
89 c->pop_pack ();
90
91 c->end_serialize();
92 }
93
94 static void
populate_serializer_with_dedup_overflow(hb_serialize_context_t * c)95 populate_serializer_with_dedup_overflow (hb_serialize_context_t* c)
96 {
97 std::string large_string(70000, 'a');
98 c->start_serialize<char> ();
99
100 unsigned obj_1 = add_object ("def", 3, c);
101
102 start_object (large_string.c_str(), 60000, c);
103 add_offset (obj_1, c);
104 unsigned obj_2 = c->pop_pack (false);
105
106 start_object (large_string.c_str(), 10000, c);
107 add_offset (obj_2, c);
108 add_offset (obj_1, c);
109 c->pop_pack (false);
110
111 c->end_serialize();
112 }
113
114 static void
populate_serializer_complex_1(hb_serialize_context_t * c)115 populate_serializer_complex_1 (hb_serialize_context_t* c)
116 {
117 c->start_serialize<char> ();
118
119 unsigned obj_4 = add_object ("jkl", 3, c);
120 unsigned obj_3 = add_object ("ghi", 3, c);
121
122 start_object ("def", 3, c);
123 add_offset (obj_3, c);
124 unsigned obj_2 = c->pop_pack (false);
125
126 start_object ("abc", 3, c);
127 add_offset (obj_2, c);
128 add_offset (obj_4, c);
129 c->pop_pack ();
130
131 c->end_serialize();
132 }
133
134 static void
populate_serializer_complex_2(hb_serialize_context_t * c)135 populate_serializer_complex_2 (hb_serialize_context_t* c)
136 {
137 c->start_serialize<char> ();
138
139 unsigned obj_5 = add_object ("mn", 2, c);
140
141 unsigned obj_4 = add_object ("jkl", 3, c);
142
143 start_object ("ghi", 3, c);
144 add_offset (obj_4, c);
145 unsigned obj_3 = c->pop_pack (false);
146
147 start_object ("def", 3, c);
148 add_offset (obj_3, c);
149 unsigned obj_2 = c->pop_pack (false);
150
151 start_object ("abc", 3, c);
152 add_offset (obj_2, c);
153 add_offset (obj_4, c);
154 add_offset (obj_5, c);
155 c->pop_pack ();
156
157 c->end_serialize();
158 }
159
160 static void
populate_serializer_complex_3(hb_serialize_context_t * c)161 populate_serializer_complex_3 (hb_serialize_context_t* c)
162 {
163 c->start_serialize<char> ();
164
165 unsigned obj_6 = add_object ("opqrst", 6, c);
166
167 unsigned obj_5 = add_object ("mn", 2, c);
168
169 start_object ("jkl", 3, c);
170 add_offset (obj_6, c);
171 unsigned obj_4 = c->pop_pack (false);
172
173 start_object ("ghi", 3, c);
174 add_offset (obj_4, c);
175 unsigned obj_3 = c->pop_pack (false);
176
177 start_object ("def", 3, c);
178 add_offset (obj_3, c);
179 unsigned obj_2 = c->pop_pack (false);
180
181 start_object ("abc", 3, c);
182 add_offset (obj_2, c);
183 add_offset (obj_4, c);
184 add_offset (obj_5, c);
185 c->pop_pack ();
186
187 c->end_serialize();
188 }
189
test_sort_kahn_1()190 static void test_sort_kahn_1 ()
191 {
192 size_t buffer_size = 100;
193 void* buffer = malloc (buffer_size);
194 hb_serialize_context_t c (buffer, buffer_size);
195 populate_serializer_complex_1 (&c);
196
197 graph_t graph (c.object_graph ());
198 graph.sort_kahn ();
199
200 assert(strncmp (graph.object (3).head, "abc", 3) == 0);
201 assert(graph.object (3).links.length == 2);
202 assert(graph.object (3).links[0].objidx == 2);
203 assert(graph.object (3).links[1].objidx == 1);
204
205 assert(strncmp (graph.object (2).head, "def", 3) == 0);
206 assert(graph.object (2).links.length == 1);
207 assert(graph.object (2).links[0].objidx == 0);
208
209 assert(strncmp (graph.object (1).head, "jkl", 3) == 0);
210 assert(graph.object (1).links.length == 0);
211
212 assert(strncmp (graph.object (0).head, "ghi", 3) == 0);
213 assert(graph.object (0).links.length == 0);
214
215 free (buffer);
216 }
217
test_sort_kahn_2()218 static void test_sort_kahn_2 ()
219 {
220 size_t buffer_size = 100;
221 void* buffer = malloc (buffer_size);
222 hb_serialize_context_t c (buffer, buffer_size);
223 populate_serializer_complex_2 (&c);
224
225 graph_t graph (c.object_graph ());
226 graph.sort_kahn ();
227
228
229 assert(strncmp (graph.object (4).head, "abc", 3) == 0);
230 assert(graph.object (4).links.length == 3);
231 assert(graph.object (4).links[0].objidx == 3);
232 assert(graph.object (4).links[1].objidx == 0);
233 assert(graph.object (4).links[2].objidx == 2);
234
235 assert(strncmp (graph.object (3).head, "def", 3) == 0);
236 assert(graph.object (3).links.length == 1);
237 assert(graph.object (3).links[0].objidx == 1);
238
239 assert(strncmp (graph.object (2).head, "mn", 2) == 0);
240 assert(graph.object (2).links.length == 0);
241
242 assert(strncmp (graph.object (1).head, "ghi", 3) == 0);
243 assert(graph.object (1).links.length == 1);
244 assert(graph.object (1).links[0].objidx == 0);
245
246 assert(strncmp (graph.object (0).head, "jkl", 3) == 0);
247 assert(graph.object (0).links.length == 0);
248
249 free (buffer);
250 }
251
test_sort_shortest()252 static void test_sort_shortest ()
253 {
254 size_t buffer_size = 100;
255 void* buffer = malloc (buffer_size);
256 hb_serialize_context_t c (buffer, buffer_size);
257 populate_serializer_complex_2 (&c);
258
259 graph_t graph (c.object_graph ());
260 graph.sort_shortest_distance ();
261
262 assert(strncmp (graph.object (4).head, "abc", 3) == 0);
263 assert(graph.object (4).links.length == 3);
264 assert(graph.object (4).links[0].objidx == 2);
265 assert(graph.object (4).links[1].objidx == 0);
266 assert(graph.object (4).links[2].objidx == 3);
267
268 assert(strncmp (graph.object (3).head, "mn", 2) == 0);
269 assert(graph.object (3).links.length == 0);
270
271 assert(strncmp (graph.object (2).head, "def", 3) == 0);
272 assert(graph.object (2).links.length == 1);
273 assert(graph.object (2).links[0].objidx == 1);
274
275 assert(strncmp (graph.object (1).head, "ghi", 3) == 0);
276 assert(graph.object (1).links.length == 1);
277 assert(graph.object (1).links[0].objidx == 0);
278
279 assert(strncmp (graph.object (0).head, "jkl", 3) == 0);
280 assert(graph.object (0).links.length == 0);
281
282 free (buffer);
283 }
284
test_duplicate_leaf()285 static void test_duplicate_leaf ()
286 {
287 size_t buffer_size = 100;
288 void* buffer = malloc (buffer_size);
289 hb_serialize_context_t c (buffer, buffer_size);
290 populate_serializer_complex_2 (&c);
291
292 graph_t graph (c.object_graph ());
293 graph.duplicate (4, 1);
294
295 assert(strncmp (graph.object (5).head, "abc", 3) == 0);
296 assert(graph.object (5).links.length == 3);
297 assert(graph.object (5).links[0].objidx == 3);
298 assert(graph.object (5).links[1].objidx == 4);
299 assert(graph.object (5).links[2].objidx == 0);
300
301 assert(strncmp (graph.object (4).head, "jkl", 3) == 0);
302 assert(graph.object (4).links.length == 0);
303
304 assert(strncmp (graph.object (3).head, "def", 3) == 0);
305 assert(graph.object (3).links.length == 1);
306 assert(graph.object (3).links[0].objidx == 2);
307
308 assert(strncmp (graph.object (2).head, "ghi", 3) == 0);
309 assert(graph.object (2).links.length == 1);
310 assert(graph.object (2).links[0].objidx == 1);
311
312 assert(strncmp (graph.object (1).head, "jkl", 3) == 0);
313 assert(graph.object (1).links.length == 0);
314
315 assert(strncmp (graph.object (0).head, "mn", 2) == 0);
316 assert(graph.object (0).links.length == 0);
317
318 free (buffer);
319 }
320
test_duplicate_interior()321 static void test_duplicate_interior ()
322 {
323 size_t buffer_size = 100;
324 void* buffer = malloc (buffer_size);
325 hb_serialize_context_t c (buffer, buffer_size);
326 populate_serializer_complex_3 (&c);
327
328 graph_t graph (c.object_graph ());
329 graph.duplicate (3, 2);
330
331 assert(strncmp (graph.object (6).head, "abc", 3) == 0);
332 assert(graph.object (6).links.length == 3);
333 assert(graph.object (6).links[0].objidx == 4);
334 assert(graph.object (6).links[1].objidx == 2);
335 assert(graph.object (6).links[2].objidx == 1);
336
337 assert(strncmp (graph.object (5).head, "jkl", 3) == 0);
338 assert(graph.object (5).links.length == 1);
339 assert(graph.object (5).links[0].objidx == 0);
340
341 assert(strncmp (graph.object (4).head, "def", 3) == 0);
342 assert(graph.object (4).links.length == 1);
343 assert(graph.object (4).links[0].objidx == 3);
344
345 assert(strncmp (graph.object (3).head, "ghi", 3) == 0);
346 assert(graph.object (3).links.length == 1);
347 assert(graph.object (3).links[0].objidx == 5);
348
349 assert(strncmp (graph.object (2).head, "jkl", 3) == 0);
350 assert(graph.object (2).links.length == 1);
351 assert(graph.object (2).links[0].objidx == 0);
352
353 assert(strncmp (graph.object (1).head, "mn", 2) == 0);
354 assert(graph.object (1).links.length == 0);
355
356 assert(strncmp (graph.object (0).head, "opqrst", 6) == 0);
357 assert(graph.object (0).links.length == 0);
358
359 free (buffer);
360 }
361
362 static void
test_serialize()363 test_serialize ()
364 {
365 size_t buffer_size = 100;
366 void* buffer_1 = malloc (buffer_size);
367 hb_serialize_context_t c1 (buffer_1, buffer_size);
368 populate_serializer_simple (&c1);
369 hb_bytes_t expected = c1.copy_bytes ();
370
371 void* buffer_2 = malloc (buffer_size);
372 hb_serialize_context_t c2 (buffer_2, buffer_size);
373
374 graph_t graph (c1.object_graph ());
375 graph.serialize (&c2);
376 hb_bytes_t actual = c2.copy_bytes ();
377
378 assert (actual == expected);
379
380 actual.free ();
381 expected.free ();
382 free (buffer_1);
383 free (buffer_2);
384 }
385
test_will_overflow_1()386 static void test_will_overflow_1 ()
387 {
388 size_t buffer_size = 100;
389 void* buffer = malloc (buffer_size);
390 hb_serialize_context_t c (buffer, buffer_size);
391 populate_serializer_complex_2 (&c);
392 graph_t graph (c.object_graph ());
393
394 assert (!graph.will_overflow (nullptr));
395
396 free (buffer);
397 }
398
test_will_overflow_2()399 static void test_will_overflow_2 ()
400 {
401 size_t buffer_size = 160000;
402 void* buffer = malloc (buffer_size);
403 hb_serialize_context_t c (buffer, buffer_size);
404 populate_serializer_with_overflow (&c);
405 graph_t graph (c.object_graph ());
406
407 assert (graph.will_overflow (nullptr));
408
409 free (buffer);
410 }
411
test_will_overflow_3()412 static void test_will_overflow_3 ()
413 {
414 size_t buffer_size = 160000;
415 void* buffer = malloc (buffer_size);
416 hb_serialize_context_t c (buffer, buffer_size);
417 populate_serializer_with_dedup_overflow (&c);
418 graph_t graph (c.object_graph ());
419
420 assert (graph.will_overflow (nullptr));
421
422 free (buffer);
423 }
424
test_resolve_overflows_via_sort()425 static void test_resolve_overflows_via_sort ()
426 {
427 size_t buffer_size = 160000;
428 void* buffer = malloc (buffer_size);
429 hb_serialize_context_t c (buffer, buffer_size);
430 populate_serializer_with_overflow (&c);
431 graph_t graph (c.object_graph ());
432
433 void* out_buffer = malloc (buffer_size);
434 hb_serialize_context_t out (out_buffer, buffer_size);
435
436 hb_resolve_overflows (c.object_graph (), &out);
437 assert (!out.offset_overflow ());
438 hb_bytes_t result = out.copy_bytes ();
439 assert (result.length == (80000 + 3 + 3 * 2));
440
441 result.free ();
442 free (buffer);
443 free (out_buffer);
444 }
445
test_resolve_overflows_via_duplication()446 static void test_resolve_overflows_via_duplication ()
447 {
448 size_t buffer_size = 160000;
449 void* buffer = malloc (buffer_size);
450 hb_serialize_context_t c (buffer, buffer_size);
451 populate_serializer_with_dedup_overflow (&c);
452 graph_t graph (c.object_graph ());
453
454 void* out_buffer = malloc (buffer_size);
455 hb_serialize_context_t out (out_buffer, buffer_size);
456
457 hb_resolve_overflows (c.object_graph (), &out);
458 assert (!out.offset_overflow ());
459 hb_bytes_t result = out.copy_bytes ();
460 assert (result.length == (10000 + 2 * 2 + 60000 + 2 + 3 * 2));
461
462 result.free ();
463 free (buffer);
464 free (out_buffer);
465 }
466
467 // TODO(garretrieger): update will_overflow tests to check the overflows array.
468 // TODO(garretrieger): add a test(s) using a real font.
469 // TODO(garretrieger): add tests for priority raising.
470
471 int
main(int argc,char ** argv)472 main (int argc, char **argv)
473 {
474 test_serialize ();
475 test_sort_kahn_1 ();
476 test_sort_kahn_2 ();
477 test_sort_shortest ();
478 test_will_overflow_1 ();
479 test_will_overflow_2 ();
480 test_will_overflow_3 ();
481 test_resolve_overflows_via_sort ();
482 test_resolve_overflows_via_duplication ();
483 test_duplicate_leaf ();
484 test_duplicate_interior ();
485 }
486