qemu/ui/vnc-enc-tight.c
<<
>>
Prefs
   1/*
   2 * QEMU VNC display driver: tight encoding
   3 *
   4 * From libvncserver/libvncserver/tight.c
   5 * Copyright (C) 2000, 2001 Const Kaplinsky.  All Rights Reserved.
   6 * Copyright (C) 1999 AT&T Laboratories Cambridge.  All Rights Reserved.
   7 *
   8 * Copyright (C) 2010 Corentin Chary <corentin.chary@gmail.com>
   9 *
  10 * Permission is hereby granted, free of charge, to any person obtaining a copy
  11 * of this software and associated documentation files (the "Software"), to deal
  12 * in the Software without restriction, including without limitation the rights
  13 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  14 * copies of the Software, and to permit persons to whom the Software is
  15 * furnished to do so, subject to the following conditions:
  16 *
  17 * The above copyright notice and this permission notice shall be included in
  18 * all copies or substantial portions of the Software.
  19 *
  20 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  21 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  22 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  23 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  24 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  25 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  26 * THE SOFTWARE.
  27 */
  28
  29#include "qemu/osdep.h"
  30
  31/* This needs to be before jpeglib.h line because of conflict with
  32   INT32 definitions between jmorecfg.h (included by jpeglib.h) and
  33   Win32 basetsd.h (included by windows.h). */
  34
  35#ifdef CONFIG_VNC_PNG
  36/* The following define is needed by pngconf.h. Otherwise it won't compile,
  37   because setjmp.h was already included by qemu-common.h. */
  38#define PNG_SKIP_SETJMP_CHECK
  39#include <png.h>
  40#endif
  41#ifdef CONFIG_VNC_JPEG
  42#include <jpeglib.h>
  43#endif
  44
  45#include "qemu/bswap.h"
  46#include "vnc.h"
  47#include "vnc-enc-tight.h"
  48#include "vnc-palette.h"
  49
  50/* Compression level stuff. The following array contains various
  51   encoder parameters for each of 10 compression levels (0..9).
  52   Last three parameters correspond to JPEG quality levels (0..9). */
  53
  54static const struct {
  55    int max_rect_size, max_rect_width;
  56    int mono_min_rect_size, gradient_min_rect_size;
  57    int idx_zlib_level, mono_zlib_level, raw_zlib_level, gradient_zlib_level;
  58    int gradient_threshold, gradient_threshold24;
  59    int idx_max_colors_divisor;
  60    int jpeg_quality, jpeg_threshold, jpeg_threshold24;
  61} tight_conf[] = {
  62    {   512,   32,   6, 65536, 0, 0, 0, 0,   0,   0,   4,  5, 10000, 23000 },
  63    {  2048,  128,   6, 65536, 1, 1, 1, 0,   0,   0,   8, 10,  8000, 18000 },
  64    {  6144,  256,   8, 65536, 3, 3, 2, 0,   0,   0,  24, 15,  6500, 15000 },
  65    { 10240, 1024,  12, 65536, 5, 5, 3, 0,   0,   0,  32, 25,  5000, 12000 },
  66    { 16384, 2048,  12, 65536, 6, 6, 4, 0,   0,   0,  32, 37,  4000, 10000 },
  67    { 32768, 2048,  12,  4096, 7, 7, 5, 4, 150, 380,  32, 50,  3000,  8000 },
  68    { 65536, 2048,  16,  4096, 7, 7, 6, 4, 170, 420,  48, 60,  2000,  5000 },
  69    { 65536, 2048,  16,  4096, 8, 8, 7, 5, 180, 450,  64, 70,  1000,  2500 },
  70    { 65536, 2048,  32,  8192, 9, 9, 8, 6, 190, 475,  64, 75,   500,  1200 },
  71    { 65536, 2048,  32,  8192, 9, 9, 9, 6, 200, 500,  96, 80,   200,   500 }
  72};
  73
  74
  75static int tight_send_framebuffer_update(VncState *vs, int x, int y,
  76                                         int w, int h);
  77
  78#ifdef CONFIG_VNC_JPEG
  79static const struct {
  80    double jpeg_freq_min;       /* Don't send JPEG if the freq is bellow */
  81    double jpeg_freq_threshold; /* Always send JPEG if the freq is above */
  82    int jpeg_idx;               /* Allow indexed JPEG */
  83    int jpeg_full;              /* Allow full color JPEG */
  84} tight_jpeg_conf[] = {
  85    { 0,   8,  1, 1 },
  86    { 0,   8,  1, 1 },
  87    { 0,   8,  1, 1 },
  88    { 0,   8,  1, 1 },
  89    { 0,   10, 1, 1 },
  90    { 0.1, 10, 1, 1 },
  91    { 0.2, 10, 1, 1 },
  92    { 0.3, 12, 0, 0 },
  93    { 0.4, 14, 0, 0 },
  94    { 0.5, 16, 0, 0 },
  95};
  96#endif
  97
  98#ifdef CONFIG_VNC_PNG
  99static const struct {
 100    int png_zlib_level, png_filters;
 101} tight_png_conf[] = {
 102    { 0, PNG_NO_FILTERS },
 103    { 1, PNG_NO_FILTERS },
 104    { 2, PNG_NO_FILTERS },
 105    { 3, PNG_NO_FILTERS },
 106    { 4, PNG_NO_FILTERS },
 107    { 5, PNG_ALL_FILTERS },
 108    { 6, PNG_ALL_FILTERS },
 109    { 7, PNG_ALL_FILTERS },
 110    { 8, PNG_ALL_FILTERS },
 111    { 9, PNG_ALL_FILTERS },
 112};
 113
 114static int send_png_rect(VncState *vs, int x, int y, int w, int h,
 115                         VncPalette *palette);
 116
 117static bool tight_can_send_png_rect(VncState *vs, int w, int h)
 118{
 119    if (vs->tight->type != VNC_ENCODING_TIGHT_PNG) {
 120        return false;
 121    }
 122
 123    if (surface_bytes_per_pixel(vs->vd->ds) == 1 ||
 124        vs->client_pf.bytes_per_pixel == 1) {
 125        return false;
 126    }
 127
 128    return true;
 129}
 130#endif
 131
 132/*
 133 * Code to guess if given rectangle is suitable for smooth image
 134 * compression (by applying "gradient" filter or JPEG coder).
 135 */
 136
 137static unsigned int
 138tight_detect_smooth_image24(VncState *vs, int w, int h)
 139{
 140    int off;
 141    int x, y, d, dx;
 142    unsigned int c;
 143    unsigned int stats[256];
 144    int pixels = 0;
 145    int pix, left[3];
 146    unsigned int errors;
 147    unsigned char *buf = vs->tight->tight.buffer;
 148
 149    /*
 150     * If client is big-endian, color samples begin from the second
 151     * byte (offset 1) of a 32-bit pixel value.
 152     */
 153    off = vs->client_be;
 154
 155    memset(stats, 0, sizeof (stats));
 156
 157    for (y = 0, x = 0; y < h && x < w;) {
 158        for (d = 0; d < h - y && d < w - x - VNC_TIGHT_DETECT_SUBROW_WIDTH;
 159             d++) {
 160            for (c = 0; c < 3; c++) {
 161                left[c] = buf[((y+d)*w+x+d)*4+off+c] & 0xFF;
 162            }
 163            for (dx = 1; dx <= VNC_TIGHT_DETECT_SUBROW_WIDTH; dx++) {
 164                for (c = 0; c < 3; c++) {
 165                    pix = buf[((y+d)*w+x+d+dx)*4+off+c] & 0xFF;
 166                    stats[abs(pix - left[c])]++;
 167                    left[c] = pix;
 168                }
 169                pixels++;
 170            }
 171        }
 172        if (w > h) {
 173            x += h;
 174            y = 0;
 175        } else {
 176            x = 0;
 177            y += w;
 178        }
 179    }
 180
 181    if (pixels == 0) {
 182        return 0;
 183    }
 184
 185    /* 95% smooth or more ... */
 186    if (stats[0] * 33 / pixels >= 95) {
 187        return 0;
 188    }
 189
 190    errors = 0;
 191    for (c = 1; c < 8; c++) {
 192        errors += stats[c] * (c * c);
 193        if (stats[c] == 0 || stats[c] > stats[c-1] * 2) {
 194            return 0;
 195        }
 196    }
 197    for (; c < 256; c++) {
 198        errors += stats[c] * (c * c);
 199    }
 200    errors /= (pixels * 3 - stats[0]);
 201
 202    return errors;
 203}
 204
 205#define DEFINE_DETECT_FUNCTION(bpp)                                     \
 206                                                                        \
 207    static unsigned int                                                 \
 208    tight_detect_smooth_image##bpp(VncState *vs, int w, int h) {        \
 209        bool endian;                                                    \
 210        uint##bpp##_t pix;                                              \
 211        int max[3], shift[3];                                           \
 212        int x, y, d, dx;                                                \
 213        unsigned int c;                                                 \
 214        unsigned int stats[256];                                        \
 215        int pixels = 0;                                                 \
 216        int sample, sum, left[3];                                       \
 217        unsigned int errors;                                            \
 218        unsigned char *buf = vs->tight->tight.buffer;                    \
 219                                                                        \
 220        endian = 0; /* FIXME */                                         \
 221                                                                        \
 222                                                                        \
 223        max[0] = vs->client_pf.rmax;                                  \
 224        max[1] = vs->client_pf.gmax;                                  \
 225        max[2] = vs->client_pf.bmax;                                  \
 226        shift[0] = vs->client_pf.rshift;                              \
 227        shift[1] = vs->client_pf.gshift;                              \
 228        shift[2] = vs->client_pf.bshift;                              \
 229                                                                        \
 230        memset(stats, 0, sizeof(stats));                                \
 231                                                                        \
 232        y = 0, x = 0;                                                   \
 233        while (y < h && x < w) {                                        \
 234            for (d = 0; d < h - y &&                                    \
 235                     d < w - x - VNC_TIGHT_DETECT_SUBROW_WIDTH; d++) {  \
 236                pix = ((uint##bpp##_t *)buf)[(y+d)*w+x+d];              \
 237                if (endian) {                                           \
 238                    pix = bswap##bpp(pix);                              \
 239                }                                                       \
 240                for (c = 0; c < 3; c++) {                               \
 241                    left[c] = (int)(pix >> shift[c] & max[c]);          \
 242                }                                                       \
 243                for (dx = 1; dx <= VNC_TIGHT_DETECT_SUBROW_WIDTH;       \
 244                     dx++) {                                            \
 245                    pix = ((uint##bpp##_t *)buf)[(y+d)*w+x+d+dx];       \
 246                    if (endian) {                                       \
 247                        pix = bswap##bpp(pix);                          \
 248                    }                                                   \
 249                    sum = 0;                                            \
 250                    for (c = 0; c < 3; c++) {                           \
 251                        sample = (int)(pix >> shift[c] & max[c]);       \
 252                        sum += abs(sample - left[c]);                   \
 253                        left[c] = sample;                               \
 254                    }                                                   \
 255                    if (sum > 255) {                                    \
 256                        sum = 255;                                      \
 257                    }                                                   \
 258                    stats[sum]++;                                       \
 259                    pixels++;                                           \
 260                }                                                       \
 261            }                                                           \
 262            if (w > h) {                                                \
 263                x += h;                                                 \
 264                y = 0;                                                  \
 265            } else {                                                    \
 266                x = 0;                                                  \
 267                y += w;                                                 \
 268            }                                                           \
 269        }                                                               \
 270        if (pixels == 0) {                                              \
 271            return 0;                                                   \
 272        }                                                               \
 273        if ((stats[0] + stats[1]) * 100 / pixels >= 90) {               \
 274            return 0;                                                   \
 275        }                                                               \
 276                                                                        \
 277        errors = 0;                                                     \
 278        for (c = 1; c < 8; c++) {                                       \
 279            errors += stats[c] * (c * c);                               \
 280            if (stats[c] == 0 || stats[c] > stats[c-1] * 2) {           \
 281                return 0;                                               \
 282            }                                                           \
 283        }                                                               \
 284        for (; c < 256; c++) {                                          \
 285            errors += stats[c] * (c * c);                               \
 286        }                                                               \
 287        errors /= (pixels - stats[0]);                                  \
 288                                                                        \
 289        return errors;                                                  \
 290    }
 291
 292DEFINE_DETECT_FUNCTION(16)
 293DEFINE_DETECT_FUNCTION(32)
 294
 295static int
 296tight_detect_smooth_image(VncState *vs, int w, int h)
 297{
 298    unsigned int errors;
 299    int compression = vs->tight->compression;
 300    int quality = vs->tight->quality;
 301
 302    if (!vs->vd->lossy) {
 303        return 0;
 304    }
 305
 306    if (surface_bytes_per_pixel(vs->vd->ds) == 1 ||
 307        vs->client_pf.bytes_per_pixel == 1 ||
 308        w < VNC_TIGHT_DETECT_MIN_WIDTH || h < VNC_TIGHT_DETECT_MIN_HEIGHT) {
 309        return 0;
 310    }
 311
 312    if (vs->tight->quality != (uint8_t)-1) {
 313        if (w * h < VNC_TIGHT_JPEG_MIN_RECT_SIZE) {
 314            return 0;
 315        }
 316    } else {
 317        if (w * h < tight_conf[compression].gradient_min_rect_size) {
 318            return 0;
 319        }
 320    }
 321
 322    if (vs->client_pf.bytes_per_pixel == 4) {
 323        if (vs->tight->pixel24) {
 324            errors = tight_detect_smooth_image24(vs, w, h);
 325            if (vs->tight->quality != (uint8_t)-1) {
 326                return (errors < tight_conf[quality].jpeg_threshold24);
 327            }
 328            return (errors < tight_conf[compression].gradient_threshold24);
 329        } else {
 330            errors = tight_detect_smooth_image32(vs, w, h);
 331        }
 332    } else {
 333        errors = tight_detect_smooth_image16(vs, w, h);
 334    }
 335    if (quality != (uint8_t)-1) {
 336        return (errors < tight_conf[quality].jpeg_threshold);
 337    }
 338    return (errors < tight_conf[compression].gradient_threshold);
 339}
 340
 341/*
 342 * Code to determine how many different colors used in rectangle.
 343 */
 344#define DEFINE_FILL_PALETTE_FUNCTION(bpp)                               \
 345                                                                        \
 346    static int                                                          \
 347    tight_fill_palette##bpp(VncState *vs, int x, int y,                 \
 348                            int max, size_t count,                      \
 349                            uint32_t *bg, uint32_t *fg,                 \
 350                            VncPalette *palette) {                      \
 351        uint##bpp##_t *data;                                            \
 352        uint##bpp##_t c0, c1, ci;                                       \
 353        int i, n0, n1;                                                  \
 354                                                                        \
 355        data = (uint##bpp##_t *)vs->tight->tight.buffer;                \
 356                                                                        \
 357        c0 = data[0];                                                   \
 358        i = 1;                                                          \
 359        while (i < count && data[i] == c0)                              \
 360            i++;                                                        \
 361        if (i >= count) {                                               \
 362            *bg = *fg = c0;                                             \
 363            return 1;                                                   \
 364        }                                                               \
 365                                                                        \
 366        if (max < 2) {                                                  \
 367            return 0;                                                   \
 368        }                                                               \
 369                                                                        \
 370        n0 = i;                                                         \
 371        c1 = data[i];                                                   \
 372        n1 = 0;                                                         \
 373        for (i++; i < count; i++) {                                     \
 374            ci = data[i];                                               \
 375            if (ci == c0) {                                             \
 376                n0++;                                                   \
 377            } else if (ci == c1) {                                      \
 378                n1++;                                                   \
 379            } else                                                      \
 380                break;                                                  \
 381        }                                                               \
 382        if (i >= count) {                                               \
 383            if (n0 > n1) {                                              \
 384                *bg = (uint32_t)c0;                                     \
 385                *fg = (uint32_t)c1;                                     \
 386            } else {                                                    \
 387                *bg = (uint32_t)c1;                                     \
 388                *fg = (uint32_t)c0;                                     \
 389            }                                                           \
 390            return 2;                                                   \
 391        }                                                               \
 392                                                                        \
 393        if (max == 2) {                                                 \
 394            return 0;                                                   \
 395        }                                                               \
 396                                                                        \
 397        palette_init(palette, max, bpp);                                \
 398        palette_put(palette, c0);                                       \
 399        palette_put(palette, c1);                                       \
 400        palette_put(palette, ci);                                       \
 401                                                                        \
 402        for (i++; i < count; i++) {                                     \
 403            if (data[i] == ci) {                                        \
 404                continue;                                               \
 405            } else {                                                    \
 406                ci = data[i];                                           \
 407                if (!palette_put(palette, (uint32_t)ci)) {              \
 408                    return 0;                                           \
 409                }                                                       \
 410            }                                                           \
 411        }                                                               \
 412                                                                        \
 413        return palette_size(palette);                                   \
 414    }
 415
 416DEFINE_FILL_PALETTE_FUNCTION(8)
 417DEFINE_FILL_PALETTE_FUNCTION(16)
 418DEFINE_FILL_PALETTE_FUNCTION(32)
 419
 420static int tight_fill_palette(VncState *vs, int x, int y,
 421                              size_t count, uint32_t *bg, uint32_t *fg,
 422                              VncPalette *palette)
 423{
 424    int max;
 425
 426    max = count / tight_conf[vs->tight->compression].idx_max_colors_divisor;
 427    if (max < 2 &&
 428        count >= tight_conf[vs->tight->compression].mono_min_rect_size) {
 429        max = 2;
 430    }
 431    if (max >= 256) {
 432        max = 256;
 433    }
 434
 435    switch (vs->client_pf.bytes_per_pixel) {
 436    case 4:
 437        return tight_fill_palette32(vs, x, y, max, count, bg, fg, palette);
 438    case 2:
 439        return tight_fill_palette16(vs, x, y, max, count, bg, fg, palette);
 440    default:
 441        max = 2;
 442        return tight_fill_palette8(vs, x, y, max, count, bg, fg, palette);
 443    }
 444    return 0;
 445}
 446
 447/*
 448 * Converting truecolor samples into palette indices.
 449 */
 450#define DEFINE_IDX_ENCODE_FUNCTION(bpp)                                 \
 451                                                                        \
 452    static void                                                         \
 453    tight_encode_indexed_rect##bpp(uint8_t *buf, int count,             \
 454                                   VncPalette *palette) {               \
 455        uint##bpp##_t *src;                                             \
 456        uint##bpp##_t rgb;                                              \
 457        int i, rep;                                                     \
 458        uint8_t idx;                                                    \
 459                                                                        \
 460        src = (uint##bpp##_t *) buf;                                    \
 461                                                                        \
 462        for (i = 0; i < count; ) {                                      \
 463                                                                        \
 464            rgb = *src++;                                               \
 465            i++;                                                        \
 466            rep = 0;                                                    \
 467            while (i < count && *src == rgb) {                          \
 468                rep++, src++, i++;                                      \
 469            }                                                           \
 470            idx = palette_idx(palette, rgb);                            \
 471            /*                                                          \
 472             * Should never happen, but don't break everything          \
 473             * if it does, use the first color instead                  \
 474             */                                                         \
 475            if (idx == (uint8_t)-1) {                                   \
 476                idx = 0;                                                \
 477            }                                                           \
 478            while (rep >= 0) {                                          \
 479                *buf++ = idx;                                           \
 480                rep--;                                                  \
 481            }                                                           \
 482        }                                                               \
 483    }
 484
 485DEFINE_IDX_ENCODE_FUNCTION(16)
 486DEFINE_IDX_ENCODE_FUNCTION(32)
 487
 488#define DEFINE_MONO_ENCODE_FUNCTION(bpp)                                \
 489                                                                        \
 490    static void                                                         \
 491    tight_encode_mono_rect##bpp(uint8_t *buf, int w, int h,             \
 492                                uint##bpp##_t bg, uint##bpp##_t fg) {   \
 493        uint##bpp##_t *ptr;                                             \
 494        unsigned int value, mask;                                       \
 495        int aligned_width;                                              \
 496        int x, y, bg_bits;                                              \
 497                                                                        \
 498        ptr = (uint##bpp##_t *) buf;                                    \
 499        aligned_width = w - w % 8;                                      \
 500                                                                        \
 501        for (y = 0; y < h; y++) {                                       \
 502            for (x = 0; x < aligned_width; x += 8) {                    \
 503                for (bg_bits = 0; bg_bits < 8; bg_bits++) {             \
 504                    if (*ptr++ != bg) {                                 \
 505                        break;                                          \
 506                    }                                                   \
 507                }                                                       \
 508                if (bg_bits == 8) {                                     \
 509                    *buf++ = 0;                                         \
 510                    continue;                                           \
 511                }                                                       \
 512                mask = 0x80 >> bg_bits;                                 \
 513                value = mask;                                           \
 514                for (bg_bits++; bg_bits < 8; bg_bits++) {               \
 515                    mask >>= 1;                                         \
 516                    if (*ptr++ != bg) {                                 \
 517                        value |= mask;                                  \
 518                    }                                                   \
 519                }                                                       \
 520                *buf++ = (uint8_t)value;                                \
 521            }                                                           \
 522                                                                        \
 523            mask = 0x80;                                                \
 524            value = 0;                                                  \
 525            if (x >= w) {                                               \
 526                continue;                                               \
 527            }                                                           \
 528                                                                        \
 529            for (; x < w; x++) {                                        \
 530                if (*ptr++ != bg) {                                     \
 531                    value |= mask;                                      \
 532                }                                                       \
 533                mask >>= 1;                                             \
 534            }                                                           \
 535            *buf++ = (uint8_t)value;                                    \
 536        }                                                               \
 537    }
 538
 539DEFINE_MONO_ENCODE_FUNCTION(8)
 540DEFINE_MONO_ENCODE_FUNCTION(16)
 541DEFINE_MONO_ENCODE_FUNCTION(32)
 542
 543/*
 544 * ``Gradient'' filter for 24-bit color samples.
 545 * Should be called only when redMax, greenMax and blueMax are 255.
 546 * Color components assumed to be byte-aligned.
 547 */
 548
 549static void
 550tight_filter_gradient24(VncState *vs, uint8_t *buf, int w, int h)
 551{
 552    uint32_t *buf32;
 553    uint32_t pix32;
 554    int shift[3];
 555    int *prev;
 556    int here[3], upper[3], left[3], upperleft[3];
 557    int prediction;
 558    int x, y, c;
 559
 560    buf32 = (uint32_t *)buf;
 561    memset(vs->tight->gradient.buffer, 0, w * 3 * sizeof(int));
 562
 563    if (1 /* FIXME */) {
 564        shift[0] = vs->client_pf.rshift;
 565        shift[1] = vs->client_pf.gshift;
 566        shift[2] = vs->client_pf.bshift;
 567    } else {
 568        shift[0] = 24 - vs->client_pf.rshift;
 569        shift[1] = 24 - vs->client_pf.gshift;
 570        shift[2] = 24 - vs->client_pf.bshift;
 571    }
 572
 573    for (y = 0; y < h; y++) {
 574        for (c = 0; c < 3; c++) {
 575            upper[c] = 0;
 576            here[c] = 0;
 577        }
 578        prev = (int *)vs->tight->gradient.buffer;
 579        for (x = 0; x < w; x++) {
 580            pix32 = *buf32++;
 581            for (c = 0; c < 3; c++) {
 582                upperleft[c] = upper[c];
 583                left[c] = here[c];
 584                upper[c] = *prev;
 585                here[c] = (int)(pix32 >> shift[c] & 0xFF);
 586                *prev++ = here[c];
 587
 588                prediction = left[c] + upper[c] - upperleft[c];
 589                if (prediction < 0) {
 590                    prediction = 0;
 591                } else if (prediction > 0xFF) {
 592                    prediction = 0xFF;
 593                }
 594                *buf++ = (char)(here[c] - prediction);
 595            }
 596        }
 597    }
 598}
 599
 600
 601/*
 602 * ``Gradient'' filter for other color depths.
 603 */
 604
 605#define DEFINE_GRADIENT_FILTER_FUNCTION(bpp)                            \
 606                                                                        \
 607    static void                                                         \
 608    tight_filter_gradient##bpp(VncState *vs, uint##bpp##_t *buf,        \
 609                               int w, int h) {                          \
 610        uint##bpp##_t pix, diff;                                        \
 611        bool endian;                                                    \
 612        int *prev;                                                      \
 613        int max[3], shift[3];                                           \
 614        int here[3], upper[3], left[3], upperleft[3];                   \
 615        int prediction;                                                 \
 616        int x, y, c;                                                    \
 617                                                                        \
 618        memset(vs->tight->gradient.buffer, 0, w * 3 * sizeof(int));     \
 619                                                                        \
 620        endian = 0; /* FIXME */                                         \
 621                                                                        \
 622        max[0] = vs->client_pf.rmax;                                    \
 623        max[1] = vs->client_pf.gmax;                                    \
 624        max[2] = vs->client_pf.bmax;                                    \
 625        shift[0] = vs->client_pf.rshift;                                \
 626        shift[1] = vs->client_pf.gshift;                                \
 627        shift[2] = vs->client_pf.bshift;                                \
 628                                                                        \
 629        for (y = 0; y < h; y++) {                                       \
 630            for (c = 0; c < 3; c++) {                                   \
 631                upper[c] = 0;                                           \
 632                here[c] = 0;                                            \
 633            }                                                           \
 634            prev = (int *)vs->tight->gradient.buffer;                    \
 635            for (x = 0; x < w; x++) {                                   \
 636                pix = *buf;                                             \
 637                if (endian) {                                           \
 638                    pix = bswap##bpp(pix);                              \
 639                }                                                       \
 640                diff = 0;                                               \
 641                for (c = 0; c < 3; c++) {                               \
 642                    upperleft[c] = upper[c];                            \
 643                    left[c] = here[c];                                  \
 644                    upper[c] = *prev;                                   \
 645                    here[c] = (int)(pix >> shift[c] & max[c]);          \
 646                    *prev++ = here[c];                                  \
 647                                                                        \
 648                    prediction = left[c] + upper[c] - upperleft[c];     \
 649                    if (prediction < 0) {                               \
 650                        prediction = 0;                                 \
 651                    } else if (prediction > max[c]) {                   \
 652                        prediction = max[c];                            \
 653                    }                                                   \
 654                    diff |= ((here[c] - prediction) & max[c])           \
 655                        << shift[c];                                    \
 656                }                                                       \
 657                if (endian) {                                           \
 658                    diff = bswap##bpp(diff);                            \
 659                }                                                       \
 660                *buf++ = diff;                                          \
 661            }                                                           \
 662        }                                                               \
 663    }
 664
 665DEFINE_GRADIENT_FILTER_FUNCTION(16)
 666DEFINE_GRADIENT_FILTER_FUNCTION(32)
 667
 668/*
 669 * Check if a rectangle is all of the same color. If needSameColor is
 670 * set to non-zero, then also check that its color equals to the
 671 * *colorPtr value. The result is 1 if the test is successful, and in
 672 * that case new color will be stored in *colorPtr.
 673 */
 674
 675static bool
 676check_solid_tile32(VncState *vs, int x, int y, int w, int h,
 677                   uint32_t *color, bool samecolor)
 678{
 679    VncDisplay *vd = vs->vd;
 680    uint32_t *fbptr;
 681    uint32_t c;
 682    int dx, dy;
 683
 684    fbptr = vnc_server_fb_ptr(vd, x, y);
 685
 686    c = *fbptr;
 687    if (samecolor && (uint32_t)c != *color) {
 688        return false;
 689    }
 690
 691    for (dy = 0; dy < h; dy++) {
 692        for (dx = 0; dx < w; dx++) {
 693            if (c != fbptr[dx]) {
 694                return false;
 695            }
 696        }
 697        fbptr = (uint32_t *)
 698            ((uint8_t *)fbptr + vnc_server_fb_stride(vd));
 699    }
 700
 701    *color = (uint32_t)c;
 702    return true;
 703}
 704
 705static bool check_solid_tile(VncState *vs, int x, int y, int w, int h,
 706                             uint32_t* color, bool samecolor)
 707{
 708    QEMU_BUILD_BUG_ON(VNC_SERVER_FB_BYTES != 4);
 709    return check_solid_tile32(vs, x, y, w, h, color, samecolor);
 710}
 711
 712static void find_best_solid_area(VncState *vs, int x, int y, int w, int h,
 713                                 uint32_t color, int *w_ptr, int *h_ptr)
 714{
 715    int dx, dy, dw, dh;
 716    int w_prev;
 717    int w_best = 0, h_best = 0;
 718
 719    w_prev = w;
 720
 721    for (dy = y; dy < y + h; dy += VNC_TIGHT_MAX_SPLIT_TILE_SIZE) {
 722
 723        dh = MIN(VNC_TIGHT_MAX_SPLIT_TILE_SIZE, y + h - dy);
 724        dw = MIN(VNC_TIGHT_MAX_SPLIT_TILE_SIZE, w_prev);
 725
 726        if (!check_solid_tile(vs, x, dy, dw, dh, &color, true)) {
 727            break;
 728        }
 729
 730        for (dx = x + dw; dx < x + w_prev;) {
 731            dw = MIN(VNC_TIGHT_MAX_SPLIT_TILE_SIZE, x + w_prev - dx);
 732
 733            if (!check_solid_tile(vs, dx, dy, dw, dh, &color, true)) {
 734                break;
 735            }
 736            dx += dw;
 737        }
 738
 739        w_prev = dx - x;
 740        if (w_prev * (dy + dh - y) > w_best * h_best) {
 741            w_best = w_prev;
 742            h_best = dy + dh - y;
 743        }
 744    }
 745
 746    *w_ptr = w_best;
 747    *h_ptr = h_best;
 748}
 749
 750static void extend_solid_area(VncState *vs, int x, int y, int w, int h,
 751                              uint32_t color, int *x_ptr, int *y_ptr,
 752                              int *w_ptr, int *h_ptr)
 753{
 754    int cx, cy;
 755
 756    /* Try to extend the area upwards. */
 757    for ( cy = *y_ptr - 1;
 758          cy >= y && check_solid_tile(vs, *x_ptr, cy, *w_ptr, 1, &color, true);
 759          cy-- );
 760    *h_ptr += *y_ptr - (cy + 1);
 761    *y_ptr = cy + 1;
 762
 763    /* ... downwards. */
 764    for ( cy = *y_ptr + *h_ptr;
 765          cy < y + h &&
 766              check_solid_tile(vs, *x_ptr, cy, *w_ptr, 1, &color, true);
 767          cy++ );
 768    *h_ptr += cy - (*y_ptr + *h_ptr);
 769
 770    /* ... to the left. */
 771    for ( cx = *x_ptr - 1;
 772          cx >= x && check_solid_tile(vs, cx, *y_ptr, 1, *h_ptr, &color, true);
 773          cx-- );
 774    *w_ptr += *x_ptr - (cx + 1);
 775    *x_ptr = cx + 1;
 776
 777    /* ... to the right. */
 778    for ( cx = *x_ptr + *w_ptr;
 779          cx < x + w &&
 780              check_solid_tile(vs, cx, *y_ptr, 1, *h_ptr, &color, true);
 781          cx++ );
 782    *w_ptr += cx - (*x_ptr + *w_ptr);
 783}
 784
 785static int tight_init_stream(VncState *vs, int stream_id,
 786                             int level, int strategy)
 787{
 788    z_streamp zstream = &vs->tight->stream[stream_id];
 789
 790    if (zstream->opaque == NULL) {
 791        int err;
 792
 793        VNC_DEBUG("VNC: TIGHT: initializing zlib stream %d\n", stream_id);
 794        VNC_DEBUG("VNC: TIGHT: opaque = %p | vs = %p\n", zstream->opaque, vs);
 795        zstream->zalloc = vnc_zlib_zalloc;
 796        zstream->zfree = vnc_zlib_zfree;
 797
 798        err = deflateInit2(zstream, level, Z_DEFLATED, MAX_WBITS,
 799                           MAX_MEM_LEVEL, strategy);
 800
 801        if (err != Z_OK) {
 802            fprintf(stderr, "VNC: error initializing zlib\n");
 803            return -1;
 804        }
 805
 806        vs->tight->levels[stream_id] = level;
 807        zstream->opaque = vs;
 808    }
 809
 810    if (vs->tight->levels[stream_id] != level) {
 811        if (deflateParams(zstream, level, strategy) != Z_OK) {
 812            return -1;
 813        }
 814        vs->tight->levels[stream_id] = level;
 815    }
 816    return 0;
 817}
 818
 819static void tight_send_compact_size(VncState *vs, size_t len)
 820{
 821    int lpc = 0;
 822    int bytes = 0;
 823    char buf[3] = {0, 0, 0};
 824
 825    buf[bytes++] = len & 0x7F;
 826    if (len > 0x7F) {
 827        buf[bytes-1] |= 0x80;
 828        buf[bytes++] = (len >> 7) & 0x7F;
 829        if (len > 0x3FFF) {
 830            buf[bytes-1] |= 0x80;
 831            buf[bytes++] = (len >> 14) & 0xFF;
 832        }
 833    }
 834    for (lpc = 0; lpc < bytes; lpc++) {
 835        vnc_write_u8(vs, buf[lpc]);
 836    }
 837}
 838
 839static int tight_compress_data(VncState *vs, int stream_id, size_t bytes,
 840                               int level, int strategy)
 841{
 842    z_streamp zstream = &vs->tight->stream[stream_id];
 843    int previous_out;
 844
 845    if (bytes < VNC_TIGHT_MIN_TO_COMPRESS) {
 846        vnc_write(vs, vs->tight->tight.buffer, vs->tight->tight.offset);
 847        return bytes;
 848    }
 849
 850    if (tight_init_stream(vs, stream_id, level, strategy)) {
 851        return -1;
 852    }
 853
 854    /* reserve memory in output buffer */
 855    buffer_reserve(&vs->tight->zlib, bytes + 64);
 856
 857    /* set pointers */
 858    zstream->next_in = vs->tight->tight.buffer;
 859    zstream->avail_in = vs->tight->tight.offset;
 860    zstream->next_out = vs->tight->zlib.buffer + vs->tight->zlib.offset;
 861    zstream->avail_out = vs->tight->zlib.capacity - vs->tight->zlib.offset;
 862    previous_out = zstream->avail_out;
 863    zstream->data_type = Z_BINARY;
 864
 865    /* start encoding */
 866    if (deflate(zstream, Z_SYNC_FLUSH) != Z_OK) {
 867        fprintf(stderr, "VNC: error during tight compression\n");
 868        return -1;
 869    }
 870
 871    vs->tight->zlib.offset = vs->tight->zlib.capacity - zstream->avail_out;
 872    /* ...how much data has actually been produced by deflate() */
 873    bytes = previous_out - zstream->avail_out;
 874
 875    tight_send_compact_size(vs, bytes);
 876    vnc_write(vs, vs->tight->zlib.buffer, bytes);
 877
 878    buffer_reset(&vs->tight->zlib);
 879
 880    return bytes;
 881}
 882
 883/*
 884 * Subencoding implementations.
 885 */
 886static void tight_pack24(VncState *vs, uint8_t *buf, size_t count, size_t *ret)
 887{
 888    uint8_t *buf8;
 889    uint32_t pix;
 890    int rshift, gshift, bshift;
 891
 892    buf8 = buf;
 893
 894    if (1 /* FIXME */) {
 895        rshift = vs->client_pf.rshift;
 896        gshift = vs->client_pf.gshift;
 897        bshift = vs->client_pf.bshift;
 898    } else {
 899        rshift = 24 - vs->client_pf.rshift;
 900        gshift = 24 - vs->client_pf.gshift;
 901        bshift = 24 - vs->client_pf.bshift;
 902    }
 903
 904    if (ret) {
 905        *ret = count * 3;
 906    }
 907
 908    while (count--) {
 909        pix = ldl_he_p(buf8);
 910        *buf++ = (char)(pix >> rshift);
 911        *buf++ = (char)(pix >> gshift);
 912        *buf++ = (char)(pix >> bshift);
 913        buf8 += 4;
 914    }
 915}
 916
 917static int send_full_color_rect(VncState *vs, int x, int y, int w, int h)
 918{
 919    int stream = 0;
 920    ssize_t bytes;
 921
 922#ifdef CONFIG_VNC_PNG
 923    if (tight_can_send_png_rect(vs, w, h)) {
 924        return send_png_rect(vs, x, y, w, h, NULL);
 925    }
 926#endif
 927
 928    vnc_write_u8(vs, stream << 4); /* no flushing, no filter */
 929
 930    if (vs->tight->pixel24) {
 931        tight_pack24(vs, vs->tight->tight.buffer, w * h,
 932                     &vs->tight->tight.offset);
 933        bytes = 3;
 934    } else {
 935        bytes = vs->client_pf.bytes_per_pixel;
 936    }
 937
 938    bytes = tight_compress_data(vs, stream, w * h * bytes,
 939                            tight_conf[vs->tight->compression].raw_zlib_level,
 940                            Z_DEFAULT_STRATEGY);
 941
 942    return (bytes >= 0);
 943}
 944
 945static int send_solid_rect(VncState *vs)
 946{
 947    size_t bytes;
 948
 949    vnc_write_u8(vs, VNC_TIGHT_FILL << 4); /* no flushing, no filter */
 950
 951    if (vs->tight->pixel24) {
 952        tight_pack24(vs, vs->tight->tight.buffer, 1, &vs->tight->tight.offset);
 953        bytes = 3;
 954    } else {
 955        bytes = vs->client_pf.bytes_per_pixel;
 956    }
 957
 958    vnc_write(vs, vs->tight->tight.buffer, bytes);
 959    return 1;
 960}
 961
 962static int send_mono_rect(VncState *vs, int x, int y,
 963                          int w, int h, uint32_t bg, uint32_t fg)
 964{
 965    ssize_t bytes;
 966    int stream = 1;
 967    int level = tight_conf[vs->tight->compression].mono_zlib_level;
 968
 969#ifdef CONFIG_VNC_PNG
 970    if (tight_can_send_png_rect(vs, w, h)) {
 971        int ret;
 972        int bpp = vs->client_pf.bytes_per_pixel * 8;
 973        VncPalette *palette = palette_new(2, bpp);
 974
 975        palette_put(palette, bg);
 976        palette_put(palette, fg);
 977        ret = send_png_rect(vs, x, y, w, h, palette);
 978        palette_destroy(palette);
 979        return ret;
 980    }
 981#endif
 982
 983    bytes = DIV_ROUND_UP(w, 8) * h;
 984
 985    vnc_write_u8(vs, (stream | VNC_TIGHT_EXPLICIT_FILTER) << 4);
 986    vnc_write_u8(vs, VNC_TIGHT_FILTER_PALETTE);
 987    vnc_write_u8(vs, 1);
 988
 989    switch (vs->client_pf.bytes_per_pixel) {
 990    case 4:
 991    {
 992        uint32_t buf[2] = {bg, fg};
 993        size_t ret = sizeof (buf);
 994
 995        if (vs->tight->pixel24) {
 996            tight_pack24(vs, (unsigned char*)buf, 2, &ret);
 997        }
 998        vnc_write(vs, buf, ret);
 999
1000        tight_encode_mono_rect32(vs->tight->tight.buffer, w, h, bg, fg);
1001        break;
1002    }
1003    case 2:
1004        vnc_write(vs, &bg, 2);
1005        vnc_write(vs, &fg, 2);
1006        tight_encode_mono_rect16(vs->tight->tight.buffer, w, h, bg, fg);
1007        break;
1008    default:
1009        vnc_write_u8(vs, bg);
1010        vnc_write_u8(vs, fg);
1011        tight_encode_mono_rect8(vs->tight->tight.buffer, w, h, bg, fg);
1012        break;
1013    }
1014    vs->tight->tight.offset = bytes;
1015
1016    bytes = tight_compress_data(vs, stream, bytes, level, Z_DEFAULT_STRATEGY);
1017    return (bytes >= 0);
1018}
1019
1020struct palette_cb_priv {
1021    VncState *vs;
1022    uint8_t *header;
1023#ifdef CONFIG_VNC_PNG
1024    png_colorp png_palette;
1025#endif
1026};
1027
1028static void write_palette(int idx, uint32_t color, void *opaque)
1029{
1030    struct palette_cb_priv *priv = opaque;
1031    VncState *vs = priv->vs;
1032    uint32_t bytes = vs->client_pf.bytes_per_pixel;
1033
1034    if (bytes == 4) {
1035        ((uint32_t*)priv->header)[idx] = color;
1036    } else {
1037        ((uint16_t*)priv->header)[idx] = color;
1038    }
1039}
1040
1041static bool send_gradient_rect(VncState *vs, int x, int y, int w, int h)
1042{
1043    int stream = 3;
1044    int level = tight_conf[vs->tight->compression].gradient_zlib_level;
1045    ssize_t bytes;
1046
1047    if (vs->client_pf.bytes_per_pixel == 1) {
1048        return send_full_color_rect(vs, x, y, w, h);
1049    }
1050
1051    vnc_write_u8(vs, (stream | VNC_TIGHT_EXPLICIT_FILTER) << 4);
1052    vnc_write_u8(vs, VNC_TIGHT_FILTER_GRADIENT);
1053
1054    buffer_reserve(&vs->tight->gradient, w * 3 * sizeof(int));
1055
1056    if (vs->tight->pixel24) {
1057        tight_filter_gradient24(vs, vs->tight->tight.buffer, w, h);
1058        bytes = 3;
1059    } else if (vs->client_pf.bytes_per_pixel == 4) {
1060        tight_filter_gradient32(vs, (uint32_t *)vs->tight->tight.buffer, w, h);
1061        bytes = 4;
1062    } else {
1063        tight_filter_gradient16(vs, (uint16_t *)vs->tight->tight.buffer, w, h);
1064        bytes = 2;
1065    }
1066
1067    buffer_reset(&vs->tight->gradient);
1068
1069    bytes = w * h * bytes;
1070    vs->tight->tight.offset = bytes;
1071
1072    bytes = tight_compress_data(vs, stream, bytes,
1073                                level, Z_FILTERED);
1074    return (bytes >= 0);
1075}
1076
1077static int send_palette_rect(VncState *vs, int x, int y,
1078                             int w, int h, VncPalette *palette)
1079{
1080    int stream = 2;
1081    int level = tight_conf[vs->tight->compression].idx_zlib_level;
1082    int colors;
1083    ssize_t bytes;
1084
1085#ifdef CONFIG_VNC_PNG
1086    if (tight_can_send_png_rect(vs, w, h)) {
1087        return send_png_rect(vs, x, y, w, h, palette);
1088    }
1089#endif
1090
1091    colors = palette_size(palette);
1092
1093    vnc_write_u8(vs, (stream | VNC_TIGHT_EXPLICIT_FILTER) << 4);
1094    vnc_write_u8(vs, VNC_TIGHT_FILTER_PALETTE);
1095    vnc_write_u8(vs, colors - 1);
1096
1097    switch (vs->client_pf.bytes_per_pixel) {
1098    case 4:
1099    {
1100        size_t old_offset, offset;
1101        uint32_t header[palette_size(palette)];
1102        struct palette_cb_priv priv = { vs, (uint8_t *)header };
1103
1104        old_offset = vs->output.offset;
1105        palette_iter(palette, write_palette, &priv);
1106        vnc_write(vs, header, sizeof(header));
1107
1108        if (vs->tight->pixel24) {
1109            tight_pack24(vs, vs->output.buffer + old_offset, colors, &offset);
1110            vs->output.offset = old_offset + offset;
1111        }
1112
1113        tight_encode_indexed_rect32(vs->tight->tight.buffer, w * h, palette);
1114        break;
1115    }
1116    case 2:
1117    {
1118        uint16_t header[palette_size(palette)];
1119        struct palette_cb_priv priv = { vs, (uint8_t *)header };
1120
1121        palette_iter(palette, write_palette, &priv);
1122        vnc_write(vs, header, sizeof(header));
1123        tight_encode_indexed_rect16(vs->tight->tight.buffer, w * h, palette);
1124        break;
1125    }
1126    default:
1127        return -1; /* No palette for 8bits colors */
1128        break;
1129    }
1130    bytes = w * h;
1131    vs->tight->tight.offset = bytes;
1132
1133    bytes = tight_compress_data(vs, stream, bytes,
1134                                level, Z_DEFAULT_STRATEGY);
1135    return (bytes >= 0);
1136}
1137
1138/*
1139 * JPEG compression stuff.
1140 */
1141#ifdef CONFIG_VNC_JPEG
1142/*
1143 * Destination manager implementation for JPEG library.
1144 */
1145
1146/* This is called once per encoding */
1147static void jpeg_init_destination(j_compress_ptr cinfo)
1148{
1149    VncState *vs = cinfo->client_data;
1150    Buffer *buffer = &vs->tight->jpeg;
1151
1152    cinfo->dest->next_output_byte = (JOCTET *)buffer->buffer + buffer->offset;
1153    cinfo->dest->free_in_buffer = (size_t)(buffer->capacity - buffer->offset);
1154}
1155
1156/* This is called when we ran out of buffer (shouldn't happen!) */
1157static boolean jpeg_empty_output_buffer(j_compress_ptr cinfo)
1158{
1159    VncState *vs = cinfo->client_data;
1160    Buffer *buffer = &vs->tight->jpeg;
1161
1162    buffer->offset = buffer->capacity;
1163    buffer_reserve(buffer, 2048);
1164    jpeg_init_destination(cinfo);
1165    return TRUE;
1166}
1167
1168/* This is called when we are done processing data */
1169static void jpeg_term_destination(j_compress_ptr cinfo)
1170{
1171    VncState *vs = cinfo->client_data;
1172    Buffer *buffer = &vs->tight->jpeg;
1173
1174    buffer->offset = buffer->capacity - cinfo->dest->free_in_buffer;
1175}
1176
1177static int send_jpeg_rect(VncState *vs, int x, int y, int w, int h, int quality)
1178{
1179    struct jpeg_compress_struct cinfo;
1180    struct jpeg_error_mgr jerr;
1181    struct jpeg_destination_mgr manager;
1182    pixman_image_t *linebuf;
1183    JSAMPROW row[1];
1184    uint8_t *buf;
1185    int dy;
1186
1187    if (surface_bytes_per_pixel(vs->vd->ds) == 1) {
1188        return send_full_color_rect(vs, x, y, w, h);
1189    }
1190
1191    buffer_reserve(&vs->tight->jpeg, 2048);
1192
1193    cinfo.err = jpeg_std_error(&jerr);
1194    jpeg_create_compress(&cinfo);
1195
1196    cinfo.client_data = vs;
1197    cinfo.image_width = w;
1198    cinfo.image_height = h;
1199    cinfo.input_components = 3;
1200    cinfo.in_color_space = JCS_RGB;
1201
1202    jpeg_set_defaults(&cinfo);
1203    jpeg_set_quality(&cinfo, quality, true);
1204
1205    manager.init_destination = jpeg_init_destination;
1206    manager.empty_output_buffer = jpeg_empty_output_buffer;
1207    manager.term_destination = jpeg_term_destination;
1208    cinfo.dest = &manager;
1209
1210    jpeg_start_compress(&cinfo, true);
1211
1212    linebuf = qemu_pixman_linebuf_create(PIXMAN_BE_r8g8b8, w);
1213    buf = (uint8_t *)pixman_image_get_data(linebuf);
1214    row[0] = buf;
1215    for (dy = 0; dy < h; dy++) {
1216        qemu_pixman_linebuf_fill(linebuf, vs->vd->server, w, x, y + dy);
1217        jpeg_write_scanlines(&cinfo, row, 1);
1218    }
1219    qemu_pixman_image_unref(linebuf);
1220
1221    jpeg_finish_compress(&cinfo);
1222    jpeg_destroy_compress(&cinfo);
1223
1224    vnc_write_u8(vs, VNC_TIGHT_JPEG << 4);
1225
1226    tight_send_compact_size(vs, vs->tight->jpeg.offset);
1227    vnc_write(vs, vs->tight->jpeg.buffer, vs->tight->jpeg.offset);
1228    buffer_reset(&vs->tight->jpeg);
1229
1230    return 1;
1231}
1232#endif /* CONFIG_VNC_JPEG */
1233
1234/*
1235 * PNG compression stuff.
1236 */
1237#ifdef CONFIG_VNC_PNG
1238static void write_png_palette(int idx, uint32_t pix, void *opaque)
1239{
1240    struct palette_cb_priv *priv = opaque;
1241    VncState *vs = priv->vs;
1242    png_colorp color = &priv->png_palette[idx];
1243
1244    if (vs->tight->pixel24)
1245    {
1246        color->red = (pix >> vs->client_pf.rshift) & vs->client_pf.rmax;
1247        color->green = (pix >> vs->client_pf.gshift) & vs->client_pf.gmax;
1248        color->blue = (pix >> vs->client_pf.bshift) & vs->client_pf.bmax;
1249    }
1250    else
1251    {
1252        int red, green, blue;
1253
1254        red = (pix >> vs->client_pf.rshift) & vs->client_pf.rmax;
1255        green = (pix >> vs->client_pf.gshift) & vs->client_pf.gmax;
1256        blue = (pix >> vs->client_pf.bshift) & vs->client_pf.bmax;
1257        color->red = ((red * 255 + vs->client_pf.rmax / 2) /
1258                      vs->client_pf.rmax);
1259        color->green = ((green * 255 + vs->client_pf.gmax / 2) /
1260                        vs->client_pf.gmax);
1261        color->blue = ((blue * 255 + vs->client_pf.bmax / 2) /
1262                       vs->client_pf.bmax);
1263    }
1264}
1265
1266static void png_write_data(png_structp png_ptr, png_bytep data,
1267                           png_size_t length)
1268{
1269    VncState *vs = png_get_io_ptr(png_ptr);
1270
1271    buffer_reserve(&vs->tight->png, vs->tight->png.offset + length);
1272    memcpy(vs->tight->png.buffer + vs->tight->png.offset, data, length);
1273
1274    vs->tight->png.offset += length;
1275}
1276
1277static void png_flush_data(png_structp png_ptr)
1278{
1279}
1280
1281static void *vnc_png_malloc(png_structp png_ptr, png_size_t size)
1282{
1283    return g_malloc(size);
1284}
1285
1286static void vnc_png_free(png_structp png_ptr, png_voidp ptr)
1287{
1288    g_free(ptr);
1289}
1290
1291static int send_png_rect(VncState *vs, int x, int y, int w, int h,
1292                         VncPalette *palette)
1293{
1294    png_byte color_type;
1295    png_structp png_ptr;
1296    png_infop info_ptr;
1297    png_colorp png_palette = NULL;
1298    pixman_image_t *linebuf;
1299    int level = tight_png_conf[vs->tight->compression].png_zlib_level;
1300    int filters = tight_png_conf[vs->tight->compression].png_filters;
1301    uint8_t *buf;
1302    int dy;
1303
1304    png_ptr = png_create_write_struct_2(PNG_LIBPNG_VER_STRING, NULL, NULL, NULL,
1305                                        NULL, vnc_png_malloc, vnc_png_free);
1306
1307    if (png_ptr == NULL)
1308        return -1;
1309
1310    info_ptr = png_create_info_struct(png_ptr);
1311
1312    if (info_ptr == NULL) {
1313        png_destroy_write_struct(&png_ptr, NULL);
1314        return -1;
1315    }
1316
1317    png_set_write_fn(png_ptr, (void *) vs, png_write_data, png_flush_data);
1318    png_set_compression_level(png_ptr, level);
1319    png_set_filter(png_ptr, PNG_FILTER_TYPE_DEFAULT, filters);
1320
1321    if (palette) {
1322        color_type = PNG_COLOR_TYPE_PALETTE;
1323    } else {
1324        color_type = PNG_COLOR_TYPE_RGB;
1325    }
1326
1327    png_set_IHDR(png_ptr, info_ptr, w, h,
1328                 8, color_type, PNG_INTERLACE_NONE,
1329                 PNG_COMPRESSION_TYPE_DEFAULT, PNG_FILTER_TYPE_DEFAULT);
1330
1331    if (color_type == PNG_COLOR_TYPE_PALETTE) {
1332        struct palette_cb_priv priv;
1333
1334        png_palette = png_malloc(png_ptr, sizeof(*png_palette) *
1335                                 palette_size(palette));
1336
1337        priv.vs = vs;
1338        priv.png_palette = png_palette;
1339        palette_iter(palette, write_png_palette, &priv);
1340
1341        png_set_PLTE(png_ptr, info_ptr, png_palette, palette_size(palette));
1342
1343        if (vs->client_pf.bytes_per_pixel == 4) {
1344            tight_encode_indexed_rect32(vs->tight->tight.buffer, w * h,
1345                                        palette);
1346        } else {
1347            tight_encode_indexed_rect16(vs->tight->tight.buffer, w * h,
1348                                        palette);
1349        }
1350    }
1351
1352    png_write_info(png_ptr, info_ptr);
1353
1354    buffer_reserve(&vs->tight->png, 2048);
1355    linebuf = qemu_pixman_linebuf_create(PIXMAN_BE_r8g8b8, w);
1356    buf = (uint8_t *)pixman_image_get_data(linebuf);
1357    for (dy = 0; dy < h; dy++)
1358    {
1359        if (color_type == PNG_COLOR_TYPE_PALETTE) {
1360            memcpy(buf, vs->tight->tight.buffer + (dy * w), w);
1361        } else {
1362            qemu_pixman_linebuf_fill(linebuf, vs->vd->server, w, x, y + dy);
1363        }
1364        png_write_row(png_ptr, buf);
1365    }
1366    qemu_pixman_image_unref(linebuf);
1367
1368    png_write_end(png_ptr, NULL);
1369
1370    if (color_type == PNG_COLOR_TYPE_PALETTE) {
1371        png_free(png_ptr, png_palette);
1372    }
1373
1374    png_destroy_write_struct(&png_ptr, &info_ptr);
1375
1376    vnc_write_u8(vs, VNC_TIGHT_PNG << 4);
1377
1378    tight_send_compact_size(vs, vs->tight->png.offset);
1379    vnc_write(vs, vs->tight->png.buffer, vs->tight->png.offset);
1380    buffer_reset(&vs->tight->png);
1381    return 1;
1382}
1383#endif /* CONFIG_VNC_PNG */
1384
1385static void vnc_tight_start(VncState *vs)
1386{
1387    buffer_reset(&vs->tight->tight);
1388
1389    // make the output buffer be the zlib buffer, so we can compress it later
1390    vs->tight->tmp = vs->output;
1391    vs->output = vs->tight->tight;
1392}
1393
1394static void vnc_tight_stop(VncState *vs)
1395{
1396    // switch back to normal output/zlib buffers
1397    vs->tight->tight = vs->output;
1398    vs->output = vs->tight->tmp;
1399}
1400
1401static int send_sub_rect_nojpeg(VncState *vs, int x, int y, int w, int h,
1402                                int bg, int fg, int colors, VncPalette *palette)
1403{
1404    int ret;
1405
1406    if (colors == 0) {
1407        if (tight_detect_smooth_image(vs, w, h)) {
1408            ret = send_gradient_rect(vs, x, y, w, h);
1409        } else {
1410            ret = send_full_color_rect(vs, x, y, w, h);
1411        }
1412    } else if (colors == 1) {
1413        ret = send_solid_rect(vs);
1414    } else if (colors == 2) {
1415        ret = send_mono_rect(vs, x, y, w, h, bg, fg);
1416    } else if (colors <= 256) {
1417        ret = send_palette_rect(vs, x, y, w, h, palette);
1418    } else {
1419        ret = 0;
1420    }
1421    return ret;
1422}
1423
1424#ifdef CONFIG_VNC_JPEG
1425static int send_sub_rect_jpeg(VncState *vs, int x, int y, int w, int h,
1426                              int bg, int fg, int colors,
1427                              VncPalette *palette, bool force)
1428{
1429    int ret;
1430
1431    if (colors == 0) {
1432        if (force || (tight_jpeg_conf[vs->tight->quality].jpeg_full &&
1433                      tight_detect_smooth_image(vs, w, h))) {
1434            int quality = tight_conf[vs->tight->quality].jpeg_quality;
1435
1436            ret = send_jpeg_rect(vs, x, y, w, h, quality);
1437        } else {
1438            ret = send_full_color_rect(vs, x, y, w, h);
1439        }
1440    } else if (colors == 1) {
1441        ret = send_solid_rect(vs);
1442    } else if (colors == 2) {
1443        ret = send_mono_rect(vs, x, y, w, h, bg, fg);
1444    } else if (colors <= 256) {
1445        if (force || (colors > 96 &&
1446                      tight_jpeg_conf[vs->tight->quality].jpeg_idx &&
1447                      tight_detect_smooth_image(vs, w, h))) {
1448            int quality = tight_conf[vs->tight->quality].jpeg_quality;
1449
1450            ret = send_jpeg_rect(vs, x, y, w, h, quality);
1451        } else {
1452            ret = send_palette_rect(vs, x, y, w, h, palette);
1453        }
1454    } else {
1455        ret = 0;
1456    }
1457    return ret;
1458}
1459#endif
1460
1461static __thread VncPalette *color_count_palette;
1462static __thread Notifier vnc_tight_cleanup_notifier;
1463
1464static void vnc_tight_cleanup(Notifier *n, void *value)
1465{
1466    g_free(color_count_palette);
1467    color_count_palette = NULL;
1468}
1469
1470static int send_sub_rect(VncState *vs, int x, int y, int w, int h)
1471{
1472    uint32_t bg = 0, fg = 0;
1473    int colors;
1474    int ret = 0;
1475#ifdef CONFIG_VNC_JPEG
1476    bool force_jpeg = false;
1477    bool allow_jpeg = true;
1478#endif
1479
1480    if (!color_count_palette) {
1481        color_count_palette = g_malloc(sizeof(VncPalette));
1482        vnc_tight_cleanup_notifier.notify = vnc_tight_cleanup;
1483        qemu_thread_atexit_add(&vnc_tight_cleanup_notifier);
1484    }
1485
1486    vnc_framebuffer_update(vs, x, y, w, h, vs->tight->type);
1487
1488    vnc_tight_start(vs);
1489    vnc_raw_send_framebuffer_update(vs, x, y, w, h);
1490    vnc_tight_stop(vs);
1491
1492#ifdef CONFIG_VNC_JPEG
1493    if (!vs->vd->non_adaptive && vs->tight->quality != (uint8_t)-1) {
1494        double freq = vnc_update_freq(vs, x, y, w, h);
1495
1496        if (freq < tight_jpeg_conf[vs->tight->quality].jpeg_freq_min) {
1497            allow_jpeg = false;
1498        }
1499        if (freq >= tight_jpeg_conf[vs->tight->quality].jpeg_freq_threshold) {
1500            force_jpeg = true;
1501            vnc_sent_lossy_rect(vs, x, y, w, h);
1502        }
1503    }
1504#endif
1505
1506    colors = tight_fill_palette(vs, x, y, w * h, &bg, &fg, color_count_palette);
1507
1508#ifdef CONFIG_VNC_JPEG
1509    if (allow_jpeg && vs->tight->quality != (uint8_t)-1) {
1510        ret = send_sub_rect_jpeg(vs, x, y, w, h, bg, fg, colors,
1511                                 color_count_palette, force_jpeg);
1512    } else {
1513        ret = send_sub_rect_nojpeg(vs, x, y, w, h, bg, fg, colors,
1514                                   color_count_palette);
1515    }
1516#else
1517    ret = send_sub_rect_nojpeg(vs, x, y, w, h, bg, fg, colors,
1518                               color_count_palette);
1519#endif
1520
1521    return ret;
1522}
1523
1524static int send_sub_rect_solid(VncState *vs, int x, int y, int w, int h)
1525{
1526    vnc_framebuffer_update(vs, x, y, w, h, vs->tight->type);
1527
1528    vnc_tight_start(vs);
1529    vnc_raw_send_framebuffer_update(vs, x, y, w, h);
1530    vnc_tight_stop(vs);
1531
1532    return send_solid_rect(vs);
1533}
1534
1535static int send_rect_simple(VncState *vs, int x, int y, int w, int h,
1536                            bool split)
1537{
1538    int max_size, max_width;
1539    int max_sub_width, max_sub_height;
1540    int dx, dy;
1541    int rw, rh;
1542    int n = 0;
1543
1544    max_size = tight_conf[vs->tight->compression].max_rect_size;
1545    max_width = tight_conf[vs->tight->compression].max_rect_width;
1546
1547    if (split && (w > max_width || w * h > max_size)) {
1548        max_sub_width = (w > max_width) ? max_width : w;
1549        max_sub_height = max_size / max_sub_width;
1550
1551        for (dy = 0; dy < h; dy += max_sub_height) {
1552            for (dx = 0; dx < w; dx += max_width) {
1553                rw = MIN(max_sub_width, w - dx);
1554                rh = MIN(max_sub_height, h - dy);
1555                n += send_sub_rect(vs, x+dx, y+dy, rw, rh);
1556            }
1557        }
1558    } else {
1559        n += send_sub_rect(vs, x, y, w, h);
1560    }
1561
1562    return n;
1563}
1564
1565static int find_large_solid_color_rect(VncState *vs, int x, int y,
1566                                       int w, int h, int max_rows)
1567{
1568    int dx, dy, dw, dh;
1569    int n = 0;
1570
1571    /* Try to find large solid-color areas and send them separately. */
1572
1573    for (dy = y; dy < y + h; dy += VNC_TIGHT_MAX_SPLIT_TILE_SIZE) {
1574
1575        /* If a rectangle becomes too large, send its upper part now. */
1576
1577        if (dy - y >= max_rows) {
1578            n += send_rect_simple(vs, x, y, w, max_rows, true);
1579            y += max_rows;
1580            h -= max_rows;
1581        }
1582
1583        dh = MIN(VNC_TIGHT_MAX_SPLIT_TILE_SIZE, (y + h - dy));
1584
1585        for (dx = x; dx < x + w; dx += VNC_TIGHT_MAX_SPLIT_TILE_SIZE) {
1586            uint32_t color_value;
1587            int x_best, y_best, w_best, h_best;
1588
1589            dw = MIN(VNC_TIGHT_MAX_SPLIT_TILE_SIZE, (x + w - dx));
1590
1591            if (!check_solid_tile(vs, dx, dy, dw, dh, &color_value, false)) {
1592                continue ;
1593            }
1594
1595            /* Get dimensions of solid-color area. */
1596
1597            find_best_solid_area(vs, dx, dy, w - (dx - x), h - (dy - y),
1598                                 color_value, &w_best, &h_best);
1599
1600            /* Make sure a solid rectangle is large enough
1601               (or the whole rectangle is of the same color). */
1602
1603            if (w_best * h_best != w * h &&
1604                w_best * h_best < VNC_TIGHT_MIN_SOLID_SUBRECT_SIZE) {
1605                continue;
1606            }
1607
1608            /* Try to extend solid rectangle to maximum size. */
1609
1610            x_best = dx; y_best = dy;
1611            extend_solid_area(vs, x, y, w, h, color_value,
1612                              &x_best, &y_best, &w_best, &h_best);
1613
1614            /* Send rectangles at top and left to solid-color area. */
1615
1616            if (y_best != y) {
1617                n += send_rect_simple(vs, x, y, w, y_best-y, true);
1618            }
1619            if (x_best != x) {
1620                n += tight_send_framebuffer_update(vs, x, y_best,
1621                                                   x_best-x, h_best);
1622            }
1623
1624            /* Send solid-color rectangle. */
1625            n += send_sub_rect_solid(vs, x_best, y_best, w_best, h_best);
1626
1627            /* Send remaining rectangles (at right and bottom). */
1628
1629            if (x_best + w_best != x + w) {
1630                n += tight_send_framebuffer_update(vs, x_best+w_best,
1631                                                   y_best,
1632                                                   w-(x_best-x)-w_best,
1633                                                   h_best);
1634            }
1635            if (y_best + h_best != y + h) {
1636                n += tight_send_framebuffer_update(vs, x, y_best+h_best,
1637                                                   w, h-(y_best-y)-h_best);
1638            }
1639
1640            /* Return after all recursive calls are done. */
1641            return n;
1642        }
1643    }
1644    return n + send_rect_simple(vs, x, y, w, h, true);
1645}
1646
1647static int tight_send_framebuffer_update(VncState *vs, int x, int y,
1648                                         int w, int h)
1649{
1650    int max_rows;
1651
1652    if (vs->client_pf.bytes_per_pixel == 4 && vs->client_pf.rmax == 0xFF &&
1653        vs->client_pf.bmax == 0xFF && vs->client_pf.gmax == 0xFF) {
1654        vs->tight->pixel24 = true;
1655    } else {
1656        vs->tight->pixel24 = false;
1657    }
1658
1659#ifdef CONFIG_VNC_JPEG
1660    if (vs->tight->quality != (uint8_t)-1) {
1661        double freq = vnc_update_freq(vs, x, y, w, h);
1662
1663        if (freq > tight_jpeg_conf[vs->tight->quality].jpeg_freq_threshold) {
1664            return send_rect_simple(vs, x, y, w, h, false);
1665        }
1666    }
1667#endif
1668
1669    if (w * h < VNC_TIGHT_MIN_SPLIT_RECT_SIZE) {
1670        return send_rect_simple(vs, x, y, w, h, true);
1671    }
1672
1673    /* Calculate maximum number of rows in one non-solid rectangle. */
1674
1675    max_rows = tight_conf[vs->tight->compression].max_rect_size;
1676    max_rows /= MIN(tight_conf[vs->tight->compression].max_rect_width, w);
1677
1678    return find_large_solid_color_rect(vs, x, y, w, h, max_rows);
1679}
1680
1681int vnc_tight_send_framebuffer_update(VncState *vs, int x, int y,
1682                                      int w, int h)
1683{
1684    vs->tight->type = VNC_ENCODING_TIGHT;
1685    return tight_send_framebuffer_update(vs, x, y, w, h);
1686}
1687
1688int vnc_tight_png_send_framebuffer_update(VncState *vs, int x, int y,
1689                                          int w, int h)
1690{
1691    vs->tight->type = VNC_ENCODING_TIGHT_PNG;
1692    return tight_send_framebuffer_update(vs, x, y, w, h);
1693}
1694
1695void vnc_tight_clear(VncState *vs)
1696{
1697    int i;
1698    for (i = 0; i < ARRAY_SIZE(vs->tight->stream); i++) {
1699        if (vs->tight->stream[i].opaque) {
1700            deflateEnd(&vs->tight->stream[i]);
1701        }
1702    }
1703
1704    buffer_free(&vs->tight->tight);
1705    buffer_free(&vs->tight->zlib);
1706    buffer_free(&vs->tight->gradient);
1707#ifdef CONFIG_VNC_JPEG
1708    buffer_free(&vs->tight->jpeg);
1709#endif
1710#ifdef CONFIG_VNC_PNG
1711    buffer_free(&vs->tight->png);
1712#endif
1713}
1714