[Freeciv-Dev] (PR#9439) Patch: writing over array bounds in make_river()

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=9439 >

> [resqu@xxxxxx - Tue Jul 20 14:32:15 2004]:
> 
> The rd_comparison_val and rd_direction_is_valid variables in 
> make_river() were all arrays of size 4. However, the indices used to 
> access those arrays are all in the range of direction8, ie values up to 
> 7. Fixed by enlarging those arrays and adding a bit of code to properly 
> initialize rd_direction_is_valid.

Bug, bug, bug...

Obviously it's a bug that the array is too small.  This is my fault.

But your patch is also buggy, I think.  When counting the number of
valid directions you look at all cardinal directions, including the ones
that lead off the edge of the map.  So the loop down below that picks
the direction may end without ever finding a direction since the
direction is too big.  I assume this bug will never come into play,
because there are normally no rivers on the poles and because of the
next bug.

But there's an older bug here, too.  The code

      direction = myrand(num_valid_directions - 1);

is clearly wrong.  This prevents the last-available direction from ever
being chosen.  No doubt this is why they needed a switch instead of just
an if...else, since the above code doesn't work with the "1" case.

Also there is no reason I can see for rd_comparison_val to be static. 
It's initialized each time through the loop.

This is a modification of your patch that fixes all the above.  I
removed the DIR8_COUNT enumeration value.  It can't be added to the enum
without giving all sorts of "DIR8_COUNT not handled in switch" warnings.
 We could just have a #define DIR8_COUNT in map.h, and eventually we
probably should - but it'll take more work to find all the places this
value should be used.

jason

Index: server/mapgen.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/mapgen.c,v
retrieving revision 1.139
diff -u -r1.139 mapgen.c
--- server/mapgen.c     9 Jul 2004 19:30:58 -0000       1.139
+++ server/mapgen.c     20 Jul 2004 15:45:13 -0000
@@ -793,13 +793,14 @@
 *********************************************************************/
 static bool make_river(int x, int y)
 {
-  /* The comparison values of the 4 tiles surrounding the current
-     tile. It is the suitability to continue a river to that tile that
-     is being compared. Lower is better.                  -Erik Sigra */
-  static int rd_comparison_val[4];
+  /* Comparison value for each tile surrounding the current tile.  It is
+   * the suitability to continue a river to the tile in that direction;
+   * lower is better.  However rivers may only run in cardinal directions;
+   * the other directions are ignored entirely. */
+  int rd_comparison_val[8];
 
-  bool rd_direction_is_valid[4];
-  int num_valid_directions, dir, func_num, direction;
+  bool rd_direction_is_valid[8];
+  int num_valid_directions, func_num, direction;
 
   while (TRUE) {
     /* Mark the current tile as river. */
@@ -824,9 +825,11 @@
     freelog(LOG_DEBUG,
            "The river did not end at (%d, %d). Evaluating directions...\n", x, 
y);
 
-    /* Mark all directions as available. */
-    for (dir = 0; dir < 4; dir++)
+    /* Mark all available cardinal directions as available. */
+    memset(rd_direction_is_valid, 0, sizeof(rd_direction_is_valid));
+    cardinal_adjc_dir_iterate(x, y, x1, y1, dir) {
       rd_direction_is_valid[dir] = TRUE;
+    } cardinal_adjc_dir_iterate_end;
 
     /* Test series that selects a direction for the river. */
     for (func_num = 0; func_num < NUM_TEST_FUNCTIONS; func_num++) {
@@ -859,28 +862,19 @@
     /* Directions evaluated with all functions. Now choose the best
        direction before going to the next iteration of the while loop */
     num_valid_directions = 0;
-    for (dir = 0; dir < 4; dir++)
-      if (rd_direction_is_valid[dir])
+    cardinal_adjc_dir_iterate(x, y, x1, y1, dir) {
+      if (rd_direction_is_valid[dir]) {
        num_valid_directions++;
+      }
+    } cardinal_adjc_dir_iterate_end;
 
-    switch (num_valid_directions) {
-    case 0:
+    if (num_valid_directions == 0) {
       return FALSE; /* river aborted */
-    case 1:
-      cardinal_adjc_dir_iterate(x, y, x1, y1, dir) {
-       if (rd_direction_is_valid[dir]) {
-         river_blockmark(x, y);
-         x = x1;
-         y = y1;
-       }
-      } cardinal_adjc_dir_iterate_end;
-      break;
-    default:
-      /* More than one possible direction; Let the random number
-        generator select the direction. */
+    } else {
+      /* One or more valid directions: choose randomly. */
       freelog(LOG_DEBUG, "mapgen.c: Had to let the random number"
              " generator select a direction for a river.");
-      direction = myrand(num_valid_directions - 1);
+      direction = myrand(num_valid_directions);
       freelog(LOG_DEBUG, "mapgen.c: direction: %d", direction);
 
       /* Find the direction that the random number generator selected. */
@@ -895,8 +889,8 @@
          }
        }
       } cardinal_adjc_dir_iterate_end;
-      break;
-    } /* end switch (rd_number_of_directions()) */
+      assert(direction == 0);
+    }
 
   } /* end while; (Make a river.) */
 }