xref: /plan9/sys/src/cmd/gs/src/gdevifno.c (revision 593dc095aefb2a85c828727bbfa9da139a49bdf4)

/*
 *		Copyright (c) 1998 by Lucent Technologies.
 * Permission to use, copy, modify, and distribute this software for any
 * purpose without fee is hereby granted, provided that this entire notice
 * is included in all copies of any software which is or includes a copy
 * or modification of this software.
 *
 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHORS NOR LUCENT TECHNOLOGIES MAKE ANY
 * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
 * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
 */

/*
 * gdevifno.c: gs device to generate inferno bitmaps
 * Russ Cox <rsc@plan9.bell-labs.com>, 3/25/98
 * Updated to fit in the standard GS distribution, 5/14/98
 */

#include "gdevprn.h"
#include "gsparam.h"
#include "gxlum.h"
#include <stdlib.h>
#undef printf

#define nil ((void*)0)
enum {
	ERROR = -2
};

typedef struct WImage WImage;
typedef struct Rectangle Rectangle;
typedef struct Point Point;

struct Point {
	int x;
	int y;
};

struct Rectangle {
	Point min;
	Point max;
};
private Point ZP = { 0, 0 };

private WImage* initwriteimage(FILE *f, Rectangle r, int ldepth);
private int writeimageblock(WImage *w, uchar *data, int ndata);
private int bytesperline(Rectangle, int);
private int rgb2cmap(int, int, int);
private long cmap2rgb(int);

#define X_DPI	100
#define Y_DPI	100

private dev_proc_map_rgb_color(inferno_rgb2cmap);
private dev_proc_map_color_rgb(inferno_cmap2rgb);
private dev_proc_open_device(inferno_open);
private dev_proc_close_device(inferno_close);
private dev_proc_print_page(inferno_print_page);
private dev_proc_put_params(inferno_put_params);
private dev_proc_get_params(inferno_get_params);

typedef struct inferno_device_s {
	gx_device_common;
	gx_prn_device_common;
	int dither;

	int ldepth;
	int lastldepth;
	int cmapcall;
} inferno_device;

enum {
	Nbits = 8,
	Bitmask = (1<<Nbits)-1,
};

private const gx_device_procs inferno_procs =
	prn_color_params_procs(inferno_open, gdev_prn_output_page, gdev_prn_close,
		inferno_rgb2cmap, inferno_cmap2rgb,
		gdev_prn_get_params, gdev_prn_put_params);
/*
		inferno_get_params, inferno_put_params);
*/


inferno_device far_data gs_inferno_device =
{ prn_device_body(inferno_device, inferno_procs, "inferno",
	DEFAULT_WIDTH_10THS, DEFAULT_HEIGHT_10THS,
	X_DPI, Y_DPI,
	0,0,0,0,	/* margins */
	3,		/* 3 = RGB, 1 = gray, 4 = CMYK */
	Nbits*3,		/* # of bits per pixel */
	(1<<Nbits)-1,		/* # of distinct gray levels. */
	(1<<Nbits)-1,		/* # of distinct color levels. */
	1<<Nbits,		/* dither gray ramp size.  used in alpha? */
	1<<Nbits,    	/* dither color ramp size.  used in alpha? */
	inferno_print_page),
	1,
};

/*
 * ghostscript asks us how to convert between
 * rgb and color map entries
 */
private gx_color_index
inferno_rgb2cmap(gx_device *dev, gx_color_value rgb[3]) {
	int shift;
	inferno_device *idev;
	ulong red, green, blue;

	idev = (inferno_device*) dev;

	shift = gx_color_value_bits - Nbits;
	red = rgb[0] >> shift;
	green = rgb[1] >> shift;
	blue = rgb[2] >> shift;

	/*
	 * we keep track of what ldepth bitmap this is by watching
	 * what colors gs asks for.
	 *
	 * one catch: sometimes print_page gets called more than one
	 * per page (for multiple copies) without cmap calls inbetween.
	 * if idev->cmapcall is 0 when print_page gets called, it uses
	 * the ldepth of the last page.
	 */
	if(red == green && green == blue) {
		if(red == 0 || red == Bitmask)
			;
		else if(red == Bitmask/3 || red == 2*Bitmask/3) {
			if(idev->ldepth < 1)
				idev->ldepth = 1;
		} else {
			if(idev->ldepth < 2)
				idev->ldepth = 2;
		}
	} else
		idev->ldepth = 3;

	idev->cmapcall = 1;
	return (blue << (2*Nbits)) | (green << Nbits) | red;
}

