src/raster/ftraster.c

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