rectangle.c

/* rectangle.c: routines for managing the set of screen area rectangles updated
                since the last display
   Copyright (c) 1999-2015 Philip Kendall, Thomas Harte, Witold Filipczyk
                           and Fredrick Meunier

   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.

   Author contact information:

   E-mail: philip-fuse@shadowmagic.org.uk

*/

#include <config.h>

#include <stdlib.h>

#include "fuse.h"
#include "rectangle.h"
#include "settings.h"
#include "ui/ui.h"

#ifndef MAX
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
#endif

// Those rectangles which were modified on the last line to be displayed
static struct rectangle *rectangle_active = NULL;
static size_t rectangle_active_count = 0, rectangle_active_allocated = 0;

// Those rectangles which weren't
struct rectangle *rectangle_inactive = NULL;
size_t rectangle_inactive_count = 0, rectangle_inactive_allocated = 0;


// Add the rectangle {x, line, w, 1} to the list of rectangles to be
// redrawn, either by extending an existing rectangle or creating a new one/
void rectangle_add(int y, int x, int w)
{
    size_t i;
    struct rectangle *ptr;

    // Check through all 'active' rectangles (those which were modified on the previous line)
    // and see if we can use this new rectangle to extend them
    for (i = 0; i < rectangle_active_count; i++) {

        if ((rectangle_active[i].x == x) && (rectangle_active[i].w == w)) {
            rectangle_active[i].h++;
            return;
        }
    }

    // We couldn't find a rectangle to extend, so create a new one
    if (++rectangle_active_count > rectangle_active_allocated) {

        size_t new_alloc;

        new_alloc = rectangle_active_allocated ? (2 * rectangle_active_allocated) : 8;

        ptr = libspectrum_renew(struct rectangle, rectangle_active, new_alloc);

        rectangle_active_allocated = new_alloc;
        rectangle_active = ptr;
    }

    ptr = &rectangle_active[rectangle_active_count - 1];

    ptr->x = x;
    ptr->y = y;
    ptr->w = w;
    ptr->h = 1;
}


static inline int compare_and_merge_rectangles(struct rectangle *source)
{
    size_t z;

    // Now look to see if there is an overlapping rectangle in the inactive list.
    // These occur when frame skip is on and the same lines are covered more than once...
    for (z = 0; z < rectangle_inactive_count; z++) {
        if ((rectangle_inactive[z].x == source->x) &&
            (rectangle_inactive[z].w == source->w)) {
            if ((rectangle_inactive[z].y == source->y) &&
                (rectangle_inactive[z].h == source->h))
                return 1;

            if (((rectangle_inactive[z].y < source->y) &&
                (source->y < (rectangle_inactive[z].y + rectangle_inactive[z].h + 1))) ||
                ((source->y < rectangle_inactive[z].y) &&
                (rectangle_inactive[z].y < (source->y + source->h + 1)))) {
                // rects overlap or touch in the y dimension, merge
                rectangle_inactive[z].h = MAX((rectangle_inactive[z].y + rectangle_inactive[z].h), (source->y + source->h)) -
                                          MIN(rectangle_inactive[z].y, source->y);
                rectangle_inactive[z].y = MIN(rectangle_inactive[z].y, source->y);
                return 1;
            }
        }
        if ((rectangle_inactive[z].y == source->y) && (rectangle_inactive[z].h == source->h)) {

            if (((rectangle_inactive[z].x < source->x) &&
                (source->x < (rectangle_inactive[z].x + rectangle_inactive[z].w + 1))) ||
                ((source->x < rectangle_inactive[z].x) &&
                (rectangle_inactive[z].x < (source->x + source->w + 1)))) {
                // rects overlap or touch in the x dimension, merge
                rectangle_inactive[z].w = MAX((rectangle_inactive[z].x + rectangle_inactive[z].w), (source->x + source->w)) -
                                          MIN(rectangle_inactive[z].x, source->x);
                rectangle_inactive[z].x = MIN(rectangle_inactive[z].x, source->x);
                return 1;
            }
        }
        // Handle overlaps offset by both x and y? how much overlap and hence overdraw can be tolerated?
    }
    return 0;
}


// Move all rectangles not updated on this line to the inactive list
void rectangle_end_line(int y)
{
    size_t i;
    struct rectangle *ptr;

    for (i = 0; i < rectangle_active_count; i++) {

        // Skip if this rectangle was updated this line
        if ((rectangle_active[i].y + rectangle_active[i].h) == (y + 1)) {
            continue;
        }

        if ((settings_current.frame_rate > 1) && compare_and_merge_rectangles(&rectangle_active[i])) {

            // Mark the active rectangle as done
            rectangle_active[i].h = 0;
            continue;
        }

        // We couldn't find a rectangle to extend, so create a new one
        if (++rectangle_inactive_count > rectangle_inactive_allocated) {

            size_t new_alloc;

            new_alloc = rectangle_inactive_allocated ? (2 * rectangle_inactive_allocated) : 8;

            ptr = libspectrum_renew(struct rectangle, rectangle_inactive, new_alloc);

            rectangle_inactive_allocated = new_alloc;
            rectangle_inactive = ptr;
        }

        rectangle_inactive[rectangle_inactive_count - 1] = rectangle_active[i];

        // Mark the active rectangle as done
        rectangle_active[i].h = 0;
    }

    // Compress the list of active rectangles
    for (i = 0, ptr = rectangle_active; i < rectangle_active_count; i++) {
        if (rectangle_active[i].h == 0) {
            continue;
        }
        *ptr = rectangle_active[i]; ptr++;
    }

    rectangle_active_count = ptr - rectangle_active;
}