File: gxshade6.c

package info (click to toggle)
ghostscript 10.0.0~dfsg-11%2Bdeb12u7
links: PTS, VCS
area: main
in suites: bookworm
size: 98,252 kB
sloc: ansic: 891,828; python: 7,649; cpp: 6,493; cs: 6,209; sh: 6,043; java: 4,028; perl: 2,372; tcl: 1,639; makefile: 521; awk: 66; javascript: 43; yacc: 18
file content (4252 lines) | stat: -rw-r--r-- 163,773 bytes
/* Copyright (C) 2001-2022 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 the license contained in the file LICENSE in this distribution.

   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.
*/


/* Rendering for Coons and tensor patch shadings */
/*
   A contiguous non-overlapping decomposition
   of a tensor shading into linear color triangles.
 */
#include "memory_.h"
#include "gx.h"
#include "gserrors.h"
#include "gsmatrix.h"           /* for gscoord.h */
#include "gscoord.h"
#include "gscicach.h"
#include "gxcspace.h"
#include "gxdcolor.h"
#include "gxgstate.h"
#include "gxshade.h"
#include "gxdevcli.h"
#include "gxshade4.h"
#include "gxarith.h"
#include "gzpath.h"
#include "stdint_.h"
#include "math_.h"
#include "gsicc_cache.h"
#include "gxdevsop.h"

/* The original version of the shading code 'decompose's shadings into
 * smaller and smaller regions until they are smaller than 1 pixel, and then
 * fills them. (Either with a constant colour, or with a linear filled trap).
 *
 * Previous versions of the code (from svn revision 7936 until June 2011
 * (shortly after the switch to git)) changed this limit to be 1 point or 1
 * pixel (whichever is larger) (on the grounds that as resolution increases,
 * we are unlikely to be able to notice increasingly small inaccuracies in
 * the shading). Given how people abuse the resolution at which things are
 * rendered (especially when rendering to images that can subsequently be
 * zoomed), this seems a poor trade off. See bug 691152.
 *
 * The code has now been changed back to operate with the proper 1 pixel
 * decomposition, which will cost us performance in some cases. Should
 * people want to restore the previous operation, they should build with
 * MAX_SHADING_RESOLUTION predefined to 72. In general, this symbol can be
 * set to the maximum dpi that shading should ever be performed at. Leaving
 * it undefined will leave the default (1 pixel limit) in place.
 *
 * A possible future optimisation here may be to use different max shading
 * resolutions for linear and non-linear shadings; linear shadings appear to
 * result in calls to "fill linear traps", and non linear ones appear to
 * result in calls to "fill constant color". As such linear shadings are much
 * more forgiving of a higher decomposition threshold.
 */

#if NOFILL_TEST
static bool dbg_nofill = false;
#endif
#if SKIP_TEST
static int dbg_patch_cnt = 0;
static int dbg_quad_cnt = 0;
static int dbg_triangle_cnt = 0;
static int dbg_wedge_triangle_cnt = 0;
#endif

enum {
    min_linear_grades = 255 /* The minimal number of device color grades,
            required to apply linear color device functions. */
};

/* ================ Utilities ================ */

static int
allocate_color_stack(patch_fill_state_t *pfs, gs_memory_t *memory)
{
    if (pfs->color_stack != NULL)
        return 0;
    pfs->color_stack_step = offset_of(patch_color_t, cc.paint.values[pfs->num_components]);
    pfs->color_stack_step = (pfs->color_stack_step + sizeof(void *) - 1) / sizeof(void *) * sizeof(void *); /* Alignment */

    pfs->color_stack_size = pfs->color_stack_step * SHADING_COLOR_STACK_SIZE;
    pfs->color_stack = gs_alloc_bytes(memory, pfs->color_stack_size, "allocate_color_stack");
    if (pfs->color_stack == NULL)
        return_error(gs_error_VMerror);
    pfs->color_stack_limit = pfs->color_stack + pfs->color_stack_size;
    pfs->color_stack_ptr = pfs->color_stack;
    pfs->memory = memory;
    return 0;
}

static inline byte *
reserve_colors_inline(patch_fill_state_t *pfs, patch_color_t *c[], int n)
{
    int i;
    byte *ptr0 = pfs->color_stack_ptr, *ptr = ptr0;

    for (i = 0; i < n; i++, ptr += pfs->color_stack_step)
        c[i] = (patch_color_t *)ptr;
    if (ptr > pfs->color_stack_limit) {
        c[0] = NULL; /* safety. */
        return NULL;
    }
    pfs->color_stack_ptr = ptr;
    return ptr0;
}

byte *
reserve_colors(patch_fill_state_t *pfs, patch_color_t *c[], int n)
{
    return reserve_colors_inline(pfs, c, n);
}

static inline void
release_colors_inline(patch_fill_state_t *pfs, byte *ptr, int n)
{
#if 0 /* Saving the invariant for records. */
    pfs->color_stack_ptr = pfs->color_stack_step * n;
    assert((byte *)pfs->color_stack_ptr == ptr);
#else
    pfs->color_stack_ptr = ptr;
#endif
}
void
release_colors(patch_fill_state_t *pfs, byte *ptr, int n)
{
    release_colors_inline(pfs, ptr, n);
}

/* Get colors for patch vertices. */
static int
shade_next_colors(shade_coord_stream_t * cs, patch_curve_t * curves,
                  int num_vertices)
{
    int i, code = 0;

    for (i = 0; i < num_vertices && code >= 0; ++i) {
        curves[i].vertex.cc[1] = 0; /* safety. (patch_fill may assume 2 arguments) */
        code = shade_next_color(cs, curves[i].vertex.cc);
    }
    return code;
}

/* Get a Bezier or tensor patch element. */
static int
shade_next_curve(shade_coord_stream_t * cs, patch_curve_t * curve)
{
    int code = shade_next_coords(cs, &curve->vertex.p, 1);

    if (code >= 0)
        code = shade_next_coords(cs, curve->control,
                                 countof(curve->control));
    return code;
}

/*
 * Parse the next patch out of the input stream.  Return 1 if done,
 * 0 if patch, <0 on error.
 */
static int
shade_next_patch(shade_coord_stream_t * cs, int BitsPerFlag,
        patch_curve_t curve[4], gs_fixed_point interior[4] /* 0 for Coons patch */)
{
    int flag = shade_next_flag(cs, BitsPerFlag);
    int num_colors, code;

    if (flag < 0) {
        if (!cs->is_eod(cs))
            return_error(gs_error_rangecheck);
        return 1;               /* no more data */
    }
    if (cs->first_patch && (flag & 3) != 0) {
        return_error(gs_error_rangecheck);
    }
    cs->first_patch = 0;
    switch (flag & 3) {
        default:
            return_error(gs_error_rangecheck);  /* not possible */
        case 0:
            if ((code = shade_next_curve(cs, &curve[0])) < 0 ||
                (code = shade_next_coords(cs, &curve[1].vertex.p, 1)) < 0
                )
                return code;
            num_colors = 4;
            goto vx;
        case 1:
            curve[0] = curve[1], curve[1].vertex = curve[2].vertex;
            goto v3;
        case 2:
            curve[0] = curve[2], curve[1].vertex = curve[3].vertex;
            goto v3;
        case 3:
            curve[1].vertex = curve[0].vertex, curve[0] = curve[3];
v3:         num_colors = 2;
vx:         if ((code = shade_next_coords(cs, curve[1].control, 2)) < 0 ||
                (code = shade_next_curve(cs, &curve[2])) < 0 ||
                (code = shade_next_curve(cs, &curve[3])) < 0 ||
                (interior != 0 &&
                 (code = shade_next_coords(cs, interior, 4)) < 0) ||
                (code = shade_next_colors(cs, &curve[4 - num_colors],
                                          num_colors)) < 0
                )
                return code;
            cs->align(cs, 8); /* See shade_next_vertex. */
    }
    return 0;
}

static inline bool
is_linear_color_applicable(const patch_fill_state_t *pfs)
{
    if (!USE_LINEAR_COLOR_PROCS)
        return false;
    if (!colors_are_separable_and_linear(&pfs->dev->color_info))
        return false;
    if (gx_get_cmap_procs(pfs->pgs, pfs->dev)->is_halftoned(pfs->pgs, pfs->dev))
        return false;
    return true;
}

static int
alloc_patch_fill_memory(patch_fill_state_t *pfs, gs_memory_t *memory, const gs_color_space *pcs)
{
    int code;

    pfs->memory = memory;
#   if LAZY_WEDGES
        code = wedge_vertex_list_elem_buffer_alloc(pfs);
        if (code < 0)
            return code;
#   endif
    pfs->max_small_coord = 1 << ((sizeof(int64_t) * 8 - 1/*sign*/) / 3);
    code = allocate_color_stack(pfs, memory);
    if (code < 0)
        return code;
    if (pfs->unlinear || pcs == NULL)
        pfs->pcic = NULL;
    else {
        pfs->pcic = gs_color_index_cache_create(memory, pcs, pfs->dev, pfs->pgs, true, pfs->trans_device);
        if (pfs->pcic == NULL)
            return_error(gs_error_VMerror);
    }
    return 0;
}

int
init_patch_fill_state(patch_fill_state_t *pfs)
{
    /* Warning : pfs->Function must be set in advance. */
    const gs_color_space *pcs = pfs->direct_space;
    gs_client_color fcc0, fcc1;
    int i;

    for (i = 0; i < pfs->num_components; i++) {
        fcc0.paint.values[i] = -1000000;
        fcc1.paint.values[i] = 1000000;
    }
    pcs->type->restrict_color(&fcc0, pcs);
    pcs->type->restrict_color(&fcc1, pcs);
    for (i = 0; i < pfs->num_components; i++)
        pfs->color_domain.paint.values[i] = max(fcc1.paint.values[i] - fcc0.paint.values[i], 1);
    pfs->vectorization = false; /* A stub for a while. Will use with pclwrite. */
    pfs->maybe_self_intersecting = true;
    pfs->monotonic_color = (pfs->Function == NULL);
    pfs->function_arg_shift = 0;
    pfs->linear_color = false;
    pfs->inside = false;
    pfs->n_color_args = 1;
#ifdef MAX_SHADING_RESOLUTION
    pfs->decomposition_limit = float2fixed(min(pfs->dev->HWResolution[0],
                                               pfs->dev->HWResolution[1]) / MAX_SHADING_RESOLUTION);
    pfs->decomposition_limit = max(pfs->decomposition_limit, fixed_1);
#else
    pfs->decomposition_limit = fixed_1;
#endif
    pfs->fixed_flat = float2fixed(pfs->pgs->flatness);
    /* Restrict the pfs->smoothness with 1/min_linear_grades, because cs_is_linear
       can't provide a better precision due to the color
       representation with integers.
     */
    pfs->smoothness = max(pfs->pgs->smoothness, 1.0 / min_linear_grades);
    pfs->color_stack_size = 0;
    pfs->color_stack_step = 0;
    pfs->color_stack_ptr = NULL;
    pfs->color_stack = NULL;
    pfs->color_stack_limit = NULL;
    pfs->unlinear = !is_linear_color_applicable(pfs);
    pfs->pcic = NULL;
    return alloc_patch_fill_memory(pfs, pfs->pgs->memory, pcs);
}

bool
term_patch_fill_state(patch_fill_state_t *pfs)
{
    bool b = (pfs->color_stack_ptr != pfs->color_stack);
#   if LAZY_WEDGES
        wedge_vertex_list_elem_buffer_free(pfs);
#   endif
    if (pfs->color_stack)
        gs_free_object(pfs->memory, pfs->color_stack, "term_patch_fill_state");
    if (pfs->pcic != NULL)
        gs_color_index_cache_destroy(pfs->pcic);
    return b;
}

/* Resolve a patch color using the Function if necessary. */
static inline void
patch_resolve_color_inline(patch_color_t * ppcr, const patch_fill_state_t *pfs)
{
    if (pfs->Function) {
        const gs_color_space *pcs = pfs->direct_space;

        gs_function_evaluate(pfs->Function, ppcr->t, ppcr->cc.paint.values);
        pcs->type->restrict_color(&ppcr->cc, pcs);
    }
}

void
patch_resolve_color(patch_color_t * ppcr, const patch_fill_state_t *pfs)
{
    patch_resolve_color_inline(ppcr, pfs);
}

/*
 * Calculate the interpolated color at a given point.
 * Note that we must do this twice for bilinear interpolation.
 * We use the name ppcr rather than ppc because an Apple compiler defines
 * ppc when compiling on PowerPC systems (!).
 */
static void
patch_interpolate_color(patch_color_t * ppcr, const patch_color_t * ppc0,
       const patch_color_t * ppc1, const patch_fill_state_t *pfs, double t)
{
    /* The old code gives -IND on Intel. */
    if (pfs->Function) {
        ppcr->t[0] = ppc0->t[0] * (1 - t) + t * ppc1->t[0];
        ppcr->t[1] = ppc0->t[1] * (1 - t) + t * ppc1->t[1];
        patch_resolve_color_inline(ppcr, pfs);
    } else {
        int ci;

        for (ci = pfs->num_components - 1; ci >= 0; --ci)
            ppcr->cc.paint.values[ci] =
                ppc0->cc.paint.values[ci] * (1 - t) + t * ppc1->cc.paint.values[ci];
    }
}

/* ================ Specific shadings ================ */

/*
 * The curves are stored in a clockwise or counter-clockwise order that maps
 * to the patch definition in a non-intuitive way.  The documentation
 * (pp. 277-281 of the PostScript Language Reference Manual, Third Edition)
 * says that the curves are in the order D1, C2, D2, C1.
 */
/* The starting points of the curves: */
#define D1START 0
#define C2START 1
#define D2START 3
#define C1START 0
/* The control points of the curves (x means reversed order): */
#define D1CTRL 0
#define C2CTRL 1
#define D2XCTRL 2
#define C1XCTRL 3
/* The end points of the curves: */
#define D1END 1
#define C2END 2
#define D2END 2
#define C1END 3

/* ---------------- Common code ---------------- */

/* Evaluate a curve at a given point. */
static void
curve_eval(gs_fixed_point * pt, const gs_fixed_point * p0,
           const gs_fixed_point * p1, const gs_fixed_point * p2,
           const gs_fixed_point * p3, double t)
{
    fixed a, b, c, d;
    fixed t01, t12;

    d = p0->x;
    curve_points_to_coefficients(d, p1->x, p2->x, p3->x,
                                 a, b, c, t01, t12);
    pt->x = (fixed) (((a * t + b) * t + c) * t + d);
    d = p0->y;
    curve_points_to_coefficients(d, p1->y, p2->y, p3->y,
                                 a, b, c, t01, t12);
    pt->y = (fixed) (((a * t + b) * t + c) * t + d);
    if_debug3('2', "[2]t=%g => (%g,%g)\n", t, fixed2float(pt->x),
              fixed2float(pt->y));
}

/* ---------------- Coons patch shading ---------------- */

/* Calculate the device-space coordinate corresponding to (u,v). */
static void
Cp_transform(gs_fixed_point * pt, const patch_curve_t curve[4],
             const gs_fixed_point ignore_interior[4], double u, double v)
{
    double co_u = 1.0 - u, co_v = 1.0 - v;
    gs_fixed_point c1u, d1v, c2u, d2v;

    curve_eval(&c1u, &curve[C1START].vertex.p,
               &curve[C1XCTRL].control[1], &curve[C1XCTRL].control[0],
               &curve[C1END].vertex.p, u);
    curve_eval(&d1v, &curve[D1START].vertex.p,
               &curve[D1CTRL].control[0], &curve[D1CTRL].control[1],
               &curve[D1END].vertex.p, v);
    curve_eval(&c2u, &curve[C2START].vertex.p,
               &curve[C2CTRL].control[0], &curve[C2CTRL].control[1],
               &curve[C2END].vertex.p, u);
    curve_eval(&d2v, &curve[D2START].vertex.p,
               &curve[D2XCTRL].control[1], &curve[D2XCTRL].control[0],
               &curve[D2END].vertex.p, v);
#define COMPUTE_COORD(xy)\
    pt->xy = (fixed)\
        ((co_v * c1u.xy + v * c2u.xy) + (co_u * d1v.xy + u * d2v.xy) -\
         (co_v * (co_u * curve[C1START].vertex.p.xy +\
                  u * curve[C1END].vertex.p.xy) +\
          v * (co_u * curve[C2START].vertex.p.xy +\
               u * curve[C2END].vertex.p.xy)))
    COMPUTE_COORD(x);
    COMPUTE_COORD(y);
#undef COMPUTE_COORD
    if_debug4('2', "[2](u=%g,v=%g) => (%g,%g)\n",
              u, v, fixed2float(pt->x), fixed2float(pt->y));
}

int
gs_shading_Cp_fill_rectangle(const gs_shading_t * psh0, const gs_rect * rect,
                             const gs_fixed_rect * rect_clip,
                             gx_device * dev, gs_gstate * pgs)
{
    const gs_shading_Cp_t * const psh = (const gs_shading_Cp_t *)psh0;
    patch_fill_state_t state;
    shade_coord_stream_t cs;
    patch_curve_t curve[4];
    int code;

    code = mesh_init_fill_state((mesh_fill_state_t *) &state,
                         (const gs_shading_mesh_t *)psh0, rect_clip, dev, pgs);
    if (code < 0) {
        if (state.icclink != NULL) gsicc_release_link(state.icclink);
        return code;
    }
    state.Function = psh->params.Function;
    code = init_patch_fill_state(&state);
    if(code < 0) {
        if (state.icclink != NULL) gsicc_release_link(state.icclink);
        return code;
    }

    curve[0].straight = curve[1].straight = curve[2].straight = curve[3].straight = false;
    shade_next_init(&cs, (const gs_shading_mesh_params_t *)&psh->params, pgs);
    while ((code = shade_next_patch(&cs, psh->params.BitsPerFlag,
                                    curve, NULL)) == 0 &&
           (code = patch_fill(&state, curve, NULL, Cp_transform)) >= 0
        ) {
        DO_NOTHING;
    }
    if (term_patch_fill_state(&state))
        return_error(gs_error_unregistered); /* Must not happen. */
    if (state.icclink != NULL) gsicc_release_link(state.icclink);
    return min(code, 0);
}

/* ---------------- Tensor product patch shading ---------------- */

/* Calculate the device-space coordinate corresponding to (u,v). */
static void
Tpp_transform(gs_fixed_point * pt, const patch_curve_t curve[4],
              const gs_fixed_point interior[4], double u, double v)
{
    double Bu[4], Bv[4];
    gs_fixed_point pts[4][4];
    int i, j;
    double x = 0, y = 0;

    /* Compute the Bernstein polynomials of u and v. */
    {
        double u2 = u * u, co_u = 1.0 - u, co_u2 = co_u * co_u;
        double v2 = v * v, co_v = 1.0 - v, co_v2 = co_v * co_v;

        Bu[0] = co_u * co_u2, Bu[1] = 3 * u * co_u2,
            Bu[2] = 3 * u2 * co_u, Bu[3] = u * u2;
        Bv[0] = co_v * co_v2, Bv[1] = 3 * v * co_v2,
            Bv[2] = 3 * v2 * co_v, Bv[3] = v * v2;
    }

    /* Arrange the points into an indexable order. */
    pts[0][0] = curve[0].vertex.p;
    pts[0][1] = curve[0].control[0];
    pts[0][2] = curve[0].control[1];
    pts[0][3] = curve[1].vertex.p;
    pts[1][3] = curve[1].control[0];
    pts[2][3] = curve[1].control[1];
    pts[3][3] = curve[2].vertex.p;
    pts[3][2] = curve[2].control[0];
    pts[3][1] = curve[2].control[1];
    pts[3][0] = curve[3].vertex.p;
    pts[2][0] = curve[3].control[0];
    pts[1][0] = curve[3].control[1];
    pts[1][1] = interior[0];
    pts[2][1] = interior[1];
    pts[2][2] = interior[2];
    pts[1][2] = interior[3];

    /* Now compute the actual point. */
    for (i = 0; i < 4; ++i)
        for (j = 0; j < 4; ++j) {
            double coeff = Bu[i] * Bv[j];

            x += pts[i][j].x * coeff, y += pts[i][j].y * coeff;
        }
    pt->x = (fixed)x, pt->y = (fixed)y;
}

int
gs_shading_Tpp_fill_rectangle(const gs_shading_t * psh0, const gs_rect * rect,
                             const gs_fixed_rect * rect_clip,
                              gx_device * dev, gs_gstate * pgs)
{
    const gs_shading_Tpp_t * const psh = (const gs_shading_Tpp_t *)psh0;
    patch_fill_state_t state;
    shade_coord_stream_t cs;
    patch_curve_t curve[4];
    gs_fixed_point interior[4];
    int code;

    code = mesh_init_fill_state((mesh_fill_state_t *) & state,
                         (const gs_shading_mesh_t *)psh0, rect_clip, dev, pgs);
    if (code < 0) {
        if (state.icclink != NULL) gsicc_release_link(state.icclink);
        return code;
    }
    state.Function = psh->params.Function;
    code = init_patch_fill_state(&state);
    if(code < 0)
        return code;
    curve[0].straight = curve[1].straight = curve[2].straight = curve[3].straight = false;
    shade_next_init(&cs, (const gs_shading_mesh_params_t *)&psh->params, pgs);
    while ((code = shade_next_patch(&cs, psh->params.BitsPerFlag,
                                    curve, interior)) == 0) {
        /*
         * The order of points appears to be consistent with that for Coons
         * patches, which is different from that documented in Red Book 3.
         */
        gs_fixed_point swapped_interior[4];

        swapped_interior[0] = interior[0];
        swapped_interior[1] = interior[3];
        swapped_interior[2] = interior[2];
        swapped_interior[3] = interior[1];
        code = patch_fill(&state, curve, swapped_interior, Tpp_transform);
        if (code < 0)
            break;
    }
    if (term_patch_fill_state(&state))
        return_error(gs_error_unregistered); /* Must not happen. */
    if (state.icclink != NULL) gsicc_release_link(state.icclink);
    return min(code, 0);
}

