/*******************************************************************
 *
 *  ttraster.c                                                  1.4
 *
 *  The FreeType glyph rasterizer (body).
 *
 *  Copyright 1996, 1997 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, LICENSE.TXT. By continuing to use, modify, or distribute
 *  this file you indicate that you have read the license and
 *  understand and accept it fully.
 *
 *  NOTES:
 *
 *  This version supports the following:
 *
 *    - direct grayscaling
 *    - sub-banding
 *    - drop-out modes 4 and 5
 *    - second pass for complete drop-out control (bitmap only)
 *    - variable precision
 *
 *
 *   Changes between 1.4 and 1.3:
 *
 *   Mainly performance tunings:
 *
 *   - Line_Down() and Bezier_Down() now use the functions Line_Up()
 *     and Bezier_Up() to do their work.
 *   - optimized Split_Bezier()
 *   - optimized linked lists used during sweeps
 *
 *   Changes between 1.2 and 1.3:
 *
 *     - made the engine optionaly re-entrant.  Saves a lot
 *       of code for a moderate performance hit.
 *
 ******************************************************************/

#include "ttraster.h"
#include "tterror.h"
#include "tttypes.h"
#include "ttengine.h"

#include "ttmemory.h"

/* The default render pool size */
#define  RASTER_RENDER_POOL   64000

/* The size of the two-lines intermediate bitmap used */
/* for anti-aliasing                                  */
#define  RASTER_GRAY_LINES    2048


#define Raster_Err_None              TT_Err_Ok
#define Raster_Err_Not_Ini           TT_Err_Raster_Not_Initialized
#define Raster_Err_Overflow          TT_Err_Raster_Pool_Overflow
#define Raster_Err_Neg_Height        TT_Err_Raster_Negative_Height
#define Raster_Err_Invalid           TT_Err_Raster_Invalid_Value
#define Raster_Err_Gray_Unsupported  TT_Err_Raster_Gray_Unsupported


/* Define this if you want to use the 'MulDiv' function from 'ttcalc'     */
/* (it computes (A*B)/C with 64 bits intermediate accuracy.  However, for */
/* 99.9% of screen display, this operation can be done directly with      */
/* good accuracy, because 'B' is only a 6bit integer).                    */
/*                                                                        */
/* Note that some compilers can manage directly 'a*b/c' with intermediate */
/* accuracy (GCC can use long longs, for example).  Using the unsecure    */
/* definition of MulDiv would then be sufficient.                         */
/*                                                                        */
/* The SECURE_COMPUTATIONS option is probably a good option for 16 bits   */
/* compilers.                                                             */

#ifdef SECURE_COMPUTATIONS
  #include "ttcalc.h"
#else
  #define FMulDiv( a, b, c )  ( (a) * (b) / (c) )
#endif


/* Define DEBUG_RASTER if you want to generate a debug version of the  */
/* rasterizer.  This will progressively draw the glyphs while all the  */
/* computation are done directly on the graphics screen (the glyphs    */
/* will be inverted).                                                  */

/* Note that DEBUG_RASTER should only be used for debugging with b/w   */
/* rendering, not with gray levels.                                    */

/* The definition of DEBUG_RASTER should appear in the file            */
/* "ttconfig.h".                                                       */

#ifdef DEBUG_RASTER
  extern char*  Vio;  /* A pointer to VRAM or display buffer */
#endif


/* The rasterizer is a very general purpose component, please leave */
/* the following redefinitions there (you never know your target    */
/* environment).                                                    */

#ifndef TRUE
#define TRUE   1
#endif

#ifndef FALSE
#define FALSE  0
#endif

#ifndef NULL
#define NULL  (void*)0
#endif

#define MaxBezier  32   /* The maximum number of stacked Bezier curves. */
                        /* Setting this constant to more than 32 is a   */
                        /* pure waste of space.                         */

#define Pixel_Bits  6   /* fractional bits of input coordinates */

  /* States of each line, arc and profile */
  enum  _TStates
  {
    Unknown,
    Ascending,
    Descending,
    Flat
  };

  typedef enum _TStates  TStates;

  struct  _TProfile;
  typedef struct _TProfile  TProfile;
  typedef TProfile*         PProfile;

  struct  _TProfile
  {                                                                     
    Int         flow;        /* Profile orientation: Asc/Descending      */
    Int         height;      /* profile's height in scanlines            */
    Int         start;       /* profile's starting scanline              */
    PStorage    offset;      /* start of profile's data in render pool   */

    PProfile    link;        /* link to next profile                     */

    TT_F26Dot6  X;           /* current coordinate during sweep          */
    Int         countL;      /* number of lines to step before this      */
                             /* profile becomes drawable                 */

    PProfile    next;        /* next profile in same contour, used       */
                             /* during drop-out control                  */
  };

  typedef PProfile   TProfileList;
  typedef PProfile*  PProfileList;


  /* I use the classic trick of two dummy records for the head and tail  */
  /* of a linked list; this reduces tests in insertion/deletion/sorting. */
  /* NOTE: used during sweeps only.                                      */

  /* Simple record used to implement a stack of bands, required */
  /* by the sub-banding mechanism                               */

  struct  _TBand
  {
    Int  y_min;   /* band's minimum */
    Int  y_max;   /* band's maximum */
  };

  typedef struct _TBand  TBand;


#define AlignProfileSize  ( (sizeof ( TProfile ) + 7) / 4)


  /* Left fill bitmask */
  static const unsigned char  LMask[8] = 
    { 0xFF, 0x7F, 0x3F, 0x1F, 0x0F, 0x07, 0x03, 0x01 };

  /* Right fill bitmask */
  static const unsigned char  RMask[8] =
    { 0x80, 0xC0, 0xE0, 0xF0, 0xF8, 0xFC, 0xFE, 0xFF };

  /* prototypes used for sweep function dispatch */
  typedef void  Function_Sweep_Init( RAS_ARGS int*  min, int*  max );

  typedef void  Function_Sweep_Span( RAS_ARGS int         y,
                                              TT_F26Dot6  x1,
                                              TT_F26Dot6  x2,
                                              PProfile    left,
                                              PProfile    right );
                    
  typedef void  Function_Sweep_Step( RAS_ARG );


/* NOTE: These operations are only valid on 2's complement processors */

#define FLOOR( x )    ( (x) & -ras.precision )
#define CEILING( x )  ( ((x) + ras.precision - 1) & -ras.precision )
#define TRUNC( x )    ( (signed long)(x) >> ras.precision_bits )
#define FRAC( x )     ( (x) & (ras.precision - 1) )
#define SCALED( x )   ( ((x) << ras.scale_shift) - ras.precision_half )

