cpp/openttd-patchpack/source Changeset - r20408:1c1a39ca1496

Changeset - r20408:1c1a39ca1496

Parent rev.

Child rev.

[Not reviewed]

master

0 1 0

fonsinchen - 11 years ago 2013-06-17 20:37:31
fonsinchen@openttd.org

(svn r25423) -Fix: integer overflows in MCF solver

1 file changed with 14 insertions and 4 deletions:

src/linkgraph/linkgraphjob.h

0 comments (0 inline, 0 general)

src/linkgraph/linkgraphjob.h

➞

Show inline comments

@@ @@ -351,14 +351,14 @@ public: @@
 	/**
 	 * Get ratio of free * 16 (so that we get fewer 0) /
-	 * total capacity + 1 (so that we don't divide by 0).
+	 * max(total capacity, 1) (so that we don't divide by 0).
 	 * @param free Free capacity.
 	 * @param total Total capacity.
-	 * @return free * 16 / (total + 1).
+	 * @return free * 16 / max(total, 1).
 	 */
-	inline static int GetCapacityRatio(int free, int total)
+	inline static int GetCapacityRatio(int free, uint total)
+	{
-		return (free << 4) / (total + 1);
+		return Clamp(free, PATH_CAP_MIN_FREE, PATH_CAP_MAX_FREE) * PATH_CAP_MULTIPLIER / max(total, 1U);
+	}
 	/**
@@ @@ -400,6 +400,16 @@ public: @@
 	void Fork(Path *base, uint cap, int free_cap, uint dist);
 protected:
 	/**
 	 * Some boundaries to clamp agains in order to avoid integer overflows.
 	 */
 	enum PathCapacityBoundaries {
 		PATH_CAP_MULTIPLIER = 16,
 		PATH_CAP_MIN_FREE = (INT_MIN + 1) / PATH_CAP_MULTIPLIER,
 		PATH_CAP_MAX_FREE = (INT_MAX - 1) / PATH_CAP_MULTIPLIER
 	};
 	uint distance;     ///< Sum(distance of all legs up to this one).
 	uint capacity;     ///< This capacity is min(capacity) fom all edges.
 	int free_capacity; ///< This capacity is min(edge.capacity - edge.flow) for the current run of Dijkstra.

0 comments (0 inline, 0 general)