Repository navigation
stb_vorbis: slow loads caused by sorting c->sorted_codewords. #1249
Description
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.
Activity
[-]stb_vorbis: slow loads caused by sorting c->lookup_values.[/-][+]stb_vorbis: slow loads caused by sorting c->sorted_codewords.[/+]ericoporto commentedon Nov 7, 2023
Hey, just to check, the PR is indeed unrelated and it doesn't impact in the slow loading time reported here, right?
AliceLR commentedon Nov 7, 2023
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 withqsort, which might be fixable.stb_vorbis: Move CODEBOOK_LIMIT check up
rygorous commentedon Oct 27, 2026
I moved the
CODEBOOK_LIMITcheck further up so that we don't even create the sorted entries when the counts are huge. This limits the max number of sorted entries to CODEBOOK_LIMIT now, i.e. 256k, which while still not instant is a whole lot better than 16M. I'm tentatively tagging this "merged-dev" (meaning fix for this is merged in the dev branch), feel free to reopen if this isn't good enough.AliceLR commentedon Oct 27, 2026
I noticed adding
CODEBOOK_LIMITto #1960 improved fuzzing speed a bit so I'm not surprised it helps here too, thanks.#1174 should also make invalid files get rejected a little faster and would make it easier to fuzz (as libFuzzer hits those leaks a lot). (Also recommend #1172, #1312, #1487, #1490 if there's going to be an stb_vorbis release soon.)