subsys/win32k/freetype/src/type1/t1hinter.c

   1 /***************************************************************************/
   2 /*                                                                         */
   3 /*  t1hinter.c                                                             */
   4 /*                                                                         */
   5 /*    Type 1 hinter (body).                                                */
   6 /*                                                                         */
   7 /*  Copyright 1996-2000 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   /*************************************************************************/
  20   /*                                                                       */
  21   /* The Hinter is in charge of fitting th scaled outline to the pixel     */
  22   /* grid in order to considerably improve the quality of the Type 1 font  */
  23   /* driver's output.                                                      */
  24   /*                                                                       */
  25   /*************************************************************************/
  26
  27
  28 #include <freetype/internal/ftdebug.h>
  29
  30
  31 #ifdef FT_FLAT_COMPILE
  32
  33 #include "t1objs.h"
  34 #include "t1hinter.h"
  35
  36 #else
  37
  38 #include <freetype/src/type1/t1objs.h>
  39 #include <freetype/src/type1/t1hinter.h>
  40
  41 #endif
  42
  43
  44   /*************************************************************************/
  45   /*                                                                       */
  46   /* The macro FT_COMPONENT is used in trace mode.  It is an implicit      */
  47   /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log  */
  48   /* messages during execution.                                            */
  49   /*                                                                       */
  50 #undef  FT_COMPONENT
  51 #define FT_COMPONENT  trace_t1hint
  52
  53
  54 #undef  ONE_PIXEL
  55 #define ONE_PIXEL  64
  56
  57 #undef  ROUND
  58 #define ROUND( x )    ( ( x + ONE_PIXEL / 2 ) & -ONE_PIXEL )
  59
  60 #undef  SCALE
  61 #define SCALE( val )  FT_MulFix( val, scale )
  62
  63 /* various constants used to describe the alignment of a horizontal */
  64 /* stem with regards to the blue zones                              */
  65
  66 #define T1_ALIGN_NONE    0
  67 #define T1_ALIGN_BOTTOM  1
  68 #define T1_ALIGN_TOP     2
  69 #define T1_ALIGN_BOTH    3
  70
  71
  72   /* very simple bubble sort (not a lot of elements, mostly */
  73   /* pre-sorted, no need for quicksort)                     */
  74
  75   static
  76   void  t1_sort_blues( FT_Int*  blues,
  77                        FT_Int   count )
  78   {
  79     FT_Int   i, swap;
  80     FT_Int*  cur;
  81
  82
  83     for ( i = 2; i < count; i += 2 )
  84     {
  85       cur = blues + i;
  86       do
  87       {
  88         if ( cur[-1] < cur[0] )
  89           break;
  90
  91         swap = cur[-2]; cur[-2] = cur[0]; cur[0] = swap;
  92         swap = cur[-1]; cur[-1] = cur[1]; cur[1] = swap;
  93         cur -= 2;
  94
  95       } while ( cur > blues );
  96     }
  97   }
  98
  99
 100   /*************************************************************************/
 101   /*                                                                       */
 102   /* <Function>                                                            */
 103   /*    t1_set_blue_zones                                                  */
 104   /*                                                                       */
 105   /* <Description>                                                         */
 106   /*    Sets a size object's blue zones during reset.  This will compute   */
 107   /*    the `snap' zone corresponding to each blue zone.                   */
 108   /*                                                                       */
 109   /* <InOut>                                                               */
 110   /*    size :: A handle to target size object.                            */
 111   /*                                                                       */
 112   /* <Return>                                                              */
 113   /*    FreeType error code.  0 means success.                             */
 114   /*                                                                       */
 115   /* <Note>                                                                */
 116   /*    This functions does the following:                                 */
 117   /*                                                                       */
 118   /*    1. It extracts the bottom and top blue zones from the face object. */
 119   /*                                                                       */
 120   /*    2. Each zone is then grown by `BlueFuzz', overlapping is           */
 121   /*       eliminated by adjusting the zone edges appropriately.           */
 122   /*                                                                       */
 123   /*    3. For each zone, we keep its original font units position, its    */
 124   /*       original scaled position, as well as its grown/adjusted edges.  */
 125   /*                                                                       */
 126   static
 127   FT_Error  t1_set_blue_zones( T1_Size  size )
 128   {
 129     T1_Face         face = (T1_Face)size->root.face;
 130     T1_Private*     priv = &face->type1.private_dict;
 131     FT_Int          n;
 132     FT_Int          blues[24];
 133     FT_Int          num_bottom;
 134     FT_Int          num_top;
 135     FT_Int          num_blues;
 136     T1_Size_Hints*  hints = size->hints;
 137     T1_Snap_Zone*   zone;
 138     FT_Pos          pix, orus;
 139     FT_Pos          min, max, threshold;
 140     FT_Fixed        scale;
 141     FT_Bool         is_bottom;
 142
 143
 144     /***********************************************************************/
 145     /*                                                                     */
 146     /*  copy bottom and top blue zones in local arrays                     */
 147     /*                                                                     */
 148
 149     /* First of all, check the sizes of the /BlueValues and /OtherBlues */
 150     /* tables.  They all must contain an even number of arguments.      */
 151     if ( priv->num_other_blues & 1 ||
 152          priv->num_blue_values & 1 )
 153     {
 154       FT_ERROR(( "t1_set_blue_zones: odd number of blue values\n" ));
 155       return T1_Err_Syntax_Error;
 156     }
 157
 158     /* copy the bottom blue zones from /OtherBlues */
 159     num_top    = 0;
 160     num_bottom = priv->num_other_blues;
 161
 162     for ( n = 0; n < num_bottom; n++ )
 163       blues[n] = priv->other_blues[n];
 164
 165     /* add the first blue zone in /BlueValues to the table */
 166     num_top = priv->num_blue_values - 2;
 167     if ( num_top >= 0 )
 168     {
 169       blues[num_bottom    ] = priv->blue_values[0];
 170       blues[num_bottom + 1] = priv->blue_values[1];
 171
 172       num_bottom += 2;
 173     }
 174
 175     /* sort the bottom blue zones */
 176     t1_sort_blues( blues, num_bottom );
 177
 178     hints->num_bottom_zones = num_bottom >> 1;
 179
 180     /* now copy the /BlueValues to the top of the blues array */
 181     if ( num_top > 0 )
 182     {
 183       for ( n = 0; n < num_top; n++ )
 184         blues[num_bottom + n] = priv->blue_values[n + 2];
 185
 186       /* sort the top blue zones */
 187       t1_sort_blues( blues + num_bottom, num_top );
 188     }
 189     else
 190       num_top = 0;
 191
 192     num_blues             = num_top + num_bottom;
 193     hints->num_blue_zones = ( num_blues ) >> 1;
 194
 195     /***********************************************************************/
 196     /*                                                                     */
 197     /* build blue snap zones from the local blues arrays                   */
 198     /*                                                                     */
 199
 200     scale     = size->root.metrics.y_scale;
 201     zone      = hints->blue_zones;
 202     threshold = ONE_PIXEL / 4;   /* 0.25 pixels */
 203
 204     for ( n = 0; n < num_blues; n += 2, zone++ )
 205     {
 206       is_bottom = n < num_bottom ? 1 : 0;
 207
 208       orus = blues[n + is_bottom];  /* get alignement coordinate */
 209       pix  = SCALE( orus );         /* scale it                  */
 210
 211       min  = SCALE( blues[n    ] - priv->blue_fuzz );
 212       max  = SCALE( blues[n + 1] + priv->blue_fuzz );
 213
 214       if ( min > pix - threshold )
 215         min = pix - threshold;
 216       if ( max < pix + threshold )
 217         max = pix + threshold;
 218
 219       zone->orus = orus;
 220       zone->pix  = pix;
 221       zone->min  = min;
 222       zone->max  = max;
 223     }
 224
 225     /* adjust edges in case of overlap */
 226     zone = hints->blue_zones;
 227     for ( n = 0; n < num_blues - 2; n += 2, zone++ )
 228     {
 229       if ( n != num_bottom - 2       &&
 230            zone[0].max > zone[1].min )
 231         zone[0].max = zone[1].min = ( zone[0].pix + zone[1].pix ) / 2;
 232     }
 233
 234     /* compare the current pixel size with the BlueScale value */
 235     /* to know whether to supress overshoots                   */
 236
 237     hints->supress_overshoots =
 238       size->root.metrics.y_ppem < FT_MulFix( 1000, priv->blue_scale );
 239
 240 #ifdef FT_DEBUG_LEVEL_TRACE
 241
 242     /* now print the new blue values in tracing mode */
 243
 244     FT_TRACE2(( "Blue Zones for size object at $%08lx:\n", (long)size ));
 245     FT_TRACE2(( "   orus    pix    min   max\n" ));
 246     FT_TRACE2(( "-------------------------------\n" ));
 247
 248     zone = hints->blue_zones;
 249     for ( n = 0; n < hints->num_blue_zones; n++ )
 250     {
 251       FT_TRACE2(( "    %3d   %.2f   %.2f  %.2f\n",
 252                   zone->orus,
 253                   zone->pix / 64.0,
 254                   zone->min / 64.0,
 255                   zone->max / 64.0 ));
 256       zone++;
 257     }
 258     FT_TRACE2(( "\nOvershoots are %s\n\n",
 259                 hints->supress_overshoots ? "supressed" : "active" ));
 260
 261 #endif /* DEBUG_LEVEL_TRACE */
 262
 263     return T1_Err_Ok;
 264   }
 265
 266
 267   /*************************************************************************/
 268   /*                                                                       */
 269   /* <Function>                                                            */
 270   /*    t1_set_snap_zones                                                  */
 271   /*                                                                       */
 272   /* <Description>                                                         */
 273   /*    This function set a size object's stem snap zones.                 */
 274   /*                                                                       */
 275   /* <InOut>                                                               */
 276   /*    size :: A handle to the target size object.                        */
 277   /*                                                                       */
 278   /* <Return>                                                              */
 279   /*    FreeType error code.  0 means success.                             */
 280   /*                                                                       */
 281   /* <Note>                                                                */
 282   /*    This function performs the following:                              */
 283   /*                                                                       */
 284   /*    1. It reads and scales the stem snap widths from the parent face.  */
 285   /*                                                                       */
 286   /*    2. A `snap zone' is computed for each snap width, by `growing' it  */
 287   /*       with a threshold of 1/2 pixel.  Overlapping is avoided through  */
 288   /*       proper edge adjustment.                                         */
 289   /*                                                                       */
 290   /*    3. Each width whose zone contain the scaled standard set width is  */
 291   /*       removed from the table.                                         */
 292   /*                                                                       */
 293   /*    4. Finally, the standard set width is scaled, and its correponding */
 294   /*       `snap zone' is inserted into the sorted snap zones table.       */
 295   /*                                                                       */
 296   static
 297   FT_Error  t1_set_snap_zones( T1_Size  size )
 298   {
 299     FT_Int          n, direction, n_zones, num_zones;
 300     T1_Snap_Zone*   zone;
 301     T1_Snap_Zone*   base_zone;
 302     FT_Short*       orgs;
 303     FT_Pos          standard_width;
 304     FT_Fixed        scale;
 305
 306     T1_Face         face  = (T1_Face)size->root.face;
 307     T1_Private*     priv  = &face->type1.private_dict;
 308     T1_Size_Hints*  hints = size->hints;
 309
 310
 311     /* start with horizontal snap zones */
 312     direction      = 0;
 313     standard_width = priv->standard_width[0];
 314     n_zones        = priv->num_snap_widths;
 315     base_zone      = hints->snap_widths;
 316     orgs           = priv->snap_widths;
 317     scale          = size->root.metrics.x_scale;
 318
 319     while ( direction < 2 )
 320     {
 321       /*********************************************************************/
 322       /*                                                                   */
 323       /* Read and scale stem snap widths table from the physical font      */
 324       /* record.                                                           */
 325       /*                                                                   */
 326
 327       FT_Pos  prev, orus, pix, min, max, threshold;
 328
 329
 330       threshold = ONE_PIXEL / 4;
 331       zone      = base_zone;
 332
 333       if ( n_zones > 0 )
 334       {
 335         orus = *orgs++;
 336         pix  = SCALE( orus );
 337         min  = pix - threshold;
 338         max  = pix + threshold;
 339
 340         zone->orus = orus;
 341         zone->pix  = pix;
 342         zone->min  = min;
 343         prev       = pix;
 344
 345         for ( n = 1; n < n_zones; n++ )
 346         {
 347           orus = *orgs++;
 348           pix  = SCALE( orus );
 349
 350           if ( pix - prev < 2 * threshold )
 351           {
 352             min = max = ( pix + prev ) / 2;
 353           }
 354           else
 355             min = pix - threshold;
 356
 357           zone->max = max;
 358           zone++;
 359           zone->orus = orus;
 360           zone->pix  = pix;
 361           zone->min  = min;
 362
 363           max  = pix + threshold;
 364           prev = pix;
 365         }
 366         zone->max = max;
 367       }
 368
 369 #ifdef FT_DEBUG_LEVEL_TRACE
 370
 371       /* print the scaled stem snap values in tracing mode */
 372
 373       FT_TRACE2(( "Set_Snap_Zones: first %s pass\n",
 374                   direction ? "vertical" : "horizontal" ));
 375
 376       FT_TRACE2(( "Scaled original stem snap zones:\n" ));
 377       FT_TRACE2(( "   orus   pix   min   max\n" ));
 378       FT_TRACE2(( "-----------------------------\n" ));
 379
 380       zone = base_zone;
 381       for ( n = 0; n < n_zones; n++, zone++ )
 382         FT_TRACE2(( "  %3d  %.2f  %.2f  %.2f\n",
 383                     zone->orus,
 384                     zone->pix / 64.0,
 385                     zone->min / 64.0,
 386                     zone->max / 64.0 ));
 387       FT_TRACE2(( "\n" ));
 388
 389       FT_TRACE2(( "Standard width = %d\n", standard_width ));
 390
 391 #endif /* FT_DEBUG_LEVEL_TRACE */
 392
 393       /*********************************************************************/
 394       /*                                                                   */
 395       /* Now, each snap width which is in the range of the standard set    */
 396       /* width will be removed from the list.                              */
 397       /*                                                                   */
 398
 399       if ( standard_width > 0 )
 400       {
 401         T1_Snap_Zone*  parent;
 402         FT_Pos         std_pix, std_min, std_max;
 403
 404
 405         std_pix = SCALE( standard_width );
 406
 407         std_min = std_pix - threshold;
 408         std_max = std_pix + threshold;
 409
 410         num_zones = 0;
 411         zone      = base_zone;
 412         parent    = base_zone;
 413
 414         for ( n = 0; n < n_zones; n++ )
 415         {
 416           if ( zone->pix >= std_min && zone->pix <= std_max )
 417           {
 418             /* this zone must be removed from the list */
 419             if ( std_min > zone->min )
 420               std_min = zone->min;
 421             if ( std_max < zone->max )
 422               std_max = zone->max;
 423           }
 424           else
 425           {
 426             *parent++ = *zone;
 427             num_zones++;
 428           }
 429           zone++;
 430         }
 431
 432         /*******************************************************************/
 433         /*                                                                 */
 434         /* Now, insert the standard width zone                             */
 435         /*                                                                 */
 436
 437         zone = base_zone + num_zones;
 438         while ( zone > base_zone && zone[-1].pix > std_max )
 439         {
 440           zone[0] = zone[-1];
 441           zone--;
 442         }
 443
 444         /* check border zones */
 445         if ( zone > base_zone && zone[-1].max > std_min )
 446           zone[-1].max = std_min;
 447
 448         if ( zone < base_zone + num_zones && zone[1].min < std_max )
 449           zone[1].min = std_max;
 450
 451         zone->orus = standard_width;
 452         zone->pix  = std_pix;
 453         zone->min  = std_min;
 454         zone->max  = std_max;
 455
 456         num_zones++;
 457       }
 458       else
 459         num_zones = n_zones;
 460
 461       /* save total number of stem snaps now */
 462       if ( direction )
 463         hints->num_snap_heights = num_zones;
 464       else
 465         hints->num_snap_widths  = num_zones;
 466
 467 #ifdef FT_DEBUG_LEVEL_TRACE
 468
 469       /* print the scaled stem snap values in tracing mode */
 470
 471       FT_TRACE2(( "Set_Snap_Zones: second %s pass\n",
 472                   direction ? "vertical" : "horizontal" ));
 473
 474       FT_TRACE2(( "Scaled clipped stem snap zones:\n" ));
 475       FT_TRACE2(( "   orus   pix   min   max\n" ));
 476       FT_TRACE2(( "-----------------------------\n" ));
 477
 478       zone = base_zone;
 479       for ( n = 0; n < num_zones; n++, zone++ )
 480         FT_TRACE2(( "  %3d  %.2f  %.2f  %.2f\n",
 481                     zone->orus,
 482                     zone->pix / 64.0,
 483                     zone->min / 64.0,
 484                     zone->max / 64.0 ));
 485       FT_TRACE2(( "\n" ));
 486
 487       FT_TRACE2(( "Standard width = %d\n", standard_width ));
 488
 489 #endif /* FT_DEBUG_LEVEL_TRACE */
 490
 491       /* continue with vertical snap zone */
 492       direction++;
 493       standard_width = priv->standard_height[0];
 494       n_zones        = priv->num_snap_heights;
 495       base_zone      = hints->snap_heights;
 496       orgs           = priv->snap_heights;
 497       scale          = size->root.metrics.y_scale;
 498     }
 499
 500     return T1_Err_Ok;
 501   }
 502
 503
 504   /*************************************************************************/
 505   /*                                                                       */
 506   /* <Function>                                                            */
 507   /*    T1_New_Size_Hinter                                                 */
 508   /*                                                                       */
 509   /* <Description>                                                         */
 510   /*    Allocates a new hinter structure for a given size object.          */
 511   /*                                                                       */
 512   /* <InOut>                                                               */
 513   /*    size :: A handle to the target size object.                        */
 514   /*                                                                       */
 515   /* <Return>                                                              */
 516   /*    FreeType Error code.  0 means success.                             */
 517   /*                                                                       */
 518   LOCAL_FUNC
 519   FT_Error  T1_New_Size_Hinter( T1_Size  size )
 520   {
 521     FT_Memory  memory = size->root.face->memory;
 522
 523
 524     return MEM_Alloc( size->hints, sizeof ( *size->hints ) );
 525   }
 526
 527
 528   /*************************************************************************/
 529   /*                                                                       */
 530   /* <Function>                                                            */
 531   /*    T1_Done_Size_Hinter                                                */
 532   /*                                                                       */
 533   /* <Description>                                                         */
 534   /*    Releases a given size object's hinter structure.                   */
 535   /*                                                                       */
 536   /* <Input>                                                               */
 537   /*    size :: A handle to the target size object.                        */
 538   /*                                                                       */
 539   LOCAL_FUNC
 540   void  T1_Done_Size_Hinter( T1_Size  size )
 541   {
 542     FT_Memory  memory = size->root.face->memory;
 543
 544
 545     FREE( size->hints );
 546   }
 547
 548
 549   /*************************************************************************/
 550   /*                                                                       */
 551   /* <Function>                                                            */
 552   /*    T1_Reset_Size_Hinter                                               */
 553   /*                                                                       */
 554   /* <Description>                                                         */
 555   /*    Recomputes hinting information when a given size object has        */
 556   /*    changed its resolutions/char sizes/pixel sizes.                    */
 557   /*                                                                       */
 558   /* <InOut>                                                               */
 559   /*    size :: A handle to the size object.                               */
 560   /*                                                                       */
 561   /* <Return>                                                              */
 562   /*    FreeType error code.  0 means success.                             */
 563   /*                                                                       */
 564   LOCAL_FUNC
 565   FT_Error  T1_Reset_Size_Hinter( T1_Size  size )
 566   {
 567     return t1_set_blue_zones( size ) || t1_set_snap_zones( size );
 568   }
 569
 570
 571   /*************************************************************************/
 572   /*                                                                       */
 573   /* <Function>                                                            */
 574   /*    T1_New_Glyph_Hinter                                                */
 575   /*                                                                       */
 576   /* <Description>                                                         */
 577   /*    Allocates a new hinter structure for a given glyph slot.           */
 578   /*                                                                       */
 579   /* <InOut>                                                               */
 580   /*    glyph :: A handle to the target glyph slot.                        */
 581   /*                                                                       */
 582   /* <Return>                                                              */
 583   /*    FreeType error code.  0 means success.                             */
 584   /*                                                                       */
 585   LOCAL_FUNC
 586   FT_Error  T1_New_Glyph_Hinter( T1_GlyphSlot  glyph )
 587   {
 588     FT_Memory  memory = glyph->root.face->memory;
 589
 590
 591     return MEM_Alloc( glyph->hints, sizeof ( *glyph->hints ) );
 592   }
 593
 594
 595   /*************************************************************************/
 596   /*                                                                       */
 597   /* <Function>                                                            */
 598   /*    T1_Done_Glyph_Hinter                                               */
 599   /*                                                                       */
 600   /* <Description>                                                         */
 601   /*    Releases a given glyph slot's hinter structure.                    */
 602   /*                                                                       */
 603   /* <Input>                                                               */
 604   /*    glyph :: A handle to the glyph slot.                               */
 605   /*                                                                       */
 606   LOCAL_FUNC
 607   void  T1_Done_Glyph_Hinter( T1_GlyphSlot  glyph )
 608   {
 609     FT_Memory  memory = glyph->root.face->memory;
 610
 611
 612     FREE( glyph->hints );
 613   }
 614
 615
 616   /*************************************************************************/
 617   /*************************************************************************/
 618   /*************************************************************************/
 619   /**********                                                     **********/
 620   /**********               HINTED GLYPH LOADER                   **********/
 621   /**********                                                     **********/
 622   /**********    The following code is in charge of the first     **********/
 623   /**********    and second pass when loading a single outline    **********/
 624   /**********                                                     **********/
 625   /*************************************************************************/
 626   /*************************************************************************/
 627   /*************************************************************************/
 628
 629
 630   static
 631   FT_Error  t1_hinter_ignore( void )
 632   {
 633     /* do nothing, used for `dotsection' which is unsupported for now */
 634     return 0;
 635   }
 636
 637
 638   static
 639   FT_Error  t1_hinter_stem( T1_Builder*  builder,
 640                             FT_Pos       pos,
 641                             FT_Int       width,
 642                             FT_Bool      vertical )
 643   {
 644     T1_Stem_Table*   stem_table;
 645     T1_Stem_Hint*    stems;
 646     T1_Stem_Hint*    cur_stem;
 647     FT_Int           min, max, n, num_stems;
 648     FT_Bool          new_stem;
 649     T1_Glyph_Hints*  hinter = builder->glyph->hints;
 650
 651
 652     /* select the appropriate stem array */
 653     stem_table = vertical ? &hinter->vert_stems : &hinter->hori_stems;
 654     stems      = stem_table->stems;
 655     num_stems  = stem_table->num_stems;
 656
 657     /* Compute minimum and maximum coord for the stem */
 658     min = pos + ( vertical
 659                 ? builder->left_bearing.x
 660                 : builder->left_bearing.y );
 661
 662     if ( width >= 0 )
 663       max = min + width;
 664     else
 665     {
 666       /* a negative width indicates a `ghost' stem */
 667       if ( width == -21 )
 668         min += width;
 669
 670       max = min;
 671     }
 672
 673     /* Now scan the array.  If we find a stem with the same borders */
 674     /* simply activate it.                                          */
 675     cur_stem = stems;
 676     new_stem = 1;
 677
 678     for ( n = 0; n < num_stems; n++, cur_stem++ )
 679     {
 680       if ( cur_stem->min_edge.orus == min &&
 681            cur_stem->max_edge.orus == max )
 682       {
 683         /* This stem is already in the table, simply activate it */
 684         if ( ( cur_stem->hint_flags & T1_HINT_FLAG_ACTIVE ) == 0 )
 685         {
 686           cur_stem->hint_flags |= T1_HINT_FLAG_ACTIVE;
 687           stem_table->num_active++;
 688         }
 689         new_stem = 0;
 690         break;
 691       }
 692     }
 693
 694     /* add a new stem to the array if necessary */
 695     if ( new_stem )
 696     {
 697       if ( cur_stem >= stems + T1_HINTER_MAX_EDGES )
 698       {
 699         FT_ERROR(( "t1_hinter_stem: too many stems in glyph charstring\n" ));
 700         return T1_Err_Syntax_Error;
 701       }
 702
 703       /* on the first pass, we record the stem, otherwise, this is */
 704       /* a bug in the glyph loader!                                */
 705       if ( builder->pass == 0 )
 706       {
 707         cur_stem->min_edge.orus = min;
 708         cur_stem->max_edge.orus = max;
 709         cur_stem->hint_flags    = T1_HINT_FLAG_ACTIVE;
 710
 711         stem_table->num_stems++;
 712         stem_table->num_active++;
 713       }
 714       else
 715       {
 716         FT_ERROR(( "t1_hinter_stem:" ));
 717         FT_ERROR(( " fatal glyph loader bug -- pass2-stem\n" ));
 718         return T1_Err_Syntax_Error;
 719       }
 720     }
 721
 722     return T1_Err_Ok;
 723   }
 724
 725
 726   static
 727   FT_Error  t1_hinter_stem3( T1_Builder*  builder,
 728                              FT_Pos       pos0,
 729                              FT_Int       width0,
 730                              FT_Pos       pos1,
 731                              FT_Int       width1,
 732                              FT_Pos       pos2,
 733                              FT_Int       width2,
 734                              FT_Bool      vertical )
 735   {
 736     /* For now, simply call `stem' 3 times */
 737     return t1_hinter_stem( builder, pos0, width0, vertical ) ||
 738            t1_hinter_stem( builder, pos1, width1, vertical ) ||
 739            t1_hinter_stem( builder, pos2, width2, vertical );
 740   }
 741
 742
 743   static
 744   FT_Error  t1_hinter_changehints( T1_Builder*  builder )
 745   {
 746     FT_Int           dimension;
 747     T1_Stem_Table*   stem_table;
 748     T1_Glyph_Hints*  hinter = builder->glyph->hints;
 749
 750
 751     /* If we are in the second pass of glyph hinting, we must     */
 752     /* call the function T1_Hint_Points() on the builder in order */
 753     /* to force the fit the latest points to the pixel grid.      */
 754     if ( builder->pass == 1 )
 755       T1_Hint_Points( builder );
 756
 757     /* Simply de-activate all hints in all arrays */
 758     stem_table = &hinter->hori_stems;
 759
 760     for ( dimension = 2; dimension > 0; dimension-- )
 761     {
 762       T1_Stem_Hint*  cur   = stem_table->stems;
 763       T1_Stem_Hint*  limit = cur + stem_table->num_stems;
 764
 765
 766       for ( ; cur < limit; cur++ )
 767         cur->hint_flags &= ~T1_HINT_FLAG_ACTIVE;
 768
 769       stem_table->num_active = 0;
 770       stem_table = &hinter->vert_stems;
 771     }
 772
 773     return T1_Err_Ok;
 774   }
 775
 776
 777   const T1_Hinter_Funcs  t1_hinter_funcs =
 778   {
 779     (T1_Hinter_ChangeHints)t1_hinter_changehints,
 780     (T1_Hinter_DotSection) t1_hinter_ignore,
 781     (T1_Hinter_Stem)       t1_hinter_stem,
 782     (T1_Hinter_Stem3)      t1_hinter_stem3
 783   };
 784
 785
 786   /*************************************************************************/
 787   /*************************************************************************/
 788   /*************************************************************************/
 789   /**********                                                      *********/
 790   /**********                                                      *********/
 791   /**********                STEM HINTS MANAGEMENT                 *********/
 792   /**********                                                      *********/
 793   /**********     The following code is in charge of computing     *********/
 794   /**********     the placement of each scaled stem hint.          *********/
 795   /**********                                                      *********/
 796   /*************************************************************************/
 797   /*************************************************************************/
 798   /*************************************************************************/
 799
 800
 801   /*************************************************************************/
 802   /*                                                                       */
 803   /* <Function>                                                            */
 804   /*    t1_sort_hints                                                      */
 805   /*                                                                       */
 806   /* <Description>                                                         */
 807   /*    Sorta the list of active stems in increasing order, through the    */
 808   /*    `sort' indexing table.                                             */
 809   /*                                                                       */
 810   /* <InOut>                                                               */
 811   /*    table :: A stem hints table.                                       */
 812   /*                                                                       */
 813   static
 814   void  t1_sort_hints( T1_Stem_Table*  table )
 815   {
 816     FT_Int         num_stems  = table->num_stems;
 817     FT_Int         num_active = 0;
 818     FT_Int*        sort       = table->sort;
 819     T1_Stem_Hint*  stems      = table->stems;
 820     FT_Int         n;
 821
 822
 823     /* record active stems in sort table */
 824     for ( n = 0; n < num_stems; n++ )
 825     {
 826       if ( stems[n].hint_flags & T1_HINT_FLAG_ACTIVE )
 827         sort[num_active++] = n;
 828     }
 829
 830     /* Now sort the indices.  There are usually very few stems, */
 831     /* and they are pre-sorted in 90% cases, so we choose a     */
 832     /* simple bubble sort (quicksort would be slower).          */
 833     for ( n = 1; n < num_active; n++ )
 834     {
 835       FT_Int         p   = n - 1;
 836       T1_Stem_Hint*  cur = stems + sort[n];
 837
 838
 839       do
 840       {
 841         FT_Int         swap;
 842         T1_Stem_Hint*  prev = stems + sort[p];
 843
 844
 845         /* note that by definition, the active stems cannot overlap        */
 846         /* so we simply compare their `min' to sort them (we could compare */
 847         /* their max values also; this wouldn't change anything).          */
 848         if ( prev->min_edge.orus <= cur->min_edge.orus )
 849           break;
 850
 851         /* swap elements */
 852         swap        = sort[p    ];
 853         sort[p    ] = sort[p + 1];
 854         sort[p + 1] = swap;
 855         p--;
 856
 857       } while ( p >= 0 );
 858     }
 859
 860     table->num_active = num_active;
 861   }
 862
 863
 864   /*************************************************************************/
 865   /*                                                                       */
 866   /* <Function>                                                            */
 867   /*    t1_hint_horizontal_stems                                           */
 868   /*                                                                       */
 869   /* <Description>                                                         */
 870   /*    Computes the location of each scaled horizontal stem hint.  This   */
 871   /*    takes care of the blue zones and the horizontal stem snap table.   */
 872   /*                                                                       */
 873   /* <Input>                                                               */
 874   /*    table     :: The horizontal stem hints table.                      */
 875   /*                                                                       */
 876   /*    hints     :: The current size's hint structure.                    */
 877   /*                                                                       */
 878   /*    blueShift :: The value of the /BlueShift as taken from the face    */
 879   /*                 object.                                               */
 880   /*                                                                       */
 881   /*    scale     :: The 16.16 scale used to convert outline units to      */
 882   /*                 26.6 pixels.                                          */
 883   /*                                                                       */
 884   /* <Note>                                                                */
 885   /*    For now, all stems are hinted independently from each other.  It   */
 886   /*    might be necessary, for better performance, to introduce the       */
 887   /*    notion of `controlled' hints describing things like counter-stems, */
 888   /*    stem3, as well as overlapping stems control.                       */
 889   /*                                                                       */
 890   static
 891   void  t1_hint_horizontal_stems( T1_Stem_Table*  table,
 892                                   T1_Size_Hints*  hints,
 893                                   FT_Pos          blueShift,
 894                                   FT_Fixed        scale )
 895   {
 896     T1_Stem_Hint*  stem      = table->stems;
 897     T1_Stem_Hint*  limit     = stem + table->num_stems;
 898
 899
 900     /* first of all, scale the blueShift */
 901     blueShift = SCALE( blueShift );
 902
 903     /* then scan the horizontal stem table */
 904     for ( ; stem < limit; stem++ )
 905     {
 906       FT_Pos  bottom_orus = stem->min_edge.orus;
 907       FT_Pos  top_orus    = stem->max_edge.orus;
 908
 909       FT_Pos  top_pix     = SCALE( top_orus );
 910       FT_Pos  bottom_pix  = SCALE( bottom_orus );
 911       FT_Pos  width_pix   = top_pix - bottom_pix;
 912
 913       FT_Pos  bottom      = bottom_pix;
 914       FT_Pos  top         = top_pix;
 915       FT_Int  align       = T1_ALIGN_NONE;
 916
 917
 918       /*********************************************************************/
 919       /*                                                                   */
 920       /* Snap pixel width if in stem snap range                            */
 921       /*                                                                   */
 922
 923       {
 924         T1_Snap_Zone*  zone       = hints->snap_heights;
 925         T1_Snap_Zone*  zone_limit = zone + hints->num_snap_heights;
 926         FT_Pos         best_dist  = 32000;
 927         T1_Snap_Zone*  best_zone  = 0;
 928
 929
 930         for ( ; zone < zone_limit; zone++ )
 931         {
 932           FT_Pos  dist;
 933
 934
 935           dist = width_pix - zone->min;
 936           if ( dist < 0 )
 937             dist = -dist;
 938           if ( dist < best_dist )
 939           {
 940             best_zone = zone;
 941             best_dist = dist;
 942           }
 943         }
 944
 945         if ( best_zone )
 946         {
 947           if ( width_pix > best_zone->pix )
 948           {
 949             width_pix -= 0x20;
 950             if ( width_pix < best_zone->pix )
 951               width_pix = best_zone->pix;
 952           }
 953           else
 954           {
 955             width_pix += 0x20;
 956             if ( width_pix > best_zone->pix )
 957               width_pix = best_zone->pix;
 958           }
 959         }
 960       }
 961
 962       /*********************************************************************/
 963       /*                                                                   */
 964       /* round width - minimum 1 pixel if this isn't a ghost stem          */
 965       /*                                                                   */
 966
 967       if ( width_pix > 0 )
 968         width_pix = width_pix < ONE_PIXEL ? ONE_PIXEL : ROUND( width_pix );
 969
 970
 971       /*********************************************************************/
 972       /*                                                                   */
 973       /* Now check for bottom blue zones alignement                        */
 974       /*                                                                   */
 975
 976       {
 977         FT_Int         num_blues  = hints->num_bottom_zones;
 978         T1_Snap_Zone*  blue       = hints->blue_zones;
 979         T1_Snap_Zone*  blue_limit = blue + num_blues;
 980
 981
 982         for ( ; blue < blue_limit; blue++ )
 983         {
 984           if ( bottom_pix < blue->min )
 985             break;
 986
 987           if ( bottom_pix <= blue->max )
 988           {
 989             align  = T1_ALIGN_BOTTOM;
 990             bottom = ROUND( blue->pix );
 991
 992             /* implement blue shift */
 993             if ( !hints->supress_overshoots )
 994             {
 995               FT_Pos  delta = blue->pix - bottom_pix;
 996
 997
 998               delta   = delta < blueShift ? 0 : ROUND( delta );
 999               bottom -= delta;
1000             }
1001           }
1002         }
1003       }
1004
1005       /*********************************************************************/
1006       /*                                                                   */
1007       /* check for top blue zones alignement                               */
1008       /*                                                                   */
1009
1010       {
1011         FT_Int         num_blues  = hints->num_blue_zones -
1012                                     hints->num_bottom_zones;
1013
1014         T1_Snap_Zone*  blue       = hints->blue_zones +
1015                                     hints->num_bottom_zones;
1016
1017         T1_Snap_Zone*  blue_limit = blue + num_blues;
1018
1019
1020         for ( ; blue < blue_limit; blue++ )
1021         {
1022           if ( top_pix < blue->min )
1023             break;
1024
1025           if ( top_pix <= blue->max )
1026           {
1027             align |= T1_ALIGN_TOP;
1028             top    = ROUND( blue->pix );
1029
1030             /* implement blue shift */
1031             if ( !hints->supress_overshoots )
1032             {
1033               FT_Pos  delta = top - blue->pix;
1034
1035
1036               delta  = delta < blueShift ? 0 : ROUND( delta );
1037               top   += delta;
1038             }
1039           }
1040         }
1041       }
1042
1043       /*********************************************************************/
1044       /*                                                                   */
1045       /* compute the hinted stem position, according to its alignment      */
1046       /*                                                                   */
1047
1048       switch ( align )
1049       {
1050       case T1_ALIGN_BOTTOM:  /* bottom zone alignment */
1051         bottom_pix = bottom;
1052         top_pix    = bottom + width_pix;
1053         break;
1054
1055       case T1_ALIGN_TOP:     /* top zone alignment */
1056         top_pix    = top;
1057         bottom_pix = top - width_pix;
1058         break;
1059
1060       case T1_ALIGN_BOTH:    /* bottom+top zone alignment */
1061         bottom_pix = bottom;
1062         top_pix    = top;
1063         break;
1064
1065       default:               /* no alignment */
1066         /* XXX TODO: Add management of controlled stems */
1067         bottom = ( SCALE( bottom_orus + top_orus ) - width_pix ) / 2;
1068
1069         bottom_pix = ROUND( bottom );
1070         top_pix    = bottom_pix + width_pix;
1071       }
1072
1073       stem->min_edge.pix = bottom_pix;
1074       stem->max_edge.pix = top_pix;
1075     }
1076   }
1077
1078
1079   /*************************************************************************/
1080   /*                                                                       */
1081   /* <Function>                                                            */
1082   /*    t1_hint_vertical_stems                                             */
1083   /*                                                                       */
1084   /* <Description>                                                         */
1085   /*    Computes the location of each scaled vertical stem hint.  This     */
1086   /*    takes care of the vertical stem snap table.                        */
1087   /*                                                                       */
1088   /* <Input>                                                               */
1089   /*    table :: The vertical stem hints table.                            */
1090   /*    hints :: The current size's hint structure.                        */
1091   /*    scale :: The 16.16 scale used to convert outline units to          */
1092   /*             26.6 pixels.                                              */
1093   /*                                                                       */
1094   /* <Note>                                                                */
1095   /*    For now, all stems are hinted independently from each other.  It   */
1096   /*    might be necessary, for better performance, to introduce the       */
1097   /*    notion of `controlled' hints describing things like counter-stems, */
1098   /*    stem3 as well as overlapping stems control.                        */
1099   /*                                                                       */
1100   static
1101   void  t1_hint_vertical_stems( T1_Stem_Table*  table,
1102                                 T1_Size_Hints*  hints,
1103                                 FT_Fixed        scale )
1104   {
1105     T1_Stem_Hint*  stem  = table->stems;
1106     T1_Stem_Hint*  limit = stem + table->num_stems;
1107
1108
1109     for ( ; stem < limit; stem++ )
1110     {
1111       FT_Pos  stem_left  = stem->min_edge.orus;
1112       FT_Pos  stem_right = stem->max_edge.orus;
1113       FT_Pos  width_pix, left;
1114
1115
1116       width_pix = SCALE( stem_right - stem_left );
1117
1118       /* Snap pixel width if in stem snap range */
1119       {
1120         T1_Snap_Zone*  zone       = hints->snap_heights;
1121         T1_Snap_Zone*  zone_limit = zone + hints->num_snap_heights;
1122         FT_Pos         best_dist  = 32000;
1123         T1_Snap_Zone*  best_zone  = 0;
1124
1125
1126         for ( ; zone < zone_limit; zone++ )
1127         {
1128           FT_Pos  dist;
1129
1130
1131           dist = width_pix - zone->min;
1132           if ( dist < 0 )
1133             dist = -dist;
1134           if ( dist < best_dist )
1135           {
1136             best_zone = zone;
1137             best_dist = dist;
1138           }
1139         }
1140
1141         if ( best_zone )
1142         {
1143           if ( width_pix > best_zone->pix )
1144           {
1145             width_pix -= 0x20;
1146             if ( width_pix < best_zone->pix )
1147               width_pix = best_zone->pix;
1148           }
1149           else
1150           {
1151             width_pix += 0x20;
1152             if ( width_pix > best_zone->pix )
1153               width_pix = best_zone->pix;
1154           }
1155         }
1156       }
1157
1158       /* round width - minimum 1 pixel if this isn't a ghost stem */
1159       if ( width_pix > 0 )
1160         width_pix = width_pix < ONE_PIXEL ? ONE_PIXEL
1161                                           : ROUND( width_pix );
1162
1163       /* now place the snapped and rounded stem   */
1164
1165       /* XXX TODO: implement controlled stems for the overlapping */
1166       /*           cases                                          */
1167
1168       left = ( SCALE( stem_left + stem_right ) - width_pix ) / 2;
1169
1170       stem->min_edge.pix = ROUND( left );
1171       stem->max_edge.pix = stem->min_edge.pix + width_pix;
1172     }
1173   }
1174
1175
1176   /*************************************************************************/
1177   /*                                                                       */
1178   /* <Function>                                                            */
1179   /*    t1_hint_point                                                      */
1180   /*                                                                       */
1181   /* <Description>                                                         */
1182   /*    Grid-fit a coordinate with regards to a given stem hints table.    */
1183   /*                                                                       */
1184   /* <Input>                                                               */
1185   /*    table :: The source stem hints table.                              */
1186   /*    coord :: The original coordinate, expressed in font units.         */
1187   /*    scale :: The 16.16 scale used to convert font units into           */
1188   /*             26.6 pixels.                                              */
1189   /*                                                                       */
1190   /* <Return>                                                              */
1191   /*    The hinted/scaled value in 26.6 pixels.                            */
1192   /*                                                                       */
1193   /* <Note>                                                                */
1194   /*    For now, all stems are hinted independently from each other.  It   */
1195   /*    might be necessary, for better performance, to introduce the       */
1196   /*    notion of `controlled' hints describing things like counter-stems, */
1197   /*    stem3 as well as overlapping stems control.                        */
1198   /*                                                                       */
1199   static
1200   FT_Pos  t1_hint_point( T1_Stem_Table*  table,
1201                          FT_Pos          coord,
1202                          FT_Fixed        scale )
1203   {
1204     FT_Int         num_active = table->num_active;
1205     FT_Int         n;
1206     T1_Stem_Hint*  prev = 0;
1207     T1_Stem_Hint*  cur  = 0;
1208     T1_Edge*       min;
1209     T1_Edge*       max;
1210     FT_Pos         delta;
1211
1212
1213     /* only hint when there is at least one stem defined */
1214     if ( num_active <= 0 )
1215       return SCALE( coord );
1216
1217     /* scan the stem table to determine placement of coordinate */
1218     /* relative to the list of sorted and stems                 */
1219     for ( n = 0; n < num_active; n++, prev = cur )
1220     {
1221       cur = table->stems + table->sort[n];
1222
1223       /* is it on the left of the current edge? */
1224       delta = cur->min_edge.orus - coord;
1225       if ( delta == 0 )
1226         return cur->min_edge.pix;
1227
1228       if ( delta > 0 )
1229       {
1230         /* if this is the left of the first edge, simply shift */
1231         if ( !prev )
1232           return cur->min_edge.pix - SCALE( delta );
1233
1234         /* otherwise, interpolate between the maximum of the */
1235         /* previous stem, and the minimum of the current one */
1236         min = &prev->max_edge;
1237         max = &cur->min_edge;
1238
1239         goto Interpolate;
1240       }
1241
1242       /* is it within the current edge? */
1243       delta = cur->max_edge.orus - coord;
1244       if ( delta == 0 )
1245         return cur->max_edge.pix;
1246
1247       if ( delta > 0 )
1248       {
1249         /* interpolate within the stem */
1250         min = &cur->min_edge;
1251         max = &cur->max_edge;
1252
1253         goto Interpolate;
1254       }
1255     }
1256
1257     /* apparently, this coordinate is on the right of the last stem */
1258     delta = coord - cur->max_edge.orus;
1259     return cur->max_edge.pix + SCALE( delta );
1260
1261   Interpolate:
1262     return min->pix + FT_MulDiv( coord     - min->orus,
1263                                  max->pix  - min->pix,
1264                                  max->orus - min->orus );
1265   }
1266
1267
1268   /*************************************************************************/
1269   /*                                                                       */
1270   /* <Function>                                                            */
1271   /*   T1_Hint_Points                                                      */
1272   /*                                                                       */
1273   /* <Description>                                                         */
1274   /*   This function grid-fits several points in a given Type 1 builder    */
1275   /*   at once.                                                            */
1276   /*                                                                       */
1277   /* <Input>                                                               */
1278   /*   builder :: A handle to target Type 1 builder.                       */
1279   /*                                                                       */
1280   LOCAL_FUNC
1281   void  T1_Hint_Points( T1_Builder*  builder )
1282   {
1283     FT_Int    first   = builder->hint_point;
1284     FT_Int    last    = builder->current->n_points - 1;
1285
1286     T1_Size   size    = builder->size;
1287     FT_Fixed  scale_x = size->root.metrics.x_scale;
1288     FT_Fixed  scale_y = size->root.metrics.y_scale;
1289
1290     T1_Glyph_Hints*  hints      = builder->glyph->hints;
1291     T1_Stem_Table*   hori_stems = &hints->hori_stems;
1292     T1_Stem_Table*   vert_stems = &hints->vert_stems;
1293
1294     FT_Vector*  cur   = builder->current->points + first;
1295     FT_Vector*  limit = cur + last - first + 1;
1296
1297
1298     /* first of all, sort the active stem hints */
1299     t1_sort_hints( hori_stems );
1300     t1_sort_hints( vert_stems );
1301
1302     for ( ; cur < limit; cur++ )
1303     {
1304       cur->x = t1_hint_point( vert_stems, cur->x, scale_x );
1305       cur->y = t1_hint_point( hori_stems, cur->y, scale_y );
1306     }
1307
1308     builder->hint_point = builder->current->n_points;
1309   }
1310
1311
1312   /*************************************************************************/
1313   /*                                                                       */
1314   /* <Function>                                                            */
1315   /*    T1_Hint_Stems                                                      */
1316   /*                                                                       */
1317   /* <Description>                                                         */
1318   /*    This function is used to compute the location of each stem hint    */
1319   /*    between the first and second passes of the glyph loader on the     */
1320   /*    charstring.                                                        */
1321   /*                                                                       */
1322   /* <Input>                                                               */
1323   /*    builder :: A handle to the target builder.                         */
1324   /*                                                                       */
1325   LOCAL_FUNC
1326   void  T1_Hint_Stems( T1_Builder*  builder )
1327   {
1328     T1_Glyph_Hints*  hints = builder->glyph->hints;
1329     T1_Private*      priv  = &builder->face->type1.private_dict;
1330
1331     T1_Size   size    = builder->size;
1332     FT_Fixed  scale_x = size->root.metrics.x_scale;
1333     FT_Fixed  scale_y = size->root.metrics.y_scale;
1334
1335
1336     t1_hint_horizontal_stems( &hints->hori_stems,
1337                               builder->size->hints,
1338                               priv->blue_shift,
1339                               scale_y );
1340
1341     t1_hint_vertical_stems( &hints->vert_stems,
1342                             builder->size->hints,
1343                             scale_x );
1344   }
1345
1346
1347 /* END */