#ifdef DEBUG_RASTER
#define DEBUG_PSET  Pset()
#else
#define DEBUG_PSET  
#endif

  struct  _TPoint
  {
    Long  x, y;
  };

  typedef struct _TPoint  TPoint;


  /* Note that I have moved the location of some fields in the */
  /* structure to ensure that the most used variables are used */
  /* at the top.  Thus, their offset can be coded with less    */
  /* opcodes, and it results in a smaller executable.          */

  struct  _TRaster_Instance
  {
    Int       precision_bits;       /* precision related variables */
    Int       precision;
    Int       precision_half;
    Long      precision_mask;
    Int       precision_shift;
    Int       precision_step;

    Int       scale_shift;        /* == precision_shift   for bitmaps */
                                  /* == precision_shift+1 for pixmaps */

    PStorage  buff;                 /* The profiles buffer          */
    PStorage  maxBuff;              /* Profiles buffer size         */
    PStorage  top;                  /* Current cursor in buffer     */

    Int       error;

    PByte     flags;                /* current flags table    */
    PUShort   outs;                 /* current outlines table */

    Int       nPoints;              /* number of points in current glyph   */
    Int       nContours;            /* number of contours in current glyph */

    TPoint*   arc;                  /* current Bezier arc pointer */

    Int       bWidth;               /* target bitmap width  */
    PByte     bTarget;              /* target bitmap buffer */
    PByte     gTarget;              /* target pixmap buffer */

    Long      lastX, lastY, minY, maxY;

    Int       num_Profs;            /* current number of profiles */

    Bool      fresh;                /* signals a fresh new profile which */ 
                                    /* 'start' field must be completed   */
    Bool      joint;                /* signals that the last arc ended   */
                                    /* exactly on a scanline.  Allows    */
                                    /* removal of doublets               */
    PProfile  cProfile;             /* current profile                   */
    PProfile  fProfile;             /* head of linked list of profiles   */
    PProfile  gProfile;             /* contour's first profile in case   */
                                    /* of impact                         */
    TStates   state;                /* rendering state */
   
    TT_Raster_Map  target;          /* description of target bit/pixmap */

    Int       traceOfs;             /* current offset in target bitmap */
    Int       traceG;               /* current offset in target pixmap */

    Int       traceIncr;            /* sweep's increment in target bitmap */

    Int       gray_min_x;           /* current min x during gray rendering */
    Int       gray_max_x;           /* current max x during gray rendering */

    /* dispatch variables */

    Function_Sweep_Init*  Proc_Sweep_Init;
    Function_Sweep_Span*  Proc_Sweep_Span;
    Function_Sweep_Span*  Proc_Sweep_Drop;
    Function_Sweep_Step*  Proc_Sweep_Step;

    PStorage  x_coord;              /* current ras.x_coord table */
    PStorage  y_coord;              /* current ras.y_coord table */

    Byte      dropOutControl;       /* current drop_out control method */

    char      grays[5];         /* Palette of gray levels used for render */

    Byte*     gray_lines;       /* Intermediate table used to render the   */
                                /* graylevels pixmaps.                     */
                                /* gray_lines is a buffer holding two      */
                                /* monochrome scanlines                    */
    Int       gray_width;       /* width in bytes of one monochrome        */
                                /* intermediate scanline of gray_lines.    */
                                /* Each gray pixel takes 2 bits long there */

                        /* The gray_lines must hold 2 lines, thus with size */
                        /* in bytes of at least 'gray_width*2'              */

    Bool      second_pass;      /* indicates wether a horizontal pass      */
                                /* should be performed to control drop-out */
                                /* accurately when calling Render_Glyph.   */
                                /* Note that there is no horizontal pass   */
                                /* during gray rendering.                  */
    TPoint    arcs[2 * MaxBezier + 1];      /* The Bezier stack */

    TBand     band_stack[16];       /* band stack used for sub-banding */
    Int       band_top;             /* band stack top                  */

    Int       count_table[256];     /* Look-up table used to quickly count */
                                    /* set bits in a gray 2x2 cell         */
  };


#ifdef TT_STATIC_RASTER

  static TRaster_Instance  cur_ras;

#define ras  cur_ras

#else

#define ras  (*raster)

#endif /* TT_STATIC_RASTER */


#ifdef DEBUG_RASTER

  /************************************************/
  /*                                              */
  /* Pset:                                        */
  /*                                              */
  /*  Used for debugging only.  Plots a point     */
  /*  in VRAM during rendering (not afterwards).  */
  /*                                              */
  /* NOTE:  This procedure relies on the value    */
  /*        of cProfile->start, which may not     */
  /*        be set when Pset is called sometimes. */
  /*        This will usually result in a dot     */
  /*        plotted on the first screen scanline  */
  /*        (far away its original position).     */
  /*                                              */
  /*        This "bug" reflects nothing wrong     */
  /*        in the current implementation, and    */
  /*        the bitmap is rendered correctly,     */
  /*        so don't panic if you see 'flying'    */
  /*        dots in debugging mode.               */
  /*                                              */
  /*  - David                                     */
  /*                                              */
  /************************************************/

  static void  Pset( RAS_ARG )
  {
    Long  o;
    Long  x;


    x = ras.top[-1];

    switch ( ras.cProfile->flow )
    {
    case TT_Flow_Up:
      o = Vio_ScanLineWidth *
         ( ras.top-ras.cProfile->offset + ras.cProfile->start ) +
         ( x / (ras.precision*8) );
      break;

    case TT_Flow_Down:
      o = Vio_ScanLineWidth *
         ( ras.cProfile->start-ras.top + ras.cProfile->offset ) +
         ( x / (ras.precision*8) );
      break;
    }

    if ( o > 0 )
      Vio[o] |= (unsigned)0x80 >> ( (x/ras.precision) & 7 );
  }


  static void  Clear_Band( RAS_ARGS Int  y1, Int  y2 )
  {
    MEM_Set( Vio + y1*Vio_ScanLineWidth, (y2-y1+1)*Vio_ScanLineWidth, 0 );
  }

#endif /* DEBUG_RASTER */


/************************************************************************/
/*                                                                      */
/* Function:    Set_High_Precision                                      */
/*                                                                      */
/* Description: Sets precision variables according to param flag.       */
/*                                                                      */
/* Input:       High     set to True for high precision (typically for  */
/*                       ppem < 18), false otherwise.                   */
/*                                                                      */
/************************************************************************/

  static void  Set_High_Precision( RAS_ARGS int  High )
  {
    if ( High )
    {
      ras.precision_bits = 10;
      ras.precision_step = 128;
    }
    else
    {
      ras.precision_bits = 6;
      ras.precision_step = 32;
    }

    ras.precision       = 1 << ras.precision_bits;
    ras.precision_half  = ras.precision / 2;
    ras.precision_shift = ras.precision_bits - Pixel_Bits;
    ras.precision_mask  = -ras.precision;
  }


/****************************************************************************/
/*                                                                          */
/* Function:    New_Profile                                                 */
/*                                                                          */
/* Description: Creates a new Profile in the render pool.                   */
/*                                                                          */
/* Input:       aState   state/orientation of the new Profile               */
/*                                                                          */
/* Returns:     SUCCESS on success.                                         */
/*              FAILURE in case of overflow or of incoherent Profile.       */
/*                                                                          */
/****************************************************************************/

  static Bool  New_Profile( RAS_ARGS TStates  aState )
  {
    if ( !ras.fProfile )
    {
      ras.cProfile  = (PProfile)ras.top;
      ras.fProfile  = ras.cProfile;
      ras.top      += AlignProfileSize;
    }

    if ( ras.top >= ras.maxBuff )
    {
      ras.error = Raster_Err_Overflow;
      return FAILURE;
    }

    switch ( aState )
    {
    case Ascending:
      ras.cProfile->flow = TT_Flow_Up;
      break;

    case Descending:
      ras.cProfile->flow = TT_Flow_Down;
      break;

    default:
      ras.error = Raster_Err_Invalid;
      return FAILURE;
    }

    ras.cProfile->start  = 0;
    ras.cProfile->height = 0;
    ras.cProfile->offset = ras.top;
    ras.cProfile->link   = (PProfile)0;
    ras.cProfile->next   = (PProfile)0;

    if ( !ras.gProfile )
      ras.gProfile = ras.cProfile;

    ras.state = aState;
    ras.fresh = TRUE;
    ras.joint = FALSE;

    return SUCCESS;
  }


/****************************************************************************/
/*                                                                          */
/* Function:    End_Profile                                                 */
/*                                                                          */
/* Description: Finalizes the current Profile.                              */
/*                                                                          */
/* Input:       None                                                        */
/*                                                                          */
/* Returns:     SUCCESS on success.                                         */
/*              FAILURE in case of overflow or incoherency.                 */
/*                                                                          */
/****************************************************************************/

  static Bool  End_Profile( RAS_ARG )
  {
    Int       h;
    PProfile  oldProfile;


    h = ras.top - ras.cProfile->offset;

    if ( h < 0 )
    {
      ras.error = Raster_Err_Neg_Height;
      return FAILURE;
    }

    if ( h > 0 )
    {
      oldProfile           = ras.cProfile;
      ras.cProfile->height = h;
      ras.cProfile         = (PProfile)ras.top;

      ras.top             += AlignProfileSize;

      ras.cProfile->height = 0;
      ras.cProfile->offset = ras.top;
      oldProfile->next     = ras.cProfile;
      ras.num_Profs++;
    }

    if ( ras.top >= ras.maxBuff )
    {
      ras.error = Raster_Err_Overflow;
      return FAILURE;
    }

    ras.joint = FALSE;

    return SUCCESS;
  }


/****************************************************************************/
/*                                                                          */
/* Function:    Finalize_Profile_Table                                      */
/*                                                                          */
/* Description: Adjusts all links in the Profiles list.                     */
/*                                                                          */
/* Input:       None                                                        */
/*                                                                          */
/* Returns:     None.                                                       */
/*                                                                          */
/****************************************************************************/

  static void  Finalize_Profile_Table( RAS_ARG )
  {
    Int       n;
    PProfile  p;


    n = ras.num_Profs;

    if ( n > 1 )
    {
      p = ras.fProfile;
      while ( n > 1 )
      {
        p->link = (PProfile)( p->offset + p->height );
        p       = p->link;
        n--;
      }
      p->link = NULL;
    }
    else
      ras.fProfile = NULL;
  }


