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

Changeset - r22757:59be1e5ea50d

Parent rev.

Child rev.

[Not reviewed]

master

0 3 0

frosch - 6 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

@@ @@ -12,6 +12,7 @@ @@
 #include "stdafx.h"
 #include <stdarg.h>
 #include <algorithm>
 #include "debug.h"
 #include "fileio_func.h"
@@ @@ -4687,16 +4688,60 @@ static void NewSpriteGroup(ByteReader *b @@
 			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;
+		}

src/newgrf_spritegroup.cpp

➞

Show inline comments

@@ @@ -10,6 +10,7 @@ @@
 /** @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"
@@ @@ -201,6 +202,11 @@ static U EvalAdjustT(const Deterministic @@
+}
 static bool RangeHighComparator(const DeterministicSpriteGroupRange& range, uint32 value)
+{
 	return range.high < value;
+}
 const SpriteGroup *DeterministicSpriteGroup::Resolve(ResolverObject &object) const
+{
 	uint32 last_value = 0;
@@ @@ -232,7 +238,7 @@ const SpriteGroup *DeterministicSpriteGr @@
 		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) {
@@ @@ -254,9 +260,17 @@ const SpriteGroup *DeterministicSpriteGr @@
 		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);
+			}
+		}
+	}

src/newgrf_spritegroup.h

➞

Show inline comments

@@ @@ -181,6 +181,8 @@ struct DeterministicSpriteGroup : Sprite @@
 	/* 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;
 };

0 comments (0 inline, 0 general)