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