From patchwork Wed Jul 7 18:57:58 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Corentin Chary X-Patchwork-Id: 58146 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.gnu.org (lists.gnu.org [199.232.76.165]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id 7F132B6ED0 for ; Thu, 8 Jul 2010 05:11:55 +1000 (EST) Received: from localhost ([127.0.0.1]:49489 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OWZy4-00068h-19 for incoming@patchwork.ozlabs.org; Wed, 07 Jul 2010 15:07:36 -0400 Received: from [140.186.70.92] (port=35012 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OWZoj-00087m-6o for qemu-devel@nongnu.org; Wed, 07 Jul 2010 14:58:04 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1OWZoc-0002gv-Mg for qemu-devel@nongnu.org; Wed, 07 Jul 2010 14:57:57 -0400 Received: from iksaif.net ([88.191.73.63]:35193) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1OWZoc-0002fI-4N for qemu-devel@nongnu.org; Wed, 07 Jul 2010 14:57:50 -0400 Received: from falgoret.iksaif.net (localhost [127.0.0.1]) (Authenticated sender: corentincj@iksaif.net) by iksaif.net (Postfix) with ESMTPA id 96784C90086; Wed, 7 Jul 2010 20:58:14 +0200 (CEST) From: Corentin Chary To: qemu-devel@nongnu.org Date: Wed, 7 Jul 2010 20:57:58 +0200 Message-Id: <1278529086-10391-11-git-send-email-corentincj@iksaif.net> X-Mailer: git-send-email 1.7.1 In-Reply-To: <1278529086-10391-1-git-send-email-corentincj@iksaif.net> References: <1278529086-10391-1-git-send-email-corentincj@iksaif.net> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) Cc: Corentin Chary , Anthony Liguori , Alexander Graf Subject: [Qemu-devel] [PATCH v2 10/18] vnc: tight: stop using qdict for palette stuff X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: qemu-devel.nongnu.org List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Profiling with callgrind seems to show that a lot of time is spent in the palette code (mostly due to memory allocation and qdict to int conversion). This patch adds a VncPalette implementation. The palette is stored in a hash table, like qdict, but which does way less memory allocations, and doesn't suffer from the QObject overhead. Signed-off-by: Corentin Chary --- Makefile.objs | 2 +- ui/vnc-enc-tight.c | 163 +++++++++++---------------------------------------- ui/vnc-palette.c | 136 +++++++++++++++++++++++++++++++++++++++++++ ui/vnc-palette.h | 63 ++++++++++++++++++++ 4 files changed, 235 insertions(+), 129 deletions(-) create mode 100644 ui/vnc-palette.c create mode 100644 ui/vnc-palette.h diff --git a/Makefile.objs b/Makefile.objs index a0b8200..bb9806c 100644 --- a/Makefile.objs +++ b/Makefile.objs @@ -107,7 +107,7 @@ ui-obj-$(CONFIG_SDL) += sdl.o sdl_zoom.o x_keymap.o ui-obj-$(CONFIG_CURSES) += curses.o ui-obj-y += vnc.o d3des.o ui-obj-y += vnc-enc-zlib.o vnc-enc-hextile.o -ui-obj-y += vnc-enc-tight.o +ui-obj-y += vnc-enc-tight.o vnc-palette.o ui-obj-$(CONFIG_VNC_TLS) += vnc-tls.o vnc-auth-vencrypt.o ui-obj-$(CONFIG_VNC_SASL) += vnc-auth-sasl.o ui-obj-$(CONFIG_COCOA) += cocoa.o diff --git a/ui/vnc-enc-tight.c b/ui/vnc-enc-tight.c index e627e00..49a456d 100644 --- a/ui/vnc-enc-tight.c +++ b/ui/vnc-enc-tight.c @@ -39,10 +39,10 @@ #include "qemu-common.h" #include "bswap.h" -#include "qdict.h" #include "qint.h" #include "vnc.h" #include "vnc-enc-tight.h" +#include "vnc-palette.h" /* Compression level stuff. The following array contains various encoder parameters for each of 10 compression levels (0..9). @@ -89,7 +89,7 @@ static const struct { }; static int send_png_rect(VncState *vs, int x, int y, int w, int h, - QDict *palette); + VncPalette *palette); static bool tight_can_send_png_rect(VncState *vs, int w, int h) { @@ -313,74 +313,13 @@ tight_detect_smooth_image(VncState *vs, int w, int h) /* * Code to determine how many different colors used in rectangle. */ - -static void tight_palette_rgb2buf(uint32_t rgb, int bpp, uint8_t buf[6]) -{ - memset(buf, 0, 6); - - if (bpp == 32) { - buf[0] = ((rgb >> 24) & 0xFF); - buf[1] = ((rgb >> 16) & 0xFF); - buf[2] = ((rgb >> 8) & 0xFF); - buf[3] = ((rgb >> 0) & 0xFF); - buf[4] = ((buf[0] & 1) == 0) << 3 | ((buf[1] & 1) == 0) << 2; - buf[4]|= ((buf[2] & 1) == 0) << 1 | ((buf[3] & 1) == 0) << 0; - buf[0] |= 1; - buf[1] |= 1; - buf[2] |= 1; - buf[3] |= 1; - } - if (bpp == 16) { - buf[0] = ((rgb >> 8) & 0xFF); - buf[1] = ((rgb >> 0) & 0xFF); - buf[2] = ((buf[0] & 1) == 0) << 1 | ((buf[1] & 1) == 0) << 0; - buf[0] |= 1; - buf[1] |= 1; - } -} - -static uint32_t tight_palette_buf2rgb(int bpp, const uint8_t *buf) -{ - uint32_t rgb = 0; - - if (bpp == 32) { - rgb |= ((buf[0] & ~1) | !((buf[4] >> 3) & 1)) << 24; - rgb |= ((buf[1] & ~1) | !((buf[4] >> 2) & 1)) << 16; - rgb |= ((buf[2] & ~1) | !((buf[4] >> 1) & 1)) << 8; - rgb |= ((buf[3] & ~1) | !((buf[4] >> 0) & 1)) << 0; - } - if (bpp == 16) { - rgb |= ((buf[0] & ~1) | !((buf[2] >> 1) & 1)) << 8; - rgb |= ((buf[1] & ~1) | !((buf[2] >> 0) & 1)) << 0; - } - return rgb; -} - - -static int tight_palette_insert(QDict *palette, uint32_t rgb, int bpp, int max) -{ - uint8_t key[6]; - int idx = qdict_size(palette); - bool present; - - tight_palette_rgb2buf(rgb, bpp, key); - present = qdict_haskey(palette, (char *)key); - if (idx >= max && !present) { - return 0; - } - if (!present) { - qdict_put(palette, (char *)key, qint_from_int(idx)); - } - return qdict_size(palette); -} - #define DEFINE_FILL_PALETTE_FUNCTION(bpp) \ \ static int \ tight_fill_palette##bpp(VncState *vs, int x, int y, \ int max, size_t count, \ uint32_t *bg, uint32_t *fg, \ - struct QDict **palette) { \ + VncPalette **palette) { \ uint##bpp##_t *data; \ uint##bpp##_t c0, c1, ci; \ int i, n0, n1; \ @@ -427,24 +366,23 @@ static int tight_palette_insert(QDict *palette, uint32_t rgb, int bpp, int max) return 0; \ } \ \ - *palette = qdict_new(); \ - tight_palette_insert(*palette, c0, bpp, max); \ - tight_palette_insert(*palette, c1, bpp, max); \ - tight_palette_insert(*palette, ci, bpp, max); \ + *palette = palette_new(max, bpp); \ + palette_put(*palette, c0); \ + palette_put(*palette, c1); \ + palette_put(*palette, ci); \ \ for (i++; i < count; i++) { \ if (data[i] == ci) { \ continue; \ } else { \ ci = data[i]; \ - if (!tight_palette_insert(*palette, (uint32_t)ci, \ - bpp, max)) { \ + if (!palette_put(*palette, (uint32_t)ci)) { \ return 0; \ } \ } \ } \ \ - return qdict_size(*palette); \ + return palette_size(*palette); \ } DEFINE_FILL_PALETTE_FUNCTION(8) @@ -453,7 +391,7 @@ DEFINE_FILL_PALETTE_FUNCTION(32) static int tight_fill_palette(VncState *vs, int x, int y, size_t count, uint32_t *bg, uint32_t *fg, - struct QDict **palette) + VncPalette **palette) { int max; @@ -478,20 +416,6 @@ static int tight_fill_palette(VncState *vs, int x, int y, return 0; } -/* Callback to dump a palette with qdict_iter -static void print_palette(const char *key, QObject *obj, void *opaque) -{ - uint8_t idx = qint_get_int(qobject_to_qint(obj)); - uint32_t rgb = tight_palette_buf2rgb(32, (uint8_t *)key); - - fprintf(stderr, "%.2x ", (unsigned char)*key); - while (*key++) - fprintf(stderr, "%.2x ", (unsigned char)*key); - - fprintf(stderr, ": idx: %x rgb: %x\n", idx, rgb); -} -*/ - /* * Converting truecolor samples into palette indices. */ @@ -499,10 +423,9 @@ static void print_palette(const char *key, QObject *obj, void *opaque) \ static void \ tight_encode_indexed_rect##bpp(uint8_t *buf, int count, \ - struct QDict *palette) { \ + VncPalette *palette) { \ uint##bpp##_t *src; \ uint##bpp##_t rgb; \ - uint8_t key[6]; \ int i, rep; \ uint8_t idx; \ \ @@ -515,15 +438,13 @@ static void print_palette(const char *key, QObject *obj, void *opaque) while (i < count && *src == rgb) { \ rep++, src++, i++; \ } \ - tight_palette_rgb2buf(rgb, bpp, key); \ - if (!qdict_haskey(palette, (char *)key)) { \ - /* \ - * Should never happen, but don't break everything \ - * if it does, use the first color instead \ - */ \ + idx = palette_idx(palette, rgb); \ + /* \ + * Should never happen, but don't break everything \ + * if it does, use the first color instead \ + */ \ + if (idx == -1) { \ idx = 0; \ - } else { \ - idx = qdict_get_int(palette, (char *)key); \ } \ while (rep >= 0) { \ *buf++ = idx; \ @@ -1035,13 +956,13 @@ static int send_mono_rect(VncState *vs, int x, int y, #ifdef CONFIG_VNC_PNG if (tight_can_send_png_rect(vs, w, h)) { int ret; - QDict *palette = qdict_new(); int bpp = vs->clientds.pf.bytes_per_pixel * 8; + VncPalette *palette = palette_new(2, bpp); - tight_palette_insert(palette, bg, bpp, 2); - tight_palette_insert(palette, fg, bpp, 2); + palette_put(palette, bg); + palette_put(palette, fg); ret = send_png_rect(vs, x, y, w, h, palette); - QDECREF(palette); + palette_destroy(palette); return ret; } #endif @@ -1091,20 +1012,15 @@ struct palette_cb_priv { #endif }; -static void write_palette(const char *key, QObject *obj, void *opaque) +static void write_palette(int idx, uint32_t color, void *opaque) { struct palette_cb_priv *priv = opaque; VncState *vs = priv->vs; uint32_t bytes = vs->clientds.pf.bytes_per_pixel; - uint8_t idx = qint_get_int(qobject_to_qint(obj)); if (bytes == 4) { - uint32_t color = tight_palette_buf2rgb(32, (uint8_t *)key); - ((uint32_t*)priv->header)[idx] = color; } else { - uint16_t color = tight_palette_buf2rgb(16, (uint8_t *)key); - ((uint16_t*)priv->header)[idx] = color; } } @@ -1145,7 +1061,7 @@ static bool send_gradient_rect(VncState *vs, int x, int y, int w, int h) } static int send_palette_rect(VncState *vs, int x, int y, - int w, int h, struct QDict *palette) + int w, int h, VncPalette *palette) { int stream = 2; int level = tight_conf[vs->tight_compression].idx_zlib_level; @@ -1158,7 +1074,7 @@ static int send_palette_rect(VncState *vs, int x, int y, } #endif - colors = qdict_size(palette); + colors = palette_size(palette); vnc_write_u8(vs, (stream | VNC_TIGHT_EXPLICIT_FILTER) << 4); vnc_write_u8(vs, VNC_TIGHT_FILTER_PALETTE); @@ -1168,11 +1084,11 @@ static int send_palette_rect(VncState *vs, int x, int y, case 4: { size_t old_offset, offset; - uint32_t header[qdict_size(palette)]; + uint32_t header[palette_size(palette)]; struct palette_cb_priv priv = { vs, (uint8_t *)header }; old_offset = vs->output.offset; - qdict_iter(palette, write_palette, &priv); + palette_iter(palette, write_palette, &priv); vnc_write(vs, header, sizeof(header)); if (vs->tight_pixel24) { @@ -1185,10 +1101,10 @@ static int send_palette_rect(VncState *vs, int x, int y, } case 2: { - uint16_t header[qdict_size(palette)]; + uint16_t header[palette_size(palette)]; struct palette_cb_priv priv = { vs, (uint8_t *)header }; - qdict_iter(palette, write_palette, &priv); + palette_iter(palette, write_palette, &priv); vnc_write(vs, header, sizeof(header)); tight_encode_indexed_rect16(vs->tight.buffer, w * h, palette); break; @@ -1370,20 +1286,11 @@ static int send_jpeg_rect(VncState *vs, int x, int y, int w, int h, int quality) * PNG compression stuff. */ #ifdef CONFIG_VNC_PNG -static void write_png_palette(const char *key, QObject *obj, void *opaque) +static void write_png_palette(int idx, uint32_t pix, void *opaque) { struct palette_cb_priv *priv = opaque; VncState *vs = priv->vs; - uint32_t bytes = vs->clientds.pf.bytes_per_pixel; - uint8_t idx = qint_get_int(qobject_to_qint(obj)); png_colorp color = &priv->png_palette[idx]; - uint32_t pix; - - if (bytes == 4) { - pix = tight_palette_buf2rgb(32, (uint8_t *)key); - } else { - pix = tight_palette_buf2rgb(16, (uint8_t *)key); - } if (vs->tight_pixel24) { @@ -1433,7 +1340,7 @@ static void vnc_png_free(png_structp png_ptr, png_voidp ptr) } static int send_png_rect(VncState *vs, int x, int y, int w, int h, - QDict *palette) + VncPalette *palette) { png_byte color_type; png_structp png_ptr; @@ -1476,13 +1383,13 @@ static int send_png_rect(VncState *vs, int x, int y, int w, int h, struct palette_cb_priv priv; png_palette = png_malloc(png_ptr, sizeof(*png_palette) * - qdict_size(palette)); + palette_size(palette)); priv.vs = vs; priv.png_palette = png_palette; - qdict_iter(palette, write_png_palette, &priv); + palette_iter(palette, write_png_palette, &priv); - png_set_PLTE(png_ptr, info_ptr, png_palette, qdict_size(palette)); + png_set_PLTE(png_ptr, info_ptr, png_palette, palette_size(palette)); offset = vs->tight.offset; if (vs->clientds.pf.bytes_per_pixel == 4) { @@ -1542,7 +1449,7 @@ static void vnc_tight_stop(VncState *vs) static int send_sub_rect(VncState *vs, int x, int y, int w, int h) { - struct QDict *palette = NULL; + VncPalette *palette = NULL; uint32_t bg = 0, fg = 0; int colors; int ret = 0; @@ -1589,7 +1496,7 @@ static int send_sub_rect(VncState *vs, int x, int y, int w, int h) ret = send_palette_rect(vs, x, y, w, h, palette); #endif } - QDECREF(palette); + palette_destroy(palette); return ret; } diff --git a/ui/vnc-palette.c b/ui/vnc-palette.c new file mode 100644 index 0000000..bff6445 --- /dev/null +++ b/ui/vnc-palette.c @@ -0,0 +1,136 @@ +/* + * QEMU VNC display driver: palette hash table + * + * From libvncserver/libvncserver/tight.c + * Copyright (C) 2000, 2001 Const Kaplinsky. All Rights Reserved. + * Copyright (C) 1999 AT&T Laboratories Cambridge. All Rights Reserved. + * + * Copyright (C) 2010 Corentin Chary + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + */ + +#include "vnc-palette.h" + +static VncPaletteEntry *palette_find(const VncPalette *palette, + uint32_t color, unsigned int hash) +{ + VncPaletteEntry *entry; + + QLIST_FOREACH(entry, &palette->table[hash], next) { + if (entry->color == color) { + return entry; + } + } + + return NULL; +} + +static unsigned int palette_hash(uint32_t rgb, int bpp) +{ + if (bpp == 16) { + return ((unsigned int)(((rgb >> 8) + rgb) & 0xFF)); + } else { + return ((unsigned int)(((rgb >> 16) + (rgb >> 8)) & 0xFF)); + } +} + +VncPalette *palette_new(size_t max, int bpp) +{ + VncPalette *palette; + + palette = qemu_mallocz(sizeof(*palette)); + palette->max = max; + palette->bpp = bpp; + return palette; +} + +void palette_destroy(VncPalette *palette) +{ + int i; + + if (palette == NULL) { + return ; + } + + for (i = 0; i < VNC_PALETTE_HASH_SIZE; i++) { + VncPaletteEntry *entry = QLIST_FIRST(&palette->table[i]); + while (entry) { + VncPaletteEntry *tmp = QLIST_NEXT(entry, next); + QLIST_REMOVE(entry, next); + qemu_free(entry); + entry = tmp; + } + } + + qemu_free(palette); +} + +int palette_put(VncPalette *palette, uint32_t color) +{ + unsigned int hash; + unsigned int idx = palette->size; + VncPaletteEntry *entry; + + hash = palette_hash(color, palette->bpp) % VNC_PALETTE_HASH_SIZE; + entry = palette_find(palette, color, hash); + + if (!entry && palette->size >= palette->max) { + return 0; + } + if (!entry) { + VncPaletteEntry *entry; + + entry = qemu_mallocz(sizeof(*entry)); + entry->color = color; + entry->idx = idx; + QLIST_INSERT_HEAD(&palette->table[hash], entry, next); + palette->size++; + } + return palette->size; +} + +int palette_idx(const VncPalette *palette, uint32_t color) +{ + VncPaletteEntry *entry; + unsigned int hash; + + hash = palette_hash(color, palette->bpp) % VNC_PALETTE_HASH_SIZE; + entry = palette_find(palette, color, hash); + return (entry == NULL ? -1 : entry->idx); +} + +size_t palette_size(const VncPalette *palette) +{ + return palette->size; +} + +void palette_iter(const VncPalette *palette, + void (*iter)(int idx, uint32_t color, void *opaque), + void *opaque) +{ + int i; + VncPaletteEntry *entry; + + for (i = 0; i < VNC_PALETTE_HASH_SIZE; i++) { + QLIST_FOREACH(entry, &palette->table[i], next) { + iter(entry->idx, entry->color, opaque); + } + } +} diff --git a/ui/vnc-palette.h b/ui/vnc-palette.h new file mode 100644 index 0000000..d0645eb --- /dev/null +++ b/ui/vnc-palette.h @@ -0,0 +1,63 @@ +/* + * QEMU VNC display driver: palette hash table + * + * From libvncserver/libvncserver/tight.c + * Copyright (C) 2000, 2001 Const Kaplinsky. All Rights Reserved. + * Copyright (C) 1999 AT&T Laboratories Cambridge. All Rights Reserved. + * + * Copyright (C) 2010 Corentin Chary + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + */ + +#ifndef VNC_PALETTE_H +#define VNC_PALETTE_H + +#include "qlist.h" +#include "qemu-queue.h" +#include + +#define VNC_PALETTE_HASH_SIZE 256 + +typedef struct VncPaletteEntry { + int idx; + uint32_t color; + QLIST_ENTRY(VncPaletteEntry) next; +} VncPaletteEntry; + +typedef struct VncPalette { + QObject_HEAD; + size_t size; + size_t max; + int bpp; + QLIST_HEAD(,VncPaletteEntry) table[VNC_PALETTE_HASH_SIZE]; +} VncPalette; + +VncPalette *palette_new(size_t max, int bpp); +void palette_destroy(VncPalette *palette); + +int palette_put(VncPalette *palette, uint32_t color); +int palette_idx(const VncPalette *palette, uint32_t color); +size_t palette_size(const VncPalette *palette); + +void palette_iter(const VncPalette *palette, + void (*iter)(int idx, uint32_t color, void *opaque), + void *opaque); + +#endif /* VNC_PALETTE_H */