1 #include <stdio.h>
2 #include <math.h>
3 #include <string.h>
4 #include <stdlib.h>
5 #include "gd.h"
6
7 /* Code drawn from ppmtogif.c, from the pbmplus package
8 **
9 ** Based on GIFENCOD by David Rowley <mgardi@watdscu.waterloo.edu>. A
10 ** Lempel-Zim compression based on "compress".
11 **
12 ** Modified by Marcel Wijkstra <wijkstra@fwi.uva.nl>
13 **
14 ** Copyright (C) 1989 by Jef Poskanzer.
15 **
16 ** Permission to use, copy, modify, and distribute this software and its
17 ** documentation for any purpose and without fee is hereby granted, provided
18 ** that the above copyright notice appear in all copies and that both that
19 ** copyright notice and this permission notice appear in supporting
20 ** documentation. This software is provided "as is" without express or
21 ** implied warranty.
22 **
23 ** The Graphics Interchange Format(c) is the Copyright property of
24 ** CompuServe Incorporated. GIF(sm) is a Service Mark property of
25 ** CompuServe Incorporated.
26 */
27
28 /*
29 * a code_int must be able to hold 2**GIFBITS values of type int, and also -1
30 */
31 typedef int code_int;
32
33 #ifdef SIGNED_COMPARE_SLOW
34 typedef unsigned long int count_int;
35 typedef unsigned short int count_short;
36 #else /*SIGNED_COMPARE_SLOW*/
37 typedef long int count_int;
38 #endif /*SIGNED_COMPARE_SLOW*/
39
40 /* 2.0.28: threadsafe */
41
42 #define maxbits GIFBITS
43
44 /* should NEVER generate this code */
45 #define maxmaxcode ((code_int)1 << GIFBITS)
46
47 #define HSIZE 5003 /* 80% occupancy */
48 #define hsize HSIZE /* Apparently invariant, left over from
49 compress */
50
51 typedef struct {
52 int Width, Height;
53 int curx, cury;
54 long CountDown;
55 int Pass;
56 int Interlace;
57 int n_bits; /* number of bits/code */
58 code_int maxcode; /* maximum code, given n_bits */
59 count_int htab [HSIZE];
60 unsigned short codetab [HSIZE];
61 code_int free_ent; /* first unused entry */
62 /*
63 * block compression parameters -- after all codes are used up,
64 * and compression rate changes, start over.
65 */
66 int clear_flg;
67 int offset;
68 long int in_count; /* length of input */
69 long int out_count; /* # of codes output (for debugging) */
70
71 int g_init_bits;
72 gdIOCtx * g_outfile;
73
74 int ClearCode;
75 int EOFCode;
76 unsigned long cur_accum;
77 int cur_bits;
78 /*
79 * Number of characters so far in this 'packet'
80 */
81 int a_count;
82 /*
83 * Define the storage for the packet accumulator
84 */
85 char accum[ 256 ];
86 } GifCtx;
87
88 static int gifPutWord(int w, gdIOCtx *out);
89 static int colorstobpp(int colors);
90 static void BumpPixel (GifCtx *ctx);
91 static int GIFNextPixel (gdImagePtr im, GifCtx *ctx);
92 static void GIFEncode (gdIOCtxPtr fp, int GWidth, int GHeight, int GInterlace, int Background, int Transparent, int BitsPerPixel, int *Red, int *Green, int *Blue, gdImagePtr im);
93 static void compress (int init_bits, gdIOCtx *outfile, gdImagePtr im, GifCtx *ctx);
94 static void output (code_int code, GifCtx *ctx);
95 static void cl_block (GifCtx *ctx);
96 static void cl_hash (register count_int chsize, GifCtx *ctx);
97 static void char_init (GifCtx *ctx);
98 static void char_out (int c, GifCtx *ctx);
99 static void flush_char (GifCtx *ctx);
100 void * gdImageGifPtr (gdImagePtr im, int *size)
101 {
102 void *rv;
103 gdIOCtx *out = gdNewDynamicCtx (2048, NULL);
104 gdImageGifCtx (im, out);
105 rv = gdDPExtractData (out, size);
106 out->gd_free (out);
107 return rv;
108 }
109
110 void gdImageGif (gdImagePtr im, FILE * outFile)
111 {
112 gdIOCtx *out = gdNewFileCtx (outFile);
113 gdImageGifCtx (im, out);
114 out->gd_free (out);
115 }
116
117 void gdImageGifCtx(gdImagePtr im, gdIOCtxPtr out)
118 {
119 gdImagePtr pim = 0, tim = im;
120 int interlace, BitsPerPixel;
121 interlace = im->interlace;
122 if (im->trueColor) {
123 /* Expensive, but the only way that produces an
124 acceptable result: mix down to a palette
125 based temporary image. */
126 pim = gdImageCreatePaletteFromTrueColor(im, 1, 256);
127 if (!pim) {
128 return;
129 }
130 tim = pim;
131 }
132 BitsPerPixel = colorstobpp(tim->colorsTotal);
133 /* All set, let's do it. */
134 GIFEncode(
135 out, tim->sx, tim->sy, tim->interlace, 0, tim->transparent, BitsPerPixel,
136 tim->red, tim->green, tim->blue, tim);
137 if (pim) {
138 /* Destroy palette based temporary image. */
139 gdImageDestroy( pim);
140 }
141 }
142
143 static int
144 colorstobpp(int colors)
145 {
146 int bpp = 0;
147
148 if ( colors <= 2 )
149 bpp = 1;
150 else if ( colors <= 4 )
151 bpp = 2;
152 else if ( colors <= 8 )
153 bpp = 3;
154 else if ( colors <= 16 )
155 bpp = 4;
156 else if ( colors <= 32 )
157 bpp = 5;
158 else if ( colors <= 64 )
159 bpp = 6;
160 else if ( colors <= 128 )
161 bpp = 7;
162 else if ( colors <= 256 )
163 bpp = 8;
164 return bpp;
165 }
166
167 /*****************************************************************************
168 *
169 * GIFENCODE.C - GIF Image compression interface
170 *
171 * GIFEncode( FName, GHeight, GWidth, GInterlace, Background, Transparent,
172 * BitsPerPixel, Red, Green, Blue, gdImagePtr )
173 *
174 *****************************************************************************/
175
176 #define TRUE 1
177 #define FALSE 0
178 /*
179 * Bump the 'curx' and 'cury' to point to the next pixel
180 */
181 static void
182 BumpPixel(GifCtx *ctx)
183 {
184 /*
185 * Bump the current X position
186 */
187 ++(ctx->curx);
188
189 /*
190 * If we are at the end of a scan line, set curx back to the beginning
191 * If we are interlaced, bump the cury to the appropriate spot,
192 * otherwise, just increment it.
193 */
194 if( ctx->curx == ctx->Width ) {
195 ctx->curx = 0;
196
197 if( !ctx->Interlace )
198 ++(ctx->cury);
199 else {
200 switch( ctx->Pass ) {
201
202 case 0:
203 ctx->cury += 8;
204 if( ctx->cury >= ctx->Height ) {
205 ++(ctx->Pass);
206 ctx->cury = 4;
207 }
208 break;
209
210 case 1:
211 ctx->cury += 8;
212 if( ctx->cury >= ctx->Height ) {
213 ++(ctx->Pass);
214 ctx->cury = 2;
215 }
216 break;
217
218 case 2:
219 ctx->cury += 4;
220 if( ctx->cury >= ctx->Height ) {
221 ++(ctx->Pass);
222 ctx->cury = 1;
223 }
224 break;
225
226 case 3:
227 ctx->cury += 2;
228 break;
229 }
230 }
231 }
232 }
233
234 /*
235 * Return the next pixel from the image
236 */
237 static int
238 GIFNextPixel(gdImagePtr im, GifCtx *ctx)
239 {
240 int r;
241
242 if( ctx->CountDown == 0 )
243 return EOF;
244
245 --(ctx->CountDown);
246
247 r = gdImageGetPixel(im, ctx->curx, ctx->cury);
248
249 BumpPixel(ctx);
250
251 return r;
252 }
253
254 /* public */
255
256 static void
257 GIFEncode(gdIOCtxPtr fp, int GWidth, int GHeight, int GInterlace, int Background, int Transparent, int BitsPerPixel, int *Red, int *Green, int *Blue, gdImagePtr im)
258 {
259 int B;
260 int RWidth, RHeight;
261 int LeftOfs, TopOfs;
262 int Resolution;
263 int ColorMapSize;
264 int InitCodeSize;
265 int i;
266 GifCtx ctx;
267
268 memset(&ctx, 0, sizeof(ctx));
269 ctx.Interlace = GInterlace;
270 ctx.in_count = 1;
271
272 ColorMapSize = 1 << BitsPerPixel;
273
274 RWidth = ctx.Width = GWidth;
275 RHeight = ctx.Height = GHeight;
276 LeftOfs = TopOfs = 0;
277
278 Resolution = BitsPerPixel;
279
280 /*
281 * Calculate number of bits we are expecting
282 */
283 ctx.CountDown = (long)ctx.Width * (long)ctx.Height;
284
285 /*
286 * Indicate which pass we are on (if interlace)
287 */
288 ctx.Pass = 0;
289
290 /*
291 * The initial code size
292 */
293 if( BitsPerPixel <= 1 )
294 InitCodeSize = 2;
295 else
296 InitCodeSize = BitsPerPixel;
297
298 /*
299 * Set up the current x and y position
300 */
301 ctx.curx = ctx.cury = 0;
302
303 /*
304 * Write the Magic header
305 */
306 gdPutBuf(Transparent < 0 ? "GIF87a" : "GIF89a", 6, fp );
307
308 /*
309 * Write out the screen width and height
310 */
311 gifPutWord( RWidth, fp );
312 gifPutWord( RHeight, fp );
313
314 /*
315 * Indicate that there is a global colour map
316 */
317 B = 0x80; /* Yes, there is a color map */
318
319 /*
320 * OR in the resolution
321 */
322 B |= (Resolution - 1) << 5;
323
324 /*
325 * OR in the Bits per Pixel
326 */
327 B |= (BitsPerPixel - 1);
328
329 /*
330 * Write it out
331 */
332 gdPutC( B, fp );
333
334 /*
335 * Write out the Background colour
336 */
337 gdPutC( Background, fp );
338
339 /*
340 * Byte of 0's (future expansion)
341 */
342 gdPutC( 0, fp );
343
344 /*
345 * Write out the Global Colour Map
346 */
347 for( i=0; i<ColorMapSize; ++i ) {
348 gdPutC( Red[i], fp );
349 gdPutC( Green[i], fp );
350 gdPutC( Blue[i], fp );
351 }
352
353 /*
354 * Write out extension for transparent colour index, if necessary.
355 */
356 if ( Transparent >= 0 ) {
357 gdPutC( '!', fp );
358 gdPutC( 0xf9, fp );
359 gdPutC( 4, fp );
360 gdPutC( 1, fp );
361 gdPutC( 0, fp );
362 gdPutC( 0, fp );
363 gdPutC( (unsigned char) Transparent, fp );
364 gdPutC( 0, fp );
365 }
366
367 /*
368 * Write an Image separator
369 */
370 gdPutC( ',', fp );
371
372 /*
373 * Write the Image header
374 */
375
376 gifPutWord( LeftOfs, fp );
377 gifPutWord( TopOfs, fp );
378 gifPutWord( ctx.Width, fp );
379 gifPutWord( ctx.Height, fp );
380
381 /*
382 * Write out whether or not the image is interlaced
383 */
384 if( ctx.Interlace )
385 gdPutC( 0x40, fp );
386 else
387 gdPutC( 0x00, fp );
388
389 /*
390 * Write out the initial code size
391 */
392 gdPutC( InitCodeSize, fp );
393
394 /*
395 * Go and actually compress the data
396 */
397 compress( InitCodeSize+1, fp, im, &ctx );
398
399 /*
400 * Write out a Zero-length packet (to end the series)
401 */
402 gdPutC( 0, fp );
403
404 /*
405 * Write the GIF file terminator
406 */
407 gdPutC( ';', fp );
408 }
409
410 /***************************************************************************
411 *
412 * GIFCOMPR.C - GIF Image compression routines
413 *
414 * Lempel-Ziv compression based on 'compress'. GIF modifications by
415 * David Rowley (mgardi@watdcsu.waterloo.edu)
416 *
417 ***************************************************************************/
418
419 /*
420 * General DEFINEs
421 */
422
423 #define GIFBITS 12
424
425 #ifdef NO_UCHAR
426 typedef char char_type;
427 #else /*NO_UCHAR*/
428 typedef unsigned char char_type;
429 #endif /*NO_UCHAR*/
430
431 /*
432 *
433 * GIF Image compression - modified 'compress'
434 *
435 * Based on: compress.c - File compression ala IEEE Computer, June 1984.
436 *
437 * By Authors: Spencer W. Thomas (decvax!harpo!utah-cs!utah-gr!thomas)
438 * Jim McKie (decvax!mcvax!jim)
439 * Steve Davies (decvax!vax135!petsd!peora!srd)
440 * Ken Turkowski (decvax!decwrl!turtlevax!ken)
441 * James A. Woods (decvax!ihnp4!ames!jaw)
442 * Joe Orost (decvax!vax135!petsd!joe)
443 *
444 */
445 #include <ctype.h>
446
447 #define ARGVAL() (*++(*argv) || (--argc && *++argv))
448
449 #ifdef COMPATIBLE /* But wrong! */
450 # define MAXCODE(n_bits) ((code_int) 1 << (n_bits) - 1)
451 #else /*COMPATIBLE*/
452 # define MAXCODE(n_bits) (((code_int) 1 << (n_bits)) - 1)
453 #endif /*COMPATIBLE*/
454
455 #define HashTabOf(i) ctx->htab[i]
456 #define CodeTabOf(i) ctx->codetab[i]
457
458
459 /*
460 * To save much memory, we overlay the table used by compress() with those
461 * used by decompress(). The tab_prefix table is the same size and type
462 * as the codetab. The tab_suffix table needs 2**GIFBITS characters. We
463 * get this from the beginning of htab. The output stack uses the rest
464 * of htab, and contains characters. There is plenty of room for any
465 * possible stack (stack used to be 8000 characters).
466 */
467
468 #define tab_prefixof(i) CodeTabOf(i)
469 #define tab_suffixof(i) ((char_type*)(htab))[i]
470 #define de_stack ((char_type*)&tab_suffixof((code_int)1<<GIFBITS))
471
472 /*
473 * compress stdin to stdout
474 *
475 * Algorithm: use open addressing double hashing (no chaining) on the
476 * prefix code / next character combination. We do a variant of Knuth's
477 * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
478 * secondary probe. Here, the modular division first probe is gives way
479 * to a faster exclusive-or manipulation. Also do block compression with
480 * an adaptive reset, whereby the code table is cleared when the compression
481 * ratio decreases, but after the table fills. The variable-length output
482 * codes are re-sized at this point, and a special CLEAR code is generated
483 * for the decompressor. Late addition: construct the table according to
484 * file size for noticeable speed improvement on small files. Please direct
485 * questions about this implementation to ames!jaw.
486 */
487
488 static void
489 output(code_int code, GifCtx *ctx);
490
491 static void
492 compress(int init_bits, gdIOCtxPtr outfile, gdImagePtr im, GifCtx *ctx)
493 {
494 register long fcode;
495 register code_int i /* = 0 */;
496 register int c;
497 register code_int ent;
498 register code_int disp;
499 register code_int hsize_reg;
500 register int hshift;
501
502 /*
503 * Set up the globals: g_init_bits - initial number of bits
504 * g_outfile - pointer to output file
505 */
506 ctx->g_init_bits = init_bits;
507 ctx->g_outfile = outfile;
508
509 /*
510 * Set up the necessary values
511 */
512 ctx->offset = 0;
513 ctx->out_count = 0;
514 ctx->clear_flg = 0;
515 ctx->in_count = 1;
516 ctx->maxcode = MAXCODE(ctx->n_bits = ctx->g_init_bits);
517
518 ctx->ClearCode = (1 << (init_bits - 1));
519 ctx->EOFCode = ctx->ClearCode + 1;
520 ctx->free_ent = ctx->ClearCode + 2;
521
522 char_init(ctx);
523
524 ent = GIFNextPixel( im, ctx );
525
526 hshift = 0;
527 for ( fcode = (long) hsize; fcode < 65536L; fcode *= 2L )
528 ++hshift;
529 hshift = 8 - hshift; /* set hash code range bound */
530
531 hsize_reg = hsize;
532 cl_hash( (count_int) hsize_reg, ctx ); /* clear hash table */
533
534 output( (code_int)ctx->ClearCode, ctx );
535
536 #ifdef SIGNED_COMPARE_SLOW
537 while ( (c = GIFNextPixel( im )) != (unsigned) EOF ) {
538 #else /*SIGNED_COMPARE_SLOW*/
539 while ( (c = GIFNextPixel( im, ctx )) != EOF ) { /* } */
540 #endif /*SIGNED_COMPARE_SLOW*/
541
542 ++(ctx->in_count);
543
544 fcode = (long) (((long) c << maxbits) + ent);
545 i = (((code_int)c << hshift) ^ ent); /* xor hashing */
546
547 if ( HashTabOf (i) == fcode ) {
548 ent = CodeTabOf (i);
549 continue;
550 } else if ( (long)HashTabOf (i) < 0 ) /* empty slot */
551 goto nomatch;
552 disp = hsize_reg - i; /* secondary hash (after G. Knott) */
553 if ( i == 0 )
554 disp = 1;
555 probe:
556 if ( (i -= disp) < 0 )
557 i += hsize_reg;
558
559 if ( HashTabOf (i) == fcode ) {
560 ent = CodeTabOf (i);
561 continue;
562 }
563 if ( (long)HashTabOf (i) > 0 )
564 goto probe;
565 nomatch:
566 output ( (code_int) ent, ctx );
567 ++(ctx->out_count);
568 ent = c;
569 #ifdef SIGNED_COMPARE_SLOW
570 if ( (unsigned) ctx->free_ent < (unsigned) maxmaxcode) {
571 #else /*SIGNED_COMPARE_SLOW*/
572 if ( ctx->free_ent < maxmaxcode ) { /* } */
573 #endif /*SIGNED_COMPARE_SLOW*/
574 CodeTabOf (i) = ctx->free_ent++; /* code -> hashtable */
575 HashTabOf (i) = fcode;
576 } else
577 cl_block(ctx);
578 }
579 /*
580 * Put out the final code.
581 */
582 output( (code_int)ent, ctx );
583 ++(ctx->out_count);
584 output( (code_int) ctx->EOFCode, ctx );
585 }
586
587 /*****************************************************************
588 * TAG( output )
589 *
590 * Output the given code.
591 * Inputs:
592 * code: A n_bits-bit integer. If == -1, then EOF. This assumes
593 * that n_bits =< (long)wordsize - 1.
594 * Outputs:
595 * Outputs code to the file.
596 * Assumptions:
597 * Chars are 8 bits long.
598 * Algorithm:
599 * Maintain a GIFBITS character long buffer (so that 8 codes will
600 * fit in it exactly). Use the VAX insv instruction to insert each
601 * code in turn. When the buffer fills up empty it and start over.
602 */
603
604 static unsigned long masks[] = { 0x0000, 0x0001, 0x0003, 0x0007, 0x000F,
605 0x001F, 0x003F, 0x007F, 0x00FF,
606 0x01FF, 0x03FF, 0x07FF, 0x0FFF,
607 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF };
608
609 static void
610 output(code_int code, GifCtx *ctx)
611 {
612 ctx->cur_accum &= masks[ ctx->cur_bits ];
613
614 if( ctx->cur_bits > 0 )
615 ctx->cur_accum |= ((long)code << ctx->cur_bits);
616 else
617 ctx->cur_accum = code;
618
619 ctx->cur_bits += ctx->n_bits;
620
621 while( ctx->cur_bits >= 8 ) {
622 char_out( (unsigned int)(ctx->cur_accum & 0xff), ctx );
623 ctx->cur_accum >>= 8;
624 ctx->cur_bits -= 8;
625 }
626
627 /*
628 * If the next entry is going to be too big for the code size,
629 * then increase it, if possible.
630 */
631 if ( ctx->free_ent > ctx->maxcode || ctx->clear_flg ) {
632
633 if( ctx->clear_flg ) {
634
635 ctx->maxcode = MAXCODE (ctx->n_bits = ctx->g_init_bits);
636 ctx->clear_flg = 0;
637
638 } else {
639
640 ++(ctx->n_bits);
641 if ( ctx->n_bits == maxbits )
642 ctx->maxcode = maxmaxcode;
643 else
644 ctx->maxcode = MAXCODE(ctx->n_bits);
645 }
646 }
647
648 if( code == ctx->EOFCode ) {
649 /*
650 * At EOF, write the rest of the buffer.
651 */
652 while( ctx->cur_bits > 0 ) {
653 char_out( (unsigned int)(ctx->cur_accum & 0xff), ctx);
654 ctx->cur_accum >>= 8;
655 ctx->cur_bits -= 8;
656 }
657
658 flush_char(ctx);
659
660 }
661 }
662
663 /*
664 * Clear out the hash table
665 */
666 static void
667 cl_block (GifCtx *ctx) /* table clear for block compress */
668 {
669
670 cl_hash ( (count_int) hsize, ctx );
671 ctx->free_ent = ctx->ClearCode + 2;
672 ctx->clear_flg = 1;
673
674 output( (code_int)ctx->ClearCode, ctx);
675 }
676
677 static void
678 cl_hash(register count_int chsize, GifCtx *ctx) /* reset code table */
679
680 {
681
682 register count_int *htab_p = ctx->htab+chsize;
683
684 register long i;
685 register long m1 = -1;
686
687 i = chsize - 16;
688 do { /* might use Sys V memset(3) here */
689 *(htab_p-16) = m1;
690 *(htab_p-15) = m1;
691 *(htab_p-14) = m1;
692 *(htab_p-13) = m1;
693 *(htab_p-12) = m1;
694 *(htab_p-11) = m1;
695 *(htab_p-10) = m1;
696 *(htab_p-9) = m1;
697 *(htab_p-8) = m1;
698 *(htab_p-7) = m1;
699 *(htab_p-6) = m1;
700 *(htab_p-5) = m1;
701 *(htab_p-4) = m1;
702 *(htab_p-3) = m1;
703 *(htab_p-2) = m1;
704 *(htab_p-1) = m1;
705 htab_p -= 16;
706 } while ((i -= 16) >= 0);
707
708 for ( i += 16; i > 0; --i )
709 *--htab_p = m1;
710 }
711
712 /******************************************************************************
713 *
714 * GIF Specific routines
715 *
716 ******************************************************************************/
717
718 /*
719 * Set up the 'byte output' routine
720 */
721 static void
722 char_init(GifCtx *ctx)
723 {
724 ctx->a_count = 0;
725 }
726
727 /*
728 * Add a character to the end of the current packet, and if it is 254
729 * characters, flush the packet to disk.
730 */
731 static void
732 char_out(int c, GifCtx *ctx)
733 {
734 ctx->accum[ ctx->a_count++ ] = c;
735 if( ctx->a_count >= 254 )
736 flush_char(ctx);
737 }
738
739 /*
740 * Flush the packet to disk, and reset the accumulator
741 */
742 static void
743 flush_char(GifCtx *ctx)
744 {
745 if( ctx->a_count > 0 ) {
746 gdPutC( ctx->a_count, ctx->g_outfile );
747 gdPutBuf( ctx->accum, ctx->a_count, ctx->g_outfile );
748 ctx->a_count = 0;
749 }
750 }
751
752 static int gifPutWord(int w, gdIOCtx *out)
753 {
754 /* Byte order is little-endian */
755 gdPutC(w & 0xFF, out);
756 gdPutC((w >> 8) & 0xFF, out);
757 return 0;
758 }
759
760