From 7e47234206a345a0b8dcbe7bd066ed360e4a9942 Mon Sep 17 00:00:00 2001 From: ericm Date: Wed, 26 Jan 2000 21:10:59 +0000 Subject: * 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). --- ChangeLog | 15 +++ doc/photo.n | 5 +- generic/tkImgGIF.c | 364 ++++++++++++++++++++++++++++++++++++++------------- generic/tkImgPhoto.c | 30 ++++- 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 + + * 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 * 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=srcY) && (ypos 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<= 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<= 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<= 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_code_size) && (max_code_size < (1<= 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; -- cgit v0.12