Annotation of embedaddon/php/ext/gd/libgd/gd_gif_out.c, revision 1.1.1.1
1.1 misho 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:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>