From: Nick Bowler Date: Wed, 7 Dec 2022 05:16:41 +0000 (-0500) Subject: Improve exposure mask calculation. X-Git-Url: http://git.draconx.ca/gitweb/rrace.git/commitdiff_plain/777611df8df4522752b3a85a14523f18bf695a0f Improve exposure mask calculation. By assuming that a >= b, the computation of board_left(a) & board_right(b) can be simplified to board_left(a-b) << a. which avoids some computation. A similar improvement can be done for board_above/board_below. Add a new board_rect function that incorporates these improvements, and use it to generate exposure update bitmaps in the Motif UI. A new test case exhaustively tests all possible inputs to this function. Furthermore, update board_above and board_below to have simpler implementations. --- diff --git a/Makefile.am b/Makefile.am index 1d55ab7..a56a8f3 100644 --- a/Makefile.am +++ b/Makefile.am @@ -87,25 +87,34 @@ EXTRA_DIST += $(DX_BASEDIR)/scripts/gen-tree.awk DISTCLEANFILES += $(TREEFILES:.dat=.h) EXTRA_DIST += $(TREEFILES) -check_PROGRAMS = t/boardmove t/boardbit t/checkgoal t/ewmhicon t/rng-test +check_PROGRAMS = t/boardbit \ + t/boardmove \ + t/boardrect \ + t/checkgoal \ + t/ewmhicon \ + t/rng-test EXTRA_DIST += t/xos256ss.c +t_boardbit_SOURCES = t/boardbit.c +t_boardbit_LDADD = libgnu.a +$(t_boardbit_OBJECTS): $(gnulib_headers) + t_boardmove_SOURCES = t/boardmove.c src/game.c t_boardmove_LDADD = libgnu.a $(LIB_CLOCK_GETTIME) $(LIB_GETHRXTIME) $(t_boardmove_OBJECTS): $(gnulib_headers) -t_boardbit_SOURCES = t/boardbit.c -t_boardbit_LDADD = libgnu.a -$(t_boardbit_OBJECTS): $(gnulib_headers) +t_boardrect_SOURCES = t/boardrect.c common/src/tap.c common/src/tap.h +t_boardrect_LDADD = libgnu.a +$(t_boardrect_OBJECTS): $(gnulib_headers) + +t_checkgoal_SOURCES = t/checkgoal.c src/game.c +t_checkgoal_LDADD = libgnu.a $(LIB_CLOCK_GETTIME) $(LIB_GETHRXTIME) +$(t_checkgoal_OBJECTS): $(gnulib_headers) t_ewmhicon_SOURCES = t/ewmhicon.c src/ewmhicon.c src/icon.c common/src/help.c t_ewmhicon_LDADD = libgnu.a $(MOTIF_LIBS) $(t_ewmhicon_OBJECTS): $(gnulib_headers) -t_checkgoal_SOURCES = t/checkgoal.c src/game.c -t_checkgoal_LDADD = libgnu.a -$(t_checkgoal_OBJECTS): $(gnulib_headers) - t_rng_test_LDADD = libgnu.a $(t_rng_test_OBJECTS): $(gnulib_headers) diff --git a/src/game.h b/src/game.h index 958cc60..7640b41 100644 --- a/src/game.h +++ b/src/game.h @@ -121,9 +121,7 @@ static inline uint_fast32_t board_mask_v(int x, int y0, int y1) */ static inline uint_fast32_t board_above(int y) { - uint_fast32_t val = board_row(y); - - return val | (val-1); + return ( 0x20ul << 5*y ) - 1; } /* @@ -131,9 +129,7 @@ static inline uint_fast32_t board_above(int y) */ static inline uint_fast32_t board_below(int y) { - uint_fast32_t val = board_row(y); - - return val | (~val + 1); + return ~( 1ul << 5*y ) + 1; } /* @@ -156,6 +152,21 @@ static inline uint_fast32_t board_right(int x) return ~val + 0x108421; } +/* + * Return the board bitmap setting the rectangle of locations that are: + * + * - on or right of column x1, and + * - on or left of column x2, and + * - on or below row y1, and + * - on or above row y2. + * + * It must be the case that x2 >= x1 and y2 >= y1. + */ +static inline uint_fast32_t board_rect(int x1, int y1, int x2, int y2) +{ + return (board_left(x2-x1) << x1) & (board_above(y2-y1) << 5*y1); +} + /* * Move the bits in the game bitmaps according to a move at position (x, y), * and update the location of the empty position which, if the move was valid diff --git a/src/motif_ui.c b/src/motif_ui.c index 718375c..3edd3ab 100644 --- a/src/motif_ui.c +++ b/src/motif_ui.c @@ -262,10 +262,10 @@ static uint_fast32_t expose_mask(int rect_x, int rect_y, int rect_w, int rect_h, int tile_w, int tile_h) { - return board_right(rect_x / tile_w) - & board_below(rect_y / tile_h) - & board_above((rect_y + rect_h - 1) / tile_h) - & board_left((rect_x + rect_w - 1) / tile_w); + return board_rect( rect_x/tile_w, + rect_y/tile_h, + (rect_x+rect_w-1)/tile_w, + (rect_y+rect_h-1)/tile_h ); } static void game_resize(Widget w, void *data, void *cb_data) diff --git a/t/.gitignore b/t/.gitignore index 9ecb975..b8c0b58 100644 --- a/t/.gitignore +++ b/t/.gitignore @@ -1,5 +1,6 @@ /boardbit /boardmove +/boardrect /checkgoal /ewmhicon /rng-test diff --git a/t/boardrect.c b/t/boardrect.c new file mode 100644 index 0000000..55b2e61 --- /dev/null +++ b/t/boardrect.c @@ -0,0 +1,76 @@ +/* + * Helper to test board_rect function. + * Copyright © 2022 Nick Bowler + * + * This program 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, either version 3 of the License, or + * (at your option) any later version. + * + * This program 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 this program. If not, see . + */ + +#include +#include "game.h" +#include "tap.h" + +#define mask_char(x) ((x) ? '@' : '.') + +static void print_mask(const char *prefix, unsigned long mask) +{ + int i; + + for (i = 0; i < 5; i++) { + tap_diag("%s%c%c%c%c%c", prefix, mask_char(mask & 1), + mask_char(mask & 2), + mask_char(mask & 4), + mask_char(mask & 8), + mask_char(mask & 16)); + mask >>= 5; + } +} + +static void do_check(int x1, int y1, int x2, int y2) +{ + unsigned long expect = board_right(x1) + & board_below(y1) + & board_left(x2) + & board_above(y2); + + unsigned long actual = board_rect(x1, y1, x2, y2); + + if (!tap_result(actual == expect, "board_rect(%d, %d, %d, %d)", + x1, y1, x2, y2)) + { + tap_diag("Failed, unexpected result"); + tap_diag("Received 0x%.7lx:", actual); + print_mask(" ", actual); + tap_diag("Expected 0x%.7lx:", expect); + print_mask(" ", expect); + } +} + +int main(void) +{ + int x1, y1, x2, y2; + + tap_plan(225); + + /* Exhaustive search of all valid inputs */ + for (x1 = 0; x1 < 5; x1++) { + for (y1 = 0; y1 < 5; y1++) { + for (x2 = x1; x2 < 5; x2++) { + for (y2 = y1; y2 < 5; y2++) { + do_check(x1, y1, x2, y2); + } + } + } + } + tap_done(); +} diff --git a/tests/game.at b/tests/game.at index 76c802a..4d367af 100644 --- a/tests/game.at +++ b/tests/game.at @@ -47,6 +47,8 @@ below(0) below(1) below(2) below(3) below(4) AT_CLEANUP +TEST_TAP_SIMPLE([board_rect], [boardrect], [], [board]) + AT_SETUP([game_do_move zigzag]) AT_CHECK([boardmove m4_do( diff --git a/testsuite.at b/testsuite.at index 104f782..f76b15a 100644 --- a/testsuite.at +++ b/testsuite.at @@ -16,5 +16,24 @@ AT_COPYRIGHT([Copyright © 2022 Nick Bowler]) AT_INIT AT_COLOR_TESTS +m4_divert_push([PREPARE_TESTS])dnl +test_run_tap () { + "$builddir/t/$1" > "$1.tap" + status=$? + cat "$1.tap" + :; { echo 'print <"$1.pl" + prove "$1.pl" 2>&1 + return $status +} +m4_divert_pop([PREPARE_TESTS]) + +m4_define([TEST_TAP], [AT_CHECK([test_run_tap "$1"], [0], [ignore])]) +m4_define([TEST_TAP_SIMPLE], [dnl +AT_SETUP([$1]) +AT_KEYWORDS([$4])dnl +m4_n([$3])dnl +TEST_TAP([$2]) +AT_CLEANUP]) + m4_include([tests/game.at]) m4_include([tests/gui.at])