sys/src/libdraw/writeimage.c

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