src/raster/ftraster.c

   1 /***************************************************************************/
   2 /*                                                                         */
   3 /*  ftraster.c                                                             */
   4 /*                                                                         */
   5 /*    The FreeType glyph rasterizer (body).                                */
   6 /*                                                                         */
   7 /*  Copyright 1996-2003, 2005, 2007-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 `ftimage.h' and `ftmisc.h' into the $(incdir)           */
  23   /* directory.  Typically, you should do something like                   */
  24   /*                                                                       */
  25   /* - copy `src/raster/ftraster.c' (this file) to your current directory  */
  26   /*                                                                       */
  27   /* - copy `include/freetype/ftimage.h' and `src/raster/ftmisc.h'         */
  28   /*   to your current directory                                           */
  29   /*                                                                       */
  30   /* - compile `ftraster' with the _STANDALONE_ macro defined, as in       */
  31   /*                                                                       */
  32   /*     cc -c -D_STANDALONE_ ftraster.c                                   */
  33   /*                                                                       */
  34   /* The renderer can be initialized with a call to                        */
  35   /* `ft_standard_raster.raster_new'; a bitmap can be generated            */
  36   /* with a call to `ft_standard_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   /*                                                                       */
  46   /* This is a rewrite of the FreeType 1.x scan-line converter             */
  47   /*                                                                       */
  48   /*************************************************************************/
  49
  50 #ifdef _STANDALONE_
  51
  52 #define FT_CONFIG_STANDARD_LIBRARY_H  <stdlib.h>
  53
  54 #include <string.h>           /* for memset */
  55
  56 #include "ftmisc.h"
  57 #include "ftimage.h"
  58
  59 #else /* !_STANDALONE_ */
  60
  61 #include <ft2build.h>
  62 #include "ftraster.h"
  63 #include FT_INTERNAL_CALC_H   /* for FT_MulDiv only */
  64
  65 #include "rastpic.h"
  66
  67 #endif /* !_STANDALONE_ */
  68
  69
  70   /*************************************************************************/
  71   /*                                                                       */
  72   /* A simple technical note on how the raster works                       */
  73   /* -----------------------------------------------                       */
  74   /*                                                                       */
  75   /*   Converting an outline into a bitmap is achieved in several steps:   */
  76   /*                                                                       */
  77   /*   1 - Decomposing the outline into successive `profiles'.  Each       */
  78   /*       profile is simply an array of scanline intersections on a given */
  79   /*       dimension.  A profile's main attributes are                     */
  80   /*                                                                       */
  81   /*       o its scanline position boundaries, i.e. `Ymin' and `Ymax'      */
  82   /*                                                                       */
  83   /*       o an array of intersection coordinates for each scanline        */
  84   /*         between `Ymin' and `Ymax'                                     */
  85   /*                                                                       */
  86   /*       o a direction, indicating whether it was built going `up' or    */
  87   /*         `down', as this is very important for filling rules           */
  88   /*                                                                       */
  89   /*       o its drop-out mode                                             */
  90   /*                                                                       */
  91   /*   2 - Sweeping the target map's scanlines in order to compute segment */
  92   /*       `spans' which are then filled.  Additionally, this pass         */
  93   /*       performs drop-out control.                                      */
  94   /*                                                                       */
  95   /*   The outline data is parsed during step 1 only.  The profiles are    */
  96   /*   built from the bottom of the render pool, used as a stack.  The     */
  97   /*   following graphics shows the profile list under construction:       */
  98   /*                                                                       */
  99   /*     __________________________________________________________ _ _    */
 100   /*    |         |                 |         |                 |          */
 101   /*    | profile | coordinates for | profile | coordinates for |-->       */
 102   /*    |    1    |  profile 1      |    2    |  profile 2      |-->       */
 103   /*    |_________|_________________|_________|_________________|__ _ _    */
 104   /*                                                                       */
 105   /*    ^                                                       ^          */
 106   /*    |                                                       |          */
 107   /* start of render pool                                      top         */
 108   /*                                                                       */
 109   /*   The top of the profile stack is kept in the `top' variable.         */
 110   /*                                                                       */
 111   /*   As you can see, a profile record is pushed on top of the render     */
 112   /*   pool, which is then followed by its coordinates/intersections.  If  */
 113   /*   a change of direction is detected in the outline, a new profile is  */
 114   /*   generated until the end of the outline.                             */
 115   /*                                                                       */
 116   /*   Note that when all profiles have been generated, the function       */
 117   /*   Finalize_Profile_Table() is used to record, for each profile, its   */
 118   /*   bottom-most scanline as well as the scanline above its upmost       */
 119   /*   boundary.  These positions are called `y-turns' because they (sort  */
 120   /*   of) correspond to local extrema.  They are stored in a sorted list  */
 121   /*   built from the top of the render pool as a downwards stack:         */
 122   /*                                                                       */
 123   /*      _ _ _______________________________________                      */
 124   /*                            |                    |                     */
 125   /*                         <--| sorted list of     |                     */
 126   /*                         <--|  extrema scanlines |                     */
 127   /*      _ _ __________________|____________________|                     */
 128   /*                                                                       */
 129   /*                            ^                    ^                     */
 130   /*                            |                    |                     */
 131   /*                         maxBuff           sizeBuff = end of pool      */
 132   /*                                                                       */
 133   /*   This list is later used during the sweep phase in order to          */
 134   /*   optimize performance (see technical note on the sweep below).       */
 135   /*                                                                       */
 136   /*   Of course, the raster detects whether the two stacks collide and    */
 137   /*   handles the situation properly.                                     */
 138   /*                                                                       */
 139   /*************************************************************************/
 140
 141
 142   /*************************************************************************/
 143   /*************************************************************************/
 144   /**                                                                     **/
 145   /**  CONFIGURATION MACROS                                               **/
 146   /**                                                                     **/
 147   /*************************************************************************/
 148   /*************************************************************************/
 149
 150   /* define DEBUG_RASTER if you want to compile a debugging version */
 151 /* #define DEBUG_RASTER */
 152
 153   /* define FT_RASTER_OPTION_ANTI_ALIASING if you want to support */
 154   /* 5-levels anti-aliasing                                       */
 155 /* #define FT_RASTER_OPTION_ANTI_ALIASING */
 156
 157   /* The size of the two-lines intermediate bitmap used */
 158   /* for anti-aliasing, in bytes.                       */
 159 #define RASTER_GRAY_LINES  2048
 160
 161
 162   /*************************************************************************/
 163   /*************************************************************************/
 164   /**                                                                     **/
 165   /**  OTHER MACROS (do not change)                                       **/
 166   /**                                                                     **/
 167   /*************************************************************************/
 168   /*************************************************************************/
 169
 170   /*************************************************************************/
 171   /*                                                                       */
 172   /* The macro FT_COMPONENT is used in trace mode.  It is an implicit      */
 173   /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log  */
 174   /* messages during execution.                                            */
 175   /*                                                                       */
 176 #undef  FT_COMPONENT
 177 #define FT_COMPONENT  trace_raster
 178
 179
 180 #ifdef _STANDALONE_
 181
 182
 183   /* This macro is used to indicate that a function parameter is unused. */
 184   /* Its purpose is simply to reduce compiler warnings.  Note also that  */
 185   /* simply defining it as `(void)x' doesn't avoid warnings with certain */
 186   /* ANSI compilers (e.g. LCC).                                          */
 187 #define FT_UNUSED( x )  (x) = (x)
 188
 189   /* Disable the tracing mechanism for simplicity -- developers can      */
 190   /* activate it easily by redefining these two macros.                  */
 191 #ifndef FT_ERROR
 192 #define FT_ERROR( x )  do { } while ( 0 )     /* nothing */
 193 #endif
 194
 195 #ifndef FT_TRACE
 196 #define FT_TRACE( x )   do { } while ( 0 )    /* nothing */
 197 #define FT_TRACE1( x )  do { } while ( 0 )    /* nothing */
 198 #define FT_TRACE6( x )  do { } while ( 0 )    /* nothing */
 199 #endif
 200
 201 #define Raster_Err_None          0
 202 #define Raster_Err_Not_Ini      -1
 203 #define Raster_Err_Overflow     -2
 204 #define Raster_Err_Neg_Height   -3
 205 #define Raster_Err_Invalid      -4
 206 #define Raster_Err_Unsupported  -5
 207
 208 #define ft_memset  memset
 209
 210 #define FT_DEFINE_RASTER_FUNCS( class_, glyph_format_, raster_new_, \
 211                                 raster_reset_, raster_set_mode_,    \
 212                                 raster_render_, raster_done_ )      \
 213           const FT_Raster_Funcs class_ =                            \
 214           {                                                         \
 215             glyph_format_,                                          \
 216             raster_new_,                                            \
 217             raster_reset_,                                          \
 218             raster_set_mode_,                                       \
 219             raster_render_,                                         \
 220             raster_done_                                            \
 221          };
 222
 223 #else /* !_STANDALONE_ */
 224
 225
 226 #include FT_INTERNAL_OBJECTS_H
 227 #include FT_INTERNAL_DEBUG_H        /* for FT_TRACE() and FT_ERROR() */
 228
 229 #include "rasterrs.h"
 230
 231 #define Raster_Err_None         Raster_Err_Ok
 232 #define Raster_Err_Not_Ini      Raster_Err_Raster_Uninitialized
 233 #define Raster_Err_Overflow     Raster_Err_Raster_Overflow
 234 #define Raster_Err_Neg_Height   Raster_Err_Raster_Negative_Height
 235 #define Raster_Err_Invalid      Raster_Err_Invalid_Outline
 236 #define Raster_Err_Unsupported  Raster_Err_Cannot_Render_Glyph
 237
 238
 239 #endif /* !_STANDALONE_ */
 240
 241
 242 #ifndef FT_MEM_SET
 243 #define FT_MEM_SET( d, s, c )  ft_memset( d, s, c )
 244 #endif
 245
 246 #ifndef FT_MEM_ZERO
 247 #define FT_MEM_ZERO( dest, count )  FT_MEM_SET( dest, 0, count )
 248 #endif
 249
 250   /* FMulDiv means `Fast MulDiv'; it is used in case where `b' is       */
 251   /* typically a small value and the result of a*b is known to fit into */
 252   /* 32 bits.                                                           */
 253 #define FMulDiv( a, b, c )  ( (a) * (b) / (c) )
 254
 255   /* On the other hand, SMulDiv means `Slow MulDiv', and is used typically */
 256   /* for clipping computations.  It simply uses the FT_MulDiv() function   */
 257   /* defined in `ftcalc.h'.                                                */
 258 #define SMulDiv  FT_MulDiv
 259
 260   /* The rasterizer is a very general purpose component; please leave */
 261   /* the following redefinitions there (you never know your target    */
 262   /* environment).                                                    */
 263
 264 #ifndef TRUE
 265 #define TRUE   1
 266 #endif
 267
 268 #ifndef FALSE
 269 #define FALSE  0
 270 #endif
 271
 272 #ifndef NULL
 273 #define NULL  (void*)0
 274 #endif
 275
 276 #ifndef SUCCESS
 277 #define SUCCESS  0
 278 #endif
 279
 280 #ifndef FAILURE
 281 #define FAILURE  1
 282 #endif
 283
 284
 285 #define MaxBezier  32   /* The maximum number of stacked Bezier curves. */
 286                         /* Setting this constant to more than 32 is a   */
 287                         /* pure waste of space.                         */
 288
 289 #define Pixel_Bits  6   /* fractional bits of *input* coordinates */
 290
 291
 292   /*************************************************************************/
 293   /*************************************************************************/
 294   /**                                                                     **/
 295   /**  SIMPLE TYPE DECLARATIONS                                           **/
 296   /**                                                                     **/
 297   /*************************************************************************/
 298   /*************************************************************************/
 299
 300   typedef int             Int;
 301   typedef unsigned int    UInt;
 302   typedef short           Short;
 303   typedef unsigned short  UShort, *PUShort;
 304   typedef long            Long, *PLong;
 305
 306   typedef unsigned char   Byte, *PByte;
 307   typedef char            Bool;
 308
 309
 310   typedef union  Alignment_
 311   {
 312     long    l;
 313     void*   p;
 314     void  (*f)(void);
 315
 316   } Alignment, *PAlignment;
 317
 318
 319   typedef struct  TPoint_
 320   {
 321     Long  x;
 322     Long  y;
 323
 324   } TPoint;
 325
 326
 327   /* values for the `flags' bit field */
 328 #define Flow_Up           0x8
 329 #define Overshoot_Top     0x10
 330 #define Overshoot_Bottom  0x20
 331
 332
 333   /* States of each line, arc, and profile */
 334   typedef enum  TStates_
 335   {
 336     Unknown_State,
 337     Ascending_State,
 338     Descending_State,
 339     Flat_State
 340
 341   } TStates;
 342
 343
 344   typedef struct TProfile_  TProfile;
 345   typedef TProfile*         PProfile;
 346
 347   struct  TProfile_
 348   {
 349     FT_F26Dot6  X;           /* current coordinate during sweep          */
 350     PProfile    link;        /* link to next profile (various purposes)  */
 351     PLong       offset;      /* start of profile's data in render pool   */
 352     unsigned    flags;       /* Bit 0-2: drop-out mode                   */
 353                              /* Bit 3: profile orientation (up/down)     */
 354                              /* Bit 4: is top profile?                   */
 355                              /* Bit 5: is bottom profile?                */
 356     long        height;      /* profile's height in scanlines            */
 357     long        start;       /* profile's starting scanline              */
 358
 359     unsigned    countL;      /* number of lines to step before this      */
 360                              /* profile becomes drawable                 */
 361
 362     PProfile    next;        /* next profile in same contour, used       */
 363                              /* during drop-out control                  */
 364   };
 365
 366   typedef PProfile   TProfileList;
 367   typedef PProfile*  PProfileList;
 368
 369
 370   /* Simple record used to implement a stack of bands, required */
 371   /* by the sub-banding mechanism                               */
 372   typedef struct  black_TBand_
 373   {
 374     Short  y_min;   /* band's minimum */
 375     Short  y_max;   /* band's maximum */
 376
 377   } black_TBand;
 378
 379
 380 #define AlignProfileSize \
 381   ( ( sizeof ( TProfile ) + sizeof ( Alignment ) - 1 ) / sizeof ( long ) )
 382
 383
 384 #undef RAS_ARG
 385 #undef RAS_ARGS
 386 #undef RAS_VAR
 387 #undef RAS_VARS
 388
 389 #ifdef FT_STATIC_RASTER
 390
 391
 392 #define RAS_ARGS       /* void */
 393 #define RAS_ARG        /* void */
 394
 395 #define RAS_VARS       /* void */
 396 #define RAS_VAR        /* void */
 397
 398 #define FT_UNUSED_RASTER  do { } while ( 0 )
 399
 400
 401 #else /* !FT_STATIC_RASTER */
 402
 403
 404 #define RAS_ARGS       black_PWorker  worker,
 405 #define RAS_ARG        black_PWorker  worker
 406
 407 #define RAS_VARS       worker,
 408 #define RAS_VAR        worker
 409
 410 #define FT_UNUSED_RASTER  FT_UNUSED( worker )
 411
 412
 413 #endif /* !FT_STATIC_RASTER */
 414
 415
 416   typedef struct black_TWorker_  black_TWorker, *black_PWorker;
 417
 418
 419   /* prototypes used for sweep function dispatch */
 420   typedef void
 421   Function_Sweep_Init( RAS_ARGS Short*  min,
 422                                 Short*  max );
 423
 424   typedef void
 425   Function_Sweep_Span( RAS_ARGS Short       y,
 426                                 FT_F26Dot6  x1,
 427                                 FT_F26Dot6  x2,
 428                                 PProfile    left,
 429                                 PProfile    right );
 430
 431   typedef void
 432   Function_Sweep_Step( RAS_ARG );
 433
 434
 435   /* NOTE: These operations are only valid on 2's complement processors */
 436 #undef FLOOR
 437 #undef CEILING
 438 #undef TRUNC
 439 #undef SCALED
 440
 441 #define FLOOR( x )    ( (x) & -ras.precision )
 442 #define CEILING( x )  ( ( (x) + ras.precision - 1 ) & -ras.precision )
 443 #define TRUNC( x )    ( (signed long)(x) >> ras.precision_bits )
 444 #define FRAC( x )     ( (x) & ( ras.precision - 1 ) )
 445 #define SCALED( x )   ( ( (x) << ras.scale_shift ) - ras.precision_half )
 446
 447 #define IS_BOTTOM_OVERSHOOT( x )  ( CEILING( x ) - x >= ras.precision_half )
 448 #define IS_TOP_OVERSHOOT( x )     ( x - FLOOR( x ) >= ras.precision_half )
 449
 450   /* The most used variables are positioned at the top of the structure. */
 451   /* Thus, their offset can be coded with less opcodes, resulting in a   */
 452   /* smaller executable.                                                 */
 453
 454   struct  black_TWorker_
 455   {
 456     Int         precision_bits;     /* precision related variables         */
 457     Int         precision;
 458     Int         precision_half;
 459     Int         precision_shift;
 460     Int         precision_step;
 461     Int         precision_jitter;
 462
 463     Int         scale_shift;        /* == precision_shift   for bitmaps    */
 464                                     /* == precision_shift+1 for pixmaps    */
 465
 466     PLong       buff;               /* The profiles buffer                 */
 467     PLong       sizeBuff;           /* Render pool size                    */
 468     PLong       maxBuff;            /* Profiles buffer size                */
 469     PLong       top;                /* Current cursor in buffer            */
 470
 471     FT_Error    error;
 472
 473     Int         numTurns;           /* number of Y-turns in outline        */
 474
 475     TPoint*     arc;                /* current Bezier arc pointer          */
 476
 477     UShort      bWidth;             /* target bitmap width                 */
 478     PByte       bTarget;            /* target bitmap buffer                */
 479     PByte       gTarget;            /* target pixmap buffer                */
 480
 481     Long        lastX, lastY;
 482     Long        minY, maxY;
 483
 484     UShort      num_Profs;          /* current number of profiles          */
 485
 486     Bool        fresh;              /* signals a fresh new profile which   */
 487                                     /* `start' field must be completed     */
 488     Bool        joint;              /* signals that the last arc ended     */
 489                                     /* exactly on a scanline.  Allows      */
 490                                     /* removal of doublets                 */
 491     PProfile    cProfile;           /* current profile                     */
 492     PProfile    fProfile;           /* head of linked list of profiles     */
 493     PProfile    gProfile;           /* contour's first profile in case     */
 494                                     /* of impact                           */
 495
 496     TStates     state;              /* rendering state                     */
 497
 498     FT_Bitmap   target;             /* description of target bit/pixmap    */
 499     FT_Outline  outline;
 500
 501     Long        traceOfs;           /* current offset in target bitmap     */
 502     Long        traceG;             /* current offset in target pixmap     */
 503
 504     Short       traceIncr;          /* sweep's increment in target bitmap  */
 505
 506     Short       gray_min_x;         /* current min x during gray rendering */
 507     Short       gray_max_x;         /* current max x during gray rendering */
 508
 509     /* dispatch variables */
 510
 511     Function_Sweep_Init*  Proc_Sweep_Init;
 512     Function_Sweep_Span*  Proc_Sweep_Span;
 513     Function_Sweep_Span*  Proc_Sweep_Drop;
 514     Function_Sweep_Step*  Proc_Sweep_Step;
 515
 516     Byte        dropOutControl;     /* current drop_out control method     */
 517
 518     Bool        second_pass;        /* indicates whether a horizontal pass */
 519                                     /* should be performed to control      */
 520                                     /* drop-out accurately when calling    */
 521                                     /* Render_Glyph.  Note that there is   */
 522                                     /* no horizontal pass during gray      */
 523                                     /* rendering.                          */
 524
 525     TPoint      arcs[3 * MaxBezier + 1]; /* The Bezier stack               */
 526
 527     black_TBand  band_stack[16];    /* band stack used for sub-banding     */
 528     Int          band_top;          /* band stack top                      */
 529
 530 #ifdef FT_RASTER_OPTION_ANTI_ALIASING
 531
 532     Byte*       grays;
 533
 534     Byte        gray_lines[RASTER_GRAY_LINES];
 535                                 /* Intermediate table used to render the   */
 536                                 /* graylevels pixmaps.                     */
 537                                 /* gray_lines is a buffer holding two      */
 538                                 /* monochrome scanlines                    */
 539
 540     Short       gray_width;     /* width in bytes of one monochrome        */
 541                                 /* intermediate scanline of gray_lines.    */
 542                                 /* Each gray pixel takes 2 bits long there */
 543
 544                        /* The gray_lines must hold 2 lines, thus with size */
 545                        /* in bytes of at least `gray_width*2'.             */
 546
 547 #endif /* FT_RASTER_ANTI_ALIASING */
 548
 549   };
 550
 551
 552   typedef struct  black_TRaster_
 553   {
 554     char*          buffer;
 555     long           buffer_size;
 556     void*          memory;
 557     black_PWorker  worker;
 558     Byte           grays[5];
 559     Short          gray_width;
 560
 561   } black_TRaster, *black_PRaster;
 562
 563 #ifdef FT_STATIC_RASTER
 564
 565   static black_TWorker  cur_ras;
 566 #define ras  cur_ras
 567
 568 #else /* !FT_STATIC_RASTER */
 569
 570 #define ras  (*worker)
 571
 572 #endif /* !FT_STATIC_RASTER */
 573
 574
 575 #ifdef FT_RASTER_OPTION_ANTI_ALIASING
 576
 577   /* A lookup table used to quickly count set bits in four gray 2x2 */
 578   /* cells.  The values of the table have been produced with the    */
 579   /* following code:                                                */
 580   /*                                                                */
 581   /*   for ( i = 0; i < 256; i++ )                                  */
 582   /*   {                                                            */
 583   /*     l = 0;                                                     */
 584   /*     j = i;                                                     */
 585   /*                                                                */
 586   /*     for ( c = 0; c < 4; c++ )                                  */
 587   /*     {                                                          */
 588   /*       l <<= 4;                                                 */
 589   /*                                                                */
 590   /*       if ( j & 0x80 ) l++;                                     */
 591   /*       if ( j & 0x40 ) l++;                                     */
 592   /*                                                                */
 593   /*       j = ( j << 2 ) & 0xFF;                                   */
 594   /*     }                                                          */
 595   /*     printf( "0x%04X", l );                                     */
 596   /*   }                                                            */
 597   /*                                                                */
 598
 599   static const short  count_table[256] =
 600   {
 601     0x0000, 0x0001, 0x0001, 0x0002, 0x0010, 0x0011, 0x0011, 0x0012,
 602     0x0010, 0x0011, 0x0011, 0x0012, 0x0020, 0x0021, 0x0021, 0x0022,
 603     0x0100, 0x0101, 0x0101, 0x0102, 0x0110, 0x0111, 0x0111, 0x0112,
 604     0x0110, 0x0111, 0x0111, 0x0112, 0x0120, 0x0121, 0x0121, 0x0122,
 605     0x0100, 0x0101, 0x0101, 0x0102, 0x0110, 0x0111, 0x0111, 0x0112,
 606     0x0110, 0x0111, 0x0111, 0x0112, 0x0120, 0x0121, 0x0121, 0x0122,
 607     0x0200, 0x0201, 0x0201, 0x0202, 0x0210, 0x0211, 0x0211, 0x0212,
 608     0x0210, 0x0211, 0x0211, 0x0212, 0x0220, 0x0221, 0x0221, 0x0222,
 609     0x1000, 0x1001, 0x1001, 0x1002, 0x1010, 0x1011, 0x1011, 0x1012,
 610     0x1010, 0x1011, 0x1011, 0x1012, 0x1020, 0x1021, 0x1021, 0x1022,
 611     0x1100, 0x1101, 0x1101, 0x1102, 0x1110, 0x1111, 0x1111, 0x1112,
 612     0x1110, 0x1111, 0x1111, 0x1112, 0x1120, 0x1121, 0x1121, 0x1122,
 613     0x1100, 0x1101, 0x1101, 0x1102, 0x1110, 0x1111, 0x1111, 0x1112,
 614     0x1110, 0x1111, 0x1111, 0x1112, 0x1120, 0x1121, 0x1121, 0x1122,
 615     0x1200, 0x1201, 0x1201, 0x1202, 0x1210, 0x1211, 0x1211, 0x1212,
 616     0x1210, 0x1211, 0x1211, 0x1212, 0x1220, 0x1221, 0x1221, 0x1222,
 617     0x1000, 0x1001, 0x1001, 0x1002, 0x1010, 0x1011, 0x1011, 0x1012,
 618     0x1010, 0x1011, 0x1011, 0x1012, 0x1020, 0x1021, 0x1021, 0x1022,
 619     0x1100, 0x1101, 0x1101, 0x1102, 0x1110, 0x1111, 0x1111, 0x1112,
 620     0x1110, 0x1111, 0x1111, 0x1112, 0x1120, 0x1121, 0x1121, 0x1122,
 621     0x1100, 0x1101, 0x1101, 0x1102, 0x1110, 0x1111, 0x1111, 0x1112,
 622     0x1110, 0x1111, 0x1111, 0x1112, 0x1120, 0x1121, 0x1121, 0x1122,
 623     0x1200, 0x1201, 0x1201, 0x1202, 0x1210, 0x1211, 0x1211, 0x1212,
 624     0x1210, 0x1211, 0x1211, 0x1212, 0x1220, 0x1221, 0x1221, 0x1222,
 625     0x2000, 0x2001, 0x2001, 0x2002, 0x2010, 0x2011, 0x2011, 0x2012,
 626     0x2010, 0x2011, 0x2011, 0x2012, 0x2020, 0x2021, 0x2021, 0x2022,
 627     0x2100, 0x2101, 0x2101, 0x2102, 0x2110, 0x2111, 0x2111, 0x2112,
 628     0x2110, 0x2111, 0x2111, 0x2112, 0x2120, 0x2121, 0x2121, 0x2122,
 629     0x2100, 0x2101, 0x2101, 0x2102, 0x2110, 0x2111, 0x2111, 0x2112,
 630     0x2110, 0x2111, 0x2111, 0x2112, 0x2120, 0x2121, 0x2121, 0x2122,
 631     0x2200, 0x2201, 0x2201, 0x2202, 0x2210, 0x2211, 0x2211, 0x2212,
 632     0x2210, 0x2211, 0x2211, 0x2212, 0x2220, 0x2221, 0x2221, 0x2222
 633   };
 634
 635 #endif /* FT_RASTER_OPTION_ANTI_ALIASING */
 636
 637
 638
 639   /*************************************************************************/
 640   /*************************************************************************/
 641   /**                                                                     **/
 642   /**  PROFILES COMPUTATION                                               **/
 643   /**                                                                     **/
 644   /*************************************************************************/
 645   /*************************************************************************/
 646
 647
 648   /*************************************************************************/
 649   /*                                                                       */
 650   /* <Function>                                                            */
 651   /*    Set_High_Precision                                                 */
 652   /*                                                                       */
 653   /* <Description>                                                         */
 654   /*    Set precision variables according to param flag.                   */
 655   /*                                                                       */
 656   /* <Input>                                                               */
 657   /*    High :: Set to True for high precision (typically for ppem < 18),  */
 658   /*            false otherwise.                                           */
 659   /*                                                                       */
 660   static void
 661   Set_High_Precision( RAS_ARGS Int  High )
 662   {
 663     /*
 664      * `precision_step' is used in `Bezier_Up' to decide when to split a
 665      * given y-monotonous Bezier arc that crosses a scanline before
 666      * approximating it as a straight segment.  The default value of 32 (for
 667      * low accuracy) corresponds to
 668      *
 669      *   32 / 64 == 0.5 pixels ,
 670      *
 671      * while for the high accuracy case we have
 672      *
 673      *   256/ (1 << 12) = 0.0625 pixels .
 674      *
 675      * `precision_jitter' is an epsilon threshold used in
 676      * `Vertical_Sweep_Span' to deal with small imperfections in the Bezier
 677      * decomposition (after all, we are working with approximations only);
 678      * it avoids switching on additional pixels which would cause artifacts
 679      * otherwise.
 680      *
 681      * The value of `precision_jitter' has been determined heuristically.
 682      *
 683      */
 684
 685     if ( High )
 686     {
 687       ras.precision_bits   = 12;
 688       ras.precision_step   = 256;
 689       ras.precision_jitter = 30;
 690     }
 691     else
 692     {
 693       ras.precision_bits   = 6;
 694       ras.precision_step   = 32;
 695       ras.precision_jitter = 2;
 696     }
 697
 698     FT_TRACE6(( "Set_High_Precision(%s)\n", High ? "true" : "false" ));
 699
 700     ras.precision       = 1 << ras.precision_bits;
 701     ras.precision_half  = ras.precision / 2;
 702     ras.precision_shift = ras.precision_bits - Pixel_Bits;
 703   }
 704
 705
 706   /*************************************************************************/
 707   /*                                                                       */
 708   /* <Function>                                                            */
 709   /*    New_Profile                                                        */
 710   /*                                                                       */
 711   /* <Description>                                                         */
 712   /*    Create a new profile in the render pool.                           */
 713   /*                                                                       */
 714   /* <Input>                                                               */
 715   /*    aState    :: The state/orientation of the new profile.             */
 716   /*                                                                       */
 717   /*    overshoot :: Whether the profile's unrounded start position        */
 718   /*                 differs by at least a half pixel.                     */
 719   /*                                                                       */
 720   /* <Return>                                                              */
 721   /*   SUCCESS on success.  FAILURE in case of overflow or of incoherent   */
 722   /*   profile.                                                            */
 723   /*                                                                       */
 724   static Bool
 725   New_Profile( RAS_ARGS TStates  aState,
 726                         Bool     overshoot )
 727   {
 728     if ( !ras.fProfile )
 729     {
 730       ras.cProfile  = (PProfile)ras.top;
 731       ras.fProfile  = ras.cProfile;
 732       ras.top      += AlignProfileSize;
 733     }
 734
 735     if ( ras.top >= ras.maxBuff )
 736     {
 737       ras.error = Raster_Err_Overflow;
 738       return FAILURE;
 739     }
 740
 741     ras.cProfile->flags  = 0;
 742     ras.cProfile->start  = 0;
 743     ras.cProfile->height = 0;
 744     ras.cProfile->offset = ras.top;
 745     ras.cProfile->link   = (PProfile)0;
 746     ras.cProfile->next   = (PProfile)0;
 747     ras.cProfile->flags  = ras.dropOutControl;
 748
 749     switch ( aState )
 750     {
 751     case Ascending_State:
 752       ras.cProfile->flags |= Flow_Up;
 753       if ( overshoot )
 754         ras.cProfile->flags |= Overshoot_Bottom;
 755
 756       FT_TRACE6(( "New ascending profile = %p\n", ras.cProfile ));
 757       break;
 758
 759     case Descending_State:
 760       if ( overshoot )
 761         ras.cProfile->flags |= Overshoot_Top;
 762       FT_TRACE6(( "New descending profile = %p\n", ras.cProfile ));
 763       break;
 764
 765     default:
 766       FT_ERROR(( "New_Profile: invalid profile direction\n" ));
 767       ras.error = Raster_Err_Invalid;
 768       return FAILURE;
 769     }
 770
 771     if ( !ras.gProfile )
 772       ras.gProfile = ras.cProfile;
 773
 774     ras.state = aState;
 775     ras.fresh = TRUE;
 776     ras.joint = FALSE;
 777
 778     return SUCCESS;
 779   }
 780
 781
 782   /*************************************************************************/
 783   /*                                                                       */
 784   /* <Function>                                                            */
 785   /*    End_Profile                                                        */
 786   /*                                                                       */
 787   /* <Description>                                                         */
 788   /*    Finalize the current profile.                                      */
 789   /*                                                                       */
 790   /* <Input>                                                               */
 791   /*    overshoot :: Whether the profile's unrounded end position differs  */
 792   /*                 by at least a half pixel.                             */
 793   /*                                                                       */
 794   /* <Return>                                                              */
 795   /*    SUCCESS on success.  FAILURE in case of overflow or incoherency.   */
 796   /*                                                                       */
 797   static Bool
 798   End_Profile( RAS_ARGS Bool  overshoot )
 799   {
 800     Long      h;
 801     PProfile  oldProfile;
 802
 803
 804     h = (Long)( ras.top - ras.cProfile->offset );
 805
 806     if ( h < 0 )
 807     {
 808       FT_ERROR(( "End_Profile: negative height encountered\n" ));
 809       ras.error = Raster_Err_Neg_Height;
 810       return FAILURE;
 811     }
 812
 813     if ( h > 0 )
 814     {
 815       FT_TRACE6(( "Ending profile %p, start = %ld, height = %ld\n",
 816                   ras.cProfile, ras.cProfile->start, h ));
 817
 818       ras.cProfile->height = h;
 819       if ( overshoot )
 820       {
 821         if ( ras.cProfile->flags & Flow_Up )
 822           ras.cProfile->flags |= Overshoot_Top;
 823         else
 824           ras.cProfile->flags |= Overshoot_Bottom;
 825       }
 826
 827       oldProfile   = ras.cProfile;
 828       ras.cProfile = (PProfile)ras.top;
 829
 830       ras.top += AlignProfileSize;
 831
 832       ras.cProfile->height = 0;
 833       ras.cProfile->offset = ras.top;
 834
 835       oldProfile->next = ras.cProfile;
 836       ras.num_Profs++;
 837     }
 838
 839     if ( ras.top >= ras.maxBuff )
 840     {
 841       FT_TRACE1(( "overflow in End_Profile\n" ));
 842       ras.error = Raster_Err_Overflow;
 843       return FAILURE;
 844     }
 845
 846     ras.joint = FALSE;
 847
 848     return SUCCESS;
 849   }
 850
 851
 852   /*************************************************************************/
 853   /*                                                                       */
 854   /* <Function>                                                            */
 855   /*    Insert_Y_Turn                                                      */
 856   /*                                                                       */
 857   /* <Description>                                                         */
 858   /*    Insert a salient into the sorted list placed on top of the render  */
 859   /*    pool.                                                              */
 860   /*                                                                       */
 861   /* <Input>                                                               */
 862   /*    New y scanline position.                                           */
 863   /*                                                                       */
 864   /* <Return>                                                              */
 865   /*    SUCCESS on success.  FAILURE in case of overflow.                  */
 866   /*                                                                       */
 867   static Bool
 868   Insert_Y_Turn( RAS_ARGS Int  y )
 869   {
 870     PLong  y_turns;
 871     Int    y2, n;
 872
 873
 874     n       = ras.numTurns - 1;
 875     y_turns = ras.sizeBuff - ras.numTurns;
 876
 877     /* look for first y value that is <= */
 878     while ( n >= 0 && y < y_turns[n] )
 879       n--;
 880
 881     /* if it is <, simply insert it, ignore if == */
 882     if ( n >= 0 && y > y_turns[n] )
 883       while ( n >= 0 )
 884       {
 885         y2 = (Int)y_turns[n];
 886         y_turns[n] = y;
 887         y = y2;
 888         n--;
 889       }
 890
 891     if ( n < 0 )
 892     {
 893       ras.maxBuff--;
 894       if ( ras.maxBuff <= ras.top )
 895       {
 896         ras.error = Raster_Err_Overflow;
 897         return FAILURE;
 898       }
 899       ras.numTurns++;
 900       ras.sizeBuff[-ras.numTurns] = y;
 901     }
 902
 903     return SUCCESS;
 904   }
 905
 906
 907   /*************************************************************************/
 908   /*                                                                       */
 909   /* <Function>                                                            */
 910   /*    Finalize_Profile_Table                                             */
 911   /*                                                                       */
 912   /* <Description>                                                         */
 913   /*    Adjust all links in the profiles list.                             */
 914   /*                                                                       */
 915   /* <Return>                                                              */
 916   /*    SUCCESS on success.  FAILURE in case of overflow.                  */
 917   /*                                                                       */
 918   static Bool
 919   Finalize_Profile_Table( RAS_ARG )
 920   {
 921     Int       bottom, top;
 922     UShort    n;
 923     PProfile  p;
 924
 925
 926     n = ras.num_Profs;
 927     p = ras.fProfile;
 928
 929     if ( n > 1 && p )
 930     {
 931       while ( n > 0 )
 932       {
 933         if ( n > 1 )
 934           p->link = (PProfile)( p->offset + p->height );
 935         else
 936           p->link = NULL;
 937
 938         if ( p->flags & Flow_Up )
 939         {
 940           bottom = (Int)p->start;
 941           top    = (Int)( p->start + p->height - 1 );
 942         }
 943         else
 944         {
 945           bottom     = (Int)( p->start - p->height + 1 );
 946           top        = (Int)p->start;
 947           p->start   = bottom;
 948           p->offset += p->height - 1;
 949         }
 950
 951         if ( Insert_Y_Turn( RAS_VARS bottom )  ||
 952              Insert_Y_Turn( RAS_VARS top + 1 ) )
 953           return FAILURE;
 954
 955         p = p->link;
 956         n--;
 957       }
 958     }
 959     else
 960       ras.fProfile = NULL;
 961
 962     return SUCCESS;
 963   }
 964
 965
 966   /*************************************************************************/
 967   /*                                                                       */
 968   /* <Function>                                                            */
 969   /*    Split_Conic                                                        */
 970   /*                                                                       */
 971   /* <Description>                                                         */
 972   /*    Subdivide one conic Bezier into two joint sub-arcs in the Bezier   */
 973   /*    stack.                                                             */
 974   /*                                                                       */
 975   /* <Input>                                                               */
 976   /*    None (subdivided Bezier is taken from the top of the stack).       */
 977   /*                                                                       */
 978   /* <Note>                                                                */
 979   /*    This routine is the `beef' of this component.  It is  _the_ inner  */
 980   /*    loop that should be optimized to hell to get the best performance. */
 981   /*                                                                       */
 982   static void
 983   Split_Conic( TPoint*  base )
 984   {
 985     Long  a, b;
 986
 987
 988     base[4].x = base[2].x;
 989     b = base[1].x;
 990     a = base[3].x = ( base[2].x + b ) / 2;
 991     b = base[1].x = ( base[0].x + b ) / 2;
 992     base[2].x = ( a + b ) / 2;
 993
 994     base[4].y = base[2].y;
 995     b = base[1].y;
 996     a = base[3].y = ( base[2].y + b ) / 2;
 997     b = base[1].y = ( base[0].y + b ) / 2;
 998     base[2].y = ( a + b ) / 2;
 999
1000     /* hand optimized.  gcc doesn't seem to be too good at common      */
1001     /* expression substitution and instruction scheduling ;-)          */
1002   }
1003
1004
1005   /*************************************************************************/
1006   /*                                                                       */
1007   /* <Function>                                                            */
1008   /*    Split_Cubic                                                        */
1009   /*                                                                       */
1010   /* <Description>                                                         */
1011   /*    Subdivide a third-order Bezier arc into two joint sub-arcs in the  */
1012   /*    Bezier stack.                                                      */
1013   /*                                                                       */
1014   /* <Note>                                                                */
1015   /*    This routine is the `beef' of the component.  It is one of _the_   */
1016   /*    inner loops that should be optimized like hell to get the best     */
1017   /*    performance.                                                       */
1018   /*                                                                       */
1019   static void
1020   Split_Cubic( TPoint*  base )
1021   {
1022     Long  a, b, c, d;
1023
1024
1025     base[6].x = base[3].x;
1026     c = base[1].x;
1027     d = base[2].x;
1028     base[1].x = a = ( base[0].x + c + 1 ) >> 1;
1029     base[5].x = b = ( base[3].x + d + 1 ) >> 1;
1030     c = ( c + d + 1 ) >> 1;
1031     base[2].x = a = ( a + c + 1 ) >> 1;
1032     base[4].x = b = ( b + c + 1 ) >> 1;
1033     base[3].x = ( a + b + 1 ) >> 1;
1034
1035     base[6].y = base[3].y;
1036     c = base[1].y;
1037     d = base[2].y;
1038     base[1].y = a = ( base[0].y + c + 1 ) >> 1;
1039     base[5].y = b = ( base[3].y + d + 1 ) >> 1;
1040     c = ( c + d + 1 ) >> 1;
1041     base[2].y = a = ( a + c + 1 ) >> 1;
1042     base[4].y = b = ( b + c + 1 ) >> 1;
1043     base[3].y = ( a + b + 1 ) >> 1;
1044   }
1045
1046
1047   /*************************************************************************/
1048   /*                                                                       */
1049   /* <Function>                                                            */
1050   /*    Line_Up                                                            */
1051   /*                                                                       */
1052   /* <Description>                                                         */
1053   /*    Compute the x-coordinates of an ascending line segment and store   */
1054   /*    them in the render pool.                                           */
1055   /*                                                                       */
1056   /* <Input>                                                               */
1057   /*    x1   :: The x-coordinate of the segment's start point.             */
1058   /*                                                                       */
1059   /*    y1   :: The y-coordinate of the segment's start point.             */
1060   /*                                                                       */
1061   /*    x2   :: The x-coordinate of the segment's end point.               */
1062   /*                                                                       */
1063   /*    y2   :: The y-coordinate of the segment's end point.               */
1064   /*                                                                       */
1065   /*    miny :: A lower vertical clipping bound value.                     */
1066   /*                                                                       */
1067   /*    maxy :: An upper vertical clipping bound value.                    */
1068   /*                                                                       */
1069   /* <Return>                                                              */
1070   /*    SUCCESS on success, FAILURE on render pool overflow.               */
1071   /*                                                                       */
1072   static Bool
1073   Line_Up( RAS_ARGS Long  x1,
1074                     Long  y1,
1075                     Long  x2,
1076                     Long  y2,
1077                     Long  miny,
1078                     Long  maxy )
1079   {
1080     Long   Dx, Dy;
1081     Int    e1, e2, f1, f2, size;     /* XXX: is `Short' sufficient? */
1082     Long   Ix, Rx, Ax;
1083
1084     PLong  top;
1085
1086
1087     Dx = x2 - x1;
1088     Dy = y2 - y1;
1089
1090     if ( Dy <= 0 || y2 < miny || y1 > maxy )
1091       return SUCCESS;
1092
1093     if ( y1 < miny )
1094     {
1095       /* Take care: miny-y1 can be a very large value; we use     */
1096       /*            a slow MulDiv function to avoid clipping bugs */
1097       x1 += SMulDiv( Dx, miny - y1, Dy );
1098       e1  = (Int)TRUNC( miny );
1099       f1  = 0;
1100     }
1101     else
1102     {
1103       e1 = (Int)TRUNC( y1 );
1104       f1 = (Int)FRAC( y1 );
1105     }
1106
1107     if ( y2 > maxy )
1108     {
1109       /* x2 += FMulDiv( Dx, maxy - y2, Dy );  UNNECESSARY */
1110       e2  = (Int)TRUNC( maxy );
1111       f2  = 0;
1112     }
1113     else
1114     {
1115       e2 = (Int)TRUNC( y2 );
1116       f2 = (Int)FRAC( y2 );
1117     }
1118
1119     if ( f1 > 0 )
1120     {
1121       if ( e1 == e2 )
1122         return SUCCESS;
1123       else
1124       {
1125         x1 += SMulDiv( Dx, ras.precision - f1, Dy );
1126         e1 += 1;
1127       }
1128     }
1129     else
1130       if ( ras.joint )
1131       {
1132         ras.top--;
1133         ras.joint = FALSE;
1134       }
1135
1136     ras.joint = (char)( f2 == 0 );
1137
1138     if ( ras.fresh )
1139     {
1140       ras.cProfile->start = e1;
1141       ras.fresh           = FALSE;
1142     }
1143
1144     size = e2 - e1 + 1;
1145     if ( ras.top + size >= ras.maxBuff )
1146     {
1147       ras.error = Raster_Err_Overflow;
1148       return FAILURE;
1149     }
1150
1151     if ( Dx > 0 )
1152     {
1153       Ix = SMulDiv( ras.precision, Dx, Dy);
1154       Rx = ( ras.precision * Dx ) % Dy;
1155       Dx = 1;
1156     }
1157     else
1158     {
1159       Ix = SMulDiv( ras.precision, -Dx, Dy) * -1;
1160       Rx =    ( ras.precision * -Dx ) % Dy;
1161       Dx = -1;
1162     }
1163
1164     Ax  = -Dy;
1165     top = ras.top;
1166
1167     while ( size > 0 )
1168     {
1169       *top++ = x1;
1170
1171       x1 += Ix;
1172       Ax += Rx;
1173       if ( Ax >= 0 )
1174       {
1175         Ax -= Dy;
1176         x1 += Dx;
1177       }
1178       size--;
1179     }
1180
1181     ras.top = top;
1182     return SUCCESS;
1183   }
1184
1185
1186   /*************************************************************************/
1187   /*                                                                       */
1188   /* <Function>                                                            */
1189   /*    Line_Down                                                          */
1190   /*                                                                       */
1191   /* <Description>                                                         */
1192   /*    Compute the x-coordinates of an descending line segment and store  */
1193   /*    them in the render pool.                                           */
1194   /*                                                                       */
1195   /* <Input>                                                               */
1196   /*    x1   :: The x-coordinate of the segment's start point.             */
1197   /*                                                                       */
1198   /*    y1   :: The y-coordinate of the segment's start point.             */
1199   /*                                                                       */
1200   /*    x2   :: The x-coordinate of the segment's end point.               */
1201   /*                                                                       */
1202   /*    y2   :: The y-coordinate of the segment's end point.               */
1203   /*                                                                       */
1204   /*    miny :: A lower vertical clipping bound value.                     */
1205   /*                                                                       */
1206   /*    maxy :: An upper vertical clipping bound value.                    */
1207   /*                                                                       */
1208   /* <Return>                                                              */
1209   /*    SUCCESS on success, FAILURE on render pool overflow.               */
1210   /*                                                                       */
1211   static Bool
1212   Line_Down( RAS_ARGS Long  x1,
1213                       Long  y1,
1214                       Long  x2,
1215                       Long  y2,
1216                       Long  miny,
1217                       Long  maxy )
1218   {
1219     Bool  result, fresh;
1220
1221
1222     fresh  = ras.fresh;
1223
1224     result = Line_Up( RAS_VARS x1, -y1, x2, -y2, -maxy, -miny );
1225
1226     if ( fresh && !ras.fresh )
1227       ras.cProfile->start = -ras.cProfile->start;
1228
1229     return result;
1230   }
1231
1232
1233   /* A function type describing the functions used to split Bezier arcs */
1234   typedef void  (*TSplitter)( TPoint*  base );
1235
1236
1237   /*************************************************************************/
1238   /*                                                                       */
1239   /* <Function>                                                            */
1240   /*    Bezier_Up                                                          */
1241   /*                                                                       */
1242   /* <Description>                                                         */
1243   /*    Compute the x-coordinates of an ascending Bezier arc and store     */
1244   /*    them in the render pool.                                           */
1245   /*                                                                       */
1246   /* <Input>                                                               */
1247   /*    degree   :: The degree of the Bezier arc (either 2 or 3).          */
1248   /*                                                                       */
1249   /*    splitter :: The function to split Bezier arcs.                     */
1250   /*                                                                       */
1251   /*    miny     :: A lower vertical clipping bound value.                 */
1252   /*                                                                       */
1253   /*    maxy     :: An upper vertical clipping bound value.                */
1254   /*                                                                       */
1255   /* <Return>                                                              */
1256   /*    SUCCESS on success, FAILURE on render pool overflow.               */
1257   /*                                                                       */
1258   static Bool
1259   Bezier_Up( RAS_ARGS Int        degree,
1260                       TSplitter  splitter,
1261                       Long       miny,
1262                       Long       maxy )
1263   {
1264     Long   y1, y2, e, e2, e0;
1265     Short  f1;
1266
1267     TPoint*  arc;
1268     TPoint*  start_arc;
1269
1270     PLong top;
1271
1272
1273     arc = ras.arc;
1274     y1  = arc[degree].y;
1275     y2  = arc[0].y;
1276     top = ras.top;
1277
1278     if ( y2 < miny || y1 > maxy )
1279       goto Fin;
1280
1281     e2 = FLOOR( y2 );
1282
1283     if ( e2 > maxy )
1284       e2 = maxy;
1285
1286     e0 = miny;
1287
1288     if ( y1 < miny )
1289       e = miny;
1290     else
1291     {
1292       e  = CEILING( y1 );
1293       f1 = (Short)( FRAC( y1 ) );
1294       e0 = e;
1295
1296       if ( f1 == 0 )
1297       {
1298         if ( ras.joint )
1299         {
1300           top--;
1301           ras.joint = FALSE;
1302         }
1303
1304         *top++ = arc[degree].x;
1305
1306         e += ras.precision;
1307       }
1308     }
1309
1310     if ( ras.fresh )
1311     {
1312       ras.cProfile->start = TRUNC( e0 );
1313       ras.fresh = FALSE;
1314     }
1315
1316     if ( e2 < e )
1317       goto Fin;
1318
1319     if ( ( top + TRUNC( e2 - e ) + 1 ) >= ras.maxBuff )
1320     {
1321       ras.top   = top;
1322       ras.error = Raster_Err_Overflow;
1323       return FAILURE;
1324     }
1325
1326     start_arc = arc;
1327
1328     while ( arc >= start_arc && e <= e2 )
1329     {
1330       ras.joint = FALSE;
1331
1332       y2 = arc[0].y;
1333
1334       if ( y2 > e )
1335       {
1336         y1 = arc[degree].y;
1337         if ( y2 - y1 >= ras.precision_step )
1338         {
1339           splitter( arc );
1340           arc += degree;
1341         }
1342         else
1343         {
1344           *top++ = arc[degree].x + FMulDiv( arc[0].x - arc[degree].x,
1345                                             e - y1, y2 - y1 );
1346           arc -= degree;
1347           e   += ras.precision;
1348         }
1349       }
1350       else
1351       {
1352         if ( y2 == e )
1353         {
1354           ras.joint  = TRUE;
1355           *top++     = arc[0].x;
1356
1357           e += ras.precision;
1358         }
1359         arc -= degree;
1360       }
1361     }
1362
1363   Fin:
1364     ras.top  = top;
1365     ras.arc -= degree;
1366     return SUCCESS;
1367   }
1368
1369
1370   /*************************************************************************/
1371   /*                                                                       */
1372   /* <Function>                                                            */
1373   /*    Bezier_Down                                                        */
1374   /*                                                                       */
1375   /* <Description>                                                         */
1376   /*    Compute the x-coordinates of an descending Bezier arc and store    */
1377   /*    them in the render pool.                                           */
1378   /*                                                                       */
1379   /* <Input>                                                               */
1380   /*    degree   :: The degree of the Bezier arc (either 2 or 3).          */
1381   /*                                                                       */
1382   /*    splitter :: The function to split Bezier arcs.                     */
1383   /*                                                                       */
1384   /*    miny     :: A lower vertical clipping bound value.                 */
1385   /*                                                                       */
1386   /*    maxy     :: An upper vertical clipping bound value.                */
1387   /*                                                                       */
1388   /* <Return>                                                              */
1389   /*    SUCCESS on success, FAILURE on render pool overflow.               */
1390   /*                                                                       */
1391   static Bool
1392   Bezier_Down( RAS_ARGS Int        degree,
1393                         TSplitter  splitter,
1394                         Long       miny,
1395                         Long       maxy )
1396   {
1397     TPoint*  arc = ras.arc;
1398     Bool     result, fresh;
1399
1400
1401     arc[0].y = -arc[0].y;
1402     arc[1].y = -arc[1].y;
1403     arc[2].y = -arc[2].y;
1404     if ( degree > 2 )
1405       arc[3].y = -arc[3].y;
1406
1407     fresh = ras.fresh;
1408
1409     result = Bezier_Up( RAS_VARS degree, splitter, -maxy, -miny );
1410
1411     if ( fresh && !ras.fresh )
1412       ras.cProfile->start = -ras.cProfile->start;
1413
1414     arc[0].y = -arc[0].y;
1415     return result;
1416   }
1417
1418
1419   /*************************************************************************/
1420   /*                                                                       */
1421   /* <Function>                                                            */
1422   /*    Line_To                                                            */
1423   /*                                                                       */
1424   /* <Description>                                                         */
1425   /*    Inject a new line segment and adjust the Profiles list.            */
1426   /*                                                                       */
1427   /* <Input>                                                               */
1428   /*   x :: The x-coordinate of the segment's end point (its start point   */
1429   /*        is stored in `lastX').                                         */
1430   /*                                                                       */
1431   /*   y :: The y-coordinate of the segment's end point (its start point   */
1432   /*        is stored in `lastY').                                         */
1433   /*                                                                       */
1434   /* <Return>                                                              */
1435   /*   SUCCESS on success, FAILURE on render pool overflow or incorrect    */
1436   /*   profile.                                                            */
1437   /*                                                                       */
1438   static Bool
1439   Line_To( RAS_ARGS Long  x,
1440                     Long  y )
1441   {
1442     /* First, detect a change of direction */
1443
1444     switch ( ras.state )
1445     {
1446     case Unknown_State:
1447       if ( y > ras.lastY )
1448       {
1449         if ( New_Profile( RAS_VARS Ascending_State,
1450                                    IS_BOTTOM_OVERSHOOT( ras.lastY ) ) )
1451           return FAILURE;
1452       }
1453       else
1454       {
1455         if ( y < ras.lastY )
1456           if ( New_Profile( RAS_VARS Descending_State,
1457                                      IS_TOP_OVERSHOOT( ras.lastY ) ) )
1458             return FAILURE;
1459       }
1460       break;
1461
1462     case Ascending_State:
1463       if ( y < ras.lastY )
1464       {
1465         if ( End_Profile( RAS_VARS IS_TOP_OVERSHOOT( ras.lastY ) ) ||
1466              New_Profile( RAS_VARS Descending_State,
1467                                    IS_TOP_OVERSHOOT( ras.lastY ) ) )
1468           return FAILURE;
1469       }
1470       break;
1471
1472     case Descending_State:
1473       if ( y > ras.lastY )
1474       {
1475         if ( End_Profile( RAS_VARS IS_BOTTOM_OVERSHOOT( ras.lastY ) ) ||
1476              New_Profile( RAS_VARS Ascending_State,
1477                                    IS_BOTTOM_OVERSHOOT( ras.lastY ) ) )
1478           return FAILURE;
1479       }
1480       break;
1481
1482     default:
1483       ;
1484     }
1485
1486     /* Then compute the lines */
1487
1488     switch ( ras.state )
1489     {
1490     case Ascending_State:
1491       if ( Line_Up( RAS_VARS ras.lastX, ras.lastY,
1492                              x, y, ras.minY, ras.maxY ) )
1493         return FAILURE;
1494       break;
1495
1496     case Descending_State:
1497       if ( Line_Down( RAS_VARS ras.lastX, ras.lastY,
1498                                x, y, ras.minY, ras.maxY ) )
1499         return FAILURE;
1500       break;
1501
1502     default:
1503       ;
1504     }
1505
1506     ras.lastX = x;
1507     ras.lastY = y;
1508
1509     return SUCCESS;
1510   }
1511
1512
1513   /*************************************************************************/
1514   /*                                                                       */
1515   /* <Function>                                                            */
1516   /*    Conic_To                                                           */
1517   /*                                                                       */
1518   /* <Description>                                                         */
1519   /*    Inject a new conic arc and adjust the profile list.                */
1520   /*                                                                       */
1521   /* <Input>                                                               */
1522   /*   cx :: The x-coordinate of the arc's new control point.              */
1523   /*                                                                       */
1524   /*   cy :: The y-coordinate of the arc's new control point.              */
1525   /*                                                                       */
1526   /*   x  :: The x-coordinate of the arc's end point (its start point is   */
1527   /*         stored in `lastX').                                           */
1528   /*                                                                       */
1529   /*   y  :: The y-coordinate of the arc's end point (its start point is   */
1530   /*         stored in `lastY').                                           */
1531   /*                                                                       */
1532   /* <Return>                                                              */
1533   /*   SUCCESS on success, FAILURE on render pool overflow or incorrect    */
1534   /*   profile.                                                            */
1535   /*                                                                       */
1536   static Bool
1537   Conic_To( RAS_ARGS Long  cx,
1538                      Long  cy,
1539                      Long  x,
1540                      Long  y )
1541   {
1542     Long     y1, y2, y3, x3, ymin, ymax;
1543     TStates  state_bez;
1544
1545
1546     ras.arc      = ras.arcs;
1547     ras.arc[2].x = ras.lastX;
1548     ras.arc[2].y = ras.lastY;
1549     ras.arc[1].x = cx;
1550     ras.arc[1].y = cy;
1551     ras.arc[0].x = x;
1552     ras.arc[0].y = y;
1553
1554     do
1555     {
1556       y1 = ras.arc[2].y;
1557       y2 = ras.arc[1].y;
1558       y3 = ras.arc[0].y;
1559       x3 = ras.arc[0].x;
1560
1561       /* first, categorize the Bezier arc */
1562
1563       if ( y1 <= y3 )
1564       {
1565         ymin = y1;
1566         ymax = y3;
1567       }
1568       else
1569       {
1570         ymin = y3;
1571         ymax = y1;
1572       }
1573
1574       if ( y2 < ymin || y2 > ymax )
1575       {
1576         /* this arc has no given direction, split it! */
1577         Split_Conic( ras.arc );
1578         ras.arc += 2;
1579       }
1580       else if ( y1 == y3 )
1581       {
1582         /* this arc is flat, ignore it and pop it from the Bezier stack */
1583         ras.arc -= 2;
1584       }
1585       else
1586       {
1587         /* the arc is y-monotonous, either ascending or descending */
1588         /* detect a change of direction                            */
1589         state_bez = y1 < y3 ? Ascending_State : Descending_State;
1590         if ( ras.state != state_bez )
1591         {
1592           Bool  o = state_bez == Ascending_State ? IS_BOTTOM_OVERSHOOT( y1 )
1593                                                  : IS_TOP_OVERSHOOT( y1 );
1594
1595
1596           /* finalize current profile if any */
1597           if ( ras.state != Unknown_State &&
1598                End_Profile( RAS_VARS o )  )
1599             goto Fail;
1600
1601           /* create a new profile */
1602           if ( New_Profile( RAS_VARS state_bez, o ) )
1603             goto Fail;
1604         }
1605
1606         /* now call the appropriate routine */
1607         if ( state_bez == Ascending_State )
1608         {
1609           if ( Bezier_Up( RAS_VARS 2, Split_Conic, ras.minY, ras.maxY ) )
1610             goto Fail;
1611         }
1612         else
1613           if ( Bezier_Down( RAS_VARS 2, Split_Conic, ras.minY, ras.maxY ) )
1614             goto Fail;
1615       }
1616
1617     } while ( ras.arc >= ras.arcs );
1618
1619     ras.lastX = x3;
1620     ras.lastY = y3;
1621
1622     return SUCCESS;
1623
1624   Fail:
1625     return FAILURE;
1626   }
1627
1628
1629   /*************************************************************************/
1630   /*                                                                       */
1631   /* <Function>                                                            */
1632   /*    Cubic_To                                                           */
1633   /*                                                                       */
1634   /* <Description>                                                         */
1635   /*    Inject a new cubic arc and adjust the profile list.                */
1636   /*                                                                       */
1637   /* <Input>                                                               */
1638   /*   cx1 :: The x-coordinate of the arc's first new control point.       */
1639   /*                                                                       */
1640   /*   cy1 :: The y-coordinate of the arc's first new control point.       */
1641   /*                                                                       */
1642   /*   cx2 :: The x-coordinate of the arc's second new control point.      */
1643   /*                                                                       */
1644   /*   cy2 :: The y-coordinate of the arc's second new control point.      */
1645   /*                                                                       */
1646   /*   x   :: The x-coordinate of the arc's end point (its start point is  */
1647   /*          stored in `lastX').                                          */
1648   /*                                                                       */
1649   /*   y   :: The y-coordinate of the arc's end point (its start point is  */
1650   /*          stored in `lastY').                                          */
1651   /*                                                                       */
1652   /* <Return>                                                              */
1653   /*   SUCCESS on success, FAILURE on render pool overflow or incorrect    */
1654   /*   profile.                                                            */
1655   /*                                                                       */
1656   static Bool
1657   Cubic_To( RAS_ARGS Long  cx1,
1658                      Long  cy1,
1659                      Long  cx2,
1660                      Long  cy2,
1661                      Long  x,
1662                      Long  y )
1663   {
1664     Long     y1, y2, y3, y4, x4, ymin1, ymax1, ymin2, ymax2;
1665     TStates  state_bez;
1666
1667
1668     ras.arc      = ras.arcs;
1669     ras.arc[3].x = ras.lastX;
1670     ras.arc[3].y = ras.lastY;
1671     ras.arc[2].x = cx1;
1672     ras.arc[2].y = cy1;
1673     ras.arc[1].x = cx2;
1674     ras.arc[1].y = cy2;
1675     ras.arc[0].x = x;
1676     ras.arc[0].y = y;
1677
1678     do
1679     {
1680       y1 = ras.arc[3].y;
1681       y2 = ras.arc[2].y;
1682       y3 = ras.arc[1].y;
1683       y4 = ras.arc[0].y;
1684       x4 = ras.arc[0].x;
1685
1686       /* first, categorize the Bezier arc */
1687
1688       if ( y1 <= y4 )
1689       {
1690         ymin1 = y1;
1691         ymax1 = y4;
1692       }
1693       else
1694       {
1695         ymin1 = y4;
1696         ymax1 = y1;
1697       }
1698
1699       if ( y2 <= y3 )
1700       {
1701         ymin2 = y2;
1702         ymax2 = y3;
1703       }
1704       else
1705       {
1706         ymin2 = y3;
1707         ymax2 = y2;
1708       }
1709
1710       if ( ymin2 < ymin1 || ymax2 > ymax1 )
1711       {
1712         /* this arc has no given direction, split it! */
1713         Split_Cubic( ras.arc );
1714         ras.arc += 3;
1715       }
1716       else if ( y1 == y4 )
1717       {
1718         /* this arc is flat, ignore it and pop it from the Bezier stack */
1719         ras.arc -= 3;
1720       }
1721       else
1722       {
1723         state_bez = ( y1 <= y4 ) ? Ascending_State : Descending_State;
1724
1725         /* detect a change of direction */
1726         if ( ras.state != state_bez )
1727         {
1728           Bool  o = state_bez == Ascending_State ? IS_BOTTOM_OVERSHOOT( y1 )
1729                                                  : IS_TOP_OVERSHOOT( y1 );
1730
1731
1732           /* finalize current profile if any */
1733           if ( ras.state != Unknown_State &&
1734                End_Profile( RAS_VARS o )  )
1735             goto Fail;
1736
1737           if ( New_Profile( RAS_VARS state_bez, o ) )
1738             goto Fail;
1739         }
1740
1741         /* compute intersections */
1742         if ( state_bez == Ascending_State )
1743         {
1744           if ( Bezier_Up( RAS_VARS 3, Split_Cubic, ras.minY, ras.maxY ) )
1745             goto Fail;
1746         }
1747         else
1748           if ( Bezier_Down( RAS_VARS 3, Split_Cubic, ras.minY, ras.maxY ) )
1749             goto Fail;
1750       }
1751
1752     } while ( ras.arc >= ras.arcs );
1753
1754     ras.lastX = x4;
1755     ras.lastY = y4;
1756
1757     return SUCCESS;
1758
1759   Fail:
1760     return FAILURE;
1761   }
1762
1763
1764 #undef  SWAP_
1765 #define SWAP_( x, y )  do                \
1766                        {                 \
1767                          Long  swap = x; \
1768                                          \
1769                                          \
1770                          x = y;          \
1771                          y = swap;       \
1772                        } while ( 0 )
1773
1774
1775   /*************************************************************************/
1776   /*                                                                       */
1777   /* <Function>                                                            */
1778   /*    Decompose_Curve                                                    */
1779   /*                                                                       */
1780   /* <Description>                                                         */
1781   /*    Scan the outline arrays in order to emit individual segments and   */
1782   /*    Beziers by calling Line_To() and Bezier_To().  It handles all      */
1783   /*    weird cases, like when the first point is off the curve, or when   */
1784   /*    there are simply no `on' points in the contour!                    */
1785   /*                                                                       */
1786   /* <Input>                                                               */
1787   /*    first   :: The index of the first point in the contour.            */
1788   /*                                                                       */
1789   /*    last    :: The index of the last point in the contour.             */
1790   /*                                                                       */
1791   /*    flipped :: If set, flip the direction of the curve.                */
1792   /*                                                                       */
1793   /* <Return>                                                              */
1794   /*    SUCCESS on success, FAILURE on error.                              */
1795   /*                                                                       */
1796   static Bool
1797   Decompose_Curve( RAS_ARGS UShort  first,
1798                             UShort  last,
1799                             int     flipped )
1800   {
1801     FT_Vector   v_last;
1802     FT_Vector   v_control;
1803     FT_Vector   v_start;
1804
1805     FT_Vector*  points;
1806     FT_Vector*  point;
1807     FT_Vector*  limit;
1808     char*       tags;
1809
1810     unsigned    tag;       /* current point's state           */
1811
1812
1813     points = ras.outline.points;
1814     limit  = points + last;
1815
1816     v_start.x = SCALED( points[first].x );
1817     v_start.y = SCALED( points[first].y );
1818     v_last.x  = SCALED( points[last].x );
1819     v_last.y  = SCALED( points[last].y );
1820
1821     if ( flipped )
1822     {
1823       SWAP_( v_start.x, v_start.y );
1824       SWAP_( v_last.x, v_last.y );
1825     }
1826
1827     v_control = v_start;
1828
1829     point = points + first;
1830     tags  = ras.outline.tags + first;
1831
1832     /* set scan mode if necessary */
1833     if ( tags[0] & FT_CURVE_TAG_HAS_SCANMODE )
1834       ras.dropOutControl = (Byte)tags[0] >> 5;
1835
1836     tag = FT_CURVE_TAG( tags[0] );
1837
1838     /* A contour cannot start with a cubic control point! */
1839     if ( tag == FT_CURVE_TAG_CUBIC )
1840       goto Invalid_Outline;
1841
1842     /* check first point to determine origin */
1843     if ( tag == FT_CURVE_TAG_CONIC )
1844     {
1845       /* first point is conic control.  Yes, this happens. */
1846       if ( FT_CURVE_TAG( ras.outline.tags[last] ) == FT_CURVE_TAG_ON )
1847       {
1848         /* start at last point if it is on the curve */
1849         v_start = v_last;
1850         limit--;
1851       }
1852       else
1853       {
1854         /* if both first and last points are conic,         */
1855         /* start at their middle and record its position    */
1856         /* for closure                                      */
1857         v_start.x = ( v_start.x + v_last.x ) / 2;
1858         v_start.y = ( v_start.y + v_last.y ) / 2;
1859
1860         v_last = v_start;
1861       }
1862       point--;
1863       tags--;
1864     }
1865
1866     ras.lastX = v_start.x;
1867     ras.lastY = v_start.y;
1868
1869     while ( point < limit )
1870     {
1871       point++;
1872       tags++;
1873
1874       tag = FT_CURVE_TAG( tags[0] );
1875
1876       switch ( tag )
1877       {
1878       case FT_CURVE_TAG_ON:  /* emit a single line_to */
1879         {
1880           Long  x, y;
1881
1882
1883           x = SCALED( point->x );
1884           y = SCALED( point->y );
1885           if ( flipped )
1886             SWAP_( x, y );
1887
1888           if ( Line_To( RAS_VARS x, y ) )
1889             goto Fail;
1890           continue;
1891         }
1892
1893       case FT_CURVE_TAG_CONIC:  /* consume conic arcs */
1894         v_control.x = SCALED( point[0].x );
1895         v_control.y = SCALED( point[0].y );
1896
1897         if ( flipped )
1898           SWAP_( v_control.x, v_control.y );
1899
1900       Do_Conic:
1901         if ( point < limit )
1902         {
1903           FT_Vector  v_middle;
1904           Long       x, y;
1905
1906
1907           point++;
1908           tags++;
1909           tag = FT_CURVE_TAG( tags[0] );
1910
1911           x = SCALED( point[0].x );
1912           y = SCALED( point[0].y );
1913
1914           if ( flipped )
1915             SWAP_( x, y );
1916
1917           if ( tag == FT_CURVE_TAG_ON )
1918           {
1919             if ( Conic_To( RAS_VARS v_control.x, v_control.y, x, y ) )
1920               goto Fail;
1921             continue;
1922           }
1923
1924           if ( tag != FT_CURVE_TAG_CONIC )
1925             goto Invalid_Outline;
1926
1927           v_middle.x = ( v_control.x + x ) / 2;
1928           v_middle.y = ( v_control.y + y ) / 2;
1929
1930           if ( Conic_To( RAS_VARS v_control.x, v_control.y,
1931                                   v_middle.x,  v_middle.y ) )
1932             goto Fail;
1933
1934           v_control.x = x;
1935           v_control.y = y;
1936
1937           goto Do_Conic;
1938         }
1939
1940         if ( Conic_To( RAS_VARS v_control.x, v_control.y,
1941                                 v_start.x,   v_start.y ) )
1942           goto Fail;
1943
1944         goto Close;
1945
1946       default:  /* FT_CURVE_TAG_CUBIC */
1947         {
1948           Long  x1, y1, x2, y2, x3, y3;
1949
1950
1951           if ( point + 1 > limit                             ||
1952                FT_CURVE_TAG( tags[1] ) != FT_CURVE_TAG_CUBIC )
1953             goto Invalid_Outline;
1954
1955           point += 2;
1956           tags  += 2;
1957
1958           x1 = SCALED( point[-2].x );
1959           y1 = SCALED( point[-2].y );
1960           x2 = SCALED( point[-1].x );
1961           y2 = SCALED( point[-1].y );
1962
1963           if ( flipped )
1964           {
1965             SWAP_( x1, y1 );
1966             SWAP_( x2, y2 );
1967           }
1968
1969           if ( point <= limit )
1970           {
1971             x3 = SCALED( point[0].x );
1972             y3 = SCALED( point[0].y );
1973
1974             if ( flipped )
1975               SWAP_( x3, y3 );
1976
1977             if ( Cubic_To( RAS_VARS x1, y1, x2, y2, x3, y3 ) )
1978               goto Fail;
1979             continue;
1980           }
1981
1982           if ( Cubic_To( RAS_VARS x1, y1, x2, y2, v_start.x, v_start.y ) )
1983             goto Fail;
1984           goto Close;
1985         }
1986       }
1987     }
1988
1989     /* close the contour with a line segment */
1990     if ( Line_To( RAS_VARS v_start.x, v_start.y ) )
1991       goto Fail;
1992
1993   Close:
1994     return SUCCESS;
1995
1996   Invalid_Outline:
1997     ras.error = Raster_Err_Invalid;
1998
1999   Fail:
2000     return FAILURE;
2001   }
2002
2003
2004   /*************************************************************************/
2005   /*                                                                       */
2006   /* <Function>                                                            */
2007   /*    Convert_Glyph                                                      */
2008   /*                                                                       */
2009   /* <Description>                                                         */
2010   /*    Convert a glyph into a series of segments and arcs and make a      */
2011   /*    profiles list with them.                                           */
2012   /*                                                                       */
2013   /* <Input>                                                               */
2014   /*    flipped :: If set, flip the direction of curve.                    */
2015   /*                                                                       */
2016   /* <Return>                                                              */
2017   /*    SUCCESS on success, FAILURE if any error was encountered during    */
2018   /*    rendering.                                                         */
2019   /*                                                                       */
2020   static Bool
2021   Convert_Glyph( RAS_ARGS int  flipped )
2022   {
2023     int       i;
2024     unsigned  start;
2025
2026     PProfile  lastProfile;
2027
2028
2029     ras.fProfile = NULL;
2030     ras.joint    = FALSE;
2031     ras.fresh    = FALSE;
2032
2033     ras.maxBuff  = ras.sizeBuff - AlignProfileSize;
2034
2035     ras.numTurns = 0;
2036
2037     ras.cProfile         = (PProfile)ras.top;
2038     ras.cProfile->offset = ras.top;
2039     ras.num_Profs        = 0;
2040
2041     start = 0;
2042
2043     for ( i = 0; i < ras.outline.n_contours; i++ )
2044     {
2045       Bool  o;
2046
2047
2048       ras.state    = Unknown_State;
2049       ras.gProfile = NULL;
2050
2051       if ( Decompose_Curve( RAS_VARS (unsigned short)start,
2052                                      ras.outline.contours[i],
2053                                      flipped ) )
2054         return FAILURE;
2055
2056       start = ras.outline.contours[i] + 1;
2057
2058       /* we must now check whether the extreme arcs join or not */
2059       if ( FRAC( ras.lastY ) == 0 &&
2060            ras.lastY >= ras.minY  &&
2061            ras.lastY <= ras.maxY  )
2062         if ( ras.gProfile                        &&
2063              ( ras.gProfile->flags & Flow_Up ) ==
2064                ( ras.cProfile->flags & Flow_Up ) )
2065           ras.top--;
2066         /* Note that ras.gProfile can be nil if the contour was too small */
2067         /* to be drawn.                                                   */
2068
2069       lastProfile = ras.cProfile;
2070       if ( ras.cProfile->flags & Flow_Up )
2071         o = IS_TOP_OVERSHOOT( ras.lastY );
2072       else
2073         o = IS_BOTTOM_OVERSHOOT( ras.lastY );
2074       if ( End_Profile( RAS_VARS o ) )
2075         return FAILURE;
2076
2077       /* close the `next profile in contour' linked list */
2078       if ( ras.gProfile )
2079         lastProfile->next = ras.gProfile;
2080     }
2081
2082     if ( Finalize_Profile_Table( RAS_VAR ) )
2083       return FAILURE;
2084
2085     return (Bool)( ras.top < ras.maxBuff ? SUCCESS : FAILURE );
2086   }
2087
2088
2089   /*************************************************************************/
2090   /*************************************************************************/
2091   /**                                                                     **/
2092   /**  SCAN-LINE SWEEPS AND DRAWING                                       **/
2093   /**                                                                     **/
2094   /*************************************************************************/
2095   /*************************************************************************/
2096
2097
2098   /*************************************************************************/
2099   /*                                                                       */
2100   /*  Init_Linked                                                          */
2101   /*                                                                       */
2102   /*    Initializes an empty linked list.                                  */
2103   /*                                                                       */
2104   static void
2105   Init_Linked( TProfileList*  l )
2106   {
2107     *l = NULL;
2108   }
2109
2110
2111   /*************************************************************************/
2112   /*                                                                       */
2113   /*  InsNew                                                               */
2114   /*                                                                       */
2115   /*    Inserts a new profile in a linked list.                            */
2116   /*                                                                       */
2117   static void
2118   InsNew( PProfileList  list,
2119           PProfile      profile )
2120   {
2121     PProfile  *old, current;
2122     Long       x;
2123
2124
2125     old     = list;
2126     current = *old;
2127     x       = profile->X;
2128
2129     while ( current )
2130     {
2131       if ( x < current->X )
2132         break;
2133       old     = &current->link;
2134       current = *old;
2135     }
2136
2137     profile->link = current;
2138     *old          = profile;
2139   }
2140
2141
2142   /*************************************************************************/
2143   /*                                                                       */
2144   /*  DelOld                                                               */
2145   /*                                                                       */
2146   /*    Removes an old profile from a linked list.                         */
2147   /*                                                                       */
2148   static void
2149   DelOld( PProfileList  list,
2150           PProfile      profile )
2151   {
2152     PProfile  *old, current;
2153
2154
2155     old     = list;
2156     current = *old;
2157
2158     while ( current )
2159     {
2160       if ( current == profile )
2161       {
2162         *old = current->link;
2163         return;
2164       }
2165
2166       old     = &current->link;
2167       current = *old;
2168     }
2169
2170     /* we should never get there, unless the profile was not part of */
2171     /* the list.                                                     */
2172   }
2173
2174
2175   /*************************************************************************/
2176   /*                                                                       */
2177   /*  Sort                                                                 */
2178   /*                                                                       */
2179   /*    Sorts a trace list.  In 95%, the list is already sorted.  We need  */
2180   /*    an algorithm which is fast in this case.  Bubble sort is enough    */
2181   /*    and simple.                                                        */
2182   /*                                                                       */
2183   static void
2184   Sort( PProfileList  list )
2185   {
2186     PProfile  *old, current, next;
2187
2188
2189     /* First, set the new X coordinate of each profile */
2190     current = *list;
2191     while ( current )
2192     {
2193       current->X       = *current->offset;
2194       current->offset += current->flags & Flow_Up ? 1 : -1;
2195       current->height--;
2196       current = current->link;
2197     }
2198
2199     /* Then sort them */
2200     old     = list;
2201     current = *old;
2202
2203     if ( !current )
2204       return;
2205
2206     next = current->link;
2207
2208     while ( next )
2209     {
2210       if ( current->X <= next->X )
2211       {
2212         old     = &current->link;
2213         current = *old;
2214
2215         if ( !current )
2216           return;
2217       }
2218       else
2219       {
2220         *old          = next;
2221         current->link = next->link;
2222         next->link    = current;
2223
2224         old     = list;
2225         current = *old;
2226       }
2227
2228       next = current->link;
2229     }
2230   }
2231
2232
2233   /*************************************************************************/
2234   /*                                                                       */
2235   /*  Vertical Sweep Procedure Set                                         */
2236   /*                                                                       */
2237   /*  These four routines are used during the vertical black/white sweep   */
2238   /*  phase by the generic Draw_Sweep() function.                          */
2239   /*                                                                       */
2240   /*************************************************************************/
2241
2242   static void
2243   Vertical_Sweep_Init( RAS_ARGS Short*  min,
2244                                 Short*  max )
2245   {
2246     Long  pitch = ras.target.pitch;
2247
2248     FT_UNUSED( max );
2249
2250
2251     ras.traceIncr = (Short)-pitch;
2252     ras.traceOfs  = -*min * pitch;
2253     if ( pitch > 0 )
2254       ras.traceOfs += ( ras.target.rows - 1 ) * pitch;
2255
2256     ras.gray_min_x = 0;
2257     ras.gray_max_x = 0;
2258   }
2259
2260
2261   static void
2262   Vertical_Sweep_Span( RAS_ARGS Short       y,
2263                                 FT_F26Dot6  x1,
2264                                 FT_F26Dot6  x2,
2265                                 PProfile    left,
2266                                 PProfile    right )
2267   {
2268     Long   e1, e2;
2269     int    c1, c2;
2270     Byte   f1, f2;
2271     Byte*  target;
2272
2273     FT_UNUSED( y );
2274     FT_UNUSED( left );
2275     FT_UNUSED( right );
2276
2277
2278     /* Drop-out control */
2279
2280     e1 = TRUNC( CEILING( x1 ) );
2281
2282     if ( x2 - x1 - ras.precision <= ras.precision_jitter )
2283       e2 = e1;
2284     else
2285       e2 = TRUNC( FLOOR( x2 ) );
2286
2287     if ( e2 >= 0 && e1 < ras.bWidth )
2288     {
2289       if ( e1 < 0 )
2290         e1 = 0;
2291       if ( e2 >= ras.bWidth )
2292         e2 = ras.bWidth - 1;
2293
2294       c1 = (Short)( e1 >> 3 );
2295       c2 = (Short)( e2 >> 3 );
2296
2297       f1 = (Byte)  ( 0xFF >> ( e1 & 7 ) );
2298       f2 = (Byte) ~( 0x7F >> ( e2 & 7 ) );
2299
2300       if ( ras.gray_min_x > c1 )
2301         ras.gray_min_x = (short)c1;
2302       if ( ras.gray_max_x < c2 )
2303         ras.gray_max_x = (short)c2;
2304
2305       target = ras.bTarget + ras.traceOfs + c1;
2306       c2 -= c1;
2307
2308       if ( c2 > 0 )
2309       {
2310         target[0] |= f1;
2311
2312         /* memset() is slower than the following code on many platforms. */
2313         /* This is due to the fact that, in the vast majority of cases,  */
2314         /* the span length in bytes is relatively small.                 */
2315         c2--;
2316         while ( c2 > 0 )
2317         {
2318           *(++target) = 0xFF;
2319           c2--;
2320         }
2321         target[1] |= f2;
2322       }
2323       else
2324         *target |= ( f1 & f2 );
2325     }
2326   }
2327
2328
2329   static void
2330   Vertical_Sweep_Drop( RAS_ARGS Short       y,
2331                                 FT_F26Dot6  x1,
2332                                 FT_F26Dot6  x2,
2333                                 PProfile    left,
2334                                 PProfile    right )
2335   {
2336     Long   e1, e2, pxl;
2337     Short  c1, f1;
2338
2339
2340     /* Drop-out control */
2341
2342     /*   e2            x2                    x1           e1   */
2343     /*                                                         */
2344     /*                 ^                     |                 */
2345     /*                 |                     |                 */
2346     /*   +-------------+---------------------+------------+    */
2347     /*                 |                     |                 */
2348     /*                 |                     v                 */
2349     /*                                                         */
2350     /* pixel         contour              contour       pixel  */
2351     /* center                                           center */
2352
2353     /* drop-out mode    scan conversion rules (as defined in OpenType) */
2354     /* --------------------------------------------------------------- */
2355     /*  0                1, 2, 3                                       */
2356     /*  1                1, 2, 4                                       */
2357     /*  2                1, 2                                          */
2358     /*  3                same as mode 2                                */
2359     /*  4                1, 2, 5                                       */
2360     /*  5                1, 2, 6                                       */
2361     /*  6, 7             same as mode 2                                */
2362
2363     e1  = CEILING( x1 );
2364     e2  = FLOOR  ( x2 );
2365     pxl = e1;
2366
2367     if ( e1 > e2 )
2368     {
2369       Int  dropOutControl = left->flags & 7;
2370
2371
2372       if ( e1 == e2 + ras.precision )
2373       {
2374         switch ( dropOutControl )
2375         {
2376         case 0: /* simple drop-outs including stubs */
2377           pxl = e2;
2378           break;
2379
2380         case 4: /* smart drop-outs including stubs */
2381           pxl = FLOOR( ( x1 + x2 - 1 ) / 2 + ras.precision_half );
2382           break;
2383
2384         case 1: /* simple drop-outs excluding stubs */
2385         case 5: /* smart drop-outs excluding stubs  */
2386
2387           /* Drop-out Control Rules #4 and #6 */
2388
2389           /* The specification neither provides an exact definition */
2390           /* of a `stub' nor gives exact rules to exclude them.     */
2391           /*                                                        */
2392           /* Here the constraints we use to recognize a stub.       */
2393           /*                                                        */
2394           /*  upper stub:                                           */
2395           /*                                                        */
2396           /*   - P_Left and P_Right are in the same contour         */
2397           /*   - P_Right is the successor of P_Left in that contour */
2398           /*   - y is the top of P_Left and P_Right                 */
2399           /*                                                        */
2400           /*  lower stub:                                           */
2401           /*                                                        */
2402           /*   - P_Left and P_Right are in the same contour         */
2403           /*   - P_Left is the successor of P_Right in that contour */
2404           /*   - y is the bottom of P_Left                          */
2405           /*                                                        */
2406           /* We draw a stub if the following constraints are met.   */
2407           /*                                                        */
2408           /*   - for an upper or lower stub, there is top or bottom */
2409           /*     overshoot, respectively                            */
2410           /*   - the covered interval is greater or equal to a half */
2411           /*     pixel                                              */
2412
2413           /* upper stub test */
2414           if ( left->next == right                &&
2415                left->height <= 0                  &&
2416                !( left->flags & Overshoot_Top   &&
2417                   x2 - x1 >= ras.precision_half ) )
2418             return;
2419
2420           /* lower stub test */
2421           if ( right->next == left                 &&
2422                left->start == y                    &&
2423                !( left->flags & Overshoot_Bottom &&
2424                   x2 - x1 >= ras.precision_half  ) )
2425             return;
2426
2427           if ( dropOutControl == 1 )
2428             pxl = e2;
2429           else
2430             pxl = FLOOR( ( x1 + x2 - 1 ) / 2 + ras.precision_half );
2431           break;
2432
2433         default: /* modes 2, 3, 6, 7 */
2434           return;  /* no drop-out control */
2435         }
2436
2437         /* undocumented but confirmed: If the drop-out would result in a  */
2438         /* pixel outside of the bounding box, use the pixel inside of the */
2439         /* bounding box instead                                           */
2440         if ( pxl < 0 )
2441           pxl = e1;
2442         else if ( TRUNC( pxl ) >= ras.bWidth )
2443           pxl = e2;
2444
2445         /* check that the other pixel isn't set */
2446         e1 = pxl == e1 ? e2 : e1;
2447
2448         e1 = TRUNC( e1 );
2449
2450         c1 = (Short)( e1 >> 3 );
2451         f1 = (Short)( e1 &  7 );
2452
2453         if ( e1 >= 0 && e1 < ras.bWidth                      &&
2454              ras.bTarget[ras.traceOfs + c1] & ( 0x80 >> f1 ) )
2455           return;
2456       }
2457       else
2458         return;
2459     }
2460
2461     e1 = TRUNC( pxl );
2462
2463     if ( e1 >= 0 && e1 < ras.bWidth )
2464     {
2465       c1 = (Short)( e1 >> 3 );
2466       f1 = (Short)( e1 & 7 );
2467
2468       if ( ras.gray_min_x > c1 )
2469         ras.gray_min_x = c1;
2470       if ( ras.gray_max_x < c1 )
2471         ras.gray_max_x = c1;
2472
2473       ras.bTarget[ras.traceOfs + c1] |= (char)( 0x80 >> f1 );
2474     }
2475   }
2476
2477
2478   static void
2479   Vertical_Sweep_Step( RAS_ARG )
2480   {
2481     ras.traceOfs += ras.traceIncr;
2482   }
2483
2484
2485   /***********************************************************************/
2486   /*                                                                     */
2487   /*  Horizontal Sweep Procedure Set                                     */
2488   /*                                                                     */
2489   /*  These four routines are used during the horizontal black/white     */
2490   /*  sweep phase by the generic Draw_Sweep() function.                  */
2491   /*                                                                     */
2492   /***********************************************************************/
2493
2494   static void
2495   Horizontal_Sweep_Init( RAS_ARGS Short*  min,
2496                                   Short*  max )
2497   {
2498     /* nothing, really */
2499     FT_UNUSED_RASTER;
2500     FT_UNUSED( min );
2501     FT_UNUSED( max );
2502   }
2503
2504
2505   static void
2506   Horizontal_Sweep_Span( RAS_ARGS Short       y,
2507                                   FT_F26Dot6  x1,
2508                                   FT_F26Dot6  x2,
2509                                   PProfile    left,
2510                                   PProfile    right )
2511   {
2512     Long   e1, e2;
2513     PByte  bits;
2514     Byte   f1;
2515
2516     FT_UNUSED( left );
2517     FT_UNUSED( right );
2518
2519
2520     if ( x2 - x1 < ras.precision )
2521     {
2522       e1 = CEILING( x1 );
2523       e2 = FLOOR  ( x2 );
2524
2525       if ( e1 == e2 )
2526       {
2527         bits = ras.bTarget + ( y >> 3 );
2528         f1   = (Byte)( 0x80 >> ( y & 7 ) );
2529
2530         e1 = TRUNC( e1 );
2531
2532         if ( e1 >= 0 && e1 < ras.target.rows )
2533         {
2534           PByte  p;
2535
2536
2537           p = bits - e1 * ras.target.pitch;
2538           if ( ras.target.pitch > 0 )
2539             p += ( ras.target.rows - 1 ) * ras.target.pitch;
2540
2541           p[0] |= f1;
2542         }
2543       }
2544     }
2545   }
2546
2547
2548   static void
2549   Horizontal_Sweep_Drop( RAS_ARGS Short       y,
2550                                   FT_F26Dot6  x1,
2551                                   FT_F26Dot6  x2,
2552                                   PProfile    left,
2553                                   PProfile    right )
2554   {
2555     Long   e1, e2, pxl;
2556     PByte  bits;
2557     Byte   f1;
2558
2559
2560     /* During the horizontal sweep, we only take care of drop-outs */
2561
2562     /* e1     +       <-- pixel center */
2563     /*        |                        */
2564     /* x1  ---+-->    <-- contour      */
2565     /*        |                        */
2566     /*        |                        */
2567     /* x2  <--+---    <-- contour      */
2568     /*        |                        */
2569     /*        |                        */
2570     /* e2     +       <-- pixel center */
2571
2572     e1  = CEILING( x1 );
2573     e2  = FLOOR  ( x2 );
2574     pxl = e1;
2575
2576     if ( e1 > e2 )
2577     {
2578       Int  dropOutControl = left->flags & 7;
2579
2580
2581       if ( e1 == e2 + ras.precision )
2582       {
2583         switch ( dropOutControl )
2584         {
2585         case 0: /* simple drop-outs including stubs */
2586           pxl = e2;
2587           break;
2588
2589         case 4: /* smart drop-outs including stubs */
2590           pxl = FLOOR( ( x1 + x2 - 1 ) / 2 + ras.precision_half );
2591           break;
2592
2593         case 1: /* simple drop-outs excluding stubs */
2594         case 5: /* smart drop-outs excluding stubs  */
2595           /* see Vertical_Sweep_Drop for details */
2596
2597           /* rightmost stub test */
2598           if ( left->next == right                &&
2599                left->height <= 0                  &&
2600                !( left->flags & Overshoot_Top   &&
2601                   x2 - x1 >= ras.precision_half ) )
2602             return;
2603
2604           /* leftmost stub test */
2605           if ( right->next == left                 &&
2606                left->start == y                    &&
2607                !( left->flags & Overshoot_Bottom &&
2608                   x2 - x1 >= ras.precision_half  ) )
2609             return;
2610
2611           if ( dropOutControl == 1 )
2612             pxl = e2;
2613           else
2614             pxl = FLOOR( ( x1 + x2 - 1 ) / 2 + ras.precision_half );
2615           break;
2616
2617         default: /* modes 2, 3, 6, 7 */
2618           return;  /* no drop-out control */
2619         }
2620
2621         /* undocumented but confirmed: If the drop-out would result in a  */
2622         /* pixel outside of the bounding box, use the pixel inside of the */
2623         /* bounding box instead                                           */
2624         if ( pxl < 0 )
2625           pxl = e1;
2626         else if ( TRUNC( pxl ) >= ras.target.rows )
2627           pxl = e2;
2628
2629         /* check that the other pixel isn't set */
2630         e1 = pxl == e1 ? e2 : e1;
2631
2632         e1 = TRUNC( e1 );
2633
2634         bits = ras.bTarget + ( y >> 3 );
2635         f1   = (Byte)( 0x80 >> ( y & 7 ) );
2636
2637         bits -= e1 * ras.target.pitch;
2638         if ( ras.target.pitch > 0 )
2639           bits += ( ras.target.rows - 1 ) * ras.target.pitch;
2640
2641         if ( e1 >= 0              &&
2642              e1 < ras.target.rows &&
2643              *bits & f1           )
2644           return;
2645       }
2646       else
2647         return;
2648     }
2649
2650     bits = ras.bTarget + ( y >> 3 );
2651     f1   = (Byte)( 0x80 >> ( y & 7 ) );
2652
2653     e1 = TRUNC( pxl );
2654
2655     if ( e1 >= 0 && e1 < ras.target.rows )
2656     {
2657       bits -= e1 * ras.target.pitch;
2658       if ( ras.target.pitch > 0 )
2659         bits += ( ras.target.rows - 1 ) * ras.target.pitch;
2660
2661       bits[0] |= f1;
2662     }
2663   }
2664
2665
2666   static void
2667   Horizontal_Sweep_Step( RAS_ARG )
2668   {
2669     /* Nothing, really */
2670     FT_UNUSED_RASTER;
2671   }
2672
2673
2674 #ifdef FT_RASTER_OPTION_ANTI_ALIASING
2675
2676
2677   /*************************************************************************/
2678   /*                                                                       */
2679   /*  Vertical Gray Sweep Procedure Set                                    */
2680   /*                                                                       */
2681   /*  These two routines are used during the vertical gray-levels sweep    */
2682   /*  phase by the generic Draw_Sweep() function.                          */
2683   /*                                                                       */
2684   /*  NOTES                                                                */
2685   /*                                                                       */
2686   /*  - The target pixmap's width *must* be a multiple of 4.               */
2687   /*                                                                       */
2688   /*  - You have to use the function Vertical_Sweep_Span() for the gray    */
2689   /*    span call.                                                         */
2690   /*                                                                       */
2691   /*************************************************************************/
2692
2693   static void
2694   Vertical_Gray_Sweep_Init( RAS_ARGS Short*  min,
2695                                      Short*  max )
2696   {
2697     Long  pitch, byte_len;
2698
2699
2700     *min = *min & -2;
2701     *max = ( *max + 3 ) & -2;
2702
2703     ras.traceOfs  = 0;
2704     pitch         = ras.target.pitch;
2705     byte_len      = -pitch;
2706     ras.traceIncr = (Short)byte_len;
2707     ras.traceG    = ( *min / 2 ) * byte_len;
2708
2709     if ( pitch > 0 )
2710     {
2711       ras.traceG += ( ras.target.rows - 1 ) * pitch;
2712       byte_len    = -byte_len;
2713     }
2714
2715     ras.gray_min_x =  (Short)byte_len;
2716     ras.gray_max_x = -(Short)byte_len;
2717   }
2718
2719
2720   static void
2721   Vertical_Gray_Sweep_Step( RAS_ARG )
2722   {
2723     Int     c1, c2;
2724     PByte   pix, bit, bit2;
2725     short*  count = (short*)count_table;
2726     Byte*   grays;
2727
2728
2729     ras.traceOfs += ras.gray_width;
2730
2731     if ( ras.traceOfs > ras.gray_width )
2732     {
2733       pix   = ras.gTarget + ras.traceG + ras.gray_min_x * 4;
2734       grays = ras.grays;
2735
2736       if ( ras.gray_max_x >= 0 )
2737       {
2738         Long  last_pixel = ras.target.width - 1;
2739         Int   last_cell  = last_pixel >> 2;
2740         Int   last_bit   = last_pixel & 3;
2741         Bool  over       = 0;
2742
2743
2744         if ( ras.gray_max_x >= last_cell && last_bit != 3 )
2745         {
2746           ras.gray_max_x = last_cell - 1;
2747           over = 1;
2748         }
2749
2750         if ( ras.gray_min_x < 0 )
2751           ras.gray_min_x = 0;
2752
2753         bit  = ras.bTarget + ras.gray_min_x;
2754         bit2 = bit + ras.gray_width;
2755
2756         c1 = ras.gray_max_x - ras.gray_min_x;
2757
2758         while ( c1 >= 0 )
2759         {
2760           c2 = count[*bit] + count[*bit2];
2761
2762           if ( c2 )
2763           {
2764             pix[0] = grays[(c2 >> 12) & 0x000F];
2765             pix[1] = grays[(c2 >> 8 ) & 0x000F];
2766             pix[2] = grays[(c2 >> 4 ) & 0x000F];
2767             pix[3] = grays[ c2        & 0x000F];
2768
2769             *bit  = 0;
2770             *bit2 = 0;
2771           }
2772
2773           bit++;
2774           bit2++;
2775           pix += 4;
2776           c1--;
2777         }
2778
2779         if ( over )
2780         {
2781           c2 = count[*bit] + count[*bit2];
2782           if ( c2 )
2783           {
2784             switch ( last_bit )
2785             {
2786             case 2:
2787               pix[2] = grays[(c2 >> 4 ) & 0x000F];
2788             case 1:
2789               pix[1] = grays[(c2 >> 8 ) & 0x000F];
2790             default:
2791               pix[0] = grays[(c2 >> 12) & 0x000F];
2792             }
2793
2794             *bit  = 0;
2795             *bit2 = 0;
2796           }
2797         }
2798       }
2799
2800       ras.traceOfs = 0;
2801       ras.traceG  += ras.traceIncr;
2802
2803       ras.gray_min_x =  32000;
2804       ras.gray_max_x = -32000;
2805     }
2806   }
2807
2808
2809   static void
2810   Horizontal_Gray_Sweep_Span( RAS_ARGS Short       y,
2811                                        FT_F26Dot6  x1,
2812                                        FT_F26Dot6  x2,
2813                                        PProfile    left,
2814                                        PProfile    right )
2815   {
2816     /* nothing, really */
2817     FT_UNUSED_RASTER;
2818     FT_UNUSED( y );
2819     FT_UNUSED( x1 );
2820     FT_UNUSED( x2 );
2821     FT_UNUSED( left );
2822     FT_UNUSED( right );
2823   }
2824
2825
2826   static void
2827   Horizontal_Gray_Sweep_Drop( RAS_ARGS Short       y,
2828                                        FT_F26Dot6  x1,
2829                                        FT_F26Dot6  x2,
2830                                        PProfile    left,
2831                                        PProfile    right )
2832   {
2833     Long   e1, e2;
2834     PByte  pixel;
2835     Byte   color;
2836
2837
2838     /* During the horizontal sweep, we only take care of drop-outs */
2839
2840     e1 = CEILING( x1 );
2841     e2 = FLOOR  ( x2 );
2842
2843     if ( e1 > e2 )
2844     {
2845       Int  dropOutControl = left->flags & 7;
2846
2847
2848       if ( e1 == e2 + ras.precision )
2849       {
2850         switch ( dropOutControl )
2851         {
2852         case 0: /* simple drop-outs including stubs */
2853           e1 = e2;
2854           break;
2855
2856         case 4: /* smart drop-outs including stubs */
2857           e1 = FLOOR( ( x1 + x2 - 1 ) / 2 + ras.precision_half );
2858           break;
2859
2860         case 1: /* simple drop-outs excluding stubs */
2861         case 5: /* smart drop-outs excluding stubs  */
2862           /* see Vertical_Sweep_Drop for details */
2863
2864           /* rightmost stub test */
2865           if ( left->next == right && left->height <= 0 )
2866             return;
2867
2868           /* leftmost stub test */
2869           if ( right->next == left && left->start == y )
2870             return;
2871
2872           if ( dropOutControl == 1 )
2873             e1 = e2;
2874           else
2875             e1 = FLOOR( ( x1 + x2 - 1 ) / 2 + ras.precision_half );
2876
2877           break;
2878
2879         default: /* modes 2, 3, 6, 7 */
2880           return;  /* no drop-out control */
2881         }
2882       }
2883       else
2884         return;
2885     }
2886
2887     if ( e1 >= 0 )
2888     {
2889       if ( x2 - x1 >= ras.precision_half )
2890         color = ras.grays[2];
2891       else
2892         color = ras.grays[1];
2893
2894       e1 = TRUNC( e1 ) / 2;
2895       if ( e1 < ras.target.rows )
2896       {
2897         pixel = ras.gTarget - e1 * ras.target.pitch + y / 2;
2898         if ( ras.target.pitch > 0 )
2899           pixel += ( ras.target.rows - 1 ) * ras.target.pitch;
2900
2901         if ( pixel[0] == ras.grays[0] )
2902           pixel[0] = color;
2903       }
2904     }
2905   }
2906
2907
2908 #endif /* FT_RASTER_OPTION_ANTI_ALIASING */
2909
2910
2911   /*************************************************************************/
2912   /*                                                                       */
2913   /*  Generic Sweep Drawing routine                                        */
2914   /*                                                                       */
2915   /*************************************************************************/
2916
2917   static Bool
2918   Draw_Sweep( RAS_ARG )
2919   {
2920     Short         y, y_change, y_height;
2921
2922     PProfile      P, Q, P_Left, P_Right;
2923
2924     Short         min_Y, max_Y, top, bottom, dropouts;
2925
2926     Long          x1, x2, xs, e1, e2;
2927
2928     TProfileList  waiting;
2929     TProfileList  draw_left, draw_right;
2930
2931
2932     /* initialize empty linked lists */
2933
2934     Init_Linked( &waiting );
2935
2936     Init_Linked( &draw_left  );
2937     Init_Linked( &draw_right );
2938
2939     /* first, compute min and max Y */
2940
2941     P     = ras.fProfile;
2942     max_Y = (Short)TRUNC( ras.minY );
2943     min_Y = (Short)TRUNC( ras.maxY );
2944
2945     while ( P )
2946     {
2947       Q = P->link;
2948
2949       bottom = (Short)P->start;
2950       top    = (Short)( P->start + P->height - 1 );
2951
2952       if ( min_Y > bottom )
2953         min_Y = bottom;
2954       if ( max_Y < top )
2955         max_Y = top;
2956
2957       P->X = 0;
2958       InsNew( &waiting, P );
2959
2960       P = Q;
2961     }
2962
2963     /* check the Y-turns */
2964     if ( ras.numTurns == 0 )
2965     {
2966       ras.error = Raster_Err_Invalid;
2967       return FAILURE;
2968     }
2969
2970     /* now initialize the sweep */
2971
2972     ras.Proc_Sweep_Init( RAS_VARS &min_Y, &max_Y );
2973
2974     /* then compute the distance of each profile from min_Y */
2975
2976     P = waiting;
2977
2978     while ( P )
2979     {
2980       P->countL = (UShort)( P->start - min_Y );
2981       P = P->link;
2982     }
2983
2984     /* let's go */
2985
2986     y        = min_Y;
2987     y_height = 0;
2988
2989     if ( ras.numTurns > 0                     &&
2990          ras.sizeBuff[-ras.numTurns] == min_Y )
2991       ras.numTurns--;
2992
2993     while ( ras.numTurns > 0 )
2994     {
2995       /* check waiting list for new activations */
2996
2997       P = waiting;
2998
2999       while ( P )
3000       {
3001         Q = P->link;
3002         P->countL -= y_height;
3003         if ( P->countL == 0 )
3004         {
3005           DelOld( &waiting, P );
3006
3007           if ( P->flags & Flow_Up )
3008             InsNew( &draw_left,  P );
3009           else
3010             InsNew( &draw_right, P );
3011         }
3012
3013         P = Q;
3014       }
3015
3016       /* sort the drawing lists */
3017
3018       Sort( &draw_left );
3019       Sort( &draw_right );
3020
3021       y_change = (Short)ras.sizeBuff[-ras.numTurns--];
3022       y_height = (Short)( y_change - y );
3023
3024       while ( y < y_change )
3025       {
3026         /* let's trace */
3027
3028         dropouts = 0;
3029
3030         P_Left  = draw_left;
3031         P_Right = draw_right;
3032
3033         while ( P_Left )
3034         {
3035           x1 = P_Left ->X;
3036           x2 = P_Right->X;
3037
3038           if ( x1 > x2 )
3039           {
3040             xs = x1;
3041             x1 = x2;
3042             x2 = xs;
3043           }
3044
3045           e1 = FLOOR( x1 );
3046           e2 = CEILING( x2 );
3047
3048           if ( x2 - x1 <= ras.precision &&
3049                e1 != x1 && e2 != x2     )
3050           {
3051             if ( e1 > e2 || e2 == e1 + ras.precision )
3052             {
3053               Int  dropOutControl = P_Left->flags & 7;
3054
3055
3056               if ( dropOutControl != 2 )
3057               {
3058                 /* a drop-out was detected */
3059
3060                 P_Left ->X = x1;
3061                 P_Right->X = x2;
3062
3063                 /* mark profile for drop-out processing */
3064                 P_Left->countL = 1;
3065                 dropouts++;
3066               }
3067
3068               goto Skip_To_Next;
3069             }
3070           }
3071
3072           ras.Proc_Sweep_Span( RAS_VARS y, x1, x2, P_Left, P_Right );
3073
3074         Skip_To_Next:
3075
3076           P_Left  = P_Left->link;
3077           P_Right = P_Right->link;
3078         }
3079
3080         /* handle drop-outs _after_ the span drawing --       */
3081         /* drop-out processing has been moved out of the loop */
3082         /* for performance tuning                             */
3083         if ( dropouts > 0 )
3084           goto Scan_DropOuts;
3085
3086       Next_Line:
3087
3088         ras.Proc_Sweep_Step( RAS_VAR );
3089
3090         y++;
3091
3092         if ( y < y_change )
3093         {
3094           Sort( &draw_left  );
3095           Sort( &draw_right );
3096         }
3097       }
3098
3099       /* now finalize the profiles that need it */
3100
3101       P = draw_left;
3102       while ( P )
3103       {
3104         Q = P->link;
3105         if ( P->height == 0 )
3106           DelOld( &draw_left, P );
3107         P = Q;
3108       }
3109
3110       P = draw_right;
3111       while ( P )
3112       {
3113         Q = P->link;
3114         if ( P->height == 0 )
3115           DelOld( &draw_right, P );
3116         P = Q;
3117       }
3118     }
3119
3120     /* for gray-scaling, flush the bitmap scanline cache */
3121     while ( y <= max_Y )
3122     {
3123       ras.Proc_Sweep_Step( RAS_VAR );
3124       y++;
3125     }
3126
3127     return SUCCESS;
3128
3129   Scan_DropOuts:
3130
3131     P_Left  = draw_left;
3132     P_Right = draw_right;
3133
3134     while ( P_Left )
3135     {
3136       if ( P_Left->countL )
3137       {
3138         P_Left->countL = 0;
3139 #if 0
3140         dropouts--;  /* -- this is useful when debugging only */
3141 #endif
3142         ras.Proc_Sweep_Drop( RAS_VARS y,
3143                                       P_Left->X,
3144                                       P_Right->X,
3145                                       P_Left,
3146                                       P_Right );
3147       }
3148
3149       P_Left  = P_Left->link;
3150       P_Right = P_Right->link;
3151     }
3152
3153     goto Next_Line;
3154   }
3155
3156
3157   /*************************************************************************/
3158   /*                                                                       */
3159   /* <Function>                                                            */
3160   /*    Render_Single_Pass                                                 */
3161   /*                                                                       */
3162   /* <Description>                                                         */
3163   /*    Perform one sweep with sub-banding.                                */
3164   /*                                                                       */
3165   /* <Input>                                                               */
3166   /*    flipped :: If set, flip the direction of the outline.              */
3167   /*                                                                       */
3168   /* <Return>                                                              */
3169   /*    Renderer error code.                                               */
3170   /*                                                                       */
3171   static int
3172   Render_Single_Pass( RAS_ARGS Bool  flipped )
3173   {
3174     Short  i, j, k;
3175
3176
3177     while ( ras.band_top >= 0 )
3178     {
3179       ras.maxY = (Long)ras.band_stack[ras.band_top].y_max * ras.precision;
3180       ras.minY = (Long)ras.band_stack[ras.band_top].y_min * ras.precision;
3181
3182       ras.top = ras.buff;
3183
3184       ras.error = Raster_Err_None;
3185
3186       if ( Convert_Glyph( RAS_VARS flipped ) )
3187       {
3188         if ( ras.error != Raster_Err_Overflow )
3189           return FAILURE;
3190
3191         ras.error = Raster_Err_None;
3192
3193         /* sub-banding */
3194
3195 #ifdef DEBUG_RASTER
3196         ClearBand( RAS_VARS TRUNC( ras.minY ), TRUNC( ras.maxY ) );
3197 #endif
3198
3199         i = ras.band_stack[ras.band_top].y_min;
3200         j = ras.band_stack[ras.band_top].y_max;
3201
3202         k = (Short)( ( i + j ) / 2 );
3203
3204         if ( ras.band_top >= 7 || k < i )
3205         {
3206           ras.band_top = 0;
3207           ras.error    = Raster_Err_Invalid;
3208
3209           return ras.error;
3210         }
3211
3212         ras.band_stack[ras.band_top + 1].y_min = k;
3213         ras.band_stack[ras.band_top + 1].y_max = j;
3214
3215         ras.band_stack[ras.band_top].y_max = (Short)( k - 1 );
3216
3217         ras.band_top++;
3218       }
3219       else
3220       {
3221         if ( ras.fProfile )
3222           if ( Draw_Sweep( RAS_VAR ) )
3223              return ras.error;
3224         ras.band_top--;
3225       }
3226     }
3227
3228     return SUCCESS;
3229   }
3230
3231
3232   /*************************************************************************/
3233   /*                                                                       */
3234   /* <Function>                                                            */
3235   /*    Render_Glyph                                                       */
3236   /*                                                                       */
3237   /* <Description>                                                         */
3238   /*    Render a glyph in a bitmap.  Sub-banding if needed.                */
3239   /*                                                                       */
3240   /* <Return>                                                              */
3241   /*    FreeType error code.  0 means success.                             */
3242   /*                                                                       */
3243   FT_LOCAL_DEF( FT_Error )
3244   Render_Glyph( RAS_ARG )
3245   {
3246     FT_Error  error;
3247
3248
3249     Set_High_Precision( RAS_VARS ras.outline.flags &
3250                                  FT_OUTLINE_HIGH_PRECISION );
3251     ras.scale_shift = ras.precision_shift;
3252
3253     if ( ras.outline.flags & FT_OUTLINE_IGNORE_DROPOUTS )
3254       ras.dropOutControl = 2;
3255     else
3256     {
3257       if ( ras.outline.flags & FT_OUTLINE_SMART_DROPOUTS )
3258         ras.dropOutControl = 4;
3259       else
3260         ras.dropOutControl = 0;
3261
3262       if ( !( ras.outline.flags & FT_OUTLINE_INCLUDE_STUBS ) )
3263         ras.dropOutControl += 1;
3264     }
3265
3266     ras.second_pass = (FT_Byte)( !( ras.outline.flags &
3267                                     FT_OUTLINE_SINGLE_PASS ) );
3268
3269     /* Vertical Sweep */
3270     ras.Proc_Sweep_Init = Vertical_Sweep_Init;
3271     ras.Proc_Sweep_Span = Vertical_Sweep_Span;
3272     ras.Proc_Sweep_Drop = Vertical_Sweep_Drop;
3273     ras.Proc_Sweep_Step = Vertical_Sweep_Step;
3274
3275     ras.band_top            = 0;
3276     ras.band_stack[0].y_min = 0;
3277     ras.band_stack[0].y_max = (short)( ras.target.rows - 1 );
3278
3279     ras.bWidth  = (unsigned short)ras.target.width;
3280     ras.bTarget = (Byte*)ras.target.buffer;
3281
3282     if ( ( error = Render_Single_Pass( RAS_VARS 0 ) ) != 0 )
3283       return error;
3284
3285     /* Horizontal Sweep */
3286     if ( ras.second_pass && ras.dropOutControl != 2 )
3287     {
3288       ras.Proc_Sweep_Init = Horizontal_Sweep_Init;
3289       ras.Proc_Sweep_Span = Horizontal_Sweep_Span;
3290       ras.Proc_Sweep_Drop = Horizontal_Sweep_Drop;
3291       ras.Proc_Sweep_Step = Horizontal_Sweep_Step;
3292
3293       ras.band_top            = 0;
3294       ras.band_stack[0].y_min = 0;
3295       ras.band_stack[0].y_max = (short)( ras.target.width - 1 );
3296
3297       if ( ( error = Render_Single_Pass( RAS_VARS 1 ) ) != 0 )
3298         return error;
3299     }
3300
3301     return Raster_Err_None;
3302   }
3303
3304
3305 #ifdef FT_RASTER_OPTION_ANTI_ALIASING
3306
3307   /*************************************************************************/
3308   /*                                                                       */
3309   /* <Function>                                                            */
3310   /*    Render_Gray_Glyph                                                  */
3311   /*                                                                       */
3312   /* <Description>                                                         */
3313   /*    Render a glyph with grayscaling.  Sub-banding if needed.           */
3314   /*                                                                       */
3315   /* <Return>                                                              */
3316   /*    FreeType error code.  0 means success.                             */
3317   /*                                                                       */
3318   FT_LOCAL_DEF( FT_Error )
3319   Render_Gray_Glyph( RAS_ARG )
3320   {
3321     Long      pixel_width;
3322     FT_Error  error;
3323
3324
3325     Set_High_Precision( RAS_VARS ras.outline.flags &
3326                                  FT_OUTLINE_HIGH_PRECISION );
3327     ras.scale_shift = ras.precision_shift + 1;
3328
3329     if ( ras.outline.flags & FT_OUTLINE_IGNORE_DROPOUTS )
3330       ras.dropOutControl = 2;
3331     else
3332     {
3333       if ( ras.outline.flags & FT_OUTLINE_SMART_DROPOUTS )
3334         ras.dropOutControl = 4;
3335       else
3336         ras.dropOutControl = 0;
3337
3338       if ( !( ras.outline.flags & FT_OUTLINE_INCLUDE_STUBS ) )
3339         ras.dropOutControl += 1;
3340     }
3341
3342     ras.second_pass = !( ras.outline.flags & FT_OUTLINE_SINGLE_PASS );
3343
3344     /* Vertical Sweep */
3345
3346     ras.band_top            = 0;
3347     ras.band_stack[0].y_min = 0;
3348     ras.band_stack[0].y_max = 2 * ras.target.rows - 1;
3349
3350     ras.bWidth  = ras.gray_width;
3351     pixel_width = 2 * ( ( ras.target.width + 3 ) >> 2 );
3352
3353     if ( ras.bWidth > pixel_width )
3354       ras.bWidth = pixel_width;
3355
3356     ras.bWidth  = ras.bWidth * 8;
3357     ras.bTarget = (Byte*)ras.gray_lines;
3358     ras.gTarget = (Byte*)ras.target.buffer;
3359
3360     ras.Proc_Sweep_Init = Vertical_Gray_Sweep_Init;
3361     ras.Proc_Sweep_Span = Vertical_Sweep_Span;
3362     ras.Proc_Sweep_Drop = Vertical_Sweep_Drop;
3363     ras.Proc_Sweep_Step = Vertical_Gray_Sweep_Step;
3364
3365     error = Render_Single_Pass( RAS_VARS 0 );
3366     if ( error )
3367       return error;
3368
3369     /* Horizontal Sweep */
3370     if ( ras.second_pass && ras.dropOutControl != 2 )
3371     {
3372       ras.Proc_Sweep_Init = Horizontal_Sweep_Init;
3373       ras.Proc_Sweep_Span = Horizontal_Gray_Sweep_Span;
3374       ras.Proc_Sweep_Drop = Horizontal_Gray_Sweep_Drop;
3375       ras.Proc_Sweep_Step = Horizontal_Sweep_Step;
3376
3377       ras.band_top            = 0;
3378       ras.band_stack[0].y_min = 0;
3379       ras.band_stack[0].y_max = ras.target.width * 2 - 1;
3380
3381       error = Render_Single_Pass( RAS_VARS 1 );
3382       if ( error )
3383         return error;
3384     }
3385
3386     return Raster_Err_None;
3387   }
3388
3389 #else /* !FT_RASTER_OPTION_ANTI_ALIASING */
3390
3391   FT_LOCAL_DEF( FT_Error )
3392   Render_Gray_Glyph( RAS_ARG )
3393   {
3394     FT_UNUSED_RASTER;
3395
3396     return Raster_Err_Unsupported;
3397   }
3398
3399 #endif /* !FT_RASTER_OPTION_ANTI_ALIASING */
3400
3401
3402   static void
3403   ft_black_init( black_PRaster  raster )
3404   {
3405 #ifdef FT_RASTER_OPTION_ANTI_ALIASING
3406     FT_UInt  n;
3407
3408
3409     /* set default 5-levels gray palette */
3410     for ( n = 0; n < 5; n++ )
3411       raster->grays[n] = n * 255 / 4;
3412
3413     raster->gray_width = RASTER_GRAY_LINES / 2;
3414 #else
3415     FT_UNUSED( raster );
3416 #endif
3417   }
3418
3419
3420   /**** RASTER OBJECT CREATION: In standalone mode, we simply use *****/
3421   /****                         a static object.                  *****/
3422
3423
3424 #ifdef _STANDALONE_
3425
3426
3427   static int
3428   ft_black_new( void*       memory,
3429                 FT_Raster  *araster )
3430   {
3431      static black_TRaster  the_raster;
3432      FT_UNUSED( memory );
3433
3434
3435      *araster = (FT_Raster)&the_raster;
3436      FT_MEM_ZERO( &the_raster, sizeof ( the_raster ) );
3437      ft_black_init( &the_raster );
3438
3439      return 0;
3440   }
3441
3442
3443   static void
3444   ft_black_done( FT_Raster  raster )
3445   {
3446     /* nothing */
3447     FT_UNUSED( raster );
3448   }
3449
3450
3451 #else /* !_STANDALONE_ */
3452
3453
3454   static int
3455   ft_black_new( FT_Memory       memory,
3456                 black_PRaster  *araster )
3457   {
3458     FT_Error       error;
3459     black_PRaster  raster = NULL;
3460
3461
3462     *araster = 0;
3463     if ( !FT_NEW( raster ) )
3464     {
3465       raster->memory = memory;
3466       ft_black_init( raster );
3467
3468       *araster = raster;
3469     }
3470
3471     return error;
3472   }
3473
3474
3475   static void
3476   ft_black_done( black_PRaster  raster )
3477   {
3478     FT_Memory  memory = (FT_Memory)raster->memory;
3479
3480
3481     FT_FREE( raster );
3482   }
3483
3484
3485 #endif /* !_STANDALONE_ */
3486
3487
3488   static void
3489   ft_black_reset( black_PRaster  raster,
3490                   char*          pool_base,
3491                   long           pool_size )
3492   {
3493     if ( raster )
3494     {
3495       if ( pool_base && pool_size >= (long)sizeof ( black_TWorker ) + 2048 )
3496       {
3497         black_PWorker  worker = (black_PWorker)pool_base;
3498
3499
3500         raster->buffer      = pool_base + ( ( sizeof ( *worker ) + 7 ) & ~7 );
3501         raster->buffer_size = pool_base + pool_size - (char*)raster->buffer;
3502         raster->worker      = worker;
3503       }
3504       else
3505       {
3506         raster->buffer      = NULL;
3507         raster->buffer_size = 0;
3508         raster->worker      = NULL;
3509       }
3510     }
3511   }
3512
3513
3514   static void
3515   ft_black_set_mode( black_PRaster  raster,
3516                      unsigned long  mode,
3517                      const char*    palette )
3518   {
3519 #ifdef FT_RASTER_OPTION_ANTI_ALIASING
3520
3521     if ( mode == FT_MAKE_TAG( 'p', 'a', 'l', '5' ) )
3522     {
3523       /* set 5-levels gray palette */
3524       raster->grays[0] = palette[0];
3525       raster->grays[1] = palette[1];
3526       raster->grays[2] = palette[2];
3527       raster->grays[3] = palette[3];
3528       raster->grays[4] = palette[4];
3529     }
3530
3531 #else
3532
3533     FT_UNUSED( raster );
3534     FT_UNUSED( mode );
3535     FT_UNUSED( palette );
3536
3537 #endif
3538   }
3539
3540
3541   static int
3542   ft_black_render( black_PRaster            raster,
3543                    const FT_Raster_Params*  params )
3544   {
3545     const FT_Outline*  outline    = (const FT_Outline*)params->source;
3546     const FT_Bitmap*   target_map = params->target;
3547     black_PWorker      worker;
3548
3549
3550     if ( !raster || !raster->buffer || !raster->buffer_size )
3551       return Raster_Err_Not_Ini;
3552
3553     if ( !outline )
3554       return Raster_Err_Invalid;
3555
3556     /* return immediately if the outline is empty */
3557     if ( outline->n_points == 0 || outline->n_contours <= 0 )
3558       return Raster_Err_None;
3559
3560     if ( !outline->contours || !outline->points )
3561       return Raster_Err_Invalid;
3562
3563     if ( outline->n_points !=
3564            outline->contours[outline->n_contours - 1] + 1 )
3565       return Raster_Err_Invalid;
3566
3567     worker = raster->worker;
3568
3569     /* this version of the raster does not support direct rendering, sorry */
3570     if ( params->flags & FT_RASTER_FLAG_DIRECT )
3571       return Raster_Err_Unsupported;
3572
3573     if ( !target_map )
3574       return Raster_Err_Invalid;
3575
3576     /* nothing to do */
3577     if ( !target_map->width || !target_map->rows )
3578       return Raster_Err_None;
3579
3580     if ( !target_map->buffer )
3581       return Raster_Err_Invalid;
3582
3583     ras.outline = *outline;
3584     ras.target  = *target_map;
3585
3586     worker->buff       = (PLong) raster->buffer;
3587     worker->sizeBuff   = worker->buff +
3588                            raster->buffer_size / sizeof ( Long );
3589 #ifdef FT_RASTER_OPTION_ANTI_ALIASING
3590     worker->grays      = raster->grays;
3591     worker->gray_width = raster->gray_width;
3592
3593     FT_MEM_ZERO( worker->gray_lines, worker->gray_width * 2 );
3594 #endif
3595
3596     return ( params->flags & FT_RASTER_FLAG_AA )
3597            ? Render_Gray_Glyph( RAS_VAR )
3598            : Render_Glyph( RAS_VAR );
3599   }
3600
3601
3602   FT_DEFINE_RASTER_FUNCS( ft_standard_raster,
3603     FT_GLYPH_FORMAT_OUTLINE,
3604     (FT_Raster_New_Func)     ft_black_new,
3605     (FT_Raster_Reset_Func)   ft_black_reset,
3606     (FT_Raster_Set_Mode_Func)ft_black_set_mode,
3607     (FT_Raster_Render_Func)  ft_black_render,
3608     (FT_Raster_Done_Func)    ft_black_done
3609   )
3610
3611
3612 /* END */