1/*
2 * tkImgGIF.c --
3 *
4 *	A photo image file handler for GIF files. Reads 87a and 89a GIF
5 *	files. At present, there only is a file write function. GIF images
6 *	may be read using the -data option of the photo image.  The data may be
7 *	given as a binary string in a Tcl_Obj or by representing
8 *	the data as BASE64 encoded ascii.  Derived from the giftoppm code
9 *	found in the pbmplus package and tkImgFmtPPM.c in the tk4.0b2
10 *	distribution.
11 *
12 * Copyright (c) Reed Wade (wade@cs.utk.edu), University of Tennessee
13 * Copyright (c) 1995-1997 Sun Microsystems, Inc.
14 * Copyright (c) 1997 Australian National University
15 *
16 * See the file "license.terms" for information on usage and redistribution
17 * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
18 *
19 * This file also contains code from the giftoppm program, which is
20 * copyrighted as follows:
21 *
22 * +--------------------------------------------------------------------+
23 * | Copyright 1990, David Koblas.					|
24 * |   Permission to use, copy, modify, and distribute this software	|
25 * |   and its documentation for any purpose and without fee is hereby	|
26 * |   granted, provided that the above copyright notice appear in all	|
27 * |   copies and that both that copyright notice and this permission	|
28 * |   notice appear in supporting documentation.  This software is	|
29 * |   provided "as is" without express or implied warranty.		|
30 * +-------------------------------------------------------------------+
31 *
32 * RCS: @(#) $Id: tkImgGIF.c,v 1.24.2.6 2008/02/01 16:59:58 rmax Exp $
33 */
34
35/*
36 * GIF's are represented as data in base64 format.
37 * base64 strings consist of 4 6-bit characters -> 3 8 bit bytes.
38 * A-Z, a-z, 0-9, + and / represent the 64 values (in order).
39 * '=' is a trailing padding char when the un-encoded data is not a
40 * multiple of 3 bytes.  We'll ignore white space when encountered.
41 * Any other invalid character is treated as an EOF
42 */
43
44#define GIF_SPECIAL	(256)
45#define GIF_PAD		(GIF_SPECIAL+1)
46#define GIF_SPACE	(GIF_SPECIAL+2)
47#define GIF_BAD		(GIF_SPECIAL+3)
48#define GIF_DONE	(GIF_SPECIAL+4)
49
50/*
51 * structure to "mimic" FILE for Mread, so we can look like fread.
52 * The decoder state keeps track of which byte we are about to read,
53 * or EOF.
54 */
55
56typedef struct mFile {
57    unsigned char *data;	/* mmencoded source string */
58    int length;			/* Length of string in bytes */
59    int c;			/* bits left over from previous character */
60    int state;			/* decoder state (0-4 or GIF_DONE) */
61} MFile;
62
63#include "tkInt.h"
64#include "tkPort.h"
65
66/*
67 * Non-ASCII encoding support:
68 * Most data in a GIF image is binary and is treated as such.  However,
69 * a few key bits are stashed in ASCII.  If we try to compare those pieces
70 * to the char they represent, it will fail on any non-ASCII (eg, EBCDIC)
71 * system.  To accomodate these systems, we test against the numeric value
72 * of the ASCII characters instead of the characters themselves.  This is
73 * encoding independant.
74 */
75
76static CONST char GIF87a[] = {			/* ASCII GIF87a */
77    0x47, 0x49, 0x46, 0x38, 0x37, 0x61, 0x00
78};
79static CONST char GIF89a[] = {			/* ASCII GIF89a */
80    0x47, 0x49, 0x46, 0x38, 0x39, 0x61, 0x00
81};
82#  define GIF_TERMINATOR 0x3b			/* ASCII ; */
83#  define GIF_EXTENSION  0x21			/* ASCII ! */
84#  define GIF_START	 0x2c			/* ASCII , */
85
86/*
87 * 			 HACK ALERT!!  HACK ALERT!!  HACK ALERT!!
88 * This code is hard-wired for reading from files.  In order to read
89 * from a data stream, we'll trick fread so we can reuse the same code.
90 * 0==from file; 1==from base64 encoded data; 2==from binary data
91 */
92
93typedef struct ThreadSpecificData {
94    int fromData;
95} ThreadSpecificData;
96static Tcl_ThreadDataKey dataKey;
97
98/*
99 * The format record for the GIF file format:
100 */
101
102static int	FileMatchGIF _ANSI_ARGS_((Tcl_Channel chan, CONST char *fileName,
103		    Tcl_Obj *format, int *widthPtr, int *heightPtr,
104		    Tcl_Interp *interp));
105static int	FileReadGIF  _ANSI_ARGS_((Tcl_Interp *interp,
106		    Tcl_Channel chan, CONST char *fileName, Tcl_Obj *format,
107		    Tk_PhotoHandle imageHandle, int destX, int destY,
108		    int width, int height, int srcX, int srcY));
109static int	StringMatchGIF _ANSI_ARGS_(( Tcl_Obj *dataObj,
110		    Tcl_Obj *format, int *widthPtr, int *heightPtr,
111		    Tcl_Interp *interp));
112static int	StringReadGIF _ANSI_ARGS_((Tcl_Interp *interp, Tcl_Obj *dataObj,
113		    Tcl_Obj *format, Tk_PhotoHandle imageHandle,
114		    int destX, int destY, int width, int height,
115		    int srcX, int srcY));
116static int 	FileWriteGIF _ANSI_ARGS_((Tcl_Interp *interp,
117		    CONST char *filename, Tcl_Obj *format,
118		    Tk_PhotoImageBlock *blockPtr));
119static int	CommonWriteGIF _ANSI_ARGS_((Tcl_Interp *interp,
120		    Tcl_Channel handle, Tcl_Obj *format,
121		    Tk_PhotoImageBlock *blockPtr));
122
123Tk_PhotoImageFormat tkImgFmtGIF = {
124    "gif",		/* name */
125    FileMatchGIF,	/* fileMatchProc */
126    StringMatchGIF,	/* stringMatchProc */
127    FileReadGIF,	/* fileReadProc */
128    StringReadGIF,	/* stringReadProc */
129    FileWriteGIF,	/* fileWriteProc */
130    NULL,		/* stringWriteProc */
131};
132
133#define INTERLACE		0x40
134#define LOCALCOLORMAP		0x80
135#define BitSet(byte, bit)	(((byte) & (bit)) == (bit))
136#define MAXCOLORMAPSIZE		256
137#define CM_RED			0
138#define CM_GREEN		1
139#define CM_BLUE			2
140#define CM_ALPHA		3
141#define MAX_LWZ_BITS		12
142#define LM_to_uint(a,b)		(((b)<<8)|(a))
143#define ReadOK(file,buffer,len)	(Fread(buffer, len, 1, file) != 0)
144
145/*
146 * Prototypes for local procedures defined in this file:
147 */
148
149static int		DoExtension _ANSI_ARGS_((Tcl_Channel chan, int label,
150			    int *transparent));
151static int		GetCode _ANSI_ARGS_((Tcl_Channel chan, int code_size,
152			    int flag));
153static int		GetDataBlock _ANSI_ARGS_((Tcl_Channel chan,
154			    unsigned char *buf));
155static int		ReadColorMap _ANSI_ARGS_((Tcl_Channel chan, int number,
156			    unsigned char buffer[MAXCOLORMAPSIZE][4]));
157static int		ReadGIFHeader _ANSI_ARGS_((Tcl_Channel chan,
158			    int *widthPtr, int *heightPtr));
159static int		ReadImage _ANSI_ARGS_((Tcl_Interp *interp,
160			    char *imagePtr, Tcl_Channel chan,
161			    int len, int rows,
162			    unsigned char cmap[MAXCOLORMAPSIZE][4],
163			    int width, int height, int srcX, int srcY,
164			    int interlace, int transparent));
165
166/*
167 * these are for the BASE64 image reader code only
168 */
169
170static int		Fread _ANSI_ARGS_((unsigned char *dst, size_t size,
171			    size_t count, Tcl_Channel chan));
172static int		Mread _ANSI_ARGS_((unsigned char *dst, size_t size,
173			    size_t count, MFile *handle));
174static int		Mgetc _ANSI_ARGS_((MFile *handle));
175static int		char64 _ANSI_ARGS_((int c));
176static void		mInit _ANSI_ARGS_((unsigned char *string,
177			    int length, MFile *handle));
178
179
180/*
181 *----------------------------------------------------------------------
182 *
183 * FileMatchGIF --
184 *
185 *	This procedure is invoked by the photo image type to see if
186 *	a file contains image data in GIF format.
187 *
188 * Results:
189 *	The return value is 1 if the first characters in file f look
190 *	like GIF data, and 0 otherwise.
191 *
192 * Side effects:
193 *	The access position in f may change.
194 *
195 *----------------------------------------------------------------------
196 */
197
198static int
199FileMatchGIF(chan, fileName, format, widthPtr, heightPtr, interp)
200    Tcl_Channel chan;		/* The image file, open for reading. */
201    CONST char *fileName;	/* The name of the image file. */
202    Tcl_Obj *format;		/* User-specified format object, or NULL. */
203    int *widthPtr, *heightPtr;	/* The dimensions of the image are
204				 * returned here if the file is a valid
205				 * raw GIF file. */
206    Tcl_Interp *interp;		/* not used */
207{
208	return ReadGIFHeader(chan, widthPtr, heightPtr);
209}
210
211/*
212 *----------------------------------------------------------------------
213 *
214 * FileReadGIF --
215 *
216 *	This procedure is called by the photo image type to read
217 *	GIF format data from a file and write it into a given
218 *	photo image.
219 *
220 * Results:
221 *	A standard TCL completion code.  If TCL_ERROR is returned
222 *	then an error message is left in the interp's result.
223 *
224 * Side effects:
225 *	The access position in file f is changed, and new data is
226 *	added to the image given by imageHandle.
227 *
228 *----------------------------------------------------------------------
229 */
230
231static int
232FileReadGIF(interp, chan, fileName, format, imageHandle, destX, destY,
233	width, height, srcX, srcY)
234    Tcl_Interp *interp;		/* Interpreter to use for reporting errors. */
235    Tcl_Channel chan;		/* The image file, open for reading. */
236    CONST char *fileName;	/* The name of the image file. */
237    Tcl_Obj *format;		/* User-specified format object, or NULL. */
238    Tk_PhotoHandle imageHandle;	/* The photo image to write into. */
239    int destX, destY;		/* Coordinates of top-left pixel in
240				 * photo image to be written to. */
241    int width, height;		/* Dimensions of block of photo image to
242				 * be written to. */
243    int srcX, srcY;		/* Coordinates of top-left pixel to be used
244				 * in image being read. */
245{
246    int fileWidth, fileHeight, imageWidth, imageHeight;
247    int nBytes, index = 0, argc = 0, i;
248    Tcl_Obj **objv;
249    Tk_PhotoImageBlock block;
250    unsigned char buf[100];
251    unsigned char *trashBuffer = NULL;
252    int bitPixel;
253    unsigned char colorMap[MAXCOLORMAPSIZE][4];
254    int transparent = -1;
255    static CONST char *optionStrings[] = {
256	"-index",	NULL
257    };
258
259    if (format && Tcl_ListObjGetElements(interp, format,
260	    &argc, &objv) != TCL_OK) {
261	return TCL_ERROR;
262    }
263    for (i = 1; i < argc; i++) {
264	if (Tcl_GetIndexFromObj(interp, objv[i], optionStrings, "option name", 0,
265		&nBytes) != TCL_OK) {
266	    return TCL_ERROR;
267	}
268	if (i == (argc-1)) {
269	    Tcl_AppendResult(interp, "no value given for \"",
270		    Tcl_GetStringFromObj(objv[i], NULL),
271		    "\" option", (char *) NULL);
272	    return TCL_ERROR;
273	}
274	if (Tcl_GetIntFromObj(interp, objv[++i], &index) != TCL_OK) {
275	    return TCL_ERROR;
276	}
277    }
278    if (!ReadGIFHeader(chan, &fileWidth, &fileHeight)) {
279    	Tcl_AppendResult(interp, "couldn't read GIF header from file \"",
280		fileName, "\"", NULL);
281	return TCL_ERROR;
282    }
283    if ((fileWidth <= 0) || (fileHeight <= 0)) {
284	Tcl_AppendResult(interp, "GIF image file \"", fileName,
285		"\" has dimension(s) <= 0", (char *) NULL);
286	return TCL_ERROR;
287    }
288
289    if (Fread(buf, 1, 3, chan) != 3) {
290	return TCL_OK;
291    }
292    bitPixel = 2<<(buf[0]&0x07);
293
294    if (BitSet(buf[0], LOCALCOLORMAP)) {	/* Global Colormap */
295	if (!ReadColorMap(chan, bitPixel, colorMap)) {
296	    Tcl_AppendResult(interp, "error reading color map",
297		    (char *) NULL);
298	    return TCL_ERROR;
299	}
300    }
301
302    if ((srcX + width) > fileWidth) {
303	width = fileWidth - srcX;
304    }
305    if ((srcY + height) > fileHeight) {
306	height = fileHeight - srcY;
307    }
308    if ((width <= 0) || (height <= 0)
309	    || (srcX >= fileWidth) || (srcY >= fileHeight)) {
310	return TCL_OK;
311    }
312
313    Tk_PhotoExpand(imageHandle, destX + width, destY + height);
314
315    block.width = width;
316    block.height = height;
317    block.pixelSize = 4;
318    block.pitch = block.pixelSize * block.width;
319    block.offset[0] = 0;
320    block.offset[1] = 1;
321    block.offset[2] = 2;
322    block.offset[3] = 3;
323    block.pixelPtr = NULL;
324
325    while (1) {
326	if (Fread(buf, 1, 1, chan) != 1) {
327	    /*
328	     * Premature end of image.
329	     */
330
331	    Tcl_AppendResult(interp,"premature end of image data for this index",
332                             (char *) NULL);
333	    goto error;
334	}
335
336	if (buf[0] == GIF_TERMINATOR) {
337	    /*
338	     * GIF terminator.
339	     */
340
341	    Tcl_AppendResult(interp,"no image data for this index",
342		    (char *) NULL);
343	    goto error;
344	}
345
346	if (buf[0] == GIF_EXTENSION) {
347	    /*
348	     * This is a GIF extension.
349	     */
350
351	    if (Fread(buf, 1, 1, chan) != 1) {
352		Tcl_SetResult(interp,
353			"error reading extension function code in GIF image",
354			TCL_STATIC);
355		goto error;
356	    }
357	    if (DoExtension(chan, buf[0], &transparent) < 0) {
358		Tcl_SetResult(interp, "error reading extension in GIF image",
359			TCL_STATIC);
360		goto error;
361	    }
362	    continue;
363	}
364
365	if (buf[0] != GIF_START) {
366	    /*
367	     * Not a valid start character; ignore it.
368	     */
369	    continue;
370	}
371
372	if (Fread(buf, 1, 9, chan) != 9) {
373	    Tcl_SetResult(interp,
374		    "couldn't read left/top/width/height in GIF image",
375		    TCL_STATIC);
376	    goto error;
377	}
378
379	imageWidth = LM_to_uint(buf[4],buf[5]);
380	imageHeight = LM_to_uint(buf[6],buf[7]);
381
382	bitPixel = 1<<((buf[8]&0x07)+1);
383
384	if (index--) {
385	    /*
386	     * This is not the image we want to read: skip it.
387	     */
388	    if (BitSet(buf[8], LOCALCOLORMAP)) {
389		if (!ReadColorMap(chan, bitPixel, colorMap)) {
390		    Tcl_AppendResult(interp,
391			    "error reading color map", (char *) NULL);
392		    goto error;
393		}
394	    }
395
396	    /*
397	     * If we've not yet allocated a trash buffer, do so now.
398	     */
399	    if (trashBuffer == NULL) {
400		nBytes = fileWidth * fileHeight * 3;
401		trashBuffer =
402		    (unsigned char *) ckalloc((unsigned int) nBytes);
403	    }
404
405	    /*
406	     * Slurp!  Process the data for this image and stuff it in
407	     * a trash buffer.
408	     *
409	     * Yes, it might be more efficient here to *not* store the
410	     * data (we're just going to throw it away later).
411	     * However, I elected to implement it this way for good
412	     * reasons.  First, I wanted to avoid duplicating the
413	     * (fairly complex) LWZ decoder in ReadImage.  Fine, you
414	     * say, why didn't you just modify it to allow the use of
415	     * a NULL specifier for the output buffer?  I tried that,
416	     * but it negatively impacted the performance of what I
417	     * think will be the common case: reading the first image
418	     * in the file.  Rather than marginally improve the speed
419	     * of the less frequent case, I chose to maintain high
420	     * performance for the common case.
421	     */
422	    if (ReadImage(interp, (char *) trashBuffer, chan, imageWidth,
423		    imageHeight, colorMap, 0, 0, 0, 0, 0, -1) != TCL_OK) {
424		goto error;
425	    }
426	    continue;
427	}
428
429	if (BitSet(buf[8], LOCALCOLORMAP)) {
430	    if (!ReadColorMap(chan, bitPixel, colorMap)) {
431		    Tcl_AppendResult(interp, "error reading color map",
432			    (char *) NULL);
433		    goto error;
434	    }
435	}
436
437	index = LM_to_uint(buf[0],buf[1]);
438	srcX -= index;
439	if (srcX<0) {
440	    destX -= srcX; width += srcX;
441	    srcX = 0;
442	}
443
444	if (width > imageWidth) {
445	    width = imageWidth;
446	}
447
448	index = LM_to_uint(buf[2],buf[3]);
449	srcY -= index;
450	if (index > srcY) {
451	    destY -= srcY; height += srcY;
452	    srcY = 0;
453	}
454	if (height > imageHeight) {
455	    height = imageHeight;
456	}
457
458	if ((width <= 0) || (height <= 0)) {
459	    block.pixelPtr = 0;
460	    goto noerror;
461	}
462
463	block.width = width;
464	block.height = height;
465	block.pixelSize = (transparent>=0) ? 4 : 3;
466	block.offset[3] = (transparent>=0) ? 3 : 0;
467	block.pitch = block.pixelSize * imageWidth;
468	nBytes = block.pitch * imageHeight;
469	block.pixelPtr = (unsigned char *) ckalloc((unsigned) nBytes);
470
471	if (ReadImage(interp, (char *) block.pixelPtr, chan, imageWidth,
472		imageHeight, colorMap, fileWidth, fileHeight, srcX, srcY,
473		BitSet(buf[8], INTERLACE), transparent) != TCL_OK) {
474	    goto error;
475	}
476	break;
477    }
478
479    Tk_PhotoPutBlock(imageHandle, &block, destX, destY, width, height,
480	    TK_PHOTO_COMPOSITE_SET);
481
482    noerror:
483    /*
484     * If a trash buffer has been allocated, free it now.
485     */
486    if (trashBuffer != NULL) {
487	ckfree((char *)trashBuffer);
488    }
489    if (block.pixelPtr) {
490	ckfree((char *) block.pixelPtr);
491    }
492    Tcl_AppendResult(interp, tkImgFmtGIF.name, (char *) NULL);
493    return TCL_OK;
494
495    error:
496    /*
497     * If a trash buffer has been allocated, free it now.
498     */
499    if (trashBuffer != NULL) {
500	ckfree((char *)trashBuffer);
501    }
502    if (block.pixelPtr) {
503	ckfree((char *) block.pixelPtr);
504    }
505    return TCL_ERROR;
506}
507
508/*
509 *----------------------------------------------------------------------
510 *
511 * StringMatchGIF --
512 *
513 *  This procedure is invoked by the photo image type to see if
514 *  an object contains image data in GIF format.
515 *
516 * Results:
517 *  The return value is 1 if the first characters in the data are
518 *  like GIF data, and 0 otherwise.
519 *
520 * Side effects:
521 *  the size of the image is placed in widthPre and heightPtr.
522 *
523 *----------------------------------------------------------------------
524 */
525
526static int
527StringMatchGIF(dataObj, format, widthPtr, heightPtr, interp)
528    Tcl_Obj *dataObj;		/* the object containing the image data */
529    Tcl_Obj *format;		/* the image format object, or NULL */
530    int *widthPtr;		/* where to put the string width */
531    int *heightPtr;		/* where to put the string height */
532    Tcl_Interp *interp;		/* not used */
533{
534    unsigned char *data, header[10];
535    int got, length;
536    MFile handle;
537
538    data = Tcl_GetByteArrayFromObj(dataObj, &length);
539
540    /*
541     * Header is a minimum of 10 bytes.
542     */
543    if (length < 10) {
544	return 0;
545    }
546
547    /*
548     * Check whether the data is Base64 encoded.
549     */
550
551    if ((strncmp(GIF87a, (char *) data, 6) != 0) &&
552	    (strncmp(GIF89a, (char *) data, 6) != 0)) {
553	/*
554	 * Try interpreting the data as Base64 encoded
555	 */
556	mInit((unsigned char *) data, length, &handle);
557	got = Mread(header, 10, 1, &handle);
558	if (got != 10
559		|| ((strncmp(GIF87a, (char *) header, 6) != 0)
560		&& (strncmp(GIF89a, (char *) header, 6) != 0))) {
561	    return 0;
562	}
563    } else {
564	memcpy((VOID *) header, (VOID *) data, 10);
565    }
566    *widthPtr = LM_to_uint(header[6],header[7]);
567    *heightPtr = LM_to_uint(header[8],header[9]);
568    return 1;
569}
570
571/*
572 *----------------------------------------------------------------------
573 *
574 * StringReadGif -- --
575 *
576 *	This procedure is called by the photo image type to read
577 *	GIF format data from an object, optionally base64 encoded,
578 *	and give it to the photo image.
579 *
580 * Results:
581 *	A standard TCL completion code.  If TCL_ERROR is returned
582 *	then an error message is left in the interp's result.
583 *
584 * Side effects:
585 *	new data is added to the image given by imageHandle.  This
586 *	procedure calls FileReadGif by redefining the operation of
587 *	fprintf temporarily.
588 *
589 *----------------------------------------------------------------------
590 */
591
592static int
593StringReadGIF(interp, dataObj, format, imageHandle,
594	destX, destY, width, height, srcX, srcY)
595    Tcl_Interp *interp;		/* interpreter for reporting errors in */
596    Tcl_Obj *dataObj;		/* object containing the image */
597    Tcl_Obj *format;		/* format object, or NULL */
598    Tk_PhotoHandle imageHandle;	/* the image to write this data into */
599    int destX, destY;		/* The rectangular region of the  */
600    int width, height;		/*   image to copy */
601    int srcX, srcY;
602{
603    int result, length;
604    MFile handle;
605    ThreadSpecificData *tsdPtr = (ThreadSpecificData *)
606	    Tcl_GetThreadData(&dataKey, sizeof(ThreadSpecificData));
607    Tcl_Channel dataSrc;
608    char *data;
609
610    /*
611     * Check whether the data is Base64 encoded
612     */
613    data = (char *) Tcl_GetByteArrayFromObj(dataObj, &length);
614    if ((strncmp(GIF87a, data, 6) != 0) && (strncmp(GIF89a, data, 6) != 0)) {
615	mInit((unsigned char *)data, length, &handle);
616	tsdPtr->fromData = 1;
617	dataSrc = (Tcl_Channel) &handle;
618    } else {
619	tsdPtr->fromData = 2;
620	mInit((unsigned char *)data, length, &handle);
621	dataSrc = (Tcl_Channel) &handle;
622    }
623    result = FileReadGIF(interp, dataSrc, "inline data",
624	    format, imageHandle, destX, destY, width, height, srcX, srcY);
625    tsdPtr->fromData = 0;
626    return result;
627}
628
629/*
630 *----------------------------------------------------------------------
631 *
632 * ReadGIFHeader --
633 *
634 *	This procedure reads the GIF header from the beginning of a
635 *	GIF file and returns the dimensions of the image.
636 *
637 * Results:
638 *	The return value is 1 if file "f" appears to start with
639 *	a valid GIF header, 0 otherwise.  If the header is valid,
640 *	then *widthPtr and *heightPtr are modified to hold the
641 *	dimensions of the image.
642 *
643 * Side effects:
644 *	The access position in f advances.
645 *
646 *----------------------------------------------------------------------
647 */
648
649static int
650ReadGIFHeader(chan, widthPtr, heightPtr)
651    Tcl_Channel chan;		/* Image file to read the header from */
652    int *widthPtr, *heightPtr;	/* The dimensions of the image are
653				 * returned here. */
654{
655    unsigned char buf[7];
656
657    if ((Fread(buf, 1, 6, chan) != 6)
658	    || ((strncmp(GIF87a, (char *) buf, 6) != 0)
659	    && (strncmp(GIF89a, (char *) buf, 6) != 0))) {
660	return 0;
661    }
662
663    if (Fread(buf, 1, 4, chan) != 4) {
664	return 0;
665    }
666
667    *widthPtr = LM_to_uint(buf[0],buf[1]);
668    *heightPtr = LM_to_uint(buf[2],buf[3]);
669    return 1;
670}
671
672/*
673 *-----------------------------------------------------------------
674 * The code below is copied from the giftoppm program and modified
675 * just slightly.
676 *-----------------------------------------------------------------
677 */
678
679static int
680ReadColorMap(chan, number, buffer)
681    Tcl_Channel chan;
682    int number;
683    unsigned char buffer[MAXCOLORMAPSIZE][4];
684{
685    int i;
686    unsigned char rgb[3];
687
688    for (i = 0; i < number; ++i) {
689	if (! ReadOK(chan, rgb, sizeof(rgb))) {
690	    return 0;
691	}
692
693	if (buffer) {
694	    buffer[i][CM_RED] = rgb[0] ;
695	    buffer[i][CM_GREEN] = rgb[1] ;
696	    buffer[i][CM_BLUE] = rgb[2] ;
697	    buffer[i][CM_ALPHA] = 255 ;
698	}
699    }
700    return 1;
701}
702
703
704
705static int
706DoExtension(chan, label, transparent)
707    Tcl_Channel chan;
708    int label;
709    int *transparent;
710{
711    static unsigned char buf[256];
712    int count;
713
714    switch (label) {
715    case 0x01:		/* Plain Text Extension */
716	break;
717
718    case 0xff:		/* Application Extension */
719	break;
720
721    case 0xfe:		/* Comment Extension */
722	do {
723	    count = GetDataBlock(chan, (unsigned char*) buf);
724	} while (count > 0);
725	return count;
726
727    case 0xf9:		/* Graphic Control Extension */
728	count = GetDataBlock(chan, (unsigned char*) buf);
729	if (count < 0) {
730	    return 1;
731	}
732	if ((buf[0] & 0x1) != 0) {
733	    *transparent = buf[3];
734	}
735
736	do {
737	    count = GetDataBlock(chan, (unsigned char*) buf);
738	} while (count > 0);
739	return count;
740    }
741
742    do {
743	count = GetDataBlock(chan, (unsigned char*) buf);
744    } while (count > 0);
745    return count;
746}
747
748static int
749GetDataBlock(chan, buf)
750    Tcl_Channel chan;
751    unsigned char *buf;
752{
753    unsigned char count;
754
755    if (! ReadOK(chan, &count,1)) {
756	return -1;
757    }
758
759    if ((count != 0) && (! ReadOK(chan, buf, count))) {
760	return -1;
761    }
762
763    return count;
764}
765
766
767
768/*
769 *----------------------------------------------------------------------
770 *
771 * ReadImage --
772 *
773 *	Process a GIF image from a given source, with a given height,
774 *	width, transparency, etc.
775 *
776 *	This code is based on the code found in the ImageMagick GIF decoder,
777 *	which is (c) 2000 ImageMagick Studio.
778 *
779 *	Some thoughts on our implementation:
780 *	It sure would be nice if ReadImage didn't take 11 parameters!  I think
781 *	that if we were smarter, we could avoid doing that.
782 *
783 *	Possible further optimizations:  we could pull the GetCode function
784 *	directly into ReadImage, which would improve our speed.
785 *
786 * Results:
787 *	Processes a GIF image and loads the pixel data into a memory array.
788 *
789 * Side effects:
790 *	None.
791 *
792 *----------------------------------------------------------------------
793 */
794
795static int
796ReadImage(interp, imagePtr, chan, len, rows, cmap,
797	width, height, srcX, srcY, interlace, transparent)
798    Tcl_Interp *interp;
799    char *imagePtr;
800    Tcl_Channel chan;
801    int len, rows;
802    unsigned char cmap[MAXCOLORMAPSIZE][4];
803    int width, height;
804    int srcX, srcY;
805    int interlace;
806    int transparent;
807{
808    unsigned char initialCodeSize;
809    int v;
810    int xpos = 0, ypos = 0, pass = 0, i;
811    register char *pixelPtr;
812    CONST static int interlaceStep[] = { 8, 8, 4, 2 };
813    CONST static int interlaceStart[] = { 0, 4, 2, 1 };
814    unsigned short prefix[(1 << MAX_LWZ_BITS)];
815    unsigned char  append[(1 << MAX_LWZ_BITS)];
816    unsigned char  stack[(1 << MAX_LWZ_BITS)*2];
817    register unsigned char *top;
818    int codeSize, clearCode, inCode, endCode, oldCode, maxCode;
819    int code, firstCode;
820
821    /*
822     *  Initialize the decoder
823     */
824    if (! ReadOK(chan, &initialCodeSize, 1))  {
825	Tcl_AppendResult(interp, "error reading GIF image: ",
826		Tcl_PosixError(interp), (char *) NULL);
827	return TCL_ERROR;
828    }
829
830    if (initialCodeSize > MAX_LWZ_BITS) {
831	Tcl_SetResult(interp, "malformed image", TCL_STATIC);
832	return TCL_ERROR;
833    }
834
835    if (transparent != -1) {
836	cmap[transparent][CM_RED] = 0;
837	cmap[transparent][CM_GREEN] = 0;
838	cmap[transparent][CM_BLUE] = 0;
839	cmap[transparent][CM_ALPHA] = 0;
840    }
841
842    pixelPtr = imagePtr;
843
844    /*
845     * Initialize the decoder.
846     *
847     * Set values for "special" numbers:
848     * clear code	reset the decoder
849     * end code		stop decoding
850     * code size	size of the next code to retrieve
851     * max code		next available table position
852     */
853    clearCode = 1 << (int) initialCodeSize;
854    endCode = clearCode + 1;
855    codeSize = (int) initialCodeSize + 1;
856    maxCode = clearCode + 2;
857    oldCode = -1;
858    firstCode = -1;
859
860    memset((void *)prefix, 0, (1 << MAX_LWZ_BITS) * sizeof(short));
861    memset((void *)append, 0, (1 << MAX_LWZ_BITS) * sizeof(char));
862    for (i = 0; i < clearCode; i++) {
863	append[i] = i;
864    }
865    top = stack;
866
867    GetCode(chan, 0, 1);
868
869    /*
870     * Read until we finish the image
871     */
872    for (i = 0, ypos = 0; i < rows; i++) {
873	for (xpos = 0; xpos < len; ) {
874
875	    if (top == stack) {
876		/*
877		 * Bummer -- our stack is empty.  Now we have to work!
878		 */
879		code = GetCode(chan, codeSize, 0);
880		if (code < 0) {
881		    return TCL_OK;
882		}
883
884		if (code > maxCode || code == endCode) {
885		    /*
886		     * If we're doing things right, we should never
887		     * receive a code that is greater than our current
888		     * maximum code.  If we do, bail, because our decoder
889		     * does not yet have that code set up.
890		     *
891		     * If the code is the magic endCode value, quit.
892		     */
893		    return TCL_OK;
894		}
895
896		if (code == clearCode) {
897		    /*
898		     * Reset the decoder.
899		     */
900		    codeSize = initialCodeSize + 1;
901		    maxCode = clearCode + 2;
902		    oldCode = -1;
903		    continue;
904		}
905
906		if (oldCode == -1) {
907		    /*
908		     * Last pass reset the decoder, so the first code we
909		     * see must be a singleton.  Seed the stack with it,
910		     * and set up the old/first code pointers for
911		     * insertion into the string table.  We can't just
912		     * roll this into the clearCode test above, because
913		     * at that point we have not yet read the next code.
914		     */
915		    *top++ = append[code];
916		    oldCode = code;
917		    firstCode = code;
918		    continue;
919		}
920
921		inCode = code;
922
923		if (code == maxCode) {
924		    /*
925		     * maxCode is always one bigger than our highest assigned
926		     * code.  If the code we see is equal to maxCode, then
927		     * we are about to add a new string to the table. ???
928		     */
929		    *top++ = firstCode;
930		    code = oldCode;
931		}
932
933		while (code > clearCode) {
934		    /*
935		     * Populate the stack by tracing the string in the
936		     * string table from its tail to its head
937		     */
938		    *top++ = append[code];
939		    code = prefix[code];
940		}
941		firstCode = append[code];
942
943		/*
944		 * If there's no more room in our string table, quit.
945		 * Otherwise, add a new string to the table
946		 */
947		if (maxCode >= (1 << MAX_LWZ_BITS)) {
948		    return TCL_OK;
949		}
950
951		/*
952		 * Push the head of the string onto the stack.
953		 */
954		*top++ = firstCode;
955
956		/*
957		 * Add a new string to the string table
958		 */
959		prefix[maxCode] = oldCode;
960		append[maxCode] = firstCode;
961		maxCode++;
962
963		/*
964		 * maxCode tells us the maximum code value we can accept.
965		 * If we see that we need more bits to represent it than
966		 * we are requesting from the unpacker, we need to increase
967		 * the number we ask for.
968		 */
969		if ((maxCode >= (1 << codeSize))
970			&& (maxCode < (1<<MAX_LWZ_BITS))) {
971		    codeSize++;
972		}
973		oldCode = inCode;
974	    }
975
976	    /*
977	     * Pop the next color index off the stack.
978	     */
979	    v = *(--top);
980	    if (v < 0) {
981		return TCL_OK;
982	    }
983
984	    /*
985	     * If pixelPtr is null, we're skipping this image (presumably
986	     * there are more in the file and we will be called to read
987	     * one of them later)
988	     */
989	    *pixelPtr++ = cmap[v][CM_RED];
990	    *pixelPtr++ = cmap[v][CM_GREEN];
991	    *pixelPtr++ = cmap[v][CM_BLUE];
992	    if (transparent >= 0) {
993		*pixelPtr++ = cmap[v][CM_ALPHA];
994	    }
995	    xpos++;
996
997	}
998
999	/*
1000	 * If interlacing, the next ypos is not just +1
1001	 */
1002	if (interlace) {
1003	    ypos += interlaceStep[pass];
1004	    while (ypos >= rows) {
1005		pass++;
1006		if (pass > 3) {
1007		    return TCL_OK;
1008		}
1009		ypos = interlaceStart[pass];
1010	    }
1011	} else {
1012	    ypos++;
1013	}
1014	pixelPtr = imagePtr + (ypos) * len * ((transparent>=0)?4:3);
1015    }
1016    return TCL_OK;
1017}
1018
1019
1020/*
1021 *----------------------------------------------------------------------
1022 *
1023 * GetCode --
1024 *
1025 *	Extract the next compression code from the file.  In GIF's, the
1026 *	compression codes are between 3 and 12 bits long and are then
1027 *	packed into 8 bit bytes, left to right, for example:
1028 *		bbbaaaaa
1029 *		dcccccbb
1030 *		eeeedddd
1031 *		...
1032 *	We use a byte buffer read from the file and a sliding window
1033 *	to unpack the bytes.  Thanks to ImageMagick for the sliding window
1034 *	idea.
1035 *	args:  chan	    the channel to read from
1036 *	       code_size    size of the code to extract
1037 *	       flag	    boolean indicating whether the extractor
1038 *			    should be reset or not
1039 *
1040 * Results:
1041 *	code		    the next compression code
1042 *
1043 * Side effects:
1044 *	May consume more input from chan.
1045 *
1046 *----------------------------------------------------------------------
1047 */
1048
1049static int
1050GetCode(chan, code_size, flag)
1051    Tcl_Channel chan;
1052    int code_size;
1053    int flag;
1054{
1055    static unsigned char buf[280];
1056    static int bytes = 0, done;
1057    static unsigned char *c;
1058
1059    static unsigned int window;
1060    static int bitsInWindow = 0;
1061    int ret;
1062
1063    if (flag) {
1064	/*
1065	 * Initialize the decoder.
1066	 */
1067	bitsInWindow = 0;
1068	bytes = 0;
1069	window = 0;
1070	done = 0;
1071	c = NULL;
1072	return 0;
1073    }
1074
1075    while (bitsInWindow < code_size) {
1076	/*
1077	 * Not enough bits in our window to cover the request.
1078	 */
1079	if (done) {
1080	    return -1;
1081	}
1082	if (bytes == 0) {
1083	    /*
1084	     * Not enough bytes in our buffer to add to the window.
1085	     */
1086	    bytes = GetDataBlock(chan, buf);
1087	    c = buf;
1088	    if (bytes <= 0) {
1089		done = 1;
1090		break;
1091	    }
1092	}
1093	/*
1094	 * Tack another byte onto the window, see if that's enough.
1095	 */
1096	window += (*c) << bitsInWindow;
1097	c++;
1098	bitsInWindow += 8;
1099	bytes--;
1100    }
1101
1102
1103    /*
1104     * The next code will always be the last code_size bits of the window.
1105     */
1106    ret = window & ((1 << code_size) - 1);
1107
1108    /*
1109     * Shift data in the window to put the next code at the end.
1110     */
1111    window >>= code_size;
1112    bitsInWindow -= code_size;
1113    return ret;
1114}
1115
1116/*
1117 *----------------------------------------------------------------------
1118 *
1119 * Minit -- --
1120 *
1121 *  This procedure initializes a base64 decoder handle
1122 *
1123 * Results:
1124 *  none
1125 *
1126 * Side effects:
1127 *  the base64 handle is initialized
1128 *
1129 *----------------------------------------------------------------------
1130 */
1131
1132static void
1133mInit(string, length, handle)
1134    unsigned char *string;	/* string containing initial mmencoded data */
1135    int length;			/* Length of string */
1136    MFile *handle;		/* mmdecode "file" handle */
1137{
1138    handle->data = string;
1139    handle->length = length;
1140    handle->state = 0;
1141    handle->c = 0;
1142}
1143
1144/*
1145 *----------------------------------------------------------------------
1146 *
1147 * Mread --
1148 *
1149 *	This procedure is invoked by the GIF file reader as a
1150 *	temporary replacement for "fread", to get GIF data out
1151 *	of a string (using Mgetc).
1152 *
1153 * Results:
1154 *	The return value is the number of characters "read"
1155 *
1156 * Side effects:
1157 *	The base64 handle will change state.
1158 *
1159 *----------------------------------------------------------------------
1160 */
1161
1162static int
1163Mread(dst, chunkSize, numChunks, handle)
1164    unsigned char *dst;	/* where to put the result */
1165    size_t chunkSize;	/* size of each transfer */
1166    size_t numChunks;	/* number of chunks */
1167    MFile *handle;	/* mmdecode "file" handle */
1168{
1169    register int i, c;
1170    int count = chunkSize * numChunks;
1171
1172    for(i=0; i<count && (c=Mgetc(handle)) != GIF_DONE; i++) {
1173	*dst++ = c;
1174    }
1175    return i;
1176}
1177
1178/*
1179 * get the next decoded character from an mmencode handle
1180 * This causes at least 1 character to be "read" from the encoded string
1181 */
1182
1183/*
1184 *----------------------------------------------------------------------
1185 *
1186 * Mgetc --
1187 *
1188 *  This procedure decodes and returns the next byte from a base64
1189 *  encoded string.
1190 *
1191 * Results:
1192 *  The next byte (or GIF_DONE) is returned.
1193 *
1194 * Side effects:
1195 *  The base64 handle will change state.
1196 *
1197 *----------------------------------------------------------------------
1198 */
1199
1200static int
1201Mgetc(handle)
1202   MFile *handle;		/* Handle containing decoder data and state */
1203{
1204    int c;
1205    int result = 0;		/* Initialization needed only to prevent
1206				 * gcc compiler warning. */
1207
1208    if (handle->state == GIF_DONE) {
1209	return GIF_DONE;
1210    }
1211
1212    do {
1213	if (handle->length-- <= 0) {
1214	    handle->state = GIF_DONE;
1215	    return GIF_DONE;
1216	}
1217	c = char64(*handle->data);
1218	handle->data++;
1219    } while (c == GIF_SPACE);
1220
1221    if (c>GIF_SPECIAL) {
1222	handle->state = GIF_DONE;
1223	return handle->c;
1224    }
1225
1226    switch (handle->state++) {
1227    case 0:
1228	handle->c = c<<2;
1229	result = Mgetc(handle);
1230	break;
1231    case 1:
1232	result = handle->c | (c>>4);
1233	handle->c = (c&0xF)<<4;
1234	break;
1235    case 2:
1236	result = handle->c | (c>>2);
1237	handle->c = (c&0x3) << 6;
1238	break;
1239    case 3:
1240	result = handle->c | c;
1241	handle->state = 0;
1242	break;
1243    }
1244    return result;
1245}
1246
1247/*
1248 *----------------------------------------------------------------------
1249 *
1250 * char64 --
1251 *
1252 *	This procedure converts a base64 ascii character into its binary
1253 *	equivalent.  This code is a slightly modified version of the
1254 *	char64 proc in N. Borenstein's metamail decoder.
1255 *
1256 * Results:
1257 *	The binary value, or an error code.
1258 *
1259 * Side effects:
1260 *	None.
1261 *----------------------------------------------------------------------
1262 */
1263
1264static int
1265char64(c)
1266int c;
1267{
1268    switch(c) {
1269    case 'A': return 0;  case 'B': return 1;  case 'C': return 2;
1270    case 'D': return 3;  case 'E': return 4;  case 'F': return 5;
1271    case 'G': return 6;  case 'H': return 7;  case 'I': return 8;
1272    case 'J': return 9;  case 'K': return 10; case 'L': return 11;
1273    case 'M': return 12; case 'N': return 13; case 'O': return 14;
1274    case 'P': return 15; case 'Q': return 16; case 'R': return 17;
1275    case 'S': return 18; case 'T': return 19; case 'U': return 20;
1276    case 'V': return 21; case 'W': return 22; case 'X': return 23;
1277    case 'Y': return 24; case 'Z': return 25; case 'a': return 26;
1278    case 'b': return 27; case 'c': return 28; case 'd': return 29;
1279    case 'e': return 30; case 'f': return 31; case 'g': return 32;
1280    case 'h': return 33; case 'i': return 34; case 'j': return 35;
1281    case 'k': return 36; case 'l': return 37; case 'm': return 38;
1282    case 'n': return 39; case 'o': return 40; case 'p': return 41;
1283    case 'q': return 42; case 'r': return 43; case 's': return 44;
1284    case 't': return 45; case 'u': return 46; case 'v': return 47;
1285    case 'w': return 48; case 'x': return 49; case 'y': return 50;
1286    case 'z': return 51; case '0': return 52; case '1': return 53;
1287    case '2': return 54; case '3': return 55; case '4': return 56;
1288    case '5': return 57; case '6': return 58; case '7': return 59;
1289    case '8': return 60; case '9': return 61; case '+': return 62;
1290    case '/': return 63;
1291
1292    case ' ': case '\t': case '\n': case '\r': case '\f':
1293	return GIF_SPACE;
1294    case '=':
1295	return GIF_PAD;
1296    case '\0':
1297	return GIF_DONE;
1298    default:
1299	return GIF_BAD;
1300    }
1301}
1302
1303/*
1304 *----------------------------------------------------------------------
1305 *
1306 * Fread --
1307 *
1308 *  This procedure calls either fread or Mread to read data
1309 *  from a file or a base64 encoded string.
1310 *
1311 * Results: - same as fread
1312 *
1313 *----------------------------------------------------------------------
1314 */
1315
1316static int
1317Fread(dst, hunk, count, chan)
1318    unsigned char *dst;		/* where to put the result */
1319    size_t hunk,count;		/* how many */
1320    Tcl_Channel chan;
1321{
1322    ThreadSpecificData *tsdPtr = (ThreadSpecificData *)
1323	    Tcl_GetThreadData(&dataKey, sizeof(ThreadSpecificData));
1324    MFile *handle;
1325
1326    switch (tsdPtr->fromData) {
1327    case 1:
1328	return Mread(dst, hunk, count, (MFile *) chan);
1329    case 2:
1330	handle = (MFile *) chan;
1331	if (handle->length <= 0 || (size_t)handle->length < (size_t) (hunk * count)) {
1332	    return -1;
1333	}
1334	memcpy((VOID *)dst, (VOID *) handle->data, (size_t) (hunk * count));
1335	handle->data += hunk * count;
1336	handle->length -= hunk * count;
1337	return (int)(hunk * count);
1338    default:
1339	return Tcl_Read(chan, (char *) dst, (int) (hunk * count));
1340    }
1341}
1342
1343
1344/*
1345 * ChanWriteGIF - writes a image in GIF format.
1346 *-------------------------------------------------------------------------
1347 * Author:			Lolo
1348 *				Engeneering Projects Area
1349 *				Department of Mining
1350 *				University of Oviedo
1351 * e-mail			zz11425958@zeus.etsimo.uniovi.es
1352 *				lolo@pcsig22.etsimo.uniovi.es
1353 * Date:			Fri September 20 1996
1354 *
1355 * Modified for transparency handling (gif89a) and miGIF compression
1356 * by Jan Nijtmans <j.nijtmans@chello.nl>
1357 *
1358 *----------------------------------------------------------------------
1359 * FileWriteGIF-
1360 *
1361 *    This procedure is called by the photo image type to write
1362 *    GIF format data from a photo image into a given file
1363 *
1364 * Results:
1365 *	A standard TCL completion code.  If TCL_ERROR is returned
1366 *	then an error message is left in interp->result.
1367 *
1368 *----------------------------------------------------------------------
1369 */
1370
1371 /*
1372  *  Types, defines and variables needed to write and compress a GIF.
1373  */
1374
1375typedef int (* ifunptr) _ANSI_ARGS_((void));
1376
1377#define LSB(a)			((unsigned char) (((short)(a)) & 0x00FF))
1378#define MSB(a)			((unsigned char) (((short)(a)) >> 8))
1379
1380#define GIFBITS 12
1381#define HSIZE  5003		/* 80% occupancy */
1382
1383static int ssize;
1384static int csize;
1385static int rsize;
1386static unsigned char *pixelo;
1387static int pixelSize;
1388static int pixelPitch;
1389static int greenOffset;
1390static int blueOffset;
1391static int alphaOffset;
1392static int num;
1393static unsigned char mapa[MAXCOLORMAPSIZE][3];
1394
1395/*
1396 *	Definition of new functions to write GIFs
1397 */
1398
1399static int color _ANSI_ARGS_((int red,int green, int blue,
1400		unsigned char mapa[MAXCOLORMAPSIZE][3]));
1401static void compress _ANSI_ARGS_((int init_bits, Tcl_Channel handle,
1402		ifunptr readValue));
1403static int nuevo _ANSI_ARGS_((int red, int green ,int blue,
1404		unsigned char mapa[MAXCOLORMAPSIZE][3]));
1405static void savemap _ANSI_ARGS_((Tk_PhotoImageBlock *blockPtr,
1406		unsigned char mapa[MAXCOLORMAPSIZE][3]));
1407static int ReadValue _ANSI_ARGS_((void));
1408
1409static int
1410FileWriteGIF(interp, filename, format, blockPtr)
1411    Tcl_Interp *interp;		/* Interpreter to use for reporting errors. */
1412    CONST char	*filename;
1413    Tcl_Obj	*format;
1414    Tk_PhotoImageBlock *blockPtr;
1415{
1416    Tcl_Channel chan = NULL;
1417    int result;
1418
1419    chan = Tcl_OpenFileChannel(interp, (char *) filename, "w", 0644);
1420    if (!chan) {
1421	return TCL_ERROR;
1422    }
1423    if (Tcl_SetChannelOption(interp, chan, "-translation", "binary") != TCL_OK) {
1424	Tcl_Close(NULL, chan);
1425	return TCL_ERROR;
1426    }
1427
1428    result = CommonWriteGIF(interp, chan, format, blockPtr);
1429    if (Tcl_Close(interp, chan) == TCL_ERROR) {
1430	return TCL_ERROR;
1431    }
1432    return result;
1433}
1434
1435#define Mputc(c,handle) Tcl_Write(handle,(char *) &c,1)
1436
1437static int
1438CommonWriteGIF(interp, handle, format, blockPtr)
1439    Tcl_Interp *interp;
1440    Tcl_Channel handle;
1441    Tcl_Obj *format;
1442    Tk_PhotoImageBlock *blockPtr;
1443{
1444    int  resolution;
1445
1446    long  width,height,x;
1447    unsigned char c;
1448    unsigned int top,left;
1449
1450    top = 0;
1451    left = 0;
1452
1453    pixelSize = blockPtr->pixelSize;
1454    greenOffset = blockPtr->offset[1]-blockPtr->offset[0];
1455    blueOffset = blockPtr->offset[2]-blockPtr->offset[0];
1456    alphaOffset = blockPtr->offset[0];
1457    if (alphaOffset < blockPtr->offset[2]) {
1458	alphaOffset = blockPtr->offset[2];
1459    }
1460    if (++alphaOffset < pixelSize) {
1461	alphaOffset -= blockPtr->offset[0];
1462    } else {
1463	alphaOffset = 0;
1464    }
1465
1466    Tcl_Write(handle, (char *) (alphaOffset ? GIF89a : GIF87a), 6);
1467
1468    for (x=0 ; x<MAXCOLORMAPSIZE ; x++) {
1469	mapa[x][CM_RED] = 255;
1470	mapa[x][CM_GREEN] = 255;
1471	mapa[x][CM_BLUE] = 255;
1472    }
1473
1474
1475    width = blockPtr->width;
1476    height = blockPtr->height;
1477    pixelo = blockPtr->pixelPtr + blockPtr->offset[0];
1478    pixelPitch = blockPtr->pitch;
1479    savemap(blockPtr,mapa);
1480    if (num >= MAXCOLORMAPSIZE) {
1481	Tcl_AppendResult(interp, "too many colors", (char *) NULL);
1482	return TCL_ERROR;
1483    }
1484    if (num<2) {
1485	num = 2;
1486    }
1487    c = LSB(width);
1488    Mputc(c,handle);
1489    c = MSB(width);
1490    Mputc(c,handle);
1491    c = LSB(height);
1492    Mputc(c,handle);
1493    c = MSB(height);
1494    Mputc(c,handle);
1495
1496    resolution = 0;
1497    while (num >> resolution) {
1498	resolution++;
1499    }
1500    c = 111 + resolution * 17;
1501    Mputc(c,handle);
1502
1503    num = 1 << resolution;
1504
1505    /*
1506     * background color
1507     */
1508
1509    c = 0;
1510    Mputc(c,handle);
1511
1512    /*
1513     * zero for future expansion.
1514     */
1515
1516    Mputc(c,handle);
1517
1518    for (x=0 ; x<num ; x++) {
1519	c = mapa[x][CM_RED];
1520	Mputc(c,handle);
1521	c = mapa[x][CM_GREEN];
1522	Mputc(c,handle);
1523	c = mapa[x][CM_BLUE];
1524	Mputc(c,handle);
1525    }
1526
1527    /*
1528     * Write out extension for transparent colour index, if necessary.
1529     */
1530
1531    if (alphaOffset) {
1532	c = GIF_EXTENSION;
1533	Mputc(c, handle);
1534	Tcl_Write(handle, "\371\4\1\0\0\0", 7);
1535    }
1536
1537    c = GIF_START;
1538    Mputc(c,handle);
1539    c = LSB(top);
1540    Mputc(c,handle);
1541    c = MSB(top);
1542    Mputc(c,handle);
1543    c = LSB(left);
1544    Mputc(c,handle);
1545    c = MSB(left);
1546    Mputc(c,handle);
1547
1548    c = LSB(width);
1549    Mputc(c,handle);
1550    c = MSB(width);
1551    Mputc(c,handle);
1552
1553    c = LSB(height);
1554    Mputc(c,handle);
1555    c = MSB(height);
1556    Mputc(c,handle);
1557
1558    c = 0;
1559    Mputc(c,handle);
1560    c = resolution;
1561    Mputc(c,handle);
1562
1563    ssize = rsize = blockPtr->width;
1564    csize = blockPtr->height;
1565    compress(resolution+1, handle, ReadValue);
1566
1567    c = 0;
1568    Mputc(c,handle);
1569    c = GIF_TERMINATOR;
1570    Mputc(c,handle);
1571
1572    return TCL_OK;
1573}
1574
1575static int
1576color(red, green, blue, mapa)
1577    int red;
1578    int green;
1579    int blue;
1580    unsigned char mapa[MAXCOLORMAPSIZE][3];
1581{
1582    int x;
1583    for (x=(alphaOffset != 0) ; x<=MAXCOLORMAPSIZE ; x++) {
1584	if ((mapa[x][CM_RED] == red) && (mapa[x][CM_GREEN] == green) &&
1585		(mapa[x][CM_BLUE] == blue)) {
1586	    return x;
1587	}
1588    }
1589    return -1;
1590}
1591
1592
1593static int
1594nuevo(red, green, blue, mapa)
1595    int red,green,blue;
1596    unsigned char mapa[MAXCOLORMAPSIZE][3];
1597{
1598    int x = (alphaOffset != 0);
1599    for (; x<=num ; x++) {
1600	if ((mapa[x][CM_RED] == red) && (mapa[x][CM_GREEN] == green) &&
1601		(mapa[x][CM_BLUE] == blue)) {
1602	    return 0;
1603	}
1604    }
1605    return 1;
1606}
1607
1608static void
1609savemap(blockPtr,mapa)
1610    Tk_PhotoImageBlock *blockPtr;
1611    unsigned char mapa[MAXCOLORMAPSIZE][3];
1612{
1613    unsigned char *colores;
1614    int x,y;
1615    unsigned char red,green,blue;
1616
1617    if (alphaOffset) {
1618	num = 0;
1619	mapa[0][CM_RED] = 0xd9;
1620	mapa[0][CM_GREEN] = 0xd9;
1621	mapa[0][CM_BLUE] = 0xd9;
1622    } else {
1623	num = -1;
1624    }
1625
1626    for(y=0 ; y<blockPtr->height ; y++) {
1627	colores = blockPtr->pixelPtr + blockPtr->offset[0]
1628		+ y * blockPtr->pitch;
1629	for(x=0 ; x<blockPtr->width ; x++) {
1630	    if (!alphaOffset || (colores[alphaOffset] != 0)) {
1631		red = colores[0];
1632		green = colores[greenOffset];
1633		blue = colores[blueOffset];
1634		if (nuevo(red,green,blue,mapa)) {
1635		    num++;
1636		    if (num >= MAXCOLORMAPSIZE) {
1637			return;
1638		    }
1639		    mapa[num][CM_RED] = red;
1640		    mapa[num][CM_GREEN] = green;
1641		    mapa[num][CM_BLUE] = blue;
1642		}
1643	    }
1644	    colores += pixelSize;
1645	}
1646    }
1647    return;
1648}
1649
1650static int
1651ReadValue()
1652{
1653    unsigned int col;
1654
1655    if (csize == 0) {
1656	return EOF;
1657    }
1658    if (alphaOffset && (pixelo[alphaOffset] == 0)) {
1659	col = 0;
1660    } else {
1661	col = color(pixelo[0], pixelo[greenOffset], pixelo[blueOffset], mapa);
1662    }
1663    pixelo += pixelSize;
1664    if (--ssize <= 0) {
1665	ssize = rsize;
1666	csize--;
1667	pixelo += pixelPitch - (rsize * pixelSize);
1668    }
1669
1670    return col;
1671}
1672
1673
1674
1675/*
1676 *-----------------------------------------------------------------------
1677 *
1678 * miGIF Compression - mouse and ivo's GIF-compatible compression
1679 *
1680 *		-run length encoding compression routines-
1681 *
1682 * Copyright (C) 1998 Hutchison Avenue Software Corporation
1683 *		 http://www.hasc.com
1684 *		 info@hasc.com
1685 *
1686 * Permission to use, copy, modify, and distribute this software and
1687 * its documentation for any purpose and without fee is hereby
1688 * granted, provided that the above copyright notice appear in all
1689 * copies and that both that copyright notice and this permission
1690 * notice appear in supporting documentation.  This software is
1691 * provided "AS IS." The Hutchison Avenue Software Corporation
1692 * disclaims all warranties, either express or implied, including but
1693 * not limited to implied warranties of merchantability and fitness
1694 * for a particular purpose, with respect to this code and
1695 * accompanying documentation.
1696 *
1697 * The miGIF compression routines do not, strictly speaking, generate
1698 * files conforming to the GIF spec, since the image data is not
1699 * LZW-compressed (this is the point: in order to avoid transgression
1700 * of the Unisys patent on the LZW algorithm.)  However, miGIF
1701 * generates data streams that any reasonably sane LZW decompresser
1702 * will decompress to what we want.
1703 *
1704 * miGIF compression uses run length encoding. It compresses
1705 * horizontal runs of pixels of the same color. This type of
1706 * compression gives good results on images with many runs, for
1707 * example images with lines, text and solid shapes on a solid-colored
1708 * background. It gives little or no compression on images with few
1709 * runs, for example digital or scanned photos.
1710 *
1711 *				 der Mouse
1712 *			mouse@rodents.montreal.qc.ca
1713 *	      7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B
1714 *
1715 *			       ivo@hasc.com
1716 *
1717 * The Graphics Interchange Format(c) is the Copyright property of
1718 * CompuServe Incorporated.  GIF(sm) is a Service Mark property of
1719 * CompuServe Incorporated.
1720 *
1721 *-----------------------------------------------------------------------
1722 */
1723
1724static int rl_pixel;
1725static int rl_basecode;
1726static int rl_count;
1727static int rl_table_pixel;
1728static int rl_table_max;
1729static int just_cleared;
1730static int out_bits;
1731static int out_bits_init;
1732static int out_count;
1733static int out_bump;
1734static int out_bump_init;
1735static int out_clear;
1736static int out_clear_init;
1737static int max_ocodes;
1738static int code_clear;
1739static int code_eof;
1740static unsigned int obuf;
1741static int obits;
1742static Tcl_Channel ofile;
1743static unsigned char oblock[256];
1744static int oblen;
1745
1746/*
1747 * Used only when debugging GIF compression code
1748 */
1749/* #define MIGIF_DEBUGGING_ENVARS */
1750
1751#ifdef MIGIF_DEBUGGING_ENVARS
1752
1753static int verbose_set = 0;
1754static int verbose;
1755#define MIGIF_VERBOSE (verbose_set?verbose:set_verbose())
1756#define DEBUGMSG(printf_args) if (MIGIF_VERBOSE) { printf printf_args; }
1757
1758static int
1759set_verbose(void)
1760{
1761    verbose = !!getenv("MIGIF_VERBOSE");
1762    verbose_set = 1;
1763    return verbose;
1764}
1765
1766static CONST char *
1767binformat(v, nbits)
1768    unsigned int v;
1769    int nbits;
1770{
1771    static char bufs[8][64];
1772    static int bhand = 0;
1773    unsigned int bit;
1774    int bno;
1775    char *bp;
1776
1777    bhand--;
1778    if (bhand < 0) {
1779	bhand = (sizeof(bufs) / sizeof(bufs[0])) - 1;
1780    }
1781    bp = &bufs[bhand][0];
1782    for (bno=nbits-1,bit=((unsigned int)1)<<bno ; bno>=0 ; bno--,bit>>=1) {
1783	*bp++ = (v & bit) ? '1' : '0';
1784	if (((bno&3) == 0) && (bno != 0)) {
1785	    *bp++ = '.';
1786	}
1787    }
1788    *bp = '\0';
1789    return &bufs[bhand][0];
1790}
1791
1792#else
1793
1794#define MIGIF_VERBOSE 0
1795#define DEBUGMSG(printf_args) /* do nothing */
1796
1797#endif
1798
1799static void
1800write_block()
1801{
1802    int i;
1803    unsigned char c;
1804
1805    if (MIGIF_VERBOSE) {
1806	printf("write_block %d:", oblen);
1807	for (i=0 ; i<oblen ; i++) {
1808	    printf(" %02x", oblock[i]);
1809	}
1810	printf("\n");
1811    }
1812    c = oblen;
1813    Tcl_Write(ofile, (char *) &c, 1);
1814    Tcl_Write(ofile, (char *) &oblock[0], oblen);
1815    oblen = 0;
1816}
1817
1818static void
1819block_out(c)
1820    unsigned char c;
1821{
1822    DEBUGMSG(("block_out %s\n", binformat(c, 8)));
1823    oblock[oblen++] = c;
1824    if (oblen >= 255) {
1825	write_block();
1826    }
1827}
1828
1829static void
1830block_flush()
1831{
1832    DEBUGMSG(("block_flush\n"));
1833    if (oblen > 0) {
1834	write_block();
1835    }
1836}
1837
1838static void
1839output(val)
1840    int val;
1841{
1842    DEBUGMSG(("output %s [%s %d %d]\n", binformat(val, out_bits),
1843	    binformat(obuf, obits), obits, out_bits));
1844    obuf |= val << obits;
1845    obits += out_bits;
1846    while (obits >= 8) {
1847	block_out(UCHAR(obuf&0xff));
1848	obuf >>= 8;
1849	obits -= 8;
1850    }
1851    DEBUGMSG(("output leaving [%s %d]\n", binformat(obuf, obits), obits));
1852}
1853
1854static void
1855output_flush()
1856{
1857    DEBUGMSG(("output_flush\n"));
1858    if (obits > 0) {
1859	block_out(UCHAR(obuf));
1860    }
1861    block_flush();
1862}
1863
1864static void
1865did_clear()
1866{
1867    DEBUGMSG(("did_clear\n"));
1868    out_bits = out_bits_init;
1869    out_bump = out_bump_init;
1870    out_clear = out_clear_init;
1871    out_count = 0;
1872    rl_table_max = 0;
1873    just_cleared = 1;
1874}
1875
1876static void
1877output_plain(c)
1878    int c;
1879{
1880    DEBUGMSG(("output_plain %s\n", binformat(c, out_bits)));
1881    just_cleared = 0;
1882    output(c);
1883    out_count++;
1884    if (out_count >= out_bump) {
1885	out_bits++;
1886	out_bump += 1 << (out_bits - 1);
1887    }
1888    if (out_count >= out_clear) {
1889	output(code_clear);
1890	did_clear();
1891    }
1892}
1893
1894static unsigned int
1895isqrt(x)
1896    unsigned int x;
1897{
1898    unsigned int r;
1899    unsigned int v;
1900
1901    if (x < 2) {
1902	return x;
1903    }
1904    for (v=x,r=1 ; v ; v>>=2,r<<=1);
1905    while (1) {
1906	v = ((x / r) + r) / 2;
1907	if (v==r || v==r+1) {
1908	    return r;
1909	}
1910	r = v;
1911    }
1912}
1913
1914static unsigned int
1915compute_triangle_count(count, nrepcodes)
1916    unsigned int count;
1917    unsigned int nrepcodes;
1918{
1919    unsigned int perrep;
1920    unsigned int cost;
1921
1922    cost = 0;
1923    perrep = (nrepcodes * (nrepcodes+1)) / 2;
1924    while (count >= perrep) {
1925	cost += nrepcodes;
1926	count -= perrep;
1927    }
1928    if (count > 0) {
1929	unsigned int n;
1930	n = isqrt(count);
1931	while (n*(n+1) >= 2*count) {
1932	    n--;
1933	}
1934	while (n*(n+1) < 2*count) {
1935	    n++;
1936	}
1937	cost += n;
1938    }
1939    return cost;
1940}
1941
1942static void
1943max_out_clear()
1944{
1945    out_clear = max_ocodes;
1946}
1947
1948static void
1949reset_out_clear()
1950{
1951    out_clear = out_clear_init;
1952    if (out_count >= out_clear) {
1953	output(code_clear);
1954	did_clear();
1955    }
1956}
1957
1958static void
1959rl_flush_fromclear(count)
1960    int count;
1961{
1962    int n;
1963
1964    DEBUGMSG(("rl_flush_fromclear %d\n", count));
1965    max_out_clear();
1966    rl_table_pixel = rl_pixel;
1967    n = 1;
1968    while (count > 0) {
1969	if (n == 1) {
1970	    rl_table_max = 1;
1971	    output_plain(rl_pixel);
1972	    count--;
1973	} else if (count >= n) {
1974	    rl_table_max = n;
1975	    output_plain(rl_basecode+n-2);
1976	    count -= n;
1977	} else if (count == 1) {
1978	    rl_table_max++;
1979	    output_plain(rl_pixel);
1980	    count = 0;
1981	} else {
1982	    rl_table_max++;
1983	    output_plain(rl_basecode+count-2);
1984	    count = 0;
1985	}
1986	if (out_count == 0) {
1987	    n = 1;
1988	} else {
1989	    n++;
1990	}
1991    }
1992    reset_out_clear();
1993    DEBUGMSG(("rl_flush_fromclear leaving table_max=%d\n", rl_table_max));
1994}
1995
1996static void
1997rl_flush_clearorrep(count)
1998    int count;
1999{
2000    int withclr;
2001
2002    DEBUGMSG(("rl_flush_clearorrep %d\n", count));
2003    withclr = 1 + compute_triangle_count(count, max_ocodes);
2004    if (withclr < count) {
2005	output(code_clear);
2006	did_clear();
2007	rl_flush_fromclear(count);
2008    } else {
2009	for (; count>0 ; count--) {
2010	    output_plain(rl_pixel);
2011	}
2012    }
2013}
2014
2015static void
2016rl_flush_withtable(count)
2017    int count;
2018{
2019    int repmax;
2020    int repleft;
2021    int leftover;
2022
2023    DEBUGMSG(("rl_flush_withtable %d\n", count));
2024    repmax = count / rl_table_max;
2025    leftover = count % rl_table_max;
2026    repleft = (leftover ? 1 : 0);
2027    if (out_count+repmax+repleft > max_ocodes) {
2028	repmax = max_ocodes - out_count;
2029	leftover = count - (repmax * rl_table_max);
2030	repleft = 1 + compute_triangle_count(leftover, max_ocodes);
2031    }
2032    DEBUGMSG(("rl_flush_withtable repmax=%d leftover=%d repleft=%d\n",
2033	    repmax, leftover, repleft));
2034    if (1+(int)compute_triangle_count(count, max_ocodes) < repmax+repleft) {
2035	output(code_clear);
2036	did_clear();
2037	rl_flush_fromclear(count);
2038	return;
2039    }
2040    max_out_clear();
2041    for (; repmax>0 ; repmax--) {
2042	output_plain(rl_basecode + rl_table_max - 2);
2043    }
2044    if (leftover) {
2045	if (just_cleared) {
2046	    rl_flush_fromclear(leftover);
2047	} else if (leftover == 1) {
2048	    output_plain(rl_pixel);
2049	} else {
2050	    output_plain(rl_basecode + leftover - 2);
2051	}
2052    }
2053    reset_out_clear();
2054}
2055
2056static void
2057rl_flush()
2058{
2059    DEBUGMSG(("rl_flush [ %d %d\n", rl_count, rl_pixel));
2060    if (rl_count == 1) {
2061	output_plain(rl_pixel);
2062	rl_count = 0;
2063	DEBUGMSG(("rl_flush ]\n"));
2064	return;
2065    }
2066    if (just_cleared) {
2067	rl_flush_fromclear(rl_count);
2068    } else if ((rl_table_max < 2) || (rl_table_pixel != rl_pixel)) {
2069	rl_flush_clearorrep(rl_count);
2070    } else {
2071	rl_flush_withtable(rl_count);
2072    }
2073    DEBUGMSG(("rl_flush ]\n"));
2074    rl_count = 0;
2075}
2076
2077
2078static void
2079compress(init_bits, handle, readValue)
2080    int init_bits;
2081    Tcl_Channel handle;
2082    ifunptr readValue;
2083{
2084    int c;
2085
2086    ofile = handle;
2087    obuf = 0;
2088    obits = 0;
2089    oblen = 0;
2090    code_clear = 1 << (init_bits - 1);
2091    code_eof = code_clear + 1;
2092    rl_basecode = code_eof + 1;
2093    out_bump_init = (1 << (init_bits - 1)) - 1;
2094    /*
2095     * For images with a lot of runs, making out_clear_init larger
2096     * will give better compression.
2097     */
2098    out_clear_init = (init_bits <= 3) ? 9 : (out_bump_init-1);
2099#ifdef MIGIF_DEBUGGING_ENVARS
2100    {
2101	const char *ocienv;
2102	ocienv = getenv("MIGIF_OUT_CLEAR_INIT");
2103	if (ocienv) {
2104	    out_clear_init = atoi(ocienv);
2105	    DEBUGMSG(("[overriding out_clear_init to %d]\n", out_clear_init));
2106	}
2107    }
2108#endif
2109    out_bits_init = init_bits;
2110    max_ocodes = (1 << GIFBITS) - ((1 << (out_bits_init - 1)) + 3);
2111    did_clear();
2112    output(code_clear);
2113    rl_count = 0;
2114    while (1) {
2115	c = readValue();
2116	if ((rl_count > 0) && (c != rl_pixel)) {
2117	    rl_flush();
2118	}
2119	if (c == EOF) {
2120	    break;
2121	}
2122	if (rl_pixel == c) {
2123	    rl_count++;
2124	} else {
2125	    rl_pixel = c;
2126	    rl_count = 1;
2127	}
2128    }
2129    output(code_eof);
2130    output_flush();
2131}
2132
2133/*
2134 *-----------------------------------------------------------------------
2135 *
2136 * End of miGIF section  - See copyright notice at start of section.
2137 *
2138 *-----------------------------------------------------------------------
2139 */
2140