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