8000 Vorbis: don't take quadratic time to open a file with large headers by sjoblomj · Pull Request #1188 · mackron/miniaudio · GitHub
[go: up one dir, main page]
Skip to content

Vorbis: don't take quadratic time to open a file with large headers - #1188

Closed
sjoblomj wants to merge 1 commit into
mackron:devfrom
sjoblomj:non-quadratic-time
Closed

Vorbis: don't take quadratic time to open a file with large headers#1188
sjoblomj wants to merge 1 commit into
mackron:devfrom
sjoblomj:non-quadratic-time

Conversation

@sjoblomj
@sjoblomj sjoblomj commented Nov 2, 2026
Copy link
Copy Markdown
Contributor

Base branch: dev. The same lines are on dev-0.12, and the change applies to them unchanged.

Summary

When a Vorbis file is opened through callbacks, ma_stbvorbis_init_internal_decoder_push() reads it 4 KiB at a time, and after each read it calls stb_vorbis_open_pushdata() again. That function starts over from the beginning of the data each time. So the number of calls grows with the size of the headers, and so does the work per call, which makes opening take quadratic time.

The file doesn't need to be unusual for this to matter. Comment headers hold embedded cover art, which can be a few MiB. With a 4 MiB comment, ma_decoder_init() takes 17 seconds at -O2. ma_sound_init_from_file() goes through the same code, by way of the VFS. This is on the thread that opens the file, unless the sound is loaded asynchronously.

ma_stbvorbis_init_file() and ma_stbvorbis_init_memory() use stb_vorbis's pull API, so they aren't affected.

The fix

Double the buffer instead of adding 4 KiB to it, so the number of calls is logarithmic and the total work is linear.

Two other changes are needed to make that safe:

  • Grow only when the buffer is full. The old code grew it on every pass, even after a short read. With doubling, a callback that returns a few bytes at a time would reach gigabytes after about 20 reads.
  • Accept MA_AT_END along with data. Reads are now larger, so they're more likely to reach the end of the file. A callback may return MA_AT_END with the last bytes it read, and the old code treated that as a failure. That rarely mattered with 4 KiB reads, but with larger reads it would stop some files that open today from opening. Now those bytes are used, and only a read that returns nothing ends the loop.

That last condition also covers a callback that returns 0 bytes and MA_SUCCESS at the end of the file. Growing only when full would otherwise turn that into an infinite loop. It already didn't return in practice, since the old loop kept growing the buffer instead.

The buffer can be up to twice the size of the headers while opening. For a 1 MiB comment, peak memory goes from 2068 KiB to 3072 KiB.

Reproduction

The program takes data/48000-stereo.ogg, rewrites it with a comment of the given size, opens it through callbacks and decodes the first frames. Run it from the root of the repository.

/* Opens data/48000-stereo.ogg through callbacks, with comment headers of increasing size. */
#define STB_VORBIS_HEADER_ONLY
#include "extras/stb_vorbis.c"
#define MINIAUDIO_IMPLEMENTATION
#include "miniaudio.h"
#undef STB_VORBIS_HEADER_ONLY
#include "extras/stb_vorbis.c"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct { const ma_uint8* pData; size_t size; size_t pos; int reads; } stream;

static ma_result on_read(ma_decoder* pDecoder, void* pOut, size_t bytesToRead, size_t* pBytesRead)
{
    stream* pStream = (stream*)pDecoder->pUserData;
    size_t remaining = pStream->size - pStream->pos;
    size_t n = (bytesToRead < remaining) ? bytesToRead : remaining;

    memcpy(pOut, pStream->pData + pStream->pos, n);
    pStream->pos += n;
    pStream->reads += 1;
    *pBytesRead = n;
    return (n == 0) ? MA_AT_END : MA_SUCCESS;
}

static ma_result on_seek(ma_decoder* pDecoder, ma_int64 offset, ma_seek_origin origin)
{
    stream* pStream = (stream*)pDecoder->pUserData;
    pStream->pos = (origin == ma_seek_origin_start) ? (size_t)offset : (size_t)((ma_int64)pStream->pos + offset);
    return MA_SUCCESS;
}

