* generic/tkImgPhoto.c: Added some comments regarding slow

processing of transparent images.

* generic/tkImgGIF.c: Improved GIF decoder for ~60% speed
increase.  Added some comments on how to further improve the
implementation, time permitting.

* doc/photo.n: Added a description of what the -data string can
contain (base64 or binary data).

4 files changed, 315 insertions, 99 deletions

diff --git a/ChangeLog b/ChangeLog
index c004176..754d848 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,18 @@
+2000-01-26  Eric Melski  <ericm@scriptics.com>
+
+	* generic/tkImgPhoto.c: Added some comments regarding slow
+	processing of transparent images.
+
+	* generic/tkImgGIF.c: Improved GIF decoder for ~60% speed
+	increase.  Added some comments on how to further improve the
+	implementation, time permitting.
+
+	* doc/photo.n: Added a description of what the -data string can
+	contain (base64 or binary data).
+
+	* generic/tkImgPhoto.c: Fixed bug with use of binary data for
+	"-data" option to "image create" command.
+
 2000-01-21  Eric Melski  <ericm@scriptics.com>
 
 	* library/tkfbox.tcl: Fixed bug relating to incorrect parent
diff --git a/doc/photo.n b/doc/photo.n
index b9f143b..c49d2a1 100644
--- a/doc/photo.n
+++ b/doc/photo.n
@@ -9,7 +9,7 @@
 '\"	    Department of Computer Science,
 '\"	    Australian National University.
 '\"
-'\" RCS: @(#) $Id: photo.n,v 1.3 1999/10/29 03:57:40 hobbs Exp $
+'\" RCS: @(#) $Id: photo.n,v 1.4 2000/01/26 21:11:00 ericm Exp $
 '\" 
 .so man.macros
 .TH photo n 4.0 Tk "Tk Built-In Commands"
@@ -40,7 +40,8 @@ command.
 Photos support the following \fIoptions\fR:
 .TP
 \fB\-data \fIstring\fR
-Specifies the contents of the image as a string.  The format of the
+Specifies the contents of the image as a string.  The string can
+contain base64 encoded data or binary data.  The format of the
 string must be one of those for which there is an image file format
 handler that will accept string data.  If both the \fB\-data\fR
 and \fB\-file\fR options are specified, the \fB\-file\fR option takes
diff --git a/generic/tkImgGIF.c b/generic/tkImgGIF.c
index 3653141..52ba2d7 100644
--- a/generic/tkImgGIF.c
+++ b/generic/tkImgGIF.c
@@ -29,7 +29,7 @@
  * |   provided "as is" without express or implied warranty.           |
  * +-------------------------------------------------------------------+
  *
