src/third_party/freetype2/src/src/autofit/afhints.c

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