Polygon to cells experimental fuzzer

[isaacbrodsky]

This adds new fuzzers for the polygonToCellsExperimental function, based on the existing functions. Since #796 (this PR is based on that branch) adds containment modes, this updates the existing fuzzers to exercise those options too.

When I run the fuzzerPolygonToCellsExperimental, I see some runtime errors about misaligned addresses, which doesn't cause an issue on Apple M1 architecture but might indicate trouble on other architectures. When I run fuzzerPolygonToCellsExperimentalNoHoles I get a crash about heap-buffer-overflow around polygonToCellsExperimental polyfill.c:646 (looks like the output exceeds the allocated output buffer in some case?)

[coveralls]

coverage: 98.762% (-0.06%) from 98.826% when pulling 74f206e093cbec5368395781e4374bf12dfe4244 on isaacbrodsky:polygon-to-cells-experimental-fuzzer into 25160b947717bef8b80fab74451c1826718bfabd on uber:master.

[nrabinowitz]

I think the/one issue here is polar shapes. When I run all countries, I see differences in output for Antarctica (not sure why I didn't catch this earlier):

My new estimator seems to cover this case, though it has other issues I'm still debugging. I haven't had a chance yet to check what the old/new output looks like, though I'd guess that the new output is closer to correct due to better handling of the pole itself.

[nrabinowitz]

Old polyfill:

New polyfill:

The new one may be correct, I'd have to import the original polygon to check

[isaacbrodsky]

The new one may be correct, I'd have to import the original polygon to check

Has this polygon been added as a test case to ensure we aren't dropping a lot of cells there?

[nrabinowitz]

The new one may be correct, I'd have to import the original polygon to check

Has this polygon been added as a test case to ensure we aren't dropping a lot of cells there?

I'd rather add some simplified version, as the Antarctica polygon is too large to be easily added to a test file. I can add a new PR with more tests for this.

[nrabinowitz]

Still seeing errors here with the new estimator. Is there an easy-ish way to get the input for the failure cases?

[isaacbrodsky]

I added a test case that demonstrates this. (If you run under valgrind it will show an issue.) It seems we do not actually test a polygon with a single vertex being passed in. If you do so with res=0, flags=2 (CONTAINMENT_OVERLAPPING), the estimate will be 0 but the function will try to write the buffer.

[isaacbrodsky]

Here is the hexdump of a new crash case for fuzzerPolygonToCellsExperimental:

$ hexdump ./crash-7bee58752754302154762e5e3a399235e773c80c
0000000 0000 4400 0005 0000 0001 0000 0000 0000
0000010 0000 0000 0000 0000 0000 0000 0009 0000
0000020 0000 0000 0000 0000 0000 9f00 9f9f 9f9f
0000030 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f 6069
0000040 6060 6060 6060 9f9f 9f9f 9f9f 9f9f 9f9f
0000050 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f
*
0000090 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f 3939 3939
00000a0 3939 3939 3939 3939 0039 0000 0000 0000
00000b0 0000 0000 0000 0000 0000 0000 0000 0000
*
0000180 9f00 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f
0000190 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f
*
00001c0 9f9f 9f9f 9f9f 9f2a 9f9f 9f9f 9f9f 9f9f
00001d0 9f9f 9f9f 9f9f 399f 3939 3939 3939 3939
00001e0 3939 3939 0000 0000 0000 0000 0000 0000
00001f0 0000 0000 0000 0000 0000 0000 0000 0000
0000200 0000 0000 0544 0000 0000 0000 0000 0000
0000210 0000 0040 0000 0000 0000 0000 9f9f 9f9f
0000220 9f9f 9f9f 9f9a 9f9f 9f9f 9f9f 9f9f 9f9f
0000230 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f
*
0000260 9f9f 9f9f 9f9f 9f9f 9f9f 399f 3939 3939
0000270 3b39 3939 3939 3939 3939 3939 3939 3939
0000280 3939 3939 3939 3939 3939 3939 3939 3939
0000290 3939 3939 3939 3939 3939 9f38 9f9f 9f9f
00002a0 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f
*
00002c0 9f9f 9f9f 9f9f 9f89 9f9f 9f9f 409f 9f9f
00002d0 9f9f fc9f 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f
00002e0 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f
00002f0 9f9f 9f9f 9f9f 0000 0000 0000 0000 0000
0000300 0000 0000 0000 0000 0000 0000 0000 9f9f
0000310 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f
*
0000340 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f 009f
0000350 0000 0000 0000 0000 9f9f 9f9f 9f9f 9f9f
0000360 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f
*
0000380 3939 3939 3939 3939 3939 3939 0039 0000
0000390 0000 0000 0800 0000 0000 0000 0000 0000
00003a0 0000 0000 0000 0000 9f9f 9f9f 9f9f 9f9f
00003b0 9fe7 9f9f 9f9f 9f9f 9f9f 0c01 0000 0000
00003c0 0000 0000 0000 0000 9f00 9f9f 9f9f 9f9f
00003d0 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f 9f9f
*
0000430 9f9f 9f9f 9f9f 9f9f 0000 0800 0000 0000
0000440 0000 0000 0000 9f00 9f9f 0000          
000044b

[CLAassistant]

Thank you for your submission! We really appreciate it. Like many open source projects, we ask that you all sign our Contributor License Agreement before we can accept your contribution.
1 out of 2 committers have signed the CLA.

:white_check_mark: isaacbrodsky
:x: Nick Rabinowitz

---

Nick Rabinowitz seems not to be a GitHub user. You need a GitHub account to be able to sign the CLA. If you have already a GitHub account, please add the email address used for this commit to your account.
_{You have signed the CLA already but the status is still pending? Let us recheck it.}

[isaacbrodsky]

I tried adding an additional check today to recompute the expected array size and bail if the function is about to write past the end of the array. That seems to, at the cost of recomputing the size, avoid any remaining crashes. Unfortunately there is a timeout with some input which is currently failing the test.