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