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