1 /* VNC Reflector
2 * Copyright (C) 2001-2003 HorizonLive.com, Inc. All rights reserved.
3 *
4 * This software is released under the terms specified in the file LICENSE,
5 * included. HorizonLive provides e-Learning and collaborative synchronous
6 * presentation solutions in a totally Web-based environment. For more
7 * information about HorizonLive, please see our website at
8 * http://www.horizonlive.com.
9 *
10 * This software was authored by Constantin Kaplinsky <const@ce.cctpu.edu.ru>
11 * and sponsored by HorizonLive.com, Inc.
12 *
13 * $Id: encode.c,v 1.25 2003/04/21 17:20:35 const Exp $
14 * Encoding screen rectangles.
15 */
16
17 #include <stdio.h>
18 #include <stdlib.h>
19 #include <string.h>
20 #include <sys/types.h>
21 #include <zlib.h>
22
23 #include "rfblib.h"
24 #include "reflector.h"
25 #include "async_io.h"
26 #include "translate.h"
27 #include "client_io.h"
28 #include "encode.h"
29
30 /* This structure describes cached data for a properly-aligned 16x16 tile. */
31 /* NOTE: If hextile_datasize is not 0 then valid_f should be non-zero too, */
32 /* but if valid_f is not 0, do not expect hextile_datasize to be non-zero. */
33 typedef struct _TILE_HINTS {
34 CARD8 valid_f; /* At least meta-data available if not 0 */
35 CARD8 num_colors; /* Meta-data: number of colors (1, 2 or 0) */
36 CARD8 bg; /* Meta-data: background color */
37 CARD8 fg; /* Meta-data: foreground color */
38 CARD16 hextile_datasize; /* Hextile-encoded data available if not 0 */
39 } TILE_HINTS;
40
41 /* Cache for the encoded data */
42 static TILE_HINTS *s_hints8 = NULL;
43 static CARD8 *s_cache8 = NULL;
44
45 /* Two-color palette */
46 typedef struct _PALETTE2 {
47 int num_colors;
48 CARD32 bg;
49 CARD32 fg;
50 } PALETTE2;
51
52 /********************************************************************/
53 /* Maintaining cache structures */
54 /********************************************************************/
55
56 static int s_cache_size;
57
58 /* FIXME: Allocate cache on demand? */
59 /* FIXME: Bad function naming. */
60
allocate_enc_cache(void)61 int allocate_enc_cache(void)
62 {
63 int tiles_x, tiles_y;
64
65 free_enc_cache();
66
67 tiles_x = (int)g_fb_width / 16;
68 tiles_y = (int)g_fb_height / 16;
69 s_hints8 = calloc(tiles_x * tiles_y, sizeof(TILE_HINTS));
70 if (s_hints8 == NULL) {
71 return 0;
72 }
73 s_cache_size = tiles_x * tiles_y * sizeof(TILE_HINTS);
74
75 s_cache8 = malloc(tiles_x * tiles_y * HEXTILE_MAX_TILE_DATASIZE);
76 if (s_cache8 == NULL) {
77 free(s_hints8);
78 s_hints8 = NULL;
79 return 0;
80 }
81 s_cache_size += tiles_x * tiles_y * HEXTILE_MAX_TILE_DATASIZE;
82
83 return 1;
84 }
85
sizeof_enc_cache(void)86 int sizeof_enc_cache(void)
87 {
88 return s_cache_size;
89 }
90
invalidate_enc_cache(FB_RECT * r)91 void invalidate_enc_cache(FB_RECT *r)
92 {
93 int tiles_in_row;
94 int tile_x0, tile_y0, tile_x1, tile_y1;
95 int x, y;
96
97 tiles_in_row = (int)g_fb_width / 16;
98
99 tile_x0 = r->x / 16;
100 tile_y0 = r->y / 16;
101 tile_x1 = (r->x + r->w - 1) / 16;
102 if (tile_x1 >= tiles_in_row)
103 tile_x1 = tiles_in_row - 1;
104 tile_y1 = (r->y + r->h - 1) / 16;
105 if (tile_y1 >= (int)g_fb_height / 16)
106 tile_y1 = (int)g_fb_height / 16 - 1;
107
108 for (y = tile_y0; y <= tile_y1; y++)
109 for (x = tile_x0; x <= tile_x1; x++)
110 s_hints8[y * tiles_in_row + x].valid_f = 0;
111 }
112
free_enc_cache(void)113 void free_enc_cache(void)
114 {
115 if (s_hints8 != NULL) {
116 free(s_hints8);
117 s_hints8 = NULL;
118 }
119 if (s_cache8 != NULL) {
120 free(s_cache8);
121 s_cache8 = NULL;
122 }
123 s_cache_size = 0;
124 }
125
126 /********************************************************************/
127 /* Simple "encoders" */
128 /********************************************************************/
129
130 /*
131 * Raw encoder
132 */
133
rfb_encode_raw_block(CL_SLOT * cl,FB_RECT * r)134 AIO_BLOCK *rfb_encode_raw_block(CL_SLOT *cl, FB_RECT *r)
135 {
136 AIO_BLOCK *block;
137
138 block = malloc(sizeof(AIO_BLOCK) + 12 +
139 r->w * r->h * (cl->format.bits_pixel / 8));
140 if (block) {
141 put_rect_header(block->data, r);
142 (*cl->trans_func)(&block->data[12], r, cl->trans_table);
143 block->data_size = 12 + r->w * r->h * (cl->format.bits_pixel / 8);
144 }
145
146 return block;
147 }
148
149 /*
150 * CopyRect "encoder" :-)
151 */
152
rfb_encode_copyrect_block(CL_SLOT * cl,FB_RECT * r)153 AIO_BLOCK *rfb_encode_copyrect_block(CL_SLOT *cl, FB_RECT *r)
154 {
155 AIO_BLOCK *block;
156
157 block = malloc(sizeof(AIO_BLOCK) + 12 + 4);
158 if (block) {
159 put_rect_header(block->data, r);
160 buf_put_CARD16(&block->data[12], r->src_x);
161 buf_put_CARD16(&block->data[14], r->src_y);
162 block->data_size = 12 + 4;
163 }
164
165 return block;
166 }
167
168 /*
169 * Tiny function to fill in rectangle header in an RFB update
170 */
171
put_rect_header(CARD8 * buf,FB_RECT * r)172 int put_rect_header(CARD8 *buf, FB_RECT *r)
173 {
174
175 buf_put_CARD16(buf, r->x);
176 buf_put_CARD16(&buf[2], r->y);
177 buf_put_CARD16(&buf[4], r->w);
178 buf_put_CARD16(&buf[6], r->h);
179 buf_put_CARD32(&buf[8], r->enc);
180
181 return 12; /* 12 bytes written */
182 }
183
184 /********************************************************************/
185 /* Hextile encoder */
186 /********************************************************************/
187
188 /* Medium-level functions */
189 static int encode_tile_using_cache(CARD8 *dst_buf, CL_SLOT *cl, FB_RECT *r);
190 static int encode_tile8(CARD8 *dst_buf, CL_SLOT *cl, FB_RECT *r);
191 static int encode_tile16(CARD8 *dst_buf, CL_SLOT *cl, FB_RECT *r);
192 static int encode_tile32(CARD8 *dst_buf, CL_SLOT *cl, FB_RECT *r);
193
194 /* Low-level functions */
195 static int encode_tile_ht8(CARD8 *dst_buf, CARD8 *tile_buf,
196 PALETTE2 *pal, FB_RECT *r);
197 static int encode_tile_ht16(CARD8 *dst_buf, CARD16 *tile_buf,
198 PALETTE2 *pal, FB_RECT *r);
199 static int encode_tile_ht32(CARD8 *dst_buf, CARD32 *tile_buf,
200 PALETTE2 *pal, FB_RECT *r);
201 static int encode_tile_raw8(CARD8 *dst_buf, CL_SLOT *cl, FB_RECT *r);
202 static int encode_tile_raw16(CARD8 *dst_buf, CL_SLOT *cl, FB_RECT *r);
203 static int encode_tile_raw32(CARD8 *dst_buf, CL_SLOT *cl, FB_RECT *r);
204 static void analyze_rect8(CARD8 *buf, PALETTE2 *pal, FB_RECT *r);
205 static void analyze_rect16(CARD16 *buf, PALETTE2 *pal, FB_RECT *r);
206 static void analyze_rect32(CARD32 *buf, PALETTE2 *pal, FB_RECT *r);
207
208 /* Variables to keep background color of previous tile */
209 static CARD32 prev_bg;
210 static int prev_bg_set;
211
212 /********************************************************************/
213 /* Hextile encoder: High-level stuff */
214 /********************************************************************/
215
216 /*
217 * Highest-level function implementing Hextile encoder. It iterates
218 * over tiles 16x16 or less pixels each, and calls appropriate
219 * lower-level functions for them.
220 */
221
rfb_encode_hextile_block(CL_SLOT * cl,FB_RECT * r)222 AIO_BLOCK *rfb_encode_hextile_block(CL_SLOT *cl, FB_RECT *r)
223 {
224 AIO_BLOCK *block;
225 int num_tiles;
226 int aligned_f;
227 int rx1, ry1;
228 FB_RECT tile_r;
229 CARD8 *data_ptr;
230
231 /* Calculate number of tiles per this rectangle */
232 num_tiles = ((r->w + 15) / 16) * ((r->h + 15) / 16);
233
234 /* Check if tiles are aligned on 16-pixel boundary */
235 aligned_f = (r->x & 0x0F) == 0 && (r->y & 0x0F) == 0;
236
237 /* Allocate a memory block of maximum possible size */
238 block = malloc(sizeof(AIO_BLOCK) + 12 +
239 r->w * r->h * (cl->format.bits_pixel / 8) +
240 num_tiles);
241 if (block == NULL)
242 return NULL;
243
244 put_rect_header(block->data, r);
245
246 prev_bg_set = 0;
247 data_ptr = (CARD8 *)&block->data[12];
248 rx1 = r->x + r->w;
249 ry1 = r->y + r->h;
250 tile_r.h = 16;
251
252 for (tile_r.y = r->y; tile_r.y < ry1; tile_r.y += 16) {
253 if (ry1 - tile_r.y < 16)
254 tile_r.h = ry1 - tile_r.y;
255 tile_r.w = 16;
256 for (tile_r.x = r->x; tile_r.x < rx1; tile_r.x += 16) {
257 if (rx1 - tile_r.x < 16)
258 tile_r.w = rx1 - tile_r.x;
259
260 switch (cl->format.bits_pixel) {
261 case 8:
262 /* 8-bit color: to cache or not to cache? */
263 if (aligned_f && cl->bgr233_f && tile_r.w == 16 && tile_r.h == 16)
264 data_ptr += encode_tile_using_cache(data_ptr, cl, &tile_r);
265 else
266 data_ptr += encode_tile8(data_ptr, cl, &tile_r);
267 break;
268 case 16:
269 data_ptr += encode_tile16(data_ptr, cl, &tile_r);
270 break;
271 case 32:
272 data_ptr += encode_tile32(data_ptr, cl, &tile_r);
273 break;
274 }
275 }
276 }
277
278 block->data_size = data_ptr - (CARD8 *)block->data;
279 return realloc(block, sizeof(AIO_BLOCK) + block->data_size);
280 }
281
282 static long s_cache_hits, s_cache_misses;
get_hextile_caching_stats(long * hits,long * misses)283 void get_hextile_caching_stats(long *hits, long *misses)
284 {
285 *hits = s_cache_hits; *misses = s_cache_misses;
286 }
287
288 /********************************************************************/
289 /* Medium-level stuff */
290 /********************************************************************/
291
292 /*
293 * Encode properly-aligned 16x16 tile in BGR233 pixel format, using
294 * data from cache if available, or saving encoded data in cache
295 * otherwise.
296 */
297
encode_tile_using_cache(CARD8 * dst_buf,CL_SLOT * cl,FB_RECT * r)298 static int encode_tile_using_cache(CARD8 *dst_buf, CL_SLOT *cl, FB_RECT *r)
299 {
300 int tiles_in_row, tile_ord;
301 TILE_HINTS *hints;
302 CARD8 *cache;
303 CARD8 *dst = dst_buf;
304 CARD8 tile_buf[256];
305 PALETTE2 pal;
306 int dst_bytes;
307
308 tiles_in_row = (int)g_fb_width / 16;
309 tile_ord = (r->y / 16) * tiles_in_row + (r->x / 16);
310 hints = &s_hints8[tile_ord];
311 cache = &s_cache8[tile_ord * HEXTILE_MAX_TILE_DATASIZE];
312
313 if (hints->valid_f && hints->hextile_datasize != 0) {
314
315 /* Cache hit! */
316 s_cache_hits++;
317
318 if (cache[0] & RFB_HEXTILE_RAW) {
319 /* Raw sub-encoding: copy cached data, forget previous background. */
320 memcpy(dst, cache, hints->hextile_datasize);
321 dst += hints->hextile_datasize;
322 prev_bg_set = 0;
323 } else {
324 if (prev_bg != hints->bg || !prev_bg_set) {
325 /* Just copy cached data. */
326 memcpy(dst, cache, hints->hextile_datasize);
327 dst += hints->hextile_datasize;
328 } else {
329 /* The same background color as in the previous tile: do not copy
330 second byte from the cache, clear RFB_HEXTILE_BG_SPECIFIED. */
331 *dst++ = (cache[0] & ~RFB_HEXTILE_BG_SPECIFIED);
332 memcpy(dst, &cache[2], hints->hextile_datasize);
333 dst += (hints->hextile_datasize - 2);
334 }
335 /* Remember previous background color. */
336 prev_bg = hints->bg;
337 prev_bg_set = 1;
338 }
339 dst_bytes = dst - dst_buf;
340
341 } else { /* Cache miss */
342
343 s_cache_misses++;
344
345 /* Step 1: Encode tile. */
346 (*cl->trans_func)(tile_buf, r, cl->trans_table);
347 if (hints->valid_f) {
348 /* Here we can save one analyze_rect8() call. */
349 pal.num_colors = (int)hints->num_colors;
350 pal.bg = (CARD32)hints->bg;
351 pal.fg = (CARD32)hints->fg;
352 } else {
353 analyze_rect8(tile_buf, &pal, r);
354 }
355 dst_bytes = encode_tile_ht8(dst_buf, tile_buf, &pal, r);
356 if (dst_bytes < 0)
357 dst_bytes = encode_tile_raw8(dst_buf, cl, r);
358
359 /* Step 2: Save meta-data in the cache. */
360 hints->num_colors = (CARD8)pal.num_colors;
361 hints->bg = (CARD8)pal.bg;
362 hints->fg = (CARD8)pal.fg;
363 hints->valid_f = 1;
364
365 /* Step 3: Save encoded data in the cache. */
366 if (dst_buf[0] & RFB_HEXTILE_RAW) {
367 memcpy(cache, dst_buf, dst_bytes);
368 hints->hextile_datasize = dst_bytes;
369 } else {
370 if (dst_buf[0] & RFB_HEXTILE_BG_SPECIFIED) {
371 memcpy(cache, dst_buf, dst_bytes);
372 hints->hextile_datasize = dst_bytes;
373 } else {
374 /* Insert background color into the cached data. */
375 cache[0] = (dst_buf[0] | RFB_HEXTILE_BG_SPECIFIED);
376 cache[1] = (CARD8)pal.bg;
377 memcpy(&cache[2], &dst_buf[1], dst_bytes - 1);
378 hints->hextile_datasize = dst_bytes + 1;
379 }
380 }
381
382 }
383
384 return dst_bytes;
385 }
386
387 /*
388 * Analyze and encode a tile.
389 */
390
391 #define DEFINE_ENCODE_TILE(bpp) \
392 \
393 static int encode_tile##bpp(CARD8 *dst_buf, CL_SLOT *cl, FB_RECT *r) \
394 { \
395 CARD##bpp tile_buf[256]; \
396 PALETTE2 pal; \
397 int bytes; \
398 \
399 /* Translate pixel data into client's format. */ \
400 (*cl->trans_func)(tile_buf, r, cl->trans_table); \
401 \
402 /* Count number of colors, consider background & foreground. */ \
403 analyze_rect##bpp(tile_buf, &pal, r); \
404 \
405 /* Try to encode tile representing it as a set of subrects. */ \
406 bytes = encode_tile_ht##bpp(dst_buf, tile_buf, &pal, r); \
407 \
408 /* If such encoding was inefficient, use raw sub-encoding. */ \
409 if (bytes < 0) \
410 bytes = encode_tile_raw##bpp(dst_buf, cl, r); \
411 \
412 return bytes; \
413 }
414
415 DEFINE_ENCODE_TILE(8)
416 DEFINE_ENCODE_TILE(16)
417 DEFINE_ENCODE_TILE(32)
418
419 /********************************************************************/
420 /* Low-level stuff */
421 /********************************************************************/
422
423 /*
424 * A function to encode a tile (of size 16x16 or less) using Hextile
425 * encoding. The tile_buf should point to raw pixel data for the tile
426 * in client pixel format. The dst_buf argument should point to an
427 * array of size at least (256 * (cl->format.bits_pixel/8) + 1) bytes.
428 * The pal argument should point to a valid PALETTE2 structire filled
429 * in by the analyze_rectNN function.
430 *
431 * Return value: the number of bytes put into the dst_buf or -1 if
432 * this tile should be raw-encoded.
433 *
434 * NOTE: tile_buf[] contents would be destroyed by this function.
435 */
436
437 #define DEFINE_ENCODE_TILE_HT(bpp) \
438 \
439 static int encode_tile_ht##bpp(CARD8 *dst_buf, CARD##bpp *tile_buf, \
440 PALETTE2 *pal, FB_RECT *r) \
441 { \
442 CARD8 *dst = dst_buf; \
443 CARD8 *dst_num_subrects; \
444 CARD8 *dst_limit; \
445 int x, y, sx, sy; \
446 int best_w, best_h, max_x; \
447 CARD##bpp color, bg_color; \
448 CARD8 subenc = 0; \
449 \
450 bg_color = (CARD##bpp)pal->bg; \
451 \
452 /* Set appropriate sub-encoding flags */ \
453 if (prev_bg != pal->bg || !prev_bg_set) { \
454 subenc |= RFB_HEXTILE_BG_SPECIFIED; \
455 } \
456 if (pal->num_colors != 1) { \
457 subenc |= RFB_HEXTILE_ANY_SUBRECTS; \
458 if (pal->num_colors == 0) \
459 subenc |= RFB_HEXTILE_SUBRECTS_COLOURED; \
460 else \
461 subenc |= RFB_HEXTILE_FG_SPECIFIED; \
462 } \
463 *dst++ = subenc; \
464 prev_bg = pal->bg; \
465 prev_bg_set = 1; \
466 \
467 /* Write subencoding-dependent heading data */ \
468 if (subenc & RFB_HEXTILE_BG_SPECIFIED) { \
469 BUF_PUT_PIXEL##bpp(dst, bg_color); \
470 dst += sizeof(CARD##bpp); \
471 } \
472 if (subenc & RFB_HEXTILE_FG_SPECIFIED) { \
473 color = (CARD##bpp)pal->fg; \
474 BUF_PUT_PIXEL##bpp(dst, color); \
475 dst += sizeof(CARD##bpp); \
476 } \
477 if (subenc & RFB_HEXTILE_ANY_SUBRECTS) { \
478 dst_num_subrects = dst; \
479 *dst++ = 0; \
480 } \
481 \
482 /* Sort out the simplest case, solid-color tile */ \
483 if (pal->num_colors == 1) \
484 return (dst - dst_buf); \
485 \
486 /* Limit data size in dst_buf */ \
487 dst_limit = dst_buf + r->w * r->h * sizeof(CARD##bpp) + 1; \
488 \
489 /* Find and encode sub-rectangles */ \
490 \
491 for (y = 0; y < r->h; y++) { \
492 for (x = 0; x < r->w; x++) { \
493 /* Skip background-colored pixels */ \
494 if (tile_buf[y * r->w + x] == bg_color) { \
495 continue; \
496 } \
497 /* Determine dimensions of the best subrect */ \
498 color = tile_buf[y * r->w + x]; \
499 best_w = 1; \
500 best_h = 1; \
501 max_x = r->w; \
502 for (sy = y; sy < r->h; sy++) { \
503 for (sx = x; sx < max_x; sx++) { \
504 if (tile_buf[sy * r->w + sx] != color) \
505 break; \
506 } \
507 max_x = sx; \
508 if (max_x == x) \
509 break; \
510 if ((sx - x) * (sy - y + 1) > best_w * best_h) { \
511 best_w = (sx - x); \
512 best_h = (sy - y + 1); \
513 } \
514 } \
515 /* Encode subrect of size (best_w * best_h) */ \
516 if (subenc & RFB_HEXTILE_SUBRECTS_COLOURED) { \
517 if (dst + sizeof(CARD##bpp) + 2 >= dst_limit) \
518 return -1; \
519 \
520 BUF_PUT_PIXEL##bpp(dst, color); \
521 dst += sizeof(CARD##bpp); \
522 } else { \
523 if (dst + 2 >= dst_limit) \
524 return -1; \
525 } \
526 *dst++ = (CARD8)((x << 4) | (y & 0x0F)); \
527 *dst++ = (CARD8)(((best_w - 1) << 4) | ((best_h - 1) & 0x0F)); \
528 (*dst_num_subrects)++; \
529 \
530 /* Fill in processed subrect with background color */ \
531 for (sy = y + 1; sy < y + best_h; sy++) { \
532 for (sx = x; sx < x + best_w; sx++) \
533 tile_buf[sy * r->w + sx] = bg_color; \
534 } \
535 /* Skip to the next pixel of different color */ \
536 x += (best_w - 1); \
537 } \
538 } \
539 \
540 return (dst - dst_buf); \
541 }
542
543 DEFINE_ENCODE_TILE_HT(8)
544 DEFINE_ENCODE_TILE_HT(16)
545 DEFINE_ENCODE_TILE_HT(32)
546
547 /*
548 * Encoding a tile using raw sub-encoding in hextile.
549 */
550
551 #define DEFINE_ENCODE_TILE_RAW(bpp) \
552 \
553 static int encode_tile_raw##bpp(CARD8 *dst_buf, CL_SLOT *cl, FB_RECT *r) \
554 { \
555 CARD##bpp raw_data[256]; \
556 \
557 (*cl->trans_func)(raw_data, r, cl->trans_table); \
558 \
559 *dst_buf++ = RFB_HEXTILE_RAW; \
560 memcpy(dst_buf, raw_data, r->w * r->h * sizeof(CARD##bpp)); \
561 prev_bg_set = 0; \
562 \
563 return (1 + r->w * r->h * sizeof(CARD##bpp)); \
564 }
565
566 DEFINE_ENCODE_TILE_RAW(8)
567 DEFINE_ENCODE_TILE_RAW(16)
568 DEFINE_ENCODE_TILE_RAW(32)
569
570 /*
571 * Determine number of colors in a tile, choose background and
572 * foreground colors. Note that this function is used not only by
573 * Hextile encoder, therefore it's not declared as static.
574 */
575
576 #define DEFINE_ANALYZE_RECT(bpp) \
577 \
578 static void analyze_rect##bpp(CARD##bpp *buf, PALETTE2 *pal, FB_RECT *r) \
579 { \
580 CARD##bpp c0, c1; \
581 int i, n0, n1; \
582 int num_pixels = r->w * r->h; \
583 \
584 c0 = buf[0]; \
585 for (i = 1; i < num_pixels && buf[i] == c0; i++); \
586 if (i == num_pixels) { \
587 pal->bg = (CARD32)c0; \
588 pal->num_colors = 1; /* Solid-color rectangle */ \
589 return; \
590 } \
591 \
592 n0 = i; \
593 c1 = buf[i]; \
594 n1 = 0; \
595 for (i++; i < num_pixels; i++) { \
596 if (buf[i] == c0) { \
597 n0++; \
598 } else if (buf[i] == c1) { \
599 n1++; \
600 } else \
601 break; \
602 } \
603 if (i == num_pixels) { \
604 /* Background color is one that occupies more pixels */ \
605 if (n0 > n1) { \
606 pal->bg = (CARD32)c0; pal->fg = (CARD32)c1; \
607 } else { \
608 pal->bg = (CARD32)c1; pal->fg = (CARD32)c0; \
609 } \
610 pal->num_colors = 2; /* Two colors */ \
611 } else { \
612 pal->num_colors = 0; /* More than two colors */ \
613 } \
614 }
615
616 DEFINE_ANALYZE_RECT(8)
617 DEFINE_ANALYZE_RECT(16)
618 DEFINE_ANALYZE_RECT(32)
619
620