private int
inferno_cmap2rgb(gx_device *dev, gx_color_index color,
  gx_color_value rgb[3]) {
	int shift, i;
	inferno_device *idev;

	if((ulong)color > 0xFFFFFF)
		return_error(gs_error_rangecheck);

	idev = (inferno_device*) dev;
	shift = gx_color_value_bits - Nbits;

	rgb[2] = ((color >> (2*Nbits)) & Bitmask) << shift;
	rgb[1] = ((color >> Nbits) & Bitmask) << shift;
	rgb[0] = (color & Bitmask) << shift;

	return 0;
}

private int
inferno_put_param_int(gs_param_list *plist, gs_param_name pname, int *pv,
	int minval, int maxval, int ecode)
{
	int code, value;
	switch(code = param_read_int(plist, pname, &value)) {
	default:
		return code;

	case 1:
		return ecode;

	case 0:
		if(value < minval || value > maxval)
			param_signal_error(plist, pname, gs_error_rangecheck);
		*pv = value;
		return (ecode < 0 ? ecode : 1);
	}
}

private int
inferno_get_params(gx_device *pdev, gs_param_list *plist)
{
	int code;
	inferno_device *idev;

	idev = (inferno_device*) pdev;
//	printf("inferno_get_params dither %d\n", idev->dither);

	if((code = gdev_prn_get_params(pdev, plist)) < 0
	 || (code = param_write_int(plist, "Dither", &idev->dither)) < 0)
		return code;
	printf("getparams: dither=%d\n", idev->dither);
	return code;
}

private int
inferno_put_params(gx_device * pdev, gs_param_list * plist)
{
	int code;
	int dither;
	inferno_device *idev;

	printf("inferno_put_params\n");

	idev = (inferno_device*)pdev;
	dither = idev->dither;

	code = inferno_put_param_int(plist, "Dither", &dither, 0, 1, 0);
	if(code < 0)
		return code;

	idev->dither = dither;
	return 0;
}

/*
 * dithering tables courtesy of john hobby
 */
/* The following constants and tables define the mapping from fine-grained RGB
   triplets to 8-bit values based on the standard Plan 9 color map.
*/
#define Rlevs	16		/* number of levels to cut red value into */
#define Glevs	16
#define Blevs	16
#define Mlevs	16
#define Rfactor 1		/* multiple of red level in p9color[] index */
#define Gfactor Rlevs
#define Bfactor	(Rlevs*Glevs)

ulong p9color[Rlevs*Glevs*Blevs];	/* index blue most sig, red least sig */

void init_p9color(void)		/* init at run time since p9color[] is so big */
{
	int r, g, b, o;
	ulong* cur = p9color;
	for (b=0; b<16; b++) {
	    for (g=0; g<16; g++) {
		int m0 = (b>g) ? b : g;
		for (r=0; r<16; r++) {
		    int V, M, rM, gM, bM, m;
		    int m1 = (r>m0) ? r : m0;
		    V=m1&3; M=(m1-V)<<1;
		    if (m1==0) m1=1;
		    m = m1 << 3;
		    rM=r*M; gM=g*M; bM=b*M;
		    *cur = 0;
		    for (o=7*m1; o>0; o-=2*m1) {
			int rr=(rM+o)/m, gg=(gM+o)/m, bb=(bM+o)/m;
			int ij = (rr<<6) + (V<<4) + ((V-rr+(gg<<2)+bb)&15);
			*cur = (*cur << 8) + 255-ij;
		    }
		    cur++;
		}
	    }
	}
}

