/* Copyright (C) 2001-2021 Artifex Software, Inc.

   All Rights Reserved.

   This software is provided AS-IS with no warranty, either express or

   implied.

   This software is distributed under license and may not be copied, modified

   or distributed except as expressly authorized under the terms of that

   license.  Refer to licensing information at http://www.artifex.com/

   or contact Artifex Software, Inc.,  1305 Grant Avenue - Suite 200,

   Novato, CA 94945, U.S.A., +1(415)492-9861, for further information.

*/

/* Path stroking procedures for Ghostscript library */

#include "math_.h"

#include "memory_.h"

#include "string_.h"

#include "gx.h"

#include "gpcheck.h"

#include "gserrors.h"

#include "gsdcolor.h"

#include "gsptype1.h"

#include "gxfixed.h"

#include "gxfarith.h"

#include "gxmatrix.h"

#include "gscoord.h"

#include "gsdevice.h"

#include "gxdevice.h"

#include "gxhttile.h"

#include "gxgstate.h"

#include "gzline.h"

#include "gzpath.h"

#include "gzcpath.h"

#include "gxpaint.h"

#include "gxscanc.h"

#include "gxfill.h"

#include "gxdcolor.h"

#include "assert_.h"

#include <stdlib.h>             /* for qsort */

#include <limits.h>             /* For INT_MAX */

/* Overview of the scan conversion algorithm.

 *

 * The normal scan conversion algorithm runs through a path, converting

 * it into a sequence of edges. It then runs through those edges from

 * top to bottom keeping a list of which ones are "active", and ordering

 * them so that it can read out a list of intersection points from left

 * to right across any given scanline (or scan "band" when working with

 * trapezoids).

 *

 * This scan conversion algorithm avoids the need to maintain an active

 * line list, and to repeatedly re-sort lines. It is thus faster, at

 * the cost of using more memory, and not being able to cope with

 * trapezoids.

 *

 * Conceptually, the idea is to make an (initially empty) table. Each

 * row of the table holds the set of intersection data for a given

 * scanline. We therefore just need to run through the path once,

 * decomposing it to a sequence of edges. We then step along each edge

 * adding intersection information into each row of the table as we go.

 * Each piece of intersection information includes the point at which

 * the edge crosses the scanline, and the direction in which it does so

 * (up or down).

 *

 * At the end of this process, we can then sort each rows data, and

 * simply 'fill in' the scanline according to the winding rule.

 *

 * This copes well with 'centre of a pixel' fill modes, but 'any part

 * of a pixel' requires some extra work. Let's describe 'centre of a

 * pixel' first.

 *

 * Assume we have a path with n segments in, and a bbox that crosses

 * a region x wide, y high.

 *

 * 1) Create a table, A, 1 int entry per scan line. Run through the path,

 * segment by segment counting how many intersections occur on each

 * scanline. (O(y * n))

 *

 * 2) Create a table, B, with as many entries per scanline as determined in

 * the table A. (O(y * n))

 *

 * [Each entry is a (xcoord,direction) tuple. xcoord = the xcoord where

 * an edge crosses the horizontal line through the middle of the pixel.

 * direction = 0 if the edge is rising, 1 if falling.]

 *

 * 3) Run through the path segment by segment, inserting entries for each

 * scanline intersection in table B. (O(y * n))

 *

 * 4) Sort the scanline intersections of table B (on left,right,direction).

 * (O(y * n log n) for current code)

 *

 * 5) Filter the scanline intersections according to the winding rule.

 * (O(y * n))

 *

 * 6) Fill rectangles according to each set of scanline intersections.

 * (O(y * n))

 *

 * So worst case complexity (when every segment crosses every scanline) is

 * O(y * n log n).

 *

 * NOTE: If we use a binary comparison based sort, then the best we can manage

 * is n log n for step 4. If we use a radix based sort, we can get O(n).

 * Consider this if we ever need it.

 *

 * In order to cope with 'any part of a pixel' it no longer suffices

 * to keep a single intersection point for each scanline intersection.

 * Instead we keep the interval of a scanline that the edge intersects.

 * Thus each entry is a (left,right,direction) tuple. left = the

 * leftmost point at which this edge intersects this scanline. right =

 * the rightmost point at which this edge intersects this scanline.

 * direction = 0 for rising edges, 1 for falling edges.

 *

 * The rest of the algorithm is unchanged, apart from additional care

 * being required when filling the scanlines to allow for the fact

 * that edges are no longer point intersections.

 *

 * The first set of routines (gx_scan_convert and gx_fill_edgebuffer)

 * implement the "pixel centre" covered routines by drawing rectangle

 * high scanlines at a time. The second set of routines

 * (gx_scan_convert_app and gx_fill_edgebuffer_app) is the equivalent,

 * for "Any Part of Pixel" covered.

 *

 * The third and fourth are the same things, but using trapezoids

 * that can be multiple scanlines high rather than scanlines.

 *

 * In order to do trapezoid extraction, we extend the edge intersection

 * information to be (left,right,id,direction) (for the "centre pixel"

 * variants) and (left,left_id,right,right_id,direction) (for the "any

 * part of a pixel" variants). The 'id' is a int that is guaranteed

 * unique for each flattened line in path.

 *

 * If we spot that each scanlines data has the same set of ids in the

 * same order, then we can 'collate' them into a trapezoid.

 */

