src/third_party/webrtc/modules/desktop_capture/differ.cc

   1 /*
   2  *  Copyright (c) 2013 The WebRTC project authors. All Rights Reserved.
   3  *
   4  *  Use of this source code is governed by a BSD-style license
   5  *  that can be found in the LICENSE file in the root of the source
   6  *  tree. An additional intellectual property rights grant can be found
   7  *  in the file PATENTS.  All contributing project authors may
   8  *  be found in the AUTHORS file in the root of the source tree.
   9  */
  10
  11 #include "webrtc/modules/desktop_capture/differ.h"
  12
  13 #include "string.h"
  14
  15 #include "webrtc/modules/desktop_capture/differ_block.h"
  16 #include "webrtc/system_wrappers/interface/logging.h"
  17
  18 namespace webrtc {
  19
  20 Differ::Differ(int width, int height, int bpp, int stride) {
  21   // Dimensions of screen.
  22   width_ = width;
  23   height_ = height;
  24   bytes_per_pixel_ = bpp;
  25   bytes_per_row_ = stride;
  26
  27   // Calc number of blocks (full and partial) required to cover entire image.
  28   // One additional row/column is added as a boundary on the right & bottom.
  29   diff_info_width_ = ((width_ + kBlockSize - 1) / kBlockSize) + 1;
  30   diff_info_height_ = ((height_ + kBlockSize - 1) / kBlockSize) + 1;
  31   diff_info_size_ = diff_info_width_ * diff_info_height_ * sizeof(DiffInfo);
  32   diff_info_.reset(new DiffInfo[diff_info_size_]);
  33 }
  34
  35 Differ::~Differ() {}
  36
  37 void Differ::CalcDirtyRegion(const void* prev_buffer, const void* curr_buffer,
  38                              DesktopRegion* region) {
  39   // Identify all the blocks that contain changed pixels.
  40   MarkDirtyBlocks(prev_buffer, curr_buffer);
  41
  42   // Now that we've identified the blocks that have changed, merge adjacent
  43   // blocks to minimize the number of rects that we return.
  44   MergeBlocks(region);
  45 }
  46
  47 void Differ::MarkDirtyBlocks(const void* prev_buffer, const void* curr_buffer) {
  48   memset(diff_info_.get(), 0, diff_info_size_);
  49
  50   // Calc number of full blocks.
  51   int x_full_blocks = width_ / kBlockSize;
  52   int y_full_blocks = height_ / kBlockSize;
  53
  54   // Calc size of partial blocks which may be present on right and bottom edge.
  55   int partial_column_width = width_ - (x_full_blocks * kBlockSize);
  56   int partial_row_height = height_ - (y_full_blocks * kBlockSize);
  57
  58   // Offset from the start of one block-column to the next.
  59   int block_x_offset = bytes_per_pixel_ * kBlockSize;
  60   // Offset from the start of one block-row to the next.
  61   int block_y_stride = (width_ * bytes_per_pixel_) * kBlockSize;
  62   // Offset from the start of one diff_info row to the next.
  63   int diff_info_stride = diff_info_width_ * sizeof(DiffInfo);
  64
  65   const uint8_t* prev_block_row_start =
  66       static_cast<const uint8_t*>(prev_buffer);
  67   const uint8_t* curr_block_row_start =
  68       static_cast<const uint8_t*>(curr_buffer);
  69   DiffInfo* diff_info_row_start = static_cast<DiffInfo*>(diff_info_.get());
  70
  71   for (int y = 0; y < y_full_blocks; y++) {
  72     const uint8_t* prev_block = prev_block_row_start;
  73     const uint8_t* curr_block = curr_block_row_start;
  74     DiffInfo* diff_info = diff_info_row_start;
  75
  76     for (int x = 0; x < x_full_blocks; x++) {
  77       // Mark this block as being modified so that it gets incorporated into
  78       // a dirty rect.
  79       *diff_info = BlockDifference(prev_block, curr_block, bytes_per_row_);
  80       prev_block += block_x_offset;
  81       curr_block += block_x_offset;
  82       diff_info += sizeof(DiffInfo);
  83     }
  84
  85     // If there is a partial column at the end, handle it.
  86     // This condition should rarely, if ever, occur.
  87     if (partial_column_width != 0) {
  88       *diff_info = DiffPartialBlock(prev_block, curr_block, bytes_per_row_,
  89                                     partial_column_width, kBlockSize);
  90       diff_info += sizeof(DiffInfo);
  91     }
  92
  93     // Update pointers for next row.
  94     prev_block_row_start += block_y_stride;
  95     curr_block_row_start += block_y_stride;
  96     diff_info_row_start += diff_info_stride;
  97   }
  98
  99   // If the screen height is not a multiple of the block size, then this
 100   // handles the last partial row. This situation is far more common than the
 101   // 'partial column' case.
 102   if (partial_row_height != 0) {
 103     const uint8_t* prev_block = prev_block_row_start;
 104     const uint8_t* curr_block = curr_block_row_start;
 105     DiffInfo* diff_info = diff_info_row_start;
 106     for (int x = 0; x < x_full_blocks; x++) {
 107       *diff_info = DiffPartialBlock(prev_block, curr_block,
 108                                     bytes_per_row_,
 109                                     kBlockSize, partial_row_height);
 110       prev_block += block_x_offset;
 111       curr_block += block_x_offset;
 112       diff_info += sizeof(DiffInfo);
 113     }
 114     if (partial_column_width != 0) {
 115       *diff_info = DiffPartialBlock(prev_block, curr_block, bytes_per_row_,
 116                                     partial_column_width, partial_row_height);
 117       diff_info += sizeof(DiffInfo);
 118     }
 119   }
 120 }
 121
 122 DiffInfo Differ::DiffPartialBlock(const uint8_t* prev_buffer,
 123                                   const uint8_t* curr_buffer,
 124                                   int stride, int width, int height) {
 125   int width_bytes = width * bytes_per_pixel_;
 126   for (int y = 0; y < height; y++) {
 127     if (memcmp(prev_buffer, curr_buffer, width_bytes) != 0)
 128       return 1;
 129     prev_buffer += bytes_per_row_;
 130     curr_buffer += bytes_per_row_;
 131   }
 132   return 0;
 133 }
 134
 135 void Differ::MergeBlocks(DesktopRegion* region) {
 136   region->Clear();
 137
 138   uint8_t* diff_info_row_start = static_cast<uint8_t*>(diff_info_.get());
 139   int diff_info_stride = diff_info_width_ * sizeof(DiffInfo);
 140
 141   for (int y = 0; y < diff_info_height_; y++) {
 142     uint8_t* diff_info = diff_info_row_start;
 143     for (int x = 0; x < diff_info_width_; x++) {
 144       if (*diff_info != 0) {
 145         // We've found a modified block. Look at blocks to the right and below
 146         // to group this block with as many others as we can.
 147         int left = x * kBlockSize;
 148         int top = y * kBlockSize;
 149         int width = 1;
 150         int height = 1;
 151         *diff_info = 0;
 152
 153         // Group with blocks to the right.
 154         // We can keep looking until we find an unchanged block because we
 155         // have a boundary block which is never marked as having diffs.
 156         uint8_t* right = diff_info + 1;
 157         while (*right) {
 158           *right++ = 0;
 159           width++;
 160         }
 161
 162         // Group with blocks below.
 163         // The entire width of blocks that we matched above much match for
 164         // each row that we add.
 165         uint8_t* bottom = diff_info;
 166         bool found_new_row;
 167         do {
 168           found_new_row = true;
 169           bottom += diff_info_stride;
 170           right = bottom;
 171           for (int x2 = 0; x2 < width; x2++) {
 172             if (*right++ == 0) {
 173               found_new_row = false;
 174             }
 175           }
 176
 177           if (found_new_row) {
 178             height++;
 179
 180             // We need to go back and erase the diff markers so that we don't
 181             // try to add these blocks a second time.
 182             right = bottom;
 183             for (int x2 = 0; x2 < width; x2++) {
 184               *right++ = 0;
 185             }
 186           }
 187         } while (found_new_row);
 188
 189         // Add rect to list of dirty rects.
 190         width *= kBlockSize;
 191         if (left + width > width_) {
 192           width = width_ - left;
 193         }
 194         height *= kBlockSize;
 195         if (top + height > height_) {
 196           height = height_ - top;
 197         }
 198         region->AddRect(DesktopRect::MakeXYWH(left, top, width, height));
 199       }
 200
 201       // Increment to next block in this row.
 202       diff_info++;
 203     }
 204
 205     // Go to start of next row.
 206     diff_info_row_start += diff_info_stride;
 207   }
 208 }
 209
 210 }  // namespace webrtc