source: libcaca/trunk/caca/dirty.c @ 4328

Last change on this file since 4328 was 3583, checked in by Sam Hocevar, 11 years ago

Allow to temporarily disable dirty rectangle handling. This allows for huge
speedups when the calling application knows the dirty rectangle covered by
a complex operation.

  • Property svn:keywords set to Id
File size: 11.5 KB
RevLine 
[3470]1/*
2 *  libcaca       Colour ASCII-Art library
3 *  Copyright (c) 2002-2009 Sam Hocevar <sam@hocevar.net>
4 *                All Rights Reserved
5 *
6 *  $Id: dirty.c 3583 2009-07-26 19:17:35Z sam $
7 *
8 *  This library is free software. It comes without any warranty, to
9 *  the extent permitted by applicable law. You can redistribute it
10 *  and/or modify it under the terms of the Do What The Fuck You Want
11 *  To Public License, Version 2, as published by Sam Hocevar. See
12 *  http://sam.zoy.org/wtfpl/COPYING for more details.
13 */
14
15/*
16 *  This file contains the dirty rectangle handling functions.
[3568]17 *
18 *
19 *  About dirty rectangles:
20 *
21 *  * Dirty rectangles MUST NOT be larger than the canvas. If the user
22 *  provides a large rectangle through caca_add_dirty_rect(), or if the
23 *  canvas changes size to become smaller, all dirty rectangles MUST
24 *  immediately be clipped to the canvas size.
[3470]25 */
26
27#include "config.h"
28
29#if !defined(__KERNEL__)
30#   include <stdio.h>
[3580]31#   include <string.h>
[3470]32#endif
33
34#include "caca.h"
35#include "caca_internals.h"
36
[3580]37static void merge_new_rect(caca_canvas_t *cv, int n);
38
[3583]39/** \brief Disable dirty rectangles.
40 *
41 *  Disable dirty rectangle handling for all \e libcaca graphic calls. This
42 *  is handy when the calling application needs to do slow operations within
43 *  a known area. Just call caca_add_dirty_rect() afterwards.
44 *
45 *  This function is recursive. Dirty rectangles are only reenabled when
46 *  caca_enable_dirty_rect() is called as many times.
47 *
48 *  This function never fails.
49 *
50 *  \param cv A libcaca canvas.
51 *  \return This function always returns 0.
52 */
53int caca_disable_dirty_rect(caca_canvas_t *cv)
54{
55    cv->dirty_disabled++;
56
57    return 0;
58}
59
60/** \brief Enable dirty rectangles.
61 *
62 *  This function can only be called after caca_disable_dirty_rect() was
63 *  called.
64 *
65 *  If an error occurs, -1 is returned and \b errno is set accordingly:
66 *  - \c EINVAL Dirty rectangles were not disabled.
67 *
68 *  \param cv A libcaca canvas.
69 *  \return 0 in case of success, -1 if an error occurred.
70 */
71int caca_enable_dirty_rect(caca_canvas_t *cv)
72{
73    if(cv->dirty_disabled <= 0)
74    {
75        seterrno(EINVAL);
76        return -1;
77    }
78
79    cv->dirty_disabled--;
80
81    return 0;
82}
83
[3470]84/** \brief Get the number of dirty rectangles in the canvas.
85 *
86 *  Get the number of dirty rectangles in a canvas. Dirty rectangles are
87 *  areas that contain cells that have changed since the last reset.
88 *
89 *  The dirty rectangles are used internally by display drivers to optimise
90 *  rendering by avoiding to redraw the whole screen. Once the display driver
91 *  has rendered the canvas, it resets the dirty rectangle list.
92 *
93 *  Dirty rectangles are guaranteed not to overlap.
94 *
95 *  This function never fails.
96 *
97 *  \param cv A libcaca canvas.
98 *  \return The number of dirty rectangles in the given canvas.
99 */
[3494]100int caca_get_dirty_rect_count(caca_canvas_t *cv)
[3470]101{
[3471]102    return cv->ndirty;
[3470]103}
104
105/** \brief Get a canvas's dirty rectangle.
106 *
107 *  Get the canvas's given dirty rectangle coordinates. The index must be
[3494]108 *  within the dirty rectangle count. See caca_get_dirty_rect_count()
[3470]109 *  for how to compute this count.
110 *
111 *  If an error occurs, no coordinates are written in the pointer arguments,
112 *  -1 is returned and \b errno is set accordingly:
113 *  - \c EINVAL Specified rectangle index is out of bounds.
114 *
115 *  \param cv A libcaca canvas.
[3484]116 *  \param r The requested rectangle index.
[3494]117 *  \param x A pointer to an integer where the leftmost edge of the
118 *           dirty rectangle will be stored.
119 *  \param y A pointer to an integer where the topmost edge of the
120 *           dirty rectangle will be stored.
121 *  \param width A pointer to an integer where the width of the
122 *               dirty rectangle will be stored.
123 *  \param height A pointer to an integer where the height of the
124 *                dirty rectangle will be stored.
[3470]125 *  \return 0 in case of success, -1 if an error occurred.
126 */
[3494]127int caca_get_dirty_rect(caca_canvas_t *cv, int r,
128                        int *x, int *y, int *width, int *height)
[3470]129{
[3484]130    if(r < 0 || r >= cv->ndirty)
[3470]131    {
132        seterrno(EINVAL);
133        return -1;
134    }
135
[3568]136    *x = cv->dirty[r].xmin;
137    *y = cv->dirty[r].ymin;
138    *width = cv->dirty[r].xmax - cv->dirty[r].xmin + 1;
139    *height = cv->dirty[r].ymax - cv->dirty[r].ymin + 1;
[3470]140
[3580]141    debug("dirty #%i: %ix%i at (%i,%i)", r, *width, *height, *x, *y);
[3470]142
143    return 0;
144}
145
146/** \brief Add an area to the canvas's dirty rectangle list.
147 *
148 *  Add an invalidating zone to the canvas's dirty rectangle list. For more
[3494]149 *  information about the dirty rectangles, see caca_get_dirty_rect().
[3470]150 *
151 *  This function may be useful to force refresh of a given zone of the
152 *  canvas even if the dirty rectangle tracking indicates that it is
153 *  unchanged. This may happen if the canvas contents were somewhat
154 *  directly modified.
155 *
156 *  If an error occurs, -1 is returned and \b errno is set accordingly:
157 *  - \c EINVAL Specified rectangle coordinates are out of bounds.
158 *
159 *  \param cv A libcaca canvas.
[3494]160 *  \param x The leftmost edge of the additional dirty rectangle.
161 *  \param y The topmost edge of the additional dirty rectangle.
162 *  \param width The width of the additional dirty rectangle.
163 *  \param height The height of the additional dirty rectangle.
[3470]164 *  \return 0 in case of success, -1 if an error occurred.
165 */
[3568]166int caca_add_dirty_rect(caca_canvas_t *cv, int x, int y, int width, int height)
[3470]167{
[3580]168    debug("new dirty: %ix%i at (%i,%i)", width, height, x, y);
[3568]169
170    /* Clip arguments to canvas */
171    if(x < 0) { width += x; x = 0; }
172
173    if(x + width > cv->width)
174        width = cv->width - x;
175
176    if(y < 0) { height += y; y = 0; }
177
178    if(y + height > cv->height)
179        height = cv->height - y;
180
181    /* Ignore empty and out-of-canvas rectangles */
182    if(width <= 0 || height <= 0)
[3470]183    {
184        seterrno(EINVAL);
185        return -1;
186    }
187
[3580]188    /* Add the new rectangle to the list; it works even if cv->ndirty
189     * is MAX_DIRTY_COUNT because there's an extra cell in the array. */
190    cv->dirty[cv->ndirty].xmin = x;
191    cv->dirty[cv->ndirty].ymin = y;
192    cv->dirty[cv->ndirty].xmax = x + width - 1;
193    cv->dirty[cv->ndirty].ymax = y + height - 1;
194    cv->ndirty++;
[3470]195
[3580]196    /* Try to merge the new rectangle with existing ones. This also ensures
197     * that cv->ndirty is brought back below MAX_DIRTY_COUNT. */
198    merge_new_rect(cv, cv->ndirty - 1);
199
[3470]200    return 0;
201}
202
203/** \brief Remove an area from the dirty rectangle list.
204 *
205 *  Mark a cell area in the canvas as not dirty. For more information about
[3494]206 *  the dirty rectangles, see caca_get_dirty_rect().
[3470]207 *
208 *  Values such that \b xmin > \b xmax or \b ymin > \b ymax indicate that
209 *  the dirty rectangle is empty. They will be silently ignored.
210 *
211 *  If an error occurs, -1 is returned and \b errno is set accordingly:
212 *  - \c EINVAL Specified rectangle coordinates are out of bounds.
213 *
214 *  \param cv A libcaca canvas.
[3494]215 *  \param x The leftmost edge of the clean rectangle.
216 *  \param y The topmost edge of the clean rectangle.
217 *  \param width The width of the clean rectangle.
218 *  \param height The height of the clean rectangle.
[3470]219 *  \return 0 in case of success, -1 if an error occurred.
220 */
[3494]221int caca_remove_dirty_rect(caca_canvas_t *cv, int x, int y,
222                           int width, int height)
[3470]223{
[3568]224    /* Clip arguments to canvas size */
225    if(x < 0) { width += x; x = 0; }
226
227    if(x + width > cv->width)
228        width = cv->width - x;
229
230    if(y < 0) { height += y; y = 0; }
231
232    if(y + height > cv->height)
233        height = cv->height - y;
234
235    /* Ignore empty and out-of-canvas rectangles */
236    if(width <= 0 || height <= 0)
[3470]237    {
238        seterrno(EINVAL);
239        return -1;
240    }
241
242    /* FIXME: implement this function. It's OK to have it do nothing,
243     * since we take a conservative approach in dirty rectangle handling,
244     * but we ought to help the rendering eventually. */
245
246    return 0;
247}
248
249/** \brief Clear a canvas's dirty rectangle list.
250 *
251 *  Empty the canvas's dirty rectangle list.
252 *
253 *  This function never fails.
254 *
255 *  \param cv A libcaca canvas.
256 *  \return This function always returns 0.
257 */
[3494]258int caca_clear_dirty_rect_list(caca_canvas_t *cv)
[3470]259{
[3471]260    cv->ndirty = 0;
[3470]261
262    return 0;
263}
264
[3568]265/*
266 * XXX: the following functions are local.
267 */
268
[3580]269static inline int int_min(int a, int b) { return a < b ? a : b; }
270static inline int int_max(int a, int b) { return a > b ? a : b; }
271
272/* Merge a newly added rectangle, if necessary. */
273static void merge_new_rect(caca_canvas_t *cv, int n)
274{
275    int wasted[MAX_DIRTY_COUNT + 1];
276    int i, sn, best, best_score;
277
278    best = -1;
279    best_score = cv->width * cv->height;
280
281    sn = (cv->dirty[n].xmax - cv->dirty[n].xmin + 1)
282           * (cv->dirty[n].ymax - cv->dirty[n].ymin + 1);
283
284    /* Check whether the new rectangle can be merged with an existing one. */
285    for(i = 0; i < cv->ndirty; i++)
286    {
287        int si, sf, xmin, ymin, xmax, ymax;
288
289        if(i == n)
290            continue;
291
292        xmin = int_min(cv->dirty[i].xmin, cv->dirty[n].xmin);
293        ymin = int_min(cv->dirty[i].ymin, cv->dirty[n].ymin);
294        xmax = int_max(cv->dirty[i].xmax, cv->dirty[n].xmax);
295        ymax = int_max(cv->dirty[i].ymax, cv->dirty[n].ymax);
296
297        sf = (xmax - xmin + 1) * (ymax - ymin + 1);
298
299        /* Shortcut: if the current rectangle is inside the new rectangle,
300         * we remove the current rectangle and continue trying merges. */
301        if(sf == sn)
302        {
303            memmove(&cv->dirty[i], &cv->dirty[i + 1],
304                    (cv->ndirty - i) * sizeof(cv->dirty[0]));
305            cv->ndirty--;
306
307            if(i < n)
308                n--;
309            else
310                i--;
311
312            continue;
313        }
314
315        si = (cv->dirty[i].xmax - cv->dirty[i].xmin + 1)
316               * (cv->dirty[i].ymax - cv->dirty[i].ymin + 1);
317
318        /* Shortcut: if the new rectangle is inside the current rectangle,
319         * we get rid of the new rectangle and bail out. */
320        if(sf == si)
321        {
322            cv->ndirty--;
323            memmove(&cv->dirty[n], &cv->dirty[n + 1],
324                    (cv->ndirty - n) * sizeof(cv->dirty[0]));
325            return;
326        }
327
328        /* We store approximately how many bytes were wasted. FIXME: this is
329         * not an exact computation, we need to be more precise. */
330        wasted[i] = sf - si - sn;
331
332        if(wasted[i] < best_score)
333        {
334             best = i;
335             best_score = wasted[i];
336        }
337    }
338
339    /* FIXME: we only try to merge the current rectangle, ignoring
340     * potentially better merges. */
341
342    /* If no acceptable score was found and the dirty rectangle list is
343     * not full, we bail out. */
344    if(best_score > 0 && cv->ndirty < MAX_DIRTY_COUNT)
345        return;
346
347    /* Otherwise, merge the rectangle with the best candidate */
348    cv->dirty[best].xmin = int_min(cv->dirty[best].xmin, cv->dirty[n].xmin);
349    cv->dirty[best].ymin = int_min(cv->dirty[best].ymin, cv->dirty[n].ymin);
350    cv->dirty[best].xmax = int_max(cv->dirty[best].xmax, cv->dirty[n].xmax);
351    cv->dirty[best].ymax = int_max(cv->dirty[best].ymax, cv->dirty[n].ymax);
352
353    memmove(&cv->dirty[n], &cv->dirty[n + 1],
354            (cv->ndirty - n) * sizeof(cv->dirty[0]));
355    cv->ndirty--;
356
357    if(best < n)
358        merge_new_rect(cv, best);
359    else
360        merge_new_rect(cv, best - 1);
361}
362
[3568]363/* Clip all dirty rectangles in case they're larger than the canvas */
364void _caca_clip_dirty_rect_list(caca_canvas_t *cv)
365{
366    int i;
367
368    for(i = 0; i < cv->ndirty; i++)
369    {
370        if(cv->dirty[i].xmin < 0)
371            cv->dirty[i].xmin = 0;
372
373        if(cv->dirty[i].ymin < 0)
374            cv->dirty[i].ymin = 0;
375
376        if(cv->dirty[i].xmax >= cv->width)
377            cv->dirty[i].xmax = cv->width - 1;
378
379        if(cv->dirty[i].ymax >= cv->height)
380            cv->dirty[i].ymax = cv->height - 1;
381    }
382}
383
Note: See TracBrowser for help on using the repository browser.