sys/src/cmd/jpg/writegif.c

   1 #include <u.h>
   2 #include <libc.h>
   3 #include <draw.h>
   4 #include <memdraw.h>
   5 #include <bio.h>
   6 #include "imagefile.h"
   7
   8 enum
   9 {
  10         Nhash   = 4001,
  11         Nbuf            = 300,
  12 };
  13
  14 typedef struct Entry Entry;
  15 typedef struct IO IO;
  16
  17
  18 struct Entry
  19 {
  20         int             index;
  21         int             prefix;
  22         int             exten;
  23         Entry   *next;
  24 };
  25
  26 struct IO
  27 {
  28         Biobuf  *fd;
  29         uchar   buf[Nbuf];
  30         int             i;
  31         int             nbits;  /* bits in right side of shift register */
  32         int             sreg;           /* shift register */
  33 };
  34
  35 static Rectangle        mainrect;
  36 static Entry    tbl[4096];
  37 static uchar    *colormap[5];   /* one for each ldepth: GREY1 GREY2 GREY4 CMAP8=rgbv plus GREY8 */
  38 #define GREYMAP 4
  39 static int              colormapsize[] = { 2, 4, 16, 256, 256 };        /* 2 for zero is an odd property of GIF */
  40
  41 static void             writeheader(Biobuf*, Rectangle, int, ulong, int);
  42 static void             writedescriptor(Biobuf*, Rectangle);
  43 static char*    writedata(Biobuf*, Image*, Memimage*);
  44 static void             writetrailer(Biobuf *fd);
  45 static void             writecomment(Biobuf *fd, char*);
  46 static void             writegraphiccontrol(Biobuf *fd, int, int);
  47 static void*    gifmalloc(ulong);
  48 static void             encode(Biobuf*, Rectangle, int, uchar*, uint);
  49
  50 static
  51 char*
  52 startgif0(Biobuf *fd, ulong chan, Rectangle r, int depth, int loopcount)
  53 {
  54         int i;
  55
  56         for(i=0; i<nelem(tbl); i++)
  57                 tbl[i] = (Entry){i, -1, i, nil};
  58
  59         switch(chan){
  60         case GREY1:
  61         case GREY2:
  62         case GREY4:
  63         case CMAP8:
  64         case GREY8:
  65                 break;
  66         default:
  67                 return "WriteGIF: can't handle channel type";
  68         }
  69
  70         mainrect = r;
  71         writeheader(fd, r, depth, chan, loopcount);
  72         return nil;
  73 }
  74
  75 char*
  76 startgif(Biobuf *fd, Image *image, int loopcount)
  77 {
  78         return startgif0(fd, image->chan, image->r, image->depth, loopcount);
  79 }
  80
  81 char*
  82 memstartgif(Biobuf *fd, Memimage *memimage, int loopcount)
  83 {
  84         return startgif0(fd, memimage->chan, memimage->r, memimage->depth, loopcount);
  85 }
  86
  87 static
  88 char*
  89 writegif0(Biobuf *fd, Image *image, Memimage *memimage, ulong chan, Rectangle r, char *comment, int dt, int trans)
  90 {
  91         char *err;
  92
  93         switch(chan){
  94         case GREY1:
  95         case GREY2:
  96         case GREY4:
  97         case CMAP8:
  98         case GREY8:
  99                 break;
 100         default:
 101                 return "WriteGIF: can't handle channel type";
 102         }
 103
 104         writecomment(fd, comment);
 105         writegraphiccontrol(fd, dt, trans);
 106         writedescriptor(fd, r);
 107
 108         err = writedata(fd, image, memimage);
 109         if(err != nil)
 110                 return err;
 111
 112         return nil;
 113 }
 114
 115 char*
 116 writegif(Biobuf *fd, Image *image, char *comment, int dt, int trans)
 117 {
 118         return writegif0(fd, image, nil, image->chan, image->r, comment, dt, trans);
 119 }
 120
 121 char*
 122 memwritegif(Biobuf *fd, Memimage *memimage, char *comment, int dt, int trans)
 123 {
 124         return writegif0(fd, nil, memimage, memimage->chan, memimage->r, comment, dt, trans);
 125 }
 126
 127 /*
 128  * Write little-endian 16-bit integer
 129  */
 130 static
 131 void
 132 put2(Biobuf *fd, int i)
 133 {
 134         Bputc(fd, i);
 135         Bputc(fd, i>>8);
 136 }
 137
 138 /*
 139  * Get color map for all ldepths, in format suitable for writing out
 140  */
 141 static
 142 void
 143 getcolormap(void)
 144 {
 145         int i, col;
 146         ulong rgb;
 147         uchar *c;
 148
 149         if(colormap[0] != nil)
 150                 return;
 151         for(i=0; i<nelem(colormap); i++)
 152                 colormap[i] = gifmalloc(3* colormapsize[i]);
 153         c = colormap[GREYMAP];  /* GREY8 */
 154         for(i=0; i<256; i++){
 155                 c[3*i+0] = i;   /* red */
 156                 c[3*i+1] = i;   /* green */
 157                 c[3*i+2] = i;   /* blue */
 158         }
 159         c = colormap[3];        /* RGBV */
 160         for(i=0; i<256; i++){
 161                 rgb = cmap2rgb(i);
 162                 c[3*i+0] = (rgb>>16) & 0xFF;    /* red */
 163                 c[3*i+1] = (rgb>> 8) & 0xFF;    /* green */
 164                 c[3*i+2] = (rgb>> 0) & 0xFF;    /* blue */
 165         }
 166         c = colormap[2];        /* GREY4 */
 167         for(i=0; i<16; i++){
 168                 col = (i<<4)|i;
 169                 rgb = cmap2rgb(col);
 170                 c[3*i+0] = (rgb>>16) & 0xFF;    /* red */
 171                 c[3*i+1] = (rgb>> 8) & 0xFF;    /* green */
 172                 c[3*i+2] = (rgb>> 0) & 0xFF;    /* blue */
 173         }
 174         c = colormap[1];        /* GREY2 */
 175         for(i=0; i<4; i++){
 176                 col = (i<<6)|(i<<4)|(i<<2)|i;
 177                 rgb = cmap2rgb(col);
 178                 c[3*i+0] = (rgb>>16) & 0xFF;    /* red */
 179                 c[3*i+1] = (rgb>> 8) & 0xFF;    /* green */
 180                 c[3*i+2] = (rgb>> 0) & 0xFF;    /* blue */
 181         }
 182         c = colormap[0];        /* GREY1 */
 183         for(i=0; i<2; i++){
 184                 if(i == 0)
 185                         col = 0;
 186                 else
 187                         col = 0xFF;
 188                 rgb = cmap2rgb(col);
 189                 c[3*i+0] = (rgb>>16) & 0xFF;    /* red */
 190                 c[3*i+1] = (rgb>> 8) & 0xFF;    /* green */
 191                 c[3*i+2] = (rgb>> 0) & 0xFF;    /* blue */
 192         }
 193 }
 194
 195 /* imported from libdraw/arith.c to permit an extern log2 function */
 196 static int log2[] = {
 197         -1, 0, 1, -1, 2, -1, -1, -1, 3, -1, -1, -1, -1, -1, -1, -1, 4,
 198         -1, -1, -1, -1, -1, -1, -1, 4 /* BUG */, -1, -1, -1, -1, -1, -1, -1, 5
 199 };
 200
 201 /*
 202  * Write header, logical screen descriptor, and color map
 203  */
 204 static
 205 void
 206 writeheader(Biobuf *fd, Rectangle r, int depth, ulong chan, int loopcount)
 207 {
 208         /* Header */
 209         Bprint(fd, "%s", "GIF89a");
 210
 211         /*  Logical Screen Descriptor */
 212         put2(fd, Dx(r));
 213         put2(fd, Dy(r));
 214
 215         /* Color table present, 4 bits per color (for RGBV best case), size of color map */
 216         Bputc(fd, (1<<7)|(3<<4)|(depth-1));     /* not right for GREY8, but GIF doesn't let us specify enough bits */
 217         Bputc(fd, 0xFF);        /* white background (doesn't matter anyway) */
 218         Bputc(fd, 0);   /* pixel aspect ratio - unused */
 219
 220         /* Global Color Table */
 221         getcolormap();
 222         if(chan == GREY8)
 223                 depth = GREYMAP;
 224         else
 225                 depth = log2[depth];
 226         Bwrite(fd, colormap[depth], 3*colormapsize[depth]);
 227
 228         if(loopcount >= 0){     /* hard-to-discover way to force cycled animation */
 229                 /* Application Extension with (1 loopcountlo loopcounthi) as data */
 230                 Bputc(fd, 0x21);
 231                 Bputc(fd, 0xFF);
 232                 Bputc(fd, 11);
 233                 Bwrite(fd, "NETSCAPE2.0", 11);
 234                 Bputc(fd, 3);
 235                 Bputc(fd, 1);
 236                 put2(fd, loopcount);
 237                 Bputc(fd, 0);
 238         }
 239 }
 240
 241 /*
 242  * Write optional comment block
 243  */
 244 static
 245 void
 246 writecomment(Biobuf *fd, char *comment)
 247 {
 248         int n;
 249
 250         if(comment==nil || comment[0]=='\0')
 251                 return;
 252
 253         /* Comment extension and label */
 254         Bputc(fd, 0x21);
 255         Bputc(fd, 0xFE);
 256
 257         /* Comment data */
 258         n = strlen(comment);
 259         if(n > 255)
 260                 n = 255;
 261         Bputc(fd, n);
 262         Bwrite(fd, comment, n);
 263
 264         /* Block terminator */
 265         Bputc(fd, 0x00);
 266 }
 267
 268 /*
 269  * Write optional control block (sets Delay Time)
 270  */
 271 static
 272 void
 273 writegraphiccontrol(Biobuf *fd, int dt, int trans)
 274 {
 275         if(dt < 0 && trans < 0)
 276                 return;
 277
 278         /* Comment extension and label and block size*/
 279         Bputc(fd, 0x21);
 280         Bputc(fd, 0xF9);
 281         Bputc(fd, 0x04);
 282
 283         /* Disposal method and other flags (none) */
 284         if(trans >= 0)
 285                 Bputc(fd, 0x01);
 286         else
 287                 Bputc(fd, 0x00);
 288
 289         /* Delay time, in centisec (argument is millisec for sanity) */
 290         if(dt < 0)
 291                 dt = 0;
 292         else if(dt < 10)
 293                 dt = 1;
 294         else
 295                 dt = (dt+5)/10;
 296         put2(fd, dt);
 297
 298         /* Transparency index */
 299         if(trans < 0)
 300                 trans = 0;
 301         Bputc(fd, trans);
 302
 303         /* Block terminator */
 304         Bputc(fd, 0x00);
 305 }
 306
 307 /*
 308  * Write image descriptor
 309  */
 310 static
 311 void
 312 writedescriptor(Biobuf *fd, Rectangle r)
 313 {
 314         /* Image Separator */
 315         Bputc(fd, 0x2C);
 316
 317         /* Left, top, width, height */
 318         put2(fd, r.min.x-mainrect.min.x);
 319         put2(fd, r.min.y-mainrect.min.y);
 320         put2(fd, Dx(r));
 321         put2(fd, Dy(r));
 322         /* no special processing */
 323         Bputc(fd, 0);
 324 }
 325
 326 /*
 327  * Write data
 328  */
 329 static
 330 char*
 331 writedata(Biobuf *fd, Image *image, Memimage *memimage)
 332 {
 333         char *err;
 334         uchar *data;
 335         int ndata, depth;
 336         Rectangle r;
 337
 338         if(memimage != nil){
 339                 r = memimage->r;
 340                 depth = memimage->depth;
 341         }else{
 342                 r = image->r;
 343                 depth = image->depth;
 344         }
 345
 346         /* LZW Minimum code size */
 347         if(depth == 1)
 348                 Bputc(fd, 2);
 349         else
 350                 Bputc(fd, depth);
 351
 352         /*
 353          * Read image data into memory
 354          * potentially one extra byte on each end of each scan line
 355          */
 356         ndata = Dy(r)*(2+(Dx(r)>>(3-log2[depth])));
 357         data = gifmalloc(ndata);
 358         if(memimage != nil)
 359                 ndata = unloadmemimage(memimage, r, data, ndata);
 360         else
 361                 ndata = unloadimage(image, r, data, ndata);
 362         if(ndata < 0){
 363                 err = gifmalloc(ERRMAX);
 364                 snprint(err, ERRMAX, "WriteGIF: %r");
 365                 free(data);
 366                 return err;
 367         }
 368
 369         /* Encode and emit the data */
 370         encode(fd, r, depth, data, ndata);
 371         free(data);
 372
 373         /*  Block Terminator */
 374         Bputc(fd, 0);
 375         return nil;
 376 }
 377
 378 /*
 379  * Write trailer
 380  */
 381 void
 382 endgif(Biobuf *fd)
 383 {
 384         Bputc(fd, 0x3B);
 385         Bflush(fd);
 386 }
 387
 388 void
 389 memendgif(Biobuf *fd)
 390 {
 391         endgif(fd);
 392 }
 393
 394 /*
 395  * Put n bits of c into output at io.buf[i];
 396  */
 397 static
 398 void
 399 output(IO *io, int c, int n)
 400 {
 401         if(c < 0){
 402                 if(io->nbits != 0)
 403                         io->buf[io->i++] = io->sreg;
 404                 Bputc(io->fd, io->i);
 405                 Bwrite(io->fd, io->buf, io->i);
 406                 io->nbits = 0;
 407                 return;
 408         }
 409
 410         if(io->nbits+n >= 31){
 411                 fprint(2, "panic: WriteGIF sr overflow\n");
 412                 exits("WriteGIF panic");
 413         }
 414         io->sreg |= c<<io->nbits;
 415         io->nbits += n;
 416
 417         while(io->nbits >= 8){
 418                 io->buf[io->i++] = io->sreg;
 419                 io->sreg >>= 8;
 420                 io->nbits -= 8;
 421         }
 422
 423         if(io->i >= 255){
 424                 Bputc(io->fd, 255);
 425                 Bwrite(io->fd, io->buf, 255);
 426                 memmove(io->buf, io->buf+255, io->i-255);
 427                 io->i -= 255;
 428         }
 429 }
 430
 431 /*
 432  * LZW encoder
 433  */
 434 static
 435 void
 436 encode(Biobuf *fd, Rectangle r, int depth, uchar *data, uint ndata)
 437 {
 438         int i, c, h, csize, prefix, first, sreg, nbits, bitsperpixel;
 439         int CTM, EOD, codesize, ld0, datai, x, ld, pm;
 440         int nentry, maxentry, early;
 441         Entry *e, *oe;
 442         IO *io;
 443         Entry **hash;
 444
 445         first = 1;
 446         ld = log2[depth];
 447         /* ldepth 0 must generate codesize 2 with values 0 and 1 (see the spec.) */
 448         ld0 = ld;
 449         if(ld0 == 0)
 450                 ld0 = 1;
 451         codesize = (1<<ld0);
 452         CTM = 1<<codesize;
 453         EOD = CTM+1;
 454
 455         io = gifmalloc(sizeof(IO));
 456         io->fd = fd;
 457         sreg = 0;
 458         nbits = 0;
 459         bitsperpixel = 1<<ld;
 460         pm = (1<<bitsperpixel)-1;
 461
 462         datai = 0;
 463         x = r.min.x;
 464         hash = gifmalloc(Nhash*sizeof(Entry*));
 465
 466 Init:
 467         memset(hash, 0, Nhash*sizeof(Entry*));
 468         csize = codesize+1;
 469         nentry = EOD+1;
 470         maxentry = (1<<csize);
 471         for(i = 0; i<nentry; i++){
 472                 e = &tbl[i];
 473                 h = (e->prefix<<24) | (e->exten<<8);
 474                 h %= Nhash;
 475                 if(h < 0)
 476                         h += Nhash;
 477                 e->next = hash[h];
 478                 hash[h] = e;
 479         }
 480         prefix = -1;
 481         if(first)
 482                 output(io, CTM, csize);
 483         first = 0;
 484
 485         /*
 486          * Scan over pixels.  Because of partially filled bytes on ends of scan lines,
 487          * which must be ignored in the data stream passed to GIF, this is more
 488          * complex than we'd like.
 489          */
 490 Next:
 491         for(;;){
 492                 if(ld != 3){
 493                         /* beginning of scan line is difficult; prime the shift register */
 494                         if(x == r.min.x){
 495                                 if(datai == ndata)
 496                                         break;
 497                                 sreg = data[datai++];
 498                                 nbits = 8-((x&(7>>ld))<<ld);
 499                         }
 500                         x++;
 501                         if(x == r.max.x)
 502                                 x = r.min.x;
 503                 }
 504                 if(nbits == 0){
 505                         if(datai == ndata)
 506                                 break;
 507                         sreg = data[datai++];
 508                         nbits = 8;
 509                 }
 510                 nbits -= bitsperpixel;
 511                 c = sreg>>nbits & pm;
 512                 h = prefix<<24 | c<<8;
 513                 h %= Nhash;
 514                 if(h < 0)
 515                         h += Nhash;
 516                 oe = nil;
 517                 for(e = hash[h]; e!=nil; e=e->next){
 518                         if(e->prefix == prefix && e->exten == c){
 519                                 if(oe != nil){
 520                                         oe->next = e->next;
 521                                         e->next = hash[h];
 522                                         hash[h] = e;
 523                                 }
 524                                 prefix = e->index;
 525                                 goto Next;
 526                         }
 527                         oe = e;
 528                 }
 529
 530                 output(io, prefix, csize);
 531                 early = 0; /* peculiar tiff feature here for reference */
 532                 if(nentry == maxentry-early){
 533                         if(csize == 12){
 534                                 nbits += bitsperpixel;  /* unget pixel */
 535                                 x--;
 536                                 if(ld != 3 && x == r.min.x)
 537                                         datai--;
 538                                 output(io, CTM, csize);
 539                                 goto Init;
 540                         }
 541                         csize++;
 542                         maxentry = (1<<csize);
 543                 }
 544
 545                 e = &tbl[nentry];
 546                 e->prefix = prefix;
 547                 e->exten = c;
 548                 e->next = hash[h];
 549                 hash[h] = e;
 550
 551                 prefix = c;
 552                 nentry++;
 553         }
 554
 555         output(io, prefix, csize);
 556         output(io, EOD, csize);
 557         output(io, -1, csize);
 558         free(io);
 559         free(hash);
 560 }
 561
 562 static
 563 void*
 564 gifmalloc(ulong sz)
 565 {
 566         void *v;
 567         v = malloc(sz);
 568         if(v == nil) {
 569                 fprint(2, "WriteGIF: out of memory allocating %ld\n", sz);
 570 abort();
 571                 exits("mem");
 572         }
 573         memset(v, 0, sz);
 574         return v;
 575 }