/*

 * Copyright (c) 2007, 2017, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package sun.java2d.marlin;

import static sun.java2d.marlin.OffHeapArray.SIZE_INT;

import jdk.internal.misc.Unsafe;

final class DRenderer implements DPathConsumer2D, MarlinRenderer {

    static final boolean DISABLE_RENDER = false;

    static final boolean ENABLE_BLOCK_FLAGS = MarlinProperties.isUseTileFlags();

    static final boolean ENABLE_BLOCK_FLAGS_HEURISTICS = MarlinProperties.isUseTileFlagsWithHeuristics();

    private static final int ALL_BUT_LSB = 0xFFFFFFFE;

    private static final int ERR_STEP_MAX = 0x7FFFFFFF; // = 2^31 - 1

    private static final double POWER_2_TO_32 = 0x1.0p32d;

    // use double to make tosubpix methods faster (no int to double conversion)

    static final double SUBPIXEL_SCALE_X = SUBPIXEL_POSITIONS_X;

    static final double SUBPIXEL_SCALE_Y = SUBPIXEL_POSITIONS_Y;

    static final int SUBPIXEL_MASK_X = SUBPIXEL_POSITIONS_X - 1;

    static final int SUBPIXEL_MASK_Y = SUBPIXEL_POSITIONS_Y - 1;

    // number of subpixels corresponding to a tile line

    private static final int SUBPIXEL_TILE

        = TILE_H << SUBPIXEL_LG_POSITIONS_Y;

    // 2048 (pixelSize) pixels (height) x 8 subpixels = 64K

    static final int INITIAL_BUCKET_ARRAY

        = INITIAL_PIXEL_DIM * SUBPIXEL_POSITIONS_Y;

    // crossing capacity = edges count / 4 ~ 1024

    static final int INITIAL_CROSSING_COUNT = INITIAL_EDGES_COUNT >> 2;

    public static final int WIND_EVEN_ODD = 0;

    public static final int WIND_NON_ZERO = 1;

    // common to all types of input path segments.

    // OFFSET as bytes

    // only integer values:

    public static final long OFF_CURX_OR  = 0;

    public static final long OFF_ERROR    = OFF_CURX_OR  + SIZE_INT;

    public static final long OFF_BUMP_X   = OFF_ERROR    + SIZE_INT;

    public static final long OFF_BUMP_ERR = OFF_BUMP_X   + SIZE_INT;

    public static final long OFF_NEXT     = OFF_BUMP_ERR + SIZE_INT;

    public static final long OFF_YMAX     = OFF_NEXT     + SIZE_INT;

    // size of one edge in bytes

    public static final int SIZEOF_EDGE_BYTES = (int)(OFF_YMAX + SIZE_INT);

    // curve break into lines

    // cubic error in subpixels to decrement step

    private static final double CUB_DEC_ERR_SUBPIX

        = MarlinProperties.getCubicDecD2() * (NORM_SUBPIXELS / 8.0d); // 1 pixel

    // cubic error in subpixels to increment step

    private static final double CUB_INC_ERR_SUBPIX

        = MarlinProperties.getCubicIncD1() * (NORM_SUBPIXELS / 8.0d); // 0.4 pixel

    // TestNonAARasterization (JDK-8170879): cubics

    // bad paths (59294/100000 == 59,29%, 94335 bad pixels (avg = 1,59), 3966 warnings (avg = 0,07)

    // cubic bind length to decrement step

    public static final double CUB_DEC_BND

        = 8.0d * CUB_DEC_ERR_SUBPIX;

    // cubic bind length to increment step

    public static final double CUB_INC_BND

        = 8.0d * CUB_INC_ERR_SUBPIX;

    // cubic countlg

    public static final int CUB_COUNT_LG = 2;

    // cubic count = 2^countlg

    private static final int CUB_COUNT = 1 << CUB_COUNT_LG;

    // cubic count^2 = 4^countlg

    private static final int CUB_COUNT_2 = 1 << (2 * CUB_COUNT_LG);

    // cubic count^3 = 8^countlg

    private static final int CUB_COUNT_3 = 1 << (3 * CUB_COUNT_LG);

    // cubic dt = 1 / count

    private static final double CUB_INV_COUNT = 1.0d / CUB_COUNT;

    // cubic dt^2 = 1 / count^2 = 1 / 4^countlg

    private static final double CUB_INV_COUNT_2 = 1.0d / CUB_COUNT_2;

    // cubic dt^3 = 1 / count^3 = 1 / 8^countlg

    private static final double CUB_INV_COUNT_3 = 1.0d / CUB_COUNT_3;

    // quad break into lines

    // quadratic error in subpixels

    private static final double QUAD_DEC_ERR_SUBPIX

        = MarlinProperties.getQuadDecD2() * (NORM_SUBPIXELS / 8.0d); // 0.5 pixel

    // TestNonAARasterization (JDK-8170879): quads

    // bad paths (62916/100000 == 62,92%, 103818 bad pixels (avg = 1,65), 6514 warnings (avg = 0,10)

    // quadratic bind length to decrement step

    public static final double QUAD_DEC_BND

        = 8.0d * QUAD_DEC_ERR_SUBPIX;

//////////////////////////////////////////////////////////////////////////////

//  SCAN LINE

//////////////////////////////////////////////////////////////////////////////

    // crossings ie subpixel edge x coordinates

    private int[] crossings;

    // auxiliary storage for crossings (merge sort)

    private int[] aux_crossings;

    // indices into the segment pointer lists. They indicate the "active"

    // sublist in the segment lists (the portion of the list that contains

    // all the segments that cross the next scan line).

    private int edgeCount;

    private int[] edgePtrs;

    // auxiliary storage for edge pointers (merge sort)

    private int[] aux_edgePtrs;

    // max used for both edgePtrs and crossings (stats only)

    private int activeEdgeMaxUsed;

    // crossings ref (dirty)

    private final IntArrayCache.Reference crossings_ref;

    // edgePtrs ref (dirty)

    private final IntArrayCache.Reference edgePtrs_ref;

    // merge sort initial arrays (large enough to satisfy most usages) (1024)

    // aux_crossings ref (dirty)

    private final IntArrayCache.Reference aux_crossings_ref;

    // aux_edgePtrs ref (dirty)

    private final IntArrayCache.Reference aux_edgePtrs_ref;

//////////////////////////////////////////////////////////////////////////////

//  EDGE LIST

//////////////////////////////////////////////////////////////////////////////

    private int edgeMinY = Integer.MAX_VALUE;

    private int edgeMaxY = Integer.MIN_VALUE;

    private double edgeMinX = Double.POSITIVE_INFINITY;

    private double edgeMaxX = Double.NEGATIVE_INFINITY;

    // edges [ints] stored in off-heap memory

    private final OffHeapArray edges;

    private int[] edgeBuckets;

    private int[] edgeBucketCounts; // 2*newedges + (1 if pruning needed)

    // used range for edgeBuckets / edgeBucketCounts

    private int buckets_minY;

    private int buckets_maxY;

    // edgeBuckets ref (clean)

    private final IntArrayCache.Reference edgeBuckets_ref;

    // edgeBucketCounts ref (clean)

    private final IntArrayCache.Reference edgeBucketCounts_ref;

    // Flattens using adaptive forward differencing. This only carries out

    // one iteration of the AFD loop. All it does is update AFD variables (i.e.

    // X0, Y0, D*[X|Y], COUNT; not variables used for computing scanline crossings).

    private void quadBreakIntoLinesAndAdd(double x0, double y0,

                                          final DCurve c,

                                          final double x2, final double y2)

    {

        int count = 1; // dt = 1 / count

        // maximum(ddX|Y) = norm(dbx, dby) * dt^2 (= 1)

        double maxDD = Math.abs(c.dbx) + Math.abs(c.dby);

        final double _DEC_BND = QUAD_DEC_BND;

        while (maxDD >= _DEC_BND) {

            // divide step by half:

            maxDD /= 4.0d; // error divided by 2^2 = 4

            count <<= 1;

            if (DO_STATS) {

                rdrCtx.stats.stat_rdr_quadBreak_dec.add(count);

            }

        }

        int nL = 0; // line count

        if (count > 1) {

            final double icount = 1.0d / count; // dt

            final double icount2 = icount * icount; // dt^2

            final double ddx = c.dbx * icount2;

            final double ddy = c.dby * icount2;

            double dx = c.bx * icount2 + c.cx * icount;

            double dy = c.by * icount2 + c.cy * icount;

            double x1, y1;

            while (--count > 0) {

                x1 = x0 + dx;

                dx += ddx;

                y1 = y0 + dy;

                dy += ddy;

                addLine(x0, y0, x1, y1);

                if (DO_STATS) { nL++; }

                x0 = x1;

                y0 = y1;

            }

        }

        addLine(x0, y0, x2, y2);

        if (DO_STATS) {

            rdrCtx.stats.stat_rdr_quadBreak.add(nL + 1);

        }

    }

    // x0, y0 and x3,y3 are the endpoints of the curve. We could compute these

    // using c.xat(0),c.yat(0) and c.xat(1),c.yat(1), but this might introduce

    // numerical errors, and our callers already have the exact values.

    // Another alternative would be to pass all the control points, and call

    // c.set here, but then too many numbers are passed around.

    private void curveBreakIntoLinesAndAdd(double x0, double y0,

                                           final DCurve c,

                                           final double x3, final double y3)

    {

        int count           = CUB_COUNT;

        final double icount  = CUB_INV_COUNT;   // dt

        final double icount2 = CUB_INV_COUNT_2; // dt^2

        final double icount3 = CUB_INV_COUNT_3; // dt^3

        // the dx and dy refer to forward differencing variables, not the last

        // coefficients of the "points" polynomial

        double dddx, dddy, ddx, ddy, dx, dy;

        dddx = 2.0d * c.dax * icount3;

        dddy = 2.0d * c.day * icount3;

        ddx = dddx + c.dbx * icount2;

        ddy = dddy + c.dby * icount2;

        dx = c.ax * icount3 + c.bx * icount2 + c.cx * icount;

        dy = c.ay * icount3 + c.by * icount2 + c.cy * icount;

        // we use x0, y0 to walk the line

        double x1 = x0, y1 = y0;

        int nL = 0; // line count

        final double _DEC_BND = CUB_DEC_BND;

        final double _INC_BND = CUB_INC_BND;

        while (count > 0) {

            // divide step by half:

            while (Math.abs(ddx) + Math.abs(ddy) >= _DEC_BND) {

                dddx /= 8.0d;

                dddy /= 8.0d;

                ddx = ddx / 4.0d - dddx;

                ddy = ddy / 4.0d - dddy;

                dx = (dx - ddx) / 2.0d;

                dy = (dy - ddy) / 2.0d;

                count <<= 1;

                if (DO_STATS) {

                    rdrCtx.stats.stat_rdr_curveBreak_dec.add(count);

                }

            }

            // double step:

            // can only do this on even "count" values, because we must divide count by 2

            while (count % 2 == 0

                   && Math.abs(dx) + Math.abs(dy) <= _INC_BND)

            {

                dx = 2.0d * dx + ddx;

                dy = 2.0d * dy + ddy;

                ddx = 4.0d * (ddx + dddx);

                ddy = 4.0d * (ddy + dddy);

                dddx *= 8.0d;

                dddy *= 8.0d;

                count >>= 1;

                if (DO_STATS) {

                    rdrCtx.stats.stat_rdr_curveBreak_inc.add(count);

                }

            }

            if (--count > 0) {

                x1 += dx;

                dx += ddx;

                ddx += dddx;

                y1 += dy;

                dy += ddy;

                ddy += dddy;

            } else {

                x1 = x3;

                y1 = y3;

            }

            addLine(x0, y0, x1, y1);

            if (DO_STATS) { nL++; }

            x0 = x1;

            y0 = y1;

        }

        if (DO_STATS) {

            rdrCtx.stats.stat_rdr_curveBreak.add(nL);

        }

    }

    private void addLine(double x1, double y1, double x2, double y2) {

        if (DO_MONITORS) {

            rdrCtx.stats.mon_rdr_addLine.start();

        }

        if (DO_STATS) {

            rdrCtx.stats.stat_rdr_addLine.add(1);

        }

        int or = 1; // orientation of the line. 1 if y increases, 0 otherwise.

        if (y2 < y1) {

            or = 0;

            double tmp = y2;

            y2 = y1;

            y1 = tmp;

            tmp = x2;

            x2 = x1;

            x1 = tmp;

        }

        // convert subpixel coordinates [double] into pixel positions [int]

        // The index of the pixel that holds the next HPC is at ceil(trueY - 0.5)

        // Since y1 and y2 are biased by -0.5 in tosubpixy(), this is simply

        // ceil(y1) or ceil(y2)

        // upper integer (inclusive)

        final int firstCrossing = FloatMath.max(FloatMath.ceil_int(y1), boundsMinY);

        // note: use boundsMaxY (last Y exclusive) to compute correct coverage

        // upper integer (exclusive)

        final int lastCrossing  = FloatMath.min(FloatMath.ceil_int(y2), boundsMaxY);

        /* skip horizontal lines in pixel space and clip edges

           out of y range [boundsMinY; boundsMaxY] */

        if (firstCrossing >= lastCrossing) {

            if (DO_MONITORS) {

                rdrCtx.stats.mon_rdr_addLine.stop();

            }

            if (DO_STATS) {

                rdrCtx.stats.stat_rdr_addLine_skip.add(1);

            }

            return;

        }

        // edge min/max X/Y are in subpixel space (half-open interval):

        // note: Use integer crossings to ensure consistent range within

        // edgeBuckets / edgeBucketCounts arrays in case of NaN values (int = 0)

        if (firstCrossing < edgeMinY) {

            edgeMinY = firstCrossing;

        }

        if (lastCrossing > edgeMaxY) {

            edgeMaxY = lastCrossing;

        }

        final double slope = (x1 - x2) / (y1 - y2);

        if (slope >= 0.0d) { // <==> x1 < x2

            if (x1 < edgeMinX) {

                edgeMinX = x1;

            }

            if (x2 > edgeMaxX) {

                edgeMaxX = x2;

            }

        } else {

            if (x2 < edgeMinX) {

                edgeMinX = x2;

            }

            if (x1 > edgeMaxX) {

                edgeMaxX = x1;

            }

        }

        // local variables for performance:

        final int _SIZEOF_EDGE_BYTES = SIZEOF_EDGE_BYTES;

        final OffHeapArray _edges = edges;

        // get free pointer (ie length in bytes)

        final int edgePtr = _edges.used;

        // use substraction to avoid integer overflow:

        if (_edges.length - edgePtr < _SIZEOF_EDGE_BYTES) {

            // suppose _edges.length > _SIZEOF_EDGE_BYTES

            // so doubling size is enough to add needed bytes

            // note: throw IOOB if neededSize > 2Gb:

            final long edgeNewSize = ArrayCacheConst.getNewLargeSize(

                                        _edges.length,

                                        edgePtr + _SIZEOF_EDGE_BYTES);

            if (DO_STATS) {

                rdrCtx.stats.stat_rdr_edges_resizes.add(edgeNewSize);

            }

            _edges.resize(edgeNewSize);

        }

        final Unsafe _unsafe = OffHeapArray.UNSAFE;

        final long SIZE_INT = 4L;

        long addr   = _edges.address + edgePtr;

        // The x value must be bumped up to its position at the next HPC we will evaluate.

        // "firstcrossing" is the (sub)pixel number where the next crossing occurs

        // thus, the actual coordinate of the next HPC is "firstcrossing + 0.5"

        // so the Y distance we cover is "firstcrossing + 0.5 - trueY".

        // Note that since y1 (and y2) are already biased by -0.5 in tosubpixy(), we have

        // y1 = trueY - 0.5

        // trueY = y1 + 0.5

        // firstcrossing + 0.5 - trueY = firstcrossing + 0.5 - (y1 + 0.5)

        //                             = firstcrossing - y1

        // The x coordinate at that HPC is then:

        // x1_intercept = x1 + (firstcrossing - y1) * slope

        // The next VPC is then given by:

        // VPC index = ceil(x1_intercept - 0.5), or alternately

        // VPC index = floor(x1_intercept - 0.5 + 1 - epsilon)

        // epsilon is hard to pin down in floating point, but easy in fixed point, so if

        // we convert to fixed point then these operations get easier:

        // long x1_fixed = x1_intercept * 2^32;  (fixed point 32.32 format)

        // curx = next VPC = fixed_floor(x1_fixed - 2^31 + 2^32 - 1)

        //                 = fixed_floor(x1_fixed + 2^31 - 1)

        //                 = fixed_floor(x1_fixed + 0x7FFFFFFF)

        // and error       = fixed_fract(x1_fixed + 0x7FFFFFFF)

        final double x1_intercept = x1 + (firstCrossing - y1) * slope;

        // inlined scalb(x1_intercept, 32):

        final long x1_fixed_biased = ((long) (POWER_2_TO_32 * x1_intercept))

                                     + 0x7FFFFFFFL;

        // curx:

        // last bit corresponds to the orientation

        _unsafe.putInt(addr, (((int) (x1_fixed_biased >> 31L)) & ALL_BUT_LSB) | or);

        addr += SIZE_INT;

        _unsafe.putInt(addr,  ((int)  x1_fixed_biased) >>> 1);

        addr += SIZE_INT;

        // inlined scalb(slope, 32):

        final long slope_fixed = (long) (POWER_2_TO_32 * slope);

        // last bit set to 0 to keep orientation:

        _unsafe.putInt(addr, (((int) (slope_fixed >> 31L)) & ALL_BUT_LSB));

        addr += SIZE_INT;

        _unsafe.putInt(addr,  ((int)  slope_fixed) >>> 1);

        addr += SIZE_INT;

        final int[] _edgeBuckets      = edgeBuckets;

        final int[] _edgeBucketCounts = edgeBucketCounts;

        final int _boundsMinY = boundsMinY;

        // each bucket is a linked list. this method adds ptr to the

        // start of the "bucket"th linked list.

        final int bucketIdx = firstCrossing - _boundsMinY;

        // pointer from bucket

        _unsafe.putInt(addr, _edgeBuckets[bucketIdx]);

        addr += SIZE_INT;

        // y max (exclusive)

        _unsafe.putInt(addr,  lastCrossing);

        // Update buckets:

        // directly the edge struct "pointer"

        _edgeBuckets[bucketIdx]       = edgePtr;

        _edgeBucketCounts[bucketIdx] += 2; // 1 << 1

        // last bit means edge end

        _edgeBucketCounts[lastCrossing - _boundsMinY] |= 0x1;

        // update free pointer (ie length in bytes)

        _edges.used += _SIZEOF_EDGE_BYTES;

        if (DO_MONITORS) {

            rdrCtx.stats.mon_rdr_addLine.stop();

        }

    }

