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/include/logging.h"
17
18 namespace webrtc {
19
Differ(int width,int height,int bpp,int stride)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(bool);
32 diff_info_.reset(new bool[diff_info_size_]);
33 }
34
~Differ()35 Differ::~Differ() {}
36
CalcDirtyRegion(const uint8_t * prev_buffer,const uint8_t * curr_buffer,DesktopRegion * region)37 void Differ::CalcDirtyRegion(const uint8_t* prev_buffer,
38 const uint8_t* curr_buffer,
39 DesktopRegion* region) {
40 // Identify all the blocks that contain changed pixels.
41 MarkDirtyBlocks(prev_buffer, curr_buffer);
42
43 // Now that we've identified the blocks that have changed, merge adjacent
44 // blocks to minimize the number of rects that we return.
45 MergeBlocks(region);
46 }
47
MarkDirtyBlocks(const uint8_t * prev_buffer,const uint8_t * curr_buffer)48 void Differ::MarkDirtyBlocks(const uint8_t* prev_buffer,
49 const uint8_t* curr_buffer) {
50 memset(diff_info_.get(), 0, diff_info_size_);
51
52 // Calc number of full blocks.
53 int x_full_blocks = width_ / kBlockSize;
54 int y_full_blocks = height_ / kBlockSize;
55
56 // Calc size of partial blocks which may be present on right and bottom edge.
57 int partial_column_width = width_ - (x_full_blocks * kBlockSize);
58 int partial_row_height = height_ - (y_full_blocks * kBlockSize);
59
60 // Offset from the start of one block-column to the next.
61 int block_x_offset = bytes_per_pixel_ * kBlockSize;
62 // Offset from the start of one block-row to the next.
63 int block_y_stride = (width_ * bytes_per_pixel_) * kBlockSize;
64 // Offset from the start of one diff_info row to the next.
65 int diff_info_stride = diff_info_width_ * sizeof(bool);
66
67 const uint8_t* prev_block_row_start = prev_buffer;
68 const uint8_t* curr_block_row_start = curr_buffer;
69 bool* diff_info_row_start = 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 bool* 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(bool);
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 = !PartialBlocksEqual(prev_block, curr_block, bytes_per_row_,
89 partial_column_width, kBlockSize);
90 diff_info += sizeof(bool);
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 bool* diff_info = diff_info_row_start;
106 for (int x = 0; x < x_full_blocks; x++) {
107 *diff_info = !PartialBlocksEqual(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(bool);
113 }
114 if (partial_column_width != 0) {
115 *diff_info = !PartialBlocksEqual(prev_block, curr_block, bytes_per_row_,
116 partial_column_width,
117 partial_row_height);
118 diff_info += sizeof(bool);
119 }
120 }
121 }
122
PartialBlocksEqual(const uint8_t * prev_buffer,const uint8_t * curr_buffer,int stride,int width,int height)123 bool Differ::PartialBlocksEqual(const uint8_t* prev_buffer,
124 const uint8_t* curr_buffer,
125 int stride, int width, int height) {
126 int width_bytes = width * bytes_per_pixel_;
127 for (int y = 0; y < height; y++) {
128 if (memcmp(prev_buffer, curr_buffer, width_bytes) != 0)
129 return false;
130 prev_buffer += bytes_per_row_;
131 curr_buffer += bytes_per_row_;
132 }
133 return true;
134 }
135
MergeBlocks(DesktopRegion * region)136 void Differ::MergeBlocks(DesktopRegion* region) {
137 region->Clear();
138
139 bool* diff_info_row_start = diff_info_.get();
140 int diff_info_stride = diff_info_width_ * sizeof(bool);
141
142 for (int y = 0; y < diff_info_height_; y++) {
143 bool* diff_info = diff_info_row_start;
144 for (int x = 0; x < diff_info_width_; x++) {
145 if (*diff_info) {
146 // We've found a modified block. Look at blocks to the right and below
147 // to group this block with as many others as we can.
148 int left = x * kBlockSize;
149 int top = y * kBlockSize;
150 int width = 1;
151 int height = 1;
152 *diff_info = false;
153
154 // Group with blocks to the right.
155 // We can keep looking until we find an unchanged block because we
156 // have a boundary block which is never marked as having diffs.
157 bool* right = diff_info + 1;
158 while (*right) {
159 *right++ = false;
160 width++;
161 }
162
163 // Group with blocks below.
164 // The entire width of blocks that we matched above much match for
165 // each row that we add.
166 bool* bottom = diff_info;
167 bool found_new_row;
168 do {
169 found_new_row = true;
170 bottom += diff_info_stride;
171 right = bottom;
172 for (int x2 = 0; x2 < width; x2++) {
173 if (!*right++) {
174 found_new_row = false;
175 }
176 }
177
178 if (found_new_row) {
179 height++;
180
181 // We need to go back and erase the diff markers so that we don't
182 // try to add these blocks a second time.
183 right = bottom;
184 for (int x2 = 0; x2 < width; x2++) {
185 *right++ = false;
186 }
187 }
188 } while (found_new_row);
189
190 // Add rect to list of dirty rects.
191 width *= kBlockSize;
192 if (left + width > width_) {
193 width = width_ - left;
194 }
195 height *= kBlockSize;
196 if (top + height > height_) {
197 height = height_ - top;
198 }
199 region->AddRect(DesktopRect::MakeXYWH(left, top, width, height));
200 }
201
202 // Increment to next block in this row.
203 diff_info++;
204 }
205
206 // Go to start of next row.
207 diff_info_row_start += diff_info_stride;
208 }
209 }
210
211 } // namespace webrtc
212