~ubuntu-branches/ubuntu/lucid/graphviz/lucid-security

« back to all changes in this revision

Viewing changes to gd/gd_gif.c

  • Committer: Bazaar Package Importer
  • Author(s): Stephen M Moraco
  • Date: 2002-02-05 18:52:12 UTC
  • Revision ID: james.westby@ubuntu.com-20020205185212-8i04c70te00rc40y
Tags: upstream-1.7.16
ImportĀ upstreamĀ versionĀ 1.7.16

Show diffs side-by-side

added added

removed removed

Lines of Context:
 
1
#include <stdio.h>
 
2
#include <math.h>
 
3
#include <string.h>
 
4
#include <stdlib.h>
 
5
#include "gd.h"
 
6
 
 
7
#define TRUE 1
 
8
#define FALSE 0
 
9
 
 
10
/* Code drawn from ppmtogif.c, from the pbmplus package
 
11
**
 
12
** Based on GIFENCOD by David Rowley <mgardi@watdscu.waterloo.edu>. A
 
13
** Lempel-Zim compression based on "compress".
 
14
**
 
15
** Modified by Marcel Wijkstra <wijkstra@fwi.uva.nl>
 
16
**
 
17
** Copyright (C) 1989 by Jef Poskanzer.
 
18
**
 
19
** Permission to use, copy, modify, and distribute this software and its
 
20
** documentation for any purpose and without fee is hereby granted, provided
 
21
** that the above copyright notice appear in all copies and that both that
 
22
** copyright notice and this permission notice appear in supporting
 
23
** documentation.  This software is provided "as is" without express or
 
24
** implied warranty.
 
25
**
 
26
** The Graphics Interchange Format(c) is the Copyright property of
 
27
** CompuServe Incorporated.  GIF(sm) is a Service Mark property of
 
28
** CompuServe Incorporated.
 
29
*
 
30
*  Heavily modified by Mouse, 1998-02-12.  
 
31
*  Remove LZW compression.
 
32
*  Added miGIF run length compression.
 
33
*
 
34
*/
 
35
 
 
36
/*
 
37
 * a code_int must be able to hold 2**GIFBITS values of type int, and also -1
 
38
 */
 
39
typedef int code_int;
 
40
 
 
41
static int colorstobpp(int colors);
 
42
static void BumpPixel (void);
 
43
static int GIFNextPixel (gdImagePtr im);
 
44
static void GIFEncode (gdIOCtx *ctx, int GWidth, int GHeight, int GInterlace, int Background, int Transparent, int BitsPerPixel, int *Red, int *Green, int *Blue, gdImagePtr im);
 
45
static void compress (int, gdIOCtx *, gdImagePtr, int);
 
46
static void output (code_int code);
 
47
/* Allows for reuse */
 
48
static void init_statics(void);
 
49
 
 
50
void gdImageGif(gdImagePtr im, FILE *outFile)
 
51
{
 
52
        gdIOCtx *out = gdNewFileCtx(outFile);
 
53
        gdImageGifCtx(im, out);
 
54
        out->free(out);
 
55
}
 
56
 
 
57
void* gdImageGifPtr(gdImagePtr im, int *size)
 
58
{
 
59
        void *rv;
 
60
        gdIOCtx *out = gdNewDynamicCtx(2048, NULL);
 
61
        gdImageGifCtx(im, out);
 
62
        rv = gdDPExtractData(out, size);
 
63
        out->free(out);
 
64
        return rv;
 
65
}
 
66
 
 
67
void gdImageGifCtx(gdImagePtr im, gdIOCtx *out)
 
68
{
 
69
        int interlace, transparent, BitsPerPixel;
 
70
        interlace = im->interlace;
 
71
        transparent = im->transparent;
 
72
 
 
73
        BitsPerPixel = colorstobpp(im->colorsTotal);
 
74
        /* Clear any old values in statics strewn through the GIF code */
 
75
        init_statics();
 
76
        /* All set, let's do it. */
 
77
        GIFEncode(
 
78
                out, im->sx, im->sy, interlace, 0, transparent, BitsPerPixel,
 
79
                im->red, im->green, im->blue, im);
 
80
}
 
81
 
 
82
static int
 
83
colorstobpp(int colors)
 
84
{
 
85
    int bpp = 0;
 
86
 
 
87
    if ( colors <= 2 )
 
88
        bpp = 1;
 
89
    else if ( colors <= 4 )
 
90
        bpp = 2;
 
91
    else if ( colors <= 8 )
 
92
        bpp = 3;
 
93
    else if ( colors <= 16 )
 
94
        bpp = 4;
 
95
    else if ( colors <= 32 )
 
96
        bpp = 5;
 
97
    else if ( colors <= 64 )
 
98
        bpp = 6;
 
99
    else if ( colors <= 128 )
 
100
        bpp = 7;
 
101
    else if ( colors <= 256 )
 
102
        bpp = 8;
 
103
    return bpp;
 
104
    }
 
105
 
 
106
/*****************************************************************************
 
107
 *
 
108
 * GIFENCODE.C    - GIF Image compression interface
 
109
 *
 
110
 * GIFEncode( FName, GHeight, GWidth, GInterlace, Background, Transparent,
 
111
 *            BitsPerPixel, Red, Green, Blue, gdImagePtr )
 
112
 *
 
113
 *****************************************************************************/
 
114
 
 
115
#define TRUE 1
 
116
#define FALSE 0
 
117
 
 
118
static int Width, Height;
 
119
static int curx, cury;
 
120
static long CountDown;
 
121
static int Pass = 0;
 
122
static int Interlace;
 
123
 
 
124
/*
 
125
 * Bump the 'curx' and 'cury' to point to the next pixel
 
126
 */
 
127
static void
 
128
BumpPixel(void)
 
