Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(152)

Side by Side Diff: src/pathops/SkOpCoincidence.cpp

Issue 2426173002: fix fuzzers (Closed)
Patch Set: fix dm Created 4 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « src/pathops/SkOpCoincidence.h ('k') | src/pathops/SkOpSegment.cpp » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 /* 1 /*
2 * Copyright 2015 Google Inc. 2 * Copyright 2015 Google Inc.
3 * 3 *
4 * Use of this source code is governed by a BSD-style license that can be 4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file. 5 * found in the LICENSE file.
6 */ 6 */
7 #include "SkOpCoincidence.h" 7 #include "SkOpCoincidence.h"
8 #include "SkOpSegment.h" 8 #include "SkOpSegment.h"
9 #include "SkPathOpsTSect.h" 9 #include "SkPathOpsTSect.h"
10 10
(...skipping 110 matching lines...) Expand 10 before | Expand all | Expand 10 after
121 if (oppTs > oppTe) { 121 if (oppTs > oppTe) {
122 SkTSwap(oppTs, oppTe); 122 SkTSwap(oppTs, oppTe);
123 } 123 }
124 return oppTs <= s->fT && e->fT <= oppTe; 124 return oppTs <= s->fT && e->fT <= oppTe;
125 } 125 }
126 } 126 }
127 127
128 // A coincident span is unordered if the pairs of points in the main and opposit e curves' 128 // A coincident span is unordered if the pairs of points in the main and opposit e curves'
129 // t values do not ascend or descend. For instance, if a tightly arced quadratic is 129 // t values do not ascend or descend. For instance, if a tightly arced quadratic is
130 // coincident with another curve, it may intersect it out of order. 130 // coincident with another curve, it may intersect it out of order.
131 bool SkCoincidentSpans::ordered() const { 131 bool SkCoincidentSpans::ordered(bool* result) const {
132 const SkOpSpanBase* start = this->coinPtTStart()->span(); 132 const SkOpSpanBase* start = this->coinPtTStart()->span();
133 const SkOpSpanBase* end = this->coinPtTEnd()->span(); 133 const SkOpSpanBase* end = this->coinPtTEnd()->span();
134 const SkOpSpanBase* next = start->upCast()->next(); 134 const SkOpSpanBase* next = start->upCast()->next();
135 if (next == end) { 135 if (next == end) {
136 *result = true;
136 return true; 137 return true;
137 } 138 }
138 bool flipped = this->flipped(); 139 bool flipped = this->flipped();
139 const SkOpSegment* oppSeg = this->oppPtTStart()->segment(); 140 const SkOpSegment* oppSeg = this->oppPtTStart()->segment();
140 double oppLastT = fOppPtTStart->fT; 141 double oppLastT = fOppPtTStart->fT;
141 do { 142 do {
142 const SkOpPtT* opp = next->contains(oppSeg); 143 const SkOpPtT* opp = next->contains(oppSeg);
143 if (!opp) { 144 if (!opp) {
144 SkASSERT(0); // may assert if coincident span isn't fully processed 145 SkOPOBJASSERT(start, 0); // may assert if coincident span isn't ful ly processed
145 continue; 146 return false;
146 } 147 }
147 if ((oppLastT > opp->fT) != flipped) { 148 if ((oppLastT > opp->fT) != flipped) {
148 return false; 149 *result = false;
150 return true;
149 } 151 }
150 oppLastT = opp->fT; 152 oppLastT = opp->fT;
151 if (next == end) { 153 if (next == end) {
152 break; 154 break;
153 } 155 }
154 if (!next->upCastable()) { 156 if (!next->upCastable()) {
155 return false; 157 *result = false;
158 return true;
156 } 159 }
157 next = next->upCast()->next(); 160 next = next->upCast()->next();
158 } while (true); 161 } while (true);
162 *result = true;
159 return true; 163 return true;
160 } 164 }
161 165
162 // if there is an existing pair that overlaps the addition, extend it 166 // if there is an existing pair that overlaps the addition, extend it
163 bool SkOpCoincidence::extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtT End, 167 bool SkOpCoincidence::extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtT End,
164 const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) { 168 const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) {
165 SkCoincidentSpans* test = fHead; 169 SkCoincidentSpans* test = fHead;
166 if (!test) { 170 if (!test) {
167 return false; 171 return false;
168 } 172 }
(...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after
227 this->add(oppPtTEnd, oppPtTStart, coinPtTEnd, coinPtTStart); 231 this->add(oppPtTEnd, oppPtTStart, coinPtTEnd, coinPtTStart);
228 } 232 }
229 return; 233 return;
230 } 234 }
231 SkASSERT(Ordered(coinPtTStart, oppPtTStart)); 235 SkASSERT(Ordered(coinPtTStart, oppPtTStart));
232 // choose the ptT at the front of the list to track 236 // choose the ptT at the front of the list to track
233 coinPtTStart = coinPtTStart->span()->ptT(); 237 coinPtTStart = coinPtTStart->span()->ptT();
234 coinPtTEnd = coinPtTEnd->span()->ptT(); 238 coinPtTEnd = coinPtTEnd->span()->ptT();
235 oppPtTStart = oppPtTStart->span()->ptT(); 239 oppPtTStart = oppPtTStart->span()->ptT();
236 oppPtTEnd = oppPtTEnd->span()->ptT(); 240 oppPtTEnd = oppPtTEnd->span()->ptT();
237 SkASSERT(coinPtTStart->fT < coinPtTEnd->fT); 241 SkOPASSERT(coinPtTStart->fT < coinPtTEnd->fT);
238 SkASSERT(oppPtTStart->fT != oppPtTEnd->fT); 242 SkASSERT(oppPtTStart->fT != oppPtTEnd->fT);
239 SkOPASSERT(!coinPtTStart->deleted()); 243 SkOPASSERT(!coinPtTStart->deleted());
240 SkOPASSERT(!coinPtTEnd->deleted()); 244 SkOPASSERT(!coinPtTEnd->deleted());
241 SkOPASSERT(!oppPtTStart->deleted()); 245 SkOPASSERT(!oppPtTStart->deleted());
242 SkOPASSERT(!oppPtTEnd->deleted()); 246 SkOPASSERT(!oppPtTEnd->deleted());
243 DebugCheckAdd(fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd); 247 DebugCheckAdd(fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd);
244 DebugCheckAdd(fTop, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd); 248 DebugCheckAdd(fTop, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd);
245 SkCoincidentSpans* coinRec = SkOpTAllocator<SkCoincidentSpans>::Allocate( 249 SkCoincidentSpans* coinRec = SkOpTAllocator<SkCoincidentSpans>::Allocate(
246 this->globalState()->allocator()); 250 this->globalState()->allocator());
247 coinRec->init(SkDEBUGCODE(fGlobalState)); 251 coinRec->init(SkDEBUGCODE(fGlobalState));
(...skipping 499 matching lines...) Expand 10 before | Expand all | Expand 10 after
747 if (!outer) { 751 if (!outer) {
748 return true; 752 return true;
749 } 753 }
750 fTop = outer; 754 fTop = outer;
751 fHead = nullptr; 755 fHead = nullptr;
752 do { 756 do {
753 // addifmissing can modify the list that this is walking 757 // addifmissing can modify the list that this is walking
754 // save head so that walker can iterate over old data unperturbed 758 // save head so that walker can iterate over old data unperturbed
755 // addifmissing adds to head freely then add saved head in the end 759 // addifmissing adds to head freely then add saved head in the end
756 const SkOpPtT* ocs = outer->coinPtTStart(); 760 const SkOpPtT* ocs = outer->coinPtTStart();
757 SkASSERT(!ocs->deleted()); 761 FAIL_IF(ocs->deleted());
758 const SkOpSegment* outerCoin = ocs->segment(); 762 const SkOpSegment* outerCoin = ocs->segment();
759 SkASSERT(!outerCoin->done()); // if it's done, should have already been removed from list 763 SkASSERT(!outerCoin->done()); // if it's done, should have already been removed from list
760 const SkOpPtT* oos = outer->oppPtTStart(); 764 const SkOpPtT* oos = outer->oppPtTStart();
761 if (oos->deleted()) { 765 if (oos->deleted()) {
762 return true; 766 return true;
763 } 767 }
764 const SkOpSegment* outerOpp = oos->segment(); 768 const SkOpSegment* outerOpp = oos->segment();
765 SkASSERT(!outerOpp->done()); 769 SkASSERT(!outerOpp->done());
766 SkOpSegment* outerCoinWritable = const_cast<SkOpSegment*>(outerCoin); 770 SkOpSegment* outerCoinWritable = const_cast<SkOpSegment*>(outerCoin);
767 SkOpSegment* outerOppWritable = const_cast<SkOpSegment*>(outerOpp); 771 SkOpSegment* outerOppWritable = const_cast<SkOpSegment*>(outerOpp);
768 SkCoincidentSpans* inner = outer; 772 SkCoincidentSpans* inner = outer;
769 while ((inner = inner->next())) { 773 while ((inner = inner->next())) {
770 this->debugValidate(); 774 this->debugValidate();
771 double overS, overE; 775 double overS, overE;
772 const SkOpPtT* ics = inner->coinPtTStart(); 776 const SkOpPtT* ics = inner->coinPtTStart();
773 FAIL_IF(ics->deleted()); 777 FAIL_IF(ics->deleted());
774 const SkOpSegment* innerCoin = ics->segment(); 778 const SkOpSegment* innerCoin = ics->segment();
775 SkASSERT(!innerCoin->done()); 779 FAIL_IF(innerCoin->done());
776 const SkOpPtT* ios = inner->oppPtTStart(); 780 const SkOpPtT* ios = inner->oppPtTStart();
777 SkASSERT(!ios->deleted()); 781 FAIL_IF(ios->deleted());
778 const SkOpSegment* innerOpp = ios->segment(); 782 const SkOpSegment* innerOpp = ios->segment();
779 SkASSERT(!innerOpp->done()); 783 SkASSERT(!innerOpp->done());
780 SkOpSegment* innerCoinWritable = const_cast<SkOpSegment*>(innerCoin) ; 784 SkOpSegment* innerCoinWritable = const_cast<SkOpSegment*>(innerCoin) ;
781 SkOpSegment* innerOppWritable = const_cast<SkOpSegment*>(innerOpp); 785 SkOpSegment* innerOppWritable = const_cast<SkOpSegment*>(innerOpp);
782 if (outerCoin == innerCoin) { 786 if (outerCoin == innerCoin) {
783 const SkOpPtT* oce = outer->coinPtTEnd(); 787 const SkOpPtT* oce = outer->coinPtTEnd();
784 if (oce->deleted()) { 788 if (oce->deleted()) {
785 return true; 789 return true;
786 } 790 }
787 const SkOpPtT* ice = inner->coinPtTEnd(); 791 const SkOpPtT* ice = inner->coinPtTEnd();
(...skipping 60 matching lines...) Expand 10 before | Expand all | Expand 10 after
848 s1 = overS->find(seg1o); 852 s1 = overS->find(seg1o);
849 e1 = overE->find(seg1o); 853 e1 = overE->find(seg1o);
850 FAIL_IF(!s1); 854 FAIL_IF(!s1);
851 FAIL_IF(!e1); 855 FAIL_IF(!e1);
852 if (!s1->starter(e1)->span()->upCast()->windValue()) { 856 if (!s1->starter(e1)->span()->upCast()->windValue()) {
853 return true; 857 return true;
854 } 858 }
855 } 859 }
856 const SkOpPtT* s2 = overS->find(seg2); 860 const SkOpPtT* s2 = overS->find(seg2);
857 const SkOpPtT* e2 = overE->find(seg2); 861 const SkOpPtT* e2 = overE->find(seg2);
862 FAIL_IF(!e2);
858 if (!s2->starter(e2)->span()->upCast()->windValue()) { 863 if (!s2->starter(e2)->span()->upCast()->windValue()) {
859 s2 = overS->find(seg2o); 864 s2 = overS->find(seg2o);
860 e2 = overE->find(seg2o); 865 e2 = overE->find(seg2o);
866 FAIL_IF(!s2);
861 if (!s2->starter(e2)->span()->upCast()->windValue()) { 867 if (!s2->starter(e2)->span()->upCast()->windValue()) {
862 return true; 868 return true;
863 } 869 }
864 } 870 }
865 if (s1->segment() == s2->segment()) { 871 if (s1->segment() == s2->segment()) {
866 return true; 872 return true;
867 } 873 }
868 if (s1->fT > e1->fT) { 874 if (s1->fT > e1->fT) {
869 SkTSwap(s1, e1); 875 SkTSwap(s1, e1);
870 SkTSwap(s2, e2); 876 SkTSwap(s2, e2);
(...skipping 78 matching lines...) Expand 10 before | Expand all | Expand 10 after
949 SkCoincidentSpans* coin = fHead; 955 SkCoincidentSpans* coin = fHead;
950 if (!coin) { 956 if (!coin) {
951 return; 957 return;
952 } 958 }
953 do { 959 do {
954 coin->correctEnds(); 960 coin->correctEnds();
955 } while ((coin = coin->next())); 961 } while ((coin = coin->next()));
956 } 962 }
957 963
958 // walk span sets in parallel, moving winding from one to the other 964 // walk span sets in parallel, moving winding from one to the other
959 void SkOpCoincidence::apply(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 965 bool SkOpCoincidence::apply(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
960 DEBUG_SET_PHASE(); 966 DEBUG_SET_PHASE();
961 SkCoincidentSpans* coin = fHead; 967 SkCoincidentSpans* coin = fHead;
962 if (!coin) { 968 if (!coin) {
963 return; 969 return true;
964 } 970 }
965 do { 971 do {
966 SkOpSpan* start = coin->coinPtTStartWritable()->span()->upCast(); 972 SkOpSpan* start = coin->coinPtTStartWritable()->span()->upCast();
967 if (start->deleted()) { 973 if (start->deleted()) {
968 continue; 974 continue;
969 } 975 }
970 const SkOpSpanBase* end = coin->coinPtTEnd()->span(); 976 const SkOpSpanBase* end = coin->coinPtTEnd()->span();
971 SkASSERT(start == start->starter(end)); 977 SkASSERT(start == start->starter(end));
972 bool flipped = coin->flipped(); 978 bool flipped = coin->flipped();
973 SkOpSpan* oStart = (flipped ? coin->oppPtTEndWritable() 979 SkOpSpan* oStart = (flipped ? coin->oppPtTEndWritable()
(...skipping 74 matching lines...) Expand 10 before | Expand all | Expand 10 after
1048 windValue = oppValue = 0; 1054 windValue = oppValue = 0;
1049 } 1055 }
1050 #if 0 && DEBUG_COINCIDENCE 1056 #if 0 && DEBUG_COINCIDENCE
1051 SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", segment->debug ID(), 1057 SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", segment->debug ID(),
1052 start->debugID(), windValue, oppValue); 1058 start->debugID(), windValue, oppValue);
1053 SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", oSegment->debu gID(), 1059 SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", oSegment->debu gID(),
1054 oStart->debugID(), oWindValue, oOppValue); 1060 oStart->debugID(), oWindValue, oOppValue);
1055 #endif 1061 #endif
1056 start->setWindValue(windValue); 1062 start->setWindValue(windValue);
1057 start->setOppValue(oppValue); 1063 start->setOppValue(oppValue);
1064 FAIL_IF(oWindValue == -1);
1058 oStart->setWindValue(oWindValue); 1065 oStart->setWindValue(oWindValue);
1059 oStart->setOppValue(oOppValue); 1066 oStart->setOppValue(oOppValue);
1060 if (!windValue && !oppValue) { 1067 if (!windValue && !oppValue) {
1061 segment->markDone(start); 1068 segment->markDone(start);
1062 } 1069 }
1063 if (!oWindValue && !oOppValue) { 1070 if (!oWindValue && !oOppValue) {
1064 oSegment->markDone(oStart); 1071 oSegment->markDone(oStart);
1065 } 1072 }
1066 SkOpSpanBase* next = start->next(); 1073 SkOpSpanBase* next = start->next();
1067 SkOpSpanBase* oNext = flipped ? oStart->prev() : oStart->next(); 1074 SkOpSpanBase* oNext = flipped ? oStart->prev() : oStart->next();
1068 if (next == end) { 1075 if (next == end) {
1069 break; 1076 break;
1070 } 1077 }
1071 start = next->upCast(); 1078 start = next->upCast();
1072 // if the opposite ran out too soon, just reuse the last span 1079 // if the opposite ran out too soon, just reuse the last span
1073 if (!oNext || !oNext->upCastable()) { 1080 if (!oNext || !oNext->upCastable()) {
1074 oNext = oStart; 1081 oNext = oStart;
1075 } 1082 }
1076 oStart = oNext->upCast(); 1083 oStart = oNext->upCast();
1077 } while (true); 1084 } while (true);
1078 } while ((coin = coin->next())); 1085 } while ((coin = coin->next()));
1086 return true;
1079 } 1087 }
1080 1088
1081 // Please keep this in sync with debugRelease() 1089 // Please keep this in sync with debugRelease()
1082 bool SkOpCoincidence::release(SkCoincidentSpans* coin, SkCoincidentSpans* remove ) { 1090 bool SkOpCoincidence::release(SkCoincidentSpans* coin, SkCoincidentSpans* remove ) {
1083 SkCoincidentSpans* head = coin; 1091 SkCoincidentSpans* head = coin;
1084 SkCoincidentSpans* prev = nullptr; 1092 SkCoincidentSpans* prev = nullptr;
1085 SkCoincidentSpans* next; 1093 SkCoincidentSpans* next;
1086 do { 1094 do {
1087 next = coin->next(); 1095 next = coin->next();
1088 if (coin == remove) { 1096 if (coin == remove) {
(...skipping 176 matching lines...) Expand 10 before | Expand all | Expand 10 after
1265 bool SkOpCoincidence::mark(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 1273 bool SkOpCoincidence::mark(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
1266 DEBUG_SET_PHASE(); 1274 DEBUG_SET_PHASE();
1267 SkCoincidentSpans* coin = fHead; 1275 SkCoincidentSpans* coin = fHead;
1268 if (!coin) { 1276 if (!coin) {
1269 return true; 1277 return true;
1270 } 1278 }
1271 do { 1279 do {
1272 SkOpSpanBase* startBase = coin->coinPtTStartWritable()->span(); 1280 SkOpSpanBase* startBase = coin->coinPtTStartWritable()->span();
1273 FAIL_IF(!startBase->upCastable()); 1281 FAIL_IF(!startBase->upCastable());
1274 SkOpSpan* start = startBase->upCast(); 1282 SkOpSpan* start = startBase->upCast();
1275 SkASSERT(!start->deleted()); 1283 FAIL_IF(start->deleted());
1276 SkOpSpanBase* end = coin->coinPtTEndWritable()->span(); 1284 SkOpSpanBase* end = coin->coinPtTEndWritable()->span();
1277 SkOPASSERT(!end->deleted()); 1285 SkOPASSERT(!end->deleted());
1278 SkOpSpanBase* oStart = coin->oppPtTStartWritable()->span(); 1286 SkOpSpanBase* oStart = coin->oppPtTStartWritable()->span();
1279 SkOPASSERT(!oStart->deleted()); 1287 SkOPASSERT(!oStart->deleted());
1280 SkOpSpanBase* oEnd = coin->oppPtTEndWritable()->span(); 1288 SkOpSpanBase* oEnd = coin->oppPtTEndWritable()->span();
1281 SkASSERT(!oEnd->deleted()); 1289 SkASSERT(!oEnd->deleted());
1282 bool flipped = coin->flipped(); 1290 bool flipped = coin->flipped();
1283 if (flipped) { 1291 if (flipped) {
1284 SkTSwap(oStart, oEnd); 1292 SkTSwap(oStart, oEnd);
1285 } 1293 }
1286 /* coin and opp spans may not match up. Mark the ends, and then let the interior 1294 /* coin and opp spans may not match up. Mark the ends, and then let the interior
1287 get marked as many times as the spans allow */ 1295 get marked as many times as the spans allow */
1288 start->insertCoincidence(oStart->upCast()); 1296 start->insertCoincidence(oStart->upCast());
1289 end->insertCoinEnd(oEnd); 1297 end->insertCoinEnd(oEnd);
1290 const SkOpSegment* segment = start->segment(); 1298 const SkOpSegment* segment = start->segment();
1291 const SkOpSegment* oSegment = oStart->segment(); 1299 const SkOpSegment* oSegment = oStart->segment();
1292 SkOpSpanBase* next = start; 1300 SkOpSpanBase* next = start;
1293 SkOpSpanBase* oNext = oStart; 1301 SkOpSpanBase* oNext = oStart;
1294 bool ordered = coin->ordered(); 1302 bool ordered;
1303 FAIL_IF(!coin->ordered(&ordered));
1295 while ((next = next->upCast()->next()) != end) { 1304 while ((next = next->upCast()->next()) != end) {
1296 FAIL_IF(!next->upCastable()); 1305 FAIL_IF(!next->upCastable());
1297 SkAssertResult(next->upCast()->insertCoincidence(oSegment, flipped, ordered)); 1306 SkAssertResult(next->upCast()->insertCoincidence(oSegment, flipped, ordered));
1298 } 1307 }
1299 while ((oNext = oNext->upCast()->next()) != oEnd) { 1308 while ((oNext = oNext->upCast()->next()) != oEnd) {
1300 FAIL_IF(!oNext->upCast()->insertCoincidence(segment, flipped, ordere d)); 1309 FAIL_IF(!oNext->upCast()->insertCoincidence(segment, flipped, ordere d));
1301 } 1310 }
1302 } while ((coin = coin->next())); 1311 } while ((coin = coin->next()));
1303 return true; 1312 return true;
1304 } 1313 }
(...skipping 60 matching lines...) Expand 10 before | Expand all | Expand 10 after
1365 } 1374 }
1366 do { 1375 do {
1367 if (coin->coinPtTStart()->segment() == deleted 1376 if (coin->coinPtTStart()->segment() == deleted
1368 || coin->coinPtTEnd()->segment() == deleted 1377 || coin->coinPtTEnd()->segment() == deleted
1369 || coin->oppPtTStart()->segment() == deleted 1378 || coin->oppPtTStart()->segment() == deleted
1370 || coin->oppPtTEnd()->segment() == deleted) { 1379 || coin->oppPtTEnd()->segment() == deleted) {
1371 this->release(fHead, coin); 1380 this->release(fHead, coin);
1372 } 1381 }
1373 } while ((coin = coin->next())); 1382 } while ((coin = coin->next()));
1374 } 1383 }
OLDNEW
« no previous file with comments | « src/pathops/SkOpCoincidence.h ('k') | src/pathops/SkOpSegment.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698