lib/freetype/src/pshinter/pshalgo3.c

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