/****************************************************************************/
/*                                                                          */
/* Function:    Split_Bezier                                                */
/*                                                                          */
/* Description: Subdivides one Bezier arc into two joint                    */
/*              sub-arcs in the Bezier stack.                               */
/*                                                                          */
/* Input:       None (subdivided bezier is taken from the top of the        */
/*              stack).                                                     */
/*                                                                          */
/* Returns:     None.                                                       */
/*                                                                          */
/*                                                                          */
/* Note:  This routine is the 'beef' of this component. It is  _the_        */
/*        inner loop that should be optimized to hell to get the            */
/*        best performance.                                                 */
/*                                                                          */
/****************************************************************************/

  static void  Split_Bezier( TPoint*  base )
  {
    Long     a, b;


    base[4].x = base[2].x;
    b = base[1].x;
    a = base[3].x = ( base[2].x + b )/2;
    b = base[1].x = ( base[0].x + b )/2;
    base[2].x = (a+b)/2;

    base[4].y = base[2].y;
    b = base[1].y;
    a = base[3].y = ( base[2].y + b )/2;
    b = base[1].y = ( base[0].y + b )/2;
    base[2].y = (a+b)/2;

    /* hand optimised.  gcc doesn't seem too good at common expression */
    /* substitution and instruction scheduling ;-)                     */
  }


/****************************************************************************/
/*                                                                          */
/* Function:    Push_Bezier                                                 */
/*                                                                          */
/* Description: Clears the Bezier stack and pushes a new arc on top of it.  */
/*                                                                          */
/* Input:       x1,y1 x2,y2 x3,y3  new Bezier arc                           */
/*                                                                          */
/* Returns:     None.                                                       */
/*                                                                          */
/****************************************************************************/

  static void  Push_Bezier( RAS_ARGS Long  x1, Long  y1,
                                     Long  x2, Long  y2,
                                     Long  x3, Long  y3 ) 
  {
    ras.arc      = ras.arcs;
    ras.arc[2].x = x1; ras.arc[2].y = y1;
    ras.arc[1].x = x2; ras.arc[1].y = y2;
    ras.arc[0].x = x3; ras.arc[0].y = y3;
  }


/****************************************************************************/
/*                                                                          */
/* Function:    Line_Up                                                     */
/*                                                                          */
/* Description: Computes the x-coordinates of an ascending line segment     */
/*              and stores them in the render pool.                         */
/*                                                                          */
/* Input:       x1,y1,x2,y2  Segment start (x1,y1) and end (x2,y2) points   */
/*                                                                          */
/* Returns:     SUCCESS on success.                                         */
/*              FAILURE on Render Pool overflow.                            */
/*                                                                          */
/****************************************************************************/

  static Bool  Line_Up( RAS_ARGS Long  x1, Long  y1, 
                                 Long  x2, Long  y2,
                                 Long  miny, Long  maxy )
  {
    Long  Dx, Dy;
    Int   e1, e2, f1, f2, size;
    Long  Ix, Rx, Ax;

    PStorage  top;


    Dx = x2 - x1;
    Dy = y2 - y1;

    if ( Dy <= 0 || y2 < miny || y1 > maxy )
      return SUCCESS;

    if ( y1 < miny )
    {
      x1 += FMulDiv( Dx, miny - y1, Dy );
      e1  = TRUNC( miny );
      f1  = 0;
    }
    else
    {
      e1 = TRUNC( y1 );
      f1 = FRAC( y1 );
    }

    if ( y2 > maxy )
    {
      /* x2 += FMulDiv( Dx, maxy-y2, Dy );  UNNECESSARY */
      e2  = TRUNC( maxy );
      f2  = 0;
    }
    else
    {
      e2 = TRUNC( y2 );
      f2 = FRAC( y2 );
    }

    if ( f1 > 0 )
      if ( e1 == e2 ) return SUCCESS;
      else
      {
        x1 += FMulDiv( Dx, ras.precision - f1, Dy );
        e1 += 1;
      }
    else
      if ( ras.joint )
      {
        ras.top--;
        ras.joint = FALSE;
      }

    ras.joint = ( f2 == 0 );

    if ( ras.fresh )
    {
      ras.cProfile->start = e1;
      ras.fresh           = FALSE;
    }

    size = e2 - e1 + 1;
    if ( ras.top + size >= ras.maxBuff )
    {
      ras.error = Raster_Err_Overflow;
      return FAILURE;
    }

    if ( Dx > 0 )
    {
      Ix = (ras.precision*Dx) / Dy;
      Rx = (ras.precision*Dx) % Dy;
      Dx = 1;
    }
    else
    {
      Ix = -( (ras.precision*-Dx) / Dy );
      Rx =    (ras.precision*-Dx) % Dy;
      Dx = -1;
    }

    Ax  = -Dy;
    top = ras.top;

    while ( size > 0 ) 
    {
      *top++ = x1;

      DEBUG_PSET;

      x1 += Ix;
      Ax += Rx;
      if ( Ax >= 0 )
      {
        Ax -= Dy;
        x1 += Dx;
      }
      size--;
    }

    ras.top = top;
    return SUCCESS;
  }


  static Bool  Line_Down( RAS_ARGS Long  x1, Long  y1, 
                                   Long  x2, Long  y2,
                                   Long  miny, Long  maxy )
  {
    Bool result, fresh;


    fresh  = ras.fresh;

    result = Line_Up( RAS_VARS x1, -y1, x2, -y2, -maxy, -miny );

    if ( fresh && !ras.fresh ) 
      ras.cProfile->start = -ras.cProfile->start;

    return result;
  }


/****************************************************************************/
/*                                                                          */
/* Function:    Bezier_Up                                                   */
/*                                                                          */
/* Description: Computes thes x-coordinates of an ascending bezier arc      */
/*              and stores them in the render pool.                         */
/*                                                                          */
/* Input:       None.  The arc is taken from the top of the Bezier stack.   */
/*                                                                          */
/* Returns:     SUCCESS on success.                                         */
/*              FAILURE on Render Pool overflow.                            */
/*                                                                          */
/****************************************************************************/

  static Bool  Bezier_Up( RAS_ARGS Long  miny, Long  maxy )
  {
    Long  y1, y2, e, e2, e0;
    Int   f1;

    TPoint*  arc;
    TPoint*  start_arc;

    PStorage top;


    arc = ras.arc;
    y1  = arc[2].y;
    y2  = arc[0].y;
    top = ras.top; 

    if ( y2 < miny || y1 > maxy )
      goto Fin;
    
    e2 = FLOOR( y2 );

    if ( e2 > maxy )
      e2 = maxy;

    e0 = miny;

    if ( y1 < miny )
      e = miny;
    else
    {
      e  = CEILING( y1 );
      f1 = FRAC( y1 );
      e0 = e;

      if ( f1 == 0 )
      {
        if ( ras.joint )
        {
          top--;
          ras.joint = FALSE;
        }

        *top++ = arc[2].x;

        DEBUG_PSET;

        e += ras.precision;
      }
    }

    if ( ras.fresh )
    {
      ras.cProfile->start = TRUNC( e0 );
      ras.fresh = FALSE;
    }

    if ( e2 < e )
      goto Fin;

    if ( ( top + TRUNC( e2 - e ) + 1 ) >= ras.maxBuff )
    {
      ras.top   = top;
      ras.error = Raster_Err_Overflow;
      return FAILURE;
    }

    start_arc = arc;

    while ( arc >= start_arc && e <= e2 )
    {
      ras.joint = FALSE;

      y2 = arc[0].y;

      if ( y2 > e )
      {
        y1 = arc[2].y;
        if ( y2 - y1 >= ras.precision_step )
        {
          Split_Bezier( arc );
          arc += 2;
        }
        else
        {
          *top++ = arc[2].x + 
                   FMulDiv( arc[0].x-arc[2].x, 
                            e - y1, 
                            y2 - y1 );
          DEBUG_PSET;
            
          arc -= 2;
          e   += ras.precision;
        }
      }
      else
      {
        if ( y2 == e )
        {
          ras.joint  = TRUE;
          *top++     = arc[0].x;
        
          DEBUG_PSET;
        
          e += ras.precision;
        }
        arc -= 2;
      }
    }

  Fin:
    ras.top  = top;
    ras.arc -= 2;
    return SUCCESS;
  }


