/****************************************************************************

**

** All rights reserved.

** Contact: Nokia Corporation (qt-info@nokia.com)

**

** This file is part of the QtGui module of the Qt Toolkit.

**

** $QT_BEGIN_LICENSE:LGPL$

** No Commercial Usage

** This file contains pre-release code and may not be distributed.

** You may use this file in accordance with the terms and conditions

** contained in the Technology Preview License Agreement accompanying

** this package.

**

** GNU Lesser General Public License Usage

** Alternatively, this file may be used under the terms of the GNU Lesser

** General Public License version 2.1 as published by the Free Software

** Foundation and appearing in the file LICENSE.LGPL included in the

** packaging of this file.  Please review the following information to

** ensure the GNU Lesser General Public License version 2.1 requirements

** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

**

** In addition, as a special exception, Nokia gives you certain additional

** rights.  These rights are described in the Nokia Qt LGPL Exception

** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

**

** If you have questions regarding the use of this file, please contact

** Nokia at qt-info@nokia.com.

**

**

**

**

**

**

**

**

** $QT_END_LICENSE$

**

****************************************************************************/

/***************************************************************************/

/*                                                                         */

/*  qgrayraster.c, derived from ftgrays.c                                  */

/*                                                                         */

/*    A new `perfect' anti-aliasing renderer (body).                       */

/*                                                                         */

/*  Copyright 2000-2001, 2002, 2003 by                                     */

/*  David Turner, Robert Wilhelm, and Werner Lemberg.                      */

/*                                                                         */

/*  This file is part of the FreeType project, and may only be used,       */

/*  modified, and distributed under the terms of the FreeType project      */

/*  license, ../../3rdparty/freetype/docs/FTL.TXT.  By continuing to use,  */

/*  modify, or distribute this file you indicate that you have read        */

/*  the license and understand and accept it fully.                        */

/*                                                                         */

/***************************************************************************/

  /*************************************************************************/

  /*                                                                       */

  /* This file can be compiled without the rest of the FreeType engine, by */

  /* defining the _STANDALONE_ macro when compiling it.  You also need to  */

  /* put the files `ftgrays.h' and `ftimage.h' into the current            */

  /* compilation directory.  Typically, you could do something like        */

  /*                                                                       */

  /* - copy `src/smooth/ftgrays.c' (this file) to your current directory   */

  /*                                                                       */

  /* - copy `include/freetype/ftimage.h' and `src/smooth/ftgrays.h' to the */

  /*   same directory                                                      */

  /*                                                                       */

  /* - compile `ftgrays' with the _STANDALONE_ macro defined, as in        */

  /*                                                                       */

  /*     cc -c -D_STANDALONE_ ftgrays.c                                    */

  /*                                                                       */

  /* The renderer can be initialized with a call to                        */

  /* `qt_ft_gray_raster.raster_new'; an anti-aliased bitmap can be generated  */

  /* with a call to `qt_ft_gray_raster.raster_render'.                        */

  /*                                                                       */

  /* See the comments and documentation in the file `ftimage.h' for more   */

  /* details on how the raster works.                                      */

  /*                                                                       */

  /*************************************************************************/

  /*************************************************************************/

  /*                                                                       */

  /* This is a new anti-aliasing scan-converter for FreeType 2.  The       */

  /* algorithm used here is _very_ different from the one in the standard  */

  /* `ftraster' module.  Actually, `ftgrays' computes the _exact_          */

  /* coverage of the outline on each pixel cell.                           */

  /*                                                                       */

  /* It is based on ideas that I initially found in Raph Levien's          */

  /* excellent LibArt graphics library (see http://www.levien.com/libart   */

  /* for more information, though the web pages do not tell anything       */

  /* about the renderer; you'll have to dive into the source code to       */

  /* understand how it works).                                             */

  /*                                                                       */

  /* Note, however, that this is a _very_ different implementation         */

  /* compared to Raph's.  Coverage information is stored in a very         */

  /* different way, and I don't use sorted vector paths.  Also, it doesn't */

  /* use floating point values.                                            */

  /*                                                                       */

  /* This renderer has the following advantages:                           */

  /*                                                                       */

  /* - It doesn't need an intermediate bitmap.  Instead, one can supply a  */

  /*   callback function that will be called by the renderer to draw gray  */

  /*   spans on any target surface.  You can thus do direct composition on */

  /*   any kind of bitmap, provided that you give the renderer the right   */

  /*   callback.                                                           */

  /*                                                                       */

  /* - A perfect anti-aliaser, i.e., it computes the _exact_ coverage on   */

  /*   each pixel cell.                                                    */

  /*                                                                       */

  /* - It performs a single pass on the outline (the `standard' FT2        */

  /*   renderer makes two passes).                                         */

  /*                                                                       */

  /* - It can easily be modified to render to _any_ number of gray levels  */

  /*   cheaply.                                                            */

  /*                                                                       */

  /* - For small (< 20) pixel sizes, it is faster than the standard        */

  /*   renderer.                                                           */

  /*                                                                       */

  /*************************************************************************/

