/*

 * Copyright (c) 2007, 2016, 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 java.util.Arrays;

import sun.awt.geom.PathConsumer2D;

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

import jdk.internal.misc.Unsafe;

final class Renderer implements PathConsumer2D, MarlinConst {

    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.0p32;

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

    public static final float f_SUBPIXEL_POSITIONS_X

        = (float) SUBPIXEL_POSITIONS_X;

    public static final float f_SUBPIXEL_POSITIONS_Y

        = (float) SUBPIXEL_POSITIONS_Y;

    public static final int SUBPIXEL_MASK_X = SUBPIXEL_POSITIONS_X - 1;

    public 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_SIZE << SUBPIXEL_LG_POSITIONS_Y;

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

    static final int INITIAL_BUCKET_ARRAY

        = INITIAL_PIXEL_DIM * SUBPIXEL_POSITIONS_Y;

    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 float CUB_DEC_ERR_SUBPIX

        = 2.5f * (NORM_SUBPIXELS / 8f); // 2.5 subpixel for typical 8x8 subpixels

    // cubic error in subpixels to increment step

    private static final float CUB_INC_ERR_SUBPIX

        = 1f * (NORM_SUBPIXELS / 8f); // 1 subpixel for typical 8x8 subpixels

    // cubic bind length to decrement step = 8 * error in subpixels

    // pisces: 20 / 8

    // openjfx pisces: 8 / 3.2

    // multiply by 8 = error scale factor:

    public static final float CUB_DEC_BND

        = 8f * CUB_DEC_ERR_SUBPIX; // 20f means 2.5 subpixel error

    // cubic bind length to increment step = 8 * error in subpixels

    public static final float CUB_INC_BND

        = 8f * CUB_INC_ERR_SUBPIX; // 8f means 1 subpixel error

    // 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 float CUB_INV_COUNT = 1f / CUB_COUNT;

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

    private static final float CUB_INV_COUNT_2 = 1f / CUB_COUNT_2;

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

    private static final float CUB_INV_COUNT_3 = 1f / CUB_COUNT_3;

    // quad break into lines

    // quadratic error in subpixels

    private static final float QUAD_DEC_ERR_SUBPIX

        = 1f * (NORM_SUBPIXELS / 8f); // 1 subpixel for typical 8x8 subpixels

    // quadratic bind length to decrement step = 8 * error in subpixels

    // pisces and openjfx pisces: 32

    public static final float QUAD_DEC_BND

        = 8f * QUAD_DEC_ERR_SUBPIX; // 8f means 1 subpixel error

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

//  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;

    // per-thread initial arrays (large enough to satisfy most usages) (1024)

    private final int[] crossings_initial = new int[INITIAL_SMALL_ARRAY]; // 4K

    // +1 to avoid recycling in Helpers.widenArray()

    private final int[] edgePtrs_initial  = new int[INITIAL_SMALL_ARRAY + 1]; // 4K

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

    private final int[] aux_crossings_initial = new int[INITIAL_SMALL_ARRAY]; // 4K

    // +1 to avoid recycling in Helpers.widenArray()

    private final int[] aux_edgePtrs_initial  = new int[INITIAL_SMALL_ARRAY + 1]; // 4K

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

//  EDGE LIST

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

    private int edgeMinY = Integer.MAX_VALUE;

    private int edgeMaxY = Integer.MIN_VALUE;

    private float edgeMinX = Float.POSITIVE_INFINITY;

    private float edgeMaxX = Float.NEGATIVE_INFINITY;

    // edges [floats|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;

    // sum of each edge delta Y (subpixels)

    private int edgeSumDeltaY;

    // +1 to avoid recycling in Helpers.widenArray()

    private final int[] edgeBuckets_initial

        = new int[INITIAL_BUCKET_ARRAY + 1]; // 64K

    private final int[] edgeBucketCounts_initial

        = new int[INITIAL_BUCKET_ARRAY + 1]; // 64K

    // 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(float x0, float y0,

                                          final Curve c,

                                          final float x2, final float y2)

    {

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

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

        float maxDD = FloatMath.max(Math.abs(c.dbx), Math.abs(c.dby));

        final float _DEC_BND = QUAD_DEC_BND;

        while (maxDD >= _DEC_BND) {

            // divide step by half:

            maxDD /= 4f; // error divided by 2^2 = 4

            count <<= 1;

            }

        }

        int nL = 0; // line count

        if (count > 1) {

            final float icount = 1f / count; // dt

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

            final float ddx = c.dbx * icount2;

            final float ddy = c.dby * icount2;

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

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

            float x1, y1;

            while (--count > 0) {

                x1 = x0 + dx;

                dx += ddx;

                y1 = y0 + dy;

                dy += ddy;

                addLine(x0, y0, x1, y1);

                x0 = x1;

                y0 = y1;

            }

        }

        addLine(x0, y0, x2, y2);

        }

    }

    // 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(float x0, float y0,

                                           final Curve c,

                                           final float x3, final float y3)

    {

        int count           = CUB_COUNT;

        final float icount  = CUB_INV_COUNT;   // dt

        final float icount2 = CUB_INV_COUNT_2; // dt^2

        final float icount3 = CUB_INV_COUNT_3; // dt^3

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

        // coefficients of the "points" polynomial

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

        dddx = 2f * c.dax * icount3;

        dddy = 2f * 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

        float x1 = x0, y1 = y0;

        int nL = 0; // line count

        final float _DEC_BND = CUB_DEC_BND;

        final float _INC_BND = CUB_INC_BND;

        while (count > 0) {

            // divide step by half:

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

                dddx /= 8f;

                dddy /= 8f;

                ddx = ddx/4f - dddx;

                ddy = ddy/4f - dddy;

                dx = (dx - ddx) / 2f;

                dy = (dy - ddy) / 2f;

                count <<= 1;

                }

            }

            // double step:

            // TODO: why use first derivative dX|Y instead of second ddX|Y ?

            // both scale changes should use speed or acceleration to have the same metric.

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

            while (count % 2 == 0

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

            {

                dx = 2f * dx + ddx;

                dy = 2f * dy + ddy;

                ddx = 4f * (ddx + dddx);

                ddy = 4f * (ddy + dddy);

                dddx *= 8f;

                dddy *= 8f;

                count >>= 1;

                }

            }

            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);

            x0 = x1;

            y0 = y1;

        }

        }

    }

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

        }

        }

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

        if (y2 < y1) {

            or = 0;

            float tmp = y2;

            y2 = y1;

            y1 = tmp;

            tmp = x2;

            x2 = x1;

            x1 = tmp;

        }

        // convert subpixel coordinates (float) 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) {

            }

            }

            return;

        }

        // edge min/max X/Y are in subpixel space (inclusive) within bounds:

        // 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;

        }

        // Use double-precision for improved accuracy:

        final double x1d   = x1;

        final double y1d   = y1;

        final double slope = (x1d - x2) / (y1d - y2);

        if (slope >= 0.0) { // <==> 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 = ArrayCache.getNewLargeSize(_edges.length,

                                        edgePtr + _SIZEOF_EDGE_BYTES);

            }

            _edges.resize(edgeNewSize);

        }

        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 = x1d + (firstCrossing - y1d) * 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 (inclusive)

        _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 sum of delta Y (subpixels):

        edgeSumDeltaY += (lastCrossing - firstCrossing);

        // update free pointer (ie length in bytes)

        _edges.used += _SIZEOF_EDGE_BYTES;

        }

    }

// 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 float x0, y0;

    // Position of most recent 'moveTo' command

    private float sx0, sy0;

    // per-thread renderer context

    final RendererContext rdrCtx;

    // dirty curve

    private final Curve curve;

    Renderer(final RendererContext rdrCtx) {

        this.rdrCtx = rdrCtx;

        this.edges = new OffHeapArray(rdrCtx.cleanerObj, INITIAL_EDGES_CAPACITY); // 96K

        this.curve = rdrCtx.curve;