1 /*
2 (c) Copyright 2001-2009 The world wide DirectFB Open Source Community (directfb.org)
3 (c) Copyright 2000-2004 Convergence (integrated media) GmbH
4
5 All rights reserved.
6
7 Written by Denis Oliver Kropp <dok@directfb.org>,
8 Andreas Hundt <andi@fischlustig.de>,
9 Sven Neumann <neo@directfb.org>,
10 Ville Syrjälä <syrjala@sci.fi> and
11 Claudio Ciccani <klan@users.sf.net>.
12
13 This library is free software; you can redistribute it and/or
14 modify it under the terms of the GNU Lesser General Public
15 License as published by the Free Software Foundation; either
16 version 2 of the License, or (at your option) any later version.
17
18 This library is distributed in the hope that it will be useful,
19 but WITHOUT ANY WARRANTY; without even the implied warranty of
20 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
21 Lesser General Public License for more details.
22
23 You should have received a copy of the GNU Lesser General Public
24 License along with this library; if not, write to the
25 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
26 Boston, MA 02111-1307, USA.
27 */
28
29 #include <config.h>
30
31 #include <string.h>
32
33 #include <sys/types.h>
34 #include <sys/stat.h>
35
36 #include <fcntl.h>
37
38 #include <sys/time.h>
39 #include <time.h>
40
41 #include <direct/debug.h>
42 #include <direct/messages.h>
43 #include <direct/util.h>
44
45 #include <misc/util.h>
46
47
48 D_DEBUG_DOMAIN( DFB_Updates, "DirectFB/Updates", "DirectFB Updates" );
49
50 /**********************************************************************************************************************/
51
DirectFBPixelFormatNames(dfb_pixelformat_names)52 const DirectFBPixelFormatNames( dfb_pixelformat_names )
53
54 /**********************************************************************************************************************/
55
56 bool
57 dfb_region_intersect( DFBRegion *region,
58 int x1, int y1, int x2, int y2 )
59 {
60 if (region->x2 < x1 ||
61 region->y2 < y1 ||
62 region->x1 > x2 ||
63 region->y1 > y2)
64 return false;
65
66 if (region->x1 < x1)
67 region->x1 = x1;
68
69 if (region->y1 < y1)
70 region->y1 = y1;
71
72 if (region->x2 > x2)
73 region->x2 = x2;
74
75 if (region->y2 > y2)
76 region->y2 = y2;
77
78 return true;
79 }
80
81 bool
dfb_region_region_intersect(DFBRegion * region,const DFBRegion * clip)82 dfb_region_region_intersect( DFBRegion *region,
83 const DFBRegion *clip )
84 {
85 if (region->x2 < clip->x1 ||
86 region->y2 < clip->y1 ||
87 region->x1 > clip->x2 ||
88 region->y1 > clip->y2)
89 return false;
90
91 if (region->x1 < clip->x1)
92 region->x1 = clip->x1;
93
94 if (region->y1 < clip->y1)
95 region->y1 = clip->y1;
96
97 if (region->x2 > clip->x2)
98 region->x2 = clip->x2;
99
100 if (region->y2 > clip->y2)
101 region->y2 = clip->y2;
102
103 return true;
104 }
105
106 bool
dfb_region_rectangle_intersect(DFBRegion * region,const DFBRectangle * rect)107 dfb_region_rectangle_intersect( DFBRegion *region,
108 const DFBRectangle *rect )
109 {
110 int x2 = rect->x + rect->w - 1;
111 int y2 = rect->y + rect->h - 1;
112
113 if (region->x2 < rect->x ||
114 region->y2 < rect->y ||
115 region->x1 > x2 ||
116 region->y1 > y2)
117 return false;
118
119 if (region->x1 < rect->x)
120 region->x1 = rect->x;
121
122 if (region->y1 < rect->y)
123 region->y1 = rect->y;
124
125 if (region->x2 > x2)
126 region->x2 = x2;
127
128 if (region->y2 > y2)
129 region->y2 = y2;
130
131 return true;
132 }
133
134 bool
dfb_unsafe_region_intersect(DFBRegion * region,int x1,int y1,int x2,int y2)135 dfb_unsafe_region_intersect( DFBRegion *region,
136 int x1, int y1, int x2, int y2 )
137 {
138 if (region->x1 > region->x2) {
139 int temp = region->x1;
140 region->x1 = region->x2;
141 region->x2 = temp;
142 }
143
144 if (region->y1 > region->y2) {
145 int temp = region->y1;
146 region->y1 = region->y2;
147 region->y2 = temp;
148 }
149
150 return dfb_region_intersect( region, x1, y1, x2, y2 );
151 }
152
153 bool
dfb_unsafe_region_rectangle_intersect(DFBRegion * region,const DFBRectangle * rect)154 dfb_unsafe_region_rectangle_intersect( DFBRegion *region,
155 const DFBRectangle *rect )
156 {
157 if (region->x1 > region->x2) {
158 int temp = region->x1;
159 region->x1 = region->x2;
160 region->x2 = temp;
161 }
162
163 if (region->y1 > region->y2) {
164 int temp = region->y1;
165 region->y1 = region->y2;
166 region->y2 = temp;
167 }
168
169 return dfb_region_rectangle_intersect( region, rect );
170 }
171
172 bool
dfb_rectangle_intersect_by_unsafe_region(DFBRectangle * rectangle,DFBRegion * region)173 dfb_rectangle_intersect_by_unsafe_region( DFBRectangle *rectangle,
174 DFBRegion *region )
175 {
176 /* validate region */
177 if (region->x1 > region->x2) {
178 int temp = region->x1;
179 region->x1 = region->x2;
180 region->x2 = temp;
181 }
182
183 if (region->y1 > region->y2) {
184 int temp = region->y1;
185 region->y1 = region->y2;
186 region->y2 = temp;
187 }
188
189 /* adjust position */
190 if (region->x1 > rectangle->x) {
191 rectangle->w -= region->x1 - rectangle->x;
192 rectangle->x = region->x1;
193 }
194
195 if (region->y1 > rectangle->y) {
196 rectangle->h -= region->y1 - rectangle->y;
197 rectangle->y = region->y1;
198 }
199
200 /* adjust size */
201 if (region->x2 < rectangle->x + rectangle->w - 1)
202 rectangle->w = region->x2 - rectangle->x + 1;
203
204 if (region->y2 < rectangle->y + rectangle->h - 1)
205 rectangle->h = region->y2 - rectangle->y + 1;
206
207 /* set size to zero if there's no intersection */
208 if (rectangle->w <= 0 || rectangle->h <= 0) {
209 rectangle->w = 0;
210 rectangle->h = 0;
211
212 return false;
213 }
214
215 return true;
216 }
217
218 bool
dfb_rectangle_intersect_by_region(DFBRectangle * rectangle,const DFBRegion * region)219 dfb_rectangle_intersect_by_region( DFBRectangle *rectangle,
220 const DFBRegion *region )
221 {
222 /* adjust position */
223 if (region->x1 > rectangle->x) {
224 rectangle->w -= region->x1 - rectangle->x;
225 rectangle->x = region->x1;
226 }
227
228 if (region->y1 > rectangle->y) {
229 rectangle->h -= region->y1 - rectangle->y;
230 rectangle->y = region->y1;
231 }
232
233 /* adjust size */
234 if (region->x2 < rectangle->x + rectangle->w - 1)
235 rectangle->w = region->x2 - rectangle->x + 1;
236
237 if (region->y2 < rectangle->y + rectangle->h - 1)
238 rectangle->h = region->y2 - rectangle->y + 1;
239
240 /* set size to zero if there's no intersection */
241 if (rectangle->w <= 0 || rectangle->h <= 0) {
242 rectangle->w = 0;
243 rectangle->h = 0;
244
245 return false;
246 }
247
248 return true;
249 }
250
dfb_rectangle_intersect(DFBRectangle * rectangle,const DFBRectangle * clip)251 bool dfb_rectangle_intersect( DFBRectangle *rectangle,
252 const DFBRectangle *clip )
253 {
254 DFBRegion region = { clip->x, clip->y,
255 clip->x + clip->w - 1, clip->y + clip->h - 1 };
256
257 /* adjust position */
258 if (region.x1 > rectangle->x) {
259 rectangle->w -= region.x1 - rectangle->x;
260 rectangle->x = region.x1;
261 }
262
263 if (region.y1 > rectangle->y) {
264 rectangle->h -= region.y1 - rectangle->y;
265 rectangle->y = region.y1;
266 }
267
268 /* adjust size */
269 if (region.x2 < rectangle->x + rectangle->w - 1)
270 rectangle->w = region.x2 - rectangle->x + 1;
271
272 if (region.y2 < rectangle->y + rectangle->h - 1)
273 rectangle->h = region.y2 - rectangle->y + 1;
274
275 /* set size to zero if there's no intersection */
276 if (rectangle->w <= 0 || rectangle->h <= 0) {
277 rectangle->w = 0;
278 rectangle->h = 0;
279
280 return false;
281 }
282
283 return true;
284 }
285
dfb_rectangle_union(DFBRectangle * rect1,const DFBRectangle * rect2)286 void dfb_rectangle_union ( DFBRectangle *rect1,
287 const DFBRectangle *rect2 )
288 {
289 if (!rect2->w || !rect2->h)
290 return;
291
292 /* FIXME: OPTIMIZE */
293
294 if (rect1->w) {
295 int temp = MIN (rect1->x, rect2->x);
296 rect1->w = MAX (rect1->x + rect1->w, rect2->x + rect2->w) - temp;
297 rect1->x = temp;
298 }
299 else {
300 rect1->x = rect2->x;
301 rect1->w = rect2->w;
302 }
303
304 if (rect1->h) {
305 int temp = MIN (rect1->y, rect2->y);
306 rect1->h = MAX (rect1->y + rect1->h, rect2->y + rect2->h) - temp;
307 rect1->y = temp;
308 }
309 else {
310 rect1->y = rect2->y;
311 rect1->h = rect2->h;
312 }
313 }
314
dfb_region_from_rotated(DFBRegion * region,const DFBRegion * from,const DFBDimension * size,int rotation)315 void dfb_region_from_rotated( DFBRegion *region,
316 const DFBRegion *from,
317 const DFBDimension *size,
318 int rotation )
319 {
320 D_ASSERT( region != NULL );
321
322 DFB_REGION_ASSERT( from );
323 D_ASSERT( size != NULL );
324 D_ASSERT( size->w > 0 );
325 D_ASSERT( size->h > 0 );
326 D_ASSUME( rotation == 0 || rotation == 90 || rotation == 180 || rotation == 270 );
327
328 switch (rotation) {
329 default:
330 D_BUG( "invalid rotation %d", rotation );
331 case 0:
332 *region = *from;
333 break;
334
335 case 90:
336 region->x1 = from->y1;
337 region->y1 = size->w - from->x2 - 1;
338 region->x2 = from->y2;
339 region->y2 = size->w - from->x1 - 1;
340 break;
341
342 case 180:
343 region->x1 = size->w - from->x2 - 1;
344 region->y1 = size->h - from->y2 - 1;
345 region->x2 = size->w - from->x1 - 1;
346 region->y2 = size->h - from->y1 - 1;
347 break;
348
349 case 270:
350 region->x1 = size->h - from->y2 - 1;
351 region->y1 = from->x1;
352 region->x2 = size->h - from->y1 - 1;
353 region->y2 = from->x2;
354 break;
355 }
356
357 DFB_REGION_ASSERT( region );
358 }
359
dfb_rectangle_from_rotated(DFBRectangle * rectangle,const DFBRectangle * from,const DFBDimension * size,int rotation)360 void dfb_rectangle_from_rotated( DFBRectangle *rectangle,
361 const DFBRectangle *from,
362 const DFBDimension *size,
363 int rotation )
364 {
365 D_ASSERT( rectangle != NULL );
366
367 DFB_RECTANGLE_ASSERT( from );
368 D_ASSERT( size != NULL );
369 D_ASSERT( size->w > 0 );
370 D_ASSERT( size->h > 0 );
371 D_ASSUME( rotation == 0 || rotation == 90 || rotation == 180 || rotation == 270 );
372
373 switch (rotation) {
374 default:
375 D_BUG( "invalid rotation %d", rotation );
376 case 0:
377 *rectangle = *from;
378 break;
379
380 case 90:
381 rectangle->x = from->y;
382 rectangle->y = size->w - from->x - from->w;
383 rectangle->w = from->h;
384 rectangle->h = from->w;
385 break;
386
387 case 180:
388 rectangle->x = size->w - from->x - from->w;
389 rectangle->y = size->h - from->y - from->h;
390 rectangle->w = from->w;
391 rectangle->h = from->h;
392 break;
393
394 case 270:
395 rectangle->x = size->h - from->y - from->h;
396 rectangle->y = from->x;
397 rectangle->w = from->h;
398 rectangle->h = from->w;
399 break;
400 }
401
402 DFB_RECTANGLE_ASSERT( rectangle );
403 }
404
dfb_point_from_rotated_region(DFBPoint * point,const DFBRegion * from,const DFBDimension * size,int rotation)405 void dfb_point_from_rotated_region( DFBPoint *point,
406 const DFBRegion *from,
407 const DFBDimension *size,
408 int rotation )
409 {
410 D_ASSERT( point != NULL );
411
412 DFB_REGION_ASSERT( from );
413 D_ASSERT( size != NULL );
414 D_ASSERT( size->w > 0 );
415 D_ASSERT( size->h > 0 );
416 D_ASSUME( rotation == 0 || rotation == 90 || rotation == 180 || rotation == 270 );
417
418 switch (rotation) {
419 default:
420 D_BUG( "invalid rotation %d", rotation );
421 case 0:
422 point->x = from->x1;
423 point->y = from->y1;
424 break;
425
426 case 90:
427 point->x = from->y1;
428 point->y = size->w - from->x2 - 1;
429 break;
430
431 case 180:
432 point->x = size->w - from->x2 - 1;
433 point->y = size->h - from->y2 - 1;
434 break;
435
436 case 270:
437 point->x = size->h - from->y2 - 1;
438 point->y = from->x1;
439 break;
440 }
441
442 D_ASSERT( point->x >= 0 );
443 D_ASSERT( point->y >= 0 );
444 D_ASSERT( point->x < size->w );
445 D_ASSERT( point->y < size->h );
446 }
447
448 /*
449 * Compute line segment intersection.
450 * Return true if intersection point exists within the given segment.
451 */
dfb_line_segment_intersect(const DFBRegion * line,const DFBRegion * seg,int * x,int * y)452 bool dfb_line_segment_intersect( const DFBRegion *line,
453 const DFBRegion *seg,
454 int *x,
455 int *y )
456 {
457 int x1, x2, x3, x4;
458 int y1, y2, y3, y4;
459 int num, den;
460
461 D_ASSERT( line != NULL );
462 D_ASSERT( seg != NULL );
463
464 x1 = seg->x1; y1 = seg->y1; x2 = seg->y2; y2 = seg->y2;
465 x3 = line->x1; y3 = line->y1; x4 = line->x2; y4 = line->y2;
466
467 num = (x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3);
468 den = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);
469
470 if (!den) /* parallel */
471 return false;
472
473 if (num && ((num < 0) != (den < 0) || abs(num) > abs(den))) /* not within segment */
474 return false;
475
476 if (x)
477 *x = (s64)(x2 - x1) * num / den + x1;
478 if (y)
479 *y = (s64)(y2 - y1) * num / den + y1;
480
481 return true;
482 }
483
484 void
dfb_updates_init(DFBUpdates * updates,DFBRegion * regions,int max_regions)485 dfb_updates_init( DFBUpdates *updates,
486 DFBRegion *regions,
487 int max_regions )
488 {
489 D_ASSERT( updates != NULL );
490 D_ASSERT( regions != NULL );
491 D_ASSERT( max_regions > 0 );
492
493 updates->regions = regions;
494 updates->max_regions = max_regions;
495 updates->num_regions = 0;
496
497 D_MAGIC_SET( updates, DFBUpdates );
498 }
499
500 void
dfb_updates_add(DFBUpdates * updates,const DFBRegion * region)501 dfb_updates_add( DFBUpdates *updates,
502 const DFBRegion *region )
503 {
504 int i;
505
506 D_MAGIC_ASSERT( updates, DFBUpdates );
507 DFB_REGION_ASSERT( region );
508 D_ASSERT( updates->regions != NULL );
509 D_ASSERT( updates->num_regions >= 0 );
510 D_ASSERT( updates->num_regions <= updates->max_regions );
511
512 D_DEBUG_AT( DFB_Updates, "%s( %p, %4d,%4d-%4dx%4d )\n", __FUNCTION__, (void*)updates,
513 DFB_RECTANGLE_VALS_FROM_REGION(region) );
514
515 if (updates->num_regions == 0) {
516 D_DEBUG_AT( DFB_Updates, " -> added as first\n" );
517
518 updates->regions[0] = updates->bounding = *region;
519 updates->num_regions = 1;
520
521 return;
522 }
523
524 for (i=0; i<updates->num_regions; i++) {
525 if (dfb_region_region_extends( &updates->regions[i], region ) ||
526 dfb_region_region_intersects( &updates->regions[i], region ))
527 {
528 D_DEBUG_AT( DFB_Updates, " -> combined with [%d] %4d,%4d-%4dx%4d\n", i,
529 DFB_RECTANGLE_VALS_FROM_REGION(&updates->regions[i]) );
530
531 dfb_region_region_union( &updates->regions[i], region );
532
533 dfb_region_region_union( &updates->bounding, region );
534
535 D_DEBUG_AT( DFB_Updates, " -> resulting in [%d] %4d,%4d-%4dx%4d\n", i,
536 DFB_RECTANGLE_VALS_FROM_REGION(&updates->regions[i]) );
537
538 return;
539 }
540 }
541
542 if (updates->num_regions == updates->max_regions) {
543 dfb_region_region_union( &updates->bounding, region );
544
545 updates->regions[0] = updates->bounding;
546 updates->num_regions = 1;
547
548 D_DEBUG_AT( DFB_Updates, " -> collapsing to [0] %4d,%4d-%4dx%4d\n",
549 DFB_RECTANGLE_VALS_FROM_REGION(&updates->regions[0]) );
550 }
551 else {
552 updates->regions[updates->num_regions++] = *region;
553
554 dfb_region_region_union( &updates->bounding, region );
555
556 D_DEBUG_AT( DFB_Updates, " -> added as [%d] %4d,%4d-%4dx%4d\n", updates->num_regions - 1,
557 DFB_RECTANGLE_VALS_FROM_REGION(&updates->regions[updates->num_regions - 1]) );
558 }
559 }
560
561 void
dfb_updates_stat(DFBUpdates * updates,int * ret_total,int * ret_bounding)562 dfb_updates_stat( DFBUpdates *updates,
563 int *ret_total,
564 int *ret_bounding )
565 {
566 int i;
567
568 D_MAGIC_ASSERT( updates, DFBUpdates );
569 D_ASSERT( updates->regions != NULL );
570 D_ASSERT( updates->num_regions >= 0 );
571 D_ASSERT( updates->num_regions <= updates->max_regions );
572
573 if (updates->num_regions == 0) {
574 if (ret_total)
575 *ret_total = 0;
576
577 if (ret_bounding)
578 *ret_bounding = 0;
579
580 return;
581 }
582
583 if (ret_total) {
584 int total = 0;
585
586 for (i=0; i<updates->num_regions; i++) {
587 const DFBRegion *r = &updates->regions[i];
588
589 total += (r->x2 - r->x1 + 1) * (r->y2 - r->y1 + 1);
590 }
591
592 *ret_total = total;
593 }
594
595 if (ret_bounding)
596 *ret_bounding = (updates->bounding.x2 - updates->bounding.x1 + 1) *
597 (updates->bounding.y2 - updates->bounding.y1 + 1);
598 }
599
600 void
dfb_updates_get_rectangles(DFBUpdates * updates,DFBRectangle * ret_rects,int * ret_num)601 dfb_updates_get_rectangles( DFBUpdates *updates,
602 DFBRectangle *ret_rects,
603 int *ret_num )
604 {
605 D_MAGIC_ASSERT( updates, DFBUpdates );
606 D_ASSERT( updates->regions != NULL );
607 D_ASSERT( updates->num_regions >= 0 );
608 D_ASSERT( updates->num_regions <= updates->max_regions );
609
610 switch (updates->num_regions) {
611 case 0:
612 *ret_num = 0;
613 break;
614
615 default: {
616 int n, d, total, bounding;
617
618 dfb_updates_stat( updates, &total, &bounding );
619
620 n = updates->max_regions - updates->num_regions + 1;
621 d = n + 1;
622
623 /* Try to optimize updates. Use individual regions only if not too much overhead. */
624 if (total < bounding * n / d) {
625 *ret_num = updates->num_regions;
626
627 for (n=0; n<updates->num_regions; n++)
628 ret_rects[n] = DFB_RECTANGLE_INIT_FROM_REGION( &updates->regions[n] );
629
630 break;
631 }
632 }
633 /* fall through */
634
635 case 1:
636 *ret_num = 1;
637 *ret_rects = DFB_RECTANGLE_INIT_FROM_REGION( &updates->bounding );
638 break;
639 }
640 }
641