XFA: merge patch from CL 817753002
[pdfium.git] / core / src / fxge / fx_freetype / fxft2.5.01 / src / cff / cf2hints.c
1 /***************************************************************************/
2 /*                                                                         */
3 /*  cf2hints.c                                                             */
4 /*                                                                         */
5 /*    Adobe's code for handling CFF hints (body).                          */
6 /*                                                                         */
7 /*  Copyright 2007-2013 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 "../../include/freetype/internal/ftdebug.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     FT_ASSERT( hintmap->isValid );  /* must call Build before Map */
308     FT_ASSERT( hintmap->lastIndex < CF2_MAX_HINT_EDGES );
309
310     if ( hintmap->count == 0 || ! hintmap->hinted )
311     {
312       /* there are no hints; use uniform scale and zero offset */
313       return FT_MulFix( csCoord, hintmap->scale );
314     }
315     else
316     {
317       /* start linear search from last hit */
318       CF2_UInt  i = hintmap->lastIndex;
319
320
321       /* search up */
322       while ( i < hintmap->count - 1                  &&
323               csCoord >= hintmap->edge[i + 1].csCoord )
324         i += 1;
325
326       /* search down */
327       while ( i > 0 && csCoord < hintmap->edge[i].csCoord )
328         i -= 1;
329
330       hintmap->lastIndex = i;
331
332       if ( i == 0 && csCoord < hintmap->edge[0].csCoord )
333       {
334         /* special case for points below first edge: use uniform scale */
335         return FT_MulFix( csCoord - hintmap->edge[0].csCoord,
336                           hintmap->scale ) +
337                  hintmap->edge[0].dsCoord;
338       }
339       else
340       {
341         /*
342          * Note: entries with duplicate csCoord are allowed.
343          * Use edge[i], the highest entry where csCoord >= entry[i].csCoord
344          */
345         return FT_MulFix( csCoord - hintmap->edge[i].csCoord,
346                           hintmap->edge[i].scale ) +
347                  hintmap->edge[i].dsCoord;
348       }
349     }
350   }
351
352
353   /*
354    * This hinting policy moves a hint pair in device space so that one of
355    * its two edges is on a device pixel boundary (its fractional part is
356    * zero).  `cf2_hintmap_insertHint' guarantees no overlap in CS
357    * space.  Ensure here that there is no overlap in DS.
358    *
359    * In the first pass, edges are adjusted relative to adjacent hints.
360    * Those that are below have already been adjusted.  Those that are
361    * above have not yet been adjusted.  If a hint above blocks an
362    * adjustment to an optimal position, we will try again in a second
363    * pass.  The second pass is top-down.
364    *
365    */
366
367   static void
368   cf2_hintmap_adjustHints( CF2_HintMap  hintmap )
369   {
370     size_t  i, j;
371
372
373     cf2_arrstack_clear( hintmap->hintMoves );      /* working storage */
374
375     /*
376      * First pass is bottom-up (font hint order) without look-ahead.
377      * Locked edges are already adjusted.
378      * Unlocked edges begin with dsCoord from `initialHintMap'.
379      * Save edges that are not optimally adjusted in `hintMoves' array,
380      * and process them in second pass.
381      */
382
383     for ( i = 0; i < hintmap->count; i++ )
384     {
385       FT_Bool  isPair = cf2_hint_isPair( &hintmap->edge[i] );
386
387
388       /* index of upper edge (same value for ghost hint) */
389       j = isPair ? i + 1 : i;
390
391       FT_ASSERT( j < hintmap->count );
392       FT_ASSERT( cf2_hint_isValid( &hintmap->edge[i] ) );
393       FT_ASSERT( cf2_hint_isValid( &hintmap->edge[j] ) );
394       FT_ASSERT( cf2_hint_isLocked( &hintmap->edge[i] ) ==
395                    cf2_hint_isLocked( &hintmap->edge[j] ) );
396
397       if ( !cf2_hint_isLocked( &hintmap->edge[i] ) )
398       {
399         /* hint edge is not locked, we can adjust it */
400         CF2_Fixed  fracDown = cf2_fixedFraction( hintmap->edge[i].dsCoord );
401         CF2_Fixed  fracUp   = cf2_fixedFraction( hintmap->edge[j].dsCoord );
402
403         /* calculate all four possibilities; moves down are negative */
404         CF2_Fixed  downMoveDown = 0 - fracDown;
405         CF2_Fixed  upMoveDown   = 0 - fracUp;
406         CF2_Fixed  downMoveUp   = fracDown == 0
407                                     ? 0
408                                     : cf2_intToFixed( 1 ) - fracDown;
409         CF2_Fixed  upMoveUp     = fracUp == 0
410                                     ? 0
411                                     : cf2_intToFixed( 1 ) - fracUp;
412
413         /* smallest move up */
414         CF2_Fixed  moveUp   = FT_MIN( downMoveUp, upMoveUp );
415         /* smallest move down */
416         CF2_Fixed  moveDown = FT_MAX( downMoveDown, upMoveDown );
417
418         /* final amount to move edge or edge pair */
419         CF2_Fixed  move;
420
421         CF2_Fixed  downMinCounter = CF2_MIN_COUNTER;
422         CF2_Fixed  upMinCounter   = CF2_MIN_COUNTER;
423         FT_Bool    saveEdge       = FALSE;
424
425
426         /* minimum counter constraint doesn't apply when adjacent edges */
427         /* are synthetic                                                */
428         /* TODO: doesn't seem a big effect; for now, reduce the code    */
429 #if 0
430         if ( i == 0                                        ||
431              cf2_hint_isSynthetic( &hintmap->edge[i - 1] ) )
432           downMinCounter = 0;
433
434         if ( j >= hintmap->count - 1                       ||
435              cf2_hint_isSynthetic( &hintmap->edge[j + 1] ) )
436           upMinCounter = 0;
437 #endif
438
439         /* is there room to move up?                                    */
440         /* there is if we are at top of array or the next edge is at or */
441         /* beyond proposed move up?                                     */
442         if ( j >= hintmap->count - 1                            ||
443              hintmap->edge[j + 1].dsCoord >=
444                hintmap->edge[j].dsCoord + moveUp + upMinCounter )
445         {
446           /* there is room to move up; is there also room to move down? */
447           if ( i == 0                                                 ||
448                hintmap->edge[i - 1].dsCoord <=
449                  hintmap->edge[i].dsCoord + moveDown - downMinCounter )
450           {
451             /* move smaller absolute amount */
452             move = ( -moveDown < moveUp ) ? moveDown : moveUp;  /* optimum */
453           }
454           else
455             move = moveUp;
456         }
457         else
458         {
459           /* is there room to move down? */
460           if ( i == 0                                                 ||
461                hintmap->edge[i - 1].dsCoord <=
462                  hintmap->edge[i].dsCoord + moveDown - downMinCounter )
463           {
464             move     = moveDown;
465             /* true if non-optimum move */
466             saveEdge = (FT_Bool)( moveUp < -moveDown );
467           }
468           else
469           {
470             /* no room to move either way without overlapping or reducing */
471             /* the counter too much                                       */
472             move     = 0;
473             saveEdge = TRUE;
474           }
475         }
476
477         /* Identify non-moves and moves down that aren't optimal, and save */
478         /* them for second pass.                                           */
479         /* Do this only if there is an unlocked edge above (which could    */
480         /* possibly move).                                                 */
481         if ( saveEdge                                    &&
482              j < hintmap->count - 1                      &&
483              !cf2_hint_isLocked( &hintmap->edge[j + 1] ) )
484         {
485           CF2_HintMoveRec  savedMove;
486
487
488           savedMove.j      = j;
489           /* desired adjustment in second pass */
490           savedMove.moveUp = moveUp - move;
491
492           cf2_arrstack_push( hintmap->hintMoves, &savedMove );
493         }
494
495         /* move the edge(s) */
496         hintmap->edge[i].dsCoord += move;
497         if ( isPair )
498           hintmap->edge[j].dsCoord += move;
499       }
500
501       /* assert there are no overlaps in device space */
502       FT_ASSERT( i == 0                                                   ||
503                  hintmap->edge[i - 1].dsCoord <= hintmap->edge[i].dsCoord );
504       FT_ASSERT( i < j                                                ||
505                  hintmap->edge[i].dsCoord <= hintmap->edge[j].dsCoord );
506
507       /* adjust the scales, avoiding divide by zero */
508       if ( i > 0 )
509       {
510         if ( hintmap->edge[i].csCoord != hintmap->edge[i - 1].csCoord )
511           hintmap->edge[i - 1].scale =
512             FT_DivFix(
513               hintmap->edge[i].dsCoord - hintmap->edge[i - 1].dsCoord,
514               hintmap->edge[i].csCoord - hintmap->edge[i - 1].csCoord );
515       }
516
517       if ( isPair )
518       {
519         if ( hintmap->edge[j].csCoord != hintmap->edge[j - 1].csCoord )
520           hintmap->edge[j - 1].scale =
521             FT_DivFix(
522               hintmap->edge[j].dsCoord - hintmap->edge[j - 1].dsCoord,
523               hintmap->edge[j].csCoord - hintmap->edge[j - 1].csCoord );
524
525         i += 1;     /* skip upper edge on next loop */
526       }
527     }
528
529     /* second pass tries to move non-optimal hints up, in case there is */
530     /* room now                                                         */
531     for ( i = cf2_arrstack_size( hintmap->hintMoves ); i > 0; i-- )
532     {
533       CF2_HintMove  hintMove = (CF2_HintMove)
534                       cf2_arrstack_getPointer( hintmap->hintMoves, i - 1 );
535
536
537       j = hintMove->j;
538
539       /* this was tested before the push, above */
540       FT_ASSERT( j < hintmap->count - 1 );
541
542       /* is there room to move up? */
543       if ( hintmap->edge[j + 1].dsCoord >=
544              hintmap->edge[j].dsCoord + hintMove->moveUp + CF2_MIN_COUNTER )
545       {
546         /* there is more room now, move edge up */
547         hintmap->edge[j].dsCoord += hintMove->moveUp;
548
549         if ( cf2_hint_isPair( &hintmap->edge[j] ) )
550         {
551           FT_ASSERT( j > 0 );
552           hintmap->edge[j - 1].dsCoord += hintMove->moveUp;
553         }
554       }
555     }
556   }
557
558
559   /* insert hint edges into map, sorted by csCoord */
560   static void
561   cf2_hintmap_insertHint( CF2_HintMap  hintmap,
562                           CF2_Hint     bottomHintEdge,
563                           CF2_Hint     topHintEdge )
564   {
565     CF2_UInt  indexInsert;
566
567     /* set default values, then check for edge hints */
568     FT_Bool   isPair         = TRUE;
569     CF2_Hint  firstHintEdge  = bottomHintEdge;
570     CF2_Hint  secondHintEdge = topHintEdge;
571
572
573     /* one or none of the input params may be invalid when dealing with */
574     /* edge hints; at least one edge must be valid                      */
575     FT_ASSERT( cf2_hint_isValid( bottomHintEdge ) ||
576                cf2_hint_isValid( topHintEdge )    );
577
578     /* determine how many and which edges to insert */
579     if ( !cf2_hint_isValid( bottomHintEdge ) )
580     {
581       /* insert only the top edge */
582       firstHintEdge = topHintEdge;
583       isPair        = FALSE;
584     }
585     else if ( !cf2_hint_isValid( topHintEdge ) )
586     {
587       /* insert only the bottom edge */
588       isPair = FALSE;
589     }
590
591     /* paired edges must be in proper order */
592     FT_ASSERT( !isPair                                         ||
593                topHintEdge->csCoord >= bottomHintEdge->csCoord );
594
595     /* linear search to find index value of insertion point */
596     indexInsert = 0;
597     for ( ; indexInsert < hintmap->count; indexInsert++ )
598     {
599       if ( hintmap->edge[indexInsert].csCoord > firstHintEdge->csCoord )
600         break;
601     }
602
603     /*
604      * Discard any hints that overlap in character space.  Most often,
605      * this is while building the initial map, but in theory, it can also
606      * occur because of darkening.
607      *
608      */
609     if ( indexInsert < hintmap->count )
610     {
611       /* we are inserting before an existing edge:              */
612       /* verify that a new pair does not straddle the next edge */
613       if ( isPair                                                       &&
614            hintmap->edge[indexInsert].csCoord < secondHintEdge->csCoord )
615         return; /* ignore overlapping stem hint */
616
617       /* verify that we are not inserting between paired edges */
618       if ( cf2_hint_isPairTop( &hintmap->edge[indexInsert] ) )
619         return; /* ignore overlapping stem hint */
620     }
621
622     /* recompute device space locations using initial hint map */
623     if ( cf2_hintmap_isValid( hintmap->initialHintMap ) &&
624          !cf2_hint_isLocked( firstHintEdge )            )
625     {
626       if ( isPair )
627       {
628         /* Use hint map to position the center of stem, and nominal scale */
629         /* to position the two edges.  This preserves the stem width.     */
630         CF2_Fixed  midpoint  = cf2_hintmap_map(
631                                  hintmap->initialHintMap,
632                                  ( secondHintEdge->csCoord +
633                                    firstHintEdge->csCoord ) / 2 );
634         CF2_Fixed  halfWidth = FT_MulFix(
635                                  ( secondHintEdge->csCoord -
636                                    firstHintEdge->csCoord ) / 2,
637                                  hintmap->scale );
638
639
640         firstHintEdge->dsCoord  = midpoint - halfWidth;
641         secondHintEdge->dsCoord = midpoint + halfWidth;
642       }
643       else
644         firstHintEdge->dsCoord = cf2_hintmap_map( hintmap->initialHintMap,
645                                                   firstHintEdge->csCoord );
646     }
647
648     /* discard any hints that overlap in device space; this can occur */
649     /* because locked hints have been moved to align with blue zones  */
650     if ( indexInsert > 0 )
651     {
652       /* we are inserting after an existing edge */
653       if ( firstHintEdge->dsCoord < hintmap->edge[indexInsert - 1].dsCoord )
654         return;
655     }
656
657     if ( indexInsert < hintmap->count )
658     {
659       /* we are inserting before an existing edge */
660       if ( isPair )
661       {
662         if ( secondHintEdge->dsCoord > hintmap->edge[indexInsert].dsCoord )
663           return;
664       }
665       else
666       {
667         if ( firstHintEdge->dsCoord > hintmap->edge[indexInsert].dsCoord )
668           return;
669       }
670     }
671
672     /* make room to insert */
673     {
674       CF2_Int  iSrc = hintmap->count - 1;
675       CF2_Int  iDst = isPair ? hintmap->count + 1 : hintmap->count;
676
677       CF2_Int  count = hintmap->count - indexInsert;
678
679
680       if ( iDst >= CF2_MAX_HINT_EDGES )
681       {
682         FT_TRACE4(( "cf2_hintmap_insertHint: too many hintmaps\n" ));
683         return;
684       }
685
686       while ( count-- )
687         hintmap->edge[iDst--] = hintmap->edge[iSrc--];
688
689       /* insert first edge */
690       hintmap->edge[indexInsert] = *firstHintEdge;         /* copy struct */
691       hintmap->count += 1;
692
693       if ( isPair )
694       {
695         /* insert second edge */
696         hintmap->edge[indexInsert + 1] = *secondHintEdge;  /* copy struct */
697         hintmap->count                += 1;
698       }
699     }
700
701     return;
702   }
703
704
705   /*
706    * Build a map from hints and mask.
707    *
708    * This function may recur one level if `hintmap->initialHintMap' is not yet
709    * valid.
710    * If `initialMap' is true, simply build initial map.
711    *
712    * Synthetic hints are used in two ways.  A hint at zero is inserted, if
713    * needed, in the initial hint map, to prevent translations from
714    * propagating across the origin.  If synthetic em box hints are enabled
715    * for ideographic dictionaries, then they are inserted in all hint
716    * maps, including the initial one.
717    *
718    */
719   FT_LOCAL_DEF( void )
720   cf2_hintmap_build( CF2_HintMap   hintmap,
721                      CF2_ArrStack  hStemHintArray,
722                      CF2_ArrStack  vStemHintArray,
723                      CF2_HintMask  hintMask,
724                      CF2_Fixed     hintOrigin,
725                      FT_Bool       initialMap )
726   {
727     FT_Byte*  maskPtr;
728         FT_Byte*  maskEndPtr;   // add by Xiaochuan_Liu
729
730     CF2_Font         font = hintmap->font;
731     CF2_HintMaskRec  tempHintMask;
732
733     size_t   bitCount, i;
734     FT_Byte  maskByte;
735
736
737     /* check whether initial map is constructed */
738     if ( !initialMap && !cf2_hintmap_isValid( hintmap->initialHintMap ) )
739     {
740       /* make recursive call with initialHintMap and temporary mask; */
741       /* temporary mask will get all bits set, below */
742       cf2_hintmask_init( &tempHintMask, hintMask->error );
743       cf2_hintmap_build( hintmap->initialHintMap,
744                          hStemHintArray,
745                          vStemHintArray,
746                          &tempHintMask,
747                          hintOrigin,
748                          TRUE );
749     }
750
751     if ( !cf2_hintmask_isValid( hintMask ) )
752     {
753       /* without a hint mask, assume all hints are active */
754       cf2_hintmask_setAll( hintMask,
755                            cf2_arrstack_size( hStemHintArray ) +
756                              cf2_arrstack_size( vStemHintArray ) );
757     }
758
759     /* begin by clearing the map */
760     hintmap->count     = 0;
761     hintmap->lastIndex = 0;
762
763     /* make a copy of the hint mask so we can modify it */
764     tempHintMask = *hintMask;
765     maskPtr      = cf2_hintmask_getMaskPtr( &tempHintMask );
766         maskEndPtr   = maskPtr + ( CF2_MAX_HINTS + 7 ) / 8;
767
768
769     /* use the hStem hints only, which are first in the mask */
770     /* TODO: compare this to cffhintmaskGetBitCount */
771     bitCount = cf2_arrstack_size( hStemHintArray );
772
773     /* synthetic embox hints get highest priority */
774     if ( font->blues.doEmBoxHints )
775     {
776       CF2_HintRec  dummy;
777
778
779       cf2_hint_initZero( &dummy );   /* invalid hint map element */
780
781       /* ghost bottom */
782       cf2_hintmap_insertHint( hintmap,
783                               &font->blues.emBoxBottomEdge,
784                               &dummy );
785       /* ghost top */
786       cf2_hintmap_insertHint( hintmap,
787                               &dummy,
788                               &font->blues.emBoxTopEdge );
789     }
790
791     /* insert hints captured by a blue zone or already locked (higher */
792     /* priority)                                                      */
793     for ( i = 0, maskByte = 0x80; i < bitCount; i++ )
794     {
795       if ( maskByte & *maskPtr )
796       {
797         /* expand StemHint into two `CF2_Hint' elements */
798         CF2_HintRec  bottomHintEdge, topHintEdge;
799
800
801         cf2_hint_init( &bottomHintEdge,
802                        hStemHintArray,
803                        i,
804                        font,
805                        hintOrigin,
806                        hintmap->scale,
807                        TRUE /* bottom */ );
808         cf2_hint_init( &topHintEdge,
809                        hStemHintArray,
810                        i,
811                        font,
812                        hintOrigin,
813                        hintmap->scale,
814                        FALSE /* top */ );
815
816         if ( cf2_hint_isLocked( &bottomHintEdge ) ||
817              cf2_hint_isLocked( &topHintEdge )    ||
818              cf2_blues_capture( &font->blues,
819                                 &bottomHintEdge,
820                                 &topHintEdge )   )
821         {
822           /* insert captured hint into map */
823           cf2_hintmap_insertHint( hintmap, &bottomHintEdge, &topHintEdge );
824
825           *maskPtr &= ~maskByte;      /* turn off the bit for this hint */
826         }
827       }
828
829       if ( ( i & 7 ) == 7 )
830       {
831         /* move to next mask byte */
832         maskPtr++;
833                 if (maskPtr >= maskEndPtr)
834                 {
835                         break;
836                 }
837                 
838         maskByte = 0x80;
839       }
840       else
841         maskByte >>= 1;
842     }
843
844     /* initial hint map includes only captured hints plus maybe one at 0 */
845
846     /*
847      * TODO: There is a problem here because we are trying to build a
848      *       single hint map containing all captured hints.  It is
849      *       possible for there to be conflicts between captured hints,
850      *       either because of darkening or because the hints are in
851      *       separate hint zones (we are ignoring hint zones for the
852      *       initial map).  An example of the latter is MinionPro-Regular
853      *       v2.030 glyph 883 (Greek Capital Alpha with Psili) at 15ppem.
854      *       A stem hint for the psili conflicts with the top edge hint
855      *       for the base character.  The stem hint gets priority because
856      *       of its sort order.  In glyph 884 (Greek Capital Alpha with
857      *       Psili and Oxia), the top of the base character gets a stem
858      *       hint, and the psili does not.  This creates different initial
859      *       maps for the two glyphs resulting in different renderings of
860      *       the base character.  Will probably defer this either as not
861      *       worth the cost or as a font bug.  I don't think there is any
862      *       good reason for an accent to be captured by an alignment
863      *       zone.  -darnold 2/12/10
864      */
865
866     if ( initialMap )
867     {
868       /* Apply a heuristic that inserts a point for (0,0), unless it's     */
869       /* already covered by a mapping.  This locks the baseline for glyphs */
870       /* that have no baseline hints.                                      */
871
872       if ( hintmap->count == 0                           ||
873            hintmap->edge[0].csCoord > 0                  ||
874            hintmap->edge[hintmap->count - 1].csCoord < 0 )
875       {
876         /* all edges are above 0 or all edges are below 0; */
877         /* construct a locked edge hint at 0               */
878
879         CF2_HintRec  edge, invalid;
880
881
882         cf2_hint_initZero( &edge );
883
884         edge.flags = CF2_GhostBottom |
885                      CF2_Locked      |
886                      CF2_Synthetic;
887         edge.scale = hintmap->scale;
888
889         cf2_hint_initZero( &invalid );
890         cf2_hintmap_insertHint( hintmap, &edge, &invalid );
891       }
892     }
893     else
894     {
895       /* insert remaining hints */
896
897       maskPtr = cf2_hintmask_getMaskPtr( &tempHintMask );
898           maskEndPtr   = maskPtr + ( CF2_MAX_HINTS + 7 ) / 8;
899
900       for ( i = 0, maskByte = 0x80; i < bitCount; i++ )
901       {
902         if ( maskByte & *maskPtr )
903         {
904           CF2_HintRec  bottomHintEdge, topHintEdge;
905
906
907           cf2_hint_init( &bottomHintEdge,
908                          hStemHintArray,
909                          i,
910                          font,
911                          hintOrigin,
912                          hintmap->scale,
913                          TRUE /* bottom */ );
914           cf2_hint_init( &topHintEdge,
915                          hStemHintArray,
916                          i,
917                          font,
918                          hintOrigin,
919                          hintmap->scale,
920                          FALSE /* top */ );
921
922           cf2_hintmap_insertHint( hintmap, &bottomHintEdge, &topHintEdge );
923         }
924
925         if ( ( i & 7 ) == 7 )
926         {
927           /* move to next mask byte */
928           maskPtr++;
929                   if (maskPtr >= maskEndPtr)
930                   {
931                         break;
932                   }
933           maskByte = 0x80;
934         }
935         else
936           maskByte >>= 1;
937       }
938     }
939
940     /*
941      * Note: The following line is a convenient place to break when
942      *       debugging hinting.  Examine `hintmap->edge' for the list of
943      *       enabled hints, then step over the call to see the effect of
944      *       adjustment.  We stop here first on the recursive call that
945      *       creates the initial map, and then on each counter group and
946      *       hint zone.
947      */
948
949     /* adjust positions of hint edges that are not locked to blue zones */
950     cf2_hintmap_adjustHints( hintmap );
951
952     /* save the position of all hints that were used in this hint map; */
953     /* if we use them again, we'll locate them in the same position    */
954     if ( !initialMap )
955     {
956       for ( i = 0; i < hintmap->count; i++ )
957       {
958         if ( !cf2_hint_isSynthetic( &hintmap->edge[i] ) )
959         {
960           /* Note: include both valid and invalid edges            */
961           /* Note: top and bottom edges are copied back separately */
962           CF2_StemHint  stemhint = (CF2_StemHint)
963                           cf2_arrstack_getPointer( hStemHintArray,
964                                                    hintmap->edge[i].index );
965
966
967           if ( cf2_hint_isTop( &hintmap->edge[i] ) )
968             stemhint->maxDS = hintmap->edge[i].dsCoord;
969           else
970             stemhint->minDS = hintmap->edge[i].dsCoord;
971
972           stemhint->used = TRUE;
973         }
974       }
975     }
976
977     /* hint map is ready to use */
978     hintmap->isValid = TRUE;
979
980     /* remember this mask has been used */
981     cf2_hintmask_setNew( hintMask, FALSE );
982   }
983
984
985   FT_LOCAL_DEF( void )
986   cf2_glyphpath_init( CF2_GlyphPath         glyphpath,
987                       CF2_Font              font,
988                       CF2_OutlineCallbacks  callbacks,
989                       CF2_Fixed             scaleY,
990                       /* CF2_Fixed  hShift, */
991                       CF2_ArrStack          hStemHintArray,
992                       CF2_ArrStack          vStemHintArray,
993                       CF2_HintMask          hintMask,
994                       CF2_Fixed             hintOriginY,
995                       const CF2_Blues       blues,
996                       const FT_Vector*      fractionalTranslation )
997   {
998     FT_ZERO( glyphpath );
999
1000     glyphpath->font      = font;
1001     glyphpath->callbacks = callbacks;
1002
1003     cf2_arrstack_init( &glyphpath->hintMoves,
1004                        font->memory,
1005                        &font->error,
1006                        sizeof ( CF2_HintMoveRec ) );
1007
1008     cf2_hintmap_init( &glyphpath->initialHintMap,
1009                       font,
1010                       &glyphpath->initialHintMap,
1011                       &glyphpath->hintMoves,
1012                       scaleY );
1013     cf2_hintmap_init( &glyphpath->firstHintMap,
1014                       font,
1015                       &glyphpath->initialHintMap,
1016                       &glyphpath->hintMoves,
1017                       scaleY );
1018     cf2_hintmap_init( &glyphpath->hintMap,
1019                       font,
1020                       &glyphpath->initialHintMap,
1021                       &glyphpath->hintMoves,
1022                       scaleY );
1023
1024     glyphpath->scaleX = font->innerTransform.a;
1025     glyphpath->scaleC = font->innerTransform.c;
1026     glyphpath->scaleY = font->innerTransform.d;
1027
1028     glyphpath->fractionalTranslation = *fractionalTranslation;
1029
1030 #if 0
1031     glyphpath->hShift = hShift;       /* for fauxing */
1032 #endif
1033
1034     glyphpath->hStemHintArray = hStemHintArray;
1035     glyphpath->vStemHintArray = vStemHintArray;
1036     glyphpath->hintMask       = hintMask;      /* ptr to current mask */
1037     glyphpath->hintOriginY    = hintOriginY;
1038     glyphpath->blues          = blues;
1039     glyphpath->darken         = font->darkened; /* TODO: should we make copies? */
1040     glyphpath->xOffset        = font->darkenX;
1041     glyphpath->yOffset        = font->darkenY;
1042     glyphpath->miterLimit     = 2 * FT_MAX(
1043                                      cf2_fixedAbs( glyphpath->xOffset ),
1044                                      cf2_fixedAbs( glyphpath->yOffset ) );
1045
1046     /* .1 character space unit */
1047     glyphpath->snapThreshold = cf2_floatToFixed( 0.1f );
1048
1049     glyphpath->moveIsPending = TRUE;
1050     glyphpath->pathIsOpen    = FALSE;
1051     glyphpath->elemIsQueued  = FALSE;
1052   }
1053
1054
1055   FT_LOCAL_DEF( void )
1056   cf2_glyphpath_finalize( CF2_GlyphPath  glyphpath )
1057   {
1058     cf2_arrstack_finalize( &glyphpath->hintMoves );
1059   }
1060
1061
1062   /*
1063    * Hint point in y-direction and apply outerTransform.
1064    * Input `current' hint map (which is actually delayed by one element).
1065    * Input x,y point in Character Space.
1066    * Output x,y point in Device Space, including translation.
1067    */
1068   static void
1069   cf2_glyphpath_hintPoint( CF2_GlyphPath  glyphpath,
1070                            CF2_HintMap    hintmap,
1071                            FT_Vector*     ppt,
1072                            CF2_Fixed      x,
1073                            CF2_Fixed      y )
1074   {
1075     FT_Vector  pt;   /* hinted point in upright DS */
1076
1077
1078     pt.x = FT_MulFix( glyphpath->scaleX, x ) +
1079              FT_MulFix( glyphpath->scaleC, y );
1080     pt.y = cf2_hintmap_map( hintmap, y );
1081
1082     ppt->x = FT_MulFix( glyphpath->font->outerTransform.a, pt.x )   +
1083                FT_MulFix( glyphpath->font->outerTransform.c, pt.y ) +
1084                glyphpath->fractionalTranslation.x;
1085     ppt->y = FT_MulFix( glyphpath->font->outerTransform.b, pt.x )   +
1086                FT_MulFix( glyphpath->font->outerTransform.d, pt.y ) +
1087                glyphpath->fractionalTranslation.y;
1088   }
1089
1090
1091   /*
1092    * From two line segments, (u1,u2) and (v1,v2), compute a point of
1093    * intersection on the corresponding lines.
1094    * Return false if no intersection is found, or if the intersection is
1095    * too far away from the ends of the line segments, u2 and v1.
1096    *
1097    */
1098   static FT_Bool
1099   cf2_glyphpath_computeIntersection( CF2_GlyphPath     glyphpath,
1100                                      const FT_Vector*  u1,
1101                                      const FT_Vector*  u2,
1102                                      const FT_Vector*  v1,
1103                                      const FT_Vector*  v2,
1104                                      FT_Vector*        intersection )
1105   {
1106     /*
1107      * Let `u' be a zero-based vector from the first segment, `v' from the
1108      * second segment.
1109      * Let `w 'be the zero-based vector from `u1' to `v1'.
1110      * `perp' is the `perpendicular dot product'; see
1111      * http://mathworld.wolfram.com/PerpDotProduct.html.
1112      * `s' is the parameter for the parametric line for the first segment
1113      * (`u').
1114      *
1115      * See notation in
1116      * http://softsurfer.com/Archive/algorithm_0104/algorithm_0104B.htm.
1117      * Calculations are done in 16.16, but must handle the squaring of
1118      * line lengths in character space.  We scale all vectors by 1/32 to
1119      * avoid overflow.  This allows values up to 4095 to be squared.  The
1120      * scale factor cancels in the divide.
1121      *
1122      * TODO: the scale factor could be computed from UnitsPerEm.
1123      *
1124      */
1125
1126 #define cf2_perp( a, b )                                    \
1127           ( FT_MulFix( a.x, b.y ) - FT_MulFix( a.y, b.x ) )
1128
1129   /* round and divide by 32 */
1130 #define CF2_CS_SCALE( x )         \
1131           ( ( (x) + 0x10 ) >> 5 )
1132
1133     FT_Vector  u, v, w;      /* scaled vectors */
1134     CF2_Fixed  denominator, s;
1135
1136
1137     u.x = CF2_CS_SCALE( u2->x - u1->x );
1138     u.y = CF2_CS_SCALE( u2->y - u1->y );
1139     v.x = CF2_CS_SCALE( v2->x - v1->x );
1140     v.y = CF2_CS_SCALE( v2->y - v1->y );
1141     w.x = CF2_CS_SCALE( v1->x - u1->x );
1142     w.y = CF2_CS_SCALE( v1->y - u1->y );
1143
1144     denominator = cf2_perp( u, v );
1145
1146     if ( denominator == 0 )
1147       return FALSE;           /* parallel or coincident lines */
1148
1149     s = FT_DivFix( cf2_perp( w, v ), denominator );
1150
1151     intersection->x = u1->x + FT_MulFix( s, u2->x - u1->x );
1152     intersection->y = u1->y + FT_MulFix( s, u2->y - u1->y );
1153
1154     /*
1155      * Special case snapping for horizontal and vertical lines.
1156      * This cleans up intersections and reduces problems with winding
1157      * order detection.
1158      * Sample case is sbc cd KozGoPr6N-Medium.otf 20 16685.
1159      * Note: these calculations are in character space.
1160      *
1161      */
1162
1163     if ( u1->x == u2->x                                                     &&
1164          cf2_fixedAbs( intersection->x - u1->x ) < glyphpath->snapThreshold )
1165       intersection->x = u1->x;
1166     if ( u1->y == u2->y                                                     &&
1167          cf2_fixedAbs( intersection->y - u1->y ) < glyphpath->snapThreshold )
1168       intersection->y = u1->y;
1169
1170     if ( v1->x == v2->x                                                     &&
1171          cf2_fixedAbs( intersection->x - v1->x ) < glyphpath->snapThreshold )
1172       intersection->x = v1->x;
1173     if ( v1->y == v2->y                                                     &&
1174          cf2_fixedAbs( intersection->y - v1->y ) < glyphpath->snapThreshold )
1175       intersection->y = v1->y;
1176
1177     /* limit the intersection distance from midpoint of u2 and v1 */
1178     if ( cf2_fixedAbs( intersection->x - ( u2->x + v1->x ) / 2 ) >
1179            glyphpath->miterLimit                                   ||
1180          cf2_fixedAbs( intersection->y - ( u2->y + v1->y ) / 2 ) >
1181            glyphpath->miterLimit                                   )
1182       return FALSE;
1183
1184     return TRUE;
1185   }
1186
1187
1188   /*
1189    * Push the cached element (glyphpath->prevElem*) to the outline
1190    * consumer.  When a darkening offset is used, the end point of the
1191    * cached element may be adjusted to an intersection point or it may be
1192    * connected by a line to the current element.  This calculation must
1193    * use a HintMap that was valid at the time the element was saved.  For
1194    * the first point in a subpath, that is a saved HintMap.  For most
1195    * elements, it just means the caller has delayed building a HintMap
1196    * from the current HintMask.
1197    *
1198    * Transform each point with outerTransform and call the outline
1199    * callbacks.  This is a general 3x3 transform:
1200    *
1201    *   x' = a*x + c*y + tx, y' = b*x + d*y + ty
1202    *
1203    * but it uses 4 elements from CF2_Font and the translation part
1204    * from CF2_GlyphPath.
1205    *
1206    */
1207   static void
1208   cf2_glyphpath_pushPrevElem( CF2_GlyphPath  glyphpath,
1209                               CF2_HintMap    hintmap,
1210                               FT_Vector*     nextP0,
1211                               FT_Vector      nextP1,
1212                               FT_Bool        close )
1213   {
1214     CF2_CallbackParamsRec  params;
1215
1216     FT_Vector*  prevP0;
1217     FT_Vector*  prevP1;
1218
1219     FT_Vector  intersection    = { 0, 0 };
1220     FT_Bool    useIntersection = FALSE;
1221
1222
1223     FT_ASSERT( glyphpath->prevElemOp == CF2_PathOpLineTo ||
1224                glyphpath->prevElemOp == CF2_PathOpCubeTo );
1225
1226     if ( glyphpath->prevElemOp == CF2_PathOpLineTo )
1227     {
1228       prevP0 = &glyphpath->prevElemP0;
1229       prevP1 = &glyphpath->prevElemP1;
1230     }
1231     else
1232     {
1233       prevP0 = &glyphpath->prevElemP2;
1234       prevP1 = &glyphpath->prevElemP3;
1235     }
1236
1237     /* optimization: if previous and next elements are offset by the same */
1238     /* amount, then there will be no gap, and no need to compute an       */
1239     /* intersection.                                                      */
1240     if ( prevP1->x != nextP0->x || prevP1->y != nextP0->y )
1241     {
1242       /* previous element does not join next element:             */
1243       /* adjust end point of previous element to the intersection */
1244       useIntersection = cf2_glyphpath_computeIntersection( glyphpath,
1245                                                            prevP0,
1246                                                            prevP1,
1247                                                            nextP0,
1248                                                            &nextP1,
1249                                                            &intersection );
1250       if ( useIntersection )
1251       {
1252         /* modify the last point of the cached element (either line or */
1253         /* curve)                                                      */
1254         *prevP1 = intersection;
1255       }
1256     }
1257
1258     params.pt0 = glyphpath->currentDS;
1259
1260     switch( glyphpath->prevElemOp )
1261     {
1262     case CF2_PathOpLineTo:
1263       params.op = CF2_PathOpLineTo;
1264
1265       /* note: pt2 and pt3 are unused */
1266       cf2_glyphpath_hintPoint( glyphpath,
1267                                hintmap,
1268                                &params.pt1,
1269                                glyphpath->prevElemP1.x,
1270                                glyphpath->prevElemP1.y );
1271
1272       glyphpath->callbacks->lineTo( glyphpath->callbacks, &params );
1273
1274       glyphpath->currentDS = params.pt1;
1275
1276       break;
1277
1278     case CF2_PathOpCubeTo:
1279       params.op = CF2_PathOpCubeTo;
1280
1281       /* TODO: should we intersect the interior joins (p1-p2 and p2-p3)? */
1282       cf2_glyphpath_hintPoint( glyphpath,
1283                                hintmap,
1284                                &params.pt1,
1285                                glyphpath->prevElemP1.x,
1286                                glyphpath->prevElemP1.y );
1287       cf2_glyphpath_hintPoint( glyphpath,
1288                                hintmap,
1289                                &params.pt2,
1290                                glyphpath->prevElemP2.x,
1291                                glyphpath->prevElemP2.y );
1292       cf2_glyphpath_hintPoint( glyphpath,
1293                                hintmap,
1294                                &params.pt3,
1295                                glyphpath->prevElemP3.x,
1296                                glyphpath->prevElemP3.y );
1297
1298       glyphpath->callbacks->cubeTo( glyphpath->callbacks, &params );
1299
1300       glyphpath->currentDS = params.pt3;
1301
1302       break;
1303     }
1304
1305     if ( !useIntersection || close )
1306     {
1307       /* insert connecting line between end of previous element and start */
1308       /* of current one                                                   */
1309       /* note: at the end of a subpath, we might do both, so use `nextP0' */
1310       /* before we change it, below                                       */
1311
1312       cf2_glyphpath_hintPoint( glyphpath,
1313                                hintmap,
1314                                &params.pt1,
1315                                nextP0->x,
1316                                nextP0->y );
1317
1318       if ( params.pt1.x != glyphpath->currentDS.x ||
1319            params.pt1.y != glyphpath->currentDS.y )
1320       {
1321         /* length is nonzero */
1322         params.op  = CF2_PathOpLineTo;
1323         params.pt0 = glyphpath->currentDS;
1324
1325         /* note: pt2 and pt3 are unused */
1326         glyphpath->callbacks->lineTo( glyphpath->callbacks, &params );
1327
1328         glyphpath->currentDS = params.pt1;
1329       }
1330     }
1331
1332     if ( useIntersection )
1333     {
1334       /* return intersection point to caller */
1335       *nextP0 = intersection;
1336     }
1337   }
1338
1339
1340   /* push a MoveTo element based on current point and offset of current */
1341   /* element                                                            */
1342   static void
1343   cf2_glyphpath_pushMove( CF2_GlyphPath  glyphpath,
1344                           FT_Vector      start )
1345   {
1346     CF2_CallbackParamsRec  params;
1347
1348
1349     params.op  = CF2_PathOpMoveTo;
1350     params.pt0 = glyphpath->currentDS;
1351
1352     /* Test if move has really happened yet; it would have called */
1353     /* `cf2_hintmap_build' to set `isValid'.                   */
1354     if ( !cf2_hintmap_isValid( &glyphpath->hintMap ) )
1355     {
1356       /* we are here iff first subpath is missing a moveto operator: */
1357       /* synthesize first moveTo to finish initialization of hintMap */
1358       cf2_glyphpath_moveTo( glyphpath,
1359                             glyphpath->start.x,
1360                             glyphpath->start.y );
1361     }
1362
1363     cf2_glyphpath_hintPoint( glyphpath,
1364                              &glyphpath->hintMap,
1365                              &params.pt1,
1366                              start.x,
1367                              start.y );
1368
1369     /* note: pt2 and pt3 are unused */
1370     glyphpath->callbacks->moveTo( glyphpath->callbacks, &params );
1371
1372     glyphpath->currentDS    = params.pt1;
1373     glyphpath->offsetStart0 = start;
1374   }
1375
1376
1377   /*
1378    * All coordinates are in character space.
1379    * On input, (x1, y1) and (x2, y2) give line segment.
1380    * On output, (x, y) give offset vector.
1381    * We use a piecewise approximation to trig functions.
1382    *
1383    * TODO: Offset true perpendicular and proper length
1384    *       supply the y-translation for hinting here, too,
1385    *       that adds yOffset unconditionally to *y.
1386    */
1387   static void
1388   cf2_glyphpath_computeOffset( CF2_GlyphPath  glyphpath,
1389                                CF2_Fixed      x1,
1390                                CF2_Fixed      y1,
1391                                CF2_Fixed      x2,
1392                                CF2_Fixed      y2,
1393                                CF2_Fixed*     x,
1394                                CF2_Fixed*     y )
1395   {
1396     CF2_Fixed  dx = x2 - x1;
1397     CF2_Fixed  dy = y2 - y1;
1398
1399
1400     /* note: negative offsets don't work here; negate deltas to change */
1401     /* quadrants, below                                                */
1402     if ( glyphpath->font->reverseWinding )
1403     {
1404       dx = -dx;
1405       dy = -dy;
1406     }
1407
1408     *x = *y = 0;
1409
1410     if ( !glyphpath->darken )
1411         return;
1412
1413     /* add momentum for this path element */
1414     glyphpath->callbacks->windingMomentum +=
1415       cf2_getWindingMomentum( x1, y1, x2, y2 );
1416
1417     /* note: allow mixed integer and fixed multiplication here */
1418     if ( dx >= 0 )
1419     {
1420       if ( dy >= 0 )
1421       {
1422         /* first quadrant, +x +y */
1423
1424         if ( dx > 2 * dy )
1425         {
1426           /* +x */
1427           *x = 0;
1428           *y = 0;
1429         }
1430         else if ( dy > 2 * dx )
1431         {
1432           /* +y */
1433           *x = glyphpath->xOffset;
1434           *y = glyphpath->yOffset;
1435         }
1436         else
1437         {
1438           /* +x +y */
1439           *x = FT_MulFix( cf2_floatToFixed( 0.7 ),
1440                           glyphpath->xOffset );
1441           *y = FT_MulFix( cf2_floatToFixed( 1.0 - 0.7 ),
1442                           glyphpath->yOffset );
1443         }
1444       }
1445       else
1446       {
1447         /* fourth quadrant, +x -y */
1448
1449         if ( dx > -2 * dy )
1450         {
1451           /* +x */
1452           *x = 0;
1453           *y = 0;
1454         }
1455         else if ( -dy > 2 * dx )
1456         {
1457           /* -y */
1458           *x = -glyphpath->xOffset;
1459           *y = glyphpath->yOffset;
1460         }
1461         else
1462         {
1463           /* +x -y */
1464           *x = FT_MulFix( cf2_floatToFixed( -0.7 ),
1465                           glyphpath->xOffset );
1466           *y = FT_MulFix( cf2_floatToFixed( 1.0 - 0.7 ),
1467                           glyphpath->yOffset );
1468         }
1469       }
1470     }
1471     else
1472     {
1473       if ( dy >= 0 )
1474       {
1475         /* second quadrant, -x +y */
1476
1477         if ( -dx > 2 * dy )
1478         {
1479           /* -x */
1480           *x = 0;
1481           *y = 2 * glyphpath->yOffset;
1482         }
1483         else if ( dy > -2 * dx )
1484         {
1485           /* +y */
1486           *x = glyphpath->xOffset;
1487           *y = glyphpath->yOffset;
1488         }
1489         else
1490         {
1491           /* -x +y */
1492           *x = FT_MulFix( cf2_floatToFixed( 0.7 ),
1493                           glyphpath->xOffset );
1494           *y = FT_MulFix( cf2_floatToFixed( 1.0 + 0.7 ),
1495                           glyphpath->yOffset );
1496         }
1497       }
1498       else
1499       {
1500         /* third quadrant, -x -y */
1501
1502         if ( -dx > -2 * dy )
1503         {
1504           /* -x */
1505           *x = 0;
1506           *y = 2 * glyphpath->yOffset;
1507         }
1508         else if ( -dy > -2 * dx )
1509         {
1510           /* -y */
1511           *x = -glyphpath->xOffset;
1512           *y = glyphpath->xOffset;
1513         }
1514         else
1515         {
1516           /* -x -y */
1517           *x = FT_MulFix( cf2_floatToFixed( -0.7 ),
1518                           glyphpath->xOffset );
1519           *y = FT_MulFix( cf2_floatToFixed( 1.0 + 0.7 ),
1520                           glyphpath->yOffset );
1521         }
1522       }
1523     }
1524   }
1525
1526
1527   FT_LOCAL_DEF( void )
1528   cf2_glyphpath_moveTo( CF2_GlyphPath  glyphpath,
1529                         CF2_Fixed      x,
1530                         CF2_Fixed      y )
1531   {
1532     cf2_glyphpath_closeOpenPath( glyphpath );
1533
1534     /* save the parameters of the move for later, when we'll know how to */
1535     /* offset it;                                                        */
1536     /* also save last move point */
1537     glyphpath->currentCS.x = glyphpath->start.x = x;
1538     glyphpath->currentCS.y = glyphpath->start.y = y;
1539
1540     glyphpath->moveIsPending = TRUE;
1541
1542     /* ensure we have a valid map with current mask */
1543     if ( !cf2_hintmap_isValid( &glyphpath->hintMap ) ||
1544          cf2_hintmask_isNew( glyphpath->hintMask )   )
1545       cf2_hintmap_build( &glyphpath->hintMap,
1546                          glyphpath->hStemHintArray,
1547                          glyphpath->vStemHintArray,
1548                          glyphpath->hintMask,
1549                          glyphpath->hintOriginY,
1550                          FALSE );
1551
1552     /* save a copy of current HintMap to use when drawing initial point */
1553     glyphpath->firstHintMap = glyphpath->hintMap;     /* structure copy */
1554   }
1555
1556
1557   FT_LOCAL_DEF( void )
1558   cf2_glyphpath_lineTo( CF2_GlyphPath  glyphpath,
1559                         CF2_Fixed      x,
1560                         CF2_Fixed      y )
1561   {
1562     CF2_Fixed  xOffset, yOffset;
1563     FT_Vector  P0, P1;
1564
1565
1566     /* can't compute offset of zero length line, so ignore them */
1567     if ( glyphpath->currentCS.x == x && glyphpath->currentCS.y == y )
1568       return;
1569
1570     cf2_glyphpath_computeOffset( glyphpath,
1571                                  glyphpath->currentCS.x,
1572                                  glyphpath->currentCS.y,
1573                                  x,
1574                                  y,
1575                                  &xOffset,
1576                                  &yOffset );
1577
1578     /* construct offset points */
1579     P0.x = glyphpath->currentCS.x + xOffset;
1580     P0.y = glyphpath->currentCS.y + yOffset;
1581     P1.x = x + xOffset;
1582     P1.y = y + yOffset;
1583
1584     if ( glyphpath->moveIsPending )
1585     {
1586       /* emit offset 1st point as MoveTo */
1587       cf2_glyphpath_pushMove( glyphpath, P0 );
1588           if (glyphpath->callbacks && glyphpath->callbacks->error && *glyphpath->callbacks->error) return;
1589
1590       glyphpath->moveIsPending = FALSE;  /* adjust state machine */
1591       glyphpath->pathIsOpen    = TRUE;
1592
1593       glyphpath->offsetStart1 = P1;              /* record second point */
1594     }
1595
1596     if ( glyphpath->elemIsQueued )
1597     {
1598       FT_ASSERT( cf2_hintmap_isValid( &glyphpath->hintMap ) );
1599
1600       cf2_glyphpath_pushPrevElem( glyphpath,
1601                                   &glyphpath->hintMap,
1602                                   &P0,
1603                                   P1,
1604                                   FALSE );
1605           if (glyphpath->callbacks && glyphpath->callbacks->error && *glyphpath->callbacks->error) return;
1606     }
1607
1608     /* queue the current element with offset points */
1609     glyphpath->elemIsQueued = TRUE;
1610     glyphpath->prevElemOp   = CF2_PathOpLineTo;
1611     glyphpath->prevElemP0   = P0;
1612     glyphpath->prevElemP1   = P1;
1613
1614     /* update current map */
1615     if ( cf2_hintmask_isNew( glyphpath->hintMask ) )
1616       cf2_hintmap_build( &glyphpath->hintMap,
1617                          glyphpath->hStemHintArray,
1618                          glyphpath->vStemHintArray,
1619                          glyphpath->hintMask,
1620                          glyphpath->hintOriginY,
1621                          FALSE );
1622
1623     glyphpath->currentCS.x = x;     /* pre-offset current point */
1624     glyphpath->currentCS.y = y;
1625   }
1626
1627
1628   FT_LOCAL_DEF( void )
1629   cf2_glyphpath_curveTo( CF2_GlyphPath  glyphpath,
1630                          CF2_Fixed      x1,
1631                          CF2_Fixed      y1,
1632                          CF2_Fixed      x2,
1633                          CF2_Fixed      y2,
1634                          CF2_Fixed      x3,
1635                          CF2_Fixed      y3 )
1636   {
1637     CF2_Fixed  xOffset1, yOffset1, xOffset3, yOffset3;
1638     FT_Vector  P0, P1, P2, P3;
1639
1640
1641     /* TODO: ignore zero length portions of curve?? */
1642     cf2_glyphpath_computeOffset( glyphpath,
1643                                  glyphpath->currentCS.x,
1644                                  glyphpath->currentCS.y,
1645                                  x1,
1646                                  y1,
1647                                  &xOffset1,
1648                                  &yOffset1 );
1649     cf2_glyphpath_computeOffset( glyphpath,
1650                                  x2,
1651                                  y2,
1652                                  x3,
1653                                  y3,
1654                                  &xOffset3,
1655                                  &yOffset3 );
1656
1657     /* add momentum from the middle segment */
1658     glyphpath->callbacks->windingMomentum +=
1659       cf2_getWindingMomentum( x1, y1, x2, y2 );
1660
1661     /* construct offset points */
1662     P0.x = glyphpath->currentCS.x + xOffset1;
1663     P0.y = glyphpath->currentCS.y + yOffset1;
1664     P1.x = x1 + xOffset1;
1665     P1.y = y1 + yOffset1;
1666     /* note: preserve angle of final segment by using offset3 at both ends */
1667     P2.x = x2 + xOffset3;
1668     P2.y = y2 + yOffset3;
1669     P3.x = x3 + xOffset3;
1670     P3.y = y3 + yOffset3;
1671
1672     if ( glyphpath->moveIsPending )
1673     {
1674       /* emit offset 1st point as MoveTo */
1675       cf2_glyphpath_pushMove( glyphpath, P0 );
1676           if (glyphpath->callbacks && glyphpath->callbacks->error && *glyphpath->callbacks->error) return;
1677
1678       glyphpath->moveIsPending = FALSE;
1679       glyphpath->pathIsOpen    = TRUE;
1680
1681       glyphpath->offsetStart1 = P1;              /* record second point */
1682     }
1683
1684     if ( glyphpath->elemIsQueued )
1685     {
1686       FT_ASSERT( cf2_hintmap_isValid( &glyphpath->hintMap ) );
1687
1688       cf2_glyphpath_pushPrevElem( glyphpath,
1689                                   &glyphpath->hintMap,
1690                                   &P0,
1691                                   P1,
1692                                   FALSE );
1693           if (glyphpath->callbacks && glyphpath->callbacks->error && *glyphpath->callbacks->error) return;
1694     }
1695
1696     /* queue the current element with offset points */
1697     glyphpath->elemIsQueued = TRUE;
1698     glyphpath->prevElemOp   = CF2_PathOpCubeTo;
1699     glyphpath->prevElemP0   = P0;
1700     glyphpath->prevElemP1   = P1;
1701     glyphpath->prevElemP2   = P2;
1702     glyphpath->prevElemP3   = P3;
1703
1704     /* update current map */
1705     if ( cf2_hintmask_isNew( glyphpath->hintMask ) )
1706       cf2_hintmap_build( &glyphpath->hintMap,
1707                          glyphpath->hStemHintArray,
1708                          glyphpath->vStemHintArray,
1709                          glyphpath->hintMask,
1710                          glyphpath->hintOriginY,
1711                          FALSE );
1712
1713     glyphpath->currentCS.x = x3;       /* pre-offset current point */
1714     glyphpath->currentCS.y = y3;
1715   }
1716
1717
1718   FT_LOCAL_DEF( void )
1719   cf2_glyphpath_closeOpenPath( CF2_GlyphPath  glyphpath )
1720   {
1721     if ( glyphpath->pathIsOpen )
1722     {
1723       FT_ASSERT( cf2_hintmap_isValid( &glyphpath->firstHintMap ) );
1724
1725       /* since we need to apply an offset to the implicit lineto, we make */
1726       /* it explicit here                                                 */
1727       cf2_glyphpath_lineTo( glyphpath,
1728                             glyphpath->start.x,
1729                             glyphpath->start.y );
1730           if (glyphpath->callbacks && glyphpath->callbacks->error && *glyphpath->callbacks->error) return;
1731
1732       /* Draw previous element (the explicit LineTo we just created,      */
1733       /* above) and connect it to the start point, but with the offset we */
1734       /* saved from the first element.                                    */
1735       /* Use the saved HintMap, too. */
1736       FT_ASSERT( glyphpath->elemIsQueued );
1737
1738       cf2_glyphpath_pushPrevElem( glyphpath,
1739                                   &glyphpath->firstHintMap,
1740                                   &glyphpath->offsetStart0,
1741                                   glyphpath->offsetStart1,
1742                                   TRUE );
1743
1744       /* reset state machine */
1745       glyphpath->moveIsPending = TRUE;
1746       glyphpath->pathIsOpen    = FALSE;
1747       glyphpath->elemIsQueued  = FALSE;
1748     }
1749   }
1750
1751
1752 /* END */