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