LibVNCServer/LibVNCClient
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
corre.c
Go to the documentation of this file.
1 /*
2  * corre.c
3  *
4  * Routines to implement Compact Rise-and-Run-length Encoding (CoRRE). This
5  * code is based on krw's original javatel rfbserver.
6  */
7 
8 /*
9  * Copyright (C) 2002 RealVNC Ltd.
10  * OSXvnc Copyright (C) 2001 Dan McGuirk <mcguirk@incompleteness.net>.
11  * Original Xvnc code Copyright (C) 1999 AT&T Laboratories Cambridge.
12  * All Rights Reserved.
13  *
14  * This is free software; you can redistribute it and/or modify
15  * it under the terms of the GNU General Public License as published by
16  * the Free Software Foundation; either version 2 of the License, or
17  * (at your option) any later version.
18  *
19  * This software is distributed in the hope that it will be useful,
20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22  * GNU General Public License for more details.
23  *
24  * You should have received a copy of the GNU General Public License
25  * along with this software; if not, write to the Free Software
26  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
27  * USA.
28  */
29 
30 #include <rfb/rfb.h>
31 
32 /*
33  * cl->beforeEncBuf contains pixel data in the client's format.
34  * cl->afterEncBuf contains the RRE encoded version. If the RRE encoded version is
35  * larger than the raw data or if it exceeds cl->afterEncBufSize then
36  * raw encoding is used instead.
37  */
38 
39 static int subrectEncode8(rfbClientPtr cl, uint8_t *data, int w, int h);
40 static int subrectEncode16(rfbClientPtr cl, uint16_t *data, int w, int h);
41 static int subrectEncode32(rfbClientPtr cl, uint32_t *data, int w, int h);
42 static uint32_t getBgColour(char *data, int size, int bpp);
43 static rfbBool rfbSendSmallRectEncodingCoRRE(rfbClientPtr cl, int x, int y,
44  int w, int h);
45 
46 
47 /*
48  * rfbSendRectEncodingCoRRE - send an arbitrary size rectangle using CoRRE
49  * encoding.
50  */
51 
52 rfbBool
53 rfbSendRectEncodingCoRRE(rfbClientPtr cl,
54  int x,
55  int y,
56  int w,
57  int h)
58 {
59  if (h > cl->correMaxHeight) {
60  return (rfbSendRectEncodingCoRRE(cl, x, y, w, cl->correMaxHeight) &&
61  rfbSendRectEncodingCoRRE(cl, x, y + cl->correMaxHeight, w,
62  h - cl->correMaxHeight));
63  }
64 
65  if (w > cl->correMaxWidth) {
66  return (rfbSendRectEncodingCoRRE(cl, x, y, cl->correMaxWidth, h) &&
67  rfbSendRectEncodingCoRRE(cl, x + cl->correMaxWidth, y,
68  w - cl->correMaxWidth, h));
69  }
70 
71  rfbSendSmallRectEncodingCoRRE(cl, x, y, w, h);
72  return TRUE;
73 }
74 
75 
76 
77 /*
78  * rfbSendSmallRectEncodingCoRRE - send a small (guaranteed < 256x256)
79  * rectangle using CoRRE encoding.
80  */
81 
82 static rfbBool
83 rfbSendSmallRectEncodingCoRRE(rfbClientPtr cl,
84  int x,
85  int y,
86  int w,
87  int h)
88 {
90  rfbRREHeader hdr;
91  int nSubrects;
92  int i;
93  char *fbptr = (cl->scaledScreen->frameBuffer + (cl->scaledScreen->paddedWidthInBytes * y)
94  + (x * (cl->scaledScreen->bitsPerPixel / 8)));
95 
96  int maxRawSize = (cl->scaledScreen->width * cl->scaledScreen->height
97  * (cl->format.bitsPerPixel / 8));
98 
99  if (cl->beforeEncBufSize < maxRawSize) {
100  cl->beforeEncBufSize = maxRawSize;
101  if (cl->beforeEncBuf == NULL)
102  cl->beforeEncBuf = (char *)malloc(cl->beforeEncBufSize);
103  else
104  cl->beforeEncBuf = (char *)realloc(cl->beforeEncBuf, cl->beforeEncBufSize);
105  }
106 
107  if (cl->afterEncBufSize < maxRawSize) {
108  cl->afterEncBufSize = maxRawSize;
109  if (cl->afterEncBuf == NULL)
110  cl->afterEncBuf = (char *)malloc(cl->afterEncBufSize);
111  else
112  cl->afterEncBuf = (char *)realloc(cl->afterEncBuf, cl->afterEncBufSize);
113  }
114 
115  (*cl->translateFn)(cl->translateLookupTable,&(cl->screen->serverFormat),
116  &cl->format, fbptr, cl->beforeEncBuf,
117  cl->scaledScreen->paddedWidthInBytes, w, h);
118 
119  switch (cl->format.bitsPerPixel) {
120  case 8:
121  nSubrects = subrectEncode8(cl, (uint8_t *)cl->beforeEncBuf, w, h);
122  break;
123  case 16:
124  nSubrects = subrectEncode16(cl, (uint16_t *)cl->beforeEncBuf, w, h);
125  break;
126  case 32:
127  nSubrects = subrectEncode32(cl, (uint32_t *)cl->beforeEncBuf, w, h);
128  break;
129  default:
130  rfbLog("getBgColour: bpp %d?\n",cl->format.bitsPerPixel);
131  return FALSE;
132  }
133 
134  if (nSubrects < 0) {
135 
136  /* RRE encoding was too large, use raw */
137 
138  return rfbSendRectEncodingRaw(cl, x, y, w, h);
139  }
140 
142  sz_rfbFramebufferUpdateRectHeader + sz_rfbRREHeader + cl->afterEncBufLen,
143  sz_rfbFramebufferUpdateRectHeader + w * h * (cl->format.bitsPerPixel / 8));
144 
146  > UPDATE_BUF_SIZE)
147  {
148  if (!rfbSendUpdateBuf(cl))
149  return FALSE;
150  }
151 
152  rect.r.x = Swap16IfLE(x);
153  rect.r.y = Swap16IfLE(y);
154  rect.r.w = Swap16IfLE(w);
155  rect.r.h = Swap16IfLE(h);
157 
158  memcpy(&cl->updateBuf[cl->ublen], (char *)&rect,
161 
162  hdr.nSubrects = Swap32IfLE(nSubrects);
163 
164  memcpy(&cl->updateBuf[cl->ublen], (char *)&hdr, sz_rfbRREHeader);
165  cl->ublen += sz_rfbRREHeader;
166 
167  for (i = 0; i < cl->afterEncBufLen;) {
168 
169  int bytesToCopy = UPDATE_BUF_SIZE - cl->ublen;
170 
171  if (i + bytesToCopy > cl->afterEncBufLen) {
172  bytesToCopy = cl->afterEncBufLen - i;
173  }
174 
175  memcpy(&cl->updateBuf[cl->ublen], &cl->afterEncBuf[i], bytesToCopy);
176 
177  cl->ublen += bytesToCopy;
178  i += bytesToCopy;
179 
180  if (cl->ublen == UPDATE_BUF_SIZE) {
181  if (!rfbSendUpdateBuf(cl))
182  return FALSE;
183  }
184  }
185 
186  return TRUE;
187 }
188 
189 
190 
191 /*
192  * subrectEncode() encodes the given multicoloured rectangle as a background
193  * colour overwritten by single-coloured rectangles. It returns the number
194  * of subrectangles in the encoded buffer, or -1 if subrect encoding won't
195  * fit in the buffer. It puts the encoded rectangles in cl->afterEncBuf. The
196  * single-colour rectangle partition is not optimal, but does find the biggest
197  * horizontal or vertical rectangle top-left anchored to each consecutive
198  * coordinate position.
199  *
200  * The coding scheme is simply [<bgcolour><subrect><subrect>...] where each
201  * <subrect> is [<colour><x><y><w><h>].
202  */
203 
204 #define DEFINE_SUBRECT_ENCODE(bpp) \
205 static int \
206 subrectEncode##bpp(rfbClientPtr client, uint##bpp##_t *data, int w, int h) { \
207  uint##bpp##_t cl; \
208  rfbCoRRERectangle subrect; \
209  int x,y; \
210  int i,j; \
211  int hx=0,hy,vx=0,vy; \
212  int hyflag; \
213  uint##bpp##_t *seg; \
214  uint##bpp##_t *line; \
215  int hw,hh,vw,vh; \
216  int thex,they,thew,theh; \
217  int numsubs = 0; \
218  int newLen; \
219  uint##bpp##_t bg = (uint##bpp##_t)getBgColour((char*)data,w*h,bpp); \
220  \
221  *((uint##bpp##_t*)client->afterEncBuf) = bg; \
222  \
223  client->afterEncBufLen = (bpp/8); \
224  \
225  for (y=0; y<h; y++) { \
226  line = data+(y*w); \
227  for (x=0; x<w; x++) { \
228  if (line[x] != bg) { \
229  cl = line[x]; \
230  hy = y-1; \
231  hyflag = 1; \
232  for (j=y; j<h; j++) { \
233  seg = data+(j*w); \
234  if (seg[x] != cl) {break;} \
235  i = x; \
236  while ((seg[i] == cl) && (i < w)) i += 1; \
237  i -= 1; \
238  if (j == y) vx = hx = i; \
239  if (i < vx) vx = i; \
240  if ((hyflag > 0) && (i >= hx)) {hy += 1;} else {hyflag = 0;} \
241  } \
242  vy = j-1; \
243  \
244  /* We now have two possible subrects: (x,y,hx,hy) and (x,y,vx,vy) \
245  * We'll choose the bigger of the two. \
246  */ \
247  hw = hx-x+1; \
248  hh = hy-y+1; \
249  vw = vx-x+1; \
250  vh = vy-y+1; \
251  \
252  thex = x; \
253  they = y; \
254  \
255  if ((hw*hh) > (vw*vh)) { \
256  thew = hw; \
257  theh = hh; \
258  } else { \
259  thew = vw; \
260  theh = vh; \
261  } \
262  \
263  subrect.x = thex; \
264  subrect.y = they; \
265  subrect.w = thew; \
266  subrect.h = theh; \
267  \
268  newLen = client->afterEncBufLen + (bpp/8) + sz_rfbCoRRERectangle; \
269  if ((newLen > (w * h * (bpp/8))) || (newLen > client->afterEncBufSize)) \
270  return -1; \
271  \
272  numsubs += 1; \
273  *((uint##bpp##_t*)(client->afterEncBuf + client->afterEncBufLen)) = cl; \
274  client->afterEncBufLen += (bpp/8); \
275  memcpy(&client->afterEncBuf[client->afterEncBufLen],&subrect,sz_rfbCoRRERectangle); \
276  client->afterEncBufLen += sz_rfbCoRRERectangle; \
277  \
278  /* \
279  * Now mark the subrect as done. \
280  */ \
281  for (j=they; j < (they+theh); j++) { \
282  for (i=thex; i < (thex+thew); i++) { \
283  data[j*w+i] = bg; \
284  } \
285  } \
286  } \
287  } \
288  } \
289  \
290  return numsubs; \
291 }
292 
296 
297 
298 /*
299  * getBgColour() gets the most prevalent colour in a byte array.
300  */
301 static uint32_t
302 getBgColour(char *data, int size, int bpp)
303 {
304 
305 #define NUMCLRS 256
306 
307  static int counts[NUMCLRS];
308  int i,j,k;
309 
310  int maxcount = 0;
311  uint8_t maxclr = 0;
312 
313  if (bpp != 8) {
314  if (bpp == 16) {
315  return ((uint16_t *)data)[0];
316  } else if (bpp == 32) {
317  return ((uint32_t *)data)[0];
318  } else {
319  rfbLog("getBgColour: bpp %d?\n",bpp);
320  return 0;
321  }
322  }
323 
324  for (i=0; i<NUMCLRS; i++) {
325  counts[i] = 0;
326  }
327 
328  for (j=0; j<size; j++) {
329  k = (int)(((uint8_t *)data)[j]);
330  if (k >= NUMCLRS) {
331  rfbLog("getBgColour: unusual colour = %d\n", k);
332  return 0;
333  }
334  counts[k] += 1;
335  if (counts[k] > maxcount) {
336  maxcount = counts[k];
337  maxclr = ((uint8_t *)data)[j];
338  }
339  }
340 
341  return maxclr;
342 }