/* experimental support for gamma correction within the rasterizer */

#define xxxGRAYS_USE_GAMMA

  /*************************************************************************/

  /*                                                                       */

  /* The macro QT_FT_COMPONENT is used in trace mode.  It is an implicit      */

  /* parameter of the QT_FT_TRACE() and QT_FT_ERROR() macros, used to print/log  */

  /* messages during execution.                                            */

  /*                                                                       */

#undef  QT_FT_COMPONENT

#define QT_FT_COMPONENT  trace_smooth

#define ErrRaster_MemoryOverflow   -4

#if defined(VXWORKS)

#  include <vxWorksCommon.h>    /* needed for setjmp.h */

#endif

#include <string.h>             /* for qt_ft_memcpy() */

#include <setjmp.h>

#include <limits.h>

#define QT_FT_UINT_MAX  UINT_MAX

#define qt_ft_memset   memset

#define qt_ft_setjmp   setjmp

#define qt_ft_longjmp  longjmp

#define qt_ft_jmp_buf  jmp_buf

#define ErrRaster_Invalid_Mode      -2

#define ErrRaster_Invalid_Outline   -1

#define ErrRaster_Invalid_Argument  -3

#define ErrRaster_Memory_Overflow   -4

#define QT_FT_BEGIN_HEADER

#define QT_FT_END_HEADER

#include <private/qrasterdefs_p.h>

#include <private/qgrayraster_p.h>

#include <stdlib.h>

#include <stdio.h>

  /* This macro is used to indicate that a function parameter is unused. */

  /* Its purpose is simply to reduce compiler warnings.  Note also that  */

  /* simply defining it as `(void)x' doesn't avoid warnings with certain */

  /* ANSI compilers (e.g. LCC).                                          */

#define QT_FT_UNUSED( x )  (x) = (x)

  /* Disable the tracing mechanism for simplicity -- developers can      */

  /* activate it easily by redefining these two macros.                  */

#ifndef QT_FT_ERROR

#define QT_FT_ERROR( x )  do ; while ( 0 )     /* nothing */

#endif

#ifndef QT_FT_TRACE

#define QT_FT_TRACE( x )  do ; while ( 0 )     /* nothing */

#endif

#ifndef QT_FT_MEM_SET

#define QT_FT_MEM_SET( d, s, c )  qt_ft_memset( d, s, c )

#endif

#ifndef QT_FT_MEM_ZERO

#define QT_FT_MEM_ZERO( dest, count )  QT_FT_MEM_SET( dest, 0, count )

#endif

  /* define this to dump debugging information */

#define xxxDEBUG_GRAYS

#define RAS_ARG   PWorker  worker

#define RAS_ARG_  PWorker  worker,

#define RAS_VAR   worker

#define RAS_VAR_  worker,

#define ras       (*worker)

  /* must be at least 6 bits! */

#define PIXEL_BITS  8

#define ONE_PIXEL       ( 1L << PIXEL_BITS )

#define PIXEL_MASK      ( -1L << PIXEL_BITS )

#define TRUNC( x )      ( (TCoord)( (x) >> PIXEL_BITS ) )

#define SUBPIXELS( x )  ( (TPos)(x) << PIXEL_BITS )

#define FLOOR( x )      ( (x) & -ONE_PIXEL )

#define CEILING( x )    ( ( (x) + ONE_PIXEL - 1 ) & -ONE_PIXEL )

#define ROUND( x )      ( ( (x) + ONE_PIXEL / 2 ) & -ONE_PIXEL )

