/* Copyright (C) 2001-2020 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.

*/

/* Path stroking procedures for Ghostscript library */

#include "math_.h"

#include <stdlib.h> /* abs() */

#include "gx.h"

#include "gpcheck.h"

#include "gserrors.h"

#include "gsdcolor.h"

#include "gsptype1.h"

#include "gxfixed.h"

#include "gxfarith.h"

#include "gxmatrix.h"

#include "gscoord.h"

#include "gsdevice.h"

#include "gxdevice.h"

#include "gxhttile.h"

#include "gxgstate.h"

#include "gzline.h"

#include "gzpath.h"

#include "gzcpath.h"

#include "gxpaint.h"

#include "gsstate.h"            /* for gs_currentcpsimode */

/* RJW: There appears to be a difference in the xps and postscript models

 * (at least in as far as Microsofts implementation of xps and Acrobats of

 * postscript). Acrobat (and ghostscript) are happy to join a line segment

 * around a corner, even when the next segment is a dash gap. Microsofts

 * implementation of XPS does not.

 *

 * A test file that shows this up is tests_private/comparefiles/298-05.ps

 *

 * Enabling the following define would emulate xps behaviour here.

 */

#undef AVOID_JOINING_TO_DASH_GAPS

/*

 * We don't really know whether it's a good idea to take fill adjustment

 * into account for stroking.  Disregarding it means that strokes

 * come out thinner than fills; observing it produces heavy-looking

 * strokes at low resolutions.  But in any case, we must disregard it

 * when stroking zero-width lines.

 */

#define USE_FILL_ADJUSTMENT

#ifdef USE_FILL_ADJUSTMENT

#  define STROKE_ADJUSTMENT(thin, pgs, xy)\

     (thin ? fixed_0 : (pgs)->fill_adjust.xy)

#else

#  define STROKE_ADJUSTMENT(thin, pgs, xy) fixed_0

#endif

/*

 * For some reason, we commented out the optimization for portrait,

 * landscape, and uniform (non-scaled) transformations.  We have no record

 * of why we did this, and we don't know what bugs re-enabling it may

 * introduce.

 */

#define OPTIMIZE_ORIENTATION

/*

 * Compute the amount by which to expand a stroked bounding box to account

 * for line width, caps and joins.  Return 0 if the result is exact, 1 if

 * it may be conservative, or gs_error_limitcheck if the result is too

 * large to fit in a gs_fixed_point.

 *

 * Because of square caps and miter and triangular joins, the maximum

 * expansion on each side (in user space) is

 *      K * line_width/2

 * where K is determined as follows:

 *      For round or butt caps, E = 1

 *      For square caps, E = sqrt(2)

 *        If the path is only a single line segment, K = E;

 *          if triangular joins, K = 2;

 *          if miter joins, K = max(miter_limit, E);

 *      otherwise, K = E.

 *

 * If the following conditions apply, K = E yields an exact result:

 *      - The CTM is of the form [X 0 0 Y] or [0 X Y 0].

 *      - Square or round caps are used, or all subpaths are closed.

 *      - All segments (including the implicit segment created by

 *        closepath) are vertical or horizontal lines.

 *

 * Note that these conditions are sufficient, but not necessary, to get an

 * exact result.  We choose this set of conditions because it is easy to

 * check and covers many common cases.  Clients that care always have the

 * option of using strokepath to get an exact result.

 */

static float join_expansion_factor(const gs_gstate *, gs_line_join);

int

gx_stroke_path_expansion(const gs_gstate * pgs, const gx_path * ppath,

                         gs_fixed_point * ppt)

{

    const subpath *psub;

    const segment *pseg;

    double cx = fabs(pgs->ctm.xx) + fabs(pgs->ctm.yx);

    double cy = fabs(pgs->ctm.xy) + fabs(pgs->ctm.yy);

    double expand = pgs->line_params.half_width;

    int result = 1;

    if (ppath == NULL) {

        ppt->x = ppt->y = 0;

        return 0;   /* no expansion */

    }

    psub = ppath->first_subpath;

    /* Adjust the expansion (E) for square caps, if needed */

    if (pgs->line_params.start_cap == gs_cap_square ||

        pgs->line_params.end_cap == gs_cap_square)

            expand *= 1.414213562;

    /* Check for whether an exact result can be computed easily. */

    if (is_fzero2(pgs->ctm.xy, pgs->ctm.yx) ||

        is_fzero2(pgs->ctm.xx, pgs->ctm.yy)

        ) {

        bool must_be_closed =

            !(pgs->line_params.start_cap == gs_cap_square ||

              pgs->line_params.start_cap == gs_cap_round  ||

              pgs->line_params.end_cap   == gs_cap_square ||

              pgs->line_params.end_cap   == gs_cap_round  ||

              pgs->line_params.dash_cap  == gs_cap_square ||

              pgs->line_params.dash_cap  == gs_cap_round);

        gs_fixed_point prev;

        prev.x = prev.y = 0; /* Quiet gcc warning. */

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

             prev = pseg->pt, pseg = pseg->next

             )

            switch (pseg->type) {

            case s_start:

                if (((const subpath *)pseg)->curve_count ||

                    (must_be_closed && !((const subpath *)pseg)->is_closed)

                    )

                    goto not_exact;

                break;

            case s_line:

            case s_dash:

            case s_line_close:

                if (!(pseg->pt.x == prev.x || pseg->pt.y == prev.y))

                    goto not_exact;

                break;

            case s_gap:

            default:            /* other/unknown segment type */

                goto not_exact;

            }

        result = 0;             /* exact result */

    }

