codec/region.c

 
#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);
  WINPR_ASSERT(region->data->nbRects <= INT32_MAX);
  return (int)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)
  {
    WINPR_ASSERT(data->nbRects <= UINT32_MAX);
    *nbRects = (UINT32)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 &region->extents;
}
 
static RECTANGLE_16* region16_extents_noconst(REGION16* region)
{
  if (!region)
    return NULL;
 
  return &region->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(&region->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);
}
 
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)
{
  RECTANGLE_16* endBand = NULL;
  int nbRects = 0;
  int finalNbRects = 0;
  int bandItems = 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;
      const size_t 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((1ULL + 4ULL * region16_n_rects(src)));
 
  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;
  }
}