aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/pathops
Commit message (Collapse)AuthorAge
...
* add pathops debuggingGravatar caryclark2016-08-25
| | | | | | | | | | | | | | | | | | | Pathops has many points of failure, most of which are triggered by extreme data generated by fuzzers. It's difficult to figure out which failure point was triggered when the operation gives up. Add instrumentation so that the failure can be debugged when the data is well-behaved. Also, add a check that looks for a sequence of coincident points on multiple edges that are out of order when compared to each other. TBR=reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2274803003 Review-Url: https://codereview.chromium.org/2274803003
* remove point aliasesGravatar caryclark2016-08-24
| | | | | | | | | | | | | | | | This removes the notion of keeping track of every different t value that resolves to the same or a similar point. Other fixes make this concept unnecessary, and removing it simplifies the code. This removes an allocation, and speeds up paths with many overlapping curves. As a bonus, four fuzzer tests that failed before now succeed. TBR=reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2275703003 Review-Url: https://codereview.chromium.org/2275703003
* fix pathops fuzzGravatar caryclark2016-08-23
| | | | | | | | | | | Extreme cubics may split so that one half is a point. Discard this rather than generating a degenerate line. TBR=reed@google.com BUG=640025 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2276503002 Review-Url: https://codereview.chromium.org/2276503002
* fix fuzzesGravatar caryclark2016-08-19
| | | | | | | | TBR=reed@google.com BUG=639157, 638783 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2255243003 Review-Url: https://codereview.chromium.org/2255243003
* fix fuzzGravatar caryclark2016-08-17
| | | | | | | | TBR=reed@google.com BUG=638496 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2250413002 Review-Url: https://codereview.chromium.org/2250413002
* fix fuzz bugGravatar caryclark2016-08-16
| | | | | | | | TBR=reed@google.com BUG=637968, 638002 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2250573003 Review-Url: https://codereview.chromium.org/2250573003
* start working on tiger againGravatar caryclark2016-08-11
| | | | | | | | | | | | | | | The tiger tests are a suite under development that exercise many coincident edge cases. This fixes the case when a duplicate point is not ignored when the coincident span references the primary point. TBR=reed@google.com BUG=skia:5131 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2239803002 Review-Url: https://codereview.chromium.org/2239803002
* Fix SkDEBUGCODE to accept commasGravatar csmartdalton2016-08-10
| | | | | | | BUG=skia: GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2231663002 Review-Url: https://codereview.chromium.org/2231663002
* template intersection fuzz fixesGravatar caryclark2016-08-08
| | | | | | | | | | | | | Plumb in the ability to ignore asserts for out of range input deeper into the template intersection code. Exit gracefully when error conditions are found. TBR=reed@google.com BUG=632607,632628,633063,633065,634251,633608 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2224823004 Review-Url: https://codereview.chromium.org/2224823004
* require semi at the end of SkASSERT and friendsGravatar caryclark2016-07-27
| | | | | | | | R=bungeman@google.com TBR=reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2185063002 Review-Url: https://codereview.chromium.org/2185063002
* fuzz wednesdayGravatar caryclark2016-07-27
| | | | | | | | | | | | | Add debug 'skip assert' access to SkCoincidentSpans. That permits suppressing asserts to make it easier to detect when this fuzz data generates unparsable data. TBR=reed@google.com BUG=631564, 631992 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2186973002 Review-Url: https://codereview.chromium.org/2186973002
* fix fuzz bugsGravatar caryclark2016-07-26
| | | | | | | | | | | | | | | Add ability for intersection template to detect that the test contains bounded numbers so that extra asserts can trigger. Add some exit points for out of range numbers in those templates. TBR=reed@google.com BUG=631383,631374,631360 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2185703002 Review-Url: https://codereview.chromium.org/2185703002
* fix fuzzGravatar caryclark2016-07-25
| | | | | | | | | | | | Extreme inputs trigger asserts intended for in range data. Return an error without asserting unless the test signals otherwise. TBR=reed@google.com BUG=630736 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2178923002 Review-Url: https://codereview.chromium.org/2178923002
* limit number of searched rootsGravatar caryclark2016-07-22
| | | | | | | | | | | | | | Extreme numbers can generate more than three found cubic roots when the roots are found through a binary search. Fail in this case. TBR=reed@google.com BUG=630649 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2176733002 Review-Url: https://codereview.chromium.org/2176733002
* conic fuzz fixGravatar caryclark2016-07-22
| | | | | | | | | | | | | | | If no closest section is found in conic intersection (which can happen if the numbers are out of range) abort the intersection. Also suppress assert fired in this case so it only checks intersections with in-range values. TBR=reed@google.com BUG=630378 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2166813006 Review-Url: https://codereview.chromium.org/2166813006
* let line/cubic intersect at four spotsGravatar caryclark2016-07-21
| | | | | | | | | With this, let's update the fuzzer. R=kjlubick@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2169983002 Review-Url: https://codereview.chromium.org/2169983002
* allow curves on side of lines to be very smallGravatar caryclark2016-07-21
| | | | | | | | | | | | | | Increase the precision of the 'all on one side' pathops angle test to reduce the number of unorderable segments found by the cubics_d3 test. This allows pathsops_unittest release build with -v -V -x to run without error. TBR=reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2168163002 Review-Url: https://codereview.chromium.org/2168163002
* fix builder fuzzGravatar caryclark2016-07-21
| | | | | | | | | Fix ASAN_heap-use-after-free crash R=kjlubick GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2168963002 Review-Url: https://codereview.chromium.org/2168963002
* fix fuzzer bugGravatar caryclark2016-07-21
| | | | | | | | | | | | | | | | | Fix another fuzzer bug. Some PathOps asserts only make sense if the incoming data is well-behaved. Well-behaved tests set debugging state to trigger these additional asserts. Formalize this by creating macros similar to SkASSERT that check to see if the assert should be skipped. TBR=reed@google.com BUG=629962 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2169863002 Review-Url: https://codereview.chromium.org/2169863002
* fix fuzzerGravatar caryclark2016-07-19
| | | | | | | | | | | | Previous spans always have a valid next pointer. The final span does not. Change the test for a valid link to take into consideration whether the links are chased forwards or backwards. TBR=reed@google.com BUG=629454 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2166543002 Review-Url: https://codereview.chromium.org/2166543002
* pathops coincidence and security rewriteGravatar caryclark2016-07-18
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Most changes stem from working on an examples bracketed by #if DEBUG_UNDER_DEVELOPMENT // tiger These exposed many problems with coincident curves, as well as errors throughout the code. Fixing these errors also fixed a number of fuzzer-inspired bug reports. * Line/Curve Intersections Check to see if the end of the line nearly intersects the curve. This was a FIXME in the old code. * Performance Use a central chunk allocator. Plumb the allocator into the global variable state so that it can be shared. (Note that 'SkGlobalState' is allocated on the stack and is visible to children functions but not other threads.) * Refactor Let SkOpAngle grow up from a structure to a class. Let SkCoincidentSpans grow up from a structure to a class. Rename enum Alias to AliasMatch. * Coincidence Rewrite Add more debugging to coincidence detection. Parallel debugging routines have read-only logic to report the current coincidence state so that steps through the logic can expose whether things got better or worse. More functions can error-out and cause the pathops engine to non-destructively exit. * Accuracy Remove code that adjusted point locations. Instead, offset the curve part so that sorted curves all use the same origin. Reduce the size (and influence) of magic numbers. * Testing The debug suite with verify and the full release suite ./out/Debug/pathops_unittest -v -V ./out/Release/pathops_unittest -v -V -x expose one error. That error is captured as cubics_d3. This error exists in the checked in code as well. BUG=skia: GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2128633003 BUG=skia: GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2128633003 Review-Url: https://codereview.chromium.org/2128633003
* fix asan bug triggered by pathops fuzz testsGravatar caryclark2016-06-29
| | | | | | | | R=dogben@google.com TBR=reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2111473004 Review-Url: https://codereview.chromium.org/2111473004
* fix another pathops fuzz bugGravatar caryclark2016-06-29
| | | | | | | | | | | | Tunnel out the error case when the numerics create uncalculable angles. R=mmoroz@chromium.org TBR=reed@google.com BUG=624351 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2103863005 Review-Url: https://codereview.chromium.org/2103863005
* fix fuzz test that exceeds numeric limitGravatar caryclark2016-06-29
| | | | | | | | | | | | The extreme values here exceed an internal test that expects computed numbers to be less than MAX_FLT. Use MAX_DBL instead. R=mmoroz@chromium.org TBR=reed@google.com BUG=624346 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2103903004 Review-Url: https://codereview.chromium.org/2103903004
* fix fuzz bugsGravatar caryclark2016-06-28
| | | | | | | | | | | | | | | | Detect more places where the pathops numerics cause numbers to become nearly identical and subsequently fail. These tests have extreme inputs and cannot succeed. Also remove the expectSuccess parameter from PathOpsDebug and check instead in the test framework. R=mbarbella@chromium.org TBR=reed@google.com BUG=623072,623022 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2103513002 Review-Url: https://codereview.chromium.org/2103513002
* add fail condition to addexpandedGravatar caryclark2016-06-10
| | | | | | | | | | | If coincident pairs don't match, give up rather than deref null. R=fmalita@chromium.org BUG=618991 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2058773002 Review-Url: https://codereview.chromium.org/2058773002
* fix pathops fuzz bugsGravatar caryclark2016-06-08
| | | | | | | | | | | | | | | | | | | Fail out in a couple of new places when the input data is very large and exceeds the limits of the pathops machinery. Most of the change here plumbs in a way to exclude an assert in one of these exceptional cases. The current SkAddIntersection implementation and the inner functions it calls has no way to report an error to the root caller for an early exit, so rather than add that in, exclude the assert when the test that would trigger it runs (allowing the test to otherwise ensure that it properly fails). TBR=reed@google.com BUG=617586,617635 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2046713003 Review-Url: https://codereview.chromium.org/2046713003
* A Mozilla developer ran the µmix static analyzer on its codebase and ↵Gravatar lsalzman2016-06-07
| | | | | | | | | | | incidentally found some issues regarding null checks in Skia. This fixes the issues that were found. Downstream bug report: https://bugzilla.mozilla.org/show_bug.cgi?id=1278452 BUG=skia: GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2046563007 Review-Url: https://codereview.chromium.org/2046563007
* pin before calling acosGravatar caryclark2016-05-27
| | | | | | | | | | | | Adobe reports some user crashes in acos(). While the cause is unknown, it's safe and may help stability to pin the input in case the arguments drifted slightly outside [-1, 1]. R=reed@google.com BUG=skia:5222 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2006653006 Review-Url: https://codereview.chromium.org/2006653006
* fix security bugGravatar caryclark2016-05-26
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This fix is a tradeoff. It changes intersection to treat a case where one coincident run is intersected at one point and the other edge is not as continuing to be a span. The old code tried to treat this as a single point. The old code is probably right, but this change alone made the data structures inconsistent. Later, extending the coincident runs would fail by incorrectly discarding the single point intersection. As a result, this fixes the security test and one other, but makes a different test fail. Isolating the failure uncovered a reduced case that fails with and without the change, so there are more serious problems here. Those problems are addressed in a separate CL. Many of the test edits below remove ill-thought out debugging messaging that fire off global state, which isn't usable in a multi-threaded test environment. In the end, with this fix, all existing tests (modulo one new failure and one new non-failure) pass in debug and in the extended release test suites. TBR=reed@google.com BUG=614248 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2018513003 Review-Url: https://codereview.chromium.org/2018513003
* Revert of SK_DECLARE_STATIC_MUTEX -> static SkMutex (patchset #1 id:1 of ↵Gravatar reed2016-05-04
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | https://codereview.chromium.org/1948193002/ ) Reason for revert: broken the Mac and Linux builders, e.g.: https://build.chromium.org/p/chromium/builders/Mac/builds/15151 https://build.chromium.org/p/chromium/builders/Linux%20x64/builds/19052 Original issue's description: > SK_DECLARE_STATIC_MUTEX -> static SkMutex > > There's no need to use a macro to declare static SkMutexes any more > (and there's likewise no need to restrict them to global scope). > > BUG=skia: > GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1948193002 > > Committed: https://skia.googlesource.com/skia/+/5e56cfd3fa1041dbb83899844fb92fa9a2ef1009 TBR=mtklein@google.com,mtklein@chromium.org # Skipping CQ checks because original CL landed less than 1 days ago. NOPRESUBMIT=true NOTREECHECKS=true NOTRY=true BUG=skia: Review-Url: https://codereview.chromium.org/1945353003
* SK_DECLARE_STATIC_MUTEX -> static SkMutexGravatar mtklein2016-05-04
| | | | | | | | | | There's no need to use a macro to declare static SkMutexes any more (and there's likewise no need to restrict them to global scope). BUG=skia: GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1948193002 Review-Url: https://codereview.chromium.org/1948193002
* Fix warnings that were exposed when running with SK_DEBUG enable on an ↵Gravatar djsollen2016-04-29
| | | | | | | | optimized release build. GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1917223006 Review-Url: https://codereview.chromium.org/1917223006
* pathops: Split loop type cubics only when there is a self-intersection.Gravatar deanm2016-04-26
| | | | | | | | | | | | | The ComplexBreak code comes from Loop and Blinn, which requires loops to be split if either double point is visible. However for intersection loops only need to be split when there is actually a self-intersection (when both double points are in [0, 1]). This patch splits cubics much less often so the output doesn't have extra segments unless the input had a self-intersecting loop. BUG=skia: GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1920663002 Review URL: https://codereview.chromium.org/1920663002
* pathops: Cosmetic only change, update comments around ComplexBreak().Gravatar deanm2016-04-26
| | | | | | | | | | Rename loopT to splitT and make it clearer that it is not just self intersecting loop cubics that are split. BUG=skia: GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1921173003 Review URL: https://codereview.chromium.org/1921173003
* pathops: Add missing header guards in two files.Gravatar deanm2016-04-26
| | | | | | | | | | Guards were missing in SkIntersectionHelper.h and SkPathOpsTSect.h. BUG=skia: GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1914873002 Review URL: https://codereview.chromium.org/1914873002
* Appease valgrind wrt testing code initializationGravatar robertphillips2016-04-07
| | | | | | | | | | | | | The new swarming valgrind bot appears to be higher maintenance. These changes seem harmless and will, hopefully, unblock the bot. TBR=bsalomon@google.com https://build.chromium.org/p/client.skia.fyi/builders/Test-Ubuntu-GCC-ShuttleA-GPU-GTX550Ti-x86_64-Release-SwarmingValgrind/builds/57 BUG=skia:5164 GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1867053002 Review URL: https://codereview.chromium.org/1867053002
* give up if huge paths have unresolvable coincidenceGravatar caryclark2016-04-05
| | | | | | | | | | | | This fuzzy test has enormous curves with coincidence runs that break numerics. If the computed intersections identify that the span of coincidence has been deleted, give up and return that the path op failed. TBR=reed@google.com BUG=597926 GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1854333002 Review URL: https://codereview.chromium.org/1854333002
* detach -> releaseGravatar mtklein2016-03-16
| | | | | | | | | | | | | The C++ standard library uses the name "release" for the operation we call "detach". Rewriting each "detach(" to "release(" brings us a step closer to using standard library types directly (e.g. std::unique_ptr instead of SkAutoTDelete). This was a fairly blind transformation. There may have been unintentional conversions in here, but it's probably for the best to have everything uniformly say "release". BUG=skia: GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1809733002 Review URL: https://codereview.chromium.org/1809733002
* fix path ops fuzz bugGravatar caryclark2016-02-24
| | | | | | | | | | | | | | | | | | | If one path is empty and the other has extreme values, the intermediate coincident paths cannot be resolved, but triggers an assert that a data structure unexpectedly has zero-length. Tunnel this failure back up to the top and return that the entire path op fails. A future optimization could detect the empty path and avoid this, allowing the op to succeed -- not sure that it's worth the additional logic though. TBR=reed@google.com BUG=535151 GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1730293002 Review URL: https://codereview.chromium.org/1730293002
* add helper to create fancy underlinesGravatar caryclark2016-02-09
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Add a couple of utility functions to SkPaint that return the bounds of glyphs between a pair of lines. The common use case envisioned generates the edges of descenders between the top and bottom bounds of an underline to allow computing a stroke that skips those descenders. The implementation stores a linked list in each glyph containing the bounds of the lines parallel to the advance and the outermost intersections within those bounds. When the glyph cache is constructed, the glyph path is intersected with the bounds and the extreme min and max values within the bounds is added to an intercept. Share the text to path iter to construct the data. Make a half-hearted attempt to support vertical text; while the vertical implementation is complete; surrounding code (e.g. paint align) has short-comings with vertical. R=fmalita@chromium.org, reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1654883003 Review URL: https://codereview.chromium.org/1654883003
* Consolidate SK_CRASH and sk_throw into SK_ABORTGravatar djsollen2016-01-29
| | | | | | | TBR=reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1648343003 Review URL: https://codereview.chromium.org/1648343003
* Revert of Consolidate SK_CRASH and sk_throw into SK_ABORT (patchset #5 ↵Gravatar djsollen2016-01-22
| | | | | | | | | | | | | | | | | | | | | id:80001 of https://codereview.chromium.org/1610823002/ ) Reason for revert: Chrome is calling SK_CRASH Original issue's description: > Consolidate SK_CRASH and sk_throw into SK_ABORT > GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1610823002 > > Committed: https://skia.googlesource.com/skia/+/4c5cd7d527ed29aabfa72aa47b23a4496eeda357 TBR=reed@google.com # Skipping CQ checks because original CL landed less than 1 days ago. NOPRESUBMIT=true NOTREECHECKS=true NOTRY=true Review URL: https://codereview.chromium.org/1620333002
* Consolidate SK_CRASH and sk_throw into SK_ABORTGravatar djsollen2016-01-22
| | | | | | GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1610823002 Review URL: https://codereview.chromium.org/1610823002
* only call scalar finite when necessaryGravatar caryclark2015-12-16
| | | | | | | | | | | | | | | | | Mike points that the the ulps compares rank high in path ops profiles. The check for finite scalars is rarely required. Call it less by: - specializing _pin version of compares - checking for 0 divides up front - handling failing cases before comparing - casting float to double before adding R=reed@google.com Review URL: https://codereview.chromium.org/1522183002
* path ops: check for deleted endsGravatar caryclark2015-12-14
| | | | | | | TBR=fmalita@chromium.org BUG=569540 Review URL: https://codereview.chromium.org/1524803002
* ubsan shift fixesGravatar caryclark2015-12-09
| | | | | | | | | | | Use an inline function that does a normal shift. When built for the sanitizer, add casts so that the shift is unsigned. Also make a few fixes to do unsigned shifts or avoid the shift altogether; and add an argument spec to some macros. R=reed@google.com,mtklein@google.com BUG=skia:4633 Review URL: https://codereview.chromium.org/1503423003
* fix coincident fuzzerGravatar caryclark2015-12-07
| | | | | | | | | | | This fuzzer has very large Y values that cause the points to sort incorrectly by t. Exit out as soon as this is detected. TBR=reed@google.com BUG=561121 Review URL: https://codereview.chromium.org/1507803002
* fix pathops coincidence fuzz bugGravatar caryclark2015-11-20
| | | | | | | | | | | | | | | | | | | | | Simplifying a series of rects with very large bounds triggers a coincidence bug where, after one of the intersection points that marks a coincident range has been deleted, it is referenced. Both the deletion and reference is (probably) happening in the SkOpCoincidence::AddExpanded() phase of HandleCoincidence(), and may signify a bug that could happen with usable input data, but I haven't been able to determine that. For now, abort the Simplify() when the erroneous condition is detected. TBR=reed@google.com BUG=558281 Review URL: https://codereview.chromium.org/1463923002
* path ops: fix fuzz-found divide by zeroGravatar caryclark2015-11-02
| | | | | | | TBR=reed@google.com BUG=542391 Review URL: https://codereview.chromium.org/1427913005
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-05 14:39:32 +0000