LibVNCServer/LibVNCClient
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
zrleencodetemplate.c
Go to the documentation of this file.
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 
97 static void ZRLE_ENCODE (int x, int y, int w, int h,
98  zrleOutStream* os, void* buf
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 
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;
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