/*
    This algorithm performs a decomposition of the shading area
    into a set of constant color trapezoids, some of which
    may use the transpozed coordinate system.

    The target device assumes semi-open intrvals by X to be painted
    (See PLRM3, 7.5. Scan conversion details), i.e.
    it doesn't paint pixels which falls exactly to the right side.
    Note that with raster devices the algorithm doesn't paint pixels,
    whigh are partially covered by the shading area,
    but which's centers are outside the area.

    Pixels inside a monotonic part of the shading area are painted
    at once, but some exceptions may happen :

        - While flattening boundaries of a subpatch,
        to keep the plane coverage contiguity we insert wedges
        between neighbor subpatches, which use a different
        flattening factor. With non-monotonic curves
        those wedges may overlap or be self-overlapping, and a pixel
        is painted so many times as many wedges cover it. Fortunately
        the area of most wedges is zero or extremily small.

        - Since quazi-horizontal wedges may have a non-constant color,
        they can't decompose into constant color trapezoids with
        keeping the coverage contiguity. To represent them we
        apply the XY plane transposition. But with the transposition
        a semiopen interval can met a non-transposed one,
        so that some lines are not covered. Therefore we emulate
        closed intervals with expanding the transposed trapesoids in
        fixed_epsilon, and pixels at that boundary may be painted twice.

        - A boundary of a monotonic area can't compute in XY
        preciselly due to high order polynomial equations.
        Therefore the subdivision near the monotonity boundary
        may paint some pixels twice within same monotonic part.

    Non-monotonic areas slow down due to a tinny subdivision required.

    The target device may be either raster or vector.
    Vector devices should preciselly pass trapezoids to the output.
    Note that ends of sides of a trapesoid are not necessary
    the trapezoid's vertices. Converting this thing into
    an exact quadrangle may cause an arithmetic error,
    and the rounding must be done so that the coverage
    contiguity is not lost.

    When a device passes a trapezoid to it's output,
    a regular rounding would keep the coverage contiguity,
    except for the transposed trapesoids.
    If a transposed trapezoid is being transposed back,
    it doesn't become a canonic trapezoid, and a further
    decomposition is neccessary. But rounding errors here
    would break the coverage contiguity at boundaries
    of the tansposed part of the area.

    Devices, which have no transposed trapezoids and represent
    trapezoids only with 8 coordinates of vertices of the quadrangle
    (pclwrite is an example) may apply the backward transposition,
    and a clipping instead the further decomposition.
    Note that many clip regions may appear for all wedges.
    Note that in some cases the adjustment of the right side to be
    withdrown before the backward transposition.
 */
 /* We believe that a multiplication of 32-bit integers with a
    64-bit result is performed by modern platforms performs
    in hardware level. Therefore we widely use it here,
    but we minimize the usage of a multiplication of longer integers.

    Unfortunately we do need a multiplication of long integers
    in intersection_of_small_bars, because solving the linear system
    requires tripple multiples of 'fixed'. Therefore we retain
    of it's usage in the algorithm of the main branch.
    Configuration macro QUADRANGLES prevents it.
  */

typedef struct {
    gs_fixed_point pole[4][4]; /* [v][u] */
    patch_color_t *c[2][2];     /* [v][u] */
} tensor_patch;

typedef enum {
    interpatch_padding = 1, /* A Padding between patches for poorly designed documents. */
    inpatch_wedge = 2  /* Wedges while a patch decomposition. */
} wedge_type_t;

int
wedge_vertex_list_elem_buffer_alloc(patch_fill_state_t *pfs)
{
    const int max_level = LAZY_WEDGES_MAX_LEVEL;
    gs_memory_t *memory = pfs->memory;

    /* We have 'max_level' levels, each of which divides 1 or 3 sides.
       LAZY_WEDGES stores all 2^level divisions until
       the other area of same bnoundary is processed.
       Thus the upper estimation of the buffer size is :
       max_level * (1 << max_level) * 3.
       Likely this estimation to be decreased to
       max_level * (1 << max_level) * 2.
       because 1 side of a triangle is always outside the division path.
       For now we set the smaller estimation for obtaining an experimental data
       from the wild. */
    pfs->wedge_vertex_list_elem_count_max = max_level * (1 << max_level) * 2;
    pfs->wedge_vertex_list_elem_buffer = (wedge_vertex_list_elem_t *)gs_alloc_bytes(memory,
            sizeof(wedge_vertex_list_elem_t) * pfs->wedge_vertex_list_elem_count_max,
            "alloc_wedge_vertex_list_elem_buffer");
    if (pfs->wedge_vertex_list_elem_buffer == NULL)
        return_error(gs_error_VMerror);
    pfs->free_wedge_vertex = NULL;
    pfs->wedge_vertex_list_elem_count = 0;
    return 0;
}

void
wedge_vertex_list_elem_buffer_free(patch_fill_state_t *pfs)
{
    gs_memory_t *memory = pfs->memory;

    gs_free_object(memory, pfs->wedge_vertex_list_elem_buffer,
                "wedge_vertex_list_elem_buffer_free");
    pfs->wedge_vertex_list_elem_buffer = NULL;
    pfs->free_wedge_vertex = NULL;
}

static inline wedge_vertex_list_elem_t *
wedge_vertex_list_elem_reserve(patch_fill_state_t *pfs)
{
    wedge_vertex_list_elem_t *e = pfs->free_wedge_vertex;

    if (e != NULL) {
        pfs->free_wedge_vertex = e->next;
        return e;
    }
    if (pfs->wedge_vertex_list_elem_count < pfs->wedge_vertex_list_elem_count_max)
        return pfs->wedge_vertex_list_elem_buffer + pfs->wedge_vertex_list_elem_count++;
    return NULL;
}

static inline void
wedge_vertex_list_elem_release(patch_fill_state_t *pfs, wedge_vertex_list_elem_t *e)
{
    e->next = pfs->free_wedge_vertex;
    pfs->free_wedge_vertex = e;
}

static inline void
release_wedge_vertex_list_interval(patch_fill_state_t *pfs,
    wedge_vertex_list_elem_t *beg, wedge_vertex_list_elem_t *end)
{
    wedge_vertex_list_elem_t *e = beg->next, *ee;

    beg->next = end;
    end->prev = beg;
    for (; e != end; e = ee) {
        ee = e->next;
        wedge_vertex_list_elem_release(pfs, e);
    }
}

static inline int
release_wedge_vertex_list(patch_fill_state_t *pfs, wedge_vertex_list_t *ll, int n)
{
    int i;

    for (i = 0; i < n; i++) {
        wedge_vertex_list_t *l = ll + i;

        if (l->beg != NULL) {
            if (l->end == NULL)
                return_error(gs_error_unregistered); /* Must not happen. */
            release_wedge_vertex_list_interval(pfs, l->beg, l->end);
            wedge_vertex_list_elem_release(pfs, l->beg);
            wedge_vertex_list_elem_release(pfs, l->end);
            l->beg = l->end = NULL;
        } else if (l->end != NULL)
            return_error(gs_error_unregistered); /* Must not happen. */
    }
    return 0;
}

static inline wedge_vertex_list_elem_t *
wedge_vertex_list_find(wedge_vertex_list_elem_t *beg, const wedge_vertex_list_elem_t *end,
            int level)
{
    wedge_vertex_list_elem_t *e = beg;

    if (beg == NULL || end == NULL)
        return NULL; /* Must not happen. */
    for (; e != end; e = e->next)
        if (e->level == level)
            return e;
    return NULL;
}

static inline void
init_wedge_vertex_list(wedge_vertex_list_t *l, int n)
{
    memset(l, 0, sizeof(*l) * n);
}

/* For a given set of poles in the tensor patch (for instance
 * [0][0], [0][1], [0][2], [0][3] or [0][2], [1][2], [2][2], [3][2])
 * return the number of subdivisions required to flatten the bezier
 * given by those poles to the required flatness.
 */
static inline int
curve_samples(patch_fill_state_t *pfs,
                const gs_fixed_point *pole, int pole_step, fixed fixed_flat)
{
    curve_segment s;
    int k;

    s.p1.x = pole[pole_step].x;
    s.p1.y = pole[pole_step].y;
    s.p2.x = pole[pole_step * 2].x;
    s.p2.y = pole[pole_step * 2].y;
    s.pt.x = pole[pole_step * 3].x;
    s.pt.y = pole[pole_step * 3].y;
    k = gx_curve_log2_samples(pole[0].x, pole[0].y, &s, fixed_flat);
    {
#       if LAZY_WEDGES || QUADRANGLES
            int k1;
            fixed L = any_abs(pole[pole_step * 1].x - pole[pole_step * 0].x) + any_abs(pole[pole_step * 1].y - pole[pole_step * 0].y) +
                      any_abs(pole[pole_step * 2].x - pole[pole_step * 1].x) + any_abs(pole[pole_step * 2].y - pole[pole_step * 1].y) +
                      any_abs(pole[pole_step * 3].x - pole[pole_step * 2].x) + any_abs(pole[pole_step * 3].y - pole[pole_step * 2].y);
#       endif

#       if LAZY_WEDGES
            /* Restrict lengths for a reasonable memory consumption : */
            k1 = ilog2(L / fixed_1 / (1 << (LAZY_WEDGES_MAX_LEVEL - 1)));
            k = max(k, k1);
#       endif
#       if QUADRANGLES
            /* Restrict lengths for intersection_of_small_bars : */
            k = max(k, ilog2(L) - ilog2(pfs->max_small_coord));
#       endif
    }
    return 1 << k;
}

static inline bool
intersection_of_small_bars(const gs_fixed_point q[4], int i0, int i1, int i2, int i3, fixed *ry, fixed *ey)
{
    /* This function is only used with QUADRANGLES. */
    return gx_intersect_small_bars(q[i0].x, q[i0].y, q[i1].x, q[i1].y, q[i2].x, q[i2].y, q[i3].x, q[i3].y, ry, ey);
}

static inline void
adjust_swapped_boundary(fixed *b, bool swap_axes)
{
    if (swap_axes) {
        /*  Sinse the rasterizer algorithm assumes semi-open interval
            when computing pixel coverage, we should expand
            the right side of the area. Otherwise a dropout can happen :
            if the left neighbour is painted with !swap_axes,
            the left side of this area appears to be the left side
            of the neighbour area, and the side is not included
            into both areas.
         */
        *b += fixed_epsilon;
    }
}

static inline void
make_trapezoid(const gs_fixed_point q[4],
        int vi0, int vi1, int vi2, int vi3, fixed ybot, fixed ytop,
        bool swap_axes, bool orient, gs_fixed_edge *le, gs_fixed_edge *re)
{
    if (!orient) {
        le->start = q[vi0];
        le->end = q[vi1];
        re->start = q[vi2];
        re->end = q[vi3];
    } else {
        le->start = q[vi2];
        le->end = q[vi3];
        re->start = q[vi0];
        re->end = q[vi1];
    }
    adjust_swapped_boundary(&re->start.x, swap_axes);
    adjust_swapped_boundary(&re->end.x, swap_axes);
}

static inline int
gx_shade_trapezoid(patch_fill_state_t *pfs, const gs_fixed_point q[4],
        int vi0, int vi1, int vi2, int vi3, fixed ybot0, fixed ytop0,
        bool swap_axes, const gx_device_color *pdevc, bool orient)
{
    gs_fixed_edge le, re;
    int code;
    fixed ybot = max(ybot0, swap_axes ? pfs->rect.p.x : pfs->rect.p.y);
    fixed ytop = min(ytop0, swap_axes ? pfs->rect.q.x : pfs->rect.q.y);
    fixed xleft  = (swap_axes ? pfs->rect.p.y : pfs->rect.p.x);
    fixed xright = (swap_axes ? pfs->rect.q.y : pfs->rect.q.x);

    if (ybot >= ytop)
        return 0;
#   if NOFILL_TEST
        if (dbg_nofill)
            return 0;
#   endif
    make_trapezoid(q, vi0, vi1, vi2, vi3, ybot, ytop, swap_axes, orient, &le, &re);
    if (!pfs->inside) {
        bool clip = false;

        /* We are asked to clip a trapezoid to a rectangle. If the rectangle
         * is entirely contained within the rectangle, then no clipping is
         * actually required. If the left edge is entirely to the right of
         * the rectangle, or the right edge is entirely to the left, we
         * clip away to nothing. If the left edge is entirely to the left of
         * the rectangle, then we can simplify it to a vertical edge along
         * the edge of the rectangle. Likewise with the right edge if it's
         * entirely to the right of the rectangle.*/
        if (le.start.x > xright) {
            if (le.end.x > xright) {
                return 0;
            }
            clip = true;
        } else if (le.end.x > xright) {
            clip = true;
        }
        if (le.start.x < xleft) {
            if (le.end.x < xleft) {
                le.start.x = xleft;
                le.end.x   = xleft;
                le.start.y = ybot;
                le.end.y   = ytop;
            } else {
                clip = true;
            }
        } else if (le.end.x < xleft) {
            clip = true;
        }
        if (re.start.x < xleft) {
            if (re.end.x < xleft) {
                return 0;
            }
            clip = true;
        } else if (re.end.x < xleft) {
            clip = true;
        }
        if (re.start.x > xright) {
            if (re.end.x > xright) {
                re.start.x = xright;
                re.end.x   = xright;
                re.start.y = ybot;
                re.end.y   = ytop;
            } else {
                clip = true;
            }
        } else if (re.end.x > xright) {
            clip = true;
        }
        if (clip)
        {
            /* Some form of clipping seems to be required. A certain amount
             * of horridness goes on here to ensure that we round 'outwards'
             * in all cases. */
            gs_fixed_edge lenew, renew;
            fixed ybl, ybr, ytl, ytr, ymid;

            /* Reduce the clipping region horizontally if possible. */
            if (re.start.x > re.end.x) {
                if (re.start.x < xright)
                    xright = re.start.x;
            } else if (re.end.x < xright)
                xright = re.end.x;
            if (le.start.x > le.end.x) {
                if (le.end.x > xleft)
                    xleft = le.end.x;
            } else if (le.start.x > xleft)
                xleft = le.start.x;

            ybot = max(ybot, min(le.start.y, re.start.y));
            ytop = min(ytop, max(le.end.y, re.end.y));
#if 0
            /* RJW: I've disabled this code a) because it doesn't make any
             * difference in the cluster tests, and b) because I think it's wrong.
             * Taking the first case as an example; just because the le.start.x
             * is > xright, does not mean that we can simply truncate the edge at
             * xright, as this may throw away part of the trap between ybot and
             * the new le.start.y. */
            /* Reduce the edges to the left/right of the clipping region. */
            /* Only in the 4 cases which can bring ytop/ybot closer */
            if (le.start.x > xright) {
                le.start.y += (fixed)((int64_t)(le.end.y-le.start.y)*
                                      (int64_t)(le.start.x-xright)/
                                      (int64_t)(le.start.x-le.end.x));
                le.start.x = xright;
            }
            if (re.start.x < xleft) {
                re.start.y += (fixed)((int64_t)(re.end.y-re.start.y)*
                                      (int64_t)(xleft-re.start.x)/
                                      (int64_t)(re.end.x-re.start.x));
                re.start.x = xleft;
            }
            if (le.end.x > xright) {
                le.end.y -= (fixed)((int64_t)(le.end.y-le.start.y)*
                                    (int64_t)(le.end.x-xright)/
                                    (int64_t)(le.end.x-le.start.x));
                le.end.x = xright;
            }
            if (re.end.x < xleft) {
                re.end.y -= (fixed)((int64_t)(re.end.y-re.start.y)*
                                    (int64_t)(xleft-re.end.x)/
                                    (int64_t)(re.start.x-re.end.x));
                re.end.x = xleft;
            }
#endif

            if (ybot >= ytop)
                return 0;
            /* Follow the edges in, so that le.start.y == ybot etc. */
            if (le.start.y < ybot) {
                int round = ((le.end.x < le.start.x) ?
                             (le.end.y-le.start.y-1) : 0);
                le.start.x += (fixed)(((int64_t)(ybot-le.start.y)*
                                       (int64_t)(le.end.x-le.start.x)-round)/
                                      (int64_t)(le.end.y-le.start.y));
                le.start.y = ybot;
            }
            if (le.end.y > ytop) {
                int round = ((le.end.x > le.start.x) ?
                             (le.end.y-le.start.y-1) : 0);
                le.end.x += (fixed)(((int64_t)(le.end.y-ytop)*
                                     (int64_t)(le.start.x-le.end.x)-round)/
                                    (int64_t)(le.end.y-le.start.y));
                le.end.y = ytop;
            }
            if ((le.start.x < xleft) && (le.end.x < xleft)) {
                le.start.x = xleft;
                le.end.x   = xleft;
                le.start.y = ybot;
                le.end.y   = ytop;
            }
            if (re.start.y < ybot) {
                int round = ((re.end.x > re.start.x) ?
                             (re.end.y-re.start.y-1) : 0);
                re.start.x += (fixed)(((int64_t)(ybot-re.start.y)*
                                       (int64_t)(re.end.x-re.start.x)+round)/
                                      (int64_t)(re.end.y-re.start.y));
                re.start.y = ybot;
            }
            if (re.end.y > ytop) {
                int round = ((re.end.x < re.start.x) ?
                             (re.end.y-re.start.y-1) : 0);
                re.end.x += (fixed)(((int64_t)(re.end.y-ytop)*
                                     (int64_t)(re.start.x-re.end.x)+round)/
                                    (int64_t)(re.end.y-re.start.y));
                re.end.y = ytop;
            }
            if ((re.start.x > xright) && (re.end.x > xright)) {
                re.start.x = xright;
                re.end.x   = xright;
                re.start.y = ybot;
                re.end.y   = ytop;
            }
            /* Now, check whether the left and right edges cross. Previously
             * this comment said: "This can only happen (for well formed
             * input) in the case where one of the edges was completely out
             * of range and has now been pulled in to the edge of the clip
             * region." I now do not believe this to be true. */
            if (le.start.x > re.start.x) {
                if (le.start.x == le.end.x) {
                    if (re.start.x == re.end.x)
                        return 0;
                    ybot += (fixed)((int64_t)(re.end.y-re.start.y)*
                                    (int64_t)(le.start.x-re.start.x)/
                                    (int64_t)(re.end.x-re.start.x));
                    re.start.x = le.start.x;
                } else {
                    ybot += (fixed)((int64_t)(le.end.y-le.start.y)*
                                    (int64_t)(le.start.x-re.start.x)/
                                    (int64_t)(le.start.x-le.end.x));
                    le.start.x = re.start.x;
                }
                if (ybot >= ytop)
                    return 0;
                le.start.y = ybot;
                re.start.y = ybot;
            }
            if (le.end.x > re.end.x) {
                if (le.start.x == le.end.x) {
                    if (re.start.x == re.end.x)
                        return 0;
                    ytop -= (fixed)((int64_t)(re.end.y-re.start.y)*
                                    (int64_t)(le.end.x-re.end.x)/
                                    (int64_t)(re.start.x-re.end.x));
                    re.end.x = le.end.x;
                } else {
                    ytop -= (fixed)((int64_t)(le.end.y-le.start.y)*
                                    (int64_t)(le.end.x-re.end.x)/
                                    (int64_t)(le.end.x-le.start.x));
                    le.end.x = re.end.x;
                }
                if (ybot >= ytop)
                    return 0;
                le.end.y = ytop;
                re.end.y = ytop;
            }
            /* At this point we are guaranteed that le and re are constrained
             * as tightly as possible to the ybot/ytop range, and that the
             * entire ybot/ytop range will be marked at least somewhere. All
             * we need to do now is to actually fill the region.
             */
            lenew.start.x = xleft;
            lenew.start.y = ybot;
            lenew.end.x   = xleft;
            lenew.end.y   = ytop;
            renew.start.x = xright;
            renew.start.y = ybot;
            renew.end.x   = xright;
            renew.end.y   = ytop;
            /* Figure out where the left edge intersects with the left at
             * the bottom */
            ybl = ybot;
            if (le.start.x > le.end.x) {
                ybl += (fixed)((int64_t)(le.start.x-xleft) *
                               (int64_t)(le.end.y-le.start.y) /
                               (int64_t)(le.start.x-le.end.x));
                if (ybl > ytop)
                    ybl = ytop;
            }
            /* Figure out where the right edge intersects with the right at
             * the bottom */
            ybr = ybot;
            if (re.start.x < re.end.x) {
                ybr += (fixed)((int64_t)(xright-re.start.x) *
                               (int64_t)(re.end.y-re.start.y) /
                               (int64_t)(re.end.x-re.start.x));
                if (ybr > ytop)
                    ybr = ytop;
            }
            /* Figure out where the left edge intersects with the left at
             * the top */
            ytl = ytop;
            if (le.end.x > le.start.x) {
                ytl -= (fixed)((int64_t)(le.end.x-xleft) *
                               (int64_t)(le.end.y-le.start.y) /
                               (int64_t)(le.end.x-le.start.x));
                if (ytl < ybot)
                    ytl = ybot;
            }
            /* Figure out where the right edge intersects with the right at
             * the bottom */
            ytr = ytop;
            if (re.end.x < re.start.x) {
                ytr -= (fixed)((int64_t)(xright-re.end.x) *
                               (int64_t)(re.end.y-re.start.y) /
                               (int64_t)(re.start.x-re.end.x));
                if (ytr < ybot)
                    ytr = ybot;
            }
            /* Check for the 2 cases where top and bottom diagonal extents
             * overlap, and deal with them explicitly. */
            if (ytl < ybr) {
                /*     |     |
                 *  ---+-----+---
                 *     | /222|
                 *     |/111/|
                 *     |000/ |
                 *  ---+-----+---
                 *     |     |
                 */
                code = dev_proc(pfs->dev, fill_trapezoid)(pfs->dev,
                                        &lenew, &re, ybot, ytl,
                                        swap_axes, pdevc, pfs->pgs->log_op);
                if (code < 0)
                    return code;
                code = dev_proc(pfs->dev, fill_trapezoid)(pfs->dev,
                                        &le, &re, ytl, ybr,
                                        swap_axes, pdevc, pfs->pgs->log_op);
                if (code < 0)
                    return code;
                ybot = ybr;
                return dev_proc(pfs->dev, fill_trapezoid)(pfs->dev,
                                        &le, &renew, ybr, ytop,
                                        swap_axes, pdevc, pfs->pgs->log_op);
            } else if (ytr < ybl) {
                /*     |     |
                 *  ---+-----+----
                 *     |555\ |
                 *     |\444\|
                 *     | \333|
                 *  ---+-----+---
                 *     |     |
                 */
                code = dev_proc(pfs->dev, fill_trapezoid)(pfs->dev,
                                        &le, &renew, ybot, ytr,
                                        swap_axes, pdevc, pfs->pgs->log_op);
                if (code < 0)
                    return code;
                code = dev_proc(pfs->dev, fill_trapezoid)(pfs->dev,
                                        &le, &re, ytr, ybl,
                                        swap_axes, pdevc, pfs->pgs->log_op);
                if (code < 0)
                    return code;
                return dev_proc(pfs->dev, fill_trapezoid)(pfs->dev,
                                        &le, &re, ybl, ytop,
                                        swap_axes, pdevc, pfs->pgs->log_op);
            }
            /* Fill in any section where both left and right edges are
             * diagonal at the bottom */
            ymid = ybl;
            if (ymid > ybr)
                ymid = ybr;
            if (ymid > ybot) {
                /*     |\   |          |   /|
                 *     | \6/|    or    |\6/ |
                 *  ---+----+---    ---+----+---
                 *     |    |          |    |
                 */
                code = dev_proc(pfs->dev, fill_trapezoid)(pfs->dev,
                                        &le, &re, ybot, ymid,
                                        swap_axes, pdevc, pfs->pgs->log_op);
                if (code < 0)
                    return code;
                ybot = ymid;
            }
            /* Fill in any section where both left and right edges are
             * diagonal at the top */
            ymid = ytl;
            if (ymid < ytr)
                ymid = ytr;
            if (ymid < ytop) {
                /*     |    |          |    |
                 *  ---+----+---    ---+----+---
                 *     |/7\ |    or    | /7\|
                 *     |   \|          |/   |
                 */
                code = dev_proc(pfs->dev, fill_trapezoid)(pfs->dev,
                                        &le, &re, ymid, ytop,
                                        swap_axes, pdevc, pfs->pgs->log_op);
                if (code < 0)
                    return code;
                ytop = ymid;
            }
            /* Now do the single diagonal cases at the bottom */
            if (ybl > ybot) {
                /*     |    |
                 *     |\666|
                 *  ---+----+---
                 *     |    |
                 */
                code = dev_proc(pfs->dev, fill_trapezoid)(pfs->dev,
                                        &le, &renew, ybot, ybl,
                                        swap_axes, pdevc, pfs->pgs->log_op);
                if (code < 0)
                    return code;
                ybot = ybl;
            } else if (ybr > ybot) {
                /*     |    |
                 *     |777/|
                 *  ---+----+---
                 *     |    |
                 */
                code = dev_proc(pfs->dev, fill_trapezoid)(pfs->dev,
                                        &lenew, &re, ybot, ybr,
                                        swap_axes, pdevc, pfs->pgs->log_op);
                if (code < 0)
                    return code;
                ybot = ybr;
            }
            /* Now do the single diagonal cases at the top */
            if (ytl < ytop) {
                /*     |    |
                 *  ---+----+---
                 *     |/888|
                 *     |    |
                 */
                code = dev_proc(pfs->dev, fill_trapezoid)(pfs->dev,
                                        &le, &renew, ytl, ytop,
                                        swap_axes, pdevc, pfs->pgs->log_op);
                if (code < 0)
                    return code;
                ytop = ytl;
            } else if (ytr < ytop) {
                /*     |    |
                 *  ---+----+---
                 *     |999\|
                 *     |    |
                 */
                code = dev_proc(pfs->dev, fill_trapezoid)(pfs->dev,
                                        &lenew, &re, ytr, ytop,
                                        swap_axes, pdevc, pfs->pgs->log_op);
                if (code < 0)
                    return code;
                ytop = ytr;
            }
            /* And finally just whatever rectangular section is left over in
             * the middle */
            if (ybot > ytop)
                return 0;
            return dev_proc(pfs->dev, fill_trapezoid)(pfs->dev,
                                        &lenew, &renew, ybot, ytop,
                                        swap_axes, pdevc, pfs->pgs->log_op);
        }
    }
    return dev_proc(pfs->dev, fill_trapezoid)(pfs->dev,
            &le, &re, ybot, ytop, swap_axes, pdevc, pfs->pgs->log_op);
}

