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