/****************************************************************************/
/*                                                                          */
/* Function:    Bezier_Down                                                 */
/*                                                                          */
/* Description: Computes the x-coordinates of a descending bezier arc       */
/*              and stores them in the render pool.                         */
/*                                                                          */
/* Input:       None.  Arc is taken from the top of the Bezier stack.       */
/*                                                                          */
/* Returns:     SUCCESS on success.                                         */
/*              FAILURE on Render Pool overflow.                            */
/*                                                                          */
/****************************************************************************/

  static Bool  Bezier_Down( RAS_ARGS Long  miny, Long  maxy )
  {
    TPoint*  arc = ras.arc;
    Bool     result, fresh;


    arc[0].y = -arc[0].y;
    arc[1].y = -arc[1].y; 
    arc[2].y = -arc[2].y;

    fresh = ras.fresh;

    result = Bezier_Up( RAS_VARS -maxy, -miny );

    if ( fresh && !ras.fresh )
      ras.cProfile->start = -ras.cProfile->start;

    arc[0].y = -arc[0].y;
    return result;
  }


/****************************************************************************/
/*                                                                          */
/* Function:    Line_To                                                     */
/*                                                                          */
/* Description: Injects a new line segment and adjusts Profiles list.       */
/*                                                                          */
/* Input:       x, y : segment endpoint (start point in LastX,LastY)        */
/*                                                                          */
/* Returns:     SUCCESS on success.                                         */
/*              FAILURE on Render Pool overflow or Incorrect Profile.       */
/*                                                                          */
/****************************************************************************/
  
  static Bool  Line_To( RAS_ARGS Long  x, Long  y )
  {
    /* First, detect a change of direction */

    switch ( ras.state )
    {
    case Unknown:
      if ( y > ras.lastY )
      {
        if ( New_Profile( RAS_VARS  Ascending ) ) return FAILURE;
      }
      else
      {
        if ( y < ras.lastY )
          if ( New_Profile( RAS_VARS  Descending ) ) return FAILURE;
      }
      break;

    case Ascending:
      if ( y < ras.lastY )
      {
        if ( End_Profile( RAS_VAR ) ||
             New_Profile( RAS_VARS  Descending ) ) return FAILURE;
      }
      break;

    case Descending:
      if ( y > ras.lastY )
      {
        if ( End_Profile( RAS_VAR ) ||
             New_Profile( RAS_VARS  Ascending ) ) return FAILURE;
      }
      break;

    default:
      ;
    }

    /* Then compute the lines */

    switch ( ras.state )
    {
    case Ascending:
      if ( Line_Up ( RAS_VARS  ras.lastX, ras.lastY,
                     x, y, ras.minY, ras.maxY ) )
        return FAILURE;
      break;

    case Descending:
      if ( Line_Down( RAS_VARS ras.lastX, ras.lastY,
                      x, y, ras.minY, ras.maxY ) )
        return FAILURE;
      break;

    default:
      ;
    }

    ras.lastX = x;
    ras.lastY = y;

    return SUCCESS;
  }


/****************************************************************************/
/*                                                                          */
/* Function:    Bezier_To                                                   */
/*                                                                          */
/* Description: Injects a new bezier arc and adjusts the profile list.      */
/*                                                                          */
/* Input:       x,   y : arc endpoint (start point in LastX, LastY)         */
/*              Cx, Cy : control point                                      */
/*                                                                          */
/* Returns:     SUCCESS on success.                                         */
/*              FAILURE on Render Pool overflow or Incorrect Profile.       */
/*                                                                          */
/****************************************************************************/

  static Bool  Bezier_To( RAS_ARGS Long  x, 
                                   Long  y, 
                                   Long  cx, 
                                   Long  cy )
  {
    Long     y1, y2, y3, x3;
    TStates  state_bez;


    Push_Bezier( RAS_VARS ras.lastX, ras.lastY, cx, cy, x, y );

    do
    {
      y1 = ras.arc[2].y;
      y2 = ras.arc[1].y;
      y3 = ras.arc[0].y;
      x3 = ras.arc[0].x;

      /* first, categorize the bezier arc */

      if ( y1 == y2 )
      {
        if ( y2 == y3 )
          state_bez = Flat;
        else if ( y2 > y3 )
          state_bez = Descending;
        else
          state_bez = Ascending;
      }
      else if ( y1 > y2 )
      {
        if ( y2 >= y3 )
          state_bez = Descending;
        else
          state_bez = Unknown;
      }
      else if ( y2 <= y3 )
        state_bez = Ascending;
      else
        state_bez = Unknown;

      /* split non-monotonic arcs, ignore flat ones, or */
      /* computes the up and down ones                  */

      switch ( state_bez )
      {
      case Flat:
        ras.arc -= 2;
        break;

      case Unknown:
        Split_Bezier( ras.arc );
        ras.arc += 2;
        break;

      default:
        /* detect a change of direction */

        if ( ras.state != state_bez )
        {
          if ( ras.state != Unknown )
            if ( End_Profile( RAS_VAR ) ) return FAILURE;

          if ( New_Profile( RAS_VARS state_bez ) ) return FAILURE;
        }

        /* compute */

        switch ( ras.state )
        {
        case Ascending:
          if ( Bezier_Up ( RAS_VARS ras.minY, ras.maxY ) )
            return FAILURE;
          break;

        case Descending:
          if ( Bezier_Down( RAS_VARS ras.minY, ras.maxY ) )
            return FAILURE;
          break;

        default:
          ;
        }
      }
    } while ( ras.arc >= ras.arcs );

    ras.lastX = x3;
    ras.lastY = y3;

    return SUCCESS;
  }


/****************************************************************************/
/*                                                                          */
/* Function:    Decompose_Curve                                             */
/*                                                                          */
/* Description: Scans the outline arays in order to emit individual         */
/*              segments and beziers by calling Line_To() and Bezier_To().  */
/*              It handles all weird cases, like when the first point       */
/*              is off the curve, or when there are simply no 'on'          */
/*              points in the contour!                                      */
/*                                                                          */
/* Input:       first, last    : indexes of first and last point in         */
/*                               contour.                                   */
/*                                                                          */
/* Returns:     SUCCESS on success.                                         */
/*              FAILURE on error.                                           */
/*                                                                          */
/****************************************************************************/

  static Bool  Decompose_Curve( RAS_ARGS Int  first, 
                                         Int  last )
  {    
    Long   x,  y;   /* current point                */
    Long   cx, cy;  /* current Bezier control point */
    Long   mx, my;  /* current middle point         */

    Long   x_first, y_first;  /* first point's coordinates */
    Long   x_last,  y_last;   /* last point's coordinates  */

    Int    index;     /* current point's index */
    Bool   on_curve;  /* current point's state */


    x_first = SCALED( ras.x_coord[first] );
    y_first = SCALED( ras.y_coord[first] );

    x_last  = SCALED( ras.x_coord[last] );
    y_last  = SCALED( ras.y_coord[last] );

    ras.lastX = cx = x_first;
    ras.lastY = cy = y_first;

    on_curve = (ras.flags[first] & 1);
    index    = first;

    /* check first point to determine origin */
    if ( !on_curve )
    {
      /* first point is off the curve.  Yes, this happens... */
      if ( ras.flags[last] & 1 )
      {
        ras.lastX = x_last;  /* start at last point if it */
        ras.lastY = y_last;  /* is on the curve           */
      }
      else
      {
        /* if both first and last points are off the curve, */
        /* start at their middle and record its position    */
        /* for closure                                      */
        ras.lastX = (ras.lastX + x_last)/2;
        ras.lastY = (ras.lastY + y_last)/2;

        x_last = ras.lastX;
        y_last = ras.lastY;
      }
    }

    /* now process each contour point individually */
    while ( index < last )
    {
      index++;
      x = SCALED( ras.x_coord[index] );
      y = SCALED( ras.y_coord[index] );

      if ( on_curve )
      {
        /* the previous point was on the curve */
        on_curve = ( ras.flags[index] & 1 );
        if ( on_curve )
        {
          /* two successive on points => emit segment */
          if ( Line_To( RAS_VARS  x, y ) ) return FAILURE;
        }
        else
        {
          /* else, keep current control point for next bezier */
          cx = x;
          cy = y;
        }
      }
      else
      {
        /* the previous point was off the curve */
        on_curve = ( ras.flags[index] & 1 );
        if ( on_curve )
        {
          /* reaching an `on' point */
          if ( Bezier_To( RAS_VARS  x, y, cx, cy ) ) return FAILURE;
        }
        else
        {
          /* two successive `off' points => create middle point */
          mx = (cx + x)/2;
          my = (cy + y)/2;

          if ( Bezier_To( RAS_VARS  mx, my, cx, cy ) ) return FAILURE;

          cx = x;
          cy = y;
        }
      }
    }

    /* end of contour, close curve cleanly */
    if ( ras.flags[first] & 1 )
    {
      if ( on_curve )
        return Line_To( RAS_VARS  x_first, y_first );
      else
        return Bezier_To( RAS_VARS  x_first, y_first, cx, cy );
    }
    else
      if (!on_curve)
        return Bezier_To( RAS_VARS  x_last, y_last, cx, cy );

    return SUCCESS;
  }


