5 * rise and run length encoding, aka rre.
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>.
11 * use raw encoding if it's shorter.
13 * for compact rre, use limited size rectangles,
14 * which are shorter to encode and therefor give better compression.
16 * hextile encoding uses rre encoding on at most 16x16 rectangles tiled
17 * across and then down the screen.
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);
33 * default routine, no compression, just the pixels
36 sendraw(Vncs *v, Rectangle r)
41 if(!rectinrect(r, v->image->r))
42 sysfatal("sending bad rectangle");
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");
52 raw = byteaddr(v->image, r.min);
56 sendtraw(v, raw, pixb, stride, Dx(r), Dy(r));
61 countraw(Vncs*, Rectangle)
67 * grab the image for the entire rectangle,
68 * then encode each tile
71 sendhextile(Vncs *v, Rectangle r)
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;
81 if(h == 0 || w == 0 || !rectinrect(r, v->image->r))
82 sysfatal("bad rectangle %R in sendhextile %R", r, v->image->r);
85 case 8: pixlg = 0; eq = eqpix8; break;
86 case 16: pixlg = 1; eq = eqpix16; break;
87 case 32: pixlg = 2; eq = eqpix32; break;
93 stride = v->image->width*sizeof(ulong);
94 if(((stride >> pixlg) << pixlg) != stride){
100 buf = malloc(HextileDim * HextileDim * pixb);
101 done = malloc(HextileDim * HextileDim);
102 if(buf == nil || done == nil){
108 raw = byteaddr(v->image, r.min);
111 vncwrlong(v, EncHextile);
114 for(sy = 0; sy < h; sy += HextileDim){
118 for(sx = 0; sx < w; sx += HextileDim){
123 traw = raw + ((sy * stride + sx) << pixlg);
125 back = findback(traw, stride, tw, th, eq);
126 nc = hexcolors(traw, stride, tw, th, eq, back, &fore);
128 if(oback < 0 || !(*eq)(raw, back + ((traw - raw) >> pixlg), oback))
133 oback = back + ((traw - raw) >> pixlg);
134 putpix(v, raw, oback, pixb);
142 if(ofore < 0 || !(*eq)(raw, fore + ((traw - raw) >> pixlg), ofore))
148 /* stupid vnc clients smash foreground in this case */
152 nr = th * tw << pixlg;
158 memset(done, 0, HextileDim * HextileDim);
159 nr = encrre(traw, stride, tw, th, back, pixb, buf, nr, done, eq, putr);
161 vncwrchar(v, HextileRaw);
162 sendtraw(v, traw, pixb, stride, tw, th);
163 /* stupid vnc clients smash colors in this case */
169 oback = back + ((traw - raw) >> pixlg);
170 putpix(v, raw, oback, pixb);
173 ofore = fore + ((traw - raw) >> pixlg);
174 putpix(v, raw, ofore, pixb);
177 vncwrbytes(v, buf, nr * bpr);
187 counthextile(Vncs*, Rectangle)
193 hexcolors(uchar *raw, int stride, int w, int h, int (*eqpix)(uchar*, int, int), int back, int *rfore)
195 int s, es, sx, esx, fore;
200 for(s = 0; s < es; s += stride){
202 for(sx = s; sx < esx; sx++){
203 if((*eqpix)(raw, back, sx))
208 }else if(!(*eqpix)(raw, fore, sx))
219 puthexcol(uchar *buf, uchar *raw, int p, int pixb, int x, int y, int w, int h)
224 *buf++ = (x << 4) | y;
225 *buf++ = (w - 1) << 4 | (h - 1);
230 puthexfore(uchar *buf, uchar*, int, int, int x, int y, int w, int h)
232 *buf++ = (x << 4) | y;
233 *buf++ = (w - 1) << 4 | (h - 1);
238 sendtraw(Vnc *v, uchar *raw, int pixb, int stride, int w, int h)
242 for(y = 0; y < h; y++)
243 vncwrbytes(v, &raw[y * stride * pixb], w * pixb);
247 rrerects(Rectangle r, int split)
249 return ((Dy(r) + split - 1) / split) * ((Dx(r) + split - 1) / split);
259 countrre(Vncs*, Rectangle r)
261 return rrerects(r, MaxRreDim);
265 countcorre(Vncs*, Rectangle r)
267 return rrerects(r, MaxCorreDim);
271 _sendrre(Vncs *v, Rectangle r, int split, int compact)
273 uchar *raw, *buf, *done;
274 int w, h, stride, pixb, pixlg, nraw, nr, bpr, back, totr;
275 int (*eq)(uchar*, int, int);
281 r.max.y = r.min.y + split;
282 totr += _sendrre(v, r, split, compact);
290 r.max.x = r.min.x + split;
291 totr += _sendrre(v, r, split, compact);
296 if(h == 0 || w == 0 || !rectinrect(r, v->image->r))
297 sysfatal("bad rectangle in sendrre");
300 case 8: pixlg = 0; eq = eqpix8; break;
301 case 16: pixlg = 1; eq = eqpix16; break;
302 case 32: pixlg = 2; eq = eqpix32; break;
308 stride = v->image->width*sizeof(ulong);
309 if(((stride >> pixlg) << pixlg) != stride){
317 done = malloc(w * h);
318 if(buf == nil || done == nil){
324 memset(done, 0, w * h);
326 raw = byteaddr(v->image, r.min);
332 nr = (nraw - 4 - pixb) / bpr;
333 back = findback(raw, stride, w, h, eq);
335 nr = encrre(raw, stride, w, h, back, pixb, buf, nr, done, eq, putcorre);
337 nr = encrre(raw, stride, w, h, back, pixb, buf, nr, done, eq, putrre);
340 vncwrlong(v, EncRaw);
341 sendtraw(v, raw, pixb, stride, w, h);
345 vncwrlong(v, EncCorre);
347 vncwrlong(v, EncRre);
349 putpix(v, raw, back, pixb);
350 vncwrbytes(v, buf, nr * bpr);
359 sendrre(Vncs *v, Rectangle r)
361 return _sendrre(v, r, MaxRreDim, 0);
365 sendcorre(Vncs *v, Rectangle r)
367 return _sendrre(v, r, MaxCorreDim, 1);
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))
375 int s, es, sx, esx, sy, syx, esyx, rh, rw, y, nr, dsy, dp;
381 for(s = 0; s < es; s += stride){
383 for(sx = s; sx < esx; ){
390 if((*eqpix)(raw, back, sx)){
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
406 for(sy = sx; sy < es; sy += stride){
407 if(!(*eqpix)(raw, sx, sy))
410 for(syx = sy + 1; syx < esyx; syx++){
411 if(!(*eqpix)(raw, sx, syx)){
424 buf = (*putr)(buf, raw, sx, pixb, sx - s, y, rw, rh);
427 * mark all pixels done
432 for(syx = dsy; syx < esyx; syx++)
433 done[syx] = esyx - syx;
446 * estimate the background color
447 * by finding the most frequent character in a small sample
450 findback(uchar *raw, int stride, int w, int h, int (*eqpix)(uchar*, int, int))
456 int ccount[NCol], col[NCol], i, wstep, hstep, x, y, pix, c, max, maxc;
458 wstep = w / NExamine;
461 hstep = h / NExamine;
465 for(i = 0; i< NCol; i++)
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++){
476 if((*eqpix)(raw, pix, col[i])){
485 for(i = 1; i < NCol; i++){
498 putrre(uchar *buf, uchar *raw, int p, int pixb, int x, int y, int w, int h)
515 putcorre(uchar *buf, uchar *raw, int p, int pixb, int x, int y, int w, int h)
528 eqpix8(uchar *raw, int p1, int p2)
530 return raw[p1] == raw[p2];
534 eqpix16(uchar *raw, int p1, int p2)
536 return ((ushort*)raw)[p1] == ((ushort*)raw)[p2];
540 eqpix32(uchar *raw, int p1, int p2)
542 return ((ulong*)raw)[p1] == ((ulong*)raw)[p2];
546 putpix(Vnc *v, uchar *raw, int p, int pixb)
548 vncwrbytes(v, raw + p * pixb, pixb);