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