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