source: trunk/poppler/freetype2/src/pshinter/pshalgo.c @ 262

Last change on this file since 262 was 262, checked in by Eugene Romanenko, 12 years ago

PDF plugin: freetype library updated to version 2.3.8

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