qgrayraster.c

上传用户:binglan008
上传日期:2007-01-28
资源大小:53508k
文件大小:57k
源码类别:Linux/Unix编程
开发平台:MultiPlatform
  1. /****************************************************************************
  2. **
  3. ** This file is part of the QtGui module of the Qt Toolkit.
  4. **
  5. ** This file contains third party code which is not governed by the Qt
  6. ** Commercial License Agreement. Please read the license headers below
  7. ** for more information.
  8. ** 
  9. ** Further information about Qt licensing is available at:
  10. ** http://www.trolltech.com/products/qt/licensing.html or by
  11. ** contacting info@trolltech.com.
  12. **
  13. ** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  14. ** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  15. **
  16. ****************************************************************************/
  17. /***************************************************************************/
  18. /*                                                                         */
  19. /*  qgrayraster.c, derived from ftgrays.c                                  */
  20. /*                                                                         */
  21. /*    A new `perfect' anti-aliasing renderer (body).                       */
  22. /*                                                                         */
  23. /*  Copyright 2000-2001, 2002, 2003 by                                     */
  24. /*  David Turner, Robert Wilhelm, and Werner Lemberg.                      */
  25. /*                                                                         */
  26. /*  This file is part of the FreeType project, and may only be used,       */
  27. /*  modified, and distributed under the terms of the FreeType project      */
  28. /*  license, ../../3rdparty/freetype/docs/FTL.TXT.  By continuing to use,  */
  29. /*  modify, or distribute this file you indicate that you have read        */
  30. /*  the license and understand and accept it fully.                        */
  31. /*                                                                         */
  32. /***************************************************************************/
  33.   /*************************************************************************/
  34.   /*                                                                       */
  35.   /* This file can be compiled without the rest of the FreeType engine, by */
  36.   /* defining the _STANDALONE_ macro when compiling it.  You also need to  */
  37.   /* put the files `ftgrays.h' and `ftimage.h' into the current            */
  38.   /* compilation directory.  Typically, you could do something like        */
  39.   /*                                                                       */
  40.   /* - copy `src/smooth/ftgrays.c' (this file) to your current directory   */
  41.   /*                                                                       */
  42.   /* - copy `include/freetype/ftimage.h' and `src/smooth/ftgrays.h' to the */
  43.   /*   same directory                                                      */
  44.   /*                                                                       */
  45.   /* - compile `ftgrays' with the _STANDALONE_ macro defined, as in        */
  46.   /*                                                                       */
  47.   /*     cc -c -D_STANDALONE_ ftgrays.c                                    */
  48.   /*                                                                       */
  49.   /* The renderer can be initialized with a call to                        */
  50.   /* `qt_ft_gray_raster.raster_new'; an anti-aliased bitmap can be generated  */
  51.   /* with a call to `qt_ft_gray_raster.raster_render'.                        */
  52.   /*                                                                       */
  53.   /* See the comments and documentation in the file `ftimage.h' for more   */
  54.   /* details on how the raster works.                                      */
  55.   /*                                                                       */
  56.   /*************************************************************************/
  57.   /*************************************************************************/
  58.   /*                                                                       */
  59.   /* This is a new anti-aliasing scan-converter for FreeType 2.  The       */
  60.   /* algorithm used here is _very_ different from the one in the standard  */
  61.   /* `ftraster' module.  Actually, `ftgrays' computes the _exact_          */
  62.   /* coverage of the outline on each pixel cell.                           */
  63.   /*                                                                       */
  64.   /* It is based on ideas that I initially found in Raph Levien's          */
  65.   /* excellent LibArt graphics library (see http://www.levien.com/libart   */
  66.   /* for more information, though the web pages do not tell anything       */
  67.   /* about the renderer; you'll have to dive into the source code to       */
  68.   /* understand how it works).                                             */
  69.   /*                                                                       */
  70.   /* Note, however, that this is a _very_ different implementation         */
  71.   /* compared to Raph's.  Coverage information is stored in a very         */
  72.   /* different way, and I don't use sorted vector paths.  Also, it doesn't */
  73.   /* use floating point values.                                            */
  74.   /*                                                                       */
  75.   /* This renderer has the following advantages:                           */
  76.   /*                                                                       */
  77.   /* - It doesn't need an intermediate bitmap.  Instead, one can supply a  */
  78.   /*   callback function that will be called by the renderer to draw gray  */
  79.   /*   spans on any target surface.  You can thus do direct composition on */
  80.   /*   any kind of bitmap, provided that you give the renderer the right   */
  81.   /*   callback.                                                           */
  82.   /*                                                                       */
  83.   /* - A perfect anti-aliaser, i.e., it computes the _exact_ coverage on   */
  84.   /*   each pixel cell.                                                    */
  85.   /*                                                                       */
  86.   /* - It performs a single pass on the outline (the `standard' FT2        */
  87.   /*   renderer makes two passes).                                         */
  88.   /*                                                                       */
  89.   /* - It can easily be modified to render to _any_ number of gray levels  */
  90.   /*   cheaply.                                                            */
  91.   /*                                                                       */
  92.   /* - For small (< 20) pixel sizes, it is faster than the standard        */
  93.   /*   renderer.                                                           */
  94.   /*                                                                       */
  95.   /*************************************************************************/
  96. /* experimental support for gamma correction within the rasterizer */
  97. #define xxxGRAYS_USE_GAMMA
  98.   /*************************************************************************/
  99.   /*                                                                       */
  100.   /* The macro QT_FT_COMPONENT is used in trace mode.  It is an implicit      */
  101.   /* parameter of the QT_FT_TRACE() and QT_FT_ERROR() macros, used to print/log  */
  102.   /* messages during execution.                                            */
  103.   /*                                                                       */
  104. #undef  QT_FT_COMPONENT
  105. #define QT_FT_COMPONENT  trace_smooth
  106. #define ErrRaster_MemoryOverflow   -4
  107. #include <string.h>             /* for qt_ft_memcpy() */
  108. #include <setjmp.h>
  109. #include <limits.h>
  110. #define QT_FT_UINT_MAX  UINT_MAX
  111. #define qt_ft_memset   memset
  112. #define qt_ft_setjmp   setjmp
  113. #define qt_ft_longjmp  longjmp
  114. #define qt_ft_jmp_buf  jmp_buf
  115. #define ErrRaster_Invalid_Mode     -2
  116. #define ErrRaster_Invalid_Outline  -1
  117. #define QT_FT_BEGIN_HEADER
  118. #define QT_FT_END_HEADER
  119. #include <private/qrasterdefs_p.h>
  120. #include <private/qgrayraster_p.h>
  121. #include <stdlib.h>
  122. #include <stdio.h>
  123.   /* This macro is used to indicate that a function parameter is unused. */
  124.   /* Its purpose is simply to reduce compiler warnings.  Note also that  */
  125.   /* simply defining it as `(void)x' doesn't avoid warnings with certain */
  126.   /* ANSI compilers (e.g. LCC).                                          */
  127. #define QT_FT_UNUSED( x )  (x) = (x)
  128.   /* Disable the tracing mechanism for simplicity -- developers can      */
  129.   /* activate it easily by redefining these two macros.                  */
  130. #ifndef QT_FT_ERROR
  131. #define QT_FT_ERROR( x )  do ; while ( 0 )     /* nothing */
  132. #endif
  133. #ifndef QT_FT_TRACE
  134. #define QT_FT_TRACE( x )  do ; while ( 0 )     /* nothing */
  135. #endif
  136. #ifndef QT_FT_MEM_SET
  137. #define QT_FT_MEM_SET( d, s, c )  qt_ft_memset( d, s, c )
  138. #endif
  139. #ifndef QT_FT_MEM_ZERO
  140. #define QT_FT_MEM_ZERO( dest, count )  QT_FT_MEM_SET( dest, 0, count )
  141. #endif
  142.   /* define this to dump debugging information */
  143. #define xxxDEBUG_GRAYS
  144.   /* as usual, for the speed hungry :-) */
  145. #define RAS_ARG   PRaster  raster
  146. #define RAS_ARG_  PRaster  raster,
  147. #define RAS_VAR   raster
  148. #define RAS_VAR_  raster,
  149. #define ras       (*raster)
  150.   /* must be at least 6 bits! */
  151. #define PIXEL_BITS  8
  152. #define ONE_PIXEL       ( 1L << PIXEL_BITS )
  153. #define PIXEL_MASK      ( -1L << PIXEL_BITS )
  154. #define TRUNC( x )      ( (TCoord)((x) >> PIXEL_BITS) )
  155. #define SUBPIXELS( x )  ( (TPos)(x) << PIXEL_BITS )
  156. #define FLOOR( x )      ( (x) & -ONE_PIXEL )
  157. #define CEILING( x )    ( ( (x) + ONE_PIXEL - 1 ) & -ONE_PIXEL )
  158. #define ROUND( x )      ( ( (x) + ONE_PIXEL / 2 ) & -ONE_PIXEL )
  159. #if PIXEL_BITS >= 6
  160. #define UPSCALE( x )    ( (x) << ( PIXEL_BITS - 6 ) )
  161. #define DOWNSCALE( x )  ( (x) >> ( PIXEL_BITS - 6 ) )
  162. #else
  163. #define UPSCALE( x )    ( (x) >> ( 6 - PIXEL_BITS ) )
  164. #define DOWNSCALE( x )  ( (x) << ( 6 - PIXEL_BITS ) )
  165. #endif
  166.   /* Define this if you want to use a more compact storage scheme.  This   */
  167.   /* increases the number of cells available in the render pool but slows  */
  168.   /* down the rendering a bit.  It is useful if you have a really tiny     */
  169.   /* render pool.                                                          */
  170. #undef GRAYS_COMPACT
  171.   /*************************************************************************/
  172.   /*                                                                       */
  173.   /*   TYPE DEFINITIONS                                                    */
  174.   /*                                                                       */
  175.   /* don't change the following types to QT_FT_Int or QT_FT_Pos, since we might */
  176.   /* need to define them to "float" or "double" when experimenting with   */
  177.   /* new algorithms                                                       */
  178.   typedef int   TCoord;   /* integer scanline/pixel coordinate */
  179.   typedef long  TPos;     /* sub-pixel coordinate              */
  180.   /* determine the type used to store cell areas.  This normally takes at */
  181.   /* least PIXEL_BYTES*2 + 1.  On 16-bit systems, we need to use `long'   */
  182.   /* instead of `int', otherwise bad things happen                        */
  183. #if PIXEL_BITS <= 7
  184.   typedef int   TArea;
  185. #else /* PIXEL_BITS >= 8 */
  186.   /* approximately determine the size of integers using an ANSI-C header */
  187. #if QT_FT_UINT_MAX == 0xFFFFU
  188.   typedef long  TArea;
  189. #else
  190.   typedef int  TArea;
  191. #endif
  192. #endif /* PIXEL_BITS >= 8 */
  193.   /* maximal number of gray spans in a call to the span callback */
  194. #define QT_FT_MAX_GRAY_SPANS  256
  195. #ifdef GRAYS_COMPACT
  196.   typedef struct  TCell_
  197.   {
  198.     short  x     : 14;
  199.     short  y     : 14;
  200.     int    cover : PIXEL_BITS + 2;
  201.     int    area  : PIXEL_BITS * 2 + 2;
  202.   } TCell, *PCell;
  203. #else /* GRAYS_COMPACT */
  204.   typedef struct  TCell_
  205.   {
  206.     TCoord  x;
  207.     TCoord  y;
  208.     int     cover;
  209.     TArea   area;
  210.   } TCell, *PCell;
  211. #endif /* GRAYS_COMPACT */
  212.   typedef struct  TRaster_
  213.   {
  214.     PCell   cells;
  215.     int     max_cells;
  216.     int     num_cells;
  217.     TPos    min_ex, max_ex;
  218.     TPos    min_ey, max_ey;
  219.     TArea   area;
  220.     int     cover;
  221.     int     invalid;
  222.     TCoord  ex, ey;
  223.     TCoord  cx, cy;
  224.     TPos    x,  y;
  225.     TPos    last_ey;
  226.     QT_FT_Vector   bez_stack[32 * 3 + 1];
  227.     int         lev_stack[32];
  228.     QT_FT_Outline  outline;
  229.     QT_FT_Bitmap   target;
  230.     QT_FT_BBox     clip_box;
  231.     QT_FT_Span     gray_spans[QT_FT_MAX_GRAY_SPANS];
  232.     int         num_gray_spans;
  233.     QT_FT_Raster_Span_Func  render_span;
  234.     void*                render_span_data;
  235.     int  band_size;
  236.     int  band_shoot;
  237.     int  conic_level;
  238.     int  cubic_level;
  239.     void*       memory;
  240.     qt_ft_jmp_buf  jump_buffer;
  241. #ifdef GRAYS_USE_GAMMA
  242.     unsigned char  gamma[257];
  243. #endif
  244.   } TRaster, *PRaster;
  245.   /*************************************************************************/
  246.   /*                                                                       */
  247.   /* Initialize the cells table.                                           */
  248.   /*                                                                       */
  249.   static void
  250.   gray_init_cells( RAS_ARG_ void*  buffer,
  251.                    long            byte_size )
  252.   {
  253.     ras.cells     = (PCell)buffer;
  254.     ras.max_cells = (int)( byte_size / sizeof ( TCell ) );
  255.     ras.num_cells = 0;
  256.     ras.area      = 0;
  257.     ras.cover     = 0;
  258.     ras.invalid   = 1;
  259.   }
  260.   /*************************************************************************/
  261.   /*                                                                       */
  262.   /* Compute the outline bounding box.                                     */
  263.   /*                                                                       */
  264.   static void
  265.   gray_compute_cbox( RAS_ARG )
  266.   {
  267.     QT_FT_Outline*  outline = &ras.outline;
  268.     QT_FT_Vector*   vec     = outline->points;
  269.     QT_FT_Vector*   limit   = vec + outline->n_points;
  270.     if ( outline->n_points <= 0 )
  271.     {
  272.       ras.min_ex = ras.max_ex = 0;
  273.       ras.min_ey = ras.max_ey = 0;
  274.       return;
  275.     }
  276.     ras.min_ex = ras.max_ex = vec->x;
  277.     ras.min_ey = ras.max_ey = vec->y;
  278.     vec++;
  279.     for ( ; vec < limit; vec++ )
  280.     {
  281.       TPos  x = vec->x;
  282.       TPos  y = vec->y;
  283.       if ( x < ras.min_ex ) ras.min_ex = x;
  284.       if ( x > ras.max_ex ) ras.max_ex = x;
  285.       if ( y < ras.min_ey ) ras.min_ey = y;
  286.       if ( y > ras.max_ey ) ras.max_ey = y;
  287.     }
  288.     /* truncate the bounding box to integer pixels */
  289.     ras.min_ex = ras.min_ex >> 6;
  290.     ras.min_ey = ras.min_ey >> 6;
  291.     ras.max_ex = ( ras.max_ex + 63 ) >> 6;
  292.     ras.max_ey = ( ras.max_ey + 63 ) >> 6;
  293.   }
  294.   /*************************************************************************/
  295.   /*                                                                       */
  296.   /* Record the current cell in the table.                                 */
  297.   /*                                                                       */
  298.   static void
  299.   gray_record_cell( RAS_ARG )
  300.   {
  301.     PCell  cell;
  302.     if ( !ras.invalid && ( ras.area | ras.cover ) )
  303.     {
  304.       if ( ras.num_cells >= ras.max_cells )
  305.         qt_ft_longjmp( ras.jump_buffer, 1 );
  306.       cell        = ras.cells + ras.num_cells++;
  307.       cell->x     = (TCoord)(ras.ex - ras.min_ex);
  308.       cell->y     = (TCoord)(ras.ey - ras.min_ey);
  309.       cell->area  = ras.area;
  310.       cell->cover = ras.cover;
  311.     }
  312.   }
  313.   /*************************************************************************/
  314.   /*                                                                       */
  315.   /* Set the current cell to a new position.                               */
  316.   /*                                                                       */
  317.   static void
  318.   gray_set_cell( RAS_ARG_ TCoord  ex,
  319.                           TCoord  ey )
  320.   {
  321.     int  invalid, record, clean;
  322.     /* Move the cell pointer to a new position.  We set the `invalid'      */
  323.     /* flag to indicate that the cell isn't part of those we're interested */
  324.     /* in during the render phase.  This means that:                       */
  325.     /*                                                                     */
  326.     /* . the new vertical position must be within min_ey..max_ey-1.        */
  327.     /* . the new horizontal position must be strictly less than max_ex     */
  328.     /*                                                                     */
  329.     /* Note that if a cell is to the left of the clipping region, it is    */
  330.     /* actually set to the (min_ex-1) horizontal position.                 */
  331.     record  = 0;
  332.     clean   = 1;
  333.     invalid = ( ey < ras.min_ey || ey >= ras.max_ey || ex >= ras.max_ex );
  334.     if ( !invalid )
  335.     {
  336.       /* All cells that are on the left of the clipping region go to the */
  337.       /* min_ex - 1 horizontal position.                                 */
  338.       if ( ex < ras.min_ex )
  339.         ex = (TCoord)(ras.min_ex - 1);
  340.       /* if our position is new, then record the previous cell */
  341.       if ( ex != ras.ex || ey != ras.ey )
  342.         record = 1;
  343.       else
  344.         clean = ras.invalid;  /* do not clean if we didn't move from */
  345.                               /* a valid cell                        */
  346.     }
  347.     /* record the previous cell if needed (i.e., if we changed the cell */
  348.     /* position, of changed the `invalid' flag)                         */
  349.     if ( ras.invalid != invalid || record )
  350.       gray_record_cell( RAS_VAR );
  351.     if ( clean )
  352.     {
  353.       ras.area  = 0;
  354.       ras.cover = 0;
  355.     }
  356.     ras.invalid = invalid;
  357.     ras.ex      = ex;
  358.     ras.ey      = ey;
  359.   }
  360.   /*************************************************************************/
  361.   /*                                                                       */
  362.   /* Start a new contour at a given cell.                                  */
  363.   /*                                                                       */
  364.   static void
  365.   gray_start_cell( RAS_ARG_  TCoord  ex,
  366.                              TCoord  ey )
  367.   {
  368.     if ( ex < ras.min_ex )
  369.       ex = (TCoord)(ras.min_ex - 1);
  370.     ras.area    = 0;
  371.     ras.cover   = 0;
  372.     ras.ex      = ex;
  373.     ras.ey      = ey;
  374.     ras.last_ey = SUBPIXELS( ey );
  375.     ras.invalid = 0;
  376.     gray_set_cell( RAS_VAR_ ex, ey );
  377.   }
  378.   /*************************************************************************/
  379.   /*                                                                       */
  380.   /* Render a scanline as one or more cells.                               */
  381.   /*                                                                       */
  382.   static void
  383.   gray_render_scanline( RAS_ARG_  TCoord  ey,
  384.                                   TPos    x1,
  385.                                   TCoord  y1,
  386.                                   TPos    x2,
  387.                                   TCoord  y2 )
  388.   {
  389.     TCoord  ex1, ex2, fx1, fx2, delta;
  390.     long    p, first, dx;
  391.     int     incr, lift, mod, rem;
  392.     dx = x2 - x1;
  393.     ex1 = TRUNC( x1 ); /* if (ex1 >= ras.max_ex) ex1 = ras.max_ex-1; */
  394.     ex2 = TRUNC( x2 ); /* if (ex2 >= ras.max_ex) ex2 = ras.max_ex-1; */
  395.     fx1 = (TCoord)( x1 - SUBPIXELS( ex1 ) );
  396.     fx2 = (TCoord)( x2 - SUBPIXELS( ex2 ) );
  397.     /* trivial case.  Happens often */
  398.     if ( y1 == y2 )
  399.     {
  400.       gray_set_cell( RAS_VAR_ ex2, ey );
  401.       return;
  402.     }
  403.     /* everything is located in a single cell.  That is easy! */
  404.     /*                                                        */
  405.     if ( ex1 == ex2 )
  406.     {
  407.       delta      = y2 - y1;
  408.       ras.area  += (TArea)( fx1 + fx2 ) * delta;
  409.       ras.cover += delta;
  410.       return;
  411.     }
  412.     /* ok, we'll have to render a run of adjacent cells on the same */
  413.     /* scanline...                                                  */
  414.     /*                                                              */
  415.     p     = ( ONE_PIXEL - fx1 ) * ( y2 - y1 );
  416.     first = ONE_PIXEL;
  417.     incr  = 1;
  418.     if ( dx < 0 )
  419.     {
  420.       p     = fx1 * ( y2 - y1 );
  421.       first = 0;
  422.       incr  = -1;
  423.       dx    = -dx;
  424.     }
  425.     delta = (TCoord)( p / dx );
  426.     mod   = (TCoord)( p % dx );
  427.     if ( mod < 0 )
  428.     {
  429.       delta--;
  430.       mod += (TCoord)dx;
  431.     }
  432.     ras.area  += (TArea)( fx1 + first ) * delta;
  433.     ras.cover += delta;
  434.     ex1 += incr;
  435.     gray_set_cell( RAS_VAR_ ex1, ey );
  436.     y1  += delta;
  437.     if ( ex1 != ex2 )
  438.     {
  439.       p    = ONE_PIXEL * ( y2 - y1 + delta );
  440.       lift = (TCoord)( p / dx );
  441.       rem  = (TCoord)( p % dx );
  442.       if ( rem < 0 )
  443.       {
  444.         lift--;
  445.         rem += (TCoord)dx;
  446.       }
  447.       mod -= (int)dx;
  448.       while ( ex1 != ex2 )
  449.       {
  450.         delta = lift;
  451.         mod  += rem;
  452.         if ( mod >= 0 )
  453.         {
  454.           mod -= (TCoord)dx;
  455.           delta++;
  456.         }
  457.         ras.area  += (TArea)ONE_PIXEL * delta;
  458.         ras.cover += delta;
  459.         y1        += delta;
  460.         ex1       += incr;
  461.         gray_set_cell( RAS_VAR_ ex1, ey );
  462.       }
  463.     }
  464.     delta      = y2 - y1;
  465.     ras.area  += (TArea)( fx2 + ONE_PIXEL - first ) * delta;
  466.     ras.cover += delta;
  467.   }
  468.   /*************************************************************************/
  469.   /*                                                                       */
  470.   /* Render a given line as a series of scanlines.                         */
  471.   /*                                                                       */
  472.   static void
  473.   gray_render_line( RAS_ARG_ TPos  to_x,
  474.                              TPos  to_y )
  475.   {
  476.     TCoord  ey1, ey2, fy1, fy2;
  477.     TPos    dx, dy, x, x2;
  478.     long    p, first;
  479.     int     delta, rem, mod, lift, incr;
  480.     ey1 = TRUNC( ras.last_ey );
  481.     ey2 = TRUNC( to_y ); /* if (ey2 >= ras.max_ey) ey2 = ras.max_ey-1; */
  482.     fy1 = (TCoord)( ras.y - ras.last_ey );
  483.     fy2 = (TCoord)( to_y - SUBPIXELS( ey2 ) );
  484.     dx = to_x - ras.x;
  485.     dy = to_y - ras.y;
  486.     /* XXX: we should do something about the trivial case where dx == 0, */
  487.     /*      as it happens very often!                                    */
  488.     /* perform vertical clipping */
  489.     {
  490.       TCoord  min, max;
  491.       min = ey1;
  492.       max = ey2;
  493.       if ( ey1 > ey2 )
  494.       {
  495.         min = ey2;
  496.         max = ey1;
  497.       }
  498.       if ( min >= ras.max_ey || max < ras.min_ey )
  499.         goto End;
  500.     }
  501.     /* everything is on a single scanline */
  502.     if ( ey1 == ey2 )
  503.     {
  504.       gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, to_x, fy2 );
  505.       goto End;
  506.     }
  507.     /* vertical line - avoid calling gray_render_scanline */
  508.     incr = 1;
  509.     if ( dx == 0 )
  510.     {
  511.       TCoord  ex     = TRUNC( ras.x );
  512.       TCoord  two_fx = (TCoord)( ( ras.x - SUBPIXELS( ex ) ) << 1 );
  513.       TPos    area;
  514.       first = ONE_PIXEL;
  515.       if ( dy < 0 )
  516.       {
  517.         first = 0;
  518.         incr  = -1;
  519.       }
  520.       delta      = (int)( first - fy1 );
  521.       ras.area  += (TArea)two_fx * delta;
  522.       ras.cover += delta;
  523.       ey1       += incr;
  524.       gray_set_cell( raster, ex, ey1 );
  525.       delta = (int)( first + first - ONE_PIXEL );
  526.       area  = (TArea)two_fx * delta;
  527.       while ( ey1 != ey2 )
  528.       {
  529.         ras.area  += area;
  530.         ras.cover += delta;
  531.         ey1       += incr;
  532.         gray_set_cell( raster, ex, ey1 );
  533.       }
  534.       delta      = (int)( fy2 - ONE_PIXEL + first );
  535.       ras.area  += (TArea)two_fx * delta;
  536.       ras.cover += delta;
  537.       goto End;
  538.     }
  539.     /* ok, we have to render several scanlines */
  540.     p     = ( ONE_PIXEL - fy1 ) * dx;
  541.     first = ONE_PIXEL;
  542.     incr  = 1;
  543.     if ( dy < 0 )
  544.     {
  545.       p     = fy1 * dx;
  546.       first = 0;
  547.       incr  = -1;
  548.       dy    = -dy;
  549.     }
  550.     delta = (int)( p / dy );
  551.     mod   = (int)( p % dy );
  552.     if ( mod < 0 )
  553.     {
  554.       delta--;
  555.       mod += (TCoord)dy;
  556.     }
  557.     x = ras.x + delta;
  558.     gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, x, (TCoord)first );
  559.     ey1 += incr;
  560.     gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 );
  561.     if ( ey1 != ey2 )
  562.     {
  563.       p     = ONE_PIXEL * dx;
  564.       lift  = (int)( p / dy );
  565.       rem   = (int)( p % dy );
  566.       if ( rem < 0 )
  567.       {
  568.         lift--;
  569.         rem += (int)dy;
  570.       }
  571.       mod -= (int)dy;
  572.       while ( ey1 != ey2 )
  573.       {
  574.         delta = lift;
  575.         mod  += rem;
  576.         if ( mod >= 0 )
  577.         {
  578.           mod -= (int)dy;
  579.           delta++;
  580.         }
  581.         x2 = x + delta;
  582.         gray_render_scanline( RAS_VAR_ ey1, x,
  583.                                        (TCoord)( ONE_PIXEL - first ), x2,
  584.                                        (TCoord)first );
  585.         x = x2;
  586.         ey1 += incr;
  587.         gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 );
  588.       }
  589.     }
  590.     gray_render_scanline( RAS_VAR_ ey1, x,
  591.                                    (TCoord)( ONE_PIXEL - first ), to_x,
  592.                                    fy2 );
  593.   End:
  594.     ras.x       = to_x;
  595.     ras.y       = to_y;
  596.     ras.last_ey = SUBPIXELS( ey2 );
  597.   }
  598.   static void
  599.   gray_split_conic( QT_FT_Vector*  base )
  600.   {
  601.     TPos  a, b;
  602.     base[4].x = base[2].x;
  603.     b = base[1].x;
  604.     a = base[3].x = ( base[2].x + b ) / 2;
  605.     b = base[1].x = ( base[0].x + b ) / 2;
  606.     base[2].x = ( a + b ) / 2;
  607.     base[4].y = base[2].y;
  608.     b = base[1].y;
  609.     a = base[3].y = ( base[2].y + b ) / 2;
  610.     b = base[1].y = ( base[0].y + b ) / 2;
  611.     base[2].y = ( a + b ) / 2;
  612.   }
  613.   static void
  614.   gray_render_conic( RAS_ARG_ QT_FT_Vector*  control,
  615.                               QT_FT_Vector*  to )
  616.   {
  617.     TPos        dx, dy;
  618.     int         top, level;
  619.     int*        levels;
  620.     QT_FT_Vector*  arc;
  621.     dx = DOWNSCALE( ras.x ) + to->x - ( control->x << 1 );
  622.     if ( dx < 0 )
  623.       dx = -dx;
  624.     dy = DOWNSCALE( ras.y ) + to->y - ( control->y << 1 );
  625.     if ( dy < 0 )
  626.       dy = -dy;
  627.     if ( dx < dy )
  628.       dx = dy;
  629.     level = 1;
  630.     dx = dx / ras.conic_level;
  631.     while ( dx > 0 )
  632.     {
  633.       dx >>= 2;
  634.       level++;
  635.     }
  636.     /* a shortcut to speed things up */
  637.     if ( level <= 1 )
  638.     {
  639.       /* we compute the mid-point directly in order to avoid */
  640.       /* calling gray_split_conic()                          */
  641.       TPos   to_x, to_y, mid_x, mid_y;
  642.       to_x  = UPSCALE( to->x );
  643.       to_y  = UPSCALE( to->y );
  644.       mid_x = ( ras.x + to_x + 2 * UPSCALE( control->x ) ) / 4;
  645.       mid_y = ( ras.y + to_y + 2 * UPSCALE( control->y ) ) / 4;
  646.       gray_render_line( RAS_VAR_ mid_x, mid_y );
  647.       gray_render_line( RAS_VAR_ to_x, to_y );
  648.       return;
  649.     }
  650.     arc       = ras.bez_stack;
  651.     levels    = ras.lev_stack;
  652.     top       = 0;
  653.     levels[0] = level;
  654.     arc[0].x = UPSCALE( to->x );
  655.     arc[0].y = UPSCALE( to->y );
  656.     arc[1].x = UPSCALE( control->x );
  657.     arc[1].y = UPSCALE( control->y );
  658.     arc[2].x = ras.x;
  659.     arc[2].y = ras.y;
  660.     while ( top >= 0 )
  661.     {
  662.       level = levels[top];
  663.       if ( level > 1 )
  664.       {
  665.         /* check that the arc crosses the current band */
  666.         TPos  min, max, y;
  667.         min = max = arc[0].y;
  668.         y = arc[1].y;
  669.         if ( y < min ) min = y;
  670.         if ( y > max ) max = y;
  671.         y = arc[2].y;
  672.         if ( y < min ) min = y;
  673.         if ( y > max ) max = y;
  674.         if ( TRUNC( min ) >= ras.max_ey || TRUNC( max ) < ras.min_ey )
  675.           goto Draw;
  676.         gray_split_conic( arc );
  677.         arc += 2;
  678.         top++;
  679.         levels[top] = levels[top - 1] = level - 1;
  680.         continue;
  681.       }
  682.     Draw:
  683.       {
  684.         TPos  to_x, to_y, mid_x, mid_y;
  685.         to_x  = arc[0].x;
  686.         to_y  = arc[0].y;
  687.         mid_x = ( ras.x + to_x + 2 * arc[1].x ) / 4;
  688.         mid_y = ( ras.y + to_y + 2 * arc[1].y ) / 4;
  689.         gray_render_line( RAS_VAR_ mid_x, mid_y );
  690.         gray_render_line( RAS_VAR_ to_x, to_y );
  691.         top--;
  692.         arc -= 2;
  693.       }
  694.     }
  695.     return;
  696.   }
  697.   static void
  698.   gray_split_cubic( QT_FT_Vector*  base )
  699.   {
  700.     TPos  a, b, c, d;
  701.     base[6].x = base[3].x;
  702.     c = base[1].x;
  703.     d = base[2].x;
  704.     base[1].x = a = ( base[0].x + c ) / 2;
  705.     base[5].x = b = ( base[3].x + d ) / 2;
  706.     c = ( c + d ) / 2;
  707.     base[2].x = a = ( a + c ) / 2;
  708.     base[4].x = b = ( b + c ) / 2;
  709.     base[3].x = ( a + b ) / 2;
  710.     base[6].y = base[3].y;
  711.     c = base[1].y;
  712.     d = base[2].y;
  713.     base[1].y = a = ( base[0].y + c ) / 2;
  714.     base[5].y = b = ( base[3].y + d ) / 2;
  715.     c = ( c + d ) / 2;
  716.     base[2].y = a = ( a + c ) / 2;
  717.     base[4].y = b = ( b + c ) / 2;
  718.     base[3].y = ( a + b ) / 2;
  719.   }
  720.   static void
  721.   gray_render_cubic( RAS_ARG_ QT_FT_Vector*  control1,
  722.                               QT_FT_Vector*  control2,
  723.                               QT_FT_Vector*  to )
  724.   {
  725.     TPos        dx, dy, da, db;
  726.     int         top, level;
  727.     int*        levels;
  728.     QT_FT_Vector*  arc;
  729.     dx = DOWNSCALE( ras.x ) + to->x - ( control1->x << 1 );
  730.     if ( dx < 0 )
  731.       dx = -dx;
  732.     dy = DOWNSCALE( ras.y ) + to->y - ( control1->y << 1 );
  733.     if ( dy < 0 )
  734.       dy = -dy;
  735.     if ( dx < dy )
  736.       dx = dy;
  737.     da = dx;
  738.     dx = DOWNSCALE( ras.x ) + to->x - 3 * ( control1->x + control2->x );
  739.     if ( dx < 0 )
  740.       dx = -dx;
  741.     dy = DOWNSCALE( ras.y ) + to->y - 3 * ( control1->x + control2->y );
  742.     if ( dy < 0 )
  743.       dy = -dy;
  744.     if ( dx < dy )
  745.       dx = dy;
  746.     db = dx;
  747.     level = 1;
  748.     da    = da / ras.cubic_level;
  749.     db    = db / ras.conic_level;
  750.     while ( da > 0 || db > 0 )
  751.     {
  752.       da >>= 2;
  753.       db >>= 3;
  754.       level++;
  755.     }
  756.     if ( level <= 1 )
  757.     {
  758.       TPos   to_x, to_y, mid_x, mid_y;
  759.       to_x  = UPSCALE( to->x );
  760.       to_y  = UPSCALE( to->y );
  761.       mid_x = ( ras.x + to_x +
  762.                 3 * UPSCALE( control1->x + control2->x ) ) / 8;
  763.       mid_y = ( ras.y + to_y +
  764.                 3 * UPSCALE( control1->y + control2->y ) ) / 8;
  765.       gray_render_line( RAS_VAR_ mid_x, mid_y );
  766.       gray_render_line( RAS_VAR_ to_x, to_y );
  767.       return;
  768.     }
  769.     arc      = ras.bez_stack;
  770.     arc[0].x = UPSCALE( to->x );
  771.     arc[0].y = UPSCALE( to->y );
  772.     arc[1].x = UPSCALE( control2->x );
  773.     arc[1].y = UPSCALE( control2->y );
  774.     arc[2].x = UPSCALE( control1->x );
  775.     arc[2].y = UPSCALE( control1->y );
  776.     arc[3].x = ras.x;
  777.     arc[3].y = ras.y;
  778.     levels    = ras.lev_stack;
  779.     top       = 0;
  780.     levels[0] = level;
  781.     while ( top >= 0 )
  782.     {
  783.       level = levels[top];
  784.       if ( level > 1 )
  785.       {
  786.         /* check that the arc crosses the current band */
  787.         TPos  min, max, y;
  788.         min = max = arc[0].y;
  789.         y = arc[1].y;
  790.         if ( y < min ) min = y;
  791.         if ( y > max ) max = y;
  792.         y = arc[2].y;
  793.         if ( y < min ) min = y;
  794.         if ( y > max ) max = y;
  795.         y = arc[3].y;
  796.         if ( y < min ) min = y;
  797.         if ( y > max ) max = y;
  798.         if ( TRUNC( min ) >= ras.max_ey || TRUNC( max ) < 0 )
  799.           goto Draw;
  800.         gray_split_cubic( arc );
  801.         arc += 3;
  802.         top ++;
  803.         levels[top] = levels[top - 1] = level - 1;
  804.         continue;
  805.       }
  806.     Draw:
  807.       {
  808.         TPos  to_x, to_y, mid_x, mid_y;
  809.         to_x  = arc[0].x;
  810.         to_y  = arc[0].y;
  811.         mid_x = ( ras.x + to_x + 3 * ( arc[1].x + arc[2].x ) ) / 8;
  812.         mid_y = ( ras.y + to_y + 3 * ( arc[1].y + arc[2].y ) ) / 8;
  813.         gray_render_line( RAS_VAR_ mid_x, mid_y );
  814.         gray_render_line( RAS_VAR_ to_x, to_y );
  815.         top --;
  816.         arc -= 3;
  817.       }
  818.     }
  819.     return;
  820.   }
  821.   /* a macro comparing two cell pointers.  Returns true if a <= b. */
  822. #if 1
  823. #define PACK( a )          ( ( (long)(a)->y << 16 ) + (a)->x )
  824. #define LESS_THAN( a, b )  ( PACK( a ) < PACK( b ) )
  825. #else /* 1 */
  826. #define LESS_THAN( a, b )  ( (a)->y < (b)->y || 
  827.                              ( (a)->y == (b)->y && (a)->x < (b)->x ) )
  828. #endif /* 1 */
  829. #define SWAP_CELLS( a, b, temp )  do             
  830.                                   {              
  831.                                     temp = *(a); 
  832.                                     *(a) = *(b); 
  833.                                     *(b) = temp; 
  834.                                   } while ( 0 )
  835. #define DEBUG_SORT
  836. #define QUICK_SORT
  837. #ifdef SHELL_SORT
  838.   /* a simple shell sort algorithm that works directly on our */
  839.   /* cells table                                              */
  840.   static void
  841.   gray_shell_sort ( PCell  cells,
  842.                     int    count )
  843.   {
  844.     PCell  i, j, limit = cells + count;
  845.     TCell  temp;
  846.     int    gap;
  847.     /* compute initial gap */
  848.     for ( gap = 0; ++gap < count; gap *= 3 )
  849.       ;
  850.     while ( gap /= 3 )
  851.     {
  852.       for ( i = cells + gap; i < limit; i++ )
  853.       {
  854.         for ( j = i - gap; ; j -= gap )
  855.         {
  856.           PCell  k = j + gap;
  857.           if ( LESS_THAN( j, k ) )
  858.             break;
  859.           SWAP_CELLS( j, k, temp );
  860.           if ( j < cells + gap )
  861.             break;
  862.         }
  863.       }
  864.     }
  865.   }
  866. #endif /* SHELL_SORT */
  867. #ifdef QUICK_SORT
  868.   /* This is a non-recursive quicksort that directly process our cells     */
  869.   /* array.  It should be faster than calling the stdlib qsort(), and we   */
  870.   /* can even tailor our insertion threshold...                            */
  871. #define QSORT_THRESHOLD  9  /* below this size, a sub-array will be sorted */
  872.                             /* through a normal insertion sort             */
  873.   static void
  874.   gray_quick_sort( PCell  cells,
  875.                    int    count )
  876.   {
  877.     PCell   stack[40];  /* should be enough ;-) */
  878.     PCell*  top;        /* top of stack */
  879.     PCell   base, limit;
  880.     TCell   temp;
  881.     limit = cells + count;
  882.     base  = cells;
  883.     top   = stack;
  884.     for (;;)
  885.     {
  886.       int    len = (int)( limit - base );
  887.       PCell  i, j, pivot;
  888.       if ( len > QSORT_THRESHOLD )
  889.       {
  890.         /* we use base + len/2 as the pivot */
  891.         pivot = base + len / 2;
  892.         SWAP_CELLS( base, pivot, temp );
  893.         i = base + 1;
  894.         j = limit - 1;
  895.         /* now ensure that *i <= *base <= *j */
  896.         if ( LESS_THAN( j, i ) )
  897.           SWAP_CELLS( i, j, temp );
  898.         if ( LESS_THAN( base, i ) )
  899.           SWAP_CELLS( base, i, temp );
  900.         if ( LESS_THAN( j, base ) )
  901.           SWAP_CELLS( base, j, temp );
  902.         for (;;)
  903.         {
  904.           do i++; while ( LESS_THAN( i, base ) );
  905.           do j--; while ( LESS_THAN( base, j ) );
  906.           if ( i > j )
  907.             break;
  908.           SWAP_CELLS( i, j, temp );
  909.         }
  910.         SWAP_CELLS( base, j, temp );
  911.         /* now, push the largest sub-array */
  912.         if ( j - base > limit - i )
  913.         {
  914.           top[0] = base;
  915.           top[1] = j;
  916.           base   = i;
  917.         }
  918.         else
  919.         {
  920.           top[0] = i;
  921.           top[1] = limit;
  922.           limit  = j;
  923.         }
  924.         top += 2;
  925.       }
  926.       else
  927.       {
  928.         /* the sub-array is small, perform insertion sort */
  929.         j = base;
  930.         i = j + 1;
  931.         for ( ; i < limit; j = i, i++ )
  932.         {
  933.           for ( ; LESS_THAN( j + 1, j ); j-- )
  934.           {
  935.             SWAP_CELLS( j + 1, j, temp );
  936.             if ( j == base )
  937.               break;
  938.           }
  939.         }
  940.         if ( top > stack )
  941.         {
  942.           top  -= 2;
  943.           base  = top[0];
  944.           limit = top[1];
  945.         }
  946.         else
  947.           break;
  948.       }
  949.     }
  950.   }
  951. #endif /* QUICK_SORT */
  952. #ifdef DEBUG_GRAYS
  953. #ifdef DEBUG_SORT
  954.   static int
  955.   gray_check_sort( PCell  cells,
  956.                    int    count )
  957.   {
  958.     PCell  p, q;
  959.     for ( p = cells + count - 2; p >= cells; p-- )
  960.     {
  961.       q = p + 1;
  962.       if ( !LESS_THAN( p, q ) )
  963.         return 0;
  964.     }
  965.     return 1;
  966.   }
  967. #endif /* DEBUG_SORT */
  968. #endif /* DEBUG_GRAYS */
  969.   static int
  970.   gray_move_to( QT_FT_Vector*  to,
  971.                 QT_FT_Raster   raster )
  972.   {
  973.     TPos  x, y;
  974.     /* record current cell, if any */
  975.     gray_record_cell( (PRaster)raster );
  976.     /* start to a new position */
  977.     x = UPSCALE( to->x );
  978.     y = UPSCALE( to->y );
  979.     gray_start_cell( (PRaster)raster, TRUNC( x ), TRUNC( y ) );
  980.     ((PRaster)raster)->x = x;
  981.     ((PRaster)raster)->y = y;
  982.     return 0;
  983.   }
  984.   static int
  985.   gray_line_to( QT_FT_Vector*  to,
  986.                 QT_FT_Raster   raster )
  987.   {
  988.     gray_render_line( (PRaster)raster,
  989.                       UPSCALE( to->x ), UPSCALE( to->y ) );
  990.     return 0;
  991.   }
  992.   static int
  993.   gray_conic_to( QT_FT_Vector*  control,
  994.                  QT_FT_Vector*  to,
  995.                  QT_FT_Raster   raster )
  996.   {
  997.     gray_render_conic( (PRaster)raster, control, to );
  998.     return 0;
  999.   }
  1000.   static int
  1001.   gray_cubic_to( QT_FT_Vector*  control1,
  1002.                  QT_FT_Vector*  control2,
  1003.                  QT_FT_Vector*  to,
  1004.                  QT_FT_Raster   raster )
  1005.   {
  1006.     gray_render_cubic( (PRaster)raster, control1, control2, to );
  1007.     return 0;
  1008.   }
  1009.   static void
  1010.   gray_render_span( int       y,
  1011.                     int       count,
  1012.                     QT_FT_Span*  spans,
  1013.                     PRaster   raster )
  1014.   {
  1015.     unsigned char*  p;
  1016.     QT_FT_Bitmap*      map = &raster->target;
  1017.     /* first of all, compute the scanline offset */
  1018.     p = (unsigned char*)map->buffer - y * map->pitch;
  1019.     if ( map->pitch >= 0 )
  1020.       p += ( map->rows - 1 ) * map->pitch;
  1021.     for ( ; count > 0; count--, spans++ )
  1022.     {
  1023.       unsigned char  coverage = spans->coverage;
  1024. #ifdef GRAYS_USE_GAMMA
  1025.       coverage = raster->gamma[coverage];
  1026. #endif
  1027.       if ( coverage )
  1028. #if 1
  1029.         QT_FT_MEM_SET( p + spans->x, (unsigned char)coverage, spans->len );
  1030. #else /* 1 */
  1031.       {
  1032.         q     = p + spans->x;
  1033.         limit = q + spans->len;
  1034.         for ( ; q < limit; q++ )
  1035.           q[0] = (unsigned char)coverage;
  1036.       }
  1037. #endif /* 1 */
  1038.     }
  1039.   }
  1040. #ifdef DEBUG_GRAYS
  1041. #include <stdio.h>
  1042.   static void
  1043.   gray_dump_cells( RAS_ARG )
  1044.   {
  1045.     PCell  cell, limit;
  1046.     int    y = -1;
  1047.     cell  = ras.cells;
  1048.     limit = cell + ras.num_cells;
  1049.     for ( ; cell < limit; cell++ )
  1050.     {
  1051.       if ( cell->y != y )
  1052.       {
  1053.         fprintf( stderr, "n%2d: ", cell->y );
  1054.         y = cell->y;
  1055.       }
  1056.       fprintf( stderr, "[%d %d %d]",
  1057.                cell->x, cell->area, cell->cover );
  1058.     }
  1059.     fprintf(stderr, "n" );
  1060.   }
  1061. #endif /* DEBUG_GRAYS */
  1062.   static void
  1063.   gray_hline( RAS_ARG_ TCoord  x,
  1064.                        TCoord  y,
  1065.                        TPos    area,
  1066.                        int     acount )
  1067.   {
  1068.     QT_FT_Span*   span;
  1069.     int        coverage;
  1070.     /* compute the coverage line's coverage, depending on the    */
  1071.     /* outline fill rule                                         */
  1072.     /*                                                           */
  1073.     /* the coverage percentage is area/(PIXEL_BITS*PIXEL_BITS*2) */
  1074.     /*                                                           */
  1075.     coverage = (int)( area >> ( PIXEL_BITS * 2 + 1 - 8 ) );
  1076.                                                     /* use range 0..256 */
  1077.     if ( coverage < 0 )
  1078.       coverage = -coverage;
  1079.     if ( ras.outline.flags & QT_FT_OUTLINE_EVEN_ODD_FILL )
  1080.     {
  1081.       coverage &= 511;
  1082.       if ( coverage > 256 )
  1083.         coverage = 512 - coverage;
  1084.       else if ( coverage == 256 )
  1085.         coverage = 255;
  1086.     }
  1087.     else
  1088.     {
  1089.       /* normal non-zero winding rule */
  1090.       if ( coverage >= 256 )
  1091.         coverage = 255;
  1092.     }
  1093.     y += (TCoord)ras.min_ey;
  1094.     x += (TCoord)ras.min_ex;
  1095.     if ( coverage )
  1096.     {
  1097.       /* see if we can add this span to the current list */
  1098.       span  = ras.gray_spans + ras.num_gray_spans - 1;
  1099.       if ( ras.num_gray_spans > 0             &&
  1100.            span->y == y                    &&
  1101.            (int)span->x + span->len == (int)x &&
  1102.            span->coverage == coverage )
  1103.       {
  1104.         span->len = (unsigned short)( span->len + acount );
  1105.         return;
  1106.       }
  1107.       if ( ras.num_gray_spans >= QT_FT_MAX_GRAY_SPANS )
  1108.       {
  1109.         if ( ras.render_span )
  1110.           ras.render_span( ras.num_gray_spans, ras.gray_spans,
  1111.                            ras.render_span_data );
  1112.         /* ras.render_span( span->y, ras.gray_spans, count ); */
  1113. #ifdef DEBUG_GRAYS
  1114.         if ( 1 )
  1115.         {
  1116.           int  n;
  1117.           fprintf( stderr, "y=%3d ", y );
  1118.           span = ras.gray_spans;
  1119.           for ( n = 0; n < count; n++, span++ )
  1120.             fprintf( stderr, "[%d..%d]:%02x ",
  1121.                      span->x, span->x + span->len - 1, span->coverage );
  1122.           fprintf( stderr, "n" );
  1123.         }
  1124. #endif /* DEBUG_GRAYS */
  1125.         ras.num_gray_spans = 0;
  1126.         span  = ras.gray_spans;
  1127.       }
  1128.       else
  1129.         span++;
  1130.       /* add a gray span to the current list */
  1131.       span->x        = (short)x;
  1132.       span->len      = (unsigned short)acount;
  1133.       span->y = (short)y;
  1134.       span->coverage = (unsigned char)coverage;
  1135.       ras.num_gray_spans++;
  1136.     }
  1137.   }
  1138.   static void
  1139.   gray_sweep( RAS_ARG_ QT_FT_Bitmap*  target )
  1140.   {
  1141.     TCoord  x, y, cover;
  1142.     TArea   area;
  1143.     PCell   start, cur, limit;
  1144.     QT_FT_UNUSED( target );
  1145.     if ( ras.num_cells == 0 )
  1146.       return;
  1147.     cur   = ras.cells;
  1148.     limit = cur + ras.num_cells;
  1149.     cover              = 0;
  1150.     for (;;)
  1151.     {
  1152.       start  = cur;
  1153.       y      = start->y;
  1154.       x      = start->x;
  1155.       area   = start->area;
  1156.       cover += start->cover;
  1157.       /* accumulate all start cells */
  1158.       for (;;)
  1159.       {
  1160.         ++cur;
  1161.         if ( cur >= limit || cur->y != start->y || cur->x != start->x )
  1162.           break;
  1163.         area  += cur->area;
  1164.         cover += cur->cover;
  1165.       }
  1166.       /* if the start cell has a non-null area, we must draw an */
  1167.       /* individual gray pixel there                            */
  1168.       if ( area && x >= 0 )
  1169.       {
  1170.         gray_hline( RAS_VAR_ x, y, cover * ( ONE_PIXEL * 2 ) - area, 1 );
  1171.         x++;
  1172.       }
  1173.       if ( x < 0 )
  1174.         x = 0;
  1175.       if ( cur < limit && start->y == cur->y )
  1176.       {
  1177.         /* draw a gray span between the start cell and the current one */
  1178.         if ( cur->x > x )
  1179.           gray_hline( RAS_VAR_ x, y,
  1180.                       cover * ( ONE_PIXEL * 2 ), cur->x - x );
  1181.       }
  1182.       else
  1183.       {
  1184.         /* draw a gray span until the end of the clipping region */
  1185.         if ( cover && x < ras.max_ex - ras.min_ex )
  1186.           gray_hline( RAS_VAR_ x, y,
  1187.                       cover * ( ONE_PIXEL * 2 ),
  1188.                       (int)( ras.max_ex - x - ras.min_ex ) );
  1189.         cover = 0;
  1190.       }
  1191.       if ( cur >= limit )
  1192.         break;
  1193.     }
  1194. #ifdef DEBUG_GRAYS
  1195.     {
  1196.       int       n;
  1197.       QT_FT_Span*  span;
  1198.       fprintf( stderr, "y=%3d ", y );
  1199.       span = ras.gray_spans;
  1200.       for ( n = 0; n < ras.num_gray_spans; n++, span++ )
  1201.         fprintf( stderr, "[%d..%d]:%02x ",
  1202.                  span->x, span->x + span->len - 1, span->coverage );
  1203.       fprintf( stderr, "n" );
  1204.     }
  1205. #endif /* DEBUG_GRAYS */
  1206.   }
  1207.   /*************************************************************************/
  1208.   /*                                                                       */
  1209.   /*  The following function should only compile in stand_alone mode,      */
  1210.   /*  i.e., when building this component without the rest of FreeType.     */
  1211.   /*                                                                       */
  1212.   /*************************************************************************/
  1213.   /*************************************************************************/
  1214.   /*                                                                       */
  1215.   /* <Function>                                                            */
  1216.   /*    QT_FT_Outline_Decompose                                            */
  1217.   /*                                                                       */
  1218.   /* <Description>                                                         */
  1219.   /*    Walks over an outline's structure to decompose it into individual  */
  1220.   /*    segments and Bezier arcs.  This function is also able to emit      */
  1221.   /*    `move to' and `close to' operations to indicate the start and end  */
  1222.   /*    of new contours in the outline.                                    */
  1223.   /*                                                                       */
  1224.   /* <Input>                                                               */
  1225.   /*    outline        :: A pointer to the source target.                  */
  1226.   /*                                                                       */
  1227.   /*    func_interface :: A table of `emitters', i.e,. function pointers   */
  1228.   /*                      called during decomposition to indicate path     */
  1229.   /*                      operations.                                      */
  1230.   /*                                                                       */
  1231.   /*    user           :: A typeless pointer which is passed to each       */
  1232.   /*                      emitter during the decomposition.  It can be     */
  1233.   /*                      used to store the state during the               */
  1234.   /*                      decomposition.                                   */
  1235.   /*                                                                       */
  1236.   /* <Return>                                                              */
  1237.   /*    Error code.  0 means success.                                      */
  1238.   /*                                                                       */
  1239.   static
  1240.   int  QT_FT_Outline_Decompose( QT_FT_Outline*              outline,
  1241.                              const QT_FT_Outline_Funcs*  func_interface,
  1242.                              void*                    user )
  1243.   {
  1244. #undef SCALED
  1245. #if 0
  1246. #define SCALED( x )  ( ( (x) << shift ) - delta )
  1247. #else
  1248. #define SCALED( x )  (x)
  1249. #endif
  1250.     QT_FT_Vector   v_last;
  1251.     QT_FT_Vector   v_control;
  1252.     QT_FT_Vector   v_start;
  1253.     QT_FT_Vector*  point;
  1254.     QT_FT_Vector*  limit;
  1255.     char*       tags;
  1256.     int   n;         /* index of contour in outline     */
  1257.     int   first;     /* index of first point in contour */
  1258.     int   error;
  1259.     char  tag;       /* current point's state           */
  1260. #if 0
  1261.     int   shift = func_interface->shift;
  1262.     TPos  delta = func_interface->delta;
  1263. #endif
  1264.     first = 0;
  1265.     for ( n = 0; n < outline->n_contours; n++ )
  1266.     {
  1267.       int  last;  /* index of last point in contour */
  1268.       last  = outline->contours[n];
  1269.       limit = outline->points + last;
  1270.       v_start = outline->points[first];
  1271.       v_last  = outline->points[last];
  1272.       v_start.x = SCALED( v_start.x ); v_start.y = SCALED( v_start.y );
  1273.       v_last.x  = SCALED( v_last.x );  v_last.y  = SCALED( v_last.y );
  1274.       v_control = v_start;
  1275.       point = outline->points + first;
  1276.       tags  = outline->tags  + first;
  1277.       tag   = QT_FT_CURVE_TAG( tags[0] );
  1278.       /* A contour cannot start with a cubic control point! */
  1279.       if ( tag == QT_FT_CURVE_TAG_CUBIC )
  1280.         goto Invalid_Outline;
  1281.       /* check first point to determine origin */
  1282.       if ( tag == QT_FT_CURVE_TAG_CONIC )
  1283.       {
  1284.         /* first point is conic control.  Yes, this happens. */
  1285.         if ( QT_FT_CURVE_TAG( outline->tags[last] ) == QT_FT_CURVE_TAG_ON )
  1286.         {
  1287.           /* start at last point if it is on the curve */
  1288.           v_start = v_last;
  1289.           limit--;
  1290.         }
  1291.         else
  1292.         {
  1293.           /* if both first and last points are conic,         */
  1294.           /* start at their middle and record its position    */
  1295.           /* for closure                                      */
  1296.           v_start.x = ( v_start.x + v_last.x ) / 2;
  1297.           v_start.y = ( v_start.y + v_last.y ) / 2;
  1298.           v_last = v_start;
  1299.         }
  1300.         point--;
  1301.         tags--;
  1302.       }
  1303.       error = func_interface->move_to( &v_start, user );
  1304.       if ( error )
  1305.         goto Exit;
  1306.       while ( point < limit )
  1307.       {
  1308.         point++;
  1309.         tags++;
  1310.         tag = QT_FT_CURVE_TAG( tags[0] );
  1311.         switch ( tag )
  1312.         {
  1313.         case QT_FT_CURVE_TAG_ON:  /* emit a single line_to */
  1314.           {
  1315.             QT_FT_Vector  vec;
  1316.             vec.x = SCALED( point->x );
  1317.             vec.y = SCALED( point->y );
  1318.             error = func_interface->line_to( &vec, user );
  1319.             if ( error )
  1320.               goto Exit;
  1321.             continue;
  1322.           }
  1323.         case QT_FT_CURVE_TAG_CONIC:  /* consume conic arcs */
  1324.           {
  1325.             v_control.x = SCALED( point->x );
  1326.             v_control.y = SCALED( point->y );
  1327.           Do_Conic:
  1328.             if ( point < limit )
  1329.             {
  1330.               QT_FT_Vector  vec;
  1331.               QT_FT_Vector  v_middle;
  1332.               point++;
  1333.               tags++;
  1334.               tag = QT_FT_CURVE_TAG( tags[0] );
  1335.               vec.x = SCALED( point->x );
  1336.               vec.y = SCALED( point->y );
  1337.               if ( tag == QT_FT_CURVE_TAG_ON )
  1338.               {
  1339.                 error = func_interface->conic_to( &v_control, &vec, user );
  1340.                 if ( error )
  1341.                   goto Exit;
  1342.                 continue;
  1343.               }
  1344.               if ( tag != QT_FT_CURVE_TAG_CONIC )
  1345.                 goto Invalid_Outline;
  1346.               v_middle.x = ( v_control.x + vec.x ) / 2;
  1347.               v_middle.y = ( v_control.y + vec.y ) / 2;
  1348.               error = func_interface->conic_to( &v_control, &v_middle, user );
  1349.               if ( error )
  1350.                 goto Exit;
  1351.               v_control = vec;
  1352.               goto Do_Conic;
  1353.             }
  1354.             error = func_interface->conic_to( &v_control, &v_start, user );
  1355.             goto Close;
  1356.           }
  1357.         default:  /* QT_FT_CURVE_TAG_CUBIC */
  1358.           {
  1359.             QT_FT_Vector  vec1, vec2;
  1360.             if ( point + 1 > limit                             ||
  1361.                  QT_FT_CURVE_TAG( tags[1] ) != QT_FT_CURVE_TAG_CUBIC )
  1362.               goto Invalid_Outline;
  1363.             point += 2;
  1364.             tags  += 2;
  1365.             vec1.x = SCALED( point[-2].x ); vec1.y = SCALED( point[-2].y );
  1366.             vec2.x = SCALED( point[-1].x ); vec2.y = SCALED( point[-1].y );
  1367.             if ( point <= limit )
  1368.             {
  1369.               QT_FT_Vector  vec;
  1370.               vec.x = SCALED( point->x );
  1371.               vec.y = SCALED( point->y );
  1372.               error = func_interface->cubic_to( &vec1, &vec2, &vec, user );
  1373.               if ( error )
  1374.                 goto Exit;
  1375.               continue;
  1376.             }
  1377.             error = func_interface->cubic_to( &vec1, &vec2, &v_start, user );
  1378.             goto Close;
  1379.           }
  1380.         }
  1381.       }
  1382.       /* close the contour with a line segment */
  1383.       error = func_interface->line_to( &v_start, user );
  1384.    Close:
  1385.       if ( error )
  1386.         goto Exit;
  1387.       first = last + 1;
  1388.     }
  1389.     return 0;
  1390.   Exit:
  1391.     return error;
  1392.   Invalid_Outline:
  1393.     return ErrRaster_Invalid_Outline;
  1394.   }
  1395.   typedef struct  TBand_
  1396.   {
  1397.     TPos  min, max;
  1398.   } TBand;
  1399.   static int
  1400.   gray_convert_glyph_inner( RAS_ARG )
  1401.   {
  1402.     static
  1403.     const QT_FT_Outline_Funcs  func_interface =
  1404.     {
  1405.       (QT_FT_Outline_MoveTo_Func) gray_move_to,
  1406.       (QT_FT_Outline_LineTo_Func) gray_line_to,
  1407.       (QT_FT_Outline_ConicTo_Func)gray_conic_to,
  1408.       (QT_FT_Outline_CubicTo_Func)gray_cubic_to,
  1409.       0,
  1410.       0
  1411.     };
  1412.     volatile int  error = 0;
  1413.     if ( qt_ft_setjmp( ras.jump_buffer ) == 0 )
  1414.     {
  1415.       error = QT_FT_Outline_Decompose( &ras.outline, &func_interface, &ras );
  1416.       gray_record_cell( RAS_VAR );
  1417.     }
  1418.     else
  1419.     {
  1420.       error = ErrRaster_MemoryOverflow;
  1421.     }
  1422.     return error;
  1423.   }
  1424.   static int
  1425.   gray_convert_glyph( RAS_ARG )
  1426.   {
  1427.     TBand            bands[40];
  1428.     TBand* volatile  band;
  1429.     int volatile     n, num_bands;
  1430.     TPos volatile    min, max, max_y;
  1431.     QT_FT_BBox*         clip;
  1432.     ras.num_gray_spans = 0;
  1433.     /* Set up state in the raster object */
  1434.     gray_compute_cbox( RAS_VAR );
  1435.     /* clip to target bitmap, exit if nothing to do */
  1436.     clip = &ras.clip_box;
  1437.     if ( ras.max_ex <= clip->xMin || ras.min_ex >= clip->xMax ||
  1438.          ras.max_ey <= clip->yMin || ras.min_ey >= clip->yMax )
  1439.       return 0;
  1440.     if ( ras.min_ex < clip->xMin ) ras.min_ex = clip->xMin;
  1441.     if ( ras.min_ey < clip->yMin ) ras.min_ey = clip->yMin;
  1442.     if ( ras.max_ex > clip->xMax ) ras.max_ex = clip->xMax;
  1443.     if ( ras.max_ey > clip->yMax ) ras.max_ey = clip->yMax;
  1444.     /* simple heuristic used to speed-up the bezier decomposition -- see */
  1445.     /* the code in gray_render_conic() and gray_render_cubic() for more  */
  1446.     /* details                                                           */
  1447.     ras.conic_level = 32;
  1448.     ras.cubic_level = 16;
  1449.     {
  1450.       int level = 0;
  1451.       if ( ras.max_ex > 24 || ras.max_ey > 24 )
  1452.         level++;
  1453.       if ( ras.max_ex > 120 || ras.max_ey > 120 )
  1454.         level++;
  1455.       ras.conic_level <<= level;
  1456.       ras.cubic_level <<= level;
  1457.     }
  1458.     /* setup vertical bands */
  1459.     num_bands = (int)( ( ras.max_ey - ras.min_ey ) / ras.band_size );
  1460.     if ( num_bands == 0 )  num_bands = 1;
  1461.     if ( num_bands >= 39 ) num_bands = 39;
  1462.     ras.band_shoot = 0;
  1463.     min   = ras.min_ey;
  1464.     max_y = ras.max_ey;
  1465.     for ( n = 0; n < num_bands; n++, min = max )
  1466.     {
  1467.       max = min + ras.band_size;
  1468.       if ( n == num_bands - 1 || max > max_y )
  1469.         max = max_y;
  1470.       bands[0].min = min;
  1471.       bands[0].max = max;
  1472.       band         = bands;
  1473.       while ( band >= bands )
  1474.       {
  1475.         TPos  bottom, top, middle;
  1476.         int   error;
  1477.         ras.num_cells = 0;
  1478.         ras.invalid   = 1;
  1479.         ras.min_ey    = band->min;
  1480.         ras.max_ey    = band->max;
  1481. #if 1
  1482.         error = gray_convert_glyph_inner( RAS_VAR );
  1483. #else
  1484.         error = QT_FT_Outline_Decompose( outline, &func_interface, &ras ) ||
  1485.                 gray_record_cell( RAS_VAR );
  1486. #endif
  1487.         if ( !error )
  1488.         {
  1489. #ifdef SHELL_SORT
  1490.           gray_shell_sort( ras.cells, ras.num_cells );
  1491. #else
  1492.           gray_quick_sort( ras.cells, ras.num_cells );
  1493. #endif
  1494. #ifdef DEBUG_GRAYS
  1495.           gray_check_sort( ras.cells, ras.num_cells );
  1496.           gray_dump_cells( RAS_VAR );
  1497. #endif
  1498.           gray_sweep( RAS_VAR_  &ras.target );
  1499.           band--;
  1500.           continue;
  1501.         }
  1502.         else if ( error != ErrRaster_MemoryOverflow )
  1503.           return 1;
  1504.         /* render pool overflow, we will reduce the render band by half */
  1505.         bottom = band->min;
  1506.         top    = band->max;
  1507.         middle = bottom + ( ( top - bottom ) >> 1 );
  1508.         /* waoow! This is too complex for a single scanline, something */
  1509.         /* must be really rotten here!                                 */
  1510.         if ( middle == bottom )
  1511.         {
  1512. #ifdef DEBUG_GRAYS
  1513.           fprintf( stderr, "Rotten glyph!n" );
  1514. #endif
  1515.           /* == Raster_Err_OutOfMemory in qblackraster.c */
  1516.           return -6;
  1517.         }
  1518.         if ( bottom-top >= ras.band_size )
  1519.           ras.band_shoot++;
  1520.         band[1].min = bottom;
  1521.         band[1].max = middle;
  1522.         band[0].min = middle;
  1523.         band[0].max = top;
  1524.         band++;
  1525.       }
  1526.     }
  1527.     if ( ras.render_span && ras.num_gray_spans > 0 )
  1528.       ras.render_span( ras.num_gray_spans,
  1529.                        ras.gray_spans, ras.render_span_data );
  1530.     if ( ras.band_shoot > 8 && ras.band_size > 16 )
  1531.       ras.band_size = ras.band_size / 2;
  1532.     return 0;
  1533.   }
  1534.   static int
  1535.   gray_raster_render( PRaster            raster,
  1536.                       QT_FT_Raster_Params*  params )
  1537.   {
  1538.     QT_FT_Outline*  outline = (QT_FT_Outline*)params->source;
  1539.     QT_FT_Bitmap*   target_map = params->target;
  1540.     if ( !raster || !raster->cells || !raster->max_cells )
  1541.       return -1;
  1542.     /* return immediately if the outline is empty */
  1543.     if ( outline->n_points == 0 || outline->n_contours <= 0 )
  1544.       return 0;
  1545.     if ( !outline || !outline->contours || !outline->points )
  1546.       return ErrRaster_Invalid_Outline;
  1547.     if ( outline->n_points !=
  1548.            outline->contours[outline->n_contours - 1] + 1 )
  1549.       return ErrRaster_Invalid_Outline;
  1550.     /* if direct mode is not set, we must have a target bitmap */
  1551.     if ( ( params->flags & QT_FT_RASTER_FLAG_DIRECT ) == 0 &&
  1552.          ( !target_map || !target_map->buffer )         )
  1553.       return -1;
  1554.     /* this version does not support monochrome rendering */
  1555.     if ( !( params->flags & QT_FT_RASTER_FLAG_AA ) )
  1556.       return ErrRaster_Invalid_Mode;
  1557.     /* compute clipping box */
  1558.     if ( ( params->flags & QT_FT_RASTER_FLAG_DIRECT ) == 0 )
  1559.     {
  1560.       /* compute clip box from target pixmap */
  1561.       ras.clip_box.xMin = 0;
  1562.       ras.clip_box.yMin = 0;
  1563.       ras.clip_box.xMax = target_map->width;
  1564.       ras.clip_box.yMax = target_map->rows;
  1565.     }
  1566.     else if ( params->flags & QT_FT_RASTER_FLAG_CLIP )
  1567.     {
  1568.       ras.clip_box = params->clip_box;
  1569.     }
  1570.     else
  1571.     {
  1572.       ras.clip_box.xMin = -32768L;
  1573.       ras.clip_box.yMin = -32768L;
  1574.       ras.clip_box.xMax =  32767L;
  1575.       ras.clip_box.yMax =  32767L;
  1576.     }
  1577.     ras.outline   = *outline;
  1578.     ras.num_cells = 0;
  1579.     ras.invalid   = 1;
  1580.     if ( target_map )
  1581.       ras.target = *target_map;
  1582.     ras.render_span      = (QT_FT_Raster_Span_Func)gray_render_span;
  1583.     ras.render_span_data = &ras;
  1584.     if ( params->flags & QT_FT_RASTER_FLAG_DIRECT )
  1585.     {
  1586.       ras.render_span      = (QT_FT_Raster_Span_Func)params->gray_spans;
  1587.       ras.render_span_data = params->user;
  1588.     }
  1589.     return gray_convert_glyph( (PRaster)raster );
  1590.   }
  1591.   /**** RASTER OBJECT CREATION: In standalone mode, we simply use *****/
  1592.   /****                         a static object.                  *****/
  1593. #ifdef GRAYS_USE_GAMMA
  1594.   /* initialize the "gamma" table. Yes, this is really a crummy function */
  1595.   /* but the results look pretty good for something that simple.         */
  1596.   /*                                                                     */
  1597. #define M_MAX  255
  1598. #define M_X    128
  1599. #define M_Y    192
  1600.   static void
  1601.   grays_init_gamma( PRaster  raster )
  1602.   {
  1603.     unsigned int  x, a;
  1604.     for ( x = 0; x < 256; x++ )
  1605.     {
  1606.       if ( x <= M_X )
  1607.         a = ( x * M_Y + M_X / 2) / M_X;
  1608.       else
  1609.         a = M_Y + ( ( x - M_X ) * ( M_MAX - M_Y ) +
  1610.             ( M_MAX - M_X ) / 2 ) / ( M_MAX - M_X );
  1611.       raster->gamma[x] = (unsigned char)a;
  1612.     }
  1613.   }
  1614. #endif /* GRAYS_USE_GAMMA */
  1615.   static int
  1616.   gray_raster_new( void*       memory,
  1617.                    QT_FT_Raster*  araster )
  1618.   {
  1619.     if (memory)
  1620.         fprintf(stderr, "gray_raster_new(), memory ignored");
  1621.     memory = malloc(sizeof(TRaster));
  1622.     QT_FT_MEM_ZERO(memory, sizeof(TRaster));
  1623.     *araster = (QT_FT_Raster) memory;
  1624. #ifdef GRAYS_USE_GAMMA
  1625.     grays_init_gamma( (PRaster)*araster );
  1626. #endif
  1627.     return 0;
  1628.   }
  1629.   static void
  1630.   gray_raster_done( QT_FT_Raster  raster )
  1631.   {
  1632.     free(raster);
  1633.   }
  1634.   static void
  1635.   gray_raster_reset( QT_FT_Raster    raster,
  1636.                      const char*  pool_base,
  1637.                      long         pool_size )
  1638.   {
  1639.     PRaster  rast = (PRaster)raster;
  1640.     if ( raster && pool_base && pool_size >= 4096 )
  1641.       gray_init_cells( rast, (char*)pool_base, pool_size );
  1642.     rast->band_size  = (int)( ( pool_size / sizeof ( TCell ) ) / 8 );
  1643.   }
  1644.   const QT_FT_Raster_Funcs  qt_ft_grays_raster =
  1645.   {
  1646.     QT_FT_GLYPH_FORMAT_OUTLINE,
  1647.     (QT_FT_Raster_New_Func)     gray_raster_new,
  1648.     (QT_FT_Raster_Reset_Func)   gray_raster_reset,
  1649.     (QT_FT_Raster_Set_Mode_Func)0,
  1650.     (QT_FT_Raster_Render_Func)  gray_raster_render,
  1651.     (QT_FT_Raster_Done_Func)    gray_raster_done
  1652.   };
  1653. /* END */