diff options
Diffstat (limited to 'libfreerdp/codec/region.c')
| -rw-r--r-- | libfreerdp/codec/region.c | 820 |
1 files changed, 820 insertions, 0 deletions
diff --git a/libfreerdp/codec/region.c b/libfreerdp/codec/region.c new file mode 100644 index 0000000..ba7f3d2 --- /dev/null +++ b/libfreerdp/codec/region.c @@ -0,0 +1,820 @@ +/** + * FreeRDP: A Remote Desktop Protocol Implementation + * + * Copyright 2014 Thincast Technologies GmbH + * Copyright 2014 Hardening <contact@hardening-consulting.com> + * Copyright 2017 Armin Novak <armin.novak@thincast.com> + * Copyright 2017 Thincast Technologies GmbH + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <winpr/assert.h> +#include <winpr/memory.h> +#include <freerdp/log.h> +#include <freerdp/codec/region.h> + +#define TAG FREERDP_TAG("codec") + +/* + * The functions in this file implement the Region abstraction largely inspired from + * pixman library. The following comment is taken from the pixman code. + * + * A Region is simply a set of disjoint(non-overlapping) rectangles, plus an + * "extent" rectangle which is the smallest single rectangle that contains all + * the non-overlapping rectangles. + * + * A Region is implemented as a "y-x-banded" array of rectangles. This array + * imposes two degrees of order. First, all rectangles are sorted by top side + * y coordinate first (y1), and then by left side x coordinate (x1). + * + * Furthermore, the rectangles are grouped into "bands". Each rectangle in a + * band has the same top y coordinate (y1), and each has the same bottom y + * coordinate (y2). Thus all rectangles in a band differ only in their left + * and right side (x1 and x2). Bands are implicit in the array of rectangles: + * there is no separate list of band start pointers. + * + * The y-x band representation does not minimize rectangles. In particular, + * if a rectangle vertically crosses a band (the rectangle has scanlines in + * the y1 to y2 area spanned by the band), then the rectangle may be broken + * down into two or more smaller rectangles stacked one atop the other. + * + * ----------- ----------- + * | | | | band 0 + * | | -------- ----------- -------- + * | | | | in y-x banded | | | | band 1 + * | | | | form is | | | | + * ----------- | | ----------- -------- + * | | | | band 2 + * -------- -------- + * + * An added constraint on the rectangles is that they must cover as much + * horizontal area as possible: no two rectangles within a band are allowed + * to touch. + * + * Whenever possible, bands will be merged together to cover a greater vertical + * distance (and thus reduce the number of rectangles). Two bands can be merged + * only if the bottom of one touches the top of the other and they have + * rectangles in the same places (of the same width, of course). + */ + +struct S_REGION16_DATA +{ + long size; + long nbRects; +}; + +static REGION16_DATA empty_region = { 0, 0 }; + +void region16_init(REGION16* region) +{ + WINPR_ASSERT(region); + ZeroMemory(region, sizeof(REGION16)); + region->data = &empty_region; +} + +int region16_n_rects(const REGION16* region) +{ + WINPR_ASSERT(region); + WINPR_ASSERT(region->data); + return region->data->nbRects; +} + +const RECTANGLE_16* region16_rects(const REGION16* region, UINT32* nbRects) +{ + REGION16_DATA* data = NULL; + + if (nbRects) + *nbRects = 0; + + if (!region) + return NULL; + + data = region->data; + + if (!data) + return NULL; + + if (nbRects) + *nbRects = data->nbRects; + + return (RECTANGLE_16*)(data + 1); +} + +static INLINE RECTANGLE_16* region16_rects_noconst(REGION16* region) +{ + REGION16_DATA* data = NULL; + data = region->data; + + if (!data) + return NULL; + + return (RECTANGLE_16*)(&data[1]); +} + +const RECTANGLE_16* region16_extents(const REGION16* region) +{ + if (!region) + return NULL; + + return ®ion->extents; +} + +static RECTANGLE_16* region16_extents_noconst(REGION16* region) +{ + if (!region) + return NULL; + + return ®ion->extents; +} + +BOOL rectangle_is_empty(const RECTANGLE_16* rect) +{ + /* A rectangle with width <= 0 or height <= 0 should be regarded + * as empty. + */ + return ((rect->left >= rect->right) || (rect->top >= rect->bottom)) ? TRUE : FALSE; +} + +BOOL region16_is_empty(const REGION16* region) +{ + WINPR_ASSERT(region); + WINPR_ASSERT(region->data); + return (region->data->nbRects == 0); +} + +BOOL rectangles_equal(const RECTANGLE_16* r1, const RECTANGLE_16* r2) +{ + return ((r1->left == r2->left) && (r1->top == r2->top) && (r1->right == r2->right) && + (r1->bottom == r2->bottom)) + ? TRUE + : FALSE; +} + +BOOL rectangles_intersects(const RECTANGLE_16* r1, const RECTANGLE_16* r2) +{ + RECTANGLE_16 tmp = { 0 }; + return rectangles_intersection(r1, r2, &tmp); +} + +BOOL rectangles_intersection(const RECTANGLE_16* r1, const RECTANGLE_16* r2, RECTANGLE_16* dst) +{ + dst->left = MAX(r1->left, r2->left); + dst->right = MIN(r1->right, r2->right); + dst->top = MAX(r1->top, r2->top); + dst->bottom = MIN(r1->bottom, r2->bottom); + return (dst->left < dst->right) && (dst->top < dst->bottom); +} + +void region16_clear(REGION16* region) +{ + WINPR_ASSERT(region); + WINPR_ASSERT(region->data); + + if ((region->data->size > 0) && (region->data != &empty_region)) + free(region->data); + + region->data = &empty_region; + ZeroMemory(®ion->extents, sizeof(region->extents)); +} + +static INLINE REGION16_DATA* allocateRegion(long nbItems) +{ + long allocSize = sizeof(REGION16_DATA) + (nbItems * sizeof(RECTANGLE_16)); + REGION16_DATA* ret = (REGION16_DATA*)malloc(allocSize); + + if (!ret) + return ret; + + ret->size = allocSize; + ret->nbRects = nbItems; + return ret; +} + +BOOL region16_copy(REGION16* dst, const REGION16* src) +{ + WINPR_ASSERT(dst); + WINPR_ASSERT(dst->data); + WINPR_ASSERT(src); + WINPR_ASSERT(src->data); + + if (dst == src) + return TRUE; + + dst->extents = src->extents; + + if ((dst->data->size > 0) && (dst->data != &empty_region)) + free(dst->data); + + if (src->data->size == 0) + dst->data = &empty_region; + else + { + dst->data = allocateRegion(src->data->nbRects); + + if (!dst->data) + return FALSE; + + CopyMemory(dst->data, src->data, src->data->size); + } + + return TRUE; +} + +void region16_print(const REGION16* region) +{ + const RECTANGLE_16* rects = NULL; + UINT32 nbRects = 0; + int currentBandY = -1; + rects = region16_rects(region, &nbRects); + WLog_DBG(TAG, "nrects=%" PRIu32 "", nbRects); + + for (UINT32 i = 0; i < nbRects; i++, rects++) + { + if (rects->top != currentBandY) + { + currentBandY = rects->top; + WLog_DBG(TAG, "band %d: ", currentBandY); + } + + WLog_DBG(TAG, "(%" PRIu16 ",%" PRIu16 "-%" PRIu16 ",%" PRIu16 ")", rects->left, rects->top, + rects->right, rects->bottom); + } +} + +static void 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) +{ + UINT16 refY = src->top; + const RECTANGLE_16* startOverlap = NULL; + const RECTANGLE_16* endOverlap = NULL; + + /* merges a band with the given rect + * Input: + * unionRect + * | | + * | | + * ==============+===============+================================ + * |Item1| |Item2| |Item3| |Item4| |Item5| Band + * ==============+===============+================================ + * before | overlap | after + * + * Resulting band: + * +-----+ +----------------------+ +-----+ + * |Item1| | Item2 | |Item3| + * +-----+ +----------------------+ +-----+ + * + * We first copy as-is items that are before Item2, the first overlapping + * item. + * Then we find the last one that overlap unionRect to agregate Item2, Item3 + * and Item4 to create Item2. + * Finally Item5 is copied as Item3. + * + * When no unionRect is provided, we skip the two first steps to just copy items + */ + + if (unionRect) + { + /* items before unionRect */ + while ((src < end) && (src->top == refY) && (src->right < unionRect->left)) + { + dst->top = newTop; + dst->bottom = newBottom; + dst->right = src->right; + dst->left = src->left; + src++; + dst++; + *dstCounter += 1; + } + + /* treat items overlapping with unionRect */ + startOverlap = unionRect; + endOverlap = unionRect; + + if ((src < end) && (src->top == refY) && (src->left < unionRect->left)) + startOverlap = src; + + while ((src < end) && (src->top == refY) && (src->right < unionRect->right)) + { + src++; + } + + if ((src < end) && (src->top == refY) && (src->left < unionRect->right)) + { + endOverlap = src; + src++; + } + + dst->bottom = newBottom; + dst->top = newTop; + dst->left = startOverlap->left; + dst->right = endOverlap->right; + dst++; + *dstCounter += 1; + } + + /* treat remaining items on the same band */ + while ((src < end) && (src->top == refY)) + { + dst->top = newTop; + dst->bottom = newBottom; + dst->right = src->right; + dst->left = src->left; + src++; + dst++; + *dstCounter += 1; + } + + if (srcPtr) + *srcPtr = src; + + *dstPtr = dst; +} + +static RECTANGLE_16* next_band(RECTANGLE_16* band1, RECTANGLE_16* endPtr, int* nbItems) +{ + UINT16 refY = band1->top; + *nbItems = 0; + + while ((band1 < endPtr) && (band1->top == refY)) + { + band1++; + *nbItems += 1; + } + + return band1; +} + +static BOOL band_match(const RECTANGLE_16* band1, const RECTANGLE_16* band2, + const RECTANGLE_16* endPtr) +{ + int refBand2 = band2->top; + const RECTANGLE_16* band2Start = band2; + + while ((band1 < band2Start) && (band2 < endPtr) && (band2->top == refBand2)) + { + if ((band1->left != band2->left) || (band1->right != band2->right)) + return FALSE; + + band1++; + band2++; + } + + if (band1 != band2Start) + return FALSE; + + return (band2 == endPtr) || (band2->top != refBand2); +} + +/** compute if the rectangle is fully included in the band + * @param band a pointer on the beginning of the band + * @param endPtr end of the region + * @param rect the rectangle to test + * @return if rect is fully included in an item of the band + */ +static BOOL rectangle_contained_in_band(const RECTANGLE_16* band, const RECTANGLE_16* endPtr, + const RECTANGLE_16* rect) +{ + UINT16 refY = band->top; + + if ((band->top > rect->top) || (rect->bottom > band->bottom)) + return FALSE; + + /* note: as the band is sorted from left to right, once we've seen an item + * that is after rect->left we're sure that the result is False. + */ + while ((band < endPtr) && (band->top == refY) && (band->left <= rect->left)) + { + if (rect->right <= band->right) + return TRUE; + + band++; + } + + return FALSE; +} + +static BOOL region16_simplify_bands(REGION16* region) +{ + /** Simplify consecutive bands that touch and have the same items + * + * ==================== ==================== + * | 1 | | 2 | | | | | + * ==================== | | | | + * | 1 | | 2 | ====> | 1 | | 2 | + * ==================== | | | | + * | 1 | | 2 | | | | | + * ==================== ==================== + * + */ + RECTANGLE_16* endBand = NULL; + int nbRects = 0; + int finalNbRects = 0; + int bandItems = 0; + int toMove = 0; + finalNbRects = nbRects = region16_n_rects(region); + + if (nbRects < 2) + return TRUE; + + RECTANGLE_16* band1 = region16_rects_noconst(region); + RECTANGLE_16* endPtr = band1 + nbRects; + + do + { + RECTANGLE_16* band2 = next_band(band1, endPtr, &bandItems); + + if (band2 == endPtr) + break; + + if ((band1->bottom == band2->top) && band_match(band1, band2, endPtr)) + { + /* adjust the bottom of band1 items */ + RECTANGLE_16* tmp = band1; + + while (tmp < band2) + { + tmp->bottom = band2->bottom; + tmp++; + } + + /* override band2, we don't move band1 pointer as the band after band2 + * may be merged too */ + endBand = band2 + bandItems; + toMove = (endPtr - endBand) * sizeof(RECTANGLE_16); + + if (toMove) + MoveMemory(band2, endBand, toMove); + + finalNbRects -= bandItems; + endPtr -= bandItems; + } + else + { + band1 = band2; + } + } while (TRUE); + + if (finalNbRects != nbRects) + { + size_t allocSize = sizeof(REGION16_DATA) + (finalNbRects * sizeof(RECTANGLE_16)); + REGION16_DATA* data = realloc(region->data, allocSize); + if (!data) + free(region->data); + region->data = data; + + if (!region->data) + { + region->data = &empty_region; + return FALSE; + } + + region->data->nbRects = finalNbRects; + region->data->size = allocSize; + } + + return TRUE; +} + +BOOL region16_union_rect(REGION16* dst, const REGION16* src, const RECTANGLE_16* rect) +{ + const RECTANGLE_16* srcExtents = NULL; + RECTANGLE_16* dstExtents = NULL; + const RECTANGLE_16* currentBand = NULL; + const RECTANGLE_16* endSrcRect = NULL; + const RECTANGLE_16* nextBand = NULL; + REGION16_DATA* newItems = NULL; + REGION16_DATA* tmpItems = NULL; + RECTANGLE_16* dstRect = NULL; + UINT32 usedRects = 0; + UINT32 srcNbRects = 0; + UINT16 topInterBand = 0; + WINPR_ASSERT(src); + WINPR_ASSERT(dst); + srcExtents = region16_extents(src); + dstExtents = region16_extents_noconst(dst); + + if (!region16_n_rects(src)) + { + /* source is empty, so the union is rect */ + dst->extents = *rect; + dst->data = allocateRegion(1); + + if (!dst->data) + return FALSE; + + dstRect = region16_rects_noconst(dst); + dstRect->top = rect->top; + dstRect->left = rect->left; + dstRect->right = rect->right; + dstRect->bottom = rect->bottom; + return TRUE; + } + + newItems = allocateRegion((1 + region16_n_rects(src)) * 4); + + if (!newItems) + return FALSE; + + dstRect = (RECTANGLE_16*)(&newItems[1]); + usedRects = 0; + + /* adds the piece of rect that is on the top of src */ + if (rect->top < srcExtents->top) + { + dstRect->top = rect->top; + dstRect->left = rect->left; + dstRect->right = rect->right; + dstRect->bottom = MIN(srcExtents->top, rect->bottom); + usedRects++; + dstRect++; + } + + /* treat possibly overlapping region */ + currentBand = region16_rects(src, &srcNbRects); + endSrcRect = currentBand + srcNbRects; + + while (currentBand < endSrcRect) + { + if ((currentBand->bottom <= rect->top) || (rect->bottom <= currentBand->top) || + rectangle_contained_in_band(currentBand, endSrcRect, rect)) + { + /* no overlap between rect and the band, rect is totally below or totally above + * the current band, or rect is already covered by an item of the band. + * let's copy all the rectangles from this band + +----+ + | | rect (case 1) + +----+ + + ================= + band of srcRect + ================= + +----+ + | | rect (case 2) + +----+ + */ + region16_copy_band_with_union(dstRect, currentBand, endSrcRect, currentBand->top, + currentBand->bottom, NULL, &usedRects, &nextBand, + &dstRect); + topInterBand = rect->top; + } + else + { + /* rect overlaps the band: + | | | | + ====^=================| |==| |=========================== band + | top split | | | | + v | 1 | | 2 | + ^ | | | | +----+ +----+ + | merge zone | | | | | | | 4 | + v +----+ | | | | +----+ + ^ | | | 3 | + | bottom split | | | | + ====v=========================| |==| |=================== + | | | | + + possible cases: + 1) no top split, merge zone then a bottom split. The band will be splitted + in two + 2) not band split, only the merge zone, band merged with rect but not splitted + 3) a top split, the merge zone and no bottom split. The band will be split + in two + 4) a top split, the merge zone and also a bottom split. The band will be + splitted in 3, but the coalesce algorithm may merge the created bands + */ + UINT16 mergeTop = currentBand->top; + UINT16 mergeBottom = currentBand->bottom; + + /* test if we need a top split, case 3 and 4 */ + if (rect->top > currentBand->top) + { + region16_copy_band_with_union(dstRect, currentBand, endSrcRect, currentBand->top, + rect->top, NULL, &usedRects, &nextBand, &dstRect); + mergeTop = rect->top; + } + + /* do the merge zone (all cases) */ + if (rect->bottom < currentBand->bottom) + mergeBottom = rect->bottom; + + region16_copy_band_with_union(dstRect, currentBand, endSrcRect, mergeTop, mergeBottom, + rect, &usedRects, &nextBand, &dstRect); + + /* test if we need a bottom split, case 1 and 4 */ + if (rect->bottom < currentBand->bottom) + { + region16_copy_band_with_union(dstRect, currentBand, endSrcRect, mergeBottom, + currentBand->bottom, NULL, &usedRects, &nextBand, + &dstRect); + } + + topInterBand = currentBand->bottom; + } + + /* test if a piece of rect should be inserted as a new band between + * the current band and the next one. band n and n+1 shouldn't touch. + * + * ============================================================== + * band n + * +------+ +------+ + * ===========| rect |====================| |=============== + * | | +------+ | | + * +------+ | rect | | rect | + * +------+ | | + * =======================================| |================ + * +------+ band n+1 + * =============================================================== + * + */ + if ((nextBand < endSrcRect) && (nextBand->top != currentBand->bottom) && + (rect->bottom > currentBand->bottom) && (rect->top < nextBand->top)) + { + dstRect->right = rect->right; + dstRect->left = rect->left; + dstRect->top = topInterBand; + dstRect->bottom = MIN(nextBand->top, rect->bottom); + dstRect++; + usedRects++; + } + + currentBand = nextBand; + } + + /* adds the piece of rect that is below src */ + if (srcExtents->bottom < rect->bottom) + { + dstRect->top = MAX(srcExtents->bottom, rect->top); + dstRect->left = rect->left; + dstRect->right = rect->right; + dstRect->bottom = rect->bottom; + usedRects++; + dstRect++; + } + + if ((src == dst) && (dst->data != &empty_region)) + free(dst->data); + + dstExtents->top = MIN(rect->top, srcExtents->top); + dstExtents->left = MIN(rect->left, srcExtents->left); + dstExtents->bottom = MAX(rect->bottom, srcExtents->bottom); + dstExtents->right = MAX(rect->right, srcExtents->right); + newItems->size = sizeof(REGION16_DATA) + (usedRects * sizeof(RECTANGLE_16)); + tmpItems = realloc(newItems, newItems->size); + if (!tmpItems) + free(newItems); + newItems = tmpItems; + dst->data = newItems; + + if (!dst->data) + return FALSE; + + dst->data->nbRects = usedRects; + return region16_simplify_bands(dst); +} + +BOOL region16_intersects_rect(const REGION16* src, const RECTANGLE_16* arg2) +{ + const RECTANGLE_16* rect = NULL; + const RECTANGLE_16* endPtr = NULL; + const RECTANGLE_16* srcExtents = NULL; + UINT32 nbRects = 0; + + if (!src || !src->data || !arg2) + return FALSE; + + rect = region16_rects(src, &nbRects); + + if (!nbRects) + return FALSE; + + srcExtents = region16_extents(src); + + if (nbRects == 1) + return rectangles_intersects(srcExtents, arg2); + + if (!rectangles_intersects(srcExtents, arg2)) + return FALSE; + + for (endPtr = rect + nbRects; (rect < endPtr) && (arg2->bottom > rect->top); rect++) + { + if (rectangles_intersects(rect, arg2)) + return TRUE; + } + + return FALSE; +} + +BOOL region16_intersect_rect(REGION16* dst, const REGION16* src, const RECTANGLE_16* rect) +{ + REGION16_DATA* newItems = NULL; + const RECTANGLE_16* srcPtr = NULL; + const RECTANGLE_16* endPtr = NULL; + const RECTANGLE_16* srcExtents = NULL; + RECTANGLE_16* dstPtr = NULL; + UINT32 nbRects = 0; + UINT32 usedRects = 0; + RECTANGLE_16 common; + RECTANGLE_16 newExtents; + WINPR_ASSERT(src); + WINPR_ASSERT(src->data); + srcPtr = region16_rects(src, &nbRects); + + if (!nbRects) + { + region16_clear(dst); + return TRUE; + } + + srcExtents = region16_extents(src); + + if (nbRects == 1) + { + BOOL intersects = rectangles_intersection(srcExtents, rect, &common); + region16_clear(dst); + + if (intersects) + return region16_union_rect(dst, dst, &common); + + return TRUE; + } + + newItems = allocateRegion(nbRects); + + if (!newItems) + return FALSE; + + dstPtr = (RECTANGLE_16*)(&newItems[1]); + usedRects = 0; + ZeroMemory(&newExtents, sizeof(newExtents)); + + /* accumulate intersecting rectangles, the final region16_simplify_bands() will + * do all the bad job to recreate correct rectangles + */ + for (endPtr = srcPtr + nbRects; (srcPtr < endPtr) && (rect->bottom > srcPtr->top); srcPtr++) + { + if (rectangles_intersection(srcPtr, rect, &common)) + { + *dstPtr = common; + usedRects++; + dstPtr++; + + if (rectangle_is_empty(&newExtents)) + { + /* Check if the existing newExtents is empty. If it is empty, use + * new common directly. We do not need to check common rectangle + * because the rectangles_intersection() ensures that it is not empty. + */ + newExtents = common; + } + else + { + newExtents.top = MIN(common.top, newExtents.top); + newExtents.left = MIN(common.left, newExtents.left); + newExtents.bottom = MAX(common.bottom, newExtents.bottom); + newExtents.right = MAX(common.right, newExtents.right); + } + } + } + + newItems->nbRects = usedRects; + newItems->size = sizeof(REGION16_DATA) + (usedRects * sizeof(RECTANGLE_16)); + + if ((dst->data->size > 0) && (dst->data != &empty_region)) + free(dst->data); + + dst->data = realloc(newItems, newItems->size); + + if (!dst->data) + { + free(newItems); + return FALSE; + } + + dst->extents = newExtents; + return region16_simplify_bands(dst); +} + +void region16_uninit(REGION16* region) +{ + WINPR_ASSERT(region); + + if (region->data) + { + if ((region->data->size > 0) && (region->data != &empty_region)) + free(region->data); + + region->data = NULL; + } +} |