[gtk-vnc-devel] [PATCH] ZRLE Encoding support

[Anthony Liguori <anthony codemonkey ws>]

Hi,

Attached is a patch for gtk-vnc to enable the ZRLE encoding.  ZRLE is a 
compressed encoding that's documented in the RFB specification.  While 
not as popular as Tight, since it's the "official" compressed encoding 
for RFB I thought it was a good place to start.

This adds a dependency on zlib.  I don't think that's a big deal 
though.  I'd appreciate if someone could look over my configure.ac 
change to make sure that's the reasonable thing to do.

I'd like to commit this before the next release (which I'll do before 
Monday) so please give it a try and let me know if it works for you.

Regards,

Anthony Liguori

diff -r be60cc1bd95f configure.ac
--- a/configure.ac	Wed Dec 26 09:09:48 2007 -0600
+++ b/configure.ac	Thu Dec 27 21:09:36 2007 -0600
@@ -89,6 +89,8 @@ AC_SUBST(GNUTLS_LIBS)
 
 GTHREAD_CFLAGS=
 GTHREAD_LIBS=
+
+AC_CHECK_LIB(z, inflate, [], [AC_MSG_ERROR([zlib not found])])
 
 WITH_UCONTEXT=1
 
diff -r be60cc1bd95f src/blt.h
--- a/src/blt.h	Wed Dec 26 09:09:48 2007 -0600
+++ b/src/blt.h	Thu Dec 27 21:09:36 2007 -0600
@@ -4,6 +4,8 @@
 #define src_pixel_t SPLICE(SPLICE(uint, SRC), _t)
 #define dst_pixel_t SPLICE(SPLICE(uint, DST), _t)
 #define SUFFIX() SPLICE(SRC,SPLICE(x,DST))
+#define SET_PIXEL SPLICE(gvnc_set_pixel_, SUFFIX())
+#define SET_PIXEL_AT SPLICE(gvnc_set_pixel_at_, SUFFIX())
 #define BLIT SPLICE(gvnc_blt_, SUFFIX())
 #define FILL SPLICE(gvnc_fill_, SUFFIX())
 #define FAST_FILL SPLICE(gvnc_fill_fast_, SUFFIX())
@@ -32,6 +34,20 @@ static void FAST_FILL(struct gvnc *gvnc,
 	}
 }
 
