The Tor Browser / file revision

gfx/skia/trunk/src/pathops/SkOpSegment.h@129ffea94266

gfx/skia/trunk/src/pathops/SkOpSegment.h

Sat, 03 Jan 2015 20:18:00 +0100

author
Michael Schloh von Bennewitz <michael@schloh.com>
date
Sat, 03 Jan 2015 20:18:00 +0100
branch
TOR_BUG_3246
changeset 7
129ffea94266
permissions
-rw-r--r--

Conditionally enable double key logic according to:
private browsing mode or privacy.thirdparty.isolate preference and
implement in GetCookieStringCommon and FindCookie where it counts...
With some reservations of how to convince FindCookie users to test
condition and pass a nullptr when disabling double key logic.

     1 /*

     2  * Copyright 2012 Google Inc.

     3  *

     4  * Use of this source code is governed by a BSD-style license that can be

     5  * found in the LICENSE file.

     6  */

     7 #ifndef SkOpSegment_DEFINE

     8 #define SkOpSegment_DEFINE

     9 

    10 #include "SkOpAngle.h"

    11 #include "SkOpSpan.h"

    12 #include "SkPathOpsBounds.h"

    13 #include "SkPathOpsCurve.h"

    14 #include "SkTArray.h"

    15 #include "SkTDArray.h"

    16 

    17 class SkPathWriter;

    18 

    19 class SkOpSegment {

    20 public:

    21     SkOpSegment() {

    22 #ifdef SK_DEBUG

    23         fID = ++SkPathOpsDebug::gSegmentID;

    24 #endif

    25     }

    26 

    27     bool operator<(const SkOpSegment& rh) const {

    28         return fBounds.fTop < rh.fBounds.fTop;

    29     }

    30 

    31     const SkPathOpsBounds& bounds() const {

    32         return fBounds;

    33     }

    34 

    35     // OPTIMIZE

    36     // when the edges are initially walked, they don't automatically get the prior and next

    37     // edges assigned to positions t=0 and t=1. Doing that would remove the need for this check,

    38     // and would additionally remove the need for similar checks in condition edges. It would

    39     // also allow intersection code to assume end of segment intersections (maybe?)

    40     bool complete() const {

    41         int count = fTs.count();

    42         return count > 1 && fTs[0].fT == 0 && fTs[--count].fT == 1;

    43     }

    44 

    45     int count() const {

    46         return fTs.count();

    47     }

    48 

    49     bool done() const {

    50         SkASSERT(fDoneSpans <= fTs.count());

    51         return fDoneSpans == fTs.count();

    52     }

    53 

    54     bool done(int min) const {

    55         return fTs[min].fDone;

    56     }

    57 

    58     bool done(const SkOpAngle* angle) const {

    59         return done(SkMin32(angle->start(), angle->end()));

    60     }

    61 

    62     // used only by partial coincidence detection

    63     SkDPoint dPtAtT(double mid) const {

    64         return (*CurveDPointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid);

    65     }

    66 

    67     SkVector dxdy(int index) const {

    68         return (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, fTs[index].fT);

    69     }

    70 

    71     SkScalar dy(int index) const {

    72         return dxdy(index).fY;

    73     }

    74 

    75     bool intersected() const {

    76         return fTs.count() > 0;

    77     }

    78 

    79     bool isCanceled(int tIndex) const {

    80         return fTs[tIndex].fWindValue == 0 && fTs[tIndex].fOppValue == 0;

    81     }

    82 

    83     bool isConnected(int startIndex, int endIndex) const {

    84         return fTs[startIndex].fWindSum != SK_MinS32 || fTs[endIndex].fWindSum != SK_MinS32;

    85     }

    86 

    87     bool isHorizontal() const {

    88         return fBounds.fTop == fBounds.fBottom;

    89     }

    90 

    91     bool isVertical() const {

    92         return fBounds.fLeft == fBounds.fRight;

    93     }

    94 

    95     bool isVertical(int start, int end) const {

    96         return (*CurveIsVertical[SkPathOpsVerbToPoints(fVerb)])(fPts, start, end);

    97     }

    98 

    99     bool operand() const {

   100         return fOperand;

   101     }

   102 

   103     int oppSign(const SkOpAngle* angle) const {

   104         SkASSERT(angle->segment() == this);

   105         return oppSign(angle->start(), angle->end());

   106     }

   107 

   108     int oppSign(int startIndex, int endIndex) const {

   109         int result = startIndex < endIndex ? -fTs[startIndex].fOppValue : fTs[endIndex].fOppValue;

   110 #if DEBUG_WIND_BUMP

   111         SkDebugf("%s oppSign=%d\n", __FUNCTION__, result);

   112 #endif

   113         return result;

   114     }

   115 

   116     int oppSum(int tIndex) const {

   117         return fTs[tIndex].fOppSum;

   118     }

   119 

   120     int oppSum(const SkOpAngle* angle) const {

   121         int lesser = SkMin32(angle->start(), angle->end());

   122         return fTs[lesser].fOppSum;

   123     }

   124 

   125     int oppValue(int tIndex) const {

   126         return fTs[tIndex].fOppValue;

   127     }

   128 

   129     int oppValue(const SkOpAngle* angle) const {

   130         int lesser = SkMin32(angle->start(), angle->end());

   131         return fTs[lesser].fOppValue;

   132     }

   133 

   134     const SkOpSegment* other(int index) const {

   135         return fTs[index].fOther;

   136     }

   137 

   138     // was used only by right angle winding finding

   139     SkPoint ptAtT(double mid) const {

   140         return (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid);

   141     }

   142 

   143     const SkPoint* pts() const {

   144         return fPts;

   145     }

   146 

   147     void reset() {

   148         init(NULL, (SkPath::Verb) -1, false, false);

   149         fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);

   150         fTs.reset();

   151     }

   152 

   153     void setOppXor(bool isOppXor) {

   154         fOppXor = isOppXor;

   155     }

   156 

   157     void setUpWinding(int index, int endIndex, int* maxWinding, int* sumWinding) {

   158         int deltaSum = spanSign(index, endIndex);

   159         *maxWinding = *sumWinding;

   160         *sumWinding -= deltaSum;

   161     }

   162 

   163     // OPTIMIZATION: mark as debugging only if used solely by tests

   164     const SkOpSpan& span(int tIndex) const {

   165         return fTs[tIndex];

   166     }

   167 

   168     // OPTIMIZATION: mark as debugging only if used solely by tests

   169     const SkTDArray<SkOpSpan>& spans() const {

   170         return fTs;

   171     }

   172 

   173     int spanSign(const SkOpAngle* angle) const {

   174         SkASSERT(angle->segment() == this);

   175         return spanSign(angle->start(), angle->end());

   176     }

   177 

   178     int spanSign(int startIndex, int endIndex) const {

   179         int result = startIndex < endIndex ? -fTs[startIndex].fWindValue : fTs[endIndex].fWindValue;

   180 #if DEBUG_WIND_BUMP

   181         SkDebugf("%s spanSign=%d\n", __FUNCTION__, result);

   182 #endif

   183         return result;

   184     }

   185 

   186     double t(int tIndex) const {

   187         return fTs[tIndex].fT;

   188     }

   189 

   190     double tAtMid(int start, int end, double mid) const {

   191         return fTs[start].fT * (1 - mid) + fTs[end].fT * mid;

   192     }

   193 

   194     bool unsortable(int index) const {

   195         return fTs[index].fUnsortableStart || fTs[index].fUnsortableEnd;

   196     }

   197 

   198     void updatePts(const SkPoint pts[]) {

   199         fPts = pts;

   200     }

   201 

   202     SkPath::Verb verb() const {

   203         return fVerb;

   204     }

   205 

   206     int windSum(int tIndex) const {

   207         return fTs[tIndex].fWindSum;

   208     }

   209 

   210     int windValue(int tIndex) const {

   211         return fTs[tIndex].fWindValue;

   212     }

   213 

   214 #if defined(SK_DEBUG) || DEBUG_WINDING

   215     SkScalar xAtT(int index) const {

   216         return xAtT(&fTs[index]);

   217     }

   218 #endif

   219 

   220     const SkPoint& xyAtT(const SkOpSpan* span) const {

   221         return span->fPt;

   222     }

   223 

   224     const SkPoint& xyAtT(int index) const {

   225         return xyAtT(&fTs[index]);

   226     }

   227 

   228 #if defined(SK_DEBUG) || DEBUG_WINDING

   229     SkScalar yAtT(int index) const {

   230         return yAtT(&fTs[index]);

   231     }

   232 #endif

   233 

   234     bool activeAngle(int index, int* done, SkTArray<SkOpAngle, true>* angles);

   235     SkPoint activeLeftTop(bool onlySortable, int* firstT) const;

   236     bool activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, SkPathOp op);

   237     bool activeWinding(int index, int endIndex);

   238     void addCubic(const SkPoint pts[4], bool operand, bool evenOdd);

   239     void addCurveTo(int start, int end, SkPathWriter* path, bool active) const;

   240     void addLine(const SkPoint pts[2], bool operand, bool evenOdd);

   241     void addOtherT(int index, double otherT, int otherIndex);

   242     void addQuad(const SkPoint pts[3], bool operand, bool evenOdd);

   243     int addSelfT(SkOpSegment* other, const SkPoint& pt, double newT);

   244     int addT(SkOpSegment* other, const SkPoint& pt, double newT);

   245     void addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);

   246     void addTCoincident(const SkPoint& startPt, const SkPoint& endPt, double endT,

   247             SkOpSegment* other);

   248     void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt);

   249     bool betweenTs(int lesser, double testT, int greater) const;

   250     void checkEnds();

   251     bool checkSmall(int index) const;

   252     void checkTiny();

   253     int computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType,

   254                     SkTArray<SkOpAngle, true>* angles, SkTArray<SkOpAngle*, true>* sorted);

   255     int crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT, bool* hitSomething,

   256                      double mid, bool opp, bool current) const;

   257     bool findCoincidentMatch(const SkOpSpan* span, const SkOpSegment* other, int oStart, int oEnd,

   258                              int step, SkPoint* startPt, SkPoint* endPt, double* endT) const;

   259     SkOpSegment* findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,

   260                             bool* unsortable, SkPathOp op, const int xorMiMask,

   261                             const int xorSuMask);

   262     SkOpSegment* findNextWinding(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,

   263                                  bool* unsortable);

   264     SkOpSegment* findNextXor(int* nextStart, int* nextEnd, bool* unsortable);

   265     int findT(double t, const SkOpSegment* ) const;

   266     SkOpSegment* findTop(int* tIndex, int* endIndex, bool* unsortable, bool onlySortable);

   267     void fixOtherTIndex();

   268     void initWinding(int start, int end);

   269     void initWinding(int start, int end, double tHit, int winding, SkScalar hitDx, int oppWind,

   270                      SkScalar hitOppDx);

   271     bool isMissing(double startT, const SkPoint& pt) const;

   272     bool isTiny(const SkOpAngle* angle) const;

   273     bool joinCoincidence(SkOpSegment* other, double otherT, int step, bool cancel);

   274     SkOpSpan* markAndChaseDoneBinary(int index, int endIndex);

   275     SkOpSpan* markAndChaseDoneUnary(int index, int endIndex);

   276     SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding);

   277     SkOpSpan* markAngle(int maxWinding, int sumWinding, int oppMaxWinding, int oppSumWinding,

   278                         const SkOpAngle* angle);

   279     void markDone(int index, int winding);

   280     void markDoneBinary(int index);

   281     void markDoneUnary(int index);

   282     bool nextCandidate(int* start, int* end) const;

   283     int nextSpan(int from, int step) const;

   284     void setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding,

   285             int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding);

   286     enum SortAngleKind {

   287         kMustBeOrdered_SortAngleKind, // required for winding calc

   288         kMayBeUnordered_SortAngleKind // ok for find top

   289     };

   290     static bool SortAngles(const SkTArray<SkOpAngle, true>& angles,  // FIXME: replace with

   291                            SkTArray<SkOpAngle*, true>* angleList,    //  Sort Angles 2

   292                            SortAngleKind );

   293     static bool SortAngles2(const SkTArray<SkOpAngle, true>& angles,

   294                             SkTArray<SkOpAngle*, true>* angleList);

   295     bool subDivide(int start, int end, SkPoint edge[4]) const;

   296     bool subDivide(int start, int end, SkDCubic* result) const;

   297     void undoneSpan(int* start, int* end);

   298     int updateOppWindingReverse(const SkOpAngle* angle) const;

   299     int updateWindingReverse(const SkOpAngle* angle) const;

   300     static bool UseInnerWinding(int outerWinding, int innerWinding);

   301     int windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx) const;

   302     int windSum(const SkOpAngle* angle) const;

   303 

   304 #ifdef SK_DEBUG

   305     int debugID() const {

   306         return fID;

   307     }

   308 #endif

   309 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY

   310     void debugShowActiveSpans() const;

   311 #endif

   312 #if DEBUG_SORT || DEBUG_SWAP_TOP

   313     void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first,

   314             const int contourWinding, const int oppContourWinding, bool sortable) const;

   315     void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first,

   316             bool sortable);

   317 #endif

   318 #if DEBUG_CONCIDENT

   319     void debugShowTs(const char* prefix) const;

   320 #endif

   321 #if DEBUG_SHOW_WINDING

   322     int debugShowWindingValues(int slotCount, int ofInterest) const;

   323 #endif

   324 

   325 private:

   326     struct MissingSpan  {

   327         double fT;

   328         double fEndT;

   329         SkOpSegment* fSegment;

   330         SkOpSegment* fOther;

   331         double fOtherT;

   332         SkPoint fPt;

   333     };

   334 

   335     bool activeAngleOther(int index, int* done, SkTArray<SkOpAngle, true>* angles);

   336     bool activeAngleInner(int index, int* done, SkTArray<SkOpAngle, true>* angles);

   337     bool activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op,

   338                   int* sumMiWinding, int* sumSuWinding, int* maxWinding, int* sumWinding,

   339                   int* oppMaxWinding, int* oppSumWinding);

   340     bool activeWinding(int index, int endIndex, int* maxWinding, int* sumWinding);

   341     void addAngle(SkTArray<SkOpAngle, true>* angles, int start, int end) const;

   342     void addCancelOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);

   343     void addCoinOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);

   344     void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt,

   345                   const SkPoint& oPt);

   346     void addTwoAngles(int start, int end, SkTArray<SkOpAngle, true>* angles) const;

   347     bool betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const;

   348     bool buildAngles(int index, SkTArray<SkOpAngle, true>* angles, bool includeOpp) const;

   349     void buildAnglesInner(int index, SkTArray<SkOpAngle, true>* angles) const;

   350     void bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* index,

   351                            SkTArray<SkPoint, true>* outsideTs);

   352     void bumpCoincidentOther(const SkOpSpan& oTest, int* index,

   353                            SkTArray<SkPoint, true>* outsideTs);

   354     bool bumpSpan(SkOpSpan* span, int windDelta, int oppDelta);

   355     bool clockwise(int tStart, int tEnd) const;

   356     static void ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,

   357                               SkOpAngle::IncludeType );

   358     static void ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,

   359                                      SkOpAngle::IncludeType );

   360     bool decrementSpan(SkOpSpan* span);

   361     int findStartingEdge(const SkTArray<SkOpAngle*, true>& sorted, int start, int end);

   362     void init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd);

   363     bool isSimple(int end) const;

   364     bool isTiny(int index) const;

   365     void matchWindingValue(int tIndex, double t, bool borrowWind);

   366     SkOpSpan* markAndChaseDone(int index, int endIndex, int winding);

   367     SkOpSpan* markAndChaseDoneBinary(const SkOpAngle* angle, int winding, int oppWinding);

   368     SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, const int winding);

   369     SkOpSpan* markAndChaseWinding(int index, int endIndex, int winding, int oppWinding);

   370     SkOpSpan* markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle);

   371     void markDoneBinary(int index, int winding, int oppWinding);

   372     SkOpSpan* markAndChaseDoneUnary(const SkOpAngle* angle, int winding);

   373     void markOneDone(const char* funName, int tIndex, int winding);

   374     void markOneDoneBinary(const char* funName, int tIndex);

   375     void markOneDoneBinary(const char* funName, int tIndex, int winding, int oppWinding);

   376     void markOneDoneUnary(const char* funName, int tIndex);

   377     SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding);

   378     SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding, int oppWinding);

   379     void markWinding(int index, int winding);

   380     void markWinding(int index, int winding, int oppWinding);

   381     void markUnsortable(int start, int end);

   382     bool monotonicInY(int tStart, int tEnd) const;

   383     bool multipleSpans(int end) const;

   384     SkOpSegment* nextChase(int* index, const int step, int* min, SkOpSpan** last);

   385     int nextExactSpan(int from, int step) const;

   386     bool serpentine(int tStart, int tEnd) const;

   387     void setUpWindings(int index, int endIndex, int* sumMiWinding,

   388             int* maxWinding, int* sumWinding);

   389     void subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const;

   390     static void TrackOutsidePair(SkTArray<SkPoint, true>* outsideTs, const SkPoint& endPt,

   391             const SkPoint& startPt);

   392     static void TrackOutside(SkTArray<SkPoint, true>* outsideTs, const SkPoint& startPt);

   393     int updateOppWinding(int index, int endIndex) const;

   394     int updateOppWinding(const SkOpAngle* angle) const;

   395     int updateWinding(int index, int endIndex) const;

   396     int updateWinding(const SkOpAngle* angle) const;

   397     int updateWindingReverse(int index, int endIndex) const;

   398     static bool UseInnerWindingReverse(int outerWinding, int innerWinding);

   399     SkOpSpan* verifyOneWinding(const char* funName, int tIndex);

   400     SkOpSpan* verifyOneWindingU(const char* funName, int tIndex);

   401 

   402     SkScalar xAtT(const SkOpSpan* span) const {

   403         return xyAtT(span).fX;

   404     }

   405 

   406     SkScalar yAtT(const SkOpSpan* span) const {

   407         return xyAtT(span).fY;

   408     }

   409 

   410     void zeroSpan(SkOpSpan* span);

   411 

   412 #if DEBUG_SWAP_TOP

   413     bool controlsContainedByEnds(int tStart, int tEnd) const;

   414 #endif

   415 #if DEBUG_CONCIDENT

   416      void debugAddTPair(double t, const SkOpSegment& other, double otherT) const;

   417 #endif

   418 #if DEBUG_MARK_DONE || DEBUG_UNSORTABLE

   419     void debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding);

   420     void debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding, int oppWinding);

   421 #endif

   422 #if DEBUG_WINDING

   423     static char as_digit(int value) {

   424         return value < 0 ? '?' : value <= 9 ? '0' + value : '+';

   425     }

   426 #endif

   427     void debugValidate() const;

   428 #ifdef SK_DEBUG

   429     void dumpPts() const;

   430     void dumpDPts() const;

   431     void dumpSpans() const;

   432 #endif

   433 

   434     const SkPoint* fPts;

   435     SkPathOpsBounds fBounds;

   436     // FIXME: can't convert to SkTArray because it uses insert

   437     SkTDArray<SkOpSpan> fTs;  // two or more (always includes t=0 t=1)

   438     // OPTIMIZATION: could pack donespans, verb, operand, xor into 1 int-sized value

   439     int fDoneSpans;  // quick check that segment is finished

   440     // OPTIMIZATION: force the following to be byte-sized

   441     SkPath::Verb fVerb;

   442     bool fOperand;

   443     bool fXor;  // set if original contour had even-odd fill

   444     bool fOppXor;  // set if opposite operand had even-odd fill

   445 #ifdef SK_DEBUG

   446     int fID;

   447 #endif

   448 };

   449 

   450 #endif

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial