#include "vnc.h"
#include "vncs.h"

/*
* rise and run length encoding, aka rre.
*
* the pixel contained in r are subdivided into
* rectangles of uniform color, each of which
* is encoded by <color, x, y, w, h>.
*
* use raw encoding if it's shorter.
*
* for compact rre, use limited size rectangles,
* which are shorter to encode and therefor give better compression.
*
* hextile encoding uses rre encoding on at most 16x16 rectangles tiled
* across and then down the screen.
*/
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));
static int      eqpix16(uchar *raw, int p1, int p2);
static int      eqpix32(uchar *raw, int p1, int p2);
static int      eqpix8(uchar *raw, int p1, int p2);
static int      findback(uchar *raw, int stride, int w, int h, int (*eqpix)(uchar*, int, int));
static uchar*   putcorre(uchar *buf, uchar *raw, int p, int pixb, int x, int y, int w, int h);
static uchar*   putrre(uchar *buf, uchar *raw, int p, int pixb, int x, int y, int w, int h);
static void     putpix(Vnc *v, uchar *raw, int p, int pixb);
static int      hexcolors(uchar *raw, int stride, int w, int h, int (*eqpix)(uchar*, int, int), int back, int *fore);
static uchar    *puthexfore(uchar *buf, uchar*, int, int, int x, int y, int w, int h);
static uchar    *puthexcol(uchar *buf, uchar*, int, int, int x, int y, int w, int h);
static void     sendtraw(Vnc *v, uchar *raw, int pixb, int stride, int w, int h);

/*
* default routine, no compression, just the pixels
*/
int
sendraw(Vncs *v, Rectangle r)
{
       int pixb, stride;
       uchar *raw;

       if(!rectinrect(r, v->image->r))
               sysfatal("sending bad rectangle");

       pixb = v->bpp >> 3;
       if((pixb << 3) != v->bpp)
               sysfatal("bad pixel math in sendraw");
       stride = v->image->width*sizeof(ulong);
       if(((stride / pixb) * pixb) != stride)
               sysfatal("bad pixel math in sendraw");
       stride /= pixb;

       raw = byteaddr(v->image, r.min);

       vncwrrect(v, r);
       vncwrlong(v, EncRaw);
       sendtraw(v, raw, pixb, stride, Dx(r), Dy(r));
       return 1;
}

int
countraw(Vncs*, Rectangle)
{
       return 1;
}

