From patchwork Fri Nov 20 07:18:41 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Rheinhardt X-Patchwork-Id: 23752 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 9119244A644 for ; Fri, 20 Nov 2020 09:24:21 +0200 (EET) Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id 5A19068B9B9; Fri, 20 Nov 2020 09:24:21 +0200 (EET) X-Original-To: ffmpeg-devel@ffmpeg.org Delivered-To: ffmpeg-devel@ffmpeg.org Received: from mail-ej1-f66.google.com (mail-ej1-f66.google.com [209.85.218.66]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id E734768B9AC for ; Fri, 20 Nov 2020 09:24:13 +0200 (EET) Received: by mail-ej1-f66.google.com with SMTP id 7so11517635ejm.0 for ; Thu, 19 Nov 2020 23:24:13 -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=sjcVtiurTCBhciIlqJSOcRZliYDRUwK2BJ+EBO6G6Lg=; b=KTp8a4g0p3vgjxQckTJBMItzdLmJ08uEw0BXoa9okNWkAKUGE8ebrknNZ6Kb2uX5vh 1hFtQLOEEf2NwrVCvcVqPb1PMH0C0mh7HZ2AkhASeGu5wiPqzfZbrQ+ctkzuU8YGp5bL mYHRHHzx1zpzWFjykaUM/1CktPOXyQVwZy6YvfHN3HrNT3PWl8uvGPkTEaBNe4WM7W0S MybCTU5CKHnItoAt9Qsr55Lp0kjqbvYXh2Wu25IvmB6uzwfxmmZ35QHgnZJMKebHCNtg XiqUjEY0Tg5Du6ggUiDQK39BdPExxFxsKoObseflP8PdCaBLonszyDlqQu/vGZi1Wpkx hN2A== 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=sjcVtiurTCBhciIlqJSOcRZliYDRUwK2BJ+EBO6G6Lg=; b=CgWxq8Wm8tnLNAkb53YjsRoLBUQ8uFLZr0XOLZ6/XUiCx0xKU1kIMzrXvFt8ioTpR8 XlfQsbBlEx1JbTBYSRtDhBfDAWxzaG8OXAerUwq2M6i/dKhiE1BYfyUKj86/LytVH3a9 17Aawzx61UEz1RQ7iBa+8Ec4JsL+6k2QoGBxQPBB3q6UvgFdfBL52OCCuHf3jOzWj7wd lXWdVBU4UNkl7elYlCCy9q8WXG8WfbbfJQN0/Gyav1d/6aTgRzFWZRTvlvV+ok1j6056 1YegPAVJ6anxpdBi65bhGZrRu4Z46xF7nifXHTpiG4cATjOUO41GyZ9Ucwe91EN9pll6 aQfw== X-Gm-Message-State: AOAM533zI6Hv/yuq5qcOrnn1qv6mfWatPhXfnwyYjRCuk4Byh7lZl7xY fFkgbAf/qAI1kct3CgjflS+0xu/fC0Xb7A== X-Google-Smtp-Source: ABdhPJz9iIN7D8uF+4SCubW2eauD2uCO9dQwDI3R1JaaNXYbfxY8JZHxkmWRX3V/ls4mFmJ4RujBWg== X-Received: by 2002:a17:906:35da:: with SMTP id p26mr31806919ejb.256.1605857053019; Thu, 19 Nov 2020 23:24:13 -0800 (PST) Received: from sblaptop.fritz.box (ipbcc1aa4b.dynamic.kabel-deutschland.de. [188.193.170.75]) by smtp.gmail.com with ESMTPSA id lz27sm779419ejb.39.2020.11.19.23.24.12 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 19 Nov 2020 23:24:12 -0800 (PST) From: Andreas Rheinhardt To: ffmpeg-devel@ffmpeg.org Date: Fri, 20 Nov 2020 08:18:41 +0100 Message-Id: <20201120072116.818090-9-andreas.rheinhardt@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20201120072116.818090-1-andreas.rheinhardt@gmail.com> References: <20201120072116.818090-1-andreas.rheinhardt@gmail.com> MIME-Version: 1.0 Subject: [FFmpeg-devel] [PATCH v2 008/162] 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..871a76257a 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, smk->avctx); 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, avctx); 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