From patchwork Sun Oct 2 00:10:17 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Rheinhardt X-Patchwork-Id: 38511 Delivered-To: ffmpegpatchwork2@gmail.com Received: by 2002:a05:6a20:3b1c:b0:96:9ee8:5cfd with SMTP id c28csp528347pzh; Sat, 1 Oct 2022 17:10:28 -0700 (PDT) X-Google-Smtp-Source: AMsMyM70czMebxR3jfmrqhLZfPX7CCNARP864I2Xq6MTx9F/Vc9tpkb4DGSL6hCv5i/CP6bLeQbk X-Received: by 2002:a17:906:ee8e:b0:730:4a24:f311 with SMTP id wt14-20020a170906ee8e00b007304a24f311mr11185528ejb.420.1664669428666; Sat, 01 Oct 2022 17:10:28 -0700 (PDT) Return-Path: Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org. [79.124.17.100]) by mx.google.com with ESMTP id sh14-20020a1709076e8e00b00781a47397b1si4648550ejc.502.2022.10.01.17.10.28; Sat, 01 Oct 2022 17:10:28 -0700 (PDT) Received-SPF: pass (google.com: domain of ffmpeg-devel-bounces@ffmpeg.org designates 79.124.17.100 as permitted sender) client-ip=79.124.17.100; Authentication-Results: mx.google.com; dkim=neutral (body hash did not verify) header.i=@outlook.com header.s=selector1 header.b=qhKb9OOn; arc=fail (body hash mismatch); spf=pass (google.com: domain of ffmpeg-devel-bounces@ffmpeg.org designates 79.124.17.100 as permitted sender) smtp.mailfrom=ffmpeg-devel-bounces@ffmpeg.org; dmarc=fail (p=NONE sp=QUARANTINE dis=NONE) header.from=outlook.com Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id 3BCA368BB7E; Sun, 2 Oct 2022 03:10:26 +0300 (EEST) X-Original-To: ffmpeg-devel@ffmpeg.org Delivered-To: ffmpeg-devel@ffmpeg.org Received: from EUR05-DB8-obe.outbound.protection.outlook.com (mail-db8eur05olkn2028.outbound.protection.outlook.com [40.92.89.28]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id 7171568BB36 for ; Sun, 2 Oct 2022 03:10:19 +0300 (EEST) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=Wj4JDBfeF8X2W2Ki5SRSFIjfu77X43qshEQZ7snQTagcq11ckLMqcDPOAAKdhvQPs6vrijZFrjXuwQH/gQBT7XNAb0pJXu6qP31s/71QrBKbFzh/vWk4/Zql9yRAc3kUqadvgI2MHEvdYWifMStZDsPNK4od3RBrmjsAmTL2iD12j+jLaK0anxWRa8+RfcYy6dazvDmQ4XJ5bnmISF0yn/mylr0OrqGVkMIXaap6DVPWuav/34nbzQ1U4tDJusrjf7i9b/fD067zhJjsHLBzsl7YqQhRGGU6b+PkXakwIPAixZB1kbxLB6QTvPsbRFUpNSNd8hvzW7/Y+8Tp8Tfa3w== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=xHDa3FXSs65OuKkvHEO3vOQ04qhj0dzMyhSCth4JP/o=; b=GdVExmvcXIJtc2CGo6AKviG9EXAmQsfylZt7CQFAesxxy9NoSL4Xzae33USy4a2qfyi1V2eSy6Vq/YmdnljZnA4w98XVsJ/GODvqJL52SHEAcftUWuSNerDSZWe+PGeeXh1pWQv0fgMP5TuOmq27a4wk3y9S5O2vDInBp9n5chfzNy4JV3ZtpkOsobQSF45zMqraVUsXJbtieUgwxdVVcPyfDQ1cxJEokoJfjZGiajYqmV8PJj7HQK0UtPk9L12s2C9FxYR1N51s7izfJcBm+qkcGSmKL0X08BHstH8Or1bW6fSeeYAbxPkeBDgQt15L44+6lgc8tlC5dcax/Or2RA== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=none; dmarc=none; dkim=none; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=outlook.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=xHDa3FXSs65OuKkvHEO3vOQ04qhj0dzMyhSCth4JP/o=; b=qhKb9OOnmTjewVHymVKrUaQeH5m5PxCznqiqSTPrF3JkRvojF4Q3gHji+5aIxJzg7MHLoBx+DhG7lOVy5ePB8ng2GK+iJOE9m3fDde3/Q8TkTnlCkGmDwbwZQR9x1pDviTxL9+v6lMl24+/jkjPSqqahnf8VhDH1u8ie07ZEF7zuFBnfY+avgW0rDXD4geTGtpnLi/esZ5J33bPnGehaSikOhRaajO+XKg8rCX7a9qvBXgYN8fmxsaslQF8cmk8mifGp85fQZ850DBbYxt2dFOU2+X1BbuzvTqlaWDVBtfm+3Inx03C5/eY9yUXIi5IRCRf6hwALY/l9gCGBx2GI8w== Received: from GV1P250MB0737.EURP250.PROD.OUTLOOK.COM (2603:10a6:150:8e::17) by GV2P250MB0997.EURP250.PROD.OUTLOOK.COM (2603:10a6:150:d7::17) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5676.23; Sun, 2 Oct 2022 00:10:18 +0000 Received: from GV1P250MB0737.EURP250.PROD.OUTLOOK.COM ([fe80::68bd:2fc7:ac52:38f8]) by GV1P250MB0737.EURP250.PROD.OUTLOOK.COM ([fe80::68bd:2fc7:ac52:38f8%9]) with mapi id 15.20.5676.023; Sun, 2 Oct 2022 00:10:18 +0000 From: Andreas Rheinhardt To: ffmpeg-devel@ffmpeg.org Date: Sun, 2 Oct 2022 02:10:17 +0200 Message-ID: X-Mailer: git-send-email 2.34.1 In-Reply-To: References: X-TMN: [6eqAGnRtHJsBTNXjmXJWvRLJZMX38ksYTLxU+eULajk=] X-ClientProxiedBy: ZR0P278CA0082.CHEP278.PROD.OUTLOOK.COM (2603:10a6:910:22::15) To GV1P250MB0737.EURP250.PROD.OUTLOOK.COM (2603:10a6:150:8e::17) X-Microsoft-Original-Message-ID: <20221002001017.469643-1-andreas.rheinhardt@outlook.com> MIME-Version: 1.0 X-MS-Exchange-MessageSentRepresentingType: 1 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: GV1P250MB0737:EE_|GV2P250MB0997:EE_ X-MS-Office365-Filtering-Correlation-Id: 78841504-cfd3-4a48-dd4f-08daa40a7d00 X-MS-Exchange-SLBlob-MailProps: AZnQBsB9XmqRS+LhpAttTUY7UGhdHTSoOsstwIkOvW6Keb9Sz9WRvnfDlbh5SMMBAS/FNmKwne+/7vaBG8bhrLhIswtkI7AaTsN2GgiSNuPDTDL7LSuzNE5ZD9KCM9mBFukR0PH0DtDRX6WCYCtcma6yYAqFQFmHQ0cPAgZtzPxG6MmHc3A/HQoanlbqGCT3i9KkLlxPDJZi4oKH43HA69mOxTB+jB7/VcP2hWwTCW6CBVFZFfDjRmCSDHruOKMMCNf9kJ089WvRbz/hneRn0ZBwmjnSEXjwX2hpN++wFnsTThHCuz8mrKPL9bP0VovQL0UQtBXSo/5mSdW+KKpOa0WbROuYUGBe2A8Tm6/nytBLIUwFGGjeQGuChvAJkaJr+ig7LoRv+rH37hB0vatzCnmjk9w6ubwISoPMQoQjh9C8QsfyX+DQWn5apreB7DMzXUx9FDJdzuW3pUR/BnS3rEubvSTn4oQVOomj4p1Yuj0rxpaEPGT6mafHTFRjP1l+Vy5IMmoirMgNyK9Fgpn+XmbOZwKkQBhdb4p1sbwwv3/U9/bg8eg43P7MlchjEbv6BXlGrM4HgXoAd7gE9k+yYCrarwRydnW0CDWE0GrNDkOGbLKni7W3uicc1CyMoNqgxiOXJqoL4XcIxYPFF/lDnsRi4w/2MNV5lTfL9tqdqXAYnnhxw5DmaxcR520YQTVwD+VpaoJOYfpenXMXEiCSGFteELrOUfsc6BNoiM3nv3lveYzWi+5R4zb8Z/NEQ1X/UNaLJo79ExQ= X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: NaRjlNVEEjg7Y5Mdc0hE0vn4/ecXhKGr+t+FArseVxSP1irSim7+IyzDsG5VdyHBO7O1Xb6OnC0/9d7dnB9p0m6UqxbNELc7/CQ6vlRsIItN2jYP0wlCyDie2iZHegppcGKvqHmtoT9H7udzdal+l2DmIjUuOHnNRU/VRs2rVS0d4e4ssHvKRS72srUrt8DQsYEb/Ew0d29xcAfCFtWSSCvgEbjCzdgi+oYON/2/zWetqIXmzWyk0HHl8TaethhJQTE7/sWfG+xZ+3A4PP0hsk//ys9FbhUq5zf4Q+qIYrpqHmMm22Ie8walfyrjm5nAqsp0dxjCysDHKANxZLdww3XH71z+WyLuoQYnMYE+JhWIqBrytMdqFjQTz2odpDiIhK9wjCdPLO3fBP8zwWqHANk1WHItMmDq8NGqr8EJlReyFNdnd1Ls5h46vGPbhdug/3dcocIngok8Q5jCEf0zGRUB0lvjMcburndPC5/5qUAEEsxqt8mhIwX/opMQEbDFGiLnEabL9slkH57XGAIQTdh/cwjnZDJQN/x63IvP9dXBMzdMoULfHkfdzAEV2WIuNs32EsQkOLtUJol2aZ5uTOucy12MLHkyWPWvxqf8ldS3mR8JNIIxGTMCUN8N39QUyToIc6y/Y1eOAwJKs/pLFaw2nR98j7pen2YyTBzk3kJa1iQKdsvlf7cy9KRfKiF0 X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: roZkRXHxnjCz+KSVCIi/JVmt1Gh85FQgBF8swEACbMRRCkWYhMFE9NFu8nxOkB7M747pMgpL4bT83m4C2kLTdJphbvT6CSVwtjk5s40b0fy0lKWwXSGb9Sfzl0M8hcsq/AthZ/Zmh78HrZ7B8zOw0U3MBQCP1U6xALxxwtZ63dv7T/OqbVydGgAUMUEoHylxNZFAufaIlReZOMbzTYZEwEqOjZGPIScBnubQWTTRQ0cnNsT1ya6eeGP1MpbHNjLG0U1XTgdTgPBd4qdfZLXi2WxHLFtnamPWQRzaV9D+o2zUx8oqTE5qCpJvL5GHBm+juKWSH2pO4QoLGg3cc1iED4DB1g/GWNIHL9QdNggwXdox3cGMjvv4zuhDCsTtdimnMK/Qf4xoJ5W0CnfIi5ydWxbdpMKFQ3prTdfnnaXavmf5+/vX5vQamyJCT1IxRNzaHcSvql2X0JdaDKkvu644VzxiU7wKFgETpWzLPWwBtjhH6ZMmFLDIkcMQjg2rc5wYvLHLxViSq2eTJZnc3zSbl2W9TUgwRWJsEOTtbPRv3gYJfRhP5FU5zRy/j+L6Y9W0kEfvSPu7w02Rcay0y+7Kjx6i9wkJnB4JfqwYRskuZUuSVLMFCQ2b/1Vlu2xORsf0+/BqxpuKs+Af58LOOmsruymVLq6sabS2oL6xLIDD/vGIvpSTzo6pvRo6IlBCSpNZk7OkIwoT+Pj4GDLME/qA24KoCPRU87DZ1E25TkjcRV2YB/o/FaTdjmPkRSiiMUk8POZ4pdZm7dMVdhAxWFgDtowar4aS0sTtDpqIPGbcc6fI7cRMZhXb2LhS1DyPSS8eZCybnn3z3BiyHMQvMdWfBdPrfw4zXuuJ5TIgrG6go2TURkxo0FAZW+7Jqn7Assg02O1jsr2yLQS+bWyxHLHAtI36q1oq0+QGNJx5oEYD5iEN2HFnGeswqGyS+ohYdYrDqkZQYDb5rWT7dFjfnnm0RH6EkJOCUGI3DQLXLNsJlUQDd7SYV3Xqk+y+0z1tLAzytwoSPj3tBzPDq9MMb0dhaw0YypfDdgdfBeX4My9qpvoDf0HO21Oyb6U93eFo+aNUY3vi3LciQCdhI2Wvak9W0g5pWcG6XREyVYw7r1h6psq8XMCaDHfGz6SqJTMlSf0DL3ze4Gh++/4uuN32WT8X1AkqfMa4nQtkwQRYbJHu/XigBOaOh6GDiM2OvS5FqibZ3Q1rPMsKtNonwRdcJOqSxPpOr4SGoTUzHF4YLqguguuEwyiMBBikAURVPfX6DgZSFSTdDtRVHxd7xdcnTkj6oS0LRpPWicFbdvNGukIZVcY= X-OriginatorOrg: outlook.com X-MS-Exchange-CrossTenant-Network-Message-Id: 78841504-cfd3-4a48-dd4f-08daa40a7d00 X-MS-Exchange-CrossTenant-AuthSource: GV1P250MB0737.EURP250.PROD.OUTLOOK.COM X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 02 Oct 2022 00:10:18.2059 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: 84df9e7f-e9f6-40af-b435-aaaaaaaaaaaa X-MS-Exchange-CrossTenant-RMS-PersistedConsumerOrg: 00000000-0000-0000-0000-000000000000 X-MS-Exchange-Transport-CrossTenantHeadersStamped: GV2P250MB0997 Subject: [FFmpeg-devel] [PATCH 14/14] avcodec/huffyuv: Speed up generating Huffman codes X-BeenThere: ffmpeg-devel@ffmpeg.org X-Mailman-Version: 2.1.29 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" X-TUID: CLtRED4Sg8wO The codes here have the property that the long codes are to the left of the tree (each zero bit child node is by definition to the left of its one bit sibling); they also have the property that among codes of the same length, the symbol is ascending from left to right. These properties can be used to create the codes from the lengths in only two passes over the array of lengths (the current code uses one pass for each length, i.e. 32): First one counts how many nodes of each length there are. Then one calculates the range of codes of each length (possible because the codes are ordered by length in the tree). This enables one to calculate the actual codes with only one further traversal of the length array. Signed-off-by: Andreas Rheinhardt --- Given that the long codes are to the left of the tree, one can actually use uint16_t here despite the codes being up to 32 bits long (so many leading digits have to be zero that the codes fit into uint16_t). libavcodec/huffyuv.c | 22 +++++++++++++--------- 1 file changed, 13 insertions(+), 9 deletions(-) diff --git a/libavcodec/huffyuv.c b/libavcodec/huffyuv.c index bbe4b952b0..6bcaacfc37 100644 --- a/libavcodec/huffyuv.c +++ b/libavcodec/huffyuv.c @@ -39,19 +39,23 @@ int ff_huffyuv_generate_bits_table(uint32_t *dst, const uint8_t *len_table, int n) { - int len, index; - uint32_t bits = 0; + int lens[33] = { 0 }; + uint32_t codes[33]; - for (len = 32; len > 0; len--) { - for (index = 0; index < n; index++) { - if (len_table[index] == len) - dst[index] = bits++; - } - if (bits & 1) { + for (int i = 0; i < n; i++) + lens[len_table[i]]++; + + codes[32] = 0; + for (int i = FF_ARRAY_ELEMS(lens) - 1; i > 0; i--) { + if ((lens[i] + codes[i]) & 1) { av_log(NULL, AV_LOG_ERROR, "Error generating huffman table\n"); return -1; } - bits >>= 1; + codes[i - 1] = (lens[i] + codes[i]) >> 1; + } + for (int i = 0; i < n; i++) { + if (len_table[i]) + dst[i] = codes[len_table[i]]++; } return 0; }