1 /* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
4
5
6 #include "nsRegion.h"
7 #include "nsTArray.h"
8 #include "gfxUtils.h"
9 #include "mozilla/ToString.h"
10
Contains(const nsRegion & aRgn) const11 bool nsRegion::Contains(const nsRegion& aRgn) const
12 {
13 // XXX this could be made faster by iterating over
14 // both regions at the same time some how
15 for (auto iter = aRgn.RectIter(); !iter.Done(); iter.Next()) {
16 if (!Contains(iter.Get())) {
17 return false;
18 }
19 }
20 return true;
21 }
22
Intersects(const nsRect & aRect) const23 bool nsRegion::Intersects(const nsRect& aRect) const
24 {
25 // XXX this could be made faster by using pixman_region32_contains_rect
26 for (auto iter = RectIter(); !iter.Done(); iter.Next()) {
27 if (iter.Get().Intersects(aRect)) {
28 return true;
29 }
30 }
31 return false;
32 }
33
Inflate(const nsMargin & aMargin)34 void nsRegion::Inflate(const nsMargin& aMargin)
35 {
36 int n;
37 pixman_box32_t *boxes = pixman_region32_rectangles(&mImpl, &n);
38 for (int i=0; i<n; i++) {
39 nsRect rect = BoxToRect(boxes[i]);
40 rect.Inflate(aMargin);
41 boxes[i] = RectToBox(rect);
42 }
43
44 pixman_region32_t region;
45 // This will union all of the rectangles and runs in about O(n lg(n))
46 pixman_region32_init_rects(®ion, boxes, n);
47
48 pixman_region32_fini(&mImpl);
49 mImpl = region;
50 }
51
SimplifyOutward(uint32_t aMaxRects)52 void nsRegion::SimplifyOutward (uint32_t aMaxRects)
53 {
54 MOZ_ASSERT(aMaxRects >= 1, "Invalid max rect count");
55
56 if (GetNumRects() <= aMaxRects)
57 return;
58
59 pixman_box32_t *boxes;
60 int n;
61 boxes = pixman_region32_rectangles(&mImpl, &n);
62
63 // Try combining rects in horizontal bands into a single rect
64 int dest = 0;
65 for (int src = 1; src < n; src++)
66 {
67 // The goal here is to try to keep groups of rectangles that are vertically
68 // discontiguous as separate rectangles in the final region. This is
69 // simple and fast to implement and page contents tend to vary more
70 // vertically than horizontally (which is why our rectangles are stored
71 // sorted by y-coordinate, too).
72 //
73 // Note: if boxes share y1 because of the canonical representation they
74 // will share y2
75 while ((src < (n)) && boxes[dest].y1 == boxes[src].y1) {
76 // merge box[i] and box[i+1]
77 boxes[dest].x2 = boxes[src].x2;
78 src++;
79 }
80 if (src < n) {
81 dest++;
82 boxes[dest] = boxes[src];
83 }
84 }
85
86 uint32_t reducedCount = dest+1;
87 // pixman has a special representation for
88 // regions of 1 rectangle. So just use the
89 // bounds in that case
90 if (reducedCount > 1 && reducedCount <= aMaxRects) {
91 // reach into pixman and lower the number
92 // of rects stored in data.
93 mImpl.data->numRects = reducedCount;
94 } else {
95 *this = GetBounds();
96 }
97 }
98
99 // compute the covered area difference between two rows.
100 // by iterating over both rows simultaneously and adding up
101 // the additional increase in area caused by extending each
102 // of the rectangles to the combined height of both rows
ComputeMergedAreaIncrease(pixman_box32_t * topRects,pixman_box32_t * topRectsEnd,pixman_box32_t * bottomRects,pixman_box32_t * bottomRectsEnd)103 static uint32_t ComputeMergedAreaIncrease(pixman_box32_t *topRects,
104 pixman_box32_t *topRectsEnd,
105 pixman_box32_t *bottomRects,
106 pixman_box32_t *bottomRectsEnd)
107 {
108 uint32_t totalArea = 0;
109 struct pt {
110 int32_t x, y;
111 };
112
113
114 pt *i = (pt*)topRects;
115 pt *end_i = (pt*)topRectsEnd;
116 pt *j = (pt*)bottomRects;
117 pt *end_j = (pt*)bottomRectsEnd;
118 bool top = false;
119 bool bottom = false;
120
121 int cur_x = i->x;
122 bool top_next = top;
123 bool bottom_next = bottom;
124 //XXX: we could probably simplify this condition and perhaps move it into the loop below
125 if (j->x < cur_x) {
126 cur_x = j->x;
127 j++;
128 bottom_next = !bottom;
129 } else if (j->x == cur_x) {
130 i++;
131 top_next = !top;
132 bottom_next = !bottom;
133 j++;
134 } else {
135 top_next = !top;
136 i++;
137 }
138
139 int topRectsHeight = topRects->y2 - topRects->y1;
140 int bottomRectsHeight = bottomRects->y2 - bottomRects->y1;
141 int inbetweenHeight = bottomRects->y1 - topRects->y2;
142 int width = cur_x;
143 // top and bottom are the in-status to the left of cur_x
144 do {
145 if (top && !bottom) {
146 totalArea += (inbetweenHeight+bottomRectsHeight)*width;
147 } else if (bottom && !top) {
148 totalArea += (inbetweenHeight+topRectsHeight)*width;
149 } else if (bottom && top) {
150 totalArea += (inbetweenHeight)*width;
151 }
152 top = top_next;
153 bottom = bottom_next;
154 // find the next edge
155 if (i->x < j->x) {
156 top_next = !top;
157 width = i->x - cur_x;
158 cur_x = i->x;
159 i++;
160 } else if (j->x < i->x) {
161 bottom_next = !bottom;
162 width = j->x - cur_x;
163 cur_x = j->x;
164 j++;
165 } else { // i->x == j->x
166 top_next = !top;
167 bottom_next = !bottom;
168 width = i->x - cur_x;
169 cur_x = i->x;
170 i++;
171 j++;
172 }
173 } while (i < end_i && j < end_j);
174
175 // handle any remaining rects
176 while (i < end_i) {
177 width = i->x - cur_x;
178 cur_x = i->x;
179 i++;
180 if (top)
181 totalArea += (inbetweenHeight+bottomRectsHeight)*width;
182 top = !top;
183 }
184
185 while (j < end_j) {
186 width = j->x - cur_x;
187 cur_x = j->x;
188 j++;
189 if (bottom)
190 totalArea += (inbetweenHeight+topRectsHeight)*width;
191 bottom = !bottom;
192 }
193 return totalArea;
194 }
195
196 static pixman_box32_t *
CopyRow(pixman_box32_t * dest_it,pixman_box32_t * src_start,pixman_box32_t * src_end)197 CopyRow(pixman_box32_t *dest_it, pixman_box32_t *src_start, pixman_box32_t *src_end)
198 {
199 // XXX: std::copy
200 pixman_box32_t *src_it = src_start;
201 while (src_it < src_end) {
202 *dest_it++ = *src_it++;
203 }
204 return dest_it;
205 }
206
207
208 #define WRITE_RECT(x1, x2, y1, y2) \
209 do { \
210 tmpRect->x1 = x1; \
211 tmpRect->x2 = x2; \
212 tmpRect->y1 = y1; \
213 tmpRect->y2 = y2; \
214 tmpRect++; \
215 } while (0)
216
217 /* If 'r' overlaps the current rect, then expand the current rect to include
218 * it. Otherwise write the current rect out to tmpRect, and set r as the
219 * updated current rect. */
220 #define MERGE_RECT(r) \
221 do { \
222 if (r->x1 <= x2) { \
223 if (x2 < r->x2) \
224 x2 = r->x2; \
225 } else { \
226 WRITE_RECT(x1, x2, y1, y2); \
227 x1 = r->x1; \
228 x2 = r->x2; \
229 } \
230 r++; \
231 } while (0)
232
233
234 /* Can we merge two sets of rects without extra space?
235 * Yes, but not easily. We can even do it stably
236 * but we don't need that property.
237 *
238 * This is written in the style of pixman_region_union_o */
239 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)240 MergeRects(pixman_box32_t *r1,
241 pixman_box32_t *r1_end,
242 pixman_box32_t *r2,
243 pixman_box32_t *r2_end,
244 pixman_box32_t *tmpRect)
245 {
246 /* This routine works by maintaining the current
247 * rectangle in x1,x2,y1,y2 and either merging
248 * in the left most rectangle if it overlaps or
249 * outputing the current rectangle and setting
250 * it to the the left most one */
251 const int y1 = r1->y1;
252 const int y2 = r2->y2;
253 int x1;
254 int x2;
255
256 /* Find the left-most edge */
257 if (r1->x1 < r2->x1) {
258 x1 = r1->x1;
259 x2 = r1->x2;
260 r1++;
261 } else {
262 x1 = r2->x1;
263 x2 = r2->x2;
264 r2++;
265 }
266
267 while (r1 != r1_end && r2 != r2_end) {
268 /* Find and merge the left-most rectangle */
269 if (r1->x1 < r2->x1)
270 MERGE_RECT (r1);
271 else
272 MERGE_RECT (r2);
273 }
274
275 /* Finish up any left overs */
276 if (r1 != r1_end) {
277 do {
278 MERGE_RECT (r1);
279 } while (r1 != r1_end);
280 } else if (r2 != r2_end) {
281 do {
282 MERGE_RECT(r2);
283 } while (r2 != r2_end);
284 }
285
286 /* Finish up the last rectangle */
287 WRITE_RECT(x1, x2, y1, y2);
288
289 return tmpRect;
290 }
291
SimplifyOutwardByArea(uint32_t aThreshold)292 void nsRegion::SimplifyOutwardByArea(uint32_t aThreshold)
293 {
294
295 pixman_box32_t *boxes;
296 int n;
297 boxes = pixman_region32_rectangles(&mImpl, &n);
298
299 // if we have no rectangles then we're done
300 if (!n)
301 return;
302
303 pixman_box32_t *end = boxes + n;
304 pixman_box32_t *topRectsEnd = boxes+1;
305 pixman_box32_t *topRects = boxes;
306
307 // we need some temporary storage for merging both rows of rectangles
308 AutoTArray<pixman_box32_t, 10> tmpStorage;
309 tmpStorage.SetCapacity(n);
310 pixman_box32_t *tmpRect = tmpStorage.Elements();
311
312 pixman_box32_t *destRect = boxes;
313 pixman_box32_t *rect = tmpRect;
314 // find the end of the first span of rectangles
315 while (topRectsEnd < end && topRectsEnd->y1 == topRects->y1) {
316 topRectsEnd++;
317 }
318
319 // if we only have one row we are done
320 if (topRectsEnd == end)
321 return;
322
323 pixman_box32_t *bottomRects = topRectsEnd;
324 pixman_box32_t *bottomRectsEnd = bottomRects+1;
325 do {
326 // find the end of the bottom span of rectangles
327 while (bottomRectsEnd < end && bottomRectsEnd->y1 == bottomRects->y1) {
328 bottomRectsEnd++;
329 }
330 uint32_t totalArea = ComputeMergedAreaIncrease(topRects, topRectsEnd,
331 bottomRects, bottomRectsEnd);
332
333 if (totalArea <= aThreshold) {
334 // merge the rects into tmpRect
335 rect = MergeRects(topRects, topRectsEnd, bottomRects, bottomRectsEnd, tmpRect);
336
337 // set topRects to where the newly merged rects will be so that we use them
338 // as our next set of topRects
339 topRects = destRect;
340 // copy the merged rects back into the destination
341 topRectsEnd = CopyRow(destRect, tmpRect, rect);
342 } else {
343 // copy the unmerged rects
344 destRect = CopyRow(destRect, topRects, topRectsEnd);
345
346 topRects = bottomRects;
347 topRectsEnd = bottomRectsEnd;
348 if (bottomRectsEnd == end) {
349 // copy the last row when we are done
350 topRectsEnd = CopyRow(destRect, topRects, topRectsEnd);
351 }
352 }
353 bottomRects = bottomRectsEnd;
354 } while (bottomRectsEnd != end);
355
356
357 uint32_t reducedCount = topRectsEnd - pixman_region32_rectangles(&this->mImpl, &n);
358 // pixman has a special representation for
359 // regions of 1 rectangle. So just use the
360 // bounds in that case
361 if (reducedCount > 1) {
362 // reach into pixman and lower the number
363 // of rects stored in data.
364 this->mImpl.data->numRects = reducedCount;
365 } else {
366 *this = GetBounds();
367 }
368 }
369
370
371 typedef void (*visit_fn)(void *closure, VisitSide side, int x1, int y1, int x2, int y2);
372
VisitNextEdgeBetweenRect(visit_fn visit,void * closure,VisitSide side,pixman_box32_t * & r1,pixman_box32_t * & r2,const int y,int & x1)373 static bool VisitNextEdgeBetweenRect(visit_fn visit, void *closure, VisitSide side,
374 pixman_box32_t *&r1, pixman_box32_t *&r2, const int y, int &x1)
375 {
376 // check for overlap
377 if (r1->x2 >= r2->x1) {
378 MOZ_ASSERT(r2->x1 >= x1);
379 visit(closure, side, x1, y, r2->x1, y);
380
381 // find the rect that ends first or always drop the one that comes first?
382 if (r1->x2 < r2->x2) {
383 x1 = r1->x2;
384 r1++;
385 } else {
386 x1 = r2->x2;
387 r2++;
388 }
389 return true;
390 } else {
391 MOZ_ASSERT(r1->x2 < r2->x2);
392 // we handle the corners by just extending the top and bottom edges
393 visit(closure, side, x1, y, r1->x2+1, y);
394 r1++;
395 // we assign x1 because we can assume that x1 <= r2->x1 - 1
396 // However the caller may know better and if so, may update
397 // x1 to r1->x1
398 x1 = r2->x1 - 1;
399 return false;
400 }
401 }
402
403 //XXX: if we need to this can compute the end of the row
404 static void
VisitSides(visit_fn visit,void * closure,pixman_box32_t * r,pixman_box32_t * r_end)405 VisitSides(visit_fn visit, void *closure, pixman_box32_t *r, pixman_box32_t *r_end)
406 {
407 // XXX: we can drop LEFT/RIGHT and just use the orientation
408 // of the line if it makes sense
409 while (r != r_end) {
410 visit(closure, VisitSide::LEFT, r->x1, r->y1, r->x1, r->y2);
411 visit(closure, VisitSide::RIGHT, r->x2, r->y1, r->x2, r->y2);
412 r++;
413 }
414 }
415
416 static void
VisitAbove(visit_fn visit,void * closure,pixman_box32_t * r,pixman_box32_t * r_end)417 VisitAbove(visit_fn visit, void *closure, pixman_box32_t *r, pixman_box32_t *r_end)
418 {
419 while (r != r_end) {
420 visit(closure, VisitSide::TOP, r->x1-1, r->y1, r->x2+1, r->y1);
421 r++;
422 }
423 }
424
425 static void
VisitBelow(visit_fn visit,void * closure,pixman_box32_t * r,pixman_box32_t * r_end)426 VisitBelow(visit_fn visit, void *closure, pixman_box32_t *r, pixman_box32_t *r_end)
427 {
428 while (r != r_end) {
429 visit(closure, VisitSide::BOTTOM, r->x1-1, r->y2, r->x2+1, r->y2);
430 r++;
431 }
432 }
433
434 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)435 VisitInbetween(visit_fn visit, void *closure, pixman_box32_t *r1,
436 pixman_box32_t *r1_end,
437 pixman_box32_t *r2,
438 pixman_box32_t *r2_end)
439 {
440 const int y = r1->y2;
441 int x1;
442
443 bool overlap = false;
444 while (r1 != r1_end && r2 != r2_end) {
445 if (!overlap) {
446 /* Find the left-most edge */
447 if (r1->x1 < r2->x1) {
448 x1 = r1->x1 - 1;
449 } else {
450 x1 = r2->x1 - 1;
451 }
452 }
453
454 MOZ_ASSERT((x1 >= (r1->x1 - 1)) || (x1 >= (r2->x1 - 1)));
455 if (r1->x1 < r2->x1) {
456 overlap = VisitNextEdgeBetweenRect(visit, closure, VisitSide::BOTTOM, r1, r2, y, x1);
457 } else {
458 overlap = VisitNextEdgeBetweenRect(visit, closure, VisitSide::TOP, r2, r1, y, x1);
459 }
460 }
461
462 /* Finish up which ever row has remaining rects*/
463 if (r1 != r1_end) {
464 // top row
465 do {
466 visit(closure, VisitSide::BOTTOM, x1, y, r1->x2 + 1, y);
467 r1++;
468 if (r1 == r1_end)
469 break;
470 x1 = r1->x1 - 1;
471 } while (true);
472 } else if (r2 != r2_end) {
473 // bottom row
474 do {
475 visit(closure, VisitSide::TOP, x1, y, r2->x2 + 1, y);
476 r2++;
477 if (r2 == r2_end)
478 break;
479 x1 = r2->x1 - 1;
480 } while (true);
481 }
482
483 return 0;
484 }
485
VisitEdges(visit_fn visit,void * closure)486 void nsRegion::VisitEdges (visit_fn visit, void *closure)
487 {
488 pixman_box32_t *boxes;
489 int n;
490 boxes = pixman_region32_rectangles(&mImpl, &n);
491
492 // if we have no rectangles then we're done
493 if (!n)
494 return;
495
496 pixman_box32_t *end = boxes + n;
497 pixman_box32_t *topRectsEnd = boxes + 1;
498 pixman_box32_t *topRects = boxes;
499
500 // find the end of the first span of rectangles
501 while (topRectsEnd < end && topRectsEnd->y1 == topRects->y1) {
502 topRectsEnd++;
503 }
504
505 // In order to properly handle convex corners we always visit the sides first
506 // that way when we visit the corners we can pad using the value from the sides
507 VisitSides(visit, closure, topRects, topRectsEnd);
508
509 VisitAbove(visit, closure, topRects, topRectsEnd);
510
511 pixman_box32_t *bottomRects = topRects;
512 pixman_box32_t *bottomRectsEnd = topRectsEnd;
513 if (topRectsEnd != end) {
514 do {
515 // find the next row of rects
516 bottomRects = topRectsEnd;
517 bottomRectsEnd = topRectsEnd + 1;
518 while (bottomRectsEnd < end && bottomRectsEnd->y1 == bottomRects->y1) {
519 bottomRectsEnd++;
520 }
521
522 VisitSides(visit, closure, bottomRects, bottomRectsEnd);
523
524 if (topRects->y2 == bottomRects->y1) {
525 VisitInbetween(visit, closure, topRects, topRectsEnd,
526 bottomRects, bottomRectsEnd);
527 } else {
528 VisitBelow(visit, closure, topRects, topRectsEnd);
529 VisitAbove(visit, closure, bottomRects, bottomRectsEnd);
530 }
531
532 topRects = bottomRects;
533 topRectsEnd = bottomRectsEnd;
534 } while (bottomRectsEnd != end);
535 }
536
537 // the bottom of the region doesn't touch anything else so we
538 // can always visit it at the end
539 VisitBelow(visit, closure, bottomRects, bottomRectsEnd);
540 }
541
542
SimplifyInward(uint32_t aMaxRects)543 void nsRegion::SimplifyInward (uint32_t aMaxRects)
544 {
545 NS_ASSERTION(aMaxRects >= 1, "Invalid max rect count");
546
547 if (GetNumRects() <= aMaxRects)
548 return;
549
550 SetEmpty();
551 }
552
Area() const553 uint64_t nsRegion::Area () const
554 {
555 uint64_t area = 0;
556 for (auto iter = RectIter(); !iter.Done(); iter.Next()) {
557 const nsRect& rect = iter.Get();
558 area += uint64_t(rect.width) * rect.height;
559 }
560 return area;
561 }
562
ScaleRoundOut(float aXScale,float aYScale)563 nsRegion& nsRegion::ScaleRoundOut (float aXScale, float aYScale)
564 {
565 if (mozilla::gfx::FuzzyEqual(aXScale, 1.0f) &&
566 mozilla::gfx::FuzzyEqual(aYScale, 1.0f)) {
567 return *this;
568 }
569
570 int n;
571 pixman_box32_t *boxes = pixman_region32_rectangles(&mImpl, &n);
572 for (int i=0; i<n; i++) {
573 nsRect rect = BoxToRect(boxes[i]);
574 rect.ScaleRoundOut(aXScale, aYScale);
575 boxes[i] = RectToBox(rect);
576 }
577
578 pixman_region32_t region;
579 // This will union all of the rectangles and runs in about O(n lg(n))
580 pixman_region32_init_rects(®ion, boxes, n);
581
582 pixman_region32_fini(&mImpl);
583 mImpl = region;
584 return *this;
585 }
586
ScaleInverseRoundOut(float aXScale,float aYScale)587 nsRegion& nsRegion::ScaleInverseRoundOut (float aXScale, float aYScale)
588 {
589 int n;
590 pixman_box32_t *boxes = pixman_region32_rectangles(&mImpl, &n);
591 for (int i=0; i<n; i++) {
592 nsRect rect = BoxToRect(boxes[i]);
593 rect.ScaleInverseRoundOut(aXScale, aYScale);
594 boxes[i] = RectToBox(rect);
595 }
596
597 pixman_region32_t region;
598 // This will union all of the rectangles and runs in about O(n lg(n))
599 pixman_region32_init_rects(®ion, boxes, n);
600
601 pixman_region32_fini(&mImpl);
602 mImpl = region;
603 return *this;
604 }
605
606 static mozilla::gfx::IntRect
TransformRect(const mozilla::gfx::IntRect & aRect,const mozilla::gfx::Matrix4x4 & aTransform)607 TransformRect(const mozilla::gfx::IntRect& aRect, const mozilla::gfx::Matrix4x4& aTransform)
608 {
609 if (aRect.IsEmpty()) {
610 return mozilla::gfx::IntRect();
611 }
612
613 mozilla::gfx::RectDouble rect(aRect.x, aRect.y, aRect.width, aRect.height);
614 rect = aTransform.TransformAndClipBounds(rect, mozilla::gfx::RectDouble::MaxIntRect());
615 rect.RoundOut();
616
617 mozilla::gfx::IntRect intRect;
618 if (!gfxUtils::GfxRectToIntRect(ThebesRect(rect), &intRect)) {
619 return mozilla::gfx::IntRect();
620 }
621
622 return intRect;
623 }
624
Transform(const mozilla::gfx::Matrix4x4 & aTransform)625 nsRegion& nsRegion::Transform (const mozilla::gfx::Matrix4x4 &aTransform)
626 {
627 int n;
628 pixman_box32_t *boxes = pixman_region32_rectangles(&mImpl, &n);
629 for (int i=0; i<n; i++) {
630 nsRect rect = BoxToRect(boxes[i]);
631 boxes[i] = RectToBox(nsIntRegion::ToRect(TransformRect(nsIntRegion::FromRect(rect), aTransform)));
632 }
633
634 pixman_region32_t region;
635 // This will union all of the rectangles and runs in about O(n lg(n))
636 pixman_region32_init_rects(®ion, boxes, n);
637
638 pixman_region32_fini(&mImpl);
639 mImpl = region;
640 return *this;
641 }
642
643
ScaleToOtherAppUnitsRoundOut(int32_t aFromAPP,int32_t aToAPP) const644 nsRegion nsRegion::ScaleToOtherAppUnitsRoundOut (int32_t aFromAPP, int32_t aToAPP) const
645 {
646 if (aFromAPP == aToAPP) {
647 return *this;
648 }
649
650 nsRegion region = *this;
651 int n;
652 pixman_box32_t *boxes = pixman_region32_rectangles(®ion.mImpl, &n);
653 for (int i=0; i<n; i++) {
654 nsRect rect = BoxToRect(boxes[i]);
655 rect = rect.ScaleToOtherAppUnitsRoundOut(aFromAPP, aToAPP);
656 boxes[i] = RectToBox(rect);
657 }
658
659 pixman_region32_t pixmanRegion;
660 // This will union all of the rectangles and runs in about O(n lg(n))
661 pixman_region32_init_rects(&pixmanRegion, boxes, n);
662
663 pixman_region32_fini(®ion.mImpl);
664 region.mImpl = pixmanRegion;
665 return region;
666 }
667
ScaleToOtherAppUnitsRoundIn(int32_t aFromAPP,int32_t aToAPP) const668 nsRegion nsRegion::ScaleToOtherAppUnitsRoundIn (int32_t aFromAPP, int32_t aToAPP) const
669 {
670 if (aFromAPP == aToAPP) {
671 return *this;
672 }
673
674 nsRegion region = *this;
675 int n;
676 pixman_box32_t *boxes = pixman_region32_rectangles(®ion.mImpl, &n);
677 for (int i=0; i<n; i++) {
678 nsRect rect = BoxToRect(boxes[i]);
679 rect = rect.ScaleToOtherAppUnitsRoundIn(aFromAPP, aToAPP);
680 boxes[i] = RectToBox(rect);
681 }
682
683 pixman_region32_t pixmanRegion;
684 // This will union all of the rectangles and runs in about O(n lg(n))
685 pixman_region32_init_rects(&pixmanRegion, boxes, n);
686
687 pixman_region32_fini(®ion.mImpl);
688 region.mImpl = pixmanRegion;
689 return region;
690 }
691
ToPixels(nscoord aAppUnitsPerPixel,bool aOutsidePixels) const692 nsIntRegion nsRegion::ToPixels (nscoord aAppUnitsPerPixel, bool aOutsidePixels) const
693 {
694 nsRegion region = *this;
695 int n;
696 pixman_box32_t *boxes = pixman_region32_rectangles(®ion.mImpl, &n);
697 for (int i=0; i<n; i++) {
698 nsRect rect = BoxToRect(boxes[i]);
699 mozilla::gfx::IntRect deviceRect;
700 if (aOutsidePixels)
701 deviceRect = rect.ToOutsidePixels(aAppUnitsPerPixel);
702 else
703 deviceRect = rect.ToNearestPixels(aAppUnitsPerPixel);
704
705 boxes[i] = RectToBox(deviceRect);
706 }
707
708 nsIntRegion intRegion;
709 pixman_region32_fini(&intRegion.mImpl.mImpl);
710 // This will union all of the rectangles and runs in about O(n lg(n))
711 pixman_region32_init_rects(&intRegion.mImpl.mImpl, boxes, n);
712
713 return intRegion;
714 }
715
ToOutsidePixels(nscoord aAppUnitsPerPixel) const716 nsIntRegion nsRegion::ToOutsidePixels (nscoord aAppUnitsPerPixel) const
717 {
718 return ToPixels(aAppUnitsPerPixel, true);
719 }
720
ToNearestPixels(nscoord aAppUnitsPerPixel) const721 nsIntRegion nsRegion::ToNearestPixels (nscoord aAppUnitsPerPixel) const
722 {
723 return ToPixels(aAppUnitsPerPixel, false);
724 }
725
ScaleToNearestPixels(float aScaleX,float aScaleY,nscoord aAppUnitsPerPixel) const726 nsIntRegion nsRegion::ScaleToNearestPixels (float aScaleX, float aScaleY,
727 nscoord aAppUnitsPerPixel) const
728 {
729 nsIntRegion result;
730 for (auto iter = RectIter(); !iter.Done(); iter.Next()) {
731 mozilla::gfx::IntRect deviceRect =
732 iter.Get().ScaleToNearestPixels(aScaleX, aScaleY, aAppUnitsPerPixel);
733 result.Or(result, deviceRect);
734 }
735 return result;
736 }
737
ScaleToOutsidePixels(float aScaleX,float aScaleY,nscoord aAppUnitsPerPixel) const738 nsIntRegion nsRegion::ScaleToOutsidePixels (float aScaleX, float aScaleY,
739 nscoord aAppUnitsPerPixel) const
740 {
741 // make a copy of the region so that we can mutate it inplace
742 nsRegion region = *this;
743 int n;
744 pixman_box32_t *boxes = pixman_region32_rectangles(®ion.mImpl, &n);
745 boxes = pixman_region32_rectangles(®ion.mImpl, &n);
746 for (int i=0; i<n; i++) {
747 nsRect rect = BoxToRect(boxes[i]);
748 mozilla::gfx::IntRect irect = rect.ScaleToOutsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel);
749 boxes[i] = RectToBox(irect);
750 }
751
752 nsIntRegion iRegion;
753 // clear out the initial pixman_region so that we can replace it below
754 pixman_region32_fini(&iRegion.mImpl.mImpl);
755 // This will union all of the rectangles and runs in about O(n lg(n))
756 pixman_region32_init_rects(&iRegion.mImpl.mImpl, boxes, n);
757
758 return iRegion;
759 }
760
ScaleToInsidePixels(float aScaleX,float aScaleY,nscoord aAppUnitsPerPixel) const761 nsIntRegion nsRegion::ScaleToInsidePixels (float aScaleX, float aScaleY,
762 nscoord aAppUnitsPerPixel) const
763 {
764 /* When scaling a rect, walk forward through the rect list up until the y value is greater
765 * than the current rect's YMost() value.
766 *
767 * For each rect found, check if the rects have a touching edge (in unscaled coordinates),
768 * and if one edge is entirely contained within the other.
769 *
770 * If it is, then the contained edge can be moved (in scaled pixels) to ensure that no
771 * gap exists.
772 *
773 * Since this could be potentially expensive - O(n^2), we only attempt this algorithm
774 * for the first rect.
775 */
776
777 // make a copy of this region so that we can mutate it in place
778 nsRegion region = *this;
779 int n;
780 pixman_box32_t *boxes = pixman_region32_rectangles(®ion.mImpl, &n);
781
782 nsIntRegion intRegion;
783 if (n) {
784 nsRect first = BoxToRect(boxes[0]);
785 mozilla::gfx::IntRect firstDeviceRect =
786 first.ScaleToInsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel);
787
788 for (int i=1; i<n; i++) {
789 nsRect rect = nsRect(boxes[i].x1, boxes[i].y1,
790 boxes[i].x2 - boxes[i].x1,
791 boxes[i].y2 - boxes[i].y1);
792 mozilla::gfx::IntRect deviceRect =
793 rect.ScaleToInsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel);
794
795 if (rect.y <= first.YMost()) {
796 if (rect.XMost() == first.x && rect.YMost() <= first.YMost()) {
797 // rect is touching on the left edge of the first rect and contained within
798 // the length of its left edge
799 deviceRect.SetRightEdge(firstDeviceRect.x);
800 } else if (rect.x == first.XMost() && rect.YMost() <= first.YMost()) {
801 // rect is touching on the right edge of the first rect and contained within
802 // the length of its right edge
803 deviceRect.SetLeftEdge(firstDeviceRect.XMost());
804 } else if (rect.y == first.YMost()) {
805 // The bottom of the first rect is on the same line as the top of rect, but
806 // they aren't necessarily contained.
807 if (rect.x <= first.x && rect.XMost() >= first.XMost()) {
808 // The top of rect contains the bottom of the first rect
809 firstDeviceRect.SetBottomEdge(deviceRect.y);
810 } else if (rect.x >= first.x && rect.XMost() <= first.XMost()) {
811 // The bottom of the first contains the top of rect
812 deviceRect.SetTopEdge(firstDeviceRect.YMost());
813 }
814 }
815 }
816
817 boxes[i] = RectToBox(deviceRect);
818 }
819
820 boxes[0] = RectToBox(firstDeviceRect);
821
822 pixman_region32_fini(&intRegion.mImpl.mImpl);
823 // This will union all of the rectangles and runs in about O(n lg(n))
824 pixman_region32_init_rects(&intRegion.mImpl.mImpl, boxes, n);
825 }
826 return intRegion;
827
828 }
829
830 // A cell's "value" is a pair consisting of
831 // a) the area of the subrectangle it corresponds to, if it's in
832 // aContainingRect and in the region, 0 otherwise
833 // b) the area of the subrectangle it corresponds to, if it's in the region,
834 // 0 otherwise
835 // Addition, subtraction and identity are defined on these values in the
836 // obvious way. Partial order is lexicographic.
837 // A "large negative value" is defined with large negative numbers for both
838 // fields of the pair. This negative value has the property that adding any
839 // number of non-negative values to it always results in a negative value.
840 //
841 // The GetLargestRectangle algorithm works in three phases:
842 // 1) Convert the region into a grid by adding vertical/horizontal lines for
843 // each edge of each rectangle in the region.
844 // 2) For each rectangle in the region, for each cell it contains, set that
845 // cells's value as described above.
846 // 3) Calculate the submatrix with the largest sum such that none of its cells
847 // contain any 0s (empty regions). The rectangle represented by the
848 // submatrix is the largest rectangle in the region.
849 //
850 // Let k be the number of rectangles in the region.
851 // Let m be the height of the grid generated in step 1.
852 // Let n be the width of the grid generated in step 1.
853 //
854 // Step 1 is O(k) in time and O(m+n) in space for the sparse grid.
855 // Step 2 is O(mn) in time and O(mn) in additional space for the full grid.
856 // Step 3 is O(m^2 n) in time and O(mn) in additional space
857 //
858 // The implementation of steps 1 and 2 are rather straightforward. However our
859 // implementation of step 3 uses dynamic programming to achieve its efficiency.
860 //
861 // Psuedo code for step 3 is as follows where G is the grid from step 1 and A
862 // is the array from step 2:
863 // Phase3 = function (G, A, m, n) {
864 // let (t,b,l,r,_) = MaxSum2D(A,m,n)
865 // return rect(G[t],G[l],G[r],G[b]);
866 // }
867 // MaxSum2D = function (A, m, n) {
868 // S = array(m+1,n+1)
869 // S[0][i] = 0 for i in [0,n]
870 // S[j][0] = 0 for j in [0,m]
871 // S[j][i] = (if A[j-1][i-1] = 0 then some large negative value else A[j-1][i-1])
872 // + S[j-1][n] + S[j][i-1] - S[j-1][i-1]
873 //
874 // // top, bottom, left, right, area
875 // var maxRect = (-1, -1, -1, -1, 0);
876 //
877 // for all (m',m'') in [0, m]^2 {
878 // let B = { S[m'][i] - S[m''][i] | 0 <= i <= n }
879 // let ((l,r),area) = MaxSum1D(B,n+1)
880 // if (area > maxRect.area) {
881 // maxRect := (m', m'', l, r, area)
882 // }
883 // }
884 //
885 // return maxRect;
886 // }
887 //
888 // Originally taken from Improved algorithms for the k-maximum subarray problem
889 // for small k - SE Bae, T Takaoka but modified to show the explicit tracking
890 // of indices and we already have the prefix sums from our one call site so
891 // there's no need to construct them.
892 // MaxSum1D = function (A,n) {
893 // var minIdx = 0;
894 // var min = 0;
895 // var maxIndices = (0,0);
896 // var max = 0;
897 // for i in range(n) {
898 // let cand = A[i] - min;
899 // if (cand > max) {
900 // max := cand;
901 // maxIndices := (minIdx, i)
902 // }
903 // if (min > A[i]) {
904 // min := A[i];
905 // minIdx := i;
906 // }
907 // }
908 // return (minIdx, maxIdx, max);
909 // }
910
911 namespace {
912 // This class represents a partitioning of an axis delineated by coordinates.
913 // It internally maintains a sorted array of coordinates.
914 class AxisPartition {
915 public:
916 // Adds a new partition at the given coordinate to this partitioning. If
917 // the coordinate is already present in the partitioning, this does nothing.
InsertCoord(nscoord c)918 void InsertCoord(nscoord c) {
919 uint32_t i = mStops.IndexOfFirstElementGt(c);
920 if (i == 0 || mStops[i-1] != c) {
921 mStops.InsertElementAt(i, c);
922 }
923 }
924
925 // Returns the array index of the given partition point. The partition
926 // point must already be present in the partitioning.
IndexOf(nscoord p) const927 int32_t IndexOf(nscoord p) const {
928 return mStops.BinaryIndexOf(p);
929 }
930
931 // Returns the partition at the given index which must be non-zero and
932 // less than the number of partitions in this partitioning.
StopAt(int32_t index) const933 nscoord StopAt(int32_t index) const {
934 return mStops[index];
935 }
936
937 // Returns the size of the gap between the partition at the given index and
938 // the next partition in this partitioning. If the index is the last index
939 // in the partitioning, the result is undefined.
StopSize(int32_t index) const940 nscoord StopSize(int32_t index) const {
941 return mStops[index+1] - mStops[index];
942 }
943
944 // Returns the number of partitions in this partitioning.
GetNumStops() const945 int32_t GetNumStops() const { return mStops.Length(); }
946
947 private:
948 nsTArray<nscoord> mStops;
949 };
950
951 const int64_t kVeryLargeNegativeNumber = 0xffff000000000000ll;
952
953 struct SizePair {
954 int64_t mSizeContainingRect;
955 int64_t mSize;
956
SizePair__anon67436b870111::SizePair957 SizePair() : mSizeContainingRect(0), mSize(0) {}
958
VeryLargeNegative__anon67436b870111::SizePair959 static SizePair VeryLargeNegative() {
960 SizePair result;
961 result.mSize = result.mSizeContainingRect = kVeryLargeNegativeNumber;
962 return result;
963 }
operator <__anon67436b870111::SizePair964 bool operator<(const SizePair& aOther) const {
965 if (mSizeContainingRect < aOther.mSizeContainingRect)
966 return true;
967 if (mSizeContainingRect > aOther.mSizeContainingRect)
968 return false;
969 return mSize < aOther.mSize;
970 }
operator >__anon67436b870111::SizePair971 bool operator>(const SizePair& aOther) const {
972 return aOther.operator<(*this);
973 }
operator +__anon67436b870111::SizePair974 SizePair operator+(const SizePair& aOther) const {
975 SizePair result = *this;
976 result.mSizeContainingRect += aOther.mSizeContainingRect;
977 result.mSize += aOther.mSize;
978 return result;
979 }
operator -__anon67436b870111::SizePair980 SizePair operator-(const SizePair& aOther) const {
981 SizePair result = *this;
982 result.mSizeContainingRect -= aOther.mSizeContainingRect;
983 result.mSize -= aOther.mSize;
984 return result;
985 }
986 };
987
988 // Returns the sum and indices of the subarray with the maximum sum of the
989 // given array (A,n), assuming the array is already in prefix sum form.
MaxSum1D(const nsTArray<SizePair> & A,int32_t n,int32_t * minIdx,int32_t * maxIdx)990 SizePair MaxSum1D(const nsTArray<SizePair> &A, int32_t n,
991 int32_t *minIdx, int32_t *maxIdx) {
992 // The min/max indicies of the largest subarray found so far
993 SizePair min, max;
994 int32_t currentMinIdx = 0;
995
996 *minIdx = 0;
997 *maxIdx = 0;
998
999 // Because we're given the array in prefix sum form, we know the first
1000 // element is 0
1001 for(int32_t i = 1; i < n; i++) {
1002 SizePair cand = A[i] - min;
1003 if (cand > max) {
1004 max = cand;
1005 *minIdx = currentMinIdx;
1006 *maxIdx = i;
1007 }
1008 if (min > A[i]) {
1009 min = A[i];
1010 currentMinIdx = i;
1011 }
1012 }
1013
1014 return max;
1015 }
1016 } // namespace
1017
GetLargestRectangle(const nsRect & aContainingRect) const1018 nsRect nsRegion::GetLargestRectangle (const nsRect& aContainingRect) const {
1019 nsRect bestRect;
1020
1021 if (GetNumRects() <= 1) {
1022 bestRect = GetBounds();
1023 return bestRect;
1024 }
1025
1026 AxisPartition xaxis, yaxis;
1027
1028 // Step 1: Calculate the grid lines
1029 for (auto iter = RectIter(); !iter.Done(); iter.Next()) {
1030 const nsRect& rect = iter.Get();
1031 xaxis.InsertCoord(rect.x);
1032 xaxis.InsertCoord(rect.XMost());
1033 yaxis.InsertCoord(rect.y);
1034 yaxis.InsertCoord(rect.YMost());
1035 }
1036 if (!aContainingRect.IsEmpty()) {
1037 xaxis.InsertCoord(aContainingRect.x);
1038 xaxis.InsertCoord(aContainingRect.XMost());
1039 yaxis.InsertCoord(aContainingRect.y);
1040 yaxis.InsertCoord(aContainingRect.YMost());
1041 }
1042
1043 // Step 2: Fill out the grid with the areas
1044 // Note: due to the ordering of rectangles in the region, it is not always
1045 // possible to combine steps 2 and 3 so we don't try to be clever.
1046 int32_t matrixHeight = yaxis.GetNumStops() - 1;
1047 int32_t matrixWidth = xaxis.GetNumStops() - 1;
1048 int32_t matrixSize = matrixHeight * matrixWidth;
1049 nsTArray<SizePair> areas(matrixSize);
1050 areas.SetLength(matrixSize);
1051
1052 for (auto iter = RectIter(); !iter.Done(); iter.Next()) {
1053 const nsRect& rect = iter.Get();
1054 int32_t xstart = xaxis.IndexOf(rect.x);
1055 int32_t xend = xaxis.IndexOf(rect.XMost());
1056 int32_t y = yaxis.IndexOf(rect.y);
1057 int32_t yend = yaxis.IndexOf(rect.YMost());
1058
1059 for (; y < yend; y++) {
1060 nscoord height = yaxis.StopSize(y);
1061 for (int32_t x = xstart; x < xend; x++) {
1062 nscoord width = xaxis.StopSize(x);
1063 int64_t size = width*int64_t(height);
1064 if (rect.Intersects(aContainingRect)) {
1065 areas[y*matrixWidth+x].mSizeContainingRect = size;
1066 }
1067 areas[y*matrixWidth+x].mSize = size;
1068 }
1069 }
1070 }
1071
1072 // Step 3: Find the maximum submatrix sum that does not contain a rectangle
1073 {
1074 // First get the prefix sum array
1075 int32_t m = matrixHeight + 1;
1076 int32_t n = matrixWidth + 1;
1077 nsTArray<SizePair> pareas(m*n);
1078 pareas.SetLength(m*n);
1079 for (int32_t y = 1; y < m; y++) {
1080 for (int32_t x = 1; x < n; x++) {
1081 SizePair area = areas[(y-1)*matrixWidth+x-1];
1082 if (!area.mSize) {
1083 area = SizePair::VeryLargeNegative();
1084 }
1085 area = area + pareas[ y*n+x-1]
1086 + pareas[(y-1)*n+x ]
1087 - pareas[(y-1)*n+x-1];
1088 pareas[y*n+x] = area;
1089 }
1090 }
1091
1092 // No longer need the grid
1093 areas.SetLength(0);
1094
1095 SizePair bestArea;
1096 struct {
1097 int32_t left, top, right, bottom;
1098 } bestRectIndices = { 0, 0, 0, 0 };
1099 for (int32_t m1 = 0; m1 < m; m1++) {
1100 for (int32_t m2 = m1+1; m2 < m; m2++) {
1101 nsTArray<SizePair> B;
1102 B.SetLength(n);
1103 for (int32_t i = 0; i < n; i++) {
1104 B[i] = pareas[m2*n+i] - pareas[m1*n+i];
1105 }
1106 int32_t minIdx, maxIdx;
1107 SizePair area = MaxSum1D(B, n, &minIdx, &maxIdx);
1108 if (area > bestArea) {
1109 bestRectIndices.left = minIdx;
1110 bestRectIndices.top = m1;
1111 bestRectIndices.right = maxIdx;
1112 bestRectIndices.bottom = m2;
1113 bestArea = area;
1114 }
1115 }
1116 }
1117
1118 bestRect.MoveTo(xaxis.StopAt(bestRectIndices.left),
1119 yaxis.StopAt(bestRectIndices.top));
1120 bestRect.SizeTo(xaxis.StopAt(bestRectIndices.right) - bestRect.x,
1121 yaxis.StopAt(bestRectIndices.bottom) - bestRect.y);
1122 }
1123
1124 return bestRect;
1125 }
1126
operator <<(std::ostream & stream,const nsRegion & m)1127 std::ostream& operator<<(std::ostream& stream, const nsRegion& m) {
1128 stream << "[";
1129
1130 int n;
1131 pixman_box32_t *boxes = pixman_region32_rectangles(const_cast<pixman_region32_t*>(&m.mImpl), &n);
1132 for (int i=0; i<n; i++) {
1133 if (i != 0) {
1134 stream << "; ";
1135 }
1136 stream << boxes[i].x1 << "," << boxes[i].y1 << "," << boxes[i].x2 << "," << boxes[i].y2;
1137 }
1138
1139 stream << "]";
1140 return stream;
1141 }
1142
1143 nsCString
ToString() const1144 nsRegion::ToString() const {
1145 return nsCString(mozilla::ToString(*this).c_str());
1146 }
1147