129
{
 
130
        /*
 
131
         * Bump the current X position
 
132
         */
 
133
        ++curx;
 
134
 
 
135
        /*
 
136
         * If we are at the end of a scan line, set curx back to the beginning
 
137
         * If we are interlaced, bump the cury to the appropriate spot,
 
138
         * otherwise, just increment it.
 
139
         */
 
140
        if( curx == Width ) {
 
141
                curx = 0;
 
142
 
 
143
                if( !Interlace )
 
144
                        ++cury;
 
145
                else {
 
146
                     switch( Pass ) {
 
147
 
 
148
                       case 0:
 
149
                          cury += 8;
 
150
                          if( cury >= Height ) {
 
151
                                ++Pass;
 
152
                                cury = 4;
 
153
                          }
 
154
                          break;
 
155
 
 
156
                       case 1:
 
157
                          cury += 8;
 
158
                          if( cury >= Height ) {
 
159
                                ++Pass;
 
160
                                cury = 2;
 
161
                          }
 
162
                          break;
 
163
 
 
164
                       case 2:
 
165
                          cury += 4;
 
166
                          if( cury >= Height ) {
 
167
                             ++Pass;
 
168
                             cury = 1;
 
169
                          }
 
170
                          break;
 
171
 
 
172
                       case 3:
 
173
                          cury += 2;
 
174
                          break;
 
175
                        }
 
176
                }
 
177
        }
 
178
}
 
179
 
 
180
/*
 
181
 * Return the next pixel from the image
 
182
 */
 
183
static int
 
184
GIFNextPixel(gdImagePtr im)
 
185
{
 
186
        int r;
 
187
 
 
188
        if( CountDown == 0 )
 
189
                return EOF;
 
190
 
 
191
        --CountDown;
 
192
 
 
193
        r = gdImageGetPixel(im, curx, cury);
 
194
 
 
195
        BumpPixel();
 
196
 
 
197
        return r;
 
198
}
 
199
 
 
200
/* public */
 
201
 
 
202
static void
 
203
GIFEncode(gdIOCtx *ctx, int GWidth, int GHeight, int GInterlace, int Background, int Transparent, int BitsPerPixel, int *Red, int *Green, int *Blue, gdImagePtr im)
 
204
{
 
205
        int B;
 
206
        int RWidth, RHeight;
 
207
        int LeftOfs, TopOfs;
 
208
        int Resolution;
 
209
        int ColorMapSize;
 
210
        int InitCodeSize;
 
211
        int i;
 
212
 
 
213
        Interlace = GInterlace;
 
214
 
 
215
        ColorMapSize = 1 << BitsPerPixel;
 
216
 
 
217
        RWidth = Width = GWidth;
 
218
        RHeight = Height = GHeight;
 
219
        LeftOfs = TopOfs = 0;
 
220
 
 
221
        Resolution = BitsPerPixel;
 
222
 
 
223
        /*
 
224
         * Calculate number of bits we are expecting
 
225
         */
 
226
        CountDown = (long)Width * (long)Height;
 
227
 
 
228
        /*
 
229
         * Indicate which pass we are on (if interlace)
 
230
         */
 
231
        Pass = 0;
 
232
 
 
233
        /*
 
234
         * The initial code size
 
235
         */
 
236
        if( BitsPerPixel <= 1 )
 
237
                InitCodeSize = 2;
 
238
        else
 
239
                InitCodeSize = BitsPerPixel;
 
240
 
 
241
        /*
 
242
         * Set up the current x and y position
 
243
         */
 
244
        curx = cury = 0;
 
245
 
 
246
        /*
 
247
         * Write the Magic header
 
248
         */
 
249
        gdPutBuf( Transparent < 0 ? "GIF87a" : "GIF89a", 6, ctx );
 
250
 
 
251
        /*
 
252
         * Write out the screen width and height
 
253
         */
 
254
        Putword( RWidth, ctx );
 
255
        Putword( RHeight, ctx );
 
256
 
 
257
        /*
 
258
         * Indicate that there is a global colour map
 
259
         */
 
260
        B = 0x80;       /* Yes, there is a color map */
 
261
 
 
262
        /*
 
263
         * OR in the resolution
 
264
         */
 
265
        B |= (Resolution - 1) << 4;
 
266
 
 
267
        /*
 
268
         * OR in the Bits per Pixel
 
269
         */
 
270
        B |= (BitsPerPixel - 1);
 
271
 
 
272
        /*
 
273
         * Write it out
 
274
         */
 
275
        Putchar( B, ctx );
 
276
 
 
277
        /*
 
278
         * Write out the Background colour
 
279
         */
 
280
        Putchar( Background, ctx );
 
281
 
 
282
        /*
 
283
         * Byte of 0's (future expansion)
 
284
         */
 
285
        Putchar( 0, ctx );
 
286
 
 
287
        /*
 
288
         * Write out the Global Colour Map
 
289
         */
 
290
        for( i=0; i<ColorMapSize; ++i ) {
 
291
                Putchar( Red[i], ctx );
 
292
                Putchar( Green[i], ctx );
 
293
                Putchar( Blue[i], ctx );
 
294
        }
 
295
 
 
296
        /*
 
297
         * Write out extension for transparent colour index, if necessary.
 
298
         */
 
299
        if ( Transparent >= 0 ) {
 
300
            Putchar( '!', ctx );
 
301
            Putchar( 0xf9, ctx );
 
302
            Putchar( 4, ctx );
 
303
            Putchar( 1, ctx );
 
304
            Putchar( 0, ctx );
 
305
            Putchar( 0, ctx );
 
306
            Putchar( (unsigned char) Transparent, ctx );
 
307
            Putchar( 0, ctx );
 
308
        }
 
309
 
 
310
        /*
 
311
         * Write an Image separator
 
312
         */
 
313
        Putchar( ',', ctx );
 
314
 
 
315
        /*
 
316
         * Write the Image header
 
317
         */
 
318
 
 
319
        Putword( LeftOfs, ctx );
 
320
        Putword( TopOfs, ctx );
 
321
        Putword( Width, ctx );
 
322
        Putword( Height, ctx );
 
323
 
 
324
        /*
 
325
         * Write out whether or not the image is interlaced
 
326
         */
 
327
        if( Interlace )
 
328
                Putchar( 0x40, ctx );
 
329
        else
 
330
                Putchar( 0x00, ctx );
 
331
 
 
332
        /*
 
333
         * Write out the initial code size
 
334
         */
 
335
        Putchar( InitCodeSize, ctx );
 
336
 
 
337
        /*
 
338
         * Go and actually compress the data
 
339
         */
 
340
        compress( InitCodeSize+1, ctx, im, Background );
 
341
 
 
342
        /*
 
343
         * Write out a Zero-length packet (to end the series)
 
344
         */
 
345
        Putchar( 0, ctx );
 
346
 
 
347
        /*
 
348
         * Write the GIF file terminator
 
349
         */
 
350
        Putchar( ';', ctx );
 
351
}
 
