inicial

1 files changed, 1116 insertions, 0 deletions

diff --git a/src/uta.c b/src/uta.c
new file mode 100644
index 0000000..8df97bc
--- /dev/null
+++ b/src/uta.c
@@ -0,0 +1,1116 @@
+/* Eye of Mate image viewer - Microtile array utilities
+ *
+ * Copyright (C) 2000-2009 The Free Software Foundation
+ *
+ * Author: Federico Mena-Quintero <[email protected]>
+ *
+ * Portions based on code from libart_lgpl by Raph Levien.
+ *
+ * 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 2 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, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#include <config.h>
+#include <glib.h>
+#include "uta.h"
+
+#define EOM_UTA_BBOX_CONS(x0, y0, x1, y1) (((x0) << 24) | ((y0) << 16) | \
+				       ((x1) << 8) | (y1))
+
+#define EOM_UTA_BBOX_X0(ub) ((ub) >> 24)
+#define EOM_UTA_BBOX_Y0(ub) (((ub) >> 16) & 0xff)
+#define EOM_UTA_BBOX_X1(ub) (((ub) >> 8) & 0xff)
+#define EOM_UTA_BBOX_Y1(ub) ((ub) & 0xff)
+
+#define eom_renew(p, type, n) ((type *)g_realloc (p, (n) * sizeof(type)))
+/* This one must be used carefully - in particular, p and max should
+   be variables. They can also be pstruct->el lvalues. */
+#define eom_expand(p, type, max) do { if(max) { p = eom_renew (p, type, max <<= 1); } else { max = 1; p = g_new(type, 1); } } while (0)
+
+
+
+/**
+ * eom_uta_new: Allocate a new uta.
+ * @x0: Left coordinate of uta.
+ * @y0: Top coordinate of uta.
+ * @x1: Right coordinate of uta.
+ * @y1: Bottom coordinate of uta.
+ *
+ * Allocates a new microtile array. The arguments are in units of
+ * tiles, not pixels.
+ *
+ * Returns: the newly allocated #EomUta.
+ **/
+static EomUta *
+eom_uta_new (int x0, int y0, int x1, int y1)
+{
+  EomUta *uta;
+
+  uta = g_new (EomUta, 1);
+  uta->x0 = x0;
+  uta->y0 = y0;
+  uta->width = x1 - x0;
+  uta->height = y1 - y0;
+
+  uta->utiles = g_new0 (EomUtaBbox, uta->width * uta->height);
+
+  return uta;
+}
+
+/**
+ * eom_uta_free: Free a uta.
+ * @uta: The uta to free.
+ *
+ * Frees the microtile array structure, including the actual microtile
+ * data.
+ **/
+void
+eom_uta_free (EomUta *uta)
+{
+  g_free (uta->utiles);
+  g_free (uta);
+}
+
+/**
+ * eom_irect_intersect: Find intersection of two integer rectangles.
+ * @dest: Where the result is stored.
+ * @src1: A source rectangle.
+ * @src2: Another source rectangle.
+ *
+ * Finds the intersection of @src1 and @src2.
+ **/
+void
+eom_irect_intersect (EomIRect *dest, const EomIRect *src1, const EomIRect *src2) {
+  dest->x0 = MAX (src1->x0, src2->x0);
+  dest->y0 = MAX (src1->y0, src2->y0);
+  dest->x1 = MIN (src1->x1, src2->x1);
+  dest->y1 = MIN (src1->y1, src2->y1);
+}
+
+/**
+ * eom_irect_empty: Determine whether integer rectangle is empty.
+ * @src: The source rectangle.
+ *
+ * Return value: TRUE if @src is an empty rectangle, FALSE otherwise.
+ **/
+int
+eom_irect_empty (const EomIRect *src) {
+  return (src->x1 <= src->x0 || src->y1 <= src->y0);
+}
+
+/**
+ * eom_uta_from_irect: Generate uta covering a rectangle.
+ * @bbox: The source rectangle.
+ *
+ * Generates a uta exactly covering @bbox. Please do not call this
+ * function with a @bbox with zero height or width.
+ *
+ * Return value: the new uta.
+ **/
+static EomUta *
+eom_uta_from_irect (EomIRect *bbox)
+{
+  EomUta *uta;
+  EomUtaBbox *utiles;
+  EomUtaBbox bb;
+  int width, height;
+  int x, y;
+  int xf0, yf0, xf1, yf1;
+  int ix;
+
+  uta = g_new (EomUta, 1);
+  uta->x0 = bbox->x0 >> EOM_UTILE_SHIFT;
+  uta->y0 = bbox->y0 >> EOM_UTILE_SHIFT;
+  width = ((bbox->x1 + EOM_UTILE_SIZE - 1) >> EOM_UTILE_SHIFT) - uta->x0;
+  height = ((bbox->y1 + EOM_UTILE_SIZE - 1) >> EOM_UTILE_SHIFT) - uta->y0;
+  utiles = g_new (EomUtaBbox, width * height);
+
+  uta->width = width;
+  uta->height = height;
+  uta->utiles = utiles;
+
+  xf0 = bbox->x0 & (EOM_UTILE_SIZE - 1);
+  yf0 = bbox->y0 & (EOM_UTILE_SIZE - 1);
+  xf1 = ((bbox->x1 - 1) & (EOM_UTILE_SIZE - 1)) + 1;
+  yf1 = ((bbox->y1 - 1) & (EOM_UTILE_SIZE - 1)) + 1;
+  if (height == 1)
+    {
+      if (width == 1)
+	utiles[0] = EOM_UTA_BBOX_CONS (xf0, yf0, xf1, yf1);
+      else
+	{
+	  utiles[0] = EOM_UTA_BBOX_CONS (xf0, yf0, EOM_UTILE_SIZE, yf1);
+	  bb = EOM_UTA_BBOX_CONS (0, yf0, EOM_UTILE_SIZE, yf1);
+	  for (x = 1; x < width - 1; x++)
+	    utiles[x] = bb;
+	  utiles[x] = EOM_UTA_BBOX_CONS (0, yf0, xf1, yf1);
+	}
+    }
+  else
+    {
+      if (width == 1)
+	{
+	  utiles[0] = EOM_UTA_BBOX_CONS (xf0, yf0, xf1, EOM_UTILE_SIZE);
+	  bb = EOM_UTA_BBOX_CONS (xf0, 0, xf1, EOM_UTILE_SIZE);
+	  for (y = 1; y < height - 1; y++)
+	    utiles[y] = bb;
+	  utiles[y] = EOM_UTA_BBOX_CONS (xf0, 0, xf1, yf1);
+	}
+      else
+	{
+	  utiles[0] =
+	    EOM_UTA_BBOX_CONS (xf0, yf0, EOM_UTILE_SIZE, EOM_UTILE_SIZE);
+	  bb = EOM_UTA_BBOX_CONS (0, yf0, EOM_UTILE_SIZE, EOM_UTILE_SIZE);
+	  for (x = 1; x < width - 1; x++)
+	    utiles[x] = bb;
+	  utiles[x] = EOM_UTA_BBOX_CONS (0, yf0, xf1, EOM_UTILE_SIZE);
+	  ix = width;
+	  for (y = 1; y < height - 1; y++)
+	    {
+	      utiles[ix++] =
+		EOM_UTA_BBOX_CONS (xf0, 0, EOM_UTILE_SIZE, EOM_UTILE_SIZE);
+	      bb = EOM_UTA_BBOX_CONS (0, 0, EOM_UTILE_SIZE, EOM_UTILE_SIZE);
+	      for (x = 1; x < width - 1; x++)
+		utiles[ix++] = bb;
+	      utiles[ix++] = EOM_UTA_BBOX_CONS (0, 0, xf1, EOM_UTILE_SIZE);
+	    }
+	  utiles[ix++] = EOM_UTA_BBOX_CONS (xf0, 0, EOM_UTILE_SIZE, yf1);
+	  bb = EOM_UTA_BBOX_CONS (0, 0, EOM_UTILE_SIZE, yf1);
+	  for (x = 1; x < width - 1; x++)
+	    utiles[ix++] = bb;
+	  utiles[ix++] = EOM_UTA_BBOX_CONS (0, 0, xf1, yf1);
+	}
+    }
+  return uta;
+}
+
+
+/**
+ * uta_ensure_size:
+ * @uta: A microtile array.
+ * @x1: Left microtile coordinate that must fit in new array.
+ * @y1: Top microtile coordinate that must fit in new array.
+ * @x2: Right microtile coordinate that must fit in new array.
+ * @y2: Bottom microtile coordinate that must fit in new array.
+ *
+ * Ensures that the size of a microtile array is big enough to fit the specified
+ * microtile coordinates.  If it is not big enough, the specified @uta will be
+ * freed and a new one will be returned.  Otherwise, the original @uta will be
+ * returned.  If a new microtile array needs to be created, this function will
+ * copy the @uta's contents to the new array.
+ *
+ * Note that the specified coordinates must have already been scaled down by the
+ * ART_UTILE_SHIFT factor.
+ *
+ * Return value: The same value as @uta if the original microtile array was
+ * big enough to fit the specified microtile coordinates, or a new array if
+ * it needed to be grown.  In the second case, the original @uta will be
+ * freed automatically.
+ **/
+EomUta *
+uta_ensure_size (EomUta *uta, int x1, int y1, int x2, int y2)
+{
+	EomUta *new_uta;
+	EomUtaBbox *utiles, *new_utiles;
+	int new_ofs, ofs;
+	int x, y;
+
+	g_return_val_if_fail (x1 < x2, NULL);
+	g_return_val_if_fail (y1 < y2, NULL);
+
+	if (!uta)
+		return eom_uta_new (x1, y1, x2, y2);
+
+	if (x1 >= uta->x0
+	    && y1 >= uta->y0
+	    && x2 <= uta->x0 + uta->width
+	    && y2 <= uta->y0 + uta->height)
+		return uta;
+
+	new_uta = g_new (EomUta, 1);
+
+	new_uta->x0 = MIN (uta->x0, x1);
+	new_uta->y0 = MIN (uta->y0, y1);
+	new_uta->width = MAX (uta->x0 + uta->width, x2) - new_uta->x0;
+	new_uta->height = MAX (uta->y0 + uta->height, y2) - new_uta->y0;
+	new_uta->utiles = g_new (EomUtaBbox, new_uta->width * new_uta->height);
+
+	utiles = uta->utiles;
+	new_utiles = new_uta->utiles;
+
+	new_ofs = 0;
+
+	for (y = new_uta->y0; y < new_uta->y0 + new_uta->height; y++) {
+		if (y < uta->y0 || y >= uta->y0 + uta->height)
+			for (x = 0; x < new_uta->width; x++)
+				new_utiles[new_ofs++] = 0;
+		else {
+			ofs = (y - uta->y0) * uta->width;
+
+			for (x = new_uta->x0; x < new_uta->x0 + new_uta->width; x++)
+				if (x < uta->x0 || x >= uta->x0 + uta->width)
+					new_utiles[new_ofs++] = 0;
+				else
+					new_utiles[new_ofs++] = utiles[ofs++];
+		}
+	}
+
+	eom_uta_free (uta);
+	return new_uta;
+}
+
+/**
+ * uta_add_rect:
+ * @uta: A microtile array, or NULL if a new array should be created.
+ * @x1: Left coordinate of rectangle.
+ * @y1: Top coordinate of rectangle.
+ * @x2: Right coordinate of rectangle.
+ * @y2: Bottom coordinate of rectangle.
+ *
+ * Adds the specified rectangle to a microtile array.  The array is
+ * grown to fit the rectangle if necessary.
+ *
+ * Return value: The original @uta, or a new microtile array if the original one
+ * needed to be grown to fit the specified rectangle.  In the second case, the
+ * original @uta will be freed automatically.
+ **/
+EomUta *
+uta_add_rect (EomUta *uta, int x1, int y1, int x2, int y2)
+{
+	EomUtaBbox *utiles;
+	EomUtaBbox bb;
+	int rect_x1, rect_y1, rect_x2, rect_y2;
+	int xf1, yf1, xf2, yf2;
+	int x, y;
+	int ofs;
+
+	g_return_val_if_fail (x1 < x2, NULL);
+	g_return_val_if_fail (y1 < y2, NULL);
+
+	/* Empty uta */
+
+	if (!uta) {
+		EomIRect r;
+
+		r.x0 = x1;
+		r.y0 = y1;
+		r.x1 = x2;
+		r.y1 = y2;
+
+		return eom_uta_from_irect (&r);
+	}
+
+	/* Grow the uta if necessary */
+
+	rect_x1 = x1 >> EOM_UTILE_SHIFT;
+	rect_y1 = y1 >> EOM_UTILE_SHIFT;
+	rect_x2 = (x2 + EOM_UTILE_SIZE - 1) >> EOM_UTILE_SHIFT;
+	rect_y2 = (y2 + EOM_UTILE_SIZE - 1) >> EOM_UTILE_SHIFT;
+
+	uta = uta_ensure_size (uta, rect_x1, rect_y1, rect_x2, rect_y2);
+
+	/* Add the rectangle */
+
+	xf1 = x1 & (EOM_UTILE_SIZE - 1);
+	yf1 = y1 & (EOM_UTILE_SIZE - 1);
+	xf2 = ((x2 - 1) & (EOM_UTILE_SIZE - 1)) + 1;
+	yf2 = ((y2 - 1) & (EOM_UTILE_SIZE - 1)) + 1;
+
+	utiles = uta->utiles;
+
+	ofs = (rect_y1 - uta->y0) * uta->width + rect_x1 - uta->x0;
+
+	if (rect_y2 - rect_y1 == 1) {
+		if (rect_x2 - rect_x1 == 1) {
+			bb = utiles[ofs];
+			if (bb == 0)
+				utiles[ofs] = EOM_UTA_BBOX_CONS (
+					xf1, yf1, xf2, yf2);
+			else
+				utiles[ofs] = EOM_UTA_BBOX_CONS (
+					MIN (EOM_UTA_BBOX_X0 (bb), xf1),
+					MIN (EOM_UTA_BBOX_Y0 (bb), yf1),
+					MAX (EOM_UTA_BBOX_X1 (bb), xf2),
+					MAX (EOM_UTA_BBOX_Y1 (bb), yf2));
+		} else {
+			/* Leftmost tile */
+			bb = utiles[ofs];
+			if (bb == 0)
+				utiles[ofs++] = EOM_UTA_BBOX_CONS (
+					xf1, yf1, EOM_UTILE_SIZE, yf2);
+			else
+				utiles[ofs++] = EOM_UTA_BBOX_CONS (
+					MIN (EOM_UTA_BBOX_X0 (bb), xf1),
+					MIN (EOM_UTA_BBOX_Y0 (bb), yf1),
+					EOM_UTILE_SIZE,
+					MAX (EOM_UTA_BBOX_Y1 (bb), yf2));
+
+			/* Tiles in between */
+			for (x = rect_x1 + 1; x < rect_x2 - 1; x++) {
+				bb = utiles[ofs];
+				if (bb == 0)
+					utiles[ofs++] = EOM_UTA_BBOX_CONS (
+						0, yf1, EOM_UTILE_SIZE, yf2);
+				else
+					utiles[ofs++] = EOM_UTA_BBOX_CONS (
+						0,
+						MIN (EOM_UTA_BBOX_Y0 (bb), yf1),
+						EOM_UTILE_SIZE,
+						MAX (EOM_UTA_BBOX_Y1 (bb), yf2));
+			}
+
+			/* Rightmost tile */
+			bb = utiles[ofs];
+			if (bb == 0)
+				utiles[ofs] = EOM_UTA_BBOX_CONS (
+					0, yf1, xf2, yf2);
+			else
+				utiles[ofs] = EOM_UTA_BBOX_CONS (
+					0,
+					MIN (EOM_UTA_BBOX_Y0 (bb), yf1),
+					MAX (EOM_UTA_BBOX_X1 (bb), xf2),
+					MAX (EOM_UTA_BBOX_Y1 (bb), yf2));
+		}
+	} else {
+		if (rect_x2 - rect_x1 == 1) {
+			/* Topmost tile */
+			bb = utiles[ofs];
+			if (bb == 0)
+				utiles[ofs] = EOM_UTA_BBOX_CONS (
+					xf1, yf1, xf2, EOM_UTILE_SIZE);
+			else
+				utiles[ofs] = EOM_UTA_BBOX_CONS (
+					MIN (EOM_UTA_BBOX_X0 (bb), xf1),
+					MIN (EOM_UTA_BBOX_Y0 (bb), yf1),
+					MAX (EOM_UTA_BBOX_X1 (bb), xf2),
+					EOM_UTILE_SIZE);
+			ofs += uta->width;
+
+			/* Tiles in between */
+			for (y = rect_y1 + 1; y < rect_y2 - 1; y++) {
+				bb = utiles[ofs];
+				if (bb == 0)
+					utiles[ofs] = EOM_UTA_BBOX_CONS (
+						xf1, 0, xf2, EOM_UTILE_SIZE);
+				else
+					utiles[ofs] = EOM_UTA_BBOX_CONS (
+						MIN (EOM_UTA_BBOX_X0 (bb), xf1),
+						0,
+						MAX (EOM_UTA_BBOX_X1 (bb), xf2),
+						EOM_UTILE_SIZE);
+				ofs += uta->width;
+			}
+
+			/* Bottommost tile */
+			bb = utiles[ofs];
+			if (bb == 0)
+				utiles[ofs] = EOM_UTA_BBOX_CONS (
+					xf1, 0, xf2, yf2);
+			else
+				utiles[ofs] = EOM_UTA_BBOX_CONS (
+					MIN (EOM_UTA_BBOX_X0 (bb), xf1),
+					0,
+					MAX (EOM_UTA_BBOX_X1 (bb), xf2),
+					MAX (EOM_UTA_BBOX_Y1 (bb), yf2));
+		} else {
+			/* Top row, leftmost tile */
+			bb = utiles[ofs];
+			if (bb == 0)
+				utiles[ofs++] = EOM_UTA_BBOX_CONS (
+					xf1, yf1, EOM_UTILE_SIZE, EOM_UTILE_SIZE);
+			else
+				utiles[ofs++] = EOM_UTA_BBOX_CONS (
+					MIN (EOM_UTA_BBOX_X0 (bb), xf1),
+					MIN (EOM_UTA_BBOX_Y0 (bb), yf1),
+					EOM_UTILE_SIZE,
+					EOM_UTILE_SIZE);
+
+			/* Top row, in between */
+			for (x = rect_x1 + 1; x < rect_x2 - 1; x++) {
+				bb = utiles[ofs];
+				if (bb == 0)
+					utiles[ofs++] = EOM_UTA_BBOX_CONS (
+						0, yf1, EOM_UTILE_SIZE, EOM_UTILE_SIZE);
+				else
+					utiles[ofs++] = EOM_UTA_BBOX_CONS (
+						0,
+						MIN (EOM_UTA_BBOX_Y0 (bb), yf1),
+						EOM_UTILE_SIZE,
+						EOM_UTILE_SIZE);
+			}
+
+			/* Top row, rightmost tile */
+			bb = utiles[ofs];
+			if (bb == 0)
+				utiles[ofs] = EOM_UTA_BBOX_CONS (
+					0, yf1, xf2, EOM_UTILE_SIZE);
+			else
+				utiles[ofs] = EOM_UTA_BBOX_CONS (
+					0,
+					MIN (EOM_UTA_BBOX_Y0 (bb), yf1),
+					MAX (EOM_UTA_BBOX_X1 (bb), xf2),
+					EOM_UTILE_SIZE);
+
+			ofs += uta->width - (rect_x2 - rect_x1 - 1);
+
+			/* Rows in between */
+			for (y = rect_y1 + 1; y < rect_y2 - 1; y++) {
+				/* Leftmost tile */
+				bb = utiles[ofs];
+				if (bb == 0)
+					utiles[ofs++] = EOM_UTA_BBOX_CONS (
+						xf1, 0, EOM_UTILE_SIZE, EOM_UTILE_SIZE);
+				else
+					utiles[ofs++] = EOM_UTA_BBOX_CONS (
+						MIN (EOM_UTA_BBOX_X0 (bb), xf1),
+						0,
+						EOM_UTILE_SIZE,
+						EOM_UTILE_SIZE);
+
+				/* Tiles in between */
+				bb = EOM_UTA_BBOX_CONS (0, 0, EOM_UTILE_SIZE, EOM_UTILE_SIZE);
+				for (x = rect_x1 + 1; x < rect_x2 - 1; x++)
+					utiles[ofs++] = bb;
+
+				/* Rightmost tile */
+				bb = utiles[ofs];
+				if (bb == 0)
+					utiles[ofs] = EOM_UTA_BBOX_CONS (
+						0, 0, xf2, EOM_UTILE_SIZE);
+				else
+					utiles[ofs] = EOM_UTA_BBOX_CONS (
+						0,
+						0,
+						MAX (EOM_UTA_BBOX_X1 (bb), xf2),
+						EOM_UTILE_SIZE);
+
+				ofs += uta->width - (rect_x2 - rect_x1 - 1);
+			}
+
+			/* Bottom row, leftmost tile */
+			bb = utiles[ofs];
+			if (bb == 0)
+				utiles[ofs++] = EOM_UTA_BBOX_CONS (
+					xf1, 0, EOM_UTILE_SIZE, yf2);
+			else
+				utiles[ofs++] = EOM_UTA_BBOX_CONS (
+					MIN (EOM_UTA_BBOX_X0 (bb), xf1),
+					0,
+					EOM_UTILE_SIZE,
+					MAX (EOM_UTA_BBOX_Y1 (bb), yf2));
+
+			/* Bottom row, tiles in between */
+			for (x = rect_x1 + 1; x < rect_x2 - 1; x++) {
+				bb = utiles[ofs];
+				if (bb == 0)
+					utiles[ofs++] = EOM_UTA_BBOX_CONS (
+						0, 0, EOM_UTILE_SIZE, yf2);
+				else
+					utiles[ofs++] = EOM_UTA_BBOX_CONS (
+						0,
+						0,
+						EOM_UTILE_SIZE,
+						MAX (EOM_UTA_BBOX_Y1 (bb), yf2));
+			}
+
+			/* Bottom row, rightmost tile */
+			bb = utiles[ofs];
+			if (bb == 0)
+				utiles[ofs] = EOM_UTA_BBOX_CONS (
+					0, 0, xf2, yf2);
+			else
+				utiles[ofs] = EOM_UTA_BBOX_CONS (
+					0,
+					0,
+					MAX (EOM_UTA_BBOX_X1 (bb), xf2),
+					MAX (EOM_UTA_BBOX_Y1 (bb), yf2));
+		}
+	}
+
+	return uta;
+}
+
+/**
+ * uta_remove_rect:
+ * @uta: A microtile array.
+ * @x1: Left coordinate of rectangle.
+ * @y1: Top coordinate of rectangle.
+ * @x2: Right coordinate of rectangle.
+ * @y2: Bottom coordinate of rectangle.
+ *
+ * Removes a rectangular region from the specified microtile array.  Due to the
+ * way microtile arrays represent regions, the tiles at the edge of the
+ * rectangle may not be clipped exactly.
+ **/
+void
+uta_remove_rect (EomUta *uta, int x1, int y1, int x2, int y2)
+{
+	EomUtaBbox *utiles;
+	int rect_x1, rect_y1, rect_x2, rect_y2;
+	int clip_x1, clip_y1, clip_x2, clip_y2;
+	int xf1, yf1, xf2, yf2;
+	int ofs;
+	int x, y;
+
+	g_return_if_fail (uta != NULL);
+	g_return_if_fail (x1 <= x2);
+	g_return_if_fail (y1 <= y2);
+
+	if (x1 == x2 || y1 == y2)
+		return;
+
+	rect_x1 = x1 >> EOM_UTILE_SHIFT;
+	rect_y1 = y1 >> EOM_UTILE_SHIFT;
+	rect_x2 = (x2 + EOM_UTILE_SIZE - 1) >> EOM_UTILE_SHIFT;
+	rect_y2 = (y2 + EOM_UTILE_SIZE - 1) >> EOM_UTILE_SHIFT;
+
+	clip_x1 = MAX (rect_x1, uta->x0);
+	clip_y1 = MAX (rect_y1, uta->y0);
+	clip_x2 = MIN (rect_x2, uta->x0 + uta->width);
+	clip_y2 = MIN (rect_y2, uta->y0 + uta->height);
+
+	if (clip_x1 >= clip_x2 || clip_y1 >= clip_y2)
+		return;
+
+	xf1 = x1 & (EOM_UTILE_SIZE - 1);
+	yf1 = y1 & (EOM_UTILE_SIZE - 1);
+	xf2 = ((x2 - 1) & (EOM_UTILE_SIZE - 1)) + 1;
+	yf2 = ((y2 - 1) & (EOM_UTILE_SIZE - 1)) + 1;
+
+	utiles = uta->utiles;
+
+	ofs = (clip_y1 - uta->y0) * uta->width + clip_x1 - uta->x0;
+
+	for (y = clip_y1; y < clip_y2; y++) {
+		int cy1, cy2;
+
+		if (y == rect_y1)
+			cy1 = yf1;
+		else
+			cy1 = 0;
+
+		if (y == rect_y2 - 1)
+			cy2 = yf2;
+		else
+			cy2 = EOM_UTILE_SIZE;
+
+		for (x = clip_x1; x < clip_x2; x++) {
+			int cx1, cx2;
+			EomUtaBbox bb;
+			int bb_x1, bb_y1, bb_x2, bb_y2;
+			int bb_cx1, bb_cy1, bb_cx2, bb_cy2;
+
+			bb = utiles[ofs];
+			bb_x1 = EOM_UTA_BBOX_X0 (bb);
+			bb_y1 = EOM_UTA_BBOX_Y0 (bb);
+			bb_x2 = EOM_UTA_BBOX_X1 (bb);
+			bb_y2 = EOM_UTA_BBOX_Y1 (bb);
+
+			if (x == rect_x1)
+				cx1 = xf1;
+			else
+				cx1 = 0;
+
+			if (x == rect_x2 - 1)
+				cx2 = xf2;
+			else
+				cx2 = EOM_UTILE_SIZE;
+
+			/* Clip top and bottom */
+
+			if (cx1 <= bb_x1 && cx2 >= bb_x2) {
+				if (cy1 <= bb_y1 && cy2 > bb_y1)
+					bb_cy1 = cy2;
+				else
+					bb_cy1 = bb_y1;
+
+				if (cy1 < bb_y2 && cy2 >= bb_y2)
+					bb_cy2 = cy1;
+				else
+					bb_cy2 = bb_y2;
+			} else {
+				bb_cy1 = bb_y1;
+				bb_cy2 = bb_y2;
+			}
+
+			/* Clip left and right */
+
+			if (cy1 <= bb_y1 && cy2 >= bb_y2) {
+				if (cx1 <= bb_x1 && cx2 > bb_x1)
+					bb_cx1 = cx2;
+				else
+					bb_cx1 = bb_x1;
+
+				if (cx1 < bb_x2 && cx2 >= bb_x2)
+					bb_cx2 = cx1;
+				else
+					bb_cx2 = bb_x2;
+			} else {
+				bb_cx1 = bb_x1;
+				bb_cx2 = bb_x2;
+			}
+
+			if (bb_cx1 < bb_cx2 && bb_cy1 < bb_cy2)
+				utiles[ofs] = EOM_UTA_BBOX_CONS (bb_cx1, bb_cy1,
+								 bb_cx2, bb_cy2);
+			else
+				utiles[ofs] = 0;
+
+			ofs++;
+		}
+
+		ofs += uta->width - (clip_x2 - clip_x1);
+	}
+}
+
+void
+uta_find_first_glom_rect (EomUta *uta, EomIRect *rect, int max_width, int max_height)
+{
+  EomIRect *rects;
+  int n_rects, n_rects_max;
+  int x, y;
+  int width, height;
+  int ix;
+  int left_ix;
+  EomUtaBbox *utiles;
+  EomUtaBbox bb;
+  int x0, y0, x1, y1;
+  int *glom;
+  int glom_rect;
+
+  n_rects = 0;
+  n_rects_max = 1;
+  rects = g_new (EomIRect, n_rects_max);
+
+  width = uta->width;
+  height = uta->height;
+  utiles = uta->utiles;
+
+  glom = g_new (int, width * height);
+  for (ix = 0; ix < width * height; ix++)
+    glom[ix] = -1;
+
+  ix = 0;
+  for (y = 0; y < height; y++)
+    for (x = 0; x < width; x++)
+      {
+	bb = utiles[ix];
+	if (bb)
+	  {
+	    x0 = ((uta->x0 + x) << EOM_UTILE_SHIFT) + EOM_UTA_BBOX_X0(bb);
+	    y0 = ((uta->y0 + y) << EOM_UTILE_SHIFT) + EOM_UTA_BBOX_Y0(bb);
+	    y1 = ((uta->y0 + y) << EOM_UTILE_SHIFT) + EOM_UTA_BBOX_Y1(bb);
+
+	    left_ix = ix;
+	    /* now try to extend to the right */
+	    while (x != width - 1 &&
+		   EOM_UTA_BBOX_X1(bb) == EOM_UTILE_SIZE &&
+		   (((bb & 0xffffff) ^ utiles[ix + 1]) & 0xffff00ff) == 0 &&
+		   (((uta->x0 + x + 1) << EOM_UTILE_SHIFT) +
+		    EOM_UTA_BBOX_X1(utiles[ix + 1]) -
+		    x0) <= max_width)
+	      {
+		bb = utiles[ix + 1];
+		ix++;
+		x++;
+	      }
+	    x1 = ((uta->x0 + x) << EOM_UTILE_SHIFT) + EOM_UTA_BBOX_X1(bb);
+
+
+	    /* if rectangle nonempty */
+	    if ((x1 ^ x0) || (y1 ^ y0))
+	      {
+		/* try to glom onto an existing rectangle */
+		glom_rect = glom[left_ix];
+		if (glom_rect != -1 &&
+		    x0 == rects[glom_rect].x0 &&
+		    x1 == rects[glom_rect].x1 &&
+		    y0 == rects[glom_rect].y1 &&
+		    y1 - rects[glom_rect].y0 <= max_height)
+		  {
+		    rects[glom_rect].y1 = y1;
+		  }
+		else
+		  {
+		    if (n_rects == n_rects_max)
+		      eom_expand (rects, EomIRect, n_rects_max);
+		    rects[n_rects].x0 = x0;
+		    rects[n_rects].y0 = y0;
+		    rects[n_rects].x1 = x1;
+		    rects[n_rects].y1 = y1;
+		    glom_rect = n_rects;
+		    n_rects++;
+		  }
+		if (y != height - 1)
+		  glom[left_ix + width] = glom_rect;
+	      }
+	  }
+	ix++;
+      }
+
+  if (n_rects > 0) {
+	  rect->x0 = rects[0].x0;
+	  rect->y0 = rects[0].y0;
+	  rect->x1 = rects[0].x1;
+	  rect->y1 = rects[0].y1;
+  } else
+	  rect->x0 = rect->y0 = rect->x1 = rect->y1 = 0;
+
+  g_free (glom);
+  g_free (rects);
+}
+
+#if 0
+
+void
+uta_find_first_glom_rect (EomUta *uta, EomIRect *rect, int max_width, int max_height)
+{
+	EomUtaBbox *utiles;
+	EomUtaBbox bb;
+	int width, height;
+	int ofs;
+	int x, y;
+	int x1, y1, x2, y2;
+
+	g_return_if_fail (uta != NULL);
+	g_return_if_fail (rect != NULL);
+	g_return_if_fail (max_width > 0 && max_height > 0);
+
+	utiles = uta->utiles;
+	width = uta->width;
+	height = uta->height;
+
+	ofs = 0;
+
+	/* We find the first nonempty tile, and then grow the rectangle to the
+	 * right and then down.
+	 */
+
+	x1 = y1 = x2 = y2 = 0;
+
+	for (y = 0; y < height; y++) {
+		for (x = 0; x < width; x++) {
+			bb = utiles[ofs];
+
+			if (!bb) {
+				ofs++;
+				continue;
+			}
+
+			x1 = ((uta->x0 + x) << EOM_UTILE_SHIFT) + EOM_UTA_BBOX_X0 (bb);
+			y1 = ((uta->y0 + y) << EOM_UTILE_SHIFT) + EOM_UTA_BBOX_Y0 (bb);
+			y2 = ((uta->y0 + y) << EOM_UTILE_SHIFT) + EOM_UTA_BBOX_Y1 (bb);
+
+			/* Grow to the right */
+
+			while (x != width - 1
+			       && EOM_UTA_BBOX_X1 (bb) == EOM_UTILE_SIZE
+			       && (((bb & 0xffffff) ^ utiles[ofs + 1]) & 0xffff00ff) == 0
+			       && (((uta->x0 + x + 1) << EOM_UTILE_SHIFT)
+				   + EOM_UTA_BBOX_X1 (utiles[ofs + 1])
+				   - x1) <= max_width) {
+				ofs++;
+				bb = utiles[ofs];
+				x++;
+			}
+
+			x2 = ((uta->x0 + x) << EOM_UTILE_SHIFT) + EOM_UTA_BBOX_X1 (bb);
+			goto grow_down;
+		}
+	}
+
+ grow_down:
+
+}
+
+#endif
+
+/* Copies a single microtile to another location in the UTA, offsetted by the
+ * specified distance.  A microtile can thus end up being added in a single part
+ * to another microtile, in two parts to two horizontally or vertically adjacent
+ * microtiles, or in four parts to a 2x2 square of microtiles.
+ *
+ * This is basically a normal BitBlt but with copying-forwards-to-the-destination
+ * instead of fetching-backwards-from-the-source.
+ */
+static void
+copy_tile (EomUta *uta, int x, int y, int xofs, int yofs)
+{
+	EomUtaBbox *utiles;
+	EomUtaBbox bb, dbb;
+	int t_x1, t_y1, t_x2, t_y2;
+	int d_x1, d_y1, d_x2, d_y2;
+	int d_tx1, d_ty1;
+	int d_xf1, d_yf1, d_xf2, d_yf2;
+	int dofs;
+
+	utiles = uta->utiles;
+
+	bb = utiles[(y - uta->y0) * uta->width + x - uta->x0];
+
+	if (bb == 0)
+		return;
+
+	t_x1 = EOM_UTA_BBOX_X0 (bb) + (x << EOM_UTILE_SHIFT);
+	t_y1 = EOM_UTA_BBOX_Y0 (bb) + (y << EOM_UTILE_SHIFT);
+	t_x2 = EOM_UTA_BBOX_X1 (bb) + (x << EOM_UTILE_SHIFT);
+	t_y2 = EOM_UTA_BBOX_Y1 (bb) + (y << EOM_UTILE_SHIFT);
+
+	d_x1 = t_x1 + xofs;
+	d_y1 = t_y1 + yofs;
+	d_x2 = t_x2 + xofs;
+	d_y2 = t_y2 + yofs;
+
+	d_tx1 = d_x1 >> EOM_UTILE_SHIFT;
+	d_ty1 = d_y1 >> EOM_UTILE_SHIFT;
+
+	dofs = (d_ty1 - uta->y0) * uta->width + d_tx1 - uta->x0;
+
+	d_xf1 = d_x1 & (EOM_UTILE_SIZE - 1);
+	d_yf1 = d_y1 & (EOM_UTILE_SIZE - 1);
+	d_xf2 = ((d_x2 - 1) & (EOM_UTILE_SIZE - 1)) + 1;
+	d_yf2 = ((d_y2 - 1) & (EOM_UTILE_SIZE - 1)) + 1;
+
+	if (d_x2 - d_x1 <= EOM_UTILE_SIZE - d_xf1) {
+		if (d_y2 - d_y1 <= EOM_UTILE_SIZE - d_yf1) {
+			if (d_tx1 >= uta->x0 && d_tx1 < uta->x0 + uta->width
+			    && d_ty1 >= uta->y0 && d_ty1 < uta->y0 + uta->height) {
+				dbb = utiles[dofs];
+				if (dbb == 0)
+					utiles[dofs] = EOM_UTA_BBOX_CONS (
+						d_xf1, d_yf1, d_xf2, d_yf2);
+				else
+					utiles[dofs] = EOM_UTA_BBOX_CONS (
+						MIN (EOM_UTA_BBOX_X0 (dbb), d_xf1),
+						MIN (EOM_UTA_BBOX_Y0 (dbb), d_yf1),
+						MAX (EOM_UTA_BBOX_X1 (dbb), d_xf2),
+						MAX (EOM_UTA_BBOX_Y1 (dbb), d_yf2));
+			}
+		} else {
+			/* Top tile */
+			if (d_tx1 >= uta->x0 && d_tx1 < uta->x0 + uta->width
+			    && d_ty1 >= uta->y0 && d_ty1 < uta->y0 + uta->height) {
+				dbb = utiles[dofs];
+				if (dbb == 0)
+					utiles[dofs] = EOM_UTA_BBOX_CONS (
+						d_xf1, d_yf1, d_xf2, EOM_UTILE_SIZE);
+				else
+					utiles[dofs] = EOM_UTA_BBOX_CONS (
+						MIN (EOM_UTA_BBOX_X0 (dbb), d_xf1),
+						MIN (EOM_UTA_BBOX_Y0 (dbb), d_yf1),
+						MAX (EOM_UTA_BBOX_X1 (dbb), d_xf2),
+						EOM_UTILE_SIZE);
+			}
+
+			dofs += uta->width;
+
+			/* Bottom tile */
+			if (d_tx1 >= uta->x0 && d_tx1 < uta->x0 + uta->width
+			    && d_ty1 + 1 >= uta->y0 && d_ty1 + 1 < uta->y0 + uta->height) {
+				dbb = utiles[dofs];
+				if (dbb == 0)
+					utiles[dofs] = EOM_UTA_BBOX_CONS (
+						d_xf1, 0, d_xf2, d_yf2);
+				else
+					utiles[dofs] = EOM_UTA_BBOX_CONS (
+						MIN (EOM_UTA_BBOX_X0 (dbb), d_xf1),
+						0,
+						MAX (EOM_UTA_BBOX_X1 (dbb), d_xf2),
+						MAX (EOM_UTA_BBOX_Y1 (dbb), d_yf2));
+			}
+		}
+	} else {
+		if (d_y2 - d_y1 <= EOM_UTILE_SIZE - d_yf1) {
+			/* Left tile */
+			if (d_tx1 >= uta->x0 && d_tx1 < uta->x0 + uta->width
+			    && d_ty1 >= uta->y0 && d_ty1 < uta->y0 + uta->height) {
+				dbb = utiles[dofs];
+				if (dbb == 0)
+					utiles[dofs] = EOM_UTA_BBOX_CONS (
+						d_xf1, d_yf1, EOM_UTILE_SIZE, d_yf2);
+				else
+					utiles[dofs] = EOM_UTA_BBOX_CONS (
+						MIN (EOM_UTA_BBOX_X0 (dbb), d_xf1),
+						MIN (EOM_UTA_BBOX_Y0 (dbb), d_yf1),
+						EOM_UTILE_SIZE,
+						MAX (EOM_UTA_BBOX_Y1 (dbb), d_yf2));
+			}
+
+			dofs++;
+
+			/* Right tile */
+			if (d_tx1 + 1 >= uta->x0 && d_tx1 + 1 < uta->x0 + uta->width
+			    && d_ty1 >= uta->y0 && d_ty1 < uta->y0 + uta->height) {
+				dbb = utiles[dofs];
+				if (dbb == 0)
+					utiles[dofs] = EOM_UTA_BBOX_CONS (
+						0, d_yf1, d_xf2, d_yf2);
+				else
+					utiles[dofs] = EOM_UTA_BBOX_CONS (
+						0,
+						MIN (EOM_UTA_BBOX_Y0 (dbb), d_yf1),
+						MAX (EOM_UTA_BBOX_X1 (dbb), d_xf2),
+						MAX (EOM_UTA_BBOX_Y1 (dbb), d_yf2));
+			}
+		} else {
+			/* Top left tile */
+			if (d_tx1 >= uta->x0 && d_tx1 < uta->x0 + uta->width
+			    && d_ty1 >= uta->y0 && d_ty1 < uta->y0 + uta->height) {
+				dbb = utiles[dofs];
+				if (dbb == 0)
+					utiles[dofs] = EOM_UTA_BBOX_CONS (
+						d_xf1, d_yf1, EOM_UTILE_SIZE, EOM_UTILE_SIZE);
+				else
+					utiles[dofs] = EOM_UTA_BBOX_CONS (
+						MIN (EOM_UTA_BBOX_X0 (dbb), d_xf1),
+						MIN (EOM_UTA_BBOX_Y0 (dbb), d_yf1),
+						EOM_UTILE_SIZE,
+						EOM_UTILE_SIZE);
+			}
+
+			dofs++;
+
+			/* Top right tile */
+			if (d_tx1 + 1 >= uta->x0 && d_tx1 + 1 < uta->x0 + uta->width
+			    && d_ty1 >= uta->y0 && d_ty1 < uta->y0 + uta->height) {
+				dbb = utiles[dofs];
+				if (dbb == 0)
+					utiles[dofs] = EOM_UTA_BBOX_CONS (
+						0, d_yf1, d_xf2, EOM_UTILE_SIZE);
+				else
+					utiles[dofs] = EOM_UTA_BBOX_CONS (
+						0,
+						MIN (EOM_UTA_BBOX_Y0 (dbb), d_yf1),
+						MAX (EOM_UTA_BBOX_X1 (dbb), d_xf2),
+						EOM_UTILE_SIZE);
+			}
+
+			dofs += uta->width - 1;
+
+			/* Bottom left tile */
+			if (d_tx1 >= uta->x0 && d_tx1 < uta->x0 + uta->width
+			    && d_ty1 + 1 >= uta->y0 && d_ty1 + 1 < uta->y0 + uta->height) {
+				dbb = utiles[dofs];
+				if (dbb == 0)
+					utiles[dofs] = EOM_UTA_BBOX_CONS (
+						d_xf1, 0, EOM_UTILE_SIZE, d_yf2);
+				else
+					utiles[dofs] = EOM_UTA_BBOX_CONS (
+						MIN (EOM_UTA_BBOX_X0 (dbb), d_xf1),
+						0,
+						EOM_UTILE_SIZE,
+						MAX (EOM_UTA_BBOX_Y1 (dbb), d_yf2));
+			}
+
+			dofs++;
+
+			/* Bottom right tile */
+			if (d_tx1 + 1 >= uta->x0 && d_tx1 + 1 < uta->x0 + uta->width
+			    && d_ty1 + 1 >= uta->y0 && d_ty1 + 1 < uta->y0 + uta->height) {
+				dbb = utiles[dofs];
+				if (dbb == 0)
+					utiles[dofs] = EOM_UTA_BBOX_CONS (
+						0, 0, d_xf2, d_yf2);
+				else
+					utiles[dofs] = EOM_UTA_BBOX_CONS (
+						0,
+						0,
+						MAX (EOM_UTA_BBOX_X1 (dbb), d_xf2),
+						MAX (EOM_UTA_BBOX_Y1 (dbb), d_yf2));
+			}
+		}
+	}
+}
+
+/**
+ * uta_copy_area:
+ * @uta: A microtile array.
+ * @src_x: Left coordinate of source rectangle.
+ * @src_y: Top coordinate of source rectangle.
+ * @dest_x: Left coordinate of destination.
+ * @dest_y: Top coordinate of destination.
+ * @width: Width of region to copy.
+ * @height: Height of region to copy.
+ *
+ * Copies a rectangular region within a microtile array.  The array will not be
+ * expanded if the destination area does not fit within it; rather only the area
+ * that fits will be copied.  The source rectangle must be completely contained
+ * within the microtile array.
+ **/
+void
+uta_copy_area (EomUta *uta, int src_x, int src_y, int dest_x, int dest_y, int width, int height)
+{
+	int rect_x1, rect_y1, rect_x2, rect_y2;
+	gboolean top_to_bottom, left_to_right;
+	int xofs, yofs;
+	int x, y;
+
+	g_return_if_fail (uta != NULL);
+	g_return_if_fail (width >= 0 && height >= 0);
+	g_return_if_fail (src_x >= uta->x0 << EOM_UTILE_SHIFT);
+	g_return_if_fail (src_y >= uta->y0 << EOM_UTILE_SHIFT);
+	g_return_if_fail (src_x + width <= (uta->x0 + uta->width) << EOM_UTILE_SHIFT);
+	g_return_if_fail (src_y + height <= (uta->y0 + uta->height) << EOM_UTILE_SHIFT);
+
+	if ((src_x == dest_x && src_y == dest_y) || width == 0 || height == 0)
+		return;
+
+	/* FIXME: This function is not perfect.  It *adds* the copied/offsetted
+	 * area to the original contents of the microtile array, thus growing
+	 * the region more than needed.  The effect should be to "overwrite" the
+	 * original contents, just like XCopyArea() does.  Care needs to be
+	 * taken when the edges of the rectangle do not fall on microtile
+	 * boundaries, because tiles may need to be "split".
+	 *
+	 * Maybe this will work:
+	 *
+	 * 1. Copy the rectangular array of tiles that form the region to a
+	 *    temporary buffer.
+	 *
+	 * 2. uta_remove_rect() the *destination* rectangle from the original
+	 *    microtile array.
+	 *
+	 * 3. Copy back the temporary buffer to the original array while
+	 *    offsetting it in the same way as copy_tile() does.
+	 */
+
+	rect_x1 = src_x >> EOM_UTILE_SHIFT;
+	rect_y1 = src_y >> EOM_UTILE_SHIFT;
+	rect_x2 = (src_x + width + EOM_UTILE_SIZE - 1) >> EOM_UTILE_SHIFT;
+	rect_y2 = (src_y + height + EOM_UTILE_SIZE - 1) >> EOM_UTILE_SHIFT;
+
+	xofs = dest_x - src_x;
+	yofs = dest_y - src_y;
+
+	left_to_right = xofs < 0;
+	top_to_bottom = yofs < 0;
+
+	if (top_to_bottom && left_to_right) {
+		for (y = rect_y1; y < rect_y2; y++)
+			for (x = rect_x1; x < rect_x2; x++)
+				copy_tile (uta, x, y, xofs, yofs);
+	} else if (top_to_bottom && !left_to_right) {
+		for (y = rect_y1; y < rect_y2; y++)
+			for (x = rect_x2 - 1; x >= rect_x1; x--)
+				copy_tile (uta, x, y, xofs, yofs);
+	} else if (!top_to_bottom && left_to_right) {
+		for (y = rect_y2 - 1; y >= rect_y1; y--)
+			for (x = rect_x1; x < rect_x2; x++)
+				copy_tile (uta, x, y, xofs, yofs);
+	} else if (!top_to_bottom && !left_to_right) {
+		for (y = rect_y2 - 1; y >= rect_y1; y--)
+			for (x = rect_x2 - 1; x >= rect_x1; x--)
+				copy_tile (uta, x, y, xofs, yofs);
+	}
+}