XFA: merge patch from CL 815103002
[pdfium.git] / third_party / freetype / src / cff / cf2hints.c
1 /***************************************************************************/
2 /*                                                                         */
3 /*  cf2hints.c                                                             */
4 /*                                                                         */
5 /*    Adobe's code for handling CFF hints (body).                          */
6 /*                                                                         */
7 /*  Copyright 2007-2014 Adobe Systems Incorporated.                        */
8 /*                                                                         */
9 /*  This software, and all works of authorship, whether in source or       */
10 /*  object code form as indicated by the copyright notice(s) included      */
11 /*  herein (collectively, the "Work") is made available, and may only be   */
12 /*  used, modified, and distributed under the FreeType Project License,    */
13 /*  LICENSE.TXT.  Additionally, subject to the terms and conditions of the */
14 /*  FreeType Project License, each contributor to the Work hereby grants   */
15 /*  to any individual or legal entity exercising permissions granted by    */
16 /*  the FreeType Project License and this section (hereafter, "You" or     */
17 /*  "Your") a perpetual, worldwide, non-exclusive, no-charge,              */
18 /*  royalty-free, irrevocable (except as stated in this section) patent    */
19 /*  license to make, have made, use, offer to sell, sell, import, and      */
20 /*  otherwise transfer the Work, where such license applies only to those  */
21 /*  patent claims licensable by such contributor that are necessarily      */
22 /*  infringed by their contribution(s) alone or by combination of their    */
23 /*  contribution(s) with the Work to which such contribution(s) was        */
24 /*  submitted.  If You institute patent litigation against any entity      */
25 /*  (including a cross-claim or counterclaim in a lawsuit) alleging that   */
26 /*  the Work or a contribution incorporated within the Work constitutes    */
27 /*  direct or contributory patent infringement, then any patent licenses   */
28 /*  granted to You under this License for that Work shall terminate as of  */
29 /*  the date such litigation is filed.                                     */
30 /*                                                                         */
31 /*  By using, modifying, or distributing the Work you indicate that you    */
32 /*  have read and understood the terms and conditions of the               */
33 /*  FreeType Project License as well as those provided in this section,    */
34 /*  and you accept them fully.                                             */
35 /*                                                                         */
36 /***************************************************************************/
37
38
39 #include "cf2ft.h"
40 #include FT_INTERNAL_DEBUG_H
41
42 #include "cf2glue.h"
43 #include "cf2font.h"
44 #include "cf2hints.h"
45 #include "cf2intrp.h"
46
47
48   /*************************************************************************/
49   /*                                                                       */
50   /* The macro FT_COMPONENT is used in trace mode.  It is an implicit      */
51   /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log  */
52   /* messages during execution.                                            */
53   /*                                                                       */
54 #undef  FT_COMPONENT
55 #define FT_COMPONENT  trace_cf2hints
56
57
58   typedef struct  CF2_HintMoveRec_
59   {
60     size_t     j;          /* index of upper hint map edge   */
61     CF2_Fixed  moveUp;     /* adjustment to optimum position */
62
63   } CF2_HintMoveRec, *CF2_HintMove;
64
65
66   /* Compute angular momentum for winding order detection.  It is called */
67   /* for all lines and curves, but not necessarily in element order.     */
68   static CF2_Int
69   cf2_getWindingMomentum( CF2_Fixed  x1,
70                           CF2_Fixed  y1,
71                           CF2_Fixed  x2,
72                           CF2_Fixed  y2 )
73   {
74     /* cross product of pt1 position from origin with pt2 position from  */
75     /* pt1; we reduce the precision so that the result fits into 32 bits */
76
77     return ( x1 >> 16 ) * ( ( y2 - y1 ) >> 16 ) -
78            ( y1 >> 16 ) * ( ( x2 - x1 ) >> 16 );
79   }
80
81
82   /*
83    * Construct from a StemHint; this is used as a parameter to
84    * `cf2_blues_capture'.
85    * `hintOrigin' is the character space displacement of a seac accent.
86    * Adjust stem hint for darkening here.
87    *
88    */
89   static void
90   cf2_hint_init( CF2_Hint            hint,
91                  const CF2_ArrStack  stemHintArray,
92                  size_t              indexStemHint,
93                  const CF2_Font      font,
94                  CF2_Fixed           hintOrigin,
95                  CF2_Fixed           scale,
96                  FT_Bool             bottom )
97   {
98     CF2_Fixed               width;
99     const CF2_StemHintRec*  stemHint;
100
101
102     FT_ZERO( hint );
103
104     stemHint = (const CF2_StemHintRec*)cf2_arrstack_getPointer(
105                                          stemHintArray,
106                                          indexStemHint );
107
108     width = stemHint->max - stemHint->min;
109
110     if ( width == cf2_intToFixed( -21 ) )
111     {
112       /* ghost bottom */
113
114       if ( bottom )
115       {
116         hint->csCoord = stemHint->max;
117         hint->flags   = CF2_GhostBottom;
118       }
119       else
120         hint->flags = 0;
121     }
122
123     else if ( width == cf2_intToFixed( -20 ) )
124     {
125       /* ghost top */
126
127       if ( bottom )
128         hint->flags = 0;
129       else
130       {
131         hint->csCoord = stemHint->min;
132         hint->flags   = CF2_GhostTop;
133       }
134     }
135
136     else if ( width < 0 )
137     {
138       /* inverted pair */
139
140       /*
141        * Hints with negative widths were produced by an early version of a
142        * non-Adobe font tool.  The Type 2 spec allows edge (ghost) hints
143        * with negative widths, but says
144        *
145        *   All other negative widths have undefined meaning.
146        *
147        * CoolType has a silent workaround that negates the hint width; for
148        * permissive mode, we do the same here.
149        *
150        * Note: Such fonts cannot use ghost hints, but should otherwise work.
151        * Note: Some poor hints in our faux fonts can produce negative
152        *       widths at some blends.  For example, see a light weight of
153        *       `u' in ASerifMM.
154        *
155        */
156       if ( bottom )
157       {
158         hint->csCoord = stemHint->max;
159         hint->flags   = CF2_PairBottom;
160       }
161       else
162       {
163         hint->csCoord = stemHint->min;
164         hint->flags   = CF2_PairTop;
165       }
166     }
167
168     else
169     {
170       /* normal pair */
171
172       if ( bottom )
173       {
174         hint->csCoord = stemHint->min;
175         hint->flags   = CF2_PairBottom;
176       }
177       else
178       {
179         hint->csCoord = stemHint->max;
180         hint->flags   = CF2_PairTop;
181       }
182     }
183
184     /* Now that ghost hints have been detected, adjust this edge for      */
185     /* darkening.  Bottoms are not changed; tops are incremented by twice */
186     /* `darkenY'.                                                         */
187     if ( cf2_hint_isTop( hint ) )
188       hint->csCoord += 2 * font->darkenY;
189
190     hint->csCoord += hintOrigin;
191     hint->scale    = scale;
192     hint->index    = indexStemHint;   /* index in original stem hint array */
193
194     /* if original stem hint has been used, use the same position */
195     if ( hint->flags != 0 && stemHint->used )
196     {
197       if ( cf2_hint_isTop( hint ) )
198         hint->dsCoord = stemHint->maxDS;
199       else
200         hint->dsCoord = stemHint->minDS;
201
202       cf2_hint_lock( hint );
203     }
204     else
205       hint->dsCoord = FT_MulFix( hint->csCoord, scale );
206   }
207
208
209   /* initialize an invalid hint map element */
210   static void
211   cf2_hint_initZero( CF2_Hint  hint )
212   {
213     FT_ZERO( hint );
214   }
215
216
217   FT_LOCAL_DEF( FT_Bool )
218   cf2_hint_isValid( const CF2_Hint  hint )
219   {
220     return (FT_Bool)( hint->flags != 0 );
221   }
222
223
224   static FT_Bool
225   cf2_hint_isPair( const CF2_Hint  hint )
226   {
227     return (FT_Bool)( ( hint->flags                      &
228                         ( CF2_PairBottom | CF2_PairTop ) ) != 0 );
229   }
230
231
232   static FT_Bool
233   cf2_hint_isPairTop( const CF2_Hint  hint )
234   {
235     return (FT_Bool)( ( hint->flags & CF2_PairTop ) != 0 );
236   }
237
238
239   FT_LOCAL_DEF( FT_Bool )
240   cf2_hint_isTop( const CF2_Hint  hint )
241   {
242     return (FT_Bool)( ( hint->flags                    &
243                         ( CF2_PairTop | CF2_GhostTop ) ) != 0 );
244   }
245
246
247   FT_LOCAL_DEF( FT_Bool )
248   cf2_hint_isBottom( const CF2_Hint  hint )
249   {
250     return (FT_Bool)( ( hint->flags                          &
251                         ( CF2_PairBottom | CF2_GhostBottom ) ) != 0 );
252   }
253
254
255   static FT_Bool
256   cf2_hint_isLocked( const CF2_Hint  hint )
257   {
258     return (FT_Bool)( ( hint->flags & CF2_Locked ) != 0 );
259   }
260
261
262   static FT_Bool
263   cf2_hint_isSynthetic( const CF2_Hint  hint )
264   {
265     return (FT_Bool)( ( hint->flags & CF2_Synthetic ) != 0 );
266   }
267
268
269   FT_LOCAL_DEF( void )
270   cf2_hint_lock( CF2_Hint  hint )
271   {
272     hint->flags |= CF2_Locked;
273   }
274
275
276   FT_LOCAL_DEF( void )
277   cf2_hintmap_init( CF2_HintMap   hintmap,
278                     CF2_Font      font,
279                     CF2_HintMap   initialMap,
280                     CF2_ArrStack  hintMoves,
281                     CF2_Fixed     scale )
282   {
283     FT_ZERO( hintmap );
284
285     /* copy parameters from font instance */
286     hintmap->hinted         = font->hinted;
287     hintmap->scale          = scale;
288     hintmap->font           = font;
289     hintmap->initialHintMap = initialMap;
290     /* will clear in `cf2_hintmap_adjustHints' */
291     hintmap->hintMoves      = hintMoves;
292   }
293
294
295   static FT_Bool
296   cf2_hintmap_isValid( const CF2_HintMap  hintmap )
297   {
298     return hintmap->isValid;
299   }
300
301
302   /* transform character space coordinate to device space using hint map */
303   static CF2_Fixed
304   cf2_hintmap_map( CF2_HintMap  hintmap,
305                    CF2_Fixed    csCoord )
306   {
307     if ( hintmap->count == 0 || ! hintmap->hinted )
308     {
309       /* there are no hints; use uniform scale and zero offset */
310       return FT_MulFix( csCoord, hintmap->scale );
311     }
312     else
313     {
314       /* start linear search from last hit */
315       CF2_UInt  i = hintmap->lastIndex;
316
317       FT_ASSERT( hintmap->lastIndex < CF2_MAX_HINT_EDGES );
318
319       /* search up */
320       while ( i < hintmap->count - 1                  &&
321               csCoord >= hintmap->edge[i + 1].csCoord )
322         i += 1;
323
324       /* search down */
325       while ( i > 0 && csCoord < hintmap->edge[i].csCoord )
326         i -= 1;
327
328       hintmap->lastIndex = i;
329
330       if ( i == 0 && csCoord < hintmap->edge[0].csCoord )
331       {
332         /* special case for points below first edge: use uniform scale */
333         return FT_MulFix( csCoord - hintmap->edge[0].csCoord,
334                           hintmap->scale ) +
335                  hintmap->edge[0].dsCoord;
336       }
337       else
338       {
339         /*
340          * Note: entries with duplicate csCoord are allowed.
341          * Use edge[i], the highest entry where csCoord >= entry[i].csCoord
342          */
343         return FT_MulFix( csCoord - hintmap->edge[i].csCoord,
344                           hintmap->edge[i].scale ) +
345                  hintmap->edge[i].dsCoord;
346       }
347     }
348   }
349
350
351   /*
352    * This hinting policy moves a hint pair in device space so that one of
353    * its two edges is on a device pixel boundary (its fractional part is
354    * zero).  `cf2_hintmap_insertHint' guarantees no overlap in CS
355    * space.  Ensure here that there is no overlap in DS.
356    *
357    * In the first pass, edges are adjusted relative to adjacent hints.
358    * Those that are below have already been adjusted.  Those that are
359    * above have not yet been adjusted.  If a hint above blocks an
360    * adjustment to an optimal position, we will try again in a second
361    * pass.  The second pass is top-down.
362    *
363    */
364
365   static void
366   cf2_hintmap_adjustHints( CF2_HintMap  hintmap )
367   {
368     size_t  i, j;
369
370
371     cf2_arrstack_clear( hintmap->hintMoves );      /* working storage */
372
373     /*
374      * First pass is bottom-up (font hint order) without look-ahead.
375      * Locked edges are already adjusted.
376      * Unlocked edges begin with dsCoord from `initialHintMap'.
377      * Save edges that are not optimally adjusted in `hintMoves' array,
378      * and process them in second pass.
379      */
380
381     for ( i = 0; i < hintmap->count; i++ )
382     {
383       FT_Bool  isPair = cf2_hint_isPair( &hintmap->edge[i] );
384
385
386       /* index of upper edge (same value for ghost hint) */
387       j = isPair ? i + 1 : i;
388
389       FT_ASSERT( j < hintmap->count );
390       FT_ASSERT( cf2_hint_isValid( &hintmap->edge[i] ) );
391       FT_ASSERT( cf2_hint_isValid( &hintmap->edge[j] ) );
392       FT_ASSERT( cf2_hint_isLocked( &hintmap->edge[i] ) ==
393                    cf2_hint_isLocked( &hintmap->edge[j] ) );
394
395       if ( !cf2_hint_isLocked( &hintmap->edge[i] ) )
396       {
397         /* hint edge is not locked, we can adjust it */
398         CF2_Fixed  fracDown = cf2_fixedFraction( hintmap->edge[i].dsCoord );
399         CF2_Fixed  fracUp   = cf2_fixedFraction( hintmap->edge[j].dsCoord );
400
401         /* calculate all four possibilities; moves down are negative */
402         CF2_Fixed  downMoveDown = 0 - fracDown;
403         CF2_Fixed  upMoveDown   = 0 - fracUp;
404         CF2_Fixed  downMoveUp   = fracDown == 0
405                                     ? 0
406                                     : cf2_intToFixed( 1 ) - fracDown;
407         CF2_Fixed  upMoveUp     = fracUp == 0
408                                     ? 0
409                                     : cf2_intToFixed( 1 ) - fracUp;
410
411         /* smallest move up */
412         CF2_Fixed  moveUp   = FT_MIN( downMoveUp, upMoveUp );
413         /* smallest move down */
414         CF2_Fixed  moveDown = FT_MAX( downMoveDown, upMoveDown );
415
416         /* final amount to move edge or edge pair */
417         CF2_Fixed  move;
418
419         CF2_Fixed  downMinCounter = CF2_MIN_COUNTER;
420         CF2_Fixed  upMinCounter   = CF2_MIN_COUNTER;
421         FT_Bool    saveEdge       = FALSE;
422
423
424         /* minimum counter constraint doesn't apply when adjacent edges */
425         /* are synthetic                                                */
426         /* TODO: doesn't seem a big effect; for now, reduce the code    */
427 #if 0
428         if ( i == 0                                        ||
429              cf2_hint_isSynthetic( &hintmap->edge[i - 1] ) )
430           downMinCounter = 0;
431
432         if ( j >= hintmap->count - 1                       ||
433              cf2_hint_isSynthetic( &hintmap->edge[j + 1] ) )
434           upMinCounter = 0;
435 #endif
436
437         /* is there room to move up?                                    */
438         /* there is if we are at top of array or the next edge is at or */
439         /* beyond proposed move up?                                     */
440         if ( j >= hintmap->count - 1                            ||
441              hintmap->edge[j + 1].dsCoord >=
442                hintmap->edge[j].dsCoord + moveUp + upMinCounter )
443         {
444           /* there is room to move up; is there also room to move down? */
445           if ( i == 0                                                 ||
446                hintmap->edge[i - 1].dsCoord <=
447                  hintmap->edge[i].dsCoord + moveDown - downMinCounter )
448           {
449             /* move smaller absolute amount */
450             move = ( -moveDown < moveUp ) ? moveDown : moveUp;  /* optimum */
451           }
452           else
453             move = moveUp;
454         }
455         else
456         {
457           /* is there room to move down? */
458           if ( i == 0                                                 ||
459                hintmap->edge[i - 1].dsCoord <=
460                  hintmap->edge[i].dsCoord + moveDown - downMinCounter )
461           {
462             move     = moveDown;
463             /* true if non-optimum move */
464             saveEdge = (FT_Bool)( moveUp < -moveDown );
465           }
466           else
467           {
468             /* no room to move either way without overlapping or reducing */
469             /* the counter too much                                       */
470             move     = 0;
471             saveEdge = TRUE;
472           }
473         }
474
475         /* Identify non-moves and moves down that aren't optimal, and save */
476         /* them for second pass.                                           */
477         /* Do this only if there is an unlocked edge above (which could    */
478         /* possibly move).                                                 */
479         if ( saveEdge                                    &&
480              j < hintmap->count - 1                      &&
481              !cf2_hint_isLocked( &hintmap->edge[j + 1] ) )
482         {
483           CF2_HintMoveRec  savedMove;
484
485
486           savedMove.j      = j;
487           /* desired adjustment in second pass */
488           savedMove.moveUp = moveUp - move;
489
490           cf2_arrstack_push( hintmap->hintMoves, &savedMove );
491         }
492
493         /* move the edge(s) */
494         hintmap->edge[i].dsCoord += move;
495         if ( isPair )
496           hintmap->edge[j].dsCoord += move;
497       }
498
499       /* assert there are no overlaps in device space */
500       FT_ASSERT( i == 0                                                   ||
501                  hintmap->edge[i - 1].dsCoord <= hintmap->edge[i].dsCoord );
502       FT_ASSERT( i < j                                                ||
503                  hintmap->edge[i].dsCoord <= hintmap->edge[j].dsCoord );
504
505       /* adjust the scales, avoiding divide by zero */
506       if ( i > 0 )
507       {
508         if ( hintmap->edge[i].csCoord != hintmap->edge[i - 1].csCoord )
509           hintmap->edge[i - 1].scale =
510             FT_DivFix(
511               hintmap->edge[i].dsCoord - hintmap->edge[i - 1].dsCoord,
512               hintmap->edge[i].csCoord - hintmap->edge[i - 1].csCoord );
513       }
514
515       if ( isPair )
516       {
517         if ( hintmap->edge[j].csCoord != hintmap->edge[j - 1].csCoord )
518           hintmap->edge[j - 1].scale =
519             FT_DivFix(
520               hintmap->edge[j].dsCoord - hintmap->edge[j - 1].dsCoord,
521               hintmap->edge[j].csCoord - hintmap->edge[j - 1].csCoord );
522
523         i += 1;     /* skip upper edge on next loop */
524       }
525     }
526
527     /* second pass tries to move non-optimal hints up, in case there is */
528     /* room now                                                         */
529     for ( i = cf2_arrstack_size( hintmap->hintMoves ); i > 0; i-- )
530     {
531       CF2_HintMove  hintMove = (CF2_HintMove)
532                       cf2_arrstack_getPointer( hintmap->hintMoves, i - 1 );
533
534
535       j = hintMove->j;
536
537       /* this was tested before the push, above */
538       FT_ASSERT( j < hintmap->count - 1 );
539
540       /* is there room to move up? */
541       if ( hintmap->edge[j + 1].dsCoord >=
542              hintmap->edge[j].dsCoord + hintMove->moveUp + CF2_MIN_COUNTER )
543       {
544         /* there is more room now, move edge up */
545         hintmap->edge[j].dsCoord += hintMove->moveUp;
546
547         if ( cf2_hint_isPair( &hintmap->edge[j] ) )
548         {
549           FT_ASSERT( j > 0 );
550           hintmap->edge[j - 1].dsCoord += hintMove->moveUp;
551         }
552       }
553     }
554   }
555
556
557   /* insert hint edges into map, sorted by csCoord */
558   static void
559   cf2_hintmap_insertHint( CF2_HintMap  hintmap,
560                           CF2_Hint     bottomHintEdge,
561                           CF2_Hint     topHintEdge )
562   {
563     CF2_UInt  indexInsert;
564
565     /* set default values, then check for edge hints */
566     FT_Bool   isPair         = TRUE;
567     CF2_Hint  firstHintEdge  = bottomHintEdge;
568     CF2_Hint  secondHintEdge = topHintEdge;
569
570
571     /* one or none of the input params may be invalid when dealing with */
572     /* edge hints; at least one edge must be valid                      */
573     FT_ASSERT( cf2_hint_isValid( bottomHintEdge ) ||
574                cf2_hint_isValid( topHintEdge )    );
575
576     /* determine how many and which edges to insert */
577     if ( !cf2_hint_isValid( bottomHintEdge ) )
578     {
579       /* insert only the top edge */
580       firstHintEdge = topHintEdge;
581       isPair        = FALSE;
582     }
583     else if ( !cf2_hint_isValid( topHintEdge ) )
584     {
585       /* insert only the bottom edge */
586       isPair = FALSE;
587     }
588
589     /* paired edges must be in proper order */
590     FT_ASSERT( !isPair                                         ||
591                topHintEdge->csCoord >= bottomHintEdge->csCoord );
592
593     /* linear search to find index value of insertion point */
594     indexInsert = 0;
595     for ( ; indexInsert < hintmap->count; indexInsert++ )
596     {
597       if ( hintmap->edge[indexInsert].csCoord >= firstHintEdge->csCoord )
598         break;
599     }
600
601     /*
602      * Discard any hints that overlap in character space.  Most often, this
603      * is while building the initial map, where captured hints from all
604      * zones are combined.  Define overlap to include hints that `touch'
605      * (overlap zero).  Hiragino Sans/Gothic fonts have numerous hints that
606      * touch.  Some fonts have non-ideographic glyphs that overlap our
607      * synthetic hints.
608      *
609      * Overlap also occurs when darkening stem hints that are close.
610      *
611      */
612     if ( indexInsert < hintmap->count )
613     {
614       /* we are inserting before an existing edge:    */
615       /* verify that an existing edge is not the same */
616       if ( hintmap->edge[indexInsert].csCoord == firstHintEdge->csCoord )
617         return; /* ignore overlapping stem hint */
618
619       /* verify that a new pair does not straddle the next edge */
620       if ( isPair                                                        &&
621            hintmap->edge[indexInsert].csCoord <= secondHintEdge->csCoord )
622         return; /* ignore overlapping stem hint */
623
624       /* verify that we are not inserting between paired edges */
625       if ( cf2_hint_isPairTop( &hintmap->edge[indexInsert] ) )
626         return; /* ignore overlapping stem hint */
627     }
628
629     /* recompute device space locations using initial hint map */
630     if ( cf2_hintmap_isValid( hintmap->initialHintMap ) &&
631          !cf2_hint_isLocked( firstHintEdge )            )
632     {
633       if ( isPair )
634       {
635         /* Use hint map to position the center of stem, and nominal scale */
636         /* to position the two edges.  This preserves the stem width.     */
637         CF2_Fixed  midpoint  = cf2_hintmap_map(
638                                  hintmap->initialHintMap,
639                                  ( secondHintEdge->csCoord +
640                                    firstHintEdge->csCoord ) / 2 );
641         CF2_Fixed  halfWidth = FT_MulFix(
642                                  ( secondHintEdge->csCoord -
643                                    firstHintEdge->csCoord ) / 2,
644                                  hintmap->scale );
645
646
647         firstHintEdge->dsCoord  = midpoint - halfWidth;
648         secondHintEdge->dsCoord = midpoint + halfWidth;
649       }
650       else
651         firstHintEdge->dsCoord = cf2_hintmap_map( hintmap->initialHintMap,
652                                                   firstHintEdge->csCoord );
653     }
654
655     /*
656      * Discard any hints that overlap in device space; this can occur
657      * because locked hints have been moved to align with blue zones.
658      *
659      * TODO: Although we might correct this later during adjustment, we
660      * don't currently have a way to delete a conflicting hint once it has
661      * been inserted.  See v2.030 MinionPro-Regular, 12 ppem darkened,
662      * initial hint map for second path, glyph 945 (the perispomeni (tilde)
663      * in U+1F6E, Greek omega with psili and perispomeni).  Darkening is
664      * 25.  Pair 667,747 initially conflicts in design space with top edge
665      * 660.  This is because 667 maps to 7.87, and the top edge was
666      * captured by a zone at 8.0.  The pair is later successfully inserted
667      * in a zone without the top edge.  In this zone it is adjusted to 8.0,
668      * and no longer conflicts with the top edge in design space.  This
669      * means it can be included in yet a later zone which does have the top
670      * edge hint.  This produces a small mismatch between the first and
671      * last points of this path, even though the hint masks are the same.
672      * The density map difference is tiny (1/256).
673      *
674      */
675
676     if ( indexInsert > 0 )
677     {
678       /* we are inserting after an existing edge */
679       if ( firstHintEdge->dsCoord < hintmap->edge[indexInsert - 1].dsCoord )
680         return;
681     }
682
683     if ( indexInsert < hintmap->count )
684     {
685       /* we are inserting before an existing edge */
686       if ( isPair )
687       {
688         if ( secondHintEdge->dsCoord > hintmap->edge[indexInsert].dsCoord )
689           return;
690       }
691       else
692       {
693         if ( firstHintEdge->dsCoord > hintmap->edge[indexInsert].dsCoord )
694           return;
695       }
696     }
697
698     /* make room to insert */
699     {
700       CF2_Int  iSrc = hintmap->count - 1;
701       CF2_Int  iDst = isPair ? hintmap->count + 1 : hintmap->count;
702
703       CF2_Int  count = hintmap->count - indexInsert;
704
705
706       if ( iDst >= CF2_MAX_HINT_EDGES )
707       {
708         FT_TRACE4(( "cf2_hintmap_insertHint: too many hintmaps\n" ));
709         return;
710       }
711
712       while ( count-- )
713         hintmap->edge[iDst--] = hintmap->edge[iSrc--];
714
715       /* insert first edge */
716       hintmap->edge[indexInsert] = *firstHintEdge;         /* copy struct */
717       hintmap->count += 1;
718
719       if ( isPair )
720       {
721         /* insert second edge */
722         hintmap->edge[indexInsert + 1] = *secondHintEdge;  /* copy struct */
723         hintmap->count                += 1;
724       }
725     }
726
727     return;
728   }
729
730
731   /*
732    * Build a map from hints and mask.
733    *
734    * This function may recur one level if `hintmap->initialHintMap' is not yet
735    * valid.
736    * If `initialMap' is true, simply build initial map.
737    *
738    * Synthetic hints are used in two ways.  A hint at zero is inserted, if
739    * needed, in the initial hint map, to prevent translations from
740    * propagating across the origin.  If synthetic em box hints are enabled
741    * for ideographic dictionaries, then they are inserted in all hint
742    * maps, including the initial one.
743    *
744    */
745   FT_LOCAL_DEF( void )
746   cf2_hintmap_build( CF2_HintMap   hintmap,
747                      CF2_ArrStack  hStemHintArray,
748                      CF2_ArrStack  vStemHintArray,
749                      CF2_HintMask  hintMask,
750                      CF2_Fixed     hintOrigin,
751                      FT_Bool       initialMap )
752   {
753     FT_Byte*  maskPtr;
754
755     CF2_Font         font = hintmap->font;
756     CF2_HintMaskRec  tempHintMask;
757
758     size_t   bitCount, i;
759     FT_Byte  maskByte;
760
761
762     /* check whether initial map is constructed */
763     if ( !initialMap && !cf2_hintmap_isValid( hintmap->initialHintMap ) )
764     {
765       /* make recursive call with initialHintMap and temporary mask; */
766       /* temporary mask will get all bits set, below */
767       cf2_hintmask_init( &tempHintMask, hintMask->error );
768       cf2_hintmap_build( hintmap->initialHintMap,
769                          hStemHintArray,
770                          vStemHintArray,
771                          &tempHintMask,
772                          hintOrigin,
773                          TRUE );
774     }
775
776     if ( !cf2_hintmask_isValid( hintMask ) )
777     {
778       /* without a hint mask, assume all hints are active */
779       cf2_hintmask_setAll( hintMask,
780                            cf2_arrstack_size( hStemHintArray ) +
781                              cf2_arrstack_size( vStemHintArray ) );
782       if ( !cf2_hintmask_isValid( hintMask ) )
783           return;                   /* too many stem hints */
784     }
785
786     /* begin by clearing the map */
787     hintmap->count     = 0;
788     hintmap->lastIndex = 0;
789
790     /* make a copy of the hint mask so we can modify it */
791     tempHintMask = *hintMask;
792     maskPtr      = cf2_hintmask_getMaskPtr( &tempHintMask );
793
794     /* use the hStem hints only, which are first in the mask */
795     bitCount = cf2_arrstack_size( hStemHintArray );
796
797     /* Defense-in-depth.  Should never return here. */
798     if ( bitCount > hintMask->bitCount )
799         return;
800
801     /* synthetic embox hints get highest priority */
802     if ( font->blues.doEmBoxHints )
803     {
804       CF2_HintRec  dummy;
805
806
807       cf2_hint_initZero( &dummy );   /* invalid hint map element */
808
809       /* ghost bottom */
810       cf2_hintmap_insertHint( hintmap,
811                               &font->blues.emBoxBottomEdge,
812                               &dummy );
813       /* ghost top */
814       cf2_hintmap_insertHint( hintmap,
815                               &dummy,
816                               &font->blues.emBoxTopEdge );
817     }
818
819     /* insert hints captured by a blue zone or already locked (higher */
820     /* priority)                                                      */
821     for ( i = 0, maskByte = 0x80; i < bitCount; i++ )
822     {
823       if ( maskByte & *maskPtr )
824       {
825         /* expand StemHint into two `CF2_Hint' elements */
826         CF2_HintRec  bottomHintEdge, topHintEdge;
827
828
829         cf2_hint_init( &bottomHintEdge,
830                        hStemHintArray,
831                        i,
832                        font,
833                        hintOrigin,
834                        hintmap->scale,
835                        TRUE /* bottom */ );
836         cf2_hint_init( &topHintEdge,
837                        hStemHintArray,
838                        i,
839                        font,
840                        hintOrigin,
841                        hintmap->scale,
842                        FALSE /* top */ );
843
844         if ( cf2_hint_isLocked( &bottomHintEdge ) ||
845              cf2_hint_isLocked( &topHintEdge )    ||
846              cf2_blues_capture( &font->blues,
847                                 &bottomHintEdge,
848                                 &topHintEdge )   )
849         {
850           /* insert captured hint into map */
851           cf2_hintmap_insertHint( hintmap, &bottomHintEdge, &topHintEdge );
852
853           *maskPtr &= ~maskByte;      /* turn off the bit for this hint */
854         }
855       }
856
857       if ( ( i & 7 ) == 7 )
858       {
859         /* move to next mask byte */
860         maskPtr++;
861         maskByte = 0x80;
862       }
863       else
864         maskByte >>= 1;
865     }
866
867     /* initial hint map includes only captured hints plus maybe one at 0 */
868
869     /*
870      * TODO: There is a problem here because we are trying to build a
871      *       single hint map containing all captured hints.  It is
872      *       possible for there to be conflicts between captured hints,
873      *       either because of darkening or because the hints are in
874      *       separate hint zones (we are ignoring hint zones for the
875      *       initial map).  An example of the latter is MinionPro-Regular
876      *       v2.030 glyph 883 (Greek Capital Alpha with Psili) at 15ppem.
877      *       A stem hint for the psili conflicts with the top edge hint
878      *       for the base character.  The stem hint gets priority because
879      *       of its sort order.  In glyph 884 (Greek Capital Alpha with
880      *       Psili and Oxia), the top of the base character gets a stem
881      *       hint, and the psili does not.  This creates different initial
882      *       maps for the two glyphs resulting in different renderings of
883      *       the base character.  Will probably defer this either as not
884      *       worth the cost or as a font bug.  I don't think there is any
885      *       good reason for an accent to be captured by an alignment
886      *       zone.  -darnold 2/12/10
887      */
888
889     if ( initialMap )
890     {
891       /* Apply a heuristic that inserts a point for (0,0), unless it's     */
892       /* already covered by a mapping.  This locks the baseline for glyphs */
893       /* that have no baseline hints.                                      */
894
895       if ( hintmap->count == 0                           ||
896            hintmap->edge[0].csCoord > 0                  ||
897            hintmap->edge[hintmap->count - 1].csCoord < 0 )
898       {
899         /* all edges are above 0 or all edges are below 0; */
900         /* construct a locked edge hint at 0               */
901
902         CF2_HintRec  edge, invalid;
903
904
905         cf2_hint_initZero( &edge );
906
907         edge.flags = CF2_GhostBottom |
908                      CF2_Locked      |
909                      CF2_Synthetic;
910         edge.scale = hintmap->scale;
911
912         cf2_hint_initZero( &invalid );
913         cf2_hintmap_insertHint( hintmap, &edge, &invalid );
914       }
915     }
916     else
917     {
918       /* insert remaining hints */
919
920       maskPtr = cf2_hintmask_getMaskPtr( &tempHintMask );
921
922       for ( i = 0, maskByte = 0x80; i < bitCount; i++ )
923       {
924         if ( maskByte & *maskPtr )
925         {
926           CF2_HintRec  bottomHintEdge, topHintEdge;
927
928
929           cf2_hint_init( &bottomHintEdge,
930                          hStemHintArray,
931                          i,
932                          font,
933                          hintOrigin,
934                          hintmap->scale,
935                          TRUE /* bottom */ );
936           cf2_hint_init( &topHintEdge,
937                          hStemHintArray,
938                          i,
939                          font,
940                          hintOrigin,
941                          hintmap->scale,
942                          FALSE /* top */ );
943
944           cf2_hintmap_insertHint( hintmap, &bottomHintEdge, &topHintEdge );
945         }
946
947         if ( ( i & 7 ) == 7 )
948         {
949           /* move to next mask byte */
950           maskPtr++;
951           maskByte = 0x80;
952         }
953         else
954           maskByte >>= 1;
955       }
956     }
957
958     /*
959      * Note: The following line is a convenient place to break when
960      *       debugging hinting.  Examine `hintmap->edge' for the list of
961      *       enabled hints, then step over the call to see the effect of
962      *       adjustment.  We stop here first on the recursive call that
963      *       creates the initial map, and then on each counter group and
964      *       hint zone.
965      */
966
967     /* adjust positions of hint edges that are not locked to blue zones */
968     cf2_hintmap_adjustHints( hintmap );
969
970     /* save the position of all hints that were used in this hint map; */
971     /* if we use them again, we'll locate them in the same position    */
972     if ( !initialMap )
973     {
974       for ( i = 0; i < hintmap->count; i++ )
975       {
976         if ( !cf2_hint_isSynthetic( &hintmap->edge[i] ) )
977         {
978           /* Note: include both valid and invalid edges            */
979           /* Note: top and bottom edges are copied back separately */
980           CF2_StemHint  stemhint = (CF2_StemHint)
981                           cf2_arrstack_getPointer( hStemHintArray,
982                                                    hintmap->edge[i].index );
983
984
985           if ( cf2_hint_isTop( &hintmap->edge[i] ) )
986             stemhint->maxDS = hintmap->edge[i].dsCoord;
987           else
988             stemhint->minDS = hintmap->edge[i].dsCoord;
989
990           stemhint->used = TRUE;
991         }
992       }
993     }
994
995     /* hint map is ready to use */
996     hintmap->isValid = TRUE;
997
998     /* remember this mask has been used */
999     cf2_hintmask_setNew( hintMask, FALSE );
1000   }
1001
1002
1003   FT_LOCAL_DEF( void )
1004   cf2_glyphpath_init( CF2_GlyphPath         glyphpath,
1005                       CF2_Font              font,
1006                       CF2_OutlineCallbacks  callbacks,
1007                       CF2_Fixed             scaleY,
1008                       /* CF2_Fixed  hShift, */
1009                       CF2_ArrStack          hStemHintArray,
1010                       CF2_ArrStack          vStemHintArray,
1011                       CF2_HintMask          hintMask,
1012                       CF2_Fixed             hintOriginY,
1013                       const CF2_Blues       blues,
1014                       const FT_Vector*      fractionalTranslation )
1015   {
1016     FT_ZERO( glyphpath );
1017
1018     glyphpath->font      = font;
1019     glyphpath->callbacks = callbacks;
1020
1021     cf2_arrstack_init( &glyphpath->hintMoves,
1022                        font->memory,
1023                        &font->error,
1024                        sizeof ( CF2_HintMoveRec ) );
1025
1026     cf2_hintmap_init( &glyphpath->initialHintMap,
1027                       font,
1028                       &glyphpath->initialHintMap,
1029                       &glyphpath->hintMoves,
1030                       scaleY );
1031     cf2_hintmap_init( &glyphpath->firstHintMap,
1032                       font,
1033                       &glyphpath->initialHintMap,
1034                       &glyphpath->hintMoves,
1035                       scaleY );
1036     cf2_hintmap_init( &glyphpath->hintMap,
1037                       font,
1038                       &glyphpath->initialHintMap,
1039                       &glyphpath->hintMoves,
1040                       scaleY );
1041
1042     glyphpath->scaleX = font->innerTransform.a;
1043     glyphpath->scaleC = font->innerTransform.c;
1044     glyphpath->scaleY = font->innerTransform.d;
1045
1046     glyphpath->fractionalTranslation = *fractionalTranslation;
1047
1048 #if 0
1049     glyphpath->hShift = hShift;       /* for fauxing */
1050 #endif
1051
1052     glyphpath->hStemHintArray = hStemHintArray;
1053     glyphpath->vStemHintArray = vStemHintArray;
1054     glyphpath->hintMask       = hintMask;      /* ptr to current mask */
1055     glyphpath->hintOriginY    = hintOriginY;
1056     glyphpath->blues          = blues;
1057     glyphpath->darken         = font->darkened; /* TODO: should we make copies? */
1058     glyphpath->xOffset        = font->darkenX;
1059     glyphpath->yOffset        = font->darkenY;
1060     glyphpath->miterLimit     = 2 * FT_MAX(
1061                                      cf2_fixedAbs( glyphpath->xOffset ),
1062                                      cf2_fixedAbs( glyphpath->yOffset ) );
1063
1064     /* .1 character space unit */
1065     glyphpath->snapThreshold = cf2_floatToFixed( 0.1f );
1066
1067     glyphpath->moveIsPending = TRUE;
1068     glyphpath->pathIsOpen    = FALSE;
1069     glyphpath->pathIsClosing = FALSE;
1070     glyphpath->elemIsQueued  = FALSE;
1071   }
1072
1073
1074   FT_LOCAL_DEF( void )
1075   cf2_glyphpath_finalize( CF2_GlyphPath  glyphpath )
1076   {
1077     cf2_arrstack_finalize( &glyphpath->hintMoves );
1078   }
1079
1080
1081   /*
1082    * Hint point in y-direction and apply outerTransform.
1083    * Input `current' hint map (which is actually delayed by one element).
1084    * Input x,y point in Character Space.
1085    * Output x,y point in Device Space, including translation.
1086    */
1087   static void
1088   cf2_glyphpath_hintPoint( CF2_GlyphPath  glyphpath,
1089                            CF2_HintMap    hintmap,
1090                            FT_Vector*     ppt,
1091                            CF2_Fixed      x,
1092                            CF2_Fixed      y )
1093   {
1094     FT_Vector  pt;   /* hinted point in upright DS */
1095
1096
1097     pt.x = FT_MulFix( glyphpath->scaleX, x ) +
1098              FT_MulFix( glyphpath->scaleC, y );
1099     pt.y = cf2_hintmap_map( hintmap, y );
1100
1101     ppt->x = FT_MulFix( glyphpath->font->outerTransform.a, pt.x )   +
1102                FT_MulFix( glyphpath->font->outerTransform.c, pt.y ) +
1103                glyphpath->fractionalTranslation.x;
1104     ppt->y = FT_MulFix( glyphpath->font->outerTransform.b, pt.x )   +
1105                FT_MulFix( glyphpath->font->outerTransform.d, pt.y ) +
1106                glyphpath->fractionalTranslation.y;
1107   }
1108
1109
1110   /*
1111    * From two line segments, (u1,u2) and (v1,v2), compute a point of
1112    * intersection on the corresponding lines.
1113    * Return false if no intersection is found, or if the intersection is
1114    * too far away from the ends of the line segments, u2 and v1.
1115    *
1116    */
1117   static FT_Bool
1118   cf2_glyphpath_computeIntersection( CF2_GlyphPath     glyphpath,
1119                                      const FT_Vector*  u1,
1120                                      const FT_Vector*  u2,
1121                                      const FT_Vector*  v1,
1122                                      const FT_Vector*  v2,
1123                                      FT_Vector*        intersection )
1124   {
1125     /*
1126      * Let `u' be a zero-based vector from the first segment, `v' from the
1127      * second segment.
1128      * Let `w 'be the zero-based vector from `u1' to `v1'.
1129      * `perp' is the `perpendicular dot product'; see
1130      * http://mathworld.wolfram.com/PerpDotProduct.html.
1131      * `s' is the parameter for the parametric line for the first segment
1132      * (`u').
1133      *
1134      * See notation in
1135      * http://softsurfer.com/Archive/algorithm_0104/algorithm_0104B.htm.
1136      * Calculations are done in 16.16, but must handle the squaring of
1137      * line lengths in character space.  We scale all vectors by 1/32 to
1138      * avoid overflow.  This allows values up to 4095 to be squared.  The
1139      * scale factor cancels in the divide.
1140      *
1141      * TODO: the scale factor could be computed from UnitsPerEm.
1142      *
1143      */
1144
1145 #define cf2_perp( a, b )                                    \
1146           ( FT_MulFix( a.x, b.y ) - FT_MulFix( a.y, b.x ) )
1147
1148   /* round and divide by 32 */
1149 #define CF2_CS_SCALE( x )         \
1150           ( ( (x) + 0x10 ) >> 5 )
1151
1152     FT_Vector  u, v, w;      /* scaled vectors */
1153     CF2_Fixed  denominator, s;
1154
1155
1156     u.x = CF2_CS_SCALE( u2->x - u1->x );
1157     u.y = CF2_CS_SCALE( u2->y - u1->y );
1158     v.x = CF2_CS_SCALE( v2->x - v1->x );
1159     v.y = CF2_CS_SCALE( v2->y - v1->y );
1160     w.x = CF2_CS_SCALE( v1->x - u1->x );
1161     w.y = CF2_CS_SCALE( v1->y - u1->y );
1162
1163     denominator = cf2_perp( u, v );
1164
1165     if ( denominator == 0 )
1166       return FALSE;           /* parallel or coincident lines */
1167
1168     s = FT_DivFix( cf2_perp( w, v ), denominator );
1169
1170     intersection->x = u1->x + FT_MulFix( s, u2->x - u1->x );
1171     intersection->y = u1->y + FT_MulFix( s, u2->y - u1->y );
1172
1173     /*
1174      * Special case snapping for horizontal and vertical lines.
1175      * This cleans up intersections and reduces problems with winding
1176      * order detection.
1177      * Sample case is sbc cd KozGoPr6N-Medium.otf 20 16685.
1178      * Note: these calculations are in character space.
1179      *
1180      */
1181
1182     if ( u1->x == u2->x                                                     &&
1183          cf2_fixedAbs( intersection->x - u1->x ) < glyphpath->snapThreshold )
1184       intersection->x = u1->x;
1185     if ( u1->y == u2->y                                                     &&
1186          cf2_fixedAbs( intersection->y - u1->y ) < glyphpath->snapThreshold )
1187       intersection->y = u1->y;
1188
1189     if ( v1->x == v2->x                                                     &&
1190          cf2_fixedAbs( intersection->x - v1->x ) < glyphpath->snapThreshold )
1191       intersection->x = v1->x;
1192     if ( v1->y == v2->y                                                     &&
1193          cf2_fixedAbs( intersection->y - v1->y ) < glyphpath->snapThreshold )
1194       intersection->y = v1->y;
1195
1196     /* limit the intersection distance from midpoint of u2 and v1 */
1197     if ( cf2_fixedAbs( intersection->x - ( u2->x + v1->x ) / 2 ) >
1198            glyphpath->miterLimit                                   ||
1199          cf2_fixedAbs( intersection->y - ( u2->y + v1->y ) / 2 ) >
1200            glyphpath->miterLimit                                   )
1201       return FALSE;
1202
1203     return TRUE;
1204   }
1205
1206
1207   /*
1208    * Push the cached element (glyphpath->prevElem*) to the outline
1209    * consumer.  When a darkening offset is used, the end point of the
1210    * cached element may be adjusted to an intersection point or we may
1211    * synthesize a connecting line to the current element.  If we are
1212    * closing a subpath, we may also generate a connecting line to the start
1213    * point.
1214    *
1215    * This is where Character Space (CS) is converted to Device Space (DS)
1216    * using a hint map.  This calculation must use a HintMap that was valid
1217    * at the time the element was saved.  For the first point in a subpath,
1218    * that is a saved HintMap.  For most elements, it just means the caller
1219    * has delayed building a HintMap from the current HintMask.
1220    *
1221    * Transform each point with outerTransform and call the outline
1222    * callbacks.  This is a general 3x3 transform:
1223    *
1224    *   x' = a*x + c*y + tx, y' = b*x + d*y + ty
1225    *
1226    * but it uses 4 elements from CF2_Font and the translation part
1227    * from CF2_GlyphPath.
1228    *
1229    */
1230   static void
1231   cf2_glyphpath_pushPrevElem( CF2_GlyphPath  glyphpath,
1232                               CF2_HintMap    hintmap,
1233                               FT_Vector*     nextP0,
1234                               FT_Vector      nextP1,
1235                               FT_Bool        close )
1236   {
1237     CF2_CallbackParamsRec  params;
1238
1239     FT_Vector*  prevP0;
1240     FT_Vector*  prevP1;
1241
1242     FT_Vector  intersection    = { 0, 0 };
1243     FT_Bool    useIntersection = FALSE;
1244
1245
1246     FT_ASSERT( glyphpath->prevElemOp == CF2_PathOpLineTo ||
1247                glyphpath->prevElemOp == CF2_PathOpCubeTo );
1248
1249     if ( glyphpath->prevElemOp == CF2_PathOpLineTo )
1250     {
1251       prevP0 = &glyphpath->prevElemP0;
1252       prevP1 = &glyphpath->prevElemP1;
1253     }
1254     else
1255     {
1256       prevP0 = &glyphpath->prevElemP2;
1257       prevP1 = &glyphpath->prevElemP3;
1258     }
1259
1260     /* optimization: if previous and next elements are offset by the same */
1261     /* amount, then there will be no gap, and no need to compute an       */
1262     /* intersection.                                                      */
1263     if ( prevP1->x != nextP0->x || prevP1->y != nextP0->y )
1264     {
1265       /* previous element does not join next element:             */
1266       /* adjust end point of previous element to the intersection */
1267       useIntersection = cf2_glyphpath_computeIntersection( glyphpath,
1268                                                            prevP0,
1269                                                            prevP1,
1270                                                            nextP0,
1271                                                            &nextP1,
1272                                                            &intersection );
1273       if ( useIntersection )
1274       {
1275         /* modify the last point of the cached element (either line or */
1276         /* curve)                                                      */
1277         *prevP1 = intersection;
1278       }
1279     }
1280
1281     params.pt0 = glyphpath->currentDS;
1282
1283     switch( glyphpath->prevElemOp )
1284     {
1285     case CF2_PathOpLineTo:
1286       params.op = CF2_PathOpLineTo;
1287
1288       /* note: pt2 and pt3 are unused */
1289
1290       if ( close )
1291       {
1292         /* use first hint map if closing */
1293         cf2_glyphpath_hintPoint( glyphpath,
1294                                  &glyphpath->firstHintMap,
1295                                  &params.pt1,
1296                                  glyphpath->prevElemP1.x,
1297                                  glyphpath->prevElemP1.y );
1298       }
1299       else
1300       {
1301         cf2_glyphpath_hintPoint( glyphpath,
1302                                  hintmap,
1303                                  &params.pt1,
1304                                  glyphpath->prevElemP1.x,
1305                                  glyphpath->prevElemP1.y );
1306       }
1307
1308       /* output only non-zero length lines */
1309       if ( params.pt0.x != params.pt1.x || params.pt0.y != params.pt1.y )
1310       {
1311         glyphpath->callbacks->lineTo( glyphpath->callbacks, &params );
1312
1313         glyphpath->currentDS = params.pt1;
1314       }
1315       break;
1316
1317     case CF2_PathOpCubeTo:
1318       params.op = CF2_PathOpCubeTo;
1319
1320       /* TODO: should we intersect the interior joins (p1-p2 and p2-p3)? */
1321       cf2_glyphpath_hintPoint( glyphpath,
1322                                hintmap,
1323                                &params.pt1,
1324                                glyphpath->prevElemP1.x,
1325                                glyphpath->prevElemP1.y );
1326       cf2_glyphpath_hintPoint( glyphpath,
1327                                hintmap,
1328                                &params.pt2,
1329                                glyphpath->prevElemP2.x,
1330                                glyphpath->prevElemP2.y );
1331       cf2_glyphpath_hintPoint( glyphpath,
1332                                hintmap,
1333                                &params.pt3,
1334                                glyphpath->prevElemP3.x,
1335                                glyphpath->prevElemP3.y );
1336
1337       glyphpath->callbacks->cubeTo( glyphpath->callbacks, &params );
1338
1339       glyphpath->currentDS = params.pt3;
1340
1341       break;
1342     }
1343
1344     if ( !useIntersection || close )
1345     {
1346       /* insert connecting line between end of previous element and start */
1347       /* of current one                                                   */
1348       /* note: at the end of a subpath, we might do both, so use `nextP0' */
1349       /* before we change it, below                                       */
1350
1351       if ( close )
1352       {
1353         /* if we are closing the subpath, then nextP0 is in the first     */
1354         /* hint zone                                                      */
1355         cf2_glyphpath_hintPoint( glyphpath,
1356                                  &glyphpath->firstHintMap,
1357                                  &params.pt1,
1358                                  nextP0->x,
1359                                  nextP0->y );
1360       }
1361       else
1362       {
1363         cf2_glyphpath_hintPoint( glyphpath,
1364                                  hintmap,
1365                                  &params.pt1,
1366                                  nextP0->x,
1367                                  nextP0->y );
1368       }
1369
1370       if ( params.pt1.x != glyphpath->currentDS.x ||
1371            params.pt1.y != glyphpath->currentDS.y )
1372       {
1373         /* length is nonzero */
1374         params.op  = CF2_PathOpLineTo;
1375         params.pt0 = glyphpath->currentDS;
1376
1377         /* note: pt2 and pt3 are unused */
1378         glyphpath->callbacks->lineTo( glyphpath->callbacks, &params );
1379
1380         glyphpath->currentDS = params.pt1;
1381       }
1382     }
1383
1384     if ( useIntersection )
1385     {
1386       /* return intersection point to caller */
1387       *nextP0 = intersection;
1388     }
1389   }
1390
1391
1392   /* push a MoveTo element based on current point and offset of current */
1393   /* element                                                            */
1394   static void
1395   cf2_glyphpath_pushMove( CF2_GlyphPath  glyphpath,
1396                           FT_Vector      start )
1397   {
1398     CF2_CallbackParamsRec  params;
1399
1400
1401     params.op  = CF2_PathOpMoveTo;
1402     params.pt0 = glyphpath->currentDS;
1403
1404     /* Test if move has really happened yet; it would have called */
1405     /* `cf2_hintmap_build' to set `isValid'.                   */
1406     if ( !cf2_hintmap_isValid( &glyphpath->hintMap ) )
1407     {
1408       /* we are here iff first subpath is missing a moveto operator: */
1409       /* synthesize first moveTo to finish initialization of hintMap */
1410       cf2_glyphpath_moveTo( glyphpath,
1411                             glyphpath->start.x,
1412                             glyphpath->start.y );
1413     }
1414
1415     cf2_glyphpath_hintPoint( glyphpath,
1416                              &glyphpath->hintMap,
1417                              &params.pt1,
1418                              start.x,
1419                              start.y );
1420
1421     /* note: pt2 and pt3 are unused */
1422     glyphpath->callbacks->moveTo( glyphpath->callbacks, &params );
1423
1424     glyphpath->currentDS    = params.pt1;
1425     glyphpath->offsetStart0 = start;
1426   }
1427
1428
1429   /*
1430    * All coordinates are in character space.
1431    * On input, (x1, y1) and (x2, y2) give line segment.
1432    * On output, (x, y) give offset vector.
1433    * We use a piecewise approximation to trig functions.
1434    *
1435    * TODO: Offset true perpendicular and proper length
1436    *       supply the y-translation for hinting here, too,
1437    *       that adds yOffset unconditionally to *y.
1438    */
1439   static void
1440   cf2_glyphpath_computeOffset( CF2_GlyphPath  glyphpath,
1441                                CF2_Fixed      x1,
1442                                CF2_Fixed      y1,
1443                                CF2_Fixed      x2,
1444                                CF2_Fixed      y2,
1445                                CF2_Fixed*     x,
1446                                CF2_Fixed*     y )
1447   {
1448     CF2_Fixed  dx = x2 - x1;
1449     CF2_Fixed  dy = y2 - y1;
1450
1451
1452     /* note: negative offsets don't work here; negate deltas to change */
1453     /* quadrants, below                                                */
1454     if ( glyphpath->font->reverseWinding )
1455     {
1456       dx = -dx;
1457       dy = -dy;
1458     }
1459
1460     *x = *y = 0;
1461
1462     if ( !glyphpath->darken )
1463         return;
1464
1465     /* add momentum for this path element */
1466     glyphpath->callbacks->windingMomentum +=
1467       cf2_getWindingMomentum( x1, y1, x2, y2 );
1468
1469     /* note: allow mixed integer and fixed multiplication here */
1470     if ( dx >= 0 )
1471     {
1472       if ( dy >= 0 )
1473       {
1474         /* first quadrant, +x +y */
1475
1476         if ( dx > 2 * dy )
1477         {
1478           /* +x */
1479           *x = 0;
1480           *y = 0;
1481         }
1482         else if ( dy > 2 * dx )
1483         {
1484           /* +y */
1485           *x = glyphpath->xOffset;
1486           *y = glyphpath->yOffset;
1487         }
1488         else
1489         {
1490           /* +x +y */
1491           *x = FT_MulFix( cf2_floatToFixed( 0.7 ),
1492                           glyphpath->xOffset );
1493           *y = FT_MulFix( cf2_floatToFixed( 1.0 - 0.7 ),
1494                           glyphpath->yOffset );
1495         }
1496       }
1497       else
1498       {
1499         /* fourth quadrant, +x -y */
1500
1501         if ( dx > -2 * dy )
1502         {
1503           /* +x */
1504           *x = 0;
1505           *y = 0;
1506         }
1507         else if ( -dy > 2 * dx )
1508         {
1509           /* -y */
1510           *x = -glyphpath->xOffset;
1511           *y = glyphpath->yOffset;
1512         }
1513         else
1514         {
1515           /* +x -y */
1516           *x = FT_MulFix( cf2_floatToFixed( -0.7 ),
1517                           glyphpath->xOffset );
1518           *y = FT_MulFix( cf2_floatToFixed( 1.0 - 0.7 ),
1519                           glyphpath->yOffset );
1520         }
1521       }
1522     }
1523     else
1524     {
1525       if ( dy >= 0 )
1526       {
1527         /* second quadrant, -x +y */
1528
1529         if ( -dx > 2 * dy )
1530         {
1531           /* -x */
1532           *x = 0;
1533           *y = 2 * glyphpath->yOffset;
1534         }
1535         else if ( dy > -2 * dx )
1536         {
1537           /* +y */
1538           *x = glyphpath->xOffset;
1539           *y = glyphpath->yOffset;
1540         }
1541         else
1542         {
1543           /* -x +y */
1544           *x = FT_MulFix( cf2_floatToFixed( 0.7 ),
1545                           glyphpath->xOffset );
1546           *y = FT_MulFix( cf2_floatToFixed( 1.0 + 0.7 ),
1547                           glyphpath->yOffset );
1548         }
1549       }
1550       else
1551       {
1552         /* third quadrant, -x -y */
1553
1554         if ( -dx > -2 * dy )
1555         {
1556           /* -x */
1557           *x = 0;
1558           *y = 2 * glyphpath->yOffset;
1559         }
1560         else if ( -dy > -2 * dx )
1561         {
1562           /* -y */
1563           *x = -glyphpath->xOffset;
1564           *y = glyphpath->yOffset;
1565         }
1566         else
1567         {
1568           /* -x -y */
1569           *x = FT_MulFix( cf2_floatToFixed( -0.7 ),
1570                           glyphpath->xOffset );
1571           *y = FT_MulFix( cf2_floatToFixed( 1.0 + 0.7 ),
1572                           glyphpath->yOffset );
1573         }
1574       }
1575     }
1576   }
1577
1578
1579   /*
1580    * The functions cf2_glyphpath_{moveTo,lineTo,curveTo,closeOpenPath} are
1581    * called by the interpreter with Character Space (CS) coordinates.  Each
1582    * path element is placed into a queue of length one to await the
1583    * calculation of the following element.  At that time, the darkening
1584    * offset of the following element is known and joins can be computed,
1585    * including possible modification of this element, before mapping to
1586    * Device Space (DS) and passing it on to the outline consumer.
1587    *
1588    */
1589   FT_LOCAL_DEF( void )
1590   cf2_glyphpath_moveTo( CF2_GlyphPath  glyphpath,
1591                         CF2_Fixed      x,
1592                         CF2_Fixed      y )
1593   {
1594     cf2_glyphpath_closeOpenPath( glyphpath );
1595
1596     /* save the parameters of the move for later, when we'll know how to */
1597     /* offset it;                                                        */
1598     /* also save last move point */
1599     glyphpath->currentCS.x = glyphpath->start.x = x;
1600     glyphpath->currentCS.y = glyphpath->start.y = y;
1601
1602     glyphpath->moveIsPending = TRUE;
1603
1604     /* ensure we have a valid map with current mask */
1605     if ( !cf2_hintmap_isValid( &glyphpath->hintMap ) ||
1606          cf2_hintmask_isNew( glyphpath->hintMask )   )
1607       cf2_hintmap_build( &glyphpath->hintMap,
1608                          glyphpath->hStemHintArray,
1609                          glyphpath->vStemHintArray,
1610                          glyphpath->hintMask,
1611                          glyphpath->hintOriginY,
1612                          FALSE );
1613
1614     /* save a copy of current HintMap to use when drawing initial point */
1615     glyphpath->firstHintMap = glyphpath->hintMap;     /* structure copy */
1616   }
1617
1618
1619   FT_LOCAL_DEF( void )
1620   cf2_glyphpath_lineTo( CF2_GlyphPath  glyphpath,
1621                         CF2_Fixed      x,
1622                         CF2_Fixed      y )
1623   {
1624     CF2_Fixed  xOffset, yOffset;
1625     FT_Vector  P0, P1;
1626     FT_Bool    newHintMap;
1627
1628     /*
1629      * New hints will be applied after cf2_glyphpath_pushPrevElem has run.
1630      * In case this is a synthesized closing line, any new hints should be
1631      * delayed until this path is closed (`cf2_hintmask_isNew' will be
1632      * called again before the next line or curve).
1633      */
1634
1635     /* true if new hint map not on close */
1636     newHintMap = cf2_hintmask_isNew( glyphpath->hintMask ) &&
1637                  !glyphpath->pathIsClosing;
1638
1639     /*
1640      * Zero-length lines may occur in the charstring.  Because we cannot
1641      * compute darkening offsets or intersections from zero-length lines,
1642      * it is best to remove them and avoid artifacts.  However, zero-length
1643      * lines in CS at the start of a new hint map can generate non-zero
1644      * lines in DS due to hint substitution.  We detect a change in hint
1645      * map here and pass those zero-length lines along.
1646      */
1647
1648     /*
1649      * Note: Find explicitly closed paths here with a conditional
1650      *       breakpoint using
1651      *
1652      *         !gp->pathIsClosing && gp->start.x == x && gp->start.y == y
1653      *
1654      */
1655
1656     if ( glyphpath->currentCS.x == x &&
1657          glyphpath->currentCS.y == y &&
1658          !newHintMap                 )
1659       /*
1660        * Ignore zero-length lines in CS where the hint map is the same
1661        * because the line in DS will also be zero length.
1662        *
1663        * Ignore zero-length lines when we synthesize a closing line because
1664        * the close will be handled in cf2_glyphPath_pushPrevElem.
1665        */
1666       return;
1667
1668     cf2_glyphpath_computeOffset( glyphpath,
1669                                  glyphpath->currentCS.x,
1670                                  glyphpath->currentCS.y,
1671                                  x,
1672                                  y,
1673                                  &xOffset,
1674                                  &yOffset );
1675
1676     /* construct offset points */
1677     P0.x = glyphpath->currentCS.x + xOffset;
1678     P0.y = glyphpath->currentCS.y + yOffset;
1679     P1.x = x + xOffset;
1680     P1.y = y + yOffset;
1681
1682     if ( glyphpath->moveIsPending )
1683     {
1684       /* emit offset 1st point as MoveTo */
1685       cf2_glyphpath_pushMove( glyphpath, P0 );
1686
1687       glyphpath->moveIsPending = FALSE;  /* adjust state machine */
1688       glyphpath->pathIsOpen    = TRUE;
1689
1690       glyphpath->offsetStart1 = P1;              /* record second point */
1691     }
1692
1693     if ( glyphpath->elemIsQueued )
1694     {
1695       FT_ASSERT( cf2_hintmap_isValid( &glyphpath->hintMap ) ||
1696                  glyphpath->hintMap.count == 0              );
1697
1698       cf2_glyphpath_pushPrevElem( glyphpath,
1699                                   &glyphpath->hintMap,
1700                                   &P0,
1701                                   P1,
1702                                   FALSE );
1703     }
1704
1705     /* queue the current element with offset points */
1706     glyphpath->elemIsQueued = TRUE;
1707     glyphpath->prevElemOp   = CF2_PathOpLineTo;
1708     glyphpath->prevElemP0   = P0;
1709     glyphpath->prevElemP1   = P1;
1710
1711     /* update current map */
1712     if ( newHintMap )
1713       cf2_hintmap_build( &glyphpath->hintMap,
1714                          glyphpath->hStemHintArray,
1715                          glyphpath->vStemHintArray,
1716                          glyphpath->hintMask,
1717                          glyphpath->hintOriginY,
1718                          FALSE );
1719
1720     glyphpath->currentCS.x = x;     /* pre-offset current point */
1721     glyphpath->currentCS.y = y;
1722   }
1723
1724
1725   FT_LOCAL_DEF( void )
1726   cf2_glyphpath_curveTo( CF2_GlyphPath  glyphpath,
1727                          CF2_Fixed      x1,
1728                          CF2_Fixed      y1,
1729                          CF2_Fixed      x2,
1730                          CF2_Fixed      y2,
1731                          CF2_Fixed      x3,
1732                          CF2_Fixed      y3 )
1733   {
1734     CF2_Fixed  xOffset1, yOffset1, xOffset3, yOffset3;
1735     FT_Vector  P0, P1, P2, P3;
1736
1737
1738     /* TODO: ignore zero length portions of curve?? */
1739     cf2_glyphpath_computeOffset( glyphpath,
1740                                  glyphpath->currentCS.x,
1741                                  glyphpath->currentCS.y,
1742                                  x1,
1743                                  y1,
1744                                  &xOffset1,
1745                                  &yOffset1 );
1746     cf2_glyphpath_computeOffset( glyphpath,
1747                                  x2,
1748                                  y2,
1749                                  x3,
1750                                  y3,
1751                                  &xOffset3,
1752                                  &yOffset3 );
1753
1754     /* add momentum from the middle segment */
1755     glyphpath->callbacks->windingMomentum +=
1756       cf2_getWindingMomentum( x1, y1, x2, y2 );
1757
1758     /* construct offset points */
1759     P0.x = glyphpath->currentCS.x + xOffset1;
1760     P0.y = glyphpath->currentCS.y + yOffset1;
1761     P1.x = x1 + xOffset1;
1762     P1.y = y1 + yOffset1;
1763     /* note: preserve angle of final segment by using offset3 at both ends */
1764     P2.x = x2 + xOffset3;
1765     P2.y = y2 + yOffset3;
1766     P3.x = x3 + xOffset3;
1767     P3.y = y3 + yOffset3;
1768
1769     if ( glyphpath->moveIsPending )
1770     {
1771       /* emit offset 1st point as MoveTo */
1772       cf2_glyphpath_pushMove( glyphpath, P0 );
1773
1774       glyphpath->moveIsPending = FALSE;
1775       glyphpath->pathIsOpen    = TRUE;
1776
1777       glyphpath->offsetStart1 = P1;              /* record second point */
1778     }
1779
1780     if ( glyphpath->elemIsQueued )
1781     {
1782       FT_ASSERT( cf2_hintmap_isValid( &glyphpath->hintMap ) ||
1783                  glyphpath->hintMap.count == 0              );
1784
1785       cf2_glyphpath_pushPrevElem( glyphpath,
1786                                   &glyphpath->hintMap,
1787                                   &P0,
1788                                   P1,
1789                                   FALSE );
1790     }
1791
1792     /* queue the current element with offset points */
1793     glyphpath->elemIsQueued = TRUE;
1794     glyphpath->prevElemOp   = CF2_PathOpCubeTo;
1795     glyphpath->prevElemP0   = P0;
1796     glyphpath->prevElemP1   = P1;
1797     glyphpath->prevElemP2   = P2;
1798     glyphpath->prevElemP3   = P3;
1799
1800     /* update current map */
1801     if ( cf2_hintmask_isNew( glyphpath->hintMask ) )
1802       cf2_hintmap_build( &glyphpath->hintMap,
1803                          glyphpath->hStemHintArray,
1804                          glyphpath->vStemHintArray,
1805                          glyphpath->hintMask,
1806                          glyphpath->hintOriginY,
1807                          FALSE );
1808
1809     glyphpath->currentCS.x = x3;       /* pre-offset current point */
1810     glyphpath->currentCS.y = y3;
1811   }
1812
1813
1814   FT_LOCAL_DEF( void )
1815   cf2_glyphpath_closeOpenPath( CF2_GlyphPath  glyphpath )
1816   {
1817     if ( glyphpath->pathIsOpen )
1818     {
1819       /*
1820        * A closing line in Character Space line is always generated below
1821        * with `cf2_glyphPath_lineTo'.  It may be ignored later if it turns
1822        * out to be zero length in Device Space.
1823        */
1824       glyphpath->pathIsClosing = TRUE;
1825
1826       cf2_glyphpath_lineTo( glyphpath,
1827                             glyphpath->start.x,
1828                             glyphpath->start.y );
1829
1830       /* empty the final element from the queue and close the path */
1831       if ( glyphpath->elemIsQueued )
1832         cf2_glyphpath_pushPrevElem( glyphpath,
1833                                     &glyphpath->hintMap,
1834                                     &glyphpath->offsetStart0,
1835                                     glyphpath->offsetStart1,
1836                                     TRUE );
1837
1838       /* reset state machine */
1839       glyphpath->moveIsPending = TRUE;
1840       glyphpath->pathIsOpen    = FALSE;
1841       glyphpath->pathIsClosing = FALSE;
1842       glyphpath->elemIsQueued  = FALSE;
1843     }
1844   }
1845
1846
1847 /* END */