1 #include <u.h>
2 #include <libc.h>
3 #include <draw.h>
4 
5 #define	HSHIFT	3	/* HSHIFT==5 runs slightly faster, but hash table is 64x bigger */
6 #define	NHASH	(1<<(HSHIFT*NMATCH))
7 #define	HMASK	(NHASH-1)
8 #define	hupdate(h, c)	((((h)<<HSHIFT)^(c))&HMASK)
9 typedef struct Hlist Hlist;
10 struct Hlist{
11 	uchar *s;
12 	Hlist *next, *prev;
13 };
14 
15 int
16 writeimage(int fd, Image *i, int dolock)
17 {
18 	uchar *outbuf, *outp, *eout;		/* encoded data, pointer, end */
19 	uchar *loutp;				/* start of encoded line */
20 	Hlist *hash;				/* heads of hash chains of past strings */
21 	Hlist *chain, *hp;			/* hash chain members, pointer */
22 	Hlist *cp;				/* next Hlist to fall out of window */
23 	int h;					/* hash value */
24 	uchar *line, *eline;			/* input line, end pointer */
25 	uchar *data, *edata;			/* input buffer, end pointer */
26 	ulong n;				/* length of input buffer */
27 	ulong nb;				/* # of bytes returned by unloadimage */
28 	int bpl;				/* input line length */
29 	int offs, runlen;			/* offset, length of consumed data */
30 	uchar dumpbuf[NDUMP];			/* dump accumulator */
31 	int ndump;				/* length of dump accumulator */
32 	int miny, dy;				/* y values while unloading input */
33 	int chunk, ncblock;
34 	Rectangle r;
35 	uchar *p, *q, *s, *es, *t;
36 	char hdr[11+5*12+1];
37 	char cbuf[20];
38 
39 	chunk = i->display->bufsize - 32;	/* a little room for header */
40 	r = i->r;
41 	bpl = bytesperline(r, i->depth);
42 	n = Dy(r)*bpl;
43 	data = malloc(n);
44 	ncblock = _compblocksize(r, i->depth);
45 	outbuf = malloc(ncblock);
46 	hash = malloc(NHASH*sizeof(Hlist));
47 	chain = malloc(NMEM*sizeof(Hlist));
48 	if(data == 0 || outbuf == 0 || hash == 0 || chain == 0){
49 	ErrOut:
50 		free(data);
51 		free(outbuf);
52 		free(hash);
53 		free(chain);
54 		return -1;
55 	}
56 	for(miny = r.min.y; miny != r.max.y; miny += dy){
57 		dy = r.max.y-miny;
58 		if(dy*bpl > chunk)
59 			dy = chunk/bpl;
60 		if(dolock)
61 			lockdisplay(i->display);
62 		nb = unloadimage(i, Rect(r.min.x, miny, r.max.x, miny+dy),
63 			data+(miny-r.min.y)*bpl, dy*bpl);
64 		if(dolock)
65 			unlockdisplay(i->display);
66 		if(nb != dy*bpl)
67 			goto ErrOut;
68 	}
69 	sprint(hdr, "compressed\n%11s %11d %11d %11d %11d ",
70 		chantostr(cbuf, i->chan), r.min.x, r.min.y, r.max.x, r.max.y);
71 	if(write(fd, hdr, 11+5*12) != 11+5*12)
72 		goto ErrOut;
73 	edata = data+n;
74 	eout = outbuf+ncblock;
75 	line = data;
76 	r.max.y = r.min.y;
77 	while(line != edata){
78 		memset(hash, 0, NHASH*sizeof(Hlist));
79 		memset(chain, 0, NMEM*sizeof(Hlist));
80 		cp = chain;
81 		h = 0;
82 		outp = outbuf;
83 		for(n = 0; n != NMATCH; n++)
84 			h = hupdate(h, line[n]);
85 		loutp = outbuf;
86 		while(line != edata){
87 			ndump = 0;
88 			eline = line+bpl;
89 			for(p = line; p != eline; ){
90 				if(eline-p < NRUN)
91 					es = eline;
92 				else
93 					es = p+NRUN;
94 				q = 0;
95 				runlen = 0;
96 				for(hp = hash[h].next; hp; hp = hp->next){
97 					s = p + runlen;
98 					if(s >= es)
99 						continue;
100 					t = hp->s + runlen;
101 					for(; s >= p; s--)
102 						if(*s != *t--)
103 							goto matchloop;
104 					t += runlen+2;
105 					s += runlen+2;
106 					for(; s < es; s++)
107 						if(*s != *t++)
108 							break;
109 					n = s-p;
110 					if(n > runlen){
111 						runlen = n;
112 						q = hp->s;
113 						if(n == NRUN)
114 							break;
115 					}
116 			matchloop: ;
117 				}
118 				if(runlen < NMATCH){
119 					if(ndump == NDUMP){
120 						if(eout-outp < ndump+1)
121 							goto Bfull;
122 						*outp++ = ndump-1+128;
123 						memmove(outp, dumpbuf, ndump);
124 						outp += ndump;
125 						ndump = 0;
126 					}
127 					dumpbuf[ndump++] = *p;
128 					runlen = 1;
129 				}
130 				else{
131 					if(ndump != 0){
132 						if(eout-outp < ndump+1)
133 							goto Bfull;
134 						*outp++ = ndump-1+128;
135 						memmove(outp, dumpbuf, ndump);
136 						outp += ndump;
137 						ndump = 0;
138 					}
139 					offs = p-q-1;
140 					if(eout-outp < 2)
141 						goto Bfull;
142 					*outp++ = ((runlen-NMATCH)<<2) + (offs>>8);
143 					*outp++ = offs&255;
144 				}
145 				for(q = p+runlen; p != q; p++){
146 					if(cp->prev)
147 						cp->prev->next = 0;
148 					cp->next = hash[h].next;
149 					cp->prev = &hash[h];
150 					if(cp->next)
151 						cp->next->prev = cp;
152 					cp->prev->next = cp;
153 					cp->s = p;
154 					if(++cp == &chain[NMEM])
155 						cp = chain;
156 					if(edata-p > NMATCH)
157 						h = hupdate(h, p[NMATCH]);
158 				}
159 			}
160 			if(ndump != 0){
161 				if(eout-outp < ndump+1)
162 					goto Bfull;
163 				*outp++ = ndump-1+128;
164 				memmove(outp, dumpbuf, ndump);
165 				outp += ndump;
166 			}
167 			line = eline;
168 			loutp = outp;
169 			r.max.y++;
170 		}
171 	Bfull:
172 		if(loutp == outbuf)
173 			goto ErrOut;
174 		n = loutp-outbuf;
175 		sprint(hdr, "%11d %11ld ", r.max.y, n);
176 		write(fd, hdr, 2*12);
177 		write(fd, outbuf, n);
178 		r.min.y = r.max.y;
179 	}
180 	free(data);
181 	free(outbuf);
182 	free(hash);
183 	free(chain);
184 	return 0;
185 }