/*

 * Copyright (c) 2000, 2001, 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.

 */

#include "GraphicsPrimitiveMgr.h"

#include "LineUtils.h"

#include "sun_java2d_loops_DrawLine.h"

#define OUTCODE_TOP     1

#define OUTCODE_BOTTOM  2

#define OUTCODE_LEFT    4

#define OUTCODE_RIGHT   8

static void

RefineBounds(SurfaceDataBounds *bounds, jint x1, jint y1, jint x2, jint y2)

{

    jint min, max;

    if (x1 < x2) {

        min = x1;

        max = x2;

    } else {

        min = x2;

        max = x1;

    }

    max++;

    if (max <= min) {

        /* integer overflow */

        max--;

    }

    if (bounds->x1 < min) bounds->x1 = min;

    if (bounds->x2 > max) bounds->x2 = max;

    if (y1 < y2) {

        min = y1;

        max = y2;

    } else {

        min = y2;

        max = y1;

    }

    max++;

    if (max <= min) {

        /* integer overflow */

        max--;

    }

    if (bounds->y1 < min) bounds->y1 = min;

    if (bounds->y2 > max) bounds->y2 = max;

}

#define _out(v, vmin, vmax, cmin, cmax) \

    ((v < vmin) ? cmin : ((v > vmax) ? cmax : 0))

#define outcode(x, y, xmin, ymin, xmax, ymax) \

    (_out(y, ymin, ymax, OUTCODE_TOP, OUTCODE_BOTTOM) | \

     _out(x, xmin, xmax, OUTCODE_LEFT, OUTCODE_RIGHT))

/*

 * "Small" math here will be done if the coordinates are less

 * than 15 bits in range (-16384 => 16383).  This could be

 * expanded to 16 bits if we rearrange some of the math in

 * the normal version of SetupBresenham.

 * "Big" math here will be done with coordinates with 30 bits

 * of total range - 2 bits less than a jint holds.

 * Intermediate calculations for "Big" coordinates will be

 * done using jlong variables.

 */

#define OverflowsSmall(v)       ((v) != (((v) << 17) >> 17))

#define OverflowsBig(v)         ((v) != (((v) << 2) >> 2))

#define BIG_MAX                 ((1 << 29) - 1)

#define BIG_MIN                 (-(1 << 29))

#define SETUP_BRESENHAM(CALC_TYPE, ORIGX1, ORIGY1, ORIGX2, ORIGY2, SHORTEN) \

