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