extension/SDL2_ttf-2.0.14/external/freetype-2.4.12/src/smooth/ftgrays.c

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