/*
 * inferno_open() is supposed to initialize the device.
 * there's not much to do.
 */
private int
inferno_open(gx_device *dev)
{
	int code;
	inferno_device *idev;

	idev = (inferno_device*) dev;
	idev->cmapcall = 0;
	idev->ldepth = 0;

//	printf("inferno_open gs_inferno_device.dither = %d idev->dither = %d\n",
//		gs_inferno_device.dither, idev->dither);
	init_p9color();

	return gdev_prn_open(dev);
}

/*
 * inferno_print_page() is called once for each page
 * (actually once for each copy of each page, but we won't
 * worry about that).
 */
private int
inferno_print_page(gx_device_printer *pdev, FILE *f)
{
	uchar *buf;	/* [8192*3*8/Nbits] BUG: malloc this */
	uchar *p;
	WImage *w;
	int bpl, y;
	int x, xmod;
	int ldepth;
	int ppb[] = {8, 4, 2, 1};	/* pixels per byte */
	int bpp[] = {1, 2, 4, 8};	/* bits per pixel */
	int gsbpl;
	int dither;
	ulong u;
	ushort us;
	Rectangle rect;
	inferno_device *idev;
	ulong r, g, b;

	gsbpl = gdev_prn_raster(pdev);
	buf = gs_malloc(pdev->memory, gsbpl, 1, "inferno_print_page");

	if(buf == nil) {
		errprintf("out of memory\n");
		return_error(gs_error_Fatal);
	}

	idev = (inferno_device *) pdev;
	if(idev->cmapcall) {
		idev->lastldepth = idev->ldepth;
		idev->ldepth = 0;
		idev->cmapcall = 0;
	}
	ldepth = idev->lastldepth;
	dither = idev->dither;

	if(pdev->color_info.anti_alias.graphics_bits || pdev->color_info.anti_alias.text_bits)
		if(ldepth < 2)
			ldepth = 2;

//	printf("inferno_print_page dither %d ldepth %d idither %d\n", dither, ldepth, gs_inferno_device.dither);
	rect.min = ZP;
	rect.max.x = pdev->width;
	rect.max.y = pdev->height;
	bpl = bytesperline(rect, ldepth);
	w = initwriteimage(f, rect, ldepth);
	if(w == nil) {
		errprintf("initwriteimage failed\n");
		return_error(gs_error_Fatal);
	}

	/*
	 * i wonder if it is faster to put the switch around the for loops
	 * to save all the ldepth lookups.
	 */
	for(y=0; y<pdev->height; y++) {
		gdev_prn_get_bits(pdev, y, buf, &p);
		for(x=0; x<pdev->width; x++) {
			b = p[3*x];
			g = p[3*x+1];
			r = p[3*x+2];
			us = ((b>>4) << 8) | ((g>>4) << 4) | (r>>4);
			switch(ldepth) {
			case 3:
				if(1 || dither){
					u = p9color[us];
					/* the ulong in p9color is a 2x2 matrix.  pull the entry
					 * u[x%2][y%2], more or less.
					 */
					p[x] = u >> (8*((y%2)+2*(x%2)));
				} else {
					p[x] = rgb2cmap(r, g, b);
				}
				break;
			case 2:
				us = ~us;
				if((x%2) == 0)
					p[x/2] = us & 0xf;
				else
					p[x/2] = (p[x/2]<<4)|(us&0xf);
				break;
			case 1:
				return_error(gs_error_Fatal);
			case 0:
				us = ~us;
				if((x%8) == 0)
					p[x/8] = us & 0x1;
				else
					p[x/8] = (p[x/8]<<1)|(us&0x1);
				break;
			}
		}

		/* pad last byte over if we didn't fill it */
		xmod = pdev->width % ppb[ldepth];
		if(xmod)
			p[(x-1)/ppb[ldepth]] <<= ((ppb[ldepth]-xmod)*bpp[ldepth]);
		if(writeimageblock(w, p, bpl) == ERROR) {
			gs_free(pdev->memory, buf, gsbpl, 1, "inferno_print_page");
			return_error(gs_error_Fatal);
		}
	}
	if(writeimageblock(w, nil, 0) == ERROR) {
		gs_free(pdev->memory, buf, gsbpl, 1, "inferno_print_page");
		return_error(gs_error_Fatal);
	}

	gs_free(pdev->memory, buf, gsbpl, 1, "inferno_print_page");
	return 0;
}