static inline void
dc2fc31(const patch_fill_state_t *pfs, gx_device_color *pdevc,
            frac31 fc[GX_DEVICE_COLOR_MAX_COMPONENTS])
{
    int j;
    const gx_device_color_info *cinfo = &pfs->trans_device->color_info;
    /* Note trans device is actually either the transparency parent
       device if transparency is present or the target device.  Basically
       the device from which we want to get the color information from
       for this */

    if (pdevc->type == &gx_dc_type_data_pure) {
        for (j = 0; j < cinfo->num_components; j++) {
                int shift = cinfo->comp_shift[j];
                int bits = cinfo->comp_bits[j];

                fc[j] = ((pdevc->colors.pure >> shift) & ((1 << bits) - 1)) <<
                        (sizeof(frac31) * 8 - 1 - bits);
        }
    } else {
        for (j = 0; j < cinfo->num_components; j++) {
                fc[j] = cv2frac31(pdevc->colors.devn.values[j]);
        }
    }
}

#define DEBUG_COLOR_INDEX_CACHE 0

static inline int
patch_color_to_device_color_inline(const patch_fill_state_t *pfs,
                                   const patch_color_t *c, gx_device_color *pdevc,
                                   frac31 *frac_values)
{
    /* Must return 2 if the color is not pure.
       See try_device_linear_color.
     */
    int code;
    gx_device_color devc;

#ifdef PACIFY_VALGRIND
    /* This is a hack to get us around some valgrind warnings seen
     * when transparency is in use with the clist. We run through
     * the shading code dealing with pfs->num_components components.
     * I believe this is intended to match the source space of the
     * shading, as we have to perform all shadings in the source
     * space initially, and only convert after decomposition.
     * When this reaches down to the clist writing phase, the
     * clist writes pfs->dev->color_info.num_components color
     * components to the clist. In the example I am using
     *  pfs->num_components = 1
     *  pfs->dev->color_info.num_components=3
     * So valgrind complains that 2 of the 3 color components
     * it is writing are uninitialised. Magically, it appears
     * not to actually use them when read back though, so
     * it suffices to blank them to kill the warnings now.
     * If pfs->num_components > pfs->dev->color_info.num_components
     * then we'll not be writing enough information to the clist
     * and so hopefully we'll see bad rendering!
     *
     * An example that shows why this is required:
     *  make gsdebugvg
     *  valgrind --track-origins=yes debugbin/gs -sOutputFile=test.ps
     *    -dMaxBitmap=1000 -sDEVICE=ps2write  -r300  -Z: -dNOPAUSE
     *    -dBATCH -K2000000 -dClusterJob Bug693480.pdf
     * (though ps2write is not implicated here).
     */
     if (frac_values) {
        int i;
	int n = pfs->dev->color_info.num_components;
	for (i = pfs->num_components; i < n; i++) {
            frac_values[i] = 0;
	}
    }
#endif

    if (DEBUG_COLOR_INDEX_CACHE && pdevc == NULL)
        pdevc = &devc;
    if (pfs->pcic) {
        code = gs_cached_color_index(pfs->pcic, c->cc.paint.values, pdevc, frac_values);
        if (code < 0)
            return code;
    }
    if (DEBUG_COLOR_INDEX_CACHE || pfs->pcic == NULL) {
#       if DEBUG_COLOR_INDEX_CACHE
        gx_color_index cindex = pdevc->colors.pure;
#       endif
        gs_client_color fcc;
        const gs_color_space *pcs = pfs->direct_space;

        if (pcs != NULL) {

            if (pdevc == NULL)
                pdevc = &devc;
            memcpy(fcc.paint.values, c->cc.paint.values,
                        sizeof(fcc.paint.values[0]) * pfs->num_components);
            code = pcs->type->remap_color(&fcc, pcs, pdevc, pfs->pgs,
                                      pfs->trans_device, gs_color_select_texture);
            if (code < 0)
                return code;
            if (frac_values != NULL) {
                if (!(pdevc->type == &gx_dc_type_data_devn ||
                      pdevc->type == &gx_dc_type_data_pure))
                    return 2;
                dc2fc31(pfs, pdevc, frac_values);
            }
#           if DEBUG_COLOR_INDEX_CACHE
            if (cindex != pdevc->colors.pure)
                return_error(gs_error_unregistered);
#           endif
        } else {
            /* This is reserved for future extension,
            when a linear color triangle with frac31 colors is being decomposed
            during a clist rasterization. In this case frac31 colors are written into
            the patch color, and pcs==NULL means an identity color mapping.
            For a while we assume here pfs->pcic is also NULL. */
            int j;
            const gx_device_color_info *cinfo = &pfs->dev->color_info;

            for (j = 0; j < cinfo->num_components; j++)
                frac_values[j] = (frac31)c->cc.paint.values[j];
            pdevc->type = &gx_dc_type_data_pure;
        }
    }
    return 0;
}

int
patch_color_to_device_color(const patch_fill_state_t *pfs, const patch_color_t *c, gx_device_color *pdevc)
{
    return patch_color_to_device_color_inline(pfs, c, pdevc, NULL);
}

static inline double
color_span(const patch_fill_state_t *pfs, const patch_color_t *c0, const patch_color_t *c1)
{
    int n = pfs->num_components, i;
    double m;

    /* Dont want to copy colors, which are big things. */
    m = any_abs(c1->cc.paint.values[0] - c0->cc.paint.values[0]) / pfs->color_domain.paint.values[0];
    for (i = 1; i < n; i++)
        m = max(m, any_abs(c1->cc.paint.values[i] - c0->cc.paint.values[i]) / pfs->color_domain.paint.values[i]);
    return m;
}

static inline void
color_diff(const patch_fill_state_t *pfs, const patch_color_t *c0, const patch_color_t *c1, patch_color_t *d)
{
    int n = pfs->num_components, i;

    for (i = 0; i < n; i++)
        d->cc.paint.values[i] = c1->cc.paint.values[i] - c0->cc.paint.values[i];
}

static inline double
color_norm(const patch_fill_state_t *pfs, const patch_color_t *c)
{
    int n = pfs->num_components, i;
    double m;

    m = any_abs(c->cc.paint.values[0]) / pfs->color_domain.paint.values[0];
    for (i = 1; i < n; i++)
        m = max(m, any_abs(c->cc.paint.values[i]) / pfs->color_domain.paint.values[i]);
    return m;
}

static inline int
isnt_color_monotonic(const patch_fill_state_t *pfs, const patch_color_t *c0, const patch_color_t *c1)
{   /* checks whether the color is monotonic in the n-dimensional interval,
       where n is the number of parameters in c0->t, c1->t.
       returns : 0 = monotonic,
       bit 0 = not or don't know by t0,
       bit 1 = not or don't know by t1,
       <0 = error. */
    /* When pfs->Function is not set, the color is monotonic.
       In this case do not call this function because
       it doesn't check whether pfs->Function is set.
       Actually pfs->monotonic_color prevents that.
     */
    /* This assumes that the color space is always monotonic.
       Non-monotonic color spaces are not recommended by PLRM,
       and the result with them may be imprecise.
     */
    uint mask;
    int code = gs_function_is_monotonic(pfs->Function, c0->t, c1->t, &mask);

    if (code >= 0)
        return mask;
    return code;
}

static inline bool
covers_pixel_centers(fixed ybot, fixed ytop)
{
    return fixed_pixround(ybot) < fixed_pixround(ytop);
}

static inline int
constant_color_trapezoid(patch_fill_state_t *pfs, gs_fixed_edge *le, gs_fixed_edge *re,
        fixed ybot, fixed ytop, bool swap_axes, const patch_color_t *c)
{
    gx_device_color dc;
    int code;

#   if NOFILL_TEST
        /* if (dbg_nofill)
                return 0; */
#   endif

    code = patch_color_to_device_color_inline(pfs, c, &dc, NULL);
    if (code < 0)
        return code;

    if (device_encodes_tags(pfs->dev)) {
        dc.tag = (pfs->dev->graphics_type_tag & ~GS_DEVICE_ENCODES_TAGS);
    } else {
        dc.tag = 0;
    }

    return dev_proc(pfs->dev, fill_trapezoid)(pfs->dev,
        le, re, ybot, ytop, swap_axes, &dc, pfs->pgs->log_op);
}

static inline float
function_linearity(const patch_fill_state_t *pfs, const patch_color_t *c0, const patch_color_t *c1)
{
    float s = 0;

    if (pfs->Function != NULL) {
        patch_color_t c;
        /* Solaris 9 (Sun C 5.5) compiler cannot initialize a 'const' */
        /* unless it is 'static const' */
        static const float q[2] = {(float)0.3, (float)0.7};
        int i, j;

        for (j = 0; j < count_of(q); j++) {
            c.t[0] = c0->t[0] * (1 - q[j]) + c1->t[0] * q[j];
            c.t[1] = c0->t[1] * (1 - q[j]) + c1->t[1] * q[j];
            patch_resolve_color_inline(&c, pfs);
            for (i = 0; i < pfs->num_components; i++) {
                float v = c0->cc.paint.values[i] * (1 - q[j]) + c1->cc.paint.values[i] * q[j];
                float d = v - c.cc.paint.values[i];
                float s1 = any_abs(d) / pfs->color_domain.paint.values[i];

                if (s1 > pfs->smoothness)
                    return s1;
                if (s < s1)
                    s = s1;
            }
        }
    }
    return s;
}

static inline int
is_color_linear(const patch_fill_state_t *pfs, const patch_color_t *c0, const patch_color_t *c1)
{   /* returns : 1 = linear, 0 = unlinear, <0 = error. */
    if (pfs->unlinear)
        return 1; /* Disable this check. */
    else {
        const gs_color_space *cs = pfs->direct_space;
        int code;
        float s = function_linearity(pfs, c0, c1);

        if (s > pfs->smoothness)
            return 0;
        if (pfs->cs_always_linear)
            return 1;
        code = cs_is_linear(cs, pfs->pgs, pfs->trans_device,
                &c0->cc, &c1->cc, NULL, NULL, pfs->smoothness - s, pfs->icclink);
        if (code <= 0)
            return code;
        return 1;
    }
}

static int
decompose_linear_color(patch_fill_state_t *pfs, gs_fixed_edge *le, gs_fixed_edge *re,
        fixed ybot, fixed ytop, bool swap_axes, const patch_color_t *c0,
        const patch_color_t *c1)
{
    /* Assuming a very narrow trapezoid - ignore the transversal color variation. */
    /* Assuming the XY span is restricted with curve_samples.
       It is important for intersection_of_small_bars to compute faster. */
    int code;
    patch_color_t *c;
    byte *color_stack_ptr;
    bool save_inside = pfs->inside;

    if (!pfs->inside) {
        gs_fixed_rect r, r1;

        if(swap_axes) {
            r.p.y = min(le->start.x, le->end.x);
            r.p.x = min(le->start.y, le->end.y);
            r.q.y = max(re->start.x, re->end.x);
            r.q.x = max(re->start.y, re->end.y);
        } else {
            r.p.x = min(le->start.x, le->end.x);
            r.p.y = min(le->start.y, le->end.y);
            r.q.x = max(re->start.x, re->end.x);
            r.q.y = max(re->start.y, re->end.y);
        }
        r1 = r;
        rect_intersect(r, pfs->rect);
        if (r.q.x <= r.p.x || r.q.y <= r.p.y)
            return 0;
        if (r1.p.x == r.p.x && r1.p.y == r.p.y &&
            r1.q.x == r.q.x && r1.q.y == r.q.y)
            pfs->inside = true;
    }
    color_stack_ptr = reserve_colors_inline(pfs, &c, 1);
    if (color_stack_ptr == NULL)
        return_error(gs_error_unregistered); /* Must not happen. */
    /* Use the recursive decomposition due to isnt_color_monotonic
       based on fn_is_monotonic_proc_t is_monotonic,
       which applies to intervals. */
    patch_interpolate_color(c, c0, c1, pfs, 0.5);
    if (ytop - ybot < pfs->decomposition_limit) /* Prevent an infinite color decomposition. */
        code = constant_color_trapezoid(pfs, le, re, ybot, ytop, swap_axes, c);
    else {
        bool monotonic_color_save = pfs->monotonic_color;
        bool linear_color_save = pfs->linear_color;

        if (!pfs->monotonic_color) {
            code = isnt_color_monotonic(pfs, c0, c1);
            if (code < 0)
                goto out;
            if (!code)
                pfs->monotonic_color = true;
        }
        if (pfs->monotonic_color && !pfs->linear_color) {
            code = is_color_linear(pfs, c0, c1);
            if (code < 0)
                goto out;
            if (code > 0)
                pfs->linear_color =  true;
        }
        if (!pfs->unlinear && pfs->linear_color) {
            gx_device *pdev = pfs->dev;
            frac31 fc[2][GX_DEVICE_COLOR_MAX_COMPONENTS];
            gs_fill_attributes fa;
            gs_fixed_rect clip;

            memset(fc, 0x99, sizeof(fc));

            clip = pfs->rect;
            if (swap_axes) {
                fixed v;

                v = clip.p.x; clip.p.x = clip.p.y; clip.p.y = v;
                v = clip.q.x; clip.q.x = clip.q.y; clip.q.y = v;
                /* Don't need adjust_swapped_boundary here. */
            }
            clip.p.y = max(clip.p.y, ybot);
            clip.q.y = min(clip.q.y, ytop);
            fa.clip = &clip;
            fa.ht = NULL;
            fa.swap_axes = swap_axes;
            fa.lop = 0;
            fa.ystart = ybot;
            fa.yend = ytop;
            code = patch_color_to_device_color_inline(pfs, c0, NULL, fc[0]);
            if (code < 0)
                goto out;
            if (code == 2) {
                /* Must not happen. */
                code=gs_note_error(gs_error_unregistered);
                goto out;
            }
            code = patch_color_to_device_color_inline(pfs, c1, NULL, fc[1]);
            if (code < 0)
                goto out;
            code = dev_proc(pdev, fill_linear_color_trapezoid)(pdev, &fa,
                            &le->start, &le->end, &re->start, &re->end,
                            fc[0], fc[1], NULL, NULL);
            if (code == 1) {
                pfs->monotonic_color = monotonic_color_save;
                pfs->linear_color = linear_color_save;
                code = 0; /* The area is filled. */
                goto out;
            }
            if (code < 0)
                goto out;
            else {      /* code == 0, the device requested to decompose the area. */
                code = gs_note_error(gs_error_unregistered); /* Must not happen. */
                goto out;
            }
        }
        if (!pfs->unlinear || !pfs->linear_color ||
                color_span(pfs, c0, c1) > pfs->smoothness) {
            fixed y = (ybot + ytop) / 2;

            code = decompose_linear_color(pfs, le, re, ybot, y, swap_axes, c0, c);
            if (code >= 0)
                code = decompose_linear_color(pfs, le, re, y, ytop, swap_axes, c, c1);
        } else
            code = constant_color_trapezoid(pfs, le, re, ybot, ytop, swap_axes, c);
        pfs->monotonic_color = monotonic_color_save;
        pfs->linear_color = linear_color_save;
    }
out:
    pfs->inside = save_inside;
    release_colors_inline(pfs, color_stack_ptr, 1);
    return code;
}

static inline int
linear_color_trapezoid(patch_fill_state_t *pfs, gs_fixed_point q[4], int i0, int i1, int i2, int i3,
                fixed ybot, fixed ytop, bool swap_axes, const patch_color_t *c0, const patch_color_t *c1,
                bool orient)
{
    /* Assuming a very narrow trapezoid - ignore the transversal color change. */
    gs_fixed_edge le, re;

    make_trapezoid(q, i0, i1, i2, i3, ybot, ytop, swap_axes, orient, &le, &re);
    return decompose_linear_color(pfs, &le, &re, ybot, ytop, swap_axes, c0, c1);
}

static int
wedge_trap_decompose(patch_fill_state_t *pfs, gs_fixed_point q[4],
        fixed ybot, fixed ytop, const patch_color_t *c0, const patch_color_t *c1,
        bool swap_axes, bool self_intersecting)
{
    /* Assuming a very narrow trapezoid - ignore the transversal color change. */
    fixed dx1, dy1, dx2, dy2;
    bool orient;

    if (!pfs->vectorization && !covers_pixel_centers(ybot, ytop))
        return 0;
    if (ybot == ytop)
        return 0;
    dx1 = q[1].x - q[0].x, dy1 = q[1].y - q[0].y;
    dx2 = q[2].x - q[0].x, dy2 = q[2].y - q[0].y;
    if ((int64_t)dx1 * dy2 != (int64_t)dy1 * dx2) {
        orient = ((int64_t)dx1 * dy2 > (int64_t)dy1 * dx2);
        return linear_color_trapezoid(pfs, q, 0, 1, 2, 3, ybot, ytop, swap_axes, c0, c1, orient);
    } else {
        fixed dx3 = q[3].x - q[0].x, dy3 = q[3].y - q[0].y;

        orient = ((int64_t)dx1 * dy3 > (int64_t)dy1 * dx3);
        return linear_color_trapezoid(pfs, q, 0, 1, 2, 3, ybot, ytop, swap_axes, c0, c1, orient);
    }
}

static inline int
fill_wedge_trap(patch_fill_state_t *pfs, const gs_fixed_point *p0, const gs_fixed_point *p1,
            const gs_fixed_point *q0, const gs_fixed_point *q1, const patch_color_t *c0, const patch_color_t *c1,
            bool swap_axes, bool self_intersecting)
{
    /* We assume that the width of the wedge is close to zero,
       so we can ignore the slope when computing transversal distances. */
    gs_fixed_point p[4];
    const patch_color_t *cc0, *cc1;

    if (p0->y < p1->y) {
        p[2] = *p0;
        p[3] = *p1;
        cc0 = c0;
        cc1 = c1;
    } else {
        p[2] = *p1;
        p[3] = *p0;
        cc0 = c1;
        cc1 = c0;
    }
    p[0] = *q0;
    p[1] = *q1;
    return wedge_trap_decompose(pfs, p, p[2].y, p[3].y, cc0, cc1, swap_axes, self_intersecting);
}

static void
split_curve_s(const gs_fixed_point *pole, gs_fixed_point *q0, gs_fixed_point *q1, int pole_step)
{
    /*  This copies a code fragment from split_curve_midpoint,
        substituting another data type.
     */
    /*
     * We have to define midpoint carefully to avoid overflow.
     * (If it overflows, something really pathological is going
     * on, but we could get infinite recursion that way....)
     */
#define midpoint(a,b)\
  (arith_rshift_1(a) + arith_rshift_1(b) + (((a) | (b)) & 1))
    fixed x12 = midpoint(pole[1 * pole_step].x, pole[2 * pole_step].x);
    fixed y12 = midpoint(pole[1 * pole_step].y, pole[2 * pole_step].y);

    /* q[0] and q[1] must not be the same as pole. */
    q0[1 * pole_step].x = midpoint(pole[0 * pole_step].x, pole[1 * pole_step].x);
    q0[1 * pole_step].y = midpoint(pole[0 * pole_step].y, pole[1 * pole_step].y);
    q1[2 * pole_step].x = midpoint(pole[2 * pole_step].x, pole[3 * pole_step].x);
    q1[2 * pole_step].y = midpoint(pole[2 * pole_step].y, pole[3 * pole_step].y);
    q0[2 * pole_step].x = midpoint(q0[1 * pole_step].x, x12);
    q0[2 * pole_step].y = midpoint(q0[1 * pole_step].y, y12);
    q1[1 * pole_step].x = midpoint(x12, q1[2 * pole_step].x);
    q1[1 * pole_step].y = midpoint(y12, q1[2 * pole_step].y);
    q0[0 * pole_step].x = pole[0 * pole_step].x;
    q0[0 * pole_step].y = pole[0 * pole_step].y;
    q0[3 * pole_step].x = q1[0 * pole_step].x = midpoint(q0[2 * pole_step].x, q1[1 * pole_step].x);
    q0[3 * pole_step].y = q1[0 * pole_step].y = midpoint(q0[2 * pole_step].y, q1[1 * pole_step].y);
    q1[3 * pole_step].x = pole[3 * pole_step].x;
    q1[3 * pole_step].y = pole[3 * pole_step].y;
#undef midpoint
}

