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