Fix bugs in DesktopRegion::Subtract().
Fixed a bug that caused the crash in the linked bug and also couple of
other issues in the same code. Also added more tests.
BUG=crbug.com/295057
R=wez@chromium.org
Review URL: https://webrtc-codereview.appspot.com/2259005
git-svn-id: http://webrtc.googlecode.com/svn/trunk@4806 4adac7df-926f-26a2-2b94-8c16560cd09d
diff --git a/webrtc/modules/desktop_capture/desktop_region.cc b/webrtc/modules/desktop_capture/desktop_region.cc
index 4159cd4..9042819 100644
--- a/webrtc/modules/desktop_capture/desktop_region.cc
+++ b/webrtc/modules/desktop_capture/desktop_region.cc
@@ -134,7 +134,7 @@
MergeWithPrecedingRow(row);
// Move to the next row.
- row++;
+ ++row;
}
if (row != rows_.end())
@@ -311,6 +311,12 @@
// If the |top| is above |row_a| then skip the range between |top| and
// top of |row_a| because it's empty.
top = row_a->second->top;
+ if (top >= row_b->second->bottom) {
+ ++row_b;
+ if (row_b != region.rows_.end())
+ top = row_b->second->top;
+ continue;
+ }
}
if (row_b->second->bottom < row_a->second->bottom) {
@@ -333,7 +339,7 @@
top = row_a->second->bottom;
if (top >= row_b->second->bottom) {
- row_b++;
+ ++row_b;
if (row_b != region.rows_.end())
top = row_b->second->top;
}
@@ -347,7 +353,7 @@
rows_.erase(row_to_delete);
} else {
MergeWithPrecedingRow(row_a);
- row_a++;
+ ++row_a;
}
}
@@ -474,17 +480,19 @@
// If there is no intersection then append the current span and continue.
if (it_b == set_b.end() || it_a->right < it_b->left) {
output->push_back(*it_a);
- it_a++;
continue;
}
// Iterate over |set_b| spans that may intersect with |it_a|.
int pos = it_a->left;
while (it_b != set_b.end() && it_b->left < it_a->right) {
- if (it_b->left > pos) {
+ if (it_b->left > pos)
output->push_back(RowSpan(pos, it_b->left));
+ if (it_b->right > pos) {
+ pos = it_b->right;
+ if (pos >= it_a->right)
+ break;
}
- pos = it_b->right;
++it_b;
}
if (pos < it_a->right)
diff --git a/webrtc/modules/desktop_capture/desktop_region_unittest.cc b/webrtc/modules/desktop_capture/desktop_region_unittest.cc
index 2c21661..747e8c0 100644
--- a/webrtc/modules/desktop_capture/desktop_region_unittest.cc
+++ b/webrtc/modules/desktop_capture/desktop_region_unittest.cc
@@ -542,6 +542,151 @@
}
}
+// Verify that DesktopRegion::SubtractRows() works correctly by creating a row
+// of not overlapping rectangles and subtracting a set of rectangle. Result
+// is verified by building a map of the region in an array and comparing it with
+// the expected values.
+TEST(DesktopRegionTest, SubtractRectOnSameRow) {
+ const int kMapWidth = 50;
+
+ struct SpanSet {
+ int count;
+ struct Range {
+ int start;
+ int end;
+ } spans[3];
+ } span_sets[] = {
+ {1, { {0, 3} } },
+ {1, { {0, 5} } },
+ {1, { {0, 7} } },
+ {1, { {0, 12} } },
+ {2, { {0, 3}, {4, 5}, {6, 16} } },
+ };
+
+ DesktopRegion base_region;
+ bool base_map[kMapWidth] = { false, };
+
+ base_region.AddRect(DesktopRect::MakeXYWH(5, 0, 5, 1));
+ std::fill_n(base_map + 5, 5, true);
+ base_region.AddRect(DesktopRect::MakeXYWH(15, 0, 5, 1));
+ std::fill_n(base_map + 15, 5, true);
+ base_region.AddRect(DesktopRect::MakeXYWH(25, 0, 5, 1));
+ std::fill_n(base_map + 25, 5, true);
+ base_region.AddRect(DesktopRect::MakeXYWH(35, 0, 5, 1));
+ std::fill_n(base_map + 35, 5, true);
+ base_region.AddRect(DesktopRect::MakeXYWH(45, 0, 5, 1));
+ std::fill_n(base_map + 45, 5, true);
+
+ for (size_t i = 0; i < sizeof(span_sets) / sizeof(span_sets[0]); i++) {
+ SCOPED_TRACE(i);
+ SpanSet& span_set = span_sets[i];
+ int span_set_end = span_set.spans[span_set.count - 1].end;
+ for (int x = 0; x < kMapWidth - span_set_end; ++x) {
+ SCOPED_TRACE(x);
+
+ DesktopRegion r = base_region;
+
+ bool expected_map[kMapWidth];
+ std::copy(base_map, base_map + kMapWidth, expected_map);
+
+ DesktopRegion region2;
+ for (int span = 0; span < span_set.count; span++) {
+ std::fill_n(x + expected_map + span_set.spans[span].start,
+ span_set.spans[span].end - span_set.spans[span].start,
+ false);
+ region2.AddRect(DesktopRect::MakeLTRB(x + span_set.spans[span].start, 0,
+ x + span_set.spans[span].end, 1));
+ }
+ r.Subtract(region2);
+
+ bool map[kMapWidth] = { false, };
+
+ int pos = -1;
+ for (DesktopRegion::Iterator it(r); !it.IsAtEnd(); it.Advance()) {
+ EXPECT_GT(it.rect().left(), pos);
+ pos = it.rect().right();
+ std::fill_n(map + it.rect().left(), it.rect().width(), true);
+ }
+
+ EXPECT_TRUE(std::equal(map, map + kMapWidth, expected_map));
+ }
+ }
+}
+
+// Verify that DesktopRegion::Subtract() works correctly by creating a column of
+// not overlapping rectangles and subtracting a set of rectangle on the same
+// column. Result is verified by building a map of the region in an array and
+// comparing it with the expected values.
+TEST(DesktopRegionTest, SubtractRectOnSameCol) {
+ const int kMapHeight = 50;
+
+ struct SpanSet {
+ int count;
+ struct Range {
+ int start;
+ int end;
+ } spans[3];
+ } span_sets[] = {
+ {1, { {0, 3} } },
+ {1, { {0, 5} } },
+ {1, { {0, 7} } },
+ {1, { {0, 12} } },
+ {2, { {0, 3}, {4, 5}, {6, 16} } },
+ };
+
+ DesktopRegion base_region;
+ bool base_map[kMapHeight] = { false, };
+
+ base_region.AddRect(DesktopRect::MakeXYWH(0, 5, 1, 5));
+ std::fill_n(base_map + 5, 5, true);
+ base_region.AddRect(DesktopRect::MakeXYWH(0, 15, 1, 5));
+ std::fill_n(base_map + 15, 5, true);
+ base_region.AddRect(DesktopRect::MakeXYWH(0, 25, 1, 5));
+ std::fill_n(base_map + 25, 5, true);
+ base_region.AddRect(DesktopRect::MakeXYWH(0, 35, 1, 5));
+ std::fill_n(base_map + 35, 5, true);
+ base_region.AddRect(DesktopRect::MakeXYWH(0, 45, 1, 5));
+ std::fill_n(base_map + 45, 5, true);
+
+ for (size_t i = 0; i < sizeof(span_sets) / sizeof(span_sets[0]); i++) {
+ SCOPED_TRACE(i);
+ SpanSet& span_set = span_sets[i];
+ int span_set_end = span_set.spans[span_set.count - 1].end;
+ for (int y = 0; y < kMapHeight - span_set_end; ++y) {
+ SCOPED_TRACE(y);
+
+ DesktopRegion r = base_region;
+
+ bool expected_map[kMapHeight];
+ std::copy(base_map, base_map + kMapHeight, expected_map);
+
+ DesktopRegion region2;
+ for (int span = 0; span < span_set.count; span++) {
+ std::fill_n(y + expected_map + span_set.spans[span].start,
+ span_set.spans[span].end - span_set.spans[span].start,
+ false);
+ region2.AddRect(DesktopRect::MakeLTRB(0, y + span_set.spans[span].start,
+ 1, y + span_set.spans[span].end));
+ }
+ r.Subtract(region2);
+
+ bool map[kMapHeight] = { false, };
+
+ int pos = -1;
+ for (DesktopRegion::Iterator it(r); !it.IsAtEnd(); it.Advance()) {
+ EXPECT_GT(it.rect().top(), pos);
+ pos = it.rect().bottom();
+ std::fill_n(map + it.rect().top(), it.rect().height(), true);
+ }
+
+ for (int j = 0; j < kMapHeight; j++) {
+ EXPECT_EQ(expected_map[j], map[j]) << "j = " << j;
+ }
+ }
+ }
+}
+
+
TEST(DesktopRegionTest, DISABLED_Performance) {
for (int c = 0; c < 1000; ++c) {
DesktopRegion r;