Closed Bug 274391 Opened 15 years ago Closed 15 years ago

GIF Decoder: Convert many malloc's to 1, also remove broken netscape extension

Categories

(Core :: ImageLib, defect)

defect
Not set

Tracking

()

VERIFIED FIXED

People

(Reporter: alfredkayser, Assigned: pavlov)

References

()

Details

Attachments

(6 files, 11 obsolete files)

69.44 KB, image/gif
Details
155.68 KB, image/gif
Details
3.05 KB, text/plain
Details
1.66 KB, image/gif
Details
14.62 KB, patch
pavlov
: review+
Details | Diff | Splinter Review
22.17 KB, patch
pavlov
: review+
Details | Diff | Splinter Review
Looking at memory allocaters (specifically the recyclingAllocator), I noticed
that GIF2.cpp allocates in one go, three blocks of fixed size, and releases them
at the same time. So these could also be allocated as one block:

535       if (!gs->prefix)
536         gs->prefix = (PRUint16 *)gif_calloc(sizeof(PRUint16), MAX_BITS);
537       if (!gs->suffix)
538         gs->suffix = ( PRUint8 *)gif_calloc(sizeof(PRUint8),  MAX_BITS);
539       if (!gs->stack)
540         gs->stack  = ( PRUint8 *)gif_calloc(sizeof(PRUint8),  MAX_BITS);

and:

1081   gif_free(gs->prefix);
1082   gif_free(gs->suffix);
1083   gif_free(gs->stack);

Allocating them as one block, saves some memory allocation overhead, also in the
recycler (or even more so!). Instead of 3 blocks of different sizes per decode
run, it allocates always one block of the same size per run.
Attachment #168599 - Flags: review?(dom_bug_listener)
Well, could we go even further and make them static member of gif_struct ?

Current life span :

- GIFInit : gs is allocated
- first call to 'gif_write' : those static size buffers are allocated
- gif_destroy : gs and the buffers (if present) are disallocated

Will usually GIFInit be called without gif_write being called too soon afterward ?

Of course, that change would need a more careful review than the obvious change
above.
Merged the allocation of GIFStruct and the prefix/suffix/stack buffers, 
also moved this allocation to nsGIFDecoder, so both allocation and free of the
GIFStruct is in one file.
Further, some small cleanups and optimisations in GIF2.cpp.
Sideeffect: some codesize reduction about 700bytes.

Note, it is not clear whether the memset's all required for the prefix/suffix
and stack buffers, but I left them in to be safe.
Blocks: 196295
Attachment #168599 - Flags: review?(dom_bug_listener) → review?(jst)
Attachment #168599 - Flags: review?(jst)
Attachment #168690 - Flags: review?(jst)
Comment on attachment 168690 [details] [diff] [review]
Merged allocation of GIFStruct and the prefix/stack/suffix

+      memset(gs->prefix, 0, sizeof(PRUint16)*MAX_BITS);
+      memset(gs->suffix, 0, sizeof(PRUint8)*MAX_BITS);
+      memset(gs->stack, 0, sizeof(PRUint8)*MAX_BITS);

How about using sizeof(gs->prefix) etc there in stead of hard coding the sizes
here too?

+    PRBool is_transparent;	    /* TRUE, if tpixel is valid */
+    PRBool is_local_colormap_defined;
+    PRBool progressive_display;    /* If TRUE, do Haeberli interlace hack */

These are asking to be changed to PRPackedBool's.

