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