/****************************************************************************/
/*                                                                          */
/* Function:    Convert_Glyph                                               */
/*                                                                          */
/* Description: Converts a glyph into a series of segments and arcs         */
/*              and makes a Profiles list with them.                        */
/*                                                                          */
/* Input:       _xCoord, _yCoord : coordinates tables.                      */
/*                                                                          */
/*              Uses the 'Flag' table too.                                  */
/*                                                                          */
/* Returns:     SUCCESS on success.                                         */
/*              FAILURE if any error was encountered during rendering.      */
/*                                                                          */
/****************************************************************************/

  static Bool  Convert_Glyph( RAS_ARGS PStorage  _xCoord, PStorage  _yCoord )
  {
    Int       i, start;

    PProfile  lastProfile;


    ras.fProfile = NULL;
    ras.joint    = FALSE;
    ras.fresh    = FALSE;

    ras.x_coord = _xCoord;
    ras.y_coord = _yCoord;

    ras.cProfile         = (PProfile)ras.top;
    ras.cProfile->offset = ras.top;
    ras.num_Profs        = 0;

    start = 0;

    for ( i = 0; i < ras.nContours; i++ )
    {
      ras.state    = Unknown;
      ras.gProfile = NULL;

      if ( Decompose_Curve( RAS_VARS  start, ras.outs[i]) ) return FAILURE;

      start = ras.outs[i]+1;

      /* We must now see if the extreme arcs join or not */
      if ( ( FRAC( ras.lastY ) == 0 &&
             ras.lastY >= ras.minY      &&
             ras.lastY <= ras.maxY ) )
        if ( ras.gProfile && ras.gProfile->flow == ras.cProfile->flow )
          ras.top--;
        /* Note that ras.gProfile can be nil if the contour was too small */
        /* to be drawn.                                                   */

      lastProfile = ras.cProfile;
      if ( End_Profile( RAS_VAR ) ) return FAILURE;

      /* close the 'next profile in contour' linked list */
      if ( ras.gProfile )
        lastProfile->next = ras.gProfile;
    }

    Finalize_Profile_Table( RAS_VAR );

    return SUCCESS;
  }


/************************************************/
/*                                              */
/*  Init_Linked                                 */
/*                                              */
/*    Inits an empty linked list.               */
/*                                              */
/************************************************/

  static void  Init_Linked( TProfileList*  l )
  {
    *l = NULL;
  }


/************************************************/
/*                                              */
/*  InsNew :                                    */
/*                                              */
/*    Inserts a new Profile in a linked list.   */
/*                                              */
/************************************************/

  static void  InsNew( PProfileList  list,
                       PProfile      profile )
  {
    PProfile  *old, current;
    Long       x;


    old     = list;
    current = *old;
    x       = profile->X;

    while ( current )
    {
      if ( x < current->X )
        goto Place;

      old     = &current->link;
      current = *old;
    }

  Place:
    profile->link = current;
    *old          = profile;
  }


/*************************************************/
/*                                               */
/*  DelOld :                                     */
/*                                               */
/*    Removes an old Profile from a linked list. */
/*                                               */
/*************************************************/

  static void  DelOld( PProfileList  list,
                       PProfile      profile )
  {
    PProfile  *old, current;


    old     = list;
    current = *old;

    while ( current )
    {
      if ( current == profile )
      {
        *old = current->link;
        return;
      }

      old     = &current->link;
      current = *old;
    }

    /* we should never get there, unless the Profile was not part of */
    /* the list.                                                     */
  }


/************************************************/
/*                                              */
/*  Sort :                                      */
/*                                              */
/*    Sorts a trace list.  In 95%, the list     */
/*    is already sorted.  We need an algorithm  */
/*    which is fast in this case.  Bubble sort  */
/*    is enough and simple.                     */
/*                                              */
/************************************************/

  static void  Sort( RAS_ARGS PProfileList  list )
  {
    PProfile  *old, current, next;


    /* First, set the new X coordinate of each profile */

    old     = list;
    current = *old;

    while ( current )
    {
      current->X       = *current->offset;
      current->offset += current->flow;
      current->height--;

      old     = &current->link;
      current = *old;
    }

    /* Then sort them */

    old     = list;
    current = *old;

    if ( !current )
      return;

    next = current->link;

    while ( next )
    {
      if ( current->X <= next->X )
      {
        old     = &current->link;
        current = *old;

        if ( !current )
          return;
      }
      else
      {
        *old          = next;
        current->link = next->link;
        next->link    = current;

        old     = list;
        current = *old;
      }

      next = current->link;
    }
  }


/***********************************************************************/
/*                                                                     */
/*  Vertical Sweep Procedure Set :                                     */
/*                                                                     */
/*  These three routines are used during the vertical black/white      */
/*  sweep phase by the generic Draw_Sweep() function.                  */
/*                                                                     */
/***********************************************************************/

  static void  Vertical_Sweep_Init( RAS_ARGS int*  min, int*  max )
  {
    switch ( ras.target.flow )
    {
    case TT_Flow_Up:
      ras.traceOfs  = *min * ras.target.cols;
      ras.traceIncr = ras.target.cols;
      break;

    default:
      ras.traceOfs  = ( ras.target.rows - 1 - *min ) * ras.target.cols;
      ras.traceIncr = -ras.target.cols;
    }

    ras.gray_min_x = 0;
    ras.gray_max_x = 0;
  }


  static void  Vertical_Sweep_Span( RAS_ARGS int         y,
                                             TT_F26Dot6  x1,
                                             TT_F26Dot6  x2,
                                             PProfile    left,
                                             PProfile    right )
  {
    Long   e1, e2;
    Int    c1, c2;
    Int    f1, f2;
    Byte*  target;


    /* Drop-out control */

    e1 = TRUNC( CEILING( x1 ) );
    e2 = TRUNC( FLOOR  ( x2 ) );
 
    if ( e2 >= 0 && e1 < ras.bWidth )
    {
      if ( e1 < 0 )           e1 = 0;
      if ( e2 >= ras.bWidth ) e2 = ras.bWidth-1;
 
      c1 = e1 >> 3;
      c2 = e2 >> 3;
 
      f1 = e1 & 7;
      f2 = e2 & 7;
 
      if ( ras.gray_min_x > c1 ) ras.gray_min_x = c1;
      if ( ras.gray_max_x < c2 ) ras.gray_max_x = c2;

      target = ras.bTarget + ras.traceOfs + c1;
 
      if ( c1 != c2 )
      {
        *target |= LMask[f1];
        
        if ( c2 > c1+1 )
          MEM_Set( target + 1, 0xFF, c2-c1-1 );
        
        target[c2-c1] |= RMask[f2];
      }
      else
        *target |= ( LMask[f1] & RMask[f2] );
    }
  }


  static void  Vertical_Sweep_Drop( RAS_ARGS int         y,
                                             TT_F26Dot6  x1,
                                             TT_F26Dot6  x2,
                                             PProfile    left,
                                             PProfile    right )
  {
    Long  e1, e2;
    Int   c1, f1;


    /* Drop-out control */

    e1 = CEILING( x1 );
    e2 = FLOOR  ( x2 );

    if ( e1 > e2 )
    {
      if ( e1 == e2 + ras.precision )
      {
        switch ( ras.dropOutControl )
        {
        case 1:
          e1 = e2;
          break;

        case 4:
          e1 = CEILING( (x1+x2+1) / 2 );
          e2 = e1;
          break;

        case 2:
        case 5:
          /* Drop-out Control Rule #4 */
  
          /* The spec is not very clear regarding rule #4.  It      */
          /* presents a method that is way too costly to implement  */
          /* while the general idea seems to get rid of 'stubs'.    */
          /*                                                        */
          /* Here, we only get rid of stubs recognized when:        */
          /*                                                        */
          /*  upper stub:                                           */
          /*                                                        */
          /*   - P_Left and P_Right are in the same contour         */
          /*   - P_Right is the successor of P_Left in that contour */
          /*   - y is the top of P_Left and P_Right                 */
          /*                                                        */
          /*  lower stub:                                           */
          /*                                                        */
          /*   - P_Left and P_Right are in the same contour         */
          /*   - P_Left is the successor of P_Right in that contour */
          /*   - y is the bottom of P_Left                          */
          /*                                                        */

          /* upper stub test */

          if ( left->next == right && left->height <= 0 ) return;

          /* lower stub test */

          if ( right->next == left && left->start == y ) return;

          /* check that the rightmost pixel isn't set */

          e1 = TRUNC( e1 );

          c1 = e1 >> 3;
          f1 = e1 &  7;

          if ( e1 >= 0 && e1 < ras.bWidth &&
               ras.bTarget[ras.traceOfs + c1] & (0x80 >> f1) )
            return;

          if ( ras.dropOutControl == 2 )
            e1 = e2;
          else
            e1 = CEILING( (x1+x2+1)/2 );
                    
          break;

        default:
          return;  /* unsupported mode */
        }
      }
      else
        return;
    }
    else
      e2 = e1;

    e1 = TRUNC( e1 );
 
    if ( e1 >= 0 && e1 < ras.bWidth )
    {
      c1 = e1 >> 3;
      f1 = e1 & 7;

      if ( ras.gray_min_x > c1 ) ras.gray_min_x = c1;
      if ( ras.gray_max_x < c1 ) ras.gray_max_x = c1;

      ras.bTarget[ras.traceOfs+c1] |= (0x80 >> f1);
    }
  }


  static void Vertical_Sweep_Step( RAS_ARG )
  {
    ras.traceOfs += ras.traceIncr;
  }