/* NOTE: code in this file assumes that fixed and int can be used

 * interchangably. */

#undef DEBUG_SCAN_CONVERTER

#undef DEBUG_OUTPUT_SC_AS_PS

typedef int64_t fixed64;

enum

{

    DIRN_UNSET = -1,

    DIRN_UP = 0,

    DIRN_DOWN = 1

};

/* Centre of a pixel routines */

static int intcmp(const void *a, const void *b)

{

    return *((int*)a) - *((int *)b);

}

#if defined(DEBUG_SCAN_CONVERTER)

int debugging_scan_converter = 1;

static void

gx_edgebuffer_print(gx_edgebuffer * edgebuffer)

{

    int i;

    dlprintf1("Edgebuffer %x\n", edgebuffer);

    dlprintf4("xmin=%x xmax=%x base=%x height=%x\n",

              edgebuffer->xmin, edgebuffer->xmax, edgebuffer->base, edgebuffer->height);

    for (i=0; i < edgebuffer->height; i++) {

        int  offset = edgebuffer->index[i];

        int *row    = &edgebuffer->table[offset];

        int count   = *row++;

        dlprintf3("%d @ %d: %d =", i, offset, count);

        while (count-- > 0) {

            int v = *row++;

            dlprintf2(" %x:%d", v&~1, v&1);

        }

        dlprintf("\n");

    }

}

#endif

#ifdef DEBUG_OUTPUT_SC_AS_PS

static void coord(const char *str, fixed x, fixed y)

{

    if (x > 0)

        dlprintf1(" 16#%x ", x);

    else

        dlprintf1("0 16#%x sub ", -x);

    if (y > 0)

        dlprintf1(" 16#%x ", y);

    else

        dlprintf1("0 16#%x sub ", -y);

    dlprintf1("%s %%PS\n", str);

}

#endif

typedef void (zero_filler_fn)(int *, const fixed *);

static void mark_line_zero(fixed sx, fixed ex, fixed *zf)

{

    if (sx < zf[0])

        zf[0] = sx;

    if (ex < zf[0])

        zf[0] = ex;

    if (sx > zf[1])

        zf[1] = sx;

    if (ex > zf[1])

        zf[1] = ex;

}

static void mark_curve_zero(fixed sx, fixed c1x, fixed c2x, fixed ex, int depth, fixed *zf)

{

    fixed ax = (sx + c1x)>>1;

    fixed bx = (c1x + c2x)>>1;

    fixed cx = (c2x + ex)>>1;

    fixed dx = (ax + bx)>>1;

    fixed fx = (bx + cx)>>1;

    fixed gx = (dx + fx)>>1;

    assert(depth >= 0);

    if (depth == 0)

        mark_line_zero(sx, ex, zf);

    else {

        depth--;

        mark_curve_zero(sx, ax, dx, gx, depth, zf);

        mark_curve_zero(gx, fx, cx, ex, depth, zf);

    }

}

static void mark_curve_big_zero(fixed64 sx, fixed64 c1x, fixed64 c2x, fixed64 ex, int depth, fixed *zf)

{

    fixed64 ax = (sx + c1x)>>1;

    fixed64 bx = (c1x + c2x)>>1;

    fixed64 cx = (c2x + ex)>>1;

    fixed64 dx = (ax + bx)>>1;

    fixed64 fx = (bx + cx)>>1;

    fixed64 gx = (dx + fx)>>1;

    assert(depth >= 0);

    if (depth == 0)

        mark_line_zero((fixed)sx, (fixed)ex, zf);

    else {

        depth--;

        mark_curve_big_zero(sx, ax, dx, gx, depth, zf);

        mark_curve_big_zero(gx, fx, cx, ex, depth, zf);

    }

}