+static void SET_PIXEL(struct gvnc *gvnc, dst_pixel_t *dp, src_pixel_t *sp)
+{
+	*dp = ((*sp >> gvnc->rrs) & gvnc->rm) << gvnc->rls
+		| ((*sp >> gvnc->grs) & gvnc->gm) << gvnc->gls
+		| ((*sp >> gvnc->brs) & gvnc->bm) << gvnc->bls;
+}
+
+static void SET_PIXEL_AT(struct gvnc *gvnc, int x, int y, src_pixel_t *sp)
+{
+	dst_pixel_t *dp = (dst_pixel_t *)gvnc_get_local(gvnc, x, y);
+
+	SET_PIXEL(gvnc, dp, sp);
+}
+
 static void FILL(struct gvnc *gvnc, src_pixel_t *sp,
 		 int x, int y, int width, int height)
 {
@@ -43,9 +59,7 @@ static void FILL(struct gvnc *gvnc, src_
 		int j;
 
 		for (j = 0; j < width; j++) {
-			*dp = ((*sp >> gvnc->rrs) & gvnc->rm) << gvnc->rls
-			    | ((*sp >> gvnc->grs) & gvnc->gm) << gvnc->gls
-			    | ((*sp >> gvnc->brs) & gvnc->bm) << gvnc->bls;
+			SET_PIXEL(gvnc, dp, sp);
 			dp++;
 		}
 		dst += gvnc->local.linesize;
@@ -67,9 +81,7 @@ static void BLIT(struct gvnc *gvnc, uint
 		int j;
 
 		for (j = 0; j < w; j++) {
-			*dp = ((*sp >> gvnc->rrs) & gvnc->rm) << gvnc->rls
-			    | ((*sp >> gvnc->grs) & gvnc->gm) << gvnc->gls
-			    | ((*sp >> gvnc->brs) & gvnc->bm) << gvnc->bls;
+			SET_PIXEL(gvnc, dp, sp);
 			dp++;
 			sp++;
 		}
diff -r be60cc1bd95f src/gvnc.c
--- a/src/gvnc.c	Wed Dec 26 09:09:48 2007 -0600
+++ b/src/gvnc.c	Thu Dec 27 21:09:36 2007 -0600
@@ -35,6 +35,8 @@
 #include <gnutls/gnutls.h>
 #include <gnutls/x509.h>
 
+#include <zlib.h>
+
 struct wait_queue
 {
 	gboolean waiting;
@@ -45,6 +47,8 @@ typedef void gvnc_blt_func(struct gvnc *
 typedef void gvnc_blt_func(struct gvnc *, uint8_t *, int, int, int, int, int);
 
 typedef void gvnc_fill_func(struct gvnc *, uint8_t *, int, int, int, int);
+
+typedef void gvnc_set_pixel_at_func(struct gvnc *, int, int, uint8_t *);
 
 typedef void gvnc_hextile_func(struct gvnc *gvnc, uint8_t flags,
 			       uint16_t x, uint16_t y,
@@ -112,6 +116,7 @@ struct gvnc
 
 	gvnc_blt_func *blt;
 	gvnc_fill_func *fill;
+	gvnc_set_pixel_at_func *set_pixel_at;
 	gvnc_hextile_func *hextile;
 
 	struct gvnc_ops ops;
@@ -125,6 +130,17 @@ struct gvnc
 	char *xmit_buffer;
 	int xmit_buffer_capacity;
 	int xmit_buffer_size;
+
+	z_stream strm;
+
+	size_t uncompressed_length;
+	uint8_t uncompressed_buffer[4096];
+
+	size_t compressed_length;
+	uint8_t *compressed_buffer;
+
+	uint8_t zrle_pi;
+	int zrle_pi_bits;
 };
 
 #define nibhi(a) (((a) >> 4) & 0x0F)
@@ -245,7 +261,55 @@ static gboolean g_condition_wait(g_condi
 	return TRUE;
 }
 
-
+static gboolean gvnc_use_compression(struct gvnc *gvnc)
+{
+	return gvnc->compressed_buffer != NULL;
+}
+
+static int gvnc_zread(struct gvnc *gvnc, void *buffer, size_t size)
+{
+	size_t offset = 0;
+
+	while (offset < size) {
+		/* if data is available in the uncompressed buffer, then
+		 * copy */
+		if (gvnc->uncompressed_length) {
+			size_t len = MIN(gvnc->uncompressed_length,
+					 size - offset);
+
+			memcpy(buffer + offset,
+			       gvnc->uncompressed_buffer,
+			       len);
+
+			gvnc->uncompressed_length -= len;
+			if (gvnc->uncompressed_length)
+				memmove(gvnc->uncompressed_buffer,
+					gvnc->uncompressed_buffer + len,
+					gvnc->uncompressed_length);
+			offset += len;
+		} else {
+			int err;
+
+			gvnc->strm.next_in = gvnc->compressed_buffer;
+			gvnc->strm.avail_in = gvnc->compressed_length;
+			gvnc->strm.next_out = gvnc->uncompressed_buffer;
+			gvnc->strm.avail_out = sizeof(gvnc->uncompressed_buffer);
+
+			/* inflate as much as possible */
+			err = inflate(&gvnc->strm, Z_SYNC_FLUSH);
+			if (err != Z_OK) {
+				errno = EIO;
+				return -1;
+			}
+
+			gvnc->uncompressed_length = (uint8_t *)gvnc->strm.next_out - gvnc->uncompressed_buffer;
+			gvnc->compressed_length -= (uint8_t *)gvnc->strm.next_in - gvnc->compressed_buffer;
+			gvnc->compressed_buffer = gvnc->strm.next_in;
+		}
+	}
+
+	return offset;
+}
 
 /* IO functions */
 
@@ -260,7 +324,17 @@ static int gvnc_read(struct gvnc *gvnc, 
 	while (offset < len) {
 		size_t tmp;
 
-		if (gvnc->read_offset == gvnc->read_size) {
+		/* compressed data is buffered independently of the read buffer
+		 * so we must by-pass it */
+		if (gvnc_use_compression(gvnc)) {
+			int ret = gvnc_zread(gvnc, data + offset, len);
+			if (ret == -1) {
+				gvnc->has_error = TRUE;
+				return -errno;
+			}
+			offset += ret;
+			continue;
+		} else if (gvnc->read_offset == gvnc->read_size) {
 			int ret;
 
 			if (gvnc->tls_session) {
@@ -410,7 +484,15 @@ static ssize_t gvnc_tls_pull(gnutls_tran
 	return ret;
 }
 
-
+static size_t gvnc_pixel_size(struct gvnc *gvnc)
+{
+	return gvnc->fmt.bits_per_pixel / 8;
+}
+
+static void gvnc_read_pixel(struct gvnc *gvnc, uint8_t *pixel)
+{
+	gvnc_read(gvnc, pixel, gvnc_pixel_size(gvnc));
+}
 
 static uint8_t gvnc_read_u8(struct gvnc *gvnc)
 {
@@ -856,6 +938,18 @@ static gvnc_hextile_func *gvnc_hextile_t
 	  (gvnc_hextile_func *)gvnc_hextile_32x32 },
 };
 
+static gvnc_set_pixel_at_func *gvnc_set_pixel_at_table[3][3] = {
+	{ (gvnc_set_pixel_at_func *)gvnc_set_pixel_at_8x8,
+	  (gvnc_set_pixel_at_func *)gvnc_set_pixel_at_8x16,
+	  (gvnc_set_pixel_at_func *)gvnc_set_pixel_at_8x32 },
+	{ (gvnc_set_pixel_at_func *)gvnc_set_pixel_at_16x8,
+	  (gvnc_set_pixel_at_func *)gvnc_set_pixel_at_16x16,
+	  (gvnc_set_pixel_at_func *)gvnc_set_pixel_at_16x32 },
+	{ (gvnc_set_pixel_at_func *)gvnc_set_pixel_at_32x8,
+	  (gvnc_set_pixel_at_func *)gvnc_set_pixel_at_32x16,
+	  (gvnc_set_pixel_at_func *)gvnc_set_pixel_at_32x32 },
+};
+
 static gvnc_fill_func *gvnc_fill_table[3][3] = {
 	{ (gvnc_fill_func *)gvnc_fill_8x8,
 	  (gvnc_fill_func *)gvnc_fill_8x16,
@@ -970,6 +1064,17 @@ static void gvnc_hextile_update(struct g
 	}
 }
 
+static void gvnc_fill(struct gvnc *gvnc, uint8_t *color,
+		      uint16_t x, uint16_t y, uint16_t width, uint16_t height)
+{
+	gvnc->fill(gvnc, color, x, y, width, height);
+}
+
+static void gvnc_set_pixel_at(struct gvnc *gvnc, int x, int y, uint8_t *pixel)
+{
+	gvnc->set_pixel_at(gvnc, x, y, pixel);
+}
+
 static void gvnc_rre_update(struct gvnc *gvnc,
 			    uint16_t x, uint16_t y,
 			    uint16_t width, uint16_t height)
@@ -979,22 +1084,242 @@ static void gvnc_rre_update(struct gvnc 
 	uint32_t i;
 
 	num = gvnc_read_u32(gvnc);
-	gvnc_read(gvnc, bg, gvnc->fmt.bits_per_pixel / 8);
-	gvnc->fill(gvnc, bg, x, y, width, height);
+	gvnc_read_pixel(gvnc, bg);
+	gvnc_fill(gvnc, bg, x, y, width, height);
 
 	for (i = 0; i < num; i++) {
 		uint8_t fg[4];
 		uint16_t sub_x, sub_y, sub_w, sub_h;
 
-		gvnc_read(gvnc, fg, gvnc->fmt.bits_per_pixel / 8);
+		gvnc_read_pixel(gvnc, fg);
 		sub_x = gvnc_read_u16(gvnc);
 		sub_y = gvnc_read_u16(gvnc);
 		sub_w = gvnc_read_u16(gvnc);
 		sub_h = gvnc_read_u16(gvnc);
 
-		gvnc->fill(gvnc, fg,
-			   x + sub_x, y + sub_y, sub_w, sub_h);
-	}
+		gvnc_fill(gvnc, fg,
+			  x + sub_x, y + sub_y, sub_w, sub_h);
+	}
+}
+
+/* CPIXELs are optimized slightly.  32-bit pixel values are packed into 24-bit
+ * values. */
+static void gvnc_read_cpixel(struct gvnc *gvnc, uint8_t *pixel)
+{
+	int bpp = gvnc_pixel_size(gvnc);
+
+	memset(pixel, 0, bpp);
+
+	if (bpp == 4 && gvnc->fmt.true_color_flag && gvnc->fmt.depth == 24) {
+		bpp = 3;
+#if __BYTE_ORDER == __BIG_ENDIAN
+		pixel += 1;
+#endif
+	}
+
+	gvnc_read(gvnc, pixel, bpp);
+}
+
+static void gvnc_zrle_update_tile_blit(struct gvnc *gvnc,
+				       uint16_t x, uint16_t y,
+				       uint16_t width, uint16_t height)
+{
+	uint8_t blit_data[4 * 64 * 64];
+	int i, bpp;
+
+	bpp = gvnc_pixel_size(gvnc);
+
+	for (i = 0; i < width * height; i++)
+		gvnc_read_cpixel(gvnc, blit_data + (i * bpp));
+
+	gvnc_blt(gvnc, blit_data, width * bpp, x, y, width, height);
+}
+
+static uint8_t gvnc_read_zrle_pi(struct gvnc *gvnc, int palette_size)
+{
+	uint8_t pi = 0;
+
+	if (gvnc->zrle_pi_bits == 0) {
+		gvnc->zrle_pi = gvnc_read_u8(gvnc);
+		gvnc->zrle_pi_bits = 8;
+	}
+
+	switch (palette_size) {
+	case 2:
+		pi = (gvnc->zrle_pi >> (gvnc->zrle_pi_bits - 1)) & 1;
+		gvnc->zrle_pi_bits -= 1;
+		break;
+	case 3 ... 4:
+		pi = (gvnc->zrle_pi >> (gvnc->zrle_pi_bits - 2)) & 3;
+		gvnc->zrle_pi_bits -= 2;
+		break;
+	case 5 ... 16:
+		pi = (gvnc->zrle_pi >> (gvnc->zrle_pi_bits - 4)) & 15;
+		gvnc->zrle_pi_bits -= 4;
+		break;
+	}
+
+	return pi;
+}
+
+static void gvnc_zrle_update_tile_palette(struct gvnc *gvnc,
+					  uint8_t palette_size,
+					  uint16_t x, uint16_t y,
+					  uint16_t width, uint16_t height)
+{
+	uint8_t palette[128][4];
+	int i, j;
+
+	for (i = 0; i < palette_size; i++)
+		gvnc_read_cpixel(gvnc, palette[i]);
+
+	for (j = 0; j < height; j++) {
+		/* discard any padding bits */
+		gvnc->zrle_pi_bits = 0;
+
+		for (i = 0; i < width; i++) {
+			int ind = gvnc_read_zrle_pi(gvnc, palette_size);
+
+			gvnc_set_pixel_at(gvnc, x + i, y + j,
+					  palette[ind & 0x7F]);
+		}
+	}
+}
+
+static int gvnc_read_zrle_rl(struct gvnc *gvnc)
+{
+	int rl = 1;
+	uint8_t byte;
+
+	do {
+		byte = gvnc_read_u8(gvnc);
+		rl += byte;
+	} while (!gvnc_has_error(gvnc) && byte == 255);
+
+	return rl;
+}
+
+static void gvnc_zrle_update_tile_rle(struct gvnc *gvnc,
+				      uint16_t x, uint16_t y,
+				      uint16_t width, uint16_t height)
+{
+	int i, j, rl = 0;
+	uint8_t pixel[4];
+
+	for (j = 0; j < height; j++) {
+		for (i = 0; i < width; i++) {
+			if (rl == 0) {
+				gvnc_read_cpixel(gvnc, pixel);
+				rl = gvnc_read_zrle_rl(gvnc);
+			}
+			gvnc_set_pixel_at(gvnc, x + i, y + j, pixel);
+			rl -= 1;
+		}
+	}
+}
+
+static void gvnc_zrle_update_tile_prle(struct gvnc *gvnc,
+				       uint8_t palette_size,
+				       uint16_t x, uint16_t y,
+				       uint16_t width, uint16_t height)
+{
+	int i, j, rl = 0;
+	uint8_t palette[128][4];
+	uint8_t pi = 0;
+
+	for (i = 0; i < palette_size; i++)
+		gvnc_read_cpixel(gvnc, palette[i]);
+
+	for (j = 0; j < height; j++) {
+		for (i = 0; i < width; i++) {
+			if (rl == 0) {
+				pi = gvnc_read_u8(gvnc);
+				if (pi & 0x80) {
+					rl = gvnc_read_zrle_rl(gvnc);
+					pi &= 0x7F;
+				} else
+					rl = 1;
+			}
+
+			gvnc_set_pixel_at(gvnc, x + i, y + j, palette[pi]);
+			rl -= 1;
+		}
+	}
+}
+
+static void gvnc_zrle_update_tile(struct gvnc *gvnc, uint16_t x, uint16_t y,
+				  uint16_t width, uint16_t height)
+{
+	uint8_t subencoding = gvnc_read_u8(gvnc);
+	uint8_t pixel[4];
+
+	switch (subencoding) {
+	case 0: /* Raw pixel data */
+		gvnc_zrle_update_tile_blit(gvnc, x, y, width, height);
+		break;
+	case 1: /* Solid tile of a single color */
+		gvnc_read_cpixel(gvnc, pixel);
+		gvnc_fill(gvnc, pixel, x, y, width, height);
+		break;
+	case 2 ... 16: /* Packed palette types */
+		gvnc_zrle_update_tile_palette(gvnc, subencoding,
+					      x, y, width, height);
+		break;
+	case 128: /* Plain RLE */
+		gvnc_zrle_update_tile_rle(gvnc, x, y, width, height);
+		break;
+	case 130 ... 255: /* Palette RLE */
+		gvnc_zrle_update_tile_prle(gvnc, subencoding - 128,
+					   x, y, width, height);
+		break;
+	case 129:
+	case 17 ... 127:
+	default:
+		/* FIXME raise error? */
+		break;
+	}
+}
+
+static void gvnc_zrle_update(struct gvnc *gvnc,
+			     uint16_t x, uint16_t y,
+			     uint16_t width, uint16_t height)
+
+{
+	uint32_t length;
+	uint32_t offset;
+	uint16_t i, j;
+	uint8_t *zlib_data;
+
+	length = gvnc_read_u32(gvnc);
+	zlib_data = malloc(length);
+	if (zlib_data == NULL) {
+		gvnc->has_error = TRUE;
+		return;
+	}
+
+	gvnc_read(gvnc, zlib_data, length);
+
+	/* setup subsequent calls to gvnc_read*() to use the compressed data */
+	gvnc->uncompressed_length = 0;
+	gvnc->compressed_length = length;
+	gvnc->compressed_buffer = zlib_data;
+
+	offset = 0;
+	for (j = 0; j < height; j += 64) {
+		for (i = 0; i < width; i += 64) {
+			uint16_t w, h;
+
+			w = MIN(width - i, 64);
+			h = MIN(height - j, 64);
+			gvnc_zrle_update_tile(gvnc, x + i, y + j, w, h);
+		}
+	}
+
+	gvnc->uncompressed_length = 0;
+	gvnc->compressed_length = 0;
+	gvnc->compressed_buffer = NULL;
+
+	free(zlib_data);
 }
 
 static void gvnc_update(struct gvnc *gvnc, int x, int y, int width, int height)
@@ -1202,6 +1527,9 @@ static void gvnc_framebuffer_update(stru
 		break;
 	case GVNC_ENCODING_HEXTILE:
 		gvnc_hextile_update(gvnc, x, y, width, height);
+		break;
+	case GVNC_ENCODING_ZRLE:
+		gvnc_zrle_update(gvnc, x, y, width, height);
 		break;
 	case GVNC_ENCODING_DESKTOP_RESIZE:
 		gvnc_resize(gvnc, width, height);
@@ -1923,6 +2251,8 @@ void gvnc_close(struct gvnc *gvnc)
 		gvnc->cred_x509_key = NULL;
 	}
 
+	inflateEnd(&gvnc->strm);
+
 	gvnc->auth_type = GVNC_AUTH_INVALID;
 	gvnc->auth_subtype = GVNC_AUTH_INVALID;
 
@@ -1959,7 +2289,6 @@ gboolean gvnc_is_initialized(struct gvnc
 		return TRUE;
 	return FALSE;
 }
-
 
 gboolean gvnc_initialize(struct gvnc *gvnc, gboolean shared_flag)
 {
@@ -2014,6 +2343,10 @@ gboolean gvnc_initialize(struct gvnc *gv
 	gvnc_read(gvnc, gvnc->name, n_name);
 	gvnc->name[n_name] = 0;
 	GVNC_DEBUG("Display name '%s'\n", gvnc->name);
+
+	memset(&gvnc->strm, 0, sizeof(gvnc->strm));
+	/* FIXME what level? */
+	inflateInit(&gvnc->strm);
 
 	gvnc_resize(gvnc, gvnc->width, gvnc->height);
 	return !gvnc_has_error(gvnc);
@@ -2309,6 +2642,7 @@ gboolean gvnc_set_local(struct gvnc *gvn
 
 	gvnc->blt = gvnc_blt_table[i - 1][j - 1];
 	gvnc->fill = gvnc_fill_table[i - 1][j - 1];
+	gvnc->set_pixel_at = gvnc_set_pixel_at_table[i - 1][j - 1];
 	gvnc->hextile = gvnc_hextile_table[i - 1][j - 1];
 
 	if (gvnc->perfect_match)
diff -r be60cc1bd95f src/vncdisplay.c
--- a/src/vncdisplay.c	Wed Dec 26 09:09:48 2007 -0600
+++ b/src/vncdisplay.c	Thu Dec 27 21:09:36 2007 -0600
@@ -678,6 +678,7 @@ static void *vnc_coroutine(void *opaque)
 				GVNC_ENCODING_RICH_CURSOR,
 				GVNC_ENCODING_XCURSOR,
 				GVNC_ENCODING_POINTER_CHANGE,
+				GVNC_ENCODING_ZRLE,
 				GVNC_ENCODING_HEXTILE,
 				GVNC_ENCODING_RRE,
 				GVNC_ENCODING_COPY_RECT,