352
 
 
353
#define GIFBITS 12
 
354
 
 
355
/*-----------------------------------------------------------------------
 
356
 *
 
357
 * miGIF Compression - mouse and ivo's GIF-compatible compression
 
358
 *
 
359
 *          -run length encoding compression routines-
 
360
 *
 
361
 * Copyright (C) 1998 Hutchison Avenue Software Corporation
 
362
 *               http://www.hasc.com
 
363
 *               info@hasc.com
 
364
 *
 
365
 * Permission to use, copy, modify, and distribute this software and its
 
366
 * documentation for any purpose and without fee is hereby granted, provided
 
367
 * that the above copyright notice appear in all copies and that both that
 
368
 * copyright notice and this permission notice appear in supporting
 
369
 * documentation.  This software is provided "AS IS." The Hutchison Avenue 
 
370
 * Software Corporation disclaims all warranties, either express or implied, 
 
371
 * including but not limited to implied warranties of merchantability and 
 
372
 * fitness for a particular purpose, with respect to this code and accompanying
 
373
 * documentation. 
 
374
 * 
 
375
 * The miGIF compression routines do not, strictly speaking, generate files 
 
376
 * conforming to the GIF spec, since the image data is not LZW-compressed 
 
377
 * (this is the point: in order to avoid transgression of the Unisys patent 
 
378
 * on the LZW algorithm.)  However, miGIF generates data streams that any 
 
379
 * reasonably sane LZW decompresser will decompress to what we want.
 
380
 *
 
381
 * miGIF compression uses run length encoding. It compresses horizontal runs 
 
382
 * of pixels of the same color. This type of compression gives good results
 
383
 * on images with many runs, for example images with lines, text and solid 
 
384
 * shapes on a solid-colored background. It gives little or no compression 
 
385
 * on images with few runs, for example digital or scanned photos.
 
386
 *
 
387
 *                               der Mouse
 
388
 *                      mouse@rodents.montreal.qc.ca
 
389
 *            7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B
 
390
 *
 
391
 *                             ivo@hasc.com
 
392
 *
 
393
 * The Graphics Interchange Format(c) is the Copyright property of
 
394
 * CompuServe Incorporated.  GIF(sm) is a Service Mark property of
 
395
 * CompuServe Incorporated.
 
396
 *
 
397
 */
 
398
 
 
399
static int rl_pixel;
 
400
static int rl_basecode;
 
401
static int rl_count;
 
402
static int rl_table_pixel;
 
403
static int rl_table_max;
 
404
static int just_cleared;
 
405
static int out_bits;
 
406
static int out_bits_init;
 
407
static int out_count;
 
408
static int out_bump;
 
409
static int out_bump_init;
 
410
static int out_clear;
 
411
static int out_clear_init;
 
412
static int max_ocodes;
 
413
static int code_clear;
 
414
static int code_eof;
 
415
static unsigned int obuf;
 
416
static int obits;
 
417
static gdIOCtx *octx;
 
418
static unsigned char oblock[256];
 
419
static int oblen;
 
420
 
 
421
/* Used only when debugging GIF compression code */
 
422
/* #define DEBUGGING_ENVARS */
 
423
 
 
424
#ifdef DEBUGGING_ENVARS
 
425
 
 
426
static int verbose_set = 0;
 
427
static int verbose;
 
428
#define VERBOSE (verbose_set?verbose:set_verbose())
 
429
 
 
430
static int set_verbose(void)
 
431
{
 
432
 verbose = !!getenv("GIF_VERBOSE");
 
433
 verbose_set = 1;
 
434
 return(verbose);
 
435
}
 
436
 
 
437
#else
 
438
 
 
439
#define VERBOSE 0
 
440
 
 
441
#endif
 
442
 
 
443
 
 
444
static const char *binformat(unsigned int v, int nbits)
 
445
{
 
446
 static char bufs[8][64];
 
447
 static int bhand = 0;
 
448
 unsigned int bit;
 
449
 int bno;
 
450
 char *bp;
 
451
 
 
452
 bhand --;
 
453
 if (bhand < 0) bhand = (sizeof(bufs)/sizeof(bufs[0]))-1;
 
454
 bp = &bufs[bhand][0];
 
455
 for (bno=nbits-1,bit=1U<<bno;bno>=0;bno--,bit>>=1)
 
456
  { *bp++ = (v & bit) ? '1' : '0';
 
457
    if (((bno&3) == 0) && (bno != 0)) *bp++ = '.';
 
458
  }
 
459
 *bp = '\0';
 
460
 return(&bufs[bhand][0]);
 
461
}
 
462
 
 
463
static void write_block(void)
 
464
{
 
465
 int i;
 
466
 
 
467
 if (VERBOSE)
 
468
  { printf("write_block %d:",oblen);
 
469
    for (i=0;i<oblen;i++) printf(" %02x",oblock[i]);
 
470
    printf("\n");
 
471
  }
 
472
 Putchar(oblen,octx);
 
473
 gdPutBuf(&oblock[0],oblen,octx);
 
474
 oblen = 0;
 
475
}
 
476
 
 
477
static void block_out(unsigned char c)
 
478
{
 
479
 if (VERBOSE) printf("block_out %s\n",binformat(c,8));
 
480
 oblock[oblen++] = c;
 
481
 if (oblen >= 255) write_block();
 
482
}
 
483
 
 
484
static void block_flush(void)
 
485
{
 
486
 if (VERBOSE) printf("block_flush\n");
 
487
 if (oblen > 0) write_block();
 
488
}
 
489
 
 
490
static void output(int val)
 
491
{
 
492
 if (VERBOSE) printf("output %s [%s %d %d]\n",binformat(val,out_bits),binformat(obuf,obits),obits,out_bits);
 
493
 obuf |= val << obits;
 
494
 obits += out_bits;
 
495
 while (obits >= 8)
 
496
  { block_out(obuf&0xff);
 
497
    obuf >>= 8;
 
498
    obits -= 8;
 
499
  }
 
500
 if (VERBOSE) printf("output leaving [%s %d]\n",binformat(obuf,obits),obits);
 
501
}
 
