Possible bug in giflib - long runtime

[andrew-epstein]

I'm filing this issue without full knowledge of whether this is actually a bug or not, but hopefully @schnaader can provide some insight. OS and compiler details are the same as #98.

The 32-byte file with the following hexdump:

0000000 47 49 46 38 39 61 df ff df ff f1 03 00 00 00 00
0000010 ff 00 00 ff ff 00 ff ff ff 2c f9 00 00 00 00 00
0000020

takes approximately 4 seconds to process on my system. The command line invocation:

./precomp -v 100

produces the following output:

Precomp v0.4.8 Unix 64-bit - DEVELOPMENT version - USE AT YOUR OWN RISK!
Free for non-commercial use - Copyright 2006-2019 by Christian Schneider
  preflate v0.3.5 support - Copyright 2018 by Dirk Steinke

Input file: 100
Output file: 100.pcf

Using packJPG for JPG recompression, packMP3 for MP3 recompression.
--> packJPG library v2.5k (01/22/2016) by Matthias Stirner / Se <--
--> packMP3 library v1.0g (01/22/2016) by Matthias Stirner <--
More about packJPG and packMP3 here: http://www.matthiasstirner.com

Compressing with LZMA, 12 threads, memory usage: 1981 MiB, block size: 24 MiB

(0.00%) Possible GIF found at position 0
New size: 107 instead of 32

Done.
Time: 4 second(s), 85 millisecond(s)

Recompressed streams: 0/0

The file doesn't cause a crash, so I don't have a stack trace. However, I ran precomp under lldb, waited 2-3 seconds, pressed Ctrl+C, and then observed the current stack. I repeated this several times, and the result was similar each time:

* thread #1, queue = 'com.apple.main-thread', stop reason = signal SIGSTOP
  * frame #0: 0x00000001008da146 libclang_rt.asan_osx_dynamic.dylib`__asan::QuarantineCallback::Recycle(__asan::AsanChunk*) + 182
    frame #1: 0x00000001008d9ffa libclang_rt.asan_osx_dynamic.dylib`__sanitizer::Quarantine<__asan::QuarantineCallback, __asan::AsanChunk>::DoRecycle(__sanitizer::QuarantineCache<__asan::QuarantineCallback>*, __asan::QuarantineCallback) + 266
    frame #2: 0x00000001008d9a49 libclang_rt.asan_osx_dynamic.dylib`__sanitizer::Quarantine<__asan::QuarantineCallback, __asan::AsanChunk>::Recycle(unsigned long, __asan::QuarantineCallback) + 361
    frame #3: 0x00000001008dbf0f libclang_rt.asan_osx_dynamic.dylib`__asan::Allocator::QuarantineChunk(__asan::AsanChunk*, void*, __sanitizer::BufferedStackTrace*) + 543
    frame #4: 0x00000001009423e0 libclang_rt.asan_osx_dynamic.dylib`wrap__ZdaPv + 352
    frame #5: 0x0000000100526bce precomp`decompress_gif(__sFILE*, __sFILE*, long long, int&, long long&, unsigned char&, GifCodeStruct*) at precomp.cpp:6000:7 [opt]
    frame #6: 0x0000000100526b36 precomp`decompress_gif(__sFILE*, __sFILE*, long long, int&, long long&, unsigned char&, GifCodeStruct*) [inlined] d_gif_result(ScreenBuff=0x000000012c516800, myGifFile=<unavailable>) at precomp.cpp:6150 [opt]
    frame #7: 0x0000000100526b36 precomp`decompress_gif(__sFILE*, __sFILE*, long long, int&, long long&, unsigned char&, GifCodeStruct*) [inlined] d_gif_error(ScreenBuff=0x000000012c516800, myGifFile=<unavailable>) at precomp.cpp:6155 [opt]
    frame #8: 0x0000000100526b36 precomp`decompress_gif(srcfile=0x00007fffb265f030, dstfile=0x00007fffb265f160, src_pos=0, gif_length=<unavailable>, decomp_length=0x00007ffeefbfdff0, block_size=0x00007ffeefbfdfd0, g=<unavailable>) at precomp.cpp:6197 [opt]
    frame #9: 0x000000010050598b precomp`try_decompression_gif(version=<unavailable>) at precomp.cpp:6320:8 [opt]
    frame #10: 0x00000001004bed22 precomp`compress_file(min_percent=0, max_percent=100) at precomp.cpp:4041:13 [opt]

and multiple times I saw the following:

* thread #1, queue = 'com.apple.main-thread', stop reason = signal SIGSTOP
  * frame #0: 0x00007fff7f840d09 libsystem_platform.dylib`_platform_memmove$VARIANT$Haswell + 41
    frame #1: 0x00000001009325db libclang_rt.asan_osx_dynamic.dylib`__asan_memcpy + 1131
    frame #2: 0x0000000100524bd7 precomp`decompress_gif(__sFILE*, __sFILE*, long long, int&, long long&, unsigned char&, GifCodeStruct*) at precomp.cpp:5993:5 [opt]
    frame #3: 0x0000000100524aa1 precomp`decompress_gif(srcfile=0x00007fffb265f030, dstfile=0x00007fffb265f160, src_pos=0, gif_length=<unavailable>, decomp_length=0x00007ffeefbfdff0, block_size=0x00007ffeefbfdfd0, g=<unavailable>) at precomp.cpp:6189 [opt]
    frame #4: 0x000000010050598b precomp`try_decompression_gif(version=<unavailable>) at precomp.cpp:6320:8 [opt]
    frame #5: 0x00000001004bed22 precomp`compress_file(min_percent=0, max_percent=100) at precomp.cpp:4041:13 [opt]

[schnaader]

Test file on Google Drive

[schnaader]

The problem is in the order of allocation and validation in the GIF code:

precomp-cpp/precomp.cpp

Lines 6216 to 6224 in 7ebe71c

	ScreenBuff = alloc_gif_screenbuf(myGifFile);
	if (!ScreenBuff) {
	DGifCloseFile(myGifFile);
	return false;
	}
	}
	if (DGifGetImageDesc(myGifFile) == GIF_ERROR) {
	return d_gif_error(ScreenBuff, myGifFile);

First it allocates memory for the screen buffer and fills it with the background color (in this case, the size is 65503x65503 bytes = ~4 GB, that's what takes so much time), but a bit later
DGifGetImageDesc returns an error and the buffer is freed. Swapping the order should solve the slowdown.

[andrew-epstein]

Confirmed, making that change reduces the runtime to approximately 0.1s