src/tahints.c

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