draw.c

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

#include <u.h>
#include <libc.h>
#include <draw.h>
#include <memdraw.h>
#include <pool.h>

extern Pool* imagmem;
int drawdebug;
static int	tablesbuilt;

/* perfect approximation to NTSC = .299r+.587g+.114b when 0 ≤ r,g,b < 256 */
#define RGB2K(r,g,b)	((156763*(r)+307758*(g)+59769*(b))>>19)

/*
 * for 0 ≤ x ≤ 255*255, (x*0x0101+0x100)>>16 is a perfect approximation.
 * for 0 ≤ x < (1<<16), x/255 = ((x+1)*0x0101)>>16 is a perfect approximation.
 * the last one is perfect for all up to 1<<16, avoids a multiply, but requires a rathole.
 */
/* #define DIV255(x) (((x)*257+256)>>16)  */
#define DIV255(x) ((((x)+1)*257)>>16)
/* #define DIV255(x) (tmp=(x)+1, (tmp+(tmp>>8))>>8) */

#define MUL(x, y, t)	(t = (x)*(y)+128, (t+(t>>8))>>8)
#define MASK13	0xFF00FF00
#define MASK02	0x00FF00FF
#define MUL13(a, x, t)		(t = (a)*(((x)&MASK13)>>8)+128, ((t+((t>>8)&MASK02))>>8)&MASK02)
#define MUL02(a, x, t)		(t = (a)*(((x)&MASK02)>>0)+128, ((t+((t>>8)&MASK02))>>8)&MASK02)
#define MUL0123(a, x, s, t)	((MUL13(a, x, s)<<8)|MUL02(a, x, t))

#define MUL2(u, v, x, y)	(t = (u)*(v)+(x)*(y)+256, (t+(t>>8))>>8)

static void mktables(void);
typedef int Subdraw(Memdrawparam*);
static Subdraw chardraw, alphadraw, memoptdraw;

static Memimage*	memones;
static Memimage*	memzeros;
Memimage *memwhite;
Memimage *memblack;
Memimage *memtransparent;
Memimage *memopaque;

int	_ifmt(Fmt*);

void
memimageinit(void)
{
	static int didinit = 0;

	if(didinit)
		return;

	didinit = 1;

	if(strcmp(imagmem->name, "Image") == 0 || strcmp(imagmem->name, "image") == 0)
		imagmem->move = memimagemove;

	mktables();
	_memmkcmap();

	fmtinstall('R', Rfmt); 
	fmtinstall('P', Pfmt);
	fmtinstall('b', _ifmt);

	memones = allocmemimage(Rect(0,0,1,1), GREY1);
	memones->flags |= Frepl;
	memones->clipr = Rect(-0x3FFFFFF, -0x3FFFFFF, 0x3FFFFFF, 0x3FFFFFF);
	*byteaddr(memones, ZP) = ~0;

	memzeros = allocmemimage(Rect(0,0,1,1), GREY1);
	memzeros->flags |= Frepl;
	memzeros->clipr = Rect(-0x3FFFFFF, -0x3FFFFFF, 0x3FFFFFF, 0x3FFFFFF);
	*byteaddr(memzeros, ZP) = 0;

	if(memones == nil || memzeros == nil)
		assert(0 /*cannot initialize memimage library */);	/* RSC BUG */

	memwhite = memones;
	memblack = memzeros;
	memopaque = memones;
	memtransparent = memzeros;
}

static ulong imgtorgba(Memimage*, ulong);
static ulong rgbatoimg(Memimage*, ulong);
static ulong pixelbits(Memimage*, Point);

