Mercurial > hg > openttd
changeset 7763:b66a3cb83e69 draft
(svn r11312) -Codechange: implement a overflow safe integer and use that for money and don't misuses CommandCost to have a overflow safe integer. Based on a patch by Noldo.
| author | rubidium <rubidium@openttd.org> |
|---|---|
| date | Sat, 20 Oct 2007 14:51:09 +0000 (2007-10-20) |
| parents | 15549e3a048b |
| children | 4cdd7ef382fe |
| files | src/ai/trolly/trolly.cpp src/build_vehicle_gui.cpp src/command.cpp src/console_cmds.cpp src/economy.cpp src/engine_gui.cpp src/graph_gui.cpp src/helpers.hpp src/openttd.h src/rail_cmd.cpp src/road_cmd.cpp src/strings.cpp |
| diffstat | 12 files changed, 164 insertions(+), 39 deletions(-) [+] |
line wrap: on
line diff
--- a/src/ai/trolly/trolly.cpp +++ b/src/ai/trolly/trolly.cpp @@ -954,7 +954,7 @@ // Check if we have enough money for it! if (p->ainew.new_cost > p->player_money - AI_MINIMUM_MONEY) { // Too bad.. - DEBUG(ai, 1, "Insufficient funds to build route (%d)", p->ainew.new_cost); + DEBUG(ai, 1, "Insufficient funds to build route (%" OTTD_PRINTF64 "d)", (int64)p->ainew.new_cost); p->ainew.state = AI_STATE_NOTHING; return; } @@ -1086,7 +1086,7 @@ } } - DEBUG(ai, 1, "Finished building path, cost: %d", p->ainew.new_cost); + DEBUG(ai, 1, "Finished building path, cost: %" OTTD_PRINTF64 "d", (int64)p->ainew.new_cost); p->ainew.state = AI_STATE_BUILD_DEPOT; } }
--- a/src/build_vehicle_gui.cpp +++ b/src/build_vehicle_gui.cpp @@ -226,8 +226,8 @@ * Because of this, the return value have to be reversed as well and we return b - a instead of a - b. * Another thing is that both power and running costs should be doubled for multiheaded engines. * Since it would be multipling with 2 in both numerator and denumerator, it will even themselves out and we skip checking for multiheaded. */ - Money va = (rvi_a->running_cost_base * _price.running_rail[rvi_a->running_cost_class]) / max((uint16)1, rvi_a->power); - Money vb = (rvi_b->running_cost_base * _price.running_rail[rvi_b->running_cost_class]) / max((uint16)1, rvi_b->power); + Money va = (rvi_a->running_cost_base * _price.running_rail[rvi_a->running_cost_class]) / max(1U, (uint)rvi_a->power); + Money vb = (rvi_b->running_cost_base * _price.running_rail[rvi_b->running_cost_class]) / max(1U, (uint)rvi_b->power); int r = ClampToI32(vb - va); return _internal_sort_order ? -r : r;
--- a/src/command.cpp +++ b/src/command.cpp @@ -677,25 +677,13 @@ CommandCost CommandCost::AddCost(Money cost) { - /* Overflow protection */ - if (cost < 0 && (this->cost + cost) > this->cost) { - this->cost = INT64_MIN; - } else if (cost > 0 && (this->cost + cost) < this->cost) { - this->cost = INT64_MAX; - } else { - this->cost += cost; - } + this->cost += cost; return *this; } CommandCost CommandCost::MultiplyCost(int factor) { - /* Overflow protection */ - if (factor != 0 && (INT64_MAX / myabs(factor)) < myabs(this->cost)) { - this->cost = (this->cost < 0 == factor < 0) ? INT64_MAX : INT64_MIN; - } else { - this->cost *= factor; - } + this->cost *= factor; return *this; }
--- a/src/console_cmds.cpp +++ b/src/console_cmds.cpp @@ -1249,7 +1249,7 @@ GetString(buffer, STR_00D1_DARK_BLUE + _player_colors[p->index], lastof(buffer)); IConsolePrintF(8, "#:%d(%s) Company Name: '%s' Year Founded: %d Money: %" OTTD_PRINTF64 "d Loan: %" OTTD_PRINTF64 "d Value: %" OTTD_PRINTF64 "d (T:%d, R:%d, P:%d, S:%d) %sprotected", - p->index + 1, buffer, npi->company_name, p->inaugurated_year, p->player_money, p->current_loan, CalculateCompanyValue(p), + p->index + 1, buffer, npi->company_name, p->inaugurated_year, (int64)p->player_money, (int64)p->current_loan, (int64)CalculateCompanyValue(p), /* trains */ npi->num_vehicle[0], /* lorry + bus */ npi->num_vehicle[1] + npi->num_vehicle[2], /* planes */ npi->num_vehicle[3],
--- a/src/economy.cpp +++ b/src/economy.cpp @@ -95,7 +95,7 @@ value.AddCost(-p->current_loan); value.AddCost(p->player_money); - return max(value.GetCost(), 1LL); + return max(value.GetCost(), (Money)1); } /** if update is set to true, the economy is updated with this score
--- a/src/engine_gui.cpp +++ b/src/engine_gui.cpp @@ -120,7 +120,7 @@ static void DrawTrainEngineInfo(EngineID engine, int x, int y, int maxw) { const RailVehicleInfo *rvi = RailVehInfo(engine); - uint multihead = (rvi->railveh_type == RAILVEH_MULTIHEAD) ? 1 : 0; + int multihead = (rvi->railveh_type == RAILVEH_MULTIHEAD) ? 1 : 0; SetDParam(0, (_price.build_railvehicle >> 3) * rvi->base_cost >> 5); SetDParam(2, rvi->max_speed * 10 / 16);
--- a/src/graph_gui.cpp +++ b/src/graph_gui.cpp @@ -41,8 +41,8 @@ }; /* Apparently these don't play well with enums. */ -static const int64 INVALID_DATAPOINT = INT64_MAX; // Value used for a datapoint that shouldn't be drawn. -static const uint INVALID_DATAPOINT_POS = UINT_MAX; // Used to determine if the previous point was drawn. +static const OverflowSafeInt64 INVALID_DATAPOINT = INT64_MAX; // Value used for a datapoint that shouldn't be drawn. +static const uint INVALID_DATAPOINT_POS = UINT_MAX; // Used to determine if the previous point was drawn. struct GraphDrawer { uint excluded_data; ///< bitmask of the datasets that shouldn't be displayed. @@ -70,9 +70,9 @@ static void DrawGraph(const GraphDrawer *gw) { - uint x, y; ///< Reused whenever x and y coordinates are needed. - int64 highest_value; ///< Highest value to be drawn. - int x_axis_offset; ///< Distance from the top of the graph to the x axis. + uint x, y; ///< Reused whenever x and y coordinates are needed. + OverflowSafeInt64 highest_value; ///< Highest value to be drawn. + int x_axis_offset; ///< Distance from the top of the graph to the x axis. /* the colors and cost array of GraphDrawer must accomodate * both values for cargo and players. So if any are higher, quit */ @@ -515,7 +515,7 @@ if (p->is_active) { gd.colors[numd] = _colour_gradient[p->player_color][6]; for (int j = gd.num_on_x_axis, i = 0; --j >= 0;) { - gd.cost[numd][i] = (j >= p->num_valid_stat_ent) ? INVALID_DATAPOINT : p->old_economy[j].delivered_cargo; + gd.cost[numd][i] = (j >= p->num_valid_stat_ent) ? INVALID_DATAPOINT : (OverflowSafeInt64)p->old_economy[j].delivered_cargo; i++; } } @@ -582,7 +582,7 @@ if (p->is_active) { gd.colors[numd] = _colour_gradient[p->player_color][6]; for (int j = gd.num_on_x_axis, i = 0; --j >= 0;) { - gd.cost[numd][i] = (j >= p->num_valid_stat_ent) ? INVALID_DATAPOINT : p->old_economy[j].performance_history; + gd.cost[numd][i] = (j >= p->num_valid_stat_ent) ? INVALID_DATAPOINT : (OverflowSafeInt64)p->old_economy[j].performance_history; i++; } }
--- a/src/helpers.hpp +++ b/src/helpers.hpp @@ -158,4 +158,139 @@ t = (T)(t ^ ((T)1 << bit_index)); } +/** + * Overflow safe template for integers, i.e. integers that will never overflow + * you multiply the maximum value with 2, or add 2, or substract somethng from + * the minimum value, etc. + * @param T the type these integers are stored with. + * @param T_MAX the maximum value for the integers. + * @param T_MIN the minimum value for the integers. + */ +template <class T, T T_MAX, T T_MIN> +class OverflowSafeInt +{ +private: + /** The non-overflow safe backend to store the value in. */ + T m_value; +public: + OverflowSafeInt() : m_value(0) { } + + OverflowSafeInt(const OverflowSafeInt& other) { this->m_value = other.m_value; } + OverflowSafeInt(const int64 int_) { this->m_value = int_; } + + FORCEINLINE OverflowSafeInt& operator = (const OverflowSafeInt& other) { this->m_value = other.m_value; return *this; } + + FORCEINLINE OverflowSafeInt operator - () const { return OverflowSafeInt(-this->m_value); } + + /** + * Safe implementation of addition. + * @param other the amount to add + * @note when the addition would yield more than T_MAX (or less than T_MIN), + * it will be T_MAX (respectively T_MIN). + */ + FORCEINLINE OverflowSafeInt& operator += (const OverflowSafeInt& other) + { + if ((T_MAX - myabs(other.m_value)) < myabs(this->m_value) && + (this->m_value < 0) == (other.m_value < 0)) { + this->m_value = (this->m_value < 0) ? T_MIN : T_MAX ; + } else { + this->m_value += other.m_value; + } + return *this; + } + + /* Operators for addition and substraction */ + FORCEINLINE OverflowSafeInt operator + (const OverflowSafeInt& other) const { OverflowSafeInt result = *this; result += other; return result; } + FORCEINLINE OverflowSafeInt operator + (const int other) const { OverflowSafeInt result = *this; result += (int64)other; return result; } + FORCEINLINE OverflowSafeInt operator + (const uint other) const { OverflowSafeInt result = *this; result += (int64)other; return result; } + FORCEINLINE OverflowSafeInt& operator -= (const OverflowSafeInt& other) { return *this += (-other); } + FORCEINLINE OverflowSafeInt operator - (const OverflowSafeInt& other) const { OverflowSafeInt result = *this; result -= other; return result; } + FORCEINLINE OverflowSafeInt operator - (const int other) const { OverflowSafeInt result = *this; result -= (int64)other; return result; } + FORCEINLINE OverflowSafeInt operator - (const uint other) const { OverflowSafeInt result = *this; result -= (int64)other; return result; } + + FORCEINLINE OverflowSafeInt& operator ++ (int) { return *this += 1; } + FORCEINLINE OverflowSafeInt& operator -- (int) { return *this += -1; } + + /** + * Safe implementation of multiplication. + * @param factor the factor to multiply this with. + * @note when the multiplication would yield more than T_MAX (or less than T_MIN), + * it will be T_MAX (respectively T_MIN). + */ + FORCEINLINE OverflowSafeInt& operator *= (const int factor) + { + if (factor != 0 && (T_MAX / myabs(factor)) < myabs(this->m_value)) { + this->m_value = ((this->m_value < 0) == (factor < 0)) ? T_MAX : T_MIN ; + } else { + this->m_value *= factor ; + } + return *this; + } + + /* Operators for multiplication */ + FORCEINLINE OverflowSafeInt operator * (const int64 factor) const { OverflowSafeInt result = *this; result *= factor; return result; } + FORCEINLINE OverflowSafeInt operator * (const int factor) const { OverflowSafeInt result = *this; result *= (int64)factor; return result; } + FORCEINLINE OverflowSafeInt operator * (const uint factor) const { OverflowSafeInt result = *this; result *= (int64)factor; return result; } + FORCEINLINE OverflowSafeInt operator * (const uint16 factor) const { OverflowSafeInt result = *this; result *= (int64)factor; return result; } + FORCEINLINE OverflowSafeInt operator * (const byte factor) const { OverflowSafeInt result = *this; result *= (int64)factor; return result; } + + /* Operators for division */ + FORCEINLINE OverflowSafeInt& operator /= (const int divisor) { this->m_value /= divisor; return *this; } + FORCEINLINE OverflowSafeInt operator / (const OverflowSafeInt& divisor) const { OverflowSafeInt result = *this; result /= divisor.m_value; return result; } + FORCEINLINE OverflowSafeInt operator / (const int divisor) const { OverflowSafeInt result = *this; result /= divisor; return result; } + FORCEINLINE OverflowSafeInt operator / (const uint divisor) const { OverflowSafeInt result = *this; result /= (int)divisor; return result; } + + /* Operators for modulo */ + FORCEINLINE OverflowSafeInt& operator %= (const int divisor) { this->m_value %= divisor; return *this; } + FORCEINLINE OverflowSafeInt operator % (const int divisor) const { OverflowSafeInt result = *this; result %= divisor; return result; } + + /* Operators for shifting */ + FORCEINLINE OverflowSafeInt& operator <<= (const int shift) { this->m_value <<= shift; return *this; } + FORCEINLINE OverflowSafeInt operator << (const int shift) const { OverflowSafeInt result = *this; result <<= shift; return result; } + FORCEINLINE OverflowSafeInt& operator >>= (const int shift) { this->m_value >>= shift; return *this; } + FORCEINLINE OverflowSafeInt operator >> (const int shift) const { OverflowSafeInt result = *this; result >>= shift; return result; } + + /* Operators for (in)equality when comparing overflow safe ints */ + FORCEINLINE bool operator == (const OverflowSafeInt& other) const { return this->m_value == other.m_value; } + FORCEINLINE bool operator != (const OverflowSafeInt& other) const { return !(*this == other); } + FORCEINLINE bool operator > (const OverflowSafeInt& other) const { return this->m_value > other.m_value; } + FORCEINLINE bool operator >= (const OverflowSafeInt& other) const { return this->m_value >= other.m_value; } + FORCEINLINE bool operator < (const OverflowSafeInt& other) const { return !(*this >= other); } + FORCEINLINE bool operator <= (const OverflowSafeInt& other) const { return !(*this > other); } + + /* Operators for (in)equality when comparing non-overflow safe ints */ + FORCEINLINE bool operator == (const int other) const { return this->m_value == other; } + FORCEINLINE bool operator != (const int other) const { return !(*this == other); } + FORCEINLINE bool operator > (const int other) const { return this->m_value > other; } + FORCEINLINE bool operator >= (const int other) const { return this->m_value >= other; } + FORCEINLINE bool operator < (const int other) const { return !(*this >= other); } + FORCEINLINE bool operator <= (const int other) const { return !(*this > other); } + + FORCEINLINE operator int64 () const { return this->m_value; } +}; + +/* Sometimes we got int64 operator OverflowSafeInt instead of vice versa. Handle that properly */ +template <class T, int64 T_MAX, int64 T_MIN> FORCEINLINE OverflowSafeInt<T, T_MAX, T_MIN> operator + (int64 a, OverflowSafeInt<T, T_MAX, T_MIN> b) { return b + a; } +template <class T, int64 T_MAX, int64 T_MIN> FORCEINLINE OverflowSafeInt<T, T_MAX, T_MIN> operator - (int64 a, OverflowSafeInt<T, T_MAX, T_MIN> b) { return -b + a; } +template <class T, int64 T_MAX, int64 T_MIN> FORCEINLINE OverflowSafeInt<T, T_MAX, T_MIN> operator * (int64 a, OverflowSafeInt<T, T_MAX, T_MIN> b) { return b * a; } +template <class T, int64 T_MAX, int64 T_MIN> FORCEINLINE OverflowSafeInt<T, T_MAX, T_MIN> operator / (int64 a, OverflowSafeInt<T, T_MAX, T_MIN> b) { return (OverflowSafeInt<T, T_MAX, T_MIN>)a / (int)b; } + +/* Sometimes we got int operator OverflowSafeInt instead of vice versa. Handle that properly */ +template <class T, int64 T_MAX, int64 T_MIN> FORCEINLINE OverflowSafeInt<T, T_MAX, T_MIN> operator + (int a, OverflowSafeInt<T, T_MAX, T_MIN> b) { return b + a; } +template <class T, int64 T_MAX, int64 T_MIN> FORCEINLINE OverflowSafeInt<T, T_MAX, T_MIN> operator - (int a, OverflowSafeInt<T, T_MAX, T_MIN> b) { return -b + a; } +template <class T, int64 T_MAX, int64 T_MIN> FORCEINLINE OverflowSafeInt<T, T_MAX, T_MIN> operator * (int a, OverflowSafeInt<T, T_MAX, T_MIN> b) { return b * a; } +template <class T, int64 T_MAX, int64 T_MIN> FORCEINLINE OverflowSafeInt<T, T_MAX, T_MIN> operator / (int a, OverflowSafeInt<T, T_MAX, T_MIN> b) { return (OverflowSafeInt<T, T_MAX, T_MIN>)a / (int)b; } + +/* Sometimes we got uint operator OverflowSafeInt instead of vice versa. Handle that properly */ +template <class T, int64 T_MAX, int64 T_MIN> FORCEINLINE OverflowSafeInt<T, T_MAX, T_MIN> operator + (uint a, OverflowSafeInt<T, T_MAX, T_MIN> b) { return b + a; } +template <class T, int64 T_MAX, int64 T_MIN> FORCEINLINE OverflowSafeInt<T, T_MAX, T_MIN> operator - (uint a, OverflowSafeInt<T, T_MAX, T_MIN> b) { return -b + a; } +template <class T, int64 T_MAX, int64 T_MIN> FORCEINLINE OverflowSafeInt<T, T_MAX, T_MIN> operator * (uint a, OverflowSafeInt<T, T_MAX, T_MIN> b) { return b * a; } +template <class T, int64 T_MAX, int64 T_MIN> FORCEINLINE OverflowSafeInt<T, T_MAX, T_MIN> operator / (uint a, OverflowSafeInt<T, T_MAX, T_MIN> b) { return (OverflowSafeInt<T, T_MAX, T_MIN>)a / (int)b; } + +/* Sometimes we got byte operator OverflowSafeInt instead of vice versa. Handle that properly */ +template <class T, int64 T_MAX, int64 T_MIN> FORCEINLINE OverflowSafeInt<T, T_MAX, T_MIN> operator + (byte a, OverflowSafeInt<T, T_MAX, T_MIN> b) { return b + a; } +template <class T, int64 T_MAX, int64 T_MIN> FORCEINLINE OverflowSafeInt<T, T_MAX, T_MIN> operator - (byte a, OverflowSafeInt<T, T_MAX, T_MIN> b) { return -b + a; } +template <class T, int64 T_MAX, int64 T_MIN> FORCEINLINE OverflowSafeInt<T, T_MAX, T_MIN> operator * (byte a, OverflowSafeInt<T, T_MAX, T_MIN> b) { return b * a; } +template <class T, int64 T_MAX, int64 T_MIN> FORCEINLINE OverflowSafeInt<T, T_MAX, T_MIN> operator / (byte a, OverflowSafeInt<T, T_MAX, T_MIN> b) { return (OverflowSafeInt<T, T_MAX, T_MIN>)a / (int)b; } + #endif /* HELPERS_HPP */
--- a/src/openttd.h +++ b/src/openttd.h @@ -69,7 +69,9 @@ typedef uint16 GroupID; typedef uint16 EngineRenewID; typedef uint16 DestinationID; -typedef int64 Money; + +typedef OverflowSafeInt<int64, INT64_MAX, INT64_MIN> OverflowSafeInt64; +typedef OverflowSafeInt64 Money; /* DestinationID must be at least as large as every these below, because it can * be any of them
--- a/src/rail_cmd.cpp +++ b/src/rail_cmd.cpp @@ -267,7 +267,7 @@ ) return_cmd_error(STR_1000_LAND_SLOPED_IN_WRONG_DIRECTION); Foundation f_old = GetRailFoundation(tileh, existing); - return CommandCost(f_new != f_old ? _price.terraform : 0); + return CommandCost(f_new != f_old ? _price.terraform : (Money)0); } /* Validate functions for rail building */
--- a/src/road_cmd.cpp +++ b/src/road_cmd.cpp @@ -366,7 +366,7 @@ /* foundation is used. Whole tile is leveled up */ if ((~_valid_tileh_slopes_road[1][tileh] & road_bits) == ROAD_NONE) { - return CommandCost(existing != ROAD_NONE ? 0 : _price.terraform); + return CommandCost(existing != ROAD_NONE ? (Money)0 : _price.terraform); } /* Force straight roads. */
--- a/src/strings.cpp +++ b/src/strings.cpp @@ -331,15 +331,15 @@ static char *FormatGenericCurrency(char *buff, const CurrencySpec *spec, Money number, bool compact, const char* last) { - const char* multiplier = ""; + /* We are going to make number absolute for printing, so + * keep this piece of data as we need it later on */ + bool negative = number < 0; + const char *multiplier = ""; char buf[40]; - char* p; + char *p; int j; - /* Multiply by exchange rate, but do it safely. */ - CommandCost cs(number); - cs.MultiplyCost(spec->rate); - number = cs.GetCost(); + number *= spec->rate; /* convert from negative */ if (number < 0) { @@ -374,7 +374,7 @@ *--p = spec->separator; j = 3; } - *--p = '0' + number % 10; + *--p = '0' + (char)(number % 10); } while ((number /= 10) != 0); buff = strecpy(buff, p, last); @@ -385,7 +385,7 @@ * The only remaining value is 1 (prefix), so everything that is not 0 */ if (spec->symbol_pos != 0) buff = strecpy(buff, spec->suffix, last); - if (cs.GetCost() < 0) { + if (negative) { if (buff + Utf8CharLen(SCC_PREVIOUS_COLOUR) > last) return buff; buff += Utf8Encode(buff, SCC_PREVIOUS_COLOUR); *buff = '\0';