/*
 * this is a modified version of the image compressor
 * from fb/bit2enc.  it is modified only in that it
 * now compiles as part of gs.
 */

/*
 * Compressed image file parameters
 */
#define	NMATCH	3		/* shortest match possible */
#define	NRUN	(NMATCH+31)	/* longest match possible */
#define	NMEM	1024		/* window size */
#define	NDUMP	128		/* maximum length of dump */
#define	NCBLOCK	6000		/* size of compressed blocks */

#define	HSHIFT	3	/* HSHIFT==5 runs slightly faster, but hash table is 64x bigger */
#define	NHASH	(1<<(HSHIFT*NMATCH))
#define	HMASK	(NHASH-1)
#define	hupdate(h, c)	((((h)<<HSHIFT)^(c))&HMASK)

typedef struct Dump	Dump;
typedef struct Hlist Hlist;

struct Hlist{
	ulong p;
	Hlist *next, *prev;
};

struct Dump {
	int ndump;
	uchar *dumpbuf;
	uchar buf[1+NDUMP];
};

struct WImage {
	FILE *f;

	/* image attributes */
	Rectangle origr, r;
	int bpl;

	/* output buffer */
	uchar outbuf[NCBLOCK], *outp, *eout, *loutp;

	/* sliding input window */
	/*
	 * ibase is the pointer to where the beginning of
	 * the input "is" in memory.  whenever we "slide" the
	 * buffer N bytes, what we are actually doing is
	 * decrementing ibase by N.
	 * the ulongs in the Hlist structures are just
	 * pointers relative to ibase.
	 */
	uchar *inbuf;	/* inbuf should be at least NMEM+NRUN+NMATCH long */
	uchar *ibase;
	int minbuf;	/* size of inbuf (malloc'ed bytes) */
	int ninbuf;	/* size of inbuf (filled bytes) */
	ulong line;	/* the beginning of the line we are currently encoding,
			 * relative to inbuf (NOT relative to ibase) */

	/* raw dump buffer */
	Dump dump;

	/* hash tables */
	Hlist hash[NHASH];
	Hlist chain[NMEM], *cp;
	int h;
	int needhash;
};

private void
zerohash(WImage *w)
{
	memset(w->hash, 0, sizeof(w->hash));
	memset(w->chain, 0, sizeof(w->chain));
	w->cp=w->chain;
	w->needhash = 1;
}

private int
addbuf(WImage *w, uchar *buf, int nbuf)
{
	int n;
	if(buf == nil || w->outp+nbuf > w->eout) {
		if(w->loutp==w->outbuf){	/* can't really happen -- we checked line length above */
			errprintf("buffer too small for line\n");
			return ERROR;
		}
		n=w->loutp-w->outbuf;
		fprintf(w->f, "%11d %11d ", w->r.max.y, n);
		fwrite(w->outbuf, 1, n, w->f);
		w->r.min.y=w->r.max.y;
		w->outp=w->outbuf;
		w->loutp=w->outbuf;
		zerohash(w);
		return -1;
	}

	memmove(w->outp, buf, nbuf);
	w->outp += nbuf;
	return nbuf;
}

/* return 0 on success, -1 if buffer is full */
private int
flushdump(WImage *w)
{
	int n = w->dump.ndump;

	if(n == 0)
		return 0;

	w->dump.buf[0] = 0x80|(n-1);
	if((n=addbuf(w, w->dump.buf, n+1)) == ERROR)
		return ERROR;
	if(n < 0)
		return -1;
	w->dump.ndump = 0;
	return 0;
}

