The International Simutrans Forum

 

Author Topic: simgraph int overflows  (Read 1064 times)

0 Members and 1 Guest are viewing this topic.

Offline Freahk

  • Devotee
  • *
  • Posts: 1473
  • Languages: DE, EN
simgraph int overflows
« on: April 13, 2021, 11:06:16 PM »
Simgraph handles all the drawing using the koord type, which makes use of KOORD_VAL, which is currently short.
minimap makes use of scr_coord instead, which makes use of scr_coord_val, which is currently sint32

Thus, sint32 will be casted to short in many places, which might be troublesome.
in practice, the maximum zoom in is limited on huge maps, so overflows won't occur.
Playing on an 8k map, however, limited the zoom_in to 4, which turned out to be insufficient.
As most parts of the minimap render just fine without that restriction, it was removed in extended.

However, some objects like lines and bezier curves might be defined far outside of the actual viewport causing overflows.
Those lines might also be clipped to the short range, but that is rather hacky.


There are a few possible solutions:
1. make use of scr_coord, aka sint32 in simgraph
2. make use of floating point in simgraph (should be network safe)
3. clip everything to short before passing to simgraph functions

I'd prefer floats here. It simplifies the code as it gets rid of some int hacking. It solves the overflow isssues and it will be even faster than int whenever the compiler can make use of SSE2 vector instructions.
The huge downside of floats, which network sync, should not kick in here.

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 10573
  • Languages: De,EN,JP
Re: simgraph int overflows
« Reply #1 on: April 14, 2021, 04:50:37 AM »
Floats are slower than int since SSE2 cannot work on single number but only on vectors or matrices (which you do not need to handle lines etc.) Moreover, in the end you need to round the float anyway to a pixel, so there is another arithmetric operation needed. And with floats you are risking gaps in line at some points due to rounding errors. (I once had a display routine for lines using floats and it was rather disappointing.) Internally the line and other drawing routines need ints.

Using sint32 (scr_coord_val) instead of sint16 is not such a big change, and can be probably done without side effects. Also some scroll bar ran in this issue as well and thus use sint32.

Offline Freahk

  • Devotee
  • *
  • Posts: 1473
  • Languages: DE, EN
Re: simgraph int overflows
« Reply #2 on: April 14, 2021, 10:06:32 AM »
SSE2 cannot work on single number but only on vectors or matrices
Most simgraph functions work on the output frame buffer using loops and can make use of vectorisation in many places. That means "exectute multiple loop iterations in a single instruction"
However, as many of these are as simple as "set those pixels to this number" the additional conversion from float to short might kill the gains.

I am wondering how precision of a float is an issue here as it's of at least int precision up to 2^22 - 1, which is more than those 2^15 -  which a short can represent.

Anyways, I'll go for scr_coord for now. It should be rather simple and solve the overflow issues on huge maps.
Later on, I might give float calculations a chance internally.
« Last Edit: April 14, 2021, 10:32:41 AM by Freahk »

Offline Ters

  • Coder/patcher
  • Devotee
  • *
  • Posts: 5691
  • Languages: EN, NO
Re: simgraph int overflows
« Reply #3 on: April 14, 2021, 02:12:25 PM »
Sticking to integer types is best. They can be vectorized just as well on SSE2 onwards, so that is not something favoring floats.

Vectorization does however require alignment, at least to run at full power.

Offline Freahk

  • Devotee
  • *
  • Posts: 1473
  • Languages: DE, EN
Re: simgraph int overflows
« Reply #4 on: April 14, 2021, 04:41:38 PM »
You are totally right, shame on me.

What did I do a few days ago? Oh, I threw a rewrite rule introducing vectorisation on a program operating on integers :o
I should better have a coffee or sleep... Or both of it.

In any case, scr_coord is on its way into standard as soon as I get the CMake set up...

Offline Freahk

  • Devotee
  • *
  • Posts: 1473
  • Languages: DE, EN

Offline ceeac

  • Devotee
  • *
  • Posts: 243
