git.maemo.org Git - presencevnc/blob - libvnc/libvncserver/corre.c

   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  * rreBeforeBuf contains pixel data in the client's format.
  34  * rreAfterBuf contains the RRE encoded version.  If the RRE encoded version is
  35  * larger than the raw data or if it exceeds rreAfterBufSize then
  36  * raw encoding is used instead.
  37  */
  38
  39 static int rreBeforeBufSize = 0;
  40 static char *rreBeforeBuf = NULL;
  41
  42 static int rreAfterBufSize = 0;
  43 static char *rreAfterBuf = NULL;
  44 static int rreAfterBufLen = 0;
  45
  46 static int subrectEncode8(uint8_t *data, int w, int h);
  47 static int subrectEncode16(uint16_t *data, int w, int h);
  48 static int subrectEncode32(uint32_t *data, int w, int h);
  49 static uint32_t getBgColour(char *data, int size, int bpp);
  50 static rfbBool rfbSendSmallRectEncodingCoRRE(rfbClientPtr cl, int x, int y,
  51                                           int w, int h);
  52
  53 void rfbCoRRECleanup(rfbScreenInfoPtr screen)
  54 {
  55   if (rreBeforeBufSize) {
  56     free(rreBeforeBuf);
  57     rreBeforeBufSize=0;
  58   }
  59   if (rreAfterBufSize) {
  60     free(rreAfterBuf);
  61     rreAfterBufSize=0;
  62   }
  63 }
  64
  65 /*
  66  * rfbSendRectEncodingCoRRE - send an arbitrary size rectangle using CoRRE
  67  * encoding.
  68  */
  69
  70 rfbBool
  71 rfbSendRectEncodingCoRRE(rfbClientPtr cl,
  72                          int x,
  73                          int y,
  74                          int w,
  75                          int h)
  76 {
  77     if (h > cl->correMaxHeight) {
  78         return (rfbSendRectEncodingCoRRE(cl, x, y, w, cl->correMaxHeight) &&
  79                 rfbSendRectEncodingCoRRE(cl, x, y + cl->correMaxHeight, w,
  80                                          h - cl->correMaxHeight));
  81     }
  82
  83     if (w > cl->correMaxWidth) {
  84         return (rfbSendRectEncodingCoRRE(cl, x, y, cl->correMaxWidth, h) &&
  85                 rfbSendRectEncodingCoRRE(cl, x + cl->correMaxWidth, y,
  86                                          w - cl->correMaxWidth, h));
  87     }
  88
  89     rfbSendSmallRectEncodingCoRRE(cl, x, y, w, h);
  90     return TRUE;
  91 }
  92
  93
  94
  95 /*
  96  * rfbSendSmallRectEncodingCoRRE - send a small (guaranteed < 256x256)
  97  * rectangle using CoRRE encoding.
  98  */
  99
 100 static rfbBool
 101 rfbSendSmallRectEncodingCoRRE(rfbClientPtr cl,
 102                               int x,
 103                               int y,
 104                               int w,
 105                               int h)
 106 {
 107     rfbFramebufferUpdateRectHeader rect;
 108     rfbRREHeader hdr;
 109     int nSubrects;
 110     int i;
 111     char *fbptr = (cl->scaledScreen->frameBuffer + (cl->scaledScreen->paddedWidthInBytes * y)
 112                    + (x * (cl->scaledScreen->bitsPerPixel / 8)));
 113
 114     int maxRawSize = (cl->scaledScreen->width * cl->scaledScreen->height
 115                       * (cl->format.bitsPerPixel / 8));
 116
 117     if (rreBeforeBufSize < maxRawSize) {
 118         rreBeforeBufSize = maxRawSize;
 119         if (rreBeforeBuf == NULL)
 120             rreBeforeBuf = (char *)malloc(rreBeforeBufSize);
 121         else
 122             rreBeforeBuf = (char *)realloc(rreBeforeBuf, rreBeforeBufSize);
 123     }
 124
 125     if (rreAfterBufSize < maxRawSize) {
 126         rreAfterBufSize = maxRawSize;
 127         if (rreAfterBuf == NULL)
 128             rreAfterBuf = (char *)malloc(rreAfterBufSize);
 129         else
 130             rreAfterBuf = (char *)realloc(rreAfterBuf, rreAfterBufSize);
 131     }
 132
 133     (*cl->translateFn)(cl->translateLookupTable,&(cl->screen->serverFormat),
 134                        &cl->format, fbptr, rreBeforeBuf,
 135                        cl->scaledScreen->paddedWidthInBytes, w, h);
 136
 137     switch (cl->format.bitsPerPixel) {
 138     case 8:
 139         nSubrects = subrectEncode8((uint8_t *)rreBeforeBuf, w, h);
 140         break;
 141     case 16:
 142         nSubrects = subrectEncode16((uint16_t *)rreBeforeBuf, w, h);
 143         break;
 144     case 32:
 145         nSubrects = subrectEncode32((uint32_t *)rreBeforeBuf, w, h);
 146         break;
 147     default:
 148         rfbLog("getBgColour: bpp %d?\n",cl->format.bitsPerPixel);
 149         return FALSE;
 150     }
 151
 152     if (nSubrects < 0) {
 153
 154         /* RRE encoding was too large, use raw */
 155
 156         return rfbSendRectEncodingRaw(cl, x, y, w, h);
 157     }
 158
 159     rfbStatRecordEncodingSent(cl,rfbEncodingCoRRE,
 160         sz_rfbFramebufferUpdateRectHeader + sz_rfbRREHeader + rreAfterBufLen,
 161         sz_rfbFramebufferUpdateRectHeader + w * h * (cl->format.bitsPerPixel / 8));
 162
 163     if (cl->ublen + sz_rfbFramebufferUpdateRectHeader + sz_rfbRREHeader
 164         > UPDATE_BUF_SIZE)
 165     {
 166         if (!rfbSendUpdateBuf(cl))
 167             return FALSE;
 168     }
 169
 170     rect.r.x = Swap16IfLE(x);
 171     rect.r.y = Swap16IfLE(y);
 172     rect.r.w = Swap16IfLE(w);
 173     rect.r.h = Swap16IfLE(h);
 174     rect.encoding = Swap32IfLE(rfbEncodingCoRRE);
 175
 176     memcpy(&cl->updateBuf[cl->ublen], (char *)&rect,
 177            sz_rfbFramebufferUpdateRectHeader);
 178     cl->ublen += sz_rfbFramebufferUpdateRectHeader;
 179
 180     hdr.nSubrects = Swap32IfLE(nSubrects);
 181
 182     memcpy(&cl->updateBuf[cl->ublen], (char *)&hdr, sz_rfbRREHeader);
 183     cl->ublen += sz_rfbRREHeader;
 184
 185     for (i = 0; i < rreAfterBufLen;) {
 186
 187         int bytesToCopy = UPDATE_BUF_SIZE - cl->ublen;
 188
 189         if (i + bytesToCopy > rreAfterBufLen) {
 190             bytesToCopy = rreAfterBufLen - i;
 191         }
 192
 193         memcpy(&cl->updateBuf[cl->ublen], &rreAfterBuf[i], bytesToCopy);
 194
 195         cl->ublen += bytesToCopy;
 196         i += bytesToCopy;
 197
 198         if (cl->ublen == UPDATE_BUF_SIZE) {
 199             if (!rfbSendUpdateBuf(cl))
 200                 return FALSE;
 201         }
 202     }
 203
 204     return TRUE;
 205 }
 206
 207
 208
 209 /*
 210  * subrectEncode() encodes the given multicoloured rectangle as a background
 211  * colour overwritten by single-coloured rectangles.  It returns the number
 212  * of subrectangles in the encoded buffer, or -1 if subrect encoding won't
 213  * fit in the buffer.  It puts the encoded rectangles in rreAfterBuf.  The
 214  * single-colour rectangle partition is not optimal, but does find the biggest
 215  * horizontal or vertical rectangle top-left anchored to each consecutive
 216  * coordinate position.
 217  *
 218  * The coding scheme is simply [<bgcolour><subrect><subrect>...] where each
 219  * <subrect> is [<colour><x><y><w><h>].
 220  */
 221
 222 #define DEFINE_SUBRECT_ENCODE(bpp)                                            \
 223 static int                                                                    \
 224 subrectEncode##bpp(uint##bpp##_t *data, int w, int h) {                       \
 225     uint##bpp##_t cl;                                                         \
 226     rfbCoRRERectangle subrect;                                                \
 227     int x,y;                                                                  \
 228     int i,j;                                                                  \
 229     int hx=0,hy,vx=0,vy;                                                      \
 230     int hyflag;                                                               \
 231     uint##bpp##_t *seg;                                                       \
 232     uint##bpp##_t *line;                                                      \
 233     int hw,hh,vw,vh;                                                          \
 234     int thex,they,thew,theh;                                                  \
 235     int numsubs = 0;                                                          \
 236     int newLen;                                                               \
 237     uint##bpp##_t bg = (uint##bpp##_t)getBgColour((char*)data,w*h,bpp);       \
 238                                                                               \
 239     *((uint##bpp##_t*)rreAfterBuf) = bg;                                      \
 240                                                                               \
 241     rreAfterBufLen = (bpp/8);                                                 \
 242                                                                               \
 243     for (y=0; y<h; y++) {                                                     \
 244       line = data+(y*w);                                                      \
 245       for (x=0; x<w; x++) {                                                   \
 246         if (line[x] != bg) {                                                  \
 247           cl = line[x];                                                       \
 248           hy = y-1;                                                           \
 249           hyflag = 1;                                                         \
 250           for (j=y; j<h; j++) {                                               \
 251             seg = data+(j*w);                                                 \
 252             if (seg[x] != cl) {break;}                                        \
 253             i = x;                                                            \
 254             while ((seg[i] == cl) && (i < w)) i += 1;                         \
 255             i -= 1;                                                           \
 256             if (j == y) vx = hx = i;                                          \
 257             if (i < vx) vx = i;                                               \
 258             if ((hyflag > 0) && (i >= hx)) {hy += 1;} else {hyflag = 0;}      \
 259           }                                                                   \
 260           vy = j-1;                                                           \
 261                                                                               \
 262           /*  We now have two possible subrects: (x,y,hx,hy) and (x,y,vx,vy)  \
 263            *  We'll choose the bigger of the two.                             \
 264            */                                                                 \
 265           hw = hx-x+1;                                                        \
 266           hh = hy-y+1;                                                        \
 267           vw = vx-x+1;                                                        \
 268           vh = vy-y+1;                                                        \
 269                                                                               \
 270           thex = x;                                                           \
 271           they = y;                                                           \
 272                                                                               \
 273           if ((hw*hh) > (vw*vh)) {                                            \
 274             thew = hw;                                                        \
 275             theh = hh;                                                        \
 276           } else {                                                            \
 277             thew = vw;                                                        \
 278             theh = vh;                                                        \
 279           }                                                                   \
 280                                                                               \
 281           subrect.x = thex;                                                   \
 282           subrect.y = they;                                                   \
 283           subrect.w = thew;                                                   \
 284           subrect.h = theh;                                                   \
 285                                                                               \
 286           newLen = rreAfterBufLen + (bpp/8) + sz_rfbCoRRERectangle;           \
 287           if ((newLen > (w * h * (bpp/8))) || (newLen > rreAfterBufSize))     \
 288             return -1;                                                        \
 289                                                                               \
 290           numsubs += 1;                                                       \
 291           *((uint##bpp##_t*)(rreAfterBuf + rreAfterBufLen)) = cl;             \
 292           rreAfterBufLen += (bpp/8);                                          \
 293           memcpy(&rreAfterBuf[rreAfterBufLen],&subrect,sz_rfbCoRRERectangle); \
 294           rreAfterBufLen += sz_rfbCoRRERectangle;                             \
 295                                                                               \
 296           /*                                                                  \
 297            * Now mark the subrect as done.                                    \
 298            */                                                                 \
 299           for (j=they; j < (they+theh); j++) {                                \
 300             for (i=thex; i < (thex+thew); i++) {                              \
 301               data[j*w+i] = bg;                                               \
 302             }                                                                 \
 303           }                                                                   \
 304         }                                                                     \
 305       }                                                                       \
 306     }                                                                         \
 307                                                                               \
 308     return numsubs;                                                           \
 309 }
 310
 311 DEFINE_SUBRECT_ENCODE(8)
 312 DEFINE_SUBRECT_ENCODE(16)
 313 DEFINE_SUBRECT_ENCODE(32)
 314
 315
 316 /*
 317  * getBgColour() gets the most prevalent colour in a byte array.
 318  */
 319 static uint32_t
 320 getBgColour(char *data, int size, int bpp)
 321 {
 322
 323 #define NUMCLRS 256
 324
 325   static int counts[NUMCLRS];
 326   int i,j,k;
 327
 328   int maxcount = 0;
 329   uint8_t maxclr = 0;
 330
 331   if (bpp != 8) {
 332     if (bpp == 16) {
 333       return ((uint16_t *)data)[0];
 334     } else if (bpp == 32) {
 335       return ((uint32_t *)data)[0];
 336     } else {
 337       rfbLog("getBgColour: bpp %d?\n",bpp);
 338       return 0;
 339     }
 340   }
 341
 342   for (i=0; i<NUMCLRS; i++) {
 343     counts[i] = 0;
 344   }
 345
 346   for (j=0; j<size; j++) {
 347     k = (int)(((uint8_t *)data)[j]);
 348     if (k >= NUMCLRS) {
 349       rfbLog("getBgColour: unusual colour = %d\n", k);
 350       return 0;
 351     }
 352     counts[k] += 1;
 353     if (counts[k] > maxcount) {
 354       maxcount = counts[k];
 355       maxclr = ((uint8_t *)data)[j];
 356     }
 357   }
 358
 359   return maxclr;
 360 }