/***********************************************************************/
/*                                                                     */
/*  Horizontal Sweep Procedure Set :                                   */
/*                                                                     */
/*  These three routines are used during the horizontal black/white    */
/*  sweep phase by the generic Draw_Sweep() function.                  */
/*                                                                     */
/***********************************************************************/

  static void  Horizontal_Sweep_Init( RAS_ARGS int*  min, int*  max )
  {
    /* nothing, really */
  }


  static void  Horizontal_Sweep_Span( RAS_ARGS int         y,
                                               TT_F26Dot6  x1,
                                               TT_F26Dot6  x2,
                                               PProfile    left,
                                               PProfile    right )
  {
    Long  e1, e2;
    PByte bits;
    Byte  f1;


    /* During the horizontal sweep, we only take care of drop-outs */

    e1 = CEILING( x1 );
    e2 = FLOOR  ( x2 );

    bits = ras.bTarget + (y >> 3);
    f1   = 0x80 >> (y  & 7);

    e1 = TRUNC( e1 );

    if ( e1 >= 0 && e1 < ras.target.rows )
      if ( ras.target.flow == TT_Flow_Down )
        bits[(ras.target.rows-1 - e1) * ras.target.cols] |= f1;
      else
        bits[e1 * ras.target.cols] |= f1;

    e2 = TRUNC( e2 );

    if ( e2 >= 0 && e2 < ras.target.rows )
      if ( ras.target.flow == TT_Flow_Down )
        bits[(ras.target.rows-1-e2) * ras.target.cols] |= f1;
      else
        bits[e2 * ras.target.cols] |= f1;
  }


  static void  Horizontal_Sweep_Drop( RAS_ARGS int         y,
                                               TT_F26Dot6  x1,
                                               TT_F26Dot6  x2,
                                               PProfile    left,
                                               PProfile    right )
  {
    Long  e1, e2;
    PByte bits;
    Byte  f1;


    /* During the horizontal sweep, we only take care of drop-outs */

    e1 = CEILING( x1 );
    e2 = FLOOR  ( x2 );

    if ( e1 > e2 )
    {
      if ( e1 == e2 + ras.precision )
      {
        switch ( ras.dropOutControl )
        {
        case 1:
          e1 = e2;
          break;

        case 4:
          e1 = CEILING( (x1+x2+1) / 2 );
          break;

        case 2:
        case 5:

          /* Drop-out Control Rule #4 */
  
          /* The spec is not very clear regarding rule #4.  It      */
          /* presents a method that is way too costly to implement  */
          /* while the general idea seems to get rid of 'stubs'.    */
          /*                                                        */

          /* rightmost stub test */

          if ( left->next == right && left->height <= 0 ) return;

          /* leftmost stub test */

          if ( right->next == left && left->start == y ) return;

          /* check that the rightmost pixel isn't set */

          e1 = TRUNC( e1 );

          bits = ras.bTarget + (y >> 3);
          f1   = 0x80 >> (y &  7);

          if ( ras.target.flow == TT_Flow_Down )
            bits += (ras.target.rows-1-e1) * ras.target.cols;
          else
            bits += e1 * ras.target.cols;

          if ( e1 >= 0              && 
               e1 < ras.target.rows && 
               *bits & f1 ) 
            return;

          if ( ras.dropOutControl == 2 )
            e1 = e2;
          else
            e1 = CEILING( (x1+x2+1) / 2 );

          break;

        default:
          return;  /* unsupported mode */
        }
      }
      else
        return;
    }

    bits = ras.bTarget + (y >> 3);
    f1   = 0x80 >> (y  & 7);

    e1 = TRUNC( e1 );

    if ( e1 >= 0 && e1 < ras.target.rows )
      if (ras.target.flow==TT_Flow_Down)
        bits[(ras.target.rows-1-e1) * ras.target.cols] |= f1;
      else
        bits[e1 * ras.target.cols] |= f1;
  }


  static void Horizontal_Sweep_Step( RAS_ARG )
  {
    /* Nothing, really */
  }


/***********************************************************************/
/*                                                                     */
/*  Vertical Gray Sweep Procedure Set :                                */
/*                                                                     */
/*  These two routines are used during the vertical gray-levels        */
/*  sweep phase by the generic Draw_Sweep() function.                  */
/*                                                                     */
/*                                                                     */
/*  NOTES:                                                             */
/*                                                                     */
/*  - The target pixmap's width *must* be a multiple of 4.             */
/*                                                                     */
/*  - you have to use the function Vertical_Sweep_Span() for           */
/*    the gray span call.                                              */
/*                                                                     */
/***********************************************************************/

  static void  Vertical_Gray_Sweep_Init( RAS_ARGS int*  min, int*  max )
  {
    *min = *min & -2;
    *max = ( *max+3 ) & -2;

    ras.traceOfs = 0;

    switch ( ras.target.flow )
    {
    case TT_Flow_Up:
      ras.traceG  = (*min/2) * ras.target.cols;
      ras.traceIncr = ras.target.cols;
      break;

    default:
      ras.traceG    = (ras.target.rows-1 - *min/2) * ras.target.cols;
      ras.traceIncr = -ras.target.cols;
    }

    ras.gray_min_x =  ras.target.cols;
    ras.gray_max_x = -ras.target.cols;
  }


  static void  Vertical_Gray_Sweep_Step( RAS_ARG )
  {
    Int    c1, c2;
    PByte  pix, bit, bit2;
    Int*   count = ras.count_table;
    char*  grays;


    ras.traceOfs += ras.gray_width;

    if ( ras.traceOfs > ras.gray_width )
    {
      pix   = ras.gTarget + ras.traceG + ras.gray_min_x*4;
      grays = ras.grays;

      if ( ras.gray_max_x >= 0 )
      {
        if ( ras.gray_max_x >= ras.target.width ) 
          ras.gray_max_x = ras.target.width - 1;

        if ( ras.gray_min_x < 0 ) 
          ras.gray_min_x = 0;

        bit   = ras.bTarget + ras.gray_min_x;
        bit2  = bit + ras.gray_width; 
        
        c1 = ras.gray_max_x - ras.gray_min_x;

        while ( c1 >= 0 )
        {
          c2 = count[*bit] + count[*bit2];
 
          if ( c2 )
          {
            pix[0] = grays[(c2 & 0xF000) >> 12];
            pix[1] = grays[(c2 & 0x0F00) >>  8];
            pix[2] = grays[(c2 & 0x00F0) >>  4];
            pix[3] = grays[(c2 & 0x000F)      ];

            *bit  = 0;
            *bit2 = 0;
          }

          bit ++;
          bit2++;
          pix += 4;
          c1  --;
        }
      }

      ras.traceOfs = 0;
      ras.traceG  += ras.traceIncr;

      ras.gray_min_x =  ras.target.cols;
      ras.gray_max_x = -ras.target.cols;
    }
  }


  static void  Horizontal_Gray_Sweep_Span( RAS_ARGS int         y,
                                                    TT_F26Dot6  x1,
                                                    TT_F26Dot6  x2,
                                                    PProfile    left,
                                                    PProfile    right )
  {
    /* nothing, really */
  }

  static void  Horizontal_Gray_Sweep_Drop( RAS_ARGS int         y,
                                                    TT_F26Dot6  x1,
                                                    TT_F26Dot6  x2,
                                                    PProfile    left,
                                                    PProfile    right )
  {
    Long  e1, e2;
    PByte pixel;
    Byte  color;

    /* During the horizontal sweep, we only take care of drop-outs */
    e1 = CEILING( x1 );
    e2 = FLOOR  ( x2 );

    if ( e1 > e2 )
    {
      if ( e1 == e2 + ras.precision )
      {
        switch ( ras.dropOutControl )
        {
        case 1:
          e1 = e2;
          break;

        case 4:
          e1 = CEILING( (x1+x2+1) / 2 );
          break;

        case 2:
        case 5:

          /* Drop-out Control Rule #4 */
  
          /* The spec is not very clear regarding rule #4.  It      */
          /* presents a method that is way too costly to implement  */
          /* while the general idea seems to get rid of 'stubs'.    */
          /*                                                        */

          /* rightmost stub test */
          if ( left->next == right && left->height <= 0 ) return;

          /* leftmost stub test */
          if ( right->next == left && left->start == y ) return;

          if ( ras.dropOutControl == 2 )
            e1 = e2;
          else
            e1 = CEILING( (x1+x2+1) / 2 );

          break;

        default:
          return;  /* unsupported mode */
        }
      }
      else
        return;
    }

    if (e1 >= 0)
    {
      if ( x2-x1 >= ras.precision_half )
        color = ras.grays[2];
      else
        color = ras.grays[1];

      e1 = TRUNC(e1)/2;
      if (e1 < ras.target.rows)
      {
        if (ras.target.flow == TT_Flow_Down)
          pixel = ras.gTarget + (ras.target.rows-1-e1)*ras.target.cols +(y/2);
        else
          pixel = ras.gTarget + e1*ras.target.cols + (y/2);

        if (pixel[0] == ras.grays[0])
          pixel[0] = color;
      }
    }
  }


