123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549 |
- #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);
- }
|