lib/freetype/src/pshinter/pshalgo2.c

   1 /***************************************************************************/
   2 /*                                                                         */
   3 /*  pshalgo2.c                                                             */
   4 /*                                                                         */
   5 /*    PostScript hinting algorithm 2 (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 "pshalgo2.h"
  23
  24 #undef  FT_COMPONENT
  25 #define FT_COMPONENT  trace_pshalgo2
  26
  27 #ifdef DEBUG_HINTER
  28   PSH2_Hint_Table  ps2_debug_hint_table = 0;
  29   PSH2_HintFunc    ps2_debug_hint_func  = 0;
  30   PSH2_Glyph       ps2_debug_glyph      = 0;
  31 #endif
  32
  33
  34   /*************************************************************************/
  35   /*************************************************************************/
  36   /*****                                                               *****/
  37   /*****                  BASIC HINTS RECORDINGS                       *****/
  38   /*****                                                               *****/
  39   /*************************************************************************/
  40   /*************************************************************************/
  41
  42   /* return true iff two stem hints overlap */
  43   static FT_Int
  44   psh2_hint_overlap( PSH2_Hint  hint1,
  45                      PSH2_Hint  hint2 )
  46   {
  47     return ( hint1->org_pos + hint1->org_len >= hint2->org_pos &&
  48              hint2->org_pos + hint2->org_len >= hint1->org_pos );
  49   }
  50
  51
  52   /* destroy hints table */
  53   static void
  54   psh2_hint_table_done( PSH2_Hint_Table  table,
  55                         FT_Memory        memory )
  56   {
  57     FT_FREE( table->zones );
  58     table->num_zones = 0;
  59     table->zone      = 0;
  60
  61     FT_FREE( table->sort );
  62     FT_FREE( table->hints );
  63     table->num_hints   = 0;
  64     table->max_hints   = 0;
  65     table->sort_global = 0;
  66   }
  67
  68
  69   /* deactivate all hints in a table */
  70   static void
  71   psh2_hint_table_deactivate( PSH2_Hint_Table  table )
  72   {
  73     FT_UInt   count = table->max_hints;
  74     PSH2_Hint  hint  = table->hints;
  75
  76
  77     for ( ; count > 0; count--, hint++ )
  78     {
  79       psh2_hint_deactivate( hint );
  80       hint->order = -1;
  81     }
  82   }
  83
  84
  85   /* internal function used to record a new hint */
  86   static void
  87   psh2_hint_table_record( PSH2_Hint_Table  table,
  88                           FT_UInt          idx )
  89   {
  90     PSH2_Hint  hint = table->hints + idx;
  91
  92
  93     if ( idx >= table->max_hints )
  94     {
  95       FT_ERROR(( "%s.activate: invalid hint index %d\n", idx ));
  96       return;
  97     }
  98
  99     /* ignore active hints */
 100     if ( psh2_hint_is_active( hint ) )
 101       return;
 102
 103     psh2_hint_activate( hint );
 104
 105     /* now scan the current active hint set in order to determine */
 106     /* if we are overlapping with another segment                 */
 107     {
 108       PSH2_Hint*  sorted = table->sort_global;
 109       FT_UInt     count  = table->num_hints;
 110       PSH2_Hint   hint2;
 111
 112
 113       hint->parent = 0;
 114       for ( ; count > 0; count--, sorted++ )
 115       {
 116         hint2 = sorted[0];
 117
 118         if ( psh2_hint_overlap( hint, hint2 ) )
 119         {
 120           hint->parent = hint2;
 121           break;
 122         }
 123       }
 124     }
 125
 126     if ( table->num_hints < table->max_hints )
 127       table->sort_global[table->num_hints++] = hint;
 128     else
 129       FT_ERROR(( "%s.activate: too many sorted hints!  BUG!\n",
 130                  "ps.fitter" ));
 131   }
 132
 133
 134   static void
 135   psh2_hint_table_record_mask( PSH2_Hint_Table  table,
 136                                PS_Mask          hint_mask )
 137   {
 138     FT_Int    mask = 0, val = 0;
 139     FT_Byte*  cursor = hint_mask->bytes;
 140     FT_UInt   idx, limit;
 141
 142
 143     limit = hint_mask->num_bits;
 144
 145     for ( idx = 0; idx < limit; idx++ )
 146     {
 147       if ( mask == 0 )
 148       {
 149         val  = *cursor++;
 150         mask = 0x80;
 151       }
 152
 153       if ( val & mask )
 154         psh2_hint_table_record( table, idx );
 155
 156       mask >>= 1;
 157     }
 158   }
 159
 160
 161   /* create hints table */
 162   static FT_Error
 163   psh2_hint_table_init( PSH2_Hint_Table  table,
 164                         PS_Hint_Table    hints,
 165                         PS_Mask_Table    hint_masks,
 166                         PS_Mask_Table    counter_masks,
 167                         FT_Memory        memory )
 168   {
 169     FT_UInt   count = hints->num_hints;
 170     FT_Error  error;
 171
 172     FT_UNUSED( counter_masks );
 173
 174
 175     /* allocate our tables */
 176     if ( FT_NEW_ARRAY( table->sort,  2 * count     ) ||
 177          FT_NEW_ARRAY( table->hints,     count     ) ||
 178          FT_NEW_ARRAY( table->zones, 2 * count + 1 ) )
 179       goto Exit;
 180
 181     table->max_hints   = count;
 182     table->sort_global = table->sort + count;
 183     table->num_hints   = 0;
 184     table->num_zones   = 0;
 185     table->zone        = 0;
 186
 187     /* now, initialize the "hints" array */
 188     {
 189       PSH2_Hint  write = table->hints;
 190       PS_Hint    read  = hints->hints;
 191
 192
 193       for ( ; count > 0; count--, write++, read++ )
 194       {
 195         write->org_pos = read->pos;
 196         write->org_len = read->len;
 197         write->flags   = read->flags;
 198       }
 199     }
 200
 201     /* we now need to determine the initial "parent" stems; first  */
 202     /* activate the hints that are given by the initial hint masks */
 203     if ( hint_masks )
 204     {
 205       FT_UInt  Count = hint_masks->num_masks;
 206       PS_Mask  Mask  = hint_masks->masks;
 207
 208
 209       table->hint_masks = hint_masks;
 210
 211       for ( ; Count > 0; Count--, Mask++ )
 212         psh2_hint_table_record_mask( table, Mask );
 213     }
 214
 215     /* now, do a linear parse in case some hints were left alone */
 216     if ( table->num_hints != table->max_hints )
 217     {
 218       FT_UInt   Index, Count;
 219
 220
 221       FT_ERROR(( "%s.init: missing/incorrect hint masks!\n" ));
 222       Count = table->max_hints;
 223       for ( Index = 0; Index < Count; Index++ )
 224         psh2_hint_table_record( table, Index );
 225     }
 226
 227   Exit:
 228     return error;
 229   }
 230
 231
 232   static void
 233   psh2_hint_table_activate_mask( PSH2_Hint_Table  table,
 234                                  PS_Mask          hint_mask )
 235   {
 236     FT_Int    mask = 0, val = 0;
 237     FT_Byte*  cursor = hint_mask->bytes;
 238     FT_UInt   idx, limit, count;
 239
 240
 241     limit = hint_mask->num_bits;
 242     count = 0;
 243
 244     psh2_hint_table_deactivate( table );
 245
 246     for ( idx = 0; idx < limit; idx++ )
 247     {
 248       if ( mask == 0 )
 249       {
 250         val  = *cursor++;
 251         mask = 0x80;
 252       }
 253
 254       if ( val & mask )
 255       {
 256         PSH2_Hint  hint = &table->hints[idx];
 257
 258
 259         if ( !psh2_hint_is_active( hint ) )
 260         {
 261           FT_UInt     count2;
 262
 263 #if 0
 264           PSH2_Hint*  sort = table->sort;
 265           PSH2_Hint   hint2;
 266
 267           for ( count2 = count; count2 > 0; count2--, sort++ )
 268           {
 269             hint2 = sort[0];
 270             if ( psh2_hint_overlap( hint, hint2 ) )
 271               FT_ERROR(( "%s.activate_mask: found overlapping hints\n",
 272                          "psf.hint" ));
 273           }
 274 #else
 275           count2 = 0;
 276 #endif
 277
 278           if ( count2 == 0 )
 279           {
 280             psh2_hint_activate( hint );
 281             if ( count < table->max_hints )
 282               table->sort[count++] = hint;
 283             else
 284               FT_ERROR(( "%s.activate_mask: too many active hints\n",
 285                          "psf.hint" ));
 286           }
 287         }
 288       }
 289
 290       mask >>= 1;
 291     }
 292     table->num_hints = count;
 293
 294     /* now, sort the hints; they are guaranteed to not overlap */
 295     /* so we can compare their "org_pos" field directly        */
 296     {
 297       FT_Int      i1, i2;
 298       PSH2_Hint   hint1, hint2;
 299       PSH2_Hint*  sort = table->sort;
 300
 301
 302       /* a simple bubble sort will do, since in 99% of cases, the hints */
 303       /* will be already sorted -- and the sort will be linear          */
 304       for ( i1 = 1; i1 < (FT_Int)count; i1++ )
 305       {
 306         hint1 = sort[i1];
 307         for ( i2 = i1 - 1; i2 >= 0; i2-- )
 308         {
 309           hint2 = sort[i2];
 310
 311           if ( hint2->org_pos < hint1->org_pos )
 312             break;
 313
 314           sort[i2 + 1] = hint2;
 315           sort[i2]     = hint1;
 316         }
 317       }
 318     }
 319   }
 320
 321
 322   /*************************************************************************/
 323   /*************************************************************************/
 324   /*****                                                               *****/
 325   /*****               HINTS GRID-FITTING AND OPTIMIZATION             *****/
 326   /*****                                                               *****/
 327   /*************************************************************************/
 328   /*************************************************************************/
 329
 330 #ifdef DEBUG_HINTER
 331   static void
 332   ps2_simple_scale( PSH2_Hint_Table  table,
 333                     FT_Fixed         scale,
 334                     FT_Fixed         delta,
 335                     FT_Int           dimension )
 336   {
 337     PSH2_Hint  hint;
 338     FT_UInt    count;
 339
 340
 341     for ( count = 0; count < table->max_hints; count++ )
 342     {
 343       hint = table->hints + count;
 344
 345       hint->cur_pos = FT_MulFix( hint->org_pos, scale ) + delta;
 346       hint->cur_len = FT_MulFix( hint->org_len, scale );
 347
 348       if ( ps2_debug_hint_func )
 349         ps2_debug_hint_func( hint, dimension );
 350     }
 351   }
 352 #endif
 353
 354
 355   static void
 356   psh2_hint_align( PSH2_Hint    hint,
 357                    PSH_Globals  globals,
 358                    FT_Int       dimension )
 359   {
 360     PSH_Dimension  dim   = &globals->dimension[dimension];
 361     FT_Fixed       scale = dim->scale_mult;
 362     FT_Fixed       delta = dim->scale_delta;
 363
 364
 365     if ( !psh2_hint_is_fitted(hint) )
 366     {
 367       FT_Pos  pos = FT_MulFix( hint->org_pos, scale ) + delta;
 368       FT_Pos  len = FT_MulFix( hint->org_len, scale );
 369
 370       FT_Pos  fit_center;
 371       FT_Pos  fit_len;
 372
 373       PSH_AlignmentRec  align;
 374
 375
 376       /* compute fitted width/height */
 377       fit_len = 0;
 378       if ( hint->org_len )
 379       {
 380         fit_len = psh_dimension_snap_width( dim, hint->org_len );
 381         if ( fit_len < 64 )
 382           fit_len = 64;
 383         else
 384           fit_len = ( fit_len + 32 ) & -64;
 385       }
 386
 387       hint->cur_len = fit_len;
 388
 389       /* check blue zones for horizontal stems */
 390       align.align = PSH_BLUE_ALIGN_NONE;
 391       align.align_bot = align.align_top = 0;
 392
 393       if ( dimension == 1 )
 394         psh_blues_snap_stem( &globals->blues,
 395                              hint->org_pos + hint->org_len,
 396                              hint->org_pos,
 397                              &align );
 398
 399       switch ( align.align )
 400       {
 401       case PSH_BLUE_ALIGN_TOP:
 402         /* the top of the stem is aligned against a blue zone */
 403         hint->cur_pos = align.align_top - fit_len;
 404         break;
 405
 406       case PSH_BLUE_ALIGN_BOT:
 407         /* the bottom of the stem is aligned against a blue zone */
 408         hint->cur_pos = align.align_bot;
 409         break;
 410
 411       case PSH_BLUE_ALIGN_TOP | PSH_BLUE_ALIGN_BOT:
 412         /* both edges of the stem are aligned against blue zones */
 413         hint->cur_pos = align.align_bot;
 414         hint->cur_len = align.align_top - align.align_bot;
 415         break;
 416
 417       default:
 418         {
 419           PSH2_Hint  parent = hint->parent;
 420
 421
 422           if ( parent )
 423           {
 424             FT_Pos  par_org_center, par_cur_center;
 425             FT_Pos  cur_org_center, cur_delta;
 426
 427
 428             /* ensure that parent is already fitted */
 429             if ( !psh2_hint_is_fitted( parent ) )
 430               psh2_hint_align( parent, globals, dimension );
 431
 432             par_org_center = parent->org_pos + ( parent->org_len / 2);
 433             par_cur_center = parent->cur_pos + ( parent->cur_len / 2);
 434             cur_org_center = hint->org_pos   + ( hint->org_len   / 2);
 435
 436             cur_delta = FT_MulFix( cur_org_center - par_org_center, scale );
 437 #if 0
 438             if ( cur_delta >= 0 )
 439               cur_delta = ( cur_delta + 16 ) & -64;
 440             else
 441               cur_delta = -( (-cur_delta + 16 ) & -64 );
 442 #endif
 443             pos = par_cur_center + cur_delta - ( len >> 1 );
 444           }
 445
 446           /* normal processing */
 447           if ( ( fit_len / 64 ) & 1 )
 448           {
 449             /* odd number of pixels */
 450             fit_center = ( ( pos + ( len >> 1 ) ) & -64 ) + 32;
 451           }
 452           else
 453           {
 454             /* even number of pixels */
 455             fit_center = ( pos + ( len >> 1 ) + 32 ) & -64;
 456           }
 457
 458           hint->cur_pos = fit_center - ( fit_len >> 1 );
 459         }
 460       }
 461
 462       psh2_hint_set_fitted( hint );
 463
 464 #ifdef DEBUG_HINTER
 465       if ( ps2_debug_hint_func )
 466         ps2_debug_hint_func( hint, dimension );
 467 #endif
 468     }
 469   }
 470
 471
 472   static void
 473   psh2_hint_table_align_hints( PSH2_Hint_Table  table,
 474                                PSH_Globals      globals,
 475                                FT_Int           dimension )
 476   {
 477     PSH2_Hint      hint;
 478     FT_UInt        count;
 479
 480 #ifdef DEBUG_HINTER
 481     PSH_Dimension  dim   = &globals->dimension[dimension];
 482     FT_Fixed       scale = dim->scale_mult;
 483     FT_Fixed       delta = dim->scale_delta;
 484
 485
 486     if ( ps_debug_no_vert_hints && dimension == 0 )
 487     {
 488       ps2_simple_scale( table, scale, delta, dimension );
 489       return;
 490     }
 491
 492     if ( ps_debug_no_horz_hints && dimension == 1 )
 493     {
 494       ps2_simple_scale( table, scale, delta, dimension );
 495       return;
 496     }
 497 #endif
 498
 499     hint  = table->hints;
 500     count = table->max_hints;
 501
 502     for ( ; count > 0; count--, hint++ )
 503       psh2_hint_align( hint, globals, dimension );
 504   }
 505
 506
 507   /*************************************************************************/
 508   /*************************************************************************/
 509   /*****                                                               *****/
 510   /*****                POINTS INTERPOLATION ROUTINES                  *****/
 511   /*****                                                               *****/
 512   /*************************************************************************/
 513   /*************************************************************************/
 514
 515 #define PSH2_ZONE_MIN  -3200000
 516 #define PSH2_ZONE_MAX  +3200000
 517
 518 #define xxDEBUG_ZONES
 519
 520
 521 #ifdef DEBUG_ZONES
 522
 523 #include <stdio.h>
 524
 525   static void
 526   psh2_print_zone( PSH2_Zone  zone )
 527   {
 528     printf( "zone [scale,delta,min,max] = [%.3f,%.3f,%d,%d]\n",
 529              zone->scale/65536.0,
 530              zone->delta/64.0,
 531              zone->min,
 532              zone->max );
 533   }
 534
 535 #else
 536
 537 #define psh2_print_zone( x )   do { } while ( 0 )
 538
 539 #endif
 540
 541 #if 0
 542   /* setup interpolation zones once the hints have been grid-fitted */
 543   /* by the optimizer                                               */
 544   static void
 545   psh2_hint_table_setup_zones( PSH2_Hint_Table  table,
 546                                FT_Fixed         scale,
 547                                FT_Fixed         delta )
 548   {
 549     FT_UInt     count;
 550     PSH2_Zone   zone;
 551     PSH2_Hint  *sort, hint, hint2;
 552
 553
 554     zone = table->zones;
 555
 556     /* special case, no hints defined */
 557     if ( table->num_hints == 0 )
 558     {
 559       zone->scale = scale;
 560       zone->delta = delta;
 561       zone->min   = PSH2_ZONE_MIN;
 562       zone->max   = PSH2_ZONE_MAX;
 563
 564       table->num_zones = 1;
 565       table->zone      = zone;
 566       return;
 567     }
 568
 569     /* the first zone is before the first hint */
 570     /* x' = (x-x0)*s + x0' = x*s + ( x0' - x0*s ) */
 571     sort = table->sort;
 572     hint = sort[0];
 573
 574     zone->scale = scale;
 575     zone->delta = hint->cur_pos - FT_MulFix( hint->org_pos, scale );
 576     zone->min   = PSH2_ZONE_MIN;
 577     zone->max   = hint->org_pos;
 578
 579     psh2_print_zone( zone );
 580
 581     zone++;
 582
 583     for ( count = table->num_hints; count > 0; count-- )
 584     {
 585       FT_Fixed  scale2;
 586
 587
 588       if ( hint->org_len > 0 )
 589       {
 590         /* setup a zone for inner-stem interpolation */
 591         /* (x' - x0') = (x - x0)*(x1'-x0')/(x1-x0)   */
 592         /* x' = x*s2 + x0' - x0*s2                   */
 593
 594         scale2      = FT_DivFix( hint->cur_len, hint->org_len );
 595         zone->scale = scale2;
 596         zone->min   = hint->org_pos;
 597         zone->max   = hint->org_pos + hint->org_len;
 598         zone->delta = hint->cur_pos - FT_MulFix( zone->min, scale2 );
 599
 600         psh2_print_zone( zone );
 601
 602         zone++;
 603       }
 604
 605       if ( count == 1 )
 606         break;
 607
 608       sort++;
 609       hint2 = sort[0];
 610
 611       /* setup zone for inter-stem interpolation */
 612       /* (x'-x1') = (x-x1)*(x2'-x1')/(x2-x1)     */
 613       /* x' = x*s3 + x1' - x1*s3                 */
 614
 615       scale2 = FT_DivFix( hint2->cur_pos - (hint->cur_pos + hint->cur_len),
 616                           hint2->org_pos - (hint->org_pos + hint->org_len) );
 617       zone->scale = scale2;
 618       zone->min   = hint->org_pos + hint->org_len;
 619       zone->max   = hint2->org_pos;
 620       zone->delta = hint->cur_pos + hint->cur_len -
 621                     FT_MulFix( zone->min, scale2 );
 622
 623       psh2_print_zone( zone );
 624
 625       zone++;
 626
 627       hint = hint2;
 628     }
 629
 630     /* the last zone */
 631     zone->scale = scale;
 632     zone->min   = hint->org_pos + hint->org_len;
 633     zone->max   = PSH2_ZONE_MAX;
 634     zone->delta = hint->cur_pos + hint->cur_len -
 635                   FT_MulFix( zone->min, scale );
 636
 637     psh2_print_zone( zone );
 638
 639     zone++;
 640
 641     table->num_zones = zone - table->zones;
 642     table->zone      = table->zones;
 643   }
 644 #endif
 645
 646 #if 0
 647   /* tune a single coordinate with the current interpolation zones */
 648   static FT_Pos
 649   psh2_hint_table_tune_coord( PSH2_Hint_Table  table,
 650                               FT_Int           coord )
 651   {
 652     PSH2_Zone   zone;
 653
 654
 655     zone = table->zone;
 656
 657     if ( coord < zone->min )
 658     {
 659       do
 660       {
 661         if ( zone == table->zones )
 662           break;
 663
 664         zone--;
 665
 666       } while ( coord < zone->min );
 667       table->zone = zone;
 668     }
 669     else if ( coord > zone->max )
 670     {
 671       do
 672       {
 673         if ( zone == table->zones + table->num_zones - 1 )
 674           break;
 675
 676         zone++;
 677
 678       } while ( coord > zone->max );
 679       table->zone = zone;
 680     }
 681
 682     return FT_MulFix( coord, zone->scale ) + zone->delta;
 683   }
 684 #endif
 685
 686 #if 0
 687  /* tune a given outline with current interpolation zones */
 688  /* the function only works in a single dimension..       */
 689   static void
 690   psh2_hint_table_tune_outline( PSH2_Hint_Table  table,
 691                                 FT_Outline*      outline,
 692                                 PSH_Globals      globals,
 693                                 FT_Int           dimension )
 694
 695   {
 696     FT_UInt        count, first, last;
 697     PS_Mask_Table  hint_masks = table->hint_masks;
 698     PS_Mask        mask;
 699     PSH_Dimension  dim        = &globals->dimension[dimension];
 700     FT_Fixed       scale      = dim->scale_mult;
 701     FT_Fixed       delta      = dim->scale_delta;
 702
 703
 704     if ( hint_masks && hint_masks->num_masks > 0 )
 705     {
 706       first = 0;
 707       mask  = hint_masks->masks;
 708       count = hint_masks->num_masks;
 709
 710       for ( ; count > 0; count--, mask++ )
 711       {
 712         last = mask->end_point;
 713
 714         if ( last > first )
 715         {
 716           FT_Vector*   vec;
 717           FT_Int       count2;
 718
 719
 720           psh2_hint_table_activate_mask( table, mask );
 721           psh2_hint_table_optimize( table, globals, outline, dimension );
 722           psh2_hint_table_setup_zones( table, scale, delta );
 723           last = mask->end_point;
 724
 725           vec    = outline->points + first;
 726           count2 = last - first;
 727
 728           for ( ; count2 > 0; count2--, vec++ )
 729           {
 730             FT_Pos  x, *px;
 731
 732
 733             px  = dimension ? &vec->y : &vec->x;
 734             x   = *px;
 735
 736             *px = psh2_hint_table_tune_coord( table, (FT_Int)x );
 737           }
 738         }
 739
 740         first = last;
 741       }
 742     }
 743     else    /* no hints in this glyph, simply scale the outline */
 744     {
 745       FT_Vector*  vec;
 746
 747
 748       vec   = outline->points;
 749       count = outline->n_points;
 750
 751       if ( dimension == 0 )
 752       {
 753         for ( ; count > 0; count--, vec++ )
 754           vec->x = FT_MulFix( vec->x, scale ) + delta;
 755       }
 756       else
 757       {
 758         for ( ; count > 0; count--, vec++ )
 759           vec->y = FT_MulFix( vec->y, scale ) + delta;
 760       }
 761     }
 762   }
 763 #endif
 764
 765
 766   /*************************************************************************/
 767   /*************************************************************************/
 768   /*****                                                               *****/
 769   /*****                    HINTER GLYPH MANAGEMENT                    *****/
 770   /*****                                                               *****/
 771   /*************************************************************************/
 772   /*************************************************************************/
 773
 774   static int
 775   psh2_point_is_extremum( PSH2_Point  point )
 776   {
 777     PSH2_Point  before = point;
 778     PSH2_Point  after  = point;
 779     FT_Pos      d_before;
 780     FT_Pos      d_after;
 781
 782
 783     do
 784     {
 785       before = before->prev;
 786       if ( before == point )
 787         return 0;
 788
 789       d_before = before->org_u - point->org_u;
 790
 791     } while ( d_before == 0 );
 792
 793     do
 794     {
 795       after = after->next;
 796       if ( after == point )
 797         return 0;
 798
 799       d_after = after->org_u - point->org_u;
 800
 801     } while ( d_after == 0 );
 802
 803     return ( ( d_before > 0 && d_after > 0 ) ||
 804              ( d_before < 0 && d_after < 0 ) );
 805   }
 806
 807
 808   static void
 809   psh2_glyph_done( PSH2_Glyph  glyph )
 810   {
 811     FT_Memory  memory = glyph->memory;
 812
 813
 814     psh2_hint_table_done( &glyph->hint_tables[1], memory );
 815     psh2_hint_table_done( &glyph->hint_tables[0], memory );
 816
 817     FT_FREE( glyph->points );
 818     FT_FREE( glyph->contours );
 819
 820     glyph->num_points   = 0;
 821     glyph->num_contours = 0;
 822
 823     glyph->memory = 0;
 824   }
 825
 826
 827   static int
 828   psh2_compute_dir( FT_Pos  dx,
 829                     FT_Pos  dy )
 830   {
 831     FT_Pos  ax, ay;
 832     int     result = PSH2_DIR_NONE;
 833
 834
 835     ax = ( dx >= 0 ) ? dx : -dx;
 836     ay = ( dy >= 0 ) ? dy : -dy;
 837
 838     if ( ay * 12 < ax )
 839     {
 840       /* |dy| <<< |dx|  means a near-horizontal segment */
 841       result = ( dx >= 0 ) ? PSH2_DIR_RIGHT : PSH2_DIR_LEFT;
 842     }
 843     else if ( ax * 12 < ay )
 844     {
 845       /* |dx| <<< |dy|  means a near-vertical segment */
 846       result = ( dy >= 0 ) ? PSH2_DIR_UP : PSH2_DIR_DOWN;
 847     }
 848
 849     return result;
 850   }
 851
 852
 853   static FT_Error
 854   psh2_glyph_init( PSH2_Glyph   glyph,
 855                    FT_Outline*  outline,
 856                    PS_Hints     ps_hints,
 857                    PSH_Globals  globals )
 858   {
 859     FT_Error   error;
 860     FT_Memory  memory;
 861
 862
 863     /* clear all fields */
 864     FT_MEM_ZERO( glyph, sizeof ( *glyph ) );
 865
 866     memory = globals->memory;
 867
 868     /* allocate and setup points + contours arrays */
 869     if ( FT_NEW_ARRAY( glyph->points,   outline->n_points   ) ||
 870          FT_NEW_ARRAY( glyph->contours, outline->n_contours ) )
 871       goto Exit;
 872
 873     glyph->num_points   = outline->n_points;
 874     glyph->num_contours = outline->n_contours;
 875
 876     {
 877       FT_UInt       first = 0, next, n;
 878       PSH2_Point    points  = glyph->points;
 879       PSH2_Contour  contour = glyph->contours;
 880
 881
 882       for ( n = 0; n < glyph->num_contours; n++ )
 883       {
 884         FT_Int      count;
 885         PSH2_Point  point;
 886
 887
 888         next  = outline->contours[n] + 1;
 889         count = next - first;
 890
 891         contour->start = points + first;
 892         contour->count = (FT_UInt)count;
 893
 894         if ( count > 0 )
 895         {
 896           point = points + first;
 897
 898           point->prev    = points + next - 1;
 899           point->contour = contour;
 900
 901           for ( ; count > 1; count-- )
 902           {
 903             point[0].next = point + 1;
 904             point[1].prev = point;
 905             point++;
 906             point->contour = contour;
 907           }
 908           point->next = points + first;
 909         }
 910
 911         contour++;
 912         first = next;
 913       }
 914     }
 915
 916     {
 917       PSH2_Point  points = glyph->points;
 918       PSH2_Point  point  = points;
 919       FT_Vector*  vec    = outline->points;
 920       FT_UInt     n;
 921
 922
 923       for ( n = 0; n < glyph->num_points; n++, point++ )
 924       {
 925         FT_Int  n_prev = point->prev - points;
 926         FT_Int  n_next = point->next - points;
 927         FT_Pos  dxi, dyi, dxo, dyo;
 928
 929
 930         if ( !( outline->tags[n] & FT_CURVE_TAG_ON ) )
 931           point->flags = PSH2_POINT_OFF;
 932
 933         dxi = vec[n].x - vec[n_prev].x;
 934         dyi = vec[n].y - vec[n_prev].y;
 935
 936         point->dir_in = (FT_Char)psh2_compute_dir( dxi, dyi );
 937
 938         dxo = vec[n_next].x - vec[n].x;
 939         dyo = vec[n_next].y - vec[n].y;
 940
 941         point->dir_out = (FT_Char)psh2_compute_dir( dxo, dyo );
 942
 943         /* detect smooth points */
 944         if ( point->flags & PSH2_POINT_OFF )
 945           point->flags |= PSH2_POINT_SMOOTH;
 946         else if ( point->dir_in  != PSH2_DIR_NONE ||
 947                   point->dir_out != PSH2_DIR_NONE )
 948         {
 949           if ( point->dir_in == point->dir_out )
 950             point->flags |= PSH2_POINT_SMOOTH;
 951         }
 952         else
 953         {
 954           FT_Angle  angle_in, angle_out, diff;
 955
 956
 957           angle_in  = FT_Atan2( dxi, dyi );
 958           angle_out = FT_Atan2( dxo, dyo );
 959
 960           diff = angle_in - angle_out;
 961           if ( diff < 0 )
 962             diff = -diff;
 963
 964           if ( diff > FT_ANGLE_PI )
 965             diff = FT_ANGLE_2PI - diff;
 966
 967           if ( diff < FT_ANGLE_PI / 16 )
 968             point->flags |= PSH2_POINT_SMOOTH;
 969         }
 970       }
 971     }
 972
 973     glyph->memory  = memory;
 974     glyph->outline = outline;
 975     glyph->globals = globals;
 976
 977     /* now deal with hints tables */
 978     error = psh2_hint_table_init( &glyph->hint_tables [0],
 979                                   &ps_hints->dimension[0].hints,
 980                                   &ps_hints->dimension[0].masks,
 981                                   &ps_hints->dimension[0].counters,
 982                                   memory );
 983     if ( error )
 984       goto Exit;
 985
 986     error = psh2_hint_table_init( &glyph->hint_tables [1],
 987                                   &ps_hints->dimension[1].hints,
 988                                   &ps_hints->dimension[1].masks,
 989                                   &ps_hints->dimension[1].counters,
 990                                   memory );
 991     if ( error )
 992       goto Exit;
 993
 994   Exit:
 995     return error;
 996   }
 997
 998
 999   /* load outline point coordinates into hinter glyph */
