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
add_wide_offset(unsigned id,hb_serialize_context_t * c)59 static void add_wide_offset (unsigned id,
60 hb_serialize_context_t* c)
61 {
62 OT::Offset32* offset = c->start_embed<OT::Offset32> ();
63 c->extend_min (offset);
64 c->add_link (*offset, id);
65 }
66
run_resolve_overflow_test(const char * name,hb_serialize_context_t & overflowing,hb_serialize_context_t & expected,unsigned num_iterations=0)67 static void run_resolve_overflow_test (const char* name,
68 hb_serialize_context_t& overflowing,
69 hb_serialize_context_t& expected,
70 unsigned num_iterations = 0)
71 {
72 printf (">>> Testing overflowing resolution for %s\n",
73 name);
74
75 graph_t graph (overflowing.object_graph ());
76
77 unsigned buffer_size = overflowing.end - overflowing.start;
78 void* out_buffer = malloc (buffer_size);
79 hb_serialize_context_t out (out_buffer, buffer_size);
80
81 assert (overflowing.offset_overflow ());
82 hb_resolve_overflows (overflowing.object_graph (), HB_TAG ('G', 'S', 'U', 'B'), &out, num_iterations);
83 assert (!out.offset_overflow ());
84 hb_bytes_t result = out.copy_bytes ();
85
86 assert (!expected.offset_overflow ());
87 hb_bytes_t expected_result = expected.copy_bytes ();
88
89 assert (result.length == expected_result.length);
90 for (unsigned i = 0; i < expected_result.length; i++)
91 {
92 assert (result[i] == expected_result[i]);
93 }
94
95 result.fini ();
96 expected_result.fini ();
97 free (out_buffer);
98 }
99
add_virtual_offset(unsigned id,hb_serialize_context_t * c)100 static void add_virtual_offset (unsigned id,
101 hb_serialize_context_t* c)
102 {
103 c->add_virtual_link (id);
104 }
105
106 static void
populate_serializer_simple(hb_serialize_context_t * c)107 populate_serializer_simple (hb_serialize_context_t* c)
108 {
109 c->start_serialize<char> ();
110
111 unsigned obj_1 = add_object ("ghi", 3, c);
112 unsigned obj_2 = add_object ("def", 3, c);
113
114 start_object ("abc", 3, c);
115 add_offset (obj_2, c);
116 add_offset (obj_1, c);
117 c->pop_pack (false);
118
119 c->end_serialize();
120 }
121
122 static void
populate_serializer_with_overflow(hb_serialize_context_t * c)123 populate_serializer_with_overflow (hb_serialize_context_t* c)
124 {
125 std::string large_string(50000, 'a');
126 c->start_serialize<char> ();
127
128 unsigned obj_1 = add_object (large_string.c_str(), 10000, c);
129 unsigned obj_2 = add_object (large_string.c_str(), 20000, c);
130 unsigned obj_3 = add_object (large_string.c_str(), 50000, c);
131
132 start_object ("abc", 3, c);
133 add_offset (obj_3, c);
134 add_offset (obj_2, c);
135 add_offset (obj_1, c);
136 c->pop_pack (false);
137
138 c->end_serialize();
139 }
140
141 static void
populate_serializer_with_dedup_overflow(hb_serialize_context_t * c)142 populate_serializer_with_dedup_overflow (hb_serialize_context_t* c)
143 {
144 std::string large_string(70000, 'a');
145 c->start_serialize<char> ();
146
147 unsigned obj_1 = add_object ("def", 3, c);
148
149 start_object (large_string.c_str(), 60000, c);
150 add_offset (obj_1, c);
151 unsigned obj_2 = c->pop_pack (false);
152
153 start_object (large_string.c_str(), 10000, c);
154 add_offset (obj_2, c);
155 add_offset (obj_1, c);
156 c->pop_pack (false);
157
158 c->end_serialize();
159 }
160
161 static void
populate_serializer_with_isolation_overflow(hb_serialize_context_t * c)162 populate_serializer_with_isolation_overflow (hb_serialize_context_t* c)
163 {
164 std::string large_string(70000, 'a');
165 c->start_serialize<char> ();
166
167 unsigned obj_4 = add_object ("4", 1, c);
168
169 start_object (large_string.c_str(), 60000, c);
170 add_offset (obj_4, c);
171 unsigned obj_3 = c->pop_pack (false);
172
173 start_object (large_string.c_str(), 10000, c);
174 add_offset (obj_4, c);
175 unsigned obj_2 = c->pop_pack (false);
176
177 start_object ("1", 1, c);
178 add_wide_offset (obj_3, c);
179 add_offset (obj_2, c);
180 c->pop_pack (false);
181
182 c->end_serialize();
183 }
184
185 static void
populate_serializer_with_isolation_overflow_complex(hb_serialize_context_t * c)186 populate_serializer_with_isolation_overflow_complex (hb_serialize_context_t* c)
187 {
188 std::string large_string(70000, 'a');
189 c->start_serialize<char> ();
190
191 unsigned obj_f = add_object ("f", 1, c);
192
193 start_object ("e", 1, c);
194 add_offset (obj_f, c);
195 unsigned obj_e = c->pop_pack (false);
196
197 start_object ("c", 1, c);
198 add_offset (obj_e, c);
199 unsigned obj_c = c->pop_pack (false);
200
201 start_object ("d", 1, c);
202 add_offset (obj_e, c);
203 unsigned obj_d = c->pop_pack (false);
204
205 start_object (large_string.c_str(), 60000, c);
206 add_offset (obj_d, c);
207 unsigned obj_h = c->pop_pack (false);
208
209 start_object (large_string.c_str(), 60000, c);
210 add_offset (obj_c, c);
211 add_offset (obj_h, c);
212 unsigned obj_b = c->pop_pack (false);
213
214 start_object (large_string.c_str(), 10000, c);
215 add_offset (obj_d, c);
216 unsigned obj_g = c->pop_pack (false);
217
218 start_object (large_string.c_str(), 11000, c);
219 add_offset (obj_d, c);
220 unsigned obj_i = c->pop_pack (false);
221
222 start_object ("a", 1, c);
223 add_wide_offset (obj_b, c);
224 add_offset (obj_g, c);
225 add_offset (obj_i, c);
226 c->pop_pack (false);
227
228 c->end_serialize();
229 }
230
231 static void
populate_serializer_with_isolation_overflow_complex_expected(hb_serialize_context_t * c)232 populate_serializer_with_isolation_overflow_complex_expected (hb_serialize_context_t* c)
233 {
234 std::string large_string(70000, 'a');
235 c->start_serialize<char> ();
236
237
238 // space 1
239
240 unsigned obj_f_prime = add_object ("f", 1, c);
241
242 start_object ("e", 1, c);
243 add_offset (obj_f_prime, c);
244 unsigned obj_e_prime = c->pop_pack (false);
245
246 start_object ("d", 1, c);
247 add_offset (obj_e_prime, c);
248 unsigned obj_d_prime = c->pop_pack (false);
249
250 start_object (large_string.c_str(), 60000, c);
251 add_offset (obj_d_prime, c);
252 unsigned obj_h = c->pop_pack (false);
253
254 start_object ("c", 1, c);
255 add_offset (obj_e_prime, c);
256 unsigned obj_c = c->pop_pack (false);
257
258 start_object (large_string.c_str(), 60000, c);
259 add_offset (obj_c, c);
260 add_offset (obj_h, c);
261 unsigned obj_b = c->pop_pack (false);
262
263 // space 0
264
265 unsigned obj_f = add_object ("f", 1, c);
266
267 start_object ("e", 1, c);
268 add_offset (obj_f, c);
269 unsigned obj_e = c->pop_pack (false);
270
271
272 start_object ("d", 1, c);
273 add_offset (obj_e, c);
274 unsigned obj_d = c->pop_pack (false);
275
276 start_object (large_string.c_str(), 11000, c);
277 add_offset (obj_d, c);
278 unsigned obj_i = c->pop_pack (false);
279
280 start_object (large_string.c_str(), 10000, c);
281 add_offset (obj_d, c);
282 unsigned obj_g = c->pop_pack (false);
283
284 start_object ("a", 1, c);
285 add_wide_offset (obj_b, c);
286 add_offset (obj_g, c);
287 add_offset (obj_i, c);
288 c->pop_pack (false);
289
290 c->end_serialize();
291 }
292
293 static void
populate_serializer_with_isolation_overflow_spaces(hb_serialize_context_t * c)294 populate_serializer_with_isolation_overflow_spaces (hb_serialize_context_t* c)
295 {
296 std::string large_string(70000, 'a');
297 c->start_serialize<char> ();
298
299 unsigned obj_d = add_object ("f", 1, c);
300 unsigned obj_e = add_object ("f", 1, c);
301
302 start_object (large_string.c_str(), 60000, c);
303 add_offset (obj_d, c);
304 unsigned obj_b = c->pop_pack ();
305
306 start_object (large_string.c_str(), 60000, c);
307 add_offset (obj_e, c);
308 unsigned obj_c = c->pop_pack ();
309
310
311 start_object ("a", 1, c);
312 add_wide_offset (obj_b, c);
313 add_wide_offset (obj_c, c);
314 c->pop_pack ();
315
316 c->end_serialize();
317 }
318
319 static void
populate_serializer_spaces(hb_serialize_context_t * c,bool with_overflow)320 populate_serializer_spaces (hb_serialize_context_t* c, bool with_overflow)
321 {
322 std::string large_string(70000, 'a');
323 c->start_serialize<char> ();
324
325 unsigned obj_i;
326
327 if (with_overflow)
328 obj_i = add_object ("i", 1, c);
329
330 // Space 2
331 unsigned obj_h = add_object ("h", 1, c);
332
333 start_object (large_string.c_str(), 30000, c);
334 add_offset (obj_h, c);
335 unsigned obj_e = c->pop_pack (false);
336
337 start_object ("b", 1, c);
338 add_offset (obj_e, c);
339 unsigned obj_b = c->pop_pack (false);
340
341 // Space 1
342 if (!with_overflow)
343 obj_i = add_object ("i", 1, c);
344
345 start_object (large_string.c_str(), 30000, c);
346 add_offset (obj_i, c);
347 unsigned obj_g = c->pop_pack (false);
348
349 start_object (large_string.c_str(), 30000, c);
350 add_offset (obj_i, c);
351 unsigned obj_f = c->pop_pack (false);
352
353 start_object ("d", 1, c);
354 add_offset (obj_g, c);
355 unsigned obj_d = c->pop_pack (false);
356
357 start_object ("c", 1, c);
358 add_offset (obj_f, c);
359 unsigned obj_c = c->pop_pack (false);
360
361 start_object ("a", 1, c);
362 add_wide_offset (obj_b, c);
363 add_wide_offset (obj_c, c);
364 add_wide_offset (obj_d, c);
365 c->pop_pack (false);
366
367 c->end_serialize();
368 }
369
370 static void
populate_serializer_spaces_16bit_connection(hb_serialize_context_t * c)371 populate_serializer_spaces_16bit_connection (hb_serialize_context_t* c)
372 {
373 std::string large_string(70000, 'a');
374 c->start_serialize<char> ();
375
376 unsigned obj_g = add_object ("g", 1, c);
377 unsigned obj_h = add_object ("h", 1, c);
378
379 start_object (large_string.c_str (), 40000, c);
380 add_offset (obj_g, c);
381 unsigned obj_e = c->pop_pack (false);
382
383 start_object (large_string.c_str (), 40000, c);
384 add_offset (obj_h, c);
385 unsigned obj_f = c->pop_pack (false);
386
387 start_object ("c", 1, c);
388 add_offset (obj_e, c);
389 unsigned obj_c = c->pop_pack (false);
390
391 start_object ("d", 1, c);
392 add_offset (obj_f, c);
393 unsigned obj_d = c->pop_pack (false);
394
395 start_object ("b", 1, c);
396 add_offset (obj_e, c);
397 add_offset (obj_h, c);
398 unsigned obj_b = c->pop_pack (false);
399
400 start_object ("a", 1, c);
401 add_offset (obj_b, c);
402 add_wide_offset (obj_c, c);
403 add_wide_offset (obj_d, c);
404 c->pop_pack (false);
405
406 c->end_serialize();
407 }
408
409 static void
populate_serializer_spaces_16bit_connection_expected(hb_serialize_context_t * c)410 populate_serializer_spaces_16bit_connection_expected (hb_serialize_context_t* c)
411 {
412 std::string large_string(70000, 'a');
413 c->start_serialize<char> ();
414
415 unsigned obj_g_prime = add_object ("g", 1, c);
416
417 start_object (large_string.c_str (), 40000, c);
418 add_offset (obj_g_prime, c);
419 unsigned obj_e_prime = c->pop_pack (false);
420
421 start_object ("c", 1, c);
422 add_offset (obj_e_prime, c);
423 unsigned obj_c = c->pop_pack (false);
424
425 unsigned obj_h_prime = add_object ("h", 1, c);
426
427 start_object (large_string.c_str (), 40000, c);
428 add_offset (obj_h_prime, c);
429 unsigned obj_f = c->pop_pack (false);
430
431 start_object ("d", 1, c);
432 add_offset (obj_f, c);
433 unsigned obj_d = c->pop_pack (false);
434
435 unsigned obj_g = add_object ("g", 1, c);
436
437 start_object (large_string.c_str (), 40000, c);
438 add_offset (obj_g, c);
439 unsigned obj_e = c->pop_pack (false);
440
441 unsigned obj_h = add_object ("h", 1, c);
442
443 start_object ("b", 1, c);
444 add_offset (obj_e, c);
445 add_offset (obj_h, c);
446 unsigned obj_b = c->pop_pack (false);
447
448 start_object ("a", 1, c);
449 add_offset (obj_b, c);
450 add_wide_offset (obj_c, c);
451 add_wide_offset (obj_d, c);
452 c->pop_pack (false);
453
454 c->end_serialize ();
455 }
456
457 static void
populate_serializer_short_and_wide_subgraph_root(hb_serialize_context_t * c)458 populate_serializer_short_and_wide_subgraph_root (hb_serialize_context_t* c)
459 {
460 std::string large_string(70000, 'a');
461 c->start_serialize<char> ();
462
463 unsigned obj_e = add_object ("e", 1, c);
464
465 start_object (large_string.c_str (), 40000, c);
466 add_offset (obj_e, c);
467 unsigned obj_c = c->pop_pack (false);
468
469 start_object (large_string.c_str (), 40000, c);
470 add_offset (obj_c, c);
471 unsigned obj_d = c->pop_pack (false);
472
473 start_object ("b", 1, c);
474 add_offset (obj_c, c);
475 add_offset (obj_e, c);
476 unsigned obj_b = c->pop_pack (false);
477
478 start_object ("a", 1, c);
479 add_offset (obj_b, c);
480 add_wide_offset (obj_c, c);
481 add_wide_offset (obj_d, c);
482 c->pop_pack (false);
483
484 c->end_serialize();
485 }
486
487 static void
populate_serializer_short_and_wide_subgraph_root_expected(hb_serialize_context_t * c)488 populate_serializer_short_and_wide_subgraph_root_expected (hb_serialize_context_t* c)
489 {
490 std::string large_string(70000, 'a');
491 c->start_serialize<char> ();
492
493 unsigned obj_e_prime = add_object ("e", 1, c);
494
495 start_object (large_string.c_str (), 40000, c);
496 add_offset (obj_e_prime, c);
497 unsigned obj_c_prime = c->pop_pack (false);
498
499 start_object (large_string.c_str (), 40000, c);
500 add_offset (obj_c_prime, c);
501 unsigned obj_d = c->pop_pack (false);
502
503 unsigned obj_e = add_object ("e", 1, c);
504
505 start_object (large_string.c_str (), 40000, c);
506 add_offset (obj_e, c);
507 unsigned obj_c = c->pop_pack (false);
508
509
510 start_object ("b", 1, c);
511 add_offset (obj_c, c);
512 add_offset (obj_e, c);
513 unsigned obj_b = c->pop_pack (false);
514
515 start_object ("a", 1, c);
516 add_offset (obj_b, c);
517 add_wide_offset (obj_c_prime, c);
518 add_wide_offset (obj_d, c);
519 c->pop_pack (false);
520
521 c->end_serialize();
522 }
523
524 static void
populate_serializer_with_split_spaces(hb_serialize_context_t * c)525 populate_serializer_with_split_spaces (hb_serialize_context_t* c)
526 {
527 // Overflow needs to be resolved by splitting the single space
528 std::string large_string(70000, 'a');
529 c->start_serialize<char> ();
530
531 unsigned obj_f = add_object ("f", 1, c);
532
533 start_object (large_string.c_str(), 40000, c);
534 add_offset (obj_f, c);
535 unsigned obj_d = c->pop_pack (false);
536
537 start_object (large_string.c_str(), 40000, c);
538 add_offset (obj_f, c);
539 unsigned obj_e = c->pop_pack (false);
540
541 start_object ("b", 1, c);
542 add_offset (obj_d, c);
543 unsigned obj_b = c->pop_pack (false);
544
545 start_object ("c", 1, c);
546 add_offset (obj_e, c);
547 unsigned obj_c = c->pop_pack (false);
548
549 start_object ("a", 1, c);
550 add_wide_offset (obj_b, c);
551 add_wide_offset (obj_c, c);
552 c->pop_pack (false);
553
554 c->end_serialize();
555 }
556
557 static void
populate_serializer_with_split_spaces_2(hb_serialize_context_t * c)558 populate_serializer_with_split_spaces_2 (hb_serialize_context_t* c)
559 {
560 // Overflow needs to be resolved by splitting the single space
561 std::string large_string(70000, 'a');
562 c->start_serialize<char> ();
563
564 unsigned obj_f = add_object ("f", 1, c);
565
566 start_object (large_string.c_str(), 40000, c);
567 add_offset (obj_f, c);
568 unsigned obj_d = c->pop_pack (false);
569
570 start_object (large_string.c_str(), 40000, c);
571 add_offset (obj_f, c);
572 unsigned obj_e = c->pop_pack (false);
573
574 start_object ("b", 1, c);
575 add_offset (obj_d, c);
576 unsigned obj_b = c->pop_pack (false);
577
578 start_object ("c", 1, c);
579 add_offset (obj_e, c);
580 unsigned obj_c = c->pop_pack (false);
581
582 start_object ("a", 1, c);
583 add_offset (obj_b, c);
584 add_wide_offset (obj_b, c);
585 add_wide_offset (obj_c, c);
586 c->pop_pack (false);
587
588 c->end_serialize();
589 }
590
591 static void
populate_serializer_with_split_spaces_expected(hb_serialize_context_t * c)592 populate_serializer_with_split_spaces_expected (hb_serialize_context_t* c)
593 {
594 // Overflow needs to be resolved by splitting the single space
595
596 std::string large_string(70000, 'a');
597 c->start_serialize<char> ();
598
599 unsigned obj_f_prime = add_object ("f", 1, c);
600
601 start_object (large_string.c_str(), 40000, c);
602 add_offset (obj_f_prime, c);
603 unsigned obj_d = c->pop_pack (false);
604
605 start_object ("b", 1, c);
606 add_offset (obj_d, c);
607 unsigned obj_b = c->pop_pack (false);
608
609 unsigned obj_f = add_object ("f", 1, c);
610
611 start_object (large_string.c_str(), 40000, c);
612 add_offset (obj_f, c);
613 unsigned obj_e = c->pop_pack (false);
614
615 start_object ("c", 1, c);
616 add_offset (obj_e, c);
617 unsigned obj_c = c->pop_pack (false);
618
619 start_object ("a", 1, c);
620 add_wide_offset (obj_b, c);
621 add_wide_offset (obj_c, c);
622 c->pop_pack (false);
623
624 c->end_serialize();
625 }
626
627 static void
populate_serializer_with_split_spaces_expected_2(hb_serialize_context_t * c)628 populate_serializer_with_split_spaces_expected_2 (hb_serialize_context_t* c)
629 {
630 // Overflow needs to be resolved by splitting the single space
631
632 std::string large_string(70000, 'a');
633 c->start_serialize<char> ();
634
635 // Space 2
636
637 unsigned obj_f_double_prime = add_object ("f", 1, c);
638
639 start_object (large_string.c_str(), 40000, c);
640 add_offset (obj_f_double_prime, c);
641 unsigned obj_d_prime = c->pop_pack (false);
642
643 start_object ("b", 1, c);
644 add_offset (obj_d_prime, c);
645 unsigned obj_b_prime = c->pop_pack (false);
646
647 // Space 1
648
649 unsigned obj_f_prime = add_object ("f", 1, c);
650
651 start_object (large_string.c_str(), 40000, c);
652 add_offset (obj_f_prime, c);
653 unsigned obj_e = c->pop_pack (false);
654
655 start_object ("c", 1, c);
656 add_offset (obj_e, c);
657 unsigned obj_c = c->pop_pack (false);
658
659 // Space 0
660
661 unsigned obj_f = add_object ("f", 1, c);
662
663 start_object (large_string.c_str(), 40000, c);
664 add_offset (obj_f, c);
665 unsigned obj_d = c->pop_pack (false);
666
667 start_object ("b", 1, c);
668 add_offset (obj_d, c);
669 unsigned obj_b = c->pop_pack (false);
670
671 // Root
672 start_object ("a", 1, c);
673 add_offset (obj_b, c);
674 add_wide_offset (obj_b_prime, c);
675 add_wide_offset (obj_c, c);
676 c->pop_pack (false);
677
678 c->end_serialize();
679 }
680
681 static void
populate_serializer_complex_1(hb_serialize_context_t * c)682 populate_serializer_complex_1 (hb_serialize_context_t* c)
683 {
684 c->start_serialize<char> ();
685
686 unsigned obj_4 = add_object ("jkl", 3, c);
687 unsigned obj_3 = add_object ("ghi", 3, c);
688
689 start_object ("def", 3, c);
690 add_offset (obj_3, c);
691 unsigned obj_2 = c->pop_pack (false);
692
693 start_object ("abc", 3, c);
694 add_offset (obj_2, c);
695 add_offset (obj_4, c);
696 c->pop_pack (false);
697
698 c->end_serialize();
699 }
700
701 static void
populate_serializer_complex_2(hb_serialize_context_t * c)702 populate_serializer_complex_2 (hb_serialize_context_t* c)
703 {
704 c->start_serialize<char> ();
705
706 unsigned obj_5 = add_object ("mn", 2, c);
707
708 unsigned obj_4 = add_object ("jkl", 3, c);
709
710 start_object ("ghi", 3, c);
711 add_offset (obj_4, c);
712 unsigned obj_3 = c->pop_pack (false);
713
714 start_object ("def", 3, c);
715 add_offset (obj_3, c);
716 unsigned obj_2 = c->pop_pack (false);
717
718 start_object ("abc", 3, c);
719 add_offset (obj_2, c);
720 add_offset (obj_4, c);
721 add_offset (obj_5, c);
722 c->pop_pack (false);
723
724 c->end_serialize();
725 }
726
727 static void
populate_serializer_complex_3(hb_serialize_context_t * c)728 populate_serializer_complex_3 (hb_serialize_context_t* c)
729 {
730 c->start_serialize<char> ();
731
732 unsigned obj_6 = add_object ("opqrst", 6, c);
733
734 unsigned obj_5 = add_object ("mn", 2, c);
735
736 start_object ("jkl", 3, c);
737 add_offset (obj_6, c);
738 unsigned obj_4 = c->pop_pack (false);
739
740 start_object ("ghi", 3, c);
741 add_offset (obj_4, c);
742 unsigned obj_3 = c->pop_pack (false);
743
744 start_object ("def", 3, c);
745 add_offset (obj_3, c);
746 unsigned obj_2 = c->pop_pack (false);
747
748 start_object ("abc", 3, c);
749 add_offset (obj_2, c);
750 add_offset (obj_4, c);
751 add_offset (obj_5, c);
752 c->pop_pack (false);
753
754 c->end_serialize();
755 }
756
757 static void
populate_serializer_virtual_link(hb_serialize_context_t * c)758 populate_serializer_virtual_link (hb_serialize_context_t* c)
759 {
760 c->start_serialize<char> ();
761
762 unsigned obj_d = add_object ("d", 1, c);
763
764 start_object ("b", 1, c);
765 add_offset (obj_d, c);
766 unsigned obj_b = c->pop_pack ();
767
768 start_object ("e", 1, c);
769 add_virtual_offset (obj_b, c);
770 unsigned obj_e = c->pop_pack();
771
772 start_object ("c", 1, c);
773 add_offset (obj_e, c);
774 unsigned obj_c = c->pop_pack ();
775
776 start_object ("a", 1, c);
777 add_offset (obj_b, c);
778 add_offset (obj_c, c);
779 c->pop_pack ();
780
781 c->end_serialize();
782 }
783
test_sort_kahn_1()784 static void test_sort_kahn_1 ()
785 {
786 size_t buffer_size = 100;
787 void* buffer = malloc (buffer_size);
788 hb_serialize_context_t c (buffer, buffer_size);
789 populate_serializer_complex_1 (&c);
790
791 graph_t graph (c.object_graph ());
792 graph.sort_kahn ();
793
794 assert(strncmp (graph.object (3).head, "abc", 3) == 0);
795 assert(graph.object (3).links.length == 2);
796 assert(graph.object (3).links[0].objidx == 2);
797 assert(graph.object (3).links[1].objidx == 1);
798
799 assert(strncmp (graph.object (2).head, "def", 3) == 0);
800 assert(graph.object (2).links.length == 1);
801 assert(graph.object (2).links[0].objidx == 0);
802
803 assert(strncmp (graph.object (1).head, "jkl", 3) == 0);
804 assert(graph.object (1).links.length == 0);
805
806 assert(strncmp (graph.object (0).head, "ghi", 3) == 0);
807 assert(graph.object (0).links.length == 0);
808
809 free (buffer);
810 }
811
test_sort_kahn_2()812 static void test_sort_kahn_2 ()
813 {
814 size_t buffer_size = 100;
815 void* buffer = malloc (buffer_size);
816 hb_serialize_context_t c (buffer, buffer_size);
817 populate_serializer_complex_2 (&c);
818
819 graph_t graph (c.object_graph ());
820 graph.sort_kahn ();
821
822
823 assert(strncmp (graph.object (4).head, "abc", 3) == 0);
824 assert(graph.object (4).links.length == 3);
825 assert(graph.object (4).links[0].objidx == 3);
826 assert(graph.object (4).links[1].objidx == 0);
827 assert(graph.object (4).links[2].objidx == 2);
828
829 assert(strncmp (graph.object (3).head, "def", 3) == 0);
830 assert(graph.object (3).links.length == 1);
831 assert(graph.object (3).links[0].objidx == 1);
832
833 assert(strncmp (graph.object (2).head, "mn", 2) == 0);
834 assert(graph.object (2).links.length == 0);
835
836 assert(strncmp (graph.object (1).head, "ghi", 3) == 0);
837 assert(graph.object (1).links.length == 1);
838 assert(graph.object (1).links[0].objidx == 0);
839
840 assert(strncmp (graph.object (0).head, "jkl", 3) == 0);
841 assert(graph.object (0).links.length == 0);
842
843 free (buffer);
844 }
845
test_sort_shortest()846 static void test_sort_shortest ()
847 {
848 size_t buffer_size = 100;
849 void* buffer = malloc (buffer_size);
850 hb_serialize_context_t c (buffer, buffer_size);
851 populate_serializer_complex_2 (&c);
852
853 graph_t graph (c.object_graph ());
854 graph.sort_shortest_distance ();
855
856 assert(strncmp (graph.object (4).head, "abc", 3) == 0);
857 assert(graph.object (4).links.length == 3);
858 assert(graph.object (4).links[0].objidx == 2);
859 assert(graph.object (4).links[1].objidx == 0);
860 assert(graph.object (4).links[2].objidx == 3);
861
862 assert(strncmp (graph.object (3).head, "mn", 2) == 0);
863 assert(graph.object (3).links.length == 0);
864
865 assert(strncmp (graph.object (2).head, "def", 3) == 0);
866 assert(graph.object (2).links.length == 1);
867 assert(graph.object (2).links[0].objidx == 1);
868
869 assert(strncmp (graph.object (1).head, "ghi", 3) == 0);
870 assert(graph.object (1).links.length == 1);
871 assert(graph.object (1).links[0].objidx == 0);
872
873 assert(strncmp (graph.object (0).head, "jkl", 3) == 0);
874 assert(graph.object (0).links.length == 0);
875
876 free (buffer);
877 }
878
test_duplicate_leaf()879 static void test_duplicate_leaf ()
880 {
881 size_t buffer_size = 100;
882 void* buffer = malloc (buffer_size);
883 hb_serialize_context_t c (buffer, buffer_size);
884 populate_serializer_complex_2 (&c);
885
886 graph_t graph (c.object_graph ());
887 graph.duplicate (4, 1);
888
889 assert(strncmp (graph.object (5).head, "abc", 3) == 0);
890 assert(graph.object (5).links.length == 3);
891 assert(graph.object (5).links[0].objidx == 3);
892 assert(graph.object (5).links[1].objidx == 4);
893 assert(graph.object (5).links[2].objidx == 0);
894
895 assert(strncmp (graph.object (4).head, "jkl", 3) == 0);
896 assert(graph.object (4).links.length == 0);
897
898 assert(strncmp (graph.object (3).head, "def", 3) == 0);
899 assert(graph.object (3).links.length == 1);
900 assert(graph.object (3).links[0].objidx == 2);
901
902 assert(strncmp (graph.object (2).head, "ghi", 3) == 0);
903 assert(graph.object (2).links.length == 1);
904 assert(graph.object (2).links[0].objidx == 1);
905
906 assert(strncmp (graph.object (1).head, "jkl", 3) == 0);
907 assert(graph.object (1).links.length == 0);
908
909 assert(strncmp (graph.object (0).head, "mn", 2) == 0);
910 assert(graph.object (0).links.length == 0);
911
912 free (buffer);
913 }
914
test_duplicate_interior()915 static void test_duplicate_interior ()
916 {
917 size_t buffer_size = 100;
918 void* buffer = malloc (buffer_size);
919 hb_serialize_context_t c (buffer, buffer_size);
920 populate_serializer_complex_3 (&c);
921
922 graph_t graph (c.object_graph ());
923 graph.duplicate (3, 2);
924
925 assert(strncmp (graph.object (6).head, "abc", 3) == 0);
926 assert(graph.object (6).links.length == 3);
927 assert(graph.object (6).links[0].objidx == 4);
928 assert(graph.object (6).links[1].objidx == 2);
929 assert(graph.object (6).links[2].objidx == 1);
930
931 assert(strncmp (graph.object (5).head, "jkl", 3) == 0);
932 assert(graph.object (5).links.length == 1);
933 assert(graph.object (5).links[0].objidx == 0);
934
935 assert(strncmp (graph.object (4).head, "def", 3) == 0);
936 assert(graph.object (4).links.length == 1);
937 assert(graph.object (4).links[0].objidx == 3);
938
939 assert(strncmp (graph.object (3).head, "ghi", 3) == 0);
940 assert(graph.object (3).links.length == 1);
941 assert(graph.object (3).links[0].objidx == 5);
942
943 assert(strncmp (graph.object (2).head, "jkl", 3) == 0);
944 assert(graph.object (2).links.length == 1);
945 assert(graph.object (2).links[0].objidx == 0);
946
947 assert(strncmp (graph.object (1).head, "mn", 2) == 0);
948 assert(graph.object (1).links.length == 0);
949
950 assert(strncmp (graph.object (0).head, "opqrst", 6) == 0);
951 assert(graph.object (0).links.length == 0);
952
953 free (buffer);
954 }
955
956 static void
test_serialize()957 test_serialize ()
958 {
959 size_t buffer_size = 100;
960 void* buffer_1 = malloc (buffer_size);
961 hb_serialize_context_t c1 (buffer_1, buffer_size);
962 populate_serializer_simple (&c1);
963 hb_bytes_t expected = c1.copy_bytes ();
964
965 void* buffer_2 = malloc (buffer_size);
966 hb_serialize_context_t c2 (buffer_2, buffer_size);
967
968 graph_t graph (c1.object_graph ());
969 graph.serialize (&c2);
970 hb_bytes_t actual = c2.copy_bytes ();
971
972 assert (actual == expected);
973
974 actual.fini ();
975 expected.fini ();
976 free (buffer_1);
977 free (buffer_2);
978 }
979
test_will_overflow_1()980 static void test_will_overflow_1 ()
981 {
982 size_t buffer_size = 100;
983 void* buffer = malloc (buffer_size);
984 hb_serialize_context_t c (buffer, buffer_size);
985 populate_serializer_complex_2 (&c);
986 graph_t graph (c.object_graph ());
987
988 assert (!graph.will_overflow (nullptr));
989
990 free (buffer);
991 }
992
test_will_overflow_2()993 static void test_will_overflow_2 ()
994 {
995 size_t buffer_size = 160000;
996 void* buffer = malloc (buffer_size);
997 hb_serialize_context_t c (buffer, buffer_size);
998 populate_serializer_with_overflow (&c);
999 graph_t graph (c.object_graph ());
1000
1001 assert (graph.will_overflow (nullptr));
1002
1003 free (buffer);
1004 }
1005
test_will_overflow_3()1006 static void test_will_overflow_3 ()
1007 {
1008 size_t buffer_size = 160000;
1009 void* buffer = malloc (buffer_size);
1010 hb_serialize_context_t c (buffer, buffer_size);
1011 populate_serializer_with_dedup_overflow (&c);
1012 graph_t graph (c.object_graph ());
1013
1014 assert (graph.will_overflow (nullptr));
1015
1016 free (buffer);
1017 }
1018
test_resolve_overflows_via_sort()1019 static void test_resolve_overflows_via_sort ()
1020 {
1021 size_t buffer_size = 160000;
1022 void* buffer = malloc (buffer_size);
1023 hb_serialize_context_t c (buffer, buffer_size);
1024 populate_serializer_with_overflow (&c);
1025 graph_t graph (c.object_graph ());
1026
1027 void* out_buffer = malloc (buffer_size);
1028 hb_serialize_context_t out (out_buffer, buffer_size);
1029
1030 hb_resolve_overflows (c.object_graph (), HB_TAG_NONE, &out);
1031 assert (!out.offset_overflow ());
1032 hb_bytes_t result = out.copy_bytes ();
1033 assert (result.length == (80000 + 3 + 3 * 2));
1034
1035 result.fini ();
1036 free (buffer);
1037 free (out_buffer);
1038 }
1039
test_resolve_overflows_via_duplication()1040 static void test_resolve_overflows_via_duplication ()
1041 {
1042 size_t buffer_size = 160000;
1043 void* buffer = malloc (buffer_size);
1044 hb_serialize_context_t c (buffer, buffer_size);
1045 populate_serializer_with_dedup_overflow (&c);
1046 graph_t graph (c.object_graph ());
1047
1048 void* out_buffer = malloc (buffer_size);
1049 hb_serialize_context_t out (out_buffer, buffer_size);
1050
1051 hb_resolve_overflows (c.object_graph (), HB_TAG_NONE, &out);
1052 assert (!out.offset_overflow ());
1053 hb_bytes_t result = out.copy_bytes ();
1054 assert (result.length == (10000 + 2 * 2 + 60000 + 2 + 3 * 2));
1055
1056 result.fini ();
1057 free (buffer);
1058 free (out_buffer);
1059 }
1060
test_resolve_overflows_via_space_assignment()1061 static void test_resolve_overflows_via_space_assignment ()
1062 {
1063 size_t buffer_size = 160000;
1064 void* buffer = malloc (buffer_size);
1065 hb_serialize_context_t c (buffer, buffer_size);
1066 populate_serializer_spaces (&c, true);
1067
1068 void* expected_buffer = malloc (buffer_size);
1069 hb_serialize_context_t e (expected_buffer, buffer_size);
1070 populate_serializer_spaces (&e, false);
1071
1072 run_resolve_overflow_test ("test_resolve_overflows_via_space_assignment",
1073 c,
1074 e);
1075
1076 free (buffer);
1077 free (expected_buffer);
1078 }
1079
test_resolve_overflows_via_isolation()1080 static void test_resolve_overflows_via_isolation ()
1081 {
1082 size_t buffer_size = 160000;
1083 void* buffer = malloc (buffer_size);
1084 hb_serialize_context_t c (buffer, buffer_size);
1085 populate_serializer_with_isolation_overflow (&c);
1086 graph_t graph (c.object_graph ());
1087
1088 void* out_buffer = malloc (buffer_size);
1089 hb_serialize_context_t out (out_buffer, buffer_size);
1090
1091 assert (c.offset_overflow ());
1092 hb_resolve_overflows (c.object_graph (), HB_TAG ('G', 'S', 'U', 'B'), &out, 0);
1093 assert (!out.offset_overflow ());
1094 hb_bytes_t result = out.copy_bytes ();
1095 assert (result.length == (1 + 10000 + 60000 + 1 + 1
1096 + 4 + 3 * 2));
1097
1098 result.fini ();
1099 free (buffer);
1100 free (out_buffer);
1101 }
1102
test_resolve_overflows_via_isolation_with_recursive_duplication()1103 static void test_resolve_overflows_via_isolation_with_recursive_duplication ()
1104 {
1105 size_t buffer_size = 160000;
1106 void* buffer = malloc (buffer_size);
1107 hb_serialize_context_t c (buffer, buffer_size);
1108 populate_serializer_with_isolation_overflow_complex (&c);
1109
1110 void* expected_buffer = malloc (buffer_size);
1111 hb_serialize_context_t e (expected_buffer, buffer_size);
1112 populate_serializer_with_isolation_overflow_complex_expected (&e);
1113
1114 run_resolve_overflow_test ("test_resolve_overflows_via_isolation_with_recursive_duplication",
1115 c,
1116 e);
1117 free (buffer);
1118 free (expected_buffer);
1119 }
1120
test_resolve_overflows_via_isolating_16bit_space()1121 static void test_resolve_overflows_via_isolating_16bit_space ()
1122 {
1123 size_t buffer_size = 160000;
1124 void* buffer = malloc (buffer_size);
1125 hb_serialize_context_t c (buffer, buffer_size);
1126 populate_serializer_spaces_16bit_connection (&c);
1127
1128 void* expected_buffer = malloc (buffer_size);
1129 hb_serialize_context_t e (expected_buffer, buffer_size);
1130 populate_serializer_spaces_16bit_connection_expected (&e);
1131
1132 run_resolve_overflow_test ("test_resolve_overflows_via_isolating_16bit_space",
1133 c,
1134 e);
1135
1136 free (buffer);
1137 free (expected_buffer);
1138 }
1139
test_resolve_overflows_via_isolating_16bit_space_2()1140 static void test_resolve_overflows_via_isolating_16bit_space_2 ()
1141 {
1142 size_t buffer_size = 160000;
1143 void* buffer = malloc (buffer_size);
1144 hb_serialize_context_t c (buffer, buffer_size);
1145 populate_serializer_short_and_wide_subgraph_root (&c);
1146
1147 void* expected_buffer = malloc (buffer_size);
1148 hb_serialize_context_t e (expected_buffer, buffer_size);
1149 populate_serializer_short_and_wide_subgraph_root_expected (&e);
1150
1151 run_resolve_overflow_test ("test_resolve_overflows_via_isolating_16bit_space_2",
1152 c,
1153 e);
1154
1155 free (buffer);
1156 free (expected_buffer);
1157 }
1158
test_resolve_overflows_via_isolation_spaces()1159 static void test_resolve_overflows_via_isolation_spaces ()
1160 {
1161 size_t buffer_size = 160000;
1162 void* buffer = malloc (buffer_size);
1163 hb_serialize_context_t c (buffer, buffer_size);
1164 populate_serializer_with_isolation_overflow_spaces (&c);
1165 graph_t graph (c.object_graph ());
1166
1167 void* out_buffer = malloc (buffer_size);
1168 hb_serialize_context_t out (out_buffer, buffer_size);
1169
1170 assert (c.offset_overflow ());
1171 hb_resolve_overflows (c.object_graph (), HB_TAG ('G', 'S', 'U', 'B'), &out, 0);
1172 assert (!out.offset_overflow ());
1173 hb_bytes_t result = out.copy_bytes ();
1174
1175 unsigned expected_length = 3 + 2 * 60000; // objects
1176 expected_length += 2 * 4 + 2 * 2; // links
1177 assert (result.length == expected_length);
1178
1179 result.fini ();
1180 free (buffer);
1181 free (out_buffer);
1182 }
1183
test_resolve_overflows_via_splitting_spaces()1184 static void test_resolve_overflows_via_splitting_spaces ()
1185 {
1186 size_t buffer_size = 160000;
1187 void* buffer = malloc (buffer_size);
1188 hb_serialize_context_t c (buffer, buffer_size);
1189 populate_serializer_with_split_spaces (&c);
1190
1191 void* expected_buffer = malloc (buffer_size);
1192 hb_serialize_context_t e (expected_buffer, buffer_size);
1193 populate_serializer_with_split_spaces_expected (&e);
1194
1195 run_resolve_overflow_test ("test_resolve_overflows_via_splitting_spaces",
1196 c,
1197 e,
1198 1);
1199
1200 free (buffer);
1201 free (expected_buffer);
1202
1203 }
1204
test_resolve_overflows_via_splitting_spaces_2()1205 static void test_resolve_overflows_via_splitting_spaces_2 ()
1206 {
1207 size_t buffer_size = 160000;
1208 void* buffer = malloc (buffer_size);
1209 hb_serialize_context_t c (buffer, buffer_size);
1210 populate_serializer_with_split_spaces_2 (&c);
1211
1212 void* expected_buffer = malloc (buffer_size);
1213 hb_serialize_context_t e (expected_buffer, buffer_size);
1214 populate_serializer_with_split_spaces_expected_2 (&e);
1215
1216 run_resolve_overflow_test ("test_resolve_overflows_via_splitting_spaces_2",
1217 c,
1218 e,
1219 1);
1220 free (buffer);
1221 free (expected_buffer);
1222 }
1223
test_virtual_link()1224 static void test_virtual_link ()
1225 {
1226 size_t buffer_size = 100;
1227 void* buffer = malloc (buffer_size);
1228 hb_serialize_context_t c (buffer, buffer_size);
1229 populate_serializer_virtual_link (&c);
1230
1231 void* out_buffer = malloc (buffer_size);
1232 hb_serialize_context_t out (out_buffer, buffer_size);
1233
1234 hb_resolve_overflows (c.object_graph (), HB_TAG_NONE, &out);
1235 assert (!out.offset_overflow ());
1236
1237 hb_bytes_t result = out.copy_bytes ();
1238 assert (result.length == 5 + 4 * 2);
1239 assert (result[0] == 'a');
1240 assert (result[5] == 'c');
1241 assert (result[8] == 'e');
1242 assert (result[9] == 'b');
1243 assert (result[12] == 'd');
1244
1245 result.fini ();
1246 free (buffer);
1247 free (out_buffer);
1248 }
1249
1250 // TODO(garretrieger): update will_overflow tests to check the overflows array.
1251 // TODO(garretrieger): add tests for priority raising.
1252
1253 int
main(int argc,char ** argv)1254 main (int argc, char **argv)
1255 {
1256 test_serialize ();
1257 test_sort_kahn_1 ();
1258 test_sort_kahn_2 ();
1259 test_sort_shortest ();
1260 test_will_overflow_1 ();
1261 test_will_overflow_2 ();
1262 test_will_overflow_3 ();
1263 test_resolve_overflows_via_sort ();
1264 test_resolve_overflows_via_duplication ();
1265 test_resolve_overflows_via_space_assignment ();
1266 test_resolve_overflows_via_isolation ();
1267 test_resolve_overflows_via_isolation_with_recursive_duplication ();
1268 test_resolve_overflows_via_isolation_spaces ();
1269 test_resolve_overflows_via_isolating_16bit_space ();
1270 test_resolve_overflows_via_isolating_16bit_space_2 ();
1271 test_resolve_overflows_via_splitting_spaces ();
1272 test_resolve_overflows_via_splitting_spaces_2 ();
1273 test_duplicate_leaf ();
1274 test_duplicate_interior ();
1275 test_virtual_link ();
1276 }
1277