static void
split_curve(const gs_fixed_point pole[4], gs_fixed_point q0[4], gs_fixed_point q1[4])
{
    split_curve_s(pole, q0, q1, 1);
}

#ifdef SHADING_SWAP_AXES_FOR_PRECISION
static inline void
do_swap_axes(gs_fixed_point *p, int k)
{
    int i;

    for (i = 0; i < k; i++) {
        p[i].x ^= p[i].y; p[i].y ^= p[i].x; p[i].x ^= p[i].y;
    }
}

static inline fixed
span_x(const gs_fixed_point *p, int k)
{
    int i;
    fixed xmin = p[0].x, xmax = p[0].x;

    for (i = 1; i < k; i++) {
        xmin = min(xmin, p[i].x);
        xmax = max(xmax, p[i].x);
    }
    return xmax - xmin;
}

static inline fixed
span_y(const gs_fixed_point *p, int k)
{
    int i;
    fixed ymin = p[0].y, ymax = p[0].y;

    for (i = 1; i < k; i++) {
        ymin = min(ymin, p[i].y);
        ymax = max(ymax, p[i].y);
    }
    return ymax - ymin;
}
#endif

static inline fixed
manhattan_dist(const gs_fixed_point *p0, const gs_fixed_point *p1)
{
    fixed dx = any_abs(p1->x - p0->x), dy = any_abs(p1->y - p0->y);

    return max(dx, dy);
}

static inline int
create_wedge_vertex_list(patch_fill_state_t *pfs, wedge_vertex_list_t *l,
        const gs_fixed_point *p0, const gs_fixed_point *p1)
{
    if (l->end != NULL)
        return_error(gs_error_unregistered); /* Must not happen. */
    l->beg = wedge_vertex_list_elem_reserve(pfs);
    l->end = wedge_vertex_list_elem_reserve(pfs);
    if (l->beg == NULL)
        return_error(gs_error_unregistered); /* Must not happen. */
    if (l->end == NULL)
        return_error(gs_error_unregistered); /* Must not happen. */
    l->beg->prev = l->end->next = NULL;
    l->beg->next = l->end;
    l->end->prev = l->beg;
    l->beg->p = *p0;
    l->end->p = *p1;
    l->beg->level = l->end->level = 0;
    return 0;
}

static inline int
insert_wedge_vertex_list_elem(patch_fill_state_t *pfs, wedge_vertex_list_t *l,
                              const gs_fixed_point *p, wedge_vertex_list_elem_t **r)
{
    wedge_vertex_list_elem_t *e = wedge_vertex_list_elem_reserve(pfs);

    /* We have got enough free elements due to the preliminary decomposition
       of curves to LAZY_WEDGES_MAX_LEVEL, see curve_samples. */
    if (e == NULL)
        return_error(gs_error_unregistered); /* Must not happen. */
    if (l->beg->next != l->end)
        return_error(gs_error_unregistered); /* Must not happen. */
    if (l->end->prev != l->beg)
        return_error(gs_error_unregistered); /* Must not happen. */
    e->next = l->end;
    e->prev = l->beg;
    e->p = *p;
    e->level = max(l->beg->level, l->end->level) + 1;
    e->divide_count = 0;
    l->beg->next = l->end->prev = e;
    {   int sx = l->beg->p.x < l->end->p.x ? 1 : -1;
        int sy = l->beg->p.y < l->end->p.y ? 1 : -1;

        if ((p->x - l->beg->p.x) * sx < 0)
            return_error(gs_error_unregistered); /* Must not happen. */
        if ((p->y - l->beg->p.y) * sy < 0)
            return_error(gs_error_unregistered); /* Must not happen. */
        if ((l->end->p.x - p->x) * sx < 0)
            return_error(gs_error_unregistered); /* Must not happen. */
        if ((l->end->p.y - p->y) * sy < 0)
            return_error(gs_error_unregistered); /* Must not happen. */
    }
    *r = e;
    return 0;
}

static inline int
open_wedge_median(patch_fill_state_t *pfs, wedge_vertex_list_t *l,
        const gs_fixed_point *p0, const gs_fixed_point *p1, const gs_fixed_point *pm,
        wedge_vertex_list_elem_t **r)
{
    wedge_vertex_list_elem_t *e;
    int code;

    if (!l->last_side) {
        if (l->beg == NULL) {
            code = create_wedge_vertex_list(pfs, l, p0, p1);
            if (code < 0)
                return code;
        }
        if (l->beg->p.x != p0->x)
            return_error(gs_error_unregistered); /* Must not happen. */
        if (l->beg->p.y != p0->y)
            return_error(gs_error_unregistered); /* Must not happen. */
        if (l->end->p.x != p1->x)
            return_error(gs_error_unregistered); /* Must not happen. */
        if (l->end->p.y != p1->y)
            return_error(gs_error_unregistered); /* Must not happen. */
        code = insert_wedge_vertex_list_elem(pfs, l, pm, &e);
        if (code < 0)
            return code;
        e->divide_count++;
    } else if (l->beg == NULL) {
        code = create_wedge_vertex_list(pfs, l, p1, p0);
        if (code < 0)
            return code;
        code = insert_wedge_vertex_list_elem(pfs, l, pm, &e);
        if (code < 0)
            return code;
        e->divide_count++;
    } else {
        if (l->beg->p.x != p1->x)
            return_error(gs_error_unregistered); /* Must not happen. */
        if (l->beg->p.y != p1->y)
            return_error(gs_error_unregistered); /* Must not happen. */
        if (l->end->p.x != p0->x)
            return_error(gs_error_unregistered); /* Must not happen. */
        if (l->end->p.y != p0->y)
            return_error(gs_error_unregistered); /* Must not happen. */
        if (l->beg->next == l->end) {
            code = insert_wedge_vertex_list_elem(pfs, l, pm, &e);
            if (code < 0)
                return code;
            e->divide_count++;
        } else {
            e = wedge_vertex_list_find(l->beg, l->end,
                        max(l->beg->level, l->end->level) + 1);
            if (e == NULL)
                return_error(gs_error_unregistered); /* Must not happen. */
            if (e->p.x != pm->x || e->p.y != pm->y)
                return_error(gs_error_unregistered); /* Must not happen. */
            e->divide_count++;
        }
    }
    *r = e;
    return 0;
}

static inline int
make_wedge_median(patch_fill_state_t *pfs, wedge_vertex_list_t *l,
        wedge_vertex_list_t *l0, bool forth,
        const gs_fixed_point *p0, const gs_fixed_point *p1, const gs_fixed_point *pm)
{
    int code;

    l->last_side = l0->last_side;
    if (!l->last_side ^ !forth) {
        code = open_wedge_median(pfs, l0, p0, p1, pm, &l->end);
        l->beg = l0->beg;
    } else {
        code = open_wedge_median(pfs, l0, p0, p1, pm, &l->beg);
        l->end = l0->end;
    }
    return code;
}

static int fill_wedge_from_list(patch_fill_state_t *pfs, const wedge_vertex_list_t *l,
            const patch_color_t *c0, const patch_color_t *c1);

static inline int
close_wedge_median(patch_fill_state_t *pfs, wedge_vertex_list_t *l,
        const patch_color_t *c0, const patch_color_t *c1)
{
    int code;

    if (!l->last_side)
        return 0;
    code = fill_wedge_from_list(pfs, l, c1, c0);
    if (code < 0)
        return code;
    release_wedge_vertex_list_interval(pfs, l->beg, l->end);
    return 0;
}

static inline void
move_wedge(wedge_vertex_list_t *l, const wedge_vertex_list_t *l0, bool forth)
{
    if (!l->last_side ^ !forth) {
        l->beg = l->end;
        l->end = l0->end;
    } else {
        l->end = l->beg;
        l->beg = l0->beg;
    }
}

static inline int
fill_triangle_wedge_aux(patch_fill_state_t *pfs,
            const shading_vertex_t *q0, const shading_vertex_t *q1, const shading_vertex_t *q2)
{   int code;
    const gs_fixed_point *p0, *p1, *p2;
    gs_fixed_point qq0, qq1, qq2;
    fixed dx = any_abs(q0->p.x - q1->p.x), dy = any_abs(q0->p.y - q1->p.y);
    bool swap_axes;

#   if SKIP_TEST
        dbg_wedge_triangle_cnt++;
#   endif
    if (dx > dy) {
        swap_axes = true;
        qq0.x = q0->p.y;
        qq0.y = q0->p.x;
        qq1.x = q1->p.y;
        qq1.y = q1->p.x;
        qq2.x = q2->p.y;
        qq2.y = q2->p.x;
        p0 = &qq0;
        p1 = &qq1;
        p2 = &qq2;
    } else {
        swap_axes = false;
        p0 = &q0->p;
        p1 = &q1->p;
        p2 = &q2->p;
    }
    /* We decompose the thin triangle into 2 thin trapezoids.
       An optimization with decomposing into 2 triangles
       appears low useful, because the self_intersecting argument
       with inline expansion does that job perfectly. */
    if (p0->y < p1->y) {
        code = fill_wedge_trap(pfs, p0, p2, p0, p1, q0->c, q2->c, swap_axes, false);
        if (code < 0)
            return code;
        return fill_wedge_trap(pfs, p2, p1, p0, p1, q2->c, q1->c, swap_axes, false);
    } else {
        code = fill_wedge_trap(pfs, p0, p2, p1, p0, q0->c, q2->c, swap_axes, false);
        if (code < 0)
            return code;
        return fill_wedge_trap(pfs, p2, p1, p1, p0, q2->c, q1->c, swap_axes, false);
    }
}

static inline int
try_device_linear_color(patch_fill_state_t *pfs, bool wedge,
        const shading_vertex_t *p0, const shading_vertex_t *p1,
        const shading_vertex_t *p2)
{
    /*  Returns :
        <0 - error;
        0 - success;
        1 - decompose to linear color areas;
        2 - decompose to constant color areas;
     */
    int code;

    if (pfs->unlinear)
        return 2;
    if (!wedge) {
        const gs_color_space *cs = pfs->direct_space;

        if (cs != NULL) {
            float s0, s1, s2, s01, s012;

            s0 = function_linearity(pfs, p0->c, p1->c);
            if (s0 > pfs->smoothness)
                return 1;
            s1 = function_linearity(pfs, p1->c, p2->c);
            if (s1 > pfs->smoothness)
                return 1;
            s2 = function_linearity(pfs, p2->c, p0->c);
            if (s2 > pfs->smoothness)
                return 1;
            /* fixme: check an inner color ? */
            s01 = max(s0, s1);
            s012 = max(s01, s2);
            if (pfs->cs_always_linear)
                code = 1;
            else
                code = cs_is_linear(cs, pfs->pgs, pfs->trans_device,
                                  &p0->c->cc, &p1->c->cc, &p2->c->cc, NULL,
                                  pfs->smoothness - s012, pfs->icclink);
            if (code < 0)
                return code;
            if (code == 0)
                return 1;
        }
    }
    {   gx_device *pdev = pfs->dev;
        frac31 fc[3][GX_DEVICE_COLOR_MAX_COMPONENTS];
        gs_fill_attributes fa;
        gx_device_color dc[3];

        fa.clip = &pfs->rect;
        fa.ht = NULL;
        fa.swap_axes = false;
        fa.lop = 0;
        code = patch_color_to_device_color_inline(pfs, p0->c, &dc[0], fc[0]);
        if (code != 0)
            return code;
        if (!(dc[0].type == &gx_dc_type_data_pure ||
            dc[0].type == &gx_dc_type_data_devn))
            return 2;
        if (!wedge) {
            code = patch_color_to_device_color_inline(pfs, p1->c, &dc[1], fc[1]);
            if (code != 0)
                return code;
        }
        code = patch_color_to_device_color_inline(pfs, p2->c, &dc[2], fc[2]);
        if (code != 0)
            return code;
        code = dev_proc(pdev, fill_linear_color_triangle)(pdev, &fa,
                        &p0->p, &p1->p, &p2->p,
                        fc[0], (wedge ? NULL : fc[1]), fc[2]);
        if (code == 1)
            return 0; /* The area is filled. */
        if (code < 0)
            return code;
        else /* code == 0, the device requested to decompose the area. */
            return 1;
    }
}

static inline int
fill_triangle_wedge(patch_fill_state_t *pfs,
            const shading_vertex_t *q0, const shading_vertex_t *q1, const shading_vertex_t *q2)
{
    if ((int64_t)(q1->p.x - q0->p.x) * (q2->p.y - q0->p.y) ==
        (int64_t)(q1->p.y - q0->p.y) * (q2->p.x - q0->p.x))
        return 0; /* Zero area. */
    /*
        Can't apply try_device_linear_color here
        because didn't check is_color_linear.
        Maybe need a decomposition.
        Do same as for 'unlinear', and branch later.
     */
    return fill_triangle_wedge_aux(pfs, q0, q1, q2);
}

static inline int
fill_triangle_wedge_from_list(patch_fill_state_t *pfs,
    const wedge_vertex_list_elem_t *beg, const wedge_vertex_list_elem_t *end,
    const wedge_vertex_list_elem_t *mid,
    const patch_color_t *c0, const patch_color_t *c1)
{
    shading_vertex_t p[3];
    patch_color_t *c;
    byte *color_stack_ptr = reserve_colors_inline(pfs, &c, 1);
    int code;

    if (color_stack_ptr == NULL)
        return_error(gs_error_unregistered); /* Must not happen. */
    p[2].c = c;
    p[0].p = beg->p;
    p[0].c = c0;
    p[1].p = end->p;
    p[1].c = c1;
    p[2].p = mid->p;
    patch_interpolate_color(c, c0, c1, pfs, 0.5);
    code = fill_triangle_wedge(pfs, &p[0], &p[1], &p[2]);
    release_colors_inline(pfs, color_stack_ptr, 1);
    return code;
}

static int
fill_wedge_from_list_rec(patch_fill_state_t *pfs,
            wedge_vertex_list_elem_t *beg, const wedge_vertex_list_elem_t *end,
            int level, const patch_color_t *c0, const patch_color_t *c1)
{
    if (beg->next == end)
        return 0;
    else if (beg->next->next == end) {
        if (beg->next->divide_count != 1 && beg->next->divide_count != 2)
            return_error(gs_error_unregistered); /* Must not happen. */
        if (beg->next->divide_count != 1)
            return 0;
        return fill_triangle_wedge_from_list(pfs, beg, end, beg->next, c0, c1);
    } else {
        gs_fixed_point p;
        wedge_vertex_list_elem_t *e;
        patch_color_t *c;
        int code;
        byte *color_stack_ptr = reserve_colors_inline(pfs, &c, 1);

        if (color_stack_ptr == NULL)
            return_error(gs_error_unregistered); /* Must not happen. */
        p.x = (beg->p.x + end->p.x) / 2;
        p.y = (beg->p.y + end->p.y) / 2;
        e = wedge_vertex_list_find(beg, end, level + 1);
        if (e == NULL)
            return_error(gs_error_unregistered); /* Must not happen. */
        if (e->p.x != p.x || e->p.y != p.y)
            return_error(gs_error_unregistered); /* Must not happen. */
        patch_interpolate_color(c, c0, c1, pfs, 0.5);
        code = fill_wedge_from_list_rec(pfs, beg, e, level + 1, c0, c);
        if (code >= 0)
            code = fill_wedge_from_list_rec(pfs, e, end, level + 1, c, c1);
        if (code >= 0) {
            if (e->divide_count != 1 && e->divide_count != 2)
                return_error(gs_error_unregistered); /* Must not happen. */
            if (e->divide_count == 1)
                code = fill_triangle_wedge_from_list(pfs, beg, end, e, c0, c1);
        }
        release_colors_inline(pfs, color_stack_ptr, 1);
        return code;
    }
}

static int
fill_wedge_from_list(patch_fill_state_t *pfs, const wedge_vertex_list_t *l,
            const patch_color_t *c0, const patch_color_t *c1)
{
    return fill_wedge_from_list_rec(pfs, l->beg, l->end,
                    max(l->beg->level, l->end->level), c0, c1);
}

static inline int
terminate_wedge_vertex_list(patch_fill_state_t *pfs, wedge_vertex_list_t *l,
        const patch_color_t *c0, const patch_color_t *c1)
{
    if (l->beg != NULL) {
        int code = fill_wedge_from_list(pfs, l, c0, c1);

        if (code < 0)
            return code;
        return release_wedge_vertex_list(pfs, l, 1);
    }
    return 0;
}

static int
wedge_by_triangles(patch_fill_state_t *pfs, int ka,
        const gs_fixed_point pole[4], const patch_color_t *c0, const patch_color_t *c1)
{   /* Assuming ka >= 2, see fill_wedges. */
    gs_fixed_point q[2][4];
    patch_color_t *c;
    shading_vertex_t p[3];
    int code;
    byte *color_stack_ptr = reserve_colors_inline(pfs, &c, 1);

    if (color_stack_ptr == NULL)
        return_error(gs_error_unregistered); /* Must not happen. */
    p[2].c = c;
    split_curve(pole, q[0], q[1]);
    p[0].p = pole[0];
    p[0].c = c0;
    p[1].p = pole[3];
    p[1].c = c1;
    p[2].p = q[0][3];
    patch_interpolate_color(c, c0, c1, pfs, 0.5);
    code = fill_triangle_wedge(pfs, &p[0], &p[1], &p[2]);
    if (code >= 0) {
        if (ka == 2)
            goto out;
        code = wedge_by_triangles(pfs, ka / 2, q[0], c0, p[2].c);
    }
    if (code >= 0)
        code = wedge_by_triangles(pfs, ka / 2, q[1], p[2].c, c1);
out:
    release_colors_inline(pfs, color_stack_ptr, 1);
    return code;
}

int
mesh_padding(patch_fill_state_t *pfs, const gs_fixed_point *p0, const gs_fixed_point *p1,
            const patch_color_t *c0, const patch_color_t *c1)
{
    gs_fixed_point q0, q1;
    const patch_color_t *cc0, *cc1;
    fixed dx = p1->x - p0->x;
    fixed dy = p1->y - p0->y;
    bool swap_axes = (any_abs(dx) > any_abs(dy));
    gs_fixed_edge le, re;
    const fixed adjust = INTERPATCH_PADDING;

    if (swap_axes) {
        if (p0->x < p1->x) {
            q0.x = p0->y;
            q0.y = p0->x;
            q1.x = p1->y;
            q1.y = p1->x;
            cc0 = c0;
            cc1 = c1;
        } else {
            q0.x = p1->y;
            q0.y = p1->x;
            q1.x = p0->y;
            q1.y = p0->x;
            cc0 = c1;
            cc1 = c0;
        }
    } else if (p0->y < p1->y) {
        q0 = *p0;
        q1 = *p1;
        cc0 = c0;
        cc1 = c1;
    } else {
        q0 = *p1;
        q1 = *p0;
        cc0 = c1;
        cc1 = c0;
    }
    le.start.x = q0.x - adjust;
    re.start.x = q0.x + adjust;
    le.start.y = re.start.y = q0.y - adjust;
    le.end.x = q1.x - adjust;
    re.end.x = q1.x + adjust;
    le.end.y = re.end.y = q1.y + adjust;
    adjust_swapped_boundary(&re.start.x, swap_axes);
    adjust_swapped_boundary(&re.end.x, swap_axes);
    return decompose_linear_color(pfs, &le, &re, le.start.y, le.end.y, swap_axes, cc0, cc1);
    /* fixme : for a better performance and quality, we would like to
       consider the bar as an oriented one and to know at what side of it the spot resides.
       If we know that, we could expand only to outside the spot.
       Note that if the boundary has a self-intersection,
       we still need to expand to both directions.
     */
}

static inline void
bbox_of_points(gs_fixed_rect *r,
        const gs_fixed_point *p0, const gs_fixed_point *p1,
        const gs_fixed_point *p2, const gs_fixed_point *p3)
{
    r->p.x = r->q.x = p0->x;
    r->p.y = r->q.y = p0->y;

    if (r->p.x > p1->x)
        r->p.x = p1->x;
    if (r->q.x < p1->x)
        r->q.x = p1->x;
    if (r->p.y > p1->y)
        r->p.y = p1->y;
    if (r->q.y < p1->y)
        r->q.y = p1->y;

    if (r->p.x > p2->x)
        r->p.x = p2->x;
    if (r->q.x < p2->x)
        r->q.x = p2->x;
    if (r->p.y > p2->y)
        r->p.y = p2->y;
    if (r->q.y < p2->y)
        r->q.y = p2->y;

    if (p3 == NULL)
        return;

    if (r->p.x > p3->x)
        r->p.x = p3->x;
    if (r->q.x < p3->x)
        r->q.x = p3->x;
    if (r->p.y > p3->y)
        r->p.y = p3->y;
    if (r->q.y < p3->y)
        r->q.y = p3->y;
}

