ui/vnc-enc-tight.c

   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 <[email protected]>
   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 "config-host.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 #include "qemu-common.h"
  35
  36 #ifdef CONFIG_VNC_PNG
  37 /* The following define is needed by pngconf.h. Otherwise it won't compile,
  38    because setjmp.h was already included by qemu-common.h. */
  39 #define PNG_SKIP_SETJMP_CHECK
  40 #include <png.h>
  41 #endif
  42 #ifdef CONFIG_VNC_JPEG
  43 #include <stdio.h>
  44 #include <jpeglib.h>
  45 #endif
  46
  47 #include "qemu/bswap.h"
  48 #include "qapi/qmp/qint.h"
  49 #include "vnc.h"
  50 #include "vnc-enc-tight.h"
  51 #include "vnc-palette.h"
  52
  53 /* Compression level stuff. The following array contains various
  54    encoder parameters for each of 10 compression levels (0..9).
  55    Last three parameters correspond to JPEG quality levels (0..9). */
  56
  57 static const struct {
  58     int max_rect_size, max_rect_width;
  59     int mono_min_rect_size, gradient_min_rect_size;
  60     int idx_zlib_level, mono_zlib_level, raw_zlib_level, gradient_zlib_level;
  61     int gradient_threshold, gradient_threshold24;
  62     int idx_max_colors_divisor;
  63     int jpeg_quality, jpeg_threshold, jpeg_threshold24;
  64 } tight_conf[] = {
  65     {   512,   32,   6, 65536, 0, 0, 0, 0,   0,   0,   4,  5, 10000, 23000 },
  66     {  2048,  128,   6, 65536, 1, 1, 1, 0,   0,   0,   8, 10,  8000, 18000 },
  67     {  6144,  256,   8, 65536, 3, 3, 2, 0,   0,   0,  24, 15,  6500, 15000 },
  68     { 10240, 1024,  12, 65536, 5, 5, 3, 0,   0,   0,  32, 25,  5000, 12000 },
  69     { 16384, 2048,  12, 65536, 6, 6, 4, 0,   0,   0,  32, 37,  4000, 10000 },
  70     { 32768, 2048,  12,  4096, 7, 7, 5, 4, 150, 380,  32, 50,  3000,  8000 },
  71     { 65536, 2048,  16,  4096, 7, 7, 6, 4, 170, 420,  48, 60,  2000,  5000 },
  72     { 65536, 2048,  16,  4096, 8, 8, 7, 5, 180, 450,  64, 70,  1000,  2500 },
  73     { 65536, 2048,  32,  8192, 9, 9, 8, 6, 190, 475,  64, 75,   500,  1200 },
  74     { 65536, 2048,  32,  8192, 9, 9, 9, 6, 200, 500,  96, 80,   200,   500 }
  75 };
  76
  77
  78 static int tight_send_framebuffer_update(VncState *vs, int x, int y,
  79                                          int w, int h);
  80
  81 #ifdef CONFIG_VNC_JPEG
  82 static const struct {
  83     double jpeg_freq_min;       /* Don't send JPEG if the freq is bellow */
  84     double jpeg_freq_threshold; /* Always send JPEG if the freq is above */
  85     int jpeg_idx;               /* Allow indexed JPEG */
  86     int jpeg_full;              /* Allow full color JPEG */
  87 } tight_jpeg_conf[] = {
  88     { 0,   8,  1, 1 },
  89     { 0,   8,  1, 1 },
  90     { 0,   8,  1, 1 },
  91     { 0,   8,  1, 1 },
  92     { 0,   10, 1, 1 },
  93     { 0.1, 10, 1, 1 },
  94     { 0.2, 10, 1, 1 },
  95     { 0.3, 12, 0, 0 },
  96     { 0.4, 14, 0, 0 },
  97     { 0.5, 16, 0, 0 },
  98 };
  99 #endif
 100
 101 #ifdef CONFIG_VNC_PNG
 102 static const struct {
 103     int png_zlib_level, png_filters;
 104 } tight_png_conf[] = {
 105     { 0, PNG_NO_FILTERS },
 106     { 1, PNG_NO_FILTERS },
 107     { 2, PNG_NO_FILTERS },
 108     { 3, PNG_NO_FILTERS },
 109     { 4, PNG_NO_FILTERS },
 110     { 5, PNG_ALL_FILTERS },
 111     { 6, PNG_ALL_FILTERS },
 112     { 7, PNG_ALL_FILTERS },
 113     { 8, PNG_ALL_FILTERS },
 114     { 9, PNG_ALL_FILTERS },
 115 };
 116
 117 static int send_png_rect(VncState *vs, int x, int y, int w, int h,
 118                          VncPalette *palette);
 119
 120 static bool tight_can_send_png_rect(VncState *vs, int w, int h)
 121 {
 122     if (vs->tight.type != VNC_ENCODING_TIGHT_PNG) {
 123         return false;
 124     }
 125
 126     if (surface_bytes_per_pixel(vs->vd->ds) == 1 ||
 127         vs->client_pf.bytes_per_pixel == 1) {
 128         return false;
 129     }
 130
 131     return true;
 132 }
 133 #endif
 134
 135 /*
 136  * Code to guess if given rectangle is suitable for smooth image
 137  * compression (by applying "gradient" filter or JPEG coder).
 138  */
 139
 140 static unsigned int
 141 tight_detect_smooth_image24(VncState *vs, int w, int h)
 142 {
 143     int off;
 144     int x, y, d, dx;
 145     unsigned int c;
 146     unsigned int stats[256];
 147     int pixels = 0;
 148     int pix, left[3];
 149     unsigned int errors;
 150     unsigned char *buf = vs->tight.tight.buffer;
 151
 152     /*
 153      * If client is big-endian, color samples begin from the second
 154      * byte (offset 1) of a 32-bit pixel value.
 155      */
 156     off = vs->client_be;
 157
 158     memset(stats, 0, sizeof (stats));
 159
 160     for (y = 0, x = 0; y < h && x < w;) {
 161         for (d = 0; d < h - y && d < w - x - VNC_TIGHT_DETECT_SUBROW_WIDTH;
 162              d++) {
 163             for (c = 0; c < 3; c++) {
 164                 left[c] = buf[((y+d)*w+x+d)*4+off+c] & 0xFF;
 165             }
 166             for (dx = 1; dx <= VNC_TIGHT_DETECT_SUBROW_WIDTH; dx++) {
 167                 for (c = 0; c < 3; c++) {
 168                     pix = buf[((y+d)*w+x+d+dx)*4+off+c] & 0xFF;
 169                     stats[abs(pix - left[c])]++;
 170                     left[c] = pix;
 171                 }
 172                 pixels++;
 173             }
 174         }
 175         if (w > h) {
 176             x += h;
 177             y = 0;
 178         } else {
 179             x = 0;
 180             y += w;
 181         }
 182     }
 183
 184     /* 95% smooth or more ... */
 185     if (stats[0] * 33 / pixels >= 95) {
 186         return 0;
 187     }
 188
 189     errors = 0;
 190     for (c = 1; c < 8; c++) {
 191         errors += stats[c] * (c * c);
 192         if (stats[c] == 0 || stats[c] > stats[c-1] * 2) {
 193             return 0;
 194         }
 195     }
 196     for (; c < 256; c++) {
 197         errors += stats[c] * (c * c);
 198     }
 199     errors /= (pixels * 3 - stats[0]);
 200
 201     return errors;
 202 }
 203
 204 #define DEFINE_DETECT_FUNCTION(bpp)                                     \
 205                                                                         \
 206     static unsigned int                                                 \
 207     tight_detect_smooth_image##bpp(VncState *vs, int w, int h) {        \
 208         bool endian;                                                    \
 209         uint##bpp##_t pix;                                              \
 210         int max[3], shift[3];                                           \
 211         int x, y, d, dx;                                                \
 212         unsigned int c;                                                 \
 213         unsigned int stats[256];                                        \
 214         int pixels = 0;                                                 \
 215         int sample, sum, left[3];                                       \
 216         unsigned int errors;                                            \
 217         unsigned char *buf = vs->tight.tight.buffer;                    \
 218                                                                         \
 219         endian = 0; /* FIXME: ((vs->clientds.flags & QEMU_BIG_ENDIAN_FLAG) != \
 220                       (vs->ds->surface->flags & QEMU_BIG_ENDIAN_FLAG)); */ \
 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                                                                         \
 271         if ((stats[0] + stats[1]) * 100 / pixels >= 90) {               \
 272             return 0;                                                   \
 273         }                                                               \
 274                                                                         \
 275         errors = 0;                                                     \
 276         for (c = 1; c < 8; c++) {                                       \
 277             errors += stats[c] * (c * c);                               \
 278             if (stats[c] == 0 || stats[c] > stats[c-1] * 2) {           \
 279                 return 0;                                               \
 280             }                                                           \
 281         }                                                               \
 282         for (; c < 256; c++) {                                          \
 283             errors += stats[c] * (c * c);                               \
 284         }                                                               \
 285         errors /= (pixels - stats[0]);                                  \
 286                                                                         \
 287         return errors;                                                  \
 288     }
 289
 290 DEFINE_DETECT_FUNCTION(16)
 291 DEFINE_DETECT_FUNCTION(32)
 292
 293 static int
 294 tight_detect_smooth_image(VncState *vs, int w, int h)
 295 {
 296     unsigned int errors;
 297     int compression = vs->tight.compression;
 298     int quality = vs->tight.quality;
 299
 300     if (!vs->vd->lossy) {
 301         return 0;
 302     }
 303
 304     if (surface_bytes_per_pixel(vs->vd->ds) == 1 ||
 305         vs->client_pf.bytes_per_pixel == 1 ||
 306         w < VNC_TIGHT_DETECT_MIN_WIDTH || h < VNC_TIGHT_DETECT_MIN_HEIGHT) {
 307         return 0;
 308     }
 309
 310     if (vs->tight.quality != (uint8_t)-1) {
 311         if (w * h < VNC_TIGHT_JPEG_MIN_RECT_SIZE) {
 312             return 0;
 313         }
 314     } else {
 315         if (w * h < tight_conf[compression].gradient_min_rect_size) {
 316             return 0;
 317         }
 318     }
 319
 320     if (vs->client_pf.bytes_per_pixel == 4) {
 321         if (vs->tight.pixel24) {
 322             errors = tight_detect_smooth_image24(vs, w, h);
 323             if (vs->tight.quality != (uint8_t)-1) {
 324                 return (errors < tight_conf[quality].jpeg_threshold24);
 325             }
 326             return (errors < tight_conf[compression].gradient_threshold24);
 327         } else {
 328             errors = tight_detect_smooth_image32(vs, w, h);
 329         }
 330     } else {
 331         errors = tight_detect_smooth_image16(vs, w, h);
 332     }
 333     if (quality != -1) {
 334         return (errors < tight_conf[quality].jpeg_threshold);
 335     }
 336     return (errors < tight_conf[compression].gradient_threshold);
 337 }
 338
 339 /*
 340  * Code to determine how many different colors used in rectangle.
 341  */
 342 #define DEFINE_FILL_PALETTE_FUNCTION(bpp)                               \
 343                                                                         \
 344     static int                                                          \
 345     tight_fill_palette##bpp(VncState *vs, int x, int y,                 \
 346                             int max, size_t count,                      \
 347                             uint32_t *bg, uint32_t *fg,                 \
 348                             VncPalette **palette) {                     \
 349         uint##bpp##_t *data;                                            \
 350         uint##bpp##_t c0, c1, ci;                                       \
 351         int i, n0, n1;                                                  \
 352                                                                         \
 353         data = (uint##bpp##_t *)vs->tight.tight.buffer;                 \
 354                                                                         \
 355         c0 = data[0];                                                   \
 356         i = 1;                                                          \
 357         while (i < count && data[i] == c0)                              \
 358             i++;                                                        \
 359         if (i >= count) {                                               \
 360             *bg = *fg = c0;                                             \
 361             return 1;                                                   \
 362         }                                                               \
 363                                                                         \
 364         if (max < 2) {                                                  \
 365             return 0;                                                   \
 366         }                                                               \
 367                                                                         \
 368         n0 = i;                                                         \
 369         c1 = data[i];                                                   \
 370         n1 = 0;                                                         \
 371         for (i++; i < count; i++) {                                     \
 372             ci = data[i];                                               \
 373             if (ci == c0) {                                             \
 374                 n0++;                                                   \
 375             } else if (ci == c1) {                                      \
 376                 n1++;                                                   \
 377             } else                                                      \
 378                 break;                                                  \
 379         }                                                               \
 380         if (i >= count) {                                               \
 381             if (n0 > n1) {                                              \
 382                 *bg = (uint32_t)c0;                                     \
 383                 *fg = (uint32_t)c1;                                     \
 384             } else {                                                    \
 385                 *bg = (uint32_t)c1;                                     \
 386                 *fg = (uint32_t)c0;                                     \
 387             }                                                           \
 388             return 2;                                                   \
 389         }                                                               \
 390                                                                         \
 391         if (max == 2) {                                                 \
 392             return 0;                                                   \
 393         }                                                               \
 394                                                                         \
 395         *palette = palette_new(max, bpp);                               \
 396         palette_put(*palette, c0);                                      \
 397         palette_put(*palette, c1);                                      \
 398         palette_put(*palette, ci);                                      \
 399                                                                         \
 400         for (i++; i < count; i++) {                                     \
 401             if (data[i] == ci) {                                        \
 402                 continue;                                               \
 403             } else {                                                    \
 404                 ci = data[i];                                           \
 405                 if (!palette_put(*palette, (uint32_t)ci)) {             \
 406                     return 0;                                           \
 407                 }                                                       \
 408             }                                                           \
 409         }                                                               \
 410                                                                         \
 411         return palette_size(*palette);                                  \
 412     }
 413
 414 DEFINE_FILL_PALETTE_FUNCTION(8)
 415 DEFINE_FILL_PALETTE_FUNCTION(16)
 416 DEFINE_FILL_PALETTE_FUNCTION(32)
 417
 418 static int tight_fill_palette(VncState *vs, int x, int y,
 419                               size_t count, uint32_t *bg, uint32_t *fg,
 420                               VncPalette **palette)
 421 {
 422     int max;
 423
 424     max = count / tight_conf[vs->tight.compression].idx_max_colors_divisor;
 425     if (max < 2 &&
 426         count >= tight_conf[vs->tight.compression].mono_min_rect_size) {
 427         max = 2;
 428     }
 429     if (max >= 256) {
 430         max = 256;
 431     }
 432
 433     switch (vs->client_pf.bytes_per_pixel) {
 434     case 4:
 435         return tight_fill_palette32(vs, x, y, max, count, bg, fg, palette);
 436     case 2:
 437         return tight_fill_palette16(vs, x, y, max, count, bg, fg, palette);
 438     default:
 439         max = 2;
 440         return tight_fill_palette8(vs, x, y, max, count, bg, fg, palette);
 441     }
 442     return 0;
 443 }
 444
 445 /*
 446  * Converting truecolor samples into palette indices.
 447  */
 448 #define DEFINE_IDX_ENCODE_FUNCTION(bpp)                                 \
 449                                                                         \
 450     static void                                                         \
 451     tight_encode_indexed_rect##bpp(uint8_t *buf, int count,             \
 452                                    VncPalette *palette) {               \
 453         uint##bpp##_t *src;                                             \
 454         uint##bpp##_t rgb;                                              \
 455         int i, rep;                                                     \
 456         uint8_t idx;                                                    \
 457                                                                         \
 458         src = (uint##bpp##_t *) buf;                                    \
 459                                                                         \
 460         for (i = 0; i < count; i++) {                                   \
 461                                                                         \
 462             rgb = *src++;                                               \
 463             rep = 0;                                                    \
 464             while (i < count && *src == rgb) {                          \
 465                 rep++, src++, i++;                                      \
 466             }                                                           \
 467             idx = palette_idx(palette, rgb);                            \
 468             /*                                                          \
 469              * Should never happen, but don't break everything          \
 470              * if it does, use the first color instead                  \
 471              */                                                         \
 472             if (idx == (uint8_t)-1) {                                   \
 473                 idx = 0;                                                \
 474             }                                                           \
 475             while (rep >= 0) {                                          \
 476                 *buf++ = idx;                                           \
 477                 rep--;                                                  \
 478             }                                                           \
 479         }                                                               \
 480     }
 481
 482 DEFINE_IDX_ENCODE_FUNCTION(16)
 483 DEFINE_IDX_ENCODE_FUNCTION(32)
 484
 485 #define DEFINE_MONO_ENCODE_FUNCTION(bpp)                                \
 486                                                                         \
 487     static void                                                         \
 488     tight_encode_mono_rect##bpp(uint8_t *buf, int w, int h,             \
 489                                 uint##bpp##_t bg, uint##bpp##_t fg) {   \
 490         uint##bpp##_t *ptr;                                             \
 491         unsigned int value, mask;                                       \
 492         int aligned_width;                                              \
 493         int x, y, bg_bits;                                              \
 494                                                                         \
 495         ptr = (uint##bpp##_t *) buf;                                    \
 496         aligned_width = w - w % 8;                                      \
 497                                                                         \
 498         for (y = 0; y < h; y++) {                                       \
 499             for (x = 0; x < aligned_width; x += 8) {                    \
 500                 for (bg_bits = 0; bg_bits < 8; bg_bits++) {             \
 501                     if (*ptr++ != bg) {                                 \
 502                         break;                                          \
 503                     }                                                   \
 504                 }                                                       \
 505                 if (bg_bits == 8) {                                     \
 506                     *buf++ = 0;                                         \
 507                     continue;                                           \
 508                 }                                                       \
 509                 mask = 0x80 >> bg_bits;                                 \
 510                 value = mask;                                           \
 511                 for (bg_bits++; bg_bits < 8; bg_bits++) {               \
 512                     mask >>= 1;                                         \
 513                     if (*ptr++ != bg) {                                 \
 514                         value |= mask;                                  \
 515                     }                                                   \
 516                 }                                                       \
 517                 *buf++ = (uint8_t)value;                                \
 518             }                                                           \
 519                                                                         \
 520             mask = 0x80;                                                \
 521             value = 0;                                                  \
 522             if (x >= w) {                                               \
 523                 continue;                                               \
 524             }                                                           \
 525                                                                         \
 526             for (; x < w; x++) {                                        \
 527                 if (*ptr++ != bg) {                                     \
 528                     value |= mask;                                      \
 529                 }                                                       \
 530                 mask >>= 1;                                             \
 531             }                                                           \
 532             *buf++ = (uint8_t)value;                                    \
 533         }                                                               \
 534     }
 535
 536 DEFINE_MONO_ENCODE_FUNCTION(8)
 537 DEFINE_MONO_ENCODE_FUNCTION(16)
 538 DEFINE_MONO_ENCODE_FUNCTION(32)
 539
 540 /*
 541  * ``Gradient'' filter for 24-bit color samples.
 542  * Should be called only when redMax, greenMax and blueMax are 255.
 543  * Color components assumed to be byte-aligned.
 544  */
 545
 546 static void
 547 tight_filter_gradient24(VncState *vs, uint8_t *buf, int w, int h)
 548 {
 549     uint32_t *buf32;
 550     uint32_t pix32;
 551     int shift[3];
 552     int *prev;
 553     int here[3], upper[3], left[3], upperleft[3];
 554     int prediction;
 555     int x, y, c;
 556
 557     buf32 = (uint32_t *)buf;
 558     memset(vs->tight.gradient.buffer, 0, w * 3 * sizeof(int));
 559
 560     if (1 /* FIXME: (vs->clientds.flags & QEMU_BIG_ENDIAN_FLAG) ==
 561              (vs->ds->surface->flags & QEMU_BIG_ENDIAN_FLAG) */) {
 562         shift[0] = vs->client_pf.rshift;
 563         shift[1] = vs->client_pf.gshift;
 564         shift[2] = vs->client_pf.bshift;
 565     } else {
 566         shift[0] = 24 - vs->client_pf.rshift;
 567         shift[1] = 24 - vs->client_pf.gshift;
 568         shift[2] = 24 - vs->client_pf.bshift;
 569     }
 570
 571     for (y = 0; y < h; y++) {
 572         for (c = 0; c < 3; c++) {
 573             upper[c] = 0;
 574             here[c] = 0;
 575         }
 576         prev = (int *)vs->tight.gradient.buffer;
 577         for (x = 0; x < w; x++) {
 578             pix32 = *buf32++;
 579             for (c = 0; c < 3; c++) {
 580                 upperleft[c] = upper[c];
 581                 left[c] = here[c];
 582                 upper[c] = *prev;
 583                 here[c] = (int)(pix32 >> shift[c] & 0xFF);
 584                 *prev++ = here[c];
 585
 586                 prediction = left[c] + upper[c] - upperleft[c];
 587                 if (prediction < 0) {
 588                     prediction = 0;
 589                 } else if (prediction > 0xFF) {
 590                     prediction = 0xFF;
 591                 }
 592                 *buf++ = (char)(here[c] - prediction);
 593             }
 594         }
 595     }
 596 }
 597
 598
 599 /*
 600  * ``Gradient'' filter for other color depths.
 601  */
 602
 603 #define DEFINE_GRADIENT_FILTER_FUNCTION(bpp)                            \
 604                                                                         \
 605     static void                                                         \
 606     tight_filter_gradient##bpp(VncState *vs, uint##bpp##_t *buf,        \
 607                                int w, int h) {                          \
 608         uint##bpp##_t pix, diff;                                        \
 609         bool endian;                                                    \
 610         int *prev;                                                      \
 611         int max[3], shift[3];                                           \
 612         int here[3], upper[3], left[3], upperleft[3];                   \
 613         int prediction;                                                 \
 614         int x, y, c;                                                    \
 615                                                                         \
 616         memset (vs->tight.gradient.buffer, 0, w * 3 * sizeof(int));     \
 617                                                                         \
 618         endian = 0; /* FIXME: ((vs->clientds.flags & QEMU_BIG_ENDIAN_FLAG) != \
 619                        (vs->ds->surface->flags & QEMU_BIG_ENDIAN_FLAG)); */ \
 620                                                                         \
 621         max[0] = vs->client_pf.rmax;                                    \
 622         max[1] = vs->client_pf.gmax;                                    \
 623         max[2] = vs->client_pf.bmax;                                    \
 624         shift[0] = vs->client_pf.rshift;                                \
 625         shift[1] = vs->client_pf.gshift;                                \
 626         shift[2] = vs->client_pf.bshift;                                \
 627                                                                         \
 628         for (y = 0; y < h; y++) {                                       \
 629             for (c = 0; c < 3; c++) {                                   \
 630                 upper[c] = 0;                                           \
 631                 here[c] = 0;                                            \
 632             }                                                           \
 633             prev = (int *)vs->tight.gradient.buffer;                    \
 634             for (x = 0; x < w; x++) {                                   \
 635                 pix = *buf;                                             \
 636                 if (endian) {                                           \
 637                     pix = bswap##bpp(pix);                              \
 638                 }                                                       \
 639                 diff = 0;                                               \
 640                 for (c = 0; c < 3; c++) {                               \
 641                     upperleft[c] = upper[c];                            \
 642                     left[c] = here[c];                                  \
 643                     upper[c] = *prev;                                   \
 644                     here[c] = (int)(pix >> shift[c] & max[c]);          \
 645                     *prev++ = here[c];                                  \
 646                                                                         \
 647                     prediction = left[c] + upper[c] - upperleft[c];     \
 648                     if (prediction < 0) {                               \
 649                         prediction = 0;                                 \
 650                     } else if (prediction > max[c]) {                   \
 651                         prediction = max[c];                            \
 652                     }                                                   \
 653                     diff |= ((here[c] - prediction) & max[c])           \
 654                         << shift[c];                                    \
 655                 }                                                       \
 656                 if (endian) {                                           \
 657                     diff = bswap##bpp(diff);                            \
 658                 }                                                       \
 659                 *buf++ = diff;                                          \
 660             }                                                           \
 661         }                                                               \
 662     }
 663
 664 DEFINE_GRADIENT_FILTER_FUNCTION(16)
 665 DEFINE_GRADIENT_FILTER_FUNCTION(32)
 666
 667 /*
 668  * Check if a rectangle is all of the same color. If needSameColor is
 669  * set to non-zero, then also check that its color equals to the
 670  * *colorPtr value. The result is 1 if the test is successful, and in
 671  * that case new color will be stored in *colorPtr.
 672  */
 673
 674 static bool
 675 check_solid_tile32(VncState *vs, int x, int y, int w, int h,
 676                    uint32_t *color, bool samecolor)
 677 {
 678     VncDisplay *vd = vs->vd;
 679     uint32_t *fbptr;
 680     uint32_t c;
 681     int dx, dy;
 682
 683     fbptr = vnc_server_fb_ptr(vd, x, y);
 684
 685     c = *fbptr;
 686     if (samecolor && (uint32_t)c != *color) {
 687         return false;
 688     }
 689
 690     for (dy = 0; dy < h; dy++) {
 691         for (dx = 0; dx < w; dx++) {
 692             if (c != fbptr[dx]) {
 693                 return false;
 694             }
 695         }
 696         fbptr = (uint32_t *)
 697             ((uint8_t *)fbptr + vnc_server_fb_stride(vd));
 698     }
 699
 700     *color = (uint32_t)c;
 701     return true;
 702 }
 703
 704 static bool check_solid_tile(VncState *vs, int x, int y, int w, int h,
 705                              uint32_t* color, bool samecolor)
 706 {
 707     switch (VNC_SERVER_FB_BYTES) {
 708     case 4:
 709         return check_solid_tile32(vs, x, y, w, h, color, samecolor);
 710     }
 711 }
 712
 713 static void find_best_solid_area(VncState *vs, int x, int y, int w, int h,
 714                                  uint32_t color, int *w_ptr, int *h_ptr)
 715 {
 716     int dx, dy, dw, dh;
 717     int w_prev;
 718     int w_best = 0, h_best = 0;
 719
 720     w_prev = w;
 721
 722     for (dy = y; dy < y + h; dy += VNC_TIGHT_MAX_SPLIT_TILE_SIZE) {
 723
 724         dh = MIN(VNC_TIGHT_MAX_SPLIT_TILE_SIZE, y + h - dy);
 725         dw = MIN(VNC_TIGHT_MAX_SPLIT_TILE_SIZE, w_prev);
 726
 727         if (!check_solid_tile(vs, x, dy, dw, dh, &color, true)) {
 728             break;
 729         }
 730
 731         for (dx = x + dw; dx < x + w_prev;) {
 732             dw = MIN(VNC_TIGHT_MAX_SPLIT_TILE_SIZE, x + w_prev - dx);
 733
 734             if (!check_solid_tile(vs, dx, dy, dw, dh, &color, true)) {
 735                 break;
 736             }
 737             dx += dw;
 738         }
 739
 740         w_prev = dx - x;
 741         if (w_prev * (dy + dh - y) > w_best * h_best) {
 742             w_best = w_prev;
 743             h_best = dy + dh - y;
 744         }
 745     }
 746
 747     *w_ptr = w_best;
 748     *h_ptr = h_best;
 749 }
 750
 751 static void extend_solid_area(VncState *vs, int x, int y, int w, int h,
 752                               uint32_t color, int *x_ptr, int *y_ptr,
 753                               int *w_ptr, int *h_ptr)
 754 {
 755     int cx, cy;
 756
 757     /* Try to extend the area upwards. */
 758     for ( cy = *y_ptr - 1;
 759           cy >= y && check_solid_tile(vs, *x_ptr, cy, *w_ptr, 1, &color, true);
 760           cy-- );
 761     *h_ptr += *y_ptr - (cy + 1);
 762     *y_ptr = cy + 1;
 763
 764     /* ... downwards. */
 765     for ( cy = *y_ptr + *h_ptr;
 766           cy < y + h &&
 767               check_solid_tile(vs, *x_ptr, cy, *w_ptr, 1, &color, true);
 768           cy++ );
 769     *h_ptr += cy - (*y_ptr + *h_ptr);
 770
 771     /* ... to the left. */
 772     for ( cx = *x_ptr - 1;
 773           cx >= x && check_solid_tile(vs, cx, *y_ptr, 1, *h_ptr, &color, true);
 774           cx-- );
 775     *w_ptr += *x_ptr - (cx + 1);
 776     *x_ptr = cx + 1;
 777
 778     /* ... to the right. */
 779     for ( cx = *x_ptr + *w_ptr;
 780           cx < x + w &&
 781               check_solid_tile(vs, cx, *y_ptr, 1, *h_ptr, &color, true);
 782           cx++ );
 783     *w_ptr += cx - (*x_ptr + *w_ptr);
 784 }
 785
 786 static int tight_init_stream(VncState *vs, int stream_id,
 787                              int level, int strategy)
 788 {
 789     z_streamp zstream = &vs->tight.stream[stream_id];
 790
 791     if (zstream->opaque == NULL) {
 792         int err;
 793
 794         VNC_DEBUG("VNC: TIGHT: initializing zlib stream %d\n", stream_id);
 795         VNC_DEBUG("VNC: TIGHT: opaque = %p | vs = %p\n", zstream->opaque, vs);
 796         zstream->zalloc = vnc_zlib_zalloc;
 797         zstream->zfree = vnc_zlib_zfree;
 798
 799         err = deflateInit2(zstream, level, Z_DEFLATED, MAX_WBITS,
 800                            MAX_MEM_LEVEL, strategy);
 801
 802         if (err != Z_OK) {
 803             fprintf(stderr, "VNC: error initializing zlib\n");
 804             return -1;
 805         }
 806
 807         vs->tight.levels[stream_id] = level;
 808         zstream->opaque = vs;
 809     }
 810
 811     if (vs->tight.levels[stream_id] != level) {
 812         if (deflateParams(zstream, level, strategy) != Z_OK) {
 813             return -1;
 814         }
 815         vs->tight.levels[stream_id] = level;
 816     }
 817     return 0;
 818 }
 819
 820 static void tight_send_compact_size(VncState *vs, size_t len)
 821 {
 822     int lpc = 0;
 823     int bytes = 0;
 824     char buf[3] = {0, 0, 0};
 825
 826     buf[bytes++] = len & 0x7F;
 827     if (len > 0x7F) {
 828         buf[bytes-1] |= 0x80;
 829         buf[bytes++] = (len >> 7) & 0x7F;
 830         if (len > 0x3FFF) {
 831             buf[bytes-1] |= 0x80;
 832             buf[bytes++] = (len >> 14) & 0xFF;
 833         }
 834     }
 835     for (lpc = 0; lpc < bytes; lpc++) {
 836         vnc_write_u8(vs, buf[lpc]);
 837     }
 838 }
 839
 840 static int tight_compress_data(VncState *vs, int stream_id, size_t bytes,
 841                                int level, int strategy)
 842 {
 843     z_streamp zstream = &vs->tight.stream[stream_id];
 844     int previous_out;
 845
 846     if (bytes < VNC_TIGHT_MIN_TO_COMPRESS) {
 847         vnc_write(vs, vs->tight.tight.buffer, vs->tight.tight.offset);
 848         return bytes;
 849     }
 850
 851     if (tight_init_stream(vs, stream_id, level, strategy)) {
 852         return -1;
 853     }
 854
 855     /* reserve memory in output buffer */
 856     buffer_reserve(&vs->tight.zlib, bytes + 64);
 857
 858     /* set pointers */
 859     zstream->next_in = vs->tight.tight.buffer;
 860     zstream->avail_in = vs->tight.tight.offset;
 861     zstream->next_out = vs->tight.zlib.buffer + vs->tight.zlib.offset;
 862     zstream->avail_out = vs->tight.zlib.capacity - vs->tight.zlib.offset;
 863     previous_out = zstream->avail_out;
 864     zstream->data_type = Z_BINARY;
 865
 866     /* start encoding */
 867     if (deflate(zstream, Z_SYNC_FLUSH) != Z_OK) {
 868         fprintf(stderr, "VNC: error during tight compression\n");
 869         return -1;
 870     }
 871
 872     vs->tight.zlib.offset = vs->tight.zlib.capacity - zstream->avail_out;
 873     /* ...how much data has actually been produced by deflate() */
 874     bytes = previous_out - zstream->avail_out;
 875
 876     tight_send_compact_size(vs, bytes);
 877     vnc_write(vs, vs->tight.zlib.buffer, bytes);
 878
 879     buffer_reset(&vs->tight.zlib);
 880
 881     return bytes;
 882 }
 883
 884 /*
 885  * Subencoding implementations.
 886  */
 887 static void tight_pack24(VncState *vs, uint8_t *buf, size_t count, size_t *ret)
 888 {
 889     uint32_t *buf32;
 890     uint32_t pix;
 891     int rshift, gshift, bshift;
 892
 893     buf32 = (uint32_t *)buf;
 894
 895     if (1 /* FIXME: (vs->clientds.flags & QEMU_BIG_ENDIAN_FLAG) ==
 896              (vs->ds->surface->flags & QEMU_BIG_ENDIAN_FLAG) */) {
 897         rshift = vs->client_pf.rshift;
 898         gshift = vs->client_pf.gshift;
 899         bshift = vs->client_pf.bshift;
 900     } else {
 901         rshift = 24 - vs->client_pf.rshift;
 902         gshift = 24 - vs->client_pf.gshift;
 903         bshift = 24 - vs->client_pf.bshift;
 904     }
 905
 906     if (ret) {
 907         *ret = count * 3;
 908     }
 909
 910     while (count--) {
 911         pix = *buf32++;
 912         *buf++ = (char)(pix >> rshift);
 913         *buf++ = (char)(pix >> gshift);
 914         *buf++ = (char)(pix >> bshift);
 915     }
 916 }
 917
 918 static int send_full_color_rect(VncState *vs, int x, int y, int w, int h)
 919 {
 920     int stream = 0;
 921     ssize_t bytes;
 922
 923 #ifdef CONFIG_VNC_PNG
 924     if (tight_can_send_png_rect(vs, w, h)) {
 925         return send_png_rect(vs, x, y, w, h, NULL);
 926     }
 927 #endif
 928
 929     vnc_write_u8(vs, stream << 4); /* no flushing, no filter */
 930
 931     if (vs->tight.pixel24) {
 932         tight_pack24(vs, vs->tight.tight.buffer, w * h, &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
 945 static 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
 962 static 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 = ((w + 7) / 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
1020 struct palette_cb_priv {
1021     VncState *vs;
1022     uint8_t *header;
1023 #ifdef CONFIG_VNC_PNG
1024     png_colorp png_palette;
1025 #endif
1026 };
1027
1028 static 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
1041 static 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
1077 static 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 */
1147 static 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!) */
1157 static 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 */
1169 static 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
1177 static 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
1238 static 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
1266 static 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
1277 static void png_flush_data(png_structp png_ptr)
1278 {
1279 }
1280
1281 static void *vnc_png_malloc(png_structp png_ptr, png_size_t size)
1282 {
1283     return g_malloc(size);
1284 }
1285
1286 static void vnc_png_free(png_structp png_ptr, png_voidp ptr)
1287 {
1288     g_free(ptr);
1289 }
1290
1291 static 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, palette);
1345         } else {
1346             tight_encode_indexed_rect16(vs->tight.tight.buffer, w * h, palette);
1347         }
1348     }
1349
1350     png_write_info(png_ptr, info_ptr);
1351
1352     buffer_reserve(&vs->tight.png, 2048);
1353     linebuf = qemu_pixman_linebuf_create(PIXMAN_BE_r8g8b8, w);
1354     buf = (uint8_t *)pixman_image_get_data(linebuf);
1355     for (dy = 0; dy < h; dy++)
1356     {
1357         if (color_type == PNG_COLOR_TYPE_PALETTE) {
1358             memcpy(buf, vs->tight.tight.buffer + (dy * w), w);
1359         } else {
1360             qemu_pixman_linebuf_fill(linebuf, vs->vd->server, w, x, y + dy);
1361         }
1362         png_write_row(png_ptr, buf);
1363     }
1364     qemu_pixman_image_unref(linebuf);
1365
1366     png_write_end(png_ptr, NULL);
1367
1368     if (color_type == PNG_COLOR_TYPE_PALETTE) {
1369         png_free(png_ptr, png_palette);
1370     }
1371
1372     png_destroy_write_struct(&png_ptr, &info_ptr);
1373
1374     vnc_write_u8(vs, VNC_TIGHT_PNG << 4);
1375
1376     tight_send_compact_size(vs, vs->tight.png.offset);
1377     vnc_write(vs, vs->tight.png.buffer, vs->tight.png.offset);
1378     buffer_reset(&vs->tight.png);
1379     return 1;
1380 }
1381 #endif /* CONFIG_VNC_PNG */
1382
1383 static void vnc_tight_start(VncState *vs)
1384 {
1385     buffer_reset(&vs->tight.tight);
1386
1387     // make the output buffer be the zlib buffer, so we can compress it later
1388     vs->tight.tmp = vs->output;
1389     vs->output = vs->tight.tight;
1390 }
1391
1392 static void vnc_tight_stop(VncState *vs)
1393 {
1394     // switch back to normal output/zlib buffers
1395     vs->tight.tight = vs->output;
1396     vs->output = vs->tight.tmp;
1397 }
1398
1399 static int send_sub_rect_nojpeg(VncState *vs, int x, int y, int w, int h,
1400                                 int bg, int fg, int colors, VncPalette *palette)
1401 {
1402     int ret;
1403
1404     if (colors == 0) {
1405         if (tight_detect_smooth_image(vs, w, h)) {
1406             ret = send_gradient_rect(vs, x, y, w, h);
1407         } else {
1408             ret = send_full_color_rect(vs, x, y, w, h);
1409         }
1410     } else if (colors == 1) {
1411         ret = send_solid_rect(vs);
1412     } else if (colors == 2) {
1413         ret = send_mono_rect(vs, x, y, w, h, bg, fg);
1414     } else if (colors <= 256) {
1415         ret = send_palette_rect(vs, x, y, w, h, palette);
1416     } else {
1417         ret = 0;
1418     }
1419     return ret;
1420 }
1421
1422 #ifdef CONFIG_VNC_JPEG
1423 static int send_sub_rect_jpeg(VncState *vs, int x, int y, int w, int h,
1424                               int bg, int fg, int colors,
1425                               VncPalette *palette, bool force)
1426 {
1427     int ret;
1428
1429     if (colors == 0) {
1430         if (force || (tight_jpeg_conf[vs->tight.quality].jpeg_full &&
1431                       tight_detect_smooth_image(vs, w, h))) {
1432             int quality = tight_conf[vs->tight.quality].jpeg_quality;
1433
1434             ret = send_jpeg_rect(vs, x, y, w, h, quality);
1435         } else {
1436             ret = send_full_color_rect(vs, x, y, w, h);
1437         }
1438     } else if (colors == 1) {
1439         ret = send_solid_rect(vs);
1440     } else if (colors == 2) {
1441         ret = send_mono_rect(vs, x, y, w, h, bg, fg);
1442     } else if (colors <= 256) {
1443         if (force || (colors > 96 &&
1444                       tight_jpeg_conf[vs->tight.quality].jpeg_idx &&
1445                       tight_detect_smooth_image(vs, w, h))) {
1446             int quality = tight_conf[vs->tight.quality].jpeg_quality;
1447
1448             ret = send_jpeg_rect(vs, x, y, w, h, quality);
1449         } else {
1450             ret = send_palette_rect(vs, x, y, w, h, palette);
1451         }
1452     } else {
1453         ret = 0;
1454     }
1455     return ret;
1456 }
1457 #endif
1458
1459 static int send_sub_rect(VncState *vs, int x, int y, int w, int h)
1460 {
1461     VncPalette *palette = NULL;
1462     uint32_t bg = 0, fg = 0;
1463     int colors;
1464     int ret = 0;
1465 #ifdef CONFIG_VNC_JPEG
1466     bool force_jpeg = false;
1467     bool allow_jpeg = true;
1468 #endif
1469
1470     vnc_framebuffer_update(vs, x, y, w, h, vs->tight.type);
1471
1472     vnc_tight_start(vs);
1473     vnc_raw_send_framebuffer_update(vs, x, y, w, h);
1474     vnc_tight_stop(vs);
1475
1476 #ifdef CONFIG_VNC_JPEG
1477     if (!vs->vd->non_adaptive && vs->tight.quality != (uint8_t)-1) {
1478         double freq = vnc_update_freq(vs, x, y, w, h);
1479
1480         if (freq < tight_jpeg_conf[vs->tight.quality].jpeg_freq_min) {
1481             allow_jpeg = false;
1482         }
1483         if (freq >= tight_jpeg_conf[vs->tight.quality].jpeg_freq_threshold) {
1484             force_jpeg = true;
1485             vnc_sent_lossy_rect(vs, x, y, w, h);
1486         }
1487     }
1488 #endif
1489
1490     colors = tight_fill_palette(vs, x, y, w * h, &fg, &bg, &palette);
1491
1492 #ifdef CONFIG_VNC_JPEG
1493     if (allow_jpeg && vs->tight.quality != (uint8_t)-1) {
1494         ret = send_sub_rect_jpeg(vs, x, y, w, h, bg, fg, colors, palette,
1495                                  force_jpeg);
1496     } else {
1497         ret = send_sub_rect_nojpeg(vs, x, y, w, h, bg, fg, colors, palette);
1498     }
1499 #else
1500     ret = send_sub_rect_nojpeg(vs, x, y, w, h, bg, fg, colors, palette);
1501 #endif
1502
1503     palette_destroy(palette);
1504     return ret;
1505 }
1506
1507 static int send_sub_rect_solid(VncState *vs, int x, int y, int w, int h)
1508 {
1509     vnc_framebuffer_update(vs, x, y, w, h, vs->tight.type);
1510
1511     vnc_tight_start(vs);
1512     vnc_raw_send_framebuffer_update(vs, x, y, w, h);
1513     vnc_tight_stop(vs);
1514
1515     return send_solid_rect(vs);
1516 }
1517
1518 static int send_rect_simple(VncState *vs, int x, int y, int w, int h,
1519                             bool split)
1520 {
1521     int max_size, max_width;
1522     int max_sub_width, max_sub_height;
1523     int dx, dy;
1524     int rw, rh;
1525     int n = 0;
1526
1527     max_size = tight_conf[vs->tight.compression].max_rect_size;
1528     max_width = tight_conf[vs->tight.compression].max_rect_width;
1529
1530     if (split && (w > max_width || w * h > max_size)) {
1531         max_sub_width = (w > max_width) ? max_width : w;
1532         max_sub_height = max_size / max_sub_width;
1533
1534         for (dy = 0; dy < h; dy += max_sub_height) {
1535             for (dx = 0; dx < w; dx += max_width) {
1536                 rw = MIN(max_sub_width, w - dx);
1537                 rh = MIN(max_sub_height, h - dy);
1538                 n += send_sub_rect(vs, x+dx, y+dy, rw, rh);
1539             }
1540         }
1541     } else {
1542         n += send_sub_rect(vs, x, y, w, h);
1543     }
1544
1545     return n;
1546 }
1547
1548 static int find_large_solid_color_rect(VncState *vs, int x, int y,
1549                                        int w, int h, int max_rows)
1550 {
1551     int dx, dy, dw, dh;
1552     int n = 0;
1553
1554     /* Try to find large solid-color areas and send them separately. */
1555
1556     for (dy = y; dy < y + h; dy += VNC_TIGHT_MAX_SPLIT_TILE_SIZE) {
1557
1558         /* If a rectangle becomes too large, send its upper part now. */
1559
1560         if (dy - y >= max_rows) {
1561             n += send_rect_simple(vs, x, y, w, max_rows, true);
1562             y += max_rows;
1563             h -= max_rows;
1564         }
1565
1566         dh = MIN(VNC_TIGHT_MAX_SPLIT_TILE_SIZE, (y + h - dy));
1567
1568         for (dx = x; dx < x + w; dx += VNC_TIGHT_MAX_SPLIT_TILE_SIZE) {
1569             uint32_t color_value;
1570             int x_best, y_best, w_best, h_best;
1571
1572             dw = MIN(VNC_TIGHT_MAX_SPLIT_TILE_SIZE, (x + w - dx));
1573
1574             if (!check_solid_tile(vs, dx, dy, dw, dh, &color_value, false)) {
1575                 continue ;
1576             }
1577
1578             /* Get dimensions of solid-color area. */
1579
1580             find_best_solid_area(vs, dx, dy, w - (dx - x), h - (dy - y),
1581                                  color_value, &w_best, &h_best);
1582
1583             /* Make sure a solid rectangle is large enough
1584                (or the whole rectangle is of the same color). */
1585
1586             if (w_best * h_best != w * h &&
1587                 w_best * h_best < VNC_TIGHT_MIN_SOLID_SUBRECT_SIZE) {
1588                 continue;
1589             }
1590
1591             /* Try to extend solid rectangle to maximum size. */
1592
1593             x_best = dx; y_best = dy;
1594             extend_solid_area(vs, x, y, w, h, color_value,
1595                               &x_best, &y_best, &w_best, &h_best);
1596
1597             /* Send rectangles at top and left to solid-color area. */
1598
1599             if (y_best != y) {
1600                 n += send_rect_simple(vs, x, y, w, y_best-y, true);
1601             }
1602             if (x_best != x) {
1603                 n += tight_send_framebuffer_update(vs, x, y_best,
1604                                                    x_best-x, h_best);
1605             }
1606
1607             /* Send solid-color rectangle. */
1608             n += send_sub_rect_solid(vs, x_best, y_best, w_best, h_best);
1609
1610             /* Send remaining rectangles (at right and bottom). */
1611
1612             if (x_best + w_best != x + w) {
1613                 n += tight_send_framebuffer_update(vs, x_best+w_best,
1614                                                    y_best,
1615                                                    w-(x_best-x)-w_best,
1616                                                    h_best);
1617             }
1618             if (y_best + h_best != y + h) {
1619                 n += tight_send_framebuffer_update(vs, x, y_best+h_best,
1620                                                    w, h-(y_best-y)-h_best);
1621             }
1622
1623             /* Return after all recursive calls are done. */
1624             return n;
1625         }
1626     }
1627     return n + send_rect_simple(vs, x, y, w, h, true);
1628 }
1629
1630 static int tight_send_framebuffer_update(VncState *vs, int x, int y,
1631                                          int w, int h)
1632 {
1633     int max_rows;
1634
1635     if (vs->client_pf.bytes_per_pixel == 4 && vs->client_pf.rmax == 0xFF &&
1636         vs->client_pf.bmax == 0xFF && vs->client_pf.gmax == 0xFF) {
1637         vs->tight.pixel24 = true;
1638     } else {
1639         vs->tight.pixel24 = false;
1640     }
1641
1642 #ifdef CONFIG_VNC_JPEG
1643     if (vs->tight.quality != (uint8_t)-1) {
1644         double freq = vnc_update_freq(vs, x, y, w, h);
1645
1646         if (freq > tight_jpeg_conf[vs->tight.quality].jpeg_freq_threshold) {
1647             return send_rect_simple(vs, x, y, w, h, false);
1648         }
1649     }
1650 #endif
1651
1652     if (w * h < VNC_TIGHT_MIN_SPLIT_RECT_SIZE) {
1653         return send_rect_simple(vs, x, y, w, h, true);
1654     }
1655
1656     /* Calculate maximum number of rows in one non-solid rectangle. */
1657
1658     max_rows = tight_conf[vs->tight.compression].max_rect_size;
1659     max_rows /= MIN(tight_conf[vs->tight.compression].max_rect_width, w);
1660
1661     return find_large_solid_color_rect(vs, x, y, w, h, max_rows);
1662 }
1663
1664 int vnc_tight_send_framebuffer_update(VncState *vs, int x, int y,
1665                                       int w, int h)
1666 {
1667     vs->tight.type = VNC_ENCODING_TIGHT;
1668     return tight_send_framebuffer_update(vs, x, y, w, h);
1669 }
1670
1671 int vnc_tight_png_send_framebuffer_update(VncState *vs, int x, int y,
1672                                           int w, int h)
1673 {
1674     vs->tight.type = VNC_ENCODING_TIGHT_PNG;
1675     return tight_send_framebuffer_update(vs, x, y, w, h);
1676 }
1677
1678 void vnc_tight_clear(VncState *vs)
1679 {
1680     int i;
1681     for (i=0; i<ARRAY_SIZE(vs->tight.stream); i++) {
1682         if (vs->tight.stream[i].opaque) {
1683             deflateEnd(&vs->tight.stream[i]);
1684         }
1685     }
1686
1687     buffer_free(&vs->tight.tight);
1688     buffer_free(&vs->tight.zlib);
1689     buffer_free(&vs->tight.gradient);
1690 #ifdef CONFIG_VNC_JPEG
1691     buffer_free(&vs->tight.jpeg);
1692 #endif
1693 #ifdef CONFIG_VNC_PNG
1694     buffer_free(&vs->tight.png);
1695 #endif
1696 }