Subversion Repositories planix.SVN

Rev

Rev 2 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 - 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 
}