1/*
2 * Copyright (c) 2000, 2001, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.  Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26#include "GraphicsPrimitiveMgr.h"
27
28#include "LineUtils.h"
29
30#include "sun_java2d_loops_DrawLine.h"
31
32#define OUTCODE_TOP     1
33#define OUTCODE_BOTTOM  2
34#define OUTCODE_LEFT    4
35#define OUTCODE_RIGHT   8
36
37static void
38RefineBounds(SurfaceDataBounds *bounds, jint x1, jint y1, jint x2, jint y2)
39{
40    jint min, max;
41    if (x1 < x2) {
42        min = x1;
43        max = x2;
44    } else {
45        min = x2;
46        max = x1;
47    }
48    max++;
49    if (max <= min) {
50        /* integer overflow */
51        max--;
52    }
53    if (bounds->x1 < min) bounds->x1 = min;
54    if (bounds->x2 > max) bounds->x2 = max;
55    if (y1 < y2) {
56        min = y1;
57        max = y2;
58    } else {
59        min = y2;
60        max = y1;
61    }
62    max++;
63    if (max <= min) {
64        /* integer overflow */
65        max--;
66    }
67    if (bounds->y1 < min) bounds->y1 = min;
68    if (bounds->y2 > max) bounds->y2 = max;
69}
70
71#define _out(v, vmin, vmax, cmin, cmax) \
72    ((v < vmin) ? cmin : ((v > vmax) ? cmax : 0))
73
74#define outcode(x, y, xmin, ymin, xmax, ymax) \
75    (_out(y, ymin, ymax, OUTCODE_TOP, OUTCODE_BOTTOM) | \
76     _out(x, xmin, xmax, OUTCODE_LEFT, OUTCODE_RIGHT))
77
78/*
79 * "Small" math here will be done if the coordinates are less
80 * than 15 bits in range (-16384 => 16383).  This could be
81 * expanded to 16 bits if we rearrange some of the math in
82 * the normal version of SetupBresenham.
83 * "Big" math here will be done with coordinates with 30 bits
84 * of total range - 2 bits less than a jint holds.
85 * Intermediate calculations for "Big" coordinates will be
86 * done using jlong variables.
87 */
88#define OverflowsSmall(v)       ((v) != (((v) << 17) >> 17))
89#define OverflowsBig(v)         ((v) != (((v) << 2) >> 2))
90#define BIG_MAX                 ((1 << 29) - 1)
91#define BIG_MIN                 (-(1 << 29))
92
93#define SETUP_BRESENHAM(CALC_TYPE, ORIGX1, ORIGY1, ORIGX2, ORIGY2, SHORTEN) \
94do { \
95    jint X1 = ORIGX1, Y1 = ORIGY1, X2 = ORIGX2, Y2 = ORIGY2; \
96    jint dx, dy, ax, ay; \
97    jint cxmin, cymin, cxmax, cymax; \
98    jint outcode1, outcode2; \
99    jboolean xmajor; \
100    jint errminor, errmajor; \
101    jint error; \
102    jint steps; \
103 \
104    dx = X2 - X1; \
105    dy = Y2 - Y1; \
106    ax = (dx < 0) ? -dx : dx; \
107    ay = (dy < 0) ? -dy : dy; \
108 \
109    cxmin = pBounds->x1; \
110    cymin = pBounds->y1; \
111    cxmax = pBounds->x2 - 1; \
112    cymax = pBounds->y2 - 1; \
113    xmajor = (ax >= ay); \
114 \
115    outcode1 = outcode(X1, Y1, cxmin, cymin, cxmax, cymax); \
116    outcode2 = outcode(X2, Y2, cxmin, cymin, cxmax, cymax); \
117    while ((outcode1 | outcode2) != 0) { \
118        CALC_TYPE xsteps, ysteps; \
119        if ((outcode1 & outcode2) != 0) { \
120            return JNI_FALSE; \
121        } \
122        if (outcode1 != 0) { \
123            if (outcode1 & (OUTCODE_TOP | OUTCODE_BOTTOM)) { \
124                if (outcode1 & OUTCODE_TOP) { \
125                    Y1 = cymin; \
126                } else { \
127                    Y1 = cymax; \
128                } \
129                ysteps = Y1 - ORIGY1; \
130                if (ysteps < 0) { \
131                    ysteps = -ysteps; \
132                } \
133                xsteps = 2 * ysteps * ax + ay; \
134                if (xmajor) { \
135                    xsteps += ay - ax - 1; \
136                } \
137                xsteps = xsteps / (2 * ay); \
138                if (dx < 0) { \
139                    xsteps = -xsteps; \
140                } \
141                X1 = ORIGX1 + (jint) xsteps; \
142            } else if (outcode1 & (OUTCODE_LEFT | OUTCODE_RIGHT)) { \
143                if (outcode1 & OUTCODE_LEFT) { \
144                    X1 = cxmin; \
145                } else { \
146                    X1 = cxmax; \
147                } \
148                xsteps = X1 - ORIGX1; \
149                if (xsteps < 0) { \
150                    xsteps = -xsteps; \
151                } \
152                ysteps = 2 * xsteps * ay + ax; \
153                if (!xmajor) { \
154                    ysteps += ax - ay - 1; \
155                } \
156                ysteps = ysteps / (2 * ax); \
157                if (dy < 0) { \
158                    ysteps = -ysteps; \
159                } \
160                Y1 = ORIGY1 + (jint) ysteps; \
161            } \
162            outcode1 = outcode(X1, Y1, cxmin, cymin, cxmax, cymax); \
163        } else { \
164            if (outcode2 & (OUTCODE_TOP | OUTCODE_BOTTOM)) { \
165                if (outcode2 & OUTCODE_TOP) { \
166                    Y2 = cymin; \
167                } else { \
168                    Y2 = cymax; \
169                } \
170                ysteps = Y2 - ORIGY2; \
171                if (ysteps < 0) { \
172                    ysteps = -ysteps; \
173                } \
174                xsteps = 2 * ysteps * ax + ay; \
175                if (xmajor) { \
176                    xsteps += ay - ax; \
177                } else { \
178                    xsteps -= 1; \
179                } \
180                xsteps = xsteps / (2 * ay); \
181                if (dx > 0) { \
182                    xsteps = -xsteps; \
183                } \
184                X2 = ORIGX2 + (jint) xsteps; \
185            } else if (outcode2 & (OUTCODE_LEFT | OUTCODE_RIGHT)) { \
186                if (outcode2 & OUTCODE_LEFT) { \
187                    X2 = cxmin; \
188                } else { \
189                    X2 = cxmax; \
190                } \
191                xsteps = X2 - ORIGX2; \
192                if (xsteps < 0) { \
193                    xsteps = -xsteps; \
194                } \
195                ysteps = 2 * xsteps * ay + ax; \
196                if (xmajor) { \
197                    ysteps -= 1; \
198                } else { \
199                    ysteps += ax - ay; \
200                } \
201                ysteps = ysteps / (2 * ax); \
202                if (dy > 0) { \
203                    ysteps = -ysteps; \
204                } \
205                Y2 = ORIGY2 + (jint) ysteps; \
206            } \
207            outcode2 = outcode(X2, Y2, cxmin, cymin, cxmax, cymax); \
208        } \
209    } \
210    *pStartX = X1; \
211    *pStartY = Y1; \
212 \
213    if (xmajor) { \
214        errmajor = ay * 2; \
215        errminor = ax * 2; \
216        *pBumpMajorMask = (dx < 0) ? BUMP_NEG_PIXEL : BUMP_POS_PIXEL; \
217        *pBumpMinorMask = (dy < 0) ? BUMP_NEG_SCAN : BUMP_POS_SCAN; \
218        ax = -ax; /* For clipping adjustment below */ \
219        steps = X2 - X1; \
220        if (X2 != ORIGX2) { \
221            SHORTEN = 0; \
222        } \
223    } else { \
224        errmajor = ax * 2; \
225        errminor = ay * 2; \
226        *pBumpMajorMask = (dy < 0) ? BUMP_NEG_SCAN : BUMP_POS_SCAN; \
227        *pBumpMinorMask = (dx < 0) ? BUMP_NEG_PIXEL : BUMP_POS_PIXEL; \
228        ay = -ay; /* For clipping adjustment below */ \
229        steps = Y2 - Y1; \
230        if (Y2 != ORIGY2) { \
231            SHORTEN = 0; \
232        } \
233    } \
234    if ((steps = ((steps >= 0) ? steps : -steps) + 1 - SHORTEN) == 0) { \
235        return JNI_FALSE; \
236    } \
237    error = - (errminor / 2); \
238    if (Y1 != ORIGY1) { \
239        jint ysteps = Y1 - ORIGY1; \
240        if (ysteps < 0) { \
241            ysteps = -ysteps; \
242        } \
243        error += ysteps * ax * 2; \
244    } \
245    if (X1 != ORIGX1) { \
246        jint xsteps = X1 - ORIGX1; \
247        if (xsteps < 0) { \
248            xsteps = -xsteps; \
249        } \
250        error += xsteps * ay * 2; \
251    } \
252    error += errmajor; \
253    errminor -= errmajor; \
254 \
255    *pSteps = steps; \
256    *pError = error; \
257    *pErrMajor = errmajor; \
258    *pErrMinor = errminor; \
259} while (0)
260
261static jboolean
262LineUtils_SetupBresenhamBig(jint _x1, jint _y1, jint _x2, jint _y2,
263                            jint shorten,
264                            SurfaceDataBounds *pBounds,
265                            jint *pStartX, jint *pStartY,
266                            jint *pSteps, jint *pError,
267                            jint *pErrMajor, jint *pBumpMajorMask,
268                            jint *pErrMinor, jint *pBumpMinorMask)
269{
270    /*
271     * Part of calculating the Bresenham parameters for line stepping
272     * involves being able to store numbers that are twice the magnitude
273     * of the biggest absolute difference in coordinates.  Since we
274     * want the stepping parameters to be stored in jints, we then need
275     * to avoid any absolute differences more than 30 bits.  Thus, we
276     * need to preprocess the coordinates to reduce their range to 30
277     * bits regardless of clipping.  We need to cut their range back
278     * before we do the clipping because the Bresenham stepping values
279     * need to be calculated based on the "unclipped" coordinates.
280     *
281     * Thus, first we perform a "pre-clipping" stage to bring the
282     * coordinates within the 30-bit range and then we proceed to the
283     * regular clipping procedure, pretending that these were the
284     * original coordinates all along.  Since this operation occurs
285     * based on a constant "pre-clip" rectangle of +/- 30 bits without
286     * any consideration for the final clip, the rounding errors that
287     * occur here will depend only on the line coordinates and be
288     * invariant with respect to the particular device/user clip
289     * rectangles in effect at the time.  Thus, rendering a given
290     * large-range line will be consistent under a variety of
291     * clipping conditions.
292     */
293    if (OverflowsBig(_x1) || OverflowsBig(_y1) ||
294        OverflowsBig(_x2) || OverflowsBig(_y2))
295    {
296        /*
297         * Use doubles to get us into range for "Big" arithmetic.
298         *
299         * The math of adjusting an endpoint for clipping can involve
300         * an intermediate result with twice the number of bits as the
301         * original coordinate range.  Since we want to maintain as
302         * much as 30 bits of precision in the resulting coordinates,
303         * we will get roundoff here even using IEEE double-precision
304         * arithmetic which cannot carry 60 bits of mantissa.  Since
305         * the rounding errors will be consistent for a given set
306         * of input coordinates the potential roundoff error should
307         * not affect the consistency of our rendering.
308         */
309        double X1d = _x1;
310        double Y1d = _y1;
311        double X2d = _x2;
312        double Y2d = _y2;
313        double DXd = X2d - X1d;
314        double DYd = Y2d - Y1d;
315        if (_x1 < BIG_MIN) {
316            Y1d = _y1 + (BIG_MIN - _x1) * DYd / DXd;
317            X1d = BIG_MIN;
318        } else if (_x1 > BIG_MAX) {
319            Y1d = _y1 - (_x1 - BIG_MAX) * DYd / DXd;
320            X1d = BIG_MAX;
321        }
322        /* Use Y1d instead of _y1 for testing now as we may have modified it */
323        if (Y1d < BIG_MIN) {
324            X1d = _x1 + (BIG_MIN - _y1) * DXd / DYd;
325            Y1d = BIG_MIN;
326        } else if (Y1d > BIG_MAX) {
327            X1d = _x1 - (_y1 - BIG_MAX) * DXd / DYd;
328            Y1d = BIG_MAX;
329        }
330        if (_x2 < BIG_MIN) {
331            Y2d = _y2 + (BIG_MIN - _x2) * DYd / DXd;
332            X2d = BIG_MIN;
333        } else if (_x2 > BIG_MAX) {
334            Y2d = _y2 - (_x2 - BIG_MAX) * DYd / DXd;
335            X2d = BIG_MAX;
336        }
337        /* Use Y2d instead of _y2 for testing now as we may have modified it */
338        if (Y2d < BIG_MIN) {
339            X2d = _x2 + (BIG_MIN - _y2) * DXd / DYd;
340            Y2d = BIG_MIN;
341        } else if (Y2d > BIG_MAX) {
342            X2d = _x2 - (_y2 - BIG_MAX) * DXd / DYd;
343            Y2d = BIG_MAX;
344        }
345        _x1 = (int) X1d;
346        _y1 = (int) Y1d;
347        _x2 = (int) X2d;
348        _y2 = (int) Y2d;
349    }
350
351    SETUP_BRESENHAM(jlong, _x1, _y1, _x2, _y2, shorten);
352
353    return JNI_TRUE;
354}
355
356jboolean
357LineUtils_SetupBresenham(jint _x1, jint _y1, jint _x2, jint _y2,
358                         jint shorten,
359                         SurfaceDataBounds *pBounds,
360                         jint *pStartX, jint *pStartY,
361                         jint *pSteps, jint *pError,
362                         jint *pErrMajor, jint *pBumpMajorMask,
363                         jint *pErrMinor, jint *pBumpMinorMask)
364{
365    if (OverflowsSmall(_x1) || OverflowsSmall(_y1) ||
366        OverflowsSmall(_x2) || OverflowsSmall(_y2))
367    {
368        return LineUtils_SetupBresenhamBig(_x1, _y1, _x2, _y2, shorten,
369                                           pBounds,
370                                           pStartX, pStartY,
371                                           pSteps, pError,
372                                           pErrMajor, pBumpMajorMask,
373                                           pErrMinor, pBumpMinorMask);
374    }
375
376    SETUP_BRESENHAM(jint, _x1, _y1, _x2, _y2, shorten);
377
378    return JNI_TRUE;
379}
380
381/*
382 * Class:     sun_java2d_loops_DrawLine
383 * Method:    DrawLine
384 * Signature: (Lsun/java2d/SunGraphics2D;Lsun/java2d/SurfaceData;IIII)V
385 */
386JNIEXPORT void JNICALL
387Java_sun_java2d_loops_DrawLine_DrawLine
388    (JNIEnv *env, jobject self,
389     jobject sg2d, jobject sData,
390     jint x1, jint y1, jint x2, jint y2)
391{
392    SurfaceDataOps *sdOps;
393    SurfaceDataRasInfo rasInfo;
394    NativePrimitive *pPrim;
395    CompositeInfo compInfo;
396    jint pixel = GrPrim_Sg2dGetPixel(env, sg2d);
397
398    pPrim = GetNativePrim(env, self);
399    if (pPrim == NULL) {
400        return;
401    }
402    if (pPrim->pCompType->getCompInfo != NULL) {
403        GrPrim_Sg2dGetCompInfo(env, sg2d, pPrim, &compInfo);
404    }
405
406    sdOps = SurfaceData_GetOps(env, sData);
407    if (sdOps == 0) {
408        return;
409    }
410
411    GrPrim_Sg2dGetClip(env, sg2d, &rasInfo.bounds);
412
413    RefineBounds(&rasInfo.bounds, x1, y1, x2, y2);
414
415    if (sdOps->Lock(env, sdOps, &rasInfo, pPrim->dstflags) != SD_SUCCESS) {
416        return;
417    }
418
419    if (rasInfo.bounds.x2 > rasInfo.bounds.x1 &&
420        rasInfo.bounds.y2 > rasInfo.bounds.y1)
421    {
422        sdOps->GetRasInfo(env, sdOps, &rasInfo);
423        if (rasInfo.rasBase) {
424            LineUtils_ProcessLine(&rasInfo, pixel,
425                                  pPrim->funcs.drawline, pPrim, &compInfo,
426                                  x1, y1, x2, y2, 0);
427        }
428        SurfaceData_InvokeRelease(env, sdOps, &rasInfo);
429    }
430    SurfaceData_InvokeUnlock(env, sdOps, &rasInfo);
431}
432