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