Skip to content
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.

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

Incorrect size bounds checks in vehicle viewport hash scan in ViewportAddVehicles #6618

Open
DorpsGek opened this issue Aug 31, 2017 · 5 comments
Labels
bug Something isn't working flyspray This issue is imported from FlySpray (https://bugs.openttd.org/)

Comments

@DorpsGek
Copy link
Member

JGR opened the ticket and wrote:

In ViewportAddVehicles in src/vehicle.cpp there are bounds checks:

if (dpi->width + (70 * ZOOM_LVL_BASE) < (1 << (7 + 6 + ZOOM_LVL_SHIFT))) {
if (dpi->height + (70 * ZOOM_LVL_BASE) < (1 << (6 + 6 + ZOOM_LVL_SHIFT))) {

These are to prevent the extent of the untruncated span from xl to xu and yl to yu from being unable to fit in the hash bit allocation (6 bits each).

In the case of width, in the case where the lower 9 bits of (l - (70 * ZOOM_LVL_BASE)) are greater than the lower 9 bits of r,
dpi->width + (70 * ZOOM_LVL_BASE) can be less than (1 << (7 + 6 + ZOOM_LVL_SHIFT)) even when the the untruncated hash values differ by 0x40, such that the truncated values are the same.
This has the effect that if the viewport re-draw area is the right size and offset, the iteration over the vehicle viewport hash only finds vehicles at the two edges but not in the middle.
This can visually manifest as flickering effects.

To give a concrete example:
Noting that: ZOOM_LVL_BASE = 4, ZOOM_LVL_SHIFT = 2
If: dpi->left = 0x317, dpi->width = 0x7CE9
Then:
dpi->width + (70 * ZOOM_LVL_BASE) = 0x7E01
(1 << (7 + 6 + ZOOM_LVL_SHIFT)) = 0x8000
dpi->width + (70 * ZOOM_LVL_BASE) < (1 << (7 + 6 + ZOOM_LVL_SHIFT)) evaluates to true
l - (70 * ZOOM_LVL_BASE) = 0x1FF, r = 0x8000
xl = 0, xu = 0
Consequently: only vehicles in hash row 0 will be drawn, even though the viewport redraw covers the whole width of the viewport hash

A possible solution for width/x would be to perform the bounds check after doing the shift-right by 9, but before truncating to 6 bits.

Height/y is the same except the shift is by 8 instead of 9.

Reported version: trunk
Operating system: All


This issue was imported from FlySpray: https://bugs.openttd.org/task/6618
@DorpsGek DorpsGek added Core flyspray This issue is imported from FlySpray (https://bugs.openttd.org/) labels Apr 7, 2018
@frosch123 frosch123 removed the Core label Apr 14, 2018
@andythenorth andythenorth added the stale Stale issues label Jan 5, 2019
@andythenorth andythenorth removed the stale Stale issues label Jan 24, 2019
@stale
Copy link

stale bot commented Mar 25, 2019

This issue has been automatically marked as stale because it has not had any activity in the last two months.
If you believe the issue is still relevant, please test on the latest nightly and report back.
It will be closed if no further activity occurs within 7 days.
Thank you for your contributions.

@stale stale bot added the stale Stale issues label Mar 25, 2019
@LordAro
Copy link
Member

LordAro commented Mar 25, 2019

@JGRennison Is this something you'd care to PR?

@stale stale bot removed the stale Stale issues label Mar 25, 2019
@JGRennison
Copy link
Contributor

I'll see what I can do.

For reference the commit in my fork is JGRennison/OpenTTD-patches@d3a1e80

JGRennison added a commit to JGRennison/Upstream-OpenTTD that referenced this issue Apr 5, 2019
Fix incorrect bounds check in ViewportAddVehicles in the case where the
viewport width or height is less than the hash wraparound
distance, however the two bounds still map to the same hash bucket
due to discarding the lower coordinate bits, such that the intermediary
hash buckets are incorrectly not iterated.
@TrueBrain
Copy link
Member

@JGRennison : sorry to dig up an old issue, but the patch you mention, has that survived the test of time? As in, can we just backport it upstream? I can imagine if you did fixes on it over time, hence the question :)

Tnx!

@JGRennison
Copy link
Contributor

git blame suggests that I haven't touched ViewportAddVehicles or any of the viewport hash bounds code at all since then.
I haven't had any further problems with it at my end.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working flyspray This issue is imported from FlySpray (https://bugs.openttd.org/)
Projects
None yet
Development

No branches or pull requests

6 participants