@@ -47,7 +47,7 @@ typedef enum Prediction {
typedef struct HuffEntry {
uint8_t len;
- uint16_t code;
+ uint16_t sym;
} HuffEntry;
typedef struct MagicYUVContext {
@@ -72,27 +72,22 @@ typedef struct MagicYUVContext {
LLVidDSPContext llviddsp;
} MagicYUVContext;
-static int huff_build(HuffEntry he[], uint16_t codes_count[33],
+static int huff_build(const uint8_t len[], uint16_t codes_pos[33],
VLC *vlc, int nb_elems)
{
- unsigned nb_codes = 0, max = 0;
-
- for (int i = 32; 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
- if (curr && !max)
- max = i;
- }
+ HuffEntry he[4096];
+
+ for (int i = 31; i > 0; i--)
+ codes_pos[i] += codes_pos[i + 1];
+
+ for (unsigned i = nb_elems; i-- > 0;)
+ he[--codes_pos[len[i]]] = (HuffEntry){ len[i], i };
- for (unsigned i = 0; i < nb_elems; i++) {
- he[i].code = codes_count[he[i].len];
- codes_count[he[i].len]++;
- }
ff_free_vlc(vlc);
- return init_vlc(vlc, FFMIN(max, 12), nb_elems,
- &he[0].len, sizeof(he[0]), sizeof(he[0].len),
- &he[0].code, sizeof(he[0]), sizeof(he[0].code), 0);
+ return ff_init_vlc_from_lengths(vlc, FFMIN(he[0].len, 12), nb_elems,
+ &he[0].len, sizeof(he[0]),
+ &he[0].sym, sizeof(he[0]), sizeof(he[0].sym),
+ 0, 0);
}
static void magicyuv_median_pred16(uint16_t *dst, const uint16_t *src1,
@@ -384,7 +379,7 @@ static int build_huffman(AVCodecContext *avctx, const uint8_t *table,
{
MagicYUVContext *s = avctx->priv_data;
GetByteContext gb;
- HuffEntry he[4096];
+ uint8_t len[4096];
uint16_t length_count[33] = { 0 };
int i = 0, j = 0, k;
@@ -408,11 +403,11 @@ static int build_huffman(AVCodecContext *avctx, const uint8_t *table,
length_count[x] += l;
for (; j < k; j++)
- he[j].len = x;
+ len[j] = x;
if (j == max) {
j = 0;
- if (huff_build(he, length_count, &s->vlc[i], max)) {
+ if (huff_build(len, length_count, &s->vlc[i], max)) {
av_log(avctx, AV_LOG_ERROR, "Cannot build Huffman codes\n");
return AVERROR_INVALIDDATA;
}
MagicYUV transmits its Huffman trees by providing the length of the code corresponding to each symbol; then the decoder has to assemble the table in such a way that (i) longer codes are to the left of the tree and (ii) for codes of the same length the symbols are ascending from left to right. Up until now the decoder did this as follows: It counted the number of codes of each length and derived the first code of a given length via (ii). Then the array of lengths is traversed a second time to create the codes; there is one running counter for each length to do so. This process creates a default symbol table (that is omitted). This commit changes this as follows: Everything is indexed by the position in the tree (with codes to the left first); given (i), we can calculate the ranges occupied by the codes of each length; and with (ii) we can derive the actual symbols of each code; the running counters for each length are now used for the symbols and not for the codes. Doing so allows us to switch to ff_init_vlc_from_lengths(); this has the advantage that the codes table needs only be traversed once and that the codes need not be sorted any more (right now, the codes that are so long that they will be put into subtables need to be sorted so that codes that end up in the same subtable are contiguous). For a sample produced by our encoder (natural content, 4000 frames, YUV420p, ten iterations, GCC 9.3) this decreased the amount of decicycles for each call to build_huffman() from 1336049 to 1309401. Notice that our encoder restricts the code lengths to 12 and our decoder only uses subtables when the code is longer than 12 bits, so the sorting that can be avoided does not happen at the moment. If one reduces the decoder's tables to nine bits, the performance improvement becomes more apparent: The amount of decicycles for build_huffman() decreased from 1165210 to 654055. Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt@gmail.com> --- libavcodec/magicyuv.c | 37 ++++++++++++++++--------------------- 1 file changed, 16 insertions(+), 21 deletions(-)