From 36d22d82aa202bb199967e9512281e9a53db42c9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 21:33:14 +0200 Subject: Adding upstream version 115.7.0esr. Signed-off-by: Daniel Baumann --- layout/painting/DashedCornerFinder.cpp | 416 +++++++++++++++++++++++++++++++++ 1 file changed, 416 insertions(+) create mode 100644 layout/painting/DashedCornerFinder.cpp (limited to 'layout/painting/DashedCornerFinder.cpp') diff --git a/layout/painting/DashedCornerFinder.cpp b/layout/painting/DashedCornerFinder.cpp new file mode 100644 index 0000000000..c892179df9 --- /dev/null +++ b/layout/painting/DashedCornerFinder.cpp @@ -0,0 +1,416 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* vim: set ts=8 sts=2 et sw=2 tw=80: */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include "DashedCornerFinder.h" + +#include + +#include "BorderCache.h" +#include "BorderConsts.h" +#include "nsTHashMap.h" + +namespace mozilla { + +using namespace gfx; + +struct BestDashLength { + typedef mozilla::gfx::Float Float; + + Float dashLength; + size_t count; + + BestDashLength() : dashLength(0.0f), count(0) {} + + BestDashLength(Float aDashLength, size_t aCount) + : dashLength(aDashLength), count(aCount) {} +}; + +static const size_t DashedCornerCacheSize = 256; +nsTHashMap DashedCornerCache; + +DashedCornerFinder::DashedCornerFinder(const Bezier& aOuterBezier, + const Bezier& aInnerBezier, + Float aBorderWidthH, Float aBorderWidthV, + const Size& aCornerDim) + : mOuterBezier(aOuterBezier), + mInnerBezier(aInnerBezier), + mLastOuterP(aOuterBezier.mPoints[0]), + mLastInnerP(aInnerBezier.mPoints[0]), + mLastOuterT(0.0f), + mLastInnerT(0.0f), + mBestDashLength(DOT_LENGTH * DASH_LENGTH), + mHasZeroBorderWidth(false), + mHasMore(true), + mMaxCount(aCornerDim.width + aCornerDim.height), + mType(OTHER), + mI(0), + mCount(0) { + NS_ASSERTION(aBorderWidthH > 0.0f || aBorderWidthV > 0.0f, + "At least one side should have non-zero width."); + + DetermineType(aBorderWidthH, aBorderWidthV); + + Reset(); +} + +void DashedCornerFinder::DetermineType(Float aBorderWidthH, + Float aBorderWidthV) { + if (aBorderWidthH < aBorderWidthV) { + // Always draw from wider side to thinner side. + std::swap(mInnerBezier.mPoints[0], mInnerBezier.mPoints[3]); + std::swap(mInnerBezier.mPoints[1], mInnerBezier.mPoints[2]); + std::swap(mOuterBezier.mPoints[0], mOuterBezier.mPoints[3]); + std::swap(mOuterBezier.mPoints[1], mOuterBezier.mPoints[2]); + mLastOuterP = mOuterBezier.mPoints[0]; + mLastInnerP = mInnerBezier.mPoints[0]; + } + + // See the comment at mType declaration for each condition. + + Float borderRadiusA = + fabs(mOuterBezier.mPoints[0].x - mOuterBezier.mPoints[3].x); + Float borderRadiusB = + fabs(mOuterBezier.mPoints[0].y - mOuterBezier.mPoints[3].y); + if (aBorderWidthH == aBorderWidthV && borderRadiusA == borderRadiusB && + borderRadiusA > aBorderWidthH * 2.0f) { + Float curveHeight = borderRadiusA - aBorderWidthH / 2.0; + + mType = PERFECT; + Float borderLength = M_PI * curveHeight / 2.0f; + + Float dashWidth = aBorderWidthH * DOT_LENGTH * DASH_LENGTH; + size_t count = ceil(borderLength / dashWidth); + if (count % 2) { + count++; + } + mCount = count / 2 + 1; + mBestDashLength = borderLength / (aBorderWidthH * count); + } + + Float minBorderWidth = std::min(aBorderWidthH, aBorderWidthV); + if (minBorderWidth == 0.0f) { + mHasZeroBorderWidth = true; + } + + if (mType == OTHER && !mHasZeroBorderWidth) { + Float minBorderRadius = std::min(borderRadiusA, borderRadiusB); + Float maxBorderRadius = std::max(borderRadiusA, borderRadiusB); + Float maxBorderWidth = std::max(aBorderWidthH, aBorderWidthV); + + FindBestDashLength(minBorderWidth, maxBorderWidth, minBorderRadius, + maxBorderRadius); + } +} + +bool DashedCornerFinder::HasMore(void) const { + if (mHasZeroBorderWidth) { + return mI < mMaxCount && mHasMore; + } + + return mI < mCount; +} + +DashedCornerFinder::Result DashedCornerFinder::Next(void) { + Float lastOuterT, lastInnerT, outerT, innerT; + + if (mI == 0) { + lastOuterT = 0.0f; + lastInnerT = 0.0f; + } else { + if (mType == PERFECT) { + lastOuterT = lastInnerT = (mI * 2.0f - 0.5f) / ((mCount - 1) * 2.0f); + } else { + Float last2OuterT = mLastOuterT; + Float last2InnerT = mLastInnerT; + + (void)FindNext(mBestDashLength); + + // + // mLastOuterT lastOuterT + // | | + // v v + // +---+---+---+---+ <- last2OuterT + // | |###|###| | + // | |###|###| | + // | |###|###| | + // +---+---+---+---+ <- last2InnerT + // ^ ^ + // | | + // mLastInnerT lastInnerT + lastOuterT = (mLastOuterT + last2OuterT) / 2.0f; + lastInnerT = (mLastInnerT + last2InnerT) / 2.0f; + } + } + + if ((!mHasZeroBorderWidth && mI == mCount - 1) || + (mHasZeroBorderWidth && !mHasMore)) { + outerT = 1.0f; + innerT = 1.0f; + } else { + if (mType == PERFECT) { + outerT = innerT = (mI * 2.0f + 0.5f) / ((mCount - 1) * 2.0f); + } else { + Float last2OuterT = mLastOuterT; + Float last2InnerT = mLastInnerT; + + (void)FindNext(mBestDashLength); + + // + // outerT last2OuterT + // | | + // v v + // mLastOuterT -> +---+---+---+---+ + // | |###|###| | + // | |###|###| | + // | |###|###| | + // mLastInnerT -> +---+---+---+---+ + // ^ ^ + // | | + // innerT last2InnerT + outerT = (mLastOuterT + last2OuterT) / 2.0f; + innerT = (mLastInnerT + last2InnerT) / 2.0f; + } + } + + mI++; + + Bezier outerSectionBezier; + Bezier innerSectionBezier; + GetSubBezier(&outerSectionBezier, mOuterBezier, lastOuterT, outerT); + GetSubBezier(&innerSectionBezier, mInnerBezier, lastInnerT, innerT); + return DashedCornerFinder::Result(outerSectionBezier, innerSectionBezier); +} + +void DashedCornerFinder::Reset(void) { + mLastOuterP = mOuterBezier.mPoints[0]; + mLastInnerP = mInnerBezier.mPoints[0]; + mLastOuterT = 0.0f; + mLastInnerT = 0.0f; + mHasMore = true; +} + +Float DashedCornerFinder::FindNext(Float dashLength) { + Float upper = 1.0f; + Float lower = mLastOuterT; + + Point OuterP, InnerP; + // Start from upper bound to check if this is the last segment. + Float outerT = upper; + Float innerT; + Float W = 0.0f; + Float L = 0.0f; + + const Float LENGTH_MARGIN = 0.1f; + for (size_t i = 0; i < MAX_LOOP; i++) { + OuterP = GetBezierPoint(mOuterBezier, outerT); + InnerP = FindBezierNearestPoint(mInnerBezier, OuterP, outerT, &innerT); + + // Calculate approximate dash length. + // + // W = (W1 + W2) / 2 + // L = (OuterL + InnerL) / 2 + // dashLength = L / W + // + // ____----+----____ + // OuterP ___--- | ---___ mLastOuterP + // +--- | ---+ + // | | | + // | | | + // | W | W1 | + // | | | + // W2 | | | + // | | ______------+ + // | ____+---- mLastInnerP + // | ___--- + // | __--- + // +-- + // InnerP + // OuterL + // ____---------____ + // OuterP ___--- ---___ mLastOuterP + // +--- ---+ + // | L | + // | ___----------______ | + // | __--- -----+ + // | __-- | + // +-- | + // | InnerL ______------+ + // | ____----- mLastInnerP + // | ___--- + // | __--- + // +-- + // InnerP + Float W1 = (mLastOuterP - mLastInnerP).Length(); + Float W2 = (OuterP - InnerP).Length(); + Float OuterL = GetBezierLength(mOuterBezier, mLastOuterT, outerT); + Float InnerL = GetBezierLength(mInnerBezier, mLastInnerT, innerT); + W = (W1 + W2) / 2.0f; + L = (OuterL + InnerL) / 2.0f; + if (L > W * dashLength + LENGTH_MARGIN) { + if (i > 0) { + upper = outerT; + } + } else if (L < W * dashLength - LENGTH_MARGIN) { + if (i == 0) { + // This is the last segment with shorter dashLength. + mHasMore = false; + break; + } + lower = outerT; + } else { + break; + } + + outerT = (upper + lower) / 2.0f; + } + + mLastOuterP = OuterP; + mLastInnerP = InnerP; + mLastOuterT = outerT; + mLastInnerT = innerT; + + if (W == 0.0f) { + return 1.0f; + } + + return L / W; +} + +void DashedCornerFinder::FindBestDashLength(Float aMinBorderWidth, + Float aMaxBorderWidth, + Float aMinBorderRadius, + Float aMaxBorderRadius) { + // If dashLength is not calculateable, find it with binary search, + // such that there exists i that OuterP_i == OuterP_n and + // InnerP_i == InnerP_n with given dashLength. + + FourFloats key(aMinBorderWidth, aMaxBorderWidth, aMinBorderRadius, + aMaxBorderRadius); + BestDashLength best; + if (DashedCornerCache.Get(key, &best)) { + mCount = best.count; + mBestDashLength = best.dashLength; + return; + } + + Float lower = 1.0f; + Float upper = DOT_LENGTH * DASH_LENGTH; + Float dashLength = upper; + size_t targetCount = 0; + + const Float LENGTH_MARGIN = 0.1f; + for (size_t j = 0; j < MAX_LOOP; j++) { + size_t count; + Float actualDashLength; + if (!GetCountAndLastDashLength(dashLength, &count, &actualDashLength)) { + if (j == 0) { + mCount = mMaxCount; + break; + } + } + + if (j == 0) { + if (count == 1) { + // If only 1 segment fits, fill entire region + // + // count = 1 + // mCount = 1 + // | 1 | + // +---+---+ + // |###|###| + // |###|###| + // |###|###| + // +---+---+ + // 1 + mCount = 1; + break; + } + + // targetCount should be 2n. + // + // targetCount = 2 + // mCount = 2 + // | 1 | 2 | + // +---+---+---+---+ + // |###| | |###| + // |###| | |###| + // |###| | |###| + // +---+---+---+---+ + // 1 2 + // + // targetCount = 6 + // mCount = 4 + // | 1 | 2 | 3 | 4 | 5 | 6 | + // +---+---+---+---+---+---+---+---+---+---+---+---+ + // |###| | |###|###| | |###|###| | |###| + // |###| | |###|###| | |###|###| | |###| + // |###| | |###|###| | |###|###| | |###| + // +---+---+---+---+---+---+---+---+---+---+---+---+ + // 1 2 3 4 + if (count % 2) { + targetCount = count + 1; + } else { + targetCount = count; + } + + mCount = targetCount / 2 + 1; + } + + if (count == targetCount) { + mBestDashLength = dashLength; + + // actualDashLength won't be greater than dashLength. + if (actualDashLength > dashLength - LENGTH_MARGIN) { + break; + } + + // We started from upper bound, no need to update range when j == 0. + if (j > 0) { + upper = dashLength; + } + } else { + // |j == 0 && count != targetCount| means that |targetCount = count + 1|, + // and we started from upper bound, no need to update range when j == 0. + if (j > 0) { + if (count > targetCount) { + lower = dashLength; + } else { + upper = dashLength; + } + } + } + + dashLength = (upper + lower) / 2.0f; + } + + if (DashedCornerCache.Count() > DashedCornerCacheSize) { + DashedCornerCache.Clear(); + } + DashedCornerCache.InsertOrUpdate(key, + BestDashLength(mBestDashLength, mCount)); +} + +bool DashedCornerFinder::GetCountAndLastDashLength(Float aDashLength, + size_t* aCount, + Float* aActualDashLength) { + // Return the number of segments and the last segment's dashLength for + // the given dashLength. + + Reset(); + + for (size_t i = 0; i < mMaxCount; i++) { + Float actualDashLength = FindNext(aDashLength); + if (mLastOuterT >= 1.0f) { + *aCount = i + 1; + *aActualDashLength = actualDashLength; + return true; + } + } + + return false; +} + +} // namespace mozilla -- cgit v1.2.3