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