502
 
 
503
static void output_flush(void)
 
504
{
 
505
 if (VERBOSE) printf("output_flush\n");
 
506
 if (obits > 0) block_out(obuf);
 
507
 block_flush();
 
508
}
 
509
 
 
510
static void did_clear(void)
 
511
{
 
512
 if (VERBOSE) printf("did_clear\n");
 
513
 out_bits = out_bits_init;
 
514
 out_bump = out_bump_init;
 
515
 out_clear = out_clear_init;
 
516
 out_count = 0;
 
517
 rl_table_max = 0;
 
518
 just_cleared = 1;
 
519
}
 
520
 
 
521
static void output_plain(int c)
 
522
{
 
523
 if (VERBOSE) printf("output_plain %s\n",binformat(c,out_bits));
 
524
 just_cleared = 0;
 
525
 output(c);
 
526
 out_count ++;
 
527
 if (out_count >= out_bump)
 
528
  { out_bits ++;
 
529
    out_bump += 1 << (out_bits - 1);
 
530
  }
 
531
 if (out_count >= out_clear)
 
532
  { output(code_clear);
 
533
    did_clear();
 
534
  }
 
535
}
 
536
 
 
537
static unsigned int isqrt(unsigned int x)
 
538
{
 
539
 unsigned int r;
 
540
 unsigned int v;
 
541
 
 
542
 if (x < 2) return(x);
 
543
 for (v=x,r=1;v;v>>=2,r<<=1) ;
 
544
 while (1)
 
545
  { v = ((x / r) + r) / 2;
 
546
    if ((v == r) || (v == r+1)) return(r);
 
547
    r = v;
 
548
  }
 
549
}
 
550
 
 
551
static unsigned int compute_triangle_count(unsigned int count, unsigned int nrepcodes)
 
552
{
 
553
 unsigned int perrep;
 
554
 unsigned int cost;
 
555
 
 
556
 cost = 0;
 
557
 perrep = (nrepcodes * (nrepcodes+1)) / 2;
 
558
 while (count >= perrep)
 
559
  { cost += nrepcodes;
 
560
    count -= perrep;
 
561
  }
 
562
 if (count > 0)
 
563
  { unsigned int n;
 
564
    n = isqrt(count);
 
565
    while ((n*(n+1)) >= 2*count) n --;
 
566
    while ((n*(n+1)) < 2*count) n ++;
 
567
    cost += n;
 
568
  }
 
569
 return(cost);
 
570
}
 
571
 
 
572
static void max_out_clear(void)
 
573
{
 
574
 out_clear = max_ocodes;
 
575
}
 
576
 
 
577
static void reset_out_clear(void)
 
578
{
 
579
 out_clear = out_clear_init;
 
580
 if (out_count >= out_clear)
 
581
  { output(code_clear);
 
582
    did_clear();
 
583
  }
 
584
}
 
585
 
 
586
static void rl_flush_fromclear(int count)
 
587
{
 
588
 int n;
 
589
 
 
590
 if (VERBOSE) printf("rl_flush_fromclear %d\n",count);
 
591
 max_out_clear();
 
592
 rl_table_pixel = rl_pixel;
 
593
 n = 1;
 
594
 while (count > 0)
 
595
  { if (n == 1)
 
596
     { rl_table_max = 1;
 
597
       output_plain(rl_pixel);
 
598
       count --;
 
599
     }
 
600
    else if (count >= n)
 
601
     { rl_table_max = n;
 
602
       output_plain(rl_basecode+n-2);
 
603
       count -= n;
 
604
     }
 
605
    else if (count == 1)
 
606
     { rl_table_max ++;
 
607
       output_plain(rl_pixel);
 
608
       count = 0;
 
609
     }
 
610
    else
 
611
     { rl_table_max ++;
 
612
       output_plain(rl_basecode+count-2);
 
613
       count = 0;
 
614
     }
 
615
    if (out_count == 0) n = 1; else n ++;
 
616
  }
 
617
 reset_out_clear();
 
618
 if (VERBOSE) printf("rl_flush_fromclear leaving table_max=%d\n",rl_table_max);
 
619
}
 
620
 
 
621
static void rl_flush_clearorrep(int count)
 
622
{
 
623
 int withclr;
 
624
 
 
625
 if (VERBOSE) printf("rl_flush_clearorrep %d\n",count);
 
626
 withclr = 1 + compute_triangle_count(count,max_ocodes);
 
627
 if (withclr < count)
 
628
  { output(code_clear);
 
629
    did_clear();
 
630
    rl_flush_fromclear(count);
 
631
  }
 
632
 else
 
633
  { for (;count>0;count--) output_plain(rl_pixel);
 
634
  }
 
635
}
 
636
 
 
637
static void rl_flush_withtable(int count)
 
638
{
 
639
 int repmax;
 
640
 int repleft;
 
641
 int leftover;
 
642
 
 
643
 if (VERBOSE) printf("rl_flush_withtable %d\n",count);
 
644
 repmax = count / rl_table_max;
 
645
 leftover = count % rl_table_max;
 
646
 repleft = (leftover ? 1 : 0);
 
647
 if (out_count+repmax+repleft > max_ocodes)
 
648
  { repmax = max_ocodes - out_count;
 
649
    leftover = count - (repmax * rl_table_max);
 
650
    repleft = 1 + compute_triangle_count(leftover,max_ocodes);
 
651
  }
 
652
 if (VERBOSE) printf("rl_flush_withtable repmax=%d leftover=%d repleft=%d\n",repmax,leftover,repleft);
 
653
 if (1+compute_triangle_count(count,max_ocodes) < repmax+repleft)
 
654
  { output(code_clear);
 
655
    did_clear();
 
656
    rl_flush_fromclear(count);
 
657
    return;
 
658
  }
 
659
 max_out_clear();
 
660
 for (;repmax>0;repmax--) output_plain(rl_basecode+rl_table_max-2);
 
661
 if (leftover)
 
662
  { if (just_cleared)
 
663
     { rl_flush_fromclear(leftover);
 
664
     }
 
665
    else if (leftover == 1)
 
666
     { output_plain(rl_pixel);
 
667
     }
 
668
    else
 
669
     { output_plain(rl_basecode+leftover-2);
 
670
     }
 
671
  }
 
672
 reset_out_clear();
 
673
}
 