/* Appends an Ogg page. stb_vorbis doesn't check the CRC when opening or reading from the start, so it's left at 0. */
static size_t put_page(ma_uint8* pOut, int flags, const ma_uint8* pLacing, int segments, const ma_uint8* pBody, size_t bodySize)
{
    memset(pOut, 0, 27);
    memcpy(pOut, "OggS", 4);
    pOut[5] = (ma_uint8)flags;
    pOut[26] = (ma_uint8)segments;
    memcpy(pOut + 27, pLacing, segments);
    memcpy(pOut + 27 + segments, pBody, bodySize);
    return 27 + (size_t)segments + bodySize;
}

/* Rewrites an Ogg Vorbis file so that it has a comment of the given size. */
static ma_uint8* with_comment(const ma_uint8* pIn, size_t inSize, size_t commentSize, size_t* pOutSize)
{
    ma_uint8* pHeaders = (ma_uint8*)malloc(inSize);
    size_t packetStart[4], headersSize = 0, pos = 0, vendorSize, commSize, setupSize, bodySize, done, outSize = 0, i;
    int packets = 0, segments;
    ma_uint8* pOut;
    ma_uint8* pBody;
    ma_uint8* pLacing;
    ma_uint32 u;

    /* Gather the three header packets. */
    packetStart[0] = 0;
    while (packets < 3) {
        int n = pIn[pos + 26], iSeg;
        const ma_uint8* pSeg = pIn + pos + 27;
        const ma_uint8* pSrc = pSeg + n;
        for (iSeg = 0; iSeg < n; iSeg += 1) {
            memcpy(pHeaders + headersSize, pSrc, pSeg[iSeg]);
            headersSize += pSeg[iSeg];
            pSrc += pSeg[iSeg];
            if (pSeg[iSeg] < 255) {
                packets += 1;
                packetStart[packets] = headersSize;
            }
        }
        pos = (size_t)(pSrc - pIn);
    }

    memcpy(&u, pHeaders + packetStart[1] + 7, 4);
    vendorSize = u;
    setupSize = packetStart[3] - packetStart[2];
    commSize = 7 + 4 + vendorSize + 4 + 4 + commentSize + 1;

    /* The new comment packet, followed by the setup packet. */
    bodySize = commSize + setupSize;
    pBody = (ma_uint8*)malloc(bodySize);
    memcpy(pBody, pHeaders + packetStart[1], 7 + 4 + vendorSize);
    done = 7 + 4 + vendorSize;
    u = 1; memcpy(pBody + done, &u, 4); done += 4;
    u = (ma_uint32)commentSize; memcpy(pBody + done, &u, 4); done += 4;
    memset(pBody + done, 'a', commentSize); pBody[done + 1] = '=';
    done += commentSize;
    pBody[done] = 1;
    memcpy(pBody + commSize, pHeaders + packetStart[2], setupSize);

    /* Lacing values for those two packets. */
    segments = (int)(commSize / 255) + 1 + (int)(setupSize / 255) + 1;
    pLacing = (ma_uint8*)malloc((size_t)segments);
    memset(pLacing, 255, (size_t)segments);
    pLacing[commSize / 255] = (ma_uint8)(commSize % 255);
    pLacing[segments - 1] = (ma_uint8)(setupSize % 255);

    pOut = (ma_uint8*)malloc(inSize + bodySize + (bodySize / 255 / 255 + 2) * 300);

    {
        ma_uint8 lacing[1];
        lacing[0] = (ma_uint8)(packetStart[1] - packetStart[0]);
        outSize += put_page(pOut + outSize, 2, lacing, 1, pHeaders, packetStart[1]);
    }

    done = 0;
    for (i = 0; i < (size_t)segments; i += 255) {
        int n = ((size_t)segments - i < 255) ? (int)((size_t)segments - i) : 255, j;
        size_t size = 0;
        for (j = 0; j < n; j += 1) {
            size += pLacing[i + j];
        }
        outSize += put_page(pOut + outSize, (i > 0 && pLacing[i - 1] == 255) ? 1 : 0, pLacing + i, n, pBody + done, size);
        done += size;
    }

    /* The audio pages are unchanged. */
    memcpy(pOut + outSize, pIn + pos, inSize - pos);
    outSize += inSize - pos;

    free(pHeaders);
    free(pBody);
    free(pLacing);
    *pOutSize = outSize;
    return pOut;
}

