diff options
| -rw-r--r-- | src/core/bitmath_func.cpp | 28 | ||||
| -rw-r--r-- | src/core/bitmath_func.hpp | 1 | ||||
| -rw-r--r-- | src/graph_gui.cpp | 31 |
3 files changed, 53 insertions, 7 deletions
diff --git a/src/core/bitmath_func.cpp b/src/core/bitmath_func.cpp index 9f36ed9a8..53139308a 100644 --- a/src/core/bitmath_func.cpp +++ b/src/core/bitmath_func.cpp @@ -25,7 +25,7 @@ const uint8 _ffb_64[64] = { * way further. If no bit is set return 0. * * @param x The value to search - * @param The position of the first bit set + * @return The position of the first bit set */ uint8 FindFirstBit(uint32 x) { @@ -43,3 +43,29 @@ uint8 FindFirstBit(uint32 x) return pos; } + +/** + * Search the last set bit in a 32 bit variable. + * + * This algorithm is a static implementation of a log + * conguence search algorithm. It checks the first half + * if there is a bit set search there further. And this + * way further. If no bit is set return 0. + * + * @param x The value to search + * @return The position of the last bit set + */ +uint8 FindLastBit(uint32 x) +{ + if (x == 0) return 0; + + uint8 pos = 0; + + if ((x & 0xffff0000) != 0) { x >>= 16; pos += 16; } + if ((x & 0x0000ff00) != 0) { x >>= 8; pos += 8; } + if ((x & 0x000000f0) != 0) { x >>= 4; pos += 4; } + if ((x & 0x0000000c) != 0) { x >>= 2; pos += 2; } + if ((x & 0x00000002) != 0) { pos += 1; } + + return pos; +} diff --git a/src/core/bitmath_func.hpp b/src/core/bitmath_func.hpp index 1877f003e..f4c6ff0bc 100644 --- a/src/core/bitmath_func.hpp +++ b/src/core/bitmath_func.hpp @@ -211,6 +211,7 @@ static inline uint8 FindFirstBit2x64(const int value) } uint8 FindFirstBit(uint32 x); +uint8 FindLastBit(uint32 x); /** * Clear the first bit in an integer. diff --git a/src/graph_gui.cpp b/src/graph_gui.cpp index 7c2543011..ddabf882d 100644 --- a/src/graph_gui.cpp +++ b/src/graph_gui.cpp @@ -65,7 +65,7 @@ struct GraphDrawer { uint height; ///< The height of the graph in pixels. StringID format_str_y_axis; byte colors[GRAPH_MAX_DATASETS]; - Money cost[GRAPH_MAX_DATASETS][24]; ///< last 2 years + OverflowSafeInt64 cost[GRAPH_MAX_DATASETS][24]; ///< last 2 years }; static void DrawGraph(const GraphDrawer *gw) @@ -133,7 +133,7 @@ static void DrawGraph(const GraphDrawer *gw) for (int i = 0; i < gw->num_dataset; i++) { if (!HasBit(gw->excluded_data, i)) { for (int j = 0; j < gw->num_on_x_axis; j++) { - Money datapoint = gw->cost[i][j]; + OverflowSafeInt64 datapoint = gw->cost[i][j]; if (datapoint != INVALID_DATAPOINT) { /* For now, if the graph has negative values the scaling is @@ -215,12 +215,31 @@ static void DrawGraph(const GraphDrawer *gw) uint prev_y = INVALID_DATAPOINT_POS; for (int j = 0; j < gw->num_on_x_axis; j++) { - Money datapoint = gw->cost[i][j]; + OverflowSafeInt64 datapoint = gw->cost[i][j]; if (datapoint != INVALID_DATAPOINT) { - /* XXX: This can overflow if x_axis_offset * datapoint is - * too big to fit in an int64. */ - y = gw->top + x_axis_offset - (x_axis_offset * datapoint) / highest_value; + /* + * Check whether we need to reduce the 'accuracy' of the + * datapoint value and the highest value to splut overflows. + * And when 'drawing' 'one million' or 'one million and one' + * there is no significant difference, so the least + * significant bits can just be removed. + * + * If there are more bits needed than would fit in a 32 bits + * integer, so at about 31 bits because of the sign bit, the + * least significant bits are removed. + */ + int mult_range = FindLastBit(x_axis_offset) + FindLastBit(abs(datapoint)); + int reduce_range = max(mult_range - 31, 0); + + /* Handle negative values differently (don't shift sign) */ + if (datapoint < 0) { + datapoint = -(abs(datapoint) >> reduce_range); + } else { + datapoint >>= reduce_range; + } + + y = gw->top + x_axis_offset - (x_axis_offset * datapoint) / (highest_value >> reduce_range); /* Draw the point. */ GfxFillRect(x - 1, y - 1, x + 1, y + 1, color); |