1 /*
2 * gif.c --
3 *
4 * GIF photo image type, Tcl/Tk package
5 *
6 * A photo image file handler for GIF files. Reads 87a and 89a GIF
7 * files. At present, there only is a file write function. GIF images may be
8 * read using the -data option of the photo image. The data may be
9 * given as a binary string in a Tcl_Obj or by representing
10 * the data as BASE64 encoded ascii. Derived from the giftoppm code
11 * found in the pbmplus package and tkImgFmtPPM.c in the tk4.0b2
12 * distribution.
13 *
14 * Copyright (c) 2002 Andreas Kupries <andreas_kupries@users.sourceforge.net>
15 * Copyright (c) 1997-2003 Jan Nijtmans <nijtmans@users.sourceforge.net>
16 *
17 * Copyright (c) Reed Wade (wade@cs.utk.edu), University of Tennessee
18 * Copyright (c) 1995-1997 Sun Microsystems, Inc.
19 * Copyright (c) 1997 Australian National University
20 *
21 * See the file "license.terms" for information on usage and redistribution
22 * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
23 *
24 * This file also contains code from the giftoppm program, which is
25 * copyrighted as follows:
26 *
27 * +-------------------------------------------------------------------+
28 * | Copyright 1990, David Koblas. |
29 * | Permission to use, copy, modify, and distribute this software |
30 * | and its documentation for any purpose and without fee is hereby |
31 * | granted, provided that the above copyright notice appear in all |
32 * | copies and that both that copyright notice and this permission |
33 * | notice appear in supporting documentation. This software is |
34 * | provided "as is" without express or implied warranty. |
35 * +-------------------------------------------------------------------+
36 *
37 */
38
39 /*
40 * Generic initialization code, parameterized via CPACKAGE and PACKAGE.
41 */
42
43 #include "init.c"
44
45 /*
46 * GIF's are represented as data in either binary or base64 format. base64
47 * strings consist of 4 6-bit characters -> 3 8 bit bytes. A-Z, a-z, 0-9, +
48 * and / represent the 64 values (in order). '=' is a trailing padding char
49 * when the un-encoded data is not a multiple of 3 bytes. We'll ignore white
50 * space when encountered. Any other invalid character is treated as an EOF
51 */
52
53 #define GIF_SPECIAL (256)
54 #define GIF_PAD (GIF_SPECIAL+1)
55 #define GIF_SPACE (GIF_SPECIAL+2)
56 #define GIF_BAD (GIF_SPECIAL+3)
57 #define GIF_DONE (GIF_SPECIAL+4)
58
59 /*
60 * Non-ASCII encoding support:
61 * Most data in a GIF image is binary and is treated as such. However,
62 * a few key bits are stashed in ASCII. If we try to compare those pieces
63 * to the char they represent, it will fail on any non-ASCII (eg, EBCDIC)
64 * system. To accomodate these systems, we test against the numeric value
65 * of the ASCII characters instead of the characters themselves. This is
66 * encoding independant.
67 */
68
69 # define GIF87a "\x47\x49\x46\x38\x37\x61" /* ASCII GIF87a */
70 # define GIF89a "\x47\x49\x46\x38\x39\x61" /* ASCII GIF89a */
71 # define GIF_TERMINATOR 0x3b /* ASCII ; */
72 # define GIF_EXTENSION 0x21 /* ASCII ! */
73 # define GIF_START 0x2c /* ASCII , */
74
75 typedef struct {
76 unsigned char buf[280];
77 int bytes;
78 int done;
79 unsigned int window;
80 int bitsInWindow;
81 unsigned char *c;
82 tkimg_MFile handle;
83 } GIFImageConfig;
84
85 /*
86 * The format record for the GIF file format:
87 */
88
89 static int CommonRead(Tcl_Interp *interp,
90 GIFImageConfig *gifConfPtr, const char *fileName, Tcl_Obj *format,
91 Tk_PhotoHandle imageHandle, int destX, int destY,
92 int width, int height, int srcX, int srcY);
93
94 static int CommonWrite(Tcl_Interp *interp,
95 tkimg_MFile *handle, Tcl_Obj *format,
96 Tk_PhotoImageBlock *blockPtr);
97
98 #define INTERLACE 0x40
99 #define LOCALCOLORMAP 0x80
100 #define BitSet(byte, bit) (((byte) & (bit)) == (bit))
101 #define MAXCOLORMAPSIZE 256
102 #define CM_RED 0
103 #define CM_GREEN 1
104 #define CM_BLUE 2
105 #define CM_ALPHA 3
106 #define MAX_LWZ_BITS 12
107 #define LM_to_uint(a,b) (((b)<<8)|(a))
108
109 #define ReadOK(handle,buf,len) (tkimg_Read2(handle, (char *)(buf), len) == len)
110
111 /*
112 * Prototypes for local procedures defined in this file:
113 */
114
115 static int DoExtension(GIFImageConfig *gifConfPtr, int label, int *transparent);
116
117 static int GetCode(GIFImageConfig *gifConfPtr, int code_size, int flag);
118
119 static int GetDataBlock(GIFImageConfig *gifConfPtr, unsigned char *buf);
120
121 static int ReadColorMap(GIFImageConfig *gifConfPtr, int number,
122 unsigned char buffer[MAXCOLORMAPSIZE][4]);
123
124 static int ReadGIFHeader(GIFImageConfig *gifConfPtr, int *widthPtr, int *heightPtr);
125
126 static int ReadImage(Tcl_Interp *interp,
127 char *imagePtr, GIFImageConfig *gifConfPtr, int len, int rows,
128 unsigned char cmap[MAXCOLORMAPSIZE][4],
129 int width, int height, int srcX, int srcY,
130 int interlace, int transparent);
131
132 /*
133 *----------------------------------------------------------------------
134 *
135 * ChnMatch --
136 *
137 * This procedure is invoked by the photo image type to see if
138 * a channel contains image data in GIF format.
139 *
140 * Results:
141 * The return value is 1 if the first characters in channel chan
142 * look like GIF data, and 0 otherwise.
143 *
144 * Side effects:
145 * The access position in f may change.
146 *
147 *----------------------------------------------------------------------
148 */
149
150 static int
ChnMatch(Tcl_Channel chan,const char * fileName,Tcl_Obj * format,int * widthPtr,int * heightPtr,Tcl_Interp * interp)151 ChnMatch(
152 Tcl_Channel chan, /* The image channel, open for reading. */
153 const char *fileName, /* The name of the image file. */
154 Tcl_Obj *format, /* User-specified format object, or NULL. */
155 int *widthPtr, /* The dimensions of the image are */
156 int *heightPtr, /* returned here if the file is a valid raw GIF file. */
157 Tcl_Interp *interp /* interpreter */
158 ) {
159 GIFImageConfig gifConf;
160
161 memset(&gifConf, 0, sizeof(GIFImageConfig));
162
163 gifConf.handle.data = (char *) chan;
164 gifConf.handle.state = IMG_CHAN;
165
166 return ReadGIFHeader(&gifConf, widthPtr, heightPtr);
167 }
168
169 /*
170 *----------------------------------------------------------------------
171 *
172 * ChnRead --
173 *
174 * This procedure is called by the photo image type to read
175 * GIF format data from a channel and write it into a given
176 * photo image.
177 *
178 * Results:
179 * A standard TCL completion code. If TCL_ERROR is returned
180 * then an error message is left in the interp's result.
181 *
182 * Side effects:
183 * The access position in channel chan is changed, and new data is
184 * added to the image given by imageHandle.
185 *
186 *----------------------------------------------------------------------
187 */
188
189 static int
ChnRead(Tcl_Interp * interp,Tcl_Channel chan,const char * fileName,Tcl_Obj * format,Tk_PhotoHandle imageHandle,int destX,int destY,int width,int height,int srcX,int srcY)190 ChnRead(
191 Tcl_Interp *interp, /* Interpreter to use for reporting errors. */
192 Tcl_Channel chan, /* The image channel, open for reading. */
193 const char *fileName, /* The name of the image file. */
194 Tcl_Obj *format, /* User-specified format object, or NULL. */
195 Tk_PhotoHandle imageHandle, /* The photo image to write into. */
196 int destX, int destY, /* Coordinates of top-left pixel in
197 * photo image to be written to. */
198 int width, int height, /* Dimensions of block of photo image to
199 * be written to. */
200 int srcX, int srcY /* Coordinates of top-left pixel to be used
201 * in image being read. */
202 ) {
203 GIFImageConfig gifConf;
204
205 memset(&gifConf, 0, sizeof(GIFImageConfig));
206
207 gifConf.handle.data = (char *) chan;
208 gifConf.handle.state = IMG_CHAN;
209
210 return CommonRead(interp, &gifConf, fileName, format,
211 imageHandle, destX, destY, width, height, srcX, srcY);
212 }
213
214 /*
215 *----------------------------------------------------------------------
216 *
217 * CommonRead --
218 *
219 * This procedure is called by the photo image type to read
220 * GIF format data from a file and write it into a given
221 * photo image.
222 *
223 * Results:
224 * A standard TCL completion code. If TCL_ERROR is returned
225 * then an error message is left in the interp's result.
226 *
227 * Side effects:
228 * The access position in file f is changed, and new data is
229 * added to the image given by imageHandle.
230 *
231 *----------------------------------------------------------------------
232 */
233
234 static int
CommonRead(Tcl_Interp * interp,GIFImageConfig * gifConfPtr,const char * fileName,Tcl_Obj * format,Tk_PhotoHandle imageHandle,int destX,int destY,int width,int height,int srcX,int srcY)235 CommonRead(
236 Tcl_Interp *interp, /* Interpreter to use for reporting errors. */
237 GIFImageConfig *gifConfPtr, /* The image file, open for reading. */
238 const char *fileName, /* The name of the image file. */
239 Tcl_Obj *format, /* User-specified format object, or NULL. */
240 Tk_PhotoHandle imageHandle, /* The photo image to write into. */
241 int destX, int destY, /* Coordinates of top-left pixel in
242 * photo image to be written to. */
243 int width, int height, /* Dimensions of block of photo image to
244 * be written to. */
245 int srcX, int srcY /* Coordinates of top-left pixel to be used
246 * in image being read. */
247 ) {
248 int fileWidth, fileHeight, imageWidth, imageHeight;
249 int nBytes, index = 0, objc = 0;
250 Tcl_Obj **objv = NULL;
251 Tk_PhotoImageBlock block;
252 unsigned char buf[100];
253 char *trashBuffer = NULL;
254 unsigned char *pixBuf = NULL;
255 int bitPixel;
256 unsigned char colorMap[MAXCOLORMAPSIZE][4];
257 int transparent = -1;
258
259 if (tkimg_ListObjGetElements(interp, format, &objc, &objv) != TCL_OK) {
260 return TCL_ERROR;
261 }
262 if (objc > 1) {
263 char *c = Tcl_GetStringFromObj(objv[1], &nBytes);
264 if ((objc > 3) || ((objc == 3) && ((c[0] != '-') ||
265 (c[1] != 'i') || strncmp(c, "-index", strlen(c))))) {
266 Tcl_AppendResult(interp, "invalid format: \"",
267 tkimg_GetStringFromObj2(format, NULL), "\"", (char *) NULL);
268 return TCL_ERROR;
269 }
270 if (Tcl_GetIntFromObj(interp, objv[objc-1], &index) != TCL_OK) {
271 return TCL_ERROR;
272 }
273 }
274
275 if (!ReadGIFHeader(gifConfPtr, &fileWidth, &fileHeight)) {
276 Tcl_AppendResult(interp, "couldn't read GIF header from file \"", fileName, "\"", NULL);
277 return TCL_ERROR;
278 }
279 if ((fileWidth <= 0) || (fileHeight <= 0)) {
280 Tcl_AppendResult(interp, "GIF image file \"", fileName,
281 "\" has dimension(s) <= 0", (char *) NULL);
282 return TCL_ERROR;
283 }
284
285 if (tkimg_Read2(&gifConfPtr->handle, (char *)buf, 3) != 3) {
286 return TCL_OK;
287 }
288
289 bitPixel = 2<<(buf[0]&0x07);
290
291 if (BitSet(buf[0], LOCALCOLORMAP)) { /* Global Colormap */
292 if (!ReadColorMap(gifConfPtr, bitPixel, colorMap)) {
293 Tcl_AppendResult(interp, "error reading color map", (char *) NULL);
294 return TCL_ERROR;
295 }
296 }
297
298 if ((srcX + width) > fileWidth) {
299 width = fileWidth - srcX;
300 }
301 if ((srcY + height) > fileHeight) {
302 height = fileHeight - srcY;
303 }
304 if ((width <= 0) || (height <= 0) || (srcX >= fileWidth) || (srcY >= fileHeight)) {
305 return TCL_OK;
306 }
307
308 if (tkimg_PhotoExpand(interp, imageHandle, destX + width, destY + height) == TCL_ERROR) {
309 return TCL_ERROR;;
310 }
311
312 block.pixelSize = 4;
313 block.offset[0] = 0;
314 block.offset[1] = 1;
315 block.offset[2] = 2;
316 block.offset[3] = 3;
317 block.pixelPtr = NULL;
318
319 while (1) {
320 if (tkimg_Read2(&gifConfPtr->handle, (char *)buf, 1) != 1) {
321 /*
322 * Premature end of image. We should really notify
323 * the user, but for now just show garbage.
324 */
325 break;
326 }
327
328 if (buf[0] == GIF_TERMINATOR) {
329 /*
330 * GIF terminator.
331 */
332 Tcl_AppendResult(interp,"no image data for this index", (char *) NULL);
333 goto error;
334 }
335
336 if (buf[0] == GIF_EXTENSION) {
337 /*
338 * This is a GIF extension.
339 */
340
341 if (tkimg_Read2(&gifConfPtr->handle, (char *)buf, 1) != 1) {
342 Tcl_AppendResult(interp,
343 "error reading extension function code in GIF image",
344 (char *) NULL);
345 goto error;
346 }
347 if (DoExtension(gifConfPtr, buf[0], &transparent) < 0) {
348 Tcl_AppendResult(interp, "error reading extension in GIF image", (char *) NULL);
349 goto error;
350 }
351 continue;
352 }
353
354 if (buf[0] != GIF_START) {
355 /*
356 * Not a valid start character; ignore it.
357 */
358 continue;
359 }
360
361 if (tkimg_Read2(&gifConfPtr->handle, (char *)buf, 9) != 9) {
362 Tcl_AppendResult(interp,
363 "couldn't read left/top/width/height in GIF image",
364 (char *) NULL);
365 goto error;
366 }
367
368 imageWidth = LM_to_uint(buf[4],buf[5]);
369 imageHeight = LM_to_uint(buf[6],buf[7]);
370
371 bitPixel = 2<<(buf[8]&0x07);
372
373 if (index--) {
374 /* this is not the image we want to read: skip it. */
375 if (BitSet(buf[8], LOCALCOLORMAP)) {
376 if (!ReadColorMap(gifConfPtr, bitPixel, colorMap)) {
377 Tcl_AppendResult(interp,
378 "error reading color map", (char *) NULL);
379 goto error;
380 }
381 }
382
383 /* If we've not yet allocated a trash buffer, do so now */
384 if (trashBuffer == NULL) {
385 nBytes = fileWidth * fileHeight * 3;
386 trashBuffer = (char *) ckalloc((unsigned int) nBytes);
387 }
388
389 /*
390 * Slurp! Process the data for this image and stuff it in a
391 * trash buffer.
392 *
393 * Yes, it might be more efficient here to *not* store the data
394 * (we're just going to throw it away later). However, I elected
395 * to implement it this way for good reasons. First, I wanted to
396 * avoid duplicating the (fairly complex) LWZ decoder in ReadImage.
397 * Fine, you say, why didn't you just modify it to allow the use of
398 * a NULL specifier for the output buffer? I tried that, but it
399 * negatively impacted the performance of what I think will be the
400 * common case: reading the first image in the file. Rather than
401 * marginally improve the speed of the less frequent case, I chose
402 * to maintain high performance for the common case.
403 */
404 if (ReadImage(interp, trashBuffer, gifConfPtr, imageWidth,
405 imageHeight, colorMap, 0, 0, 0, 0, 0, -1) != TCL_OK) {
406 goto error;
407 }
408 continue;
409 }
410
411 /* If a trash buffer has been allocated, free it now */
412 if (trashBuffer != NULL) {
413 ckfree((char *)trashBuffer);
414 trashBuffer = NULL;
415 }
416 if (BitSet(buf[8], LOCALCOLORMAP)) {
417 if (!ReadColorMap(gifConfPtr, bitPixel, colorMap)) {
418 Tcl_AppendResult(interp, "error reading color map", (char *) NULL);
419 goto error;
420 }
421 }
422
423 index = LM_to_uint(buf[0],buf[1]);
424 srcX -= index;
425 if (srcX<0) {
426 destX -= srcX; width += srcX;
427 srcX = 0;
428 }
429
430 if (width > imageWidth) {
431 width = imageWidth;
432 }
433
434 index = LM_to_uint(buf[2],buf[3]);
435 srcY -= index;
436 if (index > srcY) {
437 destY -= srcY; height += srcY;
438 srcY = 0;
439 }
440 if (height > imageHeight) {
441 height = imageHeight;
442 }
443
444 if ((width <= 0) || (height <= 0)) {
445 block.pixelPtr = 0;
446 goto noerror;
447 }
448
449 block.width = width;
450 block.height = height;
451 block.pixelSize = (transparent>=0)? 4: 3;
452 block.pitch = block.pixelSize * imageWidth;
453 nBytes = block.pitch * imageHeight;
454 pixBuf = (unsigned char *) ckalloc((unsigned) nBytes);
455 block.pixelPtr = pixBuf;
456
457 if (ReadImage(interp, (char *) block.pixelPtr, gifConfPtr, imageWidth, imageHeight,
458 colorMap, fileWidth, fileHeight, srcX, srcY,
459 BitSet(buf[8], INTERLACE), transparent) != TCL_OK) {
460 goto error;
461 }
462 break;
463 }
464
465 block.pixelPtr = pixBuf + srcY * block.pitch + srcX * block.pixelSize;
466 if (tkimg_PhotoPutBlock(interp, imageHandle, &block, destX, destY, width, height,
467 (transparent == -1)? TK_PHOTO_COMPOSITE_SET: TK_PHOTO_COMPOSITE_OVERLAY) == TCL_ERROR) {
468 goto error;
469 }
470
471 noerror:
472 if (pixBuf) {
473 ckfree((char *) pixBuf);
474 }
475 return TCL_OK;
476
477 error:
478 if (pixBuf) {
479 ckfree((char *) pixBuf);
480 }
481 return TCL_ERROR;
482 }
483
484 /*
485 *----------------------------------------------------------------------
486 *
487 * ObjMatch --
488 *
489 * This procedure is invoked by the photo image type to see if
490 * an object contains image data in GIF format.
491 *
492 * Results:
493 * The return value is 1 if the first characters in the object are
494 * like GIF data, and 0 otherwise.
495 *
496 * Side effects:
497 * the size of the image is placed in widthPtr and heightPtr.
498 *
499 *----------------------------------------------------------------------
500 */
501
502 static int
ObjMatch(Tcl_Obj * data,Tcl_Obj * format,int * widthPtr,int * heightPtr,Tcl_Interp * interp)503 ObjMatch(
504 Tcl_Obj *data, /* the object containing the image data */
505 Tcl_Obj *format, /* the image format object */
506 int *widthPtr, /* where to put the image width */
507 int *heightPtr, /* where to put the image height */
508 Tcl_Interp *interp /* interpreter */
509 ) {
510 GIFImageConfig gifConf;
511
512 memset(&gifConf, 0, sizeof(GIFImageConfig));
513
514 if (!tkimg_ReadInit(data, 'G', &gifConf.handle)) {
515 return 0;
516 }
517 return ReadGIFHeader(&gifConf, widthPtr, heightPtr);
518 }
519
520 /*
521 *----------------------------------------------------------------------
522 *
523 * ObjRead --
524 *
525 * This procedure is called by the photo image type to read
526 * GIF format data from a base64 encoded string, and give it to
527 * the photo image.
528 *
529 * Results:
530 * A standard TCL completion code. If TCL_ERROR is returned
531 * then an error message is left in the interp's result.
532 *
533 * Side effects:
534 * new data is added to the image given by imageHandle. This
535 * procedure calls FileReadGif by redefining the operation of
536 * fprintf temporarily.
537 *
538 *----------------------------------------------------------------------
539 */
540
541 static int
ObjRead(Tcl_Interp * interp,Tcl_Obj * data,Tcl_Obj * format,Tk_PhotoHandle imageHandle,int destX,int destY,int width,int height,int srcX,int srcY)542 ObjRead(
543 Tcl_Interp *interp, /* interpreter for reporting errors in */
544 Tcl_Obj *data, /* object containing the image */
545 Tcl_Obj *format, /* format object if any */
546 Tk_PhotoHandle imageHandle, /* the image to write this data into */
547 int destX, int destY, /* The rectangular region of the */
548 int width, int height, /* image to copy */
549 int srcX, int srcY
550 ) {
551 GIFImageConfig gifConf;
552
553 memset(&gifConf, 0, sizeof(GIFImageConfig));
554
555 tkimg_ReadInit(data, 'G', &gifConf.handle);
556 return CommonRead(interp, &gifConf, "inline data", format,
557 imageHandle, destX, destY, width, height, srcX, srcY);
558 }
559
560 /*
561 *----------------------------------------------------------------------
562 *
563 * ReadGIFHeader --
564 *
565 * This procedure reads the GIF header from the beginning of a
566 * GIF file and returns the dimensions of the image.
567 *
568 * Results:
569 * The return value is 1 if file "f" appears to start with
570 * a valid GIF header, 0 otherwise. If the header is valid,
571 * then *widthPtr and *heightPtr are modified to hold the
572 * dimensions of the image.
573 *
574 * Side effects:
575 * The access position in f advances.
576 *
577 *----------------------------------------------------------------------
578 */
579
580 static int
ReadGIFHeader(GIFImageConfig * gifConfPtr,int * widthPtr,int * heightPtr)581 ReadGIFHeader(
582 GIFImageConfig *gifConfPtr, /* Image file to read the header from */
583 int *widthPtr, int *heightPtr /* The dimensions of the image are
584 * returned here. */
585 ) {
586 unsigned char buf[7];
587
588 if ((tkimg_Read2(&gifConfPtr->handle, (char *)buf, 6) != 6)
589 || ((strncmp(GIF87a, (char *) buf, 6) != 0)
590 && (strncmp(GIF89a, (char *) buf, 6) != 0))) {
591 return 0;
592 }
593
594 if (tkimg_Read2(&gifConfPtr->handle, (char *)buf, 4) != 4) {
595 return 0;
596 }
597
598 *widthPtr = LM_to_uint(buf[0],buf[1]);
599 *heightPtr = LM_to_uint(buf[2],buf[3]);
600 return 1;
601 }
602
603 /*
604 *-----------------------------------------------------------------
605 * The code below is copied from the giftoppm program and modified
606 * just slightly.
607 *-----------------------------------------------------------------
608 */
609
610 static int
ReadColorMap(GIFImageConfig * gifConfPtr,int number,unsigned char buffer[MAXCOLORMAPSIZE][4])611 ReadColorMap(
612 GIFImageConfig *gifConfPtr,
613 int number,
614 unsigned char buffer[MAXCOLORMAPSIZE][4]
615 ) {
616 int i;
617 unsigned char rgb[3];
618
619 for (i=0; i<number; ++i) {
620 if (! ReadOK(&gifConfPtr->handle, rgb, sizeof(rgb))) {
621 return 0;
622 }
623
624 if (buffer) {
625 buffer[i][CM_RED] = rgb[0] ;
626 buffer[i][CM_GREEN] = rgb[1] ;
627 buffer[i][CM_BLUE] = rgb[2] ;
628 buffer[i][CM_ALPHA] = 255 ;
629 }
630 }
631 return 1;
632 }
633
634 static int
DoExtension(GIFImageConfig * gifConfPtr,int label,int * transparent)635 DoExtension(
636 GIFImageConfig *gifConfPtr,
637 int label,
638 int *transparent
639 ) {
640 int count;
641
642 switch (label) {
643 case 0x01: /* Plain Text Extension */
644 break;
645
646 case 0xff: /* Application Extension */
647 break;
648
649 case 0xfe: /* Comment Extension */
650 do {
651 count = GetDataBlock(gifConfPtr, (unsigned char*) gifConfPtr->buf);
652 } while (count > 0);
653 return count;
654
655 case 0xf9: /* Graphic Control Extension */
656 count = GetDataBlock(gifConfPtr, (unsigned char*) gifConfPtr->buf);
657 if (count < 0) {
658 return 1;
659 }
660 if ((gifConfPtr->buf[0] & 0x1) != 0) {
661 *transparent = gifConfPtr->buf[3];
662 }
663
664 do {
665 count = GetDataBlock(gifConfPtr, (unsigned char*) gifConfPtr->buf);
666 } while (count > 0);
667 return count;
668 }
669
670 do {
671 count = GetDataBlock(gifConfPtr, (unsigned char*) gifConfPtr->buf);
672 } while (count > 0);
673 return count;
674 }
675
676 static int
GetDataBlock(GIFImageConfig * gifConfPtr,unsigned char * buf)677 GetDataBlock(
678 GIFImageConfig *gifConfPtr,
679 unsigned char *buf
680 ) {
681 unsigned char count;
682
683 if (! ReadOK(&gifConfPtr->handle,&count,1)) {
684 return -1;
685 }
686
687 if ((count != 0) && (! ReadOK(&gifConfPtr->handle, buf, count))) {
688 return -1;
689 }
690
691 return count;
692 }
693
694
695
696 /*
697 *----------------------------------------------------------------------
698 *
699 * ReadImage --
700 *
701 * Process a GIF image from a given source, with a given height,
702 * width, transparency, etc.
703 *
704 * This code is based on the code found in the ImageMagick GIF decoder,
705 * which is (c) 2000 ImageMagick Studio.
706 *
707 * Some thoughts on our implementation:
708 * It sure would be nice if ReadImage didn't take 11 parameters! I think
709 * that if we were smarter, we could avoid doing that.
710 *
711 * Possible further optimizations: we could pull the GetCode function
712 * directly into ReadImage, which would improve our speed.
713 *
714 * Results:
715 * Processes a GIF image and loads the pixel data into a memory array.
716 *
717 * Side effects:
718 * None.
719 *
720 *----------------------------------------------------------------------
721 */
722
723 static int
ReadImage(Tcl_Interp * interp,char * imagePtr,GIFImageConfig * gifConfPtr,int len,int rows,unsigned char cmap[MAXCOLORMAPSIZE][4],int width,int height,int srcX,int srcY,int interlace,int transparent)724 ReadImage(
725 Tcl_Interp *interp,
726 char *imagePtr,
727 GIFImageConfig *gifConfPtr,
728 int len, int rows,
729 unsigned char cmap[MAXCOLORMAPSIZE][4],
730 int width, int height,
731 int srcX, int srcY,
732 int interlace,
733 int transparent
734 ) {
735 unsigned char initialCodeSize;
736 int v;
737 int xpos = 0, ypos = 0, pass = 0, i;
738 char *pixelPtr;
739 const static int interlaceStep[] = { 8, 8, 4, 2 };
740 const static int interlaceStart[] = { 0, 4, 2, 1 };
741 unsigned short prefix[(1 << MAX_LWZ_BITS)];
742 unsigned char append[(1 << MAX_LWZ_BITS)];
743 unsigned char stack[(1 << MAX_LWZ_BITS)*2];
744 unsigned char *top;
745 int codeSize, clearCode, inCode, endCode, oldCode, maxCode, code, firstCode;
746
747 /*
748 * Initialize the decoder
749 */
750 if (! ReadOK(&gifConfPtr->handle,&initialCodeSize,1)) {
751 Tcl_AppendResult(interp, "error reading GIF image: ",
752 Tcl_PosixError(interp), (char *) NULL);
753 return TCL_ERROR;
754 }
755 if (initialCodeSize > MAX_LWZ_BITS) {
756 Tcl_AppendResult(interp, "error reading GIF image: malformed image", (char *) NULL);
757 return TCL_ERROR;
758 }
759 if (transparent!=-1) {
760 cmap[transparent][CM_RED] = 0;
761 cmap[transparent][CM_GREEN] = 0;
762 cmap[transparent][CM_BLUE] = 0;
763 cmap[transparent][CM_ALPHA] = 0;
764 }
765
766 pixelPtr = imagePtr;
767
768 /* Initialize the decoder */
769 /* Set values for "special" numbers:
770 * clear code reset the decoder
771 * end code stop decoding
772 * code size size of the next code to retrieve
773 * max code next available table position
774 */
775 clearCode = 1 << (int) initialCodeSize;
776 endCode = clearCode + 1;
777 codeSize = (int) initialCodeSize + 1;
778 maxCode = clearCode + 2;
779 oldCode = -1;
780 firstCode = -1;
781
782 memset((void *)prefix, 0, (1 << MAX_LWZ_BITS) * sizeof(short));
783 memset((void *)append, 0, (1 << MAX_LWZ_BITS) * sizeof(char));
784 for (i = 0; i < clearCode; i++) {
785 append[i] = i;
786 }
787 top = stack;
788
789 GetCode(gifConfPtr, 0, 1);
790
791 /* Read until we finish the image */
792 for (i = 0, ypos = 0; i < rows; i++) {
793 for (xpos = 0; xpos < len; ) {
794 if (top == stack) {
795 /* Bummer -- our stack is empty. Now we have to work! */
796 code = GetCode(gifConfPtr, codeSize, 0);
797 if (code < 0) {
798 return TCL_OK;
799 }
800
801 if (code > maxCode || code == endCode) {
802 /*
803 * If we're doing things right, we should never
804 * receive a code that is greater than our current
805 * maximum code. If we do, bail, because our decoder
806 * does not yet have that code set up.
807 *
808 * If the code is the magic endCode value, quit.
809 */
810 return TCL_OK;
811 }
812
813 if (code == clearCode) {
814 /* Reset the decoder */
815 codeSize = initialCodeSize + 1;
816 maxCode = clearCode + 2;
817 oldCode = -1;
818 continue;
819 }
820
821 if (oldCode == -1) {
822 /*
823 * Last pass reset the decoder, so the first code we
824 * see must be a singleton. Seed the stack with it,
825 * and set up the old/first code pointers for
826 * insertion into the codes table. We can't just
827 * roll this into the clearCode test above, because
828 * at that point we have not yet read the next code.
829 */
830 *top++=append[code];
831 oldCode = code;
832 firstCode = code;
833 continue;
834 }
835
836 inCode = code;
837
838 if ((code == maxCode) && (maxCode < (1 << MAX_LWZ_BITS))) {
839 /*
840 * maxCode is always one bigger than our highest assigned
841 * code. If the code we see is equal to maxCode, then
842 * we are about to add a new entry to the codes table.
843 */
844 *top++ = firstCode;
845 code = oldCode;
846 }
847
848 while (code > clearCode) {
849 /*
850 * Populate the stack by tracing the code in the
851 * codes table from its tail to its head
852 */
853 *top++ = append[code];
854 code = prefix[code];
855 }
856 firstCode = append[code];
857
858 /* Push the head of the code onto the stack */
859 *top++ = firstCode;
860
861 if (maxCode < (1 << MAX_LWZ_BITS)) {
862 /*
863 * If there's still room in our codes table, add a new entry.
864 * Otherwise don't, and keep using the current table.
865 * See DEFERRED CLEAR CODE IN LZW COMPRESSION in the GIF89a
866 * specification.
867 */
868 prefix[maxCode] = oldCode;
869 append[maxCode] = firstCode;
870 maxCode++;
871 }
872
873 /* maxCode tells us the maximum code value we can accept.
874 * If we see that we need more bits to represent it than
875 * we are requesting from the unpacker, we need to increase
876 * the number we ask for.
877 */
878 if ((maxCode >= (1 << codeSize))
879 && (maxCode < (1<<MAX_LWZ_BITS))) {
880 codeSize++;
881 }
882 oldCode = inCode;
883 }
884
885 /* Pop the next color index off the stack */
886 v = *(--top);
887 if (v < 0) {
888 return TCL_OK;
889 }
890
891 /*
892 * If pixelPtr is null, we're skipping this image (presumably
893 * there are more in the file and we will be called to read
894 * one of them later)
895 */
896 *pixelPtr++ = cmap[v][CM_RED];
897 *pixelPtr++ = cmap[v][CM_GREEN];
898 *pixelPtr++ = cmap[v][CM_BLUE];
899 if (transparent >= 0) {
900 *pixelPtr++ = cmap[v][CM_ALPHA];
901 }
902 xpos++;
903 }
904
905 /* If interlacing, the next ypos is not just +1 */
906 if (interlace) {
907 ypos += interlaceStep[pass];
908 while (ypos >= rows) {
909 pass++;
910 if (pass > 3) {
911 return TCL_OK;
912 }
913 ypos = interlaceStart[pass];
914 }
915 } else {
916 ypos++;
917 }
918 pixelPtr = imagePtr + (ypos) * len * ((transparent>=0)?4:3);
919 }
920 return TCL_OK;
921 }
922
923 /*
924 *----------------------------------------------------------------------
925 *
926 * GetCode --
927 *
928 * Extract the next compression code from the file. In GIF's, the
929 * compression codes are between 3 and 12 bits long and are then
930 * packed into 8 bit bytes, left to right, for example:
931 * bbbaaaaa
932 * dcccccbb
933 * eeeedddd
934 * ...
935 * We use a byte buffer read from the file and a sliding window
936 * to unpack the bytes. Thanks to ImageMagick for the sliding window
937 * idea.
938 * args: handle the handle to read from
939 * code_size size of the code to extract
940 * flag boolean indicating whether the extractor
941 * should be reset or not
942 *
943 * Results:
944 * code the next compression code
945 *
946 * Side effects:
947 * May consume more input from chan.
948 *
949 *----------------------------------------------------------------------
950 */
951
952 static int
GetCode(GIFImageConfig * gifConfPtr,int code_size,int flag)953 GetCode(
954 GIFImageConfig *gifConfPtr,
955 int code_size,
956 int flag
957 ) {
958 int ret;
959
960 if (flag) {
961 /* Initialize the decoder */
962 gifConfPtr->bitsInWindow = 0;
963 gifConfPtr->bytes = 0;
964 gifConfPtr->window = 0;
965 gifConfPtr->done = 0;
966 gifConfPtr->c = NULL;
967 return 0;
968 }
969
970 while (gifConfPtr->bitsInWindow < code_size) {
971 /* Not enough bits in our window to cover the request */
972 if (gifConfPtr->done) {
973 return -1;
974 }
975 if (gifConfPtr->bytes == 0) {
976 /* Not enough bytes in our buffer to add to the window */
977 gifConfPtr->bytes = GetDataBlock(gifConfPtr, gifConfPtr->buf);
978 gifConfPtr->c = gifConfPtr->buf;
979 if (gifConfPtr->bytes <= 0) {
980 gifConfPtr->done = 1;
981 break;
982 }
983 }
984 /* Tack another byte onto the window, see if that's enough */
985 gifConfPtr->window += (*gifConfPtr->c) << gifConfPtr->bitsInWindow;
986 gifConfPtr->c++;
987 gifConfPtr->bitsInWindow += 8;
988 gifConfPtr->bytes--;
989 }
990
991 /* The next code will always be the last code_size bits of the window */
992 ret = gifConfPtr->window & ((1 << code_size) - 1);
993
994 /* Shift data in the window to put the next code at the end */
995 gifConfPtr->window >>= code_size;
996 gifConfPtr->bitsInWindow -= code_size;
997 return ret;
998 }
999
1000 /*
1001 * This software is copyrighted as noted below. It may be freely copied,
1002 * modified, and redistributed, provided that the copyright notice is
1003 * preserved on all copies.
1004 *
1005 * There is no warranty or other guarantee of fitness for this software,
1006 * it is provided solely "as is". Bug reports or fixes may be sent
1007 * to the author, who may or may not act on them as he desires.
1008 *
1009 * You may not include this software in a program or other software product
1010 * without supplying the source, or without informing the end-user that the
1011 * source is available for no extra charge.
1012 *
1013 * If you modify this software, you should include a notice giving the
1014 * name of the person performing the modification, the date of modification,
1015 * and the reason for such modification.
1016 */
1017
1018
1019 /*
1020 * ChnWrite - writes a image in GIF format.
1021 *-------------------------------------------------------------------------
1022 * Author: Lolo
1023 * Engeneering Projects Area
1024 * Department of Mining
1025 * University of Oviedo
1026 * e-mail zz11425958@zeus.etsimo.uniovi.es
1027 * lolo@pcsig22.etsimo.uniovi.es
1028 * Date: Fri September 20 1996
1029 *
1030 * Modified for transparency handling (gif89a) and miGIF compression
1031 * by Jan Nijtmans <nijtmans@users.sourceforge.net>
1032 *
1033 *----------------------------------------------------------------------
1034 * FileWriteGIF-
1035 *
1036 * This procedure is called by the photo image type to write
1037 * GIF format data from a photo image into a given file
1038 *
1039 * Results:
1040 * A standard TCL completion code. If TCL_ERROR is returned
1041 * then an error message is left in the interp's result.
1042 *
1043 *----------------------------------------------------------------------
1044 */
1045
1046 /*
1047 * Types, defines and variables needed to write and compress a GIF.
1048 */
1049
1050 #define LSB(a) ((unsigned char) (((short)(a)) & 0x00FF))
1051 #define MSB(a) ((unsigned char) (((short)(a)) >> 8))
1052
1053 #define GIFBITS 12
1054 #define HSIZE 5003 /* 80% occupancy */
1055
1056 #define DEFAULT_BACKGROUND_VALUE 0xD9
1057
1058 typedef struct {
1059 int ssize;
1060 int csize;
1061 int rsize;
1062 unsigned char *pixelOffset;
1063 int pixelSize;
1064 int pixelPitch;
1065 int greenOffset;
1066 int blueOffset;
1067 int alphaOffset;
1068 int num;
1069 unsigned char mapa[MAXCOLORMAPSIZE][3];
1070 } GifWriterState;
1071
1072 typedef int (* ifunptr) (GifWriterState *statePtr);
1073
1074 /*
1075 * Definition of new functions to write GIFs
1076 */
1077
1078 static int ColorNumber(GifWriterState *statePtr, int red, int green, int blue);
1079
1080 static void Compress(GifWriterState *statePtr, int init_bits, tkimg_MFile *handle,
1081 ifunptr readValue);
1082
1083 static int IsNewColor(GifWriterState *statePtr, int red, int green ,int blue);
1084
1085 static void SaveMap(GifWriterState *statePtr, Tk_PhotoImageBlock *blockPtr);
1086
1087 static int ReadValue(GifWriterState *statePtr);
1088
1089 static int
ChnWrite(Tcl_Interp * interp,const char * filename,Tcl_Obj * format,Tk_PhotoImageBlock * blockPtr)1090 ChnWrite (
1091 Tcl_Interp *interp, /* Interpreter to use for reporting errors. */
1092 const char *filename,
1093 Tcl_Obj *format,
1094 Tk_PhotoImageBlock *blockPtr
1095 ) {
1096 Tcl_Channel chan = NULL;
1097 tkimg_MFile handle;
1098 int result;
1099
1100 chan = tkimg_OpenFileChannel(interp, filename, 0644);
1101 if (!chan) {
1102 return TCL_ERROR;
1103 }
1104
1105 handle.data = (char *) chan;
1106 handle.state = IMG_CHAN;
1107
1108 result = CommonWrite(interp, &handle, format, blockPtr);
1109 if (Tcl_Close(interp, chan) == TCL_ERROR) {
1110 return TCL_ERROR;
1111 }
1112 return result;
1113 }
1114
StringWrite(Tcl_Interp * interp,Tcl_Obj * format,Tk_PhotoImageBlock * blockPtr)1115 static int StringWrite(
1116 Tcl_Interp *interp,
1117 Tcl_Obj *format,
1118 Tk_PhotoImageBlock *blockPtr
1119 ) {
1120 int result;
1121 tkimg_MFile handle;
1122 Tcl_DString data;
1123
1124 Tcl_DStringInit(&data);
1125 Tcl_DStringSetLength(&data, 1024);
1126 tkimg_WriteInit(&data, &handle);
1127
1128 result = CommonWrite(interp, &handle, format, blockPtr);
1129 tkimg_Putc(IMG_DONE, &handle);
1130
1131 if (result == TCL_OK) {
1132 Tcl_DStringResult(interp, &data);
1133 } else {
1134 Tcl_DStringFree(&data);
1135 }
1136 return result;
1137 }
1138
1139 static int
CommonWrite(Tcl_Interp * interp,tkimg_MFile * handle,Tcl_Obj * format,Tk_PhotoImageBlock * blockPtr)1140 CommonWrite(
1141 Tcl_Interp *interp,
1142 tkimg_MFile *handle,
1143 Tcl_Obj *format,
1144 Tk_PhotoImageBlock *blockPtr
1145 ) {
1146 GifWriterState state;
1147 int resolution;
1148 long width, height, x;
1149 unsigned char c;
1150 unsigned int top, left;
1151
1152 top = 0;
1153 left = 0;
1154
1155 memset(&state, 0, sizeof(state));
1156
1157 state.pixelSize=blockPtr->pixelSize;
1158 state.greenOffset=blockPtr->offset[1]-blockPtr->offset[0];
1159 state.blueOffset=blockPtr->offset[2]-blockPtr->offset[0];
1160 state.alphaOffset = blockPtr->offset[0];
1161
1162 if (state.alphaOffset < blockPtr->offset[2]) {
1163 state.alphaOffset = blockPtr->offset[2];
1164 }
1165 if (++state.alphaOffset < state.pixelSize) {
1166 state.alphaOffset -= blockPtr->offset[0];
1167 } else {
1168 state.alphaOffset = 0;
1169 }
1170
1171 tkimg_Write2(handle, (const char *) (state.alphaOffset ? GIF89a: GIF87a), 6);
1172
1173 for (x=0; x<MAXCOLORMAPSIZE; x++) {
1174 state.mapa[x][CM_RED] = 255;
1175 state.mapa[x][CM_GREEN] = 255;
1176 state.mapa[x][CM_BLUE] = 255;
1177 }
1178
1179 width=blockPtr->width;
1180 height=blockPtr->height;
1181 state.pixelOffset=blockPtr->pixelPtr + blockPtr->offset[0];
1182 state.pixelPitch=blockPtr->pitch;
1183
1184 SaveMap(&state, blockPtr);
1185 if (state.num >= MAXCOLORMAPSIZE) {
1186 Tcl_AppendResult(interp, "too many colors", (char *) NULL);
1187 return TCL_ERROR;
1188 }
1189 if (state.num<2) {
1190 state.num = 2;
1191 }
1192
1193 c=LSB(width);
1194 tkimg_Putc(c, handle);
1195 c=MSB(width);
1196 tkimg_Putc(c, handle);
1197 c=LSB(height);
1198 tkimg_Putc(c, handle);
1199 c=MSB(height);
1200 tkimg_Putc(c, handle);
1201
1202 resolution = 0;
1203 while (state.num >> resolution) {
1204 resolution++;
1205 }
1206 c = 111 + resolution * 17;
1207 tkimg_Putc(c, handle);
1208
1209 state.num = 1 << resolution;
1210
1211 /* background color */
1212 tkimg_Putc(0, handle);
1213
1214 /* zero for future expansion */
1215 tkimg_Putc(0, handle);
1216
1217 for (x=0; x<state.num ;x++) {
1218 tkimg_Putc(state.mapa[x][CM_RED], handle);
1219 tkimg_Putc(state.mapa[x][CM_GREEN], handle);
1220 tkimg_Putc(state.mapa[x][CM_BLUE], handle);
1221 }
1222
1223 /*
1224 * Write out extension for transparent color index, if necessary.
1225 */
1226
1227 if (state.alphaOffset) {
1228 c = GIF_EXTENSION;
1229 tkimg_Putc(c, handle);
1230 tkimg_Write2(handle, "\371\4\1\0\0\0", 7);
1231 }
1232
1233 c = GIF_START;
1234 tkimg_Putc(c, handle);
1235 c=LSB(top);
1236 tkimg_Putc(c, handle);
1237 c=MSB(top);
1238 tkimg_Putc(c, handle);
1239 c=LSB(left);
1240 tkimg_Putc(c, handle);
1241 c=MSB(left);
1242 tkimg_Putc(c, handle);
1243
1244 c=LSB(width);
1245 tkimg_Putc(c, handle);
1246 c=MSB(width);
1247 tkimg_Putc(c, handle);
1248
1249 c=LSB(height);
1250 tkimg_Putc(c, handle);
1251 c=MSB(height);
1252 tkimg_Putc(c, handle);
1253
1254 c=0;
1255 tkimg_Putc(c, handle);
1256 c=resolution;
1257 tkimg_Putc(c, handle);
1258
1259 state.ssize = state.rsize = blockPtr->width;
1260 state.csize = blockPtr->height;
1261 Compress(&state, resolution+1, handle, ReadValue);
1262
1263 tkimg_Putc(0, handle);
1264 c = GIF_TERMINATOR;
1265 tkimg_Putc(c, handle);
1266
1267 return TCL_OK;
1268 }
1269
1270 static int
ColorNumber(GifWriterState * statePtr,int red,int green,int blue)1271 ColorNumber(
1272 GifWriterState *statePtr,
1273 int red, int green, int blue)
1274 {
1275 int x = (statePtr->alphaOffset != 0);
1276
1277 for (; x <= MAXCOLORMAPSIZE; x++) {
1278 if ((statePtr->mapa[x][CM_RED] == red) &&
1279 (statePtr->mapa[x][CM_GREEN] == green) &&
1280 (statePtr->mapa[x][CM_BLUE] == blue)) {
1281 return x;
1282 }
1283 }
1284 return -1;
1285 }
1286
1287
1288 static int
IsNewColor(GifWriterState * statePtr,int red,int green,int blue)1289 IsNewColor(
1290 GifWriterState *statePtr,
1291 int red, int green, int blue)
1292 {
1293 int x = (statePtr->alphaOffset != 0);
1294
1295 for (; x<=statePtr->num ; x++) {
1296 if ((statePtr->mapa[x][CM_RED] == red) &&
1297 (statePtr->mapa[x][CM_GREEN] == green) &&
1298 (statePtr->mapa[x][CM_BLUE] == blue)) {
1299 return 0;
1300 }
1301 }
1302 return 1;
1303 }
1304
1305 static void
SaveMap(GifWriterState * statePtr,Tk_PhotoImageBlock * blockPtr)1306 SaveMap(
1307 GifWriterState *statePtr,
1308 Tk_PhotoImageBlock *blockPtr
1309 ) {
1310 unsigned char *colores;
1311 int x, y;
1312 unsigned char red,green,blue;
1313
1314 if (statePtr->alphaOffset) {
1315 statePtr->num = 1;
1316 statePtr->mapa[0][CM_RED] = DEFAULT_BACKGROUND_VALUE;
1317 statePtr->mapa[0][CM_GREEN] = DEFAULT_BACKGROUND_VALUE;;
1318 statePtr->mapa[0][CM_BLUE] = DEFAULT_BACKGROUND_VALUE;;
1319 } else {
1320 statePtr->num = -1;
1321 }
1322
1323 for(y=0; y<blockPtr->height; y++) {
1324 colores=blockPtr->pixelPtr + blockPtr->offset[0] + y * blockPtr->pitch;
1325 for(x=0; x<blockPtr->width; x++) {
1326 if (!statePtr->alphaOffset || (colores[statePtr->alphaOffset] != 0)) {
1327 red = colores[0];
1328 green = colores[statePtr->greenOffset];
1329 blue = colores[statePtr->blueOffset];
1330 if (IsNewColor(statePtr, red, green, blue)) {
1331 statePtr->num++;
1332 if (statePtr->num >= MAXCOLORMAPSIZE) {
1333 return;
1334 }
1335 statePtr->mapa[statePtr->num][CM_RED]=red;
1336 statePtr->mapa[statePtr->num][CM_GREEN]=green;
1337 statePtr->mapa[statePtr->num][CM_BLUE]=blue;
1338 }
1339 }
1340 colores += statePtr->pixelSize;
1341 }
1342 }
1343 }
1344
1345 static int
ReadValue(GifWriterState * statePtr)1346 ReadValue(
1347 GifWriterState *statePtr
1348 ) {
1349 unsigned int col;
1350
1351 if (statePtr->csize == 0) {
1352 return EOF;
1353 }
1354 if (statePtr->alphaOffset && (statePtr->pixelOffset[statePtr->alphaOffset]==0)) {
1355 col = 0;
1356 } else {
1357 col = ColorNumber(statePtr,
1358 statePtr->pixelOffset[0],
1359 statePtr->pixelOffset[statePtr->greenOffset],
1360 statePtr->pixelOffset[statePtr->blueOffset]);
1361 }
1362 statePtr->pixelOffset += statePtr->pixelSize;
1363 if (--statePtr->ssize <= 0) {
1364 statePtr->ssize = statePtr->rsize;
1365 statePtr->csize--;
1366 statePtr->pixelOffset += statePtr->pixelPitch - (statePtr->rsize * statePtr->pixelSize);
1367 }
1368
1369 return col;
1370 }
1371
1372
1373 /*
1374 *
1375 * GIF Image compression - modified 'compress'
1376 *
1377 * Based on: compress.c - File compression ala IEEE Computer, June 1984.
1378 *
1379 * By Authors: Spencer W. Thomas (decvax!harpo!utah-cs!utah-gr!thomas)
1380 * Jim McKie (decvax!mcvax!jim)
1381 * Steve Davies (decvax!vax135!petsd!peora!srd)
1382 * Ken Turkowski (decvax!decwrl!turtlevax!ken)
1383 * James A. Woods (decvax!ihnp4!ames!jaw)
1384 * Joe Orost (decvax!vax135!petsd!joe)
1385 *
1386 */
1387
1388 #define MAXCODE(n_bits) (((long) 1 << (n_bits)) - 1)
1389
1390 typedef struct {
1391 int n_bits; /* number of bits/code */
1392 long maxcode; /* maximum code, given n_bits */
1393 int htab[HSIZE];
1394 unsigned int codetab[HSIZE];
1395
1396 long hsize; /* for dynamic table sizing */
1397
1398 /*
1399 * To save much memory, we overlay the table used by compress() with those
1400 * used by decompress(). The tab_prefix table is the same size and type
1401 * as the codetab. The tab_suffix table needs 2**GIFBITS characters. We
1402 * get this from the beginning of htab. The output stack uses the rest
1403 * of htab, and contains characters. There is plenty of room for any
1404 * possible stack (stack used to be 8000 characters).
1405 */
1406 int free_ent; /* first unused entry */
1407
1408 /*
1409 * block compression parameters -- after all codes are used up,
1410 * and compression rate changes, start over.
1411 */
1412 int clear_flg;
1413
1414 int offset;
1415 unsigned int in_count; /* length of input */
1416 unsigned int out_count; /* # of codes output (for debugging) */
1417
1418 /*
1419 * compress stdin to stdout
1420 *
1421 * Algorithm: use open addressing double hashing (no chaining) on the
1422 * prefix code / next character combination. We do a variant of Knuth's
1423 * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
1424 * secondary probe. Here, the modular division first probe is gives way
1425 * to a faster exclusive-or manipulation. Also do block compression with
1426 * an adaptive reset, whereby the code table is cleared when the compression
1427 * ratio decreases, but after the table fills. The variable-length output
1428 * codes are re-sized at this point, and a special CLEAR code is generated
1429 * for the decompressor. Late addition: construct the table according to
1430 * file size for noticeable speed improvement on small files. Please direct
1431 * questions about this implementation to ames!jaw.
1432 */
1433 int g_init_bits;
1434 tkimg_MFile *g_outfile;
1435
1436 int ClearCode;
1437 int EOFCode;
1438
1439 unsigned long cur_accum;
1440 int cur_bits;
1441
1442 /*
1443 * Number of characters so far in this 'packet'
1444 */
1445 int a_count;
1446
1447 /*
1448 * Define the storage for the packet accumulator
1449 */
1450 unsigned char accum[256];
1451 } GIFState_t;
1452
1453 static void output(GIFState_t *statePtr, long code);
1454 static void cl_block(GIFState_t *statePtr);
1455 static void cl_hash(GIFState_t *statePtr, int hsize);
1456 static void char_init(GIFState_t *statePtr);
1457 static void char_out(GIFState_t *statePtr, int c);
1458 static void flush_char(GIFState_t *statePtr);
1459
Compress(GifWriterState * statePtr,int init_bits,tkimg_MFile * handle,ifunptr readValue)1460 static void Compress(
1461 GifWriterState *statePtr,
1462 int init_bits,
1463 tkimg_MFile *handle,
1464 ifunptr readValue
1465 ) {
1466 long fcode;
1467 long i = 0;
1468 int c;
1469 long ent;
1470 long disp;
1471 long hsize_reg;
1472 int hshift;
1473 GIFState_t state;
1474
1475 memset(&state, 0, sizeof(state));
1476 /*
1477 * Set up the globals: g_init_bits - initial number of bits
1478 * g_outfile - pointer to output file
1479 */
1480 state.g_init_bits = init_bits;
1481 state.g_outfile = handle;
1482
1483 /*
1484 * Set up the necessary values
1485 */
1486 state.offset = 0;
1487 state.hsize = HSIZE;
1488 state.out_count = 0;
1489 state.clear_flg = 0;
1490 state.in_count = 1;
1491 state.maxcode = MAXCODE(state.n_bits = state.g_init_bits);
1492
1493 state.ClearCode = (1 << (init_bits - 1));
1494 state.EOFCode = state.ClearCode + 1;
1495 state.free_ent = state.ClearCode + 2;
1496
1497 char_init(&state);
1498
1499 ent = readValue(statePtr);
1500
1501 hshift = 0;
1502 for ( fcode = (long) state.hsize; fcode < 65536L; fcode *= 2L ) {
1503 hshift++;
1504 }
1505 hshift = 8 - hshift; /* set hash code range bound */
1506
1507 hsize_reg = state.hsize;
1508 cl_hash(&state, (int) hsize_reg); /* clear hash table */
1509
1510 output(&state, (long)state.ClearCode);
1511
1512 #ifdef SIGNED_COMPARE_SLOW
1513 while ( (c = readValue(statePtr) ) != (unsigned) EOF ) {
1514 #else
1515 while ( (c = readValue(statePtr)) != EOF ) {
1516 #endif
1517
1518 state.in_count++;
1519
1520 fcode = (long) (((long) c << GIFBITS) + ent);
1521 i = (((long)c << hshift) ^ ent); /* xor hashing */
1522
1523 if (state.htab[i] == fcode) {
1524 ent = state.codetab[i];
1525 continue;
1526 } else if ( (long) state.htab[i] < 0 ) /* empty slot */
1527 goto nomatch;
1528 disp = hsize_reg - i; /* secondary hash (after G. Knott) */
1529 if ( i == 0 ) {
1530 disp = 1;
1531 }
1532 probe:
1533 if ( (i -= disp) < 0 ) {
1534 i += hsize_reg;
1535 }
1536
1537 if (state.htab[i] == fcode) {
1538 ent = state.codetab[i];
1539 continue;
1540 }
1541 if ( (long) state.htab[i] > 0 ) {
1542 goto probe;
1543 }
1544 nomatch:
1545 output (&state, (long) ent);
1546 state.out_count++;
1547 ent = c;
1548 #ifdef SIGNED_COMPARE_SLOW
1549 if ( (unsigned) free_ent < (unsigned) ((long)1 << GIFBITS)) {
1550 #else
1551 if (state.free_ent < ((long)1 << GIFBITS)) {
1552 #endif
1553 state.codetab[i] = state.free_ent++; /* code -> hashtable */
1554 state.htab[i] = fcode;
1555 } else {
1556 cl_block(&state);
1557 }
1558 }
1559 /*
1560 * Put out the final code.
1561 */
1562 output(&state, (long)ent);
1563 state.out_count++;
1564 output(&state, (long) state.EOFCode);
1565
1566 return;
1567 }
1568
1569 /*****************************************************************
1570 * TAG( output )
1571 *
1572 * Output the given code.
1573 * Inputs:
1574 * code: A n_bits-bit integer. If == -1, then EOF. This assumes
1575 * that n_bits =< (long) wordsize - 1.
1576 * Outputs:
1577 * Outputs code to the file.
1578 * Assumptions:
1579 * Chars are 8 bits long.
1580 * Algorithm:
1581 * Maintain a GIFBITS character long buffer (so that 8 codes will
1582 * fit in it exactly). Use the VAX insv instruction to insert each
1583 * code in turn. When the buffer fills up empty it and start over.
1584 */
1585
1586 static const
1587 unsigned long masks[] = {
1588 0x0000,
1589 0x0001, 0x0003, 0x0007, 0x000F,
1590 0x001F, 0x003F, 0x007F, 0x00FF,
1591 0x01FF, 0x03FF, 0x07FF, 0x0FFF,
1592 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF
1593 };
1594
1595 static void
1596 output(
1597 GIFState_t *statePtr,
1598 long code
1599 ) {
1600 statePtr->cur_accum &= masks[statePtr->cur_bits];
1601
1602 if (statePtr->cur_bits > 0) {
1603 statePtr->cur_accum |= ((long) code << statePtr->cur_bits);
1604 } else {
1605 statePtr->cur_accum = code;
1606 }
1607
1608 statePtr->cur_bits += statePtr->n_bits;
1609
1610 while (statePtr->cur_bits >= 8 ) {
1611 char_out(statePtr, (unsigned int)(statePtr->cur_accum & 0xff));
1612 statePtr->cur_accum >>= 8;
1613 statePtr->cur_bits -= 8;
1614 }
1615
1616 /*
1617 * If the next entry is going to be too big for the code size,
1618 * then increase it, if possible.
1619 */
1620
1621 if ((statePtr->free_ent > statePtr->maxcode)|| statePtr->clear_flg ) {
1622 if (statePtr->clear_flg) {
1623 statePtr->maxcode = MAXCODE(statePtr->n_bits = statePtr->g_init_bits);
1624 statePtr->clear_flg = 0;
1625 } else {
1626 statePtr->n_bits++;
1627 if (statePtr->n_bits == GIFBITS) {
1628 statePtr->maxcode = (long)1 << GIFBITS;
1629 } else {
1630 statePtr->maxcode = MAXCODE(statePtr->n_bits);
1631 }
1632 }
1633 }
1634
1635 if (code == statePtr->EOFCode) {
1636 /*
1637 * At EOF, write the rest of the buffer.
1638 */
1639 while (statePtr->cur_bits > 0) {
1640 char_out(statePtr, (unsigned int)(statePtr->cur_accum & 0xff));
1641 statePtr->cur_accum >>= 8;
1642 statePtr->cur_bits -= 8;
1643 }
1644 flush_char(statePtr);
1645 }
1646 }
1647
1648 /*
1649 * Clear out the hash table
1650 */
1651 static void
1652 cl_block(GIFState_t * statePtr) /* table clear for block compress */
1653 {
1654
1655 cl_hash (statePtr, (int) statePtr->hsize);
1656 statePtr->free_ent = statePtr->ClearCode + 2;
1657 statePtr->clear_flg = 1;
1658
1659 output(statePtr, (long) statePtr->ClearCode);
1660 }
1661
1662 static void
1663 cl_hash(GIFState_t *statePtr, int hsize) /* reset code table */
1664 {
1665 int *htab_p = statePtr->htab+hsize;
1666 long i;
1667 long m1 = -1;
1668
1669 i = hsize - 16;
1670 do { /* might use Sys V memset(3) here */
1671 *(htab_p-16) = m1;
1672 *(htab_p-15) = m1;
1673 *(htab_p-14) = m1;
1674 *(htab_p-13) = m1;
1675 *(htab_p-12) = m1;
1676 *(htab_p-11) = m1;
1677 *(htab_p-10) = m1;
1678 *(htab_p-9) = m1;
1679 *(htab_p-8) = m1;
1680 *(htab_p-7) = m1;
1681 *(htab_p-6) = m1;
1682 *(htab_p-5) = m1;
1683 *(htab_p-4) = m1;
1684 *(htab_p-3) = m1;
1685 *(htab_p-2) = m1;
1686 *(htab_p-1) = m1;
1687 htab_p -= 16;
1688 } while ((i -= 16) >= 0);
1689
1690 for (i += 16; i > 0; i--) {
1691 *--htab_p = m1;
1692 }
1693 }
1694
1695 /******************************************************************************
1696 *
1697 * GIF Specific routines
1698 *
1699 ******************************************************************************/
1700
1701 /*
1702 * Set up the 'byte output' routine
1703 */
1704 static void
1705 char_init(GIFState_t *statePtr)
1706 {
1707 statePtr->a_count = 0;
1708 statePtr->cur_accum = 0;
1709 statePtr->cur_bits = 0;
1710 }
1711
1712 /*
1713 * Add a character to the end of the current packet, and if it is 254
1714 * characters, flush the packet to disk.
1715 */
1716 static void
1717 char_out(GIFState_t *statePtr, int c)
1718 {
1719 statePtr->accum[statePtr->a_count++] = c;
1720 if (statePtr->a_count >= 254) {
1721 flush_char(statePtr);
1722 }
1723 }
1724
1725 /*
1726 * Flush the packet to disk, and reset the accumulator
1727 */
1728 static void
1729 flush_char(GIFState_t *statePtr)
1730 {
1731 unsigned char c;
1732
1733 if (statePtr->a_count > 0) {
1734 c = statePtr->a_count;
1735 tkimg_Write2(statePtr->g_outfile, (const char *) &c, 1);
1736 tkimg_Write2(statePtr->g_outfile, (const char *) statePtr->accum, statePtr->a_count);
1737 statePtr->a_count = 0;
1738 }
1739 }
1740
1741 /* The End */
1742