/src/mozilla-central/layout/painting/DashedCornerFinder.cpp

Source (jump to first uncovered line)
/* -*- 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 "mozilla/Move.h"
#include "BorderCache.h"
#include "BorderConsts.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;
nsDataHashtable<FourFloatsHashKey, BestDashLength> 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.
    Swap(mInnerBezier.mPoints[0], mInnerBezier.mPoints[3]);
    Swap(mInnerBezier.mPoints[1], mInnerBezier.mPoints[2]);
    Swap(mOuterBezier.mPoints[0], mOuterBezier.mPoints[3]);
    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.Put(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

Coverage Report

Created: 2018-09-25 14:53

Line	Count	Source (jump to first uncovered line)
1		/* -- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -- */
2		/* vim: set ts=8 sts=2 et sw=2 tw=80: */
3		/* This Source Code Form is subject to the terms of the Mozilla Public
4		* License, v. 2.0. If a copy of the MPL was not distributed with this
5		* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7		#include "DashedCornerFinder.h"
8
9		#include "mozilla/Move.h"
10		#include "BorderCache.h"
11		#include "BorderConsts.h"
12
13		namespace mozilla {
14
15		using namespace gfx;
16
17		struct BestDashLength
18		{
19		typedef mozilla::gfx::Float Float;
20
21		Float dashLength;
22		size_t count;
23
24		BestDashLength()
25		: dashLength(0.0f)
26		, count(0)
27	0	{
28	0	}
29
30		BestDashLength(Float aDashLength, size_t aCount)
31		: dashLength(aDashLength)
32		, count(aCount)
33	0	{
34	0	}
35		};
36
37		static const size_t DashedCornerCacheSize = 256;
38		nsDataHashtable<FourFloatsHashKey, BestDashLength> DashedCornerCache;
39
40		DashedCornerFinder::DashedCornerFinder(const Bezier& aOuterBezier,
41		const Bezier& aInnerBezier,
42		Float aBorderWidthH,
43		Float aBorderWidthV,
44		const Size& aCornerDim)
45		: mOuterBezier(aOuterBezier)
46		, mInnerBezier(aInnerBezier)
47		, mLastOuterP(aOuterBezier.mPoints[0])
48		, mLastInnerP(aInnerBezier.mPoints[0])
49		, mLastOuterT(0.0f)
50		, mLastInnerT(0.0f)
51		, mBestDashLength(DOT_LENGTH * DASH_LENGTH)
52		, mHasZeroBorderWidth(false)
53		, mHasMore(true)
54		, mMaxCount(aCornerDim.width + aCornerDim.height)
55		, mType(OTHER)
56		, mI(0)
57		, mCount(0)
58	0	{
59	0	NS_ASSERTION(aBorderWidthH > 0.0f \|\| aBorderWidthV > 0.0f,
60	0	"At least one side should have non-zero width.");
61	0
62	0	DetermineType(aBorderWidthH, aBorderWidthV);
63	0
64	0	Reset();
65	0	}
66
67		void
68		DashedCornerFinder::DetermineType(Float aBorderWidthH, Float aBorderWidthV)
69	0	{
70	0	if (aBorderWidthH < aBorderWidthV) {
71	0	// Always draw from wider side to thinner side.
72	0	Swap(mInnerBezier.mPoints[0], mInnerBezier.mPoints[3]);
73	0	Swap(mInnerBezier.mPoints[1], mInnerBezier.mPoints[2]);
74	0	Swap(mOuterBezier.mPoints[0], mOuterBezier.mPoints[3]);
75	0	Swap(mOuterBezier.mPoints[1], mOuterBezier.mPoints[2]);
76	0	mLastOuterP = mOuterBezier.mPoints[0];
77	0	mLastInnerP = mInnerBezier.mPoints[0];
78	0	}
79	0
80	0	// See the comment at mType declaration for each condition.
81	0
82	0	Float borderRadiusA =
83	0	fabs(mOuterBezier.mPoints[0].x - mOuterBezier.mPoints[3].x);
84	0	Float borderRadiusB =
85	0	fabs(mOuterBezier.mPoints[0].y - mOuterBezier.mPoints[3].y);
86	0	if (aBorderWidthH == aBorderWidthV && borderRadiusA == borderRadiusB &&
87	0	borderRadiusA > aBorderWidthH * 2.0f) {
88	0	Float curveHeight = borderRadiusA - aBorderWidthH / 2.0;
89	0
90	0	mType = PERFECT;
91	0	Float borderLength = M_PI * curveHeight / 2.0f;
92	0
93	0	Float dashWidth = aBorderWidthH * DOT_LENGTH * DASH_LENGTH;
94	0	size_t count = ceil(borderLength / dashWidth);
95	0	if (count % 2) {
96	0	count++;
97	0	}
98	0	mCount = count / 2 + 1;
99	0	mBestDashLength = borderLength / (aBorderWidthH * count);
100	0	}
101	0
102	0	Float minBorderWidth = std::min(aBorderWidthH, aBorderWidthV);
103	0	if (minBorderWidth == 0.0f) {
104	0	mHasZeroBorderWidth = true;
105	0	}
106	0
107	0	if (mType == OTHER && !mHasZeroBorderWidth) {
108	0	Float minBorderRadius = std::min(borderRadiusA, borderRadiusB);
109	0	Float maxBorderRadius = std::max(borderRadiusA, borderRadiusB);
110	0	Float maxBorderWidth = std::max(aBorderWidthH, aBorderWidthV);
111	0
112	0	FindBestDashLength(
113	0	minBorderWidth, maxBorderWidth, minBorderRadius, maxBorderRadius);
114	0	}
115	0	}
116
117		bool
118		DashedCornerFinder::HasMore(void) const
119	0	{
120	0	if (mHasZeroBorderWidth) {
121	0	return mI < mMaxCount && mHasMore;
122	0	}
123	0
124	0	return mI < mCount;
125	0	}
126
127		DashedCornerFinder::Result
128		DashedCornerFinder::Next(void)
129	0	{
130	0	Float lastOuterT, lastInnerT, outerT, innerT;
131	0
132	0	if (mI == 0) {
133	0	lastOuterT = 0.0f;
134	0	lastInnerT = 0.0f;
135	0	} else {
136	0	if (mType == PERFECT) {
137	0	lastOuterT = lastInnerT = (mI * 2.0f - 0.5f) / ((mCount - 1) * 2.0f);
138	0	} else {
139	0	Float last2OuterT = mLastOuterT;
140	0	Float last2InnerT = mLastInnerT;
141	0
142	0	(void)FindNext(mBestDashLength);
143	0
144	0	//
145	0	// mLastOuterT lastOuterT
146	0	// \| \|
147	0	// v v
148	0	// +---+---+---+---+ <- last2OuterT
149	0	// \| \|###\|###\| \|
150	0	// \| \|###\|###\| \|
151	0	// \| \|###\|###\| \|
152	0	// +---+---+---+---+ <- last2InnerT
153	0	// ^ ^
154	0	// \| \|
155	0	// mLastInnerT lastInnerT
156	0	lastOuterT = (mLastOuterT + last2OuterT) / 2.0f;
157	0	lastInnerT = (mLastInnerT + last2InnerT) / 2.0f;
158	0	}
159	0	}
160	0
161	0	if ((!mHasZeroBorderWidth && mI == mCount - 1) \|\|
162	0	(mHasZeroBorderWidth && !mHasMore)) {
163	0	outerT = 1.0f;
164	0	innerT = 1.0f;
165	0	} else {
166	0	if (mType == PERFECT) {
167	0	outerT = innerT = (mI * 2.0f + 0.5f) / ((mCount - 1) * 2.0f);
168	0	} else {
169	0	Float last2OuterT = mLastOuterT;
170	0	Float last2InnerT = mLastInnerT;
171	0
172	0	(void)FindNext(mBestDashLength);
173	0
174	0	//
175	0	// outerT last2OuterT
176	0	// \| \|
177	0	// v v
178	0	// mLastOuterT -> +---+---+---+---+
179	0	// \| \|###\|###\| \|
180	0	// \| \|###\|###\| \|
181	0	// \| \|###\|###\| \|
182	0	// mLastInnerT -> +---+---+---+---+
183	0	// ^ ^
184	0	// \| \|
185	0	// innerT last2InnerT
186	0	outerT = (mLastOuterT + last2OuterT) / 2.0f;
187	0	innerT = (mLastInnerT + last2InnerT) / 2.0f;
188	0	}
189	0	}
190	0
191	0	mI++;
192	0
193	0	Bezier outerSectionBezier;
194	0	Bezier innerSectionBezier;
195	0	GetSubBezier(&outerSectionBezier, mOuterBezier, lastOuterT, outerT);
196	0	GetSubBezier(&innerSectionBezier, mInnerBezier, lastInnerT, innerT);
197	0	return DashedCornerFinder::Result(outerSectionBezier, innerSectionBezier);
198	0	}
199
200		void
201		DashedCornerFinder::Reset(void)
202	0	{
203	0	mLastOuterP = mOuterBezier.mPoints[0];
204	0	mLastInnerP = mInnerBezier.mPoints[0];
205	0	mLastOuterT = 0.0f;
206	0	mLastInnerT = 0.0f;
207	0	mHasMore = true;
208	0	}
209
210		Float
211		DashedCornerFinder::FindNext(Float dashLength)
212	0	{
213	0	Float upper = 1.0f;
214	0	Float lower = mLastOuterT;
215	0
216	0	Point OuterP, InnerP;
217	0	// Start from upper bound to check if this is the last segment.
218	0	Float outerT = upper;
219	0	Float innerT;
220	0	Float W = 0.0f;
221	0	Float L = 0.0f;
222	0
223	0	const Float LENGTH_MARGIN = 0.1f;
224	0	for (size_t i = 0; i < MAX_LOOP; i++) {
225	0	OuterP = GetBezierPoint(mOuterBezier, outerT);
226	0	InnerP = FindBezierNearestPoint(mInnerBezier, OuterP, outerT, &innerT);
227	0
228	0	// Calculate approximate dash length.
229	0	//
230	0	// W = (W1 + W2) / 2
231	0	// L = (OuterL + InnerL) / 2
232	0	// dashLength = L / W
233	0	//
234	0	// ____----+----____
235	0	// OuterP ___--- \| ---___ mLastOuterP
236	0	// +--- \| ---+
237	0	// \| \| \|
238	0	// \| \| \|
239	0	// \| W \| W1 \|
240	0	// \| \| \|
241	0	// W2 \| \| \|
242	0	// \| \| ______------+
243	0	// \| ____+---- mLastInnerP
244	0	// \| ___---
245	0	// \| __---
246	0	// +--
247	0	// InnerP
248	0	// OuterL
249	0	// ____---------____
250	0	// OuterP ___--- ---___ mLastOuterP
251	0	// +--- ---+
252	0	// \| L \|
253	0	// \| ___----------______ \|
254	0	// \| __--- -----+
255	0	// \| __-- \|
256	0	// +-- \|
257	0	// \| InnerL ______------+
258	0	// \| ____----- mLastInnerP
259	0	// \| ___---
260	0	// \| __---
261	0	// +--
262	0	// InnerP
263	0	Float W1 = (mLastOuterP - mLastInnerP).Length();
264	0	Float W2 = (OuterP - InnerP).Length();
265	0	Float OuterL = GetBezierLength(mOuterBezier, mLastOuterT, outerT);
266	0	Float InnerL = GetBezierLength(mInnerBezier, mLastInnerT, innerT);
267	0	W = (W1 + W2) / 2.0f;
268	0	L = (OuterL + InnerL) / 2.0f;
269	0	if (L > W * dashLength + LENGTH_MARGIN) {
270	0	if (i > 0) {
271	0	upper = outerT;
272	0	}
273	0	} else if (L < W * dashLength - LENGTH_MARGIN) {
274	0	if (i == 0) {
275	0	// This is the last segment with shorter dashLength.
276	0	mHasMore = false;
277	0	break;
278	0	}
279	0	lower = outerT;
280	0	} else {
281	0	break;
282	0	}
283	0
284	0	outerT = (upper + lower) / 2.0f;
285	0	}
286	0
287	0	mLastOuterP = OuterP;
288	0	mLastInnerP = InnerP;
289	0	mLastOuterT = outerT;
290	0	mLastInnerT = innerT;
291	0
292	0	if (W == 0.0f) {
293	0	return 1.0f;
294	0	}
295	0
296	0	return L / W;
297	0	}
298
299		void
300		DashedCornerFinder::FindBestDashLength(Float aMinBorderWidth,
301		Float aMaxBorderWidth,
302		Float aMinBorderRadius,
303		Float aMaxBorderRadius)
304	0	{
305	0	// If dashLength is not calculateable, find it with binary search,
306	0	// such that there exists i that OuterP_i == OuterP_n and
307	0	// InnerP_i == InnerP_n with given dashLength.
308	0
309	0	FourFloats key(
310	0	aMinBorderWidth, aMaxBorderWidth, aMinBorderRadius, aMaxBorderRadius);
311	0	BestDashLength best;
312	0	if (DashedCornerCache.Get(key, &best)) {
313	0	mCount = best.count;
314	0	mBestDashLength = best.dashLength;
315	0	return;
316	0	}
317	0
318	0	Float lower = 1.0f;
319	0	Float upper = DOT_LENGTH * DASH_LENGTH;
320	0	Float dashLength = upper;
321	0	size_t targetCount = 0;
322	0
323	0	const Float LENGTH_MARGIN = 0.1f;
324	0	for (size_t j = 0; j < MAX_LOOP; j++) {
325	0	size_t count;
326	0	Float actualDashLength;
327	0	if (!GetCountAndLastDashLength(dashLength, &count, &actualDashLength)) {
328	0	if (j == 0) {
329	0	mCount = mMaxCount;
330	0	break;
331	0	}
332	0	}
333	0
334	0	if (j == 0) {
335	0	if (count == 1) {
336	0	// If only 1 segment fits, fill entire region
337	0	//
338	0	// count = 1
339	0	// mCount = 1
340	0	// \| 1 \|
341	0	// +---+---+
342	0	// \|###\|###\|
343	0	// \|###\|###\|
344	0	// \|###\|###\|
345	0	// +---+---+
346	0	// 1
347	0	mCount = 1;
348	0	break;
349	0	}
350	0
351	0	// targetCount should be 2n.
352	0	//
353	0	// targetCount = 2
354	0	// mCount = 2
355	0	// \| 1 \| 2 \|
356	0	// +---+---+---+---+
357	0	// \|###\| \| \|###\|
358	0	// \|###\| \| \|###\|
359	0	// \|###\| \| \|###\|
360	0	// +---+---+---+---+
361	0	// 1 2
362	0	//
363	0	// targetCount = 6
364	0	// mCount = 4
365	0	// \| 1 \| 2 \| 3 \| 4 \| 5 \| 6 \|
366	0	// +---+---+---+---+---+---+---+---+---+---+---+---+
367	0	// \|###\| \| \|###\|###\| \| \|###\|###\| \| \|###\|
368	0	// \|###\| \| \|###\|###\| \| \|###\|###\| \| \|###\|
369	0	// \|###\| \| \|###\|###\| \| \|###\|###\| \| \|###\|
370	0	// +---+---+---+---+---+---+---+---+---+---+---+---+
371	0	// 1 2 3 4
372	0	if (count % 2) {
373	0	targetCount = count + 1;
374	0	} else {
375	0	targetCount = count;
376	0	}
377	0
378	0	mCount = targetCount / 2 + 1;
379	0	}
380	0
381	0	if (count == targetCount) {
382	0	mBestDashLength = dashLength;
383	0
384	0	// actualDashLength won't be greater than dashLength.
385	0	if (actualDashLength > dashLength - LENGTH_MARGIN) {
386	0	break;
387	0	}
388	0
389	0	// We started from upper bound, no need to update range when j == 0.
390	0	if (j > 0) {
391	0	upper = dashLength;
392	0	}
393	0	} else {
394	0	// \|j == 0 && count != targetCount\| means that \|targetCount = count + 1\|,
395	0	// and we started from upper bound, no need to update range when j == 0.
396	0	if (j > 0) {
397	0	if (count > targetCount) {
398	0	lower = dashLength;
399	0	} else {
400	0	upper = dashLength;
401	0	}
402	0	}
403	0	}
404	0
405	0	dashLength = (upper + lower) / 2.0f;
406	0	}
407	0
408	0	if (DashedCornerCache.Count() > DashedCornerCacheSize) {
409	0	DashedCornerCache.Clear();
410	0	}
411	0	DashedCornerCache.Put(key, BestDashLength(mBestDashLength, mCount));
412	0	}
413
414		bool
415		DashedCornerFinder::GetCountAndLastDashLength(Float aDashLength,
416		size_t* aCount,
417		Float* aActualDashLength)
418	0	{
419	0	// Return the number of segments and the last segment's dashLength for
420	0	// the given dashLength.
421	0
422	0	Reset();
423	0
424	0	for (size_t i = 0; i < mMaxCount; i++) {
425	0	Float actualDashLength = FindNext(aDashLength);
426	0	if (mLastOuterT >= 1.0f) {
427	0	*aCount = i + 1;
428	0	*aActualDashLength = actualDashLength;
429	0	return true;
430	0	}
431	0	}
432	0
433	0	return false;
434	0	}
435
436		} // namespace mozilla