Initial code for screen differ that divides screen into blocks and calculate

a 'minimal' set of rectangles that covers the changed region.

BUG=none
TEST=new unittests added

Review URL: http://codereview.chromium.org/2714007

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@49325 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 842 insertions, 0 deletions

diff --git a/remoting/host/differ.cc b/remoting/host/differ.cc
new file mode 100644
index 0000000..e0a8125
--- /dev/null
+++ b/remoting/host/differ.cc
@@ -0,0 +1,226 @@
+// Copyright (c) 2010 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "remoting/host/differ.h"
+
+#include "base/logging.h"
+
+namespace remoting {
+
+Differ::Differ(int width, int height, int bpp) {
+  // Dimensions of screen.
+  width_ = width;
+  height_ = height;
+  bytes_per_pixel_ = bpp;
+  bytes_per_row_ = width_ * bytes_per_pixel_;
+
+  // Calc number of blocks (full and partial) required to cover entire image.
+  // One additional row/column is added as a boundary on the right & bottom.
+  diff_info_width_ = (width_ + kBlockSize - 1) / kBlockSize + 1;
+  diff_info_height_ = (height_ + kBlockSize - 1) / kBlockSize + 1;
+  diff_info_size_ = diff_info_width_ * diff_info_height_ * sizeof(DiffInfo);
+  diff_info_.reset(new uint8[diff_info_size_]);
+}
+
+void Differ::CalcDirtyRects(const void* prev_buffer, const void* curr_buffer,
+                            DirtyRects* rects) {
+  if (!rects) {
+    return;
+  }
+  rects->clear();
+
+  if (!prev_buffer || !curr_buffer) {
+    return;
+  }
+
+  // Identify all the blocks that contain changed pixels.
+  MarkDirtyBlocks(prev_buffer, curr_buffer);
+
+  // Now that we've identified the blocks that have changed, merge adjacent
+  // blocks to minimize the number of rects that we return.
+  MergeBlocks(rects);
+}
+
+void Differ::MarkDirtyBlocks(const void* prev_buffer, const void* curr_buffer) {
+  memset(diff_info_.get(), 0, diff_info_size_);
+
+  // Calc number of full blocks.
+  int x_full_blocks = width_ / kBlockSize;
+  int y_full_blocks = height_ / kBlockSize;
+
+  // Calc size of partial blocks which may be present on right and bottom edge.
+  int partial_column_width = width_ - (x_full_blocks * kBlockSize);
+  int partial_row_height = height_ - (y_full_blocks * kBlockSize);
+
+  // Offset from the start of one block-column to the next.
+  int block_x_offset = bytes_per_pixel_ * kBlockSize;
+  // Offset from the start of one block-row to the next.
+  int block_y_stride = (width_ * bytes_per_pixel_) * kBlockSize;
+  // Offset from the start of one diff_info row to the next.
+  int diff_info_stride = diff_info_width_ * sizeof(DiffInfo);
+
+  const uint8* prev_block_row_start = static_cast<const uint8*>(prev_buffer);
+  const uint8* curr_block_row_start = static_cast<const uint8*>(curr_buffer);
+  uint8* diff_info_row_start = static_cast<uint8*>(diff_info_.get());
+
+  for (int y = 0; y < y_full_blocks; y++) {
+    const uint8* prev_block = prev_block_row_start;
+    const uint8* curr_block = curr_block_row_start;
+    uint8* diff_info = diff_info_row_start;
+
+    for (int x = 0; x < x_full_blocks; x++) {
+      DiffInfo diff = DiffBlock(prev_block, curr_block, bytes_per_row_);
+      if (diff != 0) {
+        // Mark this block as being modified so that it gets incorporated into
+        // a dirty rect.
+        *diff_info = diff;
+      }
+      prev_block += block_x_offset;
+      curr_block += block_x_offset;
+      diff_info += sizeof(DiffInfo);
+    }
+
+    // If there is a partial column at the end, handle it.
+    if (partial_column_width != 0) {
+      // TODO(garykac): Handle last partial column.
+    }
+
+    // Update pointers for next row.
+    prev_block_row_start += block_y_stride;
+    curr_block_row_start += block_y_stride;
+    diff_info_row_start += diff_info_stride;
+  }
+  if (partial_row_height != 0) {
+    // TODO(garykac): Handle last partial row.
+  }
+}
+
+DiffInfo Differ::DiffBlock(const uint8* prev_buffer, const uint8* curr_buffer,
+                           int stride) {
+  const uint8* prev_row_start = prev_buffer;
+  const uint8* curr_row_start = curr_buffer;
+
+  // Number of uint64s in each row of the block.
+  // This must be an integral number.
+  int int64s_per_row = (kBlockSize * bytes_per_pixel_) / sizeof(uint64);
+  DCHECK(((kBlockSize * bytes_per_pixel_) % sizeof(uint64)) == 0);
+
+  for (int y = 0; y < kBlockSize; y++) {
+    const uint64* prev = reinterpret_cast<const uint64*>(prev_row_start);
+    const uint64* curr = reinterpret_cast<const uint64*>(curr_row_start);
+
+    // Check each row in uint64-sized chunks.
+    // Note that this check may straddle multiple pixels. This is OK because
+    // we're interested in identifying whether or not there was change - we
+    // don't care what the actual change is.
+    for (int x = 0; x < int64s_per_row; x++) {
+      if (*prev++ != *curr++) {
+        return 1;
+      }
+    }
+    prev_row_start += stride;
+    curr_row_start += stride;
+  }
+  return 0;
+}
+
+DiffInfo Differ::DiffPartialBlock(const uint8* prev_buffer,
+                                  const uint8* curr_buffer,
+                                  int stride, int width, int height) {
+  const uint8* prev_row_start = prev_buffer;
+  const uint8* curr_row_start = curr_buffer;
+
+  for (int y = 0; y < height; y++) {
+    const uint8* prev = prev_row_start;
+    const uint8* curr = curr_row_start;
+    for (int x = 0; x < width; x++) {
+      for (int b = 0; b < bytes_per_pixel_; b++) {
+        if (*prev++ != *curr++) {
+          return 1;
+        }
+      }
+    }
+    prev_row_start += bytes_per_row_;
+    curr_row_start += bytes_per_row_;
+  }
+  return 0;
+}
+
+void Differ::MergeBlocks(DirtyRects* rects) {
+  DCHECK(rects);
+  rects->clear();
+
+  uint8* diff_info_row_start = static_cast<uint8*>(diff_info_.get());
+  int diff_info_stride = diff_info_width_ * sizeof(DiffInfo);
+
+  for (int y = 0; y < diff_info_height_; y++) {
+    uint8* diff_info = diff_info_row_start;
+    for (int x = 0; x < diff_info_width_; x++) {
+      if (*diff_info != 0) {
+        // We've found a modified block. Look at blocks to the right and below
+        // to group this block with as many others as we can.
+        int left = x * kBlockSize;
+        int top = y * kBlockSize;
+        int width = 1;
+        int height = 1;
+        *diff_info = 0;
+
+        // Group with blocks to the right.
+        // We can keep looking until we find an unchanged block because we
+        // have a boundary block which is never marked as having diffs.
+        uint8* right = diff_info + 1;
+        while (*right) {
+          *right++ = 0;
+          width++;
+        }
+
+        // Group with blocks below.
+        // The entire width of blocks that we matched above much match for
+        // each row that we add.
+        uint8* bottom = diff_info;
+        bool found_new_row;
+        do {
+          found_new_row = true;
+          bottom += diff_info_stride;
+          right = bottom;
+          for (int x2 = 0; x2 < width; x2++) {
+            if (*right++ == 0) {
+              found_new_row = false;
+            }
+          }
+
+          if (found_new_row) {
+            height++;
+
+            // We need to go back and erase the diff markers so that we don't
+            // try to add these blocks a second time.
+            right = bottom;
+            for (int x2 = 0; x2 < width; x2++) {
+              *right++ = 0;
+            }
+          }
+        } while (found_new_row);
+
+        // Add rect to list of dirty rects.
+        width *= kBlockSize;
+        if (left + width > width_) {
+          width = width_ - left;
+        }
+        height *= kBlockSize;
+        if (top + height > height_) {
+          height = height_ - top;
+        }
+        rects->push_back(gfx::Rect(left, top, width, height));
+      }
+
+      // Increment to next block in this row.
+      diff_info++;
+    }
+
+    // Go to start of next row.
+    diff_info_row_start += diff_info_stride;
+  }
+}
+
+}  // namespace remoting
diff --git a/remoting/host/differ.h b/remoting/host/differ.h
new file mode 100644
index 0000000..645f91d
--- /dev/null
+++ b/remoting/host/differ.h
@@ -0,0 +1,86 @@
+// Copyright (c) 2010 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef REMOTING_HOST_DIFFER_H_
+#define REMOTING_HOST_DIFFER_H_
+
+#include <vector>
+
+#include "base/basictypes.h"
+#include "base/scoped_ptr.h"
+#include "gfx/rect.h"
+
+namespace remoting {
+
+typedef std::vector<gfx::Rect> DirtyRects;
+typedef uint8 DiffInfo;
+
+// Size (in pixels) of each square block used for diffing.
+// This must be a multiple of sizeof(uint64).
+static const int kBlockSize = 32;
+
+class Differ {
+ public:
+  // Create a differ that operates on bitmaps with the specified width, height
+  // and bytes_per_pixel.
+  Differ(int width, int height, int bytes_per_pixel);
+
+  // Given the previous and current screen buffer, calculate the set of
+  // rectangles that enclose all the changed pixels in the new screen.
+  void CalcDirtyRects(const void* prev_buffer, const void* curr_buffer,
+                      DirtyRects* rects);
+
+  // Identify all of the blocks that contain changed pixels.
+  void MarkDirtyBlocks(const void* prev_buffer, const void* curr_buffer);
+
+  // Diff a small block of image and return non-zero if there is a diff.
+  // Currently, this just returns 0 or 1, but this may change in the future
+  // to return the number of pixels changed.
+  DiffInfo DiffBlock(const uint8* prev_buffer, const uint8* curr_buffer,
+                     int stride);
+
+  // Diff a small block of image and return non-zero if there is a diff.
+  // This checks only the part of the block specified by the width and
+  // height parameters.
+  // This is much slower than DiffBlock() since it cannot assume that the
+  // full block is being checked.
+  // If we force the capturer to always return images whose width/height are
+  // multiples of kBlockSize, then this will never be called.
+  DiffInfo DiffPartialBlock(const uint8* prev_buffer, const uint8* curr_buffer,
+                            int stride, int width, int height);
+
+  // After the dirty blocks have been identified, this routine merges adjacent
+  // blocks into larger rectangular units.
+  // The goal is to minimize the number of rects that cover the dirty blocks,
+  // although it is not required to calc the absolute minimum of rects.
+  void MergeBlocks(DirtyRects* rects);
+
+  // Allow tests to access our private parts.
+  friend class DifferTest;
+
+ private:
+  // Dimensions of screen.
+  int width_;
+  int height_;
+
+  // Number of bytes for each pixel in source and dest bitmap.
+  int bytes_per_pixel_;
+
+  // Number of bytes in each row of the image.
+  int bytes_per_row_;
+
+  // Diff information for each block in the image.
+  scoped_ptr<DiffInfo> diff_info_;
+
+  // Dimensions and total size of diff info array.
+  int diff_info_width_;
+  int diff_info_height_;
+  int diff_info_size_;
+
+  DISALLOW_COPY_AND_ASSIGN(Differ);
+};
+
+}  // namespace remoting
+
+#endif  // REMOTING_HOST_DIFFER_H_
diff --git a/remoting/host/differ_unittest.cc b/remoting/host/differ_unittest.cc
new file mode 100644
index 0000000..580ed50
--- /dev/null
+++ b/remoting/host/differ_unittest.cc
@@ -0,0 +1,530 @@
+// Copyright (c) 2010 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "base/scoped_ptr.h"
+#include "remoting/host/differ.h"
+#include "testing/gmock/include/gmock/gmock.h"
+
+namespace remoting {
+
+// 96x96 screen gives a 3x3 grid of blocks.
+const int kScreenWidth = 96;
+const int kScreenHeight = 96;
+const int kBytesPerPixel = 3;
+
+class DifferTest : public testing::Test {
+ public:
+  DifferTest() {
+  }
+
+ protected:
+  virtual void SetUp() {
+    InitDiffer(kScreenWidth, kScreenHeight, kBytesPerPixel);
+  }
+
+  void InitDiffer(int width, int height, int bpp) {
+    width_ = width;
+    height_ = height;
+    bytes_per_pixel_ = bpp;
+
+    stride_ = width_ * bytes_per_pixel_;
+    buffer_size_ = width_ * height_ * bytes_per_pixel_;
+
+    differ_.reset(new Differ(width_, height_, bytes_per_pixel_));
+
+    prev_.reset(new uint8[buffer_size_]);
+    memset(prev_.get(), 0, buffer_size_);
+
+    curr_.reset(new uint8[buffer_size_]);
+    memset(curr_.get(), 0, buffer_size_);
+  }
+
+  void ClearBuffer(uint8* buffer) {
+    memset(buffer, 0, buffer_size_);
+  }
+
+  // Convenience wrapper for Differ's DiffBlock that calculates the appropriate
+  // offset to the start of the desired block.
+  DiffInfo DiffBlock(int block_x, int block_y) {
+    // Offset from upper-left of buffer to upper-left of requested block.
+    int block_offset = ((block_y * stride_) + (block_x * bytes_per_pixel_))
+                        * kBlockSize;
+    differ_->DiffBlock(prev_.get() + block_offset,
+                              curr_.get() + block_offset,
+                              stride_);
+  }
+
+  // Write the pixel |value| into the specified block in the |buffer|.
+  // This is a convenience wrapper around WritePixel().
+  void WriteBlockPixel(uint8* buffer, int block_x, int block_y,
+                       int pixel_x, int pixel_y, uint32 value) {
+    WritePixel(buffer, (block_x * kBlockSize) + pixel_x,
+               (block_y * kBlockSize) + pixel_y, value);
+  }
+
+  // Write the test pixel |value| into the |buffer| at the specified |x|,|y|
+  // location.
+  // Only the low-order bytes from |value| are written (assuming little-endian).
+  // So, for |value| = 0xaabbccdd:
+  //   If bytes_per_pixel = 4, then ddccbbaa will be written as the pixel value.
+  //   If                 = 3,        ddccbb
+  //   If                 = 2,          ddcc
+  //   If                 = 1,            dd
+  void WritePixel(uint8* buffer, int x, int y, uint32 value) {
+    uint8* pixel = reinterpret_cast<uint8*>(&value);
+    buffer += (y * stride_) + (x * bytes_per_pixel_);
+    for (int b = bytes_per_pixel_ - 1; b >= 0; b--) {
+      *buffer++ = pixel[b];
+    }
+  }
+
+  // DiffInfo utility routines.
+  // These are here so that we don't have to make each DifferText_Xxx_Test
+  // class a friend class to Differ.
+
+  // Clear out the entire |diff_info_| buffer.
+  void ClearDiffInfo() {
+    memset(differ_->diff_info_.get(), 0, differ_->diff_info_size_);
+  }
+
+  // Get the value in the |diff_info_| array at (x,y).
+  DiffInfo GetDiffInfo(int x, int y) {
+    DiffInfo* diff_info = differ_->diff_info_.get();
+    return diff_info[(y * GetDiffInfoWidth()) + x];
+  }
+
+  // Width of |diff_info_| array.
+  int GetDiffInfoWidth() {
+    return differ_->diff_info_width_;
+  }
+
+  // Height of |diff_info_| array.
+  int GetDiffInfoHeight() {
+    return differ_->diff_info_height_;
+  }
+
+  // Size of |diff_info_| array.
+  int GetDiffInfoSize() {
+    return differ_->diff_info_size_;
+  }
+
+  void SetDiffInfo(int x, int y, const DiffInfo& value) {
+    DiffInfo* diff_info = differ_->diff_info_.get();
+    diff_info[(y * GetDiffInfoWidth()) + x] = value;
+  }
+
+  // Mark the range of blocks specified.
+  void MarkBlocks(int x_origin, int y_origin, int width, int height) {
+    for (int y = 0; y < height; y++) {
+      for (int x = 0; x < width; x++) {
+        SetDiffInfo(x_origin + x, y_origin + y, 1);
+      }
+    }
+  }
+
+  // Verify that the given dirty rect matches the expected |x|, |y|, |width|
+  // and |height|.
+  // |x|, |y|, |width| and |height| are specified in block (not pixel) units.
+  void CheckDirtyRect(const gfx::Rect& rect, int x, int y,
+                      int width, int height) {
+    EXPECT_EQ(x * kBlockSize, rect.x());
+    EXPECT_EQ(y * kBlockSize, rect.y());
+    EXPECT_EQ(width * kBlockSize, rect.width());
+    EXPECT_EQ(height * kBlockSize, rect.height());
+  }
+
+  // Mark the range of blocks specified and then verify that they are
+  // merged correctly.
+  // Only one rectangular region of blocks can be checked with this routine.
+  void MarkBlocksAndCheckMerge(int x_origin, int y_origin,
+                               int width, int height) {
+    ClearDiffInfo();
+    MarkBlocks(x_origin, y_origin, width, height);
+
+    DirtyRects* dirty = new DirtyRects();
+    differ_->MergeBlocks(dirty);
+
+    ASSERT_EQ(1, dirty->size());
+    CheckDirtyRect(dirty->at(0), x_origin, y_origin, width, height);
+  }
+
+  // The differ class we're testing.
+  scoped_ptr<Differ> differ_;
+
+  // Screen/buffer info.
+  int width_;
+  int height_;
+  int bytes_per_pixel_;
+  int stride_;
+
+  // Size of each screen buffer.
+  int buffer_size_;
+
+  // Previous and current screen buffers.
+  scoped_ptr<uint8> prev_;
+  scoped_ptr<uint8> curr_;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(DifferTest);
+};
+
+TEST_F(DifferTest, Setup) {
+  // 96x96 pixels results in 3x3 array. Add 1 to each dimension as boundary.
+  // +---+---+---+---+
+  // | o | o | o | _ |
+  // +---+---+---+---+  o = blocks mapped to screen pixels
+  // | o | o | o | _ |
+  // +---+---+---+---+  _ = boundary blocks
+  // | o | o | o | _ |
+  // +---+---+---+---+
+  // | _ | _ | _ | _ |
+  // +---+---+---+---+
+  EXPECT_EQ(4, GetDiffInfoWidth());
+  EXPECT_EQ(4, GetDiffInfoHeight());
+  EXPECT_EQ(16, GetDiffInfoSize());
+}
+
+TEST_F(DifferTest, MarkDirtyBlocks_All) {
+  ClearDiffInfo();
+
+  // Update a pixel in each block.
+  for (int y = 0; y < GetDiffInfoHeight() - 1; y++) {
+    for (int x = 0; x < GetDiffInfoWidth() - 1; x++) {
+      WriteBlockPixel(curr_.get(), x, y, 10, 10, 0xff00ff);
+    }
+  }
+
+  differ_->MarkDirtyBlocks(prev_.get(), curr_.get());
+
+  // Make sure each block is marked as dirty.
+  for (int y = 0; y < GetDiffInfoHeight() - 1; y++) {
+    for (int x = 0; x < GetDiffInfoWidth() - 1; x++) {
+      EXPECT_EQ(1, GetDiffInfo(x, y))
+          << "when x = " << x << ", and y = " << y;
+    }
+  }
+}
+
+TEST_F(DifferTest, MarkDirtyBlocks_Sampling) {
+  ClearDiffInfo();
+
+  // Update some pixels in image.
+  WriteBlockPixel(curr_.get(), 1, 0, 10, 10, 0xff00ff);
+  WriteBlockPixel(curr_.get(), 2, 1, 10, 10, 0xff00ff);
+  WriteBlockPixel(curr_.get(), 0, 2, 10, 10, 0xff00ff);
+
+  differ_->MarkDirtyBlocks(prev_.get(), curr_.get());
+
+  // Make sure corresponding blocks are updated.
+  EXPECT_EQ(0, GetDiffInfo(0, 0));
+  EXPECT_EQ(0, GetDiffInfo(0, 1));
+  EXPECT_EQ(1, GetDiffInfo(0, 2));
+  EXPECT_EQ(1, GetDiffInfo(1, 0));
+  EXPECT_EQ(0, GetDiffInfo(1, 1));
+  EXPECT_EQ(0, GetDiffInfo(1, 2));
+  EXPECT_EQ(0, GetDiffInfo(2, 0));
+  EXPECT_EQ(1, GetDiffInfo(2, 1));
+  EXPECT_EQ(0, GetDiffInfo(2, 2));
+}
+
+TEST_F(DifferTest, DiffBlock) {
+  // Verify no differences at start.
+  EXPECT_EQ(0, DiffBlock(0, 0));
+  EXPECT_EQ(0, DiffBlock(1, 1));
+
+  // Write new data into the 4 corners of the middle block and verify that
+  // neighboring blocks are not affected.
+  int max = kBlockSize - 1;
+  WriteBlockPixel(curr_.get(), 1, 1, 0, 0, 0xffffff);
+  WriteBlockPixel(curr_.get(), 1, 1, 0, max, 0xffffff);
+  WriteBlockPixel(curr_.get(), 1, 1, max, 0, 0xffffff);
+  WriteBlockPixel(curr_.get(), 1, 1, max, max, 0xffffff);
+  EXPECT_EQ(0, DiffBlock(0, 0));
+  EXPECT_EQ(0, DiffBlock(0, 1));
+  EXPECT_EQ(0, DiffBlock(0, 2));
+  EXPECT_EQ(0, DiffBlock(1, 0));
+  EXPECT_EQ(1, DiffBlock(1, 1));  // Only this block should change.
+  EXPECT_EQ(0, DiffBlock(1, 2));
+  EXPECT_EQ(0, DiffBlock(2, 0));
+  EXPECT_EQ(0, DiffBlock(2, 1));
+  EXPECT_EQ(0, DiffBlock(2, 2));
+}
+
+TEST_F(DifferTest, DiffPartialBlocks) {
+  // TODO(garykac): Add tests for DiffPartialBlock
+}
+
+
+TEST_F(DifferTest, MergeBlocks_Empty) {
+  // No blocks marked:
+  // +---+---+---+---+
+  // |   |   |   | _ |
+  // +---+---+---+---+
+  // |   |   |   | _ |
+  // +---+---+---+---+
+  // |   |   |   | _ |
+  // +---+---+---+---+
+  // | _ | _ | _ | _ |
+  // +---+---+---+---+
+  ClearDiffInfo();
+
+  DirtyRects* dirty = new DirtyRects();
+  differ_->MergeBlocks(dirty);
+
+  EXPECT_EQ(0, dirty->size());
+}
+
+TEST_F(DifferTest, MergeBlocks_SingleBlock) {
+  // Mark a single block and make sure that there is a single merged
+  // rect with the correct bounds.
+  for (int y = 0; y < GetDiffInfoHeight() - 1; y++) {
+    for (int x = 0; x < GetDiffInfoWidth() - 1; x++) {
+      MarkBlocksAndCheckMerge(x, y, 1, 1);
+    }
+  }
+}
+
+TEST_F(DifferTest, MergeBlocks_BlockRow) {
+  // +---+---+---+---+
+  // | X | X |   | _ |
+  // +---+---+---+---+
+  // |   |   |   | _ |
+  // +---+---+---+---+
+  // |   |   |   | _ |
+  // +---+---+---+---+
+  // | _ | _ | _ | _ |
+  // +---+---+---+---+
+  MarkBlocksAndCheckMerge(0, 0, 2, 1);
+
+  // +---+---+---+---+
+  // |   |   |   | _ |
+  // +---+---+---+---+
+  // | X | X | X | _ |
+  // +---+---+---+---+
+  // |   |   |   | _ |
+  // +---+---+---+---+
+  // | _ | _ | _ | _ |
+  // +---+---+---+---+
+  MarkBlocksAndCheckMerge(0, 1, 3, 1);
+
+  // +---+---+---+---+
+  // |   |   |   | _ |
+  // +---+---+---+---+
+  // |   |   |   | _ |
+  // +---+---+---+---+
+  // |   | X | X | _ |
+  // +---+---+---+---+
+  // | _ | _ | _ | _ |
+  // +---+---+---+---+
+  MarkBlocksAndCheckMerge(1, 2, 2, 1);
+}
+
+TEST_F(DifferTest, MergeBlocks_BlockColumn) {
+  // +---+---+---+---+
+  // | X |   |   | _ |
+  // +---+---+---+---+
+  // | X |   |   | _ |
+  // +---+---+---+---+
+  // |   |   |   | _ |
+  // +---+---+---+---+
+  // | _ | _ | _ | _ |
+  // +---+---+---+---+
+  MarkBlocksAndCheckMerge(0, 0, 1, 2);
+
+  // +---+---+---+---+
+  // |   |   |   | _ |
+  // +---+---+---+---+
+  // |   | X |   | _ |
+  // +---+---+---+---+
+  // |   | X |   | _ |
+  // +---+---+---+---+
+  // | _ | _ | _ | _ |
+  // +---+---+---+---+
+  MarkBlocksAndCheckMerge(1, 1, 1, 2);
+
+  // +---+---+---+---+
+  // |   |   | X | _ |
+  // +---+---+---+---+
+  // |   |   | X | _ |
+  // +---+---+---+---+
+  // |   |   | X | _ |
+  // +---+---+---+---+
+  // | _ | _ | _ | _ |
+  // +---+---+---+---+
+  MarkBlocksAndCheckMerge(2, 0, 1, 3);
+}
+
+TEST_F(DifferTest, MergeBlocks_BlockRect) {
+  // +---+---+---+---+
+  // | X | X |   | _ |
+  // +---+---+---+---+
+  // | X | X |   | _ |
+  // +---+---+---+---+
+  // |   |   |   | _ |
+  // +---+---+---+---+
+  // | _ | _ | _ | _ |
+  // +---+---+---+---+
+  MarkBlocksAndCheckMerge(0, 0, 2, 2);
+
+  // +---+---+---+---+
+  // |   |   |   | _ |
+  // +---+---+---+---+
+  // |   | X | X | _ |
+  // +---+---+---+---+
+  // |   | X | X | _ |
+  // +---+---+---+---+
+  // | _ | _ | _ | _ |
+  // +---+---+---+---+
+  MarkBlocksAndCheckMerge(1, 1, 2, 2);
+
+  // +---+---+---+---+
+  // |   | X | X | _ |
+  // +---+---+---+---+
+  // |   | X | X | _ |
+  // +---+---+---+---+
+  // |   | X | X | _ |
+  // +---+---+---+---+
+  // | _ | _ | _ | _ |
+  // +---+---+---+---+
+  MarkBlocksAndCheckMerge(1, 0, 2, 3);
+
+  // +---+---+---+---+
+  // |   |   |   | _ |
+  // +---+---+---+---+
+  // | X | X | X | _ |
+  // +---+---+---+---+
+  // | X | X | X | _ |
+  // +---+---+---+---+
+  // | _ | _ | _ | _ |
+  // +---+---+---+---+
+  MarkBlocksAndCheckMerge(0, 1, 3, 2);
+
+  // +---+---+---+---+
+  // | X | X | X | _ |
+  // +---+---+---+---+
+  // | X | X | X | _ |
+  // +---+---+---+---+
+  // | X | X | X | _ |
+  // +---+---+---+---+
+  // | _ | _ | _ | _ |
+  // +---+---+---+---+
+  MarkBlocksAndCheckMerge(0, 0, 3, 3);
+}
+
+// This tests marked regions that require more than 1 single dirty rect.
+// The exact rects returned depend on the current implementation, so these
+// may need to be updated if we modify how we merge blocks.
+TEST_F(DifferTest, MergeBlocks_MultiRect) {
+  DirtyRects* dirty;
+
+  // +---+---+---+---+      +---+---+---+
+  // |   | X |   | _ |      |   | 0 |   |
+  // +---+---+---+---+      +---+---+---+
+  // | X |   |   | _ |      | 1 |   |   |
+  // +---+---+---+---+  =>  +---+---+---+
+  // |   |   | X | _ |      |   |   | 2 |
+  // +---+---+---+---+      +---+---+---+
+  // | _ | _ | _ | _ |
+  // +---+---+---+---+
+  ClearDiffInfo();
+  MarkBlocks(1, 0, 1, 1);
+  MarkBlocks(0, 1, 1, 1);
+  MarkBlocks(2, 2, 1, 1);
+
+  dirty = new DirtyRects();
+  differ_->MergeBlocks(dirty);
+
+  ASSERT_EQ(3, dirty->size());
+  CheckDirtyRect(dirty->at(0), 1, 0, 1, 1);
+  CheckDirtyRect(dirty->at(1), 0, 1, 1, 1);
+  CheckDirtyRect(dirty->at(2), 2, 2, 1, 1);
+
+  // +---+---+---+---+      +---+---+---+
+  // |   |   | X | _ |      |   |   | 0 |
+  // +---+---+---+---+      +---+---+   +
+  // | X | X | X | _ |      | 1   1 | 0 |
+  // +---+---+---+---+  =>  +       +   +
+  // | X | X | X | _ |      | 1   1 | 0 |
+  // +---+---+---+---+      +---+---+---+
+  // | _ | _ | _ | _ |
+  // +---+---+---+---+
+  ClearDiffInfo();
+  MarkBlocks(2, 0, 1, 3);
+  MarkBlocks(0, 1, 2, 2);
+
+  dirty = new DirtyRects();
+  differ_->MergeBlocks(dirty);
+
+  ASSERT_EQ(2, dirty->size());
+  CheckDirtyRect(dirty->at(0), 2, 0, 1, 3);
+  CheckDirtyRect(dirty->at(1), 0, 1, 2, 2);
+
+  // +---+---+---+---+      +---+---+---+
+  // |   |   |   | _ |      |   |   |   |
+  // +---+---+---+---+      +---+---+---+
+  // | X |   | X | _ |      | 0 |   | 1 |
+  // +---+---+---+---+  =>  +   +---+   +
+  // | X | X | X | _ |      | 0 | 2 | 1 |
+  // +---+---+---+---+      +---+---+---+
+  // | _ | _ | _ | _ |
+  // +---+---+---+---+
+  ClearDiffInfo();
+  MarkBlocks(0, 1, 1, 1);
+  MarkBlocks(2, 1, 1, 1);
+  MarkBlocks(0, 2, 3, 1);
+
+  dirty = new DirtyRects();
+  differ_->MergeBlocks(dirty);
+
+  ASSERT_EQ(3, dirty->size());
+  CheckDirtyRect(dirty->at(0), 0, 1, 1, 2);
+  CheckDirtyRect(dirty->at(1), 2, 1, 1, 2);
+  CheckDirtyRect(dirty->at(2), 1, 2, 1, 1);
+
+  // +---+---+---+---+      +---+---+---+
+  // | X | X | X | _ |      | 0   0   0 |
+  // +---+---+---+---+      +---+---+---+
+  // | X |   | X | _ |      | 1 |   | 2 |
+  // +---+---+---+---+  =>  +   +---+   +
+  // | X | X | X | _ |      | 1 | 3 | 2 |
+  // +---+---+---+---+      +---+---+---+
+  // | _ | _ | _ | _ |
+  // +---+---+---+---+
+  ClearDiffInfo();
+  MarkBlocks(0, 0, 3, 1);
+  MarkBlocks(0, 1, 1, 1);
+  MarkBlocks(2, 1, 1, 1);
+  MarkBlocks(0, 2, 3, 1);
+
+  dirty = new DirtyRects();
+  differ_->MergeBlocks(dirty);
+
+  ASSERT_EQ(4, dirty->size());
+  CheckDirtyRect(dirty->at(0), 0, 0, 3, 1);
+  CheckDirtyRect(dirty->at(1), 0, 1, 1, 2);
+  CheckDirtyRect(dirty->at(2), 2, 1, 1, 2);
+  CheckDirtyRect(dirty->at(3), 1, 2, 1, 1);
+
+  // +---+---+---+---+      +---+---+---+
+  // | X | X |   | _ |      | 0   0 |   |
+  // +---+---+---+---+      +       +---+
+  // | X | X |   | _ |      | 0   0 |   |
+  // +---+---+---+---+  =>  +---+---+---+
+  // |   | X |   | _ |      |   | 1 |   |
+  // +---+---+---+---+      +---+---+---+
+  // | _ | _ | _ | _ |
+  // +---+---+---+---+
+  ClearDiffInfo();
+  MarkBlocks(0, 0, 2, 2);
+  MarkBlocks(1, 2, 1, 1);
+
+  dirty = new DirtyRects();
+  differ_->MergeBlocks(dirty);
+
+  ASSERT_EQ(2, dirty->size());
+  CheckDirtyRect(dirty->at(0), 0, 0, 2, 2);
+  CheckDirtyRect(dirty->at(1), 1, 2, 1, 1);
+}
+
+}  // namespace remoting