lib/tahints.c

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