[r7264] Negative allowed goods in transit

[Fifty]

In pak128, with high industry storage numbers, if you set the in_transit_percentage pretty high (say 2000 %), some factories will have a negative number for the maximum number of goods allowed in transit, and thus you can't transport anything there at all. I assume this is a simple integer overflow/wraparound issue.

Some 128 industries where this is often reproducible: Materials Wholesale (planks), Cement Mixer (stone), Goods Factory (planks), Electronics Factory (glass).

[DrSuperGood]

Ok this is based on the nightly code that I modified for my flow system, however I never touched these parts.

The problem lines appear in two locations (horrible procedural coupling...).
1. void fabrik_t::add_supplier(koord ziel)
2. void fabrik_t::rem_supplier(koord pos)

The problem lines are...

Code Select Expand


sint32 max_storage = 1 + ( (w_out.max * welt->get_settings().get_factory_maximum_intransit_percentage() ) >> fabrik_t::precision_bits) / 100;
w.max_transit += max_storage;


There are two problems...
1. Faulty fixed point multiplication logic.
Max attribute is a q10 signed fixed point stored in an int32_t (well equivalently, you use some other declarations). This means that it only has 21 meaningful bits available (32-1 sign -10 fraction) to do the percentage multiplication. As the percentages are usually large (>2000%) this means 11 bits are used to perform the multiplication. This only leaves 10 bits for the actual storage value of the maximum storage of the supplier output (only 1000 units odd...). As you can see this will very likely overflow with some suppliers and since it is a signed 32 integer it will be a pretty random smallish negative number. I am 99% certain this is the problem he is suffering.

2. Unsafe addition. No check for overflow is performed when adding to maximum in-transit value. This means even if the value did not overflow, for very large numbers of suppliers with very large storages and multipliers you could possibly end up with an overflow. In practice this should not really be obtainable as you would need thousands of linked industries with absolutely insane output storage capacities. For this reason I believe this is not the cause of the problem, but is only a minor hidden fault.

Well to help speed this along here is the solution...
1. Correct fixed point mathematics logic. We have a 32bit multiplied by a 16bit so we need a field with at least 48 bits (round up to 64). You then reduce the value to the form desired (not percentage, q0). Since maximum storage is always positive it will have only 31 bits of information practically, combined with 16 bit percentage gives 47 bits, which after converting from q10 to q0 gives 37 bits and from percent to number (100 is about 6 to 7 bits) 31 to30 bits which is representable in a signed 32 bit without overflow so not further checking is required with the current constants. The fact I highly doubt you will see industries with 2,097,151 output storage means this is even more safe (and maybe that should be capped for yet more safety?).
2. Simply add an overflowflow check (number turns negative) which forces it to the maximum signed 32 bit value.

Here is the fixed code.

Code Select Expand


sint32 max_storage = (sint32)(1 + ( ((sint64)w_out.max * (sint64)welt->get_settings().get_factory_maximum_intransit_percentage() ) >> fabrik_t::precision_bits) / 100);
w.max_transit += max_storage;
if(  w.max_transit < 0  ) w.max_transit = 2147483647; // The maximum positive amount the variable allows!


This is assuming TRANSIT_DISTANCE is not defined. If it is the problem will be similar but a different piece of fixed code is needed.

A minor note...
Depending on how smart the compiler is it may be better to do a single division of ((1 << fabrik_t::precision_bits) * 100) since that is more likely to compile to a constant and this way only a single division operation is run instead of a shift and a division. However one can always hope compilers are smart enough to detect such a thing and optimize it appropriately.
If fabrik_t::precision_bits was lowered, overflow checks might be required.

[Ters]

I think we should rather use INT32_MAX than write out the number.

[DrSuperGood]

I think we should rather use INT32_MAX than write out the number.

There is also no advantage I can think of using custom declared int types like "sint32" over the standard defined int types "int32_t" if you are including stdint.h in order to get INT32_MAX macro. I thought extra effort was being taken to avoid coupling to stdint.h looking at the way the game was programed.