do { \

    jint X1 = ORIGX1, Y1 = ORIGY1, X2 = ORIGX2, Y2 = ORIGY2; \

    jint dx, dy, ax, ay; \

    jint cxmin, cymin, cxmax, cymax; \

    jint outcode1, outcode2; \

    jboolean xmajor; \

    jint errminor, errmajor; \

    jint error; \

    jint steps; \

 \

    dx = X2 - X1; \

    dy = Y2 - Y1; \

    ax = (dx < 0) ? -dx : dx; \

    ay = (dy < 0) ? -dy : dy; \

 \

    cxmin = pBounds->x1; \

    cymin = pBounds->y1; \

    cxmax = pBounds->x2 - 1; \

    cymax = pBounds->y2 - 1; \

    xmajor = (ax >= ay); \

 \

    outcode1 = outcode(X1, Y1, cxmin, cymin, cxmax, cymax); \

    outcode2 = outcode(X2, Y2, cxmin, cymin, cxmax, cymax); \

    while ((outcode1 | outcode2) != 0) { \

        CALC_TYPE xsteps, ysteps; \

        if ((outcode1 & outcode2) != 0) { \

            return JNI_FALSE; \

        } \

        if (outcode1 != 0) { \

            if (outcode1 & (OUTCODE_TOP | OUTCODE_BOTTOM)) { \

                if (outcode1 & OUTCODE_TOP) { \

                    Y1 = cymin; \

                } else { \

                    Y1 = cymax; \

                } \

                ysteps = Y1 - ORIGY1; \

                if (ysteps < 0) { \

                    ysteps = -ysteps; \

                } \

                xsteps = 2 * ysteps * ax + ay; \

                if (xmajor) { \

                    xsteps += ay - ax - 1; \

                } \

                xsteps = xsteps / (2 * ay); \

                if (dx < 0) { \

                    xsteps = -xsteps; \

                } \

                X1 = ORIGX1 + (jint) xsteps; \

            } else if (outcode1 & (OUTCODE_LEFT | OUTCODE_RIGHT)) { \

                if (outcode1 & OUTCODE_LEFT) { \

                    X1 = cxmin; \

                } else { \

                    X1 = cxmax; \

                } \

                xsteps = X1 - ORIGX1; \

                if (xsteps < 0) { \

                    xsteps = -xsteps; \

                } \

                ysteps = 2 * xsteps * ay + ax; \

                if (!xmajor) { \

                    ysteps += ax - ay - 1; \

                } \

                ysteps = ysteps / (2 * ax); \

                if (dy < 0) { \

                    ysteps = -ysteps; \

                } \

                Y1 = ORIGY1 + (jint) ysteps; \

            } \

            outcode1 = outcode(X1, Y1, cxmin, cymin, cxmax, cymax); \

        } else { \

            if (outcode2 & (OUTCODE_TOP | OUTCODE_BOTTOM)) { \

                if (outcode2 & OUTCODE_TOP) { \

                    Y2 = cymin; \

                } else { \

                    Y2 = cymax; \

                } \

                ysteps = Y2 - ORIGY2; \

                if (ysteps < 0) { \

                    ysteps = -ysteps; \

                } \

                xsteps = 2 * ysteps * ax + ay; \

                if (xmajor) { \

                    xsteps += ay - ax; \

                } else { \

                    xsteps -= 1; \

                } \

                xsteps = xsteps / (2 * ay); \

                if (dx > 0) { \

                    xsteps = -xsteps; \

                } \

                X2 = ORIGX2 + (jint) xsteps; \

            } else if (outcode2 & (OUTCODE_LEFT | OUTCODE_RIGHT)) { \

                if (outcode2 & OUTCODE_LEFT) { \

                    X2 = cxmin; \

                } else { \

                    X2 = cxmax; \

                } \

                xsteps = X2 - ORIGX2; \

                if (xsteps < 0) { \

                    xsteps = -xsteps; \

                } \

                ysteps = 2 * xsteps * ay + ax; \

                if (xmajor) { \

                    ysteps -= 1; \

                } else { \

                    ysteps += ax - ay; \

                } \

                ysteps = ysteps / (2 * ax); \

                if (dy > 0) { \

                    ysteps = -ysteps; \

                } \

                Y2 = ORIGY2 + (jint) ysteps; \

            } \

            outcode2 = outcode(X2, Y2, cxmin, cymin, cxmax, cymax); \

        } \

    } \

    *pStartX = X1; \

    *pStartY = Y1; \

 \

    if (xmajor) { \

        errmajor = ay * 2; \

        errminor = ax * 2; \

        *pBumpMajorMask = (dx < 0) ? BUMP_NEG_PIXEL : BUMP_POS_PIXEL; \

        *pBumpMinorMask = (dy < 0) ? BUMP_NEG_SCAN : BUMP_POS_SCAN; \

        ax = -ax; /* For clipping adjustment below */ \

        steps = X2 - X1; \

        if (X2 != ORIGX2) { \

            SHORTEN = 0; \

        } \

    } else { \

        errmajor = ax * 2; \

        errminor = ay * 2; \

        *pBumpMajorMask = (dy < 0) ? BUMP_NEG_SCAN : BUMP_POS_SCAN; \

        *pBumpMinorMask = (dx < 0) ? BUMP_NEG_PIXEL : BUMP_POS_PIXEL; \

        ay = -ay; /* For clipping adjustment below */ \

        steps = Y2 - Y1; \

        if (Y2 != ORIGY2) { \

            SHORTEN = 0; \

        } \

    } \

    if ((steps = ((steps >= 0) ? steps : -steps) + 1 - SHORTEN) == 0) { \

        return JNI_FALSE; \

    } \

    error = - (errminor / 2); \

    if (Y1 != ORIGY1) { \

        jint ysteps = Y1 - ORIGY1; \

        if (ysteps < 0) { \

            ysteps = -ysteps; \

        } \

        error += ysteps * ax * 2; \

    } \

    if (X1 != ORIGX1) { \

        jint xsteps = X1 - ORIGX1; \

        if (xsteps < 0) { \

            xsteps = -xsteps; \

        } \

        error += xsteps * ay * 2; \

    } \

    error += errmajor; \

    errminor -= errmajor; \

 \

    *pSteps = steps; \

    *pError = error; \

    *pErrMajor = errmajor; \

    *pErrMinor = errminor; \

} while (0)

