Pileus Git - ~andy/gtk/blob - gdk/broadway/broadway.c

   1 #include <glib.h>
   2 #include <string.h>
   3 #include <stdlib.h>
   4 #include <stdio.h>
   5 #include <assert.h>
   6 #include <errno.h>
   7 #include <zlib.h>
   8
   9 #include "broadway.h"
  10
  11 /************************************************************************
  12  *                Base64 functions                                      *
  13  ************************************************************************/
  14
  15 static const char base64_alphabet[] =
  16         "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
  17
  18 #if 0
  19 static void
  20 base64_uint8 (guint8 v, char *c)
  21 {
  22   c[0] = base64_alphabet[(v >> 0) & 0x3f];
  23   c[1] = base64_alphabet[(v >> 6) & 0x3];
  24 }
  25 #endif
  26
  27 static void
  28 base64_uint16 (guint32 v, char *c)
  29 {
  30   c[0] = base64_alphabet[(v >> 0) & 0x3f];
  31   c[1] = base64_alphabet[(v >> 6) & 0x3f];
  32   c[2] = base64_alphabet[(v >> 12) & 0xf];
  33 }
  34
  35 #if 0
  36 static void
  37 base64_uint24 (guint32 v, char *c)
  38 {
  39   c[0] = base64_alphabet[(v >> 0) & 0x3f];
  40   c[1] = base64_alphabet[(v >> 6) & 0x3f];
  41   c[2] = base64_alphabet[(v >> 12) & 0x3f];
  42   c[3] = base64_alphabet[(v >> 18) & 0x3f];
  43 }
  44 #endif
  45
  46 static void
  47 base64_uint32 (guint32 v, char *c)
  48 {
  49   c[0] = base64_alphabet[(v >> 0) & 0x3f];
  50   c[1] = base64_alphabet[(v >> 6) & 0x3f];
  51   c[2] = base64_alphabet[(v >> 12) & 0x3f];
  52   c[3] = base64_alphabet[(v >> 18) & 0x3f];
  53   c[4] = base64_alphabet[(v >> 24) & 0x3f];
  54   c[5] = base64_alphabet[(v >> 30) & 0x2];
  55 }
  56
  57 /************************************************************************
  58  *  conversion of raw image data to uncompressed png data: uris         *
  59  ************************************************************************/
  60
  61 /* Table of CRCs of all 8-bit messages. */
  62 static unsigned long crc_table[256];
  63
  64 /* Flag: has the table been computed? Initially false. */
  65 static int crc_table_computed = 0;
  66
  67 /* Make the table for a fast CRC. */
  68 static void
  69 make_crc_table(void)
  70 {
  71   unsigned long c;
  72   int n, k;
  73
  74   for (n = 0; n < 256; n++) {
  75     c = (unsigned long) n;
  76     for (k = 0; k < 8; k++) {
  77       if (c & 1)
  78         c = 0xedb88320L ^ (c >> 1);
  79       else
  80         c = c >> 1;
  81     }
  82     crc_table[n] = c;
  83   }
  84   crc_table_computed = 1;
  85 }
  86
  87 static unsigned long
  88 update_crc(unsigned long crc, unsigned char *buf, int len)
  89 {
  90   unsigned long c = crc;
  91   int n;
  92
  93   if (!crc_table_computed)
  94     make_crc_table();
  95   for (n = 0; n < len; n++) {
  96     c = crc_table[(c ^ buf[n]) & 0xff] ^ (c >> 8);
  97   }
  98   return c;
  99 }
 100
 101 static unsigned long
 102 crc(unsigned char *buf, int len)
 103 {
 104   return update_crc(0xffffffffL, buf, len) ^ 0xffffffffL;
 105 }
 106
 107 #define BASE 65521 /* largest prime smaller than 65536 */
 108 static unsigned long
 109 update_adler32(unsigned long adler, unsigned char *buf, int len)
 110 {
 111   unsigned long s1 = adler & 0xffff;
 112   unsigned long s2 = (adler >> 16) & 0xffff;
 113   int n;
 114
 115   for (n = 0; n < len; n++) {
 116     s1 = (s1 + buf[n]) % BASE;
 117     s2 = (s2 + s1)     % BASE;
 118   }
 119   return (s2 << 16) + s1;
 120 }
 121
 122 static char *
 123 to_png_rgb (int w, int h, int byte_stride, guint32 *data)
 124 {
 125   guchar header[] = {137, 80, 78, 71, 13, 10, 26, 10};
 126   guchar ihdr[13+12] = {0, 0, 0, 13, 'I', 'H', 'D', 'R',
 127                         /* w: */ 0, 0, 0, 0, /* h: */ 0,0,0,0,
 128                         /* bpp: */ 8, /* color type: */ 2,
 129                         0, 0, 0};
 130   guchar idat_start[8] = { /* len: */0, 0, 0, 0,   'I', 'D', 'A', 'T' };
 131   guchar iend[12] = {0, 0, 0, 0, 'I', 'E', 'N', 'D', 0xae, 0x42, 0x60, 0x82};
 132   gsize data_size, row_size;
 133   char row_header[6];
 134   guint8 *png, *p, *p_row, *p_idat;
 135   guint32 *row;
 136   unsigned long adler;
 137   guint32 pixel;
 138   gsize png_size;
 139   int x, y;
 140   char *url, *url_base64;
 141   int state = 0, outlen;
 142   int save = 0;
 143
 144   *(guint32 *)&ihdr[8] = GUINT32_TO_BE(w);
 145   *(guint32 *)&ihdr[12] = GUINT32_TO_BE(h);
 146   *(guint32 *)&ihdr[21] = GUINT32_TO_BE(crc(&ihdr[4], 13 + 4));
 147
 148   row_size = 1 + w * 3;
 149   row_header[0] = 0;
 150   row_header[1] = row_size & 0xff;
 151   row_header[2] = (row_size >> 8) & 0xff;
 152   row_header[3] = ~row_header[1];
 153   row_header[4] = ~row_header[2];
 154   row_header[5] = 0;
 155
 156   data_size = 2 + (6 + w * 3) * h + 4;
 157
 158   *(guint32 *)&idat_start[0] = GUINT32_TO_BE(data_size);
 159
 160   png_size = sizeof(header) + sizeof(ihdr) + 12 + data_size + sizeof(iend);
 161   png = g_malloc (png_size);
 162
 163   p = png;
 164   memcpy (p, header, sizeof(header));
 165   p += sizeof(header);
 166   memcpy (p, ihdr, sizeof(ihdr));
 167   p += sizeof(ihdr);
 168   memcpy (p, idat_start, sizeof(idat_start));
 169   p += sizeof(idat_start);
 170
 171   /* IDAT data:
 172
 173      zlib header:  0x78, 0x01 ,
 174      h * scanline: row_header[] + width * r,g,b
 175      checksum: adler32
 176   */
 177
 178   p_idat = p - 4;
 179
 180   /* zlib header */
 181   *p++ = 0x78;
 182   *p++ = 0x01;
 183
 184   adler = 1;
 185
 186   /* scanline data */
 187   for (y = 0; y < h; y++) {
 188     if (y == h - 1)
 189       row_header[0] = 1; /* final block */
 190     memcpy (p, row_header, sizeof(row_header));
 191     p += sizeof(row_header);
 192     p_row = p - 1;
 193     row = data;
 194     data += byte_stride / 4;
 195     for (x = 0; x < w; x++) {
 196       pixel = *row++;
 197       *p++ = (pixel >> 16) & 0xff; /* red */
 198       *p++ = (pixel >> 8) & 0xff; /* green */
 199       *p++ = (pixel >> 0) & 0xff; /* blue */
 200     }
 201     adler = update_adler32(adler, p_row, p - p_row);
 202   }
 203
 204   /* adler32 */
 205   *(guint32 *)p = GUINT32_TO_BE(adler);
 206   p += 4;
 207   *(guint32 *)p = GUINT32_TO_BE(crc(p_idat, p - p_idat));
 208   p += 4;
 209
 210   memcpy (p, iend, sizeof(iend));
 211   p += sizeof(iend);
 212
 213   assert(p - png == png_size);
 214
 215   url = g_malloc (strlen("data:image/png;base64,") +
 216                    ((png_size / 3 + 1) * 4 + 4) + 1);
 217   strcpy (url, "data:image/png;base64,");
 218
 219   url_base64 = url + strlen("data:image/png;base64,");
 220   outlen = g_base64_encode_step (png, png_size, FALSE, url_base64, &state, &save);
 221   outlen += g_base64_encode_close (FALSE, url_base64 + outlen, &state, &save);
 222   url_base64[outlen] = 0;
 223
 224   free (png);
 225
 226   return url;
 227 }
 228
 229 static char *
 230 to_png_rgba (int w, int h, int byte_stride, guint32 *data)
 231 {
 232   guchar header[] = {137, 80, 78, 71, 13, 10, 26, 10};
 233   guchar ihdr[13+12] = {0, 0, 0, 13, 'I', 'H', 'D', 'R',
 234                         /* w: */ 0, 0, 0, 0, /* h: */ 0,0,0,0,
 235                         /* bpp: */ 8, /* color type: */ 6,
 236                         0, 0, 0};
 237   guchar idat_start[8] = { /* len: */0, 0, 0, 0,   'I', 'D', 'A', 'T' };
 238   guchar iend[12] = {0, 0, 0, 0, 'I', 'E', 'N', 'D', 0xae, 0x42, 0x60, 0x82};
 239   gsize data_size, row_size;
 240   char row_header[6];
 241   guint8 *png, *p, *p_row, *p_idat;
 242   guint32 *row;
 243   unsigned long adler;
 244   guint32 pixel;
 245   gsize png_size;
 246   int x, y;
 247   char *url, *url_base64;
 248   int state = 0, outlen;
 249   int save = 0;
 250
 251   *(guint32 *)&ihdr[8] = GUINT32_TO_BE(w);
 252   *(guint32 *)&ihdr[12] = GUINT32_TO_BE(h);
 253   *(guint32 *)&ihdr[21] = GUINT32_TO_BE(crc(&ihdr[4], 13 + 4));
 254
 255   row_size = 1 + w * 4;
 256   row_header[0] = 0;
 257   row_header[1] = row_size & 0xff;
 258   row_header[2] = (row_size >> 8) & 0xff;
 259   row_header[3] = ~row_header[1];
 260   row_header[4] = ~row_header[2];
 261   row_header[5] = 0;
 262
 263   data_size = 2 + (6 + w * 4) * h + 4;
 264
 265   *(guint32 *)&idat_start[0] = GUINT32_TO_BE(data_size);
 266
 267   png_size = sizeof(header) + sizeof(ihdr) + 12 + data_size + sizeof(iend);
 268   png = g_malloc (png_size);
 269
 270   p = png;
 271   memcpy (p, header, sizeof(header));
 272   p += sizeof(header);
 273   memcpy (p, ihdr, sizeof(ihdr));
 274   p += sizeof(ihdr);
 275   memcpy (p, idat_start, sizeof(idat_start));
 276   p += sizeof(idat_start);
 277
 278   /* IDAT data:
 279
 280      zlib header:  0x78, 0x01 ,
 281      h * scanline: row_header[] + width * r,g,b,a
 282      checksum: adler32
 283   */
 284
 285   p_idat = p - 4;
 286
 287   /* zlib header */
 288   *p++ = 0x78;
 289   *p++ = 0x01;
 290
 291   adler = 1;
 292
 293   /* scanline data */
 294   for (y = 0; y < h; y++) {
 295     if (y == h - 1)
 296       row_header[0] = 1; /* final block */
 297     memcpy (p, row_header, sizeof(row_header));
 298     p += sizeof(row_header);
 299     p_row = p - 1;
 300     row = data;
 301     data += byte_stride / 4;
 302     for (x = 0; x < w; x++) {
 303       pixel = *row++;
 304       *p++ = (pixel >> 16) & 0xff; /* red */
 305       *p++ = (pixel >> 8) & 0xff; /* green */
 306       *p++ = (pixel >> 0) & 0xff; /* blue */
 307       *p++ = (pixel >> 24) & 0xff; /* alpha */
 308     }
 309     adler = update_adler32(adler, p_row, p - p_row);
 310   }
 311
 312   /* adler32 */
 313   *(guint32 *)p = GUINT32_TO_BE(adler);
 314   p += 4;
 315   *(guint32 *)p = GUINT32_TO_BE(crc(p_idat, p - p_idat));
 316   p += 4;
 317
 318   memcpy (p, iend, sizeof(iend));
 319   p += sizeof(iend);
 320
 321   assert(p - png == png_size);
 322
 323   url = g_malloc (strlen("data:image/png;base64,") +
 324                    ((png_size / 3 + 1) * 4 + 4) + 1);
 325   strcpy (url, "data:image/png;base64,");
 326
 327   url_base64 = url + strlen("data:image/png;base64,");
 328   outlen = g_base64_encode_step (png, png_size, FALSE, url_base64, &state, &save);
 329   outlen += g_base64_encode_close (FALSE, url_base64 + outlen, &state, &save);
 330   url_base64[outlen] = 0;
 331
 332   free (png);
 333
 334   return url;
 335 }
 336
 337 #if 0
 338 static char *
 339 to_png_a (int w, int h, int byte_stride, guint8 *data)
 340 {
 341   guchar header[] = {137, 80, 78, 71, 13, 10, 26, 10};
 342   guchar ihdr[13+12] = {0, 0, 0, 13, 'I', 'H', 'D', 'R',
 343                         /* w: */ 0, 0, 0, 0, /* h: */ 0,0,0,0,
 344                         /* bpp: */ 8, /* color type: */ 4,
 345                         0, 0, 0};
 346   guchar idat_start[8] = { /* len: */0, 0, 0, 0,   'I', 'D', 'A', 'T' };
 347   guchar iend[12] = {0, 0, 0, 0, 'I', 'E', 'N', 'D', 0xae, 0x42, 0x60, 0x82};
 348   gsize data_size, row_size;
 349   char row_header[6];
 350   guint8 *png, *p, *p_row, *p_idat;
 351   guint8 *row;
 352   unsigned long adler;
 353   guint32 pixel;
 354   gsize png_size;
 355   int x, y;
 356   char *url, *url_base64;
 357   int state = 0, outlen;
 358   int save = 0;
 359
 360   *(guint32 *)&ihdr[8] = GUINT32_TO_BE(w);
 361   *(guint32 *)&ihdr[12] = GUINT32_TO_BE(h);
 362   *(guint32 *)&ihdr[21] = GUINT32_TO_BE(crc(&ihdr[4], 13 + 4));
 363
 364   row_size = 1 + w * 2;
 365   row_header[0] = 0;
 366   row_header[1] = row_size & 0xff;
 367   row_header[2] = (row_size >> 8) & 0xff;
 368   row_header[3] = ~row_header[1];
 369   row_header[4] = ~row_header[2];
 370   row_header[5] = 0;
 371
 372   data_size = 2 + (6 + w * 2) * h + 4;
 373
 374   *(guint32 *)&idat_start[0] = GUINT32_TO_BE(data_size);
 375
 376   png_size = sizeof(header) + sizeof(ihdr) + 12 + data_size + sizeof(iend);
 377   png = g_malloc (png_size);
 378
 379   p = png;
 380   memcpy (p, header, sizeof(header));
 381   p += sizeof(header);
 382   memcpy (p, ihdr, sizeof(ihdr));
 383   p += sizeof(ihdr);
 384   memcpy (p, idat_start, sizeof(idat_start));
 385   p += sizeof(idat_start);
 386
 387   /* IDAT data:
 388
 389      zlib header:  0x78, 0x01 ,
 390      h * scanline: row_header[] + width * r,g,b,a
 391      checksum: adler32
 392   */
 393
 394   p_idat = p - 4;
 395
 396   /* zlib header */
 397   *p++ = 0x78;
 398   *p++ = 0x01;
 399
 400   adler = 1;
 401
 402   /* scanline data */
 403   for (y = 0; y < h; y++) {
 404     if (y == h - 1)
 405       row_header[0] = 1; /* final block */
 406     memcpy (p, row_header, sizeof(row_header));
 407     p += sizeof(row_header);
 408     p_row = p - 1;
 409     row = data;
 410     data += byte_stride / 4;
 411     for (x = 0; x < w; x++) {
 412       pixel = *row++;
 413       *p++ = 0x00; /* gray */
 414       *p++ = pixel; /* alpha */
 415     }
 416     adler = update_adler32(adler, p_row, p - p_row);
 417   }
 418
 419   /* adler32 */
 420   *(guint32 *)p = GUINT32_TO_BE(adler);
 421   p += 4;
 422   *(guint32 *)p = GUINT32_TO_BE(crc(p_idat, p - p_idat));
 423   p += 4;
 424
 425   memcpy (p, iend, sizeof(iend));
 426   p += sizeof(iend);
 427
 428   assert(p - png == png_size);
 429
 430   url = g_malloc (strlen("data:image/png;base64,") +
 431                   ((png_size / 3 + 1) * 4 + 4) + 1);
 432   strcpy (url, "data:image/png;base64,");
 433
 434   url_base64 = url + strlen("data:image/png;base64,");
 435   outlen = g_base64_encode_step (png, png_size, FALSE, url_base64, &state, &save);
 436   outlen += g_base64_encode_close (FALSE, url_base64 + outlen, &state, &save);
 437   url_base64[outlen] = 0;
 438
 439   free (png);
 440
 441   return url;
 442 }
 443 #endif
 444
 445 /************************************************************************
 446  *                Basic I/O primitives                                  *
 447  ************************************************************************/
 448
 449 struct BroadwayOutput {
 450   int fd;
 451   gzFile *zfd;
 452   int error;
 453 };
 454
 455 static void
 456 broadway_output_write_raw (BroadwayOutput *output,
 457                            const void *buf, gsize count)
 458 {
 459   gssize res;
 460   int errsave;
 461   const char *ptr = (const char *)buf;
 462
 463   if (output->error)
 464     return;
 465
 466   while (count > 0)
 467     {
 468       res = write(output->fd, ptr, count);
 469       if (res == -1)
 470         {
 471           errsave = errno;
 472           if (errsave == EINTR)
 473             continue;
 474           output->error = TRUE;
 475           return;
 476         }
 477       if (res == 0)
 478         {
 479           output->error = TRUE;
 480           return;
 481         }
 482       count -= res;
 483       ptr += res;
 484     }
 485 }
 486
 487 static void
 488 broadway_output_write (BroadwayOutput *output,
 489                        const void *buf, gsize count)
 490 {
 491   gssize res;
 492   const char *ptr = (const char *)buf;
 493
 494   if (output->error)
 495     return;
 496
 497   while (count > 0)
 498     {
 499       res = gzwrite(output->zfd, ptr, count);
 500       if (res == -1)
 501         {
 502           output->error = TRUE;
 503           return;
 504         }
 505       if (res == 0)
 506         {
 507           output->error = TRUE;
 508           return;
 509         }
 510       count -= res;
 511       ptr += res;
 512     }
 513 }
 514
 515 static void
 516 broadway_output_write_header (BroadwayOutput *output)
 517 {
 518   char *header;
 519
 520   header =
 521     "HTTP/1.1 200 OK\r\n"
 522     "Content-type: multipart/x-mixed-replace;boundary=x\r\n"
 523     "Content-Encoding: gzip\r\n"
 524     "\r\n";
 525   broadway_output_write_raw (output,
 526                              header, strlen (header));
 527 }
 528
 529 static void
 530 send_boundary (BroadwayOutput *output)
 531 {
 532   char *boundary =
 533     "--x\r\n"
 534     "\r\n";
 535
 536   broadway_output_write (output, boundary, strlen (boundary));
 537 }
 538
 539 BroadwayOutput *
 540 broadway_output_new(int fd)
 541 {
 542   BroadwayOutput *output;
 543
 544   output = g_new0 (BroadwayOutput, 1);
 545
 546   output->fd = fd;
 547
 548   broadway_output_write_header (output);
 549
 550   output->zfd = gzdopen(fd, "wb");
 551
 552   /* Need an initial multipart boundary */
 553   send_boundary (output);
 554
 555   return output;
 556 }
 557
 558 void
 559 broadway_output_free (BroadwayOutput *output)
 560 {
 561   if (output->zfd)
 562     gzclose (output->zfd);
 563   else
 564     close (output->fd);
 565   free (output);
 566 }
 567
 568 int
 569 broadway_output_flush (BroadwayOutput *output)
 570 {
 571   send_boundary (output);
 572   gzflush (output->zfd, Z_SYNC_FLUSH);
 573   return !output->error;
 574 }
 575
 576
 577 /************************************************************************
 578  *                     Core rendering operations                        *
 579  ************************************************************************/
 580
 581 void
 582 broadway_output_copy_rectangles (BroadwayOutput *output,  int id,
 583                                  BroadwayRect *rects, int n_rects,
 584                                  int dx, int dy)
 585 {
 586   char *buf;
 587   int len, i, p;
 588
 589   len = 1 + 3 + 3 + 3*4*n_rects + 3 + 3;
 590
 591   buf = g_malloc (len);
 592   p = 0;
 593   buf[p++] = 'b';
 594   base64_uint16(id, &buf[p]); p +=3;
 595   base64_uint16(n_rects, &buf[p]); p +=3;
 596   for (i = 0; i < n_rects; i++)
 597     {
 598       base64_uint16(rects[i].x, &buf[p]); p +=3;
 599       base64_uint16(rects[i].y, &buf[p]); p +=3;
 600       base64_uint16(rects[i].width, &buf[p]); p +=3;
 601       base64_uint16(rects[i].height, &buf[p]); p +=3;
 602     }
 603   base64_uint16(dx, &buf[p]); p +=3;
 604   base64_uint16(dy, &buf[p]); p +=3;
 605
 606   broadway_output_write (output, buf, len);
 607   free (buf);
 608 }
 609
 610 void
 611 broadway_output_new_surface(BroadwayOutput *output,  int id, int x, int y, int w, int h)
 612 {
 613   char buf[16];
 614
 615   buf[0] = 's';
 616   base64_uint16(id, &buf[1]);
 617   base64_uint16(x, &buf[4]);
 618   base64_uint16(y, &buf[7]);
 619   base64_uint16(w, &buf[10]);
 620   base64_uint16(h, &buf[13]);
 621
 622   broadway_output_write (output, buf, 16);
 623 }
 624
 625 void
 626 broadway_output_show_surface(BroadwayOutput *output,  int id)
 627 {
 628   char buf[4];
 629
 630   buf[0] = 'S';
 631   base64_uint16(id, &buf[1]);
 632
 633   broadway_output_write (output, buf, 4);
 634 }
 635
 636 void
 637 broadway_output_hide_surface(BroadwayOutput *output,  int id)
 638 {
 639   char buf[4];
 640
 641   buf[0] = 'H';
 642   base64_uint16(id, &buf[1]);
 643
 644   broadway_output_write (output, buf, 4);
 645 }
 646
 647 void
 648 broadway_output_destroy_surface(BroadwayOutput *output,  int id)
 649 {
 650   char buf[4];
 651
 652   buf[0] = 'd';
 653   base64_uint16(id, &buf[1]);
 654
 655   broadway_output_write (output, buf, 4);
 656 }
 657
 658 void
 659 broadway_output_move_surface(BroadwayOutput *output,  int id, int x, int y)
 660 {
 661   char buf[10];
 662
 663   buf[0] = 'm';
 664   base64_uint16(id, &buf[1]);
 665   base64_uint16(x, &buf[4]);
 666   base64_uint16(y, &buf[7]);
 667
 668   broadway_output_write (output, buf, 10);
 669 }
 670
 671 void
 672 broadway_output_resize_surface(BroadwayOutput *output,  int id, int w, int h)
 673 {
 674   char buf[10];
 675
 676   buf[0] = 'r';
 677   base64_uint16(id, &buf[1]);
 678   base64_uint16(w, &buf[4]);
 679   base64_uint16(h, &buf[7]);
 680
 681   broadway_output_write (output, buf, 10);
 682 }
 683
 684 void
 685 broadway_output_put_rgb (BroadwayOutput *output,  int id, int x, int y,
 686                          int w, int h, int byte_stride, void *data)
 687 {
 688   char buf[16];
 689   gsize len;
 690   char *url;
 691
 692   buf[0] = 'i';
 693   base64_uint16(id, &buf[1]);
 694   base64_uint16(x, &buf[4]);
 695   base64_uint16(y, &buf[7]);
 696
 697   url = to_png_rgb (w, h, byte_stride, (guint32*)data);
 698   len = strlen (url);
 699   base64_uint32(len, &buf[10]);
 700
 701   broadway_output_write (output, buf, 16);
 702
 703   broadway_output_write (output, url, len);
 704
 705   free (url);
 706 }
 707
 708 typedef struct  {
 709   int x1, y1;
 710   int x2, y2;
 711 } BroadwayBox;
 712
 713 static int
 714 is_any_x_set (unsigned char *data,
 715               int box_x1, int box_x2,
 716               int x1, int x2, int y, int *x_set,
 717               int byte_stride)
 718 {
 719   int w ;
 720   guint32 *ptr;
 721
 722   if (x1 < box_x1)
 723     x1 = box_x1;
 724
 725   if (x2 > box_x2)
 726     x2 = box_x2;
 727
 728   w = x2 - x1;
 729   if (w > 0)
 730     {
 731       ptr = (guint32 *)(data + y * byte_stride + x1 * 4);
 732       while (w-- > 0)
 733         {
 734           if (*ptr != 0)
 735             {
 736               if (x_set)
 737                 *x_set = x1;
 738               return 1;
 739             }
 740           ptr++;
 741           x1++;
 742         }
 743     }
 744   return 0;
 745 }
 746
 747
 748 #define EXTEND_X_FUZZ 10
 749 #define EXTEND_Y_FUZZ 10
 750
 751 static int
 752 extend_x_range (unsigned char *data,
 753                 int box_x1, int box_y1,
 754                 int box_x2, int box_y2,
 755                 int *x1, int *x2, int y,
 756                 int byte_stride)
 757 {
 758   int extended = 0;
 759   int new_x;
 760
 761   while (is_any_x_set (data, box_x1, box_x2, *x1 - EXTEND_X_FUZZ, *x1, y, &new_x, byte_stride))
 762     {
 763       *x1 = new_x;
 764       extended = 1;
 765     }
 766
 767   while (is_any_x_set (data, box_x1, box_x2, *x2, *x2 + EXTEND_X_FUZZ, y, &new_x, byte_stride))
 768     {
 769       *x2 = new_x + 1;
 770       extended = 1;
 771     }
 772
 773   return extended;
 774 }
 775
 776 static int
 777 extend_y_range (unsigned char *data,
 778                 int box_x1, int box_y1,
 779                 int box_x2, int box_y2,
 780                 int x1, int x2, int *y,
 781                 int byte_stride)
 782 {
 783   int extended = 0;
 784   int found_set;
 785   int yy, y2;
 786
 787   while (*y < box_y2)
 788     {
 789       found_set = 0;
 790
 791       y2 = *y + EXTEND_Y_FUZZ;
 792       if (y2 > box_y2)
 793         y2 = box_y2;
 794
 795       for (yy = y2; yy > *y + 1; yy--)
 796         {
 797           if (is_any_x_set (data, box_x1, box_x2, x1, x2, yy - 1, NULL, byte_stride))
 798             {
 799               found_set = 1;
 800               break;
 801             }
 802         }
 803       if (!found_set)
 804         break;
 805       *y = yy;
 806       extended = 1;
 807     }
 808
 809   return extended;
 810 }
 811
 812
 813 static void
 814 rgba_find_rects_extents (unsigned char *data,
 815                          int box_x1, int box_y1,
 816                          int box_x2, int box_y2,
 817                          int x, int y,
 818                          BroadwayBox *rect,
 819                          int byte_stride)
 820 {
 821   int x1, x2, y1, y2, yy;
 822   int extended;
 823
 824   x1 = x;
 825   x2 = x + 1;
 826   y1 = y;
 827   y2 = y + 1;
 828
 829   do
 830     {
 831       /* Expand maximally for all known rows */
 832       do
 833         {
 834           extended = 0;
 835
 836           for (yy = y1; yy < y2; yy++)
 837             extended |= extend_x_range (data,
 838                                         box_x1, box_y1,
 839                                         box_x2, box_y2,
 840                                         &x1, &x2, yy,
 841                                         byte_stride);
 842         }
 843       while (extended);
 844     }
 845   while (extend_y_range(data,
 846                         box_x1, box_y1,
 847                         box_x2, box_y2,
 848                         x1, x2, &y2,
 849                         byte_stride));
 850
 851   rect->x1 = x1;
 852   rect->x2 = x2;
 853   rect->y1 = y1;
 854   rect->y2 = y2;
 855 }
 856
 857 static void
 858 rgba_find_rects_sub (unsigned char *data,
 859                      int box_x1, int box_y1,
 860                      int box_x2, int box_y2,
 861                      int byte_stride,
 862                      BroadwayBox **rects,
 863                      int *n_rects, int *alloc_rects)
 864 {
 865   guint32 *line;
 866   BroadwayBox rect;
 867   int x, y;
 868
 869   if (box_x1 == box_x2 || box_y1 == box_y2)
 870     return;
 871
 872   for (y = box_y1; y < box_y2; y++)
 873     {
 874       line = (guint32 *)(data + y * byte_stride + box_x1 * 4);
 875
 876       for (x = box_x1; x < box_x2; x++)
 877         {
 878           if (*line != 0)
 879             {
 880               rgba_find_rects_extents (data,
 881                                        box_x1, box_y1, box_x2, box_y2,
 882                                        x, y, &rect, byte_stride);
 883               if (*n_rects == *alloc_rects)
 884                 {
 885                   (*alloc_rects) *= 2;
 886                   *rects = g_renew (BroadwayBox, *rects, *alloc_rects);
 887                 }
 888               (*rects)[*n_rects] = rect;
 889               (*n_rects)++;
 890               rgba_find_rects_sub (data,
 891                                    box_x1, rect.y1,
 892                                    rect.x1, rect.y2,
 893                                    byte_stride,
 894                                    rects, n_rects, alloc_rects);
 895               rgba_find_rects_sub (data,
 896                                    rect.x2, rect.y1,
 897                                    box_x2, rect.y2,
 898                                    byte_stride,
 899                                    rects, n_rects, alloc_rects);
 900               rgba_find_rects_sub (data,
 901                                    box_x1, rect.y2,
 902                                    box_x2, box_y2,
 903                                    byte_stride,
 904                                    rects, n_rects, alloc_rects);
 905               return;
 906             }
 907           line++;
 908         }
 909     }
 910 }
 911
 912 static BroadwayBox *
 913 rgba_find_rects (unsigned char *data,
 914                  int w, int h, int byte_stride,
 915                  int *n_rects)
 916 {
 917   BroadwayBox *rects;
 918   int alloc_rects;
 919
 920   alloc_rects = 20;
 921   rects = g_new (BroadwayBox, alloc_rects);
 922
 923   *n_rects = 0;
 924   rgba_find_rects_sub (data,
 925                        0, 0, w, h, byte_stride,
 926                        &rects, n_rects, &alloc_rects);
 927
 928   return rects;
 929 }
 930
 931 void
 932 broadway_output_put_rgba (BroadwayOutput *output,  int id, int x, int y,
 933                           int w, int h, int byte_stride, void *data)
 934 {
 935   char buf[16];
 936   gsize len;
 937   char *url;
 938   BroadwayBox *rects;
 939   int i, n_rects;
 940   guint8 *subdata;
 941
 942   rects = rgba_find_rects (data, w, h, byte_stride, &n_rects);
 943
 944   for (i = 0; i < n_rects; i++)
 945     {
 946       subdata = (guint8 *)data + rects[i].x1 * 4 + rects[i].y1 * byte_stride;
 947
 948       buf[0] = 'i';
 949       base64_uint16(id, &buf[1]);
 950       base64_uint16(x + rects[i].x1, &buf[4]);
 951       base64_uint16(y + rects[i].y1, &buf[7]);
 952
 953       url = to_png_rgba (rects[i].x2 - rects[i].x1,
 954                          rects[i].y2 - rects[i].y1,
 955                          byte_stride, (guint32*)subdata);
 956       len = strlen (url);
 957       base64_uint32(len, &buf[10]);
 958
 959       broadway_output_write (output, buf, 16);
 960
 961       broadway_output_write (output, url, len);
 962
 963       free (url);
 964     }
 965
 966   free (rects);
 967 }
 968
 969 #if 0
 970 static void
 971 send_image_a (BroadwayOutput *output,  int id, int x, int y,
 972               int w, int h, int byte_stride, guint8 *data)
 973 {
 974   char buf[16];
 975   gsize len;
 976   char *url;
 977
 978   buf[0] = 'i';
 979   base64_uint16(id, &buf[1]);
 980   base64_uint16(x, &buf[4]);
 981   base64_uint16(y, &buf[7]);
 982
 983   url = to_png_a (w, h, byte_stride, data);
 984   len = strlen (url);
 985   base64_uint32(len, &buf[10]);
 986
 987   broadway_output_write (output, buf, 16);
 988
 989   broadway_output_write (output, url, len);
 990
 991   free (url);
 992 }
 993 #endif