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