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

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