rre.c

这是一个同样来自贝尔实验室的和UNIX有着渊源的操作系统, 其简洁的设计和实现易于我们学习和理解

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