static jboolean

LineUtils_SetupBresenhamBig(jint _x1, jint _y1, jint _x2, jint _y2,

                            jint shorten,

                            SurfaceDataBounds *pBounds,

                            jint *pStartX, jint *pStartY,

                            jint *pSteps, jint *pError,

                            jint *pErrMajor, jint *pBumpMajorMask,

                            jint *pErrMinor, jint *pBumpMinorMask)

{

    /*

     * Part of calculating the Bresenham parameters for line stepping

     * involves being able to store numbers that are twice the magnitude

     * of the biggest absolute difference in coordinates.  Since we

     * want the stepping parameters to be stored in jints, we then need

     * to avoid any absolute differences more than 30 bits.  Thus, we

     * need to preprocess the coordinates to reduce their range to 30

     * bits regardless of clipping.  We need to cut their range back

     * before we do the clipping because the Bresenham stepping values

     * need to be calculated based on the "unclipped" coordinates.

     *

     * Thus, first we perform a "pre-clipping" stage to bring the

     * coordinates within the 30-bit range and then we proceed to the

     * regular clipping procedure, pretending that these were the

     * original coordinates all along.  Since this operation occurs

     * based on a constant "pre-clip" rectangle of +/- 30 bits without

     * any consideration for the final clip, the rounding errors that

     * occur here will depend only on the line coordinates and be

     * invariant with respect to the particular device/user clip

     * rectangles in effect at the time.  Thus, rendering a given

     * large-range line will be consistent under a variety of

     * clipping conditions.

     */

    if (OverflowsBig(_x1) || OverflowsBig(_y1) ||

        OverflowsBig(_x2) || OverflowsBig(_y2))

    {

        /*

         * Use doubles to get us into range for "Big" arithmetic.

         *

         * The math of adjusting an endpoint for clipping can involve

         * an intermediate result with twice the number of bits as the

         * original coordinate range.  Since we want to maintain as

         * much as 30 bits of precision in the resulting coordinates,

         * we will get roundoff here even using IEEE double-precision

         * arithmetic which cannot carry 60 bits of mantissa.  Since

         * the rounding errors will be consistent for a given set

         * of input coordinates the potential roundoff error should

         * not affect the consistency of our rendering.

         */

        double X1d = _x1;

        double Y1d = _y1;

        double X2d = _x2;

        double Y2d = _y2;

        double DXd = X2d - X1d;

        double DYd = Y2d - Y1d;

        if (_x1 < BIG_MIN) {

            Y1d = _y1 + (BIG_MIN - _x1) * DYd / DXd;

            X1d = BIG_MIN;

        } else if (_x1 > BIG_MAX) {

            Y1d = _y1 - (_x1 - BIG_MAX) * DYd / DXd;

            X1d = BIG_MAX;

        }

        /* Use Y1d instead of _y1 for testing now as we may have modified it */

        if (Y1d < BIG_MIN) {

            X1d = _x1 + (BIG_MIN - _y1) * DXd / DYd;

            Y1d = BIG_MIN;

        } else if (Y1d > BIG_MAX) {

            X1d = _x1 - (_y1 - BIG_MAX) * DXd / DYd;

            Y1d = BIG_MAX;

        }

        if (_x2 < BIG_MIN) {

            Y2d = _y2 + (BIG_MIN - _x2) * DYd / DXd;

            X2d = BIG_MIN;

        } else if (_x2 > BIG_MAX) {

            Y2d = _y2 - (_x2 - BIG_MAX) * DYd / DXd;

            X2d = BIG_MAX;

        }

        /* Use Y2d instead of _y2 for testing now as we may have modified it */

        if (Y2d < BIG_MIN) {

            X2d = _x2 + (BIG_MIN - _y2) * DXd / DYd;

            Y2d = BIG_MIN;

        } else if (Y2d > BIG_MAX) {

            X2d = _x2 - (_y2 - BIG_MAX) * DXd / DYd;

            Y2d = BIG_MAX;

        }

        _x1 = (int) X1d;

        _y1 = (int) Y1d;

        _x2 = (int) X2d;

        _y2 = (int) Y2d;

    }

    SETUP_BRESENHAM(jlong, _x1, _y1, _x2, _y2, shorten);

    return JNI_TRUE;

}

