1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7 #include "TiledRegion.h"
8
9 #include <algorithm>
10
11 #include "mozilla/fallible.h"
12
13 namespace mozilla {
14 namespace gfx {
15
16 static const int32_t kTileSize = 256;
17 static const size_t kMaxTiles = 1000;
18
19 /**
20 * TiledRegionImpl stores an array of non-empty rectangles (pixman_box32_ts) to
21 * represent the region. Each rectangle is contained in a single tile;
22 * rectangles never cross tile boundaries. The rectangles are sorted by their
23 * tile's origin in top-to-bottom, left-to-right order.
24 * (Note that this can mean that a rectangle r1 can come before another
25 * rectangle r2 even if r2.y1 < r1.y1, as long as the two rects are in the same
26 * row of tiles and r1.x1 < r2.x1.)
27 * Empty tiles take up no space in the array - there is no rectangle stored for
28 * them. As a result, any algorithm that needs to deal with empty tiles will
29 * iterate through the mRects array and compare the positions of two
30 * consecutive rects to figure out whether there are any empty tiles between
31 * them.
32 */
33
34 static pixman_box32_t
IntersectionOfNonEmptyBoxes(const pixman_box32_t & aBox1,const pixman_box32_t & aBox2)35 IntersectionOfNonEmptyBoxes(const pixman_box32_t& aBox1,
36 const pixman_box32_t& aBox2)
37 {
38 return pixman_box32_t {
39 std::max(aBox1.x1, aBox2.x1),
40 std::max(aBox1.y1, aBox2.y1),
41 std::min(aBox1.x2, aBox2.x2),
42 std::min(aBox1.y2, aBox2.y2)
43 };
44 }
45
46 // A TileIterator points to a specific tile inside a certain tile range, or to
47 // the end of the tile range. Advancing a TileIterator will move to the next
48 // tile inside the range (or to the range end). The next tile is either the
49 // tile to the right of the current one, or the first tile of the next tile
50 // row if the current tile is already the last tile in the row.
51 class TileIterator {
52 public:
TileIterator(const pixman_box32_t & aTileBounds,const IntPoint & aPosition)53 TileIterator(const pixman_box32_t& aTileBounds, const IntPoint& aPosition)
54 : mTileBounds(aTileBounds)
55 , mPos(aPosition)
56 {}
57
operator !=(const TileIterator & aOther)58 bool operator!=(const TileIterator& aOther) { return mPos != aOther.mPos; }
operator ==(const TileIterator & aOther)59 bool operator==(const TileIterator& aOther) { return mPos == aOther.mPos; }
60
operator *() const61 IntPoint operator*() const { return mPos; }
62
operator ++()63 const TileIterator& operator++() {
64 mPos.x += kTileSize;
65 if (mPos.x >= mTileBounds.x2) {
66 mPos.x = mTileBounds.x1;
67 mPos.y += kTileSize;
68 }
69 return *this;
70 }
71
operator =(const IntPoint & aPosition)72 TileIterator& operator=(const IntPoint& aPosition)
73 {
74 mPos = aPosition;
75 return *this;
76 }
77
IsBeforeTileContainingPoint(const IntPoint & aPoint) const78 bool IsBeforeTileContainingPoint(const IntPoint& aPoint) const
79 {
80 return (mPos.y + kTileSize) <= aPoint.y ||
81 (mPos.y <= aPoint.y && (mPos.x + kTileSize) <= aPoint.x);
82 }
83
IsAtTileContainingPoint(const IntPoint & aPoint) const84 bool IsAtTileContainingPoint(const IntPoint& aPoint) const
85 {
86 return mPos.y <= aPoint.y && aPoint.y < (mPos.y + kTileSize) &&
87 mPos.x <= aPoint.x && aPoint.x < (mPos.x + kTileSize);
88
89 }
90
IntersectionWith(const pixman_box32_t & aRect) const91 pixman_box32_t IntersectionWith(const pixman_box32_t& aRect) const
92 {
93 pixman_box32_t tile = { mPos.x, mPos.y,
94 mPos.x + kTileSize, mPos.y + kTileSize };
95 return IntersectionOfNonEmptyBoxes(tile, aRect);
96 }
97
98 private:
99 const pixman_box32_t& mTileBounds;
100 IntPoint mPos;
101 };
102
103 // A TileRange describes a range of tiles contained inside a certain tile
104 // bounds (which is a rectangle that includes all tiles that you're
105 // interested in). The tile range can start and end at any point inside a
106 // tile row.
107 // The tile range end is described by the tile that starts at the bottom
108 // left corner of the tile bounds, i.e. the first tile under the tile
109 // bounds.
110 class TileRange {
111 public:
112 // aTileBounds, aStart and aEnd need to be aligned with the tile grid.
TileRange(const pixman_box32_t & aTileBounds,const IntPoint & aStart,const IntPoint & aEnd)113 TileRange(const pixman_box32_t& aTileBounds,
114 const IntPoint& aStart, const IntPoint& aEnd)
115 : mTileBounds(aTileBounds)
116 , mStart(aStart)
117 , mEnd(aEnd)
118 {}
119 // aTileBounds needs to be aligned with the tile grid.
TileRange(const pixman_box32_t & aTileBounds)120 explicit TileRange(const pixman_box32_t& aTileBounds)
121 : mTileBounds(aTileBounds)
122 , mStart(mTileBounds.x1, mTileBounds.y1)
123 , mEnd(mTileBounds.x1, mTileBounds.y2)
124 {}
125
Begin() const126 TileIterator Begin() const { return TileIterator(mTileBounds, mStart); }
End() const127 TileIterator End() const { return TileIterator(mTileBounds, mEnd); }
128
129 // The number of tiles in this tile range.
Length() const130 size_t Length() const
131 {
132 if (mEnd.y == mStart.y) {
133 return (mEnd.x - mStart.x) / kTileSize;
134 }
135 int64_t numberOfFullRows = (((int64_t)mEnd.y - (int64_t)mStart.y) / kTileSize) - 1;
136 int64_t tilesInFirstRow = ((int64_t)mTileBounds.x2 - (int64_t)mStart.x) / kTileSize;
137 int64_t tilesInLastRow = ((int64_t)mEnd.x - (int64_t)mTileBounds.x1) / kTileSize;
138 int64_t tilesInFullRow = ((int64_t)mTileBounds.x2 - (int64_t)mTileBounds.x1) / kTileSize;
139 int64_t total = tilesInFirstRow + (tilesInFullRow * numberOfFullRows) + tilesInLastRow;
140 MOZ_ASSERT(total > 0);
141 // The total may be larger than what fits in a size_t, so clamp it to
142 // SIZE_MAX in that case.
143 return ((uint64_t)total > (uint64_t)SIZE_MAX) ? SIZE_MAX : (size_t)total;
144 }
145
146 // If aTileOrigin does not describe a tile inside our tile bounds, move it
147 // to the next tile that you'd encounter by "advancing" a tile iterator
148 // inside these tile bounds. If aTileOrigin is after the last tile inside
149 // our tile bounds, move it to the range end tile.
150 // The result of this method is a valid end tile for a tile range with our
151 // tile bounds.
MoveIntoBounds(const IntPoint & aTileOrigin) const152 IntPoint MoveIntoBounds(const IntPoint& aTileOrigin) const
153 {
154 IntPoint p = aTileOrigin;
155 if (p.x < mTileBounds.x1) {
156 p.x = mTileBounds.x1;
157 } else if (p.x >= mTileBounds.x2) {
158 p.x = mTileBounds.x1;
159 p.y += kTileSize;
160 }
161 if (p.y < mTileBounds.y1) {
162 p.y = mTileBounds.y1;
163 p.x = mTileBounds.x1;
164 } else if (p.y >= mTileBounds.y2) {
165 // There's only one valid state after the end of the tile range, and that's
166 // the bottom left point of the tile bounds.
167 p.x = mTileBounds.x1;
168 p.y = mTileBounds.y2;
169 }
170 return p;
171 }
172
173 private:
174 const pixman_box32_t& mTileBounds;
175 const IntPoint mStart;
176 const IntPoint mEnd;
177 };
178
179 static IntPoint
TileContainingPoint(const IntPoint & aPoint)180 TileContainingPoint(const IntPoint& aPoint)
181 {
182 return IntPoint(RoundDownToMultiple(aPoint.x, kTileSize),
183 RoundDownToMultiple(aPoint.y, kTileSize));
184 }
185
186 enum class IterationAction : uint8_t {
187 CONTINUE,
188 STOP
189 };
190
191 enum class IterationEndReason : uint8_t {
192 NOT_STOPPED,
193 STOPPED
194 };
195
196 template<
197 typename HandleEmptyTilesFunction,
198 typename HandleNonEmptyTileFunction,
199 typename RectArrayT>
ProcessIntersectedTiles(const pixman_box32_t & aRect,RectArrayT & aRectArray,HandleEmptyTilesFunction aHandleEmptyTiles,HandleNonEmptyTileFunction aHandleNonEmptyTile)200 IterationEndReason ProcessIntersectedTiles(const pixman_box32_t& aRect,
201 RectArrayT& aRectArray,
202 HandleEmptyTilesFunction aHandleEmptyTiles,
203 HandleNonEmptyTileFunction aHandleNonEmptyTile)
204 {
205 pixman_box32_t tileBounds = {
206 RoundDownToMultiple(aRect.x1, kTileSize),
207 RoundDownToMultiple(aRect.y1, kTileSize),
208 RoundUpToMultiple(aRect.x2, kTileSize),
209 RoundUpToMultiple(aRect.y2, kTileSize)
210 };
211 if (tileBounds.x2 < tileBounds.x1 || tileBounds.y2 < tileBounds.y1) {
212 // RoundUpToMultiple probably overflowed. Bail out.
213 return IterationEndReason::STOPPED;
214 }
215
216 TileRange tileRange(tileBounds);
217 TileIterator rangeEnd = tileRange.End();
218
219 // tileIterator points to the next tile in tileRange, or to rangeEnd if we're
220 // done.
221 TileIterator tileIterator = tileRange.Begin();
222
223 // We iterate over the rectangle array. Depending on the position of the
224 // rectangle we encounter, we may need to advance tileIterator by zero, one,
225 // or more tiles:
226 // - Zero if the rectangle we encountered is outside the tiles that
227 // intersect aRect.
228 // - One if the rectangle is in the exact tile that we're interested in next
229 // (i.e. the tile that tileIterator points at).
230 // - More than one if the encountered rectangle is in a tile that's further
231 // to the right or to the bottom than tileIterator. In that case there is
232 // at least one empty tile between the last rectangle we encountered and
233 // the current one.
234 for (size_t i = 0; i < aRectArray.Length() && tileIterator != rangeEnd; i++) {
235 MOZ_ASSERT(aRectArray[i].x1 < aRectArray[i].x2 && aRectArray[i].y1 < aRectArray[i].y2, "empty rect");
236 IntPoint rectOrigin(aRectArray[i].x1, aRectArray[i].y1);
237 if (tileIterator.IsBeforeTileContainingPoint(rectOrigin)) {
238 IntPoint tileOrigin = TileContainingPoint(rectOrigin);
239 IntPoint afterEmptyTiles = tileRange.MoveIntoBounds(tileOrigin);
240 TileRange emptyTiles(tileBounds, *tileIterator, afterEmptyTiles);
241 if (aHandleEmptyTiles(aRectArray, i, emptyTiles) == IterationAction::STOP) {
242 return IterationEndReason::STOPPED;
243 }
244 tileIterator = afterEmptyTiles;
245 if (tileIterator == rangeEnd) {
246 return IterationEndReason::NOT_STOPPED;
247 }
248 }
249 if (tileIterator.IsAtTileContainingPoint(rectOrigin)) {
250 pixman_box32_t rectIntersection = tileIterator.IntersectionWith(aRect);
251 if (aHandleNonEmptyTile(aRectArray, i, rectIntersection) == IterationAction::STOP) {
252 return IterationEndReason::STOPPED;
253 }
254 ++tileIterator;
255 }
256 }
257
258 if (tileIterator != rangeEnd) {
259 // We've looked at all of our existing rectangles but haven't covered all
260 // of the tiles that we're interested in yet. So we need to deal with the
261 // remaining tiles now.
262 size_t endIndex = aRectArray.Length();
263 TileRange emptyTiles(tileBounds, *tileIterator, *rangeEnd);
264 if (aHandleEmptyTiles(aRectArray, endIndex, emptyTiles) == IterationAction::STOP) {
265 return IterationEndReason::STOPPED;
266 }
267 }
268 return IterationEndReason::NOT_STOPPED;
269 }
270
271 static pixman_box32_t
UnionBoundsOfNonEmptyBoxes(const pixman_box32_t & aBox1,const pixman_box32_t & aBox2)272 UnionBoundsOfNonEmptyBoxes(const pixman_box32_t& aBox1,
273 const pixman_box32_t& aBox2)
274 {
275 return { std::min(aBox1.x1, aBox2.x1),
276 std::min(aBox1.y1, aBox2.y1),
277 std::max(aBox1.x2, aBox2.x2),
278 std::max(aBox1.y2, aBox2.y2) };
279 }
280
281 // Returns true when adding the rectangle was successful, and false if
282 // allocation failed.
283 // When this returns false, our internal state might not be consistent and we
284 // need to be cleared.
285 bool
AddRect(const pixman_box32_t & aRect)286 TiledRegionImpl::AddRect(const pixman_box32_t& aRect)
287 {
288 // We are adding a rectangle that can span multiple tiles.
289 // For each empty tile that aRect intersects, we need to add the intersection
290 // of aRect with that tile to mRects, respecting the order of mRects.
291 // For each tile that already has a rectangle, we need to enlarge that
292 // existing rectangle to include the intersection of aRect with the tile.
293 return ProcessIntersectedTiles(aRect, mRects,
294 [&aRect](nsTArray<pixman_box32_t>& rects, size_t& rectIndex, TileRange emptyTiles) {
295 CheckedInt<size_t> newLength(rects.Length());
296 newLength += emptyTiles.Length();
297 if (!newLength.isValid() || newLength.value() >= kMaxTiles ||
298 !rects.InsertElementsAt(rectIndex, emptyTiles.Length(), fallible)) {
299 return IterationAction::STOP;
300 }
301 for (TileIterator tileIt = emptyTiles.Begin();
302 tileIt != emptyTiles.End();
303 ++tileIt, ++rectIndex) {
304 rects[rectIndex] = tileIt.IntersectionWith(aRect);
305 }
306 return IterationAction::CONTINUE;
307 },
308 [](nsTArray<pixman_box32_t>& rects, size_t rectIndex, const pixman_box32_t& rectIntersectionWithTile) {
309 rects[rectIndex] =
310 UnionBoundsOfNonEmptyBoxes(rects[rectIndex], rectIntersectionWithTile);
311 return IterationAction::CONTINUE;
312 }) == IterationEndReason::NOT_STOPPED;
313 }
314
315 static bool
NonEmptyBoxesIntersect(const pixman_box32_t & aBox1,const pixman_box32_t & aBox2)316 NonEmptyBoxesIntersect(const pixman_box32_t& aBox1, const pixman_box32_t& aBox2)
317 {
318 return aBox1.x1 < aBox2.x2 && aBox2.x1 < aBox1.x2 &&
319 aBox1.y1 < aBox2.y2 && aBox2.y1 < aBox1.y2;
320 }
321
322 bool
Intersects(const pixman_box32_t & aRect) const323 TiledRegionImpl::Intersects(const pixman_box32_t& aRect) const
324 {
325 // aRect intersects this region if it intersects any of our rectangles.
326 return ProcessIntersectedTiles(aRect, mRects,
327 [](const nsTArray<pixman_box32_t>& rects, size_t& rectIndex, TileRange emptyTiles) {
328 // Ignore empty tiles and keep on iterating.
329 return IterationAction::CONTINUE;
330 },
331 [](const nsTArray<pixman_box32_t>& rects, size_t rectIndex, const pixman_box32_t& rectIntersectionWithTile) {
332 if (NonEmptyBoxesIntersect(rects[rectIndex], rectIntersectionWithTile)) {
333 // Found an intersecting rectangle, so aRect intersects this region.
334 return IterationAction::STOP;
335 }
336 return IterationAction::CONTINUE;
337 }) == IterationEndReason::STOPPED;
338 }
339
340 static bool
NonEmptyBoxContainsNonEmptyBox(const pixman_box32_t & aBox1,const pixman_box32_t & aBox2)341 NonEmptyBoxContainsNonEmptyBox(const pixman_box32_t& aBox1, const pixman_box32_t& aBox2)
342 {
343 return aBox1.x1 <= aBox2.x1 && aBox2.x2 <= aBox1.x2 &&
344 aBox1.y1 <= aBox2.y1 && aBox2.y2 <= aBox1.y2;
345 }
346
347 bool
Contains(const pixman_box32_t & aRect) const348 TiledRegionImpl::Contains(const pixman_box32_t& aRect) const
349 {
350 // aRect is contained in this region if aRect does not intersect any empty
351 // tiles and, for each non-empty tile, if the intersection of aRect with that
352 // tile is contained in the existing rectangle we have in that tile.
353 return ProcessIntersectedTiles(aRect, mRects,
354 [](const nsTArray<pixman_box32_t>& rects, size_t& rectIndex, TileRange emptyTiles) {
355 // Found an empty tile that intersects aRect, so aRect is not contained
356 // in this region.
357 return IterationAction::STOP;
358 },
359 [](const nsTArray<pixman_box32_t>& rects, size_t rectIndex, const pixman_box32_t& rectIntersectionWithTile) {
360 if (!NonEmptyBoxContainsNonEmptyBox(rects[rectIndex], rectIntersectionWithTile)) {
361 // Our existing rectangle in this tile does not cover the part of aRect that
362 // intersects this tile, so aRect is not contained in this region.
363 return IterationAction::STOP;
364 }
365 return IterationAction::CONTINUE;
366 }) == IterationEndReason::NOT_STOPPED;
367 }
368
369 } // namespace gfx
370 } // namespace mozilla
371