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