674
 
 
675
static void rl_flush(void)
 
676
{
 
677
 if (VERBOSE) printf("rl_flush [ %d %d\n",rl_count,rl_pixel);
 
678
 if (rl_count == 1)
 
679
  { output_plain(rl_pixel);
 
680
    rl_count = 0;
 
681
    if (VERBOSE) printf("rl_flush ]\n");
 
682
    return;
 
683
  }
 
684
 if (just_cleared)
 
685
  { rl_flush_fromclear(rl_count);
 
686
  }
 
687
 else if ((rl_table_max < 2) || (rl_table_pixel != rl_pixel))
 
688
  { rl_flush_clearorrep(rl_count);
 
689
  }
 
690
 else
 
691
  { rl_flush_withtable(rl_count);
 
692
  }
 
693
 if (VERBOSE) printf("rl_flush ]\n");
 
694
 rl_count = 0;
 
695
}
 
696
 
 
697
static void compress(int init_bits, gdIOCtx *ctx, gdImagePtr im, int background)
 
698
{
 
699
 int c;
 
700
 
 
701
 octx = ctx;
 
702
 obuf = 0;
 
703
 obits = 0;
 
704
 oblen = 0;
 
705
 code_clear = 1 << (init_bits - 1);
 
706
 code_eof = code_clear + 1;
 
707
 rl_basecode = code_eof + 1;
 
708
 out_bump_init = (1 << (init_bits - 1)) - 1;
 
709
 /* for images with a lot of runs, making out_clear_init larger will
 
710
    give better compression. */ 
 
711
 out_clear_init = (init_bits <= 3) ? 9 : (out_bump_init-1);
 
712
#ifdef DEBUGGING_ENVARS
 
713
  { const char *ocienv;
 
714
    ocienv = getenv("GIF_OUT_CLEAR_INIT");
 
715
    if (ocienv)
 
716
     { out_clear_init = atoi(ocienv);
 
717
       if (VERBOSE) printf("[overriding out_clear_init to %d]\n",out_clear_init);
 
718
     }
 
719
  }
 
720
#endif
 
721
 out_bits_init = init_bits;
 
722
 max_ocodes = (1 << GIFBITS) - ((1 << (out_bits_init - 1)) + 3);
 
723
 did_clear();
 
724
 output(code_clear);
 
725
 rl_count = 0;
 
726
 while (1)
 
727
  { c = GIFNextPixel(im);
 
728
    if ((rl_count > 0) && (c != rl_pixel)) rl_flush();
 
729
    if (c == EOF) break;
 
730
    if (rl_pixel == c)
 
731
     { rl_count ++;
 
732
     }
 
733
    else
 
734
     { rl_pixel = c;
 
735
       rl_count = 1;
 
736
     }
 
737
  }
 
738
 output(code_eof);
 
739
 output_flush();
 
740
}
 
741
 
 
742
/*-----------------------------------------------------------------------
 
743
 *
 
744
 * End of miGIF section  - See copyright notice at start of section.
 
745
 *
 
746
 *-----------------------------------------------------------------------*/
 
747
 
 
748
 
 
749
/******************************************************************************
 
750
 *
 
751
 * GIF Specific routines
 
752
 *
 
753
 ******************************************************************************/
 
754
 
 
755
static void init_statics(void) {
 
756
        /* Some of these are properly initialized later. What I'm doing
 
757
                here is making sure code that depends on C's initialization
 
758
                of statics doesn't break when the code gets called more
 
759
                than once. */
 
760
        Width = 0;
 
761
        Height = 0;
 
762
        curx = 0;
 
763
        cury = 0;
 
764
        CountDown = 0;
 
765
        Pass = 0;
 
766
        Interlace = 0;
 
767
}
 
768
 
 
769
 
 
770
/* +-------------------------------------------------------------------+ */
 
771
/* | Copyright 1990, 1991, 1993, David Koblas.  (koblas@netcom.com)    | */
 
772
/* |   Permission to use, copy, modify, and distribute this software   | */
 
773
/* |   and its documentation for any purpose and without fee is hereby | */
 
774
/* |   granted, provided that the above copyright notice appear in all | */
 
775
/* |   copies and that both that copyright notice and this permission  | */
 
776
/* |   notice appear in supporting documentation.  This software is    | */
 
777
/* |   provided "as is" without express or implied warranty.           | */
 
778
/* +-------------------------------------------------------------------+ */
 
779
 
 
780
 
 
781
#define        MAXCOLORMAPSIZE         256
 
782
 
 
783
#define        TRUE    1
 
784
#define        FALSE   0
 
785
 
 
786
#define CM_RED         0
 
787
#define CM_GREEN       1
 
788
#define CM_BLUE                2
 
789
 
 
790
#define        MAX_LWZ_BITS            12
 
791
 
 
792
#define INTERLACE              0x40
 
793
#define LOCALCOLORMAP  0x80
 
794
#define BitSet(byte, bit)      (((byte) & (bit)) == (bit))
 
795
 
 
796
#define        ReadOK(file,buffer,len) (fread(buffer, len, 1, file) != 0)
 
797
 
 
798
#define LM_to_uint(a,b)                        (((b)<<8)|(a))
 
799
 
 
800
/* We may eventually want to use this information, but def it out for now */
 
801
#if 0
 
802
static struct {
 
803
       unsigned int    Width;
 
804
       unsigned int    Height;
 
805
       unsigned char   ColorMap[3][MAXCOLORMAPSIZE];
 
806
       unsigned int    BitPixel;
 
807
       unsigned int    ColorResolution;
 
808
       unsigned int    Background;
 
809
       unsigned int    AspectRatio;
 
810
} GifScreen;
 
811
#endif
 
812
 
 
813
#if 0
 
814
/* never used */
 
815
static struct {
 
816
       int     transparent;
 
817
       int     delayTime;
 
818
       int     inputFlag;
 
819
       int     disposal;
 
820
} Gif89 = { -1, -1, -1, 0 };
 
821
#endif
 
822
 
 
823
static int ReadColorMap (FILE *fd, int number, unsigned char (*buffer)[256]);
 
