xref: /plan9/sys/src/libmemdraw/write.c (revision 9a747e4fd48b9f4522c70c07e8f882a15030f964)
17dd7cddfSDavid du Colombier #include <u.h>
27dd7cddfSDavid du Colombier #include <libc.h>
37dd7cddfSDavid du Colombier #include <draw.h>
47dd7cddfSDavid du Colombier #include <memdraw.h>
57dd7cddfSDavid du Colombier 
67dd7cddfSDavid du Colombier #define	CHUNK	8000
77dd7cddfSDavid du Colombier 
87dd7cddfSDavid du Colombier #define	HSHIFT	3	/* HSHIFT==5 runs slightly faster, but hash table is 64x bigger */
97dd7cddfSDavid du Colombier #define	NHASH	(1<<(HSHIFT*NMATCH))
107dd7cddfSDavid du Colombier #define	HMASK	(NHASH-1)
117dd7cddfSDavid du Colombier #define	hupdate(h, c)	((((h)<<HSHIFT)^(c))&HMASK)
127dd7cddfSDavid du Colombier typedef struct Hlist Hlist;
137dd7cddfSDavid du Colombier struct Hlist{
147dd7cddfSDavid du Colombier 	uchar *s;
157dd7cddfSDavid du Colombier 	Hlist *next, *prev;
167dd7cddfSDavid du Colombier };
177dd7cddfSDavid du Colombier 
187dd7cddfSDavid du Colombier int
writememimage(int fd,Memimage * i)197dd7cddfSDavid du Colombier writememimage(int fd, Memimage *i)
207dd7cddfSDavid du Colombier {
217dd7cddfSDavid du Colombier 	uchar *outbuf, *outp, *eout;		/* encoded data, pointer, end */
227dd7cddfSDavid du Colombier 	uchar *loutp;				/* start of encoded line */
237dd7cddfSDavid du Colombier 	Hlist *hash;				/* heads of hash chains of past strings */
247dd7cddfSDavid du Colombier 	Hlist *chain, *hp;			/* hash chain members, pointer */
257dd7cddfSDavid du Colombier 	Hlist *cp;				/* next Hlist to fall out of window */
267dd7cddfSDavid du Colombier 	int h;					/* hash value */
277dd7cddfSDavid du Colombier 	uchar *line, *eline;			/* input line, end pointer */
287dd7cddfSDavid du Colombier 	uchar *data, *edata;			/* input buffer, end pointer */
297dd7cddfSDavid du Colombier 	ulong n;				/* length of input buffer */
307dd7cddfSDavid du Colombier 	ulong nb;				/* # of bytes returned by unloadimage */
317dd7cddfSDavid du Colombier 	int bpl;				/* input line length */
327dd7cddfSDavid du Colombier 	int offs, runlen;			/* offset, length of consumed data */
337dd7cddfSDavid du Colombier 	uchar dumpbuf[NDUMP];			/* dump accumulator */
347dd7cddfSDavid du Colombier 	int ndump;				/* length of dump accumulator */
357dd7cddfSDavid du Colombier 	int miny, dy;				/* y values while unloading input */
36*9a747e4fSDavid du Colombier 	int ncblock;				/* size of compressed blocks */
377dd7cddfSDavid du Colombier 	Rectangle r;
387dd7cddfSDavid du Colombier 	uchar *p, *q, *s, *es, *t;
397dd7cddfSDavid du Colombier 	char hdr[11+5*12+1];
407dd7cddfSDavid du Colombier 	char cbuf[20];
417dd7cddfSDavid du Colombier 
427dd7cddfSDavid du Colombier 	r = i->r;
437dd7cddfSDavid du Colombier 	bpl = bytesperline(r, i->depth);
447dd7cddfSDavid du Colombier 	n = Dy(r)*bpl;
457dd7cddfSDavid du Colombier 	data = malloc(n);
46*9a747e4fSDavid du Colombier 	ncblock = _compblocksize(r, i->depth);
47*9a747e4fSDavid du Colombier 	outbuf = malloc(ncblock);
487dd7cddfSDavid du Colombier 	hash = malloc(NHASH*sizeof(Hlist));
497dd7cddfSDavid du Colombier 	chain = malloc(NMEM*sizeof(Hlist));
507dd7cddfSDavid du Colombier 	if(data == 0 || outbuf == 0 || hash == 0 || chain == 0){
517dd7cddfSDavid du Colombier 	ErrOut:
527dd7cddfSDavid du Colombier 		free(data);
537dd7cddfSDavid du Colombier 		free(outbuf);
547dd7cddfSDavid du Colombier 		free(hash);
557dd7cddfSDavid du Colombier 		free(chain);
567dd7cddfSDavid du Colombier 		return -1;
577dd7cddfSDavid du Colombier 	}
587dd7cddfSDavid du Colombier 	for(miny = r.min.y; miny != r.max.y; miny += dy){
597dd7cddfSDavid du Colombier 		dy = r.max.y-miny;
607dd7cddfSDavid du Colombier 		if(dy*bpl > CHUNK)
617dd7cddfSDavid du Colombier 			dy = CHUNK/bpl;
627dd7cddfSDavid du Colombier 		nb = unloadmemimage(i, Rect(r.min.x, miny, r.max.x, miny+dy),
637dd7cddfSDavid du Colombier 			data+(miny-r.min.y)*bpl, dy*bpl);
647dd7cddfSDavid du Colombier 		if(nb != dy*bpl)
657dd7cddfSDavid du Colombier 			goto ErrOut;
667dd7cddfSDavid du Colombier 	}
677dd7cddfSDavid du Colombier 	sprint(hdr, "compressed\n%11s %11d %11d %11d %11d ",
687dd7cddfSDavid du Colombier 		chantostr(cbuf, i->chan), r.min.x, r.min.y, r.max.x, r.max.y);
697dd7cddfSDavid du Colombier 	if(write(fd, hdr, 11+5*12) != 11+5*12)
707dd7cddfSDavid du Colombier 		goto ErrOut;
717dd7cddfSDavid du Colombier 	edata = data+n;
72*9a747e4fSDavid du Colombier 	eout = outbuf+ncblock;
737dd7cddfSDavid du Colombier 	line = data;
747dd7cddfSDavid du Colombier 	r.max.y = r.min.y;
757dd7cddfSDavid du Colombier 	while(line != edata){
767dd7cddfSDavid du Colombier 		memset(hash, 0, NHASH*sizeof(Hlist));
777dd7cddfSDavid du Colombier 		memset(chain, 0, NMEM*sizeof(Hlist));
787dd7cddfSDavid du Colombier 		cp = chain;
797dd7cddfSDavid du Colombier 		h = 0;
807dd7cddfSDavid du Colombier 		outp = outbuf;
817dd7cddfSDavid du Colombier 		for(n = 0; n != NMATCH; n++)
827dd7cddfSDavid du Colombier 			h = hupdate(h, line[n]);
837dd7cddfSDavid du Colombier 		loutp = outbuf;
847dd7cddfSDavid du Colombier 		while(line != edata){
857dd7cddfSDavid du Colombier 			ndump = 0;
867dd7cddfSDavid du Colombier 			eline = line+bpl;
877dd7cddfSDavid du Colombier 			for(p = line; p != eline; ){
887dd7cddfSDavid du Colombier 				if(eline-p < NRUN)
897dd7cddfSDavid du Colombier 					es = eline;
907dd7cddfSDavid du Colombier 				else
917dd7cddfSDavid du Colombier 					es = p+NRUN;
927dd7cddfSDavid du Colombier 				q = 0;
937dd7cddfSDavid du Colombier 				runlen = 0;
947dd7cddfSDavid du Colombier 				for(hp = hash[h].next; hp; hp = hp->next){
957dd7cddfSDavid du Colombier 					s = p + runlen;
967dd7cddfSDavid du Colombier 					if(s >= es)
977dd7cddfSDavid du Colombier 						continue;
987dd7cddfSDavid du Colombier 					t = hp->s + runlen;
997dd7cddfSDavid du Colombier 					for(; s >= p; s--)
1007dd7cddfSDavid du Colombier 						if(*s != *t--)
1017dd7cddfSDavid du Colombier 							goto matchloop;
1027dd7cddfSDavid du Colombier 					t += runlen+2;
1037dd7cddfSDavid du Colombier 					s += runlen+2;
1047dd7cddfSDavid du Colombier 					for(; s < es; s++)
1057dd7cddfSDavid du Colombier 						if(*s != *t++)
1067dd7cddfSDavid du Colombier 							break;
1077dd7cddfSDavid du Colombier 					n = s-p;
1087dd7cddfSDavid du Colombier 					if(n > runlen){
1097dd7cddfSDavid du Colombier 						runlen = n;
1107dd7cddfSDavid du Colombier 						q = hp->s;
1117dd7cddfSDavid du Colombier 						if(n == NRUN)
1127dd7cddfSDavid du Colombier 							break;
1137dd7cddfSDavid du Colombier 					}
1147dd7cddfSDavid du Colombier 			matchloop: ;
1157dd7cddfSDavid du Colombier 				}
1167dd7cddfSDavid du Colombier 				if(runlen < NMATCH){
1177dd7cddfSDavid du Colombier 					if(ndump == NDUMP){
1187dd7cddfSDavid du Colombier 						if(eout-outp < ndump+1)
1197dd7cddfSDavid du Colombier 							goto Bfull;
1207dd7cddfSDavid du Colombier 						*outp++ = ndump-1+128;
1217dd7cddfSDavid du Colombier 						memmove(outp, dumpbuf, ndump);
1227dd7cddfSDavid du Colombier 						outp += ndump;
1237dd7cddfSDavid du Colombier 						ndump = 0;
1247dd7cddfSDavid du Colombier 					}
1257dd7cddfSDavid du Colombier 					dumpbuf[ndump++] = *p;
1267dd7cddfSDavid du Colombier 					runlen = 1;
1277dd7cddfSDavid du Colombier 				}
1287dd7cddfSDavid du Colombier 				else{
1297dd7cddfSDavid du Colombier 					if(ndump != 0){
1307dd7cddfSDavid du Colombier 						if(eout-outp < ndump+1)
1317dd7cddfSDavid du Colombier 							goto Bfull;
1327dd7cddfSDavid du Colombier 						*outp++ = ndump-1+128;
1337dd7cddfSDavid du Colombier 						memmove(outp, dumpbuf, ndump);
1347dd7cddfSDavid du Colombier 						outp += ndump;
1357dd7cddfSDavid du Colombier 						ndump = 0;
1367dd7cddfSDavid du Colombier 					}
1377dd7cddfSDavid du Colombier 					offs = p-q-1;
1387dd7cddfSDavid du Colombier 					if(eout-outp < 2)
1397dd7cddfSDavid du Colombier 						goto Bfull;
1407dd7cddfSDavid du Colombier 					*outp++ = ((runlen-NMATCH)<<2) + (offs>>8);
1417dd7cddfSDavid du Colombier 					*outp++ = offs&255;
1427dd7cddfSDavid du Colombier 				}
1437dd7cddfSDavid du Colombier 				for(q = p+runlen; p != q; p++){
1447dd7cddfSDavid du Colombier 					if(cp->prev)
1457dd7cddfSDavid du Colombier 						cp->prev->next = 0;
1467dd7cddfSDavid du Colombier 					cp->next = hash[h].next;
1477dd7cddfSDavid du Colombier 					cp->prev = &hash[h];
1487dd7cddfSDavid du Colombier 					if(cp->next)
1497dd7cddfSDavid du Colombier 						cp->next->prev = cp;
1507dd7cddfSDavid du Colombier 					cp->prev->next = cp;
1517dd7cddfSDavid du Colombier 					cp->s = p;
1527dd7cddfSDavid du Colombier 					if(++cp == &chain[NMEM])
1537dd7cddfSDavid du Colombier 						cp = chain;
1547dd7cddfSDavid du Colombier 					if(edata-p > NMATCH)
1557dd7cddfSDavid du Colombier 						h = hupdate(h, p[NMATCH]);
1567dd7cddfSDavid du Colombier 				}
1577dd7cddfSDavid du Colombier 			}
1587dd7cddfSDavid du Colombier 			if(ndump != 0){
1597dd7cddfSDavid du Colombier 				if(eout-outp < ndump+1)
1607dd7cddfSDavid du Colombier 					goto Bfull;
1617dd7cddfSDavid du Colombier 				*outp++ = ndump-1+128;
1627dd7cddfSDavid du Colombier 				memmove(outp, dumpbuf, ndump);
1637dd7cddfSDavid du Colombier 				outp += ndump;
1647dd7cddfSDavid du Colombier 			}
1657dd7cddfSDavid du Colombier 			line = eline;
1667dd7cddfSDavid du Colombier 			loutp = outp;
1677dd7cddfSDavid du Colombier 			r.max.y++;
1687dd7cddfSDavid du Colombier 		}
1697dd7cddfSDavid du Colombier 	Bfull:
1707dd7cddfSDavid du Colombier 		if(loutp == outbuf)
1717dd7cddfSDavid du Colombier 			goto ErrOut;
1727dd7cddfSDavid du Colombier 		n = loutp-outbuf;
1737dd7cddfSDavid du Colombier 		sprint(hdr, "%11d %11ld ", r.max.y, n);
1747dd7cddfSDavid du Colombier 		write(fd, hdr, 2*12);
1757dd7cddfSDavid du Colombier 		write(fd, outbuf, n);
1767dd7cddfSDavid du Colombier 		r.min.y = r.max.y;
1777dd7cddfSDavid du Colombier 	}
1787dd7cddfSDavid du Colombier 	free(data);
1797dd7cddfSDavid du Colombier 	free(outbuf);
1807dd7cddfSDavid du Colombier 	free(hash);
1817dd7cddfSDavid du Colombier 	free(chain);
1827dd7cddfSDavid du Colombier 	return 0;
1837dd7cddfSDavid du Colombier }
184