From 3c94485ba0dcf8bb26f94f3a8e74369cd5619c01 Mon Sep 17 00:00:00 2001 From: rubidium Date: Thu, 2 Jan 2014 16:48:16 +0000 Subject: (svn r26205) -Feature: SSE 4.1 sprite sorter, improving the sorting performance significantly (MJP) For example with GCC 4.8, x86_64 Linux, Intel i5-3337U this patch improves the performance of Pile, Treham and Hamac test save games by about 10% in over-all run time at fast forward at 1920x1080 when zoomed out and when trees are not disabled. --- src/viewport_sprite_sorter_sse4.cpp | 109 ++++++++++++++++++++++++++++++++++++ 1 file changed, 109 insertions(+) create mode 100644 src/viewport_sprite_sorter_sse4.cpp (limited to 'src/viewport_sprite_sorter_sse4.cpp') diff --git a/src/viewport_sprite_sorter_sse4.cpp b/src/viewport_sprite_sorter_sse4.cpp new file mode 100644 index 000000000..40bbca87d --- /dev/null +++ b/src/viewport_sprite_sorter_sse4.cpp @@ -0,0 +1,109 @@ +/* $Id$ */ + +/* + * This file is part of OpenTTD. + * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2. + * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + * 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 . + */ + +/** @file viewport_sprite_sorter_sse.cpp Sprite sorter that uses SSE4.1. */ + +#ifdef WITH_SSE + +#include "stdafx.h" +#include "cpu.h" +#include "smmintrin.h" +#include "viewport_sprite_sorter.h" + +#ifdef _SQ64 + assert_compile((sizeof(ParentSpriteToDraw) % 16) == 0); + #define LOAD_128 _mm_load_si128 +#else + #define LOAD_128 _mm_loadu_si128 +#endif + +/** Sort parent sprites pointer array using SSE4.1 optimizations. */ +void ViewportSortParentSpritesSSE41(ParentSpriteToSortVector *psdv) +{ + const __m128i mask_ptest = _mm_setr_epi8(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 0, 0, 0); + ParentSpriteToDraw ** const psdvend = psdv->End(); + ParentSpriteToDraw **psd = psdv->Begin(); + while (psd != psdvend) { + ParentSpriteToDraw * const ps = *psd; + + if (ps->comparison_done) { + psd++; + continue; + } + + ps->comparison_done = true; + + for (ParentSpriteToDraw **psd2 = psd + 1; psd2 != psdvend; psd2++) { + ParentSpriteToDraw * const ps2 = *psd2; + + if (ps2->comparison_done) continue; + + /* + * Decide which comparator to use, based on whether the bounding boxes overlap + * + * Original code: + * if (ps->xmax >= ps2->xmin && ps->xmin <= ps2->xmax && // overlap in X? + * ps->ymax >= ps2->ymin && ps->ymin <= ps2->ymax && // overlap in Y? + * ps->zmax >= ps2->zmin && ps->zmin <= ps2->zmax) { // overlap in Z? + * + * Above conditions are equivalent to: + * 1/ !( (ps->xmax >= ps2->xmin) && (ps->ymax >= ps2->ymin) && (ps->zmax >= ps2->zmin) && (ps->xmin <= ps2->xmax) && (ps->ymin <= ps2->ymax) && (ps->zmin <= ps2->zmax) ) + * 2/ !( (ps->xmax >= ps2->xmin) && (ps->ymax >= ps2->ymin) && (ps->zmax >= ps2->zmin) && (ps2->xmax >= ps->xmin) && (ps2->ymax >= ps->ymin) && (ps2->zmax >= ps->zmin) ) + * 3/ !( ( (ps->xmax >= ps2->xmin) && (ps->ymax >= ps2->ymin) && (ps->zmax >= ps2->zmin) ) && ( (ps2->xmax >= ps->xmin) && (ps2->ymax >= ps->ymin) && (ps2->zmax >= ps->zmin) ) ) + * 4/ !( !( (ps->xmax < ps2->xmin) || (ps->ymax < ps2->ymin) || (ps->zmax < ps2->zmin) ) && !( (ps2->xmax < ps->xmin) || (ps2->ymax < ps->ymin) || (ps2->zmax < ps->zmin) ) ) + * 5/ PTEST <---------------------------------- rslt1 ----------------------------------> <------------------------------ rslt2 --------------------------------------> + */ + __m128i ps1_max = LOAD_128((__m128i*) &ps->xmax); + __m128i ps2_min = LOAD_128((__m128i*) &ps2->xmin); + __m128i rslt1 = _mm_cmplt_epi32(ps1_max, ps2_min); + if (!_mm_testz_si128(mask_ptest, rslt1)) + continue; + + __m128i ps1_min = LOAD_128((__m128i*) &ps->xmin); + __m128i ps2_max = LOAD_128((__m128i*) &ps2->xmax); + __m128i rslt2 = _mm_cmplt_epi32(ps2_max, ps1_min); + if (_mm_testz_si128(mask_ptest, rslt2)) { + /* Use X+Y+Z as the sorting order, so sprites closer to the bottom of + * the screen and with higher Z elevation, are drawn in front. + * Here X,Y,Z are the coordinates of the "center of mass" of the sprite, + * i.e. X=(left+right)/2, etc. + * However, since we only care about order, don't actually divide / 2 + */ + if (ps->xmin + ps->xmax + ps->ymin + ps->ymax + ps->zmin + ps->zmax <= + ps2->xmin + ps2->xmax + ps2->ymin + ps2->ymax + ps2->zmin + ps2->zmax) { + continue; + } + } + + /* Move ps2 in front of ps */ + ParentSpriteToDraw * const temp = ps2; + for (ParentSpriteToDraw **psd3 = psd2; psd3 > psd; psd3--) { + *psd3 = *(psd3 - 1); + } + *psd = temp; + } + } +} + +/** + * Check whether the current CPU supports SSE 4.1. + * @return True iff the CPU supports SSE 4.1. + */ +bool ViewportSortParentSpritesSSE41Checker() +{ + int cpu_info[4] = {-1}; + ottd_cpuid(cpu_info, 0); + unsigned int max_info_type = cpu_info[0]; + if (max_info_type < 1) return false; + + ottd_cpuid(cpu_info, 1); + return (cpu_info[2] & (1 << 19)) != 0; +} + +#endif /* WITH_SSE */ -- cgit v1.2.3-54-g00ecf