[FFmpeg-devel] [RFC v5] libavcodec: add a native Daala decoder

[Rostislav Pehlivanov]

>This can still overflow to -256 causing the following line to crash.
>A first step towards fixing this would be to replace '2*(*ex) >> 8'
>with '*ex >> 7'. That has the same result whenever the first expression
>is not undefined and should be faster, as well. ;)
>This prevents most of these crashes, but a few remain, because *ex
>can already be negative here due to a previous overflow.
Thanks for the feedback and the suggestion. I've fixed that as well as some
more bugs in the entropy decoding system. I've also switched to using
uint64_t for ent_win and uint32_t for ent_rng. This should hopefully make
the decoder more robust. There was no performance penalty (although a
comment in libdaala's code mentions performance gains with "fast 64 bit
arithmetic").

>To avoid this problem, this line could be replaced with:
>        *ex += (qg << 14) - (*ex >> 2);
Unfortunately that changes the result of the expectation value and causes
the decoder to go out of sync. I doubt that qg can overflow however, the
quantized gain values are usually far from INT_MAX/2;

>The width, height and pixel format can change in the middle of a stream,
>which currently causes segmentation faults due to out of bounds
>reads/writes.
I've written a new function which reinits the context and/or buffers in
case any of those change from frame to frame. It uses realloc so it should
be reasonably fast. Also I was able to remove the ugly 2D arrays and
replaced them with just a 1D array + a stride. This fixes some crashes when
reading the dering data.

You can see the changes on my repo: https://github.com/atomnuker/FFmpeg

Best regards,
Rostislav

On 3 January 2016 at 19:27, Andreas Cadhalpun <
andreas.cadhalpun at googlemail.com> wrote:

> On 02.01.2016 18:56, Rostislav Pehlivanov wrote:
> > --- /dev/null
> > +++ b/libavcodec/daala_entropy.h
> > @@ -0,0 +1,464 @@
> [...]
> > +/* Expectation value is in Q16 */
> > +static inline int daalaent_decode_generic(DaalaEntropy *e, DaalaCDF *c,
> int *ex,
> > +                                          int max, int integrate)
> > +{
> > +    int rval, lsb = 0, log_ex = daalaent_log_ex(*ex);
> > +    const int shift = FFMAX(0, (log_ex - 5) >> 1);
> > +    const int id = FFMIN(DAALAENT_MODEL_TAB - 1, log_ex);
> > +    const int ms = (max + (1 << shift >> 1)) >> shift;
> > +    int xs = (max == -1) ? 16 : FFMIN(ms + 1, 16);
> > +    ent_rng *cdf = &c->cdf[id*c->y];
> > +    if (!max)
> > +        return 0;
> > +    if ((xs = daalaent_decode_cdf(e, cdf, xs, 0, CDF_UNSCALED)) == 15) {
> > +        int g = ((2*(*ex) >> 8) + (1 << shift >> 1)) >> shift;
>
> This can still overflow to -256 causing the following line to crash.
> A first step towards fixing this would be to replace '2*(*ex) >> 8'
> with '*ex >> 7'. That has the same result whenever the first expression
> is not undefined and should be faster, as well. ;)
>
> This prevents most of these crashes, but a few remain, because *ex
> can already be negative here due to a previous overflow.
>
> > +        ent_win decay = FFMAX(2, FFMIN(254, 256*g/(g + 256)));
> > +        xs += daalaent_decode_laplace(e, decay, (max == -1) ? -1 : ms -
> 15);
> > +    }
> > +    if (shift) {
> > +        if (shift > !xs)
> > +            lsb = daalaent_decode_bits(e, shift - !xs);
> > +        lsb -= !!xs << (shift - 1);
> > +    }
> > +    rval = (xs << shift) + lsb;
> > +    daalaent_exp_model_update(c, ex, rval, xs, id, integrate);
> > +    return rval;
> > +}
>
> > --- /dev/null
> > +++ b/libavcodec/daala_pvq.h
> > @@ -0,0 +1,491 @@
> [...]
> > +static void daalapvq_decode_vector(DaalaEntropy *e, DaalaPVQ *pvq,
> > +                                   dctcoef *out, dctcoef *ref, const
> double beta,
> > +                                   uint8_t key_frame, int p, uint8_t
> *skip_rest,
> > +                                   uint8_t has_err, int band_idx,
> > +                                   int qm_off, enum DaalaBsize bsize)
> > +{
> > +    int i, k;
> > +    int qg = 0, skip = 0, itheta = (!!key_frame), has_ref = !key_frame;
> > +    double qcg, gain, theta = 0.0f, gr = 0.0f, gain_off = 0.0f;
> > +    dctcoef tmp[DAALAPVQ_MAX_PART_SIZE] = {0};
> > +
> > +    const int robust = has_err || key_frame;
> > +    const int band_len = pvq->size[band_idx];
> > +    const int16_t *qmatrix = &pvq->qmatrix[qm_off];
> > +    const int16_t *qmatrix_inv = &pvq->qmatrix_inv[qm_off];
> > +
> > +    if (!skip_rest[(band_idx + 2) % 3]) {
> > +        int iloc = (!!p)*DAALA_NBSIZES*DAALAPVQ_PARTITIONS_MAX +
> bsize*DAALAPVQ_PARTITIONS_MAX + band_idx;
> > +        i = daalaent_decode_cdf_adapt(e, &pvq->pvqtheta_gain_cdf, iloc,
> 8 + 7*pvq->skip[band_idx]);
> > +        if (!key_frame && i >= 10)
> > +            i++;
> > +        if (key_frame && i >= 8)
> > +            i++;
> > +        if (i >= 8) {
> > +            i -= 8;
> > +            skip_rest[0] = skip_rest[1] = skip_rest[2] = 1;
> > +        }
> > +        qg = i & 1;
> > +        itheta = (i >> 1) - 1;
> > +        has_ref = !(itheta == -1);
> > +    }
> > +    if (qg) {
> > +        int *ex = pvq->pvqgain_ex[p][bsize] + band_idx, ex_tmp = *ex;
> > +        DaalaCDF *mcdf = has_ref ? &pvq->pvqgain_ref_mcdf :
> &pvq->pvqgain_noref_mcdf;
> > +        qg = 1 + daalaent_decode_generic(e, mcdf, &ex_tmp, -1, 2);
> > +        *ex += ((qg << 16) - *ex) >> 2;
>
> Here is the other overflow that can cause above crash.
> To avoid this problem, this line could be replaced with:
>         *ex += (qg << 14) - (*ex >> 2);
>
> This illustrates quite well why I think that overflows should be fixed
> if reasonably possible, as they can cause weird problems in different
> parts of the code.
>
> > --- /dev/null
> > +++ b/libavcodec/daaladec.c
> > @@ -0,0 +1,824 @@
> [...]
> > +static int daala_decode_frame(AVCodecContext *avctx, void *data,
> > +                              int *got_frame, AVPacket *avpkt)
> > +{
> > +    int i, j, p, ret;
> > +    AVFrame *frame  = data;
> > +    DaalaContext *s = avctx->priv_data;
>
> The width, height and pixel format can change in the middle of a stream,
> which currently causes segmentation faults due to out of bounds
> reads/writes.
>
> It's probably possible to re-initialize the decoder for the new values,
> but until that is implemented there should be a check here preventing
> the crashes, e.g.:
>     if (avctx->width > s->width || avctx->height > s->height ||
> avctx->pix_fmt != s->fmt->fmt) {
>         av_log(avctx, AV_LOG_ERROR, "reinit not yet implemented (s:%dx%d
> %s; c:%dx%d %s)\n",
>                s->width, s->height, av_get_pix_fmt_name(s->fmt->fmt),
>                avctx->width, avctx->height,
> av_get_pix_fmt_name(avctx->pix_fmt));
>         return AVERROR_PATCHWELCOME;
>     }
>
> > --- /dev/null
> > +++ b/libavcodec/daaladsp.c
> > @@ -0,0 +1,1890 @@
>
> The code in this file still overflows quite often, but fixing above
> overflows
> also fixes a few of these. So maybe fixing all overflows outside this file
> will magically fix the overflows seen here, but that has to be
> investigated first.
> So I suggest to add a TODO comment here to look into/fix these overflows.
> If they turn out not to be reasonably fixable the comment could be replaced
> with an explanation of that.
>
> Best regards,
> Andreas
> _______________________________________________
> ffmpeg-devel mailing list
> ffmpeg-devel at ffmpeg.org
> http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
>