QRScanner/mobile/jni/thirdparty/freetype/src/pshinter/pshalgo.c

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