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 38static int subrectEncode8(rfbClientPtr cl, uint8_t *data, int w, int h); 39static int subrectEncode16(rfbClientPtr cl, uint16_t *data, int w, int h); 40static int subrectEncode32(rfbClientPtr cl, uint32_t *data, int w, int h); 41static uint32_t getBgColour(char *data, int size, int bpp); 42 43 44/* 45 * rfbSendRectEncodingRRE - send a given rectangle using RRE encoding. 46 */ 47 48rfbBool 49rfbSendRectEncodingRRE(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) \ 172static 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 260DEFINE_SUBRECT_ENCODE(8) 261DEFINE_SUBRECT_ENCODE(16) 262DEFINE_SUBRECT_ENCODE(32) 263 264 265/* 266 * getBgColour() gets the most prevalent colour in a byte array. 267 */ 268static uint32_t 269getBgColour(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