private void
updatehash(WImage *w, uchar *p, uchar *ep)
{
	uchar *q;
	Hlist *cp;
	Hlist *hash;
	int h;

	hash = w->hash;
	cp = w->cp;
	h = w->h;
	for(q=p; q<ep; q++) {
		if(cp->prev)
			cp->prev->next = cp->next;
		cp->next = hash[h].next;
		cp->prev = &hash[h];
		cp->prev->next = cp;
		if(cp->next)
			cp->next->prev = cp;
		cp->p = q - w->ibase;
		if(++cp == w->chain+NMEM)
			cp = w->chain;
		if(&q[NMATCH] < &w->inbuf[w->ninbuf])
			h = hupdate(h, q[NMATCH]);
	}
	w->cp = cp;
	w->h = h;
}

/*
 * attempt to process a line of input,
 * returning the number of bytes actually processed.
 *
 * if the output buffer needs to be flushed, we flush
 * the buffer and return 0.
 * otherwise we return bpl
 */
private int
gobbleline(WImage *w)
{
	int runlen, n, offs;
	uchar *eline, *es, *best, *p, *s, *t;
	Hlist *hp;
	uchar buf[2];
	int rv;

	if(w->needhash) {
		w->h = 0;
		for(n=0; n!=NMATCH; n++)
			w->h = hupdate(w->h, w->inbuf[w->line+n]);
		w->needhash = 0;
	}
	w->dump.ndump=0;
	eline=w->inbuf+w->line+w->bpl;
	for(p=w->inbuf+w->line;p!=eline;){
		es = (eline < p+NRUN) ? eline : p+NRUN;

		best=nil;
		runlen=0;
		/* hash table lookup */
		for(hp=w->hash[w->h].next;hp;hp=hp->next){
			/*
			 * the next block is an optimization of
			 * for(s=p, t=w->ibase+hp->p; s<es && *s == *t; s++, t++)
			 * 	;
			 */

			{	uchar *ss, *tt;
				s = p+runlen;
				t = w->ibase+hp->p+runlen;
				for(ss=s, tt=t; ss>=p && *ss == *tt; ss--, tt--)
					;
				if(ss < p)
					while(s<es && *s == *t)
						s++, t++;
			}

			n = s-p;

			if(n > runlen) {
				runlen = n;
				best = w->ibase+hp->p;
				if(p+runlen == es)
					break;
			}
		}

		/*
		 * if we didn't find a long enough run, append to
		 * the raw dump buffer
		 */
		if(runlen<NMATCH){
			if(w->dump.ndump==NDUMP) {
				if((rv = flushdump(w)) == ERROR)
					return ERROR;
				if(rv < 0)
					return 0;
			}
			w->dump.dumpbuf[w->dump.ndump++]=*p;
			runlen=1;
		}else{
		/*
		 * otherwise, assuming the dump buffer is empty,
		 * add the compressed rep.
		 */
			if((rv = flushdump(w)) == ERROR)
				return ERROR;
			if(rv < 0)
				return 0;
			offs=p-best-1;
			buf[0] = ((runlen-NMATCH)<<2)|(offs>>8);
			buf[1] = offs&0xff;
			if(addbuf(w, buf, 2) < 0)
				return 0;
		}

		/*
		 * add to hash tables what we just encoded
		 */
		updatehash(w, p, p+runlen);
		p += runlen;
	}

	if((rv = flushdump(w)) == ERROR)
		return ERROR;
	if(rv < 0)
		return 0;
	w->line += w->bpl;
	w->loutp=w->outp;
	w->r.max.y++;
	return w->bpl;
}

private uchar*
shiftwindow(WImage *w, uchar *data, uchar *edata)
{
	int n, m;

	/* shift window over */
	if(w->line > NMEM) {
		n = w->line-NMEM;
		memmove(w->inbuf, w->inbuf+n, w->ninbuf-n);
		w->line -= n;
		w->ibase -= n;
		w->ninbuf -= n;
	}

	/* fill right with data if available */
	if(w->minbuf > w->ninbuf && edata > data) {
		m = w->minbuf - w->ninbuf;
		if(edata-data < m)
			m = edata-data;
		memmove(w->inbuf+w->ninbuf, data, m);
		data += m;
		w->ninbuf += m;
	}

	return data;
}

