The Tor Browser: comparison gfx/skia/trunk/src/effects/SkDashPathEffect.cpp

--1:000000000000
+:0c92b1d2c6d1
+/*
+* Copyright 2006 The Android Open Source Project
+*
+* Use of this source code is governed by a BSD-style license that can be
+* found in the LICENSE file.
+*/
+#include "SkDashPathEffect.h"
+#include "SkReadBuffer.h"
+#include "SkWriteBuffer.h"
+#include "SkPathMeasure.h"
+static inline int is_even(int x) {
+return (~x) << 31;
+}
+static SkScalar FindFirstInterval(const SkScalar intervals[], SkScalar phase,
+int32_t* index, int count) {
+for (int i = 0; i < count; ++i) {
+if (phase > intervals[i]) {
+phase -= intervals[i];
+} else {
+*index = i;
+return intervals[i] - phase;
+}
+}
+// If we get here, phase "appears" to be larger than our length. This
+// shouldn't happen with perfect precision, but we can accumulate errors
+// during the initial length computation (rounding can make our sum be too
+// big or too small. In that event, we just have to eat the error here.
+*index = 0;
+return intervals[0];
+}
+SkDashPathEffect::SkDashPathEffect(const SkScalar intervals[], int count,
+SkScalar phase, bool scaleToFit)
+: fScaleToFit(scaleToFit) {
+SkASSERT(intervals);
+SkASSERT(count > 1 && SkAlign2(count) == count);
+fIntervals = (SkScalar*)sk_malloc_throw(sizeof(SkScalar) * count);
+fCount = count;
+SkScalar len = 0;
+for (int i = 0; i < count; i++) {
+SkASSERT(intervals[i] >= 0);
+fIntervals[i] = intervals[i];
+len += intervals[i];
+}
+fIntervalLength = len;
+// watch out for values that might make us go out of bounds
+if ((len > 0) && SkScalarIsFinite(phase) && SkScalarIsFinite(len)) {
+// Adjust phase to be between 0 and len, "flipping" phase if negative.
+// e.g., if len is 100, then phase of -20 (or -120) is equivalent to 80
+if (phase < 0) {
+phase = -phase;
+if (phase > len) {
+phase = SkScalarMod(phase, len);
+}
+phase = len - phase;
+// Due to finite precision, it's possible that phase == len,
+// even after the subtract (if len >>> phase), so fix that here.
+// This fixes http://crbug.com/124652 .
+SkASSERT(phase <= len);
+if (phase == len) {
+phase = 0;
+}
+} else if (phase >= len) {
+phase = SkScalarMod(phase, len);
+}
+SkASSERT(phase >= 0 && phase < len);
+fInitialDashLength = FindFirstInterval(intervals, phase,
+&fInitialDashIndex, count);
+SkASSERT(fInitialDashLength >= 0);
+SkASSERT(fInitialDashIndex >= 0 && fInitialDashIndex < fCount);
+} else {
+fInitialDashLength = -1;    // signal bad dash intervals
+}
+}
+SkDashPathEffect::~SkDashPathEffect() {
+sk_free(fIntervals);
+}
+static void outset_for_stroke(SkRect* rect, const SkStrokeRec& rec) {
+SkScalar radius = SkScalarHalf(rec.getWidth());
+if (0 == radius) {
+radius = SK_Scalar1;    // hairlines
+}
+if (SkPaint::kMiter_Join == rec.getJoin()) {
+radius = SkScalarMul(radius, rec.getMiter());
+}
+rect->outset(radius, radius);
+}
+// Only handles lines for now. If returns true, dstPath is the new (smaller)
+// path. If returns false, then dstPath parameter is ignored.
+static bool cull_path(const SkPath& srcPath, const SkStrokeRec& rec,
+const SkRect* cullRect, SkScalar intervalLength,
+SkPath* dstPath) {
+if (NULL == cullRect) {
+return false;
+}
+SkPoint pts[2];
+if (!srcPath.isLine(pts)) {
+return false;
+}
+SkRect bounds = *cullRect;
+outset_for_stroke(&bounds, rec);
+SkScalar dx = pts[1].x() - pts[0].x();
+SkScalar dy = pts[1].y() - pts[0].y();
+// just do horizontal lines for now (lazy)
+if (dy) {
+return false;
+}
+SkScalar minX = pts[0].fX;
+SkScalar maxX = pts[1].fX;
+if (maxX < bounds.fLeft || minX > bounds.fRight) {
+return false;
+}
+if (dx < 0) {
+SkTSwap(minX, maxX);
+}
+// Now we actually perform the chop, removing the excess to the left and
+// right of the bounds (keeping our new line "in phase" with the dash,
+// hence the (mod intervalLength).
+if (minX < bounds.fLeft) {
+minX = bounds.fLeft - SkScalarMod(bounds.fLeft - minX,
+intervalLength);
+}
+if (maxX > bounds.fRight) {
+maxX = bounds.fRight + SkScalarMod(maxX - bounds.fRight,
+intervalLength);
+}
+SkASSERT(maxX >= minX);
+if (dx < 0) {
+SkTSwap(minX, maxX);
+}
+pts[0].fX = minX;
+pts[1].fX = maxX;
+dstPath->moveTo(pts[0]);
+dstPath->lineTo(pts[1]);
+return true;
+}
+class SpecialLineRec {
+public:
+bool init(const SkPath& src, SkPath* dst, SkStrokeRec* rec,
+int intervalCount, SkScalar intervalLength) {
+if (rec->isHairlineStyle() || !src.isLine(fPts)) {
+return false;
+}
+// can relax this in the future, if we handle square and round caps
+if (SkPaint::kButt_Cap != rec->getCap()) {
+return false;
+}
+SkScalar pathLength = SkPoint::Distance(fPts[0], fPts[1]);
+fTangent = fPts[1] - fPts[0];
+if (fTangent.isZero()) {
+return false;
+}
+fPathLength = pathLength;
+fTangent.scale(SkScalarInvert(pathLength));
+fTangent.rotateCCW(&fNormal);
+fNormal.scale(SkScalarHalf(rec->getWidth()));
+// now estimate how many quads will be added to the path
+//     resulting segments = pathLen * intervalCount / intervalLen
+//     resulting points = 4 * segments
+SkScalar ptCount = SkScalarMulDiv(pathLength,
+SkIntToScalar(intervalCount),
+intervalLength);
+int n = SkScalarCeilToInt(ptCount) << 2;
+dst->incReserve(n);
+// we will take care of the stroking
+rec->setFillStyle();
+return true;
+}
+void addSegment(SkScalar d0, SkScalar d1, SkPath* path) const {
+SkASSERT(d0 < fPathLength);
+// clamp the segment to our length
+if (d1 > fPathLength) {
+d1 = fPathLength;
+}
+SkScalar x0 = fPts[0].fX + SkScalarMul(fTangent.fX, d0);
+SkScalar x1 = fPts[0].fX + SkScalarMul(fTangent.fX, d1);
+SkScalar y0 = fPts[0].fY + SkScalarMul(fTangent.fY, d0);
+SkScalar y1 = fPts[0].fY + SkScalarMul(fTangent.fY, d1);
+SkPoint pts[4];
+pts[0].set(x0 + fNormal.fX, y0 + fNormal.fY);   // moveTo
+pts[1].set(x1 + fNormal.fX, y1 + fNormal.fY);   // lineTo
+pts[2].set(x1 - fNormal.fX, y1 - fNormal.fY);   // lineTo
+pts[3].set(x0 - fNormal.fX, y0 - fNormal.fY);   // lineTo
+path->addPoly(pts, SK_ARRAY_COUNT(pts), false);
+}
+private:
+SkPoint fPts[2];
+SkVector fTangent;
+SkVector fNormal;
+SkScalar fPathLength;
+};
+bool SkDashPathEffect::filterPath(SkPath* dst, const SkPath& src,
+SkStrokeRec* rec, const SkRect* cullRect) const {
+// we do nothing if the src wants to be filled, or if our dashlength is 0
+if (rec->isFillStyle() || fInitialDashLength < 0) {
+return false;
+}
+const SkScalar* intervals = fIntervals;
+SkScalar        dashCount = 0;
+int             segCount = 0;
+SkPath cullPathStorage;
+const SkPath* srcPtr = &src;
+if (cull_path(src, *rec, cullRect, fIntervalLength, &cullPathStorage)) {
+srcPtr = &cullPathStorage;
+}
+SpecialLineRec lineRec;
+bool specialLine = lineRec.init(*srcPtr, dst, rec, fCount >> 1, fIntervalLength);
+SkPathMeasure   meas(*srcPtr, false);
+do {
+bool        skipFirstSegment = meas.isClosed();
+bool        addedSegment = false;
+SkScalar    length = meas.getLength();
+int         index = fInitialDashIndex;
+SkScalar    scale = SK_Scalar1;
+// Since the path length / dash length ratio may be arbitrarily large, we can exert
+// significant memory pressure while attempting to build the filtered path. To avoid this,
+// we simply give up dashing beyond a certain threshold.
+//
+// The original bug report (http://crbug.com/165432) is based on a path yielding more than
+// 90 million dash segments and crashing the memory allocator. A limit of 1 million
+// segments seems reasonable: at 2 verbs per segment * 9 bytes per verb, this caps the
+// maximum dash memory overhead at roughly 17MB per path.
+static const SkScalar kMaxDashCount = 1000000;
+dashCount += length * (fCount >> 1) / fIntervalLength;
+if (dashCount > kMaxDashCount) {
+dst->reset();
+return false;
+}
+if (fScaleToFit) {
+if (fIntervalLength >= length) {
+scale = SkScalarDiv(length, fIntervalLength);
+} else {
+SkScalar div = SkScalarDiv(length, fIntervalLength);
+int n = SkScalarFloorToInt(div);
+scale = SkScalarDiv(length, n * fIntervalLength);
+}
+}
+// Using double precision to avoid looping indefinitely due to single precision rounding
+// (for extreme path_length/dash_length ratios). See test_infinite_dash() unittest.
+double  distance = 0;
+double  dlen = SkScalarMul(fInitialDashLength, scale);
+while (distance < length) {
+SkASSERT(dlen >= 0);
+addedSegment = false;
+if (is_even(index) && dlen > 0 && !skipFirstSegment) {
+addedSegment = true;
+++segCount;
+if (specialLine) {
+lineRec.addSegment(SkDoubleToScalar(distance),
+SkDoubleToScalar(distance + dlen),
+dst);
+} else {
+meas.getSegment(SkDoubleToScalar(distance),
+SkDoubleToScalar(distance + dlen),
+dst, true);
+}
+}
+distance += dlen;
+// clear this so we only respect it the first time around
+skipFirstSegment = false;
+// wrap around our intervals array if necessary
+index += 1;
+SkASSERT(index <= fCount);
+if (index == fCount) {
+index = 0;
+}
+// fetch our next dlen
+dlen = SkScalarMul(intervals[index], scale);
+}
+// extend if we ended on a segment and we need to join up with the (skipped) initial segment
+if (meas.isClosed() && is_even(fInitialDashIndex) &&
+fInitialDashLength > 0) {
+meas.getSegment(0, SkScalarMul(fInitialDashLength, scale), dst, !addedSegment);
+++segCount;
+}
+} while (meas.nextContour());
+if (segCount > 1) {
+dst->setConvexity(SkPath::kConcave_Convexity);
+}
+return true;
+}
+// Currently asPoints is more restrictive then it needs to be. In the future
+// we need to:
+//      allow kRound_Cap capping (could allow rotations in the matrix with this)
+//      allow paths to be returned
+bool SkDashPathEffect::asPoints(PointData* results,
+const SkPath& src,
+const SkStrokeRec& rec,
+const SkMatrix& matrix,
+const SkRect* cullRect) const {
+// width < 0 -> fill && width == 0 -> hairline so requiring width > 0 rules both out
+if (fInitialDashLength < 0 || 0 >= rec.getWidth()) {
+return false;
+}
+// TODO: this next test could be eased up. We could allow any number of
+// intervals as long as all the ons match and all the offs match.
+// Additionally, they do not necessarily need to be integers.
+// We cannot allow arbitrary intervals since we want the returned points
+// to be uniformly sized.
+if (fCount != 2 ||
+!SkScalarNearlyEqual(fIntervals[0], fIntervals[1]) ||
+!SkScalarIsInt(fIntervals[0]) ||
+!SkScalarIsInt(fIntervals[1])) {
+return false;
+}
+// TODO: this next test could be eased up. The rescaling should not impact
+// the equality of the ons & offs. However, we would need to remove the
+// integer intervals restriction first
+if (fScaleToFit) {
+return false;
+}
+SkPoint pts[2];
+if (!src.isLine(pts)) {
+return false;
+}
+// TODO: this test could be eased up to allow circles
+if (SkPaint::kButt_Cap != rec.getCap()) {
+return false;
+}
+// TODO: this test could be eased up for circles. Rotations could be allowed.
+if (!matrix.rectStaysRect()) {
+return false;
+}
+SkScalar        length = SkPoint::Distance(pts[1], pts[0]);
+SkVector tangent = pts[1] - pts[0];
+if (tangent.isZero()) {
+return false;
+}
+tangent.scale(SkScalarInvert(length));
+// TODO: make this test for horizontal & vertical lines more robust
+bool isXAxis = true;
+if (SK_Scalar1 == tangent.fX || -SK_Scalar1 == tangent.fX) {
+results->fSize.set(SkScalarHalf(fIntervals[0]), SkScalarHalf(rec.getWidth()));
+} else if (SK_Scalar1 == tangent.fY || -SK_Scalar1 == tangent.fY) {
+results->fSize.set(SkScalarHalf(rec.getWidth()), SkScalarHalf(fIntervals[0]));
+isXAxis = false;
+} else if (SkPaint::kRound_Cap != rec.getCap()) {
+// Angled lines don't have axis-aligned boxes.
+return false;
+}
+if (NULL != results) {
+results->fFlags = 0;
+SkScalar clampedInitialDashLength = SkMinScalar(length, fInitialDashLength);
+if (SkPaint::kRound_Cap == rec.getCap()) {
+results->fFlags |= PointData::kCircles_PointFlag;
+}
+results->fNumPoints = 0;
+SkScalar len2 = length;
+if (clampedInitialDashLength > 0 || 0 == fInitialDashIndex) {
+SkASSERT(len2 >= clampedInitialDashLength);
+if (0 == fInitialDashIndex) {
+if (clampedInitialDashLength > 0) {
+if (clampedInitialDashLength >= fIntervals[0]) {
+++results->fNumPoints;  // partial first dash
+}
+len2 -= clampedInitialDashLength;
+}
+len2 -= fIntervals[1];  // also skip first space
+if (len2 < 0) {
+len2 = 0;
+}
+} else {
+len2 -= clampedInitialDashLength; // skip initial partial empty
+}
+}
+int numMidPoints = SkScalarFloorToInt(SkScalarDiv(len2, fIntervalLength));
+results->fNumPoints += numMidPoints;
+len2 -= numMidPoints * fIntervalLength;
+bool partialLast = false;
+if (len2 > 0) {
+if (len2 < fIntervals[0]) {
+partialLast = true;
+} else {
+++numMidPoints;
+++results->fNumPoints;
+}
+}
+results->fPoints = new SkPoint[results->fNumPoints];
+SkScalar    distance = 0;
+int         curPt = 0;
+if (clampedInitialDashLength > 0 || 0 == fInitialDashIndex) {
+SkASSERT(clampedInitialDashLength <= length);
+if (0 == fInitialDashIndex) {
+if (clampedInitialDashLength > 0) {
+// partial first block
+SkASSERT(SkPaint::kRound_Cap != rec.getCap()); // can't handle partial circles
+SkScalar x = pts[0].fX + SkScalarMul(tangent.fX, SkScalarHalf(clampedInitialDashLength));
+SkScalar y = pts[0].fY + SkScalarMul(tangent.fY, SkScalarHalf(clampedInitialDashLength));
+SkScalar halfWidth, halfHeight;
+if (isXAxis) {
+halfWidth = SkScalarHalf(clampedInitialDashLength);
+halfHeight = SkScalarHalf(rec.getWidth());
+} else {
+halfWidth = SkScalarHalf(rec.getWidth());
+halfHeight = SkScalarHalf(clampedInitialDashLength);
+}
+if (clampedInitialDashLength < fIntervals[0]) {
+// This one will not be like the others
+results->fFirst.addRect(x - halfWidth, y - halfHeight,
+x + halfWidth, y + halfHeight);
+} else {
+SkASSERT(curPt < results->fNumPoints);
+results->fPoints[curPt].set(x, y);
+++curPt;
+}
+distance += clampedInitialDashLength;
+}
+distance += fIntervals[1];  // skip over the next blank block too
+} else {
+distance += clampedInitialDashLength;
+}
+}
+if (0 != numMidPoints) {
+distance += SkScalarHalf(fIntervals[0]);
+for (int i = 0; i < numMidPoints; ++i) {
+SkScalar x = pts[0].fX + SkScalarMul(tangent.fX, distance);
+SkScalar y = pts[0].fY + SkScalarMul(tangent.fY, distance);
+SkASSERT(curPt < results->fNumPoints);
+results->fPoints[curPt].set(x, y);
+++curPt;
+distance += fIntervalLength;
+}
+distance -= SkScalarHalf(fIntervals[0]);
+}
+if (partialLast) {
+// partial final block
+SkASSERT(SkPaint::kRound_Cap != rec.getCap()); // can't handle partial circles
+SkScalar temp = length - distance;
+SkASSERT(temp < fIntervals[0]);
+SkScalar x = pts[0].fX + SkScalarMul(tangent.fX, distance + SkScalarHalf(temp));
+SkScalar y = pts[0].fY + SkScalarMul(tangent.fY, distance + SkScalarHalf(temp));
+SkScalar halfWidth, halfHeight;
+if (isXAxis) {
+halfWidth = SkScalarHalf(temp);
+halfHeight = SkScalarHalf(rec.getWidth());
+} else {
+halfWidth = SkScalarHalf(rec.getWidth());
+halfHeight = SkScalarHalf(temp);
+}
+results->fLast.addRect(x - halfWidth, y - halfHeight,
+x + halfWidth, y + halfHeight);
+}
+SkASSERT(curPt == results->fNumPoints);
+}
+return true;
+}
+SkFlattenable::Factory SkDashPathEffect::getFactory() const {
+return CreateProc;
+}
+void SkDashPathEffect::flatten(SkWriteBuffer& buffer) const {
+this->INHERITED::flatten(buffer);
+buffer.writeInt(fInitialDashIndex);
+buffer.writeScalar(fInitialDashLength);
+buffer.writeScalar(fIntervalLength);
+buffer.writeBool(fScaleToFit);
+buffer.writeScalarArray(fIntervals, fCount);
+}
+SkFlattenable* SkDashPathEffect::CreateProc(SkReadBuffer& buffer) {
+return SkNEW_ARGS(SkDashPathEffect, (buffer));
+}
+SkDashPathEffect::SkDashPathEffect(SkReadBuffer& buffer) : INHERITED(buffer) {
+fInitialDashIndex = buffer.readInt();
+fInitialDashLength = buffer.readScalar();
+fIntervalLength = buffer.readScalar();
+fScaleToFit = buffer.readBool();
+fCount = buffer.getArrayCount();
+size_t allocSize = sizeof(SkScalar) * fCount;
+if (buffer.validateAvailable(allocSize)) {
+fIntervals = (SkScalar*)sk_malloc_throw(allocSize);
+buffer.readScalarArray(fIntervals, fCount);
+} else {
+fIntervals = NULL;
+}
+}

The Tor Browser / file comparison

comparison: gfx/skia/trunk/src/effects/SkDashPathEffect.cpp

gfx/skia/trunk/src/effects/SkDashPathEffect.cpp