extension/SDL2_ttf-2.0.14/external/freetype-2.4.12/src/autofit/afhints.c

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