/********************************************************************/
/*                                                                  */
/*  Generic Sweep Drawing routine                                   */
/*                                                                  */
/********************************************************************/

  static Bool  Draw_Sweep( RAS_ARG )
  {
    Int  y;

    PProfile  P, Q, P_Left, P_Right, Q_Left, Q_Right;

    Int  min_Y, max_Y, top, bottom, dropouts;

    Long x1, x2, xs, e1, e2;

    TProfileList  wait;
    TProfileList  draw_left, draw_right;
    TProfileList  drop_left, drop_right;


    /* Init empty linked lists */

    Init_Linked( &wait );

    Init_Linked( &draw_left  );
    Init_Linked( &draw_right );

    Init_Linked( &drop_left  );
    Init_Linked( &drop_right );

    /* first, compute min and max Y */

    P     = ras.fProfile;
    max_Y = TRUNC( ras.minY );
    min_Y = TRUNC( ras.maxY );

    while ( P )
    {
      Q = P->link;

      switch ( P->flow )
      {
      case TT_Flow_Up:
        bottom = P->start;
        top    = P->start + P->height - 1;
        break;

      case TT_Flow_Down:
        bottom = P->start - P->height + 1;
        top    = P->start;

        P->start   = bottom;
        P->offset += P->height - 1;
        break;

      default:
        ras.error = Raster_Err_Invalid;
        return FAILURE;
      }

      if ( min_Y > bottom ) min_Y = bottom;
      if ( max_Y < top    ) max_Y = top;

      P->X = 0;
      InsNew( &wait, P );

      P = Q;
    }

    /* Now inits the sweep */

    ras.Proc_Sweep_Init( RAS_VARS  &min_Y, &max_Y );

    /* Then compute the distance of each profile from min_Y */

    P = wait;

    while ( P )
    {
      P->countL = P->start - min_Y;
      P = P->link;
    }

    /* Let's go */

    for ( y = min_Y; y <= max_Y; y++ )
    {
      /* look in the wait list for new activations */

      P = wait;

      while ( P )
      {
        Q = P->link;
        if ( P->countL == 0 )
        {
          DelOld( &wait, P );

          switch ( P->flow )
          {
          case TT_Flow_Up:
            InsNew( &draw_left,  P );
            break;
          case TT_Flow_Down:
            InsNew( &draw_right, P );
            break;
          }
        }
        else
          P->countL--;

        P = Q;
      }

      /* Sort the drawing lists */

      Sort( RAS_VARS  &draw_left );
      Sort( RAS_VARS  &draw_right );

      /* Let's trace */

      dropouts = 0;

      P_Left  = draw_left;
      P_Right = draw_right;

      while ( P_Left )
      {
        Q_Left  = P_Left ->link;
        Q_Right = P_Right->link;

        x1 = P_Left ->X;
        x2 = P_Right->X;

#ifdef IGNORE_FILL_FLOW

        if ( x1 > x2 )
        {
          xs = x1;
          x1 = x2;
          x2 = xs;
        }

#endif

        if ( x2-x1 <= ras.precision )
        {
          e1 = FLOOR( x1 );
          e2 = CEILING( x2 );
 
          if ( ras.dropOutControl != 0 && 
               (e1 > e2 || e2 == e1 + ras.precision) )
          {
            /* a drop out was detected */
 
            P_Left ->X = x1;
            P_Right->X = x2;
 
            dropouts++;
 
            DelOld( &draw_left,  P_Left  );
            DelOld( &draw_right, P_Right );
 
            InsNew( &drop_left,  P_Left  );
            InsNew( &drop_right, P_Right );
 
            goto Skip_To_Next;
          }
        }
 
        ras.Proc_Sweep_Span( RAS_VARS  y, x1, x2, P_Left, P_Right );
 
        /* We finalize the profile if needed */
 
        if ( P_Left->height <= 0 )
          DelOld( &draw_left, P_Left );
 
        if ( P_Right->height <= 0 )
          DelOld( &draw_right, P_Right );

      Skip_To_Next:
 
        P_Left  = Q_Left;
        P_Right = Q_Right;
      }

      P_Left  = drop_left;
      P_Right = drop_right;

      while ( dropouts > 0 )
      {
        Q_Left  = P_Left->link;
        Q_Right = P_Right->link;

        DelOld( &drop_left,  P_Left  );
        DelOld( &drop_right, P_Right );

        ras.Proc_Sweep_Drop( RAS_VARS  y,
                                       P_Left->X, 
                                       P_Right->X, 
                                       P_Left, 
                                       P_Right );

        if ( P_Left->height > 0 )
          InsNew( &draw_left, P_Left );
 
        if ( P_Right->height > 0 )
          InsNew( &draw_right, P_Right );

        P_Left  = Q_Left;
        P_Right = Q_Right;

        dropouts--;
      }

      /* Step to next line */

      ras.Proc_Sweep_Step( RAS_VAR );
    }

    return SUCCESS;
  }


/****************************************************************************/
/*                                                                          */
/* Function:    Render_Single_Pass                                          */
/*                                                                          */
/* Description: Performs one sweep with sub-banding.                        */
/*                                                                          */
/* Input:       _XCoord, _YCoord : x and y coordinates arrays               */
/*                                                                          */
/* Returns:     SUCCESS on success                                          */
/*              FAILURE if any error was encountered during render.         */
/*                                                                          */
/****************************************************************************/

  static TT_Error  Render_Single_Pass( RAS_ARGS TT_F26Dot6*  _xcoord,
                                                TT_F26Dot6*  _ycoord )
  {
    Int  i, j, k;


    while ( ras.band_top >= 0 )
    {
      ras.maxY = ras.band_stack[ras.band_top].y_max * ras.precision;
      ras.minY = ras.band_stack[ras.band_top].y_min * ras.precision;

      ras.top = ras.buff;

      ras.error = Raster_Err_None;

      if ( Convert_Glyph( RAS_VARS  _xcoord, _ycoord ) )
      {
        if ( ras.error != Raster_Err_Overflow ) return FAILURE;

        ras.error = Raster_Err_None;

        /* sub-banding */

#ifdef DEBUG_RASTER
        ClearBand( RAS_VARS  TRUNC( ras.minY ), TRUNC( ras.maxY ) );
#endif

        i = ras.band_stack[ras.band_top].y_min;
        j = ras.band_stack[ras.band_top].y_max;

        k = ( i + j )/2;

        if ( ras.band_top >= 7 || k < i )
        {
          ras.band_top     = 0;
          ras.error = Raster_Err_Invalid;
          return ras.error;
        }

        ras.band_stack[ras.band_top+1].y_min = k;
        ras.band_stack[ras.band_top+1].y_max = j;

        ras.band_stack[ras.band_top].y_max = k - 1;

        ras.band_top++;
      }
      else
      {
        if ( ras.fProfile )
          if ( Draw_Sweep( RAS_VAR ) ) return ras.error;
        ras.band_top--;
      }
    }

    return TT_Err_Ok;
  }


