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