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