1 /*
   2  * Copyright (c) 2005, 2013, 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 <math.h>
  27 #include <assert.h>
  28 #include <stdlib.h>
  29 #include <string.h>
  30 
  31 #include "j2d_md.h"
  32 #include "java_awt_geom_PathIterator.h"
  33 
  34 #include "ProcessPath.h"
  35 
  36 /*
  37  * This framework performs filling and drawing of paths with sub-pixel
  38  * precision. Also, it performs clipping by the specified view area.
  39  *
  40  * Drawing of the shapes is performed not pixel by pixel but segment by segment
  41  * except several pixels near endpoints of the drawn line. This approach saves
  42  * lot's of cpu cycles especially in case of large primitives (like ovals with
  43  * sizes more than 50) and helps in achieving appropriate visual quality. Also,
  44  * such method of drawing is useful for the accelerated pipelines where
  45  * overhead of the per-pixel drawing could eliminate all benefits of the
  46  * hardware acceleration.
  47  *
  48  * Filling of the path was  taken from
  49  *
  50  * [Graphics Gems, edited by Andrew S Glassner. Academic Press 1990,
  51  * ISBN 0-12-286165-5 (Concave polygon scan conversion), 87-91]
  52  *
  53  * and modified to work with sub-pixel precision and non-continuous paths.
  54  * It's also speeded up by using hash table by rows of the filled objects.
  55  *
  56  * Here is high level scheme showing the rendering process:
  57  *
  58  *                   doDrawPath   doFillPath
  59  *                         \         /
  60  *                         ProcessPath
  61  *                              |
  62  *                      CheckPathSegment
  63  *                              |
  64  *                      --------+------
  65  *                      |             |
  66  *                      |             |
  67  *                      |             |
  68  *                  _->ProcessCurve   |
  69  *                 /    / |           |
  70  *                 \___/  |           |
  71  *                        |           |
  72  *                    DrawCurve     ProcessLine
  73  *                         \         /
  74  *                          \       /
  75  *                           \     /
  76  *                            \   /
  77  *                        ------+------
  78  *             (filling) /             \ (drawing)
  79  *                      /               \
  80  *               Clipping and        Clipping
  81  *                clamping                \
  82  *                   |                     \
  83  *           StoreFixedLine          ProcessFixedLine
  84  *                   |                     /    \
  85  *                   |                    /      \
  86  *             FillPolygon       PROCESS_LINE   PROCESS_POINT
  87  *
  88  *
  89  *
  90  *  CheckPathSegment  - rough checking and skipping path's segments  in case of
  91  *                      invalid or huge coordinates of the control points to
  92  *                      avoid calculation problems with NaNs and values close
  93  *                      to the FLT_MAX
  94  *
  95  * ProcessCurve - (ProcessQuad, ProcessCubic) Splitting the curve into
  96  *                monotonic parts having appropriate size (calculated as
  97  *                boundary box of the control points)
  98  *
  99  * DrawMonotonicCurve - (DrawMonotonicQuad, DrawMonotonicCubic) flattening
 100  *                      monotonic curve using adaptive forward differencing
 101  *
 102  * StoreFixedLine - storing segment from the flattened path to the
 103  *                  FillData structure. Performing clipping and clamping if
 104  *                  necessary.
 105  *
 106  * PROCESS_LINE, PROCESS_POINT - Helpers for calling appropriate primitive from
 107  *                               DrawHandler structure
 108  *
 109  * ProcessFixedLine - Drawing line segment with subpixel precision.
 110  *
 111  */
 112 
 113 #define PROCESS_LINE(hnd, fX0, fY0, fX1, fY1, checkBounds, pixelInfo)       \
 114     do {                                                                    \
 115         jint X0 = (fX0) >> MDP_PREC;                                        \
 116         jint Y0 = (fY0) >> MDP_PREC;                                        \
 117         jint X1 = (fX1) >> MDP_PREC;                                        \
 118         jint Y1 = (fY1) >> MDP_PREC;                                        \
 119         jint res;                                                           \
 120                                                                             \
 121         /* Checking bounds and clipping if necessary.                       \
 122          * REMIND: It's temporary solution to avoid OOB in rendering code.  \
 123          * Current approach uses float equations which are unreliable for   \
 124          * clipping and makes assumptions about the line biases of the      \
 125          * rendering algorithm. Also, clipping code should be moved down    \
 126          * into only those output renderers that need it.                   \
 127          */                                                                 \
 128         if (checkBounds) {                                                  \
 129             jfloat xMinf = hnd->dhnd->xMinf + 0.5f;                         \
 130             jfloat yMinf = hnd->dhnd->yMinf + 0.5f;                         \
 131             jfloat xMaxf = hnd->dhnd->xMaxf + 0.5f;                         \
 132             jfloat yMaxf = hnd->dhnd->yMaxf + 0.5f;                         \
 133             TESTANDCLIP(yMinf, yMaxf, Y0, X0, Y1, X1, jint, res);           \
 134             if (res == CRES_INVISIBLE) break;                               \
 135             TESTANDCLIP(yMinf, yMaxf, Y1, X1, Y0, X0, jint, res);           \
 136             if (res == CRES_INVISIBLE) break;                               \
 137             TESTANDCLIP(xMinf, xMaxf, X0, Y0, X1, Y1, jint, res);           \
 138             if (res == CRES_INVISIBLE) break;                               \
 139             TESTANDCLIP(xMinf, xMaxf, X1, Y1, X0, Y0, jint, res);           \
 140             if (res == CRES_INVISIBLE) break;                               \
 141         }                                                                   \
 142                                                                             \
 143         /* Handling lines having just one pixel      */                     \
 144         if (((X0^X1) | (Y0^Y1)) == 0) {                                     \
 145             if (pixelInfo[0] == 0) {                                        \
 146                 pixelInfo[0] = 1;                                           \
 147                 pixelInfo[1] = X0;                                          \
 148                 pixelInfo[2] = Y0;                                          \
 149                 pixelInfo[3] = X0;                                          \
 150                 pixelInfo[4] = Y0;                                          \
 151                 hnd->dhnd->pDrawPixel(hnd->dhnd, X0, Y0);                   \
 152             } else if ((X0 != pixelInfo[3] || Y0 != pixelInfo[4]) &&        \
 153                        (X0 != pixelInfo[1] || Y0 != pixelInfo[2])) {        \
 154                 hnd->dhnd->pDrawPixel(hnd->dhnd, X0, Y0);                   \
 155                 pixelInfo[3] = X0;                                          \
 156                 pixelInfo[4] = Y0;                                          \
 157             }                                                               \
 158             break;                                                          \
 159         }                                                                   \
 160                                                                             \
 161         if (pixelInfo[0] &&                                                 \
 162             ((pixelInfo[1] == X0 && pixelInfo[2] == Y0) ||                  \
 163             (pixelInfo[3] == X0 && pixelInfo[4] == Y0)))                    \
 164         {                                                                   \
 165             hnd->dhnd->pDrawPixel(hnd->dhnd, X0, Y0);                       \
 166         }                                                                   \
 167                                                                             \
 168         hnd->dhnd->pDrawLine(hnd->dhnd, X0, Y0, X1, Y1);                    \
 169                                                                             \
 170         if (pixelInfo[0] == 0) {                                            \
 171             pixelInfo[0] = 1;                                               \
 172             pixelInfo[1] = X0;                                              \
 173             pixelInfo[2] = Y0;                                              \
 174             pixelInfo[3] = X0;                                              \
 175             pixelInfo[4] = Y0;                                              \
 176         }                                                                   \
 177                                                                             \
 178         /* Switch on last pixel of the line if it was already               \
 179          * drawn during rendering of the previous segments                  \
 180          */                                                                 \
 181         if ((pixelInfo[1] == X1 && pixelInfo[2] == Y1) ||                   \
 182             (pixelInfo[3] == X1 && pixelInfo[4] == Y1))                     \
 183         {                                                                   \
 184             hnd->dhnd->pDrawPixel(hnd->dhnd, X1, Y1);                       \
 185         }                                                                   \
 186         pixelInfo[3] = X1;                                                  \
 187         pixelInfo[4] = Y1;                                                  \
 188     } while(0)
 189 
 190 #define PROCESS_POINT(hnd, fX, fY, checkBounds, pixelInfo)                  \
 191     do {                                                                    \
 192         jint X_ = (fX)>> MDP_PREC;                                          \
 193         jint Y_ = (fY)>> MDP_PREC;                                          \
 194         if (checkBounds &&                                                  \
 195             (hnd->dhnd->yMin > Y_  ||                                       \
 196              hnd->dhnd->yMax <= Y_ ||                                       \
 197              hnd->dhnd->xMin > X_  ||                                       \
 198              hnd->dhnd->xMax <= X_)) break;                                 \
 199 /*                                                                          \
 200  *       (X_,Y_) should be inside boundaries                                \
 201  *                                                                          \
 202  *       assert(hnd->dhnd->yMin <= Y_ &&                                    \
 203  *              hnd->dhnd->yMax >  Y_ &&                                    \
 204  *              hnd->dhnd->xMin <= X_ &&                                    \
 205  *              hnd->dhnd->xMax >  X_);                                     \
 206  *                                                                          \
 207  */                                                                         \
 208         if (pixelInfo[0] == 0) {                                            \
 209             pixelInfo[0] = 1;                                               \
 210             pixelInfo[1] = X_;                                              \
 211             pixelInfo[2] = Y_;                                              \
 212             pixelInfo[3] = X_;                                              \
 213             pixelInfo[4] = Y_;                                              \
 214             hnd->dhnd->pDrawPixel(hnd->dhnd, X_, Y_);                       \
 215         } else if ((X_ != pixelInfo[3] || Y_ != pixelInfo[4]) &&            \
 216                    (X_ != pixelInfo[1] || Y_ != pixelInfo[2])) {            \
 217             hnd->dhnd->pDrawPixel(hnd->dhnd, X_, Y_);                       \
 218             pixelInfo[3] = X_;                                              \
 219             pixelInfo[4] = Y_;                                              \
 220         }                                                                   \
 221     } while(0)
 222 
 223 
 224 /*
 225  *                  Constants for the forward differencing
 226  *                      of the cubic and quad curves
 227  */
 228 
 229 /* Maximum size of the cubic curve (calculated as the size of the bounding box
 230  * of the control points) which could be rendered without splitting
 231  */
 232 #define MAX_CUB_SIZE    256
 233 
 234 /* Maximum size of the quad curve (calculated as the size of the bounding box
 235  * of the control points) which could be rendered without splitting
 236  */
 237 #define MAX_QUAD_SIZE   1024
 238 
 239 /* Default power of 2 steps used in the forward differencing. Here DF prefix
 240  * stands for DeFault. Constants below are used as initial values for the
 241  * adaptive forward differencing algorithm.
 242  */
 243 #define DF_CUB_STEPS    3
 244 #define DF_QUAD_STEPS   2
 245 
 246 /* Shift of the current point of the curve for preparing to the midpoint
 247  * rounding
 248  */
 249 #define DF_CUB_SHIFT    (FWD_PREC + DF_CUB_STEPS*3 - MDP_PREC)
 250 #define DF_QUAD_SHIFT    (FWD_PREC + DF_QUAD_STEPS*2 - MDP_PREC)
 251 
 252 /* Default amount of steps of the forward differencing */
 253 #define DF_CUB_COUNT    (1<<DF_CUB_STEPS)
 254 #define DF_QUAD_COUNT    (1<<DF_QUAD_STEPS)
 255 
 256 /* Default boundary constants used to check the necessity of the restepping */
 257 #define DF_CUB_DEC_BND     (1<<(DF_CUB_STEPS*3 + FWD_PREC + 2))
 258 #define DF_CUB_INC_BND     (1<<(DF_CUB_STEPS*3 + FWD_PREC - 1))
 259 #define DF_QUAD_DEC_BND     (1<<(DF_QUAD_STEPS*2 + FWD_PREC + 2))
 260 
 261 /* Multiplyers for the coefficients of the polynomial form of the cubic and
 262  * quad curves representation
 263  */
 264 #define CUB_A_SHIFT   FWD_PREC
 265 #define CUB_B_SHIFT   (DF_CUB_STEPS + FWD_PREC + 1)
 266 #define CUB_C_SHIFT   (DF_CUB_STEPS*2 + FWD_PREC)
 267 
 268 #define CUB_A_MDP_MULT    (1<<CUB_A_SHIFT)
 269 #define CUB_B_MDP_MULT    (1<<CUB_B_SHIFT)
 270 #define CUB_C_MDP_MULT    (1<<CUB_C_SHIFT)
 271 
 272 #define QUAD_A_SHIFT   FWD_PREC
 273 #define QUAD_B_SHIFT   (DF_QUAD_STEPS + FWD_PREC)
 274 
 275 #define QUAD_A_MDP_MULT    (1<<QUAD_A_SHIFT)
 276 #define QUAD_B_MDP_MULT    (1<<QUAD_B_SHIFT)
 277 
 278 #define CALC_MAX(MAX, X) ((MAX)=((X)>(MAX))?(X):(MAX))
 279 #define CALC_MIN(MIN, X) ((MIN)=((X)<(MIN))?(X):(MIN))
 280 #define MAX(MAX, X) (((X)>(MAX))?(X):(MAX))
 281 #define MIN(MIN, X) (((X)<(MIN))?(X):(MIN))
 282 #define ABS32(X) (((X)^((X)>>31))-((X)>>31))
 283 #define SIGN32(X) ((X) >> 31) | ((juint)(-(X)) >> 31)
 284 
 285 /* Boundaries used for clipping large path segments (those are inside
 286  * [UPPER/LOWER]_BND boundaries)
 287  */
 288 #define UPPER_OUT_BND (1 << (30 - MDP_PREC))
 289 #define LOWER_OUT_BND (-UPPER_OUT_BND)
 290 
 291 #define ADJUST(X, LBND, UBND)                                               \
 292     do {                                                                    \
 293         if ((X) < (LBND)) {                                                 \
 294             (X) = (LBND);                                                   \
 295         } else if ((X) > UBND) {                                            \
 296             (X) = (UBND);                                                   \
 297         }                                                                   \
 298     } while(0)
 299 
 300 /* Following constants are used for providing open boundaries of the intervals
 301  */
 302 #define EPSFX 1
 303 #define EPSF (((jfloat)EPSFX)/MDP_MULT)
 304 
 305 /* Calculation boundary. It is used for switching to the more slow but allowing
 306  * larger input values method of calculation of the initial values of the scan
 307  * converted line segments inside the FillPolygon.
 308  */
 309 #define CALC_BND (1 << (30 - MDP_PREC))
 310 
 311 /* Clipping macros for drawing and filling algorithms */
 312 
 313 #define CLIP(a1, b1, a2, b2, t) \
 314     (b1 + ((jdouble)(t - a1)*(b2 - b1)) / (a2 - a1))
 315 
 316 enum {
 317     CRES_MIN_CLIPPED,
 318     CRES_MAX_CLIPPED,
 319     CRES_NOT_CLIPPED,
 320     CRES_INVISIBLE
 321 };
 322 
 323 #define IS_CLIPPED(res) (res == CRES_MIN_CLIPPED || res == CRES_MAX_CLIPPED)
 324 
 325 #define TESTANDCLIP(LINE_MIN, LINE_MAX, a1, b1, a2, b2, TYPE, res)  \
 326    do {                                                             \
 327         jdouble t;                                                  \
 328         res = CRES_NOT_CLIPPED;                                     \
 329         if (a1 < (LINE_MIN) || a1 > (LINE_MAX)) {                   \
 330             if (a1 < (LINE_MIN)) {                                  \
 331                 if (a2 < (LINE_MIN)) {                              \
 332                     res = CRES_INVISIBLE;                           \
 333                     break;                                          \
 334                 };                                                  \
 335                 res = CRES_MIN_CLIPPED;                             \
 336                 t = (LINE_MIN);                                     \
 337             } else {                                                \
 338                 if (a2 > (LINE_MAX)) {                              \
 339                     res = CRES_INVISIBLE;                           \
 340                     break;                                          \
 341                 };                                                  \
 342                 res = CRES_MAX_CLIPPED;                             \
 343                 t = (LINE_MAX);                                     \
 344             }                                                       \
 345             b1 = (TYPE)CLIP(a1, b1, a2, b2, t);                     \
 346             a1 = (TYPE)t;                                           \
 347         }                                                           \
 348    } while (0)
 349 
 350 /* Following macro is used for clipping and clumping filled shapes.
 351  * An example of this process is shown on the picture below:
 352  *                      ----+          ----+
 353  *                    |/    |        |/    |
 354  *                    +     |        +     |
 355  *                   /|     |        I     |
 356  *                  / |     |        I     |
 357  *                  | |     |  ===>  I     |
 358  *                  \ |     |        I     |
 359  *                   \|     |        I     |
 360  *                    +     |        +     |
 361  *                    |\    |        |\    |
 362  *                    | ----+        | ----+
 363  *                 boundary       boundary
 364  *
 365  * We can only perform clipping in case of right side of the output area
 366  * because all segments passed out the right boundary don't influence on the
 367  * result of scan conversion algorithm (it correctly handles half open
 368  * contours).
 369  *
 370  */
 371 #define CLIPCLAMP(LINE_MIN, LINE_MAX, a1, b1, a2, b2, a3, b3, TYPE, res)  \
 372     do {                                                            \
 373         a3 = a1;                                                    \
 374         b3 = b1;                                                    \
 375         TESTANDCLIP(LINE_MIN, LINE_MAX, a1, b1, a2, b2, TYPE, res); \
 376         if (res == CRES_MIN_CLIPPED) {                              \
 377             a3 = a1;                                                \
 378         } else if (res == CRES_MAX_CLIPPED) {                       \
 379             a3 = a1;                                                \
 380             res = CRES_MAX_CLIPPED;                                 \
 381         } else if (res == CRES_INVISIBLE) {                         \
 382             if (a1 > LINE_MAX) {                                    \
 383                 res =  CRES_INVISIBLE;                              \
 384             } else {                                                \
 385                 a1 = (TYPE)LINE_MIN;                                \
 386                 a2 = (TYPE)LINE_MIN;                                \
 387                 res = CRES_NOT_CLIPPED;                             \
 388             }                                                       \
 389         }                                                           \
 390     } while (0)
 391 
 392 /* Following macro is used for solving quadratic equations:
 393  * A*t^2 + B*t + C = 0
 394  * in (0,1) range. That means we put to the RES the only roots which
 395  * belongs to the (0,1) range. Note: 0 and 1 are not included.
 396  * See solveQuadratic method in
 397  *  src/share/classes/java/awt/geom/QuadCurve2D.java
 398  * for more info about calculations
 399  */
 400 #define SOLVEQUADINRANGE(A,B,C,RES,RCNT)                            \
 401     do {                                                            \
 402         double param;                                               \
 403         if ((A) != 0) {                                             \
 404             /* Calculating roots of the following equation          \
 405              * A*t^2 + B*t + C = 0                                  \
 406              */                                                     \
 407             double d = (B)*(B) - 4*(A)*(C);                         \
 408             double q;                                               \
 409             if (d < 0) {                                            \
 410                 break;                                              \
 411             }                                                       \
 412             d = sqrt(d);                                            \
 413             /* For accuracy, calculate one root using:              \
 414              *     (-B +/- d) / 2*A                                 \
 415              * and the other using:                                 \
 416              *     2*C / (-B +/- d)                                 \
 417              * Choose the sign of the +/- so that B+D gets larger   \
 418              * in magnitude                                         \
 419              */                                                     \
 420             if ((B) < 0) {                                          \
 421                 d = -d;                                             \
 422             }                                                       \
 423             q = ((B) + d) / -2.0;                                   \
 424             param = q/(A);                                          \
 425             if (param < 1.0 && param > 0.0) {                       \
 426                 (RES)[(RCNT)++] = param;                            \
 427             }                                                       \
 428             if (d == 0 || q == 0) {                                 \
 429                 break;                                              \
 430             }                                                       \
 431             param = (C)/q;                                          \
 432             if (param < 1.0 && param > 0.0) {                       \
 433                 (RES)[(RCNT)++] = param;                            \
 434             }                                                       \
 435         } else {                                                    \
 436             /* Calculating root of the following equation           \
 437              * B*t + C = 0                                          \
 438              */                                                     \
 439             if ((B) == 0) {                                         \
 440                 break;                                              \
 441             }                                                       \
 442             param = -(C)/(B);                                       \
 443             if (param < 1.0 && param > 0.0) {                       \
 444                 (RES)[(RCNT)++] = param;                            \
 445             }                                                       \
 446         }                                                           \
 447     } while(0)
 448 
 449 /*                  Drawing line with subpixel endpoints
 450  *
 451  * (x1, y1), (x2, y2) -  fixed point coordinates of the endpoints
 452  *                       with MDP_PREC bits for the fractional part
 453  *
 454  * pixelInfo          -  structure which keeps drawing info for avoiding
 455  *                       multiple drawing at the same position on the
 456  *                       screen (required for the XOR mode of drawing)
 457  *
 458  *                          pixelInfo[0]   - state of the drawing
 459  *                                           0 - no pixel drawn between
 460  *                                           moveTo/close of the path
 461  *                                           1 - there are drawn pixels
 462  *
 463  *                          pixelInfo[1,2] - first pixel of the path
 464  *                                           between moveTo/close of the
 465  *                                           path
 466  *
 467  *                          pixelInfo[3,4] - last drawn pixel between
 468  *                                           moveTo/close of the path
 469  *
 470  * checkBounds        - flag showing necessity of checking the clip
 471  *
 472  */
 473 void  ProcessFixedLine(ProcessHandler* hnd,jint x1,jint y1,jint x2,jint y2,
 474                        jint* pixelInfo,jboolean checkBounds,
 475                        jboolean endSubPath)
 476 {
 477     /* Checking if line is inside a (X,Y),(X+MDP_MULT,Y+MDP_MULT) box */
 478     jint c = ((x1 ^ x2) | (y1 ^ y2));
 479     jint rx1, ry1, rx2, ry2;
 480     if ((c & MDP_W_MASK) == 0) {
 481         /* Checking for the segments with integer coordinates having
 482          * the same start and end points
 483          */
 484         if (c == 0) {
 485             PROCESS_POINT(hnd, x1 + MDP_HALF_MULT, y1 + MDP_HALF_MULT,
 486                           checkBounds, pixelInfo);
 487         }
 488         return;
 489     }
 490 
 491     if (x1 == x2 || y1 == y2) {
 492         rx1 = x1 + MDP_HALF_MULT;
 493         rx2 = x2 + MDP_HALF_MULT;
 494         ry1 = y1 + MDP_HALF_MULT;
 495         ry2 = y2 + MDP_HALF_MULT;
 496     } else {
 497         /* Neither dx nor dy can be zero because of the check above */
 498         jint dx = x2 - x1;
 499         jint dy = y2 - y1;
 500 
 501         /* Floor of x1, y1, x2, y2 */
 502         jint fx1 = x1 & MDP_W_MASK;
 503         jint fy1 = y1 & MDP_W_MASK;
 504         jint fx2 = x2 & MDP_W_MASK;
 505         jint fy2 = y2 & MDP_W_MASK;
 506 
 507         /* Processing first endpoint */
 508         if (fx1 == x1 || fy1 == y1) {
 509             /* Adding MDP_HALF_MULT to the [xy]1 if f[xy]1 == [xy]1 will not
 510              * affect the result
 511              */
 512             rx1 = x1 + MDP_HALF_MULT;
 513             ry1 = y1 + MDP_HALF_MULT;
 514         } else {
 515             /* Boundary at the direction from (x1,y1) to (x2,y2) */
 516             jint bx1 = (x1 < x2) ? fx1 + MDP_MULT : fx1;
 517             jint by1 = (y1 < y2) ? fy1 + MDP_MULT : fy1;
 518 
 519             /* intersection with column bx1 */
 520             jint cross = y1 + ((bx1 - x1)*dy)/dx;
 521             if (cross >= fy1 && cross <= fy1 + MDP_MULT) {
 522                 rx1 = bx1;
 523                 ry1 = cross + MDP_HALF_MULT;
 524             } else {
 525                 /* intersection with row by1 */
 526                 cross = x1 + ((by1 - y1)*dx)/dy;
 527                 rx1 = cross + MDP_HALF_MULT;
 528                 ry1 = by1;
 529             }
 530         }
 531 
 532         /* Processing second endpoint */
 533         if (fx2 == x2 || fy2 == y2) {
 534             /* Adding MDP_HALF_MULT to the [xy]2 if f[xy]2 == [xy]2 will not
 535              * affect the result
 536              */
 537             rx2 = x2 + MDP_HALF_MULT;
 538             ry2 = y2 + MDP_HALF_MULT;
 539         } else {
 540             /* Boundary at the direction from (x2,y2) to (x1,y1) */
 541             jint bx2 = (x1 > x2) ? fx2 + MDP_MULT : fx2;
 542             jint by2 = (y1 > y2) ? fy2 + MDP_MULT : fy2;
 543 
 544             /* intersection with column bx2 */
 545             jint cross = y2 + ((bx2 - x2)*dy)/dx;
 546             if (cross >= fy2 && cross <= fy2 + MDP_MULT) {
 547                 rx2 = bx2;
 548                 ry2 = cross + MDP_HALF_MULT;
 549             } else {
 550                 /* intersection with row by2 */
 551                 cross = x2 + ((by2 - y2)*dx)/dy;
 552                 rx2 = cross + MDP_HALF_MULT;
 553                 ry2 = by2;
 554             }
 555         }
 556     }
 557 
 558     PROCESS_LINE(hnd, rx1, ry1, rx2, ry2, checkBounds, pixelInfo);
 559 }
 560 
 561 /* Performing drawing of the monotonic in X and Y quadratic curves with sizes
 562  * less than MAX_QUAD_SIZE by using forward differencing method of calculation.
 563  * See comments to the DrawMonotonicCubic.
 564  */
 565 static void DrawMonotonicQuad(ProcessHandler* hnd,
 566                               jfloat *coords,
 567                               jboolean checkBounds,
 568                               jint* pixelInfo)
 569 {
 570     jint x0 = (jint)(coords[0]*MDP_MULT);
 571     jint y0 = (jint)(coords[1]*MDP_MULT);
 572 
 573     jint xe = (jint)(coords[4]*MDP_MULT);
 574     jint ye = (jint)(coords[5]*MDP_MULT);
 575 
 576     /* Extracting fractional part of coordinates of first control point */
 577     jint px = (x0 & (~MDP_W_MASK)) << DF_QUAD_SHIFT;
 578     jint py = (y0 & (~MDP_W_MASK)) << DF_QUAD_SHIFT;
 579 
 580     /* Setting default amount of steps */
 581     jint count = DF_QUAD_COUNT;
 582 
 583     /* Setting default shift for preparing to the midpoint rounding */
 584     jint shift =  DF_QUAD_SHIFT;
 585 
 586     jint ax = (jint)((coords[0] - 2*coords[2] +
 587                       coords[4])*QUAD_A_MDP_MULT);
 588     jint ay = (jint)((coords[1] - 2*coords[3] +
 589                       coords[5])*QUAD_A_MDP_MULT);
 590 
 591     jint bx = (jint)((-2*coords[0] + 2*coords[2])*QUAD_B_MDP_MULT);
 592     jint by = (jint)((-2*coords[1] + 2*coords[3])*QUAD_B_MDP_MULT);
 593 
 594     jint ddpx = 2*ax;
 595     jint ddpy = 2*ay;
 596 
 597     jint dpx = ax + bx;
 598     jint dpy = ay + by;
 599 
 600     jint x1, y1;
 601 
 602     jint x2 = x0;
 603     jint y2 = y0;
 604 
 605     jint maxDD = MAX(ABS32(ddpx),ABS32(ddpy));
 606     jint x0w = x0 & MDP_W_MASK;
 607     jint y0w = y0 & MDP_W_MASK;
 608 
 609     jint dx = xe - x0;
 610     jint dy = ye - y0;
 611 
 612     /* Perform decreasing step in 2 times if slope of the second forward
 613      * difference changes too quickly (more than a pixel per step in X or Y
 614      * direction). We can perform adjusting of the step size before the
 615      * rendering loop because the curvature of the quad curve remains the same
 616      * along all the curve
 617      */
 618     while (maxDD > DF_QUAD_DEC_BND) {
 619         dpx = (dpx<<1) - ax;
 620         dpy = (dpy<<1) - ay;
 621         count <<= 1;
 622         maxDD >>= 2;
 623         px <<=2;
 624         py <<=2;
 625         shift += 2;
 626     }
 627 
 628     while(count-- > 1) {
 629 
 630         px += dpx;
 631         py += dpy;
 632 
 633         dpx += ddpx;
 634         dpy += ddpy;
 635 
 636         x1 = x2;
 637         y1 = y2;
 638 
 639         x2 = x0w + (px >> shift);
 640         y2 = y0w + (py >> shift);
 641 
 642         /* Checking that we are not running out of the endpoint and bounding
 643          * violating coordinate.  The check is pretty simple because the curve
 644          * passed to the DrawMonotonicQuad already split into the monotonic
 645          * in X and Y pieces
 646          */
 647 
 648         /* Bounding x2 by xe */
 649         if (((xe-x2)^dx) < 0) {
 650             x2 = xe;
 651         }
 652 
 653         /* Bounding y2 by ye */
 654         if (((ye-y2)^dy) < 0) {
 655             y2 = ye;
 656         }
 657 
 658         hnd->pProcessFixedLine(hnd, x1, y1, x2, y2, pixelInfo, checkBounds,
 659                                JNI_FALSE);
 660     }
 661 
 662     /* We are performing one step less than necessary and use actual (xe,ye)
 663      * curve's endpoint instead of calculated. This prevent us from accumulated
 664      * errors at the last point.
 665      */
 666 
 667     hnd->pProcessFixedLine(hnd, x2, y2, xe, ye, pixelInfo, checkBounds,
 668                            JNI_FALSE);
 669 }
 670 
 671 /*
 672  * Checking size of the quad curves and split them if necessary.
 673  * Calling DrawMonotonicQuad for the curves of the appropriate size.
 674  * Note: coords array could be changed
 675  */
 676 static void ProcessMonotonicQuad(ProcessHandler* hnd,
 677                                  jfloat *coords,
 678                                  jint* pixelInfo) {
 679 
 680     jfloat coords1[6];
 681     jfloat xMin, xMax;
 682     jfloat yMin, yMax;
 683 
 684     xMin = xMax = coords[0];
 685     yMin = yMax = coords[1];
 686 
 687     CALC_MIN(xMin, coords[2]);
 688     CALC_MAX(xMax, coords[2]);
 689     CALC_MIN(yMin, coords[3]);
 690     CALC_MAX(yMax, coords[3]);
 691     CALC_MIN(xMin, coords[4]);
 692     CALC_MAX(xMax, coords[4]);
 693     CALC_MIN(yMin, coords[5]);
 694     CALC_MAX(yMax, coords[5]);
 695 
 696 
 697     if (hnd->clipMode == PH_MODE_DRAW_CLIP) {
 698 
 699         /* In case of drawing we could just skip curves which are completely
 700          * out of bounds
 701          */
 702         if (hnd->dhnd->xMaxf < xMin || hnd->dhnd->xMinf > xMax ||
 703             hnd->dhnd->yMaxf < yMin || hnd->dhnd->yMinf > yMax) {
 704             return;
 705         }
 706     } else {
 707 
 708         /* In case of filling we could skip curves which are above,
 709          * below and behind the right boundary of the visible area
 710          */
 711 
 712          if (hnd->dhnd->yMaxf < yMin || hnd->dhnd->yMinf > yMax ||
 713              hnd->dhnd->xMaxf < xMin)
 714          {
 715              return;
 716          }
 717 
 718         /* We could clamp x coordinates to the corresponding boundary
 719          * if the curve is completely behind the left one
 720          */
 721 
 722         if (hnd->dhnd->xMinf > xMax) {
 723             coords[0] = coords[2] = coords[4] = hnd->dhnd->xMinf;
 724         }
 725     }
 726 
 727     if (xMax - xMin > MAX_QUAD_SIZE || yMax - yMin > MAX_QUAD_SIZE) {
 728         coords1[4] = coords[4];
 729         coords1[5] = coords[5];
 730         coords1[2] = (coords[2] + coords[4])/2.0f;
 731         coords1[3] = (coords[3] + coords[5])/2.0f;
 732         coords[2] = (coords[0] + coords[2])/2.0f;
 733         coords[3] = (coords[1] + coords[3])/2.0f;
 734         coords[4] = coords1[0] = (coords[2] + coords1[2])/2.0f;
 735         coords[5] = coords1[1] = (coords[3] + coords1[3])/2.0f;
 736 
 737         ProcessMonotonicQuad(hnd, coords, pixelInfo);
 738 
 739         ProcessMonotonicQuad(hnd, coords1, pixelInfo);
 740     } else {
 741         DrawMonotonicQuad(hnd, coords,
 742                          /* Set checkBounds parameter if curve intersects
 743                           * boundary of the visible area. We know that the
 744                           * curve is visible, so the check is pretty simple
 745                           */
 746                          hnd->dhnd->xMinf >= xMin || hnd->dhnd->xMaxf <= xMax ||
 747                          hnd->dhnd->yMinf >= yMin || hnd->dhnd->yMaxf <= yMax,
 748                          pixelInfo);
 749     }
 750 }
 751 
 752 /*
 753  * Bite the piece of the quadratic curve from start point till the point
 754  * corresponding to the specified parameter then call ProcessQuad for the
 755  * bitten part.
 756  * Note: coords array will be changed
 757  */
 758 static void ProcessFirstMonotonicPartOfQuad(ProcessHandler* hnd, jfloat* coords,
 759                                             jint* pixelInfo, jfloat t)
 760 {
 761     jfloat coords1[6];
 762 
 763     coords1[0] = coords[0];
 764     coords1[1] = coords[1];
 765     coords1[2] = coords[0] + t*(coords[2] - coords[0]);
 766     coords1[3] = coords[1] + t*(coords[3] - coords[1]);
 767     coords[2] = coords[2] + t*(coords[4] - coords[2]);
 768     coords[3] = coords[3] + t*(coords[5] - coords[3]);
 769     coords[0] = coords1[4] = coords1[2] + t*(coords[2] - coords1[2]);
 770     coords[1] = coords1[5] = coords1[3] + t*(coords[3] - coords1[3]);
 771 
 772     ProcessMonotonicQuad(hnd, coords1, pixelInfo);
 773 }
 774 
 775 /*
 776  * Split quadratic curve into monotonic in X and Y parts. Calling
 777  * ProcessMonotonicQuad for each monotonic piece of the curve.
 778  * Note: coords array could be changed
 779  */
 780 static void ProcessQuad(ProcessHandler* hnd, jfloat* coords, jint* pixelInfo) {
 781 
 782     /* Temporary array for holding parameters corresponding to the extreme in X
 783      * and Y points. The values are inside the (0,1) range (0 and 1 excluded)
 784      * and in ascending order.
 785      */
 786     double params[2];
 787 
 788     jint cnt = 0;
 789     double param;
 790 
 791     /* Simple check for monotonicity in X before searching for the extreme
 792      * points of the X(t) function. We first check if the curve is monotonic
 793      * in X by seeing if all of the X coordinates are strongly ordered.
 794      */
 795     if ((coords[0] > coords[2] || coords[2] > coords[4]) &&
 796         (coords[0] < coords[2] || coords[2] < coords[4]))
 797     {
 798         /* Searching for extreme points of the X(t) function  by solving
 799          * dX(t)
 800          * ----  = 0 equation
 801          *  dt
 802          */
 803         double ax = coords[0] - 2*coords[2] + coords[4];
 804         if (ax != 0) {
 805             /* Calculating root of the following equation
 806              * ax*t + bx = 0
 807              */
 808             double bx = coords[0] - coords[2];
 809 
 810             param = bx/ax;
 811             if (param < 1.0 && param > 0.0) {
 812                 params[cnt++] = param;
 813             }
 814         }
 815     }
 816 
 817     /* Simple check for monotonicity in Y before searching for the extreme
 818      * points of the Y(t) function. We first check if the curve is monotonic
 819      * in Y by seeing if all of the Y coordinates are strongly ordered.
 820      */
 821     if ((coords[1] > coords[3] || coords[3] > coords[5]) &&
 822         (coords[1] < coords[3] || coords[3] < coords[5]))
 823     {
 824         /* Searching for extreme points of the Y(t) function by solving
 825          * dY(t)
 826          * ----- = 0 equation
 827          *  dt
 828          */
 829         double ay = coords[1] - 2*coords[3] + coords[5];
 830 
 831         if (ay != 0) {
 832             /* Calculating root of the following equation
 833              * ay*t + by = 0
 834              */
 835             double by = coords[1] - coords[3];
 836 
 837             param = by/ay;
 838             if (param < 1.0 && param > 0.0) {
 839                 if (cnt > 0) {
 840                     /* Inserting parameter only if it differs from
 841                      * already stored
 842                      */
 843                     if (params[0] >  param) {
 844                         params[cnt++] = params[0];
 845                         params[0] = param;
 846                     } else if (params[0] <  param) {
 847                         params[cnt++] = param;
 848                     }
 849                 } else {
 850                     params[cnt++] = param;
 851                 }
 852             }
 853         }
 854     }
 855 
 856     /* Processing obtained monotonic parts */
 857     switch(cnt) {
 858         case 0:
 859             break;
 860         case 1:
 861             ProcessFirstMonotonicPartOfQuad(hnd, coords, pixelInfo,
 862                                             (jfloat)params[0]);
 863             break;
 864         case 2:
 865             ProcessFirstMonotonicPartOfQuad(hnd, coords, pixelInfo,
 866                                             (jfloat)params[0]);
 867             param = params[1] - params[0];
 868             if (param > 0) {
 869                 ProcessFirstMonotonicPartOfQuad(hnd, coords, pixelInfo,
 870                     /* Scale parameter to match with rest of the curve */
 871                     (jfloat)(param/(1.0 - params[0])));
 872             }
 873             break;
 874     }
 875 
 876     ProcessMonotonicQuad(hnd,coords,pixelInfo);
 877 }
 878 
 879 /*
 880  * Performing drawing of the monotonic in X and Y cubic curves with sizes less
 881  * than MAX_CUB_SIZE by using forward differencing method of calculation.
 882  *
 883  * Here is some math used in the code below.
 884  *
 885  * If we express the parametric equation for the coordinates as
 886  * simple polynomial:
 887  *
 888  *  V(t) = a * t^3 + b * t^2 + c * t + d
 889  *
 890  * The equations for how we derive these polynomial coefficients
 891  * from the Bezier control points can be found in the method comments
 892  * for the CubicCurve.fillEqn Java method.
 893  *
 894  * From this polynomial, we can derive the forward differences to
 895  * allow us to calculate V(t+K) from V(t) as follows:
 896  *
 897  * 1) V1(0)
 898  *        = V(K)-V(0)
 899  *        = aK^3 + bK^2 + cK + d - d
 900  *        = aK^3 + bK^2 + cK
 901  *
 902  * 2) V1(K)
 903  *        = V(2K)-V(K)
 904  *        = 8aK^3 + 4bK^2 + 2cK + d - aK^3 - bK^2 - cK - d
 905  *        = 7aK^3 + 3bK^2 + cK
 906  *
 907  * 3) V1(2K)
 908  *        = V(3K)-V(2K)
 909  *        = 27aK^3 + 9bK^2 + 3cK + d - 8aK^3 - 4bK^2 - 2cK - d
 910  *        = 19aK^3 + 5bK^2 + cK
 911  *
 912  * 4) V2(0)
 913  *        = V1(K) - V1(0)
 914  *        = 7aK^3 + 3bK^2 + cK - aK^3 - bK^2 - cK
 915  *        = 6aK^3 + 2bK^2
 916  *
 917  * 5) V2(K)
 918  *        = V1(2K) - V1(K)
 919  *        = 19aK^3 + 5bK^2 + cK - 7aK^3 - 3bK^2 - cK
 920  *        = 12aK^3 + 2bK^2
 921  *
 922  * 6) V3(0)
 923  *        = V2(K) - V2(0)
 924  *        = 12aK^3 + 2bK^2 - 6aK^3 - 2bK^2
 925  *        = 6aK^3
 926  *
 927  * Note that if we continue on to calculate V1(3K), V2(2K) and
 928  * V3(K) we will see that V3(K) == V3(0) so we need at most
 929  * 3 cascading forward differences to step through the cubic
 930  * curve.
 931  *
 932  * Note, b coefficient calculating in the DrawCubic is actually twice the b
 933  * coefficient seen above.  It's been done for the better accuracy.
 934  *
 935  * In our case, initialy K is chosen as 1/(2^DF_CUB_STEPS) this value is taken
 936  * with FWD_PREC bits precision. This means that we should do 2^DF_CUB_STEPS
 937  * steps to pass through all the curve.
 938  *
 939  * On each step we examine how far we are stepping by examining our first(V1)
 940  * and second (V2) order derivatives and verifying that they are met following
 941  * conditions:
 942  *
 943  * abs(V2) <= DF_CUB_DEC_BND
 944  * abs(V1) > DF_CUB_INC_BND
 945  *
 946  * So, ensures that we step through the curve more slowly when its curvature is
 947  * high and faster when its curvature is lower.  If the step size needs
 948  * adjustment we adjust it so that we step either twice as fast, or twice as
 949  * slow until our step size is within range.  This modifies our stepping
 950  * variables as follows:
 951  *
 952  * Decreasing step size
 953  * (See Graphics Gems/by A.Glassner,(Tutorial on forward differencing),601-602)
 954  *
 955  * V3 = oV3/8
 956  * V2 = oV2/4 - V3
 957  * V1 = (oV1 - V2)/2
 958  *
 959  * Here V1-V3 stands for new values of the forward differencies and oV1 - oV3
 960  * for the old ones
 961  *
 962  * Using the equations above it's easy to calculating stepping variables for
 963  * the increasing step size:
 964  *
 965  * V1 = 2*oV1 + oV2
 966  * V2 = 4*oV2 + 4*oV3
 967  * V3 = 8*oV3
 968  *
 969  * And then for not to running out of 32 bit precision we are performing 3 bit
 970  * shift of the forward differencing precision (keeping in shift variable) in
 971  * left or right direction depending on what is  happening (decreasing or
 972  * increasing). So, all oV1 - oV3 variables should be thought as appropriately
 973  * shifted in regard to the V1 - V3.
 974  *
 975  * Taking all of the above into account we will have following:
 976  *
 977  * Decreasing step size:
 978  *
 979  * shift = shift + 3
 980  * V3 keeps the same
 981  * V2 = 2*oV2 - V3
 982  * V1 = 4*oV1 - V2/2
 983  *
 984  * Increasing step size:
 985  *
 986  * shift = shift - 3
 987  * V1 = oV1/4 + oV2/8
 988  * V2 = oV2/2 + oV3/2
 989  * V3 keeps the same
 990  *
 991  */
 992 
 993 static void DrawMonotonicCubic(ProcessHandler* hnd,
 994                                jfloat *coords,
 995                                jboolean checkBounds,
 996                                jint* pixelInfo)
 997 {
 998     jint x0 = (jint)(coords[0]*MDP_MULT);
 999     jint y0 = (jint)(coords[1]*MDP_MULT);
1000 
1001     jint xe = (jint)(coords[6]*MDP_MULT);
1002     jint ye = (jint)(coords[7]*MDP_MULT);
1003 
1004     /* Extracting fractional part of coordinates of first control point */
1005     jint px = (x0 & (~MDP_W_MASK)) << DF_CUB_SHIFT;
1006     jint py = (y0 & (~MDP_W_MASK)) << DF_CUB_SHIFT;
1007 
1008     /* Setting default boundary values for checking first and second forward
1009      * difference for the necessity of the restepping. See comments to the
1010      * boundary values in ProcessQuad for more info.
1011      */
1012     jint incStepBnd1 = DF_CUB_INC_BND;
1013     jint incStepBnd2 = DF_CUB_INC_BND << 1;
1014     jint decStepBnd1 = DF_CUB_DEC_BND;
1015     jint decStepBnd2 = DF_CUB_DEC_BND << 1;
1016 
1017     /* Setting default amount of steps */
1018     jint count = DF_CUB_COUNT;
1019 
1020     /* Setting default shift for preparing to the midpoint rounding */
1021     jint shift =  DF_CUB_SHIFT;
1022 
1023     jint ax = (jint)((-coords[0] + 3*coords[2] - 3*coords[4] +
1024                 coords[6])*CUB_A_MDP_MULT);
1025     jint ay = (jint)((-coords[1] + 3*coords[3] - 3*coords[5] +
1026                 coords[7])*CUB_A_MDP_MULT);
1027 
1028     jint bx = (jint)((3*coords[0] - 6*coords[2] +
1029               3*coords[4])*CUB_B_MDP_MULT);
1030     jint by = (jint)((3*coords[1] - 6*coords[3] +
1031               3*coords[5])*CUB_B_MDP_MULT);
1032 
1033     jint cx = (jint)((-3*coords[0] + 3*coords[2])*(CUB_C_MDP_MULT));
1034     jint cy = (jint)((-3*coords[1] + 3*coords[3])*(CUB_C_MDP_MULT));
1035 
1036     jint dddpx = 6*ax;
1037     jint dddpy = 6*ay;
1038 
1039     jint ddpx = dddpx + bx;
1040     jint ddpy = dddpy + by;
1041 
1042     jint dpx = ax + (bx>>1) + cx;
1043     jint dpy = ay + (by>>1) + cy;
1044 
1045     jint x1, y1;
1046 
1047     jint x2 = x0;
1048     jint y2 = y0;
1049 
1050     /* Calculating whole part of the first point of the curve */
1051     jint x0w = x0 & MDP_W_MASK;
1052     jint y0w = y0 & MDP_W_MASK;
1053 
1054     jint dx = xe - x0;
1055     jint dy = ye - y0;
1056 
1057     while (count > 0) {
1058         /* Perform decreasing step in 2 times if necessary */
1059         while (
1060                /* The code below is an optimized version of the checks:
1061                 *   abs(ddpx) > decStepBnd1 ||
1062                 *   abs(ddpy) > decStepBnd1
1063                 */
1064                (juint)(ddpx + decStepBnd1) > (juint)decStepBnd2 ||
1065                (juint)(ddpy + decStepBnd1) > (juint)decStepBnd2)
1066         {
1067             ddpx = (ddpx<<1) - dddpx;
1068             ddpy = (ddpy<<1) - dddpy;
1069             dpx = (dpx<<2) - (ddpx>>1);
1070             dpy = (dpy<<2) - (ddpy>>1);
1071             count <<=1;
1072             decStepBnd1 <<=3;
1073             decStepBnd2 <<=3;
1074             incStepBnd1 <<=3;
1075             incStepBnd2 <<=3;
1076             px <<=3;
1077             py <<=3;
1078             shift += 3;
1079         }
1080 
1081         /* Perform increasing step in 2 times if necessary.
1082          * Note: we could do it only in even steps
1083          */
1084 
1085         while (((count & 1) ^ 1) && shift > DF_CUB_SHIFT  &&
1086                /* The code below is an optimized version of the check:
1087                 *   abs(dpx) <= incStepBnd1 &&
1088                 *   abs(dpy) <= incStepBnd1
1089                 */
1090                (juint)(dpx + incStepBnd1) <= (juint)incStepBnd2 &&
1091                (juint)(dpy + incStepBnd1) <= (juint)incStepBnd2)
1092         {
1093             dpx = (dpx>>2) + (ddpx>>3);
1094             dpy = (dpy>>2) + (ddpy>>3);
1095             ddpx = (ddpx + dddpx)>>1;
1096             ddpy = (ddpy + dddpy)>>1;
1097             count >>=1;
1098             decStepBnd1 >>=3;
1099             decStepBnd2 >>=3;
1100             incStepBnd1 >>=3;
1101             incStepBnd2 >>=3;
1102             px >>=3;
1103             py >>=3;
1104             shift -= 3;
1105         }
1106 
1107         count--;
1108 
1109         /* We are performing one step less than necessary and use actual
1110          * (xe,ye) endpoint of the curve instead of calculated. This prevent
1111          * us from accumulated errors at the last point.
1112          */
1113         if (count) {
1114 
1115             px += dpx;
1116             py += dpy;
1117 
1118             dpx += ddpx;
1119             dpy += ddpy;
1120             ddpx += dddpx;
1121             ddpy += dddpy;
1122 
1123             x1 = x2;
1124             y1 = y2;
1125 
1126             x2 = x0w + (px >> shift);
1127             y2 = y0w + (py >> shift);
1128 
1129             /* Checking that we are not running out of the endpoint and
1130              * bounding violating coordinate.  The check is pretty simple
1131              * because the curve passed to the DrawMonotonicCubic already
1132              * split into the monotonic in X and Y pieces
1133              */
1134 
1135             /* Bounding x2 by xe */
1136             if (((xe-x2)^dx) < 0) {
1137                 x2 = xe;
1138             }
1139 
1140             /* Bounding y2 by ye */
1141             if (((ye-y2)^dy) < 0) {
1142                 y2 = ye;
1143             }
1144 
1145             hnd->pProcessFixedLine(hnd, x1, y1, x2, y2, pixelInfo, checkBounds,
1146                                    JNI_FALSE);
1147         } else {
1148             hnd->pProcessFixedLine(hnd, x2, y2, xe, ye, pixelInfo, checkBounds,
1149                                    JNI_FALSE);
1150         }
1151     }
1152 }
1153 
1154 /*
1155  * Checking size of the cubic curves and split them if necessary.
1156  * Calling DrawMonotonicCubic for the curves of the appropriate size.
1157  * Note: coords array could be changed
1158  */
1159 static void ProcessMonotonicCubic(ProcessHandler* hnd,
1160                                   jfloat *coords,
1161                                   jint* pixelInfo) {
1162 
1163     jfloat coords1[8];
1164     jfloat tx, ty;
1165     jfloat xMin, xMax;
1166     jfloat yMin, yMax;
1167 
1168     xMin = xMax = coords[0];
1169     yMin = yMax = coords[1];
1170 
1171     CALC_MIN(xMin, coords[2]);
1172     CALC_MAX(xMax, coords[2]);
1173     CALC_MIN(yMin, coords[3]);
1174     CALC_MAX(yMax, coords[3]);
1175     CALC_MIN(xMin, coords[4]);
1176     CALC_MAX(xMax, coords[4]);
1177     CALC_MIN(yMin, coords[5]);
1178     CALC_MAX(yMax, coords[5]);
1179     CALC_MIN(xMin, coords[6]);
1180     CALC_MAX(xMax, coords[6]);
1181     CALC_MIN(yMin, coords[7]);
1182     CALC_MAX(yMax, coords[7]);
1183 
1184     if (hnd->clipMode == PH_MODE_DRAW_CLIP) {
1185 
1186        /* In case of drawing we could just skip curves which are completely
1187         * out of bounds
1188         */
1189         if (hnd->dhnd->xMaxf < xMin || hnd->dhnd->xMinf > xMax ||
1190             hnd->dhnd->yMaxf < yMin || hnd->dhnd->yMinf > yMax) {
1191             return;
1192         }
1193     } else {
1194 
1195        /* In case of filling we could skip curves which are above,
1196         * below and behind the right boundary of the visible area
1197         */
1198 
1199         if (hnd->dhnd->yMaxf < yMin || hnd->dhnd->yMinf > yMax ||
1200             hnd->dhnd->xMaxf < xMin)
1201         {
1202             return;
1203         }
1204 
1205        /* We could clamp x coordinates to the corresponding boundary
1206         * if the curve is completely behind the left one
1207         */
1208 
1209         if (hnd->dhnd->xMinf > xMax) {
1210             coords[0] = coords[2] = coords[4] = coords[6] =
1211                 hnd->dhnd->xMinf;
1212         }
1213     }
1214 
1215     if (xMax - xMin > MAX_CUB_SIZE || yMax - yMin > MAX_CUB_SIZE) {
1216         coords1[6] = coords[6];
1217         coords1[7] = coords[7];
1218         coords1[4] = (coords[4] + coords[6])/2.0f;
1219         coords1[5] = (coords[5] + coords[7])/2.0f;
1220         tx = (coords[2] + coords[4])/2.0f;
1221         ty = (coords[3] + coords[5])/2.0f;
1222         coords1[2] = (tx + coords1[4])/2.0f;
1223         coords1[3] = (ty + coords1[5])/2.0f;
1224         coords[2] =  (coords[0] + coords[2])/2.0f;
1225         coords[3] =  (coords[1] + coords[3])/2.0f;
1226         coords[4] = (coords[2] + tx)/2.0f;
1227         coords[5] = (coords[3] + ty)/2.0f;
1228         coords[6]=coords1[0]=(coords[4] + coords1[2])/2.0f;
1229         coords[7]=coords1[1]=(coords[5] + coords1[3])/2.0f;
1230 
1231         ProcessMonotonicCubic(hnd, coords, pixelInfo);
1232 
1233         ProcessMonotonicCubic(hnd, coords1, pixelInfo);
1234 
1235     } else {
1236         DrawMonotonicCubic(hnd, coords,
1237                            /* Set checkBounds parameter if curve intersects
1238                             * boundary of the visible area. We know that the
1239                             * curve is visible, so the check is pretty simple
1240                             */
1241                            hnd->dhnd->xMinf > xMin || hnd->dhnd->xMaxf < xMax ||
1242                            hnd->dhnd->yMinf > yMin || hnd->dhnd->yMaxf < yMax,
1243                            pixelInfo);
1244     }
1245 }
1246 
1247 /*
1248  * Bite the piece of the cubic curve from start point till the point
1249  * corresponding to the specified parameter then call ProcessMonotonicCubic for
1250  * the bitten part.
1251  * Note: coords array will be changed
1252  */
1253 static void ProcessFirstMonotonicPartOfCubic(ProcessHandler* hnd,
1254                                              jfloat* coords, jint* pixelInfo,
1255                                              jfloat t)
1256 {
1257     jfloat coords1[8];
1258     jfloat tx, ty;
1259 
1260     coords1[0] = coords[0];
1261     coords1[1] = coords[1];
1262     tx = coords[2] + t*(coords[4] - coords[2]);
1263     ty = coords[3] + t*(coords[5] - coords[3]);
1264     coords1[2] =  coords[0] + t*(coords[2] - coords[0]);
1265     coords1[3] =  coords[1] + t*(coords[3] - coords[1]);
1266     coords1[4] = coords1[2] + t*(tx - coords1[2]);
1267     coords1[5] = coords1[3] + t*(ty - coords1[3]);
1268     coords[4] = coords[4] + t*(coords[6] - coords[4]);
1269     coords[5] = coords[5] + t*(coords[7] - coords[5]);
1270     coords[2] = tx + t*(coords[4] - tx);
1271     coords[3] = ty + t*(coords[5] - ty);
1272     coords[0]=coords1[6]=coords1[4] + t*(coords[2] - coords1[4]);
1273     coords[1]=coords1[7]=coords1[5] + t*(coords[3] - coords1[5]);
1274 
1275     ProcessMonotonicCubic(hnd, coords1, pixelInfo);
1276 }
1277 
1278 /*
1279  * Split cubic curve into monotonic in X and Y parts. Calling ProcessCubic for
1280  * each monotonic piece of the curve.
1281  *
1282  * Note: coords array could be changed
1283  */
1284 static void ProcessCubic(ProcessHandler* hnd, jfloat* coords, jint* pixelInfo)
1285 {
1286     /* Temporary array for holding parameters corresponding to the extreme in X
1287      * and Y points. The values are inside the (0,1) range (0 and 1 excluded)
1288      * and in ascending order.
1289      */
1290     double params[4];
1291     jint cnt = 0, i;
1292 
1293     /* Simple check for monotonicity in X before searching for the extreme
1294      * points of the X(t) function. We first check if the curve is monotonic in
1295      * X by seeing if all of the X coordinates are strongly ordered.
1296      */
1297     if ((coords[0] > coords[2] || coords[2] > coords[4] ||
1298          coords[4] > coords[6]) &&
1299         (coords[0] < coords[2] || coords[2] < coords[4] ||
1300          coords[4] < coords[6]))
1301     {
1302         /* Searching for extreme points of the X(t) function  by solving
1303          * dX(t)
1304          * ----  = 0 equation
1305          *  dt
1306          */
1307         double ax = -coords[0] + 3*coords[2] - 3*coords[4] + coords[6];
1308         double bx = 2*(coords[0] - 2*coords[2] + coords[4]);
1309         double cx = -coords[0] + coords[2];
1310 
1311         SOLVEQUADINRANGE(ax,bx,cx,params,cnt);
1312     }
1313 
1314     /* Simple check for monotonicity in Y before searching for the extreme
1315      * points of the Y(t) function. We first check if the curve is monotonic in
1316      * Y by seeing if all of the Y coordinates are strongly ordered.
1317      */
1318     if ((coords[1] > coords[3] || coords[3] > coords[5] ||
1319          coords[5] > coords[7]) &&
1320         (coords[1] < coords[3] || coords[3] < coords[5] ||
1321          coords[5] < coords[7]))
1322     {
1323         /* Searching for extreme points of the Y(t) function by solving
1324          * dY(t)
1325          * ----- = 0 equation
1326          *  dt
1327          */
1328         double ay = -coords[1] + 3*coords[3] - 3*coords[5] + coords[7];
1329         double by = 2*(coords[1] - 2*coords[3] + coords[5]);
1330         double cy = -coords[1] + coords[3];
1331 
1332         SOLVEQUADINRANGE(ay,by,cy,params,cnt);
1333     }
1334 
1335     if (cnt > 0) {
1336         /* Sorting parameter values corresponding to the extremum points of
1337          * the curve. We are using insertion sort because of tiny size of the
1338          * array.
1339          */
1340         jint j;
1341 
1342         for(i = 1; i < cnt; i++) {
1343             double value = params[i];
1344             for (j = i - 1; j >= 0 && params[j] > value; j--) {
1345                 params[j + 1] = params[j];
1346             }
1347             params[j + 1] = value;
1348         }
1349 
1350         /* Processing obtained monotonic parts */
1351         ProcessFirstMonotonicPartOfCubic(hnd, coords, pixelInfo,
1352                                          (jfloat)params[0]);
1353         for (i = 1; i < cnt; i++) {
1354             double param = params[i] - params[i-1];
1355             if (param > 0) {
1356                 ProcessFirstMonotonicPartOfCubic(hnd, coords, pixelInfo,
1357                     /* Scale parameter to match with rest of the curve */
1358                     (float)(param/(1.0 - params[i - 1])));
1359             }
1360         }
1361     }
1362 
1363     ProcessMonotonicCubic(hnd,coords,pixelInfo);
1364 }
1365 
1366 static void ProcessLine(ProcessHandler* hnd,
1367                         jfloat *coord1, jfloat *coord2, jint* pixelInfo) {
1368 
1369     jfloat xMin, yMin, xMax, yMax;
1370     jint X1, Y1, X2, Y2, X3, Y3, res;
1371     jboolean clipped = JNI_FALSE;
1372     jfloat x1 = coord1[0];
1373     jfloat y1 = coord1[1];
1374     jfloat x2 = coord2[0];
1375     jfloat y2 = coord2[1];
1376     jfloat x3,y3;
1377 
1378     jboolean lastClipped;
1379 
1380     xMin = hnd->dhnd->xMinf;
1381     yMin = hnd->dhnd->yMinf;
1382     xMax = hnd->dhnd->xMaxf;
1383     yMax = hnd->dhnd->yMaxf;
1384 
1385     TESTANDCLIP(yMin, yMax, y1, x1, y2, x2, jfloat, res);
1386     if (res == CRES_INVISIBLE) return;
1387     clipped = IS_CLIPPED(res);
1388     TESTANDCLIP(yMin, yMax, y2, x2, y1, x1, jfloat, res);
1389     if (res == CRES_INVISIBLE) return;
1390     lastClipped = IS_CLIPPED(res);
1391     clipped = clipped || lastClipped;
1392 
1393     if (hnd->clipMode == PH_MODE_DRAW_CLIP) {
1394         TESTANDCLIP(xMin, xMax,
1395                     x1, y1, x2, y2, jfloat, res);
1396         if (res == CRES_INVISIBLE) return;
1397         clipped = clipped || IS_CLIPPED(res);
1398         TESTANDCLIP(xMin, xMax,
1399                     x2, y2, x1, y1, jfloat, res);
1400         if (res == CRES_INVISIBLE) return;
1401         lastClipped = lastClipped || IS_CLIPPED(res);
1402         clipped = clipped || lastClipped;
1403         X1 = (jint)(x1*MDP_MULT);
1404         Y1 = (jint)(y1*MDP_MULT);
1405         X2 = (jint)(x2*MDP_MULT);
1406         Y2 = (jint)(y2*MDP_MULT);
1407 
1408         hnd->pProcessFixedLine(hnd, X1, Y1, X2, Y2, pixelInfo,
1409                                clipped, /* enable boundary checking in case
1410                                            of clipping to avoid entering
1411                                            out of bounds which could
1412                                            happens during rounding
1413                                          */
1414                                lastClipped /* Notify pProcessFixedLine that
1415                                               this is the end of the
1416                                               subpath (because of exiting
1417                                               out of boundaries)
1418                                             */
1419                                );
1420     } else {
1421         /* Clamping starting from first vertex of the processed segment
1422          */
1423         CLIPCLAMP(xMin, xMax, x1, y1, x2, y2, x3, y3, jfloat, res);
1424         X1 = (jint)(x1*MDP_MULT);
1425         Y1 = (jint)(y1*MDP_MULT);
1426 
1427         /* Clamping only by left boundary */
1428         if (res == CRES_MIN_CLIPPED) {
1429             X3 = (jint)(x3*MDP_MULT);
1430             Y3 = (jint)(y3*MDP_MULT);
1431             hnd->pProcessFixedLine(hnd, X3, Y3, X1, Y1, pixelInfo,
1432                                    JNI_FALSE, lastClipped);
1433 
1434         } else if (res == CRES_INVISIBLE) {
1435             return;
1436         }
1437 
1438         /* Clamping starting from last vertex of the processed segment
1439          */
1440         CLIPCLAMP(xMin, xMax, x2, y2, x1, y1, x3, y3, jfloat, res);
1441 
1442         /* Checking if there was a clip by right boundary */
1443         lastClipped = lastClipped || (res == CRES_MAX_CLIPPED);
1444 
1445         X2 = (jint)(x2*MDP_MULT);
1446         Y2 = (jint)(y2*MDP_MULT);
1447         hnd->pProcessFixedLine(hnd, X1, Y1, X2, Y2, pixelInfo,
1448                                JNI_FALSE, lastClipped);
1449 
1450         /* Clamping only by left boundary */
1451         if (res == CRES_MIN_CLIPPED) {
1452             X3 = (jint)(x3*MDP_MULT);
1453             Y3 = (jint)(y3*MDP_MULT);
1454             hnd->pProcessFixedLine(hnd, X2, Y2, X3, Y3, pixelInfo,
1455                                    JNI_FALSE, lastClipped);
1456         }
1457     }
1458 }
1459 
1460 jboolean ProcessPath(ProcessHandler* hnd,
1461                      jfloat transXf, jfloat transYf,
1462                      jfloat* coords, jint maxCoords,
1463                      jbyte* types, jint numTypes)
1464 {
1465     jfloat tCoords[8];
1466     jfloat closeCoord[2];
1467     jint pixelInfo[5];
1468     jboolean skip = JNI_FALSE;
1469     jboolean subpathStarted = JNI_FALSE;
1470     jfloat lastX, lastY;
1471     int i, index = 0;
1472 
1473     pixelInfo[0] = 0;
1474 
1475     /* Adding support of the KEY_STROKE_CONTROL rendering hint.
1476      * Now we are supporting two modes: "pixels at centers" and
1477      * "pixels at corners".
1478      * First one is disabled by default but could be enabled by setting
1479      * VALUE_STROKE_PURE to the rendering hint. It means that pixel at the
1480      * screen (x,y) has (x + 0.5, y + 0.5) float coordinates.
1481      *
1482      * Second one is enabled by default and means straightforward mapping
1483      * (x,y) --> (x,y)
1484      *
1485      */
1486     if (hnd->stroke == PH_STROKE_PURE) {
1487         closeCoord[0] = -0.5f;
1488         closeCoord[1] = -0.5f;
1489         transXf -= 0.5;
1490         transYf -= 0.5;
1491     } else {
1492         closeCoord[0] = 0.0f;
1493         closeCoord[1] = 0.0f;
1494     }
1495 
1496     /* Adjusting boundaries to the capabilities of the ProcessPath code */
1497     ADJUST(hnd->dhnd->xMin, LOWER_OUT_BND, UPPER_OUT_BND);
1498     ADJUST(hnd->dhnd->yMin, LOWER_OUT_BND, UPPER_OUT_BND);
1499     ADJUST(hnd->dhnd->xMax, LOWER_OUT_BND, UPPER_OUT_BND);
1500     ADJUST(hnd->dhnd->yMax, LOWER_OUT_BND, UPPER_OUT_BND);
1501 
1502 
1503     /*                Setting up fractional clipping box
1504      *
1505      * We are using following float -> int mapping:
1506      *
1507      *      xi = floor(xf + 0.5)
1508      *
1509      * So, fractional values that hit the [xmin, xmax) integer interval will be
1510      * situated inside the [xmin-0.5, xmax - 0.5) fractional interval. We are
1511      * using EPSF constant to provide that upper boundary is not included.
1512      */
1513     hnd->dhnd->xMinf = hnd->dhnd->xMin - 0.5f;
1514     hnd->dhnd->yMinf = hnd->dhnd->yMin - 0.5f;
1515     hnd->dhnd->xMaxf = hnd->dhnd->xMax - 0.5f - EPSF;
1516     hnd->dhnd->yMaxf = hnd->dhnd->yMax - 0.5f - EPSF;
1517 
1518 
1519     for (i = 0; i < numTypes; i++) {
1520         switch (types[i]) {
1521             case java_awt_geom_PathIterator_SEG_MOVETO:
1522                 if (index + 2 <= maxCoords) {
1523                     /* Performing closing of the unclosed segments */
1524                     if (subpathStarted & !skip) {
1525                         if (hnd->clipMode == PH_MODE_FILL_CLIP) {
1526                             if (tCoords[0] != closeCoord[0] ||
1527                                 tCoords[1] != closeCoord[1])
1528                             {
1529                                 ProcessLine(hnd, tCoords, closeCoord,
1530                                             pixelInfo);
1531                             }
1532                         }
1533                         hnd->pProcessEndSubPath(hnd);
1534                     }
1535 
1536                     tCoords[0] = coords[index++] + transXf;
1537                     tCoords[1] = coords[index++] + transYf;
1538 
1539                     /* Checking SEG_MOVETO coordinates if they are out of the
1540                      * [LOWER_BND, UPPER_BND] range.  This check also handles
1541                      * NaN and Infinity values. Skipping next path segment in
1542                      * case of invalid data.
1543                      */
1544 
1545                     if (tCoords[0] < UPPER_BND &&
1546                         tCoords[0] > LOWER_BND &&
1547                         tCoords[1] < UPPER_BND &&
1548                         tCoords[1] > LOWER_BND)
1549                     {
1550                         subpathStarted = JNI_TRUE;
1551                         skip = JNI_FALSE;
1552                         closeCoord[0] = tCoords[0];
1553                         closeCoord[1] = tCoords[1];
1554                     } else {
1555                         skip = JNI_TRUE;
1556                     }
1557                 } else {
1558                     return JNI_FALSE;
1559                 }
1560                 break;
1561             case java_awt_geom_PathIterator_SEG_LINETO:
1562                 if (index + 2 <= maxCoords) {
1563                     lastX = tCoords[2] = coords[index++] + transXf;
1564                     lastY = tCoords[3] = coords[index++] + transYf;
1565 
1566                     /* Checking SEG_LINETO coordinates if they are out of the
1567                      * [LOWER_BND, UPPER_BND] range.  This check also handles
1568                      * NaN and Infinity values. Ignoring current path segment
1569                      * in case  of invalid data. If segment is skipped its
1570                      * endpoint (if valid) is used to begin new subpath.
1571                      */
1572 
1573                     if (lastX < UPPER_BND &&
1574                         lastX > LOWER_BND &&
1575                         lastY < UPPER_BND &&
1576                         lastY > LOWER_BND)
1577                     {
1578                         if (skip) {
1579                             tCoords[0] = closeCoord[0] = lastX;
1580                             tCoords[1] = closeCoord[1] = lastY;
1581                             subpathStarted = JNI_TRUE;
1582                             skip = JNI_FALSE;
1583                         } else {
1584                             ProcessLine(hnd, tCoords, tCoords + 2,
1585                                         pixelInfo);
1586                             tCoords[0] = lastX;
1587                             tCoords[1] = lastY;
1588                         }
1589                     }
1590                 } else {
1591                     return JNI_FALSE;
1592                 }
1593                 break;
1594             case java_awt_geom_PathIterator_SEG_QUADTO:
1595                 if (index + 4 <= maxCoords) {
1596                     tCoords[2] = coords[index++] + transXf;
1597                     tCoords[3] = coords[index++] + transYf;
1598                     lastX = tCoords[4] = coords[index++] + transXf;
1599                     lastY = tCoords[5] = coords[index++] + transYf;
1600 
1601                     /* Checking SEG_QUADTO coordinates if they are out of the
1602                      * [LOWER_BND, UPPER_BND] range.  This check also handles
1603                      * NaN and Infinity values. Ignoring current path segment
1604                      * in case  of invalid endpoints's data.  Equivalent to
1605                      * the SEG_LINETO if endpoint coordinates are valid but
1606                      * there are invalid data among other coordinates
1607                      */
1608 
1609                     if (lastX < UPPER_BND &&
1610                         lastX > LOWER_BND &&
1611                         lastY < UPPER_BND &&
1612                         lastY > LOWER_BND)
1613                     {
1614                         if (skip) {
1615                             tCoords[0] = closeCoord[0] = lastX;
1616                             tCoords[1] = closeCoord[1] = lastY;
1617                             subpathStarted = JNI_TRUE;
1618                             skip = JNI_FALSE;
1619                         } else {
1620                             if (tCoords[2] < UPPER_BND &&
1621                                 tCoords[2] > LOWER_BND &&
1622                                 tCoords[3] < UPPER_BND &&
1623                                 tCoords[3] > LOWER_BND)
1624                             {
1625                                 ProcessQuad(hnd, tCoords, pixelInfo);
1626                             } else {
1627                                 ProcessLine(hnd, tCoords,
1628                                             tCoords + 4, pixelInfo);
1629                             }
1630                             tCoords[0] = lastX;
1631                             tCoords[1] = lastY;
1632                         }
1633                     }
1634                 } else {
1635                     return JNI_FALSE;
1636                 }
1637                 break;
1638             case java_awt_geom_PathIterator_SEG_CUBICTO:
1639                     if (index + 6 <= maxCoords) {
1640                     tCoords[2] = coords[index++] + transXf;
1641                     tCoords[3] = coords[index++] + transYf;
1642                     tCoords[4] = coords[index++] + transXf;
1643                     tCoords[5] = coords[index++] + transYf;
1644                     lastX = tCoords[6] = coords[index++] + transXf;
1645                     lastY = tCoords[7] = coords[index++] + transYf;
1646 
1647                     /* Checking SEG_CUBICTO coordinates if they are out of the
1648                      * [LOWER_BND, UPPER_BND] range.  This check also handles
1649                      * NaN and Infinity values. Ignoring current path segment
1650                      * in case  of invalid endpoints's data.  Equivalent to
1651                      * the SEG_LINETO if endpoint coordinates are valid but
1652                      * there are invalid data among other coordinates
1653                      */
1654 
1655                     if (lastX < UPPER_BND &&
1656                         lastX > LOWER_BND &&
1657                         lastY < UPPER_BND &&
1658                         lastY > LOWER_BND)
1659                     {
1660                         if (skip) {
1661                             tCoords[0] = closeCoord[0] = tCoords[6];
1662                             tCoords[1] = closeCoord[1] = tCoords[7];
1663                             subpathStarted = JNI_TRUE;
1664                             skip = JNI_FALSE;
1665                         } else {
1666                             if (tCoords[2] < UPPER_BND &&
1667                                 tCoords[2] > LOWER_BND &&
1668                                 tCoords[3] < UPPER_BND &&
1669                                 tCoords[3] > LOWER_BND &&
1670                                 tCoords[4] < UPPER_BND &&
1671                                 tCoords[4] > LOWER_BND &&
1672                                 tCoords[5] < UPPER_BND &&
1673                                 tCoords[5] > LOWER_BND)
1674                             {
1675                                 ProcessCubic(hnd, tCoords, pixelInfo);
1676                             } else {
1677                                 ProcessLine(hnd, tCoords, tCoords + 6,
1678                                             pixelInfo);
1679                             }
1680                             tCoords[0] = lastX;
1681                             tCoords[1] = lastY;
1682                         }
1683                     }
1684                 } else {
1685                     return JNI_FALSE;
1686                 }
1687                 break;
1688             case java_awt_geom_PathIterator_SEG_CLOSE:
1689                 if (subpathStarted && !skip) {
1690                     skip = JNI_FALSE;
1691                     if (tCoords[0] != closeCoord[0] ||
1692                         tCoords[1] != closeCoord[1])
1693                     {
1694                         ProcessLine(hnd, tCoords, closeCoord, pixelInfo);
1695                         /* Storing last path's point for using in
1696                          * following segments without initial moveTo
1697                          */
1698                         tCoords[0] = closeCoord[0];
1699                         tCoords[1] = closeCoord[1];
1700                     }
1701 
1702                     hnd->pProcessEndSubPath(hnd);
1703                 }
1704 
1705                 break;
1706         }
1707     }
1708 
1709     /* Performing closing of the unclosed segments */
1710     if (subpathStarted & !skip) {
1711         if (hnd->clipMode == PH_MODE_FILL_CLIP) {
1712             if (tCoords[0] != closeCoord[0] ||
1713                 tCoords[1] != closeCoord[1])
1714             {
1715                 ProcessLine(hnd, tCoords, closeCoord,
1716                             pixelInfo);
1717             }
1718         }
1719         hnd->pProcessEndSubPath(hnd);
1720     }
1721 
1722     return JNI_TRUE;
1723 }
1724 
1725 /* TODO Add checking of the result of the malloc/realloc functions to handle
1726  * out of memory error and don't leak earlier allocated data
1727  */
1728 
1729 
1730 #define ALLOC(ptr, type, n) \
1731     ptr = (type *)malloc((n)*sizeof(type))
1732 #define REALLOC(ptr, type, n) \
1733     ptr = (type *)realloc(ptr, (n)*sizeof(type))
1734 
1735 
1736 struct _Edge;
1737 
1738 typedef struct _Point {
1739     jint x;
1740     jint y;
1741     jboolean lastPoint;
1742     struct _Point* prev;
1743     struct _Point* next;
1744     struct _Point* nextByY;
1745     jboolean endSL;
1746     struct _Edge* edge;
1747 } Point;
1748 
1749 
1750 typedef struct _Edge {
1751     jint          x;
1752     jint          dx;
1753     Point*        p;
1754     jint          dir;
1755     struct _Edge* prev;
1756     struct _Edge* next;
1757 } Edge;
1758 
1759 /* Size of the default buffer in the FillData structure. This buffer is
1760  * replaced with heap allocated in case of large paths.
1761  */
1762 #define DF_MAX_POINT 256
1763 
1764 /* Following structure accumulates points of the non-continuous flattened
1765  * path during iteration through the origin path's segments . The end
1766  * of the each subpath is marked as lastPoint flag set at the last point
1767  */
1768 
1769 typedef struct {
1770     Point   *plgPnts;
1771     Point   dfPlgPnts[DF_MAX_POINT];
1772     jint    plgSize;
1773     jint    plgMax;
1774     jint    plgYMin;
1775     jint    plgYMax;
1776 } FillData;
1777 
1778 #define FD_INIT(PTR)                                                        \
1779     do {                                                                    \
1780         (PTR)->plgPnts = (PTR)->dfPlgPnts;                                  \
1781         (PTR)->plgSize = 0;                                                 \
1782         (PTR)->plgMax = DF_MAX_POINT;                                       \
1783     } while(0)
1784 
1785 #define FD_ADD_POINT(PTR, X, Y, LASTPT)                                     \
1786     do {                                                                    \
1787         Point* _pnts = (PTR)->plgPnts;                                      \
1788         jint _size = (PTR)->plgSize;                                        \
1789         if (_size >= (PTR)->plgMax) {                                       \
1790             jint newMax = (PTR)->plgMax*2;                                  \
1791             if ((PTR)->plgPnts == (PTR)->dfPlgPnts) {                       \
1792                 (PTR)->plgPnts = (Point*)malloc(newMax*sizeof(Point));      \
1793                 memcpy((PTR)->plgPnts, _pnts, _size*sizeof(Point));         \
1794             } else {                                                        \
1795                 (PTR)->plgPnts = (Point*)realloc(                           \
1796                     _pnts, newMax*sizeof(Point));                           \
1797             }                                                               \
1798             _pnts = (PTR)->plgPnts;                                         \
1799             (PTR)->plgMax = newMax;                                         \
1800         }                                                                   \
1801         _pnts += _size;                                                     \
1802         _pnts->x = X;                                                       \
1803         _pnts->y = Y;                                                       \
1804         _pnts->lastPoint = LASTPT;                                          \
1805         if (_size) {                                                        \
1806             if ((PTR)->plgYMin > Y) (PTR)->plgYMin = Y;                     \
1807             if ((PTR)->plgYMax < Y) (PTR)->plgYMax = Y;                     \
1808         } else {                                                            \
1809             (PTR)->plgYMin = Y;                                             \
1810             (PTR)->plgYMax = Y;                                             \
1811         }                                                                   \
1812         (PTR)->plgSize = _size + 1;                                         \
1813     } while(0)
1814 
1815 
1816 #define FD_FREE_POINTS(PTR)                                                 \
1817     do {                                                                    \
1818         if ((PTR)->plgPnts != (PTR)->dfPlgPnts) {                           \
1819             free((PTR)->plgPnts);                                           \
1820         }                                                                   \
1821     } while(0)
1822 
1823 #define FD_IS_EMPTY(PTR) (!((PTR)->plgSize))
1824 
1825 #define FD_IS_ENDED(PTR) ((PTR)->plgPnts[(PTR)->plgSize - 1].lastPoint)
1826 
1827 #define FD_SET_ENDED(PTR)                                                   \
1828     do {                                                                    \
1829         (PTR)->plgPnts[(PTR)->plgSize - 1].lastPoint = JNI_TRUE;            \
1830     } while(0)
1831 
1832 #define PFD(HND) ((FillData*)(HND)->pData)
1833 
1834 /* Bubble sorting in the ascending order of the linked list. This
1835  * implementation stops processing the list if there were no changes during the
1836  * previous pass.
1837  *
1838  * LIST - ptr to the ptr to the first element of the list
1839  * ETYPE - type of the element in the list
1840  * NEXT - accessor to the next field in the list element
1841  * GET_LKEY - accessor to the key of the list element
1842  */
1843 #define LBUBBLE_SORT(LIST, ETYPE, NEXT, GET_LKEY)                           \
1844     do {                                                                    \
1845         ETYPE *p, *q, *r, *s = NULL, *temp ;                                \
1846         jint wasSwap = 1;                                                   \
1847         /* r precedes p and s points to the node up to which comparisons    \
1848          * are to be made */                                                \
1849         while ( s != NEXT(*LIST) && wasSwap) {                              \
1850             r = p = *LIST;                                                  \
1851             q = NEXT(p);                                                    \
1852             wasSwap = 0;                                                    \
1853             while ( p != s ) {                                              \
1854                 if (GET_LKEY(p) >= GET_LKEY(q)) {                           \
1855                     wasSwap = 1;                                            \
1856                     if ( p == *LIST ) {                                     \
1857                         temp = NEXT(q);                                     \
1858                         NEXT(q) = p ;                                       \
1859                         NEXT(p) = temp ;                                    \
1860                         *LIST = q ;                                         \
1861                         r = q ;                                             \
1862                     } else {                                                \
1863                         temp = NEXT(q);                                     \
1864                         NEXT(q) = p ;                                       \
1865                         NEXT(p) = temp ;                                    \
1866                         NEXT(r) = q ;                                       \
1867                         r = q ;                                             \
1868                     }                                                       \
1869                 } else {                                                    \
1870                     r = p ;                                                 \
1871                     p = NEXT(p);                                            \
1872                 }                                                           \
1873                 q = NEXT(p);                                                \
1874                 if ( q == s ) s = p ;                                       \
1875             }                                                               \
1876         }                                                                   \
1877     } while(0);
1878 
1879 /* Accessors for the Edge structure to work with LBUBBLE_SORT */
1880 #define GET_ACTIVE_KEY(a) (a->x)
1881 #define GET_ACTIVE_NEXT(a) ((a)->next)
1882 
1883 /* TODO: Implement stack/heap allocation technique for active edges
1884  */
1885 #define DELETE_ACTIVE(head,pnt)                                     \
1886 do {                                                                \
1887     Edge *prevp = pnt->prev;                                        \
1888     Edge *nextp = pnt->next;                                        \
1889     if (prevp) {                                                    \
1890         prevp->next = nextp;                                        \
1891     } else {                                                        \
1892         head = nextp;                                               \
1893     }                                                               \
1894     if (nextp) {                                                    \
1895         nextp->prev = prevp;                                        \
1896     }                                                               \
1897 } while(0);
1898 
1899 #define INSERT_ACTIVE(head,pnt,cy)                                  \
1900 do {                                                                \
1901     Point *np = pnt->next;                                          \
1902     Edge *ne = active + nact;                                       \
1903     if (pnt->y == np->y) {                                          \
1904         /* Skipping horizontal segments */                          \
1905         break;                                                      \
1906     } else {                                                        \
1907         jint dX = np->x - pnt->x;                                   \
1908         jint dY = np->y - pnt->y;                                   \
1909         jint dy;                                                    \
1910         if (pnt->y < np->y) {                                       \
1911             ne->dir = -1;                                           \
1912             ne->p = pnt;                                            \
1913             ne->x = pnt->x;                                         \
1914             dy = cy - pnt->y;                                       \
1915         } else { /* pnt->y > np->y */                               \
1916             ne->dir = 1;                                            \
1917             ne->p = np;                                             \
1918             ne->x = np->x;                                          \
1919             dy = cy - np->y;                                        \
1920         }                                                           \
1921                                                                     \
1922         /* We need to worry only about dX because dY is in        */\
1923         /* denominator and abs(dy) < MDP_MULT (cy is a first      */\
1924         /* scanline of the scan converted segment and we subtract */\
1925         /* y coordinate of the nearest segment's end from it to   */\
1926         /* obtain dy)                                             */\
1927         if (ABS32(dX) > CALC_BND) {                                 \
1928             ne->dx = (jint)((((jdouble)dX)*MDP_MULT)/dY);           \
1929             ne->x += (jint)((((jdouble)dX)*dy)/dY);                 \
1930         } else {                                                    \
1931             ne->dx = ((dX)<<MDP_PREC)/dY;                           \
1932             ne->x += (dX*dy)/dY;                                    \
1933         }                                                           \
1934     }                                                               \
1935     ne->next = head;                                                \
1936     ne->prev = NULL;                                                \
1937     if (head) {                                                     \
1938         head->prev = ne;                                            \
1939     }                                                               \
1940     head = active + nact;                                           \
1941     pnt->edge = head;                                               \
1942     nact++;                                                         \
1943 } while(0);
1944 
1945 void FillPolygon(ProcessHandler* hnd,
1946                  jint fillRule) {
1947     jint k, y, xl, xr;
1948     jint drawing;
1949     Edge* activeList, *active;
1950     Edge* curEdge, *prevEdge;
1951     jint nact;
1952     jint n;
1953     Point* pt, *curpt, *ept;
1954     Point** yHash;
1955     Point** curHash;
1956     jint rightBnd = hnd->dhnd->xMax - 1;
1957     FillData* pfd = (FillData*)(hnd->pData);
1958     jint yMin = pfd->plgYMin;
1959     jint yMax = pfd->plgYMax;
1960     jint hashSize = ((yMax - yMin)>>MDP_PREC) + 4;
1961 
1962     /* Because of support of the KEY_STROKE_CONTROL hint we are performing
1963      * shift of the coordinates at the higher level
1964      */
1965     jint hashOffset = ((yMin - 1) & MDP_W_MASK);
1966 
1967 // TODO creating lists using fake first element to avoid special casing of
1968 // the first element in the list (which otherwise should be performed in each
1969 // list operation)
1970 
1971     /* Winding counter */
1972     jint counter;
1973 
1974     /* Calculating mask to be applied to the winding counter */
1975     jint counterMask =
1976         (fillRule == java_awt_geom_PathIterator_WIND_NON_ZERO)? -1:1;
1977     pt = pfd->plgPnts;
1978     n = pfd->plgSize;
1979 
1980     if (n <=1) return;
1981 
1982     ALLOC(yHash, Point*, hashSize);
1983     for (k = 0; k < hashSize; k++) {
1984         yHash[k] = NULL;
1985     }
1986 
1987     ALLOC(active, Edge, n);
1988 
1989     /* Creating double linked list (prev, next links) describing path order and
1990      * hash table with points which fall between scanlines. nextByY link is
1991      * used for the points which are between same scanlines. Scanlines are
1992      * passed through the centers of the pixels.
1993      */
1994     curpt = pt;
1995     curpt->prev = NULL;
1996     ept = pt + n - 1;
1997     for (curpt = pt; curpt != ept; curpt++) {
1998         Point* nextpt = curpt + 1;
1999         curHash =  yHash + ((curpt->y - hashOffset - 1) >> MDP_PREC);
2000         curpt->nextByY = *curHash;
2001         *curHash = curpt;
2002         curpt->next = nextpt;
2003         nextpt->prev = curpt;
2004         curpt->edge = NULL;
2005     }
2006 
2007     curHash =  yHash + ((ept->y - hashOffset - 1) >> MDP_PREC);
2008     ept->nextByY = *curHash;
2009     *curHash = ept;
2010     ept->next = NULL;
2011     ept->edge = NULL;
2012     nact = 0;
2013 
2014     activeList = NULL;
2015     for (y=hashOffset + MDP_MULT,k = 0;
2016          y<=yMax && k < hashSize; y += MDP_MULT, k++)
2017     {
2018         for(pt = yHash[k];pt; pt=pt->nextByY) {
2019             /* pt->y should be inside hashed interval
2020              * assert(y-MDP_MULT <= pt->y && pt->y < y);
2021              */
2022             if (pt->prev && !pt->prev->lastPoint) {
2023                 if (pt->prev->edge && pt->prev->y <= y) {
2024                     DELETE_ACTIVE(activeList, pt->prev->edge);
2025                     pt->prev->edge = NULL;
2026                 } else  if (pt->prev->y > y) {
2027                     INSERT_ACTIVE(activeList, pt->prev, y);
2028                 }
2029             }
2030 
2031             if (!pt->lastPoint && pt->next) {
2032                 if (pt->edge && pt->next->y <= y) {
2033                     DELETE_ACTIVE(activeList, pt->edge);
2034                     pt->edge = NULL;
2035                 } else if (pt->next->y > y) {
2036                     INSERT_ACTIVE(activeList, pt, y);
2037                 }
2038             }
2039         }
2040 
2041         if (!activeList) continue;
2042 
2043         /* We could not use O(N) Radix sort here because in most cases list of
2044          * edges almost sorted. So, bubble sort (O(N^2))is working much
2045          * better. Note, in case of array of edges Shell sort is more
2046          * efficient.
2047          */
2048         LBUBBLE_SORT((&activeList), Edge, GET_ACTIVE_NEXT, GET_ACTIVE_KEY);
2049 
2050         /* Correction of the back links in the double linked edge list */
2051         curEdge=activeList;
2052         prevEdge = NULL;
2053         while (curEdge) {
2054             curEdge->prev = prevEdge;
2055             prevEdge = curEdge;
2056             curEdge = curEdge->next;
2057         }
2058 
2059         xl = xr = hnd->dhnd->xMin;
2060         curEdge = activeList;
2061         counter = 0;
2062         drawing = 0;
2063         for(;curEdge; curEdge = curEdge->next) {
2064             counter += curEdge->dir;
2065             if ((counter & counterMask) && !drawing) {
2066                 xl = (curEdge->x + MDP_MULT - 1)>>MDP_PREC;
2067                 drawing = 1;
2068             }
2069 
2070             if (!(counter & counterMask) && drawing) {
2071                 xr = (curEdge->x - 1)>>MDP_PREC;
2072                 if (xl <= xr) {
2073                     hnd->dhnd->pDrawScanline(hnd->dhnd, xl, xr, y >> MDP_PREC);
2074                 }
2075                 drawing = 0;
2076             }
2077 
2078             curEdge->x += curEdge->dx;
2079         }
2080 
2081         /* Performing drawing till the right boundary (for correct rendering
2082          * shapes clipped at the right side)
2083          */
2084         if (drawing && xl <= rightBnd) {
2085             hnd->dhnd->pDrawScanline(hnd->dhnd, xl, rightBnd, y >> MDP_PREC);
2086         }
2087     }
2088     free(active);
2089     free(yHash);
2090 }
2091 
2092 
2093 
2094 void  StoreFixedLine(ProcessHandler* hnd,jint x1,jint y1,jint x2,jint y2,
2095                      jint* pixelInfo,jboolean checkBounds,
2096                      jboolean endSubPath)  {
2097     FillData* pfd;
2098     jint outXMin, outXMax, outYMin, outYMax;
2099     jint x3, y3, res;
2100 
2101     /* There is no need to round line coordinates to the forward differencing
2102      * precision anymore. Such a rounding was used for preventing the curve go
2103      * out the endpoint (this sometimes does not help). The problem was fixed
2104      * in the forward differencing loops.
2105      */
2106 
2107     if (checkBounds) {
2108         jboolean lastClipped = JNI_FALSE;
2109 
2110         /* This function is used only for filling shapes, so there is no
2111          * check for the type of clipping
2112          */
2113         outXMin = (jint)(hnd->dhnd->xMinf * MDP_MULT);
2114         outXMax = (jint)(hnd->dhnd->xMaxf * MDP_MULT);
2115         outYMin = (jint)(hnd->dhnd->yMinf * MDP_MULT);
2116         outYMax = (jint)(hnd->dhnd->yMaxf * MDP_MULT);
2117 
2118         TESTANDCLIP(outYMin, outYMax, y1, x1, y2, x2, jint, res);
2119         if (res == CRES_INVISIBLE) return;
2120         TESTANDCLIP(outYMin, outYMax, y2, x2, y1, x1, jint, res);
2121         if (res == CRES_INVISIBLE) return;
2122         lastClipped = IS_CLIPPED(res);
2123 
2124         /* Clamping starting from first vertex of the processed segment */
2125         CLIPCLAMP(outXMin, outXMax, x1, y1, x2, y2, x3, y3, jint, res);
2126 
2127         /* Clamping only by left boundary */
2128         if (res == CRES_MIN_CLIPPED) {
2129             StoreFixedLine(hnd, x3, y3, x1, y1, pixelInfo,
2130                            JNI_FALSE, lastClipped);
2131 
2132         } else if (res == CRES_INVISIBLE) {
2133             return;
2134         }
2135 
2136         /* Clamping starting from last vertex of the processed segment */
2137         CLIPCLAMP(outXMin, outXMax, x2, y2, x1, y1, x3, y3, jint, res);
2138 
2139         /* Checking if there was a clip by right boundary */
2140         lastClipped = lastClipped || (res == CRES_MAX_CLIPPED);
2141 
2142         StoreFixedLine(hnd, x1, y1, x2, y2, pixelInfo,
2143                          JNI_FALSE, lastClipped);
2144 
2145         /* Clamping only by left boundary */
2146         if (res == CRES_MIN_CLIPPED) {
2147             StoreFixedLine(hnd, x2, y2, x3, y3, pixelInfo,
2148                            JNI_FALSE, lastClipped);
2149         }
2150 
2151         return;
2152     }
2153     pfd = (FillData*)(hnd->pData);
2154 
2155     /* Adding first point of the line only in case of empty or just finished
2156      * path
2157      */
2158     if (FD_IS_EMPTY(pfd) || FD_IS_ENDED(pfd)) {
2159         FD_ADD_POINT(pfd, x1, y1, JNI_FALSE);
2160     }
2161 
2162     FD_ADD_POINT(pfd, x2, y2, JNI_FALSE);
2163 
2164     if (endSubPath) {
2165         FD_SET_ENDED(pfd);
2166     }
2167 }
2168 
2169 
2170 static void endSubPath(ProcessHandler* hnd) {
2171     FillData* pfd = (FillData*)(hnd->pData);
2172     if (!FD_IS_EMPTY(pfd)) {
2173         FD_SET_ENDED(pfd);
2174     }
2175 }
2176 
2177 static void stubEndSubPath(ProcessHandler* hnd) {
2178 }
2179 
2180 jboolean doFillPath(DrawHandler* dhnd,
2181                     jint transX, jint transY,
2182                     jfloat* coords, jint maxCoords,
2183                     jbyte* types, jint numTypes,
2184                     PHStroke stroke, jint fillRule)
2185 {
2186     jint res;
2187 
2188     FillData fillData;
2189 
2190     ProcessHandler hnd =
2191     {
2192         &StoreFixedLine,
2193         &endSubPath,
2194         NULL,
2195         PH_STROKE_DEFAULT,
2196         PH_MODE_FILL_CLIP,
2197         NULL
2198     };
2199 
2200     /* Initialization of the following fields in the declaration of the hnd
2201      * above causes warnings on sun studio compiler with  -xc99=%none option
2202      * applied (this option means compliance with C90 standard instead of C99)
2203      */
2204     hnd.dhnd = dhnd;
2205     hnd.pData = &fillData;
2206     hnd.stroke = stroke;
2207 
2208     FD_INIT(&fillData);
2209     res = ProcessPath(&hnd, (jfloat)transX, (jfloat)transY,
2210                       coords, maxCoords, types, numTypes);
2211     if (!res) {
2212         FD_FREE_POINTS(&fillData);
2213         return JNI_FALSE;
2214     }
2215     FillPolygon(&hnd, fillRule);
2216     FD_FREE_POINTS(&fillData);
2217     return JNI_TRUE;
2218 }
2219 
2220 jboolean doDrawPath(DrawHandler* dhnd,
2221                     void (*pProcessEndSubPath)(ProcessHandler*),
2222                     jint transX, jint transY,
2223                     jfloat* coords, jint maxCoords,
2224                     jbyte* types, jint numTypes, PHStroke stroke)
2225 {
2226     ProcessHandler hnd =
2227     {
2228         &ProcessFixedLine,
2229         NULL,
2230         NULL,
2231         PH_STROKE_DEFAULT,
2232         PH_MODE_DRAW_CLIP,
2233         NULL
2234     };
2235 
2236     /* Initialization of the following fields in the declaration of the hnd
2237      * above causes warnings on sun studio compiler with  -xc99=%none option
2238      * applied (this option means compliance with C90 standard instead of C99)
2239      */
2240     hnd.dhnd = dhnd;
2241     hnd.stroke = stroke;
2242 
2243     hnd.pProcessEndSubPath = (pProcessEndSubPath == NULL)?
2244         stubEndSubPath : pProcessEndSubPath;
2245     return ProcessPath(&hnd, (jfloat)transX, (jfloat)transY, coords, maxCoords,
2246                        types, numTypes);
2247 }