cpp/openttd-patchpack/source Changeset - r22757:59be1e5ea50d

Changeset - r22757:59be1e5ea50d

Parent rev.

Child rev.

[Not reviewed]

master

0 3 0

frosch - 7 years ago 2018-03-11 13:21:27
frosch@openttd.org

(svn r27985) -Codechange: Convert VA2 switches into ones with non-overlapping ranges, sort them and resolve them using binary search. Speedup sprite resolving by about 7 percent.

3 files changed with 72 insertions and 11 deletions:

src/newgrf.cpp

src/newgrf_spritegroup.cpp

src/newgrf_spritegroup.h

0 comments (0 inline, 0 general)

src/newgrf.cpp

➞

Show inline comments

@@ @@ -9,12 +9,13 @@ @@
 /** @file newgrf.cpp Base of all NewGRF support. */
 #include "stdafx.h"
 #include <stdarg.h>
 #include <algorithm>
 #include "debug.h"
 #include "fileio_func.h"
 #include "engine_func.h"
 #include "engine_base.h"
 #include "bridge.h"
@@ @@ -4684,22 +4685,66 @@ static void NewSpriteGroup(ByteReader *b @@
 			} while (HasBit(varadjust, 5));
 			group->num_adjusts = adjusts.Length();
 			group->adjusts = MallocT<DeterministicSpriteGroupAdjust>(group->num_adjusts);
 			MemCpyT(group->adjusts, adjusts.Begin(), group->num_adjusts);
 			group->num_ranges = buf->ReadByte();
 			if (group->num_ranges > 0) group->ranges = CallocT<DeterministicSpriteGroupRange>(group->num_ranges);
 			for (uint i = 0; i < group->num_ranges; i++) {
 				group->ranges[i].group = GetGroupFromGroupID(setid, type, buf->ReadWord());
 				group->ranges[i].low   = buf->ReadVarSize(varsize);
 				group->ranges[i].high  = buf->ReadVarSize(varsize);
 			std::vector<DeterministicSpriteGroupRange> ranges;
 			ranges.resize(buf->ReadByte());
 			for (uint i = 0; i < ranges.size(); i++) {
 				ranges[i].group = GetGroupFromGroupID(setid, type, buf->ReadWord());
 				ranges[i].low   = buf->ReadVarSize(varsize);
 				ranges[i].high  = buf->ReadVarSize(varsize);
+			}
 			group->default_group = GetGroupFromGroupID(setid, type, buf->ReadWord());
 			group->error_group = ranges.size() > 0 ? ranges[0].group : group->default_group;
 			/* Sort ranges ascending. When ranges overlap, this may required clamping or splitting them */
 			std::vector<uint32> bounds;
 			for (uint i = 0; i < ranges.size(); i++) {
 				bounds.push_back(ranges[i].low);
 				if (ranges[i].high != UINT32_MAX) bounds.push_back(ranges[i].high + 1);
+			}
 			std::sort(bounds.begin(), bounds.end());
 			bounds.erase(std::unique(bounds.begin(), bounds.end()), bounds.end());
 			std::vector<const SpriteGroup *> target;
 			for (uint j = 0; j < bounds.size(); ++j) {
 				uint32 v = bounds[j];
 				const SpriteGroup *t = NULL;
 				for (uint i = 0; i < ranges.size(); i++) {
 					if (ranges[i].low <= v && v <= ranges[i].high) {
 						t = ranges[i].group;
+					}
+				}
 				target.push_back(t);
+			}
 			assert(target.size() == bounds.size());
 			std::vector<DeterministicSpriteGroupRange> optimised;
 			for (uint j = 0; j < bounds.size(); ) {
 				if (target[j]) {
 					DeterministicSpriteGroupRange r;
 					r.group = target[j];
 					r.low = bounds[j];
 					while (j < bounds.size() && target[j] == r.group) {
 						j++;
+					}
 					r.high = j < bounds.size() ? bounds[j] - 1 : UINT32_MAX;
 					optimised.push_back(r);
 				} else {
 					j++;
+				}
+			}
 			group->num_ranges = optimised.size();
 			if (group->num_ranges > 0) {
 				group->ranges = MallocT<DeterministicSpriteGroupRange>(group->num_ranges);
 				MemCpyT(group->ranges, &optimised.front(), group->num_ranges);
+			}
 			break;
+		}
 		/* Randomized Sprite Group */
 		case 0x80: // Self scope
 		case 0x83: // Parent scope

