Adding upstream version 124.0.1.upstream/124.0.1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 539 insertions, 0 deletions

diff --git a/layout/painting/DottedCornerFinder.cpp b/layout/painting/DottedCornerFinder.cpp
new file mode 100644
index 0000000000..2e8408d80b
--- /dev/null
+++ b/layout/painting/DottedCornerFinder.cpp
@@ -0,0 +1,539 @@
+/* -*- 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 "DottedCornerFinder.h"
+
+#include <utility>
+
+#include "BorderCache.h"
+#include "BorderConsts.h"
+#include "nsTHashMap.h"
+
+namespace mozilla {
+
+using namespace gfx;
+
+static inline Float Square(Float x) { return x * x; }
+
+static Point PointRotateCCW90(const Point& aP) { return Point(aP.y, -aP.x); }
+
+struct BestOverlap {
+  Float overlap;
+  size_t count;
+
+  BestOverlap() : overlap(0.0f), count(0) {}
+
+  BestOverlap(Float aOverlap, size_t aCount)
+      : overlap(aOverlap), count(aCount) {}
+};
+
+static const size_t DottedCornerCacheSize = 256;
+nsTHashMap<FourFloatsHashKey, BestOverlap> DottedCornerCache;
+
+DottedCornerFinder::DottedCornerFinder(const Bezier& aOuterBezier,
+                                       const Bezier& aInnerBezier,
+                                       Corner aCorner, Float aBorderRadiusX,
+                                       Float aBorderRadiusY, const Point& aC0,
+                                       Float aR0, const Point& aCn, Float aRn,
+                                       const Size& aCornerDim)
+    : mOuterBezier(aOuterBezier),
+      mInnerBezier(aInnerBezier),
+      mCorner(aCorner),
+      mNormalSign((aCorner == C_TL || aCorner == C_BR) ? -1.0f : 1.0f),
+      mC0(aC0),
+      mCn(aCn),
+      mR0(aR0),
+      mRn(aRn),
+      mMaxR(std::max(aR0, aRn)),
+      mCenterCurveOrigin(mC0.x, mCn.y),
+      mCenterCurveR(0.0),
+      mInnerCurveOrigin(mInnerBezier.mPoints[0].x, mInnerBezier.mPoints[3].y),
+      mBestOverlap(0.0f),
+      mHasZeroBorderWidth(false),
+      mHasMore(true),
+      mMaxCount(aCornerDim.width + aCornerDim.height),
+      mType(OTHER),
+      mI(0),
+      mCount(0) {
+  NS_ASSERTION(mR0 > 0.0f || mRn > 0.0f,
+               "At least one side should have non-zero radius.");
+
+  mInnerWidth = fabs(mInnerBezier.mPoints[0].x - mInnerBezier.mPoints[3].x);
+  mInnerHeight = fabs(mInnerBezier.mPoints[0].y - mInnerBezier.mPoints[3].y);
+
+  DetermineType(aBorderRadiusX, aBorderRadiusY);
+
+  Reset();
+}
+
+static bool IsSingleCurve(Float aMinR, Float aMaxR, Float aMinBorderRadius,
+                          Float aMaxBorderRadius) {
+  return aMinR > 0.0f && aMinBorderRadius > aMaxR * 4.0f &&
+         aMinBorderRadius / aMaxBorderRadius > 0.5f;
+}
+
+void DottedCornerFinder::DetermineType(Float aBorderRadiusX,
+                                       Float aBorderRadiusY) {
+  // Calculate parameters for the center curve before swap.
+  Float centerCurveWidth = fabs(mC0.x - mCn.x);
+  Float centerCurveHeight = fabs(mC0.y - mCn.y);
+  Point cornerPoint(mCn.x, mC0.y);
+
+  bool swapped = false;
+  if (mR0 < mRn) {
+    // Always draw from wider side to thinner side.
+    std::swap(mC0, mCn);
+    std::swap(mR0, mRn);
+    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]);
+    mNormalSign = -mNormalSign;
+    swapped = true;
+  }
+
+  // See the comment at mType declaration for each condition.
+
+  Float minR = std::min(mR0, mRn);
+  Float minBorderRadius = std::min(aBorderRadiusX, aBorderRadiusY);
+  Float maxBorderRadius = std::max(aBorderRadiusX, aBorderRadiusY);
+  if (IsSingleCurve(minR, mMaxR, minBorderRadius, maxBorderRadius)) {
+    if (mR0 == mRn) {
+      Float borderLength;
+      if (minBorderRadius == maxBorderRadius) {
+        mType = PERFECT;
+        borderLength = M_PI * centerCurveHeight / 2.0f;
+
+        mCenterCurveR = centerCurveWidth;
+      } else {
+        mType = SINGLE_CURVE_AND_RADIUS;
+        borderLength =
+            GetQuarterEllipticArcLength(centerCurveWidth, centerCurveHeight);
+      }
+
+      Float diameter = mR0 * 2.0f;
+      size_t count = round(borderLength / diameter);
+      if (count % 2) {
+        count++;
+      }
+      mCount = count / 2 - 1;
+      if (mCount > 0) {
+        mBestOverlap = 1.0f - borderLength / (diameter * count);
+      }
+    } else {
+      mType = SINGLE_CURVE;
+    }
+  }
+
+  if (mType == SINGLE_CURVE_AND_RADIUS || mType == SINGLE_CURVE) {
+    Size cornerSize(centerCurveWidth, centerCurveHeight);
+    GetBezierPointsForCorner(&mCenterBezier, mCorner, cornerPoint, cornerSize);
+    if (swapped) {
+      std::swap(mCenterBezier.mPoints[0], mCenterBezier.mPoints[3]);
+      std::swap(mCenterBezier.mPoints[1], mCenterBezier.mPoints[2]);
+    }
+  }
+
+  if (minR == 0.0f) {
+    mHasZeroBorderWidth = true;
+  }
+
+  if ((mType == SINGLE_CURVE || mType == OTHER) && !mHasZeroBorderWidth) {
+    FindBestOverlap(minR, minBorderRadius, maxBorderRadius);
+  }
+}
+
+bool DottedCornerFinder::HasMore(void) const {
+  if (mHasZeroBorderWidth) {
+    return mI < mMaxCount && mHasMore;
+  }
+
+  return mI < mCount;
+}
+
+DottedCornerFinder::Result DottedCornerFinder::Next(void) {
+  mI++;
+
+  if (mType == PERFECT) {
+    Float phi = mI * 4.0f * mR0 * (1 - mBestOverlap) / mCenterCurveR;
+    if (mCorner == C_TL) {
+      phi = -M_PI / 2.0f - phi;
+    } else if (mCorner == C_TR) {
+      phi = -M_PI / 2.0f + phi;
+    } else if (mCorner == C_BR) {
+      phi = M_PI / 2.0f - phi;
+    } else {
+      phi = M_PI / 2.0f + phi;
+    }
+
+    Point C(mCenterCurveOrigin.x + mCenterCurveR * cos(phi),
+            mCenterCurveOrigin.y + mCenterCurveR * sin(phi));
+    return DottedCornerFinder::Result(C, mR0);
+  }
+
+  // Find unfilled and filled circles.
+  (void)FindNext(mBestOverlap);
+  if (mHasMore) {
+    (void)FindNext(mBestOverlap);
+  }
+
+  return Result(mLastC, mLastR);
+}
+
+void DottedCornerFinder::Reset(void) {
+  mLastC = mC0;
+  mLastR = mR0;
+  mLastT = 0.0f;
+  mHasMore = true;
+}
+
+void DottedCornerFinder::FindPointAndRadius(Point& C, Float& r,
+                                            const Point& innerTangent,
+                                            const Point& normal, Float t) {
+  // Find radius for the given tangent point on the inner curve such that the
+  // circle is also tangent to the outer curve.
+
+  NS_ASSERTION(mType == OTHER, "Wrong mType");
+
+  Float lower = 0.0f;
+  Float upper = mMaxR;
+  const Float DIST_MARGIN = 0.1f;
+  for (size_t i = 0; i < MAX_LOOP; i++) {
+    r = (upper + lower) / 2.0f;
+    C = innerTangent + normal * r;
+
+    Point Near = FindBezierNearestPoint(mOuterBezier, C, t);
+    Float distSquare = (C - Near).LengthSquare();
+
+    if (distSquare > Square(r + DIST_MARGIN)) {
+      lower = r;
+    } else if (distSquare < Square(r - DIST_MARGIN)) {
+      upper = r;
+    } else {
+      break;
+    }
+  }
+}
+
+Float DottedCornerFinder::FindNext(Float overlap) {
+  Float lower = mLastT;
+  Float upper = 1.0f;
+  Float t;
+
+  Point C = mLastC;
+  Float r = 0.0f;
+
+  Float factor = (1.0f - overlap);
+
+  Float circlesDist = 0.0f;
+  Float expectedDist = 0.0f;
+
+  const Float DIST_MARGIN = 0.1f;
+  if (mType == SINGLE_CURVE_AND_RADIUS) {
+    r = mR0;
+
+    expectedDist = (r + mLastR) * factor;
+
+    // Find C_i on the center curve.
+    for (size_t i = 0; i < MAX_LOOP; i++) {
+      t = (upper + lower) / 2.0f;
+      C = GetBezierPoint(mCenterBezier, t);
+
+      // Check overlap along arc.
+      circlesDist = GetBezierLength(mCenterBezier, mLastT, t);
+      if (circlesDist < expectedDist - DIST_MARGIN) {
+        lower = t;
+      } else if (circlesDist > expectedDist + DIST_MARGIN) {
+        upper = t;
+      } else {
+        break;
+      }
+    }
+  } else if (mType == SINGLE_CURVE) {
+    // Find C_i on the center curve, and calculate r_i.
+    for (size_t i = 0; i < MAX_LOOP; i++) {
+      t = (upper + lower) / 2.0f;
+      C = GetBezierPoint(mCenterBezier, t);
+
+      Point Diff = GetBezierDifferential(mCenterBezier, t);
+      Float DiffLength = Diff.Length();
+      if (DiffLength == 0.0f) {
+        // Basically this shouldn't happen.
+        // If differential is 0, we cannot calculate tangent circle,
+        // skip this point.
+        t = (t + upper) / 2.0f;
+        continue;
+      }
+
+      Point normal = PointRotateCCW90(Diff / DiffLength) * (-mNormalSign);
+      r = CalculateDistanceToEllipticArc(C, normal, mInnerCurveOrigin,
+                                         mInnerWidth, mInnerHeight);
+
+      // Check overlap along arc.
+      circlesDist = GetBezierLength(mCenterBezier, mLastT, t);
+      expectedDist = (r + mLastR) * factor;
+      if (circlesDist < expectedDist - DIST_MARGIN) {
+        lower = t;
+      } else if (circlesDist > expectedDist + DIST_MARGIN) {
+        upper = t;
+      } else {
+        break;
+      }
+    }
+  } else {
+    Float distSquareMax = Square(mMaxR * 3.0f);
+    Float circlesDistSquare = 0.0f;
+
+    // Find C_i and r_i.
+    for (size_t i = 0; i < MAX_LOOP; i++) {
+      t = (upper + lower) / 2.0f;
+      Point innerTangent = GetBezierPoint(mInnerBezier, t);
+      if ((innerTangent - mLastC).LengthSquare() > distSquareMax) {
+        // It's clear that this tangent point is too far, skip it.
+        upper = t;
+        continue;
+      }
+
+      Point Diff = GetBezierDifferential(mInnerBezier, t);
+      Float DiffLength = Diff.Length();
+      if (DiffLength == 0.0f) {
+        // Basically this shouldn't happen.
+        // If differential is 0, we cannot calculate tangent circle,
+        // skip this point.
+        t = (t + upper) / 2.0f;
+        continue;
+      }
+
+      Point normal = PointRotateCCW90(Diff / DiffLength) * mNormalSign;
+      FindPointAndRadius(C, r, innerTangent, normal, t);
+
+      // Check overlap with direct distance.
+      circlesDistSquare = (C - mLastC).LengthSquare();
+      expectedDist = (r + mLastR) * factor;
+      if (circlesDistSquare < Square(expectedDist - DIST_MARGIN)) {
+        lower = t;
+      } else if (circlesDistSquare > Square(expectedDist + DIST_MARGIN)) {
+        upper = t;
+      } else {
+        break;
+      }
+    }
+
+    circlesDist = sqrt(circlesDistSquare);
+  }
+
+  if (mHasZeroBorderWidth) {
+    // When calculating circle around r=0, it may result in wrong radius that
+    // is bigger than previous circle.  Detect it and stop calculating.
+    const Float R_MARGIN = 0.1f;
+    if (mLastR < R_MARGIN && r > mLastR) {
+      mHasMore = false;
+      mLastR = 0.0f;
+      return 0.0f;
+    }
+  }
+
+  mLastT = t;
+  mLastC = C;
+  mLastR = r;
+
+  if (mHasZeroBorderWidth) {
+    const Float T_MARGIN = 0.001f;
+    if (mLastT >= 1.0f - T_MARGIN ||
+        (mLastC - mCn).LengthSquare() < Square(mLastR)) {
+      mHasMore = false;
+    }
+  }
+
+  if (expectedDist == 0.0f) {
+    return 0.0f;
+  }
+
+  return 1.0f - circlesDist * factor / expectedDist;
+}
+
+void DottedCornerFinder::FindBestOverlap(Float aMinR, Float aMinBorderRadius,
+                                         Float aMaxBorderRadius) {
+  // If overlap is not calculateable, find it with binary search,
+  // such that there exists i that C_i == C_n with the given overlap.
+
+  FourFloats key(aMinR, mMaxR, aMinBorderRadius, aMaxBorderRadius);
+  BestOverlap best;
+  if (DottedCornerCache.Get(key, &best)) {
+    mCount = best.count;
+    mBestOverlap = best.overlap;
+    return;
+  }
+
+  Float lower = 0.0f;
+  Float upper = 0.5f;
+  // Start from lower bound to find the minimum number of circles.
+  Float overlap = 0.0f;
+  mBestOverlap = overlap;
+  size_t targetCount = 0;
+
+  const Float OVERLAP_MARGIN = 0.1f;
+  for (size_t j = 0; j < MAX_LOOP; j++) {
+    Reset();
+
+    size_t count;
+    Float actualOverlap;
+    if (!GetCountAndLastOverlap(overlap, &count, &actualOverlap)) {
+      if (j == 0) {
+        mCount = mMaxCount;
+        break;
+      }
+    }
+
+    if (j == 0) {
+      if (count < 3 || (count == 3 && actualOverlap > 0.5f)) {
+        // |count == 3 && actualOverlap > 0.5f| means there could be
+        // a circle but it is too near from both ends.
+        //
+        // if actualOverlap == 0.0
+        //               1       2       3
+        //   +-------+-------+-------+-------+
+        //   | ##### | ***** | ##### | ##### |
+        //   |#######|*******|#######|#######|
+        //   |###+###|***+***|###+###|###+###|
+        //   |# C_0 #|* C_1 *|# C_2 #|# C_n #|
+        //   | ##### | ***** | ##### | ##### |
+        //   +-------+-------+-------+-------+
+        //                   |
+        //                   V
+        //   +-------+---+-------+---+-------+
+        //   | ##### |   | ##### |   | ##### |
+        //   |#######|   |#######|   |#######|
+        //   |###+###|   |###+###|   |###+###| Find the best overlap to place
+        //   |# C_0 #|   |# C_1 #|   |# C_n #| C_1 at the middle of them
+        //   | ##### |   | ##### |   | ##### |
+        //   +-------+---+-------+---|-------+
+        //
+        // if actualOverlap == 0.5
+        //               1       2     3
+        //   +-------+-------+-------+---+
+        //   | ##### | ***** | ##### |## |
+        //   |#######|*******|##### C_n #|
+        //   |###+###|***+***|###+###+###|
+        //   |# C_0 #|* C_1 *|# C_2 #|###|
+        //   | ##### | ***** | ##### |## |
+        //   +-------+-------+-------+---+
+        //                 |
+        //                 V
+        //   +-------+-+-------+-+-------+
+        //   | ##### | | ##### | | ##### |
+        //   |#######| |#######| |#######|
+        //   |###+###| |###+###| |###+###| Even if we place C_1 at the middle
+        //   |# C_0 #| |# C_1 #| |# C_n #| of them, it's too near from them
+        //   | ##### | | ##### | | ##### |
+        //   +-------+-+-------+-|-------+
+        //                 |
+        //                 V
+        //   +-------+-----------+-------+
+        //   | ##### |           | ##### |
+        //   |#######|           |#######|
+        //   |###+###|           |###+###| Do not draw any circle
+        //   |# C_0 #|           |# C_n #|
+        //   | ##### |           | ##### |
+        //   +-------+-----------+-------+
+        mCount = 0;
+        break;
+      }
+
+      // targetCount should be 2n, as we're searching C_1 to C_n.
+      //
+      //   targetCount = 4
+      //   mCount = 1
+      //               1       2       3       4
+      //   +-------+-------+-------+-------+-------+
+      //   | ##### | ***** | ##### | ***** | ##### |
+      //   |#######|*******|#######|*******|#######|
+      //   |###+###|***+***|###+###|***+***|###+###|
+      //   |# C_0 #|* C_1 *|# C_2 #|* C_3 *|# C_n #|
+      //   | ##### | ***** | ##### | ***** | ##### |
+      //   +-------+-------+-------+-------+-------+
+      //                       1
+      //
+      //   targetCount = 6
+      //   mCount = 2
+      //               1       2       3       4       5       6
+      //   +-------+-------+-------+-------+-------+-------+-------+
+      //   | ##### | ***** | ##### | ***** | ##### | ***** | ##### |
+      //   |#######|*******|#######|*******|#######|*******|#######|
+      //   |###+###|***+***|###+###|***+***|###+###|***+***|###+###|
+      //   |# C_0 #|* C_1 *|# C_2 #|* C_3 *|# C_4 #|* C_5 *|# C_n #|
+      //   | ##### | ***** | ##### | ***** | ##### | ***** | ##### |
+      //   +-------+-------+-------+-------+-------+-------+-------+
+      //                       1               2
+      if (count % 2) {
+        targetCount = count + 1;
+      } else {
+        targetCount = count;
+      }
+
+      mCount = targetCount / 2 - 1;
+    }
+
+    if (count == targetCount) {
+      mBestOverlap = overlap;
+
+      if (fabs(actualOverlap - overlap) < OVERLAP_MARGIN) {
+        break;
+      }
+
+      // We started from upper bound, no need to update range when j == 0.
+      if (j > 0) {
+        if (actualOverlap > overlap) {
+          lower = overlap;
+        } else {
+          upper = overlap;
+        }
+      }
+    } 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) {
+          upper = overlap;
+        } else {
+          lower = overlap;
+        }
+      }
+    }
+
+    overlap = (upper + lower) / 2.0f;
+  }
+
+  if (DottedCornerCache.Count() > DottedCornerCacheSize) {
+    DottedCornerCache.Clear();
+  }
+  DottedCornerCache.InsertOrUpdate(key, BestOverlap(mBestOverlap, mCount));
+}
+
+bool DottedCornerFinder::GetCountAndLastOverlap(Float aOverlap, size_t* aCount,
+                                                Float* aActualOverlap) {
+  // Return the number of circles and the last circles' overlap for the
+  // given overlap.
+
+  Reset();
+
+  const Float T_MARGIN = 0.001f;
+  const Float DIST_MARGIN = 0.1f;
+  const Float DIST_MARGIN_SQUARE = Square(DIST_MARGIN);
+  for (size_t i = 0; i < mMaxCount; i++) {
+    Float actualOverlap = FindNext(aOverlap);
+    if (mLastT >= 1.0f - T_MARGIN ||
+        (mLastC - mCn).LengthSquare() < DIST_MARGIN_SQUARE) {
+      *aCount = i + 1;
+      *aActualOverlap = actualOverlap;
+      return true;
+    }
+  }
+
+  return false;
+}
+
+}  // namespace mozilla