1 #include <u.h>
2 #include <libc.h>
3 #include <draw.h>
4 #include <memdraw.h>
5
6 #define CHUNK 8000
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
writememimage(int fd,Memimage * i)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 ulong n; /* length of input buffer */
30 ulong 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 }
184