8000 Fix a possible signed integer overflow in localIjToCell by isaacbrodsky · Pull Request #706 · uber/h3 · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Fix a possible signed integer overflow in localIjToCell #706

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 4 commits into from
Oct 10, 2022
Merged

Fix a possible signed integer overflow in localIjToCell #706

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
4 commits
Select commit Hold shift + click to select a range
c6f0ecb
Fix a possible signed integer overflow in localIjToCell
Oct 6, 2022
fffdba7
Add changelog and comment
Oct 6, 2022
7740371
fix incorrectly specified test
Oct 6, 2022
e9453c1
Merge branch 'master' into localijtocell-overflow
isaacbrodsky Oct 10, 2022
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
1 change: 1 addition & 0 deletions CHANGELOG.md
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -8,6 +8,7 @@ The public API of this library consists of the functions declared in file
## [Unreleased]
### Fixed
- Fixed possible signed integer overflow in `h3NeighborRotations` (#707)
- Fixed possible signed integer overflow in `localIjToCell` (#706)

## [4.0.1] - 2022-09-15
### Fixed
Expand Down
27 changes: 27 additions & 0 deletions src/apps/testapps/testCellToLocalIj.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -280,4 +280,31 @@ SUITE(h3ToLocalIj) {
t_assert(H3_EXPORT(localIjToCell)(index, &ij, 0, &out) == E_FAILED,
"Negative I and J components fail");
}

TEST(localIjToCell_overflow_i) {
H3Index origin;
setH3Index(&origin, 2, 2, CENTER_DIGIT);
CoordIJ ij = {.i = INT32_MIN, .j = INT32_MAX};
H3Index out;
t_assert(H3_EXPORT(localIjToCell)(origin, &ij, 0, &out) == E_FAILED,
"High magnitude I and J components fail");
}

TEST(localIjToCell_overflow_j) {
H3Index origin;
setH3Index(&origin, 2, 2, CENTER_DIGIT);
CoordIJ ij = {.i = INT32_MAX, .j = INT32_MIN};
H3Index out;
t_assert(H3_EXPORT(localIjToCell)(origin, &ij, 0, &out) == E_FAILED,
"High magnitude J and I components fail");
}

TEST(localIjToCell_overflow_ij) {
H3Index origin;
setH3Index(&origin, 2, 2, CENTER_DIGIT);
CoordIJ ij = {.i = INT32_MIN, .j = INT32_MIN};
H3Index out;
t_assert(H3_EXPORT(localIjToCell)(origin, &ij, 0, &out) == E_FAILED,
"High magnitude J and I components fail");
}
}
6 changes: 3 additions & 3 deletions src/apps/testapps/testCellToLocalIjExhaustive.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -69,7 +69,7 @@ void h3ToLocalIj_coordinates_assertions(H3Index h3) {
t_assert(H3_EXPORT(cellToLocalIj)(h3, h3, 0, &ij) == 0,
"get ij for origin");
CoordIJK ijk;
ijToIjk(&ij, &ijk);
t_assertSuccess(ijToIjk(&ij, &ijk));
if (r == 0) {
t_assert(_ijkMatches(&ijk, &UNIT_VECS[0]) == 1, "res 0 cell at 0,0,0");
} else if (r == 1) {
Expand All @@ -95,7 +95,7 @@ void h3ToLocalIj_neighbors_assertions(H3Index h3) {
t_assert(H3_EXPORT(cellToLocalIj)(h3, h3, 0, &origin) == 0,
"got ij for origin");
CoordIJK originIjk;
ijToIjk(&origin, &originIjk);
t_assertSuccess(ijToIjk(&origin, &originIjk));

for (Direction d = K_AXES_DIGIT; d < INVALID_DIGIT; d++) {
if (d == K_AXES_DIGIT && H3_EXPORT(isPentagon)(h3)) {
Expand All @@ -110,7 +110,7 @@ void h3ToLocalIj_neighbors_assertions(H3Index h3) {
t_assert(H3_EXPORT(cellToLocalIj)(h3, offset, 0, &ij) == 0,
"got ij for destination");
CoordIJK ijk;
ijToIjk(&ij, &ijk);
t_assertSuccess(ijToIjk(&ij, &ijk));
CoordIJK invertedIjk = {0};
_neighbor(&invertedIjk, d);
for (int i = 0; i < 3; i++) {
Expand Down
4 changes: 2 additions & 2 deletions src/apps/testapps/testCoordIj.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -41,7 +41,7 @@ SUITE(coordIj) {
t_assert(ij.i == 0, "ij.i zero");
t_assert(ij.j == 0, "ij.j zero");

ijToIjk(&ij, &ijk);
t_assertSuccess(ijToIjk(&ij, &ijk));
t_assert(ijk.i == 0, "ijk.i zero");
t_assert(ijk.j == 0, "ijk.j zero");
t_assert(ijk.k == 0, "ijk.k zero");
Expand All @@ -56,7 +56,7 @@ SUITE(coordIj) {
ijkToIj(&ijk, &ij);

CoordIJK recovered = {0};
ijToIjk(&ij, &recovered);
t_assertSuccess(ijToIjk(&ij, &recovered));

t_assert(_ijkMatches(&ijk, &recovered),
"got same ijk coordinates back");
Expand Down
2 changes: 1 addition & 1 deletion src/h3lib/include/coordijk.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -108,7 +108,7 @@ Direction _rotate60ccw(Direction digit);
Direction _rotate60cw(Direction digit);
int ijkDistance(const CoordIJK *a, const CoordIJK *b);
void ijkToIj(const CoordIJK *ijk, CoordIJ *ij);
void ijToIjk(const CoordIJ *ij, CoordIJK *ijk);
H3Error ijToIjk(const CoordIJ *ij, CoordIJK *ijk);
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This makes me suspicious that we may need something similar for ijkToIj or the cube functions as well, might be worth adding tests.

Copy link
Collaborator Author
@isaacbrodsky isaacbrodsky Oct 6, 2022 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I am not sure if ijkToIj can be overflowed assuming that the input coordinates are all non-negative. We would need to be comfortable with that function only being called with IJK+ coordinates, of course.

void ijkToCube(CoordIJK *ijk);
void cubeToIjk(CoordIJK *ijk);

Expand Down
34 changes: 33 additions & 1 deletion src/h3lib/lib/coordijk.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -211,6 +211,11 @@ void _ijkScale(CoordIJK *c, int factor) {
* Normalizes ijk coordinates by setting the components to the smallest possible
* values. Works in place.
*
* This function does not protect against signed integer overflow. The caller
* must ensure that none of (i - j), (i - k), (j - i), (j - k), (k - i), (k - j)
* will overflow. This function may be changed in the future to make that check
* itself and return an error code.
*
* @param c The ijk coordinates to normalize.
*/
void _ijkNormalize(CoordIJK *c) {
Expand Down Expand Up @@ -527,13 +532,40 @@ void ijkToIj(const CoordIJK *ijk, CoordIJ *ij) {
*
* @param ij The input IJ coordinates
* @param ijk The output IJK+ coordinates
* @returns E_SUCCESS on success, E_FAILED if signed integer overflow would have
* occurred.
*/
void ijToIjk(const CoordIJ *ij, CoordIJK *ijk) {
H3Error ijToIjk(const CoordIJ *ij, CoordIJK *ijk) {
ijk->i = ij->i;
ijk->j = ij->j;
ijk->k = 0;

// Check for the possibility of overflow
int max, min;
if (ijk->i > ijk->j) {
max = ijk->i;
min = ijk->j;< 9E12 /td>
} else {
max = ijk->j;
min = ijk->i;
}
if (min < 0) {
// Only if the min is less than 0 will the resulting number be larger
// than max. If min is positive, then max is also positive, and a
// positive signed integer minus another positive signed integer will
// not overflow.
if (max < INT32_MIN - min) {
// max - min would overflow
return E_FAILED;
}
if (min == INT32_MIN) {
// 0 - INT32_MIN would overflow
return E_FAILED;
}
}

_ijkNormalize(ijk);
return E_SUCCESS;
}

/**
Expand Down
5 changes: 4 additions & 1 deletion src/h3lib/lib/localij.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -563,7 +563,10 @@ H3Error H3_EXPORT(localIjToCell)(H3Index origin, const CoordIJ *ij,
return E_OPTION_INVALID;
}
CoordIJK ijk;
ijToIjk(ij, &ijk);
H3Error ijToIjkError = ijToIjk(ij, &ijk);
if (ijToIjkError) {
return ijToIjkError;
}

return localIjkToCell(origin, &ijk, out);
}
Expand Down
0