src/gui/painting/qgrayraster.c

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
   4 ** Contact: http://www.qt-project.org/
   5 **
   6 ** This file is part of the QtGui module of the Qt Toolkit.
   7 **
   8 ** $QT_BEGIN_LICENSE:LGPL$
   9 ** GNU Lesser General Public License Usage
  10 ** This file may be used under the terms of the GNU Lesser General Public
  11 ** License version 2.1 as published by the Free Software Foundation and
  12 ** appearing in the file LICENSE.LGPL included in the packaging of this
  13 ** file. Please review the following information to ensure the GNU Lesser
  14 ** General Public License version 2.1 requirements will be met:
  15 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  16 **
  17 ** In addition, as a special exception, Nokia gives you certain additional
  18 ** rights. These rights are described in the Nokia Qt LGPL Exception
  19 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  20 **
  21 ** GNU General Public License Usage
  22 ** Alternatively, this file may be used under the terms of the GNU General
  23 ** Public License version 3.0 as published by the Free Software Foundation
  24 ** and appearing in the file LICENSE.GPL included in the packaging of this
  25 ** file. Please review the following information to ensure the GNU General
  26 ** Public License version 3.0 requirements will be met:
  27 ** http://www.gnu.org/copyleft/gpl.html.
  28 **
  29 ** Other Usage
  30 ** Alternatively, this file may be used in accordance with the terms and
  31 ** conditions contained in a signed written agreement between you and Nokia.
  32 **
  33 **
  34 **
  35 **
  36 **
  37 **
  38 ** $QT_END_LICENSE$
  39 **
  40 ****************************************************************************/
  41
  42 /***************************************************************************/
  43 /*                                                                         */
  44 /*  qgrayraster.c, derived from ftgrays.c                                  */
  45 /*                                                                         */
  46 /*    A new `perfect' anti-aliasing renderer (body).                       */
  47 /*                                                                         */
  48 /*  Copyright 2000-2001, 2002, 2003 by                                     */
  49 /*  David Turner, Robert Wilhelm, and Werner Lemberg.                      */
  50 /*                                                                         */
  51 /*  This file is part of the FreeType project, and may only be used,       */
  52 /*  modified, and distributed under the terms of the FreeType project      */
  53 /*  license, ../../3rdparty/freetype/docs/FTL.TXT.  By continuing to use,  */
  54 /*  modify, or distribute this file you indicate that you have read        */
  55 /*  the license and understand and accept it fully.                        */
  56 /*                                                                         */
  57 /***************************************************************************/
  58
  59   /*************************************************************************/
  60   /*                                                                       */
  61   /* This file can be compiled without the rest of the FreeType engine, by */
  62   /* defining the _STANDALONE_ macro when compiling it.  You also need to  */
  63   /* put the files `ftgrays.h' and `ftimage.h' into the current            */
  64   /* compilation directory.  Typically, you could do something like        */
  65   /*                                                                       */
  66   /* - copy `src/smooth/ftgrays.c' (this file) to your current directory   */
  67   /*                                                                       */
  68   /* - copy `include/freetype/ftimage.h' and `src/smooth/ftgrays.h' to the */
  69   /*   same directory                                                      */
  70   /*                                                                       */
  71   /* - compile `ftgrays' with the _STANDALONE_ macro defined, as in        */
  72   /*                                                                       */
  73   /*     cc -c -D_STANDALONE_ ftgrays.c                                    */
  74   /*                                                                       */
  75   /* The renderer can be initialized with a call to                        */
  76   /* `qt_ft_gray_raster.raster_new'; an anti-aliased bitmap can be generated  */
  77   /* with a call to `qt_ft_gray_raster.raster_render'.                        */
  78   /*                                                                       */
  79   /* See the comments and documentation in the file `ftimage.h' for more   */
  80   /* details on how the raster works.                                      */
  81   /*                                                                       */
  82   /*************************************************************************/
  83
  84   /*************************************************************************/
  85   /*                                                                       */
  86   /* This is a new anti-aliasing scan-converter for FreeType 2.  The       */
  87   /* algorithm used here is _very_ different from the one in the standard  */
  88   /* `ftraster' module.  Actually, `ftgrays' computes the _exact_          */
  89   /* coverage of the outline on each pixel cell.                           */
  90   /*                                                                       */
  91   /* It is based on ideas that I initially found in Raph Levien's          */
  92   /* excellent LibArt graphics library (see http://www.levien.com/libart   */
  93   /* for more information, though the web pages do not tell anything       */
  94   /* about the renderer; you'll have to dive into the source code to       */
  95   /* understand how it works).                                             */
  96   /*                                                                       */
  97   /* Note, however, that this is a _very_ different implementation         */
  98   /* compared to Raph's.  Coverage information is stored in a very         */
  99   /* different way, and I don't use sorted vector paths.  Also, it doesn't */
 100   /* use floating point values.                                            */
 101   /*                                                                       */
 102   /* This renderer has the following advantages:                           */
 103   /*                                                                       */
 104   /* - It doesn't need an intermediate bitmap.  Instead, one can supply a  */
 105   /*   callback function that will be called by the renderer to draw gray  */
 106   /*   spans on any target surface.  You can thus do direct composition on */
 107   /*   any kind of bitmap, provided that you give the renderer the right   */
 108   /*   callback.                                                           */
 109   /*                                                                       */
 110   /* - A perfect anti-aliaser, i.e., it computes the _exact_ coverage on   */
 111   /*   each pixel cell.                                                    */
 112   /*                                                                       */
 113   /* - It performs a single pass on the outline (the `standard' FT2        */
 114   /*   renderer makes two passes).                                         */
 115   /*                                                                       */
 116   /* - It can easily be modified to render to _any_ number of gray levels  */
 117   /*   cheaply.                                                            */
 118   /*                                                                       */
 119   /* - For small (< 20) pixel sizes, it is faster than the standard        */
 120   /*   renderer.                                                           */
 121   /*                                                                       */
 122   /*************************************************************************/
 123
 124 /* experimental support for gamma correction within the rasterizer */
 125 #define xxxGRAYS_USE_GAMMA
 126
 127
 128   /*************************************************************************/
 129   /*                                                                       */
 130   /* The macro QT_FT_COMPONENT is used in trace mode.  It is an implicit      */
 131   /* parameter of the QT_FT_TRACE() and QT_FT_ERROR() macros, used to print/log  */
 132   /* messages during execution.                                            */
 133   /*                                                                       */
 134 #undef  QT_FT_COMPONENT
 135 #define QT_FT_COMPONENT  trace_smooth
 136
 137
 138 #define ErrRaster_MemoryOverflow   -4
 139
 140 #if defined(VXWORKS)
 141 #  include <vxWorksCommon.h>    /* needed for setjmp.h */
 142 #endif
 143 #include <string.h>             /* for qt_ft_memcpy() */
 144 #include <setjmp.h>
 145 #include <limits.h>
 146
 147 #define QT_FT_UINT_MAX  UINT_MAX
 148
 149 #define qt_ft_memset   memset
 150
 151 #define qt_ft_setjmp   setjmp
 152 #define qt_ft_longjmp  longjmp
 153 #define qt_ft_jmp_buf  jmp_buf
 154
 155 #define ErrRaster_Invalid_Mode      -2
 156 #define ErrRaster_Invalid_Outline   -1
 157 #define ErrRaster_Invalid_Argument  -3
 158 #define ErrRaster_Memory_Overflow   -4
 159 #define ErrRaster_OutOfMemory       -6
 160
 161 #define QT_FT_BEGIN_HEADER
 162 #define QT_FT_END_HEADER
 163
 164 #include <private/qrasterdefs_p.h>
 165 #include <private/qgrayraster_p.h>
 166
 167 #include <stdlib.h>
 168 #include <stdio.h>
 169
 170   /* This macro is used to indicate that a function parameter is unused. */
 171   /* Its purpose is simply to reduce compiler warnings.  Note also that  */
 172   /* simply defining it as `(void)x' doesn't avoid warnings with certain */
 173   /* ANSI compilers (e.g. LCC).                                          */
 174 #define QT_FT_UNUSED( x )  (x) = (x)
 175
 176   /* Disable the tracing mechanism for simplicity -- developers can      */
 177   /* activate it easily by redefining these two macros.                  */
 178 #ifndef QT_FT_ERROR
 179 #define QT_FT_ERROR( x )  do ; while ( 0 )     /* nothing */
 180 #endif
 181
 182 #ifndef QT_FT_TRACE
 183 #define QT_FT_TRACE( x )  do ; while ( 0 )     /* nothing */
 184 #endif
 185
 186 #ifndef QT_FT_MEM_SET
 187 #define QT_FT_MEM_SET( d, s, c )  qt_ft_memset( d, s, c )
 188 #endif
 189
 190 #ifndef QT_FT_MEM_ZERO
 191 #define QT_FT_MEM_ZERO( dest, count )  QT_FT_MEM_SET( dest, 0, count )
 192 #endif
 193
 194   /* define this to dump debugging information */
 195 #define xxxDEBUG_GRAYS
 196
 197
 198 #define RAS_ARG   PWorker  worker
 199 #define RAS_ARG_  PWorker  worker,
 200
 201 #define RAS_VAR   worker
 202 #define RAS_VAR_  worker,
 203
 204 #define ras       (*worker)
 205
 206
 207   /* must be at least 6 bits! */
 208 #define PIXEL_BITS  8
 209
 210 #define ONE_PIXEL       ( 1L << PIXEL_BITS )
 211 #define PIXEL_MASK      ( -1L << PIXEL_BITS )
 212 #define TRUNC( x )      ( (TCoord)( (x) >> PIXEL_BITS ) )
 213 #define SUBPIXELS( x )  ( (TPos)(x) << PIXEL_BITS )
 214 #define FLOOR( x )      ( (x) & -ONE_PIXEL )
 215 #define CEILING( x )    ( ( (x) + ONE_PIXEL - 1 ) & -ONE_PIXEL )
 216 #define ROUND( x )      ( ( (x) + ONE_PIXEL / 2 ) & -ONE_PIXEL )
 217
 218 #if PIXEL_BITS >= 6
 219 #define UPSCALE( x )    ( (x) << ( PIXEL_BITS - 6 ) )
 220 #define DOWNSCALE( x )  ( (x) >> ( PIXEL_BITS - 6 ) )
 221 #else
 222 #define UPSCALE( x )    ( (x) >> ( 6 - PIXEL_BITS ) )
 223 #define DOWNSCALE( x )  ( (x) << ( 6 - PIXEL_BITS ) )
 224 #endif
 225
 226   /*************************************************************************/
 227   /*                                                                       */
 228   /*   TYPE DEFINITIONS                                                    */
 229   /*                                                                       */
 230
 231   /* don't change the following types to QT_FT_Int or QT_FT_Pos, since we might */
 232   /* need to define them to "float" or "double" when experimenting with   */
 233   /* new algorithms                                                       */
 234
 235   typedef int   TCoord;   /* integer scanline/pixel coordinate */
 236   typedef int   TPos;     /* sub-pixel coordinate              */
 237
 238   /* determine the type used to store cell areas.  This normally takes at */
 239   /* least PIXEL_BITS*2 + 1 bits.  On 16-bit systems, we need to use      */
 240   /* `long' instead of `int', otherwise bad things happen                 */
 241
 242 #if PIXEL_BITS <= 7
 243
 244   typedef int  TArea;
 245
 246 #else /* PIXEL_BITS >= 8 */
 247
 248   /* approximately determine the size of integers using an ANSI-C header */
 249 #if QT_FT_UINT_MAX == 0xFFFFU
 250   typedef long  TArea;
 251 #else
 252   typedef int   TArea;
 253 #endif
 254
 255 #endif /* PIXEL_BITS >= 8 */
 256
 257
 258   /* maximal number of gray spans in a call to the span callback */
 259 #define QT_FT_MAX_GRAY_SPANS  256
 260
 261
 262   typedef struct TCell_*  PCell;
 263
 264   typedef struct  TCell_
 265   {
 266     int    x;
 267     int    cover;
 268     TArea  area;
 269     PCell  next;
 270
 271   } TCell;
 272
 273
 274   typedef struct  TWorker_
 275   {
 276     TCoord  ex, ey;
 277     TPos    min_ex, max_ex;
 278     TPos    min_ey, max_ey;
 279     TPos    count_ex, count_ey;
 280
 281     TArea   area;
 282     int     cover;
 283     int     invalid;
 284
 285     PCell   cells;
 286     int     max_cells;
 287     int     num_cells;
 288
 289     TCoord  cx, cy;
 290     TPos    x,  y;
 291
 292     TPos    last_ey;
 293
 294     QT_FT_Vector   bez_stack[32 * 3 + 1];
 295     int         lev_stack[32];
 296
 297     QT_FT_Outline  outline;
 298     QT_FT_Bitmap   target;
 299     QT_FT_BBox     clip_box;
 300
 301     QT_FT_Span     gray_spans[QT_FT_MAX_GRAY_SPANS];
 302     int         num_gray_spans;
 303
 304     QT_FT_Raster_Span_Func  render_span;
 305     void*                render_span_data;
 306
 307     int  band_size;
 308     int  band_shoot;
 309     int  conic_level;
 310     int  cubic_level;
 311
 312     qt_ft_jmp_buf  jump_buffer;
 313
 314     void*       buffer;
 315     long        buffer_size;
 316
 317     PCell*     ycells;
 318     int        ycount;
 319
 320     int        skip_spans;
 321   } TWorker, *PWorker;
 322
 323
 324   typedef struct TRaster_
 325   {
 326     void*    buffer;
 327     long     buffer_size;
 328     long     buffer_allocated_size;
 329     int      band_size;
 330     void*    memory;
 331     PWorker  worker;
 332
 333   } TRaster, *PRaster;
 334
 335   int q_gray_rendered_spans(TRaster *raster)
 336   {
 337     if ( raster && raster->worker )
 338       return raster->worker->skip_spans > 0 ? 0 : -raster->worker->skip_spans;
 339     return 0;
 340   }
 341
 342   /*************************************************************************/
 343   /*                                                                       */
 344   /* Initialize the cells table.                                           */
 345   /*                                                                       */
 346   static void
 347   gray_init_cells( RAS_ARG_ void*  buffer,
 348                    long            byte_size )
 349   {
 350     ras.buffer      = buffer;
 351     ras.buffer_size = byte_size;
 352
 353     ras.ycells      = (PCell*) buffer;
 354     ras.cells       = NULL;
 355     ras.max_cells   = 0;
 356     ras.num_cells   = 0;
 357     ras.area        = 0;
 358     ras.cover       = 0;
 359     ras.invalid     = 1;
 360   }
 361
 362
 363   /*************************************************************************/
 364   /*                                                                       */
 365   /* Compute the outline bounding box.                                     */
 366   /*                                                                       */
 367   static void
 368   gray_compute_cbox( RAS_ARG )
 369   {
 370     QT_FT_Outline*  outline = &ras.outline;
 371     QT_FT_Vector*   vec     = outline->points;
 372     QT_FT_Vector*   limit   = vec + outline->n_points;
 373
 374
 375     if ( outline->n_points <= 0 )
 376     {
 377       ras.min_ex = ras.max_ex = 0;
 378       ras.min_ey = ras.max_ey = 0;
 379       return;
 380     }
 381
 382     ras.min_ex = ras.max_ex = vec->x;
 383     ras.min_ey = ras.max_ey = vec->y;
 384
 385     vec++;
 386
 387     for ( ; vec < limit; vec++ )
 388     {
 389       TPos  x = vec->x;
 390       TPos  y = vec->y;
 391
 392
 393       if ( x < ras.min_ex ) ras.min_ex = x;
 394       if ( x > ras.max_ex ) ras.max_ex = x;
 395       if ( y < ras.min_ey ) ras.min_ey = y;
 396       if ( y > ras.max_ey ) ras.max_ey = y;
 397     }
 398
 399     /* truncate the bounding box to integer pixels */
 400     ras.min_ex = ras.min_ex >> 6;
 401     ras.min_ey = ras.min_ey >> 6;
 402     ras.max_ex = ( ras.max_ex + 63 ) >> 6;
 403     ras.max_ey = ( ras.max_ey + 63 ) >> 6;
 404   }
 405
 406
 407   /*************************************************************************/
 408   /*                                                                       */
 409   /* Record the current cell in the table.                                 */
 410   /*                                                                       */
 411   static void
 412   gray_record_cell( RAS_ARG )
 413   {
 414     PCell  *pcell, cell;
 415     int     x = ras.ex;
 416
 417     if ( ras.invalid || !( ras.area | ras.cover ) )
 418         return;
 419
 420     if ( x > ras.max_ex )
 421       x = ras.max_ex;
 422
 423     pcell = &ras.ycells[ras.ey];
 424
 425     for (;;)
 426     {
 427       cell = *pcell;
 428       if ( cell == NULL || cell->x > x )
 429         break;
 430
 431       if ( cell->x == x ) {
 432           cell->area  += ras.area;
 433           cell->cover += ras.cover;
 434           return;
 435       }
 436
 437       pcell = &cell->next;
 438     }
 439
 440     if ( ras.num_cells >= ras.max_cells )
 441       qt_ft_longjmp( ras.jump_buffer, 1 );
 442
 443     cell        = ras.cells + ras.num_cells++;
 444     cell->x     = x;
 445     cell->area  = ras.area;
 446     cell->cover = ras.cover;
 447
 448     cell->next  = *pcell;
 449     *pcell      = cell;
 450   }
 451
 452
 453   /*************************************************************************/
 454   /*                                                                       */
 455   /* Set the current cell to a new position.                               */
 456   /*                                                                       */
 457   static void
 458   gray_set_cell( RAS_ARG_ TCoord  ex,
 459                           TCoord  ey )
 460   {
 461     /* Move the cell pointer to a new position.  We set the `invalid'      */
 462     /* flag to indicate that the cell isn't part of those we're interested */
 463     /* in during the render phase.  This means that:                       */
 464     /*                                                                     */
 465     /* . the new vertical position must be within min_ey..max_ey-1.        */
 466     /* . the new horizontal position must be strictly less than max_ex     */
 467     /*                                                                     */
 468     /* Note that if a cell is to the left of the clipping region, it is    */
 469     /* actually set to the (min_ex-1) horizontal position.                 */
 470
 471     /* All cells that are on the left of the clipping region go to the */
 472     /* min_ex - 1 horizontal position.                                 */
 473     ey -= ras.min_ey;
 474
 475     if ( ex > ras.max_ex )
 476       ex = ras.max_ex;
 477
 478     ex -= ras.min_ex;
 479     if ( ex < 0 )
 480       ex = -1;
 481
 482     /* are we moving to a different cell ? */
 483     if ( ex != ras.ex || ey != ras.ey )
 484     {
 485       /* record the current one if it is valid */
 486       if ( !ras.invalid )
 487         gray_record_cell( RAS_VAR );
 488
 489       ras.area  = 0;
 490       ras.cover = 0;
 491     }
 492
 493     ras.ex      = ex;
 494     ras.ey      = ey;
 495     ras.invalid = ( (unsigned)ey >= (unsigned)ras.count_ey ||
 496                               ex >= ras.count_ex           );
 497   }
 498
 499
 500   /*************************************************************************/
 501   /*                                                                       */
 502   /* Start a new contour at a given cell.                                  */
 503   /*                                                                       */
 504   static void
 505   gray_start_cell( RAS_ARG_ TCoord  ex,
 506                             TCoord  ey )
 507   {
 508     if ( ex > ras.max_ex )
 509       ex = (TCoord)( ras.max_ex );
 510
 511     if ( ex < ras.min_ex )
 512       ex = (TCoord)( ras.min_ex - 1 );
 513
 514     ras.area    = 0;
 515     ras.cover   = 0;
 516     ras.ex      = ex - ras.min_ex;
 517     ras.ey      = ey - ras.min_ey;
 518     ras.last_ey = SUBPIXELS( ey );
 519     ras.invalid = 0;
 520
 521     gray_set_cell( RAS_VAR_ ex, ey );
 522   }
 523
 524
 525   /*************************************************************************/
 526   /*                                                                       */
 527   /* Render a scanline as one or more cells.                               */
 528   /*                                                                       */
 529   static void
 530   gray_render_scanline( RAS_ARG_ TCoord  ey,
 531                                  TPos    x1,
 532                                  TCoord  y1,
 533                                  TPos    x2,
 534                                  TCoord  y2 )
 535   {
 536     TCoord  ex1, ex2, fx1, fx2, delta;
 537     int     p, first, dx;
 538     int     incr, lift, mod, rem;
 539
 540
 541     dx = x2 - x1;
 542
 543     ex1 = TRUNC( x1 );
 544     ex2 = TRUNC( x2 );
 545     fx1 = (TCoord)( x1 - SUBPIXELS( ex1 ) );
 546     fx2 = (TCoord)( x2 - SUBPIXELS( ex2 ) );
 547
 548     /* trivial case.  Happens often */
 549     if ( y1 == y2 )
 550     {
 551       gray_set_cell( RAS_VAR_ ex2, ey );
 552       return;
 553     }
 554
 555     /* everything is located in a single cell.  That is easy! */
 556     /*                                                        */
 557     if ( ex1 == ex2 )
 558     {
 559       delta      = y2 - y1;
 560       ras.area  += (TArea)( fx1 + fx2 ) * delta;
 561       ras.cover += delta;
 562       return;
 563     }
 564
 565     /* ok, we'll have to render a run of adjacent cells on the same */
 566     /* scanline...                                                  */
 567     /*                                                              */
 568     p     = ( ONE_PIXEL - fx1 ) * ( y2 - y1 );
 569     first = ONE_PIXEL;
 570     incr  = 1;
 571
 572     if ( dx < 0 )
 573     {
 574       p     = fx1 * ( y2 - y1 );
 575       first = 0;
 576       incr  = -1;
 577       dx    = -dx;
 578     }
 579
 580     delta = (TCoord)( p / dx );
 581     mod   = (TCoord)( p % dx );
 582     if ( mod < 0 )
 583     {
 584       delta--;
 585       mod += (TCoord)dx;
 586     }
 587
 588     ras.area  += (TArea)( fx1 + first ) * delta;
 589     ras.cover += delta;
 590
 591     ex1 += incr;
 592     gray_set_cell( RAS_VAR_ ex1, ey );
 593     y1  += delta;
 594
 595     if ( ex1 != ex2 )
 596     {
 597       p    = ONE_PIXEL * ( y2 - y1 + delta );
 598       lift = (TCoord)( p / dx );
 599       rem  = (TCoord)( p % dx );
 600       if ( rem < 0 )
 601       {
 602         lift--;
 603         rem += (TCoord)dx;
 604       }
 605
 606       mod -= (int)dx;
 607
 608       while ( ex1 != ex2 )
 609       {
 610         delta = lift;
 611         mod  += rem;
 612         if ( mod >= 0 )
 613         {
 614           mod -= (TCoord)dx;
 615           delta++;
 616         }
 617
 618         ras.area  += (TArea)ONE_PIXEL * delta;
 619         ras.cover += delta;
 620         y1        += delta;
 621         ex1       += incr;
 622         gray_set_cell( RAS_VAR_ ex1, ey );
 623       }
 624     }
 625
 626     delta      = y2 - y1;
 627     ras.area  += (TArea)( fx2 + ONE_PIXEL - first ) * delta;
 628     ras.cover += delta;
 629   }
 630
 631
 632   /*************************************************************************/
 633   /*                                                                       */
 634   /* Render a given line as a series of scanlines.                         */
 635   /*                                                                       */
 636   static void
 637   gray_render_line( RAS_ARG_ TPos  to_x,
 638                              TPos  to_y )
 639   {
 640     TCoord  ey1, ey2, fy1, fy2;
 641     TPos    dx, dy, x, x2;
 642     int     p, first;
 643     int     delta, rem, mod, lift, incr;
 644
 645
 646     ey1 = TRUNC( ras.last_ey );
 647     ey2 = TRUNC( to_y );     /* if (ey2 >= ras.max_ey) ey2 = ras.max_ey-1; */
 648     fy1 = (TCoord)( ras.y - ras.last_ey );
 649     fy2 = (TCoord)( to_y - SUBPIXELS( ey2 ) );
 650
 651     dx = to_x - ras.x;
 652     dy = to_y - ras.y;
 653
 654     /* XXX: we should do something about the trivial case where dx == 0, */
 655     /*      as it happens very often!                                    */
 656
 657     /* perform vertical clipping */
 658     {
 659       TCoord  min, max;
 660
 661
 662       min = ey1;
 663       max = ey2;
 664       if ( ey1 > ey2 )
 665       {
 666         min = ey2;
 667         max = ey1;
 668       }
 669       if ( min >= ras.max_ey || max < ras.min_ey )
 670         goto End;
 671     }
 672
 673     /* everything is on a single scanline */
 674     if ( ey1 == ey2 )
 675     {
 676       gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, to_x, fy2 );
 677       goto End;
 678     }
 679
 680     /* vertical line - avoid calling gray_render_scanline */
 681     incr = 1;
 682
 683     if ( dx == 0 )
 684     {
 685       TCoord  ex     = TRUNC( ras.x );
 686       TCoord  two_fx = (TCoord)( ( ras.x - SUBPIXELS( ex ) ) << 1 );
 687       TPos    area;
 688
 689
 690       first = ONE_PIXEL;
 691       if ( dy < 0 )
 692       {
 693         first = 0;
 694         incr  = -1;
 695       }
 696
 697       delta      = (int)( first - fy1 );
 698       ras.area  += (TArea)two_fx * delta;
 699       ras.cover += delta;
 700       ey1       += incr;
 701
 702       gray_set_cell( &ras, ex, ey1 );
 703
 704       delta = (int)( first + first - ONE_PIXEL );
 705       area  = (TArea)two_fx * delta;
 706       while ( ey1 != ey2 )
 707       {
 708         ras.area  += area;
 709         ras.cover += delta;
 710         ey1       += incr;
 711
 712         gray_set_cell( &ras, ex, ey1 );
 713       }
 714
 715       delta      = (int)( fy2 - ONE_PIXEL + first );
 716       ras.area  += (TArea)two_fx * delta;
 717       ras.cover += delta;
 718
 719       goto End;
 720     }
 721
 722     /* ok, we have to render several scanlines */
 723     p     = ( ONE_PIXEL - fy1 ) * dx;
 724     first = ONE_PIXEL;
 725     incr  = 1;
 726
 727     if ( dy < 0 )
 728     {
 729       p     = fy1 * dx;
 730       first = 0;
 731       incr  = -1;
 732       dy    = -dy;
 733     }
 734
 735     delta = (int)( p / dy );
 736     mod   = (int)( p % dy );
 737     if ( mod < 0 )
 738     {
 739       delta--;
 740       mod += (TCoord)dy;
 741     }
 742
 743     x = ras.x + delta;
 744     gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, x, (TCoord)first );
 745
 746     ey1 += incr;
 747     gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 );
 748
 749     if ( ey1 != ey2 )
 750     {
 751       p     = ONE_PIXEL * dx;
 752       lift  = (int)( p / dy );
 753       rem   = (int)( p % dy );
 754       if ( rem < 0 )
 755       {
 756         lift--;
 757         rem += (int)dy;
 758       }
 759       mod -= (int)dy;
 760
 761       while ( ey1 != ey2 )
 762       {
 763         delta = lift;
 764         mod  += rem;
 765         if ( mod >= 0 )
 766         {
 767           mod -= (int)dy;
 768           delta++;
 769         }
 770
 771         x2 = x + delta;
 772         gray_render_scanline( RAS_VAR_ ey1, x,
 773                                        (TCoord)( ONE_PIXEL - first ), x2,
 774                                        (TCoord)first );
 775         x = x2;
 776
 777         ey1 += incr;
 778         gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 );
 779       }
 780     }
 781
 782     gray_render_scanline( RAS_VAR_ ey1, x,
 783                                    (TCoord)( ONE_PIXEL - first ), to_x,
 784                                    fy2 );
 785
 786   End:
 787     ras.x       = to_x;
 788     ras.y       = to_y;
 789     ras.last_ey = SUBPIXELS( ey2 );
 790   }
 791
 792
 793   static void
 794   gray_split_conic( QT_FT_Vector*  base )
 795   {
 796     TPos  a, b;
 797
 798
 799     base[4].x = base[2].x;
 800     b = base[1].x;
 801     a = base[3].x = ( base[2].x + b ) / 2;
 802     b = base[1].x = ( base[0].x + b ) / 2;
 803     base[2].x = ( a + b ) / 2;
 804
 805     base[4].y = base[2].y;
 806     b = base[1].y;
 807     a = base[3].y = ( base[2].y + b ) / 2;
 808     b = base[1].y = ( base[0].y + b ) / 2;
 809     base[2].y = ( a + b ) / 2;
 810   }
 811
 812
 813   static void
 814   gray_render_conic( RAS_ARG_ const QT_FT_Vector*  control,
 815                               const QT_FT_Vector*  to )
 816   {
 817     TPos        dx, dy;
 818     int         top, level;
 819     int*        levels;
 820     QT_FT_Vector*  arc;
 821
 822
 823     dx = DOWNSCALE( ras.x ) + to->x - ( control->x << 1 );
 824     if ( dx < 0 )
 825       dx = -dx;
 826     dy = DOWNSCALE( ras.y ) + to->y - ( control->y << 1 );
 827     if ( dy < 0 )
 828       dy = -dy;
 829     if ( dx < dy )
 830       dx = dy;
 831
 832     level = 1;
 833     dx = dx / ras.conic_level;
 834     while ( dx > 0 )
 835     {
 836       dx >>= 2;
 837       level++;
 838     }
 839
 840     /* a shortcut to speed things up */
 841     if ( level <= 1 )
 842     {
 843       /* we compute the mid-point directly in order to avoid */
 844       /* calling gray_split_conic()                          */
 845       TPos  to_x, to_y, mid_x, mid_y;
 846
 847
 848       to_x  = UPSCALE( to->x );
 849       to_y  = UPSCALE( to->y );
 850       mid_x = ( ras.x + to_x + 2 * UPSCALE( control->x ) ) / 4;
 851       mid_y = ( ras.y + to_y + 2 * UPSCALE( control->y ) ) / 4;
 852
 853       gray_render_line( RAS_VAR_ mid_x, mid_y );
 854       gray_render_line( RAS_VAR_ to_x, to_y );
 855
 856       return;
 857     }
 858
 859     arc       = ras.bez_stack;
 860     levels    = ras.lev_stack;
 861     top       = 0;
 862     levels[0] = level;
 863
 864     arc[0].x = UPSCALE( to->x );
 865     arc[0].y = UPSCALE( to->y );
 866     arc[1].x = UPSCALE( control->x );
 867     arc[1].y = UPSCALE( control->y );
 868     arc[2].x = ras.x;
 869     arc[2].y = ras.y;
 870
 871     while ( top >= 0 )
 872     {
 873       level = levels[top];
 874       if ( level > 1 )
 875       {
 876         /* check that the arc crosses the current band */
 877         TPos  min, max, y;
 878
 879
 880         min = max = arc[0].y;
 881
 882         y = arc[1].y;
 883         if ( y < min ) min = y;
 884         if ( y > max ) max = y;
 885
 886         y = arc[2].y;
 887         if ( y < min ) min = y;
 888         if ( y > max ) max = y;
 889
 890         if ( TRUNC( min ) >= ras.max_ey || TRUNC( max ) < ras.min_ey )
 891           goto Draw;
 892
 893         gray_split_conic( arc );
 894         arc += 2;
 895         top++;
 896         levels[top] = levels[top - 1] = level - 1;
 897         continue;
 898       }
 899
 900     Draw:
 901       {
 902         TPos  to_x, to_y, mid_x, mid_y;
 903
 904
 905         to_x  = arc[0].x;
 906         to_y  = arc[0].y;
 907         mid_x = ( ras.x + to_x + 2 * arc[1].x ) / 4;
 908         mid_y = ( ras.y + to_y + 2 * arc[1].y ) / 4;
 909
 910         gray_render_line( RAS_VAR_ mid_x, mid_y );
 911         gray_render_line( RAS_VAR_ to_x, to_y );
 912
 913         top--;
 914         arc -= 2;
 915       }
 916     }
 917
 918     return;
 919   }
 920
 921
 922   static void
 923   gray_split_cubic( QT_FT_Vector*  base )
 924   {
 925     TPos  a, b, c, d;
 926
 927
 928     base[6].x = base[3].x;
 929     c = base[1].x;
 930     d = base[2].x;
 931     base[1].x = a = ( base[0].x + c ) / 2;
 932     base[5].x = b = ( base[3].x + d ) / 2;
 933     c = ( c + d ) / 2;
 934     base[2].x = a = ( a + c ) / 2;
 935     base[4].x = b = ( b + c ) / 2;
 936     base[3].x = ( a + b ) / 2;
 937
 938     base[6].y = base[3].y;
 939     c = base[1].y;
 940     d = base[2].y;
 941     base[1].y = a = ( base[0].y + c ) / 2;
 942     base[5].y = b = ( base[3].y + d ) / 2;
 943     c = ( c + d ) / 2;
 944     base[2].y = a = ( a + c ) / 2;
 945     base[4].y = b = ( b + c ) / 2;
 946     base[3].y = ( a + b ) / 2;
 947   }
 948
 949
 950   static void
 951   gray_render_cubic( RAS_ARG_ const QT_FT_Vector*  control1,
 952                               const QT_FT_Vector*  control2,
 953                               const QT_FT_Vector*  to )
 954   {
 955     TPos        dx, dy, da, db;
 956     int         top, level;
 957     int*        levels;
 958     QT_FT_Vector*  arc;
 959
 960
 961     dx = DOWNSCALE( ras.x ) + to->x - ( control1->x << 1 );
 962     if ( dx < 0 )
 963       dx = -dx;
 964     dy = DOWNSCALE( ras.y ) + to->y - ( control1->y << 1 );
 965     if ( dy < 0 )
 966       dy = -dy;
 967     if ( dx < dy )
 968       dx = dy;
 969     da = dx;
 970
 971     dx = DOWNSCALE( ras.x ) + to->x - 3 * ( control1->x + control2->x );
 972     if ( dx < 0 )
 973       dx = -dx;
 974     dy = DOWNSCALE( ras.y ) + to->y - 3 * ( control1->y + control2->y );
 975     if ( dy < 0 )
 976       dy = -dy;
 977     if ( dx < dy )
 978       dx = dy;
 979     db = dx;
 980
 981     level = 1;
 982     da    = da / ras.cubic_level;
 983     db    = db / ras.conic_level;
 984     while ( da > 0 || db > 0 )
 985     {
 986       da >>= 2;
 987       db >>= 3;
 988       level++;
 989     }
 990
 991     if ( level <= 1 )
 992     {
 993       TPos   to_x, to_y, mid_x, mid_y;
 994
 995
 996       to_x  = UPSCALE( to->x );
 997       to_y  = UPSCALE( to->y );
 998       mid_x = ( ras.x + to_x +
 999                 3 * UPSCALE( control1->x + control2->x ) ) / 8;
1000       mid_y = ( ras.y + to_y +
1001                 3 * UPSCALE( control1->y + control2->y ) ) / 8;
1002
1003       gray_render_line( RAS_VAR_ mid_x, mid_y );
1004       gray_render_line( RAS_VAR_ to_x, to_y );
1005       return;
1006     }
1007
1008     arc      = ras.bez_stack;
1009     arc[0].x = UPSCALE( to->x );
1010     arc[0].y = UPSCALE( to->y );
1011     arc[1].x = UPSCALE( control2->x );
1012     arc[1].y = UPSCALE( control2->y );
1013     arc[2].x = UPSCALE( control1->x );
1014     arc[2].y = UPSCALE( control1->y );
1015     arc[3].x = ras.x;
1016     arc[3].y = ras.y;
1017
1018     levels    = ras.lev_stack;
1019     top       = 0;
1020     levels[0] = level;
1021
1022     while ( top >= 0 )
1023     {
1024       level = levels[top];
1025       if ( level > 1 )
1026       {
1027         /* check that the arc crosses the current band */
1028         TPos  min, max, y;
1029
1030
1031         min = max = arc[0].y;
1032         y = arc[1].y;
1033         if ( y < min ) min = y;
1034         if ( y > max ) max = y;
1035         y = arc[2].y;
1036         if ( y < min ) min = y;
1037         if ( y > max ) max = y;
1038         y = arc[3].y;
1039         if ( y < min ) min = y;
1040         if ( y > max ) max = y;
1041         if ( TRUNC( min ) >= ras.max_ey || TRUNC( max ) < 0 )
1042           goto Draw;
1043         gray_split_cubic( arc );
1044         arc += 3;
1045         top ++;
1046         levels[top] = levels[top - 1] = level - 1;
1047         continue;
1048       }
1049
1050     Draw:
1051       {
1052         TPos  to_x, to_y, mid_x, mid_y;
1053
1054
1055         to_x  = arc[0].x;
1056         to_y  = arc[0].y;
1057         mid_x = ( ras.x + to_x + 3 * ( arc[1].x + arc[2].x ) ) / 8;
1058         mid_y = ( ras.y + to_y + 3 * ( arc[1].y + arc[2].y ) ) / 8;
1059
1060         gray_render_line( RAS_VAR_ mid_x, mid_y );
1061         gray_render_line( RAS_VAR_ to_x, to_y );
1062         top --;
1063         arc -= 3;
1064       }
1065     }
1066
1067     return;
1068   }
1069
1070
1071
1072   static int
1073   gray_move_to( const QT_FT_Vector*  to,
1074                 PWorker           worker )
1075   {
1076     TPos  x, y;
1077
1078
1079     /* record current cell, if any */
1080     gray_record_cell( worker );
1081
1082     /* start to a new position */
1083     x = UPSCALE( to->x );
1084     y = UPSCALE( to->y );
1085
1086     gray_start_cell( worker, TRUNC( x ), TRUNC( y ) );
1087
1088     worker->x = x;
1089     worker->y = y;
1090     return 0;
1091   }
1092
1093   static void
1094   gray_render_span( int             count,
1095                     const QT_FT_Span*  spans,
1096                     PWorker         worker )
1097   {
1098     unsigned char*  p;
1099     QT_FT_Bitmap*      map = &worker->target;
1100
1101     for ( ; count > 0; count--, spans++ )
1102     {
1103       unsigned char  coverage = spans->coverage;
1104
1105       /* first of all, compute the scanline offset */
1106       p = (unsigned char*)map->buffer - spans->y * map->pitch;
1107       if ( map->pitch >= 0 )
1108         p += ( map->rows - 1 ) * map->pitch;
1109
1110
1111       if ( coverage )
1112       {
1113         /* For small-spans it is faster to do it by ourselves than
1114          * calling `memset'.  This is mainly due to the cost of the
1115          * function call.
1116          */
1117         if ( spans->len >= 8 )
1118           QT_FT_MEM_SET( p + spans->x, (unsigned char)coverage, spans->len );
1119         else
1120         {
1121           unsigned char*  q = p + spans->x;
1122
1123
1124           switch ( spans->len )
1125           {
1126           case 7: *q++ = (unsigned char)coverage;
1127           case 6: *q++ = (unsigned char)coverage;
1128           case 5: *q++ = (unsigned char)coverage;
1129           case 4: *q++ = (unsigned char)coverage;
1130           case 3: *q++ = (unsigned char)coverage;
1131           case 2: *q++ = (unsigned char)coverage;
1132           case 1: *q   = (unsigned char)coverage;
1133           default:
1134             ;
1135           }
1136         }
1137       }
1138     }
1139   }
1140
1141
1142   static void
1143   gray_hline( RAS_ARG_ TCoord  x,
1144                        TCoord  y,
1145                        TPos    area,
1146                        int     acount )
1147   {
1148     QT_FT_Span*  span;
1149     int       coverage;
1150     int       skip;
1151
1152
1153     /* compute the coverage line's coverage, depending on the    */
1154     /* outline fill rule                                         */
1155     /*                                                           */
1156     /* the coverage percentage is area/(PIXEL_BITS*PIXEL_BITS*2) */
1157     /*                                                           */
1158     coverage = (int)( area >> ( PIXEL_BITS * 2 + 1 - 8 ) );
1159                                                     /* use range 0..256 */
1160     if ( coverage < 0 )
1161       coverage = -coverage;
1162
1163     if ( ras.outline.flags & QT_FT_OUTLINE_EVEN_ODD_FILL )
1164     {
1165       coverage &= 511;
1166
1167       if ( coverage > 256 )
1168         coverage = 512 - coverage;
1169       else if ( coverage == 256 )
1170         coverage = 255;
1171     }
1172     else
1173     {
1174       /* normal non-zero winding rule */
1175       if ( coverage >= 256 )
1176         coverage = 255;
1177     }
1178
1179     y += (TCoord)ras.min_ey;
1180     x += (TCoord)ras.min_ex;
1181
1182     /* QT_FT_Span.x is a 16-bit short, so limit our coordinates appropriately */
1183     if ( x >= 32768 )
1184       x = 32767;
1185
1186     if ( coverage )
1187     {
1188       /* see whether we can add this span to the current list */
1189       span  = ras.gray_spans + ras.num_gray_spans - 1;
1190       if ( ras.num_gray_spans > 0             &&
1191            span->y == y                       &&
1192            (int)span->x + span->len == (int)x &&
1193            span->coverage == coverage         )
1194       {
1195         span->len = (unsigned short)( span->len + acount );
1196         return;
1197       }
1198
1199       if ( ras.num_gray_spans >= QT_FT_MAX_GRAY_SPANS )
1200       {
1201         if ( ras.render_span && ras.num_gray_spans > ras.skip_spans )
1202         {
1203           skip = ras.skip_spans > 0 ? ras.skip_spans : 0;
1204           ras.render_span( ras.num_gray_spans - skip,
1205                            ras.gray_spans + skip,
1206                            ras.render_span_data );
1207         }
1208
1209         ras.skip_spans -= ras.num_gray_spans;
1210
1211         /* ras.render_span( span->y, ras.gray_spans, count ); */
1212
1213 #ifdef DEBUG_GRAYS
1214
1215         if ( 1 )
1216         {
1217           int  n;
1218
1219
1220           fprintf( stderr, "y=%3d ", y );
1221           span = ras.gray_spans;
1222           for ( n = 0; n < count; n++, span++ )
1223             fprintf( stderr, "[%d..%d]:%02x ",
1224                      span->x, span->x + span->len - 1, span->coverage );
1225           fprintf( stderr, "\n" );
1226         }
1227
1228 #endif /* DEBUG_GRAYS */
1229
1230         ras.num_gray_spans = 0;
1231
1232         span  = ras.gray_spans;
1233       }
1234       else
1235         span++;
1236
1237       /* add a gray span to the current list */
1238       span->x        = (short)x;
1239       span->len      = (unsigned short)acount;
1240       span->y        = (short)y;
1241       span->coverage = (unsigned char)coverage;
1242
1243       ras.num_gray_spans++;
1244     }
1245   }
1246
1247
1248 #ifdef DEBUG_GRAYS
1249
1250   /* to be called while in the debugger */
1251   gray_dump_cells( RAS_ARG )
1252   {
1253     int  yindex;
1254
1255
1256     for ( yindex = 0; yindex < ras.ycount; yindex++ )
1257     {
1258       PCell  cell;
1259
1260
1261       printf( "%3d:", yindex );
1262
1263       for ( cell = ras.ycells[yindex]; cell != NULL; cell = cell->next )
1264         printf( " (%3d, c:%4d, a:%6d)", cell->x, cell->cover, cell->area );
1265       printf( "\n" );
1266     }
1267   }
1268
1269 #endif /* DEBUG_GRAYS */
1270
1271
1272   static void
1273   gray_sweep( RAS_ARG_ const QT_FT_Bitmap*  target )
1274   {
1275     int  yindex;
1276
1277     QT_FT_UNUSED( target );
1278
1279
1280     if ( ras.num_cells == 0 )
1281       return;
1282
1283     for ( yindex = 0; yindex < ras.ycount; yindex++ )
1284     {
1285       PCell   cell  = ras.ycells[yindex];
1286       TCoord  cover = 0;
1287       TCoord  x     = 0;
1288
1289
1290       for ( ; cell != NULL; cell = cell->next )
1291       {
1292         TArea  area;
1293
1294
1295         if ( cell->x > x && cover != 0 )
1296           gray_hline( RAS_VAR_ x, yindex, cover * ( ONE_PIXEL * 2 ),
1297                       cell->x - x );
1298
1299         cover += cell->cover;
1300         area   = cover * ( ONE_PIXEL * 2 ) - cell->area;
1301
1302         if ( area != 0 && cell->x >= 0 )
1303           gray_hline( RAS_VAR_ cell->x, yindex, area, 1 );
1304
1305         x = cell->x + 1;
1306       }
1307
1308       if ( ras.count_ex > x && cover != 0 )
1309         gray_hline( RAS_VAR_ x, yindex, cover * ( ONE_PIXEL * 2 ),
1310                     ras.count_ex - x );
1311     }
1312   }
1313
1314   /*************************************************************************/
1315   /*                                                                       */
1316   /*  The following function should only compile in stand_alone mode,      */
1317   /*  i.e., when building this component without the rest of FreeType.     */
1318   /*                                                                       */
1319   /*************************************************************************/
1320
1321   /*************************************************************************/
1322   /*                                                                       */
1323   /* <Function>                                                            */
1324   /*    QT_FT_Outline_Decompose                                               */
1325   /*                                                                       */
1326   /* <Description>                                                         */
1327   /*    Walks over an outline's structure to decompose it into individual  */
1328   /*    segments and Bezier arcs.  This function is also able to emit      */
1329   /*    `move to' and `close to' operations to indicate the start and end  */
1330   /*    of new contours in the outline.                                    */
1331   /*                                                                       */
1332   /* <Input>                                                               */
1333   /*    outline        :: A pointer to the source target.                  */
1334   /*                                                                       */
1335   /*    user           :: A typeless pointer which is passed to each       */
1336   /*                      emitter during the decomposition.  It can be     */
1337   /*                      used to store the state during the               */
1338   /*                      decomposition.                                   */
1339   /*                                                                       */
1340   /* <Return>                                                              */
1341   /*    Error code.  0 means success.                                      */
1342   /*                                                                       */
1343   static
1344   int  QT_FT_Outline_Decompose( const QT_FT_Outline*        outline,
1345                              void*                    user )
1346   {
1347 #undef SCALED
1348 #define SCALED( x )  (x)
1349
1350     QT_FT_Vector   v_last;
1351     QT_FT_Vector   v_control;
1352     QT_FT_Vector   v_start;
1353
1354     QT_FT_Vector*  point;
1355     QT_FT_Vector*  limit;
1356     char*       tags;
1357
1358     int   n;         /* index of contour in outline     */
1359     int   first;     /* index of first point in contour */
1360     int   error;
1361     char  tag;       /* current point's state           */
1362
1363     first = 0;
1364
1365     for ( n = 0; n < outline->n_contours; n++ )
1366     {
1367       int  last;  /* index of last point in contour */
1368
1369
1370       last  = outline->contours[n];
1371       limit = outline->points + last;
1372
1373       v_start = outline->points[first];
1374       v_last  = outline->points[last];
1375
1376       v_start.x = SCALED( v_start.x );
1377       v_start.y = SCALED( v_start.y );
1378
1379       v_last.x  = SCALED( v_last.x );
1380       v_last.y  = SCALED( v_last.y );
1381
1382       v_control = v_start;
1383
1384       point = outline->points + first;
1385       tags  = outline->tags  + first;
1386       tag   = QT_FT_CURVE_TAG( tags[0] );
1387
1388       /* A contour cannot start with a cubic control point! */
1389       if ( tag == QT_FT_CURVE_TAG_CUBIC )
1390         goto Invalid_Outline;
1391
1392       /* check first point to determine origin */
1393       if ( tag == QT_FT_CURVE_TAG_CONIC )
1394       {
1395         /* first point is conic control.  Yes, this happens. */
1396         if ( QT_FT_CURVE_TAG( outline->tags[last] ) == QT_FT_CURVE_TAG_ON )
1397         {
1398           /* start at last point if it is on the curve */
1399           v_start = v_last;
1400           limit--;
1401         }
1402         else
1403         {
1404           /* if both first and last points are conic,         */
1405           /* start at their middle and record its position    */
1406           /* for closure                                      */
1407           v_start.x = ( v_start.x + v_last.x ) / 2;
1408           v_start.y = ( v_start.y + v_last.y ) / 2;
1409
1410           v_last = v_start;
1411         }
1412         point--;
1413         tags--;
1414       }
1415
1416       error = gray_move_to( &v_start, user );
1417       if ( error )
1418         goto Exit;
1419
1420       while ( point < limit )
1421       {
1422         point++;
1423         tags++;
1424
1425         tag = QT_FT_CURVE_TAG( tags[0] );
1426         switch ( tag )
1427         {
1428         case QT_FT_CURVE_TAG_ON:  /* emit a single line_to */
1429           {
1430             QT_FT_Vector  vec;
1431
1432
1433             vec.x = SCALED( point->x );
1434             vec.y = SCALED( point->y );
1435
1436             gray_render_line(user, UPSCALE(vec.x), UPSCALE(vec.y));
1437             continue;
1438           }
1439
1440         case QT_FT_CURVE_TAG_CONIC:  /* consume conic arcs */
1441           {
1442             v_control.x = SCALED( point->x );
1443             v_control.y = SCALED( point->y );
1444
1445           Do_Conic:
1446             if ( point < limit )
1447             {
1448               QT_FT_Vector  vec;
1449               QT_FT_Vector  v_middle;
1450
1451
1452               point++;
1453               tags++;
1454               tag = QT_FT_CURVE_TAG( tags[0] );
1455
1456               vec.x = SCALED( point->x );
1457               vec.y = SCALED( point->y );
1458
1459               if ( tag == QT_FT_CURVE_TAG_ON )
1460               {
1461                 gray_render_conic(user, &v_control, &vec);
1462                 continue;
1463               }
1464
1465               if ( tag != QT_FT_CURVE_TAG_CONIC )
1466                 goto Invalid_Outline;
1467
1468               v_middle.x = ( v_control.x + vec.x ) / 2;
1469               v_middle.y = ( v_control.y + vec.y ) / 2;
1470
1471               gray_render_conic(user, &v_control, &v_middle);
1472               v_control = vec;
1473               goto Do_Conic;
1474             }
1475
1476             gray_render_conic(user, &v_control, &v_start);
1477             goto Close;
1478           }
1479
1480         default:  /* QT_FT_CURVE_TAG_CUBIC */
1481           {
1482             QT_FT_Vector  vec1, vec2;
1483
1484
1485             if ( point + 1 > limit                             ||
1486                  QT_FT_CURVE_TAG( tags[1] ) != QT_FT_CURVE_TAG_CUBIC )
1487               goto Invalid_Outline;
1488
1489             point += 2;
1490             tags  += 2;
1491
1492             vec1.x = SCALED( point[-2].x );
1493             vec1.y = SCALED( point[-2].y );
1494
1495             vec2.x = SCALED( point[-1].x );
1496             vec2.y = SCALED( point[-1].y );
1497
1498             if ( point <= limit )
1499             {
1500               QT_FT_Vector  vec;
1501
1502
1503               vec.x = SCALED( point->x );
1504               vec.y = SCALED( point->y );
1505
1506               gray_render_cubic(user, &vec1, &vec2, &vec);
1507               continue;
1508             }
1509
1510             gray_render_cubic(user, &vec1, &vec2, &v_start);
1511             goto Close;
1512           }
1513         }
1514       }
1515
1516       /* close the contour with a line segment */
1517       gray_render_line(user, UPSCALE(v_start.x), UPSCALE(v_start.y));
1518
1519    Close:
1520       first = last + 1;
1521     }
1522
1523     return 0;
1524
1525   Exit:
1526     return error;
1527
1528   Invalid_Outline:
1529     return ErrRaster_Invalid_Outline;
1530   }
1531
1532   typedef struct  TBand_
1533   {
1534     TPos  min, max;
1535
1536   } TBand;
1537
1538
1539   static int
1540   gray_convert_glyph_inner( RAS_ARG )
1541   {
1542     volatile int  error = 0;
1543
1544     if ( qt_ft_setjmp( ras.jump_buffer ) == 0 )
1545     {
1546       error = QT_FT_Outline_Decompose( &ras.outline, &ras );
1547       gray_record_cell( RAS_VAR );
1548     }
1549     else
1550     {
1551       error = ErrRaster_Memory_Overflow;
1552     }
1553
1554     return error;
1555   }
1556
1557
1558   static int
1559   gray_convert_glyph( RAS_ARG )
1560   {
1561     TBand            bands[40];
1562     TBand* volatile  band;
1563     int volatile     n, num_bands;
1564     TPos volatile    min, max, max_y;
1565     QT_FT_BBox*      clip;
1566     int              skip;
1567
1568     ras.num_gray_spans = 0;
1569
1570     /* Set up state in the raster object */
1571     gray_compute_cbox( RAS_VAR );
1572
1573     /* clip to target bitmap, exit if nothing to do */
1574     clip = &ras.clip_box;
1575
1576     if ( ras.max_ex <= clip->xMin || ras.min_ex >= clip->xMax ||
1577          ras.max_ey <= clip->yMin || ras.min_ey >= clip->yMax )
1578       return 0;
1579
1580     if ( ras.min_ex < clip->xMin ) ras.min_ex = clip->xMin;
1581     if ( ras.min_ey < clip->yMin ) ras.min_ey = clip->yMin;
1582
1583     if ( ras.max_ex > clip->xMax ) ras.max_ex = clip->xMax;
1584     if ( ras.max_ey > clip->yMax ) ras.max_ey = clip->yMax;
1585
1586     ras.count_ex = ras.max_ex - ras.min_ex;
1587     ras.count_ey = ras.max_ey - ras.min_ey;
1588
1589     /* simple heuristic used to speed-up the bezier decomposition -- see */
1590     /* the code in gray_render_conic() and gray_render_cubic() for more  */
1591     /* details                                                           */
1592     ras.conic_level = 32;
1593     ras.cubic_level = 16;
1594
1595     {
1596       int level = 0;
1597
1598
1599       if ( ras.count_ex > 24 || ras.count_ey > 24 )
1600         level++;
1601       if ( ras.count_ex > 120 || ras.count_ey > 120 )
1602         level++;
1603
1604       ras.conic_level <<= level;
1605       ras.cubic_level <<= level;
1606     }
1607
1608     /* setup vertical bands */
1609     num_bands = (int)( ( ras.max_ey - ras.min_ey ) / ras.band_size );
1610     if ( num_bands == 0 )  num_bands = 1;
1611     if ( num_bands >= 39 ) num_bands = 39;
1612
1613     ras.band_shoot = 0;
1614
1615     min   = ras.min_ey;
1616     max_y = ras.max_ey;
1617
1618     for ( n = 0; n < num_bands; n++, min = max )
1619     {
1620       max = min + ras.band_size;
1621       if ( n == num_bands - 1 || max > max_y )
1622         max = max_y;
1623
1624       bands[0].min = min;
1625       bands[0].max = max;
1626       band         = bands;
1627
1628       while ( band >= bands )
1629       {
1630         TPos  bottom, top, middle;
1631         int   error;
1632
1633         {
1634           PCell  cells_max;
1635           int    yindex;
1636           int    cell_start, cell_end, cell_mod;
1637
1638
1639           ras.ycells = (PCell*)ras.buffer;
1640           ras.ycount = band->max - band->min;
1641
1642           cell_start = sizeof ( PCell ) * ras.ycount;
1643           cell_mod   = cell_start % sizeof ( TCell );
1644           if ( cell_mod > 0 )
1645             cell_start += sizeof ( TCell ) - cell_mod;
1646
1647           cell_end  = ras.buffer_size;
1648           cell_end -= cell_end % sizeof( TCell );
1649
1650           cells_max = (PCell)( (char*)ras.buffer + cell_end );
1651           ras.cells = (PCell)( (char*)ras.buffer + cell_start );
1652           if ( ras.cells >= cells_max )
1653             goto ReduceBands;
1654
1655           ras.max_cells = (int)(cells_max - ras.cells);
1656           if ( ras.max_cells < 2 )
1657             goto ReduceBands;
1658
1659           for ( yindex = 0; yindex < ras.ycount; yindex++ )
1660             ras.ycells[yindex] = NULL;
1661         }
1662
1663         ras.num_cells = 0;
1664         ras.invalid   = 1;
1665         ras.min_ey    = band->min;
1666         ras.max_ey    = band->max;
1667         ras.count_ey  = band->max - band->min;
1668
1669         error = gray_convert_glyph_inner( RAS_VAR );
1670
1671         if ( !error )
1672         {
1673           gray_sweep( RAS_VAR_ &ras.target );
1674           band--;
1675           continue;
1676         }
1677         else if ( error != ErrRaster_Memory_Overflow )
1678           return 1;
1679
1680       ReduceBands:
1681         /* render pool overflow; we will reduce the render band by half */
1682         bottom = band->min;
1683         top    = band->max;
1684         middle = bottom + ( ( top - bottom ) >> 1 );
1685
1686         /* This is too complex for a single scanline; there must */
1687         /* be some problems.                                     */
1688         if ( middle == bottom )
1689         {
1690 #ifdef DEBUG_GRAYS
1691           fprintf( stderr, "Rotten glyph!\n" );
1692 #endif
1693           return ErrRaster_OutOfMemory;
1694         }
1695
1696         if ( bottom-top >= ras.band_size )
1697           ras.band_shoot++;
1698
1699         band[1].min = bottom;
1700         band[1].max = middle;
1701         band[0].min = middle;
1702         band[0].max = top;
1703         band++;
1704       }
1705     }
1706
1707     if ( ras.render_span && ras.num_gray_spans > ras.skip_spans )
1708     {
1709         skip = ras.skip_spans > 0 ? ras.skip_spans : 0;
1710         ras.render_span( ras.num_gray_spans - skip,
1711                          ras.gray_spans + skip,
1712                          ras.render_span_data );
1713     }
1714
1715     ras.skip_spans -= ras.num_gray_spans;
1716
1717     if ( ras.band_shoot > 8 && ras.band_size > 16 )
1718       ras.band_size = ras.band_size / 2;
1719
1720     return 0;
1721   }
1722
1723
1724   static int
1725   gray_raster_render( QT_FT_Raster                  raster,
1726                       const QT_FT_Raster_Params*  params )
1727   {
1728     const QT_FT_Outline*  outline    = (const QT_FT_Outline*)params->source;
1729     const QT_FT_Bitmap*   target_map = params->target;
1730     PWorker            worker;
1731
1732
1733     if ( !raster || !raster->buffer || !raster->buffer_size )
1734       return ErrRaster_Invalid_Argument;
1735
1736     if ( raster->worker )
1737       raster->worker->skip_spans = params->skip_spans;
1738
1739     // If raster object and raster buffer are allocated, but
1740     // raster size isn't of the minimum size, indicate out of
1741     // memory.
1742     if (raster->buffer_allocated_size < MINIMUM_POOL_SIZE )
1743       return ErrRaster_OutOfMemory;
1744
1745     /* return immediately if the outline is empty */
1746     if ( outline->n_points == 0 || outline->n_contours <= 0 )
1747       return 0;
1748
1749     if ( !outline || !outline->contours || !outline->points )
1750       return ErrRaster_Invalid_Outline;
1751
1752     if ( outline->n_points !=
1753            outline->contours[outline->n_contours - 1] + 1 )
1754       return ErrRaster_Invalid_Outline;
1755
1756     worker = raster->worker;
1757
1758     /* if direct mode is not set, we must have a target bitmap */
1759     if ( ( params->flags & QT_FT_RASTER_FLAG_DIRECT ) == 0 )
1760     {
1761       if ( !target_map )
1762         return ErrRaster_Invalid_Argument;
1763
1764       /* nothing to do */
1765       if ( !target_map->width || !target_map->rows )
1766         return 0;
1767
1768       if ( !target_map->buffer )
1769         return ErrRaster_Invalid_Argument;
1770     }
1771
1772     /* this version does not support monochrome rendering */
1773     if ( !( params->flags & QT_FT_RASTER_FLAG_AA ) )
1774       return ErrRaster_Invalid_Mode;
1775
1776     /* compute clipping box */
1777     if ( ( params->flags & QT_FT_RASTER_FLAG_DIRECT ) == 0 )
1778     {
1779       /* compute clip box from target pixmap */
1780       ras.clip_box.xMin = 0;
1781       ras.clip_box.yMin = 0;
1782       ras.clip_box.xMax = target_map->width;
1783       ras.clip_box.yMax = target_map->rows;
1784     }
1785     else if ( params->flags & QT_FT_RASTER_FLAG_CLIP )
1786     {
1787       ras.clip_box = params->clip_box;
1788     }
1789     else
1790     {
1791       ras.clip_box.xMin = -32768L;
1792       ras.clip_box.yMin = -32768L;
1793       ras.clip_box.xMax =  32767L;
1794       ras.clip_box.yMax =  32767L;
1795     }
1796
1797     gray_init_cells( worker, raster->buffer, raster->buffer_size );
1798
1799     ras.outline   = *outline;
1800     ras.num_cells = 0;
1801     ras.invalid   = 1;
1802     ras.band_size = raster->band_size;
1803
1804     if ( target_map )
1805       ras.target = *target_map;
1806
1807     ras.render_span      = (QT_FT_Raster_Span_Func)gray_render_span;
1808     ras.render_span_data = &ras;
1809
1810     if ( params->flags & QT_FT_RASTER_FLAG_DIRECT )
1811     {
1812       ras.render_span      = (QT_FT_Raster_Span_Func)params->gray_spans;
1813       ras.render_span_data = params->user;
1814     }
1815
1816     return gray_convert_glyph( worker );
1817   }
1818
1819
1820   /**** RASTER OBJECT CREATION: In standalone mode, we simply use *****/
1821   /****                         a static object.                  *****/
1822
1823   static int
1824   gray_raster_new( QT_FT_Raster*  araster )
1825   {
1826     *araster = malloc(sizeof(TRaster));
1827     if (!*araster) {
1828         *araster = 0;
1829         return ErrRaster_Memory_Overflow;
1830     }
1831     QT_FT_MEM_ZERO(*araster, sizeof(TRaster));
1832
1833     return 0;
1834   }
1835
1836
1837   static void
1838   gray_raster_done( QT_FT_Raster  raster )
1839   {
1840     free(raster);
1841   }
1842
1843
1844   static void
1845   gray_raster_reset( QT_FT_Raster  raster,
1846                      char*      pool_base,
1847                      long       pool_size )
1848   {
1849     PRaster  rast = (PRaster)raster;
1850
1851     if ( raster )
1852     {
1853       if ( pool_base && ( pool_size >= MINIMUM_POOL_SIZE ) )
1854       {
1855         PWorker  worker = (PWorker)pool_base;
1856
1857
1858         rast->worker      = worker;
1859         rast->buffer      = pool_base +
1860                               ( ( sizeof ( TWorker ) + sizeof ( TCell ) - 1 ) &
1861                                 ~( sizeof ( TCell ) - 1 ) );
1862         rast->buffer_size = (long)( ( pool_base + pool_size ) -
1863                                     (char*)rast->buffer ) &
1864                                       ~( sizeof ( TCell ) - 1 );
1865         rast->band_size   = (int)( rast->buffer_size /
1866                                      ( sizeof ( TCell ) * 8 ) );
1867       }
1868       else if ( pool_base)
1869       { // Case when there is a raster pool allocated, but it
1870         // doesn't have the minimum size (and so memory will be reallocated)
1871           rast->buffer = pool_base;
1872           rast->worker = NULL;
1873           rast->buffer_size = pool_size;
1874       }
1875       else
1876       {
1877         rast->buffer      = NULL;
1878         rast->buffer_size = 0;
1879         rast->worker      = NULL;
1880       }
1881       rast->buffer_allocated_size = pool_size;
1882     }
1883   }
1884
1885   const QT_FT_Raster_Funcs  qt_ft_grays_raster =
1886   {
1887     QT_FT_GLYPH_FORMAT_OUTLINE,
1888
1889     (QT_FT_Raster_New_Func)     gray_raster_new,
1890     (QT_FT_Raster_Reset_Func)   gray_raster_reset,
1891     (QT_FT_Raster_Set_Mode_Func)0,
1892     (QT_FT_Raster_Render_Func)  gray_raster_render,
1893     (QT_FT_Raster_Done_Func)    gray_raster_done
1894   };
1895
1896 /* END */