Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | Download | RSS feed

  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 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.     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.  
  729.     CF2_Font         font = hintmap->font;
  730.     CF2_HintMaskRec  tempHintMask;
  731.  
  732.     size_t   bitCount, i;
  733.     FT_Byte  maskByte;
  734.  
  735.  
  736.     /* check whether initial map is constructed */
  737.     if ( !initialMap && !cf2_hintmap_isValid( hintmap->initialHintMap ) )
  738.     {
  739.       /* make recursive call with initialHintMap and temporary mask; */
  740.       /* temporary mask will get all bits set, below */
  741.       cf2_hintmask_init( &tempHintMask, hintMask->error );
  742.       cf2_hintmap_build( hintmap->initialHintMap,
  743.                          hStemHintArray,
  744.                          vStemHintArray,
  745.                          &tempHintMask,
  746.                          hintOrigin,
  747.                          TRUE );
  748.     }
  749.  
  750.     if ( !cf2_hintmask_isValid( hintMask ) )
  751.     {
  752.       /* without a hint mask, assume all hints are active */
  753.       cf2_hintmask_setAll( hintMask,
  754.                            cf2_arrstack_size( hStemHintArray ) +
  755.                              cf2_arrstack_size( vStemHintArray ) );
  756.     }
  757.  
  758.     /* begin by clearing the map */
  759.     hintmap->count     = 0;
  760.     hintmap->lastIndex = 0;
  761.  
  762.     /* make a copy of the hint mask so we can modify it */
  763.     tempHintMask = *hintMask;
  764.     maskPtr      = cf2_hintmask_getMaskPtr( &tempHintMask );
  765.  
  766.     /* use the hStem hints only, which are first in the mask */
  767.     /* TODO: compare this to cffhintmaskGetBitCount */
  768.     bitCount = cf2_arrstack_size( hStemHintArray );
  769.  
  770.     /* synthetic embox hints get highest priority */
  771.     if ( font->blues.doEmBoxHints )
  772.     {
  773.       CF2_HintRec  dummy;
  774.  
  775.  
  776.       cf2_hint_initZero( &dummy );   /* invalid hint map element */
  777.  
  778.       /* ghost bottom */
  779.       cf2_hintmap_insertHint( hintmap,
  780.                               &font->blues.emBoxBottomEdge,
  781.                               &dummy );
  782.       /* ghost top */
  783.       cf2_hintmap_insertHint( hintmap,
  784.                               &dummy,
  785.                               &font->blues.emBoxTopEdge );
  786.     }
  787.  
  788.     /* insert hints captured by a blue zone or already locked (higher */
  789.     /* priority)                                                      */
  790.     for ( i = 0, maskByte = 0x80; i < bitCount; i++ )
  791.     {
  792.       if ( maskByte & *maskPtr )
  793.       {
  794.         /* expand StemHint into two `CF2_Hint' elements */
  795.         CF2_HintRec  bottomHintEdge, topHintEdge;
  796.  
  797.  
  798.         cf2_hint_init( &bottomHintEdge,
  799.                        hStemHintArray,
  800.                        i,
  801.                        font,
  802.                        hintOrigin,
  803.                        hintmap->scale,
  804.                        TRUE /* bottom */ );
  805.         cf2_hint_init( &topHintEdge,
  806.                        hStemHintArray,
  807.                        i,
  808.                        font,
  809.                        hintOrigin,
  810.                        hintmap->scale,
  811.                        FALSE /* top */ );
  812.  
  813.         if ( cf2_hint_isLocked( &bottomHintEdge ) ||
  814.              cf2_hint_isLocked( &topHintEdge )    ||
  815.              cf2_blues_capture( &font->blues,
  816.                                 &bottomHintEdge,
  817.                                 &topHintEdge )   )
  818.         {
  819.           /* insert captured hint into map */
  820.           cf2_hintmap_insertHint( hintmap, &bottomHintEdge, &topHintEdge );
  821.  
  822.           *maskPtr &= ~maskByte;      /* turn off the bit for this hint */
  823.         }
  824.       }
  825.  
  826.       if ( ( i & 7 ) == 7 )
  827.       {
  828.         /* move to next mask byte */
  829.         maskPtr++;
  830.         maskByte = 0x80;
  831.       }
  832.       else
  833.         maskByte >>= 1;
  834.     }
  835.  
  836.     /* initial hint map includes only captured hints plus maybe one at 0 */
  837.  
  838.     /*
  839.      * TODO: There is a problem here because we are trying to build a
  840.      *       single hint map containing all captured hints.  It is
  841.      *       possible for there to be conflicts between captured hints,
  842.      *       either because of darkening or because the hints are in
  843.      *       separate hint zones (we are ignoring hint zones for the
  844.      *       initial map).  An example of the latter is MinionPro-Regular
  845.      *       v2.030 glyph 883 (Greek Capital Alpha with Psili) at 15ppem.
  846.      *       A stem hint for the psili conflicts with the top edge hint
  847.      *       for the base character.  The stem hint gets priority because
  848.      *       of its sort order.  In glyph 884 (Greek Capital Alpha with
  849.      *       Psili and Oxia), the top of the base character gets a stem
  850.      *       hint, and the psili does not.  This creates different initial
  851.      *       maps for the two glyphs resulting in different renderings of
  852.      *       the base character.  Will probably defer this either as not
  853.      *       worth the cost or as a font bug.  I don't think there is any
  854.      *       good reason for an accent to be captured by an alignment
  855.      *       zone.  -darnold 2/12/10
  856.      */
  857.  
  858.     if ( initialMap )
  859.     {
  860.       /* Apply a heuristic that inserts a point for (0,0), unless it's     */
  861.       /* already covered by a mapping.  This locks the baseline for glyphs */
  862.       /* that have no baseline hints.                                      */
  863.  
  864.       if ( hintmap->count == 0                           ||
  865.            hintmap->edge[0].csCoord > 0                  ||
  866.            hintmap->edge[hintmap->count - 1].csCoord < 0 )
  867.       {
  868.         /* all edges are above 0 or all edges are below 0; */
  869.         /* construct a locked edge hint at 0               */
  870.  
  871.         CF2_HintRec  edge, invalid;
  872.  
  873.  
  874.         cf2_hint_initZero( &edge );
  875.  
  876.         edge.flags = CF2_GhostBottom |
  877.                      CF2_Locked      |
  878.                      CF2_Synthetic;
  879.         edge.scale = hintmap->scale;
  880.  
  881.         cf2_hint_initZero( &invalid );
  882.         cf2_hintmap_insertHint( hintmap, &edge, &invalid );
  883.       }
  884.     }
  885.     else
  886.     {
  887.       /* insert remaining hints */
  888.  
  889.       maskPtr = cf2_hintmask_getMaskPtr( &tempHintMask );
  890.  
  891.       for ( i = 0, maskByte = 0x80; i < bitCount; i++ )
  892.       {
  893.         if ( maskByte & *maskPtr )
  894.         {
  895.           CF2_HintRec  bottomHintEdge, topHintEdge;
  896.  
  897.  
  898.           cf2_hint_init( &bottomHintEdge,
  899.                          hStemHintArray,
  900.                          i,
  901.                          font,
  902.                          hintOrigin,
  903.                          hintmap->scale,
  904.                          TRUE /* bottom */ );
  905.           cf2_hint_init( &topHintEdge,
  906.                          hStemHintArray,
  907.                          i,
  908.                          font,
  909.                          hintOrigin,
  910.                          hintmap->scale,
  911.                          FALSE /* top */ );
  912.  
  913.           cf2_hintmap_insertHint( hintmap, &bottomHintEdge, &topHintEdge );
  914.         }
  915.  
  916.         if ( ( i & 7 ) == 7 )
  917.         {
  918.           /* move to next mask byte */
  919.           maskPtr++;
  920.           maskByte = 0x80;
  921.         }
  922.         else
  923.           maskByte >>= 1;
  924.       }
  925.     }
  926.  
  927.     /*
  928.      * Note: The following line is a convenient place to break when
  929.      *       debugging hinting.  Examine `hintmap->edge' for the list of
  930.      *       enabled hints, then step over the call to see the effect of
  931.      *       adjustment.  We stop here first on the recursive call that
  932.      *       creates the initial map, and then on each counter group and
  933.      *       hint zone.
  934.      */
  935.  
  936.     /* adjust positions of hint edges that are not locked to blue zones */
  937.     cf2_hintmap_adjustHints( hintmap );
  938.  
  939.     /* save the position of all hints that were used in this hint map; */
  940.     /* if we use them again, we'll locate them in the same position    */
  941.     if ( !initialMap )
  942.     {
  943.       for ( i = 0; i < hintmap->count; i++ )
  944.       {
  945.         if ( !cf2_hint_isSynthetic( &hintmap->edge[i] ) )
  946.         {
  947.           /* Note: include both valid and invalid edges            */
  948.           /* Note: top and bottom edges are copied back separately */
  949.           CF2_StemHint  stemhint = (CF2_StemHint)
  950.                           cf2_arrstack_getPointer( hStemHintArray,
  951.                                                    hintmap->edge[i].index );
  952.  
  953.  
  954.           if ( cf2_hint_isTop( &hintmap->edge[i] ) )
  955.             stemhint->maxDS = hintmap->edge[i].dsCoord;
  956.           else
  957.             stemhint->minDS = hintmap->edge[i].dsCoord;
  958.  
  959.           stemhint->used = TRUE;
  960.         }
  961.       }
  962.     }
  963.  
  964.     /* hint map is ready to use */
  965.     hintmap->isValid = TRUE;
  966.  
  967.     /* remember this mask has been used */
  968.     cf2_hintmask_setNew( hintMask, FALSE );
  969.   }
  970.  
  971.  
  972.   FT_LOCAL_DEF( void )
  973.   cf2_glyphpath_init( CF2_GlyphPath         glyphpath,
  974.                       CF2_Font              font,
  975.                       CF2_OutlineCallbacks  callbacks,
  976.                       CF2_Fixed             scaleY,
  977.                       /* CF2_Fixed  hShift, */
  978.                       CF2_ArrStack          hStemHintArray,
  979.                       CF2_ArrStack          vStemHintArray,
  980.                       CF2_HintMask          hintMask,
  981.                       CF2_Fixed             hintOriginY,
  982.                       const CF2_Blues       blues,
  983.                       const FT_Vector*      fractionalTranslation )
  984.   {
  985.     FT_ZERO( glyphpath );
  986.  
  987.     glyphpath->font      = font;
  988.     glyphpath->callbacks = callbacks;
  989.  
  990.     cf2_arrstack_init( &glyphpath->hintMoves,
  991.                        font->memory,
  992.                        &font->error,
  993.                        sizeof ( CF2_HintMoveRec ) );
  994.  
  995.     cf2_hintmap_init( &glyphpath->initialHintMap,
  996.                       font,
  997.                       &glyphpath->initialHintMap,
  998.                       &glyphpath->hintMoves,
  999.                       scaleY );
  1000.     cf2_hintmap_init( &glyphpath->firstHintMap,
  1001.                       font,
  1002.                       &glyphpath->initialHintMap,
  1003.                       &glyphpath->hintMoves,
  1004.                       scaleY );
  1005.     cf2_hintmap_init( &glyphpath->hintMap,
  1006.                       font,
  1007.                       &glyphpath->initialHintMap,
  1008.                       &glyphpath->hintMoves,
  1009.                       scaleY );
  1010.  
  1011.     glyphpath->scaleX = font->innerTransform.a;
  1012.     glyphpath->scaleC = font->innerTransform.c;
  1013.     glyphpath->scaleY = font->innerTransform.d;
  1014.  
  1015.     glyphpath->fractionalTranslation = *fractionalTranslation;
  1016.  
  1017. #if 0
  1018.     glyphpath->hShift = hShift;       /* for fauxing */
  1019. #endif
  1020.  
  1021.     glyphpath->hStemHintArray = hStemHintArray;
  1022.     glyphpath->vStemHintArray = vStemHintArray;
  1023.     glyphpath->hintMask       = hintMask;      /* ptr to current mask */
  1024.     glyphpath->hintOriginY    = hintOriginY;
  1025.     glyphpath->blues          = blues;
  1026.     glyphpath->darken         = font->darkened; /* TODO: should we make copies? */
  1027.     glyphpath->xOffset        = font->darkenX;
  1028.     glyphpath->yOffset        = font->darkenY;
  1029.     glyphpath->miterLimit     = 2 * FT_MAX(
  1030.                                      cf2_fixedAbs( glyphpath->xOffset ),
  1031.                                      cf2_fixedAbs( glyphpath->yOffset ) );
  1032.  
  1033.     /* .1 character space unit */
  1034.     glyphpath->snapThreshold = cf2_floatToFixed( 0.1f );
  1035.  
  1036.     glyphpath->moveIsPending = TRUE;
  1037.     glyphpath->pathIsOpen    = FALSE;
  1038.     glyphpath->elemIsQueued  = FALSE;
  1039.   }
  1040.  
  1041.  
  1042.   FT_LOCAL_DEF( void )
  1043.   cf2_glyphpath_finalize( CF2_GlyphPath  glyphpath )
  1044.   {
  1045.     cf2_arrstack_finalize( &glyphpath->hintMoves );
  1046.   }
  1047.  
  1048.  
  1049.   /*
  1050.    * Hint point in y-direction and apply outerTransform.
  1051.    * Input `current' hint map (which is actually delayed by one element).
  1052.    * Input x,y point in Character Space.
  1053.    * Output x,y point in Device Space, including translation.
  1054.    */
  1055.   static void
  1056.   cf2_glyphpath_hintPoint( CF2_GlyphPath  glyphpath,
  1057.                            CF2_HintMap    hintmap,
  1058.                            FT_Vector*     ppt,
  1059.                            CF2_Fixed      x,
  1060.                            CF2_Fixed      y )
  1061.   {
  1062.     FT_Vector  pt;   /* hinted point in upright DS */
  1063.  
  1064.  
  1065.     pt.x = FT_MulFix( glyphpath->scaleX, x ) +
  1066.              FT_MulFix( glyphpath->scaleC, y );
  1067.     pt.y = cf2_hintmap_map( hintmap, y );
  1068.  
  1069.     ppt->x = FT_MulFix( glyphpath->font->outerTransform.a, pt.x )   +
  1070.                FT_MulFix( glyphpath->font->outerTransform.c, pt.y ) +
  1071.                glyphpath->fractionalTranslation.x;
  1072.     ppt->y = FT_MulFix( glyphpath->font->outerTransform.b, pt.x )   +
  1073.                FT_MulFix( glyphpath->font->outerTransform.d, pt.y ) +
  1074.                glyphpath->fractionalTranslation.y;
  1075.   }
  1076.  
  1077.  
  1078.   /*
  1079.    * From two line segments, (u1,u2) and (v1,v2), compute a point of
  1080.    * intersection on the corresponding lines.
  1081.    * Return false if no intersection is found, or if the intersection is
  1082.    * too far away from the ends of the line segments, u2 and v1.
  1083.    *
  1084.    */
  1085.   static FT_Bool
  1086.   cf2_glyphpath_computeIntersection( CF2_GlyphPath     glyphpath,
  1087.                                      const FT_Vector*  u1,
  1088.                                      const FT_Vector*  u2,
  1089.                                      const FT_Vector*  v1,
  1090.                                      const FT_Vector*  v2,
  1091.                                      FT_Vector*        intersection )
  1092.   {
  1093.     /*
  1094.      * Let `u' be a zero-based vector from the first segment, `v' from the
  1095.      * second segment.
  1096.      * Let `w 'be the zero-based vector from `u1' to `v1'.
  1097.      * `perp' is the `perpendicular dot product'; see
  1098.      * http://mathworld.wolfram.com/PerpDotProduct.html.
  1099.      * `s' is the parameter for the parametric line for the first segment
  1100.      * (`u').
  1101.      *
  1102.      * See notation in
  1103.      * http://softsurfer.com/Archive/algorithm_0104/algorithm_0104B.htm.
  1104.      * Calculations are done in 16.16, but must handle the squaring of
  1105.      * line lengths in character space.  We scale all vectors by 1/32 to
  1106.      * avoid overflow.  This allows values up to 4095 to be squared.  The
  1107.      * scale factor cancels in the divide.
  1108.      *
  1109.      * TODO: the scale factor could be computed from UnitsPerEm.
  1110.      *
  1111.      */
  1112.  
  1113. #define cf2_perp( a, b )                                    \
  1114.           ( FT_MulFix( a.x, b.y ) - FT_MulFix( a.y, b.x ) )
  1115.  
  1116.   /* round and divide by 32 */
  1117. #define CF2_CS_SCALE( x )         \
  1118.           ( ( (x) + 0x10 ) >> 5 )
  1119.  
  1120.     FT_Vector  u, v, w;      /* scaled vectors */
  1121.     CF2_Fixed  denominator, s;
  1122.  
  1123.  
  1124.     u.x = CF2_CS_SCALE( u2->x - u1->x );
  1125.     u.y = CF2_CS_SCALE( u2->y - u1->y );
  1126.     v.x = CF2_CS_SCALE( v2->x - v1->x );
  1127.     v.y = CF2_CS_SCALE( v2->y - v1->y );
  1128.     w.x = CF2_CS_SCALE( v1->x - u1->x );
  1129.     w.y = CF2_CS_SCALE( v1->y - u1->y );
  1130.  
  1131.     denominator = cf2_perp( u, v );
  1132.  
  1133.     if ( denominator == 0 )
  1134.       return FALSE;           /* parallel or coincident lines */
  1135.  
  1136.     s = FT_DivFix( cf2_perp( w, v ), denominator );
  1137.  
  1138.     intersection->x = u1->x + FT_MulFix( s, u2->x - u1->x );
  1139.     intersection->y = u1->y + FT_MulFix( s, u2->y - u1->y );
  1140.  
  1141.     /*
  1142.      * Special case snapping for horizontal and vertical lines.
  1143.      * This cleans up intersections and reduces problems with winding
  1144.      * order detection.
  1145.      * Sample case is sbc cd KozGoPr6N-Medium.otf 20 16685.
  1146.      * Note: these calculations are in character space.
  1147.      *
  1148.      */
  1149.  
  1150.     if ( u1->x == u2->x                                                     &&
  1151.          cf2_fixedAbs( intersection->x - u1->x ) < glyphpath->snapThreshold )
  1152.       intersection->x = u1->x;
  1153.     if ( u1->y == u2->y                                                     &&
  1154.          cf2_fixedAbs( intersection->y - u1->y ) < glyphpath->snapThreshold )
  1155.       intersection->y = u1->y;
  1156.  
  1157.     if ( v1->x == v2->x                                                     &&
  1158.          cf2_fixedAbs( intersection->x - v1->x ) < glyphpath->snapThreshold )
  1159.       intersection->x = v1->x;
  1160.     if ( v1->y == v2->y                                                     &&
  1161.          cf2_fixedAbs( intersection->y - v1->y ) < glyphpath->snapThreshold )
  1162.       intersection->y = v1->y;
  1163.  
  1164.     /* limit the intersection distance from midpoint of u2 and v1 */
  1165.     if ( cf2_fixedAbs( intersection->x - ( u2->x + v1->x ) / 2 ) >
  1166.            glyphpath->miterLimit                                   ||
  1167.          cf2_fixedAbs( intersection->y - ( u2->y + v1->y ) / 2 ) >
  1168.            glyphpath->miterLimit                                   )
  1169.       return FALSE;
  1170.  
  1171.     return TRUE;
  1172.   }
  1173.  
  1174.  
  1175.   /*
  1176.    * Push the cached element (glyphpath->prevElem*) to the outline
  1177.    * consumer.  When a darkening offset is used, the end point of the
  1178.    * cached element may be adjusted to an intersection point or it may be
  1179.    * connected by a line to the current element.  This calculation must
  1180.    * use a HintMap that was valid at the time the element was saved.  For
  1181.    * the first point in a subpath, that is a saved HintMap.  For most
  1182.    * elements, it just means the caller has delayed building a HintMap
  1183.    * from the current HintMask.
  1184.    *
  1185.    * Transform each point with outerTransform and call the outline
  1186.    * callbacks.  This is a general 3x3 transform:
  1187.    *
  1188.    *   x' = a*x + c*y + tx, y' = b*x + d*y + ty
  1189.    *
  1190.    * but it uses 4 elements from CF2_Font and the translation part
  1191.    * from CF2_GlyphPath.
  1192.    *
  1193.    */
  1194.   static void
  1195.   cf2_glyphpath_pushPrevElem( CF2_GlyphPath  glyphpath,
  1196.                               CF2_HintMap    hintmap,
  1197.                               FT_Vector*     nextP0,
  1198.                               FT_Vector      nextP1,
  1199.                               FT_Bool        close )
  1200.   {
  1201.     CF2_CallbackParamsRec  params;
  1202.  
  1203.     FT_Vector*  prevP0;
  1204.     FT_Vector*  prevP1;
  1205.  
  1206.     FT_Vector  intersection    = { 0, 0 };
  1207.     FT_Bool    useIntersection = FALSE;
  1208.  
  1209.  
  1210.     FT_ASSERT( glyphpath->prevElemOp == CF2_PathOpLineTo ||
  1211.                glyphpath->prevElemOp == CF2_PathOpCubeTo );
  1212.  
  1213.     if ( glyphpath->prevElemOp == CF2_PathOpLineTo )
  1214.     {
  1215.       prevP0 = &glyphpath->prevElemP0;
  1216.       prevP1 = &glyphpath->prevElemP1;
  1217.     }
  1218.     else
  1219.     {
  1220.       prevP0 = &glyphpath->prevElemP2;
  1221.       prevP1 = &glyphpath->prevElemP3;
  1222.     }
  1223.  
  1224.     /* optimization: if previous and next elements are offset by the same */
  1225.     /* amount, then there will be no gap, and no need to compute an       */
  1226.     /* intersection.                                                      */
  1227.     if ( prevP1->x != nextP0->x || prevP1->y != nextP0->y )
  1228.     {
  1229.       /* previous element does not join next element:             */
  1230.       /* adjust end point of previous element to the intersection */
  1231.       useIntersection = cf2_glyphpath_computeIntersection( glyphpath,
  1232.                                                            prevP0,
  1233.                                                            prevP1,
  1234.                                                            nextP0,
  1235.                                                            &nextP1,
  1236.                                                            &intersection );
  1237.       if ( useIntersection )
  1238.       {
  1239.         /* modify the last point of the cached element (either line or */
  1240.         /* curve)                                                      */
  1241.         *prevP1 = intersection;
  1242.       }
  1243.     }
  1244.  
  1245.     params.pt0 = glyphpath->currentDS;
  1246.  
  1247.     switch( glyphpath->prevElemOp )
  1248.     {
  1249.     case CF2_PathOpLineTo:
  1250.       params.op = CF2_PathOpLineTo;
  1251.  
  1252.       /* note: pt2 and pt3 are unused */
  1253.       cf2_glyphpath_hintPoint( glyphpath,
  1254.                                hintmap,
  1255.                                &params.pt1,
  1256.                                glyphpath->prevElemP1.x,
  1257.                                glyphpath->prevElemP1.y );
  1258.  
  1259.       glyphpath->callbacks->lineTo( glyphpath->callbacks, &params );
  1260.  
  1261.       glyphpath->currentDS = params.pt1;
  1262.  
  1263.       break;
  1264.  
  1265.     case CF2_PathOpCubeTo:
  1266.       params.op = CF2_PathOpCubeTo;
  1267.  
  1268.       /* TODO: should we intersect the interior joins (p1-p2 and p2-p3)? */
  1269.       cf2_glyphpath_hintPoint( glyphpath,
  1270.                                hintmap,
  1271.                                &params.pt1,
  1272.                                glyphpath->prevElemP1.x,
  1273.                                glyphpath->prevElemP1.y );
  1274.       cf2_glyphpath_hintPoint( glyphpath,
  1275.                                hintmap,
  1276.                                &params.pt2,
  1277.                                glyphpath->prevElemP2.x,
  1278.                                glyphpath->prevElemP2.y );
  1279.       cf2_glyphpath_hintPoint( glyphpath,
  1280.                                hintmap,
  1281.                                &params.pt3,
  1282.                                glyphpath->prevElemP3.x,
  1283.                                glyphpath->prevElemP3.y );
  1284.  
  1285.       glyphpath->callbacks->cubeTo( glyphpath->callbacks, &params );
  1286.  
  1287.       glyphpath->currentDS = params.pt3;
  1288.  
  1289.       break;
  1290.     }
  1291.  
  1292.     if ( !useIntersection || close )
  1293.     {
  1294.       /* insert connecting line between end of previous element and start */
  1295.       /* of current one                                                   */
  1296.       /* note: at the end of a subpath, we might do both, so use `nextP0' */
  1297.       /* before we change it, below                                       */
  1298.  
  1299.       cf2_glyphpath_hintPoint( glyphpath,
  1300.                                hintmap,
  1301.                                &params.pt1,
  1302.                                nextP0->x,
  1303.                                nextP0->y );
  1304.  
  1305.       if ( params.pt1.x != glyphpath->currentDS.x ||
  1306.            params.pt1.y != glyphpath->currentDS.y )
  1307.       {
  1308.         /* length is nonzero */
  1309.         params.op  = CF2_PathOpLineTo;
  1310.         params.pt0 = glyphpath->currentDS;
  1311.  
  1312.         /* note: pt2 and pt3 are unused */
  1313.         glyphpath->callbacks->lineTo( glyphpath->callbacks, &params );
  1314.  
  1315.         glyphpath->currentDS = params.pt1;
  1316.       }
  1317.     }
  1318.  
  1319.     if ( useIntersection )
  1320.     {
  1321.       /* return intersection point to caller */
  1322.       *nextP0 = intersection;
  1323.     }
  1324.   }
  1325.  
  1326.  
  1327.   /* push a MoveTo element based on current point and offset of current */
  1328.   /* element                                                            */
  1329.   static void
  1330.   cf2_glyphpath_pushMove( CF2_GlyphPath  glyphpath,
  1331.                           FT_Vector      start )
  1332.   {
  1333.     CF2_CallbackParamsRec  params;
  1334.  
  1335.  
  1336.     params.op  = CF2_PathOpMoveTo;
  1337.     params.pt0 = glyphpath->currentDS;
  1338.  
  1339.     /* Test if move has really happened yet; it would have called */
  1340.     /* `cf2_hintmap_build' to set `isValid'.                   */
  1341.     if ( !cf2_hintmap_isValid( &glyphpath->hintMap ) )
  1342.     {
  1343.       /* we are here iff first subpath is missing a moveto operator: */
  1344.       /* synthesize first moveTo to finish initialization of hintMap */
  1345.       cf2_glyphpath_moveTo( glyphpath,
  1346.                             glyphpath->start.x,
  1347.                             glyphpath->start.y );
  1348.     }
  1349.  
  1350.     cf2_glyphpath_hintPoint( glyphpath,
  1351.                              &glyphpath->hintMap,
  1352.                              &params.pt1,
  1353.                              start.x,
  1354.                              start.y );
  1355.  
  1356.     /* note: pt2 and pt3 are unused */
  1357.     glyphpath->callbacks->moveTo( glyphpath->callbacks, &params );
  1358.  
  1359.     glyphpath->currentDS    = params.pt1;
  1360.     glyphpath->offsetStart0 = start;
  1361.   }
  1362.  
  1363.  
  1364.   /*
  1365.    * All coordinates are in character space.
  1366.    * On input, (x1, y1) and (x2, y2) give line segment.
  1367.    * On output, (x, y) give offset vector.
  1368.    * We use a piecewise approximation to trig functions.
  1369.    *
  1370.    * TODO: Offset true perpendicular and proper length
  1371.    *       supply the y-translation for hinting here, too,
  1372.    *       that adds yOffset unconditionally to *y.
  1373.    */
  1374.   static void
  1375.   cf2_glyphpath_computeOffset( CF2_GlyphPath  glyphpath,
  1376.                                CF2_Fixed      x1,
  1377.                                CF2_Fixed      y1,
  1378.                                CF2_Fixed      x2,
  1379.                                CF2_Fixed      y2,
  1380.                                CF2_Fixed*     x,
  1381.                                CF2_Fixed*     y )
  1382.   {
  1383.     CF2_Fixed  dx = x2 - x1;
  1384.     CF2_Fixed  dy = y2 - y1;
  1385.  
  1386.  
  1387.     /* note: negative offsets don't work here; negate deltas to change */
  1388.     /* quadrants, below                                                */
  1389.     if ( glyphpath->font->reverseWinding )
  1390.     {
  1391.       dx = -dx;
  1392.       dy = -dy;
  1393.     }
  1394.  
  1395.     *x = *y = 0;
  1396.  
  1397.     if ( !glyphpath->darken )
  1398.         return;
  1399.  
  1400.     /* add momentum for this path element */
  1401.     glyphpath->callbacks->windingMomentum +=
  1402.       cf2_getWindingMomentum( x1, y1, x2, y2 );
  1403.  
  1404.     /* note: allow mixed integer and fixed multiplication here */
  1405.     if ( dx >= 0 )
  1406.     {
  1407.       if ( dy >= 0 )
  1408.       {
  1409.         /* first quadrant, +x +y */
  1410.  
  1411.         if ( dx > 2 * dy )
  1412.         {
  1413.           /* +x */
  1414.           *x = 0;
  1415.           *y = 0;
  1416.         }
  1417.         else if ( dy > 2 * dx )
  1418.         {
  1419.           /* +y */
  1420.           *x = glyphpath->xOffset;
  1421.           *y = glyphpath->yOffset;
  1422.         }
  1423.         else
  1424.         {
  1425.           /* +x +y */
  1426.           *x = FT_MulFix( cf2_floatToFixed( 0.7 ),
  1427.                           glyphpath->xOffset );
  1428.           *y = FT_MulFix( cf2_floatToFixed( 1.0 - 0.7 ),
  1429.                           glyphpath->yOffset );
  1430.         }
  1431.       }
  1432.       else
  1433.       {
  1434.         /* fourth quadrant, +x -y */
  1435.  
  1436.         if ( dx > -2 * dy )
  1437.         {
  1438.           /* +x */
  1439.           *x = 0;
  1440.           *y = 0;
  1441.         }
  1442.         else if ( -dy > 2 * dx )
  1443.         {
  1444.           /* -y */
  1445.           *x = -glyphpath->xOffset;
  1446.           *y = glyphpath->yOffset;
  1447.         }
  1448.         else
  1449.         {
  1450.           /* +x -y */
  1451.           *x = FT_MulFix( cf2_floatToFixed( -0.7 ),
  1452.                           glyphpath->xOffset );
  1453.           *y = FT_MulFix( cf2_floatToFixed( 1.0 - 0.7 ),
  1454.                           glyphpath->yOffset );
  1455.         }
  1456.       }
  1457.     }
  1458.     else
  1459.     {
  1460.       if ( dy >= 0 )
  1461.       {
  1462.         /* second quadrant, -x +y */
  1463.  
  1464.         if ( -dx > 2 * dy )
  1465.         {
  1466.           /* -x */
  1467.           *x = 0;
  1468.           *y = 2 * glyphpath->yOffset;
  1469.         }
  1470.         else if ( dy > -2 * dx )
  1471.         {
  1472.           /* +y */
  1473.           *x = glyphpath->xOffset;
  1474.           *y = glyphpath->yOffset;
  1475.         }
  1476.         else
  1477.         {
  1478.           /* -x +y */
  1479.           *x = FT_MulFix( cf2_floatToFixed( 0.7 ),
  1480.                           glyphpath->xOffset );
  1481.           *y = FT_MulFix( cf2_floatToFixed( 1.0 + 0.7 ),
  1482.                           glyphpath->yOffset );
  1483.         }
  1484.       }
  1485.       else
  1486.       {
  1487.         /* third quadrant, -x -y */
  1488.  
  1489.         if ( -dx > -2 * dy )
  1490.         {
  1491.           /* -x */
  1492.           *x = 0;
  1493.           *y = 2 * glyphpath->yOffset;
  1494.         }
  1495.         else if ( -dy > -2 * dx )
  1496.         {
  1497.           /* -y */
  1498.           *x = -glyphpath->xOffset;
  1499.           *y = glyphpath->xOffset;
  1500.         }
  1501.         else
  1502.         {
  1503.           /* -x -y */
  1504.           *x = FT_MulFix( cf2_floatToFixed( -0.7 ),
  1505.                           glyphpath->xOffset );
  1506.           *y = FT_MulFix( cf2_floatToFixed( 1.0 + 0.7 ),
  1507.                           glyphpath->yOffset );
  1508.         }
  1509.       }
  1510.     }
  1511.   }
  1512.  
  1513.  
  1514.   FT_LOCAL_DEF( void )
  1515.   cf2_glyphpath_moveTo( CF2_GlyphPath  glyphpath,
  1516.                         CF2_Fixed      x,
  1517.                         CF2_Fixed      y )
  1518.   {
  1519.     cf2_glyphpath_closeOpenPath( glyphpath );
  1520.  
  1521.     /* save the parameters of the move for later, when we'll know how to */
  1522.     /* offset it;                                                        */
  1523.     /* also save last move point */
  1524.     glyphpath->currentCS.x = glyphpath->start.x = x;
  1525.     glyphpath->currentCS.y = glyphpath->start.y = y;
  1526.  
  1527.     glyphpath->moveIsPending = TRUE;
  1528.  
  1529.     /* ensure we have a valid map with current mask */
  1530.     if ( !cf2_hintmap_isValid( &glyphpath->hintMap ) ||
  1531.          cf2_hintmask_isNew( glyphpath->hintMask )   )
  1532.       cf2_hintmap_build( &glyphpath->hintMap,
  1533.                          glyphpath->hStemHintArray,
  1534.                          glyphpath->vStemHintArray,
  1535.                          glyphpath->hintMask,
  1536.                          glyphpath->hintOriginY,
  1537.                          FALSE );
  1538.  
  1539.     /* save a copy of current HintMap to use when drawing initial point */
  1540.     glyphpath->firstHintMap = glyphpath->hintMap;     /* structure copy */
  1541.   }
  1542.  
  1543.  
  1544.   FT_LOCAL_DEF( void )
  1545.   cf2_glyphpath_lineTo( CF2_GlyphPath  glyphpath,
  1546.                         CF2_Fixed      x,
  1547.                         CF2_Fixed      y )
  1548.   {
  1549.     CF2_Fixed  xOffset, yOffset;
  1550.     FT_Vector  P0, P1;
  1551.  
  1552.  
  1553.     /* can't compute offset of zero length line, so ignore them */
  1554.     if ( glyphpath->currentCS.x == x && glyphpath->currentCS.y == y )
  1555.       return;
  1556.  
  1557.     cf2_glyphpath_computeOffset( glyphpath,
  1558.                                  glyphpath->currentCS.x,
  1559.                                  glyphpath->currentCS.y,
  1560.                                  x,
  1561.                                  y,
  1562.                                  &xOffset,
  1563.                                  &yOffset );
  1564.  
  1565.     /* construct offset points */
  1566.     P0.x = glyphpath->currentCS.x + xOffset;
  1567.     P0.y = glyphpath->currentCS.y + yOffset;
  1568.     P1.x = x + xOffset;
  1569.     P1.y = y + yOffset;
  1570.  
  1571.     if ( glyphpath->moveIsPending )
  1572.     {
  1573.       /* emit offset 1st point as MoveTo */
  1574.       cf2_glyphpath_pushMove( glyphpath, P0 );
  1575.  
  1576.       glyphpath->moveIsPending = FALSE;  /* adjust state machine */
  1577.       glyphpath->pathIsOpen    = TRUE;
  1578.  
  1579.       glyphpath->offsetStart1 = P1;              /* record second point */
  1580.     }
  1581.  
  1582.     if ( glyphpath->elemIsQueued )
  1583.     {
  1584.       FT_ASSERT( cf2_hintmap_isValid( &glyphpath->hintMap ) );
  1585.  
  1586.       cf2_glyphpath_pushPrevElem( glyphpath,
  1587.                                   &glyphpath->hintMap,
  1588.                                   &P0,
  1589.                                   P1,
  1590.                                   FALSE );
  1591.     }
  1592.  
  1593.     /* queue the current element with offset points */
  1594.     glyphpath->elemIsQueued = TRUE;
  1595.     glyphpath->prevElemOp   = CF2_PathOpLineTo;
  1596.     glyphpath->prevElemP0   = P0;
  1597.     glyphpath->prevElemP1   = P1;
  1598.  
  1599.     /* update current map */
  1600.     if ( cf2_hintmask_isNew( glyphpath->hintMask ) )
  1601.       cf2_hintmap_build( &glyphpath->hintMap,
  1602.                          glyphpath->hStemHintArray,
  1603.                          glyphpath->vStemHintArray,
  1604.                          glyphpath->hintMask,
  1605.                          glyphpath->hintOriginY,
  1606.                          FALSE );
  1607.  
  1608.     glyphpath->currentCS.x = x;     /* pre-offset current point */
  1609.     glyphpath->currentCS.y = y;
  1610.   }
  1611.  
  1612.  
  1613.   FT_LOCAL_DEF( void )
  1614.   cf2_glyphpath_curveTo( CF2_GlyphPath  glyphpath,
  1615.                          CF2_Fixed      x1,
  1616.                          CF2_Fixed      y1,
  1617.                          CF2_Fixed      x2,
  1618.                          CF2_Fixed      y2,
  1619.                          CF2_Fixed      x3,
  1620.                          CF2_Fixed      y3 )
  1621.   {
  1622.     CF2_Fixed  xOffset1, yOffset1, xOffset3, yOffset3;
  1623.     FT_Vector  P0, P1, P2, P3;
  1624.  
  1625.  
  1626.     /* TODO: ignore zero length portions of curve?? */
  1627.     cf2_glyphpath_computeOffset( glyphpath,
  1628.                                  glyphpath->currentCS.x,
  1629.                                  glyphpath->currentCS.y,
  1630.                                  x1,
  1631.                                  y1,
  1632.                                  &xOffset1,
  1633.                                  &yOffset1 );
  1634.     cf2_glyphpath_computeOffset( glyphpath,
  1635.                                  x2,
  1636.                                  y2,
  1637.                                  x3,
  1638.                                  y3,
  1639.                                  &xOffset3,
  1640.                                  &yOffset3 );
  1641.  
  1642.     /* add momentum from the middle segment */
  1643.     glyphpath->callbacks->windingMomentum +=
  1644.       cf2_getWindingMomentum( x1, y1, x2, y2 );
  1645.  
  1646.     /* construct offset points */
  1647.     P0.x = glyphpath->currentCS.x + xOffset1;
  1648.     P0.y = glyphpath->currentCS.y + yOffset1;
  1649.     P1.x = x1 + xOffset1;
  1650.     P1.y = y1 + yOffset1;
  1651.     /* note: preserve angle of final segment by using offset3 at both ends */
  1652.     P2.x = x2 + xOffset3;
  1653.     P2.y = y2 + yOffset3;
  1654.     P3.x = x3 + xOffset3;
  1655.     P3.y = y3 + yOffset3;
  1656.  
  1657.     if ( glyphpath->moveIsPending )
  1658.     {
  1659.       /* emit offset 1st point as MoveTo */
  1660.       cf2_glyphpath_pushMove( glyphpath, P0 );
  1661.  
  1662.       glyphpath->moveIsPending = FALSE;
  1663.       glyphpath->pathIsOpen    = TRUE;
  1664.  
  1665.       glyphpath->offsetStart1 = P1;              /* record second point */
  1666.     }
  1667.  
  1668.     if ( glyphpath->elemIsQueued )
  1669.     {
  1670.       FT_ASSERT( cf2_hintmap_isValid( &glyphpath->hintMap ) );
  1671.  
  1672.       cf2_glyphpath_pushPrevElem( glyphpath,
  1673.                                   &glyphpath->hintMap,
  1674.                                   &P0,
  1675.                                   P1,
  1676.                                   FALSE );
  1677.     }
  1678.  
  1679.     /* queue the current element with offset points */
  1680.     glyphpath->elemIsQueued = TRUE;
  1681.     glyphpath->prevElemOp   = CF2_PathOpCubeTo;
  1682.     glyphpath->prevElemP0   = P0;
  1683.     glyphpath->prevElemP1   = P1;
  1684.     glyphpath->prevElemP2   = P2;
  1685.     glyphpath->prevElemP3   = P3;
  1686.  
  1687.     /* update current map */
  1688.     if ( cf2_hintmask_isNew( glyphpath->hintMask ) )
  1689.       cf2_hintmap_build( &glyphpath->hintMap,
  1690.                          glyphpath->hStemHintArray,
  1691.                          glyphpath->vStemHintArray,
  1692.                          glyphpath->hintMask,
  1693.                          glyphpath->hintOriginY,
  1694.                          FALSE );
  1695.  
  1696.     glyphpath->currentCS.x = x3;       /* pre-offset current point */
  1697.     glyphpath->currentCS.y = y3;
  1698.   }
  1699.  
  1700.  
  1701.   FT_LOCAL_DEF( void )
  1702.   cf2_glyphpath_closeOpenPath( CF2_GlyphPath  glyphpath )
  1703.   {
  1704.     if ( glyphpath->pathIsOpen )
  1705.     {
  1706.       FT_ASSERT( cf2_hintmap_isValid( &glyphpath->firstHintMap ) );
  1707.  
  1708.       /* since we need to apply an offset to the implicit lineto, we make */
  1709.       /* it explicit here                                                 */
  1710.       cf2_glyphpath_lineTo( glyphpath,
  1711.                             glyphpath->start.x,
  1712.                             glyphpath->start.y );
  1713.  
  1714.       /* Draw previous element (the explicit LineTo we just created,      */
  1715.       /* above) and connect it to the start point, but with the offset we */
  1716.       /* saved from the first element.                                    */
  1717.       /* Use the saved HintMap, too. */
  1718.       FT_ASSERT( glyphpath->elemIsQueued );
  1719.  
  1720.       cf2_glyphpath_pushPrevElem( glyphpath,
  1721.                                   &glyphpath->firstHintMap,
  1722.                                   &glyphpath->offsetStart0,
  1723.                                   glyphpath->offsetStart1,
  1724.                                   TRUE );
  1725.  
  1726.       /* reset state machine */
  1727.       glyphpath->moveIsPending = TRUE;
  1728.       glyphpath->pathIsOpen    = FALSE;
  1729.       glyphpath->elemIsQueued  = FALSE;
  1730.     }
  1731.   }
  1732.  
  1733.  
  1734. /* END */
  1735.