In any case it should at least be 0x7fffffff. Not sure what I was thinking when I just plonked in a decimal number.

[Ters]

Well, we can always define our own constants along with our own types. INT32_MAX, like int32_t, probably isn't available on all supported platforms anyway. I blame the heat and stubborn wallpaper for me not thinking that far. My point is that I don't like typing out constants like this all around the code. If the data type is changes, it's a lot of work to find and change them all. Typos also become more likely. And the decimal value isn't as obvious, as you found out also.

[DrSuperGood]

probably isn't available on all supported platforms anyway

ARM, G++ (this is what the main release builds are made with, the C++ compiler of GCC) and VC++ should all support it now. I am also vaguely sure apple's compilers will support it but I cannot say for sure as I do not use the platform. The only platforms that do not support it are very old or very obscure. I would personally recommend the migration to stdint.h as it solves a lot of problems (such as that infamous union with integer and pointer). However this is a long term major project decision, nothing about fixing the overflow with industry maximum in transit.

Until such a constant is defined this should be used to fix the problem?

Code Select Expand



sint32 max_storage = (sint32)(1 + ( ((sint64)w_out.max * (sint64)welt->get_settings().get_factory_maximum_intransit_percentage() ) >> fabrik_t::precision_bits) / 100);
w.max_transit += max_storage;
if(  w.max_transit < 0  ) w.max_transit = 0x7fffffff; // The maximum positive amount the variable allows!


I am sure every programmer would instantly recognize that as the max for a int32_t.

It is really bugging people on fifty's 128 server atm...

[Ters]

ARM, G++ (this is what the main release builds are made with, the C++ compiler of GCC) and VC++ should all support it now.

By "now", I assume you mean that the newest versions support it. Unfortunately, the newest version isn't always available. I think prissi has a fancy for a platform, which I don't remember the name of in a hurry, that has not been up to date with it's GCC. mingw has also been less actively maintained lately, and core GCC is discussing dropping it as an official GCC platform. (Actually replacing it with mingw64, but that project doesn't even have official releases!) The latest mingw headers and/or runtime are also buggy, so Simutrans will crash if they are used. GCC has however been ahead of the standard for some time, so it likely has had these integer types for a long time. As for MSVC, people haven't stopped using MSVC6 yet! (In a sense, Simutrans built with mingw is still using it, as it is piggybacking on msvcrt.dll, which Microsoft won't maintain beyond what Windows itself needs.) Simutrans is coded by hobbyists, who might not be able to afford buying something newer.

[DrSuperGood]

By "now", I assume you mean that the newest versions support it.

No? Any compiler compatible with the standard defined in 1999 (c++99) (15 years ago) should be compatible with it and have access to stdint. It is hardly a cutting edge feature (c++11). Yes I do understand that some people might be using computer systems that are 10-15 years old but do they really not have access to a c++99 compiler?

In any case a constant like that is trivial in the code as anyone worth their salt as a programmer would know what that constant represents. As it is, a lot of "should be" constants are hard-coded values in the program file and those are much more a concern than a single hard-coded stdint constant.

[Ters]

No? Any compiler compatible with the standard defined in 1999 (c++99) (15 years ago) should be compatible with it and have access to stdint. It is hardly a cutting edge feature (c++11). Yes I do understand that some people might be using computer systems that are 10-15 years old but do they really not have access to a c++99 compiler?

There is no C++99. There is C99, but MSVC doesn't really support C, or C99 at least (http://connect.microsoft.com/VisualStudio/feedback/details/345360/visual-c-should-support-c99). As such, it only supports what parts of C99 was included in C++11, although some C++11 support may have started to appear before 2011.

In any case a constant like that is trivial in the code as anyone worth their salt as a programmer would know what that constant represents. As it is, a lot of "should be" constants are hard-coded values in the program file and those are much more a concern than a single hard-coded stdint constant.

One has to start somewhere sometime. But this is something a committer can add when committing if they feel like it.

[prissi]

Thanks, overflow check in in r7426.