static void mark_curve_top_zero(fixed sx, fixed c1x, fixed c2x, fixed ex, int depth, fixed *zf)

{

    fixed test = (sx^(sx<<1))|(c1x^(c1x<<1))|(c2x^(c2x<<1))|(ex^(ex<<1));

    if (test < 0)

        mark_curve_big_zero(sx, c1x, c2x, ex, depth, zf);

    else

        mark_curve_zero(sx, c1x, c2x, ex, depth, zf);

}

static int

zero_case(gx_device      * gs_restrict pdev,

          gx_path        * gs_restrict path,

          gs_fixed_rect  * gs_restrict ibox,

          int            * gs_restrict index,

          int            * gs_restrict table,

          fixed                        fixed_flat,

          zero_filler_fn *             fill)

{

    const subpath *psub;

    fixed zf[2];

    /* Step 2 continued: Now we run through the path, filling in the real

     * values. */

    for (psub = path->first_subpath; psub != 0;) {

        const segment *pseg = (const segment *)psub;

        fixed ex = pseg->pt.x;

        fixed sy = pseg->pt.y;

        fixed ix = ex;

        int iy = fixed2int(pseg->pt.y);

        zf[0] = ex;

        zf[1] = ex;

        while ((pseg = pseg->next) != 0 &&

               pseg->type != s_start

            ) {

            fixed sx = ex;

            ex = pseg->pt.x;

            switch (pseg->type) {

                default:

                case s_start: /* Should never happen */

                case s_dash:  /* We should never be seeing a dash here */

                    assert("This should never happen" == NULL);

                    break;

                case s_curve: {

                    const curve_segment *const pcur = (const curve_segment *)pseg;

                    int k = gx_curve_log2_samples(sx, sy, pcur, fixed_flat);

                    mark_curve_top_zero(sx, pcur->p1.x, pcur->p2.x, ex, k, zf);

                    break;

                }

                case s_gap:

                case s_line:

                case s_line_close:

                    mark_line_zero(sx, ex, zf);

                    break;

            }

        }

        /* And close any open segments */

        mark_line_zero(ex, ix, zf);

        fill(&table[index[iy-ibox->p.y]], zf);

        psub = (const subpath *)pseg;

    }

    return 0;

}

static void mark_line(fixed sx, fixed sy, fixed ex, fixed ey, int base_y, int height, int *table, int *index)

