From 5f8de423f190bbb79a62f804151bc24824fa32d8 Mon Sep 17 00:00:00 2001 From: "Matt A. Tobin" Date: Fri, 2 Feb 2018 04:16:08 -0500 Subject: Add m-esr52 at 52.6.0 --- gfx/src/nsRegion.cpp | 1146 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1146 insertions(+) create mode 100644 gfx/src/nsRegion.cpp (limited to 'gfx/src/nsRegion.cpp') diff --git a/gfx/src/nsRegion.cpp b/gfx/src/nsRegion.cpp new file mode 100644 index 000000000..3b0bec1e3 --- /dev/null +++ b/gfx/src/nsRegion.cpp @@ -0,0 +1,1146 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + + +#include "nsRegion.h" +#include "nsTArray.h" +#include "gfxUtils.h" +#include "mozilla/ToString.h" + +bool nsRegion::Contains(const nsRegion& aRgn) const +{ + // XXX this could be made faster by iterating over + // both regions at the same time some how + for (auto iter = aRgn.RectIter(); !iter.Done(); iter.Next()) { + if (!Contains(iter.Get())) { + return false; + } + } + return true; +} + +bool nsRegion::Intersects(const nsRect& aRect) const +{ + // XXX this could be made faster by using pixman_region32_contains_rect + for (auto iter = RectIter(); !iter.Done(); iter.Next()) { + if (iter.Get().Intersects(aRect)) { + return true; + } + } + return false; +} + +void nsRegion::Inflate(const nsMargin& aMargin) +{ + int n; + pixman_box32_t *boxes = pixman_region32_rectangles(&mImpl, &n); + for (int i=0; i= 1, "Invalid max rect count"); + + if (GetNumRects() <= aMaxRects) + return; + + pixman_box32_t *boxes; + int n; + boxes = pixman_region32_rectangles(&mImpl, &n); + + // Try combining rects in horizontal bands into a single rect + int dest = 0; + for (int src = 1; src < n; src++) + { + // The goal here is to try to keep groups of rectangles that are vertically + // discontiguous as separate rectangles in the final region. This is + // simple and fast to implement and page contents tend to vary more + // vertically than horizontally (which is why our rectangles are stored + // sorted by y-coordinate, too). + // + // Note: if boxes share y1 because of the canonical representation they + // will share y2 + while ((src < (n)) && boxes[dest].y1 == boxes[src].y1) { + // merge box[i] and box[i+1] + boxes[dest].x2 = boxes[src].x2; + src++; + } + if (src < n) { + dest++; + boxes[dest] = boxes[src]; + } + } + + uint32_t reducedCount = dest+1; + // pixman has a special representation for + // regions of 1 rectangle. So just use the + // bounds in that case + if (reducedCount > 1 && reducedCount <= aMaxRects) { + // reach into pixman and lower the number + // of rects stored in data. + mImpl.data->numRects = reducedCount; + } else { + *this = GetBounds(); + } +} + +// compute the covered area difference between two rows. +// by iterating over both rows simultaneously and adding up +// the additional increase in area caused by extending each +// of the rectangles to the combined height of both rows +static uint32_t ComputeMergedAreaIncrease(pixman_box32_t *topRects, + pixman_box32_t *topRectsEnd, + pixman_box32_t *bottomRects, + pixman_box32_t *bottomRectsEnd) +{ + uint32_t totalArea = 0; + struct pt { + int32_t x, y; + }; + + + pt *i = (pt*)topRects; + pt *end_i = (pt*)topRectsEnd; + pt *j = (pt*)bottomRects; + pt *end_j = (pt*)bottomRectsEnd; + bool top = false; + bool bottom = false; + + int cur_x = i->x; + bool top_next = top; + bool bottom_next = bottom; + //XXX: we could probably simplify this condition and perhaps move it into the loop below + if (j->x < cur_x) { + cur_x = j->x; + j++; + bottom_next = !bottom; + } else if (j->x == cur_x) { + i++; + top_next = !top; + bottom_next = !bottom; + j++; + } else { + top_next = !top; + i++; + } + + int topRectsHeight = topRects->y2 - topRects->y1; + int bottomRectsHeight = bottomRects->y2 - bottomRects->y1; + int inbetweenHeight = bottomRects->y1 - topRects->y2; + int width = cur_x; + // top and bottom are the in-status to the left of cur_x + do { + if (top && !bottom) { + totalArea += (inbetweenHeight+bottomRectsHeight)*width; + } else if (bottom && !top) { + totalArea += (inbetweenHeight+topRectsHeight)*width; + } else if (bottom && top) { + totalArea += (inbetweenHeight)*width; + } + top = top_next; + bottom = bottom_next; + // find the next edge + if (i->x < j->x) { + top_next = !top; + width = i->x - cur_x; + cur_x = i->x; + i++; + } else if (j->x < i->x) { + bottom_next = !bottom; + width = j->x - cur_x; + cur_x = j->x; + j++; + } else { // i->x == j->x + top_next = !top; + bottom_next = !bottom; + width = i->x - cur_x; + cur_x = i->x; + i++; + j++; + } + } while (i < end_i && j < end_j); + + // handle any remaining rects + while (i < end_i) { + width = i->x - cur_x; + cur_x = i->x; + i++; + if (top) + totalArea += (inbetweenHeight+bottomRectsHeight)*width; + top = !top; + } + + while (j < end_j) { + width = j->x - cur_x; + cur_x = j->x; + j++; + if (bottom) + totalArea += (inbetweenHeight+topRectsHeight)*width; + bottom = !bottom; + } + return totalArea; +} + +static pixman_box32_t * +CopyRow(pixman_box32_t *dest_it, pixman_box32_t *src_start, pixman_box32_t *src_end) +{ + // XXX: std::copy + pixman_box32_t *src_it = src_start; + while (src_it < src_end) { + *dest_it++ = *src_it++; + } + return dest_it; +} + + +#define WRITE_RECT(x1, x2, y1, y2) \ + do { \ + tmpRect->x1 = x1; \ + tmpRect->x2 = x2; \ + tmpRect->y1 = y1; \ + tmpRect->y2 = y2; \ + tmpRect++; \ + } while (0) + +/* If 'r' overlaps the current rect, then expand the current rect to include + * it. Otherwise write the current rect out to tmpRect, and set r as the + * updated current rect. */ +#define MERGE_RECT(r) \ + do { \ + if (r->x1 <= x2) { \ + if (x2 < r->x2) \ + x2 = r->x2; \ + } else { \ + WRITE_RECT(x1, x2, y1, y2); \ + x1 = r->x1; \ + x2 = r->x2; \ + } \ + r++; \ + } while (0) + + +/* Can we merge two sets of rects without extra space? + * Yes, but not easily. We can even do it stably + * but we don't need that property. + * + * This is written in the style of pixman_region_union_o */ +static pixman_box32_t * +MergeRects(pixman_box32_t *r1, + pixman_box32_t *r1_end, + pixman_box32_t *r2, + pixman_box32_t *r2_end, + pixman_box32_t *tmpRect) +{ + /* This routine works by maintaining the current + * rectangle in x1,x2,y1,y2 and either merging + * in the left most rectangle if it overlaps or + * outputing the current rectangle and setting + * it to the the left most one */ + const int y1 = r1->y1; + const int y2 = r2->y2; + int x1; + int x2; + + /* Find the left-most edge */ + if (r1->x1 < r2->x1) { + x1 = r1->x1; + x2 = r1->x2; + r1++; + } else { + x1 = r2->x1; + x2 = r2->x2; + r2++; + } + + while (r1 != r1_end && r2 != r2_end) { + /* Find and merge the left-most rectangle */ + if (r1->x1 < r2->x1) + MERGE_RECT (r1); + else + MERGE_RECT (r2); + } + + /* Finish up any left overs */ + if (r1 != r1_end) { + do { + MERGE_RECT (r1); + } while (r1 != r1_end); + } else if (r2 != r2_end) { + do { + MERGE_RECT(r2); + } while (r2 != r2_end); + } + + /* Finish up the last rectangle */ + WRITE_RECT(x1, x2, y1, y2); + + return tmpRect; +} + +void nsRegion::SimplifyOutwardByArea(uint32_t aThreshold) +{ + + pixman_box32_t *boxes; + int n; + boxes = pixman_region32_rectangles(&mImpl, &n); + + // if we have no rectangles then we're done + if (!n) + return; + + pixman_box32_t *end = boxes + n; + pixman_box32_t *topRectsEnd = boxes+1; + pixman_box32_t *topRects = boxes; + + // we need some temporary storage for merging both rows of rectangles + AutoTArray tmpStorage; + tmpStorage.SetCapacity(n); + pixman_box32_t *tmpRect = tmpStorage.Elements(); + + pixman_box32_t *destRect = boxes; + pixman_box32_t *rect = tmpRect; + // find the end of the first span of rectangles + while (topRectsEnd < end && topRectsEnd->y1 == topRects->y1) { + topRectsEnd++; + } + + // if we only have one row we are done + if (topRectsEnd == end) + return; + + pixman_box32_t *bottomRects = topRectsEnd; + pixman_box32_t *bottomRectsEnd = bottomRects+1; + do { + // find the end of the bottom span of rectangles + while (bottomRectsEnd < end && bottomRectsEnd->y1 == bottomRects->y1) { + bottomRectsEnd++; + } + uint32_t totalArea = ComputeMergedAreaIncrease(topRects, topRectsEnd, + bottomRects, bottomRectsEnd); + + if (totalArea <= aThreshold) { + // merge the rects into tmpRect + rect = MergeRects(topRects, topRectsEnd, bottomRects, bottomRectsEnd, tmpRect); + + // set topRects to where the newly merged rects will be so that we use them + // as our next set of topRects + topRects = destRect; + // copy the merged rects back into the destination + topRectsEnd = CopyRow(destRect, tmpRect, rect); + } else { + // copy the unmerged rects + destRect = CopyRow(destRect, topRects, topRectsEnd); + + topRects = bottomRects; + topRectsEnd = bottomRectsEnd; + if (bottomRectsEnd == end) { + // copy the last row when we are done + topRectsEnd = CopyRow(destRect, topRects, topRectsEnd); + } + } + bottomRects = bottomRectsEnd; + } while (bottomRectsEnd != end); + + + uint32_t reducedCount = topRectsEnd - pixman_region32_rectangles(&this->mImpl, &n); + // pixman has a special representation for + // regions of 1 rectangle. So just use the + // bounds in that case + if (reducedCount > 1) { + // reach into pixman and lower the number + // of rects stored in data. + this->mImpl.data->numRects = reducedCount; + } else { + *this = GetBounds(); + } +} + + +typedef void (*visit_fn)(void *closure, VisitSide side, int x1, int y1, int x2, int y2); + +static bool VisitNextEdgeBetweenRect(visit_fn visit, void *closure, VisitSide side, + pixman_box32_t *&r1, pixman_box32_t *&r2, const int y, int &x1) +{ + // check for overlap + if (r1->x2 >= r2->x1) { + MOZ_ASSERT(r2->x1 >= x1); + visit(closure, side, x1, y, r2->x1, y); + + // find the rect that ends first or always drop the one that comes first? + if (r1->x2 < r2->x2) { + x1 = r1->x2; + r1++; + } else { + x1 = r2->x2; + r2++; + } + return true; + } else { + MOZ_ASSERT(r1->x2 < r2->x2); + // we handle the corners by just extending the top and bottom edges + visit(closure, side, x1, y, r1->x2+1, y); + r1++; + // we assign x1 because we can assume that x1 <= r2->x1 - 1 + // However the caller may know better and if so, may update + // x1 to r1->x1 + x1 = r2->x1 - 1; + return false; + } +} + +//XXX: if we need to this can compute the end of the row +static void +VisitSides(visit_fn visit, void *closure, pixman_box32_t *r, pixman_box32_t *r_end) +{ + // XXX: we can drop LEFT/RIGHT and just use the orientation + // of the line if it makes sense + while (r != r_end) { + visit(closure, VisitSide::LEFT, r->x1, r->y1, r->x1, r->y2); + visit(closure, VisitSide::RIGHT, r->x2, r->y1, r->x2, r->y2); + r++; + } +} + +static void +VisitAbove(visit_fn visit, void *closure, pixman_box32_t *r, pixman_box32_t *r_end) +{ + while (r != r_end) { + visit(closure, VisitSide::TOP, r->x1-1, r->y1, r->x2+1, r->y1); + r++; + } +} + +static void +VisitBelow(visit_fn visit, void *closure, pixman_box32_t *r, pixman_box32_t *r_end) +{ + while (r != r_end) { + visit(closure, VisitSide::BOTTOM, r->x1-1, r->y2, r->x2+1, r->y2); + r++; + } +} + +static pixman_box32_t * +VisitInbetween(visit_fn visit, void *closure, pixman_box32_t *r1, + pixman_box32_t *r1_end, + pixman_box32_t *r2, + pixman_box32_t *r2_end) +{ + const int y = r1->y2; + int x1; + + bool overlap = false; + while (r1 != r1_end && r2 != r2_end) { + if (!overlap) { + /* Find the left-most edge */ + if (r1->x1 < r2->x1) { + x1 = r1->x1 - 1; + } else { + x1 = r2->x1 - 1; + } + } + + MOZ_ASSERT((x1 >= (r1->x1 - 1)) || (x1 >= (r2->x1 - 1))); + if (r1->x1 < r2->x1) { + overlap = VisitNextEdgeBetweenRect(visit, closure, VisitSide::BOTTOM, r1, r2, y, x1); + } else { + overlap = VisitNextEdgeBetweenRect(visit, closure, VisitSide::TOP, r2, r1, y, x1); + } + } + + /* Finish up which ever row has remaining rects*/ + if (r1 != r1_end) { + // top row + do { + visit(closure, VisitSide::BOTTOM, x1, y, r1->x2 + 1, y); + r1++; + if (r1 == r1_end) + break; + x1 = r1->x1 - 1; + } while (true); + } else if (r2 != r2_end) { + // bottom row + do { + visit(closure, VisitSide::TOP, x1, y, r2->x2 + 1, y); + r2++; + if (r2 == r2_end) + break; + x1 = r2->x1 - 1; + } while (true); + } + + return 0; +} + +void nsRegion::VisitEdges (visit_fn visit, void *closure) +{ + pixman_box32_t *boxes; + int n; + boxes = pixman_region32_rectangles(&mImpl, &n); + + // if we have no rectangles then we're done + if (!n) + return; + + pixman_box32_t *end = boxes + n; + pixman_box32_t *topRectsEnd = boxes + 1; + pixman_box32_t *topRects = boxes; + + // find the end of the first span of rectangles + while (topRectsEnd < end && topRectsEnd->y1 == topRects->y1) { + topRectsEnd++; + } + + // In order to properly handle convex corners we always visit the sides first + // that way when we visit the corners we can pad using the value from the sides + VisitSides(visit, closure, topRects, topRectsEnd); + + VisitAbove(visit, closure, topRects, topRectsEnd); + + pixman_box32_t *bottomRects = topRects; + pixman_box32_t *bottomRectsEnd = topRectsEnd; + if (topRectsEnd != end) { + do { + // find the next row of rects + bottomRects = topRectsEnd; + bottomRectsEnd = topRectsEnd + 1; + while (bottomRectsEnd < end && bottomRectsEnd->y1 == bottomRects->y1) { + bottomRectsEnd++; + } + + VisitSides(visit, closure, bottomRects, bottomRectsEnd); + + if (topRects->y2 == bottomRects->y1) { + VisitInbetween(visit, closure, topRects, topRectsEnd, + bottomRects, bottomRectsEnd); + } else { + VisitBelow(visit, closure, topRects, topRectsEnd); + VisitAbove(visit, closure, bottomRects, bottomRectsEnd); + } + + topRects = bottomRects; + topRectsEnd = bottomRectsEnd; + } while (bottomRectsEnd != end); + } + + // the bottom of the region doesn't touch anything else so we + // can always visit it at the end + VisitBelow(visit, closure, bottomRects, bottomRectsEnd); +} + + +void nsRegion::SimplifyInward (uint32_t aMaxRects) +{ + NS_ASSERTION(aMaxRects >= 1, "Invalid max rect count"); + + if (GetNumRects() <= aMaxRects) + return; + + SetEmpty(); +} + +uint64_t nsRegion::Area () const +{ + uint64_t area = 0; + for (auto iter = RectIter(); !iter.Done(); iter.Next()) { + const nsRect& rect = iter.Get(); + area += uint64_t(rect.width) * rect.height; + } + return area; +} + +nsRegion& nsRegion::ScaleRoundOut (float aXScale, float aYScale) +{ + if (mozilla::gfx::FuzzyEqual(aXScale, 1.0f) && + mozilla::gfx::FuzzyEqual(aYScale, 1.0f)) { + return *this; + } + + int n; + pixman_box32_t *boxes = pixman_region32_rectangles(&mImpl, &n); + for (int i=0; i= first.XMost()) { + // The top of rect contains the bottom of the first rect + firstDeviceRect.SetBottomEdge(deviceRect.y); + } else if (rect.x >= first.x && rect.XMost() <= first.XMost()) { + // The bottom of the first contains the top of rect + deviceRect.SetTopEdge(firstDeviceRect.YMost()); + } + } + } + + boxes[i] = RectToBox(deviceRect); + } + + boxes[0] = RectToBox(firstDeviceRect); + + pixman_region32_fini(&intRegion.mImpl.mImpl); + // This will union all of the rectangles and runs in about O(n lg(n)) + pixman_region32_init_rects(&intRegion.mImpl.mImpl, boxes, n); + } + return intRegion; + +} + +// A cell's "value" is a pair consisting of +// a) the area of the subrectangle it corresponds to, if it's in +// aContainingRect and in the region, 0 otherwise +// b) the area of the subrectangle it corresponds to, if it's in the region, +// 0 otherwise +// Addition, subtraction and identity are defined on these values in the +// obvious way. Partial order is lexicographic. +// A "large negative value" is defined with large negative numbers for both +// fields of the pair. This negative value has the property that adding any +// number of non-negative values to it always results in a negative value. +// +// The GetLargestRectangle algorithm works in three phases: +// 1) Convert the region into a grid by adding vertical/horizontal lines for +// each edge of each rectangle in the region. +// 2) For each rectangle in the region, for each cell it contains, set that +// cells's value as described above. +// 3) Calculate the submatrix with the largest sum such that none of its cells +// contain any 0s (empty regions). The rectangle represented by the +// submatrix is the largest rectangle in the region. +// +// Let k be the number of rectangles in the region. +// Let m be the height of the grid generated in step 1. +// Let n be the width of the grid generated in step 1. +// +// Step 1 is O(k) in time and O(m+n) in space for the sparse grid. +// Step 2 is O(mn) in time and O(mn) in additional space for the full grid. +// Step 3 is O(m^2 n) in time and O(mn) in additional space +// +// The implementation of steps 1 and 2 are rather straightforward. However our +// implementation of step 3 uses dynamic programming to achieve its efficiency. +// +// Psuedo code for step 3 is as follows where G is the grid from step 1 and A +// is the array from step 2: +// Phase3 = function (G, A, m, n) { +// let (t,b,l,r,_) = MaxSum2D(A,m,n) +// return rect(G[t],G[l],G[r],G[b]); +// } +// MaxSum2D = function (A, m, n) { +// S = array(m+1,n+1) +// S[0][i] = 0 for i in [0,n] +// S[j][0] = 0 for j in [0,m] +// S[j][i] = (if A[j-1][i-1] = 0 then some large negative value else A[j-1][i-1]) +// + S[j-1][n] + S[j][i-1] - S[j-1][i-1] +// +// // top, bottom, left, right, area +// var maxRect = (-1, -1, -1, -1, 0); +// +// for all (m',m'') in [0, m]^2 { +// let B = { S[m'][i] - S[m''][i] | 0 <= i <= n } +// let ((l,r),area) = MaxSum1D(B,n+1) +// if (area > maxRect.area) { +// maxRect := (m', m'', l, r, area) +// } +// } +// +// return maxRect; +// } +// +// Originally taken from Improved algorithms for the k-maximum subarray problem +// for small k - SE Bae, T Takaoka but modified to show the explicit tracking +// of indices and we already have the prefix sums from our one call site so +// there's no need to construct them. +// MaxSum1D = function (A,n) { +// var minIdx = 0; +// var min = 0; +// var maxIndices = (0,0); +// var max = 0; +// for i in range(n) { +// let cand = A[i] - min; +// if (cand > max) { +// max := cand; +// maxIndices := (minIdx, i) +// } +// if (min > A[i]) { +// min := A[i]; +// minIdx := i; +// } +// } +// return (minIdx, maxIdx, max); +// } + +namespace { + // This class represents a partitioning of an axis delineated by coordinates. + // It internally maintains a sorted array of coordinates. + class AxisPartition { + public: + // Adds a new partition at the given coordinate to this partitioning. If + // the coordinate is already present in the partitioning, this does nothing. + void InsertCoord(nscoord c) { + uint32_t i = mStops.IndexOfFirstElementGt(c); + if (i == 0 || mStops[i-1] != c) { + mStops.InsertElementAt(i, c); + } + } + + // Returns the array index of the given partition point. The partition + // point must already be present in the partitioning. + int32_t IndexOf(nscoord p) const { + return mStops.BinaryIndexOf(p); + } + + // Returns the partition at the given index which must be non-zero and + // less than the number of partitions in this partitioning. + nscoord StopAt(int32_t index) const { + return mStops[index]; + } + + // Returns the size of the gap between the partition at the given index and + // the next partition in this partitioning. If the index is the last index + // in the partitioning, the result is undefined. + nscoord StopSize(int32_t index) const { + return mStops[index+1] - mStops[index]; + } + + // Returns the number of partitions in this partitioning. + int32_t GetNumStops() const { return mStops.Length(); } + + private: + nsTArray mStops; + }; + + const int64_t kVeryLargeNegativeNumber = 0xffff000000000000ll; + + struct SizePair { + int64_t mSizeContainingRect; + int64_t mSize; + + SizePair() : mSizeContainingRect(0), mSize(0) {} + + static SizePair VeryLargeNegative() { + SizePair result; + result.mSize = result.mSizeContainingRect = kVeryLargeNegativeNumber; + return result; + } + bool operator<(const SizePair& aOther) const { + if (mSizeContainingRect < aOther.mSizeContainingRect) + return true; + if (mSizeContainingRect > aOther.mSizeContainingRect) + return false; + return mSize < aOther.mSize; + } + bool operator>(const SizePair& aOther) const { + return aOther.operator<(*this); + } + SizePair operator+(const SizePair& aOther) const { + SizePair result = *this; + result.mSizeContainingRect += aOther.mSizeContainingRect; + result.mSize += aOther.mSize; + return result; + } + SizePair operator-(const SizePair& aOther) const { + SizePair result = *this; + result.mSizeContainingRect -= aOther.mSizeContainingRect; + result.mSize -= aOther.mSize; + return result; + } + }; + + // Returns the sum and indices of the subarray with the maximum sum of the + // given array (A,n), assuming the array is already in prefix sum form. + SizePair MaxSum1D(const nsTArray &A, int32_t n, + int32_t *minIdx, int32_t *maxIdx) { + // The min/max indicies of the largest subarray found so far + SizePair min, max; + int32_t currentMinIdx = 0; + + *minIdx = 0; + *maxIdx = 0; + + // Because we're given the array in prefix sum form, we know the first + // element is 0 + for(int32_t i = 1; i < n; i++) { + SizePair cand = A[i] - min; + if (cand > max) { + max = cand; + *minIdx = currentMinIdx; + *maxIdx = i; + } + if (min > A[i]) { + min = A[i]; + currentMinIdx = i; + } + } + + return max; + } +} // namespace + +nsRect nsRegion::GetLargestRectangle (const nsRect& aContainingRect) const { + nsRect bestRect; + + if (GetNumRects() <= 1) { + bestRect = GetBounds(); + return bestRect; + } + + AxisPartition xaxis, yaxis; + + // Step 1: Calculate the grid lines + for (auto iter = RectIter(); !iter.Done(); iter.Next()) { + const nsRect& rect = iter.Get(); + xaxis.InsertCoord(rect.x); + xaxis.InsertCoord(rect.XMost()); + yaxis.InsertCoord(rect.y); + yaxis.InsertCoord(rect.YMost()); + } + if (!aContainingRect.IsEmpty()) { + xaxis.InsertCoord(aContainingRect.x); + xaxis.InsertCoord(aContainingRect.XMost()); + yaxis.InsertCoord(aContainingRect.y); + yaxis.InsertCoord(aContainingRect.YMost()); + } + + // Step 2: Fill out the grid with the areas + // Note: due to the ordering of rectangles in the region, it is not always + // possible to combine steps 2 and 3 so we don't try to be clever. + int32_t matrixHeight = yaxis.GetNumStops() - 1; + int32_t matrixWidth = xaxis.GetNumStops() - 1; + int32_t matrixSize = matrixHeight * matrixWidth; + nsTArray areas(matrixSize); + areas.SetLength(matrixSize); + + for (auto iter = RectIter(); !iter.Done(); iter.Next()) { + const nsRect& rect = iter.Get(); + int32_t xstart = xaxis.IndexOf(rect.x); + int32_t xend = xaxis.IndexOf(rect.XMost()); + int32_t y = yaxis.IndexOf(rect.y); + int32_t yend = yaxis.IndexOf(rect.YMost()); + + for (; y < yend; y++) { + nscoord height = yaxis.StopSize(y); + for (int32_t x = xstart; x < xend; x++) { + nscoord width = xaxis.StopSize(x); + int64_t size = width*int64_t(height); + if (rect.Intersects(aContainingRect)) { + areas[y*matrixWidth+x].mSizeContainingRect = size; + } + areas[y*matrixWidth+x].mSize = size; + } + } + } + + // Step 3: Find the maximum submatrix sum that does not contain a rectangle + { + // First get the prefix sum array + int32_t m = matrixHeight + 1; + int32_t n = matrixWidth + 1; + nsTArray pareas(m*n); + pareas.SetLength(m*n); + for (int32_t y = 1; y < m; y++) { + for (int32_t x = 1; x < n; x++) { + SizePair area = areas[(y-1)*matrixWidth+x-1]; + if (!area.mSize) { + area = SizePair::VeryLargeNegative(); + } + area = area + pareas[ y*n+x-1] + + pareas[(y-1)*n+x ] + - pareas[(y-1)*n+x-1]; + pareas[y*n+x] = area; + } + } + + // No longer need the grid + areas.SetLength(0); + + SizePair bestArea; + struct { + int32_t left, top, right, bottom; + } bestRectIndices = { 0, 0, 0, 0 }; + for (int32_t m1 = 0; m1 < m; m1++) { + for (int32_t m2 = m1+1; m2 < m; m2++) { + nsTArray B; + B.SetLength(n); + for (int32_t i = 0; i < n; i++) { + B[i] = pareas[m2*n+i] - pareas[m1*n+i]; + } + int32_t minIdx, maxIdx; + SizePair area = MaxSum1D(B, n, &minIdx, &maxIdx); + if (area > bestArea) { + bestRectIndices.left = minIdx; + bestRectIndices.top = m1; + bestRectIndices.right = maxIdx; + bestRectIndices.bottom = m2; + bestArea = area; + } + } + } + + bestRect.MoveTo(xaxis.StopAt(bestRectIndices.left), + yaxis.StopAt(bestRectIndices.top)); + bestRect.SizeTo(xaxis.StopAt(bestRectIndices.right) - bestRect.x, + yaxis.StopAt(bestRectIndices.bottom) - bestRect.y); + } + + return bestRect; +} + +std::ostream& operator<<(std::ostream& stream, const nsRegion& m) { + stream << "["; + + int n; + pixman_box32_t *boxes = pixman_region32_rectangles(const_cast(&m.mImpl), &n); + for (int i=0; i