static int
fill_wedges_aux(patch_fill_state_t *pfs, int k, int ka,
        const gs_fixed_point pole[4], const patch_color_t *c0, const patch_color_t *c1,
        int wedge_type)
{
    int code;

    if (k > 1) {
        gs_fixed_point q[2][4];
        patch_color_t *c;
        bool save_inside = pfs->inside;
        byte *color_stack_ptr;

        if (!pfs->inside) {
            gs_fixed_rect r, r1;

            bbox_of_points(&r, &pole[0], &pole[1], &pole[2], &pole[3]);
            r.p.x -= INTERPATCH_PADDING;
            r.p.y -= INTERPATCH_PADDING;
            r.q.x += INTERPATCH_PADDING;
            r.q.y += INTERPATCH_PADDING;
            r1 = r;
            rect_intersect(r, pfs->rect);
            if (r.q.x <= r.p.x || r.q.y <= r.p.y)
                return 0;
            if (r1.p.x == r.p.x && r1.p.y == r.p.y &&
                r1.q.x == r.q.x && r1.q.y == r.q.y)
                pfs->inside = true;
        }
        color_stack_ptr = reserve_colors_inline(pfs, &c, 1);
        if (color_stack_ptr == NULL)
            return_error(gs_error_unregistered); /* Must not happen. */
        patch_interpolate_color(c, c0, c1, pfs, 0.5);
        split_curve(pole, q[0], q[1]);
        code = fill_wedges_aux(pfs, k / 2, ka, q[0], c0, c, wedge_type);
        if (code >= 0)
            code = fill_wedges_aux(pfs, k / 2, ka, q[1], c, c1, wedge_type);
        release_colors_inline(pfs, color_stack_ptr, 1);
        pfs->inside = save_inside;
        return code;
    } else {
        if ((INTERPATCH_PADDING != 0) && (wedge_type & interpatch_padding)) {
            code = mesh_padding(pfs, &pole[0], &pole[3], c0, c1);
            if (code < 0)
                return code;
        }
        if (ka >= 2 && (wedge_type & inpatch_wedge))
            return wedge_by_triangles(pfs, ka, pole, c0, c1);
        return 0;
    }
}

static int
fill_wedges(patch_fill_state_t *pfs, int k0, int k1,
        const gs_fixed_point *pole, int pole_step,
        const patch_color_t *c0, const patch_color_t *c1,
        int wedge_type)
{
    /* Generate wedges between 2 variants of a curve flattening. */
    /* k0, k1 is a power of 2. */
    gs_fixed_point p[4];

    if (!(wedge_type & interpatch_padding) && k0 == k1)
        return 0; /* Wedges are zero area. */
    if (k0 > k1) { /* Swap if required, so that k0 <= k1 */
        k0 ^= k1; k1 ^= k0; k0 ^= k1;
    }
    p[0] = pole[0];
    p[1] = pole[pole_step];
    p[2] = pole[pole_step * 2];
    p[3] = pole[pole_step * 3];
    return fill_wedges_aux(pfs, k0, k1 / k0, p, c0, c1, wedge_type);
}

static inline void
make_vertices(gs_fixed_point q[4], const quadrangle_patch *p)
{
    q[0] = p->p[0][0]->p;
    q[1] = p->p[0][1]->p;
    q[2] = p->p[1][1]->p;
    q[3] = p->p[1][0]->p;
}

static inline void
wrap_vertices_by_y(gs_fixed_point q[4], const gs_fixed_point s[4])
{
    fixed y = s[0].y;
    int i = 0;

    if (y > s[1].y)
        i = 1, y = s[1].y;
    if (y > s[2].y)
        i = 2, y = s[2].y;
    if (y > s[3].y)
        i = 3, y = s[3].y;
    q[0] = s[(i + 0) % 4];
    q[1] = s[(i + 1) % 4];
    q[2] = s[(i + 2) % 4];
    q[3] = s[(i + 3) % 4];
}

static int
ordered_triangle(patch_fill_state_t *pfs, gs_fixed_edge *le, gs_fixed_edge *re, patch_color_t *c)
{
    gs_fixed_edge ue;
    int code;
    gx_device_color dc;

#   if NOFILL_TEST
        if (dbg_nofill)
            return 0;
#   endif
    code = patch_color_to_device_color_inline(pfs, c, &dc, NULL);
    if (code < 0)
        return code;
    if (le->end.y < re->end.y) {
        code = dev_proc(pfs->dev, fill_trapezoid)(pfs->dev,
            le, re, le->start.y, le->end.y, false, &dc, pfs->pgs->log_op);
        if (code >= 0) {
            ue.start = le->end;
            ue.end = re->end;
            code = dev_proc(pfs->dev, fill_trapezoid)(pfs->dev,
                &ue, re, le->end.y, re->end.y, false, &dc, pfs->pgs->log_op);
        }
    } else if (le->end.y > re->end.y) {
        code = dev_proc(pfs->dev, fill_trapezoid)(pfs->dev,
            le, re, le->start.y, re->end.y, false, &dc, pfs->pgs->log_op);
        if (code >= 0) {
            ue.start = re->end;
            ue.end = le->end;
            code = dev_proc(pfs->dev, fill_trapezoid)(pfs->dev,
                le, &ue, re->end.y, le->end.y, false, &dc, pfs->pgs->log_op);
        }
    } else
        code = dev_proc(pfs->dev, fill_trapezoid)(pfs->dev,
            le, re, le->start.y, le->end.y, false, &dc, pfs->pgs->log_op);
    return code;
}

static int
constant_color_triangle(patch_fill_state_t *pfs,
        const shading_vertex_t *p0, const shading_vertex_t *p1, const shading_vertex_t *p2)
{
    patch_color_t *c[2];
    gs_fixed_edge le, re;
    fixed dx0, dy0, dx1, dy1;
    const shading_vertex_t *pp;
    int i, code = 0;
    byte *color_stack_ptr = reserve_colors_inline(pfs, c, 2);

    if (color_stack_ptr == NULL)
        return_error(gs_error_unregistered); /* Must not happen. */
    patch_interpolate_color(c[0], p0->c, p1->c, pfs, 0.5);
    patch_interpolate_color(c[1], p2->c, c[0], pfs, 0.5);
    for (i = 0; i < 3; i++) {
        /* fixme : does optimizer compiler expand this cycle ? */
        if (p0->p.y <= p1->p.y && p0->p.y <= p2->p.y) {
            le.start = re.start = p0->p;
            le.end = p1->p;
            re.end = p2->p;

            dx0 = le.end.x - le.start.x;
            dy0 = le.end.y - le.start.y;
            dx1 = re.end.x - re.start.x;
            dy1 = re.end.y - re.start.y;
            if ((int64_t)dx0 * dy1 < (int64_t)dy0 * dx1)
                code = ordered_triangle(pfs, &le, &re, c[1]);
            else
                code = ordered_triangle(pfs, &re, &le, c[1]);
            if (code < 0)
                break;
        }
        pp = p0; p0 = p1; p1 = p2; p2 = pp;
    }
    release_colors_inline(pfs, color_stack_ptr, 2);
    return code;
}

static inline int
constant_color_quadrangle_aux(patch_fill_state_t *pfs, const quadrangle_patch *p, bool self_intersecting,
        patch_color_t *c[3])
{
    /* Assuming the XY span is restricted with curve_samples.
       It is important for intersection_of_small_bars to compute faster. */
    gs_fixed_point q[4];
    fixed ry, ey;
    int code;
    bool swap_axes = false;
    gx_device_color dc;
    bool orient;

    if (device_encodes_tags(pfs->dev)) {
        dc.tag = (pfs->dev->graphics_type_tag & ~GS_DEVICE_ENCODES_TAGS);
    } else {
        dc.tag = 0;
    }

    patch_interpolate_color(c[1], p->p[0][0]->c, p->p[0][1]->c, pfs, 0.5);
    patch_interpolate_color(c[2], p->p[1][0]->c, p->p[1][1]->c, pfs, 0.5);
    patch_interpolate_color(c[0], c[1], c[2], pfs, 0.5);
    code = patch_color_to_device_color_inline(pfs, c[0], &dc, NULL);
    if (code < 0)
        return code;
    {   gs_fixed_point qq[4];

        make_vertices(qq, p);
#ifdef SHADING_SWAP_AXES_FOR_PRECISION
             /* Swapping axes may improve the precision,
                but slows down due to the area expansion needed
                in gx_shade_trapezoid. */
            dx = span_x(qq, 4);
            dy = span_y(qq, 4);
            if (dy < dx) {
                do_swap_axes(qq, 4);
                swap_axes = true;
            }
#endif
        wrap_vertices_by_y(q, qq);
    }
    {   fixed dx1 = q[1].x - q[0].x, dy1 = q[1].y - q[0].y;
        fixed dx3 = q[3].x - q[0].x, dy3 = q[3].y - q[0].y;
        int64_t g13 = (int64_t)dx1 * dy3, h13 = (int64_t)dy1 * dx3;

        if (g13 == h13) {
            fixed dx2 = q[2].x - q[0].x, dy2 = q[2].y - q[0].y;
            int64_t g23 = (int64_t)dx2 * dy3, h23 = (int64_t)dy2 * dx3;

            if (dx1 == 0 && dy1 == 0 && g23 == h23)
                return 0;
            if (g23 != h23) {
                orient = (g23 > h23);
                if (q[2].y <= q[3].y) {
                    if ((code = gx_shade_trapezoid(pfs, q, 1, 2, 0, 3, q[1].y, q[2].y, swap_axes, &dc, orient)) < 0)
                        return code;
                    return gx_shade_trapezoid(pfs, q, 2, 3, 0, 3, q[2].y, q[3].y, swap_axes, &dc, orient);
                } else {
                    if ((code = gx_shade_trapezoid(pfs, q, 1, 2, 0, 3, q[1].y, q[3].y, swap_axes, &dc, orient)) < 0)
                        return code;
                    return gx_shade_trapezoid(pfs, q, 1, 2, 3, 2, q[3].y, q[2].y, swap_axes, &dc, orient);
                }
            } else {
                int64_t g12 = (int64_t)dx1 * dy2, h12 = (int64_t)dy1 * dx2;

                if (dx3 == 0 && dy3 == 0 && g12 == h12)
                    return 0;
                orient = (g12 > h12);
                if (q[1].y <= q[2].y) {
                    if ((code = gx_shade_trapezoid(pfs, q, 0, 1, 3, 2, q[0].y, q[1].y, swap_axes, &dc, orient)) < 0)
                        return code;
                    return gx_shade_trapezoid(pfs, q, 1, 2, 3, 2, q[1].y, q[2].y, swap_axes, &dc, orient);
                } else {
                    if ((code = gx_shade_trapezoid(pfs, q, 0, 1, 3, 2, q[0].y, q[2].y, swap_axes, &dc, orient)) < 0)
                        return code;
                    return gx_shade_trapezoid(pfs, q, 0, 1, 2, 1, q[2].y, q[1].y, swap_axes, &dc, orient);
                }
            }
        }
        orient = ((int64_t)dx1 * dy3 > (int64_t)dy1 * dx3);
    }
    if (q[1].y <= q[2].y && q[2].y <= q[3].y) {
        if (self_intersecting && intersection_of_small_bars(q, 0, 3, 1, 2, &ry, &ey)) {
            if ((code = gx_shade_trapezoid(pfs, q, 0, 1, 0, 3, q[0].y, q[1].y, swap_axes, &dc, orient)) < 0)
                return code;
            if ((code = gx_shade_trapezoid(pfs, q, 0, 3, 1, 2, q[1].y, ry + ey, swap_axes, &dc, orient)) < 0)
                return code;
            if ((code = gx_shade_trapezoid(pfs, q, 1, 2, 0, 3, ry, q[2].y, swap_axes, &dc, orient)) < 0)
                return code;
            return gx_shade_trapezoid(pfs, q, 0, 3, 2, 3, q[2].y, q[3].y, swap_axes, &dc, orient);
        } else {
            if ((code = gx_shade_trapezoid(pfs, q, 0, 1, 0, 3, q[0].y, q[1].y, swap_axes, &dc, orient)) < 0)
                return code;
            if ((code = gx_shade_trapezoid(pfs, q, 1, 2, 0, 3, q[1].y, q[2].y, swap_axes, &dc, orient)) < 0)
                return code;
            return gx_shade_trapezoid(pfs, q, 2, 3, 0, 3, q[2].y, q[3].y, swap_axes, &dc, orient);
        }
    } else if (q[1].y <= q[3].y && q[3].y <= q[2].y) {
        if (self_intersecting && intersection_of_small_bars(q, 0, 3, 1, 2, &ry, &ey)) {
            if ((code = gx_shade_trapezoid(pfs, q, 0, 1, 0, 3, q[0].y, q[1].y, swap_axes, &dc, orient)) < 0)
                return code;
            if ((code = gx_shade_trapezoid(pfs, q, 1, 2, 0, 3, q[1].y, ry + ey, swap_axes, &dc, orient)) < 0)
                return code;
            if ((code = gx_shade_trapezoid(pfs, q, 0, 3, 1, 2, ry, q[3].y, swap_axes, &dc, orient)) < 0)
                return code;
            return gx_shade_trapezoid(pfs, q, 3, 2, 1, 2, q[3].y, q[2].y, swap_axes, &dc, orient);
        } else {
            if ((code = gx_shade_trapezoid(pfs, q, 0, 1, 0, 3, q[0].y, q[1].y, swap_axes, &dc, orient)) < 0)
                return code;
            if ((code = gx_shade_trapezoid(pfs, q, 1, 2, 0, 3, q[1].y, q[3].y, swap_axes, &dc, orient)) < 0)
                return code;
            return gx_shade_trapezoid(pfs, q, 1, 2, 3, 2, q[3].y, q[2].y, swap_axes, &dc, orient);
        }
    } else if (q[2].y <= q[1].y && q[1].y <= q[3].y) {
        if (self_intersecting && intersection_of_small_bars(q, 0, 1, 2, 3, &ry, &ey)) {
            if ((code = gx_shade_trapezoid(pfs, q, 0, 1, 0, 3, q[0].y, ry + ey, swap_axes, &dc, orient)) < 0)
                return code;
            if ((code = gx_shade_trapezoid(pfs, q, 2, 1, 2, 3, q[2].y, ry + ey, swap_axes, &dc, orient)) < 0)
                return code;
            if ((code = gx_shade_trapezoid(pfs, q, 2, 1, 0, 1, ry, q[1].y, swap_axes, &dc, orient)) < 0)
                return code;
            return gx_shade_trapezoid(pfs, q, 2, 3, 0, 3, ry, q[3].y, swap_axes, &dc, orient);
        } else if (self_intersecting && intersection_of_small_bars(q, 0, 3, 1, 2, &ry, &ey)) {
            if ((code = gx_shade_trapezoid(pfs, q, 0, 1, 0, 3, q[0].y, ry + ey, swap_axes, &dc, orient)) < 0)
                return code;
            if ((code = gx_shade_trapezoid(pfs, q, 2, 1, 2, 3, q[2].y, ry + ey, swap_axes, &dc, orient)) < 0)
                return code;
            if ((code = gx_shade_trapezoid(pfs, q, 0, 1, 2, 1, ry, q[1].y, swap_axes, &dc, orient)) < 0)
                return code;
            return gx_shade_trapezoid(pfs, q, 0, 3, 2, 3, ry, q[3].y, swap_axes, &dc, orient);
        } else {
            if ((code = gx_shade_trapezoid(pfs, q, 0, 1, 0, 3, q[0].y, q[1].y, swap_axes, &dc, orient)) < 0)
                return code;
            if ((code = gx_shade_trapezoid(pfs, q, 2, 3, 2, 1, q[2].y, q[1].y, swap_axes, &dc, orient)) < 0)
                return code;
            return gx_shade_trapezoid(pfs, q, 2, 3, 0, 3, q[1].y, q[3].y, swap_axes, &dc, orient);
        }
    } else if (q[2].y <= q[3].y && q[3].y <= q[1].y) {
        if (self_intersecting && intersection_of_small_bars(q, 0, 1, 2, 3, &ry, &ey)) {
            /* Same code as someone above. */
            if ((code = gx_shade_trapezoid(pfs, q, 0, 1, 0, 3, q[0].y, ry + ey, swap_axes, &dc, orient)) < 0)
                return code;
            if ((code = gx_shade_trapezoid(pfs, q, 2, 1, 2, 3, q[2].y, ry + ey, swap_axes, &dc, orient)) < 0)
                return code;
            if ((code = gx_shade_trapezoid(pfs, q, 2, 1, 0, 1, ry, q[1].y, swap_axes, &dc, orient)) < 0)
                return code;
            return gx_shade_trapezoid(pfs, q, 2, 3, 0, 3, ry, q[3].y, swap_axes, &dc, orient);
        } else if (self_intersecting && intersection_of_small_bars(q, 0, 3, 2, 1, &ry, &ey)) {
            /* Same code as someone above. */
            if ((code = gx_shade_trapezoid(pfs, q, 0, 1, 0, 3, q[0].y, ry + ey, swap_axes, &dc, orient)) < 0)
                return code;
            if ((code = gx_shade_trapezoid(pfs, q, 2, 1, 2, 3, q[2].y, ry + ey, swap_axes, &dc, orient)) < 0)
                return code;
            if ((code = gx_shade_trapezoid(pfs, q, 0, 1, 2, 1, ry, q[1].y, swap_axes, &dc, orient)) < 0)
                return code;
            return gx_shade_trapezoid(pfs, q, 0, 3, 2, 3, ry, q[3].y, swap_axes, &dc, orient);
        } else {
            if ((code = gx_shade_trapezoid(pfs, q, 0, 1, 0, 3, q[0].y, q[2].y, swap_axes, &dc, orient)) < 0)
                return code;
            if ((code = gx_shade_trapezoid(pfs, q, 2, 3, 0, 3, q[2].y, q[3].y, swap_axes, &dc, orient)) < 0)
                return code;
            return gx_shade_trapezoid(pfs, q, 0, 1, 2, 1, q[2].y, q[1].y, swap_axes, &dc, orient);
        }
    } else if (q[3].y <= q[1].y && q[1].y <= q[2].y) {
        if (self_intersecting && intersection_of_small_bars(q, 0, 1, 3, 2, &ry, &ey)) {
            if ((code = gx_shade_trapezoid(pfs, q, 0, 1, 0, 3, q[0].y, q[3].y, swap_axes, &dc, orient)) < 0)
                return code;
            if ((code = gx_shade_trapezoid(pfs, q, 0, 1, 3, 2, q[3].y, ry + ey, swap_axes, &dc, orient)) < 0)
                return code;
            if ((code = gx_shade_trapezoid(pfs, q, 3, 2, 0, 1, ry, q[1].y, swap_axes, &dc, orient)) < 0)
                return code;
            return gx_shade_trapezoid(pfs, q, 3, 2, 1, 2, q[1].y, q[2].y, swap_axes, &dc, orient);
        } else {
            if ((code = gx_shade_trapezoid(pfs, q, 0, 1, 0, 3, q[0].y, q[3].y, swap_axes, &dc, orient)) < 0)
                return code;
            if ((code = gx_shade_trapezoid(pfs, q, 0, 1, 3, 2, q[3].y, q[1].y, swap_axes, &dc, orient)) < 0)
                return code;
            return gx_shade_trapezoid(pfs, q, 1, 2, 3, 2, q[1].y, q[2].y, swap_axes, &dc, orient);
        }
    } else if (q[3].y <= q[2].y && q[2].y <= q[1].y) {
        if (self_intersecting && intersection_of_small_bars(q, 0, 1, 2, 3, &ry, &ey)) {
            if ((code = gx_shade_trapezoid(pfs, q, 0, 1, 0, 3, q[0].y, q[3].y, swap_axes, &dc, orient)) < 0)
                return code;
            if ((code = gx_shade_trapezoid(pfs, q, 0, 1, 3, 2, q[3].y, ry + ey, swap_axes, &dc, orient)) < 0)
                return code;
            if ((code = gx_shade_trapezoid(pfs, q, 3, 2, 0, 1, ry, q[2].y, swap_axes, &dc, orient)) < 0)
                return code;
            return gx_shade_trapezoid(pfs, q, 2, 1, 0, 1, q[2].y, q[1].y, swap_axes, &dc, orient);
        } else {
            if ((code = gx_shade_trapezoid(pfs, q, 0, 1, 0, 3, q[0].y, q[3].y, swap_axes, &dc, orient)) < 0)
                return code;
            if ((code = gx_shade_trapezoid(pfs, q, 0, 1, 3, 2, q[3].y, q[2].y, swap_axes, &dc, orient)) < 0)
                return code;
            return gx_shade_trapezoid(pfs, q, 0, 1, 2, 1, q[2].y, q[1].y, swap_axes, &dc, orient);
        }
    } else {
        /* Impossible. */
        return_error(gs_error_unregistered);
    }
}

int
constant_color_quadrangle(patch_fill_state_t *pfs, const quadrangle_patch *p, bool self_intersecting)
{
    patch_color_t *c[3];
    byte *color_stack_ptr = reserve_colors_inline(pfs, c, 3);
    int code;

    if (color_stack_ptr == NULL)
        return_error(gs_error_unregistered); /* Must not happen. */
    code = constant_color_quadrangle_aux(pfs, p, self_intersecting, c);
    release_colors_inline(pfs, color_stack_ptr, 3);
    return code;
}

static inline void
divide_quadrangle_by_v(patch_fill_state_t *pfs, quadrangle_patch *s0, quadrangle_patch *s1,
            shading_vertex_t q[2], const quadrangle_patch *p, patch_color_t *c[2])
{
    q[0].c = c[0];
    q[1].c = c[1];
    q[0].p.x = (p->p[0][0]->p.x + p->p[1][0]->p.x) / 2;
    q[1].p.x = (p->p[0][1]->p.x + p->p[1][1]->p.x) / 2;
    q[0].p.y = (p->p[0][0]->p.y + p->p[1][0]->p.y) / 2;
    q[1].p.y = (p->p[0][1]->p.y + p->p[1][1]->p.y) / 2;
    patch_interpolate_color(c[0], p->p[0][0]->c, p->p[1][0]->c, pfs, 0.5);
    patch_interpolate_color(c[1], p->p[0][1]->c, p->p[1][1]->c, pfs, 0.5);
    s0->p[0][0] = p->p[0][0];
    s0->p[0][1] = p->p[0][1];
    s0->p[1][0] = s1->p[0][0] = &q[0];
    s0->p[1][1] = s1->p[0][1] = &q[1];
    s1->p[1][0] = p->p[1][0];
    s1->p[1][1] = p->p[1][1];
}

static inline void
divide_quadrangle_by_u(patch_fill_state_t *pfs, quadrangle_patch *s0, quadrangle_patch *s1,
            shading_vertex_t q[2], const quadrangle_patch *p, patch_color_t *c[2])
{
    q[0].c = c[0];
    q[1].c = c[1];
    q[0].p.x = (p->p[0][0]->p.x + p->p[0][1]->p.x) / 2;
    q[1].p.x = (p->p[1][0]->p.x + p->p[1][1]->p.x) / 2;
    q[0].p.y = (p->p[0][0]->p.y + p->p[0][1]->p.y) / 2;
    q[1].p.y = (p->p[1][0]->p.y + p->p[1][1]->p.y) / 2;
    patch_interpolate_color(c[0], p->p[0][0]->c, p->p[0][1]->c, pfs, 0.5);
    patch_interpolate_color(c[1], p->p[1][0]->c, p->p[1][1]->c, pfs, 0.5);
    s0->p[0][0] = p->p[0][0];
    s0->p[1][0] = p->p[1][0];
    s0->p[0][1] = s1->p[0][0] = &q[0];
    s0->p[1][1] = s1->p[1][0] = &q[1];
    s1->p[0][1] = p->p[0][1];
    s1->p[1][1] = p->p[1][1];
}