{

    int64_t delta;

    int iy, ih;

    fixed clip_sy, clip_ey;

    int dirn = DIRN_UP;

    int *row;

#ifdef DEBUG_SCAN_CONVERTER

    if (debugging_scan_converter)

        dlprintf6("Marking line from %x,%x to %x,%x (%x,%x)\n", sx, sy, ex, ey, fixed2int(sy + fixed_half-1) - base_y, fixed2int(ey + fixed_half-1) - base_y);

#endif

#ifdef DEBUG_OUTPUT_SC_AS_PS

    dlprintf("0.001 setlinewidth 0 0 0 setrgbcolor %%PS\n");

    coord("moveto", sx, sy);

    coord("lineto", ex, ey);

    dlprintf("stroke %%PS\n");

#endif

    if (fixed2int(sy + fixed_half-1) == fixed2int(ey + fixed_half-1))

        return;

    if (sy > ey) {

        int t;

        t = sy; sy = ey; ey = t;

        t = sx; sx = ex; ex = t;

        dirn = DIRN_DOWN;

    }

    /* Lines go from sy to ey, closed at the start, open at the end. */

    /* We clip them to a region to make them closed at both ends. */

    /* Thus the first scanline marked (>= sy) is: */

    clip_sy = ((sy + fixed_half - 1) & ~(fixed_1-1)) | fixed_half;

    /* The last scanline marked (< ey) is: */

    clip_ey = ((ey - fixed_half - 1) & ~(fixed_1-1)) | fixed_half;

    /* Now allow for banding */

    if (clip_sy < int2fixed(base_y) + fixed_half)

        clip_sy = int2fixed(base_y) + fixed_half;

    if (ey <= clip_sy)

        return;

    if (clip_ey > int2fixed(base_y + height - 1) + fixed_half)

        clip_ey = int2fixed(base_y + height - 1) + fixed_half;

    if (sy > clip_ey)

        return;

    delta = (int64_t)clip_sy - (int64_t)sy;

    if (delta > 0)

    {

        int64_t dx = (int64_t)ex - (int64_t)sx;

        int64_t dy = (int64_t)ey - (int64_t)sy;

        int advance = (int)((dx * delta + (dy>>1)) / dy);

        sx += advance;

        sy += delta;

    }

    delta = (int64_t)ey - (int64_t)clip_ey;

    if (delta > 0)

    {

        int64_t dx = (int64_t)ex - (int64_t)sx;

        int64_t dy = (int64_t)ey - (int64_t)sy;

        int advance = (int)((dx * delta + (dy>>1)) / dy);

        ex -= advance;

        ey -= delta;

    }

    ex -= sx;

    ey -= sy;

    ih = fixed2int(ey);

    assert(ih >= 0);

    iy = fixed2int(sy) - base_y;

#ifdef DEBUG_SCAN_CONVERTER

    if (debugging_scan_converter)

        dlprintf2("    iy=%x ih=%x\n", iy, ih);

#endif

    assert(iy >= 0 && iy < height);

    /* We always cross at least one scanline */

    row = &table[index[iy]];

    *row = (*row)+1; /* Increment the count */

    row[*row] = (sx&~1) | dirn;

    if (ih == 0)

        return;

    if (ex >= 0) {

        int x_inc, n_inc, f;

        /* We want to change sx by ex in ih steps. So each step, we add

         * ex/ih to sx. That's x_inc + n_inc/ih.

         */

        x_inc = ex/ih;

        n_inc = ex-(x_inc*ih);

        f     = ih>>1;

        delta = ih;

        do {

            int count;

            iy++;

            sx += x_inc;

            f  -= n_inc;

            if (f < 0) {

                f += ih;

                sx++;

            }

            assert(iy >= 0 && iy < height);

            row = &table[index[iy]];

            count = *row = (*row)+1; /* Increment the count */

            row[count] = (sx&~1) | dirn;

        } while (--delta);

    } else {

        int x_dec, n_dec, f;

        ex = -ex;

        /* We want to change sx by ex in ih steps. So each step, we subtract

         * ex/ih from sx. That's x_dec + n_dec/ih.

         */

        x_dec = ex/ih;

        n_dec = ex-(x_dec*ih);

        f     = ih>>1;

        delta = ih;

        do {

            int count;

            iy++;

            sx -= x_dec;

            f  -= n_dec;

            if (f < 0) {

                f += ih;

                sx--;

            }

            assert(iy >= 0 && iy < height);

            row = &table[index[iy]];

            count = *row = (*row)+1; /* Increment the count */

            row[count] = (sx&~1) | dirn;

        } while (--delta);

    }

}

static void mark_curve(fixed sx, fixed sy, fixed c1x, fixed c1y, fixed c2x, fixed c2y, fixed ex, fixed ey, fixed base_y, fixed height, int *table, int *index, int depth)

{

    fixed ax = (sx + c1x)>>1;

    fixed ay = (sy + c1y)>>1;

    fixed bx = (c1x + c2x)>>1;

    fixed by = (c1y + c2y)>>1;

    fixed cx = (c2x + ex)>>1;

    fixed cy = (c2y + ey)>>1;

    fixed dx = (ax + bx)>>1;

    fixed dy = (ay + by)>>1;

    fixed fx = (bx + cx)>>1;

    fixed fy = (by + cy)>>1;

    fixed gx = (dx + fx)>>1;

    fixed gy = (dy + fy)>>1;

    assert(depth >= 0);

    if (depth == 0)

        mark_line(sx, sy, ex, ey, base_y, height, table, index);

    else {

        depth--;

        mark_curve(sx, sy, ax, ay, dx, dy, gx, gy, base_y, height, table, index, depth);

        mark_curve(gx, gy, fx, fy, cx, cy, ex, ey, base_y, height, table, index, depth);

    }

}

static void mark_curve_big(fixed64 sx, fixed64 sy, fixed64 c1x, fixed64 c1y, fixed64 c2x, fixed64 c2y, fixed64 ex, fixed64 ey, fixed base_y, fixed height, int *table, int *index, int depth)

{

    fixed64 ax = (sx + c1x)>>1;

    fixed64 ay = (sy + c1y)>>1;

    fixed64 bx = (c1x + c2x)>>1;

    fixed64 by = (c1y + c2y)>>1;

    fixed64 cx = (c2x + ex)>>1;

    fixed64 cy = (c2y + ey)>>1;

    fixed64 dx = (ax + bx)>>1;

    fixed64 dy = (ay + by)>>1;

    fixed64 fx = (bx + cx)>>1;

    fixed64 fy = (by + cy)>>1;

    fixed64 gx = (dx + fx)>>1;

    fixed64 gy = (dy + fy)>>1;

    assert(depth >= 0);

    if (depth == 0)

        mark_line((fixed)sx, (fixed)sy, (fixed)ex, (fixed)ey, base_y, height, table, index);

    else {

        depth--;

        mark_curve_big(sx, sy, ax, ay, dx, dy, gx, gy, base_y, height, table, index, depth);

        mark_curve_big(gx, gy, fx, fy, cx, cy, ex, ey, base_y, height, table, index, depth);

    }

}

