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