static inline int
is_quadrangle_color_monotonic(const patch_fill_state_t *pfs, const quadrangle_patch *p,
                              bool *not_monotonic_by_u, bool *not_monotonic_by_v)
{   /* returns : 1 = monotonic, 0 = don't know, <0 = error. */
    int code, r;

    code = isnt_color_monotonic(pfs, p->p[0][0]->c, p->p[1][1]->c);
    if (code <= 0)
        return code;
    r = code << pfs->function_arg_shift;
    if (r & 1)
        *not_monotonic_by_u = true;
    if (r & 2)
        *not_monotonic_by_v = true;
    return !code;
}

static inline void
divide_bar(patch_fill_state_t *pfs,
        const shading_vertex_t *p0, const shading_vertex_t *p1, int radix, shading_vertex_t *p,
        patch_color_t *c)
{
    /* Assuming p.c == c for providing a non-const access. */
    p->p.x = (fixed)((int64_t)p0->p.x * (radix - 1) + p1->p.x) / radix;
    p->p.y = (fixed)((int64_t)p0->p.y * (radix - 1) + p1->p.y) / radix;
    patch_interpolate_color(c, p0->c, p1->c, pfs, (double)(radix - 1) / radix);
}

static int
triangle_by_4(patch_fill_state_t *pfs,
        const shading_vertex_t *p0, const shading_vertex_t *p1, const shading_vertex_t *p2,
        wedge_vertex_list_t *l01, wedge_vertex_list_t *l12, wedge_vertex_list_t *l20,
        double cd, fixed sd)
{
    shading_vertex_t p01, p12, p20;
    patch_color_t *c[3];
    wedge_vertex_list_t L01, L12, L20, L[3];
    bool inside_save = pfs->inside;
    gs_fixed_rect r = {{0,0},{0,0}}, r1 =  {{0,0},{0,0}};
    int code = 0;
    byte *color_stack_ptr;
    const bool inside = pfs->inside; /* 'const' should help compiler to analyze initializations. */

    if (!inside) {
        bbox_of_points(&r, &p0->p, &p1->p, &p2->p, NULL);
        r1 = r;
        rect_intersect(r, pfs->rect);
        if (r.q.x <= r.p.x || r.q.y <= r.p.y)
            return 0;
    }
    color_stack_ptr = reserve_colors_inline(pfs, c, 3);
    if(color_stack_ptr == NULL)
        return_error(gs_error_unregistered);
    p01.c = c[0];
    p12.c = c[1];
    p20.c = c[2];
    code = try_device_linear_color(pfs, false, p0, p1, p2);
    switch(code) {
        case 0: /* The area is filled. */
            goto out;
        case 2: /* decompose to constant color areas */
            /* Halftoned devices may do with some bigger areas
               due to imprecise representation of a contone color.
               So we multiply the decomposition limit by 4 for a faster rendering. */
            if (sd < pfs->decomposition_limit * 4) {
                code = constant_color_triangle(pfs, p2, p0, p1);
                goto out;
            }
            if (pfs->Function != NULL) {
                double d01 = color_span(pfs, p1->c, p0->c);
                double d12 = color_span(pfs, p2->c, p1->c);
                double d20 = color_span(pfs, p0->c, p2->c);

                if (d01 <= pfs->smoothness / COLOR_CONTIGUITY &&
                    d12 <= pfs->smoothness / COLOR_CONTIGUITY &&
                    d20 <= pfs->smoothness / COLOR_CONTIGUITY) {
                    code = constant_color_triangle(pfs, p2, p0, p1);
                    goto out;
                }
            } else if (cd <= pfs->smoothness / COLOR_CONTIGUITY) {
                code = constant_color_triangle(pfs, p2, p0, p1);
                goto out;
            }
            break;
        case 1: /* decompose to linear color areas */
            if (sd < pfs->decomposition_limit) {
                code = constant_color_triangle(pfs, p2, p0, p1);
                goto out;
            }
            break;
        default: /* Error. */
            goto out;
    }
    if (!inside) {
        if (r.p.x == r1.p.x && r.p.y == r1.p.y &&
            r.q.x == r1.q.x && r.q.y == r1.q.y)
            pfs->inside = true;
    }
    divide_bar(pfs, p0, p1, 2, &p01, c[0]);
    divide_bar(pfs, p1, p2, 2, &p12, c[1]);
    divide_bar(pfs, p2, p0, 2, &p20, c[2]);
    if (LAZY_WEDGES) {
        init_wedge_vertex_list(L, count_of(L));
        code = make_wedge_median(pfs, &L01, l01, true,  &p0->p, &p1->p, &p01.p);
        if (code >= 0)
            code = make_wedge_median(pfs, &L12, l12, true,  &p1->p, &p2->p, &p12.p);
        if (code >= 0)
            code = make_wedge_median(pfs, &L20, l20, false, &p2->p, &p0->p, &p20.p);
    } else {
        code = fill_triangle_wedge(pfs, p0, p1, &p01);
        if (code >= 0)
            code = fill_triangle_wedge(pfs, p1, p2, &p12);
        if (code >= 0)
            code = fill_triangle_wedge(pfs, p2, p0, &p20);
    }
    if (code >= 0)
        code = triangle_by_4(pfs, p0, &p01, &p20, &L01, &L[0], &L20, cd / 2, sd / 2);
    if (code >= 0) {
        if (LAZY_WEDGES) {
            move_wedge(&L01, l01, true);
            move_wedge(&L20, l20, false);
        }
        code = triangle_by_4(pfs, p1, &p12, &p01, &L12, &L[1], &L01, cd / 2, sd / 2);
    }
    if (code >= 0) {
        if (LAZY_WEDGES)
            move_wedge(&L12, l12, true);
        code = triangle_by_4(pfs, p2, &p20, &p12, &L20, &L[2], &L12, cd / 2, sd / 2);
    }
    if (code >= 0) {
        L[0].last_side = L[1].last_side = L[2].last_side = true;
        code = triangle_by_4(pfs, &p01, &p12, &p20, &L[1], &L[2], &L[0], cd / 2, sd / 2);
    }
    if (LAZY_WEDGES) {
        if (code >= 0)
            code = close_wedge_median(pfs, l01, p0->c, p1->c);
        if (code >= 0)
            code = close_wedge_median(pfs, l12, p1->c, p2->c);
        if (code >= 0)
            code = close_wedge_median(pfs, l20, p2->c, p0->c);
        if (code >= 0)
            code = terminate_wedge_vertex_list(pfs, &L[0], p01.c, p20.c);
        if (code >= 0)
            code = terminate_wedge_vertex_list(pfs, &L[1], p12.c, p01.c);
        if (code >= 0)
            code = terminate_wedge_vertex_list(pfs, &L[2], p20.c, p12.c);
    }
    pfs->inside = inside_save;
out:
    release_colors_inline(pfs, color_stack_ptr, 3);
    return code;
}

static inline int
fill_triangle(patch_fill_state_t *pfs,
        const shading_vertex_t *p0, const shading_vertex_t *p1, const shading_vertex_t *p2,
        wedge_vertex_list_t *l01, wedge_vertex_list_t *l12, wedge_vertex_list_t *l20)
{
    fixed sd01 = max(any_abs(p1->p.x - p0->p.x), any_abs(p1->p.y - p0->p.y));
    fixed sd12 = max(any_abs(p2->p.x - p1->p.x), any_abs(p2->p.y - p1->p.y));
    fixed sd20 = max(any_abs(p0->p.x - p2->p.x), any_abs(p0->p.y - p2->p.y));
    fixed sd1 = max(sd01, sd12);
    fixed sd = max(sd1, sd20);
    double cd = 0;

#   if SKIP_TEST
        dbg_triangle_cnt++;
#   endif
    if (pfs->Function == NULL) {
        double d01 = color_span(pfs, p1->c, p0->c);
        double d12 = color_span(pfs, p2->c, p1->c);
        double d20 = color_span(pfs, p0->c, p2->c);
        double cd1 = max(d01, d12);

        cd = max(cd1, d20);
    }
    return triangle_by_4(pfs, p0, p1, p2, l01, l12, l20, cd, sd);
}

static int
small_mesh_triangle(patch_fill_state_t *pfs,
        const shading_vertex_t *p0, const shading_vertex_t *p1, const shading_vertex_t *p2)
{
    int code;
    wedge_vertex_list_t l[3];

    init_wedge_vertex_list(l, count_of(l));
    code = fill_triangle(pfs, p0, p1, p2, &l[0], &l[1], &l[2]);
    if (code < 0)
        return code;
    code = terminate_wedge_vertex_list(pfs, &l[0], p0->c, p1->c);
    if (code < 0)
        return code;
    code = terminate_wedge_vertex_list(pfs, &l[1], p1->c, p2->c);
    if (code < 0)
        return code;
    return terminate_wedge_vertex_list(pfs, &l[2], p2->c, p0->c);
}

int
gx_init_patch_fill_state_for_clist(gx_device *dev, patch_fill_state_t *pfs, gs_memory_t *memory)
{
    int i;

    pfs->dev = dev;
    pfs->pgs = NULL;
    pfs->direct_space = NULL;
    pfs->num_components = dev->color_info.num_components;
    /* pfs->cc_max_error[GS_CLIENT_COLOR_MAX_COMPONENTS] unused */
    pfs->pshm = NULL;
    pfs->Function = NULL;
    pfs->function_arg_shift = 0;
    pfs->vectorization = false; /* A stub for a while. Will use with pclwrite. */
    pfs->n_color_args = 1; /* unused. */
    pfs->max_small_coord = 0; /* unused. */
    pfs->wedge_vertex_list_elem_buffer = NULL; /* fixme */
    pfs->free_wedge_vertex = NULL; /* fixme */
    pfs->wedge_vertex_list_elem_count = 0; /* fixme */
    pfs->wedge_vertex_list_elem_count_max = 0; /* fixme */
    for (i = 0; i < pfs->num_components; i++)
        pfs->color_domain.paint.values[i] = (float)0x7fffffff;
    /* decomposition_limit must be same as one in init_patch_fill_state */
#ifdef MAX_SHADING_RESOLUTION
    pfs->decomposition_limit = float2fixed(min(pfs->dev->HWResolution[0],
                                               pfs->dev->HWResolution[1]) / MAX_SHADING_RESOLUTION);
    pfs->decomposition_limit = max(pfs->decomposition_limit, fixed_1);
#else
    pfs->decomposition_limit = fixed_1;
#endif
    pfs->fixed_flat = 0; /* unused */
    pfs->smoothness = 0; /* unused */
    pfs->maybe_self_intersecting = false; /* unused */
    pfs->monotonic_color = true;
    pfs->linear_color = true;
    pfs->unlinear = false; /* Because it is used when fill_linear_color_triangle was called. */
    pfs->inside = false;
    pfs->color_stack_size = 0;
    pfs->color_stack_step = dev->color_info.num_components;
    pfs->color_stack_ptr = NULL; /* fixme */
    pfs->color_stack = NULL; /* fixme */
    pfs->color_stack_limit = NULL; /* fixme */
    pfs->pcic = NULL; /* Will do someday. */
    pfs->trans_device = NULL;
    pfs->icclink = NULL;
    return alloc_patch_fill_memory(pfs, memory, NULL);
}

/* A method for filling a small triangle that the device can't handle.
   Used by clist playback. */
int
gx_fill_triangle_small(gx_device *dev, const gs_fill_attributes *fa,
        const gs_fixed_point *p0, const gs_fixed_point *p1,
        const gs_fixed_point *p2,
        const frac31 *c0, const frac31 *c1, const frac31 *c2)
{
    patch_fill_state_t *pfs = fa->pfs;
    patch_color_t c[3];
    shading_vertex_t p[3];
    uchar i;

    /* pfs->rect = *fa->clip; unused ? */
    p[0].p = *p0;
    p[1].p = *p1;
    p[2].p = *p2;
    p[0].c = &c[0];
    p[1].c = &c[1];
    p[2].c = &c[2];
    c[0].t[0] = c[0].t[1] = c[1].t[0] = c[1].t[1] = c[2].t[0] = c[2].t[1] = 0; /* Dummy - not used. */
    for (i = 0; i < dev->color_info.num_components; i++) {
        c[0].cc.paint.values[i] = (float)c0[i];
        c[1].cc.paint.values[i] = (float)c1[i];
        c[2].cc.paint.values[i] = (float)c2[i];
    }
    /* fixme: the cycle above converts frac31 values into floats.
       We don't like this because (1) it misses lower bits,
       and (2) fixed point values can be faster on some platforms.
       We could fix it with coding a template for small_mesh_triangle
       and its callees until patch_color_to_device_color_inline.
    */
    /* fixme : this function is called from gxclrast.c
       after dev->procs.fill_linear_color_triangle returns 0 - "subdivide".
       After few moments small_mesh_triangle indirectly calls
       same function with same arguments as a part of
       try_device_linear_color in triangle_by_4.
       Obviusly it will return zero again.
       Actually we don't need the second call,
       so optimize with skipping the second call.
     */
    return small_mesh_triangle(pfs, &p[0], &p[1], &p[2]);
}

static int
mesh_triangle_rec(patch_fill_state_t *pfs,
        const shading_vertex_t *p0, const shading_vertex_t *p1, const shading_vertex_t *p2)
{
    pfs->unlinear = !is_linear_color_applicable(pfs);
    if (manhattan_dist(&p0->p, &p1->p) < pfs->max_small_coord &&
        manhattan_dist(&p1->p, &p2->p) < pfs->max_small_coord &&
        manhattan_dist(&p2->p, &p0->p) < pfs->max_small_coord)
        return small_mesh_triangle(pfs, p0, p1, p2);
    else {
        /* Subdivide into 4 triangles with 3 triangle non-lazy wedges.
           Doing so against the wedge_vertex_list_elem_buffer overflow.
           We could apply a smarter method, dividing long sides
           with no wedges and short sides with lazy wedges.
           This needs to start wedges dynamically when
           a side becomes short. We don't do so because the
           number of checks per call significantly increases
           and the logics is complicated, but the performance
           advantage appears small due to big meshes are rare.
         */
        shading_vertex_t p01, p12, p20;
        patch_color_t *c[3];
        int code;
        byte *color_stack_ptr = reserve_colors_inline(pfs, c, 3);

        if (color_stack_ptr == NULL)
            return_error(gs_error_unregistered); /* Must not happen. */
        p01.c = c[0];
        p12.c = c[1];
        p20.c = c[2];
        divide_bar(pfs, p0, p1, 2, &p01, c[0]);
        divide_bar(pfs, p1, p2, 2, &p12, c[1]);
        divide_bar(pfs, p2, p0, 2, &p20, c[2]);
        code = fill_triangle_wedge(pfs, p0, p1, &p01);
        if (code >= 0)
            code = fill_triangle_wedge(pfs, p1, p2, &p12);
        if (code >= 0)
            code = fill_triangle_wedge(pfs, p2, p0, &p20);
        if (code >= 0)
            code = mesh_triangle_rec(pfs, p0, &p01, &p20);
        if (code >= 0)
            code = mesh_triangle_rec(pfs, p1, &p12, &p01);
        if (code >= 0)
            code = mesh_triangle_rec(pfs, p2, &p20, &p12);
        if (code >= 0)
            code = mesh_triangle_rec(pfs, &p01, &p12, &p20);
        release_colors_inline(pfs, color_stack_ptr, 3);
        return code;
    }
}

int
mesh_triangle(patch_fill_state_t *pfs,
        const shading_vertex_t *p0, const shading_vertex_t *p1, const shading_vertex_t *p2)
{
    if ((*dev_proc(pfs->dev, dev_spec_op))(pfs->dev,
            gxdso_pattern_shading_area, NULL, 0) > 0) {
        /* Inform the device with the shading coverage area.
           First compute the sign of the area, because
           all areas to be clipped in same direction. */
        gx_device *pdev = pfs->dev;
        gx_path path;
        int code;
        fixed d01x = p1->p.x - p0->p.x, d01y = p1->p.y - p0->p.y;
        fixed d12x = p2->p.x - p1->p.x, d12y = p2->p.y - p1->p.y;
        int64_t s1 = (int64_t)d01x * d12y - (int64_t)d01y * d12x;

        gx_path_init_local(&path, pdev->memory);
        code = gx_path_add_point(&path, p0->p.x, p0->p.y);
        if (code >= 0 && s1 >= 0)
            code = gx_path_add_line(&path, p1->p.x, p1->p.y);
        if (code >= 0)
            code = gx_path_add_line(&path, p2->p.x, p2->p.y);
        if (code >= 0 && s1 < 0)
            code = gx_path_add_line(&path, p1->p.x, p1->p.y);
        if (code >= 0)
            code = gx_path_close_subpath(&path);
        if (code >= 0)
            code = (*dev_proc(pfs->dev, fill_path))(pdev, NULL, &path, NULL, NULL, NULL);
        gx_path_free(&path, "mesh_triangle");
        if (code < 0)
            return code;
    }
    return mesh_triangle_rec(pfs, p0, p1, p2);
}

static inline int
triangles4(patch_fill_state_t *pfs, const quadrangle_patch *p, bool dummy_argument)
{
    shading_vertex_t p0001, p1011, q;
    patch_color_t *c[3];
    wedge_vertex_list_t l[4];
    int code;
    byte *color_stack_ptr = reserve_colors_inline(pfs, c, 3);

    if(color_stack_ptr == NULL)
        return_error(gs_error_unregistered); /* Must not happen. */
    p0001.c = c[0];
    p1011.c = c[1];
    q.c = c[2];
    init_wedge_vertex_list(l, count_of(l));
    divide_bar(pfs, p->p[0][0], p->p[0][1], 2, &p0001, c[0]);
    divide_bar(pfs, p->p[1][0], p->p[1][1], 2, &p1011, c[1]);
    divide_bar(pfs, &p0001, &p1011, 2, &q, c[2]);
    code = fill_triangle(pfs, p->p[0][0], p->p[0][1], &q, p->l0001, &l[0], &l[3]);
    if (code >= 0) {
        l[0].last_side = true;
        l[3].last_side = true;
        code = fill_triangle(pfs, p->p[0][1], p->p[1][1], &q, p->l0111, &l[1], &l[0]);
    }
    if (code >= 0) {
        l[1].last_side = true;
        code = fill_triangle(pfs, p->p[1][1], p->p[1][0], &q, p->l1110, &l[2], &l[1]);
    }
    if (code >= 0) {
        l[2].last_side = true;
        code = fill_triangle(pfs, p->p[1][0], p->p[0][0], &q, p->l1000, &l[3], &l[2]);
    }
    if (code >= 0)
        code = terminate_wedge_vertex_list(pfs, &l[0], p->p[0][1]->c, q.c);
    if (code >= 0)
        code = terminate_wedge_vertex_list(pfs, &l[1], p->p[1][1]->c, q.c);
    if (code >= 0)
        code = terminate_wedge_vertex_list(pfs, &l[2], p->p[1][0]->c, q.c);
    if (code >= 0)
        code = terminate_wedge_vertex_list(pfs, &l[3], q.c, p->p[0][0]->c);
    release_colors_inline(pfs, color_stack_ptr, 3);
    return code;
}

static inline int
triangles2(patch_fill_state_t *pfs, const quadrangle_patch *p, bool dummy_argument)
{
    wedge_vertex_list_t l;
    int code;

    init_wedge_vertex_list(&l, 1);
    code = fill_triangle(pfs, p->p[0][0], p->p[0][1], p->p[1][1], p->l0001, p->l0111, &l);
    if (code < 0)
        return code;
    l.last_side = true;
    code = fill_triangle(pfs, p->p[1][1], p->p[1][0], p->p[0][0], p->l1110, p->l1000, &l);
    if (code < 0)
        return code;
    code = terminate_wedge_vertex_list(pfs, &l, p->p[1][1]->c, p->p[0][0]->c);
    if (code < 0)
        return code;
    return 0;
}

static inline void
make_quadrangle(const tensor_patch *p, shading_vertex_t qq[2][2],
        wedge_vertex_list_t l[4], quadrangle_patch *q)
{
    qq[0][0].p = p->pole[0][0];
    qq[0][1].p = p->pole[0][3];
    qq[1][0].p = p->pole[3][0];
    qq[1][1].p = p->pole[3][3];
    qq[0][0].c = p->c[0][0];
    qq[0][1].c = p->c[0][1];
    qq[1][0].c = p->c[1][0];
    qq[1][1].c = p->c[1][1];
    q->p[0][0] = &qq[0][0];
    q->p[0][1] = &qq[0][1];
    q->p[1][0] = &qq[1][0];
    q->p[1][1] = &qq[1][1];
    q->l0001 = &l[0];
    q->l0111 = &l[1];
    q->l1110 = &l[2];
    q->l1000 = &l[3];
}

static inline int
is_quadrangle_color_linear_by_u(const patch_fill_state_t *pfs, const quadrangle_patch *p)
{   /* returns : 1 = linear, 0 = unlinear, <0 = error. */
    int code;

    code = is_color_linear(pfs, p->p[0][0]->c, p->p[0][1]->c);
    if (code <= 0)
        return code;
    return is_color_linear(pfs, p->p[1][0]->c, p->p[1][1]->c);
}

static inline int
is_quadrangle_color_linear_by_v(const patch_fill_state_t *pfs, const quadrangle_patch *p)
{   /* returns : 1 = linear, 0 = unlinear, <0 = error. */
    int code;

    code = is_color_linear(pfs, p->p[0][0]->c, p->p[1][0]->c);
    if (code <= 0)
        return code;
    return is_color_linear(pfs, p->p[0][1]->c, p->p[1][1]->c);
}

static inline int
is_quadrangle_color_linear_by_diagonals(const patch_fill_state_t *pfs, const quadrangle_patch *p)
{   /* returns : 1 = linear, 0 = unlinear, <0 = error. */
    int code;

    code = is_color_linear(pfs, p->p[0][0]->c, p->p[1][1]->c);
    if (code <= 0)
        return code;
    return is_color_linear(pfs, p->p[0][1]->c, p->p[1][0]->c);
}

typedef enum {
    color_change_small,
    color_change_gradient,
    color_change_linear,
    color_change_bilinear,
    color_change_general
} color_change_type_t;

