ref: c1d40df49550393f3afe53fb6e6d500dfa8eb7a8
dir: /sys/src/libdraw/writeimage.c/
#include <u.h> #include <libc.h> #include <draw.h> #define HSHIFT 3 /* HSHIFT==5 runs slightly faster, but hash table is 64x bigger */ #define NHASH (1<<(HSHIFT*NMATCH)) #define HMASK (NHASH-1) #define hupdate(h, c) ((((h)<<HSHIFT)^(c))&HMASK) typedef struct Hlist Hlist; struct Hlist{ uchar *s; Hlist *next, *prev; }; int writeimage(int fd, Image *i, int dolock) { uchar *outbuf, *outp, *eout; /* encoded data, pointer, end */ uchar *loutp; /* start of encoded line */ Hlist *hash; /* heads of hash chains of past strings */ Hlist *chain, *hp; /* hash chain members, pointer */ Hlist *cp; /* next Hlist to fall out of window */ int h; /* hash value */ uchar *line, *eline; /* input line, end pointer */ uchar *data, *edata; /* input buffer, end pointer */ ulong n; /* length of input buffer */ ulong nb; /* # of bytes returned by unloadimage */ int bpl; /* input line length */ int offs, runlen; /* offset, length of consumed data */ uchar dumpbuf[NDUMP]; /* dump accumulator */ int ndump; /* length of dump accumulator */ int miny, dy; /* y values while unloading input */ int chunk, ncblock; Rectangle r; uchar *p, *q, *s, *es, *t; char hdr[11+5*12+1]; char cbuf[20]; chunk = i->display->bufsize - 32; /* a little room for header */ r = i->r; bpl = bytesperline(r, i->depth); ncblock = _compblocksize(r, i->depth); if(ncblock > chunk){ sprint(hdr, "%11s %11d %11d %11d %11d ", chantostr(cbuf, i->chan), r.min.x, r.min.y, r.max.x, r.max.y); if(write(fd, hdr, 5*12) != 5*12) return -1; data = malloc(bpl); for(miny = r.min.y; miny != r.max.y; miny++){ if(dolock) lockdisplay(i->display); nb = unloadimage(i, Rect(r.min.x, miny, r.max.x, miny+1), data, bpl); if(dolock) unlockdisplay(i->display); if(nb != bpl) goto ErrOut0; if(write(fd, data, nb) != nb) goto ErrOut0; } free(data); return 0; } n = Dy(r)*bpl; data = malloc(n); if(data == 0){ ErrOut0: free(data); return -1; } for(miny = r.min.y; miny != r.max.y; miny += dy){ dy = r.max.y-miny; if(dy*bpl > chunk) dy = chunk/bpl; if(dy <= 0) dy = 1; if(dolock) lockdisplay(i->display); nb = unloadimage(i, Rect(r.min.x, miny, r.max.x, miny+dy), data+(miny-r.min.y)*bpl, dy*bpl); if(dolock) unlockdisplay(i->display); if(nb != dy*bpl) goto ErrOut0; } outbuf = malloc(ncblock); hash = malloc(NHASH*sizeof(Hlist)); chain = malloc(NMEM*sizeof(Hlist)); if(outbuf == 0 || hash == 0 || chain == 0){ ErrOut: free(outbuf); free(hash); free(chain); goto ErrOut0; } sprint(hdr, "compressed\n%11s %11d %11d %11d %11d ", chantostr(cbuf, i->chan), r.min.x, r.min.y, r.max.x, r.max.y); if(write(fd, hdr, 11+5*12) != 11+5*12) goto ErrOut; edata = data+n; eout = outbuf+ncblock; line = data; r.max.y = r.min.y; while(line != edata){ memset(hash, 0, NHASH*sizeof(Hlist)); memset(chain, 0, NMEM*sizeof(Hlist)); cp = chain; h = 0; outp = outbuf; for(n = 0; n != NMATCH; n++) h = hupdate(h, line[n]); loutp = outbuf; while(line != edata){ ndump = 0; eline = line+bpl; for(p = line; p != eline; ){ if(eline-p < NRUN) es = eline; else es = p+NRUN; q = 0; runlen = 0; for(hp = hash[h].next; hp; hp = hp->next){ s = p + runlen; if(s >= es) continue; t = hp->s + runlen; for(; s >= p; s--) if(*s != *t--) goto matchloop; t += runlen+2; s += runlen+2; for(; s < es; s++) if(*s != *t++) break; n = s-p; if(n > runlen){ runlen = n; q = hp->s; if(n == NRUN) break; } matchloop: ; } if(runlen < NMATCH){ if(ndump == NDUMP){ if(eout-outp < ndump+1) goto Bfull; *outp++ = ndump-1+128; memmove(outp, dumpbuf, ndump); outp += ndump; ndump = 0; } dumpbuf[ndump++] = *p; runlen = 1; } else{ if(ndump != 0){ if(eout-outp < ndump+1) goto Bfull; *outp++ = ndump-1+128; memmove(outp, dumpbuf, ndump); outp += ndump; ndump = 0; } offs = p-q-1; if(eout-outp < 2) goto Bfull; *outp++ = ((runlen-NMATCH)<<2) + (offs>>8); *outp++ = offs&255; } for(q = p+runlen; p != q; p++){ if(cp->prev) cp->prev->next = 0; cp->next = hash[h].next; cp->prev = &hash[h]; if(cp->next) cp->next->prev = cp; cp->prev->next = cp; cp->s = p; if(++cp == &chain[NMEM]) cp = chain; if(edata-p > NMATCH) h = hupdate(h, p[NMATCH]); } } if(ndump != 0){ if(eout-outp < ndump+1) goto Bfull; *outp++ = ndump-1+128; memmove(outp, dumpbuf, ndump); outp += ndump; } line = eline; loutp = outp; r.max.y++; } Bfull: if(loutp == outbuf) goto ErrOut; n = loutp-outbuf; sprint(hdr, "%11d %11ld ", r.max.y, n); write(fd, hdr, 2*12); write(fd, outbuf, n); r.min.y = r.max.y; } free(data); free(outbuf); free(hash); free(chain); return 0; }