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 39static int subrectEncode8(rfbClientPtr cl, uint8_t *data, int w, int h); 40static int subrectEncode16(rfbClientPtr cl, uint16_t *data, int w, int h); 41static int subrectEncode32(rfbClientPtr cl, uint32_t *data, int w, int h); 42static uint32_t getBgColour(char *data, int size, int bpp); 43static 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 52rfbBool 53rfbSendRectEncodingCoRRE(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 82static rfbBool 83rfbSendSmallRectEncodingCoRRE(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) \ 205static int \ 206subrectEncode##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 293DEFINE_SUBRECT_ENCODE(8) 294DEFINE_SUBRECT_ENCODE(16) 295DEFINE_SUBRECT_ENCODE(32) 296 297 298/* 299 * getBgColour() gets the most prevalent colour in a byte array. 300 */ 301static uint32_t 302getBgColour(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