1 /**
2 * FreeRDP: A Remote Desktop Protocol Implementation
3 *
4 * Copyright 2014 Thincast Technologies GmbH
5 * Copyright 2014 Hardening <contact@hardening-consulting.com>
6 * Copyright 2017 Armin Novak <armin.novak@thincast.com>
7 * Copyright 2017 Thincast Technologies GmbH
8 *
9 * Licensed under the Apache License, Version 2.0 (the "License");
10 * you may not use this file except in compliance with the License.
11 * You may obtain a copy of the License at
12 *
13 * http://www.apache.org/licenses/LICENSE-2.0
14 *
15 * Unless required by applicable law or agreed to in writing, software
16 * distributed under the License is distributed on an "AS IS" BASIS,
17 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
18 * See the License for the specific language governing permissions and
19 * limitations under the License.
20 */
21
22 #include <assert.h>
23 #include <winpr/memory.h>
24 #include <freerdp/log.h>
25 #include <freerdp/codec/region.h>
26
27 #define TAG FREERDP_TAG("codec")
28
29 /*
30 * The functions in this file implement the Region abstraction largely inspired from
31 * pixman library. The following comment is taken from the pixman code.
32 *
33 * A Region is simply a set of disjoint(non-overlapping) rectangles, plus an
34 * "extent" rectangle which is the smallest single rectangle that contains all
35 * the non-overlapping rectangles.
36 *
37 * A Region is implemented as a "y-x-banded" array of rectangles. This array
38 * imposes two degrees of order. First, all rectangles are sorted by top side
39 * y coordinate first (y1), and then by left side x coordinate (x1).
40 *
41 * Furthermore, the rectangles are grouped into "bands". Each rectangle in a
42 * band has the same top y coordinate (y1), and each has the same bottom y
43 * coordinate (y2). Thus all rectangles in a band differ only in their left
44 * and right side (x1 and x2). Bands are implicit in the array of rectangles:
45 * there is no separate list of band start pointers.
46 *
47 * The y-x band representation does not minimize rectangles. In particular,
48 * if a rectangle vertically crosses a band (the rectangle has scanlines in
49 * the y1 to y2 area spanned by the band), then the rectangle may be broken
50 * down into two or more smaller rectangles stacked one atop the other.
51 *
52 * ----------- -----------
53 * | | | | band 0
54 * | | -------- ----------- --------
55 * | | | | in y-x banded | | | | band 1
56 * | | | | form is | | | |
57 * ----------- | | ----------- --------
58 * | | | | band 2
59 * -------- --------
60 *
61 * An added constraint on the rectangles is that they must cover as much
62 * horizontal area as possible: no two rectangles within a band are allowed
63 * to touch.
64 *
65 * Whenever possible, bands will be merged together to cover a greater vertical
66 * distance (and thus reduce the number of rectangles). Two bands can be merged
67 * only if the bottom of one touches the top of the other and they have
68 * rectangles in the same places (of the same width, of course).
69 */
70
71 struct _REGION16_DATA
72 {
73 long size;
74 long nbRects;
75 };
76
77 static REGION16_DATA empty_region = { 0, 0 };
78
region16_init(REGION16 * region)79 void region16_init(REGION16* region)
80 {
81 assert(region);
82 ZeroMemory(region, sizeof(REGION16));
83 region->data = &empty_region;
84 }
85
region16_n_rects(const REGION16 * region)86 int region16_n_rects(const REGION16* region)
87 {
88 assert(region);
89 assert(region->data);
90 return region->data->nbRects;
91 }
92
region16_rects(const REGION16 * region,UINT32 * nbRects)93 const RECTANGLE_16* region16_rects(const REGION16* region, UINT32* nbRects)
94 {
95 REGION16_DATA* data;
96
97 if (nbRects)
98 *nbRects = 0;
99
100 if (!region)
101 return NULL;
102
103 data = region->data;
104
105 if (!data)
106 return NULL;
107
108 if (nbRects)
109 *nbRects = data->nbRects;
110
111 return (RECTANGLE_16*)(data + 1);
112 }
113
region16_rects_noconst(REGION16 * region)114 static INLINE RECTANGLE_16* region16_rects_noconst(REGION16* region)
115 {
116 REGION16_DATA* data;
117 data = region->data;
118
119 if (!data)
120 return NULL;
121
122 return (RECTANGLE_16*)(&data[1]);
123 }
124
region16_extents(const REGION16 * region)125 const RECTANGLE_16* region16_extents(const REGION16* region)
126 {
127 if (!region)
128 return NULL;
129
130 return ®ion->extents;
131 }
132
region16_extents_noconst(REGION16 * region)133 static RECTANGLE_16* region16_extents_noconst(REGION16* region)
134 {
135 if (!region)
136 return NULL;
137
138 return ®ion->extents;
139 }
140
rectangle_is_empty(const RECTANGLE_16 * rect)141 BOOL rectangle_is_empty(const RECTANGLE_16* rect)
142 {
143 /* A rectangle with width = 0 or height = 0 should be regarded
144 * as empty.
145 */
146 return ((rect->left == rect->right) || (rect->top == rect->bottom)) ? TRUE : FALSE;
147 }
148
region16_is_empty(const REGION16 * region)149 BOOL region16_is_empty(const REGION16* region)
150 {
151 assert(region);
152 assert(region->data);
153 return (region->data->nbRects == 0);
154 }
155
rectangles_equal(const RECTANGLE_16 * r1,const RECTANGLE_16 * r2)156 BOOL rectangles_equal(const RECTANGLE_16* r1, const RECTANGLE_16* r2)
157 {
158 return ((r1->left == r2->left) && (r1->top == r2->top) && (r1->right == r2->right) &&
159 (r1->bottom == r2->bottom))
160 ? TRUE
161 : FALSE;
162 }
163
rectangles_intersects(const RECTANGLE_16 * r1,const RECTANGLE_16 * r2)164 BOOL rectangles_intersects(const RECTANGLE_16* r1, const RECTANGLE_16* r2)
165 {
166 RECTANGLE_16 tmp;
167 return rectangles_intersection(r1, r2, &tmp);
168 }
169
rectangles_intersection(const RECTANGLE_16 * r1,const RECTANGLE_16 * r2,RECTANGLE_16 * dst)170 BOOL rectangles_intersection(const RECTANGLE_16* r1, const RECTANGLE_16* r2, RECTANGLE_16* dst)
171 {
172 dst->left = MAX(r1->left, r2->left);
173 dst->right = MIN(r1->right, r2->right);
174 dst->top = MAX(r1->top, r2->top);
175 dst->bottom = MIN(r1->bottom, r2->bottom);
176 return (dst->left < dst->right) && (dst->top < dst->bottom);
177 }
178
region16_clear(REGION16 * region)179 void region16_clear(REGION16* region)
180 {
181 assert(region);
182 assert(region->data);
183
184 if ((region->data->size > 0) && (region->data != &empty_region))
185 free(region->data);
186
187 region->data = &empty_region;
188 ZeroMemory(®ion->extents, sizeof(region->extents));
189 }
190
allocateRegion(long nbItems)191 static INLINE REGION16_DATA* allocateRegion(long nbItems)
192 {
193 long allocSize = sizeof(REGION16_DATA) + (nbItems * sizeof(RECTANGLE_16));
194 REGION16_DATA* ret = (REGION16_DATA*)malloc(allocSize);
195
196 if (!ret)
197 return ret;
198
199 ret->size = allocSize;
200 ret->nbRects = nbItems;
201 return ret;
202 }
203
region16_copy(REGION16 * dst,const REGION16 * src)204 BOOL region16_copy(REGION16* dst, const REGION16* src)
205 {
206 assert(dst);
207 assert(dst->data);
208 assert(src);
209 assert(src->data);
210
211 if (dst == src)
212 return TRUE;
213
214 dst->extents = src->extents;
215
216 if ((dst->data->size > 0) && (dst->data != &empty_region))
217 free(dst->data);
218
219 if (src->data->size == 0)
220 dst->data = &empty_region;
221 else
222 {
223 dst->data = allocateRegion(src->data->nbRects);
224
225 if (!dst->data)
226 return FALSE;
227
228 CopyMemory(dst->data, src->data, src->data->size);
229 }
230
231 return TRUE;
232 }
233
region16_print(const REGION16 * region)234 void region16_print(const REGION16* region)
235 {
236 const RECTANGLE_16* rects;
237 UINT32 nbRects, i;
238 int currentBandY = -1;
239 rects = region16_rects(region, &nbRects);
240 WLog_DBG(TAG, "nrects=%" PRIu32 "", nbRects);
241
242 for (i = 0; i < nbRects; i++, rects++)
243 {
244 if (rects->top != currentBandY)
245 {
246 currentBandY = rects->top;
247 WLog_DBG(TAG, "band %d: ", currentBandY);
248 }
249
250 WLog_DBG(TAG, "(%" PRIu16 ",%" PRIu16 "-%" PRIu16 ",%" PRIu16 ")", rects->left, rects->top,
251 rects->right, rects->bottom);
252 }
253 }
254
region16_copy_band_with_union(RECTANGLE_16 * dst,const RECTANGLE_16 * src,const RECTANGLE_16 * end,UINT16 newTop,UINT16 newBottom,const RECTANGLE_16 * unionRect,UINT32 * dstCounter,const RECTANGLE_16 ** srcPtr,RECTANGLE_16 ** dstPtr)255 static void region16_copy_band_with_union(RECTANGLE_16* dst, const RECTANGLE_16* src,
256 const RECTANGLE_16* end, UINT16 newTop, UINT16 newBottom,
257 const RECTANGLE_16* unionRect, UINT32* dstCounter,
258 const RECTANGLE_16** srcPtr, RECTANGLE_16** dstPtr)
259 {
260 UINT16 refY = src->top;
261 const RECTANGLE_16 *startOverlap, *endOverlap;
262
263 /* merges a band with the given rect
264 * Input:
265 * unionRect
266 * | |
267 * | |
268 * ==============+===============+================================
269 * |Item1| |Item2| |Item3| |Item4| |Item5| Band
270 * ==============+===============+================================
271 * before | overlap | after
272 *
273 * Resulting band:
274 * +-----+ +----------------------+ +-----+
275 * |Item1| | Item2 | |Item3|
276 * +-----+ +----------------------+ +-----+
277 *
278 * We first copy as-is items that are before Item2, the first overlapping
279 * item.
280 * Then we find the last one that overlap unionRect to agregate Item2, Item3
281 * and Item4 to create Item2.
282 * Finally Item5 is copied as Item3.
283 *
284 * When no unionRect is provided, we skip the two first steps to just copy items
285 */
286
287 if (unionRect)
288 {
289 /* items before unionRect */
290 while ((src < end) && (src->top == refY) && (src->right < unionRect->left))
291 {
292 dst->top = newTop;
293 dst->bottom = newBottom;
294 dst->right = src->right;
295 dst->left = src->left;
296 src++;
297 dst++;
298 *dstCounter += 1;
299 }
300
301 /* treat items overlapping with unionRect */
302 startOverlap = unionRect;
303 endOverlap = unionRect;
304
305 if ((src < end) && (src->top == refY) && (src->left < unionRect->left))
306 startOverlap = src;
307
308 while ((src < end) && (src->top == refY) && (src->right < unionRect->right))
309 {
310 src++;
311 }
312
313 if ((src < end) && (src->top == refY) && (src->left < unionRect->right))
314 {
315 endOverlap = src;
316 src++;
317 }
318
319 dst->bottom = newBottom;
320 dst->top = newTop;
321 dst->left = startOverlap->left;
322 dst->right = endOverlap->right;
323 dst++;
324 *dstCounter += 1;
325 }
326
327 /* treat remaining items on the same band */
328 while ((src < end) && (src->top == refY))
329 {
330 dst->top = newTop;
331 dst->bottom = newBottom;
332 dst->right = src->right;
333 dst->left = src->left;
334 src++;
335 dst++;
336 *dstCounter += 1;
337 }
338
339 if (srcPtr)
340 *srcPtr = src;
341
342 *dstPtr = dst;
343 }
344
next_band(RECTANGLE_16 * band1,RECTANGLE_16 * endPtr,int * nbItems)345 static RECTANGLE_16* next_band(RECTANGLE_16* band1, RECTANGLE_16* endPtr, int* nbItems)
346 {
347 UINT16 refY = band1->top;
348 *nbItems = 0;
349
350 while ((band1 < endPtr) && (band1->top == refY))
351 {
352 band1++;
353 *nbItems += 1;
354 }
355
356 return band1;
357 }
358
band_match(const RECTANGLE_16 * band1,const RECTANGLE_16 * band2,RECTANGLE_16 * endPtr)359 static BOOL band_match(const RECTANGLE_16* band1, const RECTANGLE_16* band2, RECTANGLE_16* endPtr)
360 {
361 int refBand2 = band2->top;
362 const RECTANGLE_16* band2Start = band2;
363
364 while ((band1 < band2Start) && (band2 < endPtr) && (band2->top == refBand2))
365 {
366 if ((band1->left != band2->left) || (band1->right != band2->right))
367 return FALSE;
368
369 band1++;
370 band2++;
371 }
372
373 if (band1 != band2Start)
374 return FALSE;
375
376 return (band2 == endPtr) || (band2->top != refBand2);
377 }
378
379 /** compute if the rectangle is fully included in the band
380 * @param band a pointer on the beginning of the band
381 * @param endPtr end of the region
382 * @param rect the rectangle to test
383 * @return if rect is fully included in an item of the band
384 */
rectangle_contained_in_band(const RECTANGLE_16 * band,const RECTANGLE_16 * endPtr,const RECTANGLE_16 * rect)385 static BOOL rectangle_contained_in_band(const RECTANGLE_16* band, const RECTANGLE_16* endPtr,
386 const RECTANGLE_16* rect)
387 {
388 UINT16 refY = band->top;
389
390 if ((band->top > rect->top) || (rect->bottom > band->bottom))
391 return FALSE;
392
393 /* note: as the band is sorted from left to right, once we've seen an item
394 * that is after rect->left we're sure that the result is False.
395 */
396 while ((band < endPtr) && (band->top == refY) && (band->left <= rect->left))
397 {
398 if (rect->right <= band->right)
399 return TRUE;
400
401 band++;
402 }
403
404 return FALSE;
405 }
406
region16_simplify_bands(REGION16 * region)407 static BOOL region16_simplify_bands(REGION16* region)
408 {
409 /** Simplify consecutive bands that touch and have the same items
410 *
411 * ==================== ====================
412 * | 1 | | 2 | | | | |
413 * ==================== | | | |
414 * | 1 | | 2 | ====> | 1 | | 2 |
415 * ==================== | | | |
416 * | 1 | | 2 | | | | |
417 * ==================== ====================
418 *
419 */
420 RECTANGLE_16 *band1, *band2, *endPtr, *endBand, *tmp;
421 int nbRects, finalNbRects;
422 int bandItems, toMove;
423 finalNbRects = nbRects = region16_n_rects(region);
424
425 if (nbRects < 2)
426 return TRUE;
427
428 band1 = region16_rects_noconst(region);
429 endPtr = band1 + nbRects;
430
431 do
432 {
433 band2 = next_band(band1, endPtr, &bandItems);
434
435 if (band2 == endPtr)
436 break;
437
438 if ((band1->bottom == band2->top) && band_match(band1, band2, endPtr))
439 {
440 /* adjust the bottom of band1 items */
441 tmp = band1;
442
443 while (tmp < band2)
444 {
445 tmp->bottom = band2->bottom;
446 tmp++;
447 }
448
449 /* override band2, we don't move band1 pointer as the band after band2
450 * may be merged too */
451 endBand = band2 + bandItems;
452 toMove = (endPtr - endBand) * sizeof(RECTANGLE_16);
453
454 if (toMove)
455 MoveMemory(band2, endBand, toMove);
456
457 finalNbRects -= bandItems;
458 endPtr -= bandItems;
459 }
460 else
461 {
462 band1 = band2;
463 }
464 } while (TRUE);
465
466 if (finalNbRects != nbRects)
467 {
468 REGION16_DATA* data;
469 size_t allocSize = sizeof(REGION16_DATA) + (finalNbRects * sizeof(RECTANGLE_16));
470 data = realloc(region->data, allocSize);
471 if (!data)
472 free(region->data);
473 region->data = data;
474
475 if (!region->data)
476 {
477 region->data = &empty_region;
478 return FALSE;
479 }
480
481 region->data->nbRects = finalNbRects;
482 region->data->size = allocSize;
483 }
484
485 return TRUE;
486 }
487
region16_union_rect(REGION16 * dst,const REGION16 * src,const RECTANGLE_16 * rect)488 BOOL region16_union_rect(REGION16* dst, const REGION16* src, const RECTANGLE_16* rect)
489 {
490 const RECTANGLE_16* srcExtents;
491 RECTANGLE_16* dstExtents;
492 const RECTANGLE_16 *currentBand, *endSrcRect, *nextBand;
493 REGION16_DATA* newItems = NULL;
494 REGION16_DATA* tmpItems = NULL;
495 RECTANGLE_16* dstRect = NULL;
496 UINT32 usedRects, srcNbRects;
497 UINT16 topInterBand;
498 assert(src);
499 assert(src->data);
500 assert(dst);
501 srcExtents = region16_extents(src);
502 dstExtents = region16_extents_noconst(dst);
503
504 if (!region16_n_rects(src))
505 {
506 /* source is empty, so the union is rect */
507 dst->extents = *rect;
508 dst->data = allocateRegion(1);
509
510 if (!dst->data)
511 return FALSE;
512
513 dstRect = region16_rects_noconst(dst);
514 dstRect->top = rect->top;
515 dstRect->left = rect->left;
516 dstRect->right = rect->right;
517 dstRect->bottom = rect->bottom;
518 return TRUE;
519 }
520
521 newItems = allocateRegion((1 + region16_n_rects(src)) * 4);
522
523 if (!newItems)
524 return FALSE;
525
526 dstRect = (RECTANGLE_16*)(&newItems[1]);
527 usedRects = 0;
528
529 /* adds the piece of rect that is on the top of src */
530 if (rect->top < srcExtents->top)
531 {
532 dstRect->top = rect->top;
533 dstRect->left = rect->left;
534 dstRect->right = rect->right;
535 dstRect->bottom = MIN(srcExtents->top, rect->bottom);
536 usedRects++;
537 dstRect++;
538 }
539
540 /* treat possibly overlapping region */
541 currentBand = region16_rects(src, &srcNbRects);
542 endSrcRect = currentBand + srcNbRects;
543
544 while (currentBand < endSrcRect)
545 {
546 if ((currentBand->bottom <= rect->top) || (rect->bottom <= currentBand->top) ||
547 rectangle_contained_in_band(currentBand, endSrcRect, rect))
548 {
549 /* no overlap between rect and the band, rect is totally below or totally above
550 * the current band, or rect is already covered by an item of the band.
551 * let's copy all the rectangles from this band
552 +----+
553 | | rect (case 1)
554 +----+
555
556 =================
557 band of srcRect
558 =================
559 +----+
560 | | rect (case 2)
561 +----+
562 */
563 region16_copy_band_with_union(dstRect, currentBand, endSrcRect, currentBand->top,
564 currentBand->bottom, NULL, &usedRects, &nextBand,
565 &dstRect);
566 topInterBand = rect->top;
567 }
568 else
569 {
570 /* rect overlaps the band:
571 | | | |
572 ====^=================| |==| |=========================== band
573 | top split | | | |
574 v | 1 | | 2 |
575 ^ | | | | +----+ +----+
576 | merge zone | | | | | | | 4 |
577 v +----+ | | | | +----+
578 ^ | | | 3 |
579 | bottom split | | | |
580 ====v=========================| |==| |===================
581 | | | |
582
583 possible cases:
584 1) no top split, merge zone then a bottom split. The band will be splitted
585 in two
586 2) not band split, only the merge zone, band merged with rect but not splitted
587 3) a top split, the merge zone and no bottom split. The band will be split
588 in two
589 4) a top split, the merge zone and also a bottom split. The band will be
590 splitted in 3, but the coalesce algorithm may merge the created bands
591 */
592 UINT16 mergeTop = currentBand->top;
593 UINT16 mergeBottom = currentBand->bottom;
594
595 /* test if we need a top split, case 3 and 4 */
596 if (rect->top > currentBand->top)
597 {
598 region16_copy_band_with_union(dstRect, currentBand, endSrcRect, currentBand->top,
599 rect->top, NULL, &usedRects, &nextBand, &dstRect);
600 mergeTop = rect->top;
601 }
602
603 /* do the merge zone (all cases) */
604 if (rect->bottom < currentBand->bottom)
605 mergeBottom = rect->bottom;
606
607 region16_copy_band_with_union(dstRect, currentBand, endSrcRect, mergeTop, mergeBottom,
608 rect, &usedRects, &nextBand, &dstRect);
609
610 /* test if we need a bottom split, case 1 and 4 */
611 if (rect->bottom < currentBand->bottom)
612 {
613 region16_copy_band_with_union(dstRect, currentBand, endSrcRect, mergeBottom,
614 currentBand->bottom, NULL, &usedRects, &nextBand,
615 &dstRect);
616 }
617
618 topInterBand = currentBand->bottom;
619 }
620
621 /* test if a piece of rect should be inserted as a new band between
622 * the current band and the next one. band n and n+1 shouldn't touch.
623 *
624 * ==============================================================
625 * band n
626 * +------+ +------+
627 * ===========| rect |====================| |===============
628 * | | +------+ | |
629 * +------+ | rect | | rect |
630 * +------+ | |
631 * =======================================| |================
632 * +------+ band n+1
633 * ===============================================================
634 *
635 */
636 if ((nextBand < endSrcRect) && (nextBand->top != currentBand->bottom) &&
637 (rect->bottom > currentBand->bottom) && (rect->top < nextBand->top))
638 {
639 dstRect->right = rect->right;
640 dstRect->left = rect->left;
641 dstRect->top = topInterBand;
642 dstRect->bottom = MIN(nextBand->top, rect->bottom);
643 dstRect++;
644 usedRects++;
645 }
646
647 currentBand = nextBand;
648 }
649
650 /* adds the piece of rect that is below src */
651 if (srcExtents->bottom < rect->bottom)
652 {
653 dstRect->top = MAX(srcExtents->bottom, rect->top);
654 dstRect->left = rect->left;
655 dstRect->right = rect->right;
656 dstRect->bottom = rect->bottom;
657 usedRects++;
658 dstRect++;
659 }
660
661 if ((src == dst) && (src->data->size > 0) && (src->data != &empty_region))
662 free(src->data);
663
664 dstExtents->top = MIN(rect->top, srcExtents->top);
665 dstExtents->left = MIN(rect->left, srcExtents->left);
666 dstExtents->bottom = MAX(rect->bottom, srcExtents->bottom);
667 dstExtents->right = MAX(rect->right, srcExtents->right);
668 newItems->size = sizeof(REGION16_DATA) + (usedRects * sizeof(RECTANGLE_16));
669 tmpItems = realloc(newItems, newItems->size);
670 if (!tmpItems)
671 free(newItems);
672 newItems = tmpItems;
673 dst->data = newItems;
674
675 if (!dst->data)
676 {
677 free(newItems);
678 return FALSE;
679 }
680
681 dst->data->nbRects = usedRects;
682 return region16_simplify_bands(dst);
683 }
684
region16_intersects_rect(const REGION16 * src,const RECTANGLE_16 * arg2)685 BOOL region16_intersects_rect(const REGION16* src, const RECTANGLE_16* arg2)
686 {
687 const RECTANGLE_16 *rect, *endPtr, *srcExtents;
688 UINT32 nbRects;
689
690 if (!src || !src->data || !arg2)
691 return FALSE;
692
693 rect = region16_rects(src, &nbRects);
694
695 if (!nbRects)
696 return FALSE;
697
698 srcExtents = region16_extents(src);
699
700 if (nbRects == 1)
701 return rectangles_intersects(srcExtents, arg2);
702
703 if (!rectangles_intersects(srcExtents, arg2))
704 return FALSE;
705
706 for (endPtr = rect + nbRects; (rect < endPtr) && (arg2->bottom > rect->top); rect++)
707 {
708 if (rectangles_intersects(rect, arg2))
709 return TRUE;
710 }
711
712 return FALSE;
713 }
714
region16_intersect_rect(REGION16 * dst,const REGION16 * src,const RECTANGLE_16 * rect)715 BOOL region16_intersect_rect(REGION16* dst, const REGION16* src, const RECTANGLE_16* rect)
716 {
717 REGION16_DATA* newItems;
718 const RECTANGLE_16 *srcPtr, *endPtr, *srcExtents;
719 RECTANGLE_16* dstPtr;
720 UINT32 nbRects, usedRects;
721 RECTANGLE_16 common, newExtents;
722 assert(src);
723 assert(src->data);
724 srcPtr = region16_rects(src, &nbRects);
725
726 if (!nbRects)
727 {
728 region16_clear(dst);
729 return TRUE;
730 }
731
732 srcExtents = region16_extents(src);
733
734 if (nbRects == 1)
735 {
736 BOOL intersects = rectangles_intersection(srcExtents, rect, &common);
737 region16_clear(dst);
738
739 if (intersects)
740 return region16_union_rect(dst, dst, &common);
741
742 return TRUE;
743 }
744
745 newItems = allocateRegion(nbRects);
746
747 if (!newItems)
748 return FALSE;
749
750 dstPtr = (RECTANGLE_16*)(&newItems[1]);
751 usedRects = 0;
752 ZeroMemory(&newExtents, sizeof(newExtents));
753
754 /* accumulate intersecting rectangles, the final region16_simplify_bands() will
755 * do all the bad job to recreate correct rectangles
756 */
757 for (endPtr = srcPtr + nbRects; (srcPtr < endPtr) && (rect->bottom > srcPtr->top); srcPtr++)
758 {
759 if (rectangles_intersection(srcPtr, rect, &common))
760 {
761 *dstPtr = common;
762 usedRects++;
763 dstPtr++;
764
765 if (rectangle_is_empty(&newExtents))
766 {
767 /* Check if the existing newExtents is empty. If it is empty, use
768 * new common directly. We do not need to check common rectangle
769 * because the rectangles_intersection() ensures that it is not empty.
770 */
771 newExtents = common;
772 }
773 else
774 {
775 newExtents.top = MIN(common.top, newExtents.top);
776 newExtents.left = MIN(common.left, newExtents.left);
777 newExtents.bottom = MAX(common.bottom, newExtents.bottom);
778 newExtents.right = MAX(common.right, newExtents.right);
779 }
780 }
781 }
782
783 newItems->nbRects = usedRects;
784 newItems->size = sizeof(REGION16_DATA) + (usedRects * sizeof(RECTANGLE_16));
785
786 if ((dst->data->size > 0) && (dst->data != &empty_region))
787 free(dst->data);
788
789 dst->data = realloc(newItems, newItems->size);
790
791 if (!dst->data)
792 {
793 free(newItems);
794 return FALSE;
795 }
796
797 dst->extents = newExtents;
798 return region16_simplify_bands(dst);
799 }
800
region16_uninit(REGION16 * region)801 void region16_uninit(REGION16* region)
802 {
803 assert(region);
804
805 if (region->data)
806 {
807 if ((region->data->size > 0) && (region->data != &empty_region))
808 free(region->data);
809
810 region->data = NULL;
811 }
812 }
813