not_exact:

    if (result) {

        if (!gx_path_has_curves(ppath) && gx_path_subpath_count(ppath) <= 1 &&

            (psub == 0 || (pseg = psub->next) == 0 ||

             (pseg = pseg->next) == 0 || pseg->type == s_line_close))

            DO_NOTHING;

        else {

            float factor = join_expansion_factor(pgs, pgs->line_params.join);

            if (pgs->line_params.curve_join >= 0)

                factor = max(factor, join_expansion_factor(pgs,

                                (gs_line_join)pgs->line_params.curve_join));

            expand *= factor;

        }

    }

    /* Short-cut gs_bbox_transform. */

    {

        float exx = expand * cx;

        float exy = expand * cy;

        int code = set_float2fixed_vars(ppt->x, exx);

        if (code < 0)

            return code;

        code = set_float2fixed_vars(ppt->y, exy);

        if (code < 0)

            return code;

    }

    return result;

}

static float

join_expansion_factor(const gs_gstate *pgs, gs_line_join join)

{

    switch (join) {

    case gs_join_miter: return pgs->line_params.miter_limit;

    case gs_join_triangle: return 2.0;

    default: return 1.0;

    }

}

/*

 * Structure for a partial line (passed to the drawing routine).

 * Two of these are required to do joins right.

 * Each endpoint includes the two ends of the cap as well,

 * and the deltas for square, round, and triangular cap computation.

 *

 * The two base values for computing the caps of a partial line are the

 * width and the end cap delta.  The width value is one-half the line

 * width (suitably transformed) at 90 degrees counter-clockwise

 * (in device space, but with "90 degrees" interpreted in *user*

 * coordinates) at the end (as opposed to the origin) of the line.

 * The cdelta value is one-half the transformed line width in the same

 * direction as the line.  From these, we compute two other values at each

 * end of the line: co and ce, which are the ends of the cap.

 * Note that the cdelta values at o are the negatives of the values at e,

 * as are the offsets from p to co and ce.

 *

 * Initially, only o.p, e.p, e.cdelta, width, and thin are set.

 * compute_caps fills in the rest.

 */

typedef gs_fixed_point *p_ptr;

typedef struct endpoint_s {

    gs_fixed_point p;           /* the end of the line */

    gs_fixed_point co, ce;      /* ends of the cap, p +/- width */

    gs_fixed_point cdelta;      /* +/- cap length */

} endpoint;

typedef endpoint *ep_ptr;

typedef const endpoint *const_ep_ptr;

typedef struct partial_line_s {

    endpoint o;                 /* starting coordinate */

    endpoint e;                 /* ending coordinate */

    gs_fixed_point width;       /* one-half line width, see above */

    gs_fixed_point vector;      /* The line segment direction */

    bool thin;                  /* true if minimum-width line */

} partial_line;

typedef partial_line *pl_ptr;

/* As we stroke a path, we run through the line segments that make it up.

 * We gather each line segment together with any degenerate line segments

 * that follow it (call this set "prev"), and then 'join them' to the next

 * line segment (and any degenerate line segments that follow it) (if there

 * is one) (call this "current").

 *

 * In order to get the joins right we need to keep flags about both

 * prev and current, and whether they originally came from arcs.

 */

