sys/src/libmemdraw/write.c

   1 #include <u.h>
   2 #include <libc.h>
   3 #include <draw.h>
   4 #include <memdraw.h>
   5
   6 #define CHUNK   8000
   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         ulong n;                                /* length of input buffer */
  30         ulong 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 }