[FFmpeg-devel] MULTI VLC decoding boost

Patches attached.

Thanks for kurosu for pointing unmerged branches.

The UNCACHED_PATH for x86_32 is broken with this for 2 codecs it touches.
Fix is trivial, to be fixed later.

Will apply soon.

On Mon, Aug 28, 2023 at 07:36:17PM +0200, Paul B Mahol wrote:
> Patches attached.
> 
> Thanks for kurosu for pointing unmerged branches.
> 
> The UNCACHED_PATH for x86_32 is broken with this for 2 codecs it touches.
> Fix is trivial, to be fixed later.
[...]

> +int ff_init_vlc_multi_from_lengths(VLC *vlc, VLC_MULTI *multi, int nb_bits, int nb_elems,
> +		                   int nb_codes, const int8_t *lens, int lens_wrap,
> +                                   const void *symbols, int symbols_wrap, int symbols_size,
> +                                   int offset, int flags, void *logctx)
> +{
> +    VLCcode localbuf[LOCALBUF_ELEMS], *buf = localbuf;
> +    uint64_t code;
> +    int ret, j, len_max = FFMIN(32, 3 * nb_bits);
> +
> +    ret = vlc_common_init(vlc, nb_bits, nb_codes, &buf, flags);
> +    if (ret < 0)
> +        return ret;
> +
> +    multi->table = av_malloc(sizeof(*multi->table) << nb_bits);
> +    if (!multi->table)
> +        return AVERROR(ENOMEM);
> +
> +    j = code = 0;
> +    for (int i = 0; i < nb_codes; i++, lens += lens_wrap) {
> +        int len = *lens;
> +        if (len > 0) {
> +            unsigned sym;
> +
> +            buf[j].bits = len;
> +            if (symbols)
> +                GET_DATA(sym, symbols, i, symbols_wrap, symbols_size)
> +            else
> +                sym = i;
> +            buf[j].symbol = sym + offset;
> +            buf[j++].code = code;
> +        } else if (len <  0) {
> +            len = -len;
> +        } else
> +            continue;
> +        if (len > len_max || code & ((1U << (32 - len)) - 1)) {
> +            av_log(logctx, AV_LOG_ERROR, "Invalid VLC (length %u)\n", len);
> +            goto fail;
> +        }
> +        code += 1U << (32 - len);
> +        if (code > UINT32_MAX + 1ULL) {
> +            av_log(logctx, AV_LOG_ERROR, "Overdetermined VLC tree\n");
> +            goto fail;
> +        }
> +    }
> +    ret = vlc_common_end(vlc, nb_bits, j, buf, flags, localbuf);
> +    if (ret < 0)
> +        goto fail;
> +    return vlc_multi_gen(multi->table, vlc, nb_elems, j, nb_bits, buf, logctx);
> +fail:
> +    if (buf != localbuf)
> +        av_free(buf);
> +    return AVERROR_INVALIDDATA;
> +}

this is copy and pasted from

