From patchwork Tue Nov 10 10:58:32 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Rheinhardt X-Patchwork-Id: 23576 Return-Path: X-Original-To: patchwork@ffaux-bg.ffmpeg.org Delivered-To: patchwork@ffaux-bg.ffmpeg.org Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org [79.124.17.100]) by ffaux.localdomain (Postfix) with ESMTP id 5DBB544B529 for ; Tue, 10 Nov 2020 13:16:24 +0200 (EET) Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id CF8A268C0CB; Tue, 10 Nov 2020 12:59:41 +0200 (EET) X-Original-To: ffmpeg-devel@ffmpeg.org Delivered-To: ffmpeg-devel@ffmpeg.org Received: from mail-wm1-f66.google.com (mail-wm1-f66.google.com [209.85.128.66]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id 3C60668C09E for ; Tue, 10 Nov 2020 12:59:34 +0200 (EET) Received: by mail-wm1-f66.google.com with SMTP id c9so2544954wml.5 for ; Tue, 10 Nov 2020 02:59:34 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references:reply-to :mime-version:content-transfer-encoding; bh=C52pJRJUWmycv9jPVF98r0s1VfQfwB8vRSq446BOP9w=; b=MBtCBWx3hBjGsd1uQiVbe1x7jHoXofkYKpdXQo8Z1uYTdwQRDPkp2UJ/0yOct5LYT9 SosPNYlvQLEOiiKpdXEd7W9wzny2rYTe+ja+T27hk06njosdrYcFLIkGmx+pxcLf5fQs +yi9Bt9gE06UAik3jIoGZFs+Aw3sKeZYWg4smbFLuO5hIg9uTY7Xbcmj7uH+X5eSzuaZ RYkF+JRFkBiNWUnlqPVmbi10Nw+ne6lPgl80QnxSZ+9gafpqAVQQ704P3+U030EIgpxs Jcm/pTMm+zRmDJdwa9KsomdDgEHYZPk3vFrlYlBAXP8heaakOVDIcPLAPrqbptBXAK/o OkyA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:reply-to:mime-version:content-transfer-encoding; bh=C52pJRJUWmycv9jPVF98r0s1VfQfwB8vRSq446BOP9w=; b=tW/VxHVuBNUiweeKmCkrg96UcjNT/zJ+ejikjckrqYE/FLI9PwVkrHqETkkNTMcd3+ qW621ZCCMVpzwVu+M82YJSLjdFBkKiavSxYtr2ktICz/mv8yO+z0jhe0bs1/tSJpq2qb jdgw58VJAqUfMlNYwORQpiyXd03eBDjJNkUVLFsgWEcayxwB7gvUiD/mdtjvVaCFgWol mvKUS8HMG98EIinbSy/Sf9qnEwY+xS7kP/6NhPU3u0jyYD+nMm7ya5C/2aCUYL2CT39J kzvIJ5u2bbaiIi7N9ReBt/qqJPZYJoibWMKymmX8mEW7qwwXI6w+jGB7k2o7zg0+XPNd bTEQ== X-Gm-Message-State: AOAM533DNVygKpZcXOEQ/zB+9pIvnohtn7j0LJV9w3foza58IOMB4RxY TsXJRXgcyQloIx4Mk6ogwn9E9lCvysk= X-Google-Smtp-Source: ABdhPJxhbG0TqXldW8DZV0vZCTNw5ByfwYESl4mV58lk1IROieixcL6HTTB5j1H1y3F/BXdeKKIEUA== X-Received: by 2002:a1c:3803:: with SMTP id f3mr4029281wma.14.1605005973360; Tue, 10 Nov 2020 02:59:33 -0800 (PST) Received: from sblaptop.fritz.box (ipbcc1aa4b.dynamic.kabel-deutschland.de. [188.193.170.75]) by smtp.gmail.com with ESMTPSA id o197sm2561308wme.17.2020.11.10.02.59.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 10 Nov 2020 02:59:32 -0800 (PST) From: Andreas Rheinhardt To: ffmpeg-devel@ffmpeg.org Date: Tue, 10 Nov 2020 11:58:32 +0100 Message-Id: <20201110105836.321916-19-andreas.rheinhardt@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20201110104851.321029-1-andreas.rheinhardt@gmail.com> References: <20201110104851.321029-1-andreas.rheinhardt@gmail.com> MIME-Version: 1.0 Subject: [FFmpeg-devel] [PATCH 110/114] avcodec/magicyuv: Optimize creating Huffman tables X-BeenThere: ffmpeg-devel@ffmpeg.org X-Mailman-Version: 2.1.20 Precedence: list List-Id: FFmpeg development discussions and patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: FFmpeg development discussions and patches Cc: Andreas Rheinhardt Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" 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 --- libavcodec/magicyuv.c | 37 ++++++++++++++++--------------------- 1 file changed, 16 insertions(+), 21 deletions(-) diff --git a/libavcodec/magicyuv.c b/libavcodec/magicyuv.c index c7e2754c44..83bf14ae3a 100644 --- a/libavcodec/magicyuv.c +++ b/libavcodec/magicyuv.c @@ -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; }