libraries/freetype-2.0.5/ftraster.c

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