// END EDGE LIST

//////////////////////////////////////////////////////////////////////////////

    // Cache to store RLE-encoded coverage mask of the current primitive

    final MarlinCache cache;

    // Bounds of the drawing region, at subpixel precision.

    private int boundsMinX, boundsMinY, boundsMaxX, boundsMaxY;

    // Current winding rule

    private int windingRule;

    // Current drawing position, i.e., final point of last segment

    private double x0, y0;

    // Position of most recent 'moveTo' command

    private double sx0, sy0;

    // per-thread renderer context

    final DRendererContext rdrCtx;

    // dirty curve

    private final DCurve curve;

    // clean alpha array (zero filled)

    private int[] alphaLine;

    // alphaLine ref (clean)

    private final IntArrayCache.Reference alphaLine_ref;

    private boolean enableBlkFlags = false;

    private boolean prevUseBlkFlags = false;

    /* block flags (0|1) */

    private int[] blkFlags;

    // blkFlags ref (clean)

    private final IntArrayCache.Reference blkFlags_ref;

    DRenderer(final DRendererContext rdrCtx) {

        this.rdrCtx = rdrCtx;

        this.edges = rdrCtx.newOffHeapArray(INITIAL_EDGES_CAPACITY); // 96K

        this.curve = rdrCtx.curve;