#define DBG if(0)
void
memimagedraw(Memimage *dst, Rectangle r, Memimage *src, Point p0, Memimage *mask, Point p1, int op)
{
	static int n = 0;
	Memdrawparam par;

	if(mask == nil)
		mask = memopaque;

DBG	print("memimagedraw %p/%luX %R @ %p %p/%luX %P %p/%luX %P... ", dst, dst->chan, r, dst->data->bdata, src, src->chan, p0, mask, mask->chan, p1);

	if(drawclip(dst, &r, src, &p0, mask, &p1, &par.sr, &par.mr) == 0){
//		if(drawdebug)
//			iprint("empty clipped rectangle\n");
		return;
	}

	if(op < Clear || op > SoverD){
//		if(drawdebug)
//			iprint("op out of range: %d\n", op);
		return;
	}

	par.op = op;
	par.dst = dst;
	par.r = r;
	par.src = src;
	/* par.sr set by drawclip */
	par.mask = mask;
	/* par.mr set by drawclip */

	par.state = 0;
	if(src->flags&Frepl){
		par.state |= Replsrc;
		if(Dx(src->r)==1 && Dy(src->r)==1){
			par.sval = pixelbits(src, src->r.min);
			par.state |= Simplesrc;
			par.srgba = imgtorgba(src, par.sval);
			par.sdval = rgbatoimg(dst, par.srgba);
			if((par.srgba&0xFF) == 0 && (op&DoutS)){
//				if (drawdebug) iprint("fill with transparent source\n");
				return;	/* no-op successfully handled */
			}
		}
	}

	if(mask->flags & Frepl){
		par.state |= Replmask;
		if(Dx(mask->r)==1 && Dy(mask->r)==1){
			par.mval = pixelbits(mask, mask->r.min);
			if(par.mval == 0 && (op&DoutS)){
//				if(drawdebug) iprint("fill with zero mask\n");
				return;	/* no-op successfully handled */
			}
			par.state |= Simplemask;
			if(par.mval == ~0)
				par.state |= Fullmask;
			par.mrgba = imgtorgba(mask, par.mval);
		}
	}

//	if(drawdebug)
//		iprint("dr %R sr %R mr %R...", r, par.sr, par.mr);
DBG print("draw dr %R sr %R mr %R %lux\n", r, par.sr, par.mr, par.state);

	/*
	 * Now that we've clipped the parameters down to be consistent, we 
	 * simply try sub-drawing routines in order until we find one that was able
	 * to handle us.  If the sub-drawing routine returns zero, it means it was
	 * unable to satisfy the request, so we do not return.
	 */

	/*
	 * Hardware support.  Each video driver provides this function,
	 * which checks to see if there is anything it can help with.
	 * There could be an if around this checking to see if dst is in video memory.
	 */
DBG print("test hwdraw\n");
	if(hwdraw(&par)){
//if(drawdebug) iprint("hw handled\n");
DBG print("hwdraw handled\n");
		return;
	}
	/*
	 * Optimizations using memmove and memset.
	 */
DBG print("test memoptdraw\n");
	if(memoptdraw(&par)){
//if(drawdebug) iprint("memopt handled\n");
DBG print("memopt handled\n");
		return;
	}

	/*
	 * Character drawing.
	 * Solid source color being painted through a boolean mask onto a high res image.
	 */
DBG print("test chardraw\n");
	if(chardraw(&par)){
//if(drawdebug) iprint("chardraw handled\n");
DBG print("chardraw handled\n");
		return;
	}

	/*
	 * General calculation-laden case that does alpha for each pixel.
	 */
DBG print("do alphadraw\n");
	alphadraw(&par);
//if(drawdebug) iprint("alphadraw handled\n");
DBG print("alphadraw handled\n");
}
#undef DBG

/*
 * Clip the destination rectangle further based on the properties of the 
 * source and mask rectangles.  Once the destination rectangle is properly
 * clipped, adjust the source and mask rectangles to be the same size.
 * Then if source or mask is replicated, move its clipped rectangle
 * so that its minimum point falls within the repl rectangle.
 *
 * Return zero if the final rectangle is null.
 */
