src/gui/painting/qgrayraster.c

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
   4 ** All rights reserved.
   5 ** Contact: Nokia Corporation (qt-info@nokia.com)
   6 **
   7 ** This file is part of the QtGui module of the Qt Toolkit.
   8 **
   9 ** $QT_BEGIN_LICENSE:LGPL$
  10 ** GNU Lesser General Public License Usage
  11 ** This file may be used under the terms of the GNU Lesser General Public
  12 ** License version 2.1 as published by the Free Software Foundation and
  13 ** appearing in the file LICENSE.LGPL included in the packaging of this
  14 ** file. Please review the following information to ensure the GNU Lesser
  15 ** General Public License version 2.1 requirements will be met:
  16 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  17 **
  18 ** In addition, as a special exception, Nokia gives you certain additional
  19 ** rights. These rights are described in the Nokia Qt LGPL Exception
  20 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  21 **
  22 ** GNU General Public License Usage
  23 ** Alternatively, this file may be used under the terms of the GNU General
  24 ** Public License version 3.0 as published by the Free Software Foundation
  25 ** and appearing in the file LICENSE.GPL included in the packaging of this
  26 ** file. Please review the following information to ensure the GNU General
  27 ** Public License version 3.0 requirements will be met:
  28 ** http://www.gnu.org/copyleft/gpl.html.
  29 **
  30 ** Other Usage
  31 ** Alternatively, this file may be used in accordance with the terms and
  32 ** conditions contained in a signed written agreement between you and Nokia.
  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
