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