src/smooth/ftgrays.c

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