git.sesse.net Git - rdpsrv/blob - Xserver/programs/Xserver/hw/vnc/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  *  Copyright (C) 1999 AT&T Laboratories Cambridge.  All Rights Reserved.
  11  *
  12  *  This is free software; you can redistribute it and/or modify
  13  *  it under the terms of the GNU General Public License as published by
  14  *  the Free Software Foundation; either version 2 of the License, or
  15  *  (at your option) any later version.
  16  *
  17  *  This software is distributed in the hope that it will be useful,
  18  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  *  GNU General Public License for more details.
  21  *
  22  *  You should have received a copy of the GNU General Public License
  23  *  along with this software; if not, write to the Free Software
  24  *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307,
  25  *  USA.
  26  */
  27
  28 #include <stdio.h>
  29 #include "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;
  44
  45 static int subrectEncode8(CARD8 *data, int w, int h);
  46 static int subrectEncode16(CARD16 *data, int w, int h);
  47 static int subrectEncode32(CARD32 *data, int w, int h);
  48 static CARD32 getBgColour(char *data, int size, int bpp);
  49 static Bool rfbSendSmallRectEncodingCoRRE(rfbClientPtr cl, int x, int y,
  50                                           int w, int h);
  51
  52
  53 /*
  54  * rfbSendRectEncodingCoRRE - send an arbitrary size rectangle using CoRRE
  55  * encoding.
  56  */
  57
  58 Bool
  59 rfbSendRectEncodingCoRRE(cl, x, y, w, h)
  60     rfbClientPtr cl;
  61     int x, y, w, h;
  62 {
  63     if (h > cl->correMaxHeight) {
  64       return (rfbSendRectEncodingCoRRE(cl, x, y, w, cl->correMaxHeight) &&
  65               rfbSendRectEncodingCoRRE(cl, x, y + cl->correMaxHeight, w,
  66                                        h - cl->correMaxHeight));
  67     }
  68
  69     if (w > cl->correMaxWidth) {
  70       return (rfbSendRectEncodingCoRRE(cl, x, y, cl->correMaxWidth, h) &&
  71               rfbSendRectEncodingCoRRE(cl, x + cl->correMaxWidth, y,
  72                                        w - cl->correMaxWidth, h));
  73     }
  74
  75     return rfbSendSmallRectEncodingCoRRE(cl, x, y, w, h);
  76 }
  77
  78
  79
  80 /*
  81  * rfbSendSmallRectEncodingCoRRE - send a small (guaranteed < 256x256)
  82  * rectangle using CoRRE encoding.
  83  */
  84
  85 static Bool
  86 rfbSendSmallRectEncodingCoRRE(cl, x, y, w, h)
  87     rfbClientPtr cl;
  88     int x, y, w, h;
  89 {
  90     rfbFramebufferUpdateRectHeader rect;
  91     rfbRREHeader hdr;
  92     int nSubrects;
  93     int i;
  94     char *fbptr = (rfbScreen.pfbMemory + (rfbScreen.paddedWidthInBytes * y)
  95                    + (x * (rfbScreen.bitsPerPixel / 8)));
  96
  97     int maxRawSize = (rfbScreen.width * rfbScreen.height
  98                       * (cl->format.bitsPerPixel / 8));
  99
 100     if (rreBeforeBufSize < maxRawSize) {
 101         rreBeforeBufSize = maxRawSize;
 102         if (rreBeforeBuf == NULL)
 103             rreBeforeBuf = (char *)xalloc(rreBeforeBufSize);
 104         else
 105             rreBeforeBuf = (char *)xrealloc(rreBeforeBuf, rreBeforeBufSize);
 106     }
 107
 108     if (rreAfterBufSize < maxRawSize) {
 109         rreAfterBufSize = maxRawSize;
 110         if (rreAfterBuf == NULL)
 111             rreAfterBuf = (char *)xalloc(rreAfterBufSize);
 112         else
 113             rreAfterBuf = (char *)xrealloc(rreAfterBuf, rreAfterBufSize);
 114     }
 115
 116     (*cl->translateFn)(cl->translateLookupTable, &rfbServerFormat,
 117                        &cl->format, fbptr, rreBeforeBuf,
 118                        rfbScreen.paddedWidthInBytes, w, h);
 119
 120     switch (cl->format.bitsPerPixel) {
 121     case 8:
 122         nSubrects = subrectEncode8((CARD8 *)rreBeforeBuf, w, h);
 123         break;
 124     case 16:
 125         nSubrects = subrectEncode16((CARD16 *)rreBeforeBuf, w, h);
 126         break;
 127     case 32:
 128         nSubrects = subrectEncode32((CARD32 *)rreBeforeBuf, w, h);
 129         break;
 130     default:
 131         rfbLog("getBgColour: bpp %d?\n",cl->format.bitsPerPixel);
 132         exit(1);
 133     }
 134
 135     if (nSubrects < 0) {
 136
 137         /* RRE encoding was too large, use raw */
 138
 139         return rfbSendRectEncodingRaw(cl, x, y, w, h);
 140     }
 141
 142     cl->rfbRectanglesSent[rfbEncodingCoRRE]++;
 143     cl->rfbBytesSent[rfbEncodingCoRRE] += (sz_rfbFramebufferUpdateRectHeader
 144                                            + sz_rfbRREHeader + rreAfterBufLen);
 145
 146     if (ublen + sz_rfbFramebufferUpdateRectHeader + sz_rfbRREHeader
 147         > UPDATE_BUF_SIZE)
 148     {
 149         if (!rfbSendUpdateBuf(cl))
 150             return FALSE;
 151     }
 152
 153     rect.r.x = Swap16IfLE(x);
 154     rect.r.y = Swap16IfLE(y);
 155     rect.r.w = Swap16IfLE(w);
 156     rect.r.h = Swap16IfLE(h);
 157     rect.encoding = Swap32IfLE(rfbEncodingCoRRE);
 158
 159     memcpy(&updateBuf[ublen], (char *)&rect,
 160            sz_rfbFramebufferUpdateRectHeader);
 161     ublen += sz_rfbFramebufferUpdateRectHeader;
 162
 163     hdr.nSubrects = Swap32IfLE(nSubrects);
 164
 165     memcpy(&updateBuf[ublen], (char *)&hdr, sz_rfbRREHeader);
 166     ublen += sz_rfbRREHeader;
 167
 168     for (i = 0; i < rreAfterBufLen;) {
 169
 170         int bytesToCopy = UPDATE_BUF_SIZE - ublen;
 171
 172         if (i + bytesToCopy > rreAfterBufLen) {
 173             bytesToCopy = rreAfterBufLen - i;
 174         }
 175
 176         memcpy(&updateBuf[ublen], &rreAfterBuf[i], bytesToCopy);
 177
 178         ublen += bytesToCopy;
 179         i += bytesToCopy;
 180
 181         if (ublen == UPDATE_BUF_SIZE) {
 182             if (!rfbSendUpdateBuf(cl))
 183                 return FALSE;
 184         }
 185     }
 186
 187     return TRUE;
 188 }
 189
 190
 191
 192 /*
 193  * subrectEncode() encodes the given multicoloured rectangle as a background
 194  * colour overwritten by single-coloured rectangles.  It returns the number
 195  * of subrectangles in the encoded buffer, or -1 if subrect encoding won't
 196  * fit in the buffer.  It puts the encoded rectangles in rreAfterBuf.  The
 197  * single-colour rectangle partition is not optimal, but does find the biggest
 198  * horizontal or vertical rectangle top-left anchored to each consecutive
 199  * coordinate position.
 200  *
 201  * The coding scheme is simply [<bgcolour><subrect><subrect>...] where each
 202  * <subrect> is [<colour><x><y><w><h>].
 203  */
 204
 205 #define DEFINE_SUBRECT_ENCODE(bpp)                                            \
 206 static int                                                                    \
 207 subrectEncode##bpp(data,w,h)                                                  \
 208     CARD##bpp *data;                                                          \
 209     int w;                                                                    \
 210     int h;                                                                    \
 211 {                                                                             \
 212     CARD##bpp cl;                                                             \
 213     rfbCoRRERectangle subrect;                                                \
 214     int x,y;                                                                  \
 215     int i,j;                                                                  \
 216     int hx=0,hy,vx=0,vy;                                                      \
 217     int hyflag;                                                               \
 218     CARD##bpp *seg;                                                           \
 219     CARD##bpp *line;                                                          \
 220     int hw,hh,vw,vh;                                                          \
 221     int thex,they,thew,theh;                                                  \
 222     int numsubs = 0;                                                          \
 223     int newLen;                                                               \
 224     CARD##bpp bg = (CARD##bpp)getBgColour((char*)data,w*h,bpp);               \
 225                                                                               \
 226     *((CARD##bpp*)rreAfterBuf) = bg;                                          \
 227                                                                               \
 228     rreAfterBufLen = (bpp/8);                                                 \
 229                                                                               \
 230     for (y=0; y<h; y++) {                                                     \
 231       line = data+(y*w);                                                      \
 232       for (x=0; x<w; x++) {                                                   \
 233         if (line[x] != bg) {                                                  \
 234           cl = line[x];                                                       \
 235           hy = y-1;                                                           \
 236           hyflag = 1;                                                         \
 237           for (j=y; j<h; j++) {                                               \
 238             seg = data+(j*w);                                                 \
 239             if (seg[x] != cl) {break;}                                        \
 240             i = x;                                                            \
 241             while ((seg[i] == cl) && (i < w)) i += 1;                         \
 242             i -= 1;                                                           \
 243             if (j == y) vx = hx = i;                                          \
 244             if (i < vx) vx = i;                                               \
 245             if ((hyflag > 0) && (i >= hx)) {hy += 1;} else {hyflag = 0;}      \
 246           }                                                                   \
 247           vy = j-1;                                                           \
 248                                                                               \
 249           /*  We now have two possible subrects: (x,y,hx,hy) and (x,y,vx,vy)  \
 250            *  We'll choose the bigger of the two.                             \
 251            */                                                                 \
 252           hw = hx-x+1;                                                        \
 253           hh = hy-y+1;                                                        \
 254           vw = vx-x+1;                                                        \
 255           vh = vy-y+1;                                                        \
 256                                                                               \
 257           thex = x;                                                           \
 258           they = y;                                                           \
 259                                                                               \
 260           if ((hw*hh) > (vw*vh)) {                                            \
 261             thew = hw;                                                        \
 262             theh = hh;                                                        \
 263           } else {                                                            \
 264             thew = vw;                                                        \
 265             theh = vh;                                                        \
 266           }                                                                   \
 267                                                                               \
 268           subrect.x = thex;                                                   \
 269           subrect.y = they;                                                   \
 270           subrect.w = thew;                                                   \
 271           subrect.h = theh;                                                   \
 272                                                                               \
 273           newLen = rreAfterBufLen + (bpp/8) + sz_rfbCoRRERectangle;           \
 274           if ((newLen > (w * h * (bpp/8))) || (newLen > rreAfterBufSize))     \
 275             return -1;                                                        \
 276                                                                               \
 277           numsubs += 1;                                                       \
 278           *((CARD##bpp*)(rreAfterBuf + rreAfterBufLen)) = cl;                 \
 279           rreAfterBufLen += (bpp/8);                                          \
 280           memcpy(&rreAfterBuf[rreAfterBufLen],&subrect,sz_rfbCoRRERectangle); \
 281           rreAfterBufLen += sz_rfbCoRRERectangle;                             \
 282                                                                               \
 283           /*                                                                  \
 284            * Now mark the subrect as done.                                    \
 285            */                                                                 \
 286           for (j=they; j < (they+theh); j++) {                                \
 287             for (i=thex; i < (thex+thew); i++) {                              \
 288               data[j*w+i] = bg;                                               \
 289             }                                                                 \
 290           }                                                                   \
 291         }                                                                     \
 292       }                                                                       \
 293     }                                                                         \
 294                                                                               \
 295     return numsubs;                                                           \
 296 }
 297
 298 DEFINE_SUBRECT_ENCODE(8)
 299 DEFINE_SUBRECT_ENCODE(16)
 300 DEFINE_SUBRECT_ENCODE(32)
 301
 302
 303 /*
 304  * getBgColour() gets the most prevalent colour in a byte array.
 305  */
 306 static CARD32
 307 getBgColour(data,size,bpp)
 308     char *data;
 309     int size;
 310     int bpp;
 311 {
 312
 313 #define NUMCLRS 256
 314
 315   static int counts[NUMCLRS];
 316   int i,j,k;
 317
 318   int maxcount = 0;
 319   CARD8 maxclr = 0;
 320
 321   if (bpp != 8) {
 322     if (bpp == 16) {
 323       return ((CARD16 *)data)[0];
 324     } else if (bpp == 32) {
 325       return ((CARD32 *)data)[0];
 326     } else {
 327       rfbLog("getBgColour: bpp %d?\n",bpp);
 328       exit(1);
 329     }
 330   }
 331
 332   for (i=0; i<NUMCLRS; i++) {
 333     counts[i] = 0;
 334   }
 335
 336   for (j=0; j<size; j++) {
 337     k = (int)(((CARD8 *)data)[j]);
 338     if (k >= NUMCLRS) {
 339       rfbLog("getBgColour: unusual colour = %d\n", k);
 340       exit(1);
 341     }
 342     counts[k] += 1;
 343     if (counts[k] > maxcount) {
 344       maxcount = counts[k];
 345       maxclr = ((CARD8 *)data)[j];
 346     }
 347   }
 348
 349   return maxclr;
 350 }