Re: simgraph int overflows
« Reply #6 on: April 18, 2021, 10:02:34 AM »
Some comments about the patch:
  • In some cases, there are spaces for indentation. These should be tabs like the rest of the code.
  • In simcity.cc, x and y are initialized as sint16, compared to sint16 and used as sint16 so they should be sint16, not int.
  • In simgraph16.cc: What about using the fixed width types instead of long? long is 4 bytes on 64 bit Windows, but 8 bytes on 64 bit Linux.
    Using the types from simtypes.h prevents the inconsistency.

Performance does not seem to be affected noticeably by the patch - 22-23 fps on the yoshi test map on full zoom out with full optimizations for both 64 bit and 32 bit builds.

Offline Freahk

  • Devotee
  • *
  • Posts: 1473
  • Languages: DE, EN
Re: simgraph int overflows
« Reply #7 on: April 18, 2021, 10:35:55 PM »
Fair review.
Not sure about 1. tbh.
There are numerous of locations in the code where spaces are used instead of tabs.
Fixed in some locations, but there might be some missing.

2 and 3 should be fixed.
About performance: I didn't measure any noticeable performance impact on my machine (64 bit Linux build)
« Last Edit: April 18, 2021, 10:57:02 PM by Freahk »

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 10573
  • Languages: De,EN,JP
Re: simgraph int overflows
« Reply #8 on: April 19, 2021, 12:38:38 AM »
Same link as above for a patch?

Offline Freahk

  • Devotee
  • *
  • Posts: 1473
  • Languages: DE, EN
Re: simgraph int overflows
« Reply #9 on: April 19, 2021, 12:43:14 AM »
Yes, it's a permalink to the constantly updating diff in between my standard-master branch and the aburch master
« Last Edit: April 19, 2021, 01:07:04 AM by Freahk »

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 10573
  • Languages: De,EN,JP
Re: simgraph int overflows
« Reply #10 on: April 21, 2021, 12:16:12 PM »
Indentation for code for the first letter should be tabs. after that there is indeed change. I think I caught all wrong spaces. Incorporated in r9737, thank you
« Last Edit: April 21, 2021, 12:33:22 PM by prissi »

Offline Freahk

  • Devotee
  • *
  • Posts: 1473
  • Languages: DE, EN
Re: simgraph int overflows
« Reply #11 on: April 22, 2021, 01:26:46 AM »
The industry sorting introduced in r9736 does not build on gcc.
This tiny patch will fix the issue.
https://github.com/aburch/simutrans/compare/master...irgend42:standard-fixes.patch
« Last Edit: April 22, 2021, 01:36:56 AM by Freahk »

Offline ceeac

  • Devotee
  • *
  • Posts: 243
Re: simgraph int overflows
« Reply #12 on: April 22, 2021, 04:33:52 AM »
The industry sorting introduced in r9736 does not build on gcc
Fixed now (in r9738).

Offline Andarix

  • *
  • Posts: 256
  • Languages: de
Re: simgraph int overflows
« Reply #13 on: April 22, 2021, 10:40:46 AM »
r9739

server (non GUI) windows/linux not compile

