src/tahints.c

   1 /* tahints.c */
   2
   3 /*
   4  * Copyright (C) 2011 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 <string.h>
  21 #include <stdlib.h>
  22 #include "tahints.h"
  23
  24
  25 /* get new segment for given axis */
  26
  27 FT_Error
  28 ta_axis_hints_new_segment(TA_AxisHints axis,
  29                           TA_Segment* asegment)
  30 {
  31   FT_Error error = FT_Err_Ok;
  32   TA_Segment segment = NULL;
  33
  34
  35   if (axis->num_segments >= axis->max_segments)
  36   {
  37     TA_Segment segments_new;
  38
  39     FT_Int old_max = axis->max_segments;
  40     FT_Int new_max = old_max;
  41     FT_Int big_max = (FT_Int)(FT_INT_MAX / sizeof (*segment));
  42
  43
  44     if (old_max >= big_max)
  45     {
  46       error = FT_Err_Out_Of_Memory;
  47       goto Exit;
  48     }
  49
  50     new_max += (new_max >> 2) + 4;
  51     if (new_max < old_max
  52         || new_max > big_max)
  53       new_max = big_max;
  54
  55     segments_new = (TA_Segment)realloc(axis->segments,
  56                                        new_max * sizeof (TA_SegmentRec));
  57     if (!segments_new)
  58       return FT_Err_Out_Of_Memory;
  59
  60     axis->segments = segments_new;
  61     axis->max_segments = new_max;
  62   }
  63
  64   segment = axis->segments + axis->num_segments++;
  65
  66 Exit:
  67   *asegment = segment;
  68   return error;
  69 }
  70
  71
  72 /* get new edge for given axis, direction, and position */
  73
  74 FT_Error
  75 ta_axis_hints_new_edge(TA_AxisHints axis,
  76                        FT_Int fpos,
  77                        TA_Direction dir,
  78                        TA_Edge* anedge)
  79 {
  80   FT_Error error = FT_Err_Ok;
  81   TA_Edge edge = NULL;
  82   TA_Edge edges;
  83
  84
  85   if (axis->num_edges >= axis->max_edges)
  86   {
  87     TA_Edge edges_new;
  88
  89     FT_Int old_max = axis->max_edges;
  90     FT_Int new_max = old_max;
  91     FT_Int big_max = (FT_Int)(FT_INT_MAX / sizeof (*edge));
  92
  93
  94     if (old_max >= big_max)
  95     {
  96       error = FT_Err_Out_Of_Memory;
  97       goto Exit;
  98     }
  99
 100     new_max += (new_max >> 2) + 4;
 101     if (new_max < old_max
 102         || new_max > big_max)
 103       new_max = big_max;
 104
 105     edges_new = (TA_Edge)realloc(axis->edges,
 106                                  new_max * sizeof (TA_EdgeRec));
 107     if (!edges_new)
 108       return FT_Err_Out_Of_Memory;
 109
 110     axis->edges = edges_new;
 111     axis->max_edges = new_max;
 112   }
 113
 114   edges = axis->edges;
 115   edge = edges + axis->num_edges;
 116
 117   while (edge > edges)
 118   {
 119     if (edge[-1].fpos < fpos)
 120       break;
 121
 122     /* we want the edge with same position and minor direction */
 123     /* to appear before those in the major one in the list */
 124     if (edge[-1].fpos == fpos
 125         && dir == axis->major_dir)
 126       break;
 127
 128     edge[0] = edge[-1];
 129     edge--;
 130   }
 131
 132   axis->num_edges++;
 133
 134   memset(edge, 0, sizeof (TA_EdgeRec));
 135   edge->fpos = (FT_Short)fpos;
 136   edge->dir = (FT_Char)dir;
 137
 138 Exit:
 139   *anedge = edge;
 140   return error;
 141 }
 142
 143
 144 #ifdef TA_DEBUG
 145
 146 #include <stdlib.h>
 147
 148 static const char*
 149 ta_dir_str(TA_Direction dir)
 150 {
 151   const char* result;
 152
 153
 154   switch (dir)
 155   {
 156   case TA_DIR_UP:
 157     result = "up";
 158     break;
 159   case TA_DIR_DOWN:
 160     result = "down";
 161     break;
 162   case TA_DIR_LEFT:
 163     result = "left";
 164     break;
 165   case TA_DIR_RIGHT:
 166     result = "right";
 167     break;
 168   default:
 169     result = "none";
 170   }
 171
 172   return result;
 173 }
 174
 175
 176 #define TA_INDEX_NUM(ptr, base) \
 177           ((ptr) ? ((ptr) - (base)) \
 178                  : -1)
 179
 180
 181 void
 182 ta_glyph_hints_dump_points(TA_GlyphHints hints)
 183 {
 184   TA_Point points = hints->points;
 185   TA_Point limit = points + hints->num_points;
 186   TA_Point point;
 187
 188
 189   printf("Table of points:\n");
 190   printf("  [ index |  xorg |  yorg | xscale | yscale"
 191            " |  xfit |  yfit |  flags ]\n");
 192
 193   for (point = points; point < limit; point++)
 194   {
 195     printf("  [ %5d | %5d | %5d | %6.2f | %6.2f"
 196              " | %5.2f | %5.2f | %c%c%c%c%c%c ]\n",
 197            point - points,
 198            point->fx,
 199            point->fy,
 200            point->ox / 64.0,
 201            point->oy / 64.0,
 202            point->x / 64.0,
 203            point->y / 64.0,
 204            (point->flags & TA_FLAG_WEAK_INTERPOLATION) ? 'w' : ' ',
 205            (point->flags & TA_FLAG_INFLECTION) ? 'i' : ' ',
 206            (point->flags & TA_FLAG_EXTREMA_X) ? '<' : ' ',
 207            (point->flags & TA_FLAG_EXTREMA_Y) ? 'v' : ' ',
 208            (point->flags & TA_FLAG_ROUND_X) ? '(' : ' ',
 209            (point->flags & TA_FLAG_ROUND_Y) ? 'u' : ' ');
 210   }
 211   printf("\n");
 212 }
 213
 214
 215 static const char*
 216 ta_edge_flags_to_string(FT_Byte flags)
 217 {
 218   static char temp[32];
 219   int pos = 0;
 220
 221
 222   if (flags & TA_EDGE_ROUND)
 223   {
 224     memcpy(temp + pos, "round", 5);
 225     pos += 5;
 226   }
 227   if (flags & TA_EDGE_SERIF)
 228   {
 229     if (pos > 0)
 230       temp[pos++] = ' ';
 231     memcpy(temp + pos, "serif", 5);
 232     pos += 5;
 233   }
 234   if (pos == 0)
 235     return "normal";
 236
 237   temp[pos] = '\0';
 238
 239   return temp;
 240 }
 241
 242
 243 /* dump the array of linked segments */
 244
 245 void
 246 ta_glyph_hints_dump_segments(TA_GlyphHints hints)
 247 {
 248   FT_Int dimension;
 249
 250
 251   for (dimension = 1; dimension >= 0; dimension--)
 252   {
 253     TA_AxisHints axis = &hints->axis[dimension];
 254     TA_Point points = hints->points;
 255     TA_Edge edges = axis->edges;
 256     TA_Segment segments = axis->segments;
 257     TA_Segment limit = segments + axis->num_segments;
 258     TA_Segment seg;
 259
 260
 261     printf("Table of %s segments:\n",
 262            dimension == TA_DIMENSION_HORZ ? "vertical"
 263                                           : "horizontal");
 264     printf("  [ index |  pos  |  dir  | from |  to  | link | serif | edge |"
 265              " height | extra |    flags    ]\n");
 266
 267     for (seg = segments; seg < limit; seg++)
 268     {
 269       printf("  [ %5d | %5.2g | %5s | %4d | %4d | %4d | %5d | %4d |"
 270                " %6d | %5d | %11s ]\n",
 271              seg - segments,
 272              dimension == TA_DIMENSION_HORZ ? (int)seg->first->ox / 64.0
 273                                             : (int)seg->first->oy / 64.0,
 274              ta_dir_str((TA_Direction)seg->dir),
 275              TA_INDEX_NUM(seg->first, points),
 276              TA_INDEX_NUM(seg->last, points),
 277              TA_INDEX_NUM(seg->link, segments),
 278              TA_INDEX_NUM(seg->serif, segments),
 279              TA_INDEX_NUM(seg->edge, edges),
 280              seg->height,
 281              seg->height - (seg->max_coord - seg->min_coord),
 282              ta_edge_flags_to_string(seg->flags));
 283     }
 284     printf("\n");
 285   }
 286 }
 287
 288
 289 /* dump the array of linked edges */
 290
 291 void
 292 ta_glyph_hints_dump_edges(TA_GlyphHints hints)
 293 {
 294   FT_Int dimension;
 295
 296
 297   for (dimension = 1; dimension >= 0; dimension--)
 298   {
 299     TA_AxisHints axis = &hints->axis[dimension];
 300     TA_Edge edges = axis->edges;
 301     TA_Edge limit = edges + axis->num_edges;
 302     TA_Edge edge;
 303
 304
 305     /* note that TA_DIMENSION_HORZ corresponds to _vertical_ edges */
 306     /* since they have a constant X coordinate */
 307     printf("Table of %s edges:\n",
 308            dimension == TA_DIMENSION_HORZ ? "vertical"
 309                                           : "horizontal");
 310     printf("  [ index |  pos  |  dir  | link |"
 311              " serif | blue | opos  |  pos  |    flags    ]\n");
 312
 313     for (edge = edges; edge < limit; edge++)
 314     {
 315       printf("  [ %5d | %5.2g | %5s | %4d |"
 316                " %5d |   %c  | %5.2f | %5.2f | %11s ]\n",
 317              edge - edges,
 318              (int)edge->opos / 64.0,
 319              ta_dir_str((TA_Direction)edge->dir),
 320              TA_INDEX_NUM(edge->link, edges),
 321              TA_INDEX_NUM(edge->serif, edges),
 322              edge->blue_edge ? 'y' : 'n',
 323              edge->opos / 64.0,
 324              edge->pos / 64.0,
 325              ta_edge_flags_to_string(edge->flags));
 326     }
 327     printf("\n");
 328   }
 329 }
 330
 331
 332 void
 333 ta_glyph_hints_dump_edge_links(TA_GlyphHints hints)
 334 {
 335   FT_Int dimension;
 336
 337
 338   for (dimension = 1; dimension >= 0; dimension--)
 339   {
 340     TA_AxisHints axis = &hints->axis[dimension];
 341     TA_Segment segments = axis->segments;
 342     TA_Edge edges = axis->edges;
 343     TA_Edge limit = edges + axis->num_edges;
 344
 345     TA_Edge edge;
 346     TA_Segment seg;
 347
 348
 349     printf("%s edges consist of the following segments:\n",
 350            dimension == TA_DIMENSION_HORZ ? "Vertical"
 351                                           : "Horizontal");
 352     for (edge = edges; edge < limit; edge++)
 353     {
 354       printf("  %2d:", edge - edges);
 355
 356       seg = edge->first;
 357       do
 358       {
 359         printf(" %d", seg - segments);
 360         seg = seg->edge_next;
 361       } while (seg != edge->first);
 362
 363       printf("\n");
 364     }
 365     printf("\n");
 366   }
 367 }
 368
 369 #endif /* TA_DEBUG */
 370
 371
 372 /* compute the direction value of a given vector */
 373
 374 TA_Direction
 375 ta_direction_compute(FT_Pos dx,
 376                      FT_Pos dy)
 377 {
 378   FT_Pos ll, ss;  /* long and short arm lengths */
 379   TA_Direction dir; /* candidate direction */
 380
 381
 382   if (dy >= dx)
 383   {
 384     if (dy >= -dx)
 385     {
 386       dir = TA_DIR_UP;
 387       ll = dy;
 388       ss = dx;
 389     }
 390     else
 391     {
 392       dir = TA_DIR_LEFT;
 393       ll = -dx;
 394       ss = dy;
 395     }
 396     }
 397   else /* dy < dx */
 398   {
 399     if (dy >= -dx)
 400     {
 401       dir = TA_DIR_RIGHT;
 402       ll = dx;
 403       ss = dy;
 404     }
 405     else
 406     {
 407       dir = TA_DIR_DOWN;
 408       ll = dy;
 409       ss = dx;
 410     }
 411   }
 412
 413   /* return no direction if arm lengths differ too much */
 414   /* (value 14 is heuristic)                            */
 415   ss *= 14;
 416   if (TA_ABS(ll) <= TA_ABS(ss))
 417     dir = TA_DIR_NONE;
 418
 419   return dir;
 420 }
 421
 422
 423 void
 424 ta_glyph_hints_init(TA_GlyphHints hints)
 425 {
 426   memset(hints, 0, sizeof (TA_GlyphHintsRec));
 427 }
 428
 429
 430 void
 431 ta_glyph_hints_done(TA_GlyphHints hints)
 432 {
 433   int dim;
 434
 435
 436   if (!hints)
 437     return;
 438
 439   /* we don't need to free the segment and edge buffers */
 440   /* since they are really within the hints->points array */
 441   for (dim = 0; dim < TA_DIMENSION_MAX; dim++)
 442   {
 443     TA_AxisHints axis = &hints->axis[dim];
 444
 445
 446     axis->num_segments = 0;
 447     axis->max_segments = 0;
 448     free(axis->segments);
 449     axis->segments = NULL;
 450
 451     axis->num_edges = 0;
 452     axis->max_edges = 0;
 453     free(axis->edges);
 454     axis->edges = NULL;
 455   }
 456
 457   free(hints->contours);
 458   hints->contours = NULL;
 459   hints->max_contours = 0;
 460   hints->num_contours = 0;
 461
 462   free(hints->points);
 463   hints->points = NULL;
 464   hints->num_points = 0;
 465   hints->max_points = 0;
 466 }
 467
 468
 469 /* reset metrics */
 470
 471 void
 472 ta_glyph_hints_rescale(TA_GlyphHints hints,
 473                        TA_ScriptMetrics metrics)
 474 {
 475   hints->metrics = metrics;
 476   hints->scaler_flags = metrics->scaler.flags;
 477 }
 478
 479
 480 /* from FreeType's ftcalc.c */
 481
 482 static FT_Int
 483 ta_corner_is_flat(FT_Pos in_x,
 484                   FT_Pos in_y,
 485                   FT_Pos out_x,
 486                   FT_Pos out_y)
 487 {
 488   FT_Pos ax = in_x;
 489   FT_Pos ay = in_y;
 490
 491   FT_Pos d_in, d_out, d_corner;
 492
 493
 494   if (ax < 0)
 495     ax = -ax;
 496   if (ay < 0)
 497     ay = -ay;
 498   d_in = ax + ay;
 499
 500   ax = out_x;
 501   if (ax < 0)
 502     ax = -ax;
 503   ay = out_y;
 504   if (ay < 0)
 505     ay = -ay;
 506   d_out = ax + ay;
 507
 508   ax = out_x + in_x;
 509   if (ax < 0)
 510     ax = -ax;
 511   ay = out_y + in_y;
 512   if (ay < 0)
 513     ay = -ay;
 514   d_corner = ax + ay;
 515
 516   return (d_in + d_out - d_corner) < (d_corner >> 4);
 517 }
 518
 519
 520 /* recompute all TA_Point in TA_GlyphHints */
 521 /* from the definitions in a source outline */
 522
 523 FT_Error
 524 ta_glyph_hints_reload(TA_GlyphHints hints,
 525                       FT_Outline* outline)
 526 {
 527   FT_Error error = FT_Err_Ok;
 528   TA_Point points;
 529   FT_UInt old_max, new_max;
 530
 531   FT_Fixed x_scale = hints->x_scale;
 532   FT_Fixed y_scale = hints->y_scale;
 533   FT_Pos x_delta = hints->x_delta;
 534   FT_Pos y_delta = hints->y_delta;
 535
 536
 537   hints->num_points = 0;
 538   hints->num_contours = 0;
 539
 540   hints->axis[0].num_segments = 0;
 541   hints->axis[0].num_edges = 0;
 542   hints->axis[1].num_segments = 0;
 543   hints->axis[1].num_edges = 0;
 544
 545   /* first of all, reallocate the contours array if necessary */
 546   new_max = (FT_UInt)outline->n_contours;
 547   old_max = hints->max_contours;
 548   if (new_max > old_max)
 549   {
 550     TA_Point* contours_new;
 551
 552
 553     new_max = (new_max + 3) & ~3; /* round up to a multiple of 4 */
 554
 555     contours_new = (TA_Point*)realloc(hints->contours,
 556                                       new_max * sizeof (TA_Point));
 557     if (!contours_new)
 558       return FT_Err_Out_Of_Memory;
 559
 560     hints->contours = contours_new;
 561     hints->max_contours = new_max;
 562   }
 563
 564   /* reallocate the points arrays if necessary -- we reserve */
 565   /* two additional point positions, used to hint metrics appropriately */
 566   new_max = (FT_UInt)(outline->n_points + 2);
 567   old_max = hints->max_points;
 568   if (new_max > old_max)
 569   {
 570     TA_Point  points_new;
 571
 572
 573     new_max = (new_max + 2 + 7) & ~7; /* round up to a multiple of 8 */
 574
 575     points_new = (TA_Point)realloc(hints->points,
 576                                    new_max * sizeof (TA_PointRec));
 577     if (!points_new)
 578       return FT_Err_Out_Of_Memory;
 579
 580     hints->points = points_new;
 581     hints->max_points = new_max;
 582   }
 583
 584   hints->num_points = outline->n_points;
 585   hints->num_contours = outline->n_contours;
 586
 587   /* we can't rely on the value of `FT_Outline.flags' to know the fill */
 588   /* direction used for a glyph, given that some fonts are broken */
 589   /* (e.g. the Arphic ones); we thus recompute it each time we need to */
 590
 591   hints->axis[TA_DIMENSION_HORZ].major_dir = TA_DIR_UP;
 592   hints->axis[TA_DIMENSION_VERT].major_dir = TA_DIR_LEFT;
 593
 594   if (FT_Outline_Get_Orientation(outline) == FT_ORIENTATION_POSTSCRIPT)
 595   {
 596     hints->axis[TA_DIMENSION_HORZ].major_dir = TA_DIR_DOWN;
 597     hints->axis[TA_DIMENSION_VERT].major_dir = TA_DIR_RIGHT;
 598   }
 599
 600   hints->x_scale = x_scale;
 601   hints->y_scale = y_scale;
 602   hints->x_delta = x_delta;
 603   hints->y_delta = y_delta;
 604
 605   hints->xmin_delta = 0;
 606   hints->xmax_delta = 0;
 607
 608   points = hints->points;
 609   if (hints->num_points == 0)
 610     goto Exit;
 611
 612   {
 613     TA_Point point;
 614     TA_Point point_limit = points + hints->num_points;
 615
 616
 617     /* compute coordinates & Bezier flags, next and prev */
 618     {
 619       FT_Vector* vec = outline->points;
 620       char* tag = outline->tags;
 621
 622       TA_Point end = points + outline->contours[0];
 623       TA_Point prev = end;
 624
 625       FT_Int contour_index = 0;
 626
 627
 628       for (point = points; point < point_limit; point++, vec++, tag++)
 629       {
 630         point->fx = (FT_Short)vec->x;
 631         point->fy = (FT_Short)vec->y;
 632         point->ox = point->x = FT_MulFix(vec->x, x_scale) + x_delta;
 633         point->oy = point->y = FT_MulFix(vec->y, y_scale) + y_delta;
 634
 635         switch (FT_CURVE_TAG(*tag))
 636         {
 637         case FT_CURVE_TAG_CONIC:
 638           point->flags = TA_FLAG_CONIC;
 639           break;
 640         case FT_CURVE_TAG_CUBIC:
 641           point->flags = TA_FLAG_CUBIC;
 642           break;
 643         default:
 644           point->flags = TA_FLAG_NONE;
 645         }
 646
 647         point->prev = prev;
 648         prev->next = point;
 649         prev = point;
 650
 651         if (point == end)
 652         {
 653           if (++contour_index < outline->n_contours)
 654           {
 655             end = points + outline->contours[contour_index];
 656             prev = end;
 657           }
 658         }
 659       }
 660     }
 661
 662     /* set up the contours array */
 663     {
 664       TA_Point* contour = hints->contours;
 665       TA_Point* contour_limit = contour + hints->num_contours;
 666
 667       short* end = outline->contours;
 668       short idx = 0;
 669
 670
 671       for (; contour < contour_limit; contour++, end++)
 672       {
 673         contour[0] = points + idx;
 674         idx = (short)(end[0] + 1);
 675       }
 676     }
 677
 678     /* compute directions of in & out vectors */
 679     {
 680       TA_Point first = points;
 681       TA_Point prev = NULL;
 682
 683       FT_Pos in_x = 0;
 684       FT_Pos in_y = 0;
 685
 686       TA_Direction in_dir = TA_DIR_NONE;
 687
 688
 689       for (point = points; point < point_limit; point++)
 690       {
 691         TA_Point next;
 692         FT_Pos out_x, out_y;
 693
 694
 695         if (point == first)
 696         {
 697           prev = first->prev;
 698           in_x = first->fx - prev->fx;
 699           in_y = first->fy - prev->fy;
 700           in_dir = ta_direction_compute(in_x, in_y);
 701           first = prev + 1;
 702         }
 703
 704         point->in_dir = (FT_Char)in_dir;
 705
 706         next = point->next;
 707         out_x = next->fx - point->fx;
 708         out_y = next->fy - point->fy;
 709
 710         in_dir = ta_direction_compute(out_x, out_y);
 711         point->out_dir = (FT_Char)in_dir;
 712
 713         /* check for weak points */
 714
 715         if (point->flags & TA_FLAG_CONTROL)
 716         {
 717         Is_Weak_Point:
 718           point->flags |= TA_FLAG_WEAK_INTERPOLATION;
 719         }
 720         else if (point->out_dir == point->in_dir)
 721         {
 722           if (point->out_dir != TA_DIR_NONE)
 723             goto Is_Weak_Point;
 724
 725           if (ta_corner_is_flat(in_x, in_y, out_x, out_y))
 726             goto Is_Weak_Point;
 727         }
 728         else if (point->in_dir == -point->out_dir)
 729           goto Is_Weak_Point;
 730
 731         in_x = out_x;
 732         in_y = out_y;
 733         prev = point;
 734       }
 735     }
 736   }
 737
 738 Exit:
 739   return error;
 740 }
 741
 742
 743 /* store the hinted outline in an FT_Outline structure */
 744
 745 void
 746 ta_glyph_hints_save(TA_GlyphHints hints,
 747                     FT_Outline* outline)
 748 {
 749   TA_Point point = hints->points;
 750   TA_Point limit = point + hints->num_points;
 751
 752   FT_Vector* vec = outline->points;
 753   char* tag = outline->tags;
 754
 755
 756   for (; point < limit; point++, vec++, tag++)
 757   {
 758     vec->x = point->x;
 759     vec->y = point->y;
 760
 761     if (point->flags & TA_FLAG_CONIC)
 762       tag[0] = FT_CURVE_TAG_CONIC;
 763     else if (point->flags & TA_FLAG_CUBIC)
 764       tag[0] = FT_CURVE_TAG_CUBIC;
 765     else
 766       tag[0] = FT_CURVE_TAG_ON;
 767   }
 768 }
 769
 770
 771 /****************************************************************
 772  *
 773  *                     EDGE POINT GRID-FITTING
 774  *
 775  ****************************************************************/
 776
 777
 778 /* align all points of an edge to the same coordinate value, */
 779 /* either horizontally or vertically */
 780
 781 void
 782 ta_glyph_hints_align_edge_points(TA_GlyphHints hints,
 783                                  TA_Dimension dim)
 784 {
 785   TA_AxisHints axis = &hints->axis[dim];
 786   TA_Segment segments = axis->segments;
 787   TA_Segment segment_limit = segments + axis->num_segments;
 788   TA_Segment seg;
 789
 790
 791   if (dim == TA_DIMENSION_HORZ)
 792   {
 793     for (seg = segments; seg < segment_limit; seg++)
 794     {
 795       TA_Edge edge = seg->edge;
 796       TA_Point point, first, last;
 797
 798
 799       if (edge == NULL)
 800         continue;
 801
 802       first = seg->first;
 803       last = seg->last;
 804       point = first;
 805       for (;;)
 806       {
 807         point->x = edge->pos;
 808         point->flags |= TA_FLAG_TOUCH_X;
 809
 810         if (point == last)
 811           break;
 812
 813         point = point->next;
 814       }
 815     }
 816   }
 817   else
 818   {
 819     for (seg = segments; seg < segment_limit; seg++)
 820     {
 821       TA_Edge edge = seg->edge;
 822       TA_Point point, first, last;
 823
 824
 825       if (edge == NULL)
 826         continue;
 827
 828       first = seg->first;
 829       last = seg->last;
 830       point = first;
 831       for (;;)
 832       {
 833         point->y = edge->pos;
 834         point->flags |= TA_FLAG_TOUCH_Y;
 835
 836         if (point == last)
 837           break;
 838
 839         point = point->next;
 840       }
 841     }
 842   }
 843 }
 844
 845
 846 /****************************************************************
 847  *
 848  *                    STRONG POINT INTERPOLATION
 849  *
 850  ****************************************************************/
 851
 852
 853 /* hint the strong points -- */
 854 /* this is equivalent to the TrueType `IP' hinting instruction */
 855
 856 void
 857 ta_glyph_hints_align_strong_points(TA_GlyphHints hints,
 858                                    TA_Dimension dim)
 859 {
 860   TA_Point points = hints->points;
 861   TA_Point point_limit = points + hints->num_points;
 862
 863   TA_AxisHints axis = &hints->axis[dim];
 864
 865   TA_Edge edges = axis->edges;
 866   TA_Edge edge_limit = edges + axis->num_edges;
 867
 868   FT_UShort touch_flag;
 869
 870
 871   if (dim == TA_DIMENSION_HORZ)
 872     touch_flag = TA_FLAG_TOUCH_X;
 873   else
 874     touch_flag = TA_FLAG_TOUCH_Y;
 875
 876   if (edges < edge_limit)
 877   {
 878     TA_Point point;
 879     TA_Edge edge;
 880
 881
 882     for (point = points; point < point_limit; point++)
 883     {
 884       FT_Pos u, ou, fu;  /* point position */
 885       FT_Pos delta;
 886
 887
 888       if (point->flags & touch_flag)
 889         continue;
 890
 891       /* if this point is candidate to weak interpolation, we */
 892       /* interpolate it after all strong points have been processed */
 893
 894       if ((point->flags & TA_FLAG_WEAK_INTERPOLATION)
 895           && !(point->flags & TA_FLAG_INFLECTION))
 896         continue;
 897
 898       if (dim == TA_DIMENSION_VERT)
 899       {
 900         u = point->fy;
 901         ou = point->oy;
 902       }
 903       else
 904       {
 905         u = point->fx;
 906         ou = point->ox;
 907       }
 908
 909       fu = u;
 910
 911       /* is the point before the first edge? */
 912       edge = edges;
 913       delta = edge->fpos - u;
 914       if (delta >= 0)
 915       {
 916         u = edge->pos - (edge->opos - ou);
 917
 918         if (hints->recorder)
 919           hints->recorder(ta_ip_before, hints, dim,
 920                           point, NULL, NULL, NULL, NULL);
 921
 922         goto Store_Point;
 923       }
 924
 925       /* is the point after the last edge? */
 926       edge = edge_limit - 1;
 927       delta = u - edge->fpos;
 928       if (delta >= 0)
 929       {
 930         u = edge->pos + (ou - edge->opos);
 931
 932         if (hints->recorder)
 933           hints->recorder(ta_ip_after, hints, dim,
 934                           point, NULL, NULL, NULL, NULL);
 935
 936         goto Store_Point;
 937       }
 938
 939       {
 940         FT_PtrDist min, max, mid;
 941         FT_Pos fpos;
 942
 943
 944         /* find enclosing edges */
 945         min = 0;
 946         max = edge_limit - edges;
 947
 948         /* for a small number of edges, a linear search is better */
 949         if (max <= 8)
 950         {
 951           FT_PtrDist nn;
 952
 953
 954           for (nn = 0; nn < max; nn++)
 955             if (edges[nn].fpos >= u)
 956               break;
 957
 958           if (edges[nn].fpos == u)
 959           {
 960             u = edges[nn].pos;
 961
 962             if (hints->recorder)
 963               hints->recorder(ta_ip_on, hints, dim,
 964                               point, &edges[nn], NULL, NULL, NULL);
 965
 966             goto Store_Point;
 967           }
 968           min = nn;
 969         }
 970         else
 971           while (min < max)
 972           {
 973             mid = (max + min) >> 1;
 974             edge = edges + mid;
 975             fpos = edge->fpos;
 976
 977             if (u < fpos)
 978               max = mid;
 979             else if (u > fpos)
 980               min = mid + 1;
 981             else
 982             {
 983               /* we are on the edge */
 984               u = edge->pos;
 985
 986               if (hints->recorder)
 987                 hints->recorder(ta_ip_on, hints, dim,
 988                                 point, edge, NULL, NULL, NULL);
 989
 990               goto Store_Point;
 991             }
 992           }
 993
 994         /* point is not on an edge */
 995         {
 996           TA_Edge before = edges + min - 1;
 997           TA_Edge after = edges + min + 0;
 998
 999
1000           /* assert(before && after && before != after) */
1001           if (before->scale == 0)
1002             before->scale = FT_DivFix(after->pos - before->pos,
1003                                       after->fpos - before->fpos);
1004
1005           u = before->pos + FT_MulFix(fu - before->fpos,
1006                                       before->scale);
1007
1008           if (hints->recorder)
1009             hints->recorder(ta_ip_between, hints, dim,
1010                             point, before, after, NULL, NULL);
1011         }
1012       }
1013
1014     Store_Point:
1015       /* save the point position */
1016       if (dim == TA_DIMENSION_HORZ)
1017         point->x = u;
1018       else
1019         point->y = u;
1020
1021       point->flags |= touch_flag;
1022     }
1023   }
1024 }
1025
1026
1027 /****************************************************************
1028  *
1029  *                    WEAK POINT INTERPOLATION
1030  *
1031  ****************************************************************/
1032
1033
1034 /* shift the original coordinates of all points between `p1' and */
1035 /* `p2' to get hinted coordinates, using the same difference as */
1036 /* given by `ref' */
1037
1038 static void
1039 ta_iup_shift(TA_Point p1,
1040              TA_Point p2,
1041              TA_Point ref)
1042 {
1043   TA_Point p;
1044   FT_Pos delta = ref->u - ref->v;
1045
1046
1047   if (delta == 0)
1048     return;
1049
1050   for (p = p1; p < ref; p++)
1051     p->u = p->v + delta;
1052
1053   for (p = ref + 1; p <= p2; p++)
1054     p->u = p->v + delta;
1055 }
1056
1057
1058 /* interpolate the original coordinates of all points between `p1' and */
1059 /* `p2' to get hinted coordinates, using `ref1' and `ref2' as the */
1060 /* reference points;  the `u' and `v' members are the current and */
1061 /* original coordinate values, respectively. */
1062
1063 /* details can be found in the TrueType bytecode specification */
1064
1065 static void
1066 ta_iup_interp(TA_Point p1,
1067               TA_Point p2,
1068               TA_Point ref1,
1069               TA_Point ref2)
1070 {
1071   TA_Point p;
1072   FT_Pos u;
1073   FT_Pos v1 = ref1->v;
1074   FT_Pos v2 = ref2->v;
1075   FT_Pos d1 = ref1->u - v1;
1076   FT_Pos d2 = ref2->u - v2;
1077
1078
1079   if (p1 > p2)
1080     return;
1081
1082   if (v1 == v2)
1083   {
1084     for (p = p1; p <= p2; p++)
1085     {
1086       u = p->v;
1087
1088       if (u <= v1)
1089         u += d1;
1090       else
1091         u += d2;
1092
1093       p->u = u;
1094     }
1095     return;
1096   }
1097
1098   if (v1 < v2)
1099   {
1100     for (p = p1; p <= p2; p++)
1101     {
1102       u = p->v;
1103
1104       if (u <= v1)
1105         u += d1;
1106       else if (u >= v2)
1107         u += d2;
1108       else
1109         u = ref1->u + FT_MulDiv(u - v1, ref2->u - ref1->u, v2 - v1);
1110
1111       p->u = u;
1112     }
1113   }
1114   else
1115   {
1116     for (p = p1; p <= p2; p++)
1117     {
1118       u = p->v;
1119
1120       if (u <= v2)
1121         u += d2;
1122       else if (u >= v1)
1123         u += d1;
1124       else
1125         u = ref1->u + FT_MulDiv(u - v1, ref2->u - ref1->u, v2 - v1);
1126
1127       p->u = u;
1128     }
1129   }
1130 }
1131
1132
1133 /* hint the weak points -- */
1134 /* this is equivalent to the TrueType `IUP' hinting instruction */
1135
1136 void
1137 ta_glyph_hints_align_weak_points(TA_GlyphHints hints,
1138                                  TA_Dimension dim)
1139 {
1140   TA_Point points = hints->points;
1141   TA_Point point_limit = points + hints->num_points;
1142
1143   TA_Point* contour = hints->contours;
1144   TA_Point* contour_limit = contour + hints->num_contours;
1145
1146   FT_UShort touch_flag;
1147   TA_Point point;
1148   TA_Point end_point;
1149   TA_Point first_point;
1150
1151
1152   /* pass 1: move segment points to edge positions */
1153
1154   if (dim == TA_DIMENSION_HORZ)
1155   {
1156     touch_flag = TA_FLAG_TOUCH_X;
1157
1158     for (point = points; point < point_limit; point++)
1159     {
1160       point->u = point->x;
1161       point->v = point->ox;
1162     }
1163   }
1164   else
1165   {
1166     touch_flag = TA_FLAG_TOUCH_Y;
1167
1168     for (point = points; point < point_limit; point++)
1169     {
1170       point->u = point->y;
1171       point->v = point->oy;
1172     }
1173   }
1174
1175   point = points;
1176
1177   for (; contour < contour_limit; contour++)
1178   {
1179     TA_Point first_touched, last_touched;
1180
1181
1182     point = *contour;
1183     end_point = point->prev;
1184     first_point = point;
1185
1186     /* find first touched point */
1187     for (;;)
1188     {
1189       if (point > end_point) /* no touched point in contour */
1190         goto NextContour;
1191
1192       if (point->flags & touch_flag)
1193         break;
1194
1195       point++;
1196     }
1197
1198     first_touched = point;
1199     last_touched = point;
1200
1201     for (;;)
1202     {
1203       /* skip any touched neighbours */
1204       while (point < end_point
1205              && (point[1].flags & touch_flag) != 0)
1206         point++;
1207
1208       last_touched = point;
1209
1210       /* find the next touched point, if any */
1211       point++;
1212       for (;;)
1213       {
1214         if (point > end_point)
1215           goto EndContour;
1216
1217         if ((point->flags & touch_flag) != 0)
1218           break;
1219
1220         point++;
1221       }
1222
1223       /* interpolate between last_touched and point */
1224       ta_iup_interp(last_touched + 1, point - 1,
1225                     last_touched, point);
1226     }
1227
1228   EndContour:
1229     /* special case: only one point was touched */
1230     if (last_touched == first_touched)
1231       ta_iup_shift(first_point, end_point, first_touched);
1232
1233     else /* interpolate the last part */
1234     {
1235       if (last_touched < end_point)
1236         ta_iup_interp(last_touched + 1, end_point,
1237                       last_touched, first_touched);
1238
1239       if (first_touched > points)
1240         ta_iup_interp(first_point, first_touched - 1,
1241                       last_touched, first_touched);
1242     }
1243
1244   NextContour:
1245     ;
1246   }
1247
1248   /* now save the interpolated values back to x/y */
1249   if (dim == TA_DIMENSION_HORZ)
1250   {
1251     for (point = points; point < point_limit; point++)
1252       point->x = point->u;
1253   }
1254   else
1255   {
1256     for (point = points; point < point_limit; point++)
1257       point->y = point->u;
1258   }
1259 }
1260
1261
1262 #ifdef TA_CONFIG_OPTION_USE_WARPER
1263
1264 /* apply (small) warp scale and warp delta for given dimension */
1265
1266 static void
1267 ta_glyph_hints_scale_dim(TA_GlyphHints hints,
1268                          TA_Dimension dim,
1269                          FT_Fixed scale,
1270                          FT_Pos delta)
1271 {
1272   TA_Point points = hints->points;
1273   TA_Point points_limit = points + hints->num_points;
1274   TA_Point point;
1275
1276
1277   if (dim == TA_DIMENSION_HORZ)
1278   {
1279     for (point = points; point < points_limit; point++)
1280       point->x = FT_MulFix(point->fx, scale) + delta;
1281   }
1282   else
1283   {
1284     for (point = points; point < points_limit; point++)
1285       point->y = FT_MulFix(point->fy, scale) + delta;
1286   }
1287 }
1288
1289 #endif /* TA_CONFIG_OPTION_USE_WARPER */
1290
1291 /* end of tahints.c */