From patchwork Tue Nov 10 10:47:04 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Rheinhardt X-Patchwork-Id: 23468 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 D3800449B06 for ; Tue, 10 Nov 2020 12:49:29 +0200 (EET) Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id B05ED68BD9F; Tue, 10 Nov 2020 12:49:29 +0200 (EET) X-Original-To: ffmpeg-devel@ffmpeg.org Delivered-To: ffmpeg-devel@ffmpeg.org Received: from mail-wm1-f67.google.com (mail-wm1-f67.google.com [209.85.128.67]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id 7D6A468BD89 for ; Tue, 10 Nov 2020 12:49:26 +0200 (EET) Received: by mail-wm1-f67.google.com with SMTP id w24so2550144wmi.0 for ; Tue, 10 Nov 2020 02:49:26 -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=PrsJLGJA9tsJg/R1fYEhFLlUcxqj7RJe6NVg0YYCAnQ=; b=Tt6BQOcIHStZteCMbU18OvU5AUBGVt1/XOcFgYK91cNyBWimh0LzAKRSyYgg15+YI3 fQ8HolN4LagB/yPGhH17roj+rKvfhnWtto1tcuSAt3jQsAwtyQfuvdcF/kFM77N4STxa CnZpefYEmdK7TxU83C1K6o9ofzvOxnVcaAxFQgvSvxRX7qUv5z55sLPjuNo32vvK5Dts hyMCN1TZeuh7V9Mqr54kuOaiRU/0vBT5vajpA50pajk7ogfnEuH3PZAenD05NTRZrTUt 6rz0HFf28tkli4GUaUSwYd4tL8aOJwulmJWdimIK4WHLQqpNXmP8/DBVCAZhRdHaeepK pBug== 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=PrsJLGJA9tsJg/R1fYEhFLlUcxqj7RJe6NVg0YYCAnQ=; b=SalzCl6W8on/5C7oCiFjwBx2ZA6r9xcHCXF+blhjIjIibSS31NLmi5RymLlhsU7UP0 nhsPdD3Uw0pC+iyqG9KRRGnQTY2RMLL2i12G+nN/XcX4NDLnD+I964jfRB5WST16jw35 IQxZA+bKXtJI9vdqNNGt0K43NcuOcF62lGw28gxt0Vd0uj3OMMacMx0N0nntOV8cf0c4 sLrqm6gGeUmP6iH992HuVR/nJLVYoYB42mLoOTdQN1QfSkuGBoBMtt2bdEjqp+f2+8E4 VrooidQuOn6V6ORCVDW/oMEz4Olq1kea/ZbH3yv5zSaqtztkbNRxnWP2EfkkX8zr0J4y u/lA== X-Gm-Message-State: AOAM531n+EyLVo5J8UC79slRy2aNOHcp4lpYvjiye7bY794CVEMsHXAc 6BBBSGKnmMMpRXcSc5tdxkPrrker6uc= X-Google-Smtp-Source: ABdhPJz1WqZAsRSXI3DlNcZAh52I57R3KuIckBB0/jbiENh/K8yC/19fByxOcc08jXmN2njMXVwWeQ== X-Received: by 2002:a1c:a752:: with SMTP id q79mr3962649wme.24.1605005365654; Tue, 10 Nov 2020 02:49:25 -0800 (PST) Received: from sblaptop.fritz.box (ipbcc1aa4b.dynamic.kabel-deutschland.de. [188.193.170.75]) by smtp.gmail.com with ESMTPSA id l24sm2572543wmi.7.2020.11.10.02.49.24 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 10 Nov 2020 02:49:25 -0800 (PST) From: Andreas Rheinhardt To: ffmpeg-devel@ffmpeg.org Date: Tue, 10 Nov 2020 11:47:04 +0100 Message-Id: <20201110104851.321029-8-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 007/114] avcodec/smacker: Improve creating Huffman VLC 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" The Smacker Huffman tables are already stored in a tree-like structure; in particular, they are naturally ordered from left to right in the tree and are therefore suitable to be initialized by ff_init_vlc_from_lengths() which avoids traversing the data twice in order to sort only the codes that are so long that they need into a subtable. This improves performance (and reduces codesize): For the sample from ticket #2425 the number of decicycles for parsing and creating the VLCs in smka_decode_frame() decreased from 412322 to 359152 (tested with 10 runs each looping 20 times over the file). Signed-off-by: Andreas Rheinhardt --- libavcodec/smacker.c | 46 +++++++++++++++++++++----------------------- 1 file changed, 22 insertions(+), 24 deletions(-) diff --git a/libavcodec/smacker.c b/libavcodec/smacker.c index 6b1faec09e..19429f3b3e 100644 --- a/libavcodec/smacker.c +++ b/libavcodec/smacker.c @@ -62,14 +62,17 @@ typedef struct SmackVContext { int mmap_last[3], mclr_last[3], full_last[3], type_last[3]; } SmackVContext; +typedef struct HuffEntry { + uint8_t value; + uint8_t length; +} HuffEntry; + /** * Context used for code reconstructing */ typedef struct HuffContext { int current; - uint32_t bits[256]; - uint8_t lengths[256]; - uint8_t values[256]; + HuffEntry entries[256]; } HuffContext; /* common parameters used for decode_bigtree */ @@ -105,7 +108,7 @@ enum SmkBlockTypes { * Can read SMKTREE_DECODE_MAX_RECURSION before the first check; * does not overread gb on success. */ -static int smacker_decode_tree(GetBitContext *gb, HuffContext *hc, uint32_t prefix, int length) +static int smacker_decode_tree(GetBitContext *gb, HuffContext *hc, int length) { if (length > SMKTREE_DECODE_MAX_RECURSION || length > 3 * SMKTREE_BITS) { av_log(NULL, AV_LOG_ERROR, "Maximum tree recursion level exceeded.\n"); @@ -119,18 +122,15 @@ static int smacker_decode_tree(GetBitContext *gb, HuffContext *hc, uint32_t pref } if (get_bits_left(gb) < 8) return AVERROR_INVALIDDATA; - hc->bits[hc->current] = prefix; - hc->lengths[hc->current] = length; - hc->values[hc->current] = get_bits(gb, 8); - hc->current++; + hc->entries[hc->current++] = (HuffEntry){ get_bits(gb, 8), length }; return 0; } else { //Node int r; length++; - r = smacker_decode_tree(gb, hc, prefix, length); + r = smacker_decode_tree(gb, hc, length); if(r) return r; - return smacker_decode_tree(gb, hc, prefix | (1U << (length - 1)), length); + return smacker_decode_tree(gb, hc, length); } } @@ -216,22 +216,21 @@ static int smacker_decode_header_tree(SmackVContext *smk, GetBitContext *gb, int i ? "high" : "low"); continue; } - err = smacker_decode_tree(gb, &h, 0, 0); + err = smacker_decode_tree(gb, &h, 0); if (err < 0) goto error; skip_bits1(gb); if (h.current > 1) { - err = ff_init_vlc_sparse(&vlc[i], SMKTREE_BITS, h.current, - h.lengths, sizeof(*h.lengths), sizeof(*h.lengths), - h.bits, sizeof(*h.bits), sizeof(*h.bits), - h.values, sizeof(*h.values), sizeof(*h.values), - INIT_VLC_LE); + err = ff_init_vlc_from_lengths(&vlc[i], SMKTREE_BITS, h.current, + &h.entries[0].length, sizeof(*h.entries), + &h.entries[0].value, sizeof(*h.entries), 1, + 0, INIT_VLC_OUTPUT_LE); if (err < 0) { av_log(smk->avctx, AV_LOG_ERROR, "Cannot build VLC table\n"); goto error; } } else - ctx.vals[i] = h.values[0]; + ctx.vals[i] = h.entries[0].value; } escapes[0] = get_bits(gb, 16); @@ -650,21 +649,20 @@ static int smka_decode_frame(AVCodecContext *avctx, void *data, HuffContext h; h.current = 0; skip_bits1(&gb); - if ((ret = smacker_decode_tree(&gb, &h, 0, 0)) < 0) + if ((ret = smacker_decode_tree(&gb, &h, 0)) < 0) goto error; skip_bits1(&gb); if (h.current > 1) { - ret = ff_init_vlc_sparse(&vlc[i], SMKTREE_BITS, h.current, - h.lengths, sizeof(*h.lengths), sizeof(*h.lengths), - h.bits, sizeof(*h.bits), sizeof(*h.bits), - h.values, sizeof(*h.values), sizeof(*h.values), - INIT_VLC_LE); + ret = ff_init_vlc_from_lengths(&vlc[i], SMKTREE_BITS, h.current, + &h.entries[0].length, sizeof(*h.entries), + &h.entries[0].value, sizeof(*h.entries), 1, + 0, INIT_VLC_OUTPUT_LE); if (ret < 0) { av_log(avctx, AV_LOG_ERROR, "Cannot build VLC table\n"); goto error; } } else - values[i] = h.values[0]; + values[i] = h.entries[0].value; } /* this codec relies on wraparound instead of clipping audio */ if(bits) { //decode 16-bit data