LibVNCServer/LibVNCClient
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
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->beforeEncBufSize < maxRawSize) {
66  cl->beforeEncBufSize = maxRawSize;
67  if (cl->beforeEncBuf == NULL)
68  cl->beforeEncBuf = (char *)malloc(cl->beforeEncBufSize);
69  else
70  cl->beforeEncBuf = (char *)realloc(cl->beforeEncBuf, cl->beforeEncBufSize);
71  }
72 
73  if (cl->afterEncBufSize < maxRawSize) {
74  cl->afterEncBufSize = maxRawSize;
75  if (cl->afterEncBuf == NULL)
76  cl->afterEncBuf = (char *)malloc(cl->afterEncBufSize);
77  else
78  cl->afterEncBuf = (char *)realloc(cl->afterEncBuf, cl->afterEncBufSize);
79  }
80 
81  (*cl->translateFn)(cl->translateLookupTable,
82  &(cl->screen->serverFormat),
83  &cl->format, fbptr, cl->beforeEncBuf,
84  cl->scaledScreen->paddedWidthInBytes, w, h);
85 
86  switch (cl->format.bitsPerPixel) {
87  case 8:
88  nSubrects = subrectEncode8(cl, (uint8_t *)cl->beforeEncBuf, w, h);
89  break;
90  case 16:
91  nSubrects = subrectEncode16(cl, (uint16_t *)cl->beforeEncBuf, w, h);
92  break;
93  case 32:
94  nSubrects = subrectEncode32(cl, (uint32_t *)cl->beforeEncBuf, w, h);
95  break;
96  default:
97  rfbLog("getBgColour: bpp %d?\n",cl->format.bitsPerPixel);
98  return FALSE;
99  }
100 
101  if (nSubrects < 0) {
102 
103  /* RRE encoding was too large, use raw */
104 
105  return rfbSendRectEncodingRaw(cl, x, y, w, h);
106  }
107 
109  sz_rfbFramebufferUpdateRectHeader + sz_rfbRREHeader + cl->afterEncBufLen,
110  sz_rfbFramebufferUpdateRectHeader + w * h * (cl->format.bitsPerPixel / 8));
111 
113  > UPDATE_BUF_SIZE)
114  {
115  if (!rfbSendUpdateBuf(cl))
116  return FALSE;
117  }
118 
119  rect.r.x = Swap16IfLE(x);
120  rect.r.y = Swap16IfLE(y);
121  rect.r.w = Swap16IfLE(w);
122  rect.r.h = Swap16IfLE(h);
124 
125  memcpy(&cl->updateBuf[cl->ublen], (char *)&rect,
128 
129  hdr.nSubrects = Swap32IfLE(nSubrects);
130 
131  memcpy(&cl->updateBuf[cl->ublen], (char *)&hdr, sz_rfbRREHeader);
132  cl->ublen += sz_rfbRREHeader;
133 
134  for (i = 0; i < cl->afterEncBufLen;) {
135 
136  int bytesToCopy = UPDATE_BUF_SIZE - cl->ublen;
137 
138  if (i + bytesToCopy > cl->afterEncBufLen) {
139  bytesToCopy = cl->afterEncBufLen - i;
140  }
141 
142  memcpy(&cl->updateBuf[cl->ublen], &cl->afterEncBuf[i], bytesToCopy);
143 
144  cl->ublen += bytesToCopy;
145  i += bytesToCopy;
146 
147  if (cl->ublen == UPDATE_BUF_SIZE) {
148  if (!rfbSendUpdateBuf(cl))
149  return FALSE;
150  }
151  }
152 
153  return TRUE;
154 }
155 
156 
157 
158 /*
159  * subrectEncode() encodes the given multicoloured rectangle as a background
160  * colour overwritten by single-coloured rectangles. It returns the number
161  * of subrectangles in the encoded buffer, or -1 if subrect encoding won't
162  * fit in the buffer. It puts the encoded rectangles in cl->afterEncBuf. The
163  * single-colour rectangle partition is not optimal, but does find the biggest
164  * horizontal or vertical rectangle top-left anchored to each consecutive
165  * coordinate position.
166  *
167  * The coding scheme is simply [<bgcolour><subrect><subrect>...] where each
168  * <subrect> is [<colour><x><y><w><h>].
169  */
170 
171 #define DEFINE_SUBRECT_ENCODE(bpp) \
172 static int \
173  subrectEncode##bpp(rfbClientPtr client, uint##bpp##_t *data, int w, int h) { \
174  uint##bpp##_t cl; \
175  rfbRectangle subrect; \
176  int x,y; \
177  int i,j; \
178  int hx=0,hy,vx=0,vy; \
179  int hyflag; \
180  uint##bpp##_t *seg; \
181  uint##bpp##_t *line; \
182  int hw,hh,vw,vh; \
183  int thex,they,thew,theh; \
184  int numsubs = 0; \
185  int newLen; \
186  uint##bpp##_t bg = (uint##bpp##_t)getBgColour((char*)data,w*h,bpp); \
187  \
188  *((uint##bpp##_t*)client->afterEncBuf) = bg; \
189  \
190  client->afterEncBufLen = (bpp/8); \
191  \
192  for (y=0; y<h; y++) { \
193  line = data+(y*w); \
194  for (x=0; x<w; x++) { \
195  if (line[x] != bg) { \
196  cl = line[x]; \
197  hy = y-1; \
198  hyflag = 1; \
199  for (j=y; j<h; j++) { \
200  seg = data+(j*w); \
201  if (seg[x] != cl) {break;} \
202  i = x; \
203  while ((seg[i] == cl) && (i < w)) i += 1; \
204  i -= 1; \
205  if (j == y) vx = hx = i; \
206  if (i < vx) vx = i; \
207  if ((hyflag > 0) && (i >= hx)) {hy += 1;} else {hyflag = 0;} \
208  } \
209  vy = j-1; \
210  \
211  /* We now have two possible subrects: (x,y,hx,hy) and (x,y,vx,vy) \
212  * We'll choose the bigger of the two. \
213  */ \
214  hw = hx-x+1; \
215  hh = hy-y+1; \
216  vw = vx-x+1; \
217  vh = vy-y+1; \
218  \
219  thex = x; \
220  they = y; \
221  \
222  if ((hw*hh) > (vw*vh)) { \
223  thew = hw; \
224  theh = hh; \
225  } else { \
226  thew = vw; \
227  theh = vh; \
228  } \
229  \
230  subrect.x = Swap16IfLE(thex); \
231  subrect.y = Swap16IfLE(they); \
232  subrect.w = Swap16IfLE(thew); \
233  subrect.h = Swap16IfLE(theh); \
234  \
235  newLen = client->afterEncBufLen + (bpp/8) + sz_rfbRectangle; \
236  if ((newLen > (w * h * (bpp/8))) || (newLen > client->afterEncBufSize)) \
237  return -1; \
238  \
239  numsubs += 1; \
240  *((uint##bpp##_t*)(client->afterEncBuf + client->afterEncBufLen)) = cl; \
241  client->afterEncBufLen += (bpp/8); \
242  memcpy(&client->afterEncBuf[client->afterEncBufLen],&subrect,sz_rfbRectangle); \
243  client->afterEncBufLen += sz_rfbRectangle; \
244  \
245  /* \
246  * Now mark the subrect as done. \
247  */ \
248  for (j=they; j < (they+theh); j++) { \
249  for (i=thex; i < (thex+thew); i++) { \
250  data[j*w+i] = bg; \
251  } \
252  } \
253  } \
254  } \
255  } \
256  \
257  return numsubs; \
258 }
259 
263 
264 
265 /*
266  * getBgColour() gets the most prevalent colour in a byte array.
267  */
268 static uint32_t
269 getBgColour(char *data, int size, int bpp)
270 {
271 
272 #define NUMCLRS 256
273 
274  static int counts[NUMCLRS];
275  int i,j,k;
276 
277  int maxcount = 0;
278  uint8_t maxclr = 0;
279 
280  if (bpp != 8) {
281  if (bpp == 16) {
282  return ((uint16_t *)data)[0];
283  } else if (bpp == 32) {
284  return ((uint32_t *)data)[0];
285  } else {
286  rfbLog("getBgColour: bpp %d?\n",bpp);
287  return 0;
288  }
289  }
290 
291  for (i=0; i<NUMCLRS; i++) {
292  counts[i] = 0;
293  }
294 
295  for (j=0; j<size; j++) {
296  k = (int)(((uint8_t *)data)[j]);
297  if (k >= NUMCLRS) {
298  rfbErr("getBgColour: unusual colour = %d\n", k);
299  return 0;
300  }
301  counts[k] += 1;
302  if (counts[k] > maxcount) {
303  maxcount = counts[k];
304  maxclr = ((uint8_t *)data)[j];
305  }
306  }
307 
308  return maxclr;
309 }