#if PIXEL_BITS >= 6

#define UPSCALE( x )    ( (x) << ( PIXEL_BITS - 6 ) )

#define DOWNSCALE( x )  ( (x) >> ( PIXEL_BITS - 6 ) )

#else

#define UPSCALE( x )    ( (x) >> ( 6 - PIXEL_BITS ) )

#define DOWNSCALE( x )  ( (x) << ( 6 - PIXEL_BITS ) )

#endif

  /*************************************************************************/

  /*                                                                       */

  /*   TYPE DEFINITIONS                                                    */

  /*                                                                       */

  /* don't change the following types to QT_FT_Int or QT_FT_Pos, since we might */

  /* need to define them to "float" or "double" when experimenting with   */

  /* new algorithms                                                       */

  typedef int   TCoord;   /* integer scanline/pixel coordinate */

  typedef long  TPos;     /* sub-pixel coordinate              */

  /* determine the type used to store cell areas.  This normally takes at */

  /* least PIXEL_BITS*2 + 1 bits.  On 16-bit systems, we need to use      */

  /* `long' instead of `int', otherwise bad things happen                 */

#if PIXEL_BITS <= 7

  typedef int  TArea;

#else /* PIXEL_BITS >= 8 */

  /* approximately determine the size of integers using an ANSI-C header */

#if QT_FT_UINT_MAX == 0xFFFFU

  typedef long  TArea;

#else

  typedef int   TArea;

#endif

#endif /* PIXEL_BITS >= 8 */

  /* maximal number of gray spans in a call to the span callback */

