XFA: merge patch from CL 817753002
[pdfium.git] / core / src / fxge / fx_freetype / fxft2.5.01 / src / smooth / ftgrays.c
1 /***************************************************************************/
2 /*                                                                         */
3 /*  ftgrays.c                                                              */
4 /*                                                                         */
5 /*    A new `perfect' anti-aliasing renderer (body).                       */
6 /*                                                                         */
7 /*  Copyright 2000-2003, 2005-2013 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 `ftgrays.h' and `ftimage.h' into the current            */
23   /* compilation directory.  Typically, you could do something like        */
24   /*                                                                       */
25   /* - copy `src/smooth/ftgrays.c' (this file) to your current directory   */
26   /*                                                                       */
27   /* - copy `include/freetype/ftimage.h' and `src/smooth/ftgrays.h' to the */
28   /*   same directory                                                      */
29   /*                                                                       */
30   /* - compile `ftgrays' with the _STANDALONE_ macro defined, as in        */
31   /*                                                                       */
32   /*     cc -c -D_STANDALONE_ ftgrays.c                                    */
33   /*                                                                       */
34   /* The renderer can be initialized with a call to                        */
35   /* `ft_gray_raster.raster_new'; an anti-aliased bitmap can be generated  */
36   /* with a call to `ft_gray_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   /* This is a new anti-aliasing scan-converter for FreeType 2.  The       */
46   /* algorithm used here is _very_ different from the one in the standard  */
47   /* `ftraster' module.  Actually, `ftgrays' computes the _exact_          */
48   /* coverage of the outline on each pixel cell.                           */
49   /*                                                                       */
50   /* It is based on ideas that I initially found in Raph Levien's          */
51   /* excellent LibArt graphics library (see http://www.levien.com/libart   */
52   /* for more information, though the web pages do not tell anything       */
53   /* about the renderer; you'll have to dive into the source code to       */
54   /* understand how it works).                                             */
55   /*                                                                       */
56   /* Note, however, that this is a _very_ different implementation         */
57   /* compared to Raph's.  Coverage information is stored in a very         */
58   /* different way, and I don't use sorted vector paths.  Also, it doesn't */
59   /* use floating point values.                                            */
60   /*                                                                       */
61   /* This renderer has the following advantages:                           */
62   /*                                                                       */
63   /* - It doesn't need an intermediate bitmap.  Instead, one can supply a  */
64   /*   callback function that will be called by the renderer to draw gray  */
65   /*   spans on any target surface.  You can thus do direct composition on */
66   /*   any kind of bitmap, provided that you give the renderer the right   */
67   /*   callback.                                                           */
68   /*                                                                       */
69   /* - A perfect anti-aliaser, i.e., it computes the _exact_ coverage on   */
70   /*   each pixel cell.                                                    */
71   /*                                                                       */
72   /* - It performs a single pass on the outline (the `standard' FT2        */
73   /*   renderer makes two passes).                                         */
74   /*                                                                       */
75   /* - It can easily be modified to render to _any_ number of gray levels  */
76   /*   cheaply.                                                            */
77   /*                                                                       */
78   /* - For small (< 20) pixel sizes, it is faster than the standard        */
79   /*   renderer.                                                           */
80   /*                                                                       */
81   /*************************************************************************/
82
83
84   /*************************************************************************/
85   /*                                                                       */
86   /* The macro FT_COMPONENT is used in trace mode.  It is an implicit      */
87   /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log  */
88   /* messages during execution.                                            */
89   /*                                                                       */
90 #undef  FT_COMPONENT
91 #define FT_COMPONENT  trace_smooth
92
93
94 #ifdef _STANDALONE_
95
96
97   /* Auxiliary macros for token concatenation. */
98 #define FT_ERR_XCAT( x, y )  x ## y
99 #define FT_ERR_CAT( x, y )   FT_ERR_XCAT( x, y )
100
101
102   /* define this to dump debugging information */
103 /* #define FT_DEBUG_LEVEL_TRACE */
104
105
106 #ifdef FT_DEBUG_LEVEL_TRACE
107 #include <stdio.h>
108 #include <stdarg.h>
109 #endif
110
111 #include <stddef.h>
112 #include <string.h>
113 #include <setjmp.h>
114 #include <limits.h>
115 #define FT_UINT_MAX  UINT_MAX
116 #define FT_INT_MAX   INT_MAX
117
118 #define ft_memset   memset
119
120 #define ft_setjmp   setjmp
121 #define ft_longjmp  longjmp
122 #define ft_jmp_buf  jmp_buf
123
124 typedef ptrdiff_t  FT_PtrDist;
125
126
127 #define ErrRaster_Invalid_Mode      -2
128 #define ErrRaster_Invalid_Outline   -1
129 #define ErrRaster_Invalid_Argument  -3
130 #define ErrRaster_Memory_Overflow   -4
131
132 #define FT_BEGIN_HEADER
133 #define FT_END_HEADER
134
135 #include "ftimage.h"
136 #include "ftgrays.h"
137
138
139   /* This macro is used to indicate that a function parameter is unused. */
140   /* Its purpose is simply to reduce compiler warnings.  Note also that  */
141   /* simply defining it as `(void)x' doesn't avoid warnings with certain */
142   /* ANSI compilers (e.g. LCC).                                          */
143 #define FT_UNUSED( x )  (x) = (x)
144
145
146   /* we only use level 5 & 7 tracing messages; cf. ftdebug.h */
147
148 #ifdef FT_DEBUG_LEVEL_TRACE
149
150   void
151   FT_Message( const char*  fmt,
152               ... )
153   {
154     va_list  ap;
155
156
157     va_start( ap, fmt );
158     vfprintf( stderr, fmt, ap );
159     va_end( ap );
160   }
161
162
163   /* empty function useful for setting a breakpoint to catch errors */
164   int
165   FT_Throw( int          error,
166             int          line,
167             const char*  file )
168   {
169     FT_UNUSED( error );
170     FT_UNUSED( line );
171     FT_UNUSED( file );
172
173     return 0;
174   }
175
176
177   /* we don't handle tracing levels in stand-alone mode; */
178 #ifndef FT_TRACE5
179 #define FT_TRACE5( varformat )  FT_Message varformat
180 #endif
181 #ifndef FT_TRACE7
182 #define FT_TRACE7( varformat )  FT_Message varformat
183 #endif
184 #ifndef FT_ERROR
185 #define FT_ERROR( varformat )   FT_Message varformat
186 #endif
187
188 #define FT_THROW( e )                               \
189           ( FT_Throw( FT_ERR_CAT( ErrRaster, e ),   \
190                       __LINE__,                     \
191                       __FILE__ )                  | \
192             FT_ERR_CAT( ErrRaster, e )            )
193
194 #else /* !FT_DEBUG_LEVEL_TRACE */
195
196 #define FT_TRACE5( x )  do { } while ( 0 )     /* nothing */
197 #define FT_TRACE7( x )  do { } while ( 0 )     /* nothing */
198 #define FT_ERROR( x )   do { } while ( 0 )     /* nothing */
199 #define FT_THROW( e )   FT_ERR_CAT( ErrRaster_, e )
200
201
202 #endif /* !FT_DEBUG_LEVEL_TRACE */
203
204
205 #define FT_DEFINE_OUTLINE_FUNCS( class_,               \
206                                  move_to_, line_to_,   \
207                                  conic_to_, cubic_to_, \
208                                  shift_, delta_ )      \
209           static const FT_Outline_Funcs class_ =       \
210           {                                            \
211             move_to_,                                  \
212             line_to_,                                  \
213             conic_to_,                                 \
214             cubic_to_,                                 \
215             shift_,                                    \
216             delta_                                     \
217          };
218
219 #define FT_DEFINE_RASTER_FUNCS( class_, glyph_format_,            \
220                                 raster_new_, raster_reset_,       \
221                                 raster_set_mode_, raster_render_, \
222                                 raster_done_ )                    \
223           const FT_Raster_Funcs class_ =                          \
224           {                                                       \
225             glyph_format_,                                        \
226             raster_new_,                                          \
227             raster_reset_,                                        \
228             raster_set_mode_,                                     \
229             raster_render_,                                       \
230             raster_done_                                          \
231          };
232
233
234 #else /* !_STANDALONE_ */
235
236
237 #include "../../include/ft2build.h"
238 #include "ftgrays.h"
239 #include "../../include/freetype/internal/ftobjs.h"
240 #include "../../include/freetype/internal/ftdebug.h"
241 #include "../../include/freetype/ftoutln.h"
242
243 #include "ftsmerrs.h"
244
245 #include "ftspic.h"
246
247 #define Smooth_Err_Invalid_Mode     Smooth_Err_Cannot_Render_Glyph
248 #define Smooth_Err_Memory_Overflow  Smooth_Err_Out_Of_Memory
249 #define ErrRaster_Memory_Overflow   Smooth_Err_Out_Of_Memory
250
251
252 #endif /* !_STANDALONE_ */
253
254
255 #ifndef FT_MEM_SET
256 #define FT_MEM_SET( d, s, c )  ft_memset( d, s, c )
257 #endif
258
259 #ifndef FT_MEM_ZERO
260 #define FT_MEM_ZERO( dest, count )  FT_MEM_SET( dest, 0, count )
261 #endif
262
263   /* as usual, for the speed hungry :-) */
264
265 #undef RAS_ARG
266 #undef RAS_ARG_
267 #undef RAS_VAR
268 #undef RAS_VAR_
269
270 #ifndef FT_STATIC_RASTER
271
272 #define RAS_ARG   gray_PWorker  worker
273 #define RAS_ARG_  gray_PWorker  worker,
274
275 #define RAS_VAR   worker
276 #define RAS_VAR_  worker,
277
278 #else /* FT_STATIC_RASTER */
279
280 #define RAS_ARG   /* empty */
281 #define RAS_ARG_  /* empty */
282 #define RAS_VAR   /* empty */
283 #define RAS_VAR_  /* empty */
284
285 #endif /* FT_STATIC_RASTER */
286
287
288   /* must be at least 6 bits! */
289 #define PIXEL_BITS  8
290
291 #undef FLOOR
292 #undef CEILING
293 #undef TRUNC
294 #undef SCALED
295
296 #define ONE_PIXEL       ( 1L << PIXEL_BITS )
297 #define PIXEL_MASK      ( -1L << PIXEL_BITS )
298 #define TRUNC( x )      ( (TCoord)( (x) >> PIXEL_BITS ) )
299 #define SUBPIXELS( x )  ( (TPos)(x) << PIXEL_BITS )
300 #define FLOOR( x )      ( (x) & -ONE_PIXEL )
301 #define CEILING( x )    ( ( (x) + ONE_PIXEL - 1 ) & -ONE_PIXEL )
302 #define ROUND( x )      ( ( (x) + ONE_PIXEL / 2 ) & -ONE_PIXEL )
303
304 #if PIXEL_BITS >= 6
305 #define UPSCALE( x )    ( (x) << ( PIXEL_BITS - 6 ) )
306 #define DOWNSCALE( x )  ( (x) >> ( PIXEL_BITS - 6 ) )
307 #else
308 #define UPSCALE( x )    ( (x) >> ( 6 - PIXEL_BITS ) )
309 #define DOWNSCALE( x )  ( (x) << ( 6 - PIXEL_BITS ) )
310 #endif
311
312
313   /*************************************************************************/
314   /*                                                                       */
315   /*   TYPE DEFINITIONS                                                    */
316   /*                                                                       */
317
318   /* don't change the following types to FT_Int or FT_Pos, since we might */
319   /* need to define them to "float" or "double" when experimenting with   */
320   /* new algorithms                                                       */
321
322   typedef long  TCoord;   /* integer scanline/pixel coordinate */
323   typedef long  TPos;     /* sub-pixel coordinate              */
324
325   /* determine the type used to store cell areas.  This normally takes at */
326   /* least PIXEL_BITS*2 + 1 bits.  On 16-bit systems, we need to use      */
327   /* `long' instead of `int', otherwise bad things happen                 */
328
329 #if PIXEL_BITS <= 7
330
331   typedef int  TArea;
332
333 #else /* PIXEL_BITS >= 8 */
334
335   /* approximately determine the size of integers using an ANSI-C header */
336 #if FT_UINT_MAX == 0xFFFFU
337   typedef long  TArea;
338 #else
339   typedef int   TArea;
340 #endif
341
342 #endif /* PIXEL_BITS >= 8 */
343
344
345   /* maximum number of gray spans in a call to the span callback */
346 #define FT_MAX_GRAY_SPANS  32
347
348
349   typedef struct TCell_*  PCell;
350
351   typedef struct  TCell_
352   {
353     TPos    x;     /* same with gray_TWorker.ex    */
354     TCoord  cover; /* same with gray_TWorker.cover */
355     TArea   area;
356     PCell   next;
357
358   } TCell;
359
360
361 #if defined( _MSC_VER )      /* Visual C++ (and Intel C++) */
362   /* We disable the warning `structure was padded due to   */
363   /* __declspec(align())' in order to compile cleanly with */
364   /* the maximum level of warnings.                        */
365 #pragma warning( push )
366 #pragma warning( disable : 4324 )
367 #endif /* _MSC_VER */
368
369   typedef struct  gray_TWorker_
370   {
371     TCoord  ex, ey;
372     TPos    min_ex, max_ex;
373     TPos    min_ey, max_ey;
374     TPos    count_ex, count_ey;
375
376     TArea   area;
377     TCoord  cover;
378     int     invalid;
379
380     PCell       cells;
381     FT_PtrDist  max_cells;
382     FT_PtrDist  num_cells;
383
384     TCoord  cx, cy;
385     TPos    x,  y;
386
387     TPos    last_ey;
388
389     FT_Vector   bez_stack[32 * 3 + 1];
390     int         lev_stack[32];
391
392     FT_Outline  outline;
393     FT_Bitmap   target;
394     FT_BBox     clip_box;
395
396     FT_Span     gray_spans[FT_MAX_GRAY_SPANS];
397     int         num_gray_spans;
398
399     FT_Raster_Span_Func  render_span;
400     void*                render_span_data;
401     int                  span_y;
402
403     int  band_size;
404     int  band_shoot;
405
406     ft_jmp_buf  jump_buffer;
407
408     void*       buffer;
409     long        buffer_size;
410
411     PCell*     ycells;
412     TPos       ycount;
413
414   } gray_TWorker, *gray_PWorker;
415
416 #if defined( _MSC_VER )
417 #pragma warning( pop )
418 #endif
419
420
421 #ifndef FT_STATIC_RASTER
422 #define ras  (*worker)
423 #else
424   static gray_TWorker  ras;
425 #endif
426
427
428   typedef struct gray_TRaster_
429   {
430     void*         buffer;
431     long          buffer_size;
432     int           band_size;
433     void*         memory;
434     gray_PWorker  worker;
435
436   } gray_TRaster, *gray_PRaster;
437
438
439
440   /*************************************************************************/
441   /*                                                                       */
442   /* Initialize the cells table.                                           */
443   /*                                                                       */
444   static void
445   gray_init_cells( RAS_ARG_ void*  buffer,
446                    long            byte_size )
447   {
448     ras.buffer      = buffer;
449     ras.buffer_size = byte_size;
450
451     ras.ycells      = (PCell*) buffer;
452     ras.cells       = NULL;
453     ras.max_cells   = 0;
454     ras.num_cells   = 0;
455     ras.area        = 0;
456     ras.cover       = 0;
457     ras.invalid     = 1;
458   }
459
460
461   /*************************************************************************/
462   /*                                                                       */
463   /* Compute the outline bounding box.                                     */
464   /*                                                                       */
465   static void
466   gray_compute_cbox( RAS_ARG )
467   {
468     FT_Outline*  outline = &ras.outline;
469     FT_Vector*   vec     = outline->points;
470     FT_Vector*   limit   = vec + outline->n_points;
471
472
473     if ( outline->n_points <= 0 )
474     {
475       ras.min_ex = ras.max_ex = 0;
476       ras.min_ey = ras.max_ey = 0;
477       return;
478     }
479
480     ras.min_ex = ras.max_ex = vec->x;
481     ras.min_ey = ras.max_ey = vec->y;
482
483     vec++;
484
485     for ( ; vec < limit; vec++ )
486     {
487       TPos  x = vec->x;
488       TPos  y = vec->y;
489
490
491       if ( x < ras.min_ex ) ras.min_ex = x;
492       if ( x > ras.max_ex ) ras.max_ex = x;
493       if ( y < ras.min_ey ) ras.min_ey = y;
494       if ( y > ras.max_ey ) ras.max_ey = y;
495     }
496
497     /* truncate the bounding box to integer pixels */
498     ras.min_ex = ras.min_ex >> 6;
499     ras.min_ey = ras.min_ey >> 6;
500     ras.max_ex = ( ras.max_ex + 63 ) >> 6;
501     ras.max_ey = ( ras.max_ey + 63 ) >> 6;
502   }
503
504
505   /*************************************************************************/
506   /*                                                                       */
507   /* Record the current cell in the table.                                 */
508   /*                                                                       */
509   static PCell
510   gray_find_cell( RAS_ARG )
511   {
512     PCell  *pcell, cell;
513     TPos    x = ras.ex;
514
515
516     if ( x > ras.count_ex )
517       x = ras.count_ex;
518
519     pcell = &ras.ycells[ras.ey];
520     for (;;)
521     {
522       cell = *pcell;
523       if ( cell == NULL || cell->x > x )
524         break;
525
526       if ( cell->x == x )
527         goto Exit;
528
529       pcell = &cell->next;
530     }
531
532     if ( ras.num_cells >= ras.max_cells )
533       ft_longjmp( ras.jump_buffer, 1 );
534
535     cell        = ras.cells + ras.num_cells++;
536     cell->x     = x;
537     cell->area  = 0;
538     cell->cover = 0;
539
540     cell->next  = *pcell;
541     *pcell      = cell;
542
543   Exit:
544     return cell;
545   }
546
547
548   static void
549   gray_record_cell( RAS_ARG )
550   {
551     if ( !ras.invalid && ( ras.area | ras.cover ) )
552     {
553       PCell  cell = gray_find_cell( RAS_VAR );
554
555
556       cell->area  += ras.area;
557       cell->cover += ras.cover;
558     }
559   }
560
561
562   /*************************************************************************/
563   /*                                                                       */
564   /* Set the current cell to a new position.                               */
565   /*                                                                       */
566   static void
567   gray_set_cell( RAS_ARG_ TCoord  ex,
568                           TCoord  ey )
569   {
570     /* Move the cell pointer to a new position.  We set the `invalid'      */
571     /* flag to indicate that the cell isn't part of those we're interested */
572     /* in during the render phase.  This means that:                       */
573     /*                                                                     */
574     /* . the new vertical position must be within min_ey..max_ey-1.        */
575     /* . the new horizontal position must be strictly less than max_ex     */
576     /*                                                                     */
577     /* Note that if a cell is to the left of the clipping region, it is    */
578     /* actually set to the (min_ex-1) horizontal position.                 */
579
580     /* All cells that are on the left of the clipping region go to the */
581     /* min_ex - 1 horizontal position.                                 */
582     ey -= ras.min_ey;
583
584     if ( ex > ras.max_ex )
585       ex = ras.max_ex;
586
587     ex -= ras.min_ex;
588     if ( ex < 0 )
589       ex = -1;
590
591     /* are we moving to a different cell ? */
592     if ( ex != ras.ex || ey != ras.ey )
593     {
594       /* record the current one if it is valid */
595       if ( !ras.invalid )
596         gray_record_cell( RAS_VAR );
597
598       ras.area  = 0;
599       ras.cover = 0;
600     }
601
602     ras.ex      = ex;
603     ras.ey      = ey;
604     ras.invalid = ( (unsigned)ey >= (unsigned)ras.count_ey ||
605                               ex >= ras.count_ex           );
606   }
607
608
609   /*************************************************************************/
610   /*                                                                       */
611   /* Start a new contour at a given cell.                                  */
612   /*                                                                       */
613   static void
614   gray_start_cell( RAS_ARG_ TCoord  ex,
615                             TCoord  ey )
616   {
617     if ( ex > ras.max_ex )
618       ex = (TCoord)( ras.max_ex );
619
620     if ( ex < ras.min_ex )
621       ex = (TCoord)( ras.min_ex - 1 );
622
623     ras.area    = 0;
624     ras.cover   = 0;
625     ras.ex      = ex - ras.min_ex;
626     ras.ey      = ey - ras.min_ey;
627     ras.last_ey = SUBPIXELS( ey );
628     ras.invalid = 0;
629
630     gray_set_cell( RAS_VAR_ ex, ey );
631   }
632
633
634   /*************************************************************************/
635   /*                                                                       */
636   /* Render a scanline as one or more cells.                               */
637   /*                                                                       */
638   static void
639   gray_render_scanline( RAS_ARG_ TCoord  ey,
640                                  TPos    x1,
641                                  TCoord  y1,
642                                  TPos    x2,
643                                  TCoord  y2 )
644   {
645     TCoord  ex1, ex2, fx1, fx2, delta, mod;
646     long    p, first, dx;
647     int     incr;
648
649
650     dx = x2 - x1;
651
652     ex1 = TRUNC( x1 );
653     ex2 = TRUNC( x2 );
654     fx1 = (TCoord)( x1 - SUBPIXELS( ex1 ) );
655     fx2 = (TCoord)( x2 - SUBPIXELS( ex2 ) );
656
657     /* trivial case.  Happens often */
658     if ( y1 == y2 )
659     {
660       gray_set_cell( RAS_VAR_ ex2, ey );
661       return;
662     }
663
664     /* everything is located in a single cell.  That is easy! */
665     /*                                                        */
666     if ( ex1 == ex2 )
667     {
668       delta      = y2 - y1;
669       ras.area  += (TArea)(( fx1 + fx2 ) * delta);
670       ras.cover += delta;
671       return;
672     }
673
674     /* ok, we'll have to render a run of adjacent cells on the same */
675     /* scanline...                                                  */
676     /*                                                              */
677     p     = ( ONE_PIXEL - fx1 ) * ( y2 - y1 );
678     first = ONE_PIXEL;
679     incr  = 1;
680
681     if ( dx < 0 )
682     {
683       p     = fx1 * ( y2 - y1 );
684       first = 0;
685       incr  = -1;
686       dx    = -dx;
687     }
688
689     delta = (TCoord)( p / dx );
690     mod   = (TCoord)( p % dx );
691     if ( mod < 0 )
692     {
693       delta--;
694       mod += (TCoord)dx;
695     }
696
697     ras.area  += (TArea)(( fx1 + first ) * delta);
698     ras.cover += delta;
699
700     ex1 += incr;
701     gray_set_cell( RAS_VAR_ ex1, ey );
702     y1  += delta;
703
704     if ( ex1 != ex2 )
705     {
706       TCoord  lift, rem;
707
708
709       p    = ONE_PIXEL * ( y2 - y1 + delta );
710       lift = (TCoord)( p / dx );
711       rem  = (TCoord)( p % dx );
712       if ( rem < 0 )
713       {
714         lift--;
715         rem += (TCoord)dx;
716       }
717
718       mod -= (int)dx;
719
720       while ( ex1 != ex2 )
721       {
722         delta = lift;
723         mod  += rem;
724         if ( mod >= 0 )
725         {
726           mod -= (TCoord)dx;
727           delta++;
728         }
729
730         ras.area  += (TArea)(ONE_PIXEL * delta);
731         ras.cover += delta;
732         y1        += delta;
733         ex1       += incr;
734         gray_set_cell( RAS_VAR_ ex1, ey );
735       }
736     }
737
738     delta      = y2 - y1;
739     ras.area  += (TArea)(( fx2 + ONE_PIXEL - first ) * delta);
740     ras.cover += delta;
741   }
742
743
744   /*************************************************************************/
745   /*                                                                       */
746   /* Render a given line as a series of scanlines.                         */
747   /*                                                                       */
748   static void
749   gray_render_line( RAS_ARG_ TPos  to_x,
750                              TPos  to_y )
751   {
752     TCoord  ey1, ey2, fy1, fy2, mod;
753     TPos    dx, dy, x, x2;
754     long    p, first;
755     int     delta, rem, lift, incr;
756
757
758     ey1 = TRUNC( ras.last_ey );
759     ey2 = TRUNC( to_y );     /* if (ey2 >= ras.max_ey) ey2 = ras.max_ey-1; */
760     fy1 = (TCoord)( ras.y - ras.last_ey );
761     fy2 = (TCoord)( to_y - SUBPIXELS( ey2 ) );
762
763     dx = to_x - ras.x;
764     dy = to_y - ras.y;
765
766     /* XXX: we should do something about the trivial case where dx == 0, */
767     /*      as it happens very often!                                    */
768
769     /* perform vertical clipping */
770     {
771       TCoord  min, max;
772
773
774       min = ey1;
775       max = ey2;
776       if ( ey1 > ey2 )
777       {
778         min = ey2;
779         max = ey1;
780       }
781       if ( min >= ras.max_ey || max < ras.min_ey )
782         goto End;
783     }
784
785     /* everything is on a single scanline */
786     if ( ey1 == ey2 )
787     {
788       gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, to_x, fy2 );
789       goto End;
790     }
791
792     /* vertical line - avoid calling gray_render_scanline */
793     incr = 1;
794
795     if ( dx == 0 )
796     {
797       TCoord  ex     = TRUNC( ras.x );
798       TCoord  two_fx = (TCoord)( ( ras.x - SUBPIXELS( ex ) ) << 1 );
799       TArea   area;
800
801
802       first = ONE_PIXEL;
803       if ( dy < 0 )
804       {
805         first = 0;
806         incr  = -1;
807       }
808
809       delta      = (int)( first - fy1 );
810       ras.area  += (TArea)two_fx * delta;
811       ras.cover += delta;
812       ey1       += incr;
813
814       gray_set_cell( RAS_VAR_ ex, ey1 );
815
816       delta = (int)( first + first - ONE_PIXEL );
817       area  = (TArea)two_fx * delta;
818       while ( ey1 != ey2 )
819       {
820         ras.area  += area;
821         ras.cover += delta;
822         ey1       += incr;
823
824         gray_set_cell( RAS_VAR_ ex, ey1 );
825       }
826
827       delta      = (int)( fy2 - ONE_PIXEL + first );
828       ras.area  += (TArea)two_fx * delta;
829       ras.cover += delta;
830
831       goto End;
832     }
833
834     /* ok, we have to render several scanlines */
835     p     = ( ONE_PIXEL - fy1 ) * dx;
836     first = ONE_PIXEL;
837     incr  = 1;
838
839     if ( dy < 0 )
840     {
841       p     = fy1 * dx;
842       first = 0;
843       incr  = -1;
844       dy    = -dy;
845     }
846
847     delta = (int)( p / dy );
848     mod   = (int)( p % dy );
849     if ( mod < 0 )
850     {
851       delta--;
852       mod += (TCoord)dy;
853     }
854
855     x = ras.x + delta;
856     gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, x, (TCoord)first );
857
858     ey1 += incr;
859     gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 );
860
861     if ( ey1 != ey2 )
862     {
863       p     = ONE_PIXEL * dx;
864       lift  = (int)( p / dy );
865       rem   = (int)( p % dy );
866       if ( rem < 0 )
867       {
868         lift--;
869         rem += (int)dy;
870       }
871       mod -= (int)dy;
872
873       while ( ey1 != ey2 )
874       {
875         delta = lift;
876         mod  += rem;
877         if ( mod >= 0 )
878         {
879           mod -= (int)dy;
880           delta++;
881         }
882
883         x2 = x + delta;
884         gray_render_scanline( RAS_VAR_ ey1, x,
885                                        (TCoord)( ONE_PIXEL - first ), x2,
886                                        (TCoord)first );
887         x = x2;
888
889         ey1 += incr;
890         gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 );
891       }
892     }
893
894     gray_render_scanline( RAS_VAR_ ey1, x,
895                                    (TCoord)( ONE_PIXEL - first ), to_x,
896                                    fy2 );
897
898   End:
899     ras.x       = to_x;
900     ras.y       = to_y;
901     ras.last_ey = SUBPIXELS( ey2 );
902   }
903
904
905   static void
906   gray_split_conic( FT_Vector*  base )
907   {
908     TPos  a, b;
909
910
911     base[4].x = base[2].x;
912     b = base[1].x;
913     a = base[3].x = ( base[2].x + b ) / 2;
914     b = base[1].x = ( base[0].x + b ) / 2;
915     base[2].x = ( a + b ) / 2;
916
917     base[4].y = base[2].y;
918     b = base[1].y;
919     a = base[3].y = ( base[2].y + b ) / 2;
920     b = base[1].y = ( base[0].y + b ) / 2;
921     base[2].y = ( a + b ) / 2;
922   }
923
924
925   static void
926   gray_render_conic( RAS_ARG_ const FT_Vector*  control,
927                               const FT_Vector*  to )
928   {
929     TPos        dx, dy;
930     TPos        min, max, y;
931     int         top, level;
932     int*        levels;
933     FT_Vector*  arc;
934
935
936     levels = ras.lev_stack;
937
938     arc      = ras.bez_stack;
939     arc[0].x = UPSCALE( to->x );
940     arc[0].y = UPSCALE( to->y );
941     arc[1].x = UPSCALE( control->x );
942     arc[1].y = UPSCALE( control->y );
943     arc[2].x = ras.x;
944     arc[2].y = ras.y;
945     top      = 0;
946
947     dx = FT_ABS( arc[2].x + arc[0].x - 2 * arc[1].x );
948     dy = FT_ABS( arc[2].y + arc[0].y - 2 * arc[1].y );
949     if ( dx < dy )
950       dx = dy;
951
952     if ( dx < ONE_PIXEL / 4 )
953       goto Draw;
954
955     /* short-cut the arc that crosses the current band */
956     min = max = arc[0].y;
957
958     y = arc[1].y;
959     if ( y < min ) min = y;
960     if ( y > max ) max = y;
961
962     y = arc[2].y;
963     if ( y < min ) min = y;
964     if ( y > max ) max = y;
965
966     if ( TRUNC( min ) >= ras.max_ey || TRUNC( max ) < ras.min_ey )
967       goto Draw;
968
969     level = 0;
970     do
971     {
972       dx >>= 2;
973       level++;
974     } while ( dx > ONE_PIXEL / 4 );
975
976     levels[0] = level;
977
978     do
979     {
980       level = levels[top];
981       if ( level > 0 )
982       {
983         gray_split_conic( arc );
984         arc += 2;
985         top++;
986         levels[top] = levels[top - 1] = level - 1;
987         continue;
988       }
989
990     Draw:
991       gray_render_line( RAS_VAR_ arc[0].x, arc[0].y );
992       top--;
993       arc -= 2;
994
995     } while ( top >= 0 );
996   }
997
998
999   static void
1000   gray_split_cubic( FT_Vector*  base )
1001   {
1002     TPos  a, b, c, d;
1003
1004
1005     base[6].x = base[3].x;
1006     c = base[1].x;
1007     d = base[2].x;
1008     base[1].x = a = ( base[0].x + c ) / 2;
1009     base[5].x = b = ( base[3].x + d ) / 2;
1010     c = ( c + d ) / 2;
1011     base[2].x = a = ( a + c ) / 2;
1012     base[4].x = b = ( b + c ) / 2;
1013     base[3].x = ( a + b ) / 2;
1014
1015     base[6].y = base[3].y;
1016     c = base[1].y;
1017     d = base[2].y;
1018     base[1].y = a = ( base[0].y + c ) / 2;
1019     base[5].y = b = ( base[3].y + d ) / 2;
1020     c = ( c + d ) / 2;
1021     base[2].y = a = ( a + c ) / 2;
1022     base[4].y = b = ( b + c ) / 2;
1023     base[3].y = ( a + b ) / 2;
1024   }
1025
1026
1027   static void
1028   gray_render_cubic( RAS_ARG_ const FT_Vector*  control1,
1029                               const FT_Vector*  control2,
1030                               const FT_Vector*  to )
1031   {
1032     FT_Vector*  arc;
1033     TPos        min, max, y;
1034
1035
1036     arc      = ras.bez_stack;
1037     arc[0].x = UPSCALE( to->x );
1038     arc[0].y = UPSCALE( to->y );
1039     arc[1].x = UPSCALE( control2->x );
1040     arc[1].y = UPSCALE( control2->y );
1041     arc[2].x = UPSCALE( control1->x );
1042     arc[2].y = UPSCALE( control1->y );
1043     arc[3].x = ras.x;
1044     arc[3].y = ras.y;
1045
1046     /* Short-cut the arc that crosses the current band. */
1047     min = max = arc[0].y;
1048
1049     y = arc[1].y;
1050     if ( y < min )
1051       min = y;
1052     if ( y > max )
1053       max = y;
1054
1055     y = arc[2].y;
1056     if ( y < min )
1057       min = y;
1058     if ( y > max )
1059       max = y;
1060
1061     y = arc[3].y;
1062     if ( y < min )
1063       min = y;
1064     if ( y > max )
1065       max = y;
1066
1067     if ( TRUNC( min ) >= ras.max_ey || TRUNC( max ) < ras.min_ey )
1068       goto Draw;
1069
1070     for (;;)
1071     {
1072       /* Decide whether to split or draw. See `Rapid Termination          */
1073       /* Evaluation for Recursive Subdivision of Bezier Curves' by Thomas */
1074       /* F. Hain, at                                                      */
1075       /* http://www.cis.southalabama.edu/~hain/general/Publications/Bezier/Camera-ready%20CISST02%202.pdf */
1076
1077       {
1078         TPos  dx, dy, dx_, dy_;
1079         TPos  dx1, dy1, dx2, dy2;
1080         TPos  L, s, s_limit;
1081
1082
1083         /* dx and dy are x and y components of the P0-P3 chord vector. */
1084         dx = arc[3].x - arc[0].x;
1085         dy = arc[3].y - arc[0].y;
1086
1087         /* L is an (under)estimate of the Euclidean distance P0-P3.       */
1088         /*                                                                */
1089         /* If dx >= dy, then r = sqrt(dx^2 + dy^2) can be overestimated   */
1090         /* with least maximum error by                                    */
1091         /*                                                                */
1092         /*   r_upperbound = dx + (sqrt(2) - 1) * dy  ,                    */
1093         /*                                                                */
1094         /* where sqrt(2) - 1 can be (over)estimated by 107/256, giving an */
1095         /* error of no more than 8.4%.                                    */
1096         /*                                                                */
1097         /* Similarly, some elementary calculus shows that r can be        */
1098         /* underestimated with least maximum error by                     */
1099         /*                                                                */
1100         /*   r_lowerbound = sqrt(2 + sqrt(2)) / 2 * dx                    */
1101         /*                  + sqrt(2 - sqrt(2)) / 2 * dy  .               */
1102         /*                                                                */
1103         /* 236/256 and 97/256 are (under)estimates of the two algebraic   */
1104         /* numbers, giving an error of no more than 8.1%.                 */
1105
1106         dx_ = FT_ABS( dx );
1107         dy_ = FT_ABS( dy );
1108
1109         /* This is the same as                     */
1110         /*                                         */
1111         /*   L = ( 236 * FT_MAX( dx_, dy_ )        */
1112         /*       + 97 * FT_MIN( dx_, dy_ ) ) >> 8; */
1113         L = ( dx_ > dy_ ? 236 * dx_ +  97 * dy_
1114                         :  97 * dx_ + 236 * dy_ ) >> 8;
1115
1116         /* Avoid possible arithmetic overflow below by splitting. */
1117         if ( L > 32767 )
1118           goto Split;
1119
1120         /* Max deviation may be as much as (s/L) * 3/4 (if Hain's v = 1). */
1121         s_limit = L * (TPos)( ONE_PIXEL / 6 );
1122
1123         /* s is L * the perpendicular distance from P1 to the line P0-P3. */
1124         dx1 = arc[1].x - arc[0].x;
1125         dy1 = arc[1].y - arc[0].y;
1126         s = FT_ABS( dy * dx1 - dx * dy1 );
1127
1128         if ( s > s_limit )
1129           goto Split;
1130
1131         /* s is L * the perpendicular distance from P2 to the line P0-P3. */
1132         dx2 = arc[2].x - arc[0].x;
1133         dy2 = arc[2].y - arc[0].y;
1134         s = FT_ABS( dy * dx2 - dx * dy2 );
1135
1136         if ( s > s_limit )
1137           goto Split;
1138
1139         /* Split super curvy segments where the off points are so far
1140            from the chord that the angles P0-P1-P3 or P0-P2-P3 become
1141            acute as detected by appropriate dot products. */
1142         if ( dx1 * ( dx1 - dx ) + dy1 * ( dy1 - dy ) > 0 ||
1143              dx2 * ( dx2 - dx ) + dy2 * ( dy2 - dy ) > 0 )
1144           goto Split;
1145
1146         /* No reason to split. */
1147         goto Draw;
1148       }
1149
1150     Split:
1151       gray_split_cubic( arc );
1152       arc += 3;
1153       continue;
1154
1155     Draw:
1156       gray_render_line( RAS_VAR_ arc[0].x, arc[0].y );
1157
1158       if ( arc == ras.bez_stack )
1159         return;
1160
1161       arc -= 3;
1162     }
1163   }
1164
1165
1166   static int
1167   gray_move_to( const FT_Vector*  to,
1168                 gray_PWorker      worker )
1169   {
1170     TPos  x, y;
1171
1172
1173     /* record current cell, if any */
1174     gray_record_cell( RAS_VAR );
1175
1176     /* start to a new position */
1177     x = UPSCALE( to->x );
1178     y = UPSCALE( to->y );
1179
1180     gray_start_cell( RAS_VAR_ TRUNC( x ), TRUNC( y ) );
1181
1182     worker->x = x;
1183     worker->y = y;
1184     return 0;
1185   }
1186
1187
1188   static int
1189   gray_line_to( const FT_Vector*  to,
1190                 gray_PWorker      worker )
1191   {
1192     gray_render_line( RAS_VAR_ UPSCALE( to->x ), UPSCALE( to->y ) );
1193     return 0;
1194   }
1195
1196
1197   static int
1198   gray_conic_to( const FT_Vector*  control,
1199                  const FT_Vector*  to,
1200                  gray_PWorker      worker )
1201   {
1202     gray_render_conic( RAS_VAR_ control, to );
1203     return 0;
1204   }
1205
1206
1207   static int
1208   gray_cubic_to( const FT_Vector*  control1,
1209                  const FT_Vector*  control2,
1210                  const FT_Vector*  to,
1211                  gray_PWorker      worker )
1212   {
1213     gray_render_cubic( RAS_VAR_ control1, control2, to );
1214     return 0;
1215   }
1216
1217
1218   static void
1219   gray_render_span( int             y,
1220                     int             count,
1221                     const FT_Span*  spans,
1222                     gray_PWorker    worker )
1223   {
1224     unsigned char*  p;
1225     FT_Bitmap*      map = &worker->target;
1226
1227
1228     /* first of all, compute the scanline offset */
1229     p = (unsigned char*)map->buffer - y * map->pitch;
1230     if ( map->pitch >= 0 )
1231       p += (unsigned)( ( map->rows - 1 ) * map->pitch );
1232
1233     for ( ; count > 0; count--, spans++ )
1234     {
1235       unsigned char  coverage = spans->coverage;
1236
1237
1238       if ( coverage )
1239       {
1240         /* For small-spans it is faster to do it by ourselves than
1241          * calling `memset'.  This is mainly due to the cost of the
1242          * function call.
1243          */
1244         if ( spans->len >= 8 )
1245           FT_MEM_SET( p + spans->x, (unsigned char)coverage, spans->len );
1246         else
1247         {
1248           unsigned char*  q = p + spans->x;
1249
1250
1251           switch ( spans->len )
1252           {
1253           case 7: *q++ = (unsigned char)coverage;
1254           case 6: *q++ = (unsigned char)coverage;
1255           case 5: *q++ = (unsigned char)coverage;
1256           case 4: *q++ = (unsigned char)coverage;
1257           case 3: *q++ = (unsigned char)coverage;
1258           case 2: *q++ = (unsigned char)coverage;
1259           case 1: *q   = (unsigned char)coverage;
1260           default:
1261             ;
1262           }
1263         }
1264       }
1265     }
1266   }
1267
1268
1269   static void
1270   gray_hline( RAS_ARG_ TCoord  x,
1271                        TCoord  y,
1272                        TPos    area,
1273                        TCoord  acount )
1274   {
1275     int  coverage;
1276
1277
1278     /* compute the coverage line's coverage, depending on the    */
1279     /* outline fill rule                                         */
1280     /*                                                           */
1281     /* the coverage percentage is area/(PIXEL_BITS*PIXEL_BITS*2) */
1282     /*                                                           */
1283     coverage = (int)( area >> ( PIXEL_BITS * 2 + 1 - 8 ) );
1284                                                     /* use range 0..256 */
1285     if ( coverage < 0 )
1286       coverage = -coverage;
1287
1288     if ( ras.outline.flags & FT_OUTLINE_EVEN_ODD_FILL )
1289     {
1290       coverage &= 511;
1291
1292       if ( coverage > 256 )
1293         coverage = 512 - coverage;
1294       else if ( coverage == 256 )
1295         coverage = 255;
1296     }
1297     else
1298     {
1299       /* normal non-zero winding rule */
1300       if ( coverage >= 256 )
1301         coverage = 255;
1302     }
1303
1304     y += (TCoord)ras.min_ey;
1305     x += (TCoord)ras.min_ex;
1306
1307     /* FT_Span.x is a 16-bit short, so limit our coordinates appropriately */
1308     if ( x >= 32767 )
1309       x = 32767;
1310
1311     /* FT_Span.y is an integer, so limit our coordinates appropriately */
1312     if ( y >= FT_INT_MAX )
1313       y = FT_INT_MAX;
1314
1315     if ( coverage )
1316     {
1317       FT_Span*  span;
1318       int       count;
1319
1320
1321       /* see whether we can add this span to the current list */
1322       count = ras.num_gray_spans;
1323       span  = ras.gray_spans + count - 1;
1324       if ( count > 0                          &&
1325            ras.span_y == y                    &&
1326            (int)span->x + span->len == (int)x &&
1327            span->coverage == coverage         )
1328       {
1329         span->len = (unsigned short)( span->len + acount );
1330         return;
1331       }
1332
1333       if ( ras.span_y != y || count >= FT_MAX_GRAY_SPANS )
1334       {
1335         if ( ras.render_span && count > 0 )
1336           ras.render_span( ras.span_y, count, ras.gray_spans,
1337                            ras.render_span_data );
1338
1339 #ifdef FT_DEBUG_LEVEL_TRACE
1340
1341         if ( count > 0 )
1342         {
1343           int  n;
1344
1345
1346           FT_TRACE7(( "y = %3d ", ras.span_y ));
1347           span = ras.gray_spans;
1348           for ( n = 0; n < count; n++, span++ )
1349             FT_TRACE7(( "[%d..%d]:%02x ",
1350                         span->x, span->x + span->len - 1, span->coverage ));
1351           FT_TRACE7(( "\n" ));
1352         }
1353
1354 #endif /* FT_DEBUG_LEVEL_TRACE */
1355
1356         ras.num_gray_spans = 0;
1357         ras.span_y         = (int)y;
1358
1359         count = 0;
1360         span  = ras.gray_spans;
1361       }
1362       else
1363         span++;
1364           // Fix the Vulnerability Report FoxIT Reader - MSVR-10-0077.
1365           // Limited to the value range of 'x', we have to crop it for avoid the overflow.
1366           if (x < 32768) {
1367       /* add a gray span to the current list */
1368       span->x        = (short)x;
1369       span->len      = (unsigned short)acount;
1370       span->coverage = (unsigned char)coverage;
1371
1372       ras.num_gray_spans++;
1373           }
1374     }
1375   }
1376
1377
1378 #ifdef FT_DEBUG_LEVEL_TRACE
1379
1380   /* to be called while in the debugger --                                */
1381   /* this function causes a compiler warning since it is unused otherwise */
1382   static void
1383   gray_dump_cells( RAS_ARG )
1384   {
1385     int  yindex;
1386
1387
1388     for ( yindex = 0; yindex < ras.ycount; yindex++ )
1389     {
1390       PCell  cell;
1391
1392
1393       printf( "%3d:", yindex );
1394
1395       for ( cell = ras.ycells[yindex]; cell != NULL; cell = cell->next )
1396         printf( " (%3ld, c:%4ld, a:%6d)", cell->x, cell->cover, cell->area );
1397       printf( "\n" );
1398     }
1399   }
1400
1401 #endif /* FT_DEBUG_LEVEL_TRACE */
1402
1403
1404   static void
1405   gray_sweep( RAS_ARG_ const FT_Bitmap*  target )
1406   {
1407     int  yindex;
1408
1409     FT_UNUSED( target );
1410
1411
1412     if ( ras.num_cells == 0 )
1413       return;
1414
1415     ras.num_gray_spans = 0;
1416
1417     FT_TRACE7(( "gray_sweep: start\n" ));
1418
1419     for ( yindex = 0; yindex < ras.ycount; yindex++ )
1420     {
1421       PCell   cell  = ras.ycells[yindex];
1422       TCoord  cover = 0;
1423       TCoord  x     = 0;
1424
1425
1426       for ( ; cell != NULL; cell = cell->next )
1427       {
1428         TPos  area;
1429
1430
1431         if ( cell->x > x && cover != 0 )
1432           gray_hline( RAS_VAR_ x, yindex, cover * ( ONE_PIXEL * 2 ),
1433                       cell->x - x );
1434
1435         cover += cell->cover;
1436         area   = cover * ( ONE_PIXEL * 2 ) - cell->area;
1437
1438         if ( area != 0 && cell->x >= 0 )
1439           gray_hline( RAS_VAR_ cell->x, yindex, area, 1 );
1440
1441         x = cell->x + 1;
1442       }
1443
1444       if ( cover != 0 )
1445         gray_hline( RAS_VAR_ x, yindex, cover * ( ONE_PIXEL * 2 ),
1446                     ras.count_ex - x );
1447     }
1448
1449     if ( ras.render_span && ras.num_gray_spans > 0 )
1450       ras.render_span( ras.span_y, ras.num_gray_spans,
1451                        ras.gray_spans, ras.render_span_data );
1452
1453 #ifdef FT_DEBUG_LEVEL_TRACE
1454
1455     if ( ras.num_gray_spans > 0 )
1456     {
1457       FT_Span*  span;
1458       int       n;
1459
1460
1461       FT_TRACE7(( "y = %3d ", ras.span_y ));
1462       span = ras.gray_spans;
1463       for ( n = 0; n < ras.num_gray_spans; n++, span++ )
1464         FT_TRACE7(( "[%d..%d]:%02x ",
1465                     span->x, span->x + span->len - 1, span->coverage ));
1466       FT_TRACE7(( "\n" ));
1467     }
1468
1469     FT_TRACE7(( "gray_sweep: end\n" ));
1470
1471 #endif /* FT_DEBUG_LEVEL_TRACE */
1472
1473   }
1474
1475
1476 #ifdef _STANDALONE_
1477
1478   /*************************************************************************/
1479   /*                                                                       */
1480   /*  The following function should only compile in stand-alone mode,      */
1481   /*  i.e., when building this component without the rest of FreeType.     */
1482   /*                                                                       */
1483   /*************************************************************************/
1484
1485   /*************************************************************************/
1486   /*                                                                       */
1487   /* <Function>                                                            */
1488   /*    FT_Outline_Decompose                                               */
1489   /*                                                                       */
1490   /* <Description>                                                         */
1491   /*    Walk over an outline's structure to decompose it into individual   */
1492   /*    segments and B├ęzier arcs.  This function is also able to emit      */
1493   /*    `move to' and `close to' operations to indicate the start and end  */
1494   /*    of new contours in the outline.                                    */
1495   /*                                                                       */
1496   /* <Input>                                                               */
1497   /*    outline        :: A pointer to the source target.                  */
1498   /*                                                                       */
1499   /*    func_interface :: A table of `emitters', i.e., function pointers   */
1500   /*                      called during decomposition to indicate path     */
1501   /*                      operations.                                      */
1502   /*                                                                       */
1503   /* <InOut>                                                               */
1504   /*    user           :: A typeless pointer which is passed to each       */
1505   /*                      emitter during the decomposition.  It can be     */
1506   /*                      used to store the state during the               */
1507   /*                      decomposition.                                   */
1508   /*                                                                       */
1509   /* <Return>                                                              */
1510   /*    Error code.  0 means success.                                      */
1511   /*                                                                       */
1512   static int
1513   FT_Outline_Decompose( const FT_Outline*        outline,
1514                         const FT_Outline_Funcs*  func_interface,
1515                         void*                    user )
1516   {
1517 #undef SCALED
1518 #define SCALED( x )  ( ( (x) << shift ) - delta )
1519
1520     FT_Vector   v_last;
1521     FT_Vector   v_control;
1522     FT_Vector   v_start;
1523
1524     FT_Vector*  point;
1525     FT_Vector*  limit;
1526     char*       tags;
1527
1528     int         error;
1529
1530     int   n;         /* index of contour in outline     */
1531     int   first;     /* index of first point in contour */
1532     char  tag;       /* current point's state           */
1533
1534     int   shift;
1535     TPos  delta;
1536
1537
1538     if ( !outline || !func_interface )
1539       return FT_THROW( Invalid_Argument );
1540
1541     shift = func_interface->shift;
1542     delta = func_interface->delta;
1543     first = 0;
1544
1545     for ( n = 0; n < outline->n_contours; n++ )
1546     {
1547       int  last;  /* index of last point in contour */
1548
1549
1550       FT_TRACE5(( "FT_Outline_Decompose: Outline %d\n", n ));
1551
1552       last  = outline->contours[n];
1553       if ( last < 0 )
1554         goto Invalid_Outline;
1555       limit = outline->points + last;
1556
1557       v_start   = outline->points[first];
1558       v_start.x = SCALED( v_start.x );
1559       v_start.y = SCALED( v_start.y );
1560
1561       v_last   = outline->points[last];
1562       v_last.x = SCALED( v_last.x );
1563       v_last.y = SCALED( v_last.y );
1564
1565       v_control = v_start;
1566
1567       point = outline->points + first;
1568       tags  = outline->tags   + first;
1569       tag   = FT_CURVE_TAG( tags[0] );
1570
1571       /* A contour cannot start with a cubic control point! */
1572       if ( tag == FT_CURVE_TAG_CUBIC )
1573         goto Invalid_Outline;
1574
1575       /* check first point to determine origin */
1576       if ( tag == FT_CURVE_TAG_CONIC )
1577       {
1578         /* first point is conic control.  Yes, this happens. */
1579         if ( FT_CURVE_TAG( outline->tags[last] ) == FT_CURVE_TAG_ON )
1580         {
1581           /* start at last point if it is on the curve */
1582           v_start = v_last;
1583           limit--;
1584         }
1585         else
1586         {
1587           /* if both first and last points are conic,         */
1588           /* start at their middle and record its position    */
1589           /* for closure                                      */
1590           v_start.x = ( v_start.x + v_last.x ) / 2;
1591           v_start.y = ( v_start.y + v_last.y ) / 2;
1592
1593           v_last = v_start;
1594         }
1595         point--;
1596         tags--;
1597       }
1598
1599       FT_TRACE5(( "  move to (%.2f, %.2f)\n",
1600                   v_start.x / 64.0, v_start.y / 64.0 ));
1601       error = func_interface->move_to( &v_start, user );
1602       if ( error )
1603         goto Exit;
1604
1605       while ( point < limit )
1606       {
1607         point++;
1608         tags++;
1609
1610         tag = FT_CURVE_TAG( tags[0] );
1611         switch ( tag )
1612         {
1613         case FT_CURVE_TAG_ON:  /* emit a single line_to */
1614           {
1615             FT_Vector  vec;
1616
1617
1618             vec.x = SCALED( point->x );
1619             vec.y = SCALED( point->y );
1620
1621             FT_TRACE5(( "  line to (%.2f, %.2f)\n",
1622                         vec.x / 64.0, vec.y / 64.0 ));
1623             error = func_interface->line_to( &vec, user );
1624             if ( error )
1625               goto Exit;
1626             continue;
1627           }
1628
1629         case FT_CURVE_TAG_CONIC:  /* consume conic arcs */
1630           v_control.x = SCALED( point->x );
1631           v_control.y = SCALED( point->y );
1632
1633         Do_Conic:
1634           if ( point < limit )
1635           {
1636             FT_Vector  vec;
1637             FT_Vector  v_middle;
1638
1639
1640             point++;
1641             tags++;
1642             tag = FT_CURVE_TAG( tags[0] );
1643
1644             vec.x = SCALED( point->x );
1645             vec.y = SCALED( point->y );
1646
1647             if ( tag == FT_CURVE_TAG_ON )
1648             {
1649               FT_TRACE5(( "  conic to (%.2f, %.2f)"
1650                           " with control (%.2f, %.2f)\n",
1651                           vec.x / 64.0, vec.y / 64.0,
1652                           v_control.x / 64.0, v_control.y / 64.0 ));
1653               error = func_interface->conic_to( &v_control, &vec, user );
1654               if ( error )
1655                 goto Exit;
1656               continue;
1657             }
1658
1659             if ( tag != FT_CURVE_TAG_CONIC )
1660               goto Invalid_Outline;
1661
1662             v_middle.x = ( v_control.x + vec.x ) / 2;
1663             v_middle.y = ( v_control.y + vec.y ) / 2;
1664
1665             FT_TRACE5(( "  conic to (%.2f, %.2f)"
1666                         " with control (%.2f, %.2f)\n",
1667                         v_middle.x / 64.0, v_middle.y / 64.0,
1668                         v_control.x / 64.0, v_control.y / 64.0 ));
1669             error = func_interface->conic_to( &v_control, &v_middle, user );
1670             if ( error )
1671               goto Exit;
1672
1673             v_control = vec;
1674             goto Do_Conic;
1675           }
1676
1677           FT_TRACE5(( "  conic to (%.2f, %.2f)"
1678                       " with control (%.2f, %.2f)\n",
1679                       v_start.x / 64.0, v_start.y / 64.0,
1680                       v_control.x / 64.0, v_control.y / 64.0 ));
1681           error = func_interface->conic_to( &v_control, &v_start, user );
1682           goto Close;
1683
1684         default:  /* FT_CURVE_TAG_CUBIC */
1685           {
1686             FT_Vector  vec1, vec2;
1687
1688
1689             if ( point + 1 > limit                             ||
1690                  FT_CURVE_TAG( tags[1] ) != FT_CURVE_TAG_CUBIC )
1691               goto Invalid_Outline;
1692
1693             point += 2;
1694             tags  += 2;
1695
1696             vec1.x = SCALED( point[-2].x );
1697             vec1.y = SCALED( point[-2].y );
1698
1699             vec2.x = SCALED( point[-1].x );
1700             vec2.y = SCALED( point[-1].y );
1701
1702             if ( point <= limit )
1703             {
1704               FT_Vector  vec;
1705
1706
1707               vec.x = SCALED( point->x );
1708               vec.y = SCALED( point->y );
1709
1710               FT_TRACE5(( "  cubic to (%.2f, %.2f)"
1711                           " with controls (%.2f, %.2f) and (%.2f, %.2f)\n",
1712                           vec.x / 64.0, vec.y / 64.0,
1713                           vec1.x / 64.0, vec1.y / 64.0,
1714                           vec2.x / 64.0, vec2.y / 64.0 ));
1715               error = func_interface->cubic_to( &vec1, &vec2, &vec, user );
1716               if ( error )
1717                 goto Exit;
1718               continue;
1719             }
1720
1721             FT_TRACE5(( "  cubic to (%.2f, %.2f)"
1722                         " with controls (%.2f, %.2f) and (%.2f, %.2f)\n",
1723                         v_start.x / 64.0, v_start.y / 64.0,
1724                         vec1.x / 64.0, vec1.y / 64.0,
1725                         vec2.x / 64.0, vec2.y / 64.0 ));
1726             error = func_interface->cubic_to( &vec1, &vec2, &v_start, user );
1727             goto Close;
1728           }
1729         }
1730       }
1731
1732       /* close the contour with a line segment */
1733       FT_TRACE5(( "  line to (%.2f, %.2f)\n",
1734                   v_start.x / 64.0, v_start.y / 64.0 ));
1735       error = func_interface->line_to( &v_start, user );
1736
1737    Close:
1738       if ( error )
1739         goto Exit;
1740
1741       first = last + 1;
1742     }
1743
1744     FT_TRACE5(( "FT_Outline_Decompose: Done\n", n ));
1745     return 0;
1746
1747   Exit:
1748     FT_TRACE5(( "FT_Outline_Decompose: Error %d\n", error ));
1749     return error;
1750
1751   Invalid_Outline:
1752     return FT_THROW( Invalid_Outline );
1753   }
1754
1755 #endif /* _STANDALONE_ */
1756
1757
1758   typedef struct  gray_TBand_
1759   {
1760     TPos  min, max;
1761
1762   } gray_TBand;
1763
1764     FT_DEFINE_OUTLINE_FUNCS(func_interface,
1765       (FT_Outline_MoveTo_Func) gray_move_to,
1766       (FT_Outline_LineTo_Func) gray_line_to,
1767       (FT_Outline_ConicTo_Func)gray_conic_to,
1768       (FT_Outline_CubicTo_Func)gray_cubic_to,
1769       0,
1770       0
1771     )
1772
1773   static int
1774   gray_convert_glyph_inner( RAS_ARG )
1775   {
1776
1777     volatile int  error = 0;
1778
1779 #ifdef FT_CONFIG_OPTION_PIC
1780       FT_Outline_Funcs func_interface;
1781       Init_Class_func_interface(&func_interface);
1782 #endif
1783 #ifndef _FX_MANAGED_CODE_    
1784     if ( ft_setjmp( ras.jump_buffer ) == 0 )
1785     {
1786 #endif
1787       error = FT_Outline_Decompose( &ras.outline, &func_interface, &ras );
1788       gray_record_cell( RAS_VAR );
1789 #ifndef _FX_MANAGED_CODE_ 
1790         }
1791     else
1792       error = FT_THROW( Memory_Overflow );
1793 #endif
1794     return error;
1795   }
1796
1797
1798   static int
1799   gray_convert_glyph( RAS_ARG )
1800   {
1801     gray_TBand            bands[40];
1802     gray_TBand* volatile  band;
1803     int volatile          n, num_bands;
1804     TPos volatile         min, max, max_y;
1805     FT_BBox*              clip;
1806
1807
1808     /* Set up state in the raster object */
1809     gray_compute_cbox( RAS_VAR );
1810
1811     /* clip to target bitmap, exit if nothing to do */
1812     clip = &ras.clip_box;
1813
1814     if ( ras.max_ex <= clip->xMin || ras.min_ex >= clip->xMax ||
1815          ras.max_ey <= clip->yMin || ras.min_ey >= clip->yMax )
1816       return 0;
1817
1818     if ( ras.min_ex < clip->xMin ) ras.min_ex = clip->xMin;
1819     if ( ras.min_ey < clip->yMin ) ras.min_ey = clip->yMin;
1820
1821     if ( ras.max_ex > clip->xMax ) ras.max_ex = clip->xMax;
1822     if ( ras.max_ey > clip->yMax ) ras.max_ey = clip->yMax;
1823
1824     ras.count_ex = ras.max_ex - ras.min_ex;
1825     ras.count_ey = ras.max_ey - ras.min_ey;
1826
1827     /* set up vertical bands */
1828     num_bands = (int)( ( ras.max_ey - ras.min_ey ) / ras.band_size );
1829     if ( num_bands == 0 )
1830       num_bands = 1;
1831     if ( num_bands >= 39 )
1832       num_bands = 39;
1833
1834     ras.band_shoot = 0;
1835
1836     min   = ras.min_ey;
1837     max_y = ras.max_ey;
1838
1839     for ( n = 0; n < num_bands; n++, min = max )
1840     {
1841       max = min + ras.band_size;
1842       if ( n == num_bands - 1 || max > max_y )
1843         max = max_y;
1844
1845       bands[0].min = min;
1846       bands[0].max = max;
1847       band         = bands;
1848
1849       while ( band >= bands )
1850       {
1851         TPos  bottom, top, middle;
1852         int   error;
1853
1854         {
1855           PCell  cells_max;
1856           int    yindex;
1857           long   cell_start, cell_end, cell_mod;
1858
1859
1860           ras.ycells = (PCell*)ras.buffer;
1861           ras.ycount = band->max - band->min;
1862
1863           cell_start = sizeof ( PCell ) * ras.ycount;
1864           cell_mod   = cell_start % sizeof ( TCell );
1865           if ( cell_mod > 0 )
1866             cell_start += sizeof ( TCell ) - cell_mod;
1867
1868           cell_end  = ras.buffer_size;
1869           cell_end -= cell_end % sizeof ( TCell );
1870
1871           cells_max = (PCell)( (char*)ras.buffer + cell_end );
1872           ras.cells = (PCell)( (char*)ras.buffer + cell_start );
1873           if ( ras.cells >= cells_max )
1874             goto ReduceBands;
1875
1876           ras.max_cells = cells_max - ras.cells;
1877           if ( ras.max_cells < 2 )
1878             goto ReduceBands;
1879
1880           for ( yindex = 0; yindex < ras.ycount; yindex++ )
1881             ras.ycells[yindex] = NULL;
1882         }
1883
1884         ras.num_cells = 0;
1885         ras.invalid   = 1;
1886         ras.min_ey    = band->min;
1887         ras.max_ey    = band->max;
1888         ras.count_ey  = band->max - band->min;
1889
1890         error = gray_convert_glyph_inner( RAS_VAR );
1891
1892         if ( !error )
1893         {
1894           gray_sweep( RAS_VAR_ &ras.target );
1895           band--;
1896           continue;
1897         }
1898         else if ( error != ErrRaster_Memory_Overflow )
1899           return 1;
1900
1901       ReduceBands:
1902         /* render pool overflow; we will reduce the render band by half */
1903         bottom = band->min;
1904         top    = band->max;
1905         middle = bottom + ( ( top - bottom ) >> 1 );
1906
1907         /* This is too complex for a single scanline; there must */
1908         /* be some problems.                                     */
1909         if ( middle == bottom )
1910         {
1911 #ifdef FT_DEBUG_LEVEL_TRACE
1912           FT_TRACE7(( "gray_convert_glyph: rotten glyph\n" ));
1913 #endif
1914           return 1;
1915         }
1916
1917         if ( bottom-top >= ras.band_size )
1918           ras.band_shoot++;
1919
1920         band[1].min = bottom;
1921         band[1].max = middle;
1922         band[0].min = middle;
1923         band[0].max = top;
1924         band++;
1925       }
1926     }
1927
1928     if ( ras.band_shoot > 8 && ras.band_size > 16 )
1929       ras.band_size = ras.band_size / 2;
1930
1931     return 0;
1932   }
1933
1934
1935   static int
1936   gray_raster_render( gray_PRaster             raster,
1937                       const FT_Raster_Params*  params )
1938   {
1939     const FT_Outline*  outline    = (const FT_Outline*)params->source;
1940     const FT_Bitmap*   target_map = params->target;
1941     gray_PWorker       worker;
1942
1943
1944     if ( !raster || !raster->buffer || !raster->buffer_size )
1945       return FT_THROW( Invalid_Argument );
1946
1947     if ( !outline )
1948       return FT_THROW( Invalid_Outline );
1949
1950     /* return immediately if the outline is empty */
1951     if ( outline->n_points == 0 || outline->n_contours <= 0 )
1952       return 0;
1953
1954     if ( !outline->contours || !outline->points )
1955       return FT_THROW( Invalid_Outline );
1956
1957     if ( outline->n_points !=
1958            outline->contours[outline->n_contours - 1] + 1 )
1959       return FT_THROW( Invalid_Outline );
1960
1961     worker = raster->worker;
1962
1963     /* if direct mode is not set, we must have a target bitmap */
1964     if ( !( params->flags & FT_RASTER_FLAG_DIRECT ) )
1965     {
1966       if ( !target_map )
1967         return FT_THROW( Invalid_Argument );
1968
1969       /* nothing to do */
1970       if ( !target_map->width || !target_map->rows )
1971         return 0;
1972
1973       if ( !target_map->buffer )
1974         return FT_THROW( Invalid_Argument );
1975     }
1976
1977     /* this version does not support monochrome rendering */
1978     if ( !( params->flags & FT_RASTER_FLAG_AA ) )
1979       return FT_THROW( Invalid_Mode );
1980
1981     /* compute clipping box */
1982     if ( !( params->flags & FT_RASTER_FLAG_DIRECT ) )
1983     {
1984       /* compute clip box from target pixmap */
1985       ras.clip_box.xMin = 0;
1986       ras.clip_box.yMin = 0;
1987       ras.clip_box.xMax = target_map->width;
1988       ras.clip_box.yMax = target_map->rows;
1989     }
1990     else if ( params->flags & FT_RASTER_FLAG_CLIP )
1991       ras.clip_box = params->clip_box;
1992     else
1993     {
1994       ras.clip_box.xMin = -32768L;
1995       ras.clip_box.yMin = -32768L;
1996       ras.clip_box.xMax =  32767L;
1997       ras.clip_box.yMax =  32767L;
1998     }
1999
2000     gray_init_cells( RAS_VAR_ raster->buffer, raster->buffer_size );
2001
2002     ras.outline        = *outline;
2003     ras.num_cells      = 0;
2004     ras.invalid        = 1;
2005     ras.band_size      = raster->band_size;
2006     ras.num_gray_spans = 0;
2007
2008     if ( params->flags & FT_RASTER_FLAG_DIRECT )
2009     {
2010       ras.render_span      = (FT_Raster_Span_Func)params->gray_spans;
2011       ras.render_span_data = params->user;
2012     }
2013     else
2014     {
2015       ras.target           = *target_map;
2016       ras.render_span      = (FT_Raster_Span_Func)gray_render_span;
2017       ras.render_span_data = &ras;
2018     }
2019
2020     return gray_convert_glyph( RAS_VAR );
2021   }
2022
2023
2024   /**** RASTER OBJECT CREATION: In stand-alone mode, we simply use *****/
2025   /****                         a static object.                   *****/
2026
2027 #ifdef _STANDALONE_
2028
2029   static int
2030   gray_raster_new( void*       memory,
2031                    FT_Raster*  araster )
2032   {
2033     static gray_TRaster  the_raster;
2034
2035     FT_UNUSED( memory );
2036
2037
2038     *araster = (FT_Raster)&the_raster;
2039     FT_MEM_ZERO( &the_raster, sizeof ( the_raster ) );
2040
2041     return 0;
2042   }
2043
2044
2045   static void
2046   gray_raster_done( FT_Raster  raster )
2047   {
2048     /* nothing */
2049     FT_UNUSED( raster );
2050   }
2051
2052 #else /* !_STANDALONE_ */
2053
2054   static int
2055   gray_raster_new( FT_Memory   memory,
2056                    FT_Raster*  araster )
2057   {
2058     FT_Error      error;
2059     gray_PRaster  raster = NULL;
2060
2061
2062     *araster = 0;
2063     if ( !FT_ALLOC( raster, sizeof ( gray_TRaster ) ) )
2064     {
2065       raster->memory = memory;
2066       *araster       = (FT_Raster)raster;
2067     }
2068
2069     return error;
2070   }
2071
2072
2073   static void
2074   gray_raster_done( FT_Raster  raster )
2075   {
2076     FT_Memory  memory = (FT_Memory)((gray_PRaster)raster)->memory;
2077
2078
2079     FT_FREE( raster );
2080   }
2081
2082 #endif /* !_STANDALONE_ */
2083
2084
2085   static void
2086   gray_raster_reset( FT_Raster  raster,
2087                      char*      pool_base,
2088                      long       pool_size )
2089   {
2090     gray_PRaster  rast = (gray_PRaster)raster;
2091
2092
2093     if ( raster )
2094     {
2095       if ( pool_base && pool_size >= (long)sizeof ( gray_TWorker ) + 2048 )
2096       {
2097         gray_PWorker  worker = (gray_PWorker)pool_base;
2098
2099
2100         rast->worker      = worker;
2101         rast->buffer      = pool_base +
2102                               ( ( sizeof ( gray_TWorker ) +
2103                                   sizeof ( TCell ) - 1 )  &
2104                                 ~( sizeof ( TCell ) - 1 ) );
2105         rast->buffer_size = (long)( ( pool_base + pool_size ) -
2106                                     (char*)rast->buffer ) &
2107                                       ~( sizeof ( TCell ) - 1 );
2108         rast->band_size   = (int)( rast->buffer_size /
2109                                      ( sizeof ( TCell ) * 8 ) );
2110       }
2111       else
2112       {
2113         rast->buffer      = NULL;
2114         rast->buffer_size = 0;
2115         rast->worker      = NULL;
2116       }
2117     }
2118   }
2119
2120
2121   FT_DEFINE_RASTER_FUNCS(ft_grays_raster,
2122     FT_GLYPH_FORMAT_OUTLINE,
2123
2124     (FT_Raster_New_Func)     gray_raster_new,
2125     (FT_Raster_Reset_Func)   gray_raster_reset,
2126     (FT_Raster_Set_Mode_Func)0,
2127     (FT_Raster_Render_Func)  gray_raster_render,
2128     (FT_Raster_Done_Func)    gray_raster_done
2129   )
2130
2131
2132 /* END */
2133
2134
2135 /* Local Variables: */
2136 /* coding: utf-8    */
2137 /* End:             */