lib/tahints.c

   1 /* tahints.c */
   2
   3 /*
   4  * Copyright (C) 2011-2016 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 == NULL)
  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 == NULL)
 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    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  %5.2g  %5s  %4d  %4d"
 431               "  %4s  %5s  %4s"
 432               "  %6d  %5d  %11s\n",
 433               TA_INDEX_NUM(seg, segments),
 434               dimension == TA_DIMENSION_HORZ ? (int)seg->first->ox / 64.0
 435                                              : (int)seg->first->oy / 64.0,
 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     TA_LOG(("Table of %s edges:\n",
 475             dimension == TA_DIMENSION_HORZ ? "vertical"
 476                                            : "horizontal"));
 477     if (axis->num_edges)
 478       TA_LOG(("  index   pos    dir   link  serif"
 479               "  blue  opos    pos      flags\n"));
 480     else
 481       TA_LOG(("  (none)\n"));
 482
 483     for (edge = edges; edge < limit; edge++)
 484       TA_LOG(("  %5d  %5.2g  %5s  %4s  %5s"
 485               "    %c   %5.2f  %5.2f  %11s\n",
 486               TA_INDEX_NUM(edge, edges),
 487               (int)edge->opos / 64.0,
 488               ta_dir_str((TA_Direction)edge->dir),
 489               ta_print_idx(buf1, TA_INDEX_NUM(edge->link, edges)),
 490               ta_print_idx(buf2, TA_INDEX_NUM(edge->serif, edges)),
 491
 492               edge->blue_edge ? 'y' : 'n',
 493               edge->opos / 64.0,
 494               edge->pos / 64.0,
 495               ta_edge_flags_to_string(edge->flags)));
 496     TA_LOG(("\n"));
 497   }
 498 }
 499
 500 #endif /* TA_DEBUG */
 501
 502
 503 /* compute the direction value of a given vector */
 504
 505 TA_Direction
 506 ta_direction_compute(FT_Pos dx,
 507                      FT_Pos dy)
 508 {
 509   FT_Pos ll, ss; /* long and short arm lengths */
 510   TA_Direction dir; /* candidate direction */
 511
 512
 513   if (dy >= dx)
 514   {
 515     if (dy >= -dx)
 516     {
 517       dir = TA_DIR_UP;
 518       ll = dy;
 519       ss = dx;
 520     }
 521     else
 522     {
 523       dir = TA_DIR_LEFT;
 524       ll = -dx;
 525       ss = dy;
 526     }
 527   }
 528   else /* dy < dx */
 529   {
 530     if (dy >= -dx)
 531     {
 532       dir = TA_DIR_RIGHT;
 533       ll = dx;
 534       ss = dy;
 535     }
 536     else
 537     {
 538       dir = TA_DIR_DOWN;
 539       ll = -dy;
 540       ss = dx;
 541     }
 542   }
 543
 544   /* return no direction if arm lengths do not differ enough */
 545   /* (value 14 is heuristic, corresponding to approx. 4.1 degrees); */
 546   /* the long arm is never negative */
 547   if (ll <= 14 * TA_ABS(ss))
 548     dir = TA_DIR_NONE;
 549
 550   return dir;
 551 }
 552
 553
 554 void
 555 ta_glyph_hints_init(TA_GlyphHints hints)
 556 {
 557   /* no need to initialize the embedded items */
 558   memset(hints, 0, sizeof (*hints) - sizeof (hints->embedded));
 559 }
 560
 561
 562 void
 563 ta_glyph_hints_done(TA_GlyphHints hints)
 564 {
 565   int dim;
 566
 567
 568   if (!hints)
 569     return;
 570
 571   /* we don't need to free the segment and edge buffers */
 572   /* since they are really within the hints->points array */
 573   for (dim = 0; dim < TA_DIMENSION_MAX; dim++)
 574   {
 575     TA_AxisHints axis = &hints->axis[dim];
 576
 577
 578     axis->num_segments = 0;
 579     axis->max_segments = 0;
 580     if (axis->segments != axis->embedded.segments)
 581     {
 582       free(axis->segments);
 583       axis->segments = NULL;
 584     }
 585
 586     axis->num_edges = 0;
 587     axis->max_edges = 0;
 588     if (axis->edges != axis->embedded.edges)
 589     {
 590       free(axis->edges);
 591       axis->edges = NULL;
 592     }
 593   }
 594
 595   if (hints->contours != hints->embedded.contours)
 596   {
 597     free(hints->contours);
 598     hints->contours = NULL;
 599   }
 600   hints->max_contours = 0;
 601   hints->num_contours = 0;
 602
 603   if (hints->points != hints->embedded.points)
 604   {
 605     free(hints->points);
 606     hints->points = NULL;
 607   }
 608   hints->max_points = 0;
 609   hints->num_points = 0;
 610 }
 611
 612
 613 /* reset metrics */
 614
 615 void
 616 ta_glyph_hints_rescale(TA_GlyphHints hints,
 617                        TA_StyleMetrics metrics)
 618 {
 619   hints->metrics = metrics;
 620   hints->scaler_flags = metrics->scaler.flags;
 621 }
 622
 623
 624 /* from FreeType's ftcalc.c */
 625
 626 static FT_Int
 627 ta_corner_is_flat(FT_Pos in_x,
 628                   FT_Pos in_y,
 629                   FT_Pos out_x,
 630                   FT_Pos out_y)
 631 {
 632   FT_Pos ax = in_x;
 633   FT_Pos ay = in_y;
 634
 635   FT_Pos d_in, d_out, d_corner;
 636
 637
 638   if (ax < 0)
 639     ax = -ax;
 640   if (ay < 0)
 641     ay = -ay;
 642   d_in = ax + ay;
 643
 644   ax = out_x;
 645   if (ax < 0)
 646     ax = -ax;
 647   ay = out_y;
 648   if (ay < 0)
 649     ay = -ay;
 650   d_out = ax + ay;
 651
 652   ax = out_x + in_x;
 653   if (ax < 0)
 654     ax = -ax;
 655   ay = out_y + in_y;
 656   if (ay < 0)
 657     ay = -ay;
 658   d_corner = ax + ay;
 659
 660   return (d_in + d_out - d_corner) < (d_corner >> 4);
 661 }
 662
 663
 664 /* recompute all TA_Point in TA_GlyphHints */
 665 /* from the definitions in a source outline */
 666
 667 FT_Error
 668 ta_glyph_hints_reload(TA_GlyphHints hints,
 669                       FT_Outline* outline)
 670 {
 671   FT_Error error = FT_Err_Ok;
 672   TA_Point points;
 673   FT_UInt old_max, new_max;
 674
 675   FT_Fixed x_scale = hints->x_scale;
 676   FT_Fixed y_scale = hints->y_scale;
 677   FT_Pos x_delta = hints->x_delta;
 678   FT_Pos y_delta = hints->y_delta;
 679
 680
 681   hints->num_points = 0;
 682   hints->num_contours = 0;
 683
 684   hints->axis[0].num_segments = 0;
 685   hints->axis[0].num_edges = 0;
 686   hints->axis[1].num_segments = 0;
 687   hints->axis[1].num_edges = 0;
 688
 689   /* first of all, reallocate the contours array if necessary */
 690   new_max = (FT_UInt)outline->n_contours;
 691   old_max = (FT_UInt)hints->max_contours;
 692
 693   if (new_max <= TA_CONTOURS_EMBEDDED)
 694   {
 695     if (hints->contours == NULL)
 696     {
 697       hints->contours = hints->embedded.contours;
 698       hints->max_contours = TA_CONTOURS_EMBEDDED;
 699     }
 700   }
 701   else if (new_max > old_max)
 702   {
 703     TA_Point* contours_new;
 704
 705
 706     if (hints->contours == hints->embedded.contours)
 707       hints->contours = NULL;
 708
 709     new_max = (new_max + 3) & ~3U; /* round up to a multiple of 4 */
 710
 711     contours_new = (TA_Point*)realloc(hints->contours,
 712                                       new_max * sizeof (TA_Point));
 713     if (!contours_new)
 714       return FT_Err_Out_Of_Memory;
 715
 716     hints->contours = contours_new;
 717     hints->max_contours = (FT_Int)new_max;
 718   }
 719
 720   /* reallocate the points arrays if necessary -- we reserve */
 721   /* two additional point positions, used to hint metrics appropriately */
 722   new_max = (FT_UInt)(outline->n_points + 2);
 723   old_max = (FT_UInt)hints->max_points;
 724
 725   if (new_max <= TA_POINTS_EMBEDDED)
 726   {
 727     if (hints->points == NULL)
 728     {
 729       hints->points = hints->embedded.points;
 730       hints->max_points = TA_POINTS_EMBEDDED;
 731     }
 732   }
 733   else if (new_max > old_max)
 734   {
 735     TA_Point points_new;
 736
 737
 738     if (hints->points == hints->embedded.points)
 739       hints->points = NULL;
 740
 741     new_max = (new_max + 2 + 7) & ~7U; /* round up to a multiple of 8 */
 742
 743     points_new = (TA_Point)realloc(hints->points,
 744                                    new_max * sizeof (TA_PointRec));
 745     if (!points_new)
 746       return FT_Err_Out_Of_Memory;
 747
 748     hints->points = points_new;
 749     hints->max_points = (FT_Int)new_max;
 750   }
 751
 752   hints->num_points = outline->n_points;
 753   hints->num_contours = outline->n_contours;
 754
 755   /* we can't rely on the value of `FT_Outline.flags' to know the fill */
 756   /* direction used for a glyph, given that some fonts are broken */
 757   /* (e.g. the Arphic ones); we thus recompute it each time we need to */
 758
 759   hints->axis[TA_DIMENSION_HORZ].major_dir = TA_DIR_UP;
 760   hints->axis[TA_DIMENSION_VERT].major_dir = TA_DIR_LEFT;
 761
 762   if (FT_Outline_Get_Orientation(outline) == FT_ORIENTATION_POSTSCRIPT)
 763   {
 764     hints->axis[TA_DIMENSION_HORZ].major_dir = TA_DIR_DOWN;
 765     hints->axis[TA_DIMENSION_VERT].major_dir = TA_DIR_RIGHT;
 766   }
 767
 768   hints->x_scale = x_scale;
 769   hints->y_scale = y_scale;
 770   hints->x_delta = x_delta;
 771   hints->y_delta = y_delta;
 772
 773   hints->xmin_delta = 0;
 774   hints->xmax_delta = 0;
 775
 776   points = hints->points;
 777   if (hints->num_points == 0)
 778     goto Exit;
 779
 780   {
 781     TA_Point point;
 782     TA_Point point_limit = points + hints->num_points;
 783
 784
 785     /* compute coordinates & Bezier flags, next and prev */
 786     {
 787       FT_Vector* vec = outline->points;
 788       char* tag = outline->tags;
 789
 790       TA_Point end = points + outline->contours[0];
 791       TA_Point prev = end;
 792
 793       FT_Int contour_index = 0;
 794
 795
 796       for (point = points; point < point_limit; point++, vec++, tag++)
 797       {
 798         point->in_dir = (FT_Char)TA_DIR_NONE;
 799         point->out_dir = (FT_Char)TA_DIR_NONE;
 800
 801         point->fx = (FT_Short)vec->x;
 802         point->fy = (FT_Short)vec->y;
 803         point->ox = point->x = FT_MulFix(vec->x, x_scale) + x_delta;
 804         point->oy = point->y = FT_MulFix(vec->y, y_scale) + y_delta;
 805
 806         switch (FT_CURVE_TAG(*tag))
 807         {
 808         case FT_CURVE_TAG_CONIC:
 809           point->flags = TA_FLAG_CONIC;
 810           break;
 811         case FT_CURVE_TAG_CUBIC:
 812           point->flags = TA_FLAG_CUBIC;
 813           break;
 814         default:
 815           point->flags = TA_FLAG_NONE;
 816         }
 817
 818         point->prev = prev;
 819         prev->next = point;
 820         prev = point;
 821
 822         if (point == end)
 823         {
 824           if (++contour_index < outline->n_contours)
 825           {
 826             end = points + outline->contours[contour_index];
 827             prev = end;
 828           }
 829         }
 830       }
 831     }
 832
 833     /* set up the contours array */
 834     {
 835       TA_Point* contour = hints->contours;
 836       TA_Point* contour_limit = contour + hints->num_contours;
 837
 838       short* end = outline->contours;
 839       short idx = 0;
 840
 841
 842       for (; contour < contour_limit; contour++, end++)
 843       {
 844         contour[0] = points + idx;
 845         idx = (short)(end[0] + 1);
 846       }
 847     }
 848
 849     {
 850       /*
 851        *  Compute directions of `in' and `out' vectors.
 852        *
 853        *  Note that distances between points that are very near to each
 854        *  other are accumulated.  In other words, the auto-hinter
 855        *  prepends the small vectors between near points to the first
 856        *  non-near vector.  All intermediate points are tagged as
 857        *  weak; the directions are adjusted also to be equal to the
 858        *  accumulated one.
 859        */
 860
 861       /* value 20 in `near_limit' is heuristic */
 862       FT_UInt units_per_em = hints->metrics->scaler.face->units_per_EM;
 863       FT_Int near_limit = 20 * units_per_em / 2048;
 864       FT_Int near_limit2 = 2 * near_limit - 1;
 865
 866       TA_Point* contour;
 867       TA_Point* contour_limit = hints->contours + hints->num_contours;
 868
 869
 870       for (contour = hints->contours; contour < contour_limit; contour++)
 871       {
 872         TA_Point first = *contour;
 873         TA_Point next, prev, curr;
 874
 875         FT_Pos out_x, out_y;
 876
 877
 878         /* since the first point of a contour could be part of a */
 879         /* series of near points, go backwards to find the first */
 880         /* non-near point and adjust `first' */
 881
 882         point = first;
 883         prev = first->prev;
 884
 885         while (prev != first)
 886         {
 887           out_x = point->fx - prev->fx;
 888           out_y = point->fy - prev->fy;
 889
 890           /*
 891            *  We use Taxicab metrics to measure the vector length.
 892            *
 893            *  Note that the accumulated distances so far could have the
 894            *  opposite direction of the distance measured here.  For this
 895            *  reason we use `near_limit2' for the comparison to get a
 896            *  non-near point even in the worst case.
 897            */
 898           if (TA_ABS(out_x) + TA_ABS(out_y) >= near_limit2)
 899             break;
 900
 901           point = prev;
 902           prev = prev->prev;
 903         }
 904
 905         /* adjust first point */
 906         first = point;
 907
 908         /* now loop over all points of the contour to get */
 909         /* `in' and `out' vector directions */
 910
 911         curr = first;
 912
 913         /*
 914          *  We abuse the `u' and `v' fields to store index deltas to the
 915          *  next and previous non-near point, respectively.
 916          *
 917          *  To avoid problems with not having non-near points, we point to
 918          *  `first' by default as the next non-near point.
 919          */
 920         curr->u = (FT_Pos)(first - curr);
 921         first->v = -curr->u;
 922
 923         out_x = 0;
 924         out_y = 0;
 925
 926         next = first;
 927         do
 928         {
 929           TA_Direction out_dir;
 930
 931
 932           point = next;
 933           next = point->next;
 934
 935           out_x += next->fx - point->fx;
 936           out_y += next->fy - point->fy;
 937
 938           if (TA_ABS(out_x) + TA_ABS(out_y) < near_limit)
 939           {
 940             next->flags |= TA_FLAG_WEAK_INTERPOLATION;
 941             continue;
 942           }
 943
 944           curr->u = (FT_Pos)(next - curr);
 945           next->v = -curr->u;
 946
 947           out_dir = ta_direction_compute(out_x, out_y);
 948
 949           /* adjust directions for all points inbetween; */
 950           /* the loop also updates position of `curr' */
 951           curr->out_dir = (FT_Char)out_dir;
 952           for (curr = curr->next; curr != next; curr = curr->next)
 953           {
 954             curr->in_dir = (FT_Char)out_dir;
 955             curr->out_dir = (FT_Char)out_dir;
 956           }
 957           next->in_dir = (FT_Char)out_dir;
 958
 959           curr->u = (FT_Pos)(first - curr);
 960           first->v = -curr->u;
 961
 962           out_x = 0;
 963           out_y = 0;
 964
 965         } while (next != first);
 966       }
 967
 968       /*
 969        *  The next step is to `simplify' an outline's topology so that we
 970        *  can identify local extrema more reliably: A series of
 971        *  non-horizontal or non-vertical vectors pointing into the same
 972        *  quadrant are handled as a single, long vector.  From a
 973        *  topological point of the view, the intermediate points are of no
 974        *  interest and thus tagged as weak.
 975        */
 976
 977       for (point = points; point < point_limit; point++)
 978       {
 979         if (point->flags & TA_FLAG_WEAK_INTERPOLATION)
 980           continue;
 981
 982         if (point->in_dir == TA_DIR_NONE
 983             && point->out_dir == TA_DIR_NONE)
 984         {
 985           /* check whether both vectors point into the same quadrant */
 986
 987           FT_Pos in_x, in_y;
 988           FT_Pos out_x, out_y;
 989
 990           TA_Point next_u = point + point->u;
 991           TA_Point prev_v = point + point->v;
 992
 993
 994           in_x = point->fx - prev_v->fx;
 995           in_y = point->fy - prev_v->fy;
 996
 997           out_x = next_u->fx - point->fx;
 998           out_y = next_u->fy - point->fy;
 999
1000           if ((in_x ^ out_x) >= 0 && (in_y ^ out_y) >= 0)
1001           {
1002             /* yes, so tag current point as weak */
1003             /* and update index deltas */
1004
1005             point->flags |= TA_FLAG_WEAK_INTERPOLATION;
1006
1007             prev_v->u = (FT_Pos)(next_u - prev_v);
1008             next_u->v = -prev_v->u;
1009           }
1010         }
1011       }
1012
1013       /*
1014        *  Finally, check for remaining weak points.  Everything else not
1015        *  collected in edges so far is then implicitly classified as strong
1016        *  points.
1017        */
1018
1019       for (point = points; point < point_limit; point++)
1020       {
1021         if (point->flags & TA_FLAG_WEAK_INTERPOLATION)
1022           continue;
1023
1024         if (point->flags & TA_FLAG_CONTROL)
1025         {
1026           /* control points are always weak */
1027         Is_Weak_Point:
1028           point->flags |= TA_FLAG_WEAK_INTERPOLATION;
1029         }
1030         else if (point->out_dir == point->in_dir)
1031         {
1032           if (point->out_dir != TA_DIR_NONE)
1033           {
1034             /* current point lies on a horizontal or */
1035             /* vertical segment (but doesn't start or end it) */
1036             goto Is_Weak_Point;
1037           }
1038
1039           {
1040             TA_Point next_u = point + point->u;
1041             TA_Point prev_v = point + point->v;
1042
1043
1044             if (ta_corner_is_flat(point->fx - prev_v->fx,
1045                                   point->fy - prev_v->fy,
1046                                   next_u->fx - point->fx,
1047                                   next_u->fy - point->fy))
1048             {
1049               /* either the `in' or the `out' vector is much more */
1050               /* dominant than the other one, so tag current point */
1051               /* as weak and update index deltas */
1052
1053               prev_v->u = (FT_Pos)(next_u - prev_v);
1054               next_u->v = -prev_v->u;
1055
1056               goto Is_Weak_Point;
1057             }
1058           }
1059         }
1060         else if (point->in_dir == -point->out_dir)
1061         {
1062           /* current point forms a spike */
1063           goto Is_Weak_Point;
1064         }
1065       }
1066     }
1067   }
1068
1069   /* change some directions at the user's request */
1070   /* to make ttfautohint insert one-point segments */
1071   /* or remove points from segments */
1072   {
1073     FONT* font;
1074     FT_Int idx;
1075     TA_Direction dir;
1076     int left_offset;
1077     int right_offset;
1078
1079
1080     /* `globals' is not set up while initializing metrics, */
1081     /* so exit early in this case */
1082     if (!hints->metrics->globals)
1083       goto Exit;
1084
1085     font = hints->metrics->globals->font;
1086
1087     /* start conditions are set with `TA_control_segment_dir_collect' */
1088     while (TA_control_segment_dir_get_next(font, &idx, &dir,
1089                                            &left_offset, &right_offset))
1090     {
1091       TA_Point point = &points[idx];
1092
1093
1094       point->out_dir = dir;
1095       if (dir == TA_DIR_NONE)
1096         point->flags |= TA_FLAG_WEAK_INTERPOLATION;
1097       else
1098         point->flags &= ~TA_FLAG_WEAK_INTERPOLATION;
1099       point->left_offset = (FT_Short)left_offset;
1100       point->right_offset = (FT_Short)right_offset;
1101     }
1102   }
1103
1104 Exit:
1105   return error;
1106 }
1107
1108
1109 /* store the hinted outline in an FT_Outline structure */
1110
1111 void
1112 ta_glyph_hints_save(TA_GlyphHints hints,
1113                     FT_Outline* outline)
1114 {
1115   TA_Point point = hints->points;
1116   TA_Point limit = point + hints->num_points;
1117
1118   FT_Vector* vec = outline->points;
1119   char* tag = outline->tags;
1120
1121
1122   for (; point < limit; point++, vec++, tag++)
1123   {
1124     vec->x = point->x;
1125     vec->y = point->y;
1126
1127     if (point->flags & TA_FLAG_CONIC)
1128       tag[0] = FT_CURVE_TAG_CONIC;
1129     else if (point->flags & TA_FLAG_CUBIC)
1130       tag[0] = FT_CURVE_TAG_CUBIC;
1131     else
1132       tag[0] = FT_CURVE_TAG_ON;
1133   }
1134 }
1135
1136
1137 /****************************************************************
1138  *
1139  *                     EDGE POINT GRID-FITTING
1140  *
1141  ****************************************************************/
1142
1143
1144 /* align all points of an edge to the same coordinate value, */
1145 /* either horizontally or vertically */
1146
1147 void
1148 ta_glyph_hints_align_edge_points(TA_GlyphHints hints,
1149                                  TA_Dimension dim)
1150 {
1151   TA_AxisHints axis = &hints->axis[dim];
1152   TA_Segment segments = axis->segments;
1153   TA_Segment segment_limit = segments + axis->num_segments;
1154   TA_Segment seg;
1155
1156
1157   if (dim == TA_DIMENSION_HORZ)
1158   {
1159     for (seg = segments; seg < segment_limit; seg++)
1160     {
1161       TA_Edge edge = seg->edge;
1162       TA_Point point, first, last;
1163
1164
1165       if (edge == NULL)
1166         continue;
1167
1168       first = seg->first;
1169       last = seg->last;
1170       point = first;
1171       for (;;)
1172       {
1173         point->x = edge->pos;
1174         point->flags |= TA_FLAG_TOUCH_X;
1175
1176         if (point == last)
1177           break;
1178
1179         point = point->next;
1180       }
1181     }
1182   }
1183   else
1184   {
1185     for (seg = segments; seg < segment_limit; seg++)
1186     {
1187       TA_Edge edge = seg->edge;
1188       TA_Point point, first, last;
1189
1190
1191       if (edge == NULL)
1192         continue;
1193
1194       first = seg->first;
1195       last = seg->last;
1196       point = first;
1197       for (;;)
1198       {
1199         point->y = edge->pos;
1200         point->flags |= TA_FLAG_TOUCH_Y;
1201
1202         if (point == last)
1203           break;
1204
1205         point = point->next;
1206       }
1207     }
1208   }
1209 }
1210
1211
1212 /****************************************************************
1213  *
1214  *                    STRONG POINT INTERPOLATION
1215  *
1216  ****************************************************************/
1217
1218
1219 /* hint the strong points -- */
1220 /* this is equivalent to the TrueType `IP' hinting instruction */
1221
1222 void
1223 ta_glyph_hints_align_strong_points(TA_GlyphHints hints,
1224                                    TA_Dimension dim)
1225 {
1226   TA_Point points = hints->points;
1227   TA_Point point_limit = points + hints->num_points;
1228
1229   TA_AxisHints axis = &hints->axis[dim];
1230
1231   TA_Edge edges = axis->edges;
1232   TA_Edge edge_limit = edges + axis->num_edges;
1233
1234   FT_UShort touch_flag;
1235
1236
1237   if (dim == TA_DIMENSION_HORZ)
1238     touch_flag = TA_FLAG_TOUCH_X;
1239   else
1240     touch_flag = TA_FLAG_TOUCH_Y;
1241
1242   if (edges < edge_limit)
1243   {
1244     TA_Point point;
1245     TA_Edge edge;
1246
1247
1248     for (point = points; point < point_limit; point++)
1249     {
1250       FT_Pos u, ou, fu; /* point position */
1251       FT_Pos delta;
1252
1253
1254       if (point->flags & touch_flag)
1255         continue;
1256
1257       /* if this point is candidate to weak interpolation, we */
1258       /* interpolate it after all strong points have been processed */
1259
1260       if ((point->flags & TA_FLAG_WEAK_INTERPOLATION))
1261         continue;
1262
1263       if (dim == TA_DIMENSION_VERT)
1264       {
1265         u = point->fy;
1266         ou = point->oy;
1267       }
1268       else
1269       {
1270         u = point->fx;
1271         ou = point->ox;
1272       }
1273
1274       fu = u;
1275
1276       /* is the point before the first edge? */
1277       edge = edges;
1278       delta = edge->fpos - u;
1279       if (delta >= 0)
1280       {
1281         u = edge->pos - (edge->opos - ou);
1282
1283         if (hints->recorder)
1284           hints->recorder(ta_ip_before, hints, dim,
1285                           point, NULL, NULL, NULL, NULL);
1286
1287         goto Store_Point;
1288       }
1289
1290       /* is the point after the last edge? */
1291       edge = edge_limit - 1;
1292       delta = u - edge->fpos;
1293       if (delta >= 0)
1294       {
1295         u = edge->pos + (ou - edge->opos);
1296
1297         if (hints->recorder)
1298           hints->recorder(ta_ip_after, hints, dim,
1299                           point, NULL, NULL, NULL, NULL);
1300
1301         goto Store_Point;
1302       }
1303
1304       {
1305         FT_PtrDist min, max, mid;
1306         FT_Pos fpos;
1307
1308
1309         /* find enclosing edges */
1310         min = 0;
1311         max = edge_limit - edges;
1312
1313         /* for a small number of edges, a linear search is better */
1314         if (max <= 8)
1315         {
1316           FT_PtrDist nn;
1317
1318
1319           for (nn = 0; nn < max; nn++)
1320             if (edges[nn].fpos >= u)
1321               break;
1322
1323           if (edges[nn].fpos == u)
1324           {
1325             u = edges[nn].pos;
1326
1327             if (hints->recorder)
1328               hints->recorder(ta_ip_on, hints, dim,
1329                               point, &edges[nn], NULL, NULL, NULL);
1330
1331             goto Store_Point;
1332           }
1333           min = nn;
1334         }
1335         else
1336           while (min < max)
1337           {
1338             mid = (max + min) >> 1;
1339             edge = edges + mid;
1340             fpos = edge->fpos;
1341
1342             if (u < fpos)
1343               max = mid;
1344             else if (u > fpos)
1345               min = mid + 1;
1346             else
1347             {
1348               /* we are on the edge */
1349               u = edge->pos;
1350
1351               if (hints->recorder)
1352                 hints->recorder(ta_ip_on, hints, dim,
1353                                 point, edge, NULL, NULL, NULL);
1354
1355               goto Store_Point;
1356             }
1357           }
1358
1359         /* point is not on an edge */
1360         {
1361           TA_Edge before = edges + min - 1;
1362           TA_Edge after = edges + min + 0;
1363
1364
1365           /* assert(before && after && before != after) */
1366           if (before->scale == 0)
1367             before->scale = FT_DivFix(after->pos - before->pos,
1368                                       after->fpos - before->fpos);
1369
1370           u = before->pos + FT_MulFix(fu - before->fpos,
1371                                       before->scale);
1372
1373           if (hints->recorder)
1374             hints->recorder(ta_ip_between, hints, dim,
1375                             point, before, after, NULL, NULL);
1376         }
1377       }
1378
1379     Store_Point:
1380       /* save the point position */
1381       if (dim == TA_DIMENSION_HORZ)
1382         point->x = u;
1383       else
1384         point->y = u;
1385
1386       point->flags |= touch_flag;
1387     }
1388   }
1389 }
1390
1391
1392 /****************************************************************
1393  *
1394  *                    WEAK POINT INTERPOLATION
1395  *
1396  ****************************************************************/
1397
1398
1399 /* shift the original coordinates of all points between `p1' and */
1400 /* `p2' to get hinted coordinates, using the same difference as */
1401 /* given by `ref' */
1402
1403 static void
1404 ta_iup_shift(TA_Point p1,
1405              TA_Point p2,
1406              TA_Point ref)
1407 {
1408   TA_Point p;
1409   FT_Pos delta = ref->u - ref->v;
1410
1411
1412   if (delta == 0)
1413     return;
1414
1415   for (p = p1; p < ref; p++)
1416     p->u = p->v + delta;
1417
1418   for (p = ref + 1; p <= p2; p++)
1419     p->u = p->v + delta;
1420 }
1421
1422
1423 /* interpolate the original coordinates of all points between `p1' and */
1424 /* `p2' to get hinted coordinates, using `ref1' and `ref2' as the */
1425 /* reference points; the `u' and `v' members are the current and */
1426 /* original coordinate values, respectively. */
1427
1428 /* details can be found in the TrueType bytecode specification */
1429
1430 static void
1431 ta_iup_interp(TA_Point p1,
1432               TA_Point p2,
1433               TA_Point ref1,
1434               TA_Point ref2)
1435 {
1436   TA_Point p;
1437   FT_Pos u, v1, v2, u1, u2, d1, d2;
1438
1439
1440   if (p1 > p2)
1441     return;
1442
1443   if (ref1->v > ref2->v)
1444   {
1445     p = ref1;
1446     ref1 = ref2;
1447     ref2 = p;
1448   }
1449
1450   v1 = ref1->v;
1451   v2 = ref2->v;
1452   u1 = ref1->u;
1453   u2 = ref2->u;
1454   d1 = u1 - v1;
1455   d2 = u2 - v2;
1456
1457   if (u1 == u2 || v1 == v2)
1458   {
1459     for (p = p1; p <= p2; p++)
1460     {
1461       u = p->v;
1462
1463       if (u <= v1)
1464         u += d1;
1465       else if (u >= v2)
1466         u += d2;
1467       else
1468         u = u1;
1469
1470       p->u = u;
1471     }
1472   }
1473   else
1474   {
1475     FT_Fixed scale = FT_DivFix(u2 - u1, v2 - v1);
1476
1477
1478     for (p = p1; p <= p2; p++)
1479     {
1480       u = p->v;
1481
1482       if (u <= v1)
1483         u += d1;
1484       else if (u >= v2)
1485         u += d2;
1486       else
1487         u = u1 + FT_MulFix(u - v1, scale);
1488
1489       p->u = u;
1490     }
1491   }
1492 }
1493
1494
1495 /* hint the weak points -- */
1496 /* this is equivalent to the TrueType `IUP' hinting instruction */
1497
1498 void
1499 ta_glyph_hints_align_weak_points(TA_GlyphHints hints,
1500                                  TA_Dimension dim)
1501 {
1502   TA_Point points = hints->points;
1503   TA_Point point_limit = points + hints->num_points;
1504
1505   TA_Point* contour = hints->contours;
1506   TA_Point* contour_limit = contour + hints->num_contours;
1507
1508   FT_UShort touch_flag;
1509   TA_Point point;
1510   TA_Point end_point;
1511   TA_Point first_point;
1512
1513
1514   /* pass 1: move segment points to edge positions */
1515
1516   if (dim == TA_DIMENSION_HORZ)
1517   {
1518     touch_flag = TA_FLAG_TOUCH_X;
1519
1520     for (point = points; point < point_limit; point++)
1521     {
1522       point->u = point->x;
1523       point->v = point->ox;
1524     }
1525   }
1526   else
1527   {
1528     touch_flag = TA_FLAG_TOUCH_Y;
1529
1530     for (point = points; point < point_limit; point++)
1531     {
1532       point->u = point->y;
1533       point->v = point->oy;
1534     }
1535   }
1536
1537   for (; contour < contour_limit; contour++)
1538   {
1539     TA_Point first_touched, last_touched;
1540
1541
1542     point = *contour;
1543     end_point = point->prev;
1544     first_point = point;
1545
1546     /* find first touched point */
1547     for (;;)
1548     {
1549       if (point > end_point) /* no touched point in contour */
1550         goto NextContour;
1551
1552       if (point->flags & touch_flag)
1553         break;
1554
1555       point++;
1556     }
1557
1558     first_touched = point;
1559
1560     for (;;)
1561     {
1562       /* skip any touched neighbours */
1563       while (point < end_point
1564              && (point[1].flags & touch_flag) != 0)
1565         point++;
1566
1567       last_touched = point;
1568
1569       /* find the next touched point, if any */
1570       point++;
1571       for (;;)
1572       {
1573         if (point > end_point)
1574           goto EndContour;
1575
1576         if ((point->flags & touch_flag) != 0)
1577           break;
1578
1579         point++;
1580       }
1581
1582       /* interpolate between last_touched and point */
1583       ta_iup_interp(last_touched + 1, point - 1,
1584                     last_touched, point);
1585     }
1586
1587   EndContour:
1588     /* special case: only one point was touched */
1589     if (last_touched == first_touched)
1590       ta_iup_shift(first_point, end_point, first_touched);
1591
1592     else /* interpolate the last part */
1593     {
1594       if (last_touched < end_point)
1595         ta_iup_interp(last_touched + 1, end_point,
1596                       last_touched, first_touched);
1597
1598       if (first_touched > points)
1599         ta_iup_interp(first_point, first_touched - 1,
1600                       last_touched, first_touched);
1601     }
1602
1603   NextContour:
1604     ;
1605   }
1606
1607   /* now save the interpolated values back to x/y */
1608   if (dim == TA_DIMENSION_HORZ)
1609   {
1610     for (point = points; point < point_limit; point++)
1611       point->x = point->u;
1612   }
1613   else
1614   {
1615     for (point = points; point < point_limit; point++)
1616       point->y = point->u;
1617   }
1618 }
1619
1620
1621 #ifdef TA_CONFIG_OPTION_USE_WARPER
1622
1623 /* apply (small) warp scale and warp delta for given dimension */
1624
1625 static void
1626 ta_glyph_hints_scale_dim(TA_GlyphHints hints,
1627                          TA_Dimension dim,
1628                          FT_Fixed scale,
1629                          FT_Pos delta)
1630 {
1631   TA_Point points = hints->points;
1632   TA_Point points_limit = points + hints->num_points;
1633   TA_Point point;
1634
1635
1636   if (dim == TA_DIMENSION_HORZ)
1637   {
1638     for (point = points; point < points_limit; point++)
1639       point->x = FT_MulFix(point->fx, scale) + delta;
1640   }
1641   else
1642   {
1643     for (point = points; point < points_limit; point++)
1644       point->y = FT_MulFix(point->fy, scale) + delta;
1645   }
1646 }
1647
1648 #endif /* TA_CONFIG_OPTION_USE_WARPER */
1649
1650 /* end of tahints.c */