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