src/smooth/ftgrays.c

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