[Qemu-devel] [PATCH v2 10/18] vnc: tight: stop using qdict for palette stuff

[Corentin Chary <corentincj@iksaif.net>]

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 <corentincj@iksaif.net>
---
 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 <corentin.chary@gmail.com>
+ *
+ * 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 <corentin.chary@gmail.com>
+ *
+ * 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 <stdint.h>
+
+#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 */
-- 
1.7.1