[WebRTC] Add ScreenCapturerDifferWrapper to share Differ across ScreenCapturers

webrtc/modules/desktop_capture/screen_capturer_differ_wrapper.cc

+/*
+ *  Copyright (c) 2016 The WebRTC project authors. All Rights Reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license
+ *  that can be found in the LICENSE file in the root of the source
+ *  tree. An additional intellectual property rights grant can be found
+ *  in the file PATENTS.  All contributing project authors may
+ *  be found in the AUTHORS file in the root of the source tree.
+ */
+
+#include "webrtc/modules/desktop_capture/screen_capturer_differ_wrapper.h"
+
+#include <algorithm>
+#include <utility>
+
+#include "webrtc/base/checks.h"
+#include "webrtc/base/timeutils.h"
+#include "webrtc/modules/desktop_capture/desktop_geometry.h"
+#include "webrtc/modules/desktop_capture/differ_block.h"
+
+namespace webrtc {
+
+namespace {
+
+static const int kBlockXOffset = kBlockSize * DesktopFrame::kBytesPerPixel;

[Sergey Ulanov, 2016/09/01 19:27:56]

nit: this const is used in only 2 places, so I don't think you really need it.

[Hzj_jie, 2016/09/01 23:26:42]

Done.

+
+// Returns true if (0, 0) - (|width|, |height|) vector in |old_buffer| and
+// |new_buffer| are equal. |width| should be less than 32
+// (defined by kBlockSize), otherwise BlockDifference() should be used.
+bool PartialBlockDifference(const uint8_t* old_buffer,
+                            const uint8_t* new_buffer,
+                            int width,
+                            int height,
+                            int stride) {
+  RTC_DCHECK(width < kBlockSize);

[Sergey Ulanov, 2016/09/01 19:27:56]

RTC_DCHECK_LT

[Hzj_jie, 2016/09/01 23:26:43]

Done.

+  const int width_bytes = width * DesktopFrame::kBytesPerPixel;
+  for (int i = 0; i < height; i++) {
+    if (memcmp(old_buffer, new_buffer, width_bytes) != 0) {
+      return true;
+    }
+    old_buffer += stride;
+    new_buffer += stride;
+  }
+  return false;
+}
+
+// Compares columns in the range of [|column_left|,
+// |column_left| + |block_count| * kBlockSize + |last_block_width|), in a row in
+// the range of [row_top, row_top + row_height), starts from |old_buffer| and
+// |new_buffer|, and outputs updated regions into |output|. |stride| is the
+// DesktopFrame::stride().
+void CompareRow(const uint8_t* old_buffer,
+                const uint8_t* new_buffer,
+                const int column_left,
+                const int block_count,
+                const int last_block_width,

[Sergey Ulanov, 2016/09/01 19:27:56]

Instead of passing  block_count and last_block_width here it would be better to
pass width and calculate number of blocks here.

[Hzj_jie, 2016/09/01 23:26:43]

I believe besides the functionality, the first priority of this class is
performance. Both block_count and last_block_width won't change in the for loop
in line 138. So we can save the redundant calculating here.

[Sergey Ulanov, 2016/09/02 19:23:03]

You also calculate column_right below, so I don't think this optimization can
actually have any effect. In either case any potential effect of this perf
optimization is negligible, so it's better to make this code more readable.

[Hzj_jie, 2016/09/02 21:46:30]

Done.

+                const int row_top,
+                const int row_height,
+                const int stride,
+                DesktopRegion* const output) {
+  RTC_DCHECK(last_block_width <= kBlockSize && last_block_width > 0);
+  const int row_bottom = row_top + row_height;
+  const int column_right =
+      column_left + block_count * kBlockSize + last_block_width;
+
+  // The first block-column in a continuous dirty area in current block-row.
+  int first_dirty_x_block = -1;
+
+  // We always need to add dirty area into |output| in the last block, so handle
+  // it separatedly.
+  for (int x = 0; x < block_count; x++) {
+    if (BlockDifference(old_buffer, new_buffer, row_height, stride)) {
+      if (first_dirty_x_block == -1) {
+        // This is the first dirty block in a continuous dirty area.
+        first_dirty_x_block = x;
+      }
+    } else if (first_dirty_x_block != -1) {

[Sergey Ulanov, 2016/09/01 19:27:56]

I don't think it's worth to merge the blocks horizontally here. Just add them to
the Region one by one and let it handle this case - that would simplify this
code significantly.

[Hzj_jie, 2016/09/01 23:26:43]

By using this merging logic, we can save at least 80% time for each frame.
The time to execute test case can be significantly increased from 6s to 10s by
removing the merge logic.

This should be expected, as DesktopRegion will merge the rectangle by row. The
merging logic here can help to reduce the complexity from O(n * log(n) * log(n))
to O(log(n) * log(n)).

And though the test cases may not consistent with real world, the real world may
be even worse. As the perf drops more with larger rectangles.

+      // The block on the left is the last dirty block in a continuous
+      // dirty area.
+      output->AddRect(DesktopRect::MakeLTRB(
+          first_dirty_x_block * kBlockSize + column_left, row_top,
+          x * kBlockSize + column_left, row_bottom));
+      first_dirty_x_block = -1;
+    }
+    old_buffer += kBlockXOffset;
+    new_buffer += kBlockXOffset;
+  }
+
+  bool last_block_diff;
+  if (last_block_width < kBlockSize) {

[Sergey Ulanov, 2016/09/01 19:27:56]

Why would we want last_block_width = kBlockSize? if width is multiple of 32 then
last_block_width should be 0, and we just ignore it here

[Hzj_jie, 2016/09/01 23:26:42]

It relates to the merging logic above, we always need to handle the last block
differently. i.e. Adding last dirty area into |output|. So we expect a > 0
last_block_width.

+    // The last one is a partial vector.
+    last_block_diff = PartialBlockDifference(
+        old_buffer, new_buffer, last_block_width, row_height, stride);
+  } else {
+    last_block_diff =
+        BlockDifference(old_buffer, new_buffer, row_height, stride);
+  }
+  if (last_block_diff) {
+    if (first_dirty_x_block == -1) {
+      output->AddRect(
+          DesktopRect::MakeLTRB(column_left + block_count * kBlockSize, row_top,
+                                column_right, row_bottom));
+    } else {
+      output->AddRect(
+          DesktopRect::MakeLTRB(first_dirty_x_block * kBlockSize + column_left,
+                                row_top, column_right, row_bottom));
+    }
+  } else if (first_dirty_x_block != -1) {
+    output->AddRect(DesktopRect::MakeLTRB(
+        first_dirty_x_block * kBlockSize + column_left, row_top,
+        block_count * kBlockSize + column_left, row_bottom));
+  }
+}
+
+// Compares |rect| area in |old_frame| and |new_frame|, and outputs dirty
+// regions into |output|.
+void CompareFrames(const DesktopFrame& old_frame,
+                   const DesktopFrame& new_frame,
+                   DesktopRect rect,
+                   DesktopRegion* const output) {
+  RTC_DCHECK(old_frame.size().equals(new_frame.size()));
+  RTC_DCHECK_EQ(old_frame.stride(), new_frame.stride());
+  rect.IntersectWith(DesktopRect::MakeSize(old_frame.size()));
+
+  const int x_block_count = (rect.width() - 1) / kBlockSize;

[Sergey Ulanov, 2016/09/01 19:27:56]

Don't need -1 here

[Hzj_jie, 2016/09/01 23:26:42]

This relates to the merging logic in CompareRow.

+  const int last_x_block_width = rect.width() - x_block_count * kBlockSize;
+  const int y_block_count = (rect.height() - 1) / kBlockSize;

[Sergey Ulanov, 2016/09/01 19:27:56]

don't need -1 here

[Hzj_jie, 2016/09/01 23:26:42]

By -1 here, and adding a CompareRow in 146, we can save bool comparison in the
for loop in line 138.

+  const int last_y_block_height = rect.height() - y_block_count * kBlockSize;
+  // Offset from the start of one block-row to the next.
+  const int block_y_stride = old_frame.stride() * kBlockSize;
+  const uint8_t* prev_block_row_start =
+      old_frame.GetFrameDataAtPos(rect.top_left());
+  const uint8_t* curr_block_row_start =
+      new_frame.GetFrameDataAtPos(rect.top_left());
+
+  int row_top = rect.top();
+  // The last row may have a different height, so we handle it separately.
+  for (int y = 0; y < y_block_count; y++) {
+    CompareRow(prev_block_row_start, curr_block_row_start, rect.left(),
+               x_block_count, last_x_block_width, row_top, kBlockSize,
+               old_frame.stride(), output);
+    row_top += kBlockSize;
+    prev_block_row_start += block_y_stride;
+    curr_block_row_start += block_y_stride;
+  }
+  CompareRow(prev_block_row_start, curr_block_row_start, rect.left(),
+             x_block_count, last_x_block_width, row_top, last_y_block_height,
+             old_frame.stride(), output);
+}
+
+}  // namespace
+
+ScreenCapturerDifferWrapper::ScreenCapturerDifferWrapper(
+    std::unique_ptr<ScreenCapturer> base_capturer)
+    : base_capturer_(std::move(base_capturer)) {
+  RTC_DCHECK(base_capturer_);
+}
+
+ScreenCapturerDifferWrapper::~ScreenCapturerDifferWrapper() {}
+
+void ScreenCapturerDifferWrapper::Start(DesktopCapturer::Callback* callback) {
+  callback_ = callback;
+  base_capturer_->Start(this);
+}
+
+void ScreenCapturerDifferWrapper::SetSharedMemoryFactory(
+    std::unique_ptr<SharedMemoryFactory> shared_memory_factory) {
+  base_capturer_->SetSharedMemoryFactory(std::move(shared_memory_factory));
+}
+
+void ScreenCapturerDifferWrapper::Capture(const DesktopRegion& region) {
+  base_capturer_->Capture(region);
+}
+
+bool ScreenCapturerDifferWrapper::GetScreenList(ScreenList* screens) {
+  return base_capturer_->GetScreenList(screens);
+}
+
+bool ScreenCapturerDifferWrapper::SelectScreen(ScreenId id) {
+  return base_capturer_->SelectScreen(id);
+}
+
+void ScreenCapturerDifferWrapper::OnCaptureResult(
+    Result result,
+    std::unique_ptr<DesktopFrame> input_frame) {
+  int64_t start_time_nanos = rtc::TimeNanos();
+  if (!input_frame) {
+    callback_->OnCaptureResult(result, nullptr);
+    return;
+  }
+
+  std::unique_ptr<SharedDesktopFrame> frame =
+      SharedDesktopFrame::Wrap(std::move(input_frame));
+  if (result == Result::SUCCESS) {
+    if (last_frame_ &&
+        (last_frame_->size().width() != frame->size().width() ||
+         last_frame_->size().height() != frame->size().height() ||
+         last_frame_->stride() != frame->stride())) {
+      last_frame_.reset();
+    }
+
+    if (last_frame_) {
+      DesktopRegion hints;
+      hints.Swap(frame->GetUnderlyingFrame()->mutable_updated_region());
+      for (DesktopRegion::Iterator it(hints); !it.IsAtEnd(); it.Advance()) {
+        CompareFrames(*last_frame_, *frame, it.rect(),
+                      frame->mutable_updated_region());
+      }
+    } else {
+      frame->mutable_updated_region()->SetRect(
+          DesktopRect::MakeSize(frame->size()));
+    }
+    last_frame_ = frame->Share();
+  } else {
+    last_frame_.reset();
+  }
+
+  frame->set_capture_time_ms(frame->GetUnderlyingFrame()->capture_time_ms() +
+                             (rtc::TimeNanos() - start_time_nanos) /
+                                 rtc::kNumNanosecsPerMillisec);
+  callback_->OnCaptureResult(result, std::move(frame));
+}
+
+}  // namespace webrtc