- * RCS: @(#) $Id: tkImgGIF.c,v 1.8 1999/12/09 14:46:33 hobbs Exp $
+ * RCS: @(#) $Id: tkImgGIF.c,v 1.9 2000/01/26 21:11:00 ericm Exp $
  */
 
 /*
@@ -717,6 +717,41 @@ GetDataBlock(chan, buf)
 }
 
 
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * ReadImage --
+ *
+ *	Process a GIF image from a given source, with a given height,
+ *      width, transparency, etc.
+ *
+ *      This code is based on the code found in the ImageMagick GIF decoder,
+ *      which is (c) 2000 ImageMagick Studio.
+ *
+ *      Some thoughts on our implementation:
+ *      We currently have implementations for two separate GIF decoders in
+ *      this source.  One is here, in ReadImage; the other is in LWZReadByte.
+ *      This is an artifact of our original implementation.  Ideally, we
+ *      should remove all vestiges of LWZReadByte, which is slow and poorly
+ *      documented.  However, that would require some additional effort to
+ *      collapse the calling layers of this system:  Instead of
+ *      FileReadGIF -> ReadImage, it would change to FileReadGIF.
+ *
+ *      Possible further optimizations:  we could pull the GetCode function
+ *      directly into ReadImage, which would improve our speed.  The reason
+ *      I have not yet done so is because GetCode is still used by LWZReadByte,
+ *      and I don't want to duplicate the code.
+ *
+ * Results:
+ *	Processes a GIF image and loads the pixel data into a memory array.
+ *
+ * Side effects:
+ *	None.
+ *
+ *----------------------------------------------------------------------
+ */
+
 static int
 ReadImage(interp, imagePtr, chan, len, rows, cmap,
 	width, height, srcX, srcY, interlace, transparent)
@@ -730,26 +765,28 @@ ReadImage(interp, imagePtr, chan, len, rows, cmap,
      int interlace;
      int transparent;
 {
-    unsigned char c;
+    unsigned char initialCodeSize;
     int v;
-    int xpos = 0, ypos = 0, pass = 0;
+    int xpos = 0, ypos = 0, pass = 0, i;
     char *pixelPtr;
-
-
+    const static int interlaceStep[] = { 8, 8, 4, 2 };
+    const static int interlaceStart[] = { 0, 4, 2, 1 };
+    unsigned short prefix[(1 << MAX_LWZ_BITS)];
+    unsigned char  append[(1 << MAX_LWZ_BITS)];
+    unsigned char  stack[(1 << MAX_LWZ_BITS)*2];
+    unsigned char *top;
+    int codeSize, clearCode, inCode, endCode, oldCode, maxCode,
+	code, firstCode;
+    
+    
     /*
-     *  Initialize the Compression routines
+     *  Initialize the decompression routines
      */
-    if (! ReadOK(chan, &c, 1))  {
+    if (! ReadOK(chan, &initialCodeSize, 1))  {
 	Tcl_AppendResult(interp, "error reading GIF image: ",
 		Tcl_PosixError(interp), (char *) NULL);
 	return TCL_ERROR;
     }
-
-    if (LWZReadByte(chan, 1, c) < 0) {
-	Tcl_SetResult(interp, "format error in GIF image", TCL_STATIC);
-	return TCL_ERROR;
-    }
-
     if (transparent!=-1) {
 	cmap[transparent][CM_RED] = 0;
 	cmap[transparent][CM_GREEN] = 0;
@@ -758,52 +795,154 @@ ReadImage(interp, imagePtr, chan, len, rows, cmap,
     }
 
     pixelPtr = imagePtr;
-    while ((v = LWZReadByte(chan, 0, c)) >= 0 ) {
 
-	if ((xpos>=srcX) && (xpos<srcX+len) &&
-		(ypos>=srcY) && (ypos<srcY+rows)) {
+    /* Initialize the decoder */
+    /* Set values for "special" numbers:
+     * clear code	reset the decoder
+     * end code		stop decoding
+     * code size	size of the next code to retrieve
+     * max code		next available table position
+     */
+    clearCode   = 1 << (int) initialCodeSize;
+    endCode     = clearCode + 1;
+    codeSize    = (int) initialCodeSize + 1;
+    maxCode     = clearCode + 2;
+    oldCode     = -1;
+    firstCode   = -1;
+    
+    memset((void *)prefix, 0, (1 << MAX_LWZ_BITS) * sizeof(short));
+    memset((void *)append, 0, (1 << MAX_LWZ_BITS) * sizeof(char));
+    for (i = 0; i < clearCode; i++) {
+	append[i] = i;
+    }
+    top = stack;
+
+    GetCode(chan, 0, 1);
+
+    /* Read until we finish the image */
+    for (i = 0, ypos = 0; i < rows; i++) {
+	for (xpos = 0; xpos < len; ) {
+
+	    if (top == stack) {
+		/* Bummer -- our stack is empty.  Now we have to work! */
+		code = GetCode(chan, codeSize, 0);
+		if (code < 0) {
+		    return TCL_OK;
+		}
+
+		if (code > maxCode || code == endCode) {
+		    /*
+		     * If we're doing things right, we should never
+		     * receive a code that is greater than our current
+		     * maximum code.  If we do, bail, because our decoder
+		     * does not yet have that code set up.
+		     *
+		     * If the code is the magic endCode value, quit.
+		     */
+		    return TCL_OK;
+		}
+
+		if (code == clearCode) {
+		    /* Reset the decoder */
+		    codeSize    = initialCodeSize + 1;
+		    maxCode     = clearCode + 2;
+		    oldCode     = -1;
+		    continue;
+		}
+		
+		if (oldCode == -1) {
+		    /*
+		     * Last pass reset the decoder, so the first code we
+		     * see must be a singleton.  Seed the stack with it,
+		     * and set up the old/first code pointers for
+		     * insertion into the string table.  We can't just
+		     * roll this into the clearCode test above, because
+		     * at that point we have not yet read the next code.
+		     */
+		    *top++=append[code];
+		    oldCode = code;
+		    firstCode = code;
+		    continue;
+		}
+		
+		inCode = code;
+
+		if (code == maxCode) {
+		    /*
+		     * maxCode is always one bigger than our highest assigned
+		     * code.  If the code we see is equal to maxCode, then
+		     * we are about to add a new string to the table. ???
+		     */
+		    *top++ = firstCode;
+		    code = oldCode;
+		}
+
+		while (code > clearCode) {
+		    /*
+		     * Populate the stack by tracing the string in the
+		     * string table from its tail to its head
+		     */
+		    *top++ = append[code];
+		    code = prefix[code];
+		}
+		firstCode = append[code];
+
+		/*
+		 * If there's no more room in our string table, quit.
+		 * Otherwise, add a new string to the table
+		 */
+		if (maxCode >= (1 << MAX_LWZ_BITS)) {
+		    return TCL_OK;
+		}
+
+		/* Push the head of the string onto the stack */
+		*top++ = firstCode;
+
+		/* Add a new string to the string table */
+		prefix[maxCode] = oldCode;
+		append[maxCode] = firstCode;
+		maxCode++;
+
+		/* maxCode tells us the maximum code value we can accept.
+		 * If we see that we need more bits to represent it than
+		 * we are requesting from the unpacker, we need to increase
+		 * the number we ask for.
+		 */
+		if ((maxCode >= (1 << codeSize))
+			&& (maxCode < (1<<MAX_LWZ_BITS))) {
+		    codeSize++;
+		}
+		oldCode = inCode;
+	    }
+
+	    /* Pop the next color index off the stack */
+	    v = *(--top);
+	    if (v < 0) {
+		return TCL_OK;
+	    }
 	    *pixelPtr++ = cmap[v][CM_RED];
 	    *pixelPtr++ = cmap[v][CM_GREEN];
 	    *pixelPtr++ = cmap[v][CM_BLUE];
 	    if (transparent >= 0) {
 		*pixelPtr++ = cmap[v][CM_ALPHA];
 	    }
+	    xpos++;
 	}
 
-	++xpos;
-	if (xpos == width) {
-	    xpos = 0;
-	    if (interlace) {
-		switch (pass) {
-		    case 0:
-		    case 1:
-			ypos += 8; break;
-		    case 2:
-			ypos += 4; break;
-		    case 3:
-			ypos += 2; break;
+	/* If interlacing, the next ypos is not just +1 */
+	if (interlace) {
+	    ypos += interlaceStep[pass];
+	    while (ypos >= height) {
+		pass++;
+		if (pass > 3) {
+		    return TCL_OK;
 		}
-		
-		while (ypos >= height) {
-		    ++pass;
-		    switch (pass) {
-			case 1:
-			    ypos = 4; break;
-			case 2:
-			    ypos = 2; break;
-			case 3:
-			    ypos = 1; break;
-			default:
-			    return TCL_OK;
-		    }
-		}
-	    } else {
-		++ypos;
+		ypos = interlaceStart[pass];
 	    }
-	    pixelPtr = imagePtr + (ypos-srcY) * len * ((transparent>=0)?4:3);
+	} else {
+	    ypos++;
 	}
-	if (ypos >= height)
-	    break;
+	pixelPtr = imagePtr + (ypos) * len * ((transparent>=0)?4:3);
     }
     return TCL_OK;
 }
@@ -820,7 +959,8 @@ LWZReadByte(chan, flag, input_code_size)
     static int max_code, max_code_size;
     static int firstcode, oldcode;
     static int clear_code, end_code;
-    static int table[2][(1<< MAX_LWZ_BITS)];
+    static int prefix[(1 << MAX_LWZ_BITS)];
+    static int append[(1 << MAX_LWZ_BITS)];
     static int stack[(1<<(MAX_LWZ_BITS))*2], *sp;
     register int    i;
 
@@ -832,26 +972,31 @@ LWZReadByte(chan, flag, input_code_size)
 	max_code_size = 2*clear_code;
 	max_code = clear_code+2;
 
+	/* Init the lwz unpacker */
 	GetCode(chan, 0, 1);
 
 	fresh = 1;
 
+	/* Initialize prefix and append tables */
+	memset((void *)prefix, 0, (1 << MAX_LWZ_BITS) * sizeof(int));
+	memset((void *)append, 0, (1 << MAX_LWZ_BITS) * sizeof(int));
 	for (i = 0; i < clear_code; ++i) {
-	    table[0][i] = 0;
-	    table[1][i] = i;
+	    append[i] = i;
 	}
-	for (; i < (1<<MAX_LWZ_BITS); ++i) {
-	    table[0][i] = table[1][0] = 0;
-	}
-
 	sp = stack;
 
 	return 0;
     } else if (fresh) {
+	/*
+	 * find the first "real" code and return that.  Because of
+	 * how LWZ works, it will necessarily refer to a single char,
+	 * so we need not bother with the stack
+	 */
 	fresh = 0;
 	do {
-	    firstcode = oldcode = GetCode(chan, code_size, 0);
+	    firstcode = GetCode(chan, code_size, 0);
 	} while (firstcode == clear_code);
+	oldcode = firstcode;
 	return firstcode;
     }
 
@@ -861,13 +1006,10 @@ LWZReadByte(chan, flag, input_code_size)
 
     while ((code = GetCode(chan, code_size, 0)) >= 0) {
 	if (code == clear_code) {
+	    memset((void *)prefix, 0, (1 << MAX_LWZ_BITS) * sizeof(int));
+	    memset((void *)append, 0, (1 << MAX_LWZ_BITS) * sizeof(int));
 	    for (i = 0; i < clear_code; ++i) {
-		table[0][i] = 0;
-		table[1][i] = i;
-	    }
-	    
-	    for (; i < (1<<MAX_LWZ_BITS); ++i) {
-		table[0][i] = table[1][i] = 0;
+		append[i] = i;
 	    }
 
 	    code_size = set_code_size+1;
@@ -901,8 +1043,8 @@ LWZReadByte(chan, flag, input_code_size)
 	}
 
 	while (code >= clear_code) {
-	    *sp++ = table[1][code];
-	    if (code == table[0][code]) {
+	    *sp++ = append[code];
+	    if (code == prefix[code]) {
 		return -2;
 
 		/*
@@ -911,14 +1053,14 @@ LWZReadByte(chan, flag, input_code_size)
 		 printf("circular table entry BIG ERROR\n");
 		 */
 	    }
-	    code = table[0][code];
+	    code = prefix[code];
 	}
 
-	*sp++ = firstcode = table[1][code];
+	*sp++ = firstcode = append[code];
 
 	if ((code = max_code) <(1<<MAX_LWZ_BITS)) {
-	    table[0][code] = oldcode;
-	    table[1][code] = firstcode;
+	    prefix[code] = oldcode;
+	    append[code] = firstcode;
 	    ++max_code;
 	    if ((max_code>=max_code_size) && (max_code_size < (1<<MAX_LWZ_BITS))) {
 		max_code_size *= 2;
@@ -934,6 +1076,35 @@ LWZReadByte(chan, flag, input_code_size)
 	return code;
 }
 
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * GetCode --
+ *
+ *      Extract the next compression code from the file.  In GIF's, the
+ *      compression codes are between 3 and 12 bits long and are then
+ *      packed into 8 bit bytes, left to right, for example:
+ *                 bbbaaaaa
+ *                 dcccccbb
+ *                 eeeedddd
+ *                 ...
+ *      We use a byte buffer read from the file and a sliding window
+ *      to unpack the bytes.  Thanks to ImageMagick for the sliding window
+ *      idea.
+ *      args:  chan         the channel to read from
+ *             code_size    size of the code to extract
+ *             flag         boolean indicating whether the extractor
+ *                          should be reset or not
+ *
+ * Results:
+ *	code                the next compression code
+ *
+ * Side effects:
+ *	May consume more input from chan.
+ *
+ *----------------------------------------------------------------------
+ */
 
 static int
 GetCode(chan, code_size, flag)
@@ -942,46 +1113,51 @@ GetCode(chan, code_size, flag)
      int flag;
 {
     static unsigned char buf[280];
-    static int curbit, lastbit, done, last_byte;
-    int i, j, ret;
-    unsigned char count;
+    static int bytes = 0, done;
+    static unsigned char *c;
 
+    static unsigned int window;
+    static int bitsInWindow = 0;
+    int ret;
+    
     if (flag) {
-	curbit = 0;
-	lastbit = 0;
+	/* Initialize the decoder */
+	bitsInWindow = 0;
+	bytes = 0;
+	window = 0;
 	done = 0;
+	c = NULL;
 	return 0;
     }
 
-
-    if ( (curbit+code_size) >= lastbit) {
+    while (bitsInWindow < code_size) {
+	/* Not enough bits in our window to cover the request */
 	if (done) {
-	    /* ran off the end of my bits */
 	    return -1;
 	}
-	if (last_byte >= 2) {
-	    buf[0] = buf[last_byte-2];
-	}
-	if (last_byte >= 1) {
-	    buf[1] = buf[last_byte-1];
-	}
-
-	if ((count = GetDataBlock(chan, &buf[2])) == 0) {
-	    done = 1;
+	if (bytes == 0) {
+	    /* Not enough bytes in our buffer to add to the window */
+	    bytes = GetDataBlock(chan, buf);
+	    c = buf;
+	    if (bytes <= 0) {
+		done = 1;
+		break;
+	    }
 	}
-
-	last_byte = 2 + count;
-	curbit = (curbit - lastbit) + 16;
-	lastbit = (2+count)*8 ;
-    }
-
-    ret = 0;
-    for (i = curbit, j = 0; j < code_size; ++i, ++j) {
-	ret |= ((buf[ i / 8 ] & (1 << (i % 8))) != 0) << j;
+	/* Tack another byte onto the window, see if that's enough */
+	window += (*c) << bitsInWindow;
+	c++;
+	bitsInWindow += 8;
+	bytes--;
     }
 
-    curbit += code_size;
 
+    /* The next code will always be the last code_size bits of the window */
+    ret = window & ((1 << code_size) - 1);
+    
+    /* Shift data in the window to put the next code at the end */
+    window >>= code_size;
+    bitsInWindow -= code_size;
     return ret;
 }
 
diff --git a/generic/tkImgPhoto.c b/generic/tkImgPhoto.c
index 97e61af..17b61eb 100644
--- a/generic/tkImgPhoto.c
+++ b/generic/tkImgPhoto.c
@@ -15,7 +15,7 @@
  *	   Department of Computer Science,
  *	   Australian National University.
  *
- * RCS: @(#) $Id: tkImgPhoto.c,v 1.13 2000/01/26 17:02:27 ericm Exp $
+ * RCS: @(#) $Id: tkImgPhoto.c,v 1.14 2000/01/26 21:11:00 ericm Exp $
  */
 
 #include "tkInt.h"
@@ -3760,7 +3760,13 @@ Tk_PhotoPutBlock(handle, blockPtr, x, y, width, height)
     destLinePtr = masterPtr->pix24 + (y * masterPtr->width + x) * 4;
     pitch = masterPtr->width * 4;
 
-    if ((blockPtr->pixelSize == 4) && (greenOffset == 1) && (blueOffset == 2) && (alphaOffset == 0)
+    /*
+     * This test is probably too restrictive.  We should also be able to
+     * do a memcpy if pixelSize == 3 and alphaOffset == 0.  Maybe other cases
+     * too.
+     */
+    if ((blockPtr->pixelSize == 4)
+	    && (greenOffset == 1) && (blueOffset == 2) && (alphaOffset == 3)
 	    && (width <= blockPtr->width) && (height <= blockPtr->height)
 	    && ((height == 1) || ((x == 0) && (width == masterPtr->width)
 		&& (blockPtr->pitch == pitch)))) {
@@ -3811,7 +3817,25 @@ Tk_PhotoPutBlock(handle, blockPtr, x, y, width, height)
 
   if (alphaOffset) {
     int x1, y1, end;
-
+    
+    /*
+     * This block is grossly inefficient.  For each row in the image, it
+     * finds each continguous string of transparent pixels, then marks those
+     * areas as invalid in the validRegion mask.  This makes drawing very
+     * efficient, because of the way we use X:  we just say, here's your
+     * mask, and here's your data.  We need not worry about the current
+     * background color, etc.  But this costs us a lot on the image setup.
+     * Still, image setup only happens once, whereas the drawing happens
+     * many times, so this might be the best way to go.
+     *
+     * An alternative might be to not set up this mask, and instead, at
+     * drawing time, for each transparent pixel, set its color to the
+     * color of the background behind that pixel.  This is what I suspect
+     * most of programs do.  However, they don't have to deal with the canvas,
+     * which could have many different background colors.  Determining the
+     * correct bg color for a given pixel might be expensive.
+     */
+     
     destLinePtr = masterPtr->pix24 + (y * masterPtr->width + x) * 4 + 3;
     for (y1 = 0; y1 < height; y1++) {
 	x1 = 0;