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 "bswap.h"
  48 #include "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 (ds_get_bytes_per_pixel(vs->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 (ds_get_bytes_per_pixel(vs->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 (ds_get_bytes_per_pixel(vs->ds) == 1)
1188         return send_full_color_rect(vs, x, y, w, h);
1189
1190     buffer_reserve(&vs->tight.jpeg, 2048);
1191
1192     cinfo.err = jpeg_std_error(&jerr);
1193     jpeg_create_compress(&cinfo);
1194
1195     cinfo.client_data = vs;
1196     cinfo.image_width = w;
1197     cinfo.image_height = h;
1198     cinfo.input_components = 3;
1199     cinfo.in_color_space = JCS_RGB;
1200
1201     jpeg_set_defaults(&cinfo);
1202     jpeg_set_quality(&cinfo, quality, true);
1203
1204     manager.init_destination = jpeg_init_destination;
1205     manager.empty_output_buffer = jpeg_empty_output_buffer;
1206     manager.term_destination = jpeg_term_destination;
1207     cinfo.dest = &manager;
1208
1209     jpeg_start_compress(&cinfo, true);
1210
1211     linebuf = qemu_pixman_linebuf_create(PIXMAN_BE_r8g8b8, w);
1212     buf = (uint8_t *)pixman_image_get_data(linebuf);
1213     row[0] = buf;
1214     for (dy = 0; dy < h; dy++) {
1215         qemu_pixman_linebuf_fill(linebuf, vs->vd->server, w, dy);
1216         jpeg_write_scanlines(&cinfo, row, 1);
1217     }
1218     qemu_pixman_image_unref(linebuf);
1219
1220     jpeg_finish_compress(&cinfo);
1221     jpeg_destroy_compress(&cinfo);
1222
1223     vnc_write_u8(vs, VNC_TIGHT_JPEG << 4);
1224
1225     tight_send_compact_size(vs, vs->tight.jpeg.offset);
1226     vnc_write(vs, vs->tight.jpeg.buffer, vs->tight.jpeg.offset);
1227     buffer_reset(&vs->tight.jpeg);
1228
1229     return 1;
1230 }
1231 #endif /* CONFIG_VNC_JPEG */
1232
1233 /*
1234  * PNG compression stuff.
1235  */
1236 #ifdef CONFIG_VNC_PNG
1237 static void write_png_palette(int idx, uint32_t pix, void *opaque)
1238 {
1239     struct palette_cb_priv *priv = opaque;
1240     VncState *vs = priv->vs;
1241     png_colorp color = &priv->png_palette[idx];
1242
1243     if (vs->tight.pixel24)
1244     {
1245         color->red = (pix >> vs->client_pf.rshift) & vs->client_pf.rmax;
1246         color->green = (pix >> vs->client_pf.gshift) & vs->client_pf.gmax;
1247         color->blue = (pix >> vs->client_pf.bshift) & vs->client_pf.bmax;
1248     }
1249     else
1250     {
1251         int red, green, blue;
1252
1253         red = (pix >> vs->client_pf.rshift) & vs->client_pf.rmax;
1254         green = (pix >> vs->client_pf.gshift) & vs->client_pf.gmax;
1255         blue = (pix >> vs->client_pf.bshift) & vs->client_pf.bmax;
1256         color->red = ((red * 255 + vs->client_pf.rmax / 2) /
1257                       vs->client_pf.rmax);
1258         color->green = ((green * 255 + vs->client_pf.gmax / 2) /
1259                         vs->client_pf.gmax);
1260         color->blue = ((blue * 255 + vs->client_pf.bmax / 2) /
1261                        vs->client_pf.bmax);
1262     }
1263 }
1264
1265 static void png_write_data(png_structp png_ptr, png_bytep data,
1266                            png_size_t length)
1267 {
1268     VncState *vs = png_get_io_ptr(png_ptr);
1269
1270     buffer_reserve(&vs->tight.png, vs->tight.png.offset + length);
1271     memcpy(vs->tight.png.buffer + vs->tight.png.offset, data, length);
1272
1273     vs->tight.png.offset += length;
1274 }
1275
1276 static void png_flush_data(png_structp png_ptr)
1277 {
1278 }
1279
1280 static void *vnc_png_malloc(png_structp png_ptr, png_size_t size)
1281 {
1282     return g_malloc(size);
1283 }
1284
1285 static void vnc_png_free(png_structp png_ptr, png_voidp ptr)
1286 {
1287     g_free(ptr);
1288 }
1289
1290 static int send_png_rect(VncState *vs, int x, int y, int w, int h,
1291                          VncPalette *palette)
1292 {
1293     png_byte color_type;
1294     png_structp png_ptr;
1295     png_infop info_ptr;
1296     png_colorp png_palette = NULL;
1297     pixman_image_t *linebuf;
1298     int level = tight_png_conf[vs->tight.compression].png_zlib_level;
1299     int filters = tight_png_conf[vs->tight.compression].png_filters;
1300     uint8_t *buf;
1301     int dy;
1302
1303     png_ptr = png_create_write_struct_2(PNG_LIBPNG_VER_STRING, NULL, NULL, NULL,
1304                                         NULL, vnc_png_malloc, vnc_png_free);
1305
1306     if (png_ptr == NULL)
1307         return -1;
1308
1309     info_ptr = png_create_info_struct(png_ptr);
1310
1311     if (info_ptr == NULL) {
1312         png_destroy_write_struct(&png_ptr, NULL);
1313         return -1;
1314     }
1315
1316     png_set_write_fn(png_ptr, (void *) vs, png_write_data, png_flush_data);
1317     png_set_compression_level(png_ptr, level);
1318     png_set_filter(png_ptr, PNG_FILTER_TYPE_DEFAULT, filters);
1319
1320     if (palette) {
1321         color_type = PNG_COLOR_TYPE_PALETTE;
1322     } else {
1323         color_type = PNG_COLOR_TYPE_RGB;
1324     }
1325
1326     png_set_IHDR(png_ptr, info_ptr, w, h,
1327                  8, color_type, PNG_INTERLACE_NONE,
1328                  PNG_COMPRESSION_TYPE_DEFAULT, PNG_FILTER_TYPE_DEFAULT);
1329
1330     if (color_type == PNG_COLOR_TYPE_PALETTE) {
1331         struct palette_cb_priv priv;
1332
1333         png_palette = png_malloc(png_ptr, sizeof(*png_palette) *
1334                                  palette_size(palette));
1335
1336         priv.vs = vs;
1337         priv.png_palette = png_palette;
1338         palette_iter(palette, write_png_palette, &priv);
1339
1340         png_set_PLTE(png_ptr, info_ptr, png_palette, palette_size(palette));
1341
1342         if (vs->client_pf.bytes_per_pixel == 4) {
1343             tight_encode_indexed_rect32(vs->tight.tight.buffer, w * h, palette);
1344         } else {
1345             tight_encode_indexed_rect16(vs->tight.tight.buffer, w * h, palette);
1346         }
1347     }
1348
1349     png_write_info(png_ptr, info_ptr);
1350
1351     buffer_reserve(&vs->tight.png, 2048);
1352     linebuf = qemu_pixman_linebuf_create(PIXMAN_BE_r8g8b8, w);
1353     buf = (uint8_t *)pixman_image_get_data(linebuf);
1354     for (dy = 0; dy < h; dy++)
1355     {
1356         if (color_type == PNG_COLOR_TYPE_PALETTE) {
1357             memcpy(buf, vs->tight.tight.buffer + (dy * w), w);
1358         } else {
1359             qemu_pixman_linebuf_fill(linebuf, vs->vd->server, w, dy);
1360         }
1361         png_write_row(png_ptr, buf);
1362     }
1363     qemu_pixman_image_unref(linebuf);
1364
1365     png_write_end(png_ptr, NULL);
1366
1367     if (color_type == PNG_COLOR_TYPE_PALETTE) {
1368         png_free(png_ptr, png_palette);
1369     }
1370
1371     png_destroy_write_struct(&png_ptr, &info_ptr);
1372
1373     vnc_write_u8(vs, VNC_TIGHT_PNG << 4);
1374
1375     tight_send_compact_size(vs, vs->tight.png.offset);
1376     vnc_write(vs, vs->tight.png.buffer, vs->tight.png.offset);
1377     buffer_reset(&vs->tight.png);
1378     return 1;
1379 }
1380 #endif /* CONFIG_VNC_PNG */
1381
1382 static void vnc_tight_start(VncState *vs)
1383 {
1384     buffer_reset(&vs->tight.tight);
1385
1386     // make the output buffer be the zlib buffer, so we can compress it later
1387     vs->tight.tmp = vs->output;
1388     vs->output = vs->tight.tight;
1389 }
1390
1391 static void vnc_tight_stop(VncState *vs)
1392 {
1393     // switch back to normal output/zlib buffers
1394     vs->tight.tight = vs->output;
1395     vs->output = vs->tight.tmp;
1396 }
1397
1398 static int send_sub_rect_nojpeg(VncState *vs, int x, int y, int w, int h,
1399                                 int bg, int fg, int colors, VncPalette *palette)
1400 {
1401     int ret;
1402
1403     if (colors == 0) {
1404         if (tight_detect_smooth_image(vs, w, h)) {
1405             ret = send_gradient_rect(vs, x, y, w, h);
1406         } else {
1407             ret = send_full_color_rect(vs, x, y, w, h);
1408         }
1409     } else if (colors == 1) {
1410         ret = send_solid_rect(vs);
1411     } else if (colors == 2) {
1412         ret = send_mono_rect(vs, x, y, w, h, bg, fg);
1413     } else if (colors <= 256) {
1414         ret = send_palette_rect(vs, x, y, w, h, palette);
1415     } else {
1416         ret = 0;
1417     }
1418     return ret;
1419 }
1420
1421 #ifdef CONFIG_VNC_JPEG
1422 static int send_sub_rect_jpeg(VncState *vs, int x, int y, int w, int h,
1423                               int bg, int fg, int colors,
1424                               VncPalette *palette, bool force)
1425 {
1426     int ret;
1427
1428     if (colors == 0) {
1429         if (force || (tight_jpeg_conf[vs->tight.quality].jpeg_full &&
1430                       tight_detect_smooth_image(vs, w, h))) {
1431             int quality = tight_conf[vs->tight.quality].jpeg_quality;
1432
1433             ret = send_jpeg_rect(vs, x, y, w, h, quality);
1434         } else {
1435             ret = send_full_color_rect(vs, x, y, w, h);
1436         }
1437     } else if (colors == 1) {
1438         ret = send_solid_rect(vs);
1439     } else if (colors == 2) {
1440         ret = send_mono_rect(vs, x, y, w, h, bg, fg);
1441     } else if (colors <= 256) {
1442         if (force || (colors > 96 &&
1443                       tight_jpeg_conf[vs->tight.quality].jpeg_idx &&
1444                       tight_detect_smooth_image(vs, w, h))) {
1445             int quality = tight_conf[vs->tight.quality].jpeg_quality;
1446
1447             ret = send_jpeg_rect(vs, x, y, w, h, quality);
1448         } else {
1449             ret = send_palette_rect(vs, x, y, w, h, palette);
1450         }
1451     } else {
1452         ret = 0;
1453     }
1454     return ret;
1455 }
1456 #endif
1457
1458 static int send_sub_rect(VncState *vs, int x, int y, int w, int h)
1459 {
1460     VncPalette *palette = NULL;
1461     uint32_t bg = 0, fg = 0;
1462     int colors;
1463     int ret = 0;
1464 #ifdef CONFIG_VNC_JPEG
1465     bool force_jpeg = false;
1466     bool allow_jpeg = true;
1467 #endif
1468
1469     vnc_framebuffer_update(vs, x, y, w, h, vs->tight.type);
1470
1471     vnc_tight_start(vs);
1472     vnc_raw_send_framebuffer_update(vs, x, y, w, h);
1473     vnc_tight_stop(vs);
1474
1475 #ifdef CONFIG_VNC_JPEG
1476     if (!vs->vd->non_adaptive && vs->tight.quality != (uint8_t)-1) {
1477         double freq = vnc_update_freq(vs, x, y, w, h);
1478
1479         if (freq < tight_jpeg_conf[vs->tight.quality].jpeg_freq_min) {
1480             allow_jpeg = false;
1481         }
1482         if (freq >= tight_jpeg_conf[vs->tight.quality].jpeg_freq_threshold) {
1483             force_jpeg = true;
1484             vnc_sent_lossy_rect(vs, x, y, w, h);
1485         }
1486     }
1487 #endif
1488
1489     colors = tight_fill_palette(vs, x, y, w * h, &fg, &bg, &palette);
1490
1491 #ifdef CONFIG_VNC_JPEG
1492     if (allow_jpeg && vs->tight.quality != (uint8_t)-1) {
1493         ret = send_sub_rect_jpeg(vs, x, y, w, h, bg, fg, colors, palette,
1494                                  force_jpeg);
1495     } else {
1496         ret = send_sub_rect_nojpeg(vs, x, y, w, h, bg, fg, colors, palette);
1497     }
1498 #else
1499     ret = send_sub_rect_nojpeg(vs, x, y, w, h, bg, fg, colors, palette);
1500 #endif
1501
1502     palette_destroy(palette);
1503     return ret;
1504 }
1505
1506 static int send_sub_rect_solid(VncState *vs, int x, int y, int w, int h)
1507 {
1508     vnc_framebuffer_update(vs, x, y, w, h, vs->tight.type);
1509
1510     vnc_tight_start(vs);
1511     vnc_raw_send_framebuffer_update(vs, x, y, w, h);
1512     vnc_tight_stop(vs);
1513
1514     return send_solid_rect(vs);
1515 }
1516
1517 static int send_rect_simple(VncState *vs, int x, int y, int w, int h,
1518                             bool split)
1519 {
1520     int max_size, max_width;
1521     int max_sub_width, max_sub_height;
1522     int dx, dy;
1523     int rw, rh;
1524     int n = 0;
1525
1526     max_size = tight_conf[vs->tight.compression].max_rect_size;
1527     max_width = tight_conf[vs->tight.compression].max_rect_width;
1528
1529     if (split && (w > max_width || w * h > max_size)) {
1530         max_sub_width = (w > max_width) ? max_width : w;
1531         max_sub_height = max_size / max_sub_width;
1532
1533         for (dy = 0; dy < h; dy += max_sub_height) {
1534             for (dx = 0; dx < w; dx += max_width) {
1535                 rw = MIN(max_sub_width, w - dx);
1536                 rh = MIN(max_sub_height, h - dy);
1537                 n += send_sub_rect(vs, x+dx, y+dy, rw, rh);
1538             }
1539         }
1540     } else {
1541         n += send_sub_rect(vs, x, y, w, h);
1542     }
1543
1544     return n;
1545 }
1546
1547 static int find_large_solid_color_rect(VncState *vs, int x, int y,
1548                                        int w, int h, int max_rows)
1549 {
1550     int dx, dy, dw, dh;
1551     int n = 0;
1552
1553     /* Try to find large solid-color areas and send them separately. */
1554
1555     for (dy = y; dy < y + h; dy += VNC_TIGHT_MAX_SPLIT_TILE_SIZE) {
1556
1557         /* If a rectangle becomes too large, send its upper part now. */
1558
1559         if (dy - y >= max_rows) {
1560             n += send_rect_simple(vs, x, y, w, max_rows, true);
1561             y += max_rows;
1562             h -= max_rows;
1563         }
1564
1565         dh = MIN(VNC_TIGHT_MAX_SPLIT_TILE_SIZE, (y + h - dy));
1566
1567         for (dx = x; dx < x + w; dx += VNC_TIGHT_MAX_SPLIT_TILE_SIZE) {
1568             uint32_t color_value;
1569             int x_best, y_best, w_best, h_best;
1570
1571             dw = MIN(VNC_TIGHT_MAX_SPLIT_TILE_SIZE, (x + w - dx));
1572
1573             if (!check_solid_tile(vs, dx, dy, dw, dh, &color_value, false)) {
1574                 continue ;
1575             }
1576
1577             /* Get dimensions of solid-color area. */
1578
1579             find_best_solid_area(vs, dx, dy, w - (dx - x), h - (dy - y),
1580                                  color_value, &w_best, &h_best);
1581
1582             /* Make sure a solid rectangle is large enough
1583                (or the whole rectangle is of the same color). */
1584
1585             if (w_best * h_best != w * h &&
1586                 w_best * h_best < VNC_TIGHT_MIN_SOLID_SUBRECT_SIZE) {
1587                 continue;
1588             }
1589
1590             /* Try to extend solid rectangle to maximum size. */
1591
1592             x_best = dx; y_best = dy;
1593             extend_solid_area(vs, x, y, w, h, color_value,
1594                               &x_best, &y_best, &w_best, &h_best);
1595
1596             /* Send rectangles at top and left to solid-color area. */
1597
1598             if (y_best != y) {
1599                 n += send_rect_simple(vs, x, y, w, y_best-y, true);
1600             }
1601             if (x_best != x) {
1602                 n += tight_send_framebuffer_update(vs, x, y_best,
1603                                                    x_best-x, h_best);
1604             }
1605
1606             /* Send solid-color rectangle. */
1607             n += send_sub_rect_solid(vs, x_best, y_best, w_best, h_best);
1608
1609             /* Send remaining rectangles (at right and bottom). */
1610
1611             if (x_best + w_best != x + w) {
1612                 n += tight_send_framebuffer_update(vs, x_best+w_best,
1613                                                    y_best,
1614                                                    w-(x_best-x)-w_best,
1615                                                    h_best);
1616             }
1617             if (y_best + h_best != y + h) {
1618                 n += tight_send_framebuffer_update(vs, x, y_best+h_best,
1619                                                    w, h-(y_best-y)-h_best);
1620             }
1621
1622             /* Return after all recursive calls are done. */
1623             return n;
1624         }
1625     }
1626     return n + send_rect_simple(vs, x, y, w, h, true);
1627 }
1628
1629 static int tight_send_framebuffer_update(VncState *vs, int x, int y,
1630                                          int w, int h)
1631 {
1632     int max_rows;
1633
1634     if (vs->client_pf.bytes_per_pixel == 4 && vs->client_pf.rmax == 0xFF &&
1635         vs->client_pf.bmax == 0xFF && vs->client_pf.gmax == 0xFF) {
1636         vs->tight.pixel24 = true;
1637     } else {
1638         vs->tight.pixel24 = false;
1639     }
1640
1641 #ifdef CONFIG_VNC_JPEG
1642     if (vs->tight.quality != (uint8_t)-1) {
1643         double freq = vnc_update_freq(vs, x, y, w, h);
1644
1645         if (freq > tight_jpeg_conf[vs->tight.quality].jpeg_freq_threshold) {
1646             return send_rect_simple(vs, x, y, w, h, false);
1647         }
1648     }
1649 #endif
1650
1651     if (w * h < VNC_TIGHT_MIN_SPLIT_RECT_SIZE) {
1652         return send_rect_simple(vs, x, y, w, h, true);
1653     }
1654
1655     /* Calculate maximum number of rows in one non-solid rectangle. */
1656
1657     max_rows = tight_conf[vs->tight.compression].max_rect_size;
1658     max_rows /= MIN(tight_conf[vs->tight.compression].max_rect_width, w);
1659
1660     return find_large_solid_color_rect(vs, x, y, w, h, max_rows);
1661 }
1662
1663 int vnc_tight_send_framebuffer_update(VncState *vs, int x, int y,
1664                                       int w, int h)
1665 {
1666     vs->tight.type = VNC_ENCODING_TIGHT;
1667     return tight_send_framebuffer_update(vs, x, y, w, h);
1668 }
1669
1670 int vnc_tight_png_send_framebuffer_update(VncState *vs, int x, int y,
1671                                           int w, int h)
1672 {
1673     vs->tight.type = VNC_ENCODING_TIGHT_PNG;
1674     return tight_send_framebuffer_update(vs, x, y, w, h);
1675 }
1676
1677 void vnc_tight_clear(VncState *vs)
1678 {
1679     int i;
1680     for (i=0; i<ARRAY_SIZE(vs->tight.stream); i++) {
1681         if (vs->tight.stream[i].opaque) {
1682             deflateEnd(&vs->tight.stream[i]);
1683         }
1684     }
1685
1686     buffer_free(&vs->tight.tight);
1687     buffer_free(&vs->tight.zlib);
1688     buffer_free(&vs->tight.gradient);
1689 #ifdef CONFIG_VNC_JPEG
1690     buffer_free(&vs->tight.jpeg);
1691 #endif
1692 #ifdef CONFIG_VNC_PNG
1693     buffer_free(&vs->tight.png);
1694 #endif
1695 }