1 /*
2 * Copyright (C) 2002 RealVNC Ltd. All Rights Reserved.
3 * Copyright (C) 2003 Sun Microsystems, Inc.
4 *
5 * This is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
9 *
10 * This software is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this software; if not, write to the Free Software
17 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
18 * USA.
19 */
20
21 /*
22 * Before including this file, you must define a number of CPP macros.
23 *
24 * BPP should be 8, 16 or 32 depending on the bits per pixel.
25 * GET_IMAGE_INTO_BUF should be some code which gets a rectangle of pixel data
26 * into the given buffer. EXTRA_ARGS can be defined to pass any other
27 * arguments needed by GET_IMAGE_INTO_BUF.
28 *
29 * Note that the buf argument to ZRLE_ENCODE needs to be at least one pixel
30 * bigger than the largest tile of pixel data, since the ZRLE encoding
31 * algorithm writes to the position one past the end of the pixel data.
32 */
33
34 #include "zrleoutstream.h"
35 #include "zrlepalettehelper.h"
36 #include <assert.h>
37
38 /* __RFB_CONCAT2 concatenates its two arguments. __RFB_CONCAT2E does the same
39 but also expands its arguments if they are macros */
40
41 #ifndef __RFB_CONCAT2E
42 #define __RFB_CONCAT2(a,b) a##b
43 #define __RFB_CONCAT2E(a,b) __RFB_CONCAT2(a,b)
44 #endif
45
46 #ifndef __RFB_CONCAT3E
47 #define __RFB_CONCAT3(a,b,c) a##b##c
48 #define __RFB_CONCAT3E(a,b,c) __RFB_CONCAT3(a,b,c)
49 #endif
50
51 #undef END_FIX
52 #if ZYWRLE_ENDIAN == ENDIAN_LITTLE
53 # define END_FIX LE
54 #elif ZYWRLE_ENDIAN == ENDIAN_BIG
55 # define END_FIX BE
56 #else
57 # define END_FIX NE
58 #endif
59
60 #ifdef CPIXEL
61 #define PIXEL_T __RFB_CONCAT2E(zrle_U,BPP)
62 #define zrleOutStreamWRITE_PIXEL __RFB_CONCAT2E(zrleOutStreamWriteOpaque,CPIXEL)
63 #define ZRLE_ENCODE __RFB_CONCAT3E(zrleEncode,CPIXEL,END_FIX)
64 #define ZRLE_ENCODE_TILE __RFB_CONCAT3E(zrleEncodeTile,CPIXEL,END_FIX)
65 #define BPPOUT 24
66 #elif BPP==15
67 #define PIXEL_T __RFB_CONCAT2E(zrle_U,16)
68 #define zrleOutStreamWRITE_PIXEL __RFB_CONCAT2E(zrleOutStreamWriteOpaque,16)
69 #define ZRLE_ENCODE __RFB_CONCAT3E(zrleEncode,BPP,END_FIX)
70 #define ZRLE_ENCODE_TILE __RFB_CONCAT3E(zrleEncodeTile,BPP,END_FIX)
71 #define BPPOUT 16
72 #else
73 #define PIXEL_T __RFB_CONCAT2E(zrle_U,BPP)
74 #define zrleOutStreamWRITE_PIXEL __RFB_CONCAT2E(zrleOutStreamWriteOpaque,BPP)
75 #define ZRLE_ENCODE __RFB_CONCAT3E(zrleEncode,BPP,END_FIX)
76 #define ZRLE_ENCODE_TILE __RFB_CONCAT3E(zrleEncodeTile,BPP,END_FIX)
77 #define BPPOUT BPP
78 #endif
79
80 #ifndef ZRLE_ONCE
81 #define ZRLE_ONCE
82
83 static const int bitsPerPackedPixel[] = {
84 0, 1, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
85 };
86
87 #endif /* ZRLE_ONCE */
88
89 void ZRLE_ENCODE_TILE (PIXEL_T* data, int w, int h, zrleOutStream* os,
90 int zywrle_level, int *zywrleBuf, void *paletteHelper);
91
92 #if BPP!=8
93 #define ZYWRLE_ENCODE
94 #include "zywrletemplate.c"
95 #endif
96
ZRLE_ENCODE(int x,int y,int w,int h,zrleOutStream * os,void * buf EXTRA_ARGS)97 static void ZRLE_ENCODE (int x, int y, int w, int h,
98 zrleOutStream* os, void* buf
99 EXTRA_ARGS
100 )
101 {
102 int ty;
103 for (ty = y; ty < y+h; ty += rfbZRLETileHeight) {
104 int tx, th = rfbZRLETileHeight;
105 if (th > y+h-ty) th = y+h-ty;
106 for (tx = x; tx < x+w; tx += rfbZRLETileWidth) {
107 int tw = rfbZRLETileWidth;
108 if (tw > x+w-tx) tw = x+w-tx;
109
110 GET_IMAGE_INTO_BUF(tx,ty,tw,th,buf);
111
112 if (cl->paletteHelper == NULL) {
113 cl->paletteHelper = (void *) calloc(sizeof(zrlePaletteHelper), 1);
114 }
115
116 ZRLE_ENCODE_TILE((PIXEL_T*)buf, tw, th, os,
117 cl->zywrleLevel, cl->zywrleBuf, cl->paletteHelper);
118 }
119 }
120 zrleOutStreamFlush(os);
121 }
122
123
ZRLE_ENCODE_TILE(PIXEL_T * data,int w,int h,zrleOutStream * os,int zywrle_level,int * zywrleBuf,void * paletteHelper)124 void ZRLE_ENCODE_TILE(PIXEL_T* data, int w, int h, zrleOutStream* os,
125 int zywrle_level, int *zywrleBuf, void *paletteHelper)
126 {
127 /* First find the palette and the number of runs */
128
129 zrlePaletteHelper *ph;
130
131 int runs = 0;
132 int singlePixels = 0;
133
134 rfbBool useRle;
135 rfbBool usePalette;
136
137 int estimatedBytes;
138 int plainRleBytes;
139 int i;
140
141 PIXEL_T* ptr = data;
142 PIXEL_T* end = ptr + h * w;
143 *end = ~*(end-1); /* one past the end is different so the while loop ends */
144
145 ph = (zrlePaletteHelper *) paletteHelper;
146 zrlePaletteHelperInit(ph);
147
148 while (ptr < end) {
149 PIXEL_T pix = *ptr;
150 if (*++ptr != pix) {
151 singlePixels++;
152 } else {
153 while (*++ptr == pix) ;
154 runs++;
155 }
156 zrlePaletteHelperInsert(ph, pix);
157 }
158
159 /* Solid tile is a special case */
160
161 if (ph->size == 1) {
162 zrleOutStreamWriteU8(os, 1);
163 zrleOutStreamWRITE_PIXEL(os, ph->palette[0]);
164 return;
165 }
166
167 /* Try to work out whether to use RLE and/or a palette. We do this by
168 estimating the number of bytes which will be generated and picking the
169 method which results in the fewest bytes. Of course this may not result
170 in the fewest bytes after compression... */
171
172 useRle = FALSE;
173 usePalette = FALSE;
174
175 estimatedBytes = w * h * (BPPOUT/8); /* start assuming raw */
176
177 #if BPP!=8
178 if (zywrle_level > 0 && !(zywrle_level & 0x80))
179 estimatedBytes >>= zywrle_level;
180 #endif
181
182 plainRleBytes = ((BPPOUT/8)+1) * (runs + singlePixels);
183
184 if (plainRleBytes < estimatedBytes) {
185 useRle = TRUE;
186 estimatedBytes = plainRleBytes;
187 }
188
189 if (ph->size < 128) {
190 int paletteRleBytes = (BPPOUT/8) * ph->size + 2 * runs + singlePixels;
191
192 if (paletteRleBytes < estimatedBytes) {
193 useRle = TRUE;
194 usePalette = TRUE;
195 estimatedBytes = paletteRleBytes;
196 }
197
198 if (ph->size < 17) {
199 int packedBytes = ((BPPOUT/8) * ph->size +
200 w * h * bitsPerPackedPixel[ph->size-1] / 8);
201
202 if (packedBytes < estimatedBytes) {
203 useRle = FALSE;
204 usePalette = TRUE;
205 estimatedBytes = packedBytes;
206 }
207 }
208 }
209
210 if (!usePalette) ph->size = 0;
211
212 zrleOutStreamWriteU8(os, (useRle ? 128 : 0) | ph->size);
213
214 for (i = 0; i < ph->size; i++) {
215 zrleOutStreamWRITE_PIXEL(os, ph->palette[i]);
216 }
217
218 if (useRle) {
219
220 PIXEL_T* ptr = data;
221 PIXEL_T* end = ptr + w * h;
222 PIXEL_T* runStart;
223 PIXEL_T pix;
224 while (ptr < end) {
225 int len;
226 runStart = ptr;
227 pix = *ptr++;
228 while (*ptr == pix && ptr < end)
229 ptr++;
230 len = ptr - runStart;
231 if (len <= 2 && usePalette) {
232 int index = zrlePaletteHelperLookup(ph, pix);
233 if (len == 2)
234 zrleOutStreamWriteU8(os, index);
235 zrleOutStreamWriteU8(os, index);
236 continue;
237 }
238 if (usePalette) {
239 int index = zrlePaletteHelperLookup(ph, pix);
240 zrleOutStreamWriteU8(os, index | 128);
241 } else {
242 zrleOutStreamWRITE_PIXEL(os, pix);
243 }
244 len -= 1;
245 while (len >= 255) {
246 zrleOutStreamWriteU8(os, 255);
247 len -= 255;
248 }
249 zrleOutStreamWriteU8(os, len);
250 }
251
252 } else {
253
254 /* no RLE */
255
256 if (usePalette) {
257 int bppp;
258 PIXEL_T* ptr = data;
259
260 /* packed pixels */
261
262 assert (ph->size < 17);
263
264 bppp = bitsPerPackedPixel[ph->size-1];
265
266 for (i = 0; i < h; i++) {
267 zrle_U8 nbits = 0;
268 zrle_U8 byte = 0;
269
270 PIXEL_T* eol = ptr + w;
271
272 while (ptr < eol) {
273 PIXEL_T pix = *ptr++;
274 zrle_U8 index = zrlePaletteHelperLookup(ph, pix);
275 byte = (byte << bppp) | index;
276 nbits += bppp;
277 if (nbits >= 8) {
278 zrleOutStreamWriteU8(os, byte);
279 nbits = 0;
280 }
281 }
282 if (nbits > 0) {
283 byte <<= 8 - nbits;
284 zrleOutStreamWriteU8(os, byte);
285 }
286 }
287 } else {
288
289 /* raw */
290
291 #if BPP!=8
292 if (zywrle_level > 0 && !(zywrle_level & 0x80)) {
293 ZYWRLE_ANALYZE(data, data, w, h, w, zywrle_level, zywrleBuf);
294 ZRLE_ENCODE_TILE(data, w, h, os, zywrle_level | 0x80, zywrleBuf, paletteHelper);
295 }
296 else
297 #endif
298 {
299 #ifdef CPIXEL
300 PIXEL_T *ptr;
301 for (ptr = data; ptr < data+w*h; ptr++)
302 zrleOutStreamWRITE_PIXEL(os, *ptr);
303 #else
304 zrleOutStreamWriteBytes(os, (zrle_U8 *)data, w*h*(BPP/8));
305 #endif
306 }
307 }
308 }
309 }
310
311 #undef PIXEL_T
312 #undef zrleOutStreamWRITE_PIXEL
313 #undef ZRLE_ENCODE
314 #undef ZRLE_ENCODE_TILE
315 #undef ZYWRLE_ENCODE_TILE
316 #undef BPPOUT
317