stb icon indicating copy to clipboard operation
stb copied to clipboard

stb_vorbis: slow loads caused by sorting c->sorted_codewords.

Open AliceLR opened this issue 3 years ago • 2 comments

Describe the bug When loading an ordered codebook with a large number of entries, stb_vorbis can take a very long time to sort the codebook in compute_sorted_huffman. This is due to using qsort (non-inlineable) on a very large array (which is implied to be pre-sorted? Not familiar enough with this part of the Vorbis spec) (edit: on further inspection it's only pre-sorted prior to bit reversal).

Like #1248, this might benefit from early filtering of absurd codebook entries*dimensions values that don't fit in the current packet. This sort is on c->sorted_entries entries, which is bounded by c->entries, so the number of multipliers stored in the packet should directly correspond to this. Otherwise, a sort where the compare can be inlined could help here.

To Reproduce Load any of these OGG files with stb_vorbis_decode_filename: OGG_slow_loads2.zip

Expected behavior stb_vorbis should not take several seconds each to reject these input files.

I originally reported this in #1174, but it's completely unrelated to that patch and deserves a separate issue.

AliceLR avatar Nov 18 '21 02:11 AliceLR

Hey, just to check, the PR is indeed unrelated and it doesn't impact in the slow loading time reported here, right?

ericoporto avatar Nov 07 '23 16:11 ericoporto

Correct. #1174 primarily adds EOF checks to start_decoder. This issue is that malicious or fuzzer-generated Vorbis files can create a large number of codewords that take 40+ seconds sort with qsort, which might be fixable.

AliceLR avatar Nov 07 '23 19:11 AliceLR