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