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