src/newgrf_spritegroup.cpp

➞

Show inline comments

@@ @@ -7,12 +7,13 @@ @@
  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
  */
 /** @file newgrf_spritegroup.cpp Handling of primarily NewGRF action 2. */
 #include "stdafx.h"
 #include <algorithm>
 #include "debug.h"
 #include "newgrf_spritegroup.h"
 #include "core/pool_func.hpp"
 #include "safeguards.h"
@@ @@ -198,12 +199,17 @@ static U EvalAdjustT(const Deterministic @@
 		case DSGA_OP_SAR:  return (int32)(S)last_value >> ((U)value & 0x1F);
 		default:           return value;
+	}
+}
 static bool RangeHighComparator(const DeterministicSpriteGroupRange& range, uint32 value)
+{
 	return range.high < value;
+}
 const SpriteGroup *DeterministicSpriteGroup::Resolve(ResolverObject &object) const
+{
 	uint32 last_value = 0;
 	uint32 value = 0;
 	uint i;
@@ @@ -229,13 +235,13 @@ const SpriteGroup *DeterministicSpriteGr @@
 			value = GetVariable(object, scope, adjust->variable, adjust->parameter, &available);
+		}
 		if (!available) {
 			/* Unsupported variable: skip further processing and return either
 			 * the group from the first range or the default group. */
-			return SpriteGroup::Resolve(this->num_ranges > 0 ? this->ranges[0].group : this->default_group, object, false);
+			return SpriteGroup::Resolve(this->error_group, object, false);
+		}
 		switch (this->size) {
 			case DSG_SIZE_BYTE:  value = EvalAdjustT<uint8,  int8> (adjust, scope, last_value, value); break;
 			case DSG_SIZE_WORD:  value = EvalAdjustT<uint16, int16>(adjust, scope, last_value, value); break;
 			case DSG_SIZE_DWORD: value = EvalAdjustT<uint32, int32>(adjust, scope, last_value, value); break;
@@ @@ -251,15 +257,23 @@ const SpriteGroup *DeterministicSpriteGr @@
 		if (value != CALLBACK_FAILED) value = GB(value, 0, 15);
 		static CallbackResultSpriteGroup nvarzero(0, true);
 		nvarzero.result = value;
 		return &nvarzero;
+	}
 	for (i = 0; i < this->num_ranges; i++) {
 		if (this->ranges[i].low <= value && value <= this->ranges[i].high) {
 			return SpriteGroup::Resolve(this->ranges[i].group, object, false);
 	if (this->num_ranges > 4) {
 		DeterministicSpriteGroupRange *lower = std::lower_bound(this->ranges + 0, this->ranges + this->num_ranges, value, RangeHighComparator);
 		if (lower != this->ranges + this->num_ranges && lower->low <= value) {
 			assert(lower->low <= value && value <= lower->high);
 			return SpriteGroup::Resolve(lower->group, object, false);
+		}
 	} else {
 		for (i = 0; i < this->num_ranges; i++) {
 			if (this->ranges[i].low <= value && value <= this->ranges[i].high) {
 				return SpriteGroup::Resolve(this->ranges[i].group, object, false);
+			}
+		}
+	}
 	return SpriteGroup::Resolve(this->default_group, object, false);
+}

src/newgrf_spritegroup.h

➞

Show inline comments

@@ @@ -178,12 +178,14 @@ struct DeterministicSpriteGroup : Sprite @@
 	DeterministicSpriteGroupAdjust *adjusts;
 	DeterministicSpriteGroupRange *ranges; // Dynamically allocated
 	/* Dynamically allocated, this is the sole owner */
 	const SpriteGroup *default_group;
 	const SpriteGroup *error_group; // was first range, before sorting ranges
 protected:
 	const SpriteGroup *Resolve(ResolverObject &object) const;
 };
 enum RandomizedSpriteGroupCompareMode {
 	RSG_CMP_ANY,

0 comments (0 inline, 0 general)