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 1d55ab7f9159d3878ff7e23664e5da1075013a17..a56a8f349e749766da9d4b57c5e8c3652bf5ccf1 100644 (file)
--- 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 958cc60f94168489d966fc5ff21466d93c7ff2df..7640b415d0bd6aba2c67f98bd3692439f556c43c 100644 (file)
--- 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 718375ce411bb4dd416e3482e2dc199743486133..3edd3aba3cf4964074b48217fb568aa6773e30f4 100644 (file)
--- 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 9ecb9754932dbdb6ee2eb67e7fd23a75727ecaf4..b8c0b58af5b47f083157e5ad563dba7c3799e70b 100644 (file)
--- 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 (file)
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 <https://www.gnu.org/licenses/>.
+ */
+
+#include <config.h>
+#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 76c802a5beb9072783c092cf1cc604f38d266eb6..4d367afd9a1e3f4ced0cb0f650fb52a97681158b 100644 (file)
--- 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 104f7822f34039698595b24c782fd633c22e2afe..f76b15a834d71a17aa317c28a7e3b5a5fc312ffd 100644 (file)
--- 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 <<EOF'; cat "$1.tap"; echo 'EOF'; } >"$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])