1 #include <u.h> 2 #include <libc.h> 3 #include <draw.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 18 writeimage(int fd, Image *i, int dolock) 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 Rectangle r; 36 uchar *p, *q, *s, *es, *t; 37 char hdr[11+5*12+1]; 38 char cbuf[20]; 39 40 r = i->r; 41 bpl = bytesperline(r, i->depth); 42 n = Dy(r)*bpl; 43 data = malloc(n); 44 outbuf = malloc(NCBLOCK); 45 hash = malloc(NHASH*sizeof(Hlist)); 46 chain = malloc(NMEM*sizeof(Hlist)); 47 if(data == 0 || outbuf == 0 || hash == 0 || chain == 0){ 48 ErrOut: 49 free(data); 50 free(outbuf); 51 free(hash); 52 free(chain); 53 return -1; 54 } 55 for(miny = r.min.y; miny != r.max.y; miny += dy){ 56 dy = r.max.y-miny; 57 if(dy*bpl > CHUNK) 58 dy = CHUNK/bpl; 59 if(dolock) 60 lockdisplay(i->display); 61 nb = unloadimage(i, Rect(r.min.x, miny, r.max.x, miny+dy), 62 data+(miny-r.min.y)*bpl, dy*bpl); 63 if(dolock) 64 unlockdisplay(i->display); 65 if(nb != dy*bpl) 66 goto ErrOut; 67 } 68 sprint(hdr, "compressed\n%11s %11d %11d %11d %11d ", 69 chantostr(cbuf, i->chan), r.min.x, r.min.y, r.max.x, r.max.y); 70 if(write(fd, hdr, 11+5*12) != 11+5*12) 71 goto ErrOut; 72 edata = data+n; 73 eout = outbuf+NCBLOCK; 74 line = data; 75 r.max.y = r.min.y; 76 while(line != edata){ 77 memset(hash, 0, NHASH*sizeof(Hlist)); 78 memset(chain, 0, NMEM*sizeof(Hlist)); 79 cp = chain; 80 h = 0; 81 outp = outbuf; 82 for(n = 0; n != NMATCH; n++) 83 h = hupdate(h, line[n]); 84 loutp = outbuf; 85 while(line != edata){ 86 ndump = 0; 87 eline = line+bpl; 88 for(p = line; p != eline; ){ 89 if(eline-p < NRUN) 90 es = eline; 91 else 92 es = p+NRUN; 93 q = 0; 94 runlen = 0; 95 for(hp = hash[h].next; hp; hp = hp->next){ 96 s = p + runlen; 97 if(s >= es) 98 continue; 99 t = hp->s + runlen; 100 for(; s >= p; s--) 101 if(*s != *t--) 102 goto matchloop; 103 t += runlen+2; 104 s += runlen+2; 105 for(; s < es; s++) 106 if(*s != *t++) 107 break; 108 n = s-p; 109 if(n > runlen){ 110 runlen = n; 111 q = hp->s; 112 if(n == NRUN) 113 break; 114 } 115 matchloop: ; 116 } 117 if(runlen < NMATCH){ 118 if(ndump == NDUMP){ 119 if(eout-outp < ndump+1) 120 goto Bfull; 121 *outp++ = ndump-1+128; 122 memmove(outp, dumpbuf, ndump); 123 outp += ndump; 124 ndump = 0; 125 } 126 dumpbuf[ndump++] = *p; 127 runlen = 1; 128 } 129 else{ 130 if(ndump != 0){ 131 if(eout-outp < ndump+1) 132 goto Bfull; 133 *outp++ = ndump-1+128; 134 memmove(outp, dumpbuf, ndump); 135 outp += ndump; 136 ndump = 0; 137 } 138 offs = p-q-1; 139 if(eout-outp < 2) 140 goto Bfull; 141 *outp++ = ((runlen-NMATCH)<<2) + (offs>>8); 142 *outp++ = offs&255; 143 } 144 for(q = p+runlen; p != q; p++){ 145 if(cp->prev) 146 cp->prev->next = 0; 147 cp->next = hash[h].next; 148 cp->prev = &hash[h]; 149 if(cp->next) 150 cp->next->prev = cp; 151 cp->prev->next = cp; 152 cp->s = p; 153 if(++cp == &chain[NMEM]) 154 cp = chain; 155 if(edata-p > NMATCH) 156 h = hupdate(h, p[NMATCH]); 157 } 158 } 159 if(ndump != 0){ 160 if(eout-outp < ndump+1) 161 goto Bfull; 162 *outp++ = ndump-1+128; 163 memmove(outp, dumpbuf, ndump); 164 outp += ndump; 165 } 166 line = eline; 167 loutp = outp; 168 r.max.y++; 169 } 170 Bfull: 171 if(loutp == outbuf) 172 goto ErrOut; 173 n = loutp-outbuf; 174 sprint(hdr, "%11d %11ld ", r.max.y, n); 175 write(fd, hdr, 2*12); 176 write(fd, outbuf, n); 177 r.min.y = r.max.y; 178 } 179 free(data); 180 free(outbuf); 181 free(hash); 182 free(chain); 183 return 0; 184 } 185