1094   static int
1095   gray_line_to( const QT_FT_Vector*  to,
1096                 PWorker           worker )
1097   {
1098     gray_render_line( worker, UPSCALE( to->x ), UPSCALE( to->y ) );
1099     return 0;
1100   }
1101
1102
1103   static int
1104   gray_conic_to( const QT_FT_Vector*  control,
1105                  const QT_FT_Vector*  to,
1106                  PWorker           worker )
1107   {
1108     gray_render_conic( worker, control, to );
1109     return 0;
1110   }
1111
1112
1113   static int
1114   gray_cubic_to( const QT_FT_Vector*  control1,
1115                  const QT_FT_Vector*  control2,
1116                  const QT_FT_Vector*  to,
1117                  PWorker           worker )
1118   {
1119     gray_render_cubic( worker, control1, control2, to );
1120     return 0;
1121   }
1122
1123
1124   static void
1125   gray_render_span( int             count,
1126                     const QT_FT_Span*  spans,
1127                     PWorker         worker )
1128   {
1129     unsigned char*  p;
1130     QT_FT_Bitmap*      map = &worker->target;
1131
1132     for ( ; count > 0; count--, spans++ )
1133     {
1134       unsigned char  coverage = spans->coverage;
1135
1136       /* first of all, compute the scanline offset */
1137       p = (unsigned char*)map->buffer - spans->y * map->pitch;
1138       if ( map->pitch >= 0 )
1139         p += ( map->rows - 1 ) * map->pitch;
1140
1141
1142       if ( coverage )
1143       {
1144         /* For small-spans it is faster to do it by ourselves than
1145          * calling `memset'.  This is mainly due to the cost of the
1146          * function call.
1147          */
1148         if ( spans->len >= 8 )
1149           QT_FT_MEM_SET( p + spans->x, (unsigned char)coverage, spans->len );
1150         else
1151         {
1152           unsigned char*  q = p + spans->x;
1153
1154
1155           switch ( spans->len )
1156           {
1157           case 7: *q++ = (unsigned char)coverage;
1158           case 6: *q++ = (unsigned char)coverage;
1159           case 5: *q++ = (unsigned char)coverage;
1160           case 4: *q++ = (unsigned char)coverage;
1161           case 3: *q++ = (unsigned char)coverage;
1162           case 2: *q++ = (unsigned char)coverage;
1163           case 1: *q   = (unsigned char)coverage;
1164           default:
1165             ;
1166           }
1167         }
1168       }
1169     }
1170   }
1171
1172
1173   static void
1174   gray_hline( RAS_ARG_ TCoord  x,
1175                        TCoord  y,
1176                        TPos    area,
1177                        int     acount )
1178   {
1179     QT_FT_Span*  span;
1180     int       coverage;
1181     int       skip;
1182
1183
1184     /* compute the coverage line's coverage, depending on the    */
1185     /* outline fill rule                                         */
1186     /*                                                           */
1187     /* the coverage percentage is area/(PIXEL_BITS*PIXEL_BITS*2) */
1188     /*                                                           */
1189     coverage = (int)( area >> ( PIXEL_BITS * 2 + 1 - 8 ) );
1190                                                     /* use range 0..256 */
1191     if ( coverage < 0 )
1192       coverage = -coverage;
1193
1194     if ( ras.outline.flags & QT_FT_OUTLINE_EVEN_ODD_FILL )
1195     {
1196       coverage &= 511;
1197
1198       if ( coverage > 256 )
1199         coverage = 512 - coverage;
1200       else if ( coverage == 256 )
1201         coverage = 255;
1202     }
1203     else
1204     {
1205       /* normal non-zero winding rule */
1206       if ( coverage >= 256 )
1207         coverage = 255;
1208     }
1209
1210     y += (TCoord)ras.min_ey;
1211     x += (TCoord)ras.min_ex;
1212
1213     /* QT_FT_Span.x is a 16-bit short, so limit our coordinates appropriately */
1214     if ( x >= 32768 )
1215       x = 32767;
1216
1217     if ( coverage )
1218     {
1219       /* see whether we can add this span to the current list */
1220       span  = ras.gray_spans + ras.num_gray_spans - 1;
1221       if ( ras.num_gray_spans > 0             &&
1222            span->y == y                       &&
1223            (int)span->x + span->len == (int)x &&
1224            span->coverage == coverage         )
1225       {
1226         span->len = (unsigned short)( span->len + acount );
1227         return;
1228       }
1229
1230       if ( ras.num_gray_spans >= QT_FT_MAX_GRAY_SPANS )
1231       {
1232         if ( ras.render_span && ras.num_gray_spans > ras.skip_spans )
1233         {
1234           skip = ras.skip_spans > 0 ? ras.skip_spans : 0;
1235           ras.render_span( ras.num_gray_spans - skip,
1236                            ras.gray_spans + skip,
1237                            ras.render_span_data );
1238         }
1239
1240         ras.skip_spans -= ras.num_gray_spans;
1241
1242         /* ras.render_span( span->y, ras.gray_spans, count ); */
1243
1244 #ifdef DEBUG_GRAYS
1245
1246         if ( 1 )
1247         {
1248           int  n;
1249
1250
1251           fprintf( stderr, "y=%3d ", y );
1252           span = ras.gray_spans;
1253           for ( n = 0; n < count; n++, span++ )
1254             fprintf( stderr, "[%d..%d]:%02x ",
1255                      span->x, span->x + span->len - 1, span->coverage );
1256           fprintf( stderr, "\n" );
1257         }
1258
1259 #endif /* DEBUG_GRAYS */
1260
1261         ras.num_gray_spans = 0;
1262
1263         span  = ras.gray_spans;
1264       }
1265       else
1266         span++;
1267
1268       /* add a gray span to the current list */
1269       span->x        = (short)x;
1270       span->len      = (unsigned short)acount;
1271       span->y        = (short)y;
1272       span->coverage = (unsigned char)coverage;
1273
1274       ras.num_gray_spans++;
1275     }
1276   }
1277
1278
1279 #ifdef DEBUG_GRAYS
1280
1281   /* to be called while in the debugger */
1282   gray_dump_cells( RAS_ARG )
1283   {
1284     int  yindex;
1285
1286
1287     for ( yindex = 0; yindex < ras.ycount; yindex++ )
1288     {
1289       PCell  cell;
1290
1291
1292       printf( "%3d:", yindex );
1293
1294       for ( cell = ras.ycells[yindex]; cell != NULL; cell = cell->next )
1295         printf( " (%3d, c:%4d, a:%6d)", cell->x, cell->cover, cell->area );
1296       printf( "\n" );
1297     }
1298   }
1299
1300 #endif /* DEBUG_GRAYS */
1301
1302
1303   static void
1304   gray_sweep( RAS_ARG_ const QT_FT_Bitmap*  target )
1305   {
1306     int  yindex;
1307
1308     QT_FT_UNUSED( target );
1309
1310
1311     if ( ras.num_cells == 0 )
1312       return;
1313
1314     for ( yindex = 0; yindex < ras.ycount; yindex++ )
1315     {
1316       PCell   cell  = ras.ycells[yindex];
1317       TCoord  cover = 0;
1318       TCoord  x     = 0;
1319
1320
1321       for ( ; cell != NULL; cell = cell->next )
1322       {
1323         TArea  area;
1324
1325
1326         if ( cell->x > x && cover != 0 )
1327           gray_hline( RAS_VAR_ x, yindex, cover * ( ONE_PIXEL * 2 ),
1328                       cell->x - x );
1329
1330         cover += cell->cover;
1331         area   = cover * ( ONE_PIXEL * 2 ) - cell->area;
1332
1333         if ( area != 0 && cell->x >= 0 )
1334           gray_hline( RAS_VAR_ cell->x, yindex, area, 1 );
1335
1336         x = cell->x + 1;
1337       }
1338
1339       if ( ras.count_ex > x && cover != 0 )
1340         gray_hline( RAS_VAR_ x, yindex, cover * ( ONE_PIXEL * 2 ),
1341                     ras.count_ex - x );
1342     }
1343   }
1344
1345   /*************************************************************************/
1346   /*                                                                       */
1347   /*  The following function should only compile in stand_alone mode,      */
1348   /*  i.e., when building this component without the rest of FreeType.     */
1349   /*                                                                       */
1350   /*************************************************************************/
1351
1352   /*************************************************************************/
1353   /*                                                                       */
1354   /* <Function>                                                            */
1355   /*    QT_FT_Outline_Decompose                                               */
1356   /*                                                                       */
1357   /* <Description>                                                         */
1358   /*    Walks over an outline's structure to decompose it into individual  */
1359   /*    segments and Bezier arcs.  This function is also able to emit      */
1360   /*    `move to' and `close to' operations to indicate the start and end  */
1361   /*    of new contours in the outline.                                    */
1362   /*                                                                       */
1363   /* <Input>                                                               */
1364   /*    outline        :: A pointer to the source target.                  */
1365   /*                                                                       */
1366   /*    user           :: A typeless pointer which is passed to each       */
1367   /*                      emitter during the decomposition.  It can be     */
1368   /*                      used to store the state during the               */
1369   /*                      decomposition.                                   */
1370   /*                                                                       */
1371   /* <Return>                                                              */
1372   /*    Error code.  0 means success.                                      */
1373   /*                                                                       */
1374   static
1375   int  QT_FT_Outline_Decompose( const QT_FT_Outline*        outline,
1376                              void*                    user )
1377   {
1378 #undef SCALED
1379 #define SCALED( x )  (x)
1380
1381     QT_FT_Vector   v_last;
1382     QT_FT_Vector   v_control;
1383     QT_FT_Vector   v_start;
1384
1385     QT_FT_Vector*  point;
1386     QT_FT_Vector*  limit;
1387     char*       tags;
1388
1389     int   n;         /* index of contour in outline     */
1390     int   first;     /* index of first point in contour */
1391     int   error;
1392     char  tag;       /* current point's state           */
1393
1394     first = 0;
1395
1396     for ( n = 0; n < outline->n_contours; n++ )
1397     {
1398       int  last;  /* index of last point in contour */
1399
1400
1401       last  = outline->contours[n];
1402       limit = outline->points + last;
1403
1404       v_start = outline->points[first];
1405       v_last  = outline->points[last];
1406
1407       v_start.x = SCALED( v_start.x );
1408       v_start.y = SCALED( v_start.y );
1409
1410       v_last.x  = SCALED( v_last.x );
1411       v_last.y  = SCALED( v_last.y );
1412
1413       v_control = v_start;
1414
1415       point = outline->points + first;
1416       tags  = outline->tags  + first;
1417       tag   = QT_FT_CURVE_TAG( tags[0] );
1418
1419       /* A contour cannot start with a cubic control point! */
1420       if ( tag == QT_FT_CURVE_TAG_CUBIC )
1421         goto Invalid_Outline;
1422
1423       /* check first point to determine origin */
1424       if ( tag == QT_FT_CURVE_TAG_CONIC )
1425       {
1426         /* first point is conic control.  Yes, this happens. */
1427         if ( QT_FT_CURVE_TAG( outline->tags[last] ) == QT_FT_CURVE_TAG_ON )
1428         {
1429           /* start at last point if it is on the curve */
1430           v_start = v_last;
1431           limit--;
1432         }
1433         else
1434         {
1435           /* if both first and last points are conic,         */
1436           /* start at their middle and record its position    */
1437           /* for closure                                      */
1438           v_start.x = ( v_start.x + v_last.x ) / 2;
1439           v_start.y = ( v_start.y + v_last.y ) / 2;
1440
1441           v_last = v_start;
1442         }
1443         point--;
1444         tags--;
1445       }
1446
1447       error = gray_move_to( &v_start, user );
1448       if ( error )
1449         goto Exit;
1450
1451       while ( point < limit )
1452       {
1453         point++;
1454         tags++;
1455
1456         tag = QT_FT_CURVE_TAG( tags[0] );
1457         switch ( tag )
1458         {
1459         case QT_FT_CURVE_TAG_ON:  /* emit a single line_to */
1460           {
1461             QT_FT_Vector  vec;
1462
1463
1464             vec.x = SCALED( point->x );
1465             vec.y = SCALED( point->y );
1466
1467             error = gray_line_to( &vec, user );
1468             if ( error )
1469               goto Exit;
1470             continue;
1471           }
1472
1473         case QT_FT_CURVE_TAG_CONIC:  /* consume conic arcs */
1474           {
1475             v_control.x = SCALED( point->x );
1476             v_control.y = SCALED( point->y );
1477
1478           Do_Conic:
1479             if ( point < limit )
1480             {
1481               QT_FT_Vector  vec;
1482               QT_FT_Vector  v_middle;
1483
1484
1485               point++;
1486               tags++;
1487               tag = QT_FT_CURVE_TAG( tags[0] );
1488
1489               vec.x = SCALED( point->x );
1490               vec.y = SCALED( point->y );
1491
1492               if ( tag == QT_FT_CURVE_TAG_ON )
1493               {
1494                 error = gray_conic_to( &v_control, &vec,
1495                                                   user );
1496                 if ( error )
1497                   goto Exit;
1498                 continue;
1499               }
1500
1501               if ( tag != QT_FT_CURVE_TAG_CONIC )
1502                 goto Invalid_Outline;
1503
1504               v_middle.x = ( v_control.x + vec.x ) / 2;
1505               v_middle.y = ( v_control.y + vec.y ) / 2;
1506
1507               error = gray_conic_to( &v_control, &v_middle,
1508                                                 user );
1509               if ( error )
1510                 goto Exit;
1511
1512               v_control = vec;
1513               goto Do_Conic;
1514             }
1515
1516             error = gray_conic_to( &v_control, &v_start,
1517                                               user );
1518             goto Close;
1519           }
1520
1521         default:  /* QT_FT_CURVE_TAG_CUBIC */
1522           {
1523             QT_FT_Vector  vec1, vec2;
1524
1525
1526             if ( point + 1 > limit                             ||
1527                  QT_FT_CURVE_TAG( tags[1] ) != QT_FT_CURVE_TAG_CUBIC )
1528               goto Invalid_Outline;
1529
1530             point += 2;
1531             tags  += 2;
1532
1533             vec1.x = SCALED( point[-2].x );
1534             vec1.y = SCALED( point[-2].y );
1535
1536             vec2.x = SCALED( point[-1].x );
1537             vec2.y = SCALED( point[-1].y );
1538
1539             if ( point <= limit )
1540             {
1541               QT_FT_Vector  vec;
1542
1543
1544               vec.x = SCALED( point->x );
1545               vec.y = SCALED( point->y );
1546
1547               error = gray_cubic_to( &vec1, &vec2, &vec, user );
1548               if ( error )
1549                 goto Exit;
1550               continue;
1551             }
1552
1553             error = gray_cubic_to( &vec1, &vec2, &v_start, user );
1554             goto Close;
1555           }
1556         }
1557       }
1558
1559       /* close the contour with a line segment */
1560       error = gray_line_to( &v_start, user );
1561
1562    Close:
1563       if ( error )
1564         goto Exit;
1565
1566       first = last + 1;
1567     }
1568
1569     return 0;
1570
1571   Exit:
1572     return error;
1573
1574   Invalid_Outline:
1575     return ErrRaster_Invalid_Outline;
1576   }
1577
1578   typedef struct  TBand_
1579   {
1580     TPos  min, max;
1581
1582   } TBand;
1583
1584
1585   static int
1586   gray_convert_glyph_inner( RAS_ARG )
1587   {
1588     volatile int  error = 0;
1589
1590     if ( qt_ft_setjmp( ras.jump_buffer ) == 0 )
1591     {
1592       error = QT_FT_Outline_Decompose( &ras.outline, &ras );
1593       gray_record_cell( RAS_VAR );
1594     }
1595     else
1596     {
1597       error = ErrRaster_Memory_Overflow;
1598     }
1599
1600     return error;
1601   }
1602
1603
1604   static int
1605   gray_convert_glyph( RAS_ARG )
1606   {
1607     TBand            bands[40];
1608     TBand* volatile  band;
1609     int volatile     n, num_bands;
1610     TPos volatile    min, max, max_y;
1611     QT_FT_BBox*      clip;
1612     int              skip;
1613
1614     ras.num_gray_spans = 0;
1615
1616     /* Set up state in the raster object */
1617     gray_compute_cbox( RAS_VAR );
1618
1619     /* clip to target bitmap, exit if nothing to do */
1620     clip = &ras.clip_box;
1621
1622     if ( ras.max_ex <= clip->xMin || ras.min_ex >= clip->xMax ||
1623          ras.max_ey <= clip->yMin || ras.min_ey >= clip->yMax )
1624       return 0;
1625
1626     if ( ras.min_ex < clip->xMin ) ras.min_ex = clip->xMin;
1627     if ( ras.min_ey < clip->yMin ) ras.min_ey = clip->yMin;
1628
1629     if ( ras.max_ex > clip->xMax ) ras.max_ex = clip->xMax;
1630     if ( ras.max_ey > clip->yMax ) ras.max_ey = clip->yMax;
1631
1632     ras.count_ex = ras.max_ex - ras.min_ex;
1633     ras.count_ey = ras.max_ey - ras.min_ey;
1634
1635     /* simple heuristic used to speed-up the bezier decomposition -- see */
1636     /* the code in gray_render_conic() and gray_render_cubic() for more  */
1637     /* details                                                           */
1638     ras.conic_level = 32;
1639     ras.cubic_level = 16;
1640
1641     {
1642       int level = 0;
1643
1644
1645       if ( ras.count_ex > 24 || ras.count_ey > 24 )
1646         level++;
1647       if ( ras.count_ex > 120 || ras.count_ey > 120 )
1648         level++;
1649
1650       ras.conic_level <<= level;
1651       ras.cubic_level <<= level;
1652     }
1653
1654     /* setup vertical bands */
1655     num_bands = (int)( ( ras.max_ey - ras.min_ey ) / ras.band_size );
1656     if ( num_bands == 0 )  num_bands = 1;
1657     if ( num_bands >= 39 ) num_bands = 39;
1658
1659     ras.band_shoot = 0;
1660
1661     min   = ras.min_ey;
1662     max_y = ras.max_ey;
1663
1664     for ( n = 0; n < num_bands; n++, min = max )
1665     {
1666       max = min + ras.band_size;
1667       if ( n == num_bands - 1 || max > max_y )
1668         max = max_y;
1669
1670       bands[0].min = min;
1671       bands[0].max = max;
1672       band         = bands;
1673
1674       while ( band >= bands )
1675       {
1676         TPos  bottom, top, middle;
1677         int   error;
1678
1679         {
1680           PCell  cells_max;
1681           int    yindex;
1682           int    cell_start, cell_end, cell_mod;
1683
1684
1685           ras.ycells = (PCell*)ras.buffer;
1686           ras.ycount = band->max - band->min;
1687
1688           cell_start = sizeof ( PCell ) * ras.ycount;
1689           cell_mod   = cell_start % sizeof ( TCell );
1690           if ( cell_mod > 0 )
1691             cell_start += sizeof ( TCell ) - cell_mod;
1692
1693           cell_end  = ras.buffer_size;
1694           cell_end -= cell_end % sizeof( TCell );
1695
1696           cells_max = (PCell)( (char*)ras.buffer + cell_end );
1697           ras.cells = (PCell)( (char*)ras.buffer + cell_start );
1698           if ( ras.cells >= cells_max )
1699             goto ReduceBands;
1700
1701           ras.max_cells = (int)(cells_max - ras.cells);
1702           if ( ras.max_cells < 2 )
1703             goto ReduceBands;
1704
1705           for ( yindex = 0; yindex < ras.ycount; yindex++ )
1706             ras.ycells[yindex] = NULL;
1707         }
1708
1709         ras.num_cells = 0;
1710         ras.invalid   = 1;
1711         ras.min_ey    = band->min;
1712         ras.max_ey    = band->max;
1713         ras.count_ey  = band->max - band->min;
1714
1715         error = gray_convert_glyph_inner( RAS_VAR );
1716
1717         if ( !error )
1718         {
1719           gray_sweep( RAS_VAR_ &ras.target );
1720           band--;
1721           continue;
1722         }
1723         else if ( error != ErrRaster_Memory_Overflow )
1724           return 1;
1725
1726       ReduceBands:
1727         /* render pool overflow; we will reduce the render band by half */
1728         bottom = band->min;
1729         top    = band->max;
1730         middle = bottom + ( ( top - bottom ) >> 1 );
1731
1732         /* This is too complex for a single scanline; there must */
1733         /* be some problems.                                     */
1734         if ( middle == bottom )
1735         {
1736 #ifdef DEBUG_GRAYS
1737           fprintf( stderr, "Rotten glyph!\n" );
1738 #endif
1739           return ErrRaster_OutOfMemory;
1740         }
1741
1742         if ( bottom-top >= ras.band_size )
1743           ras.band_shoot++;
1744
1745         band[1].min = bottom;
1746         band[1].max = middle;
1747         band[0].min = middle;
1748         band[0].max = top;
1749         band++;
1750       }
1751     }
1752
1753     if ( ras.render_span && ras.num_gray_spans > ras.skip_spans )
1754     {
1755         skip = ras.skip_spans > 0 ? ras.skip_spans : 0;
1756         ras.render_span( ras.num_gray_spans - skip,
1757                          ras.gray_spans + skip,
1758                          ras.render_span_data );
1759     }
1760
1761     ras.skip_spans -= ras.num_gray_spans;
1762
1763     if ( ras.band_shoot > 8 && ras.band_size > 16 )
1764       ras.band_size = ras.band_size / 2;
1765
1766     return 0;
1767   }
1768
1769
1770   static int
1771   gray_raster_render( QT_FT_Raster                  raster,
1772                       const QT_FT_Raster_Params*  params )
1773   {
1774     const QT_FT_Outline*  outline    = (const QT_FT_Outline*)params->source;
1775     const QT_FT_Bitmap*   target_map = params->target;
1776     PWorker            worker;
1777
1778
1779     if ( !raster || !raster->buffer || !raster->buffer_size )
1780       return ErrRaster_Invalid_Argument;
1781
1782     if ( raster->worker )
1783       raster->worker->skip_spans = params->skip_spans;
1784
1785     // If raster object and raster buffer are allocated, but
1786     // raster size isn't of the minimum size, indicate out of
1787     // memory.
1788     if (raster->buffer_allocated_size < MINIMUM_POOL_SIZE )
1789       return ErrRaster_OutOfMemory;
1790
1791     /* return immediately if the outline is empty */
1792     if ( outline->n_points == 0 || outline->n_contours <= 0 )
1793       return 0;
1794
1795     if ( !outline || !outline->contours || !outline->points )
1796       return ErrRaster_Invalid_Outline;
1797
1798     if ( outline->n_points !=
1799            outline->contours[outline->n_contours - 1] + 1 )
1800       return ErrRaster_Invalid_Outline;
1801
1802     worker = raster->worker;
1803
1804     /* if direct mode is not set, we must have a target bitmap */
1805     if ( ( params->flags & QT_FT_RASTER_FLAG_DIRECT ) == 0 )
1806     {
1807       if ( !target_map )
1808         return ErrRaster_Invalid_Argument;
1809
1810       /* nothing to do */
1811       if ( !target_map->width || !target_map->rows )
1812         return 0;
1813
1814       if ( !target_map->buffer )
1815         return ErrRaster_Invalid_Argument;
1816     }
1817
1818     /* this version does not support monochrome rendering */
1819     if ( !( params->flags & QT_FT_RASTER_FLAG_AA ) )
1820       return ErrRaster_Invalid_Mode;
1821
1822     /* compute clipping box */
1823     if ( ( params->flags & QT_FT_RASTER_FLAG_DIRECT ) == 0 )
1824     {
1825       /* compute clip box from target pixmap */
1826       ras.clip_box.xMin = 0;
1827       ras.clip_box.yMin = 0;
1828       ras.clip_box.xMax = target_map->width;
1829       ras.clip_box.yMax = target_map->rows;
1830     }
1831     else if ( params->flags & QT_FT_RASTER_FLAG_CLIP )
1832     {
1833       ras.clip_box = params->clip_box;
1834     }
1835     else
1836     {
1837       ras.clip_box.xMin = -32768L;
1838       ras.clip_box.yMin = -32768L;
1839       ras.clip_box.xMax =  32767L;
1840       ras.clip_box.yMax =  32767L;
1841     }
1842
1843     gray_init_cells( worker, raster->buffer, raster->buffer_size );
1844
1845     ras.outline   = *outline;
1846     ras.num_cells = 0;
1847     ras.invalid   = 1;
1848     ras.band_size = raster->band_size;
1849
1850     if ( target_map )
1851       ras.target = *target_map;
1852
1853     ras.render_span      = (QT_FT_Raster_Span_Func)gray_render_span;
1854     ras.render_span_data = &ras;
1855
1856     if ( params->flags & QT_FT_RASTER_FLAG_DIRECT )
1857     {
1858       ras.render_span      = (QT_FT_Raster_Span_Func)params->gray_spans;
1859       ras.render_span_data = params->user;
1860     }
1861
1862     return gray_convert_glyph( worker );
1863   }
1864
1865
1866   /**** RASTER OBJECT CREATION: In standalone mode, we simply use *****/
1867   /****                         a static object.                  *****/
1868
1869   static int
1870   gray_raster_new( QT_FT_Raster*  araster )
1871   {
1872     *araster = malloc(sizeof(TRaster));
1873     if (!*araster) {
1874         *araster = 0;
1875         return ErrRaster_Memory_Overflow;
1876     }
1877     QT_FT_MEM_ZERO(*araster, sizeof(TRaster));
1878
1879     return 0;
1880   }
1881
1882
1883   static void
1884   gray_raster_done( QT_FT_Raster  raster )
1885   {
1886     free(raster);
1887   }
1888
1889
1890   static void
1891   gray_raster_reset( QT_FT_Raster  raster,
1892                      char*      pool_base,
1893                      long       pool_size )
1894   {
1895     PRaster  rast = (PRaster)raster;
1896
1897     if ( raster )
1898     {
1899       if ( pool_base && ( pool_size >= MINIMUM_POOL_SIZE ) )
1900       {
1901         PWorker  worker = (PWorker)pool_base;
1902
1903
1904         rast->worker      = worker;
1905         rast->buffer      = pool_base +
1906                               ( ( sizeof ( TWorker ) + sizeof ( TCell ) - 1 ) &
1907                                 ~( sizeof ( TCell ) - 1 ) );
1908         rast->buffer_size = (long)( ( pool_base + pool_size ) -
1909                                     (char*)rast->buffer ) &
1910                                       ~( sizeof ( TCell ) - 1 );
1911         rast->band_size   = (int)( rast->buffer_size /
1912                                      ( sizeof ( TCell ) * 8 ) );
1913       }
1914       else if ( pool_base)
1915       { // Case when there is a raster pool allocated, but it
1916         // doesn't have the minimum size (and so memory will be reallocated)
1917           rast->buffer = pool_base;
1918           rast->worker = NULL;
1919           rast->buffer_size = pool_size;
1920       }
1921       else
1922       {
1923         rast->buffer      = NULL;
1924         rast->buffer_size = 0;
1925         rast->worker      = NULL;
1926       }
1927       rast->buffer_allocated_size = pool_size;
1928     }
1929   }
1930
1931   const QT_FT_Raster_Funcs  qt_ft_grays_raster =
1932   {
1933     QT_FT_GLYPH_FORMAT_OUTLINE,
1934
1935     (QT_FT_Raster_New_Func)     gray_raster_new,
1936     (QT_FT_Raster_Reset_Func)   gray_raster_reset,
1937     (QT_FT_Raster_Set_Mode_Func)0,
1938     (QT_FT_Raster_Render_Func)  gray_raster_render,
1939     (QT_FT_Raster_Done_Func)    gray_raster_done
1940   };
1941
1942 /* END */