static inline color_change_type_t
quadrangle_color_change(const patch_fill_state_t *pfs, const quadrangle_patch *p,
                        bool is_big_u, bool is_big_v, double size_u, double size_v,
                        bool *divide_u, bool *divide_v)
{
    patch_color_t d0001, d1011, d;
    double D, D0001, D1011, D0010, D0111, D0011, D0110;
    double Du, Dv;

    color_diff(pfs, p->p[0][0]->c, p->p[0][1]->c, &d0001);
    color_diff(pfs, p->p[1][0]->c, p->p[1][1]->c, &d1011);
    D0001 = color_norm(pfs, &d0001);
    D1011 = color_norm(pfs, &d1011);
    D0010 = color_span(pfs, p->p[0][0]->c, p->p[1][0]->c);
    D0111 = color_span(pfs, p->p[0][1]->c, p->p[1][1]->c);
    D0011 = color_span(pfs, p->p[0][0]->c, p->p[1][1]->c);
    D0110 = color_span(pfs, p->p[0][1]->c, p->p[1][0]->c);
    if (pfs->unlinear) {
        if (D0001 <= pfs->smoothness && D1011 <= pfs->smoothness &&
            D0010 <= pfs->smoothness && D0111 <= pfs->smoothness &&
            D0011 <= pfs->smoothness && D0110 <= pfs->smoothness)
            return color_change_small;
        if (D0001 <= pfs->smoothness && D1011 <= pfs->smoothness) {
            if (!is_big_v) {
                /* The color function looks uncontiguous. */
                return color_change_small;
            }
            *divide_v = true;
            return color_change_gradient;
        }
        if (D0010 <= pfs->smoothness && D0111 <= pfs->smoothness) {
            if (!is_big_u) {
                /* The color function looks uncontiguous. */
                return color_change_small;
            }
            *divide_u = true;
            return color_change_gradient;
        }
    }
    color_diff(pfs, &d0001, &d1011, &d);
    Du = max(D0001, D1011);
    Dv = max(D0010, D0111);
    if (Du <= pfs->smoothness / 8 && Dv <= pfs->smoothness / 8)
        return color_change_small;
    if (Du <= pfs->smoothness / 8)
        return color_change_linear;
    if (Dv <= pfs->smoothness / 8)
        return color_change_linear;
    D = color_norm(pfs, &d);
    if (D <= pfs->smoothness)
        return color_change_bilinear;
#if 1
    if (Du > Dv && is_big_u)
        *divide_u = true;
    else if (Du < Dv && is_big_v)
        *divide_v = true;
    else if (is_big_u && size_u > size_v)
        *divide_u = true;
    else if (is_big_v && size_v > size_u)
        *divide_v = true;
    else if (is_big_u)
        *divide_u = true;
    else if (is_big_v)
        *divide_v = true;
    else {
        /* The color function looks uncontiguous. */
        return color_change_small;
    }
#else /* Disabled due to infinite recursion with -r200 09-57.PS
         (Standard Test 6.4  - Range 6) (Test05). */
    if (Du > Dv)
        *divide_u = true;
    else
        *divide_v = true;
#endif
    return color_change_general;
}

static int
fill_quadrangle(patch_fill_state_t *pfs, const quadrangle_patch *p, bool big)
{
    /* The quadrangle is flattened enough by V and U, so ignore inner poles. */
    /* Assuming the XY span is restricted with curve_samples.
       It is important for intersection_of_small_bars to compute faster. */
    quadrangle_patch s0, s1;
    wedge_vertex_list_t l0, l1, l2;
    int code;
    bool divide_u = false, divide_v = false, big1 = big;
    shading_vertex_t q[2];
    bool monotonic_color_save = pfs->monotonic_color;
    bool linear_color_save = pfs->linear_color;
    bool inside_save = pfs->inside;
    const bool inside = pfs->inside; /* 'const' should help compiler to analyze initializations. */
    gs_fixed_rect r = {{0,0},{0,0}}, r1 = {{0,0},{0,0}};
    /* Warning : pfs->monotonic_color is not restored on error. */

    if (!inside) {
        bbox_of_points(&r, &p->p[0][0]->p, &p->p[0][1]->p, &p->p[1][0]->p, &p->p[1][1]->p);
        r1 = r;
        rect_intersect(r, pfs->rect);
        if (r.q.x <= r.p.x || r.q.y <= r.p.y)
            return 0; /* Outside. */
    }
    if (big) {
        /* Likely 'big' is an unuseful rudiment due to curve_samples
           restricts lengthes. We keep it for a while because its implementation
           isn't obvious and its time consumption is invisibly small.
         */
        fixed size_u = max(max(any_abs(p->p[0][0]->p.x - p->p[0][1]->p.x),
                               any_abs(p->p[1][0]->p.x - p->p[1][1]->p.x)),
                           max(any_abs(p->p[0][0]->p.y - p->p[0][1]->p.y),
                               any_abs(p->p[1][0]->p.y - p->p[1][1]->p.y)));
        fixed size_v = max(max(any_abs(p->p[0][0]->p.x - p->p[1][0]->p.x),
                               any_abs(p->p[0][1]->p.x - p->p[1][1]->p.x)),
                           max(any_abs(p->p[0][0]->p.y - p->p[1][0]->p.y),
                               any_abs(p->p[0][1]->p.y - p->p[1][1]->p.y)));

        if (QUADRANGLES && pfs->maybe_self_intersecting) {
            if (size_v > pfs->max_small_coord) {
                /* constant_color_quadrangle can't handle big self-intersecting areas
                   because we don't want int64_t in it. */
                divide_v = true;
            } else if (size_u > pfs->max_small_coord) {
                /* constant_color_quadrangle can't handle big self-intersecting areas,
                   because we don't want int64_t in it. */
                divide_u = true;
            } else
                big1 = false;
        } else
            big1 = false;
    }
    if (!big1) {
        bool is_big_u = false, is_big_v = false;
        double d0001x = any_abs(p->p[0][0]->p.x - p->p[0][1]->p.x);
        double d1011x = any_abs(p->p[1][0]->p.x - p->p[1][1]->p.x);
        double d0001y = any_abs(p->p[0][0]->p.y - p->p[0][1]->p.y);
        double d1011y = any_abs(p->p[1][0]->p.y - p->p[1][1]->p.y);
        double d0010x = any_abs(p->p[0][0]->p.x - p->p[1][0]->p.x);
        double d0111x = any_abs(p->p[0][1]->p.x - p->p[1][1]->p.x);
        double d0010y = any_abs(p->p[0][0]->p.y - p->p[1][0]->p.y);
        double d0111y = any_abs(p->p[0][1]->p.y - p->p[1][1]->p.y);
        double size_u = max(max(d0001x, d1011x), max(d0001y, d1011y));
        double size_v = max(max(d0010x, d0111x), max(d0010y, d0111y));

        if (size_u > pfs->decomposition_limit)
            is_big_u = true;
        if (size_v > pfs->decomposition_limit)
            is_big_v = true;
        else if (!is_big_u)
            return (QUADRANGLES || !pfs->maybe_self_intersecting ?
                        constant_color_quadrangle : triangles4)(pfs, p,
                            pfs->maybe_self_intersecting);
        if (!pfs->monotonic_color) {
            bool not_monotonic_by_u = false, not_monotonic_by_v = false;

            code = is_quadrangle_color_monotonic(pfs, p, &not_monotonic_by_u, &not_monotonic_by_v);
            if (code < 0)
                return code;
            if (is_big_u)
                divide_u = not_monotonic_by_u;
            if (is_big_v)
                divide_v = not_monotonic_by_v;
            if (!divide_u && !divide_v)
                pfs->monotonic_color = true;
        }
        if (pfs->monotonic_color && !pfs->linear_color) {
            if (divide_v && divide_u) {
                if (size_u > size_v)
                    divide_v = false;
                else
                    divide_u = false;
            } else if (!divide_u && !divide_v && !pfs->unlinear) {
                if (d0001x + d1011x + d0001y + d1011y > d0010x + d0111x + d0010y + d0111y) { /* fixme: use size_u, size_v */
                    code = is_quadrangle_color_linear_by_u(pfs, p);
                    if (code < 0)
                        return code;
                    divide_u = !code;
                }
                if (is_big_v) {
                    code = is_quadrangle_color_linear_by_v(pfs, p);
                    if (code < 0)
                        return code;
                    divide_v = !code;
                }
                if (is_big_u && is_big_v) {
                    code = is_quadrangle_color_linear_by_diagonals(pfs, p);
                    if (code < 0)
                        return code;
                    if (!code) {
                        if (d0001x + d1011x + d0001y + d1011y > d0010x + d0111x + d0010y + d0111y) { /* fixme: use size_u, size_v */
                            divide_u = true;
                            divide_v = false;
                        } else {
                            divide_v = true;
                            divide_u = false;
                        }
                    }
                }
            }
            if (!divide_u && !divide_v)
                pfs->linear_color = true;
        }
        if (!pfs->linear_color) {
            /* go to divide. */
        } else switch(quadrangle_color_change(pfs, p, is_big_u, is_big_v, size_u, size_v, &divide_u, &divide_v)) {
            case color_change_small:
                code = (QUADRANGLES || !pfs->maybe_self_intersecting ?
                            constant_color_quadrangle : triangles4)(pfs, p,
                                pfs->maybe_self_intersecting);
                pfs->monotonic_color = monotonic_color_save;
                pfs->linear_color = linear_color_save;
                return code;
            case color_change_bilinear:
                if (!QUADRANGLES) {
                    code = triangles4(pfs, p, true);
                    pfs->monotonic_color = monotonic_color_save;
                    pfs->linear_color = linear_color_save;
                    return code;
                }
            case color_change_linear:
                if (!QUADRANGLES) {
                    code = triangles2(pfs, p, true);
                    pfs->monotonic_color = monotonic_color_save;
                    pfs->linear_color = linear_color_save;
                    return code;
                }
            case color_change_gradient:
            case color_change_general:
                ; /* goto divide. */
        }
    }
    if (!inside) {
        if (r.p.x == r1.p.x && r.p.y == r1.p.y &&
            r.q.x == r1.q.x && r.q.y == r1.q.y)
            pfs->inside = true;
    }
    if (LAZY_WEDGES)
        init_wedge_vertex_list(&l0, 1);
    if (divide_v) {
        patch_color_t *c[2];
        byte *color_stack_ptr = reserve_colors_inline(pfs, c, 2);

        if(color_stack_ptr == NULL)
            return_error(gs_error_unregistered); /* Must not happen. */
        q[0].c = c[0];
        q[1].c = c[1];
        divide_quadrangle_by_v(pfs, &s0, &s1, q, p, c);
        if (LAZY_WEDGES) {
            code = make_wedge_median(pfs, &l1, p->l0111, true,  &p->p[0][1]->p, &p->p[1][1]->p, &s0.p[1][1]->p);
            if (code >= 0)
                code = make_wedge_median(pfs, &l2, p->l1000, false, &p->p[1][0]->p, &p->p[0][0]->p, &s0.p[1][0]->p);
            if (code >= 0) {
                s0.l1110 = s1.l0001 = &l0;
                s0.l0111 = s1.l0111 = &l1;
                s0.l1000 = s1.l1000 = &l2;
                s0.l0001 = p->l0001;
                s1.l1110 = p->l1110;
            }
        } else {
            code = fill_triangle_wedge(pfs, s0.p[0][0], s1.p[1][0], s0.p[1][0]);
            if (code >= 0)
                code = fill_triangle_wedge(pfs, s0.p[0][1], s1.p[1][1], s0.p[1][1]);
        }
        if (code >= 0)
            code = fill_quadrangle(pfs, &s0, big1);
        if (code >= 0) {
            if (LAZY_WEDGES) {
                l0.last_side = true;
                move_wedge(&l1, p->l0111, true);
                move_wedge(&l2, p->l1000, false);
            }
            code = fill_quadrangle(pfs, &s1, big1);
        }
        if (LAZY_WEDGES) {
            if (code >= 0)
                code = close_wedge_median(pfs, p->l0111, p->p[0][1]->c, p->p[1][1]->c);
            if (code >= 0)
                code = close_wedge_median(pfs, p->l1000, p->p[1][0]->c, p->p[0][0]->c);
            if (code >= 0)
                code = terminate_wedge_vertex_list(pfs, &l0, s0.p[1][0]->c, s0.p[1][1]->c);
            release_colors_inline(pfs, color_stack_ptr, 2);
        }
    } else if (divide_u) {
        patch_color_t *c[2];
        byte *color_stack_ptr = reserve_colors_inline(pfs, c, 2);

        if(color_stack_ptr == NULL)
            return_error(gs_error_unregistered); /* Must not happen. */
        q[0].c = c[0];
        q[1].c = c[1];
        divide_quadrangle_by_u(pfs, &s0, &s1, q, p, c);
        if (LAZY_WEDGES) {
            code = make_wedge_median(pfs, &l1, p->l0001, true,  &p->p[0][0]->p, &p->p[0][1]->p, &s0.p[0][1]->p);
            if (code >= 0)
                code = make_wedge_median(pfs, &l2, p->l1110, false, &p->p[1][1]->p, &p->p[1][0]->p, &s0.p[1][1]->p);
            if (code >= 0) {
                s0.l0111 = s1.l1000 = &l0;
                s0.l0001 = s1.l0001 = &l1;
                s0.l1110 = s1.l1110 = &l2;
                s0.l1000 = p->l1000;
                s1.l0111 = p->l0111;
            }
        } else {
            code = fill_triangle_wedge(pfs, s0.p[0][0], s1.p[0][1], s0.p[0][1]);
            if (code >= 0)
                code = fill_triangle_wedge(pfs, s0.p[1][0], s1.p[1][1], s0.p[1][1]);
        }
        if (code >= 0)
            code = fill_quadrangle(pfs, &s0, big1);
        if (code >= 0) {
            if (LAZY_WEDGES) {
                l0.last_side = true;
                move_wedge(&l1, p->l0001, true);
                move_wedge(&l2, p->l1110, false);
            }
            code = fill_quadrangle(pfs, &s1, big1);
        }
        if (LAZY_WEDGES) {
            if (code >= 0)
                code = close_wedge_median(pfs, p->l0001, p->p[0][0]->c, p->p[0][1]->c);
            if (code >= 0)
                code = close_wedge_median(pfs, p->l1110, p->p[1][1]->c, p->p[1][0]->c);
            if (code >= 0)
                code = terminate_wedge_vertex_list(pfs, &l0, s0.p[0][1]->c, s0.p[1][1]->c);
            release_colors_inline(pfs, color_stack_ptr, 2);
        }
    } else
        code = (QUADRANGLES || !pfs->maybe_self_intersecting ?
                    constant_color_quadrangle : triangles4)(pfs, p,
                        pfs->maybe_self_intersecting);
    pfs->monotonic_color = monotonic_color_save;
    pfs->linear_color = linear_color_save;
    pfs->inside = inside_save;
    return code;
}

/* This splits tensor patch p->pole[v][u] on u to give s0->pole[v][u] and s1->pole[v][u] */
static inline void
split_stripe(patch_fill_state_t *pfs, tensor_patch *s0, tensor_patch *s1, const tensor_patch *p, patch_color_t *c[2])
{
    s0->c[0][1] = c[0];
    s0->c[1][1] = c[1];
    split_curve_s(p->pole[0], s0->pole[0], s1->pole[0], 1);
    split_curve_s(p->pole[1], s0->pole[1], s1->pole[1], 1);
    split_curve_s(p->pole[2], s0->pole[2], s1->pole[2], 1);
    split_curve_s(p->pole[3], s0->pole[3], s1->pole[3], 1);
    s0->c[0][0] = p->c[0][0];
    s0->c[1][0] = p->c[1][0];
    s1->c[0][0] = s0->c[0][1];
    s1->c[1][0] = s0->c[1][1];
    patch_interpolate_color(s0->c[0][1], p->c[0][0], p->c[0][1], pfs, 0.5);
    patch_interpolate_color(s0->c[1][1], p->c[1][0], p->c[1][1], pfs, 0.5);
    s1->c[0][1] = p->c[0][1];
    s1->c[1][1] = p->c[1][1];
}

/* This splits tensor patch p->pole[v][u] on v to give s0->pole[v][u] and s1->pole[v][u] */
static inline void
split_patch(patch_fill_state_t *pfs, tensor_patch *s0, tensor_patch *s1, const tensor_patch *p, patch_color_t *c[2])
{
    s0->c[1][0] = c[0];
    s0->c[1][1] = c[1];
    split_curve_s(&p->pole[0][0], &s0->pole[0][0], &s1->pole[0][0], 4);
    split_curve_s(&p->pole[0][1], &s0->pole[0][1], &s1->pole[0][1], 4);
    split_curve_s(&p->pole[0][2], &s0->pole[0][2], &s1->pole[0][2], 4);
    split_curve_s(&p->pole[0][3], &s0->pole[0][3], &s1->pole[0][3], 4);
    s0->c[0][0] = p->c[0][0];
    s0->c[0][1] = p->c[0][1];
    s1->c[0][0] = s0->c[1][0];
    s1->c[0][1] = s0->c[1][1];
    patch_interpolate_color(s0->c[1][0], p->c[0][0], p->c[1][0], pfs, 0.5);
    patch_interpolate_color(s0->c[1][1], p->c[0][1], p->c[1][1], pfs, 0.5);
    s1->c[1][0] = p->c[1][0];
    s1->c[1][1] = p->c[1][1];
}

static inline void
tensor_patch_bbox(gs_fixed_rect *r, const tensor_patch *p)
{
    int i, j;

    r->p.x = r->q.x = p->pole[0][0].x;
    r->p.y = r->q.y = p->pole[0][0].y;
    for (i = 0; i < 4; i++) {
        for (j = 0; j < 4; j++) {
            const gs_fixed_point *q = &p->pole[i][j];

            if (r->p.x > q->x)
                r->p.x = q->x;
            if (r->p.y > q->y)
                r->p.y = q->y;
            if (r->q.x < q->x)
                r->q.x = q->x;
            if (r->q.y < q->y)
                r->q.y = q->y;
        }
    }
}

static int
decompose_stripe(patch_fill_state_t *pfs, const tensor_patch *p, int ku)
{
    if (ku > 1) {
        tensor_patch s0, s1;
        patch_color_t *c[2];
        int code;
        byte *color_stack_ptr;
        bool save_inside = pfs->inside;

        if (!pfs->inside) {
            gs_fixed_rect r, r1;

            tensor_patch_bbox(&r, p);
            r1 = r;
            rect_intersect(r, pfs->rect);
            if (r.q.x <= r.p.x || r.q.y <= r.p.y)
                return 0;
            if (r1.p.x == r.p.x && r1.p.y == r.p.y &&
                r1.q.x == r.q.x && r1.q.y == r.q.y)
                pfs->inside = true;
        }
        color_stack_ptr = reserve_colors_inline(pfs, c, 2);
        if(color_stack_ptr == NULL)
            return_error(gs_error_unregistered); /* Must not happen. */
        split_stripe(pfs, &s0, &s1, p, c);
        code = decompose_stripe(pfs, &s0, ku / 2);
        if (code >= 0)
            code = decompose_stripe(pfs, &s1, ku / 2);
        release_colors_inline(pfs, color_stack_ptr, 2);
        pfs->inside = save_inside;
        return code;
    } else {
        quadrangle_patch q;
        shading_vertex_t qq[2][2];
        wedge_vertex_list_t l[4];
        int code;

        init_wedge_vertex_list(l, count_of(l));
        make_quadrangle(p, qq, l, &q);
#       if SKIP_TEST
            dbg_quad_cnt++;
#       endif
        code = fill_quadrangle(pfs, &q, true);
        if (code < 0)
            return code;
        if (LAZY_WEDGES) {
            code = terminate_wedge_vertex_list(pfs, &l[0], q.p[0][0]->c, q.p[0][1]->c);
            if (code < 0)
                return code;
            code = terminate_wedge_vertex_list(pfs, &l[1], q.p[0][1]->c, q.p[1][1]->c);
            if (code < 0)
                return code;
            code = terminate_wedge_vertex_list(pfs, &l[2], q.p[1][1]->c, q.p[1][0]->c);
            if (code < 0)
                return code;
            code = terminate_wedge_vertex_list(pfs, &l[3], q.p[1][0]->c, q.p[0][1]->c);
            if (code < 0)
                return code;
        }
        return code;
    }
}

static int
fill_stripe(patch_fill_state_t *pfs, const tensor_patch *p)
{
    /* The stripe is flattened enough by V, so ignore inner poles. */
    int ku[4], kum, code;

    /* We would like to apply iterations for enumerating the kum curve parts,
       but the roundinmg errors would be too complicated due to
       the dependence on the direction. Note that neigbour
       patches may use the opposite direction for same bounding curve.
       We apply the recursive dichotomy, in which
       the rounding errors do not depend on the direction. */
    ku[0] = curve_samples(pfs, p->pole[0], 1, pfs->fixed_flat);
    ku[3] = curve_samples(pfs, p->pole[3], 1, pfs->fixed_flat);
    kum = max(ku[0], ku[3]);
    code = fill_wedges(pfs, ku[0], kum, p->pole[0], 1, p->c[0][0], p->c[0][1], inpatch_wedge);
    if (code < 0)
        return code;
    if (INTERPATCH_PADDING) {
        code = mesh_padding(pfs, &p->pole[0][0], &p->pole[3][0], p->c[0][0], p->c[1][0]);
        if (code < 0)
            return code;
        code = mesh_padding(pfs, &p->pole[0][3], &p->pole[3][3], p->c[0][1], p->c[1][1]);
        if (code < 0)
            return code;
    }
    code = decompose_stripe(pfs, p, kum);
    if (code < 0)
        return code;
    return fill_wedges(pfs, ku[3], kum, p->pole[3], 1, p->c[1][0], p->c[1][1], inpatch_wedge);
}

static inline bool neqs(int *a, int b)
{   /* Unequal signs. Assuming -1, 0, 1 only. */
    if (*a * b < 0)
        return true;
    if (!*a)
        *a = b;
    return false;
}

static inline int
vector_pair_orientation(const gs_fixed_point *p0, const gs_fixed_point *p1, const gs_fixed_point *p2)
{   fixed dx1 = p1->x - p0->x, dy1 = p1->y - p0->y;
    fixed dx2 = p2->x - p0->x, dy2 = p2->y - p0->y;
    int64_t vp = (int64_t)dx1 * dy2 - (int64_t)dy1 * dx2;

    return (vp > 0 ? 1 : vp < 0 ? -1 : 0);
}