824
static int DoExtension (FILE *fd, int label, int *Transparent);
 
825
static int GetDataBlock (FILE *fd, unsigned char *buf);
 
826
static int GetCode (FILE *fd, int code_size, int flag);
 
827
static int LWZReadByte (FILE *fd, int flag, int input_code_size);
 
828
static void ReadImage (gdImagePtr im, FILE *fd, int len, int height, unsigned char (*cmap)[256], int interlace, int ignore);
 
829
 
 
830
int ZeroDataBlock;
 
831
 
 
832
gdImagePtr
 
833
gdImageCreateFromGif(FILE *fd)
 
834
{
 
835
       int imageNumber;
 
836
       int BitPixel;
 
837
#if 0
 
838
/* never used */
 
839
       int ColorResolution;
 
840
       int Background;
 
841
       int AspectRatio;
 
842
#endif
 
843
       int Transparent = (-1);
 
844
       unsigned char   buf[16];
 
845
       unsigned char   c;
 
846
       unsigned char   ColorMap[3][MAXCOLORMAPSIZE];
 
847
       unsigned char   localColorMap[3][MAXCOLORMAPSIZE];
 
848
       int             imw, imh;
 
849
       int             useGlobalColormap;
 
850
       int             bitPixel;
 
851
       int             imageCount = 0;
 
852
       char            version[4];
 
853
       gdImagePtr im = 0;
 
854
       ZeroDataBlock = FALSE;
 
855
 
 
856
       imageNumber = 1;
 
857
       if (! ReadOK(fd,buf,6)) {
 
858
                return 0;
 
859
        }
 
860
       if (strncmp((char *)buf,"GIF",3) != 0) {
 
861
                return 0;
 
862
        }
 
863
       strncpy(version, (char *)buf + 3, 3);
 
864
       version[3] = '\0';
 
865
 
 
866
       if ((strcmp(version, "87a") != 0) && (strcmp(version, "89a") != 0)) {
 
867
                return 0;
 
868
        }
 
869
       if (! ReadOK(fd,buf,7)) {
 
870
                return 0;
 
871
        }
 
872
       BitPixel        = 2<<(buf[4]&0x07);
 
873
#if 0
 
874
/* never used */
 
875
       ColorResolution = (int) (((buf[4]&0x70)>>3)+1);
 
876
       Background      = buf[5];
 
877
       AspectRatio     = buf[6];
 
878
#endif
 
879
 
 
880
       if (BitSet(buf[4], LOCALCOLORMAP)) {    /* Global Colormap */
 
881
               if (ReadColorMap(fd, BitPixel, ColorMap)) {
 
882
                        return 0;
 
883
                }
 
884
       }
 
885
       for (;;) {
 
886
               if (! ReadOK(fd,&c,1)) {
 
887
                       return 0;
 
888
               }
 
889
               if (c == ';') {         /* GIF terminator */
 
890
                       int i;
 
891
                       if (imageCount < imageNumber) {
 
892
                               return 0;
 
893
                       }
 
894
                       /* Terminator before any image was declared! */
 
895
                       if (!im) {
 
896
                              return 0;
 
897
                       }
 
898
                       /* Check for open colors at the end, so
 
899
                          we can reduce colorsTotal and ultimately
 
900
                          BitsPerPixel */
 
901
                       for (i=((im->colorsTotal-1)); (i>=0); i--) {
 
902
                               if (im->open[i]) {
 
903
                                       im->colorsTotal--;
 
904
                               } else {
 
905
                                       break;
 
906
                               }
 
907
                       } 
 
908
                       return im;
 
909
               }
 
910
 
 
911
               if (c == '!') {         /* Extension */
 
912
                       if (! ReadOK(fd,&c,1)) {
 
913
                               return 0;
 
914
                       }
 
915
                       DoExtension(fd, c, &Transparent);
 
916
                       continue;
 
917
               }
 
918
 
 
919
               if (c != ',') {         /* Not a valid start character */
 
920
                       continue;
 
921
               }
 
922
 
 
923
               ++imageCount;
 
924
 
 
925
               if (! ReadOK(fd,buf,9)) {
 
926
                       return 0;
 
927
               }
 
928
 
 
929
               useGlobalColormap = ! BitSet(buf[8], LOCALCOLORMAP);
 
930
 
 
931
               bitPixel = 1<<((buf[8]&0x07)+1);
 
932
 
 
933
               imw = LM_to_uint(buf[4],buf[5]);
 
934
               imh = LM_to_uint(buf[6],buf[7]);
 
935
               if (!(im = gdImageCreate(imw, imh))) {
 
936
                         return 0;
 
937
               }
 
938
               im->interlace = BitSet(buf[8], INTERLACE);
 
939
               if (! useGlobalColormap) {
 
940
                       if (ReadColorMap(fd, bitPixel, localColorMap)) { 
 
941
                                 return 0;
 
942
                       }
 
943
                       ReadImage(im, fd, imw, imh, localColorMap, 
 
944
                                 BitSet(buf[8], INTERLACE), 
 
945
                                 imageCount != imageNumber);
 
946
               } else {
 
947
                       ReadImage(im, fd, imw, imh,
 
948
                                 ColorMap, 
 
949
                                 BitSet(buf[8], INTERLACE), 
 
950
                                 imageCount != imageNumber);
 
951
               }
 
952
               if (Transparent != (-1)) {
 
953
                       gdImageColorTransparent(im, Transparent);
 
954
               }           
 
955
       }
 
956
}
 
957
 
 
958
static int
 
959
ReadColorMap(FILE *fd, int number, unsigned char (*buffer)[256])
 
960
{
 
961
       int             i;
 
962
       unsigned char   rgb[3];
 
963
 
 
964
 
 
965
       for (i = 0; i < number; ++i) {
 
966
               if (! ReadOK(fd, rgb, sizeof(rgb))) {
 
967
                       return TRUE;
 
968
               }
 
969
               buffer[CM_RED][i] = rgb[0] ;
 
970
               buffer[CM_GREEN][i] = rgb[1] ;
 
971
               buffer[CM_BLUE][i] = rgb[2] ;
 
972
       }
 
973
 
 
974
 
 
975
       return FALSE;
 
976
}
 
977
 
 
978
static int
 