int
drawclip(Memimage *dst, Rectangle *r, Memimage *src, Point *p0, Memimage *mask, Point *p1, Rectangle *sr, Rectangle *mr)
{
	Point rmin, delta;
	int splitcoords;
	Rectangle omr;

	if(r->min.x>=r->max.x || r->min.y>=r->max.y)
		return 0;
	splitcoords = (p0->x!=p1->x) || (p0->y!=p1->y);
	/* clip to destination */
	rmin = r->min;
	if(!rectclip(r, dst->r) || !rectclip(r, dst->clipr))
		return 0;
	/* move mask point */
	p1->x += r->min.x-rmin.x;
	p1->y += r->min.y-rmin.y;
	/* move source point */
	p0->x += r->min.x-rmin.x;
	p0->y += r->min.y-rmin.y;
	/* map destination rectangle into source */
	sr->min = *p0;
	sr->max.x = p0->x+Dx(*r);
	sr->max.y = p0->y+Dy(*r);
	/* sr is r in source coordinates; clip to source */
	if(!(src->flags&Frepl) && !rectclip(sr, src->r))
		return 0;
	if(!rectclip(sr, src->clipr))
		return 0;
	/* compute and clip rectangle in mask */
	if(splitcoords){
		/* move mask point with source */
		p1->x += sr->min.x-p0->x;
		p1->y += sr->min.y-p0->y;
		mr->min = *p1;
		mr->max.x = p1->x+Dx(*sr);
		mr->max.y = p1->y+Dy(*sr);
		omr = *mr;
		/* mr is now rectangle in mask; clip it */
		if(!(mask->flags&Frepl) && !rectclip(mr, mask->r))
			return 0;
		if(!rectclip(mr, mask->clipr))
			return 0;
		/* reflect any clips back to source */
		sr->min.x += mr->min.x-omr.min.x;
		sr->min.y += mr->min.y-omr.min.y;
		sr->max.x += mr->max.x-omr.max.x;
		sr->max.y += mr->max.y-omr.max.y;
		*p1 = mr->min;
	}else{
		if(!(mask->flags&Frepl) && !rectclip(sr, mask->r))
			return 0;
		if(!rectclip(sr, mask->clipr))
			return 0;
		*p1 = sr->min;
	}

	/* move source clipping back to destination */
	delta.x = r->min.x - p0->x;
	delta.y = r->min.y - p0->y;
	r->min.x = sr->min.x + delta.x;
	r->min.y = sr->min.y + delta.y;
	r->max.x = sr->max.x + delta.x;
	r->max.y = sr->max.y + delta.y;

	/* move source rectangle so sr->min is in src->r */
	if(src->flags&Frepl) {
		delta.x = drawreplxy(src->r.min.x, src->r.max.x, sr->min.x) - sr->min.x;
		delta.y = drawreplxy(src->r.min.y, src->r.max.y, sr->min.y) - sr->min.y;
		sr->min.x += delta.x;
		sr->min.y += delta.y;
		sr->max.x += delta.x;
		sr->max.y += delta.y;
	}
	*p0 = sr->min;

	/* move mask point so it is in mask->r */
	*p1 = drawrepl(mask->r, *p1);
	mr->min = *p1;
	mr->max.x = p1->x+Dx(*sr);
	mr->max.y = p1->y+Dy(*sr);

	assert(Dx(*sr) == Dx(*mr) && Dx(*mr) == Dx(*r));
	assert(Dy(*sr) == Dy(*mr) && Dy(*mr) == Dy(*r));
	assert(ptinrect(*p0, src->r));
	assert(ptinrect(*p1, mask->r));
	assert(ptinrect(r->min, dst->r));

	return 1;
}

/*
 * Conversion tables.
 */
static uchar replbit[1+8][256];		/* replbit[x][y] is the replication of the x-bit quantity y to 8-bit depth */
static uchar conv18[256][8];		/* conv18[x][y] is the yth pixel in the depth-1 pixel x */
static uchar conv28[256][4];		/* ... */
static uchar conv48[256][2];

/*
 * bitmap of how to replicate n bits to fill 8, for 1 ≤ n ≤ 8.
 * the X's are where to put the bottom (ones) bit of the n-bit pattern.
 * only the top 8 bits of the result are actually used.
 * (the lower 8 bits are needed to get bits in the right place
 * when n is not a divisor of 8.)
 *
 * Should check to see if its easier to just refer to replmul than
 * use the precomputed values in replbit.  On PCs it may well
 * be; on machines with slow multiply instructions it probably isn't.
 */
#define a ((((((((((((((((0
#define X *2+1)
#define _ *2)
static int replmul[1+8] = {
	0,
	a X X X X X X X X X X X X X X X X,
	a _ X _ X _ X _ X _ X _ X _ X _ X,
	a _ _ X _ _ X _ _ X _ _ X _ _ X _,
	a _ _ _ X _ _ _ X _ _ _ X _ _ _ X,
	a _ _ _ _ X _ _ _ _ X _ _ _ _ X _,
	a _ _ _ _ _ X _ _ _ _ _ X _ _ _ _, 
	a _ _ _ _ _ _ X _ _ _ _ _ _ X _ _,
	a _ _ _ _ _ _ _ X _ _ _ _ _ _ _ X,
};
#undef a
#undef X
#undef _

static void
mktables(void)
{
	int i, j, mask, sh, small;
		
	if(tablesbuilt)
		return;

	fmtinstall('R', Rfmt);
	fmtinstall('P', Pfmt);
	tablesbuilt = 1;

	/* bit replication up to 8 bits */
	for(i=0; i<256; i++){
		for(j=0; j<=8; j++){	/* j <= 8 [sic] */
			small = i & ((1<<j)-1);
			replbit[j][i] = (small*replmul[j])>>8;
		}
	}

	/* bit unpacking up to 8 bits, only powers of 2 */
	for(i=0; i<256; i++){
		for(j=0, sh=7, mask=1; j<8; j++, sh--)
			conv18[i][j] = replbit[1][(i>>sh)&mask];

		for(j=0, sh=6, mask=3; j<4; j++, sh-=2)
			conv28[i][j] = replbit[2][(i>>sh)&mask];

		for(j=0, sh=4, mask=15; j<2; j++, sh-=4)
			conv48[i][j] = replbit[4][(i>>sh)&mask];
	}
}