1000   static void
1001   psh2_glyph_load_points( PSH2_Glyph  glyph,
1002                           FT_Int      dimension )
1003   {
1004     FT_Vector*  vec   = glyph->outline->points;
1005     PSH2_Point  point = glyph->points;
1006     FT_UInt     count = glyph->num_points;
1007
1008
1009     for ( ; count > 0; count--, point++, vec++ )
1010     {
1011       point->flags &= PSH2_POINT_OFF | PSH2_POINT_SMOOTH;
1012       point->hint   = 0;
1013       if ( dimension == 0 )
1014         point->org_u = vec->x;
1015       else
1016         point->org_u = vec->y;
1017
1018 #ifdef DEBUG_HINTER
1019       point->org_x = vec->x;
1020       point->org_y = vec->y;
1021 #endif
1022     }
1023   }
1024
1025
1026   /* save hinted point coordinates back to outline */
1027   static void
1028   psh2_glyph_save_points( PSH2_Glyph  glyph,
1029                           FT_Int      dimension )
1030   {
1031     FT_UInt     n;
1032     PSH2_Point  point = glyph->points;
1033     FT_Vector*  vec   = glyph->outline->points;
1034     char*       tags  = glyph->outline->tags;
1035
1036
1037     for ( n = 0; n < glyph->num_points; n++ )
1038     {
1039       if ( dimension == 0 )
1040         vec[n].x = point->cur_u;
1041       else
1042         vec[n].y = point->cur_u;
1043
1044       if ( psh2_point_is_strong( point ) )
1045         tags[n] |= (char)( ( dimension == 0 ) ? 32 : 64 );
1046
1047 #ifdef DEBUG_HINTER
1048       if ( dimension == 0 )
1049       {
1050         point->cur_x   = point->cur_u;
1051         point->flags_x = point->flags;
1052       }
1053       else
1054       {
1055         point->cur_y   = point->cur_u;
1056         point->flags_y = point->flags;
1057       }
1058 #endif
1059       point++;
1060     }
1061   }
1062
1063
1064 #define PSH2_STRONG_THRESHOLD  10
1065
1066
1067   static void
1068   psh2_hint_table_find_strong_point( PSH2_Hint_Table  table,
1069                                      PSH2_Point       point,
1070                                      FT_Int           major_dir )
1071   {
1072     PSH2_Hint*   sort      = table->sort;
1073     FT_UInt      num_hints = table->num_hints;
1074
1075
1076     for ( ; num_hints > 0; num_hints--, sort++ )
1077     {
1078       PSH2_Hint  hint = sort[0];
1079
1080
1081       if ( ABS( point->dir_in )  == major_dir ||
1082            ABS( point->dir_out ) == major_dir )
1083       {
1084         FT_Pos  d;
1085
1086
1087         d = point->org_u - hint->org_pos;
1088         if ( ABS( d ) < PSH2_STRONG_THRESHOLD )
1089         {
1090         Is_Strong:
1091           psh2_point_set_strong( point );
1092           point->hint = hint;
1093           break;
1094         }
1095
1096         d -= hint->org_len;
1097         if ( ABS( d ) < PSH2_STRONG_THRESHOLD )
1098           goto Is_Strong;
1099       }
1100
1101 #if 1
1102       if ( point->org_u >= hint->org_pos &&
1103            point->org_u <= hint->org_pos + hint->org_len &&
1104            psh2_point_is_extremum( point ) )
1105       {
1106         /* attach to hint, but don't mark as strong */
1107         point->hint = hint;
1108         break;
1109       }
1110 #endif
1111     }
1112   }
1113
1114
1115   /* find strong points in a glyph */
1116   static void
1117   psh2_glyph_find_strong_points( PSH2_Glyph  glyph,
1118                                  FT_Int      dimension )
1119   {
1120     /* a point is strong if it is located on a stem                   */
1121     /* edge and has an "in" or "out" tangent to the hint's direction  */
1122     {
1123       PSH2_Hint_Table  table     = &glyph->hint_tables[dimension];
1124       PS_Mask          mask      = table->hint_masks->masks;
1125       FT_UInt          num_masks = table->hint_masks->num_masks;
1126       FT_UInt          first     = 0;
1127       FT_Int           major_dir = dimension == 0 ? PSH2_DIR_UP : PSH2_DIR_RIGHT;
1128
1129
1130       /* process secondary hints to "selected" points */
1131       if ( num_masks > 1 && glyph->num_points > 0 )
1132       {
1133         first = mask->end_point;
1134         mask++;
1135         for ( ; num_masks > 1; num_masks--, mask++ )
1136         {
1137           FT_UInt  next;
1138           FT_Int   count;
1139
1140
1141           next  = mask->end_point;
1142           count = next - first;
1143           if ( count > 0 )
1144           {
1145             PSH2_Point  point = glyph->points + first;
1146
1147
1148             psh2_hint_table_activate_mask( table, mask );
1149
1150             for ( ; count > 0; count--, point++ )
1151               psh2_hint_table_find_strong_point( table, point, major_dir );
1152           }
1153           first = next;
1154         }
1155       }
1156
1157       /* process primary hints for all points */
1158       if ( num_masks == 1 )
1159       {
1160         FT_UInt     count = glyph->num_points;
1161         PSH2_Point  point = glyph->points;
1162
1163
1164         psh2_hint_table_activate_mask( table, table->hint_masks->masks );
1165         for ( ; count > 0; count--, point++ )
1166         {
1167           if ( !psh2_point_is_strong( point ) )
1168             psh2_hint_table_find_strong_point( table, point, major_dir );
1169         }
1170       }
1171
1172       /* now, certain points may have been attached to hint and */
1173       /* not marked as strong; update their flags then          */
1174       {
1175         FT_UInt     count = glyph->num_points;
1176         PSH2_Point  point = glyph->points;
1177
1178
1179         for ( ; count > 0; count--, point++ )
1180           if ( point->hint && !psh2_point_is_strong( point ) )
1181             psh2_point_set_strong( point );
1182       }
1183     }
1184   }
1185
1186
1187   /* interpolate strong points with the help of hinted coordinates */
1188   static void
1189   psh2_glyph_interpolate_strong_points( PSH2_Glyph  glyph,
1190                                         FT_Int      dimension )
1191   {
1192     PSH_Dimension    dim   = &glyph->globals->dimension[dimension];
1193     FT_Fixed         scale = dim->scale_mult;
1194
1195
1196     {
1197       FT_UInt     count = glyph->num_points;
1198       PSH2_Point  point = glyph->points;
1199
1200
1201       for ( ; count > 0; count--, point++ )
1202       {
1203         PSH2_Hint  hint = point->hint;
1204
1205
1206         if ( hint )
1207         {
1208           FT_Pos  delta;
1209
1210
1211           delta = point->org_u - hint->org_pos;
1212
1213           if ( delta <= 0 )
1214             point->cur_u = hint->cur_pos + FT_MulFix( delta, scale );
1215
1216           else if ( delta >= hint->org_len )
1217             point->cur_u = hint->cur_pos + hint->cur_len +
1218                            FT_MulFix( delta - hint->org_len, scale );
1219
1220           else if ( hint->org_len > 0 )
1221             point->cur_u = hint->cur_pos +
1222                            FT_MulDiv( delta, hint->cur_len, hint->org_len );
1223           else
1224             point->cur_u = hint->cur_pos;
1225
1226           psh2_point_set_fitted( point );
1227         }
1228       }
1229     }
1230   }
1231
1232
1233   static void
1234   psh2_glyph_interpolate_normal_points( PSH2_Glyph  glyph,
1235                                         FT_Int      dimension )
1236   {
1237 #if 1
1238     PSH_Dimension    dim   = &glyph->globals->dimension[dimension];
1239     FT_Fixed         scale = dim->scale_mult;
1240
1241
1242     /* first technique: a point is strong if it is a local extrema */
1243     {
1244       FT_UInt     count = glyph->num_points;
1245       PSH2_Point  point = glyph->points;
1246
1247
1248       for ( ; count > 0; count--, point++ )
1249       {
1250         if ( psh2_point_is_strong( point ) )
1251           continue;
1252
1253         /* sometimes, some local extremas are smooth points */
1254         if ( psh2_point_is_smooth( point ) )
1255         {
1256           if ( point->dir_in == PSH2_DIR_NONE  ||
1257                point->dir_in != point->dir_out )
1258             continue;
1259
1260           if ( !psh2_point_is_extremum( point ) )
1261             continue;
1262
1263           point->flags &= ~PSH2_POINT_SMOOTH;
1264         }
1265
1266         /* find best enclosing point coordinates */
1267         {
1268           PSH2_Point  before = 0;
1269           PSH2_Point  after  = 0;
1270
1271           FT_Pos      diff_before = -32000;
1272           FT_Pos      diff_after  =  32000;
1273           FT_Pos      u = point->org_u;
1274
1275           FT_Int      count2 = glyph->num_points;
1276           PSH2_Point  cur    = glyph->points;
1277
1278
1279           for ( ; count2 > 0; count2--, cur++ )
1280           {
1281             if ( psh2_point_is_strong( cur ) )
1282             {
1283               FT_Pos   diff = cur->org_u - u;;
1284
1285
1286               if ( diff <= 0 )
1287               {
1288                 if ( diff > diff_before )
1289                 {
1290                   diff_before = diff;
1291                   before      = cur;
1292                 }
1293               }
1294               else if ( diff >= 0 )
1295               {
1296                 if ( diff < diff_after )
1297                 {
1298                   diff_after = diff;
1299                   after      = cur;
1300                 }
1301               }
1302             }
1303           }
1304
1305           if ( !before )
1306           {
1307             if ( !after )
1308               continue;
1309
1310             /* we are before the first strong point coordinate; */
1311             /* simply translate the point                       */
1312             point->cur_u = after->cur_u +
1313                            FT_MulFix( point->org_u - after->org_u, scale );
1314           }
1315           else if ( !after )
1316           {
1317             /* we are after the last strong point coordinate; */
1318             /* simply translate the point                     */
1319             point->cur_u = before->cur_u +
1320                            FT_MulFix( point->org_u - before->org_u, scale );
1321           }
1322           else
1323           {
1324             if ( diff_before == 0 )
1325               point->cur_u = before->cur_u;
1326
1327             else if ( diff_after == 0 )
1328               point->cur_u = after->cur_u;
1329
1330             else
1331               point->cur_u = before->cur_u +
1332                              FT_MulDiv( u - before->org_u,
1333                                         after->cur_u - before->cur_u,
1334                                         after->org_u - before->org_u );
1335           }
1336
1337           psh2_point_set_fitted( point );
1338         }
1339       }
1340     }
1341 #endif
1342   }
1343
1344
1345   /* interpolate other points */
1346   static void
1347   psh2_glyph_interpolate_other_points( PSH2_Glyph  glyph,
1348                                        FT_Int      dimension )
1349   {
1350     PSH_Dimension dim          = &glyph->globals->dimension[dimension];
1351     FT_Fixed      scale        = dim->scale_mult;
1352     FT_Fixed      delta        = dim->scale_delta;
1353     PSH2_Contour  contour      = glyph->contours;
1354     FT_UInt       num_contours = glyph->num_contours;
1355
1356
1357     for ( ; num_contours > 0; num_contours--, contour++ )
1358     {
1359       PSH2_Point   start = contour->start;
1360       PSH2_Point   first, next, point;
1361       FT_UInt      fit_count;
1362
1363
1364       /* count the number of strong points in this contour */
1365       next      = start + contour->count;
1366       fit_count = 0;
1367       first     = 0;
1368
1369       for ( point = start; point < next; point++ )
1370         if ( psh2_point_is_fitted( point ) )
1371         {
1372           if ( !first )
1373             first = point;
1374
1375           fit_count++;
1376         }
1377
1378       /* if there are less than 2 fitted points in the contour, we */
1379       /* simply scale and eventually translate the contour points  */
1380       if ( fit_count < 2 )
1381       {
1382         if ( fit_count == 1 )
1383           delta = first->cur_u - FT_MulFix( first->org_u, scale );
1384
1385         for ( point = start; point < next; point++ )
1386           if ( point != first )
1387             point->cur_u = FT_MulFix( point->org_u, scale ) + delta;
1388
1389         goto Next_Contour;
1390       }
1391
1392       /* there are more than 2 strong points in this contour; we */
1393       /* need to interpolate weak points between them            */
1394       start = first;
1395       do
1396       {
1397         point = first;
1398
1399         /* skip consecutive fitted points */
1400         for (;;)
1401         {
1402           next = first->next;
1403           if ( next == start )
1404             goto Next_Contour;
1405
1406           if ( !psh2_point_is_fitted( next ) )
1407             break;
1408
1409           first = next;
1410         }
1411
1412         /* find next fitted point after unfitted one */
1413         for (;;)
1414         {
1415           next = next->next;
1416           if ( psh2_point_is_fitted( next ) )
1417             break;
1418         }
1419
1420         /* now interpolate between them */
1421         {
1422           FT_Pos    org_a, org_ab, cur_a, cur_ab;
1423           FT_Pos    org_c, org_ac, cur_c;
1424           FT_Fixed  scale_ab;
1425
1426
1427           if ( first->org_u <= next->org_u )
1428           {
1429             org_a  = first->org_u;
1430             cur_a  = first->cur_u;
1431             org_ab = next->org_u - org_a;
1432             cur_ab = next->cur_u - cur_a;
1433           }
1434           else
1435           {
1436             org_a  = next->org_u;
1437             cur_a  = next->cur_u;
1438             org_ab = first->org_u - org_a;
1439             cur_ab = first->cur_u - cur_a;
1440           }
1441
1442           scale_ab = 0x10000L;
1443           if ( org_ab > 0 )
1444             scale_ab = FT_DivFix( cur_ab, org_ab );
1445
1446           point = first->next;
1447           do
1448           {
1449             org_c  = point->org_u;
1450             org_ac = org_c - org_a;
1451
1452             if ( org_ac <= 0 )
1453             {
1454               /* on the left of the interpolation zone */
1455               cur_c = cur_a + FT_MulFix( org_ac, scale );
1456             }
1457             else if ( org_ac >= org_ab )
1458             {
1459               /* on the right on the interpolation zone */
1460               cur_c = cur_a + cur_ab + FT_MulFix( org_ac - org_ab, scale );
1461             }
1462             else
1463             {
1464               /* within the interpolation zone */
1465               cur_c = cur_a + FT_MulFix( org_ac, scale_ab );
1466             }
1467
1468             point->cur_u = cur_c;
1469
1470             point = point->next;
1471
1472           } while ( point != next );
1473         }
1474
1475         /* keep going until all points in the contours have been processed */
1476         first = next;
1477
1478       } while ( first != start );
1479
1480     Next_Contour:
1481       ;
1482     }
1483   }
1484
1485
1486   /*************************************************************************/
1487   /*************************************************************************/
1488   /*****                                                               *****/
1489   /*****                     HIGH-LEVEL INTERFACE                      *****/
1490   /*****                                                               *****/
1491   /*************************************************************************/
1492   /*************************************************************************/
1493
1494   FT_Error
1495   ps2_hints_apply( PS_Hints        ps_hints,
1496                    FT_Outline*     outline,
1497                    PSH_Globals     globals,
1498                    FT_Render_Mode  hint_mode )
1499   {
1500     PSH2_GlyphRec  glyphrec;
1501     PSH2_Glyph     glyph = &glyphrec;
1502     FT_Error       error;
1503 #ifdef DEBUG_HINTER
1504     FT_Memory      memory;
1505 #endif
1506     FT_Int         dimension;
1507
1508     FT_UNUSED( hint_mode );
1509
1510 #ifdef DEBUG_HINTER
1511     memory = globals->memory;
1512
1513     if ( ps2_debug_glyph )
1514     {
1515       psh2_glyph_done( ps2_debug_glyph );
1516       FT_FREE( ps2_debug_glyph );
1517     }
1518
1519     if ( FT_NEW( glyph ) )
1520       return error;
1521
1522     ps2_debug_glyph = glyph;
1523 #endif
1524
1525     error = psh2_glyph_init( glyph, outline, ps_hints, globals );
1526     if ( error )
1527       goto Exit;
1528
1529     for ( dimension = 0; dimension < 2; dimension++ )
1530     {
1531       /* load outline coordinates into glyph */
1532       psh2_glyph_load_points( glyph, dimension );
1533
1534       /* compute aligned stem/hints positions */
1535       psh2_hint_table_align_hints( &glyph->hint_tables[dimension],
1536                                    glyph->globals,
1537                                    dimension );
1538
1539       /* find strong points, align them, then interpolate others */
1540       psh2_glyph_find_strong_points( glyph, dimension );
1541       psh2_glyph_interpolate_strong_points( glyph, dimension );
1542       psh2_glyph_interpolate_normal_points( glyph, dimension );
1543       psh2_glyph_interpolate_other_points( glyph, dimension );
1544
1545       /* save hinted coordinates back to outline */
1546       psh2_glyph_save_points( glyph, dimension );
1547     }
1548
1549   Exit:
1550 #ifndef DEBUG_HINTER
1551     psh2_glyph_done( glyph );
1552 #endif
1553     return error;
1554   }
1555
1556
1557 /* END */