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