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