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