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