diff options
Diffstat (limited to 'src/libdraw/md-write.c')
| -rw-r--r-- | src/libdraw/md-write.c | 183 |
1 files changed, 183 insertions, 0 deletions
diff --git a/src/libdraw/md-write.c b/src/libdraw/md-write.c new file mode 100644 index 00000000..c03c58e8 --- /dev/null +++ b/src/libdraw/md-write.c @@ -0,0 +1,183 @@ +#include <u.h> +#include <libc.h> +#include <draw.h> +#include <memdraw.h> + +#define CHUNK 8000 + +#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 +writememimage(int fd, Memimage *i) +{ + 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 */ + u32int n; /* length of input buffer */ + u32int 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 ncblock; /* size of compressed blocks */ + Rectangle r; + uchar *p, *q, *s, *es, *t; + char hdr[11+5*12+1]; + char cbuf[20]; + + r = i->r; + bpl = bytesperline(r, i->depth); + n = Dy(r)*bpl; + data = malloc(n); + ncblock = _compblocksize(r, i->depth); + outbuf = malloc(ncblock); + hash = malloc(NHASH*sizeof(Hlist)); + chain = malloc(NMEM*sizeof(Hlist)); + if(data == 0 || outbuf == 0 || hash == 0 || chain == 0){ + ErrOut: + free(data); + free(outbuf); + free(hash); + free(chain); + 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; + nb = unloadmemimage(i, Rect(r.min.x, miny, r.max.x, miny+dy), + data+(miny-r.min.y)*bpl, dy*bpl); + if(nb != dy*bpl) + goto ErrOut; + } + 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; +} |