On Sat, Sep 26, 2020 at 12:27:54PM +0200, Andreas Rheinhardt wrote:
> The Ut video format uses Huffman trees which are only implicitly coded
> in the bitstream: Only the lengths of the codes are coded, the rest has
> to be inferred by the decoder according to the rule that the longer
> codes are to the left of shorter codes in the tree and on each level the
> symbols are descending from left to right.
>
> Because longer codes are to the left of shorter codes, one needs to know
> how many non-leaf nodes there are on each level in order to know the
> code of the next left-most leaf (which belongs to the highest symbol on
> that level). The current code does this by sorting the entries to be
> ascending according to length and (for entries with the same length)
> ascending according to their symbols. This array is then traversed in
> reverse order, so that the lowest level is dealt with first, so that the
> number of non-leaf nodes of the next higher level is known when
> processing said level.
>
> But this can also be calculated without sorting: Simply count how many
> leaf nodes there are on each level. Then one can calculate the number of
> non-leaf nodes on each level iteratively from the lowest level upwards:
> It is just half the number of nodes of the level below.
>
> This improves performance: For the sample from ticket #4044 the amount
> of decicycles for one call to build_huff() decreased from 1055489 to
> 446310 for Clang 10 and from 1080306 to 535155 for GCC 9.
>
> Signed-off-by: Andreas Rheinhardt <andreas.rheinha...@gmail.com>
> ---
> libavcodec/utvideo.c | 6 -----
> libavcodec/utvideo.h | 1 -
> libavcodec/utvideodec.c | 53 ++++++++++++++++++++---------------------
> 3 files changed, 26 insertions(+), 34 deletions(-)
>
ok, i guess fate passes.
> diff --git a/libavcodec/utvideo.c b/libavcodec/utvideo.c
> index 5828d5ec0d..b14e56e0d8 100644
> --- a/libavcodec/utvideo.c
> +++ b/libavcodec/utvideo.c
> @@ -39,9 +39,3 @@ int ff_ut_huff_cmp_len(const void *a, const void *b)
> const HuffEntry *aa = a, *bb = b;
> return (aa->len - bb->len)*256 + aa->sym - bb->sym;
> }
> -
> -int ff_ut10_huff_cmp_len(const void *a, const void *b)
> -{
> - const HuffEntry *aa = a, *bb = b;
> - return (aa->len - bb->len)*1024 + aa->sym - bb->sym;
> -}
> diff --git a/libavcodec/utvideo.h b/libavcodec/utvideo.h
> index cf0bb28c44..2975f287a7 100644
> --- a/libavcodec/utvideo.h
> +++ b/libavcodec/utvideo.h
> @@ -99,6 +99,5 @@ typedef struct HuffEntry {
>
> /* Compare huffman tree nodes */
> int ff_ut_huff_cmp_len(const void *a, const void *b);
> -int ff_ut10_huff_cmp_len(const void *a, const void *b);
>
> #endif /* AVCODEC_UTVIDEO_H */
> diff --git a/libavcodec/utvideodec.c b/libavcodec/utvideodec.c
> index f014e90606..8b47c14d98 100644
> --- a/libavcodec/utvideodec.c
> +++ b/libavcodec/utvideodec.c
> @@ -43,45 +43,44 @@
> static int build_huff(const uint8_t *src, VLC *vlc, int *fsym, unsigned
> nb_elems)
> {
> int i;
> - HuffEntry he[1024];
> - int last;
> uint32_t codes[1024];
> uint8_t bits[1024];
> - uint16_t syms[1024];
> - uint32_t code;
> + uint16_t codes_count[33] = { 0 };
>
> *fsym = -1;
> for (i = 0; i < nb_elems; i++) {
> - he[i].sym = i;
> - he[i].len = *src++;
> - }
> - qsort(he, nb_elems, sizeof(*he), ff_ut10_huff_cmp_len);
> + if (src[i] == 0) {
> + *fsym = i;
> + return 0;
> + } else if (src[i] == 255) {
> + bits[i] = 0;
> + } else if (src[i] <= 32) {
> + bits[i] = src[i];
> + } else
> + return AVERROR_INVALIDDATA;
>
> - if (!he[0].len) {
> - *fsym = he[0].sym;
> - return 0;
> + codes_count[bits[i]]++;
> }
> + if (codes_count[0] == nb_elems)
> + return AVERROR_INVALIDDATA;
>
> - last = nb_elems - 1;
> - while (he[last].len == 255 && last)
> - last--;
> -
> - if (he[last].len > 32) {
> - return -1;
> + for (unsigned i = 32, nb_codes = 0; i > 0; i--) {
> + uint16_t curr = codes_count[i]; // # of leafs of length i
> + codes_count[i] = nb_codes / 2; // # of non-leaf nodes on level i
> + nb_codes = codes_count[i] + curr; // # of nodes on level i
> }
>
> - code = 0;
> - for (i = last; i >= 0; i--) {
> - codes[i] = code >> (32 - he[i].len);
> - bits[i] = he[i].len;
> - syms[i] = he[i].sym;
> - code += 0x80000000u >> (he[i].len - 1);
> + for (unsigned i = nb_elems; i-- > 0;) {
> + if (!bits[i]) {
> + codes[i] = 0;
> + continue;
> + }
> + codes[i] = codes_count[bits[i]]++;
> }
> #define VLC_BITS 11
> - return ff_init_vlc_sparse(vlc, VLC_BITS, last + 1,
> - bits, sizeof(*bits), sizeof(*bits),
> - codes, sizeof(*codes), sizeof(*codes),
> - syms, sizeof(*syms), sizeof(*syms), 0);
> + return init_vlc(vlc, VLC_BITS, nb_elems,
> + bits, sizeof(*bits), sizeof(*bits),
> + codes, sizeof(*codes), sizeof(*codes), 0);
> }
>
> static int decode_plane10(UtvideoContext *c, int plane_no,
> --
> 2.25.1
>
> _______________________________________________
> ffmpeg-devel mailing list
> ffmpeg-devel@ffmpeg.org
> https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
>
> To unsubscribe, visit link above, or email
> ffmpeg-devel-requ...@ffmpeg.org with subject "unsubscribe".
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
To unsubscribe, visit link above, or email
ffmpeg-devel-requ...@ffmpeg.org with subject "unsubscribe".
