1 /*
2 * Copyright © 2024 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
25 #include "hb-subset-instancer-iup.hh"
26
27 /* This file is a straight port of the following:
28 *
29 * https://github.com/fonttools/fonttools/blob/main/Lib/fontTools/varLib/iup.py
30 *
31 * Where that file returns optimzied deltas vector, we return optimized
32 * referenced point indices.
33 */
34
35 constexpr static unsigned MAX_LOOKBACK = 8;
36
_iup_contour_bound_forced_set(const hb_array_t<const contour_point_t> contour_points,const hb_array_t<const int> x_deltas,const hb_array_t<const int> y_deltas,hb_set_t & forced_set,double tolerance=0.0)37 static void _iup_contour_bound_forced_set (const hb_array_t<const contour_point_t> contour_points,
38 const hb_array_t<const int> x_deltas,
39 const hb_array_t<const int> y_deltas,
40 hb_set_t& forced_set, /* OUT */
41 double tolerance = 0.0)
42 {
43 unsigned len = contour_points.length;
44 unsigned next_i = 0;
45 for (int i = len - 1; i >= 0; i--)
46 {
47 unsigned last_i = (len + i -1) % len;
48 for (unsigned j = 0; j < 2; j++)
49 {
50 double cj, lcj, ncj;
51 int dj, ldj, ndj;
52 if (j == 0)
53 {
54 cj = static_cast<double> (contour_points.arrayZ[i].x);
55 dj = x_deltas.arrayZ[i];
56 lcj = static_cast<double> (contour_points.arrayZ[last_i].x);
57 ldj = x_deltas.arrayZ[last_i];
58 ncj = static_cast<double> (contour_points.arrayZ[next_i].x);
59 ndj = x_deltas.arrayZ[next_i];
60 }
61 else
62 {
63 cj = static_cast<double> (contour_points.arrayZ[i].y);
64 dj = y_deltas.arrayZ[i];
65 lcj = static_cast<double> (contour_points.arrayZ[last_i].y);
66 ldj = y_deltas.arrayZ[last_i];
67 ncj = static_cast<double> (contour_points.arrayZ[next_i].y);
68 ndj = y_deltas.arrayZ[next_i];
69 }
70
71 double c1, c2;
72 int d1, d2;
73 if (lcj <= ncj)
74 {
75 c1 = lcj;
76 c2 = ncj;
77 d1 = ldj;
78 d2 = ndj;
79 }
80 else
81 {
82 c1 = ncj;
83 c2 = lcj;
84 d1 = ndj;
85 d2 = ldj;
86 }
87
88 bool force = false;
89 if (c1 == c2)
90 {
91 if (abs (d1 - d2) > tolerance && abs (dj) > tolerance)
92 force = true;
93 }
94 else if (c1 <= cj && cj <= c2)
95 {
96 if (!(hb_min (d1, d2) - tolerance <= dj &&
97 dj <= hb_max (d1, d2) + tolerance))
98 force = true;
99 }
100 else
101 {
102 if (d1 != d2)
103 {
104 if (cj < c1)
105 {
106 if (abs (dj) > tolerance &&
107 abs (dj - d1) > tolerance &&
108 ((dj - tolerance < d1) != (d1 < d2)))
109 force = true;
110 }
111 else
112 {
113 if (abs (dj) > tolerance &&
114 abs (dj - d2) > tolerance &&
115 ((d2 < dj + tolerance) != (d1 < d2)))
116 force = true;
117 }
118 }
119 }
120
121 if (force)
122 {
123 forced_set.add (i);
124 break;
125 }
126 }
127 next_i = i;
128 }
129 }
130
131 template <typename T,
132 hb_enable_if (hb_is_trivially_copyable (T))>
rotate_array(const hb_array_t<const T> & org_array,int k,hb_vector_t<T> & out)133 static bool rotate_array (const hb_array_t<const T>& org_array,
134 int k,
135 hb_vector_t<T>& out)
136 {
137 unsigned n = org_array.length;
138 if (!n) return true;
139 if (unlikely (!out.resize (n, false)))
140 return false;
141
142 unsigned item_size = hb_static_size (T);
143 if (k < 0)
144 k = n - (-k) % n;
145 else
146 k %= n;
147
148 hb_memcpy ((void *) out.arrayZ, (const void *) (org_array.arrayZ + n - k), k * item_size);
149 hb_memcpy ((void *) (out.arrayZ + k), (const void *) org_array.arrayZ, (n - k) * item_size);
150 return true;
151 }
152
rotate_set(const hb_set_t & org_set,int k,unsigned n,hb_set_t & out)153 static bool rotate_set (const hb_set_t& org_set,
154 int k,
155 unsigned n,
156 hb_set_t& out)
157 {
158 if (!n) return false;
159 k %= n;
160 if (k < 0)
161 k = n + k;
162
163 if (k == 0)
164 {
165 out.set (org_set);
166 }
167 else
168 {
169 for (auto v : org_set)
170 out.add ((v + k) % n);
171 }
172 return !out.in_error ();
173 }
174
175 /* Given two reference coordinates (start and end of contour_points array),
176 * output interpolated deltas for points in between */
_iup_segment(const hb_array_t<const contour_point_t> contour_points,const hb_array_t<const int> x_deltas,const hb_array_t<const int> y_deltas,const contour_point_t & p1,const contour_point_t & p2,int p1_dx,int p2_dx,int p1_dy,int p2_dy,hb_vector_t<double> & interp_x_deltas,hb_vector_t<double> & interp_y_deltas)177 static bool _iup_segment (const hb_array_t<const contour_point_t> contour_points,
178 const hb_array_t<const int> x_deltas,
179 const hb_array_t<const int> y_deltas,
180 const contour_point_t& p1, const contour_point_t& p2,
181 int p1_dx, int p2_dx,
182 int p1_dy, int p2_dy,
183 hb_vector_t<double>& interp_x_deltas, /* OUT */
184 hb_vector_t<double>& interp_y_deltas /* OUT */)
185 {
186 unsigned n = contour_points.length;
187 if (unlikely (!interp_x_deltas.resize (n, false) ||
188 !interp_y_deltas.resize (n, false)))
189 return false;
190
191 for (unsigned j = 0; j < 2; j++)
192 {
193 double x1, x2, d1, d2;
194 double *out;
195 if (j == 0)
196 {
197 x1 = static_cast<double> (p1.x);
198 x2 = static_cast<double> (p2.x);
199 d1 = p1_dx;
200 d2 = p2_dx;
201 out = interp_x_deltas.arrayZ;
202 }
203 else
204 {
205 x1 = static_cast<double> (p1.y);
206 x2 = static_cast<double> (p2.y);
207 d1 = p1_dy;
208 d2 = p2_dy;
209 out = interp_y_deltas.arrayZ;
210 }
211
212 if (x1 == x2)
213 {
214 if (d1 == d2)
215 {
216 for (unsigned i = 0; i < n; i++)
217 out[i] = d1;
218 }
219 else
220 {
221 for (unsigned i = 0; i < n; i++)
222 out[i] = 0.0;
223 }
224 continue;
225 }
226
227 if (x1 > x2)
228 {
229 hb_swap (x1, x2);
230 hb_swap (d1, d2);
231 }
232
233 double scale = (d2 - d1) / (x2 - x1);
234 for (unsigned i = 0; i < n; i++)
235 {
236 double x = (j == 0 ? static_cast<double> (contour_points.arrayZ[i].x) : static_cast<double> (contour_points.arrayZ[i].y));
237 double d;
238 if (x <= x1)
239 d = d1;
240 else if (x >= x2)
241 d = d2;
242 else
243 d = d1 + (x - x1) * scale;
244
245 out[i] = d;
246 }
247 }
248 return true;
249 }
250
_can_iup_in_between(const hb_array_t<const contour_point_t> contour_points,const hb_array_t<const int> x_deltas,const hb_array_t<const int> y_deltas,const contour_point_t & p1,const contour_point_t & p2,int p1_dx,int p2_dx,int p1_dy,int p2_dy,double tolerance)251 static bool _can_iup_in_between (const hb_array_t<const contour_point_t> contour_points,
252 const hb_array_t<const int> x_deltas,
253 const hb_array_t<const int> y_deltas,
254 const contour_point_t& p1, const contour_point_t& p2,
255 int p1_dx, int p2_dx,
256 int p1_dy, int p2_dy,
257 double tolerance)
258 {
259 hb_vector_t<double> interp_x_deltas, interp_y_deltas;
260 if (!_iup_segment (contour_points, x_deltas, y_deltas,
261 p1, p2, p1_dx, p2_dx, p1_dy, p2_dy,
262 interp_x_deltas, interp_y_deltas))
263 return false;
264
265 unsigned num = contour_points.length;
266
267 for (unsigned i = 0; i < num; i++)
268 {
269 double dx = static_cast<double> (x_deltas.arrayZ[i]) - interp_x_deltas.arrayZ[i];
270 double dy = static_cast<double> (y_deltas.arrayZ[i]) - interp_y_deltas.arrayZ[i];
271
272 if (sqrt (dx * dx + dy * dy) > tolerance)
273 return false;
274 }
275 return true;
276 }
277
_iup_contour_optimize_dp(const contour_point_vector_t & contour_points,const hb_vector_t<int> & x_deltas,const hb_vector_t<int> & y_deltas,const hb_set_t & forced_set,double tolerance,unsigned lookback,hb_vector_t<unsigned> & costs,hb_vector_t<int> & chain)278 static bool _iup_contour_optimize_dp (const contour_point_vector_t& contour_points,
279 const hb_vector_t<int>& x_deltas,
280 const hb_vector_t<int>& y_deltas,
281 const hb_set_t& forced_set,
282 double tolerance,
283 unsigned lookback,
284 hb_vector_t<unsigned>& costs, /* OUT */
285 hb_vector_t<int>& chain /* OUT */)
286 {
287 unsigned n = contour_points.length;
288 if (unlikely (!costs.resize (n, false) ||
289 !chain.resize (n, false)))
290 return false;
291
292 lookback = hb_min (lookback, MAX_LOOKBACK);
293
294 for (unsigned i = 0; i < n; i++)
295 {
296 unsigned best_cost = (i == 0 ? 1 : costs.arrayZ[i-1] + 1);
297
298 costs.arrayZ[i] = best_cost;
299 chain.arrayZ[i] = (i == 0 ? -1 : i - 1);
300
301 if (i > 0 && forced_set.has (i - 1))
302 continue;
303
304 int lookback_index = hb_max ((int) i - (int) lookback + 1, -1);
305 for (int j = i - 2; j >= lookback_index; j--)
306 {
307 unsigned cost = j == -1 ? 1 : costs.arrayZ[j] + 1;
308 /* num points between i and j */
309 unsigned num_points = i - j - 1;
310 unsigned p1 = (j == -1 ? n - 1 : j);
311 if (cost < best_cost &&
312 _can_iup_in_between (contour_points.as_array ().sub_array (j + 1, num_points),
313 x_deltas.as_array ().sub_array (j + 1, num_points),
314 y_deltas.as_array ().sub_array (j + 1, num_points),
315 contour_points.arrayZ[p1], contour_points.arrayZ[i],
316 x_deltas.arrayZ[p1], x_deltas.arrayZ[i],
317 y_deltas.arrayZ[p1], y_deltas.arrayZ[i],
318 tolerance))
319 {
320 best_cost = cost;
321 costs.arrayZ[i] = best_cost;
322 chain.arrayZ[i] = j;
323 }
324
325 if (j > 0 && forced_set.has (j))
326 break;
327 }
328 }
329 return true;
330 }
331
_iup_contour_optimize(const hb_array_t<const contour_point_t> contour_points,const hb_array_t<const int> x_deltas,const hb_array_t<const int> y_deltas,hb_array_t<bool> opt_indices,double tolerance=0.0)332 static bool _iup_contour_optimize (const hb_array_t<const contour_point_t> contour_points,
333 const hb_array_t<const int> x_deltas,
334 const hb_array_t<const int> y_deltas,
335 hb_array_t<bool> opt_indices, /* OUT */
336 double tolerance = 0.0)
337 {
338 unsigned n = contour_points.length;
339 if (opt_indices.length != n ||
340 x_deltas.length != n ||
341 y_deltas.length != n)
342 return false;
343
344 bool all_within_tolerance = true;
345 for (unsigned i = 0; i < n; i++)
346 {
347 int dx = x_deltas.arrayZ[i];
348 int dy = y_deltas.arrayZ[i];
349 if (sqrt ((double) dx * dx + (double) dy * dy) > tolerance)
350 {
351 all_within_tolerance = false;
352 break;
353 }
354 }
355
356 /* If all are within tolerance distance, do nothing, opt_indices is
357 * initilized to false */
358 if (all_within_tolerance)
359 return true;
360
361 /* If there's exactly one point, return it */
362 if (n == 1)
363 {
364 opt_indices.arrayZ[0] = true;
365 return true;
366 }
367
368 /* If all deltas are exactly the same, return just one (the first one) */
369 bool all_deltas_are_equal = true;
370 for (unsigned i = 1; i < n; i++)
371 if (x_deltas.arrayZ[i] != x_deltas.arrayZ[0] ||
372 y_deltas.arrayZ[i] != y_deltas.arrayZ[0])
373 {
374 all_deltas_are_equal = false;
375 break;
376 }
377
378 if (all_deltas_are_equal)
379 {
380 opt_indices.arrayZ[0] = true;
381 return true;
382 }
383
384 /* else, solve the general problem using Dynamic Programming */
385 hb_set_t forced_set;
386 _iup_contour_bound_forced_set (contour_points, x_deltas, y_deltas, forced_set, tolerance);
387
388 if (!forced_set.is_empty ())
389 {
390 int k = n - 1 - forced_set.get_max ();
391 if (k < 0)
392 return false;
393
394 hb_vector_t<int> rot_x_deltas, rot_y_deltas;
395 contour_point_vector_t rot_points;
396 hb_set_t rot_forced_set;
397 if (!rotate_array (contour_points, k, rot_points) ||
398 !rotate_array (x_deltas, k, rot_x_deltas) ||
399 !rotate_array (y_deltas, k, rot_y_deltas) ||
400 !rotate_set (forced_set, k, n, rot_forced_set))
401 return false;
402
403 hb_vector_t<unsigned> costs;
404 hb_vector_t<int> chain;
405
406 if (!_iup_contour_optimize_dp (rot_points, rot_x_deltas, rot_y_deltas,
407 rot_forced_set, tolerance, n,
408 costs, chain))
409 return false;
410
411 hb_set_t solution;
412 int index = n - 1;
413 while (index != -1)
414 {
415 solution.add (index);
416 index = chain.arrayZ[index];
417 }
418
419 if (solution.is_empty () ||
420 forced_set.get_population () > solution.get_population ())
421 return false;
422
423 for (unsigned i : solution)
424 opt_indices.arrayZ[i] = true;
425
426 hb_vector_t<bool> rot_indices;
427 const hb_array_t<const bool> opt_indices_array (opt_indices.arrayZ, opt_indices.length);
428 rotate_array (opt_indices_array, -k, rot_indices);
429
430 for (unsigned i = 0; i < n; i++)
431 opt_indices.arrayZ[i] = rot_indices.arrayZ[i];
432 }
433 else
434 {
435 hb_vector_t<int> repeat_x_deltas, repeat_y_deltas;
436 contour_point_vector_t repeat_points;
437
438 if (unlikely (!repeat_x_deltas.resize (n * 2, false) ||
439 !repeat_y_deltas.resize (n * 2, false) ||
440 !repeat_points.resize (n * 2, false)))
441 return false;
442
443 unsigned contour_point_size = hb_static_size (contour_point_t);
444 for (unsigned i = 0; i < n; i++)
445 {
446 hb_memcpy ((void *) repeat_x_deltas.arrayZ, (const void *) x_deltas.arrayZ, n * sizeof (repeat_x_deltas[0]));
447 hb_memcpy ((void *) (repeat_x_deltas.arrayZ + n), (const void *) x_deltas.arrayZ, n * sizeof (repeat_x_deltas[0]));
448
449 hb_memcpy ((void *) repeat_y_deltas.arrayZ, (const void *) y_deltas.arrayZ, n * sizeof (repeat_x_deltas[0]));
450 hb_memcpy ((void *) (repeat_y_deltas.arrayZ + n), (const void *) y_deltas.arrayZ, n * sizeof (repeat_x_deltas[0]));
451
452 hb_memcpy ((void *) repeat_points.arrayZ, (const void *) contour_points.arrayZ, n * contour_point_size);
453 hb_memcpy ((void *) (repeat_points.arrayZ + n), (const void *) contour_points.arrayZ, n * contour_point_size);
454 }
455
456 hb_vector_t<unsigned> costs;
457 hb_vector_t<int> chain;
458 if (!_iup_contour_optimize_dp (repeat_points, repeat_x_deltas, repeat_y_deltas,
459 forced_set, tolerance, n,
460 costs, chain))
461 return false;
462
463 unsigned best_cost = n + 1;
464 int len = costs.length;
465 hb_set_t best_sol;
466 for (int start = n - 1; start < len; start++)
467 {
468 hb_set_t solution;
469 int i = start;
470 int lookback = start - (int) n;
471 while (i > lookback)
472 {
473 solution.add (i % n);
474 i = chain.arrayZ[i];
475 }
476 if (i == lookback)
477 {
478 unsigned cost_i = i < 0 ? 0 : costs.arrayZ[i];
479 unsigned cost = costs.arrayZ[start] - cost_i;
480 if (cost <= best_cost)
481 {
482 best_sol.set (solution);
483 best_cost = cost;
484 }
485 }
486 }
487
488 for (unsigned i = 0; i < n; i++)
489 if (best_sol.has (i))
490 opt_indices.arrayZ[i] = true;
491 }
492 return true;
493 }
494
iup_delta_optimize(const contour_point_vector_t & contour_points,const hb_vector_t<int> & x_deltas,const hb_vector_t<int> & y_deltas,hb_vector_t<bool> & opt_indices,double tolerance)495 bool iup_delta_optimize (const contour_point_vector_t& contour_points,
496 const hb_vector_t<int>& x_deltas,
497 const hb_vector_t<int>& y_deltas,
498 hb_vector_t<bool>& opt_indices, /* OUT */
499 double tolerance)
500 {
501 if (!opt_indices.resize (contour_points.length))
502 return false;
503
504 hb_vector_t<unsigned> end_points;
505 unsigned count = contour_points.length;
506 if (unlikely (!end_points.alloc (count)))
507 return false;
508
509 for (unsigned i = 0; i < count - 4; i++)
510 if (contour_points.arrayZ[i].is_end_point)
511 end_points.push (i);
512
513 /* phantom points */
514 for (unsigned i = count - 4; i < count; i++)
515 end_points.push (i);
516
517 if (end_points.in_error ()) return false;
518
519 unsigned start = 0;
520 for (unsigned end : end_points)
521 {
522 unsigned len = end - start + 1;
523 if (!_iup_contour_optimize (contour_points.as_array ().sub_array (start, len),
524 x_deltas.as_array ().sub_array (start, len),
525 y_deltas.as_array ().sub_array (start, len),
526 opt_indices.as_array ().sub_array (start, len),
527 tolerance))
528 return false;
529 start = end + 1;
530 }
531 return true;
532 }
533