typedef enum note_flags {

    /* If set, all the line segments that make up current come from arcs. */

    nf_all_from_arc       = 1,

    /* If set, at least one of the line segments that make up current, come

     * from arcs. */

    nf_some_from_arc      = 2,

    /* If set then this segment should have a dash cap on the start rather

     * than a start cap. */

    nf_dash_head          = 4,

    /* If set then this segment should have a dash cap on the end rather

     * than an end cap. */

    nf_dash_tail          = 8,

    /* If set, all the line segments that make up prev come from arcs. */

    nf_prev_all_from_arc  = 16,

    /* If set, at least one of the line segment that make up prev, come from

     * arcs. */

    nf_prev_some_from_arc = 32,

    /* If set then prev should have a dash cap on the start rather

     * than a start cap. */

    nf_prev_dash_head     = 64,

    /* If set then prev should have a dash cap on the end rather

     * than an end cap. */

    nf_prev_dash_tail     = 128

} note_flags;

/* Macro to combine the prev and current arc_flags. After applying this

 * macro, the bits in the result have the following meanings:

 *  nf_all_from_arc    set if all the components of current and prev

 *                     come from an Arc.

 *  nf_some_from_arc   set if any of the components of current and

 *                     prev come from an Arc.

 *  nf_dash_head       set if prev should have a dash cap rather than

 *                     a start cap.

 *  nf_dash_tail       set if prev should have a dash cap rather than

 *                     an end cap.

 */

#define COMBINE_FLAGS(F) \

    (((F>>4) | ((F) & nf_some_from_arc)) & \

     (((F) & nf_all_from_arc) ? ~0 : ~nf_all_from_arc))

/* Assign a point.  Some compilers would do this with very slow code */

/* if we simply implemented it as an assignment. */

#define ASSIGN_POINT(pp, p)\

  ((pp)->x = (p).x, (pp)->y = (p).y)

/* Other forward declarations */

static bool width_is_thin(pl_ptr);

static void adjust_stroke(gx_device *, pl_ptr, const gs_gstate *, bool, bool, note_flags);

static int line_join_points(const gx_line_params * pgs_lp,

                             pl_ptr plp, pl_ptr nplp,

                             gs_fixed_point * join_points,

                             const gs_matrix * pmat, gs_line_join join,

                             bool reflected);

static int line_join_points_fast_cw(const gx_line_params * pgs_lp,

                                    pl_ptr plp, pl_ptr nplp,

                                    gs_fixed_point * rjoin_points,

                                    const gs_matrix * pmat,

                                    gs_line_join join);

static int line_join_points_fast_ccw(const gx_line_params * pgs_lp,

                                     pl_ptr plp, pl_ptr nplp,

                                     gs_fixed_point * join_points,

                                     const gs_matrix * pmat,

                                     gs_line_join join);

static void compute_caps(pl_ptr);

static int add_points(gx_path *, const gs_fixed_point *,

                       int, bool);

static int add_pie_join(gx_path *, pl_ptr, pl_ptr, bool, bool);

static int add_pie_join_fast_cw(gx_path *, pl_ptr, pl_ptr, bool);

static int add_pie_join_fast_ccw(gx_path *, pl_ptr, pl_ptr, bool);

static int add_round_cap(gx_path *, const_ep_ptr);

static int add_pie_cap(gx_path *, const_ep_ptr);

static int cap_points(gs_line_cap, const_ep_ptr,

                       gs_fixed_point * /*[3] */ );

static int join_under_pie(gx_path *, pl_ptr, pl_ptr, bool);

/* Define the default implementation of the device stroke_path procedure. */

int

gx_default_stroke_path(gx_device * dev, const gs_gstate * pgs,

                       gx_path * ppath, const gx_stroke_params * params,

                       const gx_drawing_color * pdcolor,

                       const gx_clip_path * pcpath)

{

    return gx_stroke_path_only(ppath, (gx_path *) 0, dev, pgs, params,

                               pdcolor, pcpath);

}

/* Fill a partial stroked path.  Free variables: */

/* to_path, stroke_path_body, fill_params, always_thin, pgs, dev, pdevc, */

/* code, ppath, exit(label). */

#define FILL_STROKE_PATH(dev, thin, pcpath, final)\

  if(to_path==&stroke_path_body && !gx_path_is_void(&stroke_path_body) &&\

     (final || lop_is_idempotent(pgs->log_op))) {\

    fill_params.adjust.x = STROKE_ADJUSTMENT(thin, pgs, x);\

    fill_params.adjust.y = STROKE_ADJUSTMENT(thin, pgs, y);\

    if (to_path_reverse != NULL) {\

        code = gx_join_path_and_reverse(to_path, to_path_reverse);\

        if(code < 0) goto exit;\

    }\

    code = gx_fill_path_only(to_path, dev, pgs, &fill_params, pdevc, pcpath);\

    gx_path_free(&stroke_path_body, "fill_stroke_path");\

    if ( code < 0 ) goto exit;\

    gx_path_init_local(&stroke_path_body, ppath->memory);\

  }

