1 /****************************************************************************
   2  *
   3  * pshalgo.c
   4  *
   5  *   PostScript hinting algorithm (body).
   6  *
   7  * Copyright (C) 2001-2020 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 <ft2build.h>
  20 #include FT_INTERNAL_OBJECTS_H
  21 #include FT_INTERNAL_DEBUG_H
  22 #include FT_INTERNAL_CALC_H
  23 #include "pshalgo.h"
  24 
  25 #include "pshnterr.h"
  26 
  27 
  28 #undef  FT_COMPONENT
  29 #define FT_COMPONENT  pshalgo
  30 
  31 
  32 #ifdef DEBUG_HINTER
  33   PSH_Hint_Table  ps_debug_hint_table = NULL;
  34   PSH_HintFunc    ps_debug_hint_func  = NULL;
  35   PSH_Glyph       ps_debug_glyph      = NULL;
  36 #endif
  37 
  38 
  39 #define  COMPUTE_INFLEXS  /* compute inflection points to optimize `S' */
  40                           /* and similar glyphs                        */
  41 
  42 
  43   /*************************************************************************/
  44   /*************************************************************************/
  45   /*****                                                               *****/
  46   /*****                  BASIC HINTS RECORDINGS                       *****/
  47   /*****                                                               *****/
  48   /*************************************************************************/
  49   /*************************************************************************/
  50 
  51   /* return true if two stem hints overlap */
  52   static FT_Int
  53   psh_hint_overlap( PSH_Hint  hint1,
  54                     PSH_Hint  hint2 )
  55   {
  56     return ADD_INT( hint1->org_pos, hint1->org_len ) >= hint2->org_pos &&
  57            ADD_INT( hint2->org_pos, hint2->org_len ) >= hint1->org_pos;
  58   }
  59 
  60 
  61   /* destroy hints table */
  62   static void
  63   psh_hint_table_done( PSH_Hint_Table  table,
  64                        FT_Memory       memory )
  65   {
  66     FT_FREE( table->zones );
  67     table->num_zones = 0;
  68     table->zone      = NULL;
  69 
  70     FT_FREE( table->sort );
  71     FT_FREE( table->hints );
  72     table->num_hints   = 0;
  73     table->max_hints   = 0;
  74     table->sort_global = NULL;
  75   }
  76 
  77 
  78   /* deactivate all hints in a table */
  79   static void
  80   psh_hint_table_deactivate( PSH_Hint_Table  table )
  81   {
  82     FT_UInt   count = table->max_hints;
  83     PSH_Hint  hint  = table->hints;
  84 
  85 
  86     for ( ; count > 0; count--, hint++ )
  87     {
  88       psh_hint_deactivate( hint );
  89       hint->order = -1;
  90     }
  91   }
  92 
  93 
  94   /* internal function to record a new hint */
  95   static void
  96   psh_hint_table_record( PSH_Hint_Table  table,
  97                          FT_UInt         idx )
  98   {
  99     PSH_Hint  hint = table->hints + idx;
 100 
 101 
 102     if ( idx >= table->max_hints )
 103     {
 104       FT_TRACE0(( "psh_hint_table_record: invalid hint index %d\n", idx ));
 105       return;
 106     }
 107 
 108     /* ignore active hints */
 109     if ( psh_hint_is_active( hint ) )
 110       return;
 111 
 112     psh_hint_activate( hint );
 113 
 114     /* now scan the current active hint set to check */
 115     /* whether `hint' overlaps with another hint     */
 116     {
 117       PSH_Hint*  sorted = table->sort_global;
 118       FT_UInt    count  = table->num_hints;
 119       PSH_Hint   hint2;
 120 
 121 
 122       hint->parent = NULL;
 123       for ( ; count > 0; count--, sorted++ )
 124       {
 125         hint2 = sorted[0];
 126 
 127         if ( psh_hint_overlap( hint, hint2 ) )
 128         {
 129           hint->parent = hint2;
 130           break;
 131         }
 132       }
 133     }
 134 
 135     if ( table->num_hints < table->max_hints )
 136       table->sort_global[table->num_hints++] = hint;
 137     else
 138       FT_TRACE0(( "psh_hint_table_record: too many sorted hints!  BUG!\n" ));
 139   }
 140 
 141 
 142   static void
 143   psh_hint_table_record_mask( PSH_Hint_Table  table,
 144                               PS_Mask         hint_mask )
 145   {
 146     FT_Int    mask = 0, val = 0;
 147     FT_Byte*  cursor = hint_mask->bytes;
 148     FT_UInt   idx, limit;
 149 
 150 
 151     limit = hint_mask->num_bits;
 152 
 153     for ( idx = 0; idx < limit; idx++ )
 154     {
 155       if ( mask == 0 )
 156       {
 157         val  = *cursor++;
 158         mask = 0x80;
 159       }
 160 
 161       if ( val & mask )
 162         psh_hint_table_record( table, idx );
 163 
 164       mask >>= 1;
 165     }
 166   }
 167 
 168 
 169   /* create hints table */
 170   static FT_Error
 171   psh_hint_table_init( PSH_Hint_Table  table,
 172                        PS_Hint_Table   hints,
 173                        PS_Mask_Table   hint_masks,
 174                        PS_Mask_Table   counter_masks,
 175                        FT_Memory       memory )
 176   {
 177     FT_UInt   count;
 178     FT_Error  error;
 179 
 180     FT_UNUSED( counter_masks );
 181 
 182 
 183     count = hints->num_hints;
 184 
 185     /* allocate our tables */
 186     if ( FT_NEW_ARRAY( table->sort,  2 * count     ) ||
 187          FT_NEW_ARRAY( table->hints,     count     ) ||
 188          FT_NEW_ARRAY( table->zones, 2 * count + 1 ) )
 189       goto Exit;
 190 
 191     table->max_hints   = count;
 192     table->sort_global = table->sort + count;
 193     table->num_hints   = 0;
 194     table->num_zones   = 0;
 195     table->zone        = NULL;
 196 
 197     /* initialize the `table->hints' array */
 198     {
 199       PSH_Hint  write = table->hints;
 200       PS_Hint   read  = hints->hints;
 201 
 202 
 203       for ( ; count > 0; count--, write++, read++ )
 204       {
 205         write->org_pos = read->pos;
 206         write->org_len = read->len;
 207         write->flags   = read->flags;
 208       }
 209     }
 210 
 211     /* we now need to determine the initial `parent' stems; first  */
 212     /* activate the hints that are given by the initial hint masks */
 213     if ( hint_masks )
 214     {
 215       PS_Mask  mask = hint_masks->masks;
 216 
 217 
 218       count             = hint_masks->num_masks;
 219       table->hint_masks = hint_masks;
 220 
 221       for ( ; count > 0; count--, mask++ )
 222         psh_hint_table_record_mask( table, mask );
 223     }
 224 
 225     /* finally, do a linear parse in case some hints were left alone */
 226     if ( table->num_hints != table->max_hints )
 227     {
 228       FT_UInt  idx;
 229 
 230 
 231       FT_TRACE0(( "psh_hint_table_init: missing/incorrect hint masks\n" ));
 232 
 233       count = table->max_hints;
 234       for ( idx = 0; idx < count; idx++ )
 235         psh_hint_table_record( table, idx );
 236     }
 237 
 238   Exit:
 239     return error;
 240   }
 241 
 242 
 243   static void
 244   psh_hint_table_activate_mask( PSH_Hint_Table  table,
 245                                 PS_Mask         hint_mask )
 246   {
 247     FT_Int    mask = 0, val = 0;
 248     FT_Byte*  cursor = hint_mask->bytes;
 249     FT_UInt   idx, limit, count;
 250 
 251 
 252     limit = hint_mask->num_bits;
 253     count = 0;
 254 
 255     psh_hint_table_deactivate( table );
 256 
 257     for ( idx = 0; idx < limit; idx++ )
 258     {
 259       if ( mask == 0 )
 260       {
 261         val  = *cursor++;
 262         mask = 0x80;
 263       }
 264 
 265       if ( val & mask )
 266       {
 267         PSH_Hint  hint = &table->hints[idx];
 268 
 269 
 270         if ( !psh_hint_is_active( hint ) )
 271         {
 272           FT_UInt     count2;
 273 
 274 #if 0
 275           PSH_Hint*  sort = table->sort;
 276           PSH_Hint   hint2;
 277 
 278 
 279           for ( count2 = count; count2 > 0; count2--, sort++ )
 280           {
 281             hint2 = sort[0];
 282             if ( psh_hint_overlap( hint, hint2 ) )
 283               FT_TRACE0(( "psh_hint_table_activate_mask:"
 284                           " found overlapping hints\n" ))
 285           }
 286 #else
 287           count2 = 0;
 288 #endif
 289 
 290           if ( count2 == 0 )
 291           {
 292             psh_hint_activate( hint );
 293             if ( count < table->max_hints )
 294               table->sort[count++] = hint;
 295             else
 296               FT_TRACE0(( "psh_hint_tableactivate_mask:"
 297                           " too many active hints\n" ));
 298           }
 299         }
 300       }
 301 
 302       mask >>= 1;
 303     }
 304     table->num_hints = count;
 305 
 306     /* now, sort the hints; they are guaranteed to not overlap */
 307     /* so we can compare their "org_pos" field directly        */
 308     {
 309       FT_Int     i1, i2;
 310       PSH_Hint   hint1, hint2;
 311       PSH_Hint*  sort = table->sort;
 312 
 313 
 314       /* a simple bubble sort will do, since in 99% of cases, the hints */
 315       /* will be already sorted -- and the sort will be linear          */
 316       for ( i1 = 1; i1 < (FT_Int)count; i1++ )
 317       {
 318         hint1 = sort[i1];
 319         for ( i2 = i1 - 1; i2 >= 0; i2-- )
 320         {
 321           hint2 = sort[i2];
 322 
 323           if ( hint2->org_pos < hint1->org_pos )
 324             break;
 325 
 326           sort[i2 + 1] = hint2;
 327           sort[i2]     = hint1;
 328         }
 329       }
 330     }
 331   }
 332 
 333 
 334   /*************************************************************************/
 335   /*************************************************************************/
 336   /*****                                                               *****/
 337   /*****               HINTS GRID-FITTING AND OPTIMIZATION             *****/
 338   /*****                                                               *****/
 339   /*************************************************************************/
 340   /*************************************************************************/
 341 
 342 #if 1
 343   static FT_Pos
 344   psh_dimension_quantize_len( PSH_Dimension  dim,
 345                               FT_Pos         len,
 346                               FT_Bool        do_snapping )
 347   {
 348     if ( len <= 64 )
 349       len = 64;
 350     else
 351     {
 352       FT_Pos  delta = len - dim->stdw.widths[0].cur;
 353 
 354 
 355       if ( delta < 0 )
 356         delta = -delta;
 357 
 358       if ( delta < 40 )
 359       {
 360         len = dim->stdw.widths[0].cur;
 361         if ( len < 48 )
 362           len = 48;
 363       }
 364 
 365       if ( len < 3 * 64 )
 366       {
 367         delta = ( len & 63 );
 368         len  &= -64;
 369 
 370         if ( delta < 10 )
 371           len += delta;
 372 
 373         else if ( delta < 32 )
 374           len += 10;
 375 
 376         else if ( delta < 54 )
 377           len += 54;
 378 
 379         else
 380           len += delta;
 381       }
 382       else
 383         len = FT_PIX_ROUND( len );
 384     }
 385 
 386     if ( do_snapping )
 387       len = FT_PIX_ROUND( len );
 388 
 389     return  len;
 390   }
 391 #endif /* 0 */
 392 
 393 
 394 #ifdef DEBUG_HINTER
 395 
 396   static void
 397   ps_simple_scale( PSH_Hint_Table  table,
 398                    FT_Fixed        scale,
 399                    FT_Fixed        delta,
 400                    FT_Int          dimension )
 401   {
 402     FT_UInt  count;
 403 
 404 
 405     for ( count = 0; count < table->max_hints; count++ )
 406     {
 407       PSH_Hint  hint = table->hints + count;
 408 
 409 
 410       hint->cur_pos = FT_MulFix( hint->org_pos, scale ) + delta;
 411       hint->cur_len = FT_MulFix( hint->org_len, scale );
 412 
 413       if ( ps_debug_hint_func )
 414         ps_debug_hint_func( hint, dimension );
 415     }
 416   }
 417 
 418 #endif /* DEBUG_HINTER */
 419 
 420 
 421   static FT_Fixed
 422   psh_hint_snap_stem_side_delta( FT_Fixed  pos,
 423                                  FT_Fixed  len )
 424   {
 425     FT_Fixed  delta1 = FT_PIX_ROUND( pos ) - pos;
 426     FT_Fixed  delta2 = FT_PIX_ROUND( pos + len ) - pos - len;
 427 
 428 
 429     if ( FT_ABS( delta1 ) <= FT_ABS( delta2 ) )
 430       return delta1;
 431     else
 432       return delta2;
 433   }
 434 
 435 
 436   static void
 437   psh_hint_align( PSH_Hint     hint,
 438                   PSH_Globals  globals,
 439                   FT_Int       dimension,
 440                   PSH_Glyph    glyph )
 441   {
 442     PSH_Dimension  dim   = &globals->dimension[dimension];
 443     FT_Fixed       scale = dim->scale_mult;
 444     FT_Fixed       delta = dim->scale_delta;
 445 
 446 
 447     if ( !psh_hint_is_fitted( hint ) )
 448     {
 449       FT_Pos  pos = FT_MulFix( hint->org_pos, scale ) + delta;
 450       FT_Pos  len = FT_MulFix( hint->org_len, scale );
 451 
 452       FT_Int            do_snapping;
 453       FT_Pos            fit_len;
 454       PSH_AlignmentRec  align;
 455 
 456 
 457       /* ignore stem alignments when requested through the hint flags */
 458       if ( ( dimension == 0 && !glyph->do_horz_hints ) ||
 459            ( dimension == 1 && !glyph->do_vert_hints ) )
 460       {
 461         hint->cur_pos = pos;
 462         hint->cur_len = len;
 463 
 464         psh_hint_set_fitted( hint );
 465         return;
 466       }
 467 
 468       /* perform stem snapping when requested - this is necessary
 469        * for monochrome and LCD hinting modes only
 470        */
 471       do_snapping = ( dimension == 0 && glyph->do_horz_snapping ) ||
 472                     ( dimension == 1 && glyph->do_vert_snapping );
 473 
 474       hint->cur_len = fit_len = len;
 475 
 476       /* check blue zones for horizontal stems */
 477       align.align     = PSH_BLUE_ALIGN_NONE;
 478       align.align_bot = align.align_top = 0;
 479 
 480       if ( dimension == 1 )
 481         psh_blues_snap_stem( &globals->blues,
 482                              ADD_INT( hint->org_pos, hint->org_len ),
 483                              hint->org_pos,
 484                              &align );
 485 
 486       switch ( align.align )
 487       {
 488       case PSH_BLUE_ALIGN_TOP:
 489         /* the top of the stem is aligned against a blue zone */
 490         hint->cur_pos = align.align_top - fit_len;
 491         break;
 492 
 493       case PSH_BLUE_ALIGN_BOT:
 494         /* the bottom of the stem is aligned against a blue zone */
 495         hint->cur_pos = align.align_bot;
 496         break;
 497 
 498       case PSH_BLUE_ALIGN_TOP | PSH_BLUE_ALIGN_BOT:
 499         /* both edges of the stem are aligned against blue zones */
 500         hint->cur_pos = align.align_bot;
 501         hint->cur_len = align.align_top - align.align_bot;
 502         break;
 503 
 504       default:
 505         {
 506           PSH_Hint  parent = hint->parent;
 507 
 508 
 509           if ( parent )
 510           {
 511             FT_Pos  par_org_center, par_cur_center;
 512             FT_Pos  cur_org_center, cur_delta;
 513 
 514 
 515             /* ensure that parent is already fitted */
 516             if ( !psh_hint_is_fitted( parent ) )
 517               psh_hint_align( parent, globals, dimension, glyph );
 518 
 519             /* keep original relation between hints, this is, use the */
 520             /* scaled distance between the centers of the hints to    */
 521             /* compute the new position                               */
 522             par_org_center = parent->org_pos + ( parent->org_len >> 1 );
 523             par_cur_center = parent->cur_pos + ( parent->cur_len >> 1 );
 524             cur_org_center = hint->org_pos   + ( hint->org_len   >> 1 );
 525 
 526             cur_delta = FT_MulFix( cur_org_center - par_org_center, scale );
 527             pos       = par_cur_center + cur_delta - ( len >> 1 );
 528           }
 529 
 530           hint->cur_pos = pos;
 531           hint->cur_len = fit_len;
 532 
 533           /* Stem adjustment tries to snap stem widths to standard
 534            * ones.  This is important to prevent unpleasant rounding
 535            * artefacts.
 536            */
 537           if ( glyph->do_stem_adjust )
 538           {
 539             if ( len <= 64 )
 540             {
 541               /* the stem is less than one pixel; we will center it
 542                * around the nearest pixel center
 543                */
 544               if ( len >= 32 )
 545               {
 546                 /* This is a special case where we also widen the stem
 547                  * and align it to the pixel grid.
 548                  *
 549                  *   stem_center          = pos + (len/2)
 550                  *   nearest_pixel_center = FT_ROUND(stem_center-32)+32
 551                  *   new_pos              = nearest_pixel_center-32
 552                  *                        = FT_ROUND(stem_center-32)
 553                  *                        = FT_FLOOR(stem_center-32+32)
 554                  *                        = FT_FLOOR(stem_center)
 555                  *   new_len              = 64
 556                  */
 557                 pos = FT_PIX_FLOOR( pos + ( len >> 1 ) );
 558                 len = 64;
 559               }
 560               else if ( len > 0 )
 561               {
 562                 /* This is a very small stem; we simply align it to the
 563                  * pixel grid, trying to find the minimum displacement.
 564                  *
 565                  * left               = pos
 566                  * right              = pos + len
 567                  * left_nearest_edge  = ROUND(pos)
 568                  * right_nearest_edge = ROUND(right)
 569                  *
 570                  * if ( ABS(left_nearest_edge - left) <=
 571                  *      ABS(right_nearest_edge - right) )
 572                  *    new_pos = left
 573                  * else
 574                  *    new_pos = right
 575                  */
 576                 FT_Pos  left_nearest  = FT_PIX_ROUND( pos );
 577                 FT_Pos  right_nearest = FT_PIX_ROUND( pos + len );
 578                 FT_Pos  left_disp     = left_nearest - pos;
 579                 FT_Pos  right_disp    = right_nearest - ( pos + len );
 580 
 581 
 582                 if ( left_disp < 0 )
 583                   left_disp = -left_disp;
 584                 if ( right_disp < 0 )
 585                   right_disp = -right_disp;
 586                 if ( left_disp <= right_disp )
 587                   pos = left_nearest;
 588                 else
 589                   pos = right_nearest;
 590               }
 591               else
 592               {
 593                 /* this is a ghost stem; we simply round it */
 594                 pos = FT_PIX_ROUND( pos );
 595               }
 596             }
 597             else
 598             {
 599               len = psh_dimension_quantize_len( dim, len, 0 );
 600             }
 601           }
 602 
 603           /* now that we have a good hinted stem width, try to position */
 604           /* the stem along a pixel grid integer coordinate             */
 605           hint->cur_pos = pos + psh_hint_snap_stem_side_delta( pos, len );
 606           hint->cur_len = len;
 607         }
 608       }
 609 
 610       if ( do_snapping )
 611       {
 612         pos = hint->cur_pos;
 613         len = hint->cur_len;
 614 
 615         if ( len < 64 )
 616           len = 64;
 617         else
 618           len = FT_PIX_ROUND( len );
 619 
 620         switch ( align.align )
 621         {
 622           case PSH_BLUE_ALIGN_TOP:
 623             hint->cur_pos = align.align_top - len;
 624             hint->cur_len = len;
 625             break;
 626 
 627           case PSH_BLUE_ALIGN_BOT:
 628             hint->cur_len = len;
 629             break;
 630 
 631           case PSH_BLUE_ALIGN_BOT | PSH_BLUE_ALIGN_TOP:
 632             /* don't touch */
 633             break;
 634 
 635 
 636           default:
 637             hint->cur_len = len;
 638             if ( len & 64 )
 639               pos = FT_PIX_FLOOR( pos + ( len >> 1 ) ) + 32;
 640             else
 641               pos = FT_PIX_ROUND( pos + ( len >> 1 ) );
 642 
 643             hint->cur_pos = pos - ( len >> 1 );
 644             hint->cur_len = len;
 645         }
 646       }
 647 
 648       psh_hint_set_fitted( hint );
 649 
 650 #ifdef DEBUG_HINTER
 651       if ( ps_debug_hint_func )
 652         ps_debug_hint_func( hint, dimension );
 653 #endif
 654     }
 655   }
 656 
 657 
 658 #if 0  /* not used for now, experimental */
 659 
 660  /*
 661   * A variant to perform "light" hinting (i.e. FT_RENDER_MODE_LIGHT)
 662   * of stems
 663   */
 664   static void
 665   psh_hint_align_light( PSH_Hint     hint,
 666                         PSH_Globals  globals,
 667                         FT_Int       dimension,
 668                         PSH_Glyph    glyph )
 669   {
 670     PSH_Dimension  dim   = &globals->dimension[dimension];
 671     FT_Fixed       scale = dim->scale_mult;
 672     FT_Fixed       delta = dim->scale_delta;
 673 
 674 
 675     if ( !psh_hint_is_fitted( hint ) )
 676     {
 677       FT_Pos  pos = FT_MulFix( hint->org_pos, scale ) + delta;
 678       FT_Pos  len = FT_MulFix( hint->org_len, scale );
 679 
 680       FT_Pos  fit_len;
 681 
 682       PSH_AlignmentRec  align;
 683 
 684 
 685       /* ignore stem alignments when requested through the hint flags */
 686       if ( ( dimension == 0 && !glyph->do_horz_hints ) ||
 687            ( dimension == 1 && !glyph->do_vert_hints ) )
 688       {
 689         hint->cur_pos = pos;
 690         hint->cur_len = len;
 691 
 692         psh_hint_set_fitted( hint );
 693         return;
 694       }
 695 
 696       fit_len = len;
 697 
 698       hint->cur_len = fit_len;
 699 
 700       /* check blue zones for horizontal stems */
 701       align.align = PSH_BLUE_ALIGN_NONE;
 702       align.align_bot = align.align_top = 0;
 703 
 704       if ( dimension == 1 )
 705         psh_blues_snap_stem( &globals->blues,
 706                              ADD_INT( hint->org_pos, hint->org_len ),
 707                              hint->org_pos,
 708                              &align );
 709 
 710       switch ( align.align )
 711       {
 712       case PSH_BLUE_ALIGN_TOP:
 713         /* the top of the stem is aligned against a blue zone */
 714         hint->cur_pos = align.align_top - fit_len;
 715         break;
 716 
 717       case PSH_BLUE_ALIGN_BOT:
 718         /* the bottom of the stem is aligned against a blue zone */
 719         hint->cur_pos = align.align_bot;
 720         break;
 721 
 722       case PSH_BLUE_ALIGN_TOP | PSH_BLUE_ALIGN_BOT:
 723         /* both edges of the stem are aligned against blue zones */
 724         hint->cur_pos = align.align_bot;
 725         hint->cur_len = align.align_top - align.align_bot;
 726         break;
 727 
 728       default:
 729         {
 730           PSH_Hint  parent = hint->parent;
 731 
 732 
 733           if ( parent )
 734           {
 735             FT_Pos  par_org_center, par_cur_center;
 736             FT_Pos  cur_org_center, cur_delta;
 737 
 738 
 739             /* ensure that parent is already fitted */
 740             if ( !psh_hint_is_fitted( parent ) )
 741               psh_hint_align_light( parent, globals, dimension, glyph );
 742 
 743             par_org_center = parent->org_pos + ( parent->org_len / 2 );
 744             par_cur_center = parent->cur_pos + ( parent->cur_len / 2 );
 745             cur_org_center = hint->org_pos   + ( hint->org_len   / 2 );
 746 
 747             cur_delta = FT_MulFix( cur_org_center - par_org_center, scale );
 748             pos       = par_cur_center + cur_delta - ( len >> 1 );
 749           }
 750 
 751           /* Stems less than one pixel wide are easy -- we want to
 752            * make them as dark as possible, so they must fall within
 753            * one pixel.  If the stem is split between two pixels
 754            * then snap the edge that is nearer to the pixel boundary
 755            * to the pixel boundary.
 756            */
 757           if ( len <= 64 )
 758           {
 759             if ( ( pos + len + 63 ) / 64  != pos / 64 + 1 )
 760               pos += psh_hint_snap_stem_side_delta ( pos, len );
 761           }
 762 
 763           /* Position stems other to minimize the amount of mid-grays.
 764            * There are, in general, two positions that do this,
 765            * illustrated as A) and B) below.
 766            *
 767            *   +                   +                   +                   +
 768            *
 769            * A)             |--------------------------------|
 770            * B)   |--------------------------------|
 771            * C)       |--------------------------------|
 772            *
 773            * Position A) (split the excess stem equally) should be better
 774            * for stems of width N + f where f < 0.5.
 775            *
 776            * Position B) (split the deficiency equally) should be better
 777            * for stems of width N + f where f > 0.5.
 778            *
 779            * It turns out though that minimizing the total number of lit
 780            * pixels is also important, so position C), with one edge
 781            * aligned with a pixel boundary is actually preferable
 782            * to A).  There are also more possible positions for C) than
 783            * for A) or B), so it involves less distortion of the overall
 784            * character shape.
 785            */
 786           else /* len > 64 */
 787           {
 788             FT_Fixed  frac_len = len & 63;
 789             FT_Fixed  center = pos + ( len >> 1 );
 790             FT_Fixed  delta_a, delta_b;
 791 
 792 
 793             if ( ( len / 64 ) & 1 )
 794             {
 795               delta_a = FT_PIX_FLOOR( center ) + 32 - center;
 796               delta_b = FT_PIX_ROUND( center ) - center;
 797             }
 798             else
 799             {
 800               delta_a = FT_PIX_ROUND( center ) - center;
 801               delta_b = FT_PIX_FLOOR( center ) + 32 - center;
 802             }
 803 
 804             /* We choose between B) and C) above based on the amount
 805              * of fractional stem width; for small amounts, choose
 806              * C) always, for large amounts, B) always, and inbetween,
 807              * pick whichever one involves less stem movement.
 808              */
 809             if ( frac_len < 32 )
 810             {
 811               pos += psh_hint_snap_stem_side_delta ( pos, len );
 812             }
 813             else if ( frac_len < 48 )
 814             {
 815               FT_Fixed  side_delta = psh_hint_snap_stem_side_delta ( pos,
 816                                                                      len );
 817 
 818               if ( FT_ABS( side_delta ) < FT_ABS( delta_b ) )
 819                 pos += side_delta;
 820               else
 821                 pos += delta_b;
 822             }
 823             else
 824             {
 825               pos += delta_b;
 826             }
 827           }
 828 
 829           hint->cur_pos = pos;
 830         }
 831       }  /* switch */
 832 
 833       psh_hint_set_fitted( hint );
 834 
 835 #ifdef DEBUG_HINTER
 836       if ( ps_debug_hint_func )
 837         ps_debug_hint_func( hint, dimension );
 838 #endif
 839     }
 840   }
 841 
 842 #endif /* 0 */
 843 
 844 
 845   static void
 846   psh_hint_table_align_hints( PSH_Hint_Table  table,
 847                               PSH_Globals     globals,
 848                               FT_Int          dimension,
 849                               PSH_Glyph       glyph )
 850   {
 851     PSH_Hint       hint;
 852     FT_UInt        count;
 853 
 854 #ifdef DEBUG_HINTER
 855 
 856     PSH_Dimension  dim   = &globals->dimension[dimension];
 857     FT_Fixed       scale = dim->scale_mult;
 858     FT_Fixed       delta = dim->scale_delta;
 859 
 860 
 861     if ( ps_debug_no_vert_hints && dimension == 0 )
 862     {
 863       ps_simple_scale( table, scale, delta, dimension );
 864       return;
 865     }
 866 
 867     if ( ps_debug_no_horz_hints && dimension == 1 )
 868     {
 869       ps_simple_scale( table, scale, delta, dimension );
 870       return;
 871     }
 872 
 873 #endif /* DEBUG_HINTER*/
 874 
 875     hint  = table->hints;
 876     count = table->max_hints;
 877 
 878     for ( ; count > 0; count--, hint++ )
 879       psh_hint_align( hint, globals, dimension, glyph );
 880   }
 881 
 882 
 883   /*************************************************************************/
 884   /*************************************************************************/
 885   /*****                                                               *****/
 886   /*****                POINTS INTERPOLATION ROUTINES                  *****/
 887   /*****                                                               *****/
 888   /*************************************************************************/
 889   /*************************************************************************/
 890 
 891 #define xxDEBUG_ZONES
 892 
 893 
 894 #ifdef DEBUG_ZONES
 895 
 896 #include FT_CONFIG_STANDARD_LIBRARY_H
 897 
 898   static void
 899   psh_print_zone( PSH_Zone  zone )
 900   {
 901     printf( "zone [scale,delta,min,max] = [%.5f,%.2f,%d,%d]\n",
 902              zone->scale / 65536.0,
 903              zone->delta / 64.0,
 904              zone->min,
 905              zone->max );
 906   }
 907 
 908 #endif /* DEBUG_ZONES */
 909 
 910 
 911   /*************************************************************************/
 912   /*************************************************************************/
 913   /*****                                                               *****/
 914   /*****                    HINTER GLYPH MANAGEMENT                    *****/
 915   /*****                                                               *****/
 916   /*************************************************************************/
 917   /*************************************************************************/
 918 
 919 #define  psh_corner_is_flat      ft_corner_is_flat
 920 #define  psh_corner_orientation  ft_corner_orientation
 921 
 922 
 923 #ifdef COMPUTE_INFLEXS
 924 
 925   /* compute all inflex points in a given glyph */
 926   static void
 927   psh_glyph_compute_inflections( PSH_Glyph  glyph )
 928   {
 929     FT_UInt  n;
 930 
 931 
 932     for ( n = 0; n < glyph->num_contours; n++ )
 933     {
 934       PSH_Point  first, start, end, before, after;
 935       FT_Pos     in_x, in_y, out_x, out_y;
 936       FT_Int     orient_prev, orient_cur;
 937       FT_Int     finished = 0;
 938 
 939 
 940       /* we need at least 4 points to create an inflection point */
 941       if ( glyph->contours[n].count < 4 )
 942         continue;
 943 
 944       /* compute first segment in contour */
 945       first = glyph->contours[n].start;
 946 
 947       start = end = first;
 948       do
 949       {
 950         end = end->next;
 951         if ( end == first )
 952           goto Skip;
 953 
 954         in_x = end->org_u - start->org_u;
 955         in_y = end->org_v - start->org_v;
 956 
 957       } while ( in_x == 0 && in_y == 0 );
 958 
 959       /* extend the segment start whenever possible */
 960       before = start;
 961       do
 962       {
 963         do
 964         {
 965           start  = before;
 966           before = before->prev;
 967           if ( before == first )
 968             goto Skip;
 969 
 970           out_x = start->org_u - before->org_u;
 971           out_y = start->org_v - before->org_v;
 972 
 973         } while ( out_x == 0 && out_y == 0 );
 974 
 975         orient_prev = psh_corner_orientation( in_x, in_y, out_x, out_y );
 976 
 977       } while ( orient_prev == 0 );
 978 
 979       first = start;
 980       in_x  = out_x;
 981       in_y  = out_y;
 982 
 983       /* now, process all segments in the contour */
 984       do
 985       {
 986         /* first, extend current segment's end whenever possible */
 987         after = end;
 988         do
 989         {
 990           do
 991           {
 992             end   = after;
 993             after = after->next;
 994             if ( after == first )
 995               finished = 1;
 996 
 997             out_x = after->org_u - end->org_u;
 998             out_y = after->org_v - end->org_v;
 999 
1000           } while ( out_x == 0 && out_y == 0 );
1001 
1002           orient_cur = psh_corner_orientation( in_x, in_y, out_x, out_y );
1003 
1004         } while ( orient_cur == 0 );
1005 
1006         if ( ( orient_cur ^ orient_prev ) < 0 )
1007         {
1008           do
1009           {
1010             psh_point_set_inflex( start );
1011             start = start->next;
1012           }
1013           while ( start != end );
1014 
1015           psh_point_set_inflex( start );
1016         }
1017 
1018         start       = end;
1019         end         = after;
1020         orient_prev = orient_cur;
1021         in_x        = out_x;
1022         in_y        = out_y;
1023 
1024       } while ( !finished );
1025 
1026     Skip:
1027       ;
1028     }
1029   }
1030 
1031 #endif /* COMPUTE_INFLEXS */
1032 
1033 
1034   static void
1035   psh_glyph_done( PSH_Glyph  glyph )
1036   {
1037     FT_Memory  memory = glyph->memory;
1038 
1039 
1040     psh_hint_table_done( &glyph->hint_tables[1], memory );
1041     psh_hint_table_done( &glyph->hint_tables[0], memory );
1042 
1043     FT_FREE( glyph->points );
1044     FT_FREE( glyph->contours );
1045 
1046     glyph->num_points   = 0;
1047     glyph->num_contours = 0;
1048 
1049     glyph->memory = NULL;
1050   }
1051 
1052 
1053   static int
1054   psh_compute_dir( FT_Pos  dx,
1055                    FT_Pos  dy )
1056   {
1057     FT_Pos  ax, ay;
1058     int     result = PSH_DIR_NONE;
1059 
1060 
1061     ax = FT_ABS( dx );
1062     ay = FT_ABS( dy );
1063 
1064     if ( ay * 12 < ax )
1065     {
1066       /* |dy| <<< |dx|  means a near-horizontal segment */
1067       result = ( dx >= 0 ) ? PSH_DIR_RIGHT : PSH_DIR_LEFT;
1068     }
1069     else if ( ax * 12 < ay )
1070     {
1071       /* |dx| <<< |dy|  means a near-vertical segment */
1072       result = ( dy >= 0 ) ? PSH_DIR_UP : PSH_DIR_DOWN;
1073     }
1074 
1075     return result;
1076   }
1077 
1078 
1079   /* load outline point coordinates into hinter glyph */
1080   static void
1081   psh_glyph_load_points( PSH_Glyph  glyph,
1082                          FT_Int     dimension )
1083   {
1084     FT_Vector*  vec   = glyph->outline->points;
1085     PSH_Point   point = glyph->points;
1086     FT_UInt     count = glyph->num_points;
1087 
1088 
1089     for ( ; count > 0; count--, point++, vec++ )
1090     {
1091       point->flags2 = 0;
1092       point->hint   = NULL;
1093       if ( dimension == 0 )
1094       {
1095         point->org_u = vec->x;
1096         point->org_v = vec->y;
1097       }
1098       else
1099       {
1100         point->org_u = vec->y;
1101         point->org_v = vec->x;
1102       }
1103 
1104 #ifdef DEBUG_HINTER
1105       point->org_x = vec->x;
1106       point->org_y = vec->y;
1107 #endif
1108 
1109     }
1110   }
1111 
1112 
1113   /* save hinted point coordinates back to outline */
1114   static void
1115   psh_glyph_save_points( PSH_Glyph  glyph,
1116                          FT_Int     dimension )
1117   {
1118     FT_UInt     n;
1119     PSH_Point   point = glyph->points;
1120     FT_Vector*  vec   = glyph->outline->points;
1121     char*       tags  = glyph->outline->tags;
1122 
1123 
1124     for ( n = 0; n < glyph->num_points; n++ )
1125     {
1126       if ( dimension == 0 )
1127         vec[n].x = point->cur_u;
1128       else
1129         vec[n].y = point->cur_u;
1130 
1131       if ( psh_point_is_strong( point ) )
1132         tags[n] |= (char)( ( dimension == 0 ) ? 32 : 64 );
1133 
1134 #ifdef DEBUG_HINTER
1135 
1136       if ( dimension == 0 )
1137       {
1138         point->cur_x   = point->cur_u;
1139         point->flags_x = point->flags2 | point->flags;
1140       }
1141       else
1142       {
1143         point->cur_y   = point->cur_u;
1144         point->flags_y = point->flags2 | point->flags;
1145       }
1146 
1147 #endif
1148 
1149       point++;
1150     }
1151   }
1152 
1153 
1154   static FT_Error
1155   psh_glyph_init( PSH_Glyph    glyph,
1156                   FT_Outline*  outline,
1157                   PS_Hints     ps_hints,
1158                   PSH_Globals  globals )
1159   {
1160     FT_Error   error;
1161     FT_Memory  memory;
1162 
1163 
1164     /* clear all fields */
1165     FT_ZERO( glyph );
1166 
1167     memory = glyph->memory = globals->memory;
1168 
1169     /* allocate and setup points + contours arrays */
1170     if ( FT_NEW_ARRAY( glyph->points,   outline->n_points   ) ||
1171          FT_NEW_ARRAY( glyph->contours, outline->n_contours ) )
1172       goto Exit;
1173 
1174     glyph->num_points   = (FT_UInt)outline->n_points;
1175     glyph->num_contours = (FT_UInt)outline->n_contours;
1176 
1177     {
1178       FT_UInt      first = 0, next, n;
1179       PSH_Point    points  = glyph->points;
1180       PSH_Contour  contour = glyph->contours;
1181 
1182 
1183       for ( n = 0; n < glyph->num_contours; n++ )
1184       {
1185         FT_UInt    count;
1186         PSH_Point  point;
1187 
1188 
1189         next  = (FT_UInt)outline->contours[n] + 1;
1190         count = next - first;
1191 
1192         contour->start = points + first;
1193         contour->count = count;
1194 
1195         if ( count > 0 )
1196         {
1197           point = points + first;
1198 
1199           point->prev    = points + next - 1;
1200           point->contour = contour;
1201 
1202           for ( ; count > 1; count-- )
1203           {
1204             point[0].next = point + 1;
1205             point[1].prev = point;
1206             point++;
1207             point->contour = contour;
1208           }
1209           point->next = points + first;
1210         }
1211 
1212         contour++;
1213         first = next;
1214       }
1215     }
1216 
1217     {
1218       PSH_Point   points = glyph->points;
1219       PSH_Point   point  = points;
1220       FT_Vector*  vec    = outline->points;
1221       FT_UInt     n;
1222 
1223 
1224       for ( n = 0; n < glyph->num_points; n++, point++ )
1225       {
1226         FT_Int  n_prev = (FT_Int)( point->prev - points );
1227         FT_Int  n_next = (FT_Int)( point->next - points );
1228         FT_Pos  dxi, dyi, dxo, dyo;
1229 
1230 
1231         if ( !( outline->tags[n] & FT_CURVE_TAG_ON ) )
1232           point->flags = PSH_POINT_OFF;
1233 
1234         dxi = vec[n].x - vec[n_prev].x;
1235         dyi = vec[n].y - vec[n_prev].y;
1236 
1237         point->dir_in = (FT_Char)psh_compute_dir( dxi, dyi );
1238 
1239         dxo = vec[n_next].x - vec[n].x;
1240         dyo = vec[n_next].y - vec[n].y;
1241 
1242         point->dir_out = (FT_Char)psh_compute_dir( dxo, dyo );
1243 
1244         /* detect smooth points */
1245         if ( point->flags & PSH_POINT_OFF )
1246           point->flags |= PSH_POINT_SMOOTH;
1247 
1248         else if ( point->dir_in == point->dir_out )
1249         {
1250           if ( point->dir_out != PSH_DIR_NONE           ||
1251                psh_corner_is_flat( dxi, dyi, dxo, dyo ) )
1252             point->flags |= PSH_POINT_SMOOTH;
1253         }
1254       }
1255     }
1256 
1257     glyph->outline = outline;
1258     glyph->globals = globals;
1259 
1260 #ifdef COMPUTE_INFLEXS
1261     psh_glyph_load_points( glyph, 0 );
1262     psh_glyph_compute_inflections( glyph );
1263 #endif /* COMPUTE_INFLEXS */
1264 
1265     /* now deal with hints tables */
1266     error = psh_hint_table_init( &glyph->hint_tables [0],
1267                                  &ps_hints->dimension[0].hints,
1268                                  &ps_hints->dimension[0].masks,
1269                                  &ps_hints->dimension[0].counters,
1270                                  memory );
1271     if ( error )
1272       goto Exit;
1273 
1274     error = psh_hint_table_init( &glyph->hint_tables [1],
1275                                  &ps_hints->dimension[1].hints,
1276                                  &ps_hints->dimension[1].masks,
1277                                  &ps_hints->dimension[1].counters,
1278                                  memory );
1279     if ( error )
1280       goto Exit;
1281 
1282   Exit:
1283     return error;
1284   }
1285 
1286 
1287   /* compute all extrema in a glyph for a given dimension */
1288   static void
1289   psh_glyph_compute_extrema( PSH_Glyph  glyph )
1290   {
1291     FT_UInt  n;
1292 
1293 
1294     /* first of all, compute all local extrema */
1295     for ( n = 0; n < glyph->num_contours; n++ )
1296     {
1297       PSH_Point  first = glyph->contours[n].start;
1298       PSH_Point  point, before, after;
1299 
1300 
1301       if ( glyph->contours[n].count == 0 )
1302         continue;
1303 
1304       point  = first;
1305       before = point;
1306 
1307       do
1308       {
1309         before = before->prev;
1310         if ( before == first )
1311           goto Skip;
1312 
1313       } while ( before->org_u == point->org_u );
1314 
1315       first = point = before->next;
1316 
1317       for (;;)
1318       {
1319         after = point;
1320         do
1321         {
1322           after = after->next;
1323           if ( after == first )
1324             goto Next;
1325 
1326         } while ( after->org_u == point->org_u );
1327 
1328         if ( before->org_u < point->org_u )
1329         {
1330           if ( after->org_u < point->org_u )
1331           {
1332             /* local maximum */
1333             goto Extremum;
1334           }
1335         }
1336         else /* before->org_u > point->org_u */
1337         {
1338           if ( after->org_u > point->org_u )
1339           {
1340             /* local minimum */
1341           Extremum:
1342             do
1343             {
1344               psh_point_set_extremum( point );
1345               point = point->next;
1346 
1347             } while ( point != after );
1348           }
1349         }
1350 
1351         before = after->prev;
1352         point  = after;
1353 
1354       } /* for  */
1355 
1356     Next:
1357       ;
1358     }
1359 
1360     /* for each extremum, determine its direction along the */
1361     /* orthogonal axis                                      */
1362     for ( n = 0; n < glyph->num_points; n++ )
1363     {
1364       PSH_Point  point, before, after;
1365 
1366 
1367       point  = &glyph->points[n];
1368       before = point;
1369       after  = point;
1370 
1371       if ( psh_point_is_extremum( point ) )
1372       {
1373         do
1374         {
1375           before = before->prev;
1376           if ( before == point )
1377             goto Skip;
1378 
1379         } while ( before->org_v == point->org_v );
1380 
1381         do
1382         {
1383           after = after->next;
1384           if ( after == point )
1385             goto Skip;
1386 
1387         } while ( after->org_v == point->org_v );
1388       }
1389 
1390       if ( before->org_v < point->org_v &&
1391            after->org_v  > point->org_v )
1392       {
1393         psh_point_set_positive( point );
1394       }
1395       else if ( before->org_v > point->org_v &&
1396                 after->org_v  < point->org_v )
1397       {
1398         psh_point_set_negative( point );
1399       }
1400 
1401     Skip:
1402       ;
1403     }
1404   }
1405 
1406 
1407   /* major_dir is the direction for points on the bottom/left of the stem; */
1408   /* Points on the top/right of the stem will have a direction of          */
1409   /* -major_dir.                                                           */
1410 
1411   static void
1412   psh_hint_table_find_strong_points( PSH_Hint_Table  table,
1413                                      PSH_Point       point,
1414                                      FT_UInt         count,
1415                                      FT_Int          threshold,
1416                                      FT_Int          major_dir )
1417   {
1418     PSH_Hint*  sort      = table->sort;
1419     FT_UInt    num_hints = table->num_hints;
1420 
1421 
1422     for ( ; count > 0; count--, point++ )
1423     {
1424       FT_Int  point_dir = 0;
1425       FT_Pos  org_u     = point->org_u;
1426 
1427 
1428       if ( psh_point_is_strong( point ) )
1429         continue;
1430 
1431       if ( PSH_DIR_COMPARE( point->dir_in, major_dir ) )
1432         point_dir = point->dir_in;
1433 
1434       else if ( PSH_DIR_COMPARE( point->dir_out, major_dir ) )
1435         point_dir = point->dir_out;
1436 
1437       if ( point_dir )
1438       {
1439         if ( point_dir == major_dir )
1440         {
1441           FT_UInt  nn;
1442 
1443 
1444           for ( nn = 0; nn < num_hints; nn++ )
1445           {
1446             PSH_Hint  hint = sort[nn];
1447             FT_Pos    d    = org_u - hint->org_pos;
1448 
1449 
1450             if ( d < threshold && -d < threshold )
1451             {
1452               psh_point_set_strong( point );
1453               point->flags2 |= PSH_POINT_EDGE_MIN;
1454               point->hint    = hint;
1455               break;
1456             }
1457           }
1458         }
1459         else if ( point_dir == -major_dir )
1460         {
1461           FT_UInt  nn;
1462 
1463 
1464           for ( nn = 0; nn < num_hints; nn++ )
1465           {
1466             PSH_Hint  hint = sort[nn];
1467             FT_Pos    d    = org_u - hint->org_pos - hint->org_len;
1468 
1469 
1470             if ( d < threshold && -d < threshold )
1471             {
1472               psh_point_set_strong( point );
1473               point->flags2 |= PSH_POINT_EDGE_MAX;
1474               point->hint    = hint;
1475               break;
1476             }
1477           }
1478         }
1479       }
1480 
1481 #if 1
1482       else if ( psh_point_is_extremum( point ) )
1483       {
1484         /* treat extrema as special cases for stem edge alignment */
1485         FT_UInt  nn, min_flag, max_flag;
1486 
1487 
1488         if ( major_dir == PSH_DIR_HORIZONTAL )
1489         {
1490           min_flag = PSH_POINT_POSITIVE;
1491           max_flag = PSH_POINT_NEGATIVE;
1492         }
1493         else
1494         {
1495           min_flag = PSH_POINT_NEGATIVE;
1496           max_flag = PSH_POINT_POSITIVE;
1497         }
1498 
1499         if ( point->flags2 & min_flag )
1500         {
1501           for ( nn = 0; nn < num_hints; nn++ )
1502           {
1503             PSH_Hint  hint = sort[nn];
1504             FT_Pos    d    = org_u - hint->org_pos;
1505 
1506 
1507             if ( d < threshold && -d < threshold )
1508             {
1509               point->flags2 |= PSH_POINT_EDGE_MIN;
1510               point->hint    = hint;
1511               psh_point_set_strong( point );
1512               break;
1513             }
1514           }
1515         }
1516         else if ( point->flags2 & max_flag )
1517         {
1518           for ( nn = 0; nn < num_hints; nn++ )
1519           {
1520             PSH_Hint  hint = sort[nn];
1521             FT_Pos    d    = org_u - hint->org_pos - hint->org_len;
1522 
1523 
1524             if ( d < threshold && -d < threshold )
1525             {
1526               point->flags2 |= PSH_POINT_EDGE_MAX;
1527               point->hint    = hint;
1528               psh_point_set_strong( point );
1529               break;
1530             }
1531           }
1532         }
1533 
1534         if ( !point->hint )
1535         {
1536           for ( nn = 0; nn < num_hints; nn++ )
1537           {
1538             PSH_Hint  hint = sort[nn];
1539 
1540 
1541             if ( org_u >=          hint->org_pos                  &&
1542                  org_u <= ADD_INT( hint->org_pos, hint->org_len ) )
1543             {
1544               point->hint = hint;
1545               break;
1546             }
1547           }
1548         }
1549       }
1550 
1551 #endif /* 1 */
1552     }
1553   }
1554 
1555 
1556   /* the accepted shift for strong points in fractional pixels */
1557 #define PSH_STRONG_THRESHOLD  32
1558 
1559   /* the maximum shift value in font units */
1560 #define PSH_STRONG_THRESHOLD_MAXIMUM  30
1561 
1562 
1563   /* find strong points in a glyph */
1564   static void
1565   psh_glyph_find_strong_points( PSH_Glyph  glyph,
1566                                 FT_Int     dimension )
1567   {
1568     /* a point is `strong' if it is located on a stem edge and       */
1569     /* has an `in' or `out' tangent parallel to the hint's direction */
1570 
1571     PSH_Hint_Table  table     = &glyph->hint_tables[dimension];
1572     PS_Mask         mask      = table->hint_masks->masks;
1573     FT_UInt         num_masks = table->hint_masks->num_masks;
1574     FT_UInt         first     = 0;
1575     FT_Int          major_dir = ( dimension == 0 ) ? PSH_DIR_VERTICAL
1576                                                    : PSH_DIR_HORIZONTAL;
1577     PSH_Dimension   dim       = &glyph->globals->dimension[dimension];
1578     FT_Fixed        scale     = dim->scale_mult;
1579     FT_Int          threshold;
1580 
1581 
1582     threshold = (FT_Int)FT_DivFix( PSH_STRONG_THRESHOLD, scale );
1583     if ( threshold > PSH_STRONG_THRESHOLD_MAXIMUM )
1584       threshold = PSH_STRONG_THRESHOLD_MAXIMUM;
1585 
1586     /* process secondary hints to `selected' points */
1587     if ( num_masks > 1 && glyph->num_points > 0 )
1588     {
1589       /* the `endchar' op can reduce the number of points */
1590       first = mask->end_point > glyph->num_points
1591                 ? glyph->num_points
1592                 : mask->end_point;
1593       mask++;
1594       for ( ; num_masks > 1; num_masks--, mask++ )
1595       {
1596         FT_UInt  next = FT_MIN( mask->end_point, glyph->num_points );
1597 
1598 
1599         if ( next > first )
1600         {
1601           FT_UInt    count = next - first;
1602           PSH_Point  point = glyph->points + first;
1603 
1604 
1605           psh_hint_table_activate_mask( table, mask );
1606 
1607           psh_hint_table_find_strong_points( table, point, count,
1608                                              threshold, major_dir );
1609         }
1610         first = next;
1611       }
1612     }
1613 
1614     /* process primary hints for all points */
1615     if ( num_masks == 1 )
1616     {
1617       FT_UInt    count = glyph->num_points;
1618       PSH_Point  point = glyph->points;
1619 
1620 
1621       psh_hint_table_activate_mask( table, table->hint_masks->masks );
1622 
1623       psh_hint_table_find_strong_points( table, point, count,
1624                                          threshold, major_dir );
1625     }
1626 
1627     /* now, certain points may have been attached to a hint and */
1628     /* not marked as strong; update their flags then            */
1629     {
1630       FT_UInt    count = glyph->num_points;
1631       PSH_Point  point = glyph->points;
1632 
1633 
1634       for ( ; count > 0; count--, point++ )
1635         if ( point->hint && !psh_point_is_strong( point ) )
1636           psh_point_set_strong( point );
1637     }
1638   }
1639 
1640 
1641   /* find points in a glyph which are in a blue zone and have `in' or */
1642   /* `out' tangents parallel to the horizontal axis                   */
1643   static void
1644   psh_glyph_find_blue_points( PSH_Blues  blues,
1645                               PSH_Glyph  glyph )
1646   {
1647     PSH_Blue_Table  table;
1648     PSH_Blue_Zone   zone;
1649     FT_UInt         glyph_count = glyph->num_points;
1650     FT_UInt         blue_count;
1651     PSH_Point       point = glyph->points;
1652 
1653 
1654     for ( ; glyph_count > 0; glyph_count--, point++ )
1655     {
1656       FT_Pos  y;
1657 
1658 
1659       /* check tangents */
1660       if ( !PSH_DIR_COMPARE( point->dir_in,  PSH_DIR_HORIZONTAL ) &&
1661            !PSH_DIR_COMPARE( point->dir_out, PSH_DIR_HORIZONTAL ) )
1662         continue;
1663 
1664       /* skip strong points */
1665       if ( psh_point_is_strong( point ) )
1666         continue;
1667 
1668       y = point->org_u;
1669 
1670       /* look up top zones */
1671       table      = &blues->normal_top;
1672       blue_count = table->count;
1673       zone       = table->zones;
1674 
1675       for ( ; blue_count > 0; blue_count--, zone++ )
1676       {
1677         FT_Pos  delta = y - zone->org_bottom;
1678 
1679 
1680         if ( delta < -blues->blue_fuzz )
1681           break;
1682 
1683         if ( y <= zone->org_top + blues->blue_fuzz )
1684           if ( blues->no_overshoots || delta <= blues->blue_threshold )
1685           {
1686             point->cur_u = zone->cur_bottom;
1687             psh_point_set_strong( point );
1688             psh_point_set_fitted( point );
1689           }
1690       }
1691 
1692       /* look up bottom zones */
1693       table      = &blues->normal_bottom;
1694       blue_count = table->count;
1695       zone       = table->zones + blue_count - 1;
1696 
1697       for ( ; blue_count > 0; blue_count--, zone-- )
1698       {
1699         FT_Pos  delta = zone->org_top - y;
1700 
1701 
1702         if ( delta < -blues->blue_fuzz )
1703           break;
1704 
1705         if ( y >= zone->org_bottom - blues->blue_fuzz )
1706           if ( blues->no_overshoots || delta < blues->blue_threshold )
1707           {
1708             point->cur_u = zone->cur_top;
1709             psh_point_set_strong( point );
1710             psh_point_set_fitted( point );
1711           }
1712       }
1713     }
1714   }
1715 
1716 
1717   /* interpolate strong points with the help of hinted coordinates */
1718   static void
1719   psh_glyph_interpolate_strong_points( PSH_Glyph  glyph,
1720                                        FT_Int     dimension )
1721   {
1722     PSH_Dimension  dim   = &glyph->globals->dimension[dimension];
1723     FT_Fixed       scale = dim->scale_mult;
1724 
1725     FT_UInt        count = glyph->num_points;
1726     PSH_Point      point = glyph->points;
1727 
1728 
1729     for ( ; count > 0; count--, point++ )
1730     {
1731       PSH_Hint  hint = point->hint;
1732 
1733 
1734       if ( hint )
1735       {
1736         FT_Pos  delta;
1737 
1738 
1739         if ( psh_point_is_edge_min( point ) )
1740           point->cur_u = hint->cur_pos;
1741 
1742         else if ( psh_point_is_edge_max( point ) )
1743           point->cur_u = hint->cur_pos + hint->cur_len;
1744 
1745         else
1746         {
1747           delta = point->org_u - hint->org_pos;
1748 
1749           if ( delta <= 0 )
1750             point->cur_u = hint->cur_pos + FT_MulFix( delta, scale );
1751 
1752           else if ( delta >= hint->org_len )
1753             point->cur_u = hint->cur_pos + hint->cur_len +
1754                              FT_MulFix( delta - hint->org_len, scale );
1755 
1756           else /* hint->org_len > 0 */
1757             point->cur_u = hint->cur_pos +
1758                              FT_MulDiv( delta, hint->cur_len,
1759                                         hint->org_len );
1760         }
1761         psh_point_set_fitted( point );
1762       }
1763     }
1764   }
1765 
1766 
1767 #define  PSH_MAX_STRONG_INTERNAL  16
1768 
1769   static void
1770   psh_glyph_interpolate_normal_points( PSH_Glyph  glyph,
1771                                        FT_Int     dimension )
1772   {
1773 
1774 #if 1
1775     /* first technique: a point is strong if it is a local extremum */
1776 
1777     PSH_Dimension  dim    = &glyph->globals->dimension[dimension];
1778     FT_Fixed       scale  = dim->scale_mult;
1779     FT_Memory      memory = glyph->memory;
1780 
1781     PSH_Point*     strongs     = NULL;
1782     PSH_Point      strongs_0[PSH_MAX_STRONG_INTERNAL];
1783     FT_UInt        num_strongs = 0;
1784 
1785     PSH_Point      points = glyph->points;
1786     PSH_Point      points_end = points + glyph->num_points;
1787     PSH_Point      point;
1788 
1789 
1790     /* first count the number of strong points */
1791     for ( point = points; point < points_end; point++ )
1792     {
1793       if ( psh_point_is_strong( point ) )
1794         num_strongs++;
1795     }
1796 
1797     if ( num_strongs == 0 )  /* nothing to do here */
1798       return;
1799 
1800     /* allocate an array to store a list of points, */
1801     /* stored in increasing org_u order             */
1802     if ( num_strongs <= PSH_MAX_STRONG_INTERNAL )
1803       strongs = strongs_0;
1804     else
1805     {
1806       FT_Error  error;
1807 
1808 
1809       if ( FT_NEW_ARRAY( strongs, num_strongs ) )
1810         return;
1811     }
1812 
1813     num_strongs = 0;
1814     for ( point = points; point < points_end; point++ )
1815     {
1816       PSH_Point*  insert;
1817 
1818 
1819       if ( !psh_point_is_strong( point ) )
1820         continue;
1821 
1822       for ( insert = strongs + num_strongs; insert > strongs; insert-- )
1823       {
1824         if ( insert[-1]->org_u <= point->org_u )
1825           break;
1826 
1827         insert[0] = insert[-1];
1828       }
1829       insert[0] = point;
1830       num_strongs++;
1831     }
1832 
1833     /* now try to interpolate all normal points */
1834     for ( point = points; point < points_end; point++ )
1835     {
1836       if ( psh_point_is_strong( point ) )
1837         continue;
1838 
1839       /* sometimes, some local extrema are smooth points */
1840       if ( psh_point_is_smooth( point ) )
1841       {
1842         if ( point->dir_in == PSH_DIR_NONE   ||
1843              point->dir_in != point->dir_out )
1844           continue;
1845 
1846         if ( !psh_point_is_extremum( point ) &&
1847              !psh_point_is_inflex( point )   )
1848           continue;
1849 
1850         point->flags &= ~PSH_POINT_SMOOTH;
1851       }
1852 
1853       /* find best enclosing point coordinates then interpolate */
1854       {
1855         PSH_Point   before, after;
1856         FT_UInt     nn;
1857 
1858 
1859         for ( nn = 0; nn < num_strongs; nn++ )
1860           if ( strongs[nn]->org_u > point->org_u )
1861             break;
1862 
1863         if ( nn == 0 )  /* point before the first strong point */
1864         {
1865           after = strongs[0];
1866 
1867           point->cur_u = after->cur_u +
1868                            FT_MulFix( point->org_u - after->org_u,
1869                                       scale );
1870         }
1871         else
1872         {
1873           before = strongs[nn - 1];
1874 
1875           for ( nn = num_strongs; nn > 0; nn-- )
1876             if ( strongs[nn - 1]->org_u < point->org_u )
1877               break;
1878 
1879           if ( nn == num_strongs )  /* point is after last strong point */
1880           {
1881             before = strongs[nn - 1];
1882 
1883             point->cur_u = before->cur_u +
1884                              FT_MulFix( point->org_u - before->org_u,
1885                                         scale );
1886           }
1887           else
1888           {
1889             FT_Pos  u;
1890 
1891 
1892             after = strongs[nn];
1893 
1894             /* now interpolate point between before and after */
1895             u = point->org_u;
1896 
1897             if ( u == before->org_u )
1898               point->cur_u = before->cur_u;
1899 
1900             else if ( u == after->org_u )
1901               point->cur_u = after->cur_u;
1902 
1903             else
1904               point->cur_u = before->cur_u +
1905                                FT_MulDiv( u - before->org_u,
1906                                           after->cur_u - before->cur_u,
1907                                           after->org_u - before->org_u );
1908           }
1909         }
1910         psh_point_set_fitted( point );
1911       }
1912     }
1913 
1914     if ( strongs != strongs_0 )
1915       FT_FREE( strongs );
1916 
1917 #endif /* 1 */
1918 
1919   }
1920 
1921 
1922   /* interpolate other points */
1923   static void
1924   psh_glyph_interpolate_other_points( PSH_Glyph  glyph,
1925                                       FT_Int     dimension )
1926   {
1927     PSH_Dimension  dim          = &glyph->globals->dimension[dimension];
1928     FT_Fixed       scale        = dim->scale_mult;
1929     FT_Fixed       delta        = dim->scale_delta;
1930     PSH_Contour    contour      = glyph->contours;
1931     FT_UInt        num_contours = glyph->num_contours;
1932 
1933 
1934     for ( ; num_contours > 0; num_contours--, contour++ )
1935     {
1936       PSH_Point  start = contour->start;
1937       PSH_Point  first, next, point;
1938       FT_UInt    fit_count;
1939 
1940 
1941       /* count the number of strong points in this contour */
1942       next      = start + contour->count;
1943       fit_count = 0;
1944       first     = NULL;
1945 
1946       for ( point = start; point < next; point++ )
1947         if ( psh_point_is_fitted( point ) )
1948         {
1949           if ( !first )
1950             first = point;
1951 
1952           fit_count++;
1953         }
1954 
1955       /* if there are less than 2 fitted points in the contour, we */
1956       /* simply scale and eventually translate the contour points  */
1957       if ( fit_count < 2 )
1958       {
1959         if ( fit_count == 1 )
1960           delta = first->cur_u - FT_MulFix( first->org_u, scale );
1961 
1962         for ( point = start; point < next; point++ )
1963           if ( point != first )
1964             point->cur_u = FT_MulFix( point->org_u, scale ) + delta;
1965 
1966         goto Next_Contour;
1967       }
1968 
1969       /* there are more than 2 strong points in this contour; we */
1970       /* need to interpolate weak points between them            */
1971       start = first;
1972       do
1973       {
1974         /* skip consecutive fitted points */
1975         for (;;)
1976         {
1977           next = first->next;
1978           if ( next == start )
1979             goto Next_Contour;
1980 
1981           if ( !psh_point_is_fitted( next ) )
1982             break;
1983 
1984           first = next;
1985         }
1986 
1987         /* find next fitted point after unfitted one */
1988         for (;;)
1989         {
1990           next = next->next;
1991           if ( psh_point_is_fitted( next ) )
1992             break;
1993         }
1994 
1995         /* now interpolate between them */
1996         {
1997           FT_Pos    org_a, org_ab, cur_a, cur_ab;
1998           FT_Pos    org_c, org_ac, cur_c;
1999           FT_Fixed  scale_ab;
2000 
2001 
2002           if ( first->org_u <= next->org_u )
2003           {
2004             org_a  = first->org_u;
2005             cur_a  = first->cur_u;
2006             org_ab = next->org_u - org_a;
2007             cur_ab = next->cur_u - cur_a;
2008           }
2009           else
2010           {
2011             org_a  = next->org_u;
2012             cur_a  = next->cur_u;
2013             org_ab = first->org_u - org_a;
2014             cur_ab = first->cur_u - cur_a;
2015           }
2016 
2017           scale_ab = 0x10000L;
2018           if ( org_ab > 0 )
2019             scale_ab = FT_DivFix( cur_ab, org_ab );
2020 
2021           point = first->next;
2022           do
2023           {
2024             org_c  = point->org_u;
2025             org_ac = org_c - org_a;
2026 
2027             if ( org_ac <= 0 )
2028             {
2029               /* on the left of the interpolation zone */
2030               cur_c = cur_a + FT_MulFix( org_ac, scale );
2031             }
2032             else if ( org_ac >= org_ab )
2033             {
2034               /* on the right on the interpolation zone */
2035               cur_c = cur_a + cur_ab + FT_MulFix( org_ac - org_ab, scale );
2036             }
2037             else
2038             {
2039               /* within the interpolation zone */
2040               cur_c = cur_a + FT_MulFix( org_ac, scale_ab );
2041             }
2042 
2043             point->cur_u = cur_c;
2044 
2045             point = point->next;
2046 
2047           } while ( point != next );
2048         }
2049 
2050         /* keep going until all points in the contours have been processed */
2051         first = next;
2052 
2053       } while ( first != start );
2054 
2055     Next_Contour:
2056       ;
2057     }
2058   }
2059 
2060 
2061   /*************************************************************************/
2062   /*************************************************************************/
2063   /*****                                                               *****/
2064   /*****                     HIGH-LEVEL INTERFACE                      *****/
2065   /*****                                                               *****/
2066   /*************************************************************************/
2067   /*************************************************************************/
2068 
2069   FT_Error
2070   ps_hints_apply( PS_Hints        ps_hints,
2071                   FT_Outline*     outline,
2072                   PSH_Globals     globals,
2073                   FT_Render_Mode  hint_mode )
2074   {
2075     PSH_GlyphRec  glyphrec;
2076     PSH_Glyph     glyph = &glyphrec;
2077     FT_Error      error;
2078 #ifdef DEBUG_HINTER
2079     FT_Memory     memory;
2080 #endif
2081     FT_Int        dimension;
2082 
2083 
2084     /* something to do? */
2085     if ( outline->n_points == 0 || outline->n_contours == 0 )
2086       return FT_Err_Ok;
2087 
2088 #ifdef DEBUG_HINTER
2089 
2090     memory = globals->memory;
2091 
2092     if ( ps_debug_glyph )
2093     {
2094       psh_glyph_done( ps_debug_glyph );
2095       FT_FREE( ps_debug_glyph );
2096     }
2097 
2098     if ( FT_NEW( glyph ) )
2099       return error;
2100 
2101     ps_debug_glyph = glyph;
2102 
2103 #endif /* DEBUG_HINTER */
2104 
2105     error = psh_glyph_init( glyph, outline, ps_hints, globals );
2106     if ( error )
2107       goto Exit;
2108 
2109     /* try to optimize the y_scale so that the top of non-capital letters
2110      * is aligned on a pixel boundary whenever possible
2111      */
2112     {
2113       PSH_Dimension  dim_x = &glyph->globals->dimension[0];
2114       PSH_Dimension  dim_y = &glyph->globals->dimension[1];
2115 
2116       FT_Fixed  x_scale = dim_x->scale_mult;
2117       FT_Fixed  y_scale = dim_y->scale_mult;
2118 
2119       FT_Fixed  old_x_scale = x_scale;
2120       FT_Fixed  old_y_scale = y_scale;
2121 
2122       FT_Fixed  scaled;
2123       FT_Fixed  fitted;
2124 
2125       FT_Bool  rescale = FALSE;
2126 
2127 
2128       scaled = FT_MulFix( globals->blues.normal_top.zones->org_ref, y_scale );
2129       fitted = FT_PIX_ROUND( scaled );
2130 
2131       if ( fitted != 0 && scaled != fitted )
2132       {
2133         rescale = TRUE;
2134 
2135         y_scale = FT_MulDiv( y_scale, fitted, scaled );
2136 
2137         if ( fitted < scaled )
2138           x_scale -= x_scale / 50;
2139 
2140         psh_globals_set_scale( glyph->globals, x_scale, y_scale, 0, 0 );
2141       }
2142 
2143       glyph->do_horz_hints = 1;
2144       glyph->do_vert_hints = 1;
2145 
2146       glyph->do_horz_snapping = FT_BOOL( hint_mode == FT_RENDER_MODE_MONO ||
2147                                          hint_mode == FT_RENDER_MODE_LCD  );
2148 
2149       glyph->do_vert_snapping = FT_BOOL( hint_mode == FT_RENDER_MODE_MONO  ||
2150                                          hint_mode == FT_RENDER_MODE_LCD_V );
2151 
2152       glyph->do_stem_adjust   = FT_BOOL( hint_mode != FT_RENDER_MODE_LIGHT );
2153 
2154       for ( dimension = 0; dimension < 2; dimension++ )
2155       {
2156         /* load outline coordinates into glyph */
2157         psh_glyph_load_points( glyph, dimension );
2158 
2159         /* compute local extrema */
2160         psh_glyph_compute_extrema( glyph );
2161 
2162         /* compute aligned stem/hints positions */
2163         psh_hint_table_align_hints( &glyph->hint_tables[dimension],
2164                                     glyph->globals,
2165                                     dimension,
2166                                     glyph );
2167 
2168         /* find strong points, align them, then interpolate others */
2169         psh_glyph_find_strong_points( glyph, dimension );
2170         if ( dimension == 1 )
2171           psh_glyph_find_blue_points( &globals->blues, glyph );
2172         psh_glyph_interpolate_strong_points( glyph, dimension );
2173         psh_glyph_interpolate_normal_points( glyph, dimension );
2174         psh_glyph_interpolate_other_points( glyph, dimension );
2175 
2176         /* save hinted coordinates back to outline */
2177         psh_glyph_save_points( glyph, dimension );
2178 
2179         if ( rescale )
2180           psh_globals_set_scale( glyph->globals,
2181                                  old_x_scale, old_y_scale, 0, 0 );
2182       }
2183     }
2184 
2185   Exit:
2186 
2187 #ifndef DEBUG_HINTER
2188     psh_glyph_done( glyph );
2189 #endif
2190 
2191     return error;
2192   }
2193 
2194 
2195 /* END */