/*
* grab the image for the entire rectangle,
* then encode each tile
*/
int
sendhextile(Vncs *v, Rectangle r)
{
       uchar *(*putr)(uchar*, uchar*, int, int, int, int, int, int);
       int (*eq)(uchar*, int, int);
       uchar *raw, *buf, *done, *traw;
       int w, h, stride, pixb, pixlg, nr, bpr, back, fore;
       int sy, sx, th, tw, oback, ofore, k, nc;

       h = Dy(r);
       w = Dx(r);
       if(h == 0 || w == 0 || !rectinrect(r, v->image->r))
               sysfatal("bad rectangle %R in sendhextile %R", r, v->image->r);

       switch(v->bpp){
       case  8:        pixlg = 0;      eq = eqpix8;    break;
       case 16:        pixlg = 1;      eq = eqpix16;   break;
       case 32:        pixlg = 2;      eq = eqpix32;   break;
       default:
               sendraw(v, r);
               return 1;
       }
       pixb = 1 << pixlg;
       stride = v->image->width*sizeof(ulong);
       if(((stride >> pixlg) << pixlg) != stride){
               sendraw(v, r);
               return 1;
       }
       stride >>= pixlg;

       buf = malloc(HextileDim * HextileDim * pixb);
       done = malloc(HextileDim * HextileDim);
       if(buf == nil || done == nil){
               free(buf);
               free(done);
               sendraw(v, r);
               return 1;
       }
       raw = byteaddr(v->image, r.min);

       vncwrrect(v, r);
       vncwrlong(v, EncHextile);
       oback = -1;
       ofore = -1;
       for(sy = 0; sy < h; sy += HextileDim){
               th = h - sy;
               if(th > HextileDim)
                       th = HextileDim;
               for(sx = 0; sx < w; sx += HextileDim){
                       tw = w - sx;
                       if(tw > HextileDim)
                               tw = HextileDim;

                       traw = raw + ((sy * stride + sx) << pixlg);

                       back = findback(traw, stride, tw, th, eq);
                       nc = hexcolors(traw, stride, tw, th, eq, back, &fore);
                       k = 0;
                       if(oback < 0 || !(*eq)(raw, back + ((traw - raw) >> pixlg), oback))
                               k |= HextileBack;
                       if(nc == 1){
                               vncwrchar(v, k);
                               if(k & HextileBack){
                                       oback = back + ((traw - raw) >> pixlg);
                                       putpix(v, raw, oback, pixb);
                               }
                               continue;
                       }
                       k |= HextileRects;
                       if(nc == 2){
                               putr = puthexfore;
                               bpr = 2;
                               if(ofore < 0 || !(*eq)(raw, fore + ((traw - raw) >> pixlg), ofore))
                                       k |= HextileFore;
                       }else{
                               putr = puthexcol;
                               bpr = 2 + pixb;
                               k |= HextileCols;
                               /* stupid vnc clients smash foreground in this case */
                               ofore = -1;
                       }

                       nr = th * tw << pixlg;
                       if(k & HextileBack)
                               nr -= pixb;
                       if(k & HextileFore)
                               nr -= pixb;
                       nr /= bpr;
                       memset(done, 0, HextileDim * HextileDim);
                       nr = encrre(traw, stride, tw, th, back, pixb, buf, nr, done, eq, putr);
                       if(nr < 0){
                               vncwrchar(v, HextileRaw);
                               sendtraw(v, traw, pixb, stride, tw, th);
                               /* stupid vnc clients smash colors in this case */
                               ofore = -1;
                               oback = -1;
                       }else{
                               vncwrchar(v, k);
                               if(k & HextileBack){
                                       oback = back + ((traw - raw) >> pixlg);
                                       putpix(v, raw, oback, pixb);
                               }
                               if(k & HextileFore){
                                       ofore = fore + ((traw - raw) >> pixlg);
                                       putpix(v, raw, ofore, pixb);
                               }
                               vncwrchar(v, nr);
                               vncwrbytes(v, buf, nr * bpr);
                       }
               }
       }
       free(buf);
       free(done);
       return 1;
}

int
counthextile(Vncs*, Rectangle)
{
       return 1;
}

static int
hexcolors(uchar *raw, int stride, int w, int h, int (*eqpix)(uchar*, int, int), int back, int *rfore)
{
       int s, es, sx, esx, fore;

       *rfore = -1;
       fore = -1;
       es = stride * h;
       for(s = 0; s < es; s += stride){
               esx = s + w;
               for(sx = s; sx < esx; sx++){
                       if((*eqpix)(raw, back, sx))
                               continue;
                       if(fore < 0){
                               fore = sx;
                               *rfore = fore;
                       }else if(!(*eqpix)(raw, fore, sx))
                               return 3;
               }
       }

       if(fore < 0)
               return 1;
       return 2;
}

static uchar*
puthexcol(uchar *buf, uchar *raw, int p, int pixb, int x, int y, int w, int h)
{
       raw += p * pixb;
       while(pixb--)
               *buf++ = *raw++;
       *buf++ = (x << 4) | y;
       *buf++ = (w - 1) << 4 | (h - 1);
       return buf;
}

static uchar*
puthexfore(uchar *buf, uchar*, int, int, int x, int y, int w, int h)
{
       *buf++ = (x << 4) | y;
       *buf++ = (w - 1) << 4 | (h - 1);
       return buf;
}

static void
sendtraw(Vnc *v, uchar *raw, int pixb, int stride, int w, int h)
{
       int y;

       for(y = 0; y < h; y++)
               vncwrbytes(v, &raw[y * stride * pixb], w * pixb);
}

