lib/tahints.c

   1 /* tahints.c */
   2
   3 /*
   4  * Copyright (C) 2011-2017 by Werner Lemberg.
   5  *
   6  * This file is part of the ttfautohint library, and may only be used,
   7  * modified, and distributed under the terms given in `COPYING'.  By
   8  * continuing to use, modify, or distribute this file you indicate that you
   9  * have read `COPYING' and understand and accept it fully.
  10  *
  11  * The file `COPYING' mentioned in the previous paragraph is distributed
  12  * with the ttfautohint library.
  13  */
  14
  15
  16 /* originally file `afhints.c' (2011-Mar-28) from FreeType */
  17
  18 /* heavily modified 2011 by Werner Lemberg <wl@gnu.org> */
  19
  20 #include "ta.h"
  21
  22 #include <string.h>
  23 #include <stdlib.h>
  24 #include "tahints.h"
  25
  26
  27 /* get new segment for given axis */
  28
  29 FT_Error
  30 ta_axis_hints_new_segment(TA_AxisHints axis,
  31                           TA_Segment* asegment)
  32 {
  33   FT_Error error = FT_Err_Ok;
  34   TA_Segment segment = NULL;
  35
  36
  37   if (axis->num_segments < TA_SEGMENTS_EMBEDDED)
  38   {
  39     if (!axis->segments)
  40     {
  41       axis->segments = axis->embedded.segments;
  42       axis->max_segments = TA_SEGMENTS_EMBEDDED;
  43     }
  44   }
  45   else if (axis->num_segments >= axis->max_segments)
  46   {
  47     TA_Segment segments_new;
  48
  49     FT_Int old_max = axis->max_segments;
  50     FT_Int new_max = old_max;
  51     FT_Int big_max = (FT_Int)(FT_INT_MAX / sizeof (*segment));
  52
  53
  54     if (old_max >= big_max)
  55     {
  56       error = FT_Err_Out_Of_Memory;
  57       goto Exit;
  58     }
  59
  60     new_max += (new_max >> 2) + 4;
  61     if (new_max < old_max
  62         || new_max > big_max)
  63       new_max = big_max;
  64
  65     if (axis->segments == axis->embedded.segments)
  66     {
  67       axis->segments = (TA_Segment)malloc(
  68                          (size_t)new_max * sizeof (TA_SegmentRec));
  69       if (!axis->segments)
  70         return FT_Err_Out_Of_Memory;
  71
  72       memcpy(axis->segments, axis->embedded.segments,
  73              sizeof (axis->embedded.segments));
  74     }
  75     else
  76     {
  77       segments_new = (TA_Segment)realloc(
  78                        axis->segments,
  79                        (size_t)new_max * sizeof (TA_SegmentRec));
  80       if (!segments_new)
  81         return FT_Err_Out_Of_Memory;
  82       axis->segments = segments_new;
  83     }
  84
  85     axis->max_segments = new_max;
  86   }
  87
  88   segment = axis->segments + axis->num_segments++;
  89
  90 Exit:
  91   *asegment = segment;
  92   return error;
  93 }
  94
  95
  96 /* get new edge for given axis, direction, and position, */
  97 /* without initializing the edge itself */
  98
  99 FT_Error
 100 ta_axis_hints_new_edge(TA_AxisHints axis,
 101                        FT_Int fpos,
 102                        TA_Direction dir,
 103                        FT_Bool top_to_bottom_hinting,
 104                        TA_Edge* anedge)
 105 {
 106   FT_Error error = FT_Err_Ok;
 107   TA_Edge edge = NULL;
 108   TA_Edge edges;
 109
 110
 111   if (axis->num_edges < TA_EDGES_EMBEDDED)
 112   {
 113     if (!axis->edges)
 114     {
 115       axis->edges = axis->embedded.edges;
 116       axis->max_edges = TA_EDGES_EMBEDDED;
 117     }
 118   }
 119   else if (axis->num_edges >= axis->max_edges)
 120   {
 121     TA_Edge edges_new;
 122
 123     FT_Int old_max = axis->max_edges;
 124     FT_Int new_max = old_max;
 125     FT_Int big_max = (FT_Int)(FT_INT_MAX / sizeof (*edge));
 126
 127
 128     if (old_max >= big_max)
 129     {
 130       error = FT_Err_Out_Of_Memory;
 131       goto Exit;
 132     }
 133
 134     new_max += (new_max >> 2) + 4;
 135     if (new_max < old_max
 136         || new_max > big_max)
 137       new_max = big_max;
 138
 139     if (axis->edges == axis->embedded.edges)
 140     {
 141       axis->edges = (TA_Edge)malloc((size_t)new_max * sizeof (TA_EdgeRec));
 142       if (!axis->edges)
 143         return FT_Err_Out_Of_Memory;
 144
 145       memcpy(axis->edges, axis->embedded.edges,
 146              sizeof (axis->embedded.edges));
 147     }
 148     else
 149     {
 150       edges_new = (TA_Edge)realloc(axis->edges,
 151                                    (size_t)new_max * sizeof (TA_EdgeRec));
 152       if (!edges_new)
 153         return FT_Err_Out_Of_Memory;
 154       axis->edges = edges_new;
 155     }
 156
 157     axis->max_edges = new_max;
 158   }
 159
 160   edges = axis->edges;
 161   edge = edges + axis->num_edges;
 162
 163   while (edge > edges)
 164   {
 165     if (top_to_bottom_hinting ? (edge[-1].fpos > fpos)
 166                               : (edge[-1].fpos < fpos))
 167       break;
 168
 169     /* we want the edge with same position and minor direction */
 170     /* to appear before those in the major one in the list */
 171     if (edge[-1].fpos == fpos
 172         && dir == axis->major_dir)
 173       break;
 174
 175     edge[0] = edge[-1];
 176     edge--;
 177   }
 178
 179   axis->num_edges++;
 180
 181 Exit:
 182   *anedge = edge;
 183   return error;
 184 }
 185
 186
 187 #ifdef TA_DEBUG
 188
 189 #include <stdio.h>
 190 #include <stdarg.h>
 191 #include <string.h>
 192
 193
 194 void
 195 _ta_message(const char* format,
 196             ...)
 197 {
 198   va_list ap;
 199
 200
 201   va_start(ap, format);
 202   vfprintf(stderr, format, ap);
 203   va_end(ap);
 204 }
 205
 206
 207 static const char*
 208 ta_dir_str(TA_Direction dir)
 209 {
 210   const char* result;
 211
 212
 213   switch (dir)
 214   {
 215   case TA_DIR_UP:
 216     result = "up";
 217     break;
 218   case TA_DIR_DOWN:
 219     result = "down";
 220     break;
 221   case TA_DIR_LEFT:
 222     result = "left";
 223     break;
 224   case TA_DIR_RIGHT:
 225     result = "right";
 226     break;
 227   default:
 228     result = "none";
 229   }
 230
 231   return result;
 232 }
 233
 234
 235 #define TA_INDEX_NUM(ptr, base) \
 236           (int)((ptr) ? ((ptr) - (base)) \
 237                       : -1)
 238
 239
 240 static char*
 241 ta_print_idx(char* p,
 242              int idx)
 243 {
 244   if (idx == -1)
 245   {
 246     p[0] = '-';
 247     p[1] = '-';
 248     p[2] = '\0';
 249   }
 250   else
 251     sprintf(p, "%d", idx);
 252
 253   return p;
 254 }
 255
 256
 257 static int
 258 ta_get_segment_index(TA_GlyphHints hints,
 259                      int point_idx,
 260                      int dimension)
 261 {
 262   TA_AxisHints axis = &hints->axis[dimension];
 263   TA_Point point = hints->points + point_idx;
 264   TA_Segment segments = axis->segments;
 265   TA_Segment limit = segments + axis->num_segments;
 266   TA_Segment segment;
 267
 268
 269   for (segment = segments; segment < limit; segment++)
 270   {
 271     if (segment->first <= segment->last)
 272     {
 273       if (point >= segment->first && point <= segment->last)
 274         break;
 275     }
 276     else
 277     {
 278       TA_Point p = segment->first;
 279
 280
 281       for (;;)
 282       {
 283         if (point == p)
 284           goto Exit;
 285
 286         if (p == segment->last)
 287           break;
 288
 289         p = p->next;
 290       }
 291     }
 292   }
 293
 294 Exit:
 295   if (segment == limit)
 296     return -1;
 297
 298   return (int)(segment - segments);
 299 }
 300
 301
 302 static int
 303 ta_get_edge_index(TA_GlyphHints hints,
 304                   int segment_idx,
 305                   int dimension)
 306 {
 307   TA_AxisHints axis = &hints->axis[dimension];
 308   TA_Edge edges = axis->edges;
 309   TA_Segment segment = axis->segments + segment_idx;
 310
 311
 312   return segment_idx == -1 ? -1 : TA_INDEX_NUM(segment->edge, edges);
 313 }
 314
 315
 316 void
 317 ta_glyph_hints_dump_points(TA_GlyphHints hints)
 318 {
 319   TA_Point points = hints->points;
 320   TA_Point limit = points + hints->num_points;
 321   TA_Point* contour = hints->contours;
 322   TA_Point* climit = contour + hints->num_contours;
 323   TA_Point point;
 324
 325
 326   TA_LOG(("Table of points:\n"));
 327
 328   if (hints->num_points)
 329     TA_LOG(("  index  hedge  hseg  flags"
 330             "  xorg  yorg  xscale  yscale   xfit    yfit"));
 331   else
 332     TA_LOG(("  (none)\n"));
 333
 334   for (point = points; point < limit; point++)
 335   {
 336     int point_idx = TA_INDEX_NUM(point, points);
 337     int segment_idx_1 = ta_get_segment_index(hints, point_idx, 1);
 338
 339     char buf1[16], buf2[16];
 340
 341
 342     /* insert extra newline at the beginning of a contour */
 343     if (contour < climit && *contour == point)
 344     {
 345       TA_LOG(("\n"));
 346       contour++;
 347     }
 348
 349     /* we don't show vertical edges since they are never used */
 350     TA_LOG(("  %5d  %5s %5s  %s "
 351             " %5d %5d %7.2f %7.2f %7.2f %7.2f\n",
 352             point_idx,
 353             ta_print_idx(buf1,
 354                          ta_get_edge_index(hints, segment_idx_1, 1)),
 355             ta_print_idx(buf2, segment_idx_1),
 356             (point->flags & TA_FLAG_WEAK_INTERPOLATION) ? "weak" : " -- ",
 357
 358             point->fx,
 359             point->fy,
 360             point->ox / 64.0,
 361             point->oy / 64.0,
 362             point->x / 64.0,
 363             point->y / 64.0));
 364   }
 365   TA_LOG(("\n"));
 366 }
 367
 368
 369 static const char*
 370 ta_edge_flags_to_string(FT_Byte flags)
 371 {
 372   static char temp[32];
 373   int pos = 0;
 374
 375
 376   if (flags & TA_EDGE_ROUND)
 377   {
 378     memcpy(temp + pos, "round", 5);
 379     pos += 5;
 380   }
 381   if (flags & TA_EDGE_SERIF)
 382   {
 383     if (pos > 0)
 384       temp[pos++] = ' ';
 385     memcpy(temp + pos, "serif", 5);
 386     pos += 5;
 387   }
 388   if (pos == 0)
 389     return "normal";
 390
 391   temp[pos] = '\0';
 392
 393   return temp;
 394 }
 395
 396
 397 /* dump the array of linked segments */
 398
 399 void
 400 ta_glyph_hints_dump_segments(TA_GlyphHints hints)
 401 {
 402   FT_Int dimension;
 403
 404
 405   for (dimension = TA_DEBUG_STARTDIM;
 406        dimension >= TA_DEBUG_ENDDIM;
 407        dimension--)
 408   {
 409     TA_AxisHints axis = &hints->axis[dimension];
 410     TA_Point points = hints->points;
 411     TA_Edge edges = axis->edges;
 412     TA_Segment segments = axis->segments;
 413     TA_Segment limit = segments + axis->num_segments;
 414     TA_Segment seg;
 415
 416     char buf1[16], buf2[16], buf3[16];
 417
 418
 419     TA_LOG(("Table of %s segments:\n",
 420             dimension == TA_DIMENSION_HORZ ? "vertical"
 421                                            : "horizontal"));
 422     if (axis->num_segments)
 423       TA_LOG(("  index   pos   delta   dir   from   to"
 424               "  link  serif  edge"
 425               "  height  extra     flags\n"));
 426     else
 427       TA_LOG(("  (none)\n"));
 428
 429     for (seg = segments; seg < limit; seg++)
 430       TA_LOG(("  %5d  %5d  %5d  %5s  %4d  %4d"
 431               "  %4s  %5s  %4s"
 432               "  %6d  %5d  %11s\n",
 433               TA_INDEX_NUM(seg, segments),
 434               seg->pos,
 435               seg->delta,
 436               ta_dir_str((TA_Direction)seg->dir),
 437               TA_INDEX_NUM(seg->first, points),
 438               TA_INDEX_NUM(seg->last, points),
 439
 440               ta_print_idx(buf1, TA_INDEX_NUM(seg->link, segments)),
 441               ta_print_idx(buf2, TA_INDEX_NUM(seg->serif, segments)),
 442               ta_print_idx(buf3, TA_INDEX_NUM(seg->edge, edges)),
 443
 444               seg->height,
 445               seg->height - (seg->max_coord - seg->min_coord),
 446               ta_edge_flags_to_string(seg->flags)));
 447     TA_LOG(("\n"));
 448   }
 449 }
 450
 451
 452 /* dump the array of linked edges */
 453
 454 void
 455 ta_glyph_hints_dump_edges(TA_GlyphHints hints)
 456 {
 457   FT_Int dimension;
 458
 459
 460   for (dimension = TA_DEBUG_STARTDIM;
 461        dimension >= TA_DEBUG_ENDDIM;
 462        dimension--)
 463   {
 464     TA_AxisHints axis = &hints->axis[dimension];
 465     TA_Edge edges = axis->edges;
 466     TA_Edge limit = edges + axis->num_edges;
 467     TA_Edge edge;
 468
 469     char buf1[16], buf2[16];
 470
 471
 472     /* note that TA_DIMENSION_HORZ corresponds to _vertical_ edges */
 473     /* since they have a constant X coordinate */
 474     if (dimension == TA_DIMENSION_HORZ)
 475       TA_LOG(("Table of %s edges (1px=%.2fu, 10u=%.2fpx):\n",
 476               "vertical",
 477               65536.0 * 64.0 / hints->x_scale,
 478               10.0 * hints->x_scale / 65536.0 / 64.0));
 479     else
 480       TA_LOG(("Table of %s edges (1px=%.2fu, 10u=%.2fpx):\n",
 481               "horizontal",
 482               65536.0 * 64.0 / hints->y_scale,
 483               10.0 * hints->y_scale / 65536.0 / 64.0));
 484
 485     if (axis->num_edges)
 486       TA_LOG(("  index    pos     dir   link  serif"
 487               "  blue    opos     pos       flags\n"));
 488     else
 489       TA_LOG(("  (none)\n"));
 490
 491     for (edge = edges; edge < limit; edge++)
 492       TA_LOG(("  %5d  %7.2f  %5s  %4s  %5s"
 493               "    %c   %7.2f  %7.2f  %11s\n",
 494               TA_INDEX_NUM(edge, edges),
 495               (int)edge->opos / 64.0,
 496               ta_dir_str((TA_Direction)edge->dir),
 497               ta_print_idx(buf1, TA_INDEX_NUM(edge->link, edges)),
 498               ta_print_idx(buf2, TA_INDEX_NUM(edge->serif, edges)),
 499
 500               edge->blue_edge ? 'y' : 'n',
 501               edge->opos / 64.0,
 502               edge->pos / 64.0,
 503               ta_edge_flags_to_string(edge->flags)));
 504     TA_LOG(("\n"));
 505   }
 506 }
 507
 508 #endif /* TA_DEBUG */
 509
 510
 511 /* compute the direction value of a given vector */
 512
 513 TA_Direction
 514 ta_direction_compute(FT_Pos dx,
 515                      FT_Pos dy)
 516 {
 517   FT_Pos ll, ss; /* long and short arm lengths */
 518   TA_Direction dir; /* candidate direction */
 519
 520
 521   if (dy >= dx)
 522   {
 523     if (dy >= -dx)
 524     {
 525       dir = TA_DIR_UP;
 526       ll = dy;
 527       ss = dx;
 528     }
 529     else
 530     {
 531       dir = TA_DIR_LEFT;
 532       ll = -dx;
 533       ss = dy;
 534     }
 535   }
 536   else /* dy < dx */
 537   {
 538     if (dy >= -dx)
 539     {
 540       dir = TA_DIR_RIGHT;
 541       ll = dx;
 542       ss = dy;
 543     }
 544     else
 545     {
 546       dir = TA_DIR_DOWN;
 547       ll = -dy;
 548       ss = dx;
 549     }
 550   }
 551
 552   /* return no direction if arm lengths do not differ enough */
 553   /* (value 14 is heuristic, corresponding to approx. 4.1 degrees); */
 554   /* the long arm is never negative */
 555   if (ll <= 14 * TA_ABS(ss))
 556     dir = TA_DIR_NONE;
 557
 558   return dir;
 559 }
 560
 561
 562 void
 563 ta_glyph_hints_init(TA_GlyphHints hints)
 564 {
 565   /* no need to initialize the embedded items */
 566   memset(hints, 0, sizeof (*hints) - sizeof (hints->embedded));
 567 }
 568
 569
 570 void
 571 ta_glyph_hints_done(TA_GlyphHints hints)
 572 {
 573   int dim;
 574
 575
 576   if (!hints)
 577     return;
 578
 579   /* we don't need to free the segment and edge buffers */
 580   /* since they are really within the hints->points array */
 581   for (dim = 0; dim < TA_DIMENSION_MAX; dim++)
 582   {
 583     TA_AxisHints axis = &hints->axis[dim];
 584
 585
 586     axis->num_segments = 0;
 587     axis->max_segments = 0;
 588     if (axis->segments != axis->embedded.segments)
 589     {
 590       free(axis->segments);
 591       axis->segments = NULL;
 592     }
 593
 594     axis->num_edges = 0;
 595     axis->max_edges = 0;
 596     if (axis->edges != axis->embedded.edges)
 597     {
 598       free(axis->edges);
 599       axis->edges = NULL;
 600     }
 601   }
 602
 603   if (hints->contours != hints->embedded.contours)
 604   {
 605     free(hints->contours);
 606     hints->contours = NULL;
 607   }
 608   hints->max_contours = 0;
 609   hints->num_contours = 0;
 610
 611   if (hints->points != hints->embedded.points)
 612   {
 613     free(hints->points);
 614     hints->points = NULL;
 615   }
 616   hints->max_points = 0;
 617   hints->num_points = 0;
 618 }
 619
 620
 621 /* reset metrics */
 622
 623 void
 624 ta_glyph_hints_rescale(TA_GlyphHints hints,
 625                        TA_StyleMetrics metrics)
 626 {
 627   hints->metrics = metrics;
 628   hints->scaler_flags = metrics->scaler.flags;
 629 }
 630
 631
 632 /* from FreeType's ftcalc.c */
 633
 634 static FT_Int
 635 ta_corner_is_flat(FT_Pos in_x,
 636                   FT_Pos in_y,
 637                   FT_Pos out_x,
 638                   FT_Pos out_y)
 639 {
 640   FT_Pos ax = in_x;
 641   FT_Pos ay = in_y;
 642
 643   FT_Pos d_in, d_out, d_corner;
 644
 645
 646   if (ax < 0)
 647     ax = -ax;
 648   if (ay < 0)
 649     ay = -ay;
 650   d_in = ax + ay;
 651
 652   ax = out_x;
 653   if (ax < 0)
 654     ax = -ax;
 655   ay = out_y;
 656   if (ay < 0)
 657     ay = -ay;
 658   d_out = ax + ay;
 659
 660   ax = out_x + in_x;
 661   if (ax < 0)
 662     ax = -ax;
 663   ay = out_y + in_y;
 664   if (ay < 0)
 665     ay = -ay;
 666   d_corner = ax + ay;
 667
 668   return (d_in + d_out - d_corner) < (d_corner >> 4);
 669 }
 670
 671
 672 /* recompute all TA_Point in TA_GlyphHints */
 673 /* from the definitions in a source outline */
 674
 675 FT_Error
 676 ta_glyph_hints_reload(TA_GlyphHints hints,
 677                       FT_Outline* outline)
 678 {
 679   FT_Error error = FT_Err_Ok;
 680   TA_Point points;
 681   FT_UInt old_max, new_max;
 682
 683   FT_Fixed x_scale = hints->x_scale;
 684   FT_Fixed y_scale = hints->y_scale;
 685   FT_Pos x_delta = hints->x_delta;
 686   FT_Pos y_delta = hints->y_delta;
 687
 688
 689   hints->num_points = 0;
 690   hints->num_contours = 0;
 691
 692   hints->axis[0].num_segments = 0;
 693   hints->axis[0].num_edges = 0;
 694   hints->axis[1].num_segments = 0;
 695   hints->axis[1].num_edges = 0;
 696
 697   /* first of all, reallocate the contours array if necessary */
 698   new_max = (FT_UInt)outline->n_contours;
 699   old_max = (FT_UInt)hints->max_contours;
 700
 701   if (new_max <= TA_CONTOURS_EMBEDDED)
 702   {
 703     if (!hints->contours)
 704     {
 705       hints->contours = hints->embedded.contours;
 706       hints->max_contours = TA_CONTOURS_EMBEDDED;
 707     }
 708   }
 709   else if (new_max > old_max)
 710   {
 711     TA_Point* contours_new;
 712
 713
 714     if (hints->contours == hints->embedded.contours)
 715       hints->contours = NULL;
 716
 717     new_max = (new_max + 3) & ~3U; /* round up to a multiple of 4 */
 718
 719     contours_new = (TA_Point*)realloc(hints->contours,
 720                                       new_max * sizeof (TA_Point));
 721     if (!contours_new)
 722       return FT_Err_Out_Of_Memory;
 723
 724     hints->contours = contours_new;
 725     hints->max_contours = (FT_Int)new_max;
 726   }
 727
 728   /* reallocate the points arrays if necessary -- we reserve */
 729   /* two additional point positions, used to hint metrics appropriately */
 730   new_max = (FT_UInt)(outline->n_points + 2);
 731   old_max = (FT_UInt)hints->max_points;
 732
 733   if (new_max <= TA_POINTS_EMBEDDED)
 734   {
 735     if (!hints->points)
 736     {
 737       hints->points = hints->embedded.points;
 738       hints->max_points = TA_POINTS_EMBEDDED;
 739     }
 740   }
 741   else if (new_max > old_max)
 742   {
 743     TA_Point points_new;
 744
 745
 746     if (hints->points == hints->embedded.points)
 747       hints->points = NULL;
 748
 749     new_max = (new_max + 2 + 7) & ~7U; /* round up to a multiple of 8 */
 750
 751     points_new = (TA_Point)realloc(hints->points,
 752                                    new_max * sizeof (TA_PointRec));
 753     if (!points_new)
 754       return FT_Err_Out_Of_Memory;
 755
 756     hints->points = points_new;
 757     hints->max_points = (FT_Int)new_max;
 758   }
 759
 760   hints->num_points = outline->n_points;
 761   hints->num_contours = outline->n_contours;
 762
 763   /* we can't rely on the value of `FT_Outline.flags' to know the fill */
 764   /* direction used for a glyph, given that some fonts are broken */
 765   /* (e.g. the Arphic ones); we thus recompute it each time we need to */
 766
 767   hints->axis[TA_DIMENSION_HORZ].major_dir = TA_DIR_UP;
 768   hints->axis[TA_DIMENSION_VERT].major_dir = TA_DIR_LEFT;
 769
 770   if (FT_Outline_Get_Orientation(outline) == FT_ORIENTATION_POSTSCRIPT)
 771   {
 772     hints->axis[TA_DIMENSION_HORZ].major_dir = TA_DIR_DOWN;
 773     hints->axis[TA_DIMENSION_VERT].major_dir = TA_DIR_RIGHT;
 774   }
 775
 776   hints->x_scale = x_scale;
 777   hints->y_scale = y_scale;
 778   hints->x_delta = x_delta;
 779   hints->y_delta = y_delta;
 780
 781   hints->xmin_delta = 0;
 782   hints->xmax_delta = 0;
 783
 784   points = hints->points;
 785   if (hints->num_points == 0)
 786     goto Exit;
 787
 788   {
 789     TA_Point point;
 790     TA_Point point_limit = points + hints->num_points;
 791
 792
 793     /* compute coordinates & Bezier flags, next and prev */
 794     {
 795       FT_Vector* vec = outline->points;
 796       char* tag = outline->tags;
 797
 798       TA_Point end = points + outline->contours[0];
 799       TA_Point prev = end;
 800
 801       FT_Int contour_index = 0;
 802
 803
 804       for (point = points; point < point_limit; point++, vec++, tag++)
 805       {
 806         point->in_dir = (FT_Char)TA_DIR_NONE;
 807         point->out_dir = (FT_Char)TA_DIR_NONE;
 808
 809         point->fx = (FT_Short)vec->x;
 810         point->fy = (FT_Short)vec->y;
 811         point->ox = point->x = FT_MulFix(vec->x, x_scale) + x_delta;
 812         point->oy = point->y = FT_MulFix(vec->y, y_scale) + y_delta;
 813
 814         switch (FT_CURVE_TAG(*tag))
 815         {
 816         case FT_CURVE_TAG_CONIC:
 817           point->flags = TA_FLAG_CONIC;
 818           break;
 819         case FT_CURVE_TAG_CUBIC:
 820           point->flags = TA_FLAG_CUBIC;
 821           break;
 822         default:
 823           point->flags = TA_FLAG_NONE;
 824         }
 825
 826         point->prev = prev;
 827         prev->next = point;
 828         prev = point;
 829
 830         if (point == end)
 831         {
 832           if (++contour_index < outline->n_contours)
 833           {
 834             end = points + outline->contours[contour_index];
 835             prev = end;
 836           }
 837         }
 838       }
 839     }
 840
 841     /* set up the contours array */
 842     {
 843       TA_Point* contour = hints->contours;
 844       TA_Point* contour_limit = contour + hints->num_contours;
 845
 846       short* end = outline->contours;
 847       short idx = 0;
 848
 849
 850       for (; contour < contour_limit; contour++, end++)
 851       {
 852         contour[0] = points + idx;
 853         idx = (short)(end[0] + 1);
 854       }
 855     }
 856
 857     {
 858       /*
 859        *  Compute directions of `in' and `out' vectors.
 860        *
 861        *  Note that distances between points that are very near to each
 862        *  other are accumulated.  In other words, the auto-hinter
 863        *  prepends the small vectors between near points to the first
 864        *  non-near vector.  All intermediate points are tagged as
 865        *  weak; the directions are adjusted also to be equal to the
 866        *  accumulated one.
 867        */
 868
 869       /* value 20 in `near_limit' is heuristic */
 870       FT_UInt units_per_em = hints->metrics->scaler.face->units_per_EM;
 871       FT_Int near_limit = 20 * units_per_em / 2048;
 872       FT_Int near_limit2 = 2 * near_limit - 1;
 873
 874       TA_Point* contour;
 875       TA_Point* contour_limit = hints->contours + hints->num_contours;
 876
 877
 878       for (contour = hints->contours; contour < contour_limit; contour++)
 879       {
 880         TA_Point first = *contour;
 881         TA_Point next, prev, curr;
 882
 883         FT_Pos out_x, out_y;
 884
 885
 886         /* since the first point of a contour could be part of a */
 887         /* series of near points, go backwards to find the first */
 888         /* non-near point and adjust `first' */
 889
 890         point = first;
 891         prev = first->prev;
 892
 893         while (prev != first)
 894         {
 895           out_x = point->fx - prev->fx;
 896           out_y = point->fy - prev->fy;
 897
 898           /*
 899            *  We use Taxicab metrics to measure the vector length.
 900            *
 901            *  Note that the accumulated distances so far could have the
 902            *  opposite direction of the distance measured here.  For this
 903            *  reason we use `near_limit2' for the comparison to get a
 904            *  non-near point even in the worst case.
 905            */
 906           if (TA_ABS(out_x) + TA_ABS(out_y) >= near_limit2)
 907             break;
 908
 909           point = prev;
 910           prev = prev->prev;
 911         }
 912
 913         /* adjust first point */
 914         first = point;
 915
 916         /* now loop over all points of the contour to get */
 917         /* `in' and `out' vector directions */
 918
 919         curr = first;
 920
 921         /*
 922          *  We abuse the `u' and `v' fields to store index deltas to the
 923          *  next and previous non-near point, respectively.
 924          *
 925          *  To avoid problems with not having non-near points, we point to
 926          *  `first' by default as the next non-near point.
 927          */
 928         curr->u = (FT_Pos)(first - curr);
 929         first->v = -curr->u;
 930
 931         out_x = 0;
 932         out_y = 0;
 933
 934         next = first;
 935         do
 936         {
 937           TA_Direction out_dir;
 938
 939
 940           point = next;
 941           next = point->next;
 942
 943           out_x += next->fx - point->fx;
 944           out_y += next->fy - point->fy;
 945
 946           if (TA_ABS(out_x) + TA_ABS(out_y) < near_limit)
 947           {
 948             next->flags |= TA_FLAG_WEAK_INTERPOLATION;
 949             continue;
 950           }
 951
 952           curr->u = (FT_Pos)(next - curr);
 953           next->v = -curr->u;
 954
 955           out_dir = ta_direction_compute(out_x, out_y);
 956
 957           /* adjust directions for all points inbetween; */
 958           /* the loop also updates position of `curr' */
 959           curr->out_dir = (FT_Char)out_dir;
 960           for (curr = curr->next; curr != next; curr = curr->next)
 961           {
 962             curr->in_dir = (FT_Char)out_dir;
 963             curr->out_dir = (FT_Char)out_dir;
 964           }
 965           next->in_dir = (FT_Char)out_dir;
 966
 967           curr->u = (FT_Pos)(first - curr);
 968           first->v = -curr->u;
 969
 970           out_x = 0;
 971           out_y = 0;
 972
 973         } while (next != first);
 974       }
 975
 976       /*
 977        *  The next step is to `simplify' an outline's topology so that we
 978        *  can identify local extrema more reliably: A series of
 979        *  non-horizontal or non-vertical vectors pointing into the same
 980        *  quadrant are handled as a single, long vector.  From a
 981        *  topological point of the view, the intermediate points are of no
 982        *  interest and thus tagged as weak.
 983        */
 984
 985       for (point = points; point < point_limit; point++)
 986       {
 987         if (point->flags & TA_FLAG_WEAK_INTERPOLATION)
 988           continue;
 989
 990         if (point->in_dir == TA_DIR_NONE
 991             && point->out_dir == TA_DIR_NONE)
 992         {
 993           /* check whether both vectors point into the same quadrant */
 994
 995           FT_Pos in_x, in_y;
 996           FT_Pos out_x, out_y;
 997
 998           TA_Point next_u = point + point->u;
 999           TA_Point prev_v = point + point->v;
1000
1001
1002           in_x = point->fx - prev_v->fx;
1003           in_y = point->fy - prev_v->fy;
1004
1005           out_x = next_u->fx - point->fx;
1006           out_y = next_u->fy - point->fy;
1007
1008           if ((in_x ^ out_x) >= 0 && (in_y ^ out_y) >= 0)
1009           {
1010             /* yes, so tag current point as weak */
1011             /* and update index deltas */
1012
1013             point->flags |= TA_FLAG_WEAK_INTERPOLATION;
1014
1015             prev_v->u = (FT_Pos)(next_u - prev_v);
1016             next_u->v = -prev_v->u;
1017           }
1018         }
1019       }
1020
1021       /*
1022        *  Finally, check for remaining weak points.  Everything else not
1023        *  collected in edges so far is then implicitly classified as strong
1024        *  points.
1025        */
1026
1027       for (point = points; point < point_limit; point++)
1028       {
1029         if (point->flags & TA_FLAG_WEAK_INTERPOLATION)
1030           continue;
1031
1032         if (point->flags & TA_FLAG_CONTROL)
1033         {
1034           /* control points are always weak */
1035         Is_Weak_Point:
1036           point->flags |= TA_FLAG_WEAK_INTERPOLATION;
1037         }
1038         else if (point->out_dir == point->in_dir)
1039         {
1040           if (point->out_dir != TA_DIR_NONE)
1041           {
1042             /* current point lies on a horizontal or */
1043             /* vertical segment (but doesn't start or end it) */
1044             goto Is_Weak_Point;
1045           }
1046
1047           {
1048             TA_Point next_u = point + point->u;
1049             TA_Point prev_v = point + point->v;
1050
1051
1052             if (ta_corner_is_flat(point->fx - prev_v->fx,
1053                                   point->fy - prev_v->fy,
1054                                   next_u->fx - point->fx,
1055                                   next_u->fy - point->fy))
1056             {
1057               /* either the `in' or the `out' vector is much more */
1058               /* dominant than the other one, so tag current point */
1059               /* as weak and update index deltas */
1060
1061               prev_v->u = (FT_Pos)(next_u - prev_v);
1062               next_u->v = -prev_v->u;
1063
1064               goto Is_Weak_Point;
1065             }
1066           }
1067         }
1068         else if (point->in_dir == -point->out_dir)
1069         {
1070           /* current point forms a spike */
1071           goto Is_Weak_Point;
1072         }
1073       }
1074     }
1075   }
1076
1077   /* change some directions at the user's request */
1078   /* to make ttfautohint insert one-point segments */
1079   /* or remove points from segments */
1080   {
1081     FONT* font;
1082     FT_Int idx;
1083     TA_Direction dir;
1084     int left_offset;
1085     int right_offset;
1086
1087
1088     /* `globals' is not set up while initializing metrics, */
1089     /* so exit early in this case */
1090     if (!hints->metrics->globals)
1091       goto Exit;
1092
1093     font = hints->metrics->globals->font;
1094
1095     /* start conditions are set with `TA_control_segment_dir_collect' */
1096     while (TA_control_segment_dir_get_next(font, &idx, &dir,
1097                                            &left_offset, &right_offset))
1098     {
1099       TA_Point point = &points[idx];
1100
1101
1102       point->out_dir = dir;
1103       if (dir == TA_DIR_NONE)
1104         point->flags |= TA_FLAG_WEAK_INTERPOLATION;
1105       else
1106         point->flags &= ~TA_FLAG_WEAK_INTERPOLATION;
1107       point->left_offset = (FT_Short)left_offset;
1108       point->right_offset = (FT_Short)right_offset;
1109     }
1110   }
1111
1112 Exit:
1113   return error;
1114 }
1115
1116
1117 /* store the hinted outline in an FT_Outline structure */
1118
1119 void
1120 ta_glyph_hints_save(TA_GlyphHints hints,
1121                     FT_Outline* outline)
1122 {
1123   TA_Point point = hints->points;
1124   TA_Point limit = point + hints->num_points;
1125
1126   FT_Vector* vec = outline->points;
1127   char* tag = outline->tags;
1128
1129
1130   for (; point < limit; point++, vec++, tag++)
1131   {
1132     vec->x = point->x;
1133     vec->y = point->y;
1134
1135     if (point->flags & TA_FLAG_CONIC)
1136       tag[0] = FT_CURVE_TAG_CONIC;
1137     else if (point->flags & TA_FLAG_CUBIC)
1138       tag[0] = FT_CURVE_TAG_CUBIC;
1139     else
1140       tag[0] = FT_CURVE_TAG_ON;
1141   }
1142 }
1143
1144
1145 /****************************************************************
1146  *
1147  *                     EDGE POINT GRID-FITTING
1148  *
1149  ****************************************************************/
1150
1151
1152 /* align all points of an edge to the same coordinate value, */
1153 /* either horizontally or vertically */
1154
1155 void
1156 ta_glyph_hints_align_edge_points(TA_GlyphHints hints,
1157                                  TA_Dimension dim)
1158 {
1159   TA_AxisHints axis = &hints->axis[dim];
1160   TA_Segment segments = axis->segments;
1161   TA_Segment segment_limit = segments + axis->num_segments;
1162   TA_Segment seg;
1163
1164
1165   if (dim == TA_DIMENSION_HORZ)
1166   {
1167     for (seg = segments; seg < segment_limit; seg++)
1168     {
1169       TA_Edge edge = seg->edge;
1170       TA_Point point, first, last;
1171
1172
1173       if (!edge)
1174         continue;
1175
1176       first = seg->first;
1177       last = seg->last;
1178       point = first;
1179       for (;;)
1180       {
1181         point->x = edge->pos;
1182         point->flags |= TA_FLAG_TOUCH_X;
1183
1184         if (point == last)
1185           break;
1186
1187         point = point->next;
1188       }
1189     }
1190   }
1191   else
1192   {
1193     for (seg = segments; seg < segment_limit; seg++)
1194     {
1195       TA_Edge edge = seg->edge;
1196       TA_Point point, first, last;
1197
1198
1199       if (!edge)
1200         continue;
1201
1202       first = seg->first;
1203       last = seg->last;
1204       point = first;
1205       for (;;)
1206       {
1207         point->y = edge->pos;
1208         point->flags |= TA_FLAG_TOUCH_Y;
1209
1210         if (point == last)
1211           break;
1212
1213         point = point->next;
1214       }
1215     }
1216   }
1217 }
1218
1219
1220 /****************************************************************
1221  *
1222  *                    STRONG POINT INTERPOLATION
1223  *
1224  ****************************************************************/
1225
1226
1227 /* hint the strong points -- */
1228 /* this is equivalent to the TrueType `IP' hinting instruction */
1229
1230 void
1231 ta_glyph_hints_align_strong_points(TA_GlyphHints hints,
1232                                    TA_Dimension dim)
1233 {
1234   TA_Point points = hints->points;
1235   TA_Point point_limit = points + hints->num_points;
1236
1237   TA_AxisHints axis = &hints->axis[dim];
1238
1239   TA_Edge edges = axis->edges;
1240   TA_Edge edge_limit = edges + axis->num_edges;
1241
1242   FT_UShort touch_flag;
1243
1244
1245   if (dim == TA_DIMENSION_HORZ)
1246     touch_flag = TA_FLAG_TOUCH_X;
1247   else
1248     touch_flag = TA_FLAG_TOUCH_Y;
1249
1250   if (edges < edge_limit)
1251   {
1252     TA_Point point;
1253     TA_Edge edge;
1254
1255
1256     for (point = points; point < point_limit; point++)
1257     {
1258       FT_Pos u, ou, fu; /* point position */
1259       FT_Pos delta;
1260
1261
1262       if (point->flags & touch_flag)
1263         continue;
1264
1265       /* if this point is candidate to weak interpolation, we */
1266       /* interpolate it after all strong points have been processed */
1267
1268       if ((point->flags & TA_FLAG_WEAK_INTERPOLATION))
1269         continue;
1270
1271       if (dim == TA_DIMENSION_VERT)
1272       {
1273         u = point->fy;
1274         ou = point->oy;
1275       }
1276       else
1277       {
1278         u = point->fx;
1279         ou = point->ox;
1280       }
1281
1282       fu = u;
1283
1284       /* is the point before the first edge? */
1285       edge = edges;
1286       delta = edge->fpos - u;
1287       if (delta >= 0)
1288       {
1289         u = edge->pos - (edge->opos - ou);
1290
1291         if (hints->recorder)
1292           hints->recorder(ta_ip_before, hints, dim,
1293                           point, NULL, NULL, NULL, NULL);
1294
1295         goto Store_Point;
1296       }
1297
1298       /* is the point after the last edge? */
1299       edge = edge_limit - 1;
1300       delta = u - edge->fpos;
1301       if (delta >= 0)
1302       {
1303         u = edge->pos + (ou - edge->opos);
1304
1305         if (hints->recorder)
1306           hints->recorder(ta_ip_after, hints, dim,
1307                           point, NULL, NULL, NULL, NULL);
1308
1309         goto Store_Point;
1310       }
1311
1312       {
1313         FT_PtrDist min, max, mid;
1314         FT_Pos fpos;
1315
1316
1317         /* find enclosing edges */
1318         min = 0;
1319         max = edge_limit - edges;
1320
1321         /* for a small number of edges, a linear search is better */
1322         if (max <= 8)
1323         {
1324           FT_PtrDist nn;
1325
1326
1327           for (nn = 0; nn < max; nn++)
1328             if (edges[nn].fpos >= u)
1329               break;
1330
1331           if (edges[nn].fpos == u)
1332           {
1333             u = edges[nn].pos;
1334
1335             if (hints->recorder)
1336               hints->recorder(ta_ip_on, hints, dim,
1337                               point, &edges[nn], NULL, NULL, NULL);
1338
1339             goto Store_Point;
1340           }
1341           min = nn;
1342         }
1343         else
1344           while (min < max)
1345           {
1346             mid = (max + min) >> 1;
1347             edge = edges + mid;
1348             fpos = edge->fpos;
1349
1350             if (u < fpos)
1351               max = mid;
1352             else if (u > fpos)
1353               min = mid + 1;
1354             else
1355             {
1356               /* we are on the edge */
1357               u = edge->pos;
1358
1359               if (hints->recorder)
1360                 hints->recorder(ta_ip_on, hints, dim,
1361                                 point, edge, NULL, NULL, NULL);
1362
1363               goto Store_Point;
1364             }
1365           }
1366
1367         /* point is not on an edge */
1368         {
1369           TA_Edge before = edges + min - 1;
1370           TA_Edge after = edges + min + 0;
1371
1372
1373           /* assert(before && after && before != after) */
1374           if (before->scale == 0)
1375             before->scale = FT_DivFix(after->pos - before->pos,
1376                                       after->fpos - before->fpos);
1377
1378           u = before->pos + FT_MulFix(fu - before->fpos,
1379                                       before->scale);
1380
1381           if (hints->recorder)
1382             hints->recorder(ta_ip_between, hints, dim,
1383                             point, before, after, NULL, NULL);
1384         }
1385       }
1386
1387     Store_Point:
1388       /* save the point position */
1389       if (dim == TA_DIMENSION_HORZ)
1390         point->x = u;
1391       else
1392         point->y = u;
1393
1394       point->flags |= touch_flag;
1395     }
1396   }
1397 }
1398
1399
1400 /****************************************************************
1401  *
1402  *                    WEAK POINT INTERPOLATION
1403  *
1404  ****************************************************************/
1405
1406
1407 /* shift the original coordinates of all points between `p1' and */
1408 /* `p2' to get hinted coordinates, using the same difference as */
1409 /* given by `ref' */
1410
1411 static void
1412 ta_iup_shift(TA_Point p1,
1413              TA_Point p2,
1414              TA_Point ref)
1415 {
1416   TA_Point p;
1417   FT_Pos delta = ref->u - ref->v;
1418
1419
1420   if (delta == 0)
1421     return;
1422
1423   for (p = p1; p < ref; p++)
1424     p->u = p->v + delta;
1425
1426   for (p = ref + 1; p <= p2; p++)
1427     p->u = p->v + delta;
1428 }
1429
1430
1431 /* interpolate the original coordinates of all points between `p1' and */
1432 /* `p2' to get hinted coordinates, using `ref1' and `ref2' as the */
1433 /* reference points; the `u' and `v' members are the current and */
1434 /* original coordinate values, respectively. */
1435
1436 /* details can be found in the TrueType bytecode specification */
1437
1438 static void
1439 ta_iup_interp(TA_Point p1,
1440               TA_Point p2,
1441               TA_Point ref1,
1442               TA_Point ref2)
1443 {
1444   TA_Point p;
1445   FT_Pos u, v1, v2, u1, u2, d1, d2;
1446
1447
1448   if (p1 > p2)
1449     return;
1450
1451   if (ref1->v > ref2->v)
1452   {
1453     p = ref1;
1454     ref1 = ref2;
1455     ref2 = p;
1456   }
1457
1458   v1 = ref1->v;
1459   v2 = ref2->v;
1460   u1 = ref1->u;
1461   u2 = ref2->u;
1462   d1 = u1 - v1;
1463   d2 = u2 - v2;
1464
1465   if (u1 == u2 || v1 == v2)
1466   {
1467     for (p = p1; p <= p2; p++)
1468     {
1469       u = p->v;
1470
1471       if (u <= v1)
1472         u += d1;
1473       else if (u >= v2)
1474         u += d2;
1475       else
1476         u = u1;
1477
1478       p->u = u;
1479     }
1480   }
1481   else
1482   {
1483     FT_Fixed scale = FT_DivFix(u2 - u1, v2 - v1);
1484
1485
1486     for (p = p1; p <= p2; p++)
1487     {
1488       u = p->v;
1489
1490       if (u <= v1)
1491         u += d1;
1492       else if (u >= v2)
1493         u += d2;
1494       else
1495         u = u1 + FT_MulFix(u - v1, scale);
1496
1497       p->u = u;
1498     }
1499   }
1500 }
1501
1502
1503 /* hint the weak points -- */
1504 /* this is equivalent to the TrueType `IUP' hinting instruction */
1505
1506 void
1507 ta_glyph_hints_align_weak_points(TA_GlyphHints hints,
1508                                  TA_Dimension dim)
1509 {
1510   TA_Point points = hints->points;
1511   TA_Point point_limit = points + hints->num_points;
1512
1513   TA_Point* contour = hints->contours;
1514   TA_Point* contour_limit = contour + hints->num_contours;
1515
1516   FT_UShort touch_flag;
1517   TA_Point point;
1518   TA_Point end_point;
1519   TA_Point first_point;
1520
1521
1522   /* pass 1: move segment points to edge positions */
1523
1524   if (dim == TA_DIMENSION_HORZ)
1525   {
1526     touch_flag = TA_FLAG_TOUCH_X;
1527
1528     for (point = points; point < point_limit; point++)
1529     {
1530       point->u = point->x;
1531       point->v = point->ox;
1532     }
1533   }
1534   else
1535   {
1536     touch_flag = TA_FLAG_TOUCH_Y;
1537
1538     for (point = points; point < point_limit; point++)
1539     {
1540       point->u = point->y;
1541       point->v = point->oy;
1542     }
1543   }
1544
1545   for (; contour < contour_limit; contour++)
1546   {
1547     TA_Point first_touched, last_touched;
1548
1549
1550     point = *contour;
1551     end_point = point->prev;
1552     first_point = point;
1553
1554     /* find first touched point */
1555     for (;;)
1556     {
1557       if (point > end_point) /* no touched point in contour */
1558         goto NextContour;
1559
1560       if (point->flags & touch_flag)
1561         break;
1562
1563       point++;
1564     }
1565
1566     first_touched = point;
1567
1568     for (;;)
1569     {
1570       /* skip any touched neighbours */
1571       while (point < end_point
1572              && (point[1].flags & touch_flag) != 0)
1573         point++;
1574
1575       last_touched = point;
1576
1577       /* find the next touched point, if any */
1578       point++;
1579       for (;;)
1580       {
1581         if (point > end_point)
1582           goto EndContour;
1583
1584         if ((point->flags & touch_flag) != 0)
1585           break;
1586
1587         point++;
1588       }
1589
1590       /* interpolate between last_touched and point */
1591       ta_iup_interp(last_touched + 1, point - 1,
1592                     last_touched, point);
1593     }
1594
1595   EndContour:
1596     /* special case: only one point was touched */
1597     if (last_touched == first_touched)
1598       ta_iup_shift(first_point, end_point, first_touched);
1599
1600     else /* interpolate the last part */
1601     {
1602       if (last_touched < end_point)
1603         ta_iup_interp(last_touched + 1, end_point,
1604                       last_touched, first_touched);
1605
1606       if (first_touched > points)
1607         ta_iup_interp(first_point, first_touched - 1,
1608                       last_touched, first_touched);
1609     }
1610
1611   NextContour:
1612     ;
1613   }
1614
1615   /* now save the interpolated values back to x/y */
1616   if (dim == TA_DIMENSION_HORZ)
1617   {
1618     for (point = points; point < point_limit; point++)
1619       point->x = point->u;
1620   }
1621   else
1622   {
1623     for (point = points; point < point_limit; point++)
1624       point->y = point->u;
1625   }
1626 }
1627
1628
1629 #ifdef TA_CONFIG_OPTION_USE_WARPER
1630
1631 /* apply (small) warp scale and warp delta for given dimension */
1632
1633 static void
1634 ta_glyph_hints_scale_dim(TA_GlyphHints hints,
1635                          TA_Dimension dim,
1636                          FT_Fixed scale,
1637                          FT_Pos delta)
1638 {
1639   TA_Point points = hints->points;
1640   TA_Point points_limit = points + hints->num_points;
1641   TA_Point point;
1642
1643
1644   if (dim == TA_DIMENSION_HORZ)
1645   {
1646     for (point = points; point < points_limit; point++)
1647       point->x = FT_MulFix(point->fx, scale) + delta;
1648   }
1649   else
1650   {
1651     for (point = points; point < points_limit; point++)
1652       point->y = FT_MulFix(point->fy, scale) + delta;
1653   }
1654 }
1655
1656 #endif /* TA_CONFIG_OPTION_USE_WARPER */
1657
1658 /* end of tahints.c */