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
sendraw(Vncs * v,Rectangle r)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
countraw(Vncs *,Rectangle)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
sendhextile(Vncs * v,Rectangle r)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
counthextile(Vncs *,Rectangle)187 counthextile(Vncs*, Rectangle)
188 {
189 return 1;
190 }
191
192 static int
hexcolors(uchar * raw,int stride,int w,int h,int (* eqpix)(uchar *,int,int),int back,int * rfore)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*
puthexcol(uchar * buf,uchar * raw,int p,int pixb,int x,int y,int w,int h)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*
puthexfore(uchar * buf,uchar *,int,int,int x,int y,int w,int h)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
sendtraw(Vnc * v,uchar * raw,int pixb,int stride,int w,int h)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
rrerects(Rectangle r,int split)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
countrre(Vncs *,Rectangle r)259 countrre(Vncs*, Rectangle r)
260 {
261 return rrerects(r, MaxRreDim);
262 }
263
264 int
countcorre(Vncs *,Rectangle r)265 countcorre(Vncs*, Rectangle r)
266 {
267 return rrerects(r, MaxCorreDim);
268 }
269
270 static int
_sendrre(Vncs * v,Rectangle r,int split,int compact)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
sendrre(Vncs * v,Rectangle r)359 sendrre(Vncs *v, Rectangle r)
360 {
361 return _sendrre(v, r, MaxRreDim, 0);
362 }
363
364 int
sendcorre(Vncs * v,Rectangle r)365 sendcorre(Vncs *v, Rectangle r)
366 {
367 return _sendrre(v, r, MaxCorreDim, 1);
368 }
369
370 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))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
findback(uchar * raw,int stride,int w,int h,int (* eqpix)(uchar *,int,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*
putrre(uchar * buf,uchar * raw,int p,int pixb,int x,int y,int w,int h)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*
putcorre(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)
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
eqpix8(uchar * raw,int p1,int p2)528 eqpix8(uchar *raw, int p1, int p2)
529 {
530 return raw[p1] == raw[p2];
531 }
532
533 static int
eqpix16(uchar * raw,int p1,int p2)534 eqpix16(uchar *raw, int p1, int p2)
535 {
536 return ((ushort*)raw)[p1] == ((ushort*)raw)[p2];
537 }
538
539 static int
eqpix32(uchar * raw,int p1,int p2)540 eqpix32(uchar *raw, int p1, int p2)
541 {
542 return ((ulong*)raw)[p1] == ((ulong*)raw)[p2];
543 }
544
545 static void
putpix(Vnc * v,uchar * raw,int p,int pixb)546 putpix(Vnc *v, uchar *raw, int p, int pixb)
547 {
548 vncwrbytes(v, raw + p * pixb, pixb);
549 }
550