static void mark_curve_top(fixed sx, fixed sy, fixed c1x, fixed c1y, fixed c2x, fixed c2y, fixed ex, fixed ey, fixed base_y, fixed height, int *table, int *index, int depth)

{

    fixed test = (sx^(sx<<1))|(sy^(sy<<1))|(c1x^(c1x<<1))|(c1y^(c1y<<1))|(c2x^(c2x<<1))|(c2y^(c2y<<1))|(ex^(ex<<1))|(ey^(ey<<1));

    if (test < 0)

        mark_curve_big(sx, sy, c1x, c1y, c2x, c2y, ex, ey, base_y, height, table, index, depth);

    else

        mark_curve(sx, sy, c1x, c1y, c2x, c2y, ex, ey, base_y, height, table, index, depth);

}

static int make_bbox(gx_path       * path,

               const gs_fixed_rect * clip,

                     gs_fixed_rect * bbox,

                     gs_fixed_rect * ibox,

                     fixed           adjust)

{

    int           code;

    int           ret = 0;

    /* Find the bbox - fixed */

    code = gx_path_bbox(path, bbox);

    if (code < 0)

        return code;

    if (bbox->p.y == bbox->q.y) {

        /* Zero height path */

        if (!clip ||

            (bbox->p.y >= clip->p.y && bbox->q.y <= clip->q.y)) {

            /* Either we're not clipping, or we are vertically inside the clip */

            if (clip) {

                if (bbox->p.x < clip->p.x)

                    bbox->p.x = clip->p.x;

                if (bbox->q.x > clip->q.x)

                    bbox->q.x = clip->q.x;

            }

            if (bbox->p.x <= bbox->q.x) {

                /* Zero height rectangle, not clipped completely away */

                ret = 1;

            }

        }

    }

    if (clip) {

        if (bbox->p.y < clip->p.y)

            bbox->p.y = clip->p.y;

        if (bbox->q.y > clip->q.y)

            bbox->q.y = clip->q.y;

    }

    /* Convert to bbox - int */

    ibox->p.x = fixed2int(bbox->p.x+adjust-(adjust?1:0));

    ibox->p.y = fixed2int(bbox->p.y+adjust-(adjust?1:0));

    ibox->q.x = fixed2int(bbox->q.x-adjust+fixed_1);

    ibox->q.y = fixed2int(bbox->q.y-adjust+fixed_1);

    return ret;

}

static inline int

make_table_template(gx_device     * pdev,

                    gx_path       * path,

                    gs_fixed_rect * ibox,

                    int             intersection_size,

                    int             adjust,

                    int           * scanlinesp,

                    int          ** indexp,

                    int          ** tablep)

