libraries/freetype-2.0.5/ftgrays.c

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