linux
Quote
2021-04-22T09:24:07.3458246Z ===> HOSTCXX display/simgraph0.cc
2021-04-22T09:24:07.5916721Z display/simgraph0.cc: In function ‘sint16 display_get_width()’:
2021-04-22T09:24:07.5919468Z display/simgraph0.cc:77:8: error: ambiguating new declaration of ‘sint16 display_get_width()’
2021-04-22T09:24:07.5922432Z  sint16 display_get_width()
2021-04-22T09:24:07.5925816Z         ^~~~~~~~~~~~~~~~~
2021-04-22T09:24:07.5926545Z In file included from display/../descriptor/image.h:10:0,
2021-04-22T09:24:07.5927598Z                  from display/simgraph0.cc:8:
2021-04-22T09:24:07.5928714Z display/../descriptor/../display/simgraph.h:159:15: note: old declaration ‘scr_coord_val display_get_width()’
2021-04-22T09:24:07.5929505Z  scr_coord_val display_get_width();
2021-04-22T09:24:07.5929924Z                ^~~~~~~~~~~~~~~~~
2021-04-22T09:24:07.5930711Z display/simgraph0.cc: In function ‘sint16 display_get_height()’:
2021-04-22T09:24:07.5931815Z display/simgraph0.cc:82:8: error: ambiguating new declaration of ‘sint16 display_get_height()’
2021-04-22T09:24:07.5932570Z  sint16 display_get_height()
2021-04-22T09:24:07.5932965Z         ^~~~~~~~~~~~~~~~~~
2021-04-22T09:24:07.5933489Z In file included from display/../descriptor/image.h:10:0,
2021-04-22T09:24:07.5934099Z                  from display/simgraph0.cc:8:
2021-04-22T09:24:07.5935139Z display/../descriptor/../display/simgraph.h:160:15: note: old declaration ‘scr_coord_val display_get_height()’
2021-04-22T09:24:07.5935926Z  scr_coord_val display_get_height();
2021-04-22T09:24:07.5936485Z                ^~~~~~~~~~~~~~~~~~
2021-04-22T09:24:07.6222465Z common.mk:50: recipe for target 'build/default/display/simgraph0.o' failed
2021-04-22T09:24:07.6230358Z make: *** [build/default/display/simgraph0.o] Error 1
2021-04-22T09:24:07.6242449Z ##[error]Process completed with exit code 2.

windows
Quote
2021-04-22T09:24:21.4373128Z "D:\a\simutrans\simutrans\Simutrans-Server.vcxproj" (default target) (1) ->
2021-04-22T09:24:21.4373948Z (ClCompile target) ->
2021-04-22T09:24:21.4375086Z   display\simgraph0.cc(78): error C2556: 'sint16 display_get_width(void)': overloaded function differs only by return type from 'scr_coord_val display_get_width(void)' [D:\a\simutrans\simutrans\Simutrans-Server.vcxproj]
2021-04-22T09:24:21.4376691Z   display\simgraph0.cc(77): error C2371: 'display_get_width': redefinition; different basic types [D:\a\simutrans\simutrans\Simutrans-Server.vcxproj]
2021-04-22T09:24:21.4378328Z   display\simgraph0.cc(83): error C2556: 'sint16 display_get_height(void)': overloaded function differs only by return type from 'scr_coord_val display_get_height(void)' [D:\a\simutrans\simutrans\Simutrans-Server.vcxproj]
2021-04-22T09:24:21.4379948Z   display\simgraph0.cc(82): error C2371: 'display_get_height': redefinition; different basic types [D:\a\simutrans\simutrans\Simutrans-Server.vcxproj]
2021-04-22T09:24:21.4381089Z
2021-04-22T09:24:21.4381469Z     16 Warning(s)
2021-04-22T09:24:21.4381849Z     4 Error(s)
2021-04-22T09:24:21.4382141Z
2021-04-22T09:24:21.4382518Z Time Elapsed 00:02:32.71
2021-04-22T09:24:22.6350151Z Copy-Item: D:\a\_temp\0683fedf-038f-41a4-a0b0-d9ad4e5cdc4e.ps1:3
2021-04-22T09:24:22.6351221Z Line |
2021-04-22T09:24:22.6351829Z    3 |  copy Simutrans_Server.exe simutrans\Simutrans-Server.exe
2021-04-22T09:24:22.6352411Z      |  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2021-04-22T09:24:22.6353283Z      | Cannot find path 'D:\a\simutrans\simutrans\Simutrans_Server.exe' because it does not exist.
2021-04-22T09:24:22.6354582Z 
2021-04-22T09:24:22.6558013Z ##[error]Process completed with exit code 1.

Offline Freahk

  • Devotee
  • *
  • Posts: 1473
  • Languages: DE, EN
Re: simgraph int overflows
« Reply #14 on: April 22, 2021, 11:34:31 AM »
Fixed in latest standard-fixes
https://github.com/aburch/simutrans/compare/master...irgend42:standard-fixes.patch

