sys/src/cmd/vnc/rre.c

   1 #include "vnc.h"
   2 #include "vncs.h"
   3
   4 /*
   5  * rise and run length encoding, aka rre.
   6  *
   7  * the pixel contained in r are subdivided into
   8  * rectangles of uniform color, each of which
   9  * is encoded by <color, x, y, w, h>.
  10  *
  11  * use raw encoding if it's shorter.
  12  *
  13  * for compact rre, use limited size rectangles,
  14  * which are shorter to encode and therefor give better compression.
  15  *
  16  * hextile encoding uses rre encoding on at most 16x16 rectangles tiled
  17  * across and then down the screen.
  18  */
  19 static int      encrre(uchar *raw, int stride, int w, int h, int back, int pixb, uchar *buf, int maxr, uchar *done, int (*eqpix)(uchar*, int, int), uchar *(putr)(uchar*, uchar*, int, int, int, int, int, int));
  20 static int      eqpix16(uchar *raw, int p1, int p2);
  21 static int      eqpix32(uchar *raw, int p1, int p2);
  22 static int      eqpix8(uchar *raw, int p1, int p2);
  23 static int      findback(uchar *raw, int stride, int w, int h, int (*eqpix)(uchar*, int, int));
  24 static uchar*   putcorre(uchar *buf, uchar *raw, int p, int pixb, int x, int y, int w, int h);
  25 static uchar*   putrre(uchar *buf, uchar *raw, int p, int pixb, int x, int y, int w, int h);
  26 static void     putpix(Vnc *v, uchar *raw, int p, int pixb);
  27 static int      hexcolors(uchar *raw, int stride, int w, int h, int (*eqpix)(uchar*, int, int), int back, int *fore);
  28 static uchar    *puthexfore(uchar *buf, uchar*, int, int, int x, int y, int w, int h);
  29 static uchar    *puthexcol(uchar *buf, uchar*, int, int, int x, int y, int w, int h);
  30 static void     sendtraw(Vnc *v, uchar *raw, int pixb, int stride, int w, int h);
  31
  32 /*
  33  * default routine, no compression, just the pixels
  34  */
  35 int
  36 sendraw(Vncs *v, Rectangle r)
  37 {
  38         int pixb, stride;
  39         uchar *raw;
  40
  41         if(!rectinrect(r, v->image->r))
  42                 sysfatal("sending bad rectangle");
  43
  44         pixb = v->bpp >> 3;
  45         if((pixb << 3) != v->bpp)
  46                 sysfatal("bad pixel math in sendraw");
  47         stride = v->image->width*sizeof(ulong);
  48         if(((stride / pixb) * pixb) != stride)
  49                 sysfatal("bad pixel math in sendraw");
  50         stride /= pixb;
  51
  52         raw = byteaddr(v->image, r.min);
  53
  54         vncwrrect(v, r);
  55         vncwrlong(v, EncRaw);
  56         sendtraw(v, raw, pixb, stride, Dx(r), Dy(r));
  57         return 1;
  58 }
  59
  60 int
  61 countraw(Vncs*, Rectangle)
  62 {
  63         return 1;
  64 }
  65
  66 /*
  67  * grab the image for the entire rectangle,
  68  * then encode each tile
  69  */
  70 int
  71 sendhextile(Vncs *v, Rectangle r)
  72 {
  73         uchar *(*putr)(uchar*, uchar*, int, int, int, int, int, int);
  74         int (*eq)(uchar*, int, int);
  75         uchar *raw, *buf, *done, *traw;
  76         int w, h, stride, pixb, pixlg, nr, bpr, back, fore;
  77         int sy, sx, th, tw, oback, ofore, k, nc;
  78
  79         h = Dy(r);
  80         w = Dx(r);
  81         if(h == 0 || w == 0 || !rectinrect(r, v->image->r))
  82                 sysfatal("bad rectangle %R in sendhextile %R", r, v->image->r);
  83
  84         switch(v->bpp){
  85         case  8:        pixlg = 0;      eq = eqpix8;    break;
  86         case 16:        pixlg = 1;      eq = eqpix16;   break;
  87         case 32:        pixlg = 2;      eq = eqpix32;   break;
  88         default:
  89                 sendraw(v, r);
  90                 return 1;
  91         }
  92         pixb = 1 << pixlg;
  93         stride = v->image->width*sizeof(ulong);
  94         if(((stride >> pixlg) << pixlg) != stride){
  95                 sendraw(v, r);
  96                 return 1;
  97         }
  98         stride >>= pixlg;
  99
 100         buf = malloc(HextileDim * HextileDim * pixb);
 101         done = malloc(HextileDim * HextileDim);
 102         if(buf == nil || done == nil){
 103                 free(buf);
 104                 free(done);
 105                 sendraw(v, r);
 106                 return 1;
 107         }
 108         raw = byteaddr(v->image, r.min);
 109
 110         vncwrrect(v, r);
 111         vncwrlong(v, EncHextile);
 112         oback = -1;
 113         ofore = -1;
 114         for(sy = 0; sy < h; sy += HextileDim){
 115                 th = h - sy;
 116                 if(th > HextileDim)
 117                         th = HextileDim;
 118                 for(sx = 0; sx < w; sx += HextileDim){
 119                         tw = w - sx;
 120                         if(tw > HextileDim)
 121                                 tw = HextileDim;
 122
 123                         traw = raw + ((sy * stride + sx) << pixlg);
 124
 125                         back = findback(traw, stride, tw, th, eq);
 126                         nc = hexcolors(traw, stride, tw, th, eq, back, &fore);
 127                         k = 0;
 128                         if(oback < 0 || !(*eq)(raw, back + ((traw - raw) >> pixlg), oback))
 129                                 k |= HextileBack;
 130                         if(nc == 1){
 131                                 vncwrchar(v, k);
 132                                 if(k & HextileBack){
 133                                         oback = back + ((traw - raw) >> pixlg);
 134                                         putpix(v, raw, oback, pixb);
 135                                 }
 136                                 continue;
 137                         }
 138                         k |= HextileRects;
 139                         if(nc == 2){
 140                                 putr = puthexfore;
 141                                 bpr = 2;
 142                                 if(ofore < 0 || !(*eq)(raw, fore + ((traw - raw) >> pixlg), ofore))
 143                                         k |= HextileFore;
 144                         }else{
 145                                 putr = puthexcol;
 146                                 bpr = 2 + pixb;
 147                                 k |= HextileCols;
 148                                 /* stupid vnc clients smash foreground in this case */
 149                                 ofore = -1;
 150                         }
 151
 152                         nr = th * tw << pixlg;
 153                         if(k & HextileBack)
 154                                 nr -= pixb;
 155                         if(k & HextileFore)
 156                                 nr -= pixb;
 157                         nr /= bpr;
 158                         memset(done, 0, HextileDim * HextileDim);
 159                         nr = encrre(traw, stride, tw, th, back, pixb, buf, nr, done, eq, putr);
 160                         if(nr < 0){
 161                                 vncwrchar(v, HextileRaw);
 162                                 sendtraw(v, traw, pixb, stride, tw, th);
 163                                 /* stupid vnc clients smash colors in this case */
 164                                 ofore = -1;
 165                                 oback = -1;
 166                         }else{
 167                                 vncwrchar(v, k);
 168                                 if(k & HextileBack){
 169                                         oback = back + ((traw - raw) >> pixlg);
 170                                         putpix(v, raw, oback, pixb);
 171                                 }
 172                                 if(k & HextileFore){
 173                                         ofore = fore + ((traw - raw) >> pixlg);
 174                                         putpix(v, raw, ofore, pixb);
 175                                 }
 176                                 vncwrchar(v, nr);
 177                                 vncwrbytes(v, buf, nr * bpr);
 178                         }
 179                 }
 180         }
 181         free(buf);
 182         free(done);
 183         return 1;
 184 }
 185
 186 int
 187 counthextile(Vncs*, Rectangle)
 188 {
 189         return 1;
 190 }
 191
 192 static int
 193 hexcolors(uchar *raw, int stride, int w, int h, int (*eqpix)(uchar*, int, int), int back, int *rfore)
 194 {
 195         int s, es, sx, esx, fore;
 196
 197         *rfore = -1;
 198         fore = -1;
 199         es = stride * h;
 200         for(s = 0; s < es; s += stride){
 201                 esx = s + w;
 202                 for(sx = s; sx < esx; sx++){
 203                         if((*eqpix)(raw, back, sx))
 204                                 continue;
 205                         if(fore < 0){
 206                                 fore = sx;
 207                                 *rfore = fore;
 208                         }else if(!(*eqpix)(raw, fore, sx))
 209                                 return 3;
 210                 }
 211         }
 212
 213         if(fore < 0)
 214                 return 1;
 215         return 2;
 216 }
 217
 218 static uchar*
 219 puthexcol(uchar *buf, uchar *raw, int p, int pixb, int x, int y, int w, int h)
 220 {
 221         raw += p * pixb;
 222         while(pixb--)
 223                 *buf++ = *raw++;
 224         *buf++ = (x << 4) | y;
 225         *buf++ = (w - 1) << 4 | (h - 1);
 226         return buf;
 227 }
 228
 229 static uchar*
 230 puthexfore(uchar *buf, uchar*, int, int, int x, int y, int w, int h)
 231 {
 232         *buf++ = (x << 4) | y;
 233         *buf++ = (w - 1) << 4 | (h - 1);
 234         return buf;
 235 }
 236
 237 static void
 238 sendtraw(Vnc *v, uchar *raw, int pixb, int stride, int w, int h)
 239 {
 240         int y;
 241
 242         for(y = 0; y < h; y++)
 243                 vncwrbytes(v, &raw[y * stride * pixb], w * pixb);
 244 }
 245
 246 static int
 247 rrerects(Rectangle r, int split)
 248 {
 249         return ((Dy(r) + split - 1) / split) * ((Dx(r) + split - 1) / split);
 250 }
 251
 252 enum
 253 {
 254         MaxCorreDim     = 48,
 255         MaxRreDim       = 64,
 256 };
 257
 258 int
 259 countrre(Vncs*, Rectangle r)
 260 {
 261         return rrerects(r, MaxRreDim);
 262 }
 263
 264 int
 265 countcorre(Vncs*, Rectangle r)
 266 {
 267         return rrerects(r, MaxCorreDim);
 268 }
 269
 270 static int
 271 _sendrre(Vncs *v, Rectangle r, int split, int compact)
 272 {
 273         uchar *raw, *buf, *done;
 274         int w, h, stride, pixb, pixlg, nraw, nr, bpr, back, totr;
 275         int (*eq)(uchar*, int, int);
 276
 277         totr = 0;
 278         h = Dy(r);
 279         while(h > split){
 280                 h = r.max.y;
 281                 r.max.y = r.min.y + split;
 282                 totr += _sendrre(v, r, split, compact);
 283                 r.min.y = r.max.y;
 284                 r.max.y = h;
 285                 h = Dy(r);
 286         }
 287         w = Dx(r);
 288         while(w > split){
 289                 w = r.max.x;
 290                 r.max.x = r.min.x + split;
 291                 totr += _sendrre(v, r, split, compact);
 292                 r.min.x = r.max.x;
 293                 r.max.x = w;
 294                 w = Dx(r);
 295         }
 296         if(h == 0 || w == 0 || !rectinrect(r, v->image->r))
 297                 sysfatal("bad rectangle in sendrre");
 298
 299         switch(v->bpp){
 300         case  8:        pixlg = 0;      eq = eqpix8;    break;
 301         case 16:        pixlg = 1;      eq = eqpix16;   break;
 302         case 32:        pixlg = 2;      eq = eqpix32;   break;
 303         default:
 304                 sendraw(v, r);
 305                 return totr + 1;
 306         }
 307         pixb = 1 << pixlg;
 308         stride = v->image->width*sizeof(ulong);
 309         if(((stride >> pixlg) << pixlg) != stride){
 310                 sendraw(v, r);
 311                 return totr + 1;
 312         }
 313         stride >>= pixlg;
 314
 315         nraw = w * pixb * h;
 316         buf = malloc(nraw);
 317         done = malloc(w * h);
 318         if(buf == nil || done == nil){
 319                 free(buf);
 320                 free(done);
 321                 sendraw(v, r);
 322                 return totr + 1;
 323         }
 324         memset(done, 0, w * h);
 325
 326         raw = byteaddr(v->image, r.min);
 327
 328         if(compact)
 329                 bpr = 4 * 1 + pixb;
 330         else
 331                 bpr = 4 * 2 + pixb;
 332         nr = (nraw - 4 - pixb) / bpr;
 333         back = findback(raw, stride, w, h, eq);
 334         if(compact)
 335                 nr = encrre(raw, stride, w, h, back, pixb, buf, nr, done, eq, putcorre);
 336         else
 337                 nr = encrre(raw, stride, w, h, back, pixb, buf, nr, done, eq, putrre);
 338         if(nr < 0){
 339                 vncwrrect(v, r);
 340                 vncwrlong(v, EncRaw);
 341                 sendtraw(v, raw, pixb, stride, w, h);
 342         }else{
 343                 vncwrrect(v, r);
 344                 if(compact)
 345                         vncwrlong(v, EncCorre);
 346                 else
 347                         vncwrlong(v, EncRre);
 348                 vncwrlong(v, nr);
 349                 putpix(v, raw, back, pixb);
 350                 vncwrbytes(v, buf, nr * bpr);
 351         }
 352         free(buf);
 353         free(done);
 354
 355         return totr + 1;
 356 }
 357
 358 int
 359 sendrre(Vncs *v, Rectangle r)
 360 {
 361         return _sendrre(v, r, MaxRreDim, 0);
 362 }
 363
 364 int
 365 sendcorre(Vncs *v, Rectangle r)
 366 {
 367         return _sendrre(v, r, MaxCorreDim, 1);
 368 }
 369
 370 static int
 371 encrre(uchar *raw, int stride, int w, int h, int back, int pixb, uchar *buf,
 372         int maxr, uchar *done, int (*eqpix)(uchar*, int, int),
 373         uchar *(*putr)(uchar*, uchar*, int, int, int, int, int, int))
 374 {
 375         int s, es, sx, esx, sy, syx, esyx, rh, rw, y, nr, dsy, dp;
 376
 377         es = stride * h;
 378         y = 0;
 379         nr = 0;
 380         dp = 0;
 381         for(s = 0; s < es; s += stride){
 382                 esx = s + w;
 383                 for(sx = s; sx < esx; ){
 384                         rw = done[dp];
 385                         if(rw){
 386                                 sx += rw;
 387                                 dp += rw;
 388                                 continue;
 389                         }
 390                         if((*eqpix)(raw, back, sx)){
 391                                 sx++;
 392                                 dp++;
 393                                 continue;
 394                         }
 395
 396                         if(nr >= maxr)
 397                                 return -1;
 398
 399                         /*
 400                          * find the tallest maximally wide uniform colored rectangle
 401                          * with p at the upper left.
 402                          * this isn't an optimal parse, but it's pretty good for text
 403                          */
 404                         rw = esx - sx;
 405                         rh = 0;
 406                         for(sy = sx; sy < es; sy += stride){
 407                                 if(!(*eqpix)(raw, sx, sy))
 408                                         break;
 409                                 esyx = sy + rw;
 410                                 for(syx = sy + 1; syx < esyx; syx++){
 411                                         if(!(*eqpix)(raw, sx, syx)){
 412                                                 if(sy == sx)
 413                                                         break;
 414                                                 goto breakout;
 415                                         }
 416                                 }
 417                                 if(sy == sx)
 418                                         rw = syx - sy;
 419                                 rh++;
 420                         }
 421                 breakout:;
 422
 423                         nr++;
 424                         buf = (*putr)(buf, raw, sx, pixb, sx - s, y, rw, rh);
 425
 426                         /*
 427                          * mark all pixels done
 428                          */
 429                         dsy = dp;
 430                         while(rh--){
 431                                 esyx = dsy + rw;
 432                                 for(syx = dsy; syx < esyx; syx++)
 433                                         done[syx] = esyx - syx;
 434                                 dsy += w;
 435                         }
 436
 437                         sx += rw;
 438                         dp += rw;
 439                 }
 440                 y++;
 441         }
 442         return nr;
 443 }
 444
 445 /*
 446  * estimate the background color
 447  * by finding the most frequent character in a small sample
 448  */
 449 static int
 450 findback(uchar *raw, int stride, int w, int h, int (*eqpix)(uchar*, int, int))
 451 {
 452         enum{
 453                 NCol = 6,
 454                 NExamine = 4
 455         };
 456         int ccount[NCol], col[NCol], i, wstep, hstep, x, y, pix, c, max, maxc;
 457
 458         wstep = w / NExamine;
 459         if(wstep < 1)
 460                 wstep = 1;
 461         hstep = h / NExamine;
 462         if(hstep < 1)
 463                 hstep = 1;
 464
 465         for(i = 0; i< NCol; i++)
 466                 ccount[i] = 0;
 467         for(y = 0; y < h; y += hstep){
 468                 for(x = 0; x < w; x += wstep){
 469                         pix = y * stride + x;
 470                         for(i = 0; i < NCol; i++){
 471                                 if(ccount[i] == 0){
 472                                         ccount[i] = 1;
 473                                         col[i] = pix;
 474                                         break;
 475                                 }
 476                                 if((*eqpix)(raw, pix, col[i])){
 477                                         ccount[i]++;
 478                                         break;
 479                                 }
 480                         }
 481                 }
 482         }
 483         maxc = ccount[0];
 484         max = 0;
 485         for(i = 1; i < NCol; i++){
 486                 c = ccount[i];
 487                 if(!c)
 488                         break;
 489                 if(c > maxc){
 490                         max = i;
 491                         maxc = c;
 492                 }
 493         }
 494         return col[max];
 495 }
 496
 497 static uchar*
 498 putrre(uchar *buf, uchar *raw, int p, int pixb, int x, int y, int w, int h)
 499 {
 500         raw += p * pixb;
 501         while(pixb--)
 502                 *buf++ = *raw++;
 503         *buf++ = x >> 8;
 504         *buf++ = x;
 505         *buf++ = y >> 8;
 506         *buf++ = y;
 507         *buf++ = w >> 8;
 508         *buf++ = w;
 509         *buf++ = h >> 8;
 510         *buf++ = h;
 511         return buf;
 512 }
 513
 514 static uchar*
 515 putcorre(uchar *buf, uchar *raw, int p, int pixb, int x, int y, int w, int h)
 516 {
 517         raw += p * pixb;
 518         while(pixb--)
 519                 *buf++ = *raw++;
 520         *buf++ = x;
 521         *buf++ = y;
 522         *buf++ = w;
 523         *buf++ = h;
 524         return buf;
 525 }
 526
 527 static int
 528 eqpix8(uchar *raw, int p1, int p2)
 529 {
 530         return raw[p1] == raw[p2];
 531 }
 532
 533 static int
 534 eqpix16(uchar *raw, int p1, int p2)
 535 {
 536         return ((ushort*)raw)[p1] == ((ushort*)raw)[p2];
 537 }
 538
 539 static int
 540 eqpix32(uchar *raw, int p1, int p2)
 541 {
 542         return ((ulong*)raw)[p1] == ((ulong*)raw)[p2];
 543 }
 544
 545 static void
 546 putpix(Vnc *v, uchar *raw, int p, int pixb)
 547 {
 548         vncwrbytes(v, raw + p * pixb, pixb);
 549 }