static uchar ones = 0xff;

/*
 * General alpha drawing case.  Can handle anything.
 */
typedef struct	Buffer	Buffer;
struct Buffer {
	/* used by most routines */
	uchar	*red;
	uchar	*grn;
	uchar	*blu;
	uchar	*alpha;
	uchar	*grey;
	ulong	*rgba;
	int	delta;	/* number of bytes to add to pointer to get next pixel to the right */

	/* used by boolcalc* for mask data */
	uchar	*m;		/* ptr to mask data r.min byte; like p->bytermin */
	int		mskip;	/* no. of left bits to skip in *m */
	uchar	*bm;		/* ptr to mask data img->r.min byte; like p->bytey0s */
	int		bmskip;	/* no. of left bits to skip in *bm */
	uchar	*em;		/* ptr to mask data img->r.max.x byte; like p->bytey0e */
	int		emskip;	/* no. of right bits to skip in *em */
};

typedef struct	Param	Param;
typedef Buffer	Readfn(Param*, uchar*, int);
typedef void	Writefn(Param*, uchar*, Buffer);
typedef Buffer	Calcfn(Buffer, Buffer, Buffer, int, int, int);

enum {
	MAXBCACHE = 16
};

/* giant rathole to customize functions with */
struct Param {
	Readfn	*replcall;
	Readfn	*greymaskcall;	
	Readfn	*convreadcall;
	Writefn	*convwritecall;

	Memimage *img;
	Rectangle	r;
	int	dx;	/* of r */
	int	needbuf;
	int	convgrey;
	int	alphaonly;

	uchar	*bytey0s;		/* byteaddr(Pt(img->r.min.x, img->r.min.y)) */
	uchar	*bytermin;	/* byteaddr(Pt(r.min.x, img->r.min.y)) */
	uchar	*bytey0e;		/* byteaddr(Pt(img->r.max.x, img->r.min.y)) */
	int		bwidth;

	int	replcache;	/* if set, cache buffers */
	Buffer	bcache[MAXBCACHE];
	ulong	bfilled;
	uchar	*bufbase;
	int	bufoff;
	int	bufdelta;

	int	dir;

	int	convbufoff;
	uchar	*convbuf;
	Param	*convdpar;
	int	convdx;
};

static uchar *drawbuf;
static int	ndrawbuf;
static int	mdrawbuf;
static Readfn	greymaskread, replread, readptr;
static Writefn	nullwrite;
static Calcfn	alphacalc0, alphacalc14, alphacalc2810, alphacalc3679, alphacalc5, alphacalc11, alphacalcS;
static Calcfn	boolcalc14, boolcalc236789, boolcalc1011;

static Readfn*	readfn(Memimage*);
static Readfn*	readalphafn(Memimage*);
static Writefn*	writefn(Memimage*);

static Calcfn*	boolcopyfn(Memimage*, Memimage*);
static Readfn*	convfn(Memimage*, Param*, Memimage*, Param*, int*);
static Readfn*	ptrfn(Memimage*);

static Calcfn *alphacalc[Ncomp] = 
{
	alphacalc0,		/* Clear */
	alphacalc14,		/* DoutS */
	alphacalc2810,		/* SoutD */
	alphacalc3679,		/* DxorS */
	alphacalc14,		/* DinS */
	alphacalc5,		/* D */
	alphacalc3679,		/* DatopS */
	alphacalc3679,		/* DoverS */
	alphacalc2810,		/* SinD */
	alphacalc3679,		/* SatopD */
	alphacalc2810,		/* S */
	alphacalc11,		/* SoverD */
};

static Calcfn *boolcalc[Ncomp] =
{
	alphacalc0,		/* Clear */
	boolcalc14,		/* DoutS */
	boolcalc236789,		/* SoutD */
	boolcalc236789,		/* DxorS */
	boolcalc14,		/* DinS */
	alphacalc5,		/* D */
	boolcalc236789,		/* DatopS */
	boolcalc236789,		/* DoverS */
	boolcalc236789,		/* SinD */
	boolcalc236789,		/* SatopD */
	boolcalc1011,		/* S */
	boolcalc1011,		/* SoverD */
};