+/*****************************************************************************
**
+ * Gif decoder allocator
+ *
+ * For every image that gets loaded, we allocate
+ *	4097 x 2 : gs->prefix
+ *	4097 x 1 : gs->suffix
+ *	4097 x 1 : gs->stack
+ * for lzw to operate on the data. These are held for a very short interval
+ * and freed. This allocator tries to keep one set of these around
+ * and reuses them; automatically fails over to use calloc/free when all
+ * buckets are full.

That's not exactly true any more, no more separate allocations etc. Update the
comment.

With that, r=jst.
Attachment #168690 - Flags: review?(jst) → review+
Attached patch Incorporated comments from jst. (obsolete) — Splinter Review
Note, the free of mGIFStruct in ::Close was missing, so I've added it there.
So save more code bytes, the destructor now calls ::Close (which is save to
do),
and some other small assembly level optimisations in GIF2.cpp.

Fully tested with a wide range of GIF files, very large ones, 'truecolors',
very large interlaced files, etc.
Attachment #168599 - Attachment is obsolete: true
Attachment #168690 - Attachment is obsolete: true
Attachment #168765 - Flags: superreview?(darin)
Comment on attachment 168765 [details] [diff] [review]
Incorporated comments from jst.

>Index: modules/libpr0n/decoders/gif/GIF2.cpp

>+const PRUintn kDup[]    = { 0, 7, 3, 1 }; 
>+const PRUintn kRowInc[] = { 0, 8, 8, 4, 2 }; 
>+const PRUintn kRowTop[] = { 0, 4, 2, 1, 0 }; 

can you add a comment for these?


>Index: modules/libpr0n/decoders/gif/nsGIFDecoder2.cpp

>+  if (!gGifAllocator)
>+    gGifAllocator = new nsRecyclingAllocator(kGifAllocatorNBucket,
>+                                             NS_DEFAULT_RECYCLE_TIMEOUT, "gif");
>+  mGIFStruct = (gif_struct *)(gGifAllocator ?
>+                              gGifAllocator->Calloc(sizeof(gif_struct),1) :
>+                              calloc(sizeof(gif_struct),1))

If |new nsRecyclingAllocator| failed, why do you bother trying to
call |calloc|?	I don't understand.  It seems like you would have
an OOM condition, and would just want to bail.	Surely calloc will
also fail, no?


I think this patch should also be reviewed by one of the ImageLib
peers, preferrably by pavlov.
This version incorporates comments from Darin:
* Added comments to the constant arrays
* I left in the 'calloc' bailout, because it doesn't hurt, and can be be backup
for the RecyclingAllocator...

I've added the following changes:
* removed some unused states from the gif decoder, merged the gif header
parsing into one state.
* changed BlockAllocCat to keep the 'hold' size a multiple of 256 bytes, and to
only resize when it needs to be bigger (it will be at most 1024 bytes anyway).
This saves a malloc and realloc for each 4096 byte crossing (because GifWrite
gets 4K bytes per call), and even for very large animated gifs, now at most one
malloc and one realloc is needed. This makes the loading of those gifs much
faster. (memory usage is still bad because of the 24bit color processing...)
* Renamed functions to be more consistent (GifInit, GifWrite, GifClose)
* Removed gif_write_ready, because it is not needed anymore because of the
streaming (4K per call), and because the parser is not limited to the buffer
size anyway.
Attachment #168765 - Attachment is obsolete: true
Attachment #168941 - Flags: review?(pavlov)
Attachment #168765 - Flags: superreview?(darin)
> * I left in the 'calloc' bailout, because it doesn't hurt, and can be be backup
> for the RecyclingAllocator...

on the contrary, it increases codesize even though it will practically never be
used.  seems like a bad choice to me.

be careful about adding more complexity to this patch.  it increases the barrier
to code review.
Attachment #168941 - Attachment is obsolete: true
Attachment #169278 - Flags: review?(pavlov)
Comment on attachment 168941 [details] [diff] [review]
Incorporated comments from Darin, and more malloc optimisation.

See latest patch for the review!
Attachment #168941 - Flags: review?(pavlov)
Blocks: 92580
Comment on attachment 169278 [details] [diff] [review]
Per darin's comment, removed the fallback to 'calloc'

GIF2.h:114    int ipass;		  /* Interlace pass; Ranges 1-4 if
interlaced. */

Please modify this comment to explain 0 is non-interlaced.

+      /* Do we already have enough data in the accumulation
+	  buffer to satisfy the request ?  (This can happen
+	  after we transition from the gif_delay state.) */

This comment refers to a const that has been removed.

The memory allocation stuff will take me a bit longer to digest.  

Ultimately pav will have to decide whether it's wise to remove netscape
extension #2.  While I don't fully understand it myself, wouldn't it be
possible right now for a GIF to request that all its data be available before
the images is decoded?	Without the extension, the gif author would lose that
ability.  Please correct me if I misinterpreted what this extension is
accomplishing.
Thanks for the review sofar.
I've assimilated the first two comments.

About the Netscape extension:
I've had a lot of thought and research on this.
It seems that there are no GIF images at all using this.
Furthermore, the extension is very rarely described.
No image creation applications are using this.
But the most important reason to remove it, is that
it is 'unsafe'. One can add this extension to an image, requesting
a very large 'read-ahead' (say about 2GB), which then is all allocated
and tried to filled from the stream, which may cause problems in the application
(and even OS).

So, this is a very strong case to remove it. It is not used, doesn't have any
visible impact, and can cause 'buffer overflow / memory overflow', when the
extension is misused. 
Attachment #169278 - Flags: review?(pavlov)
Attachment #169278 - Attachment is obsolete: true
Attachment #171477 - Flags: review?(pavlov)
I don't think we want to remove the netscape extension support.
Comment on attachment 171477 [details] [diff] [review]
Incorporated comments from ArronM