{

    int             scanlines;

    const subpath * gs_restrict psub;

    int           * gs_restrict index;

    int           * gs_restrict table;

    int             i;

    int64_t         offset;

    int             delta;

    fixed           base_y;

    *scanlinesp = 0;

    *indexp     = NULL;

    *tablep     = NULL;

    if (pdev->max_fill_band != 0)

        ibox->p.y &= ~(pdev->max_fill_band-1);

    base_y = ibox->p.y;

    /* Previously we took adjust as a fixed distance to add to miny/maxy

     * to allow for the expansion due to 'any part of a pixel'. This causes

     * problems with over/underflow near INT_MAX/INT_MIN, so instead we

     * take adjust as boolean telling us whether to expand y by 1 or not, and

     * then adjust the assignments into the index as appropriate. This

     * solves Bug 697970. */

    /* Step 1: Make us a table */

    scanlines = ibox->q.y-base_y;

    /* +1+adjust simplifies the loop below */

    index = (int *)gs_alloc_bytes(pdev->memory,

                                  (scanlines+1+adjust) * sizeof(*index),

                                  "scanc index buffer");

    if (index == NULL)

        return_error(gs_error_VMerror);

    /* Step 1 continued: Blank the index */

    memset(index, 0, (scanlines+1)*sizeof(int));

    /* Step 1 continued: Run through the path, filling in the index */

    for (psub = path->first_subpath; psub != 0;) {

        const segment * gs_restrict pseg = (const segment *)psub;

        fixed          ey = pseg->pt.y;

        fixed          iy = ey;

        int            iey = fixed2int(iy) - base_y;

        assert(pseg->type == s_start);

        /* Allow for 2 extra intersections on the start scanline.

         * This copes with the 'zero height rectangle' case. */

        if (iey >= 0 && iey < scanlines)

        {

            index[iey] += 2;

            if (iey+1 < scanlines)

                index[iey+1] -= 2;

        }

        while ((pseg = pseg->next) != 0 &&

               pseg->type != s_start

            ) {

            fixed sy = ey;

            ey = pseg->pt.y;

            switch (pseg->type) {

                default:

                case s_start: /* Should never happen */

                case s_dash:  /* We should never be seeing a dash here */

                    assert("This should never happen" == NULL);

                    break;

                case s_curve: {

                    const curve_segment *const gs_restrict pcur = (const curve_segment *)pseg;

                    fixed c1y = pcur->p1.y;

                    fixed c2y = pcur->p2.y;

                    fixed maxy = sy, miny = sy;

                    int imaxy, iminy;

                    if (miny > c1y)

                        miny = c1y;

                    if (miny > c2y)

                        miny = c2y;

                    if (miny > ey)

                        miny = ey;

                    if (maxy < c1y)

                        maxy = c1y;

                    if (maxy < c2y)

                        maxy = c2y;

                    if (maxy < ey)

                        maxy = ey;

#ifdef DEBUG_SCAN_CONVERTER

                    if (debugging_scan_converter)

                        dlprintf2("Curve (%x->%x) ", miny, maxy);

#endif

                    iminy = fixed2int(miny) - base_y;

                    if (iminy <= 0)

                        iminy = 0;

                    else

                        iminy -= adjust;

                    if (iminy < scanlines) {

                        imaxy = fixed2int(maxy) - base_y;

                        if (imaxy >= 0) {

#ifdef DEBUG_SCAN_CONVERTER

                            if (debugging_scan_converter)

                                dlprintf1("+%x ", iminy);

#endif

                            index[iminy]+=3;

                            if (imaxy < scanlines) {

#ifdef DEBUG_SCAN_CONVERTER

                                if (debugging_scan_converter)

                                    dlprintf1("-%x ", imaxy+1);

#endif

                                index[imaxy+1+adjust]-=3;

                            }

                        }

                    }

#ifdef DEBUG_SCAN_CONVERTER

                    if (debugging_scan_converter)

                        dlprintf("\n");

#endif

                    break;

                }

                case s_gap:

                case s_line:

                case s_line_close: {

                    fixed miny, maxy;

                    int imaxy, iminy;

                    if (sy == ey) {

#ifdef DEBUG_SCAN_CONVERTER

                        if (debugging_scan_converter)

                            dlprintf("Line (Horiz)\n");

#endif

                        break;

                    }

                    if (sy < ey)

                        miny = sy, maxy = ey;

                    else

                        miny = ey, maxy = sy;

#ifdef DEBUG_SCAN_CONVERTER

                    if (debugging_scan_converter)

                        dlprintf2("Line (%x->%x) ", miny, maxy);

#endif

                    iminy = fixed2int(miny) - base_y;

                    if (iminy <= 0)

                        iminy = 0;

                    else

                        iminy -= adjust;

                    if (iminy < scanlines) {

                        imaxy = fixed2int(maxy) - base_y;

                        if (imaxy >= 0) {

#ifdef DEBUG_SCAN_CONVERTER

                            if (debugging_scan_converter)

                                dlprintf1("+%x ", iminy);

#endif

                            index[iminy]++;

                            if (imaxy < scanlines) {

#ifdef DEBUG_SCAN_CONVERTER

                                if (debugging_scan_converter)

                                    dlprintf1("-%x ", imaxy+1);

#endif

                                index[imaxy+1+adjust]--;

                            }

                        }

                    }

#ifdef DEBUG_SCAN_CONVERTER

                    if (debugging_scan_converter)

                        dlprintf("\n");

#endif

                    break;

                }

            }

        }

        /* And close any segments that need it */

        if (ey != iy) {

            fixed miny, maxy;

            int imaxy, iminy;

            if (iy < ey)

                miny = iy, maxy = ey;

            else

                miny = ey, maxy = iy;

#ifdef DEBUG_SCAN_CONVERTER

            if (debugging_scan_converter)

                dlprintf2("Close (%x->%x) ", miny, maxy);

#endif

            iminy = fixed2int(miny) - base_y;

            if (iminy <= 0)

                iminy = 0;

            else

                iminy -= adjust;

            if (iminy < scanlines) {

                imaxy = fixed2int(maxy) - base_y;

                if (imaxy >= 0) {

#ifdef DEBUG_SCAN_CONVERTER

                    if (debugging_scan_converter)

                        dlprintf1("+%x ", iminy);

#endif

                    index[iminy]++;

                    if (imaxy < scanlines) {

#ifdef DEBUG_SCAN_CONVERTER

                        if (debugging_scan_converter)

                            dlprintf1("-%x ", imaxy+1);

#endif

                        index[imaxy+1+adjust]--;

                    }

                }

            }

#ifdef DEBUG_SCAN_CONVERTER

            if (debugging_scan_converter)

                dlprintf("\n");

#endif

        }

#ifdef DEBUG_SCAN_CONVERTER

        if (debugging_scan_converter)

            dlprintf("\n");

#endif

        psub = (const subpath *)pseg;

    }

    /* Step 1 continued: index now contains a list of deltas (how the

     * number of intersects on line x differs from the number on line x-1).

     * First convert them to be the real number of intersects on that line.

     * Sum these values to get us the total number of intersects. Then

     * convert the table to be a list of offsets into the real intersect

     * buffer. */

    offset = 0;

    delta  = 0;

    for (i=0; i < scanlines+adjust; i++) {

        delta    += intersection_size*index[i];  /* delta = Num ints on this scanline. */

        index[i]  = offset;                      /* Offset into table for this lines data. */

        offset   += delta+1;                     /* Adjust offset for next line. */

    }

    /* Ensure we always have enough room for our zero height rectangle hack. */

    if (offset < 2*intersection_size)

        offset += 2*intersection_size;

    offset *= sizeof(*table);

    /* Try to keep the size to 1Meg. This is enough for the vast majority

     * of files. Allow us to grow above this if it would mean dropping

     * the height below a suitably small number (set to be larger than

     * any max_fill_band we might meet). */

    if (scanlines > 16 && offset > 1024*1024) { /* Arbitrary */

        gs_free_object(pdev->memory, index, "scanc index buffer");

        return offset/(1024*1024) + 1;

    }

    /* In the case where we have let offset be large, at least make sure

     * it's not TOO large for us to malloc. */

    if (offset != (int64_t)(uint)offset)

    {

        gs_free_object(pdev->memory, index, "scanc index buffer");

        return_error(gs_error_VMerror);

    }

    /* End of step 1: index[i] = offset into table 2 for scanline i's

     * intersection data. offset = Total number of int entries required for

     * table. */

    /* Step 2: Collect the real intersections */

    table = (int *)gs_alloc_bytes(pdev->memory, offset,

                                  "scanc intersects buffer");

    if (table == NULL) {

        gs_free_object(pdev->memory, index, "scanc index buffer");

        return_error(gs_error_VMerror);

    }

    /* Step 2 continued: initialise table's data; each scanlines data starts

     * with a count of the number of intersects so far, followed by a record

     * of the intersect points on this scanline. */

    for (i=0; i < scanlines; i++) {

        table[index[i]] = 0;

    }

    *scanlinesp = scanlines;

    *tablep     = table;

    *indexp     = index;

    return 0;

}