/*
 * Avoid standard Lock, QLock so that can be used in kernel.
 */
typedef struct Dbuf Dbuf;
struct Dbuf
{
	uchar *p;
	int n;
	Param spar, mpar, dpar;
	int inuse;
};
static Dbuf dbuf[10];

static Dbuf*
allocdbuf(void)
{
	int i;

	for(i=0; i<nelem(dbuf); i++){
		if(dbuf[i].inuse)
			continue;
		if(!_tas(&dbuf[i].inuse))
			return &dbuf[i];
	}
	return nil;
}

static void
getparam(Param *p, Memimage *img, Rectangle r, int convgrey, int needbuf, int *ndrawbuf)
{
	int nbuf;

	memset(p, 0, sizeof *p);

	p->img = img;
	p->r = r;
	p->dx = Dx(r);
	p->needbuf = needbuf;
	p->convgrey = convgrey;

	assert(img->r.min.x <= r.min.x && r.min.x < img->r.max.x);

	p->bytey0s = byteaddr(img, Pt(img->r.min.x, img->r.min.y));
	p->bytermin = byteaddr(img, Pt(r.min.x, img->r.min.y));
	p->bytey0e = byteaddr(img, Pt(img->r.max.x, img->r.min.y));
	p->bwidth = sizeof(ulong)*img->width;

	assert(p->bytey0s <= p->bytermin && p->bytermin <= p->bytey0e);

	if(p->r.min.x == p->img->r.min.x)
		assert(p->bytermin == p->bytey0s);

	nbuf = 1;
	if((img->flags&Frepl) && Dy(img->r) <= MAXBCACHE && Dy(img->r) < Dy(r)){
		p->replcache = 1;
		nbuf = Dy(img->r);
	}
	p->bufdelta = 4*p->dx;
	p->bufoff = *ndrawbuf;
	*ndrawbuf += p->bufdelta*nbuf;
}

static void
clipy(Memimage *img, int *y)
{
	int dy;

	dy = Dy(img->r);
	if(*y == dy)
		*y = 0;
	else if(*y == -1)
		*y = dy-1;
	assert(0 <= *y && *y < dy);
}

static void
dumpbuf(char *s, Buffer b, int n)
{
	int i;
	uchar *p;
	
	print("%s", s);
	for(i=0; i<n; i++){
		print(" ");
		if(p=b.grey){
			print(" k%.2uX", *p);
			b.grey += b.delta;
		}else{	
			if(p=b.red){
				print(" r%.2uX", *p);
				b.red += b.delta;
			}
			if(p=b.grn){
				print(" g%.2uX", *p);
				b.grn += b.delta;
			}
			if(p=b.blu){
				print(" b%.2uX", *p);
				b.blu += b.delta;
			}
		}
		if((p=b.alpha) != &ones){
			print(" α%.2uX", *p);
			b.alpha += b.delta;
		}
	}
	print("\n");
}

/*
 * For each scan line, we expand the pixels from source, mask, and destination
 * into byte-aligned red, green, blue, alpha, and grey channels.  If buffering is not
 * needed and the channels were already byte-aligned (grey8, rgb24, rgba32, rgb32),
 * the readers need not copy the data: they can simply return pointers to the data.
 * If the destination image is grey and the source is not, it is converted using the NTSC
 * formula.
 *
 * Once we have all the channels, we call either rgbcalc or greycalc, depending on 
 * whether the destination image is color.  This is allowed to overwrite the dst buffer (perhaps
 * the actual data, perhaps a copy) with its result.  It should only overwrite the dst buffer
 * with the same format (i.e. red bytes with red bytes, etc.)  A new buffer is returned from
 * the calculator, and that buffer is passed to a function to write it to the destination.
 * If the buffer is already pointing at the destination, the writing function is a no-op.
 */
#define DBG if(0)
static int
alphadraw(Memdrawparam *par)
{
	int isgrey, starty, endy, op;
	int needbuf, dsty, srcy, masky;
	int y, dir, dx, dy, ndrawbuf;
	uchar *drawbuf;
	Buffer bsrc, bdst, bmask;
	Readfn *rdsrc, *rdmask, *rddst;
	Calcfn *calc;
	Writefn *wrdst;
	Memimage *src, *mask, *dst;
	Rectangle r, sr, mr;
	Dbuf *z;

	r = par->r;
	dx = Dx(r);