Aaron, could you review this and let us know if you feel it might
be too risky to take right now as we're nearing the end of the 1.8 cycle?
Attachment #171477 - Flags: review?(pavlov) → review?(paper)
Comment on attachment 171477 [details] [diff] [review]
Incorporated comments from ArronM

The sheer size and amount of changes the patch has is reason enough to say it's
definitely not for 1.8.

-r due to pavlov's comments.
Attachment #171477 - Flags: review?(paper) → review-
I can agree with postponing it after 1.8.

However I don't agree with the Netscape extension.
To make the earlier argument against this extension more clear:
using this extension, one can easily create a GIF image with a request to
buffer upto 4GB bytes before decoding it. This means that the GIF decoder will
never end the decoding, and tries to build up an holding buffer of that size.
I have not yet tested this, but it is very likely that this will surely crash
the application.
Furthermore, the net effect of this extension is gone, because of the streaming
towards the decoder. There is no usefull effect of it, and no image creation
program can produce this extension. It is not a standard extension, and only
documented as being proposed by Netscape around version Netscape 2.1, but it is
never formally released.

So, normally when it doesn't harm, we would leave such backwards compatibility
things such as this 'netscape extension' in. However, it can do serious harm, so
let's remove it.
>I have not yet tested this, but it is very likely that this will surely crash
>the application.

that would be a bug. mozilla should not crash if a memory allocation fails.
Summary: Convert 3 malloc's to 1. → GIF Decoder: Convert many malloc's to 1, also remove unsafe netscape extension
Compile and run this. It takes an c:\tmp\error.gif and creates an
c:\tmp\error2.gif with the NETSCAPE2.0 wait_for_fullness extension inserted.
I have tested the support of the NETSCAPE2.0 extension with the old code and the
new code. Luckely it doesn't crash mozilla but mozilla won't display the image
either.
With the new code, mozilla is able to correctly read, parse, and display the image.

IE, IrfanView, PaintshopPro can all load the extended gif image, but
mozilla/firefox refuses to display it at all (it does not even 'broken image' ) 

Further analysis of the code confirms me that the extension is not supported at
all, it doesn't work, and prevents the otherwise valid image to display.

So, let's remove something which is not working anyway, and prevent issues later
with this extension.  Anyway I didn't really remove it, I only changed it into a
'NOP'. 

So, requesting re-review, as all other comments have been incorporated.
Summary: GIF Decoder: Convert many malloc's to 1, also remove unsafe netscape extension → GIF Decoder: Convert many malloc's to 1, also remove broken netscape extension
Comment on attachment 171477 [details] [diff] [review]
Incorporated comments from ArronM

Even not for 1.8, let's still review it.
Attachment #171477 - Flags: review- → review?(paper)
Comment on attachment 171477 [details] [diff] [review]
Incorporated comments from ArronM

I agree it should be reviewed, but not by me.  This is definitely more of a
Stuart review, since he has concerns about the extension, and knows more about
the decoding process than I do.

Re-assigning review :)
Attachment #171477 - Flags: review?(paper) → review?(pavlov)
Added bug 105370 to the 'block' list, as the identified MLK (the calloc at
GIF2.cpp:1017) is fixed with this patch as well.
Blocks: 105370
This patch saves even more code (now in total more than 5K on a windows
optimized build for just the GIF decoder).

The main difference with the last one, is that the whole 'gather' construct is
replaced with one 'hold' buffer of fixed size (3*256 bytes), and that instead
of increating the gathering in state engine, the entry and exit points of
GifWrite take care of 'hold' buffer, as the only function is to move not yet
parsed bytes from one GifWrite call to the next.

This also speeds up the parsing as in the old case between each state, the
gather_state was called upon, and now the state engine directly switches from
gif_image_header to the next valid state, if there are enough bytes in the
buffer. If not the remaining bytes are put in the hold, awaiting the next call
to GifWrite.

Also merged consume_comment with skip_block, as they did the same thing:
skipping the blocks... 