Is there any proper gitish way of messing around with patches?
Whenever a patch is applied, I have to merge the upstream branch into my own branch, which already is basically the same, but git does not know this.
Either I merge those changes in, which results in a kind of broken history or I rebase, which is evil on public repositories.

Offline Roboron

  • Devotee
  • *
  • Posts: 261
    • Las Galácticas Aventuras de Komoyo Diga
  • Languages: ES, EN
Re: simgraph int overflows
« Reply #15 on: April 22, 2021, 11:57:51 AM »
Why do you say rebase is evil?

Whatever, if the patch has been incorporated, then the "git way" is to remove the branch (since it has served its purpose), and create a new one if other changes are needed.

Offline Freahk

  • Devotee
  • *
  • Posts: 1473
  • Languages: DE, EN
Re: simgraph int overflows
« Reply #16 on: April 22, 2021, 12:12:40 PM »
Rebase is nice in some situations (local repositories) but evil in others (quite often when public repositories are involved)
That's because it rewrites the commit history. Work based on a specific commit will then be decoupled from the new one.

Pushing such a rebase to the public repository is rejected by default for that reason, so you have to force the push.

Deleting feature branches is not quite gitish tbh for the same reason but the best we can come up with in this situation I guess.

Offline Dwachs

  • DevTeam, Coder/patcher
  • Administrator
  • *
  • Posts: 4863
  • Languages: EN, DE, AT
Re: simgraph int overflows
« Reply #17 on: April 22, 2021, 12:15:19 PM »
The easiest way is to start your own git-svn repo locally (which then is not a fork of the github aburch mirror). In this way, updates from svn happen quite seemless.

Offline Roboron

  • Devotee
  • *
  • Posts: 261
    • Las Galácticas Aventuras de Komoyo Diga
  • Languages: ES, EN
Re: simgraph int overflows
« Reply #18 on: April 22, 2021, 12:37:35 PM »
There are two kind of branches from my experience:

1 - development branches - such as the one you are talking about. You push commits to this branch, then delete it after it gets merged upstream. Yes, this is the common procedure.
2 - experimental/feature branches - used to implement features/changes that for some reason can't be merged upstream (an example would be Extended and/or OTRP). Now it makes sense to keep those branches around, until the experiment fails or the feature is no longer needed (if such time ever comes).

Offline Ters

  • Coder/patcher
  • Devotee
  • *
  • Posts: 5691
  • Languages: EN, NO
Re: simgraph int overflows
« Reply #19 on: April 25, 2021, 12:13:09 PM »
Pushing such a rebase to the public repository is rejected by default for that reason, so you have to force the push.

Force pushing is the evil part, not the rebase. If a rebase requires a force push, rebasing was likely not the proper solution to the problem (or the problem was misidentified in the first place).

Although there are some arguments that rebasing changes the conceptual history of the code, that has more to do with what people want from their code management tools. There are many different philosophies on what commit logs are for, and therefore how to set up branches, and also whether to merge or cherry-pick. Some seems to consider commits older than a year, maybe even less, as worthless and useless. On the other hand, I have often found myself digging into ten year old commits to figure out how a part of the code is the way it is, mostly at work, but also for Simutrans. (After switching to git at work, this has gotten harder, as git does not have true file history.)

If one doesn't create branches for features/patches, but do everything on master, or whatever is the main branch for development, rebasing rather than merging when pulling would probably be better. Unless the patch has been altered prior to being merged by someone else, git will mostly realize the commit being rebased has already happened on the new base, and move on without making a fuss. If there are some differences, you can either resolve the issue like any other merge conflict, or just tell git to skip your version of the commit and keep rebasing.

Personally, I rarely use pull. I rather fetch first, to see what is incoming before getting my branch heads up to date with origin. Another reason, is that I may have several branches that I want to track origin, or I'm currently on a feature branch, but want to get master or similar core branches up-to-date. I also often use worktrees.