blob: 0ec673496236f2cc0bb64abe4fcae65a73b12a5f [file] [log] [blame]
Constantin Kaplinsky9ee8dc62007-10-09 07:46:32 +00001/* Copyright (C) 2004-2007 Constantin Kaplinsky. All Rights Reserved.
Constantin Kaplinskyb30ae7f2006-05-25 05:04:46 +00002 *
3 * This is free software; you can redistribute it and/or modify
4 * it under the terms of the GNU General Public License as published by
5 * the Free Software Foundation; either version 2 of the License, or
6 * (at your option) any later version.
7 *
8 * This software is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public License
14 * along with this software; if not, write to the Free Software
15 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
16 * USA.
17 */
18//
19// PollingManager.cxx
20//
21
Constantin Kaplinskyb30ae7f2006-05-25 05:04:46 +000022#include <stdio.h>
23#include <string.h>
24#include <time.h>
25#include <X11/Xlib.h>
26#include <rfb/LogWriter.h>
27#include <rfb/VNCServer.h>
28#include <rfb/Configuration.h>
29#include <rfb/ServerCore.h>
30
31#include <x0vncserver/PollingManager.h>
32
33static LogWriter vlog("PollingMgr");
34
Constantin Kaplinskyb30ae7f2006-05-25 05:04:46 +000035const int PollingManager::m_pollingOrder[32] = {
36 0, 16, 8, 24, 4, 20, 12, 28,
37 10, 26, 18, 2, 22, 6, 30, 14,
38 1, 17, 9, 25, 7, 23, 15, 31,
39 19, 3, 27, 11, 29, 13, 5, 21
40};
41
42//
43// Constructor.
44//
45// Note that dpy and image should remain valid during the object
46// lifetime, while factory is used only in the constructor itself.
47//
48
49PollingManager::PollingManager(Display *dpy, Image *image,
50 ImageFactory *factory,
51 int offsetLeft, int offsetTop)
52 : m_dpy(dpy), m_server(0), m_image(image),
53 m_offsetLeft(offsetLeft), m_offsetTop(offsetTop),
Constantin Kaplinskyd0b15c62007-10-09 08:15:25 +000054 m_pollingStep(0)
Constantin Kaplinskyb30ae7f2006-05-25 05:04:46 +000055{
56 // Save width and height of the screen (and the image).
57 m_width = m_image->xim->width;
58 m_height = m_image->xim->height;
59
60 // Compute width and height in 32x32 tiles.
61 m_widthTiles = (m_width + 31) / 32;
62 m_heightTiles = (m_height + 31) / 32;
63
64 // Get initial screen image.
65 m_image->get(DefaultRootWindow(m_dpy), m_offsetLeft, m_offsetTop);
66
Constantin Kaplinsky9ee8dc62007-10-09 07:46:32 +000067 // Create additional images used in polling algorithm, warn if
Constantin Kaplinskyb30ae7f2006-05-25 05:04:46 +000068 // underlying class names are different from the class name of the
69 // primary image.
70 m_rowImage = factory->newImage(m_dpy, m_width, 1);
Constantin Kaplinskyd0b15c62007-10-09 08:15:25 +000071 if (strcmp(m_image->className(), m_rowImage->className()) != 0) {
72 vlog.error("Image types do not match (%s)",
73 m_rowImage->className());
Constantin Kaplinskyb30ae7f2006-05-25 05:04:46 +000074 }
75
Constantin Kaplinskyb30ae7f2006-05-25 05:04:46 +000076 int numTiles = m_widthTiles * m_heightTiles;
Constantin Kaplinskyb30ae7f2006-05-25 05:04:46 +000077 m_rateMatrix = new char[numTiles];
78 m_videoFlags = new char[numTiles];
Constantin Kaplinskyb30ae7f2006-05-25 05:04:46 +000079 memset(m_rateMatrix, 0, numTiles);
80 memset(m_videoFlags, 0, numTiles);
Constantin Kaplinskyb30ae7f2006-05-25 05:04:46 +000081}
82
83PollingManager::~PollingManager()
84{
Constantin Kaplinskyb30ae7f2006-05-25 05:04:46 +000085 delete[] m_videoFlags;
86 delete[] m_rateMatrix;
87
Constantin Kaplinskyb30ae7f2006-05-25 05:04:46 +000088 delete m_rowImage;
89}
90
91//
92// Register VNCServer object.
93//
94
95void PollingManager::setVNCServer(VNCServer *s)
96{
97 m_server = s;
98}
99
100//
Constantin Kaplinskyb30ae7f2006-05-25 05:04:46 +0000101// DEBUG: Measuring time spent in the poll() function,
102// as well as time intervals between poll() calls.
103//
104
105#ifdef DEBUG
106void PollingManager::debugBeforePoll()
107{
108 TimeMillis timeNow;
109 int diff = timeNow.diffFrom(m_timeSaved);
110 fprintf(stderr, "[wait%4dms]\t[step %2d]\t", diff, m_pollingStep % 32);
111 m_timeSaved = timeNow;
112}
113
114void PollingManager::debugAfterPoll()
115{
116 TimeMillis timeNow;
117 int diff = timeNow.diffFrom(m_timeSaved);
118 fprintf(stderr, "[poll%4dms]\n", diff);
119 m_timeSaved = timeNow;
120}
121
122#endif
123
124//
125// Search for changed rectangles on the screen.
126//
127
128void PollingManager::poll()
129{
130#ifdef DEBUG
131 debugBeforePoll();
132#endif
133
Constantin Kaplinskyd0b15c62007-10-09 08:15:25 +0000134 // Perform polling and try update clients if changes were detected.
135 if (pollScreen())
Constantin Kaplinskyb30ae7f2006-05-25 05:04:46 +0000136 m_server->tryUpdate();
137
138#ifdef DEBUG
139 debugAfterPoll();
140#endif
141}
142
Constantin Kaplinsky9ee8dc62007-10-09 07:46:32 +0000143bool PollingManager::pollScreen()
Constantin Kaplinskya119b482007-10-04 06:02:02 +0000144{
145 if (!m_server)
146 return false;
147
Constantin Kaplinskybc6b9e22007-10-04 11:43:41 +0000148 // mxChanged[] array will hold boolean values corresponding to each
149 // 32x32 tile. If a value is true, then we've detected a change in
Constantin Kaplinsky5e2f69f2007-10-07 13:08:18 +0000150 // that tile. Initially, we fill in the array with zero values.
Constantin Kaplinskya119b482007-10-04 06:02:02 +0000151 bool *mxChanged = new bool[m_widthTiles * m_heightTiles];
Constantin Kaplinskyf25307a2007-10-08 13:49:44 +0000152 memset(mxChanged, 0, m_widthTiles * m_heightTiles * sizeof(bool));
Constantin Kaplinskya119b482007-10-04 06:02:02 +0000153
Constantin Kaplinskybc6b9e22007-10-04 11:43:41 +0000154 // First pass over the framebuffer. Here we scan 1/32 part of the
155 // framebuffer -- that is, one line in each (32 * m_width) stripe.
156 // We compare the pixels of that line with previous framebuffer
157 // contents and raise corresponding member values of mxChanged[].
158 int scanOffset = m_pollingOrder[m_pollingStep++ % 32];
159 bool *pmxChanged = mxChanged;
Constantin Kaplinskya119b482007-10-04 06:02:02 +0000160 int nTilesChanged = 0;
Constantin Kaplinskybc6b9e22007-10-04 11:43:41 +0000161 for (int y = scanOffset; y < m_height; y += 32) {
162 nTilesChanged += checkRow(0, y, m_width, pmxChanged);
163 pmxChanged += m_widthTiles;
Constantin Kaplinskya119b482007-10-04 06:02:02 +0000164 }
165
Constantin Kaplinskyc1984e02007-10-08 14:54:18 +0000166 // Do the work related to video area detection.
167 bool videoDetected = detectVideo(mxChanged);
168
Constantin Kaplinskya119b482007-10-04 06:02:02 +0000169 // Inform the server about the changes.
Constantin Kaplinskya79255b2007-10-07 13:03:55 +0000170 if (nTilesChanged)
171 sendChanges(mxChanged);
Constantin Kaplinskya119b482007-10-04 06:02:02 +0000172
173 // Cleanup.
174 delete[] mxChanged;
175
Constantin Kaplinskyc1984e02007-10-08 14:54:18 +0000176#ifdef DEBUG
177 if (nTilesChanged != 0) {
178 fprintf(stderr, "#%d# ", nTilesChanged);
179 }
180#endif
181
182 return (nTilesChanged != 0 || videoDetected);
Constantin Kaplinskya119b482007-10-04 06:02:02 +0000183}
184
Constantin Kaplinskybc6b9e22007-10-04 11:43:41 +0000185int PollingManager::checkRow(int x, int y, int w, bool *pmxChanged)
186{
187 int bytesPerPixel = m_image->xim->bits_per_pixel / 8;
188 int bytesPerLine = m_image->xim->bytes_per_line;
189
Constantin Kaplinsky29d32052007-10-08 14:16:02 +0000190 if (x == 0 && w == m_width) {
191 getFullRow(y); // use more efficient method if possible
192 } else {
193 getRow(x, y, w);
194 }
Constantin Kaplinskybc6b9e22007-10-04 11:43:41 +0000195
196 char *ptr_old = m_image->xim->data + y * bytesPerLine + x * bytesPerPixel;
197 char *ptr_new = m_rowImage->xim->data;
198
199 int nTilesChanged = 0;
200 for (int i = 0; i < (w + 31) / 32; i++) {
201 int tile_w = (w - i * 32 >= 32) ? 32 : w - i * 32;
202 int nBytes = tile_w * bytesPerPixel;
203 if (memcmp(ptr_old, ptr_new, nBytes)) {
204 *pmxChanged = true;
205 nTilesChanged++;
206 }
207 pmxChanged++;
208 ptr_old += nBytes;
209 ptr_new += nBytes;
210 }
211
212 return nTilesChanged;
213}
214
Constantin Kaplinskya79255b2007-10-07 13:03:55 +0000215void PollingManager::sendChanges(bool *pmxChanged)
216{
217 Rect rect;
218 for (int y = 0; y < m_heightTiles; y++) {
219 for (int x = 0; x < m_widthTiles; x++) {
220 if (*pmxChanged++) {
221 // Count successive tiles marked as changed.
222 int count = 1;
223 while (x + count < m_widthTiles && *pmxChanged++) {
224 count++;
225 }
226 // Compute the coordinates and the size of this band.
227 rect.setXYWH(x * 32, y * 32, count * 32, 32);
228 if (rect.br.x > m_width)
229 rect.br.x = m_width;
230 if (rect.br.y > m_height)
231 rect.br.y = m_height;
232 // Add to the changed region maintained by the server.
233 getScreenRect(rect);
234 m_server->add_changed(rect);
235 // Skip processed tiles.
236 x += count;
237 }
238 }
239 }
240}
241
Constantin Kaplinskyc1984e02007-10-08 14:54:18 +0000242bool PollingManager::detectVideo(bool *pmxChanged)
243{
244 // Configurable parameters.
245 const int VIDEO_THRESHOLD_0 = 3;
246 const int VIDEO_THRESHOLD_1 = 5;
247
248 // Each call: update counters in m_rateMatrix.
249 int numTiles = m_heightTiles * m_widthTiles;
250 for (int i = 0; i < numTiles; i++)
251 m_rateMatrix[i] += (pmxChanged[i] != false);
252
Constantin Kaplinsky646998a2007-10-09 09:31:41 +0000253 // Once per eight calls: detect video rectangle.
Constantin Kaplinskyc1984e02007-10-08 14:54:18 +0000254 bool isGrandStep = (m_pollingStep % 8 == 0);
255 if (isGrandStep) {
Constantin Kaplinsky646998a2007-10-09 09:31:41 +0000256 //
257 // First, detect candidate region that looks like video. In other
258 // words, find a region that consists of continuously changing
259 // pixels. Save the result in m_videoFlags[] and reset counters in
260 // m_rateMatrix[].
261 //
Constantin Kaplinskyc1984e02007-10-08 14:54:18 +0000262 for (int i = 0; i < numTiles; i++) {
263 if (m_rateMatrix[i] <= VIDEO_THRESHOLD_0) {
264 m_videoFlags[i] = 0;
265 } else if (m_rateMatrix[i] >= VIDEO_THRESHOLD_1) {
266 m_videoFlags[i] = 1;
267 }
268 m_rateMatrix[i] = 0;
269 }
Constantin Kaplinsky646998a2007-10-09 09:31:41 +0000270 //
271 // Now, choose the biggest rectangle from that candidate region.
272 //
273 Rect newRect;
274 getVideoAreaRect(&newRect);
275 //
276 // Does new rectangle differ from the previously detected one?
277 // If it does, save new rectangle and inform the server.
278 //
279 if (!newRect.equals(m_videoRect)) {
280 if (newRect.is_empty()) {
281 fprintf(stderr, "No video detected\n");
282 } else {
283 fprintf(stderr, "Video rect %dx%d\tat(%d,%d)\n",
284 newRect.width(), newRect.height(), newRect.tl.x, newRect.tl.y);
285 }
286 m_videoRect = newRect;
287 m_server->set_video_area(newRect);
Constantin Kaplinskyc1984e02007-10-08 14:54:18 +0000288 }
289 }
290
Constantin Kaplinsky646998a2007-10-09 09:31:41 +0000291 // Grab the pixels of video area. Also, exclude video rectangle from
292 // pmxChanged[], to prevent grabbing the same pixels twice.
293 if (!m_videoRect.is_empty()) {
294 Rect r(m_videoRect.tl.x / 32, m_videoRect.tl.y / 32,
295 m_videoRect.br.x / 32, m_videoRect.br.y / 32);
296 for (int y = r.tl.y; y < r.br.y; y++) {
297 for (int x = r.tl.x; x < r.br.x; x++) {
298 pmxChanged[y * m_widthTiles + x] = false;
299 }
300 }
301 getScreenRect(m_videoRect);
302 return true; // we've got a video rectangle
303 }
Constantin Kaplinskyc1984e02007-10-08 14:54:18 +0000304
Constantin Kaplinsky646998a2007-10-09 09:31:41 +0000305 return false; // video rectangle is empty
Constantin Kaplinskyc1984e02007-10-08 14:54:18 +0000306}
307
Constantin Kaplinsky56649982007-09-04 09:15:35 +0000308void
309PollingManager::getVideoAreaRect(Rect *result)
310{
Constantin Kaplinsky0fc9f172007-09-29 04:00:02 +0000311 int *mx_hlen, *mx_vlen;
312 constructLengthMatrices(&mx_hlen, &mx_vlen);
Constantin Kaplinsky56649982007-09-04 09:15:35 +0000313
Constantin Kaplinsky0fc9f172007-09-29 04:00:02 +0000314 int full_h = m_heightTiles;
315 int full_w = m_widthTiles;
316 int x, y;
317 Rect max_rect(0, 0, 0, 0);
318 Rect local_rect;
319
320 for (y = 0; y < full_h; y++) {
321 for (x = 0; x < full_w; x++) {
322 int max_w = mx_hlen[y * full_w + x];
323 int max_h = mx_vlen[y * full_w + x];
324 if (max_w > 2 && max_h > 1 && max_h * max_w > (int)max_rect.area()) {
325 local_rect.tl.x = x;
326 local_rect.tl.y = y;
327 findMaxLocalRect(&local_rect, mx_hlen, mx_vlen);
328 if (local_rect.area() > max_rect.area()) {
329 max_rect = local_rect;
330 }
331 }
Constantin Kaplinsky56649982007-09-04 09:15:35 +0000332 }
333 }
334
Constantin Kaplinsky0fc9f172007-09-29 04:00:02 +0000335 destroyLengthMatrices(mx_hlen, mx_vlen);
Constantin Kaplinsky56649982007-09-04 09:15:35 +0000336
Constantin Kaplinsky0fc9f172007-09-29 04:00:02 +0000337 max_rect.tl.x *= 32;
338 max_rect.tl.y *= 32;
339 max_rect.br.x *= 32;
340 max_rect.br.y *= 32;
341 if (max_rect.br.x > m_width)
342 max_rect.br.x = m_width;
343 if (max_rect.br.y > m_height)
344 max_rect.br.y = m_height;
345 *result = max_rect;
Constantin Kaplinsky56649982007-09-04 09:15:35 +0000346}
Constantin Kaplinsky0fc9f172007-09-29 04:00:02 +0000347
348void
349PollingManager::constructLengthMatrices(int **pmx_h, int **pmx_v)
350{
351 // Handy shortcuts.
352 int h = m_heightTiles;
353 int w = m_widthTiles;
354
355 // Allocate memory.
356 int *mx_h = new int[h * w];
357 memset(mx_h, 0, h * w * sizeof(int));
358 int *mx_v = new int[h * w];
359 memset(mx_v, 0, h * w * sizeof(int));
360
361 int x, y, len, i;
362
363 // Fill in horizontal length matrix.
364 for (y = 0; y < h; y++) {
365 for (x = 0; x < w; x++) {
366 len = 0;
367 while (x + len < w && m_videoFlags[y * w + x + len]) {
368 len++;
369 }
370 for (i = 0; i < len; i++) {
371 mx_h[y * w + x + i] = len - i;
372 }
373 x += len;
374 }
375 }
376
377 // Fill in vertical length matrix.
378 for (x = 0; x < w; x++) {
379 for (y = 0; y < h; y++) {
380 len = 0;
381 while (y + len < h && m_videoFlags[(y + len) * w + x]) {
382 len++;
383 }
384 for (i = 0; i < len; i++) {
385 mx_v[(y + i) * w + x] = len - i;
386 }
387 y += len;
388 }
389 }
390
391 *pmx_h = mx_h;
392 *pmx_v = mx_v;
393}
394
395void
396PollingManager::destroyLengthMatrices(int *mx_h, int *mx_v)
397{
398 delete[] mx_h;
399 delete[] mx_v;
400}
401
402// NOTE: This function assumes that current tile has non-zero in mx_h[],
403// otherwise we get division by zero.
404void
405PollingManager::findMaxLocalRect(Rect *r, int mx_h[], int mx_v[])
406{
407 int idx = r->tl.y * m_widthTiles + r->tl.x;
408
409 // NOTE: Rectangle's maximum width and height are 25 and 18
410 // (in tiles, where each tile is usually 32x32 pixels).
411 int max_w = mx_h[idx];
412 if (max_w > 25)
413 max_w = 25;
414 int cur_h = 18;
415
416 int best_w = max_w;
417 int best_area = 1 * best_w;
418
419 for (int i = 0; i < max_w; i++) {
420 int h = mx_v[idx + i];
421 if (h < cur_h) {
422 cur_h = h;
423 if (cur_h * max_w <= best_area)
424 break;
425 }
426 if (cur_h * (i + 1) > best_area) {
427 best_w = i + 1;
428 best_area = cur_h * best_w;
429 }
430 }
431
432 r->br.x = r->tl.x + best_w;
433 r->br.y = r->tl.y + best_area / best_w;
434}
435