jboolean

LineUtils_SetupBresenham(jint _x1, jint _y1, jint _x2, jint _y2,

                         jint shorten,

                         SurfaceDataBounds *pBounds,

                         jint *pStartX, jint *pStartY,

                         jint *pSteps, jint *pError,

                         jint *pErrMajor, jint *pBumpMajorMask,

                         jint *pErrMinor, jint *pBumpMinorMask)

{

    if (OverflowsSmall(_x1) || OverflowsSmall(_y1) ||

        OverflowsSmall(_x2) || OverflowsSmall(_y2))

    {

        return LineUtils_SetupBresenhamBig(_x1, _y1, _x2, _y2, shorten,

                                           pBounds,

                                           pStartX, pStartY,

                                           pSteps, pError,

                                           pErrMajor, pBumpMajorMask,

                                           pErrMinor, pBumpMinorMask);

    }

    SETUP_BRESENHAM(jint, _x1, _y1, _x2, _y2, shorten);

    return JNI_TRUE;

}

/*

 * Class:     sun_java2d_loops_DrawLine

 * Method:    DrawLine

 * Signature: (Lsun/java2d/SunGraphics2D;Lsun/java2d/SurfaceData;IIII)V

 */

JNIEXPORT void JNICALL

Java_sun_java2d_loops_DrawLine_DrawLine

    (JNIEnv *env, jobject self,

     jobject sg2d, jobject sData,

     jint x1, jint y1, jint x2, jint y2)

{

    SurfaceDataOps *sdOps;

    SurfaceDataRasInfo rasInfo;

    NativePrimitive *pPrim;

    CompositeInfo compInfo;

    jint pixel = GrPrim_Sg2dGetPixel(env, sg2d);

    pPrim = GetNativePrim(env, self);

    if (pPrim == NULL) {

        return;

    }

    if (pPrim->pCompType->getCompInfo != NULL) {

        GrPrim_Sg2dGetCompInfo(env, sg2d, pPrim, &compInfo);

    }

    sdOps = SurfaceData_GetOps(env, sData);

    if (sdOps == 0) {

        return;

    }

    GrPrim_Sg2dGetClip(env, sg2d, &rasInfo.bounds);

    RefineBounds(&rasInfo.bounds, x1, y1, x2, y2);

    if (sdOps->Lock(env, sdOps, &rasInfo, pPrim->dstflags) != SD_SUCCESS) {

        return;

    }

    if (rasInfo.bounds.x2 > rasInfo.bounds.x1 &&

        rasInfo.bounds.y2 > rasInfo.bounds.y1)

    {

        sdOps->GetRasInfo(env, sdOps, &rasInfo);

        if (rasInfo.rasBase) {

            LineUtils_ProcessLine(&rasInfo, pixel,

                                  pPrim->funcs.drawline, pPrim, &compInfo,

                                  x1, y1, x2, y2, 0);

        }

        SurfaceData_InvokeRelease(env, sdOps, &rasInfo);

    }

    SurfaceData_InvokeUnlock(env, sdOps, &rasInfo);

}