int ff_vlc_init_from_lengths(VLC *vlc, int nb_bits, int nb_codes,

leading to code duplication, it would be better if you could
factor the duplication out

thx

[...]

On Fri, Sep 15, 2023 at 12:01 AM Michael Niedermayer <michael@niedermayer.cc>
wrote:

> On Mon, Aug 28, 2023 at 07:36:17PM +0200, Paul B Mahol wrote:
> > Patches attached.
> >
> > Thanks for kurosu for pointing unmerged branches.
> >
> > The UNCACHED_PATH for x86_32 is broken with this for 2 codecs it touches.
> > Fix is trivial, to be fixed later.
> [...]
>
> > +int ff_init_vlc_multi_from_lengths(VLC *vlc, VLC_MULTI *multi, int
> nb_bits, int nb_elems,
> > +                                int nb_codes, const int8_t *lens, int
> lens_wrap,
> > +                                   const void *symbols, int
> symbols_wrap, int symbols_size,
> > +                                   int offset, int flags, void *logctx)
> > +{
> > +    VLCcode localbuf[LOCALBUF_ELEMS], *buf = localbuf;
> > +    uint64_t code;
> > +    int ret, j, len_max = FFMIN(32, 3 * nb_bits);
> > +
> > +    ret = vlc_common_init(vlc, nb_bits, nb_codes, &buf, flags);
> > +    if (ret < 0)
> > +        return ret;
> > +
> > +    multi->table = av_malloc(sizeof(*multi->table) << nb_bits);
> > +    if (!multi->table)
> > +        return AVERROR(ENOMEM);
> > +
> > +    j = code = 0;
> > +    for (int i = 0; i < nb_codes; i++, lens += lens_wrap) {
> > +        int len = *lens;
> > +        if (len > 0) {
> > +            unsigned sym;
> > +
> > +            buf[j].bits = len;
> > +            if (symbols)
> > +                GET_DATA(sym, symbols, i, symbols_wrap, symbols_size)
> > +            else
> > +                sym = i;
> > +            buf[j].symbol = sym + offset;
> > +            buf[j++].code = code;
> > +        } else if (len <  0) {
> > +            len = -len;
> > +        } else
> > +            continue;
> > +        if (len > len_max || code & ((1U << (32 - len)) - 1)) {
> > +            av_log(logctx, AV_LOG_ERROR, "Invalid VLC (length %u)\n",
> len);
> > +            goto fail;
> > +        }
> > +        code += 1U << (32 - len);
> > +        if (code > UINT32_MAX + 1ULL) {
> > +            av_log(logctx, AV_LOG_ERROR, "Overdetermined VLC tree\n");
> > +            goto fail;
> > +        }
> > +    }
> > +    ret = vlc_common_end(vlc, nb_bits, j, buf, flags, localbuf);
> > +    if (ret < 0)
> > +        goto fail;
> > +    return vlc_multi_gen(multi->table, vlc, nb_elems, j, nb_bits, buf,
> logctx);
> > +fail:
> > +    if (buf != localbuf)
> > +        av_free(buf);
> > +    return AVERROR_INVALIDDATA;
> > +}
>
> this is copy and pasted from
>
> int ff_vlc_init_from_lengths(VLC *vlc, int nb_bits, int nb_codes,
>
> leading to code duplication, it would be better if you could
> factor the duplication out
>
> thx
>

-1


>
> [...]
>
> --
> Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
>
> "You are 36 times more likely to die in a bathtub than at the hands of a
> terrorist. Also, you are 2.5 times more likely to become a president and
> 2 times more likely to become an astronaut, than to die in a terrorist
> attack." -- Thoughty2
>
> _______________________________________________
> ffmpeg-devel mailing list
> ffmpeg-devel@ffmpeg.org
> https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
>
> To unsubscribe, visit link above, or email
> ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
>

On Mon, Aug 28, 2023 at 07:36:17PM +0200, Paul B Mahol wrote:
> Patches attached.
> 
> Thanks for kurosu for pointing unmerged branches.
> 


[...]

> +static void add_level(VLC_MULTI_ELEM *table, const int nb_elems,
> +		      const int num, const int numbits,
> +                      const VLCcode *buf,
> +                      uint32_t curcode, int curlen,
> +                      int curlimit, int curlevel,
> +                      const int minlen, const int max,
> +                      unsigned* levelcnt, VLC_MULTI_ELEM *info)
> +{

> +    if (nb_elems > 256 && curlevel > 2)
> +        return; // No room

this and


> +    for (int i = num-1; i > max; i--) {
> +        for (int j = 0; j < 2; j++) {
> +            int newlimit, sym;
> +            int t = j ? i-1 : i;
> +            int l = buf[t].bits;
> +            uint32_t code;
> +
> +            sym = buf[t].symbol;
> +            if (l > curlimit)
> +                return;
> +            code = curcode + (buf[t].code >> curlen);
> +            newlimit = curlimit - l;
> +            l  += curlen;
> +            if (nb_elems>256) AV_WN16(info->val+2*curlevel, sym);
> +            else info->val[curlevel] = sym&0xFF;
> +
> +            if (curlevel) { // let's not add single entries
> +                uint32_t val = code >> (32 - numbits);
> +                uint32_t  nb = val + (1U << (numbits - l));
> +                info->len = l;
> +                info->num = curlevel+1;
> +                for (; val < nb; val++)
> +                    AV_COPY64(table+val, info);
> +                levelcnt[curlevel-1]++;
> +            }
> +

> +            if (curlevel+1 < VLC_MULTI_MAX_SYMBOLS && newlimit >= minlen) {

this are 2 checks doing the same thing for 8 and 16 bit
what mess is this ?
for 8bit we have VLC_MULTI_MAX_SYMBOLS space (6) in the array so we skip beyond that
for 16bit we have VLC_MULTI_MAX_SYMBOLS/2 space which is 3 and the skip instead
is inside add_level() above with hardcoded litteral number
(nb_elems > 256 is a check for if its 8 or 16bit)

why is such totally hacked up code pushed with standing objections and no
review ?

yes, ill fix this one but i have the feeling this code has more surprises


> +                add_level(table, nb_elems, num, numbits, buf,
> +                          code, l, newlimit, curlevel+1,
> +                          minlen, max, levelcnt, info);
> +            }
> +        }
> +    }
> +}

[...]