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