1 #include <u.h>
2 #include <libc.h>
3 #include <bio.h>
4 #include <draw.h>
5 #include "imagefile.h"
6 
7 /*
8  * Hacked version for writing from Rawimage to file.
9  * Assumes 8 bits per component.
10  */
11 
12 #define	HSHIFT	3	/* HSHIFT==5 runs slightly faster, but hash table is 64x bigger */
13 #define	NHASH	(1<<(HSHIFT*NMATCH))
14 #define	HMASK	(NHASH-1)
15 #define	hupdate(h, c)	((((h)<<HSHIFT)^(c))&HMASK)
16 typedef struct Hlist Hlist;
17 struct Hlist{
18 	uchar *s;
19 	Hlist *next, *prev;
20 };
21 
22 int
23 writerawimage(int fd, Rawimage *i)
24 {
25 	uchar *outbuf, *outp, *eout;		/* encoded data, pointer, end */
26 	uchar *loutp;				/* start of encoded line */
27 	Hlist *hash;				/* heads of hash chains of past strings */
28 	Hlist *chain, *hp;			/* hash chain members, pointer */
29 	Hlist *cp;				/* next Hlist to fall out of window */
30 	int h;					/* hash value */
31 	uchar *line, *eline;			/* input line, end pointer */
32 	uchar *data, *edata;			/* input buffer, end pointer */
33 	ulong n;				/* length of input buffer */
34 	int bpl;				/* input line length */
35 	int offs, runlen;			/* offset, length of consumed data */
36 	uchar dumpbuf[NDUMP];			/* dump accumulator */
37 	int ndump;				/* length of dump accumulator */
38 	int ncblock;				/* size of buffer */
39 	Rectangle r;
40 	uchar *p, *q, *s, *es, *t;
41 	char hdr[11+5*12+1], buf[16];
42 	ulong desc;
43 
44 	r = i->r;
45 	switch(i->chandesc){
46 	default:
47 		werrstr("can't handle chandesc %d", i->chandesc);
48 		return -1;
49 	case CY:
50 		bpl = Dx(r);
51 		desc = GREY8;
52 		break;
53 	case CYA16:
54 		bpl = 2*Dx(r);
55 		desc = CHAN2(CGrey, 8, CAlpha, 8);
56 		break;
57 	case CRGBV:
58 		bpl = Dx(r);
59 		desc = CMAP8;
60 		break;
61 	case CRGBVA16:
62 		bpl = 2*Dx(r);
63 		desc = CHAN2(CMap, 8, CAlpha, 8);
64 		break;
65 	case CRGB24:
66 		bpl = 3*Dx(r);
67 		desc = RGB24;
68 		break;
69 	case CRGBA32:
70 		bpl = 4*Dx(r);
71 		desc = RGBA32;
72 		break;
73 	}
74 	ncblock = _compblocksize(r, bpl/Dx(r));
75 	outbuf = malloc(ncblock);
76 	hash = malloc(NHASH*sizeof(Hlist));
77 	chain = malloc(NMEM*sizeof(Hlist));
78 	if(outbuf == 0 || hash == 0 || chain == 0){
79 	ErrOut:
80 		free(outbuf);
81 		free(hash);
82 		free(chain);
83 		return -1;
84 	}
85 	n = Dy(r)*bpl;
86 	data = i->chans[0];
87 	sprint(hdr, "compressed\n%11s %11d %11d %11d %11d ",
88 		chantostr(buf, desc), r.min.x, r.min.y, r.max.x, r.max.y);
89 	if(write(fd, hdr, 11+5*12) != 11+5*12){
90 		werrstr("i/o error writing header");
91 		goto ErrOut;
92 	}
93 	edata = data+n;
94 	eout = outbuf+ncblock;
95 	line = data;
96 	r.max.y = r.min.y;
97 	while(line != edata){
98 		memset(hash, 0, NHASH*sizeof(Hlist));
99 		memset(chain, 0, NMEM*sizeof(Hlist));
100 		cp = chain;
101 		h = 0;
102 		outp = outbuf;
103 		for(n = 0; n != NMATCH; n++)
104 			h = hupdate(h, line[n]);
105 		loutp = outbuf;
106 		while(line != edata){
107 			ndump = 0;
108 			eline = line+bpl;
109 			for(p = line; p != eline; ){
110 				if(eline-p < NRUN)
111 					es = eline;
112 				else
113 					es = p+NRUN;
114 				q = 0;
115 				runlen = 0;
116 				for(hp = hash[h].next; hp; hp = hp->next){
117 					s = p + runlen;
118 					if(s >= es)
119 						continue;
120 					t = hp->s + runlen;
121 					for(; s >= p; s--)
122 						if(*s != *t--)
123 							goto matchloop;
124 					t += runlen+2;
125 					s += runlen+2;
126 					for(; s < es; s++)
127 						if(*s != *t++)
128 							break;
129 					n = s-p;
130 					if(n > runlen){
131 						runlen = n;
132 						q = hp->s;
133 						if(n == NRUN)
134 							break;
135 					}
136 			matchloop: ;
137 				}
138 				if(runlen < NMATCH){
139 					if(ndump == NDUMP){
140 						if(eout-outp < ndump+1)
141 							goto Bfull;
142 						*outp++ = ndump-1+128;
143 						memmove(outp, dumpbuf, ndump);
144 						outp += ndump;
145 						ndump = 0;
146 					}
147 					dumpbuf[ndump++] = *p;
148 					runlen = 1;
149 				}
150 				else{
151 					if(ndump != 0){
152 						if(eout-outp < ndump+1)
153 							goto Bfull;
154 						*outp++ = ndump-1+128;
155 						memmove(outp, dumpbuf, ndump);
156 						outp += ndump;
157 						ndump = 0;
158 					}
159 					offs = p-q-1;
160 					if(eout-outp < 2)
161 						goto Bfull;
162 					*outp++ = ((runlen-NMATCH)<<2) + (offs>>8);
163 					*outp++ = offs&255;
164 				}
165 				for(q = p+runlen; p != q; p++){
166 					if(cp->prev)
167 						cp->prev->next = 0;
168 					cp->next = hash[h].next;
169 					cp->prev = &hash[h];
170 					if(cp->next)
171 						cp->next->prev = cp;
172 					cp->prev->next = cp;
173 					cp->s = p;
174 					if(++cp == &chain[NMEM])
175 						cp = chain;
176 					if(edata-p > NMATCH)
177 						h = hupdate(h, p[NMATCH]);
178 				}
179 			}
180 			if(ndump != 0){
181 				if(eout-outp < ndump+1)
182 					goto Bfull;
183 				*outp++ = ndump-1+128;
184 				memmove(outp, dumpbuf, ndump);
185 				outp += ndump;
186 			}
187 			line = eline;
188 			loutp = outp;
189 			r.max.y++;
190 		}
191 	Bfull:
192 		if(loutp == outbuf){
193 			werrstr("compressor out of sync");
194 			goto ErrOut;
195 		}
196 		n = loutp-outbuf;
197 		sprint(hdr, "%11d %11ld ", r.max.y, n);
198 		write(fd, hdr, 2*12);
199 		write(fd, outbuf, n);
200 		r.min.y = r.max.y;
201 	}
202 	free(outbuf);
203 	free(hash);
204 	free(chain);
205 	return 0;
206 }