/****************************************************************************/
/*                                                                          */
/* Function:    Render_Glyph                                                */
/*                                                                          */
/* Description: Renders a glyph in a bitmap.  Sub-banding if needed.        */
/*                                                                          */
/* Input:       AGlyph   Glyph record                                       */
/*                                                                          */
/* Returns:     SUCCESS on success.                                         */
/*              FAILURE if any error was encountered during rendering.      */
/*                                                                          */
/****************************************************************************/

  TT_Error  Render_Glyph( RAS_ARGS TT_Outline*     glyph,
                                   TT_Raster_Map*  target_map )
  {
    TT_Error  error;


    if ( !ras.buff )
    {
      ras.error = Raster_Err_Not_Ini;
      return ras.error;
    }

	if ( glyph->points <= 0 || glyph->contours <= 0 )
	  return TT_Err_Ok;

    if ( glyph->points < glyph->conEnds[glyph->contours-1] )
    {
      ras.error = TT_Err_Too_Many_Points;
      return ras.error;
    }

    if ( target_map )
      ras.target = *target_map;

    ras.outs      = glyph->conEnds;
    ras.flags     = glyph->flag;
    ras.nPoints   = glyph->points;
    ras.nContours = glyph->contours;

	Set_High_Precision( RAS_VARS glyph->high_precision );
    ras.scale_shift    = ras.precision_shift;
    ras.dropOutControl = glyph->dropout_mode;
	ras.second_pass    = glyph->high_precision;


    /* Vertical Sweep */

    ras.Proc_Sweep_Init = Vertical_Sweep_Init;
    ras.Proc_Sweep_Span = Vertical_Sweep_Span;
    ras.Proc_Sweep_Drop = Vertical_Sweep_Drop;
    ras.Proc_Sweep_Step = Vertical_Sweep_Step;

    ras.band_top            = 0;
    ras.band_stack[0].y_min = 0;
    ras.band_stack[0].y_max = ras.target.rows - 1;

    ras.bWidth  = ras.target.width;
    ras.bTarget = (unsigned char*)ras.target.bitmap;

    if ( (error = Render_Single_Pass( RAS_VARS glyph->xCoord, 
                                               glyph->yCoord )) )
      return error;

    /* Horizontal Sweep */

    if ( ras.second_pass && ras.dropOutControl != 0 )
    {
      ras.Proc_Sweep_Init = Horizontal_Sweep_Init;
      ras.Proc_Sweep_Span = Horizontal_Sweep_Span;
      ras.Proc_Sweep_Drop = Horizontal_Sweep_Drop;
      ras.Proc_Sweep_Step = Horizontal_Sweep_Step;

      ras.band_top            = 0;
      ras.band_stack[0].y_min = 0;
      ras.band_stack[0].y_max = ras.target.width - 1;

      if ( (error = Render_Single_Pass( RAS_VARS glyph->yCoord, 
                                                 glyph->xCoord )) )
        return error;
    }

    return TT_Err_Ok;
  }


/****************************************************************************/
/*                                                                          */
/* Function:    Render_Gray_Glyph                                           */
/*                                                                          */
/* Description: Renders a glyph with grayscaling. Sub-banding if needed.    */
/*                                                                          */
/* Input:       AGlyph   Glyph record                                       */
/*                                                                          */
/* Returns:     SUCCESS on success                                          */
/*              FAILURE if any error was encountered during rendering.      */
/*                                                                          */
/****************************************************************************/

  TT_Error  Render_Gray_Glyph( RAS_ARGS  TT_Outline*     glyph,
                                         TT_Raster_Map*  target_map,
                                         char*           palette )
  {
    Int       i;
    TT_Error  error;

    if ( !ras.buff )
    {
      ras.error = Raster_Err_Not_Ini;
      return ras.error;
    }

	if ( glyph->points <= 0 || glyph->contours <= 0 )
	  return TT_Err_Ok;

    if ( glyph->points < glyph->conEnds[glyph->contours-1] )
    {
      ras.error = TT_Err_Too_Many_Points;
      return ras.error;
    }

    if ( palette )
    {
      for ( i = 0; i < 5; i++ )
        ras.grays[i] = palette[i];
    }

    if ( target_map )
      ras.target = *target_map;

    ras.outs      = glyph->conEnds;
    ras.flags     = glyph->flag;
    ras.nPoints   = glyph->points;
    ras.nContours = glyph->contours;

	Set_High_Precision( RAS_VARS glyph->high_precision );
    ras.scale_shift    = ras.precision_shift+1;
    ras.dropOutControl = glyph->dropout_mode;
	ras.second_pass    = glyph->high_precision;


    /* Vertical Sweep */

    ras.band_top            = 0;
    ras.band_stack[0].y_min = 0;
    ras.band_stack[0].y_max = 2 * ras.target.rows - 1;

    ras.bWidth  = ras.gray_width;
    if ( ras.bWidth > ras.target.cols/4 )
      ras.bWidth = ras.target.cols/4;

    ras.bWidth  = ras.bWidth * 8;
    ras.bTarget = (unsigned char*)ras.gray_lines;
    ras.gTarget = (unsigned char*)ras.target.bitmap;

    ras.Proc_Sweep_Init = Vertical_Gray_Sweep_Init;
    ras.Proc_Sweep_Span = Vertical_Sweep_Span;
    ras.Proc_Sweep_Drop = Vertical_Sweep_Drop;
    ras.Proc_Sweep_Step = Vertical_Gray_Sweep_Step;

    error = Render_Single_Pass( RAS_VARS  glyph->xCoord, glyph->yCoord );
    if (error)
      return error;

    /* Horizontal Sweep */

    if ( ras.second_pass && ras.dropOutControl != 0 )
    {
      ras.Proc_Sweep_Init = Horizontal_Sweep_Init;
      ras.Proc_Sweep_Span = Horizontal_Gray_Sweep_Span;
      ras.Proc_Sweep_Drop = Horizontal_Gray_Sweep_Drop;
      ras.Proc_Sweep_Step = Horizontal_Sweep_Step;

      ras.band_top            = 0;
      ras.band_stack[0].y_min = 0;
      ras.band_stack[0].y_max = ras.target.width*2 - 1;

      error = Render_Single_Pass( RAS_VARS glyph->yCoord, glyph->xCoord );
      if (error)
        return error;
    }

    return TT_Err_Ok;
  }


/************************************************/
/*                                              */
/* InitRasterizer                               */
/*                                              */
/*  Raster Initialization.                      */
/*  Gets the bitmap description and render pool */
/*  addresses.                                  */
/*                                              */
/************************************************/

#undef ras

  TT_Error  TTRaster_Done( PEngine_Instance  engine )
  {
    TRaster_Instance*  ras = (TRaster_Instance*)engine->raster_component;

    if ( !ras )
      return TT_Err_Ok;

    FREE( ras->buff );
    FREE( ras->gray_lines );

#ifndef TT_STATIC_RASTER
    FREE( engine->raster_component );
#endif

    return TT_Err_Ok;
  }



  TT_Error  TTRaster_Init( PEngine_Instance  engine )
  {
    TT_Error  error;

    int  i, l, j, c;

    TRaster_Instance*  ras;


#ifdef TT_STATIC_RASTER

    ras = engine->raster_component = &cur_ras;

#else

    if ( ALLOC( engine->raster_component, sizeof ( TRaster_Instance ) ) )
      return error;

    ras = (TRaster_Instance*)engine->raster_component;

#endif

    if ( ALLOC( ras->buff,       RASTER_RENDER_POOL )  ||
         ALLOC( ras->gray_lines, RASTER_GRAY_LINES ) )
       return error;

    ras->maxBuff    = ras->buff + ( RASTER_RENDER_POOL / 4 ) 
                      - AlignProfileSize;

    ras->gray_width = RASTER_GRAY_LINES / 2;

    /* Initialization of Count_Table */

    for ( i = 0; i < 256; i++ )
    {
      l = 0;
      j = i;

      for ( c = 0; c < 4; c++ )
      {
        l <<= 4;

        if ( j & 0x80 ) l++;
        if ( j & 0x40 ) l++;

        j = ( j << 2 ) & 0xFF;
      }

      ras->count_table[i] = l;
    }

    ras->dropOutControl = 2;
    ras->error          = Raster_Err_None;

    return TT_Err_Ok;
  }


/* END */
