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

[Andreas Cadhalpun]

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