[FFmpeg-devel] [PATCH 2/3] [WIP] avcodec: add HVQM4 Video decoder

[Andreas Rheinhardt]

Paul B Mahol:
> Signed-off-by: Paul B Mahol <onemda at gmail.com>
> ---
>  libavcodec/Makefile     |    1 +
>  libavcodec/allcodecs.c  |    1 +
>  libavcodec/codec_desc.c |    7 +
>  libavcodec/codec_id.h   |    1 +
>  libavcodec/hvqm4.c      | 1719 +++++++++++++++++++++++++++++++++++++++
>  5 files changed, 1729 insertions(+)
>  create mode 100644 libavcodec/hvqm4.c
> 


> +static int read_trees(int index,
> +                      int length,
> +                      uint16_t code,
> +                      uint8_t *bits,
> +                      uint16_t *codes,
> +                      uint16_t *symbols,
> +                      GetBitContext *gb,
> +                      const uint32_t tree_signed,
> +                      const uint32_t tree_scale)
> +{
> +    if (get_bits1(gb) == 0) { // leaf node
> +        uint8_t byte = get_bits(gb, 8);
> +        int16_t symbol = byte;
> +
> +        if (tree_signed && byte > 0x7F)

Is the check "byte > 0x7F" actually is an improvement?

> +            symbol = (int8_t)byte;
> +
> +        symbol *= 1 << tree_scale;
> +        bits[index] = length;
> +        codes[index] = code;
> +        symbols[index] = symbol;
> +        index++;
> +        return index;
> +    } else { // recurse
> +        index = read_trees(index, length + 1,  code << 1, bits, codes, symbols, gb, tree_signed, tree_scale);
> +        index = read_trees(index, length + 1, (code << 1) + 1, bits, codes, symbols, gb, tree_signed, tree_scale);
> +        return index;
> +    }
> +}
> +
> +static int build_huff(GBCWithVLC *buf, uint32_t is_signed, uint32_t scale)
> +{
> +    const uint32_t tree_signed = is_signed;
> +    const uint32_t tree_scale = scale;
> +    uint8_t bits[256] = { 0 };
> +    uint16_t codes[256] = { 0 };
> +    uint16_t symbols[256] = { 0 };
> +    VLC *vlc = buf->vlc;
> +    int nb_codes;
> +
> +    ff_free_vlc(vlc);
> +    nb_codes = read_trees(0, 0, 0, bits, codes, symbols, &buf->gb, tree_signed, tree_scale);
> +
> +    return ff_init_vlc_sparse(vlc, ff_log2(nb_codes) + 3, nb_codes, bits, 1, 1,
> +                              codes, 2, 2, symbols, 2, 2, 0);
> +}
> +
1. The above code does not check against stack overflow or buffer
overflow; you are also not checking that your codes fit into 16bits.
2. I also don't get where your ff_log2(nb_codes) + 3 comes from.
3. The nodes are stored from left to right in the tree, so using
ff_init_vlc_sparse() is unnecessary; ff_init_vlc_from_lengths() can be
used like this (untested):

struct HuffTree {
    int nb_codes;
    uint8_t bits[256];
    uint16_t symbols[256];
} HuffTree;

static int read_trees(int length,
                      HuffTree *huff,
                      GetBitContext *gb,
                      const uint32_t tree_signed,
                      const uint32_t tree_scale)
{
    int ret;

    if (get_bits1(gb) == 0) { // leaf node
        uint8_t byte = get_bits(gb, 8);
        int16_t symbol = tree_signed ? (int8_t)byte : byte;

        symbol *= 1 << tree_scale;
        if (huff->nb_codes >= FF_ARRAY_ELEMS(huff->bits))
            return AVERROR_INVALIDDATA;
        huff->bits[huff->nb_codes]    = length;
        huff->symbols[huff->nb_codes] = symbol;
        huff->nb_codes++;
        return 0;
    } else { // recurse
        if (length == 16)
            return AVERROR_INVALIDDATA;
        ret = read_trees(length + 1, huff, gb, tree_signed, tree_scale);
        if (ret < 0)
            return ret;
        return read_trees(length + 1, huff, gb, tree_signed, tree_scale);
    }
}

static int build_huff(GBCWithVLC *buf, uint32_t is_signed, uint32_t scale)
{
    const uint32_t tree_signed = is_signed;
    const uint32_t tree_scale = scale;
    HuffTree huff;
    VLC *vlc = buf->vlc;
    int ret;

    huff.nb_codes = 0;

    ff_free_vlc(vlc);
    ret = read_trees(0, &huff, &buf->gb, tree_signed, tree_scale);
    if (ret < 0)
        return ret;

    return ff_init_vlc_from_lengths(vlc, ff_log2(huff.nb_codes) + 3,
huff.nb_codes,
                                    huff.bits, 1, huff.symbols, 2, 2,
                                    0, 0, NULL);
}

4. Is it legal for the tree to consists of only the root (which then has
length zero)? Our code for generating VLCs can't handle this at the
moment; I always pondered adding support for it (and somewhere I have a
stash entry for it), but never did it.

- Andreas