From de71b07792a0751406e8f83264f08ec78449a15c Mon Sep 17 00:00:00 2001 From: Nick Rabinowitz Date: Fri, 3 Nov 2023 17:50:09 -0700 Subject: [PATCH 01/37] Add support for full containment mode in polygonToCells --- src/apps/testapps/testPolygonToCells.c | 10 ++-- .../testapps/testPolygonToCellsExperimental.c | 10 ++-- src/h3lib/include/polygon.h | 15 ++++++ src/h3lib/lib/algos.c | 10 ++-- src/h3lib/lib/polyfill.c | 54 ++++++++++++++----- src/h3lib/lib/polygon.c | 15 ++++++ 6 files changed, 88 insertions(+), 26 deletions(-) diff --git a/src/apps/testapps/testPolygonToCells.c b/src/apps/testapps/testPolygonToCells.c index 22a0cdecf8..b35dedd580 100644 --- a/src/apps/testapps/testPolygonToCells.c +++ b/src/apps/testapps/testPolygonToCells.c @@ -461,19 +461,21 @@ SUITE(polygonToCells) { TEST(invalidFlags) { int64_t numHexagons; - for (uint32_t flags = 1; flags <= 32; flags++) { + for (uint32_t flags = 3; flags <= 32; flags++) { t_assert( H3_EXPORT(maxPolygonToCellsSize)( &sfGeoPolygon, 9, flags, &numHexagons) == E_OPTION_INVALID, - "Flags other than 0 are invalid for maxPolygonToCellsSize"); + "Flags other than polyfill modes are invalid for " + "maxPolygonToCellsSize"); } t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)(&sfGeoPolygon, 9, 0, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); - for (uint32_t flags = 1; flags <= 32; flags++) { + for (uint32_t flags = 3; flags <= 32; flags++) { t_assert(H3_EXPORT(polygonToCells)(&sfGeoPolygon, 9, flags, hexagons) == E_OPTION_INVALID, - "Flags other than 0 are invalid for polygonToCells"); + "Flags other than polyfill modes are invalid for " + "polygonToCells"); } free(hexagons); } diff --git a/src/apps/testapps/testPolygonToCellsExperimental.c b/src/apps/testapps/testPolygonToCellsExperimental.c index f389456abb..22a825e48c 100644 --- a/src/apps/testapps/testPolygonToCellsExperimental.c +++ b/src/apps/testapps/testPolygonToCellsExperimental.c @@ -413,19 +413,21 @@ SUITE(polygonToCells) { TEST(invalidFlags) { int64_t numHexagons; - for (uint32_t flags = 1; flags <= 32; flags++) { + for (uint32_t flags = 3; flags <= 32; flags++) { t_assert( H3_EXPORT(maxPolygonToCellsSize)( &sfGeoPolygon, 9, flags, &numHexagons) == E_OPTION_INVALID, - "Flags other than 0 are invalid for maxPolygonToCellsSize"); + "Flags other than polyfill modes are invalid for " + "maxPolygonToCellsSize"); } t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)(&sfGeoPolygon, 9, 0, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); - for (uint32_t flags = 1; flags <= 32; flags++) { + for (uint32_t flags = 3; flags <= 32; flags++) { t_assert(H3_EXPORT(polygonToCellsExperimental)( &sfGeoPolygon, 9, flags, hexagons) == E_OPTION_INVALID, - "Flags other than 0 are invalid for polygonToCells"); + "Flags other than polyfill modes are invalid for " + "polygonToCells"); } free(hexagons); } diff --git a/src/h3lib/include/polygon.h b/src/h3lib/include/polygon.h index 387ed034a3..3fce0c6929 100644 --- a/src/h3lib/include/polygon.h +++ b/src/h3lib/include/polygon.h @@ -40,7 +40,22 @@ /** Macro: Whether a GeoLoop is empty */ #define IS_EMPTY_GEOFENCE(geoloop) geoloop->numVerts == 0 +/** + * Values representing polyfill containment modes, to be used in + * the `flags` bit field. + */ +typedef enum { + CENTER_CONTAINMENT = 0, + FULL_CONTAINMENT = 1, + INTERSECTION = 2 +} ContainmentMode; + +// 1s in the 4 bits defining the polyfill containment mode, 0s elsewhere +#define FLAG_CONTAINMENT_MODE_MASK ((uint32_t)(15)) +#define FLAG_GET_CONTAINMENT_MODE(flags) (flags & FLAG_CONTAINMENT_MODE_MASK) + // Defined directly in polygon.c: +H3Error validatePolygonFlags(uint32_t flags); void bboxesFromGeoPolygon(const GeoPolygon *polygon, BBox *bboxes); bool pointInsidePolygon(const GeoPolygon *geoPolygon, const BBox *bboxes, const LatLng *coord); diff --git a/src/h3lib/lib/algos.c b/src/h3lib/lib/algos.c index 79666d8432..949988a082 100644 --- a/src/h3lib/lib/algos.c +++ b/src/h3lib/lib/algos.c @@ -774,8 +774,9 @@ H3Error H3_EXPORT(gridRingUnsafe)(H3Index origin, int k, H3Index *out) { */ H3Error H3_EXPORT(maxPolygonToCellsSize)(const GeoPolygon *geoPolygon, int res, uint32_t flags, int64_t *out) { - if (flags != 0) { - return E_OPTION_INVALID; + H3Error flagErr = validatePolygonFlags(flags); + if (flagErr) { + return flagErr; } // Get the bounding box for the GeoJSON-like struct BBox bbox; @@ -890,8 +891,9 @@ H3Error _getEdgeHexagons(const GeoLoop *geoloop, int64_t numHexagons, int res, */ H3Error H3_EXPORT(polygonToCells)(const GeoPolygon *geoPolygon, int res, uint32_t flags, H3Index *out) { - if (flags != 0) { - return E_OPTION_INVALID; + H3Error flagErr = validatePolygonFlags(flags); + if (flagErr) { + return flagErr; } // One of the goals of the polygonToCells algorithm is that two adjacent // polygons with zero overlap have zero overlapping hexagons. That the diff --git a/src/h3lib/lib/polyfill.c b/src/h3lib/lib/polyfill.c index 7ba5a28b53..6411f6972d 100644 --- a/src/h3lib/lib/polyfill.c +++ b/src/h3lib/lib/polyfill.c @@ -354,8 +354,9 @@ IterCellsPolygonCompact iterInitPolygonCompact(const GeoPolygon *polygon, return iter; } - if (flags != 0) { - iterErrorPolygonCompact(&iter, E_OPTION_INVALID); + H3Error flagErr = validatePolygonFlags(flags); + if (flagErr) { + iterErrorPolygonCompact(&iter, flagErr); return iter; } @@ -406,23 +407,48 @@ void iterStepPolygonCompact(IterCellsPolygonCompact *iter) { iter->_started = true; } + ContainmentMode mode = FLAG_GET_CONTAINMENT_MODE(iter->_flags); + while (cell) { int cellRes = H3_GET_RESOLUTION(cell); // Target res: Do a fine-grained check if (cellRes == iter->_res) { - // Check if the cell is in the polygon - // TODO: Handle other polyfill modes here - LatLng center; - H3Error centerErr = H3_EXPORT(cellToLatLng)(cell, ¢er); - if (NEVER(centerErr != E_SUCCESS)) { - iterErrorPolygonCompact(iter, centerErr); - return; - } - if (pointInsidePolygon(iter->_polygon, iter->_bboxes, ¢er)) { - // Set to next output - iter->cell = cell; - return; + if (mode == CENTER_CONTAINMENT) { + // Check if the cell center is inside the polygon + LatLng center; + H3Error centerErr = H3_EXPORT(cellToLatLng)(cell, ¢er); + if (centerErr != E_SUCCESS) { + iterErrorPolygonCompact(iter, centerErr); + return; + } + if (pointInsidePolygon(iter->_polygon, iter->_bboxes, + ¢er)) { + // Set to next output + iter->cell = cell; + return; + } + } else if (mode == FULL_CONTAINMENT) { + // Check if the cell is fully contained by the polygon + CellBoundary boundary; + H3Error boundaryErr = + H3_EXPORT(cellToBoundary)(cell, &boundary); + if (boundaryErr != E_SUCCESS) { + iterErrorPolygonCompact(iter, boundaryErr); + return; + } + BBox bbox; + H3Error bboxErr = cellToBBox(cell, &bbox, false); + if (bboxErr) { + iterErrorPolygonCompact(iter, bboxErr); + return; + } + if (cellBoundaryInsidePolygon(iter->_polygon, iter->_bboxes, + &boundary, &bbox)) { + // Set to next output + iter->cell = cell; + return; + } } } diff --git a/src/h3lib/lib/polygon.c b/src/h3lib/lib/polygon.c index a92fecfba5..e1ec4a37dc 100644 --- a/src/h3lib/lib/polygon.c +++ b/src/h3lib/lib/polygon.c @@ -42,6 +42,21 @@ #undef ITERATE #undef IS_EMPTY +/** + * Whether the flags for the polyfill operation are valid + * TODO: Move to polyfill.c when the old algo is removed + * @param flags Flags to validate + * @return Whether the flags are valid + */ +H3Error validatePolygonFlags(uint32_t flags) { + if (flags & (~FLAG_CONTAINMENT_MODE_MASK) || + !(FLAG_GET_CONTAINMENT_MODE(flags) == CENTER_CONTAINMENT || + FLAG_GET_CONTAINMENT_MODE(flags) == FULL_CONTAINMENT)) { + return E_OPTION_INVALID; + } + return E_SUCCESS; +} + /** * Create a bounding box from a GeoPolygon * @param polygon Input GeoPolygon From 45255d55a42cff678b6bb39bc6b4ab85719dca06 Mon Sep 17 00:00:00 2001 From: Nick Rabinowitz Date: Fri, 3 Nov 2023 17:59:33 -0700 Subject: [PATCH 02/37] Add tests --- .../testapps/testPolygonToCellsExperimental.c | 32 +++++++++++++++++++ 1 file changed, 32 insertions(+) diff --git a/src/apps/testapps/testPolygonToCellsExperimental.c b/src/apps/testapps/testPolygonToCellsExperimental.c index 22a825e48c..2baa7c587a 100644 --- a/src/apps/testapps/testPolygonToCellsExperimental.c +++ b/src/apps/testapps/testPolygonToCellsExperimental.c @@ -22,6 +22,7 @@ #include "h3Index.h" #include "latLng.h" #include "polyfill.h" +#include "polygon.h" #include "test.h" #include "utility.h" @@ -172,6 +173,21 @@ SUITE(polygonToCells) { free(hexagons); } + TEST(polygonToCellsFullContainment) { + int64_t numHexagons; + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( + &sfGeoPolygon, 9, FULL_CONTAINMENT, &numHexagons)); + H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); + + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &sfGeoPolygon, 9, FULL_CONTAINMENT, hexagons)); + int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); + + t_assert(actualNumIndexes == 1175, + "got expected polygonToCells size (full containment mode)"); + free(hexagons); + } + TEST(polygonToCellsHole) { int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)(&holeGeoPolygon, 9, 0, @@ -187,6 +203,22 @@ SUITE(polygonToCells) { free(hexagons); } + TEST(polygonToCellsHoleFullContainment) { + int64_t numHexagons; + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( + &holeGeoPolygon, 9, FULL_CONTAINMENT, &numHexagons)); + H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); + + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &holeGeoPolygon, 9, FULL_CONTAINMENT, hexagons)); + int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); + + t_assert( + actualNumIndexes == 1118, + "got expected polygonToCells size (hole, full containment mode)"); + free(hexagons); + } + TEST(polygonToCellsEmpty) { int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)(&emptyGeoPolygon, 9, 0, From 61d3e5bcac518db1945311635b6a3bf662417cd5 Mon Sep 17 00:00:00 2001 From: Nick Rabinowitz Date: Sat, 4 Nov 2023 14:49:45 -0700 Subject: [PATCH 03/37] Implement OVERLAPPING mode, update tests to use mode flags --- scripts/make_countries.js | 17 ++- .../benchmarkPolygonToCellsExperimental.c | 19 ++- src/apps/testapps/testH3Memory.c | 13 +- src/apps/testapps/testPolygonInternal.c | 24 ++-- .../testapps/testPolygonToCellsExperimental.c | 118 ++++++++++++------ .../testPolygonToCellsReportedExperimental.c | 44 ++++--- src/h3lib/include/polygon.h | 11 +- src/h3lib/lib/polyfill.c | 20 ++- src/h3lib/lib/polygon.c | 36 +++++- 9 files changed, 207 insertions(+), 95 deletions(-) diff --git a/scripts/make_countries.js b/scripts/make_countries.js index 4e8a495d43..42c0a39746 100644 --- a/scripts/make_countries.js +++ b/scripts/make_countries.js @@ -131,6 +131,7 @@ async function makeCountries(sourceUrl, targetPath) { #include "h3api.h" #include "mathExtensions.h" #include "polyfill.h" +#include "polygon.h" const GeoPolygon COUNTRIES[${polygons.length}] = {${ polygons.map((poly, i) => formatGeoPolygon(poly, names[i])).join(',') @@ -149,13 +150,25 @@ for (int res = 0; res < MAX_RES + 1; res++) { BENCHMARK(polygonToCells_AllCountries1, 5, { for (int index = 0; index < ${polygons.length}; index++) { - H3_EXPORT(polygonToCells)(&COUNTRIES[index], res, 0, hexagons); + H3_EXPORT(polygonToCells)(&COUNTRIES[index], res, CENTER_CONTAINMENT, hexagons); } }); BENCHMARK(polygonToCells_AllCountries2, 5, { for (int index = 0; index < ${polygons.length}; index++) { - H3_EXPORT(polygonToCellsExperimental)(&COUNTRIES[index], res, 0, hexagons); + H3_EXPORT(polygonToCellsExperimental)(&COUNTRIES[index], res, CENTER_CONTAINMENT, hexagons); + } + }); + + BENCHMARK(polygonToCells_AllCountries3, 5, { + for (int index = 0; index < ${polygons.length}; index++) { + H3_EXPORT(polygonToCellsExperimental)(&COUNTRIES[index], res, FULL_CONTAINMENT, hexagons); + } + }); + + BENCHMARK(polygonToCells_AllCountries4, 5, { + for (int index = 0; index < ${polygons.length}; index++) { + H3_EXPORT(polygonToCellsExperimental)(&COUNTRIES[index], res, OVERLAPPING, hexagons); } }); diff --git a/src/apps/benchmarks/benchmarkPolygonToCellsExperimental.c b/src/apps/benchmarks/benchmarkPolygonToCellsExperimental.c index b0837c7fcb..13c01cebdc 100644 --- a/src/apps/benchmarks/benchmarkPolygonToCellsExperimental.c +++ b/src/apps/benchmarks/benchmarkPolygonToCellsExperimental.c @@ -17,6 +17,7 @@ #include "benchmark.h" #include "h3api.h" #include "polyfill.h" +#include "polygon.h" // Fixtures LatLng sfVerts[] = { @@ -123,23 +124,29 @@ int64_t numHexagons; H3Index *hexagons; BENCHMARK(polygonToCellsSF, 500, { - H3_EXPORT(maxPolygonToCellsSize)(&sfGeoPolygon, 9, 0, &numHexagons); + H3_EXPORT(maxPolygonToCellsSize) + (&sfGeoPolygon, 9, CENTER_CONTAINMENT, &numHexagons); hexagons = calloc(numHexagons, sizeof(H3Index)); - H3_EXPORT(polygonToCellsExperimental)(&sfGeoPolygon, 9, 0, hexagons); + H3_EXPORT(polygonToCellsExperimental) + (&sfGeoPolygon, 9, CENTER_CONTAINMENT, hexagons); free(hexagons); }); BENCHMARK(polygonToCellsAlameda, 500, { - H3_EXPORT(maxPolygonToCellsSize)(&alamedaGeoPolygon, 9, 0, &numHexagons); + H3_EXPORT(maxPolygonToCellsSize) + (&alamedaGeoPolygon, 9, CENTER_CONTAINMENT, &numHexagons); hexagons = calloc(numHexagons, sizeof(H3Index)); - H3_EXPORT(polygonToCellsExperimental)(&alamedaGeoPolygon, 9, 0, hexagons); + H3_EXPORT(polygonToCellsExperimental) + (&alamedaGeoPolygon, 9, CENTER_CONTAINMENT, hexagons); free(hexagons); }); BENCHMARK(polygonToCellsSouthernExpansion, 10, { - H3_EXPORT(maxPolygonToCellsSize)(&southernGeoPolygon, 9, 0, &numHexagons); + H3_EXPORT(maxPolygonToCellsSize) + (&southernGeoPolygon, 9, CENTER_CONTAINMENT, &numHexagons); hexagons = calloc(numHexagons, sizeof(H3Index)); - H3_EXPORT(polygonToCellsExperimental)(&southernGeoPolygon, 9, 0, hexagons); + H3_EXPORT(polygonToCellsExperimental) + (&southernGeoPolygon, 9, CENTER_CONTAINMENT, hexagons); free(hexagons); }); diff --git a/src/apps/testapps/testH3Memory.c b/src/apps/testapps/testH3Memory.c index 96627b5431..f4e9ec4afc 100644 --- a/src/apps/testapps/testH3Memory.c +++ b/src/apps/testapps/testH3Memory.c @@ -26,6 +26,7 @@ #include "h3api.h" #include "latLng.h" #include "polyfill.h" +#include "polygon.h" #include "test.h" #include "utility.h" @@ -230,22 +231,22 @@ SUITE(h3Memory) { sfGeoPolygon.numHoles = 0; int64_t numHexagons; - t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)(&sfGeoPolygon, 9, 0, - &numHexagons)); + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( + &sfGeoPolygon, 9, CENTER_CONTAINMENT, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); resetMemoryCounters(0); failAlloc = true; - H3Error err = H3_EXPORT(polygonToCellsExperimental)(&sfGeoPolygon, 9, 0, - hexagons); + H3Error err = H3_EXPORT(polygonToCellsExperimental)( + &sfGeoPolygon, 9, CENTER_CONTAINMENT, hexagons); t_assert(err == E_MEMORY_ALLOC, "polygonToCellsExperimental failed (1)"); t_assert(actualAllocCalls == 1, "alloc called once"); t_assert(actualFreeCalls == 0, "free not called"); resetMemoryCounters(1); - err = H3_EXPORT(polygonToCellsExperimental)(&sfGeoPolygon, 9, 0, - hexagons); + err = H3_EXPORT(polygonToCellsExperimental)( + &sfGeoPolygon, 9, CENTER_CONTAINMENT, hexagons); t_assert(err == E_SUCCESS, "polygonToCellsExperimental succeeded (1)"); t_assert(actualAllocCalls == 1, "alloc called one time"); t_assert(actualFreeCalls == 1, "free called one time"); diff --git a/src/apps/testapps/testPolygonInternal.c b/src/apps/testapps/testPolygonInternal.c index 4b0f802868..42d19d14a8 100644 --- a/src/apps/testapps/testPolygonInternal.c +++ b/src/apps/testapps/testPolygonInternal.c @@ -626,55 +626,55 @@ SUITE(polygonInternal) { H3_EXPORT(destroyLinkedMultiPolygon)(&polygon); } - TEST(lineIntersectsLine) { + TEST(lineCrossesLine) { LatLng lines1[4] = {{0, 0}, {1, 1}, {0, 1}, {1, 0}}; t_assert( - lineIntersectsLine(&lines1[0], &lines1[1], &lines1[2], &lines1[3]), + lineCrossesLine(&lines1[0], &lines1[1], &lines1[2], &lines1[3]), "diagonal intersection"); LatLng lines2[4] = {{1, 1}, {0, 0}, {1, 0}, {0, 1}}; t_assert( - lineIntersectsLine(&lines2[0], &lines2[1], &lines2[2], &lines2[3]), + lineCrossesLine(&lines2[0], &lines2[1], &lines2[2], &lines2[3]), "diagonal intersection, reverse vertexes"); LatLng lines3[4] = {{0.5, 0}, {0.5, 1}, {0, 0.5}, {1, 0.5}}; t_assert( - lineIntersectsLine(&lines3[0], &lines3[1], &lines3[2], &lines3[3]), + lineCrossesLine(&lines3[0], &lines3[1], &lines3[2], &lines3[3]), "horizontal/vertical intersection"); LatLng lines4[4] = {{0.5, 1}, {0.5, 0}, {1, 0.5}, {0, 0.5}}; t_assert( - lineIntersectsLine(&lines4[0], &lines4[1], &lines4[2], &lines4[3]), + lineCrossesLine(&lines4[0], &lines4[1], &lines4[2], &lines4[3]), "horizontal/vertical intersection, reverse vertexes"); LatLng lines5[4] = {{0, 0}, {0.4, 0.4}, {0, 1}, {1, 0}}; t_assert( - !lineIntersectsLine(&lines5[0], &lines5[1], &lines5[2], &lines5[3]), + !lineCrossesLine(&lines5[0], &lines5[1], &lines5[2], &lines5[3]), "diagonal non-intersection, below"); LatLng lines6[4] = {{0.6, 0.6}, {1, 1}, {0, 1}, {1, 0}}; t_assert( - !lineIntersectsLine(&lines6[0], &lines6[1], &lines6[2], &lines6[3]), + !lineCrossesLine(&lines6[0], &lines6[1], &lines6[2], &lines6[3]), "diagonal non-intersection, above"); LatLng lines7[4] = {{0.5, 0}, {0.5, 1}, {0, 0.5}, {0.4, 0.5}}; t_assert( - !lineIntersectsLine(&lines7[0], &lines7[1], &lines7[2], &lines7[3]), + !lineCrossesLine(&lines7[0], &lines7[1], &lines7[2], &lines7[3]), "horizontal/vertical non-intersection, below"); LatLng lines8[4] = {{0.5, 0}, {0.5, 1}, {0.6, 0.5}, {1, 0.5}}; t_assert( - !lineIntersectsLine(&lines8[0], &lines8[1], &lines8[2], &lines8[3]), + !lineCrossesLine(&lines8[0], &lines8[1], &lines8[2], &lines8[3]), "horizontal/vertical non-intersection, above"); LatLng lines9[4] = {{0.5, 0}, {0.5, 0.4}, {0, 0.5}, {1, 0.5}}; t_assert( - !lineIntersectsLine(&lines9[0], &lines9[1], &lines9[2], &lines9[3]), + !lineCrossesLine(&lines9[0], &lines9[1], &lines9[2], &lines9[3]), "horizontal/vertical non-intersection, left"); LatLng lines10[4] = {{0.5, 0.6}, {0.5, 1}, {0, 0.5}, {1, 0.5}}; - t_assert(!lineIntersectsLine(&lines10[0], &lines10[1], &lines10[2], - &lines10[3]), + t_assert(!lineCrossesLine(&lines10[0], &lines10[1], &lines10[2], + &lines10[3]), "horizontal/vertical non-intersection, right"); } diff --git a/src/apps/testapps/testPolygonToCellsExperimental.c b/src/apps/testapps/testPolygonToCellsExperimental.c index 2baa7c587a..1435c8d511 100644 --- a/src/apps/testapps/testPolygonToCellsExperimental.c +++ b/src/apps/testapps/testPolygonToCellsExperimental.c @@ -100,7 +100,7 @@ static void fillIndex_assertions(H3Index h) { H3Index *polygonToCellsOut = calloc(polygonToCellsSize, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &polygon, nextRes, 0, polygonToCellsOut)); + &polygon, nextRes, CENTER_CONTAINMENT, polygonToCellsOut)); int64_t polygonToCellsCount = countNonNullIndexes(polygonToCellsOut, polygonToCellsSize); @@ -161,12 +161,12 @@ SUITE(polygonToCells) { TEST(polygonToCells) { int64_t numHexagons; - t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)(&sfGeoPolygon, 9, 0, - &numHexagons)); + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( + &sfGeoPolygon, 9, CENTER_CONTAINMENT, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); - t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)(&sfGeoPolygon, 9, - 0, hexagons)); + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &sfGeoPolygon, 9, CENTER_CONTAINMENT, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 1253, "got expected polygonToCells size"); @@ -188,14 +188,29 @@ SUITE(polygonToCells) { free(hexagons); } + TEST(polygonToCellsOverlapping) { + int64_t numHexagons; + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( + &sfGeoPolygon, 9, OVERLAPPING, &numHexagons)); + H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); + + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &sfGeoPolygon, 9, OVERLAPPING, hexagons)); + int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); + + t_assert(actualNumIndexes == 1334, + "got expected polygonToCells size (overlapping mode)"); + free(hexagons); + } + TEST(polygonToCellsHole) { int64_t numHexagons; - t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)(&holeGeoPolygon, 9, 0, - &numHexagons)); + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( + &holeGeoPolygon, 9, CENTER_CONTAINMENT, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); - t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)(&holeGeoPolygon, - 9, 0, hexagons)); + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &holeGeoPolygon, 9, CENTER_CONTAINMENT, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 1214, @@ -219,14 +234,29 @@ SUITE(polygonToCells) { free(hexagons); } + TEST(polygonToCellsHoleOverlapping) { + int64_t numHexagons; + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( + &holeGeoPolygon, 9, OVERLAPPING, &numHexagons)); + H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); + + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &holeGeoPolygon, 9, OVERLAPPING, hexagons)); + int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); + + t_assert(actualNumIndexes == 1311, + "got expected polygonToCells size (hole, overlapping mode)"); + free(hexagons); + } + TEST(polygonToCellsEmpty) { int64_t numHexagons; - t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)(&emptyGeoPolygon, 9, 0, - &numHexagons)); + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( + &emptyGeoPolygon, 9, CENTER_CONTAINMENT, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); - t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)(&emptyGeoPolygon, - 9, 0, hexagons)); + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &emptyGeoPolygon, 9, CENTER_CONTAINMENT, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 0, @@ -255,15 +285,27 @@ SUITE(polygonToCells) { someHexagon.numHoles = 0; int64_t numHexagons; - t_assertSuccess( - H3_EXPORT(maxPolygonToCellsSize)(&someHexagon, 9, 0, &numHexagons)); + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( + &someHexagon, 9, CENTER_CONTAINMENT, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); - t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)(&someHexagon, 9, - 0, hexagons)); - int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); + int64_t actualNumIndexes; + + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &someHexagon, 9, CENTER_CONTAINMENT, hexagons)); + actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); + t_assert(actualNumIndexes == 1, + "got expected polygonToCells size for center containment (1)"); + + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &someHexagon, 9, FULL_CONTAINMENT, hexagons)); + actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); + t_assert(actualNumIndexes == 1, + "got expected polygonToCells size for full containment (1)"); + + // TODO: OVERLAPPING yields 7 cells, presumably due to FPE in the + // various cell boundaries - t_assert(actualNumIndexes == 1, "got expected polygonToCells size (1)"); free(hexagons); free(verts); } @@ -304,11 +346,11 @@ SUITE(polygonToCells) { expectedSize = 4228; int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &primeMeridianGeoPolygon, 7, 0, &numHexagons)); + &primeMeridianGeoPolygon, 7, CENTER_CONTAINMENT, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &primeMeridianGeoPolygon, 7, 0, hexagons)); + &primeMeridianGeoPolygon, 7, CENTER_CONTAINMENT, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == expectedSize, @@ -319,11 +361,11 @@ SUITE(polygonToCells) { // differences in hex size and grid offset between the two cases expectedSize = 4238; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &transMeridianGeoPolygon, 7, 0, &numHexagons)); + &transMeridianGeoPolygon, 7, CENTER_CONTAINMENT, &numHexagons)); H3Index *hexagonsTM = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &transMeridianGeoPolygon, 7, 0, hexagonsTM)); + &transMeridianGeoPolygon, 7, CENTER_CONTAINMENT, hexagonsTM)); actualNumIndexes = countNonNullIndexes(hexagonsTM, numHexagons); t_assert(actualNumIndexes == expectedSize, @@ -332,21 +374,23 @@ SUITE(polygonToCells) { // Transmeridian filled hole case -- only needed for calculating hole // size t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &transMeridianFilledHoleGeoPolygon, 7, 0, &numHexagons)); + &transMeridianFilledHoleGeoPolygon, 7, CENTER_CONTAINMENT, + &numHexagons)); H3Index *hexagonsTMFH = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &transMeridianFilledHoleGeoPolygon, 7, 0, hexagonsTMFH)); + &transMeridianFilledHoleGeoPolygon, 7, CENTER_CONTAINMENT, + hexagonsTMFH)); int64_t actualNumHoleIndexes = countNonNullIndexes(hexagonsTMFH, numHexagons); // Transmeridian hole case t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &transMeridianHoleGeoPolygon, 7, 0, &numHexagons)); + &transMeridianHoleGeoPolygon, 7, CENTER_CONTAINMENT, &numHexagons)); H3Index *hexagonsTMH = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &transMeridianHoleGeoPolygon, 7, 0, hexagonsTMH)); + &transMeridianHoleGeoPolygon, 7, CENTER_CONTAINMENT, hexagonsTMH)); actualNumIndexes = countNonNullIndexes(hexagonsTMH, numHexagons); t_assert(actualNumIndexes == expectedSize - actualNumHoleIndexes, @@ -369,12 +413,12 @@ SUITE(polygonToCells) { GeoPolygon polygon = {.geoloop = geoloop, .numHoles = 0}; int64_t numHexagons; - t_assertSuccess( - H3_EXPORT(maxPolygonToCellsSize)(&polygon, 4, 0, &numHexagons)); + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( + &polygon, 4, CENTER_CONTAINMENT, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); - t_assertSuccess( - H3_EXPORT(polygonToCellsExperimental)(&polygon, 4, 0, hexagons)); + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &polygon, 4, CENTER_CONTAINMENT, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); @@ -421,12 +465,12 @@ SUITE(polygonToCells) { polygon.numHoles = 0; int64_t numHexagons; - t_assertSuccess( - H3_EXPORT(maxPolygonToCellsSize)(&polygon, 9, 0, &numHexagons)); + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( + &polygon, 9, CENTER_CONTAINMENT, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); - t_assertSuccess( - H3_EXPORT(polygonToCellsExperimental)(&polygon, 9, 0, hexagons)); + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &polygon, 9, CENTER_CONTAINMENT, hexagons)); int found = 0; int numPentagons = 0; @@ -452,8 +496,8 @@ SUITE(polygonToCells) { "Flags other than polyfill modes are invalid for " "maxPolygonToCellsSize"); } - t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)(&sfGeoPolygon, 9, 0, - &numHexagons)); + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( + &sfGeoPolygon, 9, CENTER_CONTAINMENT, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); for (uint32_t flags = 3; flags <= 32; flags++) { t_assert(H3_EXPORT(polygonToCellsExperimental)( diff --git a/src/apps/testapps/testPolygonToCellsReportedExperimental.c b/src/apps/testapps/testPolygonToCellsReportedExperimental.c index 58e6885045..54aee41361 100644 --- a/src/apps/testapps/testPolygonToCellsReportedExperimental.c +++ b/src/apps/testapps/testPolygonToCellsReportedExperimental.c @@ -21,6 +21,7 @@ #include "h3Index.h" #include "latLng.h" #include "polyfill.h" +#include "polygon.h" #include "test.h" #include "utility.h" @@ -42,23 +43,26 @@ SUITE(polygonToCells_reported) { for (int res = 0; res < 3; res++) { int64_t polygonToCellsSize; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &worldGeoPolygon, res, 0, &polygonToCellsSize)); + &worldGeoPolygon, res, CENTER_CONTAINMENT, + &polygonToCellsSize)); H3Index *polygonToCellsOut = calloc(polygonToCellsSize, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &worldGeoPolygon, res, 0, polygonToCellsOut)); + &worldGeoPolygon, res, CENTER_CONTAINMENT, polygonToCellsOut)); int64_t actualNumIndexes = countNonNullIndexes(polygonToCellsOut, polygonToCellsSize); int64_t polygonToCellsSize2; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &worldGeoPolygon2, res, 0, &polygonToCellsSize2)); + &worldGeoPolygon2, res, CENTER_CONTAINMENT, + &polygonToCellsSize2)); H3Index *polygonToCellsOut2 = calloc(polygonToCellsSize2, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &worldGeoPolygon2, res, 0, polygonToCellsOut2)); + &worldGeoPolygon2, res, CENTER_CONTAINMENT, + polygonToCellsOut2)); int64_t actualNumIndexes2 = countNonNullIndexes(polygonToCellsOut2, polygonToCellsSize2); @@ -105,12 +109,12 @@ SUITE(polygonToCells_reported) { int res = 7; int64_t numHexagons; - t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)(&testPolygon, res, 0, - &numHexagons)); + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( + &testPolygon, res, CENTER_CONTAINMENT, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); - t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)(&testPolygon, res, - 0, hexagons)); + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &testPolygon, res, CENTER_CONTAINMENT, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 4499, @@ -134,12 +138,12 @@ SUITE(polygonToCells_reported) { int res = 7; int64_t numHexagons; - t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)(&testPolygon, res, 0, - &numHexagons)); + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( + &testPolygon, res, CENTER_CONTAINMENT, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); - t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)(&testPolygon, res, - 0, hexagons)); + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &testPolygon, res, CENTER_CONTAINMENT, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 4609, @@ -160,12 +164,12 @@ SUITE(polygonToCells_reported) { int res = 13; int64_t numHexagons; - t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)(&testPolygon, res, 0, - &numHexagons)); + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( + &testPolygon, res, CENTER_CONTAINMENT, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); - t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)(&testPolygon, res, - 0, hexagons)); + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &testPolygon, res, CENTER_CONTAINMENT, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 4353, "got expected polygonToCells size"); @@ -193,12 +197,12 @@ SUITE(polygonToCells_reported) { int res = 5; int64_t numHexagons; - t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)(&testPolygon, res, 0, - &numHexagons)); + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( + &testPolygon, res, CENTER_CONTAINMENT, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); - t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)(&testPolygon, res, - 0, hexagons)); + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &testPolygon, res, CENTER_CONTAINMENT, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 8, "got expected polygonToCells size"); diff --git a/src/h3lib/include/polygon.h b/src/h3lib/include/polygon.h index 3fce0c6929..3a07e6f7ee 100644 --- a/src/h3lib/include/polygon.h +++ b/src/h3lib/include/polygon.h @@ -47,7 +47,8 @@ typedef enum { CENTER_CONTAINMENT = 0, FULL_CONTAINMENT = 1, - INTERSECTION = 2 + OVERLAPPING = 2, + INVALID_CONTAINMENT = 3 } ContainmentMode; // 1s in the 4 bits defining the polyfill containment mode, 0s elsewhere @@ -62,11 +63,15 @@ bool pointInsidePolygon(const GeoPolygon *geoPolygon, const BBox *bboxes, bool cellBoundaryInsidePolygon(const GeoPolygon *geoPolygon, const BBox *bboxes, const CellBoundary *boundary, const BBox *boundaryBBox); +bool cellBoundaryCrossesPolygon(const GeoPolygon *geoPolygon, + const BBox *bboxes, + const CellBoundary *boundary, + const BBox *boundaryBBox); bool cellBoundaryCrossesGeoLoop(const GeoLoop *geoloop, const BBox *loopBBox, const CellBoundary *boundary, const BBox *boundaryBBox); -bool lineIntersectsLine(const LatLng *a1, const LatLng *a2, const LatLng *b1, - const LatLng *b2); +bool lineCrossesLine(const LatLng *a1, const LatLng *a2, const LatLng *b1, + const LatLng *b2); // The following functions are created via macro in polygonAlgos.h, // so their signatures are documented here: diff --git a/src/h3lib/lib/polyfill.c b/src/h3lib/lib/polyfill.c index 6411f6972d..8a957f9f6c 100644 --- a/src/h3lib/lib/polyfill.c +++ b/src/h3lib/lib/polyfill.c @@ -414,7 +414,7 @@ void iterStepPolygonCompact(IterCellsPolygonCompact *iter) { // Target res: Do a fine-grained check if (cellRes == iter->_res) { - if (mode == CENTER_CONTAINMENT) { + if (mode == CENTER_CONTAINMENT || mode == OVERLAPPING) { // Check if the cell center is inside the polygon LatLng center; H3Error centerErr = H3_EXPORT(cellToLatLng)(cell, ¢er); @@ -428,8 +428,8 @@ void iterStepPolygonCompact(IterCellsPolygonCompact *iter) { iter->cell = cell; return; } - } else if (mode == FULL_CONTAINMENT) { - // Check if the cell is fully contained by the polygon + } + if (mode == FULL_CONTAINMENT || mode == OVERLAPPING) { CellBoundary boundary; H3Error boundaryErr = H3_EXPORT(cellToBoundary)(cell, &boundary); @@ -443,12 +443,24 @@ void iterStepPolygonCompact(IterCellsPolygonCompact *iter) { iterErrorPolygonCompact(iter, bboxErr); return; } - if (cellBoundaryInsidePolygon(iter->_polygon, iter->_bboxes, + // Check if the cell is fully contained by the polygon + if (mode == FULL_CONTAINMENT && + cellBoundaryInsidePolygon(iter->_polygon, iter->_bboxes, &boundary, &bbox)) { // Set to next output iter->cell = cell; return; } + // For overlap, we've already checked for center point inclusion + // above; if that failed, we only need to check for line + // intersection + else if (mode == OVERLAPPING && + cellBoundaryCrossesPolygon( + iter->_polygon, iter->_bboxes, &boundary, &bbox)) { + // Set to next output + iter->cell = cell; + return; + } } } diff --git a/src/h3lib/lib/polygon.c b/src/h3lib/lib/polygon.c index e1ec4a37dc..3685d0b7a1 100644 --- a/src/h3lib/lib/polygon.c +++ b/src/h3lib/lib/polygon.c @@ -50,8 +50,7 @@ */ H3Error validatePolygonFlags(uint32_t flags) { if (flags & (~FLAG_CONTAINMENT_MODE_MASK) || - !(FLAG_GET_CONTAINMENT_MODE(flags) == CENTER_CONTAINMENT || - FLAG_GET_CONTAINMENT_MODE(flags) == FULL_CONTAINMENT)) { + FLAG_GET_CONTAINMENT_MODE(flags) >= INVALID_CONTAINMENT) { return E_OPTION_INVALID; } return E_SUCCESS; @@ -130,6 +129,33 @@ bool cellBoundaryInsidePolygon(const GeoPolygon *geoPolygon, const BBox *bboxes, return true; } +/** + * Whether any part of a cell boundary crosses a polygon. Crossing in this case + * means whether any line segments intersect; it does not include containment. + * @param geoPolygon The polygon to test + * @param bboxes The bboxes for the main geoloop and each of its holes + * @param boundary The cell boundary to test + * @return Whether the cell boundary is contained + */ +bool cellBoundaryCrossesPolygon(const GeoPolygon *geoPolygon, + const BBox *bboxes, + const CellBoundary *boundary, + const BBox *boundaryBBox) { + // Check for line intersections with outer loop + if (cellBoundaryCrossesGeoLoop(&(geoPolygon->geoloop), &bboxes[0], boundary, + boundaryBBox)) { + return true; + } + // Check for line intersections with any hole + for (int i = 0; i < geoPolygon->numHoles; i++) { + if (cellBoundaryCrossesGeoLoop(&(geoPolygon->holes[i]), &bboxes[i + 1], + boundary, boundaryBBox)) { + return true; + } + } + return false; +} + /** * Whether a cell boundary crosses a geo loop. Crossing in this case means * whether any line segments intersect; it does not include containment. @@ -182,7 +208,7 @@ bool cellBoundaryCrossesGeoLoop(const GeoLoop *geoloop, const BBox *loopBBox, } for (int j = 0; j < normalBoundary.numVerts; j++) { - if (lineIntersectsLine( + if (lineCrossesLine( &loop1, &loop2, &normalBoundary.verts[j], &normalBoundary.verts[(j + 1) % normalBoundary.numVerts])) { return true; @@ -202,8 +228,8 @@ bool cellBoundaryCrossesGeoLoop(const GeoLoop *geoloop, const BBox *loopBBox, * @param b2 End of line B * @return Whether the lines intersect */ -bool lineIntersectsLine(const LatLng *a1, const LatLng *a2, const LatLng *b1, - const LatLng *b2) { +bool lineCrossesLine(const LatLng *a1, const LatLng *a2, const LatLng *b1, + const LatLng *b2) { double denom = ((b2->lng - b1->lng) * (a2->lat - a1->lat) - (b2->lat - b1->lat) * (a2->lng - a1->lng)); if (!denom) return false; From 585f4974bd85a840746e9d030fc8ecaa9a0de6af Mon Sep 17 00:00:00 2001 From: Nick Rabinowitz Date: Mon, 6 Nov 2023 10:25:46 -0800 Subject: [PATCH 04/37] Rename containment enum values --- scripts/make_countries.js | 8 +-- .../benchmarkPolygonToCellsExperimental.c | 12 ++-- src/apps/testapps/testH3Memory.c | 6 +- .../testapps/testPolygonToCellsExperimental.c | 66 +++++++++---------- .../testPolygonToCellsReportedExperimental.c | 24 +++---- src/h3lib/include/polygon.h | 8 +-- src/h3lib/lib/polyfill.c | 8 +-- src/h3lib/lib/polygon.c | 2 +- 8 files changed, 67 insertions(+), 67 deletions(-) diff --git a/scripts/make_countries.js b/scripts/make_countries.js index 42c0a39746..8e810dff3b 100644 --- a/scripts/make_countries.js +++ b/scripts/make_countries.js @@ -150,25 +150,25 @@ for (int res = 0; res < MAX_RES + 1; res++) { BENCHMARK(polygonToCells_AllCountries1, 5, { for (int index = 0; index < ${polygons.length}; index++) { - H3_EXPORT(polygonToCells)(&COUNTRIES[index], res, CENTER_CONTAINMENT, hexagons); + H3_EXPORT(polygonToCells)(&COUNTRIES[index], res, CONTAINMENT_CENTER, hexagons); } }); BENCHMARK(polygonToCells_AllCountries2, 5, { for (int index = 0; index < ${polygons.length}; index++) { - H3_EXPORT(polygonToCellsExperimental)(&COUNTRIES[index], res, CENTER_CONTAINMENT, hexagons); + H3_EXPORT(polygonToCellsExperimental)(&COUNTRIES[index], res, CONTAINMENT_CENTER, hexagons); } }); BENCHMARK(polygonToCells_AllCountries3, 5, { for (int index = 0; index < ${polygons.length}; index++) { - H3_EXPORT(polygonToCellsExperimental)(&COUNTRIES[index], res, FULL_CONTAINMENT, hexagons); + H3_EXPORT(polygonToCellsExperimental)(&COUNTRIES[index], res, CONTAINMENT_FULL, hexagons); } }); BENCHMARK(polygonToCells_AllCountries4, 5, { for (int index = 0; index < ${polygons.length}; index++) { - H3_EXPORT(polygonToCellsExperimental)(&COUNTRIES[index], res, OVERLAPPING, hexagons); + H3_EXPORT(polygonToCellsExperimental)(&COUNTRIES[index], res, CONTAINMENT_OVERLAPPING, hexagons); } }); diff --git a/src/apps/benchmarks/benchmarkPolygonToCellsExperimental.c b/src/apps/benchmarks/benchmarkPolygonToCellsExperimental.c index 13c01cebdc..b475cd7834 100644 --- a/src/apps/benchmarks/benchmarkPolygonToCellsExperimental.c +++ b/src/apps/benchmarks/benchmarkPolygonToCellsExperimental.c @@ -125,28 +125,28 @@ H3Index *hexagons; BENCHMARK(polygonToCellsSF, 500, { H3_EXPORT(maxPolygonToCellsSize) - (&sfGeoPolygon, 9, CENTER_CONTAINMENT, &numHexagons); + (&sfGeoPolygon, 9, CONTAINMENT_CENTER, &numHexagons); hexagons = calloc(numHexagons, sizeof(H3Index)); H3_EXPORT(polygonToCellsExperimental) - (&sfGeoPolygon, 9, CENTER_CONTAINMENT, hexagons); + (&sfGeoPolygon, 9, CONTAINMENT_CENTER, hexagons); free(hexagons); }); BENCHMARK(polygonToCellsAlameda, 500, { H3_EXPORT(maxPolygonToCellsSize) - (&alamedaGeoPolygon, 9, CENTER_CONTAINMENT, &numHexagons); + (&alamedaGeoPolygon, 9, CONTAINMENT_CENTER, &numHexagons); hexagons = calloc(numHexagons, sizeof(H3Index)); H3_EXPORT(polygonToCellsExperimental) - (&alamedaGeoPolygon, 9, CENTER_CONTAINMENT, hexagons); + (&alamedaGeoPolygon, 9, CONTAINMENT_CENTER, hexagons); free(hexagons); }); BENCHMARK(polygonToCellsSouthernExpansion, 10, { H3_EXPORT(maxPolygonToCellsSize) - (&southernGeoPolygon, 9, CENTER_CONTAINMENT, &numHexagons); + (&southernGeoPolygon, 9, CONTAINMENT_CENTER, &numHexagons); hexagons = calloc(numHexagons, sizeof(H3Index)); H3_EXPORT(polygonToCellsExperimental) - (&southernGeoPolygon, 9, CENTER_CONTAINMENT, hexagons); + (&southernGeoPolygon, 9, CONTAINMENT_CENTER, hexagons); free(hexagons); }); diff --git a/src/apps/testapps/testH3Memory.c b/src/apps/testapps/testH3Memory.c index f4e9ec4afc..54a7c688e6 100644 --- a/src/apps/testapps/testH3Memory.c +++ b/src/apps/testapps/testH3Memory.c @@ -232,13 +232,13 @@ SUITE(h3Memory) { int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &sfGeoPolygon, 9, CENTER_CONTAINMENT, &numHexagons)); + &sfGeoPolygon, 9, CONTAINMENT_CENTER, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); resetMemoryCounters(0); failAlloc = true; H3Error err = H3_EXPORT(polygonToCellsExperimental)( - &sfGeoPolygon, 9, CENTER_CONTAINMENT, hexagons); + &sfGeoPolygon, 9, CONTAINMENT_CENTER, hexagons); t_assert(err == E_MEMORY_ALLOC, "polygonToCellsExperimental failed (1)"); t_assert(actualAllocCalls == 1, "alloc called once"); @@ -246,7 +246,7 @@ SUITE(h3Memory) { resetMemoryCounters(1); err = H3_EXPORT(polygonToCellsExperimental)( - &sfGeoPolygon, 9, CENTER_CONTAINMENT, hexagons); + &sfGeoPolygon, 9, CONTAINMENT_CENTER, hexagons); t_assert(err == E_SUCCESS, "polygonToCellsExperimental succeeded (1)"); t_assert(actualAllocCalls == 1, "alloc called one time"); t_assert(actualFreeCalls == 1, "free called one time"); diff --git a/src/apps/testapps/testPolygonToCellsExperimental.c b/src/apps/testapps/testPolygonToCellsExperimental.c index 1435c8d511..cf359a4ce3 100644 --- a/src/apps/testapps/testPolygonToCellsExperimental.c +++ b/src/apps/testapps/testPolygonToCellsExperimental.c @@ -100,7 +100,7 @@ static void fillIndex_assertions(H3Index h) { H3Index *polygonToCellsOut = calloc(polygonToCellsSize, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &polygon, nextRes, CENTER_CONTAINMENT, polygonToCellsOut)); + &polygon, nextRes, CONTAINMENT_CENTER, polygonToCellsOut)); int64_t polygonToCellsCount = countNonNullIndexes(polygonToCellsOut, polygonToCellsSize); @@ -162,11 +162,11 @@ SUITE(polygonToCells) { TEST(polygonToCells) { int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &sfGeoPolygon, 9, CENTER_CONTAINMENT, &numHexagons)); + &sfGeoPolygon, 9, CONTAINMENT_CENTER, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &sfGeoPolygon, 9, CENTER_CONTAINMENT, hexagons)); + &sfGeoPolygon, 9, CONTAINMENT_CENTER, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 1253, "got expected polygonToCells size"); @@ -176,11 +176,11 @@ SUITE(polygonToCells) { TEST(polygonToCellsFullContainment) { int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &sfGeoPolygon, 9, FULL_CONTAINMENT, &numHexagons)); + &sfGeoPolygon, 9, CONTAINMENT_FULL, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &sfGeoPolygon, 9, FULL_CONTAINMENT, hexagons)); + &sfGeoPolygon, 9, CONTAINMENT_FULL, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 1175, @@ -191,11 +191,11 @@ SUITE(polygonToCells) { TEST(polygonToCellsOverlapping) { int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &sfGeoPolygon, 9, OVERLAPPING, &numHexagons)); + &sfGeoPolygon, 9, CONTAINMENT_OVERLAPPING, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &sfGeoPolygon, 9, OVERLAPPING, hexagons)); + &sfGeoPolygon, 9, CONTAINMENT_OVERLAPPING, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 1334, @@ -206,11 +206,11 @@ SUITE(polygonToCells) { TEST(polygonToCellsHole) { int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &holeGeoPolygon, 9, CENTER_CONTAINMENT, &numHexagons)); + &holeGeoPolygon, 9, CONTAINMENT_CENTER, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &holeGeoPolygon, 9, CENTER_CONTAINMENT, hexagons)); + &holeGeoPolygon, 9, CONTAINMENT_CENTER, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 1214, @@ -221,11 +221,11 @@ SUITE(polygonToCells) { TEST(polygonToCellsHoleFullContainment) { int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &holeGeoPolygon, 9, FULL_CONTAINMENT, &numHexagons)); + &holeGeoPolygon, 9, CONTAINMENT_FULL, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &holeGeoPolygon, 9, FULL_CONTAINMENT, hexagons)); + &holeGeoPolygon, 9, CONTAINMENT_FULL, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert( @@ -237,11 +237,11 @@ SUITE(polygonToCells) { TEST(polygonToCellsHoleOverlapping) { int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &holeGeoPolygon, 9, OVERLAPPING, &numHexagons)); + &holeGeoPolygon, 9, CONTAINMENT_OVERLAPPING, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &holeGeoPolygon, 9, OVERLAPPING, hexagons)); + &holeGeoPolygon, 9, CONTAINMENT_OVERLAPPING, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 1311, @@ -252,11 +252,11 @@ SUITE(polygonToCells) { TEST(polygonToCellsEmpty) { int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &emptyGeoPolygon, 9, CENTER_CONTAINMENT, &numHexagons)); + &emptyGeoPolygon, 9, CONTAINMENT_CENTER, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &emptyGeoPolygon, 9, CENTER_CONTAINMENT, hexagons)); + &emptyGeoPolygon, 9, CONTAINMENT_CENTER, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 0, @@ -286,25 +286,25 @@ SUITE(polygonToCells) { int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &someHexagon, 9, CENTER_CONTAINMENT, &numHexagons)); + &someHexagon, 9, CONTAINMENT_CENTER, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); int64_t actualNumIndexes; t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &someHexagon, 9, CENTER_CONTAINMENT, hexagons)); + &someHexagon, 9, CONTAINMENT_CENTER, hexagons)); actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 1, "got expected polygonToCells size for center containment (1)"); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &someHexagon, 9, FULL_CONTAINMENT, hexagons)); + &someHexagon, 9, CONTAINMENT_FULL, hexagons)); actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 1, "got expected polygonToCells size for full containment (1)"); - // TODO: OVERLAPPING yields 7 cells, presumably due to FPE in the - // various cell boundaries + // TODO: CONTAINMENT_OVERLAPPING yields 7 cells, presumably due to FPE + // in the various cell boundaries free(hexagons); free(verts); @@ -346,11 +346,11 @@ SUITE(polygonToCells) { expectedSize = 4228; int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &primeMeridianGeoPolygon, 7, CENTER_CONTAINMENT, &numHexagons)); + &primeMeridianGeoPolygon, 7, CONTAINMENT_CENTER, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &primeMeridianGeoPolygon, 7, CENTER_CONTAINMENT, hexagons)); + &primeMeridianGeoPolygon, 7, CONTAINMENT_CENTER, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == expectedSize, @@ -361,11 +361,11 @@ SUITE(polygonToCells) { // differences in hex size and grid offset between the two cases expectedSize = 4238; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &transMeridianGeoPolygon, 7, CENTER_CONTAINMENT, &numHexagons)); + &transMeridianGeoPolygon, 7, CONTAINMENT_CENTER, &numHexagons)); H3Index *hexagonsTM = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &transMeridianGeoPolygon, 7, CENTER_CONTAINMENT, hexagonsTM)); + &transMeridianGeoPolygon, 7, CONTAINMENT_CENTER, hexagonsTM)); actualNumIndexes = countNonNullIndexes(hexagonsTM, numHexagons); t_assert(actualNumIndexes == expectedSize, @@ -374,23 +374,23 @@ SUITE(polygonToCells) { // Transmeridian filled hole case -- only needed for calculating hole // size t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &transMeridianFilledHoleGeoPolygon, 7, CENTER_CONTAINMENT, + &transMeridianFilledHoleGeoPolygon, 7, CONTAINMENT_CENTER, &numHexagons)); H3Index *hexagonsTMFH = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &transMeridianFilledHoleGeoPolygon, 7, CENTER_CONTAINMENT, + &transMeridianFilledHoleGeoPolygon, 7, CONTAINMENT_CENTER, hexagonsTMFH)); int64_t actualNumHoleIndexes = countNonNullIndexes(hexagonsTMFH, numHexagons); // Transmeridian hole case t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &transMeridianHoleGeoPolygon, 7, CENTER_CONTAINMENT, &numHexagons)); + &transMeridianHoleGeoPolygon, 7, CONTAINMENT_CENTER, &numHexagons)); H3Index *hexagonsTMH = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &transMeridianHoleGeoPolygon, 7, CENTER_CONTAINMENT, hexagonsTMH)); + &transMeridianHoleGeoPolygon, 7, CONTAINMENT_CENTER, hexagonsTMH)); actualNumIndexes = countNonNullIndexes(hexagonsTMH, numHexagons); t_assert(actualNumIndexes == expectedSize - actualNumHoleIndexes, @@ -414,11 +414,11 @@ SUITE(polygonToCells) { int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &polygon, 4, CENTER_CONTAINMENT, &numHexagons)); + &polygon, 4, CONTAINMENT_CENTER, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &polygon, 4, CENTER_CONTAINMENT, hexagons)); + &polygon, 4, CONTAINMENT_CENTER, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); @@ -466,11 +466,11 @@ SUITE(polygonToCells) { int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &polygon, 9, CENTER_CONTAINMENT, &numHexagons)); + &polygon, 9, CONTAINMENT_CENTER, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &polygon, 9, CENTER_CONTAINMENT, hexagons)); + &polygon, 9, CONTAINMENT_CENTER, hexagons)); int found = 0; int numPentagons = 0; @@ -497,7 +497,7 @@ SUITE(polygonToCells) { "maxPolygonToCellsSize"); } t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &sfGeoPolygon, 9, CENTER_CONTAINMENT, &numHexagons)); + &sfGeoPolygon, 9, CONTAINMENT_CENTER, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); for (uint32_t flags = 3; flags <= 32; flags++) { t_assert(H3_EXPORT(polygonToCellsExperimental)( diff --git a/src/apps/testapps/testPolygonToCellsReportedExperimental.c b/src/apps/testapps/testPolygonToCellsReportedExperimental.c index 54aee41361..b3fe8e5b83 100644 --- a/src/apps/testapps/testPolygonToCellsReportedExperimental.c +++ b/src/apps/testapps/testPolygonToCellsReportedExperimental.c @@ -43,25 +43,25 @@ SUITE(polygonToCells_reported) { for (int res = 0; res < 3; res++) { int64_t polygonToCellsSize; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &worldGeoPolygon, res, CENTER_CONTAINMENT, + &worldGeoPolygon, res, CONTAINMENT_CENTER, &polygonToCellsSize)); H3Index *polygonToCellsOut = calloc(polygonToCellsSize, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &worldGeoPolygon, res, CENTER_CONTAINMENT, polygonToCellsOut)); + &worldGeoPolygon, res, CONTAINMENT_CENTER, polygonToCellsOut)); int64_t actualNumIndexes = countNonNullIndexes(polygonToCellsOut, polygonToCellsSize); int64_t polygonToCellsSize2; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &worldGeoPolygon2, res, CENTER_CONTAINMENT, + &worldGeoPolygon2, res, CONTAINMENT_CENTER, &polygonToCellsSize2)); H3Index *polygonToCellsOut2 = calloc(polygonToCellsSize2, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &worldGeoPolygon2, res, CENTER_CONTAINMENT, + &worldGeoPolygon2, res, CONTAINMENT_CENTER, polygonToCellsOut2)); int64_t actualNumIndexes2 = countNonNullIndexes(polygonToCellsOut2, polygonToCellsSize2); @@ -110,11 +110,11 @@ SUITE(polygonToCells_reported) { int res = 7; int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &testPolygon, res, CENTER_CONTAINMENT, &numHexagons)); + &testPolygon, res, CONTAINMENT_CENTER, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &testPolygon, res, CENTER_CONTAINMENT, hexagons)); + &testPolygon, res, CONTAINMENT_CENTER, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 4499, @@ -139,11 +139,11 @@ SUITE(polygonToCells_reported) { int res = 7; int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &testPolygon, res, CENTER_CONTAINMENT, &numHexagons)); + &testPolygon, res, CONTAINMENT_CENTER, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &testPolygon, res, CENTER_CONTAINMENT, hexagons)); + &testPolygon, res, CONTAINMENT_CENTER, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 4609, @@ -165,11 +165,11 @@ SUITE(polygonToCells_reported) { int res = 13; int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &testPolygon, res, CENTER_CONTAINMENT, &numHexagons)); + &testPolygon, res, CONTAINMENT_CENTER, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &testPolygon, res, CENTER_CONTAINMENT, hexagons)); + &testPolygon, res, CONTAINMENT_CENTER, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 4353, "got expected polygonToCells size"); @@ -198,11 +198,11 @@ SUITE(polygonToCells_reported) { int res = 5; int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( - &testPolygon, res, CENTER_CONTAINMENT, &numHexagons)); + &testPolygon, res, CONTAINMENT_CENTER, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &testPolygon, res, CENTER_CONTAINMENT, hexagons)); + &testPolygon, res, CONTAINMENT_CENTER, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 8, "got expected polygonToCells size"); diff --git a/src/h3lib/include/polygon.h b/src/h3lib/include/polygon.h index 3a07e6f7ee..d7d24ffbcc 100644 --- a/src/h3lib/include/polygon.h +++ b/src/h3lib/include/polygon.h @@ -45,10 +45,10 @@ * the `flags` bit field. */ typedef enum { - CENTER_CONTAINMENT = 0, - FULL_CONTAINMENT = 1, - OVERLAPPING = 2, - INVALID_CONTAINMENT = 3 + CONTAINMENT_CENTER = 0, ///< Cell center is contained in the shape + CONTAINMENT_FULL = 1, ///< Cell is fully contained in the shape + CONTAINMENT_OVERLAPPING = 2, ///< Cell overlaps the shape at any point + CONTAINMENT_INVALID = 3 ///< This mode is invalid and should not be used } ContainmentMode; // 1s in the 4 bits defining the polyfill containment mode, 0s elsewhere diff --git a/src/h3lib/lib/polyfill.c b/src/h3lib/lib/polyfill.c index 8a957f9f6c..4e23c2b94f 100644 --- a/src/h3lib/lib/polyfill.c +++ b/src/h3lib/lib/polyfill.c @@ -414,7 +414,7 @@ void iterStepPolygonCompact(IterCellsPolygonCompact *iter) { // Target res: Do a fine-grained check if (cellRes == iter->_res) { - if (mode == CENTER_CONTAINMENT || mode == OVERLAPPING) { + if (mode == CONTAINMENT_CENTER || mode == CONTAINMENT_OVERLAPPING) { // Check if the cell center is inside the polygon LatLng center; H3Error centerErr = H3_EXPORT(cellToLatLng)(cell, ¢er); @@ -429,7 +429,7 @@ void iterStepPolygonCompact(IterCellsPolygonCompact *iter) { return; } } - if (mode == FULL_CONTAINMENT || mode == OVERLAPPING) { + if (mode == CONTAINMENT_FULL || mode == CONTAINMENT_OVERLAPPING) { CellBoundary boundary; H3Error boundaryErr = H3_EXPORT(cellToBoundary)(cell, &boundary); @@ -444,7 +444,7 @@ void iterStepPolygonCompact(IterCellsPolygonCompact *iter) { return; } // Check if the cell is fully contained by the polygon - if (mode == FULL_CONTAINMENT && + if (mode == CONTAINMENT_FULL && cellBoundaryInsidePolygon(iter->_polygon, iter->_bboxes, &boundary, &bbox)) { // Set to next output @@ -454,7 +454,7 @@ void iterStepPolygonCompact(IterCellsPolygonCompact *iter) { // For overlap, we've already checked for center point inclusion // above; if that failed, we only need to check for line // intersection - else if (mode == OVERLAPPING && + else if (mode == CONTAINMENT_OVERLAPPING && cellBoundaryCrossesPolygon( iter->_polygon, iter->_bboxes, &boundary, &bbox)) { // Set to next output diff --git a/src/h3lib/lib/polygon.c b/src/h3lib/lib/polygon.c index 3685d0b7a1..1944e5bda7 100644 --- a/src/h3lib/lib/polygon.c +++ b/src/h3lib/lib/polygon.c @@ -50,7 +50,7 @@ */ H3Error validatePolygonFlags(uint32_t flags) { if (flags & (~FLAG_CONTAINMENT_MODE_MASK) || - FLAG_GET_CONTAINMENT_MODE(flags) >= INVALID_CONTAINMENT) { + FLAG_GET_CONTAINMENT_MODE(flags) >= CONTAINMENT_INVALID) { return E_OPTION_INVALID; } return E_SUCCESS; From 1a446270955dda27cccaa261980578f40c7cf9bf Mon Sep 17 00:00:00 2001 From: Nick Rabinowitz Date: Tue, 7 Nov 2023 17:48:01 -0800 Subject: [PATCH 05/37] Fix and test for case where OVERLAPPING cell contains polygon --- .../benchmarkPolygonToCellsExperimental.c | 60 ++++++++++++++- .../testapps/testPolygonToCellsExperimental.c | 75 ++++++++++++++++++- src/h3lib/lib/polyfill.c | 18 +++++ 3 files changed, 148 insertions(+), 5 deletions(-) diff --git a/src/apps/benchmarks/benchmarkPolygonToCellsExperimental.c b/src/apps/benchmarks/benchmarkPolygonToCellsExperimental.c index b475cd7834..1034f33724 100644 --- a/src/apps/benchmarks/benchmarkPolygonToCellsExperimental.c +++ b/src/apps/benchmarks/benchmarkPolygonToCellsExperimental.c @@ -123,7 +123,7 @@ southernGeoPolygon.geoloop = southernGeoLoop; int64_t numHexagons; H3Index *hexagons; -BENCHMARK(polygonToCellsSF, 500, { +BENCHMARK(polygonToCellsSF_Center, 500, { H3_EXPORT(maxPolygonToCellsSize) (&sfGeoPolygon, 9, CONTAINMENT_CENTER, &numHexagons); hexagons = calloc(numHexagons, sizeof(H3Index)); @@ -132,7 +132,25 @@ BENCHMARK(polygonToCellsSF, 500, { free(hexagons); }); -BENCHMARK(polygonToCellsAlameda, 500, { +BENCHMARK(polygonToCellsSF_Full, 500, { + H3_EXPORT(maxPolygonToCellsSize) + (&sfGeoPolygon, 9, CONTAINMENT_FULL, &numHexagons); + hexagons = calloc(numHexagons, sizeof(H3Index)); + H3_EXPORT(polygonToCellsExperimental) + (&sfGeoPolygon, 9, CONTAINMENT_FULL, hexagons); + free(hexagons); +}); + +BENCHMARK(polygonToCellsSF_Overlapping, 500, { + H3_EXPORT(maxPolygonToCellsSize) + (&sfGeoPolygon, 9, CONTAINMENT_OVERLAPPING, &numHexagons); + hexagons = calloc(numHexagons, sizeof(H3Index)); + H3_EXPORT(polygonToCellsExperimental) + (&sfGeoPolygon, 9, CONTAINMENT_OVERLAPPING, hexagons); + free(hexagons); +}); + +BENCHMARK(polygonToCellsAlameda_Center, 500, { H3_EXPORT(maxPolygonToCellsSize) (&alamedaGeoPolygon, 9, CONTAINMENT_CENTER, &numHexagons); hexagons = calloc(numHexagons, sizeof(H3Index)); @@ -141,7 +159,25 @@ BENCHMARK(polygonToCellsAlameda, 500, { free(hexagons); }); -BENCHMARK(polygonToCellsSouthernExpansion, 10, { +BENCHMARK(polygonToCellsAlameda_Full, 500, { + H3_EXPORT(maxPolygonToCellsSize) + (&alamedaGeoPolygon, 9, CONTAINMENT_FULL, &numHexagons); + hexagons = calloc(numHexagons, sizeof(H3Index)); + H3_EXPORT(polygonToCellsExperimental) + (&alamedaGeoPolygon, 9, CONTAINMENT_FULL, hexagons); + free(hexagons); +}); + +BENCHMARK(polygonToCellsAlameda_Overlapping, 500, { + H3_EXPORT(maxPolygonToCellsSize) + (&alamedaGeoPolygon, 9, CONTAINMENT_OVERLAPPING, &numHexagons); + hexagons = calloc(numHexagons, sizeof(H3Index)); + H3_EXPORT(polygonToCellsExperimental) + (&alamedaGeoPolygon, 9, CONTAINMENT_OVERLAPPING, hexagons); + free(hexagons); +}); + +BENCHMARK(polygonToCellsSouthernExpansion_Center, 10, { H3_EXPORT(maxPolygonToCellsSize) (&southernGeoPolygon, 9, CONTAINMENT_CENTER, &numHexagons); hexagons = calloc(numHexagons, sizeof(H3Index)); @@ -150,4 +186,22 @@ BENCHMARK(polygonToCellsSouthernExpansion, 10, { free(hexagons); }); +BENCHMARK(polygonToCellsSouthernExpansion_Full, 10, { + H3_EXPORT(maxPolygonToCellsSize) + (&southernGeoPolygon, 9, CONTAINMENT_FULL, &numHexagons); + hexagons = calloc(numHexagons, sizeof(H3Index)); + H3_EXPORT(polygonToCellsExperimental) + (&southernGeoPolygon, 9, CONTAINMENT_FULL, hexagons); + free(hexagons); +}); + +BENCHMARK(polygonToCellsSouthernExpansion_Overlapping, 10, { + H3_EXPORT(maxPolygonToCellsSize) + (&southernGeoPolygon, 9, CONTAINMENT_OVERLAPPING, &numHexagons); + hexagons = calloc(numHexagons, sizeof(H3Index)); + H3_EXPORT(polygonToCellsExperimental) + (&southernGeoPolygon, 9, CONTAINMENT_OVERLAPPING, hexagons); + free(hexagons); +}); + END_BENCHMARKS(); diff --git a/src/apps/testapps/testPolygonToCellsExperimental.c b/src/apps/testapps/testPolygonToCellsExperimental.c index cf359a4ce3..239a1fb884 100644 --- a/src/apps/testapps/testPolygonToCellsExperimental.c +++ b/src/apps/testapps/testPolygonToCellsExperimental.c @@ -173,7 +173,7 @@ SUITE(polygonToCells) { free(hexagons); } - TEST(polygonToCellsFullContainment) { + TEST(polygonToCells_FullContainment) { int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( &sfGeoPolygon, 9, CONTAINMENT_FULL, &numHexagons)); @@ -188,7 +188,7 @@ SUITE(polygonToCells) { free(hexagons); } - TEST(polygonToCellsOverlapping) { + TEST(polygonToCells_Overlapping) { int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( &sfGeoPolygon, 9, CONTAINMENT_OVERLAPPING, &numHexagons)); @@ -264,6 +264,77 @@ SUITE(polygonToCells) { free(hexagons); } + TEST(polygonToCellsContainsPolygon) { + int64_t numHexagons; + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( + &sfGeoPolygon, 4, CONTAINMENT_CENTER, &numHexagons)); + H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); + + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &sfGeoPolygon, 4, CONTAINMENT_CENTER, hexagons)); + int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); + + t_assert(actualNumIndexes == 0, "got expected polygonToCells size"); + free(hexagons); + } + + TEST(polygonToCellsContainsPolygon_CenterContained) { + // Contains the center point of a res 4 cell + static LatLng centerVerts[] = {{0.6595645, -2.1353315}, + {0.6595645, -2.1353314}, + {0.6595644, -2.1353314}, + {0.6595644, -2.1353314265}}; + static GeoLoop centerGeoLoop = {.numVerts = 6, .verts = centerVerts}; + static GeoPolygon centerGeoPolygon; + centerGeoPolygon.geoloop = centerGeoLoop; + centerGeoPolygon.numHoles = 0; + + int64_t numHexagons; + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( + ¢erGeoPolygon, 4, CONTAINMENT_CENTER, &numHexagons)); + H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); + + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + ¢erGeoPolygon, 4, CONTAINMENT_CENTER, hexagons)); + int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); + + t_assert(actualNumIndexes == 1, "got expected polygonToCells size"); + t_assert(hexagons[0] == 0x8428309ffffffff, "got expected hexagon"); + + free(hexagons); + } + + TEST(polygonToCellsContainsPolygon_FullContainment) { + int64_t numHexagons; + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( + &sfGeoPolygon, 4, CONTAINMENT_FULL, &numHexagons)); + H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); + + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &sfGeoPolygon, 4, CONTAINMENT_FULL, hexagons)); + int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); + + t_assert(actualNumIndexes == 0, + "got expected polygonToCells size (full containment mode)"); + free(hexagons); + } + + TEST(polygonToCellsContainsPolygon_Overlapping) { + int64_t numHexagons; + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSize)( + &sfGeoPolygon, 4, CONTAINMENT_OVERLAPPING, &numHexagons)); + H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); + + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &sfGeoPolygon, 4, CONTAINMENT_OVERLAPPING, hexagons)); + int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); + + t_assert(actualNumIndexes == 1, + "got expected polygonToCells size (overlapping mode)"); + t_assert(hexagons[0] == 0x8428309ffffffff, "got expected hexagon"); + free(hexagons); + } + TEST(polygonToCellsExact) { LatLng somewhere = {1, 2}; H3Index origin; diff --git a/src/h3lib/lib/polyfill.c b/src/h3lib/lib/polyfill.c index 4e23c2b94f..f62d568069 100644 --- a/src/h3lib/lib/polyfill.c +++ b/src/h3lib/lib/polyfill.c @@ -429,6 +429,24 @@ void iterStepPolygonCompact(IterCellsPolygonCompact *iter) { return; } } + if (mode == CONTAINMENT_OVERLAPPING) { + // For overlapping, we need to do a quick check to determine + // whether the polygon is wholly contained by the cell. We check + // the first polygon vertex, which if it is contained could also + // mean we simply intersect. + H3Index polygonCell; + H3Error polygonCellErr = H3_EXPORT(latLngToCell)( + &(iter->_polygon->geoloop.verts[0]), cellRes, &polygonCell); + if (polygonCellErr != E_SUCCESS) { + iterErrorPolygonCompact(iter, polygonCellErr); + return; + } + if (polygonCell == cell) { + // Set to next output + iter->cell = cell; + return; + } + } if (mode == CONTAINMENT_FULL || mode == CONTAINMENT_OVERLAPPING) { CellBoundary boundary; H3Error boundaryErr = From edaa901b55fc872a660109f37014f44398ea6e0f Mon Sep 17 00:00:00 2001 From: Nick Rabinowitz Date: Tue, 7 Nov 2023 18:39:33 -0800 Subject: [PATCH 06/37] Possibly fix test --- src/apps/testapps/testPolygonToCellsExperimental.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) diff --git a/src/apps/testapps/testPolygonToCellsExperimental.c b/src/apps/testapps/testPolygonToCellsExperimental.c index 239a1fb884..06f2408241 100644 --- a/src/apps/testapps/testPolygonToCellsExperimental.c +++ b/src/apps/testapps/testPolygonToCellsExperimental.c @@ -280,12 +280,12 @@ SUITE(polygonToCells) { TEST(polygonToCellsContainsPolygon_CenterContained) { // Contains the center point of a res 4 cell - static LatLng centerVerts[] = {{0.6595645, -2.1353315}, - {0.6595645, -2.1353314}, - {0.6595644, -2.1353314}, - {0.6595644, -2.1353314265}}; - static GeoLoop centerGeoLoop = {.numVerts = 6, .verts = centerVerts}; - static GeoPolygon centerGeoPolygon; + LatLng centerVerts[] = {{0.6595645, -2.1353315}, + {0.6595645, -2.1353314}, + {0.6595644, -2.1353314}, + {0.6595644, -2.1353314265}}; + GeoLoop centerGeoLoop = {.numVerts = 6, .verts = centerVerts}; + GeoPolygon centerGeoPolygon; centerGeoPolygon.geoloop = centerGeoLoop; centerGeoPolygon.numHoles = 0; From fedaa5f897a40e4b53a5e42c7e1d203b25ce024f Mon Sep 17 00:00:00 2001 From: Nick Rabinowitz Date: Tue, 7 Nov 2023 22:46:42 -0800 Subject: [PATCH 07/37] Fixture fix --- src/apps/testapps/testPolygonToCellsExperimental.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/apps/testapps/testPolygonToCellsExperimental.c b/src/apps/testapps/testPolygonToCellsExperimental.c index 06f2408241..24464597dc 100644 --- a/src/apps/testapps/testPolygonToCellsExperimental.c +++ b/src/apps/testapps/testPolygonToCellsExperimental.c @@ -284,7 +284,7 @@ SUITE(polygonToCells) { {0.6595645, -2.1353314}, {0.6595644, -2.1353314}, {0.6595644, -2.1353314265}}; - GeoLoop centerGeoLoop = {.numVerts = 6, .verts = centerVerts}; + GeoLoop centerGeoLoop = {.numVerts = 4, .verts = centerVerts}; GeoPolygon centerGeoPolygon; centerGeoPolygon.geoloop = centerGeoLoop; centerGeoPolygon.numHoles = 0; From b3eb114480c108ce20b816d1fe850e3e0f302872 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Wed, 15 Nov 2023 16:56:20 -0800 Subject: [PATCH 08/37] add polygonToCellsExperimental fuzzers --- CMakeLists.txt | 4 + src/apps/fuzzers/README.md | 7 +- src/apps/fuzzers/fuzzerPolygonToCells.c | 18 +-- .../fuzzerPolygonToCellsExperimental.c | 105 ++++++++++++++++++ .../fuzzerPolygonToCellsExperimentalNoHoles.c | 63 +++++++++++ .../fuzzers/fuzzerPolygonToCellsNoHoles.c | 6 +- 6 files changed, 191 insertions(+), 12 deletions(-) create mode 100644 src/apps/fuzzers/fuzzerPolygonToCellsExperimental.c create mode 100644 src/apps/fuzzers/fuzzerPolygonToCellsExperimentalNoHoles.c diff --git a/CMakeLists.txt b/CMakeLists.txt index 4c90917a1d..87fbbca367 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -272,7 +272,9 @@ set(OTHER_SOURCE_FILES src/apps/fuzzers/fuzzerDirectedEdge.c src/apps/fuzzers/fuzzerLocalIj.c src/apps/fuzzers/fuzzerPolygonToCells.c + src/apps/fuzzers/fuzzerPolygonToCellsExperimental.c src/apps/fuzzers/fuzzerPolygonToCellsNoHoles.c + src/apps/fuzzers/fuzzerPolygonToCellsExperimentalNoHoles.c src/apps/fuzzers/fuzzerCellToChildPos.c src/apps/fuzzers/fuzzerInternalAlgos.c src/apps/fuzzers/fuzzerInternalCoordIjk.c @@ -547,7 +549,9 @@ if(BUILD_FUZZERS) add_h3_fuzzer(fuzzerDirectedEdge src/apps/fuzzers/fuzzerDirectedEdge.c) add_h3_fuzzer(fuzzerLocalIj src/apps/fuzzers/fuzzerLocalIj.c) add_h3_fuzzer(fuzzerPolygonToCells src/apps/fuzzers/fuzzerPolygonToCells.c) + add_h3_fuzzer(fuzzerPolygonToCellsExperimental src/apps/fuzzers/fuzzerPolygonToCellsExperimental.c) add_h3_fuzzer(fuzzerPolygonToCellsNoHoles src/apps/fuzzers/fuzzerPolygonToCellsNoHoles.c) + add_h3_fuzzer(fuzzerPolygonToCellsExperimentalNoHoles src/apps/fuzzers/fuzzerPolygonToCellsExperimentalNoHoles.c) add_h3_fuzzer(fuzzerCellToChildPos src/apps/fuzzers/fuzzerCellToChildPos.c) if(ENABLE_REQUIRES_ALL_SYMBOLS) add_h3_fuzzer(fuzzerInternalAlgos src/apps/fuzzers/fuzzerInternalAlgos.c) diff --git a/src/apps/fuzzers/README.md b/src/apps/fuzzers/README.md index 392c9c206d..a0e386e713 100644 --- a/src/apps/fuzzers/README.md +++ b/src/apps/fuzzers/README.md @@ -11,8 +11,8 @@ such as the H3 core library. The public API of H3 is covered in the following fuzzers: -| Function | File or status -| -------- | -------------- +| Function | File +| -------- | ---- | latLngToCell | [fuzzerLatLngToCell](./fuzzerLatLngToCell.c) | cellToLatLng | [fuzzerCellToLatLng](./fuzzerCellToLatLng.c) | cellToBoundary | [fuzzerCellToLatLng](./fuzzerCellToLatLng.c) @@ -20,7 +20,8 @@ The public API of H3 is covered in the following fuzzers: | gridDiskDistances | [fuzzerGridDisk](./fuzzerGridDisk.c) | gridRingUnsafe | [fuzzerGridDisk](./fuzzerGridDisk.c) | gridDisksUnsafe | [fuzzerGridDisk](./fuzzerGridDisk.c) -| polygonToCells | [fuzzerPoylgonToCells](./fuzzerPolygonToCells.c) +| polygonToCells | [fuzzerPoylgonToCells](./fuzzerPolygonToCells.c) [fuzzerPoylgonToCellsNoHoles](./fuzzerPolygonToCellsNoHoles.c) +| polygonToCellsExperimental | [fuzzerPoylgonToCellsExperimental](./fuzzerPolygonToCellsExperimental.c) [fuzzerPoylgonToCellsExperimentalNoHoles](./fuzzerPolygonToCellsExperimentalNoHoles.c) | h3SetToMultiPolygon | [fuzzerH3SetToLinkedGeo](./fuzzerH3SetToLinkedGeo.c) | degsToRads | Trivial | radsToDegs | Trivial diff --git a/src/apps/fuzzers/fuzzerPolygonToCells.c b/src/apps/fuzzers/fuzzerPolygonToCells.c index 2c5333f9a0..84463037bc 100644 --- a/src/apps/fuzzers/fuzzerPolygonToCells.c +++ b/src/apps/fuzzers/fuzzerPolygonToCells.c @@ -1,5 +1,5 @@ /* - * Copyright 2022 Uber Technologies, Inc. + * Copyright 2023 Uber Technologies, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -14,11 +14,12 @@ * limitations under the License. */ /** @file - * @brief Fuzzer program for polygonToCells and related functions + * @brief Fuzzer program for polygonToCellsExperimental and related functions */ #include "aflHarness.h" #include "h3api.h" +#include "polygon.h" #include "utility.h" typedef struct { @@ -71,7 +72,8 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { int res = args->res % (MAX_RES + 1); GeoPolygon geoPolygon; - geoPolygon.numHoles = args->numHoles % MAX_HOLES; + int originalNumHoles = args->numHoles % MAX_HOLES; + geoPolygon.numHoles = originalNumHoles; if (geoPolygon.numHoles < 0) { return 0; } @@ -88,10 +90,12 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { } } - // TODO: Fuzz the `flags` input as well when it has meaningful input - run(&geoPolygon, 0, res); - geoPolygon.numHoles = 0; - run(&geoPolygon, 0, res); + for (uint32_t flags = 0; flags < CONTAINMENT_INVALID; flags++) { + geoPolygon.numHoles = originalNumHoles; + run(&geoPolygon, 0, res); + geoPolygon.numHoles = 0; + run(&geoPolygon, 0, res); + } free(geoPolygon.holes); return 0; diff --git a/src/apps/fuzzers/fuzzerPolygonToCellsExperimental.c b/src/apps/fuzzers/fuzzerPolygonToCellsExperimental.c new file mode 100644 index 0000000000..109f34baab --- /dev/null +++ b/src/apps/fuzzers/fuzzerPolygonToCellsExperimental.c @@ -0,0 +1,105 @@ +/* + * Copyright 2023 Uber Technologies, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/** @file + * @brief Fuzzer program for polygonToCells2 and related functions + */ + +#include "aflHarness.h" +#include "h3api.h" +#include "polyfill.h" +#include "polygon.h" +#include "utility.h" + +typedef struct { + int res; + int numHoles; + // repeating: num verts, verts + // We add a large fixed buffer so our test case generator for AFL + // knows how large to make the file. + uint8_t buffer[1024]; +} inputArgs; + +const int MAX_RES = 15; +const int MAX_SZ = 4000000; +const int MAX_HOLES = 100; + +int populateGeoLoop(GeoLoop *g, const uint8_t *data, size_t *offset, + size_t size) { + if (size < *offset + sizeof(int)) { + return 1; + } + int numVerts = *(const int *)(data + *offset); + *offset = *offset + sizeof(int); + g->numVerts = numVerts; + if (size < *offset + sizeof(LatLng) * numVerts) { + return 1; + } + g->verts = (LatLng *)(data + *offset); + *offset = *offset + sizeof(LatLng) * numVerts; + return 0; +} + +void run(GeoPolygon *geoPolygon, uint32_t flags, int res) { + int64_t sz; + H3Error err = H3_EXPORT(maxPolygonToCellsSize)(geoPolygon, res, flags, &sz); + if (!err && sz < MAX_SZ) { + H3Index *out = calloc(sz, sizeof(H3Index)); + H3_EXPORT(polygonToCellsExperimental)(geoPolygon, res, flags, out); + free(out); + } +} + +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { + // TODO: It is difficult for the fuzzer to generate inputs that are + // considered valid by this fuzzer. fuzzerPolygonToCellsNoHoles.c + // is a workaround for that. + if (size < sizeof(inputArgs)) { + return 0; + } + const inputArgs *args = (const inputArgs *)data; + int res = args->res % (MAX_RES + 1); + + GeoPolygon geoPolygon; + int originalNumHoles = args->numHoles % MAX_HOLES; + geoPolygon.numHoles = originalNumHoles; + if (geoPolygon.numHoles < 0) { + return 0; + } + geoPolygon.holes = calloc(geoPolygon.numHoles, sizeof(GeoLoop)); + size_t offset = sizeof(inputArgs) - sizeof(args->buffer); + if (populateGeoLoop(&geoPolygon.geoloop, data, &offset, size)) { + free(geoPolygon.holes); + return 0; + } + for (int i = 0; i < geoPolygon.numHoles; i++) { + if (populateGeoLoop(&geoPolygon.holes[i], data, &offset, size)) { + free(geoPolygon.holes); + return 0; + } + } + + for (uint32_t flags = 0; flags < CONTAINMENT_INVALID; flags++) { + geoPolygon.numHoles = originalNumHoles; + run(&geoPolygon, flags, res); + geoPolygon.numHoles = 0; + run(&geoPolygon, flags, res); + } + free(geoPolygon.holes); + + return 0; +} + +AFL_HARNESS_MAIN(sizeof(inputArgs)); diff --git a/src/apps/fuzzers/fuzzerPolygonToCellsExperimentalNoHoles.c b/src/apps/fuzzers/fuzzerPolygonToCellsExperimentalNoHoles.c new file mode 100644 index 0000000000..0649887adc --- /dev/null +++ b/src/apps/fuzzers/fuzzerPolygonToCellsExperimentalNoHoles.c @@ -0,0 +1,63 @@ +/* + * Copyright 2023 Uber Technologies, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/** @file + * @brief Fuzzer program for polygonToCellsExperimental and related functions, + * without holes + */ + +#include "aflHarness.h" +#include "h3api.h" +#include "polyfill.h" +#include "polygon.h" +#include "utility.h" + +const int MAX_RES = 15; +const int MAX_SZ = 4000000; + +void run(GeoPolygon *geoPolygon, uint32_t flags, int res) { + int64_t sz; + H3Error err = H3_EXPORT(maxPolygonToCellsSize)(geoPolygon, res, flags, &sz); + if (!err && sz < MAX_SZ) { + H3Index *out = calloc(sz, sizeof(H3Index)); + H3_EXPORT(polygonToCellsExperimental)(geoPolygon, res, flags, out); + free(out); + } +} + +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { + if (size < sizeof(int)) { + return 0; + } + + uint8_t res = *data; + size_t vertsSize = size - 1; + int numVerts = vertsSize / sizeof(LatLng); + + GeoPolygon geoPolygon; + geoPolygon.numHoles = 0; + geoPolygon.holes = NULL; + geoPolygon.geoloop.numVerts = numVerts; + // Offset by 1 since *data was used for `res`, above. + geoPolygon.geoloop.verts = (LatLng *)(data + 1); + + for (uint32_t flags = 0; flags < CONTAINMENT_INVALID; flags++) { + run(&geoPolygon, flags, res); + } + + return 0; +} + +AFL_HARNESS_MAIN(sizeof(H3Index) * 1024); diff --git a/src/apps/fuzzers/fuzzerPolygonToCellsNoHoles.c b/src/apps/fuzzers/fuzzerPolygonToCellsNoHoles.c index 72558b51ec..546c6eb46b 100644 --- a/src/apps/fuzzers/fuzzerPolygonToCellsNoHoles.c +++ b/src/apps/fuzzers/fuzzerPolygonToCellsNoHoles.c @@ -19,6 +19,7 @@ #include "aflHarness.h" #include "h3api.h" +#include "polygon.h" #include "utility.h" const int MAX_RES = 15; @@ -50,8 +51,9 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { // Offset by 1 since *data was used for `res`, above. geoPolygon.geoloop.verts = (LatLng *)(data + 1); - // TODO: Fuzz the `flags` input as well when it has meaningful input - run(&geoPolygon, 0, res); + for (uint32_t flags = 0; flags < CONTAINMENT_INVALID; flags++) { + run(&geoPolygon, 0, res); + } return 0; } From a2adc0467f71465c2a0db989f2f82ac9ae7e3066 Mon Sep 17 00:00:00 2001 From: Nick Rabinowitz Date: Sat, 25 Nov 2023 08:49:05 -0800 Subject: [PATCH 09/37] Additional test coverage for error cases --- src/apps/testapps/testPolyfillInternal.c | 62 +++++++++++++++++++++--- 1 file changed, 55 insertions(+), 7 deletions(-) diff --git a/src/apps/testapps/testPolyfillInternal.c b/src/apps/testapps/testPolyfillInternal.c index db393cc30b..75a2b55f48 100644 --- a/src/apps/testapps/testPolyfillInternal.c +++ b/src/apps/testapps/testPolyfillInternal.c @@ -14,11 +14,14 @@ * limitations under the License. */ +#include + #include "bbox.h" #include "h3Index.h" #include "h3api.h" #include "latLng.h" #include "polyfill.h" +#include "polygon.h" #include "test.h" #include "utility.h" @@ -33,16 +36,24 @@ static GeoPolygon sfGeoPolygon = { {0.6599990002976, -2.1376771158464}}}, .numHoles = 0}; +static GeoPolygon invalidGeoPolygon = { + .geoloop = {.numVerts = 4, + .verts = (LatLng[]){{NAN, -2.1364398519396}, + {0.6595011102219, NAN}, + {NAN, -2.1354884206045}, + {0.6581220034068, NAN}}}, + .numHoles = 0}; + SUITE(polyfillInternal) { TEST(iterInitPolygonCompact_errors) { IterCellsPolygonCompact iter; - iter = iterInitPolygonCompact(&sfGeoPolygon, -1, 0); + iter = iterInitPolygonCompact(&sfGeoPolygon, -1, CONTAINMENT_CENTER); t_assert(iter.error == E_RES_DOMAIN, "Got expected error for invalid res"); t_assert(iter.cell == H3_NULL, "Got null output for invalid res"); - iter = iterInitPolygonCompact(&sfGeoPolygon, 16, 0); + iter = iterInitPolygonCompact(&sfGeoPolygon, 16, CONTAINMENT_CENTER); t_assert(iter.error == E_RES_DOMAIN, "Got expected error for invalid res"); t_assert(iter.cell == H3_NULL, "Got null output for invalid res"); @@ -53,11 +64,12 @@ SUITE(polyfillInternal) { t_assert(iter.cell == H3_NULL, "Got null output for invalid flags"); } - TEST(iterStepPolygonCompact_errors) { + TEST(iterStepPolygonCompact_invalidCellErrors) { IterCellsPolygonCompact iter; H3Index cell; - iter = iterInitPolygonCompact(&sfGeoPolygon, 9, 0); + iter = iterInitPolygonCompact(&sfGeoPolygon, 9, CONTAINMENT_CENTER); + t_assertSuccess(iter.error); // Give the iterator a cell with a bad base cell cell = 0x85283473fffffff; @@ -69,7 +81,22 @@ SUITE(polyfillInternal) { "Got expected error for invalid cell"); t_assert(iter.cell == H3_NULL, "Got null output for invalid cell"); - iter = iterInitPolygonCompact(&sfGeoPolygon, 9, 0); + iter = iterInitPolygonCompact(&sfGeoPolygon, 9, CONTAINMENT_CENTER); + t_assertSuccess(iter.error); + + // Give the iterator a cell with a bad base cell, at the target res + cell = 0x89283470003ffff; + H3_SET_BASE_CELL(cell, 123); + iter.cell = cell; + + iterStepPolygonCompact(&iter); + t_assert(iter.error == E_CELL_INVALID, + "Got expected error for invalid cell"); + t_assert(iter.cell == H3_NULL, + "Got null output for invalid cell at res"); + + iter = iterInitPolygonCompact(&sfGeoPolygon, 9, CONTAINMENT_CENTER); + t_assertSuccess(iter.error); // Give the iterator a cell that's too fine for a child check, // and a target resolution that allows this to run. This cell has @@ -84,9 +111,28 @@ SUITE(polyfillInternal) { t_assert(iter.cell == H3_NULL, "Got null output for invalid cell"); } + TEST(iterStepPolygonCompact_invalidPolygonErrors) { + IterCellsPolygonCompact iter; + + // Start with a good polygon, otherwise we error out early + iter = + iterInitPolygonCompact(&sfGeoPolygon, 5, CONTAINMENT_OVERLAPPING); + t_assertSuccess(iter.error); + + // Give the iterator a bad polygon and a cell at target res + iter._polygon = &invalidGeoPolygon; + iter.cell = 0x85283473fffffff; + + iterStepPolygonCompact(&iter); + t_assert(iter.error == E_LATLNG_DOMAIN, + "Got expected error for invalid polygon"); + t_assert(iter.cell == H3_NULL, "Got null output for invalid cell"); + } + TEST(iterDestroyPolygonCompact) { IterCellsPolygonCompact iter = - iterInitPolygonCompact(&sfGeoPolygon, 9, 0); + iterInitPolygonCompact(&sfGeoPolygon, 9, CONTAINMENT_CENTER); + t_assertSuccess(iter.error); iterDestroyPolygonCompact(&iter); t_assert(iter.error == E_SUCCESS, "Got success for destroyed iterator"); @@ -101,7 +147,9 @@ SUITE(polyfillInternal) { } TEST(iterDestroyPolygon) { - IterCellsPolygon iter = iterInitPolygon(&sfGeoPolygon, 9, 0); + IterCellsPolygon iter = + iterInitPolygon(&sfGeoPolygon, 9, CONTAINMENT_CENTER); + t_assertSuccess(iter.error); iterDestroyPolygon(&iter); t_assert(iter.error == E_SUCCESS, "Got success for destroyed iterator"); From f0f1b45adff09a01f09c9fc29fc6e9e0f7c1cf56 Mon Sep 17 00:00:00 2001 From: Nick Rabinowitz Date: Sat, 25 Nov 2023 14:45:02 -0800 Subject: [PATCH 10/37] Test coverage for one more error, excluding unreachable block from coverage --- src/apps/testapps/testPolyfillInternal.c | 15 +++++++++++++++ src/h3lib/lib/polyfill.c | 4 +++- 2 files changed, 18 insertions(+), 1 deletion(-) diff --git a/src/apps/testapps/testPolyfillInternal.c b/src/apps/testapps/testPolyfillInternal.c index 75a2b55f48..4e44255ad1 100644 --- a/src/apps/testapps/testPolyfillInternal.c +++ b/src/apps/testapps/testPolyfillInternal.c @@ -89,6 +89,21 @@ SUITE(polyfillInternal) { H3_SET_BASE_CELL(cell, 123); iter.cell = cell; + iterStepPolygonCompact(&iter); + t_assert(iter.error == E_CELL_INVALID, + "Got expected error for invalid cell"); + t_assert(iter.cell == H3_NULL, + "Got null output for invalid cell at res"); + + iter = iterInitPolygonCompact(&sfGeoPolygon, 9, CONTAINMENT_FULL); + t_assertSuccess(iter.error); + + // Give the iterator a cell with a bad base cell, at the target res + // (full containment) + cell = 0x89283470003ffff; + H3_SET_BASE_CELL(cell, 123); + iter.cell = cell; + iterStepPolygonCompact(&iter); t_assert(iter.error == E_CELL_INVALID, "Got expected error for invalid cell"); diff --git a/src/h3lib/lib/polyfill.c b/src/h3lib/lib/polyfill.c index f62d568069..bde5eedbcb 100644 --- a/src/h3lib/lib/polyfill.c +++ b/src/h3lib/lib/polyfill.c @@ -457,7 +457,9 @@ void iterStepPolygonCompact(IterCellsPolygonCompact *iter) { } BBox bbox; H3Error bboxErr = cellToBBox(cell, &bbox, false); - if (bboxErr) { + if (NEVER(bboxErr != E_SUCCESS)) { + // Should be unreachable - invalid cells would be caught in + // the previous boundaryErr iterErrorPolygonCompact(iter, bboxErr); return; } From 4226e437f00e90d9e55e6d3a51b27a28717945a0 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 26 Nov 2023 08:27:03 -0800 Subject: [PATCH 11/37] fix fuzzer comment --- src/apps/fuzzers/fuzzerPolygonToCells.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/src/apps/fuzzers/fuzzerPolygonToCells.c b/src/apps/fuzzers/fuzzerPolygonToCells.c index 84463037bc..cc6b77da06 100644 --- a/src/apps/fuzzers/fuzzerPolygonToCells.c +++ b/src/apps/fuzzers/fuzzerPolygonToCells.c @@ -1,5 +1,5 @@ /* - * Copyright 2023 Uber Technologies, Inc. + * Copyright 2022-2023 Uber Technologies, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -14,7 +14,7 @@ * limitations under the License. */ /** @file - * @brief Fuzzer program for polygonToCellsExperimental and related functions + * @brief Fuzzer program for polygonToCells and related functions */ #include "aflHarness.h" From b055cd5af149ce164dcfe36eb5a99cf4927eb1d5 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Mon, 4 Dec 2023 12:01:10 -0800 Subject: [PATCH 12/37] fix size estimation --- src/apps/fuzzers/fuzzerPolygonToCellsExperimental.c | 3 ++- src/apps/fuzzers/fuzzerPolygonToCellsExperimentalNoHoles.c | 3 ++- 2 files changed, 4 insertions(+), 2 deletions(-) diff --git a/src/apps/fuzzers/fuzzerPolygonToCellsExperimental.c b/src/apps/fuzzers/fuzzerPolygonToCellsExperimental.c index 109f34baab..23a9b43fae 100644 --- a/src/apps/fuzzers/fuzzerPolygonToCellsExperimental.c +++ b/src/apps/fuzzers/fuzzerPolygonToCellsExperimental.c @@ -54,7 +54,8 @@ int populateGeoLoop(GeoLoop *g, const uint8_t *data, size_t *offset, void run(GeoPolygon *geoPolygon, uint32_t flags, int res) { int64_t sz; - H3Error err = H3_EXPORT(maxPolygonToCellsSize)(geoPolygon, res, flags, &sz); + H3Error err = H3_EXPORT(maxPolygonToCellsSizeExperimental)(geoPolygon, res, + flags, &sz); if (!err && sz < MAX_SZ) { H3Index *out = calloc(sz, sizeof(H3Index)); H3_EXPORT(polygonToCellsExperimental)(geoPolygon, res, flags, out); diff --git a/src/apps/fuzzers/fuzzerPolygonToCellsExperimentalNoHoles.c b/src/apps/fuzzers/fuzzerPolygonToCellsExperimentalNoHoles.c index 0649887adc..eca247d5e4 100644 --- a/src/apps/fuzzers/fuzzerPolygonToCellsExperimentalNoHoles.c +++ b/src/apps/fuzzers/fuzzerPolygonToCellsExperimentalNoHoles.c @@ -29,7 +29,8 @@ const int MAX_SZ = 4000000; void run(GeoPolygon *geoPolygon, uint32_t flags, int res) { int64_t sz; - H3Error err = H3_EXPORT(maxPolygonToCellsSize)(geoPolygon, res, flags, &sz); + H3Error err = H3_EXPORT(maxPolygonToCellsSizeExperimental)(geoPolygon, res, + flags, &sz); if (!err && sz < MAX_SZ) { H3Index *out = calloc(sz, sizeof(H3Index)); H3_EXPORT(polygonToCellsExperimental)(geoPolygon, res, flags, out); From 629c65481c7b0cd464586540a51b003d1519d6e0 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Thu, 14 Dec 2023 16:50:20 -0800 Subject: [PATCH 13/37] add test --- .../testapps/testPolygonToCellsExperimental.c | 47 ++++++++++++++++++- 1 file changed, 46 insertions(+), 1 deletion(-) diff --git a/src/apps/testapps/testPolygonToCellsExperimental.c b/src/apps/testapps/testPolygonToCellsExperimental.c index 4d48c3c1d6..08ccf745fe 100644 --- a/src/apps/testapps/testPolygonToCellsExperimental.c +++ b/src/apps/testapps/testPolygonToCellsExperimental.c @@ -300,7 +300,52 @@ SUITE(polygonToCells) { int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 0, - "got expected polygonToCells size (empty)"); + "got expected polygonToCells size (empty center)"); + free(hexagons); + } + + TEST(polygonToCellsEmptyContainsOverlapping) { + int64_t numHexagons; + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSizeExperimental)( + &emptyGeoPolygon, 9, CONTAINMENT_OVERLAPPING, &numHexagons)); + H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); + + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &emptyGeoPolygon, 9, CONTAINMENT_OVERLAPPING, hexagons)); + int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); + + t_assert(actualNumIndexes == 0, + "got expected polygonToCells size (empty overlapping)"); + free(hexagons); + } + + TEST(polygonToCellsEmpty) { + int64_t numHexagons; + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSizeExperimental)( + &emptyGeoPolygon, 9, CONTAINMENT_FULL, &numHexagons)); + H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); + + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &emptyGeoPolygon, 9, CONTAINMENT_FULL, hexagons)); + int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); + + t_assert(actualNumIndexes == 0, + "got expected polygonToCells size (empty full)"); + free(hexagons); + } + + TEST(polygonToCellsEmptyOverlappingBbox) { + int64_t numHexagons; + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSizeExperimental)( + &emptyGeoPolygon, 9, CONTAINMENT_OVERLAPPING_BBOX, &numHexagons)); + H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); + + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &emptyGeoPolygon, 9, CONTAINMENT_OVERLAPPING_BBOX, hexagons)); + int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); + + t_assert(actualNumIndexes == 0, + "got expected polygonToCells size (empty overlapping bbox)"); free(hexagons); } From 641d481b94d0e1980767402211d38af242cb881d Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Thu, 14 Dec 2023 16:57:06 -0800 Subject: [PATCH 14/37] add null test --- .../testapps/testPolygonToCellsExperimental.c | 41 ++++++++++++++----- src/h3lib/lib/polyfill.c | 7 ++++ 2 files changed, 38 insertions(+), 10 deletions(-) diff --git a/src/apps/testapps/testPolygonToCellsExperimental.c b/src/apps/testapps/testPolygonToCellsExperimental.c index 08ccf745fe..a754119cfb 100644 --- a/src/apps/testapps/testPolygonToCellsExperimental.c +++ b/src/apps/testapps/testPolygonToCellsExperimental.c @@ -46,6 +46,9 @@ static LatLng emptyVerts[] = {{0.659966917655, -2.1364398519394}, static GeoLoop emptyGeoLoop = {.numVerts = 3, .verts = emptyVerts}; static GeoPolygon emptyGeoPolygon; +static GeoLoop nullGeoLoop = {.numVerts = 0}; +static GeoPolygon nullGeoPolygon; + static LatLng invalidVerts[] = {{INFINITY, INFINITY}, {-INFINITY, -INFINITY}}; static GeoLoop invalidGeoLoop = {.numVerts = 2, .verts = invalidVerts}; static GeoPolygon invalidGeoPolygon; @@ -147,6 +150,9 @@ SUITE(polygonToCells) { emptyGeoPolygon.geoloop = emptyGeoLoop; emptyGeoPolygon.numHoles = 0; + nullGeoPolygon.geoloop = nullGeoLoop; + nullGeoPolygon.numHoles = 0; + invalidGeoPolygon.geoloop = invalidGeoLoop; invalidGeoPolygon.numHoles = 0; @@ -304,48 +310,63 @@ SUITE(polygonToCells) { free(hexagons); } + TEST(polygonToCellsNull) { + int64_t numHexagons; + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSizeExperimental)( + &nullGeoPolygon, 9, CONTAINMENT_CENTER, &numHexagons)); + H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); + + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &nullGeoPolygon, 9, CONTAINMENT_CENTER, hexagons)); + int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); + + t_assert(actualNumIndexes == 0, + "got expected polygonToCells size (null center)"); + free(hexagons); + } + TEST(polygonToCellsEmptyContainsOverlapping) { int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSizeExperimental)( - &emptyGeoPolygon, 9, CONTAINMENT_OVERLAPPING, &numHexagons)); + &nullGeoPolygon, 9, CONTAINMENT_OVERLAPPING, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &emptyGeoPolygon, 9, CONTAINMENT_OVERLAPPING, hexagons)); + &nullGeoPolygon, 9, CONTAINMENT_OVERLAPPING, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 0, - "got expected polygonToCells size (empty overlapping)"); + "got expected polygonToCells size (null overlapping)"); free(hexagons); } - TEST(polygonToCellsEmpty) { + TEST(polygonToCellsEmptyFull) { int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSizeExperimental)( - &emptyGeoPolygon, 9, CONTAINMENT_FULL, &numHexagons)); + &nullGeoPolygon, 9, CONTAINMENT_FULL, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &emptyGeoPolygon, 9, CONTAINMENT_FULL, hexagons)); + &nullGeoPolygon, 9, CONTAINMENT_FULL, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 0, - "got expected polygonToCells size (empty full)"); + "got expected polygonToCells size (null full)"); free(hexagons); } TEST(polygonToCellsEmptyOverlappingBbox) { int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSizeExperimental)( - &emptyGeoPolygon, 9, CONTAINMENT_OVERLAPPING_BBOX, &numHexagons)); + &nullGeoPolygon, 9, CONTAINMENT_OVERLAPPING_BBOX, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &emptyGeoPolygon, 9, CONTAINMENT_OVERLAPPING_BBOX, hexagons)); + &nullGeoPolygon, 9, CONTAINMENT_OVERLAPPING_BBOX, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 0, - "got expected polygonToCells size (empty overlapping bbox)"); + "got expected polygonToCells size (null overlapping bbox)"); free(hexagons); } diff --git a/src/h3lib/lib/polyfill.c b/src/h3lib/lib/polyfill.c index 688cb1529a..46c9c85a91 100644 --- a/src/h3lib/lib/polyfill.c +++ b/src/h3lib/lib/polyfill.c @@ -418,6 +418,12 @@ void iterStepPolygonCompact(IterCellsPolygonCompact *iter) { iter->_started = true; } + if (iter->_polygon->geoloop.numVerts == 0) { + // Nothing can be returned in this case + iterDestroyPolygonCompact(iter); + return; + } + ContainmentMode mode = FLAG_GET_CONTAINMENT_MODE(iter->_flags); while (cell) { @@ -446,6 +452,7 @@ void iterStepPolygonCompact(IterCellsPolygonCompact *iter) { // the first polygon vertex, which if it is contained could also // mean we simply intersect. H3Index polygonCell; + // Deferencing verts[0] is safe because we check numVerts above H3Error polygonCellErr = H3_EXPORT(latLngToCell)( &(iter->_polygon->geoloop.verts[0]), cellRes, &polygonCell); if (polygonCellErr != E_SUCCESS) { From 7659732b9e1909e1cf71aa566b4bdf0f5e98404c Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Thu, 14 Dec 2023 16:59:35 -0800 Subject: [PATCH 15/37] add TODO --- src/h3lib/lib/polygon.c | 1 + 1 file changed, 1 insertion(+) diff --git a/src/h3lib/lib/polygon.c b/src/h3lib/lib/polygon.c index db20bd17cf..b09721a396 100644 --- a/src/h3lib/lib/polygon.c +++ b/src/h3lib/lib/polygon.c @@ -130,6 +130,7 @@ bool cellBoundaryInsidePolygon(const GeoPolygon *geoPolygon, const BBox *bboxes, // Check for line intersections with, or containment of, any hole for (int i = 0; i < geoPolygon->numHoles; i++) { + // TODO: There may be numVerts = 0 here, which would cause a crash if (pointInsideGeoLoop(&boundaryLoop, boundaryBBox, &geoPolygon->holes[i].verts[0]) || cellBoundaryCrossesGeoLoop(&(geoPolygon->holes[i]), &bboxes[i + 1], From 4f0341cf5b5cf992af5cb8c541ad1d56b9a21a59 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Fri, 15 Dec 2023 10:59:34 -0800 Subject: [PATCH 16/37] guard against numVerts = 0 for hole check --- src/h3lib/lib/polygon.c | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-) diff --git a/src/h3lib/lib/polygon.c b/src/h3lib/lib/polygon.c index b09721a396..18f5b858cf 100644 --- a/src/h3lib/lib/polygon.c +++ b/src/h3lib/lib/polygon.c @@ -130,11 +130,12 @@ bool cellBoundaryInsidePolygon(const GeoPolygon *geoPolygon, const BBox *bboxes, // Check for line intersections with, or containment of, any hole for (int i = 0; i < geoPolygon->numHoles; i++) { - // TODO: There may be numVerts = 0 here, which would cause a crash - if (pointInsideGeoLoop(&boundaryLoop, boundaryBBox, - &geoPolygon->holes[i].verts[0]) || - cellBoundaryCrossesGeoLoop(&(geoPolygon->holes[i]), &bboxes[i + 1], - boundary, boundaryBBox)) { + // If the hole has no verts, it is not possible to intersect with it. + if (geoPolygon->holes[i].numVerts > 0 && + (pointInsideGeoLoop(&boundaryLoop, boundaryBBox, + &geoPolygon->holes[i].verts[0]) || + cellBoundaryCrossesGeoLoop(&(geoPolygon->holes[i]), &bboxes[i + 1], + boundary, boundaryBBox))) { return false; } } From c6a21b82f32117aa879808fba5059ac2c64702a7 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 17 Dec 2023 10:37:48 -0800 Subject: [PATCH 17/37] add empty with null hole test --- .../testapps/testPolygonToCellsExperimental.c | 75 +++++++------------ 1 file changed, 27 insertions(+), 48 deletions(-) diff --git a/src/apps/testapps/testPolygonToCellsExperimental.c b/src/apps/testapps/testPolygonToCellsExperimental.c index a754119cfb..a94274ff8b 100644 --- a/src/apps/testapps/testPolygonToCellsExperimental.c +++ b/src/apps/testapps/testPolygonToCellsExperimental.c @@ -49,6 +49,8 @@ static GeoPolygon emptyGeoPolygon; static GeoLoop nullGeoLoop = {.numVerts = 0}; static GeoPolygon nullGeoPolygon; +static GeoPolygon emptyGeoPolygonWithNullHole; + static LatLng invalidVerts[] = {{INFINITY, INFINITY}, {-INFINITY, -INFINITY}}; static GeoLoop invalidGeoLoop = {.numVerts = 2, .verts = invalidVerts}; static GeoPolygon invalidGeoPolygon; @@ -153,6 +155,10 @@ SUITE(polygonToCells) { nullGeoPolygon.geoloop = nullGeoLoop; nullGeoPolygon.numHoles = 0; + emptyGeoPolygonWithNullHole.geoloop = emptyGeoLoop; + emptyGeoPolygonWithNullHole.numHoles = 1; + emptyGeoPolygonWithNullHole.holes = &nullGeoLoop; + invalidGeoPolygon.geoloop = invalidGeoLoop; invalidGeoPolygon.numHoles = 0; @@ -306,68 +312,41 @@ SUITE(polygonToCells) { int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 0, - "got expected polygonToCells size (empty center)"); - free(hexagons); - } - - TEST(polygonToCellsNull) { - int64_t numHexagons; - t_assertSuccess(H3_EXPORT(maxPolygonToCellsSizeExperimental)( - &nullGeoPolygon, 9, CONTAINMENT_CENTER, &numHexagons)); - H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); - - t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &nullGeoPolygon, 9, CONTAINMENT_CENTER, hexagons)); - int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); - - t_assert(actualNumIndexes == 0, - "got expected polygonToCells size (null center)"); - free(hexagons); - } - - TEST(polygonToCellsEmptyContainsOverlapping) { - int64_t numHexagons; - t_assertSuccess(H3_EXPORT(maxPolygonToCellsSizeExperimental)( - &nullGeoPolygon, 9, CONTAINMENT_OVERLAPPING, &numHexagons)); - H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); - - t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &nullGeoPolygon, 9, CONTAINMENT_OVERLAPPING, hexagons)); - int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); - - t_assert(actualNumIndexes == 0, - "got expected polygonToCells size (null overlapping)"); + "got expected polygonToCells size (empty)"); free(hexagons); } - TEST(polygonToCellsEmptyFull) { + TEST(polygonToCellsEmptyWithNullHole) { int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSizeExperimental)( - &nullGeoPolygon, 9, CONTAINMENT_FULL, &numHexagons)); + &emptyGeoPolygonWithNullHole, 9, CONTAINMENT_CENTER, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &nullGeoPolygon, 9, CONTAINMENT_FULL, hexagons)); + &emptyGeoPolygonWithNullHole, 9, CONTAINMENT_CENTER, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 0, - "got expected polygonToCells size (null full)"); + "got expected polygonToCells size (empty with null hole)"); free(hexagons); } - TEST(polygonToCellsEmptyOverlappingBbox) { - int64_t numHexagons; - t_assertSuccess(H3_EXPORT(maxPolygonToCellsSizeExperimental)( - &nullGeoPolygon, 9, CONTAINMENT_OVERLAPPING_BBOX, &numHexagons)); - H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); - - t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &nullGeoPolygon, 9, CONTAINMENT_OVERLAPPING_BBOX, hexagons)); - int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); - - t_assert(actualNumIndexes == 0, - "got expected polygonToCells size (null overlapping bbox)"); - free(hexagons); + TEST(polygonToCellsNull) { + for (uint32_t flags = 0; flags < CONTAINMENT_INVALID; flags++) { + int64_t numHexagons; + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSizeExperimental)( + &nullGeoPolygon, 9, flags, &numHexagons)); + H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); + + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &nullGeoPolygon, 9, flags, hexagons)); + int64_t actualNumIndexes = + countNonNullIndexes(hexagons, numHexagons); + + t_assert(actualNumIndexes == 0, + "got expected polygonToCells size (null)"); + free(hexagons); + } } TEST(polygonToCellsContainsPolygon) { From 3975ff942017fe946cfa4384ab487f6bb76ba29a Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 17 Dec 2023 10:50:47 -0800 Subject: [PATCH 18/37] update test --- .../testapps/testPolygonToCellsExperimental.c | 37 ++++++++++++++----- 1 file changed, 27 insertions(+), 10 deletions(-) diff --git a/src/apps/testapps/testPolygonToCellsExperimental.c b/src/apps/testapps/testPolygonToCellsExperimental.c index a94274ff8b..717f4a8ade 100644 --- a/src/apps/testapps/testPolygonToCellsExperimental.c +++ b/src/apps/testapps/testPolygonToCellsExperimental.c @@ -317,18 +317,35 @@ SUITE(polygonToCells) { } TEST(polygonToCellsEmptyWithNullHole) { - int64_t numHexagons; - t_assertSuccess(H3_EXPORT(maxPolygonToCellsSizeExperimental)( - &emptyGeoPolygonWithNullHole, 9, CONTAINMENT_CENTER, &numHexagons)); - H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); + for (uint32_t flags = 0; flags < CONTAINMENT_INVALID; flags++) { + // Confirm that the same number of cells are returned with and + // without an empty hole + int64_t numHexagonsWithoutHole; + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSizeExperimental)( + &emptyGeoPolygon, 9, flags, &numHexagonsWithoutHole)); + H3Index *hexagonsWithoutHole = + calloc(numHexagonsWithoutHole, sizeof(H3Index)); - t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &emptyGeoPolygonWithNullHole, 9, CONTAINMENT_CENTER, hexagons)); - int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &emptyGeoPolygon, 9, flags, hexagonsWithoutHole)); + int64_t actualNumIndexesWithoutHole = countNonNullIndexes( + hexagonsWithoutHole, numHexagonsWithoutHole); + free(hexagonsWithoutHole); - t_assert(actualNumIndexes == 0, - "got expected polygonToCells size (empty with null hole)"); - free(hexagons); + int64_t numHexagons; + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSizeExperimental)( + &emptyGeoPolygonWithNullHole, 9, flags, &numHexagons)); + H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); + + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &emptyGeoPolygonWithNullHole, 9, flags, hexagons)); + int64_t actualNumIndexes = + countNonNullIndexes(hexagons, numHexagons); + + t_assert(actualNumIndexes == actualNumIndexesWithoutHole, + "got expected polygonToCells size (empty with null hole)"); + free(hexagons); + } } TEST(polygonToCellsNull) { From cfe8816f9682230996f5675b97db8578d8f52052 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 17 Dec 2023 11:02:43 -0800 Subject: [PATCH 19/37] actually cover --- .../testapps/testPolygonToCellsExperimental.c | 20 +++++++++---------- 1 file changed, 10 insertions(+), 10 deletions(-) diff --git a/src/apps/testapps/testPolygonToCellsExperimental.c b/src/apps/testapps/testPolygonToCellsExperimental.c index 717f4a8ade..988880e958 100644 --- a/src/apps/testapps/testPolygonToCellsExperimental.c +++ b/src/apps/testapps/testPolygonToCellsExperimental.c @@ -49,7 +49,7 @@ static GeoPolygon emptyGeoPolygon; static GeoLoop nullGeoLoop = {.numVerts = 0}; static GeoPolygon nullGeoPolygon; -static GeoPolygon emptyGeoPolygonWithNullHole; +static GeoPolygon sfGeoPolygonWithNullHole; static LatLng invalidVerts[] = {{INFINITY, INFINITY}, {-INFINITY, -INFINITY}}; static GeoLoop invalidGeoLoop = {.numVerts = 2, .verts = invalidVerts}; @@ -155,9 +155,9 @@ SUITE(polygonToCells) { nullGeoPolygon.geoloop = nullGeoLoop; nullGeoPolygon.numHoles = 0; - emptyGeoPolygonWithNullHole.geoloop = emptyGeoLoop; - emptyGeoPolygonWithNullHole.numHoles = 1; - emptyGeoPolygonWithNullHole.holes = &nullGeoLoop; + sfGeoPolygonWithNullHole.geoloop = sfGeoLoop; + sfGeoPolygonWithNullHole.numHoles = 1; + sfGeoPolygonWithNullHole.holes = &nullGeoLoop; invalidGeoPolygon.geoloop = invalidGeoLoop; invalidGeoPolygon.numHoles = 0; @@ -316,34 +316,34 @@ SUITE(polygonToCells) { free(hexagons); } - TEST(polygonToCellsEmptyWithNullHole) { + TEST(polygonToCellssfWithNullHole) { for (uint32_t flags = 0; flags < CONTAINMENT_INVALID; flags++) { // Confirm that the same number of cells are returned with and // without an empty hole int64_t numHexagonsWithoutHole; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSizeExperimental)( - &emptyGeoPolygon, 9, flags, &numHexagonsWithoutHole)); + &sfGeoPolygon, 9, flags, &numHexagonsWithoutHole)); H3Index *hexagonsWithoutHole = calloc(numHexagonsWithoutHole, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &emptyGeoPolygon, 9, flags, hexagonsWithoutHole)); + &sfGeoPolygon, 9, flags, hexagonsWithoutHole)); int64_t actualNumIndexesWithoutHole = countNonNullIndexes( hexagonsWithoutHole, numHexagonsWithoutHole); free(hexagonsWithoutHole); int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSizeExperimental)( - &emptyGeoPolygonWithNullHole, 9, flags, &numHexagons)); + &sfGeoPolygonWithNullHole, 9, flags, &numHexagons)); H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( - &emptyGeoPolygonWithNullHole, 9, flags, hexagons)); + &sfGeoPolygonWithNullHole, 9, flags, hexagons)); int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == actualNumIndexesWithoutHole, - "got expected polygonToCells size (empty with null hole)"); + "got expected polygonToCells size (sf with null hole)"); free(hexagons); } } From 673046900ad0eabaa65bcd66c508047ce24af806 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 28 Jan 2024 11:07:49 -0800 Subject: [PATCH 20/37] add fuzzer derived test case --- .../testapps/testPolygonToCellsExperimental.c | 29 +++++++++++++++++++ 1 file changed, 29 insertions(+) diff --git a/src/apps/testapps/testPolygonToCellsExperimental.c b/src/apps/testapps/testPolygonToCellsExperimental.c index 988880e958..0710f54ed2 100644 --- a/src/apps/testapps/testPolygonToCellsExperimental.c +++ b/src/apps/testapps/testPolygonToCellsExperimental.c @@ -49,6 +49,12 @@ static GeoPolygon emptyGeoPolygon; static GeoLoop nullGeoLoop = {.numVerts = 0}; static GeoPolygon nullGeoPolygon; +static LatLng singleVert[] = { + {-2458342481021883972259660398208400791736363001944288341450980211606536535492675816838520454729626606617401537208948885147545930079455247090683734597891092223711178354749340595418656865312221132096067702544124896034621453367423118181128977366942366333665280.000000, + -2458343740331028994843467164510968055426643495662759512417906485158670133931720348722610840257947672725818463095310525347561848316357826117675135273725409046652087471434926446163500402816566116551621419239229327985229318738203409398420671266791854901821440.000000}}; +static GeoLoop singleVertGeoLoop = {.numVerts = 1, .verts = singleVert}; +static GeoPolygon singleVertGeoPolygon; + static GeoPolygon sfGeoPolygonWithNullHole; static LatLng invalidVerts[] = {{INFINITY, INFINITY}, {-INFINITY, -INFINITY}}; @@ -155,6 +161,9 @@ SUITE(polygonToCells) { nullGeoPolygon.geoloop = nullGeoLoop; nullGeoPolygon.numHoles = 0; + singleVertGeoPolygon.geoloop = singleVertGeoLoop; + singleVertGeoPolygon.numHoles = 0; + sfGeoPolygonWithNullHole.geoloop = sfGeoLoop; sfGeoPolygonWithNullHole.numHoles = 1; sfGeoPolygonWithNullHole.holes = &nullGeoLoop; @@ -366,6 +375,26 @@ SUITE(polygonToCells) { } } + TEST(polygonToCellsSingleVert) { + for (int res = 0; res < MAX_H3_RES; res++) { + for (uint32_t flags = 0; flags < CONTAINMENT_INVALID; flags++) { + int64_t numHexagons; + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSizeExperimental)( + &singleVertGeoPolygon, res, flags, &numHexagons)); + H3Index *hexagons = calloc(numHexagons, sizeof(H3Index)); + + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)( + &singleVertGeoPolygon, res, flags, hexagons)); + int64_t actualNumIndexes = + countNonNullIndexes(hexagons, numHexagons); + + t_assert(actualNumIndexes == 0, + "got expected polygonToCells size (null)"); + free(hexagons); + } + } + } + TEST(polygonToCellsContainsPolygon) { int64_t numHexagons; t_assertSuccess(H3_EXPORT(maxPolygonToCellsSizeExperimental)( From 29a9b01089ba2fb76bd2cee278921ae96c3d300c Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 28 Jan 2024 11:09:52 -0800 Subject: [PATCH 21/37] simplify --- src/apps/testapps/testPolygonToCellsExperimental.c | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) diff --git a/src/apps/testapps/testPolygonToCellsExperimental.c b/src/apps/testapps/testPolygonToCellsExperimental.c index 0710f54ed2..206cf8a82a 100644 --- a/src/apps/testapps/testPolygonToCellsExperimental.c +++ b/src/apps/testapps/testPolygonToCellsExperimental.c @@ -49,9 +49,7 @@ static GeoPolygon emptyGeoPolygon; static GeoLoop nullGeoLoop = {.numVerts = 0}; static GeoPolygon nullGeoPolygon; -static LatLng singleVert[] = { - {-2458342481021883972259660398208400791736363001944288341450980211606536535492675816838520454729626606617401537208948885147545930079455247090683734597891092223711178354749340595418656865312221132096067702544124896034621453367423118181128977366942366333665280.000000, - -2458343740331028994843467164510968055426643495662759512417906485158670133931720348722610840257947672725818463095310525347561848316357826117675135273725409046652087471434926446163500402816566116551621419239229327985229318738203409398420671266791854901821440.000000}}; +static LatLng singleVert[] = {{-10, 0}}; static GeoLoop singleVertGeoLoop = {.numVerts = 1, .verts = singleVert}; static GeoPolygon singleVertGeoPolygon; @@ -65,6 +63,7 @@ static LatLng invalid2Verts[] = {{NAN, NAN}, {-NAN, -NAN}}; static GeoLoop invalid2GeoLoop = {.numVerts = 2, .verts = invalid2Verts}; static GeoPolygon invalid2GeoPolygon; +// TODO: This is unused static LatLng pointVerts[] = {{0, 0}}; static GeoLoop pointGeoLoop = {.numVerts = 1, .verts = pointVerts}; static GeoPolygon pointGeoPolygon; From 85d5641b7aedf4ff9b37c78c9bc163cdcddd6cad Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 28 Jan 2024 11:12:03 -0800 Subject: [PATCH 22/37] year --- src/apps/fuzzers/fuzzerPolygonToCellsExperimental.c | 2 +- src/apps/fuzzers/fuzzerPolygonToCellsExperimentalNoHoles.c | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) diff --git a/src/apps/fuzzers/fuzzerPolygonToCellsExperimental.c b/src/apps/fuzzers/fuzzerPolygonToCellsExperimental.c index 23a9b43fae..1a87dc4a01 100644 --- a/src/apps/fuzzers/fuzzerPolygonToCellsExperimental.c +++ b/src/apps/fuzzers/fuzzerPolygonToCellsExperimental.c @@ -1,5 +1,5 @@ /* - * Copyright 2023 Uber Technologies, Inc. + * Copyright 2023-2024 Uber Technologies, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. diff --git a/src/apps/fuzzers/fuzzerPolygonToCellsExperimentalNoHoles.c b/src/apps/fuzzers/fuzzerPolygonToCellsExperimentalNoHoles.c index eca247d5e4..a507e432c5 100644 --- a/src/apps/fuzzers/fuzzerPolygonToCellsExperimentalNoHoles.c +++ b/src/apps/fuzzers/fuzzerPolygonToCellsExperimentalNoHoles.c @@ -1,5 +1,5 @@ /* - * Copyright 2023 Uber Technologies, Inc. + * Copyright 2023-2024 Uber Technologies, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. From 5ac48c5fa57560fdf9d08aa22a07d1e758fe7293 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 28 Jan 2024 11:14:12 -0800 Subject: [PATCH 23/37] actually pass flags --- src/apps/fuzzers/fuzzerPolygonToCells.c | 2 +- src/apps/fuzzers/fuzzerPolygonToCellsNoHoles.c | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) diff --git a/src/apps/fuzzers/fuzzerPolygonToCells.c b/src/apps/fuzzers/fuzzerPolygonToCells.c index cc6b77da06..84fe863b78 100644 --- a/src/apps/fuzzers/fuzzerPolygonToCells.c +++ b/src/apps/fuzzers/fuzzerPolygonToCells.c @@ -1,5 +1,5 @@ /* - * Copyright 2022-2023 Uber Technologies, Inc. + * Copyright 2022-2024 Uber Technologies, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. diff --git a/src/apps/fuzzers/fuzzerPolygonToCellsNoHoles.c b/src/apps/fuzzers/fuzzerPolygonToCellsNoHoles.c index 546c6eb46b..b4e1d47bfd 100644 --- a/src/apps/fuzzers/fuzzerPolygonToCellsNoHoles.c +++ b/src/apps/fuzzers/fuzzerPolygonToCellsNoHoles.c @@ -52,7 +52,7 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { geoPolygon.geoloop.verts = (LatLng *)(data + 1); for (uint32_t flags = 0; flags < CONTAINMENT_INVALID; flags++) { - run(&geoPolygon, 0, res); + run(&geoPolygon, flags, res); } return 0; From 377777bbd3a4c9fdf40da767e7d73eacfcc71a7e Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 4 Aug 2024 14:33:29 -0700 Subject: [PATCH 24/37] attempted fix --- src/h3lib/include/polygonAlgos.h | 5 +++++ 1 file changed, 5 insertions(+) diff --git a/src/h3lib/include/polygonAlgos.h b/src/h3lib/include/polygonAlgos.h index e6ce98403f..880381a11a 100644 --- a/src/h3lib/include/polygonAlgos.h +++ b/src/h3lib/include/polygonAlgos.h @@ -121,6 +121,11 @@ bool GENERIC_LOOP_ALGO(pointInside)(const TYPE *loop, const BBox *bbox, lng -= DBL_EPSILON; } + // Illegal input, reject. + if (fabs(aLng) > M_2PI || fabs(bLng) > M_2PI) { + return false; + } + // For the latitude of the point, compute the longitude of the // point that lies on the line segment defined by a and b // This is done by computing the percent above a the lat is, From 48f064ee9f635a23baa756c90848760b8832114c Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 4 Aug 2024 14:42:35 -0700 Subject: [PATCH 25/37] remove ineffective fix --- src/h3lib/include/polygonAlgos.h | 5 ----- src/h3lib/lib/polyfill.c | 11 +++++++++++ 2 files changed, 11 insertions(+), 5 deletions(-) diff --git a/src/h3lib/include/polygonAlgos.h b/src/h3lib/include/polygonAlgos.h index 880381a11a..e6ce98403f 100644 --- a/src/h3lib/include/polygonAlgos.h +++ b/src/h3lib/include/polygonAlgos.h @@ -121,11 +121,6 @@ bool GENERIC_LOOP_ALGO(pointInside)(const TYPE *loop, const BBox *bbox, lng -= DBL_EPSILON; } - // Illegal input, reject. - if (fabs(aLng) > M_2PI || fabs(bLng) > M_2PI) { - return false; - } - // For the latitude of the point, compute the longitude of the // point that lies on the line segment defined by a and b // This is done by computing the percent above a the lat is, diff --git a/src/h3lib/lib/polyfill.c b/src/h3lib/lib/polyfill.c index 150dd24740..eb40006bb2 100644 --- a/src/h3lib/lib/polyfill.c +++ b/src/h3lib/lib/polyfill.c @@ -692,10 +692,21 @@ void iterDestroyPolygon(IterCellsPolygon *iter) { H3Error H3_EXPORT(polygonToCellsExperimental)(const GeoPolygon *polygon, int res, uint32_t flags, H3Index *out) { + int64_t maxSize; + H3Error sizeError = H3_EXPORT(maxPolygonToCellsSizeExperimental)( + polygon, res, flags, &maxSize); + if (sizeError) { + return sizeError; + } + IterCellsPolygon iter = iterInitPolygon(polygon, res, flags); int64_t i = 0; for (; iter.cell; iterStepPolygon(&iter)) { out[i++] = iter.cell; + if (i > maxSize) { + iterDestroyPolygon(&iter); + return E_FAILED; + } } return iter.error; } From b4370cba1de614a491575ab322095c63bb0fc053 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 4 Aug 2024 14:47:46 -0700 Subject: [PATCH 26/37] fix inequality --- src/h3lib/lib/polyfill.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/h3lib/lib/polyfill.c b/src/h3lib/lib/polyfill.c index eb40006bb2..dcface5301 100644 --- a/src/h3lib/lib/polyfill.c +++ b/src/h3lib/lib/polyfill.c @@ -703,7 +703,7 @@ H3Error H3_EXPORT(polygonToCellsExperimental)(const GeoPolygon *polygon, int64_t i = 0; for (; iter.cell; iterStepPolygon(&iter)) { out[i++] = iter.cell; - if (i > maxSize) { + if (i >= maxSize) { iterDestroyPolygon(&iter); return E_FAILED; } From 1c4cef00040354ff95c4fbdffe73d26b451850a9 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 4 Aug 2024 14:55:04 -0700 Subject: [PATCH 27/37] fix for 0 length maxes --- src/h3lib/lib/polyfill.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/h3lib/lib/polyfill.c b/src/h3lib/lib/polyfill.c index dcface5301..7a47d6bb9a 100644 --- a/src/h3lib/lib/polyfill.c +++ b/src/h3lib/lib/polyfill.c @@ -702,11 +702,11 @@ H3Error H3_EXPORT(polygonToCellsExperimental)(const GeoPolygon *polygon, IterCellsPolygon iter = iterInitPolygon(polygon, res, flags); int64_t i = 0; for (; iter.cell; iterStepPolygon(&iter)) { - out[i++] = iter.cell; if (i >= maxSize) { iterDestroyPolygon(&iter); return E_FAILED; } + out[i++] = iter.cell; } return iter.error; } From 74f206e093cbec5368395781e4374bf12dfe4244 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 4 Aug 2024 15:00:56 -0700 Subject: [PATCH 28/37] fix memory test --- src/apps/testapps/testH3Memory.c | 12 ++++++++++-- 1 file changed, 10 insertions(+), 2 deletions(-) diff --git a/src/apps/testapps/testH3Memory.c b/src/apps/testapps/testH3Memory.c index 57d5d3bc03..b781abba4a 100644 --- a/src/apps/testapps/testH3Memory.c +++ b/src/apps/testapps/testH3Memory.c @@ -247,10 +247,18 @@ SUITE(h3Memory) { resetMemoryCounters(1); err = H3_EXPORT(polygonToCellsExperimental)( &sfGeoPolygon, 9, CONTAINMENT_CENTER, hexagons); - t_assert(err == E_SUCCESS, "polygonToCellsExperimental succeeded (1)"); - t_assert(actualAllocCalls == 1, "alloc called one time"); + t_assert(err == E_MEMORY_ALLOC, + "polygonToCellsExperimental failed (1)"); + t_assert(actualAllocCalls == 2, "alloc called two times"); t_assert(actualFreeCalls == 1, "free called one time"); + resetMemoryCounters(2); + err = H3_EXPORT(polygonToCellsExperimental)( + &sfGeoPolygon, 9, CONTAINMENT_CENTER, hexagons); + t_assert(err == E_SUCCESS, "polygonToCellsExperimental succeeded (2)"); + t_assert(actualAllocCalls == 2, "alloc called two times"); + t_assert(actualFreeCalls == 2, "free called two times"); + int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 1253, "got expected polygonToCellsExperimental size"); From 572325ca26f1e9fd026d79bd6d09dd0159328bd6 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 22 Sep 2024 09:27:55 -0700 Subject: [PATCH 29/37] fix for overlapping bbox inconsistency --- .../testPolygonToCellsReportedExperimental.c | 30 +++++++++++++++++++ src/h3lib/lib/polyfill.c | 5 ++-- 2 files changed, 33 insertions(+), 2 deletions(-) diff --git a/src/apps/testapps/testPolygonToCellsReportedExperimental.c b/src/apps/testapps/testPolygonToCellsReportedExperimental.c index b3fe8e5b83..e1cc62fea2 100644 --- a/src/apps/testapps/testPolygonToCellsReportedExperimental.c +++ b/src/apps/testapps/testPolygonToCellsReportedExperimental.c @@ -28,6 +28,36 @@ // Tests for specific polygonToCells examples SUITE(polygonToCells_reported) { + // fuzzer crash due to inconsistent handling of CONTAINMENT_OVERLAPPING + TEST(fuzzer_crash) { + uint8_t data[] = { + 0xff, 0xff, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, + 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0xa, 0x0, 0x0, 0xff, + 0xff, 0x0, 0x0, 0x0, 0xa, 0xa, 0xa, 0xa, 0xa, 0xff, + }; + + uint8_t res = 0; + size_t vertsSize = sizeof(data); + int numVerts = vertsSize / sizeof(LatLng); + + GeoPolygon geoPolygon; + geoPolygon.numHoles = 0; + geoPolygon.holes = NULL; + geoPolygon.geoloop.numVerts = numVerts; + // Offset by 1 since *data was used for `res`, above. + geoPolygon.geoloop.verts = (LatLng *)(data); + + uint32_t flags = CONTAINMENT_OVERLAPPING; + int64_t sz; + t_assertSuccess(H3_EXPORT(maxPolygonToCellsSizeExperimental)( + &geoPolygon, res, flags, &sz)); + t_assert(sz == 1, "Expected output count"); + H3Index *out = calloc(sz, sizeof(H3Index)); + t_assertSuccess(H3_EXPORT(polygonToCellsExperimental)(&geoPolygon, res, + flags, out)); + free(out); + } + // https://github.com/uber/h3-js/issues/76#issuecomment-561204505 TEST(entireWorld) { // TODO: Fails for a single worldwide polygon diff --git a/src/h3lib/lib/polyfill.c b/src/h3lib/lib/polyfill.c index 7a47d6bb9a..de8bb1900e 100644 --- a/src/h3lib/lib/polyfill.c +++ b/src/h3lib/lib/polyfill.c @@ -448,7 +448,8 @@ void iterStepPolygonCompact(IterCellsPolygonCompact *iter) { return; } } - if (mode == CONTAINMENT_OVERLAPPING) { + if (mode == CONTAINMENT_OVERLAPPING || + mode == CONTAINMENT_OVERLAPPING_BBOX) { // For overlapping, we need to do a quick check to determine // whether the polygon is wholly contained by the cell. We // check the first polygon vertex, which if it is contained @@ -702,7 +703,7 @@ H3Error H3_EXPORT(polygonToCellsExperimental)(const GeoPolygon *polygon, IterCellsPolygon iter = iterInitPolygon(polygon, res, flags); int64_t i = 0; for (; iter.cell; iterStepPolygon(&iter)) { - if (i >= maxSize) { + if (NEVER(i >= maxSize)) { iterDestroyPolygon(&iter); return E_FAILED; } From 942a54b0cb1625aa9612b7b7a68966e7e09619f8 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 22 Sep 2024 09:34:36 -0700 Subject: [PATCH 30/37] revert check --- src/h3lib/lib/polyfill.c | 11 ----------- 1 file changed, 11 deletions(-) diff --git a/src/h3lib/lib/polyfill.c b/src/h3lib/lib/polyfill.c index de8bb1900e..2ea83b53d7 100644 --- a/src/h3lib/lib/polyfill.c +++ b/src/h3lib/lib/polyfill.c @@ -693,20 +693,9 @@ void iterDestroyPolygon(IterCellsPolygon *iter) { H3Error H3_EXPORT(polygonToCellsExperimental)(const GeoPolygon *polygon, int res, uint32_t flags, H3Index *out) { - int64_t maxSize; - H3Error sizeError = H3_EXPORT(maxPolygonToCellsSizeExperimental)( - polygon, res, flags, &maxSize); - if (sizeError) { - return sizeError; - } - IterCellsPolygon iter = iterInitPolygon(polygon, res, flags); int64_t i = 0; for (; iter.cell; iterStepPolygon(&iter)) { - if (NEVER(i >= maxSize)) { - iterDestroyPolygon(&iter); - return E_FAILED; - } out[i++] = iter.cell; } return iter.error; From 9b512217de5b424f6a98aa6aea7b359e8c8f149a Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 22 Sep 2024 09:42:14 -0700 Subject: [PATCH 31/37] revert memory test --- src/apps/testapps/testH3Memory.c | 12 ++---------- 1 file changed, 2 insertions(+), 10 deletions(-) diff --git a/src/apps/testapps/testH3Memory.c b/src/apps/testapps/testH3Memory.c index b781abba4a..57d5d3bc03 100644 --- a/src/apps/testapps/testH3Memory.c +++ b/src/apps/testapps/testH3Memory.c @@ -247,18 +247,10 @@ SUITE(h3Memory) { resetMemoryCounters(1); err = H3_EXPORT(polygonToCellsExperimental)( &sfGeoPolygon, 9, CONTAINMENT_CENTER, hexagons); - t_assert(err == E_MEMORY_ALLOC, - "polygonToCellsExperimental failed (1)"); - t_assert(actualAllocCalls == 2, "alloc called two times"); + t_assert(err == E_SUCCESS, "polygonToCellsExperimental succeeded (1)"); + t_assert(actualAllocCalls == 1, "alloc called one time"); t_assert(actualFreeCalls == 1, "free called one time"); - resetMemoryCounters(2); - err = H3_EXPORT(polygonToCellsExperimental)( - &sfGeoPolygon, 9, CONTAINMENT_CENTER, hexagons); - t_assert(err == E_SUCCESS, "polygonToCellsExperimental succeeded (2)"); - t_assert(actualAllocCalls == 2, "alloc called two times"); - t_assert(actualFreeCalls == 2, "free called two times"); - int64_t actualNumIndexes = countNonNullIndexes(hexagons, numHexagons); t_assert(actualNumIndexes == 1253, "got expected polygonToCellsExperimental size"); From 9417bb058bf426860f0fad63002b299eaf5653ea Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 22 Sep 2024 10:16:31 -0700 Subject: [PATCH 32/37] more overlapping bbox changes --- .../testPolygonToCellsReportedExperimental.c | 447 ++++++++++++++++++ src/h3lib/lib/polyfill.c | 27 +- 2 files changed, 470 insertions(+), 4 deletions(-) diff --git a/src/apps/testapps/testPolygonToCellsReportedExperimental.c b/src/apps/testapps/testPolygonToCellsReportedExperimental.c index e1cc62fea2..61dbcb2d3f 100644 --- a/src/apps/testapps/testPolygonToCellsReportedExperimental.c +++ b/src/apps/testapps/testPolygonToCellsReportedExperimental.c @@ -27,7 +27,454 @@ // Tests for specific polygonToCells examples +typedef struct { + int res; + int numHoles; + // repeating: num verts, verts + // We add a large fixed buffer so our test case generator for AFL + // knows how large to make the file. + uint8_t buffer[1024]; +} inputArgs; + +const int MAX_RES = 15; +const int MAX_SZ = 4000000; +const int MAX_HOLES = 100; + +int populateGeoLoop(GeoLoop *g, const uint8_t *data, size_t *offset, + size_t size) { + if (size < *offset + sizeof(int)) { + return 1; + } + int numVerts = *(const int *)(data + *offset); + *offset = *offset + sizeof(int); + g->numVerts = numVerts; + if (size < *offset + sizeof(LatLng) * numVerts) { + return 1; + } + g->verts = (LatLng *)(data + *offset); + *offset = *offset + sizeof(LatLng) * numVerts; + return 0; +} + +void run(GeoPolygon *geoPolygon, uint32_t flags, int res) { + int64_t sz; + H3Error err = H3_EXPORT(maxPolygonToCellsSizeExperimental)(geoPolygon, res, + flags, &sz); + if (!err && sz < MAX_SZ) { + H3Index *out = calloc(sz, sizeof(H3Index)); + H3_EXPORT(polygonToCellsExperimental)(geoPolygon, res, flags, out); + free(out); + } +} + SUITE(polygonToCells_reported) { + TEST(fuzzer_crash3) { + unsigned char __crash_0e87cee635058fcd61145800fcbf9ca5faf8b082[] = { + 0x00, 0x00, 0xac, 0xac, 0xac, 0x59, 0x59, 0x59, 0x59, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x66, 0x66, 0x66, 0x66, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xff, + 0xff, 0xff, 0xff, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0x2c, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0x0a, 0xac, 0xac, 0xac, 0xac, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0xff, 0xff, 0xff, 0xff, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0x2c, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, + 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, + 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, + 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0x56, 0x53, 0x53, + 0x53, 0xac, 0xac, 0xac, 0xac, 0xac, 0x0a, 0xac, 0xac, 0xac, 0xac, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xff, 0xff, 0xff, 0xff, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, + 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, + 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, + 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, + 0x49, 0x49, 0x49, 0x49, 0x49, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x49, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x32, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xfb, 0xa5, 0xa6, 0xa6, 0xa6, 0xa6, + 0xa6, 0xa6, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x6b, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0x55, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x49, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xfb, 0xa5, 0xa6, 0xa6, 0xa6, 0xa6, 0xa6, 0xa6, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, + 0x49, 0x49, 0x49, 0x46, 0x49, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, + 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, + 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, + 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xe8, 0xf8, 0xf8, 0xf8, 0xf8, + 0x64, 0x64, 0x64, 0x64, 0x64, 0x64, 0x64, 0x64, 0x64, 0x64, 0x64, + 0x64, 0x64, 0x64, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, + 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, + 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, + 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, + 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, + 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, + 0xf8, 0xf8, 0xf8, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, + 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, + 0x49, 0x49, 0x49, 0x49, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0x55, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x31, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x55, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x5b, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0x54, 0x53, 0x53, + 0x4b, 0x56, 0x53, 0x53, 0x53, 0xac, 0xac, 0xac, 0xac, 0xac, 0x0a, + 0xac, 0xac, 0xac, 0xac, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0xac, 0xac, 0xac, 0xac, 0xac, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xac, 0xff, 0xff, 0xff, + 0xff, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac}; + unsigned int __crash_0e87cee635058fcd61145800fcbf9ca5faf8b082_len = + 1717; + + const inputArgs *args = + (const inputArgs *)__crash_0e87cee635058fcd61145800fcbf9ca5faf8b082; + int res = args->res % (MAX_RES + 1); + + GeoPolygon geoPolygon; + int originalNumHoles = args->numHoles % MAX_HOLES; + geoPolygon.numHoles = originalNumHoles; + t_assert(geoPolygon.numHoles >= 0, "holes present"); + geoPolygon.holes = calloc(geoPolygon.numHoles, sizeof(GeoLoop)); + size_t offset = sizeof(inputArgs) - sizeof(args->buffer); + if (populateGeoLoop( + &geoPolygon.geoloop, + __crash_0e87cee635058fcd61145800fcbf9ca5faf8b082, &offset, + __crash_0e87cee635058fcd61145800fcbf9ca5faf8b082_len)) { + free(geoPolygon.holes); + t_assert(0, "not populated"); + } + for (int i = 0; i < geoPolygon.numHoles; i++) { + if (populateGeoLoop( + &geoPolygon.holes[i], + __crash_0e87cee635058fcd61145800fcbf9ca5faf8b082, &offset, + __crash_0e87cee635058fcd61145800fcbf9ca5faf8b082_len)) { + free(geoPolygon.holes); + t_assert(0, "not populated hole"); + } + } + + for (uint32_t flags = 0; flags < CONTAINMENT_INVALID; flags++) { + printf("flag=%d\n", flags); + geoPolygon.numHoles = originalNumHoles; + run(&geoPolygon, flags, res); + printf("No hole\n"); + geoPolygon.numHoles = 0; + run(&geoPolygon, flags, res); + } + free(geoPolygon.holes); + } + + TEST(fuzzer_crash2) { + unsigned char __crash_dd5587cdcb9c09ae0bb840261ff1fce7c054f520[] = { + 0x00, 0x00, 0xac, 0xac, 0xac, 0x59, 0x59, 0x59, 0x59, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xff, 0xff, 0xff, 0xff, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0x2c, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x0a, + 0xac, 0xac, 0xac, 0xac, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xff, 0xff, + 0xff, 0xff, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0x2c, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0x49, 0x49, + 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, + 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, + 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, + 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x20, 0x20, 0x20, + 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, + 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, + 0x20, 0x20, 0x20, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x55, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0x56, 0x53, 0x53, 0x53, 0xac, 0xac, 0xac, + 0xac, 0xac, 0x0a, 0xac, 0xac, 0xac, 0xac, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0xff, 0xff, 0xff, 0xff, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x49, + 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, + 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, + 0x49, 0x49, 0x49, 0x49, 0x00, 0x00, 0x00, 0x80, 0x49, 0x49, 0x49, + 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, + 0x49, 0x49, 0x49, 0x49, 0x49, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x49, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xfb, 0xa5, 0xa6, 0xa6, 0xa6, 0xa6, 0xa6, + 0xa6, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xa7, 0xa6, 0xa6, 0xa9, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x6b, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x55, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x49, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xfb, 0xa5, 0xa6, 0xa6, 0xa6, 0xa6, 0xa6, 0xa6, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, + 0x49, 0x49, 0x46, 0x49, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, + 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, + 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, + 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xe8, 0xf8, 0xf8, 0xf8, 0xf8, 0x64, + 0x64, 0x64, 0x64, 0x64, 0x64, 0x64, 0x64, 0x64, 0x64, 0x64, 0x64, + 0x64, 0x64, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, + 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, + 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, + 0xf8, 0xf8, 0xf8, 0xf8, 0xf9, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, + 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, + 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, + 0xf8, 0xf8, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, + 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, + 0x49, 0x49, 0x49, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0x55, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0x55, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x5b, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0x56, + 0x53, 0x53, 0x53, 0xac, 0xac, 0xac, 0xac, 0xac, 0x0a, 0xac, 0xac, + 0xac, 0xac, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0xac, 0xac, 0xac, 0xac, 0xac, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, + 0x59, 0x59, 0x59, 0x59, 0x59, 0xac, 0xff, 0xff, 0xff, 0xff, 0xac, + 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac}; + unsigned int __crash_dd5587cdcb9c09ae0bb840261ff1fce7c054f520_len = + 1825; + + const inputArgs *args = + (const inputArgs *)__crash_dd5587cdcb9c09ae0bb840261ff1fce7c054f520; + int res = args->res % (MAX_RES + 1); + + GeoPolygon geoPolygon; + int originalNumHoles = args->numHoles % MAX_HOLES; + geoPolygon.numHoles = originalNumHoles; + t_assert(geoPolygon.numHoles >= 0, "holes present"); + geoPolygon.holes = calloc(geoPolygon.numHoles, sizeof(GeoLoop)); + size_t offset = sizeof(inputArgs) - sizeof(args->buffer); + if (populateGeoLoop( + &geoPolygon.geoloop, + __crash_dd5587cdcb9c09ae0bb840261ff1fce7c054f520, &offset, + __crash_dd5587cdcb9c09ae0bb840261ff1fce7c054f520_len)) { + free(geoPolygon.holes); + t_assert(0, "not populated"); + } + for (int i = 0; i < geoPolygon.numHoles; i++) { + if (populateGeoLoop( + &geoPolygon.holes[i], + __crash_dd5587cdcb9c09ae0bb840261ff1fce7c054f520, &offset, + __crash_dd5587cdcb9c09ae0bb840261ff1fce7c054f520_len)) { + free(geoPolygon.holes); + t_assert(0, "not populated hole"); + } + } + + for (uint32_t flags = 0; flags < CONTAINMENT_INVALID; flags++) { + geoPolygon.numHoles = originalNumHoles; + run(&geoPolygon, flags, res); + geoPolygon.numHoles = 0; + run(&geoPolygon, flags, res); + } + free(geoPolygon.holes); + } + // fuzzer crash due to inconsistent handling of CONTAINMENT_OVERLAPPING TEST(fuzzer_crash) { uint8_t data[] = { diff --git a/src/h3lib/lib/polyfill.c b/src/h3lib/lib/polyfill.c index 2ea83b53d7..56316116cc 100644 --- a/src/h3lib/lib/polyfill.c +++ b/src/h3lib/lib/polyfill.c @@ -433,7 +433,8 @@ void iterStepPolygonCompact(IterCellsPolygonCompact *iter) { // Target res: Do a fine-grained check if (cellRes == iter->_res) { - if (mode == CONTAINMENT_CENTER || mode == CONTAINMENT_OVERLAPPING) { + if (mode == CONTAINMENT_CENTER || mode == CONTAINMENT_OVERLAPPING || + mode == CONTAINMENT_OVERLAPPING_BBOX) { // Check if the cell center is inside the polygon LatLng center; H3Error centerErr = H3_EXPORT(cellToLatLng)(cell, ¢er); @@ -478,7 +479,8 @@ void iterStepPolygonCompact(IterCellsPolygonCompact *iter) { } } } - if (mode == CONTAINMENT_FULL || mode == CONTAINMENT_OVERLAPPING) { + if (mode == CONTAINMENT_FULL || mode == CONTAINMENT_OVERLAPPING || + mode == CONTAINMENT_OVERLAPPING_BBOX) { CellBoundary boundary; H3Error boundaryErr = H3_EXPORT(cellToBoundary)(cell, &boundary); @@ -495,7 +497,8 @@ void iterStepPolygonCompact(IterCellsPolygonCompact *iter) { return; } // Check if the cell is fully contained by the polygon - if (mode == CONTAINMENT_FULL && + if ((mode == CONTAINMENT_FULL || + mode == CONTAINMENT_OVERLAPPING_BBOX) && cellBoundaryInsidePolygon(iter->_polygon, iter->_bboxes, &boundary, &bbox)) { // Set to next output @@ -505,7 +508,8 @@ void iterStepPolygonCompact(IterCellsPolygonCompact *iter) { // For overlap, we've already checked for center point inclusion // above; if that failed, we only need to check for line // intersection - else if (mode == CONTAINMENT_OVERLAPPING && + else if ((mode == CONTAINMENT_OVERLAPPING || + mode == CONTAINMENT_OVERLAPPING_BBOX) && cellBoundaryCrossesPolygon( iter->_polygon, iter->_bboxes, &boundary, &bbox)) { // Set to next output @@ -693,9 +697,24 @@ void iterDestroyPolygon(IterCellsPolygon *iter) { H3Error H3_EXPORT(polygonToCellsExperimental)(const GeoPolygon *polygon, int res, uint32_t flags, H3Index *out) { +#ifndef NDEBUG + int64_t maxSize; + H3Error sizeError = H3_EXPORT(maxPolygonToCellsSizeExperimental)( + polygon, res, flags, &maxSize); + if (sizeError) { + return sizeError; + } +#endif + IterCellsPolygon iter = iterInitPolygon(polygon, res, flags); int64_t i = 0; for (; iter.cell; iterStepPolygon(&iter)) { +#ifndef NDEBUG + if (NEVER(i >= maxSize)) { + iterDestroyPolygon(&iter); + return E_FAILED; + } +#endif out[i++] = iter.cell; } return iter.error; From 08bc56e2c30317f24d1ecc1c6825a31d3be550ed Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 22 Sep 2024 10:20:04 -0700 Subject: [PATCH 33/37] change assert to avoid triggering in test --- src/h3lib/lib/polyfill.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/src/h3lib/lib/polyfill.c b/src/h3lib/lib/polyfill.c index 56316116cc..cf6611df40 100644 --- a/src/h3lib/lib/polyfill.c +++ b/src/h3lib/lib/polyfill.c @@ -697,7 +697,7 @@ void iterDestroyPolygon(IterCellsPolygon *iter) { H3Error H3_EXPORT(polygonToCellsExperimental)(const GeoPolygon *polygon, int res, uint32_t flags, H3Index *out) { -#ifndef NDEBUG +#ifdef H3_POLYGON_TO_CELLS_ASSERT int64_t maxSize; H3Error sizeError = H3_EXPORT(maxPolygonToCellsSizeExperimental)( polygon, res, flags, &maxSize); @@ -709,7 +709,7 @@ H3Error H3_EXPORT(polygonToCellsExperimental)(const GeoPolygon *polygon, IterCellsPolygon iter = iterInitPolygon(polygon, res, flags); int64_t i = 0; for (; iter.cell; iterStepPolygon(&iter)) { -#ifndef NDEBUG +#ifdef H3_POLYGON_TO_CELLS_ASSERT if (NEVER(i >= maxSize)) { iterDestroyPolygon(&iter); return E_FAILED; From 6048f3683ecd0fc5b1345c6f2c4a139c16e96c92 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 22 Sep 2024 10:33:21 -0700 Subject: [PATCH 34/37] remove tests with unaligned reads --- .../testPolygonToCellsReportedExperimental.c | 447 ------------------ 1 file changed, 447 deletions(-) diff --git a/src/apps/testapps/testPolygonToCellsReportedExperimental.c b/src/apps/testapps/testPolygonToCellsReportedExperimental.c index 61dbcb2d3f..e1cc62fea2 100644 --- a/src/apps/testapps/testPolygonToCellsReportedExperimental.c +++ b/src/apps/testapps/testPolygonToCellsReportedExperimental.c @@ -27,454 +27,7 @@ // Tests for specific polygonToCells examples -typedef struct { - int res; - int numHoles; - // repeating: num verts, verts - // We add a large fixed buffer so our test case generator for AFL - // knows how large to make the file. - uint8_t buffer[1024]; -} inputArgs; - -const int MAX_RES = 15; -const int MAX_SZ = 4000000; -const int MAX_HOLES = 100; - -int populateGeoLoop(GeoLoop *g, const uint8_t *data, size_t *offset, - size_t size) { - if (size < *offset + sizeof(int)) { - return 1; - } - int numVerts = *(const int *)(data + *offset); - *offset = *offset + sizeof(int); - g->numVerts = numVerts; - if (size < *offset + sizeof(LatLng) * numVerts) { - return 1; - } - g->verts = (LatLng *)(data + *offset); - *offset = *offset + sizeof(LatLng) * numVerts; - return 0; -} - -void run(GeoPolygon *geoPolygon, uint32_t flags, int res) { - int64_t sz; - H3Error err = H3_EXPORT(maxPolygonToCellsSizeExperimental)(geoPolygon, res, - flags, &sz); - if (!err && sz < MAX_SZ) { - H3Index *out = calloc(sz, sizeof(H3Index)); - H3_EXPORT(polygonToCellsExperimental)(geoPolygon, res, flags, out); - free(out); - } -} - SUITE(polygonToCells_reported) { - TEST(fuzzer_crash3) { - unsigned char __crash_0e87cee635058fcd61145800fcbf9ca5faf8b082[] = { - 0x00, 0x00, 0xac, 0xac, 0xac, 0x59, 0x59, 0x59, 0x59, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x66, 0x66, 0x66, 0x66, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xff, - 0xff, 0xff, 0xff, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0x2c, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0x0a, 0xac, 0xac, 0xac, 0xac, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0xff, 0xff, 0xff, 0xff, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0x2c, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, - 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, - 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, - 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0x56, 0x53, 0x53, - 0x53, 0xac, 0xac, 0xac, 0xac, 0xac, 0x0a, 0xac, 0xac, 0xac, 0xac, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xff, 0xff, 0xff, 0xff, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, - 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, - 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, - 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, - 0x49, 0x49, 0x49, 0x49, 0x49, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x49, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x32, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xfb, 0xa5, 0xa6, 0xa6, 0xa6, 0xa6, - 0xa6, 0xa6, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x6b, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0x55, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x49, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xfb, 0xa5, 0xa6, 0xa6, 0xa6, 0xa6, 0xa6, 0xa6, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, - 0x49, 0x49, 0x49, 0x46, 0x49, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, - 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, - 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, - 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xe8, 0xf8, 0xf8, 0xf8, 0xf8, - 0x64, 0x64, 0x64, 0x64, 0x64, 0x64, 0x64, 0x64, 0x64, 0x64, 0x64, - 0x64, 0x64, 0x64, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, - 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, - 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, - 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, - 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, - 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, - 0xf8, 0xf8, 0xf8, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, - 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, - 0x49, 0x49, 0x49, 0x49, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0x55, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x31, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x55, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x5b, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0x54, 0x53, 0x53, - 0x4b, 0x56, 0x53, 0x53, 0x53, 0xac, 0xac, 0xac, 0xac, 0xac, 0x0a, - 0xac, 0xac, 0xac, 0xac, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0xac, 0xac, 0xac, 0xac, 0xac, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xac, 0xff, 0xff, 0xff, - 0xff, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac}; - unsigned int __crash_0e87cee635058fcd61145800fcbf9ca5faf8b082_len = - 1717; - - const inputArgs *args = - (const inputArgs *)__crash_0e87cee635058fcd61145800fcbf9ca5faf8b082; - int res = args->res % (MAX_RES + 1); - - GeoPolygon geoPolygon; - int originalNumHoles = args->numHoles % MAX_HOLES; - geoPolygon.numHoles = originalNumHoles; - t_assert(geoPolygon.numHoles >= 0, "holes present"); - geoPolygon.holes = calloc(geoPolygon.numHoles, sizeof(GeoLoop)); - size_t offset = sizeof(inputArgs) - sizeof(args->buffer); - if (populateGeoLoop( - &geoPolygon.geoloop, - __crash_0e87cee635058fcd61145800fcbf9ca5faf8b082, &offset, - __crash_0e87cee635058fcd61145800fcbf9ca5faf8b082_len)) { - free(geoPolygon.holes); - t_assert(0, "not populated"); - } - for (int i = 0; i < geoPolygon.numHoles; i++) { - if (populateGeoLoop( - &geoPolygon.holes[i], - __crash_0e87cee635058fcd61145800fcbf9ca5faf8b082, &offset, - __crash_0e87cee635058fcd61145800fcbf9ca5faf8b082_len)) { - free(geoPolygon.holes); - t_assert(0, "not populated hole"); - } - } - - for (uint32_t flags = 0; flags < CONTAINMENT_INVALID; flags++) { - printf("flag=%d\n", flags); - geoPolygon.numHoles = originalNumHoles; - run(&geoPolygon, flags, res); - printf("No hole\n"); - geoPolygon.numHoles = 0; - run(&geoPolygon, flags, res); - } - free(geoPolygon.holes); - } - - TEST(fuzzer_crash2) { - unsigned char __crash_dd5587cdcb9c09ae0bb840261ff1fce7c054f520[] = { - 0x00, 0x00, 0xac, 0xac, 0xac, 0x59, 0x59, 0x59, 0x59, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xff, 0xff, 0xff, 0xff, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0x2c, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x0a, - 0xac, 0xac, 0xac, 0xac, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xff, 0xff, - 0xff, 0xff, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0x2c, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0x49, 0x49, - 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, - 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, - 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, - 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x20, 0x20, 0x20, - 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, - 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, - 0x20, 0x20, 0x20, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x55, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0x56, 0x53, 0x53, 0x53, 0xac, 0xac, 0xac, - 0xac, 0xac, 0x0a, 0xac, 0xac, 0xac, 0xac, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0xff, 0xff, 0xff, 0xff, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x49, - 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, - 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, - 0x49, 0x49, 0x49, 0x49, 0x00, 0x00, 0x00, 0x80, 0x49, 0x49, 0x49, - 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, - 0x49, 0x49, 0x49, 0x49, 0x49, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x49, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xfb, 0xa5, 0xa6, 0xa6, 0xa6, 0xa6, 0xa6, - 0xa6, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xa7, 0xa6, 0xa6, 0xa9, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x6b, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x55, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x49, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xfb, 0xa5, 0xa6, 0xa6, 0xa6, 0xa6, 0xa6, 0xa6, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, - 0x49, 0x49, 0x46, 0x49, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, - 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, - 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, - 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xe8, 0xf8, 0xf8, 0xf8, 0xf8, 0x64, - 0x64, 0x64, 0x64, 0x64, 0x64, 0x64, 0x64, 0x64, 0x64, 0x64, 0x64, - 0x64, 0x64, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, - 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, - 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, - 0xf8, 0xf8, 0xf8, 0xf8, 0xf9, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, - 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, - 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, 0xf8, - 0xf8, 0xf8, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, - 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, - 0x49, 0x49, 0x49, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0x55, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0x55, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x5b, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0x56, - 0x53, 0x53, 0x53, 0xac, 0xac, 0xac, 0xac, 0xac, 0x0a, 0xac, 0xac, - 0xac, 0xac, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0xac, 0xac, 0xac, 0xac, 0xac, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, 0x59, - 0x59, 0x59, 0x59, 0x59, 0x59, 0xac, 0xff, 0xff, 0xff, 0xff, 0xac, - 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac, 0xac}; - unsigned int __crash_dd5587cdcb9c09ae0bb840261ff1fce7c054f520_len = - 1825; - - const inputArgs *args = - (const inputArgs *)__crash_dd5587cdcb9c09ae0bb840261ff1fce7c054f520; - int res = args->res % (MAX_RES + 1); - - GeoPolygon geoPolygon; - int originalNumHoles = args->numHoles % MAX_HOLES; - geoPolygon.numHoles = originalNumHoles; - t_assert(geoPolygon.numHoles >= 0, "holes present"); - geoPolygon.holes = calloc(geoPolygon.numHoles, sizeof(GeoLoop)); - size_t offset = sizeof(inputArgs) - sizeof(args->buffer); - if (populateGeoLoop( - &geoPolygon.geoloop, - __crash_dd5587cdcb9c09ae0bb840261ff1fce7c054f520, &offset, - __crash_dd5587cdcb9c09ae0bb840261ff1fce7c054f520_len)) { - free(geoPolygon.holes); - t_assert(0, "not populated"); - } - for (int i = 0; i < geoPolygon.numHoles; i++) { - if (populateGeoLoop( - &geoPolygon.holes[i], - __crash_dd5587cdcb9c09ae0bb840261ff1fce7c054f520, &offset, - __crash_dd5587cdcb9c09ae0bb840261ff1fce7c054f520_len)) { - free(geoPolygon.holes); - t_assert(0, "not populated hole"); - } - } - - for (uint32_t flags = 0; flags < CONTAINMENT_INVALID; flags++) { - geoPolygon.numHoles = originalNumHoles; - run(&geoPolygon, flags, res); - geoPolygon.numHoles = 0; - run(&geoPolygon, flags, res); - } - free(geoPolygon.holes); - } - // fuzzer crash due to inconsistent handling of CONTAINMENT_OVERLAPPING TEST(fuzzer_crash) { uint8_t data[] = { From 21c5a65495027a8abea27263850a75f14c497a9e Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 22 Sep 2024 10:33:41 -0700 Subject: [PATCH 35/37] ignore extra build directories --- .gitignore | 1 + 1 file changed, 1 insertion(+) diff --git a/.gitignore b/.gitignore index 5ecab97257..130f47983f 100644 --- a/.gitignore +++ b/.gitignore @@ -10,6 +10,7 @@ /lib/ # Travis CI build directory /build/ +/build*/ # Local build directories /Debug/ /Release/ From c256faac64a36bd824785a9a0569bfff9fc54a6f Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 22 Sep 2024 10:34:48 -0700 Subject: [PATCH 36/37] comment --- src/h3lib/lib/polyfill.c | 3 +++ 1 file changed, 3 insertions(+) diff --git a/src/h3lib/lib/polyfill.c b/src/h3lib/lib/polyfill.c index cf6611df40..5b8220f899 100644 --- a/src/h3lib/lib/polyfill.c +++ b/src/h3lib/lib/polyfill.c @@ -698,6 +698,9 @@ H3Error H3_EXPORT(polygonToCellsExperimental)(const GeoPolygon *polygon, int res, uint32_t flags, H3Index *out) { #ifdef H3_POLYGON_TO_CELLS_ASSERT + // TODO: This is incompatible with testH3Memory, since it will make more + // allocations. This is just for debugging that the algorithm is not + // exceeding its buffer size. int64_t maxSize; H3Error sizeError = H3_EXPORT(maxPolygonToCellsSizeExperimental)( polygon, res, flags, &maxSize); From 9dbea70dcf3909a6db72c76cd551640de7d7ce86 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 22 Sep 2024 11:35:26 -0700 Subject: [PATCH 37/37] back out unneeded change --- src/h3lib/lib/polyfill.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) diff --git a/src/h3lib/lib/polyfill.c b/src/h3lib/lib/polyfill.c index 5b8220f899..6269aaef3e 100644 --- a/src/h3lib/lib/polyfill.c +++ b/src/h3lib/lib/polyfill.c @@ -508,8 +508,7 @@ void iterStepPolygonCompact(IterCellsPolygonCompact *iter) { // For overlap, we've already checked for center point inclusion // above; if that failed, we only need to check for line // intersection - else if ((mode == CONTAINMENT_OVERLAPPING || - mode == CONTAINMENT_OVERLAPPING_BBOX) && + else if (mode == CONTAINMENT_OVERLAPPING && cellBoundaryCrossesPolygon( iter->_polygon, iter->_bboxes, &boundary, &bbox)) { // Set to next output