1 /*
2 ** Copyright 1994, Home Pages, Inc.
3 **
4 ** Please read the file COPYRIGHT for specific information.
5 **
6 ** Home Pages, Inc.
7 ** 257 Castro St. Suite 219
8 ** Mountain View, CA 94041
9 **
10 ** Phone: 1 415 903 5353
11 ** Fax: 1 415 903 5345
12 **
13 ** EMail: support@homepages.com
14 **
15 */
16
17 /* +-------------------------------------------------------------------+ */
18 /* | Copyright 1993, David Koblas (koblas@netcom.com) | */
19 /* | | */
20 /* | Permission to use, copy, modify, and to distribute this software | */
21 /* | and its documentation for any purpose is hereby granted without | */
22 /* | fee, provided that the above copyright notice appear in all | */
23 /* | copies and that both that copyright notice and this permission | */
24 /* | notice appear in supporting documentation. There is no | */
25 /* | representations about the suitability of this software for | */
26 /* | any purpose. this software is provided "as is" without express | */
27 /* | or implied warranty. | */
28 /* | | */
29 /* +-------------------------------------------------------------------+ */
30
31 /* ppmtogif.c - read a portable pixmap and produce a GIF file
32 **
33 ** Based on GIFENCOD by David Rowley <mgardi@watdscu.waterloo.edu>.A
34 ** Lempel-Zim compression based on "compress".
35 **
36 ** Copyright (C) 1989 by Jef Poskanzer.
37 **
38 ** Permission to use, copy, modify, and distribute this software and its
39 ** documentation for any purpose and without fee is hereby granted, provided
40 ** that the above copyright notice appear in all copies and that both that
41 ** copyright notice and this permission notice appear in supporting
42 ** documentation. This software is provided "as is" without express or
43 ** implied warranty.
44 **
45 ** The Graphics Interchange Format(c) is the Copyright property of
46 ** CompuServe Incorporated. GIF(sm) is a Service Mark property of
47 ** CompuServe Incorporated.
48 */
49
50 #include <stdio.h>
51 #include "gif.h"
52
53 #define TRUE 1
54 #define FALSE 0
55
56 #define PUTBYTE(v, fp) putc(v, fp)
57 #define PUTWORD(v, fp) do { \
58 putc(((v) & 0xff), fp); \
59 putc((((v) >> 8) & 0xff), fp); \
60 } while (0)
61
62 /*
63 * a code_int must be able to hold 2**BITS values of type int, and also -1
64 */
65 typedef int code_int;
66
67 typedef long int count_int;
68
69 static void putImage(FILE *, int, int, int, int, unsigned char *);
70 static void putColorMap(FILE *, int, unsigned char [GIF_MAXCOLORS][3]);
71 static void putDataBlocks(FILE *fp, int, unsigned char *);
72 static void putGif89Info(FILE *, GIF89info *);
73
74 static void output ( code_int code );
75 static void cl_block ( void );
76 static void cl_hash ( count_int hsize );
77 static void char_init ( void );
78 static void char_out ( int c );
79 static void flush_char ( void );
80
81 /*
82 **
83 */
84 struct cval {
85 int idx, cnt;
86 };
cvalCMP(struct cval * a,struct cval * b)87 static int cvalCMP(struct cval *a, struct cval *b)
88 {
89 return b->cnt - a->cnt;
90 }
optimizeCMAP(GIFStream * stream)91 static int optimizeCMAP(GIFStream *stream)
92 {
93 GIFData *cur, *img;
94 int count = 0;
95
96 for (cur = stream->data; cur != NULL; cur = cur->next) {
97 if (cur->type == gif_image) {
98 img = cur;
99 count++;
100 }
101 }
102 /*
103 ** No images, no optimizations...
104 ** or too many images...
105 */
106 if (count == 0 || count > 1)
107 return 0;
108
109 /*
110 ** One image, nice and simple...
111 ** Insure there is a global colormap, and optimize the
112 ** image too it.
113 */
114 {
115 int size;
116 unsigned char *dp = img->data.image.data;
117 unsigned char *ep = dp + img->width * img->height;
118 struct cval vals[256];
119 int i, j;
120 unsigned char tmap[256][3], rmap[256];
121
122
123 if ((size = img->data.image.cmapSize) == 0)
124 size = stream->cmapSize;
125
126 for (i = 0; i < size; i++) {
127 vals[i].idx = i;
128 vals[i].cnt = 0;
129 }
130 for (dp = img->data.image.data, i = 0; dp < ep; i++, dp++)
131 vals[*dp].cnt++;
132
133 /*
134 ** Quite, I'm doing a bubble sort... ACK!
135 */
136 qsort(vals, size, sizeof(vals[0]), cvalCMP);
137
138 for (i = 0; i < size; i++)
139 if (vals[i].idx != i)
140 break;
141 /*
142 ** Already sorted, no change!
143 */
144 if (i == size)
145 return 1;
146 for (i = 0; i < size; i++)
147 rmap[vals[i].idx] = i;
148
149 /*
150 ** Now reorder the colormap, and the image
151 */
152 for (dp = img->data.image.data, i = 0; dp < ep; i++, dp++)
153 *dp = rmap[*dp];
154 if (img->info.transparent != -1)
155 img->info.transparent = rmap[img->info.transparent];
156 /*
157 ** Toast the local colormap
158 */
159 if (img->data.image.cmapSize != 0) {
160 for (i = 0; i < size; i++) {
161 stream->cmapData[i][0] =
162 img->data.image.cmapData[i][0];
163 stream->cmapData[i][1] =
164 img->data.image.cmapData[i][1];
165 stream->cmapData[i][2] =
166 img->data.image.cmapData[i][2];
167 }
168 img->data.image.cmapSize = 0;
169 stream->cmapSize = size;
170 }
171
172 /*
173 ** Now finally reorer the colormap
174 */
175 for (i = 0; i < size; i++) {
176 tmap[i][0] = stream->cmapData[i][0];
177 tmap[i][1] = stream->cmapData[i][1];
178 tmap[i][2] = stream->cmapData[i][2];
179 }
180 for (i = 0; i < size; i++) {
181 stream->cmapData[rmap[i]][0] = tmap[i][0];
182 stream->cmapData[rmap[i]][1] = tmap[i][1];
183 stream->cmapData[rmap[i]][2] = tmap[i][2];
184 }
185 }
186 return 1;
187 }
188
189
190 /*
191 ** Return the ceiling log of n
192 */
binaryLog(int val)193 static int binaryLog(int val)
194 {
195 int i;
196
197 if (val == 0)
198 return 0;
199
200 for (i = 1; i <= 8; i++)
201 if (val <= (1 << i))
202 return i;
203 return 8;
204 }
205
GIFWriteFP(FILE * fp,GIFStream * stream,int optimize)206 int GIFWriteFP(FILE *fp, GIFStream *stream, int optimize)
207 {
208 GIFData *cur;
209 int flag = FALSE;
210 int c;
211 int globalBitsPP = 0;
212 int resolution;
213
214 if (fp == NULL)
215 return TRUE;
216 if (stream == NULL)
217 return FALSE;
218
219 /*
220 ** First find if this is a 87A or an 89A GIF image
221 ** also, figure out the color resolution of the image.
222 */
223 resolution = binaryLog(stream->cmapSize) - 1;
224 for (cur = stream->data; !flag && cur != NULL; cur = cur->next) {
225 if (cur->type == gif_text || cur->type == gif_comment) {
226 flag = TRUE;
227 } else if (cur->type == gif_image) {
228 int v = binaryLog(cur->data.image.cmapSize);
229
230 if (v > resolution)
231 resolution = v;
232
233 /*
234 ** Uses one of the 89 extensions.
235 */
236 if (cur->info.transparent != -1 ||
237 cur->info.delayTime != 0 ||
238 cur->info.inputFlag != 0 ||
239 cur->info.disposal != 0)
240 flag = TRUE;
241 }
242 }
243 /*
244 **
245 */
246 if (optimize)
247 optimize = optimizeCMAP(stream);
248
249 fwrite(flag ? "GIF89a" : "GIF87a", 1, 6, fp);
250
251 PUTWORD(stream->width, fp);
252 PUTWORD(stream->height, fp);
253
254 /*
255 ** assume 256 entry color resution, and non sorted colormap
256 */
257 c = ((resolution & 0x07) << 5) | 0x00;
258 if (stream->cmapSize != 0) {
259 globalBitsPP = binaryLog(stream->cmapSize);
260 c |= 0x80;
261 c |= globalBitsPP - 1;
262 }
263 /*
264 ** Is the global colormap optimized?
265 */
266 if (optimize)
267 c |= 0x08;
268 PUTBYTE(c, fp);
269
270 PUTBYTE(stream->background, fp);
271 PUTBYTE(stream->aspectRatio, fp);
272
273 putColorMap(fp, stream->cmapSize, stream->cmapData);
274
275 for (cur = stream->data; cur != NULL; cur = cur->next) {
276 if (cur->type == gif_image) {
277 int bpp;
278
279 putGif89Info(fp, &cur->info);
280
281 PUTBYTE(0x2c, fp);
282 PUTWORD(cur->x, fp);
283 PUTWORD(cur->y, fp);
284 PUTWORD(cur->width, fp);
285 PUTWORD(cur->height, fp);
286
287 c = cur->data.image.interlaced ? 0x40 : 0x00;
288 if (cur->data.image.cmapSize != 0) {
289 bpp = binaryLog(cur->data.image.cmapSize);
290 c |= 0x80;
291 c |= bpp;
292 } else {
293 bpp = globalBitsPP;
294 }
295
296 PUTBYTE(c, fp);
297
298 putColorMap(fp, cur->data.image.cmapSize,
299 cur->data.image.cmapData);
300
301 putImage(fp, cur->data.image.interlaced, bpp,
302 cur->width, cur->height,
303 cur->data.image.data);
304 } else if (cur->type == gif_comment) {
305 PUTBYTE('!', fp);
306 PUTBYTE(0xfe, fp);
307 putDataBlocks(fp, cur->data.comment.len,
308 (unsigned char*)cur->data.comment.text);
309 } else if (cur->type == gif_text) {
310 putGif89Info(fp, &cur->info);
311
312 PUTBYTE('!', fp);
313 PUTBYTE(0x01, fp);
314
315 PUTWORD(cur->x, fp);
316 PUTWORD(cur->y, fp);
317 PUTWORD(cur->width, fp);
318 PUTWORD(cur->height, fp);
319
320 PUTBYTE(cur->data.text.cellWidth, fp);
321 PUTBYTE(cur->data.text.cellHeight, fp);
322 PUTBYTE(cur->data.text.fg, fp);
323 PUTBYTE(cur->data.text.bg, fp);
324
325 putDataBlocks(fp, cur->data.text.len,
326 (unsigned char*)cur->data.text.text);
327 }
328 }
329
330 /*
331 ** Write termination
332 */
333 PUTBYTE(';', fp);
334
335 return FALSE;
336 }
337
GIFWrite(char * file,GIFStream * stream,int optimize)338 int GIFWrite(char *file, GIFStream *stream, int optimize)
339 {
340 if (stream != NULL) {
341 FILE *fp = fopen(file, "wb");
342
343 if (fp != NULL) {
344 int s = GIFWriteFP(fp, stream, optimize);
345 fclose(fp);
346 return s;
347 }
348 }
349 return TRUE;
350 }
351
putColorMap(FILE * fp,int size,unsigned char data[GIF_MAXCOLORS][3])352 static void putColorMap(FILE *fp, int size, unsigned char data[GIF_MAXCOLORS][3])
353 {
354 int i;
355
356 for (i = 0; i < size; i++) {
357 PUTBYTE(data[i][0], fp);
358 PUTBYTE(data[i][1], fp);
359 PUTBYTE(data[i][2], fp);
360 }
361 }
362
putDataBlocks(FILE * fp,int size,unsigned char * data)363 static void putDataBlocks(FILE *fp, int size, unsigned char *data)
364 {
365 int n;
366
367 while (size > 0) {
368 n = size > 255 ? 255 : size;
369
370 PUTBYTE(n, fp);
371 fwrite(data, 1, n, fp);
372 data += n;
373 size -= n;
374 }
375 PUTBYTE(0, fp); /* End Block */
376 }
377
putGif89Info(FILE * fp,GIF89info * info)378 static void putGif89Info(FILE *fp, GIF89info *info)
379 {
380 unsigned char c;
381
382 if (info->transparent == -1 &&
383 info->delayTime == 0 &&
384 info->inputFlag == 0 &&
385 info->disposal == 0)
386 return;
387
388 PUTBYTE('!', fp);
389 PUTBYTE(0xf9, fp);
390 PUTBYTE(4, fp);
391 c = (info->inputFlag ? 0x02 : 0x00) |
392 ((info->disposal & 0x07) << 2) |
393 ((info->transparent != -1) ? 0x01 : 0x00);
394 PUTBYTE(c, fp);
395 PUTWORD(info->delayTime, fp);
396 PUTBYTE(info->transparent, fp);
397
398 /*
399 ** End
400 */
401 PUTBYTE(0, fp);
402 }
403
404
405 /***************************************************************************
406 *
407 * GIFCOMPR.C - GIF Image compression routines
408 *
409 * Lempel-Ziv compression based on 'compress'. GIF modifications by
410 * David Rowley (mgardi@watdcsu.waterloo.edu)
411 *
412 ***************************************************************************/
413
414 /*
415 * General DEFINEs
416 */
417
418 #define BITS 12
419
420 #define HSIZE 5003 /* 80% occupancy */
421
422 #ifdef NO_UCHAR
423 typedef char char_type;
424 #else /*NO_UCHAR*/
425 typedef unsigned char char_type;
426 #endif /*NO_UCHAR*/
427
428 /*
429 *
430 * GIF Image compression - modified 'compress'
431 *
432 * Based on: compress.c - File compression ala IEEE Computer, June 1984.
433 *
434 * By Authors: Spencer W. Thomas (decvax!harpo!utah-cs!utah-gr!thomas)
435 * Jim McKie (decvax!mcvax!jim)
436 * Steve Davies (decvax!vax135!petsd!peora!srd)
437 * Ken Turkowski (decvax!decwrl!turtlevax!ken)
438 * James A. Woods (decvax!ihnp4!ames!jaw)
439 * Joe Orost (decvax!vax135!petsd!joe)
440 *
441 */
442 #include <ctype.h>
443
444 #define ARGVAL() (*++(*argv) || (--argc && *++argv))
445
446 static int n_bits; /* number of bits/code */
447 static int maxbits; /* user settable max # bits/code */
448 static code_int maxcode; /* maximum code, given n_bits */
449 static code_int maxmaxcode; /* should NEVER generate this code */
450 # define MAXCODE(n_bits) (((code_int) 1 << (n_bits)) - 1)
451
452 static count_int htab [HSIZE];
453 static unsigned short codetab [HSIZE];
454 #define HashTabOf(i) htab[i]
455 #define CodeTabOf(i) codetab[i]
456
457 static code_int hsize; /* for dynamic table sizing */
458
459 static unsigned long cur_accum;
460 static int cur_bits;
461
462 /*
463 * To save much memory, we overlay the table used by compress() with those
464 * used by decompress(). The tab_prefix table is the same size and type
465 * as the codetab. The tab_suffix table needs 2**BITS characters. We
466 * get this from the beginning of htab. The output stack uses the rest
467 * of htab, and contains characters. There is plenty of room for any
468 * possible stack (stack used to be 8000 characters).
469 */
470
471 #define tab_prefixof(i) CodeTabOf(i)
472 #define tab_suffixof(i) ((char_type*)(htab))[i]
473 #define de_stack ((char_type*)&tab_suffixof((code_int)1<<BITS))
474
475 static code_int free_ent; /* first unused entry */
476
477 /*
478 * block compression parameters -- after all codes are used up,
479 * and compression rate changes, start over.
480 */
481 static int clear_flg;
482
483 static int offset;
484
485 /*
486 * compress stdin to stdout
487 *
488 * Algorithm: use open addressing double hashing (no chaining) on the
489 * prefix code / next character combination. We do a variant of Knuth's
490 * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
491 * secondary probe. Here, the modular division first probe is gives way
492 * to a faster exclusive-or manipulation. Also do block compression with
493 * an adaptive reset, whereby the code table is cleared when the compression
494 * ratio decreases, but after the table fills. The variable-length output
495 * codes are re-sized at this point, and a special CLEAR code is generated
496 * for the decompressor. Late addition: construct the table according to
497 * file size for noticeable speed improvement on small files. Please direct
498 * questions about this implementation to ames!jaw.
499 */
500
501 static int g_init_bits;
502 static FILE* g_outfile;
503
504 static int ClearCode;
505 static int EOFCode;
506
putImage(FILE * fp,int interlaced,int bpp,int width,int height,unsigned char * data)507 static void putImage(FILE *fp, int interlaced, int bpp, int width, int height,
508 unsigned char *data)
509 {
510 unsigned char *end = data + width * height;
511 int left = interlaced ? width : width * height;
512 int cury = 0, pass = 0;
513 unsigned char *dp = data;
514 long fcode;
515 code_int v, i, ent, disp, hsize_reg;
516 int c, hshift;
517 int skip = 8;
518
519 if (bpp <= 1) {
520 g_init_bits = 3;
521 PUTBYTE(2, fp);
522 } else {
523 g_init_bits = bpp + 1;
524 PUTBYTE(bpp, fp);
525 }
526
527 /*
528 ** Set up the globals: g_init_bits - initial number of bits
529 ** g_outfile - pointer to output file
530 */
531 g_outfile = fp;
532
533 /*
534 ** Set up the necessary values
535 */
536 offset = 0;
537 clear_flg = FALSE;
538 maxbits = BITS;
539 maxmaxcode = 1 << BITS;
540 maxcode = MAXCODE(n_bits = g_init_bits);
541 hsize = HSIZE;
542 cur_accum = 0;
543 cur_bits = 0;
544
545 ClearCode = (1 << (g_init_bits - 1));
546 EOFCode = ClearCode + 1;
547 free_ent = ClearCode + 2;
548
549 char_init(); /* clear the output accumulator */
550
551 hshift = 0;
552 for (fcode = (long)hsize; fcode < 65536; fcode *= 2)
553 ++hshift;
554 hshift = 8 - hshift; /* set hash code range bound */
555
556 hsize_reg = hsize;
557 cl_hash((count_int)hsize); /* clear hash table */
558
559 output((code_int)ClearCode);
560
561 ent = *dp++;
562 do {
563 again:
564 /*
565 ** Fetch the next pixel
566 */
567 c = *dp++;
568 if (--left == 0) {
569 if (interlaced) {
570 do {
571 switch (pass) {
572 case 0:
573 cury += 8;
574 if (cury >= height) {
575 pass++;
576 cury = 4;
577 }
578 break;
579 case 1:
580 cury += 8;
581 if (cury >= height) {
582 pass++;
583 cury = 2;
584 }
585 break;
586 case 2:
587 cury += 4;
588 if (cury >= height) {
589 pass++;
590 cury = 1;
591 }
592 break;
593 case 3:
594 cury += 2;
595 break;
596 }
597 } while (pass < 3 && cury >= height);
598 if (cury >= height)
599 goto done;
600 dp = data + cury * width;
601 left = width;
602 c = *dp++;
603 } else {
604 goto done;
605 }
606 }
607
608
609 /*
610 ** Now output it...
611 */
612
613 fcode = (long) (((long) c << maxbits) + ent);
614
615 i = (((code_int)c << hshift) ^ ent); /* xor hashing */
616 v = HashTabOf(i);
617
618 if (v == fcode) {
619 ent = CodeTabOf (i);
620 goto again;
621 } else if (v >= 0) {
622 /*
623 ** secondary hash (after G. Knott)
624 */
625 disp = hsize_reg - i;
626 if (i == 0)
627 disp = 1;
628 do {
629 if ((i -= disp) < 0)
630 i += hsize_reg;
631
632 v = HashTabOf(i);
633 if (v == fcode) {
634 ent = CodeTabOf(i);
635 goto again;
636 }
637 } while (v > 0);
638 }
639
640 output((code_int)ent);
641 ent = c;
642 if (free_ent < maxmaxcode) {
643 CodeTabOf(i) = free_ent++; /* code -> hashtable */
644 HashTabOf(i) = fcode;
645 } else {
646 cl_block();
647 }
648 } while (1);
649 done:
650 /*
651 ** Put out the final code.
652 **/
653 output((code_int)ent);
654 output((code_int)EOFCode);
655
656 /*
657 ** End block byte
658 */
659 PUTBYTE(0x00, fp);
660 }
661
662 /*****************************************************************
663 * TAG( output )
664 *
665 * Output the given code.
666 * Inputs:
667 * code: A n_bits-bit integer. If == -1, then EOF. This assumes
668 * that n_bits =< (long)wordsize - 1.
669 * Outputs:
670 * Outputs code to the file.
671 * Assumptions:
672 * Chars are 8 bits long.
673 * Algorithm:
674 * Maintain a BITS character long buffer (so that 8 codes will
675 * fit in it exactly). Use the VAX insv instruction to insert each
676 * code in turn. When the buffer fills up empty it and start over.
677 */
678
679 static unsigned long masks[] = { 0x0000,
680 0x0001, 0x0003, 0x0007, 0x000F,
681 0x001F, 0x003F, 0x007F, 0x00FF,
682 0x01FF, 0x03FF, 0x07FF, 0x0FFF,
683 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF };
684
output(code_int code)685 static void output(code_int code)
686 {
687 cur_accum &= masks[ cur_bits ];
688
689 if( cur_bits > 0 )
690 cur_accum |= ((long)code << cur_bits);
691 else
692 cur_accum = code;
693
694 cur_bits += n_bits;
695
696 while( cur_bits >= 8 ) {
697 char_out( (unsigned int)(cur_accum & 0xff) );
698 cur_accum >>= 8;
699 cur_bits -= 8;
700 }
701
702 /*
703 ** If the next entry is going to be too big for the code size,
704 ** then increase it, if possible.
705 */
706 if (free_ent > maxcode || clear_flg) {
707 if( clear_flg ) {
708 maxcode = MAXCODE (n_bits = g_init_bits);
709 clear_flg = FALSE;
710 } else {
711 ++n_bits;
712 if ( n_bits == maxbits )
713 maxcode = maxmaxcode;
714 else
715 maxcode = MAXCODE(n_bits);
716 }
717 }
718
719 if (code == EOFCode) {
720 /*
721 ** At EOF, write the rest of the buffer.
722 */
723 while (cur_bits > 0) {
724 char_out((unsigned int)(cur_accum & 0xff));
725 cur_accum >>= 8;
726 cur_bits -= 8;
727 }
728
729 flush_char();
730
731 fflush(g_outfile);
732 }
733 }
734
735 /*
736 * Clear out the hash table
737 */
cl_block()738 static void cl_block()
739 {
740
741 cl_hash((count_int)hsize);
742 free_ent = ClearCode + 2;
743 clear_flg = TRUE;
744
745 output((code_int)ClearCode);
746 }
747
cl_hash(count_int hsize)748 static void cl_hash(count_int hsize) /* reset code table */
749 {
750 int i;
751
752 for (i = 0; i < hsize; i++)
753 htab[i] = -1;
754 }
755
756 /******************************************************************************
757 *
758 * GIF Specific routines
759 *
760 ******************************************************************************/
761
762 /*
763 ** Number of characters so far in this 'packet'
764 */
765 static int a_count;
766
767 /*
768 ** Define the storage for the packet accumulator
769 */
770 static char accum[256];
771
772
773 /*
774 ** Set up the 'byte output' routine
775 */
char_init()776 static void char_init()
777 {
778 a_count = 0;
779 }
780
781 /*
782 ** Add a character to the end of the current packet, and if it is 254
783 ** characters, flush the packet to disk.
784 */
char_out(int c)785 static void char_out(int c)
786 {
787 accum[a_count++] = c;
788 if (a_count == 255)
789 flush_char();
790 }
791
792 /*
793 ** Flush the packet to disk, and reset the accumulator
794 */
flush_char()795 static void flush_char()
796 {
797 if (a_count != 0) {
798 PUTBYTE(a_count, g_outfile);
799 fwrite(accum, 1, a_count, g_outfile);
800 a_count = 0;
801 }
802 }
803