/* Opens through callbacks and decodes the first frames. Returns a hash of them. */
static ma_uint32 open_and_decode(const ma_uint8* pData, size_t size, const char* pName)
{
    static float frames[4096 * 2];
    stream s;
    ma_decoder_config config = ma_decoder_config_init(ma_format_f32, 0, 0);
    ma_decoder decoder;
    ma_timer timer;
    ma_result result;
    double seconds;
    ma_uint64 framesRead, total = 0;
    ma_uint32 hash = 2166136261u;
    int i;

    s.pData = pData; s.size = size; s.pos = 0; s.reads = 0;

    ma_timer_init(&timer);
    config.encodingFormat = ma_encoding_format_vorbis;
    result = ma_decoder_init(on_read, on_seek, &s, &config, &decoder);
    seconds = ma_timer_get_time_in_seconds(&timer);

    printf("%-16s %-10s %8.3f s %8d reads", pName, ma_result_description(result), seconds, s.reads);
    if (result != MA_SUCCESS) {
        printf("\n");
        return 0;
    }

    for (i = 0; i < 16; i += 1) {
        size_t iByte;
        ma_decoder_read_pcm_frames(&decoder, frames, 2048, &framesRead);
        for (iByte = 0; iByte < framesRead * sizeof(float) * decoder.outputChannels; iByte += 1) {
            hash = (hash ^ ((const ma_uint8*)frames)[iByte]) * 16777619u;
        }
        total += framesRead;
    }

    printf(" %8d frames, hash %08x\n", (int)total, (unsigned int)hash);
    ma_decoder_uninit(&decoder);
    return hash;
}

#ifndef OGG_LARGE_COMMENT_NO_MAIN
int main(void)
{
    static const int sizesInKiB[] = { 0, 256, 1024, 4096 };
    FILE* pFile = fopen("data/48000-stereo.ogg", "rb");
    ma_uint8* pIn;
    size_t inSize;
    int i;

    if (pFile == NULL) {
        printf("Run this from the root of the repository.\n");
        return 1;
    }

    fseek(pFile, 0, SEEK_END);
    inSize = (size_t)ftell(pFile);
    fseek(pFile, 0, SEEK_SET);
    pIn = (ma_uint8*)malloc(inSize);
    inSize = fread(pIn, 1, inSize, pFile);
    fclose(pFile);

    open_and_decode(pIn, inSize, "original");

    for (i = 0; i < 4; i += 1) {
        char name[32];
        size_t size;
        ma_uint8* pOut = with_comment(pIn, inSize, (size_t)sizesInKiB[i] * 1024 + 2, &size);
        sprintf(name, "comment %d KiB", sizesInKiB[i]);
        open_and_decode(pOut, size, name);
        free(pOut);
    }

    free(pIn);
    return 0;
}
#endif
gcc ogg_large_comment.c -o ogg_large_comment -std=c99 -O2 -Wall -Wextra -lm -lpthread -ldl
./ogg_large_comment

It has to be built as C99 or later, as stb_vorbis.c isn't C89.

Before, on 877ea4a:

original         No error      0.001 s        2 reads    32768 frames, hash 4e4df19e
comment 0 KiB    No error      0.001 s        2 reads    32768 frames, hash 4e4df19e
comment 256 KiB  No error      0.073 s       66 reads    32768 frames, hash 4e4df19e
comment 1024 KiB No error      1.149 s      259 reads    32768 frames, hash 4e4df19e
comment 4096 KiB No error     17.400 s     1030 reads    32768 frames, hash 4e4df19e

After:

original         No error      0.001 s        2 reads    32768 frames, hash 4e4df19e
comment 0 KiB    No error      0.001 s        2 reads    32768 frames, hash 4e4df19e
comment 256 KiB  No error      0.014 s        8 reads    32768 frames, hash 4e4df19e
comment 1024 KiB No error      0.049 s       10 reads    32768 frames, hash 4e4df19e
comment 4096 KiB No error      0.178 s       12 reads    32768 frames, hash 4e4df19e

The hash is the same throughout, so the audio doesn't change.

@mackron
mackron commented Nov 2, 2026
Copy link
Copy Markdown
Owner

Support for stb_vorbis is being removed in a future version and I'm no longer doing maintenance on it. It's recommended you use the libvorbis custom decoder in extras/decoders/libvorbis/.

@mackron mackron closed this Nov 2, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

@sjoblomj @mackron
0