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 "gsubgpos-context.hh"
28 #include "classdef-graph.hh"
29 #include "hb-iter.hh"
30 #include "hb-serialize.hh"
31
32 typedef hb_codepoint_pair_t gid_and_class_t;
33 typedef hb_vector_t<gid_and_class_t> gid_and_class_list_t;
34
35 template<typename It>
actual_class_def_size(It glyph_and_class)36 static unsigned actual_class_def_size(It glyph_and_class) {
37 char buffer[100];
38 hb_serialize_context_t serializer(buffer, 100);
39 OT::ClassDef_serialize (&serializer, glyph_and_class);
40 serializer.end_serialize ();
41 assert(!serializer.in_error());
42
43 hb_blob_t* blob = serializer.copy_blob();
44 unsigned size = hb_blob_get_length(blob);
45 hb_blob_destroy(blob);
46 return size;
47 }
48
actual_class_def_size(gid_and_class_list_t consecutive_map,hb_vector_t<unsigned> classes)49 static unsigned actual_class_def_size(gid_and_class_list_t consecutive_map, hb_vector_t<unsigned> classes) {
50 auto filtered_it =
51 + consecutive_map.as_sorted_array().iter()
52 | hb_filter([&] (unsigned c) {
53 for (unsigned klass : classes) {
54 if (c == klass) {
55 return true;
56 }
57 }
58 return false;
59 }, hb_second);
60 return actual_class_def_size(+ filtered_it);
61 }
62
63 template<typename It>
actual_coverage_size(It glyphs)64 static unsigned actual_coverage_size(It glyphs) {
65 char buffer[100];
66 hb_serialize_context_t serializer(buffer, 100);
67 OT::Layout::Common::Coverage_serialize (&serializer, glyphs);
68 serializer.end_serialize ();
69 assert(!serializer.in_error());
70
71 hb_blob_t* blob = serializer.copy_blob();
72 unsigned size = hb_blob_get_length(blob);
73 hb_blob_destroy(blob);
74 return size;
75 }
76
actual_coverage_size(gid_and_class_list_t consecutive_map,hb_vector_t<unsigned> classes)77 static unsigned actual_coverage_size(gid_and_class_list_t consecutive_map, hb_vector_t<unsigned> classes) {
78 auto filtered_it =
79 + consecutive_map.as_sorted_array().iter()
80 | hb_filter([&] (unsigned c) {
81 for (unsigned klass : classes) {
82 if (c == klass) {
83 return true;
84 }
85 }
86 return false;
87 }, hb_second);
88 return actual_coverage_size(+ filtered_it | hb_map_retains_sorting(hb_first));
89 }
90
check_coverage_size(graph::class_def_size_estimator_t & estimator,const gid_and_class_list_t & map,hb_vector_t<unsigned> klasses)91 static bool check_coverage_size(graph::class_def_size_estimator_t& estimator,
92 const gid_and_class_list_t& map,
93 hb_vector_t<unsigned> klasses)
94 {
95 unsigned result = estimator.coverage_size();
96 unsigned expected = actual_coverage_size(map, klasses);
97 if (result != expected) {
98 printf ("FAIL: estimated coverage expected size %u but was %u\n", expected, result);
99 return false;
100 }
101 return true;
102 }
103
check_add_class_def_size(graph::class_def_size_estimator_t & estimator,const gid_and_class_list_t & map,unsigned klass,hb_vector_t<unsigned> klasses)104 static bool check_add_class_def_size(graph::class_def_size_estimator_t& estimator,
105 const gid_and_class_list_t& map,
106 unsigned klass, hb_vector_t<unsigned> klasses)
107 {
108 unsigned result = estimator.add_class_def_size(klass);
109 unsigned expected = actual_class_def_size(map, klasses);
110 if (result != expected) {
111 printf ("FAIL: estimated class def expected size %u but was %u\n", expected, result);
112 return false;
113 }
114
115 return check_coverage_size(estimator, map, klasses);
116 }
117
check_add_class_def_size(const gid_and_class_list_t & list,unsigned klass)118 static bool check_add_class_def_size (const gid_and_class_list_t& list, unsigned klass)
119 {
120 graph::class_def_size_estimator_t estimator (list.iter ());
121
122 unsigned result = estimator.add_class_def_size (klass);
123 auto filtered_it =
124 + list.as_sorted_array().iter()
125 | hb_filter([&] (unsigned c) {
126 return c == klass;
127 }, hb_second);
128
129 unsigned expected = actual_class_def_size(filtered_it);
130 if (result != expected)
131 {
132 printf ("FAIL: class def expected size %u but was %u\n", expected, result);
133 return false;
134 }
135
136 auto cov_it = + filtered_it | hb_map_retains_sorting(hb_first);
137 result = estimator.coverage_size ();
138 expected = actual_coverage_size(cov_it);
139 if (result != expected)
140 {
141 printf ("FAIL: coverage expected size %u but was %u\n", expected, result);
142 return false;
143 }
144
145 return true;
146 }
147
test_class_and_coverage_size_estimates()148 static void test_class_and_coverage_size_estimates ()
149 {
150 gid_and_class_list_t empty = {
151 };
152 assert (check_add_class_def_size (empty, 0));
153 assert (check_add_class_def_size (empty, 1));
154
155 gid_and_class_list_t class_zero = {
156 {5, 0},
157 };
158 assert (check_add_class_def_size (class_zero, 0));
159
160 gid_and_class_list_t consecutive = {
161 {4, 0},
162 {5, 0},
163
164 {6, 1},
165 {7, 1},
166
167 {8, 2},
168 {9, 2},
169 {10, 2},
170 {11, 2},
171 };
172 assert (check_add_class_def_size (consecutive, 0));
173 assert (check_add_class_def_size (consecutive, 1));
174 assert (check_add_class_def_size (consecutive, 2));
175
176 gid_and_class_list_t non_consecutive = {
177 {4, 0},
178 {6, 0},
179
180 {8, 1},
181 {10, 1},
182
183 {9, 2},
184 {10, 2},
185 {11, 2},
186 {13, 2},
187 };
188 assert (check_add_class_def_size (non_consecutive, 0));
189 assert (check_add_class_def_size (non_consecutive, 1));
190 assert (check_add_class_def_size (non_consecutive, 2));
191
192 gid_and_class_list_t multiple_ranges = {
193 {4, 0},
194 {5, 0},
195
196 {6, 1},
197 {7, 1},
198
199 {9, 1},
200
201 {11, 1},
202 {12, 1},
203 {13, 1},
204 };
205 assert (check_add_class_def_size (multiple_ranges, 0));
206 assert (check_add_class_def_size (multiple_ranges, 1));
207 }
208
test_running_class_and_coverage_size_estimates()209 static void test_running_class_and_coverage_size_estimates () {
210 // #### With consecutive gids: switches formats ###
211 gid_and_class_list_t consecutive_map = {
212 // range 1-4 (f1: 8 bytes), (f2: 6 bytes)
213 {1, 1},
214 {2, 1},
215 {3, 1},
216 {4, 1},
217
218 // (f1: 2 bytes), (f2: 6 bytes)
219 {5, 2},
220
221 // (f1: 14 bytes), (f2: 6 bytes)
222 {6, 3},
223 {7, 3},
224 {8, 3},
225 {9, 3},
226 {10, 3},
227 {11, 3},
228 {12, 3},
229 };
230
231 graph::class_def_size_estimator_t estimator1(consecutive_map.iter());
232 assert(check_add_class_def_size(estimator1, consecutive_map, 1, {1}));
233 assert(check_add_class_def_size(estimator1, consecutive_map, 2, {1, 2}));
234 assert(check_add_class_def_size(estimator1, consecutive_map, 2, {1, 2})); // check that adding the same class again works
235 assert(check_add_class_def_size(estimator1, consecutive_map, 3, {1, 2, 3}));
236
237 estimator1.reset();
238 assert(check_add_class_def_size(estimator1, consecutive_map, 2, {2}));
239 assert(check_add_class_def_size(estimator1, consecutive_map, 3, {2, 3}));
240
241 // #### With non-consecutive gids: always uses format 2 ###
242 gid_and_class_list_t non_consecutive_map = {
243 // range 1-4 (f1: 8 bytes), (f2: 6 bytes)
244 {1, 1},
245 {2, 1},
246 {3, 1},
247 {4, 1},
248
249 // (f1: 2 bytes), (f2: 12 bytes)
250 {6, 2},
251 {8, 2},
252
253 // (f1: 14 bytes), (f2: 6 bytes)
254 {9, 3},
255 {10, 3},
256 {11, 3},
257 {12, 3},
258 {13, 3},
259 {14, 3},
260 {15, 3},
261 };
262
263 graph::class_def_size_estimator_t estimator2(non_consecutive_map.iter());
264 assert(check_add_class_def_size(estimator2, non_consecutive_map, 1, {1}));
265 assert(check_add_class_def_size(estimator2, non_consecutive_map, 2, {1, 2}));
266 assert(check_add_class_def_size(estimator2, non_consecutive_map, 3, {1, 2, 3}));
267
268 estimator2.reset();
269 assert(check_add_class_def_size(estimator2, non_consecutive_map, 2, {2}));
270 assert(check_add_class_def_size(estimator2, non_consecutive_map, 3, {2, 3}));
271 }
272
test_running_class_size_estimates_with_locally_consecutive_glyphs()273 static void test_running_class_size_estimates_with_locally_consecutive_glyphs () {
274 gid_and_class_list_t map = {
275 {1, 1},
276 {6, 2},
277 {7, 3},
278 };
279
280 graph::class_def_size_estimator_t estimator(map.iter());
281 assert(check_add_class_def_size(estimator, map, 1, {1}));
282 assert(check_add_class_def_size(estimator, map, 2, {1, 2}));
283 assert(check_add_class_def_size(estimator, map, 3, {1, 2, 3}));
284
285 estimator.reset();
286 assert(check_add_class_def_size(estimator, map, 2, {2}));
287 assert(check_add_class_def_size(estimator, map, 3, {2, 3}));
288 }
289
290 int
main(int argc,char ** argv)291 main (int argc, char **argv)
292 {
293 test_class_and_coverage_size_estimates ();
294 test_running_class_and_coverage_size_estimates ();
295 test_running_class_size_estimates_with_locally_consecutive_glyphs ();
296 }
297