1 #include "lib9.h"
2 #include "draw.h"
3 #include "kernel.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
writeimage(int fd,Image * i,int dolock)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(libwrite(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 libwrite(fd, hdr, 2*12);
177 libwrite(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 }
186