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
rfbSendRectEncodingCoRRE(rfbClientPtr cl,int x,int y,int w,int h)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
rfbSendSmallRectEncodingCoRRE(rfbClientPtr cl,int x,int y,int w,int h)83 rfbSendSmallRectEncodingCoRRE(rfbClientPtr cl,
84 int x,
85 int y,
86 int w,
87 int h)
88 {
89 rfbFramebufferUpdateRectHeader rect;
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
141 rfbStatRecordEncodingSent(cl,rfbEncodingCoRRE,
142 sz_rfbFramebufferUpdateRectHeader + sz_rfbRREHeader + cl->afterEncBufLen,
143 sz_rfbFramebufferUpdateRectHeader + w * h * (cl->format.bitsPerPixel / 8));
144
145 if (cl->ublen + sz_rfbFramebufferUpdateRectHeader + sz_rfbRREHeader
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);
156 rect.encoding = Swap32IfLE(rfbEncodingCoRRE);
157
158 memcpy(&cl->updateBuf[cl->ublen], (char *)&rect,
159 sz_rfbFramebufferUpdateRectHeader);
160 cl->ublen += sz_rfbFramebufferUpdateRectHeader;
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
293 DEFINE_SUBRECT_ENCODE(8)
294 DEFINE_SUBRECT_ENCODE(16)
295 DEFINE_SUBRECT_ENCODE(32)
296
297
298 /*
299 * getBgColour() gets the most prevalent colour in a byte array.
300 */
301 static uint32_t
getBgColour(char * data,int size,int bpp)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 }
343