1 /*
   2  * Copyright (c) 2007, 2018, 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 package com.sun.marlin;
  27 
  28 import com.sun.javafx.geom.PathConsumer2D;
  29 import java.util.Arrays;
  30 import com.sun.marlin.stats.Histogram;
  31 import com.sun.marlin.stats.StatLong;
  32 
  33 final class Helpers implements MarlinConst {
  34 
  35     private Helpers() {
  36         throw new Error("This is a non instantiable class");
  37     }
  38 
  39     static boolean within(final float x, final float y, final float err) {
  40         final float d = y - x;
  41         return (d <= err && d >= -err);
  42     }
  43 
  44     static boolean within(final double x, final double y, final double err) {
  45         final double d = y - x;
  46         return (d <= err && d >= -err);
  47     }
  48 
  49     static float evalCubic(final float a, final float b,
  50                            final float c, final float d,
  51                            final float t)
  52     {
  53         return t * (t * (t * a + b) + c) + d;
  54     }
  55 
  56     static float evalQuad(final float a, final float b,
  57                           final float c, final float t)
  58     {
  59         return t * (t * a + b) + c;
  60     }
  61 
  62     static int quadraticRoots(final float a, final float b, final float c,
  63                               final float[] zeroes, final int off)
  64     {
  65         int ret = off;
  66         if (a != 0.0f) {
  67             final float dis = b*b - 4.0f * a * c;
  68             if (dis > 0.0f) {
  69                 final float sqrtDis = (float) Math.sqrt(dis);
  70                 // depending on the sign of b we use a slightly different
  71                 // algorithm than the traditional one to find one of the roots
  72                 // so we can avoid adding numbers of different signs (which
  73                 // might result in loss of precision).
  74                 if (b >= 0.0f) {
  75                     zeroes[ret++] = (2.0f * c) / (-b - sqrtDis);
  76                     zeroes[ret++] = (-b - sqrtDis) / (2.0f * a);
  77                 } else {
  78                     zeroes[ret++] = (-b + sqrtDis) / (2.0f * a);
  79                     zeroes[ret++] = (2.0f * c) / (-b + sqrtDis);
  80                 }
  81             } else if (dis == 0.0f) {
  82                 zeroes[ret++] = -b / (2.0f * a);
  83             }
  84         } else if (b != 0.0f) {
  85             zeroes[ret++] = -c / b;
  86         }
  87         return ret - off;
  88     }
  89 
  90     // find the roots of g(t) = d*t^3 + a*t^2 + b*t + c in [A,B)
  91     static int cubicRootsInAB(final float d0, float a0, float b0, float c0,
  92                               final float[] pts, final int off,
  93                               final float A, final float B)
  94     {
  95         if (d0 == 0.0f) {
  96             final int num = quadraticRoots(a0, b0, c0, pts, off);
  97             return filterOutNotInAB(pts, off, num, A, B) - off;
  98         }
  99         // From Graphics Gems:
 100         // https://github.com/erich666/GraphicsGems/blob/master/gems/Roots3And4.c
 101         // (also from awt.geom.CubicCurve2D. But here we don't need as
 102         // much accuracy and we don't want to create arrays so we use
 103         // our own customized version).
 104 
 105         // normal form: x^3 + ax^2 + bx + c = 0
 106 
 107         // 2018.1: Need double precision if d is very small (flat curve) !
 108         /*
 109          * TODO: cleanup all that code after reading Roots3And4.c
 110          */
 111         final double a = ((double)a0) / d0;
 112         final double b = ((double)b0) / d0;
 113         final double c = ((double)c0) / d0;
 114 
 115         //  substitute x = y - A/3 to eliminate quadratic term:
 116         //     x^3 +Px + Q = 0
 117         //
 118         // Since we actually need P/3 and Q/2 for all of the
 119         // calculations that follow, we will calculate
 120         // p = P/3
 121         // q = Q/2
 122         // instead and use those values for simplicity of the code.
 123         final double sub = (1.0d / 3.0d) * a;
 124         final double sq_A = a * a;
 125         final double p = (1.0d / 3.0d) * ((-1.0d / 3.0d) * sq_A + b);
 126         final double q = (1.0d / 2.0d) * ((2.0d / 27.0d) * a * sq_A - sub * b + c);
 127 
 128         // use Cardano's formula
 129 
 130         final double cb_p = p * p * p;
 131         final double D = q * q + cb_p;
 132 
 133         int num;
 134         if (D < 0.0d) {
 135             // see: http://en.wikipedia.org/wiki/Cubic_function#Trigonometric_.28and_hyperbolic.29_method
 136             final double phi = (1.0d / 3.0d) * Math.acos(-q / Math.sqrt(-cb_p));
 137             final double t = 2.0d * Math.sqrt(-p);
 138 
 139             pts[off    ] = (float) ( t * Math.cos(phi) - sub);
 140             pts[off + 1] = (float) (-t * Math.cos(phi + (Math.PI / 3.0d)) - sub);
 141             pts[off + 2] = (float) (-t * Math.cos(phi - (Math.PI / 3.0d)) - sub);
 142             num = 3;
 143         } else {
 144             final double sqrt_D = Math.sqrt(D);
 145             final double u =   Math.cbrt(sqrt_D - q);
 146             final double v = - Math.cbrt(sqrt_D + q);
 147 
 148             pts[off    ] = (float) (u + v - sub);
 149             num = 1;
 150 
 151             if (within(D, 0.0d, 1e-8d)) {
 152                 pts[off + 1] = (float)((-1.0d / 2.0d) * (u + v) - sub);
 153                 num = 2;
 154             }
 155         }
 156 
 157         return filterOutNotInAB(pts, off, num, A, B) - off;
 158     }
 159 
 160     // returns the index 1 past the last valid element remaining after filtering
 161     static int filterOutNotInAB(final float[] nums, final int off, final int len,
 162                                 final float a, final float b)
 163     {
 164         int ret = off;
 165         for (int i = off, end = off + len; i < end; i++) {
 166             if (nums[i] >= a && nums[i] < b) {
 167                 nums[ret++] = nums[i];
 168             }
 169         }
 170         return ret;
 171     }
 172 
 173     static float fastLineLen(final float x0, final float y0,
 174                              final float x1, final float y1)
 175     {
 176         final float dx = x1 - x0;
 177         final float dy = y1 - y0;
 178 
 179         // use manhattan norm:
 180         return Math.abs(dx) + Math.abs(dy);
 181     }
 182 
 183     static float linelen(final float x0, final float y0,
 184                          final float x1, final float y1)
 185     {
 186         final float dx = x1 - x0;
 187         final float dy = y1 - y0;
 188         return (float) Math.sqrt(dx * dx + dy * dy);
 189     }
 190 
 191     static float fastQuadLen(final float x0, final float y0,
 192                              final float x1, final float y1,
 193                              final float x2, final float y2)
 194     {
 195         final float dx1 = x1 - x0;
 196         final float dx2 = x2 - x1;
 197         final float dy1 = y1 - y0;
 198         final float dy2 = y2 - y1;
 199 
 200         // use manhattan norm:
 201         return Math.abs(dx1) + Math.abs(dx2)
 202              + Math.abs(dy1) + Math.abs(dy2);
 203     }
 204 
 205     static float quadlen(final float x0, final float y0,
 206                          final float x1, final float y1,
 207                          final float x2, final float y2)
 208     {
 209         return (linelen(x0, y0, x1, y1)
 210                 + linelen(x1, y1, x2, y2)
 211                 + linelen(x0, y0, x2, y2)) / 2.0f;
 212     }
 213 
 214 
 215     static float fastCurvelen(final float x0, final float y0,
 216                               final float x1, final float y1,
 217                               final float x2, final float y2,
 218                               final float x3, final float y3)
 219     {
 220         final float dx1 = x1 - x0;
 221         final float dx2 = x2 - x1;
 222         final float dx3 = x3 - x2;
 223         final float dy1 = y1 - y0;
 224         final float dy2 = y2 - y1;
 225         final float dy3 = y3 - y2;
 226 
 227         // use manhattan norm:
 228         return Math.abs(dx1) + Math.abs(dx2) + Math.abs(dx3)
 229              + Math.abs(dy1) + Math.abs(dy2) + Math.abs(dy3);
 230     }
 231 
 232     static float curvelen(final float x0, final float y0,
 233                           final float x1, final float y1,
 234                           final float x2, final float y2,
 235                           final float x3, final float y3)
 236     {
 237         return (linelen(x0, y0, x1, y1)
 238               + linelen(x1, y1, x2, y2)
 239               + linelen(x2, y2, x3, y3)
 240               + linelen(x0, y0, x3, y3)) / 2.0f;
 241     }
 242 
 243     // finds values of t where the curve in pts should be subdivided in order
 244     // to get good offset curves a distance of w away from the middle curve.
 245     // Stores the points in ts, and returns how many of them there were.
 246     static int findSubdivPoints(final Curve c, final float[] pts,
 247                                 final float[] ts, final int type,
 248                                 final float w2)
 249     {
 250         final float x12 = pts[2] - pts[0];
 251         final float y12 = pts[3] - pts[1];
 252         // if the curve is already parallel to either axis we gain nothing
 253         // from rotating it.
 254         if ((y12 != 0.0f && x12 != 0.0f)) {
 255             // we rotate it so that the first vector in the control polygon is
 256             // parallel to the x-axis. This will ensure that rotated quarter
 257             // circles won't be subdivided.
 258             final float hypot = (float)Math.sqrt(x12 * x12 + y12 * y12);
 259             final float cos = x12 / hypot;
 260             final float sin = y12 / hypot;
 261             final float x1 = cos * pts[0] + sin * pts[1];
 262             final float y1 = cos * pts[1] - sin * pts[0];
 263             final float x2 = cos * pts[2] + sin * pts[3];
 264             final float y2 = cos * pts[3] - sin * pts[2];
 265             final float x3 = cos * pts[4] + sin * pts[5];
 266             final float y3 = cos * pts[5] - sin * pts[4];
 267 
 268             switch(type) {
 269             case 8:
 270                 final float x4 = cos * pts[6] + sin * pts[7];
 271                 final float y4 = cos * pts[7] - sin * pts[6];
 272                 c.set(x1, y1, x2, y2, x3, y3, x4, y4);
 273                 break;
 274             case 6:
 275                 c.set(x1, y1, x2, y2, x3, y3);
 276                 break;
 277             default:
 278             }
 279         } else {
 280             c.set(pts, type);
 281         }
 282 
 283         int ret = 0;
 284         // we subdivide at values of t such that the remaining rotated
 285         // curves are monotonic in x and y.
 286         ret += c.dxRoots(ts, ret);
 287         ret += c.dyRoots(ts, ret);
 288 
 289         // subdivide at inflection points.
 290         if (type == 8) {
 291             // quadratic curves can't have inflection points
 292             ret += c.infPoints(ts, ret);
 293         }
 294 
 295         // now we must subdivide at points where one of the offset curves will have
 296         // a cusp. This happens at ts where the radius of curvature is equal to w.
 297         ret += c.rootsOfROCMinusW(ts, ret, w2, 0.0001f);
 298 
 299         ret = filterOutNotInAB(ts, 0, ret, 0.0001f, 0.9999f);
 300         isort(ts, ret);
 301         return ret;
 302     }
 303 
 304     // finds values of t where the curve in pts should be subdivided in order
 305     // to get intersections with the given clip rectangle.
 306     // Stores the points in ts, and returns how many of them there were.
 307     static int findClipPoints(final Curve curve, final float[] pts,
 308                               final float[] ts, final int type,
 309                               final int outCodeOR,
 310                               final float[] clipRect)
 311     {
 312         curve.set(pts, type);
 313 
 314         // clip rectangle (ymin, ymax, xmin, xmax)
 315         int ret = 0;
 316 
 317         if ((outCodeOR & OUTCODE_LEFT) != 0) {
 318             ret += curve.xPoints(ts, ret, clipRect[2]);
 319         }
 320         if ((outCodeOR & OUTCODE_RIGHT) != 0) {
 321             ret += curve.xPoints(ts, ret, clipRect[3]);
 322         }
 323         if ((outCodeOR & OUTCODE_TOP) != 0) {
 324             ret += curve.yPoints(ts, ret, clipRect[0]);
 325         }
 326         if ((outCodeOR & OUTCODE_BOTTOM) != 0) {
 327             ret += curve.yPoints(ts, ret, clipRect[1]);
 328         }
 329         isort(ts, ret);
 330         return ret;
 331     }
 332 
 333     static void subdivide(final float[] src,
 334                           final float[] left, final float[] right,
 335                           final int type)
 336     {
 337         switch(type) {
 338         case 8:
 339             subdivideCubic(src, left, right);
 340             return;
 341         case 6:
 342             subdivideQuad(src, left, right);
 343             return;
 344         default:
 345             throw new InternalError("Unsupported curve type");
 346         }
 347     }
 348 
 349     static void isort(final float[] a, final int len) {
 350         for (int i = 1, j; i < len; i++) {
 351             final float ai = a[i];
 352             j = i - 1;
 353             for (; j >= 0 && a[j] > ai; j--) {
 354                 a[j + 1] = a[j];
 355             }
 356             a[j + 1] = ai;
 357         }
 358     }
 359 
 360     // Most of these are copied from classes in java.awt.geom because we need
 361     // both single and double precision variants of these functions, and Line2D,
 362     // CubicCurve2D, QuadCurve2D don't provide them.
 363     /**
 364      * Subdivides the cubic curve specified by the coordinates
 365      * stored in the <code>src</code> array at indices <code>srcoff</code>
 366      * through (<code>srcoff</code>&nbsp;+&nbsp;7) and stores the
 367      * resulting two subdivided curves into the two result arrays at the
 368      * corresponding indices.
 369      * Either or both of the <code>left</code> and <code>right</code>
 370      * arrays may be <code>null</code> or a reference to the same array
 371      * as the <code>src</code> array.
 372      * Note that the last point in the first subdivided curve is the
 373      * same as the first point in the second subdivided curve. Thus,
 374      * it is possible to pass the same array for <code>left</code>
 375      * and <code>right</code> and to use offsets, such as <code>rightoff</code>
 376      * equals (<code>leftoff</code> + 6), in order
 377      * to avoid allocating extra storage for this common point.
 378      * @param src the array holding the coordinates for the source curve
 379      * @param left the array for storing the coordinates for the first
 380      * half of the subdivided curve
 381      * @param right the array for storing the coordinates for the second
 382      * half of the subdivided curve
 383      * @since 1.7
 384      */
 385     static void subdivideCubic(final float[] src,
 386                                final float[] left,
 387                                final float[] right)
 388     {
 389         float  x1 = src[0];
 390         float  y1 = src[1];
 391         float cx1 = src[2];
 392         float cy1 = src[3];
 393         float cx2 = src[4];
 394         float cy2 = src[5];
 395         float  x2 = src[6];
 396         float  y2 = src[7];
 397 
 398         left[0]  = x1;
 399         left[1]  = y1;
 400 
 401         right[6] = x2;
 402         right[7] = y2;
 403 
 404         x1 = (x1 + cx1) / 2.0f;
 405         y1 = (y1 + cy1) / 2.0f;
 406         x2 = (x2 + cx2) / 2.0f;
 407         y2 = (y2 + cy2) / 2.0f;
 408 
 409         float cx = (cx1 + cx2) / 2.0f;
 410         float cy = (cy1 + cy2) / 2.0f;
 411 
 412         cx1 = (x1 + cx) / 2.0f;
 413         cy1 = (y1 + cy) / 2.0f;
 414         cx2 = (x2 + cx) / 2.0f;
 415         cy2 = (y2 + cy) / 2.0f;
 416         cx  = (cx1 + cx2) / 2.0f;
 417         cy  = (cy1 + cy2) / 2.0f;
 418 
 419         left[2] = x1;
 420         left[3] = y1;
 421         left[4] = cx1;
 422         left[5] = cy1;
 423         left[6] = cx;
 424         left[7] = cy;
 425 
 426         right[0] = cx;
 427         right[1] = cy;
 428         right[2] = cx2;
 429         right[3] = cy2;
 430         right[4] = x2;
 431         right[5] = y2;
 432     }
 433 
 434     static void subdivideCubicAt(final float t,
 435                                  final float[] src, final int offS,
 436                                  final float[] pts, final int offL, final int offR)
 437     {
 438         float  x1 = src[offS    ];
 439         float  y1 = src[offS + 1];
 440         float cx1 = src[offS + 2];
 441         float cy1 = src[offS + 3];
 442         float cx2 = src[offS + 4];
 443         float cy2 = src[offS + 5];
 444         float  x2 = src[offS + 6];
 445         float  y2 = src[offS + 7];
 446 
 447         pts[offL    ] = x1;
 448         pts[offL + 1] = y1;
 449 
 450         pts[offR + 6] = x2;
 451         pts[offR + 7] = y2;
 452 
 453         x1 =  x1 + t * (cx1 - x1);
 454         y1 =  y1 + t * (cy1 - y1);
 455         x2 = cx2 + t * (x2 - cx2);
 456         y2 = cy2 + t * (y2 - cy2);
 457 
 458         float cx = cx1 + t * (cx2 - cx1);
 459         float cy = cy1 + t * (cy2 - cy1);
 460 
 461         cx1 =  x1 + t * (cx - x1);
 462         cy1 =  y1 + t * (cy - y1);
 463         cx2 =  cx + t * (x2 - cx);
 464         cy2 =  cy + t * (y2 - cy);
 465         cx  = cx1 + t * (cx2 - cx1);
 466         cy  = cy1 + t * (cy2 - cy1);
 467 
 468         pts[offL + 2] = x1;
 469         pts[offL + 3] = y1;
 470         pts[offL + 4] = cx1;
 471         pts[offL + 5] = cy1;
 472         pts[offL + 6] = cx;
 473         pts[offL + 7] = cy;
 474 
 475         pts[offR    ] = cx;
 476         pts[offR + 1] = cy;
 477         pts[offR + 2] = cx2;
 478         pts[offR + 3] = cy2;
 479         pts[offR + 4] = x2;
 480         pts[offR + 5] = y2;
 481     }
 482 
 483     static void subdivideQuad(final float[] src,
 484                               final float[] left,
 485                               final float[] right)
 486     {
 487         float x1 = src[0];
 488         float y1 = src[1];
 489         float cx = src[2];
 490         float cy = src[3];
 491         float x2 = src[4];
 492         float y2 = src[5];
 493 
 494         left[0]  = x1;
 495         left[1]  = y1;
 496 
 497         right[4] = x2;
 498         right[5] = y2;
 499 
 500         x1 = (x1 + cx) / 2.0f;
 501         y1 = (y1 + cy) / 2.0f;
 502         x2 = (x2 + cx) / 2.0f;
 503         y2 = (y2 + cy) / 2.0f;
 504         cx = (x1 + x2) / 2.0f;
 505         cy = (y1 + y2) / 2.0f;
 506 
 507         left[2] = x1;
 508         left[3] = y1;
 509         left[4] = cx;
 510         left[5] = cy;
 511 
 512         right[0] = cx;
 513         right[1] = cy;
 514         right[2] = x2;
 515         right[3] = y2;
 516     }
 517 
 518     static void subdivideQuadAt(final float t,
 519                                 final float[] src, final int offS,
 520                                 final float[] pts, final int offL, final int offR)
 521     {
 522         float x1 = src[offS    ];
 523         float y1 = src[offS + 1];
 524         float cx = src[offS + 2];
 525         float cy = src[offS + 3];
 526         float x2 = src[offS + 4];
 527         float y2 = src[offS + 5];
 528 
 529         pts[offL    ] = x1;
 530         pts[offL + 1] = y1;
 531 
 532         pts[offR + 4] = x2;
 533         pts[offR + 5] = y2;
 534 
 535         x1 = x1 + t * (cx - x1);
 536         y1 = y1 + t * (cy - y1);
 537         x2 = cx + t * (x2 - cx);
 538         y2 = cy + t * (y2 - cy);
 539         cx = x1 + t * (x2 - x1);
 540         cy = y1 + t * (y2 - y1);
 541 
 542         pts[offL + 2] = x1;
 543         pts[offL + 3] = y1;
 544         pts[offL + 4] = cx;
 545         pts[offL + 5] = cy;
 546 
 547         pts[offR    ] = cx;
 548         pts[offR + 1] = cy;
 549         pts[offR + 2] = x2;
 550         pts[offR + 3] = y2;
 551     }
 552 
 553     static void subdivideLineAt(final float t,
 554                                 final float[] src, final int offS,
 555                                 final float[] pts, final int offL, final int offR)
 556     {
 557         float x1 = src[offS    ];
 558         float y1 = src[offS + 1];
 559         float x2 = src[offS + 2];
 560         float y2 = src[offS + 3];
 561 
 562         pts[offL    ] = x1;
 563         pts[offL + 1] = y1;
 564 
 565         pts[offR + 2] = x2;
 566         pts[offR + 3] = y2;
 567 
 568         x1 = x1 + t * (x2 - x1);
 569         y1 = y1 + t * (y2 - y1);
 570 
 571         pts[offL + 2] = x1;
 572         pts[offL + 3] = y1;
 573 
 574         pts[offR    ] = x1;
 575         pts[offR + 1] = y1;
 576     }
 577 
 578     static void subdivideAt(final float t,
 579                             final float[] src, final int offS,
 580                             final float[] pts, final int offL, final int type)
 581     {
 582         // if instead of switch (perf + most probable cases first)
 583         if (type == 8) {
 584             subdivideCubicAt(t, src, offS, pts, offL, offL + type);
 585         } else if (type == 4) {
 586             subdivideLineAt(t, src, offS, pts, offL, offL + type);
 587         } else {
 588             subdivideQuadAt(t, src, offS, pts, offL, offL + type);
 589         }
 590     }
 591 
 592     // From sun.java2d.loops.GeneralRenderer:
 593 
 594     static int outcode(final float x, final float y,
 595                        final float[] clipRect)
 596     {
 597         int code;
 598         if (y < clipRect[0]) {
 599             code = OUTCODE_TOP;
 600         } else if (y >= clipRect[1]) {
 601             code = OUTCODE_BOTTOM;
 602         } else {
 603             code = 0;
 604         }
 605         if (x < clipRect[2]) {
 606             code |= OUTCODE_LEFT;
 607         } else if (x >= clipRect[3]) {
 608             code |= OUTCODE_RIGHT;
 609         }
 610         return code;
 611     }
 612 
 613     // a stack of polynomial curves where each curve shares endpoints with
 614     // adjacent ones.
 615     static final class PolyStack {
 616         private static final byte TYPE_LINETO  = (byte) 0;
 617         private static final byte TYPE_QUADTO  = (byte) 1;
 618         private static final byte TYPE_CUBICTO = (byte) 2;
 619 
 620         // curves capacity = edges count (8192) = edges x 2 (coords)
 621         private static final int INITIAL_CURVES_COUNT = INITIAL_EDGES_COUNT << 1;
 622 
 623         // types capacity = edges count (4096)
 624         private static final int INITIAL_TYPES_COUNT = INITIAL_EDGES_COUNT;
 625 
 626         float[] curves;
 627         int end;
 628         byte[] curveTypes;
 629         int numCurves;
 630 
 631         // curves ref (dirty)
 632         final FloatArrayCache.Reference curves_ref;
 633         // curveTypes ref (dirty)
 634         final ByteArrayCache.Reference curveTypes_ref;
 635 
 636         // used marks (stats only)
 637         int curveTypesUseMark;
 638         int curvesUseMark;
 639 
 640         private final StatLong stat_polystack_types;
 641         private final StatLong stat_polystack_curves;
 642         private final Histogram hist_polystack_curves;
 643         private final StatLong stat_array_polystack_curves;
 644         private final StatLong stat_array_polystack_curveTypes;
 645 
 646         PolyStack(final RendererContext rdrCtx) {
 647             this(rdrCtx, null, null, null, null, null);
 648         }
 649 
 650         PolyStack(final RendererContext rdrCtx,
 651                   final StatLong stat_polystack_types,
 652                   final StatLong stat_polystack_curves,
 653                   final Histogram hist_polystack_curves,
 654                   final StatLong stat_array_polystack_curves,
 655                   final StatLong stat_array_polystack_curveTypes)
 656         {
 657             curves_ref = rdrCtx.newDirtyFloatArrayRef(INITIAL_CURVES_COUNT); // 32K
 658             curves     = curves_ref.initial;
 659 
 660             curveTypes_ref = rdrCtx.newDirtyByteArrayRef(INITIAL_TYPES_COUNT); // 4K
 661             curveTypes     = curveTypes_ref.initial;
 662             numCurves = 0;
 663             end = 0;
 664 
 665             if (DO_STATS) {
 666                 curveTypesUseMark = 0;
 667                 curvesUseMark = 0;
 668             }
 669             this.stat_polystack_types = stat_polystack_types;
 670             this.stat_polystack_curves = stat_polystack_curves;
 671             this.hist_polystack_curves = hist_polystack_curves;
 672             this.stat_array_polystack_curves = stat_array_polystack_curves;
 673             this.stat_array_polystack_curveTypes = stat_array_polystack_curveTypes;
 674         }
 675 
 676         /**
 677          * Disposes this PolyStack:
 678          * clean up before reusing this instance
 679          */
 680         void dispose() {
 681             end = 0;
 682             numCurves = 0;
 683 
 684             if (DO_STATS) {
 685                 stat_polystack_types.add(curveTypesUseMark);
 686                 stat_polystack_curves.add(curvesUseMark);
 687                 hist_polystack_curves.add(curvesUseMark);
 688 
 689                 // reset marks
 690                 curveTypesUseMark = 0;
 691                 curvesUseMark = 0;
 692             }
 693 
 694             // Return arrays:
 695             // curves and curveTypes are kept dirty
 696             curves     = curves_ref.putArray(curves);
 697             curveTypes = curveTypes_ref.putArray(curveTypes);
 698         }
 699 
 700         private void ensureSpace(final int n) {
 701             // use substraction to avoid integer overflow:
 702             if (curves.length - end < n) {
 703                 if (DO_STATS) {
 704                     stat_array_polystack_curves.add(end + n);
 705                 }
 706                 curves = curves_ref.widenArray(curves, end, end + n);
 707             }
 708             if (curveTypes.length <= numCurves) {
 709                 if (DO_STATS) {
 710                     stat_array_polystack_curveTypes.add(numCurves + 1);
 711                 }
 712                 curveTypes = curveTypes_ref.widenArray(curveTypes,
 713                                                        numCurves,
 714                                                        numCurves + 1);
 715             }
 716         }
 717 
 718         void pushCubic(float x0, float y0,
 719                        float x1, float y1,
 720                        float x2, float y2)
 721         {
 722             ensureSpace(6);
 723             curveTypes[numCurves++] = TYPE_CUBICTO;
 724             // we reverse the coordinate order to make popping easier
 725             final float[] _curves = curves;
 726             int e = end;
 727             _curves[e++] = x2;    _curves[e++] = y2;
 728             _curves[e++] = x1;    _curves[e++] = y1;
 729             _curves[e++] = x0;    _curves[e++] = y0;
 730             end = e;
 731         }
 732 
 733         void pushQuad(float x0, float y0,
 734                       float x1, float y1)
 735         {
 736             ensureSpace(4);
 737             curveTypes[numCurves++] = TYPE_QUADTO;
 738             final float[] _curves = curves;
 739             int e = end;
 740             _curves[e++] = x1;    _curves[e++] = y1;
 741             _curves[e++] = x0;    _curves[e++] = y0;
 742             end = e;
 743         }
 744 
 745         void pushLine(float x, float y) {
 746             ensureSpace(2);
 747             curveTypes[numCurves++] = TYPE_LINETO;
 748             curves[end++] = x;    curves[end++] = y;
 749         }
 750 
 751         void pullAll(final PathConsumer2D io) {
 752             final int nc = numCurves;
 753             if (nc == 0) {
 754                 return;
 755             }
 756             if (DO_STATS) {
 757                 // update used marks:
 758                 if (numCurves > curveTypesUseMark) {
 759                     curveTypesUseMark = numCurves;
 760                 }
 761                 if (end > curvesUseMark) {
 762                     curvesUseMark = end;
 763                 }
 764             }
 765             final byte[]  _curveTypes = curveTypes;
 766             final float[] _curves = curves;
 767             int e = 0;
 768 
 769             for (int i = 0; i < nc; i++) {
 770                 switch(_curveTypes[i]) {
 771                 case TYPE_LINETO:
 772                     io.lineTo(_curves[e], _curves[e+1]);
 773                     e += 2;
 774                     continue;
 775                 case TYPE_CUBICTO:
 776                     io.curveTo(_curves[e],   _curves[e+1],
 777                                _curves[e+2], _curves[e+3],
 778                                _curves[e+4], _curves[e+5]);
 779                     e += 6;
 780                     continue;
 781                 case TYPE_QUADTO:
 782                     io.quadTo(_curves[e],   _curves[e+1],
 783                               _curves[e+2], _curves[e+3]);
 784                     e += 4;
 785                     continue;
 786                 default:
 787                 }
 788             }
 789             numCurves = 0;
 790             end = 0;
 791         }
 792 
 793         void popAll(final PathConsumer2D io) {
 794             int nc = numCurves;
 795             if (nc == 0) {
 796                 return;
 797             }
 798             if (DO_STATS) {
 799                 // update used marks:
 800                 if (numCurves > curveTypesUseMark) {
 801                     curveTypesUseMark = numCurves;
 802                 }
 803                 if (end > curvesUseMark) {
 804                     curvesUseMark = end;
 805                 }
 806             }
 807             final byte[]  _curveTypes = curveTypes;
 808             final float[] _curves = curves;
 809             int e  = end;
 810 
 811             while (nc != 0) {
 812                 switch(_curveTypes[--nc]) {
 813                 case TYPE_LINETO:
 814                     e -= 2;
 815                     io.lineTo(_curves[e], _curves[e+1]);
 816                     continue;
 817                 case TYPE_CUBICTO:
 818                     e -= 6;
 819                     io.curveTo(_curves[e],   _curves[e+1],
 820                                _curves[e+2], _curves[e+3],
 821                                _curves[e+4], _curves[e+5]);
 822                     continue;
 823                 case TYPE_QUADTO:
 824                     e -= 4;
 825                     io.quadTo(_curves[e],   _curves[e+1],
 826                               _curves[e+2], _curves[e+3]);
 827                     continue;
 828                 default:
 829                 }
 830             }
 831             numCurves = 0;
 832             end = 0;
 833         }
 834 
 835         @Override
 836         public String toString() {
 837             String ret = "";
 838             int nc = numCurves;
 839             int last = end;
 840             int len;
 841             while (nc != 0) {
 842                 switch(curveTypes[--nc]) {
 843                 case TYPE_LINETO:
 844                     len = 2;
 845                     ret += "line: ";
 846                     break;
 847                 case TYPE_QUADTO:
 848                     len = 4;
 849                     ret += "quad: ";
 850                     break;
 851                 case TYPE_CUBICTO:
 852                     len = 6;
 853                     ret += "cubic: ";
 854                     break;
 855                 default:
 856                     len = 0;
 857                 }
 858                 last -= len;
 859                 ret += Arrays.toString(Arrays.copyOfRange(curves, last, last+len))
 860                                        + "\n";
 861             }
 862             return ret;
 863         }
 864     }
 865 
 866     // a stack of integer indices
 867     static final class IndexStack {
 868 
 869         // integer capacity = edges count / 4 ~ 1024
 870         private static final int INITIAL_COUNT = INITIAL_EDGES_COUNT >> 2;
 871 
 872         private int end;
 873         private int[] indices;
 874 
 875         // indices ref (dirty)
 876         private final IntArrayCache.Reference indices_ref;
 877 
 878         // used marks (stats only)
 879         private int indicesUseMark;
 880 
 881         private final StatLong stat_idxstack_indices;
 882         private final Histogram hist_idxstack_indices;
 883         private final StatLong stat_array_idxstack_indices;
 884 
 885         IndexStack(final RendererContext rdrCtx) {
 886             this(rdrCtx, null, null, null);
 887         }
 888 
 889         IndexStack(final RendererContext rdrCtx,
 890                    final StatLong stat_idxstack_indices,
 891                    final Histogram hist_idxstack_indices,
 892                    final StatLong stat_array_idxstack_indices)
 893         {
 894             indices_ref = rdrCtx.newDirtyIntArrayRef(INITIAL_COUNT); // 4K
 895             indices     = indices_ref.initial;
 896             end = 0;
 897 
 898             if (DO_STATS) {
 899                 indicesUseMark = 0;
 900             }
 901             this.stat_idxstack_indices = stat_idxstack_indices;
 902             this.hist_idxstack_indices = hist_idxstack_indices;
 903             this.stat_array_idxstack_indices = stat_array_idxstack_indices;
 904         }
 905 
 906         /**
 907          * Disposes this PolyStack:
 908          * clean up before reusing this instance
 909          */
 910         void dispose() {
 911             end = 0;
 912 
 913             if (DO_STATS) {
 914                 stat_idxstack_indices.add(indicesUseMark);
 915                 hist_idxstack_indices.add(indicesUseMark);
 916 
 917                 // reset marks
 918                 indicesUseMark = 0;
 919             }
 920 
 921             // Return arrays:
 922             // values is kept dirty
 923             indices = indices_ref.putArray(indices);
 924         }
 925 
 926         boolean isEmpty() {
 927             return (end == 0);
 928         }
 929 
 930         void reset() {
 931             end = 0;
 932         }
 933 
 934         void push(final int v) {
 935             // remove redundant values (reverse order):
 936             int[] _values = indices;
 937             final int nc = end;
 938             if (nc != 0) {
 939                 if (_values[nc - 1] == v) {
 940                     // remove both duplicated values:
 941                     end--;
 942                     return;
 943                 }
 944             }
 945             if (_values.length <= nc) {
 946                 if (DO_STATS) {
 947                     stat_array_idxstack_indices.add(nc + 1);
 948                 }
 949                 indices = _values = indices_ref.widenArray(_values, nc, nc + 1);
 950             }
 951             _values[end++] = v;
 952 
 953             if (DO_STATS) {
 954                 // update used marks:
 955                 if (end > indicesUseMark) {
 956                     indicesUseMark = end;
 957                 }
 958             }
 959         }
 960 
 961         void pullAll(final float[] points, final PathConsumer2D io) {
 962             final int nc = end;
 963             if (nc == 0) {
 964                 return;
 965             }
 966             final int[] _values = indices;
 967 
 968             for (int i = 0, j; i < nc; i++) {
 969                 j = _values[i] << 1;
 970                 io.lineTo(points[j], points[j + 1]);
 971             }
 972             end = 0;
 973         }
 974     }
 975 }