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
18namespace webrtc {
19
20Differ::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
35Differ::~Differ() {}
36
37void 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
47void 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
122DiffInfo 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
135void 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
211