static inline bool
is_x_bended(const tensor_patch *p)
{
    int sign = vector_pair_orientation(&p->pole[0][0], &p->pole[0][1], &p->pole[1][0]);

    if (neqs(&sign, vector_pair_orientation(&p->pole[0][1], &p->pole[0][2], &p->pole[1][1])))
        return true;
    if (neqs(&sign, vector_pair_orientation(&p->pole[0][2], &p->pole[0][3], &p->pole[1][2])))
        return true;
    if (neqs(&sign, -vector_pair_orientation(&p->pole[0][3], &p->pole[0][2], &p->pole[1][3])))
        return true;

    if (neqs(&sign, vector_pair_orientation(&p->pole[1][1], &p->pole[1][2], &p->pole[2][1])))
        return true;
    if (neqs(&sign, vector_pair_orientation(&p->pole[1][1], &p->pole[1][2], &p->pole[2][1])))
        return true;
    if (neqs(&sign, vector_pair_orientation(&p->pole[1][2], &p->pole[1][3], &p->pole[2][2])))
        return true;
    if (neqs(&sign, -vector_pair_orientation(&p->pole[1][3], &p->pole[1][2], &p->pole[2][3])))
        return true;

    if (neqs(&sign, vector_pair_orientation(&p->pole[2][1], &p->pole[2][2], &p->pole[3][1])))
        return true;
    if (neqs(&sign, vector_pair_orientation(&p->pole[2][1], &p->pole[2][2], &p->pole[3][1])))
        return true;
    if (neqs(&sign, vector_pair_orientation(&p->pole[2][2], &p->pole[2][3], &p->pole[3][2])))
        return true;
    if (neqs(&sign, -vector_pair_orientation(&p->pole[2][3], &p->pole[2][2], &p->pole[3][3])))
        return true;

    if (neqs(&sign, -vector_pair_orientation(&p->pole[3][1], &p->pole[3][2], &p->pole[2][1])))
        return true;
    if (neqs(&sign, -vector_pair_orientation(&p->pole[3][1], &p->pole[3][2], &p->pole[2][1])))
        return true;
    if (neqs(&sign, -vector_pair_orientation(&p->pole[3][2], &p->pole[3][3], &p->pole[2][2])))
        return true;
    if (neqs(&sign, vector_pair_orientation(&p->pole[3][3], &p->pole[3][2], &p->pole[2][3])))
        return true;
    return false;
}

static inline bool
is_y_bended(const tensor_patch *p)
{
    int sign = vector_pair_orientation(&p->pole[0][0], &p->pole[1][0], &p->pole[0][1]);

    if (neqs(&sign, vector_pair_orientation(&p->pole[1][0], &p->pole[2][0], &p->pole[1][1])))
        return true;
    if (neqs(&sign, vector_pair_orientation(&p->pole[2][0], &p->pole[3][0], &p->pole[2][1])))
        return true;
    if (neqs(&sign, -vector_pair_orientation(&p->pole[3][0], &p->pole[2][0], &p->pole[3][1])))
        return true;

    if (neqs(&sign, vector_pair_orientation(&p->pole[1][1], &p->pole[2][1], &p->pole[1][2])))
        return true;
    if (neqs(&sign, vector_pair_orientation(&p->pole[1][1], &p->pole[2][1], &p->pole[1][2])))
        return true;
    if (neqs(&sign, vector_pair_orientation(&p->pole[2][1], &p->pole[3][1], &p->pole[2][2])))
        return true;
    if (neqs(&sign, -vector_pair_orientation(&p->pole[3][1], &p->pole[2][1], &p->pole[3][2])))
        return true;

    if (neqs(&sign, vector_pair_orientation(&p->pole[1][2], &p->pole[2][2], &p->pole[1][3])))
        return true;
    if (neqs(&sign, vector_pair_orientation(&p->pole[1][2], &p->pole[2][2], &p->pole[1][3])))
        return true;
    if (neqs(&sign, vector_pair_orientation(&p->pole[2][2], &p->pole[3][2], &p->pole[2][3])))
        return true;
    if (neqs(&sign, -vector_pair_orientation(&p->pole[3][2], &p->pole[2][2], &p->pole[3][3])))
        return true;

    if (neqs(&sign, -vector_pair_orientation(&p->pole[1][3], &p->pole[2][3], &p->pole[1][2])))
        return true;
    if (neqs(&sign, -vector_pair_orientation(&p->pole[1][3], &p->pole[2][3], &p->pole[1][2])))
        return true;
    if (neqs(&sign, -vector_pair_orientation(&p->pole[2][3], &p->pole[3][3], &p->pole[2][2])))
        return true;
    if (neqs(&sign, vector_pair_orientation(&p->pole[3][3], &p->pole[2][3], &p->pole[3][2])))
        return true;
    return false;
}

static inline bool
is_curve_x_small(const patch_fill_state_t *pfs, const gs_fixed_point *pole, int pole_step, fixed fixed_flat)
{   /* Is curve within a single pixel, or smaller than half pixel ? */
    fixed xmin0 = min(pole[0 * pole_step].x, pole[1 * pole_step].x);
    fixed xmin1 = min(pole[2 * pole_step].x, pole[3 * pole_step].x);
    fixed xmin =  min(xmin0, xmin1);
    fixed xmax0 = max(pole[0 * pole_step].x, pole[1 * pole_step].x);
    fixed xmax1 = max(pole[2 * pole_step].x, pole[3 * pole_step].x);
    fixed xmax =  max(xmax0, xmax1);

    if(xmax - xmin <= pfs->decomposition_limit)
        return true;
    return false;
}

static inline bool
is_curve_y_small(const patch_fill_state_t *pfs, const gs_fixed_point *pole, int pole_step, fixed fixed_flat)
{   /* Is curve within a single pixel, or smaller than half pixel ? */
    fixed ymin0 = min(pole[0 * pole_step].y, pole[1 * pole_step].y);
    fixed ymin1 = min(pole[2 * pole_step].y, pole[3 * pole_step].y);
    fixed ymin =  min(ymin0, ymin1);
    fixed ymax0 = max(pole[0 * pole_step].y, pole[1 * pole_step].y);
    fixed ymax1 = max(pole[2 * pole_step].y, pole[3 * pole_step].y);
    fixed ymax =  max(ymax0, ymax1);

    if (ymax - ymin <= pfs->decomposition_limit)
        return true;
    return false;
}

static inline bool
is_patch_narrow(const patch_fill_state_t *pfs, const tensor_patch *p)
{
    if (!is_curve_x_small(pfs, &p->pole[0][0], 4, pfs->fixed_flat))
        return false;
    if (!is_curve_x_small(pfs, &p->pole[0][1], 4, pfs->fixed_flat))
        return false;
    if (!is_curve_x_small(pfs, &p->pole[0][2], 4, pfs->fixed_flat))
        return false;
    if (!is_curve_x_small(pfs, &p->pole[0][3], 4, pfs->fixed_flat))
        return false;
    if (!is_curve_y_small(pfs, &p->pole[0][0], 4, pfs->fixed_flat))
        return false;
    if (!is_curve_y_small(pfs, &p->pole[0][1], 4, pfs->fixed_flat))
        return false;
    if (!is_curve_y_small(pfs, &p->pole[0][2], 4, pfs->fixed_flat))
        return false;
    if (!is_curve_y_small(pfs, &p->pole[0][3], 4, pfs->fixed_flat))
        return false;
    return true;
}

static int
fill_patch(patch_fill_state_t *pfs, const tensor_patch *p, int kv, int kv0, int kv1)
{
    if (kv <= 1) {
        if (is_patch_narrow(pfs, p))
            return fill_stripe(pfs, p);
        if (!is_x_bended(p))
            return fill_stripe(pfs, p);
    }
    {   tensor_patch s0, s1;
        patch_color_t *c[2];
        shading_vertex_t q0, q1, q2;
        int code = 0;
        byte *color_stack_ptr;
        bool save_inside = pfs->inside;

        if (!pfs->inside) {
            gs_fixed_rect r, r1;

            tensor_patch_bbox(&r, p);
            r.p.x -= INTERPATCH_PADDING;
            r.p.y -= INTERPATCH_PADDING;
            r.q.x += INTERPATCH_PADDING;
            r.q.y += INTERPATCH_PADDING;
            r1 = r;
            rect_intersect(r, pfs->rect);
            if (r.q.x <= r.p.x || r.q.y <= r.p.y)
                return 0;
            if (r1.p.x == r.p.x && r1.p.y == r.p.y &&
                r1.q.x == r.q.x && r1.q.y == r.q.y)
                pfs->inside = true;
        }
        color_stack_ptr = reserve_colors_inline(pfs, c, 2);
        if(color_stack_ptr == NULL)
            return_error(gs_error_unregistered); /* Must not happen. */
        split_patch(pfs, &s0, &s1, p, c);
        if (kv0 <= 1) {
            q0.p = s0.pole[0][0];
            q0.c = s0.c[0][0];
            q1.p = s1.pole[3][0];
            q1.c = s1.c[1][0];
            q2.p = s0.pole[3][0];
            q2.c = s0.c[1][0];
            code = fill_triangle_wedge(pfs, &q0, &q1, &q2);
        }
        if (kv1 <= 1 && code >= 0) {
            q0.p = s0.pole[0][3];
            q0.c = s0.c[0][1];
            q1.p = s1.pole[3][3];
            q1.c = s1.c[1][1];
            q2.p = s0.pole[3][3];
            q2.c = s0.c[1][1];
            code = fill_triangle_wedge(pfs, &q0, &q1, &q2);
        }
        if (code >= 0)
            code = fill_patch(pfs, &s0, kv / 2, kv0 / 2, kv1 / 2);
        if (code >= 0)
            code = fill_patch(pfs, &s1, kv / 2, kv0 / 2, kv1 / 2);
        /* fixme : To provide the precise filling order, we must
           decompose left and right wedges into pieces by intersections
           with stripes, and fill each piece with its stripe.
           A lazy wedge list would be fine for storing
           the necessary information.

           If the patch is created from a radial shading,
           the wedge color appears a constant, so the filling order
           isn't important. The order is important for other
           self-overlapping patches, but the visible effect is
           just a slight narrowing of the patch (as its lower layer appears
           visible through the upper layer near the side).
           This kind of dropout isn't harmful, because
           contacting self-overlapping patches are painted
           one after one by definition, so that a side coverage break
           appears unavoidable by definition.

           Delaying this improvement because it is low importance.
         */
        release_colors_inline(pfs, color_stack_ptr, 2);
        pfs->inside = save_inside;
        return code;
    }
}

static inline int64_t
lcp1(int64_t p0, int64_t p3)
{   /* Computing the 1st pole of a 3d order besier, which appears a line. */
    return (p0 + p0 + p3);
}
static inline int64_t
lcp2(int64_t p0, int64_t p3)
{   /* Computing the 2nd pole of a 3d order besier, which appears a line. */
    return (p0 + p3 + p3);
}

static void
patch_set_color(const patch_fill_state_t *pfs, patch_color_t *c, const float *cc)
{
    if (pfs->Function) {
        c->t[0] = cc[0];
        c->t[1] = cc[1];
    } else
        memcpy(c->cc.paint.values, cc, sizeof(c->cc.paint.values[0]) * pfs->num_components);
}

static void
make_tensor_patch(const patch_fill_state_t *pfs, tensor_patch *p, const patch_curve_t curve[4],
           const gs_fixed_point interior[4])
{
    const gs_color_space *pcs = pfs->direct_space;

    p->pole[0][0] = curve[0].vertex.p;
    p->pole[1][0] = curve[0].control[0];
    p->pole[2][0] = curve[0].control[1];
    p->pole[3][0] = curve[1].vertex.p;
    p->pole[3][1] = curve[1].control[0];
    p->pole[3][2] = curve[1].control[1];
    p->pole[3][3] = curve[2].vertex.p;
    p->pole[2][3] = curve[2].control[0];
    p->pole[1][3] = curve[2].control[1];
    p->pole[0][3] = curve[3].vertex.p;
    p->pole[0][2] = curve[3].control[0];
    p->pole[0][1] = curve[3].control[1];
    if (interior != NULL) {
        p->pole[1][1] = interior[0];
        p->pole[1][2] = interior[1];
        p->pole[2][2] = interior[2];
        p->pole[2][1] = interior[3];
    } else {
        p->pole[1][1].x = (fixed)((3*(lcp1(p->pole[0][1].x, p->pole[3][1].x) +
                                      lcp1(p->pole[1][0].x, p->pole[1][3].x)) -
                                   lcp1(lcp1(p->pole[0][0].x, p->pole[0][3].x),
                                        lcp1(p->pole[3][0].x, p->pole[3][3].x)))/9);
        p->pole[1][2].x = (fixed)((3*(lcp1(p->pole[0][2].x, p->pole[3][2].x) +
                                      lcp2(p->pole[1][0].x, p->pole[1][3].x)) -
                                   lcp1(lcp2(p->pole[0][0].x, p->pole[0][3].x),
                                        lcp2(p->pole[3][0].x, p->pole[3][3].x)))/9);
        p->pole[2][1].x = (fixed)((3*(lcp2(p->pole[0][1].x, p->pole[3][1].x) +
                                      lcp1(p->pole[2][0].x, p->pole[2][3].x)) -
                                   lcp2(lcp1(p->pole[0][0].x, p->pole[0][3].x),
                                        lcp1(p->pole[3][0].x, p->pole[3][3].x)))/9);
        p->pole[2][2].x = (fixed)((3*(lcp2(p->pole[0][2].x, p->pole[3][2].x) +
                                      lcp2(p->pole[2][0].x, p->pole[2][3].x)) -
                                   lcp2(lcp2(p->pole[0][0].x, p->pole[0][3].x),
                                        lcp2(p->pole[3][0].x, p->pole[3][3].x)))/9);

        p->pole[1][1].y = (fixed)((3*(lcp1(p->pole[0][1].y, p->pole[3][1].y) +
                                      lcp1(p->pole[1][0].y, p->pole[1][3].y)) -
                                   lcp1(lcp1(p->pole[0][0].y, p->pole[0][3].y),
                                        lcp1(p->pole[3][0].y, p->pole[3][3].y)))/9);
        p->pole[1][2].y = (fixed)((3*(lcp1(p->pole[0][2].y, p->pole[3][2].y) +
                                      lcp2(p->pole[1][0].y, p->pole[1][3].y)) -
                                   lcp1(lcp2(p->pole[0][0].y, p->pole[0][3].y),
                                        lcp2(p->pole[3][0].y, p->pole[3][3].y)))/9);
        p->pole[2][1].y = (fixed)((3*(lcp2(p->pole[0][1].y, p->pole[3][1].y) +
                                      lcp1(p->pole[2][0].y, p->pole[2][3].y)) -
                                   lcp2(lcp1(p->pole[0][0].y, p->pole[0][3].y),
                                        lcp1(p->pole[3][0].y, p->pole[3][3].y)))/9);
        p->pole[2][2].y = (fixed)((3*(lcp2(p->pole[0][2].y, p->pole[3][2].y) +
                                      lcp2(p->pole[2][0].y, p->pole[2][3].y)) -
                                   lcp2(lcp2(p->pole[0][0].y, p->pole[0][3].y),
                                        lcp2(p->pole[3][0].y, p->pole[3][3].y)))/9);
    }
    patch_set_color(pfs, p->c[0][0], curve[0].vertex.cc);
    patch_set_color(pfs, p->c[1][0], curve[1].vertex.cc);
    patch_set_color(pfs, p->c[1][1], curve[2].vertex.cc);
    patch_set_color(pfs, p->c[0][1], curve[3].vertex.cc);
    patch_resolve_color_inline(p->c[0][0], pfs);
    patch_resolve_color_inline(p->c[0][1], pfs);
    patch_resolve_color_inline(p->c[1][0], pfs);
    patch_resolve_color_inline(p->c[1][1], pfs);
    if (!pfs->Function) {
        pcs->type->restrict_color(&p->c[0][0]->cc, pcs);
        pcs->type->restrict_color(&p->c[0][1]->cc, pcs);
        pcs->type->restrict_color(&p->c[1][0]->cc, pcs);
        pcs->type->restrict_color(&p->c[1][1]->cc, pcs);
    }
}

int
gx_shade_background(gx_device *pdev, const gs_fixed_rect *rect,
        const gx_device_color *pdevc, gs_logical_operation_t log_op)
{
    gs_fixed_edge le, re;

    le.start.x = rect->p.x - INTERPATCH_PADDING;
    le.start.y = rect->p.y - INTERPATCH_PADDING;
    le.end.x = rect->p.x - INTERPATCH_PADDING;
    le.end.y = rect->q.y + INTERPATCH_PADDING;
    re.start.x = rect->q.x + INTERPATCH_PADDING;
    re.start.y = rect->p.y - INTERPATCH_PADDING;
    re.end.x = rect->q.x + INTERPATCH_PADDING;
    re.end.y = rect->q.y + INTERPATCH_PADDING;
    return dev_proc(pdev, fill_trapezoid)(pdev,
            &le, &re, le.start.y, le.end.y, false, pdevc, log_op);
}

int
patch_fill(patch_fill_state_t *pfs, const patch_curve_t curve[4],
           const gs_fixed_point interior[4],
           void (*transform) (gs_fixed_point *, const patch_curve_t[4],
                              const gs_fixed_point[4], double, double))
{
    tensor_patch p;
    patch_color_t *c[4];
    int kv[4], kvm, ku[4], kum;
    int code = 0;
    byte *color_stack_ptr = reserve_colors_inline(pfs, c, 4); /* Can't fail */

    p.c[0][0] = c[0];
    p.c[0][1] = c[1];
    p.c[1][0] = c[2];
    p.c[1][1] = c[3];
#if SKIP_TEST
    dbg_patch_cnt++;
    /*if (dbg_patch_cnt != 67 && dbg_patch_cnt != 78)
        return 0;*/
#endif
    /* We decompose the patch into tiny quadrangles,
       possibly inserting wedges between them against a dropout. */
    make_tensor_patch(pfs, &p, curve, interior);
    pfs->unlinear = !is_linear_color_applicable(pfs);
    pfs->linear_color = false;
    if ((*dev_proc(pfs->dev, dev_spec_op))(pfs->dev,
            gxdso_pattern_shading_area, NULL, 0) > 0) {
        /* Inform the device with the shading coverage area.
           First compute the sign of the area, because
           all areas to be clipped in same direction. */
        gx_device *pdev = pfs->dev;
        gx_path path;
        fixed d01x = (curve[1].vertex.p.x - curve[0].vertex.p.x) >> 1;
        fixed d01y = (curve[1].vertex.p.y - curve[0].vertex.p.y) >> 1;
        fixed d12x = (curve[2].vertex.p.x - curve[1].vertex.p.x) >> 1;
        fixed d12y = (curve[2].vertex.p.y - curve[1].vertex.p.y) >> 1;
        fixed d23x = (curve[3].vertex.p.x - curve[2].vertex.p.x) >> 1;
        fixed d23y = (curve[3].vertex.p.y - curve[2].vertex.p.y) >> 1;
        fixed d30x = (curve[0].vertex.p.x - curve[3].vertex.p.x) >> 1;
        fixed d30y = (curve[0].vertex.p.y - curve[3].vertex.p.y) >> 1;
        int64_t s1 = (int64_t)d01x * d12y - (int64_t)d01y * d12x;
        int64_t s2 = (int64_t)d23x * d30y - (int64_t)d23y * d30x;
        int s = (s1 + s2 > 0 ? 1 : 3), i, j, k, jj, l = (s == 1 ? 0 : 1);

        gx_path_init_local(&path, pdev->memory);
        if (is_x_bended(&p) || is_y_bended(&p)) {
            /* The patch possibly is self-overlapping,
               so the patch coverage may fall outside the patch outline.
               In this case we pass an empty path,
               and the device must use a bitmap mask instead clipping. */
        } else {
            code = gx_path_add_point(&path, curve[0].vertex.p.x, curve[0].vertex.p.y);
            for (i = k = 0; k < 4 && code >= 0; i = j, k++) {
                j = (i + s) % 4, jj = (s == 1 ? i : j);
                if (curve[jj].straight)
                    code = gx_path_add_line(&path, curve[j].vertex.p.x,
                                                curve[j].vertex.p.y);
                else
                    code = gx_path_add_curve(&path, curve[jj].control[l].x, curve[jj].control[l].y,
                                                    curve[jj].control[(l + 1) & 1].x, curve[jj].control[(l + 1) & 1].y,
                                                    curve[j].vertex.p.x,
                                                    curve[j].vertex.p.y);
            }
            if (code >= 0)
                code = gx_path_close_subpath(&path);
        }
        if (code >= 0)
            code = (*dev_proc(pfs->dev, fill_path))(pdev, NULL, &path, NULL, NULL, NULL);
        gx_path_free(&path, "patch_fill");
        if (code < 0)
            goto out;
    }
    /* How many subdividions of the patch in the u and v direction? */
    kv[0] = curve_samples(pfs, &p.pole[0][0], 4, pfs->fixed_flat);
    kv[1] = curve_samples(pfs, &p.pole[0][1], 4, pfs->fixed_flat);
    kv[2] = curve_samples(pfs, &p.pole[0][2], 4, pfs->fixed_flat);
    kv[3] = curve_samples(pfs, &p.pole[0][3], 4, pfs->fixed_flat);
    kvm = max(max(kv[0], kv[1]), max(kv[2], kv[3]));
    ku[0] = curve_samples(pfs, p.pole[0], 1, pfs->fixed_flat);
    ku[1] = curve_samples(pfs, p.pole[1], 1, pfs->fixed_flat);
    ku[2] = curve_samples(pfs, p.pole[2], 1, pfs->fixed_flat);
    ku[3] = curve_samples(pfs, p.pole[3], 1, pfs->fixed_flat);
    kum = max(max(ku[0], ku[1]), max(ku[2], ku[3]));
#   if NOFILL_TEST
    dbg_nofill = false;
#   endif
    code = fill_wedges(pfs, ku[0], kum, p.pole[0], 1, p.c[0][0], p.c[0][1],
        interpatch_padding | inpatch_wedge);
    if (code >= 0) {
        /* We would like to apply iterations for enumerating the kvm curve parts,
           but the roundinmg errors would be too complicated due to
           the dependence on the direction. Note that neigbour
           patches may use the opposite direction for same bounding curve.
           We apply the recursive dichotomy, in which
           the rounding errors do not depend on the direction. */
#       if NOFILL_TEST
            dbg_nofill = false;
            code = fill_patch(pfs, &p, kvm, kv[0], kv[3]);
            dbg_nofill = true;
#       endif
            code = fill_patch(pfs, &p, kvm, kv[0], kv[3]);
    }
    if (code >= 0)
        code = fill_wedges(pfs, ku[3], kum, p.pole[3], 1, p.c[1][0], p.c[1][1],
                interpatch_padding | inpatch_wedge);
out:
    release_colors_inline(pfs, color_stack_ptr, 4);
    return code;
}