From 07d841d0efb3fc3ed8cca1f3519c3b21bead0bb9 Mon Sep 17 00:00:00 2001 From: frosch Date: Sun, 11 Mar 2018 13:21:27 +0000 Subject: (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. --- src/newgrf.cpp | 59 ++++++++++++++++++++++++++++++++++++++++------ src/newgrf_spritegroup.cpp | 22 +++++++++++++---- src/newgrf_spritegroup.h | 2 ++ 3 files changed, 72 insertions(+), 11 deletions(-) (limited to 'src') diff --git a/src/newgrf.cpp b/src/newgrf.cpp index 704892e5c..41d719591 100644 --- a/src/newgrf.cpp +++ b/src/newgrf.cpp @@ -12,6 +12,7 @@ #include "stdafx.h" #include +#include #include "debug.h" #include "fileio_func.h" @@ -4687,16 +4688,60 @@ static void NewSpriteGroup(ByteReader *buf) group->adjusts = MallocT(group->num_adjusts); MemCpyT(group->adjusts, adjusts.Begin(), group->num_adjusts); - group->num_ranges = buf->ReadByte(); - if (group->num_ranges > 0) group->ranges = CallocT(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 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 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 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 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(group->num_ranges); + MemCpyT(group->ranges, &optimised.front(), group->num_ranges); + } break; } diff --git a/src/newgrf_spritegroup.cpp b/src/newgrf_spritegroup.cpp index cb70a88bf..8f44ef9c5 100644 --- a/src/newgrf_spritegroup.cpp +++ b/src/newgrf_spritegroup.cpp @@ -10,6 +10,7 @@ /** @file newgrf_spritegroup.cpp Handling of primarily NewGRF action 2. */ #include "stdafx.h" +#include #include "debug.h" #include "newgrf_spritegroup.h" #include "core/pool_func.hpp" @@ -201,6 +202,11 @@ static U EvalAdjustT(const DeterministicSpriteGroupAdjust *adjust, ScopeResolver } +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 *DeterministicSpriteGroup::Resolve(ResolverObject &object) con 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 *DeterministicSpriteGroup::Resolve(ResolverObject &object) con 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); + } } } diff --git a/src/newgrf_spritegroup.h b/src/newgrf_spritegroup.h index 4d290b137..b2e764599 100644 --- a/src/newgrf_spritegroup.h +++ b/src/newgrf_spritegroup.h @@ -181,6 +181,8 @@ struct DeterministicSpriteGroup : SpriteGroup { /* 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; }; -- cgit v1.2.3-54-g00ecf