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