--- ./client/gui-gtk/mapview.c	2001/08/11 07:43:46	1.1
+++ ./client/gui-gtk/mapview.c	2001/08/11 08:53:16
@@ -143,20 +143,301 @@
 static GtkObject *map_hadj, *map_vadj;
 
 
-/**************************************************************************
-...
-**************************************************************************/
-void pixmap_put_tile(GdkDrawable *pm, int x, int y,
-		     int canvas_x, int canvas_y, int citymode)
+int tile_cache_size = 1024;
+int min_cached_tile_depth = 2;
+
+struct Tilecacheobject {
+  struct Sprite sprite;
+  unsigned int id;
+};
+
+static struct Tilecacheobject *tile_cache = NULL;
+
+static int cache_hits = 0, cache_misses = 0;
+
+int use_tile_cache = 0;
+
+void gui_cleanup(void) {
+  int n = 0, i;
+
+  if (use_tile_cache && tile_cache != NULL) {
+    freelog (LOG_NORMAL, "Cache hits: %u, misses: %u", cache_hits,
+	     cache_misses);
+    for (i = 0 ; i < tile_cache_size ; ++i) {
+      if (tile_cache[i].sprite.pixmap) {
+	n++;
+	gdk_pixmap_unref(tile_cache[i].sprite.pixmap);
+      }
+    }
+    freelog (LOG_NORMAL, "Cache population: %d out of %d", n, tile_cache_size);
+  }
+}
+
+void initcache(void) {
+  int i;
+
+  freelog (LOG_DEBUG, "Initializing cache...");
+  tile_cache = malloc(tile_cache_size * sizeof(*tile_cache));
+  if (tile_cache == NULL) {
+    /* Ooops.  No memory for this.  Other things will probably break, but
+     * in any case the right thing to do now is to cause things to fall
+     * back onto uncached behavior... */
+    freelog (LOG_ERROR, "Can't get memory for cache!  Falling back to uncached behavior...");
+    use_tile_cache = 0;
+    return;
+  }
+  for (i = 0 ; i < tile_cache_size ; ++i) {
+    tile_cache[i].sprite.pixmap = NULL;
+    tile_cache[i].sprite.mask = NULL;
+    tile_cache[i].sprite.has_mask = 0;
+    tile_cache[i].sprite.width = 0;
+    tile_cache[i].sprite.height = 0;
+    tile_cache[i].id = 0;
+  }
+}
+
+#if 1
+
+/* Found at http://burtleburtle.net/bob/hash/hashfaq.html */
+
+static unsigned int hash (char *key, int len, unsigned int initval) {
+  unsigned int h;
+  int i;
+
+  for (h = initval, i = 0 ; i < len ; ++i) {
+    h += key[i];
+    h += (h<<10);
+    h ^= (h>>6);
+  }
+  h += (h<<3); h ^= (h>>11); h += (h<<15);
+  return h;
+}
+#else
+
+/* Found at http://burtleburtle.net/bob/hash/doobs.html */
+
+typedef  unsigned long  int  ub4;   /* unsigned 4-byte quantities */
+typedef  unsigned       char ub1;   /* unsigned 1-byte quantities */
+
+#define hashsize(n) ((ub4)1<<(n))
+#define hashmask(n) (hashsize(n)-1)
+
+/*
+--------------------------------------------------------------------
+mix -- mix 3 32-bit values reversibly.
+For every delta with one or two bits set, and the deltas of all three
+  high bits or all three low bits, whether the original value of a,b,c
+  is almost all zero or is uniformly distributed,
+* If mix() is run forward or backward, at least 32 bits in a,b,c
+  have at least 1/4 probability of changing.
+* If mix() is run forward, every bit of c will change between 1/3 and
+  2/3 of the time.  (Well, 22/100 and 78/100 for some 2-bit deltas.)
+mix() was built out of 36 single-cycle latency instructions in a 
+  structure that could supported 2x parallelism, like so:
+      a -= b; 
+      a -= c; x = (c>>13);
+      b -= c; a ^= x;
+      b -= a; x = (a<<8);
+      c -= a; b ^= x;
+      c -= b; x = (b>>13);
+      ...
+  Unfortunately, superscalar Pentiums and Sparcs can't take advantage 
+  of that parallelism.  They've also turned some of those single-cycle
+  latency instructions into multi-cycle latency instructions.  Still,
+  this is the fastest good hash I could find.  There were about 2^^68
+  to choose from.  I only looked at a billion or so.
+--------------------------------------------------------------------
+*/
+#define mix(a,b,c) \
+{ \
+  a -= b; a -= c; a ^= (c>>13); \
+  b -= c; b -= a; b ^= (a<<8); \
+  c -= a; c -= b; c ^= (b>>13); \
+  a -= b; a -= c; a ^= (c>>12);  \
+  b -= c; b -= a; b ^= (a<<16); \
+  c -= a; c -= b; c ^= (b>>5); \
+  a -= b; a -= c; a ^= (c>>3);  \
+  b -= c; b -= a; b ^= (a<<10); \
+  c -= a; c -= b; c ^= (b>>15); \
+}
+
+/*
+--------------------------------------------------------------------
+hash() -- hash a variable-length key into a 32-bit value
+  k       : the key (the unaligned variable-length array of bytes)
+  len     : the length of the key, counting by bytes
+  initval : can be any 4-byte value
+Returns a 32-bit value.  Every bit of the key affects every bit of
+the return value.  Every 1-bit and 2-bit delta achieves avalanche.
+About 6*len+35 instructions.
+
+The best hash table sizes are powers of 2.  There is no need to do
+mod a prime (mod is sooo slow!).  If you need less than 32 bits,
+use a bitmask.  For example, if you need only 10 bits, do
+  h = (h & hashmask(10));
+In which case, the hash table should have hashsize(10) elements.
+
+If you are hashing n strings (ub1 **)k, do it like this:
+  for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
+
+By Bob Jenkins, 1996.  bob_jenkins@xxxxxxxxxxxxxxxx.  You may use this
+code any way you wish, private, educational, or commercial.  It's free.
+
+See http://burtleburtle.net/bob/hash/evahash.html
+Use for hash table lookup, or anything where one collision in 2^^32 is
+acceptable.  Do NOT use for cryptographic purposes.
+--------------------------------------------------------------------
+*/
+
+ub4 hash( k, length, initval)
+register ub1 *k;        /* the key */
+register ub4  length;   /* the length of the key */
+register ub4  initval;  /* the previous hash, or an arbitrary value */
 {
-  struct Sprite *tile_sprs[80];
-  int fill_bg;
-  struct player *pplayer;
+   register ub4 a,b,c,len;
 
-  if (normalize_map_pos(&x, &y) && tile_is_known(x, y)) {
-    int count = fill_tile_sprite_array(tile_sprs, x, y, citymode, &fill_bg, &pplayer);
-    int i = 0;
+   /* Set up the internal state */
+   len = length;
+   a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
+   c = initval;         /* the previous hash value */
 
+   /*---------------------------------------- handle most of the key */
+   while (len >= 12)
+   {
+      a += (k[0] +((ub4)k[1]<<8) +((ub4)k[2]<<16) +((ub4)k[3]<<24));
+      b += (k[4] +((ub4)k[5]<<8) +((ub4)k[6]<<16) +((ub4)k[7]<<24));
+      c += (k[8] +((ub4)k[9]<<8) +((ub4)k[10]<<16)+((ub4)k[11]<<24));
+      mix(a,b,c);
+      k += 12; len -= 12;
+   }
+
+   /*------------------------------------- handle the last 11 bytes */
+   c += length;
+   switch(len)              /* all the case statements fall through */
+   {
+   case 11: c+=((ub4)k[10]<<24);
+   case 10: c+=((ub4)k[9]<<16);
+   case 9 : c+=((ub4)k[8]<<8);
+      /* the first byte of c is reserved for the length */
+   case 8 : b+=((ub4)k[7]<<24);
+   case 7 : b+=((ub4)k[6]<<16);
+   case 6 : b+=((ub4)k[5]<<8);
+   case 5 : b+=k[4];
+   case 4 : a+=((ub4)k[3]<<24);
+   case 3 : a+=((ub4)k[2]<<16);
+   case 2 : a+=((ub4)k[1]<<8);
+   case 1 : a+=k[0];
+     /* case 0: nothing left to add */
+   }
+   mix(a,b,c);
+   /*-------------------------------------------- report the result */
+   return c;
+}
+
+#endif
+
+/*
+ * The meat of the cacheing system.  Without the cache, multiple layers of
+ * tiles have to be drawn for each tile displayed on the screen, one on top
+ * of the other.  When draw_fog_of_war is turned off, this isn't much of an
+ * issue because in that case there's usually only one tile to lay down,
+ * though even then sometimes there may be two or even three.
+ *
+ * With draw_fog_of_war turned on, most of the tiles will have a depth of
+ * at least two.  Normally this would mean two pixmap drawing cycles per
+ * visible tile.
+ *
+ * What we do here is cache the combined tiles.  We look at the list of
+ * tiles to be drawn and if we find that same list pre-rendered in the
+ * cache, we just return the sprite that we had already built for that
+ * list.  Otherwise we build the sprite in the same way that the original
+ * drawing function, pixmap_put_tile(), does.
+ *
+ * The real trick was finding a hashing function that wouldn't produce
+ * false matches.  We rely on the fact that the tiles in the list we're
+ * handed aren't reused for something else and aren't generated dynamically.
+ * We use the pointers to the tiles themselves as the data to hash.
+ *
+ * Note that it's very important that we be able to distinguish between a
+ * list of tiles (a, b) and a list of tiles (b, a), since this implies that
+ * the drawing order has been reversed and thus the resulting combined
+ * tile will look different.  The hashing method we're currently using
+ * accounts for this.
+ *
+ * Because of strange display artifacts, combinations that involve sprites
+ * of differing sizes get punted to the caller.  To deal properly with
+ * this would require that we derive a combined bitmask for all the
+ * sprites in the tile.  But since the bitmasks are stored on the X server,
+ * that means manipulating them there.  I didn't see any GTK/GDK calls
+ * that would allow that.  Define CACHE_VARYING_WIDTHS if you want to
+ * live with these display artifacts for the slight performance gain.
+ */  
+struct Sprite *get_cached_tile (struct Sprite **tiles, int ntiles,
+				int fill_bg, struct player *pplayer)
+{
+  int i = 0;
+  unsigned int id;
+  int maxwidth = 0, maxheight = 0;
+  struct Tilecacheobject *entry;
+  GdkPixmap *pixmap = NULL;
+  struct Sprite *sprite = NULL;
+
+  if (ntiles < min_cached_tile_depth || ! use_tile_cache || tiles[0] == NULL)
+    return NULL;
+  if (tile_cache == NULL)
+    initcache();
+  id = hash((char *)tiles, ntiles * sizeof(*tiles), 0);
+  maxwidth = tiles[0]->width;
+  maxheight = tiles[i]->height;
+  for (i = 0 ; i < ntiles ; ++i) {
+    if (tiles[i] == NULL) continue;
+#ifdef CACHE_VARYING_WIDTHS
+    if (tiles[i]->width > maxwidth) maxwidth = tiles[i]->width;
+    if (tiles[i]->height > maxheight) maxheight = tiles[i]->height;
+#else
+    if (tiles[i]->width != maxwidth || tiles[i]->height != maxheight) {
+      return NULL;
+    }
+#endif
+    id = hash((char *)(tiles[i]), sizeof(*(tiles[i])), id);
+  }
+  if (fill_bg) {
+#ifdef CACHE_VARYING_WIDTHS
+    if (NORMAL_TILE_WIDTH > maxwidth) maxwidth = NORMAL_TILE_WIDTH;
+    if (NORMAL_TILE_HEIGHT > maxheight) maxheight = NORMAL_TILE_HEIGHT;
+#else
+    if (maxwidth != NORMAL_TILE_WIDTH ||maxwidth != NORMAL_TILE_HEIGHT)
+      return NULL;
+#endif
+  }
+  id ^= ((fill_bg ? 1 << 1 : 0) ^ (pplayer ? 1 << 2 : 0));
+  i = id % tile_cache_size;
+  entry = &(tile_cache[i]);
+  if (entry -> sprite.pixmap != NULL && entry -> sprite.width == maxwidth &&
+      entry -> sprite.height == maxheight && entry -> id == id) {
+    cache_hits++;
+    sprite = &(entry -> sprite);
+  } else {
+    cache_misses++;
+    pixmap = entry->sprite.pixmap;
+    if ( entry -> sprite.width != maxwidth ||
+	 entry -> sprite.height != maxheight ) {
+      /* Existing pixmap is of the wrong size.  Free it if it exists, and
+       * arrange for us to get a new pixmap. */
+      if ( pixmap != NULL ) {
+	gdk_pixmap_unref(pixmap);
+	pixmap = NULL;
+      }
+    }
+    if (pixmap == NULL) {
+      pixmap = gdk_pixmap_new(root_window, maxwidth, maxheight, -1);
+      if (pixmap == NULL) {
+	freelog (LOG_ERROR, "get_cached_tile(): Can't get a pixmap!!!");
+	return NULL;
+      }
+    }
+
+    i = 0;
     if (fill_bg) {
       if (pplayer) {
 	gdk_gc_set_foreground(fill_bg_gc,
@@ -165,23 +446,83 @@
 	gdk_gc_set_foreground(fill_bg_gc,
 			      colors_standard[COLOR_STD_BACKGROUND]);	
       }
-      gdk_draw_rectangle(pm, fill_bg_gc, TRUE,
-			 canvas_x, canvas_y,
+      gdk_draw_rectangle(pixmap, fill_bg_gc, TRUE,
+			 0, 0,
 			 NORMAL_TILE_WIDTH, NORMAL_TILE_HEIGHT);
     } else {
       /* first tile without mask */
-      gdk_draw_pixmap(pm, civ_gc, tile_sprs[0]->pixmap,
-                      0, 0, canvas_x, canvas_y,
-                      tile_sprs[0]->width, tile_sprs[0]->height);
+      gdk_draw_pixmap(pixmap, civ_gc, tiles[0]->pixmap,
+                      0, 0, 0, 0,
+                      tiles[0]->width, tiles[0]->height);
       i++;
     }
 
-    for (;i<count; i++) {
-      if (tile_sprs[i]) {
-        pixmap_put_overlay_tile(pm, canvas_x, canvas_y, tile_sprs[i]);
+    for (;i<ntiles; i++) {
+      if (tiles[i]) {
+        pixmap_put_overlay_tile(pixmap, 0, 0, tiles[i]);
       }
     }
 
+    entry->sprite.pixmap = pixmap;
+    entry->sprite.mask = NULL;
+    entry->sprite.has_mask = 0;
+    entry->sprite.width = maxwidth;
+    entry->sprite.height = maxheight;
+    entry->id = id;
+    sprite = &(entry->sprite);
+  }
+  return sprite;
+}
+
+
+
+#define USECACHE
+/**************************************************************************
+...
+**************************************************************************/
+void pixmap_put_tile(GdkDrawable *pm, int x, int y,
+		     int canvas_x, int canvas_y, int citymode)
+{
+  struct Sprite *tile_sprs[80];
+  int fill_bg;
+  struct player *pplayer;
+  struct Sprite *tile;
+
+  if (normalize_map_pos(&x, &y) && tile_is_known(x, y)) {
+    int count = fill_tile_sprite_array(tile_sprs, x, y, citymode, &fill_bg, &pplayer);
+    int i = 0;
+    if (use_tile_cache && count >= min_cached_tile_depth &&
+	(tile = get_cached_tile(tile_sprs, count, fill_bg, pplayer)) !=
+	NULL) {
+      gdk_draw_pixmap(pm, civ_gc, tile->pixmap,
+                      0, 0, canvas_x, canvas_y,
+                      tile->width, tile->height);
+    } else {
+      if (fill_bg) {
+	if (pplayer) {
+	  gdk_gc_set_foreground(fill_bg_gc,
+				colors_standard[player_color(pplayer)]);
+	} else {
+	  gdk_gc_set_foreground(fill_bg_gc,
+				colors_standard[COLOR_STD_BACKGROUND]);	
+	}
+	gdk_draw_rectangle(pm, fill_bg_gc, TRUE,
+			   canvas_x, canvas_y,
+			   NORMAL_TILE_WIDTH, NORMAL_TILE_HEIGHT);
+      } else {
+	/* first tile without mask */
+	gdk_draw_pixmap(pm, civ_gc, tile_sprs[0]->pixmap,
+			0, 0, canvas_x, canvas_y,
+			tile_sprs[0]->width, tile_sprs[0]->height);
+	i++;
+      }
+
+      for (;i<count; i++) {
+	if (tile_sprs[i]) {
+	  pixmap_put_overlay_tile(pm, canvas_x, canvas_y, tile_sprs[i]);
+	}
+      }
+    }
     if (draw_map_grid && !citymode) {
       int here_in_radius =
 	player_in_city_radius(game.player_ptr, x, y);
--- ./client/gui-gtk/mapview.h	2001/08/11 07:43:46	1.1
+++ ./client/gui-gtk/mapview.h	2001/08/11 08:43:08
@@ -52,5 +52,6 @@
 
 /* contains the x0, y0 coordinates of the upper left corner block */
 extern int map_view_x0, map_view_y0;
+void gui_cleanup(void);
 
 #endif  /* FC__MAPVIEW_H */
--- ./client/gui-gtk/gui_main.c	2001/08/11 07:54:15	1.2
+++ ./client/gui-gtk/gui_main.c	2001/08/11 08:43:10
@@ -145,16 +145,22 @@
 static void print_usage(const char *argv0)
 {
   /* add client-specific usage information here */
+  fprintf(stderr, _("  --use-tile-cache\tCache stacked tiles for better performance\n"));
+  fprintf(stderr, _("  --tile-cache-size NUM\tSet cache size to NUM.  Default is %d\n"), tile_cache_size);
+  fprintf(stderr, _("  --min-cached-tile-depth NUM\tOnly cache tiles stacked NUM or higher.  Default is %d\n"), min_cached_tile_depth);
   fprintf(stderr, _("Report bugs to <%s>.\n"), BUG_EMAIL_ADDRESS);
 }
 
 
 static char *ui_single_options[] = {
   "--help",
+  "--use-tile-cache",
   NULL
 };
 
 static char *ui_arg_options[] = {
+  "--tile-cache-size",
+  "--min-cached-tile-depth",
   NULL
 };
 
@@ -189,6 +195,19 @@
       print_usage(argv[0]);
       exit(0);
     }
+    else if (is_option("--use-tile-cache", argv[i]))
+      use_tile_cache = 1;
+    else if ((option = get_option("--tile-cache-size", argv, &i, argc)) !=
+	     NULL) {
+      tile_cache_size = atoi(option);
+      if (tile_cache_size < 1) {
+	fprintf(stderr, _("tile-cache-size must be greater than 0!\n"));
+	exit(1);
+      }
+    }
+    else if ((option = get_option("--min-cached-tile-depth", argv, &i, argc))
+	     != NULL)
+      min_cached_tile_depth = atoi(option);
     i += 1;
   }
 }
@@ -821,6 +840,7 @@
   set_client_state(CLIENT_PRE_GAME_STATE);
 
   gtk_main();
+  gui_cleanup();
 }
 
 /**************************************************************************