1 /****************************************************************************
   2  *
   3  * ftgrays.c
   4  *
   5  *   A new `perfect' anti-aliasing renderer (body).
   6  *
   7  * Copyright (C) 2000-2019 by
   8  * David Turner, Robert Wilhelm, and Werner Lemberg.
   9  *
  10  * This file is part of the FreeType project, and may only be used,
  11  * modified, and distributed under the terms of the FreeType project
  12  * license, LICENSE.TXT.  By continuing to use, modify, or distribute
  13  * this file you indicate that you have read the license and
  14  * understand and accept it fully.
  15  *
  16  */
  17 
  18   /**************************************************************************
  19    *
  20    * This file can be compiled without the rest of the FreeType engine, by
  21    * defining the STANDALONE_ macro when compiling it.  You also need to
  22    * put the files `ftgrays.h' and `ftimage.h' into the current
  23    * compilation directory.  Typically, you could do something like
  24    *
  25    * - copy `src/smooth/ftgrays.c' (this file) to your current directory
  26    *
  27    * - copy `include/freetype/ftimage.h' and `src/smooth/ftgrays.h' to the
  28    *   same directory
  29    *
  30    * - compile `ftgrays' with the STANDALONE_ macro defined, as in
  31    *
  32    *     cc -c -DSTANDALONE_ ftgrays.c
  33    *
  34    * The renderer can be initialized with a call to
  35    * `ft_gray_raster.raster_new'; an anti-aliased bitmap can be generated
  36    * with a call to `ft_gray_raster.raster_render'.
  37    *
  38    * See the comments and documentation in the file `ftimage.h' for more
  39    * details on how the raster works.
  40    *
  41    */
  42 
  43   /**************************************************************************
  44    *
  45    * This is a new anti-aliasing scan-converter for FreeType 2.  The
  46    * algorithm used here is _very_ different from the one in the standard
  47    * `ftraster' module.  Actually, `ftgrays' computes the _exact_
  48    * coverage of the outline on each pixel cell by straight segments.
  49    *
  50    * It is based on ideas that I initially found in Raph Levien's
  51    * excellent LibArt graphics library (see https://www.levien.com/libart
  52    * for more information, though the web pages do not tell anything
  53    * about the renderer; you'll have to dive into the source code to
  54    * understand how it works).
  55    *
  56    * Note, however, that this is a _very_ different implementation
  57    * compared to Raph's.  Coverage information is stored in a very
  58    * different way, and I don't use sorted vector paths.  Also, it doesn't
  59    * use floating point values.
  60    *
  61    * Bézier segments are flattened by splitting them until their deviation
  62    * from straight line becomes much smaller than a pixel.  Therefore, the
  63    * pixel coverage by a Bézier curve is calculated approximately.  To
  64    * estimate the deviation, we use the distance from the control point
  65    * to the conic chord centre or the cubic chord trisection.  These
  66    * distances vanish fast after each split.  In the conic case, they vanish
  67    * predictably and the number of necessary splits can be calculated.
  68    *
  69    * This renderer has the following advantages:
  70    *
  71    * - It doesn't need an intermediate bitmap.  Instead, one can supply a
  72    *   callback function that will be called by the renderer to draw gray
  73    *   spans on any target surface.  You can thus do direct composition on
  74    *   any kind of bitmap, provided that you give the renderer the right
  75    *   callback.
  76    *
  77    * - A perfect anti-aliaser, i.e., it computes the _exact_ coverage on
  78    *   each pixel cell by straight segments.
  79    *
  80    * - It performs a single pass on the outline (the `standard' FT2
  81    *   renderer makes two passes).
  82    *
  83    * - It can easily be modified to render to _any_ number of gray levels
  84    *   cheaply.
  85    *
  86    * - For small (< 80) pixel sizes, it is faster than the standard
  87    *   renderer.
  88    *
  89    */
  90 
  91 
  92   /**************************************************************************
  93    *
  94    * The macro FT_COMPONENT is used in trace mode.  It is an implicit
  95    * parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log
  96    * messages during execution.
  97    */
  98 #undef  FT_COMPONENT
  99 #define FT_COMPONENT  smooth
 100 
 101 
 102 #ifdef STANDALONE_
 103 
 104 
 105   /* The size in bytes of the render pool used by the scan-line converter  */
 106   /* to do all of its work.                                                */
 107 #define FT_RENDER_POOL_SIZE  16384L
 108 
 109 
 110   /* Auxiliary macros for token concatenation. */
 111 #define FT_ERR_XCAT( x, y )  x ## y
 112 #define FT_ERR_CAT( x, y )   FT_ERR_XCAT( x, y )
 113 
 114 #define FT_BEGIN_STMNT  do {
 115 #define FT_END_STMNT    } while ( 0 )
 116 
 117 #define FT_MIN( a, b )  ( (a) < (b) ? (a) : (b) )
 118 #define FT_MAX( a, b )  ( (a) > (b) ? (a) : (b) )
 119 #define FT_ABS( a )     ( (a) < 0 ? -(a) : (a) )
 120 
 121 
 122   /*
 123    * Approximate sqrt(x*x+y*y) using the `alpha max plus beta min'
 124    * algorithm.  We use alpha = 1, beta = 3/8, giving us results with a
 125    * largest error less than 7% compared to the exact value.
 126    */
 127 #define FT_HYPOT( x, y )                 \
 128           ( x = FT_ABS( x ),             \
 129             y = FT_ABS( y ),             \
 130             x > y ? x + ( 3 * y >> 3 )   \
 131                   : y + ( 3 * x >> 3 ) )
 132 
 133 
 134   /* define this to dump debugging information */
 135 /* #define FT_DEBUG_LEVEL_TRACE */
 136 
 137 
 138 #ifdef FT_DEBUG_LEVEL_TRACE
 139 #include <stdio.h>
 140 #include <stdarg.h>
 141 #endif
 142 
 143 #include <stddef.h>
 144 #include <string.h>
 145 #include <setjmp.h>
 146 #include <limits.h>
 147 #define FT_CHAR_BIT   CHAR_BIT
 148 #define FT_UINT_MAX   UINT_MAX
 149 #define FT_INT_MAX    INT_MAX
 150 #define FT_ULONG_MAX  ULONG_MAX
 151 
 152 #define ADD_LONG( a, b )                                    \
 153           (long)( (unsigned long)(a) + (unsigned long)(b) )
 154 #define SUB_LONG( a, b )                                    \
 155           (long)( (unsigned long)(a) - (unsigned long)(b) )
 156 #define MUL_LONG( a, b )                                    \
 157           (long)( (unsigned long)(a) * (unsigned long)(b) )
 158 #define NEG_LONG( a )                                       \
 159           (long)( -(unsigned long)(a) )
 160 
 161 
 162 #define ft_memset   memset
 163 
 164 #define ft_setjmp   setjmp
 165 #define ft_longjmp  longjmp
 166 #define ft_jmp_buf  jmp_buf
 167 
 168 typedef ptrdiff_t  FT_PtrDist;
 169 
 170 
 171 #define ErrRaster_Invalid_Mode      -2
 172 #define ErrRaster_Invalid_Outline   -1
 173 #define ErrRaster_Invalid_Argument  -3
 174 #define ErrRaster_Memory_Overflow   -4
 175 
 176 #define FT_BEGIN_HEADER
 177 #define FT_END_HEADER
 178 
 179 #include "ftimage.h"
 180 #include "ftgrays.h"
 181 
 182 
 183   /* This macro is used to indicate that a function parameter is unused. */
 184   /* Its purpose is simply to reduce compiler warnings.  Note also that  */
 185   /* simply defining it as `(void)x' doesn't avoid warnings with certain */
 186   /* ANSI compilers (e.g. LCC).                                          */
 187 #define FT_UNUSED( x )  (x) = (x)
 188 
 189 
 190   /* we only use level 5 & 7 tracing messages; cf. ftdebug.h */
 191 
 192 #ifdef FT_DEBUG_LEVEL_TRACE
 193 
 194   void
 195   FT_Message( const char*  fmt,
 196               ... )
 197   {
 198     va_list  ap;
 199 
 200 
 201     va_start( ap, fmt );
 202     vfprintf( stderr, fmt, ap );
 203     va_end( ap );
 204   }
 205 
 206 
 207   /* empty function useful for setting a breakpoint to catch errors */
 208   int
 209   FT_Throw( int          error,
 210             int          line,
 211             const char*  file )
 212   {
 213     FT_UNUSED( error );
 214     FT_UNUSED( line );
 215     FT_UNUSED( file );
 216 
 217     return 0;
 218   }
 219 
 220 
 221   /* we don't handle tracing levels in stand-alone mode; */
 222 #ifndef FT_TRACE5
 223 #define FT_TRACE5( varformat )  FT_Message varformat
 224 #endif
 225 #ifndef FT_TRACE7
 226 #define FT_TRACE7( varformat )  FT_Message varformat
 227 #endif
 228 #ifndef FT_ERROR
 229 #define FT_ERROR( varformat )   FT_Message varformat
 230 #endif
 231 
 232 #define FT_THROW( e )                               \
 233           ( FT_Throw( FT_ERR_CAT( ErrRaster_, e ),  \
 234                       __LINE__,                     \
 235                       __FILE__ )                  | \
 236             FT_ERR_CAT( ErrRaster_, e )           )
 237 
 238 #else /* !FT_DEBUG_LEVEL_TRACE */
 239 
 240 #define FT_TRACE5( x )  do { } while ( 0 )     /* nothing */
 241 #define FT_TRACE7( x )  do { } while ( 0 )     /* nothing */
 242 #define FT_ERROR( x )   do { } while ( 0 )     /* nothing */
 243 #define FT_THROW( e )   FT_ERR_CAT( ErrRaster_, e )
 244 
 245 
 246 #endif /* !FT_DEBUG_LEVEL_TRACE */
 247 
 248 
 249 #define FT_DEFINE_OUTLINE_FUNCS( class_,               \
 250                                  move_to_, line_to_,   \
 251                                  conic_to_, cubic_to_, \
 252                                  shift_, delta_ )      \
 253           static const FT_Outline_Funcs class_ =       \
 254           {                                            \
 255             move_to_,                                  \
 256             line_to_,                                  \
 257             conic_to_,                                 \
 258             cubic_to_,                                 \
 259             shift_,                                    \
 260             delta_                                     \
 261          };
 262 
 263 #define FT_DEFINE_RASTER_FUNCS( class_, glyph_format_,            \
 264                                 raster_new_, raster_reset_,       \
 265                                 raster_set_mode_, raster_render_, \
 266                                 raster_done_ )                    \
 267           const FT_Raster_Funcs class_ =                          \
 268           {                                                       \
 269             glyph_format_,                                        \
 270             raster_new_,                                          \
 271             raster_reset_,                                        \
 272             raster_set_mode_,                                     \
 273             raster_render_,                                       \
 274             raster_done_                                          \
 275          };
 276 
 277 
 278 #else /* !STANDALONE_ */
 279 
 280 
 281 #include <ft2build.h>
 282 #include "ftgrays.h"
 283 #include FT_INTERNAL_OBJECTS_H
 284 #include FT_INTERNAL_DEBUG_H
 285 #include FT_INTERNAL_CALC_H
 286 #include FT_OUTLINE_H
 287 
 288 #include "ftsmerrs.h"
 289 
 290 #define Smooth_Err_Invalid_Mode     Smooth_Err_Cannot_Render_Glyph
 291 #define Smooth_Err_Memory_Overflow  Smooth_Err_Out_Of_Memory
 292 #define ErrRaster_Memory_Overflow   Smooth_Err_Out_Of_Memory
 293 
 294 
 295 #endif /* !STANDALONE_ */
 296 
 297 
 298 #ifndef FT_MEM_SET
 299 #define FT_MEM_SET( d, s, c )  ft_memset( d, s, c )
 300 #endif
 301 
 302 #ifndef FT_MEM_ZERO
 303 #define FT_MEM_ZERO( dest, count )  FT_MEM_SET( dest, 0, count )
 304 #endif
 305 
 306 #ifndef FT_ZERO
 307 #define FT_ZERO( p )  FT_MEM_ZERO( p, sizeof ( *(p) ) )
 308 #endif
 309 
 310   /* as usual, for the speed hungry :-) */
 311 
 312 #undef RAS_ARG
 313 #undef RAS_ARG_
 314 #undef RAS_VAR
 315 #undef RAS_VAR_
 316 
 317 #ifndef FT_STATIC_RASTER
 318 
 319 #define RAS_ARG   gray_PWorker  worker
 320 #define RAS_ARG_  gray_PWorker  worker,
 321 
 322 #define RAS_VAR   worker
 323 #define RAS_VAR_  worker,
 324 
 325 #else /* FT_STATIC_RASTER */
 326 
 327 #define RAS_ARG   void
 328 #define RAS_ARG_  /* empty */
 329 #define RAS_VAR   /* empty */
 330 #define RAS_VAR_  /* empty */
 331 
 332 #endif /* FT_STATIC_RASTER */
 333 
 334 
 335   /* must be at least 6 bits! */
 336 #define PIXEL_BITS  8
 337 
 338 #define ONE_PIXEL       ( 1 << PIXEL_BITS )
 339 #define TRUNC( x )      (TCoord)( (x) >> PIXEL_BITS )
 340 #define FRACT( x )      (TCoord)( (x) & ( ONE_PIXEL - 1 ) )
 341 
 342 #if PIXEL_BITS >= 6
 343 #define UPSCALE( x )    ( (x) * ( ONE_PIXEL >> 6 ) )
 344 #define DOWNSCALE( x )  ( (x) >> ( PIXEL_BITS - 6 ) )
 345 #else
 346 #define UPSCALE( x )    ( (x) >> ( 6 - PIXEL_BITS ) )
 347 #define DOWNSCALE( x )  ( (x) * ( 64 >> PIXEL_BITS ) )
 348 #endif
 349 
 350 
 351   /* Compute `dividend / divisor' and return both its quotient and     */
 352   /* remainder, cast to a specific type.  This macro also ensures that */
 353   /* the remainder is always positive.  We use the remainder to keep   */
 354   /* track of accumulating errors and compensate for them.             */
 355 #define FT_DIV_MOD( type, dividend, divisor, quotient, remainder ) \
 356   FT_BEGIN_STMNT                                                   \
 357     (quotient)  = (type)( (dividend) / (divisor) );                \
 358     (remainder) = (type)( (dividend) % (divisor) );                \
 359     if ( (remainder) < 0 )                                         \
 360     {                                                              \
 361       (quotient)--;                                                \
 362       (remainder) += (type)(divisor);                              \
 363     }                                                              \
 364   FT_END_STMNT
 365 
 366 #ifdef  __arm__
 367   /* Work around a bug specific to GCC which make the compiler fail to */
 368   /* optimize a division and modulo operation on the same parameters   */
 369   /* into a single call to `__aeabi_idivmod'.  See                     */
 370   /*                                                                   */
 371   /*  https://gcc.gnu.org/bugzilla/show_bug.cgi?id=43721               */
 372 #undef FT_DIV_MOD
 373 #define FT_DIV_MOD( type, dividend, divisor, quotient, remainder ) \
 374   FT_BEGIN_STMNT                                                   \
 375     (quotient)  = (type)( (dividend) / (divisor) );                \
 376     (remainder) = (type)( (dividend) - (quotient) * (divisor) );   \
 377     if ( (remainder) < 0 )                                         \
 378     {                                                              \
 379       (quotient)--;                                                \
 380       (remainder) += (type)(divisor);                              \
 381     }                                                              \
 382   FT_END_STMNT
 383 #endif /* __arm__ */
 384 
 385 
 386   /* These macros speed up repetitive divisions by replacing them */
 387   /* with multiplications and right shifts.                       */
 388 #define FT_UDIVPREP( c, b )                                        \
 389   long  b ## _r = c ? (long)( FT_ULONG_MAX >> PIXEL_BITS ) / ( b ) \
 390                     : 0
 391 #define FT_UDIV( a, b )                                                \
 392   (TCoord)( ( (unsigned long)( a ) * (unsigned long)( b ## _r ) ) >>   \
 393             ( sizeof( long ) * FT_CHAR_BIT - PIXEL_BITS ) )
 394 
 395 
 396   /**************************************************************************
 397    *
 398    * TYPE DEFINITIONS
 399    */
 400 
 401   /* don't change the following types to FT_Int or FT_Pos, since we might */
 402   /* need to define them to "float" or "double" when experimenting with   */
 403   /* new algorithms                                                       */
 404 
 405   typedef long  TPos;     /* subpixel coordinate               */
 406   typedef int   TCoord;   /* integer scanline/pixel coordinate */
 407   typedef int   TArea;    /* cell areas, coordinate products   */
 408 
 409 
 410   typedef struct TCell_*  PCell;
 411 
 412   typedef struct  TCell_
 413   {
 414     TCoord  x;     /* same with gray_TWorker.ex    */
 415     TCoord  cover; /* same with gray_TWorker.cover */
 416     TArea   area;
 417     PCell   next;
 418 
 419   } TCell;
 420 
 421   typedef struct TPixmap_
 422   {
 423     unsigned char*  origin;  /* pixmap origin at the bottom-left */
 424     int             pitch;   /* pitch to go down one row */
 425 
 426   } TPixmap;
 427 
 428   /* maximum number of gray cells in the buffer */
 429 #if FT_RENDER_POOL_SIZE > 2048
 430 #define FT_MAX_GRAY_POOL  ( FT_RENDER_POOL_SIZE / sizeof ( TCell ) )
 431 #else
 432 #define FT_MAX_GRAY_POOL  ( 2048 / sizeof ( TCell ) )
 433 #endif
 434 
 435   /* FT_Span buffer size for direct rendering only */
 436 #define FT_MAX_GRAY_SPANS  10
 437 
 438 
 439 #if defined( _MSC_VER )      /* Visual C++ (and Intel C++) */
 440   /* We disable the warning `structure was padded due to   */
 441   /* __declspec(align())' in order to compile cleanly with */
 442   /* the maximum level of warnings.                        */
 443 #pragma warning( push )
 444 #pragma warning( disable : 4324 )
 445 #endif /* _MSC_VER */
 446 
 447   typedef struct  gray_TWorker_
 448   {
 449     ft_jmp_buf  jump_buffer;
 450 
 451     TCoord  ex, ey;
 452     TCoord  min_ex, max_ex;
 453     TCoord  min_ey, max_ey;
 454 
 455     TArea   area;
 456     TCoord  cover;
 457     int     invalid;
 458 
 459     PCell*      ycells;
 460     PCell       cells;
 461     FT_PtrDist  max_cells;
 462     FT_PtrDist  num_cells;
 463 
 464     TPos    x,  y;
 465 
 466     FT_Outline  outline;
 467     TPixmap     target;
 468 
 469     FT_Raster_Span_Func  render_span;
 470     void*                render_span_data;
 471     FT_Span              spans[FT_MAX_GRAY_SPANS];
 472     int                  num_spans;
 473 
 474   } gray_TWorker, *gray_PWorker;
 475 
 476 #if defined( _MSC_VER )
 477 #pragma warning( pop )
 478 #endif
 479 
 480 
 481 #ifndef FT_STATIC_RASTER
 482 #define ras  (*worker)
 483 #else
 484   static gray_TWorker  ras;
 485 #endif
 486 
 487 
 488   typedef struct gray_TRaster_
 489   {
 490     void*         memory;
 491 
 492   } gray_TRaster, *gray_PRaster;
 493 
 494 
 495 #ifdef FT_DEBUG_LEVEL_TRACE
 496 
 497   /* to be called while in the debugger --                                */
 498   /* this function causes a compiler warning since it is unused otherwise */
 499   static void
 500   gray_dump_cells( RAS_ARG )
 501   {
 502     int  y;
 503 
 504 
 505     for ( y = ras.min_ey; y < ras.max_ey; y++ )
 506     {
 507       PCell  cell = ras.ycells[y - ras.min_ey];
 508 
 509 
 510       printf( "%3d:", y );
 511 
 512       for ( ; cell != NULL; cell = cell->next )
 513         printf( " (%3d, c:%4d, a:%6d)",
 514                 cell->x, cell->cover, cell->area );
 515       printf( "\n" );
 516     }
 517   }
 518 
 519 #endif /* FT_DEBUG_LEVEL_TRACE */
 520 
 521 
 522   /**************************************************************************
 523    *
 524    * Record the current cell in the linked list.
 525    */
 526   static void
 527   gray_record_cell( RAS_ARG )
 528   {
 529     PCell  *pcell, cell;
 530     TCoord  x = ras.ex;
 531 
 532 
 533     pcell = &ras.ycells[ras.ey - ras.min_ey];
 534     while ( ( cell = *pcell ) )
 535     {
 536       if ( cell->x > x )
 537         break;
 538 
 539       if ( cell->x == x )
 540         goto Found;
 541 
 542       pcell = &cell->next;
 543     }
 544 
 545     if ( ras.num_cells >= ras.max_cells )
 546       ft_longjmp( ras.jump_buffer, 1 );
 547 
 548     /* insert new cell */
 549     cell        = ras.cells + ras.num_cells++;
 550     cell->x     = x;
 551     cell->area  = ras.area;
 552     cell->cover = ras.cover;
 553 
 554     cell->next  = *pcell;
 555     *pcell      = cell;
 556 
 557     return;
 558 
 559   Found:
 560     /* update old cell */
 561     cell->area  += ras.area;
 562     cell->cover += ras.cover;
 563   }
 564 
 565 
 566   /**************************************************************************
 567    *
 568    * Set the current cell to a new position.
 569    */
 570   static void
 571   gray_set_cell( RAS_ARG_ TCoord  ex,
 572                           TCoord  ey )
 573   {
 574     /* Move the cell pointer to a new position.  We set the `invalid'      */
 575     /* flag to indicate that the cell isn't part of those we're interested */
 576     /* in during the render phase.  This means that:                       */
 577     /*                                                                     */
 578     /* . the new vertical position must be within min_ey..max_ey-1.        */
 579     /* . the new horizontal position must be strictly less than max_ex     */
 580     /*                                                                     */
 581     /* Note that if a cell is to the left of the clipping region, it is    */
 582     /* actually set to the (min_ex-1) horizontal position.                 */
 583 
 584     /* record the current one if it is valid and substantial */
 585     if ( !ras.invalid && ( ras.area || ras.cover ) )
 586       gray_record_cell( RAS_VAR );
 587 
 588     ras.area  = 0;
 589     ras.cover = 0;
 590     ras.ex    = FT_MAX( ex, ras.min_ex - 1 );
 591     ras.ey    = ey;
 592 
 593     ras.invalid = ( ey >= ras.max_ey || ey < ras.min_ey ||
 594                     ex >= ras.max_ex );
 595   }
 596 
 597 
 598 #ifndef FT_LONG64
 599 
 600   /**************************************************************************
 601    *
 602    * Render a scanline as one or more cells.
 603    */
 604   static void
 605   gray_render_scanline( RAS_ARG_ TCoord  ey,
 606                                  TPos    x1,
 607                                  TCoord  y1,
 608                                  TPos    x2,
 609                                  TCoord  y2 )
 610   {
 611     TCoord  ex1, ex2, fx1, fx2, first, dy, delta, mod;
 612     TPos    p, dx;
 613     int     incr;
 614 
 615 
 616     ex1 = TRUNC( x1 );
 617     ex2 = TRUNC( x2 );
 618 
 619     /* trivial case.  Happens often */
 620     if ( y1 == y2 )
 621     {
 622       gray_set_cell( RAS_VAR_ ex2, ey );
 623       return;
 624     }
 625 
 626     fx1   = FRACT( x1 );
 627     fx2   = FRACT( x2 );
 628 
 629     /* everything is located in a single cell.  That is easy! */
 630     /*                                                        */
 631     if ( ex1 == ex2 )
 632       goto End;
 633 
 634     /* ok, we'll have to render a run of adjacent cells on the same */
 635     /* scanline...                                                  */
 636     /*                                                              */
 637     dx = x2 - x1;
 638     dy = y2 - y1;
 639 
 640     if ( dx > 0 )
 641     {
 642       p     = ( ONE_PIXEL - fx1 ) * dy;
 643       first = ONE_PIXEL;
 644       incr  = 1;
 645     }
 646     else
 647     {
 648       p     = fx1 * dy;
 649       first = 0;
 650       incr  = -1;
 651       dx    = -dx;
 652     }
 653 
 654     /* the fractional part of y-delta is mod/dx. It is essential to */
 655     /* keep track of its accumulation for accurate rendering.       */
 656     /* XXX: y-delta and x-delta below should be related.            */
 657     FT_DIV_MOD( TCoord, p, dx, delta, mod );
 658 
 659     ras.area  += (TArea)( ( fx1 + first ) * delta );
 660     ras.cover += delta;
 661     y1        += delta;
 662     ex1       += incr;
 663     gray_set_cell( RAS_VAR_ ex1, ey );
 664 
 665     if ( ex1 != ex2 )
 666     {
 667       TCoord  lift, rem;
 668 
 669 
 670       p = ONE_PIXEL * dy;
 671       FT_DIV_MOD( TCoord, p, dx, lift, rem );
 672 
 673       do
 674       {
 675         delta = lift;
 676         mod  += rem;
 677         if ( mod >= (TCoord)dx )
 678         {
 679           mod -= (TCoord)dx;
 680           delta++;
 681         }
 682 
 683         ras.area  += (TArea)( ONE_PIXEL * delta );
 684         ras.cover += delta;
 685         y1        += delta;
 686         ex1       += incr;
 687         gray_set_cell( RAS_VAR_ ex1, ey );
 688       } while ( ex1 != ex2 );
 689     }
 690 
 691     fx1 = ONE_PIXEL - first;
 692 
 693   End:
 694     dy = y2 - y1;
 695 
 696     ras.area  += (TArea)( ( fx1 + fx2 ) * dy );
 697     ras.cover += dy;
 698   }
 699 
 700 
 701   /**************************************************************************
 702    *
 703    * Render a given line as a series of scanlines.
 704    */
 705   static void
 706   gray_render_line( RAS_ARG_ TPos  to_x,
 707                              TPos  to_y )
 708   {
 709     TCoord  ey1, ey2, fy1, fy2, first, delta, mod;
 710     TPos    p, dx, dy, x, x2;
 711     int     incr;
 712 
 713 
 714     ey1 = TRUNC( ras.y );
 715     ey2 = TRUNC( to_y );     /* if (ey2 >= ras.max_ey) ey2 = ras.max_ey-1; */
 716 
 717     /* perform vertical clipping */
 718     if ( ( ey1 >= ras.max_ey && ey2 >= ras.max_ey ) ||
 719          ( ey1 <  ras.min_ey && ey2 <  ras.min_ey ) )
 720       goto End;
 721 
 722     fy1 = FRACT( ras.y );
 723     fy2 = FRACT( to_y );
 724 
 725     /* everything is on a single scanline */
 726     if ( ey1 == ey2 )
 727     {
 728       gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, to_x, fy2 );
 729       goto End;
 730     }
 731 
 732     dx = to_x - ras.x;
 733     dy = to_y - ras.y;
 734 
 735     /* vertical line - avoid calling gray_render_scanline */
 736     if ( dx == 0 )
 737     {
 738       TCoord  ex     = TRUNC( ras.x );
 739       TCoord  two_fx = FRACT( ras.x ) << 1;
 740       TArea   area;
 741 
 742 
 743       if ( dy > 0)
 744       {
 745         first = ONE_PIXEL;
 746         incr  = 1;
 747       }
 748       else
 749       {
 750         first = 0;
 751         incr  = -1;
 752       }
 753 
 754       delta      = first - fy1;
 755       ras.area  += (TArea)two_fx * delta;
 756       ras.cover += delta;
 757       ey1       += incr;
 758 
 759       gray_set_cell( RAS_VAR_ ex, ey1 );
 760 
 761       delta = first + first - ONE_PIXEL;
 762       area  = (TArea)two_fx * delta;
 763       while ( ey1 != ey2 )
 764       {
 765         ras.area  += area;
 766         ras.cover += delta;
 767         ey1       += incr;
 768 
 769         gray_set_cell( RAS_VAR_ ex, ey1 );
 770       }
 771 
 772       delta      = fy2 - ONE_PIXEL + first;
 773       ras.area  += (TArea)two_fx * delta;
 774       ras.cover += delta;
 775 
 776       goto End;
 777     }
 778 
 779     /* ok, we have to render several scanlines */
 780     if ( dy > 0)
 781     {
 782       p     = ( ONE_PIXEL - fy1 ) * dx;
 783       first = ONE_PIXEL;
 784       incr  = 1;
 785     }
 786     else
 787     {
 788       p     = fy1 * dx;
 789       first = 0;
 790       incr  = -1;
 791       dy    = -dy;
 792     }
 793 
 794     /* the fractional part of x-delta is mod/dy. It is essential to */
 795     /* keep track of its accumulation for accurate rendering.       */
 796     FT_DIV_MOD( TCoord, p, dy, delta, mod );
 797 
 798     x = ras.x + delta;
 799     gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, x, first );
 800 
 801     ey1 += incr;
 802     gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 );
 803 
 804     if ( ey1 != ey2 )
 805     {
 806       TCoord  lift, rem;
 807 
 808 
 809       p    = ONE_PIXEL * dx;
 810       FT_DIV_MOD( TCoord, p, dy, lift, rem );
 811 
 812       do
 813       {
 814         delta = lift;
 815         mod  += rem;
 816         if ( mod >= (TCoord)dy )
 817         {
 818           mod -= (TCoord)dy;
 819           delta++;
 820         }
 821 
 822         x2 = x + delta;
 823         gray_render_scanline( RAS_VAR_ ey1,
 824                                        x, ONE_PIXEL - first,
 825                                        x2, first );
 826         x = x2;
 827 
 828         ey1 += incr;
 829         gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 );
 830       } while ( ey1 != ey2 );
 831     }
 832 
 833     gray_render_scanline( RAS_VAR_ ey1,
 834                                    x, ONE_PIXEL - first,
 835                                    to_x, fy2 );
 836 
 837   End:
 838     ras.x       = to_x;
 839     ras.y       = to_y;
 840   }
 841 
 842 #else
 843 
 844   /**************************************************************************
 845    *
 846    * Render a straight line across multiple cells in any direction.
 847    */
 848   static void
 849   gray_render_line( RAS_ARG_ TPos  to_x,
 850                              TPos  to_y )
 851   {
 852     TPos    dx, dy;
 853     TCoord  fx1, fy1, fx2, fy2;
 854     TCoord  ex1, ey1, ex2, ey2;
 855 
 856 
 857     ey1 = TRUNC( ras.y );
 858     ey2 = TRUNC( to_y );
 859 
 860     /* perform vertical clipping */
 861     if ( ( ey1 >= ras.max_ey && ey2 >= ras.max_ey ) ||
 862          ( ey1 <  ras.min_ey && ey2 <  ras.min_ey ) )
 863       goto End;
 864 
 865     ex1 = TRUNC( ras.x );
 866     ex2 = TRUNC( to_x );
 867 
 868     fx1 = FRACT( ras.x );
 869     fy1 = FRACT( ras.y );
 870 
 871     dx = to_x - ras.x;
 872     dy = to_y - ras.y;
 873 
 874     if ( ex1 == ex2 && ey1 == ey2 )       /* inside one cell */
 875       ;
 876     else if ( dy == 0 ) /* ex1 != ex2 */  /* any horizontal line */
 877     {
 878       gray_set_cell( RAS_VAR_ ex2, ey2 );
 879       goto End;
 880     }
 881     else if ( dx == 0 )
 882     {
 883       if ( dy > 0 )                       /* vertical line up */
 884         do
 885         {
 886           fy2 = ONE_PIXEL;
 887           ras.cover += ( fy2 - fy1 );
 888           ras.area  += ( fy2 - fy1 ) * fx1 * 2;
 889           fy1 = 0;
 890           ey1++;
 891           gray_set_cell( RAS_VAR_ ex1, ey1 );
 892         } while ( ey1 != ey2 );
 893       else                                /* vertical line down */
 894         do
 895         {
 896           fy2 = 0;
 897           ras.cover += ( fy2 - fy1 );
 898           ras.area  += ( fy2 - fy1 ) * fx1 * 2;
 899           fy1 = ONE_PIXEL;
 900           ey1--;
 901           gray_set_cell( RAS_VAR_ ex1, ey1 );
 902         } while ( ey1 != ey2 );
 903     }
 904     else                                  /* any other line */
 905     {
 906       TPos  prod = dx * (TPos)fy1 - dy * (TPos)fx1;
 907       FT_UDIVPREP( ex1 != ex2, dx );
 908       FT_UDIVPREP( ey1 != ey2, dy );
 909 
 910 
 911       /* The fundamental value `prod' determines which side and the  */
 912       /* exact coordinate where the line exits current cell.  It is  */
 913       /* also easily updated when moving from one cell to the next.  */
 914       do
 915       {
 916         if      ( prod                                   <= 0 &&
 917                   prod - dx * ONE_PIXEL                  >  0 ) /* left */
 918         {
 919           fx2 = 0;
 920           fy2 = FT_UDIV( -prod, -dx );
 921           prod -= dy * ONE_PIXEL;
 922           ras.cover += ( fy2 - fy1 );
 923           ras.area  += ( fy2 - fy1 ) * ( fx1 + fx2 );
 924           fx1 = ONE_PIXEL;
 925           fy1 = fy2;
 926           ex1--;
 927         }
 928         else if ( prod - dx * ONE_PIXEL                  <= 0 &&
 929                   prod - dx * ONE_PIXEL + dy * ONE_PIXEL >  0 ) /* up */
 930         {
 931           prod -= dx * ONE_PIXEL;
 932           fx2 = FT_UDIV( -prod, dy );
 933           fy2 = ONE_PIXEL;
 934           ras.cover += ( fy2 - fy1 );
 935           ras.area  += ( fy2 - fy1 ) * ( fx1 + fx2 );
 936           fx1 = fx2;
 937           fy1 = 0;
 938           ey1++;
 939         }
 940         else if ( prod - dx * ONE_PIXEL + dy * ONE_PIXEL <= 0 &&
 941                   prod                  + dy * ONE_PIXEL >= 0 ) /* right */
 942         {
 943           prod += dy * ONE_PIXEL;
 944           fx2 = ONE_PIXEL;
 945           fy2 = FT_UDIV( prod, dx );
 946           ras.cover += ( fy2 - fy1 );
 947           ras.area  += ( fy2 - fy1 ) * ( fx1 + fx2 );
 948           fx1 = 0;
 949           fy1 = fy2;
 950           ex1++;
 951         }
 952         else /* ( prod                  + dy * ONE_PIXEL <  0 &&
 953                   prod                                   >  0 )    down */
 954         {
 955           fx2 = FT_UDIV( prod, -dy );
 956           fy2 = 0;
 957           prod += dx * ONE_PIXEL;
 958           ras.cover += ( fy2 - fy1 );
 959           ras.area  += ( fy2 - fy1 ) * ( fx1 + fx2 );
 960           fx1 = fx2;
 961           fy1 = ONE_PIXEL;
 962           ey1--;
 963         }
 964 
 965         gray_set_cell( RAS_VAR_ ex1, ey1 );
 966       } while ( ex1 != ex2 || ey1 != ey2 );
 967     }
 968 
 969     fx2 = FRACT( to_x );
 970     fy2 = FRACT( to_y );
 971 
 972     ras.cover += ( fy2 - fy1 );
 973     ras.area  += ( fy2 - fy1 ) * ( fx1 + fx2 );
 974 
 975   End:
 976     ras.x       = to_x;
 977     ras.y       = to_y;
 978   }
 979 
 980 #endif
 981 
 982   static void
 983   gray_split_conic( FT_Vector*  base )
 984   {
 985     TPos  a, b;
 986 
 987 
 988     base[4].x = base[2].x;
 989     a = base[0].x + base[1].x;
 990     b = base[1].x + base[2].x;
 991     base[3].x = b >> 1;
 992     base[2].x = ( a + b ) >> 2;
 993     base[1].x = a >> 1;
 994 
 995     base[4].y = base[2].y;
 996     a = base[0].y + base[1].y;
 997     b = base[1].y + base[2].y;
 998     base[3].y = b >> 1;
 999     base[2].y = ( a + b ) >> 2;
1000     base[1].y = a >> 1;
1001   }
1002 
1003 
1004   static void
1005   gray_render_conic( RAS_ARG_ const FT_Vector*  control,
1006                               const FT_Vector*  to )
1007   {
1008     FT_Vector   bez_stack[16 * 2 + 1];  /* enough to accommodate bisections */
1009     FT_Vector*  arc = bez_stack;
1010     TPos        dx, dy;
1011     int         draw, split;
1012 
1013 
1014     arc[0].x = UPSCALE( to->x );
1015     arc[0].y = UPSCALE( to->y );
1016     arc[1].x = UPSCALE( control->x );
1017     arc[1].y = UPSCALE( control->y );
1018     arc[2].x = ras.x;
1019     arc[2].y = ras.y;
1020 
1021     /* short-cut the arc that crosses the current band */
1022     if ( ( TRUNC( arc[0].y ) >= ras.max_ey &&
1023            TRUNC( arc[1].y ) >= ras.max_ey &&
1024            TRUNC( arc[2].y ) >= ras.max_ey ) ||
1025          ( TRUNC( arc[0].y ) <  ras.min_ey &&
1026            TRUNC( arc[1].y ) <  ras.min_ey &&
1027            TRUNC( arc[2].y ) <  ras.min_ey ) )
1028     {
1029       ras.x = arc[0].x;
1030       ras.y = arc[0].y;
1031       return;
1032     }
1033 
1034     dx = FT_ABS( arc[2].x + arc[0].x - 2 * arc[1].x );
1035     dy = FT_ABS( arc[2].y + arc[0].y - 2 * arc[1].y );
1036     if ( dx < dy )
1037       dx = dy;
1038 
1039     /* We can calculate the number of necessary bisections because  */
1040     /* each bisection predictably reduces deviation exactly 4-fold. */
1041     /* Even 32-bit deviation would vanish after 16 bisections.      */
1042     draw = 1;
1043     while ( dx > ONE_PIXEL / 4 )
1044     {
1045       dx   >>= 2;
1046       draw <<= 1;
1047     }
1048 
1049     /* We use decrement counter to count the total number of segments */
1050     /* to draw starting from 2^level. Before each draw we split as    */
1051     /* many times as there are trailing zeros in the counter.         */
1052     do
1053     {
1054       split = draw & ( -draw );  /* isolate the rightmost 1-bit */
1055       while ( ( split >>= 1 ) )
1056       {
1057         gray_split_conic( arc );
1058         arc += 2;
1059       }
1060 
1061       gray_render_line( RAS_VAR_ arc[0].x, arc[0].y );
1062       arc -= 2;
1063 
1064     } while ( --draw );
1065   }
1066 
1067 
1068   static void
1069   gray_split_cubic( FT_Vector*  base )
1070   {
1071     TPos  a, b, c;
1072 
1073 
1074     base[6].x = base[3].x;
1075     a = base[0].x + base[1].x;
1076     b = base[1].x + base[2].x;
1077     c = base[2].x + base[3].x;
1078     base[5].x = c >> 1;
1079     c += b;
1080     base[4].x = c >> 2;
1081     base[1].x = a >> 1;
1082     a += b;
1083     base[2].x = a >> 2;
1084     base[3].x = ( a + c ) >> 3;
1085 
1086     base[6].y = base[3].y;
1087     a = base[0].y + base[1].y;
1088     b = base[1].y + base[2].y;
1089     c = base[2].y + base[3].y;
1090     base[5].y = c >> 1;
1091     c += b;
1092     base[4].y = c >> 2;
1093     base[1].y = a >> 1;
1094     a += b;
1095     base[2].y = a >> 2;
1096     base[3].y = ( a + c ) >> 3;
1097   }
1098 
1099 
1100   static void
1101   gray_render_cubic( RAS_ARG_ const FT_Vector*  control1,
1102                               const FT_Vector*  control2,
1103                               const FT_Vector*  to )
1104   {
1105     FT_Vector   bez_stack[16 * 3 + 1];  /* enough to accommodate bisections */
1106     FT_Vector*  arc = bez_stack;
1107 
1108 
1109     arc[0].x = UPSCALE( to->x );
1110     arc[0].y = UPSCALE( to->y );
1111     arc[1].x = UPSCALE( control2->x );
1112     arc[1].y = UPSCALE( control2->y );
1113     arc[2].x = UPSCALE( control1->x );
1114     arc[2].y = UPSCALE( control1->y );
1115     arc[3].x = ras.x;
1116     arc[3].y = ras.y;
1117 
1118     /* short-cut the arc that crosses the current band */
1119     if ( ( TRUNC( arc[0].y ) >= ras.max_ey &&
1120            TRUNC( arc[1].y ) >= ras.max_ey &&
1121            TRUNC( arc[2].y ) >= ras.max_ey &&
1122            TRUNC( arc[3].y ) >= ras.max_ey ) ||
1123          ( TRUNC( arc[0].y ) <  ras.min_ey &&
1124            TRUNC( arc[1].y ) <  ras.min_ey &&
1125            TRUNC( arc[2].y ) <  ras.min_ey &&
1126            TRUNC( arc[3].y ) <  ras.min_ey ) )
1127     {
1128       ras.x = arc[0].x;
1129       ras.y = arc[0].y;
1130       return;
1131     }
1132 
1133     for (;;)
1134     {
1135       /* with each split, control points quickly converge towards  */
1136       /* chord trisection points and the vanishing distances below */
1137       /* indicate when the segment is flat enough to draw          */
1138       if ( FT_ABS( 2 * arc[0].x - 3 * arc[1].x + arc[3].x ) > ONE_PIXEL / 2 ||
1139            FT_ABS( 2 * arc[0].y - 3 * arc[1].y + arc[3].y ) > ONE_PIXEL / 2 ||
1140            FT_ABS( arc[0].x - 3 * arc[2].x + 2 * arc[3].x ) > ONE_PIXEL / 2 ||
1141            FT_ABS( arc[0].y - 3 * arc[2].y + 2 * arc[3].y ) > ONE_PIXEL / 2 )
1142         goto Split;
1143 
1144       gray_render_line( RAS_VAR_ arc[0].x, arc[0].y );
1145 
1146       if ( arc == bez_stack )
1147         return;
1148 
1149       arc -= 3;
1150       continue;
1151 
1152     Split:
1153       gray_split_cubic( arc );
1154       arc += 3;
1155     }
1156   }
1157 
1158 
1159   static int
1160   gray_move_to( const FT_Vector*  to,
1161                 gray_PWorker      worker )
1162   {
1163     TPos  x, y;
1164 
1165 
1166     /* start to a new position */
1167     x = UPSCALE( to->x );
1168     y = UPSCALE( to->y );
1169 
1170     gray_set_cell( RAS_VAR_ TRUNC( x ), TRUNC( y ) );
1171 
1172     ras.x = x;
1173     ras.y = y;
1174     return 0;
1175   }
1176 
1177 
1178   static int
1179   gray_line_to( const FT_Vector*  to,
1180                 gray_PWorker      worker )
1181   {
1182     gray_render_line( RAS_VAR_ UPSCALE( to->x ), UPSCALE( to->y ) );
1183     return 0;
1184   }
1185 
1186 
1187   static int
1188   gray_conic_to( const FT_Vector*  control,
1189                  const FT_Vector*  to,
1190                  gray_PWorker      worker )
1191   {
1192     gray_render_conic( RAS_VAR_ control, to );
1193     return 0;
1194   }
1195 
1196 
1197   static int
1198   gray_cubic_to( const FT_Vector*  control1,
1199                  const FT_Vector*  control2,
1200                  const FT_Vector*  to,
1201                  gray_PWorker      worker )
1202   {
1203     gray_render_cubic( RAS_VAR_ control1, control2, to );
1204     return 0;
1205   }
1206 
1207 
1208   static void
1209   gray_hline( RAS_ARG_ TCoord  x,
1210                        TCoord  y,
1211                        TArea   coverage,
1212                        TCoord  acount )
1213   {
1214     /* scale the coverage from 0..(ONE_PIXEL*ONE_PIXEL*2) to 0..256  */
1215     coverage >>= PIXEL_BITS * 2 + 1 - 8;
1216 
1217     /* compute the line's coverage depending on the outline fill rule */
1218     if ( ras.outline.flags & FT_OUTLINE_EVEN_ODD_FILL )
1219     {
1220       coverage &= 511;
1221 
1222       if ( coverage >= 256 )
1223         coverage = 511 - coverage;
1224     }
1225     else  /* default non-zero winding rule */
1226     {
1227       if ( coverage < 0 )
1228         coverage = ~coverage;  /* the same as -coverage - 1 */
1229 
1230       if ( coverage >= 256 )
1231         coverage = 255;
1232     }
1233 
1234     if ( ras.num_spans >= 0 )  /* for FT_RASTER_FLAG_DIRECT only */
1235     {
1236       FT_Span*  span = ras.spans + ras.num_spans++;
1237 
1238 
1239       span->x        = (short)x;
1240       span->len      = (unsigned short)acount;
1241       span->coverage = (unsigned char)coverage;
1242 
1243       if ( ras.num_spans == FT_MAX_GRAY_SPANS )
1244       {
1245         /* flush the span buffer and reset the count */
1246         ras.render_span( y, ras.num_spans, ras.spans, ras.render_span_data );
1247         ras.num_spans = 0;
1248       }
1249     }
1250     else
1251     {
1252       unsigned char*  q = ras.target.origin - ras.target.pitch * y + x;
1253       unsigned char   c = (unsigned char)coverage;
1254 
1255 
1256       /* For small-spans it is faster to do it by ourselves than
1257        * calling `memset'.  This is mainly due to the cost of the
1258        * function call.
1259        */
1260       switch ( acount )
1261       {
1262       case 7:
1263         *q++ = c;
1264         /* fall through */
1265       case 6:
1266         *q++ = c;
1267         /* fall through */
1268       case 5:
1269         *q++ = c;
1270         /* fall through */
1271       case 4:
1272         *q++ = c;
1273         /* fall through */
1274       case 3:
1275         *q++ = c;
1276         /* fall through */
1277       case 2:
1278         *q++ = c;
1279         /* fall through */
1280       case 1:
1281         *q = c;
1282         /* fall through */
1283       case 0:
1284         break;
1285       default:
1286         FT_MEM_SET( q, c, acount );
1287       }
1288     }
1289   }
1290 
1291 
1292   static void
1293   gray_sweep( RAS_ARG )
1294   {
1295     int  y;
1296 
1297 
1298     for ( y = ras.min_ey; y < ras.max_ey; y++ )
1299     {
1300       PCell   cell  = ras.ycells[y - ras.min_ey];
1301       TCoord  x     = ras.min_ex;
1302       TArea   cover = 0;
1303       TArea   area;
1304 
1305 
1306       for ( ; cell != NULL; cell = cell->next )
1307       {
1308         if ( cover != 0 && cell->x > x )
1309           gray_hline( RAS_VAR_ x, y, cover, cell->x - x );
1310 
1311         cover += (TArea)cell->cover * ( ONE_PIXEL * 2 );
1312         area   = cover - cell->area;
1313 
1314         if ( area != 0 && cell->x >= ras.min_ex )
1315           gray_hline( RAS_VAR_ cell->x, y, area, 1 );
1316 
1317         x = cell->x + 1;
1318       }
1319 
1320       if ( cover != 0 )
1321         gray_hline( RAS_VAR_ x, y, cover, ras.max_ex - x );
1322 
1323       if ( ras.num_spans > 0 )  /* for FT_RASTER_FLAG_DIRECT only */
1324       {
1325         /* flush the span buffer and reset the count */
1326         ras.render_span( y, ras.num_spans, ras.spans, ras.render_span_data );
1327         ras.num_spans = 0;
1328       }
1329     }
1330   }
1331 
1332 
1333 #ifdef STANDALONE_
1334 
1335   /**************************************************************************
1336    *
1337    * The following functions should only compile in stand-alone mode,
1338    * i.e., when building this component without the rest of FreeType.
1339    *
1340    */
1341 
1342   /**************************************************************************
1343    *
1344    * @Function:
1345    *   FT_Outline_Decompose
1346    *
1347    * @Description:
1348    *   Walk over an outline's structure to decompose it into individual
1349    *   segments and Bézier arcs.  This function is also able to emit
1350    *   `move to' and `close to' operations to indicate the start and end
1351    *   of new contours in the outline.
1352    *
1353    * @Input:
1354    *   outline ::
1355    *     A pointer to the source target.
1356    *
1357    *   func_interface ::
1358    *     A table of `emitters', i.e., function pointers
1359    *     called during decomposition to indicate path
1360    *     operations.
1361    *
1362    * @InOut:
1363    *   user ::
1364    *     A typeless pointer which is passed to each
1365    *     emitter during the decomposition.  It can be
1366    *     used to store the state during the
1367    *     decomposition.
1368    *
1369    * @Return:
1370    *   Error code.  0 means success.
1371    */
1372   static int
1373   FT_Outline_Decompose( const FT_Outline*        outline,
1374                         const FT_Outline_Funcs*  func_interface,
1375                         void*                    user )
1376   {
1377 #undef SCALED
1378 #define SCALED( x )  ( (x) * ( 1L << shift ) - delta )
1379 
1380     FT_Vector   v_last;
1381     FT_Vector   v_control;
1382     FT_Vector   v_start;
1383 
1384     FT_Vector*  point;
1385     FT_Vector*  limit;
1386     char*       tags;
1387 
1388     int         error;
1389 
1390     int   n;         /* index of contour in outline     */
1391     int   first;     /* index of first point in contour */
1392     char  tag;       /* current point's state           */
1393 
1394     int   shift;
1395     TPos  delta;
1396 
1397 
1398     if ( !outline )
1399       return FT_THROW( Invalid_Outline );
1400 
1401     if ( !func_interface )
1402       return FT_THROW( Invalid_Argument );
1403 
1404     shift = func_interface->shift;
1405     delta = func_interface->delta;
1406     first = 0;
1407 
1408     for ( n = 0; n < outline->n_contours; n++ )
1409     {
1410       int  last;  /* index of last point in contour */
1411 
1412 
1413       FT_TRACE5(( "FT_Outline_Decompose: Outline %d\n", n ));
1414 
1415       last  = outline->contours[n];
1416       if ( last < 0 )
1417         goto Invalid_Outline;
1418       limit = outline->points + last;
1419 
1420       v_start   = outline->points[first];
1421       v_start.x = SCALED( v_start.x );
1422       v_start.y = SCALED( v_start.y );
1423 
1424       v_last   = outline->points[last];
1425       v_last.x = SCALED( v_last.x );
1426       v_last.y = SCALED( v_last.y );
1427 
1428       v_control = v_start;
1429 
1430       point = outline->points + first;
1431       tags  = outline->tags   + first;
1432       tag   = FT_CURVE_TAG( tags[0] );
1433 
1434       /* A contour cannot start with a cubic control point! */
1435       if ( tag == FT_CURVE_TAG_CUBIC )
1436         goto Invalid_Outline;
1437 
1438       /* check first point to determine origin */
1439       if ( tag == FT_CURVE_TAG_CONIC )
1440       {
1441         /* first point is conic control.  Yes, this happens. */
1442         if ( FT_CURVE_TAG( outline->tags[last] ) == FT_CURVE_TAG_ON )
1443         {
1444           /* start at last point if it is on the curve */
1445           v_start = v_last;
1446           limit--;
1447         }
1448         else
1449         {
1450           /* if both first and last points are conic,         */
1451           /* start at their middle and record its position    */
1452           /* for closure                                      */
1453           v_start.x = ( v_start.x + v_last.x ) / 2;
1454           v_start.y = ( v_start.y + v_last.y ) / 2;
1455 
1456           v_last = v_start;
1457         }
1458         point--;
1459         tags--;
1460       }
1461 
1462       FT_TRACE5(( "  move to (%.2f, %.2f)\n",
1463                   v_start.x / 64.0, v_start.y / 64.0 ));
1464       error = func_interface->move_to( &v_start, user );
1465       if ( error )
1466         goto Exit;
1467 
1468       while ( point < limit )
1469       {
1470         point++;
1471         tags++;
1472 
1473         tag = FT_CURVE_TAG( tags[0] );
1474         switch ( tag )
1475         {
1476         case FT_CURVE_TAG_ON:  /* emit a single line_to */
1477           {
1478             FT_Vector  vec;
1479 
1480 
1481             vec.x = SCALED( point->x );
1482             vec.y = SCALED( point->y );
1483 
1484             FT_TRACE5(( "  line to (%.2f, %.2f)\n",
1485                         vec.x / 64.0, vec.y / 64.0 ));
1486             error = func_interface->line_to( &vec, user );
1487             if ( error )
1488               goto Exit;
1489             continue;
1490           }
1491 
1492         case FT_CURVE_TAG_CONIC:  /* consume conic arcs */
1493           v_control.x = SCALED( point->x );
1494           v_control.y = SCALED( point->y );
1495 
1496         Do_Conic:
1497           if ( point < limit )
1498           {
1499             FT_Vector  vec;
1500             FT_Vector  v_middle;
1501 
1502 
1503             point++;
1504             tags++;
1505             tag = FT_CURVE_TAG( tags[0] );
1506 
1507             vec.x = SCALED( point->x );
1508             vec.y = SCALED( point->y );
1509 
1510             if ( tag == FT_CURVE_TAG_ON )
1511             {
1512               FT_TRACE5(( "  conic to (%.2f, %.2f)"
1513                           " with control (%.2f, %.2f)\n",
1514                           vec.x / 64.0, vec.y / 64.0,
1515                           v_control.x / 64.0, v_control.y / 64.0 ));
1516               error = func_interface->conic_to( &v_control, &vec, user );
1517               if ( error )
1518                 goto Exit;
1519               continue;
1520             }
1521 
1522             if ( tag != FT_CURVE_TAG_CONIC )
1523               goto Invalid_Outline;
1524 
1525             v_middle.x = ( v_control.x + vec.x ) / 2;
1526             v_middle.y = ( v_control.y + vec.y ) / 2;
1527 
1528             FT_TRACE5(( "  conic to (%.2f, %.2f)"
1529                         " with control (%.2f, %.2f)\n",
1530                         v_middle.x / 64.0, v_middle.y / 64.0,
1531                         v_control.x / 64.0, v_control.y / 64.0 ));
1532             error = func_interface->conic_to( &v_control, &v_middle, user );
1533             if ( error )
1534               goto Exit;
1535 
1536             v_control = vec;
1537             goto Do_Conic;
1538           }
1539 
1540           FT_TRACE5(( "  conic to (%.2f, %.2f)"
1541                       " with control (%.2f, %.2f)\n",
1542                       v_start.x / 64.0, v_start.y / 64.0,
1543                       v_control.x / 64.0, v_control.y / 64.0 ));
1544           error = func_interface->conic_to( &v_control, &v_start, user );
1545           goto Close;
1546 
1547         default:  /* FT_CURVE_TAG_CUBIC */
1548           {
1549             FT_Vector  vec1, vec2;
1550 
1551 
1552             if ( point + 1 > limit                             ||
1553                  FT_CURVE_TAG( tags[1] ) != FT_CURVE_TAG_CUBIC )
1554               goto Invalid_Outline;
1555 
1556             point += 2;
1557             tags  += 2;
1558 
1559             vec1.x = SCALED( point[-2].x );
1560             vec1.y = SCALED( point[-2].y );
1561 
1562             vec2.x = SCALED( point[-1].x );
1563             vec2.y = SCALED( point[-1].y );
1564 
1565             if ( point <= limit )
1566             {
1567               FT_Vector  vec;
1568 
1569 
1570               vec.x = SCALED( point->x );
1571               vec.y = SCALED( point->y );
1572 
1573               FT_TRACE5(( "  cubic to (%.2f, %.2f)"
1574                           " with controls (%.2f, %.2f) and (%.2f, %.2f)\n",
1575                           vec.x / 64.0, vec.y / 64.0,
1576                           vec1.x / 64.0, vec1.y / 64.0,
1577                           vec2.x / 64.0, vec2.y / 64.0 ));
1578               error = func_interface->cubic_to( &vec1, &vec2, &vec, user );
1579               if ( error )
1580                 goto Exit;
1581               continue;
1582             }
1583 
1584             FT_TRACE5(( "  cubic to (%.2f, %.2f)"
1585                         " with controls (%.2f, %.2f) and (%.2f, %.2f)\n",
1586                         v_start.x / 64.0, v_start.y / 64.0,
1587                         vec1.x / 64.0, vec1.y / 64.0,
1588                         vec2.x / 64.0, vec2.y / 64.0 ));
1589             error = func_interface->cubic_to( &vec1, &vec2, &v_start, user );
1590             goto Close;
1591           }
1592         }
1593       }
1594 
1595       /* close the contour with a line segment */
1596       FT_TRACE5(( "  line to (%.2f, %.2f)\n",
1597                   v_start.x / 64.0, v_start.y / 64.0 ));
1598       error = func_interface->line_to( &v_start, user );
1599 
1600    Close:
1601       if ( error )
1602         goto Exit;
1603 
1604       first = last + 1;
1605     }
1606 
1607     FT_TRACE5(( "FT_Outline_Decompose: Done\n", n ));
1608     return 0;
1609 
1610   Exit:
1611     FT_TRACE5(( "FT_Outline_Decompose: Error 0x%x\n", error ));
1612     return error;
1613 
1614   Invalid_Outline:
1615     return FT_THROW( Invalid_Outline );
1616   }
1617 
1618 #endif /* STANDALONE_ */
1619 
1620 
1621   FT_DEFINE_OUTLINE_FUNCS(
1622     func_interface,
1623 
1624     (FT_Outline_MoveTo_Func) gray_move_to,   /* move_to  */
1625     (FT_Outline_LineTo_Func) gray_line_to,   /* line_to  */
1626     (FT_Outline_ConicTo_Func)gray_conic_to,  /* conic_to */
1627     (FT_Outline_CubicTo_Func)gray_cubic_to,  /* cubic_to */
1628 
1629     0,                                       /* shift    */
1630     0                                        /* delta    */
1631   )
1632 
1633 
1634   static int
1635   gray_convert_glyph_inner( RAS_ARG,
1636                             int  continued )
1637   {
1638     int  error;
1639 
1640 
1641     if ( ft_setjmp( ras.jump_buffer ) == 0 )
1642     {
1643       if ( continued )
1644         FT_Trace_Disable();
1645       error = FT_Outline_Decompose( &ras.outline, &func_interface, &ras );
1646       if ( continued )
1647         FT_Trace_Enable();
1648 
1649       if ( !ras.invalid )
1650         gray_record_cell( RAS_VAR );
1651 
1652       FT_TRACE7(( "band [%d..%d]: %d cell%s\n",
1653                   ras.min_ey,
1654                   ras.max_ey,
1655                   ras.num_cells,
1656                   ras.num_cells == 1 ? "" : "s" ));
1657     }
1658     else
1659     {
1660       error = FT_THROW( Memory_Overflow );
1661 
1662       FT_TRACE7(( "band [%d..%d]: to be bisected\n",
1663                   ras.min_ey, ras.max_ey ));
1664     }
1665 
1666     return error;
1667   }
1668 
1669 
1670   static int
1671   gray_convert_glyph( RAS_ARG )
1672   {
1673     const TCoord  yMin = ras.min_ey;
1674     const TCoord  yMax = ras.max_ey;
1675 
1676     TCell    buffer[FT_MAX_GRAY_POOL];
1677     size_t   height = (size_t)( yMax - yMin );
1678     size_t   n = FT_MAX_GRAY_POOL / 8;
1679     TCoord   y;
1680     TCoord   bands[32];  /* enough to accommodate bisections */
1681     TCoord*  band;
1682 
1683     int  continued = 0;
1684 
1685 
1686     /* set up vertical bands */
1687     if ( height > n )
1688     {
1689       /* two divisions rounded up */
1690       n       = ( height + n - 1 ) / n;
1691       height  = ( height + n - 1 ) / n;
1692     }
1693 
1694     /* memory management */
1695     n = ( height * sizeof ( PCell ) + sizeof ( TCell ) - 1 ) / sizeof ( TCell );
1696 
1697     ras.cells     = buffer + n;
1698     ras.max_cells = (FT_PtrDist)( FT_MAX_GRAY_POOL - n );
1699     ras.ycells    = (PCell*)buffer;
1700 
1701     for ( y = yMin; y < yMax; )
1702     {
1703       ras.min_ey = y;
1704       y         += height;
1705       ras.max_ey = FT_MIN( y, yMax );
1706 
1707       band    = bands;
1708       band[1] = ras.min_ey;
1709       band[0] = ras.max_ey;
1710 
1711       do
1712       {
1713         TCoord  width = band[0] - band[1];
1714         int     error;
1715 
1716 
1717         FT_MEM_ZERO( ras.ycells, height * sizeof ( PCell ) );
1718 
1719         ras.num_cells = 0;
1720         ras.invalid   = 1;
1721         ras.min_ey    = band[1];
1722         ras.max_ey    = band[0];
1723 
1724         error     = gray_convert_glyph_inner( RAS_VAR, continued );
1725         continued = 1;
1726 
1727         if ( !error )
1728         {
1729           gray_sweep( RAS_VAR );
1730           band--;
1731           continue;
1732         }
1733         else if ( error != ErrRaster_Memory_Overflow )
1734           return 1;
1735 
1736         /* render pool overflow; we will reduce the render band by half */
1737         width >>= 1;
1738 
1739         /* this should never happen even with tiny rendering pool */
1740         if ( width == 0 )
1741         {
1742           FT_TRACE7(( "gray_convert_glyph: rotten glyph\n" ));
1743           return 1;
1744         }
1745 
1746         band++;
1747         band[1]  = band[0];
1748         band[0] += width;
1749       } while ( band >= bands );
1750     }
1751 
1752     return 0;
1753   }
1754 
1755 
1756   static int
1757   gray_raster_render( FT_Raster                raster,
1758                       const FT_Raster_Params*  params )
1759   {
1760     const FT_Outline*  outline    = (const FT_Outline*)params->source;
1761     const FT_Bitmap*   target_map = params->target;
1762 
1763 #ifndef FT_STATIC_RASTER
1764     gray_TWorker  worker[1];
1765 #endif
1766 
1767 
1768     if ( !raster )
1769       return FT_THROW( Invalid_Argument );
1770 
1771     /* this version does not support monochrome rendering */
1772     if ( !( params->flags & FT_RASTER_FLAG_AA ) )
1773       return FT_THROW( Invalid_Mode );
1774 
1775     if ( !outline )
1776       return FT_THROW( Invalid_Outline );
1777 
1778     /* return immediately if the outline is empty */
1779     if ( outline->n_points == 0 || outline->n_contours <= 0 )
1780       return 0;
1781 
1782     if ( !outline->contours || !outline->points )
1783       return FT_THROW( Invalid_Outline );
1784 
1785     if ( outline->n_points !=
1786            outline->contours[outline->n_contours - 1] + 1 )
1787       return FT_THROW( Invalid_Outline );
1788 
1789     ras.outline = *outline;
1790 
1791     if ( params->flags & FT_RASTER_FLAG_DIRECT )
1792     {
1793       if ( !params->gray_spans )
1794         return 0;
1795 
1796       ras.render_span      = (FT_Raster_Span_Func)params->gray_spans;
1797       ras.render_span_data = params->user;
1798       ras.num_spans        = 0;
1799 
1800       ras.min_ex = params->clip_box.xMin;
1801       ras.min_ey = params->clip_box.yMin;
1802       ras.max_ex = params->clip_box.xMax;
1803       ras.max_ey = params->clip_box.yMax;
1804     }
1805     else
1806     {
1807       /* if direct mode is not set, we must have a target bitmap */
1808       if ( !target_map )
1809         return FT_THROW( Invalid_Argument );
1810 
1811       /* nothing to do */
1812       if ( !target_map->width || !target_map->rows )
1813         return 0;
1814 
1815       if ( !target_map->buffer )
1816         return FT_THROW( Invalid_Argument );
1817 
1818       if ( target_map->pitch < 0 )
1819         ras.target.origin = target_map->buffer;
1820       else
1821         ras.target.origin = target_map->buffer
1822               + ( target_map->rows - 1 ) * (unsigned int)target_map->pitch;
1823 
1824       ras.target.pitch = target_map->pitch;
1825 
1826       ras.render_span      = (FT_Raster_Span_Func)NULL;
1827       ras.render_span_data = NULL;
1828       ras.num_spans        = -1;  /* invalid */
1829 
1830       ras.min_ex = 0;
1831       ras.min_ey = 0;
1832       ras.max_ex = (FT_Pos)target_map->width;
1833       ras.max_ey = (FT_Pos)target_map->rows;
1834     }
1835 
1836     /* exit if nothing to do */
1837     if ( ras.max_ex <= ras.min_ex || ras.max_ey <= ras.min_ey )
1838       return 0;
1839 
1840     return gray_convert_glyph( RAS_VAR );
1841   }
1842 
1843 
1844   /**** RASTER OBJECT CREATION: In stand-alone mode, we simply use *****/
1845   /****                         a static object.                   *****/
1846 
1847 #ifdef STANDALONE_
1848 
1849   static int
1850   gray_raster_new( void*       memory,
1851                    FT_Raster*  araster )
1852   {
1853     static gray_TRaster  the_raster;
1854 
1855     FT_UNUSED( memory );
1856 
1857 
1858     *araster = (FT_Raster)&the_raster;
1859     FT_ZERO( &the_raster );
1860 
1861     return 0;
1862   }
1863 
1864 
1865   static void
1866   gray_raster_done( FT_Raster  raster )
1867   {
1868     /* nothing */
1869     FT_UNUSED( raster );
1870   }
1871 
1872 #else /* !STANDALONE_ */
1873 
1874   static int
1875   gray_raster_new( FT_Memory   memory,
1876                    FT_Raster*  araster )
1877   {
1878     FT_Error      error;
1879     gray_PRaster  raster = NULL;
1880 
1881 
1882     *araster = 0;
1883     if ( !FT_ALLOC( raster, sizeof ( gray_TRaster ) ) )
1884     {
1885       raster->memory = memory;
1886       *araster       = (FT_Raster)raster;
1887     }
1888 
1889     return error;
1890   }
1891 
1892 
1893   static void
1894   gray_raster_done( FT_Raster  raster )
1895   {
1896     FT_Memory  memory = (FT_Memory)((gray_PRaster)raster)->memory;
1897 
1898 
1899     FT_FREE( raster );
1900   }
1901 
1902 #endif /* !STANDALONE_ */
1903 
1904 
1905   static void
1906   gray_raster_reset( FT_Raster       raster,
1907                      unsigned char*  pool_base,
1908                      unsigned long   pool_size )
1909   {
1910     FT_UNUSED( raster );
1911     FT_UNUSED( pool_base );
1912     FT_UNUSED( pool_size );
1913   }
1914 
1915 
1916   static int
1917   gray_raster_set_mode( FT_Raster      raster,
1918                         unsigned long  mode,
1919                         void*          args )
1920   {
1921     FT_UNUSED( raster );
1922     FT_UNUSED( mode );
1923     FT_UNUSED( args );
1924 
1925 
1926     return 0; /* nothing to do */
1927   }
1928 
1929 
1930   FT_DEFINE_RASTER_FUNCS(
1931     ft_grays_raster,
1932 
1933     FT_GLYPH_FORMAT_OUTLINE,
1934 
1935     (FT_Raster_New_Func)     gray_raster_new,       /* raster_new      */
1936     (FT_Raster_Reset_Func)   gray_raster_reset,     /* raster_reset    */
1937     (FT_Raster_Set_Mode_Func)gray_raster_set_mode,  /* raster_set_mode */
1938     (FT_Raster_Render_Func)  gray_raster_render,    /* raster_render   */
1939     (FT_Raster_Done_Func)    gray_raster_done       /* raster_done     */
1940   )
1941 
1942 
1943 /* END */
1944 
1945 
1946 /* Local Variables: */
1947 /* coding: utf-8    */
1948 /* End:             */