#define QT_FT_MAX_GRAY_SPANS  256

  typedef struct TCell_*  PCell;

  typedef struct  TCell_

  {

    int    x;

    int    cover;

    TArea  area;

    PCell  next;

  } TCell;

  typedef struct  TWorker_

  {

    TCoord  ex, ey;

    TPos    min_ex, max_ex;

    TPos    min_ey, max_ey;

    TPos    count_ex, count_ey;

    TArea   area;

    int     cover;

    int     invalid;

    PCell   cells;

    int     max_cells;

    int     num_cells;

    TCoord  cx, cy;

    TPos    x,  y;

    TPos    last_ey;

    QT_FT_Vector   bez_stack[32 * 3 + 1];

    int         lev_stack[32];

    QT_FT_Outline  outline;

    QT_FT_Bitmap   target;

    QT_FT_BBox     clip_box;

    QT_FT_Span     gray_spans[QT_FT_MAX_GRAY_SPANS];

    int         num_gray_spans;

    QT_FT_Raster_Span_Func  render_span;

    void*                render_span_data;

    int  band_size;

    int  band_shoot;

    int  conic_level;

    int  cubic_level;

    qt_ft_jmp_buf  jump_buffer;

    void*       buffer;

    long        buffer_size;

    PCell*     ycells;

    int        ycount;

  } TWorker, *PWorker;

  typedef struct TRaster_

  {

    void*    buffer;

    long     buffer_size;

    int      band_size;

    void*    memory;

    PWorker  worker;

  } TRaster, *PRaster;

  /*************************************************************************/

  /*                                                                       */

  /* Initialize the cells table.                                           */

  /*                                                                       */

  static void

  gray_init_cells( RAS_ARG_ void*  buffer,

                   long            byte_size )

  {

    ras.buffer      = buffer;

    ras.buffer_size = byte_size;

    ras.ycells      = (PCell*) buffer;

    ras.cells       = NULL;

    ras.max_cells   = 0;

    ras.num_cells   = 0;

    ras.area        = 0;

    ras.cover       = 0;

    ras.invalid     = 1;

  }

  /*************************************************************************/

  /*                                                                       */

  /* Compute the outline bounding box.                                     */

  /*                                                                       */

  static void

  gray_compute_cbox( RAS_ARG )

  {

    QT_FT_Outline*  outline = &ras.outline;

    QT_FT_Vector*   vec     = outline->points;

    QT_FT_Vector*   limit   = vec + outline->n_points;

    if ( outline->n_points <= 0 )

    {

      ras.min_ex = ras.max_ex = 0;

      ras.min_ey = ras.max_ey = 0;

      return;

    }

    ras.min_ex = ras.max_ex = vec->x;

    ras.min_ey = ras.max_ey = vec->y;

    vec++;

    for ( ; vec < limit; vec++ )

    {

      TPos  x = vec->x;

      TPos  y = vec->y;

      if ( x < ras.min_ex ) ras.min_ex = x;

      if ( x > ras.max_ex ) ras.max_ex = x;

      if ( y < ras.min_ey ) ras.min_ey = y;

      if ( y > ras.max_ey ) ras.max_ey = y;

    }

    /* truncate the bounding box to integer pixels */

    ras.min_ex = ras.min_ex >> 6;

    ras.min_ey = ras.min_ey >> 6;

    ras.max_ex = ( ras.max_ex + 63 ) >> 6;

    ras.max_ey = ( ras.max_ey + 63 ) >> 6;

  }

  /*************************************************************************/

  /*                                                                       */

  /* Record the current cell in the table.                                 */

  /*                                                                       */

  static PCell

  gray_find_cell( RAS_ARG )

  {

    PCell  *pcell, cell;

    int     x = ras.ex;

    if ( x > ras.max_ex )

      x = ras.max_ex;

    pcell = &ras.ycells[ras.ey];

    for (;;)

    {

      cell = *pcell;

      if ( cell == NULL || cell->x > x )

        break;

      if ( cell->x == x )

        goto Exit;

      pcell = &cell->next;

    }

    if ( ras.num_cells >= ras.max_cells )

      qt_ft_longjmp( ras.jump_buffer, 1 );

    cell        = ras.cells + ras.num_cells++;

    cell->x     = x;

    cell->area  = 0;

    cell->cover = 0;

    cell->next  = *pcell;

    *pcell      = cell;

  Exit:

    return cell;

  }

  static void

  gray_record_cell( RAS_ARG )

  {

    if ( !ras.invalid && ( ras.area | ras.cover ) )

    {

      PCell  cell = gray_find_cell( RAS_VAR );

      cell->area  += ras.area;

      cell->cover += ras.cover;

    }

  }

  /*************************************************************************/

  /*                                                                       */

  /* Set the current cell to a new position.                               */

  /*                                                                       */

  static void

  gray_set_cell( RAS_ARG_ TCoord  ex,

                          TCoord  ey )

  {

    /* Move the cell pointer to a new position.  We set the `invalid'      */

    /* flag to indicate that the cell isn't part of those we're interested */

    /* in during the render phase.  This means that:                       */

    /*                                                                     */

    /* . the new vertical position must be within min_ey..max_ey-1.        */

    /* . the new horizontal position must be strictly less than max_ex     */

    /*                                                                     */

    /* Note that if a cell is to the left of the clipping region, it is    */

    /* actually set to the (min_ex-1) horizontal position.                 */

    /* All cells that are on the left of the clipping region go to the */

    /* min_ex - 1 horizontal position.                                 */

    ey -= ras.min_ey;

    if ( ex > ras.max_ex )

      ex = ras.max_ex;

    ex -= ras.min_ex;

    if ( ex < 0 )

      ex = -1;

    /* are we moving to a different cell ? */

    if ( ex != ras.ex || ey != ras.ey )

    {

      /* record the current one if it is valid */

      if ( !ras.invalid )

        gray_record_cell( RAS_VAR );

      ras.area  = 0;

      ras.cover = 0;

    }

    ras.ex      = ex;

    ras.ey      = ey;

    ras.invalid = ( (unsigned)ey >= (unsigned)ras.count_ey ||

                              ex >= ras.count_ex           );

  }

  /*************************************************************************/

  /*                                                                       */

  /* Start a new contour at a given cell.                                  */

  /*                                                                       */

  static void

  gray_start_cell( RAS_ARG_ TCoord  ex,

                            TCoord  ey )

  {

    if ( ex > ras.max_ex )

      ex = (TCoord)( ras.max_ex );

    if ( ex < ras.min_ex )

      ex = (TCoord)( ras.min_ex - 1 );

    ras.area    = 0;

    ras.cover   = 0;

    ras.ex      = ex - ras.min_ex;

    ras.ey      = ey - ras.min_ey;

    ras.last_ey = SUBPIXELS( ey );

    ras.invalid = 0;

    gray_set_cell( RAS_VAR_ ex, ey );

  }