lib/freetype/src/raster/ftraster.c

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