Memory corruption when optimizing GIF

[CyberShadow]

Input files.

gifsicle --delay 2 --loop --optimize=9 --colors=256 video_000000.gif video_000001.gif video_000002.gif > out.gif

This sometimes crashes for me on Windows, but invariably crashes with more input files.

Running the same command under Valgrind reveals invalid memory access:

==21388== Memcheck, a memory error detector
==21388== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==21388== Using Valgrind-3.10.0.SVN and LibVEX; rerun with -h for copyright info
==21388== Command: /home/vladimir/gifsicle/src/gifsicle --delay 2 --loop --optimize=3 --colors=256 video_000000.gif video_000001.gif video_000002.gif
==21388== 
gifsicle: warning: trivial adaptive palette (only 230 colors in source)
==21388== Invalid read of size 1
==21388==    at 0x40FC68: get_used_colors16 (opttemplate.c:399)
==21388==    by 0x410188: create_subimages16 (opttemplate.c:540)
==21388==    by 0x413C17: optimize_fragments (optimize.c:483)
==21388==    by 0x4268ED: merge_and_write_frames (gifsicle.c:958)
==21388==    by 0x426BEF: output_frames (gifsicle.c:1029)
==21388==    by 0x429390: main (gifsicle.c:2005)
==21388==  Address 0x5999180 is not stack'd, malloc'd or (recently) free'd
==21388== 
==21388== Invalid write of size 1
==21388==    at 0x40FC8C: get_used_colors16 (opttemplate.c:400)
==21388==    by 0x410188: create_subimages16 (opttemplate.c:540)
==21388==    by 0x413C17: optimize_fragments (optimize.c:483)
==21388==    by 0x4268ED: merge_and_write_frames (gifsicle.c:958)
==21388==    by 0x426BEF: output_frames (gifsicle.c:1029)
==21388==    by 0x429390: main (gifsicle.c:2005)
==21388==  Address 0x5999180 is not stack'd, malloc'd or (recently) free'd
==21388== 
==21388== Invalid write of size 1
==21388==    at 0x40FC46: get_used_colors16 (opttemplate.c:398)
==21388==    by 0x410188: create_subimages16 (opttemplate.c:540)
==21388==    by 0x413C17: optimize_fragments (optimize.c:483)
==21388==    by 0x4268ED: merge_and_write_frames (gifsicle.c:958)
==21388==    by 0x426BEF: output_frames (gifsicle.c:1029)
==21388==    by 0x429390: main (gifsicle.c:2005)
==21388==  Address 0x59993e0 is not stack'd, malloc'd or (recently) free'd
==21388== 
==21388== Invalid read of size 2
==21388==    at 0x410715: create_out_global_map16 (opttemplate.c:684)
==21388==    by 0x413C23: optimize_fragments (optimize.c:484)
==21388==    by 0x4268ED: merge_and_write_frames (gifsicle.c:958)
==21388==    by 0x426BEF: output_frames (gifsicle.c:1029)
==21388==    by 0x429390: main (gifsicle.c:2005)
==21388==  Address 0x5878d00 is not stack'd, malloc'd or (recently) free'd
==21388== 
==21388== Invalid read of size 2
==21388==    at 0x41086E: create_out_global_map16 (opttemplate.c:702)
==21388==    by 0x413C23: optimize_fragments (optimize.c:484)
==21388==    by 0x4268ED: merge_and_write_frames (gifsicle.c:958)
==21388==    by 0x426BEF: output_frames (gifsicle.c:1029)
==21388==    by 0x429390: main (gifsicle.c:2005)
==21388==  Address 0x5878d00 is 16 bytes before a block of size 2,048 alloc'd
==21388==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21388==    by 0x4C2CF1F: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21388==    by 0x407504: Gif_Realloc (fmalloc.c:19)
==21388==    by 0x40789E: Gif_NewFullColormap (giffunc.c:95)
==21388==    by 0x41077B: create_out_global_map16 (opttemplate.c:691)
==21388==    by 0x413C23: optimize_fragments (optimize.c:484)
==21388==    by 0x4268ED: merge_and_write_frames (gifsicle.c:958)
==21388==    by 0x426BEF: output_frames (gifsicle.c:1029)
==21388==    by 0x429390: main (gifsicle.c:2005)
==21388== 
==21388== Invalid read of size 1
==21388==    at 0x410953: simple_frame_data16 (opttemplate.c:729)
==21388==    by 0x41110A: create_new_image_data16 (opttemplate.c:917)
==21388==    by 0x413C34: optimize_fragments (optimize.c:485)
==21388==    by 0x4268ED: merge_and_write_frames (gifsicle.c:958)
==21388==    by 0x426BEF: output_frames (gifsicle.c:1029)
==21388==    by 0x429390: main (gifsicle.c:2005)
==21388==  Address 0x5999780 is not stack'd, malloc'd or (recently) free'd
==21388== 
==21388== Invalid read of size 1
==21388==    at 0x410953: simple_frame_data16 (opttemplate.c:729)
==21388==    by 0x4109DB: transp_frame_data16 (opttemplate.c:751)
==21388==    by 0x4110EF: create_new_image_data16 (opttemplate.c:915)
==21388==    by 0x413C34: optimize_fragments (optimize.c:485)
==21388==    by 0x4268ED: merge_and_write_frames (gifsicle.c:958)
==21388==    by 0x426BEF: output_frames (gifsicle.c:1029)
==21388==    by 0x429390: main (gifsicle.c:2005)
==21388==  Address 0x58e51b0 is not stack'd, malloc'd or (recently) free'd
==21388== 
==21388== Invalid read of size 1
==21388==    at 0x410C49: transp_frame_data16 (opttemplate.c:823)
==21388==    by 0x4110EF: create_new_image_data16 (opttemplate.c:915)
==21388==    by 0x413C34: optimize_fragments (optimize.c:485)
==21388==    by 0x4268ED: merge_and_write_frames (gifsicle.c:958)
==21388==    by 0x426BEF: output_frames (gifsicle.c:1029)
==21388==    by 0x429390: main (gifsicle.c:2005)
==21388==  Address 0x58e51b0 is not stack'd, malloc'd or (recently) free'd
==21388== 
==21388== Invalid read of size 1
==21388==    at 0x410BED: transp_frame_data16 (opttemplate.c:816)
==21388==    by 0x4110EF: create_new_image_data16 (opttemplate.c:915)
==21388==    by 0x413C34: optimize_fragments (optimize.c:485)
==21388==    by 0x4268ED: merge_and_write_frames (gifsicle.c:958)
==21388==    by 0x426BEF: output_frames (gifsicle.c:1029)
==21388==    by 0x429390: main (gifsicle.c:2005)
==21388==  Address 0x58e51b0 is not stack'd, malloc'd or (recently) free'd
==21388== 
==21388== Invalid read of size 1
==21388==    at 0x410AC5: transp_frame_data16 (opttemplate.c:801)
==21388==    by 0x4110EF: create_new_image_data16 (opttemplate.c:915)
==21388==    by 0x413C34: optimize_fragments (optimize.c:485)
==21388==    by 0x4268ED: merge_and_write_frames (gifsicle.c:958)
==21388==    by 0x426BEF: output_frames (gifsicle.c:1029)
==21388==    by 0x429390: main (gifsicle.c:2005)
==21388==  Address 0x5bb3f70 is not stack'd, malloc'd or (recently) free'd
==21388== 
==21388== 
==21388== HEAP SUMMARY:
==21388==     in use at exit: 128 bytes in 1 blocks
==21388==   total heap usage: 324 allocs, 323 frees, 9,448,840 bytes allocated
==21388== 
==21388== LEAK SUMMARY:
==21388==    definitely lost: 0 bytes in 0 blocks
==21388==    indirectly lost: 0 bytes in 0 blocks
==21388==      possibly lost: 0 bytes in 0 blocks
==21388==    still reachable: 128 bytes in 1 blocks
==21388==         suppressed: 0 bytes in 0 blocks
==21388== Rerun with --leak-check=full to see details of leaked memory
==21388== 
==21388== For counts of detected and suppressed errors, rerun with: -v
==21388== ERROR SUMMARY: 678738 errors from 10 contexts (suppressed: 0 from 0)

Looking at:

==21388==    at 0x40FC68: get_used_colors16 (opttemplate.c:399)

The relevant line is:

      else if (need[data[x]] == 0)

it looks like data[x] is 256, however the need array is only as big as all_ncol, which is 230.

[CyberShadow]

I don't know what the problem is. The global background variable gets set to 256, which I assume is not a valid value. It ends up at 256 because unmark_colors_2 sets .pixel to 256, which later is propagated to background at the end of initialize_optimizer. unmark_colors_2 also sets .haspixel to 0, but that gets set back to 1 in mark_used_colors. I can't make sense of the whole thing.

[kohler]

What a dumb bug! In an checkin that sped up optimization for images with many colors (cdd7f23), I stopped storing the 1st color in the output colormap. That is now fixed. (3901edf) I'll leave this for you to close (assuming that you stop seeing crashes). Thanks for the report.

[CyberShadow]

Yep, that fixed it, thanks!