979
DoExtension(FILE *fd, int label, int *Transparent)
 
980
{
 
981
       static unsigned char     buf[256];
 
982
 
 
983
       switch (label) {
 
984
       case 0xf9:              /* Graphic Control Extension */
 
985
               (void) GetDataBlock(fd, (unsigned char*) buf);
 
986
#if 0
 
987
/* never used */
 
988
               Gif89.disposal    = (buf[0] >> 2) & 0x7;
 
989
               Gif89.inputFlag   = (buf[0] >> 1) & 0x1;
 
990
               Gif89.delayTime   = LM_to_uint(buf[1],buf[2]);
 
991
#endif
 
992
               if ((buf[0] & 0x1) != 0)
 
993
                       *Transparent = buf[3];
 
994
 
 
995
               while (GetDataBlock(fd, (unsigned char*) buf) != 0)
 
996
                       ;
 
997
               return FALSE;
 
998
       default:
 
999
               break;
 
1000
       }
 
1001
       while (GetDataBlock(fd, (unsigned char*) buf) != 0)
 
1002
               ;
 
1003
 
 
1004
       return FALSE;
 
1005
}
 
1006
 
 
1007
static int
 
1008
GetDataBlock_(FILE *fd, unsigned char *buf)
 
1009
{
 
1010
       unsigned char   count;
 
1011
 
 
1012
       if (! ReadOK(fd,&count,1)) {
 
1013
               return -1;
 
1014
       }
 
1015
 
 
1016
       ZeroDataBlock = count == 0;
 
1017
 
 
1018
       if ((count != 0) && (! ReadOK(fd, buf, count))) {
 
1019
               return -1;
 
1020
       }
 
1021
 
 
1022
       return count;
 
1023
}
 
1024
 
 
1025
static int
 
1026
GetDataBlock(FILE *fd, unsigned char *buf)
 
1027
{
 
1028
 int rv;
 
1029
 int i;
 
1030
 
 
1031
 rv = GetDataBlock_(fd,buf);
 
1032
 if (VERBOSE)
 
1033
  { printf("[GetDataBlock returning %d",rv);
 
1034
    if (rv > 0)
 
1035
     { printf(":");
 
1036
       for (i=0;i<rv;i++) printf(" %02x",buf[i]);
 
1037
     }
 
1038
    printf("]\n");
 
1039
  }
 
1040
 return(rv);
 
1041
}
 
1042
 
 
1043
static int
 
1044
GetCode_(FILE *fd, int code_size, int flag)
 
1045
{
 
1046
       static unsigned char    buf[280];
 
1047
       static int              curbit, lastbit, done, last_byte;
 
1048
       int                     i, j, ret;
 
1049
       unsigned char           count;
 
1050
 
 
1051
       if (flag) {
 
1052
               curbit = 0;
 
1053
               lastbit = 0;
 
1054
               done = FALSE;
 
1055
               return 0;
 
1056
       }
 
1057
 
 
1058
       if ( (curbit+code_size) >= lastbit) {
 
1059
               if (done) {
 
1060
                       if (curbit >= lastbit) {
 
1061
                                /* Oh well */
 
1062
                       }                        
 
1063
                       return -1;
 
1064
               }
 
1065
               buf[0] = buf[last_byte-2];
 
1066
               buf[1] = buf[last_byte-1];
 
1067
 
 
1068
               if ((count = GetDataBlock(fd, &buf[2])) == 0)
 
1069
                       done = TRUE;
 
1070
 
 
1071
               last_byte = 2 + count;
 
1072
               curbit = (curbit - lastbit) + 16;
 
1073
               lastbit = (2+count)*8 ;
 
1074
       }
 
1075
 
 
1076
       ret = 0;
 
1077
       for (i = curbit, j = 0; j < code_size; ++i, ++j)
 
1078
               ret |= ((buf[ i / 8 ] & (1 << (i % 8))) != 0) << j;
 
1079
 
 
1080
       curbit += code_size;
 
1081
       return ret;
 
1082
}
 
1083
 
 
1084
static int
 
1085
GetCode(FILE *fd, int code_size, int flag)
 
1086
{
 
1087
 int rv;
 
1088
 
 
1089
 rv = GetCode_(fd,code_size,flag);
 
1090
 if (VERBOSE) printf("[GetCode(,%d,%d) returning %d]\n",code_size,flag,rv);
 
1091
 return(rv);
 
1092
}
 
1093
 
 
1094
static int
 
1095
LWZReadByte_(FILE *fd, int flag, int input_code_size)
 
