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*
startgif0(Biobuf * fd,ulong chan,Rectangle r,int depth,int loopcount)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*
startgif(Biobuf * fd,Image * image,int loopcount)76 startgif(Biobuf *fd, Image *image, int loopcount)
77 {
78 return startgif0(fd, image->chan, image->r, image->depth, loopcount);
79 }
80
81 char*
memstartgif(Biobuf * fd,Memimage * memimage,int loopcount)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*
writegif0(Biobuf * fd,Image * image,Memimage * memimage,ulong chan,Rectangle r,char * comment,int dt,int trans)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*
writegif(Biobuf * fd,Image * image,char * comment,int dt,int trans)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*
memwritegif(Biobuf * fd,Memimage * memimage,char * comment,int dt,int trans)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
put2(Biobuf * fd,int i)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
getcolormap(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
writeheader(Biobuf * fd,Rectangle r,int depth,ulong chan,int loopcount)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
writecomment(Biobuf * fd,char * comment)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
writegraphiccontrol(Biobuf * fd,int dt,int trans)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
writedescriptor(Biobuf * fd,Rectangle r)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*
writedata(Biobuf * fd,Image * image,Memimage * memimage)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
endgif(Biobuf * fd)382 endgif(Biobuf *fd)
383 {
384 Bputc(fd, 0x3B);
385 Bflush(fd);
386 }
387
388 void
memendgif(Biobuf * fd)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
output(IO * io,int c,int n)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
encode(Biobuf * fd,Rectangle r,int depth,uchar * data,uint ndata)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*
gifmalloc(ulong sz)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 }
576