diff options
Diffstat (limited to 'src/uta.c')
| -rw-r--r-- | src/uta.c | 1116 |
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); + } +} |