private WImage*
initwriteimage(FILE *f, Rectangle r, int ldepth)
{
	WImage *w;
	int n, bpl;

	bpl = bytesperline(r, ldepth);
	if(r.max.y <= r.min.y || r.max.x <= r.min.x || bpl <= 0) {
		errprintf("bad rectangle, ldepth");
		return nil;
	}

	n = NMEM+NMATCH+NRUN+bpl*2;
	w = malloc(n+sizeof(*w));
	if(w == nil)
		return nil;
	w->inbuf = (uchar*) &w[1];
	w->ibase = w->inbuf;
	w->line = 0;
	w->minbuf = n;
	w->ninbuf = 0;
	w->origr = r;
	w->r = r;
	w->r.max.y = w->r.min.y;
	w->eout = w->outbuf+sizeof(w->outbuf);
	w->outp = w->loutp = w->outbuf;
	w->bpl = bpl;
	w->f = f;
	w->dump.dumpbuf = w->dump.buf+1;
	w->dump.ndump = 0;
	zerohash(w);

	fprintf(f, "compressed\n%11d %11d %11d %11d %11d ",
		ldepth, r.min.x, r.min.y, r.max.x, r.max.y);
	return w;
}

private int
writeimageblock(WImage *w, uchar *data, int ndata)
{
	uchar *edata;

	if(data == nil) {	/* end of data, flush everything */
		while(w->line < w->ninbuf)
			if(gobbleline(w) == ERROR)
				return ERROR;
		addbuf(w, nil, 0);
		if(w->r.min.y != w->origr.max.y) {
			errprintf("not enough data supplied to writeimage\n");
		}
		free(w);
		return 0;
	}

	edata = data+ndata;
	data = shiftwindow(w, data, edata);
	while(w->ninbuf >= w->line+w->bpl+NMATCH) {
		if(gobbleline(w) == ERROR)
			return ERROR;
		data = shiftwindow(w, data, edata);
	}
	if(data != edata) {
		fprintf(w->f, "data != edata.  uh oh\n");
		return ERROR; /* can't happen */
	}
	return 0;
}

/*
 * functions from the Plan9/Brazil drawing libraries
 */
private int
bytesperline(Rectangle r, int ld)
{
	ulong ws, l, t;
	int bits = 8;

	ws = bits>>ld;	/* pixels per unit */
	if(r.min.x >= 0){
		l = (r.max.x+ws-1)/ws;
		l -= r.min.x/ws;
	}else{			/* make positive before divide */
		t = (-r.min.x)+ws-1;
		t = (t/ws)*ws;
		l = (t+r.max.x+ws-1)/ws;
	}
	return l;
}

private int
rgb2cmap(int cr, int cg, int cb)
{
	int r, g, b, v, cv;

	if(cr < 0)
		cr = 0;
	else if(cr > 255)
		cr = 255;
	if(cg < 0)
		cg = 0;
	else if(cg > 255)
		cg = 255;
	if(cb < 0)
		cb = 0;
	else if(cb > 255)
		cb = 255;
	r = cr>>6;
	g = cg>>6;
	b = cb>>6;
	cv = cr;
	if(cg > cv)
		cv = cg;
	if(cb > cv)
		cv = cb;
	v = (cv>>4)&3;
	return 255-((((r<<2)+v)<<4)+(((g<<2)+b+v-r)&15));
}

/*
 * go the other way; not currently used.
 *
private long
cmap2rgb(int c)
{
	int j, num, den, r, g, b, v, rgb;

	c = 255-c;
	r = c>>6;
	v = (c>>4)&3;
	j = (c-v+r)&15;
	g = j>>2;
	b = j&3;
	den=r;
	if(g>den)
		den=g;
	if(b>den)
		den=b;
	if(den==0) {
		v *= 17;
		rgb = (v<<16)|(v<<8)|v;
	}
	else{
		num=17*(4*den+v);
		rgb = ((r*num/den)<<16)|((g*num/den)<<8)|(b*num/den);
	}
	return rgb;
}
 *
 *
 */