static int
rrerects(Rectangle r, int split)
{
       return ((Dy(r) + split - 1) / split) * ((Dx(r) + split - 1) / split);
}

enum
{
       MaxCorreDim     = 48,
       MaxRreDim       = 64,
};

int
countrre(Vncs*, Rectangle r)
{
       return rrerects(r, MaxRreDim);
}

int
countcorre(Vncs*, Rectangle r)
{
       return rrerects(r, MaxCorreDim);
}

static int
_sendrre(Vncs *v, Rectangle r, int split, int compact)
{
       uchar *raw, *buf, *done;
       int w, h, stride, pixb, pixlg, nraw, nr, bpr, back, totr;
       int (*eq)(uchar*, int, int);

       totr = 0;
       h = Dy(r);
       while(h > split){
               h = r.max.y;
               r.max.y = r.min.y + split;
               totr += _sendrre(v, r, split, compact);
               r.min.y = r.max.y;
               r.max.y = h;
               h = Dy(r);
       }
       w = Dx(r);
       while(w > split){
               w = r.max.x;
               r.max.x = r.min.x + split;
               totr += _sendrre(v, r, split, compact);
               r.min.x = r.max.x;
               r.max.x = w;
               w = Dx(r);
       }
       if(h == 0 || w == 0 || !rectinrect(r, v->image->r))
               sysfatal("bad rectangle in sendrre");

       switch(v->bpp){
       case  8:        pixlg = 0;      eq = eqpix8;    break;
       case 16:        pixlg = 1;      eq = eqpix16;   break;
       case 32:        pixlg = 2;      eq = eqpix32;   break;
       default:
               sendraw(v, r);
               return totr + 1;
       }
       pixb = 1 << pixlg;
       stride = v->image->width*sizeof(ulong);
       if(((stride >> pixlg) << pixlg) != stride){
               sendraw(v, r);
               return totr + 1;
       }
       stride >>= pixlg;

       nraw = w * pixb * h;
       buf = malloc(nraw);
       done = malloc(w * h);
       if(buf == nil || done == nil){
               free(buf);
               free(done);
               sendraw(v, r);
               return totr + 1;
       }
       memset(done, 0, w * h);

       raw = byteaddr(v->image, r.min);

       if(compact)
               bpr = 4 * 1 + pixb;
       else
               bpr = 4 * 2 + pixb;
       nr = (nraw - 4 - pixb) / bpr;
       back = findback(raw, stride, w, h, eq);
       if(compact)
               nr = encrre(raw, stride, w, h, back, pixb, buf, nr, done, eq, putcorre);
       else
               nr = encrre(raw, stride, w, h, back, pixb, buf, nr, done, eq, putrre);
       if(nr < 0){
               vncwrrect(v, r);
               vncwrlong(v, EncRaw);
               sendtraw(v, raw, pixb, stride, w, h);
       }else{
               vncwrrect(v, r);
               if(compact)
                       vncwrlong(v, EncCorre);
               else
                       vncwrlong(v, EncRre);
               vncwrlong(v, nr);
               putpix(v, raw, back, pixb);
               vncwrbytes(v, buf, nr * bpr);
       }
       free(buf);
       free(done);

       return totr + 1;
}

int
sendrre(Vncs *v, Rectangle r)
{
       return _sendrre(v, r, MaxRreDim, 0);
}