static int make_table(gx_device     * pdev,

                      gx_path       * path,

                      gs_fixed_rect * ibox,

                      int           * scanlines,

                      int          ** index,

                      int          ** table)

{

    return make_table_template(pdev, path, ibox, 1, 1, scanlines, index, table);

}

static void

fill_zero(int *row, const fixed *x)

{

    int n = *row = (*row)+2; /* Increment the count */

    row[n-1] = (x[0]&~1);

    row[n  ] = (x[1]|1);

}

int gx_scan_convert(gx_device     * gs_restrict pdev,

                    gx_path       * gs_restrict path,

              const gs_fixed_rect * gs_restrict clip,

                    gx_edgebuffer * gs_restrict edgebuffer,

                    fixed                       fixed_flat)

{

    gs_fixed_rect  ibox;

    gs_fixed_rect  bbox;

    int            scanlines;

    const subpath *psub;

    int           *index;

    int           *table;

    int            i;

    int            code;

    int            zero;

    edgebuffer->index = NULL;

    edgebuffer->table = NULL;

    /* Bale out if no actual path. We see this with the clist */

    if (path->first_subpath == NULL)

        return 0;

    zero = make_bbox(path, clip, &bbox, &ibox, fixed_half);

    if (zero < 0)

        return zero;

    if (ibox.q.y <= ibox.p.y)

        return 0;

    code = make_table(pdev, path, &ibox, &scanlines, &index, &table);

    if (code != 0) /* >0 means "retry with smaller height" */

        return code;

    if (scanlines == 0)

        return 0;

    if (zero) {

        code = zero_case(pdev, path, &ibox, index, table, fixed_flat, fill_zero);

    } else {

    /* Step 2 continued: Now we run through the path, filling in the real

     * values. */

    for (psub = path->first_subpath; psub != 0;) {

        const segment *pseg = (const segment *)psub;

        fixed ex = pseg->pt.x;

        fixed ey = pseg->pt.y;

        fixed ix = ex;

        fixed iy = ey;

        while ((pseg = pseg->next) != 0 &&

               pseg->type != s_start

            ) {

            fixed sx = ex;

            fixed sy = ey;

            ex = pseg->pt.x;

            ey = pseg->pt.y;

            switch (pseg->type) {

                default:

                case s_start: /* Should never happen */

                case s_dash:  /* We should never be seeing a dash here */

                    assert("This should never happen" == NULL);

                    break;

                case s_curve: {

                    const curve_segment *const pcur = (const curve_segment *)pseg;

                    int k = gx_curve_log2_samples(sx, sy, pcur, fixed_flat);

                    mark_curve_top(sx, sy, pcur->p1.x, pcur->p1.y, pcur->p2.x, pcur->p2.y, ex, ey, ibox.p.y, scanlines, table, index, k);

                    break;

                }

                case s_gap:

                case s_line:

                case s_line_close:

                    if (sy != ey)

                        mark_line(sx, sy, ex, ey, ibox.p.y, scanlines, table, index);

                    break;

            }

        }

        /* And close any open segments */

        if (iy != ey)

            mark_line(ex, ey, ix, iy, ibox.p.y, scanlines, table, index);

        psub = (const subpath *)pseg;

    }

    }

    /* Step 2 complete: We now have a complete list of intersection data in

     * table, indexed by index. */

    edgebuffer->base   = ibox.p.y;

    edgebuffer->height = scanlines;

    edgebuffer->xmin   = ibox.p.x;

    edgebuffer->xmax   = ibox.q.x;

    edgebuffer->index  = index;

    edgebuffer->table  = table;

#ifdef DEBUG_SCAN_CONVERTER

    if (debugging_scan_converter) {

        dlprintf("Before sorting:\n");

        gx_edgebuffer_print(edgebuffer);

    }

#endif

    /* Step 3: Sort the intersects on x */

    for (i=0; i < scanlines; i++) {

        int *row = &table[index[i]];

        int  rowlen = *row++;

        /* Bubblesort short runs, qsort longer ones. */

        /* FIXME: Check "6" below */

        if (rowlen <= 6) {

            int j, k;

            for (j = 0; j < rowlen-1; j++) {

                int t = row[j];

                for (k = j+1; k < rowlen; k++) {

                    int s = row[k];

                    if (t > s)

                         row[k] = t, t = row[j] = s;

                }

            }

        } else

            qsort(row, rowlen, sizeof(int), intcmp);

    }

    return 0;

}

/* Step 5: Filter the intersections according to the rules */

int

gx_filter_edgebuffer(gx_device       * gs_restrict pdev,

                     gx_edgebuffer   * gs_restrict edgebuffer,

                     int                        rule)

{

    int i;

#ifdef DEBUG_SCAN_CONVERTER

    if (debugging_scan_converter) {

        dlprintf("Before filtering:\n");

        gx_edgebuffer_print(edgebuffer);

    }

#endif

    for (i=0; i < edgebuffer->height; i++) {

        int *row      = &edgebuffer->table[edgebuffer->index[i]];

        int *rowstart = row;

        int  rowlen   = *row++;

        int *rowout   = row;

        while (rowlen > 0)

        {

            int left, right;

            if (rule == gx_rule_even_odd) {

                /* Even Odd */

                left  = (*row++)&~1;

                right = (*row++)&~1;

                rowlen -= 2;

            } else {

                /* Non-Zero */

                int w;

                left = *row++;

                w = ((left&1)-1) | (left&1);

                rowlen--;

                do {

                    right  = *row++;

                    rowlen--;

                    w += ((right&1)-1) | (right&1);

                } while (w != 0);

                left &= ~1;

                right &= ~1;

            }