/*

 * Define the internal procedures that stroke a partial_line

 * (the first pl_ptr argument).  If both partial_lines are non-null,

 * the procedure creates an appropriate join; otherwise, the procedure

 * creates an end cap.  If the first int is 0, the procedure also starts

 * with an appropriate cap.

 */

#define stroke_line_proc(proc)\

  int proc(gx_path *, gx_path *, bool ensure_closed, int, pl_ptr, pl_ptr,\

           const gx_device_color *, gx_device *, const gs_gstate *,\

           const gx_stroke_params *, const gs_fixed_rect *, int,\

           gs_line_join, bool, note_flags)

typedef stroke_line_proc((*stroke_line_proc_t));

static stroke_line_proc(stroke_add);

static stroke_line_proc(stroke_add_compat);

static stroke_line_proc(stroke_add_fast);

static stroke_line_proc(stroke_fill);

static int stroke_add_initial_cap_compat(gx_path * ppath, pl_ptr plp, bool adlust_longitude,

           const gx_device_color * pdevc, gx_device * dev,

           const gs_gstate * pgs);

/* Define the orientations we handle specially. */

typedef enum {

    orient_other = 0,

    orient_portrait,            /* [xx 0 0 yy tx ty] */

    orient_landscape            /* [0 xy yx 0 tx ty] */

} orientation;

/*

 * Internal function used to merge the 2 sides of a stroked path.

 * path contains the 'forward' side, rpath contains the 'reversed' side.

 * Reverse rpath, then append it to path.

 *

 * If path is closed, then rpath should be too. If path is open, then the

 * starting and ending points of both paths should be the same, so as to

 * guarantee a closed path.

 */

static int

gx_join_path_and_reverse(gx_path * path, gx_path * rpath)

{

    int code;

    if (gx_path_is_void(rpath))

        return 0;

     code = gx_path_append_reversed(rpath, path);

    if (code < 0)

        return code;

    gx_path_free(rpath, "gx_join_path_and_reverse");

    gx_path_init_local(rpath, path->memory);

    return gx_path_close_subpath(path);

}

/*

 * Stroke a path.  If to_path != 0, append the stroke outline to it;

 * if to_path == 0, draw the strokes on pdev.

 *

 * Note that gx_stroke_path_only with to_path != NULL may clip the path to

 * the clipping path, as for to_path == NULL.  This is almost never

 * what is wanted.

 */

static int

gx_stroke_path_only_aux(gx_path * ppath, gx_path * to_path, gx_device * pdev,

               const gs_gstate * pgs, const gx_stroke_params * params,

                 const gx_device_color * pdevc, const gx_clip_path * pcpath)

