LibVNCServer/LibVNCClient
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->beforeEncBuf || cl->beforeEncBufSize < maxRawSize) {
100  if (cl->beforeEncBuf == NULL)
101  cl->beforeEncBuf = (char *)malloc(maxRawSize);
102  else {
103  char *reallocedBeforeEncBuf = (char *)realloc(cl->beforeEncBuf, maxRawSize);
104  if (!reallocedBeforeEncBuf) return FALSE;
105  cl->beforeEncBuf = reallocedBeforeEncBuf;
106  }
107  if(cl->beforeEncBuf)
108  cl->beforeEncBufSize = maxRawSize;
109  }
110 
111  if (!cl->afterEncBuf || cl->afterEncBufSize < maxRawSize) {
112  if (cl->afterEncBuf == NULL)
113  cl->afterEncBuf = (char *)malloc(maxRawSize);
114  else {
115  char *reallocedAfterEncBuf = (char *)realloc(cl->afterEncBuf, maxRawSize);
116  if (!reallocedAfterEncBuf) return FALSE;
117  cl->afterEncBuf = reallocedAfterEncBuf;
118  }
119  if(cl->afterEncBuf)
120  cl->afterEncBufSize = maxRawSize;
121  }
122 
123  if (!cl->beforeEncBuf || !cl->afterEncBuf)
124  {
125  rfbLog("rfbSendSmallRectEncodingCoRRE: failed to allocate memory\n");
126  return FALSE;
127  }
128 
129  (*cl->translateFn)(cl->translateLookupTable,&(cl->screen->serverFormat),
130  &cl->format, fbptr, cl->beforeEncBuf,
131  cl->scaledScreen->paddedWidthInBytes, w, h);
132 
133  switch (cl->format.bitsPerPixel) {
134  case 8:
135  nSubrects = subrectEncode8(cl, (uint8_t *)cl->beforeEncBuf, w, h);
136  break;
137  case 16:
138  nSubrects = subrectEncode16(cl, (uint16_t *)cl->beforeEncBuf, w, h);
139  break;
140  case 32:
141  nSubrects = subrectEncode32(cl, (uint32_t *)cl->beforeEncBuf, w, h);
142  break;
143  default:
144  rfbLog("getBgColour: bpp %d?\n",cl->format.bitsPerPixel);
145  return FALSE;
146  }
147 
148  if (nSubrects < 0) {
149 
150  /* RRE encoding was too large, use raw */
151 
152  return rfbSendRectEncodingRaw(cl, x, y, w, h);
153  }
154 
156  sz_rfbFramebufferUpdateRectHeader + sz_rfbRREHeader + cl->afterEncBufLen,
157  sz_rfbFramebufferUpdateRectHeader + w * h * (cl->format.bitsPerPixel / 8));
158 
160  > UPDATE_BUF_SIZE)
161  {
162  if (!rfbSendUpdateBuf(cl))
163  return FALSE;
164  }
165 
166  rect.r.x = Swap16IfLE(x);
167  rect.r.y = Swap16IfLE(y);
168  rect.r.w = Swap16IfLE(w);
169  rect.r.h = Swap16IfLE(h);
171 
172  memcpy(&cl->updateBuf[cl->ublen], (char *)&rect,
175 
176  hdr.nSubrects = Swap32IfLE(nSubrects);
177 
178  memcpy(&cl->updateBuf[cl->ublen], (char *)&hdr, sz_rfbRREHeader);
179  cl->ublen += sz_rfbRREHeader;
180 
181  for (i = 0; i < cl->afterEncBufLen;) {
182 
183  int bytesToCopy = UPDATE_BUF_SIZE - cl->ublen;
184 
185  if (i + bytesToCopy > cl->afterEncBufLen) {
186  bytesToCopy = cl->afterEncBufLen - i;
187  }
188 
189  memcpy(&cl->updateBuf[cl->ublen], &cl->afterEncBuf[i], bytesToCopy);
190 
191  cl->ublen += bytesToCopy;
192  i += bytesToCopy;
193 
194  if (cl->ublen == UPDATE_BUF_SIZE) {
195  if (!rfbSendUpdateBuf(cl))
196  return FALSE;
197  }
198  }
199 
200  return TRUE;
201 }
202 
203 
204 
205 /*
206  * subrectEncode() encodes the given multicoloured rectangle as a background
207  * colour overwritten by single-coloured rectangles. It returns the number
208  * of subrectangles in the encoded buffer, or -1 if subrect encoding won't
209  * fit in the buffer. It puts the encoded rectangles in cl->afterEncBuf. The
210  * single-colour rectangle partition is not optimal, but does find the biggest
211  * horizontal or vertical rectangle top-left anchored to each consecutive
212  * coordinate position.
213  *
214  * The coding scheme is simply [<bgcolour><subrect><subrect>...] where each
215  * <subrect> is [<colour><x><y><w><h>].
216  */
217 
218 #define DEFINE_SUBRECT_ENCODE(bpp) \
219 static int \
220 subrectEncode##bpp(rfbClientPtr client, uint##bpp##_t *data, int w, int h) { \
221  uint##bpp##_t cl; \
222  rfbCoRRERectangle subrect; \
223  int x,y; \
224  int i,j; \
225  int hx=0,hy,vx=0,vy; \
226  int hyflag; \
227  uint##bpp##_t *seg; \
228  uint##bpp##_t *line; \
229  int hw,hh,vw,vh; \
230  int thex,they,thew,theh; \
231  int numsubs = 0; \
232  int newLen; \
233  uint##bpp##_t bg = (uint##bpp##_t)getBgColour((char*)data,w*h,bpp); \
234  \
235  *((uint##bpp##_t*)client->afterEncBuf) = bg; \
236  \
237  client->afterEncBufLen = (bpp/8); \
238  \
239  for (y=0; y<h; y++) { \
240  line = data+(y*w); \
241  for (x=0; x<w; x++) { \
242  if (line[x] != bg) { \
243  cl = line[x]; \
244  hy = y-1; \
245  hyflag = 1; \
246  for (j=y; j<h; j++) { \
247  seg = data+(j*w); \
248  if (seg[x] != cl) {break;} \
249  i = x; \
250  while ((i < w) && (seg[i] == cl)) i += 1; \
251  i -= 1; \
252  if (j == y) vx = hx = i; \
253  if (i < vx) vx = i; \
254  if ((hyflag > 0) && (i >= hx)) {hy += 1;} else {hyflag = 0;} \
255  } \
256  vy = j-1; \
257  \
258  /* We now have two possible subrects: (x,y,hx,hy) and (x,y,vx,vy) \
259  * We'll choose the bigger of the two. \
260  */ \
261  hw = hx-x+1; \
262  hh = hy-y+1; \
263  vw = vx-x+1; \
264  vh = vy-y+1; \
265  \
266  thex = x; \
267  they = y; \
268  \
269  if ((hw*hh) > (vw*vh)) { \
270  thew = hw; \
271  theh = hh; \
272  } else { \
273  thew = vw; \
274  theh = vh; \
275  } \
276  \
277  subrect.x = thex; \
278  subrect.y = they; \
279  subrect.w = thew; \
280  subrect.h = theh; \
281  \
282  newLen = client->afterEncBufLen + (bpp/8) + sz_rfbCoRRERectangle; \
283  if ((newLen > (w * h * (bpp/8))) || (newLen > client->afterEncBufSize)) \
284  return -1; \
285  \
286  numsubs += 1; \
287  *((uint##bpp##_t*)(client->afterEncBuf + client->afterEncBufLen)) = cl; \
288  client->afterEncBufLen += (bpp/8); \
289  memcpy(&client->afterEncBuf[client->afterEncBufLen],&subrect,sz_rfbCoRRERectangle); \
290  client->afterEncBufLen += sz_rfbCoRRERectangle; \
291  \
292  /* \
293  * Now mark the subrect as done. \
294  */ \
295  for (j=they; j < (they+theh); j++) { \
296  for (i=thex; i < (thex+thew); i++) { \
297  data[j*w+i] = bg; \
298  } \
299  } \
300  } \
301  } \
302  } \
303  \
304  return numsubs; \
305 }
306 
310 
311 
312 /*
313  * getBgColour() gets the most prevalent colour in a byte array.
314  */
315 static uint32_t
316 getBgColour(char *data, int size, int bpp)
317 {
318 
319 #define NUMCLRS 256
320 
321  static int counts[NUMCLRS];
322  int i,j,k;
323 
324  int maxcount = 0;
325  uint8_t maxclr = 0;
326 
327  if (bpp != 8) {
328  if (bpp == 16) {
329  return ((uint16_t *)data)[0];
330  } else if (bpp == 32) {
331  return ((uint32_t *)data)[0];
332  } else {
333  rfbLog("getBgColour: bpp %d?\n",bpp);
334  return 0;
335  }
336  }
337 
338  for (i=0; i<NUMCLRS; i++) {
339  counts[i] = 0;
340  }
341 
342  for (j=0; j<size; j++) {
343  k = (int)(((uint8_t *)data)[j]);
344 #if NUMCLRS != 256
345  if (k >= NUMCLRS) {
346  rfbLog("getBgColour: unusual colour = %d\n", k);
347  return 0;
348  }
349 #endif
350  counts[k] += 1;
351  if (counts[k] > maxcount) {
352  maxcount = counts[k];
353  maxclr = ((uint8_t *)data)[j];
354  }
355  }
356 
357  return maxclr;
358 }
int x
Definition: SDLvncviewer.c:34
#define TRUE
Definition: rfbproto.h:112
rfbBool rfbSendRectEncodingRaw(rfbClientPtr cl, int x, int y, int w, int h)
Definition: rfbserver.c:3373
#define Swap32IfLE(l)
Definition: rfb.h:718
int8_t rfbBool
Definition: rfbproto.h:108
#define UPDATE_BUF_SIZE
UPDATE_BUF_SIZE must be big enough to send at least one whole line of the framebuffer.
Definition: rfb.h:558
uint16_t y
Definition: rfbproto.h:142
uint32_t nSubrects
Definition: rfbproto.h:640
rfbBool rfbSendUpdateBuf(rfbClientPtr cl)
Definition: rfbserver.c:3615
uint16_t h
Definition: rfbproto.h:144
#define DEFINE_SUBRECT_ENCODE(bpp)
Definition: corre.c:218
rfbBool rfbSendRectEncodingCoRRE(rfbClientPtr cl, int x, int y, int w, int h)
Definition: corre.c:53
uint16_t w
Definition: rfbproto.h:143
void rfbStatRecordEncodingSent(rfbClientPtr cl, uint32_t type, int byteCount, int byteIfRaw)
Definition: stats.c:220
#define rfbEncodingCoRRE
Definition: rfbproto.h:442
uint16_t x
Definition: rfbproto.h:141
int y
Definition: SDLvncviewer.c:34
#define sz_rfbFramebufferUpdateRectHeader
Definition: rfbproto.h:567
rfbLogProc rfbLog
Definition: main.c:263
#define FALSE
Definition: rfbproto.h:110
#define NUMCLRS
#define Swap16IfLE(s)
Definition: rfb.h:716
#define sz_rfbRREHeader
Definition: rfbproto.h:643