/*
 * Copyright 2020 Google LLC.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#include "src/gpu/tessellate/GrStrokeHardwareTessellator.h"

#include "src/core/SkPathPriv.h"
#include "src/gpu/GrRecordingContextPriv.h"
#include "src/gpu/GrVx.h"
#include "src/gpu/geometry/GrPathUtils.h"
#include "src/gpu/tessellate/GrWangsFormula.h"

using Tolerances = GrStrokeTessellateShader::Tolerances;

namespace {

static float num_combined_segments(float numParametricSegments, float numRadialSegments) {
    // The first and last edges are shared by both the parametric and radial sets of edges, so
    // the total number of edges is:
    //
    //   numCombinedEdges = numParametricEdges + numRadialEdges - 2
    //
    // It's also important to differentiate between the number of edges and segments in a strip:
    //
    //   numCombinedSegments = numCombinedEdges - 1
    //
    // So the total number of segments in the combined strip is:
    //
    //   numCombinedSegments = numParametricEdges + numRadialEdges - 2 - 1
    //                       = numParametricSegments + 1 + numRadialSegments + 1 - 2 - 1
    //                       = numParametricSegments + numRadialSegments - 1
    //
    return numParametricSegments + numRadialSegments - 1;
}

static grvx::float2 pow4(grvx::float2 x) {
    auto xx = x*x;
    return xx*xx;
}

class PatchWriter {
public:
    using ShaderFlags = GrStrokeTessellator::ShaderFlags;
    using PatchChunk = GrStrokeHardwareTessellator::PatchChunk;

    enum class JoinType {
        kMiter = SkPaint::kMiter_Join,
        kRound = SkPaint::kRound_Join,
        kBevel = SkPaint::kBevel_Join,
        kBowtie = SkPaint::kLast_Join + 1  // Double sided round join.
    };

    PatchWriter(ShaderFlags shaderFlags, GrMeshDrawOp::Target* target, float matrixMaxScale,
                SkTArray<PatchChunk>* patchChunks, int totalCombinedVerbCnt)
            : fShaderFlags(shaderFlags)
            , fTarget(target)
            , fPatchChunks(patchChunks)
            , fPatchStride(GrStrokeTessellateShader::PatchStride(fShaderFlags))
            // Subtract 2 because the tessellation shader chops every cubic at two locations, and
            // each chop has the potential to introduce an extra segment.
            , fMaxTessellationSegments(target->caps().shaderCaps()->maxTessellationSegments() - 2)
            , fParametricIntolerance(Tolerances::CalcParametricIntolerance(matrixMaxScale)) {
        // Pre-allocate at least enough vertex space for 1 in 4 strokes to chop, and for 8 caps.
        int strokePreallocCount = totalCombinedVerbCnt * 5/4;
        int capPreallocCount = 8;
        fNextChunkMinPatchAllocCount = strokePreallocCount + capPreallocCount;
    }

    ~PatchWriter() {
        if (!fPatchChunks->empty()) {
            fTarget->putBackVertices(fCurrChunkPatchCapacity - fCurrChunkPatchCount, fPatchStride);
            fPatchChunks->back().fPatchCount = fCurrChunkPatchCount;
        }
    }

    // This is the intolerance value, adjusted for the view matrix, to use with Wang's formulas when
    // determining how many parametric segments a curve will require.
    float parametricIntolerance() const {
        return fParametricIntolerance;
    }
    // Will a line and worst-case previous join both fit in a single patch together?
    bool lineFitsInPatch_withJoin() {
        return fMaxCombinedSegments_withJoin >= 1;
    }
    // Will a stroke with the given number of parametric segments and a worst-case rotation of 180
    // degrees fit in a single patch?
    bool stroke180FitsInPatch(float numParametricSegments_pow4) {
        return numParametricSegments_pow4 <= fMaxParametricSegments_pow4[0];
    }
    // Will a worst-case 180-degree stroke with the given number of parametric segments, and a
    // worst-case join fit in a single patch together?
    bool stroke180FitsInPatch_withJoin(float numParametricSegments_pow4) {
        return numParametricSegments_pow4 <= fMaxParametricSegments_pow4_withJoin[0];
    }
    // Will a stroke with the given number of parametric segments and a worst-case rotation of 360
    // degrees fit in a single patch?
    bool stroke360FitsInPatch(float numParametricSegments_pow4) {
        return numParametricSegments_pow4 <= fMaxParametricSegments_pow4[1];
    }
    // Will a worst-case 360-degree stroke with the given number of parametric segments, and a
    // worst-case join fit in a single patch together?
    bool stroke360FitsInPatch_withJoin(float numParametricSegments_pow4) {
        return numParametricSegments_pow4 <= fMaxParametricSegments_pow4_withJoin[1];
    }

    void updateTolerances(float numRadialSegmentsPerRadian, SkPaint::Join joinType) {
        using grvx::float2;

        fNumRadialSegmentsPerRadian = numRadialSegmentsPerRadian;

        // Calculate the worst-case numbers of parametric segments our hardware can support for the
        // current stroke radius, in the event that there are also enough radial segments to rotate
        // 180 and 360 degrees respectively. These are used for "quick accepts" that allow us to
        // send almost all curves directly to the hardware without having to chop.
        float2 numRadialSegments_180_360 = skvx::max(skvx::ceil(
                float2{SK_ScalarPI, 2*SK_ScalarPI} * fNumRadialSegmentsPerRadian), 1);
        // numEdges = numSegments + 1. See num_combined_segments().
        float maxTotalEdges = fMaxTessellationSegments + 1;
        // numParametricSegments = numTotalEdges - numRadialSegments. See num_combined_segments().
        float2 maxParametricSegments = skvx::max(maxTotalEdges - numRadialSegments_180_360, 0);
        float2 maxParametricSegments_pow4 = pow4(maxParametricSegments);
        maxParametricSegments_pow4.store(fMaxParametricSegments_pow4);

        // Find the worst-case numbers of parametric segments if we are to integrate a join into the
        // same patch as the curve.
        float numRadialSegments180 = numRadialSegments_180_360[0];
        float worstCaseNumSegmentsInJoin;
        switch (joinType) {
            case SkPaint::kBevel_Join: worstCaseNumSegmentsInJoin = 1; break;
            case SkPaint::kMiter_Join: worstCaseNumSegmentsInJoin = 2; break;
            case SkPaint::kRound_Join: worstCaseNumSegmentsInJoin = numRadialSegments180; break;
        }

        // Now calculate the worst-case numbers of parametric segments if we also want to combine a
        // join with the patch. Subtract an extra 1 off the end because when we integrate a join,
        // the tessellator has to add a redundant edge between the join and curve.
        float2 maxParametricSegments_pow4_withJoin = pow4(skvx::max(
                maxParametricSegments - worstCaseNumSegmentsInJoin - 1, 0));
        maxParametricSegments_pow4_withJoin.store(fMaxParametricSegments_pow4_withJoin);

        fMaxCombinedSegments_withJoin = fMaxTessellationSegments - worstCaseNumSegmentsInJoin - 1;
        fSoloRoundJoinAlwaysFitsInPatch = (numRadialSegments180 <= fMaxTessellationSegments);
        fStrokeJoinType = JoinType(joinType);
    }

    void updateDynamicStroke(const SkStrokeRec& stroke) {
        SkASSERT(fShaderFlags & ShaderFlags::kDynamicStroke);
        fDynamicStroke.set(stroke);
    }

    void updateDynamicColor(const SkPMColor4f& color) {
        SkASSERT(fShaderFlags & ShaderFlags::kDynamicColor);
        bool wideColor = fShaderFlags & ShaderFlags::kWideColor;
        SkASSERT(wideColor || color.fitsInBytes());
        fDynamicColor.set(color, wideColor);
    }

    void moveTo(SkPoint pt) {
        fCurrContourStartPoint = pt;
        fHasLastControlPoint = false;
    }

    // Writes out the given line, possibly chopping its previous join until the segments fit in
    // tessellation patches.
    void writeLineTo(SkPoint p0, SkPoint p1) {
        this->writeLineTo(fStrokeJoinType, p0, p1);
    }
    void writeLineTo(JoinType prevJoinType, SkPoint p0, SkPoint p1) {
        // Zero-length paths need special treatment because they are spec'd to behave differently.
        if (p0 == p1) {
            return;
        }
        SkPoint asPatch[4] = {p0, p0, p1, p1};
        this->internalPatchTo(prevJoinType, this->lineFitsInPatch_withJoin(), asPatch, p1);
    }

    // Recursively chops the given conic and its previous join until the segments fit in
    // tessellation patches.
    void writeConicPatchesTo(const SkPoint p[3], float w) {
        this->internalConicPatchesTo(fStrokeJoinType, p, w);
    }

    // Chops the given cubic at points of inflection and 180-degree rotation, and then recursively
    // chops the previous join and cubic sections as necessary until the segments fit in
    // tessellation patches.
    void writeCubicConvex180PatchesTo(const SkPoint p[4]) {
        SkPoint chops[10];
        float chopT[2];
        bool areCusps;
        int numChops = GrPathUtils::findCubicConvex180Chops(p, chopT, &areCusps);
        if (numChops == 0) {
            // The curve is already convex and rotates no more than 180 degrees.
            this->internalCubicConvex180PatchesTo(fStrokeJoinType, p);
        } else if (numChops == 1) {
            SkChopCubicAt(p, chops, chopT[0]);
            if (areCusps) {
                // When chopping on a perfect cusp, these 3 points will be equal.
                chops[2] = chops[4] = chops[3];
            }
            this->internalCubicConvex180PatchesTo(fStrokeJoinType, chops);
            this->internalCubicConvex180PatchesTo(JoinType::kBowtie, chops + 3);
        } else {
            SkASSERT(numChops == 2);
            SkChopCubicAt(p, chops, chopT[0], chopT[1]);
            // Two cusps are only possible on a flat line with two 180-degree turnarounds.
            if (areCusps) {
                this->writeLineTo(chops[0], chops[3]);
                this->writeLineTo(JoinType::kBowtie, chops[3], chops[6]);
                this->writeLineTo(JoinType::kBowtie, chops[6], chops[9]);
                return;
            }
            this->internalCubicConvex180PatchesTo(fStrokeJoinType, chops);
            this->internalCubicConvex180PatchesTo(JoinType::kBowtie, chops + 3);
            this->internalCubicConvex180PatchesTo(JoinType::kBowtie, chops + 6);
        }
    }

    // Writes out the given stroke patch exactly as provided, without chopping or checking the
    // number of segments. Possibly chops its previous join until the segments fit in tessellation
    // patches.
    SK_ALWAYS_INLINE void writePatchTo(bool prevJoinFitsInPatch, const SkPoint p[4],
                                       SkPoint endControlPoint) {
        SkASSERT(fStrokeJoinType != JoinType::kBowtie);

        if (!fHasLastControlPoint) {
            // The first stroke doesn't have a previous join (yet). If the current contour ends up
            // closing itself, we will add that join as its own patch. TODO: Consider deferring the
            // first stroke until we know whether the contour will close. This will allow us to use
            // the closing join as the first patch's previous join.
            fHasLastControlPoint = true;
            fCurrContourFirstControlPoint = (p[1] != p[0]) ? p[1] : p[2];
            fLastControlPoint = p[0];  // Disables the join section of this patch.
        } else if (!prevJoinFitsInPatch) {
            // There aren't enough guaranteed segments to fold the previous join into this patch.
            // Emit the join in its own separate patch.
            this->internalJoinTo(fStrokeJoinType, p[0], (p[1] != p[0]) ? p[1] : p[2]);
            fLastControlPoint = p[0];  // Disables the join section of this patch.
        }

        if (this->allocPatch()) {
            fPatchWriter.write(fLastControlPoint);
            fPatchWriter.writeArray(p, 4);
            this->writeDynamicAttribs();
        }

        fLastControlPoint = endControlPoint;
    }

    void writeClose(SkPoint contourEndpoint, const SkMatrix& viewMatrix,
                    const SkStrokeRec& stroke) {
        if (!fHasLastControlPoint) {
            // Draw caps instead of closing if the subpath is zero length:
            //
            //   "Any zero length subpath ...  shall be stroked if the 'stroke-linecap' property has
            //   a value of round or square producing respectively a circle or a square."
            //
            //   (https://www.w3.org/TR/SVG11/painting.html#StrokeProperties)
            //
            this->writeCaps(contourEndpoint, viewMatrix, stroke);
            return;
        }

        // Draw a line back to the beginning. (This will be discarded if
        // contourEndpoint == fCurrContourStartPoint.)
        this->writeLineTo(contourEndpoint, fCurrContourStartPoint);
        this->internalJoinTo(fStrokeJoinType, fCurrContourStartPoint, fCurrContourFirstControlPoint);

        fHasLastControlPoint = false;
    }

    void writeCaps(SkPoint contourEndpoint, const SkMatrix& viewMatrix, const SkStrokeRec& stroke) {
        if (!fHasLastControlPoint) {
            // We don't have any control points to orient the caps. In this case, square and round
            // caps are specified to be drawn as an axis-aligned square or circle respectively.
            // Assign default control points that achieve this.
            SkVector outset;
            if (!stroke.isHairlineStyle()) {
                outset = {1, 0};
            } else {
                // If the stroke is hairline, orient the square on the post-transform x-axis
                // instead. We don't need to worry about the vector length since it will be
                // normalized later. Since the matrix cannot have perspective, the below is
                // equivalent to:
                //
                //    outset = inverse(|a b|) * |1| * arbitrary_scale
                //                     |c d|    |0|
                //
                //    == 1/det * | d -b| * |1| * arbitrary_scale
                //               |-c  a|   |0|
                //
                //    == 1/det * | d| * arbitrary_scale
                //               |-c|
                //
                //    == | d|
                //       |-c|
                //
                SkASSERT(!viewMatrix.hasPerspective());
                float c=viewMatrix.getSkewY(), d=viewMatrix.getScaleY();
                outset = {d, -c};
            }
            fCurrContourFirstControlPoint = fCurrContourStartPoint - outset;
            fLastControlPoint = fCurrContourStartPoint + outset;
            fHasLastControlPoint = true;
            contourEndpoint = fCurrContourStartPoint;
        }

        switch (stroke.getCap()) {
            case SkPaint::kButt_Cap:
                break;
            case SkPaint::kRound_Cap: {
                // A round cap is the same thing as a 180-degree round join.
                // If our join type isn't round we can alternatively use a bowtie.
                JoinType roundCapJoinType = (stroke.getJoin() == SkPaint::kRound_Join)
                        ? JoinType::kRound : JoinType::kBowtie;
                this->internalJoinTo(roundCapJoinType, contourEndpoint, fLastControlPoint);
                this->internalMoveTo(fCurrContourStartPoint, fCurrContourFirstControlPoint);
                this->internalJoinTo(roundCapJoinType, fCurrContourStartPoint,
                                     fCurrContourFirstControlPoint);
                break;
            }
            case SkPaint::kSquare_Cap: {
                // A square cap is the same as appending lineTos.
                auto strokeJoinType = JoinType(stroke.getJoin());
                SkVector lastTangent = contourEndpoint - fLastControlPoint;
                if (!stroke.isHairlineStyle()) {
                    // Extend the cap by 1/2 stroke width.
                    lastTangent *= (.5f * stroke.getWidth()) / lastTangent.length();
                } else {
                    // Extend the cap by what will be 1/2 pixel after transformation.
                    lastTangent *=
                            .5f / viewMatrix.mapVector(lastTangent.fX, lastTangent.fY).length();
                }
                this->writeLineTo(strokeJoinType, contourEndpoint, contourEndpoint + lastTangent);
                this->internalMoveTo(fCurrContourStartPoint, fCurrContourFirstControlPoint);
                SkVector firstTangent = fCurrContourFirstControlPoint - fCurrContourStartPoint;
                if (!stroke.isHairlineStyle()) {
                    // Set the the cap back by 1/2 stroke width.
                    firstTangent *= (-.5f * stroke.getWidth()) / firstTangent.length();
                } else {
                    // Set the cap back by what will be 1/2 pixel after transformation.
                    firstTangent *=
                            -.5f / viewMatrix.mapVector(firstTangent.fX, firstTangent.fY).length();
                }
                this->writeLineTo(strokeJoinType, fCurrContourStartPoint,
                                  fCurrContourStartPoint + firstTangent);
                break;
            }
        }

        fHasLastControlPoint = false;
    }

private:
    void internalMoveTo(SkPoint pt, SkPoint lastControlPoint) {
        fCurrContourStartPoint = pt;
        fCurrContourFirstControlPoint = fLastControlPoint = lastControlPoint;
        fHasLastControlPoint = true;
    }

    // Recursively chops the given conic and its previous join until the segments fit in
    // tessellation patches.
    void internalConicPatchesTo(JoinType prevJoinType, const SkPoint p[3], float w,
                                int maxDepth = -1) {
        // Zero-length paths need special treatment because they are spec'd to behave differently.
        // If the control point is colocated on an endpoint then this might end up being the case.
        // Fall back on a lineTo and let it make the final check.
        if (p[1] == p[0] || p[1] == p[2] || w == 0) {
            this->writeLineTo(prevJoinType, p[0], p[2]);
            return;
        }

        // Convert to a patch.
        SkPoint asPatch[4];
        if (w == 1) {
            GrPathUtils::convertQuadToCubic(p, asPatch);
        } else {
            GrPathShader::WriteConicPatch(p, w, asPatch);
        }

        float numParametricSegments_pow4 =
                GrWangsFormula::quadratic_pow4(fParametricIntolerance, p);
        if (this->stroke180FitsInPatch(numParametricSegments_pow4) || maxDepth == 0) {
            this->internalPatchTo(prevJoinType,
                                  this->stroke180FitsInPatch_withJoin(numParametricSegments_pow4),
                                  asPatch, p[2]);
            return;
        }

        // We still might have enough tessellation segments to render the curve. Check again with
        // the actual rotation.
        float numRadialSegments = SkMeasureQuadRotation(p) * fNumRadialSegmentsPerRadian;
        numRadialSegments = std::max(std::ceil(numRadialSegments), 1.f);
        float numParametricSegments = GrWangsFormula::root4(numParametricSegments_pow4);
        numParametricSegments = std::max(std::ceil(numParametricSegments), 1.f);
        float numCombinedSegments = num_combined_segments(numParametricSegments, numRadialSegments);
        if (numCombinedSegments > fMaxTessellationSegments) {
            // The hardware doesn't support enough segments for this curve. Chop and recurse.
            if (maxDepth < 0) {
                // Decide on an extremely conservative upper bound for when to quit chopping. This
                // is solely to protect us from infinite recursion in instances where FP error
                // prevents us from chopping at the correct midtangent.
                maxDepth = sk_float_nextlog2(numParametricSegments) +
                           sk_float_nextlog2(numRadialSegments) + 1;
                maxDepth = std::max(maxDepth, 1);
            }
            if (w == 1) {
                SkPoint chops[5];
                if (numParametricSegments >= numRadialSegments) {
                    SkChopQuadAtHalf(p, chops);
                } else {
                    SkChopQuadAtMidTangent(p, chops);
                }
                this->internalConicPatchesTo(prevJoinType, chops, 1, maxDepth - 1);
                this->internalConicPatchesTo(JoinType::kBowtie, chops + 2, 1, maxDepth - 1);
            } else {
                SkConic conic(p, w);
                float chopT = (numParametricSegments >= numRadialSegments) ? .5f
                                                                           : conic.findMidTangent();
                SkConic chops[2];
                if (conic.chopAt(chopT, chops)) {
                    this->internalConicPatchesTo(prevJoinType, chops[0].fPts, chops[0].fW,
                                                  maxDepth - 1);
                    this->internalConicPatchesTo(JoinType::kBowtie, chops[1].fPts, chops[1].fW,
                                                  maxDepth - 1);
                }
            }
            return;
        }

        this->internalPatchTo(prevJoinType, (numCombinedSegments <= fMaxCombinedSegments_withJoin),
                              asPatch, p[2]);
    }

    // Recursively chops the given cubic and its previous join until the segments fit in
    // tessellation patches. The cubic must be convex and must not rotate more than 180 degrees.
    void internalCubicConvex180PatchesTo(JoinType prevJoinType, const SkPoint p[4],
                                         int maxDepth = -1) {
        // The stroke tessellation shader assigns special meaning to p0==p1==p2 and p1==p2==p3. If
        // this is the case then we need to rewrite the cubic.
        if (p[1] == p[2] && (p[1] == p[0] || p[1] == p[3])) {
            this->writeLineTo(prevJoinType, p[0], p[3]);
            return;
        }

        float numParametricSegments_pow4 = GrWangsFormula::cubic_pow4(fParametricIntolerance, p);
        if (this->stroke180FitsInPatch(numParametricSegments_pow4) || maxDepth == 0) {
            this->internalPatchTo(prevJoinType,
                                  this->stroke180FitsInPatch_withJoin(numParametricSegments_pow4),
                                  p, p[3]);
            return;
        }

        // We still might have enough tessellation segments to render the curve. Check again with
        // its actual rotation.
        float numRadialSegments = SkMeasureNonInflectCubicRotation(p) * fNumRadialSegmentsPerRadian;
        numRadialSegments = std::max(std::ceil(numRadialSegments), 1.f);
        float numParametricSegments = GrWangsFormula::root4(numParametricSegments_pow4);
        numParametricSegments = std::max(std::ceil(numParametricSegments), 1.f);
        float numCombinedSegments = num_combined_segments(numParametricSegments, numRadialSegments);
        if (numCombinedSegments > fMaxTessellationSegments) {
            // The hardware doesn't support enough segments for this curve. Chop and recurse.
            SkPoint chops[7];
            if (maxDepth < 0) {
                // Decide on an extremely conservative upper bound for when to quit chopping. This
                // is solely to protect us from infinite recursion in instances where FP error
                // prevents us from chopping at the correct midtangent.
                maxDepth = sk_float_nextlog2(numParametricSegments) +
                           sk_float_nextlog2(numRadialSegments) + 1;
                maxDepth = std::max(maxDepth, 1);
            }
            if (numParametricSegments >= numRadialSegments) {
                SkChopCubicAtHalf(p, chops);
            } else {
                SkChopCubicAtMidTangent(p, chops);
            }
            this->internalCubicConvex180PatchesTo(prevJoinType, chops, maxDepth - 1);
            this->internalCubicConvex180PatchesTo(JoinType::kBowtie, chops + 3, maxDepth - 1);
            return;
        }

        this->internalPatchTo(prevJoinType, (numCombinedSegments <= fMaxCombinedSegments_withJoin),
                              p, p[3]);
    }

    // Writes out the given stroke patch exactly as provided, without chopping or checking the
    // number of segments. Possibly chops its previous join until the segments fit in tessellation
    // patches. It is valid for prevJoinType to be kBowtie.
    void internalPatchTo(JoinType prevJoinType, bool prevJoinFitsInPatch, const SkPoint p[4],
                         SkPoint endPt) {
        if (prevJoinType == JoinType::kBowtie) {
            SkASSERT(fHasLastControlPoint);
            // Bowtie joins are only used on internal chops, and internal chops almost always have
            // continuous tangent angles (i.e., the ending tangent of the first chop and the
            // beginning tangent of the second both point in the same direction). The tangents will
            // only ever not point in the same direction if we chopped at a cusp point, so that's
            // the only time we actually need a bowtie.
            SkPoint nextControlPoint = (p[1] == p[0]) ? p[2] : p[1];
            SkVector a = p[0] - fLastControlPoint;
            SkVector b = nextControlPoint - p[0];
            float ab_cosTheta = a.dot(b);
            float ab_pow2 = a.dot(a) * b.dot(b);
            // To check if tangents 'a' and 'b' do not point in the same direction, any of the
            // following formulas work:
            //
            //          0 != theta
            //          1 != cosTheta
            //          1 != cosTheta * abs(cosTheta)  [Still false when cosTheta == -1]
            //
            // Introducing a slop term for fuzzy equality gives:
            //
            //          1 !~= cosTheta * abs(cosTheta)                [tolerance = epsilon]
            //     (ab)^2 !~= (ab)^2 * cosTheta * abs(cosTheta)       [tolerance = (ab)^2 * epsilon]
            //     (ab)^2 !~= (ab * cosTheta) * (ab * abs(cosTheta))  [tolerance = (ab)^2 * epsilon]
            //     (ab)^2 !~= (ab * cosTheta) * abs(ab * cosTheta)    [tolerance = (ab)^2 * epsilon]
            //
            // Since we also scale the tolerance, the formula is unaffected by the magnitude of the
            // tangent vectors. (And we can fold "ab" in to the abs() because it's always positive.)
            if (!SkScalarNearlyEqual(ab_pow2, ab_cosTheta * fabsf(ab_cosTheta),
                                     ab_pow2 * SK_ScalarNearlyZero)) {
                this->internalJoinTo(JoinType::kBowtie, p[0], nextControlPoint);
                fLastControlPoint = p[0];  // Disables the join section of this patch.
                prevJoinFitsInPatch = true;
            }
        }

        this->writePatchTo(prevJoinFitsInPatch, p, (p[2] != endPt) ? p[2] : p[1]);
    }

    // Recursively chops the given join until the segments fit in tessellation patches.
    void internalJoinTo(JoinType joinType, SkPoint junctionPoint, SkPoint nextControlPoint,
                        int maxDepth = -1) {
        if (!fHasLastControlPoint) {
            // The first stroke doesn't have a previous join.
            return;
        }

        if (!fSoloRoundJoinAlwaysFitsInPatch && maxDepth != 0 &&
            (joinType == JoinType::kRound || joinType == JoinType::kBowtie)) {
            SkVector tan0 = junctionPoint - fLastControlPoint;
            SkVector tan1 = nextControlPoint - junctionPoint;
            float rotation = SkMeasureAngleBetweenVectors(tan0, tan1);
            float numRadialSegments = rotation * fNumRadialSegmentsPerRadian;
            if (numRadialSegments > fMaxTessellationSegments) {
                // This is a round join that requires more segments than the tessellator supports.
                // Split it and recurse.
                if (maxDepth < 0) {
                    // Decide on an upper bound for when to quit chopping. This is solely to protect
                    // us from infinite recursion due to FP precision issues.
                    maxDepth = sk_float_nextlog2(numRadialSegments / fMaxTessellationSegments);
                    maxDepth = std::max(maxDepth, 1);
                }
                // Find the bisector so we can split the join in half.
                SkPoint bisector = SkFindBisector(tan0, tan1);
                // c0 will be the "next" control point for the first join half, and c1 will be the
                // "previous" control point for the second join half.
                SkPoint c0, c1;
                // FIXME(skia:11347): This hack ensures "c0 - junctionPoint" gives the exact same
                // ieee fp32 vector as "-(c1 - junctionPoint)". Tessellated stroking is becoming
                // less experimental, so t's time to think of a cleaner method to avoid T-junctions
                // when we chop joins.
                int maxAttempts = 10;
                do {
                    bisector = (junctionPoint + bisector) - (junctionPoint - bisector);
                    c0 = junctionPoint + bisector;
                    c1 = junctionPoint - bisector;
                } while (c0 - junctionPoint != -(c1 - junctionPoint) && --maxAttempts);
                // First join half.
                this->internalJoinTo(joinType, junctionPoint, c0, maxDepth - 1);
                fLastControlPoint = c1;
                // Second join half.
                this->internalJoinTo(joinType, junctionPoint, nextControlPoint, maxDepth - 1);
                return;
            }
        }

        // We should never write out joins before the first curve.
        SkASSERT(fHasLastControlPoint);

        if (this->allocPatch()) {
            fPatchWriter.write(fLastControlPoint, junctionPoint);
            if (joinType == JoinType::kBowtie) {
                // {prevControlPoint, [p0, p0, p0, p3]} is a reserved patch pattern that means this
                // patch is a bowtie. The bowtie is anchored on p0 and its tangent angles go from
                // (p0 - prevControlPoint) to (p3 - p0).
                fPatchWriter.write(junctionPoint, junctionPoint);
            } else {
                // {prevControlPoint, [p0, p3, p3, p3]} is a reserved patch pattern that means this
                // patch is a join only (no curve sections in the patch). The join is anchored on p0
                // and its tangent angles go from (p0 - prevControlPoint) to (p3 - p0).
                fPatchWriter.write(nextControlPoint, nextControlPoint);
            }
            fPatchWriter.write(nextControlPoint);
            this->writeDynamicAttribs();
        }

        fLastControlPoint = nextControlPoint;
    }

    SK_ALWAYS_INLINE void writeDynamicAttribs() {
        if (fShaderFlags & ShaderFlags::kDynamicStroke) {
            fPatchWriter.write(fDynamicStroke);
        }
        if (fShaderFlags & ShaderFlags::kDynamicColor) {
            fPatchWriter.write(fDynamicColor);
        }
    }

    SK_ALWAYS_INLINE bool allocPatch() {
        if (fCurrChunkPatchCount == fCurrChunkPatchCapacity && !this->allocPatchChunk()) {
            return false;
        }
        SkASSERT(fCurrChunkPatchCount < fCurrChunkPatchCapacity);
        ++fCurrChunkPatchCount;
        return true;
    }

    bool allocPatchChunk() {
        if (!fPatchChunks->empty()) {
            fPatchChunks->back().fPatchCount = fCurrChunkPatchCount;
            // No need to put back vertices; the buffer is full.
        }
        fCurrChunkPatchCount = 0;
        PatchChunk* chunk = &fPatchChunks->push_back();
        fPatchWriter = {fTarget->makeVertexSpaceAtLeast(fPatchStride, fNextChunkMinPatchAllocCount,
                                                        fNextChunkMinPatchAllocCount,
                                                        &chunk->fPatchBuffer, &chunk->fBasePatch,
                                                        &fCurrChunkPatchCapacity)};
        if (!fPatchWriter.isValid()) {
            SkDebugf("WARNING: Failed to allocate vertex buffer for tessellated stroke.\n");
            fPatchChunks->pop_back();
            fCurrChunkPatchCapacity = 0;
            return false;
        }
        fNextChunkMinPatchAllocCount *= 2;
        return true;
    }

    const ShaderFlags fShaderFlags;
    GrMeshDrawOp::Target* const fTarget;
    SkTArray<PatchChunk>* const fPatchChunks;

    // Size in bytes of a tessellation patch with our shader flags.
    const size_t fPatchStride;

    // The maximum number of tessellation segments the hardware can emit for a single patch.
    const int fMaxTessellationSegments;

    // This is the intolerance value, adjusted for the view matrix, to use with Wang's formulas when
    // determining how many parametric segments a curve will require.
    const float fParametricIntolerance;

    // Number of radial segments required for each radian of rotation in order to look smooth with
    // the current stroke radius.
    float fNumRadialSegmentsPerRadian;

    // These arrays contain worst-case numbers of parametric segments, raised to the 4th power, that
    // our hardware can support for the current stroke radius. They assume curve rotations of 180
    // and 360 degrees respectively. These are used for "quick accepts" that allow us to send almost
    // all curves directly to the hardware without having to chop. We raise to the 4th power because
    // the "pow4" variants of Wang's formula are the quickest to evaluate.
    float fMaxParametricSegments_pow4[2];  // Values for strokes that rotate 180 and 360 degrees.
    float fMaxParametricSegments_pow4_withJoin[2];  // For strokes that rotate 180 and 360 degrees.

    // Maximum number of segments we can allocate for a stroke if we are stuffing it in a patch
    // together with a worst-case join.
    float fMaxCombinedSegments_withJoin;

    // Additional info on the current stroke radius/join type.
    bool fSoloRoundJoinAlwaysFitsInPatch;
    JoinType fStrokeJoinType;

    // Variables related to the patch chunk that we are currently writing out during prepareBuffers.
    int fCurrChunkPatchCount = 0;
    int fCurrChunkPatchCapacity = 0;
    int fNextChunkMinPatchAllocCount;
    GrVertexWriter fPatchWriter;

    // Variables related to the specific contour that we are currently iterating during
    // prepareBuffers().
    bool fHasLastControlPoint = false;
    SkPoint fCurrContourStartPoint;
    SkPoint fCurrContourFirstControlPoint;
    SkPoint fLastControlPoint;

    // Values for the current dynamic state (if any) that will get written out with each patch.
    GrStrokeTessellateShader::DynamicStroke fDynamicStroke;
    GrVertexColor fDynamicColor;
};

// Calculates and buffers up future values for "numRadialSegmentsPerRadian" using SIMD.
class alignas(sizeof(grvx::float4)) RadialSegmentsPerRadianBuffer {
public:
    using PathStrokeList = GrStrokeTessellator::PathStrokeList;

    RadialSegmentsPerRadianBuffer(float parametricIntolerance)
            : fParametricIntolerance(parametricIntolerance) {
    }

    float fetchNext(PathStrokeList* head) {
        // GrStrokeTessellateOp::onCombineIfPossible does not allow hairlines to become dynamic. If
        // this changes, we will need to call Tolerances::GetLocalStrokeWidth() for each stroke.
        SkASSERT(!head->fStroke.isHairlineStyle());
        if (fBufferIdx == 4) {
            // We ran out of values. Peek ahead and buffer up 4 more.
            PathStrokeList* peekAhead = head;
            int i = 0;
            do {
                fStrokeWidths[i++] = peekAhead->fStroke.getWidth();
            } while ((peekAhead = peekAhead->fNext) && i < 4);
            Tolerances::ApproxNumRadialSegmentsPerRadian(fParametricIntolerance,
                                                         fStrokeWidths).store(
                    fNumRadialSegmentsPerRadian);
            fBufferIdx = 0;
        }
        SkASSERT(0 <= fBufferIdx && fBufferIdx < 4);
        SkASSERT(fStrokeWidths[fBufferIdx] == head->fStroke.getWidth());
        return fNumRadialSegmentsPerRadian[fBufferIdx++];
    }

private:
    grvx::float4 fStrokeWidths{};  // Must be first for alignment purposes.
    float fNumRadialSegmentsPerRadian[4];
    const float fParametricIntolerance;
    int fBufferIdx = 4;  // Initialize the buffer as "empty";
};

SK_ALWAYS_INLINE static bool conic_has_cusp(const SkPoint p[3]) {
    SkVector a = p[1] - p[0];
    SkVector b = p[2] - p[1];
    // A conic of any class can only have a cusp if it is a degenerate flat line with a 180 degree
    // turnarund. To detect this, the beginning and ending tangents must be parallel
    // (a.cross(b) == 0) and pointing in opposite directions (a.dot(b) < 0).
    return a.cross(b) == 0 && a.dot(b) < 0;
}

SK_ALWAYS_INLINE static bool cubic_has_cusp(const SkPoint p[4]) {
    using grvx::float2;

    float2 p0 = skvx::bit_pun<float2>(p[0]);
    float2 p1 = skvx::bit_pun<float2>(p[1]);
    float2 p2 = skvx::bit_pun<float2>(p[2]);
    float2 p3 = skvx::bit_pun<float2>(p[3]);

    // See GrPathUtils::findCubicConvex180Chops() for the math.
    float2 C = p1 - p0;
    float2 D = p2 - p1;
    float2 E = p3 - p0;
    float2 B = D - C;
    float2 A = grvx::fast_madd<2>(-3, D, E);

    float a = grvx::cross(A, B);
    float b = grvx::cross(A, C);
    float c = grvx::cross(B, C);
    float discr = b*b - 4*a*c;

    // If -cuspThreshold <= discr <= cuspThreshold, it means the two roots are within a distance of
    // 2^-11 from one another in parametric space. This is close enough for our purposes to take the
    // slow codepath that knows how to handle cusps.
    constexpr static float kEpsilon = 1.f / (1 << 11);
    float cuspThreshold = (2*kEpsilon) * a;
    cuspThreshold *= cuspThreshold;

    return fabsf(discr) <= cuspThreshold &&
           // The most common type of cusp we encounter is when p0==p1 or p2==p3. Unless the curve
           // is a flat line (a==b==c==0), these don't actually need special treatment because the
           // cusp occurs at t=0 or t=1.
           (!(skvx::all(p0 == p1) || skvx::all(p2 == p3)) || (a == 0 && b == 0 && c == 0));
}

}  // namespace

void GrStrokeHardwareTessellator::prepare(GrMeshDrawOp::Target* target,
                                          const SkMatrix& viewMatrix) {
    using JoinType = PatchWriter::JoinType;

    std::array<float, 2> matrixMinMaxScales;
    if (!viewMatrix.getMinMaxScales(matrixMinMaxScales.data())) {
        matrixMinMaxScales.fill(1);
    }

    PatchWriter patchWriter(fShaderFlags, target, matrixMinMaxScales[1], &fPatchChunks,
                            fTotalCombinedVerbCnt);
    if (!(fShaderFlags & ShaderFlags::kDynamicStroke)) {
        // Strokes are static. Calculate tolerances once.
        const SkStrokeRec& stroke = fPathStrokeList->fStroke;
        float localStrokeWidth = Tolerances::GetLocalStrokeWidth(matrixMinMaxScales.data(),
                                                                 stroke.getWidth());
        float numRadialSegmentsPerRadian = Tolerances::CalcNumRadialSegmentsPerRadian(
                patchWriter.parametricIntolerance(), localStrokeWidth);
        patchWriter.updateTolerances(numRadialSegmentsPerRadian, stroke.getJoin());
    }

    // Fast SIMD queue that buffers up values for "numRadialSegmentsPerRadian". Only used when we
    // have dynamic strokes.
    RadialSegmentsPerRadianBuffer radialSegmentsPerRadianBuffer(
            patchWriter.parametricIntolerance());

    for (PathStrokeList* pathStroke = fPathStrokeList; pathStroke; pathStroke = pathStroke->fNext) {
        const SkStrokeRec& stroke = pathStroke->fStroke;
        if (fShaderFlags & ShaderFlags::kDynamicStroke) {
            // Strokes are dynamic. Update tolerances with every new stroke.
            patchWriter.updateTolerances(radialSegmentsPerRadianBuffer.fetchNext(pathStroke),
                                         stroke.getJoin());
            patchWriter.updateDynamicStroke(stroke);
        }
        if (fShaderFlags & ShaderFlags::kDynamicColor) {
            patchWriter.updateDynamicColor(pathStroke->fColor);
        }

        const SkPath& path = pathStroke->fPath;
        bool contourIsEmpty = true;
        for (auto [verb, p, w] : SkPathPriv::Iterate(path)) {
            bool prevJoinFitsInPatch;
            SkPoint scratchPts[4];
            const SkPoint* patchPts;
            SkPoint endControlPoint;
            switch (verb) {
                case SkPathVerb::kMove:
                    // "A subpath ... consisting of a single moveto shall not be stroked."
                    // https://www.w3.org/TR/SVG11/painting.html#StrokeProperties
                    if (!contourIsEmpty) {
                        patchWriter.writeCaps(p[-1], viewMatrix, stroke);
                    }
                    patchWriter.moveTo(p[0]);
                    contourIsEmpty = true;
                    continue;
                case SkPathVerb::kClose:
                    patchWriter.writeClose(p[0], viewMatrix, stroke);
                    contourIsEmpty = true;
                    continue;
                case SkPathVerb::kLine:
                    // Set this to false first, before the upcoming continue might disrupt our flow.
                    contourIsEmpty = false;
                    if (p[0] == p[1]) {
                        continue;
                    }
                    prevJoinFitsInPatch = patchWriter.lineFitsInPatch_withJoin();
                    scratchPts[0] = scratchPts[1] = p[0];
                    scratchPts[2] = scratchPts[3] = p[1];
                    patchPts = scratchPts;
                    endControlPoint = p[0];
                    break;
                case SkPathVerb::kQuad: {
                    contourIsEmpty = false;
                    if (p[1] == p[0] || p[1] == p[2]) {
                        // Zero-length paths need special treatment because they are spec'd to
                        // behave differently. If the control point is colocated on an endpoint then
                        // this might end up being the case. Fall back on a lineTo and let it make
                        // the final check.
                        patchWriter.writeLineTo(p[0], p[2]);
                        continue;
                    }
                    if (conic_has_cusp(p)) {
                        // Cusps are rare, but the tessellation shader can't handle them. Chop the
                        // curve into segments that the shader can handle.
                        SkPoint cusp = SkEvalQuadAt(p, SkFindQuadMidTangent(p));
                        patchWriter.writeLineTo(p[0], cusp);
                        patchWriter.writeLineTo(JoinType::kBowtie, cusp, p[2]);
                        continue;
                    }
                    float numParametricSegments_pow4 =
                            GrWangsFormula::quadratic_pow4(patchWriter.parametricIntolerance(), p);
                    if (!patchWriter.stroke180FitsInPatch(numParametricSegments_pow4)) {
                        // The curve requires more tessellation segments than the hardware can
                        // support. This is rare. Recursively chop until each sub-curve fits.
                        patchWriter.writeConicPatchesTo(p, 1);
                        continue;
                    }
                    // The curve fits in a single tessellation patch. This is the most common case.
                    // Write it out directly.
                    prevJoinFitsInPatch = patchWriter.stroke180FitsInPatch_withJoin(
                            numParametricSegments_pow4);
                    GrPathUtils::convertQuadToCubic(p, scratchPts);
                    patchPts = scratchPts;
                    endControlPoint = patchPts[2];
                    break;
                }
                case SkPathVerb::kConic: {
                    contourIsEmpty = false;
                    if (p[1] == p[0] || p[1] == p[2]) {
                        // Zero-length paths need special treatment because they are spec'd to
                        // behave differently. If the control point is colocated on an endpoint then
                        // this might end up being the case. Fall back on a lineTo and let it make
                        // the final check.
                        patchWriter.writeLineTo(p[0], p[2]);
                        continue;
                    }
                    if (conic_has_cusp(p)) {
                        // Cusps are rare, but the tessellation shader can't handle them. Chop the
                        // curve into segments that the shader can handle.
                        SkConic conic(p, *w);
                        SkPoint cusp = conic.evalAt(conic.findMidTangent());
                        patchWriter.writeLineTo(p[0], cusp);
                        patchWriter.writeLineTo(JoinType::kBowtie, cusp, p[2]);
                        continue;
                    }
                    // For now, the tessellation shader still uses Wang's quadratic formula when it
                    // draws conics.
                    // TODO: Update here when the shader starts using the real conic formula.
                    float numParametricSegments_pow4 =
                            GrWangsFormula::quadratic_pow4(patchWriter.parametricIntolerance(), p);
                    if (!patchWriter.stroke180FitsInPatch(numParametricSegments_pow4)) {
                        // The curve requires more tessellation segments than the hardware can
                        // support. This is rare. Recursively chop until each sub-curve fits.
                        patchWriter.writeConicPatchesTo(p, *w);
                        continue;
                    }
                    // The curve fits in a single tessellation patch. This is the most common
                    // case. Write it out directly.
                    prevJoinFitsInPatch = patchWriter.stroke180FitsInPatch_withJoin(
                            numParametricSegments_pow4);
                    GrPathShader::WriteConicPatch(p, *w, scratchPts);
                    patchPts = scratchPts;
                    endControlPoint = p[1];
                    break;
                }
                case SkPathVerb::kCubic: {
                    contourIsEmpty = false;
                    if (p[1] == p[2] && (p[1] == p[0] || p[1] == p[3])) {
                        // The stroke tessellation shader assigns special meaning to p0==p1==p2 and
                        // p1==p2==p3. If this is the case then we need to rewrite the cubic.
                        patchWriter.writeLineTo(p[0], p[3]);
                        continue;
                    }
                    float numParametricSegments_pow4 =
                            GrWangsFormula::cubic_pow4(patchWriter.parametricIntolerance(), p);
                    if (!patchWriter.stroke360FitsInPatch(numParametricSegments_pow4) ||
                        cubic_has_cusp(p)) {
                        // Either the curve requires more tessellation segments than the hardware
                        // can support, or it has cusp(s). Either case is rare. Chop it into
                        // sections that rotate 180 degrees or less (which will naturally be the
                        // cusp points if there are any), and then recursively chop each section
                        // until it fits.
                        patchWriter.writeCubicConvex180PatchesTo(p);
                        continue;
                    }
                    // The curve fits in a single tessellation patch. This is the most common case.
                    // Write it out directly.
                    prevJoinFitsInPatch = patchWriter.stroke360FitsInPatch_withJoin(
                            numParametricSegments_pow4);
                    patchPts = p;
                    endControlPoint = (p[2] != p[3]) ? p[2] : p[1];
                    break;
                }
            }
            patchWriter.writePatchTo(prevJoinFitsInPatch, patchPts, endControlPoint);
        }
        if (!contourIsEmpty) {
            const SkPoint* p = SkPathPriv::PointData(path);
            patchWriter.writeCaps(p[path.countPoints() - 1], viewMatrix, stroke);
        }
    }
}

void GrStrokeHardwareTessellator::draw(GrOpFlushState* flushState) const {
    for (const auto& chunk : fPatchChunks) {
        if (chunk.fPatchBuffer) {
            flushState->bindBuffers(nullptr, nullptr, std::move(chunk.fPatchBuffer));
            flushState->draw(chunk.fPatchCount, chunk.fBasePatch);
        }
    }
}