{

    bool CPSI_mode = gs_currentcpsimode(pgs->memory);

    bool traditional = CPSI_mode | params->traditional;

    stroke_line_proc_t line_proc =

               ((to_path == 0 && !gx_dc_is_pattern1_color_clist_based(pdevc))

                      ? (lop_is_idempotent(pgs->log_op) ? stroke_fill : stroke_add) :

                        (traditional ? stroke_add_compat : stroke_add_fast));

    gs_fixed_rect ibox, cbox;

    gx_device_clip cdev;

    gx_device *dev = pdev;

    int code = 0;

    gx_fill_params fill_params;

    const gx_line_params *pgs_lp = gs_currentlineparams_inline(pgs);

    int dash_count = pgs_lp->dash.pattern_size;

    gx_path fpath, dpath;

    gx_path stroke_path_body;

    gx_path stroke_path_reverse;

    gx_path *to_path_reverse = NULL;

    const gx_path *spath;

    float xx = pgs->ctm.xx, xy = pgs->ctm.xy;

    float yx = pgs->ctm.yx, yy = pgs->ctm.yy;

    /*

     * We are dealing with a reflected coordinate system

     * if transform(1,0) is counter-clockwise from transform(0,1).

     * See the note in stroke_add for the algorithm.

     */

    int uniform;

    bool reflected;

    orientation orient =

        (

#ifdef OPTIMIZE_ORIENTATION

         is_fzero2(xy, yx) ?

         (uniform = (xx == yy ? 1 : xx == -yy ? -1 : 0),

          reflected = (uniform ? uniform < 0 : (xx < 0) != (yy < 0)),

          orient_portrait) :

         is_fzero2(xx, yy) ?

         (uniform = (xy == yx ? -1 : xy == -yx ? 1 : 0),

          reflected = (uniform ? uniform < 0 : (xy < 0) == (yx < 0)),

          orient_landscape) :

    /* We should optimize uniform rotated coordinate systems */

    /* here as well, but we don't. */

#endif

         (uniform = 0,

          reflected = xy * yx > xx * yy,

          orient_other));

    const segment_notes not_first = sn_not_first;

    gs_line_join curve_join =

        (pgs_lp->curve_join >= 0 ? (gs_line_join)pgs_lp->curve_join :

         pgs_lp->join == gs_join_none || pgs_lp->join == gs_join_round ?

            gs_join_bevel : pgs_lp->join);

    float line_width = pgs_lp->half_width;      /* (*half* the line width) */

    bool always_thin;

    double line_width_and_scale;

    double device_line_width_scale = 0; /* Quiet compiler. */

    double device_dot_length = pgs_lp->dot_length * fixed_1;

    const subpath *psub;

    gs_matrix initial_matrix;

    bool initial_matrix_reflected;

    note_flags flags;

    (*dev_proc(pdev, get_initial_matrix)) (pdev, &initial_matrix);

    initial_matrix_reflected = initial_matrix.xy * initial_matrix.yx >

                               initial_matrix.xx * initial_matrix.yy;

#ifdef DEBUG

    if (gs_debug_c('o')) {

        int i;

        dmlprintf4(ppath->memory, "[o]half_width=%f, start_cap=%d, end_cap=%d, dash_cap=%d,\n",

                   pgs_lp->half_width, (int)pgs_lp->start_cap,

                   (int)pgs_lp->end_cap, (int)pgs_lp->dash_cap);

        dmlprintf3(ppath->memory, "   join=%d, miter_limit=%f, miter_check=%f,\n",

                   (int)pgs_lp->join, pgs_lp->miter_limit,

                   pgs_lp->miter_check);

        dmlprintf1(ppath->memory, "   dash pattern=%d", dash_count);

        for (i = 0; i < dash_count; i++)

            dmprintf1(ppath->memory, ",%f", pgs_lp->dash.pattern[i]);

        dmputs(ppath->memory, ",\n");

        dmlprintf4(ppath->memory, "\toffset=%f, init(ink_on=%d, index=%d, dist_left=%f)\n",

                   pgs_lp->dash.offset, pgs_lp->dash.init_ink_on,

                   pgs_lp->dash.init_index, pgs_lp->dash.init_dist_left);

    }

#endif

    gx_path_bbox(ppath, &ibox);

    /* Expand the path bounding box by the scaled line width. */

    {

        gs_fixed_point expansion;

        if (gx_stroke_path_expansion(pgs, ppath, &expansion) < 0) {

            /* The expansion is so large it caused a limitcheck. */

            ibox.p.x = ibox.p.y = min_fixed;

            ibox.q.x = ibox.q.y = max_fixed;

        } else {

            expansion.x += pgs->fill_adjust.x;

            expansion.y += pgs->fill_adjust.y;

            /*

             * It's theoretically possible for the following computations to

             * overflow, so we need to check for this.

             */

            ibox.p.x = (ibox.p.x < min_fixed + expansion.x ? min_fixed :

                        ibox.p.x - expansion.x);

            ibox.p.y = (ibox.p.y < min_fixed + expansion.y ? min_fixed :

                        ibox.p.y - expansion.y);

            ibox.q.x = (ibox.q.x > max_fixed - expansion.x ? max_fixed :

                        ibox.q.x + expansion.x);

            ibox.q.y = (ibox.q.y > max_fixed - expansion.y ? max_fixed :

                        ibox.q.y + expansion.y);

        }

    }

    /* Check the expanded bounding box against the clipping regions. */

    if (pcpath)

        gx_cpath_inner_box(pcpath, &cbox);

    else if (pdevc)

        (*dev_proc(pdev, get_clipping_box)) (pdev, &cbox);

    else {

        /* This is strokepath, not stroke.  Don't clip. */

        cbox = ibox;

    }

    if (!rect_within(ibox, cbox)) {

        /* Intersect the path box and the clip bounding box. */

        /* If the intersection is empty, this call is a no-op. */

        gs_fixed_rect bbox;

        if (pcpath) {

            gx_cpath_outer_box(pcpath, &bbox);

            if_debug4m('f', ppath->memory, "   outer_box=(%g,%g),(%g,%g)\n",

                       fixed2float(bbox.p.x), fixed2float(bbox.p.y),

                       fixed2float(bbox.q.x), fixed2float(bbox.q.y));

            rect_intersect(ibox, bbox);

        } else

            rect_intersect(ibox, cbox);

        if (ibox.p.x >= ibox.q.x || ibox.p.y >= ibox.q.y) {

            /* Intersection of boxes is empty! */

            return 0;

        }

        /*

         * The path is neither entirely inside the inner clip box

         * nor entirely outside the outer clip box.

         * If we had to flatten the path, this is where we would

         * recompute its bbox and make the tests again,

         * but we don't bother right now.

         */

        /*

         * If there is a clipping path, set up a clipping device.

         * for stroke_fill because, because the latter uses low level methods

         * which don't accept a clipping path.

         * Note that in some cases stroke_fill appends the path to stroke_path_body

         * instead a real painting, and it is painted with FILL_STROKE_PATH.

         *

         * Contrary to that, FILL_STROKE_PATH paints a path with

         * the fill_path method, which handles a clipping path,

         * so we don't pass the clipper device to FILL_STROKE_PATH

         * to prevent an appearence of superposing clippers.

         */

        if (pcpath && line_proc == stroke_fill) {

            gx_make_clip_device_on_stack(&cdev, pcpath, pdev);

            cdev.max_fill_band = pdev->max_fill_band;

            dev = (gx_device *)&cdev;

        }

    }

    fill_params.rule = gx_rule_winding_number;

    fill_params.flatness = pgs->flatness;

    if (line_width < 0)

        line_width = -line_width;

    line_width_and_scale = line_width * (double)int2fixed(1);

    if (is_fzero(line_width))

        always_thin = true;

    else {

        float xa, ya;

        switch (orient) {

            case orient_portrait:

                xa = xx, ya = yy;

                goto sat;

            case orient_landscape:

                xa = xy, ya = yx;

              sat:

                if (xa < 0)

                    xa = -xa;

                if (ya < 0)

                    ya = -ya;

                always_thin = (max(xa, ya) * line_width < 0.5);

                if (!always_thin && uniform) {  /* Precompute a value we'll need later. */

                    device_line_width_scale = line_width_and_scale * xa;

                }

                break;

            default:

                {

                    /* The check is more complicated, but it's worth it. */

                    /* Compute radii of the transformed round brush. */

                    /* Let x = [a, sqrt(1-a^2)]'

                       radius^2 is an extremum of :

                       rr(a)=(CTM*x)^2 = (a*xx + sqrt(1 - a^2)*xy)^2 + (a*yx + sqrt(1 - a^2)*yy)^2

                       With solving D(rr(a),a)==0, got :

                       max_rr = (xx^2 + xy^2 + yx^2 + yy^2 + sqrt(((xy + yx)^2 + (xx - yy)^2)*((xy - yx)^2 + (xx + yy)^2)))/2.

                       r = sqrt(max_rr);

                       Well we could use eigenvalues of the quadratic form,

                       but it gives same result with a bigger calculus.

                     */

                    double max_rr = ((double)(xx*xx + xy*xy + yx*yx + yy*yy) +

                                     sqrt((double)((xy + yx)*(xy + yx) + (xx - yy)*(xx - yy)) *

                                                  ((xy - yx)*(xy - yx) + (xx + yy)*(xx + yy))

                                          )

                                     )/2;

                    always_thin = max_rr * line_width * line_width < 0.25;

                }

        }

    }

    if_debug7m('o', ppath->memory, "[o]ctm=(%g,%g,%g,%g,%g,%g) thin=%d\n",

              xx, xy, yx, yy, pgs->ctm.tx, pgs->ctm.ty, always_thin);

    if (device_dot_length != 0) {

        /*

         * Compute the dot length in device space.  We can't do this

         * quite right for non-uniform coordinate systems; too bad.

         */

        gs_matrix mat;

        const gs_matrix *pmat;

        if (pgs_lp->dot_length_absolute) {

            gs_deviceinitialmatrix(pdev, &mat);

            pmat = &mat;

        } else

            pmat = (const gs_matrix *)&pgs->ctm;

        device_dot_length *= fabs(pmat->xy) + fabs(pmat->yy);

    }

    /* Start by flattening the path.  We should do this on-the-fly.... */

    if (!gx_path_has_curves(ppath) && !gx_path_has_long_segments(ppath)) {

        /* don't need to flatten */

        if (!ppath->first_subpath)

            return 0;

        spath = ppath;

    } else {

        gx_path_init_local(&fpath, ppath->memory);

        if ((code = gx_path_add_flattened_for_stroke(ppath, &fpath,

                                                params->flatness, pgs)) < 0

            )

            return code;

        spath = &fpath;

    }

    if (dash_count) {

        float max_dash_len = 0;

        float expand_squared;

        int i;

        float adjust = (float)pgs->fill_adjust.x;

        if (adjust > (float)pgs->fill_adjust.y)

            adjust = (float)pgs->fill_adjust.y;

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

            if (max_dash_len < pgs_lp->dash.pattern[i])

                max_dash_len = pgs_lp->dash.pattern[i];

        }

        expand_squared = pgs->ctm.xx * pgs->ctm.yy - pgs->ctm.xy * pgs->ctm.yx;

        if (expand_squared < 0)

            expand_squared = -expand_squared;

        expand_squared *= max_dash_len * max_dash_len;

        /* Wide lines in curves can show dashes up, so fudge to allow for

         * this. */

        if (pgs->line_params.half_width > 1)

            adjust /= pgs->line_params.half_width;

        if (expand_squared*65536.0f >= (float)(adjust*adjust)) {

            gx_path_init_local(&dpath, ppath->memory);

            code = gx_path_add_dash_expansion(spath, &dpath, pgs);

            if (code < 0)

                goto exf;

            spath = &dpath;

        } else {

            dash_count = 0;

        }

    }

    if (to_path == 0) {

        /* We might try to defer this if it's expensive.... */

        to_path = &stroke_path_body;

        gx_path_init_local(&stroke_path_body, ppath->memory);

    }

    if (line_proc == stroke_add_fast) {

        to_path_reverse = &stroke_path_reverse;

        gx_path_init_local(&stroke_path_reverse, ppath->memory);

    }

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

        int index = 0;

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

        fixed x = pseg->pt.x;

        fixed y = pseg->pt.y;

        bool is_closed = ((const subpath *)pseg)->is_closed;

        partial_line pl, pl_prev, pl_first;

        bool zero_length = true;

        int pseg_notes = pseg->notes;

        flags = nf_all_from_arc;

        /* Run through each segment in the current path, drawing each segment

         * delayed by 1 - that is, when we're looking at segment n, we draw

         * (or not) segment n-1. This delay allows us to always know whether

         * to join or cap the line. */

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

               pseg->type != s_start

            ) {

            /* Compute the width parameters in device space. */

            /* We work with unscaled values, for speed. */

            fixed sx, udx, sy, udy;

            bool is_dash_segment;

            pseg_notes = pseg->notes;

         d2:is_dash_segment = false;

         d1:if (pseg->type == s_dash) {

                dash_segment *pd = (dash_segment *)pseg;

                sx = pd->pt.x;

                sy = pd->pt.y;

                udx = pd->tangent.x;

                udy = pd->tangent.y;

                is_dash_segment = true;

            } else if (pseg->type == s_gap) {

                sx = pseg->pt.x;

                sy = pseg->pt.y;

                udx = sx - x;

                udy = sy - y;

                is_dash_segment = true;

            } else {

                sx = pseg->pt.x;

                sy = pseg->pt.y;

                udx = sx - x;

                udy = sy - y;

            }

            zero_length &= ((udx | udy) == 0);

            pl.o.p.x = x, pl.o.p.y = y;

          d:flags = (((pseg_notes & sn_not_first) ?

                      ((flags & nf_all_from_arc) | nf_some_from_arc) : 0) |

                     ((pseg_notes & sn_dash_head) ? nf_dash_head : 0)    |

                     ((pseg_notes & sn_dash_tail) ? nf_dash_tail : 0)    |

                     (flags & ~nf_all_from_arc));

            pl.e.p.x = sx, pl.e.p.y = sy;

            if (!(udx | udy) || pseg->type == s_dash || pseg->type == s_gap) { /* degenerate or short */

                /*

                 * If this is the first segment of the subpath,

                 * check the entire subpath for degeneracy.

                 * Otherwise, ignore the degenerate segment.

                 */

                if (index != 0 && pseg->type != s_dash && pseg->type != s_gap)

                {

                    if (pseg->next == NULL || pseg->next->type == s_start)

                        continue;

                    pseg = pseg->next;

                    /* We're skipping a degenerate path segment; if it was

                     * labelled as being the first from a curve, then make

                     * sure the one we're skipping to is also labelled as

                     * being the first from a curve, otherwise we can get

                     * improper joins being used. See Bug 696466. */

                    pseg_notes = (((pseg_notes & sn_not_first) == 0) ?

                                  (pseg->notes & ~sn_not_first) :

                                  pseg->notes);

                    goto d2;

                }

                /* Check for a degenerate subpath. */

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

                       pseg->type != s_start

                    ) {

                    if (is_dash_segment)

                        break;

                    if (pseg->type == s_dash || pseg->type == s_gap)

                        goto d1;

                    sx = pseg->pt.x, udx = sx - x;

                    sy = pseg->pt.y, udy = sy - y;

                    if (udx | udy) {

                        zero_length = false;

                        goto d;

                    }

                }

                if (pgs_lp->dot_length == 0 &&

                    pgs_lp->start_cap != gs_cap_round &&

                    pgs_lp->end_cap != gs_cap_round &&

                    !is_dash_segment) {

                    /* From PLRM, stroke operator :

                       If a subpath is degenerate (consists of a single-point closed path

                       or of two or more points at the same coordinates),

                       stroke paints it only if round line caps have been specified */

                    break;

                }

                /*

                 * If the subpath is a dash, take the orientation from the dash segment.

                 * Otherwise orient the dot according to the previous segment if

                 * any, or else the next segment if any, or else

                 * according to the specified dot orientation.

                 */

                {

                    /* When passing here, either pseg == NULL or it points to the

                       start of the next subpaph. So we can't use pseg

                       for determining the segment direction.

                       In same time, psub->last may help, so use it. */

                    const segment *end = psub->last;

                    if (is_dash_segment) {

                        /* Nothing. */

                    } else if (end != 0 && (end->pt.x != x || end->pt.y != y))

                        sx = end->pt.x, sy = end->pt.y, udx = sx - x, udy = sy - y;

                }

                /*

                 * Compute the properly oriented dot length, and then

                 * draw the dot like a very short line.

                 */

                if ((udx | udy) == 0) {

                    if (is_fzero(pgs_lp->dot_orientation.xy)) {

                        /* Portrait orientation, dot length = X */

                        udx = fixed_1;

                    } else {

                        /* Landscape orientation, dot length = Y */

                        udy = fixed_1;

                    }

                }

                if (sx == x && sy == y && (pseg == NULL || pseg->type == s_start)) {

                    double scale = device_dot_length /

                                hypot((double)udx, (double)udy);

                    fixed udx1, udy1;

                    /*

                     * If we're using butt caps, make sure the "line" is

                     * long enough to show up.

                     * Don't apply this with always_thin, becase

                     * draw thin line always rounds the length up.

                     */

                    if (!always_thin && (pgs_lp->start_cap == gs_cap_butt ||

                                         pgs_lp->end_cap   == gs_cap_butt ||

                                         pgs_lp->dash_cap  == gs_cap_butt)) {

                        fixed dmax = max(any_abs(udx), any_abs(udy));

                        if (dmax * scale < fixed_1)

                            scale = (float)fixed_1 / dmax;

                    }

                    udx1 = (fixed) (udx * scale);

                    udy1 = (fixed) (udy * scale);

                    sx = x + udx1;

                    sy = y + udy1;

                }

                /*

                 * Back up 1 segment to keep the bookkeeping straight.

                 */

                pseg = (pseg != 0 ? pseg->prev : psub->last);

                if (!is_dash_segment)

                    goto d;

                pl.e.p.x = sx;

                pl.e.p.y = sy;

            }

            pl.vector.x = udx;

            pl.vector.y = udy;

            if (always_thin) {

                pl.e.cdelta.x = pl.e.cdelta.y = 0;

                pl.width.x = pl.width.y = 0;

                pl.thin = true;

            } else {

                if (uniform != 0) {

                    /* We can save a lot of work in this case. */

                    /* We know orient != orient_other. */

                    double dpx = udx, dpy = udy;

                    double wl = device_line_width_scale /

                    hypot(dpx, dpy);

                    pl.e.cdelta.x = (fixed) (dpx * wl);

                    pl.e.cdelta.y = (fixed) (dpy * wl);

                    /* The width is the cap delta rotated by */

                    /* 90 degrees. */

                    if (initial_matrix_reflected)

                        pl.width.x = pl.e.cdelta.y, pl.width.y = -pl.e.cdelta.x;

                    else

                        pl.width.x = -pl.e.cdelta.y, pl.width.y = pl.e.cdelta.x;

                    pl.thin = false;    /* if not always_thin, */

                    /* then never thin. */

                } else {

                    gs_point dpt;       /* unscaled */

                    float wl;

                    code = gs_gstate_idtransform(pgs,

                                                 (float)udx, (float)udy,

                                                 &dpt);

                    if (code < 0) {

                        dpt.x = 0; dpt.y = 0;

                        /* Swallow the error */

                        code = 0;

                    } else {

                        wl = line_width_and_scale /

                            hypot(dpt.x, dpt.y);

                        /* Construct the width vector in */

                        /* user space, still unscaled. */

                        dpt.x *= wl;

                        dpt.y *= wl;

                    }