int
sendcorre(Vncs *v, Rectangle r)
{
       return _sendrre(v, r, MaxCorreDim, 1);
}

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))
{
       int s, es, sx, esx, sy, syx, esyx, rh, rw, y, nr, dsy, dp;

       es = stride * h;
       y = 0;
       nr = 0;
       dp = 0;
       for(s = 0; s < es; s += stride){
               esx = s + w;
               for(sx = s; sx < esx; ){
                       rw = done[dp];
                       if(rw){
                               sx += rw;
                               dp += rw;
                               continue;
                       }
                       if((*eqpix)(raw, back, sx)){
                               sx++;
                               dp++;
                               continue;
                       }

                       if(nr >= maxr)
                               return -1;

                       /*
                        * find the tallest maximally wide uniform colored rectangle
                        * with p at the upper left.
                        * this isn't an optimal parse, but it's pretty good for text
                        */
                       rw = esx - sx;
                       rh = 0;
                       for(sy = sx; sy < es; sy += stride){
                               if(!(*eqpix)(raw, sx, sy))
                                       break;
                               esyx = sy + rw;
                               for(syx = sy + 1; syx < esyx; syx++){
                                       if(!(*eqpix)(raw, sx, syx)){
                                               if(sy == sx)
                                                       break;
                                               goto breakout;
                                       }
                               }
                               if(sy == sx)
                                       rw = syx - sy;
                               rh++;
                       }
               breakout:;

                       nr++;
                       buf = (*putr)(buf, raw, sx, pixb, sx - s, y, rw, rh);

                       /*
                        * mark all pixels done
                        */
                       dsy = dp;
                       while(rh--){
                               esyx = dsy + rw;
                               for(syx = dsy; syx < esyx; syx++)
                                       done[syx] = esyx - syx;
                               dsy += w;
                       }

                       sx += rw;
                       dp += rw;
               }
               y++;
       }
       return nr;
}

/*
* estimate the background color
* by finding the most frequent character in a small sample
*/
static int
findback(uchar *raw, int stride, int w, int h, int (*eqpix)(uchar*, int, int))
{
       enum{
               NCol = 6,
               NExamine = 4
       };
       int ccount[NCol], col[NCol], i, wstep, hstep, x, y, pix, c, max, maxc;

       wstep = w / NExamine;
       if(wstep < 1)
               wstep = 1;
       hstep = h / NExamine;
       if(hstep < 1)
               hstep = 1;

       for(i = 0; i< NCol; i++)
               ccount[i] = 0;
       for(y = 0; y < h; y += hstep){
               for(x = 0; x < w; x += wstep){
                       pix = y * stride + x;
                       for(i = 0; i < NCol; i++){
                               if(ccount[i] == 0){
                                       ccount[i] = 1;
                                       col[i] = pix;
                                       break;
                               }
                               if((*eqpix)(raw, pix, col[i])){
                                       ccount[i]++;
                                       break;
                               }
                       }
               }
       }
       maxc = ccount[0];
       max = 0;
       for(i = 1; i < NCol; i++){
               c = ccount[i];
               if(!c)
                       break;
               if(c > maxc){
                       max = i;
                       maxc = c;
               }
       }
       return col[max];
}

static uchar*
putrre(uchar *buf, uchar *raw, int p, int pixb, int x, int y, int w, int h)
{
       raw += p * pixb;
       while(pixb--)
               *buf++ = *raw++;
       *buf++ = x >> 8;
       *buf++ = x;
       *buf++ = y >> 8;
       *buf++ = y;
       *buf++ = w >> 8;
       *buf++ = w;
       *buf++ = h >> 8;
       *buf++ = h;
       return buf;
}

static uchar*
putcorre(uchar *buf, uchar *raw, int p, int pixb, int x, int y, int w, int h)
{
       raw += p * pixb;
       while(pixb--)
               *buf++ = *raw++;
       *buf++ = x;
       *buf++ = y;
       *buf++ = w;
       *buf++ = h;
       return buf;
}

static int
eqpix8(uchar *raw, int p1, int p2)
{
       return raw[p1] == raw[p2];
}

static int
eqpix16(uchar *raw, int p1, int p2)
{
       return ((ushort*)raw)[p1] == ((ushort*)raw)[p2];
}

static int
eqpix32(uchar *raw, int p1, int p2)
{
       return ((ulong*)raw)[p1] == ((ulong*)raw)[p2];
}

static void
putpix(Vnc *v, uchar *raw, int p, int pixb)
{
       vncwrbytes(v, raw + p * pixb, pixb);
}

You are viewing proxied material from sdf.org. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.