1096
{
 
1097
       static int      fresh = FALSE;
 
1098
       int             code, incode;
 
1099
       static int      code_size, set_code_size;
 
1100
       static int      max_code, max_code_size;
 
1101
       static int      firstcode, oldcode;
 
1102
       static int      clear_code, end_code;
 
1103
       static int      table[2][(1<< MAX_LWZ_BITS)];
 
1104
       static int      stack[(1<<(MAX_LWZ_BITS))*2], *sp;
 
1105
       register int    i;
 
1106
 
 
1107
       if (flag) {
 
1108
               set_code_size = input_code_size;
 
1109
               code_size = set_code_size+1;
 
1110
               clear_code = 1 << set_code_size ;
 
1111
               end_code = clear_code + 1;
 
1112
               max_code_size = 2*clear_code;
 
1113
               max_code = clear_code+2;
 
1114
 
 
1115
               GetCode(fd, 0, TRUE);
 
1116
               
 
1117
               fresh = TRUE;
 
1118
 
 
1119
               for (i = 0; i < clear_code; ++i) {
 
1120
                       table[0][i] = 0;
 
1121
                       table[1][i] = i;
 
1122
               }
 
1123
               for (; i < (1<<MAX_LWZ_BITS); ++i)
 
1124
                       table[0][i] = table[1][0] = 0;
 
1125
 
 
1126
               sp = stack;
 
1127
 
 
1128
               return 0;
 
1129
       } else if (fresh) {
 
1130
               fresh = FALSE;
 
1131
               do {
 
1132
                       firstcode = oldcode =
 
1133
                               GetCode(fd, code_size, FALSE);
 
1134
               } while (firstcode == clear_code);
 
1135
               return firstcode;
 
1136
       }
 
1137
 
 
1138
       if (sp > stack)
 
1139
               return *--sp;
 
1140
 
 
1141
       while ((code = GetCode(fd, code_size, FALSE)) >= 0) {
 
1142
               if (code == clear_code) {
 
1143
                       for (i = 0; i < clear_code; ++i) {
 
1144
                               table[0][i] = 0;
 
1145
                               table[1][i] = i;
 
1146
                       }
 
1147
                       for (; i < (1<<MAX_LWZ_BITS); ++i)
 
1148
                               table[0][i] = table[1][i] = 0;
 
1149
                       code_size = set_code_size+1;
 
1150
                       max_code_size = 2*clear_code;
 
1151
                       max_code = clear_code+2;
 
1152
                       sp = stack;
 
1153
                       firstcode = oldcode =
 
1154
                                       GetCode(fd, code_size, FALSE);
 
1155
                       return firstcode;
 
1156
               } else if (code == end_code) {
 
1157
                       int             count;
 
1158
                       unsigned char   buf[260];
 
1159
 
 
1160
                       if (ZeroDataBlock)
 
1161
                               return -2;
 
1162
 
 
1163
                       while ((count = GetDataBlock(fd, buf)) > 0)
 
1164
                               ;
 
1165
 
 
1166
                       if (count != 0)
 
1167
                       return -2;
 
1168
               }
 
1169
 
 
1170
               incode = code;
 
1171
 
 
1172
               if (code >= max_code) {
 
1173
                       *sp++ = firstcode;
 
1174
                       code = oldcode;
 
1175
               }
 
1176
 
 
1177
               while (code >= clear_code) {
 
1178
                       *sp++ = table[1][code];
 
1179
                       if (code == table[0][code]) {
 
1180
                               /* Oh well */
 
1181
                       }
 
1182
                       code = table[0][code];
 
1183
               }
 
1184
 
 
1185
               *sp++ = firstcode = table[1][code];
 
1186
 
 
1187
               if ((code = max_code) <(1<<MAX_LWZ_BITS)) {
 
1188
                       table[0][code] = oldcode;
 
1189
                       table[1][code] = firstcode;
 
1190
                       ++max_code;
 
1191
                       if ((max_code >= max_code_size) &&
 
1192
                               (max_code_size < (1<<MAX_LWZ_BITS))) {
 
1193
                               max_code_size *= 2;
 
1194
                               ++code_size;
 
1195
                       }
 
1196
               }
 
1197
 
 
1198
               oldcode = incode;
 
1199
 
 
1200
               if (sp > stack)
 
1201
                       return *--sp;
 
1202
       }
 
1203
       return code;
 
1204
}
 
1205
 
 
1206
static int
 
1207
LWZReadByte(FILE *fd, int flag, int input_code_size)
 
1208
{
 
1209
 int rv;
 
1210
 
 
1211
 rv = LWZReadByte_(fd,flag,input_code_size);
 
1212
 if (VERBOSE) printf("[LWZReadByte(,%d,%d) returning %d]\n",flag,input_code_size,rv);
 
1213
 return(rv);
 
1214
}
 
1215
 
 
1216
static void
 
1217
ReadImage(gdImagePtr im, FILE *fd, int len, int height, unsigned char (*cmap)[256], int interlace, int ignore)
 
1218
{
 
1219
       unsigned char   c;      
 
1220
       int             v;
 
1221
       int             xpos = 0, ypos = 0, pass = 0;
 
1222
       int i;
 
1223
       /* Stash the color map into the image */
 
1224
       for (i=0; (i<gdMaxColors); i++) {
 
1225
               im->red[i] = cmap[CM_RED][i];    
 
1226
               im->green[i] = cmap[CM_GREEN][i];        
 
1227
               im->blue[i] = cmap[CM_BLUE][i];  
 
1228
               im->open[i] = 1;
 
1229
       }
 
1230
       /* Many (perhaps most) of these colors will remain marked open. */
 
1231
       im->colorsTotal = gdMaxColors;
 
1232
       /*
 
1233
       **  Initialize the Compression routines
 
1234
       */
 
1235
       if (! ReadOK(fd,&c,1)) {
 
1236
               return; 
 
1237
       }
 
1238
       if (LWZReadByte(fd, TRUE, c) < 0) {
 
1239
               return;
 
1240
       }
 
1241
 
 
1242
       /*
 
1243
       **  If this is an "uninteresting picture" ignore it.
 
1244
       */
 
1245
       if (ignore) {
 
1246
               while (LWZReadByte(fd, FALSE, c) >= 0)
 
1247
                       ;
 
1248
               return;
 
1249
       }
 
1250
 
 
1251
       while ((v = LWZReadByte(fd,FALSE,c)) >= 0 ) {
 
1252
               /* This how we recognize which colors are actually used. */
 
1253
               if (im->open[v]) {
 
1254
                       im->open[v] = 0;
 
1255
               }
 
1256
               gdImageSetPixel(im, xpos, ypos, v);
 
1257
               ++xpos;
 
1258
               if (xpos == len) {
 
1259
                       xpos = 0;
 
1260
                       if (interlace) {
 
1261
                               switch (pass) {
 
1262
                               case 0:
 
1263
                               case 1:
 
1264
                                       ypos += 8; break;
 
1265
                               case 2:
 
1266
                                       ypos += 4; break;
 
1267
                               case 3:
 
1268
                                       ypos += 2; break;
 
1269
                               }
 
1270
 
 
1271
                               if (ypos >= height) {
 
1272
                                       ++pass;
 
1273
                                       switch (pass) {
 
1274
                                       case 1:
 
1275
                                               ypos = 4; break;
 
1276
                                       case 2:
 
1277
                                               ypos = 2; break;
 
1278
                                       case 3:
 
1279
                                               ypos = 1; break;
 
1280
                                       default:
 
1281
                                               goto fini;
 
1282
                                       }
 
1283
                               }
 
1284
                       } else {
 
1285
                               ++ypos;
 
1286
                       }
 
1287
               }
 
1288
               if (ypos >= height)
 
1289
                       break;
 
1290
       }
 
1291
 
 
1292
fini:
 
1293
       if (LWZReadByte(fd,FALSE,c)>=0) {
 
1294
               /* Ignore extra */
 
1295
       }
 
1296
}