Tested with a wide range of static and animated gif files (upto 6MB).
Attachment #171477 - Attachment is obsolete: true
To stress the importancy of this patch:
* Not only it saves code and footprint, but it also speeds up the loading of
large animated GIFs.
* But even more importantly it reduces 7 dynamic allocated (and often
reallocated buffers to 3 (rowbuf, global_colormap and local_colormap) once
allocated per image (possibly enlarged for next frames).
* Even more: each GifWrite caused in the old situation at least one malloc and
one realloc for the 'gathering', now it is only one static buffer.
* Even more: local_colormap is now only allocated once and only enlarged when
needed for all frames within an animation.

So, this reduces memory fragmentation a lot, and even reduces the change on
MLK's. With the old code it does seem to happen sometimes (bug 105370).
Attachment #171477 - Flags: review?(pavlov)
Comment on attachment 175330 [details] [diff] [review]
Updated version, using fixed buffer of holding block between GifWrite's

Moved review request to latest patch version.
Attachment #175330 - Flags: review?(pavlov)
Additional changes:
* Now also global_colormap is a fixed buffer, and directly copied into from the
input stream (saves copy through hold buffer)
* Also local_colormap is directly assembled in its (dynamically allocated)
colormap
* Remove BackgroundColor as it isn't used at all
* Optimized same function signatures

Some statistics:
		    Before			Alloc4
Startup 	    8 allocs, 17424 bytes	4 allocs, 17628 bytes
Loading dir:	    119 allocs, ± 17500 bytes	16 allocs, ±17700 bytes per
image
Loading aniGif.gif: 40 allocs, 17509 bytes	4 allocs, 17843 bytes
Loading tholen.gif  37 allocs, 19285 bytes	3 allocs, 19234 bytes

Note: Each alloc also some overhead, so the actual memory usage is much more 

In summary, each GIF decoding now takes at most 4 allocs (not counting the
allocations by gfxImageFrame and imgContainer), instead of 8 +
2*number_of_4K_input_stream_crossings + number_of_frames.

Some time measurements:
		    Before			Alloc4
Startup (loading throbber.gif):
		    21				6
Loading techno_moogle_dance_party_by_the_darkmoogle.gif:
		    1748			1291
Loading galaxy_anim_short.mov2.gif:	
		    237537			218299

Note, measured with PRTimeInterval on WinXP, so numbers are in itself
meaningless, but the difference is interesting: between 10% and 30% faster
image decoding.
Attachment #175330 - Flags: review?(pavlov)
Comment on attachment 175923 [details] [diff] [review]
Even more memory and code size optimization

Moving review request to latest patch version. See also the included benchmark
data between the old situation and the latest patch version.
Attachment #175923 - Flags: review?(pavlov)
Comment on attachment 175923 [details] [diff] [review]
Even more memory and code size optimization

You're combining too many changes into a single patch.	Mozilla's
gif decoder has been battle hardened by years of exposure, so
we take changes to it pretty seriously.  A patch doing lots of
unrelated changes makes it hard to give a full review.	Please
split your work into logical stages.
Attachment #175923 - Flags: superreview-
Attachment #175923 - Flags: review?(pavlov)
Attached patch Do only the malloc optimisation. (obsolete) — Splinter Review
Reverted to the level of 2005-01-17, as reviewed by Darin and ArronM.
This one should be 'easier' to review.
Attachment #175330 - Attachment is obsolete: true
Attachment #175923 - Attachment is obsolete: true
Attachment #175938 - Flags: review?(tor)
Comment on attachment 175938 [details] [diff] [review]
Do only the malloc optimisation.

This version of the patch still combines your allocation changes with
modifications to the state machine and other miscellaneous code
tweaks.  While we like code cleanup, it should be seperated from other
changes.

Please don't feel as though you're being singled out for these sort of
comments; new mozilla contributors often run into this.  Unfortunately
the mozilla review process generates a bit of a viscious cycle -
reviews take a while, so contributors want to put more into their
patch to reduce the number of reviews they need to chase, which slows
the review, etc...
Attachment #175938 - Flags: review?(tor) → review-
This version only contains the following malloc changes:
* stack, prefix and suffix of the lzw decoding from alloc to array as part of 
gif_struct
* Moved RecyclingAllocator from gif2.cpp to nsGIFdecoder.cpp where it used for
the full gifstruct allocation, instead of three items stack, prefix and suffix.

* global_colormap as an array part of gif_struct: is always used, and never
larger than 768 bytes.
* mRGBLine and mAlphaLine: only REALLOC when it needs to be bigger instead of
always (generally it will be same or smaller (first frame is generally the
largests)).
* Remove 'request_buffer_fullness' as it doesn't work (image will not show up,
and see testcase above, and can potentially generate a very large memory
allocation (as large as the full image source file).
* Removed unused member 'control_extension' (only set once, never used).
* Changed a few bools into PRPackedBools (as asked by jst)
Attachment #175938 - Attachment is obsolete: true
Attached patch Two dirty patch lines removed... (obsolete) — Splinter Review
Attachment #176042 - Attachment is obsolete: true
Attachment #176044 - Flags: review?(tor)
Comment on attachment 176044 [details] [diff] [review]
Two dirty patch lines removed...

>--- modules/libpr0n/decoders/gif/GIF2.cpp	9 Jun 2004 18:36:25 -0000	1.51
>+++ modules/libpr0n/decoders/gif/GIF2.cpp	2 Mar 2005 15:40:49 -0000
>+  // Clear out the structure, excluding the arrays
>+  memset(gs, 0, (int)((char*)&((gif_struct*)0)->stack) );

Include stddef.h and use "offsetof(gif_struct, stack)".

>@@ -406,20 +422,17 @@
> {
>   nsGIFDecoder2* decoder = NS_STATIC_CAST(nsGIFDecoder2*, aClientData);
>   PRUint32 bpr, abpr;
>+
>   // We have to delay allocation of the image frame until now because
>-  // we won't have control block info (transparency) until now. The conrol
>+  // we won't have control block info (transparency) until now. The control
>   // block of a GIF stream shows up after the image header since transparency
>   // is added in GIF89a and control blocks are how the extensions are done.
>   // How annoying.
>   if(! decoder->mImageFrame) {
>-    gfx_format format = gfxIFormats::RGB;
>-    if (decoder->mGIFStruct->is_transparent) {
>-      format = gfxIFormats::RGB_A1;
>-    }
>-
> #if defined(XP_WIN) || defined(XP_OS2) || defined(XP_BEOS) || defined(MOZ_WIDGET_PHOTON)
>-    // XXX this works...
>-    format += 1; // RGB to BGR
>+    gfx_format format = decoder->mGIFStruct->is_transparent ? gfxIFormats::BGR_A1 : gfxIFormats::BGR;
>+#else
>+    gfx_format format = decoder->mGIFStruct->is_transparent ? gfxIFormats::RGB_A1 : gfxIFormats::RGB;
> #endif
> 
>     // initalize the frame and append it to the container

Remove this chunk from your patch.
Added the use of 'offsetof' (much nicer indeed),
and remove the patch chunk fixing the typo and the 'XXX this works' thing.
Attachment #176044 - Attachment is obsolete: true
Attachment #176044 - Flags: review?(tor)
Comment on attachment 176122 [details] [diff] [review]
Comments from tor incorporated

Note, the removal of '#include "prtypes.h" was not intentional, but it compiles
and work, but may be other platform will still require it?
Attachment #176122 - Flags: review?(tor)
Attachment #176122 - Flags: review?(tor) → review+
Attachment #176122 - Flags: superreview?(tor)
Comment on attachment 176122 [details] [diff] [review]
Comments from tor incorporated

>+    PRUint8   stack[MAX_BITS];      /* Base of decoder stack */
>+    PRUint16  prefix[MAX_BITS];
>+    PRUint8   suffix[MAX_BITS];
>+    PRUint8   global_colormap[3*MAX_COLORS];   /* Default colormap if local not supplied, 3 bytes for each color  */

Since MAX_BITS is odd, for maximum packing this should be reordered prefix,
global_colormap,
stack, suffix (flip last two to taste), with the appropriate corresponding
change to GIFInit.
sr=tor with that change.

Add -p to your diff options in the future.
Attachment #176122 - Flags: superreview?(tor) → superreview+
Changed order of arrays to: prefix, suffix, stack and global_colormap, as
prefix is the only one with even size, others are all odd.
Checking in GIF2.cpp;
/cvsroot/mozilla/modules/libpr0n/decoders/gif/GIF2.cpp,v  <--  GIF2.cpp
new revision: 1.52; previous revision: 1.51
done
Checking in GIF2.h;
/cvsroot/mozilla/modules/libpr0n/decoders/gif/GIF2.h,v  <--  GIF2.h
new revision: 1.20; previous revision: 1.19
done
Checking in nsGIFDecoder2.cpp;
/cvsroot/mozilla/modules/libpr0n/decoders/gif/nsGIFDecoder2.cpp,v  <-- 
nsGIFDecoder2.cpp
new revision: 1.65; previous revision: 1.64
done
Checking in nsGIFDecoder2.h;
/cvsroot/mozilla/modules/libpr0n/decoders/gif/nsGIFDecoder2.h,v  <-- 
nsGIFDecoder2.h
new revision: 1.25; previous revision: 1.24
done
Status: NEW → RESOLVED
Closed: 15 years ago
Resolution: --- → FIXED
Attachment #176985 - Flags: review+
Code is committed and verified to be working as designed
Status: RESOLVED → VERIFIED
Good Job, Alfred Kayser.
You need to log in before you can comment on or make changes to this bug.