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
rfbSendRectEncodingRRE(rfbClientPtr cl,int x,int y,int w,int h)49 rfbSendRectEncodingRRE(rfbClientPtr cl,
50 int x,
51 int y,
52 int w,
53 int h)
54 {
55 rfbFramebufferUpdateRectHeader rect;
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
108 rfbStatRecordEncodingSent(cl, rfbEncodingRRE,
109 sz_rfbFramebufferUpdateRectHeader + sz_rfbRREHeader + cl->afterEncBufLen,
110 sz_rfbFramebufferUpdateRectHeader + w * h * (cl->format.bitsPerPixel / 8));
111
112 if (cl->ublen + sz_rfbFramebufferUpdateRectHeader + sz_rfbRREHeader
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);
123 rect.encoding = Swap32IfLE(rfbEncodingRRE);
124
125 memcpy(&cl->updateBuf[cl->ublen], (char *)&rect,
126 sz_rfbFramebufferUpdateRectHeader);
127 cl->ublen += sz_rfbFramebufferUpdateRectHeader;
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
260 DEFINE_SUBRECT_ENCODE(8)
261 DEFINE_SUBRECT_ENCODE(16)
262 DEFINE_SUBRECT_ENCODE(32)
263
264
265 /*
266 * getBgColour() gets the most prevalent colour in a byte array.
267 */
268 static uint32_t
getBgColour(char * data,int size,int bpp)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 }
310